E. Kowalski’s blog

I was in Bordeaux this week until yesterday to attend (parts of) the conference Quantum Chaos 2009 organized by M-L. Chabanol, S. Nonenmacher and G. Ricotta. This was a very enjoyable stay, although it was threatened by natural chaos on the left due to a terrible storm that went over the South West part of France last Saturday, and by more social chaos on the right from a fairly general strike tomorrow, including that of the public transportation system and of the university personnel restaurant in Bordeaux.

I will not try to give a summary of what Quantum Chaos is, since I am not at all an expert in this field in general, and also because Arnd Bäcker, the first lecturer, gave a wonderful overall presentation from the point of view of mathematical physics (which is where the subject grew). The downloadable version does not include the very nice computer simulations that he presented, unfortunately.

I lectured myself on the part of the subject that I know (a bit) about: the Arithmetic Quantum Unique Ergodicity Conjecture of Rudnick and Sarnak [see this survey of J. Marklof for some background on this and other arithmetic aspects of Quantum Chaos], which claimed that the probability measures on the modular surface

defined by

for eigenfunctions f of the Laplace operator which are of norm 1 and are also eigenfunctions of all Hecke operators, should converge weakly to the Poincaré measure

on the modular surface. I said “claimed” because this is a conjecture no more: rather dramatically, G. Prakash pointed out at the end of my second lecture that K. Soundararajan had posted on arXiv the same morning a preprint containing a proof of the last missing step required to verify the correctness of the conjecture! This is based on the ground-breaking work of E. Lindenstrauss, who had used ergodic theoretic methods to prove that any weak limit had to be a multiple of the Poincaré measure, but without being able to avoid the possibility that some of the unit mass would be lost (“escape in the cusp”): Soundararajan manages to exclude this last possibility. (I find somewhat ironic that this happened the first day probably in months where I didn’t have time to check the arXiv posting in the morning…)

What I had lectured on was the recent work of R. Holowinsky, and of (another work of) Soundararajan. roughly speaking, Holowinsky had managed to prove the conjecture either “with very few exceptions” or under the Ramanujan-Petersson conjecture for Hecke eigenforms, using a very beautiful and clever sieve argument (the link between sieve methods and a conjecture motivated by mathematical physics is part of the beauty of mathematics…) Soundararajan, also with a remarkable argument of analytic number theory, had proved a fairly general “weak subconvexity” result for values of L-functions satisfying the Ramanujan-Petersson conjecture. This gave — among other things! — another proof of the Unique Ergodicity with very few exception (assuming the Ramanujan-Petersson) conjecture, because of earlier work, in particular, of Sarnak and a formula of Watson linking the desired equidistribution to some special values of triple product L-functions.

Although the (brand new) result of Soundararajan means that these two works are not needed any more to try to prove the original conjecture, their interest is not just as beautiful pieces of mathematics, as Holowinsky and Soundararajan show in another joint work: their methods work also for holomorphic cusp forms of large weight (still Hecke eigenfunctions). There, on the one hand, we have the Ramanujan-Petersson conjecture (by Deligne’s one-two knockout step: first linking it with the Riemann Hypothesis over finite fields, and then proving the latter). Also, on the other hand, a rather wonderful stroke of good fortune arises: the two “exceptional subsets”, where each method fails to give equidistribution, are disjoint! So Holowinsky and Soundararajan end up proving the holomorphic case of AQUE by a completely devious route (which recalls the first ineffective solution of the class number problem of Gauss, where either assuming that GRH holds, or that it doesn’t, led to the result!)

It is also interesting to note that this holomorphic case of AQUE is currently inaccessible to ergodic-theoretic methods, the reason being (apparently) that there is no “classical dynamics” behind it — the geodesic flow being the classical system underlying the original conjecture. (This was explained to me by M. Einsiedler, whose lectures in Bordeaux cover the ergodic-theoretic methods of Lindenstrauss).

