OctoInformBeta

OpenAI preprint, September 2026 · §3. Cancellation and the matrix-nil algebra

Lemma 3.4 [Reduction by the cuts]: For a commutative ring KK and dimension dd, letter vanishing in Ah(K)A_h(K) follows from bound-1010 chunk vanishing in ADh(K)A_{Dh}(K)

Letter vanishing in hierarchy algebras reduces to chunk vanishing.

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

Given a commutative ring KK, a dimension dd, a finite alphabet α\alpha, and an associative KK-algebra generated by α\alpha, matrix letter tests sum nn-fold products of d×dd \times d scalar matrices and algebra generators over all length-nn words in α\alpha, while chunk tests sum over sequences of multi-letter blocks of total length nn. When words decompose at designated cut letters into bounded prefixes, sequences of tokens, and bounded suffixes, both sums enter an abstract cut reduction. For a self-simulating hierarchy of rewriting-table algebras over KK with dilation factor D≥2D \ge 2, the question is how eventual vanishing of dimension-dd matrix letter tests at height hh reduces to eventual vanishing of dimension-dd matrix chunk tests of label bound 1010 at height DhDh.

Cut Intervals and Abstract Word Sums

For an alphabet α\alpha, write α*\alpha^* for the free monoid of words over α\alpha; the word evaluation ev(f,w)∈Λ\mathrm{ev}(f, w) \in \Lambda of a word w=a1⋯ar∈α*w = a_1 \cdots a_r \in \alpha^* along a map f:α→Λf : \alpha \to \Lambda into a monoid or ring Λ\Lambda is the product ∏i=1rf(ai)\prod_{i=1}^r f(a_i) in Λ\Lambda (taking value 11 on the empty word). Given a cut predicate κ\kappa on an alphabet α\alpha, a word w∈α*w \in \alpha^* is cut-free for κ\kappa if no letter occurring in ww satisfies κ\kappa✦, and ww is a cut interval for κ\kappa if w=atw = a t for a letter a∈αa \in \alpha satisfying κ\kappa and a cut-free word t∈α*t \in \alpha^* for κ\kappa.✦

For a finite alphabet α\alpha and n∈ℕn \in \mathbb{N}, the set α≤n\alpha^{\le n} of candidate words up to length nn is the finite set of all words over α\alpha of length at most nn, and αn⊆α≤n\alpha^n \subseteq \alpha^{\le n} is the subset of words of length nn.✦ The letter sum Sn(f)∈ΛS_n(f) \in \Lambda of a map f:α→Λf : \alpha \to \Lambda from a finite alphabet α\alpha into a ring Λ\Lambda at n∈ℕn \in \mathbb{N} is Sn(f)=∑w∈αnev(f,w).S_n(f) = \sum_{w \in \alpha^n} \mathrm{ev}(f, w).(1)✦ For a finite chunk alphabet Γ\Gamma, a ring Λ\Lambda, a length map ℓ:Γ→ℕ\ell : \Gamma \to \mathbb{N}, a weight map ω:Γ→Λ\omega : \Gamma \to \Lambda, and m∈ℕm \in \mathbb{N}, the chunk sum Cm(ℓ,ω)∈ΛC_m(\ell, \omega) \in \Lambda is Cm(ℓ,ω)=∑gs=c1⋯cr∈Γ≤m∑i=1rℓ(ci)=mev(ω,gs).C_m(\ell, \omega) = \sum_{\substack{gs = c_1 \cdots c_r \in \Gamma^{\le m} \\ \sum_{i=1}^r \ell(c_i) = m}} \mathrm{ev}(\omega, gs).(2)✦

