Lattices with Large Kissing Number from Local Density

Abstract

Let ${\kappa }_p(n)$ denote the maximum kissing number of a lattice $\mathcal{L}\subset {\mathbb{R}}^n$. We prove that ${\kappa }_p(n)\ge 2^{\Omega (\sqrt{n})}$ for all $p\ge 1$ and that ${\kappa }_p(n)\ge \Omega ({\alpha }_p^n)$ for all $p>2$, where ${\alpha }_p>1$ is a constant depending only on $p$. In particular, our former result improves on the previously best known lower bound of ${\kappa }_2(n)\ge 2^{\Theta ({\log }^{2}n)}$ for the ${\ell }_2$ kissing number, which has stood for over $60$ years. (In concurrent and independent work, Laarhoven and Kominers [arXiv, 2026] showed a similar lower bound on ${\kappa }_2(n)$ using similar techniques.) In fact, our lower bounds follow from efficient (randomized) constructions of lattices with large kissing number. Our results use a general construction of lattices with large kissing number. Specifically, we show a simple equivalence between such lattices and a new object that we call an exact locally dense lattice. Closely related objects appear throughout the literature on computational lattice problems. Our constructions of lattices with large kissing number then follow as corollaries by showing that constructions due to Bennett and Peikert [RANDOM, 2023] (using Craig lattices) and Aggarwal and Stephens-Davidowitz [STOC, 2018] (using sparsification of ${\mathbb{Z}}^n$) in fact give exact locally dense lattices, as well as a new construction of exact locally dense lattices built from rotations of the $m$-dimensional checkerboard lattice $D_m$.