OctoInformBeta

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

Theorem 3.7: Polynomial length gradings, finite relations for h≥4h \ge 4, infinite hierarchy algebras, and matrix nilpotence in characteristic 22 for D>10(10000+1)(10+1)D > 10(10000+1)(10+1)

A concrete machine 𝔽2\mathbb{F}_2-algebra has a matrix-nil augmentation kernel.

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

Take a unital associative algebra RR over 𝔽2\mathbb{F}_2 equipped with an augmentation homomorphism ε:R→𝔽2\varepsilon : R \to \mathbb{F}_2. Can RR be infinite and finitely presented while carrying a length grading and satisfying the condition that every finite square matrix over ker⁡ε\ker \varepsilon is nilpotent? A self-simulating Turing machine whose local verification transitions form a rewriting system over binary strings yields an algebra of this kind. These notes set out the definitions behind that construction and the theorem stated over them.

Word Rewriting Algebras and Matrix Nilpotence

For an alphabet α\alpha, the free monoid of words α*\alpha^* is the free monoid generated by α\alpha, with empty word 11 and word length |w||w| for w∈α*w \in \alpha^*.✦ Given a map f:α→Sf : \alpha \to S into a monoid SS, the word evaluation eval⁡f(w)\operatorname{eval}_f(w) of w=a1⋯am∈α*w = a_1 \cdots a_m \in \alpha^* is the product f(a1)⋯f(am)f(a_1) \cdots f(a_m) in SS, with eval⁡f(1)=1\operatorname{eval}_f(1) = 1.✦

Over a semiring KK and an alphabet α\alpha, the monoid algebra of words K⟨α⟩K\langle\alpha\rangle is the monoid algebra K[α*]K[\alpha^*].✦ Inside K⟨α⟩K\langle\alpha\rangle, the basis monomial mwm_w of a word w∈α*w \in \alpha^* is the single-term element with coefficient 11 at ww and 00 elsewhere.✦

A word rewriting table T=(repT,ZT)T = (\mathrel{\mathrm{rep}}_T, Z_T) over an alphabet α\alpha is a pair consisting of a binary replacement relation repT\mathrel{\mathrm{rep}}_T on α*\alpha^* and a subset ZT⊆α*Z_T \subseteq \alpha^* of zero words.✦ For a ring KK, the defining relations ℛ(T,K)\mathcal{R}(T, K) in K⟨α⟩K\langle\alpha\rangle form the subset ℛ(T,K)={mv−mw:v,w∈α*,vrepTw}∪{mz:z∈ZT}.\mathcal{R}(T, K) = \{ m_v - m_w : v, w \in \alpha^*,\; v \mathrel{\mathrm{rep}}_T w \} \cup \{ m_z : z \in Z_T \}.(1)✦ The defining two-sided ideal I(T,K)I(T, K) of TT over KK is the two-sided ideal of K⟨α⟩K\langle\alpha\rangle generated by ℛ(T,K)\mathcal{R}(T, K) in (1). The table algebra A(T,K)A(T, K) of TT over KK is the quotient ring A(T,K)=K⟨α⟩/I(T,K).A(T, K) = K\langle\alpha\rangle / I(T, K).(2)✦ The algebra quotient map qT,K:K⟨α⟩→A(T,K)q_{T, K} : K\langle\alpha\rangle \to A(T, K) of the table algebra A(T,K)A(T, K) is the quotient homomorphism onto (2), and the word image w‾\bar{w} in A(T,K)A(T, K) of w∈α*w \in \alpha^* is qT,K(mw)q_{T, K}(m_w).✦

Call a word rewriting table TT over α\alpha homogeneous when |v|=|w||v| = |w| for all words satisfying vrepTwv \mathrel{\mathrm{rep}}_T w.✦ For an alphabet α\alpha and a ring KK, the free-monoid augmentation α*→K\alpha^* \to K is the monoid homomorphism sending every letter of α\alpha to 00.✦ When TT is homogeneous and 1∉ZT1 \notin Z_T, the table algebra augmentation εT:A(T,K)→K\varepsilon_T : A(T, K) \to K is a KK-algebra homomorphism for any commutative ring KK.✦

