4ea352d
THE BOONE-HIGMAN CONJECTURE
===========================
A finitely generated group has a solvable word problem if and only if
it embeds in a finitely presented simple group.
A readable presentation of "Finite algebraic envelopes and the
Boone-Higman conjecture" by OpenAI, October 2026.
Original source: boone_higman_finite_envelopes_original.txt
This version reorganises the proof, expands the places a reader is most
likely to get stuck, and states every result that is used. The mathematics
is the same as the original; nothing is assumed on faith except the named
standard theorems, which are stated in full where they are used.
=================================================
ABOUT THIS VERSION
=================================================
What the original paper is. A long technical document in group theory,
ring theory and computability. It proves the Boone-Higman conjecture:
decidable word problem is exactly the property that separates the finitely
generated groups that embed in finitely presented simple groups from the
rest.
What this version changes. Nothing about the mathematical content. Three
things about its presentation:
(1) Every theorem and lemma that the proof relies on is stated before
it is used, with its hypotheses visible, so the reader never has to
guess what is being assumed.
(2) Long constructions are introduced by a short paragraph saying what
the construction is for, before the technical definitions arrive.
(3) The proof is split into two layers. Part II is the "macro" proof:
it shows how a handful of algebraic and computability statements fit
together to give the theorem. Part III is the "micro" proof: it
proves the hardest of those statements, the monoid construction,
from a program index. A reader can understand Part II completely
while treating Part III as an appendix; a reader who wants the whole
proof reads both.
How to read it. Chapter order is proof order. Nothing in a chapter uses a
result from a later chapter without saying so.
Notation. Standard, and collected in Chapter 2 so a reader can flip back.
=================================================
ABSTRACT
=================================================
The word problem for a finitely generated group asks for an algorithm
that, given a word in the generators and their inverses, decides whether
the word equals the identity. A group is simple if it is nontrivial and
has no normal subgroups other than {1} and the whole group.
Boone and Higman proved in 1974 that a finitely generated group G has
solvable word problem if and only if G sits inside a chain G <= H <= K,
where H is simple and K is finitely presented. They asked whether the
simple group could itself be chosen finitely presented. This paper
answers yes:
THEOREM (Main). For a finitely generated group G, the following are
equivalent:
(i) G has a solvable word problem;
(ii) G embeds in a finitely presented simple group.
The hard direction is (i) => (ii). It passes through a geometric statement
about permutation actions:
THEOREM (Envelope). Every finitely generated group with solvable word
problem embeds in a finitely presented group Gamma that acts faithfully
and two-transitively on a countably infinite set, with finitely
generated point stabilizers.
Two-transitive actions are exactly the input expected by Zaremsky's
finite-presentation version of the twisted Brin-Thompson construction,
which turns Gamma into a finitely presented simple group. The envelope is
built from an affine action: translations plus matrix operations over a
carefully chosen algebra. The algebra itself is produced by a monoid
construction that codes a program into a finite presentation.
=================================================
TABLE OF CONTENTS
=================================================
Part I. Setting and statements
1. What this paper proves
2. Background and notation
3. The strategy in one page
4. The four engine theorems
Part II. The proof
5. Step 0: a group in which every element is a commutator
6. Step 1: the affine group, and its finite presentation
7. Step 2: killing the Steinberg kernel
8. Step 3: the mapping torus and the two-transitive action
9. Step 4: embedding the input group
10. Step 5: from two-transitive action to simple group
11. Step 6: the converse direction
Part III. The engine: building the algebras
12. The monoid theorem
13. The finite compiler and its bounded evaluator
14. The fixed point, the induction, and the two monoids
15. From monoids to the algebra package
16. References
=================================================
Part I. Setting and statements
=================================================
=================================================
1. What this paper proves
=================================================
Throughout, a group is written multiplicatively and its identity is 1.
A group is finitely generated if it has a finite set S of generators, so
every element is a finite word in S and the inverses of elements of S.
1.1 The word problem.
Fix a finite generating set S of a group G, and let S^{-1} be the set of
formal inverses. A word is a finite string in S union S^{-1}. Each word
names an element of G by multiplying it out. The word problem asks for an
algorithm that takes a word w and decides whether w names the identity.
One subtlety: the question must not depend on which generating set we
chose. It does not. If S and T are two finite generating sets, each is a
word in the other, so a procedure for one set converts mechanically into
a procedure for the other. We record this as a fact because it is used at
the very end:
FACT 1.1. Whether G has a solvable word problem is independent of the
choice of finite generating set.
So "decidable word problem" is a property of the group, not of a
presentation.
1.2 Simple groups.
A group is simple if it is nontrivial (has more than one element) and its
only normal subgroups are {1} and the whole group. Finite simple groups
are the familiar atoms of finite group theory. Infinite finitely presented
simple groups are the exotic, useful objects here: their internal
relations are so tangled that there is nothing to quotient by.
A group embeds in another if there is an injective homomorphism. "G embeds
in a finitely presented simple group" means: there is a simple group S
that has a finite presentation and contains a subgroup isomorphic to G.
1.3 The main theorem.
THEOREM 1.2 (Boone-Higman, proved here in full). For a finitely
generated group G the following are equivalent:
(i) G has a solvable word problem;
(ii) G embeds in a finitely presented simple group.
The implication (ii) => (i) is classical and short; Chapter 11 proves it.
The content of the paper is (i) => (ii).
1.4 The intermediate theorem.
THEOREM 1.3 (Envelope). Let G be a finitely generated group with
solvable word problem. Then G embeds in a finitely presented group Gamma
that acts on a countably infinite set X such that:
(a) the action is faithful (only the identity element fixes every
point of X);
(b) the action is two-transitive (it sends any ordered pair of
distinct points to any other ordered pair of distinct points);
(c) every point stabilizer is finitely generated.
Theorem 1.3 is the middle of the proof. Once we have it, Chapter 10 shows
that Theorem 1.3 plus the following result of Zaremsky finishes the
argument.
THEOREM 1.4 (Zaremsky). Suppose a finitely presented group Gamma acts
faithfully on a nonempty countable set X, every point stabilizer is
finitely generated, and Gamma has finitely many orbits on the unordered
two-element subsets of X. Then Gamma embeds in a nontrivial finitely
presented simple group.
A two-transitive action on a set with at least two points has exactly one
orbit on ordered pairs of distinct points, hence exactly one orbit on
unordered pairs. So Theorem 1.3 feeds directly into Theorem 1.4.
RESULT FOR THIS CHAPTER. It is enough to prove Theorem 1.3. That is what
Part II does.
=================================================
2. Background and notation
=================================================
This chapter collects the pieces of mathematics the proof uses, so the
later chapters can name them instead of rebuilding them.
2.1 Groups, subgroups, actions.
A group G acts on a set X if each g in G gives a permutation x -> g.x of
X with (gh).x = g.(h.x) and 1.x = x. The action is faithful if g.x = x
for every x forces g = 1. It is transitive if any two points are sent to
each other by some element. It is two-transitive if any ordered pair of
distinct points is sent to any other ordered pair of distinct points.
Our actions come from affine transformations of a module: translations
(x -> x + v) and linear maps (x -> Mx). Translations are always transitive
on the module, and they let us move one point of an ordered pair to the
origin. So for affine actions, two-transitivity reduces to: the linear
part acts transitively on the nonzero vectors. That is the whole reason
the construction uses simple algebras, whose inner structure is rich
enough to connect every nonzero vector to every other.
2.2 Rings, algebras, and the Steinberg group.
An algebra over a field k is a vector space over k that is also a ring,
with the two structures compatible. All algebras here have an identity,
written 1, except where we say "nonunital".
An algebra is simple if it is nonzero and has no two-sided ideal other
than {0} and the whole algebra.
A corner of an algebra B is the set qBq = {qbq : b in B} for an
idempotent q (an element with q^2 = q). The corner is itself an algebra
with identity q, and q need not equal the identity of B. This "identity
different from the ambient identity" idea is central: the map that sends
B into a corner is injective, but it does not preserve the identity, and
that failure is exactly what makes the later stage-shift detectable.
The Steinberg group. Let R be a unital ring and let n >= 3. The Steinberg
group St_n(R) has, for each ordered pair of distinct indices i, j in
{1,...,n} and each element r of R, a symbol x_{ij}(r), subject to:
additivity x_{ij}(r) x_{ij}(s) = x_{ij}(r+s);
chain [x_{ij}(r), x_{jk}(s)] = x_{ik}(rs) (i,j,k distinct);
commutativity [x_{ij}(r), x_{kl}(s)] = 1 (i != l, j != k).
Here [a,b] = a b a^{-1} b^{-1}. The map x_{ij}(r) -> I + r e_{ij} (where
e_{ij} is the matrix unit and I is the identity matrix) is a surjection
St_n(R) ->> E_n(R), the group of elementary matrices. Its kernel is the
"Steinberg kernel"; measuring and controlling that kernel is a recurring
theme.
2.3 Finitely presented rings and the Krstic-McCool theorem.
A unital ring R is finitely presented if it is the quotient of a free
associative unital ring on finitely many generators by an ideal generated
by finitely many elements. We use the following established theorem; we
do not reprove it.
THEOREM 2.1 (Krstic-McCool 1999). If R is a finitely presented unital
associative ring (not necessarily commutative) and n >= 4, then St_n(R)
is finitely presented.
2.4 The tensor ring R = B (x) B^{op}.
Let B be an algebra over k and let B^{op} be the same vector space with
multiplication reversed. The tensor product R = B (x)_k B^{op} acts on B
by
(a (x) b^{op}) . m = a m b for m in B,
extended linearly. The "op" makes the second factor act on the right, and
this convention arranges that composing two such operations is the same as
multiplying the corresponding tensors. Thus B becomes a left R-module. If
B is a finitely presented unital k-algebra, then R is a finitely presented
unital ring over k (take two copies of a presentation of B, impose the
commutation of the two copies, and 2.1 = 0). This is the ring whose
Steinberg group acts on B^n.
2.5 Two-complexity facts we use later.
(Nonunital coefficient maps.) If lambda : R -> R is additive and
multiplicative but does not preserve 1, and G is a matrix over R with
entrywise image lambda^{(n)}(G), then the elementary computation
G H - I = (G - I) + (H - I) + (G - I)(H - I)
shows that the formula I + lambda^{(n)}(G - I) is multiplicative in G and
sends the identity to the identity. This is how a nonunital map still
induces a homomorphism of matrix groups. (Used in Chapters 6 and 7.)
(Enumeration of consequences.) The set of consequences of a finite group
presentation is recursively enumerable: enumerate finite products of
conjugates of relators and their inverses. (Used in Chapter 11.)
(Rest of notation.) F_2 is the field with two elements. Q is the rationals.
Dyadic rationals are numbers m / 2^t with m, t integers. Shortlex order on
words is: shorter first, and among equal length, dictionary order.
=================================================
3. The strategy in one page
=================================================
Here is the shape of the proof, before any details.
(1) Enlarge the input. Given G finitely generated with solvable word
problem, form an HNN extension G-hat that contains two copies of G and a
stable letter s, arranged so that each element of G is a commutator in
G-hat (Chapter 5). Commutators are needed because elementary matrix
manipulations naturally produce commutators.
(2) Build an algebra with a self-embedding. Construct over F_2 a finitely
presented algebra B, a simple subalgebra A of B with its own identity, and
an injective nonunital map phi : B -> B whose image lies in A. Also
arrange 2x2 "matrix units" in the corner pBp, where p = phi(1). This is
the "algebra package", Theorem 4.1, proved in Part III from a monoid
construction.
(3) Build the affine group. Form Gamma_0 = B^6 semidirect St_6(R) with
R = B (x) B^{op}. This is a finitely presented group (Chapter 6) of
translations of B^6 and matrix operations.
(4) Kill the Steinberg kernel. The map phi induces an endomorphism Theta
of Gamma_0. Its linear part goes through the Steinberg group, whose kernel
would spoil faithfulness. Show that Theta kills that whole kernel in one
step, using the 2x2 matrix units and a four-corner argument (Chapter 7).
(5) Take a mapping torus. From Gamma_0 and Theta form the mapping torus
Gamma. It is finitely presented (Chapter 8), and its direct-limit
description is exactly translations plus elementary matrices plus a stage
shift. This description has no Steinberg kernel left.
(6) Read off the action. Let M_inf = direct limit of B under phi, and let
X = M_inf^6. The group Gamma acts affinely and faithfully on X. Simplicity
of A makes the linear part transitive on nonzero vectors, so the action is
two-transitive (Chapter 8). Point stabilizers are finitely generated.
(7) Put G inside. Use the commutator property from step 1 and balanced
elementary diagonal matrices to embed G into the linear part of Gamma
(Chapter 9). This proves Theorem 1.3.
(8) Finish with Zaremsky. Theorem 1.3 plus Zaremsky's Theorem 1.4 gives a
finitely presented simple group containing G (Chapter 10).
(9) The converse. Its short proof is in Chapter 11.
The engine, step 2, is the one genuinely hard piece, and Part III is
devoted to it.
=================================================
4. The four engine theorems
=================================================
The proof rests on four statements. The first two are the algebra package
and the monoid theorem. The third and fourth are the geometric inputs from
the literature (Zaremsky's theorem, already stated, and the Krstic-McCool
theorem, stated in Chapter 2). Here we state the algebra package and the
monoid theorem in full, because everything in Parts II and III refers to
them.
4.1 The algebra package.
THEOREM 4.1 (Algebra package). Let L be a finitely generated group with
solvable word problem. Over k = F_2 there exist:
(i) a nonzero finitely presented unital algebra B;
(ii) a simple subalgebra A of B, with identity e, into whose unit
group A^x there is an embedding L -> A^x;
(iii) an injective nonunital algebra homomorphism phi : B -> B with
phi(B) contained in A and with p := phi(1_B) != 1_B;
(iv) elements s_0, s_1, t_0, t_1 in the corner pBp that commute with
phi(B) and satisfy
t_i s_j = delta_{ij} p (i, j in {0,1}),
s_0 t_0 + s_1 t_1 = p;
(v) an element b_* of B with the following detection property. Put
R = B (x) B^{op} and psi = phi (x) phi^{op}. Then for every
nonzero r in R,
psi(r) . b_* != 0.
Three remarks make this digestible.
* The corner pBp is where the "matrix units" (iv) live. The identities
in (iv) are exactly the rectangular-inverse form of a 2x2 matrix unit
system: s_j and t_j act like one-directional moves, t_i s_j is zero
off the diagonal, and the two diagonal moves sum to the corner
identity p. They are what lets two orthogonal copies of the corner be
interchanged and split, which is the crux of Chapter 7.
* Properties (iii) and (v) are what make the affine action faithful.
The properness p != 1_B makes the stage shift detectable (different
points end up in different stages). The detector b_* makes the linear
part faithful (no nonzero coefficient matrix acts as zero on b_*).
* Why we can have all this at once is the content of Part III. The idea
is that a finite presentation can be compiled directly from a program
index, before we know the program halts, and a bounded evaluator then
keeps every dependency strictly shorter than the word being reduced.
4.2 The monoid theorem.
The algebras in Theorem 4.1 are built as "contracted monoid algebras" of
two monoids that encode each other. The monoid theorem says those monoids
exist.
Write 1_H for the identity of a monoid H, and 0 for the zero of a monoid
with zero (an absorbing element, 0.h = h.0 = 0 for all h).
THEOREM 4.2 (Monoid theorem). Let G-hat be a finitely generated group
with solvable word problem. There exist:
* a finitely presented monoid K with a zero Omega != 1_K;
* a finitely generated monoid H with solvable word problem and a zero
zeta != 1_H;
with the following five properties.
(i) There is an injective group homomorphism G-hat -> H^x.
(ii) Form the monoid T = ((K minus {Omega}) x P) union {0_T}, where P
is the partial-affine monoid defined in Chapter 15, multiplication
is coordinatewise except that a product whose K-coordinate is
Omega becomes 0_T, and 0_T is absorbing. Then there is an
injective unital monoid map kappa : T -> H with kappa(0_T) = zeta.
(iii) Selector property. For every finite ordered tuple
h_1, ..., h_d of distinct nonzero elements of H (d >= 1) there
are L, R in H with L h_1 R = 1_H and L h_i R = zeta for i >= 2.
(iv) There is an injective multiplicative map c : H -> K, not required
to preserve identities or zeros, whose image misses both 1_K and
Omega. We write c_h = c(h).
(v) Separator property. There is an element z of H such that
(tau, tau') -> kappa(tau) z kappa(tau') is an injection from
(T minus {0_T})^2 into H minus {zeta}.
Why each clause is there:
(iii) is the simplicity machine. In a contracted monoid algebra, a
nonzero element is a finite linear combination of distinct basis
elements. The selectors isolate the first basis element and kill the
rest, so any nonzero two-sided ideal contains the identity. That makes
the algebra simple.
(ii) and (iv) give embeddings of algebras in opposite directions that
differ in how they treat the zero class. One of them is used to build a
simple algebra inside a finitely presented one, the other to build the
self-embedding. Their mismatch at zero is repaired by subtracting a
fixed nonzero basis element; this is spelled out in Chapter 15.
(v) is the detector. It distinguishes ordered pairs of basis elements,
which is what makes the tensor detector of Theorem 4.1(v) injective.
Theorem 4.2 is proved in Part III. Everything else in Part II uses it as
given.
RESULT FOR PART I. We have stated the main theorem (1.2) and reduced it to
the envelope theorem (1.3), which in turn uses the algebra package (4.1)
and Zaremsky (1.4). Part II proves the envelope theorem from the algebra
package; Part III proves the algebra package from the monoid theorem; and
the monoid theorem is proved in the same Part III.
=================================================
Part II. The proof
=================================================
=================================================
5. Step 0: a group in which every element is a commutator
=================================================
WHY THIS STEP. Elementary matrix groups are generated by commutators: the
Steinberg relation says x_{ij}(a) is the commutator of x_{ik}(a) and
x_{kj}(1). If we want to realise an arbitrary group G inside such a matrix
group, it helps a lot if every element of G is already a commutator in
some larger group. Then a product of elementary commutators can spell it
out. This short chapter builds that larger group.
LEMMA 5.1 (Commutator enlargement). Let G be finitely generated with
solvable word problem. Then there is a finitely generated group G-hat
with solvable word problem, containing a copy of G x G, and an element
s of G-hat such that for every g in G,
[ (g,g), s ] = (g,1).
Moreover the two copies of a finite generating set of G, together with
s, generate G-hat.
PROOF. Consider the HNN extension
G-hat = < G x G, s | s (g,g) s^{-1} = (1,g) for all g in G >.
The two associated subgroups are the diagonal
Delta = { (g,g) : g in G }
and the second factor
1 x G = { (1,g) : g in G }.
They are isomorphic, and the isomorphism sends (g,g) to (1,g). So the HNN
extension is well defined. By Britton's Lemma, the base G x G embeds in
G-hat. (Britton's Lemma: in an HNN extension, the base group embeds, and a
word in normal form with a stable letter is nontrivial.)
NEXT: THE WORD PROBLEM IS STILL SOLVABLE. We must show that G-hat, which
is only finitely generated, has a solvable word problem. Give an algorithm
that, given any word in the generators, decides whether it is the identity.
First write the word in normal form with respect to the stable letter: a
word is a product base . s^{e} . base . s^{e} ... . base, with e = +-1.
Store each base factor as a pair (a,b) of words on the chosen generators of
G.
Now look for a "pinch": a substring of the form s (a,a) s^{-1} or
s^{-1} (1,b) s. In the first case (a,a) belongs to the associated subgroup
and we may replace the substring by (1,a); in the second, (1,b) belongs and
we replace by (b,b). These replacements come straight from the defining
relation of the HNN extension. Each replacement removes two stable letters.
Since a word has finitely many stable letters, this process terminates.
When no pinch remains, either the word still contains a stable letter, in
which case Britton's Lemma says it is NOT the identity (a nontrivial word
in normal form is nontrivial), or it contains no stable letter, in which
case it is a base word (a, b) and we decide whether a = 1 and b = 1 using
the word-problem decider for G (which we are given; the decider applies to
each coordinate, and we can also test ab^{-1} = 1 the same way, which is
exactly the membership test for the diagonal that the pinch search needs).
This decides the word problem, and every step is effective. No finite
presentation of G is used, only the decidable word problem of G.
FINALLY, THE GENERATION AND THE COMMUTATOR IDENTITY. The two copies of a
finite generating set of G generate G x G, and adding s generates G-hat.
Compute directly:
[ (g,g), s ] = (g,g) . s . (g,g)^{-1} . s^{-1}
= (g,g) . s . (g^{-1},g^{-1}) . s^{-1}
= (g,g) . [ s (g^{-1},g^{-1}) s^{-1} ]
= (g,g) . (1, g^{-1})
= (g, 1).
In the third line we used the defining relation in the form
s (h,h) s^{-1} = (1,h) with h = g^{-1}. Done. The case where G is finite,
or even trivial, is covered: if G is trivial then G-hat is the infinite
cyclic group generated by s, and the identity is vacuous.
REMARK. The point of this construction is only to make elements of G
commutators. It costs us nothing: G-hat is still finitely generated and
still has a solvable word problem, and it contains G (twice).
=================================================
6. Step 1: the affine group, and its finite presentation
=================================================
THE PLAN. From the algebra package (Theorem 4.1) we build a finitely
presented group Gamma_0 made of two kinds of moves on the 6-fold product
B^6:
* translations v -> v + m, where m is in B^6;
* matrix moves v -> g v, where g is an elementary 6x6 matrix over
the ring R = B (x) B^{op}.
The matrix moves act on vectors by the ring action of R on B; that is how
left-and-right multiplication by elements of B enters. The whole chapter is
the proof that this group of moves has a finite presentation, given that B
has one.
The reason for the 6-fold product, and not say 2- or 3-fold, is that the
matrix arguments need at least six coordinates in order to have enough
"free" indices to conjugate with (the four-corner argument of Chapter 7
needs three pairwise disjoint pairs of indices). The Krstic-McCool theorem
needs n >= 4; six is a comfortable choice.
6.1 The coefficient ring and the cyclic module.
Let B be the finitely presented F_2-algebra from Theorem 4.1 and define
R = B (x)_{F_2} B^{op},
(a (x) b^{op}) . m = a m b (m in B),
extended linearly. As in Section 2.4 this makes B a left R-module, and R is
a finitely presented unital F_2-ring because B is. The module we actually
want is B^6, which is the direct sum of six copies of B. We must show B^6
is a finitely presented R-module, i.e. that B itself is a quotient of R by
a finitely generated left ideal. That is the next lemma.
LEMMA 6.1 (Cyclic module). Let Y be a finite algebra generating set for
B. For b in B put
d_b = b (x) 1 - 1 (x) b^{op} in R,
and let J = sum over y in Y of R d_y be the left ideal generated by the
d_y. Then evaluation at 1_B induces an isomorphism of left R-modules
R / J ~= B.
PROOF. Evaluation is the map eps : R -> B, eps(a (x) b^{op}) = a b. It is
a surjective R-module map (surjective because R contains 1 (x) 1 whose
image is 1), and every d_y annihilates 1_B, so J lies in the kernel of eps.
We compute the whole kernel.
The key identity is, for b, c in B,
d_{bc} = (b (x) 1) d_c + (1 (x) c^{op}) d_b. (6.1)
Check it: the right side is
(b (x) 1)(c(x)1 - 1(x)c^{op}) + (1(x)c^{op})(b(x)1 - 1(x)b^{op})
= bc(x)1 - b(x)c^{op} + b(x)c^{op} - 1(x)(bc)^{op}
= bc(x)1 - 1(x)(bc)^{op}
= d_{bc}.
By (6.1), additivity, and d_1 = 0, the set { b : d_b in J } is a subring
of B containing Y. Since Y generates B as an algebra over F_2 and d_1 = 0,
that set is all of B. Hence d_b is in J for EVERY b in B.
Consequently, modulo J, we may slide the right factor to the left:
a (x) b^{op} = a (x) b^{op} - (a (x) 1) d_b mod J
= a (x) b^{op} - (ab (x) 1 - a (x) b^{op})
= ab (x) 1 mod J.
So every element of R is congruent modulo J to something of the form c (x) 1.
The additive map b -> (b (x) 1) + J from B to R/J is then a two-sided
inverse to eps: eps(b(x)1 + J) = b, and the computation above shows every
class has a representative b(x)1. Hence ker(eps) = J and eps induces an
isomorphism R/J ~= B. Done.
As a consequence, the R-module B^6 = (R/J)^6 is finitely presented (a
direct sum of six copies of R/J, and J is finitely generated by the
finitely many d_y).
6.2 The Steinberg group, and its finite presentation.
Recall the Steinberg group from Section 2.2: St_n(R) is generated by
x_{ij}(r) (i != j in {1,...,n}, r in R) subject to additivity, the chain
relation, and the commutativity relation. It maps onto the elementary
matrix group E_n(R) by x_{ij}(r) -> I + r e_{ij}; call this map pi_n, and
its kernel the Steinberg kernel.
By the Krstic-McCool theorem (Theorem 2.1), and because R is a finitely
presented unital ring and n = 6 >= 4, the group St_6(R) is finitely
presented. This is one of our two external inputs; we do not reprove it.
6.3 The relative presentation.
The group we want, B^6 semidirect St_6(R), has translations by the module
B^6 = (R/J)^6. We give it a finite presentation, starting from a finite
presentation of St_6(R) and adding finitely many generators and relations
for the translations. The point of the following lemma is that the
semidirect product decomposition, which looks like it needs the whole group
action, is actually pinned down by finitely many relations.
LEMMA 6.2 (Relative presentation). Let R be a finitely generated unital
associative ring, let J = sum over d in D of R d for a finite subset D of
R, and let n >= 4. If St_n(R) is finitely presented, then the semidirect
product
(R/J)^n semidirect St_n(R)
(where St_n(R) acts on the column (R/J)^n through pi_n) is finitely
presented. Concretely: choose a finite ring generating set F of R
containing 1. A finite presentation is obtained from a finite
presentation of St_n(R) by adjoining generators p_1, ..., p_n and the
relations
[p_a, p_b] = 1 (6.2)
[x_{ab}(s), p_c] = 1 for s in F, c != b (6.3)
[x_{ab}(1), p_b] = p_a (6.4)
[x_{ab}(d), p_b] = 1 for d in D (6.5)
where every root shown has a != b. Each root in these relations is
represented by a word in the chosen generators of St_n(R).
INTERPRETATION BEFORE THE PROOF. The element p_a is meant to be
"translate by 1 + J in row a". The relation (6.4) says that conjugating p_b
by the elementary root x_{ab}(1) moves the translation from row b to row a,
which is what the elementary matrix I + e_{ab} does to a column. Relation
(6.3) says x_{ab}(s) does not disturb p_c as long as its column c is not b.
Relation (6.5) kills the translations coming from J, so the module becomes
R/J. Relation (6.2) makes the translations commute. The proof shows these
finitely many relations force the full intended semidirect product.
PROOF. Let Q be the group presented by (6.2)-(6.5). We work inside Q until
the very end, then produce inverse homomorphisms to the intended semidirect
product.
STEP 1: THE COMMUTATION (6.3) HOLDS FOR ALL s IN R, NOT JUST s IN F.
Let C be the set of s in R for which [x_{ab}(s), p_c] = 1 holds for all
permitted triples (a,b,c). By additivity of x_{ab} (the Steinberg relation),
C is an additive subgroup, and F is contained in C. Suppose r, s are in C.
Choose an index h different from a, b, c; this is possible because
n >= 4. Then the chain relation gives
x_{ab}(rs) = [ x_{ah}(r), x_{hb}(s) ].
Now x_{ah}(r) commutes with p_c (since c is not any of the columns a, h,
so r in C applies with (a,h,c)), and x_{hb}(s) commutes with p_c (with
(h,b,c), and h != c, so s in C applies). A commutator of two elements that
each commute with p_c also commutes with p_c. So rs is in C. Thus C is a
subring of R containing F, hence C = R.
STEP 2: THE TRANSLATION ELEMENT IS INDEPENDENT OF THE CHOICE OF COLUMN.
For a != b define
w_a^b(r) = [ x_{ab}(r), p_b ].
This is a conjugate of p_b, so it is a "translation" candidate in row a.
We claim w_a^b(r) does not depend on b (for b != a). First note that if h
differs from a and b, then w_a^b(r) commutes with p_h: both x_{ab}(r) and
p_b commute with p_h, by Step 1 and (6.2).
Now pick h different from a, b and set
X = x_{ah}(r), Y = x_{hb}(1), Z = x_{ab}(r).
The chain relation gives [X, Y] = Z, i.e. X Y = Z Y X. Conjugate p_b by the
two equal products X Y and Z Y X:
(X Y) p_b (X Y)^{-1} = w_a^h(r) p_h p_b,
(Z Y X) p_b (Z Y X)^{-1} = p_h w_a^b(r) p_b.
We verify the two displayed lines. First, Y p_b Y^{-1} = [x_{hb}(1), p_b] p_b
= p_h p_b, and X commutes with p_b (Step 1, since the column h of X is not b),
while X p_h X^{-1} = [x_{ah}(r), p_h] p_h = w_a^h(r) p_h. Composing:
(X Y) p_b (X Y)^{-1} = X (p_h p_b) X^{-1}
= (X p_h X^{-1})(X p_b X^{-1}) = w_a^h(r) p_h p_b
= p_h w_a^h(r) p_b,
because w_a^h(r) commutes with p_h. Second, Z commutes with p_h (its column
b is not h) and Z p_b Z^{-1} = [x_{ab}(r), p_b] p_b = w_a^b(r) p_b, so
(Z Y X) p_b (Z Y X)^{-1} = Z (p_h p_b) Z^{-1} = p_h w_a^b(r) p_b.
Since X Y = Z Y X the two left sides are equal, so
p_h w_a^h(r) p_b = p_h w_a^b(r) p_b.
Cancel p_h on the left and p_b on the right (both invertible):
w_a^h(r) = w_a^b(r). Thus the element is independent of the permitted column
b; write it w_a(r).
STEP 3: COMMUTATIONS. w_a(r) commutes with every p_c: choose the defining
column b not in {a, c} (possible since n >= 3), so both defining factors
commute with p_c. Also w_a(r) commutes with x_{cd}(s) whenever d != a:
choose defining column b not in {a, c, d} (possible since n >= 4); then
x_{ab}(r) commutes with x_{cd}(s) by Steinberg commutativity (a != d, b != c),
and p_b commutes with x_{cd}(s) because b != d (relation (6.3)).
Consequently all the w's commute. Given w_a(r) and w_c(s), choose
b not in {a, c} and write w_c(s) = [x_{cb}(s), p_b]. The element w_a(r)
commutes with both factors (x_{cb}(s) by the previous sentence since
b != a; p_b by the first sentence), hence with their commutator. This
covers a = c too.
STEP 4: ADDITIVITY. Using the commutator identity
[uv, p] = u [v, p] u^{-1} [u, p], and any b != a,
w_a(r+s) = [x_{ab}(r) x_{ab}(s), p_b]
= x_{ab}(r) w_a(s) x_{ab}(r)^{-1} . w_a(r)
= w_a(r) w_a(s),
where the last step uses that w_a(s) commutes with x_{ab}(r): by Step 3,
w_a(s) commutes with x_{cd}(t) whenever d != a, and here the column of x_{ab}
is b != a. Thus w_a : (R, +) -> Q is a
homomorphism of additive groups. And w_a(1) = p_a by (6.4). In particular
any additive relation among elements of R holds among the w_a: for example
in characteristic two, p_a^2 = w_a(1 + 1) = w_a(0) = 1.
STEP 5: CONJUGATION. We must see how a root whose column is a acts on
w_a(r). For c != a, choose b not in {a, c} and set
X = x_{ca}(s), Y = x_{ab}(r), Z = x_{cb}(sr).
Then X fixes p_b (column b != a, Step 1), and X Y X^{-1} = Z Y (chain
relation, reordered). Conjugating w_a(r) = [Y, p_b] by X, and using
X p_b X^{-1} = p_b,
X w_a(r) X^{-1} = [X Y X^{-1}, X p_b X^{-1}] = [Z Y, p_b]
= Z w_a(r) Z^{-1} . w_c(sr)
= w_a(r) w_c(sr).
The last equality: Z = x_{cb}(sr) has column b != a, so Z commutes with
w_a(r) (Step 3). And [Z, p_b] = w_c(sr) by definition (column b, row c).
Thus
X w_a(r) X^{-1} = w_a(r) w_c(sr). (6.6)
Together with the commutations of Step 3, (6.6) says exactly that the
x_{ca}(s) act on the additive group generated by the w_a(r) as elementary
matrices act on a column over the left module R. This is the elementary
action we wanted.
STEP 6: THE MODULE RELATIONS. Relation (6.5) says w_a(d) = 1 for every a
and every d in D. To kill a left multiple in a prescribed row c, choose
a != c and conjugate w_a(d) = 1 by x_{ca}(s); by (6.6),
x_{ca}(s) w_a(d) x_{ca}(s)^{-1} = w_a(d) w_c(sd) = w_c(sd),
so w_c(sd) = 1. Since the w_c are additive (Step 4), every w_c vanishes on
the left ideal J generated by D.
STEP 7: INVERSE HOMOMORPHISMS. Let P_0 = (R/J)^n semidirect St_n(R) be the
intended group. Sending p_a to "translate by 1 + J in row a" and using the
identity on St_n(R) respects all of (6.2)-(6.5) (compare with the intended
semidirect product), so it gives a homomorphism f : Q -> P_0.
Conversely, the additive maps r + J -> w_a(r) define a homomorphism
(R/J)^n -> Q (well defined by Step 6). Equation (6.6) and the root
commutations give the required equivariance, so this map and the canonical
map St_n(R) -> Q together induce a homomorphism g : P_0 -> Q.
Now check the two composites. The composite g f fixes St_n(R) and each
p_a = w_a(1), so g f is the identity on Q. The composite f g fixes
St_n(R) and every translation (in P_0, the commutator of x_{ab}(r) with
translation by 1 + J in row b is translation by r + J in row a, which is
exactly what (6.6) says on the Q side), so f g is the identity on P_0. Thus
f and g are inverse isomorphisms and Q ~= P_0. In particular Q is the
semidirect product, and the finite presentation (6.2)-(6.5) presents it.
6.4 The affine group is finitely presented.
PROPOSITION 6.3. For B as in the algebra package and R = B (x) B^{op}, the
group
Gamma_0 = B^6 semidirect St_6(R)
is finitely presented.
PROOF. The ring R is finitely presented, so by Krstic-McCool St_6(R) is
finitely presented. By Lemma 6.1, B is the quotient R/J of R by the
finitely generated left ideal J; hence B^6 = (R/J)^6. Lemma 6.2 with n = 6
now presents the semidirect product B^6 semidirect St_6(R) finitely, from a
finite presentation of St_6(R) plus finitely many generators and relations.
Done.
6.5 The transition endomorphism.
We now build the endomorphism of Gamma_0 that becomes the stage shift.
Recall phi : B -> B is the injective nonunital algebra map from the algebra
package, with image in the simple subalgebra A. Define
psi = phi (x) phi^{op} : R -> R, psi(a (x) b^{op}) = phi(a) (x) phi(b)^{op}.
This is additive and multiplicative and injective (tensoring injective maps
over the field F_2 preserves injectivity). It need not preserve 1; indeed
psi(1_R) = phi(1_B) (x) phi(1_B)^{op} = p (x) p^{op} = P, and P != 1_R.
LEMMA 6.4 (Transition endomorphism). The formulas
theta( x_{ab}(r) ) = x_{ab}( psi(r) ),
Theta( m , h ) = ( phi^{(6)}(m) , theta(h) )
(where phi^{(6)} acts componentwise on B^6) define endomorphisms of
St_6(R) and of Gamma_0 respectively. The induced map on elementary
matrices is the injective homomorphism
F : E_6(R) -> E_6(R), F(g) = I + psi^{(6)}(g - I),
where psi^{(6)} acts entrywise on 6x6 matrices. Thus pi theta = F pi.
PROOF. Additivity and multiplicativity of psi preserve every Steinberg
relation (additivity, chain, commutativity), so theta is a homomorphism.
For the semidirect product, we need phi to be compatible with the R-action:
for r = a (x) b^{op} and m in B,
phi(r . m) = phi(a m b) = phi(a) phi(m) phi(b) = psi(r) . phi(m),
using that phi is multiplicative (though not unital). By additivity this
holds for every r in R. So for each elementary root,
phi^{(6)}( (I + r e_{ab}) m ) = (I + psi(r) e_{ab}) phi^{(6)}(m).
Since the roots generate St_6(R), this equivariance proves Theta is an
endomorphism of the semidirect product.
For the matrix assertion, write g = I + A and h = I + C. Entrywise
application psi^{(6)} is additive and multiplicative on matrices (it is a
ring homomorphism "entry by entry", ignoring the identity). Since
gh - I = A + C + A C,
F(gh) = I + psi^{(6)}(A) + psi^{(6)}(C) + psi^{(6)}(A) psi^{(6)}(C)
= F(g) F(h),
and F(I) = I. The same computation gives F(g^{-1}) = F(g)^{-1}. On
elementary matrices, F(I + r e_{ab}) = I + psi(r) e_{ab}, which shows both
that F maps E_6(R) into E_6(R) and that pi theta = F pi.
Finally F is injective: if F(g) = I then every entry of g - I is killed by
psi, and psi is injective, so g = I. Done.
WHAT WE HAVE. A finitely presented group Gamma_0 = B^6 semidirect St_6(R)
and an endomorphism Theta whose matrix part F is injective. The map Theta
itself need not be injective, because theta can have a kernel: it acts on
St_6(R), and two different Steinberg elements with the same elementary
matrix may be sent to different, or even to trivial, things. The remaining
obstruction is exactly the Steinberg kernel (the kernel of pi). Chapter 7
proves theta annihilates that whole kernel.
=================================================
7. Step 2: killing the Steinberg kernel
=================================================
WHAT IS AT STAKE. The linear part of our group acts through the Steinberg
group St_6(R), which maps onto the elementary matrices E_6(R). That map
pi has a kernel. Elements of the kernel act as the identity matrix, so if
any of them survived into the action on B^6, the action would fail to be
faithful (they would fix every point yet not be the identity of the group).
The transition map Theta = (phi^{(6)}, theta) sends the Steinberg part by
r -> psi(r). This chapter proves that theta KILLS the whole kernel: every
element of ker(pi) is sent to 1. Then, after the mapping torus, no
spurious matrix kernel remains.
The argument is a classical-style computation in the Steinberg group. It
does not need to know anything about the kernel element except that its
matrix is the identity. It uses the 2x2 matrix units from the algebra
package, expanded to four corners, and a clever "shuffle" that makes a
central element equal to its own square.
NOTATION. Throughout, R is a unital associative ring, psi : R -> R is an
additive multiplicative map (NOT necessarily unital), and P = psi(1) is
the support idempotent. The Steinberg relations are those of Section 2.2:
x_{ij}(a) x_{ij}(b) = x_{ij}(a+b) (7.1)
[x_{ij}(a), x_{jk}(b)] = x_{ik}(ab) (i,j,k distinct) (7.2)
[x_{ij}(a), x_{kl}(b)] = 1 (i != l, j != k) (7.3)
and pi : St_6(R) -> E_6(R) sends x_{ij}(a) to I + a e_{ij}.
7.1 Statement.
THEOREM 7.1 (Kernel annihilation). Suppose U_0, U_1, V_0, V_1 in the
corner PRP commute with psi(R) and satisfy
V_i U_j = delta_{ij} P (i, j in {0,1}),
U_0 V_0 + U_1 V_1 = P.
Then the homomorphism
theta : St_6(R) -> St_6(R), x_{ij}(a) -> x_{ij}(psi(a)),
satisfies theta(ker pi) = 1.
REMARK ON THE HYPOTHESES. The U's and V's are exactly the image under
psi of the 2x2 matrix units s_l, t_l of the algebra package (Theorem
4.1(iv)), tensored with P. In the application we take R = B (x) B^{op}
and psi = phi (x) phi^{op}, and the U, V are U_i = s_i (x) p^{op},
V_i = t_i (x) p^{op}; they satisfy the displayed relations by (4.1)(iv).
So the theorem is tailor-made for our situation. Stating it for a general
ring keeps the hypotheses visible.
7.2 First tool: nonunital coefficient maps preserve identity matrices.
For any additive multiplicative map lambda : R -> R and any matrix g over
R, define lambda^{(6)}(g) entrywise and set F_lambda(g) = I + lambda^{(6)}(g-I).
The computation of Section 2.5 shows F_lambda is multiplicative and sends I
to I. In particular, if w is a word in the Steinberg generators whose
matrix pi(w) is the identity, then the same word with every coefficient a
replaced by lambda(a) also has identity matrix. We will use this for maps
of the form a -> psi(a) Q, where Q is an idempotent commuting with psi(R):
such a map is multiplicative (Q^2 = Q) and has image in QRQ, so applying it
to a matrix-identity word gives another matrix-identity word, now with
coefficients in QRQ.
7.3 Second tool: centralising by an unused index.
LEMMA 7.2 (External roots). Let J be a subset of {1,...,6} and let k not
be in J. For a column c = (c_i) indexed by J and a row r = (r_i) indexed
by J, put
C_k(c) = product over i in J of x_{ik}(c_i),
R_k(r) = product over i in J of x_{ki}(r_i).
If w is a root word using only indices in J, and A is its matrix on the
indices J, then
w C_k(c) w^{-1} = C_k(A c),
w R_k(r) w^{-1} = R_k(r A^{-1}). (7.4)
In particular, an element represented by a root word that omits index 6
and has identity matrix is central in St_6(R).
PROOF. The factors in each defining product commute (relation (7.3), since
the column index k is outside J, and distinct row indices in J give
distinct x_{ik}). It is enough to check conjugation by a single generator
x_{ij}(a), with i, j in J. The column index k is fixed and outside J, so
every column factor x_{ik}(c_i) has its second index equal to this external
k. Conjugation by x_{ij}(a) acts on the column vector c by the elementary
term
x_{ij}(a) x_{jk}(c_j) x_{ij}(a)^{-1}
= x_{ik}(a c_j) x_{jk}(c_j) (by (7.2)),
and row factors:
x_{ij}(a) x_{ki}(r_i) x_{ij}(a)^{-1}
= x_{kj}(- r_i a) x_{ki}(r_i) (reverse of (7.2)).
These are exactly multiplication of the column c by I + a e_{ij} (which
adds a c_j to the i-th entry and keeps the rest) and multiplication of the
row r by I - a e_{ij} (which adds -r_i a to the j-th entry). Composing over
the word w gives (7.4) inside the Steinberg group.
Now suppose w omits 6 and has identity matrix A = I on its indices. Then
(7.4) with k = 6 and A = I shows w commutes with every C_6(c) and R_6(r),
i.e. with every x_{i6}(a) and x_{6i}(a). It also commutes with the
remaining roots, because for i, j != 6 we can write
x_{ij}(a) = [x_{i6}(a), x_{6j}(1)] (by (7.2)),
a commutator of two things w commutes with. As these roots generate
St_6(R), w is central. Done.
7.4 Third tool: a word in a corner with identity matrix is central.
LEMMA 7.3 (Corner centrality). Let E, F be idempotents in R with
EF = FE = 0. Suppose d, d* in R satisfy
d = F d E, d* = E d* F, d* d = E, d d* = F. (7.5)
Then every root word whose coefficients lie in ERE and whose matrix is
the identity represents a central element of St_6(R).
PROOF. (d* is just a name for the second element; no involution on R is
meant.) Consider the "compression" element built from indices 1 and 6:
W = x_{16}(d) x_{61}(-d*) x_{16}(d).
By multiplying out the three elementary 2x2 blocks (using (7.5)), its
matrix and its inverse on the ordered pair (1,6) are
H = [ 1-F d ; -d* 1-E ],
H^{-1} = [ 1-F -d ; d* 1-E ]. (7.6)
Let y = E y E be a coefficient in the corner ERE, and let k not be in
{1,6}. Apply Lemma 7.2 to the actual word W (whose relevant matrix is H).
The four conjugates are
W x_{1k}(y) W^{-1} = x_{1k}(y),
W x_{6k}(y) W^{-1} = x_{1k}(d y),
W x_{k1}(y) W^{-1} = x_{k1}(y),
W x_{k6}(y) W^{-1} = x_{k1}(y d*). (7.7)
Indeed d* y = 0 and y d = 0 because E and F are orthogonal, and the
(1-E) and (1-F) parts act trivially on y. Roots whose indices both avoid
{1,6} commute with W.
To handle the two roots internal to the pair (1,6), use factorisations:
x_{16}(y) = [x_{1k}(y), x_{k6}(E)],
x_{61}(y) = [x_{6k}(y), x_{k1}(E)] (by (7.2)).
Under W, the first commutator becomes, via (7.7),
[ x_{1k}(y), x_{k1}(d*) ], and the second becomes
[ x_{1k}(d y), x_{k1}(E) ]. Both are words OMITTING index 6. So W
conjugates each root with coefficient in ERE to a word whose matrix is
still the identity and which omits index 6. By the last part of Lemma 7.2,
that conjugated element is central; hence the original was central too. Done.
7.5 Fourth tool: comparing two corners.
First recall the balanced elementary step. For a unit a of R define
w_{ij}(a) = x_{ij}(a) x_{ji}(-a^{-1}) x_{ij}(a),
h_{ij}(a) = w_{ij}(a) w_{ij}(-1).
Direct matrix multiplication gives
pi(w_{ij}(a)) on {i,j} = [ 0 a ;
-a^{-1} 0 ],
pi(h_{ij}(a)) on {i,j} = [ a 0 ;
0 a^{-1} ], (7.8)
both the identity on the other indices. So h_{ij}(a) acts as a balanced
"diagonal" with a in one slot and a^{-1} in another.
LEMMA 7.4 (Corner comparison). Let E, F, d, d* satisfy (7.5) with E, F
orthogonal idempotents, and suppose all four commute with psi(R). For
z in ker(pi), let z_E, z_F be its images under the coefficient maps
a -> psi(a) E and a -> psi(a) F (which are multiplicative because E and F
are idempotents commuting with psi(R)). Then z_E = z_F, and both are
central.
PROOF. By Section 7.2, the root word defining z, with coefficients
restricted into ERE or into FRF, has identity matrix; by Lemma 7.3 it is
central. So z_E and z_F are central. The centrality is all we need; it does
not matter in which order the corner maps were applied.
Now build b = d + d* + 1 - E - F. A direct check using (7.5) gives
d^2 = 0, (d*)^2 = 0, d d* = F, d* d = E,
and 1 - E - F is an idempotent annihilating d and d* on both sides. So
b^2 = 1 and b E b^{-1} = F; b is an involution interchanging E and F. And
b commutes with psi(R) because everything it is built from does.
Form the element (indices in three disjoint pairs)
D = h_{12}(b) h_{34}(b) h_{56}(b) in St_6(R).
By (7.8), pi(D) is diagonal with b in all six positions. In fact we claim
the exact Steinberg identity, for every y in R,
D x_{ij}(y) D^{-1} = x_{ij}(b y b^{-1}). (7.9)
If i and j lie in different pairs among (1,2), (3,4), (5,6): apply
Lemma 7.2 to the two relevant factors of D. The factor for the pair
containing i multiplies the coefficient on the left by b, the factor for
the pair containing j multiplies on the right by b^{-1}, and the third
factor commutes with the root. (Because b = b^{-1}, it does not matter
which slot of a pair we use.) If i, j are in the same pair, choose k in
another pair and write x_{ij}(y) = [x_{ik}(y), x_{kj}(1)]; the cross-pair
case already conjugates the two factors to x_{ik}(b y b^{-1}) and
x_{kj}(1), so the commutator transforms correctly. This proves (7.9).
Since b commutes with psi(R) and interchanges E, F, equation (7.9) implies
D z_E D^{-1} = z_F. But z_E and z_F are central, so z_E = z_F. Done.
LEMMA 7.5 (Orthogonal corner images commute). If E, F in R are
orthogonal idempotents, the subgroup of St_6(R) generated by roots with
coefficients in ERE commutes with the subgroup generated by roots with
coefficients in FRF.
PROOF. For a in ERE and c in FRF, ac = ca = 0. Two roots with these
coefficients commute by (7.2)/(7.3) unless they are opposite (same pair of
indices): a chain commutator would have coefficient ac = 0 or ca = 0, and
roots in the same position commute by additivity (7.1). For the remaining
opposite pair x_{ij}(a), x_{ji}(c), choose k distinct from i, j and write
x_{ij}(a) = [x_{ik}(a), x_{kj}(E)]. The root x_{ji}(c) commutes with
x_{ik}(a) because its coefficient product is ca = 0, and with x_{kj}(E)
because E c = 0. A commutator therefore commutes with it. Done.
7.6 Proof of Theorem 7.1.
Define four idempotents:
E_i = U_i V_i (i in {0,1}),
E_{0i} = U_0 U_i V_i V_0 (i in {0,1}).
All of them commute with psi(R) (products of things that do). The pair
relations give two orthogonal decompositions:
P = E_0 + E_1,
E_0 = E_{00} + E_{01}. (7.10)
Each of E_0, E_{00}, E_{01} is orthogonal to E_1 and equivalent to it in
the sense of (7.5). Let us verify this. Put
U_{00} = U_0 U_0, V_{00} = V_0 V_0,
U_{01} = U_0 U_1, V_{01} = V_1 V_0,
and for v in {0, 00, 01} set
d_v = U_1 V_v, d_v* = U_v V_1.
Then V_v U_v = P and U_v V_v = E_v (this is what pinning down the
products shows; the only nontrivial one is E_{0i} = U_0 U_i V_i V_0 =
U_0 E_i V_0 and a short check with the pair relations), and one obtains
d_v = E_1 d_v E_v, d_v* = E_v d_v* E_1,
d_v* d_v = E_v, d_v d_v* = E_1,
which is exactly (7.5) with (E, F) = (E_v, E_1). All four commute with
psi(R).
Fix z in ker(pi) and let z_Q denote its image under a -> psi(a) Q for one
of these idempotents. Applying Lemma 7.4 three times, always with second
corner E_1, gives
z_{E_0} = z_{E_1} = z_{E_{00}} = z_{E_{01}}. (7.11)
By additivity, the decomposition E_0 = E_{00} + E_{01} splits every root
image into the sum of its two child images. By Lemma 7.5 those child
factors commute, so we may collect them separately in any word, giving
z_{E_0} = z_{E_{00}} z_{E_{01}}.
But (7.11) says z_{E_{00}} = z_{E_{01}} = z_{E_0}, and these commute (they
are images into orthogonal corners, by Lemma 7.5), so
z_{E_0} = z_{E_0}^2.
Hence z_{E_0} = 1, and then z_{E_1} = 1. Finally psi(a) P = psi(a) (since
P = psi(1) and psi is multiplicative: psi(a) psi(1) = psi(a)), so the
first decomposition of (7.10) with the same commutation gives
theta(z) = z_P = z_{E_0} z_{E_1} = 1.
This holds for every z in ker(pi). Done.
CONSEQUENCE FOR THE CONSTRUCTION. In our setting R = B (x) B^{op} and
psi = phi (x) phi^{op}, and the U_i, V_i are U_i = s_i (x) p^{op},
V_i = t_i (x) p^{op}, which lie in PRP, commute with psi(R), and satisfy
the pair relations (4.1)(iv) tensored with p^{op}. So Theorem 7.1 applies:
the transition theta annihilates the Steinberg kernel in one step. This is
the property that makes the next chapter work.
=================================================
8. Step 3: the mapping torus and the two-transitive action
=================================================
WHAT THIS CHAPTER DOES. We convert the finitely presented group Gamma_0
and its endomorphism Theta into a finitely presented group Gamma whose
direct-limit description is clean: translations of M_inf^6, plus elementary
matrices, plus a stage shift t. Because Theta kills the Steinberg kernel
(Chapter 7), the Steinberg kernel does not survive into this description.
Then we exhibit the faithful two-transitive action of Gamma on
X = M_inf^6. This is the bulk of Theorem 1.3.
8.1 The mapping torus.
The mapping torus is a standard construction; we recall it and prove the
two facts we need (that it is finitely presented, and that it has a clean
direct-limit description even when the endomorphism is not injective).
LEMMA 8.1 (Mapping torus). Let Q be a group and f : Q -> Q an
endomorphism. Write L = direct limit of Q under f, with classes [q,j] for
j >= 0 and the relation [q,j] = [f(q),j+1]. Define
alpha([q,j]) = [q, j+1] on L.
Then alpha is an automorphism of L, and
< Q, t | t^{-1} q t = f(q) for all q in Q > ~= L semidirect_alpha Z.
If Q is finitely presented, so is this group.
PROOF. In the direct limit, two classes are equal if and only if they
become equal after finitely many forward steps. So alpha is well defined,
as is beta([q,j]) = [f(q),j] (one step back, permissible because
[q,j] = [f(q),j+1]). The defining equivalence gives alpha beta = beta
alpha = identity on L. So alpha is an automorphism.
Let t act on L by alpha. Then t^{-1} [q,0] t = beta([q,0]) = [f(q),0],
so the map sending q to [q,0] and t to t is compatible with the
presenting relations t^{-1} q t = f(q); hence it defines a homomorphism
from the presented group to L semidirect Z.
In the other direction, send [q,j] to t^j q t^{-j}. The relation
t^{-1} q t = f(q) gives t^{j+1} f(q) t^{-(j+1)} = t^j q t^{-j}, so this
map is well defined on the direct limit. It intertwines alpha with
conjugation by t, so it extends to a homomorphism L semidirect Z -> the
presented group. The two maps are inverse on the generators Q and t,
hence inverse isomorphisms.
For the finite-presentation claim: given Q = < X | Rel >, choose a word in
X representing f(x) for each x in X (finite, since X is finite). Adjoin t
and the finitely many relations t^{-1} x t = f(x) for x in X. These imply
t^{-1} q t = f(q) for every q in Q, because both conjugation and f are
homomorphisms. So the enlarged finite presentation presents the mapping
torus. Done.
APPLICATION. Apply Lemma 8.1 with (Q, f) = (Gamma_0, Theta). Because
Gamma_0 is finitely presented (Proposition 6.3), the resulting group Gamma
is finitely presented. Now describe its direct limit explicitly. Define
M_inf = direct limit of (B, +) under phi,
E_inf = direct limit of (E_6(R), F),
where F(g) = I + psi^{(6)}(g - I) is the injective map of Lemma 6.4, and
recall the matrix map pi : St_6(R) -> E_6(R).
LEMMA 8.2 (Affine limit). There are compatible isomorphisms
direct limit of (Gamma_0, Theta) ~= M_inf^6 semidirect E_inf,
Gamma ~= (M_inf^6 semidirect E_inf) semidirect Z.
In the second isomorphism, conjugation by the stable letter t shifts the
stage index forward by one on both M_inf and E_inf.
PROOF. The commuting square pi theta = F pi induces a surjection from the
Steinberg direct limit to E_inf. Suppose a class of the Steinberg direct
limit, represented by h in St_6(R), maps to the identity of E_inf. Then
some iterate F^k sends pi(h) to I. But F is injective (Lemma 6.4), so
pi(h) = I already. Theorem 7.1 (kernel annihilation) then gives
theta(h) = 1, so the class is trivial. Hence the induced map from the
Steinberg direct limit to E_inf is injective as well as surjective, an
isomorphism.
The module action is compatible after passage to any common stage:
for g in E_6(R) and v in B^6,
phi^{(6)}( g v ) = F(g) phi^{(6)}(v). (8.1)
Indeed it is enough to check on an elementary root g = I + r e_{ab}, where
phi^{(6)}((I + r e_{ab}) v) = (I + psi(r) e_{ab}) phi^{(6)}(v) =
F(I + r e_{ab}) phi^{(6)}(v), and additivity extends it. Thus matrices and
vectors act on one another consistently at every stage.
Now the stage maps
(v, h) -> ( [v,j] , [pi(h),j] )
induce a homomorphism from the direct limit of (Gamma_0, Theta) to
M_inf^6 semidirect E_inf. It is surjective: given a vector and a matrix in
the target, choose a common representing stage and a Steinberg preimage of
the matrix. It is injective: if a representative (v,h) maps to the
identity, injectivity of phi gives v = 0, and injectivity of F on E_inf
gives pi(h) = I; Theorem 7.1 then gives theta(h) = 1, so (0, 1) is the
identity in the direct limit. So it is an isomorphism. The construction
respects the stage shift, so Lemma 8.1 gives the second isomorphism
Gamma ~= (M_inf^6 semidirect E_inf) semidirect Z as well. Done.
REMARK. Lemma 8.2 is where "the Steinberg kernel has disappeared": the
object on the right is built from M_inf^6 and E_inf and a shift, with no
Steinberg group in sight. The kernel was absorbed when we proved the
Steinberg direct limit is E_inf.
8.2 The action and its properties.
Set X = M_inf^6. The group M_inf^6 acts on X by translations. The group
E_inf acts by matrices after passing to a common stage, as in (8.1). The
stable letter t acts by the forward stage shift. These formulas are
compatible (the shift intertwines the matrix actions, as (8.1) says), so
they define an action of Gamma on X.
PROPOSITION 8.3 (Two-transitive action). The set X is countably infinite.
The action of Gamma on X is faithful and two-transitive, and every point
stabilizer is finitely generated.
PROOF. We prove the five claims in order.
(1) STAGE FILTRATION. Because phi is injective, identify the j-th additive
stage of M_inf with its image M_j inside M_inf, and put X_j = M_j^6. The
stages are nested: [b,j] = [phi(b), j+1]. They are STRICTLY nested:
every phi(b) satisfies p phi(b) = phi(b) with p = phi(1_B) != 1_B, so
1_B is not in phi(B). Hence [1_B, j+1] is not in M_j, and
X_0 proper subset X_1 proper subset X_2 proper subset ... (8.2)
The algebra B is countable (it is a quotient of a free algebra on finitely
many generators over the finite field F_2). So X = union of X_j is
countable, and the strict inclusions make it infinite.
(2) THE LINEAR ACTION IS FAITHFUL. Take a nonidentity element of E_inf,
represented by a matrix g != I at some stage j. Choose a nonzero entry r
of g - I, in row a and column b. At stage j+1, let v have b_* in coordinate
b and 0 in the other coordinates (b_* is the detector from 4.1(v)). The
a-th coordinate of F(g) v - v is psi(r) . b_*, which is nonzero by
4.1(v). It remains nonzero in the direct limit because phi is injective.
So g sends v to a different point; the linear action is faithful.
(3) THE AFFINE ACTION IS FAITHFUL. If an affine element acts as the
identity, evaluating it at the origin 0 first shows its translation part is
0; then the linear faithfulness of (2) shows its matrix part is the
identity. So the affine action on X is faithful.
(4) THE WHOLE ACTION IS FAITHFUL. Every affine limit element and its
inverse have representatives at some common stage. At every later stage
their translation vectors, matrices, and inverse matrices act inside that
stage. Hence for each affine limit element a,
a(X_j) = X_j for all sufficiently large j. (8.3)
In contrast, t^k(X_j) = X_{j+k} for all j, j+k >= 0. For k != 0 this
differs from X_j by (8.2). So no nonzero power of t agrees, as a
permutation, with an affine limit element. If a t^k acts trivially, then
t^k acts as a^{-1}, which forces k = 0 by (8.3). Then a = 1 by (3). So
the action of the whole group Gamma is faithful.
(5) TWO-TRANSITIVITY. Since translations act transitively, it suffices to
show that the linear part E_inf is transitive on the NONZERO vectors of X.
Given two nonzero vectors in X, choose a common representing stage and
advance one step further. After that step all their coordinates lie in A
(since phi(B) is contained in A) and the vectors are still nonzero. We now
work in this one stage, with the simple algebra A and its identity e.
Take a vector with a nonzero coordinate m_j in A. Simplicity of A means the
two-sided ideal A m_j A equals A: the finite sums of elements a m_j b form
a nonzero two-sided ideal, and A is simple. Hence for any d in A there are
finitely many a_ν, b_ν in A with d = sum_ν a_ν m_j b_ν. The coefficient
r = sum_ν a_ν (x) b_ν^{op} in R satisfies r . m_j = d. For an index l != j,
the elementary matrix in row l, column j, with coefficient r, adds d to
coordinate l and changes no other coordinate. So we can set coordinate l
to any prescribed value in A.
Now move both vectors to the common target (0,0,0,0,0,e):
* if the nonzero coordinate is j != 6, set the last coordinate (index 6)
to e;
* if j = 6, first set coordinate 1 to e (possible since 1 != 6), then
use coordinate 1 to set the last coordinate to something, namely use the
now-nonzero coordinate 1 to set coordinate 6 to e;
* use the last coordinate e to kill every other coordinate (set them to 0).
Applying this procedure to each of the two original vectors sends both to
(0,0,0,0,0,e) at the same stage. Hence the linear action is transitive on
nonzero vectors, and translations then take any ordered pair of distinct
points to any other. The action is two-transitive.
(6) POINT STABILIZERS ARE FINITELY GENERATED. Both E_inf and t fix the
origin 0, so from the semidirect-product description,
Stab_Gamma(0) = E_inf semidirect <t> ~= Gamma / X.
This is a quotient of the finitely presented group Gamma by the translation
subgroup, hence finitely generated (indeed, t together with the images of a
finite generating set of the Steinberg group generate it: conjugating by
positive powers of t reaches every linear stage). All other point
stabilizers are conjugate to this one, because translations act
transitively. Done.
RESULT. We have a finitely presented group Gamma (Lemma 8.1) with a
faithful two-transitive action on a countably infinite set X = M_inf^6,
with finitely generated point stabilizers (Proposition 8.3). What is still
missing for Theorem 1.3 is that G itself sits inside Gamma. Chapter 9 puts
it there.
=================================================
9. Step 4: embedding the input group
=================================================
WHAT THIS CHAPTER DOES. Chapter 8 built a finitely presented group Gamma
with the good action, but Gamma only contains the ALGEBRAIC package. We
must verify that the ORIGINAL group G sits inside Gamma. The abstract
algebra package (Theorem 4.1) was applied to the group L = G-hat of
Lemma 5.1; it gives an embedding of G-hat into the unit group of A. Now we
compose this with the construction of Gamma, using the commutator identity
of Lemma 5.1 and balanced elementary diagonals to get G inside the linear
part E_inf. This proves Theorem 1.3.
9.1 From units of A to units of R.
Let G-hat be the group of Lemma 5.1: it contains G x G and an element s
with [(g,g), s] = (g,1) for every g in G. Apply the algebra package
(Theorem 4.1) with L = G-hat. It gives:
iota : G-hat -> A^x (injective group homomorphism),
e : the identity of A (a subalgebra of B),
phi : B -> B (injective nonunital, image in A).
From iota we build a unit of B:
nu(h) = 1_B - e + iota(h) for h in G-hat.
LEMMA 9.1. nu is an injective homomorphism G-hat -> B^x, with identity
behaviour nu(1) = 1_B and inverse nu(h)^{-1} = nu(h^{-1}).
PROOF. The element 1_B - e annihilates A on both sides: (1_B - e) a = 0 and
a (1_B - e) = 0 for every a in A, because e is the identity of A and acts as
e on elements of A. In particular it annihilates iota(h). So
nu(h) nu(h') = (1_B - e + iota(h))(1_B - e + iota(h'))
= (1_B - e)^2 + (1_B - e) iota(h')
+ iota(h)(1_B - e) + iota(h) iota(h')
= (1_B - e) + 0 + 0 + iota(hh')
= nu(hh').
The identity: nu(1) = 1_B - e + e = 1_B. Conversely nu(h) nu(h^{-1}) =
nu(1) = 1_B, so nu(h)^{-1} = nu(h^{-1}). Finally nu is injective because
iota is (iota(h) is recovered from nu(h) as nu(h) - 1_B + e). Done.
Compose nu with the injective unital ring map B -> R, b -> b (x) 1_B. The
composite
nu-bar : G-hat -> R^x, nu-bar(h) = nu(h) (x) 1_B,
is again an injective group homomorphism (the tensor map is injective
because B is a nonzero vector space over F_2). Now we are inside the
coefficient ring R of the Steinberg group.
9.2 Balanced diagonals and the commutator trick.
For a unit u of R, define the "balanced diagonal" D_ij(u) to be the 6x6
diagonal matrix with entries u and u^{-1} in positions i and j, and 1
elsewhere. We already saw in (7.8) that such a diagonal lies in E_6(R): it
is the image under pi of the balanced elementary combination
h_{ij}(u) = w_{ij}(u) w_{ij}(-1). So D_ij(u) is an honest elementary
matrix and belongs to E_6(R) < E_inf.
Let s be the stable letter of G-hat, and put
a_g = nu-bar((g,g)) in R^x,
b_s = nu-bar(s) in R^x.
By the commutator identity of Lemma 5.1,
[ (g,g), s ] = (g,1),
so applying the injective homomorphism nu-bar,
[ a_g, b_s ] = nu-bar((g,1)).
Now take the commutator of balanced diagonals on two pairs that overlap in
exactly ONE coordinate, say the pair (1,2) and the pair (1,3):
[ D_12(a_g), D_13(b_s) ] = diag( [a_g, b_s], 1, 1, 1, 1, 1 )
= diag( nu-bar((g,1)), 1, 1, 1, 1, 1 ).
The point is that a diagonal with a in slot 1 and the other diagonals with
b in slot 1 multiply slot 1 in the order a b a^{-1} b^{-1} = [a_g, b_s],
while their other slots are simply 1 (the second diagonal is 1 in slot 2,
the first is 1 in slot 3). So the commutator is a diagonal with [a_g, b_s]
in the (1,1) entry and 1 elsewhere.
9.3 The embedding of G.
The assignment
g -> diag( nu-bar((g,1)), 1, 1, 1, 1, 1 ) (9.1)
is a group homomorphism G -> E_6(R): it is the composition of the
injective homomorphism nu-bar, the diagonal embedding, and the commutator
construction above (which realises each such diagonal as a commutator of
balanced diagonals, hence inside E_6(R)). It is injective because nu-bar is
injective. So G embeds in E_6(R).
Finally, E_6(R) sits in E_inf: the natural map E_6(R) -> E_inf, g -> [g,0],
is injective because F is injective (if F^k(g) = I then g = I). Hence G
embeds in E_inf, which by Lemma 8.2 is a subgroup of Gamma. This completes
the missing piece of Theorem 1.3.
PROOF OF THEOREM 1.3 (Envelope). Let G be finitely generated with
solvable word problem. By the above:
* Gamma is finitely presented (Proposition 6.3 and Lemma 8.1);
* Gamma acts faithfully and two-transitively on the countably infinite
set X = M_inf^6 (Proposition 8.3);
* every point stabilizer is finitely generated (Proposition 8.3);
* G embeds in Gamma (Section 9.3).
This is exactly the statement of Theorem 1.3. Done.
=================================================
10. Step 5: from two-transitive action to simple group
=================================================
We now finish the (i) => (ii) direction of the main theorem, using
Zaremsky's theorem (Theorem 1.4).
PROOF OF THEOREM 1.2, DIRECTION (i) => (ii). Let G be finitely generated
with solvable word problem. By Theorem 1.3, G embeds in a finitely
presented group Gamma acting faithfully and two-transitively on a
countably infinite set X, with finitely generated point stabilizers.
A two-transitive action on a set with at least two points has exactly one
orbit on ordered pairs of distinct points. Forgetting the order, it has
exactly one orbit on unordered pairs of distinct points. So the
hypotheses of Theorem 1.4 (Zaremsky) are met: Gamma is finitely
presented, acts faithfully on the nonempty countable set X, has finitely
generated point stabilizers, and has finitely many (in fact one) orbits
on unordered pairs.
Theorem 1.4 then embeds Gamma in a nontrivial finitely presented simple
group S. The group S is nontrivial because Gamma acts transitively on an
infinite set (so Gamma itself is infinite, and a simple group containing
it is not the trivial group). Composing embeddings, G embeds in S.
Done.
=================================================
11. Step 6: the converse direction
=================================================
It remains to see that (ii) implies (i): anything that embeds in a finitely
presented simple group has a solvable word problem. The argument is
classical and is due (as credited by Boone and Higman) to Kuznetsov. We
give it in full.
PROOF OF THEOREM 1.2, DIRECTION (ii) => (i). Let S be a finitely
presented simple group, S = < Y | Rel >, with Y finite. Let G be a
finitely generated subgroup of S. We show G has a solvable word problem.
Set up two searches that run in parallel. On an input word w (a word in the
chosen generators of S), the two searches are:
(I) enumerate all presentation proofs that w = 1 follows from Rel
(i.e. that w is the identity in S);
(II) enumerate, for every generator y in Y, a presentation proof that
y = 1 follows from Rel together with the extra relation w = 1;
the search succeeds when such a proof has been found for EVERY
generator y.
Both searches are effective. Consequences of a finite group presentation
are recursively enumerable: enumerate finite products of conjugates of
relators and their inverses, and check whether the result is the word you
want to be trivial. So (I) and (II) can each be carried out mechanically.
Now the key dichotomy.
Case w = 1 in S. Then search (I) eventually succeeds. Search (II) CANNOT
succeed: if w = 1 then Rel plus w = 1 is the same as Rel, so a proof that
every generator y equals 1 would say the generators of S are all trivial,
i.e. S is the trivial group; but S is a simple FINITELY PRESENTED group,
nontrivial by hypothesis (simple means nontrivial). So (II) never
terminates in this case.
Case w != 1 in S. Let N be the normal closure of w in S, the smallest
normal subgroup containing w. Since S is simple and w is a nontrivial
element, N is a normal subgroup not equal to {1}, hence N = S. So all
generators y lie in N, meaning each y can be expressed as a product of
conjugates of w and w^{-1}, i.e. each y = 1 follows from Rel together with
w = 1. Hence search (II) eventually succeeds. Search (I) never succeeds,
because w != 1.
Exactly one of the two searches terminates in each case, and we can run
them in parallel deciding which. This decides whether w = 1 in S.
Finally we transfer the decider from S to G. G is finitely generated; fix
words in Y representing its generators. Substitute these words into every
input word over G's generators (a word in G's generators is a word in Y
after substitution). This reduces the word problem in G to the word
problem we just decided in S.
We also note (this was Fact 1.1) that the word problem is independent of
the finite generating set: two finite generating sets convert into each
other, so a decider for one transfers to the other. This completes
(ii) => (i), and with it Theorem 1.2. Done.
=================================================
Part III. The engine: building the algebras
=================================================
=================================================
12. The monoid theorem
=================================================
WHAT THIS PART DOES. Parts I and II reduced the Boone-Higman conjecture to
the algebra package (Theorem 4.1). This Part proves the algebra package
from the monoid theorem (Theorem 4.2), and then proves the monoid theorem.
The monoid theorem is the computational heart: it builds two monoids that
code each other, one finitely presented (K) and one finitely generated with
a solvable word problem (H). From these we manufacture the simple algebra
inside a finitely presented algebra, the self-embedding, and the detector.
We restate the monoid theorem for convenience, with a word on the shape of
the proof so this chapter is not a surprise.
THEOREM 4.2 (Monoid theorem, restated). Let G-hat be a finitely generated
group with solvable word problem. There exist a finitely presented monoid
K with zero Omega != 1_K, and a finitely generated monoid H with solvable
word problem and zero zeta != 1_H, with:
(i) an injective group homomorphism G-hat -> H^x;
(ii) injective unital monoid map kappa : T -> H with kappa(0_T) = zeta,
where T = ((K minus {Omega}) x P) union {0_T} and P is the
partial-affine monoid (defined in Chapter 15, and see below);
(iii) the selector property: for every finite ordered tuple
h_1,...,h_d of distinct nonzero elements of H, some L, R in H
give L h_1 R = 1_H and L h_i R = zeta for i >= 2;
(iv) an injective multiplicative map c : H -> K missing 1_K and Omega;
(v) a separator z in H making (tau, tau') -> kappa(tau) z kappa(tau')
injective on (T minus {0_T})^2.
12.1 What the auxiliary monoid P is, and why.
The monoid P is the monoid of certain PARTIAL affine maps of the rational
line. Concretely, P is generated by the full affine maps
u(x) = x/2, v(x) = (x+1)/2,
their inverses, and the partial identities e_0, e_1 on the rational tails
[0, infinity) and [1, infinity) respectively (intersected with Q). The
elements of P are computable objects and P has a solvable word problem, so
it can be used as a supply of "extra coordinates" without wrecking
decidability. Its role is to provide the 2x2 matrix-unit-like corner used
in Chapter 15 (the idempotent q = e_0 - e_1). We prove its basic properties
where it is used, in Chapter 15, so that the two halves of the argument can
be checked together.
12.2 The shape of the proof, in words.
The proof of Theorem 4.2 has three conceptual ingredients.
(A) A FINITE COMPILER. From a program index eta (a program expecting
words over an alphabet Sigma and returning words over Sigma), we can
compile, WITHOUT EVER RUNNING THE PROGRAM, a finite monoid presentation
K_eta and a partial evaluator N_eta. The presentation K_eta has a zero
letter Omega, a finite presentation alphabet X_eta, an additive grade
gamma (grade of a generator is 0, 1, or 2; grade extends additively to
words), and a distinguished word raw(u) = alpha Q u_R omega for each
input u. The evaluator N_eta has the following remarkable property: on any
word a, its calls to the program f_eta are only on words of length at most
gamma(a). So the evaluator is "self-limiting": the deeper it actually
runs the program, the shorter the inputs to that run are. This is
Chapter 13.
(B) A FIXED POINT AND A LENGTH INDUCTION. We choose the program eta
cleverly, as a fixed point of a computable transformation tau (Kleene's
recursion theorem). The program eta computes a function f = f_eta that,
on a word w of length n, builds a finite rule table R_n of equations that
(a) encode the finitely many "static" reduction rules from the ALREADY
decided small words, and (b) add "selector" rules that isolate basis
elements. Because each static test uses a call to f only on words of
length at most gamma roughly n/D_0 < n (for a fixed code length D_0), a
strong induction on length proves that f is total, length-nonincreasing,
and compatible with context. This is Chapter 14.
(C) THE TWO MONOIDS. From f we build H (whose equations are the union of
all the rule tables R_n; its word problem is decided by the induced normal
form) and, via the compiler of (A), a finitely presented monoid K. The
maps kappa, c, and z of Theorem 4.2 all come from the coding of words by
raw words. This is Chapter 14 as well, and Chapter 15 turns the monoids
into the algebra package.
We now prove (A).
=================================================
13. The finite compiler and its bounded evaluator
=================================================
We fix throughout a finite alphabet Sigma and a partial function
f_eta : Sigma^* -> Sigma^* computed by a deterministic one-tape Turing
machine (the "compiled machine"). The tape cells are indexed by the
nonnegative integers; a left move at cell zero stays put; the input starts
at cell zero and is followed by blanks; a returned string starts at cell
zero and ends at its first blank. The construction below never runs
f_eta; it only reads the finite transition table of the machine.
The alphabet Sigma contains two disjoint triples of "code letters"
(b_T, a_T, c_T) and (b_G, a_G, c_G), plus special letters
z, d, l, r, h, zeta. This is fixed notation for Chapter 14; here it just
sits in the background.
13.1 Cells, paths, and sectors.
A CELL has an immutable BASE in Sigma union {C, D, W} and a finite TAG.
Bases in Sigma are "anchors"; C, D, W are two cuts and a workspace cell.
A tag records a few finite bits: whether an anchor was read, whether a
workspace cell is filled, a work symbol from the machine's tape alphabet,
whether an output has been read, and an output mark (a letter of Sigma or
"none"). The empty/clean tag has all bits unset, blank work symbol, and no
output mark.
The presentation is best drawn as a small graph (a "quiver"):
O --alpha--> L --heads--> R --omega--> O,
with two LOOPS at L and at R, one loop for every tagged cell b: a loop
b_L at L and a loop b_R at R. There are no vertex-identity generators; the
empty word is the global identity. We add a zero letter Omega, make it
absorbing, and make every incompatible pair of arrows equal to Omega: a
nonzero word is exactly a PATH in this quiver.
Cut a nonempty path at every occurrence of the two-arrow combination
omega alpha (this returns from R to O and immediately leaves again). What
remains are "sectors". Each sector contains at most one "head" (an arrow
from the finite set of head states), because getting from R back to L
requires crossing omega alpha. A sector with a head looks like
(optional alpha) (some L-loops) (a head) (some R-loops) (optional omega),
and sectors without heads are allowed. This notation describes both
complete computations and words with missing boundaries.
GRADE. Set grade(Omega) = 0 and grade(workspace cell) = 0; grade(cut cell
with base C) = 2; grade(every other generator) = 1. Tags do not affect
grade. Extend grade additively to words: gamma(w) = sum of grades of
letters. The maximum generator grade is M = 2. The whole point of
workspace cells having grade 0 is that we can insert as many as we like
without increasing grade (though the literal length grows).
THE HEADS we use are: raw head Q, quota head P, validator heads
I, J, J', N, V; a disjoint set of machine (simulation) heads; and a cleanup
head Z. For an anchor word x, the notation x_L or x_R means the sequence
of clean cell copies of x, sitting at L or at R.
A sector is FULL RAW if it has the form
raw(x) = alpha Q x_R omega for some x in Sigma^*.
The word x is its PAYLOAD.
13.2 Preparing a product for computation.
Two full raw sectors, with payloads x and y, are supposed to multiply:
the composite is to become raw(f_eta(xy)). To make that happen we first
impose the following equations (they are all equations, usable both ways in
the presentation; the arrows below show the forward direction the
evaluator will use):
slide: Q a_R = a_L Q for a in Sigma,
merge: Q omega alpha Q = C_L P D_R,
quota: P D_R = W_L P D_R,
entry: P D_R = I D_R.
"Slide" walks the raw head Q rightward across the first payload's letters.
"Merge" turns the meeting point of the two raw heads into cut cells with a
quota head. "Quota" lets us insert workspace cells (grade 0). "Entry"
turns the quota head into a validator head I sitting before the clean D_R.
13.3 Validation.
The validator checks that a candidate entry is CLEAN: both boundary cells
alpha and omega are present, the workspace cells are clean, the anchors on
both sides are clean copies of a word, and the cuts are correct. The
validator is a fixed finite list of equations, each moving one head across
one cell:
W_L I -> I W_R C_L I -> J C_R a_L J -> J a_R
alpha J -> alpha J' J' a_R -> a_L J' J' C_R -> C_L N
N W_R -> W_L N N D_R -> D_L V V a_R -> a_L V
V omega -> q_start omega
(these are equations; the arrows show the forward validator direction). A
passing entry reaches q_start exactly when the entry has the clean form
alpha x_L C_L W_L^s I D_R y_R omega, s >= 0.
The left sweeps check the clean workspace up to C and the clean anchors up
to alpha; the rightward sweeps re-check the anchors, the first cut, the
workspace, the second cut, and the anchors up to omega. Any dirty tag makes
a scan unable to proceed, i.e. it gets stuck (no rule applies).
13.4 The simulation and cleanup.
Once q_start is reached, we move the machine head to the first workspace
cell and run the compiled machine on the workspace, using the finite
transition table of f_eta. Each machine state has a designated reading
side; its scan instructions are expanded into finitely many equations of
the form q b_R -> b'_L q' or q b_R -> q' b'_R (right moves and stationary
moves) and their left-reading mirrors. Because there are finitely many
states, work symbols, and tags, this is a finite list of equations. A
failed test means no rule applies (stuck). A left move at the left end
stays put. Halt is recognised only at an in-bounds workspace cell. Then we
READ THE OUTPUT: rewrite the workspace content onto output marks on the
anchors, and finish in a fresh state q_ok with two cells' worth of
bookkeeping done.
Finally cleanup turns the whole thing back into a raw word:
q_ok omega -> Z omega,
b_L Z -> Z a_R for an anchor b with output mark a in Sigma,
b_L Z -> Z for every other tagged cell b,
alpha Z -> alpha Q.
Cleanup is deterministic and never increases grade. Applied to a
successful passing entry it leaves raw(f_eta(xy)) = alpha Q f_eta(xy)_R omega.
13.5 The component lemma.
The subtle point is that the presentation relations can be used BACKWARDS,
so the presented monoid is not just "forward computations". The way to
control it is to look at the WHOLE weak connected component of a sector's
local configuration graph.
For a validator or machine sector, consider the graph whose vertices are
configurations of that sector (fixed ordered bases, fixed boundary flags,
one head, finite tags) and whose edges are single internal forward
transitions (excluding "entry from P" and "exit to Z"). If the sector has k
cells and there are h internal head states with at most c tags per cell,
there are at most (k+1) h c^k configurations. So the weak connected
component is finite and can be searched effectively, without running the
machine and without waiting for anything to halt. (Quota insertion is kept
OUT of this graph, precisely because grade does not bound the number of
grade-0 workspace cells.)
LEMMA 13.1 (Components). Every internal weak component of a sector graph
has at most one "entry" (a configuration with head I just before clean
D_R) and at most one "success" (a configuration ending q_ok omega). If
both occur, the forward computation from the entry reaches that success,
and the entry has the clean form and genuine output of 13.3-13.4.
PROOF. An entry has internal indegree zero (the only possible predecessor
of an I-sector is a left sweep, whose output has clean W immediately right
of the head, whereas an entry has clean D). Every other validator sector
has indegree at most one; for each head, clean C versus an anchor
immediately to the right (or the mirror) distinguishes the possible
predecessors, and there are no transitions from machine states back to
validator states. The validator phases progress in their displayed order
and each sweep is finite, so a failing entry sits on an isolated finite
chain with no other entry in its component; a passing entry is determined
uniquely by its fixed base sequence and boundary flags. So at most one
entry.
Now the eventual-cycle argument. A finite directed graph with outdegree at
most one has, in each weak component, exactly one eventual cycle or
terminal vertex: the unique forward trajectories of two adjacent vertices
coincide eventually, and this propagates along weak paths. A sector ending
in q_ok omega is terminal, so it is the only such sector in its component
and every forward trajectory there reaches it. If an entry is present it
therefore passes validation and genuinely succeeds. Done.
13.6 The partial evaluator N_eta.
We can now define the partial word algorithm N_eta. It preserves the empty
word, sends every word containing Omega and every nonpath to Omega (using
the zero equations), and otherwise preprocesses sectors:
(1) Move each raw head Q to its leftmost reachable gap (slide).
(2) If a quota head P has clean D_R immediately to its right, remove all
immediately preceding clean W_L (quota). If clean C_L is then
immediately left, unmerge C_L P D_R into Q omega alpha Q and normalize
the two resulting raw heads; otherwise keep the trimmed sector.
(3) Run Z cleanup until it is stuck or becomes Q; in the latter case
normalize that raw head.
(4) For any validator or machine head, find its finite internal weak
component (Lemma 13.1). If a component has an entry, move to it and
revert to P, then apply rule (2). If it has no entry but has a
success, move there and apply cleanup. If neither, use the least
sector of the component in shortlex order.
Finally, replace every maximal run of t >= 2 consecutive full raw sectors
with payloads u_1, ..., u_t by the single full raw sector
alpha Q f_eta(u_1 u_2 ... u_t)_R omega. (13.1)
A run of length one is left unchanged, WITHOUT evaluating f_eta. The only
places N_eta calls f_eta are in (13.1), and the input to each such call has
length at most the total grade of the original word (each input letter
contributes one anchor, and grade counts anchors). This is the "bounded
call" property: grade-bounded inputs produce grade-bounded calls.
13.7 The compiler lemma.
LEMMA 13.2 (Bounded compiler). From a program index eta one can compute
a finite monoid presentation K_eta with zero Omega, a finite presentation
alphabet X_eta, and an additive grade gamma on words with 0 <= gamma(x)
<= 2 for every letter and gamma(Omega) = 0. There is a partial algorithm
N_eta, independent of any budget, such that:
(a) N_eta fixes the empty word, Omega, and every raw(u); it sends every
word containing Omega to Omega; on a word a its only calls to f_eta
are on words of length at most gamma(a).
(b) Suppose that for some integer m >= 0,
f_eta(w) is defined and |f_eta(w)| <= |w| for |w| <= m,
f_eta(x f_eta(w) y) = f_eta(x w y) for |xwy| <= m.
Then N_eta terminates on every word of grade at most m, joins each
such word to its literal output by a derivation whose intermediate
grades do not exceed the input grade, and a single presentation
equation used in any context preserves the output whenever both
endpoints have grade at most m. In particular
N_eta(u) = N_eta(v) implies N_eta(xuy) = N_eta(xvy)
whenever gamma(xuy), gamma(xvy) <= m.
(c) If those budget conditions hold for all m, then N_eta decides
equality in K_eta and N_eta(raw(u) raw(v)) = raw(f_eta(uv)).
PROOF (SKETCH, WITH THE GAPS FILLED IN THE ORIGINAL). Part (a) is by
inspection of Section 13.6: the only calls to f_eta are in (13.1), on
grade-bounded arguments; everything else is a finite computation.
Part (b) is where the grade bound and the component lemma do their work.
Every preprocessing operation (slide, quota, unmerge, cleanup, component
path) has a derivation that never raises grade: slides and entry-reversal
preserve grade; quota cells have grade 0; unmerge preserves grade because
gamma(C_L P D_R) = 2+1+1 = 1+1+1+1 = gamma(Q omega alpha Q); component
paths preserve every base and hence preserve grade; cleanup preserves or
decreases grade. The replacement (13.1) of a run is derivable without
raising grade by physically merging two raw sectors, running the machine,
and cleaning up, and it uses the budget identities
f_eta(f_eta(u1 u2) u3) = f_eta(u1 u2 u3) and so on; the successive
arguments to f_eta stay within the grade bound because f_eta is
length-nonincreasing. So every word of grade at most m has a
grade-nonincreasing derivation to its literal output, giving termination
and the derivation statement. The contextual statement (b)-in-context
follows by transplanting the two nonincreasing derivations into the context
x(-)y: additivity keeps every intermediate word within grade.
For one equation STEP to preserve the output in every context, check the
few kinds of equations: raw slides and quota changes give the same
leftmost gap and same trimmed sector; entry has the same preprocessing on
both sides (the component lemma gives priority to its entry, even if that
entry is malformed); internal validator/machine equations leave the weak
component unchanged; cleanup equations agree by forward determinism; a
merge is immediately undone by quota preprocessing; two code sides with
aligned starts have a union which is an entire code sequence, and
replacing a subword by a tested-equal word preserves the tested class by
the (b)-in-context hypothesis. The one remaining equation,
q_ok omega -> Z omega, is either in a component with no entry (both sides
use the same terminal cleanup) or with an entry (both sides compute the
same f_eta, and the neighbouring raw runs give f_eta(axyb) and
f_eta(a f_eta(xy) b), equal by the budget identity). This proves the
one-step contextual invariance.
Part (c) is now immediate: if the budget conditions hold at every m, every
finite derivation is covered by some budget, so equal monoid words have
equal N_eta answers and vice versa. Done (modulo the explicit case checks
spelled out in the original compiler appendix).
REMARK. The construction never evaluates f_eta; it only compiles its
finite transition table into a finite presentation. This is essential: at
the moment we build K_eta we do not yet know that f_eta is total or what it
computes. The fixed point and the induction of Chapter 14 will supply
that knowledge for our special choice of eta.
=================================================
14. The fixed point, the induction, and the two monoids
=================================================
We now choose the program eta so that its finite presentation K_eta is the
K we want, and prove f_eta has the budget properties that let N_eta decide
equality. Then we build the two monoids H and K, the maps kappa, c, and the
separator z.
14.1 Codes.
First consider any program index eta, giving presentation alphabet X_eta
via the compiler. Let Y be the disjoint union of X_eta and a fixed finite
generating alphabet for the monoid P of Chapter 12. For a Y-word v, write
v_K and v_P for its projections to the two alphabets (delete the letters of
the other). Its TESTED CLASS is:
* zero, if N_eta(v_K) = Omega;
* otherwise, the pair ( N_eta(v_K) , the value of v_P in P ).
This is a partial test (it may not terminate), which is exactly why we need
the fixed point and the induction.
There is a second kind of code. Fix a finite monoid generating alphabet Z
for G-hat that includes the inverses of a finite group generating set of
G-hat. Test Z-words by their value in G-hat. This test is total by the
monoid theorem hypothesis (G-hat has a solvable word problem).
Choose (computably) an integer D_0 > M = 2 with
2^{D_0 - 1} >= max(|Y|, |Z|).
Encode the letters of Y, in their chosen order, by distinct words that
begin with b_T and continue with D_0 - 1 letters from {a_T, c_T}, in
lexicographic order. Encode the letters of Z the same way using the triple
(b_G, a_G, c_G). Write C(v) for the concatenation of the codes of the
letters of a word v, and C(empty) = empty. The type of a nonempty code
sequence is unambiguous, because b_T and b_G differ. Codes preserve
shortlex comparison and have length D_0 per generator.
14.2 Envelope spacing.
Enumerate all nonempty finite ordered tuples
( w_1^{(j)}, ..., w_{s_j}^{(j)} ) j = 1, 2, 3, ...
of distinct Sigma-words avoiding the letter zeta (the empty word is allowed
as a member). Choose integers N_j recursively so that
N_j > j,
N_j > max_i |w_i^{(j)}|,
N_j > 2 N_h + 2 + max_i |w_i^{(h)}| for h < j. (14.1)
These conditions concern ALL potential earlier envelopes, not just the ones
that will be selected. The N_j are computable without doing any
tested-class evaluation. The inequalities make the "selector" left sides
(which have long runs of l and r letters) mutually non-overlapping and
separated from each other and from any code of comparable length.
14.3 The rule table R_n and the partial procedure F(eta, w).
Define a partial procedure F(eta, w) as follows. Put n = |w| and form the
finite rule table R_n.
STEP 1 (static rules). Include zeta a -> zeta and a zeta -> zeta for every
letter a in Sigma. For each nonempty Y-word v with D_0 |v| <= n, test its
class.
* If it is zero, include C(v) -> zeta.
* Otherwise find the shortlex least word v' of the same tested class
among all words of length at most |v|, including the empty word, and
include C(v) -> C(v') if v' != v.
Do the same for Z-words using equality in G-hat, with no zero case. These
are the STATIC rules; they are decided by testing words of length at most
n / D_0.
STEP 2 (selector rules). Process the tuples with N_j <= n in increasing
order of j. If every member of tuple j has no reducible occurrence under
the static rules and the previously selected rules, include
d l^{N_j} w_i^{(j)} r^{N_j} h -> empty if i = 1,
-> zeta if i > 1. (14.2)
Some of these left sides may be longer than n; they simply cannot act on
the input w.
STEP 3 (reduce). Reduce w until no rule applies, using a fixed
deterministic choice of occurrence and rule.
Whenever the tests terminate, the last step terminates: every rule
decreases shortlex (a nonempty code reduced to zeta shortens since
D_0 > 2; all non-code rules shorten too). So F is a uniformly partial
computable function of (eta, w).
14.4 The fixed point.
Effective substitution of parameters gives a total computable index
transformation tau(eta) for the partial function F(eta, -). Kleene's
Recursion Theorem supplies an index eta with
f_eta(w) = F(eta, w) as partial functions. (14.3)
Let us write the short parameterisation argument. Let U be universal
evaluation and let d(a) be an effective index for the partial function
w -> U(U(a,a), w). Choose an index b computing the total function
a -> tau(d(a)). For eta = d(b),
U(eta, w) = U(U(b,b), w) = U(tau(d(b)), w) = F(eta, w).
Only now fix the presentation alphabet X_eta and the code length D_0 that
belong to this particular eta. There is no advance bound on the machine's
size or working space. Write f = f_eta and K = K_eta.
14.5 The length induction.
LEMMA 14.1 (Bootstrap). The function f is total and length-nonincreasing.
The rule tables are stable on bounded-length words: for k <= n, R_k and
R_n have the same rules whose left sides have length at most k. Each R_n
is confluent on words of length at most n, and
f(x f(w) y) = f(x w y) for all words x, w, y. (14.4)
PROOF. We prove all bounded assertions together by induction on n. For
n = 0 there are no tested classes or tuple decisions, and the empty word is
unchanged. Suppose n > 0 and the assertions are known at all smaller
bounds.
TERMINATION OF TESTS. Every use of N_eta in a static test, including each
candidate in a least-representative search, is on a Y-word of length at
most floor(n / D_0). Its K-projection has grade at most
m = M floor(n / D_0) < n. (14.5)
The induction hypothesis supplies the budget conditions of Lemma 13.2 at
m. Lemma 13.2 therefore makes all these tests terminate. There are only
finitely many tests and tuple decisions, and the subsequent
shortlex-decreasing reduction terminates. So f is defined on every word of
length n; by induction f is total and length-nonincreasing.
STABILITY. For a fixed generator word v, its static rule is determined by
the same tests and the same candidates of length at most |v| at every
larger bound. Consider a tuple with N_j <= k <= n. Each tested body has
length less than N_j, hence less than k. New static left sides longer than
k cannot occur in it. Induction over earlier tuple numbers shows that the
previously selected rules that can occur in the bodies also agree. Hence
the decision for tuple j agrees at both bounds. A new tuple with N_j > k
has every selector side longer than k, so cannot add a rule acting on a
word of length at most k. This proves stability, including for selected
rules that are too long to act at the smaller bound.
LOCAL CONFLUENCE. All reductions stay inside the length-<=n ball.
Disjoint occurrences can be reduced in either order. If the word contains
zeta, every branch retains it (absorption keeps zeta, no other rule has a
left side containing zeta), so absorption joins all branches at zeta. The
remaining overlaps are checked explicitly.
* Selectors from different stages. Let the older left side have total
length L and the newer one be d l^N w r^N h. By (14.1), L < N and
|w| < N. A nonempty old suffix cannot equal a new prefix (the old
ends in h, while a prefix of length at most L lies in the initial
l-run), and an old prefix cannot equal a new suffix (first letters d
versus r or h). These exclude proper boundary overlaps. For
containment, an old occurrence cannot start at the new initial d
(its terminal h would lie in the initial l-run); any other start
must be in the body, and cannot leave the body, hence (by the newer
tuple's irreducibility test) does not exist.
* Selectors from one stage. A second start strictly inside one side lies
in its body, but then fewer than N body letters remain before the
final r-run, so it cannot be followed by N consecutive l's. If two
sides start at the same place with different body lengths, the
shorter one's terminal h falls in the longer one's final r-run (both
body lengths are less than N). Equal body lengths force equal bodies,
hence the same rule (members of a tuple are distinct). This also
covers an empty body.
* A code and a selector. Code letters are disjoint from the envelope
markers, so an overlapping code side would lie wholly inside a
selector's body; the static irreducibility test excluded this. All
static sides short enough to occur there were present when the tuple
was processed, because the body length is less than N_j.
* Two code sides. They have the same type and aligned starts (within a
code sequence, b_T or b_G occurs only at a block boundary). Their
union is an entire code sequence C(v), of length at most n. For group
codes, a replacement preserves the value of this union by group
multiplication. For product codes, replacing a subword by a nonzero
tested-equal word preserves the tested class of the union by the
(b)-in-context hypothesis of Lemma 13.2 and equality in P: each old
or new union has generator length at most floor(n / D_0), hence its
K-projection has grade at most m. If a subword tests zero, apply
(b)-in-context to its K-projection and Omega; the union then tests
zero, so one branch reduces the whole union to zeta and the other
either does the same or retains a zero-class sequence (which its
whole-word zero rule reduces to zeta; the sequence is nonempty since
N_eta(empty) = empty != Omega). If the union class is nonzero with
least representative v_*, either branch yields a word v_b of the same
class with |v_b| <= |v|, and v_* is also the least candidate within
this smaller bound; so both branches reduce to C(v_*).
This exhausts the local peaks. Termination and local confluence give
confluence on the ball by Newman's Lemma: by well-founded induction,
assume every proper descendant of a word has a unique normal form; any two
first steps have a common descendant by local confluence, and the
induction hypothesis makes their normal forms equal.
CONTEXT. If |xwy| <= n, perform inside x(-)y the normalisation of w
computed at bound |w|. By stability every rule used belongs to R_n, and
length never increases. Confluence gives f(x f(w) y) = f(x w y). This
establishes the budget conditions at n and completes the induction. Done.
CONSEQUENCE. By Lemma 14.1 the budget conditions of Lemma 13.2 hold at
every length. So the compiler supplies an equality test for K, and in
particular the identity of K and its zero are distinct.
14.6 The two monoids.
Define H to be the monoid on Sigma whose equations are the union of all
the rule tables R_n. Every word is related to its computed normal form,
which is irreducible for this union by stability. Conversely, a contextual
use of any single equation preserves that form (choose a bound containing
both endpoints and the equation, then use stability and confluence from
Lemma 14.1). Hence:
two words represent the same element of H <=> their f-outputs agree.
This decides the word problem of H. The empty word and the letter zeta are
distinct irreducibles; they are the identity 1_H and the absorbing zero
zeta of H.
The product monoid. The tested product classes are now the actual elements
of
T = ( (K minus {Omega}) x P ) union { 0_T },
with coordinatewise multiplication and every pair whose first coordinate is
Omega collapsed to 0_T. A letter of X_eta acts in the first coordinate and
a generator of P in the second; the letter Omega maps to 0_T. Thus the
finite alphabet Y generates T.
THE MAP kappa. For a nonzero element of T, take its least shortlex
Y-representative v. The code C(v) is irreducible: a subcode rule would
either force the element to be zero or produce a smaller representative,
and no selector or absorption side occurs in a pure code word. Every other
representative reduces by its whole-word rule to this same code, and every
zero-class code reduces to zeta. Consequently coding defines an injective
zero-preserving monoid map
kappa : T -> H.
It is unital (the least representative of the identity is empty) and
multiplicative (codes concatenate). The identical argument for Z-words
embeds G-hat unitally in H; its image consists of units, because products
of mutually inverse group words have the empty representative. So
G-hat -> H^x is injective. This proves (i) and (ii) of Theorem 4.2.
THE SEPARATOR z. Let z in H be represented by the separator letter z. For
least representatives v, v' of elements of T minus {0_T}, the words
C(v) z C(v')
are irreducible: no code crosses the separator, each code portion is
already irreducible, and there are no selector markers or zeta. These
literal words recover the ordered pair (v, v'), including when one or both
representatives are empty. They are nonzero because none equals zeta. This
proves the separator assertion (v).
THE SELECTORS. Take any ordered tuple of distinct nonzero elements
h_1, ..., h_s of H, and let w_1, ..., w_s be their normal words. These
words avoid zeta (any word containing it reduces to the zero word). Their
tuple occurs in the enumeration, say at stage j. A word irreducible for the
final rule set is irreducible for the static and selected rules present at
stage j, so this tuple passes its test. With
L = d l^{N_j}, R = r^{N_j} h
as elements of H, the selected equations give L h_1 R = 1_H and
L h_i R = zeta for i > 1. (A tuple containing the identity is covered, its
normal representative being empty.) This proves the selector property
(iii).
THE MAP c. Define a multiplicative map in the opposite direction by
c : H -> K, c([w]) = [ raw(f(w)) ].
The normal-form characterisation of H makes this well defined. Every raw
singleton is its own literal N_eta-output, so distinct normal words give
distinct elements of K, and none of these elements is the identity or the
zero of K. For normal words u, v, the raw-product rule of Lemma 13.2(c)
gives
c([u]) c([v]) = [ raw(f(u)) raw(f(v)) ] = [ raw(f(uv)) ] = c([uv]).
So c is injective and multiplicative, as required by (iv). It is not
unital: even c(1) = [ raw(empty) ] is distinct from 1_K. And c(zeta) is not
Omega; it is absorbing only within c(H).
This completes the proof of the monoid theorem (Theorem 4.2). The finite
presentation of K came from the compiler; the finite alphabet and the
normal-form procedure give the finite generation and decidability of H.
=================================================
15. From monoids to the algebra package
=================================================
Now we turn the two monoids into the algebra package (Theorem 4.1). This is
where simplicity, the self-embedding, the corner matrix units, and the
detector all appear.
15.1 Contracted monoid algebras.
Throughout this chapter k = F_2. For a monoid D with zero 0_D != 1_D, the
CONTRACTED MONOID ALGEBRA k_0[D] has k-basis the set D minus {0_D}. Basis
elements multiply as in D, and a product that would equal 0_D is
interpreted as the zero vector. It is a unital algebra: the identity is the
basis element 1_D. (The "contracted" means we threw away the zero element
of D, so 1_D != 0 and the algebra is nonzero.)
Apply the monoid theorem (Theorem 4.2) with G-hat = L (the group we want to
embed). It gives the finitely presented monoid K (zero Omega) and the
decidable monoid H (zero zeta), together with kappa, c, z. Set
A_0 = k_0[H], B = k_0[K].
Both are nonzero algebras. We take care to distinguish four things: the
monoid elements zeta and Omega, the zero vector of an algebra, and the
element c_zeta. The element c_zeta is a nonzero basis element of B, so it is
distinct from all three.
15.2 The algebra embeddings.
LEMMA 15.1 (Algebra embeddings). The algebra A_0 is simple, the algebra B
is finitely presented, and there are injective algebra homomorphisms
i : A_0 -> B,
rho : B (x)_k k[P] -> A_0.
Here k[P] is the ordinary monoid algebra of the partial-affine monoid P.
The map rho is unital. The map i is nonunital with support identity
e = i(1_{A_0}) != 1_B.
PROOF. (a) A_0 is simple. Take a nonzero element
a = sum_{j=1}^d lambda_j h_j of A_0, with distinct nonzero-support
elements h_j in H minus {zeta} and nonzero coefficients lambda_j in k.
Apply the selectors of Theorem 4.2(iii) to the tuple (h_1, ..., h_d):
there are L, R in H with L h_1 R = 1_H and L h_i R = zeta for i >= 2. In
the contracted algebra this gives
L a R = lambda_1 1_{A_0},
a nonzero scalar of the identity. Hence every nonzero two-sided ideal
contains the identity, so A_0 is simple. (The argument covers a support
element equal to 1_H too.)
(b) i is defined by i(h) = c_h - c_zeta on basis elements h != zeta, and
extended linearly. First note the multiplicative properties of c:
c_h c_{h'} = c_{h h'}, c_h c_zeta = c_zeta c_h = c_zeta,
c_zeta^2 = c_zeta,
using that c is multiplicative and that zeta is absorbing in H. Hence
(c_h - c_zeta)(c_{h'} - c_zeta) = c_{h h'} - c_zeta.
When h h' = zeta this is zero, exactly matching the contraction in
k_0[H] (where the product h h' is the zero vector). So i is multiplicative.
The vectors c_h are distinct nonzero basis elements of B, and in particular
the coefficient of c_h (for h != zeta) in i(a) equals the coefficient of h
in a. So i is injective. Its support identity is
e = c_{1_H} - c_zeta, e^2 = e,
e i(a) = i(a) e = i(a).
Since neither basis vector in e is 1_K, e != 1_B, and indeed 1_B is not in
i(A_0).
(c) B is finitely presented. The monoid K is finitely presented, say by
finitely many generators and equations. Adjoin a generator Omega and a
relation identifying it with a word representing the zero, so Omega is a
presentation letter. Now take the same generators in a free associative
unital k-algebra, replace each monoid equation u = v by u - v = 0, and
impose Omega = 0 (i.e. the relation making Omega the zero vector, with
2 . 1 = 0 already automatic over F_2). The binomial ideal so generated is
exactly the span of all differences of words in the same monoid
congruence class: one inclusion is because each contextual use of a
defining equation is a binomial in the ideal and a chain of uses telescopes,
the other by mapping each word to its congruence class in the free vector
space on K. The quotient has basis K; imposing Omega = 0 removes exactly
the absorbing zero class and gives B. So B is finitely presented.
(d) rho. The nonzero basis pairs give a unital algebra isomorphism
B (x)_k k[P] ~= k_0[T], b (x) p -> (b, p),
where T is the product monoid of Theorem 4.2(ii) (products acquiring
K-coordinate Omega vanish on both sides). The linear extension of kappa is
the required injective unital map rho : B (x)_k k[P] -> A_0 = k_0[H]. Done.
Identify A = i(A_0) as a subalgebra of B. It is simple, with its own
identity e. By Theorem 4.2(i), L embeds in A^x: a unit of H and its inverse
give inverse basis elements in A_0, which i sends to units of A relative to
e.
15.3 The partial-affine corner.
For a dyadic rational a, let e_a denote the partial identity on the
rational tail [a, infinity) intersected with Q. These maps belong to P:
u^{-1} v is translation by 1, its powers and conjugates by powers of u give
all dyadic translations, and conjugating e_0 by translation by a gives e_a.
In the monoid P itself,
e_a e_b = e_{max(a,b)}, w e_a w^{-1} = e_{w(a)} (15.1)
for every available full increasing affine map w. These are equalities of
basis elements in the abstract algebra k[P].
LEMMA 15.2 (Binary tail corner). There is a nonzero idempotent q in k[P]
and elements s'_0, s'_1, t'_0, t'_1 in q k[P] q with
t'_i s'_j = delta_{ij} q,
s'_0 t'_0 + s'_1 t'_1 = q.
PROOF. Set q = e_0 - e_1. Its two basis elements and 1_P are distinct, so
q != 0, 1, and (15.1) gives q^2 = q. Put
w_0 = u, w_1 = v,
q_0 = w_0 q w_0^{-1} = e_0 - e_{1/2},
q_1 = w_1 q w_1^{-1} = e_{1/2} - e_1.
Using (15.1) and expanding in the monoid basis gives
q_0^2 = q_0, q_1^2 = q_1, q_0 + q_1 = q,
q_0 q_1 = q_1 q_0 = 0
(for example q_0 q_1 = e_{1/2} - e_1 - e_{1/2} + e_1 = 0). In particular
q q_j = q_j q = q_j. Define s'_j = w_j q and t'_j = q w_j^{-1}. Then
s'_j t'_j = q_j and t'_j s'_j = q. The identities s'_j = q_j w_j and
t'_j = w_j^{-1} q_j, together with q q_j = q_j q = q_j, show that s'_j and
t'_j lie in q k[P] q (they are absorbed by q on both sides). Moreover
t'_j q_j = t'_j and q_j s'_j = s'_j, so for i != j,
t'_i s'_j = t'_i q_i q_j s'_j = 0.
Finally s'_0 t'_0 + s'_1 t'_1 = q_0 + q_1 = q. Done.
15.4 The self-embedding phi and the corner pairs.
Define
j : B -> A_0, j(b) = rho(b (x) q),
phi = i o j : B -> B.
These are nonunital algebra homomorphisms. The map j is multiplicative
because q^2 = q, and injective because q != 0 and tensor products are over
the field k (b (x) q = 0 forces b = 0). Hence phi is injective and
phi(B) is contained in A.
Let
p = phi(1_B),
s_l = i rho(1_B (x) s'_l),
t_l = i rho(1_B (x) t'_l) for l = 0, 1.
The idempotent p belongs to A, so p != 1_B. Applying the two algebra maps
to Lemma 15.2 gives
s_l, t_l in p B p,
t_l s_j = delta_{l j} p,
s_0 t_0 + s_1 t_1 = p. (15.2)
These corner elements commute with phi(B): indeed, for b in B,
(b (x) q)(1_B (x) s'_l) = b (x) s'_l = (1_B (x) s'_l)(b (x) q),
and the identical calculation holds for t'_l; now apply i rho. This
supplies the binary matrix units of Theorem 4.1(iv), centralising phi(B).
15.5 The separating tensor vector.
This is the last ingredient: the detector b_* of Theorem 4.1(v). As in
Chapter 6, R = B (x) B^{op} acts on B by (a (x) b^{op}) . m = a m b, and
psi = phi (x) phi^{op}.
We need one vector on which psi(r) acts nontrivially for every r != 0.
Let W = rho(B (x) k[P]) inside A_0, with basis { kappa(tau) : tau in
T minus {0_T} }. Part (v) of the monoid theorem proves that the linear map
D : W (x)_k W^{op} -> A_0, D(x (x) y^{op}) = x z y,
is injective: it sends distinct basis tensors to distinct nonzero basis
elements of A_0 (this includes tensors with an identity factor). Since
j(B) is contained in W, the composite
R --> W (x) W^{op} --> A_0 --> B,
r --> (j (x) j^{op})(r) --> D(...) --> i(...)
is a sequence of injective linear maps. For r = sum_ν a_ν (x) b_ν^{op}, its
value is
sum_ν i(j(a_ν)) i(z) i(j(b_ν)) = psi(r) . i(z).
Thus b_* = i(z) satisfies
r != 0 implies psi(r) . b_* != 0. (15.3)
The assertion concerns the action after applying psi; its proof uses the
explicit separator vector z. Done.
PROOF OF THEOREM 4.1 (Algebra package). The algebra B is nonzero and
finitely presented (Lemma 15.1). Its subalgebra A = i(A_0) is simple with
identity e and contains L in its unit group. The map phi is injective,
has image in A, and has proper support p. Equation (15.2) supplies the
binary pairs centralising phi(B), which give the ring identities
(4.1)(iv). Equation (15.3) supplies the detector b_*. These are all the
asserted data. Done.
This closes the logical loop. We have proved:
* the monoid theorem (Theorem 4.2), in Chapter 14;
* the algebra package (Theorem 4.1), here;
* the envelope theorem (Theorem 1.3), in Chapters 5-9;
* the main theorem (Theorem 1.2), in Chapters 10-11.
=================================================
16. References
=================================================
The proof uses the following published results, which are not reproved
here. Labels match the citations in the text.
Boone-Higman conjecture and its history:
W. W. Boone and G. Higman, An algebraic characterization of groups with
soluble word problem, J. Austral. Math. Soc. 18 (1974), 41-53.
G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. London
Ser. A 262 (1961), 455-475.
R. J. Thompson, Embeddings into finitely generated simple groups which
preserve the word problem, in Word Problems II (1980), 401-441.
J. Belk, C. Bleak, F. Matucci, M. C. B. Zaremsky, Progress around the
Boone-Higman conjecture, arXiv:2306.16356 (2025).
J. Belk, C. Bleak, F. Matucci, M. C. B. Zaremsky, Hyperbolic groups
satisfy the Boone-Higman conjecture, Duke Math. J. 175 (2026),
1519-1592.
J. Belk, F. Fournier-Facio, J. Hyde, M. C. B. Zaremsky, Boone-Higman
embeddings of Aut(F_n) and mapping class groups of punctured surfaces,
arXiv:2503.21882 (2026).
K.-U. Bux, C. Llosa Isenrich, X. Wu, On the Boone-Higman conjecture for
groups acting on locally finite trees, arXiv:2408.05673 (2025).
Twisted Brin-Thompson groups and the finite-presentation criterion:
J. Belk and M. C. B. Zaremsky, Twisted Brin-Thompson groups, Geom. Topol.
26 (2022), 1189-1223.
M. C. B. Zaremsky, Finite presentability of twisted Brin-Thompson groups,
Proc. Roy. Soc. Edinburgh Sect. A (2024); arXiv:2405.18354.
Steinberg groups and K-theory:
S. Krstic and J. McCool, Presenting GL_n(k<T>), J. Pure Appl. Algebra 141
(1999), 175-183.
C. A. Weibel, The K-book: An Introduction to Algebraic K-Theory, GSM 145,
Amer. Math. Soc., 2013.
H. V. Khanh, General linear and Steinberg groups over the Leavitt algebra
L_{F_2}(1,2), arXiv:2609.08428 (2026).
Machine encodings and rewriting:
E. L. Post, Recursive unsolvability of a problem of Thue, J. Symbolic
Logic 12 (1947), 1-11.
V. L. Murskii, Isomorphic imbeddability of a semigroup with an enumerable
set of defining relations into a finitely presented semigroup,
Mat. Zametki 1 (1967), 217-224.
M. H. A. Newman, On theories with a combinatorial definition of
"equivalence", Ann. of Math. 43 (1942), 223-243.
J. L. Britton, The word problem, Ann. of Math. 77 (1963), 16-32.
Recursion and decidability:
S. C. Kleene, On notation for ordinal numbers, J. Symbolic Logic 3
(1938), 150-155.
S. I. Adian, W. W. Boone, G. Higman (eds.), Word Problems II, Studies in
Logic and the Foundations of Mathematics 95, North-Holland, 1980
(including Aanderaa-Cohen and the Kuznetsov argument cited in
Chapter 11).
Leavitt and module-type constructions:
W. G. Leavitt, The module type of a ring, Trans. Amer. Math. Soc. 103
(1962), 113-130.
That is the whole proof. A finitely generated group has a solvable word
problem precisely when it embeds in a finitely presented simple group.