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.

Thursday, January 14, 2021

On Rolle's theorem

This post is inspired by a paper of Azé and Hiriart-Urruty published in a French high school math journal; in fact, it is mostly a paraphrase of that paper with the hope that it be of some interest to young university students, or to students preparing Agrégation. The topic is Rolle's theorem.

1. The one-dimensional theorem, a generalization and two other proofs

Let us first quote the theorem, in a nonstandard form.

Theorem.Let $I=\mathopen]a;b\mathclose[$ be a nonempty but possibly unbounded interval of $\mathbf R$ and let $f\colon I\to\mathbf R$ be a continuous function. Assume that $f$ has limits at $a$ and $b$, equal to some element $\ell\in\mathbf R\cup\{+\infty\}$. Then $f$ is bounded from below.

  1. If $\inf_I(f)<\ell$, then there exists a point $c\in I$ such that $f(c)=\inf_I (f)$. If, moreover, $f$ has a right derivative and a left derivative at $c$, then $f'_l(c)\leq0$ and $f'_r(c)\geq0$.
  2. If $\inf_I(f)\geq\ell$, then $f$ is bounded on $I$ and there exists a point $c\in I$ such that $f(c)=\sup_I(f)$. If, moreover, $f$ has a right derivative and a left derivative at $c$, then $f'_l(c)\geq0$ and $f'_r(c)\leq0$.

Three ingredients make this version slightly nonstandard:

  • The interval $I$ may be taken to be infinite;
  • The function $f$ may tend to $+\infty$ at the endpoints of $I$;
  • Only left and  right derivatives are assumed.

Of course, if $f$ has a derivative at each point, then the statement implies that $f'(c)=f'_l(c)=f'_r(c)=0$.

a) As stated in this way, the proof is however quite standard and proceeds in two steps.

  1. Using that $f$ has a limit $\ell$ which is not $-\infty$ at $a$ and $b$, it follows that there exists $a'$ and $b'$ in $I$ such that $a<a'<b'<b$ such that $f$ is bounded from below on $\mathopen ]a;a']$ and on $[b';b\mathclose[$. Since $f$ is continuous on the compact interval $[a';b']$, it is then bounded from below on $I$.
    If $\inf_I(f)<\ell$, then we can choose $\ell'\in\mathbf R$ such that $\inf_I(f)<\ell'<\ell$ and $a'$, $b'$ such that $f(x)>\ell'$ outside of $[a';b']$. Then, let $c\in [a';b']$ such that $f(c)=\inf_{[a';b']}(f)$; then $f(c)=\inf_I(f)$. 
    If $\sup_I(f)>\ell$, then we have in particular $\ell\neq+\infty$, and we apply the preceding analysis to $-f$.
    In the remaining case, $\inf_I(f)=\sup_I(f)=\ell$ and $f$ is constant.
  2. For $x>c$, one has $f(x)\geq f(c)$, hence $f'_r(c)\geq 0$; for $x<c$, one has $f(x)\geq f(c)$, hence $f'_l(c)\leq0$.

The interest of the given formulation can be understood by looking at the following two examples.

  1. If $f(x)=|x|$, on $\mathbf R$, then $f$ attains its lower bound at $x=0$ only, where one has $f'_r(0)=1$ and $f'_l(0)=-1$.
  2. Take $f(x)=e^{-x^2}$. Then there exists $c\in\mathbf R$ such that $f'(c)=0$. Of course, one has $f'(x)=-2xe^{-x^2}$, so that $c=0$. However, it is readily seen by induction that for any integer $n$, the $n$th derivative of $f$ is of the form $P_n(x)e^{-x^2}$, where $P_n$ has degree $n$. In particular, $f^{(n)}$ tends to $0$ at infinity. And, by induction again, the theorem implies that $P_n$ has $n$ distinct roots in $\mathbf R$, one between any two consecutive roots of $P_{n-1}$, one larger than the largest root of $P_n$, and one smaller than the smallest root of $P_n$.

b) In a 1959 paper, the Rumanian mathematician Pompeiu proposed an alternative proof of Rolle's theorem, when the interval $I$ is bounded, and which works completely differently. Here is how it works, following the 1979 paper published in American Math. Monthly by Hans Samelson.

