OctoInformBeta

OpenAI preprint, September 2026 · Section 5. Rare matched walks and continuation records

Section 5 (setting): compatibility, matched walks, records and exceptional states: Compatibility and transitions on metric block states determine bounded records along reduced graph walks

Continuation records define exceptional directions.

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 Lipschitz-free space construction compares finite families of metric block points with walks in a colored graph.

A graph with reversible ports on a vertex set XX and port set PP consists of a reversal e↦e‾e\mapsto\bar e and a move map (x,e)↦x⋅e(x,e)\mapsto x\cdot e satisfying the laws in (1): e‾¯=e,(x⋅e)⋅e‾=x.\overline{\bar e}=e, \qquad (x\cdot e)\cdot\bar e=x.(1)✦ A port word ww is a finite list of elements of PP; write |w||w| for its length and ewew for the word obtained by placing ee before ww. The endpoint W(x,w)W(x,w) of a port word ww from a vertex x∈Xx\in X is the vertex defined by (2): W(x,⌀)=x,W(x,ew)=W(x⋅e,w).W(x,\varnothing)=x, \qquad W(x,ew)=W(x\cdot e,w).(2)✦ For w=(e1,…,em)w=(e_1,\ldots,e_m), put xt=W(x,(e1,…,et))x_t=W(x,(e_1,\ldots,e_t)) for 0≤t≤m0\le t\le m. A reduced port word ww over PP is a word in which successive ports e,fe,f satisfy f≠e‾f\ne\bar e.✦

Metric Block Labels

Let CC be a color set, let c:X→Cc:X\to C be a coloring, and let DD be a nonnegative integer cap. The truncated distance from xx to color ii is the integer ℓi(x)\ell_i(x) in (3): ℓi(x)=min⁡({D}∪{|w|:w is a port word and c(W(x,w))=i}).\ell_i(x)=\min\Bigl(\{D\}\cup \{|w|:w\text{ is a port word and }c(W(x,w))=i\}\Bigr).(3)✦ A box label bb is a vector in B={0,…,D}CB=\{0,\ldots,D\}^{C}. The vertex distance profile hX:X→Bh_X:X\to B and the set AA of realized label anchors are defined in (4): hX(x)i=ℓi(x),A=hX(X)⊆B.h_X(x)_i=\ell_i(x), \qquad A=h_X(X)\subseteq B.(4) For a nonnegative attachment scale RR, the graph with label anchors has the point set MM and block label map h:M→Bh:M\to B in (5): M=X⊔A,h(x)=hX(x)(x∈X),h(a)=a(a∈A).M=X\sqcup A, \qquad h(x)=h_X(x)\quad(x\in X), \qquad h(a)=a\quad(a\in A).(5) Write (M,d,o)(M,d,o) for the pointed metric block and ∥⋅∥∞\|\cdot\|_\infty for the supremum norm on its labels.

The Definition

Definition 1. Let K,LK,L be nonnegative integers. A block state j∈Mj\in M is compatible with a vertex x∈Xx\in X when the relation 𝒞blk\mathcal C_{\mathrm{blk}} in (6) holds: 𝒞blk(x,j)⇔∥hX(x)−h(j)∥∞≤K+2L+1.\mathcal C_{\mathrm{blk}}(x,j) \quad\Longleftrightarrow\quad \|h_X(x)-h(j)\|_\infty\le K+2L+1.(6)✦ A transition between block states j,k∈Mj,k\in M is a pair satisfying the relation 𝒯blk\mathcal T_{\mathrm{blk}} in (7): 𝒯blk(j,k)⇔d(j,k)≤2L.\mathcal T_{\mathrm{blk}}(j,k) \quad\Longleftrightarrow\quad d(j,k)\le 2L.(7)✦

