OctoInformBeta

OpenAI preprint, September 2026 · §5. Coverage from shared continuation data

Signed coordinates and (τ, β) coverage: A signed index picks πp\pi_p or π‾p\bar\pi_p, and the low residues of a law on GG are the elements of probability below τ/|G|\tau/|G|

Residues modulo signed factors and low residues of laws.

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

A rational prime p≡1(mod⁡4)p \equiv 1 \pmod 4 splits in ℤ[i]\mathbb{Z}[i] into two conjugate Gaussian primes, p=ππ‾p = \pi\bar\pi, and modulo either factor the residue classes of ℤ[i]\mathbb{Z}[i] form a group of pp elements. For a finite set of such primes, a sign for each prime picks one of its two factors, and a random Gaussian integer ZZ has a residue modulo each factor picked. The question is how evenly the law of such a residue spreads over its pp classes, and in particular how many classes it leaves with much less than the fair share 1/p1/p.

Split Prime Sieves

A split prime sieve ss is a finite set 𝒫\mathcal{P} of rational primes p≡1(mod⁡4)p \equiv 1 \pmod 4 together with a choice, for each p∈𝒫p \in \mathcal{P}, of a Gaussian prime πp\pi_p of norm pp.✦ The enumeration of ss is a fixed bijection k↦pkk \mapsto p_k from {0,…,n−1}\{0, \dots, n-1\} onto 𝒫\mathcal{P}, where n=|𝒫|n = |\mathcal{P}|.✦

For a Gaussian integer π\pi and a sign ϵ∈{+,−}\epsilon \in \{+, -\}, the signed factor π(ϵ)\pi^{(\epsilon)} is the Gaussian integer given by π(+)=π,π(−)=π‾.\pi^{(+)} = \pi, \qquad \pi^{(-)} = \bar\pi.(1)✦

Residue Classes

For a Gaussian integer π\pi, the multiples of π\pi, the products πw\pi w with w∈ℤ[i]w \in \mathbb{Z}[i], form the subgroup (π)(\pi) of ℤ[i]\mathbb{Z}[i].✦

For Gaussian integers π\pi and zz, the residue class of zz modulo π\pi is the element of the quotient group ℤ[i]/(π)\mathbb{Z}[i]/(\pi) given by zmod⁡π=z+(π)={z+πw:w∈ℤ[i]}.z \bmod \pi = z + (\pi) = \{z + \pi w : w \in \mathbb{Z}[i]\}.(2)✦

Finite Probability Laws

A finite probability law μ\mu on a finite set GG is a function μ:G→ℝ\mu \colon G \to \mathbb{R} with μ(x)≥0\mu(x) \ge 0 for every x∈Gx \in G and ∑x∈Gμ(x)=1\sum_{x \in G} \mu(x) = 1.✦

The Definition

Definition 1. Let ss be a split prime sieve with primes p0,…,pn−1p_0, \dots, p_{n-1}, listed by its enumeration. A signed index of ss is a pair c=(σ,k)c = (\sigma, k) of a sign pattern σ=(σ0,…,σn−1)\sigma = (\sigma_0, \dots, \sigma_{n-1}), one sign for each position, and a position kk; the signed indices of ss form the set Is={+,−}n×{0,…,n−1}.I_s = \{+, -\}^{n} \times \{0, \dots, n-1\}.(3)✦ The prime of cc is pc=pkp_c = p_k✦, and its factor is the signed factor πc=πpk(σk)\pi_c = \pi_{p_k}^{(\sigma_k)}✦. The residue group at cc is the group of residue classes modulo πc\pi_c, Rc=ℤ[i]/(πc),R_c = \mathbb{Z}[i]/(\pi_c),(4)✦ and the residue map at cc sends each Gaussian integer to its class (2) modulo πc\pi_c: rc:ℤ[i]→Rc,rc(z)=zmod⁡πc.r_c \colon \mathbb{Z}[i] \to R_c, \qquad r_c(z) = z \bmod \pi_c.(5)✦ For a finite probability law μ\mu on a finite set GG and a real number τ\tau, the set of low residues of μ\mu is Lτ(μ)={x∈G:μ(x)<τ/|G|}.L_\tau(\mu) = \{x \in G : \mu(x) < \tau/|G|\}.(6)✦

In the paper, the result reads: a signed coordinate c=(j,σ)c = (j, \sigma) comes with a homomorphism φc\varphi_c from a lattice Λ\Lambda to a finite abelian group of order pjp_j, and a random variable XX on an alphabet of size pp has (τ,β)(\tau, \beta) coverage when #{x:Pr⁡(X=x)<τ/p}<p1−β\#\{x : \Pr(X = x) < \tau/p\} < p^{1-\beta}.

For a finite probability law μ\mu on a finite set GG, a real number τ\tau and a threshold uu, the law μ\mu has coverage at threshold uu when its set Lτ(μ)L_\tau(\mu) (6) of low residues has fewer than uu elements; the library counts the low residues against uu in place of p1−βp^{1-\beta}.

What Is Checked

The definition is stated over a split prime sieve, with its primes p≡1(mod⁡4)p \equiv 1 \pmod 4, its Gaussian primes πp\pi_p of norm pp and its enumeration; over the signed factors (1), the multiples (π)(\pi) of a Gaussian integer and the residue classes (2); and over finite probability laws on a finite set.

The library also establishes that taking coordinates z↦(Re⁡z,Im⁡z)z \mapsto (\operatorname{Re} z, \operatorname{Im} z) in the basis 1,i1, i of ℤ[i]\mathbb{Z}[i] is a ℤ\mathbb{Z}-linear isomorphism of ℤ[i]\mathbb{Z}[i] onto ℤ2\mathbb{Z}^2.