We consider the problem of constructing dense lattices in with a given non trivial automorphisms group. We exhibit a family of such lattices of density at least , which matches, up to a multiplicative constant, the best known density of a lattice packing. For an infinite sequence of dimensions , we exhibit a finite set of lattices that come with an automorphisms group of size , 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, 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.
On s’intéresse à la construction de réseaux denses de contenant un groupe d’automorphismes donné non trivial. On obtient une telle construction de réseaux, dont la densité est au moins , 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 , un ensemble de réseaux de groupe d’automorphismes fixé et de taille , 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, 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.
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
Gaborit, Philippe 1; Zémor, Gilles 2
@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}, pages = {1051--1062}, publisher = {Association des Annales de l{\textquoteright}institut Fourier}, volume = {57}, number = {4}, year = {2007}, doi = {10.5802/aif.2286}, mrnumber = {2339326}, zbl = {1172.11021}, language = {en}, url = {https://aif.centre-mersenne.org/articles/10.5802/aif.2286/} }
TY - JOUR AU - Gaborit, Philippe AU - Zémor, Gilles TI - On the construction of dense lattices with a given automorphisms group JO - Annales de l'Institut Fourier PY - 2007 SP - 1051 EP - 1062 VL - 57 IS - 4 PB - Association des Annales de l’institut Fourier UR - https://aif.centre-mersenne.org/articles/10.5802/aif.2286/ DO - 10.5802/aif.2286 LA - en ID - AIF_2007__57_4_1051_0 ER -
%0 Journal Article %A Gaborit, Philippe %A Zémor, Gilles %T On the construction of dense lattices with a given automorphisms group %J Annales de l'Institut Fourier %D 2007 %P 1051-1062 %V 57 %N 4 %I Association des Annales de l’institut Fourier %U https://aif.centre-mersenne.org/articles/10.5802/aif.2286/ %R 10.5802/aif.2286 %G en %F 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, Volume 57 (2007) no. 4, pp. 1051-1062. doi : 10.5802/aif.2286. https://aif.centre-mersenne.org/articles/10.5802/aif.2286/
[1] A new inequality for the Hermite constants, arXiv:math.NT/0603477, 2006
[2] A lower bound for the optimal density of lattice packings, Internat. Math. Res. Notices, Volume 10 (1992), pp. 217-221 | DOI | MR | Zbl
[3] Sphere packings, lattices and groups, 290, Springer-Verlag, New-York (third edition), 1999 | MR | Zbl
[4] Hlawka’s theorem in the geometry of numbers, Duke Math. J., Volume 14 (1947), pp. 367-375 | DOI | Zbl
[5] Asymptotic improvement of the Gilbert-Varshamov bound for linear codes, Inter. Symp. Inf. Theo., ISIT 2006, Seattle (2006), pp. 287-291
[6] Zero-free regions for Dirichlet -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] 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] Existence theorems in the geometry of numbers, Ann. of Math. (2), Volume 48 (1947), pp. 994-1002 | DOI | MR | Zbl
[9] A lower bound on packing density, Invent. Math, Volume 98 (1989) no. 3, pp. 499-509 | DOI | MR | Zbl
[10] An improvement to the Minkowski-Hlawka bound for packing superballs, Mathematika, Volume 34 (1987) no. 1, pp. 8-18 | DOI | MR | Zbl
[11] Random lattices and random sphere packings: typical properties, Mosc. Math. J., Volume 1 (2001) no. 1, pp. 73-89 | MR | Zbl
Cited by Sources: