Tag Archives: Borel equivalence relations

Commensurability of finitely generated groups

Let’s begin with a definition.

Definition: Two groups G,H are commensurable, which we’ll write G\approx H, if there exist subgroups G_0 \leq G, H_0 \leq H such that [G \colon G_0],[H \colon H_0]<\infty and G_0 \cong H_0.

This relation pops up in geometric group theory (among other places, I’m sure); for example the index in De La Harpe’s book lists about a dozen entries for “commensurable groups”.  Groups which are commensurable are easily seen to be quasi-isometric, and classifying groups up to quasi-isometry is a main focus in geometric group theory.

Commensurability of finitely generated groups is a countable Borel equivalence relation.  At some point, one begins to take the Borelness of these sorts of things for granted, so that part isn’t so surprising.  But the fact that the relation is countable is, I think.  It’s easy to see that a finitely generated group only has countably many finite-index subgroups; any finite-index subgroup is also finitely generated, and a finitely generated group only has countably many finitely generated subgroups.  But for this equivalence relation to be countable, one also needs to know that a given finitely generated group can only be a finite-index subgroup of countably many finitely generated subgroups.  This is not immediately obvious (at least, not to me).  As far as I can tell, the easiest way to see this is by appealing to the following theorem, due to Kaloujnine and Krasner:

Theorem (Kaloujnine-Krasner): Every extension of a group N by a group H is embeddable in the unrestricted wreath product N \mathbin{Wr} H.

So say that N is a finite-index normal subgroup of a group G.  Then G is the extension of N by some finite group H, and so G embeds into N \mathbin{Wr} H = N \mathbin{wr} H, since H is finite.  Since N \mathbin{wr} H is countable, it contains only countably many finitely generated subgroups, so there are only countably many possibilities for G given H.  There are also only countably many possibilities for H, so there are only countably many groups which N for which can be a finite-index normal subgroup.  What if N is not a normal subgroup?  Then it contains a finite-index normal subgroup, so everything still works out.

Recall the terminology from the last post.  We’re going to look at the proof of the following result.

Theorem (Thomas): Commensurability of finitely generated groups is a universal countable Borel equivalence relation.

Note that it’s easy to see that commensurability is weakly universal, since it contains isomorphism of finitely generated groups as a subequivalence relation, and isomorphism is universal.  So this proof makes exactly the leap from weakly universal to universal that we’d like to make with the theorems I discussed last time.

The proof proceeds by creating a reduction from isomorphism to commensurability.  In fact, the reduction is easy to write down.  Let S be your favorite infinite, finitely generated simple group, and let A_5 denote the alternating group on 5 elements.  Then the map

G \mapsto W_G = (A_5 \mathbin{wr} G) \mathbin{wr} S

is our reduction.  Clearly isomorphic groups will be sent to commensurable (in fact, isomorphic) groups.  The trick, of course, is to verify that this sends nonisomorphic groups to non-commensurable groups.

— Showing W_A \approx W_B implies that particular subgroups are isomorphic —

Suppose that W_A \approx W_B.  We want to show that A \cong B.  It is enough to show that (A_5 \mathbin{wr} A) \cong (A_5 \mathbin{wr} B), by a result of P.M. Neumann which states that A \mathbin{wr} B \cong A' \mathbin{wr} B' iff A\cong A' and B\cong B'.  The idea of the proof is to show that given a finite index subgroup of W_A , one must be able to somehow recover (A_5 \mathbin{wr} A).

A priori this could be quite difficult.  Suppose that you know two groups G,H are isomorphic, say via \pi.  Say K is a subgroup of G that is somehow special or contains information you’ve coded into the construction of G, and H also contains a special subgroup L.  There is no reason that \pi(K) should have anything to do with L, and so there is no reason to expect the information you’ve coded in K is the same as the information you’ve coded in L.

