The “Hot spots conjecture” proposal has taken off, with 42 comments as of this time of writing. As such, it is time to take the proposal to the next level, by starting a discussion thread (this one) to hold all the meta-mathematical discussion about the proposal (e.g. organisational issues, feedback, etc.), and also starting a wiki page to hold the various facts, strategies, and bibliography around the polymath project (which now is “officially” the Polymath7 project).
I’ve seeded the wiki with the links and references culled from the original discussion, but it was a bit of a rush job and any editing would be greatly appreciated. From past polymath experience, these projects can get difficult to follow from the research threads alone once the discussion takes off, so the wiki becomes a crucial component of the project as it can be used to collate all the progress made so far and make it easier for people to catch up. (If the wiki page gets more complicated, we can start shunting off some stuff into sub-pages, but I think it is at a reasonable size for now.)
One thing I see is that not everybody who has participated knows how to make latex formatting such as appear in their comments. The instructions for that (as well as a “sandbox” to try out the code) are at this link.
Once the research thread gets long enough, we usually start off a new thread (with some summaries of the preceding discussion) to make it easier to keep the discussion at a manageable level of complexity; traditionally we do this at about the 100-comment mark, but of course we can alter this depending on how people are able to keep up with the thread.
In October 2010 there was a discussion about polymath projects at an event organized by the I.A.S in NYC. Tim Gowers described the endeavor and some prospects, and hopes, and Peter Sarnak responded with some concerns. An interesting discussion followed. Some of the discussion is described in the IAS Institute Letter for fall 2010 .
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 summarise the progress made so far, in a manner accessible to “casual” participants of the project.
- To have “meta-discussions” about the direction of the project, and what can be done to make it run more smoothly. (Thus one can view this thread as a sort of “oversight panel” for the research thread.)
- To ask questions about the tools and ideas used in the project (e.g. to clarify some point in analytic number theory or computational complexity of relevance to the project). Don’t be shy; “dumb” questions can in fact be very valuable in regaining some perspective.
- (Given that this is still a proposal) To evaluate the suitability of this proposal for an actual polymath, and decide what preparations might be useful before actually launching it.
To start the ball rolling, let me collect some of the observations accumulated as of July 28:
- A number of potentially relevant conjectures in complexity theory and number theory have been identified: P=NP, P=BPP, P=promise-BPP, existence of PRG, existence of one-way functions, whether DTIME(2^n) has subexponential circuits, GRH, the Hardy-Littlewood prime tuples conjecture, the ABC conjecture, Cramer’s conjecture, discrete log in P, factoring in P.
- The problem is solved if one has P=NP, existence of PRG, or Cramer’s conjecture, so we may assume that these statements all fail. The problem is probably also solved on P=promise-BPP, which is a bit stronger than P=BPP, but weaker than existence of PRG; we currently do not have a solution just assuming P=BPP, due to a difficulty getting enough of a gap in the success probabilities.
- Existence of PRG is assured if DTIME(2^n) does not have subexponential circuits (Impagliazzo-Wigderson), or if one has one-way functions (is there a precise statement to this effect?)
- Discrete log being in hard (or easy) may end up being a useless hypothesis, since one needs to find large primes before discrete logarithms even make sense.
- If the problem is false, it implies (roughly speaking) that all large constructible numbers are composite. Assuming factoring is in P, it implies the stronger fact that all large constructible numbers are smooth. This seems unlikely (especially if one assumes ABC).
- Besides adding various conjectures in complexity theory or number theory, we have found some other ways to make the problem easier:
- The trivial deterministic algorithm for finding k-bit primes takes exponentially long in k in the worst case. Our goal is polynomial in k. What about a partial result, such as exp(o(k))?
- An essentially equivalent variant: in time polynomial in k, we can find a prime with at least log k digits. Our goal is k. Can we find a prime with slightly more than log k digits?
- The trivial probabilistic algorithm takes O(k^2) random bits; looks like we can cut this down to O(k). Our goal is O(log k) (as one can iterate through these bits in polynomial time). Can we do o(k)?
- Rather than find primes, what about finding almost primes? Note that if factoring is in P, the two problems are basically equivalent. There may also be other number theoretically interesting sets of numbers one could try here instead of primes.
- At the scale log n, primes are assumed to resemble a Poisson process of intensity 1/log n (this can be formalised using a suitably uniform version of the prime tuples conjecture). Cramer’s conjecture can be viewed as one extreme case of this principle. Is there some way to use this conjectured Poisson structure in a way without requiring the full strength of Cramer’s conjecture? (I believe there is also some work of Granville and Soundarajan tweaking Cramer’s prediction slightly, though only by a multiplicative constant if I recall correctly.)
See also the wiki page for this project.
This is a mockup of what a discussion thread for a polymath project would look like; it would run alongside the research thread, but is focused on strategy, exposition, and discussion by casual participants, as opposed to the more cutting edge research conducted by more active participants in the research thread.
Please feel free to make suggestions in this thread as to how the format and organisation of these projects (or this blog) could be improved.