OctoInformBeta

OpenAI preprint, September 2026 · §4. Conditioning on block types

Proposition 4.2: Finite-scale bands for translation laws conditioned on symbol types

Retained entropy loss forces pair capacity.

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

Conditioning affine words on their symbol types leaves a finite distribution of translations. The entropy lost when these translations are observed through a fine grid is compared with the mass that can be assigned to pairs of nearby translations. Words are retained according to a linear bound on their contraction depth.

A weighted affine iterated function system on a finite alphabet II consists of maps and probabilities satisfying (1), with signed slopes rir_i and arbitrary real translations tit_i: φi(x)=rix+ti,0<|ri|<1,pi>0,∑i∈Ipi=1.\varphi_i(x)=r_i x+t_i,\qquad 0<|r_i|<1,\qquad p_i>0,\qquad \sum_{i\in I}p_i=1.(1)✦ The complete affine map of a word w=i1⋯in∈Inw=i_1\cdots i_n\in I^n is its composition in address order.✦ Its signed slope rwr_w, translation twt_w, word probability pwp_w and contraction depth d(w)d(w) are given by (2): φw(x)=(φi1∘⋯∘φin)(x)=rwx+tw,φ⌀(x)=x,pw=∏j=1npij,d(w)=−ln⁡|rw|ln⁡2.\begin{aligned} \varphi_w(x)&=(\varphi_{i_1}\circ\cdots\circ\varphi_{i_n})(x)=r_wx+t_w, &\varphi_{\varnothing}(x)&=x,\\ p_w&=\prod_{j=1}^n p_{i_j}, &d(w)&=-\frac{\ln|r_w|}{\ln2}. \end{aligned}(2)

Conditional Laws and Entropy

For real weights q=(qj)j∈Jq=(q_j)_{j\in J} on a finite set JJ, their Shannon entropy in nats is Hnat(q)H_{\mathrm{nat}}(q) in (3).✦ The fiber mass mf(x)m_f(x) and entropy of an observable ff on JJ are defined in (3), with zero contribution at zero mass. For the observable distribution below, the weights are strictly positive and have total mass one. Hnat(q)=−∑j∈Jqjln⁡qj,mf(x)=∑j∈Jf(j)=xqj,Hnat(f*q)=−∑x∈f(J)mf(x)ln⁡mf(x).\begin{aligned} H_{\mathrm{nat}}(q)&=-\sum_{j\in J}q_j\ln q_j, &m_f(x)&=\sum_{\substack{j\in J\\f(j)=x}}q_j,\\ H_{\mathrm{nat}}(f_*q)&=-\sum_{x\in f(J)}m_f(x)\ln m_f(x). \end{aligned}(3) A finitely supported probability law ν\nu on ℝ\mathbb R consists of a finite support and strictly positive point masses summing to one.✦ For a real-valued observable ff and strictly positive qq, the observable distribution f*qf_*q has support f(J)f(J) and point masses mf(x)m_f(x).✦

A tag map τ:I→T\tau:I\to T assigns a type to each symbol. The word tag sequence of w=i1⋯inw=i_1\cdots i_n is τ(w)=(τ(i1),…,τ(in))\tau(w)=(\tau(i_1),\ldots,\tau(i_n)).✦ The tag fiber FwF_w of a word ww is the set of words of the same length whose tag sequence equals τ(w)\tau(w)✦, and the fiber mass MwM_w is the sum of their word probabilities.✦ The type-conditioned translation law νw\nu_w of a word ww is the conditional observable distribution of translation on the tag fiber FwF_w, defined in (4): Fw={v∈In:τ(v)=τ(w)},Mw=∑v∈Fwpv,νw({x})=1Mw∑v∈Fwtv=xpv.F_w=\{v\in I^n:\tau(v)=\tau(w)\},\qquad M_w=\sum_{v\in F_w}p_v,\qquad \nu_w(\{x\})=\frac{1}{M_w}\sum_{\substack{v\in F_w\\t_v=x}}p_v.(4)✦

For a finite probability law ν\nu and a mesh ρ>0\rho>0, the grid-cell mass qjρq_j^\rho is its mass in the cell indexed by j∈ℤj\in\mathbb Z. Its Shannon entropy H2(ν)H_2(\nu) and grid entropy H2ρ(ν)H_2^\rho(\nu) in bits are defined by (5): qjρ=ν({x:⌊x/ρ⌋=j}),H2(ν)=Hnat(ν)ln⁡2,H2ρ(ν)=−∑j∈ℤqjρlog⁡2qjρ.\begin{aligned} q_j^\rho&=\nu\bigl(\{x:\lfloor x/\rho\rfloor=j\}\bigr),\\ H_2(\nu)&=\frac{H_{\mathrm{nat}}(\nu)}{\ln2}, &H_2^\rho(\nu)&=-\sum_{j\in\mathbb Z}q_j^\rho\log_2q_j^\rho. \end{aligned}(5) The conditional grid entropy deficit Lw(ρ)L_w(\rho) of the type-conditioned translation law νw\nu_w at mesh ρ>0\rho>0 is the loss in nats defined by (6): Lw(ρ)=(H2(νw)−H2ρ(νw))ln⁡2.L_w(\rho)=\bigl(H_2(\nu_w)-H_2^\rho(\nu_w)\bigr)\ln2.(6)✦ For A∈ℝA\in\mathbb R and n≥0n\ge0, the fine scale ρn\rho_n and first dyadic band ana_n are defined by (7): ρn=2−⌈An⌉,an=⌈An⌉−1.\rho_n=2^{-\lceil An\rceil},\qquad a_n=\lceil An\rceil-1.(7) The retained entropy loss RnR_n for A′∈ℝA'\in\mathbb R is the weighted sum of deficits on words satisfying the depth cutoff, as in (8): Rn=∑w∈Ind(w)≤A′npwLw(ρn).R_n=\sum_{\substack{w\in I^n\\d(w)\le A'n}}p_wL_w(\rho_n).(8)✦

