OctoInformBeta

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

Definition 3.1 [Weighted tests]: Word and chunk sums over semirings, and vanishing over any commutative ring from the hierarchy threshold upward for nonnegative bounds

Weighted matrix tests and eventual 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

Fix a commutative ring KK and a self-simulating machine hierarchy AA, together with an integer height hh at least the threshold of AA. At height hh, the hierarchy determines a finite alphabet Σh\Sigma_h of raw bitstrings and an associative unital algebra Ah(K)A_h(K) over KK generated by Σh\Sigma_h. Given matrix weights over KK assigned either to individual letters in Σh\Sigma_h or to bounded nonempty words over Σh\Sigma_h, the question is how to form the resulting weighted matrix sums of length n≥0n \ge 0 over Ah(K)A_h(K) and when every such matrix test of dimension at most d≥0d \ge 0 vanishes for all sufficiently large nn.

Rewriting Algebras and Matrix Weights

For an alphabet α\alpha, the free monoid of words α*\alpha^* is the free monoid generated by α\alpha under concatenation with identity the empty word ε\varepsilon; each word w∈α*w \in \alpha^* has length |w||w| and letters w1,…,w|w|w_1, \dots, w_{|w|}.✦ For a finite alphabet α\alpha and an integer n≥0n \ge 0, the set of candidate words α≤n⊆α*\alpha^{\le n} \subseteq \alpha^* is the finite set of all words over α\alpha of length at most nn, and the set of words of length nn, αn⊆α≤n\alpha^n \subseteq \alpha^{\le n}, is the subset of words of length nn. Given a map f:α→Bf : \alpha \to B from an alphabet α\alpha into a monoid BB, the word evaluation eval⁡(f,w)∈B\operatorname{eval}(f, w) \in B of a word w=(a1,…,ak)∈α*w = (a_1, \dots, a_k) \in \alpha^* is the product ∏r=1kf(ar)\prod_{r=1}^k f(a_r) in BB (taking the value 1∈B1 \in B on ε\varepsilon).✦ Given a chunk alphabet Γ\Gamma, an alphabet α\alpha, and a labeling map label⁡:Γ→α*\operatorname{label} : \Gamma \to \alpha^*, the spelled word spell⁡(label⁡,s)∈α*\operatorname{spell}(\operatorname{label}, s) \in \alpha^* of a chunk sequence s=(c1,…,ck)∈Γ*s = (c_1, \dots, c_k) \in \Gamma^* is the concatenation label⁡(c1)⋯label⁡(ck)\operatorname{label}(c_1) \cdots \operatorname{label}(c_k) (equal to ε\varepsilon when s=εs = \varepsilon).✦

For a semiring KK and an index set ι\iota, the matrix algebra Mι(K)M_\iota(K) is the set of ι×ι\iota \times \iota matrices over KK, which forms a semiring when ι\iota is finite, and for an integer d≥0d \ge 0, the matrix algebra Md(K)M_d(K) is Mι(K)M_\iota(K) with ι={0,…,d−1}\iota = \{0, \dots, d - 1\}. Given a chunk alphabet Γ\Gamma, a semiring KK, an integer d≥0d \ge 0, and a matrix weight map W:Γ→Md(K)W : \Gamma \to M_d(K), the chunk-sequence weight matrix ΠW(s)∈Md(K)\Pi_W(s) \in M_d(K) of a sequence s=(c1,…,ck)∈Γ*s = (c_1, \dots, c_k) \in \Gamma^* is the matrix product ∏r=1kW(cr)\prod_{r=1}^k W(c_r) (equal to the identity matrix IdI_d when s=εs = \varepsilon).✦ Given an index set ι\iota, sets KK and BB with a scalar action of KK on BB, a matrix X∈Mι(K)X \in M_\iota(K), and an element u∈Bu \in B, the tensor product X⊗u∈Mι(B)X \otimes u \in M_\iota(B) is the ι×ι\iota \times \iota matrix over BB defined entrywise by (1): (X⊗u)i,j=Xi,j⋅u(i,j∈ι).(X \otimes u)_{i,j} = X_{i,j} \cdot u \qquad (i, j \in \iota).(1)✦

