# How do you know which relations will define a group?

Consider the dihedral group of degree $n$, denoted $D_n$. I know that $D_n$ has presentation $\langle r,f\vert r^n,f^2,rfrf\rangle$, and I see why, but there are a lot of expressions which reduce to the identity $r_0$ in $D_n$, so I'm wondering how someone constructing a presentation for $D_n$ would know that just those three relations suffice to unambiguously define the group $D_n$.

In general, if I have a group $G$ and want to make a presentation for it, how would I go about doing so? Particularly, how would I know which relations need to be listed so that the presentation indeed defines my group and not a "more free" group?

• If you are interested in algorithms to do this for finite groups, you could look at sciencedirect.com/science/article/pii/0012365X73901040 – Derek Holt Nov 3 '16 at 8:34
• As someone who, aside from algebra, also has a deep interest in computer science and graph theory (and the intersection of these 3 topics), that article looks really interesting. I'll definitely read that. Thanks for sharing! – MightyTyGuy Nov 6 '16 at 1:04

## 2 Answers

Let $F_n$ denote the free group on $n$ generators, say $F_n = \langle x_1, \ldots, x_n\rangle$.

Suppose $G$ is a group and you want to find a presentation for $G$. You find some generators $g_1, \ldots, g_n \in G$. Then the universal property of free groups tells you there is a surjective group homomorphism $\Phi: F_n \twoheadrightarrow G$ via $x_i \mapsto g_i$.

Then you find some relations $r_1, \ldots, r_k \in F_n$ that are satisfied by the $g_i$, i.e., $r_i \in \ker(\Phi)$. So you let $N$ be the normal closure of the subgroup generators by $r_1, \ldots, r_k$, and $\Phi$ can be factored through the surjection $$\hat\Phi: F_n/N \twoheadrightarrow G.$$ Here $F_n/N = \langle x_1, \ldots, x_n \mid r_1, \ldots, r_k\rangle$.

Your question becomes: How do we show that $\hat\Phi$ is one-to-one, or determine that it's actually not one-to-one?

The best way to show that it is one-to-one, as far as I know, is to use the relations to convert every word in $x_1, \ldots, x_n$ into a "canonical representative", one for each element of $G$. In your example, every element of the group $\langle r,f\vert r^n,f^2,rfrf\rangle$ can be written as $f^\epsilon r^i$, for some $\epsilon \in \{0, 1\}$, and $i \in \{0, 1, \ldots, n-1\}$. These are precisely in correspondence with the elements of $D_n$, so you have a presentation for $D_n$.

To show that $\hat\Phi$ is not one-to-one, you simply need to somehow derive a contradiction from the assumption that $\hat\Phi$ is an isomorphism. One way to do this is to find a bigger group $\hat G$ such that $\hat\Phi$ can be expressed as a composition $$F_n/N \twoheadrightarrow \hat G \twoheadrightarrow G.$$

A more subtle way to get a contradiction is to find a group $\hat G$ which has generators satisfying the same specified relations, such that $\hat G$ cannot be expressed as a quotient of $G$. This is a contradiction because you have $F_n/N \twoheadrightarrow \hat G$ but $G \not\twoheadrightarrow \hat G$.

For example, you might think that the Quaternion group can be presented by $\langle i, j \mid i^2 = j^2, i^4=1\rangle$. But note that $F_2/N \twoheadrightarrow \mathbb Z/4\mathbb Z \times \mathbb Z/2\mathbb Z$, via $i \mapsto (1, 0)$ and $j \mapsto (1, 1)$. Since $\mathbb Z/4\mathbb Z \times \mathbb Z/2\mathbb Z$ is not a quotient of the quaternion group (it is the same size as the quaternion group, but, e.g., it is abelian while the quaternion group is not), our presentation must not be complete.

• Using your example of the Quaternion group, once you realize that the presentation isn't complete, how would you determine what other relation to include? – MightyTyGuy Nov 6 '16 at 1:02
• There isn't an exact science about it. One way to go about it is to decide in advance what "canonical representative" words among the generators you wish to use; for example, for the Quaternion group, knowing that $Q = \{\pm 1, \pm i, \pm j, \pm k\}$ where $-1 = i^2$ and $k = ij$, one might choose $\{i^mj^n\}$ with $m \in \{0, 1, 2, 3\}$ and $n \in \{0, 1\}$. In this case the relations $i^2=j^2, i^4=1$ already provide a way of reducing the exponents $m$ and $n$, so all we need is a relation which tells us how to express $ji$ in that form. – Dustan Levenstein Nov 6 '16 at 2:10
• Looking up a presentation for the quaternions, I see that there's one which uses just $i$ and $j$ and another which uses more elements. Does every generating set for a group $G$ admit a presentation of $G$? – MightyTyGuy Nov 6 '16 at 2:41
• Absolutely. For any generating set, you just need to give enough relations to narrow down the set of elements of the group. – Dustan Levenstein Nov 6 '16 at 3:26

$\newcommand{\Span}[1]{\left\langle #1 \right\rangle}$In the particular case of the dihedral group, one knows that $D_{n}$ is a semidirect product of a cyclic group of order $n$ by a cyclic group of order $2$.

So the first relation $r^{n}$ attempts to define (see below) a group $\Span{r}$ of order $n$. The relation $f^{2}$ attempts to define a group $\Span{f}$ of order $2$. And the relation $r f r f$, which you can rewrite as $f^{-1} r f = r^{-1}$ tells you that the unique non-trivial element $f$ of the group $\Span{f}$ acts on $\Span{r}$ by inducing the inversion automorphism of $\Span{r}$. This is exactly what it takes to define the desired semidirect product.

The reason why I said "attempts" is that even if you start with the relation $r^{n}$, further relations may force $r$ to have a smaller order than $n$. For instance if you take relations $r^{4}, f^{2}, r^{-2} f r f$, then in the group you have $f^{-1} r f = r^{2}$, so that $$f^{-1} r^{2} f = (f^{-1} r f)^{2} = (r^{2})^{2} = 1,$$ so that $r^{2} = 1$, and thus $r = 1$