A token map τ:Γ→α*\tau : \Gamma \to \alpha^* between alphabets Γ\Gamma and α\alpha extends to words gs=c1⋯cr∈Γ*gs = c_1 \cdots c_r \in \Gamma^* by τ*(gs)=τ(c1)⋯τ(cr)\tau^*(gs) = \tau(c_1) \cdots \tau(c_r), and for any triple x=(p,s,gs)∈α*×α*×Γ*x = (p, s, gs) \in \alpha^* \times \alpha^* \times \Gamma^*, the token join is Jτ(x)=pτ*(gs)s∈α*J_\tau(x) = p \, \tau^*(gs) \, s \in \alpha^*.✦ When α\alpha and Γ\Gamma are finite, the token decomposition language ℒτ(𝒫,𝒮,n)\mathcal{L}_\tau(\mathcal{P}, \mathcal{S}, n) for finite subsets 𝒫,𝒮⊆α*\mathcal{P}, \mathcal{S} \subseteq \alpha^* and n∈ℕn \in \mathbb{N} is the finite set of all triples x∈𝒫×𝒮×Γ≤nx \in \mathcal{P} \times \mathcal{S} \times \Gamma^{\le n} satisfying |Jτ(x)|=n|J_\tau(x)| = n.✦

Matrix Tests and Rewriting Table Algebras

Let ι\iota be a finite index set, KK a commutative ring, and Λ\Lambda an associative KK-algebra. The tensor product X⊗a∈Mat⁡ι(Λ)X \otimes a \in \operatorname{Mat}_\iota(\Lambda) of a matrix X∈Mat⁡ι(K)X \in \operatorname{Mat}_\iota(K) and an element a∈Λa \in \Lambda is the ι×ι\iota \times \iota matrix over Λ\Lambda with (i,j)(i, j)-entry Xij⋅aX_{ij} \cdot a for all i,j∈ιi, j \in \iota.✦ For a finite alphabet α\alpha, a matrix weight W:α→Mat⁡ι(K)W : \alpha \to \operatorname{Mat}_\iota(K), a map f:α→Λf : \alpha \to \Lambda, and n∈ℕn \in \mathbb{N}, the matrix letter sum 𝑺n(W,f)∈Mat⁡ι(Λ)\mathbf{S}_n(W, f) \in \operatorname{Mat}_\iota(\Lambda) is defined via (1) by 𝑺n(W,f)=Sn(a↦W(a)⊗f(a))\mathbf{S}_n(W, f) = S_n(a \mapsto W(a) \otimes f(a)).✦ For a finite chunk alphabet Γ\Gamma, a label map ψ:Γ→α*\psi : \Gamma \to \alpha^*, a matrix weight W:Γ→Mat⁡ι(K)W : \Gamma \to \operatorname{Mat}_\iota(K), a map f:α→Λf : \alpha \to \Lambda, and n∈ℕn \in \mathbb{N}, the matrix chunk sum 𝑪n(ψ,W,f)∈Mat⁡ι(Λ)\mathbf{C}_n(\psi, W, f) \in \operatorname{Mat}_\iota(\Lambda) is defined via (2) by 𝑪n(ψ,W,f)=Cn(c↦|ψ(c)|,c↦W(c)⊗ev(f,ψ(c)))\mathbf{C}_n(\psi, W, f) = C_n(c \mapsto |\psi(c)|, \, c \mapsto W(c) \otimes \mathrm{ev}(f, \psi(c))).✦

For an alphabet α\alpha and a ring KK, write K[α*]K[\alpha^*] for the monoid algebra of α*\alpha^* over KK, in which each word w∈α*w \in \alpha^* determines a basis monomial [w]∈K[α*][w] \in K[\alpha^*] with coefficient 11 at ww. A word rewriting table T=(rep⁡,zero⁡)T = (\operatorname{rep}, \operatorname{zero}) over α\alpha consists of a binary replacement relation rep\operatorname{rep} on α*\alpha^* and a subset zero⁡⊆α*\operatorname{zero} \subseteq \alpha^* of zero words.✦ For a word rewriting table T=(rep⁡,zero⁡)T = (\operatorname{rep}, \operatorname{zero}) over α\alpha, the defining relations of TT over KK form the subset {[v]−[w]∣(v,w)∈rep⁡}∪{[z]∣z∈zero⁡}\{[v] - [w] \mid (v, w) \in \operatorname{rep}\} \cup \{[z] \mid z \in \operatorname{zero}\} of K[α*]K[\alpha^*], generating a two-sided ideal IK(T)⊆K[α*]I_K(T) \subseteq K[\alpha^*]. The rewriting-table algebra K[T]=K[α*]/IK(T)K[T] = K[\alpha^*] / I_K(T) is the quotient ring of K[α*]K[\alpha^*] by IK(T)I_K(T), equipped with the quotient homomorphism K[α*]→K[T]K[\alpha^*] \to K[T] sending each basis monomial [w][w] to its word class [w]T∈K[T][w]_T \in K[T].

