Sylow subgroups of symmetric groups

The purpose of this post is to collect some proofs of known results on Sylow subgroups of symmetric groups that are scattered across the literature, and in one case, wrongly stated in the standard reference. Throughout permutations act on the right. Let S_{p^r} denote the symmetric group on \{0,1,\ldots,p^r-1\}.

Rooted trees

Let T_r be the rooted p-ary tree with levels numbered from 0 at the root to r at the leaves. Let T_r(\ell) denote the set of p^\ell vertices at level \ell. We label the vertices in T_r(\ell) by \{0,1,\ldots, p^\ell-1\}, so that \beta \in T_r(\ell+1) is a child of \alpha \in T_r(\ell) if and only if \beta \equiv \alpha mod p^\ell. Thus the children of \alpha \in T_r(\ell) are

\alpha, \alpha + p^\ell, \ldots, \alpha + (p-1)p^\ell \in T_r(\ell+1).

For example, the children of the root vertex \varnothing are labelled 0,1,\ldots, p-1 and correspond to congruence classes modulo p, the children of 1 \in T_r(1) are labelled (in base p) by 01, 11, \ldots, (p-1)1, and correspond to the congruence classes modulo p^2 of numbers congruent to 1 modulo p, and so on. All this may be seen from the tree T_3 for p=3 shown below.

Let \mathrm{Aut}(T_r) be the group of automorphisms of T_r. Any automorphism is determined by its action on the p^r leaves of T_r, so, when it is useful to do so, we regard \mathrm{Aut}(T_r) as a subgroup of the symmetric group S_{p^r}.

Let 0 \le \ell < r. For each vertex \alpha \in T_r(\ell), let g(\alpha) \in \mathrm{Aut}(T_r) fix \alpha and all vertices of T_r that are not a descendant of \alpha, and permute the descendants of \alpha (of any generation) by adding p^{\ell} modulo p^{\ell+1}. More formally, the vertex \alpha + ip^\ell + jp^{\ell+1} where 0\le i < p and 0 \le j < p is sent to \alpha + (i+c \ \mathrm{mod}\  p)p^\ell +jp^{\ell+1}. For example, if r=3 then g(01) = (1,10,19) and

g(1) = (1,4,7)(10,13,16)(19,22,25).

(We rely on the length of the p-ary form of the vertex to indicate the intended level.) Let B(\ell) be the subgroup of \mathrm{Aut}(T_r) generated by all the g(\alpha) for \alpha \in T_r(\ell). Each subgroup B(\ell) is normalized by the B(j) for j < \ell, so P_r = B(r-1) B(r-2) \ldots B(0) is a p-subgroup of S_{p^r}. We have |P_r| = p^e where

e = 1 + p + \cdots + p^{r-1}.

It is well known that the highest power of p dividing n! is \sum_{i \ge 1} \lfloor n/p^i \rfloor, so P_r is a Sylow p-subgroup of S_{p^r}.

We now make the connection with the other standard construction of P_r. Let \phi : P_r \rightarrow P_{r-1} be the group homomorphism defined by restricting g \in \mathrm{Aut}(T_r) to T_r(r-1). Thus \phi(g) describes the action of g on the p^{r-1} vertices at level r-1, or, equivalently, on the p^{r-1} congruence classes of numbers in \{0,1,\ldots,p^r-1\} modulo p^{r-1}.

Lemma 1.P_r is permutation isomorphic to the iterated wreath product C_p \wr (C_p \wr \cdots \wr C_p) with r factors, in its intransitive action.

Proof. By induction \phi(P_r) \cong B(r-2)\ldots B(0) is permutation isomorphic to the imprimitive wreath product with r-1 factors. Therefore B(r-1) \cong C_p^{p^{r-1}} is the base group in a semidirect product B(r-1) \rtimes B(r-2) \ldots B(0) permutation isomorphic to C_p \wr (C_p \wr \cdots \wr C_p) in its imprimitive action. \Box

Centre and normalizer

The centre of P_r and its normalizer in S_{p^r} can be described by slightly more involved inductive arguments. The following elements of P_r will be useful: for 0 \le \ell < r, let z_r(\ell) = \prod_{\alpha \in T_r(\ell)} g(\alpha). For example, if p=3 and r=3 then

