Source-linked AI summary
A Note on Sphere Packing Bounds for Tuple Lattice Sieving
Thijs Laarhoven
TL;DR
The paper studies how large a set of unit vectors can be when every permitted signed sum of two through k distinct vectors has norm greater than one. It bounds this rate using spherical-code packing and compares the result with a known lower bound.
Problem
Method
Theorem 3.1 converts half-tuple sums into a spherical code and minimizes the resulting packing bound over r.
Source: §3 · pp. 3–5Results
Theorem 3.1 bounds Rk by minimizing (1/r)κ(1−1/(2r)) over 1 ≤ r ≤ floor(k/2); for k = 2, R2 ≤ 0.396602 using the stated explicit bound.
Source: §3 · pp. 4–5Takeaways & Limitations
The bound retains the pairwise estimate at k = 4 and first improves on it at k = 6.
Source: §3 · p. 5At k = 4, the explicit upper bound does not show that the true four-tuple rate equals the pairwise rate.
Source: §3 · p. 5
Abstract
from arXiv · showhide
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 $\kappa(\alpha)$ be the maximal asymptotic rate of spherical codes with pairwise inner products at most $\alpha$. For $k \ge 2$ we show: \begin{align} \mathcal{R}_k \le \min_{1 \le r \le \lfloor k/2 \rfloor} \frac{1}{r} \, \kappa\!\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}
1 Introduction
Classical pairwise sieving links list size to spherical-code bounds, while tuple sieving extends the combinations used and raises a separate extremal question about sets with no short permitted signed sums.
1 Introduction
- Pairwise lattice sieving turns equal-length lists with no short pairwise reductions into spherical codes, whose size is controlled by kissing-number bounds.After scaling to unit length, distinct vectors have absolute inner product below 1/2 when sums of norm at most one are excluded; this observation underlies GaussSieve-type list analysis [7].Source: §1 · p. 1
- Tuple lattice sieving permits combinations of more than two vectors to reduce memory requirements [1].Its decreasing list-size exponent was predicted in [1] and later established for independent random spherical inputs in.Source: §1 · p. 2
- The extremal question is how large a spherical set can be when none of its permitted signed combinations is short.Further classical and quantum improvements to tuple sieving reflect continuing interest in the algorithmic methods.Source: §1 · p. 2
2 Spherical codes
This section sets the spherical-code and tuple-irreducibility definitions, records the pairwise case, and gives the lower-rate benchmark used in later comparisons.
2 Spherical codes
- A spherical code is a subset of the unit sphere whose distinct vectors have inner products at most α, with asymptotic rate defined from its maximal size.Here α is the maximum inner product, and the corresponding minimum Euclidean distance is 2(1−α); at α = 1/2, the code size is the ordinary kissing number and κ(1/2) its asymptotic exponent.Source: §2 · p. 2
- For k = 2m, even-irreducibility requires the signed-sum condition only at support sizes 2, 4, …, 2m, whereas full irreducibility requires every size through k.The rate Rk is defined from the asymptotic exponential growth of the largest k-irreducible set, with k fixed as dimension tends to infinity.Source: §2 · p. 2
- For k = 2, the signed condition gives R2 ≤ κ(1/2), without identifying this restricted signed-code rate with the ordinary kissing-number rate.The section uses the strict condition that every signed sum of between two and k distinct unit vectors has norm greater than one; coefficients are ±1, and zero sums are excluded.Source: §2 · p. 2
- The Herold–Kirshanova lower bound supplies a rate benchmark for comparison, obtained by alteration from configuration estimates over signed support sizes two through k [3].The exponent was predicted in [1] and established as the random-list exponent in [3].Source: §2 · p. 3
3 The upper bound
Theorem 3.1 bounds the rate of k-irreducible sets by minimizing a spherical-code rate bound over r. Its proof turns short, separated half-tuple sums into a spherical code, and the resulting estimate also applies to full irreducibility.
3 The upper bound
- A global signing yields many short r-subset sums, irreducibility separates distinct sums, and lifting them gives a spherical code.The sums lie in a ball of radius √r and are separated by more than 1; lifting gives inner products below 1 − 1/(2r).Source: §3 · pp. 3–4
- Even-irreducibility through order 2m suffices for the packing argument, and full irreducibility implies those even conditions.Overlapping r-subsets can leave supports smaller than 2r, so separation uses irreducibility across the relevant even support sizes.Source: §3 · p. 4
- R_k ≤ min_{1≤r≤⌊k/2⌋} (1/r) κ(1 − 1/(2r)), by Theorem 3.1’s half-tuple packing bound.The bound follows by minimizing over r; the same rate statement applies to odd k.Source: §3 · pp. 3–4
- The factor 1/r counts the conversion of roughly N^r half-tuple sums into a spherical code, whose lifted points have inner products below 1 − 1/(2r).The two geometric features are the number of sums and the radius √r of their containing ball.Source: §3 · p. 5
- At k = 2, the bound recovers the pairwise estimate; at k = 4, the explicit bound retains that estimate and first improves on it at k = 6.The four-tuple upper bound does not imply that the true four-tuple rate equals the pairwise rate.Source: §3 · p. 5
4 Large-k asymptotics
Taking the dimension limit first, the paper compares the large-k lower and upper rate bounds. They are asymptotically a factor of two apart, and the estimates are not asserted uniformly when k grows with dimension.
4 Large-k asymptotics
- The estimates take the dimension limit for each rate before k grows; they are not asserted uniformly when k = k(n) grows with n..Source: §4 · p. 5
- The upper-bound asymptotics use r = k/2 for even k and transfer the estimate from k − 1 for odd k.Replacing k − 1 by k costs O((log k)/k^2) = o(1/k).Source: §4 · p. 5
- The upper and lower bounds are asymptotically a factor of two apart.Figure 1 shows the rate bounds and the same curves divided by (log2 k)/k, with horizontal asymptotes 1/2 and 1.Source: §4 · p. 5, Figure 1 · p. 6