Finite Table Cells and the Machine Hierarchy

For h∈ℕh \in \mathbb{N}, let Ωh={0,1}10000h\Omega_h = \{0, 1\}^{10000h} be the finite alphabet of raw bitstrings of length 10000h10000h.✦ A verification task is a pair consisting of an arity in {0,…,9}\{0, \dots, 9\} and a Boolean zero-task flag.✦ For q∈ℕq \in \mathbb{N}, a cell memory address is either a data address (a Boolean side, a block index in {0,…,9}\{0, \dots, 9\}, and a position strictly less than qq) or a certificate address (a position strictly less than qq)✦; a verification clause of capacity qq consists of three cell memory addresses indexed by {0,1,2}\{0, 1, 2\} together with a Boolean truth function on 𝔽23\mathbb{F}_2^3✦; and a verification clause schedule Φ\Phi of capacity qq assigns to each verification task a positive clause count at most qq and a family of verification clauses indexed by clause index strictly less than qq.✦ A finite table cell of capacity qq consists of a skeleton (a position that is a core coordinate strictly less than qq, a palette color strictly less than qq, or stop; a marker from idle, left, boundary, full, or right; and metadata giving an arity strictly less than 1010, a zero-task flag, and a block index at most that arity), a palette checker state (idle, passed with a sought color strictly less than qq, or an active head seeking a color strictly less than qq), two side-indexed 𝔽2\mathbb{F}_2 data bits, an 𝔽2\mathbb{F}_2 certificate bit, and a reading head state (a Boolean side, a clause index strictly less than qq, one of nine computation phases, and a register in 𝔽23\mathbb{F}_2^3).✦

For q≥1q \ge 1, a finite table cell cc of capacity qq satisfies the cut predicate if its position is the core coordinate 00 and either its marker is idle or the block index in its metadata equals 00.✦ Given a schedule Φ\Phi of capacity qq and a data size d∈ℕd \in \mathbb{N}, two cell lists satisfy the replacement relation when every cell in both lists is formatted and the lists are singletons or pairs related in either direction by a unary or binary transition✦; replacing a subword by a replacement-related subword defines a rewriting step, whose reflexive-transitive closure is reachability. A cell word satisfies the zero cell word predicate if it is a single cell failing formatting, hitting a semantic head-phase failure, or resting in a passed state at its own palette color (a unary-zero cell), or a pair of cells failing skeleton or checker compatibility, sharing a palette position, or pairing a palette cell seeking a distinct color with a stop cell (a binary-zero cell pair).✦ A cell word survives under Φ\Phi and dd if no reachable word contains a subword satisfying the zero cell word predicate✦, and a cell token for Φ\Phi and dd is a cut interval tt for the cut predicate such that tbt b survives for some cell bb satisfying the cut predicate. For h>0h > 0, cell encoding embeds cells of capacity qh=2hq_h = 2^h into Ωh\Omega_h, and cell decoding (extended letterwise to words) recovers a cell cc from w∈Ωhw \in \Omega_h precisely when parsing ww yields cc and encoding cc reproduces ww; a raw token for hh, Φ\Phi, and dd is the letterwise encoding of a cell token.✦ The algebra table T(h,Φ,d)T(h, \Phi, d) over Ωh\Omega_h has replacement relation holding whenever both raw words decode to replacement-related cell lists, and zero words consisting of raw singletons that fail to decode or decode to a unary-zero cell together with raw pairs decoding to a binary-zero cell pair; for a Boolean selector zz and v,w∈Ωh*v, w \in \Omega_h^*, the codec table entry holds if ww is empty and vv is zero in T(h,Φ,d)T(h, \Phi, d) when zz is true, and if (v,w)(v, w) is a replacement pair when zz is false.✦

