Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$ ?

share|improve this question
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  B. S. Apr 2 '12 at 12:01
add comment

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.

share|improve this answer
    
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. –  B. S. Mar 30 '12 at 8:03
2  
@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. –  joriki Mar 30 '12 at 8:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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