6
$\begingroup$

I would like to know $\mathfrak{S}_n$ could act faithfully transitively on sets with $m$ elements, with $m > n$. I know that it is not possible if $m = n+1$ except for $n = 5$. Any ideas ?

$\endgroup$
6
$\begingroup$

There are many sets of more than $n$ elements on which $\mathfrak S_n$ acts transitively. The largest possible example is that of the $n!$ total orderings of the set of $n$ elements (the one used to define $\mathfrak S_n$). One can deduce numerous smaller examples from this one.

$\endgroup$
  • 4
    $\begingroup$ ... which is just the action of the group on itself by multiplication $\endgroup$ – Hagen von Eitzen May 28 '14 at 13:32
  • 1
    $\begingroup$ @HagenvonEitzen Well, the actions are equivalent, but not naturally equivalent (one must pick one preferred total ordering to get an intertwining bijection). $\endgroup$ – Marc van Leeuwen May 28 '14 at 14:12
6
$\begingroup$

This question is equivalent to asking what the conjugacy classes of subgroups of $S_{n}$ are, since each transitive permutation representation of any finite group is permutation equivalent to the action on the cosets of one of its subgroups, and conjugate subgroups lead to equivalent permutation representations. Since every finite group embeds in some symmetric group, this would soon become an enormous task without further information.

For larger $n,$ I think that the next smallest degree of a faithful permutation representation of $S_{n}$ ( after $n$) is $\frac{n(n-1)}{2},$ which comes from the action on unordered pairs from $\{1,2, \ldots n \}.$ There are small exceptions to this though.

$\endgroup$
5
$\begingroup$

There is a complete classification of sets equipped with a transitive $G$-action. Namely:

If $G$ acts on a set $X$ (on the left) transitively, then there is a subgroup $H \le G$ and a $G$-equivariant bijection between the set $[G : H]$ of (left) cosets of $H$ (with the evident (left) $G$-action) and $X$.

In fact, this is just a different way of stating the orbit–stabiliser theorem. Thus, $G$ can act transitively on a set of $n$ elements if and only if $G$ has a subgroup of index $n$.

$\endgroup$
  • 1
    $\begingroup$ Calling this 'complete classification' is an overstatement, IMHO (just an equivalence of two classification problems). $\endgroup$ – Grigory M May 28 '14 at 13:24
  • 1
    $\begingroup$ This is a complete classification. We can't do any better if we don't know anything about $G$. $\endgroup$ – Zhen Lin May 28 '14 at 13:28
5
$\begingroup$

Here is a way to understand the faithful, transitive actions of $S_n$. We concentrate on small $|X|$. Clearly $\binom{n}{1} \leq X$, and we describe the $X$ that are “near” to $\binom{n}{k}$.

For $n$ sufficiently large compared to $k$, the answer is very simple: $S_n$ is (basically) acting on the subsets of size $k$ of $\{1,2,\ldots,n\}$. For small $k$ we can list the exceptions.

Claim (large $n$): For each $k$ there is some $N$ such that for $n>N$ the only faithful transitive actions of $S_n$ on $X$ with $\binom{n}{k} \leq |X| < \binom{n}{k+1}$ have a stabilizer $H$ satisfying $$\underbrace{S_1 \times \cdots \times S_1}_{k\text{ factors}} \times A_{n-k} \leq H \leq S_k \times S_{n-k},$$ where the left hand and right hand groups are the natural subgroups of $S_n$ acting on the sets $\{1\},\{2\}, \ldots, \{k\}, \{k+1, \ldots, n\}$ and $\{1,2,\ldots,k\}, \{k+1,\ldots,n\}$. This means that $$\binom{n}{k} \leq |X| \leq 2k! \binom{n}{k}=2n(n-1)\cdots(n-k+1).$$

Depending on what kind of relationship you want $|X|$ and $n$ to have, we can make the claim more specific. For instance, if you want $|X|$ to grow linearly with $n$, then for large enough $n$, you'll want $|X| < \binom{n}{2}$.

Claim ($k=1$): If $S_n$ has a faithful, transitive action on a set $X$ with $|X| < \binom{n}{2}$, then the stabilizer $H$ of a point is conjugate to exactly one of:

  • the natural $S_1 \times S_{n-1}$ with $|X|= \phantom{2}\binom{n}{1}$, or
  • the natural $S_1 \times A_{n-1}$ with $|X|= 2\binom{n}{1}$

unless $H$ exists in an exceptional way:

  • $n=5$, $|X|=6$, $H$ is the natural affine $\operatorname{AGL}(1,5) = F_{20}$
  • $n=6$, $|X|=6$, $H$ is the natural almost simple $\operatorname{PGL}(2,5)$,
    outer conjugate to $(H,|X|)=(S_1\times S_5,\binom{n}{1})$
  • $n=6$, $|X|=10$, $H$ is the natural wreath $S_3 \wr S_2$
  • $n=6$, $|X|=12$, $H$ is the natural almost simple $\operatorname{PSL}(2,5)$,
    outer conjugate to $(H,|X|)=(S_1 \times A_5,2\binom{n}{1})$

