Growing Apollonian Packings

Colin Mallows Avaya Labs Basking Ridge, NJ 07920 USA

                   colinm@avaya.com

Abstract

In two dimensions, start with three mutually tangent circles, with disjoint interiors (a circle with negative radius has the point at infinity in its interior). We can draw two new circles that touch these three, and then six more in the gaps that are formed, and so on. This procedure generates an (infinite) Apollonian packing of circles. We show that the sum of the bends (curvatures) of the circles that appear in successive generations is an integer multiple of the sum of the bends of the original three circles. The same is true if we start with four mutually tangent circles (a Descartes configuration) instead of three. Also the integrality holds in three (resp., five) dimensions, if we start with four or five (resp. six or seven) mutually tangent spheres. (In four and higher dimensions the spheres in successive generations are not disjoint.) The analysis in the threedimensional case is difficult. There is an ambiguity in how the successive generations are defined. We are unable to give general results for this case.

1 Reflection and the Apollonian group

We draw on the definitions and analysis in [1, 2]. The “bend” of a circle or sphere is its curvature, = 1/radius. In n dimensions, a “Descartes configuration” consists of n + 2 mutually tangent spheres with disjoint interiors. The bends b_{i} of these spheres satisfy the Soddy-Gosset relation (see [2])

n(∑ b_{i}^{2}) = (∑ b_{i})^{2}.

Thus we can form n + 2 new Descartes configurations by deleting one of the spheres, say the i-th, and adding a new sphere tangent to the remaining n + 1 spheres, whose bend is the other root of the quadratic equation that is satisfied by b_{i}. We call this operation “Descartes reflection”. If the bends of the original set of n + 2 spheres are contained in the column vector b, the bends of the i-th new set are in the vector R_{i}b where

R_{i} = I + \frac{2}{n − 1}e_{i}1^{T} − \frac{2n}{n − 1}e_{i}e_{i}^{T} ,  (1)

where I is the unit (n + 2) × (n + 2) matrix, the column vector e_{i} has 1 in the i-th position and zeroes elsewhere, and 1 is a column of 1’s. Thus R_{i} is the identity matrix except for the -1 on the diagonal and 2/(n − 1) elsewhere. (See [2, Eq. 4.1].) Each of these n + 2 matrices is an involution, and they generate an infinite Coxeter group which we name G_{n}. In all dimensions except 3, there are no relations among them except the involutory ones: R_{i}^{2} = I. (See [2, Thm. 5.2]). However, in 3 dimensions there are extra relations (R_{i}R_{j})^{3} = I which will cause us difficulty below. Until further notice, we consider only dimensions n = 2 and n ≥ 4.

A word of length k, W = R_{i_{1}}R_{i_{2}} ⋯ R_{i_{k}}, in the generators of G_{n} is called reduced if i_{j} ≠ i_{j+1} for j = 1, …, k − 1. (So all squares have been cancelled). The number of reduced words of length k ≥ 1 is clearly (n + 2)(n + 1)^{k−1}.

We will derive the quantities s_{k}/s_{0} where s_{k} is the sum of the bends of the spheres that are generated in the kth generation of the Apollonian construction.

2 Starting with a Descartes configuration

We start with n + 2 spheres in an n-dimensional Descartes configuration, n ≠ 3. Since every application of a generator (in a reduced word) produces exactly one new sphere, the following lemma is clear.

Lemma 1. The spheres in the k-th generation (k ≥ 1) are in 1–1 correspondence with reduced words of length k in the generators of G_{n}.

Theorem 2. In n dimensions (n ≠ 3) the generating function of the sum of the bends in the kth generation is

G(x) = (1 − x)(1 − nx)s_{0}/(1 − θx + (n + 1)x^{2})

where θ = (n^{2} + n + 2)/(n − 1).

Proof. The sum of the bends in the kth generation is

s_{k} = ∑ e_{i_{1}}^{T}R_{i_{1}} ⋯ R_{i_{k}}b  (2)

where b is the vector containing the bends of the initial configuration, and the sum is over all sequences i_{1}, i_{2}, …, i_{k} with i_{j} ≠ i_{j+1}, j = 1, …, k − 1. We define

T = ∑_{j} R_{j}

Then T = aI + bJ where J is the matrix of all ones, a = (n^{2} − n − 2)/(n − 1), and b = 2/(n − 1). Let X_{k} be the row vector ∑ e_{i_{1}}R_{i_{1}} ⋯ R_{i_{k}} where the sum is as in (2). Then X_{0} = 1^{T}, X_{1} = ((n + 3)/(n − 1))1^{T}, and

X_{k+1} = X_{k}T − (n + 1)X_{k−1}

