# The order of a group presentation

Find the order of the group $G$ which has the presentation $\langle a,b \mid a^{16}=b^6=1,bab^{-1}=a^3\rangle$

I found that $a^8b=ba^8$ hence $\langle a^8,b\rangle$ is an abelian sungroup of $G$. But I couldn't go further.

• Just looking at the orders of elements $a$ and $b$, what is an upper bound that comes to mind of the order of $G$? – Conan Wong Aug 26 '13 at 22:11
• @Serkan - thanks. You're right. $a^{16} = 1$ is slightly different from $a^{16} = b^6 = 1$. I'll let you explain to Danial then. – Conan Wong Aug 26 '13 at 22:31
• By considering all the hints you have been given, you might be able to prove an upper bound of 48 on the order of the group, and in fact that is the order. The group is a semidirect product of a cyclic group of order 8 by a cyclic group of order 6. I think you probably need to know a bit about semidirect products in order to prove that the order really is 48. – Derek Holt Aug 27 '13 at 10:07
• @user1729: But how do you verify that $a$ has order 8? – Derek Holt Aug 27 '13 at 13:44
• @DerekHolt Oh, sorry, I hadn't quite understood your comment (I thought that it had already been proven that $a$ has oder eight). – user1729 Aug 27 '13 at 17:51

There is no general approach that will work for all presentations but, for examples such as this one, and many others, a useful ad hoc strategy that can work has two main steps.

First, notice that you can find a normal form for the elements of the group, and count them to get an upper bound on the order. Second, get a lower bound on the order by finding a homomorphism from the group defined by the presentation onto a "concrete" group of known order. (For example, a group of permutations or of matrices.) The trick is to get these upper and lower bounds to agree.

For your example, notice that, since $a$ and $b$ generate the group $G$, each element of $G$ can be written as a word of the form $a^{\alpha_{1}}b^{\beta_{1}}a^{\alpha_{2}}b^{\beta_{2}}\cdots a^{\alpha_{k}}b^{\beta_{k}}$, for some $k$ and integers $\alpha_{i}$ and $\beta_{j}$. From the power relations $a^{16} = b^{6} = 1$, it follows that we can take $0\leq\alpha_{i}\leq 15$ and $0\leq\beta_{j}\leq 5$. From the commutation relation $bab^{-1} = a^3$ (or, equivalently, $ba = a^{3}b$), it follows (induction) that we can put every such word into the form $a^{\alpha}b^{\beta}$ where, again, $0\leq\alpha\leq 15$ and $0\leq\beta\leq 5$. However, these are not all distinct. Again, from the relation $bab^{-1} = a^{3}$ we get (by induction), $b^{k}ab^{-k} = a^{3^{k}}$. Putting this together with $b^{6} = 1$, and taking $k = 6$, we find that $a = b^{6}ab^{-6} = a^{3^{6}} = a^{729}$, so $1 = a^{728} = a^{16\cdot 25 + 8} = a^{8}$. That is, the order of $a$ divides $8$, so we can actually impose the restriction $0\leq\alpha\leq 7$. This gives us the upper bound $48 = 8\cdot 6$ for the order of $G$. This really is still just an upper bound (so far as we have proved), because we have not yet ruled out the possibility that the $48$ words $a^{\alpha}b^{\beta}$, with $0\leq\alpha\leq 7$ and $0\leq\beta\leq 5$ are still not all distinct. Doing this is the job of the second step.

To implement the second step, we need to find a "concrete" group $P$ of known order, and a homomorphism from $G$ onto $P$. One such example is the permutation group $$P = \langle (1,2,3,4,5,6,7,8), (2,4)(3,7)(6,8)(9,10,11) \rangle .$$ It can be shown that $P$ is a group of order $48$. Since the generators $\alpha = (1,2,3,4,5,6,7,8)$ and $\beta = (2,4)(3,7)(6,8)(9,10,11)$ of $P$ satisfy $\alpha^{16} = \beta^{6} = 1$ and $\beta\alpha\beta^{-1} = \alpha^{3}$, it follows that the assignment $a\mapsto\alpha, b\mapsto\beta$ extends to a homomorphism from $G$ to $P$, which is surjective because $\alpha$ and $\beta$ generate $P$.

Remark. Had I not gotten the answer from Maple beforehand, I might have wasted a lot of time trying to prove that the group had order $96$, which is the bound we get before noticing that $a$ had order dividing $8$. Even having done so, I might also have wasted time trying to further improve the upper bound to $24$ or even $12$.

Remark. How did we pull the permutation group $P$ from a hat? In general, this can be quite difficult, but in this case, it's not too bad once we know what we're looking for. We knew we wanted a group with generators $\alpha$ and $\beta$ such that $\alpha$ had order $8$ and $\beta$ had order $6$. The most obvious permutation of order $8$ is an $8$-cycle, so we write that down: $$\alpha = (1,2,3,4,5,6,7,8).$$ Since $3$ is prime to $8$, we know that $\alpha^{3}$ is also an $8$-cycle, so we write down $\alpha^{3}$: $$\alpha^{3} = (1,4,7,2,5,8,3,6).$$ Now we needed a permutation $\beta$ conjugating $\alpha$ to $\alpha^{3}$. But, having displayed $\alpha$ and $\alpha^{3}$ above, we can just read this off: $$\beta = (2,4)(3,7)(6,8).$$ The problem is that this $\beta$ has order $2$, not $6$. So we just tack on a disjoint $3$-cycle to get $$\beta = (2,4)(3,7)(6,8)(9,10,11).$$

If we hadn't noticed the smaller upper bound of $48$ before, we might have tried constructing a group of order $96$ along these lines by writing down a $16$-cycle, but we'd then get a hint we were on the wrong track since the $\beta$ we find has $4$-cycles.

Remark. A more systematic approach is to use the Todd-Coxeter algorithm, which is what most computer algebra systems will use to answer a question like this. It will fail if the group is not finite, but (given sufficient time and memory) will complete if the group is indeed finite. For problems that are not too large, this can be done by hand. See the book "Topics in the theory of group presentations", by D.L. Johnson (Cambridge Univ. Press, 1980) for a good description.

• I would just like to remark I find it slightly easier to notice that $3^4=81\equiv 1\pmod{16}$, and thus $b^4$ centralizes $a$. Since $b$ has order (dividing) $6$, this implies $b^2$ centralizes $a$ as well. Thus $a=b^{-2}ab^2=a^9$, so $a^8=1$. I only mention this because for groups with presentations of this type, finding the smallest power $\tau$ such that $3^\tau\equiv 1\pmod{16}$ - with the numbers $3$ and $16$ suitably replaced - is an algorithic "first step" in finding the order of the group. – user641 Aug 27 '13 at 21:17
• I did the Todd-Coxeter algorithm but it gets long and so I gave up. – mrs Aug 28 '13 at 1:19