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

  1. H acts (n-m)-transitively on \{1,2,...,n\},
  2. |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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. If n\leq 12, see the above table.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s