On the construction of dense lattices with a given automorphisms group

DOI10.5802/AIF.2286MaRDI QIDQ2372823zbMATH OpenOpenAlexFDO

Authors Philippe Gaborit, Gilles Zémor

Publication date 1 August 2007

Published in Annales de l’institut Fourier (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0605098, http://www.numdam.org/item?id=AIF_2007__57_4_1051_0, http://www.numdam.org/item?id=AIF_2007__57_4_1051_0/, https://eudml.org/doc/10250

zbMATH Keywords

automorphism groupdouble circulant codeslattice packingMinkowski-Hlawka lower boundprobability

Mathematics Subject Classification ID

Lattice packing and covering (number-theoretic aspects) (11H31) Relations with coding theory (11H71) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Linear codes (general theory) (94B05)

Abstract: We consider the problem of constructing dense lattices of R^n with a given automorphism 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 automorphism 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 automorphism group, namely the class of double circulant codes.

Review text

The main result of this article is the construction of a family of lattices for large enough primes \(q\) in dimensions \(n=2q\) with density at least \(c\,n/2^n\), where \(c\) is an absolute constant, and whose automorphism group contains a subgroup isomorphic to \(\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/q \mathbb{Z}\). Up to the constant \(c\), this density is of the same order as the best known density for lattice packings. The complexity of the construction a lattice is of order \(\exp(n \log n)\), which improves the known orders for such a density. The technique used here relies on the Construction A by Leech and Sloane and consists in picking a double circulant code and lifting it to a lattice. Evidence are given that a constant proportion of these codes give rise to lattices that achieve the aforementioned lower bound on the density.

Recommendations

• On the density of cyclotomic lattices constructed from codes
• A FAMILY OF ASYMPTOTICALLY GOOD LATTICES HAVING A LATTICE IN EACH DIMENSION
• New Lattice Packings of Spheres
• Density in families of lattices. Application to isodual lattices
• Laminating lattices with symmetrical glue

Cites work

• A lower bound on packing density
• An improvement to the Minkowski‐Hiawka bound for packing superballs
• Existence theorems in the geometry of numbers
• Hlawka's theorem in the geometry of numbers
• scientific article; zbMATH DE number 179210 (Why is no real title available?)
• scientific article; zbMATH DE number 192896 (Why is no real title available?)
• scientific article; zbMATH DE number 2147309 (Why is no real title available?)
• Random lattices and random sphere packings: Typical properties
• Zero-Free Regions for Dirichlet L-Functions, and the Least Prime in an Arithmetic Progression

Cited in

(10)

• Embedding lattices in \(L^2([0,1], \mathbb Z)\)
• Two matrix-based lattice construction techniques
• On a generalization of Craig lattices
• Permutation invariant lattices
• Dense packings from algebraic number fields and codes
• A Gilbert-Varshamov-type bound for lattice packings
• A NEW INEQUALITY FOR THE HERMITE CONSTANTS
• Local testing of lattices
• On the density of cyclotomic lattices constructed from codes
• A Note on Lattice Packings via Lattice Refinements

This page was built for publication: On the construction of dense lattices with a given automorphisms group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2372823)