Apollonian Circle Packings: Geometry and Group Theory I. The Apollonian Group

Apollonian circle packings arise by repeatedly filling the interstices between four mutually tangent circles with further tangent circles. We observe that there exist Apollonian packings which have strong integrality properties, in which all circles in the packing have integer curvatures and rational centers such that (curvature) $\times$ (center) is an integer vector. This series of papers explain such properties. A Descartes configuration is a set of four mutually tangent circles with disjoint interiors. An Apollonian circle packing can be described in terms of the Descartes configuration it contains. We describe the space of all ordered, oriented Descartes configurations using a coordinate system $M_ D$ consisting of those $4 \times 4$ real matrices $W$ with $W^T Q_{D} \bW = Q_{W}$ where $Q_D$ is the matrix of the Descartes quadratic form $Q_D= x_1^2 + x_2^2+ x_3^2 + x_4^2 - \frac{1}{2}(x_1 +x_2 +x_3 + x_4)^2$ and $Q_W$ of the quadratic form $Q_W = -8x_1x_2 + 2x_3^2 + 2x_4^2$. On the parameter space $M_ D$ the group $\mathop{\it Aut}(Q_D)$ acts on the left, and $\mathop{\it Aut}(Q_W)$ acts on the right, giving two different "geometric" actions. Both these groups are isomorphic to the Lorentz group $O(3, 1)$. The right action of $\mathop{\it Aut}(Q_W)$ (essentially) corresponds to Mobius transformations acting on the underlying Euclidean space $\rr^2$ while the left action of $\mathop{\it Aut}(Q_D)$ is defined only on the parameter space. We observe that the Descartes configurations in each Apollonian packing form an orbit of a single Descartes configuration under a certain finitely generated discrete subgroup of $\mathop{\it Aut}(Q_D)$, which we call the Apollonian group. This group consists of $4 \times 4$ integer matrices, and its integrality properties lead to the integrality properties observed in some Apollonian circle packings. We introduce two more related finitely generated groups in $\mathop{\it Aut}(Q_D)$, the dual Apollonian group produced from the Apollonian group by a "duality" conjugation, and the super-Apollonian group which is the group generated by the Apollonian and dual Apollonian groups together. These groups also consist of integer $4 \times 4$ matrices. We show these groups are hyperbolic Coxeter groups.     

Apollonian Circle Packings: Geometry and Group Theory III. Higher Dimensions

This paper gives $n$-dimensional analogues of the Apollonian circle packings in Parts I and II. Those papers considered circle packings described in terms of their Descartes configurations, which are sets of four mutually touching circles. They studied packings that had integrality properties in terms of the curvatures and centers of the circles. Here we consider collections of $n$-dimensional Descartes configurations, which consist of $n+2$ mutually touching spheres. We work in the space $M_D^n$ of all $n$-dimensional oriented Descartes configurations parametrized in a coordinate system, augmented curvature-center coordinates, as those $(n+2) \times (n+2)$ real matrices $W$ with $W^T Q_{D,n} W = Q_{W,n}$ where $Q_{D,n} = x_1^2 + \cdots + x_{n+2}^2 - ({1}/{n})(x_1 +\cdots + x_{n+2})^2$ is the $n$-dimensional Descartes quadratic form, $Q_{W,n} = -8x_1x_2 + 2x_3^2 + \cdots + 2x_{n+2}^2$, and $\bQ_{D,n}$ and $\bQ_{W,n}$ are their corresponding symmetric matrices. On the parameter space $M_D^n$ of augmented curvature-center matrices, the group ${\it Aut}(Q_{D,n})$ acts on the left and ${\it Aut}(Q_{W,n})$ acts on the right. Both these groups are isomorphic to the $(n+2)$-dimensional Lorentz group $O(n+1,1)$, and give two different "geometric" actions. The right action of ${\it Aut}(Q_{W,n})$ (essentially) corresponds to Mobius transformations acting on the underlying Euclidean space $\rr^n$ while the left action of ${\it Aut}(Q_{D,n})$ is defined only on the parameter space $M_D^n$. We introduce $n$-dimensional analogues of the Apollonian group, the dual Apollonian group and the super-Apollonian group. These are finitely generated groups in ${\it Aut}(Q_{D,n})$, with the following integrality properties: the dual Apollonian group consists of integral matrices in all dimensions, while the other two consist of rational matrices, with denominators having prime divisors drawn from a finite set $S$ depending on the dimension. We show that the Apollonian group and the dual Apollonian group are finitely presented, and are Coxeter groups. We define an Apollonian cluster ensemble to be any orbit under the Apollonian group, with similar notions for the other two groups. We determine in which dimensions there exist rational Apollonian cluster ensembles (all curvatures are rational) and strongly rational Apollonian sphere ensembles (all augmented curvature-center coordinates are rational).     