Other lecturers in the programme are P. Kurlberg, describing the quantization of toral automorphisms and the problems that arise (where it is again very satisfying from the point of view of the unity of mathematics that the Riemann Hypothesis over finite fields turns out to play a big role), and J. Keating who will lecture Thursday and Friday on Quantum Graphs (which, unfortunately, I know nothing about, but I’ll try to find a good survey to link to).

When D. Goldston, J. Pintz and C. Yildirim proved the spectacular result that the gaps between consecutive primes satisfy

(which means that those gaps are infinitely often smaller than an arbitrarily small multiple of their average size) there was a great hope that maybe some of their ideas would lead to a proof of the much stronger result

and possibly to the twin prime conjecture (in the form stating that this liminf should be equal to 2). Since then, titles of lectures like Goldston’s “Revenge of the twin prime conjecture” have shown that this hope was, maybe, somewhat sanguine.

The work of Goldston-Pintz-Yildirim has been the subject of a number of surveys, and there is an excellent recent blog post on this topic by T. Tao (the first paragraph of which links to three of these surveys). In this post, I wish to discuss a complementary topic which is not addressed in detail in any of these: what, exactly, is needed to go to finite gaps (i.e., to prove (**))? why did it seem reasonable to hope that it might be accessible, and how hard can we guess this extra step to actually be? Some of this is discussed in my own Bourbaki report, but there will be new information towards the end, based on some discussions I had with É. Fouvry after I had written it.

The basic data that the method of Goldston-Pintz-Yildirim depends on is the quantitative equidistribution of primes in arithmetic progression, which is measured by the functions

defined for any modulus q> 0 and residue class a modulo q, coprime with q. The basic information is that, in various senses, E(x;q,a) is small, and the difficulty (in this method as well as in countless other problems of analytic number theory) is that we must quantify this intuition in various ranges of the three variables, and most often uniformly.

What is known, and gives a reasonably strong foundation for further results and expectations, is that

for any A>0, for some constant C(A) which is independent of q and a, but which is however ineffective (not actually computable for any given A). This looks good but recall the “main term” involved is

and because the Euler function is of size roughly q (up to small oscillations which are not important in this post), this means that the estimate we obtain is, in fact, trivial (and turns out to be useless) if q grows with x faster than any power of logarithm. For instance, this theorem (due to Siegel and Walfisz) doesn’t give any information about

if q is a small power of x (in particular, one can not guarantee the existence of primes occuring in the summation even if the main term x/φ(q) suggests there should be plenty of them).

Now, what is needed for (*) and (**)? (Note that by jumping to this, I — purposely in this post — am leaving aside the extremely ingenious and beautiful original ideas of Goldston, Pintz and Yildirim). Well, for (*), it suffices to know some upper bound on average over q up to, roughly, the square root of x, and uniformly over a: it suffices to find some B, depending on A, such that

(where the constant C(A) may of course be another one than the one before). Now this is much stronger than the Siegel-Walfisz Theorem, and at first sight one may wonder if this is reasonable. That it is, indeed, expected, was known for a long time before it was proved unconditionally by Bombieri and Vinogradov (independently) in the 1960′s. The reason is that this estimate (with some specific value of B which I won’t write down explicitly) is a trivial consequence of the Generalized Riemann Hypothesis for Dirichlet L-functions (widely expected to be true…) and the so-called “Explicit formulas” which transform sums over primes in arithmetic progressions into sums over the zeros of the relevant L-functions. Indeed, as in this post, the “trivial” refers here to transforming an identity (or something close to it) to an upper bound by using the triangle inequality for a sum.

(Of course, the fact that this was expected does not mean that the result is easy: proving the Bombieri-Vinogradov theorem was a remarkable breakthrough in analytic number theory, and it was one of the main achievements that led to Bombieri being awarded the Fields Medal in 1974).

So, in a sense, the Bombieri-Vinogradov theorem explains why (*) is a theorem today. As to (**), much more is needed: it would suffice to extend the Bombieri-Vinogradov theorem to any range of modulus larger than the square-root of x, i.e., to prove, for any A, that

