OctoInformBeta

OpenAI preprint, September 2026 · §5. Processing the period groups · §5

Lemma 5.1: Local exit gaps control global width, while full-text alignment limits recorded occurrences

Choosing sparse bands of 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

Within a periodic text group, several layers can record the same word at aligned positions. Processing a block of the highest layers requires a width bound along the whole text and a count of the recorded occurrences with a specified full-text alignment.

Let α\alpha be an alphabet and VV a set of finite words over α\alpha. The set VV is substring-closed when every contiguous substring of every word in VV, including the empty word, also belongs to VV.✦ Write |s||s| for the symbol length of a word ss. A down-edge threading CC on a finite token set II is a word assignment and a successor permutation σ\sigma of II: it assigns a nonempty word w(i)∈Vw(i)\in V to each token ii, with the tail of w(i)w(i) a prefix of w(σ(i))w(\sigma(i)).✦ Its induced integer-indexed text AiA_i is given by (1), where integer powers of σ\sigma include inverse iterates. Ai(x)=head⁡(w(σx(i))),x∈ℤ.A_i(x)=\operatorname{head}\bigl(w(\sigma^x(i))\bigr), \qquad x\in\mathbb Z.(1)✦

Text translation equivalence on the token set II is the relation that identifies tokens ii and jj when some integer dd satisfies Ai(x+d)=Aj(x)A_i(x+d)=A_j(x) for every integer xx.✦ A primitive text group gg of the threading CC is an equivalence class of tokens under text translation equivalence.✦ The group text representative AgA_g of a primitive text group gg is the text of a representative token of gg.✦ The primitive group period pgp_g of gg is the smallest positive integer whose translation leaves AgA_g unchanged.✦ A positive integer pp is a period of a text AA when A(x+p)=A(x)A(x+p)=A(x) for all integers xx; it is the least positive period when every positive period is at least pp.✦

