Next: Examples of quasi-periodic packings Up: Maximizing the packing density Previous: Sphere packings and dynamical

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 tex2html_wrap_inline823 , a rotation vector tex2html_wrap_inline825 , a radius r bigger than zero and the standard basis tex2html_wrap_inline829 in tex2html_wrap_inline555 .

Define tex2html_wrap_inline833 , where tex2html_wrap_inline835 is the Euclidean tex2html_wrap_inline837 -norm in tex2html_wrap_inline555 . If tex2html_wrap_inline841 , we get for any tex2html_wrap_inline843 a sphere-packing


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 ;SPMlt;r. This packing is not periodic if one of the numbers tex2html_wrap_inline857 is irrational. We call such a packing quasi-periodic.



The density of a quasi-periodic sphere-packing can be approximated explicitly by periodic sphere-packings because every vector tex2html_wrap_inline791 is a limit of rational vectors and the density depends continuously on tex2html_wrap_inline791 . It is not excluded that in some dimension, the highest possible packing is aperiodic, but we will see that if J consists of a single interval, the maximal density is obtained by a periodic packing.

The center density tex2html_wrap_inline895 of a sphere-packing is defined as tex2html_wrap_inline897 , where tex2html_wrap_inline721 is the density and V(d) is the volume of the unit sphere in tex2html_wrap_inline555 .



Remark. Note that evenso the map tex2html_wrap_inline931 is not continuous, the density is continuous.

tex2html_wrap1235 Fig. 3. The set tex2html_wrap_inline935 with the vector tex2html_wrap_inline937 . On the right, we see the set tex2html_wrap_inline939 and the interval tex2html_wrap_inline941 .
We can replace the standard basis by any other basis tex2html_wrap_inline943 with tex2html_wrap_inline945 .



Given , we find J consisting of one interval such that tex2html_wrap_inline841 . Start with tex2html_wrap_inline973 and form the finite set


The points tex2html_wrap_inline977 nearest to tex2html_wrap_inline979 are symmetric to 0. Form J=[0,c). We check that tex2html_wrap_inline985 . The center density of the packing with this interval is then tex2html_wrap_inline987 .

1) We can add a second interval J' as follows. Assume the interval tex2html_wrap_inline991 of length tex2html_wrap_inline993 is the largest interval disjoint from tex2html_wrap_inline995 . There are three cases. If tex2html_wrap_inline997 , take tex2html_wrap_inline999 . If tex2html_wrap_inline1001 , define tex2html_wrap_inline1003 . In the other case, take tex2html_wrap_inline1005 . We show now that, tex2html_wrap_inline1007 . For tex2html_wrap_inline1009 , we have tex2html_wrap_inline1011 and tex2html_wrap_inline1013 , since J' is disjoint from tex2html_wrap_inline1017 . For tex2html_wrap_inline1019 , we have also that tex2html_wrap_inline1021 is disjoint from J'. It is also disjoint from tex2html_wrap_inline1025 , since tex2html_wrap_inline1027 . The center density of the packing is then tex2html_wrap_inline1029 .
2) We could proceed as follows to get larger and larger sets J. Given tex2html_wrap_inline1033 , take any point tex2html_wrap_inline1035 outside . If is disjoint from tex2html_wrap_inline1033 , we can find a maximal interval which has the property . Form . Repeating this construction leads to a finite or countable union J of half-open intervals which has the property that . In other words, we are adding spheres until the covering is saturated, in the sense that there is no longer room with positive density for adding additional spheres. Usually, in our experiments if the first interval is large enough, then J is already saturated and no second interval is needed.
3) For getting high densities, we have to choose r such that the number of lattice points inside the ball of radius r is just below a point of discontinuity. Necessary is tex2html_wrap_inline1059 , where tex2html_wrap_inline1061 and that there is a lattice point on the boundary of the ball with radius r so that a further increase of r increases the number of lattice points. By a theorem of Lagrange in number theory, this is always true if tex2html_wrap_inline1067 and tex2html_wrap_inline1059 . In other words, by extending the variational problem and varying r also, a packing which maximizes the density has the property that tex2html_wrap_inline1073 is an integer.
4) We expected to get high densities for radii r, for which many lattice points are on the boundary of a sphere of radius r because of a possible large kissing number. The experiments confirm this in some cases like r=5, d=2,3, but it was not the rule.



tex2html_wrap1237 Fig. 4. The piecewise linear function tex2html_wrap_inline1107 in the case r=5. As larger the value, as brighter is the point tex2html_wrap_inline1111 . On the black resonance lines, the value is zero.
The next proposition deals with the variational problem to maximize the nondifferentiable function tex2html_wrap_inline1113 over the d dimensional torus of parameters tex2html_wrap_inline791 , when the dimension d and the radius r are fixed. The proposition says that this variational problem has only rational "critical points". It means that on some finite dimensional manifolds of almost periodic packings, the maximal density is achieved by periodic packings.



The same argument shows that for any finite set tex2html_wrap_inline1217 not containing the origin, the function


takes its global maximum on a rational point tex2html_wrap_inline1221 . We can consider therefore any packing problem, where the spheres are replaced by some compact set tex2html_wrap_inline1223 . The analogues problem is to find for a given r, the densest packing of tex2html_wrap_inline555 with copies tex2html_wrap_inline1229 of tex2html_wrap_inline1231 . The same construction gives a d-dimensional manifold of almost periodic packings for which the density exists. The maximal density on this manifold is obtained by periodic packings.

next up previous
Next: Examples of quasi-periodic packings Up: Maximizing the packing density Previous: Sphere packings and dynamical

Oliver Knill
Mon Jun 22 17:57:55 CDT 1998