OctoInformBeta

OpenAI preprint, September 2026 · §6. Opening cycles of planned links · §6

Theorem 6.3: The count bound gives common superstrings of symbol length at most 2W2W, where WW is the total forced letter count

Planned layer connections give bounded tours.

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 vertices are finite words, and the construction seeks a closed walk from the empty word that visits prescribed periodic layers. Connection plans assign budgets to blocks of layers and specify the overlaps at which they can meet.

Let α\alpha be an alphabet and ε\varepsilon the empty word. Write s⊑ts\sqsubseteq t when ss is a contiguous substring of tt, allowing s=εs=\varepsilon. A substring-closed vertex set V⊆α*V\subseteq\alpha^* contains every substring of each of its words.✦ A hierarchical walk in VV consists of stationary walks, steps appending one symbol, steps deleting the first symbol, and concatenations of such walks; all vertices belong to VV.✦ The cost c(P)c(P) of a hierarchical walk PP in VV is its number of appended symbols, and its visited set 𝒱(P)\mathcal V(P) is the set of its actual vertices, including the endpoints. Costs add under concatenation, whose visited set is the union of the constituent visited sets. A based closed walk is a hierarchical walk from a chosen base to itself, with the same cost and visitation conventions.✦

Periodic Layers

For an integer-indexed text A:ℤ→αA:\mathbb Z\to\alpha, its finite window A[a,b)A[a,b) lists its symbols at positions in [a,b)[a,b), and is empty when b≤ab\le a.✦ A periodic layer LL for VV, AA and a parameter p∈ℕp\in\mathbb N is a nondecreasing exit function zL:ℤ→ℤz_L:\mathbb Z\to\mathbb Z with the conditions in (1).✦ Its first and last exit positions are fLf_L and ℓL\ell_L; its base layer vertices form KLK_L: fL(x)=zL(x−1),ℓL(x)=zL(x),x≤fL(x),zL(x+p)=zL(x)+p,KL={A[x,e):x∈ℤ,fL(x)≤e≤ℓL(x)}⊆V.\begin{gathered} f_L(x)=z_L(x-1),\qquad \ell_L(x)=z_L(x),\qquad x\le f_L(x),\qquad z_L(x+p)=z_L(x)+p,\\ K_L=\{A[x,e):x\in\mathbb Z,\ f_L(x)\le e\le\ell_L(x)\} \subseteq V. \end{gathered}(1)

An ordered layer collection CC has groups g∈Gg\in G, each with a text AgA_g, a positive period pgp_g and a positive number ngn_g of layers Lg,jL_{g,j}, 0≤j<ng0\le j<n_g. The text satisfies Ag(x+pg)=Ag(x)A_g(x+p_g)=A_g(x), and the exit functions zg,jz_{g,j} of the layers Lg,jL_{g,j} satisfy zg,i(x)≤zg,j(x)z_{g,i}(x)\le z_{g,j}(x) whenever i≤ji\le j. Distinct groups have texts that differ at some position under every integer shift. A grouped layer index is a pair i=(g,j)i=(g,j); write Li=Lg,jL_i=L_{g,j} and Ki=KLiK_i=K_{L_i}.

For a linearly ordered alphabet, the forward rotation stream of AA at phase tt is (A(t+n))n≥0(A(t+n))_{n\ge0}, ordered lexicographically.✦ A greatest rotation phase tgt_g of a group gg is an integer phase at which the forward rotation stream of AgA_g is lexicographically greatest.✦ The greatest rotation rank rgr_g of a group gg is the forward rotation stream of AgA_g beginning at a greatest rotation phase tgt_g.✦

A shifted layer record of a text AA in a layer DD with text BB is a triple (δ,a,b)∈ℤ3(\delta,a,b)\in\mathbb Z^3 satisfying (2).✦ The second condition is interval agreement of AA with the shifted text on [a,b)[a,b): fD(a+δ)≤b+δ≤ℓD(a+δ),A(x)=B(x+δ)(a≤x<b).f_D(a+\delta)\le b+\delta\le\ell_D(a+\delta),\qquad A(x)=B(x+\delta)\quad(a\le x<b).(2) A shifted layer record (δ,a,b)(\delta,a,b) of a text AA in a layer DD with text BB is foreign when AA and BB disagree at some integer position after shifting BB by δ\delta. The recorded window of a shifted layer record (δ,a,b)(\delta,a,b) of a text AA is the word A[a,b)A[a,b).

