# Three ways of embedding a countable group in a 2-generated group

Let me start off by saying that between travel and life intervening (stolen laptop, good times), I haven’t devoted much time to the paper I discussed in the last post.  What’s more, it seems I bit off a bit more than I could chew; I’m quite familiar with amenability from the point of view of Følner sequences and finitely additive probability measures, but the paper comes at it from a much more dynamical systems/functional analysis point of view.  One of the great strengths of the concept of amenability is that it can be defined in so many disparate ways, tying together several fields, but it can make for situations like I just had, where I couldn’t make it even halfway through the second section of the paper without learning a lot of new (albeit straightforward) mathematics.  Of course, I do want to learn some new things, that’s the whole point, but it got a bit overwhelming.  So I’m setting that aside that for now and getting back to something a bit closer to my research.

It’s a well-known fact that any countable group can be embedded into a 2-generated group.  Heck, I’ve mentioned it previously.  I’m going to go through three different proofs of this result, which each have some interesting consequences.

The original proof

The original proof of this result is due to Higman, Neumann, and Neumann, and uses what are now known as HNN extensions.  Here’s a quick refresher:

Definition: Suppose $G$ is a group with subgroups $A,B$ such that $A$ is isomorphic to $B$, as witnessed by $\phi\colon A\rightarrow B$.  Then the HNN extension of $G$ relative to this information is the group

$\langle G, t \mid t^{-1}at = \phi(a), a\in A \rangle$

The key result is that the above group behaves the way that you hope it would given the definition.  By this I mean the following: we can call a word in $G$ and $t$ reduced if it does not contain a subword of the form $t^{-1} a t$ or $t b t^{-1}$, where $a\in A$ and $b\in B$.  (Such subwords could obviously be replaced by a single element of $B$ or $A$, respectively.)  Then reduced words which aren’t literally the identity do not represent the identity in the above group.  Note that this immediately implies that $G$ embeds into the above group.

Given this, how do we get the theorem?  Suppose $C$ is a countable group with elements $c_1, c_2, c_3,\ldots$.  Let $F = C * \langle a, b\rangle$, i.e. the free product of $C$ and the free group on two generators.  Note that $\langle a,b \rangle$ contains the free group on countably many generators as a subgroup, e.g. the group $A$ generated by $\{ a, b^{-1}ab, b^{-2}ab^2,\ldots\}$ is free.  (For the topologically inclined, this is easy to see using covering spaces.  Otherwise just proving it combinatorially is easy enough.)  What’s more, the group $B\leq F$ generated by $\{b, c_1 a^{-1} b a, c_2 a^{-2} b a^2, \ldots\}$ is free.

So now we have isomorphic subgroups $A,B$ of $F$, so we can take the HNN extension

$\langle F, t \mid t^{-1} a t = b, t^{-1} b^{-i} a b t = c_i a^{-i} b a^i \rangle$

This embeds $F$ and so it embeds $C$.  It’s easy to see from the presentation that the group is generated by $t$ and $a$.  So there you have it.

The HNN extension continues to lead an illustrious life in group theory, getting used in all sorts of embedding results, as well as playing a prominent role in Bass-Serre theory.  But this is where it all began.

Using wreath products

Later, Neumann and Neumann did a proof completely avoiding HNN extensions.  To understand it, we need to be familiar with wreath products.  Somewhat annoyingly, there are several slight variations on the definition, so let’s be clear about what we’re looking at here.

Definition: Let $G$ and $H$ be groups, and let $math B$ denote the set of functions from $H$ to $G$.  Note that this is a group under pointwise multiplication, i.e. $\alpha\beta(x)=\alpha(x)\beta(x)$.  Note also that $H$ acts on $B$ by shift: $h\cdot f(x)=f(h^{-1}x)$.  This is an action by automorphisms, so we may define the semidirect product $B \rtimes H$.  It is this group which we call the (unrestricted) wreath product $G \mathbin{\mathrm{Wr}} H$.

A few remarks.  First, note that the if $G$ and $H$ are countably infinite, then the cardinality of $G \mathbin{\mathrm{Wr}} H$ is that of the continuum.  One can instead define the restricted wreath product by starting with the group of functions from $G$ to $H$ having finite support and obtain a countable group.  This is often denoted $G \mathbin{\mathrm{wr}} H$ or $G \wr H$.  Second, people have a tendency to define the semidirect product in a few different (but isomorphic) ways, so let’s go ahead and be explicit about the group operation here:

$(h, f)(h', f')=(hh', (h'\cdot f) f'),$

