Counting Problems in Apollonian Circle Packings

I’ve spent most of the last year and a half contemplating pretty pictures like the one that follows. These pictures, called Apollonian circle packings, have captivated me since I heard Sarnak speak on them at the 2009 Joint Meetings.

Apollonian circle packing with root quadruple (-1,2,2,3)Apollonian circle packing with root quadruple (-1,2,2,3)

Pictures such as these are constructed by inscribing a triple of three circles inside a larger circle, inscribing a circle in each lune created, and iterating the process. The numbers labelling the circles are the curvatures (1/radius). (The exterior circle has radius 1, but because it is exterior we say that it’s curvature is -1 by convention.) To a number theorist, the amazing fact is that if the four circles we begin with have integral curvature (in the figure, the starting circles have curvature -1, 2, 2, 3), or indeed if any four mutually tangent circles in such a packing have integral curvature, all the rest of the circles automatically have integral curvature. Such pictures are called integer Apollonian circle packings (IACPs).

One question I like to think about, the one that got me into the subject, is to think about which numbers appear in IACPs. That is, think about all PACPs at once. How many times does a given curvature appear? What pairs of numbers can appear? How often? All of my counting is up to symmetry; the picture above, for example, accounts for only one occurrence of 6, not four, and only one occurrence of the pair (2,3).

It turns out that answers to these counting problems can be unexpectedly elegant.

(Note: as the “Out[56]” which I clumsily left in the picture suggests, I generated this diagram and all my other Apollonian pictures using Mathematica 7; please contact me if you’re interested in methods for constructing pictures of this sort.)

0. Some basics

Four numbers (a,b,c,d) are the curvatures of four mutually tangent circles iff they satisfy the Descartes equation a^2+b^2+c^2+d^2=2(ab+ac+ad+bc+bd+cd).

Given a triple of mutually tangent circles with curvatures (a,b,c), the possible curvatures of a fourth circle are the roots of the above equation, viewed as a quadratic in d; in general there are two possibilities, a+b+c\pm\sqrt{ab+ac+bc}. In particular, their sum is 2(a+b+c). If we know one curvature d, then the “other” possibility is d'=2(a+b+c)-d.

A nice upshot of this is that, if we know the curvatures of four mutually tangent circles in a packing, we can compute all the rest using only addition and subtraction!

1. Counting Occurrences of a Pair of Curvatures

Let a,b be fixed integers, at least one positive, and let us count the occurrences of adjacent circles of curvatures a,b.

The trick is to identify any occurrence of the pair of a,b with the doubly-infinite chain of circles/numbers tangent to both. For the (2,3) which appears in the above picture, the corresponding chain is \ldots,230,167,114,71,38,15,2,-1,6,23,50,87,134,191,\ldots. Can we characterize the chains attached to a pair (a,b)?

It’s easy to prove, using the equations in section 0, that if c is in such a chain, then all the curvatures in the chain have the form (a+b)n^2 + 2(\sqrt{ab+ac+bc})n + c for n\in\mathbb{Z}. The key is to realize that, for fixed a,b and varying c, all of these quadratic functions have the same leading coefficient (a+b) and the same minimum -\frac{ab}{a+b}.

Then what we are really counting is integer sequences of the form \ldots,f(-3+\alpha),f(-2+\alpha),f(-1+\alpha),f(\alpha),f(1+\alpha),f(2+\alpha),f(3+\alpha),\ldots, where f(x)=(a+b)x^2-\frac{ab}{a+b}, where without loss of generality we can take \alpha\in[0,1/2] (choices of \alpha which differ only by sign lead to the same sequence in reverse order). Such \alpha must have the form \frac{l}{a+b}, where l^2\equiv ab\pmod{a+b}, and 0\leq l\leq (a+b)/2.

In other words, there is a natural bijection between occurrences of (a,b) in IACPs and square roots \pm l of ab modulo a+b.

1½. Nice Special Case

What we’ve said so far applies for any pair of integers (a,b). In the special case where a,b are relatively prime, we can actually say a bit more, or at least a more aesthetically pleasing version of what we already said. Since, modulo a+b, we have ab\equiv -a^2. Since a is invertible modulo a+b, the square roots of -a^2 correspond to the square roots of -1. That is, if \gcd(a,b)=1, then the number of occurrences of the pair (a,b) up to symmetry is the number of square roots of -1 modulo a+b.

2. The Circumference of ACP(-1,2,2,3)

Let’s look harder at the specific packing pictured above. Since we only want to consider things up to symmetry, let’s just consider one quarter of the circle, from one of the 2’s to one of the 3’s. What numbers appear? In between 2 and 3 is 6. In between 2 and 6 is 11; in between 3 and 6 is 14. Etc. Perhaps motivated by the result of the previous section, note that each of these numbers is 1 more than the sum of squares.

If you have seen Farey fractions or the Stern-Brocot tree, you probably have a guess now as to what’s going on. The circle 2 corresponds to the fraction 0/1 (or, if you prefer, the pair (0,1)), the circle 3 corresponds to (1,1), and between circles a/b and c/d we inscribe a circle corresponding to (a+c)/(b+d). (A circle corresponding to (a,b) has curvature a^2+b^2+1.)

Once guessed, this is easy to prove by induction. If -1,\alpha=a^2+b^2+1,\beta=c^2+d^2+1,\gamma=(a+c)^2+(b+d)^2+1 appear as a mutually tangent quadruple of curvatures with \gamma “between” the other circles of positive curvature, then the circle in between \alpha and \gamma has curvature 2(\alpha+\gamma+(-1))-\beta, i.e. 2[a^2+b^2+1+(a+c)^2+(b+d)^2+1-1]-(c^2+d^2+1)=(2a+c)^2+(2b+d)^2+1 which is just what we hoped. Likewise the circle between \beta and \gamma has curvature (a+2c)^2+(b+2d)^2+1. This completes the induction.

Parting Shot.

Notice that section 2 does not depend logically on section 1. Also, the diagram shown is the only integral packing in which the external circle has radius 1, so the only occurrences of pairs (-1,b) with b>0 appear in this diagram. Combining all this, we have two independent descriptions of which numbers appear on the circumference of the packing shown and how often (up to symmetry).

  • Section 1 tells us that there is one occurrence of n for every pair of square roots \pm \eta of -1 modulo n-1.
  • Section 2 tells us that there is one occurrence of n for every expression n=a^2+b^2-1 where a/b is a fraction in lowest terms in the interval [0,1].

Rather surprisingly, we have obtained an alternate proof of the classical fact that the number of representations of an integer n in the form n=a^2+b^2 with 0\leq a\leq b and \gcd(a,b)=1 is equal to the number of (pairs of ) square roots of -1 modulo n!


Tags: , ,

2 Responses to “Counting Problems in Apollonian Circle Packings”

  1. Arun Iyengar Says:

    So this is the diagram you drew on the board in class. The modular arithmetic is a bit foreign to me as I have not taken any classes that involve MA. Do you have any recommendations on (introductory?) courses cover (at least) the basics of MA?

    • Cap Khoury Says:

      Modular arithmetic is part of elementary number theory, so any number theory course which doesn’t have another number theory course as a prerequisite must cover it.

      If it’s totally new to you, you might start here. If you’re more adventurous, why not just head over to Wikipedia and start poking around the See Also links?

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: