OctoInformBeta

OpenAI preprint, September 2026 · §5. Processing the period groups · §5

Proposition 5.2: Local plans and pending requests support a global walk that visits every layer vertex

Period groups admit coverage within reserve.

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

Processing periodic layers in the hierarchical graph assigns the cost of visiting their windows to group budgets. A link to another layer may be planned before its connecting walk is executed.

Let VV be a set of finite words over a linearly ordered alphabet α\alpha. A substring-closed set VV contains every contiguous substring of each of its words, including the empty word.✦ A hierarchical walk PP on VV is a walk with vertices in VV, with up steps appending one symbol and down steps deleting the first symbol; walks concatenate at a common endpoint and may be stationary.✦ Write v(P)v(P) for the actual vertices visited by PP, including its endpoints, and c(P)c(P) for its number of up steps. Costs add under concatenation. A based closed walk starts and ends at a chosen vertex; its visitation and cost are those of its underlying walk. A rooted walk starts and ends at the empty word ε\varepsilon.

For an integer-indexed text AA, let A[a,b)A[a,b) be its finite window on the half-open interval [a,b)[a,b), with the empty word when b<ab<a.✦ A periodic layer of AA with period parameter pp is a nondecreasing integer-valued exit function zz satisfying the bounds and shift rule in (1), with first and last exit positions ff and ℓ\ell and set 𝒱\mathcal V of actual layer vertices as given there. x≤z(x−1),z(x+p)=z(x)+p,f(x)=z(x−1),ℓ(x)=z(x),𝒱={A[x,e):x,e∈ℤ,f(x)≤e≤ℓ(x)}⊆V.\begin{aligned} x&\le z(x-1), & z(x+p)&=z(x)+p, & f(x)&=z(x-1), & \ell(x)&=z(x),\\ \mathcal V&=\{A[x,e):x,e\in\mathbb Z,\ f(x)\le e\le\ell(x)\} \subseteq V. \end{aligned}(1) A walk touches a layer when its visited vertices intersect 𝒱\mathcal V.✦

An ordered layer collection 𝒞\mathcal C has a set GG of groups and assigns to each group g∈Gg\in G a text AgA_g with a positive period pgp_g, a positive number ngn_g of layers, and layers Dg,jD_{g,j} for 0≤j<ng0\le j<n_g. The period need not be the least positive period. For i≤ji\le j, their exit functions satisfy zg,i(x)≤zg,j(x)z_{g,i}(x)\le z_{g,j}(x) at every integer xx. Distinct groups have texts that differ at some position after every integer shift. A grouped layer index d=(g,j)d=(g,j) of 𝒞\mathcal C is a pair consisting of a group and a layer index in that group; write γ(d)=g\gamma(d)=g, Dd=Dg,jD_d=D_{g,j} and 𝒱d\mathcal V_d for its layer vertices. For a set JJ of indices in group gg, put Mg(J)={(g,j):j∈J}M_g(J)=\{(g,j):j\in J\}, and for any set MM of grouped indices put 𝒱(M)=⋃d∈M𝒱d\mathcal V(M)=\bigcup_{d\in M}\mathcal V_d.

The forward rotation stream of AgA_g at phase tt is (Ag(t+n))n≥0(A_g(t+n))_{n\ge0}, ordered lexicographically.✦ A greatest rotation phase tgt_g is a phase whose stream is greatest among all integer phases.✦ The greatest rotation rank ρg\rho_g is the stream at tgt_g.✦

Records and Reserves

A shifted layer record R=(a,b,δ)R=(a,b,\delta) from group gg to a layer dd is an interval and an integer shift satisfying (2).✦ fd(a+δ)≤b+δ≤ℓd(a+δ),Ag(x)=Aγ(d)(x+δ)(a≤x<b).f_d(a+\delta)\le b+\delta\le\ell_d(a+\delta), \qquad A_g(x)=A_{\gamma(d)}(x+\delta)\quad(a\le x<b).(2) A shifted layer record R=(a,b,δ)R=(a,b,\delta) from group gg to layer dd is foreign when there is an integer xx with Ag(x)≠Aγ(d)(x+δ)A_g(x)\ne A_{\gamma(d)}(x+\delta).

