## Permutation bases and an unexpected duality

June 10, 2018

Let $G$ be a finite group acting transitively on a set $\Omega$. An important object in representation theory, much used by Burnside and his successors to study the action of $G$, is the permutation module $\mathbb{K}\Omega$, defined to be the vector space of all formal linear combinations of the elements of $\Omega$, over a chosen field $\mathbb{K}$. Thus $\mathbb{K} \Omega$ has $\Omega$ as a canonical basis.

It’s easy to fall into the trap of thinking that the canonical basis of a permutation module is in some sense special, or even unique. The latter is certainly wrong in all but the smallest cases. For example, whenever $\mathbb{K}$ has characteristic zero, or the characteristic of $\mathbb{K}$ does not divide $|\Omega|- 1$, the linear map defined on the canonical basis by

$\omega \mapsto \sum_{\omega' \in \Omega} \omega'$

is an isomorphism of $\mathbb{K} G$-modules. Generally, if $G$ has rank $r$ in its action on $\Omega$ then $\mathrm{dim}\ \mathrm{Hom}_{\mathbb{K}S_n}(\mathbb{K}\Omega,\mathbb{F}\Omega) = r$, and a generic linear combination of these $r$-linearly independent homomorphisms is an automorphism of $\mathbb{K}\Omega$ sending the canonical basis to a basis of $\mathbb{K}\Omega$ permuted by $G$.

The motivation for this post is an example where $\mathbb{K}\Omega$ has a permutation basis not obtained in this way. Take $\mathrm{GL}_3(\mathbb{F}_2)$ acting on $E = \langle e_1,e_2,e_3 \rangle_{\mathbb{F}_2}$. Let $\Omega = \bigl\{ \langle e \rangle : e \in E \backslash \{0 \} \bigr\}$ be the set of lines in $E$. (Each line has a unique non-zero point; but we use the line notation to makes clear the distinction between $e \in E$ and $\langle e \rangle \in \mathbb{K}\Omega$.) The canonical basis for $\mathbb{K}\Omega$ is therefore

$\bigl\{ \langle e_1 \rangle, \langle e_2 \rangle, \langle e_3 \rangle, \langle e_2 + e_3 \rangle, \langle e_1 + e_3 \rangle, \langle e_1 + e_2 \rangle, \langle e_1 + e_2 + e_3 \rangle \bigr\}.$

For each plane $\Pi$ contained in $E$, let $v_\Pi = \sum_{e \in \Pi \backslash \{0\}} \langle e \rangle$. Clearly $v_\Pi g = v_{\Pi g}$, for $g \in \mathrm{GL}_3(\mathbb{F}_2)$, so the $v_\Pi$ are permuted by $\mathrm{GL}_3(\mathbb{F}_2)$. The duality $\langle e \rangle \mapsto \langle e \rangle^\bot$ gives a bijection between the $7$ lines and $7$ planes. Ordering basis vectors as above, the $v_{\langle e \rangle^\bot}$ for non-zero $e \in E$ have the coefficients shown in the matrix $P$ below.

$\left(\begin{matrix} 0&1&1&1&0&0&0 \\ 1&0&1&0&1&0&0 \\ 1&1&0&0&0&1&0 \\ 1&0&0&1&0&0&1 \\ 0&1&0&0&1&0&1 \\ 0&0&1&0&0&1&1 \\ 0&0&0&1&1&1&0 \end{matrix} \right)$

The determinant of $P$ is $-24$, so whenever $\mathbb{K}$ has characteristic $0$ or $\mathbb{K}$ has prime characteristic $\ge 5$, the $v_\Pi$ form a permutation basis for $\mathbb{K} \Omega$. Since $\mathrm{GL}_3(\mathbb{F}_2)$ acts $2$-transitively on $\Omega$, the endomorphism algebra of $\mathbb{K}\Omega$ is $2$-dimensional, spanned by the identity and the ‘complementing’ map defined above. Therefore this alternative basis is not obtained by an endomorphism of $\mathbb{K}\Omega$.

Now for the surprising duality. When $\mathbb{K}$ has characteristic $2$, the three linear relations whose first is

$v_{\langle e_1 \rangle^\perp} + v_{\langle e_1 + e_2 \rangle^\perp} + v_{\langle e_1 + e_3 \rangle^\perp} + v_{\langle e_1 + e_2 + e_3 \rangle^\perp} = 0$

show that $\mathrm{rank}\ P \le 4$. It is clear from the final four rows of $P$ that $v_{\langle e_2 + e_3\rangle^\perp}$, $v_{\langle e_1 + e_3\rangle^\perp}$, $v_{\langle e_1 + e_2 \rangle^\perp}$, $v_{\langle e_1 + e_2 + e_3 \rangle^\perp}$ are linearly independent and span a $4$-dimensional submodule of $\mathbb{K} \Omega$. The sum of these vectors, namely $\langle e_1 \rangle + \cdots + \langle e_1 + e_2+e_3\rangle$, spans the unique trivial submodule of $\mathbb{K}\Omega$. Since $7$ is odd, it splits off as a direct summand. Observe from rows $4$ and $7$ of the matrix $P$ that

\begin{aligned} \langle e_1 \rangle + \langle e_1 + e_2 \rangle + \langle e_1 + e_3 \rangle & + \langle e_1 + e_2 + e_3 \rangle \\ &\quad = v_{\langle e_2+e_3\rangle^\perp} + v_{\langle e_1+e_2+e_3 \rangle^\perp}. \end{aligned}

A convenient basis for a complement to the trivial submodule is therefore

\begin{aligned} w_1 &= \langle e_1 \rangle + \langle e_1 + e_2 \rangle + \langle e_1 + e_3 \rangle + \langle e_1 + e_2 + e_3 \rangle \\ w_2 &= \langle e_2 \rangle + \langle e_1 + e_2 \rangle + \langle e_2 + e_3 \rangle + \langle e_1 + e_2 + e_3 \rangle \\ w_3 &= \langle e_3 \rangle + \langle e_1 + e_3 \rangle + \langle e_2 + e_3 \rangle + \langle e_1 + e_2 + e_3 \rangle. \end{aligned}

We have shown that $W = \langle w_1, w_2, w_3 \rangle_\mathbb{K}$ is a $3$-dimensional $\mathbb{K}\mathrm{GL}_3(\mathbb{F}_2)$-submodule of $\mathbb{K}\Omega$. In the special case $K = \mathbb{F}_2$, the representation homomorphism $\rho : \mathrm{GL}_3(\mathbb{F}_2) \rightarrow \mathrm{GL(W)}$ is even an isomorphism. Looking at the definitions of $w_1, w_2, w_3$, it might seem almost obvious that $W$ is isomorphic to the natural representation of $\mathrm{GL}_3(\mathbb{F}_2)$.

This is not the case. There are two $3$-dimensional irreducible $\mathbb{F}_2\mathrm{GL}_3(\mathbb{F}_2)$-modules, namely the natural module $E$ and its dual $E^\star$. These are distinguished by the action of the matrices in $\mathrm{GL}_3(\mathbb{F}_2)$ of order $7$. Let

$g = \left( \begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} \right)$