For an exit family z0,…,zm−1z_0,\ldots,z_{m-1}, threshold H∈ℤH\in\mathbb Z and p,k∈ℕp,k\in\mathbb N, the set J(z;H,p,k)J(z;H,p,k) of qualifying layer indices is given by (3): J(z;H,p,k)={j:0≤j<m,H−kp≤zj}.J(z;H,p,k)=\{j:0\le j<m,\ H-kp\le z_j\}.(3) For a layer Lg,jL_{g,j}, write fg,j=fLg,jf_{g,j}=f_{L_{g,j}} and ℓg,j=ℓLg,j\ell_{g,j}=\ell_{L_{g,j}}. Foreign record supply for an ordered layer collection CC is the property that, for every g,j,tg,j,t and positive kk with t+kpg<fg,j(t)t+kp_g<f_{g,j}(t) and |J((ℓg,l(t))l<ng;fg,j(t),pg,k)|≤k|J((\ell_{g,l}(t))_{l<n_g};f_{g,j}(t),p_g,k)|\le k, there is a foreign record (δ,a,b)(\delta,a,b) of AgA_g in some layer LdL_d with a≤ta\le t and b≥fg,j(t)−kpgb\ge f_{g,j}(t)-kp_g.✦

Connection Plans

A block connection plan indexed by β\beta assigns to each i∈βi\in\beta a content set Ki⊆α*K_i\subseteq\alpha^*, nonnegative integer reserve RiR_i and free allowance FiF_i, an ordered rank rir_i, an optional target τi\tau_i, and a recorded word viv_i. A specified target τi=j\tau_i=j requires vi∈Kjv_i\in K_j. For each ii there is a based closed walk through Ki∪{vi}K_i\cup\{v_i\} of cost at most RiR_i, and a based closed walk through KiK_i whose cost plus FiF_i is at most RiR_i. When τi=j≠i\tau_i=j\ne i and rj≤rir_j\le r_i, there is a based closed walk of cost at most RiR_i through Ki∪{vi}K_i\cup\{v_i\} that visits a word of length at most FjF_j. A self-target requires a word in KiK_i of length at most FiF_i.

An outgoing layer plan BB for CC over a linearly ordered alphabet chooses a source group ss, a nonempty finite set MBM_B of layers in that group, a target layer d=(h,j)d=(h,j), and a foreign record (δ,a,b)(\delta,a,b) of AsA_s in LdL_d. Its content, recorded word and reserve are given in (4); the reserve includes base turns and connections: KB=⋃i∈MBKi,vB=As[a,b),RB=2|MB|ps.K_B=\bigcup_{i\in M_B}K_i,\qquad v_B=A_s[a,b),\qquad R_B=2|M_B|p_s.(4) The plan requires a link walk PlinkP_{\mathrm{link}} and an internal walk PintP_{\mathrm{int}}, both based closed walks, satisfying (5). When rh≤rsr_h\le r_s, it also requires a based closed walk PshortP_{\mathrm{short}} satisfying its final two lines: c(Plink)≤RB,KB∪{vB}⊆𝒱(Plink),c(Pint)+ps≤RB,KB⊆𝒱(Pint),c(Pshort)≤RB,KB∪{vB}⊆𝒱(Pshort),∃w∈𝒱(Pshort),|w|≤ph.\begin{aligned} c(P_{\mathrm{link}})&\le R_B, &K_B\cup\{v_B\}&\subseteq\mathcal V(P_{\mathrm{link}}),\\ c(P_{\mathrm{int}})+p_s&\le R_B, &K_B&\subseteq\mathcal V(P_{\mathrm{int}}),\\ c(P_{\mathrm{short}})&\le R_B, &K_B\cup\{v_B\}&\subseteq\mathcal V(P_{\mathrm{short}}),\\ &&\exists w\in\mathcal V(P_{\mathrm{short}}),\ |w|&\le p_h. \end{aligned}(5)

