CS Paper Radar

A lattice family with kissing numbers $τ(\mathcal{L}_n) \ge e^{2 \sqrt{n}}$

Thijs Laarhoven, Scott Duke Kominers

cs.IT math.COmath.MGmath.NT ·submitted 2026-09-11 23:45 UTC · v2

Abstract

For all prime powers $q\geq5$, we construct lattices $\mathcal{L}_q\subseteq\mathbb{Z}^q$ with kissing numbers \[ τ(\mathcal{L}_q)\geq \left(\frac{1}{2πe^2}+o(1)\right)\sqrt{q}\,e^{2\sqrt{q}}. \] The same asymptotic bound holds on a set of integer dimensions of natural density $1$, and in every sufficiently large integer dimension $n$ with an additional factor $e^{-\tfrac{1}{2}n^{1/40}}$. The construction is an extension of a previous construction by Bennett-Peikert based on Reed-Solomon codes.

Comment
v1 contained a construction with $τ(\mathcal{L}_n) \ge e^{\sqrt{n}}$; v2 improves the constant in the exponent by a factor $2$

Closest papers

Nearest neighbours by meaning across the whole index.

Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices

cs.CR math.COmath.MG ·2026-10-11 ·Thijs Laarhoven
theory similarity 0.66
Abstract · 27 pages, 4 figures, 2 tables

To bridge the gap between worst-case and heuristic analyses of lattice enumeration, we study the sizes of (unpruned) enumeration trees on $n$-dimensional Haar-random lattices. Writing $n^{cn+o(n)}$ for the tree size at the shortest vector radius, we investigate the asymptotic scaling of $c$, and which bases minimize it. For quasi-HKZ bases, we rigorously analyze the random-lattice HKZ geometry and establish $c=1/(2e)\approx 0.1839$. This matches the worst-case enumeration exponent of Hanrot-Stehlé and confirms earlier predictions for the geometry of HKZ bases on random lattices. Searching beyond quasi-HKZ bases, we prove that with high probability, the minimum achievable tree size exponent $c$ over all bases of a random lattice satisfies: \begin{align} 0.1464 \approx \frac{2-\sqrt{2}}{4}\leq c<0.1474. \end{align} For the lower bound, we use Kim's mean-value formula for nested chains of primitive sublattices to rule out bases with small prefix determinants. This strengthens the earlier Rankin-based heuristic lower bound exponent $c \geq 1/8$, discussed by Nguyen and Hanrot-Stehlé, and rules out the existence of random-lattice bases with trees as small as predicted by the geometric series assumption. For the upper bound, we show that with high probability a dense primitive half-rank sublattice exists with determinant at most $n^{n/8 + o(n)}$. Combining dual HKZ on this sublattice with HKZ on its quotient gives a basis with $c \leq 1/(4\sqrt{e}) \approx 0.1516$. Recursively splitting each half lowers the upper bound below $0.1474$, and under a natural heuristic assumption we prove that the lower bound is tight. Combined with the collision search of Feng-Gao-Liu, our two-block construction gives a polynomial-space algorithm solving the closest vector problem with preprocessing (CVPP) on random lattices in query time $n^{0.0892 n + o(n)}$ for arbitrary targets.

0.52

A Note on Sphere Packing Bounds for Tuple Lattice Sieving

cs.CR math.COcs.ITmath.MG ·2026-09-08 ·Thijs Laarhoven
similarity 0.63
Abstract · 6 pages, 1 figure

