# Upper bound for order of finite group given relations

Say I have a group with the following presentation: $$G = \langle a,b \mid a^2 = b^3 = (ab)^3 = e \rangle$$

During a conversation someone had mentioned that the order for $G$ must be less than or equal to $12$. I couldn't follow the conversation very well, but on trying to figure out where this bound came from I got confused. They seemed to make it sound like there was some certain property that allowed them to calculate this fairly rapidly. Is there some theorem that gives an upper bound to finite groups that are relatively nicely behaved? (Like those with two or maybe three generators).

I don't think there is any general theorem of this sort, unless we know something reasonably specific about the relations. For example, every finite simple group can be generated by two elements, albeit possibly with many relations. Also disturbing: the word problem for finitely presented groups is not solvable in general; that is, there is no algorithm that can determine whether two elements in an arbitrary finitely presented group are equal. And finally, an open problem: it is unknown whether a 2-generated group where all fifth powers are trivial must be finite. (See $B(2, 5)$.)

I would go the most basic way : enumerate the elements.

So from $a^2 = b^3 = e$, you know that the elements of the group are sequences of $a$ and $b$ where there is at most one consecutive $a$, and two consecutive $b$.

Let us list the elements by their number of factors.

• 0 factors : $e$
• 1 factor : $a$ and $b$
• 2 factors : $ab, ba$ and $b^2$, all distincts
• 3 factors : $aba, bab, ab^2, b^2a$, all distincts
• 4 factors : $abab, baba, ab^2a, b^2ab, bab^2$

But we have $baba = (ba)^{-1} = ab^2,\quad abab = (ab)^{-1} = b^2a$, and $ab^2a = (aba)^{-1} = bab$, so the only new element with 4 factors are $b^2ab$ and $bab^2$, whoch makes us 12 elements in total.

Now let's look at the elements with 5 factors : $ababa, abab^2, ab^2ab, babab, bab^2a, b^2aba, b^2ab^2$. Each one but the last contains a 4-factor that reduced to a 3-factor, so these are in fact 4-factors and we have already seen them. Now $b^2ab^2 = (bab)^{-1} = aba$ is a 3-factor.

Any factor of superior length would also be reducible, so we have enumerated all the elements, and there are at most 12 of them.

There are already several good answers, but I would like to mention one additional tool, because it is systematic: the Todd-Coxeter algorithm. Given a presentation of a group that includes a finite-order generator, if the group is finite, the Todd-Coxeter algorithm will terminate and provide the group order. (If there is a danger that the group is not finite, then you run the risk of the algorithm not terminating.)

I learned the algorithm from Chapter 6 of this book.

• What do you mnean by "that includes a finite-order generator"? If the group is finite then all of its elements have finite order. – Derek Holt Nov 7 '15 at 9:43
• @DerekHolt I think it's because the algorithm applies to any group, not just finite ones. I've used it before, it's a suuuuuper nice algorithm. I was going to use the Todd-Coxeter algorithm, but the problem is that in itself it only gives a lower bound. But it definitely does help in determining an exact value for the order of G. – Aram Papazian Nov 7 '15 at 12:15
• @DerekHolt - I just meant that the presentation includes a generator $x$ and a relation of the form $x^r=1$. I had in mind for the user to use the T-C algorithm to calculate the coset action on $\langle x\rangle$; since if the group is finite the algorithm will terminate giving the index $i$, the user will then know the group order divides $ir$. I knew the condition could be weakened but at the time I didn't have time to think about how. I guess the user could just use T-C to calculate the coset action on $\{1\}$, giving the order directly... – Ben Blum-Smith Nov 7 '15 at 18:29
• @AramPapazian - You're incorrect that the T-C algorithm gives only a lower bound. In general, when it terminates it actually gives you the (exact) index of the subgroup you apply it to. If you know the subgroup order, it gives you the exact group order. In your case I was imagining you'd apply it, say, to the subgroup $\langle a\rangle$. Because $a^2=1$, this subgroup has order at most 2, so if you knew its index this would actually give you an upper bound on the group order. – Ben Blum-Smith Nov 7 '15 at 20:07
• @BenBlum-Smith Sorry, what I meant was it gives a lower bound in the sense that it's now dependent on the smaller subgroup. So unless you know the order of the subgroup you now still have a lower bound. In the case of 2 generators that's not so bad as you mentioned you can just take one of your two generators since you already know their order and you're good to go. The reason I went against that was because it seemed the decision was made without calculating the T-C algorithm. Additionally, for large groups the method can become cumbersome to do by hand. – Aram Papazian Nov 8 '15 at 13:15

If you are able to give an upper bound for the order of a group, it's usually because you recognize $G$ as a quotient (homomorphic image) of a known finite group, say $\tilde{G}$. In this case, you might notice that the tetrahedral group $\tilde{G} = A_4 < S_4$ can be given by the presentation $$\langle x, y \mid x^2 = y^3 = (xy)^3 = 1 \rangle,$$ where $x = (1\,2)(3\,4)$ and $y = (1\,2\,3)$.

You check that the map $\varphi: A_4 \to G$, defined by \begin{align} x \mapsto a \\ y \mapsto b \end{align} is, in fact, a homomorphism. This amounts to checking that for each relation in the variables $x$ and $y$, the corresponding relation is satisfied in the image of $\varphi$ in the variables $a$ and $b$. (In this example, it's trivial because the map is so simple.)

Finally, you check that the map is onto. (Again, this is trivial in this case.)

Now, you can conclude that $\lvert G \rvert \le \lvert \tilde{G} \rvert < \infty$. You actually get a stronger conclusion: by Lagrange's theorem, $\lvert G \rvert$ is a divisor of $\lvert \tilde{G} \rvert$.

• This is a bit confused. This method shows that $A_4$ is a homomorphic image of $G$, which proves a lower bound rather than an upper bound on the order of $G$. – Derek Holt Nov 7 '15 at 9:42