OctoInformBeta

OpenAI preprint, September 2026 · §2. Forced occurrence counts · §2

Lemma 2.2: The total letter count measures edge copies, while recorded phases account for required words

Forced counts balance the base edges.

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

In a hierarchical graph of substring vertices, an up step appends one symbol and costs one; a down step deletes the first symbol and costs zero. Assigning copies to these edges expresses occurrence requirements for the input words. The base multiplicities concern both the flow at a word and the occurrences recorded in periodic layer windows.

A finite count instance D=(V,R,A)D=(V,R,A) consists of finite sets VV and RR of words over a symbol set Σ\Sigma, and a finite alphabet A⊆ΣA\subseteq\Sigma.✦ The words in RR are required words. A vertex set VV is substring-closed if every contiguous substring of every word in VV, including the empty word ε\varepsilon, belongs to VV.✦ A valid count instance D=(V,R,A)D=(V,R,A) is a finite count instance such that ε∈V\varepsilon\in V, VV is substring-closed, and every symbol occurring in a word of VV belongs to AA.✦

The count iteration starts with zero counts and successively computes new occurrence counts.✦ The forced occurrence count m(s)m(s) of a word ss is its value after h+1h+1 stages, where the maximum vertex length hh is defined in (1).✦ This maximum is zero when VV is empty. h=max⁡({0}∪{|s|:s∈V}).h=\max\bigl(\{0\}\cup\{|s|:s\in V\}\bigr).(1)✦ The total forced letter count WW is the sum in (2). W=∑c∈Am(c).W=\sum_{c\in A}m(c).(2)✦ Here a symbol cc in the argument of mm denotes the one-letter word.

The base up and down multiplicities u(s)u(s) and d(s)d(s) of a word ss are the nonnegative integers defined in (3). u(s)=max⁡{m(s)−∑c∈Am(cs),0},d(s)=max⁡{m(s)−∑c∈Am(sc),0}.\begin{aligned} u(s)&=\max\left\{m(s)-\sum_{c\in A}m(cs),\,0\right\},\\ d(s)&=\max\left\{m(s)-\sum_{c\in A}m(sc),\,0\right\}. \end{aligned}(3) For a nonempty word ss, these are the multiplicities of the up edge that appends its last symbol and the down edge that deletes its first symbol.

Threading and Recorded Occurrences

A downward token (s,k)(s,k) of a finite count instance DD is a distinct copy of a downward edge, indexed by the set IDI_D in (4); its word is w(s,k)=sw_{(s,k)}=s. ID={(s,k):s∈V,0≤k<d(s)}.I_D=\{(s,k):s\in V,\ 0\leq k<d(s)\}.(4) A threading on a vertex set VV is a set II of tokens with nonempty words wi∈Vw_i\in V and a permutation π\pi of II satisfying the compatibility condition (5).✦ The notation t≼st\preceq s means that tt is a prefix of ss, and tail⁡(s)\operatorname{tail}(s) deletes its first symbol. tail⁡(wi)≼wπ(i)(i∈I).\operatorname{tail}(w_i)\preceq w_{\pi(i)} \qquad(i\in I).(5) The base threading of a valid count instance uses IDI_D, its token words, and a compatible permutation.✦

The text induced by a token ii is the integer-indexed text TiT_i defined in (6), where first\operatorname{first} takes the first symbol. Ti(x)=first⁡(wπx(i))(x∈ℤ).T_i(x)=\operatorname{first}\bigl(w_{\pi^x(i)}\bigr) \qquad(x\in\mathbb Z).(6)✦ Two tokens have translation-equivalent texts when they satisfy (7).✦ A text group gg of a threading is an equivalence class of tokens whose induced texts are translation-equivalent.✦ i∼j⇔∃a∈ℤ∀x∈ℤ,Ti(x+a)=Tj(x).i\sim j \quad\Longleftrightarrow\quad \exists a\in\mathbb Z\ \forall x\in\mathbb Z,\quad T_i(x+a)=T_j(x).(7)✦ The primitive period pp of an integer-indexed text AA is the least positive integer that is a period of AA. For each group gg, choose a representative text Ag=TiA_g=T_i and write pgp_g for its primitive period, as specified by (8). pg=min⁡{p∈ℕ:p>0,Ag(x+p)=Ag(x) for every x∈ℤ}.p_g=\min\{p\in\mathbb N:p>0,\ A_g(x+p)=A_g(x) \text{ for every }x\in\mathbb Z\}.(8)✦