where $h,h'\in H$ and $f,f'\in B$.  Finally, I should mention one other construction commonly referred to as a wreath product.  Suppose that $Y$ is a set on which a group $H$ acts by permutations.  Then we can let $B$ be the group of functions from $Y$ to $G$, on which $H$ acts by shift, and again set up the semidirect product.  Most frequently this happens with $Y=\{1,2,\ldots,n\}$ and $H$ the symmetric group on $n$ elements.  If you’re lucky, the authors will write this like $G \mathbin{\mathrm{Wr}}_Y H$ or $G\wr_Y H$, but don’t count on it.

So where were we?  Right, suppose we have a countable group $C=\{c_1,c_2,\ldots\}$.  We wish to embed it into a 2-generated group.  It’s unclear at first how the wreath product could help, since it’s too big to be finitely generated.  We’ll get around this by embedding $C$ into a 2-generated subgroup of a wreath product.

Let $Z=\langle z \rangle$ be the infinite cyclic group, and define $P = C \mathbin{\mathrm{Wr}} Z$.  We’ll focus on the elements $(0, g_i)\in P$, where $g_i(z^t)=c_i^{-t}$.  So in some sense $g_i$ keeps track of the powers of the ith element of $C$.  Now look at $k_i = [(0,g_i), (z, id)]$:

$[(0,g_i), (z, id)]=(0,g_i^{-1})(-z,id)(0,g_i)(z, id)$

$=(0,g_i^{-1})(-z,id)(z,z\cdot g_i)$

$=(0,g_i^{-1})(0, z\cdot g_i)$

$=(0, g_i^{-1} (z\cdot g_i))$

Since $z$ shifts the values of $g_i$ over one spot, we see that $g_i^{-1} (z\cdot g_i)$ is just the function which is constantly $c_i$.  The group of constant functions is clearly isomorphic to $C$, but $P$ is not finitely generated, so we’re not done yet.

Now let $D=\langle d \rangle$ be another infinite cyclic group.  We single out elements $d_i = d^{2^i-1}\in D$, for every $i\in\mathbb{N}$.  A good way to think of these elements are as those numbers written in binary using only 1s.  The reason for choosing these is that the sum of any two such elements never makes a third (or the identity in $D$).  Certainly there are other choices for such a set, but this is of no importance.

Let $Q = P \mathbin{\mathrm{Wr}} D$.  Let $q\in Q$ be the function from $D$ to $P$ defined by $q(0)=z$, $q(d_i^{-1})=g_i$, and $q(y)=id_P$ for other values of $y$.  So $q$ has information about every $g_i$.  Now look at $h_i = [d_i \cdot q, q]$.

$[d_i \cdot q, q](0)=[d_i \cdot q(0), q(0)]$

$= [q(d_i^{-1}), q(0)]$

$= [g_i, z] = k_i$

Also, $[d_i \cdot q, q](d_j^{-1})=[d_i \cdot q(d_j^{-1}), q(d_j^{-1})]$

$= [q((d_i d_j)^{-1}), q(d_j^{-1})] = id_P,$

since $d_i d_j \neq d_k$ for any $k\in\mathbb{N}$.  Similarly we find that $h_i(y)=id_P$ for any other value of $y$.

So it’s now clear that the group generated by the $h_i$ is isomorphic to that generated by the $k_i$, which is isomorphic to $C$.  What’s more, the $h_i$ are all just products of $q$ and $d$.  So we have embedded $C$ into the subgroup of $Q$ generated by $q$ and $d$.

In fact, we can say more.  Suppose that $C$ is a solvable group of class $k$.  Then $C^\mathbb{Z}$ is also solvable of class $k$, and so $P$ is solvable of class at most $k+1$.  Similarly, $Q$ is solvable of class at most $k+2$, and thus so are its subgroups.  So we’ve shown that any countable solvable group of class $k$ embeds into a 2-generated solvable group of class $k+2$.

One can show this is tight; there is a countable abelian group (i.e. a countable solvable group of class 1) which does not embed into any finitely generated metabelian group (i.e. a solvable group of class 2).  You can say even more if you’re willing to talk about varieties of groups, but let’s not get into that.  This construction can also be used to create a finitely generated solvable group which is non-Hopfian.  Pretty neat!

Subgroups of symmetric groups

The last proof is due to Galvin, but in his own words, it’s just the Neumann-Neumann proof, done from a slightly different point of view.  The coding involved is more transparent, but you lose the nice structural properties (e.g. there’s no guarantee that solvable groups will be embedded in solvable groups).

