Next: Isospectral packings with a Up: Maximizing the packing density Previous: Quasi-periodic sphere-packings

Examples of quasi-periodic packings

Lattice packings. Assume the packing is a lattice packing defined by the generator matrix U. We can take r=1 so that and leading to independent of . The density of the lattice packing is . For example, for d=2 and with the generator matrix

the density is

which is known to be the highest density in two dimensions.

Packings with radius give the lattices . Take and the standard basis . We have

With and J=[0,1/2], we get and the density is corresponding to a center density . These packings are lattice packings called . In dimensions d=3,4,5, these packings are the packings with the highest known density like for d=3, the density is and in four dimensions .

Packings with radius . With , and , we get and a center density . This density is larger than the density of for d;SPMgt;12. These packings were the densest we found numerically for d=2,3,4,5 in the class of quasi-periodic packings with .

Packings with radius r=2. We have the problem to find integers p and such that in the group , no sum gives zero if . In other words, all sums are different from zero modulo p. We can build solutions by defining recursively a sequence with the linear difference equation , and define the vector . In the case or , or , these were the densest 2-packings we found in our class. For d=5, the 2-packing was denser than the 2-packing determined by .

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 such that for any with , the equation in has no solution. The center density of the corresponding packing is then . We rephrase the result in the following proposition.

Remark.
For prime p, a packing in the proposition defines a code in the vector space . In coding theory, one considers however rather the packing problem with the Hamming metric instead of the Euclidean metric.

We found some good packings in the special case, when r is an integer and .

Remarks.
1) Because of the periodicity of the packing, we have for even r that p-r/2 is a multiple of r and that for odd r, p-(r+1)/2 is a multiple of r.
Example: for r=89, , this gives a packing with density 0.73386212.
2) The construction can be modified by taking for example with suitable p', which gives for some r denser packings than .

 Fig. 5. Packing densities for special packings in the case d=2,d=3. For each r, we plot the density obtained by taking , where p=p(r) is the integer described in corollary 4.2. The densities seem to accumulate at the maximal known density in two dimensions and to in three dimensions.
We were also looking for dense packings using a multiscale Monte Carlo method. We restricted ourselves to the standard basis in and to packings defined by one interval and went only up to dimension 5. One method was to shoot randomly vectors for fixed r and to adapt the search step near good parameters. We did not assume that the best density is obtained for a rational . Indeed, we conjectured and proved only after having done some experiments that the maxima are rational. For larger values of r and especially for higher dimensions, the searches need a lot of computing time. The reason is that for fixed r and d, the function is a piecewise linear function having gradients of the order . We would need therefore to check roughly at points in order to find the global maximum since so many local maxima are expected. This is an very time consuming task also for quite small r and d's. The huge number of local minima is also the reason why the common methods for minimizing multidimensional functions like the downhill simplex method would not work well here. The function is just too wiggly.

Some good packings were obtained by taking a good solution and choosing so that the packing has maximal density. This is motivated (evenso there is no direct relation) by the laminated lattice construction (see [3]), which also constructs d-dimensional packings by building up layers of (d-1)-dimensional packings which are known to be dense.

We never found a denser packing while using two intervals. The search is also algorithmically more expensive, since we have to order the set .

Table 1. Some examples of packings in three dimension. The packing with radius is the Kepler packing. The packing with radius 120 gives a slightly denser packing as the packing reported in [17] using Penrose tilings which have densities accumulating by 0.7341.

Table 2. Some examples of packings in four dimension. The first packing is the packing which is believed to be the densest.

Table 3. Some examples of packings in five dimension. The first packing is the packing which is believed to be the densest.

Next: Isospectral packings with a Up: Maximizing the packing density Previous: Quasi-periodic sphere-packings

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