COMPUTING SCIENCE

# A Tisket, a Tasket, an Apollonian Gasket

Fractals made of circles do funny things to mathematicians

In the spring of 2007 I had the good fortune to spend a semester at the Mathematical Sciences Research Institute in Berkeley, an institution of higher learning that takes “higher” to a whole new extreme. Perched precariously on a ridge far above the University of California at Berkeley campus, the building offers postcard-perfect vistas of the San Francisco Bay, 1,200 feet below. That’s on the west side. Rather sensibly, the institute assigned me an office on the east side, with a view of nothing much but my computer screen. Otherwise I might not have gotten any work done.

However, there was one flaw in the plan: Someone installed a screen-saver program on the computer. Of course, it had to be mathematical. The program drew an endless assortment of fractals of varying shapes and ingenuity. Every couple minutes the screen would go blank and refresh itself with a completely different fractal. I have to confess that I spent a few idle minutes watching the fractals instead of writing.

One day, a new design popped up on the screen *(see the figure above)*. It was different from all the other fractals. It was made up of simple shapes—circles, in fact—and unlike all the other screen-savers, it had numbers! My attention was immediately drawn to the sequence of numbers running along the bottom edge: 1, 4, 9, 16 … They were the perfect squares! The sequence was 1-squared, 2-squared, 3-squared, and so on.

Before I became a full-time writer, I used to be a mathematician. Seeing those numbers awakened the math geek in me. What did they mean? And what did they have to do with the fractal on the screen? Quickly, before the screen-saver image vanished into the ether, I sketched it on my notepad, making a resolution to find out someday.

As it turned out, the picture on the screen was a special case of a more general construction. Start with three circles of any size, with each one touching the other two. Draw a new circle that fits snugly into the space between them, and another around the outside enclosing all the circles. Now you have four roughly triangular spaces between the circles. In each of those spaces, draw a new circle that just touches each side. This creates 12 triangular pores; insert a new circle into each one of them, just touching each side. Keep on going forever, or at least until the circles become too small to see. The resulting foam-like structure is called an Apollonian gasket *(see the figure at right).*

Something about the Apollonian gasket makes ordinary, sensible mathematicians get a little bit giddy. It inspired a Nobel laureate to write a poem and publish it in the journal *Nature*. An 18th-century Japanese samurai painted a similar picture on a tablet and hung it in front of a Buddhist temple. Researchers at AT&T Labs printed it onto T-shirts. And in a book about fractals with the lovely title *Indra’s Pearls*, mathematician David Wright compared the gasket to Dr. Seuss’s *The Cat in the Hat*:

The cat takes off his hat to reveal Little Cat A, who then removes his hat and releases Little Cat B, who then uncovers Little Cat C, and so on. Now imagine there are not one but three cats inside each cat’s hat. That gives a good impression of the explosive proliferation of these tiny ideal triangles.

# Getting the Bends

Even the first step of drawing an Apollonian gasket is far from straightforward. Given three circles, how do you draw a fourth circle that is exactly tangent to all three?

Apparently the first mathematician to seriously consider this question was Apollonius of Perga, a Greek geometer who lived in the third century B.C. He has been somewhat overshadowed by his predecessor Euclid, in part because most of his books have been lost. However, Apollonius’s surviving book *Conic Sections* was the first to systematically study ellipses, hyperbolas and parabolas—curves that have remained central to mathematics ever since.

One of Apollonius’s lost manuscripts was called *Tangencies*. According to later commentators, Apollonius apparently solved the problem of drawing circles that are simultaneously tangent to three lines, or two lines and a circle, or two circles and a line, or three circles. The hardest case of all was the case where the three circles are tangent.

No one knows, of course, what Apollonius’ solution was, or whether it was correct. After many of the writings of the ancient Greeks became available again to European scholars of the Renaissance, the unsolved “problem of Apollonius” became a great challenge. In 1643, in a letter to Princess Elizabeth of Bohemia, the French philosopher and mathematician René Descartes correctly stated (but incorrectly proved) a beautiful formula concerning the radii of four mutually touching circles. If the radii are *r*, *s*, *t* and *u*, then Descartes’s formula looks like this:

