# Minimal maximal subgroup of the symmetric group

The question is pretty much in the title: What is the maximal subgroup of $S_d$ of maximal index (so minimal size)? A slight variant (I am not sure if it leads to a different answer) is: what if we restrict to transitive subgroups? (Of course, in both cases, there might be massive ties, but at least the index is well-defined).

Clarification: I want both asymptotic results, and, if possible, a pointer to a table for small $d.$

• Do you want the asymptotic behaviour or exact values for small $d$? Commented Nov 18, 2015 at 17:14
• Can a maximal subgroup be smaller in size than $PSL(2,p) \subset S_{p+1}$? Commented Nov 18, 2015 at 17:18
• @AndreasThom: Yes, $\text{AGL}(1,p)\subset S_p$ is a maximal subgroup for most primes $p$. Commented Nov 18, 2015 at 17:35
• @AndreasThom you read my mind! I want both, will edit! Commented Nov 18, 2015 at 18:50
• @DerekHolt Actually, for my nepharious purposes I need the table only up to degree $11,$ inclusively, which you can probably recall from memory :) Commented Nov 18, 2015 at 19:10

Maximal intransitive groups will be $S_a\times S_b$ and have comparatively small index. I think once $d>6$ (otherwise there is a small number effect) the maximal subgroup of maximal index will always be transitive: If $d$ is prime, $AGL(1,d)$ is transitive, maximal, of larger index; if $d=a\cdot b$, then $S_a\wr S_b$ is transitive, maximal of larger index. (To show this one only needs to estimate $x!\cdot (n-x)!$ versus $a!^b\cdot b!$.)

The question on what the largest index is will depend on properties of $d$, as it often will be an almost simple group, and even the sporadic groups can come in. For example if $d$ is prime it will typically be $AGL(1,p)$. If $d-1$ is prime, I think $PGL(2,p-1)$ will be maximal of largest index.

On the other hand for some degrees (e.g. 33,34) no relevant simple groups, or in fact primitive groups of large index, exist and an imprimitive wreath product becomes the best option.

So as a generic answer I think $a!^b\cdot b!$ with $n=ab$, $a$ the smallest prime divisor, is the best estimate one can hope for.

The relevant paper is:

Liebeck, Martin W.(4-LNDIC); Praeger, Cheryl E.(5-WA); Saxl, Jan(4-CAMBC) A classification of the maximal subgroups of the finite alternating and symmetric groups. J. Algebra 111 (1987), no. 2, 365–383.

A GAP program to find the indices for small degrees is:

for i in [2..100] do
g:=SymmetricGroup(i);
m:=ShallowCopy(MaximalSubgroupClassReps(g));
SortBy(m,Size);
Print(i," ");
PrintFactorsInt(Index(g,m[1]));
Print("\n");
od;

• Thanks! The takeaway is "maximal" does not mean "large"... Commented Nov 19, 2015 at 14:08
• @IgorRivin Yes. The reason is that $S_n$ has, in the Young subgroups, "surprisingly" large subgroups. (Respectively, it has permutation representations of surprisingly small degree for its order.) Commented Nov 19, 2015 at 16:04

A table of the largest indices of maximal subgroups of ${\rm S}_d$ for small $d$ can be computed with GAP:

    d | largest index of a maximal subgroup of S_d
