tag:blogger.com,1999:blog-3722233.post4511892902627593093..comments2018-12-10T20:52:53.733-05:00Comments on Computational Complexity: Van der Waerden's theorem implies the infinitude of the primesLance Fortnowhttps://plus.google.com/101693130490639305932noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-4315682900618952182017-12-07T09:22:31.908-05:002017-12-07T09:22:31.908-05: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-04T22:56:44.607-05:002017-12-04T22:56:44.607-05: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-04T17:35:23.252-05:002017-12-04T17:35:23.252-05: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-29T04:49:09.995-05:002017-11-29T04:49:09.995-05: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-28T15:09:52.035-05:002017-11-28T15:09:52.035-05: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-28T15:02:04.926-05:002017-11-28T15:02:04.926-05: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