A finite set of unit vectors is $k$-irreducible if every signed sum of between two and $k$ distinct elements has norm greater than one. Let $\mathcal{R}_k$ be the maximal asymptotic rate of such sets, and let $κ(α)$ be the maximal asymptotic rate of spherical codes with pairwise inner products at most $α$. For $k \ge 2$ we show: \begin{align} \mathcal{R}_k \le \min_{1 \le r \le \lfloor k/2 \rfloor} \frac{1}{r} \, κ\!\left(1 - \frac{1}{2r}\right) \, . \end{align} Combining this with standard sphere packing bounds, for large $k$ we obtain an almost-tight asymptotic comparison with the known lower bounds: \begin{align} \left(\tfrac{1}{2}-o(1)\right) \, \frac{\log_2 k}{k} \le \mathcal{R}_k \le (1 + o(1)) \, \frac{\log_2 k}{k} \, . \end{align}

0.24

The Golomb--Welch conjecture for lattice tilings

cs.IT ·2026-10-25 ·Bocong Chen, Jing Huang, Gaojun Luo
theory similarity 0.59
Abstract

We prove the Golomb--Welch conjecture for lattice tilings: for every $n\ge3$ and $r\ge2$, the integer lattice $\Z^n$ admits no lattice tiling by Lee balls $B_n(r)$ of radius $r$. Together with the classical constructions for $n\le2$ and for $r=1$, this determines all parameters for which a lattice Lee tiling exists. Equivalently, we show that every abelian Cayley graph of even degree $2n\ge6$ and diameter $r\ge2$ has strictly fewer than $|B_n(r)|$ vertices.

0.25

Gaussian mass inequalities for lattices

cs.IT math.NT ·2026-11-15 ·Minjia Shi, Xinguang Dai, Patrick Solé
similarity 0.59
Abstract · 50 pages

The Gaussian mass of a lattice is the evaluation of its theta series at a real nome and is relevant to lattice coding for the wiretap Gaussian channel. The ratio of the Gaussian mass of stable lattices to the Gaussian mass of the integer lattice was conjectured to be $\le 1$ (Regev et al., 2024). Kominers proved this bound recently for lattices obtained by Construction~A from binary self-dual codes. Building on Kominers' bound, we establish corresponding inequalities on average for Construction~$A_4$ lattices obtained from free self-dual quaternary codes and for Construction~$A_6$ lattices obtained from self-dual senary codes. We also prove the strict Gaussian-mass inequality for extremal unimodular lattices of both Type~II and Type~I. The Type~I result uses the Rains--Sloane definition of extremality. Its proof combines a universal theta truncation with an exact inversion of the shadow coefficients, and a Gaussian inequality for translated lattices. In addition, we obtain an averaging bound over the genus of Type~II lattices, and extend the binary Construction~A inequality to Siegel theta series of arbitrary genus, with further quaternary results under conditions on the residue code.

0.39

On the generation of multiplicative groups by small primes

cs.DS math.NTmath.GR ·2026-09-21 ·Oleksiy Klurman, Igor E. Shparlinski, Joni Teräväinen
theory similarity 0.58
Abstract

Motivated by a question of Regev arising from his improved quantum factoring algorithm, we study how many small primes are needed to generate the group $({\mathbb Z}/q{\mathbb Z})^\times$ when each prime may be used with exponent only $0$ or $1$. We prove that, for every fixed $\varepsilon>0$ and $A>0$, there is an absolute constant $C_*$ and a set of at most $(\log Q)^{1+\varepsilon}$ primes, all at most $(\log Q)^{C_*(A+1)}$, such that for all but $O(Q(\log Q)^{-A})$ (with the implied constant depending only on $\varepsilon$ and $A$) integers $q\leq Q$, every element of $({\mathbb Z}/q{\mathbb Z})^\times$ is a product of a subset of these primes modulo $q$. The exponent $1+\varepsilon$ in the number of primes is best possible up to the arbitrary $\varepsilon$ in the exponent.

0.44

On the Kissing Number of Craig's Lattice and Spherical List Decoding

cs.IT ·2026-11-17 ·Léo Ducas, Julian Nowakowski, Ailsa Robertson
theory similarity 0.57
Abstract

