A presentation of one possible near future polymath: the mathematics of the origin of life can be found on Gowers’s blog.
A presentation of one possible near future polymath: the mathematics of the origin of life can be found on Gowers’s blog.
The current goal is to find a deterministic way to locate a prime in an interval in time that breaks the “square root barrier” of (or more precisely, ). Currently, we have two ways to reach that barrier:
Currently we have one promising approach to break the square root barrier, based on the polynomial method, but while individual components of this approach fall underneath the square root barrier, we have not yet been able to get the whole thing below (or even matching) the square root. I will sketch the approach (as far as I understand it) below; right now we are needing some shortcuts (e.g. FFT, fast matrix multiplication, that sort of thing) that can cut the run time further.
This post will be somewhat abridged due to my traveling schedule.
Currently we are up against the “square root barrier”: the fastest time we know of to find a k-digit prime is about (up to factors), even in the presence of a factoring oracle (though, thanks to a method of Odlyzko, we no longer need the Riemann hypothesis). We also have a “generic prime” razor that has eliminated (or severely limited) a number of potential approaches.
One promising approach, though, proceeds by transforming the “finding primes” problem into a “counting primes” problem. If we can compute prime counting function in substantially less than time, then we have beaten the square root barrier.
Currently we have a way to compute the parity (least significant bit) of in time , and there is hope to improve this (especially given the progress on the toy problem of counting square-frees less than x). There are some variants that also look promising, for instance to work in polynomial extensions of finite fields (in the spirit of the AKS algorithm) and to look at residues of in other moduli, e.g. , though currently we can’t break the barrier for that particular problem.
This is a continuation of Research Thread II of the “Finding primes” polymath project, which is now full. It seems that we are facing particular difficulty breaching the square root barrier, in particular the following problems remain open:
We are still in the process of weighing several competing strategies to solve these and related problems. Some of these have been effectively eliminated, but we have a number of still viable strategies, which I will attempt to list below. (The list may be incomplete, and of course totally new strategies may emerge also. Please feel free to elaborate or extend the above list in the comments.)
Strategy A: Find a short interval [x,x+y] such that , where is the number of primes less than x, by using information about the zeroes of the Riemann zeta function.
Comment: it may help to assume a Siegel zero (or, at the other extreme, to assume RH).
Strategy B: Assume that an interval [n,n+a] consists entirely of u-smooth numbers (i.e. no prime factors greater than u) and somehow arrive at a contradiction. (To break the square root barrier, we need , and to stop the factoring oracle from being ridiculously overpowered, n should be subexponential size in u.)
Comment: in this scenario, we will have n/p close to an integer for many primes between and u, and n/p far from an integer for all primes larger than u.
Strategy C: Solve the following toy problem: given n and u, what is the distance to the closest integer to n which contains a factor comparable to u (e.g. in [u,2u])? [Ideally, we want a prime factor here, but even the problem of getting an integer factor is not fully understood yet.] Beating here is analogous to breaking the square root barrier in the primes problem.
Strategy D. Find special sequences of integers that are known to have special types of prime factors, or are known to have unusually high densities of primes.
Comment. There are only a handful of explicitly computable sparse sequences that are known unconditionally to capture infinitely many primes.
Strategy E. Find efficient deterministic algorithms for finding various types of “pseudoprimes” – numbers which obey some of the properties of being prime, e.g. . (For this discussion, we will consider primes as a special case of pseudoprimes.)
Comment. For the specific problem of solving there is an elementary observation that if n obeys this property, then does also, which solves this particular problem; but this does not indicate how to, for instance, have and obeyed simultaneously.
This thread marks the formal launch of “Finding primes” as the massively collaborative research project Polymath4, and now supersedes the proposal thread for this project as the official “research” thread for this project, which has now become rather lengthy. (Simultaneously with this research thread, we also have the discussion thread to oversee the research thread and to provide a forum for casual participants, and also the wiki page to store all the settled knowledge and accumulated insights gained from the project to date.) See also this list of general polymath rules.
The basic problem we are studying here can be stated in a number of equivalent forms:
Problem 1. (Finding primes) Find a deterministic algorithm which, when given an integer k, is guaranteed to locate a prime of at least k digits in length in as quick a time as possible (ideally, in time polynomial in k, i.e. after steps).
Problem 2. (Finding primes, alternate version) Find a deterministic algorithm which, after running for k steps, is guaranteed to locate as large a prime as possible (ideally, with a polynomial number of digits, i.e. at least digits for some .)
To make the problem easier, we will assume the existence of a primality oracle, which can test whether any given number is prime in O(1) time, as well as a factoring oracle, which will provide all the factors of a given number in O(1) time. (Note that the latter supersedes the former.) The primality oracle can be provided essentially for free, due to polynomial-time deterministic primality algorithms such as the AKS primality test; the factoring oracle is somewhat more expensive (there are deterministic factoring algorithms, such as the quadratic sieve, which are suspected to be subexponential in running time, but no polynomial-time algorithm is known), but seems to simplify the problem substantially.
The problem comes in at least three forms: a strong form, a weak form, and a very weak form.
The pr0blem in all of these forms remain open, even assuming a factoring oracle and strong number-theoretic hypotheses such as GRH. One of the main difficulties is that we are seeking a deterministic guarantee that the algorithm works in all cases, which is very different from a heuristic argument that the algorithm “should” work in “most” cases. (Note that there are already several efficient probabilistic or heuristic prime generation algorithms in the literature, e.g. this one, which already suffice for all practical purposes; the question here is purely theoretical.) In other words, rather than working in some sort of “average-case” environment where probabilistic heuristics are expected to be valid, one should instead imagine a “Murphy’s law” or “worst-case” scenario in which the primes are situated in a “maximally unfriendly” manner. The trick is to ensure that the algorithm remains efficient and successful even in the worst-case scenario.
Below the fold, we will give some partial results, and some promising avenues of attack to explore. Anyone is welcome to comment on these strategies, and to propose new ones. (If you want to participate in a more “casual” manner, you can ask questions on the discussion thread for this project.)
Also, if anything from the previous thread that you feel is relevant has been missed in the text below, please feel free to recall it in the comments to this thread.
There has been some discussion of the polymath enterprise on other blogs, so I thought it would be good to collect these links on the main polymath wiki page. If you find another link about polymath on the net, please feel free to add it to the wiki also (or at least to mention it in the comments here).
It should also be mentioned that besides the proposed polymath projects on this blog, Gil Kalai is in the process of setting up a polymath project on the polynomial Hirsch conjecture, tentatively scheduled to be launched later this month. See the following preparatory posts:
An extremely rudimentary wiki page for the proposed project has now been created.
New: Tim Gowers devotes a post to several proposals for a polymath project in November.
The proposal “deterministic way to find primes” is not officially a polymath yet, but is beginning to acquire the features of one, as we have already had quite a bit of interesting ideas. So perhaps it is time to open up the discussion thread a little earlier than anticipated. There are a number of purposes to such a discussion thread, including but not restricted to:
To start the ball rolling, let me collect some of the observations accumulated as of July 28:
See also the wiki page for this project.
In a few months (the tentative target date is October), we plan to launch another polymath project (though there may also be additional projects before this date); however, at this stage, we have not yet settled on what that project would be, or even how exactly we are to select it. The purpose of this post, then, is to begin a sort of pre-pre-selection process, in which we discuss how to organise the search for a new project, what criteria we would use to identify particularly promising projects, and how to run the ensuing discussion or voting to decide exactly which project to begin. (We think it best to only launch one project at a time, for reasons to be discussed below.)
There are already a small number of polymath projects being proposed, and I expect this number to grow in the near future. Anyone with a problem which is potentially receptive to the polymath approach, and who is willing to invest significant amounts of time and effort to administrate and advance the effort, is welcome to make their own proposal, either in their own forum, or by contacting one of us. (If you do make a proposal on your own wordpress blog, put it in the category “polymath proposals” so that it will be picked up by the above link.) There is already some preliminary debate and discussion at the pages of each of these proposals, though one should avoid any major sustained efforts at solving the problem yet, until the participants for the project are fully assembled and prepared, and the formal polymath threads are ready to launch.
[One lesson we got from the minipolymath feedback was that one would like a long period of lead time before a polymath project is formally launched, to get people prepared by reading up and allocating time in advance. So it makes sense to have the outlines of a project revealed well in advance, though perhaps the precise details of the project (e.g. a compilation of the proposer’s own thoughts on the problem) can wait until the launch date.]
On the other hand, we do not want to launch multiple projects at once. So far, the response to each new launched project has been overwhelming, but this may not always be the case in the future, and in particular simultaneous projects may have to compete with each other for attention, and perhaps most crucially, for the time and efforts of the core participants of the project. Such a conflict would be particularly acute for projects that are in the same field, or in related fields. (In particular, we would like to diversify the polymath enterprise beyond combinatorics, which is where most of the existing projects lie.)
So we need some way to identify the most promising projects to work on. What criteria would we look for in a polymath project that would indicate a high likelihood of full or partial success, or at least a valuable learning experience to aid the organisation of future projects of this type? Some key factors come to mind:
Over to the other readers of this blog: what else should we be looking for in a polymath project? How quickly should we proceed with the selection process? Should we decide by popular vote, or by some fixed criteria?
Another proposal for a polymath project is the following question of Michael Boshneritzan:
Question. Let be a (simple) path in a lattice which has bounded step sizes, i.e. for some C and all i. Is it necessarily the case that this path contains arbitrarily long arithmetic progressions, i.e. for each k there exists with r non-zero such that .
The d=1 case follows from Szemerédi’s theorem, as the path has positive density. Even for d=2 and k=3 the problem is open. The question looks intriguingly like the multidimensional Szemerédi theorem, but it is not obvious how to deduce it from that theorem. It is also tempting to try to invoke the Furstenberg correspondence principle to create an ergodic theory counterpart to this question, but to my knowledge this has not been done. There are also some faint resemblances to the angel problem that has recently been solved.
In honour of mini-polymath1, one could phrase this problem as a grasshopper trying to jump forever (with bounded jumps) in a square lattice without creating an arithmetic progression (of length three, say).
It is also worth trying to find a counterexample if C, d, k are large enough. Note that the continuous analogue of the problem is false: a convex curve in the plane, such as the parabola , contains no arithmetic progressions, but is rectifiable. However it is not obvious how to discretise this example.
In short, there seem to be a variety of tempting avenues to try to attack this problem; it may well be that many of them fail, but the reason for that failure should be instructive.
Andrew Mullhaupt informs me that this question would have applications to short pulse rejected Boolean delay equations.