11
$\begingroup$

In a comment at the recent question What is the standard 2-generating set of the symmetric group good for?, it was remarked that the symmetric groups $S_n$ for $n\gt 2$, $n\neq 5,6,8$, can be generated by an element of order 2 and an element of order 3 (G. A. Miller, Bull. Amer. Math. Soc. 7 (1901), 424-426 doi:10.1090/S0002-9904-1901-00826-9). The remaining three nonabelian cases can of course be generated by a pair of elements, but these are cycles of length $5,6,8$ respectively. What is the best that can be done in these cases, and is there a conceptual reason why these are exceptional? (eg the presence of the nontrivial outer automorphism of $S_6$? Or some action on an exceptional combinatorial object?)


ADDED By 'conceptual' proof I mean something more like 'structural', or the analogue of what in combinatorics is a 'bijective proof'. There should be some actual construction for the generic case that clearly breaks down for the small cases, due to a lack of space. Compare for instance the deep understanding of what goes wrong with the sort of handle moves that happen in high-dimensional topology, when we go down to dimension 4, and then why the replacement there will not work in lower dimensions. Simply counting two sets and noticing they have the same number of elements isn't the sort of thing I want. Nor do I want a proof that just writes down a pair of generators and checks they work, but of course I do want to see said generators.

$\endgroup$
25
  • 2
    $\begingroup$ By the way for every $n$ equal to $-1$ modulo $3$, $S_n$ can't be generated by an element of order 3 and a transposition. Because an element of order 3 fixes 2 elements, so these should be moved by the last one, but then the resulting group is cyclic of order $6$. Also it's clear that a transposition and an element of order 3 can't generate a transitive subgroup for any $n>6$. The 1901 Miller reference says that $S_n$ (for $n$ not $5,6,8$) can be generated by a pair of elements of order 2 and 3, but don't say a transposition. $\endgroup$
    – YCor
    Oct 5 at 6:21
  • 2
    $\begingroup$ Sure, but a conceptual" reason for some fixed cases looks like asking a conceptual reason why $7\times 9=63$. Computation can help finding the right generating pair with some condition generalizing to larger $n$. $\endgroup$
    – YCor
    Oct 5 at 7:49
  • 3
    $\begingroup$ One quick way of seeing that $S_{5}$ is not $\{2,3\}$-generated is that, if it is, the generator of order $2$ has to be an odd permutation, so a transposition. The element of order $3$ is a $3$-cycle: if it fixes the points interchanged by the transposition, then it commutes with the transposition. Otherwise, there is a point fixed by both the transposition and the $3$-cycle. In either case, the two elements chosen generate a proper subgroup. $\endgroup$ Oct 5 at 8:58
  • 5
    $\begingroup$ I don't think there needs to be a conceptual reason why some general rule has a few small exceptions - that happens all the time. $\endgroup$
    – Derek Holt
    Oct 5 at 9:48
  • 3
    $\begingroup$ @spin Yes exactly, so for $n < 12$ there is no reason to expect anything other than random sporadic behaviour. Of course we can give proofs for all of the individual cases. IIRC, then for $A_n$, the examples examples that are not $\{2,3\}$-generated are $n=6,7,8$. $\endgroup$
    – Derek Holt
    Oct 5 at 14:39
12
$\begingroup$

It is also possible to use the (exceptional) outer automorphism of order $2$ of $S_{6}$ to give an "explanation" of why $S_{6}$ is not $\{2,3\}$-generated, along the lines I used in comments for $S_{5}$ above. Take a $6$-cycle $\sigma \in S_{6}.$ Then $\sigma^{2}$ is a product of two disjoint three cycles and $\sigma^{3}$ is a product of three disjoint $2$-cycles. These clearly commute. Now take an outer automorphism $\tau$ of $S_{6}$ which sends products of two disjoint three cycles to three cycles. Then $\tau$ must also send products of three disjoint transpositions to transpositions, since $\tau(\sigma^{2})$ and $\tau(\sigma^{3})$ must commute.

Now suppose that $S_{6}$ is $\{2,3\}$-generated say $S_{6} = \langle \alpha, \beta : \alpha^{2} = \beta^{3} = 1 \rangle.$ Then we may apply $\tau$ if necessary, and assume that $\beta$ is a $3$-cycle. Then $\alpha$ is an odd permutation, so is either a transposition, or a product of three disjoint transpositions.

In the former case, we have a contradiction since there is a point fixed by both $\alpha$ and $\beta$. In the latter case, none of the transpositions in $\alpha$ can fix all points moved by $\beta$, for otherwise that transposition would be central in $\langle \alpha, \beta \rangle.$ It follows that $\alpha$ sends each point moved by $\beta$ to a point fixed by $\beta$ and conversely. It follows that $\beta$ and $\beta^{\alpha}$ commute. Now $\alpha$ normalizes the Abelian subgroup $\langle \beta, \beta^{\alpha}\rangle $, so that $\langle \alpha, \beta \rangle = \langle \alpha \rangle \langle \beta^{\alpha} ,\beta \rangle$ has order dividing $18$, a contradiction.

