OctoInformBeta

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

Lemma 3.3 [Direct cancellation]: Over commutative rings KK of characteristic two, dimension-dd chunk tests of label bound bb in Ah(K)A_h(K) vanish eventually when 100b(d2+3)<2h100b(d^2+3)<2^h

Direct cancellation yields eventual vanishing of chunk 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

Fix a commutative ring KK of characteristic two and a finitely presented associative algebra over KK, given as a quotient of a monoid algebra by word rewriting relations and zero words. For a finite alphabet of chunks labeled by nonempty words of length at most bb over the generating alphabet and weighted by d×dd \times d matrices over KK, summing the matrix-weighted word products over all chunk sequences whose concatenated labels have total length nn produces a d×dd \times d matrix over the algebra. For the height-hh rewriting algebra Ah(K)A_h(K) of a self-simulating machine hierarchy with qh=2hq_h = 2^h, the question is when every such dimension-dd chunk test of label bound bb vanishes for all sufficiently large nn, and whether 100b(d2+3)<2h100 b (d^2 + 3) < 2^h suffices.

Packets, Chunk Sums, and Eligible Intervals

For a natural number mm, write Im={0,…,m−1}I_m = \{0, \dots, m - 1\} (empty when m=0m = 0), and for a ring or semiring BB, finite index set ι\iota, and natural number dd, write Mι(B)M_\iota(B) for the ring of ι×ι\iota \times \iota matrices over BB and Md(B)=MId(B)M_d(B) = M_{I_d}(B). For an alphabet α\alpha, the free monoid α*\alpha^* consists of finite words over α\alpha under concatenation, with |w||w| denoting the length of w∈α*w \in \alpha^*.✦ Given a finite alphabet α\alpha and n≥0n \ge 0, the set of candidate words 𝒞n(α)\mathcal{C}_n(\alpha) up to length nn is the finite set {w∈α*:|w|≤n}\{w \in \alpha^* : |w| \le n\}.✦

Given an alphabet α\alpha, a ring BB, and a map f:α→Bf : \alpha \to B, the word evaluation evf(w)∈B\mathrm{ev}_f(w) \in B of w=(a0,…,am−1)∈α*w = (a_0, \dots, a_{m-1}) \in \alpha^* under ff is given by (1): evf(w)=∏k=0m−1f(ak)∈B.\mathrm{ev}_f(w) = \prod_{k=0}^{m-1} f(a_k) \in B.(1) For a finite chunk alphabet Γ\Gamma, a ring BB, a length map ℓ0:Γ→ℕ\ell_0 : \Gamma \to \mathbb{N}, a weight map w:Γ→Bw : \Gamma \to B, and m≥0m \ge 0, the scalar chunk sum of target length mm is the element of BB defined by (2): ∑s∈𝒞m(Γ)∑k=0|s|−1ℓ0(sk)=mevw(s)∈B,\sum_{\substack{s \in \mathcal{C}_m(\Gamma) \\ \sum_{k=0}^{|s|-1} \ell_0(s_k) = m}} \mathrm{ev}_w(s) \in B,(2) where s=(s0,…,s|s|−1)s = (s_0, \dots, s_{|s|-1}).

A packet p=(u,v,z)p = (u, v, z) over an alphabet Γ\Gamma is a triple of words over Γ\Gamma, consisting of a prefix uu, an interior vv, and a suffix zz.✦ For a packet p=(u,v,z)p = (u, v, z) over an alphabet Γ\Gamma, the concatenation of pp is the word uvz∈Γ*u v z \in \Gamma^*, and the invariant key of pp is the triple (u,z,[v])(u, z, [v]), where [v][v] is the multiset of entries of vv. The permuted packet word pσ∈Γ*p^\sigma \in \Gamma^* of a packet p=(u,v,z)p = (u, v, z) over an alphabet Γ\Gamma with v=(v0,…,v|v|−1)v = (v_0, \dots, v_{|v|-1}) under a permutation σ\sigma of I|v|I_{|v|} is the word u(vσ(0),…,vσ(|v|−1))zu (v_{\sigma(0)}, \dots, v_{\sigma(|v|-1)}) z. Given d≥0d \ge 0 and a matrix weight map W:Γ→Md(K)W : \Gamma \to M_d(K) over a ring KK, the chunk sequence weight matrix W(s)∈Md(K)W(s) \in M_d(K) of s=(s0,…,sr−1)∈Γ*s = (s_0, \dots, s_{r-1}) \in \Gamma^* is the matrix product (3): W(s)=∏k=0r−1W(sk)∈Md(K).W(s) = \prod_{k=0}^{r-1} W(s_k) \in M_d(K).(3)