------+----------------------------------------------------------------
2 : 2
3 : 3
4 : 2^2
5 : 2*5
6 : 3*5
7 : 2^3*3*5
8 : 2^3*3*5
9 : 2^3*3*5*7
10 : 2^3*3^2*5*7
11 : 2^7*3^4*5*7
12 : 2^7*3^4*5*7
13 : 2^8*3^4*5^2*7*11
14 : 2^8*3^4*5^2*7*11
15 : 2^3*5^2*7^2*11*13
16 : 3*5^3*7^2*11*13
17 : 2^11*3^6*5^3*7^2*11*13
18 : 2^11*3^6*5^3*7^2*11*13
19 : 2^15*3^6*5^3*7^2*11*13*17
20 : 2^15*3^6*5^3*7^2*11*13*17
21 : 2^14*3^8*5^4*7^2*11*13*17*19
22 : 2^11*3^7*5^3*7^2*11*13*17*19
23 : 2^18*3^9*5^4*7^3*11*13*17*19
24 : 2^18*3^9*5^4*7^3*11*13*17*19
25 : 2^17*3^9*5^3*7^3*11^2*13*17*19*23
26 : 2^18*3^9*5^4*7^3*11^2*13*17*19*23
27 : 2^18*3^7*5^6*7^3*11^2*13*17*19*23
28 : 2^22*3^9*5^6*7^3*11^2*13*17*19*23
29 : 2^23*3^13*5^6*7^3*11^2*13^2*17*19*23
30 : 2^23*3^13*5^6*7^3*11^2*13^2*17*19*23
31 : 2^25*3^13*5^6*7^4*11^2*13^2*17*19*23*29
32 : 2^25*3^13*5^6*7^4*11^2*13^2*17*19*23*29
33 : 2^12*5^5*7^3*11^2*13^2*17*19*23*29*31
34 : 3^9*5^4*7^2*11^2*13*17*19*23*29*31
35 : 2^7*3^6*7^4*11^3*13^2*17^2*19*23*29*31
36 : 2^27*3^13*5^7*7^4*11^3*13^2*17^2*19*23*29*31
37 : 2^32*3^15*5^8*7^5*11^3*13^2*17^2*19*23*29*31
38 : 2^32*3^15*5^8*7^5*11^3*13^2*17^2*19*23*29*31
39 : 2^12*5^6*7^4*11^2*13^2*17^2*19^2*23*29*31*37
40 : 2^31*3^14*5^8*7^5*11^3*13^3*17^2*19^2*23*29*31*37
41 : 2^35*3^18*5^8*7^5*11^3*13^3*17^2*19^2*23*29*31*37
42 : 2^35*3^18*5^8*7^5*11^3*13^3*17^2*19^2*23*29*31*37
43 : 2^38*3^18*5^9*7^5*11^3*13^3*17^2*19^2*23*29*31*37*41
44 : 2^38*3^18*5^9*7^5*11^3*13^3*17^2*19^2*23*29*31*37*41
45 : 2^34*3^17*5^9*7^6*11^4*13^3*17^2*19^2*23*29*31*37*41*43
46 : 3^12*5^6*7^3*11^2*13^2*17*19*23*29*31*37*41*43
47 : 2^41*3^21*5^10*7^6*11^4*13^3*17^2*19^2*23*29*31*37*41*43
48 : 2^41*3^21*5^10*7^6*11^4*13^3*17^2*19^2*23*29*31*37*41*43
49 : 2^41*3^20*5^10*7^5*11^4*13^3*17^2*19^2*23^2*29*31*37*41*43*47
50 : 2^41*3^21*5^10*7^6*11^4*13^3*17^2*19^2*23^2*29*31*37*41*43*47
51 : 2^15*5^9*7^6*11^3*13^2*17^2*19^2*23^2*29*31*37*41*43*47
52 : 3^5*5^10*7^7*11^3*13^3*17^3*19^2*23^2*29*31*37*41*43*47
53 : 2^47*3^23*5^12*7^8*11^4*13^3*17^3*19^2*23^2*29*31*37*41*43*47
54 : 2^47*3^23*5^12*7^8*11^4*13^3*17^3*19^2*23^2*29*31*37*41*43*47
------+----------------------------------------------------------------


The GAP function used to compute these values is

LargestIndexOfMaximalSubgroupOfSn := function ( n )

local  Sn, maxes, indices;

Sn := SymmetricGroup(n);
maxes := MaximalSubgroupClassReps(Sn);
indices := List(maxes,G->Factorial(n)/Size(G));
return Maximum(indices);
end;


and the body of the table has been produced with

gap> for n in [2..54] do
>      Print("       ",String(n,2)," : ");
>      PrintFactorsInt(LargestIndexOfMaximalSubgroupOfSn(n));
>      Print("\n");
>    od;


This loop takes about $4$ seconds on my laptop; for $n > 54$ there appears to be a sharp increase in runtime.

• Cool! Could you share the GAP program with us philistines? Commented Nov 18, 2015 at 20:07
• @IgorRivin: Of course! -- Done. Commented Nov 18, 2015 at 22:55