OctoInformBeta

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

Lemma 5.1: A palette bound gives a radius with few reduced matched walks

Counting matched roots across finite colorings.

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 finite graph construction compares walks with label sequences subject to vertex compatibility and transition relations. A root is counted when some walk from it has no immediate reversal and admits such a sequence. Let AA and CC be finite sets of generators and colors, and let SS be a finite label set. Write FAF_A for the free group on AA, identifying each generator with its canonical image in FAF_A. The signed ports, their reversal and their associated group elements are given by (1). D=A×{+1,−1},Δ=|D|,k=|C|,r(a,ε)=(a,−ε),ℓ(a,ε)=aε.\begin{aligned} D&=A\times\{+1,-1\}, & \Delta&=|D|, & k&=|C|,\\ r(a,\varepsilon)&=(a,-\varepsilon), & \ell(a,\varepsilon)&=a^{\varepsilon}. \end{aligned}(1)

A graph with reversible ports on a vertex set XX consists of a reversal map r:D→Dr:D\to D and a move map t:X×D→Xt:X\times D\to X satisfying (2). r(r(e))=e,t(t(x,e),r(e))=x(x∈X,e∈D).r(r(e))=e,\qquad t(t(x,e),r(e))=x \quad(x\in X,\ e\in D).(2)✦

For a nonnegative integer NN, the word ball WNW_N in FAF_A is the set of group elements of reduced length at most NN, and its word ball permutation group ΓN\Gamma_N is the group of permutations of WNW_N, as in (3). WN={g∈FA:|g|≤N},ΓN=Sym⁡(WN).W_N=\{g\in F_A:|g|\leq N\},\qquad \Gamma_N=\operatorname{Sym}(W_N).(3) For a generator a∈Aa\in A, an extended generator translation σN,a\sigma_{N,a} is a permutation of WNW_N that agrees with left multiplication by aa whenever the product remains in WNW_N. Choose one for each a∈Aa\in A. The word ball permutation representation ρN\rho_N is the homomorphism from FAF_A to ΓN\Gamma_N determined by these choices; (4) also specifies the moves of the finite Cayley graph. ρN:FA→ΓN,ρN(a)=σN,a,tN(x,e)=xρN(ℓ(e)).\rho_N:F_A\longrightarrow\Gamma_N,\qquad \rho_N(a)=\sigma_{N,a},\qquad t_N(x,e)=x\rho_N(\ell(e)).(4)

The all-colorings graph GNG_N has vertex set XNX_N: a vertex (f,x)(f,x) consists of a coloring ff of ΓN\Gamma_N and a group element xx. Its move keeps the coloring fixed, and its root color is cN(f,x)c_N(f,x), as specified in (5). XN=CΓN×ΓN,(f,x)⋅e=(f,tN(x,e)),cN(f,x)=f(x).X_N=C^{\Gamma_N}\times\Gamma_N,\qquad (f,x)\mathbin{\cdot}e=(f,t_N(x,e)),\qquad c_N(f,x)=f(x).(5) The sequence graph GG is the disjoint union of the graphs GNG_N over all radii.✦ Its vertex set XX, the inclusion ιN\iota_N of a radius and its componentwise coloring cc are given by (6); moves stay at the same radius. X=∐N≥0XN,ιN(f,x)=(N,f,x),c(ιN(f,x))=f(x).X=\coprod_{N\geq0}X_N,\qquad \iota_N(f,x)=(N,f,x),\qquad c(\iota_N(f,x))=f(x).(6)

Matching Rules

Fix a graph with reversible ports, a compatibility relation x∼jx\sim j between vertices and labels in SS, and a transition relation TT on SS. For a port word w=(e1,…,en)w=(e_1,\ldots,e_n) starting at x0x_0, let xi+1=t(xi,ei+1)x_{i+1}=t(x_i,e_{i+1}) be its successive vertices. A port word ww in a graph with reversible ports is reduced, or nonbacktracking, when it satisfies the first condition in (7); a walk (x0,j0,w)(x_0,j_0,w) with initial label j0j_0 in SS is matched when it satisfies the second condition. w is reduced⇔ei+1≠r(ei)(1≤i<n),(x0,j0,w) is matched⇔∃j1,…,jn∈S:xi∼ji(0≤i≤n),jiTji+1(0≤i<n).\begin{aligned} w\text{ is reduced} &\quad\Longleftrightarrow\quad e_{i+1}\ne r(e_i)\quad(1\leq i<n),\\ (x_0,j_0,w)\text{ is matched} &\quad\Longleftrightarrow\quad \exists j_1,\ldots,j_n\in S:\\ &\hspace{1.5em}x_i\sim j_i\quad(0\leq i\leq n),\qquad j_i\mathrel T j_{i+1}\quad(0\leq i<n). \end{aligned}(7) A root xx of a graph GG with reversible ports is good to depth nn when no reduced matched walk of length nn starts at xx. The set ℬn(G)\mathcal B_n(G) of bad roots of a graph GG with reversible ports consists of the roots that are not good to depth nn, as in (8), with the matching relations understood. ℬn(G)={x:∃j∈S,∃w,|w|=n,w is reduced and (x,j,w) is matched}.\mathcal B_n(G)= \{x:\exists j\in S,\ \exists w,\ |w|=n, w\text{ is reduced and }(x,j,w)\text{ is matched}\}.(8)

A palette assignment PP on SS is a map that assigns to each label j∈Sj\in S a subset P(j)⊆CP(j)\subseteq C. The palette width HH and the transition bound QQ are nonnegative integers satisfying (9). |P(j)|≤H,|{j′∈S:jTj′}|≤Q(j∈S).|P(j)|\leq H,\qquad |\{j'\in S:j\mathrel T j'\}|\leq Q \quad(j\in S).(9)

The Claim

Theorem 1. Let n≤Nn\leq N be nonnegative integers. Suppose the palettes and transitions satisfy (9), and compatibility on XNX_N requires f(x)∈P(j)f(x)\in P(j) whenever (f,x)∼j(f,x)\sim j. The finite counting bound is (10). |ℬn(GN)|kn+1≤Δn|S|QnHn+1|XN|.|\mathcal B_n(G_N)|\,k^{n+1} \leq \Delta^n |S| Q^n H^{n+1}|X_N|.(10)✦ Suppose instead that compatibility is specified on XX and requires c(z)∈P(j)c(z)\in P(j) whenever z∼jz\sim j, with the same palette and transition bounds. Assume Q,H,Δ>0Q,H,\Delta>0 and k>2ΔQHk>2\Delta QH. For every nonnegative integer VV, there is an integer n≥2n\geq2 satisfying (11). 20V|{z∈Xn:ιn(z)∈ℬn(G)}|<|Xn|.20V\,|\{z\in X_n:\iota_n(z)\in\mathcal B_n(G)\}|<|X_n|.(11)✦

In the paper, the result reads: for fixed n≥1n\geq1, if βm\beta_m is the fraction of vertices of GmG_m starting a matched walk of length nn, then limsup⁡m→∞βm≤|S|(H/k)(ΔQH/k)n\limsup_{m\to\infty}\beta_m\leq |S|(H/k)(\Delta QH/k)^n, and consequently one can first choose n≥2n\geq2 and then mm with βm<1/(20V)\beta_m<1/(20V).

What Is Checked

The claims are stated over finite colorings of word ball permutation groups, compatibility relations constrained by palettes, and label transitions with at most QQ successors. The generator translation extension theorem ensures that an extended generator translation exists for every radius NN and every generator aa.✦