OctoInformBeta

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

Lemma 3.5 [A matrix automaton for chunks]: Block realization in dimension at most b|Σ|bdb |\Sigma|^b d for nonempty finite Σ\Sigma with b>0b > 0, and chunk vanishing from letter vanishing in Ah(K)A_h(K)

Realizing bounded chunk tests by matrix letter tests.

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

Let KK be a commutative ring, 𝒜\mathcal{A} a KK-algebra, and Σ\Sigma a finite alphabet mapped into 𝒜\mathcal{A}. To test eventual vanishing in 𝒜\mathcal{A} with matrix coefficients over KK, one sums matrix-weighted products over all nn-letter words in Σ\Sigma, or sums over sequences from a finite chunk alphabet labeled by nonempty words over Σ\Sigma of length at most bb whose concatenated labels have length nn. How can any such chunk test of matrix dimension at most dd and label bound b>0b > 0 be realized as a fixed d×dd \times d block of a letter test over Σ\Sigma of controlled dimension, so that eventual vanishing of letter tests forces eventual vanishing of chunk tests?

Matrix Tests and Rewriting Algebras

For an alphabet Σ\Sigma, the free monoid of words Σ*\Sigma^* over Σ\Sigma consists of all finite sequences of letters in Σ\Sigma under concatenation, with empty word ε\varepsilon.✦ Given an alphabet Σ\Sigma, a monoid or ring RR, and a map f:Σ→Rf : \Sigma \to R, the evaluation eval⁡(f,w)∈R\operatorname{eval}(f, w) \in R of a word w=a1⋯ar∈Σ*w = a_1 \cdots a_r \in \Sigma^* of length |w|=r|w| = r is ∏k=1rf(ak)\prod_{k=1}^r f(a_k) in RR.✦ When Σ\Sigma is finite and n∈ℕn \in \mathbb{N}, the set 𝒞n(Σ)\mathcal{C}_n(\Sigma) of candidate words up to length nn is the finite set of all words over Σ\Sigma of length at most nn.✦ Over a ring RR, for a finite alphabet Σ\Sigma, a map f:Σ→Rf : \Sigma \to R, and n∈ℕn \in \mathbb{N}, the abstract letter sum of length nn is (1): ∑w∈𝒞n(Σ)|w|=neval⁡(f,w).\sum_{\substack{w \in \mathcal{C}_n(\Sigma) \\ |w| = n}} \operatorname{eval}(f, w).(1)✦ For a finite chunk alphabet Γ\Gamma, a ring RR, a length function ν:Γ→ℕ\nu : \Gamma \to \mathbb{N}, a weight map ω:Γ→R\omega : \Gamma \to R, and m∈ℕm \in \mathbb{N}, with gkg_k denoting the kk-th letter of a word gg, the abstract chunk sum of target length mm is (2): ∑g∈𝒞m(Γ)∑k=1|g|ν(gk)=meval⁡(ω,g).\sum_{\substack{g \in \mathcal{C}_m(\Gamma) \\ \sum_{k=1}^{|g|} \nu(g_k) = m}} \operatorname{eval}(\omega, g).(2)