First of all, one uses the particular case $n=2$ of the Levi chord lemma :

Lemma.Let $f\colon [a;b]\to\mathbf R$ be a continuous function such that $f(a)=f(b)$. For every integer $n\geq 2$, there exists $a',b'\in[a;b]$ such that $f(a')=f(b')$ and $b'-a'=(b-a)/n$.

Let $h=(b-a)/n$. From the equality
\[ 0 = f(b)-f(a) = (f(a+h)-f(a))+(f(a+2h)-f(a+h))+\cdots + (f(a+nh)-f(a+(n-1)h), \]
one sees that the function $x\mapsto f(x+h)-f(x)$ from $[a;b-h]$ to $\mathbf R$ does not have constant sign. By the intermediate value theorem, it vanishes at some point $a'\in [a;b-h]$. If $b'=a'+h$, then $b'\in[a;b]$, $b'-a'=(b-a)/n$ and $f(a')=f(b')$.

Then, it follows by induction that there exists a sequence of nested intervals $([a_n;b_n])$ in $[a;b]$ with $f(a_n)=f(b_n)$ and $b_n-a_n=(b-a)/2^n$ for all $n$. The sequences $(a_n)$ and $(b_n)$ converge to a same limit $c\in [a;b]$. Since $f(b_n)=f(c)+(b_n-c) (f'(c) + \mathrm o(1))$, $f(a_n)=f(c)+(a_n-c)(f'(c)+\mathrm o(1))$, one has
\[ f'(c) = \lim \frac{f(b_n)-f(a_n)}{b_n-a_n} = 0. \]

What makes this proof genuinely distinct from the classical one is that the obtained point $c$ may not be a local minimum or maximum of $f$, also I don't have an example to offer now.

c) In 1979, Abian furnished yet another proof, which he termed as the “ultimate” one. Here it is:

It focuses on functions $f\colon[a;b]\to\mathbf R$ on a bounded interval of $\mathbf R$ which are not monotone and, precisely, which are up-down, in the sense that $f(a)\leq f(c)$ and $f(c)\geq f(b)$, where $c=(a+b)/2$ is the midpoint of $f$. If $f(a)=f(b)$, then either $f$ or $-f$ is up-down.

Then divide the interval $[a;b]$ in four equal parts: $[a;p]$, $[p;c]$, $[c;q]$ and $[q;b]$. If $f(p)\geq f(c)$, the $f|_{[a;c]}$ is up-down. Otherwise, one has $f(p)\leq f(c)$. In this case, if $f(c)\geq f(q)$, we see that $f|_{[p;q]}$ is up-down. And otherwise, we observe that $f(q)\leq f(c)$ and $f(c)\geq f(b)$, so that $f|_{[c;b]}$ is up-down. Conclusion: we have isolated within the interval $[a;b]$ a subinterval $[a';b']$ of length $(b-a)/2$ such that $f|_{[a';b']}$ is still up-down.

Iterating the procedure, we construct a sequence $([a_n;b_n])$ of nested intervals, with $(b_n-a_n)=(b-a)/2^n$ such that the restriction of $f$ to each of them is up-down. Set $c_n=(a_n+b_n)/2$.

The sequences $(a_n), (b_n),(c_n)$ satisfy have a common limit $c\in [a;b]$. From the inequalities $f(a_n)\leq f(c_n)$ and $a_n\leq c_n$,  we obtain $f'(c)\geq 0$; from the inequalities $f(c_n)\geq f(b_n)$ and $c_n\leq b_n$, we obtain $f'(c)\leq 0$. In conclusion, $f'(c)=0$.

2. Rolle's theorem in normed vector spaces

Theorem. Let $E$ be a normed vector space, let $U$ be an open subset of $E$ and let $f\colon U\to\mathbf R$ be a differentiable function. Assume that there exists $\ell\in\mathbf R\cup\{+\infty\}$ such that $f(x)\to \ell$ when $x$ tends to the “boundary” of $U$ — for every $\ell'<\ell$, there exists a compact subset $K$ of $U$ such that $f(x)\geq\ell'$ for all $x\in U$ but $x\not\in K$. Then $f$ is bounded below on $U$, there exists $a\in U$ such that $f(a)=\inf_U (f)$ and $Df(a)=0$.

The proof is essentially the same as the one we gave in dimension 1. I skip it here.

If $E$ is finite dimensional, then this theorem applies in a vast class of examples : for example, bounded open subsets $U$ of $E$, and continuous functions $f\colon \overline U\to\mathbf R$ which are constant on the boundary $\partial(U)=\overline U - U$ of $U$ and differentiable on $U$.

However, if $E$ is infinite dimensional, the closure of a bounded open set is no more compact, and it does not suffice that $f$ extends to a function on $\overline U$ with a constant value on the boundary.

Example. — Let $E$ be an infinite dimensional Hilbert space, let $U$ be the open unit ball and $B$ be the closed unit ball. Let $g(x)=\frac12 \langle Ax,x\rangle+\langle b,x\rangle +c$ be a quadratic function, where $A\in\mathcal L(E)$, $b\in E$ and $c\in\mathbf R$, and let $f(x)=(1-\lVert x\rVert^2) g(x)$. The function $f$ is differentiable on $E$ and one has
\[  \nabla f(x) =  (1-\Vert x\rVert^2) ( Ax + b) - 2 (\frac12 \langle Ax,x\rangle + \langle b,x\rangle + c) x. \]
Assume that there exists $x\in U$ such that $\nabla f(x)=0$. Then $Ax+b = \lambda x$, with
\[ \lambda= \frac2{1-\lVert x\rVert ^2} \left(\frac12 \langle Ax,x\rangle + \langle b,x\rangle + c \right). \]
Azé and Hiriart-Urruty take $E=L^2([0;1])$, for $A$ the operator of multiplication by the function $t$,  $b(t)=t(1-t)$, and $c=4/27$. Then, one has $g(x)>0$, hence $\lambda>0$, and $x(t)=\frac1{\lambda-t}b(t)$ for $t\in[0;1]$. This implies that $\lambda\geq 1$, for, otherwise, the function $x(t)$ would not belong to $E$. This allows to compute $\lambda$ in terms of $\mu$,  obtaining $\lambda\leq3/4$, which contradicts the inequality $\lambda\geq 1$. (I refer to the paper of Azé and Hiriart-Urruty for more details.)

3. An approximate version of Rolle's theorem

Theorem. Let $B$ the closed euclidean unit ball in $\mathbf R^n$, let $U$ be its interior, let $f\colon B\to \mathbf R$ be a continuous function on $B$. Assume that $\lvert f\rvert \leq \epsilon $ on the boundary $\partial(U)$ and that $f$ is differentiable on $U$. Then there exists $x\in U$ such that $\lVert Df(x)\rVert\leq\epsilon$.

In fact, replacing $f$ by $f/\epsilon$, one sees that it suffices to treat the case $\epsilon =1$.

Let $g(x)=\lVert x\rVert^2- f(x)^2$. This is a continuous function on $B$; it is differentiable on $U$, with $ \nabla g(x)=2(x-f(x)\nabla f(x))$. Let $\mu=\inf_B(g)$. Since $g(0)=-f(0)^2\leq0$, one has $\mu\leq 0$. We distinguish two cases:

  1. If $\mu=0$, then $\rvert f(x)\lvert \leq \lVert x\rVert$ for all $x\in B$. This implies that $\lVert\nabla f(0)\rVert\leq1$.
  2. If $\mu<0$, let $x\in B$ be such that $ g(x)=\mu$; in particular, $f(x)^2\geq \lVert x\rVert^2-\mu>0$, which implies that $f(x)\neq0$. Since $g\geq0$ on $\partial(U)$, we have $x\in B$, hence $\nabla g(x)=0$. Then $x=f(x)\nabla f(x)$, hence $\nabla f(x)=x/f(x)$. Consequently,
    \[ \lVert \nabla f(x)\rVert \leq \frac{\lVert x\rVert}{f(x)}\leq \frac{\lVert x\rVert}{(\lVert x\rVert^2-\mu)^{1/2}}<1.\]

This concludes the proof. 

Thanks to the Twitter users @AntoineTeutsch, @paulbroussous and @apauthie for having indicated me some misprints and incorrections.

Tuesday, December 22, 2020

Celebrating Ramanujan's birthday — From powers of divisors to coefficients of modular forms

In a Twitter post, Anton Hilado reminded us that today (December 22nd) was the birthday of Srinivasa Ramanujan, and suggested somebody explains the “Ramanujan conjectures”. The following blog post is an attempt at an informal account. Or, as @tjf frames it, my christmas present to math twitter.

The story begins 1916, in a paper Ramanujan published in the Transactions of the Cambridge Philosophical Society, under the not so explicit title: On certain arithmetical functions. His goal started as the investigation of the sum $\sigma_s(n)$ of all $s$th powers of all divisors of an integer $n$, and approximate functional equations of the form
\[ \sigma_r(0)\sigma_s(n)+\sigma_r(1)\sigma_s(n-1)+\dots+\sigma_r(n)\sigma_s(0)
\approx \frac{\Gamma(r+1)\Gamma(s+1)}{\Gamma(r+s+2)} \frac{\zeta(r+1)\zeta(s+1)}{\zeta(r+s+2)}\sigma_{r+s+1}(n) + \frac{\zeta(1-r)+\zeta(1-s)}{r+s} n \sigma_{r+s-1}(n), \]
where $\sigma_s(0)=\dfrac12 \zeta(-s)$, and $\zeta$ is Riemann's zeta function. In what follows, $r,s$ will be positive odd integers, so that $\sigma_s(0)$ is half the value of Riemann's zeta function at a negative odd integer; it is known to be a rational number, namely $(-1)^sB_{s+1}/2(s+1)$, where $B_{s+1}$ is the $(s+1)$th Bernoulli number.

This investigation, in which Ramanujan engages without giving any motivation, quickly leads him to the introduction of infinite series,
\[ S_r = \frac12 \zeta(-r) + \frac{1^rx}{1-x}+\frac{2^r x^2}{1-x^2}+\frac{3^rx^3}{1-x^3}+\dots. \]
Nowadays, the parameter $x$ would be written $q$, and $S_r=\frac12 \zeta(-r) E_{r+1}$, at least if $r$ is an odd integer, $E_r$ being the Fourier expansion of the Eisenstein series of weight $r$. The particular cases $r=1,3,5$ are given special names, namely $P,Q,R$, and Ramanujan proves that $S_s$ is a linear combination of $Q^mR^n$, for integers $m,n$ such that $4m+6n=s+1$. Nowadays, we understand this as the fact that $Q$ and $R$ generated the algebra of modular forms—for the full modular group $\mathrm{SL}(2,\mathbf Z)$.

In the same paper, Ramanujan spells out the system of algebraic differential equations satisfied by $P,Q,R$:
\[ x \frac {dP}{dx} = \frac{1}{12}(P^2-Q),  x\frac{dQ}{dx}=\frac13(PQ-R), x\frac{dR}{dx}=\frac12(PR-Q^2). \]

The difference of the two sides of the initial equation has an expansion as a linear combination of $Q^mR^n$, where $4m+6n=r+s+2$. By the functional equation of Riemann's zeta function, relating $\zeta(s)$ and $\zeta(1-s)$, this expression vanishes for $x=0$, hence there is a factor $Q^3-R^2$.

Ramanujan then notes that

$ x\frac{d}{dx} \log(Q^3-R^2)=P$, so that

\[  P =x\frac{d}{dx} \log \left( x\big((1-x)(1-x^2)(1-x^3)\dots\big)^{24} \right) \]


\[ Q^3-R^2 = 1728 x  \big((1-x)(1-x^2)(1-x^3)\dots\big)^{24}= \sum \tau(n) x^n, \]
an expression now known as Ramanujan's $\Delta$-function. In fact, Ramanujan also makes the relation with elliptic functions, in particular, with Weierstrass's $\wp$-function. Then, $\Delta$ corresponds to the discriminant of the degree 3 polynomial $f$ such that $\wp'(u)^2=f(\wp(u))$. 

In any case, factoring $Q^3-R^2$ in the difference of the two terms, it is written as a linear combination of $Q^mR^n$, where $4m+6n=r+s-10$. When $r$ and $s$ are positive odd integers such that $r+s\leq 12$, there are no such pairs $(m,n)$, hence the difference vanishes, and Ramanujan obtains an equality in these cases. 

Ramanujan is interested in the quality of the initial approximation. He finds an upper bound of the form $\mathrm O(n^{\frac23(r+s+1)})$. Using Hardy–Littlewood's method, he shows that it cannot be smaller than $n^{\frac12(r+s)}$. That prompts his interest for the size of the coefficients of arithmetical functions, and $Q^3-R^2$ is the simplest one. He computes the coefficients $\tau(n)$ for $n\leq30$ and gives them in a table:

Recalling that $\tau(n)$ is $\mathrm O(n^7)$, and not $\mathrm O(n^5)$, Ramanujan states that there is reason to believe that $\tau(n)=\mathrm O(n^{\frac{11}2+\epsilon})$ but not $\mathrm O(n^{\frac{11}2})$. That this holds is Ramanujan's conjecture.

Ramanujan was led to believe this by observing that the Dirichlet series $ \sum \frac{\tau(n)}{n^s} $ factors as an infinite product (“Euler product”, would we say), indexed by the prime numbers:

\[ \sum_{n=1}^\infty \frac{\tau(n)}{n^s} = \prod_p \frac{1}{1-\tau(p)p^{-s}+p^{11-2s}}. \]

This would imply that $\tau$ is a multiplicative function: $\tau(mn )=\tau(m)\tau(n)$ if $m$ and $n$ are coprime, as well as the more complicated relation $\tau(p^{k+2})=\tau(p)\tau(p^{k+1})-p^{11}\tau(p^k)$ between the $\tau(p^k)$. These relations have been proved by Louis Mordell in 1917. He introduced operators (now called Hecke operators) $T_p$ (indexed by prime numbers $p$) on the algebra of modular functions and proved that Ramanujan's $\Delta$-function is an eigenfunction. (It has little merit for that, because it is alone in its weight, so that $T_p \Delta$ is a multiple of $\Delta$, necessarily $T_p\Delta=\tau(p)\Delta$.)

The bound $\lvert{\tau(p)}\rvert\leq p^{11/2}$ means that the polynomial $1-\tau(p) X+p^{11}X^2$ has two complex conjugate roots. This part of the conjecture would be proved in 1973 only, by Pierre Deligne, and required many additional ideas. One was conjectures of Weil about the number of points of algebraic varieties over finite fields, proved by Deligne in 1973, building on Grothendieck's étale cohomology. Another was the insight (due to Michio Kuga, Mikio Sato and Goro Shimura) that Ramanujan's conjecture could be reframed as an instance of the Weil conjectures, and its actual proof by Deligne in 1968, applied to the 10th symmetric product of the universal elliptic curve.