OctoInformBeta

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

Lemma 4.4: A closed walk touching the host and each interior requester, with cost bounded by their periods

Connecting periodic layers through recorded windows.

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 host layer and its child layers describe windows from different periodic texts. The connection problem asks for a closed hierarchical walk that visits a window of each layer.

Let α\alpha be an alphabet and let VV be a set of finite words over α\alpha. A substring-closed vertex set VV over α\alpha is a set of finite words over α\alpha that contains every contiguous substring of each of its words, including the empty word ϵ\epsilon.✦ For an integer-indexed text A:ℤ→αA\colon\mathbb Z\to\alpha, write A[a,b)A[a,b) for the finite word read on the half-open interval [a,b)[a,b); this word is empty when b≤ab\le a.✦ A positive period of AA is an integer p>0p>0 such that A(x+p)=A(x)A(x+p)=A(x) for every integer xx; it need not be the least positive period.

A hierarchical walk PP in VV is a finite walk whose up steps append one symbol and whose down steps delete the first symbol, with the source and target of every step in VV.✦ A stationary walk at any word of VV is allowed, and walks with a common endpoint may be concatenated. A walk visits a word when that word is an actual vertex of the walk, including either endpoint.✦ The cost cost⁡(P)\operatorname{cost}(P) of a hierarchical walk PP in VV is the number of up steps in PP: stationary walks and down steps cost zero, and concatenation adds costs.✦

A periodic layer DD for VV, a text AA and a nonnegative integer period parameter pp is a nondecreasing function zD:ℤ→ℤz_D\colon\mathbb Z\to\mathbb Z satisfying x≤zD(x−1),zD(x+p)=zD(x)+p(x∈ℤ),A[x,e)∈Vwhenever zD(x−1)≤e≤zD(x).\begin{aligned} x&\le z_D(x-1), & z_D(x+p)&=z_D(x)+p &&(x\in\mathbb Z),\\ A[x,e)&\in V &&&\text{whenever }z_D(x-1)\le e\le z_D(x). \end{aligned}(1)✦ The first exit position first⁡D(x)\operatorname{first}_D(x) and last exit position last⁡D(x)\operatorname{last}_D(x) of a periodic layer DD at an integer xx are the integers defined by first⁡D(x)=zD(x−1),last⁡D(x)=zD(x).\operatorname{first}_D(x)=z_D(x-1),\qquad \operatorname{last}_D(x)=z_D(x).(2) A walk PP touches DD when it visits some word A[x,e)A[x,e) with ee between the two exit positions in (2), inclusively.✦

Recorded Windows and Requests

Two integer-indexed texts AA and BB have interval agreement on [a,b)[a,b) when A(x)=B(x)A(x)=B(x) for every integer xx with a≤x<ba\le x<b.✦ A recorded host window H=(B,p,a,b)H=(B,p,a,b) of a layer DD on AA consists of a text BB with positive period pp, distinct from AA, and integer endpoints satisfying (3): first⁡D(a)≤b≤last⁡D(a),A(x)=B(x)(a≤x<b).\operatorname{first}_D(a)\le b\le\operatorname{last}_D(a), \qquad A(x)=B(x)\quad(a\le x<b).(3)✦

A child layer request R=(E,c)R=(E,c) of H=(B,p,a,b)H=(B,p,a,b) consists of a periodic layer EE for VV, text BB and period parameter pp, with an integer endpoint cc satisfying the interior conditions in (4): first⁡E(a)≤c≤last⁡E(a),a+p<c,c≤b−p.\operatorname{first}_E(a)\le c\le\operatorname{last}_E(a), \qquad a+p<c,\qquad c\le b-p.(4)✦

For a family of recorded host windows Hj=(Bj,pj,aj,bj)H_j=(B_j,p_j,a_j,b_j) indexed by a set JJ, distinctness of the hosted texts modulo shifts means Bj≠(x↦Bk(x+t))(j≠k,t∈ℤ).B_j\ne\bigl(x\mapsto B_k(x+t)\bigr) \qquad(j\ne k,\ t\in\mathbb Z).(5)

A family of requests is indexed by a set KK, with a map g:K→Jg\colon K\to J assigning each request Ri=(Ei,ci)R_i=(E_i,c_i) to its recorded host window Hg(i)H_{g(i)}.

The Claim

Theorem 1. Let VV be substring-closed, let AA have positive period qq, and let DD be a periodic layer for VV, AA and qq. Let Hj=(Bj,pj,aj,bj)H_j=(B_j,p_j,a_j,b_j) be recorded host windows of DD whose texts satisfy (5), and let Ri=(Ei,ci)R_i=(E_i,c_i) be requests assigned by g:K→Jg\colon K\to J. Suppose that every one-letter word [A(x)][A(x)] and [Bj(x)][B_j(x)] belongs to VV. For every finite nonempty set I⊆KI\subseteq K, there is a hierarchical walk QQ from ϵ\epsilon to ϵ\epsilon such that cost⁡(Q)≤q+∑i∈Ipg(i),Q touches D,Q touches Eifor every i∈I.\operatorname{cost}(Q)\le q+\sum_{i\in I}p_{g(i)},\qquad Q\text{ touches }D,\qquad Q\text{ touches }E_i\ \text{for every }i\in I.(6)✦

What Is Checked

The claim (6) is stated over substring-closed word sets, periodic layers and their actual visited windows, recorded host windows with texts distinct modulo shifts, and finite nonempty families of interior child layer requests, with all one-letter words of the participating texts present.