Given a finite index set ι\iota, a ring KK, and a KK-algebra 𝒜\mathcal{A}, the tensor product X⊗a∈Mι(𝒜)X \otimes a \in M_\iota(\mathcal{A}) of a matrix X∈Mι(K)X \in M_\iota(K) and an element a∈𝒜a \in \mathcal{A} is the ι×ι\iota \times \iota matrix over 𝒜\mathcal{A} whose (i,j)(i, j)-entry is Xij⋅aX_{ij} \cdot a for all i,j∈ιi, j \in \iota.✦ For finite sets Σ\Sigma and ι\iota, a ring KK, a KK-algebra 𝒜\mathcal{A}, a weight W:Σ→Mι(K)W : \Sigma \to M_\iota(K), a map f:Σ→𝒜f : \Sigma \to \mathcal{A}, and n∈ℕn \in \mathbb{N}, the matrix letter sum Ln(W,f)∈Mι(𝒜)L_n(W, f) \in M_\iota(\mathcal{A}) is the abstract letter sum of length nn for a↦W(a)⊗f(a)a \mapsto W(a) \otimes f(a).✦ For finite sets Σ\Sigma and ι\iota, a ring KK, and a KK-algebra 𝒜\mathcal{A}, a letter test (W,f)(W, f) of dimension |ι||\iota| over Σ\Sigma is a pair of a weight W:Σ→Mι(K)W : \Sigma \to M_\iota(K) and a map f:Σ→𝒜f : \Sigma \to \mathcal{A}. When Γ\Gamma and ι\iota are finite, Σ\Sigma is an alphabet, KK is a ring, 𝒜\mathcal{A} is a KK-algebra, ℓ:Γ→Σ*\ell : \Gamma \to \Sigma^*, W:Γ→Mι(K)W : \Gamma \to M_\iota(K), f:Σ→𝒜f : \Sigma \to \mathcal{A}, and n∈ℕn \in \mathbb{N}, the matrix chunk sum Cn(ℓ,W,f)∈Mι(𝒜)C_n(\ell, W, f) \in M_\iota(\mathcal{A}) is the abstract chunk sum of target length nn for the length function c↦|ℓ(c)|c \mapsto |\ell(c)| and weight c↦W(c)⊗eval⁡(f,ℓ(c))c \mapsto W(c) \otimes \operatorname{eval}(f, \ell(c)). For finite sets Γ\Gamma and ι\iota, an alphabet Σ\Sigma, a ring KK, and a KK-algebra 𝒜\mathcal{A}, and b∈ℕb \in \mathbb{N}, a chunk test (ℓ,W,f)(\ell, W, f) of dimension |ι||\iota| and label bound bb over Σ\Sigma is a triple of a label map ℓ:Γ→Σ*\ell : \Gamma \to \Sigma^* sending each chunk c∈Γc \in \Gamma to a nonempty word of length at most bb, a weight W:Γ→Mι(K)W : \Gamma \to M_\iota(K), and a map f:Σ→𝒜f : \Sigma \to \mathcal{A}.

For a semiring KK and an alphabet Σ\Sigma, the monoid algebra of words K⟨Σ⟩K\langle \Sigma \rangle is the monoid algebra of Σ*\Sigma^* over KK✦, in which each word w∈Σ*w \in \Sigma^* has basis monomial [w][w] with coefficient 11 at ww.✦ A word rewriting table TT over an alphabet Σ\Sigma consists of a binary replacement relation rep\mathrm{rep} on Σ*\Sigma^* and a subset zero⊆Σ*\mathrm{zero} \subseteq \Sigma^* of zero words.✦ Given a ring KK and a word rewriting table TT over Σ\Sigma, the defining two-sided ideal IK(T)⊆K⟨Σ⟩I_K(T) \subseteq K\langle \Sigma \rangle is the two-sided ideal generated by the defining relations of TT, namely the differences [v]−[w][v] - [w] for (v,w)∈rep(v, w) \in \mathrm{rep} and the monomials [z][z] for z∈zeroz \in \mathrm{zero}; the algebra of the rewriting table TT over KK is the quotient algebra K⟨Σ⟩/IK(T)K\langle \Sigma \rangle / I_K(T), with quotient homomorphism πT:K⟨Σ⟩→K⟨Σ⟩/IK(T)\pi_T : K\langle \Sigma \rangle \to K\langle \Sigma \rangle / I_K(T) mapping each w∈Σ*w \in \Sigma^* to the word element πT([w])\pi_T([w]).

For h∈ℕh \in \mathbb{N}, the alphabet Σh={0,1}10000h\Sigma_h = \{0, 1\}^{10000 h} of raw bitstrings consists of Boolean vectors of length 10000h10000 h.✦ A verification clause schedule of capacity q∈ℕq \in \mathbb{N} assigns to each verification task (an arity below 1010 and a zero-task flag) a positive clause count at most qq and a family of clauses indexed below qq on three cell memory addresses.✦ Given h>0h > 0, a schedule SS of capacity qh=2hq_h = 2^h, and a data size m∈ℕm \in \mathbb{N}, the algebra table T(h,S,m)T(h, S, m) is the word rewriting table over Σh\Sigma_h whose replacement relation and zero words encode local cell transitions and invalid patterns; for a ring KK, each a∈Σha \in \Sigma_h yields a raw letter generator πT(h,S,m)([a])\pi_{T(h, S, m)}([a]) in the algebra of T(h,S,m)T(h, S, m) over KK.✦