By induction, X_{k} = c_{k}1^{T} for some numbers c_{k} and a little work shows that

c_{0} = 1, c_{1} = (n + 3)/(n − 1), c_{k+1} = θc_{k} − (n + 1)c_{k−1}

The theorem follows.

The coefficients in G(x) are integer multiples of s_{0} only for n = 2, 5 (our analysis does not relate to n = 3). We find them to be

k = 0 1 2 3  4  5  6  7  8
n = 2 s_{k}/s_{0} = 1 5 39 297 2259 17181 130671 993825 7558587
n = 5 s_{k}/s_{0} = 1 2 15 108 774 5544 39708 284400 2036952

We remark, without giving details, that in all dimensions (except 3) a similar (but more tedious) computation shows that the sum of the squares of the bends in the k-th generation, t_{k} say, is a multiple of the sum of the squares of the bends in the zeroth generation, which is t_{0} = (1/n)s_{0}^{2}. The generating function is

(1 − x)(1 − nx)t_{0}/(1 − ϕ(n)x + (n + 1)x^{2})

where ϕ(n) = (n^{3} + 5n + 2)/(n − 1)^{2}. In two dimensions the multiples are integers:

\begin{matrix}k = & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ t_{k}/t_{0} = & 1 & 17 & 339 & 6729 & 133563 & 2651073 & 52620771 & 1044462201 \end{matrix}

In two dimensions the average bend in the kth generation, s̄_{k}, is asymptotically C_{1}μ^{k} where μ = (4 + \sqrt{1}3)/3, and the average squared bend t̄_{k} is asymptotically C_{2}ν^{k} where ν = (10 + \sqrt{9}7)/3. Thus the coefficient of variation of the bends in the kth generation is asymptotically Cλ^{k} − 1 where λ = 3ν/μ^{2} = 1.029427. One can conjecture that some transformation (such as taking logs) would give a limiting distribution. But since the higher moments are not independent of the starting configuration, it is not clear whether such a limit can exist independent of the initial configuration. For all n ≥ 4 as k → ∞ the coefficient of variation of the bends in the kth generation is of the form C(1 + ϵ)^{k} − 1 where ϵ is a small fraction.

3 Starting with n + 1 spheres

Now suppose we start with only n + 1 mutually tangent spheres, S_{1}, …, S_{n+1}, with bends summing to s_{0}^{−}, and with the sum of squares of the bends being t_{0}^{−}. By the Soddy-Gosset result, the two spheres that each touch all of these n + 1 spheres have bends a, a′ = (s_{0}^{−} ± q)/(n−1) where q^{2} = n(s_{0}^{−})^{2} −(n−1)t_{0}^{−}. Pick one of these two spheres and call it S_{n+2}, with bend b_{n+2} = a. Then S_{1}, …, S_{n+1}, S_{n+2} form a Descartes configuration, and the sum of the bends of this configuration is s_{0} = s_{0}^{−} + a. The first derived generation of spheres consists of S_{n+2} and the sphere obtained by reflecting this sphere in the original n + 1 spheres. The sum of these two bends is thus s_{1}^{−} = a + a′ = 2s_{0}^{−}/(n − 1). Again, the following lemma is clear.

Lemma 3. For k ≥ 1 the spheres in the (k + 1)st generation, starting from n + 1 spheres, are in 1–1 correspondence with reduced words in the generators of the group G_{n} of these two forms: (i) words of length k whose right-most element is not R_{n+2} (ii) words of length k + 1 whose right-most element is R_{n+2}.

The number of such words is 2(n + 1)^{k}.

Theorem 4. The generating function of the sum of the bends in the kth generation, starting from n + 1 spheres in n dimensions, is

G^{−}(x) = (1 − x)(1 − ((n^{2} + 1)/(n − 1))x)s_{0}^{−}/(1 − θx + (n + 1)x^{2})

Proof. Computations using the explicit form of R_{i} show that s_{2}^{−} = 2((n + 1)/(n − 1))^{2}s_{0}^{−}. For k ≥ 2 we have

s_{k+1}^{−} = ∑ e_{i_{1}}^{T}R_{i_{1}}...R_{i_{k}}(b + R_{n+2}b)

where the sum is over i_{j} ≠ i_{j+1}, i_{k} ≠ n + 2. Adding and subtracting the words that have i_{k} = n + 2, we get

s_{k+1}^{−} = s_{k} + s′_{k} − ∑ e_{i_{1}}^{T}R_{i_{1}}...R_{i_{k}−1}(R_{n+2}b + b)  (3)

