HNN Extensions

Motivation and Definition

When we studied free products, we discussed the free product with amalgmation very briefly. To recall, given two groups $G = \langle X|R\rangle$ and $H= \langle Y|S\rangle$ , with subgroups $A \subseteq G$ and $B \subseteq H$ and an isomorphism $\phi: A\rightarrow B$ ; the free product of $G$ and $H$ , amalgamating the subgroups $A$ and $B$ by $\phi$ is the group

$\langle X,Y|R,S, a= \phi(a), a\in A \rangle$ .

Essentially, we are adding in a set of relators where every element of $A$ is equivalent to its image in $B$ . A Higman-Neumann-Neumann Extension (HNN Extension) of a group is similar, but both $A$ and $B$ are subgroups of the same group $G$ and we introduce a new, stable, generator to relate elements of $A$ to elements of $B$ . Without further ado, let us see the definition of an HNN Extension!

Definition. Let $G$ be a group with subgroups $A$ and $B$ such that there exists an isomorphism $\phi$ from $A$ to $B$ . Then the HNN Extension of $G$ with respect to $A,B,$ and $\phi$ is the group

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

Under this definition, we retain all of the generators and relators from $G$ and add in a single stable generator, $t$ . We then add in a set of relators whereby we conjugate elements of $A$ by $t$ to get their images under $\phi$ . While the definition officially requires relations for all elements of $A$ , in practice we only need to define relators for the generators of $A$ . Let $a= g_1g_2g_3\dots g_n \in A$ . Then,
$t^{-1}at=t^{-1}g_1g_2g_3\dots g_nt= t^{-1}g_1tt^{-1}g_2tt^{-1}g_3tt^{-1}\dots tt^{-1}g_nt=\phi(g_1)\phi(g_2)\phi(g_3)\dots\phi(g_n)=\phi(g_1g_2g_3\dots g_n)=\phi(a).$
Since $\phi$ is an isomorphism, we can get the relators we need for the other elements of $A$ using only the relators involving the generators.

Let us now see some examples! Let $G = F_2=\langle a,b|\rangle$ with $A = \langle a\rangle$ and $B= \langle b \rangle$ with $\phi: a\rightarrow b$ . Then, $G^\ast = \langle a,b,t|t^{-1}at=b\rangle.$ We will see a normal form for this group later, but for right now, we can think of words in this group as alternating between freely reduced elements of $F_2$ and either $t$ or $t^{-1}$ , where we can reduce the word by replacing $t^{-1}a^nt$ with $b^n$ and $tb^mt^{-1}$ with $a^m$ .

Additionally, the Baumslag-Solitar groups are all HNN extensions of $\mathbb{Z}$ with $BS(m,n) = \langle a,t|ta^mt^{-1}=a^n \rangle$ . While we do define it here as $ta^mt^{-1}$ instead of $t^{-1}a^mt$ , we can easily take $t^{-1}$ for $t$ and the presentations will be equivalent. For once they are an example and not a counter-example!

Our definition and example are of an HNN Extension with a single stable letter. We can also define a more general HNN extension for a family of subgroups $A_i$ and a family of subgroups $B_i$ with associated isomorphisms $\phi_i$ for each $A,B$ pair. We would then define $G^\ast = \langle G, t_1,\dots ,t_i | t^{-1}_ia_it_i=\phi_i(a_i), a_i\in A_i\rangle$ . However, for notational and simplification reasons we will focus the rest of this blogpost on the single stable letter case.

Britton’s Lemma

Our next goal is to define a normal form for $G^*$ . We will define something close to a normal form first before diving into an actual normal form. Let $g$ be any element of $G$ and let $\epsilon = \pm 1$ . Every element of $G^*$ can be written as a product $g_0t^{\epsilon_1}g_1t^{\epsilon_2}g_2\dots t^{\epsilon_n}g_n.$ We will allow $g_i$ to be equal to the identity in $G$ , so we can have higher powers of $t$ if we want to but we will write them as $t1t1t\dots t$ or $t^{-1}1t^{-1}1\dots t^{-1}$ . We then define a word to be reduced if and only if there is no subsequence of the form $t^{-1}g_it$ for $g_i \in A$ or $tg_jt^{-1}$ for $g_j\in B$ . Essentially, we just reduce the word using the relators we got from the extension.

J.L. Britton proved the following lemma:

Lemma. If the word $g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n$ is reduced and $n \ge 1$ , then $g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n \ne 1$ in $G^*$ .