For a dilation factor 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 at every height h≥h0h \ge h_0 the parameter bounds for the self-specialized code of the program hold and satisfiability of the verification tableau at height hh matches the rewriting-table membership condition at height DhD h with data size 10000D2h10000 D^2 h.✦ At any height h≥h0h \ge h_0, the hierarchy AA produces a verification clause schedule ShS_h of capacity qh=2hq_h = 2^h, a rewriting table Th=T(h,Sh,10000Dh)T_h = T(h, S_h, 10000 D h) over Σh\Sigma_h, the machine hierarchy algebra Ah(K)A_h(K) defined as the algebra of ThT_h over a ring KK, and, when KK is commutative, the letter map λh:Σh→Ah(K)\lambda_h : \Sigma_h \to A_h(K) sending each a∈Σha \in \Sigma_h to its raw letter generator in Ah(K)A_h(K).

A sequence of matrices (Mn)n∈ℕ(M_n)_{n \in \mathbb{N}} is eventually vanishing if there exists N∈ℕN \in \mathbb{N} such that Mn=0M_n = 0 for all n≥Nn \ge N. For a self-simulating machine hierarchy AA, a commutative ring KK, a height hh at least the threshold of AA, and d∈ℕd \in \mathbb{N}, the algebra Ah(K)A_h(K) satisfies letter vanishing in dimension dd if Ln(W,λh)L_n(W, \lambda_h) eventually vanishes for every letter test (W,λh)(W, \lambda_h) over Σh\Sigma_h of dimension at most dd.✦ Given a self-simulating machine hierarchy AA, a commutative ring KK, a height hh at least the threshold of AA, and d,b∈ℕd, b \in \mathbb{N}, the algebra Ah(K)A_h(K) satisfies chunk vanishing in dimension dd and label bound bb when Cn(ℓ,W,λh)C_n(\ell, W, \lambda_h) eventually vanishes for every chunk test (ℓ,W,λh)(\ell, W, \lambda_h) over Σh\Sigma_h of dimension at most dd and label bound bb.✦

The Matrix Automaton

For an alphabet Σ\Sigma and b∈ℕb \in \mathbb{N}, the automaton state space 𝒬b(Σ)\mathcal{Q}_b(\Sigma) is the set of all words over Σ\Sigma of length strictly less than bb✦. When b>0b > 0, the root state q0∈𝒬b(Σ)q_0 \in \mathcal{Q}_b(\Sigma) of the automaton state space 𝒬b(Σ)\mathcal{Q}_b(\Sigma) is the empty word ε\varepsilon.✦ Given an alphabet Σ\Sigma, b∈ℕb \in \mathbb{N}, a ring SS, a weight W:Σ*→SW : \Sigma^* \to S, and a letter a∈Σa \in \Sigma, with Kronecker delta δu,v\delta_{u, v} equal to 11 when u=vu = v and 00 otherwise, and papa denoting the concatenation of pp and aa, the automaton transition matrix TW(a)T_W(a) indexed by 𝒬b(Σ)×𝒬b(Σ)\mathcal{Q}_b(\Sigma) \times \mathcal{Q}_b(\Sigma) over SS has entries (3): TW(a)p,q=δq,pa1+δq,εW(pa)(p,q∈𝒬b(Σ)),T_W(a)_{p, q} = \delta_{q,\, pa}\, 1 + \delta_{q,\, \varepsilon}\, W(pa) \qquad (p, q \in \mathcal{Q}_b(\Sigma)),(3) When Σ\Sigma and ι\iota are finite, b∈ℕb \in \mathbb{N}, SS is a ring, W:Σ*→Mι(S)W : \Sigma^* \to M_\iota(S), and a∈Σa \in \Sigma, the block transition matrix BW(a)B_W(a) indexed by (𝒬b(Σ)×ι)×(𝒬b(Σ)×ι)(\mathcal{Q}_b(\Sigma) \times \iota) \times (\mathcal{Q}_b(\Sigma) \times \iota) over SS has ((p,i),(q,j))((p, i), (q, j))-entry (TW(a)p,q)i,j(T_W(a)_{p, q})_{i, j} for all p,q∈𝒬b(Σ)p, q \in \mathcal{Q}_b(\Sigma) and i,j∈ιi, j \in \iota, giving a matrix weight BW:Σ→M𝒬b(Σ)×ι(S)B_W : \Sigma \to M_{\mathcal{Q}_b(\Sigma) \times \iota}(S).