Apollonian circle packings: number theory

Apollonian circle packings arise by repeatedly filling the interstices between mutually tangent circles with further tangent circles. It is possible for every circle in such a packing to have integer radius of curvature, and we call such a packing an integral Apollonian circle packing. This paper studies number-theoretic properties of the set of integer curvatures appearing in such packings. Each Descartes quadruple of four tangent circles in the packing gives an integer solution to the Descartes equation, which relates the radii of curvature of four mutually tangent circles: . Each integral Apollonian circle packing is classified by a certain root quadruple of integers that satisfies the Descartes equation, and that corresponds to a particular quadruple of circles appearing in the packing. We express the number of root quadruples with fixed minimal element −n as a class number, and give an exact formula for it. We study which integers occur in a given integer packing, and determine congruence restrictions which sometimes apply. We present evidence suggesting that the set of integer radii of curvatures that appear in an integral Apollonian circle packing has positive density, and in fact represents all sufficiently large integers not excluded by congruence conditions. Finally, we discuss asymptotic properties of the set of curvatures obtained as the packing is recursively constructed from a root quadruple.     

On integral Apollonian circle packings

The curvatures of four mutually tangent circles with disjoint interiors form what is called a Descartes quadruple. The four least curvatures in an integral Apollonian circle packing form what is called a root Descartes quadruple and, if the curvatures are relatively prime, we say that it is a primitive root quadruple. We prove a conjecture of Mallows by giving a closed formula for the number of primitive root quadruples with minimum curvature −n. An Apollonian circle packing is called strongly integral if every circle has curvature times center a Gaussian integer. The set of all such circle packings for which the curvature plus curvature times center is congruent to 1 modulo 2 is called the “standard supergasket.” Those centers in the unit square are in one-to-one correspondence with the primitive root quadruples and exhibit certain symmetries first conjectured by Mallows. We prove these symmetries; in particular, the centers are symmetric around y=x if n is odd, around x=1/2 if n is an odd multiple of 2, and around y=1/2 if n is a multiple of 4.     

Irreducible Apollonian Configurations and Packings

An Apollonian configuration of circles is a collection of circles in the plane with disjoint interiors such that the complement of the interiors of the circles consists of curvilinear triangles. One well-studied method of forming an Apollonian configuration is to start with three mutually tangent circles and fill a curvilinear triangle with a new circle, then repeat with each newly created curvilinear triangle. More generally, we can start with three mutually tangent circles and a rule (or rules) for how to fill a curvilinear triangle with circles.     

Apollonian circle packings: Number theory II. Spherical and hyperbolic packings

Apollonian circle packings arise by repeatedly filling the interstices between mutually tangent circles with further tangent circles. In Euclidean space it is possible for every circle in such a packing to have integer radius of curvature, and we call such a packing an integral Apollonian circle packing. There are infinitely many different integral packings; these were studied in Part I (J. Number Theory 100, 1–45, 2003). Integral circle packings also exist in spherical and hyperbolic space, provided a suitable definition of curvature is used and again there are an infinite number of different integral packings. This paper studies number-theoretic properties of such packings. This amounts to studying the orbits of a particular subgroup of the group of integral automorphs of the indefinite quaternary quadratic form . This subgroup, called the Apollonian group, acts on integer solutions . This paper gives a reduction theory for orbits of acting on integer solutions to valid for all integer k. It also classifies orbits for all k≡0 (mod 4) in terms of an extra parameter n and an auxiliary class group (depending on n and k), and studies congruence conditions on integers in a given orbit. Much of this work was done while the authors were at AT&T Labs-Research, whom the authors thank for support. N. Eriksson was also supported by an NDSEG fellowship and J.C. Lagarias by NSF grant DMS-0500555.     

