OctoInformBeta

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

§3 (setting): periodic texts, actual windows and recorded occurrences: Integer coordinates retain receiving windows and interval alignments for connections between layers

Windows and 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

Connections between periodic pieces of a superstring depend on where a word is read and which window receives it. A substring inside a visited window need not itself be a visited vertex. The library defines layers with explicit window endpoints and records that align an interval of one text with a receiving layer of another.

Let Σ\Sigma be an alphabet and V⊆Σ*V\subseteq\Sigma^* a set of finite words. Write ε\varepsilon for the empty word and |s||s| for the symbol length of a word ss. Texts have integer positions, so a text is a function A:ℤ→ΣA:\mathbb Z\to\Sigma.

The Definition

Definition 1. The finite text window A[a,b)A[a,b) of a text AA at integer endpoints a,ba,b is the word in (1).✦ A[a,b)={A(a)A(a+1)⋯A(b−1),a<b,ε,b≤a.A[a,b)= \begin{cases} A(a)A(a+1)\cdots A(b-1),&a<b,\\ \varepsilon,&b\le a. \end{cases}(1)✦

For a text admitting a positive period, its primitive period pp is the least positive shift preserving every symbol, as in (2).✦ p=min⁡{n∈ℕ>0:A(x+n)=A(x) for every x∈ℤ}.p=\min\{n\in\mathbb N_{>0}: A(x+n)=A(x)\text{ for every }x\in\mathbb Z\}.(2)✦

A threading of VV indexed by a set II is a family of words (wi)i∈I(w_i)_{i\in I} and a permutation σ\sigma of II satisfying (3).✦ Here tail⁡(w)\operatorname{tail}(w) deletes the first symbol of ww, and ≼pref\preceq_{\mathrm{pref}} denotes prefix containment. wi∈V,wi≠ε,tail⁡(wi)≼prefwσ(i)(i∈I).w_i\in V,\qquad w_i\ne\varepsilon,\qquad \operatorname{tail}(w_i)\preceq_{\mathrm{pref}}w_{\sigma(i)} \quad(i\in I).(3)✦

A layer DD over VV on a text AA, with shift p∈ℕp\in\mathbb N, is an integer boundary function z:ℤ→ℤz:\mathbb Z\to\mathbb Z satisfying (4); all variables x,y,ex,y,e in these conditions are integers.✦ z(x)≤z(y)(x≤y),x≤z(x−1),z(x+p)=z(x)+p,A[x,e)∈V(z(x−1)≤e≤z(x)).\begin{aligned} z(x)&\le z(y) &&(x\le y),\\ x&\le z(x-1),\\ z(x+p)&=z(x)+p,\\ A[x,e)&\in V &&(z(x-1)\le e\le z(x)). \end{aligned}(4)✦ The first exit position fD(x)f_D(x) and last exit position ℓD(x)\ell_D(x) of DD at xx are the bounds in (5). fD(x)=z(x−1),ℓD(x)=z(x).f_D(x)=z(x-1),\qquad \ell_D(x)=z(x).(5)

An occurrence of a word ss in a text AA at a starting position x∈ℤx\in\mathbb Z, written s⊑xAs\sqsubseteq_x A, is specified by (6), where sis_i is the symbol at position ii of ss, counted from zero.✦ s⊑xA⇔si=A(x+i)for every integer i with 0≤i<|s|.s\sqsubseteq_x A \quad\Longleftrightarrow\quad s_i=A(x+i)\quad\text{for every integer }i\text{ with }0\le i<|s|.(6) A layer DD records a word ss at xx, written Rec⁡D(s,x)\operatorname{Rec}_D(s,x), when (7) holds.✦ Rec⁡D(s,x)⇔s⊑xA and x+|s|≤z(x).\operatorname{Rec}_D(s,x) \quad\Longleftrightarrow\quad s\sqsubseteq_x A\ \text{ and }\ x+|s|\le z(x).(7)✦ A recorded occurrence residue rr of a word ss in a layer DD with shift pp is an integer belonging to the set Occ⁡D(s)\operatorname{Occ}_D(s) in (8). Occ⁡D(s)={r∈ℤ:0≤r<p and Rec⁡D(s,r)}.\operatorname{Occ}_D(s)= \{r\in\mathbb Z:0\le r<p\ \text{ and }\operatorname{Rec}_D(s,r)\}.(8)✦

Two texts A,C:ℤ→ΣA,C:\mathbb Z\to\Sigma agree on the half-open interval [a,b)[a,b), written A≡[a,b)CA\equiv_{[a,b)}C, when (9) holds.✦ A≡[a,b)C⇔A(x)=C(x)for every integer x with a≤x<b.A\equiv_{[a,b)}C \quad\Longleftrightarrow\quad A(x)=C(x)\quad\text{for every integer }x\text{ with }a\le x<b.(9) For a receiving layer DD on a text BB with shift qq, a shifted interval record of a text AA is a triple (o,a,b)∈ℤ3(o,a,b)\in\mathbb Z^3 satisfying (10).✦ The integer oo is the offset, and a,ba,b are the interval endpoints. fD(a+o)≤b+o≤ℓD(a+o),A≡[a,b)(x↦B(x+o)).f_D(a+o)\le b+o\le\ell_D(a+o),\qquad A\equiv_{[a,b)}\bigl(x\mapsto B(x+o)\bigr).(10)✦

What Is Checked

The layer and record definitions in (4) and (10) range over arbitrary alphabets and word sets, with integer-indexed texts and natural shifts, and the threading definition (3) permits an arbitrary index set.