Which finite groups have their minimal permutation degree equal to their order?

Question

I define the degree of a permutation representation of a group (or group acting on a set) as the number of letters in that representation, and the minimal degree of a group $G$ to be the minimum number of letters that the group can act on; i.e., $G$ injects into $S_n$ but not into $S_{n-1}$.

I define a group $G$ to be Cayley if its minimal degree is the same as the order of the group, so that the Cayley representation is an example of this minimal degree.

So which groups are Cayley?

So far I have found that cyclic groups of prime power order are Cayley, and the Klein 4-group is Cayley. The quaternion group $Q_8$ is Cayley because it has too many elements of order $4$ (six) to be injected into $S_7$, which has only four order-$4$ elements.

The direct product of a group $G$ of order $>2$ and a group $H$ of order $>1$ is not Cayley.

I wonder if there are any other Cayley groups. In particular I wonder if the generalized quaternion group $Q_{16}$ is Cayley.

Answer 1

To make sure this does not go unanswered (but I'm making it community wiki):

As Derek Holt points out, a similar question was asked in math.overflow; that question asked more generally what is the minimal degree of a group.

An answer by Jack Schmidt there cites the paper:

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

The paper is available on JSTOR (second link above). Theorem 1 states:

Theorem 1. The regular representation of a group $G$ is minimal if and only if $G$ is

1. a cyclic group of prime power order, or
2. a generalized quaternion $2$-group, or
3. the [Klein] four-group.

So this says that your question about $Q_{16}$ has a positive answer, and that the ones you found are essentially (except for larger generalized quaternion groups) all the examples of what you've called Cayley groups.

Answer 2

It might be worth producing a quick proof here, as the result is not difficult. (I came up with this, then checked Johnson's proof, which is incredibly similar.)

We proceed by induction on $|G|$, aiming to show that $G$ is $C_{p^n}$, $C_2\times C_2$, or $Q_{2^n}$.

If $G$ has two distinct subgroups $A$ and $B$ of prime orders $p$ and $q$ respectively (allowing $p=q$) then $G$ acts on the cosets of $A$ and $B$, yielding a faithful permutation representation on $|G|/|A|+|G|/|B|=|G|/p+|G|/q$ points. This is less than $|G|$ unless $p=q=2$. Thus we may assume that $G$ is a $p$-group with a unique subgroup of order $p$, or $p=2$. In the former case, it is a 'standard' fact that $p$-groups with a unique subgroup of order $p$ are cyclic or generalized quaternion. This yields the first and third of our options.

Thus by induction $p=2$, $G$ has two subgroups $A$ and $B$ of order $2$, and they are necessarily normal, else $G$ has a faithful representation on the cosets of $A$ (or $B$). The minimal degree of $G$ is at most the sum of that of $G/A$ and $G/B$, both of order $|G|/2$, so if $G$ is Cayley then both $G/A$ and $G/B$ are. If either is $C_2\times C_2$ then $|G|=8$ and we can just check, so both are cyclic or generalized quaternion. Thus $G/A$ has a unique subgroup of order $2$ for any subgroup $A$ of order $2$, so there is a unique subgroup of order $4$ containing $A$. Since there is more than one element of order $2$, there can therefore be no element of order $4$ squaring into $A$. But $A$ was chosen arbitrarily, so $G$ has no elements of order $4$ at all.

Thus $G$ has exponent $2$, so is abelian, and has a unique subgroup of order $4$ containing any given element of order $2$, so is $C_2\times C_2$, and we are done.