Limits on packing angles of vectors improve understanding of lattice sieving
A Note on Sphere Packing Bounds for Tuple Lattice Sieving
Cryptography and SecurityInformation Theory
Summary
This paper looks at how many special unit vectors you can have so that any combination of them is always longer than a fixed length. The authors find mathematical limits on how densely these vectors can be packed depending on how many you combine at once. They connect these results to sphere packing ideas, which help explain how shapes can fit together without overlapping. Their work narrows down the possible rates at which these vector sets can grow, giving bounds that almost match what was known before. This helps in understanding complex algorithms that use such vectors, like those in lattice sieving.
unit vectorssphere packinglattice sievingasymptotic ratespherical codesinner productsigned sumcombinatorial geometry
Authors
Thijs Laarhoven
Abstract
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}