tag:blogger.com,1999:blog-3722233.post747317852549327178..comments2024-11-14T17:42:16.782-06:00Comments on Computational Complexity: There are an infinite number of proofs that there are an infinite number of primesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-53264719652872368472023-05-04T06:52:06.717-05:002023-05-04T06:52:06.717-05:00Quanta Magazine is funded by the Simons Foundation...Quanta Magazine is funded by the Simons Foundation and has no paywall.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76225627928128624392023-05-03T16:36:07.591-05:002023-05-03T16:36:07.591-05:00When I was an undergrad, I misremembered Euclid...When I was an undergrad, I misremembered Euclid's proof as "Let N be the product of all primes p_i. Then for all i, N is congruent to 1 (mod p_i). So N is prime." (Which is wrong; N is only guaranteed to have a new prime factor.)<br /><br />I then thought, huh, for all i, N is congruent to -1 (mod p_i), and so it sort of seemed like N and N-2 must be twin primes.<br /><br />I asked a TA about this, who reminded me of the actual Euclid proof. D'oh!<br />Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30373810199995634332023-05-03T11:09:05.772-05:002023-05-03T11:09:05.772-05:00Proofs are only a path between the axioms and the ...Proofs are only a path between the axioms and the theorem to be proved on a "proof system digraph"; as in real life it is not surprising that there are arbitrarily long paths to get to the goal :-))Marzio De Biasihttps://www.nearly42.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67594080305671604822023-05-02T19:14:20.040-05:002023-05-02T19:14:20.040-05:00Re: "ANY integral domain with Unique Factoriz...Re: "ANY integral domain with Unique Factorization has an infinite number of primes." An integral domain is either a field, in which case the zero ideal is the only prime ideal, or it has infinitely many prime ideals. <br />I wonder if unique factorization can be relaxed in that proof since in general rings of integers, we don't have unique factorization, only unique factorization of ideals into prime ideals.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76858197140755843092023-05-02T12:59:48.240-05:002023-05-02T12:59:48.240-05:00There are many proofs, but how many of them are th...There are many proofs, but how many of them are the same or based on the same idea? For example, Keith Conrad argued in his write-up that Furstenberg's proof is based on the same idea as Euclid's proof: https://kconrad.math.uconn.edu/blurbs/ugradnumthy/primestopology.pdfZGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3082665558412708882023-05-01T23:43:39.194-05:002023-05-01T23:43:39.194-05:00https://mathoverflow.net/questions/319686/reverse-...https://mathoverflow.net/questions/319686/reverse-mathematics-of-euclids-theoremAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41019914253084670252023-05-01T14:51:33.306-05:002023-05-01T14:51:33.306-05:00My favorite proof uses Kolmogorov complexity.My <a href="https://blog.computationalcomplexity.org/2017/11/kolmogorov-complexity-and-primes.html" rel="nofollow">favorite proof</a> uses Kolmogorov complexity. Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59408692751200705222023-05-01T14:36:40.057-05:002023-05-01T14:36:40.057-05:00I am not sure what this comment means. I think you...I am not sure what this comment means. I think you are saying that my goal with L is in the realm of Reverse Mathematics. The classes RCA_0 etc defined in Reverse Mathematics are WAY ABOVE the level I am talking about. I've asked people in Rev. Math. and they tell me that any system strong enough to prove the implication is likely strong enough to prove Primes Infinite outright. I've also thought about complexity versions like a proof that there are \ge n primes requires say 2^n steps where the relevant implication takes poly(n) steps. I suspect that that is also not doable. ANYWAY, please clarify your comment. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87009523474668630982023-05-01T10:26:34.233-05:002023-05-01T10:26:34.233-05:00reverse mathematics and complexity theory version ...reverse mathematics and complexity theory version of it.Anonymousnoreply@blogger.com