^{1}/_{r2}+^{1}/_{s2}+^{1}/_{t2}+^{1}/_{u2}=^{ 1}/_{2 }(^{1}/_{r}+^{1}/_{s}+^{1}/_{t}+^{1}/_{u})^{2}.

All of these reciprocals look a little bit extravagant, so the formula is usually simplified by writing it in terms of the *curvatures* or the *bends* of the circles. The curvature is simply defined as the reciprocal of the radius. Thus, if the curvatures are denoted by *a*, *b*, *c* and *d*, then Descartes’s formula reads as follows:

*a*^{2}+*b*^{2}+*c*^{2}+*d*^{2}=(*a*+*b*+*c*+*d*)^{2}/2.

As the third figure shows, Descartes’s formula greatly simplifies the task of finding the *size* of the fourth circle, assuming the sizes of the first three are known. It is much less obvious that the very same equation can be used to compute the *location* of the fourth circle as well, and thus completely solve the drawing problem. This fact was discovered in the late 1990s by Allan Wilks and Colin Mallows of AT&T Labs, and Wilks used it to write a very efficient computer program for plotting Apollonian gaskets. One such plot went on his office door and eventually got made into the aforementioned T-shirt.

Descartes himself could not have discovered this procedure, because it involves treating the coordinates of the circle centers as complex numbers. Imaginary and complex numbers were not widely accepted by mathematicians until a century and a half after Descartes died.

In spite of its relative simplicity, Descartes’s formula has never become widely known, even among mathematicians. Thus, it has been rediscovered over and over through the years. In Japan, during the Edo period, a delightful tradition arose of posting beautiful mathematics problems on tablets that were hung in Buddhist or Shinto temples, perhaps as an offering to the gods. One of these “Japanese temple problems,” or *sangaku,* is to find the radius of a circle that just touches two circles and a line, which are themselves mutually tangent. This is a restricted version of the Apollonian problem, where one circle has infinite radius (or zero bend). The anonymous author shows that, in this case, *√a–+√b–=√c–, *a sort of demented version of the Pythagorean theorem. This formula, by the way, explains the pattern I saw in the screensaver. If the first two circles have bends 1 and 1, then the circle between them will have bend 4, because √1–+√1–=√4–. The next circle will have bend 9, because √1–+√4–=√9–. Needless to say, the pattern continues forever. (This also explains what the numbers in the first figure mean. Each circle is labeled with its own bend.)

Apollonian circles experienced perhaps their most glorious rediscovery in 1936, when the Nobel laureate (in chemistry, not mathematics) Frederick Soddy became mesmerized by their charm. He published in *Nature* a poetic version of Descartes’ theorem, which he called “The Kiss Precise”:

Four circles to the kissing come

The smaller are the benter.

The bend is just the inverse of

The distance from the center.

Though their intrigue left Euclid dumb,

There’s now no need for rule of thumb.

Since zero bend’s a dead straight line,

And concave bends have minus sign,

The sum of the squares of all four bends

Is half the square of their sum.

Soddy went on to state a version for three-dimensional spheres (which he was also not the first to discover) in the final stanza of his poem.

Ever since Soddy’s prosodic effort, it has become something of a tradition to publish any extension of his theorem in poetic form as well. The following year, Thorold Gosset published an *n*-dimensional version, also in *Nature*. In 2002, when Wilks, Mallows and Jeff Lagarias published a long article in the *American Mathematical Monthly*, they ended it with a continuation of Soddy’s poem entitled “The Complex Kiss Precise”:

Yet more is true: if all four discs

Are sited in the complex plane,

Then centers over radii

Obey the self-same rule again.

(The authors note that the poem is to be pronounced in the Queen’s English.)

# A Little Bit of Gasketry

To this point I have only written about the very beginning of the gasket- making process—how to inscribe one circle among three given circles. However, the most interesting phenomena show up when you look at the gasket as a whole.

The first thing to notice is the foamlike structure that remains after you cut out all of the discs in the gasket. Clearly the disks themselves take up an area that approaches 100 percent of the area within the outer disk, and so the area of the foam (known as the “residual set”) must be zero. On the other hand, the foam also has infinite length. Thus, in fact, it was one of the first known examples of a *fractal*—a curve of dimension between 1 and 2. Even today its dimension (denoted δ) is not known exactly; the best-proven estimate is 1.30568.

