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 tex2html_wrap_inline1243 and tex2html_wrap_inline1245 leading to tex2html_wrap_inline1247 independent of tex2html_wrap_inline791 . The density of the lattice packing is tex2html_wrap_inline1251 . For example, for d=2 and with the generator matrix

displaymath1255

the density is

displaymath1257

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

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

displaymath1267

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

Packings with radius tex2html_wrap_inline1289 . With tex2html_wrap_inline1289 , and tex2html_wrap_inline1293 , we get tex2html_wrap_inline1295 and a center density tex2html_wrap_inline1297 . This density is larger than the density of tex2html_wrap_inline1261 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 tex2html_wrap_inline1289 .

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

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

propo231

trivlist422

Remark.
For prime p, a packing in the proposition defines a code in the vector space tex2html_wrap_inline1407 . 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 tex2html_wrap_inline1411 .

  coro237

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, tex2html_wrap_inline1437 , this gives a packing with density 0.73386212.
2) The construction can be modified by taking for example tex2html_wrap_inline1441 with suitable p', which gives for some r denser packings than tex2html_wrap_inline1447 .

Special packings Fig. 5. Packing densities for special packings in the case d=2,d=3. For each r, we plot the density obtained by taking tex2html_wrap_inline1453 , where p=p(r) is the integer described in corollary 4.2. The densities seem to accumulate at the maximal known density tex2html_wrap_inline1457 in two dimensions and to tex2html_wrap_inline1459 in three dimensions.
We were also looking for dense packings using a multiscale Monte Carlo method. We restricted ourselves to the standard basis in tex2html_wrap_inline555 and to packings defined by one interval and went only up to dimension 5. One method was to shoot randomly vectors tex2html_wrap_inline791 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 tex2html_wrap_inline791 . 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 tex2html_wrap_inline1477 is a piecewise linear function having gradients of the order tex2html_wrap_inline1479 . We would need therefore to check roughly at tex2html_wrap_inline1481 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 tex2html_wrap_inline1477 is just too wiggly.

Some good packings were obtained by taking a good solution tex2html_wrap_inline1489 and choosing tex2html_wrap_inline1491 so that the packing tex2html_wrap_inline1493 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 tex2html_wrap_inline1499 .

tabular255

Table 1. Some examples of packings in three dimension. The packing with radius tex2html_wrap_inline1547 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.

tabular266

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

tabular275

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


next up previous
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