OctoInformBeta

OpenAI preprint, September 2026 · §4. An ordinary finite presentation for the Steinberg group

Theorem 4.1 [Finite presentation of the Steinberg group]: Explicit presentation over free 𝔽2\mathbb{F}_2-algebras for rank n≥5n \ge 5 and finite presentation of quotient Steinberg groups and the rank-twelve group

Finite presentation of Steinberg groups over quotient algebras.

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 an integer n≥5n \ge 5, a finite alphabet α\alpha, and a finitely generated two-sided ideal in the free associative algebra on α\alpha over the two-element field 𝔽2\mathbb{F}_2. Even when the resulting quotient algebra is infinite, the question is whether its Steinberg group of rank nn is finitely presented, and whether the same holds in rank twelve over the concrete coordinate ring built from a self-simulating machine hierarchy. These notes go through the finite presentation theorems and the definitions they are built on.

Steinberg Groups and the Free Presentation

In any group GG, the commutator [x,y][x, y] of two elements x,y∈Gx, y \in G is the element xyx−1y−1x y x^{-1} y^{-1}.✦ For a natural number nn, a root p=(i,j)p = (i, j) of rank nn is an ordered pair of distinct indices i,j∈{0,…,n−1}i, j \in \{0, \dots, n - 1\} with row prow=ip_{\mathrm{row}} = i and column pcol=jp_{\mathrm{col}} = j; the set of all roots of rank nn is denoted Root⁡(n)\operatorname{Root}(n).✦

Let BB be a unital associative ring. A Steinberg generator pair (p,a)(p, a) of rank nn over BB is an element of Root⁡(n)×B\operatorname{Root}(n) \times B, and its canonical image in the free group F(Root⁡(n)×B)F(\operatorname{Root}(n) \times B) is denoted x̃p(a)\tilde{x}_p(a) (or x̃ij(a)\tilde{x}_{ij}(a) when p=(i,j)p = (i, j)).✦ The Steinberg group relations in F(Root⁡(n)×B)F(\operatorname{Root}(n) \times B) form the subset consisting of the relators x̃p(a+b)(x̃p(a)x̃p(b))−1,[x̃p(a),x̃q(b)],[x̃ij(a),x̃jk(b)]x̃ik(ab)−1,\tilde{x}_p(a + b)\bigl(\tilde{x}_p(a)\tilde{x}_p(b)\bigr)^{-1}, \qquad [\tilde{x}_p(a), \tilde{x}_q(b)], \qquad [\tilde{x}_{ij}(a), \tilde{x}_{jk}(b)]\,\tilde{x}_{ik}(ab)^{-1},(1)✦ for all a,b∈Ba, b \in B, every root p∈Root⁡(n)p \in \operatorname{Root}(n), all pairs p,q∈Root⁡(n)p, q \in \operatorname{Root}(n) with pcol≠qrowp_{\mathrm{col}} \ne q_{\mathrm{row}} and prow≠qcolp_{\mathrm{row}} \ne q_{\mathrm{col}}, and all pairwise distinct indices i,j,k∈{0,…,n−1}i, j, k \in \{0, \dots, n - 1\}. The Steinberg group St⁡n(B)\operatorname{St}_n(B) is the quotient of F(Root⁡(n)×B)F(\operatorname{Root}(n) \times B) by the normal closure of the relators (1)✦; for p=(i,j)∈Root⁡(n)p = (i, j) \in \operatorname{Root}(n) and a∈Ba \in B, the Steinberg generator xp(a)=xij(a)∈St⁡n(B)x_p(a) = x_{ij}(a) \in \operatorname{St}_n(B) is the image of x̃p(a)\tilde{x}_p(a).✦

By the universal property of St⁡n(B)\operatorname{St}_n(B), if a map f:Root⁡(n)×B→Gf : \operatorname{Root}(n) \times B \to G into a group GG satisfies f(p,a+b)=f(p,a)f(p,b)f(p, a + b) = f(p, a)f(p, b) for all pp and a,b∈Ba, b \in B, the elements f(p,a)f(p, a) and f(q,b)f(q, b) commute whenever pcol≠qrowp_{\mathrm{col}} \ne q_{\mathrm{row}} and prow≠qcolp_{\mathrm{row}} \ne q_{\mathrm{col}}, and [f((i,j),a),f((j,k),b)]=f((i,k),ab)[f((i, j), a), f((j, k), b)] = f((i, k), ab) for all pairwise distinct i,j,ki, j, k and a,b∈Ba, b \in B, then ff descends to a group homomorphism St⁡n(B)→G\operatorname{St}_n(B) \to G sending xp(a)x_p(a) to f(p,a)f(p, a).✦ For any ring homomorphism ρ:B→B′\rho : B \to B', the induced Steinberg homomorphism St⁡n(ρ):St⁡n(B)→St⁡n(B′)\operatorname{St}_n(\rho) : \operatorname{St}_n(B) \to \operatorname{St}_n(B') is the group homomorphism sending each generator xp(a)x_p(a) to xp(ρ(a))x_p(\rho(a)).✦

