OctoInformBeta

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

Lemma 3.3: Bracketing witnesses and template agreement inside actual visited windows

Counting blocked occurrences in periodic 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

Given an occurrence recorded by a periodic layer, the question is whether it lies inside an actual visited window that agrees with a prescribed template. A blocking witness specifies a longer recorded word and an occurrence inside it, with mismatches at the two ends of the longer word.

Let α\alpha be an alphabet. A substring occurrence of a word ss in a word rr at position jj is a contiguous match with 0≤j0\le j and j+|s|≤|r|j+|s|\le |r|; distinct starts count separately, including for overlapping matches and the empty word.✦ For an integer-indexed text B:ℤ→αB:\mathbb Z\to\alpha, write B[a,b)B[a,b) for its finite text window, with the empty word when b<ab<a.✦ A text occurrence of a word ss in an integer-indexed text BB at position xx is a match satisfying s[k]=B(x+k)s[k]=B(x+k) for 0≤k<|s|0\le k<|s|.✦ A word ss agrees with a template A:ℤ→αA:\mathbb Z\to\alpha when s[k]=A(k)s[k]=A(k) throughout its positions.✦ Two texts agree on [a,b)[a,b) when their symbols agree at every integer in that interval.✦

A periodic layer DD over a vertex set V⊆α*V\subseteq\alpha^* and a text BB, with parameter p∈ℕp\in\mathbb N, is a nondecreasing integer-valued exit function zDz_D satisfying (1).✦ Its first and last exits at xx are fD(x)=zD(x−1)f_D(x)=z_D(x-1) and ℓD(x)=zD(x)\ell_D(x)=z_D(x). x≤zD(x−1),zD(x+p)=zD(x)+p,B[x,e)∈Vwhenever zD(x−1)≤e≤zD(x).\begin{gathered} x\le z_D(x-1),\qquad z_D(x+p)=z_D(x)+p,\\ B[x,e)\in V\quad\text{whenever }z_D(x-1)\le e\le z_D(x). \end{gathered}(1) An actual window B[x,e)B[x,e) of a periodic layer DD over a text BB is a window with fD(x)≤e≤ℓD(x)f_D(x)\le e\le\ell_D(x). The recording predicate RD(s,x)R_D(s,x) and the set 𝒪D(s)\mathcal O_D(s) of recorded occurrence residues are defined by (2). An occurrence contained in an actual window need not itself be an actual window. RD(s,x)⇔s[k]=B(x+k)(0≤k<|s|) and x+|s|≤zD(x),𝒪D(s)={x∈ℤ:0≤x<p,RD(s,x)}.\begin{aligned} R_D(s,x)&\ \Longleftrightarrow\ s[k]=B(x+k)\ (0\le k<|s|)\ \text{ and }\ x+|s|\le z_D(x),\\ \mathcal O_D(s)&=\{x\in\mathbb Z:0\le x<p,\ R_D(s,x)\}. \end{aligned}(2) For a finite family 𝒟=(Di)i∈I\mathscr D=(D_i)_{i\in I}, the family occurrence set is the disjoint union 𝒪𝒟(s)=⨆i∈I𝒪Di(s)\mathcal O_{\mathscr D}(s)=\bigsqcup_{i\in I}\mathcal O_{D_i}(s); each occurrence retains its layer index.✦

Bracketing Witnesses

A blocking position jj of a word ss in a word rr, relative to a template AA, is a position satisfying (3).✦ Write JA(s,r)J_A(s,r) for the set of these positions. 1≤j,j+|s|<|r|,s occurs in r at j,r[h]=A(h−j)(0<h<|r|−1),r[0]≠A(−j),r[|r|−1]≠A(|r|−1−j).\begin{gathered} 1\le j,\qquad j+|s|<|r|,\qquad s\text{ occurs in }r\text{ at }j,\\ r[h]=A(h-j)\quad(0<h<|r|-1),\\ r[0]\ne A(-j),\qquad r[|r|-1]\ne A(|r|-1-j). \end{gathered}(3)✦ For a finite word set FF and a count function m:α*→ℕm:\alpha^*\to\mathbb N, the blocking coefficient cA(s,r)c_A(s,r) counts blocking positions✦, and the weighted blocking sum BA(s;m)B_A(s;m) is defined by (4) over FF.✦ cA(s,r)=|JA(s,r)|,BA(s;m)=∑r∈FcA(s,r)m(r).c_A(s,r)=|J_A(s,r)|,\qquad B_A(s;m)=\sum_{r\in F}c_A(s,r)m(r).(4)

