OctoInformBeta

OpenAI preprint, September 2026 · §3. Periodic layers · §3

Lemma 3.2: Actual windows, preserved upward edge multiplicities, and a layer budget equal to the forced letter count

Sorting periodic passages into ordered layers.

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

Periodic passages through the hierarchical word graph have a start position and an exit position. Lemma 3.2 concerns the layers obtained by sorting passage exits at each start, with passages aligned to the same full periodic text.

A substring-closed vertex set VV is a set of finite words over symbols α\alpha that contains every contiguous substring of each of its words, including the empty word.✦ A hierarchical walk in VV consists of up steps that append one symbol and down steps that delete the first symbol, with both endpoints of every step in VV; empty walks and concatenations of composable walks are allowed.✦ The cost c(P)c(P) of a hierarchical walk PP in VV is its number of up steps.✦ A walk visits a word when that word is one of its vertices, including an endpoint.✦

A down edge threading CC on VV with finite token set II is an assignment of a nonempty word w(i)∈Vw(i)\in V to each token i∈Ii\in I, together with a successor permutation σ\sigma of II such that deleting the first symbol of w(i)w(i) leaves a prefix of w(σ(i))w(\sigma(i)).✦ The induced text Ai:ℤ→αA_i:\mathbb Z\to\alpha at token ii is defined by (1); negative powers use the inverse permutation. Ai(x)=the first symbol of w(σx(i)).A_i(x)=\text{the first symbol of }w(\sigma^x(i)).(1)✦ For an integer-indexed text AA, its finite window A[a,b)A[a,b) lists the symbols at positions a,a+1,…,b−1a,a+1,\ldots,b-1, and is empty when b≤ab\le a.✦ A positive period of AA is a positive integer pp satisfying A(x+p)=A(x)A(x+p)=A(x) for every integer xx. The primitive period of an integer-indexed text AA is its least positive period.✦

Two tokens i,j∈Ii,j\in I of a down edge threading CC are text translation equivalent when their full induced texts agree after an integer shift.✦ For a down edge threading CC with token set II, the primitive text groups 𝒢C\mathcal G_C are the text translation equivalence classes in II, given by (2).✦ For each group gg, choose a representative token igi_g, write Ag=AigA_g=A_{i_g}, and let pgp_g be the primitive period of AgA_g. i∼j⇔there is d∈ℤ such that Ai(x+d)=Aj(x) for every x∈ℤ,𝒢C=I/∼.i\sim j\quad\Longleftrightarrow\quad \text{there is }d\in\mathbb Z\text{ such that } A_i(x+d)=A_j(x)\text{ for every }x\in\mathbb Z, \qquad \mathcal G_C=I/{\sim}.(2)

Passage Exits and Layers

The tokens fully aligned with the text AA form the set IAI_A in (3); alignment here concerns every integer position. Let nA=|IA|n_A=|I_A| and enumerate these tokens bijectively as i0,…,inA−1i_0,\ldots,i_{n_A-1}.✦ IA={i∈I:Ai=A}.I_A=\{i\in I:A_i=A\}.(3)✦ The unsorted passage exit Ej(x)E_j(x) is the endpoint in (4), where word length counts symbols. Ej(x)=x+|w(σx(ij))|,0≤j<nA.E_j(x)=x+|w(\sigma^x(i_j))|, \qquad 0\le j<n_A.(4)✦ For a finite family of ordered values, its sorted value list is its list of values in nondecreasing order, retaining repetitions✦; its jjth order statistic is the entry at index jj, starting at zero.✦ The sorted layer exit zj(x)z_j(x) is the order statistic in (5). zj(x)=the jth order statistic of (E0(x),…,EnA−1(x)).z_j(x)=\text{the $j$th order statistic of } (E_0(x),\ldots,E_{n_A-1}(x)).(5)✦

A periodic layer LL for V,AV,A and a nonnegative integer parameter pp is an integer-valued exit function zz satisfying (6) and having A[x,e)∈VA[x,e)\in V whenever z(x−1)≤e≤z(x)z(x-1)\le e\le z(x).✦ The first and last exit positions of a periodic layer LL with exit function zz at an integer xx are fL(x)=z(x−1)f_L(x)=z(x-1) and ℓL(x)=z(x)\ell_L(x)=z(x). Write ℒ(V,A,p)\mathscr L(V,A,p) for the set of these layers. z(x)≤z(y)(x≤y),x≤z(x−1),z(x+p)=z(x)+p(x∈ℤ).\begin{gathered} z(x)\le z(y)\quad(x\le y),\qquad x\le z(x-1),\\ z(x+p)=z(x)+p\quad(x\in\mathbb Z). \end{gathered}(6)

Count Data and Their Budget

