Can we choose a set to make sure the action of a permutation group transitive?

Question

Let a finite group $G$ of order $n$ be given, so $G$ is isomorphic to a permutation group embedded in $S_n$. Can we always find a set $\Omega$ such that $G$ acts transitively on $\Omega$? (For example, does $G$ always act transitively on a set $\Omega$ of size $n$)? If so, is it a difficult problem to find the smallest such set?

I am learning about Cayley's theorem and wondering about this question. I know that in general, if we're given a finite group $G$ it's hard to find the symmetric group of minimal order into which $G$ embeds. This question seems analogous in some ways, and I'm curious if it is easier.

Answer 1

Your question has two parts.

We fix a finite group $G$ of order $n$.

(1) Does $G$ act transitively on a set $\Omega$ of size $n$?

The answer is yes, and the reason is already found in the standard proof of Cayley's theorem, which considers the the action of $G$ on itself (so $\Omega = G$) via $$g \bullet x = gx.$$ This action is easily shown to be free and transitive (which is called regular).

To check the transitivity, let $x,y\in\Omega = G$. Then for $g = y x^{-1}$ we have $$g \bullet x = (y x^{-1}) x = y.$$

(2) Smallest size of a set $\Omega$ such that $G$ acts transitively on $\Omega$

The smallest set $\Omega$ such that there is a transitive action of $G$ on $\Omega$ is the empty set $\Omega = \emptyset$. In this case, the transitivity condition $$\forall x,y\in X : \exists g\in G : g\bullet x = y$$ is vacuously true. (Admittedly this is a bit on the esoteric side, but everything is well-defined and it is the correct answer to your question.)

Addition: General characterization of transitive actions of $G$

As requested in the comments below, we investigate non-empty sets $X$ for a transitive action of $G$ on $X$. The general answer is the following statement.

Let $n$ be a positive integer.

There is a transitive action of $G$ on a set of size $n$ if and only if $G$ has a subgroup of index $n$.

Proof

For the direction $\Rightarrow$, assume that $G$ acts transitively on a set $X$ of size $n$. let $x\in X$. By the orbit-stabilizer theorem, the stabilizer $G_x$ of $x$ has index $[G : G_x] = \#(Gx) = \#X = n$ in $G$, where the equality $\#(Gx) = n$ follows from the transitivity of the action.

For the direction $\Leftarrow$, assume that $G$ has a subgroup $H$ of index $[G : H] = n$. Then the action of $G$ on the set $G/H$ of the left cosets of $H$ via $g\bullet hH = (gh) H$ is a transitive action of $G$ on a set of size $[G : H] = n$.

Example

The alternating group $A_4$ of order $12$ has subgroups of oder $1, 2, 3, 4$ and $12$ (but remarkably not of order $6$, see this question). Hence there exists a transitive action of $A_4$ on a given set $X$ if and only if $X$ is of size $0$, $1$, $3$, $4$, $6$, or $12$.

Answer 2

I like to add that it is a much more interesting question to ask for a minimal set $\Omega$ such that $G$ acts faithfully on $\Omega$. Answers:

• Which finite groups have their minimal permutation degree equal to their order?
• Minimal Permutation Representation Degree of a group: GAP implementation
• Finding the minimal $n$ such that a given finite group $G$ is a subgroup of $S_n$
• Minimal degree faithful permutation representations of some finite simple groups