# Which finite simple groups can be characterized by their action on a small set?

It is well known that a finite 4-times transitive permutation group is Matthieu, symmetric, or alternating. Another way of stating this is that the set $$\Omega = \{(x_1, x_2, x_3, x_4), 1\leq x_i\leq n, \mbox{x_1, \ldots, x_4 pairwise different}\}$$ has the property that $S_n$ acts transitively on $\Omega$, and every subgroup $U<S_n$, which also acts transitively on $\Omega$ is either $A_n$ or $S_n$, or one of a finite list of exceptions.

My question is: For which other simple groups does a similar statement hold true? What I would wish for is the following: There is some constant $c$, such that for every finite simple group $G$ there exists a set $\Omega$ with $|\Omega|<(\log G)^c$, on which $G$ acts transitively, such that every subgroup $U$ of $G$, which also acts transitively, is equal to $G$.

Unfortunately this statement is wrong, as can be seen e.g. for $G=\mathrm{Sl}_2(\mathbb{F}_p)$. If $q$ is the smallest prime divisor of $p^2-1$, then there cannot be a set $\Omega$ of size $<q$ with a non-trivial $G$-action, since the stabilizer of a point would be a subgroup of index equal to the size of the orbit of this point.

But what about $\mathrm{Sl}_n(\mathbb{F}_p)$ with $p$ fixed and $n\rightarrow\infty$? What about other sequences of groups?

• @GeoffRobinson, The work on factorizations that you mention is by Praeger, Liebeck and Saxl and is in Memoirs of AMS. It gives a classification of every maximal factorization of every almost simple group. A quick glance suggests that (for $n$ large enough), there are no factorizations of any classical group with $P_2$, the "second" parabolic group.... – Nick Gill Sep 2 '14 at 21:45
• .. I suspect this will be as small an action as one can hope for of the given type. To get the log bound in the question for a classical group of rank $n$, even for fixed $p$, one would need an action on a set of size polynomial in $n$ which is hopeless... – Nick Gill Sep 2 '14 at 21:53
• ... By the way I have an e-copy of the LPS-memoir - email me if you want it.... – Nick Gill Sep 2 '14 at 21:55

The answer is NO for $G=\mathrm{SL}_n(p)$ with $p$ fixed and $n\to\infty$. The bound you give - $(\log|G|)^c$ - requires an action of $G$ on a set of a size that is polynomial in $n$. But all the actions of $G$ have order exponential in $n$ - see, for instance Section 5 of Kleidman and Liebeck's book. I have an e-copy of this book if you want me to email it...

Added later: In fact the answer No generalizes: Let $G_r(p^a)$ be any finite group of Lie type of rank $r$ with level ($\approx$ field size) $p^a$. We can send any of the parameters $p,r$ or $a$ to infinity but in every case we find that $G$ does not have ANY actions small enough to satisfy the given bound (never mind also satisfying the requirement on the action of subgroups).

This is because $|G|\sim q^{f(r)}$ while any action of $G$ has degree bounded below by $q^{g(r)}$. Here $f$ is quadratic and $g$ is linear.

• Fixing $p,a$ with $r\to\infty$ we would need an action of size polynomial in $r$, but any action is exponential in $r$;
• Fixing $p,r$ with $a\to\infty$ we would need an action of size polynomial in $a$, but any action is exponential in $a$;
• Fixing $a,r$ with $p\to\infty$ we would need an action of size polynomial in $\log(p)$ but any action is polynomial in $p$.

Final remark: It's possible that one can conclude the same result (i.e. characterizing alternating groups amongst simple group by the existence of an action on a small set) without using the Classification of Finite Simple Groups. There are some famous results in this direction - due to Babai and Pyber separately - where they give upper bounds on the size of primitive groups in terms of the degree of the action. They are not quite strong enough to yield the required conclusion here, because their bounds are exponential in the degree. The reason for this is that they consider arbitrary primitive groups and, in this case, wreath products acting in the product action are of such a size. It might be possible to adapt their arguments with the added supposition that the group $G$ is simple and obtain a bound something like $|G|\preceq n^{\log(n)}$ (where $n$ is the degree) which, I think, would be enough. My feeling is that such a result would be pretty big news though...

• Thank you! I had some simple ideas concerning the product replacement graph of $S_n$, but it seems that they do not carry over to other simple groups at all. – Jan-Christoph Schlage-Puchta Sep 3 '14 at 9:46