for some δ>1/2 (independent of A); precisely, if this holds for a given δ, it follows that there are infinitely many primes at a finite distance from each other, the bound on the distance depending on δ. Currently (as far as I know), assuming the best possible result, which is that any δ<1 will work, one gets primes at a distance at most 16 from each other.

But any estimate of the type above remains completely conjectural! And based on the previous description of the Bombieri-Vinogradov Theorem, one can understand: the latter is, in some sense, an unconditional confirmation of what the Generalized Riemann Hypothesis suggests should be true. But GRH says nothing about primes in arithmetic progressions where the modulus exceeds (roughly) the square root of the length! So estimates like the one we need are unknown, even under the assumption of GRH.

This may lead to some scratching of chin, and some wonderment whether those statements are, in fact, correct. This is definitely a legitimate question: based on very clever ideas of Maier, Friedlander and Granville have shown that some very optimistic versions where the bound on the modulus is

are definitely false. But there are reasons to hope, at least for δ just slightly larger than 1/2, if one remembers that GRH implies the Bombieri-Vinogradov by a trivial treatment of a sum over zeros of L-functions: surely, the ordinates of the latter must be distributed randomly enough to lead to compensations when the sum is not submitted to the rough treatment of the triangle inequality!

A further — and more convincing — cause to hope is given by the remarkable work of Fouvry and Iwaniec first, strenghtened later by Bombieri, Friedlander and Iwaniec: for certain specific types of weights (arising naturally in sieve theory), and for certain explicit δ>1/2 (namely any δ<4/7 in the strongest version), we have

This type of statements (which go back to the beginning to mid 1980′s) rank among the deepest known results in analytic number theory. Indeed, note that, for the reason sketched above, this can not be deduced from the Generalized Riemann Hypothesis, and yet it is an unconditional result: hence, it goes well beyond the already remarkable Bombieri-Vinogradov Theorem. (It would actually be interesting to have a proof of such results assuming — and using! — GRH, since apparently it involves in some mysterious way the detection of randomness in the ordinates of zeros of L-functions, but I don’t think there has been any work in this direction).

The proofs of these bounds for primes in arithmetic progressions to large moduli depend essentially on general estimates from the spectral theory of Kloosterman sums (due largely to Deshouillers and Iwaniec), and thus (ultimately) on properties of modular forms and eigenfunctions of the hyperbolic Laplace operator on finite area hyperbolic surfaces. Among applications, one may mention a result of Fouvry which was used (among other applications) in the first version of the deterministic polynomial-time algorithm for primality testing of Agrawal, Kayal and Saxena.

Coming back to (**), the fact that the exponent 4/7 is larger than 1/2 may suggest that the job is done. Unfortunately, there are two difficulties: (i) the weights γ_q are not arbitrary, and can not be chosen to give the absolute value in the summation; (ii) more importantly, the residue class a is now fixed. This second condition is the crucial one, because the method of Goldston, Pintz and Yildirim fundamentally requires to use more than one residue class.
Despite renewed efforts, it would seem to be very hard to obtain (***) using anything like the methods of Bombieri, Fouvry, Friedlander and Iwaniec.

However, one shouldn’t discard any hope too quickly: looking at the proof of (**), one realizes that it is not (***) really which is needed, but the following type of inequality

where the moduli q can be restricted to squarefree ones while the set of residue classes in the inner sum is

for some integral (monic) polynomial which is fixed (though its degree may be fairly high). This special structure may be more accessible, because

for some (fixed) exponent E>0, so the number of residue classes considered is, on average, not very large. In particular, note that a trivial summation of the Bombieri-Fouvry-Friedlander-Iwaniec bounds over

shows (together with the information that the implied constant is polynomial in a) that their result does hold uniformly over sets with that many residue classes… except that those must, in the current state of knowledge, be located in the beginning interval, and not be spread out all over the residue classes, like the roots of P modulo q are likely to be.

