How does one find all distinct elements of a group given by presentation? In this lecture, the lecturer gives a presentation
$$G = \langle a, b\mid a^3 = e, b^2 = e, aba = b\rangle,$$
then he says that the set of all elements of $G$ is
$$F=\{e, a, a^2, b, ba, ba^2\}.$$
How does one know all distinct elements of $G$ are exactly those in $F$, no more, no less? In general, given a presentation whose generators set is finite, is there a systematic way to find all distinct elements of the group?
 A: It is not possible to write an algorithm
where you type in any finitely presented group you want and any pair of distinct words
and it tells you whether or not the words give different elements.
This is the famous word problem for groups.
$\\$
But given your specific example $G = \langle \;a\,,\,b\;| \;a^3 = e,\; b^2 = e,\; aba = b\;\rangle$,
you can prove that $F$ covers all the distinct elements of $G$ by checking that every word of at most four characters gives an element of $F$.
There are other, perhaps cleverer, ways of proving that $G$ is indeed the dihedral group of order $6$.
A: While there's no algorithm in general,  when there's an anti-commutativity relation, as in this case, one easily gets an upper bound on the number of elements.   That's $aba=b\implies $ every element of the group can be written in the form $a^nb^m,\,0\le n\le2,\,0\le m\le1$.  Thus we have an upper bound of $6$ elements.
For a lower bound,  just note that $$a^nb^m=a^{n'}b^{m'}\implies a^{n'-n}=b^{m-m'}=e$$
(that's
$$\langle a\rangle \cap\langle b\rangle =\{e\})\implies n'\equiv n\pmod 3$$
and $m'\equiv m\pmod2$, giving the six distinct elements you listed.
A: It is true that there is no general algorithm which finds all distinct elements of a group (given by a presentation). However, there is still a systemic approach to this problem for finitely presented groups (and in fact to the more general problem of computing the set $ H \backslash G = \{ Hg | g \in G \} $ of right cosets with respect to any subgroup $ H $), which always works if the group is finite (resp. if $ H \backslash G $ is finite):
The Todd-Coxeter algorithm
Input: A finitely presented group $ G $ (given by a presentation $ \langle X | R \rangle $) and a subgroup $ H $ (given by a finite set of generators $ h_1, \dots, h_s $).
Output:

*

*If $ H \backslash G $ is finite, then the algorithm terminates and computes $ n := |H \backslash G| $ and the action of $ G $ on $ H \backslash G $. More precisely, $ H \backslash G $ is identified with the set $ \{ 1, \dots, n \} $ (where $ 1 $ represents the coset $ H $) and the algorithm computes the (right) action of $ G $ on this set. This information is usually given by a coset table with one row for each coset (i.e. $ n$ rows) and one column for each $ x \in X \cup X^{-1} $, where the entry at position $ (i, x) $ is the unique $ j \in \{ 1, \dots, n \} $ such that $ i^x = j $.

*If $ H \backslash G $ is not finite, then the algorithm does not terminate. (Thus it is not a proper algorithm in the strict sense, but only a semi-algorithm to the question "Is $ G \backslash H $ finite?".)

Applying this algorithm to the trivial subgroup $ H = \{ 1 \} $, we obtain, first of all, the number $ n = |G| $ (if it is finite). For each $ i \in \{ 1, \dots, n \} $, we can use the coset table to find an element $ g \in G $ (given as a product of generators) such that $ i = 1^g $. Since 1 is the trivial coset, we conclude that $ i $ is the coset $ \{ g \} $. Thus we find distinct elements $ g_1, \dots, g_n $ such that $ G = \{ g_1, \dots, g_n \} $. Similarly, we can use the coset table to produce a multiplication table of $ G $.
If you start with a list $ F $ of elements of $ G $, as in your example, and want to check whether $ F $ contains each element of $ G $ exactly once, then you apply the algorithm as above and then use the coset table to identify each element of $ F $ with a row in your coset table. This way, you can check whether all elements of $ G $ appear in $ F $ and whether there are duplicates.
Note that you do not have to know from the start that your presentation defines a finite group: Just start the algorithm and if it terminates, then you have (after a finite amount of time) a proof that the group is finite. Of course, if the group is not finite, then the algorithm will never prove anything, it will simply not terminate.
How does the algorithm work? Well, it is a bit involved, but it can be done by hand for small groups. I suggest to have a look at section III.6 of Alexander Hulpke's notes on computational group theory which contains some nicely illustrated examples. The idea is to start with an empty coset table with only one row (for the trivial coset $ 1 = H $) and then to try to fill this table by defining new cosets as the images of previously known cosets. Whenever you define a coset, you fill as many entries in the coset table as possible (e.g. if you define $ 2 := 1^a $, then you can fill the entry $ (1, a) $ with $2$ and the entry $ (2, a^{-1}) $ with $1$). The problem is that the cosets you define in this process are not necessarily distinct: In your example, if you start with the trivial coset $ 1 := \{ 1_G \} $ and define $ 2 := 1^a $, $ 3 := 2^b $, $ 4 := 3^a $ and $ 5 := 1^b $, then clearly $ 4 = 5 $ because of the relation $ aba = b $. The solution is to treat your cosets as "distinct until proven otherwise" and to keep track of so-called relator tables (one for each relation) which will, at some point, allow you to deduce that some of your cosets coincide or that some additional entries in your coset table can be filled. If the group $ H $ is not trivial (not relevant if you only want to enumerate the elements of $ G $), then you also have to keep track of so-called subgroup tables, one for each $ h $ in the finite generating set of $ H $, which keep track of the information that $ 1^h = 1 $. If the coset table is completely filled at some point in the procedure, then each row in the coset table represents a distinct coset and these are all cosets in $ H \backslash G $. If $ G \backslash H $ is infinite, this will never happen, so the number of rows in the coset table grows indefinitely and the algorithm never terminates.
