15
$\begingroup$

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.$

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

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;
$\endgroup$
  • $\begingroup$ Thanks! The takeaway is "maximal" does not mean "large"... $\endgroup$ – Igor Rivin Nov 19 '15 at 14:08
  • $\begingroup$ @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.) $\endgroup$ – ahulpke Nov 19 '15 at 16:04
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Cool! Could you share the GAP program with us philistines? $\endgroup$ – Igor Rivin Nov 18 '15 at 20:07
  • $\begingroup$ @IgorRivin: Of course! -- Done. $\endgroup$ – Stefan Kohl Nov 18 '15 at 22:55

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.