be the companion matrix for the irreducible cubic $1 + X + X^3$. Computing the action of $g$ on $W$ we find that

\begin{aligned} w_1 g &= \langle e_1 g \rangle + \langle (e_1 + e_2)g \rangle + \langle (e_1 + e_3) g \rangle + \langle (e_1 + e_2 + e_3)g \rangle \\ &= \langle e_2 \rangle + \langle e_2 + e_3 \rangle + \langle e_1 \rangle + \langle e_1 + e_3 \rangle \\ &= w_1 + w_2. \end{aligned}

Similar calculations show that $w_2 g = w_3$ and $w_3 g = w_1$. Reordering basis vectors as $w_2, w_3, w_1$, we see that in its action on $W$, $g$ is represented by the matrix

$\left( \begin{matrix} 0 &1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{matrix} \right).$

This is the companion matrix of the irreducible cubic $1 + X^2 + X^3$, which lies in the other conjugacy class of matrices of order $7$ to $g$. Therefore $W \cong E^\star$.

Since $\mathrm{dim}\ \mathrm{End}_{\mathbb{F}_2\mathrm{GL}_3(\mathbb{F}_2)}(\mathbb{F}_2\Omega) = 2$, it follows that $\mathbb{F}_2\Omega \cong \mathbb{F}_2 \oplus U$ where $U$ is an indecomposable $6$-dimensional $\mathbb{F}_2\mathrm{GL}_3(\mathbb{F}_2)$-module with $\mathrm{rad}\ U = \mathrm{soc}\ U \cong E^\star$ and $U / \mathrm{rad}\ U \cong E$. As expected, the summand $U$ is self-dual, but I think it is a mild surprise that it has $E^\star$ and not $E$ in its socle.

## Burnside’s method

April 24, 2017

Burnside proved in 1901 that if $p$ is an odd prime then a permutation group containing a regular subgroup isomorphic to $C_{p^2}$ is either imprimitive or 2-transitive. His proof was an early application of character theory to permutation groups. Groups with this property are now called B-groups.

Burnside attempted to generalize his 1901 result in two later papers: in 1911, he claimed a proof that $C_{p^n}$ is a B-group for any prime $p$ and any $n \ge 2$, and in 1921, he claimed a proof that all abelian groups, except for elementary abelian groups, are B-groups. The first claim is correct, but his proof has a serious gap. This error appears to have been unobserved (or, just possibly, observed but ignored, since the result was soon proved in another way using Schur’s theory of $S$-rings) until 1994 when it was noted by Peter Neumann, whose explication may be found in his introduction to Burnside’s collected works. In 1995, Knapp extended Burnside’s argument to give a correct proof. Burnside’s second claim is simply false: for example, $S_4 \wr S_2$ acts primitively on $\{1,2,3,4\}^2$, and has a regular subgroup isomorphic to $C_4 \times C_4$. In one of my current projects, I’ve simplified Knapp’s proof and adapted Burnside’s character-theoretic methods to show, more generally, that any cyclic group of composite order is a B-group.

The purpose of this post is to record some proofs omitted for reasons of space from the draft paper. This companion post has some notes on B-groups that may be of more general interest.

### Sums over roots of unity

Let $\xi$ be a primitive $n$th root of unity. Define

$R(r) = \{ r, r + p^{n-1}, \ldots, r+ (p-1)p^{n-1} \}$

for $0 < r < p^{n-1}$. Define a subset $Z$ of $\{1,\ldots,p^n-1\}$ to be null if there exists $s \in \mathbb{N}_0$ and distinct $r_{ij} \in \{1,\ldots, p^{n-1}-1\}$ for $0 \le i \le p-1$ and $1 \le j \le s$ such that $r_{ij} \equiv i$ mod $p$ for each $i$ and $j$ and