For alphabets Γ\Gamma and α\alpha and a label map ℓ:Γ→α*\ell : \Gamma \to \alpha^*, the word spelled by s=(s0,…,sr−1)∈Γ*s = (s_0, \dots, s_{r-1}) \in \Gamma^* is the concatenation ℓ*(s)=ℓ(s0)⋯ℓ(sr−1)∈α*\ell^*(s) = \ell(s_0) \cdots \ell(s_{r-1}) \in \alpha^*.✦ When Γ\Gamma is a finite chunk alphabet, α\alpha is an alphabet, ℓ:Γ→α*\ell : \Gamma \to \alpha^* is a label map, KK is a ring, BB is a KK-algebra, d,n≥0d, n \ge 0, W:Γ→Md(K)W : \Gamma \to M_d(K), f:α→Bf : \alpha \to B, and i,j∈Idi, j \in I_d, the entrywise chunk sum Sn(ℓ,W,f)ij∈BS_n(\ell, W, f)_{ij} \in B is given by (4): Sn(ℓ,W,f)ij=∑s∈𝒞n(Γ)|ℓ*(s)|=nW(s)ij⋅evf(ℓ*(s)).S_n(\ell, W, f)_{ij} = \sum_{\substack{s \in \mathcal{C}_n(\Gamma) \\ |\ell^*(s)| = n}} W(s)_{ij} \cdot \mathrm{ev}_f(\ell^*(s)).(4) Given a finite index set ι\iota, a KK-algebra BB, X∈Mι(K)X \in M_\iota(K), and a∈Ba \in B, the tensor product X⊗a∈Mι(B)X \otimes a \in M_\iota(B) is the matrix with (i,j)(i, j)-entry Xij⋅aX_{ij} \cdot a for all i,j∈ιi, j \in \iota.✦ For finite Γ\Gamma and ι\iota, a label map ℓ:Γ→α*\ell : \Gamma \to \alpha^*, W:Γ→Mι(K)W : \Gamma \to M_\iota(K), f:α→Bf : \alpha \to B, and n≥0n \ge 0, setting θ(c)=W(c)⊗evf(ℓ(c))\theta(c) = W(c) \otimes \mathrm{ev}_f(\ell(c)) for each c∈Γc \in \Gamma, the matrix chunk sum Σn(ℓ,W,f)∈Mι(B)\Sigma_n(\ell, W, f) \in M_\iota(B) is the special case of (2) in Mι(B)M_\iota(B) given by (5): Σn(ℓ,W,f)=∑s∈𝒞n(Γ)∑k=0|s|−1|ℓ(sk)|=nevθ(s).\Sigma_n(\ell, W, f) = \sum_{\substack{s \in \mathcal{C}_n(\Gamma) \\ \sum_{k=0}^{|s|-1} |\ell(s_k)| = n}} \mathrm{ev}_\theta(s).(5) A sequence (Mn)n≥0(M_n)_{n \ge 0} in Mι(B)M_\iota(B) eventually vanishes if Mn=0M_n = 0 for all sufficiently large nn.

