Tuesday, September 13, 2022

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.

Tuesday, December 21, 2021

The very simple proof that the alternating group on 5 letters (or more) is simple

\( \def\supp {\operatorname{supp}} \)

As explained in the previous post, I wanted to formalize the proof that the alternating group on 5 letters or more is simple, using the Iwasawa criterion. This formalization is in the middle of nowhere, because it requires a proof that the natural action of the alternating group $A_n$ on $k$-elements subsets of $\{1,\dots,n\}$ is primitive, provided $n\neq 2k$, $k\neq 0,n$ and $n\geq 5$.

A simple proof

There is a simple, slightly computational proof that the alternating group of 5 letters (or more) is simple, it is explained in many textbooks, for example in James Milne's Group theory notes. However, its formalization is not so easy, because even Milne has a lot of implicit stuff.

The situation, as in Lemma 4.36 of Milne's booklet, is the following.

One is given a nontrivial normal subgroup $N$ of $A_n$ and one wishes to prove that $N=A_n$. We know that the 3-cycles generate $A_n$. We also know that 3-cycles are pairwise conjugate in the symmetric group, and also, using $n\geq 5$, in the alternating group $A_n$. Consequently, it suffices to prove that $N$ contains a 3-cycle. To that aim, one argues by induction on the cardinality of the support $\supp(g)$ of a nontrivial element $g$ of $N$. 

Here is an attempt at presenting the induction argument in a way which is as straightforward as possible.

Since $g\neq 1$, $\supp(g)$ has cardinality $\geq 2$.

If $\supp(g)$ has cardinality $2$, then $g$ is a transposition, contradicting the hypothesis that $g$ belongs to the alternating group. So the support of $g$ has cardinality $\geq 3$.

If $\supp(g)$ has cardinality $3$, then $g$ is a 3-cycle, and we are done. So we may assume that the support of $g$ has cardinality $\geq 4$.

Let us choose an element $a\in\{1,\dots,n\}$ which belongs to the largest cycle of $g$ and set $b=g(a)$; by assumption, one has $b\neq a$. The proof consists in considering an element $c\in\{1,\dots,n\}$ such that $c\neq a$ and $c\neq b$, the 3-cycle $h=(a\,b\,c)$ and the conjugate $g'=h g h^{-1}$. 

Since $h$ is a 3-cycle, it belongs to the alternating group; since $N$ is normal, one has $g'\in N$.

We wish to apply the induction hypothesis to the element $g' g^{-1}$ of $N$. So we need to prove

  1. $g'\neq g$, and
  2. The support of $g' g^{-1}$ has cardinality strictly smaller than the one of $g$.

