SIMPLE F_INFINITY OVERGROUPS OF GROUPS
WITH DECIDABLE WORD PROBLEM

A complete proof, written for a reader who has seen groups
but not necessarily homology or advanced algebra.

ABSTRACT

Every finitely generated group with decidable word problem
embeds in a simple group of type F_infinity. This proves the
higher-finiteness strengthening of the Boone-Higman conjecture.

--------------------------------------------------------------------
0. A QUICK GUIDE FOR THE READER
--------------------------------------------------------------------

This paper is long because the proof builds a very complicated
object step by step. To help you, here is the plan in plain words.

A group is a set of symmetries that you can compose and undo.
The word problem asks: given a list of moves (a word in the
generators), can you decide by an algorithm whether the moves
cancel back to doing nothing?

A group is finitely presented if it can be described by finitely
many generators and finitely many rules (relations). A group is
simple if it has no normal subgroups except the trivial one and
the whole group. A group has type F_infinity if it has a
classifying space with only finitely many cells in each dimension.
This is a strong finiteness condition; in particular it implies
the group is finitely presented.

Our main theorem says: if a finitely generated group has a
decidable word problem, then it sits inside a simple group that
is as finitely describable as possible in every dimension.

The proof has three big ingredients.

(1) A ring that encodes its own action.
    We construct a finitely presented ring B such that the
    elementary matrix group E_7(B) acts on B^7 in a very flexible
    way. The ring is built using a "compiler" and a length
    induction; this is the most technical part (Section 2).

(2) An ascending torus criterion.
    We give a criterion for a group built from an injective
    endomorphism (an HNN extension) to have type F_infinity.
    The criterion uses two finite systems of idempotents over
    F_2 and F_3 to kill homology by 2 and by 3 (Section 1).

(3) Twisted Brin-Thompson groups.
    A theorem of Belk and Zaremsky turns a highly transitive
    action with finite-type stabilizers into a simple group of
    type F_infinity containing the acting group (Section 3).

We apply (1) and (2) to build a highly transitive action of a
group Lambda containing the original group G, with all finite
point stabilizers of type F_infinity. Then (3) gives the simple
overgroup H.

Each section begins with a short explanation of what it does
and why. The proofs are complete, but the exposition tries to
explain the ideas before the formulas.

--------------------------------------------------------------------
1. INTRODUCTION
--------------------------------------------------------------------

1.1 The main theorem

Let G be a finitely generated group. We say G has a decidable
word problem if there is an algorithm which, given a word in
the generators and their inverses, decides whether the word
represents the identity element.

A group H has type F_n if there is a CW complex K(H,1) with
finite n-skeleton. It has type F_infinity if there is a CW
complex K(H,1) with finitely many cells in each dimension.
Here K(H,1) is a connected CW complex with fundamental group H
and contractible universal cover. Type F_1 is finite generation;
type F_2 is finite presentation.

THEOREM 1.1 (Main theorem).
Every finitely generated group G with decidable word problem
admits an injective homomorphism into a nontrivial simple group H
of type F_infinity.

The input group need not be finitely presented, and its word
problem algorithm can run as slowly as you like. The group H can
have torsion and can have infinite cohomological dimension.
The theorem implies the Boone-Higman conjecture, which asked
whether the simple overgroup can always be finitely presented.

Conversely, any finitely generated subgroup of a finitely
presented simple group has decidable word problem. This is a
classical observation: run two searches in parallel, one
enumerating consequences of the relations, and one enumerating
consequences after adding the candidate word as a relation.
Since the simple group is nontrivial, exactly one search
succeeds. Thus the groups in Theorem 1.1 are exactly the
finitely generated subgroups of simple groups of type F_infinity.

1.2 Background

Higman's embedding theorem characterizes the finitely generated
subgroups of finitely presented groups as the recursively
presented groups. Boone and Higman refined this: a finitely
generated group has decidable word problem if and only if it
embeds in a simple group which in turn embeds in a finitely
presented group. They asked whether the simple group itself can
be finitely presented. Thompson showed the simple group can be
chosen finitely generated with decidable word problem.

Thompson-type groups have long supplied simple groups with good
finiteness properties. Brown proved type F_infinity for the
Thompson-Higman families. Belk and Zaremsky constructed a simple
group of type F_infinity containing all finitely generated
right-angled Artin groups. Belk, Hyde and Matucci constructed a
simple group of type F_infinity containing every countable
abelian group.