where s′_{k} is the sum of the bends in the kth generation, starting from the full Descartes configuration with b_{n+2} = a′. In the summation in (3), we have i_{k−1} ≠ n + 2, so this sum is just s_{k}^{−}. Also, using the Soddy-Gosset equation, s_{0} + s′_{0} = (2n/(n − 1))s_{0}^{−}, so that for k ≥ 1

(s_{k+1}^{−} + s_{k}^{−})/s_{0}^{−} = (2n/(n − 1))s_{k}/s_{0} = (2n/(n − 1))c_{k}

in the notation of Theorem 2. Hence the required generating function satisfies

(1 + x)\frac{G^{−}(x)}{s_{0}^{−}} = 1 + \frac{n + 1}{n − 1}x + \frac{2nx}{n − 1} (\frac{G(x)}{s_{0}} − 1)

and the theorem follows.

For n = 2 we find

\begin{matrix}k = & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ s_{k}^{−}/s_{0}^{−} = & 1 & 2 & 18 & 138 & 1050 & 7986 & 60738 & 461946 & 3513354 \end{matrix}

and for k ≥ 3 these numbers satisfy the same recurrence as in the (n + 2)-sphere-start case. The generating function is (1 − x)(1 − 5x)/(1 − 8x + 3x^{2}).

Again, for k ≥ 3 the sum of the squares of the bends in the kth generation, t_{k}^{−}, satisfies the same recurrence as in the (n + 2)-start case; for n = 2 we find

\begin{matrix}k = & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ t_{k}^{−}/t_{0}^{−} = & 1 & 2 & 66 & 1314 & 26082 & 517698 & 10275714 & 203961186 \end{matrix}

and the generating function is (1 − 18x + 29x^{2})/(1 − 20x + 3x^{2}).

4 Three dimensions

The analogous problems for the 3-dimensional case, starting with either four or five tangent spheres, are much more difficult. Counting reduced words is challenging, and there is an indeterminacy in how the spheres are counted.

The reflection operators are 5 × 5 matrices as in Eq. (1), with all elements in {−1, 0, 1}. They satisfy

R_{i}^{2} = I, (R_{i}R_{j})^{3} = I  (4)

In [2] reduced words were defined as those that

(i) contain no subwords of the form R_{j}R_{j},

(ii) contain no subwords of the form V_{1}V_{2} ⋯ V_{2m} in which V_{1} = V_{3}, V_{2j} = V_{2j+3} for 1 ≤ j ≤ m − 2, and V_{2m−2} = V_{2m}.

Thus all possible cancellations using the identities in (4) have been performed. The definition implies that every subword of a reduced word is also reduced.

It is not the case that spheres correspond to reduced words. To see this, assume the zeroth generation is a five-sphere Descartes configuration in which the bends are 0, 0, 1, 1, 1. This consists of two parallel planes, distant 2 apart, with three unit spheres between them, touching each other and both planes. The first derived generation, obtained by Descartes reflection of each of these spheres, using single-letter words R_{i}, consists of five spheres, with bends 1, 1, 1, 3, 3. The second derived generation, obtained from words R_{i}R_{j} with i ≠ j, has 20 spheres, with bends 1^{6}3^{6}4^{6}6^{2}. In this generation the 20 spheres form 10 pairs, with the spheres in a pair (R_{i}R_{j} and R_{j}R_{i}) touching each other. The bends of the touching pairs are (1, 1)^{3}, (3, 4)^{6}, (6, 6)^{1}. Thus we have formed an additional 10 Descartes quintuples, each containing three spheres of generation zero and two spheres of generation 2. These quintuples will be obtained (in two ways, each) in generation 3, (e.g., as R_{i}R_{j}R_{i} = R_{j}R_{i}R_{j}) but these generation-3 quintuples will not contain any new spheres. Also, applying “reflection” to one of these “extra” quintuples we find only three new spheres, not four. It is unclear to which generation the spheres that are obtained by reflection from these “extra” quintuples belong. There are two arguments:

(a) They belong to the fourth generation because they are obtained by reflection using the quintuples that are obtained from words in the third generation.

(b) They belong in the third generation because they can be obtained by reflection using the “extra” quintuples that are formed at the second generation.

Similar ambiguities arise in succeeding generations. Thus we are faced with four distinct problems:

(1) count reduced words of length k.

(2) count spheres, using strategy (a).

