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--