Fouvry has looked a little bit at this type of inequalities, starting at the beginning; unfortunately, his rough computations give no particular reason to be optimistic at this point: it seems one needs to understand averages of very short Kloosterman sums in many variables, and both the length and the number of variables depend on the degree of the polynomial. Now, this polynomial is not arbitrary: in a somewhat delicate way, its degree ends up dictating for which value of θ>1/2 one needs to get (****) in order to derive (**). But the larger the degree, the smaller the exponent one can actually achieve assuming the most optimistic bounds for those short exponential sums (which are utterly out of reach anyway).

The conclusion? Well, one which seems to be unavoidable is that it really looks like a significant new idea is needed to get bounded gaps between primes: either to bypass the type of strategies which have been successful up to now in studying the distribution of primes in arithmetic progressions; or to find a way to bring those techniques to an entirely new level!

Should the proof of a theorem (taken in isolation) allow us to reconstitute precisely its statement? That seems like an interesting question, and I guess my personal answer would be that it should, more or less, given maybe enough context information (and with some restrictions on the length of the proof).

However, there might be other opinions. For instance, it is clear that if the proof does not make use, explicitly, of one of the assumptions, by hiding it in a computation or check left to the reader, then the reconstruction from the proof might miss it (I mentioned earlier reading a proof of the Banach-Alaoglu theorem where the important fact that one works with the weak-* topology is hidden from view).

In this spirit, today’s challenge is to find the theorem for which this short sentence is supposedly a proof:

The heat kernel defines a renormalization-group invariant plaquette action.

Back in the days when fractals where the most fashionable thing, I had heard of fractal cabbages, and seen pictures of them. However, they are typically not available in French or American stores, so I didn’t see a real one until noticing that they are very common in Swiss supermarkets. Here’s a picture of one, but I should say that pictures do not quite convey the actual feel of seeing and handling this vegetable (not to mention eating it — and it is indeed quite tasty). The diameter (of horizontal cross-sections) of the specimen displayed here is between 10 and 15 centimeters, and the height is slightly larger.

Every once in a while, “at an uncertain hour”, algebraic fever returns, and I look at inequalities with mistrust. (This is a dramatized introduction, to be sung to the tune of The Rime of the Ancient Mariner; as Wodehouse would say, the poet Coleridge puts these things well.)

Compared with an identity such as

which one can easily imagine occupying pride of place in a platonic heaven, what is one to make of an inequality like

where

for every prime number p? (This is the famous Weil bound for Kloosterman sums). Or what should one think of a statement like: for every ε>0, there exists a constant C_ε such that

for all positive integers n, d(n) being the number of positive divisors of n? (See this post by T. Tao for an enlightening discussion of this well-known inequality, which was apparently first proved by Runge in 1885, in a paper in Acta Mathematica on solvable equations of the type x⁵+ux+v=0 — this slightly surprising reference is given in Montgomery and Vaughan’s Multiplicative Number Theory).

The suspicion that inequalities are not quite “right” may have led to a number of devices to transform them into equalities (or identities) as much as possible. For instance, one may say that any inequality of the type

where A is an arbitrarily complicated real-valued expression (notice that any inequality could be written in this way…) is a bad version of an identity

where B is some more intrinsic (and possibly even more complicated) expression. Note that this is in fact of some importance in logic (and in algebra, with the theory of real fields): extending slightly, it shows that the positive integers are definable existentially in the integers by the first order formula φ(n) given by

in the language of rings (and let me recall the much subtler formula of J. Robinson that extracts the integers from the rationals, though not purely existentially — whether the latter is possible is still an open problem).

I have also heard it said that Selberg sometimes claimed that his whole career was built on the fact that the square of a real number is non-negative, but I have no idea if he actually did — at the very least, it seems to completely ignore the Trace Formula…

Turning to Kloosterman sums, algebraists certainly sleep better at night knowing that the “correct” statement is that

