Week Four Wednesday: Free Products and Word Metrics

[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 $A$ and $B$ be groups. Let $C = \{[a,b] | a \in A, b \in B \} - \{e\}$ . Then any subset of $C$ is a basis for a free subgroup of $A*B$ . 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 $d: S \times S \rightarrow \mathbb{R}_{\geq 0}$ such that
1. The distance from a point to itself is 0. That is, $d(x,x) = 0$ for any $x \in S$ .
2. $d$ is symmetric; in other words, $d(x,y) = d(y,x)$ for every $x,y \in S$ .
3. $d$ obeys the triangle inequality. This means that for any $x,y,z \in S$ , $d(x,y) + d(y,z) \geq d(x,z)$ .

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 $g$ is in a group $G$ generated by a set $S$ , the word length $|g|_S$ is the minimum length of a word on $S$ that represents $g$ .

Note that the length of an individual word may be different from the word length of the corresponding group element. For example, if $G$ is a group with generating set $S = \{a,b \}$ , then the word length $|a^5 b^{2} b^{-2} a| = 6$ .

This brings us to the following definition:

Definition: Let G be a group with a generating set $S$ . The word metric on $G$ with respect to $S$ is a function $d: G \rightarrow \mathbb{R}_{\geq 0}$ such that $d(g,h) = |g^{-1}h|_S$ .

One thing that helps me visualize a word metric is to consider the Cayley graph $\Gamma$ of $G$ with respect to $S$ . Recall that if $g,h \in G$ , then $g^{-1}h$ is expressed by the sequence of edges in the path from $g$ to $h$ in $\Gamma$ . This means that if $d$ is the word metric on $G$ with respect to $S$ , then $d(g,h)$ is the length of the shortest path from $g$ to $h$ in $\Gamma$ . This lends a nice geometric interpretation to the concept.

Note that different generating sets for $G$ 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 $G = \mathbb{Z}$ and $S = \{1\}$ , then the word metric $d(g,h)$ is given by $|h-g|$ .
2. If $w_1$ and $w_2$ are words, let $pref(w_1,w_2)$ denote the longest common prefix of $w_1$ and $w_2$ . If $G$ is a free group generated by $S$ , containing freely reduced words $w_1$ and $w_2$ , then $d(w_1,w_2)$ is given by $|w_1|_S + |w_2|_S - 2\cdot pref(w_1,w_2)$ .
3. The word distance from any group element $g$ to the identity is the length of the shortest word expressing $g$ 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 $A$ and $B$ are finite groups then, $A*B$ 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 $\phi : A*B \rightarrow A \times B$ be a homomorphism defined as follows: for any element $a$ in the generating set of $A$ , $\phi(a) = a$ . For any element $b$ in the generating set of $B$ , $\phi(b) =b$ .

[Side note about notation: the presentation we are using for $A \times B$ is $\langle A \cup B | ab = ba, a \in A, b \in B \rangle$ . An element $a$ in this generating set can be written in more set-theoretic notation as $(a, id_B) \in A \times B$ . Similarly, a generator $b$ can be written as $(id_A, b)$ . So, we can also think of $\phi$ as mapping $a$ to $(a,id_B)$ and $b$ to $(id_a,b)$ for any $a \in A$ and $b \in B$ .]

Observe that every generator of $A \times B$ is mapped to by a generator of $A * B$ . This implies that im $\phi = A \times B$ . By the First Isomorphism Theorem, $A * B /$ ker $\phi \cong A \times B$ . Because $A$ and $B$ are finite by assumption, $[A * B :$ ker $\phi] = |A \times B| < \infty$ . Therefore, ker $\phi$ is a finite-indexed subgroup of $A*B$ . Let’s try showing ker $\phi$ is free.

There are a few ways we can go about this:
1. We can find a basis for ker $\phi$ .
2. We can show ker $\phi$ 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 $\phi$ is given by $C = \{ [a,b] | a \in A, b \in B \} - \{ e \}$ .

Claim: $C$ generates ker $\phi$ (left as an exercise to the reader).

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

Inductive hypothesis: every reduced word $w$ such that $|w|_{C} = \ell$ satisfies the condition that $|w|_{*} \geq \ell + 3$ .

[Here, $|w|_{*}$ denotes the syllable length of $w$ with respect to the groups $A$ and $B$ . Recall that the syllable length of $w$ is the number of ‘runs’ in $w$ , 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 $a_1 a_2 a_3 b_1 a_4 b_2 a_5 a_6$ is 5. Any letter in $C$ can be expressed as $aba^{-1}b^{-1}$ for $a \in A$ and $b \in B$ . So, if $w = c = aba^{-1}b^{-1}$ , then $|w|_{*} = 4$ .]

Base case: $|w|_{C} = 1$ . Then $w \in C$ , so $w = aba^{-1}b^{-1}$ for some $a \in A$ and $b \in B$ . Therefore, $|w|_{*} \geq 4 = 1 + 3 = \ell + 3$ .

Inductive step: Let $w$ be a word such that $|w|_C = \ell + 1$ . Therefore $w = c_1 c_2 ... c_{\ell} c_{\ell + 1}$ where $c_i \in C$ . Consider the word $w' = c_1 c_2 ... c_{\ell}$ . By the inductive hypothesis, $|w'|_{*} \geq \ell + 3$ .

Observe that each letter $c_i$ in $w$ can be expressed as $a_i b_i a_i^{-1}b_i^{-1}$ for some $a_i \in A$ and $b_i \in B$ . Assume without loss of generality that the second to last syllable of $w'$ is from $A$ and the last syllable is from $B$ . So, we have that:

$w = x_1 x_2 ... x_k a_{\ell} b_{\ell} c_{\ell + 1}$ where every $x_i \in A \cup B$ .

Case 1: $c_{\ell + 1} = [a,b]$ . In other words, there exist $a \in A$ and $b \in B$ such that $c_{\ell +1} = aba^{-1}b^{-1}$ . Therefore, we can express $w$ as:

$w = x_1 x_2 ... x_k a_{\ell} b_{\ell} a_{\ell +1} b_{\ell +1} a_{\ell +1}^{-1}b_{\ell +1}^{-1}$ . This word cannot be reduced further, as we have no relators between the elements of $A$ and $B$ . Thus, we have that this word has four more syllables than $w'$ , so

$|w|_{*} = |w'|_{*} + 4 \geq \ell + 3 + 4 > (\ell+1) + 3$ .

Case 2: $c_{\ell + 1} = [a,b]^{-1}$ for $a \in A$ and $b \in B$ (recall that the inverse of an element of a set can be included in words over that set). We have that:

$w = x_1 x_2 ... x_k a_{\ell} b_{\ell} b_{\ell +1}^{-1}a_{\ell +1}^{-1}b_{\ell +1}a_{\ell +1}$ . There are two subcases:

i) If $b_{\ell} \neq b_{\ell + 1}$ , then the word is freely reduced as is, and we have that $|w|_{*} = |w'|_{*} + 3 \geq \ell + 3 + 4 > (\ell + 1) + 3$ .