\begin{aligned} z_3(0) &= (0,1,2)(3,4,5)(6,7,8)(9,10,11) \ldots (24,25,26), \\  z_3(1) &= (0,3,6)(1,4,7)(2,5,8)(9,12,15)\ldots (20,23,26), \\ z_3(2) &= (0,9,18)(1,10,19)(2,11,20)(3,12,21) \ldots (8,17,26). \end{aligned}

Observe that \phi(z_r(\ell)) = z_{r-1}(\ell) for 0 \le \ell < r-1, and that \phi(z_r(r-1)) = \mathrm{id}.

Lemma 2. Z(P_r) = \langle z_r(r-1) \rangle.

Proof. If r=1 then z_1(0) = (0,1,\ldots,p) generates P_1. Let r \ge 2 and let z \in Z(P_r). By induction \phi(z) \in \langle \phi(z_r(r-2))\rangle. Hence z \in \phi^{-1} \langle \phi(z_r(r-2)) \rangle = B_{r-1} \langle z_{r}(r-2) \rangle. Let z = b z_r(r-2)^i where 0 \le i \le p-1 and b \in B_{r-1}. Since B(r-1) is abelian, we see that z_r(r-2)^i commutes with all permutations in B(r-1). If i\not=0 then there exists \alpha \in T_r(r-1) such that \alpha z \not= \alpha and so

\alpha g(\alpha) z_r(r-2)^i = (\alpha +p^n) z_r(r-2)^i = \alpha + p^{r-1} + ip^{r-2}


\alpha z_r(r-2)^i g(\alpha)  = (\alpha +ip^{r-2}) g_x = \alpha + ip^{r-2},

a contradiction. Therefore i=0 and z = \prod_{\beta \in T_r(r-1)} g(\beta)^{i_\beta} where 0 \le i_\beta < p for each \beta. A similar argument considering the actions of the generators g(\alpha) for \alpha \in T_r(r-2) now shows that i_\beta is independent of \beta, and so g \in \langle z_r(r-1)\rangle. \Box

The normalizer N_{S_{p^r}}(P_r) turns out to be a split extension of P_r. Let c be a primitive root modulo p. Let \alpha \in T_r(\ell). Let h(\alpha) fix \alpha and every vertex that is not a descendant of \alpha and permute the descendants of \alpha (of any generation) by sending \alpha + ip^\ell + jp^{\ell+1} where 0 \le i < \ell and 0 \le j < p^{r-\ell-1} to \alpha + (ci \ \mathrm{mod}\ p)p^\ell + jp^{\ell+1}. Thus h(\alpha) fixes the child 0\alpha of \alpha, and permutes the remaining p-1 children 1\alpha \ldots (p-1)\alpha by a (p-1)-cycle, acting compatibly on their descendants in turn. Let k_r(\ell) = \prod_{\alpha \in T_r(\ell)}h(\alpha). For example, if p=3 and r=3 then h(01) = (12,21), h(1) = (4,7)(13,16)(22,25) and

\begin{aligned}\scriptstyle k_3(0) = (1, 2)(4, 5)(7, 8)(10, 11)(13, 14)(16, 17)(19, 20)(22, 23)(25, 26), \\ \scriptstyle k_3(1) = (3, 6)(4, 7)(5, 8)(12, 15)(13, 16)(14, 17)(21, 24)(22, 25)(23, 26), \\ \scriptstyle k_3(2) = (9, 18)(10, 19)(11, 20)(12, 21)(13, 22)(14, 23)(15, 24)(16, 25)(17, 26).  \end{aligned}

The permutation k_3(0) is shown below.

Proposition 3. N_{S_{p^r}}(P_r) = P_r \rtimes \langle k_r(\ell) : 0 \le \ell < r-1 \rangle.

