*[At the beginning of class, we discussed possible topics for the final project – for more information, click the ‘Course Info’ link at the top of the page. We also looked at some very nice drawings of Bass-Serre trees.]*

We started out today’s lesson by continuing our discussion of free products. Here are a couple neat facts about free products of groups:

1. Free products of groups are free if and only if both original groups are free. Proving this will be a problem on the upcoming problem set.

2. Let and be groups. Let . Then any subset of is a basis for a free subgroup of . A complete proof of this claim is fiddly and annoying [see: the latter half of this post].

Let’s switch gears for a moment.

**Definition:** A *metric* on a space *S* is a function such that

1. The distance from a point to itself is 0. That is, for any .

2. is symmetric; in other words, for every .

3. obeys the *triangle inequality*. This means that for any , .

A space equipped with a metric is called a *metric space*. Why does this help us study the geometry of groups? To answer this question, we need to define the following notion:

**Definition: **If is in a group generated by a set , the *word length* is the minimum length of a word on that represents .

Note that the length of an individual word may be different from the *word length* of the corresponding group element. For example, if is a group with generating set , then the word length .

This brings us to the following definition:

**Definition:** Let *G* be a group with a generating set . The *word metric* on with respect to is a function such that .

One thing that helps me visualize a word metric is to consider the Cayley graph of with respect to . Recall that if , then is expressed by the sequence of edges in the path from to in . This means that if is the word metric on with respect to , then is the length of the shortest path from to in . This lends a nice geometric interpretation to the concept.

Note that different generating sets for may yield completely different word metrics. For instance, if you use the entire group as a generating set, any two elements will have distance 1 under the word metric. This is not true in general.

Here are a couple examples of word metrics in action:

1. If and , then the word metric is given by .

2. If and are words, let denote the longest common prefix of and . If is a free group generated by , containing freely reduced words and , then is given by .

3. The word distance from any group element to the identity is the length of the shortest word expressing over the generating set.

Now that we know a bit about word metrics, we can switch back to our discussion of free products:

**Theorem:** If and are finite groups then, is virtually free.

[Recall from last class that a group is virtually *P* (for some property *P*) if it contains a finite-indexed subgroup that is *P*.]

*Proof.* Let be a homomorphism defined as follows: for any element in the generating set of , . For any element in the generating set of , .

[*Side note about notation*: the presentation we are using for is . An element in this generating set can be written in more set-theoretic notation as . Similarly, a generator can be written as . So, we can also think of as mapping to and to for any and .]

Observe that every generator of is mapped to by a generator of . This implies that im. By the First Isomorphism Theorem, ker. Because and are finite by assumption, ker. Therefore, ker is a finite-indexed subgroup of . Let’s try showing ker is free.

There are a few ways we can go about this:

1. We can find a basis for ker.

2. We can show ker acts freely on a tree.

3. We can use the ping-pong lemma.

We will be using the first technique. I’ll assert that a basis for ker is given by .

Claim: generates ker (left as an exercise to the reader).

Claim: Any reduced word on is non-trivial in . We’ll prove this inductively on the length of the word.

Inductive hypothesis: every reduced word such that satisfies the condition that .

[Here, denotes the *syllable length* of with respect to the groups and . Recall that the syllable length of is the number of ‘runs’ in , where a run is a maximal subword consisting entirely of letters from a single one of the original groups. For example, the syllable length of is 5. Any letter in can be expressed as for and . So, if , then .]

Base case: . Then , so for some and . Therefore, .

Inductive step: Let be a word such that . Therefore where . Consider the word . By the inductive hypothesis, .

Observe that each letter in can be expressed as for some and . Assume without loss of generality that the second to last syllable of is from and the last syllable is from . So, we have that:

where every .

Case 1: . In other words, there exist and such that . Therefore, we can express as:

. This word cannot be reduced further, as we have no relators between the elements of and . Thus, we have that this word has four more syllables than , so

.

Case 2: for and (recall that the inverse of an element of a set can be included in words over that set). We have that:

. There are two subcases:

i) If , then the word is freely reduced as is, and we have that .

ii) If , then cancels to , and we have that . I claim this word is reduced. Note that if and cancel, then . This implies , which implies is not reduced over .

So, we have that . This concludes the inductive argument.

Thus, any reduced word on is non-trivial in . Because also generates ker, is a basis for ker. This implies ker is a free subgroup of . Because we showed above that ker has finite index in , is virtually free.

This concludes the proof.

*Looking ahead*: On Friday, we’ll have a guest lecture on Baumslag-Solitar groups. On Monday, we’ll prove the following theorem:

**Theorem:** If a finite group acts on a tree, there is a universal point fixed by every element of the group.

I want to conclude this blog post by discussing a random fact I only know for bizarre coincidental reasons: word metrics are *really* hard to compute. While an individual group may permit an efficient algorithm to compute the distance between two of its elements, trying to compute a word metric on a *class* of groups is usually quite hard. This often remains true even when the class is quite restricted.

To see what I mean, consider the following problem: given a symmetric group , a generating set of transpositions, and two elements , what is the shortest word on needed to express ?

Even this problem, which deals only with order two generators over a very restricted class of *finite groups*, is known to be NP-hard [1], providing strong evidence there is no efficient algorithm to solve it. The problem only becomes harder if one makes it more general.

[1] Miltzow, L. Narins, Y. Okamoto, G. Rote, A. Thomas, and T. Uno, “Approximation and hardness for token swapping,” *Proceedings from the 24th Annual European Symposium on Algorithms*, 2016. arxiv preprint here: https://arxiv.org/abs/1602.05150

Great Job, Sam! I enjoyed reading your post. Thank you very much for discussing the NP-hard problem in the end. It rationalizes the intuition that symmetric groups are really really hard since they are literally the group of all groups. I am wondering that is there a linear algorithm to generate at least one word for expressing ?

Yes; given two elements and in a symmetric group , as well as a generating set for , one can ‘quickly’ find a word over representing that is at most 4 times longer than the shortest word possible. You can potentially do better if you place more restrictions on the structure of the generating set.

Note when I say an algorithm runs ‘quickly,’ I mean with respect to the size of the generating set , not with respect to , (as is potentially exponentially larger than ). Given a finite group with generating set , one can actually compute a word metric exactly in (I think) time by constructing a Cayley graph and using breadth-first search [1] to find the shortest path from one element to another.

[1] https://en.wikipedia.org/wiki/Breadth-first_search

This is a really fabulous post, Sam! I loved all of the hyperlinks you included. I’m a little bit confused at the beginning where you claim that “Free products of groups are free if both original groups are free. Note that the converse is not necessarily true.” However, on the homework this was given as as if and only if statement (See problem 4.1). This might be a simple mistake or misunderstanding, but if not, what do you mean by “converse”?

My bad! The converse is indeed true. That was an error on my part – I have now fixed it. Thanks for pointing it out!

I really like the way you talked about the computability of word metrics at the end! It’s interesting that even in the very theoretical world of geometric group theory, these questions of computational complexity emerge pretty naturally. I mean on some level we have to face facts and realize that we’re all combinatorial group theorists–and one of those facts is that combinatorial structures like graphs are often good playgrounds for algorithms. Just take the word problem for instance, which is very related.

Great post Sam! I really like how you prove the If A and B are finite groups then, A*B is virtually free theorem. The sections of ‘claim’ and steps in the proof help me understand it way better.

One thing that I find really interesting is the final theorem you state which talks about a universal fixed point. I feel like we take the identity for granted so much in group theory, but it really is remarkable that there is such a fixed point in this huge infinite tree.