To guarantee (1), that $g'\neq g$, it suffices to choose $c$ such that $g'(b)\neq g(b)$. But \[ g'(b) = hgh^{-1}(b) = hg(a) = h(b) = x, \] so the new assumption we make is that $c\neq g(b)$.

The rest of the argument is devoted to finding appropriate conditions on $c$ that guarantee (2). First, observe the inclusion $\supp(g'g^{-1})\subset g(\supp(h))\cup \supp(h)$, which is proved by contraposition. Indeed, if $x$ does not belong to the right hand side, then $g^{-1}(x) \notin \supp(h)$, hence $h^{-1}g^{-1}(x)=g^{-1}(x)$ (for example, using that $\supp(h)=\supp(h^{-1})$), and then $g' g^{-1}(x)=hgh^{-1}(g^{-1}(x))=hg(g^{-1}(x))=h(x)=x$, since $x\not\in h(x)$. This proves that the cardinality of the support of $g'g^{-1}$ is at most 6.

However, since $g(a)=b$ belongs both to $g(\supp(h))$ and to $\supp(h)$, the cardinality is at most 5. Explicitly, $\supp(g'g^{-1})\subset \{a,b,c,g(b), g(c)\}$. In particular, a clever choice for $c$ is only needed when $\supp(g)$ has cardinality 4 or 5!

To conclude in the remaining cases, we remark that there are only two possibilities for the cycle-type of $g$: it can only be $(5)$ or $(2,2)$, since it is an alternating permutation, and we split the discussion according to these two cases:

  • If the cycle-type of $g$ is $(5)$, then we choose for $c$ the “last” element of the cycle of $a$, namely $c=g^{-1}(a)$. Then, $g(c)=a$, so that $\supp(g'g^{-1})\subset\{a,b,c,g(b)\}$ which has at most 4 elements.
  • If the cycle-type of $g$ is $(2,2)$, then we have $g(b)=a$ and we choose for $c$ any fixed point of $g$. Then $\supp(g'g^{-1})\subset\{a,b,c\}$ has at most 3 elements.

About the formalization

One annoying part for formalizing this argument is the elimination of cycle-types. One would like that a computer assistant is able to list all possible cycle-types of a given size. Presumably it can, by I cannot (yet), so I need to do the argument by hand, for that specific value.

In principle, that argument needs to be spelt out in class too. We use two formulas:

  1. The sum of the length of the cycles is the cardinality of the support, hence $4$ or $5$ in this case.
  2. The signature of a permutation is even if and only if the number of cycles and the cardinality of the support have the same parity.

One way to write it down consists in taking the length $m$ of the smallest cycle of $g$. One has $m\geq 2$ by assumption.

  1. If there are no other cycles, then the cycle-type of $g$ is $(m)$. Then $m=4$ or $5$, and only $(5)$ respects the parity constraint.
  2. Otherwise, there is only one other cycles, otherwise the sum of their lengths would be at least $3\cdot 2\geq 6$. If $m'$ is the length of that other cycle, one has $2\leq m\leq m'$. Then $2m\leq m+m'\leq 5$, hence $m\leq 2$, so that $m=2$. This gives $m'\leq 3$, giving two cycle-types $(2,3)$ and $(2,2)$, of which the second one only satisfies the parity constraint.

Monday, December 13, 2021

Not simple proofs of simplicity

The last few weeks, I started my self-education in proof formalization (in Lean) by a test case, the simplicity of the alternating group. In this blog post, I want to discuss some aspects of the underlying mathematics which I think I learnt during the formalization process.

Simple groups. Some examples

This is about groups, eventually finite groups. Let us recall that a subgroup $N$ of a group $G$ is normal if for every $g \in G$ and $n\in N$, one has $gng^{-1}\in N$. Concretely, this means that the two equivalence relations modulo $N$ (left or right) coincide, and that the quotient set $G/N$ inherits a group structure that makes the natural projection $G \to G/N$ a morphism of groups.

In this setting, the group $G$ can be viewed as an extension of the two groups $G/N$ and $N$, which are possibly simpler, and this extension may help at understanding properties of the group $G$. At the opposite, one says that $G$ is simple if it has no normal subgroup besides $\{e\}$ and $G$ itself (and if $G\neq\{e\}$).

Trivial examples of normal subgroups of a group $G$ are $\{e\}$ and $G$ itself. Less trivial examples are the center $Z(G)$ of $G$ (those elements $g$ such that $gh=hg $ for all $h\in G$), and the derived subgroup $D(G)$, the subgroup generated by all commutators $ghg^{-1}h^{-1}$. This commutator subgroup is interesting: any subgroup $N$ of $G$ containing the commutator subgroup $D(G)$ is normal, and the quotient is abelian; and conversely.

The kernel of a group morphism is a normal subgroup, and the construction of a quotient shows that all normal subgroups appear in this way. In particular, the alternating group $A_n$ is a normal subgroup of the symmetric group $S_n$.

A simple group has either $Z(G)=\{e\}$ or $Z(G)=G$; in the latter case, this means that $G$ is commutative, and it quickly appears that $G$ has to be finite of prime order. Consequently, our discussion will now concern groups with trivial center.

The concept of simplicity of groups is classically presented in connection with Galois theory, and the question of solvability of equations by radicals. Namely, a “general” polynomial equation of degre $n$ has $S_n$, the full symmetric group on $n$ elements, for its Galois group, and, if $n\geq 5$, the only possible dévissage of this group consists in introducing the alternating group $A_n$ of even permutations, the subgroup $A_n$ being normal and simple. On the other hand, the solvability of polynomial equation by radicals is equivalent to such a dévissage where all successive quotients are cyclic groups (equivalently abelian groups). Since $A_n$ is not abelian, this implies that a “general” polynomial equation of degree $n$ is not solvable by radicals. However, using simplicity of the alternating group is much stronger than what we need: what would be needed is solvability of the symmetric group, and that this does not hold if $n\geq 5$ is much simpler. Consequently, for the problem of resolution by radicals, it suffices to prove that the derived subgroup $D(A_n)$ of the alternating group is equal to $A_n$.

Theorem. — For $n\geq 5$, one has $D(A_n)=A_n$. In particular, the alternating group and the symmetric group on $n$ letters are not solvable.
I give two (equivalent) proofs, the second one being a computational interpretation of the first one. Both use that the 3-cycles generate $A_n$ and are conjugate in $A_n$. The computational proof is shorter, arguingly simpler. As a matter of fact, I never understood it, nor could remember it, until I translated the conceptual proof into the proof assistant.
Consider the morphism $p\colon A_n\to A_n/D(A_n)$. Since $A_n/D(A_n)$ is commutative, all 3-cycles have the same image. Since the square of a 3-cycle is again a 3-cycle, both have the same image. This implies that for every 3-cycle $g\in A_n$, one has $p(g)=p(g^2)$, hence $p(g)=e$. Since the 3_cycles generate $A_n$, the morphism $p$ is trivial; since it is surjective, one has $A_n/D(A_n)=\{e\}$ and $D(A_n)=A_n$.
Computationally, consider a 3-cycle $g$ and its square $g^2$. Since they are conjugate, there exists $h\in A_n$ such that $g^2=hgh^{-1}$. Then $g=hgh^{-1}g^{-1}$, so that $g$ is a commutator; in particular, $D(A_n)$ contains all commutators and $D(A_n)=A_n$.

The remaining cases, for $n\leq 4, are interesting, but classically left as exercises in text books:

  1. One has $A_1=S_1=\{e\}$;
  2. The group $S_2$ is the cyclic group of order 2, hence is simple and solvable, and $A_2$ is trivial;
  3. The group $S_3$ is a noncommutative group of order 6, and $A_3$ is a cyclic group of order 2.
  4. The groups $S_4$ and $A_4$ are noncommutative and solvable, of orders 24 and 12. The derived subgroups $D(S_4)$ and $D(A_4)$ are both equal to the Klein subgroup $V_4$ of $S_4$, consisting of the permutations of the form $(ab)(cd)$ for $a,b,c,d$ any enumeration of $1,2,3,4$ — “double transpositions” – and of the identity. The group $V_4$ is commutative, isomorphic to $(\mathbf Z/2\mathbf Z)^2$, and the quotient $D(A_4)/V_4$ is cyclic of order $3$.

Another classical series of simple groups appears in linear algebra. Let $F$ be a field and let $n$ be an integer such that $n\geq 2$. The group $\mathrm{GL}(n,F)$ of $n\times n$ invertible matrices is not simple, for it is noncommutative but its center consists of homotheties; we can try to mod out by the center, getting the group $\mathrm{PGL}(n,F)=\mathrm{GL}(n,F)/F^\times$ but that one may not be simple. Indeed, another reason for $\mathrm{GL}(n,F)$ not to be simple is that it admits the special linear group $\mathrm{SL}(n,F)$, kernel of determinant, as a normal subgroup. The group $\mathrm{SL}(n,F)$ has a nontrivial center in general, it consists of homotheties of ratio $a\in F^\times$ such that $a^n=1$ — let us denote it by $\mu_n$. But the quotient $\mathrm{PSL}(n,F)=\mathrm{SL}(n,F)/\mu_n$ is simple in general — in general meaning that is is always the case but for two exceptions:

  1. $n=2$ and $F=\mathbf F_2$. Then $\mathrm{PSL}(2,\mathbf F_2)\simeq S_3$ (by the action on $\mathbf P_1(\mathbf F_2)$, see below), hence is not simple.
  2. $n=2$ and $F=\mathbf F_3$. Then $\mathrm{PSL}(2,\mathbf F_3)\simeq S_4$ (again by the action on $\mathbf P_1(\mathbf F_3)$), and is not simple.

Bilinear algebra gives rise to new groups, orthogonal, unitary and symplectic, which also furnish simple groups up to elementary transformations. By the famous “classification of finite simple groups”, these constructions furnish all finite simple groups, up to 26 (or 27) examples called sporadic groups. This remarkable theorem has a fantastic proof, encompassing thousands of pages across the years 1960-2010.

But the question here is: How can one prove that a given group is simple?

Alternating groups

There is a large supply of proofs that the alternating group $A_n$ is simple for $n\geq 5$. Here is a sketch of one.

Let $N$ be a normal subgoup of $A_n$ ($n\geq 5$) and assume that $N\neq\{e\}$. An element of $A_n$ can be written as a product of an even number of transpositions. If two successive permutations in the product are equal, we can cancel them; if the share exactly one a common member, as in $(a\,b)(a\,c)$, their product is a 3-cycle $(a\,c\,b)$; if they have no common member, their product is a double transposition. On the other hand, if $n\geq 5$, we can either insert $(b\,c)(b\,c)$ in the product $(a\,b)(c\,d)$, writing a double transposition as a product of two 3-cycles, or insert $(d\,e)(d\,e)$ in the product $(a\,b)(a\,c)$, writing a 3-cycle as a product of two double transpositions. Consequently, $A_n$ is generated by, either the 3-cycles, or the double transpositions. Moreover, since $n\geq 5$, we can check that 3-cycles are pairwise conjugate, and similarly for double transpositions; consequently, if the normal subgroup $N$ of $A_n$ contains either a 3-cycle, or a double transposition, it will contain all of them, hence be equal to $A_n$.

When $n=5$, the only case that remains to consider is when $N$ contains a 5-cycle, say $g=(1\,2\,3\,4\,5)$. Conjugating $g$ by the 3-cycle $h=(4\,5\,1)$, we get $hgh^{-1}=(h1\,h2\,h3\,h4\,h5)=(4\,2\,3\,5\,1)\in N$. By construction, this element behaves as $g$ on $5$, but differs. Consequently, the commutator $hgh^{-1}g^{-1}$ is a nontrivial element of $N$ that fixes $5$. By the first two cases, one has $N=A_5$.

A similar argument works in general, arguing by descending induction on the cardinality on the fixed point set of an element $g\neq e$ of $N$. One considers an element $h$ of $A_n$ and the conjugate $hgh^{-1}$; if $g=(a_1\,a_2\,\dots)(b_1\,b_2\,\dots)\dots$, then $hgh^{-1}=(ha_1\,ha_2\,\dots)(hb_1\,hb_2\,\dots)\dots$ is an element of $N$ that behaves as $g$ on many elements, but not all. Consquently, $hgh^{-1}g^{-1}$ is a non trivial element of $N$ that fixes more elements than $g$, and we conclude by induction. (Details can be found in James Milne's lectures, 4.34.)

The Iwasawa criterion

In 1941, Kenkiti Iwasawa published a proof of the simplicity of the projective special linear group. From this proof, a general criterion for simplicity has been abstracted:

Theorem (Iwasawa). — Let $G$ be a group with a primitive action on a set $X$. Assume that one is given, for every $x\in X$, a subgroup $T(x)$ of $G$ satisfying the following properties:

  • For every $x\in X$, the subgroup $T(x)$ is commutative;
  • For every $g\in G$ and $x\in X$, $T(g\cdot x)=g T(x)g^{-1}$;
  • The union of the groups $T(x)$, for $x\in X$, generate $G$.
Then any normal subgroup $N$ of $G$ that acts nontrivially on $X$ contains the commutator subgroup of $G$. In particular, if $G=D(G)$, then $G$ is simple.

There are two classical ways to state that the action is primitive. The simplest states that it is transitive and that the stabilizers of points are maximal subgroups of $G$. Another is that there is no imprimitivity block, a nontrivial partition $(X_i)$ of $X$ such that for every $g\in G$ and every $i$, there exist $j$ such that $g\cdot X_i=$X_j$. One can prove that a 2-transitive action (= transitive on ordered pairs of distinct elements) is primitive.

Iwasawa applies his criterion to $G=\mathrm{SL}(n,F)$ acting on the projective space $\mathbf P_{n-1}(F)$ of lines in $F^n$. Except when $n=2$ and $F$ has 2 or 3 elements, this action is 2-transitive, hence primitive. For a nonzero $x\in F^n$, one considers the group $T(x)$ of linear transformations of the form $y\mapsto y + \phi(y) x$ (transvections), for all linear forms $\phi$ on $F^n$ such that $\phi(x)=0$. They constitute a commutative subgroup of $\mathrm{SL}(n,F)$ (isomorphic, as a group, to $F^{n-1}$). The map $T$ gives rise to the data as in Iwasawa's theorem. Consequently, every normal subgroup $N$ of $\mathrm{SL}(n,F)$ that acts nontrivially on $\mathbf P_{n-1}(F)$ contains the commutator subgroup of $\mathrm{SL}(n,F)$, which is $\mathrm{SL}(n,F)$. Explicitly, either $N$ consists of homotheties, or $N$ contains $\mathrm{SL}(n,F)$. This implies that $\mathrm{PSL}(n,F)$ is simple.

Applying the Iwasawa criterion for symmetric groups

One may wish to apply the Iwasawa criterion to the symmetric group. However, the conclusion is not as nice as what I had hoped initially.

Let $S_n$ act on the set of 2-element subsets of $X=\{1,\dots,n\}$. If $n\geq 5$, the action is primitive. This is not completely obvious, because it this action is not 2-transitive (you cannot map $\{1,2\}$ and $\{1,3\}$ to $\{1,2\}$ and $\{3,4\}$)! Its primitivity means that stabilizers are maximal subgroups, and one can prove that the stabilizer of a 2-element subset is indeed maximal unless $n=4$. It is also faithful (no nontrivial acts trivially). To a pair $\{a,b\}$, associate the subgroup of order 2 generated by the transposition $(a\,b)$. It satisfies the criterion, and this shows that the nontrivial normal subgroups of $S_n$ contain $D(S_n)=A_n$. Since $A_n$ has index 2, this shows $N=A_n$ or $N=S_n$.

It is interesting to guess how the criterion breaks for $n=4$. In fact, the action of $S_4$ on pairs is transitive, but not primitive: the stabilizer of $\{1,2\}$ is a subgroup of $S_4$ of order $4$, consisting of the identiy, two transpositions $(1\,2)$ and $(3\,4)$, and their product. Since $\mathrm{Card}(S_4)=24!=2^3\cdot 3$, this subgroup is contained in a 2-sylow subgroup, of order 8, so is not maximal.

However, and I find it unfortunate, this proof does not imply that the alternating group $A_n$ is simple for $n\geq 5$. To prove the simplicity of $A_n$ along these lines, we need to consider the following actions.

  • Let $A_n$ act on the set $X_3$ of 3-element subsets of $X$. For $x=\{a,b,c\}\in X_3$, consider the subgroup $T(x)$ of order 3 of $A_n$ consisting of the identity and the 3-cycles $(a\,b\,c)$ and $(a\,c\,b)$. (It is the alternating group on $x$, viewed as a subgroup of $A_n$.) The Iwasawa criterion applies provided the action is primitive, which presumably holds for $n>6$. Consequently, $A_n$ is simple for $n\geq 7$. However, if $n=6$, the stabilizer of $\{1,2\,3\}$ in $A_6$ is not maximal, for a reason analogous to the one explained for $S_4$.
  • Let $A_n$ act on the set $X_4$ of 4-element subsets of $X$. For $x\in X_4$, we can consider the Klein subgroup $T(x)$ of $A_4$, acting on $x$, viewed as a subgroup of $A_n$. I hope that the action is primitive, except for $n=8$, and this would prove that $A_n$ is simple for $n\geq 8$. This uses that double transpositions generate $A_n$.
  • One can improve the two preceding arguments a little bit. If $n=5$, we can have $A_n$ act on $X_2$, associating with $x$ the alternating group on the three remaining letters. Therefore, $A_5$ is simple (the action is primitive because the stabilizer of a point is the Klein subgroup of $A_4$, as a subgroup of $A_5$, its cardinality is 12, that of $A_5$ is 60, and since 60/12=5 is prime, the Klein subgroup of $A_4$ is maximal in $A_5$). Similarly, if $n=6$, we have $A_6$ act on $X_2$, associating with $x\in X_2$ the Klein subgroup corresponding to the four remaining letters. Provided one can prove that the stabilizer of a pair in $A_6$ is a maximal subgroup, this gives a proof that $A_6$ is simple!

The primitivity assertions seem to hold. In fact, maximal subgroups of $A_n$ and $S_n$ are classified by the O'Nan–Scott theorem. Those we're concerned with have type (a) in the notation of (Liebeck, Praeger, Saxl, 1987. “A Classification of the Maximal Subgroups of the Finite Alternating and Symmetric Groups.” Journal of Algebra 111 (2): 365–83. DOI:10.1016/0021-8693(87)90223-7), and according to Theorem 1 of that paper, the relevant subgroups are indeed maximal.

Formalization: where am I now?

I have already formalized the Iwasawa criterion in Lean (there's an ongoing pull request for this), as well as the result that the normal subgroups of $S_n$ are $\{e\}$, $A_n$ and $S_n$ for $n\geq 5$.

It remains to formalize the rest of the proof, and the main difficulty will be in proving primitivity, plus some nice way of defining the maps $T$ so that their properties are visible.

I also wish to formalize the simplicity of the special linear group along these lines, and it should be ready for an application to orthogonal, unitary or symplectic groups as well.

Thursday, April 22, 2021

Growth of the Gaussian pivoting algorithm

Gaussian elimination” is the standard method for solving systems of linear equations that runs by choosing one pivot variable in one of the equations and eliminating it from the other equations by a suitable linear combination. These other equations have one less variable and one may iterate the process, leading to a system that has a triangular form and can be solved in a relatively straightforward way. In the so-called Gauss-Jordan method, the pivot variables are eliminated from all of the equations, and this leads to the row reduced echelon form of the initial system, a new system in which the pivot variables are explicitly solved in terms of the remaining variables; it also has the merit of being independent of the intermediate steps, but this would be a story for another night.

How the name of Gauss is attributed to this method is also another story, that is recounted in great detail by J. Grcar. As he explains, systems of linear equations and their solution already appear on Babylonian tablets (2000 BC), on the Egyptian Rhind papyrus (1550 BC), in the Chinese Nine chapters on the mathematical art (200 AD), the Arithmetica of the Greek mathematician Diophantus (250 AD), the Āryabhaṭīya of the Hindu mathematician Āryabhaṭa (499 AD). Such systems were essentially absent of the mathematics treatises during the Renaissance and it is to Newton (17th century) that we owe its revival in Western Europe. At the beginning of the 19th century, in relation with the problem in celestial mechanics/geodesy of fitting together multiple imprecise measurements, Gauss and Legendre invented the least square methods. This involved a system of linear equations which Gauss solved by what he called “common elimination”. In the 20th century, the development of computing machines and numerical analysis led to further work, from Cholesky (in relation with geodesy), Crout, to von Neumann and Goldstine and their $LDU$ decomposition.

Whoever had to perform elimination by hand knows that the computations are rapidly tedious and often lead to more and more complicated fractions. 

When computer calculations are done with floating point algebra, the difficulty of rounding errors appears. If in a linear system, say $Ax=b$,  the matrices $A$ and $b$ are only known up to an error, so that the system that is actually solved would rather be $(A+E)x=b+\delta b$, and it is of an obvious importance to compare its solution with the solution of the initial system. One way to make this comparison involves the inverse of $A$, which is unknown at this stage. The product of the norms $\|A\| \,\|A^{-1}\|$ is the conditioning number of $A$, and one can not avoid the problem of ill-conditioned matrices, which will inherently lead to lack of precision.

But when floating points numbers are used in the computation, a new problem appears, even when one restricts to well-conditioned systems. Floating points numbers are of the form $\pm a\cdot 10^e$ (in base 10, say), where $a$ is a real number between $1$ and $10$ which is known up to a fixed number of decimal places. In other words, floating points numbers are known up to a relative error. Let us examine the consequence for the subtraction of floating point numbers. Consider two such numbers, say $x=a\cdot 10^e$ and $x'=a'\cdot 10^e$, with the same exponent $e$, and such that $a$ and $a'$ are close. Their difference is given by $x'-x=(a'-a)\cdot 10^e$, but since $a$ and $a'$ are close, their difference $y=x'-x$ is no more between $1$ and $10$, but may be, say of size $10^{-5}$, so that the floating point expression of $x'-x$ is $(10^5(a'-a))\cdot 10^{e-5}=b\cdot 10^{e-5}$; the problem is that the last 5 decimals of $b$ are absolutely unknown, which leads to a relative error for $y$ which is $10^5$ as big as expected!

Now, by its very essence, the elimination method features a lot of such subtractions, hence it is inherently not very well suited with floating points numbers. 

In the 1960s, the American mathematician Wilkinson analysed the situation very precisely.  He showed that for the Gaussian elimination, the main parameter is the relative size of the matrices that intervene in the process. To set up some notation, imagine that the initial system $Ax=b$ is transformed, step by step, into a series of equivalent systems $A^{(r)}x=b^{(r)}$, where $A^{(r)}=(a_{ij}^{(r)})$ is a matrix whose first $r$ lines are in triangular form, and the remaining $n-r$ lines still need to be worked on. To get the matrix $A^{(r+1)}$, one subtract a multiple $m_{ir}$ of the $r$th row from the $i$th row he multipliers, for $i$ ranging from $r+1$ to $n$, where the multipliers $m_{ir}$ are defined by
\[ m_{ir}=a_{ir}^{(r)}/a_{rr}^{(r)}. \]
Large multipliers lead to lack of precision, but if complete pivoting method is used, one has $|m_{ir}|\leq 1$. In this case, one observes that a bound $|a_{ij}^{(r)}|\leq M$ for the coefficients of $A^{(r)}$ leads to the bound $|a_{ij}^{(r+1)}|\leq 2M$ at the next step. At the last step, one gets $|a_{ij}^{(n)}|\leq 2^{n-1}M$, where $M=\sup(|a_{ij}|)$. Consequently, the relevant constant to be estimated,
\[ R(A) = \sup_r \frac{\sup_{i,j}|a_{ij}^{(r)}|}{\sup_{i,j}|a_{ij}|}, \]
satisfies $R(A)\leq 2^{n-1}$.

In fact, Wilkinson (1961) gave a much better bound. Let $B^{(r)}$ be the square matrix of size $n-r$ that has to be worked on after the $r$th step and let $b_{r}$ be the maximum size of its coefficients, the size of the chosen pivot since one does complete pivoting. One has the following fomula for its determinant:
\[ \det(B^{(r)})= b_{r+1}\cdots b_n. \]
Moreover, the Euclidean norms of the the columns of $B^{(r)}$ are bounded above by $\sqrt{n-r} b_{r+1}$ and Hadamard inequality (“the volume of a parallelepiped is smaller than the product of the sizes of its edges”) implies that
\[ | \det(B^{(r)})| \leq (n-r)^{(n-r)/2} b_{r+1}^{n-r}. \]
Together, these relations lead to an upper bound
\[ R(A) \leq n^{1/2} \left( 2\cdot 3^{1/2}\cdot 4^{1/3}\cdots n^{1/(n-1)}\right)^{1/2}, \]
roughly $n^{\log(n)/4}$, a bound that Wilkinson considers to be a “severe overestimate”, and in Wilkinson (Rounding Errors in Algebraic Processes, Dover, 1963, bottom of p. 97), he even notes that “No matrix has yet been discovered for which $R(A)>n$.

This statement remained known as Wilkinson's conjecture, although Wilkinson himself did not state it as such. Tornheim (1964) proved that Hadamard matrices — matrices with entries $\pm1$ and pairwise orthogonal columns and rows — satisfy $R(A)\geq n$ and this led Cryer (1968) to formally state the conjecture and to suspect that $R(A)<n$ unless $A$ is a Hadamard matrix. Some matrices have been shown such that $R(A)\geq (n+1)/2$ (Higham & Higham, 1989) and random matrices seems to have an $R$-factor roughly $n^{1/2}$ (Trefethen & Schreiber, 1990). In fact, Hadamard matrices of size $n=12$ (Edelman & Mascarenhas, 1995) or $n=16$ (Kravvaritis & Mtrouli, 2009) satisfy $R(A)=n$, but this is definitely nontrivial.

However, Gould (1991) could exhibit a matrix $A$ of size $n=13$ with  growth factor $R(A)=13.0205$, thus providing a counterexample to Wilkinson's “conjecture”. To that aim, he reduced the question to finding a solution of a nonlinear programming problem with roughly $n^3/3\approx 700$ variables, fortunately a sparse one, a computation he did using a programming package he had developed with Conn and Toint. The matrix he gives has integer coefficients of size up to 20 digits!

But the story does not end here!

Edelman tried to replicate Gould's computations using the computer algebra softwares Mathematica and Maple — what he found is the growth factor of Gould's matrix is around $7.355$, consistently in both softwares! As he writes, one of these softwares could have had a bug, but it is rather unlikely that both of them had had the same one.

What happened, and you will agree that there is much irony in this story, is that Gould had performed his computations using floating point algebra. A near tie in the 6th pivot lead to an incorrect choice of pivot and to an erroneous computation, even within the double precision that he has used.

Fortunately, Edelman (1992) showed that changing one coefficient by $10^{-7}$ in Gould's matrix yields a growth of $13.02$, so that Wilkinson's “conjecture” is definitely incorrect.

Friday, April 2, 2021

On the Hadamard-Lévy theorem, or is it Banach-Mazur?

During the preparation of an agrégation lecture on connectedness, I came across the following theorem, attributed to Hadamard–Lévy: 

Theorem. — Let $f\colon \mathbf R^n\to\mathbf R^n$ be a $\mathscr C^1$-map which is proper and a local diffeomorphism. Then $f$ is a global diffeomorphism.

In this context, that $f$ is proper means that $\| f(x)\| \to+\infty$ when $\| x\|\to+\infty$, while, by the inverse function theorem, the condition that $f$ is a local diffeomorphism is equivalent to the property that its differential $f'(x)$ is invertible, for every $x\in\mathbf R^n$. The conclusion is that $f$ is a diffeomorphism from $\mathbf R^n$ to itself; in particular, $f$ is bijective and its inverse is continuous.

This theorem is not stated in this form neither by Hadamard (1906), nor by Lévy (1920), but is essentially due to Banach & Mazur (1934) and it is the purpose of this note to clarify the history, explain a few proofs, as well as more recent consequences for partial differential equations.

A proper map is closed: the image $f(A)$ of a closed subset $A$ of $\mathbf R^n$ is closed in $\mathbf R^n$. Indeed, let $(a_m)$ be a sequence in $A$ whose image $(f(a_m))$ converges in $\mathbf R^n$ to an element $b$; let us show that there exists $a\in A$ such that $b=f(a)$. The properness assumption on $f$ implies that $(a_m)$ is bounded. Consequently, it has a limit point $a$, and $a\in A$ because $A$ is closed. Necessarily, $f(a)$ is a limit point of the sequence $(f(a_m))$, hence $b=f(a)$.

In this respect, let us note the following reinforcement of the previous theorem, due to Browder (1954):
Theorem (Browder). — Let $f\colon \mathbf R^n\to\mathbf R^n$ be a local homeomorphism. If $f$ is closed, then $f$ is a global homeomorphism.

A surprising aspect of these results and their descendents is that they are based on two really different ideas. Banach & Mazur and Browder are based on the notion of covering, with ideas of homotopy theory and, ultimately, the fact that $\mathbf R^n$ is simply connected. On the other hand, the motivation of Hadamard was to generalize to dimension $n$ the following elementary discussion in the one-dimensional case: Let $f\colon\mathbf R\to\mathbf R$ be a $\mathscr C^1$-function whose derivative is $>0$ everywhere (so that $f$ is strictly increasing); give a condition for $f$ to be surjective. In this case, the condition is easy to find: the indefinite integral $\int f'(x)\,dx$ has to be divergent both at $-\infty$ and $+\infty$. In the $n$-dimensional case, the theorems of Hadamard is the following:

Theorem.Let $f\colon\mathbf R^n\to\mathbf R^n$ be a $\mathscr C^1$-map. For $r\in\mathbf R_+$, let $\omega(r)$ be the infimum, for $x\in\mathbf R^n$ such that $\|x\|=r$, of the norm of the linear map $f'(x)^{-1}$; if $\int_0^\infty dr/\omega(r)=+\infty$, then $f$ is a global diffeomorphism.

In Hadamard's paper, the quantity $\omega(r)$ is described geometrically as the minor axis of the ellipsoid defined by $f'(x)$, and Hadamard insists that using the volume of this ellipsoid only, essentially given by the determinant of $f'(x)$, would not suffice to characterize global diffeomorphisms. (Examples are furnished by maps of the form $f(x_1,x_2)=(f_1(x_1),f_2(x_2))$. The determinant condition considers $f_1'(x_1)f_2'(x_2)$, while one needs individual conditions on $f'_1(x_1)$ and $f'_2(x_2)$.)

In fact, as explained in Plastock (1974), both versions (closedness hypothesis or quantitative assumptions on the differential) imply that the map $f$ is a topological covering of $\mathbf R^n$. Since the target $\mathbf R^n$ is simply connected and the source $\mathbf R^n$ is connceted, $f$ has to be a homeomorphism. I will explain this proof below, but I would first like to explain another one, due to Zuily & Queffelec (1995) propose an alternating proof which is quite interesting.

A dynamical system approach

The goal is to prove that $f$ is bijective and, to that aim, we will prove that every preimage set $f^{-1}(b)$ is reduced to one element. Replacing $f$ by $f-b$, it suffices to treat the case of $b=0$. In other words, we wish to solve that the equation $f(x)=0$ has exactly one solution. For that, it is natural to try to start from some point $\xi\in\mathbf R^n$ and to force $f$ to decrease. This can be done by following the flow of the vector field given by $v(x)=-f'(x)^{-1}(f(x))$. This is a vector field on $\mathbf R^n$ and we can consider its flow: a map $\Phi$ defined on an open subset of $\mathbf R\times\mathbf R^n$ such that $\partial_t \Phi(t,x)=v(\Phi(t,x))$ for all $(t,x)$ and $\Phi(0,x)=x$ for all $x$. In fact, the Cauchy–Lipschitz theorem guarantees the existence of such a flow only if the vector field $v$ is locally Lipschitz, which happens if, for example, $f$ is assumed to be $\mathscr C^2$. In this case, there is even uniqueness of a maximal flow, and we will make this assumption, for safety. (In fact, the paper of De Marco, Gorni & Zampieri (1994) constructs the flow directly thanks to the hypothesis that the vector field is pulled back from the Euler vector field on $\mathbf R^n$.)

What are we doing here? Note that in $\mathbf R^n$, the opposite of the Euler vector field, defined by $u(y)=-y$, has a very simple solution: the flow lines are straight lines going to $0$. The formula above just pulls back this vector field $u$ via the local diffeomorphism $f$, and the flow lines of the vector field $v$ will just be the ones given by pull back by $f$, which will explain the behaviour described below.

In particular, let $a\in\mathbf R^n$ be such that $f(a)=0$ and let $U$ be a neighborhood of $a$ such that $f$ induces a diffeomorphism from $U$ to a ball around $0$. Pulling back the solution of the minus-Euler vector field by $f$, we see that once a flow line enters the open set $U$, it converges to $a$. The goal is now to prove that it will indeed enter such a neighborhood (and, in particular, that such a point $a$ exists).

We consider a flow line starting from a point $x$, that is, $\phi(t)=\Phi(t,x)$ for all times $t$. Let $g(t)= f(\phi(t))$; observe that $g$ satisfies $g'(t)=f'(\phi(t))(\phi'(t))=-g(t)$, hence $g(t)=g(0)e^{-t}$. Assume that the line flow is defined on $[0;t_1\mathopen[$, with $t_1<+\infty$. by what precedes, $g$ is bounded in the neighborhood of $t_1$; since $f$ is assumed to be proper, this implies that $\phi(t)$ is bounded as well. The continuity of the vector field $v$ implies that $\phi$ is uniformly continuous, hence it has a limit at $t_1$. We may then extend the line flow a bit right of $t_1$. As a consequence, the line flow is defined for all times, and $g(t)\to0$ when $t\to+\infty$. By the same properness argument, this implies that $\phi(t)$ is bounded when $t\to+\infty$, hence it has limit points $a$ which satisfy $f(a)=0$. Once $\phi$ enters an appropriate neighborhood of such a point, we have seen that the line flow automatically converges to some point $a\in f^{-1}(0)$.

Let us now consider the map $\lambda\colon\mathbf R^n\to f^{-1}(0)$ that associates with a point $\xi$ the limit of the line flow $t\mapsto \Phi(t,\xi)$ starting from the initial condition $\xi$. By continuity of the flow of a vector field depending on the initial condition, the map $\lambda$ is continuous. On the other hand, the hypothesis that $f$ is a local diffeomorphism implies that $f^{-1}(0)$ is a closed discrete subset of $\mathbf R^n$. Since $\mathbf R^n$ is connected, the map $\lambda$ is constant. Since one has $\lambda(\xi)=\xi$ for every $\xi\in f^{-1}(0)$, this establishes that $f^{-1}(0)$ is reduced to one element, as claimed.

Once $f$ is shown to be bijective, the fact that it is proper (closed would suffice) implies that its inverse bijection $f^{-1}$ is continuous. This concludes the proof.

The theorem of Banach and Mazur

The paper of Banach and Mazur is written in a bigger generality. They consider multivalued continuous maps $F\colon X\to Y$ ($k$-deutige stetige Abbildungen) by which they mean that for every $x$, a subset $F(x)$ of $Y$ is given, of cardinality $k$, the continuity being expressed by sequences: if $x_n\to x$, one can order, for every $n$, the elements of $F(x_n)=\{y_{n,1},\dots,y_{n,k}\}$, as well as the elements of $F(x)=\{y_1,\dots,y_k\}$, in such a way that $y_{n,j}\to y_n$ for all $j$. (In their framework, $X$ and $Y$ are metric spaces, but one could transpose their definition to topological spaces if needed.) They say that such a map is decomposed (zerfällt) if there are continuous functions $f_1,\dots,f_k$ from $X$ to $Y$ such that $F(x)=\{f_1(x),\dots,f_k(x)\}$ for all $x\in X$.

In essence, the definition that Banach and Mazur are proposing contains as a particular case the finite coverings. Namely, if $p\colon Y\to X$ is a finite covering of degree $k$, then the map $x\mapsto p^{-1}(x)$ is a continuous $k$-valued map from $X$ to $Y$. Conversely, let us consider the graph $Z$ of $F$, namely the set of all points $(x,y)\in X\times Y$ such that $y\in F(x)$. Then the first projection $p\colon Z\to X$ is a covering map of degree $k$, but it is not clear that it has local sections.

It would however not be so surprising to 21st-century mathematicians that if one makes a suitable assumption of simple connectedness on $X$, then every such $F$ should be decomposed. Banach and Mazur assume that $X$ satisfies two properties:

  1. The space $X$ is semilocally arcwise connected: for every point $x\in X$ and every neighborhood $U$ of $x$, there exists an open neighborhood $U'$ contained in $U$ such that for every point $x'\in U'$, there exists a path $c\colon[0;1]\to U$ such that $c(0)=x$ and $c(1)=x'$. (Semilocally means that the path is not necessarily in $U'$ but in $U$.)
  2. The space $X$ is arcwise simply connected: two paths $c_0,c_1\colon[0;1]\to X$ with the same endpoints ($c_0(0)=c_1(0)$ and $c_0(1)=c_1(1)$) are strictly homotopic — there exists a continuous map $h\colon[0;1]\to X$ such that $h(0,t)=c_0(t)$ and $h(1,t)=c_1(t)$ for all $t$, and $h(s,0)=c_0(0)$ and $h(s,1)=c_0(1)$ for all $s$.

Consider a $k$-valued continuous map $F$ from $X$ to $Y$, where $X$ is connected. Banach and Mazur first prove that for every path $c\colon [0;1]\to X$ and every point $y_0\in F(c(0))$, there exists a continuous function $f\colon[0;1]\to Y$ such that $f(t)\in F(c(t))$ for all $t$. To that aim, the consider disjoint neighborhoods $V_1,\dots,V_k$ of the elements of $F(c(0))$, with $y_0\in V_1$, say, and observe that for $t$ small enough, there is a unique element in $F(c(t))\cap V_1$. This defines a bit of the path $c$, and one can go on. Now, given two paths $c,c'$ such that $c(0)=c'(0)$ and $c(1)=c'(1)$, and two maps $f,f'$ as above, they consider a homotopy $h\colon[0;1]\times[0;1]\to X$ linking $c$ to $c'$. Subdividing this square in small enough subsquares, one see by induction that $f(1)=f'(1)$. (This is analogous to the proof that a topological covering of the square is trivial.) Fixing a point $x_0\in X$ and a point $y_0\in F(x_0)$, one gets in this way a map from $X$ to $Y$ such that $F(x)$ is equal to $f(1)$, for every path $c\colon[0;1]\to X$ such that $c(0)=x_0$ and $c(1)=x$, and every continuous map $f\colon [0;1]\to Y$ such that $f(t)\in F(c(t))$ for all $t$ and $f(0)=y_0$. This furnishes a map from $X$ to $Y$, and one proves that it is continuous. If one considers all such maps, for all points in $F(x_0)$, one obtains the decomposition of the multivalued map $F$.

To prove their version of the Hadamard–Lévy theorem, Banach and Mazur observe that if $f\colon Y\to X$ is a local homeomorphism which is proper, then setting $F(x)=f^{-1}(y)$ gives a multivalued continuous map. It is not obvious that the cardinalities $k(x)$ of the sets $F(x)$ are constant, but this follows (if $X$ is connected) from the fact that $f$ is both a local homeomorphism and proper. Then $F$ is decomposed, so that there exist continuous maps $g_1,\dots,g_k\colon X\to Y$ such that $f^{-1}(x)=\{g_1(x),\dots,g_k(x)\}$ for all $x\in X$. This implies that $Y$ is the disjoint union of the $k$ connected subsets $g_j(X)$. If $Y$ is connected, then $f$ is a homeomorphism.

The versions of Hadamard and Lévy, after Plastock

Hadamard considered the finite dimensional case, and Lévy extended it to the case of Hilbert spaces.

Plastock considers a Banach-space version of the theorem above: $f\colon E\to F$ is a $\mathscr C^1$-map between Banach spaces with invertible differentials and such that, setting $\omega(r)=\inf_{\|x\| = r}\|f'(x)^{-1}\|$, one has $\int_0^\infty \omega(r)\,dr=+\infty$. Of course, under these hypotheses, the Banach spaces $E$ and $F$ are isomorphic, but it may be useful that they are not identical. Note that $f(E)$ is open in $F$, and the proposition that will insure that $f$ is a global diffeomorphism is the following one, in the spirit of covering theory.

Proposition.(Assuming that $f$ is a local diffeomorphism.) It suffices to prove that the map $f$ satisfies the path lifting property: for every point $x\in E$ and every $\mathscr C^1$ map $c\colon[0;1]\to f(E)$ such that $c(0)=f(x)$, there exists a $\mathscr C^1$ map $d\colon[0;1]\to E$ such that $c(t)=f(d(t))$ for all $t$ and $d(0)=c$.

The goal is now to prove that $f$ satisfies this path lifting property. Using that $f$ is a local homeomorphism, one sees that lifts are unique, and are defined on a maximal subinterval of $[0;1]$ which is either $[0;1]$ itself, or of the form $[0;s\mathclose[$. To prevent the latter case, one needs to impose conditions on the norm $\| f'(x)^{-1}\|$ such as the one phrased in terms of $\omega(r)$ as in the Hadamard–Lévy theorem. In fact, Plastock starts with a simpler case.

Proposition.The path lifting property follows from the following additional hypotheses:

  1. One has $\|f(x)\|\to+\infty$ when $\|x\|\to+\infty$;
  2. There exists a positive continuous function $M\colon\mathbf R_+\to\mathbf R_+$ such that $\|f'(x)^{-1}\|\leq M(\|x\|)$ for all $x.

Assume indeed that a path $c$ has a maximal lift $d$, defined over the interval $[0;s\mathclose[$. By the hypothesis (i), $d(t)$ remains bounded when $t\to s$, because $c(t)=f(d(t))$ tends to $c(s)$. Differentiating the relation $c(t)=f(d(t))$, one gets $c'(t)=f'(d(t))(d'(t))$, hence $d'(t)=f'(d(t))^{-1}(c'(t))$, so that $\| d'(t)\|\leq M(\|d(t)\|) \|c'(t)\|$. This implies that $\|d'\|$ is bounded, so that $d$ is uniformly continuous, hence it has a limit at $s$. Then the path $d$ can be extended by setting $d(s)$ to this limit and using the local diffeomorphism property to go beyong $s$.

The Hadamard–Lévy is related to completeness of some length-spaces. So we shall modify the distance of the Banach space $E$ as follows: if $c\colon[0;1]\to E$ is a path in $E$, then its length is defined by \[ \ell(c) = \int_0^1 \| f'(c(t))^{-1}\|^{-1} \|{c'(t)}\|\, dt. \] Observe that $\|f'(c(t))^{-1}\|^{-1} \geq \omega(\|c(t)\|)$, so that \[ \ell(c) \geq \int_0^1 \omega(\|c(t)\|) \|{c'(t)}\|\, dt. \] The modified distance of two points in $E$ is then redefined as the infimum of the lengths of all paths joining two points.

Lemma.With respect to the modified distance, the space $E$ is complete.

One proves that $\ell(c) \geq \int_{\|{c(0)}\|}^{\|{c(1)}\|}\omega(r)\,dr$. Since $\int_0^\infty \omega(r)\,dr=+\infty$, this implies that Cauchy sequences for the modified distance are bounded in $E$ for the original norm. On the other hand, on any bounded subset of $E$, the Banach norm and the modified distance are equivalent, so that they have the same Cauchy sequences.

Other conditions can be derived from Plastock's general theorem. For example, assuming that $E$ and $F$ are a Hilbert space $H$, he shows that it suffices to assume the existence of a decreasing function $\lambda\colon\mathbf R_+\to\mathbf R_+$ such that $\langle f'(x)(u),u\rangle \geq \lambda(\|x\|) \| u\|^2$ for all $x,y$ and $\int_0^\infty \lambda(r)\,dr=+\infty$. Indeed, under this assumption, one may set $\omega(r)=\lambda(r)$.

Application to periodic solutions of differential equations

Spectral theory can be seen as the infinite dimensional generalization of classical linear algebra. Linear differential operators and linear partial differential operators furnish prominent examples of such operators. The theorems of Hadamard–Lévy type have been applied to solve nonlinear differential equations.

I just give an example here, to give an idea of how this works, and also because I am quite lazy enough to check the details.

Following Brown & Lin (1979), we consider the Newtonian equation of motion: \[ u''(t) + \nabla G (u(t)) = p(t) \] where $G$ represents the ambiant potential, assumed to be smooth enough, and $p\colon \mathbf R\to\mathbf R^n$ is some external control. The problem studied by Brown and Lin is to prove the existence of periodic solutions when $p$ is itself periodic. The method consists in interpreting the left hand side as a non linear map defined on the Sobolev space $E$ of $2\pi$-periodic $\mathscr C^1$-functions with a second derivative in $F=L^2([0;2\pi];\mathbf R^n)$, with values in $F$. Write $L$ for the linear operator $u\mapsto u''$ and $N$ for the (nonlinear) operator $u\mapsto \nabla G(u)$. Then $L$ is linear continuous (hence $L'(u)(v)=L'(v)$), and $N$ is continuously differentiable, with differential given by \[ N'(u) (v) = \left( t \mapsto Q (u(t)) (v(t)) \right) \] for $u,v\in E$, and $Q$ is the Hessian of $G$.

In other words, the differential $(L+N)'(u)$ is the linear map $v\mapsto L(v) + Q(u(t)) v$. It is invertible if the eigenvalues of $Q(u(t))$ are away from integers. Concretely, Brown and Lin assume that there are two constant symmetric matrices $A$ and $B$ such that $A\leq Q(x) \leq B$ for all $x$, and whose eigenvalues $\lambda_1\leq \dots\lambda_n$ and $\mu_1\leq\dots\leq \mu_n$ are such that there are integers $N_1,\dots,N_n$ with $N_k^2<\lambda_k\leq\mu_k<(N_k+1)^2$ for all $k$. Using spectral theory in Hilbert spaces, these conditions imply that the linear operator $L+Q(u)\colon E\to F$ is an isomorphism, and that $\|(L+Q(u)^{-1}\|$ is bounded from above by the constant expression \[ c= \sup_{1\leq k\leq n} \sup (\lambda_k-N_k^2)^{-1},((N_k+1)^2-\mu_k)^{-1} ).\]

Thanks to this differential estimate, the theorem of Hadamard–Lévy implies that the nonlinear differential operator $L+N$ is a global diffeomorphism from $E$ to $F$. In particular, there is a unique $2\pi$-periodic solution for every $2\pi$-periodic control function $p$.

I thank Thomas Richard for his comments.

Saturday, March 27, 2021

The Fermat–Lévy constant

Undergraduate analysis is full of computions of strange trigonometric series and I posted on Twitter, as a challenge, to compute the following constant: $$ c = \sum_{p=3}^\infty \frac1{p^2} \int_0^{2\pi} \left( \sum_{n=1}^\infty \frac1{n^2} \cos(nx)\right)^3\, dx. $$ As some followers quickly remarked, there could be some irony with this exercise, because quite unexpectedly, they could solve it using the solution to Fermat's Last Theorem. So I'll start with the origin of this problem.

(Light) philosophy of mathematics

This constant came as a screen capture from a 1950 paper by Paul Lévy, Axiome de Zermelo et nombres transfinis (Zermelo axiom and transfinite numbers) where he discusses various reasons to accept, or refuse, Zermelo's principle according to which every set can be endowed with a well-ordering.

Zermelo had proved this principle in 1905 and we know today that this principle is equivalent to the “axiom of choice”. In fact, given a set $S$, Zermelo chooses once and for all, for every nonempty subset $A$ of $S$ some element $f(A)$ of $A$ and it seems that this is precisely this simultaneous quantity of choices that led his contemporaries to realize the necessity of the axiom of choice, as an axiom, first for philosophical reasons — because they objected to the very possibility of doing so.

We know today how Zermelo's theorem is equivalent to the axiom of choice, that it is essentially inoccuous (Gödel, 1938, showing that if there is a set theory without assuming choice, there is some set theory where the axiom of choice is valid), but that it is also unprovable from the other axioms of set theory, say, those (ZF) proposed by Zermelo and Fraenkel (Cohen, 1965, showing that if there is a set theory without assuming the axiom of choice, there is some set theory where the axiom of choice does not hold).

We also know how this axiom, whose usefulness is recognized in the proofs of many theorems of algebra (existence and uniqueness of an algebraic closure, of prime or maximal ideals, of basis for vector spaces, etc.), also leads to paradoxical constructions (such as nonmeasurable sets, or the Banach–Tarski paradoxical decomposition of the unit sphere into finitely many parts that can be recombined into two unit spheres). For many modern mathematicians, the question is now that of a risk-benefice balance — using this axiom on safe grounds, say. However, for mathematicians such as Lebesgue, Borel or Brouwer, who were inspired by a constructive or intuitionistic philosophy of mathematics, this axiom had to be rejected, because they objected to the idea of using objects that cannot be named.

In his 1950 paper, Paul Lévy discusses these objections and explains why he rejects them. As he recognizes, the nature of language only allows for a countable amount of mathematical formulas, hence we can only name a countable amount of mathematical objects, and we know – this is a 1878 theorem of Cantor – that the continuum, for example, is not countable. There must exist, says Paul Lévy, numbers that cannot be named, « des nombres innomables ». I should add that Loren Graham and Jean-Michel Kantor wrote a book on that topic, Naming Infinity: A True Story of Religious Mysticism and Mathematical Creativity, which contains a whole chapter on what they call “the French trio: Borel, Lebesgue, Baire”.

At this point, Lévy introduces the constant whose definition starts this note. Let us now read what Lévy tells us (my translation):

Do mathematical objects exist in themselves, or only as products of the human mind and of our human logic? The point of view of Mr Brouwer regarding the truth of the statements of theorems forces us to ask the question.

Let us consider a precise statement, to fix ideas, that of Fermat's theorem. For us, it is true or false, and the sum $$ c = \sum_{p=3}^\infty \int_0^{2\pi} \left( \sum_1^\infty \frac{\cos n^p x}{n^2}\right)^3\, dx $$ is zero in the first case and positive in the second. If it is false, one can check that it is false (although we do not know in advance how much time is needed). If it is true, an infinite number of checks would be necessary to assure it, and nothing guarantees a priori that this infinite number can be replaced by a finite reasoning. So there are three possible hypotheses (for some theorems, there would be four): the theorem is false; it is true and provable; it is true and unprovable.

In this latter case, Mr Brouwer refuses to consider this theorem as true, and the constant $c$ is neither zero nor positive (nor negative, of course).

Let us detail his argument a little bit. Lévy says that his strangely defined constant $c$ is zero in case FLT is true, and is strictly positive otherwise. But what is its value? For some mathematicians such as Brouwer, this constant can only have a value if we can prove that we are in one case or the other. At the time when Lévy writes his article, in 1950, one did not know yet whether Fermat's last theorem was true or false, it would only be proved in 1995! There is one way to prove that FLT is false, it consists in enumerating all quadruples $(x,y,z,p)$, where $x,y,z$ are strictly positive integers and $p$ is a prime number $\geq 3$, until one reaches some quadruple where $x^p+y^p=z^p$ – this guarantees that $c>0$, Lévy says. But if FLT is true, then this enumeration will go on indefinitely and we will never reach the conclusion. Lévy has an objection to this disappointment, which I find quite amusing, based on the paradox of Zeno of Elea: imagine that we are quicker and quicker at each verification, for example, say twice as fast each time. We could need 1 second for the first quadruple, half a second for the second one, a quarter second for the third one, and so on, and then the whole verification would take 2 seconds. This is obviously a thought experiment and I do not know if physics forbids such a phaenomenon, which anyway Lévy qualifies as supernatural. Computer scientists could object as well, because the complexity of the required computations grows at each step. But let us stop that this philosophical discussion and go back to Lévy's constant.

Computing the Lévy constant

The indicated sum is a series, indexed by prime number $p\geq 3$ (we could consider integers as well) of some integral from $0$ to $2\pi$ of some trigonometric expression (divided by $p^2$) which I will denote by $c_p$.

The point is that $c_p$ is always positive or zero, and that $c_p$ is strictly positive if and only if Fermat's last theorem fails for exponent $p$. It is not precised by Lévy, but the goal of division by $p^2$ is to make sure that the infinite series converges, whatever its sum.

Since cosines are smaller than $1$, the series of all $\cos(n^p x)/n^2$ converges normally and its sum is a continuous function of $x$ which I will denote by $f(x)$. And one has $c_p=\int_0^{2\pi} f(x)^3\,dx$. (Since $f$ is bounded from above independently of $p$, for example by $\pi^2/6$, each integral is uniformly bounded, and the division by $p^2$ will make the whole series convergent.) To understand this integral, let us expand the cube.

What we get is a sum, indexed by triples of integers $(k,m,n)$ of terms of the form $\cos(k^px) \cos(m^px)\cos(n^px) / k^2m^2n^2$, and we need to integrate each of them from $0$ to $2\pi$.

Several methods are possible, such as knowing one's formulas for products of cosines, but I prefer replacing the cosines by their complex exponential expression (Euler's formula), so that each term gets replaced by a sum of 8 terms of the form $e^{\pm i k^p x} e^{\pm i m^p x} e^{\pm i n^p x} / 8 k^2m^2n^2$. Let us factor the exponentials: we get $e^{ i (\pm k^p\pm m^p\pm n^p) x} / 8k^2m^2 n^2$, and its integral from $0$ to $2\pi$ is equal to $\pi/4k^2m^2n^2$ if the argument of $x$ vanishes, and is zero otherwise.

In other words, the triple $(k,m,n)$ contributes as a strictly positive quantity to the sum as soon as $(\pm k,\pm m,\pm n)$ is a counterexample to Fermat's theorem for exponent $p$. Amusing, isn't it? Yes, but you will admit that it is essentially tautological… However…

The circle method

I now reach deeper, in any case mathematically more efficient, considerations and wish to say some words of the circle method. I'll take as an example the problem that the English mathematician Waring had posed in 1770.

In his Arithmetics, Diophantus had asked whether every integer is a sum of 4 perfect squares of integers, and Lagrange proved in 1770 that it is indeed the case. Waring generalized the question to higher powers: is it true that every integer is the sum of at most 9 perfect cubes of integers, or 19 fourth powers, etc.? These two numbers, 9 and 19, correspond to the fact that we need indeed 9 cubes to write 23 ($23 = 2^3 + 2^3 + 2^3 + 1 +1 + 1 + 1 + 1$) and 19 fourth powers to write $79$. So Waring was asking whether this necessary bound was, in fact, sufficient.

We know today that this is the case for cubes (Wieferich, 1909; Kempner, 1912) ou les puissances quatrièmes (Balasubramanian, Dress, Deshouillers, 1986). We also know that there is, for every integer $k\geq3$, some smallest integer $g(k)$ such that every integer is the sum of at most $g(k)$, as well as an upper bound which conjecturally is an equality, namely $g(k)=2^k+\lfloor (3/2)^k\rfloor - 2$.

However, the question seems to me as rather less interesting, when $k$ grows, than the asymptotic analogue: every large enough integer is the sum of at most $G(k)$ perfect $k$th powers, because for this problem a much better bound is known to hold: $G(k)\leq 2k \log(k)+\cdots$ (Vinogradov, Karatsuba, Vaughan, Wooley…).

And to establish these results, trigonometric series strike back, as the heart of the circle method of Hardy and Littlewood.

To write $N$ as a sum of $k$th powers, the idea is to set $f(x)$ as the sum, for all integers $n$ smaller than $P=N^{1/k}$, of $\exp(2i\pi n^k x)$, and to observe that the number of solution to Waring's equality $n_1^k+\cdots+n_r^k=N$ is given by the integral from $0$ to $1$ of the quantity $f(x)^r \exp(-2i\pi Nx)$.

At this point, we have not been less tautological than Paul Lévy was, and it required the genius of Hardy, Littlewood and their followers to observe that this integral could be actually evaluated. To that aim, the idea is to split the interval $[0;1]$ in two regions. First of all, intervals (major arcs) centered around rational numbers of the form $a/q$, where $q$ is “small”, and the complementary set (minor arcs). Roughly, the contribution of major arcs can be reduced to trigonometric sums in finite fields, using the Chinese remainder theorem and other trics, and it appears to have a simple asymptotic expansion – this is number theory. When the Gods favor us, the contribution of the minor arcs may be bounded efficiently, using more analytic methods, such as Cauchy-Schwarz or Weyl differencing. This requires the integer $r$ to be large enough, and then one gets an asymptotic expansion for the number of $r$ perfect $k$th powers that add up to $N$, and it is strictly positive for $N$ large enough!

What one needs to remember is that this works for $r$ quite large. In other words, we can study Diophantine equations whose number of variables is very large compared to the degree. An article by Birch (and which I have not studied well enough…) is called Forms in many variables. Alas, it is completely inoperant for questions such as Fermat's last theorem which has 3 variables and quite a large degree. On the other hand, the circle method is very robust, it allows the equation to be modified – Birch's paper is very flexible – and we know that small modifications of an equation can give rise to dramatic differences regarding its behaviour.

So, as the computer scientists would say, this may be rather a feature than a bug.

Wednesday, February 24, 2021

Transcendence properties of the Painlevé and Schwarzian differential equations

The paper of Joel Nagloo, Model Theory and Differential Equations, just published in the Notices of the AMS, is a beautiful portrait of an area of research that encompasses the end of the 19th century, the full 20th century, up to today. It conflates two totally distinct line of thought. The first line is the theory of differential equations, such as the ones that appear in trigonometry (the sine and cosine functions are solutions of the differential equation $y''+y=0$) or in elaborations of trigonometry (Schwarzian or Painlevé equations). 

The Painlevé equations, named after the mathematician and statesman Paul Painlevé (1863–1933) — he has been minister of war and prime minister during the French 3rd Republic — are a series of 6 differential equations of the second order, of the form $y''=R(t,y,y')$, where $R$ is a rational function. They are characterized by the Painlevé property that all “movable singularities” of their solutions— those which depend on the initial conditions and are not imposed by the form of the equation— are poles. Painlevé classified these equations: up to computation errors later corrected by Gambier and Fuchs, this gives the following irreducible list of 6 equations, in which the variable is $t$, the unknown is $y$, and the Greek letters $\alpha, \beta,\gamma,\delta$ representing parameters:

  1. $y''=6y^2+t$
  2. $y''=2y^3+ty+\alpha$
  3. $tyy''=t(y')^2-yy'+\delta t+\beta y+\alpha y^2+\gamma ty^4$
  4. $y y''=\frac12 (y')^2+\beta+2(t^2-\alpha)y^2+4ty^3+\frac32 y^3$
  5. $y''=(\dfrac1{2y}+\dfrac1{y-1})(y')^2-\dfrac1t y'+\dfrac{(y-1)^2}{t^2} (\alpha y+\beta \dfrac1y)+\gamma\dfrac yt+\delta \dfrac{y(y+1)}{y-1}$
  6. $y''=\frac12(\dfrac1y+\dfrac1{y-1}+\dfrac1{y-t})(y')^2-(\dfrac1t+\dfrac1{t-1}+\dfrac1{y-t})y'+\dfrac{y(y-1)(y-t)}{t^2(t-1)^2}(\alpha+\beta \frac t{y^2}+\gamma \dfrac{t-1}{(y-1)^2}+\delta\dfrac{t(t-1)}{(y-t)^2}$

By irreducible list, it is meant that all equations satisfying the Painlevé property are reducible to either previously known equations (involving elliptic functions or the Ricatti equations), and that those equations are not. Therefore, the solutions of these equations were classically called “transcendental” because they were generally (meaning except for some particular choices of parameters) not rational functions, nor could be derived by algebraic equations. The basic questions that people want to understand here is how much these functions are transcendental.

In this direction, a 2020 theorem of Joel Nagloo is that if you take $n$ distinct solutions $y_1,\dots, y_n$ of a “generic” Painlevé equation of type III or VI, then there is no (nontrivial) algebraic relation between the $2n$ functions $y_1,\dots,y_n$ and their derivatives $y_1',\dots,y_n'$. Here, generic means that the parameters involved in the differential equation they satisfy are algebraically independent over the field of rational numbers.

With Guy Casale and James Freitag, Joel Nagloo has proved a similar theorem for the third order Schwarzian equations associated with a Fuchsian subgroup $\Gamma$ of $\mathrm{PSL}(2,\mathbf R)$. The situation is more subtle: there are possible algebraic relations, but they are completely classified by Hecke correspondences.

The second line of thought is model theory, an area of mathematics classically attached to mathematical logic that tries to understand the intrinsic properties of mathematical theories, whatever they are. To that aim, they do geometry: they consider “definable subsets”, that is, loci defined (in some object of the considered theory) by the type of equations that the theory affords.

For example, if the theory involves fields only, the object could be a large algebraically closed field (such as the field complex numbers) and the equations are essentially polynomial equations, with the exception that they allow quantifiers, and negations, to define their loci. In fact, in this case, it is a theorem, classically attributed to Chevalley, that quantifiers are not needed — one only gets so-called constructible sets.

Another kind of interesting structure is that of differential fields, in which one has the classical field operations, but also an abstract derivation operator (satisfying the standard rules for derivations). Then, definable sets are essentially differential equations.

What model theory does in general is trying to define ways to categorize the definable subsets. One such important invariant would be an analogue of the Zariski dimension of constructible sets in algebraic geometry: the Morley rank. Roughly, a definable set has Morley rank $0$ if it is finite. It has Morley rank at least $n$ if it admits an infinite family of disjoint definable subsets of Morley rank $\geq n-1$. A particular case of sets of Morley rank $1$ are the strongly minimal definable subsets which are infinite and such that any definable subset of it is finite or cofinite (the complementary set is finite).

More importantly, model theory identifies structural properties of theories that make them “neater”, and this gives rise to an “universe of theories”. As you can see on this “map of the universe” (made by Gabriel Conant), the theory ACF of algebraically closed fields is one of the simplest ones that exists, and recent work in model theory tries to clarify what happens in much more complicated ones, characterized by incredible names or acronyms, strongly minimal, stable, distal, o-minimal, NIP, supersimple, NTP₂…

One of the fundamental results in model theory that emerged in the years 1980-2000 is the theory of Zariski geometries and Boris Zilber's “trichotomy principle” that indicates that 1-dimensional (strongly minimal) objects classify in 3 disjoint classes:

  • geometrically trivial: there are essentially no other relation between distinct points of that object, beyond the fact that they belong to it. The generic Painlevé equations furnish important examples of this case, but proving strong minimality is the hard step.
  • group-like: some algebraic group is hidden in the picture, and constrains all possible relations.
  • field-like: this is essentially algebraic geometry over some hidden field.

I must be terse here, stability theory in model theory is an immense area with which I am not enough familiar, and I just insert pictures of three big names in the field, namely Morley, Shelah and Hrushovski:

For more details, and definitely more insight, I refer you to Joel Nagloo's paper quoted above. I also refer you to the Freedom Math Dance blog posts on Model theory and algebraic geometry.