$Z = \bigcup_{i=0}^{p-1} \bigcup_{j=1}^s R(r_{ij}).$

Proposition 6.2 Let $\omega = \zeta^{p^{n-1} c}$ where $c$ is not divisible by $p$. Let $\mathcal{O} \subseteq \{1,\ldots,p^n-1\}$. Then

$\sum_{i \in \mathcal{O}} \zeta^i = \sum_{i \in \mathcal{O}} \omega^i$

if and only if either

1. $\mathcal{O}$ is null; or
2. $\mathcal{O} = \{p^{n-1}, \ldots, (p-1)p^{n-1} \} \; \cup \; \bigcup_{i=1}^{p-1} R(r_i) \; \cup \; Z$ where $Z$ is a null set, the $r_i$ are distinct elements of $\{1,\ldots,p^{n-1}-1\}\backslash Z$ and $r_i \equiv i$ mod $p$ for each $i$.

Proof. Since the minimum polynomial of $\zeta$ is

$1+X^{p^{n-1}} + \cdots + X^{(p-1)p^{n-1}}$

we have $\sum_{i \in R(r)} \zeta^i = 0$. Since $\xi^{p^{n-1}} = \omega$, we have $\sum_{i \in R(r)} \omega^i = p\omega^r$. It follows that $\sum_{i \in Z} \xi^i = \sum_{i \in Z} \omega^i = 0$ if $Z$ is a null set. (For the second equality, note the contributions from the $R(r_{ij})$ for fixed $j$ combine to give $p + p\omega + \cdots + p\omega^{p-1} = 0$.) For (2) we have $\sum_{i=1}^{p-1} \xi^{i p^{n-1}} = \omega + \cdots + \omega^{p-1} = -1$, $\sum_{i=1}^{p-1} \omega^{i p^{n-1}} = (p-1)$ and $\sum_{i=1}^{p-1} p \omega^i = - p$. This proves the ‘if’ direction.

Conversely, by Lemma 2.1 in the paper, $\mathcal{O} \backslash \{p^{n-1},\ldots,(p-1)p^{n-1} \}$ is a union of some of some of the sets $R(r)$. There exists a unique subset $A$ of $\{1,\ldots,p-1\}$ and unique $j_i \in \mathbb{N}$ for $0 \le i \le p-1$ and unique $r_{ij} \in \{1,\ldots, p^{n-1}-1\}$ for $1 \le j \le s$ and $0 \le i \le j_i$ such that

$\mathcal{O} = \{ p^{n-1} i : i \in A \} \cup \bigcup_{i=0}^{p-1}\bigcup_{j=1}^{i_j} R(r_{ij}).$

We have $\sum_{i \in \mathcal{O}} \zeta^i = \sum_{i \in A} \omega^i$ and $\sum_{i \in \mathcal{O}} \omega^i = |A| + \sum_{i=0}^{p-1} pj_i \omega^i$. Therefore

$|A| + \sum_{i=0}^{p-1} (pj_i - [i \in A]) X^i$

has $\omega$ as a root. Since this polynomial has degree at most $p-1$ and the minimal polynomial of $\omega$ is $1+X +\cdots + X^{p-1}$, it follows that the coefficients are constant. Hence

$|A| + pj_0 = pj_i - [i \in A]$

for $1\le i \le p-1$. If $A = \varnothing$ then $j_0 = j_1 = \ldots = j_{p-1}$ and $\mathcal{O}$ is null. Otherwise, taking the previous displayed equation mod $p$ we see that $A = \{1,\ldots,p-1\}$, and, moreover, the $j_i$ are constant for $1 \le i \le p-1$. (This holds even if $p=2$.) Set

$s = j_1 = \ldots = j_{p-1}.$

We have $j_0 = s-1$. Hence, $s \in \mathbb{N}$ and choosing in any way $r_i \in \{1,\ldots,p^{n-1}-1\}$ for $1 \le i \le p-1$ such that $r_i \in \mathcal{O}$, we see that $\mathcal{O}$ is the union of $\{p^{n-1}, \ldots, (p-1)p^{n-1}\}$, the sets $R(r_i)$ for $1 \le i \le p-1$ and a null set. $\Box$.

### Ramanujan matrices.

For $p$ prime and $n \in \mathbb{N}$ we define $R(p^n)$ to be the matrix

$\left( \begin{matrix} \scriptstyle 1 & \scriptstyle1 & \scriptstyle 1 & \scriptstyle\ldots & \scriptstyle 1 & \scriptstyle1 & \scriptstyle1 \\ \scriptstyle-1 & \scriptstyle p-1 & \scriptstyle p-1 & \scriptstyle \ldots & \scriptstyle p-1 & \scriptstyle p-1 & \scriptstyle p-1 \\ \scriptstyle0 & \scriptstyle -p & \scriptstyle p(p-1) & \scriptstyle \ldots & \scriptstyle p(p-1) & \scriptstyle p(p-1) & \scriptstyle p(p-1) \\ \scriptstyle 0 & \scriptstyle 0 & \scriptstyle -p^2 & \scriptstyle \ldots & \scriptstyle p^2(p-1) & \scriptstyle p^2(p-1) & \scriptstyle p^2(p-1) \\ \scriptstyle\vdots & \scriptstyle \vdots & \scriptstyle \vdots & \scriptstyle \ddots & \scriptstyle \vdots & \scriptstyle \vdots & \scriptstyle \vdots \\ \scriptstyle 0 & \scriptstyle 0 & \scriptstyle 0 & \scriptstyle \ldots & \scriptstyle -p^{n-2} & \scriptstyle p^{n-2}(p-1) & \scriptstyle p^{n-2}(p-1) \\ \scriptstyle 0 & \scriptstyle 0 & \scriptstyle 0 & \scriptstyle \ldots & \scriptstyle 0 & \scriptstyle -p^{n-1} & \scriptstyle p^{n-1}(p-1) \end{matrix} \right).$