The concept of fractional dimension was popularized by Benoît Mandelbrot in his enormously influential book *The Fractal Geometry of Nature*. Although the meaning of dimension 1.30568 is somewhat opaque, this number is related to other properties of the foam that have direct physical meaning. For instance, if you pick any cutoff radius *r*, how many bubbles in the foam have radius larger than *r*? The answer, denoted *N*(*r*), is roughly proportional to *r*^{δ}. Or if you pick the *n* largest bubbles, what is the remaining pore space between those bubbles? The answer is roughly proportional to *n*^{1–2/δ}.

Physicists are very familiar with this sort of rule, which is called a *power law*. As I read the literature on Apollonian packings, an interesting cultural difference emerged between physicists and mathematicians. In the physics literature, a fractional dimension δ is *de facto *equivalent to a power law *r*^{δ}. However, mathematicians look at things through a sharper lens, and they realize that there can be additional, slowly increasing or slowly decreasing terms. For instance, *N*(*r*) could be proportional to *r*^{δ}log(*r*) or *r*^{δ}/log(*r*). For physicists, who study foams empirically (or semi-empirically, via computer simulation), the logarithm terms are absolutely undetectable. The discrepancy they introduce will always be swamped by the noise in any simulation. But for mathematicians, who deal in logical rigor, the logarithm terms are where most of the action is. In 2008, mathematicians Alex Kontorovich and Hee Oh of Brown University showed that there are in fact no logarithm terms in *N*(*r*). The number of circles of radius greater than *r* obeys a strict power law, *N*(*r*)∼*Cr*^{δ}, where *C* is a constant that depends on the first three circles of the packing. For the “bugeye” packing illustrated in the second figure, *C* is about 0.201. (The tilde (∼) means that this is not an *equation* but an *estimate* that becomes more and more accurate as the radius *r* decreases to 0.) For mathematicians, this was a major advance. For physicists, the likely reaction would be, “Didn’t we know that already?”

# Random Packing

For many physical problems, the classical definition of the Apollonian gasket is too restrictive, and a random model may be more appropriate. A bubble may start growing in a randomly chosen location and expand until it hits an existing bubble, and then stop. Or a tree in a forest may grow until its canopy touches another tree, and then stop. In this case, the new circles do not touch three circles at a time, but only one. Computer simulations show that these “random Apollonian packings” still behave like a fractal, but with a different dimension. The empirically observed dimension is 1.56. (This means the residual set is larger, and the packing is less efficient, than in a deterministic Apollonian gasket.) More recently, Stefan Hutzler of Trinity College Dublin, along with Gary Delaney and Tomaso Aste of the University of Canberra, studied the effect of bubbles with different shapes in a random Apollonian packing. They found, for example, that squares become much more efficient packers than circles if they are allowed to rotate as they grow, but surprisingly, triangles become only slightly more efficient. As far as I know, all of these results are begging for a theoretical explanation.

For mathematicians, however, the classical, deterministic Apollonian gasket still offers more than enough challenging problems. Perhaps the most astounding fact about the Apollonian gasket is that if the first four circles have integer bends, then *every other circle* in the packing does too. If you are given the first three circles of an Apollonian gasket, the bend of the fourth is found (as explained above) by solving a quadratic equation. However, every *subsequent* bend can be found by solving a *linear* equation:

*d*+*d'*=2(*a*+*b*+*c*)

For instance, in the “bugeye” gasket, the three circles with bends *a*=2, *b*=3, and *c*=15 are mutually tangent to two other circles. One of them, with bend *d*=2, is already given in the first generation. The other has bend *d'*=38, as predicted by the formula, 2+38=2(2+3+15). More importantly, even if we did not know *d'*, we would still be guaranteed that it was an integer, because *a*, *b*, *c* and *d* are.

Hidden behind this “baby Descartes equation” is an important fact about Apollonian gaskets: They have a very high degree of symmetry. Circles *a*, *b* and *c* actually form a sort of curved mirror that reflects circle *d* to circle *d'* and vice versa. Thus the whole gasket is like a kaleidoscopic image of the first four circles, reflected again and again through an infinite collection of curved mirrors.

