Friday, 15 June 2007

nt.number theory - A "round" lattice with low kissing number?

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...

No comments:

Post a Comment