You are currently browsing the category archive for the ‘admin’ category.
In the winter quarter (starting January 5) I will be teaching a graduate topics course entitled “An introduction to analytic prime number theory“. As the name suggests, this is a course covering many of the analytic number theory techniques used to study the distribution of the prime numbers . I will list the topics I intend to cover in this course below the fold. As with my previous courses, I will place lecture notes online on my blog in advance of the physical lectures.
The type of results about primes that one aspires to prove here is well captured by Landau’s classical list of problems:
- Even Goldbach conjecture: every even number greater than two is expressible as the sum of two primes.
- Twin prime conjecture: there are infinitely many pairs which are simultaneously prime.
- Legendre’s conjecture: for every natural number , there is a prime between and .
- There are infinitely many primes of the form .
All four of Landau’s problems remain open, but we have convincing heuristic evidence that they are all true, and in each of the four cases we have some highly non-trivial partial results, some of which will be covered in this course. We also now have some understanding of the barriers we are facing to fully resolving each of these problems, such as the parity problem; this will also be discussed in the course.
One of the main reasons that the prime numbers are so difficult to deal with rigorously is that they have very little usable algebraic or geometric structure that we know how to exploit; for instance, we do not have any useful prime generating functions. One of course can create non-useful functions of this form, such as the ordered parameterisation that maps each natural number to the prime , or one could invoke Matiyasevich’s theorem to produce a polynomial of many variables whose only positive values are prime, but these sorts of functions have no usable structure to exploit (for instance, they give no insight into any of the Landau problems listed above; see also Remark 2 below). The various primality tests in the literature, while useful for practical applications (e.g. cryptography) involving primes, have also proven to be of little utility for these sorts of problems; again, see Remark 2. In fact, in order to make plausible heuristic predictions about the primes, it is best to take almost the opposite point of view to the structured viewpoint, using as a starting point the belief that the primes exhibit strong pseudorandomness properties that are largely incompatible with the presence of rigid algebraic or geometric structure. We will discuss such heuristics later in this course.
It may be in the future that some usable structure to the primes (or related objects) will eventually be located (this is for instance one of the motivations in developing a rigorous theory of the “field with one element“, although this theory is far from being fully realised at present). For now, though, analytic and combinatorial methods have proven to be the most effective way forward, as they can often be used even in the near-complete absence of structure.
In this course, we will not discuss combinatorial approaches (such as the deployment of tools from additive combinatorics) in depth, but instead focus on the analytic methods. The basic principles of this approach can be summarised as follows:
- Rather than try to isolate individual primes in , one works with the set of primes in aggregate, focusing in particular on asymptotic statistics of this set. For instance, rather than try to find a single pair of twin primes, one can focus instead on the count of twin primes up to some threshold . Similarly, one can focus on counts such as , , or , which are the natural counts associated to the other three Landau problems. In all four of Landau’s problems, the basic task is now to obtain a non-trivial lower bounds on these counts.
- If one wishes to proceed analytically rather than combinatorially, one should convert all these counts into sums, using the fundamental identity
(or variants thereof) for the cardinality of subsets of the natural numbers , where is the indicator function of (and ranges over ). Thus we are now interested in estimating (and particularly in lower bounding) sums such as
- Once one expresses number-theoretic problems in this fashion, we are naturally led to the more general question of how to accurately estimate (or, less ambitiously, to lower bound or upper bound) sums such as
or more generally bilinear or multilinear sums such as
for various functions of arithmetic interest. (Importantly, one should also generalise to include integrals as well as sums, particularly contour integrals or integrals over the unit circle or real line, but we postpone discussion of these generalisations to later in the course.) Indeed, a huge portion of modern analytic number theory is devoted to precisely this sort of question. In many cases, we can predict an expected main term for such sums, and then the task is to control the error term between the true sum and its expected main term. It is often convenient to normalise the expected main term to be zero or negligible (e.g. by subtracting a suitable constant from ), so that one is now trying to show that a sum of signed real numbers (or perhaps complex numbers) is small. In other words, the question becomes one of rigorously establishing a significant amount of cancellation in one’s sums (also referred to as a gain or savings over a benchmark “trivial bound”). Or to phrase it negatively, the task is to rigorously prevent a conspiracy of non-cancellation, caused for instance by two factors in the summand exhibiting an unexpectedly large correlation with each other.
- It is often difficult to discern cancellation (or to prevent conspiracy) directly for a given sum (such as ) of interest. However, analytic number theory has developed a large number of techniques to relate one sum to another, and then the strategy is to keep transforming the sum into more and more analytically tractable expressions, until one arrives at a sum for which cancellation can be directly exhibited. (Note though that there is often a short-term tradeoff between analytic tractability and algebraic simplicity; in a typical analytic number theory argument, the sums will get expanded and decomposed into many quite messy-looking sub-sums, until at some point one applies some crude estimation to replace these messy sub-sums by tractable ones again.) There are many transformations available, ranging such basic tools as the triangle inequality, pointwise domination, or the Cauchy-Schwarz inequality to key identities such as multiplicative number theory identities (such as the Vaughan identity and the Heath-Brown identity), Fourier-analytic identities (e.g. Fourier inversion, Poisson summation, or more advanced trace formulae), or complex analytic identities (e.g. the residue theorem, Perron’s formula, or Jensen’s formula). The sheer range of transformations available can be intimidating at first; there is no shortage of transformations and identities in this subject, and if one applies them randomly then one will typically just transform a difficult sum into an even more difficult and intractable expression. However, one can make progress if one is guided by the strategy of isolating and enhancing a desired cancellation (or conspiracy) to the point where it can be easily established (or dispelled), or alternatively to reach the point where no deep cancellation is needed for the application at hand (or equivalently, that no deep conspiracy can disrupt the application).
- One particularly powerful technique (albeit one which, ironically, can be highly “ineffective” in a certain technical sense to be discussed later) is to use one potential conspiracy to defeat another, a technique I refer to as the “dueling conspiracies” method. This technique may be unable to prevent a single strong conspiracy, but it can sometimes be used to prevent two or more such conspiracies from occurring, which is particularly useful if conspiracies come in pairs (e.g. through complex conjugation symmetry, or a functional equation). A related (but more “effective”) strategy is to try to “disperse” a single conspiracy into several distinct conspiracies, which can then be used to defeat each other.
As stated before, the above strategy has not been able to establish any of the four Landau problems as stated. However, they can come close to such problems (and we now have some understanding as to why these problems remain out of reach of current methods). For instance, by using these techniques (and a lot of additional effort) one can obtain the following sample partial results in the Landau problems:
- Chen’s theorem: every sufficiently large even number is expressible as the sum of a prime and an almost prime (the product of at most two primes). The proof proceeds by finding a nontrivial lower bound on , where is the set of almost primes.
- Zhang’s theorem: There exist infinitely many pairs of consecutive primes with . The proof proceeds by giving a non-negative lower bound on the quantity for large and certain distinct integers between and . (The bound has since been lowered to .)
- The Baker-Harman-Pintz theorem: for sufficiently large , there is a prime between and . Proven by finding a nontrivial lower bound on .
- The Friedlander-Iwaniec theorem: There are infinitely many primes of the form . Proven by finding a nontrivial lower bound on .
We will discuss (simpler versions of) several of these results in this course.
Of course, for the above general strategy to have any chance of succeeding, one must at some point use some information about the set of primes. As stated previously, usefully structured parametric descriptions of do not appear to be available. However, we do have two other fundamental and useful ways to describe :
- (Sieve theory description) The primes consist of those numbers greater than one, that are not divisible by any smaller prime.
- (Multiplicative number theory description) The primes are the multiplicative generators of the natural numbers : every natural number is uniquely factorisable (up to permutation) into the product of primes (the fundamental theorem of arithmetic).
The sieve-theoretic description and its variants lead one to a good understanding of the almost primes, which turn out to be excellent tools for controlling the primes themselves, although there are known limitations as to how much information on the primes one can extract from sieve-theoretic methods alone, which we will discuss later in this course. The multiplicative number theory methods lead one (after some complex or Fourier analysis) to the Riemann zeta function (and other L-functions, particularly the Dirichlet L-functions), with the distribution of zeroes (and poles) of these functions playing a particularly decisive role in the multiplicative methods.
Many of our strongest results in analytic prime number theory are ultimately obtained by incorporating some combination of the above two fundamental descriptions of (or variants thereof) into the general strategy described above. In contrast, more advanced descriptions of , such as those coming from the various primality tests available, have (until now, at least) been surprisingly ineffective in practice for attacking problems such as Landau’s problems. One reason for this is that such tests generally involve operations such as exponentiation or the factorial function , which grow too quickly to be amenable to the analytic techniques discussed above.
To give a simple illustration of these two basic approaches to the primes, let us first give two variants of the usual proof of Euclid’s theorem:
Proof: (Multiplicative number theory proof) Suppose for contradiction that there were only finitely many primes . Then, by the fundamental theorem of arithmetic, every natural number is expressible as the product of the primes . But the natural number is larger than one, but not divisible by any of the primes , a contradiction.
(Sieve-theoretic proof) Suppose for contradiction that there were only finitely many primes . Then, by the Chinese remainder theorem, the set of natural numbers that is not divisible by any of the has density , that is to say
In particular, has positive density and thus contains an element larger than . But the least such element is one further prime in addition to , a contradiction.
Remark 1 One can also phrase the proof of Euclid’s theorem in a fashion that largely avoids the use of contradiction; see this previous blog post for more discussion.
Both proofs in fact extend to give a stronger result:
Proof: (Multiplicative number theory proof) By the fundamental theorem of arithmetic, every natural number is expressible uniquely as the product of primes in increasing order. In particular, we have the identity
(both sides make sense in as everything is unsigned). Since the left-hand side is divergent, the right-hand side is as well. But
and , so must be divergent.
(Sieve-theoretic proof) Suppose for contradiction that the sum is convergent. For each natural number , let be the set of natural numbers not divisible by the first primes , and let be the set of numbers not divisible by any prime in . As in the previous proof, each has density . Also, since contains at most multiples of , we have from the union bound that
Since is assumed to be convergent, we conclude that the density of converges to the density of ; thus has density , which is non-zero by the hypothesis that converges. On the other hand, since the primes are the only numbers greater than one not divisible by smaller primes, is just , which has density zero, giving the desired contradiction.
Remark 2 We have seen how easy it is to prove Euler’s theorem by analytic methods. In contrast, there does not seem to be any known proof of this theorem that proceeds by using any sort of prime-generating formula or a primality test, which is further evidence that such tools are not the most effective way to make progress on problems such as Landau’s problems. (But the weaker theorem of Euclid, Theorem 1, can sometimes be proven by such devices.)
The two proofs of Theorem 2 given above are essentially the same proof, as is hinted at by the geometric series identity
One can also see the Riemann zeta function begin to make an appearance in both proofs. Once one goes beyond Euler’s theorem, though, the sieve-theoretic and multiplicative methods begin to diverge significantly. On one hand, sieve theory can still handle to some extent sets such as twin primes, despite the lack of multiplicative structure (one simply has to sieve out two residue classes per prime, rather than one); on the other, multiplicative number theory can attain results such as the prime number theorem for which purely sieve theoretic techniques have not been able to establish. The deepest results in analytic number theory will typically require a combination of both sieve-theoretic methods and multiplicative methods in conjunction with the many transforms discussed earlier (and, in many cases, additional inputs from other fields of mathematics such as arithmetic geometry, ergodic theory, or additive combinatorics).
I’m encountering a sporadic bug over the past few months with the way WordPress renders or displays its LaTeX images on this blog (and occasionally on other WordPress blogs). On most computers, it seems to work fine, but on some computers, the sizes of images are occasionally way off, leading to extremely distorted and fairly unreadable versions of the images appearing in blog posts and comments. A sample screenshot (with accompanying HTML source), supplied to me by a reader, can be found here (in which an image whose dimensions should be 321 x 59 are instead being displayed as 552 x 20). Is anyone else encountering this issue? The problem sometimes can be resolved by refreshing the page, but not always, so it is a bit unclear where the problem is coming from and how one might mitigate it. (If nothing else, I can add it to the bug collection post, once it can be reliably replicated.)
It’s time to (somewhat belatedly) roll over the previous thread on writing the first paper from the Polymath8 project, as this thread is overflowing with comments. We are getting near the end of writing this large (173 pages!) paper, establishing a bound of 4,680 on the gap between primes, with only a few sections left to thoroughly proofread (and the last section should probably be removed, with appropriate changes elsewhere, in view of the more recent progress by Maynard). As before, one can access the working copy of the paper at this subdirectory, as well as the rest of the directory, and the plan is to submit the paper to Algebra and Number theory (and the arXiv) once there is consensus to do so. Even before this paper was submitted, it already has had some impact; Andrew Granville’s exposition of the bounded gaps between primes story for the Bulletin of the AMS follows several of the Polymath8 arguments in deriving the result.
After this paper is done, there is interest in continuing onwards with other Polymath8 – related topics, and perhaps it is time to start planning for them. First of all, we have an invitation from the Newsletter of the European Mathematical Society to discuss our experiences and impressions with the project. I think it would be interesting to collect some impressions or thoughts (both positive and negative) from people who were highly active in the research and/or writing aspects of the project, as well as from more casual participants who were following the progress more quietly. This project seemed to attract a bit more attention than most other polymath projects (with the possible exception of the very first project, Polymath1). I think there are several reasons for this; the project builds upon a recent breakthrough (Zhang’s paper) that attracted an impressive amount of attention and publicity; the objective is quite easy to describe, when compared against other mathematical research objectives; and one could summarise the current state of progress by a single natural number H, which implied by infinite descent that the project was guaranteed to terminate at some point, but also made it possible to set up a “scoreboard” that could be quickly and easily updated. From the research side, another appealing feature of the project was that – in the early stages of the project, at least – it was quite easy to grab a new world record by means of making a small observation, which made it fit very well with the polymath spirit (in which the emphasis is on lots of small contributions by many people, rather than a few big contributions by a small number of people). Indeed, when the project first arose spontaneously as a blog post of Scott Morrrison over at the Secret Blogging Seminar, I was initially hesitant to get involved, but soon found the “game” of shaving a few thousands or so off of to be rather fun and addictive, and with a much greater sense of instant gratification than traditional research projects, which often take months before a satisfactory conclusion is reached. Anyway, I would welcome other thoughts or impressions on the projects in the comments below (I think that the pace of comments regarding proofreading of the paper has slowed down enough that this post can accommodate both types of comments comfortably.)
Then of course there is the “Polymath 8b” project in which we build upon the recent breakthroughs of James Maynard, which have simplified the route to bounded gaps between primes considerably, bypassing the need for any Elliott-Halberstam type distribution results beyond the Bombieri-Vinogradov theorem. James has kindly shown me an advance copy of the preprint, which should be available on the arXiv in a matter of days; it looks like he has made a modest improvement to the previously announced results, improving a bit to 105 (which then improves H to the nice round number of 600). He also has a companion result on bounding gaps between non-consecutive primes for any (not just ), with a bound of the shape , which is in fact the first time that the finiteness of this limit inferior has been demonstrated. I plan to discuss these results (from a slightly different perspective than Maynard) in a subsequent blog post kicking off the Polymath8b project, once Maynard’s paper has been uploaded. It should be possible to shave the value of down further (or to get better bounds for for larger ), both unconditionally and under assumptions such as the Elliott-Halberstam conjecture, either by performing more numerical or theoretical optimisation on the variational problem Maynard is faced with, and also by using the improved distributional estimates provided by our existing paper; again, I plan to discuss these issues in a subsequent post. ( James, by the way, has expressed interest in participating in this project, which should be very helpful.)
Once again it is time to roll over the previous discussion thread, which has become rather full with comments. The paper is nearly finished (see also the working copy at this subdirectory, as well as the rest of the directory), but several people are carefully proofreading various sections of the paper. Once all the people doing so have signed off on it, I think we will be ready to submit (there appears to be no objection to the plan to submit to Algebra and Number Theory).
Another thing to discuss is an invitation to Polymath8 to write a feature article (up to 8000 words or 15 pages) for the Newsletter of the European Mathematical Society on our experiences with this project. It is perhaps premature to actually start writing this article before the main research paper is finalised, but we can at least plan how to write such an article. One suggestion, proposed by Emmanuel, is to have individual participants each contribute a brief account of their interaction with the project, which we would compile together with some additional text summarising the project as a whole (and maybe some speculation for any lessons we can apply here for future polymath projects). Certainly I plan to have a separate blog post collecting feedback on this project once the main writing is done.
The main purpose of this post is to roll over the discussion from the previous Polymath8 thread, which has become rather full with comments. We are still writing the paper, but it appears to have stabilised in a near-final form (source files available here); the main remaining tasks are proofreading, checking the mathematics, and polishing the exposition. We also have a tentative consensus to submit the paper to Algebra and Number Theory when the proofreading is all complete.
The paper is quite large now (164 pages!) but it is fortunately rather modular, and thus hopefully somewhat readable (particularly regarding the first half of the paper, which does not need any of the advanced exponential sum estimates). The size should not be a major issue for the journal, so I would not seek to artificially shorten the paper at the expense of readability or content.
The main purpose of this post is to roll over the discussion from the previous Polymath8 thread, which has become rather full with comments. As with the previous thread, the main focus on the comments to this thread are concerned with writing up the results of the Polymath8 “bounded gaps between primes” project; the latest files on this writeup may be found at this directory, with the most recently compiled PDF file (clocking in at about 90 pages so far, with a few sections still to be written!) being found here. There is also still some active discussion on improving the numerical results, with a particular focus on improving the sieving step that converts distribution estimates such as into weak prime tuples results . (For a discussion of the terminology, and for a general overview of the proof strategy, see this previous progress report on the Polymath8 project.) This post can also contain any other discussion pertinent to any aspect of the polymath8 project, of course.
There are a few sections that still need to be written for the draft, mostly concerned with the Type I, Type II, and Type III estimates. However, the proofs of these estimates exist already on this blog, so I hope to transcribe them to the paper fairly shortly (say by the end of this week). Barring any unexpected surprises, or major reorganisation of the paper, it seems that the main remaining task in the writing process would be the proofreading and polishing, and turning from the technical mathematical details to expository issues. As always, feedback from casual participants, as well as those who have been closely involved with the project, would be very valuable in this regard. (One small comment, by the way, regarding corrections: as the draft keeps changing with time, referring to a specific line of the paper using page numbers and line numbers can become inaccurate, so if one could try to use section numbers, theorem numbers, or equation numbers as reference instead (e.g. “the third line after (5.35)” instead of “the twelfth line of page 54″) that would make it easier to track down specific portions of the paper.)
Also, we have set up a wiki page for listing the participants of the polymath8 project, their contact information, and grant information (if applicable). We have two lists of participants; one for those who have been making significant contributions to the project (comparable to that of a co-author of a traditional mathematical research paper), and another list for those who have made auxiliary contributions (e.g. typos, stylistic suggestions, or supplying references) that would typically merit inclusion in the Acknowledgments section of a traditional paper. It’s difficult to exactly draw the line between the two types of contributions, but we have relied in the past on self-reporting, which has worked pretty well so far. (By the time this project concludes, I may go through the comments to previous posts and see if any further names should be added to these lists that have not already been self-reported.)
The main objectives of the polymath8 project, initiated back in June, were to understand the recent breakthrough paper of Zhang establishing an infinite number of prime gaps bounded by a fixed constant , and then to lower that value of as much as possible. After a large number of refinements, optimisations, and other modifications to Zhang’s method, we have now lowered the value of from the initial value of down to (provisionally) , as well as to the slightly worse value of if one wishes to avoid any reliance on the deep theorems of Deligne on the Weil conjectures.
As has often been the case with other polymath projects, the pace has settled down subtantially after the initial frenzy of activity; in particular, the values of (and other key parameters, such as , , and ) have stabilised over the last few weeks. While there may still be a few small improvements in these parameters that can be wrung out of our methods, I think it is safe to say that we have cleared out most of the “low-hanging fruit” (and even some of the “medium-hanging fruit”), which means that it is time to transition to the next phase of the polymath project, namely the writing phase.
After some discussion at the previous post, we have tentatively decided on writing a single research paper, which contains (in a reasonably self-contained fashion) the details of the strongest result we have (i.e. bounded gaps with ), together with some variants, such as the bound that one can obtain without invoking Deligne’s theorems. We can of course also include some discussion as to where further improvements could conceivably arise from these methods, although even if one assumes the most optimistic estimates regarding distribution of the primes, we still do not have any way to get past the barrier of identified as the limit of this method by Goldston, Pintz, and Yildirim. This research paper does not necessarily represent the only output of the polymath8 project; for instance, as part of the polymath8 project the admissible tuples page was created, which is a repository of narrow prime tuples which can automatically accept (and verify) new submissions. (At an early stage of the project, it was suggested that we set up a computing challenge for mathematically inclined programmers to try to find the narrowest prime tuples of a given width; it might be worth revisiting this idea now that our value of has stabilised and the prime tuples page is up and running.) Other potential outputs include additional expository articles, lecture notes, or perhaps the details of a “minimal proof” of bounded gaps between primes that gives a lousy value of but with as short and conceptual a proof as possible. But it seems to me that these projects do not need to proceed via the traditional research paper route (perhaps ending up on the blog, on the wiki, or on the admissible tuples page instead). Also, these projects might also benefit from the passage of time to lend a bit of perspective and depth, especially given that there are likely to be further advances in this field from outside of the polymath project.
I have taken the liberty of setting up a Dropbox folder containing a skeletal outline of a possible research paper, and anyone who is interested in making significant contributions to the writeup of the paper can contact me to be given write access to that folder. However, I am not firmly wedded to the organisational structure of that paper, and at this stage it is quite easy to move sections around if this would lead to a more readable or more logically organised paper.
I have tried to structure the paper so that the deepest arguments – the ones which rely on Deligne’s theorems – are placed at the end of the paper, so that a reader who wishes to read and understand a proof of bounded gaps that does not rely on Deligne’s theorems can stop reading about halfway through the paper. I have also moved the top-level structure of the argument (deducing bounded gaps from a Dickson-Hardy-Littlewood claim , which in turn is established from a Motohashi-Pintz-Zhang distribution estimate , which is in turn deduced from Type I, Type II, and Type III estimates) to the front of the paper.
Of course, any feedback on the draft paper is encouraged, even from (or especially from!) readers who have been following this project on a casual basis, as this would be valuable in making sure that the paper is written in as accessible as fashion as possible. (Sometimes it is possible to be so close to a project that one loses some sense of perspective, and does not realise that what one is writing might not necessarily be as clear to other mathematicians as it is to the author.)
I recently finished the first draft of the last of my books based on my 2011 blog posts (and also my Google buzzes and Google+ posts from that year), entitled “Spending symmetry“. The PDF of this draft is available here. This is again a rather assorted (and lightly edited) collection of posts (and buzzes, and Google+ posts), though concentrating in the areas of analysis (both standard and nonstandard), logic, and geometry. As always, comments and corrections are welcome.
I’ve just opened the research thread for the mini-polymath4 project over at the polymath blog to collaboratively solve one of the six questions from this year’s IMO. This year I have selected Q3, which is a somewhat intricate game-theoretic question. (The full list of questions this year may be found here.)
This post will serve as the discussion thread of the project, intended to focus all the non-research aspects of the project such as organisational matters or commentary on the progress of the project. The third component of the project is the wiki page, which is intended to summarise the progress made so far on the problem.