A fixed timed-tape stack machine implementing a wrapped universal stack interpreter has a one-hot binary tape coding of bit width β\beta, an input-packet decoder of packet bit width equal to the cardinality of its packet set, and a combinational not-and (NAND) circuit realization with gg gates computing its local step. For q,β,g,r,u∈ℕq, \beta, g, r, u \in \mathbb{N} with β>0\beta > 0, r>0r > 0, and u≥3u \ge 3, a tableau layout specifies an origin index strictly less than uu such that both the total certificate variable count βur+g(u−2)(r−1)\beta u r + g(u - 2)(r - 1) and the total tableau clause count 2βu+2β(r−1)+(3g+2β)(u−2)(r−1)+β2\beta u + 2\beta(r - 1) + (3g + 2\beta)(u - 2)(r - 1) + \beta are at most qq.✦ Letting b2(m)b_2(m) be 11 for m=0m = 0 and the binary length of mm otherwise, for height hh, dilation DD, and code length nn, with rh=2⌊h/5⌋r_h = 2^{\lfloor h/5 \rfloor} and uh=4rhu_h = 4 r_h, the layout parameter bounds hold when 64h+512≤10000h64h + 512 \le 10000h, 10≤22h10 \le 2^{2h}, 2h≤22h2^h \le 2^{2h}, 10000Dh≤2h10000Dh \le 2^h, the certificate and clause counts for (rh,uh)(r_h, u_h) are at most 2h2^h, and n+2b2(n)+2b2(Dh)+12+20(10000Dh)<⌊rh/4⌋n + 2 b_2(n) + 2 b_2(Dh) + 12 + 20(10000Dh) < \lfloor r_h/4 \rfloor.✦ Under these bounds with 10000Dh>010000Dh > 0, the source clause schedule at height hh for a code a∈{0,1}na \in \{0, 1\}^n is the verification clause schedule of capacity qh=2hq_h = 2^h constructed from the tableau layout with (rh,uh)(r_h, u_h) and origin 2rh2 r_h, the circuit realization, and the initial inputs formed from aa and data size 10000Dh10000Dh. Given an integer dilation D≥2D \ge 2, a self-simulating machine hierarchy AA consists of a Boolean program and a threshold h0≥4h_0 \ge 4 such that every height h≥h0h \ge h_0 satisfies the layout parameter bounds for the self-specialized code of the program (prepending a true bit to the prefix encoding of the length and bits of the program twice, where the prefix encoding of m∈ℕm \in \mathbb{N} concatenates b2(m)b_2(m) true bits, a false delimiter bit, and the b2(m)b_2(m) binary digits of mm) together with the self-certification equivalence: for every verification task of arity vv and every Boolean assignment on data addresses of capacity qhq_h, there exists a Boolean certificate on positions strictly less than qhq_h satisfying every clause of the height-hh tableau layout on the assignment assembled from that data assignment and certificate if and only if the codec table entry at height DhDh (for the source clause schedule of that self-specialized code at height DhDh, data size 10000D2h10000D^2h, and selector equal to the zero-task flag) accepts the length-(v+1)(v + 1) sequence of candidate raw words in ΩDh\Omega_{Dh} extracted from the false-side blocks of that data assignment and, when the zero-task flag is false, the corresponding true-side sequence (otherwise empty).✦

