AMERICAN MATHEMATICAL MONTHLY

APRIL, 1999

The Mandelbrot Set, the Farey Tree, and the Fibonacci Sequence
by Robert L. Devaney
bob@bu.edu
In this paper we discuss several folk theorems involving the Mandelbrot set. Each of these theorems concerns the size of the bulbs or decorations attached to the Mandelbrot set. One may recognize the p/q bulbs from the geometry of their antennas. Moreover, the size of these bulbs is determined by the Farey tree. These results are proved using the theory of external rays of Douady and Hubbard, so we also give an explanation of their results.

Existence Proofs
by Fred Richman
richman@fau.edu
The difference between constructive and nonconstructive existence proofs is examined through three examples. Bezout's equation has well-known nonconstructive and constructive proofs. There is no known constructive proof that some digit appears infinitely often in the decimal expansion of pi. The zero-one valued function of f defined by f(n) = 1 if there are at least n consecutive 4's in the decimal expansion of pi, is computable according to the received wisdom. Yet no one has a program to compute it, and a proof that the program is right.

Introduction to Metric-Preserving Functions
by Paul Corazza
pcorazza@telegroup.com
When I was a graduate student, a professor asked us to verify that for any metric d, d/(1+d) is also a metric, topologically equivalent to d, while d/(1+d*d) is not generally a metric at all. I became curious about the possibility of characterizing those functions f, like x/(1+x), for which f(d(×)) is a metric, or a metric that is equivalent to d.

After coming up with such a characterization and obtaining a few related results, I learned that there is a substantial literature on the subject. This paper is a survey of this literature, containing a number of surprising results:

Every nondecreasing, subadditive function from the nonnegative reals to the nonnegative reals is metric-preserving.
Metric-preserving functions need not be continuous. Indeed, there exist nowhere continuous metric-preserving functions, and there are "more" metric-preserving functions than there are continuous functions.
If a metric-preserving function is continuous at 0, it is continuous everywhere.
A metric-preserving function f has the property that f(d(×)) is equivalent to d for every metric d if and only if f is continuous.
Every metric-preserving function has a (possibly infinite) derivative at 0. If it has a finite derivative at 0, then it's differentiable almost everywhere.

Magic Dice
by Bernard D. Flury, Robert Irving, and M. N. Goria
flury@indiana.edu, rwi@dcs.gla.ac.uk, mgoria@gelso.unitn.it
A magician offers her audience a game with two dice. For certain pairs of numbers (X,Y) shown by the two dice the magician wins 1 ruble, and for other combinations she loses 1 ruble. Sure enough, the magician wins all the time, despite the fact that two people who tally the frequencies of X and Y find that both dice take values 1 to 6 with the required probabilities of 1/6. A third observer tallies X + Y, but again nothing is found to be wrong. A fourth observer tallies X - Y, and a fifth observer X + 2Y, and still all frequencies are in agreement with the assumption that the two dice are fair and independent. However, when the magician is asked to admit a sixth observer she stops the game.

How many observers (that is, different linear combinations) can the magician admit and still cheat? For six-sided dice the answer is five. What if she uses 20-sided dice, or 1998-sided dice?

The Set of Differences of a Given Set
by Andrew Granville and Friedrich Roesler
andrew@math.uga.edu, roeslerf@mathematik.tu-muenchen.de
Given a finite set of integers, form all of the reduced fractions that result from dividing any one element of this set from any other. We show that there are at least as many distinct products of the numerator and denominator of such fractions as there were elements in the original set. We show how this (somewhat contrived sounding) result links up with many questions of current interest in number theory and combinatorial geometry. Several natural open questions are posed, both in terms of number theory and in terms of geometry, and a few partial results are given.

Six Ways of Looking at Burtin's Lemma
by S. Anoulova, J. Bennies, J. Lenhard, D. Metzler, Y. Sung, A. Weber
bennies@math.uni-frankfurt.de, lenhard@mathematik.uni-frankfurt.de, dmetzler@math.uni-frankfurt.de, y.sung@mathematik.uni-frankfurt.de, weber@compuserve.com
What is the probability that the graph of a non-uniform random mapping consists of only one component?

Consider a random mapping F : {1,..., n:} -> {0,..., n: }, where for each i its image F( i) is chosen independently according to given probability weights p ₀, ..., p_n. Associate a random graph consisting of vertices 0, 1, ..., n and edges, which are directed from each i to F( i ). Note that there is no edge pointing from 0 to another vertex.

Well, what is the probability that all vertices are connected to 0? The answer is surprisingly simple: it equals p_0. This result is known as Burtin's lemma and was originally proved by induction.

Should not such a simple result have a more simple proof? We arrived at six different approaches, which still leave the question open whether there is a most natural way of looking at Burtin's lemma.

NOTES

Lexell's Theorem Via an Inscribed Angle Theorem
by Hiroshi Maehara
hmaehara@edu.u-ryukyu.ac.jp

A Characteristic Property of Differentiation
by Khristo Boyadzhiev
k-boyadzhiev@onu.edu

A Weighted Mixed-Mean Inequality
by Kiran S. Kedlaya
kedlaya@math.mit.edu

UNSOLVED PROBLEMS

Periods in Taking and Splitting Games
by Ian Caines, Carrie Gates, Richard K. Guy, and Richard J. Nowakowski

PROBLEMS AND SOLUTIONS

REVIEWS

The French Mathematician
By Tom Petsinis

Reviewed by Tony Rothman
trothman@titan.iwu.edu

Social Constructivism as a Philosophy of Mathematics
By Paul Ernest

What is Mathematics, Really?
By Reuben Hersh

Reviewed by Bonnie Gold
bgold@mondec.monmouth.edu

TELEGRAPHIC REVIEWS