Craig's lattices $A_{p-1}^k$ are a family of lattices with large kissing numbers, i.e., relative to their dimension $n = p-1$, they contain a large number of shortest nonzero vectors. Specifically, for small $k = o(\log p / \log \log p)$, a lower bound of Bacher (2015) shows that $A_{p-1}^k$ has a super-polynomial kissing number of $ω(n^k)$. Craig's lattices are therefore attractive candidates for the construction of spherical codes. In this work, we introduce a polynomial-time list decoder for spherical codes obtained from Craig's lattices for angular distance below $45^\circ$. Our second main result shows that Bacher's lower bound is asymptotically tight for $k = o(\log p / \log \log p)$. Finally, we introduce an efficient algorithm for computing the kissing number of $A_{p-1}^k$. Using this algorithm, we compute their kissing number in dimensions up to 521. Based on this data, we pose the open question whether the kissing number of $A_{p-1}^k$ with $k \approx \sqrt{p}$ grows like $e^{Θ(\sqrt{n})}$ in dimension $n=p-1$. Concurrent work by Laarhoven and Kominers as well as Bennett, Hhan, Li and Stephens-Davidowitz proves such a bound for very closely related lattices.

0.15

Communication Complexity of Integer Matrix Singularity

cs.CC quant-ph ·2026-10-24 ·Chengu Wang
theory similarity 0.57
Abstract

Alice and Bob hold complementary halves of the columns of an $n\times n$ matrix of $k$-bit integers and decide whether it is singular over $\mathbb Q$. Up to constant-factor dimension growth, this partitioned problem is equivalent to additive singularity, where Alice and Bob hold $n\times n$ matrices $A,B$ of $k$-bit integers and test the singularity of $A+B$ over $\mathbb Q$. We prove a bounded-error quantum lower bound $Ω(\min\{n^{3/2}\sqrt{k\log n},n^2\log(nk)\})$ and a randomized upper bound $O(n^2\min\{k,\log(k+\log n)\})$. The bounds match at $Θ(n^2\log(nk))$ for $k\ge n\log n$. The lower bound holds even under the promise of rank $n-1$ versus $n$. Its proof combines an integer witness with a local digit encoding, while the upper-bound protocol lifts modular kernel relations using short messages. Bitwise sharing changes how the communication complexity depends on the entry bit length $k$. If Alice and Bob instead hold $n\times n$ matrices $A,B$ of $k$-bit integers and test whether their entrywise bitwise XOR $A\oplus B$ is singular over $\mathbb Q$, we prove a quantum lower bound $Ω(n^2k)$, matching the trivial upper bound. This lower bound holds even under the promise of rank $n-1$ versus $n$. Our proof uses a dense weighted equation and a signed Fourier witness whose exceptional dyadic frequencies can be removed at small variation cost.

0.12

New lower bounds for kissing numbers in dimensions 32-35 and 37-39

cs.DM math.MGcs.ITmath.CO ·2026-10-22 ·Qihong Lin
code/data similarity 0.56
Abstract · 8 pages. Certificates and verification programs: https://github.com/QH-Lin/kissing-number-32 (doi:10.5281/zenodo.23527725) and https://githu…

We show that the kissing numbers in dimensions 32, 33, 34, 35, 37, 38 and 39 are at least 352320, 370240, 390980, 415308, 499816, 605322 and 768916, improving the previous bounds 347584, 364736, 384836, 409676, 498024, 591900 and 763668. Except in dimension 38, the configurations are those of Edel, Rains and Sloane with new binary constant-weight codes of weight 8 and minimum distance 8 in the middle layer; each additional word adds 128 points. In dimension 38 we add 6855 antipodal pairs of vectors of the second shell of the Leech lattice to the empty equator of Kravatskiy's 591612-point configuration, where 144 pairs were known; this is an independent set problem in a regular graph of degree 11178 on 8386560 vertices. The codes and lines were found by local search, and all configurations were checked pair by pair in exact integer arithmetic.

0.40