Fix D≥2D \ge 2, a self-simulating machine hierarchy AA, a commutative ring KK, and a height hh at least the threshold h0h_0 of AA. The hierarchy clause schedule Φh(A)\Phi_h(A) is the source clause schedule of capacity qh=2hq_h = 2^h for the self-specialized code of AA at height hh✦, and Th(A)=T(h,Φh(A),10000Dh)T_h(A) = T(h, \Phi_h(A), 10000Dh) is its algebra table over Ωh\Omega_h.✦ The rewriting-table algebra Ah(K)A_h(K) of Th(A)T_h(A) is K[Th(A)]K[T_h(A)], and the letter map ηh,K:Ωh→Ah(K)\eta_{h,K} : \Omega_h \to A_h(K) sends each raw bitstring a∈Ωha \in \Omega_h to the word class [a]Th(A)∈Ah(K)[a]_{T_h(A)} \in A_h(K).✦ The hierarchy token set 𝒯h(A)\mathcal{T}_h(A) is the set of raw tokens for hh, Φh(A)\Phi_h(A), and data size 10000Dh10000Dh✦, and the token normal-form map νh:𝒯h(A)→ΩDh*\nu_h : \mathcal{T}_h(A) \to \Omega_{Dh}^* sends each token in 𝒯h(A)\mathcal{T}_h(A) to a normalized raw word of height DhDh.✦ Say that a sequence (Xn)n∈ℕ(X_n)_{n \in \mathbb{N}} eventually vanishes if there exists N∈ℕN \in \mathbb{N} such that Xn=0X_n = 0 for all n≥Nn \ge N. For d∈ℕd \in \mathbb{N}, Ah(K)A_h(K) satisfies letter vanishing in dimension dd, written 𝒱d(Ah(K))\mathcal{V}_d(A_h(K)), if 𝑺n(W,ηh,K)\mathbf{S}_n(W, \eta_{h,K}) eventually vanishes for every finite index set ι\iota with |ι|≤d|\iota| \le d and every matrix weight W:Ωh→Mat⁡ι(K)W : \Omega_h \to \operatorname{Mat}_\iota(K)✦, and for d,b∈ℕd, b \in \mathbb{N}, the algebra Ah(K)A_h(K) satisfies chunk vanishing in dimension dd with label bound bb, written 𝒞d,b(Ah(K))\mathcal{C}_{d,b}(A_h(K)), if 𝑪n(ψ,W,ηh,K)\mathbf{C}_n(\psi, W, \eta_{h,K}) eventually vanishes for every finite index set ι\iota with |ι|≤d|\iota| \le d, every finite chunk alphabet Γ\Gamma, every label map ψ:Γ→Ωh*\psi : \Gamma \to \Omega_h^* with 1≤|ψ(c)|≤b1 \le |\psi(c)| \le b for all c∈Γc \in \Gamma, and every matrix weight W:Γ→Mat⁡ι(K)W : \Gamma \to \operatorname{Mat}_\iota(K).

The Claim

Theorem 1. Let D≥2D \ge 2, let AA be a self-simulating machine hierarchy with dilation DD, let KK be a commutative ring, let hh be at least the threshold of AA, and let d∈ℕd \in \mathbb{N}. If ADh(K)A_{Dh}(K) satisfies chunk vanishing in dimension dd with label bound 1010, then 𝒱d(Ah(K)).\mathcal{V}_d(A_h(K)).(3)✦

For the same DD, AA, KK, and hh, let ι\iota be a finite index set and let W:Ωh→Mat⁡ι(K)W : \Omega_h \to \operatorname{Mat}_\iota(K) be a matrix weight. If for every token weight W′:𝒯h(A)→Mat⁡ι(K)W' : \mathcal{T}_h(A) \to \operatorname{Mat}_\iota(K) the sequence 𝑪n(νh,W′,ηDh,K)\mathbf{C}_n(\nu_h, W', \eta_{Dh,K}) eventually vanishes, then there exists N∈ℕN \in \mathbb{N} such that 𝑺n(W,ηh,K)=0(n≥N).\mathbf{S}_n(W, \eta_{h,K}) = 0 \qquad (n \ge N).(4)✦