Pair Capacity

For a finite probability law ν\nu and an integer ℓ\ell, the pair set ℰℓ(ν)\mathcal E_\ell(\nu) is the set of unordered pairs of atoms satisfying the distance bounds in (9).✦ The incident mass Iu(x)I_u(x) of weights uu on these pairs is one half of the total weight of pairs containing xx: ℰℓ(ν)={{x,y}:x,y∈supp⁡ν,2−ℓ≤|x−y|<21−ℓ},Iu(x)=12∑e∈ℰℓ(ν)x∈eue.\begin{aligned} \mathcal E_\ell(\nu) &=\bigl\{\{x,y\}:x,y\in\operatorname{supp}\nu, \ 2^{-\ell}\le|x-y|<2^{1-\ell}\bigr\},\\ I_u(x)&=\frac12\sum_{\substack{e\in\mathcal E_\ell(\nu)\\x\in e}}u_e. \end{aligned}(9)✦ Feasible pair weights on ℰℓ(ν)\mathcal E_\ell(\nu) are nonnegative weights ueu_e whose incident mass at each atom is at most its probability.✦ The fair-pair capacity cℓ(ν)c_\ell(\nu) of a finite probability law ν\nu in band ℓ\ell is the supremum of the total weights of feasible pair weights on ℰℓ(ν)\mathcal E_\ell(\nu), as in (10): cℓ(ν)=sup⁡{∑e∈ℰℓ(ν)ue:ue≥0,Iu(x)≤ν({x})for all x∈suppν}.c_\ell(\nu)=\sup\left\{\sum_{e\in\mathcal E_\ell(\nu)}u_e: u_e\ge0,\quad I_u(x)\le\nu(\{x\})\ \text{for all }x\in\operatorname{supp}\nu\right\}.(10)✦ The weighted pair budget Pn(a,B)P_n(a,B) on an integer band a≤Ba\le B is the sum in (11), with the same depth cutoff as the retained loss: Pn(a,B)=∑w∈Ind(w)≤A′npw∑ℓ=aBcℓ(νw).P_n(a,B)=\sum_{\substack{w\in I^n\\d(w)\le A'n}}p_w \sum_{\ell=a}^{B}c_\ell(\nu_w).(11)✦

The Claim

Theorem 1. Let τ\tau have constant signed slopes on its fibers: symbols with the same tag have the same rir_i. Fix A,A′∈ℝA,A'\in\mathbb R. For n≥0n\ge0 and an integer k≥1k\ge1, the estimate (12) holds simultaneously for all words w∈Inw\in I^n with a common integer upper band index B≥anB\ge a_n: kLw(ρn)≤n|I|ln⁡(k+1)+60000k4ln⁡2∑ℓ=anBcℓ(νw).kL_w(\rho_n)\le n|I|\ln(k+1) +60000k^4\ln2\sum_{\ell=a_n}^{B}c_\ell(\nu_w).(12)✦ If ε>0\varepsilon>0 and N∈ℕN\in\mathbb N satisfy Rn≥εnR_n\ge\varepsilon n for every n≥Nn\ge N, then there is c>0c>0 such that, for each n≥Nn\ge N, an integer B≥anB\ge a_n satisfies (13): cn≤Pn(an,B).cn\le P_n(a_n,B).(13)✦

In the paper, the result reads: under all the assumptions and notation of Lemma 4.1, there are c>0c>0 and n0n_0 such that for each n≥n0n\ge n_0 a deterministic finite integer Bn≥anB_n\ge a_n satisfies 𝔼[𝟏En∑ℓ=anBncℓ(νω,n)]≥cn\mathbb E[\mathbf1_{E_n}\sum_{\ell=a_n}^{B_n}c_\ell(\nu_{\omega,n})]\ge cn, with b,A,A′,c,n0b,A,A',c,n_0 independent of nn and ω\omega and no asserted growth bound on BnB_n.

What Is Checked

The claims are stated over finite weighted affine systems and tag maps that preserve the signed contraction ratio, using conditional translation laws and the depth cutoff in (8).