An update on the status of the Polymath4 paper on finding primes. I’ve received a referee report from Mathematics of Computation on the submission, which can be found here. The referee liked the result but wanted a fair number of expository changes before he or she was willing to recommend acceptance, so the editor has asked for a revision. I will be happy to make the relevant changes, but if there are any other changes that other participants would like to make, now would be a good time to suggest them. (The most recent version of the paper can be found at the Subversion repository or at this link; see also the arXiv version.)
One change requested is to add a list of participants to the project. In analogy with what we did for Polymath1, I therefore started a “signup sheet” on the wiki at
http://michaelnielsen.org/polymath1/index.php?title=Polymath4_grant_acknowledgments
for people to self-report their participation, contact information, and grant information for the project. There is the usual problem of trying to decide who is a “main participant” of the project, and who is a “contributor” (though I think I can safely add Ernie, Harald, and myself as participants); as with Polymath1, I will leave it to each of you to self-report what level of participation you feel is appropriate.
The polymath blog 
[…] There is a referee report for polymath4 from mathematics of computation. It is here. Also see this post. […]
Pingback by Polymath4 « Euclidean Ramsey Theory — February 14, 2011 @ 7:21 pm |
When I go to the subversion site I can’t view the pdf of the paper. I get the error message “1: File is too big or a binary file”. I think a pdf is a binary file.
Comment by kristalcantwell — February 14, 2011 @ 7:27 pm |
Hmm, I didn’t realise that the Subversion repository does not directly allow for downloading or viewing the files. With your subversion account you should be able to “check out” the whole repository onto a local folder, but in the short term the quickest fix is to look at the arXiv version at http://arxiv.org/abs/1009.3956
Comment by Terence Tao — February 15, 2011 @ 11:16 am |
It might be that someone typing
svn propset svn:mime-type "application/pdf" fast_strassen.pdf
(and similarly for other PDFs) will fix this problem. I’m not sure about this particular web interface, but for some I’ve used this is the required trick.
Comment by Scott Morrison — February 15, 2011 @ 12:15 pm |
Ah, thanks! I updated the PDF type, but actually I realise the main problem was that I linked to the wrong web page (that showed diffs and revision history rather than the files themselves). I now have a better link
https://svnbackup.xp-dev.com/svn/Finding_primes/
and specifically
Click to access polymath.pdf
for the most recent version. (I also placed it on my blog at
Click to access polymath.pdf
in case the other link does not work well.) I’ve now implemented all the referee changes; I’ll wait for a few days to see if the other contributors have something to say and then will send back the revision.
Comment by Terence Tao — February 15, 2011 @ 12:33 pm |
My current NSF grant is DMS-1001111, and while working on the project I was supported by NSA grant.
Comment by Ernie Croot — February 16, 2011 @ 5:56 pm |
I was supported by grant EPSRC EP-054919/1 at the time. That grant is actually somewhat specific to another project, but it would be better to mention it even if I was not using it for this purpose. (“While working on the project, H. A. Helfgott was staying at his parents'”, while truthful, would be non-standard.)
Comment by Harald Helfgott — February 20, 2011 @ 2:45 pm |
Regarding the paragraph: “Given that there is a probabilistic algorithm to locate primes in time polynomial in the digits, it may seem that the conjecture P = BPP would be able to quickly imply a
fast algorithm to locate primes. Unfortunately, to use the P = BPP conjecture, one
would presumably need to obtain a bounded-error probabilistic polynomial (BPP) time
algorithm for solving the above decision problem (or some closely related problem), and
it is not clear how to achieve this.”
Maybe we should mention in one sentence that the required result will follow from “Full derandomization” http://blog.computationalcomplexity.org/2006/07/full-derandomization.html which itself follows from some very harsh hardness result. Then there was a comment (but I forgot where) by Avi Wigderson that full derandomization is much more than needed because of some unary nature of the problem which implies that less harsh hardness result (for turing machines rather than circuits) would suffice.
Comment by Gil Kalai — February 20, 2011 @ 6:46 pm |
[…] week started off with good news for Polymath4, the referee report is out and looks good. Monday could not get enough of Valentine’s Day mathematics and M@atematicamente had a sweet […]
Pingback by Weekly picks « Mathblogging.org developer.blog — February 21, 2011 @ 7:43 pm |
The paper has now been accepted, and the published version has been placed on the arXiv.
Gil: I am not so familiar with this aspect of complexity theory, so did not figure out how to write a proper remark about the implications of full derandomisation. I’ll put the remark on the wiki instead (which we already link to regarding the oracle counterexample showing that P=BPP is not sufficient).
Comment by Terence Tao — February 25, 2011 @ 2:15 am |
I just returned the proofs to Mathematics of Computation; there were no changes except for the author names (unfortunately, they would not accept a pseudonym authorship, as it disrupted their bibliographic system). Instead, Ernie, Harald, and myself will now be primary authors.
Comment by Terence Tao — June 1, 2011 @ 5:49 pm |
[…] The proofs for the article “Deterministic methods to find primes” will appear in Mathematics of Computation but not with a pseudonym. Apparently Mathematics of Computation had a problem with that. The authors will be Ernie Croot, Harald Helfgott and Terence Tao. See this post. […]
Pingback by Polymath4 « Euclidean Ramsey Theory — June 1, 2011 @ 8:22 pm |
a little hard for me,but a very good work!
Comment by muondo — June 13, 2011 @ 4:23 pm |
It is probably not likely to be viewed. But I thought that finding a way to rule out that a certain number is a prime efficiently could be a good challenge as well.
Comment by Eyal — April 26, 2018 @ 11:50 pm |