More generally, let Σ\Sigma be a state set with relations 𝒞⊆X×Σ\mathcal C\subseteq X\times\Sigma and 𝒯⊆Σ×Σ\mathcal T\subseteq\Sigma\times\Sigma. A matched walk from (x,j)∈X×Σ(x,j)\in X\times\Sigma is a word w=(e1,…,em)w=(e_1,\ldots,e_m) admitting states as in (8), where xtx_t denotes its successive vertices: Matched⁡(x,j,w)⇔there exist j0,…,jm∈Σ with j0=j,𝒞(xt,jt)(0≤t≤m),𝒯(jt−1,jt)(1≤t≤m).\begin{split} \operatorname{Matched}(x,j,w)\quad\Longleftrightarrow\quad &\text{there exist }j_0,\ldots,j_m\in\Sigma\text{ with }j_0=j,\\ &\mathcal C(x_t,j_t)\quad(0\le t\le m),\\ &\mathcal T(j_{t-1},j_t)\quad(1\le t\le m). \end{split}(8)✦ For a nonnegative integer nn, an nn-good vertex is a vertex x∈Xx\in X with no matched reduced word of length nn, as specified by (9): x∈𝒢n⇔{w:|w|=n,w is reduced,∃j∈ΣMatched⁡(x,j,w)}=⌀.x\in\mathcal G_n\quad\Longleftrightarrow\quad \{w:|w|=n,\ w\text{ is reduced},\ \exists j\in\Sigma\ \operatorname{Matched}(x,j,w)\}=\varnothing.(9)✦

The attainable continuation lengths through e∈Pe\in P at (x,j)∈X×Σ(x,j)\in X\times\Sigma form the set ℒ(x,e,j)\mathcal L(x,e,j) in (10): ℒ(x,e,j)={0}∪{1+|w|:ew is reduced and Matched⁡(x,j,ew)}.\mathcal L(x,e,j)=\{0\}\cup \{1+|w|:ew\text{ is reduced and }\operatorname{Matched}(x,j,ew)\}.(10)✦ The continuation record through ee at (x,j)(x,j), bounded by nn, is the integer rx(e,j)r_x(e,j) in (11): rx(e,j)=max⁡(ℒ(x,e,j)∩{0,…,n}).r_x(e,j)=\max\bigl(\mathcal L(x,e,j)\cap\{0,\ldots,n\}\bigr).(11)✦ For any function ρ:P×Σ→ℕ\rho:P\times\Sigma\to\mathbb N, an exceptional direction at j∈Σj\in\Sigma is a port e∈Pe\in P satisfying (12): Exc⁡ρ(e,j)⇔ρ(g,j)<ρ(e,j)for every g∈P\{e}.\operatorname{Exc}_{\rho}(e,j)\quad\Longleftrightarrow\quad \rho(g,j)<\rho(e,j)\quad\text{for every }g\in P\setminus\{e\}.(12)✦

For a finite S⊆MS\subseteq M, take Σ=S\Sigma=S and restrict the relations in (6) and (7) to SS. The exceptional state set for the port ee at xx is the subset Ex,eE_{x,e} of SS defined by (13): Ex,e={j∈S:x∉𝒢n or Exc⁡rx(e,j)}.E_{x,e}=\{j\in S:x\notin\mathcal G_n \text{ or }\operatorname{Exc}_{r_x}(e,j)\}.(13)✦

In the paper, the result reads: fix a finite S⊆MS\subseteq M containing oo, take compatibility to mean ∥h(x)−h(j)∥∞≤K+2L+1=D−4\|h(x)-h(j)\|_\infty\le K+2L+1=D-4 and transitions to mean d(j,j′)≤2Ld(j,j')\le2L, call a nonbacktracking walk matched when its states are compatible at every vertex and make a transition at every step, and, for n≥2n\ge2, call a vertex good when no such walk of length nn starts there, set rx(e,j)r_x(e,j) at a good vertex equal to the maximum of zero and all positive lengths of such walks beginning through ee at initial state jj, declare an incidence exceptional for jj when its record strictly exceeds every other outgoing record and every incidence exceptional at a bad vertex, and let Ex,eE_{x,e} be the states exceptional for ee.

What Is Checked

The definitions are stated over a graph with reversible ports and arbitrary state relations, with (13) specialized to finite state sets in the metric block.