8 ms·
A One-Line Proof of the Infinitude of Primes
- buzzdenver 10y agoEngineer's honest question to a mathematician: is this proof more simple than the one the multiplies all the supposedly finite primes and shows that their product plus or minus one is not divisible by any of those primes, ergo there are always more primes ?
- quantumtremor 10y agoI'm not a mathematician but I'd say no since trig functions inherently require a lot more math to formulate, whereas Euclid's proof follows from much simpler facts.
- schoen 10y agoI see that proof, due to Euclid, as simpler because it doesn't require any facts about trigonometric functions. It might be harder to write out in mathematical notation in one line, but maybe I should try (using set-builder notation or something).
- quantumtremor 10y agoWe know it can be written out as a haiku: https://xkcd.com/622/ https://xkcd.com/622/!
- schoen 10y agoWhile that's very clever, it doesn't accurately present Euclid's argument because the haiku is Top prime's divisors' product (plus one)'s factors are...? Q.E.D., bitches! This doesn't include Euclid's argument about multiplying all of the primes, mistakenly referring instead to "top prime's divisors". The "top prime's divisors' product" would be equal to the top prime itself, so Randall's haiku asks "if there is a largest prime p, what are the divisors of (p+1)?" which doesn't create any contradiction (it could simply be divisible by various smaller primes!). Maybe we should amend it to Take factorial of top prime, then add one: what are the divisors?
- adrianratnapala 10y agoIt's not the factorial either, that would include composites in the product too.
- schoen 10y agoEuclid didn't use the factorial in his original proof, but it still produces a logically correct argument and it has fewer syllables. Metri causa. :-)
- JadeNB 10y agoUsing the factorial is better, I think, even if ahistorical; it avoids the slight unpleasantness of having to show that every non-unit integer is divisible by a prime.
- wangarific 10y agoBut then you can't exclaim Q.E.D., bitches! and it would be a terrible cartoon. :)
- schoen 10y agoIt's restored in a version further down in the thread.
- JadeNB 10y agoCouldn't you just change "divisors' product" to "factorial's"? I guess that it does some violence to the metre.
- schoen 10y agoYou could work with it and get the original last line back: Factorial of top prime, plus one: factor that! Q.E.D., bitches!
- mikeash 10y agoDepending on how much you're willing to assume and what exactly counts as "one line," it could be as simple as: > One plus the product of all primes is itself prime, and larger than all primes. This omits a bunch of stuff, but it seems like less than the linked paper.
- dllthomas 10y ago> One plus the product of all primes is itself prime One plus the product of the first N primes is not necessarily prime. Consider 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 59 * 509
- mikeash 10y agoHow about: one plus the product of a list of primes has a prime factor not in the list.
- jwatte 10y agoYes! Because primes are infinite! The statement assumes limited primes. And, because it falsifies, it proves primes must be unlimited. I find this argument based on prime factors much simpler.
- dllthomas 10y agoI would have been fine with "would have to be prime"; I like the edit Mike suggested even better.
- deleted 10y ago
- yequalsx 10y agoPeople tend to think of the proof you are thinking of as easier because they are more familiar with it. There are some subtle things that the proof you mentioned glosses over. Namely, if p|A and p|B then p|(A-B). Now this is not a deep concept but it is something which people who are not accustomed to thinking of proofs tend to gloss over. Namely, they will see the part that if P = p1 p2 p3...pn + 1 and p|P then p|1 and not think that this does itself require justification. Personally, I really like the proof using sines. I won't claim it is easier or simpler but it is very nice. I've never thought to prove the infinitude of primes this way and it uses facts from trigonometry. I will now incorporate this into my trig classes. I think it is quite straightforward and easy for one to understand. Students in trigonometry and calculus generally do not have experience in proving statements about arithmetic. Here is an excellent way to show a connection between concepts that seemingly have nothing to do with each other. It is this that mathematicians really like.
- JadeNB 10y ago> Namely, they will see the part that if P = p1 p2 p3...pn + 1 and p|P then p|1 and not think that this does itself require justification. While your point that every step of a proof requires justification is a good one, this is really, really easy to verify. That doesn't excuse one from actually giving that justification, in the course of a formal proof; but there's at least as much implicit knowledge bound up in the linked proof. (For example, one needs the existence of sine, its 2π-periodicity, the fact that it is positive from 0 to π/2 ….)
- yequalsx 10y agoYes, definitely there is more information implicitly wrapped into the sine proof. That's why it's not simpler. However, it is not a worse proof either. It's just a different one that is clever and can help to reinforce concepts from trigonometry.
- bonoboTP 10y agoThere's not much trigonometry in this proof, just the fact that sine has period 2pi is zero at pi. Any function that has these two properties could directly replace sine in this proof. And actually any periodic function that is zero somewhere could be used in a tiny bit modified version of this proof.
- adrianratnapala 10y agoAs others have said, the proof relies on some trig facts (Though maybe you can replace `sin` with any zero-crossing periodic function). But it's worse than that. The only proof I can see for the second equality there depends on showing the numerator is composite. And that in turn depends on something very like the argument you mention. So unless there is a much simpler proof of that equality, the proof is only a "one liner" because it leaves Euclid's argument as an exercise to the reader.
- deleted 10y ago[deleted]
- blevinstein 10y agoThis proof is nearly equivalent to that proof, but uses the sine function to generate a contradiction. The crucial step involves the fact that: 1 + 2 * product(p', p') must be divisible by some prime number, where product(p', p') is the product of all primes you were talking about.
- mbreedlove 10y agoHere's an video with some explanation: https://www.youtube.com/watch?v=-v6yPtM4VLA https://www.youtube.com/watch?v=-v6yPtM4VLA
- pierre_d528 10y agoShould be re-titled: "One-Line proof that I use circular arguments." One real numbers: https://www.youtube.com/watch?v=fXdFGbuAoF0&index=5&list=PLIljB45xT85AzmoZKEgFs6RPaFvKmJHYt https://www.youtube.com/watch?v=fXdFGbuAoF0&index=5&list=PLI...
- jackmaney 10y agoHow does the periodicity of the sine function depend upon the infinitude of primes?
- pierre_d528 10y agoBecause real numbers and infinities are a fairy tale. This enlightening video makes it clear: https://youtu.be/4DNlEq0ZrTo?list=PLIljB45xT85Bfc-S4WHvTIM7E-ir3nAOf&t=2577 https://youtu.be/4DNlEq0ZrTo?list=PLIljB45xT85Bfc-S4WHvTIM7E...
- schoen 10y agoThis argument is seemingly related to Gregory Chaitin's views on noncomputability and nondefinability. Chaitin observes that almost all real numbers cannot be referred to, or singled out, by any mathematical method available to us -- for example because definable numbers using a language or notation must have the cardinality of the natural numbers, but we know from Cantor that the cardinality of the reals should be larger. Chaitin simply thought this was an impressive fact about the reals and the limitations of mathematics -- a way in which mathematics contains randomness and that many or most facts are "true for no particular reason". This author instead seems to conclude for a related reason that the reals don't exist because we have (and could have) no usable technique to distinguish most real numbers from one another. His complaint in this video is a Chaitin-like observation that we have no way to distinguish real number A from real number B in a finite amount of time or with a finite amount of reasoning or information, and an un-Chaitin-like conclusion that maybe we then have no reason to believe that these numbers exist and are distinct from each other. Edit: and he emphasizes later that if we believe in the reals, numbers must exist that we can't actually do arithmetic with (which I would suggest is sometimes for the Chaitinesque reason that we can't name or define them, or other times for the weaker Chaitinesque reason that we can't calculate their values), so he seems to ask what good such numbers are to us or what reason we could have to believe that they are real.
- 4ad 10y agoRarely you can find a proof that assumes the axiom of choice in such an obvious way.
- mbroshi 10y agoCan you expand? Many proofs assume the axiom of choice, and I'm missing how this one does.
- paulddraper 10y agoIt doesn't. For one thing, the axiom of choice is only necessary in situations with infinite sets, and this has none.
- 4ad 10y agoOf course it has infinite sets, N is an infinite set, and the proof makes a statement about another infinite set, the set of primes. This proof is non-constructive because proof-by-contradiction proofs that can't be changed into proof-by-negation proofs are not allowed in constructive math, because there's no law of excluded middle with infinite sets in constructive math, which follows from a lack of a strong axiom of choice. This proof says that the set of prime numbers can't be finite. Only in classical logic you can deduce from this that the set of prime numbers must be infinite. In intuitionistic logic you can't deduce this. This is interesting because most "normal" proofs and results can be written so that they are valid both in classical logic and intuitionistic logic. Only "crazy" results like the Banach–Tarski theorem are different. An yet this is a trivial proof of a trivial result that can't be easily converted to constructivism. That is why it screams of axiom of choice.
- paulddraper 10y ago> Only in classical logic you can deduce from this that the set of prime numbers must be infinite. In intuitionistic logic you can't deduce this. ? I was not aware of any system where proof by contradiction isn't acceptable. The opposite of false is true. But apparently you are right. https://en.wikipedia.org/wiki/Intuitionistic_logic https://en.wikipedia.org/wiki/Intuitionistic_logic > intuitionistic logic has no interpretation as a two-valued logic
- ars 10y ago> since infinite products can converge to 0 even if all the terms are positive. Eh? Can someone explain? Is that because you are multiplying a huge amount of numbers << 1?
- kkylin 10y agoYes. Easiest example would be just the product of a_n, n=1,2,3,..., with a_n=same constant in (0,1). Then all the partial products will be positive, but the limit is clearly 0.
- andrewla 10y agoYes -- just look at Pi_0^inf(.1), the partial products are just 0.1^n, and the limit of that as n goes to infinity is zero.
- deleted 10y ago[deleted]
- witty_username 10y agoConsider the product of the sequence which has ½ repeated N times. The product is (½)^N; which halves each time. If we want the product to go below x, then we can plug in N > log2(1/x). Since for any x > 0 we can find an N, we say lim (½)^∞ = 0. tl;dr Basically, as N goes to infinity, the product gets arbitrarily close to 0.
- deleted 10y ago[deleted]
- schoen 10y agoIf you define the value of an infinite operation as its limit, as mathematicians normally do, then you can make a limit argument for an infinite product of many numbers 0<n<1 being zero because each additional number that you multiply makes the product smaller, and you can find a point at which they will go smaller than any chosen positive number. In the epsilon-delta concept of limits (you challenge me to show where the value becomes closer than an epsilon of your choice to the purported limit; I show you where that happens) this then suffices to show that the limit is 0. For example, suppose we multiply 0.9 by itself an infinite number of times. If we want it to be smaller than epsilon, we have to multiply it ceil(log_0.9(epsilon))+1 times. For instance, if you want it to get smaller than 0.01, the formula shows you should multiply it 45 times (actually 44 times suffices; the +1 is just for the case where it equals epsilon exactly). Here 0.9⁴⁵=0.00872796356808771242 which is indeed smaller than 0.01.
- deleted 10y ago[deleted]
- jsprogrammer 10y agoNot a proof.
- pklausler 10y agoIf there were a finite set of all primes, none of them would evenly divide the number after its product, so you'd have a prime that's not in the set. So there ain't no such thing. Fits on one line if the font is small enough.
- bonoboTP 10y agoThe whole sine and product business just encodes and obfuscates the claim that "there exists a prime p, such that (1+2product_of_primes) is divisible by p". And the two sides of the equation just show how both the claim and its negation can be derived if one assumes a finite set of primes. It's true since any natural number > 1 (including 1+2*product_of_primes) has a prime divisor, and it's false because for any prime p, 2product_of_primes is divisible by p but 1 is not, so the sum cannot be divisible by p. It's actually the classic proof at its core, just with some obfuscation.
- paulddraper 10y agoCorrect. The non-zeroness of the product is a logical AND of the non-zeroness of the terms. And the sin establishes that the argument/pi is non-integer. Still, I think it's quite clever, even if fundamentally "not new".
- paulddraper 10y agoExplanation: 1. sin(pi/p) is non-zero for any prime p since 1/p is not an integer. Thus the product is non-zero. 2. Since sin has period 2pi and product(p')/p is an integer, sin(pi/p) = sin(pi/p + 2pi*product(p')/p) = sin((1 + 2product(p'))pi/p) All integers over two are divisible by some prime so (1 + 2product(p'))/p is an integer for some p, and the sin is 0. Since one of the terms is zero, the product is zero. --- As bonoboTP, points out, this is simply encoding logic into math functions. * TRUE is non-zero; FALSE is zero. * AND is product. * N IS INTEGER is sin(n * pi). Note that I think 0 != to be semantically simpler than 0 <.
- chias 10y agoI'm not a big fan of "one-line proofs". Any proof is a one-liner if you omit the details of how you get from A to B. I'd liken the utility of something like this to that of a "one-line program" where you just don't take a new line after the semicolons, and you skip all the initialization because "it's obvious given the context". The contents of the explanatory sidebar, while not one line, are significantly better than the contents of the main page.
- 4ad 10y agoA one-line APL program like this: https://www.youtube.com/watch?v=a9xAKttWgP4 https://www.youtube.com/watch?v=a9xAKttWgP4, is it really one-line?