Yet another post on simplicity

I see that I finally arrive to an end of my journey in formalizing in Lean the simplicity of the alternating group in 5 letters or more, so it may be a good time to summarize what I did, from the mathematical side. 

On a first blog post, “Not simple proofs of simplicity”, I had described my initial plan, but it was not clear at that time that I would either arrive at a final proof, nor that I would be able to formalize it in Lean. In fact, a few weeks after I had started this experiment, I doubted I would make it and went on formalizing the traditional proof that the alternating group is simple. I added a few simplifications—which I was later told were already explained in Jacobson's Basic Algebra, say that's life…– leading to “The very simple proof that the alternating groups of five letters (or more) is simple”. I managed to formalize that proof at the end of 2021, and spent a lot of energy of the 8 next months to formalize the proof that I initially had in mind.

As I had already explained, the goal/constraint is to apply the Iwasawa criterion to the alternating group. This criterion says that if a group $G$ acts primitively on a set $X$, and if we attach to each point $x\in X$ a commutative subgroup $Tx$ of $G$, in such a way that $T(g\cdot x)=g\cdot Tx\cdot g^{-1}$ for every $g\in G$ and every $x\in X$, and if the subgroups $Tx$ generate $G$, then every normal subgroup of $G$ that acts nontrivially on $X$ contains the commutator subgroup. We take $G=\mathfrak A_n$. For $n\geq 5$, its commutator subgroup is $\mathfrak A_n$ itself (for example because any two 3-cycles are conjugated; in particular, a 3-cycle is conjugate to its square, which implies that it maps to $1$ in the abelianization of $\mathfrak A_n$). So we need to get primitive actions of $\mathfrak A_n$ and commutative subgroups. 

One of the equivalent criteria for primitivity of a transitive actions is that the stabilizers of points are maximal subgroups. As I had explained at the end of the first post, the maximal subgroups of $\mathfrak S_n$ and $\mathfrak A_n$ are known by the O'Nan–Scott theorem, combined with its converse which is a theorem of Liebeck, Praeger and Saxl. These theorems give a precise list of the maximal subgroups of $\mathfrak S_n$ and $\mathfrak A_n$, of which the first entry is precisely $\mathfrak S_p\times \mathfrak S_{n-p}$ (where the first factor acts on $\{1;\dots;p\}$ and the second acts on $\{p+1;\dots;n\}$) and its intersection with $\mathfrak A_n$, if $0<p<n$ and $n\neq 2p$.

We need to understand the limitation $n\neq 2p$, the point being that if $n=2p$, the subgroup $\mathfrak S_p\times\mathfrak S_p$ is not maximal in $\mathfrak S_{2p}$, it is a subgroup of index 2 of a “wreath product” obtained by adding one permutation that exchanges the two blocks $\{1,\dots,p\}$ and $\{p+1,\dots,2p\}$, for example $(1\,p+1)(2\,p+2)\dots (p\,2p)$. This group is the second entry in the O'Nan–Scott theorem.

These two entries are labelled as intransitive and imprimitive respectively, because $\mathfrak S_p\times \mathfrak S_{n-p}$ has two orbits on $\{1;\dots;n\}$, while the wreath product is transitive but it preserves the partition consisting of the two blocks $\{1,\dots,p\}$ and $\{p+1,\dots,2p\}$.

These two entries seem to be obvious to the group theorists. It is given without proof in the paper of Liebeck, Praeger and Saxl.

The case of $\mathfrak S_n$ is easy, and occupies a subsection of Wilson's book on Finite Simple Groups. It is even funny to prove by hand, and not so hard to formalize in Lean. Take a subgroup $K$ of $\mathfrak S_n$ such that $\mathfrak S_p\times \mathfrak S_{n-p} \subsetneq K$ and let us prove that $K=\mathfrak S_n$.  To that end, it suffices to show that $K$ contains any transposition $(a\,b)$. This is obvious if both $a$ and $b$ belong to $\{1;\dots;p\}$ or if they both belong to $\{p+1;dots;n\}$, so assume that $a\in\{1;\dots;p\}$ and $b\in\{p+1;\dots;n\}$. Since $K$ does not stabilize $\{1;\dots;p\}$, there is $x\in\{1;\dots;p\}$ and $k\in K$ such that $y=k\cdot x \in\{p+1;\dots;n\}$. If $n>2p$, there exists $z\in\{p+1;\dots;n\}$ such that $z\neq y$ and $t=k^{-1}\cdot z\in\{p+1;\dots;n\}$; from the relation $k^{-1} \cdot (y\,z) \cdot k=(x\,t)$ and the fact that $(y\,z)\in \mathfrak S_p\times\mathfrak S_{n-p}$, we deduce that $(x\,t)$ belongs to $K$. This gives us one transposition of the desired form; finally, the relation $(a\,b)=h (x\,t) h^{-1}$ with $h=(x\,a)(t\,b)\in\mathfrak S_p\times\mathfrak S_{n-p}$ shows that $(a\,b)\in K$. The other case, $n<2p$ is symmetric.

