tag:blogger.com,1999:blog-3722233.post4511892902627593093..comments2024-05-20T10:34:03.365-05:00Comments on Computational Complexity: Van der Waerden's theorem implies the infinitude of the primesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-4315682900618952182017-12-07T08:22:31.908-06:002017-12-07T08:22:31.908-06:00I think one might also reduce the number of cases ...I think one might also reduce the number of cases by unifying Case 1 and Case 2 in the following way:<br /><br />If a' > d', consider two values of v_p(a+id) as follows:<br /><br />- always take i=0 to get the value of a'.<br />- if a' and d' have different parities, <br /> take i=1 to get the value of d'.<br />- if a' and d' have the same parity, then a'>d'+1,<br /> so take i=p to get the value of d'+1.<br /><br />We still need to choose i up to p_max^2 in the remaining case a'=d', but not here.<br />Anatoly Vorobeyhttps://www.blogger.com/profile/15075147858952180578noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42520624441004949902017-12-04T21:56:44.607-06:002017-12-04T21:56:44.607-06:00Fixed.
Thanks.
Thanks more than usual- I'm tea...Fixed.<br />Thanks.<br />Thanks more than usual- I'm teaching a course on<br />Ramsey theory and its ``applications'' and will be handing<br />out the writeup for one of the ``applications''GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70959008009067186592017-12-04T16:35:23.252-06:002017-12-04T16:35:23.252-06:00In the proof there's a typo in Case 4: it says...In the proof there's a typo in Case 4: it says "For all p ∈ P a' ≤ d' + 1", but it should be d'-1.<br />Anatoly Vorobeyhttps://www.blogger.com/profile/15075147858952180578noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91514087926689149902017-11-29T03:49:09.995-06:002017-11-29T03:49:09.995-06:00If the system is powerful enough to prove Bertrand...If the system is powerful enough to prove Bertrand's postulate (for every n > 1 there is always at least one prime p s.t. n < p < 2n) then #3 should be O(1).Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16371374193646884812017-11-28T14:09:52.035-06:002017-11-28T14:09:52.035-06:00Fixed- thanks.
Hope its right now.Fixed- thanks.<br />Hope its right now.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72509440478944715762017-11-28T14:02:04.926-06:002017-11-28T14:02:04.926-06:00Open Problem 3 has a sign problem. As stated, it...Open Problem 3 has a sign problem. As stated, it can easily be refuted for all n>= 2 since 2 which has 2 digits in binary is trivially prime.Anonymousnoreply@blogger.com