Proof. Let g \in N_{S_{p^r}}(P_r). By a similar argument to Lemma 1, we have g \in B(r-2)\ldots B(0) \langle k_3(0), \ldots, k_3(r-2) \rangle h where h \in \ker \phi. By composing h with a suitable power of z_r(r-1), we may assume that 0h = 0. Let h^\star denote the permutation induced by h on \{p^{\ell-1},\ldots,(p-1)p^{\ell-1}\}. Since Z(P_r) = \langle z_r(r-1) \rangle is a characteristic subgroup of P_r, it is normalized by g. Therefore h^\star normalizes the p-cycle (0,p^{\ell-1},\ldots,(p-1)p^{\ell-1}) forming part of the disjoint cycle form of z_r(r-1). Therefore h^\star acts on \{p^{\ell-1},\ldots,(p-1)p^{\ell-1}\} as some power of k_r(r-1). Since h normalizes Z(P_r), it follows that h acts compatibly on all the other p-cycles in the disjoint cycle form of z_r(r-1), and so h \in \langle k_r(r-1) \rangle, as required. \Box

In particular, a Sylow 2-subgroup of S_{2^r} is self-normalizing. The following corollary is also immediate from Proposition 3.

Corollary 4. The number of Sylow p-subgroups of S_{p^r} is (p^r)!/p^{e}(p-1)^r where e = 1 + p + \cdots + p^{r-1}. \Box

Derived group

Using the transitive action of P_r on the vertices at each level of T_r, it is not hard to prove the following lemma.

Lemma 5. The derived group P_r' of P_r contains the permutations g_\alpha g_\beta^{-1} for all \alpha, \beta vertices at the same level of T_r. \Box

Corollary 6. The permutations g(\alpha) g(\beta)^{-1} for \alpha, \beta vertices at the same level of T_r generate P_r' and P_r/P_r' \cong C_p^r.

Proof. Let \gamma_\ell \in T_r(\ell) be the vertex labelled 0 at level l of T_r. Let H be the subgroup generated by the permutations g(\alpha) g(\beta)^{-1}. By Lemma 5, \mathrm{Aut}(T_r) is generated by the g(\gamma_\ell) and H. Moreover, the g(\gamma_\ell) commute modulo H. Therefore P_r/H is abelian, and so H = P_r', with the permutations g(\gamma_\ell) generating the quotient group. \Box

Weisner’s counting argument

In On the Sylow subgroups of the symmetric and alternating groups,
Amer. J. Math. 47 (1925), 121–124, Louis Weisner gives a counting argument that, specialized to P_r, claims to show that P_r has exactly (p^r)!/p^e (p-1)^e Sylow p-subgroups, where, as above e = 1 + p + \cdots + p^{r-1}. The exponent of p is correct, but by Corollary 4, the exponent of p-1 is too large. Weisner’s error appears to be on page 123, where he implicitly assumes that Sylow subgroups of S_{p^r} with the same base group are equal. This is false whenever p \not= 2 and r \ge 2: for example

\begin{aligned} \langle (036), (147), (258) \rangle \rtimes \langle (012)(345)(678) \rangle, \\ \langle (063), (147), (258) \rangle \rtimes \langle (012)(378)(645) \rangle \end{aligned}

are distinct.

An alternative reference for the correct result is La structure des p-groupes de Sylow des groupes symétriques finis, Léo Kaloujnine, Ann. Sci. École Norm. Sup. (3) 65 (1948), 239–276: see page 262. In the footnote, Kaloujnine notes that, in general, the action of N_{S_{p^r}}(P_r) on P_r does not induce the full automorphism group. Indeed, when p=2 and r=2, the base group \langle (02), (13)\rangle of the wreath product

C_2 \wr C_2 = \langle (02), (13), (01)(23) \rangle

is not even a characteristic subgroup of C_2 \wr C_2. For more on this see On the structure of standard wreath products of groups, Peter M. Neumann, Math. Z. 84 1964, 343–373.

The mistake in Weisner’s paper is pointed out on page 73 of an M.Sc. thesis by Sandra Covello.

Final remarks

Lower central series

The lower central series of P_r was found by Weir in The Sylow subgroups of the symmetric groups, Proc. Amer. Math. Soc. 6 (1955) 534–541. Another description is given in the paper of Kaloujnine. There has been much further related work: see for example Lie algebra associated with the group of finitary automorphisms of p-adic tree, N. V. Bondarenko, C. K. Gupta V. I. Sushchansky, J. Algebra 324 (2010), 2198–2218 and the references to earlier papers therein. Using Lemma 6, one gets the description in Proposition 8 below. (This is almost certainly equivalent to a result in Kaloujnine’s paper stated using his formalism of tableaux polynomials, but the close connection with cyclic codes seems worth noting.)

