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