OctoInformBeta

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

Lemma 3.1: Recorded occurrences match prefix counts in finite threadings and forced counts in the constructed base threading

Primitive layers preserve nonempty word counts.

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

The counting problem concerns occurrences of words in periodic layers. Overlapping occurrences are distinguished by their starting positions, and distinct copies of a hierarchical edge remain separate.

A finite count instance D=(V,R,Σ)D=(V,R,\Sigma) over a symbol set α\alpha consists of a finite set VV of vertex words, a finite set RR of required words, and a finite alphabet Σ\Sigma.✦ Write ε\varepsilon for the empty word, |s||s| for symbol length, and s≼ts\preceq t when ss is a prefix of tt. A substring-closed set VV contains every contiguous substring of each of its words, including ε\varepsilon.✦ A finite count instance D=(V,R,Σ)D=(V,R,\Sigma) is valid when ε∈V\varepsilon\in V, VV is substring-closed, and every letter of every vertex word belongs to Σ\Sigma.✦

The maximum vertex length is h=max⁡({0}∪{|v|:v∈V})h=\max(\{0\}\cup\{|v|:v\in V\}).✦ The count iteration cnc_n starts with the identically zero function c0c_0 and obtains cn+1c_{n+1} by applying DD’s count recursion operator to cnc_n.✦ The forced occurrence count m(s)m(s) and the base down multiplicity d(s)d(s) are defined by (1), where scsc denotes appending the letter cc and (a)+=max⁡{a,0}(a)_+=\max\{a,0\}. m(s)=ch+1(s),d(s)=(m(s)−∑c∈Σm(sc))+.m(s)=c_{h+1}(s), \qquad d(s)=\left(m(s)-\sum_{c\in\Sigma}m(sc)\right)_+.(1) A downward edge token is a pair (s,k)(s,k) with s∈Vs\in V and 0≤k<d(s)0\le k<d(s)✦; its token word is w(s,k)=sw(s,k)=s.✦ Denote this finite token set by IDI_D.

Threadings and Their Texts

A finite down edge threading CC on a vertex set VV assigns each token ii in a finite set II a nonempty word w(i)∈Vw(i)\in V and a successor permutation σ\sigma of II satisfying (2).✦ Here tail\operatorname{tail} deletes the first symbol. tail⁡(w(i))≼w(σ(i))(i∈I).\operatorname{tail}(w(i))\preceq w(\sigma(i)) \qquad(i\in I).(2) The base edge threading CDC_D of a valid count instance uses IDI_D, its token words, and a chosen compatible successor permutation.✦

The induced periodic text based at token ii is the integer-indexed text Ai(x)=first⁡(w(σx(i)))A_i(x)=\operatorname{first}(w(\sigma^x(i))), where first\operatorname{first} denotes the first symbol of a nonempty word.✦ Two tokens i,j∈Ii,j\in I are text translation equivalent when some integer tt satisfies Ai(x+t)=Aj(x)A_i(x+t)=A_j(x) for every integer xx.✦ A primitive text group gg of a threading CC is an equivalence class of tokens of CC under text translation equivalence.✦ Write GCG_C for the set of groups, choose a representative token igi_g in each group gg, and put Ag=AigA_g=A_{i_g}.✦ A period pp of a text AA is a positive integer such that A(x+p)=A(x)A(x+p)=A(x) for every integer xx; the least positive period of AA is a positive period of AA no larger than any other positive period of AA.✦ Denote the least positive period of AgA_g by pgp_g.✦

The full-text aligned tokens for a text AA form the set IA={i∈I:Ai(x)=A(x) for every x∈ℤ}I_A=\{i\in I:A_i(x)=A(x)\text{ for every }x\in\mathbb Z\}.✦ Put nA=|IA|n_A=|I_A| and enumerate these tokens as i0,…,inA−1i_0,\ldots,i_{n_A-1}. The unsorted passage exits eA,j(x)e_{A,j}(x) and sorted layer exits zA,j(x)z_{A,j}(x) of the enumerated tokens aligned with a text AA are the integer positions given by (3). The notation ord⁡j\operatorname{ord}_j means the entry at index jj, starting at zero, in the nondecreasing sorted list of the indicated values, with repetitions retained.✦ An aligned token enumeration for AA is a bijection from the indices 0,…,nA−10,\ldots,n_A-1 to the full-text aligned token set IAI_A, sending jj to iji_j.✦ eA,j(x)=x+|w(σx(ij))|,zA,j(x)=ord⁡j(eA,0(x),…,eA,nA−1(x)).e_{A,j}(x)=x+|w(\sigma^x(i_j))|, \qquad z_{A,j}(x)=\operatorname{ord}_j \bigl(e_{A,0}(x),\ldots,e_{A,n_A-1}(x)\bigr).(3)

