It is well known, that any finite group of order $n$ is isomorphic to a subgroup of $S_n$. Let’s call a finite group $G$ incompressible iff it is not isomorphic to any subgroup of $S_{|G|-1}$ . Does there exist some sort of classification of incompressible groups?

What I currently know:

Any non-trivial incompressible group has non-trivial center

If the center of a group $G$ is trivial, then it acts faithfully by conjugation on $G \setminus \{e\}$.

If an incompressible group is non-trivially decomposed into a direct product of two its subgroups, it is isomorphic to $C_2 \times C_2$

One can construct a faithful action of $H \times K$ on $H \cup K$. It is defined as $(h, k)h_0 \mapsto hh_0$ and $(h, k)h_0 \mapsto kk_0$ for $h, h_0 \in H$, $k, k_0 \in K$.

$|H| + |K| \geq |H||K|$ iff either one of the groups is trivial, or both of them are isomorphic to $C_2$.

$C_2 \times C_2$ is the only possible group and indeed is not contained in $S_3$.

I also conjecture, that «direct product» in this statement can be replaced with «semidirect product», but do not know how to prove that.

All cyclic $p$-groups are incompressible

If $p$ is prime, then $S_{p^n - 1}$ does not have an element of order $p^n$

$Q_8$ is incompressible

$S_7$ does not contain $Q_8$ as a subgroup

  • 5
    $\begingroup$ According to Jack Schmidt's answer to mathoverflow.net/questions/16858, the only examples are $C_2\times C_2$, cyclic groups of prime power order, and (generalized) quaternion groups. He gives a reference to a paper by D.L Johnson. $\endgroup$
    – Derek Holt
    Jun 4, 2019 at 8:51
  • 3
    $\begingroup$ You could have considered another word for the definition. 😂 $\endgroup$ Jun 4, 2019 at 9:06
  • 5
    $\begingroup$ Why "horny"?!?! $\endgroup$
    – user1729
    Jun 4, 2019 at 9:16
  • 7
    $\begingroup$ At the risk of being boring, I have seen such groups be called 'incompressible' $\endgroup$ Jun 4, 2019 at 9:47
  • 2
    $\begingroup$ Well I dislike "horny" because I find it distracting. $\endgroup$
    – Derek Holt
    Jun 4, 2019 at 11:31

1 Answer 1


These were fully classified by Johnson in the paper 'Minimal Permutation Representations of Finite Groups'.

A group is incompressible iff it is isomorphic to one of the following:

  • Cyclic group of prime power order $C_{p^n}$
  • Generalised quaternion $2$-group $\langle x,y|x^{2^n}=1,x^{2^{n-1}}=y^2,x^y=x^{-1}\rangle$
  • the Klein four-group $C_2\times C_2$

The proof is reasonably short so well worth looking up!

Reference: Johnson, D. L. "Minimal permutation representations of finite groups." Amer. J. Math. 93 (1971), 857-866. MR 316540 DOI: 10.2307/2373739.

  • $\begingroup$ What does $x^y$ mean in this context? $\endgroup$
    – celtschk
    Oct 17, 2019 at 22:01
  • $\begingroup$ Here $x^y=y^{-1}xy$ $\endgroup$ Oct 17, 2019 at 22:08
  • $\begingroup$ So the last condition is equivalent to $xyx=y$, right? $\endgroup$
    – celtschk
    Oct 17, 2019 at 22:14
  • $\begingroup$ the last condition for the generalised quaternion $2$-group, yes $\endgroup$ Oct 18, 2019 at 7:54
  • $\begingroup$ @RobertChamberlain If you don't mind, is it widely used that $x^y = y^{-1}xy$, or could it also mean $yxy^{-1}$ in other places? $\endgroup$
    – Ovi
    Dec 31, 2019 at 20:23

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.