Deterministic methods to find primes

I’ve uploaded to the arXiv the polymath research paper “Deterministic methods to find primes“, which is the outcome of the Polymath4 collaborative mathematics project, and has been submitted to Mathematics of Computation.

The objective of this paper was to find fast deterministic algorithms to solve the following problem:

Given a (large) integer x, find a prime p larger than x.

Thanks to the AKS algorithm, a number of size O(x) can be deterministically tested for primality in time .   By Bertrand’s postulate, there is always at least one prime between x and 2x; by testing each one of these integers in turn for primality, one can thus obtain a deterministic algorithm to find primes in time .

But one should be able to do much better.  For comparison, if probabilistic algorithms are allowed, then by randomly selecting integers between x and 2x to test for primality, it is easy to see from the prime number theorem that one will succeed in obtaining a prime with high probability in time .  However, after some effort we were not able to “derandomise” this algorithm to create any reasonable deterministic counterpart.  Nevertheless, we conjecture that a deterministic algorithm with run time exists.  Such algorithms can be easily obtained if one assumes some standard conjectures regarding the primes (e.g. Cramer’s conjecture on prime gaps), but we do not know of any deterministic algorithms which can be unconditionally proved to run in time .

Currently, the best known deterministic algorithm is due to Lagarias and Odlyzko, and has a run time of .  Roughly speaking, it is based on the ability to compute the prime counting function in time ; once one has this function, one can detect which intervals contain primes or not, and then starting from Bertrand’s postulate and performing a binary search one can then locate a prime.  The Lagarias-Odlyzko argument is based on approximating by a certain integral of the Riemann zeta function, which one then approximates in turn by quadrature.

We conjecture that one should be able to compute in faster time, and in particular in time for some .  Unfortunately, we were not able to achieve this; however, we do have a non-trivial method to compute the parity of in such a time; a bit more generally (and oversimplifying a little bit), we can compute various projections of the prime polynomial modulo some small polynomials g.  This seems close to being able to achieve the goal of detecting whether primes exist in a given interval, but unfortunately some additional work seems to be needed in that area.  Still, the methods used to get the parity seem to be interesting (involving the Dirichlet hyperbola method, a piecewise approximation of the hyperbola, and the Strassen fast multiplication algorithm), and these techniques might be useful for some other problems.

Roughly speaking, the idea to compute the parity of is as follows.  The first observation is that, for square-free n, the number of divisors of n is equal to 2 when n is a prime, and a multiple of 4 otherwise.  So to compute the parity of , it suffices to compute modulo 4 (or more precisely, the restriction of this sum to squarefree n).

The restriction to squarefree numbers turns out to be relatively easy to handle, so we ignore it.  Since , we can rewrite

.

So it suffices to find an efficient way to count the number of lattice points below the hyperbola .

The classic way to do this is via the Dirichlet hyperbola method.  This lets one rewrite the above expression as

(assuming is not a perfect square, where is the greatest integer function).  One can then compute this quantity in time without difficulty.

To improve this to , we used some ideas of Vinogradov, based on using Diophantine approximation to find moderately long arithmetic progressions on which the map is linear, and thus easily summable.

The same method extends to the polynomial setting, though now, instead of summing an arithmetic progression, one has to find an efficient way to sum quadratic sums such as .  This turns out to be possible by expressing this sum as a matrix product and then using fast matrix multiplication algorithms.

There is still some scope to improve the results and methods further; Ernie Croot is pursuing this with two undergraduate students, David Hollis and David Lowry,

Mini-polymath2 discussion thread

I’ve just opened the Mini-polymath2 project over at the polymath blog.  I decided to use Q5 from the 2010 IMO in the end, rather than Q6, as it seems to be a little bit more challenging and interesting.

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.     (Is it possible for one blog thread to “live-blog” another?) The third component of the project is the wiki page, which is intended to summarise the progress made so far on the problem.

As with mini-polymath1, I myself will be serving primarily as a moderator, and hope other participants will take the lead in the research and in keeping the wiki up-to-date.   (Ideally, once we get all the kinks in the format ironed out, it should be possible for anyone with a blog and an interested pool of participants to start their own mini-polymath project, without being overly dependent on one key contributor.)

Mini-polymath2 start time

In view of feedback, I have decided to start the mini-polymath2 project at 16:00 July 8 UTC, at which time I will select one of the 2010 IMO questions to solve.  The actual project will be run on the polymath blog; this blog will host the discussion threads and post-experiment analysis.