For an alphabet α\alpha, the free monoid of words over α\alpha is denoted α*\alpha^*, and the length of a word w∈α*w \in \alpha^* is denoted |w||w|.✦ For a unital semiring KK, the monoid algebra K⟨α⟩K\langle\alpha\rangle is the free associative KK-algebra on α\alpha✦, and for each word w∈α*w \in \alpha^*, the basis monomial [w]∈K⟨α⟩[w] \in K\langle\alpha\rangle is the single-term element with coefficient 11 at ww✦; over 𝔽2\mathbb{F}_2, we write P=𝔽2⟨α⟩P = \mathbb{F}_2\langle\alpha\rangle.✦

A short word ww over an alphabet α\alpha is a word of α*\alpha^* with |w|≤2|w| \le 2, and the Steinberg presentation generating set Gen⁡(n,α)\operatorname{Gen}(n, \alpha) is the product of Root⁡(n)\operatorname{Root}(n) with the set of short words over α\alpha.✦ Writing g̃p(w)\tilde{g}_p(w) for the free generator (p,w)(p, w) in the free group F(Gen⁡(n,α))F(\operatorname{Gen}(n, \alpha)), the Steinberg presentation relations form the subset of F(Gen⁡(n,α))F(\operatorname{Gen}(n, \alpha)) consisting of the relators g̃p(w)2,[g̃p(u),g̃q(v)],[g̃ij(u),g̃jk(v)]g̃ik(uv)−1,\tilde{g}_p(w)^2, \qquad [\tilde{g}_p(u), \tilde{g}_q(v)], \qquad [\tilde{g}_{ij}(u), \tilde{g}_{jk}(v)]\,\tilde{g}_{ik}(uv)^{-1},(2)✦ for all p,q∈Root⁡(n)p, q \in \operatorname{Root}(n) with pcol≠qrowp_{\mathrm{col}} \ne q_{\mathrm{row}} and prow≠qcolp_{\mathrm{row}} \ne q_{\mathrm{col}}, all pairwise distinct i,j,k∈{0,…,n−1}i, j, k \in \{0, \dots, n - 1\}, and all short words w,u,vw, u, v over α\alpha with |u|+|v|≤2|u| + |v| \le 2 in the third family, where uvuv is word concatenation. The presented Steinberg group Gn(α)G_n(\alpha) is the quotient of F(Gen⁡(n,α))F(\operatorname{Gen}(n, \alpha)) by the normal closure of the relators (2); for p∈Root⁡(n)p \in \operatorname{Root}(n) and a short word ww over α\alpha, the presented Steinberg generator gp(w)∈Gn(α)g_p(w) \in G_n(\alpha) is the image of g̃p(w)\tilde{g}_p(w).✦

For an integer nn, an alphabet α\alpha, and a group GG, a monomial completion seed ss is a map g:Root⁡(n)×α*→Gg : \operatorname{Root}(n) \times \alpha^* \to G satisfying three conditions for all words u,v,w∈α*u, v, w \in \alpha^* of length at most 22: g(p,w)2=1g(p, w)^2 = 1 for every p∈Root⁡(n)p \in \operatorname{Root}(n), [g(p,u),g(q,v)]=1[g(p, u), g(q, v)] = 1 whenever pcol≠qrowp_{\mathrm{col}} \ne q_{\mathrm{row}} and prow≠qcolp_{\mathrm{row}} \ne q_{\mathrm{col}}, and [g((i,j),u),g((j,k),v)]=g((i,k),uv)[g((i, j), u), g((j, k), v)] = g((i, k), uv) whenever i,j,ki, j, k are distinct and |u|+|v|≤2|u| + |v| \le 2.✦