Given a word rewriting table TT over α\alpha and a commutative ring KK, the word grading homomorphism α*→A(T,K)[X]\alpha^* \to A(T, K)[X] is the monoid homomorphism mapping each word w∈α*w \in \alpha^* to w‾X|w|\bar{w} X^{|w|}.✦ When TT is homogeneous, the algebra grading homomorphism γT\gamma_T is a KK-algebra homomorphism γT:A(T,K)→A(T,K)[X].\gamma_T : A(T, K) \to A(T, K)[X].(3)✦

Given a ring SS and a ring homomorphism ε:S→𝔽2\varepsilon : S \to \mathbb{F}_2, the kernel ker⁡ε\ker \varepsilon is matrix-nil (and Mn(ker⁡ε)M_n(\ker \varepsilon) is nil for every integer n≥0n \ge 0) if for every integer n≥0n \ge 0, every matrix M∈Mn(S)M \in M_n(S) whose entries satisfy ε(Mij)=0\varepsilon(M_{ij}) = 0 satisfies Mk=0M^k = 0 for some integer k≥1k \ge 1.✦

Finite-table Rewriting and Bitstring Coding

A verification task t=(r,Z)t = (r, Z) is a pair consisting of a block arity r∈{0,…,9}r \in \{0, \dots, 9\} and a Boolean zero-task flag ZZ.✦ Given an integer capacity q≥0q \ge 0, a cell memory address is either a data address (s,b,p)(s, b, p) with side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, block index b∈{0,…,9}b \in \{0, \dots, 9\}, and position p<qp < q, or a certificate address p<qp < q.✦ Over {0,1,2}\{0, 1, 2\}, a three-bit register is a map {0,1,2}→𝔽2\{0, 1, 2\} \to \mathbb{F}_2.✦ 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 three-bit registers. A verification clause schedule SS of capacity qq is a family assigning to each verification task tt a clause count cS(t)c_S(t) satisfying 0<cS(t)≤q0 < c_S(t) \le q and a family of verification clauses indexed by tt and j<qj < q.✦

Each block metadata record consists of an arity r<10r < 10, a zero-task flag ZZ, and a block index b≤rb \le r, with task projection (r,Z)(r, Z). A cell syntactic skeleton of capacity qq consists of a position (core p<qp < q, palette color c<qc < q, or stop), a marker (idle, left wing, boundary, full, or right wing), and a block metadata record.✦ A cell syntactic skeleton of capacity qq is admissible when no initial skeleton (b=0b = 0 at core 00) has the right-wing marker and no terminal skeleton (b=rb = r at stop) has the left-wing marker, and it carries an active head when its marker is boundary or full.✦ Over colors below qq, a palette checker state is idle, passed seeking a color, or an active head seeking a color.✦ A reading head state of capacity qq records a side bit, a clause index j<qj < q, a three-bit register, and one of nine head computation phases (acquisition, left read, right read, before-gate, after-gate, left undo, right undo, finish, or success), among which acquisition, before-gate, after-gate, finish, and success are the endpoint phases.

A finite-table cell of capacity qq consists of a syntactic skeleton, a palette checker state, side-indexed data bits in 𝔽2\mathbb{F}_2, a certificate bit in 𝔽2\mathbb{F}_2, and a reading head state; such a cell is head-free if its skeleton carries no active head marker and its checker is not a checker head.✦ Reading a cell memory address from a cell cc returns its data bit on matching core position and block, its certificate bit on matching core position at block 00, and 00 elsewhere, so each verification clause yields a three-bit register delta from cc. For a schedule SS of capacity qq and data size d≥0d \ge 0, a finite-table cell cc of capacity qq satisfies the cell formatting condition if its skeleton is admissible, its checker is idle off palette positions, its data and certificate bits vanish off the core (with data bits vanishing at core positions p≥dp \ge d), and its marker constrains its metadata and head fields: idle cells carry arity 00, zero-task flag false\mathrm{false}, block 00, side false\mathrm{false}, clause 00, acquisition phase, zero register, zero true-side data, and zero certificate; left and right wings carry side false\mathrm{false}, clause 00, acquisition phase, and zero register; boundary cells carry clause 00, acquisition phase, and zero register; active heads with zero-task metadata take side false\mathrm{false}; and full cells take clause 00 in success, a clause below cS(r,Z)c_S(r, Z) otherwise, and terminal skeletons at endpoint phases.✦

