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 is a group with subgroups such that is isomorphic to , as witnessed by . Then the HNN extension of relative to this information is the group
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 and reduced if it does not contain a subword of the form or , where and . (Such subwords could obviously be replaced by a single element of or , 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 embeds into the above group.
Given this, how do we get the theorem? Suppose is a countable group with elements . Let , i.e. the free product of and the free group on two generators. Note that contains the free group on countably many generators as a subgroup, e.g. the group generated by 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 generated by is free.
So now we have isomorphic subgroups of , so we can take the HNN extension
This embeds and so it embeds . It’s easy to see from the presentation that the group is generated by and . 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 and be groups, and let $math B$ denote the set of functions from to . Note that this is a group under pointwise multiplication, i.e. . Note also that acts on by shift: . This is an action by automorphisms, so we may define the semidirect product . It is this group which we call the (unrestricted) wreath product .
A few remarks. First, note that the if and are countably infinite, then the cardinality of is that of the continuum. One can instead define the restricted wreath product by starting with the group of functions from to having finite support and obtain a countable group. This is often denoted or . 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:
where and . Finally, I should mention one other construction commonly referred to as a wreath product. Suppose that is a set on which a group acts by permutations. Then we can let be the group of functions from to , on which acts by shift, and again set up the semidirect product. Most frequently this happens with and the symmetric group on elements. If you’re lucky, the authors will write this like or , but don’t count on it.
So where were we? Right, suppose we have a countable group . 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 into a 2-generated subgroup of a wreath product.
Let be the infinite cyclic group, and define . We’ll focus on the elements , where . So in some sense keeps track of the powers of the ith element of . Now look at :
Since shifts the values of over one spot, we see that is just the function which is constantly . The group of constant functions is clearly isomorphic to , but is not finitely generated, so we’re not done yet.
Now let be another infinite cyclic group. We single out elements , for every . 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 ). Certainly there are other choices for such a set, but this is of no importance.
Let . Let be the function from to defined by , , and for other values of . So has information about every . Now look at .
since for any . Similarly we find that for any other value of .
So it’s now clear that the group generated by the is isomorphic to that generated by the , which is isomorphic to . What’s more, the are all just products of and . So we have embedded into the subgroup of generated by and .
In fact, we can say more. Suppose that is a solvable group of class . Then is also solvable of class , and so is solvable of class at most . Similarly, is solvable of class at most , and thus so are its subgroups. So we’ve shown that any countable solvable group of class embeds into a 2-generated solvable group of class .
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 . We may assume that is a subgroup of . We’ll show there is a 2-generator subgroup of into which embeds. The picture I have in my head of is of an infinite grid (that’s the part) with infinite columns on top of each point in the grid (that’s the part). So I’ll talk about -columns in the grid when I mean a set of the form , and I’ll just call something a column when it’s a set of the form . The basic idea is to define a permutation which encodes information about the ith element of in what it does to the column for each . In reality we have to do a little extra, but it’s not too complex.
We will enumerate as . Let be the permutation sending to . Let be the permutation defined by
So by looking at acting on, say, the column, we can tell exactly how acts on . We want, given some , to be able to somehow isolate just the information.
First, we conjugate by a power of to shift it. For odd and positive, let . If we conjugate by , what happens? Well, permutes around (some) even-indexed -columns but leaves the odd-indexed -columns alone, while does the opposite, except at the columns. Thus behaves like everywhere except possibly the columns. We see that acts like on each column with , but sends to , so acts like on each column with . Thus, when we look at , there is cancellation everywhere but the column, i.e. for all , and is the identity everywhere else. So clearly the group generated by the is isomorphic to . Further, it’s a subgroup of the group generated by and .
One thing one notices about all these proofs is that you must choose an enumeration for your countable group , 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 denote the space of countable groups, and denote the space of finitely generated groups. There is no Borel map such that
- , and
- implies that .
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 denote the space of 2-generated groups. Then there is a Borel map such that
- , and
- implies that .
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.