For an integer-indexed text AA, the finite window A[a,b)A[a,b) lists its symbols at the integer positions in [a,b)[a,b), with the empty word used when b≤ab\le a.✦ A periodic layer DD for VV, AA and a period parameter pp is a nondecreasing integer-valued exit function zDz_D satisfying (2).✦ The first and last exits of a periodic layer DD with exit function zDz_D at start 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,x∈ℤ,A[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,\qquad x\in\mathbb Z,\\ A[x,e)\in V\quad\text{whenever }z_D(x-1)\le e\le z_D(x). \end{gathered}(2)

The full-text-aligned token set IAI_A of a threading CC for a text AA is the set of tokens of CC whose induced text equals AA at every integer position.✦ Put mA=|IA|m_A=|I_A|, and enumerate these tokens bijectively as qA(0),…,qA(mA−1)q_A(0),\ldots,q_A(m_A-1).✦ The sorted value list of a finite indexed family is a list of the family’s values in nondecreasing order, retaining repetitions✦; the jjth order statistic ord⁡j\operatorname{ord}_j of the family is the entry at index jj in its sorted value list, starting from zero.✦ The unsorted passage exits eA,je_{A,j} and sorted layer exits zA,jz_{A,j} for the text AA are integer-valued functions of the start position given by (3). eA,j(x)=x+|w(σx(qA(j)))|,zA,j(x)=ord⁡j(eA,0(x),…,eA,mA−1(x)),0≤j<mA.\begin{aligned} e_{A,j}(x)&=x+\bigl|w(\sigma^x(q_A(j)))\bigr|,\\ z_{A,j}(x)&=\operatorname{ord}_j \bigl(e_{A,0}(x),\ldots,e_{A,m_A-1}(x)\bigr), \qquad 0\le j<m_A. \end{aligned}(3) For substring-closed VV and a text AA with period pp, the ordered layer DA,jD_{A,j} is the periodic layer with exit function zA,jz_{A,j}.✦ The primitive layer indices of the threading CC are the pairs (g,j)(g,j) in which gg is a primitive text group and 0≤j<mAg0\le j<m_{A_g}✦; the indexed primitive layer Dg,j=DAg,jD_{g,j}=D_{A_g,j} at a primitive layer index (g,j)(g,j) is a periodic layer with text AgA_g and period pgp_g.✦

A word ss occurs in AA at an integer origin rr when si=A(r+i)s_i=A(r+i) for every 0≤i<|s|0\le i<|s|.✦ A recorded occurrence at origin rr of a word ss in a layer DD with text AA is an occurrence of ss in AA whose endpoint does not exceed zD(r)z_D(r).✦ The layer occurrence set 𝒪D(s)\mathcal O_D(s) of a word ss in a periodic layer DD with text AA and period pp is the set of start residues of recorded occurrences in one period, as in (4).✦ These records need not themselves be windows whose endpoints lie between the first and last exits at their starts. 𝒪D(s)={r∈ℤ:0≤r<p,s=A[r,r+|s|),r+|s|≤zD(r)}.\mathcal O_D(s)= \{r\in\mathbb Z:0\le r<p,\ s=A[r,r+|s|),\ r+|s|\le z_D(r)\}.(4)✦ The family occurrence set 𝒪(s)\mathcal O(s) for a word ss in a threading CC is the disjoint union of 𝒪Dh,j(s)\mathcal O_{D_{h,j}}(s) over primitive layer indices (h,j)(h,j) of CC, so an occurrence retains its owner and start residue.✦ For a word ss, a primitive text group gg and an integer tt, the aligned occurrence set 𝒜g,t(s)\mathcal A_{g,t}(s) is the subset of 𝒪(s)\mathcal O(s) defined by (5). 𝒜g,t(s)={(h,j,r)∈𝒪(s):Ah(y+r)=Ag(y+t) for every y∈ℤ}.\mathcal A_{g,t}(s)= \{(h,j,r)\in\mathcal O(s): A_h(y+r)=A_g(y+t)\text{ for every }y\in\mathbb Z\}.(5)✦

For an integer exit family z0,…,zm−1z_0,\ldots,z_{m-1}, an integer threshold hh and nonnegative integers p,kp,k, the qualifying index set Qk(z,h,p)Q_k(z,h,p) is the set of layer indices specified in (6). Qk(z,h,p)={j:0≤j<m,h−kp≤zj}.Q_k(z,h,p)=\{j:0\le j<m,\ h-kp\le z_j\}.(6)✦

The Claim

Theorem 1 (Lemma 5.1). Let 1≤n≤m1\le n\le m, let z0≤⋯≤zm−1z_0\le\cdots\le z_{m-1} be integer exits, and let hh be an integer threshold with h≤zm−1h\le z_{m-1}. For a nonnegative integer pp, suppose |Qn(z,h,p)|≤n|Q_n(z,h,p)|\le n. There is an integer kk satisfying (7). 1≤k≤n,|Qk(z,h,p)|≤k,h−(k−1)p≤zm−k.1\le k\le n,\qquad |Q_k(z,h,p)|\le k,\qquad h-(k-1)p\le z_{m-k}.(7)✦

Let UU and DD be periodic layers for the same VV, text AA and positive period pp. Let k≥1k\ge1 and t∈ℤt\in\mathbb Z, and suppose fU(t)−ℓD(t)≤(k−1)pf_U(t)-\ell_D(t)\le(k-1)p. Then (8) holds at every integer start. fU(x)−ℓD(x)≤kp,x∈ℤ.f_U(x)-\ell_D(x)\le kp,\qquad x\in\mathbb Z.(8)✦

Let CC be a finite down-edge threading through a substring-closed vertex set VV. For a primitive text group gg, an integer tt and a word ss, its aligned recorded occurrences satisfy (9). |𝒜g,t(s)|≤|{j:0≤j<mAg,t+|s|≤zAg,j(t)}|.|\mathcal A_{g,t}(s)|\le \bigl|\{j:0\le j<m_{A_g},\ t+|s|\le z_{A_g,j}(t)\}\bigr|.(9)✦

What Is Checked

The selection statement ranges over finite nondecreasing integer exit families; the width and occurrence statements concern periodic layers and the primitive layers of finite threadings through substring-closed vertex sets.

Sorted exits are nondecreasing✦ and satisfy the first inequality in (2) for every text AA.✦ For a text with period pp, they satisfy the translation identity in (2) with that period.✦ For substring-closed VV, every window between the preceding and current sorted exits belongs to VV.✦