Organising mini-polymath2

This is a continuation of the preceding post regarding the setting up of the mini-polymath2 project.  From the discussion, it seems that it is best to start at some fixed time, either on July 8 or July 9, to ensure an orderly opening to the project and also so that I can select which of the six questions would be most suitable for such a project.

I have set up a placeholder wiki page for the project here, though right now it is necessarily quite bare.

There wasn’t much feedback on where to host the polymath project, but I am thinking of hosting the main project over on the polymath blog, in order to take advantage of the slightly better threading format there (numbered comments and nested comments in particular, although unfortunately there is no comment editing capability), and also because it would be technically easier to have multiple moderators on that blog.   When the project begins, I will also announce it in a brief post on this blog, which can then serve as the “meta” or “discussion” page for the project.

The one thing that I need to fix before the project begins is the starting time.   I do not know exactly when the Kazakhstan local IMO organising committee will release the full list of questions, but presumably they should be available by, say, noon July 8 at Kazazhstan time (GMT+4), or about 8am July 8 GMT, which would probably be the earliest feasible starting time.   Given that I am at GMT-8, the next reasonable starting time would be about eight hours later, at 4pm July 8 GMT.  Below is a poll regarding what times participants would most prefer and least prefer, spaced at 4 hour intervals:

I’ve set it so that up to three answers may be selected.  I am also open to other suggestions regarding the starting time.  I encourage everyone who is interested in participating to select some times for the poll.  Note: the times given are with respect to GMT.  A list of some representative time zones and their UTC offsets (which are more or less equivalent to GMT offsets, modulo daylight savings issues) can be found here.

With this feedback, I should be able to select a reasonable starting time.  The previous mini-polymath was active for about 48 hours (in particular, continuing to produce alternate solutions well after the first one was posted), and I would expect something similar here.  I am hoping therefore that provided there is some effort by participants to help bring people up to speed, that one could drop in even several hours after the formal start of the project and still be able to contribute.

Future mini-polymath project: 2010 IMO Q6?

About a year ago, as an experiment, I set up on this blog a “mini-polymath” project, in which readers were invited to collaboratively solve the sixth question on the 2009 International Mathematical Olympiad (aka “the grasshopper problem”).  After two or three days of somewhat chaotic activity, multiple solutions to this problem were obtained, and have been archived on this page.

In the post-mortem discussion of this experiment, it became clear that the project could have benefited from some more planning and organisation, for instance by setting up a wiki page early on to try to collect strategies, insights, partial results, etc.  Also, the project was opened without any advance warning or prior discussion, which led to an interesting but chaotic opening few hours to the project.

About a month from now, the 51st International Mathematical Olympiad will be held in Kazahkstan, with the actual problems being released on July 7 and 8.  Traditionally, the sixth problem of the Olympiad (which would thus be made public on July 8) is the hardest, and often the most interesting to solve.  So in the interest of getting another data point for the polymath process, I am thinking of setting up another mini-polymath for this question (though I of course do not know in advance what this question will be!).  But this time, I would like to try to plan things out well in advance, to see if this makes much of a difference in how the project unfolds.

So I would like to open a discussion among those readers who might be interested in such a project, regarding the logistics of such a project.  Some basic issues include:

1. Date and time. Clearly, the project cannot start any earlier than July 8.  One could either try to fix a specific time (to within an hour, say), to officially start the project, or one could open the thread in advance of the IMO organisers releasing the questions, and just let the first person to find the questions post them to the thread, and start the clock from there.  I assume one can rely on the honour code to refrain from privately trying to solve the question before any official starting time.
2. Location. In addition to this blog here, there is now also a dedicated polymath blog for these projects, which has some minor advantages over this one (e.g. numbered and threaded comments with wide margins).  It has fairly low levels of activity right now (though we are just starting to write up some modest progress from the ongoing Polymath4 “finding primes” project), but this may actually be a plus when running the project, to minimise cross-traffic.  Also, another benefit of the other blog is that the project can be co-administered by several people, and not just by myself.  This blog here admittedly has significantly higher traffic than the polymath blog at present, but I would certainly post a crosslink to the polymath blog if the project started.
3. Ground rules.  The rules for the first mini-polymath project can be found here.  Basically the spirit of the rules is that the objective is not to be the first to produce an individual solution, but instead to contribute to a collective solution by sharing one’s insights, even if they are small or end up being inconclusive.  (See also Tim Gowers’ original post regarding polymath projects.)   But perhaps some tweaking to the rules may be needed.  (For instance, we may want to have some semi-official role for moderators to organise the discussion.  Ideally I would prefer not to be the sole moderator, in part because I want to see the extent to which such projects can flourish independently of one key person.)
4. Set up.  It seems clear that we should have an official wiki page (probably a subpage from the polymath wiki) well in advance of the project actually starting (which could also be used to advertise the project beyond the usual readership of this blog).  Is there anything else which it might be useful to have in place before the project starts?
5. Contingency planning. It may happen that for one reason or another, 2010 IMO Q6 will not turn out to be that good of a polymath problem.  I suppose it may be sensible to reserve the right to switch to, say, 2010 IMO Q5, if need be.  This might be one place where I might exercise some unilateral judgement, as it may be difficult to quickly get consensus on these sorts of issues.   I don’t know if it’s worth discussing these sorts of possibilities in advance; it may simply be better to improvise when and if some course corrections need to be made.

Anyway, I hope that this project will be interesting, and am hoping to get some good suggestions as to how make it an instructive and enjoyable experience for all.

Some links

Michael Nielsen has posted a draft of his article “Introduction to the Polymath Project and “Density Hales-Jewett and Moser Numbers”” for comments, which will precede our own polymath article in the Szemerédi birthday conference proceedings.

As an unrelated link, Jordan Ellenberg has just written a piece for the Washington Post on statistical sampling and how it could make the US census more accurate.  (Whether this is politically viable is, of course, a different matter.)

DHJ Polymath paper accepted

Ordinarily, I only mention my research papers on this blog when they are first submitted, or if a major update is required.  With the paper arising from the DHJ Polymath “Low Dimensions” project, though, the situation is a little different as the collaboration to produce the paper took place on this blog.

Anyway, the good news is that the paper has been accepted for the Szemerédi birthday conference proceedings.  The referee was positive and recommended only some minor changes (I include the list of changes below the fold).  I have incorporated these changes, and the new version of the paper can be found here.  Within a few days I need to return the paper to the editor, so this is the last chance to propose any further corrections or changes (though at this stage any major changes are unlikely to be feasible).

The editor asked a good question: should we have a list of participants for this project somewhere?  If so, it seems to make more sense to have this list as a link on the wiki, rather than in the paper itself. But making a list opens the can of worms of deciding what level of participation should be the threshold for inclusion in the list – should someone who only contributed, say, one tangential comment to one of the blog posts be listed alongside a substantially more active participant?

One possibility is that of self-reporting; we could set up a page for participants on the wiki and let anyone who felt like they contributed add their name, and rely on the honour code to keep it accurate.    This might be feasible as long as the page is kept unofficial (so, in particular, it will not be used as the formal list of authors for the paper).

A related question is whether to add an explicit link to the timeline for progress on this project and on the sister “New proof” project.  If so, this should also be kept unofficial (there was no formal guidelines as to what was included in the timeline and what was not).

These decisions do not necessarily have to be taken quickly; one can simply point to the wiki in the paper (as is already done in the current version), and update the wiki later if we decide to add these sorts of acknowledgments on that site.

Incidentally, if we have another successful Polymath project to write up, I would now strongly recommend using version control software (such as Subversion or git) to organise the writing process, both at the informal notes stage and also at the drafting stage.  It is certainly far superior to our improvised solution of putting the raw TeX files on a wiki…

“Density Hales-Jewett and Moser numbers” – nearing the final draft

After a hiatus of several months, I’ve made an effort to advance the writing of the second Polymath1 paper, entitled “Density Hales-Jewett and Moser numbers“.  This is in part due to a request from the Szemeredi 60th 70th birthday conference proceedings (which solicited the paper) to move the submission date up from April to February.  (Also, the recent launch of Polymath5 on Tim Gowers blog reminds me that I should get this older project out of the way.)

The current draft of the paper is here, with source files here.  I have been trimming the paper, in particular replacing some of the auxiliary or incomplete material in the paper with references to pages on the polymath wiki instead.  Nevertheless this is still a large paper, at 51 pages.  It is now focused primarily on the computation of the Density Hales-Jewett numbers and the Moser numbers for all n up to 6, with the latter requiring a significant amount of computer assistance.