Suppose TT is an alphabet, PP is a predicate on TT, q≥0q \ge 0, and v=(t0,…,tm−1)∈T*v = (t_0, \dots, t_{m-1}) \in T^*. A pair (a,e)(a, e) of integers with 0≤a<e≤m0 \le a < e \le m is a qq-eligible interval for vv with respect to PP if 100(e−a)≥q100(e - a) \ge q and there exists t∈Tt \in T satisfying PP such that tk=tt_k = t for all a≤k<ea \le k < e, ta−1≠tt_{a-1} \neq t whenever a>0a > 0, and te≠tt_e \neq t whenever e<me < m.✦ For any map η:α→T\eta : \alpha \to T, write η*:α*→T*\eta^* : \alpha^* \to T^* for letterwise application of η\eta.

Rewriting-table Algebras and Machine Hierarchies

Given a semiring KK and an alphabet α\alpha, the monoid algebra of words K[α*]K[\alpha^*] is the monoid algebra of α*\alpha^* over KK, in which each w∈α*w \in \alpha^* has a basis monomial m(w)∈K[α*]m(w) \in K[\alpha^*] supported at ww with coefficient 11. A word rewriting table 𝒯=(rep,Z)\mathcal{T} = (\mathrm{rep}, Z) over α\alpha consists of a binary replacement relation rep\mathrm{rep} on α*\alpha^* and a set Z⊆α*Z \subseteq \alpha^* of zero words.✦ When KK is a ring, the defining relations of 𝒯\mathcal{T} form the subset R𝒯⊆K[α*]R_{\mathcal{T}} \subseteq K[\alpha^*] in (6): R𝒯={m(u)−m(v):(u,v)∈rep}∪{m(z):z∈Z}.R_{\mathcal{T}} = \{m(u) - m(v) : (u, v) \in \mathrm{rep}\} \cup \{m(z) : z \in Z\}.(6)✦ Writing I𝒯⊆K[α*]I_{\mathcal{T}} \subseteq K[\alpha^*] for the two-sided ideal generated by R𝒯R_{\mathcal{T}}, the algebra of the rewriting table is the quotient ring K[α*]/I𝒯K[\alpha^*] / I_{\mathcal{T}}, with canonical quotient homomorphism π𝒯:K[α*]→K[α*]/I𝒯\pi_{\mathcal{T}} : K[\alpha^*] \to K[\alpha^*] / I_{\mathcal{T}} sending m(w)m(w) to the word element w¯=π𝒯(m(w))\overline{w} = \pi_{\mathcal{T}}(m(w)).

The raw bitstring alphabet at height h≥0h \ge 0 is Σh={0,1}10000h\Sigma_h = \{0, 1\}^{10000h}.✦ For an integer dilation factor D≥2D \ge 2, a self-simulating machine hierarchy ℳ\mathcal{M} consists of a Boolean program and a threshold h0≥4h_0 \ge 4 such that, for every height h≥h0h \ge h_0, the size of the program specialized to itself fits a computation tableau of address capacity 2h2^h, and satisfiability of that height-hh tableau’s Boolean clauses is equivalent to acceptance under the replacement and zero conditions of the height-DhDh rewriting table on words over ΣDh\Sigma_{Dh}.✦ Each height h≥h0h \ge h_0 determines a clause schedule at capacity 2h2^h and an induced word rewriting table 𝒯h\mathcal{T}_h over Σh\Sigma_h; over a ring KK, the machine hierarchy algebra Ah(K)A_h(K) is the quotient algebra K[Σh*]/I𝒯hK[\Sigma_h^*] / I_{\mathcal{T}_h} with qh=2hq_h = 2^h, and when KK is commutative the letter map λh,K:Σh→Ah(K)\lambda_{h,K} : \Sigma_h \to A_h(K) sends each a∈Σha \in \Sigma_h to (a)¯∈Ah(K)\overline{(a)} \in A_h(K) for the one-letter word (a)(a).