A token ii aligned with an integer-indexed text AA is a token whose full induced text TiT_i equals AA. The alignment set I(A)I(A) of an integer-indexed text AA is the set of tokens aligned with AA, as in (9); enumerate its members as i0,…,iℓ(A)−1i_0,\ldots,i_{\ell(A)-1}, where ℓ(A)=|I(A)|\ell(A)=|I(A)|. I(A)={i∈I:Ti=A}.I(A)=\{i\in I:T_i=A\}.(9)✦ The passage exits ej(A,x)e_j(A,x) of an integer-indexed text AA at position xx are the integers defined in (10). The sorted exit bj(A,x)b_j(A,x) of a text AA at position xx is the jjth order statistic of its passage exits: index jj in the nondecreasing list of passage exits, retaining repetitions.✦ ej(A,x)=x+|wπx(ij)|,b0(A,x)≤⋯≤bℓ(A)−1(A,x).e_j(A,x)=x+|w_{\pi^x(i_j)}|, \qquad b_0(A,x)\leq\cdots\leq b_{\ell(A)-1}(A,x).(10)

A finite window A[a,b)A[a,b) of an integer-indexed text AA, for integers aa and bb, is the word of symbols at the integer positions in the half-open interval [a,b)[a,b); it is empty when b≤ab\leq a.✦ A layered phase (g,r,j)(g,r,j) of a threading is a triple consisting of a text group gg and integer indices rr and jj with 0≤r<pg0\leq r<p_g and 0≤j<ℓ(Ag)0\leq j<\ell(A_g).✦ The phase window qg,r,jq_{g,r,j} of a layered phase (g,r,j)(g,r,j) is the finite word in (11). qg,r,j=Ag[r,bj(Ag,r)).q_{g,r,j}=A_g[r,b_j(A_g,r)).(11) A recorded occurrence of a word ss is a phase whose window begins with ss.✦ The set ℛ(s)\mathcal R(s) of recorded occurrences of a word ss is the set of layered phases specified in (12). ℛ(s)={(g,r,j):0≤r<pg,0≤j<ℓ(Ag),s≼qg,r,j}.\mathcal R(s)=\{(g,r,j):0\leq r<p_g,\ 0\leq j<\ell(A_g),\ s\preceq q_{g,r,j}\}.(12)

The Claim

Theorem 1. Let D=(V,R,A)D=(V,R,A) be a finite count instance. Every nonempty required vertex w∈V∩Rw\in V\cap R satisfies (13). 1≤m(w).1\leq m(w).(13)✦ Suppose further that DD is valid. At every word ss, the base multiplicities satisfy the balance equation (14). u(s)+∑c∈Ad(cs)=d(s)+∑c∈Au(sc).u(s)+\sum_{c\in A}d(cs) =d(s)+\sum_{c\in A}u(sc).(14)✦ The total up and down multiplicities are given by (15) and (16), respectively. ∑s∈Vu(s)=W.\sum_{s\in V}u(s)=W.(15)✦ ∑s∈Vd(s)=W.\sum_{s\in V}d(s)=W.(16)✦ For every nonempty word ss, the base threading has the recorded multiplicity (17). |ℛ(s)|=m(s).|\mathcal R(s)|=m(s).(17)✦

What Is Checked

The required-word bound is stated over arbitrary finite count instances; the balance and total identities, and the recorded multiplicity identity, are stated over valid instances and their base threadings. Every downward token has a nonempty word.