On the construction of dense lattices with a given automorphisms group
[Construction de réseaux denses avec un groupe d’automorphismes donné]
Gaborit, Philippe ; Zémor, Gilles
Annales de l'Institut Fourier, Tome 57 (2007), p. 1051-1062 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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

Publié le : 2007-01-01
DOI : https://doi.org/10.5802/aif.2286
Classification:  06B20,  03G10
Mots clés: réseaux, borne de Minkowski-Hlawka, probabilités, groupe d’automorphisme, codes doublement circulants 
@article{AIF_2007__57_4_1051_0,
     author = {Gaborit, Philippe and Z\'emor, Gilles},
     title = {On the construction of dense lattices with a given automorphisms group},
     journal = {Annales de l'Institut Fourier},
     volume = {57},
     year = {2007},
     pages = {1051-1062},
     doi = {10.5802/aif.2286},
     zbl = {1172.11021},
     mrnumber = {2339326},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_2007__57_4_1051_0}
}

Gaborit, Philippe; Zémor, Gilles. On the construction of dense lattices with a given automorphisms group. Annales de l'Institut Fourier, Tome 57 (2007) pp. 1051-1062. doi : 10.5802/aif.2286. http://gdmltest.u-ga.fr/item/AIF_2007__57_4_1051_0/

[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, Tome 10 (1992), pp. 217-221 | Article | MR 1191572 | Zbl 0776.52006

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

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

[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), Tome 64 (1992) no. 2, pp. 265-338 | Article | MR 1143227 | Zbl 0739.11033

[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 | Article | MR 2076096 | Zbl 1071.52018

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

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

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

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