There are a number of minor issues remaining with the paper:

1. A picture of a Fujimura set for the introduction would be nice.
2. In the proof of Theorem 1.3 (asymptotic lower bound for DHJ numbers), it is asserted without proof that the circulant matrix with first row 1,2,…,k-1 is nonsingular.  One can prove this claim by computing the Fourier coefficients for all t, but is there a slicker way to see this (e.g. by citing a reference?).
3. Reference [15] (which is Komlos’s lower bound on the Moser numbers) is missing a volume number.  The reference is currently given as
   J. Komlos, solution to problem P.170 by Leo Moser, Canad. Math.. Bull. vol  ???  (1972), 312-313, 1970.

Finally, the text probably needs to be proofread one or two more times before it is ready to go, hopefully by early February.  There is still also one last opportunity to propose non-trivial restructuring of the paper (in particular, if there are other ways to trim the size of the paper, this may be worth looking into).

Applications-oriented periodic table

Here is a nice version of the periodic table (produced jointly by the Association for the British Pharmaceutical Industry, British Petroleum, the Chemical Industry Education Centre, and the Royal Society for Chemistry) that focuses on the applications of each of the elements, rather than their chemical properties.  A simple idea, but remarkably effective in bringing the table to life.

It might be amusing to attempt something similar for mathematics, for instance creating a poster that takes each of the top-level categories in the AMS 2010 Mathematics Subject Classification scheme (or perhaps the arXiv math subject classification), and listing four or five applications of each, one of which would be illustrated by some simple artwork.  (Except, of course, for those subfields that are “seldom found in nature”. :-) )

A project like this, which would need expertise both in mathematics and in graphic design, and which could be decomposed into several loosely interacting subprojects, seems amenable to a polymath-type approach; it seems to me that popularisation of mathematics is as valid an application of this paradigm as research mathematics.   (Admittedly, there is a danger of “design by committee“, but a polymath project is not quite the same thing as a committee, and it would be an interesting experiment to see the relative strengths and weaknesses of this design method.)   I’d be curious to see what readers would think of such an experiment.

[Update, Oct 25: A Math Overflow thread to collect applications of each of the major branches of mathematics has now been formed here, and is already rather active.  Please feel free to contribute!]

[Via this post from the Red Ferret, which was suggested to me automatically via Google Reader's recommendation algorithm.]

A new proof of the density Hales-Jewett theorem

The polymath1 project has just uploaded to the arXiv the paper “A new proof of the density Hales-Jewett theorem“, to be submitted shortly.  Special thanks here go to Ryan O’Donnell for performing the lion’s share of the writing up of the results, and to Tim Gowers for running a highly successful online mathematical experiment.

I’ll state the main result in the first non-trivial case for simplicity, though the methods extend surprisingly easily to higher (but with significantly worse bounds).  Let be the size of the largest subset of the cube that does not contain any combinatorial line.    The density Hales-Jewett theorem of Furstenberg and Katznelson shows that .  In the course of the Polymath1 project, the explicit values

were established, as well as the asymptotic lower bound

(actually we have a slightly more precise bound than this).  The main result of this paper is then

Theorem. ( version) .

Here is the inverse tower exponential function; it is the number of times one has to take (natural) logarithms until one drops below 1.  So it does go to infinity, but extremely slowly.  Nevertheless, this is the first explicitly quantitative version of the density Hales-Jewett theorem.

The argument is based on the density increment argument as pioneered by Roth, and also used in later papers of Ajtai-Szemerédi and Shkredov on the corners problem, which was also influential in our current work (though, perhaps paradoxically, the generality of our setting makes our argument simpler than the above arguments, in particular allowing one to avoid use of the Fourier transform, regularity lemma, or Szemerédi’s theorem).   I discuss the argument in the first part of this previous blog post.

I’ll end this post with an open problem.  In our paper, we cite the work of P. L. Varnavides, who was the first to observe the elementary averaging argument that showed that Roth’s theorem (which showed that dense sets of integers contained at least one progression of length three) could be amplified (to show that there was in some sense a “dense” set of arithmetic progressions of length three).  However, despite much effort, we were not able to expand “P.” into the first name.  As one final task of the Polymath1 project, perhaps some readers with skills in detective work could lend a hand in finding out what Varnavides’ first name was? Update, Oct 22: Mystery now solved; see comments.