Recent work has proved the Boone-Higman conjecture for several
classes: hyperbolic groups and contracting self-similar groups
(Belk-Bleak-Matucci-Zaremsky), and Aut(F_n) and mapping class
groups of punctured surfaces (Belk-Fournier-Facio-Hyde-Zaremsky).
Those results do not by themselves give simple overgroups of
type F_infinity. Higher finiteness requires controlling
relations among relations in every dimension.

1.3 The idea of the proof

The final step uses the twisted Brin-Thompson construction of
Belk and Zaremsky. Its input is a faithful action of a group
Lambda on a countably infinite set S. The action must be
oligomorphic: it has finitely many orbits on finite subsets of
each fixed cardinality. If Lambda and all its finite-set
stabilizers have type F_infinity, then there is a simple group
SV_Lambda of type F_infinity containing Lambda.

So we need to embed G in a group Lambda with a highly transitive
action whose finite point stabilizers have type F_infinity.

We build Lambda from a finitely presented ring B and its
elementary group Q = E_7(B) acting on the column set X = B^7.
We construct injective maps delta: Q -> Q and sigma: X -> X
that are compatible with the action. At each stage, matrices can
permute any finite collection of the compressed columns sigma(X).
Taking direct limits and adjoining a stage-shift element t gives
a group Lambda acting on a set S. This action is highly
transitive. The same construction embeds G into Q.

The ring B must encode an action built from its own elementary
group on B^7. This is a self-reference. We resolve it by a
length induction: a finite compiler gives equality calculations
at each finite bound; the encoding ensures recursive calls use
strictly smaller bounds. Kleene's recursion theorem supplies
the program, and the length induction proves totality and
compatibility with multiplication.

Finiteness is supplied by the ascending-torus criterion. For an
injective endomorphism f: U -> U, write
T(U,f) = < U, t | t^{-1} u t = f(u) for u in U >.
A factorization of f through a finitely presented group gives a
finite presentation of T(U,f). For higher finiteness, we use two
finite systems of homomorphisms whose images commute in
specified pairs. Their product identities come from orthogonal
idempotents over F_2 and F_3. After lower-dimensional terms have
been killed, commuting products act additively on homology. The
two systems force the same class to be annihilated by both 2
and 3, hence to vanish.

The essential point is uniformity. We use simplices whose
vertices are elements of U, and regard two simplices as having
the same type when they differ by simultaneous left translation.
One iterate and one finite set of output types work for every
cycle using a given finite set of input types. Chain lengths and
coefficients can be arbitrarily large. This control allows
fillings with coefficients in products of copies of the group
ring, and the Bieri-Eckmann finiteness method then gives finite
skeleta in every dimension.

1.4 Organization

Section 2 proves the ascending-torus criterion (Theorem 2.1).
Section 3 constructs the ring B and the encoded actions
(Theorem 3.1). Section 4 constructs the highly transitive action
of Lambda and proves type F_infinity for its stabilizers
(Theorem 4.1). Section 5 applies the twisted Brin-Thompson
theorem and proves Theorem 1.1.

1.5 Conventions

All rings are unital and associative unless stated otherwise.
Ring embeddings and endomorphisms need not preserve the identity
when this is expressly stated. All homology is integral. Group
actions are on the left; coefficient modules for group homology
are right modules. The notation F_l denotes the field with l
elements. The elementary group E_r(R) is generated by the
off-diagonal elementary matrices I + b * e_{ij}, where e_{ij} is
a matrix unit and b is in R.


--------------------------------------------------------------------
2. THE ASCENDING TORUS CRITERION
--------------------------------------------------------------------

This section proves a criterion for a group built from an
injective endomorphism to have type F_infinity. The criterion is
used later for the group Lambda and for its finite point
stabilizers. The main idea is to use two finite systems of
idempotents, one over F_2 and one over F_3, to force certain
homology classes to be annihilated by both 2 and 3.

Throughout, l is either 2 or 3. Let D_l be the unital F_l-algebra
of operators generated by l_0, l_1, r_0, r_1 on the free vector
space with basis {0,1}^N. The operator l_i prefixes i, and r_i
deletes an initial i and sends every other basis vector to zero.
Thus
    r_i l_j = delta_{ij} 1,
    l_0 r_0 + l_1 r_1 = 1.
For a finite binary word v, l_v prefixes v, r_v deletes v, and
E_v = l_v r_v.

Every product of these operators is zero or a prefix replacement
l_v r_w. Equality of finite linear combinations of prefix
replacements is decidable. Indeed, choose m at least as large as
every domain prefix length and expand each term by
    l_v r_w = sum_{|a| = m - |w|} l_{va} r_{wa}.