Given n≥5n \ge 5, a monomial completion seed ss into GG, and a root p=(i,j)∈Root⁡(n)p = (i, j) \in \operatorname{Root}(n), the completed word map ξp:α*→G\xi_p : \alpha^* \to G agrees with g(p,w)g(p, w) when |w|≤2|w| \le 2, and on any word aw′a w' with a∈αa \in \alpha (viewed as a word of length 11) and |w′|≥2|w'| \ge 2 is given recursively by ξij(aw′)=[g((i,m),a),ξmj(w′)]\xi_{ij}(a w') = \bigl[g((i, m), a),\, \xi_{mj}(w')\bigr](3)✦ for a chosen index m∈{0,…,n−1}\{i,j}m \in \{0, \dots, n - 1\} \setminus \{i, j\}.

For each p∈Root⁡(n)p \in \operatorname{Root}(n), the elements ξp(w)\xi_p(w) (w∈α*w \in \alpha^*) given by g(p,w)g(p, w) and (3) generate a root subgroup Up≤GU_p \le G.✦ Viewing ξp(w)\xi_p(w) inside UpU_p and extending the map 𝔽2→Up\mathbb{F}_2 \to U_p (0↦10 \mapsto 1, 1↦ξp(w)1 \mapsto \xi_p(w)) over the coefficients of a polynomial f∈Pf \in P defines an element Φs(p,f)∈G\Phi_s(p, f) \in G✦, and applying the universal property of St⁡n(P)\operatorname{St}_n(P) to Φs\Phi_s produces the seed lift homomorphism Λs:St⁡n(P)→G\Lambda_s : \operatorname{St}_n(P) \to G sending xp(f)x_p(f) to Φs(p,f)\Phi_s(p, f).✦

The presentation-to-Steinberg homomorphism φ:Gn(α)→St⁡n(P)\varphi : G_n(\alpha) \to \operatorname{St}_n(P) is the group homomorphism sending each generator gp(w)g_p(w) (|w|≤2|w| \le 2) to the Steinberg generator xp([w])x_p([w]).✦ On Gn(α)G_n(\alpha), the canonical presentation seed s0s_0 is the monomial completion seed mapping (p,w)(p, w) to gp(w)g_p(w) when |w|≤2|w| \le 2 and to 11 when |w|>2|w| > 2; for n≥5n \ge 5, the Steinberg-to-presentation homomorphism ψ:St⁡n(P)→Gn(α)\psi : \operatorname{St}_n(P) \to G_n(\alpha) is the seed lift Λs0\Lambda_{s_0} of s0s_0.

Quotient Steinberg Groups and the Concrete Algebra

Let BB be a unital associative ring and S⊆BS \subseteq B a subset. The coefficient ideal IS=⟨S⟩⊆BI_S = \langle S \rangle \subseteq B is the two-sided ideal generated by SS, with quotient ring B/ISB / I_S. In St⁡n(B)\operatorname{St}_n(B), the Steinberg root relations for SS form the subset {xp(a):p∈Root⁡(n),a∈S}\{x_p(a) : p \in \operatorname{Root}(n),\, a \in S\}, whose normal closure in St⁡n(B)\operatorname{St}_n(B) is denoted NSN_S. The Steinberg quotient group St⁡n(B)/NS\operatorname{St}_n(B) / N_S of St⁡n(B)\operatorname{St}_n(B) by SS is the quotient group of St⁡n(B)\operatorname{St}_n(B) by NSN_S, equipped with the canonical quotient homomorphism κS:St⁡n(B)→St⁡n(B)/NS\kappa_S : \operatorname{St}_n(B) \to \operatorname{St}_n(B) / N_S.

The quotient-to-Steinberg homomorphism θS:St⁡n(B)/NS→St⁡n(B/IS)\theta_S : \operatorname{St}_n(B) / N_S \to \operatorname{St}_n(B / I_S) is the group homomorphism induced on quotients by applying St⁡n\operatorname{St}_n to the canonical ring projection B→B/ISB \to B / I_S.✦ For n≥5n \ge 5 and each root p∈Root⁡(n)p \in \operatorname{Root}(n), the quotient root map rp:B/IS→St⁡n(B)/NSr_p : B / I_S \to \operatorname{St}_n(B) / N_S is the map sending each coset a+ISa + I_S to κS(xp(a))\kappa_S(x_p(a)), and the Steinberg-to-quotient homomorphism ηS:St⁡n(B/IS)→St⁡n(B)/NS\eta_S : \operatorname{St}_n(B / I_S) \to \operatorname{St}_n(B) / N_S is the group homomorphism induced on St⁡n(B/IS)\operatorname{St}_n(B / I_S) by the quotient root maps rpr_p via the universal property.