Layers and Recorded Occurrences

For an integer-indexed text AA, the finite window A[a,b)A[a,b) is the word of symbols at positions a,…,b−1a,\ldots,b-1, and is empty when b≤ab\le a.✦ A word ss occurs in an integer-indexed text AA at an integer position xx when sr=A(x+r)s_r=A(x+r) for every 0≤r<|s|0\le r<|s|.✦

A periodic layer L=(A,p,z)L=(A,p,z) on VV consists of an integer-indexed text AA, a nonnegative integer parameter pp, and an integer-valued nondecreasing exit function zz satisfying the conditions in (4).✦ The visited windows of a periodic layer L=(A,p,z)L=(A,p,z) are the windows specified by the last condition of (4). x≤z(x−1),z(x+p)=z(x)+p(x∈ℤ),A[x,e)∈Vwhenever z(x−1)≤e≤z(x).\begin{gathered} x\le z(x-1),\qquad z(x+p)=z(x)+p \qquad(x\in\mathbb Z),\\ A[x,e)\in V \qquad\text{whenever }z(x-1)\le e\le z(x). \end{gathered}(4) For a substring-closed vertex set VV and a period pp of a text AA, the ordered layer with index jj is the periodic layer on VV with text AA, period pp, and exit function zA,jz_{A,j}.✦ The primitive layer indices of CC are the pairs (g,j)(g,j) with g∈GCg\in G_C and 0≤j<nAg0\le j<n_{A_g}✦; the indexed primitive layer Lg,jL_{g,j} uses text AgA_g, period pgp_g, and exits zAg,jz_{A_g,j}.✦ Denote this family by ℱC\mathcal F_C.

A layer L=(A,p,z)L=(A,p,z) records a word ss at an integer position xx when ss occurs in AA at xx and x+|s|≤z(x)x+|s|\le z(x).✦ The occurrence set Occ⁡L(s)\operatorname{Occ}_L(s) of a word ss in a layer L=(A,p,z)L=(A,p,z) is the set of its recorded positions 0≤x<p0\le x<p.✦ An occurrence of a word ss in a family of layers is a pair consisting of a layer in that family and an occurrence of ss in that layer; for ℱC\mathcal F_C this gives (5).✦ 𝒪ℱC(s)=∐g∈GC∐0≤j<nAgOcc⁡Lg,j(s).\mathcal O_{\mathcal F_C}(s) =\coprod_{g\in G_C}\coprod_{0\le j<n_{A_g}} \operatorname{Occ}_{L_{g,j}}(s).(5)

A primitive layered phase is a triple (g,x,j)(g,x,j) with g∈GCg\in G_C, 0≤x<pg0\le x<p_g, and 0≤j<nAg0\le j<n_{A_g}.✦ The phase window Pg,x,jP_{g,x,j} of a primitive layered phase (g,x,j)(g,x,j) is a finite word, and the recorded occurrence set ℛC(s)\mathcal R_C(s) of a word ss in a threading CC is a set of primitive layered phases, as defined in (6). Pg,x,j=Ag[x,zAg,j(x)),ℛC(s)={(g,x,j):s≼Pg,x,j}.P_{g,x,j}=A_g[x,z_{A_g,j}(x)), \qquad \mathcal R_C(s)=\{(g,x,j):s\preceq P_{g,x,j}\}.(6)

The Claim

Theorem 1. For a finite down edge threading CC and any finite word ss, the recorded count satisfies (7).✦ |ℛC(s)|=|{i∈I:s≼w(i)}|.|\mathcal R_C(s)|=|\{i\in I:s\preceq w(i)\}|.(7)✦ Let DD be a valid finite count instance, let CDC_D be its base edge threading, and let ℱCD\mathcal F_{C_D} be its primitive layer family. For every nonempty word ss, the threading and family counts satisfy (8) and (9), respectively. |ℛCD(s)|=m(s).|\mathcal R_{C_D}(s)|=m(s).(8)✦ |𝒪ℱCD(s)|=m(s).|\mathcal O_{\mathcal F_{C_D}}(s)|=m(s).(9)✦

In the paper, the result reads: for every nonempty word ss, the total number of recorded occurrences of ss on all the closed walks is m(s)m(s), counting starting positions modulo each walk’s turn length.

What Is Checked

The prefix count is stated over arbitrary finite down edge threadings; the forced counts are stated over valid finite count instances and nonempty words.

Every downward edge token has a nonempty vertex word. For a valid count instance, a compatible token permutation exists.✦ For every text AA, its sorted exits are nondecreasing✦ and satisfy the lower bound in (4)✦; when pp is a period of AA, their shift rule holds✦, and when VV is substring-closed, their visited windows belong to VV.✦