A Note on Sphere Packing Bounds for Tuple Lattice Sieving
arXiv:2609.08190v1 [math.CO] 8 Sep 2026
Thijs Laarhoven Corresponding author(s). E-mail(s): [email protected]; 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 Rk 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 ≥ 2 we show: 1 Rk ≤ min κ 1− . 1≤r≤⌊k/2⌋ r 2r 1
(1)
Combining this with standard sphere packing bounds, for large k we obtain an almost-tight asymptotic comparison with the known lower bounds: log2 k
1 − o(1) 2
k
≤ Rk ≤ (1 + o(1))
log2 k k
.
(2)
Keywords: spherical codes, (tuple) lattice sieving, asymptotic bounds, kissing constant MSC Classification: 94B65 , 52C17 , 11H31 , 68W40
1 Introduction Lattice sieving seeks short lattice vectors by repeatedly combining elements of a list. The classical pairwise operation replaces a vector using a shorter sum or difference. For an equal-length list, the absence of such reductions imposes an angular separation: after scaling to unit length, distinct vectors satisfy |⟨xi , xj ⟩| < 1/2 if sums of norm at most one are excluded. The list is therefore a spherical code, and kissing-number upper bounds control its size. This geometric observation is central to the analysis of GaussSieve-type lists [7].
1
Bai, Laarhoven, and Stehlé (BLS) introduced tuple lattice sieving to reduce the memory requirement by permitting combinations of more than two vectors [1]. Their analysis predicted a decreasing list-size exponent, subsequently established for independent random spherical inputs by Herold and Kirshanova (HK) [3]. Subsequent work involved further classical [4] and quantum improvements to tuple lattice sieving [2, 6], illustrating continuing interest in these methods. These algorithmic developments leave a distinct extremal question: how large can a spherical set be if none of its permitted signed combinations is short?
2 Spherical codes All logarithms are to base two unless written as ln. The dimension is n ≥ 2, and k is fixed whenever n → ∞. We write Sn−1 = {x ∈ Rn : ∥x∥ = 1}, with the Euclidean norm. All lists in this note are finite sets; indices in a tuple are distinct. Definition 2.1 (Spherical codes and their rates) For −1 ≤ α < 1, let A(n, α) be the largest cardinality of a set C ⊂ Sn−1 satisfying ⟨x, y⟩ ≤ α for all distinct x, y ∈ C. Its asymptotic rate is 1 κ(α) = lim sup log2 A(n, α). (3) n n→∞
The parameter α p is the maximum inner product. The equivalent minimum Euclidean distance is 2(1 − α). In particular, A(n, 1/2) is the ordinary kissing number in dimension n, and κ(1/2) is its asymptotic exponent. Definition 2.2 (Tuple irreducibility) A set C = {x1 , . . . , xN } ⊂ Sn−1 is irreducible through order k if X
si xi > 1
for all 2 ≤ |I| ≤ k
and all si ∈ {−1, 1}.
(4)
i∈I
Let Nk (n) be the largest size of such a set, and put Rk = lim supn→∞ n−1 log2 Nk (n). For ev k = 2m, define N2m (n) and Rev 2m analogously, but require (4) only for |I| ∈ {2, 4, . . . , 2m}.
The permitted nonzero coefficients are exactly ±1; repetitions and coefficients of larger magnitude are not part of the definition. Zero sums are excluded as well. The condition is cumulative: irreducibility at the largest support size alone is insufficient for our upper-bound argument. We use the strict convention in (4) throughout. For random spherical tuples the boundary has probability zero. In particular,
Nk+1 (n) ≤ Nk (n),
ev N2m (n) ≤ N2m (n) ≤ A(n, 1/2).
(5)
At k = 2 the signed condition is |⟨x, y⟩| < 1/2. Thus R2 ≤ κ(1/2); we do not identify this restricted signed-code rate with the ordinary kissing-number rate. We use the following numerical forms of the classical KL bound and the recent OpenAI bound. The constants are rounded outwards. 2
Lemma 2.3 (Kabatiansky–Levenshtein bound [5]) For 1/2 ≤ α < 1, 1 κ(α) ≤ κ(KL) (α) := − log2 2(1 − α) + 0.400944234. 2
(6)
Lemma 2.4 (OpenAI bound [8]) For 1/2 ≤ α < 1, (OAI)
κ(α) ≤ κ
1 (α) := − log2 2(1 − α) + 2
( 0.396602, 0.395615,
1/2 ≤ α < 3/4, 3/4 ≤ α < 1.
(7)
Moreover, the full hierarchy gives κ(α) ≤ 21 log2 (e/(π(1 − α))) + o(1) as α ↑ 1.
Lemma 2.4 uses Chapter 2, Theorem 1.2 and its spherical-cap form (12), and Theorem 8.3 of [8]. The displayed decimals come from explicit level-two parameters supplied with the numerical code. We finally record the rate lower bound used for comparison. Lemma 2.5 (Rate lower bound from Herold–Kirshanova) For k ≥ 2, with the expansion as k → ∞, log2 k − log2 e 1 log2 k log k (HK) Rk ≥ Lk := . (8) − log2 1 + k1 = +O 2 k−1 2k k2 (HK)
Moreover, Lk
≥ (log2 k − log2 e)/(2k) for every k ≥ 2.
The rate bound is the standard alteration consequence of the configuration estimates in [3, Corollary 1, based on Theorems 1–2], applied to all signed support sizes from two through k . The exponent was predicted in [1, Eq. (3.2)] and established as the random-list exponent in [3, Theorem 3]. The expansion and the last inequality are (HK) elementary consequences of the formula for Lk .
3 The upper bound Theorem 3.1 (Half-tuple packing bound) For every fixed k ≥ 2, 1 1 Rk ≤ min κ 1− . 2r 1≤r≤⌊k/2⌋ r
(9)
The following three lemmas prepare the proof of Theorem 3.1. A common signing yields many short half-tuple sums, irreducibility separates them, and a lifting turns them into a spherical code. Lemma 3.2 (A global signing with many short sums) Let x1 , . . . , xN ∈ Sn−1 P and 1 ≤ r ≤ N . There is a signing s = (s1 , . . . , sN ) ∈ {−1, 1}N such that, writing yA = i∈A si xi , ( ! ) ! [N ] 2 1−r N # A∈ : ∥yA ∥ ≤ r ≥ 2 . (10) r r
3
Proof Choose the entries of s independently and uniformly. For every fixed r-subset A, X X ∥xi ∥2 + E(si sj )⟨xi , xj ⟩ = r. (11) Es ∥yA ∥2 = i∈A
i,j∈A,i̸=j
At least one of the 2r sign patterns on A therefore has squared norm at most r. Its negative has the same norm, so at least two patterns do. Consequently, the probability that ∥yA ∥2 ≤ r is at least 21−r . By linearity of expectation, the expected number of such subsets A is at least 21−r N □ r . Some global signing attains at least this number, proving (10). Lemma 3.3 (Separation of half-tuple sums) Suppose C is even-irreducible through order 2m. For any global signing s and any r ≤ m, the sums yA over distinct r-subsets obey ∥yA − yB ∥ > 1. In particular, all these sums are distinct.
Proof For A ̸= B, cancellation gives yA − yB =
X
si xi −
i∈A\B
X
si xi .
(12)
i∈B\A
Because |A| = |B| = r, the support A△B has size 2(r − |A ∩ B|) ∈ {2, 4, . . . , 2r}. All its coefficients are signs, so even irreducibility proves the claim. This also explains why forbidding only support size 2m would not suffice: overlapping subsets can leave smaller supports. □ Lemma 3.4 (Lifting a ball packing to a sphere) Let Y ⊂ Rn lie in the closed ball of radius ρ > 0 centered at the origin, and suppose distinct points of Y have distance greater than ℓ > 0. If ℓ/ρ ≤ 2, then |Y | ≤ A(n + 1, 1 − ℓ2 /(2ρ2 )).
Proof Map each y ∈ Y to uy = ρ−1 y, map injective, and ∥uy − uz ∥2 =
p ρ2 − ∥y∥2 ∈ Sn . The first n coordinates make the
∥y − z∥2 + (
p p ρ2 − ∥y∥2 − ρ2 − ∥z∥2 )2 ℓ2 > 2. 2 ρ ρ
(13)
Since the images are unit vectors, ⟨uy , uz ⟩ = 1 − ∥uy − uz ∥2 /2 < 1 − ℓ2 /(2ρ2 ). Thus they form the required spherical code. □ Proof of Theorem 3.1 Put m = ⌊k/2⌋. Fix r ≤ m and a set of size N ≥ r that is even distinct, irreducible through order 2m. Lemmas 3.2 and 3.3 produce at least 21−r N r √ √ mutually separated points in a ball of radius r. Lemma 3.4, with ρ = r and ℓ = 1, gives ! 1 1−r N 2 ≤ A n + 1, 1 − . (14) r 2r Minimizing over r proves the cardinality bound for even-irreducible sets. Full irreducibility implies these even conditions, so the bound applies to Nk (n) as well. For each fixed r, the same estimate gives 1 1 log2 N ≤ log2 A n + 1, 1 − + Or (1). (15) r 2r Divide by n, take the upper limit as n → ∞, and use (n + 1)/n → 1. The definition of κ then −1 gives Rev κ(1 − 1/(2r)). Minimizing over r ≤ m proves the rate statements, including 2m ≤ r for odd k, since Rk ≤ Rev □ 2m .
4
r The factor 1/r comes √ from converting roughly N half-tuple sums into a spherical code. Their radius is r, so lifting and scaling give pairwise inner products below 1 − 1/(2r). These are the two geometric features responsible for the large-k behavior. Substituting κ(OAI) from Lemma 2.4 into Theorem 3.1, with r = 1 and r = k/2, gives the following explicit form of our upper bound.
Corollary 3.5 (Explicit upper bound) For even k ≥ 4, log2 k − 0.208770 Rk ≤ Uk := min 0.396602, . k
(16)
The same upper bound holds for Rev k . For k = 2, it reads R2 ≤ U2 := 0.396602. For odd k, the corresponding bounds at k − 1 apply. Remark 3.6 (The cases k = 2 and k = 4) For k = 2, Theorem 3.1 gives R2 ≤ κ(1/2), recovering the pairwise bound. At k = 4, substituting κ(OAI) gives the half-tuple term 0.4478075, which exceeds the pairwise estimate 0.396602. Our explicit upper bound therefore retains the pairwise estimate at k = 4, and first improves on it at k = 6. This does not imply that the true four-tuple rate equals the pairwise rate.
4 Large-k asymptotics We now let k grow after taking the dimension limit defining each rate. The previous estimates are not asserted to hold uniformly when k = k (n) grows with n. Theorem 4.1 (Two-sided asymptotics) As k → ∞ through integers, log2 k + log2 (e/π) + o(1) log2 k − log2 e ≤ Rk ≤ . (17) 2k k ev The same statement holds for Rk through even k. In particular, Rk = Θ((log k)/k) and 1 kRk kRk ≤ lim inf ≤ lim sup ≤ 1. 2 log k→∞ log2 k k→∞ 2k
(18)
Proof The lower bound is contained in Lemma 2.5. For even k, take r = k/2 in Theorem 3.1 and use the small-angle estimate in Lemma 2.4: log2 k + log2 (e/π) + o(1) 2 κ(1 − 1/k) ≤ . (19) k k For odd k, apply the even estimate at k − 1 and use Rk ≤ Rev k−1 . Replacing k − 1 by k costs O((log k)/k2 ) = o(1/k). Dividing by (log2 k)/k proves (18). □ Rev k ≤
The upper and lower bounds in Fig. 1 are asymptotically a factor two apart: (HK) Uk /Lk → 2 as k → ∞ through even integers.
5
(a) Rates
(b) Normalized rates
0.4 Rk
0.3
Rk · (k/ log2 k)
Uk (HK)
Lk
0.2 0.1 0
21
24
27
210
1 0.75 0.5 0.25 0 21
even tuple order k
24
27
210
even tuple order k
(HK) Fig. 1 The lower bound Lk from Lemma 2.5 and our upper bound Uk from (16). Left: the two rate bounds. Right: the same curves divided by (log2 k)/k, with horizontal asymptotes 1/2 and 1.
References [1] Bai, S., Laarhoven, T., Stehlé, D.: Tuple lattice sieving. LMS J. Comput. Math. 19(A), 146–162 (2016). https://doi.org/10.1112/S1461157016000292 [2] Engelberts, L., Chen, Y., Gilani, A.S., van Hoof, M.-I., Jeffery, S., de Wolf, R.: An improved quantum algorithm for 3-tuple lattice sieving. In: CRYPTO 2026. LNCS, vol. 16802, pp. 429–461. Springer (2026). https://doi.org/10.1007/ 978-3-032-35377-1 14 [3] Herold, G., Kirshanova, E.: Improved algorithms for the approximate k -list problem in Euclidean norm. In: PKC 2017. LNCS, vol. 10174, pp. 16–40. Springer (2017). https://doi.org/10.1007/978-3-662-54365-8 2. [4] Herold, G., Kirshanova, E., Laarhoven, T.: Speed-ups and time–memory tradeoffs for tuple lattice sieving. In: PKC 2018. LNCS, vol. 10769, pp. 407–436. Springer (2018). https://doi.org/10.1007/978-3-319-76578-5 14 [5] Kabatiansky, G.A., Levenshtein, V.I.: Bounds for packings on a sphere and in space. Probl. Inf. Transm. 14(1), 1–17 (1978) [6] Kirshanova, E., Mårtensson, E., Postlethwaite, E.W., Moulik, S.R.: Quantum algorithms for the approximate k -list problem and their application to lattice sieving. In: ASIACRYPT 2019. LNCS, vol. 11921, pp. 521–551. Springer (2019). https://doi.org/10.1007/978-3-030-34578-5 19 [7] Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: SODA 2010, pp. 1468–1480. SIAM (2010). https://doi.org/ 10.1137/1.9781611973075.119 [8] OpenAI: Ten advances in mathematics and theoretical computer science, Chapter 2: Binary and spherical codes. Technical manuscript, version of 6 August 2026 (2026). https://cdn.openai.com/pdf/ten-proofs-oai.pdf
6