For a commutative ring KK, height h≥h0h \ge h_0, and integers d,b≥0d, b \ge 0, a dimension-dd chunk test (ι,Γ,ℓ,W)(\iota, \Gamma, \ell, W) of label bound bb at height hh over KK is a tuple consisting of a finite index set ι\iota with |ι|≤d|\iota| \le d, a finite chunk alphabet Γ\Gamma, a map ℓ:Γ→Σh*\ell : \Gamma \to \Sigma_h^* with each ℓ(c)\ell(c) nonempty and |ℓ(c)|≤b|\ell(c)| \le b, and W:Γ→Mι(K)W : \Gamma \to M_\iota(K). The chunk vanishing property for (ℳ,K,h,d,b)(\mathcal{M}, K, h, d, b) is the condition that (Σn(ℓ,W,λh,K))n≥0(\Sigma_n(\ell, W, \lambda_{h,K}))_{n \ge 0} eventually vanishes in Mι(Ah(K))M_\iota(A_h(K)) for every dimension-dd chunk test (ι,Γ,ℓ,W)(\iota, \Gamma, \ell, W) of label bound bb at height hh over KK.

The Claim

For a commutative ring KK of characteristic two, take a KK-module VV, an alphabet Γ\Gamma, d≥0d \ge 0, a finite set S⊆Γ*S \subseteq \Gamma^*, W:Γ→Md(K)W : \Gamma \to M_d(K), Φ:Γ*→V\Phi : \Gamma^* \to V, and an assignment s↦p(s)=(us,vs,zs)s \mapsto p(s) = (u_s, v_s, z_s) of packets over Γ\Gamma. Assume that for every s∈Ss \in S and every permutation σ\sigma of I|vs|I_{|v_s|}, one has usvszs=su_s v_s z_s = s, pairwise distinct entries in vsv_s, |vs|>d2|v_s| > d^2, p(s)σ∈Sp(s)^\sigma \in S, invariant key (us,zs,[vs])(u_s, z_s, [v_s]) for p(p(s)σ)p(p(s)^\sigma), and Φ(p(s)σ)=Φ(s)\Phi(p(s)^\sigma) = \Phi(s). Every matrix index pair i,j∈Idi, j \in I_d then satisfies (7): ∑s∈SW(s)ij⋅Φ(s)=0.\sum_{s \in S} W(s)_{ij} \cdot \Phi(s) = 0.(7)✦

Let BB be an algebra over a commutative ring KK of characteristic two, let Γ\Gamma be a finite chunk alphabet, let α\alpha and TT be alphabets, and fix d,b,n≥0d, b, n \ge 0. Given ℓ:Γ→α*\ell : \Gamma \to \alpha^* with each ℓ(c)\ell(c) nonempty and |ℓ(c)|≤b|\ell(c)| \le b, together with η:α→T\eta : \alpha \to T, ρ:T*→ℕ×ℕ\rho : T^* \to \mathbb{N} \times \mathbb{N}, W:Γ→Md(K)W : \Gamma \to M_d(K), and f:α→Bf : \alpha \to B, suppose that for every s∈Γ*s \in \Gamma^* with |ℓ*(s)|=n|\ell^*(s)| = n and evf(ℓ*(s))≠0\mathrm{ev}_f(\ell^*(s)) \neq 0, writing w=ℓ*(s)=(x0,…,xn−1)w = \ell^*(s) = (x_0, \dots, x_{n-1}) and (a,e)=ρ(η*(w))(a, e) = \rho(\eta^*(w)), one has e≤ne \le n, e−a>b(d2+3)e - a > b(d^2 + 3), pairwise distinct letters xa,…,xe−1x_a, \dots, x_{e-1}, and an element t∈Tt \in T such that η(xk)=t\eta(x_k) = t for a≤k<ea \le k < e and f(x)f(y)=f(y)f(x)f(x) f(y) = f(y) f(x) whenever η(x)=η(y)=t\eta(x) = \eta(y) = t. Then (8) holds for all i,j∈Idi, j \in I_d: Sn(ℓ,W,f)ij=0.S_n(\ell, W, f)_{ij} = 0.(8)✦

