\documentstyle[]{article}
% this is a plain LaTeX file and does not use any additional style files
% this version for the archive does not contain figures
\setlength{\topmargin}{-1cm}
%\setlength{\topmargin}{-4cm} % for Next Printer
\setlength{\headheight}{1.5cm}
\setlength{\headsep}{0.3cm}
\setlength{\textheight}{21cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\textwidth}{14.0cm}
\author{Oliver Knill\thanks{Division of Physics, Mathematics and Astronomy,
Caltech, Pasadena, CA, 91125,
e-mail: $knill@cco.caltech.edu$ }}
\title{Maximizing the packing density on a class of
almost periodic sphere packings}
\date{August 29, 1995} % submitted version
\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{propo}[thm]{Proposition}
\newtheorem{coro}[thm]{Corollary}
\newenvironment{proof}{\begin{trivlist}\item[]{\em Proof.\/\ }}%
{\hfill$\Box$\end{trivlist}}
\def\marnote#1{\marginpar{\scriptsize\raggedright #1}}
%\input mssymb
%\newcommand{\RR}{{\Bbb R}} \newcommand{\ZZ}{{\Bbb Z}}
%\newcommand{\NN}{{\Bbb N}} \newcommand{\CC}{{\Bbb C}}
%\newcommand{\QQ}{{\Bbb Q}} \newcommand{\TT}{{\Bbb T}}
\newcommand{\RR}{{\bf R}} \newcommand{\ZZ}{{\bf Z}}
\newcommand{\NN}{{\bf N}} \newcommand{\CC}{{\bf C}}
\newcommand{\QQ}{{\bf Q}} \newcommand{\TT}{{\bf T}}
\newcommand{\Scal}{\mbox{$\cal S$}}
\newcommand{\Ycal}{\mbox{$\cal Y$}}
\parskip=4pt plus1pt
\setlength{\parindent}{0cm}
%\renewcommand{\baselinestretch}{1.5}
\begin{document}
\bibliographystyle{plain}
\maketitle
\begin{abstract}
We consider the variational problem of maximizing the packing density
on some finite dimensional set of almost periodic sphere packings. We
show that the maximal density on this manifold is obtained by periodic
packings. Since the density is a continuous, but a nondifferentiable function
on this manifold, the variational problem is related to
number theoretical questions.
Every sphere packing in $\RR^d$ defines
a dynamical system with time $\RR^d$. If the dynamical
system is strictly ergodic, the packing
has a well defined density. The packings considered here
belong to quasi-periodic dynamical systems, strictly ergodic
translations on a compact topological group and are higher dimensional
versions of circle sequences in one dimension. In most cases,
these packings are quasicrystals because the dynamics has
dense point spectrum.
Attached to each quasi-periodic sphere-packing
is a periodic or aperiodic Voronoi tiling of $\RR^d$ by
finitely many types of polytopes. Most of the tilings
belonging to the $d$-dimensional set of packings are aperiodic.
We construct a one-parameter family of dynamically isospectral
quasi-periodic sphere packings
which have a uniform lower bound on the density when variing the radius
of the packing. The simultaneous density bound depends on constants in
the theory of simultaneous Diophantine approximation.
\end{abstract}
\section{Introduction}
Finding sphere packings in $\RR^d$ with maximal density
are important mostly unsolved
problems with many applications (see \cite{CS}).
The problem is interesting in
geometry, group theory, crystallography or physics.
Here, we look at the problem from a dynamical system point
of view. \\
It is still controversial, whether the
{\bf Kepler conjecture} claiming that
there is no sphere-packing in $\RR^3$ with density higher
than $\pi/\sqrt{18}$ is open or proven
(\cite{Hal94,Hsi95}). Also
for dimensions bigger than $3$, the best densities are still not known evenso
there is a list of candidates (see \cite{CoSl95},\cite{CS}).
According to a general result of Groemer (\cite{Gro63} see also \cite{Gruber}),
there exists a sphere packing which has a maximal density. \\
Periodic packings and often lattice packings
have achieved the highest today known densities (see \cite{CS}).
Following an advise in \cite{Fejes} p. 188, we restrict us here
to a subclass of packings, where we know that
the density of the packing exists.
This family of quasicrystals,
almost periodic sphere-packings in $\RR^d$
which form a part of the huge space $\Scal$ of all packings.
Quasicrystalline dense sphere packings are of interest in physics
(see for example \cite{Smi93,Coc94}).
The ergodic-theoretical side of
the problem comes natural in the context of aperiodic tilings.
Tilings and packings are closely related since to every strictly ergodic
sphere-packing is attached a tiling of $\RR^d$
by Voronoi cells consisting of finitely many types of polytopes. \\
The quasicrystals in this article are defined by higher dimensional
circle sequences and have the property that the densities can
be computed explicitely from the parameters.
This allows for a machine to search through many of these packings
and to determine in each case the exact density.
The feature of being able to compute macroscopic quantities like densities
for aperiodic configurations
was also useful when we studied cellular automata on circle configurations
\cite{HoKn95}. The main motivation for the present work
was to investigate dense packings with a new class of packings.
We could consider many packings with high periodicity which are close
to the best known packing. \\
A packing $S \subset \ZZ^d$ can be described by a configuration
$n \mapsto x_n= \{0,1\}^{\ZZ^d}$.
The closure $Y$ of all the translates of $x$ in $\{0,1\}^{\ZZ^d}$
forms a {\bf subshift} with time $\ZZ^d$.
In general, there exist many shift-
invariant measures on $Y$ and the density depends
on the choice of the invariant measure.
For the packings, we consider here,
the subshift $Y$ has
a unique shift-invariant measure and it implies that the
density is well defined and can explicitly be determined.
Moreover, if we make a translation in the
$i'th$ coordinate, we get a one-dimensional strictly ergodic subshift
for which the dynamical spectrum (and so the diffraction spectrum)
is known to be pure point. The packings are therefore crystals or
quasicrystals (see \cite{Senechal}). \\
The organization of this article is as follows. In section 2, we relate
sphere packings with dynamical systems and point out, that the
uniquely ergodic packings have a well defined density.
In section 3, we consider a finite dimensional class of strictly
ergodic sphere packings and compute the density of the packings. We
show that the density functional takes its maximum on periodic packings.
In section 4, we give classes of such packings and relate the problem
to find dense packings to number theoretical questions. We also report
about packings found by numerical experiments.
In section 5, we will construct a one-parameter family
of isospectral sphere packings
which have a uniform positive density depending on constants in
simultaneous Diophantine approximation.
In section 6, we discuss a related construction for coverings.
Relations with other topics are outlined in section 7 and in section 8,
some open problems are summarized.
\section{Sphere packings and dynamical systems}
A $r$-{\bf sphere packing} $S$ is a countable set of points in $\RR^d$
such that the minimal distance between two points is $\geq 2r$.
Let $\Scal$ be the set of all sphere packings. Define a metric on $\Scal$
by $d(S,S')=\min(1,\epsilon)$, where $\epsilon$ is the smallest number
such that $T_x S = S+x =S'$ on the ball $\{||y|| \leq 1/\epsilon\}$
for some $x \in \RR^d$. With this metric, which is adapted from the metric for
tilings, $(\Scal,d)$ is a complete metric space. Let $\RR^d$ act
on $\Scal$ by translations $T_t(S)=S+t$. Given a specific sphere packing $S$,
we can look at the closure $X_S$ of the orbit
$\RR^d(S)=\{S+t \; | \; t \in \RR^d \}$. If $X_s$
compact in $\Scal$,
we get a dynamical system $(X_S,\RR^d)$, where $X_S$
is a compact metric space on which $\RR^d$ acts by homeomorphisms. Such
a system is called {\bf minimal} or {\bf almost periodic},
if for every $S \in \Scal$, the orbit is dense in $X_S$,
it is called {\bf uniquely ergodic}, if there exists exactly one $\RR^d$-
invariant measure on $X_{S}$, {\bf strictly ergodic},
if it is uniquely ergodic and minimal. \\
Remarks. \\
1) A metric on $\Scal$, with respect to
which the subset of $r$-packings in $\Scal$ becomes
compact is described in \cite{Dwo93}. For our purposes,
the stronger metric $d$ is good enough. \\
2) In the
statistical mechanics literature, a sphere packing is also called
a configuration with hard core restriction. \\
3) By normalization of the distance in $\RR^d$, we could assume that a
sphere packing has radius $r=1$.
We keep the additional parameter $r$ since
we are interested in packings $S \subset \ZZ^d$. \\
We call a sphere packing $S$ {\bf rational}, if all points of $S$ belong
to a $d$-dimensional lattice $U \cdot \ZZ^d \subset \RR^d$, where
$U$ is an invertible $d \times d$-matrix.
On a rational sphere packing, there is a
natural $\ZZ^d$-action, by identifying $\ZZ^d$ with the maximal
subgroup of $\RR^d$ which
leaves the lattice invariant. The packing $S$ consists then of
a subset of the lattice and every rational sphere packing defines so a
subshift $\Ycal_S \subset \{0,1\}^{\ZZ^d}$.
This set $\Ycal_S$ is is invariant under the $\ZZ^d$-action.
A rational sphere packings is called
{\bf strictly ergodic}, if the dynamical system $(\Ycal_S,\ZZ^d)$ is strictly
ergodic.
If every shift of the $\ZZ^d$-action is periodic, $S$ is called {\bf periodic},
Remarks. \\
1) Clearly, a periodic packing
is rational and also strictly ergodic. \\
2) Periodic packings are dense in $\Scal$ since we can
periodically continue a given packing outside a given box.
Periodic packings are also
dense in the set of rational packings. \\
3) The name {\bf almost
periodic} which stands as a synonym for minimal
has no relation
with the usual almost periodicity of functions or sequences. The expression
almost periodic is however widely used in the topological dynamics
and mathematical physics literature. \\
The lower and upper {\bf densities} of a sphere packing $S$ are defined as
$$ \Delta^-= \liminf_{n \rightarrow \infty}
\frac{|S \cap \Lambda_n|}{|\Lambda_n|} \; ,
\Delta^+=\limsup_{n \rightarrow \infty}
\frac{|S \cap \Lambda_n|}{|\Lambda_n|} \; , $$
where $\Lambda_n=[-n,n]^d$. If $\Delta=\Delta^-=\Delta^+$, then $\Delta$ is
called the {\bf density} of $S$.
\begin{lemma}
For a strictly ergodic sphere packing, the density exists.
\end{lemma}
\begin{proof}
The limits
$$ f \mapsto \phi^{\pm}(f)= \pm \limsup_{n \rightarrow \infty} \pm
|\Lambda_n|^{-1} \sum_{k \in \Lambda_n} f(T^k(x)) $$
define bounded functionals $\phi^{\pm}$
on $C(X)$ which are invariant under the translations $f \mapsto f(T^k)$.
By Riesz representation theorem, $\phi^{\pm}(f)=\int f \; d\nu^{\pm}$,
where $\nu^{\pm}$ are some measures on $X$ which are invariant under the
stricly ergodic $\ZZ^d$ or $\RR^d$ dynamical system $(X,T,\mu)$. It follows
from the unique ergodicity that $\nu^{\pm}=
\mu$ and hence that the two limits coincide.
For $\rho: \Scal \rightarrow \RR$ given by
$\rho(S)=1_{\{d(S_0,S)0$, we can make $B_1$ so large that the distance
between the original packing and the modified packing is smaller than
$\epsilon$. \\
3) We are forced to define the packing problem on a subclass of packings
since the density is not a continuous function on the
set of all packings for which the density exists: take such a
packing $S$ and define a sequence of packings $S_n$ obtained from $S$
by deleting all balls in distance less than $n$ from the origin.
The packings $S_n$ have all the same density but $S_n$ converges to
the $S_{\infty}=\emptyset$, which is a packing with zero density.
\section{Quasi-periodic sphere-packings}
We consider now a specific class of almost periodic sphere packings.
These packings contain also periodic packings but the computations do not
rely on the distinction between periodic and aperiodic. In order to find
dense packings experimentally, it was sometimes
of advantage, not to distinguish between
periodic and aperiodic packings.
Take a finite union of disjoint half-open intervals $J \subset \RR^1=\RR/\ZZ$, a
rotation vector $\alpha \in \RR^d$, a radius $r>0$ and the standard basis
$\{e_i\}_{i=1}^d$ in $\RR^d$. \\
Define $R(r)=\{ k \in \ZZ^d \; | \; 0 < ||\sum_{i=1}^d k_i e_i||_2 < r \}$,
where $|| \cdot ||$ is the Euclidean $l^2$-norm in $\RR^d$.
If $(J + R(r) \alpha) \cap J = \emptyset$,
we get for any $\theta \in \TT^1$ a sphere-packing
$$ S=\{ k \in \ZZ^d \;
| \; \sum_{i=1}^d \theta + k_i \alpha_i \in J \} \; . $$
If we put a sphere of radius $r/2$ at each point of $H$, we get a
$r$-packing because the maximal distance between two different points in $H$ is
by construction $2c$, take
$J'=[a,b)=[\theta_{i+1}-2c,\theta_{i+1}-c)$. If $c12$. These packings were
the densest we found numerically for $d=2,3,4,5$ in the class of quasi-periodic
packings with $r=\sqrt{3}$. \\
{\bf Packings with radius $r=2$}.
We have the problem to find integers $p$ and $a_1, \dots a_d$
such that in the group $\ZZ_p$, no sum $\sum n_i^2 a_i$ gives zero
if $\sum_i n_i^2 < r$. In other words, all
sums $a_{i_1} \pm a_{i_2} \pm a_{i_3}$ are different from zero modulo $p$.
We can build solutions by defining recursively a sequence $a_n$ with
the linear difference equation
$a_1=1,a_2=2$, $a_n=a_{n-1}+a_{n-2}+1$ and define the vector
$\alpha=(a_1,a_2, \dots , a_d)/(2a_d)$. In the
case $d=2,\alpha=(1,2)/4$ or $d=3,\alpha=(1,2,4)/8$,
or $d=4,\alpha=(1,2,4,7)/14$, these were the densest $2$-packings
we found in our class. For $d=5$, the $2$-packing
$\alpha=(1,3,5,7,9)/18$ was denser than the $2$-packing determined by
$\alpha=(1,2,4,7,12)/24$. \\
This construction of families of packings with increasing dimension
can be generalized for any $r$. The problem is to find the smallest
$p=p(d,r)$, such that there exist $d$ numbers $a_1, \dots, a_d \in \ZZ_p$
such that for any $n \in \ZZ^d$ with $||n||_20$.
The estimate $N(d,r \alpha) \geq C(d) \cdot r^{-d} d^{-d/2}$ is
crude for small $r$.
\section{Coverings}
The algorithm to compute packings can be modified to get coverings.
Assume, we have an interval $J \subset \TT^1$ such that $R(r) J=\TT^1$.
In this case, the spheres with centers in
$$ S(\theta)=\{ k \in \ZZ^d \;
| \; \sum_{i=1}^d \theta + k_i \alpha_i \in J \} \; $$
and radius $r$ are covering all $\ZZ^d$ and
the spheres of radius $r+\sqrt{d}/2$ are covering the whole space $\RR^d$.
The density of the covering is
$$ V(d) |J| (r+\sqrt{d}/2)^d \; . $$
\begin{propo}
There exist sphere-coverings of $\RR^d$ with densities
$$ V(d) (r+\sqrt{d}/2)^d \cdot M(d,r,\alpha)\; , $$
where
$$ M(d,r,\alpha)=\max_{\; ||n||_2 \leq r} \; \;
\min_{||m||_2 \leq r, m \neq n}
|(n-m) \alpha \; \; ({\rm mod} \; 1)| > 0\;. $$
\end{propo}
\begin{proof}
Given parameters $d,r$ and $\alpha$, we can find $M(d,r,\alpha)$ such that
$(n-m) \alpha \; \; {\rm mod} \; 1 \geq M(d,r,\alpha)$ for all
$||n||_2,||m||_2 \leq r$ satisfying
$n \alpha \neq m \alpha \; \; ({\rm mod} \; 1)$.
We can choose for the interval $J$ the largest gap in the finite set
$R(r) \cdot \alpha \subset \TT^1$, since then, $R(r) J$
is a covering of $\TT^1$. The length of $J$ is $M(d,r,\alpha)$.
\end{proof}
Remark. \\
This proposition
implies that in order to get a good covering,
the parameters $r$ and $\alpha$ have to be chosen in such a way that
$R(r) \cdot \alpha \subset \TT^1$ is as homogeneous as possible.
The computations for coverings are more involved as the computations for
packings since the determination of the set
$R(r) \cdot \alpha \; {\rm mod} \; 1$ includes a time-consuming
sorting.
\section{Related topics}
{\bf Crystallographic considerations.}
The packing question for spheres has been formulated by Hilbert
for general compact subsets $K$
of $\RR^d$. An example is to replace the Eucledean norm by the $l^p$ norm
$||n||_p=(\sum_{i=1}^d |n_i|^p)^{1/p}$ and to pack $\RR^d$ with with
$l^p$ spheres and clearly for $p=1$ or $p=\infty$, the maximal
packing density is $1$ and different $p$ will probably lead to different
lattices with optimal density. Parameters $p$, where the optimal packing type
changes should be considered as a bifurcation parameter. \\
For general $K$, the construction of quasiperiodic packings is the same
as already described.
We have only to replace $||n||_2 < r$
by $n \in {\rm int}(K)$ to obtain the corresponding densities.
General packing problems with
different type of subsets $K$ are interesting and relevant in
crystallography or chemistry, where $K$ takes the shape of a molecule.
The same proof as shown above shows that the
maximal packing density on $d$-dimensional manifolds
of quasi-periodic packings is attained by periodic packings if we take
only copies of $K$ which are obtained from $K$ by translation by
$n \in \ZZ^d$. Removing the last restriction might lead in general to aperiodic
packings with maximal density: an indication is that
there exist convex sets in $\RR^3$, the Schmitt-Conway-Danzer tiles,
for which the densest packing is aperiodic with density $1$.
We mention also a result in \cite{Fej95} which says that for
a generic set of convex sets in the plane, the densests packing is
not lattice like. \\
{\bf Quasicrystals}.
Crystals in nature are often periodic. A situation closest
to the periodic case are quasi-periodic crystals which are a family of
so called quasicrystals. Our result that in
a class of quasi-periodic crystals, the maximal density is attained on
periodic crystals can have physical relevance since high
densities are favored by stable crystalline structures. \\
{\bf Defects}.
If the packing is almost periodic, there are large domains, where the packing
looks periodic, but there must be defects, if the lattice is not
periodic.
For $\epsilon>0$, consider the $\epsilon$-collar $K_{\epsilon}$ of
the packing $S$ which consists of all points in $\RR^d$ which have distance
$\leq \epsilon$ from any ball. There exists a largest $\epsilon>0$,
such that the complement of $K_{\epsilon}$ still percolates.
The defect, the complement of $K_{\epsilon}$ with critical $\epsilon$
is not necessarily almost periodic since the
topology of $K_{\epsilon}$ does not depend continuously on $\epsilon$. \\
{\bf Minimizing energy}.
Moving on the manifold of almost periodic rational $r$-packings parametrized
by $\alpha \in \TT^d$ corresponds to (non continuous)
deformations of the crystal. The density, when considered as
a negative "energy" of the crystal is a piecewise linear continuous
function on the parameters. Variational methods do not apply in order
to find the maximal density which correspond to minimizing the energy
because the energy is not differentiable at the maximum. However, we have
seen that the minimal energy on this manifold is obtained by periodic
crystals. Since atomic dense packings are believed to be fundamental in
condenced matter, our toy model can in principle explain an aspect of
the stability of crystals. Moreover, the periodicity of some of the
crystals can be so large that it would be hard to distinguish them
experimentally from a true quasicrystal. \\
{\bf Aperiodic Voronoi tilings}.
For strictly ergodic packings,
there exists a constant $C$ such that if $x_n=1$ then there exists
$x_m=1$ with some $m$ satisfying $||m-n||_2 0$,
the smallest cyclic group $\ZZ_p=\ZZ/(p \ZZ)$ such that
there exist $a_1, \dots, a_d \in \ZZ_p$ such that
for any $n \in \ZZ^d$ with $0