Let K_A denote the base group of W_A.  Then other results of P.M. Neumann show that W'_A=[S,K_A]S.  This characterization, combined with a few other P.M. Neumann results (and here is where we use that S is infinite and simple) tells us that if H_A is a finite-index subgroup of W_A, then W'_A=H'_A.  So indeed, we can try and use the commutator subgroup of W_A to recover A.  (All of these P.M. Neumann results are from the same paper, On the structure of standard wreath products of groups, which is a very thorough account of properties of wreath products.) This is great, because if H_A \cong H_B, then the isomorphism must send H'_A to H'_B. So if we’ve coded information into H'_A it must be the same as the information in H'_B. In this case, we’re hoping to be able to recover A from H'_A.

— Finding A in H'_A

So if W_A \approx W_B, we know that [S,K_A]S\cong [S,K_B]S.  We want to keep peeling away until we can see A and B.  It seems intuitively obvious that we can get rid of the S‘s, but how?  Let sf\in [S,K_A]S be such that f\in[S,K_A], and s\in S, and let \pi(sf)=s'f'\in[S,K_B]S with f'\in[S,K_B] and 1\neq s'\in S.  We’d like to show that s\neq 1 iff s'\neq 1, since this implies [S,K_A]\cong [S,K_B].

We again look for certain subgroups that we know any isomorphism must preserve.  It would be nice to prove something like the following: C_{W'_A}(sf) is cyclic iff s\neq 1.  Then since C_{W'_B}(s'f')\cong C_{W'_A}(sf), we’d be done.  Unfortunately, things aren’t quite so easy.  Define L_{sf} to be the normal closure of sf in W'_A, and R_{sf}=\langle (sf)^{L_{sf}} \rangle (i.e. R_{sf} is the normal closure of sf in L_{sf}).  Then one can show that C_{L_{sf}}(R_{sf})=1 iff s=1.  Since all of these groups are preserved under isomorphism, we now know [S,K_A] \cong [S,K_B].

I don’t really have a good idea of how one decides to look at these groups beyond trial and error.  The one thing I’ll note is that centralizers are relatively easy to understand in wreath products A \mathbin{wr} B, since conjugating elements of the base group K by elements of B just shifts them around, and understanding conjugation by elements of K is really only as difficult as understanding conjugation in A.  In particular, clearly C_{A \mathbin{wr} B}(K)=\{e\}, and so any subgroup containing K will have trivial centralizer with respect to the whole group.  So it makes sense to look at centralizers.

For X\subseteq S, let K^X_A=\{f\in K_A \mid \sigma(f)\subseteq X\}, where \sigma(f) denotes the support of f.  Now by a result of P.M. Neumann (again, I know), [S,K_A]=W'_A\cap K_A.  Obviously if |X|=1 we have K^X_A\cong A_5 \mathbin{wr} A, so if K^X_A \leq W'_A \cap K_A, we’d be well on our way to being done.  But in general this doesn’t happen.  We can do almost as well though.  Call A_5 \mathbin{wr} A=\hat{A}.  Using the P.M. Neumann result, it’s not too hard to check that if s\neq t\in S, (W'_A\cap K_A^{\{s,t\}})/(W'_A\cap K_A^{\{s\}}) \cong \hat{A}, and the analogous statements are true for W_B.  (Obviously K_A^{\{s,t\}}/K_A^{\{s\}} \cong \hat{A}, so this is just a matter of checking that enough of these groups are contained in W'_A for such an isomorphism to still exist.)  So it is enough to show that there are some a,b,c\in S with a\neq b such that \pi(W'_A \cap K_A^{\{c\}})=W'_B \cap K_B^{\{a\}} and \pi(W'_A \cap K_A^{\{1,c\}})=W'_B \cap K_B^{\{a,b\}}.

