Historically, the lattices with high density were studied intensively, e.g. E_8 lattice or Leech Lattice. However, there are situations that lattices with low kissing number are required. Specifically, I am wondering if there is any infinite family of n-dimension lattices which the kissing number is bounded by poly(n), and still relatively dense?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
If the question is about the asymptotic behavior in high dimensions then I do not think it is known or even conjectured that the kissing number for the densest packing is not polynomial in n. To the best of my memory (but check the book by Conway and Sloane) there are no known examples of lattices where the kissing number is exponential, and the best known bound are only quasi-polynomial ($n^{\log n}$).
So "dense lattice packing" and "huge kissing numbers" are not the same in very high dimensions. (There are the same in dimension 24!). If you are interested in interesting notions of low density packings you can think about packings which are locally densest but globally very undense. It does make sense to consider, even in low dimensions, what is the smallest "local maximum" for density of lattices.
Update: Let me add some more details on the connection between kissing number and more generally "the low end of the distance distribution" of a packing and the density. It is convenient to talk, more genarally, about spherical codes, and also to draw the analogy with binary codes. The densest examples of spherical codes and binary error correcting codes are obtained by randomized constructions. For those the kissing number is expected to be subexponential. It is known that if these randomized bounds can be improved to get higher density than some relaxed notion of a kissing number will be exponential. (This is a result of Nati Linial and me for the binary case and I think that it was extended to larger alphabets and sperical codes.) As I mentioned for sphere packing (and I think also for general spherical codes) no example is known where the kissing number is exponential. For error-correcting codes over a large alphabet the algebraic geometric codes (which are denser than the randomized construction) give such an example. This example can be transforned to the binary case but it doesnot give a higher density.
I think that the notion of minimum density among local maximum density packings was studied and also the corresponding question for covering. At least in low dimensions. This looks like the "correct" understanding of the question. But I do not recall the details.
More update: Frank Vallentin gave me some further relevant information. Indeed the relevant notion in discussing the problem is that of a "perfect lattice". In a perfect lattice, the following equality is true:
dim span{$v~ v^t: ~v$ shortest nonzero lattice vector} = $n(n+1)/2$.
(In general one only has the inequality "$\le$") A lattice which is a local maximum for the packing density function is always perfect.
Trying to find perfet lattices with low density (which seems to be one purpose of the question if we put aside the kissing number issue), is interesting. Coxeter conjectured (Extreme forms, 1951) that the lattice $A_n$, (which is perfect,) gives the lowest density among all perfect lattices. It is known to be true up to dimension 8.
There is another conjecture by Conway and Sloane (Low dimensional lattices III, Perfect forms, 1988) saying that Coxeter's conjecture is wrong if the dimension is large enough...
answered Nov 19, 2009 at 21:59
$\begingroup$
$\endgroup$
The question is seems ill-posed, because you can always make a small deformation of a lattice to send the kissing number to zero. Even if you expand the spheres as much as possible, the kissing number will generically be 2. Even if you require linearly independent kissing points, then I think that generically there will only be 2n of them.
You could look at unimodular lattices. By definition, this is a lattice such that if you write the Euclidean dot product in a basis of the lattice, its matrix has integer entries and determinant 1. If you drop either determinant 1 or integer entries, you're back to the deformation instability. There are only finitely many unimodular lattices in any fixed dimension, and not very many in low dimensions. I don't know the behavior of unimodular kissing numbers in high dimensions.
Gil's answer is better. My comments make sense in low dimensions. But in high dimensions, people have a lot of trouble making lattices with large kissing numbers at all. That turn of events didn't occur to me.
answered Nov 5, 2009 at 2:35
$\begingroup$
$\endgroup$
1
Gil´s answer is complete. But I want to know about low kissing number in codes. It´s true that high density is favorable for codes. But, when we have codes with the same density how to find the best code? Is the best code, in this sense, whose have the smaller kissing number?
-
$\begingroup$ Ask a question instead of giving an answer, then! :) $\endgroup$ Commented Feb 8, 2010 at 16:23