A bracketing witness (r,y,j)(r,y,j) for a word ss in a layer DD, relative to a finite word set FF and a template AA, is a triple consisting of a word rr of FF, a recorded occurrence yy of rr and a blocking position jj inside rr, as in (5).✦ Family bracketing witnesses also retain the layer index.✦ 𝒲D,AF(s)={(r,y,j):r∈F,y∈𝒪D(r),j∈JA(s,r)},𝒲𝒟,AF(s)=⨆i∈I𝒲Di,AF(s).\begin{aligned} \mathcal W_{D,A}^F(s) &=\{(r,y,j):r\in F,\ y\in\mathcal O_D(r),\ j\in J_A(s,r)\},\\ \mathcal W_{\mathscr D,A}^F(s) &=\bigsqcup_{i\in I}\mathcal W_{D_i,A}^F(s). \end{aligned}(5) When p>0p>0 and BB is pp-periodic, phase normalization sends an integer recording start to its representative in [0,p)[0,p).✦ The blocked occurrence map βD,A,s\beta_{D,A,s} sends (r,y,j)(r,y,j) to the normalized occurrence of ss induced at y+jy+j.✦ Its family version β𝒟,A,s\beta_{\mathscr D,A,s} applies this map in each layer and preserves the layer index.✦

Primitive Layers from Counts

A finite count instance 𝒞\mathcal C is a triple of finite sets: a set VV of vertex words, a set SS of required words and a set Γ\Gamma of symbols.✦ A valid finite count instance 𝒞\mathcal C is a finite count instance whose vertex set VV contains the empty word, is closed under contiguous substrings and uses only symbols of its symbol set Γ\Gamma.✦ The maximum vertex length HH of a finite count instance 𝒞\mathcal C with vertex set VV is the maximum in (6), equal to zero when VV is empty. The forced count m(s)m(s) of a word ss in a finite count instance 𝒞\mathcal C is the value at stage H+1H+1 of the count iteration of 𝒞\mathcal C, which starts from zero and repeatedly applies the count recursion of 𝒞\mathcal C. The downward multiplicity d(s)d(s) of a word ss in a finite count instance 𝒞\mathcal C is the truncated difference in (6).✦ H=max⁡({0}∪{|r|:r∈V}),d(s)=max⁡{0,m(s)−∑c∈Γm(sc)}.H=\max\bigl(\{0\}\cup\{|r|:r\in V\}\bigr),\qquad d(s)=\max\left\{0,\ m(s)-\sum_{c\in\Gamma}m(sc)\right\}.(6) A downward edge token (r,k)(r,k) of a finite count instance 𝒞\mathcal C with vertex set VV and downward multiplicity dd is a pair with r∈Vr\in V and 0≤k<d(r)0\le k<d(r); its token word is rr.✦

A down-edge threading II on a vertex set VV is a set of tokens with nonempty token words w(i)∈Vw(i)\in V and a successor permutation σ\sigma such that deleting the first symbol of w(i)w(i) leaves a prefix of w(σi)w(\sigma i) for every i∈Ii\in I.✦ Here the token set is finite. For a valid finite count instance 𝒞\mathcal C, the base edge threading uses its downward edge tokens and a chosen compatible successor permutation.✦ For a threading with successor permutation σ\sigma and token words w(i)w(i), the induced periodic text TiT_i at token ii is the integer-indexed text defined by (7), using integer iterates of σ\sigma.✦ Ti(x)=the first symbol of w(σxi),x∈ℤ.T_i(x)=\text{the first symbol of }w(\sigma^x i),\qquad x\in\mathbb Z.(7)

Two tokens ii and jj of a threading II are text translation equivalent when their induced texts TiT_i and TjT_j agree after an integer translation.✦ A primitive text group gg of a threading is an equivalence class of tokens whose induced texts agree after an integer translation.✦ Choose a representative text BgB_g from the class and let pgp_g be its least positive period, the smallest positive integer pp with Bg(x+p)=Bg(x)B_g(x+p)=B_g(x) for all xx. For a text BB, its full-text-aligned tokens are E(B)={i∈I:Ti=B}E(B)=\{i\in I:T_i=B\}, where equality is at every integer position.✦ An aligned token enumeration of E(B)E(B) is a bijection j↦tjj\mapsto t_j from the ranks 0≤j<|E(B)|0\le j<|E(B)| onto the full-text-aligned tokens E(B)E(B).