Two finite-table cells aa and bb of capacity qq form a compatible adjacent cell pair when their positions are adjacent (core pp before p+1p+1, core q−1q-1 before palette, palette before palette or stop, or stop before core 00), their external or internal markers and block metadata agree across the boundary, and their palette checkers satisfy adjacent and terminal compatibility.✦ The symmetric cell-list replacement relation on formatted singletons and pairs is generated by twelve unary transitions at block ends and eight binary transitions on adjacent pairs: they sweep a reading head across a block to accumulate clause register deltas, test the clause truth function at the before-gate phase, advance clauses to success and pivot the side flag for nonzero tasks, create or advance palette checker heads, and swap head-free palette cells.✦ On a single finite-table cell cc of capacity qq, the unary zero condition for SS and dd holds if cc fails formatting, exhibits a semantic failure (nonzero register at acquisition, finish, or success, false clause evaluation at after-gate, or success on a zero-task cell), or has a palette color xx already marked passed xx.✦ On two finite-table cells aa and bb of capacity qq, the binary zero condition holds if they do not form a compatible adjacent pair, repeat the same palette color, or place a palette checker head seeking y≠xy \neq x at color xx immediately before stop.✦

For an integer h>0h > 0 and capacity qh=2hq_h = 2^h, a raw bitstring of height hh is a Boolean vector of length 10000h10000h, and the set of such bitstrings is denoted Rawh\mathrm{Raw}_h.✦ The cell encoding map sends each finite-table cell of capacity qhq_h to 3232 binary slots of 2h2h bits and 512512 flag bits in Rawh\mathrm{Raw}_h, and cell decoding recovers a cell from w∈Rawhw \in \mathrm{Raw}_h when re-encoding yields ww, extending letterwise to words in Rawh*\mathrm{Raw}_h^*. The raw replacement relation and the raw zero predicate on Rawh*\mathrm{Raw}_h^* are obtained by lifting cell-list replacement and the unary and binary zero conditions to decoded words, marking undecodable singletons as zero and rejecting lengths other than 11 and 22. Given an integer h>0h > 0, a schedule SS of capacity qhq_h, and data size d≥0d \ge 0, the codec algebra table Th,S,dT_{h,S,d} over Rawh\mathrm{Raw}_h is the word rewriting table with the raw replacement relation and the raw zero predicate (with single-letter generators a↦a‾∈A(Th,S,d,K)a \mapsto \bar{a} \in A(T_{h,S,d}, K) for any ring KK) together with a Boolean table entry selector testing either zero-word membership or replacement.

Self-simulating Machine Hierarchies

Over a tape alphabet Γ\Gamma and state set QQ, a tape cell label records a symbol in Γ\Gamma, a Boolean origin mark, and an optional active head state in QQ.✦ A Turing machine transition function δ\delta sends each state and symbol to a command specifying a written symbol, a next state, and a head motion (left, stay, or right), defining a local three-cell update rule on adjacent tape labels. Using three stack registers (source, destination, and auxiliary), a stack machine compiler translates a stack program on multi-track tape symbols into a one-tape Turing machine, yielding a concrete timed tape transition function δ\delta over a finite alphabet Γ\Gamma and finite state set QQ that interprets a universal stack machine fed by a prefix-wrapper decoder and an input decoder reading fixed-width bit packets (whose packet bit width is the cardinality of the set of optional universal stack tokens).