I do not know if there is an argument using the fact that $S_{8}$ is isomorphic to ${\rm GL}(4,2)\langle \gamma \rangle$, where $\gamma$ is the transpose inverse automorphism, to "explain" that $S_{8}$ is not $\{2,3\}$-generated.

Later edit: It would have been better perhaps to use the outer automorphism of $S_{6}$ to reduce to the case that $\alpha$ is a transposition,(in which case, generation requires that $\beta$ is a product of two disjoint $3$-cycles), and then note the general fact that when $n >1$, $S_{2n}$ is never generated by a transposition $\alpha$ and an element $\beta$ which is a product of two disjoint $n$-cycles. For if it were, we may conjugate the pair and assume that $\alpha = (12).$ If either of the $n$-cycles in $\beta$ were disjoint from $\alpha$, then that $n$-cycle would be central in $\langle \alpha, \beta \rangle = S_{2n}$, a contradiction. Hence both $n$-cycles of $\beta$ contain a point moved by $\alpha$.

We may conjugate $\beta$ by a permutation fixing both $1$ and $2$ and assume that $\beta = (1357 \ldots 2n-1)(2468 \ldots 2n)$ without disturbing the generation property. Then $\langle \alpha, \alpha^{\beta}, \ldots, \alpha^{\beta^{n-1}}\rangle$ = $\langle (12),(34), \ldots , (2n-1 2n) \rangle$ is Abelian and normal in $\langle \alpha, \beta \rangle = S_{2n},$ a contradiction.

$\endgroup$
5
  • $\begingroup$ Excellent, this is the sort of thing I was hoping for. $\endgroup$ Oct 5 at 12:10
  • 1
    $\begingroup$ The argument I had in mind before: "It follows that $\alpha$ sends each point moved by $\beta$ to a point fixed by $\beta$ and conversely." => Hence $\langle \alpha, \beta \rangle$ is imprimitive, contradiction. $\endgroup$
    – spin
    Oct 5 at 12:54
  • 2
    $\begingroup$ Say $S_8 = \langle \alpha, \beta \rangle$ with $|\alpha| = 2$ and $|\beta| = 3$. I think with similar arguments as in this answer, $\alpha$ must be a product of three disjoint transpositions, and $\beta$ must be a product of two disjoint $3$-cycles (else $\langle \alpha, \beta \rangle$ fixes a point or is imprimitive). Then again with similar arguments wlog $\alpha = (12)(34)(56)$ and $\beta = (178)(235)$. These permutations generate $PGL(2,7)$. Not sure what is a quick way to see they do not generate $S_8$ to finish the proof that $S_8$ is not $\{2,3\}$-generated. $\endgroup$
    – spin
    Oct 5 at 13:41
  • 2
    $\begingroup$ I'm pretty skeptical that this is "more conceptual." It's just saying that the outer automorphism lets you divide the number of cases by 2. But I don't think doing 2 cases by hand is "more conceptual" than doing 4 cases by hand. $\endgroup$ Oct 6 at 3:13
  • 1
    $\begingroup$ Here's something slightly easier for $S_6$. Notice that if $G$ is $(2,3)$-generated, $x^2=y^3=1$, then $\langle y,y^x\rangle$ generates a subgroup of index at most $2$ in $G$. Now $A_6$ cannot be generated by two conjugate elements of order $3$: by the outer automorphism, we can assume they are both $3$-cycles, but them it's clear. $\endgroup$ Oct 11 at 20:28
8
$\begingroup$

Here is some data for generating pairs mentioned in a comment.

A group $G$ is $(r,s)$-generated if $G = \langle x, y \rangle$ with $|x| = r$ and $|y| = s$.

$S_5$ is $(2,4)$-generated, for example by $x = (12)$ and $y = (1345)$. And $S_5$ is not $(2,3)$-generated, although $A_5$ is.

$S_6$ is $(2,5)$-generated, for example by $x = (12)$ and $y = (13456)$. And $S_6$ is not $(2,s)$-generated for $s = 3,4$.

$S_8$ is $(2,4)$-generated, for example by $x = (12)(34)(56)$ and $y =(1564)(2837)$. And $S_8$ is not $(2,3)$-generated.

$\endgroup$
3
  • $\begingroup$ This pattern continues down: $S_4$ is generated by $(12)$ and $(134)$, and $S_3$ is generated by $(12)$ and $(13)$. We also have $S_8$ coming from $(12)$ and $(1345678)$, but something exceptional allows for the (2,4)-generation. And presumably something special happens for $S_7$, not sure what it is, to get (2,3)-generation. $\endgroup$ Oct 6 at 4:26
  • $\begingroup$ Yes, in general $S_n$ is $(2,n-1)$-generated by $(12)$ and $(134 \cdots n)$. Also $(2,n)$-generated by $(12)$ and $(123 \cdots n)$. $\endgroup$
    – spin
    Oct 6 at 4:45
  • $\begingroup$ Yes, the original question that inspired this one was about the second of these, which is why someone comment about (2,3)-generation. In some sense, $S_4$ and $S_3$ are exceptions to the exception, since the 'inefficient' generating cycle cannot be longer. $\endgroup$ Oct 6 at 5:14

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.