For a semiring KK and an alphabet α\alpha, the monoid algebra of words K[α*]K[\alpha^*] is the monoid algebra of α*\alpha^* with coefficients in KK✦, and the basis monomial ew∈K[α*]e_w \in K[\alpha^*] of a word w∈α*w \in \alpha^* is the single-term element with coefficient 11 at ww.✦ For an alphabet α\alpha, a word rewriting table T=(∼T,ZT)T = (\sim_T, Z_T) over α\alpha consists of a binary replacement relation ∼T\sim_T on α*\alpha^* and a set of zero words ZT⊆α*Z_T \subseteq \alpha^*.✦ For a ring KK and a word rewriting table T=(∼T,ZT)T = (\sim_T, Z_T) over α\alpha, the defining two-sided ideal IT⊆K[α*]I_T \subseteq K[\alpha^*] is the two-sided ideal generated by the defining relations {ev−ew:v∼Tw}∪{ez:z∈ZT}\{e_v - e_w : v \sim_T w\} \cup \{e_z : z \in Z_T\}✦, and the table algebra K[α*]/ITK[\alpha^*]/I_T is the quotient ring of K[α*]K[\alpha^*] by ITI_T, equipped with the quotient homomorphism qT:K[α*]→K[α*]/ITq_T : K[\alpha^*] \to K[\alpha^*]/I_T assigning to each word w∈α*w \in \alpha^* its image [w]T=qT(ew)[w]_T = q_T(e_w).

For an integer h≥0h \ge 0, the raw bitstring alphabet Σh={0,1}10000h\Sigma_h = \{0, 1\}^{10000h} is the finite set of Boolean vectors of length 10000h10000h.✦ For an integer dilation factor D≥2D \ge 2, a self-simulating machine hierarchy AA consists of a binary program and an integer threshold h0≥4h_0 \ge 4 such that every integer h≥h0h \ge h_0 satisfies the layout parameter bounds for the self-specialized code of the program and the self-certification equivalence relating tableau satisfiability at height hh to the local verification table entry at height DhD h.✦ Given such a machine hierarchy AA, a commutative ring KK, and an integer h≥h0h \ge h_0, the hierarchy clause schedule for the self-specialized code produces a word rewriting table TA,hT_{A,h} over Σh\Sigma_h at data size 10000Dh10000 D h whose replacement relation and zero-word set encode the raw word replacement and zero-word conditions of that schedule✦, and the machine hierarchy algebra Ah(K)A_h(K) is the table algebra K[Σh*]/ITA,hK[\Sigma_h^*]/I_{T_{A,h}}.✦ At height h≥h0h \ge h_0 over a commutative ring KK for a machine hierarchy AA, the letter map ℓh:Σh→Ah(K)\ell_h : \Sigma_h \to A_h(K) assigns to each raw bitstring a∈Σha \in \Sigma_h the generator [(a)]TA,h[(a)]_{T_{A,h}} corresponding to the one-letter word (a)(a).✦

The Definition

