OctoInformBeta

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

Lemma 4.2: Layers between two bounds can be joined at a cost controlled by a multiple of the period parameter

A bounded gap permits a band tour.

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 connection problem is to pass through a band of periodic layers while controlling the number of appended symbols. The relevant graph has finite words as vertices and allows a word to grow at its right end or shrink at its left end.

A substring-closed vertex set VV over an alphabet α\alpha is a set of finite words containing every contiguous substring of each of its words, including the empty word.✦ A hierarchical walk in VV is a finite sequence of steps between vertices of VV, each appending one symbol at the right or deleting the first symbol.✦ Stationary walks are allowed, and walks with a common endpoint can be concatenated. A walk visits a word when that word is an actual vertex of the walk, including either endpoint.✦

The cost c(P)c(P) of a hierarchical walk PP is its number of append steps.✦ Costs add under concatenation.

For an integer-indexed text A:ℤ→αA\colon\mathbb Z\to\alpha, the finite window A[a,b)A[a,b) is the word of symbols at positions a,a+1,…,b−1a,a+1,\ldots,b-1 when a<ba<b, and the empty word when b≤ab\le a.✦

A periodic layer DD for VV, AA and a parameter p∈ℕp\in\mathbb N is an integer-valued exit function zD:ℤ→ℤz_D\colon\mathbb Z\to\mathbb Z satisfying (1); all variables in these conditions are integers. x≤y⇒zD(x)≤zD(y),x≤zD(x−1),zD(x+p)=zD(x)+p,zD(x−1)≤e≤zD(x)⇒A[x,e)∈V.\begin{aligned} x\le y&\ \Longrightarrow\ z_D(x)\le z_D(y),\\ x&\le z_D(x-1),\\ z_D(x+p)&=z_D(x)+p,\\ z_D(x-1)\le e\le z_D(x)&\ \Longrightarrow\ A[x,e)\in V. \end{aligned}(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 walk PP touches a layer DD when it visits a window with endpoints satisfying (3). There exist x,e∈ℤ such that fD(x)≤e≤ℓD(x)and P visits A[x,e).\text{There exist }x,e\in\mathbb Z\text{ such that } f_D(x)\le e\le\ell_D(x) \quad\text{and }P\text{ visits }A[x,e).(3)✦

The Claim

Theorem 1. Let VV be substring-closed, and let A:ℤ→αA\colon\mathbb Z\to\alpha be a text whose one-letter words A[x,x+1)A[x,x+1) all belong to VV. Let p,k∈ℕp,k\in\mathbb N, and suppose A(x+p)=A(x)A(x+p)=A(x) for every integer xx.

Let (Di)i∈I(D_i)_{i\in I} be a family of periodic layers for VV, AA and pp, with designated bottom and top layers DloD_{\mathrm{lo}} and DhiD_{\mathrm{hi}}. Suppose every exit function zDiz_{D_i} lies pointwise between zDloz_{D_{\mathrm{lo}}} and zDhiz_{D_{\mathrm{hi}}}. Let t∈ℤt\in\mathbb Z satisfy fDhi(t)−ℓDlo(t)≤kpf_{D_{\mathrm{hi}}}(t)-\ell_{D_{\mathrm{lo}}}(t)\le kp.

There is a closed hierarchical walk PP based at A[t,ℓDlo(t))A[t,\ell_{D_{\mathrm{lo}}}(t)) with the band tour bound (4). c(P)≤kp,P touches Di for every i∈I.c(P)\le kp, \qquad P\text{ touches }D_i\text{ for every }i\in I.(4)✦

What Is Checked

The claim is stated over hierarchical walks in a substring-closed word set and a family of layers of an integer-indexed periodic text, bounded pointwise by two designated layers.