A finite count instance D=(V,R,Σ)D=(V,R,\Sigma) consists of finite sets of vertex words VV, required words RR, and symbols Σ⊆α\Sigma\subseteq\alpha.✦ A valid finite count instance D=(V,R,Σ)D=(V,R,\Sigma) is a finite count instance for which VV contains the empty word, is substring-closed, and every symbol in a vertex word belongs to Σ\Sigma.✦ The count iteration m0,m1,…m_0,m_1,\ldots starts with the zero count and applies DD’s count recursion at each successive stage.✦ The maximum vertex length hh and forced occurrence count mm of a finite count instance D=(V,R,Σ)D=(V,R,\Sigma) are given by (7). h=max⁡({0}∪{|s|:s∈V}),m(s)=mh+1(s).h=\max\bigl(\{0\}\cup\{|s|:s\in V\}\bigr), \qquad m(s)=m_{h+1}(s).(7) The base down multiplicity d(s)d(s) and total forced letter count WW are (8), where [c][c] is the one-letter word, s[c]s[c] denotes the word obtained by appending cc to ss, and subtraction is truncated at zero. d(s)=max⁡{0,m(s)−∑c∈Σm(s[c])},W=∑c∈Σm([c]).d(s)=\max\left\{0,m(s)-\sum_{c\in\Sigma}m(s[c])\right\}, \qquad W=\sum_{c\in\Sigma}m([c]).(8) A down token of DD is a pair (s,r)(s,r) with s∈Vs\in V and 0≤r<d(s)0\le r<d(s)✦; its token word is ss.✦ Denote the set of these tokens by IDI_D. For a valid count instance DD, its base edge threading CDC_D assigns each token its token word and chooses a successor permutation of IDI_D such that deleting the first symbol of each token word leaves a prefix of the next token word.

The Claim

Theorem 1 (Lemma 3.2). Let CC be a down edge threading on VV with finite token set II, let A:ℤ→αA:\mathbb Z\to\alpha be a text, and let pp be a nonnegative integer. If VV is substring-closed and A(x+p)=A(x)A(x+p)=A(x) for every integer xx, the ordered layer construction is (9). Lj=(zj)∈ℒ(V,A,p),0≤j<nA.L_j=(z_j)\in\mathscr L(V,A,p),\qquad 0\le j<n_A.(9)✦ For any AA, indices 0≤i≤j<nA0\le i\le j<n_A and integer xx, the exits satisfy (10). zi(x)≤zj(x).z_i(x)\le z_j(x).(10)✦ For all integers x,ex,e, the upward unit-edge multiplicities satisfy (11), with both sets indexed by 0≤j<nA0\le j<n_A. |{j:zj(x−1)≤e<zj(x)}|=|{j:Ej(x−1)≤e<Ej(x)}|.\bigl|\{j:z_j(x-1)\le e<z_j(x)\}\bigr| =\bigl|\{j:E_j(x-1)\le e<E_j(x)\}\bigr|.(11)✦ If VV is substring-closed, then for any AA, any j<nAj<n_A, and integers x,ex,e with zj(x−1)≤e≤zj(x)z_j(x-1)\le e\le z_j(x), the actual window satisfies (12). A[x,e)∈V.A[x,e)\in V.(12)✦ Let L∈ℒ(V,A,p)L\in\mathscr L(V,A,p), with VV substring-closed and A(x+p)=A(x)A(x+p)=A(x) for every integer xx. For every integer tt, there is a closed hierarchical walk PP based at A[t,fL(t))A[t,f_L(t)) satisfying (13). c(P)=p,P visits A[x,e)(t≤x<t+p,fL(x)≤e≤ℓL(x)).\begin{gathered} c(P)=p,\\ P\text{ visits }A[x,e)\quad \bigl(t\le x<t+p,\ f_L(x)\le e\le\ell_L(x)\bigr). \end{gathered}(13)✦ The primitive text groups of every finite threading satisfy (14). ∑g∈𝒢Cpg|IAg|=|I|.\sum_{g\in\mathcal G_C}p_g\,|I_{A_g}|=|I|.(14)✦ For every valid finite count instance DD, the specialization to its base edge threading CDC_D is (15), with groups and aligned token sets taken in CDC_D. ∑g∈𝒢CDpg|IAg|=W.\sum_{g\in\mathcal G_{C_D}}p_g\,|I_{A_g}|=W.(15)✦

In the paper, the result reads: closed walks with the same periodic text up to translation and least period pp can be rearranged without changing their edge multiset into pointwise ordered one-turn layers whose exit functions obey (6), each with up cost pp, and with total cost WW over all groups.

What Is Checked

The statements range over finite down edge threadings, substring-closed vertex sets where required, integer-indexed texts with a specified period for layer construction and turns, and valid finite count instances for the budget WW. For sorted exits, monotonicity and the lower bound hold for every text, and the shift identity holds for each period of that text.✦ For count data, every down token has a nonempty vertex word.