## 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}$

whereas

$\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 $m$th 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 $m$th 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.