Kontorovich and Oh exploited this symmetry in an extraordinary and amusing way to prove their estimate of the function *N*(*r*). Remember that *N*(*r*) simply counts how many circles in the gasket have radius larger than *r*. Kontorovich and Oh modified the function *N*(*r*) by introducing an extra variable of position—roughly equivalent to putting a lightbulb at a point *x *and asking how many circles illuminated by that lightbulb have radius larger than *r*. The count will fluctuate, depending on exactly where the bulb is placed. But it fluctuates in a very predictable way. For instance, the count is unchanged if you move the bulb to the location of any of its kaleidoscopic reflections.

This property makes the “lightbulb counting function” a very special kind of function, one which is invariant under the same symmetries as the Apollonian gasket itself. It can be broken down into a spectrum of similarly symmetric functions, just as a sound wave can be decomposed into a fundamental frequency and a series of overtones. From this spectrum, you can in theory find out everything you want to know about the lightbulb counting function, including its value at any particular location of the lightbulb.

For a musical instrument, the fundamental frequency or lowest overtone is the most important one. Similarly, it turned out that the first symmetric function was all that Kontorovich and Oh needed to figure out what happens to *N*(*r*) as *r* approaches 0.

In this way, a simple problem in geometry connects up with some of the most fundamental concepts of modern mathematics. Functions that have a kaleidoscopic set of symmetries are rare and wonderful. Kontorovich calls them “the Holy Grail of number theory.” Such functions were, for instance, used by Andrew Wiles in his proof of Fermat’s Last Theorem. An interesting new kaleidoscope is enough to keep mathematicians happy for years.

# Gaskets Galore

Kontorovich learned about the Apollonian kaleidoscope from his mentor, Peter Sarnak of Princeton University, who learned about it from Lagarias, who learned about it from Wilks and Mallows. For Sarnak, the Apollonian gasket is wonderful because it has neither too few nor too many mirrors. If there were too few, you would not get enough information from the spectral decomposition. If there were too many, then previously known methods, such as the ones Wiles used, would already answer all your questions.

Because Apollonian gaskets fall right in the middle, they generate a host of unsolved number-theoretic problems. For example, which numbers actually appear as bends in a given gasket? These numbers must satisfy certain “congruence restrictions.” For example, in the bugeye gasket, the only legal bends have a remainder of 2, 3, 6 or 11 when divided by 12. So far, it seems that every number that satisfies this congruence restriction does indeed appear in the figure somewhere. (The reader may find it amusing to hunt for 2, 3, 6, 11, 14, 15, 18, 23, etc.) “Computation indicates that every number occurs, but we can’t prove that even 1 percent of them actually occur!” says Ron Graham of the University of California at San Diego. For other Apollonian gaskets, such as the “coins” gasket in the fifth figure, there are some absentees—numbers that obey the congruence restrictions but don’t appear in the gasket. Sarnak believes, however, that the number of absentees is always finite, and beyond a certain point any number that obeys the congruence restrictions does appear somewhere in the gasket. At this point, though, he is far from proving this conjecture—the necessary math just doesn’t exist yet.

And even if all the problems concerning the classic Apollonian gaskets are solved, there are still gaskets galore for mathematicians to work on. As mentioned before, they could study random Apollonian gaskets. Another modification is the gasket shown in the last figure, where each pore is filled by three circles instead of one. Mallows and Gerhard Guettler have shown that such gaskets behave similarly to the original Apollonian gaskets—if the first six bends are integers, then all the rest of the bends are as well. Ambitious readers might want to work out the “Descartes formula” and the “baby Descartes formula” for these configurations, and investigate whether there are congruence restrictions on the bends.

Perhaps you, too, will be inspired to write a poem or paint a tablet in honor of Apollonius’ ingenious legagy. “For me, what’s attractive about Apollonian gaskets is that even my 14-year-old daughter finds them interesting,” says Sarnak. “It’s truly a god-given problem—or perhaps a Greek-given problem.”

EMAIL TO A FRIEND :