More generally, if $d$ has prime factorization $p_1^{a_1} \ldots p_s^{a_s}$, we define $R(d) = R(p_1^{a_1}) \otimes \cdots \otimes R(p_s^{a_s})$. The rows and columns of $R(d)$ are labelled by the divisors $D$ of $2^m p^n$, as indicated below for the case $d = 2^3 p$, with $p$ and odd prime.

$R(2^3 p) = \begin{matrix} 1 \\ 2 \\ 2^2 \\ 2^3 \\ p \\ 2p \\ 2^2p \\ 2^3p \end{matrix} \left( \begin{array}{cccc|cccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ -1 & 1 & 1 & 1 & -1 & 1 & 1 & 1 \\ 0 & -2 & 2 &2 & 0 & -2 & 2 & 2 \\ 0 & 0 & -2^2 & 2 & 0 & 0 & -2^2 & 2^2\\ \hline -1 & -1 & -1 & -1 & 1 & 1 & 1 & 1 \\ 1 & -1 & -1 & -1 & -1 & 1 & 1 & 1 \\ 0 & 2 & -2 & -2 & 0 & -2 & 2 & 2 \\ 0 & 0 & 2^2 & -2^2 & 0 & 0 & -2^2 & 2^2 \end{array} \right).$

Say that a partition of $D \backslash \{ d\}$ is coprime if the highest common factor of the numbers in each part is $1$. The aim of the game is to find a non-empty set of rows, $X$ say, of $R(d)$ such that the subsets of columns (excluding column $d$) on which the sum of the rows in $X$ are equal form a coprime partition of the divisors.

There is an application to B-groups only when $d$ is even, in which case we may assume that $2 \in X$. Proposition 6.7 in the paper states that in this case, the only way to win this game when $d = 2^n$, $d = 2^n p$ or $d = 2 p^n$, where $p$ is an odd prime, is to put every single row in $X$. This implies that $C_{2^m p^n}$ is a B-group when $n \le 1$ or $m \le 1$. However the result on the game may well hold more generally.

#### Constant sums for $p^n$

The only coprime partition of $D \backslash \{p^n\}$ has a singleton part, so the row sums are all equal. By adding $p^{e-1}$ to each entry in row $p^e$ for $e \in \{1,\ldots, n\}$, we obtain the matrix below.

$\left( \begin{matrix} \scriptstyle 1 & \scriptstyle1 & \scriptstyle 1 & \scriptstyle\ldots & \scriptstyle 1 & \scriptstyle1 & \scriptstyle1 \\ \scriptstyle 0 & \scriptstyle p & \scriptstyle p & \scriptstyle \ldots & \scriptstyle p & \scriptstyle p & \scriptstyle p \\ \scriptstyle p & \scriptstyle 0 & \scriptstyle p^2 & \scriptstyle \ldots & \scriptstyle p^2 & \scriptstyle p^2 & \scriptstyle p^2 \\ \scriptstyle p^2 & \scriptstyle p^2 & \scriptstyle 0 & \scriptstyle \ldots & \scriptstyle p^3 & \scriptstyle p^3 & \scriptstyle p^3 \\ \scriptstyle\vdots & \scriptstyle \vdots & \scriptstyle \vdots & \scriptstyle \ddots & \scriptstyle \vdots & \scriptstyle \vdots & \scriptstyle \vdots \\ \scriptstyle p^{n-2} & \scriptstyle p^{n-2} & \scriptstyle p^{n-2} & \scriptstyle \ldots & \scriptstyle 0 & \scriptstyle p^{n-1} & \scriptstyle p^{n-1} \\ \scriptstyle p^{n-1} & \scriptstyle p^{n-1} & \scriptstyle p^{n-1} & \scriptstyle \ldots & \scriptstyle p^{n-1} & \scriptstyle 0 & \scriptstyle p^n \end{matrix} \right)$

which still has constant sums over the rows in $X$. Let $x_i = 1$ if $p^i \in X$ and let $x_i = 0$ otherwise. Writing numbers in base $p$, the row sums over $X$ are, for each column,

\begin{aligned} 1 \quad &\quad x_nx_{n-1} \ldots x_3x_2x_0 \\ p \quad &\quad x_n x_{n-1} \ldots x_3x_1x_0 \\ p^2\quad &\quad x_n x_{n-1} \ldots x_2x_1x_0 \\ \vdots \; \quad &\quad \qquad \vdots \\ p^{n-2} \quad &\quad x_nx_{n-2} \ldots x_2x_1x_0 \\ p^{n-1} \quad &\quad x_{n-1}x_{n-2} \ldots x_2x_1x_2. \end{aligned}

(Note in each case there are $n$ digits, the most significant corresponding to $p^{n-1}$.) The numbers in the right column are equal, hence all the $x_i$ are equal and $X = D$, as required. Taking $p=2$ this gives an alternative proof of Proposition 6.7(i).

#### Proofs of further claims on the Ramanujan matrices

Let $R(d)^{\circ}$ denote $R(d)$ rotated by a half turn. The following result was stated without proof in the paper; it implies that each $R(d)$ is invertible, with inverse $\frac{1}{d}R(d)^\circ$. (Update: I later found a much better proof, now outlined in the paper, using a lower-upper decomposition of $R(d)$.)

Proposition. We have $R(p^n)^{-1} = \frac{1}{p^n} R(p^n)^\circ$ and $\det R(p^n) = p^{n(n+1)}/2$.

Proof. Since $R(p^n)^\circ_{p^sp^t} = R(p^n)_{p^{n-s}p^{n-t}}$, we have $R(p^n)^\circ_{p^np^t} = 1$ for all $t \in \{0,\ldots, n\}$ and

\begin{aligned} R(p^n)^\circ_{p^sp^t} &= \begin{cases} (p-1)p^{n-s-1} & n-t \ge n-s \\ -p^{n-s-1} & n-t=n-s-1 \\ 0 & n-t \le n-s-2 \end{cases} \\ &= \begin{cases} (p-1)p^{n-s-1} & s \ge t \\ -p^{n-s-1} & s = t-1 \\ 0 & s \le t-2 \end{cases} \end{aligned}

for $s \in \{0,\ldots, n-1\}$ and $t \in \{0,\ldots,n\}$. We use this to show that

$\sum_{c=0}^n R(p^n)_{p^rp^c} R(p^n)^{\circ}_{p^c p^{r'}} = p^n [r=r']$

for $r,r' \in \{0,\ldots, n\}$. When $r=0$ the first term in each product is $1$, so the left-hand side is the column sum of the $n-r'$-th of $R(p^n)$; this is $p^n$ if $r'=0$ and $0$ otherwise, as required. Now suppose that $r \ge 1$. Since $R(p^n)_{p^rp^c}$ vanishes when $c \le r-2$, the left-hand side is

$-p^{r-1}R(p^n)^\circ_{p^{r-1}p^{r'}} + \sum_{c=r}^n p^{r-1}(p-1) R(p^n)_{p^cp^{r'}}.$

Take out a factor $p^{r-1}$ to define $L$. Substitute for $R(p^n)^\circ_{p^cp^{r'}}$, and split off the summand from $R(p^n)^\circ_{p^np^{r'}} = 1$ to get

\begin{aligned} L &= \begin{cases} (p-1)p^{n-r} & r' \le r-1 \\ -p^{n-r} & r' = r \\ 0 & r' \ge r+1 \end{cases} \\ & \qquad + (p-1) \sum_{c=r}^{n-1} (p-1) \begin{cases} (p-1)p^{n-c-1} & c \ge r' \\ -p^{n-c-1} & c = r'-1 \\ 0 & c \le r'-2 \end{cases} + p-1.\end{aligned}

We must now consider three cases. When $r=r'$ we get

\begin{aligned} L &= p^{n-r} + (p-1)\sum_{c=r}^{n-1} (p-1)p^{n-c-1} + p-1 \\ &= p^{n-r} + (p-1)(p^{n-r}-1) + p-1 \\ &= p^{n-r+1} \end{aligned}

as required. When $r \ge r'+1$ we have $c > r'$ in all summands so

\begin{aligned} L &= -(p-1)p^{n-r} + (p-1)\sum_{c=r}^{n-1} (p-1)p^{n-c-1} + p^{r-1}(p-1) \\ &= (p-1) \bigl( -p^{n-r} + (p^{n-r}-1) + 1 \bigr) \\ &= 0. \end{aligned}

When $r \le r'-1$ the first non-zero summand occurs for $c=r'-1$ so we have

\begin{aligned} L &= - (p-1)p^{n-r'} + (p-1) \sum_{c=r'}^{n-1} (p-1)p^{n-c-1} + p^{r-1}(p-1) \\ &= (p-1) \bigl( -p^{n-r'} + (p^{n-r'}-1) + 1 \bigr) \\ &=0. \end{aligned}

Now taking determinants, using that $\det R(p^n)^\circ = \det R(p^n)$ (the matrices are conjugate by the matrix with $1$s on its antidiagonal and $0$s elsewhere), we get $1 / \det R(p^n) = (p^n)^{n+1} \det R(p^n)$. Hence $\det R(p^n) = p^{n(n+1)/2}$, as required.

### Jordan block matrices.

Let $J$ be the $m \times m$ unipotent upper-triangular Jordan block matrix over $\mathbb{F}_p$. We have $(J-I)^m = 0$, hence $(J-I)^{p^r} = 0$ whenever $p^r \ge m$. On the other hand if $k \le m-1$ then $J^k$ has a $1$ in position $(1,k)$. Therefore $J^{p^r} = I$ if and only if $p^r \ge m$. We also need a result on the relative trace matrix $I + J + \cdots + J^{p^{r}-1}$. Note that $\binom{p}{k}$ is divisible by $p$ for $k \in \{1,\ldots, p-1\}$. (For instance, a $p$-cycle acts freely on the set of $k$-subsets of $\{1,\ldots, p\}$.) An easy inductive argument using $\binom{p-1}{k-1} + \binom{p-1}{k} = \binom{p}{k}$ shows that $\binom{p-1}{k} \equiv (-1)^k$ mod $p$ for all $k$. Now Lucas’ Theorem implies that $\binom{p^r-1}{k} \equiv (-1)^k$ mod $p$. Hence

$(J-I)^{p^r-1} = I + J + \cdots + J^{p^r-1}.$

It follows that the right-hand side is $0$ if and only if $p^r > m$.

## Regular abelian subgroups of permutation groups

March 15, 2017

A B-group is a group $K$ such that if $G$ is a permutation group containing $K$ as a regular subgroup then $G$ is either imprimitive or $2$-transitive. (Regular subgroups are always transitive in this post.) The term ‘B-group’ was introduced by Wielandt, in honour of Burnside, who showed in 1901 that if $p$ is an odd prime then $C_{p^2}$ is a B-group. This is a companion to his important 1906 theorem that a transitive permutation group of prime degree is either solvable or $2$-transitive.

One might imagine that, post-classification, it would be clear which groups are B-groups, but this is far from the case. The purpose of this post is to collect some ancillary results with a bearing on this question.

### Quasiprimitivity

When Burnside’s argument succeeds in proving that $G$ is imprimitive, it does so by showing that the kernel $N$ of an irreducible non-trivial constituent of the permutation character of $G$ is intransitive. The orbits of $N$ are then a non-trivial block system for $G$. Thus $G$ is not even quasiprimitive. That one always gets this stronger result is explained by Corollary 3.4 in this paper by Li. The details are spelled out below.

Claim. If $G$ is a permutation group containing a regular abelian subgroup $K$ then $G$ is primitive if and only if $G$ is quasiprimitive.

Proof. Suppose $B$ is part of a non-trivial block system $\mathcal{B}$ for $G$. Let $L$ be the kernel of the induced action of $K$ on $\mathcal{B}$. The key observation is that $K/L$ acts regularly on $\mathcal{B}$: it acts semiregularly, since $K/L$ is abelian, and since $K$ is transitive, $K/L$ is transitive on $\mathcal{B}$. Similarly, since $K$ is transitive, $L$ is transitive on the block $B$ (given $\alpha, \beta \in B$, there exists $k \in K$ such that $\alpha^k = \beta$; then $B^k = B$ and because $k$ acts regularly on $\mathcal{B}$, we have $k \in L$). So we can factor $K$ as a top part $K/L$, acting regularly on $\mathcal{B}$, and a bottom part $L$ acting regularly on each block. In particular, the kernel of $G$ acting on $\mathcal{B}$ contains $L$ and $L$ has $\mathcal{B}$ as its orbits. Therefore $\mathcal{B}$ is the set of orbits of a normal subgroup of $G$, and $G$ is not quasiprimitive. $\Box$

Dropping the condition that $K$ be abelian, one finds many imprimitive but quasiprimitive groups: they can be obtained from factorizations $G = HK$ of a finite simple group $G$ where $H \cap K = 1$ and $H$ is not maximal. One nice example is $A_7 = F_{21}S_5$ where $F_{21}$ is the transitive Frobenius group of order $21$ inside $A_7$ and $S_5$ is generated by $(1,2,3,4,5)$ and $(1,2)(6,7)$. Here $F_{21}$ is not maximal because it is a subgroup of $\mathrm{GL}_3(\mathbb{F}_2)$ in its action on the $7$ non-zero vectors of $\mathbb{F}_2^3$. For an easier example, take $A_5 = \langle (1,2,3,4,5) \rangle A_4$.

### Factorizable groups

Say that a finite group $K$ is factorizable if there exists $t > 1$ and groups $K_1, \ldots, K_t$ such that $K \cong K_1 \times \cdots \times K_t$ where $|K_1| = \ldots = |K_t| \ge 3$. If $K$ is factorizable with $|K_i| = m$ for each $i$, then, since each $K_i$ acts as a regular subgroup of $S_m$, $K$ is a regular subgroup of $S_m \wr S_t$ in its primitive action on $\{1,\ldots,m\}^t$. Therefore no factorizable group is a B-group. This example appears as Theorem 25.7 in Wielandt Permutation Groups.

### Affine groups

An interesting source of examples is affine groups of the form $G = V \rtimes H$ where $V = \mathbb{F}_p^n$ for some prime $p$ and $H \le \mathrm{GL}(V)$. Here $V$ acts by translation on itself and $H$ is the point stabiliser of $0$. Any non-trivial block is invariant under the action of $V$ and so is a linear subspace of $V$. Therefore $G$ is primitive if and only if $H$ acts irreducibly on $V$. The action of $G$ is 2-transitive if and only if the point stabiliser $H$ is transitive. Therefore if there exists a linear group $H$ acting irreducibly but not transitively on $\mathbb{F}_p^n$, then $C_p^n$ is not a B-group.

#### Symmetric group representations

Consider the symmetric group $S_n$ acting on $\langle v_1, \ldots, v_n \rangle$ by permutation matrices. Let $V = \langle v_i - v_j : 1 \le i 2$ and $n \ge 2$ then the orbit of $v_1-v_2$ does not contain $v_2-v_1$, and hence $C_p^n$ is not a B-group in these cases. If $p = 2$ and $n \ge 4$ then the orbit of $v_1+v_2$ does not contain $v_1+v_2+v_3+v_4$. Therefore $C_2^m$ is not a B-group when $m$ is even and $m \ge 4$.

#### Exotic regular abelian subgroups of affine groups

An interesting feature of these examples, noted by Li in Remark 1.1 following the main theorem, is that $V \rtimes H$ may have regular abelian subgroups other than the obvious translation subgroup $V$. Let $t_v : V \rightarrow V$ denote translation by $v \in V$.
Take $n=2r+1$, fix $s \le r$, and consider the subgroup

$K = \langle (2,3)t_{v_1+v_2}, \ldots, (2s,2s+1)t_{v_1+v_{2s}}, t_{v_{2s+2}}, \ldots, t_{v_{2r+1}} \rangle$.

By the multiplication rule

$h t_v h' t_{v'} = h h' t_{vh' + v'}$

