OctoInformBeta

OpenAI preprint, September 2026 · §4. Connection operations · §4

Lemma 4.3: Three endpoint inequalities give a closed hierarchical walk of prescribed cost

Linking bounded layers through a text window.

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

A collective connection asks for a closed walk based at a specified text window that meets each layer in a family. The cost counts the symbols appended along the walk.✦

Let α\alpha be an alphabet and A:ℤ→αA:\mathbb Z\to\alpha an integer-indexed text. For integers a,ba,b, the finite text window A[a,b)A[a,b) of the integer-indexed text AA is the word on the half-open interval [a,b)[a,b), with the empty word when b≤ab\le a.✦ A substring-closed set VV of words over α\alpha is a set containing every contiguous substring of each of its words, including the empty word.✦

A hierarchical walk PP in VV is a finite concatenation of steps that append a symbol at the end or delete the first symbol, with every vertex in VV; a stationary walk at any vertex of VV is also allowed.✦ Write cost⁡(P)\operatorname{cost}(P) for the cost of PP. A walk visits a word when that word is an actual vertex of the walk, including either endpoint.✦

Fix a nonnegative integer pp. A periodic layer DD for VV, AA and pp is a nondecreasing function zD:ℤ→ℤz_D:\mathbb Z\to\mathbb Z satisfying (1) for all integers x,ex,e: x≤zD(x−1),zD(x+p)=zD(x)+p,zD(x−1)≤e≤zD(x)⇒A[x,e)∈V.\begin{gathered} x\le z_D(x-1),\qquad z_D(x+p)=z_D(x)+p,\\ z_D(x-1)\le e\le z_D(x)\quad\Longrightarrow\quad A[x,e)\in V. \end{gathered}(1)✦ The first and last exit positions of DD at a start xx are the endpoints fD(x)f_D(x) and ℓD(x)\ell_D(x) defined in (2): fD(x)=zD(x−1),ℓD(x)=zD(x).f_D(x)=z_D(x-1),\qquad \ell_D(x)=z_D(x).(2) A hierarchical walk PP touches a layer DD when there are integers x,ex,e with fD(x)≤e≤ℓD(x)f_D(x)\le e\le\ell_D(x) such that PP visits the word A[x,e)A[x,e).✦

The Claim

Theorem 1 (Collective link). Suppose VV is substring-closed, contains every one-letter word A[x,x+1)A[x,x+1), and A(x+p)=A(x)A(x+p)=A(x) for every integer xx. Let kk be a nonnegative integer and (Li)i∈I(L_i)_{i\in I} a family of periodic layers for VV, AA and pp. Choose indices lo,hi∈I\mathrm{lo},\mathrm{hi}\in I such that zLlo(x)≤zLi(x)≤zLhi(x)z_{L_{\mathrm{lo}}}(x)\le z_{L_i}(x)\le z_{L_{\mathrm{hi}}}(x) for every i∈Ii\in I and integer xx. Let a≤ba\le b be integers with R=A[a,b)∈VR=A[a,b)\in V, and assume the endpoint bounds (3): fLhi(a)≤b+kp,fLhi(a)−ℓLlo(a)≤kp,b≤ℓLlo(a)+kp.\begin{aligned} f_{L_{\mathrm{hi}}}(a)&\le b+kp,\\ f_{L_{\mathrm{hi}}}(a)-\ell_{L_{\mathrm{lo}}}(a)&\le kp,\\ b&\le\ell_{L_{\mathrm{lo}}}(a)+kp. \end{aligned}(3) Then there is a closed hierarchical walk PP based at RR satisfying (4): cost⁡(P)=kp,P touches Li for every i∈I.\operatorname{cost}(P)=kp,\qquad P\text{ touches }L_i\text{ for every }i\in I.(4)✦

What Is Checked

The claim is stated over hierarchical walks in a substring-closed word set containing every letter of the periodic text, and an arbitrary indexed family of layers with pointwise lower and upper members.