Effective Circle Count for Apollonian Packings and Closed Horospheres

The main result of this paper is an effective count for Apollonian circle packings that are either bounded or contain two parallel lines. We obtain this by proving an effective equidistribution of closed horospheres in the unit tangent bundle of a geometrically finite hyperbolic 3-manifold, whose fundamental group has critical exponent bigger than 1. We also discuss applications to affine sieves. Analogous results for surfaces are treated as well.     

Integral Apollonian circle packings and prime curvatures

It is shown that any primitive integral Apollonian circle packing captures a fraction of the prime numbers. Basically, the method consists of applying the circle method and considering the curvatures produced by a well-chosen family of binary quadratic forms.     

The asymptotic distribution of circles in the orbits of Kleinian groups

Let P\mathcal{P} be a locally finite circle packing in the plane ℂ invariant under a non-elementary Kleinian group Γ and with finitely many Γ-orbits. When Γ is geometrically finite, we construct an explicit Borel measure on ℂ which describes the asymptotic distribution of small circles in P\mathcal{P}, assuming that either the critical exponent of Γ is strictly bigger than 1 or P\mathcal{P} does not contain an infinite bouquet of tangent circles glued at a parabolic fixed point of Γ. Our construction also works for P\mathcal{P} invariant under a geometrically infinite group Γ, provided Γ admits a finite Bowen-Margulis-Sullivan measure and the Γ-skinning size of P\mathcal{P} is finite. Some concrete circle packings to which our result applies include Apollonian circle packings, Sierpinski curves, Schottky dances, etc.     

Patterns and Structures in Disk Packings

Using a computational procedure that imitates tightening of an assembly of billiard balls, we have generated a number of packings of n equal and non-equal disks in regions of various shapes. Our experiments are of three major types. In the first type, the values of n are in thousands, the initial disk configuration is random and a priori one expects the generated packings to be random. In fact, the packings turn out to display non-random geometric patterns and regular features, including polycrystalline textures with "rattlers" typically trapped along the grain boundaries. An experiment of the second type begins with a known or conjectured optimal disk packing configuration, which is then "frustrated" by a small perturbation such as variation of the boundary shape or a relative increase of the size of a selected disk with respect to the sizes of the other disks. We present such frustrated packings for both large n (~ 10, 000) and small n (~ 50 to 200). Motivated by applications in material science and physics, the first and second type of experiments are performed for boundary shapes rarely discussed in the literature on dense packings: torus, a strip cut from a cylinder, a regular hexagon with periodic boundaries. Experiments of the third type involve the shapes popular among mathematicians: circles, squares, and equilateral triangles the boundaries of which are hard reflecting walls. The values of n in these experiments vary from several tens to few hundreds. Here the obtained configurations could be considered as candidates for the densest packings, rather than random ones. Some of these conjecturally optimal packings look regular and the regularity often extends across different values of n. Specifically, as n takes on an increasing sequence of values, n = n(1), n(2), ...n(k), ..., the packings follow a well-defined pattern. This phenomenon is especially striking for packings in equilateral triangles, where (as far as we can tell from our finite computational experiments), not only are there an infinite number of different patterns, each with its own different sequence n(1), n(2), ...n(k), ..., but many of these sequences seem to continue indefinitely. For other shapes, notably squares and circles, the patterns either cease to be optimal or even cease to exist (as packings of non-overlapping disks) above some threshold value n(k0) (depending on the pattern). In these cases, we try to identify the values of n(k0).