New lattices achieve extremely high kissing numbers in prime dimensions
A lattice family with kissing constant $τ(\mathcal{L}_n) \ge e^{\sqrt{n}}$
Information Theory
Summary
The paper finds a way to create special grids of points in spaces whose dimension is a prime number greater or equal to five. These grids have a surprisingly large number of spheres that can touch a central sphere without overlapping, much more than previous known constructions. The authors improve on earlier methods by extending a construction that used ideas from error-correcting codes. This means they found denser ways to pack spheres in high-dimensional spaces for certain dimensions.
What this means in practice
- •For cryptography engineers: Construct lattices with very large kissing numbers to explore new hardness assumptions in lattice-based cryptographic schemes.
- •For error-correcting code developers: Use connections between lattices and Reed-Solomon codes to design coding methods with improved geometric properties for communication systems.
A theory result. No direct application yet.
Authors
Thijs Laarhoven
Abstract
For prime dimensions $n \ge 5$, we define integer lattices $\mathcal{L}_n$ with kissing constant \begin{align} τ(\mathcal{L}_n) \ge \left(\frac{1}{\sqrt{2 πe}} + o(1)\right) n^{3/4} e^{\sqrt n}. \notag \end{align} This improves on the growth rate $e^{Θ((\log n)^2)}$ of the Barnes-Wall lattices, which provided the previously best known asymptotic lower bound. The construction is an extension of a previous construction by Bennett-Peikert based on Reed-Solomon codes.