For f\in [S,K_A], let L_f=\langle f^{[S,K_A]} \rangle, and define R_f = C_{[S,K_A]}(L_f).  Note the similarity to the groups looked at couple of paragraphs ago.  A quick calculation shows that every element of L_f has support contained in \sigma(f), so L_f \leq W'_A \cap K_A^{\sigma(f)}.  We also note that since A_5 is simple and nonabelian, \hat{A} has a unique nontrivial minimal normal subgroup, its base group \hat{K}_A.  Minimality is easy to check.  For uniqueness, since C_{\hat{A}}(\hat{K}_A)=\{e\}, we find that any normal subgroup of \hat{A} must contain \hat{K}_A.  That second fact can be used to show that L_f contains all the elements of K_A with support contained in \sigma(f) and range contained in \hat{K}_A.  It’s easy to see what happens to these functions under conjugation, and so after further calculation we find that C_{[S,K_A]}(R_f)=W'_A \cap K_A^{\sigma(f)}.  We now know that |\sigma(f)|=1 iff C_{[S,K_A]}(R_f) is minimal among all groups of the form C_{[S,K_A]}(R_h) with h\in [S,K_A], and since similar results hold in [S,K_B], we get our desired result.

To sum up, I think the main insight is that some subgroups don’t really change under isomorphism. (There is a little work to get from asking about commensurability to asking about isomorphism, but this is taken care of by P.M. Neumann’s results.) Derived subgroups map to derived subgroups; centralizers map to centralizers. This means that we can try and use those subgroups to encode the information we’re interested in preserving. Perhaps it’s an obvious idea, but until I actually wrote out what was happening, I hadn’t thought of things in those terms.


Leave a comment

Filed under Uncategorized

Universal countable Borel equivalence relations with an eye toward finitely generated groups

In the previous post, I discussed a technique due to Neumann and Neumann for embedding any countable group into a 2-generated group, and mentioned in passing that they used the same ideas to create a finitely generated 3-solvable non-Hopfian group.  This construction turned out to be very useful to my own research, but to describe how requires a few definitions, which I’ll get to in a moment.  The aim of this post is not really to discuss my research, but instead to gear up to look at a related result, which I hope to understand better.  That will be the subject of the next post.  Perhaps it will help with my research again.

I’ve previously mentioned Borel equivalence relations in passing.  Let’s talk about them in a bit more detail.

Definition: If X is a Polish space (or more generally, a standard Borel space) and E is an equivalence relation on X, then we say E is Borel if E is Borel as a subset of X\times X.

Definition: We call an equivalence relation countable if all of its equivalence classes are countable.

My research focuses on countable Borel equivalence relations.  Many interesting equivalence relations are countable Borel; for example Turing equivalence, eventual equality of infinite binary sequences (known as E_0, which you may have seen in a hat problem), isomorphism of finitely generated groups, or orbit equivalence relations arising from Borel actions of countable groups.  (In fact, a theorem of Feldman and Moore says that every countable Borel equivalence relation can be realized as the orbit equivalence relation arising from a Borel action of a countable group!)  When discussing Borel equivalence relations, we are mainly interested in comparing them using the notion of a Borel reduction.

Definition: Suppose E and F are Borel equivalence relations on Polish spaces X,Y.  Then a Borel homomorphism from E to F is a Borel map f\colon X \rightarrow Y such that

\displaystyle x \mathbin{E} y \,\, \Rightarrow \,\, f(x) \mathbin{F} f(y)

Borel reduction from E to F is a map f\colon X \rightarrow Y such that

\displaystyle x \mathbin{E} y \,\, \Leftrightarrow \,\, f(x) \mathbin{F} f(y)

If E Borel reduces to F, we write E \leq_B F.

The idea behind a Borel reduction is that if E \leq_B F, then F is at least as complicated as F.  If one could classify the elements of Y up to F-equivalence, then using the Borel reduction you could also classify the elements of X up to E-equivalence.  (Note that this is not so different from the justification for using poly-time reductions in complexity theory to compare the difficulty of decision problems.)  The point of keeping things Borel that Borel objects are in some sense explicit.  Using the axiom of choice one can show there exist reductions between any two equivalence relations with the same number of equivalence classes, but the reductions are in general not Borel.  In fact, there are a whole host of results establishing non-reducibility of certain Borel equivalence relations.  A relatively simple example is that equality on 2^\mathbb{N} Borel reduces to E_0, but not vice versa, as can be seen using Baire category or measure arguments.

