Constructing a group (a permutation group) which acts on a set of 4 letters transitively is easy. for example $G_{1}=\{id, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)\}$ < $S_{4}$. Can it be verified how many groups we have like $G_{1}$ ?


Although this is not an easy problem, finding all subgroups of $S_n$ first is not necessary, and is not the best way to proceed. The classification of all subgroups of $S_n$ has been completed for $n \le 18$, whereas the transitive subgroups are known for $n \le 32$. For $n=32$ there are 2801324 conjugacy classes of transitive subgroups, and their calculation is described in the paper: J. Cannon and D. Holt, The transitive groups of degree 32, Experimental Mathematics 17 (2008), 307-314.

The primitive subgroups of $S_n$ have been classified up to $n=4095$, so for a given $n$ the problem reduces to finding the imprimitive groups preserving a block system of $r$ blocks of size $b$, where $rb=n$. The possible induced actions on the block systems are just the transitive groups of degree $r$, which you can assume are already known. The idea is to first find all possible kernels of the actions on the block systems, which (in nearly all cases) are subdirect products of transitive groups of degree $b$, and then classify the groups with a given kernel and action group. This involves a large amount of computation, which becomes rapidly less feasible with increasing degree. Testing two subgroups for conjugacy in $S_n$ can be a particularly slow in difficult cases, so the principal aim is try to organise the computations so that you do as little conjugacy testing as possible.

  • $\begingroup$ The main intent of above question was that I wanted to find all groups, acting on four letters transitively, such that for example in that, {1,2} and {3,4} would be conjugates blocks. So, I wrote some transitive groups and then I thought how many groups should I write to find all ones here. Thanks Prof. Holt. $\endgroup$ – mrs Apr 2 '12 at 12:01

It's pretty straightforward to count them using a table of subgroups of $S_4$. We have three cyclic groups of order $4$, one normal Klein four-subgroup, three copies of $D_8$, the alternating group $A_4$, and $S_4$ itself, for a total of nine.

  • $\begingroup$ Thanks for the answer. But are not there any other ways counting these transitively acting groups on 4 letters, without writting and checking them for transivity, dear joriki? For example to do the same for $S_{10}$, it would be a bit difficult even using GAP. $\endgroup$ – mrs Mar 30 '12 at 8:03
  • 2
    $\begingroup$ @Babak: There doesn't seem to be an easy way of doing this. See this answer and this paper (Table 2 on p. 7) and this more recent paper for some numbers. (Note that they all count the number of transitive subgroups up to conjugacy.) The fact that in the first paper some numbers beginning at $S_{24}$ are marked as "preliminary, and not yet confirmed" seems to indicate that no efficient way to obtain this count was known. $\endgroup$ – joriki Mar 30 '12 at 8:30

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.