OctoInformBeta

OpenAI preprint, September 2026 · §3. Packing signed intervals

Lemma 3.1: If 2∑iwi<12\sum_i w_i<1, points θ1,…,θH∈𝕋m\theta_1,\dots,\theta_H\in\mathbb{T}^m make the arcs I(σai⋅θh,wi/H)I(\sigma a_i\cdot\theta_h,w_i/H) pairwise disjoint, with a version modulo a prime

Nonparallel integer frequencies admit disjoint signed arcs.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Write 𝕋=ℝ/ℤ\mathbb{T} = \mathbb{R}/\mathbb{Z} for the circle and e(x)=exp⁡(2πix)e(x) = \exp(2\pi i x). For a finite set JJ, the torus 𝕋J\mathbb{T}^J is the product of copies of the circle 𝕋\mathbb{T} indexed by JJ; for an integer vector aa with entries indexed by JJ, the character θ↦e(a⋅θ)\theta \mapsto e(a\cdot\theta) of 𝕋J\mathbb{T}^J has at the point θ\theta the phase a⋅θ=∑j∈Jajθja\cdot\theta = \sum_{j \in J} a_j\theta_j, a point of the circle 𝕋\mathbb{T}; for a positive integer mm and J={1,…,m}J = \{1, \dots, m\} the torus is 𝕋m\mathbb{T}^m. Take nonzero frequencies a1,…,ar∈ℤma_1, \dots, a_r \in \mathbb{Z}^m, no two of them parallel, widths w1,…,wr>0w_1, \dots, w_r > 0, a positive integer HH and points θ1,…,θH\theta_1, \dots, \theta_H of the torus 𝕋m\mathbb{T}^m. At each signed phase σai⋅θh\sigma\, a_i\cdot\theta_h, the phase itself for σ=1\sigma = 1 and its negative for σ=−1\sigma = -1, center a closed arc of length wi/Hw_i/H. The 2rH2rH arcs have total length 2∑iwi2\sum_i w_i, whatever HH is. The question is whether, as soon as 2∑iwi<12\sum_i w_i < 1, some HH and some points θh\theta_h make the arcs pairwise disjoint.

The library states this packing for r≥2r \ge 2 frequencies in ℤm\mathbb{Z}^m, for frequencies indexed by finite sets, and for any nonempty finite family of them, a single frequency included. It states with it a version modulo a prime qq, in which the slots defined below take the place of the arcs and points of (ℤ/qℤ)m(\mathbb{Z}/q\mathbb{Z})^m take the place of the points θh\theta_h.

Arcs and Slots

For a point c∈𝕋c \in \mathbb{T} and a real number ℓ\ell, the closed interval I(c,ℓ)I(c, \ell) of the circle with center cc and length ℓ\ell is the set I(c,ℓ)={c+xmod⁡1:x∈ℝ,|x|≤ℓ/2}.I(c, \ell) = \{c + x \bmod 1 : x \in \mathbb{R},\ |x| \le \ell/2\}.(1)✦ The arcs of the question are the intervals I(σai⋅θh,wi/H)I(\sigma\, a_i\cdot\theta_h, w_i/H).

Fix nonnegative integers d1,…,drd_1, \dots, d_r, one for each frequency aia_i; the index i=1,…,ri = 1, \dots, r is the row of the frequency aia_i, and the slots are indexed by rows. The odd lengths of dd are Li=2di+1L_i = 2d_i + 1✦; its period length is their sum P=L1+…+LrP = L_1 + \dots + L_r✦, and the prefix sum of row ii is L<i=L1+…+Li−1L_{<i} = L_1 + \dots + L_{i-1}✦.

Let ii be a row and RR, kk, pp, ss nonnegative integers, where a chunk consists of RR consecutive periods, each of length PP. The slot of row ii in period pp of chunk kk under the shift ss is the block of LiL_i consecutive integers with left site bk,p,i(s)b_{k,p,i}(s) and center nk,p,i(s)n_{k,p,i}(s), the integers given by bk,p,i(s)=kRP+pP+s+L<i,nk,p,i(s)=bk,p,i(s)+di+1.b_{k,p,i}(s) = kRP + pP + s + L_{<i}, \qquad n_{k,p,i}(s) = b_{k,p,i}(s) + d_i + 1.(2)

A slot choice for KK chunks is a sequence ω=((sk,σk))0≤k≤K−1\omega = ((s_k, \sigma_k))_{0 \le k \le K-1} that gives each chunk kk a shift sk∈{0,…,P−1}s_k \in \{0, \dots, P - 1\} and a sign σk∈{−1,1}\sigma_k \in \{-1, 1\}.✦

Fix a modulus qq, integers RR and KK, and a slot choice ω\omega for KK chunks. The set 𝒮i(ω)\mathcal{S}_i(\omega) of residues that hit the slots of row ii consists of the signed sites σknmod⁡q\sigma_k n \bmod q of the centers n=nk,p,i(sk)n = n_{k,p,i}(s_k) in the first R−1R - 1 periods of each chunk: 𝒮i(ω)={σknk,p,i(sk)mod⁡q:0≤k≤K−1,0≤p≤R−2}⊂ℤ/qℤ.\mathcal{S}_i(\omega) = \{\sigma_k\, n_{k,p,i}(s_k) \bmod q : 0 \le k \le K - 1,\ 0 \le p \le R - 2\} \subset \mathbb{Z}/q\mathbb{Z}.(3)✦

