# All generating sets of $S_3$?

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.

• $S_3$ has $6$ elements so $64$ possible subsets. Why do you think that brute forcing this will take a noticable amount of time? – freakish Oct 7 '19 at 12:09
• Perhaps a better question you could ask is this: "How many minimal generating sets does $S_3$ have and how do I find them all?" This is because every generating set contains a minimal generating set and from any minimal generating set you can construct further generating sets by simply appending more elements. – the_fox Oct 7 '19 at 12:09

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\}$$.

• Comments are not for extended discussion; this conversation has been moved to chat. – quid Oct 9 '19 at 19:29

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$$.

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.

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.