The proof of this lemma is beyond the scope of this blogpost, but can be found in “The Word Problem for Groups” by John L. Britton, published in 1958 as Lemma 4 (The Principal Lemma).

This lemma tells us that if we can reduce a word in $G^*$ , we can easily tell if it is equivalent to the identity, assuming that the word problem is solvable in $G$ , so we can tell whether or not the resulting element of $G$ is equal to the identity or not. However, there may be two words which are both reduced in $G<em>^</em>*$ and are not equivalent, but are equal in the group. Thus, simply reducing words as described above is not enough to define a normal form. For example, consider again $G=F_2$ and let $x\in G^*$ be $a^2bt1tab$ . This is a reduced word in $G^\ast$ . We can, however, replace the second $t$ with $a^{-1}tb$ to get $a^2bta^{-1}tbab$ . This word is also reduced. Instead to define a normal form, we will need to add some restrictions on what the elements of $g$ look like.

A Normal Form for HNN Extensions

As part of defining a normal form for $G^*$ we will choose a set of right coset representatives of both $A$ and $B$ and will allow $1$ to be the representative of both $A$ and $B$ . We also choose a normal form for $G$ We define a normal form for $G^*$ as follows:

Definition. A normal form is a word $g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n$ for $n\ge 0$ such that the following hold:

1. $g_0$ is an arbitrary element of $G$ in normal form,
2. if $\epsilon_i=-1$ , then $g_i$ is a representative of a coset of $A$ in $G$ ,
3. if $\epsilon_i=1$ , then $g_i$ is a representative of a coset of $B$ in $G$ , and
4. there is no consecutive sequence $t^\epsilon 1 t^{-\epsilon}.$

we know that for all $a\in A$ , $t^{-1}at=\phi(a)$ , and since $\phi$ is an isomorphism we can define $\phi^{-1}$ and get $tbt^{-1}=\phi^{-1}(b)$ . We can rearrange these equalities to get $t^{-1}a=\phi(a)t^{-1}$ and $tb=\phi^{-1}(b)t.$ We will use these relationships as we put words into their normal form. Let us consider a couple of examples.

Example 1.
$G= F_2$ , $G^* = \langle a,b,t|t^{-1}at=b\rangle.$ Let $x = a^2bt1tab$ as before. We will choose the coset representatives of $A$ to be the freely reduced elements of $G$ that start with a power of $b$ and the coset representatives of $B$ to be the freely reduced elements of $G$ that start with a power of $a$ . Then, both 1 and $ab$ are representative of their cosets of $B$ , so $x$ is in normal form. However, the other word for $x$ that we discussed before is not in normal form. Recall that we had the word $a^2bta^{-1}tbab$ . We know that $bab$ is not a coset representative of $B$ , so we need to get rid of the second to last $b$ . We do this by using the relationship $tb=at$ , which after free reduction gives us back the sequence for $x$ .

Example 2.
Let $G,G^*$ , and the coset representatives be as above. Let $x = ab^2t^{-1}abab^2tbatba^2t^{-1}ab.$ This word is reduced, but not in a normal form as defined above. We will work right to left to put it into a normal form. $g_4=ab$ , and since $\epsilon_4=-1$ , we need $g_4$ to be a representative of a coset of $A$ . This is not currently the case. We use the fact that $t^{-1}a=\phi(a)t^{-1}=bt^{-1}$ to give us $ab^2t^{-1}abab^2tbatba^2bt^{-1}b.$ Now $g_4=b$ , which is in line with our definition. Next we consider $g_3 = ba^2b$ and apply the same relationship to give us $ab^2t^{-1}abab^2tbaata^2bt^{-1}b=ab^2t^{-1}abab^2tba^2ta^2bt^{-1}b.$ Applying the same idea to $g_2$ gets us $ab^2t^{-1}abab^2ata^2ta^2bt^{-1}b$ . Finally, $g_1$ should be a coset representative for $A$ , which means we need to use the fact that $t^{-1}a=bt^{-1}$ to give us $ab^2bt^{-1}bab^2ata^2ta^2bt^{-1}b=ab^3t^{-1}bab^2ata^2ta^2bt^{-1}b$ , which is finally in normal form.

Normal Form Theorem for HNN Extensions

Having defined a normal form for HNN Extensions, we now prove that each of these normal forms represents a unique element in the group. This is summarized in the Normal Form Theorem for HNN Extensions:

Theorem. Let $G^*= \langle G,t|t^{-1}at=\phi(a),a\in A\rangle$ be an HNN extension. Then,

(I) The group  is embedded in  by the map . If  in  where , then  is not reduced.

(II) Every element  of  has a unique representation as  where  is a normal form.

For the proof, we begin by showing that I implies II and vice versa so that I and II are equivalent. We do this by using Britton’s lemma and induction. We then show that statement II is actually true by defining a homomorphism from $G^*$ to the set of permutations of the normal forms of $G^*$ .

We begin by showing that I implies II. Let $G$ be embedded in $G^\ast$ and assume that if $g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n = 1$ in $G<em>^</em>*$ and $n\ge 1$ , then $g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n$ is not reduced. We wish to show that each element of $G^*$ has a unique normal form. Suppose that we have two normal forms for $w$ — $g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n$ and $h_0t^{\delta_1}\dots t^{\delta_n}h_n$ . It is enough to show that these two words are equivalent as words and not just as elements in the group. Since the two words correspond to equivalent elements we know that \begin{center} $g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n = h_0t^{\delta_1}\dots t^{\delta_m}h_m$ . \end{center} If both $n$ and $m$ are zero, then we have $g_0=h_0$ , which are both elements of $G$ and since we write the first element of any word in $G^*$ in normal form, we know that $g_0$ and $h_0$ are the same word. Thus, suppose that $m > 0$ . By rearranging the statement above, we get

$1= g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_nh_m^{-1}t^{-\delta_m}\dots t^{-\delta_1}h_0^{-1}$ .

Since $m > 0$ , we know that the number of $t$ ‘s in the sequence is at least 1, and by statement I (our assumption), this word is not reduced. However, both of our original words were reduced so the only place where there can be cancellation is in the middle. From this we know that $\epsilon_n=\delta_m$ and $g_nh_m^{-1}$ must be an element of either $A$ or $B$ such that we can reduce. We have two cases to consider: $\epsilon_n=\delta_m=1$ and $\epsilon_n=\delta_m=-1$ . Let us consider the first case first. Since $\epsilon_n=\delta_m=1$ , we know that $g_n$ and $h_m$ are both coset representatives of $B$ and are thus not elements of $B$ . However, in order for the reduction to work, we must have that $g_nh_m^{-1}\in B$ . The only way this works is if $g_nh_m^{-1}=e$ . Hence, $g_n=h_m.$ A similar argument holds when $\epsilon_n=\delta_m=-1.$

Having now shown that $g_n=h_m$ and $\epsilon_n=\delta_m$ , we can multiply on the right to get

$g_0t^{\epsilon_1}\dots t^{\epsilon_{n-1}}g_{n-1} = h_0t^{\delta_1}\dots t^{\delta_{m-1}}h_{m-1}$ .

We can then follow the same process until we get to $m=0$ , in which case $n$ must also equal zero for both words to be in normal form. Thus, using an inductive proof we show that

$g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n = h_0t^{\delta_1}\dots t^{\delta_m}h_m$

not only as elements in the group but also as words, and thus, the normal form is, in fact, unique and statement II is satisfied.

Let us now assume statement II and show that statement I holds. It is clear that $G$ embeds in $G^*$ by $g\rightarrow g$ . We wish to show that if we have a word that represents the identity and we have at least one $t$ in the word, then the word is not reduced. This is true by Britton’s Lemma.

Having shown that the two statements are equivalent, let us show that the theorem is in fact true. We will prove statement II. Let $W$ be the set of all normal forms and $G^*$ and let $S(W)$ be the set of permutations of $W$ . We define a homomorphism $\Phi: G^ *\rightarrow S(W)$ . By showing that this is in fact a homomorphism, we are showing that each element of $G^*$ permutes the normal forms in exactly one way and each of the normal forms maps to exactly one other word, so they must represent a unique element.

The action of $\Phi$ is to multiply on the left and then convert to normal form from right to left. Since we are mapping to the set of permutations, we need to always show how $\Phi$ of some element acts on a generic normal form. In order to show that it is a homomorphism, we need to define $\Phi$ on the generators of $G^*$ (the generators of $G$ and $t$ ) and show that each of the relations under $\Phi$ still goes to 1. For any $g\in G$ , we define $\Phi(g)$ as follows. For $g_0t^{\epsilon_1}\dots t^{\ep_n}g_n\in W$ , $\Phi(g)(g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n) = gg_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n$ and then convert $gg_0$ to normal form. It is clear that $\Phi(gg^{-1})=\Phi(g)\Phi(g^{-1})=\Phi(g^{-1})\Phi(g)=\Phi(g^{-1}g)=\Phi(1)=1$ since we are simply multiplying on the left and can cancel out the $g$ and $g^{-1}$ before converting to normal form.

