3 ms·
Old proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do this by noting that v_n + 1 has at lea
by Chinjut 11y ago
Old proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do this by noting that v_n + 1 has at least one prime factor but no prime factors in common with v_n, and thus taking v_{n + 1} to be v_n * (some prime factor of (v_n + 1)).
"New" proof: Let's produce a series of values v_1, v_2, ..., such that v_n has at least n distinct prime factors. We can do this by noting that v_n + 1 has at least one prime factor but no prime factors in common with v_n, and thus taking v_{n + 1} to be v_n * (v_n + 1).
Doesn't seem terribly different or more constructive or any such thing to me. I'd say both of these have the same fundamental content, just framed slightly differently.
[Just to head off what might superficially seem to be a significant distinction: Note that, in both proofs, we use the (constructive) fact that every integer > 1 has a prime factor, and even in the "new" proof, in order to actually extract an infinite stream of primes, one must actually carry out this process of finding prime factors for integers > 1 on demand.]
- mgalka 11y agoSurprised this got published. This theorem is literally day-1 number theory. And unless I'm missing something, this paper is just rephrasing it in a slightly different way. http://wstein.org/ent/ent.pdf http://wstein.org/ent/ent.pdf Also seems like a pretty baseless claim to say that this proof has never been done before.
- phasmantistes 11y agoThat's not really an accurate representation of the old proof. You've turned it around to make it look like the new one, but that's not how it is originally laid out at all. The fundamental problem (for constructivists) with Euclid's proof is that it assumes the existence of a set of all primes, and then proves that that set is incorrect (either contains a composite, or doesn't contain at least one specific prime). Saidak's proof, on the other hand, only assumes the existence of a single integer, and then constructs infinitely many primes from that integer. Your restatement of Euclid's proof is basically "look, Euclid and Saidak proved the same thing", not "look, Euclid's proof is constructive too".
- obastani 11y agoI think the point is you can easily remove the "deficiencies" of Euclid's proof. Basically, say: let p_1, ..., p_n be the first n primes. We can construct a new prime by examining p_1...p_n + 1. This process can be continued indefinitely. In fact, I think the statement "this process can be continued indefinitely" is quite misleading -- to formalize this, I think you need proof by contradiction. So, the difference is the syntax used, not the actual semantics of the proof.
- IngoBlechschmid 11y agoThere a ways to formulate "the infinity of the prime numbers" without any recourse to a previously-constructed set of all prime numbers (or even all natural numbers). Two such ways are: 1. "For any natural number n, there is a prime number greater than n." 2. "For any natural number m, and for any list of m prime numbers p_1, ..., p_m, there exists a prime number not on that list." Both statements have a perfectly fine constructive proof. The second statement is more or less precisely what Euclid proved. The first statement follows from the second one with a bit more work.
- Chinjut 11y agoTwo points: A) Euclid never assumes the existence of a finite set of all primes (doing so at the outset is a framing adopted only by later mathematicians); people just frequently erroneously think Euclid's proof did this, never having actually read it. Rather, Euclid constructively frames things, directly arguing that, for any finite set of primes, there is furthermore some prime outside that set. See http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.html http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.ht.... B) Regardless, I don't particularly care how Euclid phrased his proof; I never mentioned Euclid. Certainly, mathematicians have been aware that Euclid's insight could be framed in the way I called an "old proof" for a long, long time. The distinctions between the various framings here are trivial.