for some complex number α_p of modulus 1, which can be defined in some beautifully elegant manner: the Weil bound then becomes a simple matter of neglecting part of this interesting information, and only remembering the triangle inequality.

Another way of understanding certain inequalities is to rephrase them as instances of bounds arising from the norm of a linear operator between normed vector spaces: if T is such an operator, its norm is equal to the infimum of numbers C such that

for all vectors in the source space. So, for instance, one of the large sieve inequalities, as a purely analytic statement, is that for any N and any complex numbers a_n we have

and one could say that N-1+Q² is here a placeholder for the “right” quantity which is simply

the norm of some (fairly obvious) linear map between two finite-dimensional Hilbert spaces. The implied criticism would be that it is only because we are not clever enough to find a formula for this norm that we have to do with disappointing inequalities. (Though Ramaré’s investigations of eigenvalues of the large sieve operator show that this operator is in fact quite mysterious: in the critical case where N and Q² are of comparable size, there seems ot be a limiting distribution for the eigenvalues, but it has a very strange look).

This method of introducing linear operators applies for many well-known inequalities, for instance the Cauchy-Schwarz and Hölder inequalities: they can be interpreted as giving the formula for the norms of linear forms

between suitable L_p spaces.

But now, this ghastly tale being told, I come back to my analytic senses: I am sure that there is much more to inequalities than being des identités manquées! But it’s not clear if, or how, this might be formalized. Maybe what is needed is a very elementary inequality where the best possible constant is known, but involves much more sophisticated notions than the statement of the inequality? Possibly, the Hilbert inequality

(again with arbitrary complex coefficients a_n and b_m, and with arbitrary N) might be interpreted in this way. The constant π is here best possible, but since π occurs everywhere from the most elementary mathematics, it may not be “sophisticated” enough to carry conviction. Are there other known operators with similarly simple descriptions and norm known to be very complicated numbers (in some sense)?

Another possibility towards proving that inequalities are unavoidable would be to look at something like the function

and hope to show that, in some sense, it is “much more complicated” than the divisor function, and thus unlikely to be replaceable by something nicer — though in that specific case, it seems not clear that it can be true, because the divisor function itself is really quite a complicated object already (for instance, with respect to its algorithmic computability).

One situation in which, I think, there is a fairly general consensus that the inequality can not be replaced in a non-tautological manner even by an asymptotic formula, is that of class numbers of imaginary quadratic fields, a famous problem going back to Gauss. This can in fact be described very elementarily (though the algebraic interpretation is probably the only way to justify why one would look at this particular question): for a positive squarefree number d, let h(d) be the number of integral solutions (a,b,c) , with no common factor e>1, to the (in)equations

The question is then to know the size of h(d), and this is a notoriously difficult problem. It is relatively simple to show an inequality like

and it is further known that, for every ε>0, there is a constant C_ε>0 such that

(a theorem due to Siegel, which is much harder, and for which no one knows how to compute C_ε if ε is small enough; and here I can’t help quoting what may be the century’s greatest understatement, taken from MathWorld: “There are at least two Siegel’s theorems“).

Those two inequalities show that the class number is of size about d^1/2, in some sense, but after extensive work, I don’t think anyone who has looked at the problem in some depth would expect to get even an asymptotic formula

where the function g(d) is “elementary” in a reasonable sense. Of course, this is not a formal statement, and it’s not clear if a precise version is possible (this may be another interesting somewhat meta-mathematical problem to consider…)

In that particular case, algebraists might exclaim that the Class Number Formula of Dirichlet provides the required “identity” version of h(d): up to minor (explicit) factors, we have

relating the mysterious class number to a special value of a Dirichlet L-function associated with the underlying imaginary quadratic field. But this gives essentially no information on the size of h(d), so this transcription is not as convincing as what we saw in the case of Kloosterman sums. (Although this formula has been the basis of the deepest estimates for h(d), which have been deduced from bounds for L-functions.)