A child request at a layer dd consists of a source group gg, a nonempty finite set JJ of its layer indices and a foreign record R=(a,b,δ)R=(a,b,\delta) to dd, with the margins in (3).✦ A pending request rr is a child request at a layer dd with its target τ(r)=d\tau(r)=d specified.✦ For a pending request rr from group gg with layer index set JJ, its source is s(r)=gs(r)=g, its member indices are M(r)=Mg(J)M(r)=M_g(J), and its period budget and reserve are β(r)\beta(r) and σ(r)\sigma(r) in (3). a+pg<fg,j(a),ℓg,j(a)<b−pg(j∈J),β(r)=|J|pg,σ(r)=2β(r).\begin{aligned} a+p_g&<f_{g,j}(a), & \ell_{g,j}(a)&<b-p_g &&(j\in J),\\ \beta(r)&=|J|p_g, & \sigma(r)&=2\beta(r). \end{aligned}(3)

Write 𝒫(𝒞)\mathscr P(\mathcal C) for the set of outgoing plans for the ordered layer collection 𝒞\mathcal C. An outgoing plan Π∈𝒫(𝒞)\Pi\in\mathscr P(\mathcal C) consists of a source s(Π)=gs(\Pi)=g, a nonempty finite member set M(Π)M(\Pi) of layers of gg, a target τ(Π)=d\tau(\Pi)=d and a foreign record RΠ=(a,b,δ)R_\Pi=(a,b,\delta) to dd. Put k=|M(Π)|k=|M(\Pi)| and p=pgp=p_g. Its reserve σ(Π)=2kp\sigma(\Pi)=2kp pays for base turns and connections.✦ The plan requires the closed walks in (4), where wR=Ag[a,b)w_R=A_g[a,b); the walks in the different requirements may be different. ∃L:c(L)≤2kp,𝒱(M(Π))∪{wR}⊆v(L),∃U:c(U)+p≤2kp,𝒱(M(Π))⊆v(U),ργ(d)≤ρg⇒∃S:c(S)≤2kp,𝒱(M(Π))∪{wR}⊆v(S),∃w∈v(S),|w|≤pγ(d).\begin{aligned} &\exists L:\quad c(L)\le2kp,\qquad \mathcal V(M(\Pi))\cup\{w_R\}\subseteq v(L),\\ &\exists U:\quad c(U)+p\le2kp,\qquad \mathcal V(M(\Pi))\subseteq v(U),\\ &\rho_{\gamma(d)}\le\rho_g\ \Longrightarrow\ \exists S:\quad c(S)\le2kp,\quad \mathcal V(M(\Pi))\cup\{w_R\}\subseteq v(S),\quad \exists w\in v(S),\ |w|\le p_{\gamma(d)}. \end{aligned}(4)

For a rooted walk PP, a finite family ℬ\mathcal B of outgoing plans and a finite family ℛ\mathcal R of pending requests, layer coverage Cov⁡(P,ℬ,ℛ;d)\operatorname{Cov}(P,\mathcal B,\mathcal R;d) of an index dd is the condition in (5). Cov⁡(P,ℬ,ℛ;d)⇔𝒱d⊆v(P)∨∃Π∈ℬ,d∈M(Π)∨∃r∈ℛ,d∈M(r).\operatorname{Cov}(P,\mathcal B,\mathcal R;d) \quad\Longleftrightarrow\quad \mathcal V_d\subseteq v(P) \ \lor\ \exists\Pi\in\mathcal B,\ d\in M(\Pi) \ \lor\ \exists r\in\mathcal R,\ d\in M(r).(5)✦

For a finite family of exit positions zjz_j, a threshold HH and nonnegative integers p,kp,k, the qualifying indices are 𝒬(z,H;p,k)={j:H−kp≤zj}\mathcal Q(z,H;p,k)=\{j:H-kp\le z_j\}.✦ An ordered layer collection 𝒞\mathcal C has foreign record supply if the following condition holds for every g,j,tg,j,t and positive kk: when t+kpg<fg,j(t)t+kp_g<f_{g,j}(t) and |𝒬((ℓg,l(t))l,fg,j(t);pg,k)|≤k|\mathcal Q((\ell_{g,l}(t))_l,f_{g,j}(t);p_g,k)|\le k, there is a foreign record R=(a,b,δ)R=(a,b,\delta) to some layer dd with the endpoints in (6). a≤t,fg,j(t)−kpg≤b.a\le t,\qquad f_{g,j}(t)-kp_g\le b.(6)✦

The Claim

Theorem 1. Let 𝒞\mathcal C be an ordered layer collection on a substring-closed vertex set VV over a linearly ordered alphabet.