So suppose we have a countable group $G$.  We may assume that $G$ is a subgroup of $Sym(\mathbb{N})$.  We’ll show there is a 2-generator subgroup of $Sym(\mathbb{Z}\times\mathbb{Z}\times\mathbb{N})$ into which $G$ embeds.  The picture I have in my head of $\mathbb{Z}\times\mathbb{Z}\times\mathbb{N}$ is of an infinite grid (that’s the $\mathbb{Z}\times\mathbb{Z}$ part) with infinite columns on top of each point in the grid (that’s the $\mathbb{N}$ part).  So I’ll talk about $x$-columns in the grid when I mean a set of the form $(x,-,-)$, and I’ll just call something a column when it’s a set of the form $(m,n,-)$.  The basic idea is to define a permutation which encodes information about the ith element of $G$ in what it does to the $(i, n, -)$ column for each $n\geq 0$.  In reality we have to do a little extra, but it’s not too complex.

We will enumerate $G$ as $\{g_1,g_3,g_5,\ldots\}$.  Let $a$ be the permutation sending $(m,n,k)$ to $(m+1,n,k)$.  Let $b$ be the permutation defined by

$b((0,n,k)) = (0,n+1,k)$

$b((2m+1,n,k)) = (2m+1,n,g_{2m+1}(k))$ for $m>0$ and $n\geq 0$

$b(m,n,k) =(m,n,k)$ otherwise

So by looking at $b$ acting on, say, the $(2m+1, 0,-)$ column, we can tell exactly how $g_{2m+1}$ acts on $\mathbb{N}$.  We want, given some $j$, to be able to somehow isolate just the $g_{2j+1}$ information.

First, we conjugate $b$ by a power of $a$ to shift it.  For $i$ odd and positive, let $b_i = a^{-i} b a^i$.  If we conjugate $b_i^{-1}$ by $b$, what happens?  Well, $b_i^{-1}$ permutes around (some) even-indexed $x$-columns but leaves the odd-indexed $x$-columns alone, while $b$ does the opposite, except at the $(0, n, -)$ columns.  Thus $b b_i^{-1} b^{-1}$ behaves like $b_i^{-1}$ everywhere except possibly the $(0,n,-)$ columns.  We see that $b_i^{-1}$ acts like $g_i^{-1}$ on each $(0,n,-)$ column with $n\geq 0$, but $b$ sends $(0,n,p)$ to $(0,n+1,p)$, so $b b_i^{-1} b^{-1}$ acts like $g_i^{-1}$ on each $(0,n,-)$ column with $n>0$.  Thus, when we look at $c_i=(b b_i^{-1} b^{-1}) b_i$, there is cancellation everywhere but the $(0,0,-)$ column, i.e. $c_i(0,0,p) = g_i(p)$ for all $p\in\mathbb{N}$, and $c_i$ is the identity everywhere else.  So clearly the group generated by the $c_i$ is isomorphic to $G$.  Further, it’s a subgroup of the group generated by $a$ and $b$.

Epilogue

One thing one notices about all these proofs is that you must choose an enumeration for your countable group $G$, or at least its generators.  But different enumerations will, in general, give rise to different groups.  So one might wish for a construction which does not depend on the enumeration you choose, so it would be less set-theoretic and more purely group-theoretic.  Alas, it is not to be.

Theorem (Simon Thomas): Let $\mathcal G$ denote the space of countable groups, and $\mathcal G_{fg}$ denote the space of finitely generated groups.  There is no Borel map $\phi\colon \mathcal G \rightarrow \mathcal G_{fg}$ such that

• $G \hookrightarrow \phi(G)$, and
• $G\cong H$ implies that $\phi(G) \cong \phi(H)$.

Borel maps should be thought of as “explicit” maps.  In fact, in the context of group-theoretic constructions, nearly everything induces a continuous map on the above spaces.  So ruling out Borel maps is the same as ruling out group-theoretic constructions.  The choice of an enumeration is unavoidable!

However, if you restrict yourself, you can get by without an enumeration.  Using Galvin’s above construction to modify a proof of Harvey Friedman’s, Thomas was able to show the following:

Theorem: Let $\mathcal G_2$ denote the space of 2-generated groups.  Then there is a Borel map $\psi\colon\mathcal G_{fg} \rightarrow \mathcal G_2$ such that

• $G \hookrightarrow \psi(G)$, and
• $G\cong H$ implies that $\psi(G)\cong\psi(H)$.

The map doesn’t seem purely group-theoretic, as it uses ideas from computability theory, and Galvin’s coding is pretty much just combinatorics, but it does avoid the use of Choice.  Ultimately the difference between the two situations comes down to results from Borel equivalence relations, but that’s another post altogether.