Definition 1. For a finite alphabet α\alpha, a semiring ℛ\mathcal{R}, a map g:α→ℛg : \alpha \to \mathcal{R}, and an integer n≥0n \ge 0, the abstract letter sum Snabs(g)∈ℛS^{\mathrm{abs}}_n(g) \in \mathcal{R} is the element given by (2): Snabs(g)=∑w∈αneval⁡(g,w).S^{\mathrm{abs}}_n(g) = \sum_{w \in \alpha^n} \operatorname{eval}(g, w).(2)✦ When Γ\Gamma is a finite chunk alphabet, ℛ\mathcal{R} is a semiring, len⁡:Γ→ℤ≥0\operatorname{len} : \Gamma \to \mathbb{Z}_{\ge 0} is a length map, g:Γ→ℛg : \Gamma \to \mathcal{R} is a weight map, and m≥0m \ge 0 is an integer, the abstract chunk sum Cmabs(len⁡,g)∈ℛC^{\mathrm{abs}}_m(\operatorname{len}, g) \in \mathcal{R} is the element defined by (3): Cmabs(len⁡,g)=∑s∈Γ≤m∑r=1|s|len⁡(sr)=meval⁡(g,s).C^{\mathrm{abs}}_m(\operatorname{len}, g) = \sum_{\substack{s \in \Gamma^{\le m} \\ \sum_{r=1}^{|s|} \operatorname{len}(s_r) = m}} \operatorname{eval}(g, s).(3)✦ Given a finite index set ι\iota, a finite alphabet α\alpha, a semiring KK acting by scalars on a semiring BB, maps W:α→Mι(K)W : \alpha \to M_\iota(K) and f:α→Bf : \alpha \to B, and an integer n≥0n \ge 0, the matrix letter sum Sn(W,f)∈Mι(B)S_n(W, f) \in M_\iota(B) is the matrix over BB given by (4): Sn(W,f)=Snabs(a↦W(a)⊗f(a)).S_n(W, f) = S^{\mathrm{abs}}_n\bigl(a \mapsto W(a) \otimes f(a)\bigr).(4)✦ Take a finite index set ι\iota, a finite chunk alphabet Γ\Gamma, an alphabet α\alpha, a semiring KK acting by scalars on a semiring BB, maps label⁡:Γ→α*\operatorname{label} : \Gamma \to \alpha^*, W:Γ→Mι(K)W : \Gamma \to M_\iota(K), and f:α→Bf : \alpha \to B, and an integer n≥0n \ge 0; the matrix chunk sum Cn(label⁡,W,f)∈Mι(B)C_n(\operatorname{label}, W, f) \in M_\iota(B) is the matrix over BB defined by (5): Cn(label⁡,W,f)=Cnabs(c↦|label⁡(c)|,c↦W(c)⊗eval⁡(f,label⁡(c))).C_n(\operatorname{label}, W, f) = C^{\mathrm{abs}}_n\bigl(c \mapsto |\operatorname{label}(c)|,\; c \mapsto W(c) \otimes \operatorname{eval}(f, \operatorname{label}(c))\bigr).(5)✦ At matrix dimension d≥0d \ge 0, with a finite chunk alphabet Γ\Gamma, an alphabet α\alpha, a semiring KK acting by scalars on a semiring BB, maps label⁡:Γ→α*\operatorname{label} : \Gamma \to \alpha^*, W:Γ→Md(K)W : \Gamma \to M_d(K), and f:α→Bf : \alpha \to B, an integer n≥0n \ge 0, and indices 0≤i,j<d0 \le i, j < d, the chunk sum matrix entry Cnentry(label⁡,W,f)i,j∈BC^{\mathrm{entry}}_n(\operatorname{label}, W, f)_{i,j} \in B is the element of BB defined by (6): Cnentry(label⁡,W,f)i,j=∑s∈Γ≤n|spell⁡(label⁡,s)|=nΠW(s)i,j⋅eval⁡(f,spell⁡(label⁡,s)).C^{\mathrm{entry}}_n(\operatorname{label}, W, f)_{i,j} = \sum_{\substack{s \in \Gamma^{\le n} \\ |\operatorname{spell}(\operatorname{label}, s)| = n}} \Pi_W(s)_{i,j} \cdot \operatorname{eval}\bigl(f, \operatorname{spell}(\operatorname{label}, s)\bigr).(6)✦ Let AA be a self-simulating machine hierarchy with threshold h0≥4h_0 \ge 4, let KK be a commutative ring, and let h≥h0h \ge h_0 be an integer; an integer dimension bound d≥0d \ge 0 satisfies the letter vanishing condition over KK at height hh if for every finite index set ι\iota with |ι|≤d|\iota| \le d and every weight map W:Σh→Mι(K)W : \Sigma_h \to M_\iota(K), there exists an integer N≥0N \ge 0 satisfying (7): Sn(W,ℓh)=0for all n≥N.S_n(W, \ell_h) = 0 \qquad \text{for all } n \ge N.(7)✦ Fix a self-simulating machine hierarchy AA with threshold h0≥4h_0 \ge 4, a commutative ring KK, and an integer h≥h0h \ge h_0; a dimension bound d≥0d \ge 0 and a label bound b≥0b \ge 0 satisfy the chunk vanishing condition over KK at height hh if for every finite index set ι\iota with |ι|≤d|\iota| \le d, every finite chunk alphabet Γ\Gamma, every labeling map label⁡:Γ→Σh*\operatorname{label} : \Gamma \to \Sigma_h^* satisfying 1≤|label⁡(c)|≤b1 \le |\operatorname{label}(c)| \le b for all c∈Γc \in \Gamma, and every weight map W:Γ→Mι(K)W : \Gamma \to M_\iota(K), there exists an integer N≥0N \ge 0 satisfying (8): Cn(label⁡,W,ℓh)=0for all n≥N.C_n(\operatorname{label}, W, \ell_h) = 0 \qquad \text{for all } n \ge N.(8)✦

