On the construction of dense lattices with a given automorphisms group

Gaborit, Philippe; Zémor, Gilles

Annales de l'Institut Fourier, Tome 57 (2007) no. 4, pp. 1051-1062.

On s’intéresse à la construction de réseaux denses de ${ℝ}^n$ contenant un groupe d’automorphismes donné non trivial. On obtient une telle construction de réseaux, dont la densité est au moins $cn{2}^{-n}$, ce qui, à une constante multiplicative près, atteint la meilleure densité asymptotique connue d’un empilement de sphères. Plus précisément, on exhibe, pour une suite infinie de dimensions $n$, un ensemble de réseaux de groupe d’automorphismes fixé et de taille $n$, et dont une proportion constante atteint la borne inférieure précitée sur la densité. La complexité algorithmique de la construction d’une base d’un tel réseau dense est d’ordre exp$(nlogn)$, ce qui améliore la complexité des constructions déjà connues de réseaux d’une densité équivalente. La méthode que nous proposons utilise la construction A de Leech et Sloane appliquée à une classe particulière de codes  : la classe des codes doublement circulants.

We consider the problem of constructing dense lattices in ${ℝ}^n$ with a given non trivial automorphisms group. We exhibit a family of such lattices of density at least $cn{2}^{-n}$, which matches, up to a multiplicative constant, the best known density of a lattice packing. For an infinite sequence of dimensions $n$, we exhibit a finite set of lattices that come with an automorphisms group of size $n$, and a constant proportion of which achieves the aforementioned lower bound on the largest packing density. The algorithmic complexity for exhibiting a basis of such a lattice is of order exp$(nlogn)$, which improves upon previous theorems that yield an equivalent lattice packing density. The method developed here involves applying Leech and Sloane’s Construction A to a special class of codes with a given automorphisms group, namely the class of double circulant codes.

Classification : 06B20, 03G10
Keywords: Lattice packings, Minkowski-Hlawka lower bound, probability, automorphism group, double circulant codes
Mot clés : réseaux, borne de Minkowski-Hlawka, probabilités, groupe d’automorphisme, codes doublement circulants

[1] Bacher, R. A new inequality for the Hermite constants, arXiv:math.NT/0603477, 2006

[2] Ball, K. A lower bound for the optimal density of lattice packings, Internat. Math. Res. Notices, Volume 10 (1992), pp. 217-221 | DOI | MR | Zbl

[3] Conway, J.; Sloane, N. J. A. Sphere packings, lattices and groups, 290, Springer-Verlag, New-York (third edition), 1999 | MR | Zbl

[4] Davenport, H.; Rogers, C. A. Hlawka’s theorem in the geometry of numbers, Duke Math. J., Volume 14 (1947), pp. 367-375 | DOI | Zbl

[5] Gaborit, P.; Zémor, G. Asymptotic improvement of the Gilbert-Varshamov bound for linear codes, Inter. Symp. Inf. Theo., ISIT 2006, Seattle (2006), pp. 287-291

[6] Heath-Brown, D. R. Zero-free regions for Dirichlet $L$-functions and the least prime in an arithmetic progression, Proc. London Math. Soc. (3), Volume 64 (1992) no. 2, pp. 265-338 | DOI | MR | Zbl

[7] Krivelevich, Michael; Litsyn, Simon; Vardy, Alexander A lower bound on the density of sphere packings via graph theory, Int. Math. Res. Not. (2004) no. 43, pp. 2271-2279 | DOI | MR | Zbl

[8] Rogers, C. A. Existence theorems in the geometry of numbers, Ann. of Math. (2), Volume 48 (1947), pp. 994-1002 | DOI | MR | Zbl

[9] Rush, J. A. A lower bound on packing density, Invent. Math, Volume 98 (1989) no. 3, pp. 499-509 | DOI | MR | Zbl

[10] Rush, J. A.; Sloane, N. J. A. An improvement to the Minkowski-Hlawka bound for packing superballs, Mathematika, Volume 34 (1987) no. 1, pp. 8-18 | DOI | MR | Zbl

[11] Shlosman, S.; Tsfasman, M. Random lattices and random sphere packings: typical properties, Mosc. Math. J., Volume 1 (2001) no. 1, pp. 73-89 | MR | Zbl