Collect terms with the same domain prefix and the same output
prefix. For a fixed domain prefix, distinct output prefixes give
distinct outputs on an input whose remaining tail is not
eventually periodic. Equality of two such outputs with different
prefixes would make the shorter prefix a prefix of the longer and
would force the remaining tail to be periodic. Thus the collected
coefficients all vanish if and only if the operator vanishes.
This is a finite test over F_l.

Put
    A = E_{00},   B' = E_{01},   C' = E_1,
    A_0 = E_{000},   A_1 = E_{001}.
For each of the three prefix-free lists
    (00,01,1),   (000,01,1),   (001,01,1),
the operators l_v r_w form matrix units for a copy of M_3(F_l)
inside D_l. Only the first of these copies has identity 1. Let
P_l be the union of their sets of idempotents, together with
I = 1. This is a finite, explicitly specified set. In the
following statement, orthogonal means EP = PE = 0.

LEMMA 2.1 (Idempotent additivity).
Let T be an abelian group, and suppose that elements z_E in T,
indexed by E in P_l, satisfy
    z_{E+P} = z_E + z_P
whenever E, P, E+P are in P_l and E, P are orthogonal. Then
l z_I = 0.

PROOF.
Within a rank-three matrix algebra, we show that the l-multiples
attached to its diagonal units agree. The overlapping corners
then identify these multiples for A, A_0, A_1, B', C', and the
split A = A_0 + A_1 forces their common value to vanish.

First work in any one of the three matrix algebras. For a column
vector u and a row covector lambda with lambda u = 1, write
x(u,lambda) = z_{u lambda}. Fix v not zero in ker lambda. We claim
that x(u+v,lambda) - x(u,lambda) is independent of the choice of
u with lambda u = 1.

Suppose first that u' - u and v are linearly independent. The
vectors u, u' - u, v then form a basis, so there is a covector mu
with
    mu u = mu u' = 0,   mu v = 1.
The identity
    u lambda + v mu = (u+v) lambda + v (mu - lambda)
expresses the same rank-two idempotent in two ways as a sum of
orthogonal rank-one idempotents. Applying additivity gives
    x(u+v,lambda) - x(u,lambda) = x(v,mu) - x(v,mu-lambda).
The same calculation for u' gives the same difference. If instead
u' - u belongs to the span of v, choose w in ker lambda not in
 and set u'' = u + w. Both u'' - u and u'' - u' are
independent of v, so comparison through u'' proves the claim.
This argument also applies over F_2.

Apply the claim successively at u, u+v, ..., u+(l-1)v. The
resulting differences are equal, and their sum is zero. Hence
    l x(u+v,lambda) = l x(u,lambda).
Transposing the argument shows that the l-multiple is also
unchanged when the covector is varied with the vector fixed and
its value still equal to one. For two different basis vectors
e_i, e_j, take lambda = e_i^* + e_j^*. Change the covector at e_i,
change the vector from e_i to e_j, and then change the covector at
e_j. It follows that the l-multiples of all three diagonal units
agree.

The overlaps among our three matrix algebras now give
    l z_A = l z_{B'} = l z_{C'} = l z_{A_0} = l z_{A_1}.
Call their common value q. Since A = A_0 + A_1, additivity gives
q = 2q, and therefore q = 0. Finally, I = (A+B') + C', with A+B'
an idempotent in the first matrix algebra. Two applications of
additivity yield l z_I = 0. This proves the lemma.

--------------------------------------------------------------------
2.2 The ascending torus theorem
--------------------------------------------------------------------

For a group U and an injective endomorphism f: U -> U, write
    T(U,f) = < U, t | t^{-1} u t = f(u) for all u in U >.
This is an HNN extension. The notation includes all relations
already holding in U. The stable letter t conjugates U into
itself according to f.

THEOREM 2.2 (Ascending torus).
Let f: U -> U be an injective endomorphism. Assume the following.

(i) There are a finitely presented group P and homomorphisms
    a: U -> P, b: P -> U with f = b a.

(ii) For each l in {2,3} there are homomorphisms h_E: U -> U,
     indexed by E in P_l, such that h_I = f. Whenever E, P',
     E+P' are in P_l and E P' = P' E = 0, the subgroups h_E(U)
     and h_{P'}(U) commute elementwise, and
         h_{E+P'}(u) = h_E(u) h_{P'}(u)   for all u in U.

Then T(U,f) has type F_infinity.

# ^C interrupted by user!