On the construction of dense lattices with a given automorphisms group

Philippe Gaborit[1]; Gilles Zémor[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)

Annales de l’institut Fourier (2007)

  • Volume: 57, Issue: 4, page 1051-1062
  • ISSN: 0373-0956

Abstract

top
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 c n 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 ( n log n ) , 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.

How to cite

top

Gaborit, Philippe, and Zémor, Gilles. "On the construction of dense lattices with a given automorphisms group." Annales de l’institut Fourier 57.4 (2007): 1051-1062. <http://eudml.org/doc/10250>.

@article{Gaborit2007,
abstract = {We consider the problem of constructing dense lattices in $\mathbb\{R\} ^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$(n \log n)$, 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.},
affiliation = {Université de Limoges, XLIM 123 av. A. Thomas, 87000 Limoges (France); Université Bordeaux I 351 av. de la Libération 33405 Talence (France)},
author = {Gaborit, Philippe, Zémor, Gilles},
journal = {Annales de l’institut Fourier},
keywords = {Lattice packings; Minkowski-Hlawka lower bound; probability; automorphism group; double circulant codes; lattice packing},
language = {eng},
number = {4},
pages = {1051-1062},
publisher = {Association des Annales de l’institut Fourier},
title = {On the construction of dense lattices with a given automorphisms group},
url = {http://eudml.org/doc/10250},
volume = {57},
year = {2007},
}

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
PB - Association des Annales de l’institut Fourier
VL - 57
IS - 4
SP - 1051
EP - 1062
AB - We consider the problem of constructing dense lattices in $\mathbb{R} ^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$(n \log n)$, 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.
LA - eng
KW - Lattice packings; Minkowski-Hlawka lower bound; probability; automorphism group; double circulant codes; lattice packing
UR - http://eudml.org/doc/10250
ER -

References

top
  1. R. Bacher, A new inequality for the Hermite constants, arXiv:math.NT/0603477 (2006) Zbl1165.11056
  2. K. Ball, A lower bound for the optimal density of lattice packings, Internat. Math. Res. Notices 10 (1992), 217-221 Zbl0776.52006MR1191572
  3. J. Conway, N. J. A. Sloane, Sphere packings, lattices and groups, 290 (1999), Springer-Verlag, New-York (third edition) Zbl0634.52002MR1662447
  4. H. Davenport, C. A. Rogers, Hlawka’s theorem in the geometry of numbers, Duke Math. J. 14 (1947), 367-375 Zbl0030.34602
  5. P. Gaborit, G. Zémor, Asymptotic improvement of the Gilbert-Varshamov bound for linear codes, Inter. Symp. Inf. Theo., ISIT 2006, Seattle (2006), 287-291 Zbl1318.94120
  6. D. R. Heath-Brown, Zero-free regions for Dirichlet L -functions and the least prime in an arithmetic progression, Proc. London Math. Soc. (3) 64 (1992), 265-338 Zbl0739.11033MR1143227
  7. Michael Krivelevich, Simon Litsyn, Alexander Vardy, A lower bound on the density of sphere packings via graph theory, Int. Math. Res. Not. (2004), 2271-2279 Zbl1071.52018MR2076096
  8. C. A. Rogers, Existence theorems in the geometry of numbers, Ann. of Math. (2) 48 (1947), 994-1002 Zbl0036.02701MR22863
  9. J. A. Rush, A lower bound on packing density, Invent. Math 98 (1989), 499-509 Zbl0659.10033MR1022304
  10. J. A. Rush, N. J. A. Sloane, An improvement to the Minkowski-Hlawka bound for packing superballs, Mathematika 34 (1987), 8-18 Zbl0606.10028MR908835
  11. S. Shlosman, M. Tsfasman, Random lattices and random sphere packings: typical properties, Mosc. Math. J. 1 (2001), 73-89 Zbl0999.11032MR1852935

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.