I know that finite simple groups can be generated by two elements.(See this question on MO)

So as a specific example, Take Alternating group $A_{n}$, $n>4$.

We also know that $A_{n}$ is $(2,3)$ generated.

I want to write a program, which takes a positive integer($n>4$) as input and return two elements of $A_{n}$ one having order $2$ and other having order $3$, also these two elements generate the whole group.

But I am not able to write an algorithm.

Any hints.

  • 2
    $\begingroup$ $A_n$ is not $(2,3)$-generated for $n=6,7$ and $8$. If I wanted to do this I would just choose random elements of order $2$ and $3$ having minimal numbers of fixed points. You will find generators very quickly that way. $\endgroup$ – Derek Holt Nov 13 '16 at 11:27

There's some discussion related to your question.

As for algorithm, just take even involution with maximal support and try to find an even element of order 3 such that union of that partitions is just $(n)$; this pair will generate the whole group. That "greedy" algorithm will suffice if $n > 9$. Take that maximal involution $I = (12)(34)\dots(4k-1, 4k)$; take element $T$ of the form $(235)(679)..(4l+2, 4l+3, 4l+5), 4l+5 < 4k$ "connecting" all but maybe one 2-cycle. Now you have remaining fixed points (from 0 to 3) and 0 or 1 leftover 2-cycle. Number of holes in support of $T$ intersected with support of $I$ is at least $k+1$. Now arrange leftovers in pairs and connect it with support of $I$ adding 0 to 2 3-cycles to $T$ taking up no more than 3 holes. That "algorithm" (it admits closed form, obviously) is even 4-periodic in $n$. I'm not paying attention to primitivity, so this can be true only by coincidence.

Upd: there's whole article about explicit $(2,3)$ generators for $A_n$ and $S_n$


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.