When Γ\Gamma and QQ are finite, a binary tape label coding of bit width b>0b > 0 encodes tape cell labels as bb-bit Boolean vectors with a left inverse✦, and the one-hot coding of Γ\Gamma and QQ fixes a coding of bit width β\beta. Given an input count II and gate count kk, a combinational not-and (NAND) circuit is an ordered sequence of kk two-input NAND gates wired from the II inputs and earlier gates, generating 3k3k three-wire circuit clauses; a circuit realization of the encoded 3β3\beta-bit local transition function fixes a gate count gg and a combinational NAND circuit with β\beta output wires evaluating δ\delta.

Take parameters q,b,k,T,Wq, b, k, T, W with b>0b > 0, T>0T > 0, W≥3W \ge 3, an origin column o<Wo < W, and capacity qq bounding both the certificate variable count bWT+k(W−2)(T−1)b W T + k(W - 2)(T - 1) and the tableau clause count 2bW+2b(T−1)+(3k+2b)(W−2)(T−1)+b2b W + 2b(T - 1) + (3k + 2b)(W - 2)(T - 1) + b. An addressable tableau layout assigns cell memory addresses to T×WT \times W tape cells of bb bits and (T−1)×(W−2)(T - 1) \times (W - 2) gate blocks of kk bits, and compiles a schedule of three-wire verification clauses enforcing the initial row, blank boundaries, local NAND transitions, and accepting origin bits against a Boolean assignment assembled from data addresses and a certificate vector in {false,true}q\{\mathrm{false}, \mathrm{true}\}^q. For a natural number mm, let binSize⁡(m)\operatorname{binSize}(m) be 11 if m=0m = 0 and the binary bit length of mm otherwise✦, let enc⁡(m)\operatorname{enc}(m) be its prefix-free encoding (binSize⁡(m)\operatorname{binSize}(m) true bits, one false delimiter, and the binary digits of mm)✦, and for Boolean words tt and vv, let program specialization specialize⁡(t,v)\operatorname{specialize}(t, v) prepend a true bit to enc⁡(|t|)tenc⁡(|v|)v\operatorname{enc}(|t|) \, t \, \operatorname{enc}(|v|) \, v.✦

Given bit width bb, gate count kk, dilation DD, height hh, and code length nn, with T=2⌊h/5⌋T = 2^{\lfloor h/5 \rfloor} and W=4TW = 4T, the layout parameter bounds predicate Fits⁡(b,k,D,h,n)\operatorname{Fits}(b, k, D, h, n) requires 64h+512≤10000h64h + 512 \le 10000h, 10≤22h10 \le 2^{2h}, 2h≤22h2^h \le 2^{2h}, 10000Dh≤2h10000 D h \le 2^h, both the certificate and clause counts to be at most 2h2^h, and n+2binSize⁡(n)+2binSize⁡(Dh)+12+20(10000Dh)<⌊T/4⌋.n + 2\operatorname{binSize}(n) + 2\operatorname{binSize}(Dh) + 12 + 20(10000 D h) < \lfloor T/4 \rfloor.(4)✦ When Fits⁡(β,g,D,h,|a|)\operatorname{Fits}(\beta, g, D, h, |a|) holds for a Boolean program aa and 10000Dh>010000 D h > 0, the source machine clause schedule S(a,D,h)S(a, D, h) of capacity qh=2hq_h = 2^h instantiates the tableau layout at origin 2T2T with the local NAND circuit, the one-hot encodings of the timed tape blank label, initial origin label, accepting output label, and Boolean bit labels, and the initial input row encoding aa, DhD h, and for each verification task t=(r,Z)t = (r, Z) the arity r+1r + 1, zero-task flag ZZ, and the data addresses.✦

