OctoInformBeta

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

Lemma 5.3: At a good vertex, a state is exceptional in at most one direction

Matched edges meet exceptional states.

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 metric blocks in the Lipschitz-free space construction carry finite sets of states. Compatibility constrains a state at a graph vertex, while a distance bound constrains successive states along a walk.

A graph with reversible ports on a vertex set XX and a port set EE consists of moves x↦x⋅ex\mapsto x\cdot e and a reversal e↦e‾e\mapsto\bar e satisfying (1): e‾¯=e,(x⋅e)⋅e‾=x.\overline{\bar e}=e, \qquad (x\cdot e)\cdot\bar e=x.(1)✦ The port walk endpoint x⋅wx\cdot w follows the entries of a finite port word ww in order; the empty word ends at xx.✦ A nonbacktracking port word ww over EE is a word in which every successive pair e,fe,f satisfies f≠e‾f\ne\bar e.✦

For a state set SS, fix a compatibility relation 𝖢⊆X×S\mathsf C\subseteq X\times S and a transition relation 𝖳⊆S×S\mathsf T\subseteq S\times S. A matched walk ww from (x,j)(x,j) in the graph on XX with state set SS is a port word accompanied by states at its successive vertices, starting with jj at xx, such that every state is compatible with its vertex and each successive pair of states belongs to 𝖳\mathsf T.✦ For a horizon n∈ℕn\in\mathbb N, a vertex xx of the graph is good, a condition denoted by 𝖦n(x)\mathsf G_n(x), if it admits no matched nonbacktracking walk of length nn, with any initial state.✦

The set 𝒜x,e,j\mathcal A_{x,e,j} of attainable continuation lengths from (x,j)(x,j) in direction ee consists of zero and the lengths of matched nonbacktracking words beginning with ee.✦ The continuation record rn,x(e,j)r_{n,x}(e,j) from (x,j)(x,j) in direction ee is the greatest element of 𝒜x,e,j\mathcal A_{x,e,j} at most nn, as in (2): 𝒜x,e,j={0}∪{|w|:w begins with e,w is nonbacktracking and matched from (x,j)},rn,x(e,j)=max⁡(𝒜x,e,j∩{0,…,n}).\begin{aligned} \mathcal A_{x,e,j} &=\{0\}\cup\bigl\{|w|:w\text{ begins with }e, \ w\text{ is nonbacktracking and matched from }(x,j)\bigr\},\\ r_{n,x}(e,j) &=\max\bigl(\mathcal A_{x,e,j}\cap\{0,\ldots,n\}\bigr). \end{aligned}(2)✦ For any array r:E×S→ℕr:E\times S\to\mathbb N, a direction ee is exceptional at a state jj if it is a strict maximizer of the records over directions; this condition is denoted by Exc⁡(r;e,j)\operatorname{Exc}(r;e,j) and defined by (3): Exc⁡(r;e,j)⇔r(f,j)<r(e,j)for every f∈E\{e}.\operatorname{Exc}(r;e,j) \quad\Longleftrightarrow\quad r(f,j)<r(e,j)\quad\text{for every }f\in E\setminus\{e\}.(3)✦

Metric States and Exceptional Sets

Fix a coloring c:X→Cc:X\to C and an integer cap D≥0D\geq0. The set BB of bounded color coordinate vectors for the color set CC and cap DD consists of the functions from CC to {0,…,D}\{0,\ldots,D\} and is equipped with the supremum norm.✦ The truncated distance ℓi(x)\ell_i(x) to color ii and the vertex distance profile bx∈Bb_x\in B are given by (4): ℓi(x)=min⁡({D}∪{|w|:c(x⋅w)=i}),bx(i)=ℓi(x).\ell_i(x)=\min\bigl(\{D\}\cup \{|w|:c(x\cdot w)=i\}\bigr), \qquad b_x(i)=\ell_i(x).(4)

A realized label anchor aa in BB is a vector in A={bx:x∈X}⊆BA=\{b_x:x\in X\}\subseteq B.✦ At attachment scale R∈ℕR\in\mathbb N, the graph with label anchors has point set M=X⊔AM=X\sqcup A, with its block metric dd.✦ The block label b:M→Bb:M\to B sends an original vertex xx to bxb_x and an anchor aa to its coordinate vector aa.✦

Fix parameters L,K∈ℕL,K\in\mathbb N and a finite state set S⊆MS\subseteq M. Label compatibility and the proximity transition relation are the relations in (5): 𝖢(x,j)⇔∥bx−b(j)∥∞≤K+2L+1,𝖳(j,k)⇔d(j,k)≤2L.\mathsf C(x,j)\ \Longleftrightarrow\ \|b_x-b(j)\|_\infty\leq K+2L+1, \qquad \mathsf T(j,k)\ \Longleftrightarrow\ d(j,k)\leq2L.(5) For the label compatibility and proximity transition relations in (5) and a fixed horizon nn, the exceptional state set Ee(x)E_e(x) in direction ee at xx is the subset of SS defined in (6): Ee(x)={j∈S:¬𝖦n(x)orExc⁡(rn,x;e,j)}.E_e(x)=\bigl\{j\in S: \neg\mathsf G_n(x)\ \text{or}\ \operatorname{Exc}(r_{n,x};e,j)\bigr\}.(6)✦

The Claim

Theorem 1. Let x∈Xx\in X, e∈Ee\in E and y=x⋅ey=x\cdot e. In the metric block, let j,k∈Sj,k\in S be compatible with x,yx,y, respectively, and suppose that d(j,k)≤2Ld(j,k)\leq2L. Then (7) holds: j∈Ee(x)ork∈Ee‾(y).j\in E_e(x)\quad\text{or}\quad k\in E_{\bar e}(y).(7)✦

For a reversible port graph with an arbitrary state set SS and relations 𝖢,𝖳\mathsf C,\mathsf T, suppose that xx and y=x⋅ey=x\cdot e are good at horizon nn, that 𝖢(x,j)\mathsf C(x,j) and 𝖢(y,k)\mathsf C(y,k) hold, and that both 𝖳(j,k)\mathsf T(j,k) and 𝖳(k,j)\mathsf T(k,j) hold. Then (8) holds: Exc⁡(rn,x;e,j)orExc⁡(rn,y;e‾,k).\operatorname{Exc}(r_{n,x};e,j) \quad\text{or}\quad \operatorname{Exc}(r_{n,y};\bar e,k).(8)✦

In the metric block, suppose that xx is good at horizon nn and that j∈Ee(x)∩Ef(x)j\in E_e(x)\cap E_f(x). Then (9) holds: e=f.e=f.(9)✦

For an arbitrary state set SS and any array r:E×S→ℕr:E\times S\to\mathbb N, suppose that both Exc⁡(r;e,j)\operatorname{Exc}(r;e,j) and Exc⁡(r;f,j)\operatorname{Exc}(r;f,j) hold. Then (10) holds: e=f.e=f.(10)✦

In the paper, the result reads: for an incidence e:x→ye:x\to y and states j,j′∈Sj,j'\in S, if (x,j)(x,j) and (y,j′)(y,j') are compatible and d(j,j′)≤2Ld(j,j')\leq2L, then j∈Ee(x)j\in E_e(x) or j′∈Ee‾(y)j'\in E_{\bar e}(y).

What Is Checked

The claims are stated over reversible port graphs with arbitrary compatibility and transition relations and over their metric specializations on finite state sets S⊆MS\subseteq M, under the goodness hypotheses in (8) and (9).