A word rewriting table T=(Rrep,Z)T = (R_{\mathrm{rep}}, Z) over an alphabet α\alpha consists of a binary replacement relation RrepR_{\mathrm{rep}} on α*\alpha^* and a set Z⊆α*Z \subseteq \alpha^* of zero words.✦ Over a unital associative ring KK, the defining relations of TT in K⟨α⟩K\langle\alpha\rangle form the set consisting of the differences [v]−[w][v] - [w] for (v,w)∈Rrep(v, w) \in R_{\mathrm{rep}} and the basis monomials [z][z] for z∈Zz \in Z✦; these generate the defining two-sided ideal IT⊆K⟨α⟩I_T \subseteq K\langle\alpha\rangle✦, and the algebra of TT over KK is the quotient ring K⟨α⟩/ITK\langle\alpha\rangle / I_T.✦

For an integer dilation factor D≥2D \ge 2, a self-simulating machine hierarchy MM consists of a Boolean program and a threshold height h0≥4h_0 \ge 4 satisfying size bounds at capacity 2h2^h and a self-certification equivalence at every height h≥h0h \ge h_0 between Boolean satisfiability at height hh and the rewriting or zero condition at height DhDh.✦ At each h≥h0h \ge h_0, MM produces a word rewriting table over the finite alphabet of bitstrings of length 10000h10000h with data block size 10000Dh10000Dh, whose algebra over KK is denoted Ah(K)A_h(K). For the concrete dilation factor D=10(10000+1)(10+1)+1D = 10(10000 + 1)(10 + 1) + 1, the concrete source machine is a self-simulating machine hierarchy with threshold height h0≥4h_0 \ge 4, and its coordinate ring over 𝔽2\mathbb{F}_2 is R=Ah0(𝔽2)R = A_{h_0}(\mathbb{F}_2).✦

The Claim

Theorem 1. Let n≥5n \ge 5 be an integer, let α\alpha be an alphabet, and let P=𝔽2⟨α⟩P = \mathbb{F}_2\langle\alpha\rangle. Then φ:Gn(α)→∼St⁡n(P),φ−1=ψ,\varphi : G_n(\alpha) \xrightarrow{\;\sim\;} \operatorname{St}_n(P), \qquad \varphi^{-1} = \psi,(4)✦ is a group isomorphism. If α\alpha is finite, then St⁡n(P) is finitely presented.\operatorname{St}_n(P) \text{ is finitely presented.}(5)✦ Let BB be a unital associative ring and let S⊆BS \subseteq B be a subset, with two-sided ideal IS=⟨S⟩I_S = \langle S \rangle and relator normal closure NS⊴St⁡n(B)N_S \trianglelefteq \operatorname{St}_n(B). Then θS:St⁡n(B)/NS→∼St⁡n(B/IS),θS−1=ηS,\theta_S : \operatorname{St}_n(B) / N_S \xrightarrow{\;\sim\;} \operatorname{St}_n(B / I_S), \qquad \theta_S^{-1} = \eta_S,(6)✦ is a group isomorphism. If SS is finite and St⁡n(B)\operatorname{St}_n(B) is finitely presented, then St⁡n(B/IS) is finitely presented.\operatorname{St}_n(B / I_S) \text{ is finitely presented.}(7)✦ For n≥5n \ge 5, a finite alphabet α\alpha, and a finite subset S⊆PS \subseteq P generating the two-sided ideal I=⟨S⟩I = \langle S \rangle, St⁡n(P/I) is finitely presented.\operatorname{St}_n(P / I) \text{ is finitely presented.}(8)✦ For the concrete coordinate ring RR, St⁡12(R) is finitely presented.\operatorname{St}_{12}(R) \text{ is finitely presented.}(9)✦

