All generating sets of $S_3$?

Question

I am trying to find all generating sets of $S_3$, is there a theorem which states how many sets I should have?

I know for example $(12)$ and $(123)$ is one such generating set however my question is 'how do I find all generating sets without having to compute them with brute force?' as of course, this will be lengthy.

Answer 1

I am not aware of any general theorem for this task. However, since $S_3$ is not cyclic, every set that generates it must have at least two distinct elements, both of which are distinct from the identity element $e$. That doesn't leave you with many choices. In fact, any subset $S$ of $S_3\setminus\{e\}$ with at least two distinct elements generates $S_3$, with one exception: that's when $S=\bigl\{(1\ \ 2\ \ 3),(1\ \ 3\ \ 2)\bigr\}$; this set generates the subgroup $\bigl\{e,(1\ \ 2\ \ 3),(1\ \ 3\ \ 2)\bigr\}$.

Answer 2

Since the order of $S_3$ is $6$, you can do the following: let $X$ be a subset. If $X$ contains an element of order $3$ and an element of order $2$, then it contains the subgroup they generate and so, by Lagrange's theorem, it generates $S_3$.

If $X$ does not contain an element of order $3$, then it contains only transpositions. If it contains only one transposition, then clearly $X$ generates a cyclic group, and $S_3$ is not cyclic. So it contains at least two. Now note that $(12)(23) = (123)$ (and similarly the product of any two distinct transpositions has order $3$), so again $X$ generates $S_3$.

If $X$ does not contain an element of order $2$, then it contains only element of order $3$. But there are two of those, and they are multiples of each other, so in this case $X$ can only generate $C_3$.

In the end, $X$ generates $S_3$ if and only if $X$ contains at least one transposition and a distinct nontrivial element.

In general, you can say that transpositions generate a symmetric group, or that a $n$-cycle and a transposition generate $S_n$, but the aim is more oriented towards finding a generating set, instead of all.

There are, however, probabilistic results that for particular classes of groups $G$ tell you what is the probability that any two, three, $n$ random elements generate $G$.

Answer 3

The group $S_3$ consist of the unit element $1$, three transpositions $(12), (13), (23)$ and two 3-cycles $(123),(132)$.

The transpositions are reflections of an equilateral triangle and the 3-cycles are rotations by 120 degrees each.

The subgroups of $S_3$ are the trivial subgroups, the subgroups of order 2 each of which given by one of the transpositions, and one subgroup of order 3, given by the 3-cycles.

Note that two reflections provide a rotation.

This information should be enough to construct all generating sets.

Answer 4

Let me try to collect a few things written in the comments. I will argue that the only non-generating set is the one comprising the two elements of order $3$. Observe, first, that if $S \subset S_3$ contains at least one element of order $2$ and at least one element of order $3$ then $|S_3| = 2 \cdot 3 \mid |\langle S \rangle|$, thus $\langle S \rangle = S_3$.

If a subset $S \subset S_3$ contains at least three elements then either it must contain at least one element of order $3$ and at least one element of order $2$, so $\langle S \rangle = S_3$ in that case, or the three transpositions. For the latter case see further down.

Therefore, the problem reduces to showing that the only non-generating set with two elements is the one comprising the two elements of order $3$. By the previous argument, an element of order $2$ and an element of order $3$ generate $S_3$. So the matter is merely to show that any two transpositions generate $S_3$. The product of any two transpositions in $S_3$, however, results in an element of order $3$ and we are done.

To answer the counting part of the question: any subset of $S_3 \setminus \{\mathrm{id}\}$ is a generating set except $\{(123), (132) \}$. In total, we thus have $2^5 -1$ generating sets. If instead you want minimal generating sets then you are looking at ${5 \choose 2}-1 = 9$.

P.S. The working assumption here is that only non-trivial elements can contribute as generators. If we include the trivial element then the count needs correction.