ii) If $b_{\ell} = b_{\ell + 1}^{-1}$ , then $b_{\ell} b_{\ell +1}$ cancels to $e$ , and we have that $w = x_1 x_2 ... x_k a_{\ell} a_{\ell +1}b_{\ell +1}^{-1}a_{\ell +1}^{-1}$ . I claim this word is reduced. Note that if $a_{\ell}$ and $a_{\ell +1}^{-1}$ cancel, then $(a_{\ell} = a_{\ell+1}$ . This implies $c_{\ell} = a_{\ell}^{-1} b_{\ell}^{-1} a_{\ell} b_{\ell} = (b_{\ell}^{-1} a_{\ell}^{-1} b_{\ell} a_{\ell})^{-1} = c_{\ell}^{-1}$ , which implies $w$ is not reduced over $C$ .

So, we have that $|w|_{*} = |w'|_{*} -1 + 2 \geq \ell + 3 -1 + 2 = (\ell + 1) + 3$ . This concludes the inductive argument.

Thus, any reduced word on $C$ is non-trivial in $A * B$ . Because $C$ also generates ker $\phi$ , $C$ is a basis for ker $\phi$ . This implies ker $\phi$ is a free subgroup of $A*B$ . Because we showed above that ker $\phi$ has finite index in $A*B$ , $A*B$ 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 $S_n$ , a generating set $T$ of transpositions, and two elements $g, h \in S_n$ , what is the shortest word on $T$ needed to express $g^{-1}h$ ?

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

6 Responses to Week Four Wednesday: Free Products and Word Metrics

Shuhang Xue says:

October 9, 2022 at 9:08 pm

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 $g^{-1}h$ ?

- Sam Hiken says:
  
  October 10, 2022 at 11:03 pm
  
  Yes; given two elements $g$ and $h$ in a symmetric group $S_n$ , as well as a generating set $T$ for $S_n$ , one can ‘quickly’ find a word over $T$ representing $g^{-1}h$ 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 $T$ , not with respect to $|S_n|$ , (as $|S_n|$ is potentially exponentially larger than $|T|$ ). Given a finite group $G$ with generating set $T$ , one can actually compute a word metric exactly in (I think) $O(|G| \cdot |T|)$ 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
  
Michaela Polley says:

October 12, 2022 at 7:01 am

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”?

- Sam Hiken says:
  
  October 13, 2022 at 10:37 pm
  
  My bad! The converse is indeed true. That was an error on my part – I have now fixed it. Thanks for pointing it out!
  
Horace Fusco says:

October 12, 2022 at 11:54 pm

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.

Osip Surdutovich says:

October 13, 2022 at 11:24 pm

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.

6 Responses to Week Four Wednesday: Free Products and Word Metrics

Leave a Reply Cancel reply

Recent Posts

Recent Comments