In the paper, the result reads: for n≥5n \ge 5 and a finite presentation P/I=𝔽2⟨α⟩/(f1,…,fs)P / I = \mathbb{F}_2\langle\alpha\rangle / (f_1, \dots, f_s) as a unital associative 𝔽2\mathbb{F}_2-algebra (where the paper writes RR for P/IP / I and 𝒜\mathcal{A} for α\alpha), St⁡n(P/I)\operatorname{St}_n(P / I) has the ordinary finite presentation with generators gij(w)g_{ij}(w) (i≠ji \ne j, |w|≤2|w| \le 2), recursive words ξij(w)\xi_{ij}(w), and relators gij(w)2=1g_{ij}(w)^2 = 1, [gij(u),gkl(v)]=1[g_{ij}(u), g_{kl}(v)] = 1 (j≠kj \ne k, i≠li \ne l), [gij(u),gjk(v)]=gik(uv)[g_{ij}(u), g_{jk}(v)] = g_{ik}(uv) (|u|+|v|≤2|u| + |v| \le 2, i,j,ki, j, k distinct), and ∏w∈Sftξij(w)=1\prod_{w \in S_{f_t}} \xi_{ij}(w) = 1. In the library, the explicit presentation is stated over the free algebra PP in (4) and (5), while (6), (7), (8), and (9) treat quotients and the concrete ring RR.

What Is Checked

The quotient theorem (8) is stated over an integer n≥5n \ge 5, a finite alphabet α\alpha, the algebra P=𝔽2⟨α⟩P = \mathbb{F}_2\langle\alpha\rangle, a finite subset S⊆PS \subseteq P generating the two-sided ideal I=⟨S⟩I = \langle S \rangle, and the Steinberg group St⁡n(P/I)\operatorname{St}_n(P / I). Over an arbitrary alphabet α\alpha (finite in (5)), the free-algebra claims (4) and (5) concern n≥5n \ge 5, the presented Steinberg group Gn(α)G_n(\alpha), the homomorphisms φ\varphi and ψ\psi, and St⁡n(P)\operatorname{St}_n(P). For a unital associative ring BB, a subset S⊆BS \subseteq B (finite in (7), where St⁡n(B)\operatorname{St}_n(B) is also assumed finitely presented), and n≥5n \ge 5, the quotient claims (6) and (7) involve the ideal IS=⟨S⟩I_S = \langle S \rangle, the normal closure NS⊴St⁡n(B)N_S \trianglelefteq \operatorname{St}_n(B), the maps θS\theta_S and ηS\eta_S, and the groups St⁡n(B)/NS\operatorname{St}_n(B) / N_S and St⁡n(B/IS)\operatorname{St}_n(B / I_S). Claim (9) is stated over St⁡12(R)\operatorname{St}_{12}(R) for the concrete coordinate ring R=Ah0(𝔽2)R = A_{h_0}(\mathbb{F}_2) at the threshold height h0h_0 of the concrete self-simulating machine hierarchy with dilation factor D=10(10000+1)(10+1)+1D = 10(10000 + 1)(10 + 1) + 1.

For these constructions, the library proves that for any n≥5n \ge 5, alphabet α\alpha, group GG, and monomial completion seed ss, the polynomial map Φs\Phi_s satisfies Φs(p,f+g)=Φs(p,f)Φs(p,g)\Phi_s(p, f + g) = \Phi_s(p, f)\Phi_s(p, g) for all p∈Root⁡(n)p \in \operatorname{Root}(n) and f,g∈Pf, g \in P✦, that Φs(p,f)\Phi_s(p, f) and Φs(q,g)\Phi_s(q, g) commute whenever pcol≠qrowp_{\mathrm{col}} \ne q_{\mathrm{row}} and prow≠qcolp_{\mathrm{row}} \ne q_{\mathrm{col}}✦, and that [Φs((i,j),f),Φs((j,k),g)]=Φs((i,k),fg)[\Phi_s((i, j), f), \Phi_s((j, k), g)] = \Phi_s((i, k), fg) for pairwise distinct i,j,k∈{0,…,n−1}i, j, k \in \{0, \dots, n - 1\}.✦ For any ring BB and subset S⊆BS \subseteq B, the library proves that NSN_S lies in the kernel of the homomorphism St⁡n(B)→St⁡n(B/IS)\operatorname{St}_n(B) \to \operatorname{St}_n(B / I_S) induced by B→B/ISB \to B / I_S.✦ For the machine constructions, the library also proves that the concrete dilation factor satisfies D≥2D \ge 2✦ and that at any height h≥h0h \ge h_0 of a self-simulating machine hierarchy, both h>0h > 0 and the data block size 10000Dh>010000 D h > 0 hold.