Given an alphabet Σ\Sigma and a word w∈Σ*w \in \Sigma^*, the collection 𝒫(w)\mathcal{P}(w) of partitions of ww is the finite list of all decompositions (v1,…,vm)(v_1, \dots, v_m) of ww into nonempty contiguous subwords satisfying v1⋯vm=wv_1 \cdots v_m = w, with 𝒫(ε)\mathcal{P}(\varepsilon) consisting solely of the empty decomposition.✦ For a finite alphabet Γ\Gamma, an alphabet Σ\Sigma, a ring SS, a label map ℓ:Γ→Σ*\ell : \Gamma \to \Sigma^*, and a weight W:Γ→SW : \Gamma \to S, the combined weight W̃ℓ,W:Σ*→S\widetilde{W}_{\ell, W} : \Sigma^* \to S is defined for each v∈Σ*v \in \Sigma^* by (4): W̃ℓ,W(v)=∑c∈Γℓ(c)=vW(c).\widetilde{W}_{\ell, W}(v) = \sum_{\substack{c \in \Gamma \\ \ell(c) = v}} W(c).(4)✦ For an alphabet Γ\Gamma and n∈ℕn \in \mathbb{N}, the set ℬn(Γ)\mathcal{B}_n(\Gamma) of bounded sequences of length at most nn over Γ\Gamma is the set of all finite sequences s=(s1,…,sr)s = (s_1, \dots, s_r) of elements of Γ\Gamma with r≤nr \le n; for an alphabet Σ\Sigma, a label map ℓ:Γ→Σ*\ell : \Gamma \to \Sigma^*, a ring SS, and a weight W:Γ→SW : \Gamma \to S, the spelled word spelled⁡(ℓ,s)∈Σ*\operatorname{spelled}(\ell, s) \in \Sigma^* of ss is ℓ(s1)⋯ℓ(sr)\ell(s_1) \cdots \ell(s_r), and its sequence weight wt⁡(W,s)∈S\operatorname{wt}(W, s) \in S is ∏k=1rW(sk)\prod_{k=1}^r W(s_k). When Γ\Gamma is finite, Σ\Sigma is an alphabet, SS is a ring, ℓ:Γ→Σ*\ell : \Gamma \to \Sigma^*, and W:Γ→SW : \Gamma \to S, the word coefficient coeff⁡ℓ,W(w)∈S\operatorname{coeff}_{\ell, W}(w) \in S of any word w∈Σ*w \in \Sigma^* is given by (5): coeff⁡ℓ,W(w)=∑s∈ℬ|w|(Γ)spelled⁡(ℓ,s)=wwt⁡(W,s).\operatorname{coeff}_{\ell, W}(w) = \sum_{\substack{s \in \mathcal{B}_{|w|}(\Gamma) \\ \operatorname{spelled}(\ell, s) = w}} \operatorname{wt}(W, s).(5)✦

The Claim

