Large gaps between consecutive prime numbers

Kevin Ford, Ben Green, Sergei Konyagin, and myself have just posted to the arXiv our preprint “Large gaps between consecutive prime numbers“. This paper concerns the “opposite” problem to that considered by the recently concluded Polymath8 project, which was concerned with very small values of the prime gap . Here, we wish to consider the largest prime gap that one can find in the interval as goes to infinity.

Finding lower bounds on is more or less equivalent to locating long strings of consecutive composite numbers that are not too large compared to the length of the string. A classic (and quite well known) construction here starts with the observation that for any natural number , the consecutive numbers are all composite, because each , is divisible by some prime , while being strictly larger than that prime . From this and Stirling’s formula, it is not difficult to obtain the bound

A more efficient bound comes from the prime number theorem: there are only primes up to , so just from the pigeonhole principle one can locate a string of consecutive composite numbers up to of length at least , thus

where we use or as shorthand for or .

What about upper bounds? The Cramér random model predicts that the primes up to are distributed like a random subset of density . Using this model, Cramér arrived at the conjecture

In fact, if one makes the extremely optimistic assumption that the random model perfectly describes the behaviour of the primes, one would arrive at the even more precise prediction

However, it is no longer widely believed that this optimistic version of the conjecture is true, due to some additional irregularities in the primes coming from the basic fact that large primes cannot be divisible by very small primes. Using the Maier matrix method to capture some of this irregularity, Granville was led to the conjecture that

(note that is slightly larger than ). For comparison, the known upper bounds on are quite weak; unconditionally one has by the work of Baker, Harman, and Pintz, and even on the Riemann hypothesis one only gets down to , as shown by Cramér (a slight improvement is also possible if one additionally assumes the pair correlation conjecture; see this article of Heath-Brown and the references therein).

This conjecture remains out of reach of current methods. In 1931, Westzynthius managed to improve the bound (2) slightly to

which Erdös in 1935 improved to

and Rankin in 1938 improved slightly further to

with . Remarkably, this rather strange bound then proved extremely difficult to advance further on; until recently, the only improvements were to the constant , which was raised to in 1963 by Schönhage, to in 1963 by Rankin, to by Maier and Pomerance, and finally to in 1997 by Pintz.

Erdös listed the problem of making arbitrarily large one of his favourite open problems, even offering (“somewhat rashly”, in his words) a cash prize for the solution. Our main result answers this question in the affirmative:

Theorem 1 The bound (3) holds for arbitrarily large .

In principle, we thus have a bound of the form

for some that grows to infinity. Unfortunately, due to various sources of ineffectivity in our methods, we cannot provide any explicit rate of growth on at all.

We decided to announce this result the old-fashioned way, as part of a research lecture; more precisely, Ben Green announced the result in his ICM lecture this Tuesday. (The ICM staff have very efficiently put up video of his talks (and most of the other plenary and prize talks) online; Ben’s talk is here, with the announcement beginning at about 0:48. Note a slight typo in his slides, in that the exponent of in the denominator is instead of .) Ben’s lecture slides may be found here.

By coincidence, an independent proof of this theorem has also been obtained very recently by James Maynard.

I discuss our proof method below the fold.

(Matilde Lalin) Attending conferences with small children

[This guest post is authored by Matilde Lalin, an Associate Professor in the Département de mathématiques et de statistique at the Université de Montréal.  I have lightly edited the text, mostly by adding some HTML formatting. -T.]

Mathematicians (and likely other academics!) with small children face some unique challenges when traveling to conferences and workshops. The goal of this post is to reflect on these, and to start a constructive discussion what institutions and event organizers could do to improve the experiences of such participants.

The first necessary step is to recognize that different families have different needs. While it is hard to completely address everybody’s needs, there are some general measures that have a good chance to help most of the people traveling with young children. In this post, I will mostly focus on nursing mothers with infants ( months old) because that is my personal experience. Many of the suggestions will apply to other cases such as non-nursing babies, children of single parents, children of couples of mathematicians who are interested in attending the same conference, etc..