or $n$ is so small, that some rows need to be ignored:

  • $n\leq 3$, in which case no such $X$ exists, since $\binom{n}{2} \leq \binom{n}{1}$
  • $n=4$, in which case the second row is too big, since $\binom{n}{2} \leq 2\binom{n}{1}$

This says that actions of linear size are basically the natural action on $n$ points. We can also handle quadratic easily enough. Again for $n$ large enough, you'll want $|X| < \binom{n}{3}$.

Claim ($k=2$): If $S_n$ has a faithful, transitive action on a set $X$ with $|X|< \binom{n}{3}$, then the stabilizer $H$ of a point is conjugate to exactly one of:

  • the natural $S_1 \times S_{n-1}$ with $|X|= \phantom{2}\binom{n}{1}$,
  • the natural $S_1 \times A_{n-1}$ with $|X|= 2\binom{n}{1}$,
  • the natural $S_2 \times S_{n-2}$ with $|X|= \phantom{2}\binom{n}{2}$,
  • the natural $S_2 \times A_{n-2}$ with $|X|= 2\binom{n}{2}$,
  • the natural $A_2 \times S_{n-2}$ with $|X|= 2\binom{n}{2}$,
  • the natural $2(A_2 \times A_{n-2})$ with $|X|= 2\binom{n}{2}$,
  • the natural $A_2 \times A_{n-2}$ with $|X|= 4\binom{n}{2}$,

unless $H$ is a new group:

  • $n=5$, $|X|=6$, $H$ is the natural affine $\operatorname{AGL}(1,5) = F_{20}$
  • $n=6$, $|X|=6$, $H$ is the natural almost simple $\operatorname{PGL}(2,5)$,
    outer conjugate to $(H,|X|)=(S_1\times S_5,\binom{n}{1})$
  • $n=6$, $|X|=10$, $H$ is the natural wreath $S_3 \wr S_2$
  • $n=6$, $|X|=12$, $H$ is the natural almost simple $\operatorname{PSL}(2,5)$,
    outer conjugate to $(H,|X|)=(S_1 \times A_5,2\binom{n}{1})$
  • $n=6$, $|X|=15$, $H$ is an outer conjugate of $(H,|X|) = (S_2 \times S_4,\binom{n}{2})$
  • $n=7$, $|X|=30$, $H$ is the natural almost simple $\operatorname{PSL}(3,2)$
  • $n=8$, $|X|=30$, $H$ is the natural affine $\operatorname{ASL}(3,2)$
  • $n=8$, $|X|=35$, $H$ is the natural wreath $S_4 \wr S_2$

or $H$ does not exist / should be ignored:

  • $n\leq 3$, in which case no such $X$ exists, since $\binom{n}{3} \leq \binom{n}{1}$
  • $n=4,5$, in which case the fourth through the seventh row are too big, since $\binom{n}{3} \leq \binom{n}{2}$
  • $n=6,7,8$, in which case the fifth through seventh row are too big, since $\binom{n}{3} \leq 2\binom{n}{2}$
  • $n=9,10$, in which case the seventh row is too big, since $\binom{n}{3} \leq 4\binom{n}{2}$

This says the actions of quadratic size are basically the natural actions on pairs of points. The exceptions are either due to stabilizers not existing / having the right index for tiny $n$ (for example, $A_n$ has order $n!/2$ unless $n=0,1$), or honest to goodness other families from the O'Nan Scott classification: acting on block systems to give wreath product stabilizers, affine subgroups acting naturally on $p^n$ points, almost simple groups (either acting in in their “natural” way, or in other primitive ways), etc.

We could even continue to cubic:

Claim $(k=3)$: For $|X| < \binom{n}{4}$, the only new things happening are $$S_1 \times S_1 \times S_1 \times A_{n-3} \leq H \leq S_3 \times S_{n-3}$$ in general (that is $i\binom{n}{3}$ for $i=1,2,2,2,3,4,6,6,6,12$ up to conjugacy). The new exceptions are:

  • $n=4$, $|X|=6$, an exceptional $H=C_4$
  • $n=10$, $|X|=126$, the natural wreath $S_5 \wr S_2$
  • $n=12$, $|X|=462$, the natural wreath $S_6 \wr S_2$

The orders with problematic rows that may need to be ignored stop at $n=52$.

This says the actions of cubic size are basically the natural action on triples of points.

Caveat: Personally, I'm only interested in small $n$. For small $n$ there are very few exceptions, so these claims seem very useful. Also the proofs are tedious but easy. For general $n$, I get very weird inequalities that are basically ridiculous (find $n$ such that $n > n!$) but they have enough complication that I'm not sure how to prove them. I would not be surprised if some of them are still open. Some of the exceptional cases were only checked by order and multiplicity, so for $n < 52$ there could be an error where on of the general rows does not exist ($A_1$ vs $S_1$ type thing), while some other $H$ does exist. One could check this more carefully, but I think my lists give the right feel.

$\endgroup$

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.