Content-Type: multipart/mixed; boundary="-------------0011121021195" This is a multi-part message in MIME format. ---------------0011121021195 Content-Type: text/plain; name="00-450.keywords" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="00-450.keywords" aperiodic, circle packing, hyperbolic plane ---------------0011121021195 Content-Type: application/x-tex; name="hyper.tex" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="hyper.tex" \magnification 1200 \font\tenmsb=msbm10 %%%% these first lines are to define \Bbb, for R etc. \font\sevenmsb=msbm7 \font\fivemsb=msbm5 \newfam\msbfam \textfont\msbfam=\tenmsb \scriptfont\msbfam=\sevenmsb \scriptscriptfont\msbfam=\fivemsb \def\Bbb#1{\fam\msbfam\relax#1} \let\nd\noindent % NOINDENT \def\NL{\hfill\break}% NEWLINE \def\qed{\hbox{\hskip 6pt\vrule width6pt height7pt depth1pt \hskip1pt}} \def\natural{{\rm I\kern-.18em N}} \font\newfont=cmr10 at 12pt % or scaled\magstep2 TO INSERT LARGE FONT \def\A{{\cal A}} \def\B{{\cal B}} \def\H{{\cal H}} \def\G{{\cal G}} \def\P{{\cal R}} \def\O{{\cal O}} \def\M{{\cal M}} \def\F{{\cal F}} \def\N{{\Bbb N}} \def\integer{{\rm Z\kern-.32em Z}} \def\chix{{\raise.5ex\hbox{$\chi$}}} \def\Z{{\Bbb Z}} \def\real{{\rm I\kern-.2em R}} \def\R{{\Bbb R}} \def\Q{{\Bbb Q}} \def\complex{\kern.1em{\raise.47ex\hbox{ $\scriptscriptstyle |$}}\kern-.40em{\rm C}} \def\C{{\Bbb C}} \def\I{{\Bbb I}} \def\vs#1 {\vskip#1truein} \def\hs#1 {\hskip#1truein} \def\signed{\vskip1truein\hskip 2.5truein{Charles Radin}} \def\Signed{\vskip1truein\hskip 2.5truein{Charles Radin}\vs-.15 \hskip 2.5truein{Professor of Mathematics}} \def\Sinc{\vskip .5truein\hskip 2.5truein} \def\Indent{\vskip 0truein\hskip 2.5truein} \def\Month{\ifcase\number\month \relax\or January \or February \or March \or April \or May \or June \or July \or August \or September \or October \or November \or December \else \relax\fi } \def\date{\Month \the\day, \the\year} \font\personalfont=cmr10 scaled 1200 \font\sealfont=utseal \font\univfont=cmr8 scaled 1440 \font\deptfont=cmr6 scaled 1440 \font\addressfont=cmsl8 \def\utletterhead {\hbox to \hsize{\parskip=4pt \parindent=0pt \vbox{\hbox to .1\hsize {\hss\sealfont\char0}}\hskip.05\hsize \vbox{\deptfont Department of Mathematics \endgraf \univfont The University of Texas \endgraf \vskip 6pt\hrule width .85\hsize \vskip 2pt \addressfont Austin, Texas 78712 $\cdot$ (512) 471-7711 $\cdot$ FAX (512) 471-9038 \vskip 8pt}}} \def\makehead{\utletterhead \vs0 } \def\lett{\nopagenumbers\hbox{}\vs1 % can replace \vs1 by \makehead \personalfont \vs.2 \hskip 2.5truein{\date}\vskip.5truein} % DO NOT MAGNIFY FILE WHEN USING SEAL \hsize=6truein \hoffset=.25truein %was \hoffset=1.2truein \vsize=8.8truein %\voffset=1truein \pageno=1 \baselineskip=12pt \parskip=0 pt \parindent=20pt % \parskip=12pt \parindent=0pt (FOR USE IN LETTERS) \overfullrule=0pt \lineskip=0pt \lineskiplimit=0pt \hbadness=10000 \vbadness=10000 % REPORT ONLY BEYOND THIS BADNESS % Start of Text %\nopagenumbers %\lett %\nd \pageno=0 \font\bit=cmbxti10 \footline{\ifnum\pageno=0\hss\else\hss\tenrm\folio\hss\fi} \hbox{} \vskip 1truein\centerline{{\bf DENSEST PACKING OF EQUAL CIRCLES IN}} \vskip .1truein\centerline{{\bf THE HYPERBOLIC PLANE }} \vskip .2truein\centerline{by} \vskip .2truein \centerline{Lewis Bowen and Charles Radin \footnote{*}{Research supported in part by Texas ARP Grant 003658-158 \hfill\break \indent and NSF Grant DMS-0071643\hfil}} \vskip .5truein\centerline{ Mathematics Department, University of Texas at Austin} \vs.5 \centerline{{\bf Abstract}} \vs.1 \nd We propose a definition of density for packings of circles of fixed radius in the hyperbolic plane, and prove that for all but countably many radii, optimally dense packings must have low symmetry. \vs.8 \centerline{November 2000} \vs.2 \centerline{Subject Classification:\ \ 52A40, 52C26, 52C23} \vfill\eject \nd {\bf 1. Introduction}. \vs.1 While the study of densest packings of spheres in Euclidean space has made impressive gains in recent years [Hal], the analogous study in hyperbolic space has been held back at a fundamental level; there has not been a convincing approach to define what one should mean by ``densest packing of spheres'' in hyperbolic space [Fej, FeK]. Intuitively the difficulty in hyperbolic space is due to the feature that in a packing of equal spheres the ratio, of the number intersecting the surface of a region to the number contained in that region, need not vanish as the region increases, and therefore defining density in a noncompact hyperbolic space as a limit of the relative density within expanding compact subregions is too sensitive to the details of the boundary of the subregions. Alternatives also pose difficulties, as is well illustrated by an instructive example of B\"or\"oczky [Bor,FeK] of a packing $x$ of disks in the hyperbolic plane, together with a pair of tilings, $T_1$ and $T_2$, with the following properties. Each tiling consists of congruent copies of a single polygonal tile, and each tile in the corresponding tiling contains a single disk of $x$; but the tile for $T_1$ has larger area than that of $T_2$, so the ``relative density'' of the packing $x$ would be lower if defined using $T_1$ than with $T_2$. There is a tendency to expect an optimal packing to be very regular and symmetric [Ra1]. An example which fits well with intuition is the densest packings of equal disks in the Euclidean plane; the optimum is essentially unique, with six disks surrounding each disk in the packing, and has high symmetry: within the (connected component of the) isometry group of the plane, the symmetry group of the optimum is cocompact, generated by rotation by $2\pi/6$ about the center of any disk, and by a pair of translations. (We are choosing the dividing line between ``high'' and ``low'' symmetry to be that between cocompact and not-cocompact subgroups of the isometry group of the space.) There is little known about optimally dense packings of the Euclidean plane using other smooth bodies. But generalizing to packings using congruent copies of a finite number of pairwise noncongruent {\it polygons} we find the surprising phenomenon of ``aperiodic tiling'', wherein such packings {\it cannot have} high symmetry [Ra2]. The best known example is the kite \& dart tilings of the plane created by Penrose [Gar]. These tilings use congruent copies of two polygons, and the {\it only} symmetries that tilings made with these tiles can possess are rotations. Concerning the hyperbolic plane there is little published on optimally dense packings of disks, in part because of the difficulty, discussed above, of the definition of the density of a packing. This difficulty has therefore been avoided by jumping to tilings of polygons (see for instance [Moz, MaM]). In a sense what we show below is that this may be premature; unlike in Euclidean space, in hyperbolic space the ``aperiodicity'' phenomenon already shows up in optimally dense packing of spheres. Specifically, we analyze the situation for packing disks densely in the hyperbolic plane, propose a definition of optimally dense packings, and prove that for all but countably many radii, optimally dense packings must have low symmetry. \vs.2 \nd {\bf 2. Definitions and Results}. \vs.1 For definiteness we choose the metric $d(\cdot,\cdot)$ so that our hyperbolic plane $\H$ has curvature $-1$, and choose a distinguished ``origin'' $\O$ so we can identify $\H$ with the space $\G/\Sigma_\O$ of left cosets of the (connected) isometry group $\G(=PSL_2(\R))$ of $\H$ by the (compact) stability subgroup $\Sigma_\O$ of $\O$. Specifically, if $\G$ has its usual metrizable topology and $\G/\Sigma_\O$ its quotient topology, the pairing, of the left cosets $g\Sigma_\O$ with the images of $\O$ under $g$, is a homeomorphism. We fix the normalization of the Haar measure $\mu^H$ on $\G$ such that its connection with the measure $\mu_\H$ on $\H$ associated with its metric is: $\mu_\H[S]=\mu^H[\pi^{-1}_\O(S)]$, where $\pi_\O$ is the projection of $\G$ onto $\G/\Sigma_\O$. We will consider packings of $\H$ by ``$R$-disks'', disks of fixed radius $R>0$. (The special case of ``tight radius'', by which we mean an $R$ for which an integral number of $R$-disks fit tightly around a central $R$-disk (or equivalently, an equilateral triangle of edge length $2R$ has angle $2\pi/n$ for integer $n$), has been analyzed in detail in [Bow].) We will analyze the situation for the whole range of radii, and show that most such radii have optimal packings {\it only} with low symmetry. Before we can state any such result we must give a definition for optimality. We note first that, as in the parallel situation of aperiodic tilings, if optimal packings are of low symmetry then they should not be expected to be unique in the way disk packings of the Euclidean plane are unique -- that is, unique up to rigid motion. The kite \& dart tilings are not unique up to rigid motion; they are unique in the local sense that any finite region of one kite \& dart tiling is congruent to some local region of any other kite \& dart tiling. A natural framework in which to analyze structures with this form of uniqueness is ergodic theory, which we will adopt here. For fixed $R >0$ we begin with the space $S_R$ of all ``saturated'' packings of $\H$ by (closed) $R$-disks, that is, packings $x$ with the property that any closed $R$-disk in $\H$ intersects a disk of $x$. (The saturated restriction is made only for convenience.) For a packing $x$ we denote the set of centers of its disks by $C_x$. On $S_R$ we put the following metric: $$m(x, y)=\sup_{n\ge 1}{1\over n}h(B_{n}\cap C_x,B_{n}\cap C_y),\eqno (1)$$ \nd where for compact sets $A$ and $B$, we define $h(A,B) = \max \{ g(A,B), g(B,A)\}$ and \nd $g(A,B) = \sup_{a \in A}\inf_{b\in B}d(a,b)$, and ${B}_{n}$ denotes the closed disk of radius $n$ centered at the origin. It is not hard to see [RaW] that $S_R$ is compact in the metric topology of $D$, and that the natural action: $(g,x)\in \G\times S_R\longrightarrow g(x)\in S_R$ of the isometry group $\G$ of $\H$ on $S_R$ is (jointly) continuous. Let $\M$ be the family of Borel probability measures on $S_R$, $\M_I$ the subset of those invariant under $\G$, and $\M^e_I$ the convex extreme (``ergodic'') points of $\M_I$, all in their weak topology, in which $\M$ and $\M_I$ are compact. Some relevant elements of $\M^e_I$ can be constructed as follows. Consider any packing $x$ whose symmetry group $G_x$ is cocompact in $\G$. (We will call such a packing ``periodic''.) There is a natural projection of the Haar measure $\mu^H$ of $\G$ to a probability measure $\hat \mu_x$ on the compact space $G_x\backslash \G$ of right cosets, which we can describe as follows. Choose any fundamental domain $\F\subset \H$ for $G_x$. The set $G_x\pi^{-1}_\O(\F)=\pi^{-1}_\O(G_x\F)\subset \G$ is of full $\mu^H$-measure, and we will use it in $\G$ as we use $G_x\F$ in $\H$. Namely, let $\F_c$ be the component $\pi^{-1}_\O(\F)$ of $\pi^{-1}_\O(G_x\F)$ and define the measure $\hat \mu_x$ on subsets of $G_x\backslash \G$ by $\hat \mu_x(B)=\mu^H[\pi^{-1}_x(B)\cap\F_c]/\mu^H[\F_c]$, where $\pi_x$ is the projection of $\G$ onto $G_x\backslash \G$. If $h: G_x\backslash \G\longrightarrow S_R$ is the homeomorphism taking the cosets $G_x g$ into the packings $gx$, $\hat \mu_x$ can be lifted uniquely (using intersection with $h[G_x\backslash \G$]) to a $\G$-invariant probability measure, called $\mu_x$, on $S_R$. (We call a measure ``periodic'' when it can be associated as $\hat \mu_x$ or $\mu_x$ from a periodic packing.) For any $p\in \H$ we now define the real valued function $F_p$ on $S_R$ as the characteristic function (otherwise denoted $\chix_{K_p}$) of the closed subset $K_p$ of those packings such that $p$ is contained in one of its disks. Finally, we define the ``density'' as follows (based on [BeS]). \vs.1 \nd {\bf Definition 1}. For any $\mu\in M_I$, we define the density of $\mu$, which we denote by $d_\mu$, as $\int_{S_R} F_p(y)\, d\mu(y)=\mu(K_p)$. \vs.1 \nd (The density is independent of the choice of $p$, because of the invariance of the measure, so for convenience we sometimes use $p=\O$.) One justification for this notion of density comes from an ergodic theorem of Nevo and Stein [NeS] from which it follows that, for any $\mu\in M_I$, and $\mu$-almost every packing $y\in S_R$, the density $d_\mu$ is the limit of the relative fraction in expanding circles centered at $\O$ taken up by the disks in the packing $y$. Another justification comes from its relation to the density of Voronoi cells, as we now show. For $y\in S_R$ we wish to focus on two ways to represent the packing in terms of a tiling of $\H$. For the first, consider, for each disk center $a\in C_y$, the geodesic segment $ab$ which joins $a$ to any $b\in C_y$, $b\ne a$, and the two half-spaces defined by the geodesic which is the perpendicular bisector of $ab$. Let $\B(a)$ be the subset of these half-spaces in which $a$ is contained. The ``Voronoi cell of $a$'', which clearly contains the disk centered at $a$, is the closure of the intersection of the half-spaces in $\B(a)$. The Voronoi cells of $y$ form a tiling of $\H$, which we call the ``Voronoi tiling of $y$'', the first of the tilings of $\H$ associated with $y$ with which we are interested. To define the other tiling of $\H$ associated with $y$, consider each (closed) ``supporting disk'' in $\H$, which has at least three centers of $C_y$ on its boundary but none in its interior. Those centers on the boundary of a supporting disk define a convex polygon which we call a ``dual Voronoi cell''. It was shown in [Fej] that these polygons form a tiling of $\H$, which we call the ``dual Voronoi tiling of $y$'', the second of the tilings of $\H$ associated with $y$ in which we are interested. For $y\in S_R$ such that $\O$ is contained in the interior of a Voronoi cell (which we denote by $V_\O(y)$), we define $\tilde F(y)$ as the relative area of $V_\O(y)$ occupied by the disks of $y$. (We note that $\tilde F(y)$ is defined $\mu$-almost everywhere for any $\mu\in M_I$.) Then for $\mu\in M_I$ we define the ``Voronoi density for $\mu$'' as $\int_{S_R}\tilde F(y)\,d\mu(y)$. Similarly, for $y\in S_R$ such that $\O$ is contained in the interior of a dual Voronoi cell (which we denote by $T_\O(y)$), we define $\hat F(y)$ as the relative area of $T_\O(y)$ occupied by the disks of $y$. (We note that $\hat F(y)$ is defined $\mu$-almost everywhere for any $\mu\in M_I$.) Then for any $\mu\in M_I$ we define the ``dual Voronoi density for $\mu$'' as $\int_{S_R}\hat F(y)\,d\mu(y)$. \vs.1 \nd {\bf Proposition 1}. For any $\mu\in M_I$, the Voronoi density for $\mu$ and the dual Voronoi density for $\mu$ both equal $d_\mu$. \vs.1 \nd Proof. We will only prove that the Voronoi density of $\mu$ equals $d_\mu$, the case for the dual density following similarly, and we begin by stating the following without proof. \vs.1 \nd {\bf Lemma 1}. Given any $\epsilon >0$ there exists $\delta >0$ such that if $x,y\in S_R$ and $\O$ is not on an edge of the Voronoi cells $V_\O(x), V_\O(y)$, and $m(x,y)<\delta$, then $$\int_\H\Biggl|{\chix_{V_\O(x)}(p)\over \mu_\H[V_\O(x)]} - {\chix_{V_\O(y)}(p)\over \mu_\H[V_\O(y)]}\Biggr|d\mu_\H(p)<\epsilon.\eqno (2)$$ Now given $\epsilon >0$ we use the compactness of $S_R$ to choose measurable subsets $\{C^j:j=1,\ldots,N\}$, of $S_R$, such that i) -- iv) hold: \vs.1 \nd i) $C^j\cap C^k=\emptyset$, for $j\ne k$ \vs.1 \nd ii) if $x\in C^j$, $\O$ is not on an edge of the Voronoi cell $V_\O(x)$ \vs.1 \nd iii) $\mu[\cup_jC^j]=\mu[S_R]$, for all $\mu\in M_I$ \vs.1 \nd iv) if $x,y\in C^j$, $m(x,y)<\delta$. \vs.1 \nd Finally, for each $j$ fix some choice of $x_j\in C^j$. Then, for $\mu\in M_I$, $$\eqalign{ d_\mu &=\int_{S_R}F_p(y)\,d\mu(y)\cr &=\Sigma_j\int_{S_R}F_p(y)\chix_{C^j}(y)\,d\mu(y)\cr &=\Sigma_j\int_\H\Biggl[\int_{S_R}F_p(y)\chix_{C^j}(y)\,d\mu(y){\chix_{V_\O(x_j)}(p) \over \mu_\H[V_\O(x_j)]}\Biggr]\,d\mu_\H(p)\cr &=\Sigma_j\int_{S_R}\Biggl[\int_\H F_p(y){\chix_{V_\O(x_j)}(p) \over \mu_\H[V_\O(x_j)]}\,d\mu_\H(p)\chix_{C^j}(y)\Biggr]\,d\mu(y).\cr }\eqno (3)$$ \nd Noting that $$\tilde F(y)=\int_\H F_p(y){\chix_{V_\O(y)}(p) \over \mu_\H[V_\O(y)]}\,d\mu_\H(p),\eqno (4)$$ \nd we see from Lemma 1, for $y\in C^j$, $$\eqalign{ \Biggl|\tilde F(y)-\int_\H F_p(y) {\chix_{V_\O(x_j)}(p) \over \mu_\H[V_\O(x_j)]}\,d\mu_\H(p)\Biggr| &\le \int_\H F_p(y)\Biggl|{\chix_{V_\O(y)}(p) \over \mu_\H[V_\O(y)]} - {\chix_{V_\O(x_j)}(p) \over \mu_\H[V_\O(x_j)]}\Biggr| \,d\mu_\H(p)\cr &<\epsilon.\cr }\eqno (5)$$ So $|d_\mu - \int_{S_R}\tilde F(y)\, d\mu(y)|<\epsilon.$\qed \vs.1 Our last justification of the definition of density concerns periodic packings, as follows. \vs.1 \nd {\bf Proposition 2}. If $x$ is a periodic packing, $d_{\mu_x}$ is the relative area of any fundamental domain taken up by its disks. \vs.1 \nd Proof. Let $\F\subset \H$ be a fundamental domain for $G_x$ and let $K_x\subset \H$ denote the union of the disks in $x$. It is not hard to see that $\pi^{-1}_\O[K_x]=(\pi^{-1}_x\{h^{-1}(K_\O) \cap [G_x\backslash \G]\})^{-1}$ and therefore $$\eqalign{{\mu_\H(K_x\cap \F)\over \mu_\H(\F)}=&{\mu^H(\pi^{-1}_\O[K_x]\cap \F_c) \over \mu^H(\F_c)}={\mu^H(\pi^{-1}_x\{h^{-1}(K_\O\cap [G_x\backslash \G])\}\cap \F_c)\over \mu^H(\F_c)}\cr =&\hat \mu_x\{h^{-1}(K_\O\cap [G_x\backslash \G])\}=\mu_x(K_\O)\cr}, \eqno (6)$$ \nd which proves the proposition.\qed \vs.1 The last two propositions show how the density can be understood locally; in contrast to the use of some tiling perhaps ill suited to a packing (as in the example of B\"or\"oczky noted above), we see that local structures appropriate to the packing can be reliably used to compute density. We now define optimality, again through measures. \vs.1 \nd {\bf Definition 2}. $d_R\equiv \sup_{\mu\in M^e_I}d_\mu$ will be called the optimal density for radius $R$, and any $\tilde \mu\in M^e_I$ will be called optimally dense for radius $R$ if $d_{\tilde \mu}=d_R$. Those packings in the support of an optimally dense measure, whose orbit under $\G$ is dense in the support of that measure, will be called ``optimally dense''. \vs.1 To see the value of Proposition 1 in computing optimal densities, we note the fact (see Section 37 in [Fej]) that if $x$ is the obvious packing for the tight radius $R$ then its dual Voronoi cells (which are all congruent triangles) have the highest density among all dual Voronoi cells of all packings in $S_R$, and so $\mu_x$ (and $x$) is optimally dense. Note that there may be many optimal measures for given $R$, as is the case for three dimensional Euclidean space (corresponding for instance to the face centered cubic and body centered cubic packings). More important here however is the question of the {\it existence} of optimal packings in hyperbolic spaces. \vs.1 \nd {\bf Proposition 3}. For any radius $R>0$ there exists an optimally dense measure $\mu$ and a subset, of full $\mu$-measure, of optimally dense packings in the support of $\mu$. \vs.1 \nd Proof. $F_\O$ is upper semicontinuous, and it is easy to construct a decreasing sequence $F_j$ of continuous real valued functions on $S_R$ which converge pointwise to $F_\O$. Choose a sequence $\mu_k\in M^e_I$ such that $d_{\mu_k}=\int_{S_R} F_\O\, d\mu_k\to d_R$ as $k\to \infty$, and, using the compactness of $M_I$, assume without loss of generality that $\mu_k$ converges to some $\mu_\infty\in M_I$. Then $\int_{S_R} F_j\, d\mu_k\to \int_{S_R} F_j\, d\mu_\infty$ as $j\to \infty$, and $\int_{S_R} F_j\, d\mu_\infty\searrow d_{\mu_\infty}$ as $k\to \infty$. Since $\int_{S_R} F_j\, d\mu_k\ge d_{\mu_k} \to d_R$ as $k\to \infty$, $d_{\mu_\infty}\ge d_R$. From the Krein-Milman theorem there exists $\tilde \mu\in M^e_I$ for which $d_{\tilde \mu}=\int_{S_R} F_\O\, d_{\tilde\mu}\ge d_{\mu_\infty}$, and thus $d_{\tilde\mu}\ge d_R$. But then from the definition of $d_R$, $d_{\tilde\mu}= d_R$. We now show there optimally dense packings in the support $\sigma(\tilde\mu)$ of $\tilde\mu$. Choose a countable dense subset $A$ in $\sigma(\tilde\mu)$ and for each of these points consider the open balls of radius $1/n$ centered on them. This gives a countable collection $C$ of open balls. Consider any point $y\in \sigma(\tilde\mu)$, and ball $B$ of radius $1/N$ centered on it. There is some point $x\in A$ of distance less than $1/2N$ from $y$, so the ball centered at $x$ of radius $1/2N$ lies in $B$. Now for each of the balls $c\in C$ there is a subset of $\sigma(\tilde\mu)$, of full $\tilde\mu$-measure, whose orbit intersects $c$, as we see by applying the ergodic theorem to the characteristic function of $c$. It follows that there is a set of full $\tilde\mu$-measure of points whose orbit intersects each of the balls in $C$, and thus intersects $B$.\qed \vs.1 We need some further notation. For a packing $x$, we denote the radius of its disks by $\P(x)$, and let $K(x)$ denote the CW complex with vertex set $C_x$, with 1-cells between vertices $p$ and $q$ if and only if the distance between $p$ and $q$ is $2\P(x)$, and 2-cells with boundary $e_1,\ldots , e_n$ if and only if $e_1, \ldots ,e_n$ are adjacent in the given order, the piecewise geodesic curve associated to $e_1, \ldots ,e_n$ separates the space into two components, and there are no elements of $C_x$ in the interior of at least one of the components. If $\tilde G$ is a discrete subgroup of the isometry group of $x$ then $x/\tilde G$ is the packing of $\H/\tilde G$ induced by the covering space map. For a periodic packing $x$ we call $d_x\equiv d_{\mu_x}$ the density of $x$. Further, we call $x$ ``genus g optimal'' if for any periodic packing $x'$, of the same radius, for which $G_{x'}\backslash \G$ has genus g, $d_{x'}\le d_x$; we call it ``periodic optimal'' if for any periodic packing $x'$ of the same radius, $d_{x'}\le d_x$. If $r$ is any positive real number then the ``periodic density'' $D(r)$ of $r$, is the supremum of all $d_x$ where $x$ is periodic and of radius $r$. Finally, a packing will be called ``completely saturated'' if whichever $N$ disks are removed, $N+1$ may not be added to the remainder and still produce a packing. \vs.1 \nd {\bf Theorem}. For all but countably many radii $R>0$, no optimal measure or packing is periodic. \vs.1 \nd Proof. The bulk of the proof consists of three lemmas. \vs.1 \nd {\bf Lemma 2}. Suppose $x$ is a periodic disk packing. If $x$ is periodic optimal, then $x$ is completely saturated. \vs.1 \nd Proof of lemma. Suppose $x$ is not completely saturated. Then there exists a packing $x'$ with the following three properties. First, $\P(x')=\P(x)$. Second, there is some $q\in C_{x'}$, $q\notin C_x$, and a number $K$ such that if $c\in C_{x'}$ is not contained in the ball of radius $K$ with center $q$, then $c\in C_x$. Also, conversely, if $c\in C_x$ and is not contained in the ball of radius $K$ with center $q$, then $c\in C_{x'}$. Third, the number of centers of $x'$ contained in the ball of radius $K$ centered at $q$ is greater than the number of centers of $x$ contained in the ball of radius $K$ centered at $q$. Let $q'$ be the image of $q$ in $\H/G_x$. By Theorem 1.6.11 in [Bus], the number of closed geodesics through $q'$ in $\H/G_x$ that have length less than or equal to $2K$ is finite. Let $h_1, h_2, \dots ,h_t$ denote these geodesics. Let $\tilde h_i\in \H$ be a lift of $h_i$. Let $g_i\in G_x$ be such that its axis is $\tilde h_i$ and for any $p\in \tilde h_i$, $d(p,g_ip)$ is the length of $h_i$. From [Sco] there is a normal subgroup $G'$ of finite index in $G_x$ such that $\H/G'$ does not contain $g_1, g_2, \ldots$ or $g_t$. Since $G'$ is normal, $G_x$ does not contain any conjugates of $g_1, g_2, \ldots, g_t$ either. This implies that there are no closed geodesics passing through $q'$ in $\H/G'$ that have length less than $2K$. By Lemma 4.1.5 of [Bus], the injectivity radius of $\H/G'$ at the image of $q$ is greater than $K$. So there is a fundamental domain in $\H$ for $G'$ that contains the circle of radius $K$ centered at $q$. $x'$ gives rise to a packing of $\H/G'$ which has more disks in it than the packing $x/G'$. Hence $x'/G'$ is denser than $x/G'$, and so $x$ is not optimal.\qed \vs.1 \nd {\bf Lemma 3}. Suppose $x$ is a packing for which there is $t > 0$ such that the distance between any two centers of $x$ is greater than or equal to $2\P(x) + t$. Let $k$ be an integer such that $kt > 2\P(x)\ge (k-1)t$ and let $R = k(2\P(x) + t)$. Then for any point $q$ that is not in a disk of $x$, the centers of $x$ inside the circle of radius $R$ centered at $q$ may be rearranged so that there is room for at least one more disk of radius $\P(x)$. In particular, $x$ is not completely saturated. \vs.1 \nd Proof of lemma. The idea behind the proof is that by moving a finite number of disks away from $q$, there will be space enough to place a new disk with center at $q$. For any point $p\neq$ and any $t > 0$, let $p(t)$ be the point on the ray starting at $q$ and containing $p$ such that $d(q,p(t)) = d(q,p) + t$. We partition the centers $c$ of $x$ into three types, and define a function $f$ on $C_x$ as follows. \vs.05 \nd (i) $c$ is type 1 if $d(c,q) \ge R$. In this case, let $f(c) = c$. \vs.05 \nd (ii) $c$ is type 2 if there is a $j$ such that $0 < j < k$ and $R - 2(j-1)(\P(x) + t) > d(q,c) \ge R - 2j(\P(x) + t)$. In this case, define $f(c) = c(jt)$. \vs.05 \nd (iii) $c$ is type 3 if $R - 2(k-1)(\P(x) + t) > d(q,c)$. In this case, define $f(c) = c(kt)$. \vs.05 Define $C'$ to be the union of the point $q$ and the image of $C_x$ under $f$. From the definitions, it is clear that $C'$ differs from $C_x$ in only a finite number of points. Hence once we show that disks of radius $\P(x)$ centered at points of $C'$ do not overlap, it follows that $x$ is not completely saturated. First, let $c$ be type 2. It follows from the definitions that \vs.1 \nd $$R - 2(j-1)[\P(x) + t] + jt = R - (j-1)(2\P(x) + t) + t \eqno (7)$$ $$R - (j-1)[2\P(x) + t] + t = (k-j+1)[2\P(x) + t] + t\eqno (8)$$ $$(k-j+1)[2\P(x) + t] + t > d(f(c),q)\eqno (9)$$ $$d(f(c),q) \ge R - 2j[\P(x) + t] + jt\eqno (10)$$ $$R-2j[\P(x) + t] + jt = (k-j)[2\P(x) + t]\eqno (11).$$ \nd In particular, $d(f(c),q) > 2\P(x)$, so the disk centered at $f(c)$ does not overlap the disk centered at $q$. Also if $c$ is type 1 or type 3, the distance between $c$ and $q$ is greater or equal than $2\P(x)$ since both $R$ and $kt$ are. Now assume for a contradiction that there exist two distinct centers $c$ and $c'$ in $C_x$ with $d(f(c),f(c')) < 2\P(x)$. Suppose that $c$ is type 1. If $c'$ is also type 1 then $f(c)=c$ and $f(c')=c'$ so $d(c,c') < 2\P(x)$. This contradicts the hypothesis that $x$ is a packing so $c'$ is not type 1. If $c'$ is type 2 then by (8) and (9) there exists a $j$ with $0 d(f(c'),q).\eqno (12)$$ \vs.1 \nd On the other hand, $$\eqalign{ R \le & d(f(c),q)\cr \le & d(f(c),q) + d(f(c),f(c'))\cr < & R - (j-1)[2\P(x) + t] +t + 2\P(x)\cr = & R - (j-2)[2\P(x) + t].\cr}\eqno (13)$$ \vs.1 \nd Since $0 < j < k$, $j=1$. Hence $$\eqalign{ d(f(c),f(c')) &= d(c,f(c'))\cr &\ge d(c,c') - d(c',f(c'))\cr &\ge 2\P(x)+t-t\cr &=2\P(x),\cr }\eqno (14)$$ \nd a contradiction. Thus $c'$ is not type 2. If $c'$ is type 3, then \vs.1 \nd $$f(c') = c'(kt)\eqno (15)$$ \nd and $$R - 2(k-1)(\P(x) + t) \ge d(c',q).\eqno (16)$$ \nd Hence $$\eqalign{ d(f(c'),q) &\le R - 2(k-1)(\P(x) + t) + kt\cr &= R - 2k\P(x) - kt + 2(\P(x) + t)\cr &\le R - 2k\P(x) + 2t.\cr }\eqno (17)$$ \nd Since $d(f(c'),f(c)) < 2\P(x)$, $$\eqalign{ R &\le d(f(c),q) \le d(f(c),f(c')) + d(f(c'),q)\cr &< R - 2k\P(x) + 2t + 2\P(x).\cr }\eqno (18)$$ \nd This implies that $$\P(x)(k-1) < t.\eqno (19)$$ \nd Since from the definition of $\P(x)$ $$t \ge {2\P(x)\over k},\eqno (20)$$ $$k-1 < 2/k.\eqno (21)$$ \nd Thus $k = 1$ which implies that $t > 2\P(x)$. In this case, let $c$ be a center of $x$. Let $c'$ be a point with $d(c,c') = 2\P(x)$. If $c''$ is another center of $x$, then $$\eqalign{ 4\P(x) &\le 2\P(x) + t\cr &\le d(c'',c)\cr &\le d(c'',c') + d(c',c)\cr &= d(c'',c') + 2\P(x)\cr }.\eqno (22)$$ \nd So, $$2\P(x) \le d(c'',c).\eqno (23)$$ Thus $x$ is not completely saturated. So Lemma 2 implies that $x$ is not optimal. So we may assume that $c$ is not type 1. By symmetry we may also assume that $c'$ is not type 1. Assume that $c$ and $c'$ are type 2 and that $f(c) = c(j)$ and $f(c')=c'(j')$. By (10) and (11), and then (9), $$\eqalign{ (k-j)[2\P(x) + t] &< d(f(c),q)\cr &\le d(f(c),f(c')) + d(f(c'),q)\cr &< 2\P(x) + (k - j' + 1)[2\P(x) + t] + t.\cr }\eqno (24)$$ \nd This implies that $$0 < (j - j' + 2)[2\P(x) + t].\eqno (25)$$ \nd So $$j' < j + 2.\eqno (26)$$ \nd By symmetry, $$j < j' + 2.\eqno (27)$$ We now need \vs.1 \nd {\bf Lemma 4}. If $a$ and $b$ are any distinct points, neither equal to $q$, and $s > 0$, then $d(a(s),b(s)) > d(a,b)$. \vs.1 Assuming Lemma 4 we will finish the proof. By (26) and (27) either $j'=j$ or $j'=j+1$. Suppose that $j' = j + 1$. Then $$\eqalign{ 2\P(x) + t &\le d(c,c')\cr &< d(c(jt),c'(jt))\cr &= d(f(c),c'(jt))\cr &\le d(f(c),c'(j't)) + d(c'(j't),c'(jt))\cr &= d(f(c),f(c')) + d(c'(j't),c'(jt))\cr &< 2\P(x) + t.\cr }\eqno (28)$$ This contradiction shows that $j'$ is not equal to $j + 1$. So assume that $j' = j$. Then Lemma 4 shows that $d(c(jt), c'(jt)) > d(c,c') \ge 2\P(x) + t$. This contradiction shows that $c'$ is not type 2. Suppose that $c'$ is type 3. By (8) and (9) (and since $c'$ is type 3), $$\eqalign{ R - j[2\P(x) + t] &= (k-j)[2\P(x) + t]\cr &< d(q,f(c))\cr &\le d(q,f(c')) + d(f(c'),f(c))\cr &< d(q,c') + kt + 2\P(x)\cr &\le R - 2(k-1)(\P(x) + t) + kt + 2\P(x).\cr }\eqno (29)$$ \nd So, $$(k - 2 - j)[2\P(x) + t] < 0.\eqno (30)$$ Thus, $j > k - 2$. By definition of type 2, $j = k - 1$. This case can be handled the same way as the previous case in which $j = j' - 1$. Namely, $$\eqalign{ 2\P(x) + t &\le d(c,c')\cr &< d(c((k-1)t), c'((k-1)t))\cr &= d(f(c),c'((k-1)t))\cr &\le d(f(c),c'(kt)) + d(c'(kt),c'((k-1)t))\cr &= d(f(c),f(c')) + d(c'(kt),c'((k-1)t))\cr &< 2\P(x) + t.\cr }\eqno (31)$$ This contradiction shows that $c$ cannot be type 2. By symmetry, $c'$ cannot be type 2 either. So they must both be type 3. But, this is impossible by Lemma 4. So Lemma 3 is proven given Lemma 4. \vs.1 We now prove Lemma 4. For any points $y$ and $z$ in the plane we will use the notation $yz$ to denote both the segment $yz$ and its length. By the law of cosines, $$D(b) \equiv \cosh(a(s)b(s)) = \cosh(qa + s)\cosh(qb + s) - \cos(aqb)\sinh(qa + s)\sinh(qb + s).\eqno (32)$$ \nd If we differentiate this with respect to length $qb$ keeping angle $aqb$, length $qa$, and $s$ fixed, we get $$\eqalign{ dD/db &= (\cosh(aq+s)\sinh(bq+s) - \cos(aqb)\sinh(aq+s)\cosh(qb+s))\cr &= (\cosh(aq+s)\sinh(bq+s) - \cos(aqb)\sinh(aq+s)\cosh(qb+s)).\cr }\eqno (33)$$ \nd This function is positive whenever $b > a$ because $$\hbox{cotanh}(a+s)\tanh(b+s) > 1 \ge \cos(aqb)\eqno (34)$$ \nd and because $\tanh$ is a monotonic increasing function and cotanh is its multiplicative inverse. Since $dD/db$ is always positive for $b > a$ and we are trying to find a lower bound on $D$, we may assume than $b = a$. Now we differentiate $D$ with respect to $s$, keeping angle$(aqb)$, and $a=b$ fixed. $$\eqalign{ dD/ds &= 2\cosh(qa + s)\sinh(qa + s) - 2\cos(aqb) \cosh(qa +s)\sinh(qa + s)\cr &= 2\cosh(qa + s)\sinh(qa + s)(1 - \cos(aqb)).\cr }\eqno (35)$$ So $dD/ds$ is always positive whenever $a\ne b$. This implies that $D$ is an increasing function of $s$. Since at $s= 0$, $D = \cosh(ab)$, and $\cosh$ is monotonic increasing, Lemma 4 is proven, which completes the proof of the lemma. \qed \vs.1 \nd {\bf Corollary 1}. If $x$ is periodic and optimal and $r' < \P(x)$, then $$D(r')>D(\P(x)){\cosh(r') - 1\over \cosh(\P(x)) -1}.$$ \vs.1 \nd Proof. Let $t = \P(x) - r'$. Let $x'$ be the packing with $C_{x'}=C_x$ and $\P(x')=r'$. Then $x'$ satisfies the hypotheses of Lemma 3. Let $q$ be a point not in a disk of $x'$ and let $R$ be as in the lemma. Let $G'$ be a subgroup of $G_x$ such that $\H/G'$ is compact and the circle of radius $R$ centered at $q$ is contained in a fundamental domain for $\H/G'$. By the lemma, there is a packing $x''/G'$ of $\H/G'$ of radius $r'$ that has more disks in $\H/G'$ then $x'/G'$ does. Therefore the density of $x'/G'$ is less than $D(r')$. The area of a disk of radius $r$ is $2\pi[\cosh r -1]$, the density of $x'/G'$ is equal to $D(\P(x))(\cosh(r') - 1)/(\cosh(\P(x)) -1)$. So Corollary 1 is proven. \qed \vs.1 \nd {\bf Corollary 2}. If $x$ and $x'$ are both optimal and periodic and $\P(x) < \P(x')$ then $K(x)$ is not isomorphic to $K(x')$. \vs.1 \nd Proof. Suppose, for a contradiction, that there is an isomorphism $M$ from $K(x)$ to $K(x')$. Let Aut$(x)$ and Aut$(x')$ denote the group of automorphisms of $K(x)$ and $K(x')$, respectively. Then $M$ induces an isomorphism $M^*$ from Aut$(x)$ to Aut$(x')$. Also there are natural embeddings $E$ and $E'$ of $G_x$ and $G_{x'}$ into Aut$(x)$ and Aut$(x')$ respectively. Since $\H/G_x$ and $\H/G_{x'}$ are compact, [Aut$(x):E(G_x)$] and [Aut$(x'):E'(G_{x'})$] are finite. Hence, [Aut$(x'):M^*(E(G_x))\cap E'(G_{x'})$] is finite index. Hence, there exists isomorphic finite index subgroups $G'$ and $G''$ of $G_x$ and $G_{x'}$ respectively. Moreover, by passing to finite index subgroups of $G'$ and $G''$ we can assume that $G'$ and $G''$ are torsion free. So the genus of $\H/G'$ equals the genus of $\H/G''$. Also there is a fundamental domain $\F$ in $x$ for $G'$ such that $M(\F)$ is a fundamental domain for $G''$. Hence the number of disks of $x$ in $\H/G'$ equals the number of disks of $x'$ in $\H/G''$. Hence the density of $x$ is equal to $D(\P(x'))(\cosh(\P(x)) - 1)/(\cosh(\P(x')) -1)$. This contradicts Corollary 1. \qed \vs.1 \nd We now need a few more definitions. Define $f(r,g)$ as the maximum number of disks in $x/G'$ for any packing $x$ and subgroup $G'\subset G_x$ which satisfies $\P(x)=r$ and the genus of $\H/G'$ is $g$. Define $F(r)$ as the $\limsup$, as $g\to \infty$, of $f(r,g) / (2g- 2)$. The maximum density of any disk packing $x$ with radius $r$ of a surface of genus $g$ is then $f(r,g)(\cosh r -1) / (2g - 2)$. So the periodic density $D(r) =F(r)(\cosh r - 1)$. Define $opt(g,n) $ as the supremum, over all $r \in (0,\infty)$ for which $f(r,g) \ge $n. Define $O_g$ to be the set of all $r \in (0, \infty)$ for which $r = opt(g,n)$ for some $n > 0$. Define $O=\cup_{g>1}O_g$. Define $Per$ as the set of all $r \in (0,\infty)$ for which there exists a periodic packing $x$ with $\P(x) = r$ and $d_x = D(r)$. And finally, define $Per_g$ as set of all $r$ in $Per$ for which there exists a periodic packing $x$ with $\P(x) = r,\ d_x = D(r)$, and a subgroup $G'$ of $G_x$ such that $\H/G'$ has genus $g$. \vs.1 \nd {\bf Corollary 3}. Let $g > 1$. Then $Per_g\subset O_g$. \vs.1 \nd Proof. Suppose $r\in Per_g$ and $r\notin O_g$. Then there exists $r' > r$ with $f(g,r) = f(g,r')$. So there is a packing $x'$ with $\P(x')=r'$ and a subgroup $G'$ of $G_{x'}$ with $\H/G'$ of genus $g$ and the number of disks of $x'/G'$ equal to $f(g,r')$. Let $x$ be the packing with $C_x=C_{x'}$ and with $\P(x)=r$. Since $\H/G'$ has genus $g$ and $x/G'$ has $f(g,r)$ disks, with $r\in Per_g$, $x$ must be optimal. But $x$ satisfies these hypotheses of Lemma 3 with $t=2(r'-r)$. Hence $x$ is not completely saturated. But $x$ is periodic, so Lemma 2 implies $x$ is not optimal. This contradiction proves the corollary. \qed \vs.1 \nd {\bf Corollary 4}. $Per$ is countable. \vs.1 \nd Proof. $Per=\cup_{g>1}Per_g$. By Corollary 3, $Per_g\subset O_g$. Thus $Per\subset O$, and $O$ is obviously countable. \vs.1 \nd This completes the proof of the Theorem.\qed \vs.1 \nd {\bf 3. Conclusion}. \vs.1 The definition we propose for optimally dense (measures and) packings circumvents some of the difficulties of more direct approaches. We have justified the definition of density of invariant measures on packings in three ways: by its relation to the limit of the density in expanding compact subregions of packings, using the ergodic theorem; by its coincidence with the density in Voronoi cells; and by its coincidence with density in a fundamental domain, for periodic measures. We have used the definition of density to define optimally dense (measures and) packings and proved that: for the countable number of ``tight'' radii, the obvious packings, of high symmetry, are optimally dense; and that for all but countably many radii, optimally dense packings must have low symmetry. Further progress should come when the first specific example of a low-symmetry optimum is analyzed. \vs.1 \nd {\bf Acknowledgments}. We are very grateful to Oded Schramm for pointing us to [BeS] and its use in defining density in the hyperbolic plane. \vfill \eject \nd {\bf References} \vs.3 \nd \item{[BeS]} I. Benjamini and O. Schramm, Percolation in the hyperbolic plane, preprint, Hebrew University, Jan. 2000. Available from http://front.math.ucdavis.edu/ \item{[Bor]} K. B\"or\"oczky, Sphere packing in the hyperbolic plane I (in Hungarian), {\it Mat. Lapok} 25(1974) 265-306. \item{[Bow]} L. Bowen, Circle packing in the hyperbolic plane, preprint, University of Texas, June 1999. Available from the electronic preprint archive mp\_arc@math.utexas.edu \item{[Bus]} P. Buser, {\it Geometry and Spectra of Compact Surfaces}, Birkhauser, Boston, 1992. \item{[Fej]} L. Fejes T\'oth, {\it Regular Figures}, Macmillan, New York, 1964. \item{[FeK]} G. Fejes T\'oth and W. Kuperberg, Packing and covering with convex sets, chapter 3.3 in {\it Handbook of Convex Geometry}, ed.\ P. Gruber and J. Wills, North Holland, Amsterdam, 1993. \item{[Gar]} M. Gardner, Extraordinary nonperiodic tiling that enriches the theory of tiles, {\it Sci.\ Am.\ (USA)} (December 1977), 110-119. \item{[Hal]} T. Hales, preprints available from http://www.math.lsa.umich.edu/~hales/countdown/ \item {[MaM]} G.A. Margulis and S. Mozes, Aperiodic tilings of the hyperbolic plane by convex polygons, {\it Israel J. Math.} 107(1998), 319-332. \item {[Moz]} S. Mozes, Aperiodic tilings, {\it Invent. Math.} 128(1997), 603--611. \item{[NeS]} A. Nevo and E. Stein, Analogs of Weiner's ergodic theorems for semisimple groups I, {\it Annals of Math.} 145(1997), 565-595. \item{[Ra1]} C. Radin, Global order from local sources, Review-Expository Paper, {\it Bull. Amer. Math. Soc.} 25(1991), 335-364. \item{[Ra2]} C. Radin, {\it Miles of Tiles}, Student Mathematical Library, Vol. 1, Amer. Math. Soc., Providence, 1999. \item{[RaW]} C. Radin and M. Wolff, Space tilings and local isomorphism, {\it Geometriae Dedicata} 42(1992), 355-360. \item{[Sco]} P. Scott, Subgroups of surface groups are almost geometric, {\it J. London Math. Soc.} (2) 17(1978), 555--565. \vs1 \line{Lewis Bowen, Mathematics Department, University of Texas, Austin, TX\ \ 78712} \nd {\it Email address}: {\tt lbowen@math.utexas.edu} \vs.1 \line{Charles Radin, Mathematics Department, University of Texas, Austin, TX\ \ 78712} \nd {\it Email address}: {\tt radin@math.utexas.edu} \vfill \end ---------------0011121021195--