we see that $(2t,2t+1)t_{v_1+v_{2t}}$ has square $t_{v_{2t}+v_{2t+1}}$ and that the generators of $K$ commute. Therefore $K \cong C_4^s \times C_2^{2(r-s)}$, and no group of this form, with $r \ge 2$ is a B-group. (Since these groups are factorizable, this also follows from Wielandt’s result above.)

Li’s paper includes this example: the assumption that $n$ is odd, needed to ensure that $V$ is irreducible, is omitted. In fact it is an open problem to decide when $C_2^n$ is a B-group.

Perhaps surprisingly, this example does not generalize to odd primes. To see this, we introduce some ideas from an interesting paper by Caranti, Della Volta and Sala. Observe that if $K$ is a regular abelian subgroup of $G$ then for each $v \in V$, there exists a unique $g_v \in K$ such that $0g_v = v$. There exists a unique $h_v \in H$ such that $g_v = h_v t_v$. By the multiplication rule above we have

$h_u t_u h_v t_v = h_u h_v t_{uh_v + v} = h_vh_u t_{vh_u+u} = h_vt_vh_ut_u$

for all $u, v \in V$. Therefore $\{h_v : v \in V\}$ is an abelian subgroup of $H$ and $uh_v + v = vh_u + u$ for all $u,v \in V$. Replacing $v$ with $v+w$, we have