Bizarrely, the analogous result for the alternating group looked more difficult to me, although some colleague assured me that it could be done, an other one that I could certainly do it, and a last one did it for $n>7$. Since Liebeck, Praeger and Saxl gave no reference at all, I asked Liebeck about and he explained me a short proof that uses totally different ideas.

Let $G=\mathfrak A_n$ or $\mathfrak S_n$ and consider a subgroup $K$ such that $(\mathfrak S_p\times\mathfrak S_{n-p})\cap G \subsetneq K\subseteq G$; we wish to prove that $K=G$. Arguments as given above already show that $K$ acts transitively on $\{1;\dots;n\}$. But we can do more: it acts primitively. Now, one just needs to invoke a 1870 theorem of Jordan: a primitive subgroup of $\mathfrak S_n$ that contains a transposition is $\mathfrak S_n$, and a primitive subgroup of $\mathfrak S_n$ that contains a 3-cycle contains $\mathfrak A_n$!

To prove that $K$ acts primitively, it is convenient to use the standard definition of a primitive action. If a group $G$ acts on a set $X$, call block of the action a nonempty subset $B$ of $X$ which, for every $g\in G$, is either fixed or moved to a disjoint subset by $G$; it follows from the definition that the translates of a block by the action form a partition of $X$. Singletons are blocks, the full subset is a block, and one definition of a primitive action is that the only blocks are these trivial ones (and $X$ is nonempty). Orbits are blocks, so that a primitive action is transitive. Conversely, one can prove that if the action is transitive, then it is primitive if and only if stabilizers of points in $X$ are maximal subgroups. A more general result is that for every point $a\in X$, associating with a set $B$ its stabilizer $G_B$ gives a bijection from the set of blocks that contain $a$ to the set of subgroups of $G$ that contain $G_a$, with inverse bijection associating with a subgroup $K$ containing $G_a$ the orbit $K\cdot a$, and these bijections preserve inclusion. 

Proof. — Let $B,B'$ be blocks such that $B\subseteq B'$ and let $g\in G_B$; then $g\cdot B'$ contains $g\cdot B=B$, hence $g\cdot B'$ is not disjoint from $B'$, so that $g\cdot B'=B'$ by definition of a block. This proves that $G_B$ is a subgroup of $G_{B'}$.

Let $B$ be a block that contains $a$; then $G_B \cdot a=B$. Indeed, the inclusion $G_B\cdot a\subseteq B$ follows from the definition of $G_B$. To prove the other inclusion, let $b\in B$. Since the action is transitive, there exists $g\in G$ such that $g\cdot a=b$; then $g\cdot B$ and $B$ both contain $b$, hence $g\cdot B=B$, so that $g\in G_B$ and $b\in G_B\cdot a$.

Finally, let $K$ a a subgroup of $G$ containing $G_a$ and let $B=K\cdot a$. Let us prove that $B$ is a block such that $K=G_B$. Let $g\in G$ such that $g\cdot B$ and $B$ are not disjoint; let $b,c\in B$ be such that $b=g\cdot c$; write $b=k\cdot a$ and $c=h\cdot a$ for $k,h\in K$. Then $k\cdot a = gh\cdot a$ so that $k^{-1}gh\in G_a$, hence $k^{-1}gh\in K$; we conclude that $g\in K$, hence $g\cdot B=gK\cdot a = K\cdot a=B.$ So $B$ is a block. This also shows that $G_B\subseteq K$, and the converse inclusion is obvious.

