Packings with large minimum kissing numbers (Q1377762)

The minimum kissing number of a collection of objects in \(R^n\) with pairwise disjoint interiors is the minimum, over all objects \(B\) in the collection, of the number of other objects touched by \(B\). It is known that a lattice packing of unit balls in \(R^n\) may have a minimum kissing number of at least \(2^{\Omega (\log^2n)}\). Here, the author constructs, where \(n=4^k\), a finite collection of balls with a kissing number greater than \(2^{\sqrt n}\). It may be seen that this is a very significant increase over the best known result for a lattice packing. The first step is to construct, for each \(k\geq 2\), a linear, binary error correcting code of length \(4^k\), dimension \(k(2^{k-1} +1)\) and minimum distance \(4^{k-1}\), in which the number of words of minimum Hamming weight is greater than \(2^{\sqrt n}\). The desired construction is given by a set of balls, centered at the vectors of the code, and of radius \(2^{k-2}\). The author conjectures, in closing, that further order-of-magnitude improvements remain to be made; in particular, that there exist lattice packings in \(R^n\) with kissing number \(2^{\Omega (n)}\).