The mother of a nursing infant that wishes to attend a conference has three options:

1. Bring the infant and a relative/friend to help caring for the infant. The main challenge in this case is to fund the trip expenses of the relative. This involves trip costs, lodging, and food. The family may need a hotel room with some special amenities such as crib, fridge, microwave, etc. Location is also important, with easy access to facilities such as a grocery store, pharmacy, etc. The mother will need to take regular breaks from the conference in order to nurse the baby (this could be as often as every three hours or so). Depending on personal preferences, she may need to nurse privately. It is convenient, thus, to make a private room available, located as close to the conference venue as possible. The relative may need to have a place to stay with the baby near the conference such as a playground or a room with toys, particularly if the hotel room is far.
2. Bring the infant and hire someone local (a nanny) to help caring for the infant. The main challenges in this case are two: finding the caregiver and paying for such services. Finding a caregiver in a place where one does not live is hard, as it is difficult to conduct interviews or get references. There are agencies that can do this for a (quite expensive) fee: they will find a professional caregiver with background checks, CPR certification, many references, etc. It may be worth it, though, as professional caregivers tend to provide high-quality services and peace of mind is priceless for the mother mathematician attending a conference. As in the previous case, the mother may have particular needs regarding the hotel room, location, and all the other facilities mentioned for Option 1.
3. Travel without the infant and pump milk regularly. This can be very challenging for the mother, the baby, and the person that stays behind taking care of the baby, but the costs of this arrangement are much lower than in Option 1 or 2 (I am ignoring the possibility that the family needs to hire help at home, which is necessary in some cases). A nursing mother away from her baby has no option but to pump her milk to prevent her from pain and serious health complications. This mother may have to pump milk very often. Pumping is less efficient than nursing, so she will be gone for longer in each break or she will have more breaks compared to a mother that travels with her baby. For pumping, people need a room which should ideally be private, with a sink, and located as close to the conference venue as possible. It is often impossible for these three conditions to be met at the same time, so different mothers give priority to different features. Some people pump milk in washrooms, to have easy access to water. Other people might prefer to pump in a more comfortable setting, such as an office, and go to the washroom to wash the breast pump accessories after. If the mother expects that the baby will drink breastmilk while she is away, then she will also have to pump milk in advance of her trip. This requires some careful planning.Many pumping mothers try to store the pumped milk and bring it back home. In this case the mother needs a hotel room with a fridge which (ideally, but hard to find) has a freezer. In a perfect world there would also be a fridge in the place where she pumps/where the conference is held.

It is important to keep in mind that each option has its own set of challenges (even when expenses and facilities are all covered) and that different families may be restricted in their choice of options for a variety of reasons. It is therefore important that all these three options be facilitated.

As for the effect these choices have on the conference experience for the mother, Option 1 means that she has to balance her time between the conference and spending time with her relative/friend. This pressure disappears when we consider Option 2, so this option may lead to more participation in the conferences activities. In Option 3, the mother is in principle free to participate in all the conference activities, but the frequent breaks may limit the type of activity. A mother may choose different options depending on the nature of the conference.

I want to stress, for the three options, that having to make choices about what to miss in the conference is very hard. While talks are important, so are the opportunities to meet people and discuss mathematics that happen during breaks and social events. It is very difficult to balance all of this. This is particularly difficult for the pumping mother in Option 3: because she travels without her baby, she is not perceived to be a in special situation or in need of accommodation. However, this mother is probably choosing between going to the last lecture in the morning or having lunch alone, because if she goes to pump right after the last lecture, by the time she is back, everybody has left for lunch.

Here is the Hall of Fame for those organizations that are already supporting nursing mothers’ travels in mathematics:

• The Natural Sciences and Engineering Research Council of Canada (NSERC) (search for “child care”) allows to reimburse the costs of child care with Option 2 out of the mother’s grants. They will also reimburse the travel expenses of a relative with Option 1 up to the amount that would cost to hire a local caregiver.
• The ENFANT/ELEFANT conference (co-organized by Lillian Pierce and Damaris Schindler) provided a good model to follow regarding accommodation for parents with children during conferences that included funding for covering the travel costs of accompanying caretakers (the funding was provided by the Deutsche Forschungsgemeinschaft, and lactation rooms and play rooms near the conference venue (the facilities were provided by the Hausdorff Center for Mathematics).Additional information (where to go with kids, etc) was provided on site by the organizers and was made available to all participants all the time, by means of a display board that was left standing during the whole week of the conference.
• The American Institute of Mathematics (AIM) reimburses up to 500 dollars on childcare for visitors and they have some online resources that assist in finding childcare and nannies.

[UPDATED] Added a few more things to the Hall of Fame

• The Joint Mathematics Meetings have been providing onsite childcare in the last few years.
• The Institute for Applied Mathematics (IPAM) provides childcare resources and funding to workshop participants with small children (comment from juliawolf).
• The Simons Institute for the Theory of Computing at Berkeley has a separate lactation room as part of some female washrooms (comment from juliawolf).
• The London Mathematical Society (LMS) offers Childcare Supplementary Grants of up to £200 to all mathematicians based in the UK travelling to conferences and other research schools, meetings or visits (comments from Peter).

In closing, here is a (possibly incomplete) list of resources that institutes, funding agencies, and conferences could consider providing for nursing mother mathematicians:

1. Funding (for cost associated to child care either professional or by an accompanying relative).
2. List of childcare resources (nannies, nanny agencies, drop-in childcare centre, etc).
3. Nursing rooms and playrooms near the conference venue. Nearby fridge.
4. Breaks of at least 20 minutes every 2-3 hours.
5. Information about transportation with infants. More specific, taxi and/or shuttle companies that provide infant car seats. Information regarding the law on infant seats in taxis and other public transportation.
6. Accessibility for strollers.
7. [UPDATED] A nearby playground location. (comment from Peter).

I also find it important that these resources be listed publicly in the institute/conference website. This serves a double purpose: first, it helps those in need of the resources to access them easily, and second, it contributes to make these accommodations normal, setting a good model for future events, and inspiring organizers of future events.

Finally, I am pretty sure that the options and solutions I described do not cover all cases. I would like to finish this note by inviting readers to make suggestions, share experiences, and/or pose questions about this topic.

Khot, Osher, Griffiths

In addition to the Fields medallists mentioned in the previous post, the IMU also awarded the Nevanlinna prize to Subhash Khot, the Gauss prize to Stan Osher (my colleague here at UCLA!), and the Chern medal to Phillip Griffiths. Like I did in 2010, I’ll try to briefly discuss one result of each of the prize winners, though the fields of mathematics here are even further from my expertise than those discussed in the previous post (and all the caveats from that post apply here also).

Subhash Khot is best known for his Unique Games Conjecture, a problem in complexity theory that is perhaps second in importance only to the problem for the purposes of demarcating the mysterious line between “easy” and “hard” problems (if one follows standard practice and uses “polynomial time” as the definition of “easy”). The problem can be viewed as an assertion that it is difficult to find exact solutions to certain standard theoretical computer science problems (such as -SAT); thanks to the NP-completeness phenomenon, it turns out that the precise problem posed here is not of critical importance, and -SAT may be substituted with one of the many other problems known to be NP-complete. The unique games conjecture is similarly an assertion about the difficulty of finding even approximate solutions to certain standard problems, in particular “unique games” problems in which one needs to colour the vertices of a graph in such a way that the colour of one vertex of an edge is determined uniquely (via a specified matching) by the colour of the other vertex. This is an easy problem to solve if one insists on exact solutions (in which 100% of the edges have a colouring compatible with the specified matching), but becomes extremely difficult if one permits approximate solutions, with no exact solution available. In analogy with the NP-completeness phenomenon, the threshold for approximate satisfiability of many other problems (such as the MAX-CUT problem) is closely connected with the truth of the unique games conjecture; remarkably, the truth of the unique games conjecture would imply asymptotically sharp thresholds for many of these problems. This has implications for many theoretical computer science constructions which rely on hardness of approximation, such as probabilistically checkable proofs. For a more detailed survey of the unique games conjecture and its implications, see this Bulletin article of Trevisan.

My colleague Stan Osher has worked in many areas of applied mathematics, ranging from image processing to modeling fluids for major animation studies such as Pixar or Dreamworks, but today I would like to talk about one of his contributions that is close to an area of my own expertise, namely compressed sensing. One of the basic reconstruction problem in compressed sensing is the basis pursuit problem of finding the vector in an affine space (where and are given, and is typically somewhat smaller than ) which minimises the -norm of the vector . This is a convex optimisation problem, and thus solvable in principle (it is a polynomial time problem, and thus “easy” in the above theoretical computer science sense). However, once and get moderately large (e.g. of the order of ), standard linear optimisation routines begin to become computationally expensive; also, it is difficult for off-the-shelf methods to exploit any additional structure (e.g. sparsity) in the measurement matrix . Much of the problem comes from the fact that the functional is only barely convex. One way to speed up the optimisation problem is to relax it by replacing the constraint with a convex penalty term , thus one is now trying to minimise the unconstrained functional

This functional is more convex, and is over a computationally simpler domain than the affine space , so is easier (though still not entirely trivial) to optimise over. However, the minimiser to this problem need not match the minimiser to the original problem, particularly if the (sub-)gradient of the original functional is large at , and if is not set to be small. (And setting too small will cause other difficulties with numerically solving the optimisation problem, due to the need to divide by very small denominators.) However, if one modifies the objective function by an additional linear term

then some simple convexity considerations reveal that the minimiser to this new problem will match the minimiser to the original problem, provided that is (or more precisely, lies in) the (sub-)gradient of at – even if is not small. But, one does not know in advance what the correct value of should be, because one does not know what the minimiser is.

With Yin, Goldfarb and Darbon, Osher introduced a Bregman iteration method in which one solves for and simultaneously; given an initial guess for both and , one first updates to the minimiser of the convex functional

and then updates to the natural value of the subgradient at , namely

(note upon taking the first variation of (1) that is indeed in the subgradient). This procedure converges remarkably quickly (both in theory and in practice) to the true minimiser even for non-small values of , and also has some ability to be parallelised, and has led to actual performance improvements of an order of magnitude or more in certain compressed sensing problems (such as reconstructing an MRI image).

Phillip Griffiths has made many contributions to complex, algebraic and differential geometry, and I am not qualified to describe most of these; my primary exposure to his work is through his text on algebraic geometry with Harris, but as excellent though that text is, it is not really representative of his research. But I thought I would mention one cute result of his related to the famous Nash embedding theorem. Suppose that one has a smooth -dimensional Riemannian manifold that one wants to embed locally into a Euclidean space . The Nash embedding theorem guarantees that one can do this if is large enough depending on , but what is the minimal value of one can get away with? Many years ago, my colleague Robert Greene showed that sufficed (a simplified proof was subsequently given by Gunther). However, this is not believed to be sharp; if one replaces “smooth” with “real analytic” then a standard Cauchy-Kovalevski argument shows that is possible, and no better. So this suggests that is the threshold for the smooth problem also, but this remains open in general. The cases is trivial, and the case is not too difficult (if the curvature is non-zero) as the codimension is one in this case, and the problem reduces to that of solving a Monge-Ampere equation. With Bryant and Yang, Griffiths settled the case, under a non-degeneracy condition on the Einstein tensor. This is quite a serious paper – over 100 pages combining differential geometry, PDE methods (e.g. Nash-Moser iteration), and even some harmonic analysis (e.g. they rely at one key juncture on an extension theorem of my advisor, Elias Stein). The main difficulty is that that the relevant PDE degenerates along a certain characteristic submanifold of the cotangent bundle, which then requires an extremely delicate analysis to handle.

Avila, Bhargava, Hairer, Mirzakhani

The 2014 Fields medallists have just been announced as (in alphabetical order of surname) Artur Avila, Manjul Bhargava, Martin Hairer, and Maryam Mirzakhani (see also these nice video profiles for the winners, which is a new initiative of the IMU and the Simons foundation). This time four years ago, I wrote a blog post discussing one result from each of the 2010 medallists; I thought I would try to repeat the exercise here, although the work of the medallists this time around is a little bit further away from my own direct area of expertise than last time, and so my discussion will unfortunately be a bit superficial (and possibly not completely accurate) in places. As before, I am picking these results based on my own idiosyncratic tastes, and they should not be viewed as necessarily being the “best” work of these medallists. (See also the press releases for Avila, Bhargava, Hairer, and Mirzakhani.)

Artur Avila works in dynamical systems and in the study of Schrödinger operators. The work of Avila that I am most familiar with is his solution with Svetlana Jitormiskaya of the ten martini problem of Kac, the solution to which (according to Barry Simon) he offered ten martinis for, hence the name. (The problem had also been previously posed in the work of Azbel and of Hofstadter.) The problem involves perhaps the simplest example of a Schrödinger operator with non-trivial spectral properties, namely the almost Mathieu operator defined for parameters and by a discrete one-dimensional Schrödinger operator with cosine potential:

This is a bounded self-adjoint operator and thus has a spectrum that is a compact subset of the real line; it arises in a number of physical contexts, most notably in the theory of the integer quantum Hall effect, though I will not discuss these applications here. Remarkably, the structure of this spectrum depends crucially on the Diophantine properties of the frequency . For instance, if is a rational number, then the operator is periodic with period , and then basic (discrete) Floquet theory tells us that the spectrum is simply the union of (possibly touching) intervals. But for irrational (in which case the spectrum is independent of the phase ), the situation is much more fractal in nature, for instance in the critical case the spectrum (as a function of ) gives rise to the Hofstadter butterfly. The “ten martini problem” asserts that for every irrational and every choice of coupling constant , the spectrum is homeomorphic to a Cantor set. Prior to the work of Avila and Jitormiskaya, there were a number of partial results on this problem, notably the result of Puig establishing Cantor spectrum for a full measure set of parameters , as well as results requiring a perturbative hypothesis, such as being very small or very large. The result was also already known for being either very close to rational (i.e. a Liouville number) or very far from rational (a Diophantine number), although the analyses for these two cases failed to meet in the middle, leaving some cases untreated. The argument uses a wide variety of existing techniques, both perturbative and non-perturbative, to attack this problem, as well as an amusing argument by contradiction: they assume (in certain regimes) that the spectrum fails to be a Cantor set, and use this hypothesis to obtain additional Lipschitz control on the spectrum (as a function of the frequency ), which they can then use (after much effort) to improve existing arguments and conclude that the spectrum was in fact Cantor after all!

Manjul Bhargava produces amazingly beautiful mathematics, though most of it is outside of my own area of expertise. One part of his work that touches on an area of my own interest (namely, random matrix theory) is his ongoing work with many co-authors on modeling (both conjecturally and rigorously) the statistics of various key number-theoretic features of elliptic curves (such as their rank, their Selmer group, or their Tate-Shafarevich groups). For instance, with Kane, Lenstra, Poonen, and Rains, Manjul has proposed a very general random matrix model that predicts all of these statistics (for instance, predicting that the -component of the Tate-Shafarevich group is distributed like the cokernel of a certain random -adic matrix, very much in the spirit of the Cohen-Lenstra heuristics discussed in this previous post). But what is even more impressive is that Manjul and his coauthors have been able to verify several non-trivial fragments of this model (e.g. showing that certain moments have the predicted asymptotics), giving for the first time non-trivial upper and lower bounds for various statistics, for instance obtaining lower bounds on how often an elliptic curve has rank or rank , leading most recently (in combination with existing work of Gross-Zagier and of Kolyvagin, among others) to his amazing result with Skinner and Zhang that at least of all elliptic curves over (ordered by height) obey the Birch and Swinnerton-Dyer conjecture. Previously it was not even known that a positive proportion of curves obeyed the conjecture. This is still a fair ways from resolving the conjecture fully (in particular, the situation with the presumably small number of curves of rank and higher is still very poorly understood, and the theory of Gross-Zagier and Kolyvagin that this work relies on, which was initially only available for , has only been extended to totally real number fields thus far, by the work of Zhang), but it certainly does provide hope that the conjecture could be within reach in a statistical sense at least.

Martin Hairer works in at the interface between probability and partial differential equations, and in particular in the theory of stochastic differential equations (SDEs). The result of his that is closest to my own interests is his remarkable demonstration with Jonathan Mattingly of unique invariant measure for the two-dimensional stochastically forced Navier-Stokes equation

on the two-torus , where is a Gaussian field that forces a fixed set of frequencies. It is expected that for any reasonable choice of initial data, the solution to this equation should asymptotically be distributed according to Kolmogorov’s power law, as discussed in this previous post. This is still far from established rigorously (although there are some results in this direction for dyadic models, see e.g. this paper of Cheskidov, Shvydkoy, and Friedlander). However, Hairer and Mattingly were able to show that there was a unique probability distribution to almost every initial data would converge to asymptotically; by the ergodic theorem, this is equivalent to demonstrating the existence and uniqueness of an invariant measure for the flow. Existence can be established using standard methods, but uniqueness is much more difficult. One of the standard routes to uniqueness is to establish a “strong Feller property” that enforces some continuity on the transition operators; among other things, this would mean that two ergodic probability measures with intersecting supports would in fact have a non-trivial common component, contradicting the ergodic theorem (which forces different ergodic measures to be mutually singular). Since all ergodic measures for Navier-Stokes can be seen to contain the origin in their support, this would give uniqueness. Unfortunately, the strong Feller property is unlikely to hold in the infinite-dimensional phase space for Navier-Stokes; but Hairer and Mattingly develop a clean abstract substitute for this property, which they call the asymptotic strong Feller property, which is again a regularity property on the transition operator; this in turn is then demonstrated by a careful application of Malliavin calculus.

Maryam Mirzakhani has mostly focused on the geometry and dynamics of Teichmuller-type moduli spaces, such as the moduli space of Riemann surfaces with a fixed genus and a fixed number of cusps (or with a fixed number of boundaries that are geodesics of a prescribed length). These spaces have an incredibly rich structure, ranging from geometric structure (such as the Kahler geometry given by the Weil-Petersson metric), to dynamical structure (through the action of the mapping class group on this and related spaces), to algebraic structure (viewing these spaces as algebraic varieties), and are thus connected to many other objects of interest in geometry and dynamics. For instance, by developing a new recursive formula for the Weil-Petersson volume of this space, Mirzakhani was able to asymptotically count the number of simple prime geodesics of length up to some threshold in a hyperbolic surface (or more precisely, she obtained asymptotics for the number of such geodesics in a given orbit of the mapping class group); the answer turns out to be polynomial in , in contrast to the much larger class of non-simple prime geodesics, whose asymptotics are exponential in (the “prime number theorem for geodesics”, developed in a classic series of works by Delsart, Huber, Selberg, and Margulis); she also used this formula to establish a new proof of a conjecture of Witten on intersection numbers that was first proven by Kontsevich. More recently, in two lengthy papers with Eskin and with Eskin-Mohammadi, Mirzakhani established rigidity theorems for the action of on such moduli spaces that are close analogues of Ratner’s celebrated rigidity theorems for unipotently generated groups (discussed in this previous blog post). Ratner’s theorems are already notoriously difficult to prove, and rely very much on the polynomial stability properties of unipotent flows; in this even more complicated setting, the unipotent flows are no longer tractable, and Mirzakhani instead uses a recent “exponential drift” method of Benoist and Quint as a substitute. Ratner’s theorems are incredibly useful for all sorts of problems connected to homogeneous dynamics, and the analogous theorems established by Mirzakhani, Eskin, and Mohammadi have a similarly broad range of applications, for instance in counting periodic billiard trajectories in rational polygons.