Let us now define $\Phi(t)$ . Essentially, we are still multiplying on the left and converting to normal form, but we need to carefully consider how we do it so that we end up with a normal form. If $\epsilon_1=-1$ and $g_0\in B$ , then once we multiply on the left we get something of the form $tbt^{-1}$ , which is equal to $\phi^{-1}(b)$ . This leaves us with

$\Phi(t)(g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n) = \phi^{-1}(g_0)g_1\dots t^{\epsilon_n}g_n$ .

Otherwise, we get

$\Phi(t)(g_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n) = tg_0t^{\epsilon_1}\dots t^{\epsilon_n}g_n$

which we can convert to normal form using the steps outlined in the examples to get

$\phi^{-1}(b)t\hat{g_0}t^{\epsilon_1}\dots t^{\epsilon_n}g_n$

where $g_0 = b\hat{g_0}$ and $\hat{g_0}$ is the coset representative of the coset of $B$ containing $g_0$ and $b\in B$ .

We must also check that $\Phi(t)$ actually permutes the normal forms of $G^*$ , which we do by showing that $\phi^{-1}(b)t\hat{g_0}t^{\epsilon_1}\dots t^{\epsilon_n}g_n$ is a normal form. We can see that this is true because we are starting with an element of $G$ , we know that $\hat{g_0}$ is a representative of a coset of $B$ and everything following was already a normal form. Finally, we need to show that $\Phi(tt^{-1})=\Phi(t^{-1}t)=\Phi(t)\Phi(t^{-1})=\Phi(t^{-1})\Phi(t)=1$ . We can verify this by considering all of the different cases (since there were two cases for $\Phi(t)$ ). I will not go into the details here, since this proof is already more than two pages long, but the cases are given in Lyndon and Schupp’s Combinatorial Group Theory if you are interested. Once all of the cases are considered and we have shown that the relators are still mapped to 1 under the homomorphism, we know that we have a homomorphism and then we get unique normal forms for each element.

Conclusions

HNN extensions are important because they generate groups with interesting properties (think Baumslag-Solitar groups) and also because they are an extension of amalgamated free products. Given the Normal Form Theorem and Britton’s Lemma, we see that $G^*$ will have solvable word problem is everything acts “nicely” together — $G$ has solvable word problem, $A$ and $B$ have solvable word problem, and $\phi$ and $\phi^{-1}$ are easily defined. HNN extensions are cool and if you want more information, look at Combinatorial Group Theory by Lyndon and Schupp!

References

Baumslag–Solitar group. (2021). In Wikipedia. \url{https://en.wikipedia.org/w/index.php?title=Baumslag%E2%80%93Solitar_group&oldid=1026392287}

Britton, J. L. (1958). The Word Problem for Groups. Proceedings of the London Mathematical Society, s3-8(4), 493–506. \url{https://doi.org/10.1112/plms/s3-8.4.493}

Britton, J. L. (1963). The Word Problem. Annals of Mathematics, 77(1), 16–32. \url{https://doi.org/10.2307/1970200}

Lyman, R. (2019, April 18). Answer to “Understanding HNN extensions: Intuition, examples, exercises.” Mathematics Stack Exchange. \url{https://math.stackexchange.com/a/3192668}

Polak, J. (2018, October 8). Britton’s lemma and a non-Hopfian fp group – Aleph Zero Categorical. \url{https://blog.jpolak.org/?p=2072}

Roger C. Lyndon and Paul E. Schupp. (2001). Higman-Neumann-Neumann Extensions and Free Products with Amalgmation. In Combinatorial Group Theory (pp. 178–186). Springer.

user1729. (2021, March 28). Answer to “Baumslag-Solitar Group.” Mathematics Stack Exchange. \url{https://math.stackexchange.com/a/4080463}

Motivation and Definition

Britton’s Lemma

A Normal Form for HNN Extensions

Normal Form Theorem for HNN Extensions

Conclusions

References

Leave a Reply Cancel reply

Recent Posts

Recent Comments