For an integer dilation D≥2D \ge 2, a self-simulating machine hierarchy AA consists of a Boolean program pAp_A and a threshold height h0(A)≥4h_0(A) \ge 4 such that the self-specialized code aA=specialize⁡(pA,pA)a_A = \operatorname{specialize}(p_A, p_A) satisfies Fits⁡(β,g,D,h,|aA|)\operatorname{Fits}(\beta, g, D, h, |a_A|) from (4) at every height h≥h0(A)h \ge h_0(A), and for every verification task t=(r,Z)t = (r, Z) and every Boolean assignment 𝑑𝑎𝑡𝑎\mathit{data} on data bit addresses of capacity qh=2hq_h = 2^h, there exists a certificate vector satisfying every clause of S(aA,D,h)S(a_A, D, h) under the assembled assignment if and only if the codec table entry selector for S(aA,D,Dh)S(a_A, D, Dh) at height DhDh and data size 10000D2h10000 D^2 h accepts the candidate raw words of length r+1r + 1 in RawDh*\mathrm{Raw}_{Dh}^* extracted from 𝑑𝑎𝑡𝑎\mathit{data} (testing the false-side word under the raw zero predicate when Z=trueZ = \mathrm{true}, and the pair of false-side and true-side words under the raw replacement relation when Z=falseZ = \mathrm{false}).✦ Every integer D≥2D \ge 2 admits a self-simulating machine hierarchy of dilation DD.✦

Given a self-simulating machine hierarchy AA of dilation D≥2D \ge 2 and an integer h≥h0(A)h \ge h_0(A), let SA,h=S(aA,D,h)S_{A,h} = S(a_A, D, h) be the hierarchy clause schedule✦ and TA(h)=Th,SA,h,10000DhT_A(h) = T_{h, S_{A,h}, 10000 D h} be the hierarchy rewriting table over Rawh\mathrm{Raw}_h.✦ For any ring KK, the machine hierarchy algebra Ah(K)A_h(K) is the table algebra Ah(K)=A(TA(h),K).A_h(K) = A(T_A(h), K).(5)✦ For every h≥h0(A)h \ge h_0(A), the hierarchy rewriting table TA(h)T_A(h) is homogeneous✦ and every word in its zero set is nonempty✦, so every commutative ring KK yields a KK-algebra augmentation εA,h,K:Ah(K)→K\varepsilon_{A,h,K} : A_h(K) \to K.✦ Letting ℓA,h,K:Rawh→Ah(K)\ell_{A,h,K} : \mathrm{Raw}_h \to A_h(K) send each raw bitstring to its single-letter generator in (5), the positive span Ph(K)⊆Ah(K)P_h(K) \subseteq A_h(K) is the KK-submodule Ph(K)=span⁡K{eval⁡ℓA,h,K(w):w∈Rawh*,w≠1}.P_h(K) = \operatorname{span}_K \{ \operatorname{eval}_{\ell_{A,h,K}}(w) : w \in \mathrm{Raw}_h^*,\; w \neq 1 \}.(6)✦

The Concrete Algebra

Fix the concrete dilation factor D0=10(10000+1)(10+1)+1D_0 = 10(10000+1)(10+1)+1✦, let A0A_0 be the concrete self-simulating machine hierarchy of dilation D0D_0✦, and let h0=h0(A0)h_0 = h_0(A_0) be its threshold height.✦ The concrete algebra RR is the machine hierarchy algebra of A0A_0 over 𝔽2\mathbb{F}_2 at height h0h_0, R=(A0)h0(𝔽2).R = (A_0)_{h_0}(\mathbb{F}_2).(7)✦ The augmentation ε:R→𝔽2\varepsilon : R \to \mathbb{F}_2 of RR in (7) is the hierarchy augmentation εA0,h0,𝔽2\varepsilon_{A_0, h_0, \mathbb{F}_2}.✦ The grading homomorphism γ\gamma of RR is the 𝔽2\mathbb{F}_2-algebra homomorphism obtained by applying (3) to TA0(h0)T_{A_0}(h_0) over 𝔽2\mathbb{F}_2, γ=γTA0(h0):R→R[X].\gamma = \gamma_{T_{A_0}(h_0)} : R \to R[X].(8)✦