\begin{aligned} uh_{v+w} + (v+w) &= (v+w)h_u + u \\ &= vh_u + wh_u + u \\ &= uh_v + v + uh_w + w - u \end{aligned}

and so, cancelling $v+w$, we get the striking linearity property

$h_{v+w} = h_v + h_w - \mathrm{id}$.

Equivalently, $h_{v+w}-\mathrm{id} = (h_v-\mathrm{id}) + (h_w-\mathrm{id})$. Since $(h_v - \mathrm{id})(h_w - \mathrm{id}) = (h_vh_w - \mathrm{id}) - (h_v - \mathrm{id}) - (h_w - \mathrm{id})$, it follows that the linear maps $\{h_v - \mathrm{id} : v \in V \}$ form a subalgebra of $\mathrm{End}(V)$. (This is essentially Fact 3 in the linked paper.)

#### Abelian regular subgroups of odd degree affine symmetric groups

Suppose that $K$ is a regular abelian subgroup of $V \rtimes S_n$ and that there exists $v \in V$ such that $h_v \not= \mathrm{id}$. The matrix $M$ representing $h_v$ in the basis $v_2-v_1, \ldots, v_n-v_1$ of $V$ is a permutation matrix if $1 h_v = 1$. If $1h_v = a > 1$ and $bh_v = 1$ then from