Definition 7. Let P_r^m be the mth term in the lower central series of P_r, so P_r^1 = P_r' and P_r^m = [P_r, P_r^{m-1}] for m \ge 2. Let B(\ell,m) = P_r^m \cap B(\ell) for 0 \le s < r.

Let V = \mathbb{F}_p^{p^\ell}. Index coordinates of vectors in V by the set \{0,1,\ldots,p^{\ell}-1\} labelling the vertices in T_r(\ell). Given v \in V, we may define a corresponding element of B(\ell) by \prod_{\alpha=0}^{p^\ell-1} g(\alpha)^{v_\alpha}. This sets up a bijective correspondence between subgroups of B(\ell) and subspaces of \mathbb{F}_p^{p^\ell}. In turn, a subspace of \mathbb{F}_2^{p^\ell} invariant under the shift map sending (v_0,\ldots,v_{p^\ell-2},v_{p^\ell-1}) to (v_{p^\ell-1},v_0, \ldots, v_{p^\ell-2}) corresponds to an ideal in \mathbb{F}_p[x]/(x^{p^\ell}-1). (This is a basic observation in the theory of cyclic error-correcting codes.)

Proposition 8. We have

P_r^m = B(r-1,m)B(r-2,m) \ldots B(0,m)

where B(\ell, m) corresponds to the ideal in \mathbb{F}_p[x]/(x^{p^\ell}-1) generated by (x-1)^m.

Proof. Under the correspondence above, multiplication by x corresponds to conjugation by (0,1,\ldots,p^{\ell}-1) \in P_\ell. Each B(\ell,m) is invariant under conjugation by P_r, so we see that the subspaces of V corresponding to the B(\ell,m) are all x-invariant. Hence they are ideals in \mathbb{F}_p[x]/(x^{p^\ell}-1). It is easily seen by induction that (x-1)^m is in the ideal corresponding to B(\ell,m). Since the lower central series is strictly decreasing, and (x-1)^m generates an ideal of codimension m, the proposition follows. \Box

Corollary 9. Let M be the natural permutation module for P_r, defined over a field of characteristic p. Then the socle series for M and the radical series for M coincide; the mth term (from the top) in either is the image of (t-1)^m where t = (0,1,\ldots, p^r). \Box

Thus the radical and socle series of M considered just as an \mathbb{F}_p\langle t \rangle-module coincide with the radical and socle series of M as an \mathbb{F}_pP_r-module. This is not really unexpected: the trivial module is the unique simple \mathbb{F}\langle t \rangle-module, and M is uniserial even when considered as an \mathbb{F}_p\langle t \rangle-module. Still, it seems non-obvious without this injection of theory that \mathrm{im}(t-1)^m = \mathrm{ker}(t-1)^{p^r-m} is P_r-invariant.

It is a nice exercise to find the decomposition of the analogously defined permutation module over \mathbb{C}: it has exactly p-1 summands of dimension p^\ell for each \ell \in \{1,\ldots, r-1\} and p 1-dimensional summands, affording the characters of P_r / B(r-1)\ldots B(1) \cong C_p. The correspondence after Definition 7 can also be used to prove this conjecture.

Proposition 10. There are (p-1)^r conjugacy classes of p^r-cycles in P_r. All p^r-cycles in N_{S_{p^r}}(P_r) are conjugate.

Sketch proof. We take the special case r=2. Let g \in P_2 \cong C_p \wr C_p. In the notation of Chapter 4 of The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley 1981), we have

g = (h^{a_0},\ldots,h^{a_{p-1}}; t )

where h generates a copy of C_p and t is a non-identity power of (0,1,\ldots, p-1). For simplicity, assume that t = (0,1,\ldots,p-1). The base group part of g corresponds to (a_0,\ldots,a_{p-1}) \in \mathbb{F}_p^p. Let c = a_0 + \cdots + a_{p-1}. The identity

x^k = k^{-1}xk = k^{-1}xkx^{-1} h = k^{-1}k^{x^{-1}} h

implies that

