no. 4
On the construction of dense lattices with a given automorphisms group
[Construction de réseaux denses avec un groupe d’automorphismes donné]
Gaborit, Philippe1 ; Zémor, Gilles2
1 Université de Limoges, XLIM 123 av. A. Thomas, 87000 Limoges (France)
2 Université Bordeaux I 351 av. de la Libération 33405 Talence (France)
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 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.

DOI : 10.5802/aif.2286
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

Gaborit, Philippe 1 ; Zémor, Gilles 2

1 Université de Limoges, XLIM 123 av. A. Thomas, 87000 Limoges (France)
2 Université Bordeaux I 351 av. de la Libération 33405 Talence (France) 
@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, Tome 57 (2007) no. 4, pp. 1051-1062. doi : 10.5802/aif.2286. https://aif.centre-mersenne.org/articles/10.5802/aif.2286/

[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

Cité par Sources :