$(v_i - v_1)h_v = (v_{ih}-1) - (v_a-v_1)$

we see that $M$ has $-1$ in each entry in the column for $v_a-v_1$, and the only other non-zero entries are a unique $1$ in the row for $v_i-v_1$, for each $i \not= b$. For example, $(1,2,3,4)$ is represented by

$\left( \begin{matrix} -1 & 1 & 0 \\ -1 & 0 & 1 \\ -1 & 0 & 0 \end{matrix} \right).$

By the linearity property above, $h_{2v} = 2h_v - \mathrm{id}$. But if $p > 2$ then $2M - I$ is not of either of these forms. Therefore $V$ is the unique regular abelian subgroup of $V \rtimes S_n$.

Suppose that $p = 2$. Suppose that $h_v$ has a cycle of length at least $4$. By relabelling, we may assume this cycle is $(1,2,\ldots,a)$ where $a$ is a 2-power. The matrix representing $h_v$ has $-1$ entries in column $2$, and the matrix representing $h_v^{-1}$ has $-1$ entries in column $a$. Therefore the matrix representing $h_v + h_v^{-1} + \mathrm{id}$ has $-1$ entries in both columns $2$ and $a$, and so is not of the permitted form. It follows that, when $p=2$ and $n=2r+1$ is odd, the only abelian regular subgroups of $V \rtimes S_n$ are isomorphic to $C_4^s \times C_2^{2r-2s}$. (In fact it seems they are precisely the subgroups constructed above.)

#### Abelian regular subgroups of even degree affine symmetric groups

Now suppose that $n$ is even. Let $U = V / \langle v_1 + \cdots + v_n \rangle$ and consider $U \rtimes S_n$. When $n=4$ the action of $S_4$ is not faithful: after factoring out the kernel $\langle (1,2)(3,4), (1,3)(2,4)\rangle$ we get $\mathbb{F}_2^2 \rtimes S_3 \cong S_4$, which has abelian regular subgroups $C_2 \times C_2$ and $C_4$. When $n=6$, there is an abelian regular subgroup isomorphic to $C_8 \times C_2$, generated by $t_{v_1+v_3}(3,4,5,6)$ and $t_{v_1+v_2}$. The obstruction seen above does not apply: for example, in the basis $v_1+v_3, v_1+v_4,v_1+v_5,v_1+v_6$, we have