Suppose 𝒞\mathcal C has foreign record supply. Fix a group gg and a finite family ℛ\mathcal R of pending requests whose targets belong to gg and whose sources are pairwise distinct. There are a rooted walk QQ, a finite family ℬ\mathcal B of outgoing plans and a finite family 𝒪\mathcal O of pending requests satisfying (7). c(Q)+∑Π∈ℬσ(Π)+∑r∈𝒪σ(r)≤2ngpg+∑r∈ℛσ(r),Cov⁡(Q,ℬ,𝒪;(g,j))(0≤j<ng),𝒱(⋃r∈ℛM(r))⊆v(Q),s(r)=g(r∈𝒪),|𝒪|≤1.\begin{aligned} c(Q)+\sum_{\Pi\in\mathcal B}\sigma(\Pi) +\sum_{r\in\mathcal O}\sigma(r) &\le 2n_gp_g+\sum_{r\in\mathcal R}\sigma(r),\\ \operatorname{Cov}(Q,\mathcal B,\mathcal O;(g,j)) &\qquad(0\le j<n_g),\\ \mathcal V\!\left(\bigcup_{r\in\mathcal R}M(r)\right) &\subseteq v(Q),\\ s(r)&=g\quad(r\in\mathcal O),\qquad |\mathcal O|\le1. \end{aligned}(7)✦

Suppose 𝒞\mathcal C has foreign record supply. Let I⊆GI\subseteq G be finite and upward closed under strictly larger periods: for g∈Ig\in I and pg<php_g<p_h, also h∈Ih\in I. Let PP be a rooted walk, ℬ\mathcal B a finite family of outgoing plans and ℛ\mathcal R a finite family of pending requests. Assume that each request targets a group in II, has its source outside II, and has a source different from every other request’s source. Assume every layer dd whose group is outside II satisfies Cov⁡(P,ℬ,ℛ;d)\operatorname{Cov}(P,\mathcal B,\mathcal R;d). There is a rooted walk QQ satisfying (8). c(Q)≤c(P)+∑Π∈ℬσ(Π)+∑r∈ℛσ(r)+∑g∈I2ngpg,v(P)⊆v(Q),⋃d𝒱d⊆v(Q).\begin{aligned} c(Q)&\le c(P)+\sum_{\Pi\in\mathcal B}\sigma(\Pi) +\sum_{r\in\mathcal R}\sigma(r)+\sum_{g\in I}2n_gp_g,\\ v(P)&\subseteq v(Q),\qquad \bigcup_d\mathcal V_d\subseteq v(Q). \end{aligned}(8)✦

Let JJ be a nonempty finite set of indices in group gg, with l=min⁡Jl=\min J, h=max⁡Jh=\max J and k=|J|k=|J|. Let R=(a,b,δ)R=(a,b,\delta) be a foreign record to dd with a≤tg<ba\le t_g<b. Suppose the sharp-band inequality fg,h(tg)−ℓg,l(tg)≤(k−1)pgf_{g,h}(t_g)-\ell_{g,l}(t_g)\le(k-1)p_g holds, together with fg,h(tg)≤b+kpgf_{g,h}(t_g)\le b+kp_g and b≤ℓg,l(a)+kpgb\le\ell_{g,l}(a)+kp_g. There is a collective outgoing plan with source gg, member set Mg(J)M_g(J), target dd and record RR, as in (9). Πcollective(g,J,l,h,d,R)∈𝒫(𝒞).\Pi_{\mathrm{collective}}(g,J,l,h,d,R)\in\mathscr P(\mathcal C).(9)✦

Let ii be a layer index in group gg and R=(a,b,δ)R=(a,b,\delta) a foreign record to dd. Suppose fg,i(a)≤b≤ℓg,i(a)+pgf_{g,i}(a)\le b\le\ell_{g,i}(a)+p_g. There is an individual outgoing plan with source gg, the single member layer (g,i)(g,i), target dd and record RR, as in (10). Πindividual(g,i,d,R)∈𝒫(𝒞).\Pi_{\mathrm{individual}}(g,i,d,R)\in\mathscr P(\mathcal C).(10)✦

In the paper, the result reads: after all groups are processed, every layer is marked rooted or belongs to exactly one outgoing block, disjointly, each block comes from one primitive-text group, targets a single actual layer and retains its total budget for its planned link, collective blocks of kk layers and period pp satisfy the sharp-band inequality at their distinguished position, and individual blocks contain one layer.

What Is Checked

The statements concern ordered periodic layers and their actual windows, shifted records, hierarchical walks and finite families of plans and requests; the group-processing and scheduling bounds assume foreign record supply.