The Claim

Theorem 1. For the concrete 𝔽2\mathbb{F}_2-algebra RR with augmentation ε:R→𝔽2\varepsilon : R \to \mathbb{F}_2 and every integer n≥0n \ge 0, Mn(ker⁡ε) is nil.M_n(\ker \varepsilon) \text{ is nil}.(9)✦ For any self-simulating machine hierarchy AA with dilation D>10(10000+1)(10+1)D > 10(10000+1)(10+1), any integer h≥h0(A)h \ge h_0(A), and every integer n≥0n \ge 0, Mn(ker⁡εA,h,𝔽2) is nil.M_n(\ker \varepsilon_{A,h,\mathbb{F}_2}) \text{ is nil}.(10)✦ If AA is a self-simulating machine hierarchy with dilation D>10(10000+1)(10+1)D > 10(10000+1)(10+1), h≥h0(A)h \ge h_0(A), KK is a commutative ring of characteristic 22, and M∈Mι(Ah(K))M \in M_\iota(A_h(K)) is a matrix over a finite index set ι\iota with all entries in the positive span Ph(K)P_h(K) of (6), then Mk=0for some integer k≥1.M^k = 0 \quad \text{for some integer } k \ge 1.(11)✦ For any self-simulating machine hierarchy AA of dilation D≥2D \ge 2, any nontrivial ring KK, and any integer h≥h0(A)h \ge h_0(A), |Ah(K)|=∞.|A_h(K)| = \infty.(12)✦ For every integer h≥4h \ge 4, every verification clause schedule SS of capacity qh=2hq_h = 2^h, every integer d≥0d \ge 0, and every ring KK, |ℛ(Th,S,d,K)|<∞.|\mathcal{R}(T_{h,S,d}, K)| < \infty.(13)✦

In the paper, the result reads: there is an infinite, finitely presented, graded unital associative 𝔽2\mathbb{F}_2-algebra R=⨁n≥0Rn=𝔽2⊕IR = \bigoplus_{n \ge 0} R_n = \mathbb{F}_2 \oplus I (R0=𝔽2R_0 = \mathbb{F}_2, I=⨁n≥1RnI = \bigoplus_{n \ge 1} R_n) such that Mℓ(I)M_\ell(I) is nil for every integer ℓ≥1\ell \ge 1, where II stands for ker⁡ε\ker \varepsilon. Instead of decomposing RR as a direct sum ⨁n≥0Rn\bigoplus_{n \ge 0} R_n, the library equips RR with the polynomial-valued grading (8) and formulates the remaining properties through (9), (10), (11), (12), and (13).

What Is Checked

Claim (9) is stated over the concrete 𝔽2\mathbb{F}_2-algebra RR of (7) and its augmentation ε:R→𝔽2\varepsilon : R \to \mathbb{F}_2 at threshold height h0h_0 of the machine hierarchy A0A_0 with dilation D0=10(10000+1)(10+1)+1D_0 = 10(10000+1)(10+1)+1. Claims (10), (11), and (12) are stated over an arbitrary self-simulating machine hierarchy AA of dilation D≥2D \ge 2 and height h≥h0(A)h \ge h_0(A), with D>10(10000+1)(10+1)D > 10(10000+1)(10+1) for (10) and (11), a commutative ring KK of characteristic 22 and the positive span (6) for (11), and a nontrivial ring KK for (12). Claim (13) is stated over any integer h≥4h \ge 4, verification clause schedule SS of capacity qh=2hq_h = 2^h, integer d≥0d \ge 0, and ring KK, while (3) and (8) are defined for homogeneous word rewriting tables and for TA0(h0)T_{A_0}(h_0).

For those constructions, the library also establishes that D0≥2D_0 \ge 2✦, that hh and 10000Dh10000 D h are positive for all h≥h0(A)h \ge h_0(A), and that the coding bit width β\beta and the input-decoder packet bit width are positive, as is the tableau clause count of any layout.✦