Count Data

A finite count instance D=(VD,SD,ΣD)D=(V_D,S_D,\Sigma_D) consists of finite sets of substring vertices, required words and alphabet symbols.✦ A finite count instance D=(VD,SD,ΣD)D=(V_D,S_D,\Sigma_D) is valid when ε∈VD\varepsilon\in V_D, VDV_D is substring-closed, and every symbol of every word in VDV_D lies in ΣD\Sigma_D.✦ The count iteration of a finite count instance DD is the sequence of count assignments that starts at zero and repeatedly applies the count recursion operator ΦD\Phi_D.✦ The maximum vertex length hh, forced occurrence count m(s)m(s) and total forced letter count WW are defined in (6); lengths count symbols: m0(s)=0,mn+1=ΦD(mn),h=max⁡({0}∪{|s|:s∈VD}),m(s)=mh+1(s),W=∑c∈ΣDm([c]).\begin{gathered} m_0(s)=0,\qquad m_{n+1}=\Phi_D(m_n),\qquad h=\max\bigl(\{0\}\cup\{|s|:s\in V_D\}\bigr),\\ m(s)=m_{h+1}(s),\qquad W=\sum_{c\in\Sigma_D}m([c]). \end{gathered}(6) Here [c][c] denotes the one-letter word with symbol cc.

The Claim

Theorem 1. Let VV be substring-closed. For a block connection plan, let I⊆βI\subseteq\beta be finite and let PP be a walk from ε\varepsilon to ε\varepsilon. Suppose each i∈Ii\in I either has its target in II or has vi∈𝒱(P)v_i\in\mathcal V(P), with the latter condition required when its target is absent. There is a walk QQ from ε\varepsilon to ε\varepsilon satisfying (7): c(Q)≤c(P)+∑i∈IRi,𝒱(P)∪⋃i∈IKi⊆𝒱(Q).c(Q)\le c(P)+\sum_{i\in I}R_i,\qquad \mathcal V(P)\cup\bigcup_{i\in I}K_i\subseteq\mathcal V(Q).(7)✦

For an ordered layer collection CC over a linearly ordered alphabet, let ℐ\mathcal I be a finite set of outgoing layer plans and let PP be a walk from ε\varepsilon to ε\varepsilon. Suppose each layer either has all its vertices in 𝒱(P)\mathcal V(P) or belongs to a member set MBM_B for some B∈ℐB\in\mathcal I. There is a walk QQ from ε\varepsilon to ε\varepsilon satisfying (8): c(Q)≤c(P)+∑B∈ℐRB,𝒱(P)∪⋃iKi⊆𝒱(Q).c(Q)\le c(P)+\sum_{B\in\mathcal I}R_B,\qquad \mathcal V(P)\cup\bigcup_{i}K_i\subseteq\mathcal V(Q).(8)✦

Suppose CC has finitely many groups, ε∈V\varepsilon\in V, and foreign record supply holds. There is a walk QQ from ε\varepsilon to ε\varepsilon satisfying (9): c(Q)≤2∑g∈Gngpg,⋃iKi⊆𝒱(Q).c(Q)\le 2\sum_{g\in G}n_gp_g,\qquad \bigcup_i K_i\subseteq\mathcal V(Q).(9)✦

Let DD be a valid finite count instance whose required words are nonempty vertices. There is a word TT satisfying (10): |T|≤2W,s⊑Tfor every s∈SD.|T|\le 2W,\qquad s\sqsubseteq T\quad\text{for every }s\in S_D.(10)✦

In the paper, the result reads: the base graph can be connected to ε\varepsilon by adding closed walks of total up cost at most WW.

What Is Checked

The claims are stated over substring-closed hierarchical graphs with the specified connection plans or foreign record supply, and over valid finite count instances whose required words are nonempty vertices.