6 ms·

A new proof of Euclid's Theorem (2006)

56 points by bezierc 11y ago

wodenokoto 11y ago
Off-topic, but, what's the deal with all those dashes in the document?
- Rainymood 11y ago
 Getting them too, using Firefox 43.0.4 on OS X Yosemite 10.10.3
- tzs 11y ago
 The markup is really weird on that page. There are empty spans in the middle of words. For example, here is how the word "positive" is represented: positive
rrauenza 11y ago
Note: this paper is from 2006.
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 ago
  Surprised 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 ago
  That'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 ago
    I 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 ago
      There 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.
jaybosamiya 11y ago
The idea of using `consecutive numbers are coprime` as the sole property for this concise proof is quite remarkable. I would definitely be interested to know if there are any other such simple proofs exist for other theorems. (i.e. ones where a new proof simplifies it massively by using a simpler property).
- Chinjut 11y ago
  What property does the classic proof use that the "new" proof does not?
  - deleted 11y ago
    [deleted]
  - shasta 11y ago
    From the article: The proof just given is conceptually even simpler than the original proof due to Euclid, since it does not use Eudoxus’s method of“reductio ad absurdum,” proof by contradiction. And unlike most other proofs of the theorem, it does not require Proposition 30 of Elements (sometimes called “Euclid’s Lemma”) that states: if p is a prime and p|ab, then either p|a or p|b. Moreover, our proof is constructive, and it gives integers with an arbitrary number of prime factors. Edit: Actually, even though the article seems to imply that the classic proof ("most proofs") uses prop 30, it doesn't really seem to.
    - Chinjut 11y ago
      The article makes suggestions here about the classic proof which aren't true. Euclid's proof of the infinitude of the primes was not phrased in terms of an overarching reductio ad absurdum (and even had it counterfactually been, mathematicians would've long ago been able to trivially rephrase it so as not to be, showing "For any finite set of primes, there is some further prime" directly). And the classic proof of the infinitude of the primes does not anywhere use Proposition 30 of the Elements (see for yourself at http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.html http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.ht... ; Proposition 31 (that every composite has some prime factor) is used, but this in turn is argued for without any invocation of Proposition 30). Where in the classic proof would you imagine "if p is a prime and p | ab, then p | a or p | b" would come up?
deleted 11y ago
[deleted]
- obastani 11y ago
  The proof isn't referring to n, n+1, and n+2 -- it refers to n, n+1, and n(n+1) + 1. In your example, this would be 2, 3, and 2*3 + 1 = 7, which in fact include 3 prime factors.
- Chinjut 11y ago
  You've misread the proof. They do not argue that n, n + 1, and n + 2 are co-prime; they only note that n, (n + 1), and n * (n + 1) + 1 are co-prime [and more generally they continue in the same fashion, using the basic fact that n and n + 1 are co-prime for any n]. The proof is sound. However, it is also not particularly different in essence from the classic proof; considering it so is misguided (see https://news.ycombinator.com/item?id=10889290 https://news.ycombinator.com/item?id=10889290).
  - btilly 11y ago
    You're right.
CurtMonash 11y ago
This discussion illustrates an interesting point -- it can be a little tricky to judge whether two proofs are actually "different" or not. When I was a grad student I interrupted a study session to raise the simple question -- can a theorem really have two different proofs? We all thought the answer was yes, but the discussion went on for several minutes until I settled it by contriving a stupidly simple and synthetic set of axioms to construct a example. Basically, the axioms were: "All As are also Bs" "All As are also Cs" "All Bs are also Ds" "All Cs are also Ds" and the theorem was "All As are also Ds"
- danharaj 11y ago
  Sure. Theorem: There exists an even natural number. Proof 1: 2. ∎ Proof 2: 4. ∎
- Chinjut 11y ago
  Yes; putting essentially the same example another way, we might feel intuitively that there are two separate proofs of the propositional theorem that "B AND C" implies "B OR C". Edit: Or, following up on danharaj's framing, we might feel intuitively that there are two separate proofs of "The set {B, C} is inhabited".
- zingermc 11y ago
  A / \ v v B C \ / v D That was making my eyes cross, so I drew it out. In short, there are two distinct paths that you can apply a transitive rule over to get A -> D. Very cool example!
  - danharaj 11y ago
    It can get more complicated. When your logic can talk about equivalence of equivalences of proofs, then you can have two proofs that are equivalent in two ways that are not equivalent. Or, you could have two proofs that are equivalent in two ways whose equivalence can be proved, but maybe also in more than one way. You can iterate equivalences of equivalences in such a logic and equality becomes a significantly richer concept. The study of such mathematical structures is the study of what is called an (infinity,1)-topos.
IngoBlechschmid 11y ago
I'd like to draw attention to a fact already pointed out by Chinjut in this thread: The original formulation of Euclid's proof is in fact entirely constructive, contrary to what the article claims. Michael Hardy and Catherine Woodgold have written a very nice and readable account on the misconceptions about Euclid's proof (published in 2009). I'm sorry that I can only give a paywalled link; at least the first two pages are available. http://link.springer.com/article/10.1007%2Fs00283-009-9064-8 http://link.springer.com/article/10.1007%2Fs00283-009-9064-8 Incidentally, with the specific situation at hand, the question "constructive vs. nonconstructive" is slightly moot. This is because there is a certain metatheorem in mathematical logic which states: If there is a nonconstructive proof of a statement, then there is also a constructive proof. Of course this metatheorem doesn't apply to arbitrary statements, only to statements of a specific logical form (so called "geometric sequents"). But the statement "there are infinitely many prime numbers" can be put into such a form. Also, in case you are wondering, this metatheorem admits itself a constructive proof. Summarizing, there is a mechanical way to turn any nonconstructive proof of the infinitude of the primes into a constructive one. The key words to look up here are "double-negation translation" and "Friedman's trick". Fantastically, the double-negation translation turns out to be "the same as" the continuation-passing style transformation, if viewed from the right angle. Some pointers are in this slide deck: http://rawgit.com/iblech/talk-constructive-mathematics/master/negneg-translation.pdf http://rawgit.com/iblech/talk-constructive-mathematics/maste...
rnhmjoj 11y ago
I wonder, do proofs of this kind, where some process is repeated forever to prove the thesis, have an infinite length? Could this be made into a finite number of steps in some formal system? Using a rule of induction maybe?

56 points by bezierc 11y ago

wodenokoto 11y ago

Off-topic, but, what's the deal with all those dashes in the document?

Rainymood 11y ago
Getting them too, using Firefox 43.0.4 on OS X Yosemite 10.10.3
tzs 11y ago
The markup is really weird on that page. There are empty spans in the middle of words. For example, here is how the word "positive" is represented: positive

rrauenza 11y ago

Note: this paper is from 2006.

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 ago
Surprised 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 ago
That'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 ago
  I 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 ago
    There 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.

jaybosamiya 11y ago

The idea of using `consecutive numbers are coprime` as the sole property for this concise proof is quite remarkable. I would definitely be interested to know if there are any other such simple proofs exist for other theorems. (i.e. ones where a new proof simplifies it massively by using a simpler property).

Chinjut 11y ago
What property does the classic proof use that the "new" proof does not?
- deleted 11y ago
  [deleted]
- shasta 11y ago
  From the article: The proof just given is conceptually even simpler than the original proof due to Euclid, since it does not use Eudoxus’s method of“reductio ad absurdum,” proof by contradiction. And unlike most other proofs of the theorem, it does not require Proposition 30 of Elements (sometimes called “Euclid’s Lemma”) that states: if p is a prime and p|ab, then either p|a or p|b. Moreover, our proof is constructive, and it gives integers with an arbitrary number of prime factors. Edit: Actually, even though the article seems to imply that the classic proof ("most proofs") uses prop 30, it doesn't really seem to.
  - Chinjut 11y ago
    The article makes suggestions here about the classic proof which aren't true. Euclid's proof of the infinitude of the primes was not phrased in terms of an overarching reductio ad absurdum (and even had it counterfactually been, mathematicians would've long ago been able to trivially rephrase it so as not to be, showing "For any finite set of primes, there is some further prime" directly). And the classic proof of the infinitude of the primes does not anywhere use Proposition 30 of the Elements (see for yourself at http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.html http://aleph0.clarku.edu/~djoyce/elements/bookIX/propIX20.ht... ; Proposition 31 (that every composite has some prime factor) is used, but this in turn is argued for without any invocation of Proposition 30). Where in the classic proof would you imagine "if p is a prime and p | ab, then p | a or p | b" would come up?

deleted 11y ago

[deleted]

obastani 11y ago
The proof isn't referring to n, n+1, and n+2 -- it refers to n, n+1, and n(n+1) + 1. In your example, this would be 2, 3, and 2*3 + 1 = 7, which in fact include 3 prime factors.
Chinjut 11y ago
You've misread the proof. They do not argue that n, n + 1, and n + 2 are co-prime; they only note that n, (n + 1), and n * (n + 1) + 1 are co-prime [and more generally they continue in the same fashion, using the basic fact that n and n + 1 are co-prime for any n]. The proof is sound. However, it is also not particularly different in essence from the classic proof; considering it so is misguided (see https://news.ycombinator.com/item?id=10889290 https://news.ycombinator.com/item?id=10889290).
- btilly 11y ago
  You're right.

CurtMonash 11y ago

This discussion illustrates an interesting point -- it can be a little tricky to judge whether two proofs are actually "different" or not. When I was a grad student I interrupted a study session to raise the simple question -- can a theorem really have two different proofs? We all thought the answer was yes, but the discussion went on for several minutes until I settled it by contriving a stupidly simple and synthetic set of axioms to construct a example. Basically, the axioms were: "All As are also Bs" "All As are also Cs" "All Bs are also Ds" "All Cs are also Ds" and the theorem was "All As are also Ds"

danharaj 11y ago
Sure. Theorem: There exists an even natural number. Proof 1: 2. ∎ Proof 2: 4. ∎
Chinjut 11y ago
Yes; putting essentially the same example another way, we might feel intuitively that there are two separate proofs of the propositional theorem that "B AND C" implies "B OR C". Edit: Or, following up on danharaj's framing, we might feel intuitively that there are two separate proofs of "The set {B, C} is inhabited".
zingermc 11y ago
A / \ v v B C \ / v D That was making my eyes cross, so I drew it out. In short, there are two distinct paths that you can apply a transitive rule over to get A -> D. Very cool example!
- danharaj 11y ago
  It can get more complicated. When your logic can talk about equivalence of equivalences of proofs, then you can have two proofs that are equivalent in two ways that are not equivalent. Or, you could have two proofs that are equivalent in two ways whose equivalence can be proved, but maybe also in more than one way. You can iterate equivalences of equivalences in such a logic and equality becomes a significantly richer concept. The study of such mathematical structures is the study of what is called an (infinity,1)-topos.

IngoBlechschmid 11y ago

I'd like to draw attention to a fact already pointed out by Chinjut in this thread: The original formulation of Euclid's proof is in fact entirely constructive, contrary to what the article claims. Michael Hardy and Catherine Woodgold have written a very nice and readable account on the misconceptions about Euclid's proof (published in 2009). I'm sorry that I can only give a paywalled link; at least the first two pages are available. http://link.springer.com/article/10.1007%2Fs00283-009-9064-8 http://link.springer.com/article/10.1007%2Fs00283-009-9064-8 Incidentally, with the specific situation at hand, the question "constructive vs. nonconstructive" is slightly moot. This is because there is a certain metatheorem in mathematical logic which states: If there is a nonconstructive proof of a statement, then there is also a constructive proof. Of course this metatheorem doesn't apply to arbitrary statements, only to statements of a specific logical form (so called "geometric sequents"). But the statement "there are infinitely many prime numbers" can be put into such a form. Also, in case you are wondering, this metatheorem admits itself a constructive proof. Summarizing, there is a mechanical way to turn any nonconstructive proof of the infinitude of the primes into a constructive one. The key words to look up here are "double-negation translation" and "Friedman's trick". Fantastically, the double-negation translation turns out to be "the same as" the continuation-passing style transformation, if viewed from the right angle. Some pointers are in this slide deck: http://rawgit.com/iblech/talk-constructive-mathematics/master/negneg-translation.pdf http://rawgit.com/iblech/talk-constructive-mathematics/maste...

rnhmjoj 11y ago

I wonder, do proofs of this kind, where some process is repeated forever to prove the thesis, have an infinite length? Could this be made into a finite number of steps in some formal system? Using a rule of induction maybe?