$(3,4,5,6) + (3,6,5,4) + \mathrm{id} \mapsto \left( \begin{matrix} 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \end{matrix} \right)$

which is the matrix representing $(1,2)(3,6,5,4)$, thanks to the relations present in the quotient module. However, in this case the action of $S_6$ on $\mathbb{F}_2^4$ is transitive (any element of $U$ is congruent to some $v_i + v_j$) and in fact $C_8 \times C_2$ is a B-group. (A related, remarkable fact, is that the action of $A_6$ on $U$ extends to a $2$-transitive action of $A_7$, giving an example of a $3$-transitive affine group, $U \rtimes A_7$.) A computer calculation shows that, up to conjugacy, there are also three abelian regular subgroups of $U \rtimes S_n$ isomorphic to $C_4 \times C_4$ and two isomorphic to $C_4 \times C_2 \times C_2$. If $n \ge 8$ then a similar argument to the odd degree case shows that any abelian regular subgroup has exponent at most $4$, so we get no new examples.

#### Elementary abelian subgroups other than $V$

The following lemma has a simple ad-hoc proof.

Lemma. If $n < p$ then the only regular abelian subgroups of $V \rtimes \mathrm{GL}(V)$ are elementary abelian.

Proof. Suppose that $K$ is an elementary abelian subgroup of $V \rtimes \mathrm{GL}(V)$. Let $h_v t_v \in K$. Since $h_v - 1$ is a nilpotent $n \times n$-matrix and $n \textless\; n$ we have $(h_v - 1)^p = 0$ The $p$-th power of $h_v t_v \in V$ is therefore $t_w$ where $w = v + vh_v + \cdots + vh_v^{p-1}$. Since each Jordan block in $h_v$ has size at most $p-1$, we have $w=0$. Therefore $K$ has exponent $p$. $\Box$

Note however that there exist elementary abelian subgroups other than the obvious $V$ whenever $n \ge 2$. Possibly they can be classified by the correspondence with nil-algebras in the Caranti, Della Volta, Sala paper.

#### Algebra groups

Given $n \in \mathbb{N}$ and a field $F$, define an algebra group to be a subgroup of $\mathrm{GL}_n(F)$ of the form $\{I + X : X \in A \}$ where $A$ is a nilalgebra of $n \times n$ matrices. (We may assume all elements of $A$ are strictly upper triangular.) The subalgebra property above shows that any abelian regular subgroup of an affine group of dimension $n$ over $\mathbb{F}_2$ is an extension

$1 \rightarrow C_2^r \hookrightarrow K \twoheadrightarrow \{I + X : X \in A \} \rightarrow 1$

of an algebra group by an elementary abelian 2-group. If $F$ has characteristic $2$ then, since

$(I+X)(I+Y) = (I+XY) + (I+X) + (I+Y)$

by the dual of the calculation above, a subgroup $G$ of $\mathrm{GL}_n(F)$ is an algebra group if and only if $\{ I + g : g \in G \}$ is additively closed.

An exhaustive search shows that if $n \le 4$ then every 2-subgroup of $\mathrm{GL}_n(\mathbb{F}_2)$ is an algebra group; note it suffices to consider subgroups up to conjugacy. But when $n = 5$ there are, up to conjugacy, 110 algebra subgroups of $\mathrm{GL}_5(\mathbb{F}_2)$, and 66 non-algebra subgroups, of which 34 are not isomorphic to an algebra subgroup. Of these:

• 1 is abelian, namely $C_8$;
• 4 are nilpotent of class 2, namely $\langle x, c : x^8 = c^2 = 1, x^c = x^5 \rangle$, $\langle x, y, c : x^4 = y^2 = c^4 = 1, x^c = xy, y^c = y \rangle$, $\langle x, y, c : x^2 = y^2 = c^8 = 1, x^c = xy, y^c = y \rangle$, $\langle x,y,c : x^4 = y^2 = c^4 = 1, x^c = xy, y^c = y\rangle$;
• 17 are nilpotent of class 3;
• 12 are nilpotent of class 4.

The appearance of $C_8$ is explained by the following lemma, which implies that there is an algebra group isomorphic to $C_{2^m}$ if and only if $m \le 2$.

Lemma. Let $g \in \mathrm{GL}_n(\mathbb{F}_2)$ have order $2^m$. Then $\langle g \rangle$ is an algebra group if and only if all Jordan blocks in $g$ have dimension at most $3$.

Proof. Let $1 + X$ be a Jordan block of $g$ of dimension $d$ and order $2^m$. The subalgebra of $d\times d$-matrices generated by $X$ has dimension $d-1$, and so has size $2^{d-1}$. Therefore if $\langle g \rangle$ is an algebra group then $2^{d-1} \le 2^m$. Hence $d-1 \le m$. On the other hand, since $X^{d-1} \not=0$, if $2^r < d$ then $(1+X)^{2^r} \not=0$, and so the order of $1+X$ is the minimal $s$ such that $2^s \ge d$. Hence $2^{m-1} < d$. Combining these inequalities we get

$2^{m-1} < d \le m+1$

and so $m \le 2$, and, since $d-1 \le m$, we have $d \le 3$. The converse is easily checked. $\Box$.

## Sylow subgroups of symmetric groups

November 27, 2016

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.