Complements in the symmetric group

Almost 20 years ago I was asked a question by Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in $S_E$ and $S_V$ (the groups of all permutations of the edges $E$ and vertices $V$ , respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of $S_m$ in $S_n$ . Specifically, he asked if $S_8$ has a complement in $S_{12}$ (this terminology is defined below). The answer is, as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a ” $k$ -tuple of complementary subgroups” for which the answer to the analogous question is ”yes.”

This post is a very short summary of part of a paper I wrote (still unpublished) which can be downloaded here. This post explains the ”no” part of the answer. For the more technical ”yes” part of the answer, see the more complete pdf version.

Notation: If $X$ is any finite set then

$|X|$ denotes the number of elements in $X$ .
$S_X$ denotes the symmetric group on $X$ .
$S_n$ denotes the symmetric group on $\{1,2,...,n\}$ .
$A_n$ denotes its alternating subgroup of even permutations.
$C_n$ denotes the cyclic subgroup of $S_n$ generated by the $n$ -cycle $(1,2,...,n)$ .
$M_{10}$ denotes ”the Mathieu group of degree $10$” and order $720=10!/7!$, which we define as the subgroup of $S_{10}$ generated by $(2,6,10,7)(3,9,4,5)$ and $(1,5)(3,8)(4,10)(7,9)$ .
$M_{11}$ denotes the Mathieu group of degree $11$ and order $7920=11!/7!$ generated by $(1,2,3,4,5,6,7,8,9,10,11)$ and $(3,7,11,8)(4,10,5,6)$ .
$M_{12}$ denotes the Mathieu group of degree $12$ and order $95040=12!/7!$ generated by $(2,3,5,9,8,10,6,11,4,7,12)$ and $(1,12)(2,11)(3,10)(4,9)(5,8)(6,7)$ .
For any prime power $q$ , ${\Bbb F}_q$ denotes the finite field with $q$ elements.
$AGL_n({{\Bbb F}}_q)$ denotes the affine group of transformations on ${\Bbb F}_q^n$ of the form $\vec{v}\longmapsto A\vec{v}+\vec{a}$ , where $A\in GL_n({{\Bbb F}}_q)$ and $\vec{a} \in {\Bbb F}_q^n$ .

If $G$ is a finite group and $G_1,G_2$ are subgroups then we say $G_2$ is the complement of $G_1$ when

$G_1\cap G_2=\{1\}$ , the identity of $G$ ,
and
$G=G_1\cdot G_2=\{g_1g_2\ |\ g_1\in G_1,\ g_2\in G_2\}$ .

Let $X$ denote a finite set. If $G$ is a subgroup of $S_X$ and $x\in X$ then we let $G_x$ denote the stabilizer of $x$ in $G$ :
$G_x=\{ g\in G\ |\ g(x)=x\}.$

Let $G$ be a permutation group acting on a finite set $X$ (so $G$ is a subgroup of the symmetric
group of $X$ , $S_X$ ). Let $k\geq 1$ be an integer and let
$X^{(k)}=\{{\rm distinct\ }k{\rm -tuples\ in\ }X\} =\{(x_1,x_2,...,x_k)\ |\ x_i\not= x_j,\ 1\leq i \textless j\leq k\}.$
We say $G$ acts $k$ -transitively on $X$ if $G$ acts transitively on $X^{(k)}$ via the ”diagonal” action
$g:(x_1,x_2,...,x_k)\longmapsto (g(x_1),g(x_2),...,g(x_k)).$

If $G$ acts transitively on $X$ and $G_x=1$ for some (hence all) $x\in X$ then we say $G$ acts regularly on $X$ . If $G$ acts $k$ -transitively on $X$ and acts regularly on $X^{(k)}$ then we say $G$ acts sharply $k$ -transitively on $X$ .

The classification of $k$ -transitive groups, for $k\geq 4$ , is to Jordan: A sharply $k$ -transitive group, $k\geq 4$ , must be one of the following.

$k \geq 6$ : $S_k$ , $S_{k+1}$ and $A_{k+2}$ only.
$k = 5$ : $S_5$ , $S_6$ , $A_7$ and the Mathieu group $M_{12}$ .
$k = 4$ : $S_4$ , $S_5$ , $A_6$ and the Mathieu group $M_{11}$ .

We give a table which indicates, for small values of $n$ , which $S_m$ have a complement in $S_n$ .

$n$	$m$	complement of $S_m$ in $S_n$
$4$	$2$	$A_4$
$4$	$3$	$C_4$
$5$	$2$	$A_5$
$5$	$3$	$\langle (1,2,3,4,5),(2,3,5,4)\rangle \cong AGL_1({{\Bbb F}}_5)$
		size $20$
$5$	$4$	$C_5$
$6$	$2$	$A_6$
$6$	$3$	$\langle (2,3,4,5,6),(3,4,6,5)\rangle \cong PGL_2({{\Bbb F}}_5)$
		size $120$
$6$	$5$	$C_6$
$7$	$2$	$A_7$
$7$	$5$	$\langle (1,2,6,5,3,7),(1,4,3,2,5,6)\rangle \cong AGL_1({{\Bbb F}}_7)$
		size $42$
$7$	$6$	$C_7$
$8$	$2$	$A_8$
$8$	$5$	$\langle (1,5,8,6,7,4),(1,5,8,7)(2,3,4,6)\rangle \cong PGL_2({{\Bbb F}}_7)$
		size $336$
$8$	$6$	$AGL_1({{\Bbb F}}_8)$
		size $56$
$8$	$7$	$C_8$
$9$	$2$	$A_9$
$9$	$6$	$PGL_2({{\Bbb F}}_8)$
		size $504$
$9$	$7$	$AGL_1({{\Bbb F}}_9)$
		size $72$
$9$	$8$	$C_9$
$10$	$2$	$A_{10}$
$10$	$7$	$M_{10}$
		size $720$
		( $PGL_2({{\Bbb F}}_9)$ is another)
$10$	$9$	$C_{10}$
$11$	$2$	$A_{11}$
$11$	$7$	$M_{11}$
		size $7920$
$11$	$9$	$AGL_1({{\Bbb F}}_{11})$
		size $110$
$11$	$10$	$C_{11}$
$12$	$2$	$A_{12}$
$12$	$7$	$M_{12}$
		size $95040$
$12$	$9$	$PGL_2({{\Bbb F}}_{11})$
		$=\langle (1,2,3,4,5,6,7,8,9,10,11), (1,2,4,8,5,10,9,7,3,6),$
		$(1,10)(2,5)(3,7)(4,8)(6,9)(11,12)\rangle$
		size $1320$
$12$	$11$	$C_{12}$

Proposition: $S_m$ has a complement in $S_n$ if and only if there is an subgroup $H$ of $S_n$ such that

$H$ acts $(n-m)$ -transitively on $\{1,2,...,n\}$ ,
$|H|=n(n-1)...(m+1)=n!/m!$ .

Example: $S_{10}$ has not one but two non-isomorphic subgroups, $M_{10}$ and $PGL_2({{\Bbb F}}_9)$ , of order $720=10!/7!$ , each of which acts $3$ -transitively on $\{1,2,...,10\}$ . Thus $S_7$ has two non-isomorphic complements in $S_{10}$ .

The statement below is the main result.

Theorem: The following statements hold.

If $n>2$ is not a prime power or a prime power plus $1$ then the only $1<m<n$ for which $S_m$ has a complement in $S_n$ are $m=2$ and $m=n-1$ .
If $n>12$ is a prime power and not a prime power plus $1$ then the only $1<m<n$ for which $S_m$ has a complement in $S_n$ are $m=2$ , $m=n-2$ and $m=n-1$ .
If $n>12$ is a prime power plus $1$ but not a prime power then the only $1<m<n$ for which $S_m$ has a complement in $S_n$ are $m=2$ , $m=n-3$ and $m=n-1$ .
If $n>12$ is both a prime power plus $1$ and a prime power then the only $1<m<n$ for which $S_m$ has a complement in $S_n$ are $m=2$ , $m=n-3$ , $m=n-2$ and $m=n-1$ .
If $n\leq 12$ , see the above table.