OctoInformBeta

OpenAI preprint, September 2026 · §3. Pair mass below a fixed scale

Lemma 3.2: Finite laws admit an explicit correction to the logarithm of the iterated sumset size

Pair capacities bound fixed-grid entropy loss.

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 fixed grid records the cell containing a real random variable and discards its position within that cell. For a finite law, this observation can identify distinct atoms.

A finitely supported probability law ν\nu on ℝ\mathbb R is a probability measure with a finite support FF and strictly positive normalized masses pxp_x, as in (1), where δx\delta_x is the unit point mass at xx. ν=∑x∈Fpxδx,px>0(x∈F),∑x∈Fpx=1.\nu=\sum_{x\in F}p_x\delta_x, \qquad p_x>0\quad(x\in F), \qquad \sum_{x\in F}p_x=1.(1)✦ The entropy ℋ(S,a)\mathcal H(S,a) in nats of weights aa on a finite set SS and the Shannon entropy H(ν)H(\nu) in bits of the finite law ν\nu are the real quantities given in (2). ℋ(S,a)=−∑x∈Saxln⁡ax,H(ν)=ℋ(F,p)ln⁡2.\mathcal H(S,a)=-\sum_{x\in S}a_x\ln a_x, \qquad H(\nu)=\frac{\mathcal H(F,p)}{\ln 2}.(2) Here the summand at a zero weight is zero.

For a finite set SS in a set AA, real weights a:A→ℝa:A\to\mathbb R, an observable f:A→Tf:A\to T taking values in a set TT and a value b∈Tb\in T, the fiber mass qf(b)q_f(b) is the sum of the weights of the points of SS mapped to bb.✦ The observable entropy ℋ(f(S),qf)\mathcal H(f(S),q_f) of real weights aa on a finite set SS under an observable ff is the Shannon entropy in nats of the fiber masses on f(S)f(S).✦ For the law ν\nu, its observable entropy ℋf(ν)\mathcal H_f(\nu) is given in (3). qf(b)=∑x∈Ff(x)=bpx,ℋf(ν)=ℋ(f(F),qf).q_f(b)=\sum_{\substack{x\in F\\f(x)=b}}p_x, \qquad \mathcal H_f(\nu)=\mathcal H\bigl(f(F),q_f\bigr).(3) At a scale ρ>0\rho>0, the unshifted grid observation gρg_\rho assigns each atom its cell index; its grid entropy in bits is Hρ0(ν)H_\rho^0(\nu) in (4). gρ(x)=⌊xρ⌋,Hρ0(ν)=ℋgρ(ν)ln⁡2.g_\rho(x)=\left\lfloor\frac{x}{\rho}\right\rfloor, \qquad H_\rho^0(\nu)=\frac{\mathcal H_{g_\rho}(\nu)}{\ln 2}.(4)✦

For a nonnegative integer kk, the iterated sumset kFkF is the set of sums of kk atoms, with the empty sum interpreted as zero, as in (5). kF={x1+⋯+xk:x1,…,xk∈F},0F={0}.kF=\left\{x_1+\cdots+x_k:x_1,\ldots,x_k\in F\right\}, \qquad 0F=\{0\}.(5)✦

Dyadic Pair Capacities

The dyadic distance band index b(u)b(u) of a real number uu is the negative of the floor of its base-two logarithm, as in (6). b(u)=−⌊log⁡2u⌋.b(u)=-\lfloor\log_2 u\rfloor.(6)✦ For an integer ℓ\ell, the pairs Eℓ(ν)E_\ell(\nu) at scale 2−ℓ2^{-\ell} are the unordered pairs of atoms whose distances lie in that dyadic band✦; the occupied distance bands B(ν)B(\nu) are the indices of nonempty pair sets in (7). Eℓ(ν)={{x,y}:x,y∈F,2−ℓ≤|x−y|<21−ℓ},B(ν)={ℓ∈ℤ:Eℓ(ν)≠⌀}.\begin{aligned} E_\ell(\nu) &=\bigl\{\{x,y\}:x,y\in F, \ 2^{-\ell}\leq |x-y|<2^{1-\ell}\bigr\},\\ B(\nu)&=\{\ell\in\mathbb Z:E_\ell(\nu)\ne\varnothing\}. \end{aligned}(7)

The incident pair mass Iw(x)I_w(x) of weights w:Eℓ(ν)→ℝw:E_\ell(\nu)\to\mathbb R at a real point xx is half the total weight of the pairs containing xx, as in (8). Iw(x)=12∑e∈Eℓ(ν)x∈ew(e).I_w(x)=\frac12\sum_{\substack{e\in E_\ell(\nu)\\x\in e}}w(e).(8)✦ Feasible pair weights on Eℓ(ν)E_\ell(\nu) are nonnegative weights whose incident mass at each atom is at most that atom’s mass; their set 𝒲ℓ(ν)\mathcal W_\ell(\nu) is defined in (9). 𝒲ℓ(ν)={w:Eℓ(ν)→[0,∞):Iw(x)≤px for every x∈F}.\mathcal W_\ell(\nu)= \bigl\{w:E_\ell(\nu)\to[0,\infty): I_w(x)\leq p_x\text{ for every }x\in F\bigr\}.(9)✦ The fair-pair capacity cℓ(ν)c_\ell(\nu) is the fractional matching capacity obtained by taking the supremum of total feasible pair weights in (10). cℓ(ν)=supw∈𝒲ℓ(ν)∑e∈Eℓ(ν)w(e).c_\ell(\nu)=\sup_{w\in\mathcal W_\ell(\nu)} \sum_{e\in E_\ell(\nu)}w(e).(10)✦

The Claim

Theorem 1. Let ν\nu be a finitely supported probability law on ℝ\mathbb R, let k≥1k\geq1 be an integer, and let ρ>0\rho>0. Its fixed-grid entropy loss obeys (11). k(H(ν)−Hρ0(ν))≤log⁡2|kF|+60000k4∑ℓ∈B(ν)2−ℓ≤2ρcℓ(ν).k\bigl(H(\nu)-H_\rho^0(\nu)\bigr) \leq \log_2|kF| +60000k^4 \sum_{\substack{\ell\in B(\nu)\\2^{-\ell}\leq2\rho}}c_\ell(\nu).(11)✦

In the paper, the result reads: for every integer k≥1k\geq1 there is a finite constant CkC_k, independent of the smallest positive distance in FF, such that every finitely supported probability law ν\nu on ℝ\mathbb R and every ρ>0\rho>0 satisfy (12). k(H(ν)−Hρ0(ν))≤log⁡2|kF|+Ck∑ℓ∈ℤ2−ℓ≤2ρcℓ(ν).k\bigl(H(\nu)-H_\rho^0(\nu)\bigr) \leq\log_2|kF| +C_k\sum_{\substack{\ell\in\mathbb Z\\2^{-\ell}\leq2\rho}}c_\ell(\nu).(12)

What Is Checked

The claim is stated for finite probability laws on ℝ\mathbb R, positive integers kk and positive grid scales ρ\rho, with the capacities in (10) defined using the feasible pair weights in (9).