Definition: A countable Borel equivalence relation E is universal (or complete) if for any countable Borel equivalence relation F, F\leq_B E.

To extend the analogy with complexity theory, a universal countable Borel equivalence relation (if it exists) relates to countable Borel equivalence relations in the same way an NP-complete decision problem relates to NP decision problems; it’s as complicated as it possibly could be given its complexity.  Note that one could easily make a similar definition for any class of Borel equivalence relations.  Indeed, this is done.  Some classes have universal equivalence relations and some don’t.

Theorem (Dougherty-Jackson-Kechris): There is a universal countable Borel equivalence relation.

Once one has one example of universal countable equivalence relation E_\infty, then one can show another countable Borel equivalence relation E is universal simply by showing E_\infty \leq_B E, and indeed this is how most proofs of universality proceed.

Theorem (Thomas-Velickovic): Isomorphism of finitely generated groups is a universal countable Borel equivalence relation.

There are many other examples, but this is the one which interests us in this post.  Finitely generated groups can be quite complicated, and this result puts some rigor behind that intuition.  The proof rather heavily uses free products with amalgamation.  These are “large” from a group-theoretic standpoint (for example, they all contain free non-abelian subgroups), and so seen as complicated in and of themselves.  So it’s not surprising that isomorphism of these sorts of groups is complicated.  But what about finitely generated groups which are not as complicated?  Is the isomorphism relation still complex?  There has been some progress towards answering this, but we need one more definition.

Definition: A countable Borel equivalence relation E is weakly universal if for any countable Borel equivalence relation F there is a countable-to-1 Borel homomorphism from F to E.  Equivalently (this is not obvious), E is weakly universal if it contains a universal countable equivalence relation.

Clearly every universal countable Borel equivalence relations is weakly universal.  The idea behind looking at countable-to-1 Borel homomorphisms from an equivalence relation E to another equivalence relation F is that although these are not necessarily Borel reductions, they can’t fail too badly to be such, sending at most countably many E-inequivalent elements to F-equivalent elements .  Compare this with E_0 and equality on 2^\mathbb{N}; every Borel homomorphism from E_0 to equality must send a measure 1 set to the same point!

Whether or not every weakly universal equivalence relation is in fact universal is a notorious open problem.  A positive answer would make many proofs of universality trivial (or at least much simpler); creating Borel homomorphisms from a universal E to another Borel equivalence relation F is always the easy part, it’s making these maps reductions which is trickier.  A negative answer follows from Martin’s Conjecture, a stubbornly open conjecture in its own right, but which seems to provide excellent tools for analyzing weakly universal equivalence relations.  In any event, weakly universal equivalence relations are pretty high up in the \leq_B-hierarchy (which is not at all linear, so this should be understood as an imprecise-but-ultimately-mathematically-defensible statement).

So, back to isomorphism of finitely generated groups.  We have the following:

Theorem (Thomas-Williams): Isomorphism of Kazhdan groups is weakly universal.

Theorem (Williams): Isomorphism of finitely generated 3-solvable groups is weakly universal.

In both of these cases, we expect that the relations are in fact universal, but as I mentioned, making Borel reductions is a bit trickier than making Borel homomorphisms, which is all that is needed to prove weak universality.  My proof of the second theorem makes use of a modification of the Neumann and Neumann construction mentioned at the beginning of this post; in fact to modern eyes their construction already showed that E_0 Borel reduces to isomorphism of finitely generated 3-solvable groups, a non-trivial lower bound on the complexity.  It is known that E_0 is strictly below any weakly universal equivalence relation with respect to Borel complexity, so my result is a stronger lower bound than Neumann and Neumann’s.

It would be nice to make the leap from weak universality to universality.  In the next post, we’ll look at how a different group-theoretic equivalence relation was shown to be universal in the hopes of learning something we can use.

1 Comment

Filed under Uncategorized