\begin{aligned} (h^{a_0}&,\ldots,h^{a_{p-1}}; t)^{(h,1,\ldots,1; 1)} \\ &= (h^{-1},1,\ldots,1)(h,1,\ldots,1)^{t^{-1}}(h^{a_0},\ldots,h^{a_{p-1}};t) \\        &= (h^{-1},1,\ldots,1)(1,h,\ldots,1)(h^{a_0},\ldots,h^{a_{p-1}}; t) \\        &= (h^{a_0-1},h^{a_1+1},\ldots,h^{a_{p-1}};t). \end{aligned}
The new base group part corresponds to (a_0-1,a_1+1,\ldots,a_{p-1}). Similarly by conjugating by (1,h,\ldots,1), and so on, we can shift any two adjacent positions as above. It follows that the conjugacy class of g contains all elements (h^{b_0},\ldots,h^{b_{p-1}}; t) such that b_0 + \cdots + b_{p-1} = c. By the general theory in the reference above, the conjugacy class is no larger. Extending the action to the normalizing group, Proposition 3 implies that any non-zero sum can be attained. \Box

Automorphism groups of cyclic codes

The previous section implies that the automorphism group of a p-ary cyclic code of length p^r contains a Sylow p-subgroup of S_{p^r}. In fact we get more: provided we label positions in the sensible way, so that the cyclic shift is (0,1,\ldots,p^r-1), the automorphism group contains our distinguished Sylow subgroup S_{p^r}. The results on N_{S_{p^r}}(P_r) above can be used to give a more powerful version of a result of Brand on equivalences of codes.

Proposition 11. Cyclic codes C and C' of length p^r are equivalent if and only if they are equivalent by an element of \langle k_r(\ell) : 0 \le \ell < r-1 \rangle.

Proof. Let Cg= C'. We have seen that P_r \le \mathrm{Aut}(C) and P_r \le \mathrm{Aut}(C'). Hence C'g^{-1}P_rg = C' so P_r^g \le \mathrm{Aut}(C'). By Sylow’s Theorem, there exists h \in \mathrm{Aut}(C') such that P_r^{gh} = P_r. Let gh = k \in N_{S_{p^r}}(P_r). Clearly we have C' = C'h = Cgh = Ck. Now apply Proposition 3 to k. \Box

For comparison, Brand’s result (see Lemma 3.1 in Polynomial isomorphisms of combinatorial objects, Graphs and Combinatorics 7 7–14) says that, for codes of arbitrary length, if P is a Sylow p-subgroup of C, then the equivalence may be assumed to conjugate (0,1,\ldots,p^r-1) to another permutation in P.

Application to Sylow’s Theorem

Let G be a finite group of order n. If G acts transitively on a set of size coprime to p then any point stabiliser contains a Sylow p-subgroup of G. The existence of Sylow subgroups of S_n gives a very convenient setting to exploit this observation. By letting G act regularly on itself, we may regard G as a subgroup of S_n. Fix a Sylow p-subgroup P of S_n. The coset space S_n/P has size coprime to p. Let Pg be in an orbit of G of size coprime to p and let H \le G be the stabiliser of Pg. Now PgH = Pg implies that gHg^{-1} is a subgroup of P, so gHg^{-1} is a p-subgroup of G of order divisible by the highest power of p dividing |G|.

Intransitivity of derived group

By Corollary 6, any permutation in P_r' permutes amongst themselves the odd and even numbers in \{0,1,\ldots,p^r-1\}. Hence P_r' is not transitive. More generally, let Q \le S_n be a transitive p-group. By embedding Q in a Sylow p-subgroup P of S_n, we see that Q' \le P' is not transitive. Of course this can be proved in many other ways: for example, if Q' is transitive then Q = RQ' where R is a point stabiliser. But Q' \le \Phi(Q), where \Phi(G) is the Frattini subgroup of `non-generators’ of Q, so we have Q = R, a contradiction.

Automorphisms of permutation groups

Let G \le S_n be a transitive permutation group. It is natural to ask when every automorphism of G is induced by the action of N_{S_n}(G). For example, this is the case whenever G acts regularly.

Magma code

MAGMA code constructing all the permutations and groups defined in this post is available here.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: