5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $S_3$ has $6$ elements so $64$ possible subsets. Why do you think that brute forcing this will take a noticable amount of time? $\endgroup$ – freakish Oct 7 '19 at 12:09
  • 1
    $\begingroup$ 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. $\endgroup$ – the_fox Oct 7 '19 at 12:09
4
$\begingroup$

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

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

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.