Going back to our initial problem, it remains to show that the action of $K$ on $\{1;\dots;n\}$ only has trivial blocks. The proof uses two remarks.

1. The trace of a block on $\{1;\dots;p\}$, respectively $\{p+1;\dots;n\}$, is either a singleton, or all of it. Indeed, this trace is a block for the induced action of $(\mathfrak S_p\times\mathfrak S_{n-p})\cap G$ on $\{1;\dots;p\}$ (respectively $\{p+1;\dots;n\}$), and this action contains that of $\mathfrak A_p$ (respectively…) and even that of $\mathfrak S_p$ if $p\neq n-1$. On the other hand, the symmetric group acts 2-transitively, hence primitively.  (The cases $p=1$ or $p=n-1$ need minor adjustements.)
   
2. If $2p<n$, then no nontrivial block can contain $\{p+1;\dots;n\}$. Indeed, there is not enough space in the complementary subset so that disjoint translates of this block make a partition of $\{1;\dots;n\}$.

Let us now conclude the proof. (I still find the following argument a bit convoluted but have nothing really better to propose yet.) Consider a block $B\subset\{1;\dots;n\}$ for the action of $K$, and assume that $B$ is not a singleton, nor the full set. If $B$ meets $\{p+1;\dots;n\}$ in at least two elements, then it contains $\{p+1;\dots;n\}$, hence is the full block, a contradiction. If $B$ meets $\{1;\dots;p\}$ in at least two elements, then it contains $\{1;\dots;p\}$, and some disjoint translate of it  is contained in $\{p+1;\dots;n\}$; this translate is a block that contains $\{p+1;\dots;n\}$, hence is the full set, so that the initial block is the full set as well.  By similar arguments, $B$ meets both $\{1;\dots;p\}$ and $\{p+1;\dots;n\}$ in exactly one element, and the same hold for any translate $k\cdot B$ of $B$. However, using the hypothesis that $p\neq n-p$ and that $K$ strictly contains $(\mathfrak S_p\times\mathfrak S_{n-p})\cap G$, we find $k\in K$ such that $k\cdot B$ meets $\{p+1;\dots;n\}$ in at least two elements, and we can conclude as earlier that $B$ is the full set.

To terminate this blog spot, I need to say something about Jordan's theorem. Jordan was concerned about the concept multiple transitivity: a group $G$ acting on a set $X$ is $m$-transitive if whenever systems of distinct elements $a_1,\dots,a_m$ on the one side, $b_1,\dots,b_m$ on the other side, are given, there exists $g\in G$ such that $g\cdot a_1=b_1,\dots g \cdot a_m=b_m$ (one assumes here that $m\leq {\mathrm{Card}(X)}$). Many theorems from this time (Matthieu, Bertrand, Serret, Jordan…), partly in relation with Galois theory of equations, aim at limiting the multiple transitivity of subgroups of the symmetric group. The symmetric group itself is $n$-transitive, if $n={\mathrm {Card}(X)}$, the alternating group is $(n-2)$-transitive, and other subgroups have to be much less transitive.

The general result of Jordan, proved in the Note C (page 664) to §398 of his Traité des substitutions et des équations algébriques (1870, Gauthier-Villars)  is that a primitive subgroup of $\mathfrak S_n$ containing a cycle of prime order $p$ is $n-p+1$-transitive. For $p=2$, we get that this subgroup is $(n-1)$-transitive, hence is $\mathfrak S_n$; for $p=3$, we get that it is $(n-2)$-transitive, and that implies that it contains the alternating group $\mathfrak A_n$. I formalized these results in Lean, following the presentation of Wielandt's book on Finite permutation groups (theorem 13.3 of that reference). A later theorem of Jordan (1873; see theorem 13.9 in Wielandt's book) asserts that such a subgroup always contains the alternating group provided $n-p\geq 3$; I have not (not yet?) formalized it in Lean.

All in all, this gives a fairly sophisticated proof that the alternating group is simple. One of its merit is to follow a general line, that applies to many other groups. In particular, Iwasawa's criterion is also used by Wilson in his book Finite simple groups to prove that the simplicity of the Mathieu groups $M_{11}, M_{12}$, and of many other finite groups.

I just opened Jordan's book to write this blog post. Let me add that it contains (§85) another proof of simplicity of the alternating group, and I will try to explain it in a later post.