Let α\alpha and Γ\Gamma be finite alphabets, let Λ\Lambda be a ring, let κ\kappa be a cut predicate on α\alpha, and let τ:Γ→α*\tau : \Gamma \to \alpha^* be an injective map such that τ(c)\tau(c) is a cut interval for κ\kappa for every c∈Γc \in \Gamma. Let 𝒫,𝒮⊆α*\mathcal{P}, \mathcal{S} \subseteq \alpha^* be finite sets of cut-free words and cut intervals for κ\kappa, respectively, with |p|≤B|p| \le B for all p∈𝒫p \in \mathcal{P} and |s|≤B|s| \le B for all s∈𝒮s \in \mathcal{S} for some B∈ℕB \in \mathbb{N}, and let ℓ:Γ→ℕ\ell : \Gamma \to \mathbb{N} and L∈ℕL \in \mathbb{N} satisfy ℓ(c)≥1\ell(c) \ge 1, L≥1L \ge 1, and |τ(c)|=L⋅ℓ(c)|\tau(c)| = L \cdot \ell(c) for all c∈Γc \in \Gamma. If f:α→Λf : \alpha \to \Lambda and N0,N1∈ℕN_0, N_1 \in \mathbb{N} are such that every word w∈α*w \in \alpha^* with |w|≥N0|w| \ge N_0 and ev(f,w)≠0\mathrm{ev}(f, w) \neq 0 factors as w=pτ*(gs)sw = p \, \tau^*(gs) \, s for some p∈𝒫p \in \mathcal{P}, s∈𝒮s \in \mathcal{S}, and gs∈Γ*gs \in \Gamma^*, and such that Cm(ℓ,c↦ev(f,τ(c)))=0C_m(\ell, c \mapsto \mathrm{ev}(f, \tau(c))) = 0 for all m≥N1m \ge N_1, then for every n≥max⁡(N0,2B+LN1)n \ge \max(N_0, 2B + L N_1), Sn(f)=0.S_n(f) = 0.(5)✦

Under the same α\alpha, Γ\Gamma, Λ\Lambda, κ\kappa, τ\tau, 𝒫\mathcal{P}, 𝒮\mathcal{S}, and f:α→Λf : \alpha \to \Lambda, if n∈ℕn \in \mathbb{N} is such that every word w∈αnw \in \alpha^n with ev(f,w)≠0\mathrm{ev}(f, w) \neq 0 factors as w=pτ*(gs)sw = p \, \tau^*(gs) \, s for some p∈𝒫p \in \mathcal{P}, s∈𝒮s \in \mathcal{S}, and gs∈Γ*gs \in \Gamma^*, then Sn(f)=∑x∈ℒτ(𝒫,𝒮,n)ev(f,Jτ(x)).S_n(f) = \sum_{x \in \mathcal{L}_\tau(\mathcal{P}, \mathcal{S}, n)} \mathrm{ev}(f, J_\tau(x)).(6)✦

In the paper, the result reads: for a level jj, a field KK of characteristic two, and a dimension dd, if every dimension-dd chunk test of label bound kk at level j+1j + 1 eventually vanishes, then every dimension-dd letter test at level jj eventually vanishes. The library’s statement (3) replaces the level indices jj and j+1j + 1 with the hierarchy heights hh and DhDh, fixes the label bound at k=10k = 10, and holds over an arbitrary commutative ring KK rather than only over a field of characteristic two.

What Is Checked

Claims (3) and (4) are stated over an arbitrary commutative ring KK, a self-simulating machine hierarchy AA of dilation D≥2D \ge 2, a height hh at least the threshold of AA, the rewriting-table algebras Ah(K)A_h(K) and ADh(K)A_{Dh}(K) over the raw bitstring alphabets Ωh\Omega_h and ΩDh\Omega_{Dh}, the token set 𝒯h(A)\mathcal{T}_h(A) with normal-form map νh\nu_h, a finite index set ι\iota (of cardinality at most dd in (3)), and matrix weights on Ωh\Omega_h and 𝒯h(A)\mathcal{T}_h(A) over KK, while (5) and (6) are stated over finite alphabets α\alpha and Γ\Gamma, a ring Λ\Lambda, a cut predicate κ\kappa on α\alpha, an injective cut-interval token map τ\tau, finite sets 𝒫\mathcal{P} and 𝒮\mathcal{S} of cut-free prefixes and cut-interval suffixes, a weight map f:α→Λf : \alpha \to \Lambda, and (in (5)) positive chunk lengths ℓ\ell, a positive multiplier LL, a bound BB, and thresholds N0,N1N_0, N_1. Beyond (3) through (6), the library establishes for these constructions that every height hh meeting the threshold of AA is positive, has positive data size 10000Dh10000Dh, and yields a dilated height DhDh that also meets the threshold of AA, and that the tape-coding bit width β\beta, the packet bit width of the input decoder, and the total clause count of any tableau layout are positive.