(3) count quintuples, assuming “extra” quints belong in the generation in which they first appear (i.e. strategy (b).

(4) count spheres, using strategy (b).

There are similar problems when we start with only four touching spheres instead of five. We have been unable to make much progress on these problems. We have the following

results for small values of k, starting with five spheres.

generation  0 1 2  3  4  5  6
reduced words 1 5 20 80 300 1140 4260
unique words 1 5 20 70 240  780 2730
no. spheres (a) 5 5 20 60 210  690 3330
s_{k}/s_{0} (a)  1 3 20 108 630 3570 20460
t_{k}/t_{0} (a)  1 6 77 732 7278 71634 707076
quintuples (b) 1 5 30 120 480 2070
no. spheres (b) 5 5 20 90 330 1290
s_{k}/s_{0} (b)  1 3 20 174 1170 8454
t_{k}/t_{0} (b)  1 6 77 1278 15978 216366

5 How these results were computed

We remind the reader that we are in three dimensions. We use the “curvature-center coordinates” defined in [2, Defn. 3.2]. A sphere with bend b and center x = (x_{1}, x_{2}, x_{3}) is described by the vector (b, bx). The plane h^{T} x = p has c-c coordinates (0, h), and does not uniquely define the plane; we could avoid this by using the “augmented c-c coordinates” defined in [2] but this is not necessary since in our calculations there will never be more than two planes. The spheres in a Descartes configuration are described by a 5 × 3 matrix C whose rows are the c-c coordinates of the various spheres. The operation of reflection of the ith sphere in this configuration replaces C by R_{i}C.

We start with the special Descartes configuration described by the matrix

C = ( \begin{matrix}1 & 2r & 0 & 0 \\ 1 & −r & 1 & 0 \\ 1 & −r & −1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & −1 \end{matrix} )

where r is 1/\sqrt{3}. To save space and computational effort (using the statistical language Splus) we encode a row (b, bx, by, bz) as the integer 10^{7}b + 10^{4}bx/r + 10^{2}by + bz. Thus the starting configuration is described by the column vector c = (10020000, 9990100, 9989900, 1, −1)^{T}. After reflection by R_{i} the configuration is R_{i}c.

For k = 1, ..., 7 we formed a list of the types of reduced words of length k. Thus for k = 3 we have 121 and 123; for k = 4 we have 1213, 1231, 1232, 1234. For k = 5, 6, 7 we find 12,39,139 types, respectively. For each type, we consider the words that are formed when each of 1, 2, etc. are replaced by generators R_{i}, R_{j}, ⋯ in all possible ways. To get the number of unique words, duplicates are eliminated using the identities (4). Thus R_{1}R_{2}R_{1} and R_{2}R_{1}R_{2} are counted as distinct reduced words, but as the same unique word. Now we compute the coded coordinates of the last sphere that is added when each of these products of generators is applied to the base configuration. The list of coded spheres is then culled to eliminate duplicates. This gives the coded coordinates of spheres formed using strategy (a).

To compute the number of spheres in the kth generation using strategy (b), we need to count spheres that are added by reflection from the “extra” quintuples. Each (reduced) word of length k that contains j sub-words of type 121 (=212) will be an “extra” word in generation k − j. These words do not provide extra spheres in generation k − j, but have progeny in succeeding generations.

Computation finds the numbers of types in the following table. Note that the type 12131 is counted as having just one 121 substring, not two, because the word ABACA equals BABCA and ABCAC, and appears as a single “extra” word (in two ways) in generation 4.

generation  0 1 2 3 4 5 6 7
total no. types  1 1 1 2 4 12 39 139
types with no 121s  1 1 1 1 2 5 14 43
with one 121 substring  1 2 7 24 83
with two 121 substrings  1 13
“extra” types  1 2 8 37
total no. types (b)  1 1 2 3 10 42

6 Open problems

In all dimensions we do not know how the higher moments behave (they do not depend only on s_{0}). It is possible that for each starting configuration, some transformation of the bends might have a limiting distribution, which possibly might be independent of the starting configuration, but our numerical results are not extensive enough to allow us to make any conjectures. In three dimensions, all four of the problems listed above remain open. We have not done any computations for a four-sphere starting configuration, but expect that the method we used in section 3 will work here.

7 Acknowledgement

Thanks to a referee for simplifying my proofs of Theorems 2 and 4, and for a very careful reading of my manuscript.

References

[1] R. L. Graham, J. C. Lagarias, C. L. Mallows, A. R. Wilks, and C. Yan. Apollonian circle packings: Geometry and Group theory I. The Apollonian Group. Discrete Comput. Geom. 34 (2005), 547–585.

[2] R. L. Graham, J. C. Lagarias, C. L. Mallows, A. R. Wilks, and C. Yan. Apollonian circle packings: Geometry and Group theory III. Higher Dimensions. Discrete Comput. Geom. 35 (2006), 37–72.

2000 Mathematics Subject Classification: Primary 05A15. Keywords: circle-packing.

Received September 26 2008; revised version received January 2 2009. Published in Journal of Integer Sequences, January 3 2009.

Return to Journal of Integer Sequences home page.