Theorem 1. For any nonempty finite alphabet Σ\Sigma and b∈ℕb \in \mathbb{N}, the automaton state space satisfies (6): |𝒬b(Σ)|≤b|Σ|b.|\mathcal{Q}_b(\Sigma)| \le b |\Sigma|^b.(6)✦ Given b>0b > 0, a finite alphabet Σ\Sigma, a finite index set ι\iota, a ring SS, and a matrix weight W:Σ*→Mι(S)W : \Sigma^* \to M_\iota(S) such that W(v)=0W(v) = 0 whenever |v|>b|v| > b, every word w=w1⋯wr∈Σ*w = w_1 \cdots w_r \in \Sigma^* and all i,j∈ιi, j \in \iota satisfy (7): (∏k=1rBW(wk))(q0,i),(q0,j)=(∑(v1,…,vm)∈𝒫(w)∏t=1mW(vt))i,j.\Bigl(\prod_{k=1}^{r} B_W(w_k)\Bigr)_{(q_0, i), (q_0, j)} = \Bigl(\sum_{(v_1, \dots, v_m) \in \mathcal{P}(w)} \prod_{t=1}^{m} W(v_t)\Bigr)_{i, j}.(7)✦ Suppose b>0b > 0, Σ\Sigma and Γ\Gamma are finite alphabets, ι\iota is a finite index set, SS is a ring, ℓ:Γ→Σ*\ell : \Gamma \to \Sigma^* sends every chunk to a nonempty word of length at most bb, and W:Γ→Mι(S)W : \Gamma \to M_\iota(S). Then every word w=w1⋯wr∈Σ*w = w_1 \cdots w_r \in \Sigma^* and all i,j∈ιi, j \in \iota satisfy (8): (∏k=1rBW̃ℓ,W(wk))(q0,i),(q0,j)=(coeff⁡ℓ,W(w))i,j.\Bigl(\prod_{k=1}^{r} B_{\widetilde{W}_{\ell, W}}(w_k)\Bigr)_{(q_0, i), (q_0, j)} = \bigl(\operatorname{coeff}_{\ell, W}(w)\bigr)_{i, j}.(8)✦ When b>0b > 0, Σ\Sigma and Γ\Gamma are finite alphabets, ι\iota is a finite index set, KK is a ring, 𝒜\mathcal{A} is a KK-algebra, ℓ:Γ→Σ*\ell : \Gamma \to \Sigma^* sends every chunk to a nonempty word of length at most bb, W:Γ→Mι(K)W : \Gamma \to M_\iota(K), and f:Σ→𝒜f : \Sigma \to \mathcal{A}, every n∈ℕn \in \mathbb{N} and i,j∈ιi, j \in \iota satisfy (9): Ln(BW̃ℓ,W,f)(q0,i),(q0,j)=Cn(ℓ,W,f)i,j.L_n\bigl(B_{\widetilde{W}_{\ell, W}}, f\bigr)_{(q_0, i), (q_0, j)} = C_n(\ell, W, f)_{i, j}.(9)✦ Let AA be a self-simulating machine hierarchy, KK a commutative ring, hh a height at least the threshold of AA, and d,b∈ℕd, b \in \mathbb{N} with b>0b > 0. Suppose Ah(K)A_h(K) satisfies letter vanishing in dimension b|Σh|bdb |\Sigma_h|^b d; then for every chunk test (ℓ,W,λh)(\ell, W, \lambda_h) over Σh\Sigma_h of dimension at most dd and label bound bb, there exists N∈ℕN \in \mathbb{N} such that (10) holds: Cn(ℓ,W,λh)=0(n≥N).C_n(\ell, W, \lambda_h) = 0 \qquad (n \ge N).(10)✦

In the paper, the result reads: for a chunk test of dimension dd and label bound bb over a nonempty finite alphabet Σ\Sigma of size s=|Σ|s = |\Sigma|, there is a letter test of dimension at most CbsbdC_b s^b d (Cb=bC_b = b) whose length-nn sum has the chunk sum as one fixed d×dd \times d block for every nn; consequently eventual vanishing of all letter tests in that dimension implies eventual vanishing of the chunk test. The library splits this statement into the state-space bound (6), the block identities (7), (8), and (9) over arbitrary finite alphabets and rings, and the transfer from letter vanishing to chunk vanishing (10) in Ah(K)A_h(K).

What Is Checked

The automaton bound and block identities are stated over the state space 𝒬b(Σ)\mathcal{Q}_b(\Sigma), root state q0q_0, transition and block transition matrices TWT_W and BWB_W, partitions 𝒫(w)\mathcal{P}(w), combined weights W̃ℓ,W\widetilde{W}_{\ell, W}, word coefficients over bounded sequences, and matrix letter and chunk sums LnL_n and CnC_n for finite alphabets Σ\Sigma (nonempty for the state bound) and Γ\Gamma, a finite index set ι\iota, rings SS and KK, and a KK-algebra 𝒜\mathcal{A}; the vanishing implication is stated over a self-simulating machine hierarchy AA, a commutative ring KK, a height hh at least the threshold of AA, the rewriting-table algebra Ah(K)A_h(K) over the raw bitstrings Σh\Sigma_h with letter map λh\lambda_h, and the letter and chunk vanishing predicates. Beyond the claim, at every height hh at least the threshold of a self-simulating machine hierarchy AA with dilation factor DD, hh and the data block size 10000Dh10000 D h are positive.