Keeping KK, BB, Γ\Gamma, α\alpha, TT, dd, bb, ℓ\ell, η\eta, and WW as in (8), let q,N≥0q, N \ge 0 satisfy 100b(d2+3)<q100 b (d^2 + 3) < q, let PP be a predicate on TT, and let f:α→Bf : \alpha \to B. Assume that f(x)f(y)=f(y)f(x)f(x) f(y) = f(y) f(x) whenever t∈Tt \in T satisfies PP and η(x)=η(y)=t\eta(x) = \eta(y) = t, that f(x)2=0f(x)^2 = 0 whenever η(x)\eta(x) satisfies PP, and that every word w∈α*w \in \alpha^* with |w|≥N|w| \ge N and evf(w)≠0\mathrm{ev}_f(w) \neq 0 admits a qq-eligible interval in η*(w)\eta^*(w) with respect to PP. For every n≥Nn \ge N and all i,j∈Idi, j \in I_d, the entrywise chunk sum satisfies (9): Sn(ℓ,W,f)ij=0.S_n(\ell, W, f)_{ij} = 0.(9)✦

Under the hypotheses of (9), for every n≥Nn \ge N the d×dd \times d matrix chunk sum in Md(B)M_d(B) satisfies (10): Σn(ℓ,W,f)=0.\Sigma_n(\ell, W, f) = 0.(10)✦

Replacing IdI_d by an arbitrary finite index set ι\iota, the bound 100b(d2+3)<q100 b (d^2 + 3) < q by 100b(|ι|2+3)<q100 b (|\iota|^2 + 3) < q, and WW by a map Γ→Mι(K)\Gamma \to M_\iota(K) while retaining all remaining hypotheses of (9), for every n≥Nn \ge N the matrix chunk sum in Mι(B)M_\iota(B) satisfies (11): Σn(ℓ,W,f)=0.\Sigma_n(\ell, W, f) = 0.(11)✦

Theorem 1. Let D≥2D \ge 2, let ℳ\mathcal{M} be a self-simulating machine hierarchy of dilation factor DD and threshold h0≥4h_0 \ge 4, let h≥h0h \ge h_0, let KK be a commutative ring of characteristic two, and let d,b≥0d, b \ge 0 satisfy 100b(d2+3)<2h100 b (d^2 + 3) < 2^h. Then for every dimension-dd chunk test (ι,Γ,ℓ,W)(\iota, \Gamma, \ell, W) of label bound bb at height hh over KK, there exists N≥0N \ge 0 such that (12) holds for all n≥Nn \ge N: Σn(ℓ,W,λh,K)=0\Sigma_n(\ell, W, \lambda_{h,K}) = 0(12)✦ in Mι(Ah(K))M_\iota(A_h(K)).

In the paper, the result reads: if qj/100>b(d2+3)q_j / 100 > b(d^2 + 3), then every dimension-dd chunk test of label bound bb at level jj eventually vanishes over every field of characteristic two, where hh and qh=2hq_h = 2^h stand for the paper’s jj and qjq_j.

What Is Checked

The main claim (12) is stated over a commutative ring KK of characteristic two, a self-simulating machine hierarchy ℳ\mathcal{M} of dilation factor D≥2D \ge 2 and threshold h0≥4h_0 \ge 4, a height h≥h0h \ge h_0, the rewriting-table algebra Ah(K)A_h(K) generated by Σh\Sigma_h via λh,K\lambda_{h,K}, and parameters d,b≥0d, b \ge 0 with 100b(d2+3)<2h100 b (d^2 + 3) < 2^h, while the general cancellation claims (7), (8), (9), (10), and (11) are stated over a commutative ring KK of characteristic two, an arbitrary KK-module VV or KK-algebra BB, and finite matrix-weighted chunk alphabets satisfying the packet, range, or eligible-interval hypotheses.