In the paper, the result reads: a letter test of dimension d≥1d \ge 1 at level jj assigns M(a)∈Md(K)M(a) \in M_d(K) to each a∈Σja \in \Sigma_j with length-nn sum Sj,n(M)=∑w∈ΣjnM(w)⊗[w]jS_{j,n}(M) = \sum_{w \in \Sigma_j^n} M(w) \otimes [w]_j, a chunk test of dimension dd and label bound b≥1b \ge 1 has finite identifiers 𝒞\mathcal{C}, nonempty labels vγ∈Σj*v_\gamma \in \Sigma_j^* with |vγ|≤b|v_\gamma| \le b, and weights Wγ∈Md(K)W_\gamma \in M_d(K) with length-nn sum Cj,n(𝒞,W)C_{j,n}(\mathcal{C}, W), and a test eventually vanishes if its length-nn sum is zero for all sufficiently large nn (with hh for jj, Σh\Sigma_h for Σj\Sigma_j, Γ\Gamma for 𝒞\mathcal{C}, label\operatorname{label} for γ↦vγ\gamma \mapsto v_\gamma, WW for MM and γ↦Wγ\gamma \mapsto W_\gamma, eval⁡(M,w)\operatorname{eval}(M, w) for M(w)M(w), eval⁡(ℓh,w)\operatorname{eval}(\ell_h, w) for [w]j[w]_j, SnS_n for Sj,nS_{j,n}, and CnC_n for Cj,nC_{j,n}). Whereas the paper defines these tests individually for d,b≥1d, b \ge 1, the library’s definitions build the matrix sums from abstract word and chunk sums over semirings, allow any d,b≥0d, b \ge 0 and finite index sets ι\iota with |ι|≤d|\iota| \le d, and quantify vanishing universally over all weight maps and bounded nonempty labelings at height h≥h0h \ge h_0.

What Is Checked

The weighted sums and vanishing conditions are stated over finite alphabets, semirings with scalar actions, finite matrix index sets, table algebras of word rewriting tables, and, for eventual vanishing, a commutative ring KK, a self-simulating machine hierarchy AA with dilation factor D≥2D \ge 2 and threshold h0≥4h_0 \ge 4, an integer height h≥h0h \ge h_0, the raw bitstring alphabet Σh\Sigma_h, the hierarchy algebra Ah(K)A_h(K) with its letter map ℓh\ell_h, and nonnegative bounds dd and bb.