Let q=|E(B)|q=|E(B)| and enumerate E(B)E(B) as t0,…,tq−1t_0,\ldots,t_{q-1}. At coordinate xx, the unsorted passage exits ej(x)e_j(x) and sorted layer exits zj(x)z_j(x) are given by (8). The sorted value list arranges the passage exits in nondecreasing order, retaining multiplicities✦; its entry of rank jj, counted from zero, is the jjth order statistic.✦ ej(x)=x+|w(σxtj)|,zj(x)=the jth order statistic of (ek(x))0≤k<q.e_j(x)=x+|w(\sigma^x t_j)|,\qquad z_j(x)=\text{the $j$th order statistic of }(e_k(x))_{0\le k<q}.(8) For substring-closed VV and a period pp of BB, the ordered layer at rank jj is the layer over BB with exit function zjz_j and parameter pp.✦ The indexed primitive layer Dg,jD_{g,j} of a threading is the ordered layer at rank jj over BgB_g with parameter pgp_g, with 0≤j<|E(Bg)|0\le j<|E(B_g)|.✦ Write 𝒟𝒞\mathscr D^{\mathcal C} for this family from the base threading, and put μ(r)=|𝒪𝒟𝒞(r)|\mu(r)=|\mathcal O_{\mathscr D^{\mathcal C}}(r)|. A primitive layer index is a pair (g,j)(g,j) consisting of a primitive text group gg and a rank jj with 0≤j<|E(Bg)|0\le j<|E(B_g)|.

The Claim

Theorem 1 (Lemma 3.3). Let 𝒟=(Di)i∈I\mathscr D=(D_i)_{i\in I} be a finite family of layers, with texts BiB_i and parameters pip_i. For a finite word set FF, a template AA and a word ss, the bracketing witness cardinality is (9), with the blocking sum taken over FF.✦ |𝒲𝒟,AF(s)|=BA(s;r↦|𝒪𝒟(r)|).|\mathcal W_{\mathscr D,A}^F(s)| =B_A\bigl(s;r\mapsto|\mathcal O_{\mathscr D}(r)|\bigr).(9)✦ If every pip_i is positive and every BiB_i is pip_i-periodic, the family blocked occurrence map satisfies (10).✦ β𝒟,A,s:𝒲𝒟,AF(s)→𝒪𝒟(s)is injective.\beta_{\mathscr D,A,s}:\mathcal W_{\mathscr D,A}^F(s) \longrightarrow\mathcal O_{\mathscr D}(s) \quad\text{is injective}.(10)✦ For a valid finite count instance 𝒞\mathcal C, its forced count mm and primitive layer count μ\mu satisfy (11) for every AA and ss, with both blocking sums taken over its vertex set VV.✦ BA(s;μ)=BA(s;m).B_A(s;\mu)=B_A(s;m).(11)✦ Finally, let DD be a layer over BB with parameter p>0p>0 and V=FV=F substring-closed. Suppose BB is pp-periodic and ss agrees with AA. For a recorded occurrence x∈𝒪D(s)x\in\mathcal O_D(s) outside the image of βD,A,s\beta_{D,A,s}, there is a matching actual window as specified in (12).✦ ∃a,b∈ℤ:a≤x,x+|s|≤b,fD(a)≤b≤ℓD(a),B(t)=A(t−x)for every integer t∈[a,b).\begin{gathered} \exists a,b\in\mathbb Z:\quad a\le x,\quad x+|s|\le b,\quad f_D(a)\le b\le\ell_D(a),\\ B(t)=A(t-x)\quad\text{for every integer }t\in[a,b). \end{gathered}(12)✦

What Is Checked

The witness statements range over finite families of layers and finite word sets; the blocking sum identity uses valid finite count instances and their base threadings, while the matching window statement uses a substring-closed vertex set and a template agreeing with ss.

For a count instance, each downward token has a nonempty vertex word, and validity ensures the existence of a compatible token permutation.✦ For an arbitrary threading, the ordered exit functions are nondecreasing✦ and bound each start from the preceding coordinate.✦ They translate by every period of their text.✦ With substring closure, every window between the first and last ordered exits belongs to the vertex set.✦