A ternary construction of lattices

Hao ChenarXiv 2013 · DOI · arXiv

TL;DR

This paper introduces a novel "ternary construction" method that uses ternary codes (codes over the field $\mathbb{F}_3$) to build highly dense and symmetric lattices in $n$-dimensional space. The framework not only provides a unified way to recover famous structures like the Leech and Barnes-Wall lattices but also succeeds in generating entirely new extremal even unimodular lattices in dimensions 32, 40, and 48.

What Problem Does This Paper Address?

The paper tackles a classic challenge in geometry and information theory: the sphere packing problem. Specifically, how can we arrange non-overlapping spheres in $n$-dimensional space to cover the highest possible fraction of that space? While the answer is known for low dimensions (like the hexagonal packing in 2D or the face-centered cubic packing in 3D), the problem becomes exponentially difficult as dimensions increase.

Lattices—discrete, periodic arrangements of points—are the primary tools used to solve this. Finding "extremal" lattices (those that achieve the theoretical upper bound for density and minimum distance between points) is a major goal. Before this paper, many famous lattices were discovered through disparate, specialized constructions. The author seeks a more general, unified algebraic method to produce these "gold standard" lattices and discover new ones that were previously hidden.

Methods

The author proposes a ternary construction of lattices. This is an evolution of the classical "Construction A," which typically uses binary codes (0s and 1s) to build lattices.

The core technique involves:

  1. Starting Lattices: Taking a known lattice $L$ in $\mathbb{Z}^n$ (often the $D_n$ lattice, which consists of vectors with an even sum of coordinates).
  2. Ternary Codes: Utilizing error-correcting codes over the finite field $\mathbb{F}_3$ (elements $\{0, 1, 2\}$ or $\{-1, 0, 1\}$).
  3. The "Three Rows" Approach: Defining a new lattice in a higher-dimensional space (typically $3n$ or $2n$) by imposing conditions on how three sets of vectors relate to each other modulo 3. For example, a key lemma defines a lattice $E$ where vectors $(x, y, z)$ must satisfy $x + y + z = 0$.
  4. Lifting: Mapping the algebraic properties of the ternary code (its length, dimension, and minimum Hamming distance) onto the geometric properties of the lattice (its volume and minimum norm).

Datasets

In the context of pure mathematics and coding theory, "datasets" refer to established libraries of codes and lattices used for comparison:

  • Ternary Golay Code $[12, 6, 6]_3$: A famous perfect code used here to recover the Leech lattice.
  • Ternary Hamming Codes: Used for lower-dimensional constructions.
  • Koch-Venkov List: A known set of 15 extremal even unimodular lattices in dimension 32 used as a benchmark for the author's new 32D constructions.
  • Magma Computational Algebra System: Used to calculate Gram matrices, theta series, and verify the isometry (equivalence) of the newly found lattices against existing ones.

Key Insights and Ideas

  • Unified Framework: The most striking insight is that a single ternary construction can "naturally" recover a vast array of the densest known lattices, including the Coxeter-Todd lattice ($K_{12}$), the Barnes-Wall lattice ($\Lambda_{16}$), and the Leech lattice ($\Lambda_{24}$). This suggests that ternary logic is deeply woven into the geometry of high-dimensional packing.
  • Dimension Jumping: The construction excels at "jumping" between dimensions that are multiples of 8 or 24, which are the "sweet spots" for exceptional mathematical symmetry.
  • Construction of New Extremals: By applying the ternary method to specific self-dual ternary codes, the author found new extremal even unimodular lattices in dimension 32. These are distinct from the 15 previously known Koch-Venkov lattices, expanding the known "map" of 32D space.
  • Sub-optimal Lattices: The method is flexible enough to generate "sub-optimal" lattices in lower dimensions ($n < 24$) that are still highly efficient for applications like signal processing or cryptography.

Key Results

  • Leech Lattice Recovery: Successfully reconstructed the 24-dimensional Leech lattice ($\Lambda_{24}$) with a center density of 1, confirming the method's power.
  • Dimension 32: Constructed four extremal even unimodular lattices. The author concludes that at least one of these (the "2nd" and "3rd" constructions) represents a newly discovered lattice not present in the standard 32D lists.
  • Dimension 40: Produced at least four new 40-dimensional extremal even unimodular lattices.
  • Dimension 48: Demonstrated a method to build 48-dimensional extremal lattices with a minimum norm of 6, which is a significant threshold for density in that dimension.

Limitations and Future Work

  • Isometry Testing: Proving that a lattice is truly "new" (not just a rotated version of an old one) is computationally expensive. For the 32D and 48D lattices, the author notes that Magma's isometry tests sometimes timed out after several hours, leaving the exact relationship between some new constructions and old ones as an open question.
  • Higher Dimensions: While the paper touches on dimension 72 (a major "holy grail" in lattice theory), it does not provide a definitive new construction there, suggesting this as a frontier for the ternary method.
  • Classification: The paper provides specific examples but does not yet offer a complete classification of all lattices that can be generated via this ternary approach.

Summary updated

Abstract

In this paper we propose a general ternary construction of lattices from three rows and ternary codes. Most laminated lattices and Kappa lattices in ${\bf R}^n$, $n\leq 24$ can be recovered from our tenary construction naturally. This ternary construction of lattices can be used to generate many new "sub-optimal" lattices of low dimensions.Based on this ternary construction new extremal even lattices of dimensions $32, 40$ and $48$ are also constructed.
BibTeX
@misc{chen2013ternary,
  author = {Hao Chen},
  title = {{A ternary construction of lattices}},
  year = {2013},
  eprint = {1306.1432},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1306.1432},
}

Loading related content...

Figure