\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Growing Apollonian Packings } \vskip 1cm \large Colin Mallows\\ Avaya Labs \\ Basking Ridge, NJ 07920 \\ USA \\ \href{mailto:colinm@avaya.com}{\tt colinm@avaya.com}\\ \end{center} \vskip .2 in \begin{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 three-dimensional case is difficult. There is an ambiguity in how the successive generations are defined. We are unable to give general results for this case. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Remark} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \newcommand{\mb}{{\mathbf b}} \newcommand{\mc}{{\mathbf c}} \newcommand{\me}{{\mathbf e}} \newcommand{\mh}{{\mathbf h}} \newcommand{\mx}{{\mathbf x}} %\newcommand{\m1}{{\mathbf 1}} Doesn't work \newcommand{\mC}{{\mathbf C}} \newcommand{\mI}{{\mathbf I}} \newcommand{\mJ}{{\mathbf J}} \newcommand{\mR}{{\mathbf R}} \newcommand{\mS}{{\mathbf S}} \newcommand{\mT}{{\mathbf T}} \newcommand{\mV}{{\mathbf V}} \newcommand{\mW}{{\mathbf W}} \newcommand{\mX}{{\mathbf X}} \section{Reflection and the Apollonian group} We draw on the definitions and analysis in \cite{G1,G3}. 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 \cite{G3}) $$ n(\sum b_i^2) = (\sum 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 $\mb$, the bends of the $i$-th new set are in the vector $\mR_i \mb$ where \begin{equation} \mR_i = \mI + \frac{2}{n-1} \me_i 1^T - \frac{2n}{n-1}\me_i \me_i^T , \label{eq:Ri} \end{equation} where $\mI$ is the unit $(n+2) \times (n+2)$ matrix, the column vector $\me_i$ has $1$ in the $i$-th position and zeroes elsewhere, and $1$ is a column of 1's. Thus $\mR_i$ is the identity matrix except for the %i%th row, which has -1 on the diagonal and $2/(n-1)$ elsewhere. (See \cite[Eq.\ 4.1]{G3}.) Each of these $n+2$ matrices is an involution, and they generate an infinite Coxeter group which we name ${\cal G}_n$. In all dimensions except 3, there are no relations among them except the involutory ones: $\mR_i^2 = \mI$. (See \cite[Thm.\ 5.2]{G3}). However, in 3 dimensions there are extra relations $(\mR_i \mR_j)^3 = \mI$ which will cause us difficulty below. Until further notice, we consider only dimensions $n =2$ and $n \ge 4$. A word of length $k$, $\mW = \mR_{i_1} \mR_{i_2} \cdots \mR_{i_k}$, in the generators of ${\cal G}_n$ is called {\em reduced} if $i_j \ne i_{j+1}$ for $j = 1, \ldots, k-1$. (So all squares have been cancelled). The number of reduced words of length $k \ge 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 $k$th generation of the Apollonian construction. \section{Starting with a Descartes configuration} We start with $n+2$ spheres in an $n$-dimensional Descartes configuration, $n \ne 3$. Since every application of a generator (in a reduced word) produces exactly one new sphere, the following lemma is clear. \begin{lemma} The spheres in the $k$-th generation ($k \ge 1$) are in 1--1 correspondence with reduced words of length $k$ in the generators of ${\cal G}_n$. \end{lemma} \begin{theorem} In $n$ dimensions ($n \ne 3$) the generating function of the sum of the bends in the $k$th generation is $$ G(x) = (1-x)(1-nx)s_0/(1-\theta x + (n+1)x^2) $$ where $\theta = (n^2 + n + 2)/(n-1)$. \label{thm1} \end{theorem} \begin{proof} The sum of the bends in the $k$th generation is \begin{equation} s_k = \sum \me_{i_1}^T \mR_{i_1} \cdots \mR_{i_k} \mb \label{eq:sk} \end{equation} where $\mb$ is the vector containing the bends of the initial configuration, and the sum is over all sequences $i_1,i_2, \ldots, i_k$ with $i_j \ne i_{j+1},~~~ j = 1, \ldots, k-1$. We define $$ \mT = \sum_j \mR_j $$ Then $\mT = a\mI + b\mJ $ where $\mJ$ is the matrix of all ones, $a = (n^2 - n - 2)/(n-1)$, and $b = 2/(n-1)$. Let $\mX_k$ be the row vector $\sum \me_{i_1} \mR_{i_1} \cdots \mR_{i_k}$ where the sum is as in (\ref{eq:sk}). Then $\mX_0 = 1^T$, $\mX_1 = ((n+3)/(n-1)) 1^T$, and $$ \mX_{k+1} = \mX_k \mT - (n+1)\mX_{k-1} $$ By induction, $\mX_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} = \theta c_k - (n+1)c_{k-1} $$ The theorem follows. \end{proof} 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 \medskip \begin{tabular}{lrrrrrrrrrr} & $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 \end{tabular} \medskip 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-\phi(n)x+(n+1)x^2) $$ where $\phi(n) = (n^3 + 5n + 2)/(n-1)^2$. In two dimensions the multiples are integers: \medskip \begin{tabular}{lrrrrrrrr} $k=$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ $t_k/t_0 =$ & 1 & 17 & 339 & 6729 & 133563 & 2651073 & 52620771 & 1044462201 \end{tabular} \medskip In two dimensions the average bend in the $k$th generation, $\bar{s_k}$, is asymptotically $C_1 \mu ^k$ where $\mu = (4+\sqrt 13 )/3$, and the average squared bend $\bar{t_k}$ is asymptotically $C_2 \nu ^k$ where $\nu = (10+\sqrt 97 )/3$. Thus the coefficient of variation of the bends in the $k$th generation is asymptotically $C \lambda ^k -1$ where $\lambda = 3\nu/\mu^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 \ge 4$ as $k \rightarrow \infty$ the coefficient of variation of the bends in the $k$th generation is of the form $C(1+\epsilon)^k -1$ where $\epsilon$ is a small fraction. \section{Starting with $n+1$ spheres} Now suppose we start with only $n+1$ mutually tangent spheres, $S_1, \ldots, 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^- \pm 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, \ldots, 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. \begin{lemma} For $k \ge 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 ${\cal G}_n$ of these two forms: (i) words of length $k$ whose right-most element is not $\mR_{n+2}$ (ii) words of length $k+1$ whose right-most element is $\mR_{n+2}$. \end{lemma} The number of such words is $2(n+1)^k$. \begin{theorem} The generating function of the sum of the bends in the $k$th generation, starting from $n+1$ spheres in $n$ dimensions, is $$ G^-(x) = (1-x)(1-((n^2+1)/(n-1))x)s_0^-/(1-\theta x + (n+1)x^2) $$ \label{thm2} \end{theorem} \begin{proof} Computations using the explicit form of $\mR_i$ show that $s_2^- = 2((n+1)/(n-1))^2 s_0^-$. For $k \ge 2$ we have $$ s_{k+1}^- = \sum \me_{i_1}^T \mR_{i_1} ... \mR_{i_k} (\mb + \mR_{n+2} \mb) $$ where the sum is over $i_j \ne i_{j+1} ,~~~ i_k \ne n+2$. Adding and subtracting the words that have $i_k = n+2$, we get \begin{equation} s_{k+1}^- = s_k + s_k' - \sum \me_{i_1}^T \mR_{i_1} ... \mR_{i_k-1} (\mR_{n+2} \mb + \mb) \label{eq:sk-} \end{equation} where $s_k'$ is the sum of the bends in the $k$th generation, starting from the full Descartes configuration with $b_{n+2} = a'$. In the summation in (\ref{eq:sk-}), we have $i_{k-1} \ne 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 \ge 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~\ref{thm1}. Hence the required generating function satisfies $$ (1+x)\frac{G^-(x)}{s_0^-} = 1 + \frac{n+1}{n-1}x + \frac{2nx}{n-1}\left(\frac{G(x)}{s_0} -1 \right) $$ and the theorem follows. \end{proof} For $n=2$ we find \medskip \begin{tabular}{lrrrrrrrrr} $k=$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ $s_k^-/s_0^- = $ & 1 & 2 & 18 & 138 & 1050 & 7986 & 60738 & 461946 & 3513354 \end{tabular} \medskip \noindent and for $k \ge 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 \ge 3$ the sum of the squares of the bends in the $k$th generation, $t_k^-$, satisfies the same recurrence as in the $(n+2)$-start case; for $n=2$ we find \medskip \begin{tabular}{lrrrrrrrr} $k=$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ $t_k^-/t_0^- =$ & 1 & 2 & 66 & 1314 & 26082 & 517698 & 10275714 & 203961186 \end{tabular} \medskip \noindent and the generating function is $(1-18x+29x^2)/(1-20x+3x^2)$. \section{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\times 5$ matrices as in Eq.~(\ref{eq:Ri}), with all elements in $\{ -1,0,1\}$. They satisfy \begin{equation} \mR_i^2 = \mI,~~~ (\mR_i \mR_j)^3 = \mI \label{eq:ident} \end{equation} In \cite{G3} {\em reduced} words were defined as those that \begin{verse} (i) contain no subwords of the form $\mR_j \mR_j$, \\ (ii) contain no subwords of the form $\mV_1 \mV_2 \cdots \mV_{2m}$ in which $\mV_1 = \mV_3, \mV_{2j} = \mV_{2j+3}$ for $1 \le j \le m-2$, and $\mV_{2m-2} = \mV_{2m}$. \end{verse} Thus all possible cancellations using the identities in (\ref{eq:ident}) 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 $\mR_i$, consists of five spheres, with bends $1,1,1,3,3$. The second derived generation, obtained from words $\mR_i \mR_j$ with $i \ne 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 ($\mR_i \mR_j$ and $\mR_j \mR_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 $\mR_i \mR_j \mR_i = \mR_j \mR_i \mR_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: \begin{verse} (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). \end{verse} 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. \medskip \begin{tabular}{lrrrrrrr} 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 & \end{tabular} \section{How these results were computed} We remind the reader that we are in three dimensions. We use the ``curvature-center coordinates" defined in \cite[Defn.\ 3.2]{G3}. A sphere with bend $b$ and center $\mx = (x_1, x_2, x_3)$ is described by the vector $(b, b\mx)$. The plane $\mh^T \mx = p$ has c-c coordinates $(0,\mh)$, and does not uniquely define the plane; we could avoid this by using the ``augmented c-c coordinates" defined in \cite{G3} 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 \times 3$ matrix $\mC$ whose rows are the c-c coordinates of the various spheres. The operation of reflection of the $i$th sphere in this configuration replaces $\mC$ by $\mR_i\mC$. We start with the special Descartes configuration described by the matrix $$ \mC = \left(\begin{array}{cccc} 1 & 2r & 0 & 0 \\ 1 & -r & 1 & 0 \\ 1 & -r & -1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & -1 \end{array} \right) $$ 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^7b + 10^4bx/r +10^2by +bz$. Thus the starting configuration is described by the column vector $\mc = (10020000,9990100,9989900,1,-1)^T$. After reflection by $\mR_i$ the configuration is $\mR_i \mc$. 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 $\mR_i, \mR_j, \cdots$ in all possible ways. To get the number of unique words, duplicates are eliminated using the identities (4). Thus $\mR_1\mR_2\mR_1$ and $\mR_2\mR_1\mR_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 $k$th 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. \medskip \begin{tabular}{lrrrrrrrr} 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 & & \end{tabular} \section{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. \section{Acknowledgement} Thanks to a referee for simplifying my proofs of Theorems~\ref{thm1} and \ref{thm2}, and for a very careful reading of my manuscript. \begin{thebibliography}{9} \bibitem{G1} 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. {\em Discrete Comput. Geom.} {\bf 34} (2005), 547--585. \bibitem{G3} 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. {\em Discrete Comput. Geom.} {\bf 35} (2006), 37--72. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15. \noindent \emph{Keywords: } circle-packing. \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received September 26 2008; revised version received January 2 2009. Published in {\it Journal of Integer Sequences}, January 3 2009. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}