Let $G$ be a primitive group acting on a set $\Omega$ with $n$ elements. By Cameron/Liebeck (essentially a consequence of the Classification + O'Nan-Scott), there are two possibilities:

(a) $G$ has a subgroup of index $\leq n$ isomorphic to an alternating group,

(b) $G$ is of size $\leq n^{O(\log n)}$.

In case (a), $G$ cannot have a composition series $$\{e\} = H_0 \triangleleft H_1 \triangleleft \dotsc \triangleleft H_{\ell} = G$$ of length $\ell$ greater than $O(\log n)$.

In case (b), the trivial bound on the length $\ell$ of a composition series is $\ell = O((\log n)^2)$. In fact, the trivial bound on the length of a chain of subgroups $\{e\} = H_0 \lneq H_1 \lneq \dotsc \lneq H_{\ell'} = G$ is also $O((\log n)^2)$.


  1. (The question I asked at first.) In case (b), can one give a better bound on $\ell'$ than $O((\log n)^2)$? (Answer: no; see below.)
  2. (The question I meant to ask.) In case (b), can one give a better on bound on $\ell$ than $O((\log n)^2)$? Perhaps $O(\log n)$? (Answer: yes; see below.)
  • $\begingroup$ Ah, silly me, I slipped and asked the wrong question. Your answer below is interesting, though. Thanks! $\endgroup$ – H A Helfgott Mar 25 '18 at 12:55
  • $\begingroup$ Has there been any progress since mathoverflow.net/questions/68560/…? It would seem that the bound $O(\log n)$ does hold, but is there a result in the literature one can quote (or an argument one can explain fully and briefly)? $\endgroup$ – H A Helfgott Mar 25 '18 at 13:09
  • $\begingroup$ Harald, there have been a number of discussions on meta about such cases (concerning when after an answer, the OP realizes that this is not the right question, and alters the questions making the answer obsolete). See for instance: meta.mathoverflow.net/questions/2839 , meta.mathoverflow.net/questions/2951 , meta.mathoverflow.net/questions/3637 . You might thus consider resuming the original question (with subgroup chains), and posting a separate question for composition series. $\endgroup$ – YCor Mar 25 '18 at 13:20
  • $\begingroup$ All right, makes sense. But how am I going to do as much now? One answer refers to one question and the other one to the other one. Moreover, the first formulation had to be changed (it should be about case (b) alone, as the person who replied correctly understood; I was thinking about the second version of the question while asking the first version). $\endgroup$ – H A Helfgott Mar 25 '18 at 15:40
  • 1
    $\begingroup$ Since it is OK to ask two related questions in the same post, I would suggest that you put the original question back (I didn't delete my answer, because it's still a reasonable question) and call it Question 1, and call your new question Question 2. $\endgroup$ – Derek Holt Mar 25 '18 at 17:00

To answer your new question, Theorem 1.3 of this arXiv paper proves that the composition length $c(G)$ of primitive $G \le S_n$ satisfies $$c(G) \le \frac{8}{3} \log_2 n - \frac{4}{3}$$ and also identifies the examples in which equality holds.


Note: This is an answer to an earlier version of the question about whether there is an $O(\log n)$ bound on the length of an arbitrary subgroup chain of a group in case (b). The example below shows that the answer to that question is no, and we cannot do better than $O((\log n)^2)$.

${\rm GL}(n,p)$ acts primitively (in fact $2$-transitively) on $(p^n-1)/(p-1)$ points, and it has (for $n$ even) an elementary abelian $p$-subgroup of order $p^{n^2/4}$ (think of upper unitriangular matrices with an $n/2 \times n/2$ block in the top right corner), and hence a subgroup chain of length $n^2/4$.

  • $\begingroup$ This is a good answer to the question I mistakenly asked at first (bounding the length of subgroup chains). $\endgroup$ – H A Helfgott Mar 25 '18 at 13:06

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.