For a∈ℤma \in \mathbb{Z}^m and y∈(ℤ/qℤ)my \in (\mathbb{Z}/q\mathbb{Z})^m, the product a⋅y=a1y1+…+amyma\cdot y = a_1y_1 + \dots + a_my_m is the element of ℤ/qℤ\mathbb{Z}/q\mathbb{Z} computed with the entries of aa reduced mod qq.

The Claim

Theorem 1. (a) Let r≥2r \ge 2, let a1,…,ar∈ℤma_1, \dots, a_r \in \mathbb{Z}^m be nonzero vectors, none of them a rational multiple of another, and let w1,…,wr>0w_1, \dots, w_r > 0 with 2∑iwi<12\sum_i w_i < 1. Then there are an integer H≥1H \ge 1 and points θ1,…,θH∈𝕋m\theta_1, \dots, \theta_H \in \mathbb{T}^m such that the 2rH2rH closed intervals I(σai⋅θh,wi/H),σ∈{−1,1},1≤i≤r,1≤h≤H,I(\sigma\, a_i\cdot\theta_h,\, w_i/H), \qquad \sigma \in \{-1, 1\},\ 1 \le i \le r,\ 1 \le h \le H,(4)✦ are pairwise disjoint.

(b) Let II and JJ be finite sets, II with at least two elements, let ai∈ℤJa_i \in \mathbb{Z}^J, for i∈Ii \in I, be nonzero vectors, none of them a real multiple of another, and let wi>0w_i > 0, for i∈Ii \in I, with 2∑i∈Iwi<12\sum_{i \in I} w_i < 1. Then there are an integer H≥1H \ge 1 and points θ1,…,θH∈𝕋J\theta_1, \dots, \theta_H \in \mathbb{T}^J such that the 2|I|H2|I|H closed intervals I(σai⋅θh,wi/H),σ∈{−1,1},i∈I,1≤h≤H,I(\sigma\, a_i\cdot\theta_h,\, w_i/H), \qquad \sigma \in \{-1, 1\},\ i \in I,\ 1 \le h \le H,(5)✦ are pairwise disjoint.

(c) Let II and JJ be finite sets, II nonempty, and let aia_i and wiw_i, for i∈Ii \in I, be as in (b). Then there are an integer H≥1H \ge 1 and points θ1,…,θH∈𝕋J\theta_1, \dots, \theta_H \in \mathbb{T}^J such that the 2|I|H2|I|H closed intervals I(σai⋅θh,wi/H),σ∈{−1,1},i∈I,1≤h≤H,I(\sigma\, a_i\cdot\theta_h,\, w_i/H), \qquad \sigma \in \{-1, 1\},\ i \in I,\ 1 \le h \le H,(6)✦ are pairwise disjoint.

(d) Let r≥2r \ge 2, let a1,…,ar∈ℤma_1, \dots, a_r \in \mathbb{Z}^m be nonzero vectors, none of them a rational multiple of another, let d1,…,drd_1, \dots, d_r be nonnegative integers with period length PP, and let 0<τ<1/(2P)0 < \tau < 1/(2P). Then there are a prime qq, integers R≥3R \ge 3 and K≥1K \ge 1 with 2KRP<q2KRP < q, a slot choice ω\omega for KK chunks and a set MM of more than τq\tau q points of (ℤ/qℤ)m(\mathbb{Z}/q\mathbb{Z})^m such that, for every row ii, ai⋅y∈𝒮i(ω)(y∈M),ai⋅y≠ai⋅y′(y≠y′ in M).a_i\cdot y \in \mathcal{S}_i(\omega) \quad (y \in M), \qquad a_i\cdot y \ne a_i\cdot y' \quad (y \ne y' \text{ in } M).(7)✦

In the paper, the result reads: for m≥1m \ge 1, r≥2r \ge 2 and pairwise nonparallel a1,…,ar∈ℤm\{0}a_1, \dots, a_r \in \mathbb{Z}^m \setminus \{0\}, and widths w1,…,wr>0w_1, \dots, w_r > 0 with 2∑iwi<12\sum_i w_i < 1, there are H≥1H \ge 1 and θ1,…,θH∈𝕋m\theta_1, \dots, \theta_H \in \mathbb{T}^m such that the 2rH2rH closed intervals I(σai⋅θh,wi/H)I(\sigma\, a_i\cdot\theta_h, w_i/H), 1≤i≤r1 \le i \le r, 1≤h≤H1 \le h \le H, σ∈{−1,1}\sigma \in \{-1, 1\}, are pairwise disjoint.

What Is Checked

The packing statements (4), (5) and (6) are stated over the closed intervals (1) of the circle, centered at signed phases, and the statement (7) over the sets (3) of residues that hit the slots, built from a slot choice and the slot centers (2) of the odd lengths 2di+12d_i + 1.