A One-Line Proof of the Infinitude of Primes | Hacker News Reader

A One-Line Proof of the Infinitude of Primes

fermatslibrary.com

49 pointsluisb66 comments

The 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.

Correct. 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".

I'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.

A one-line APL program like this: https://www.youtube.com/watch?v=a9xAKttWgP4, is it really one-line?

Engineer'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 ?

People 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.

> 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 ….)

Yes, 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.

There'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.

> And actually any periodic function that is zero somewhere could be used in a tiny bit modified version of this proof.

I think that, for the modification to be tiny, you need something like: there is an interval on which the function is positive, and on the boundary of which it vanishes. (Some sign condition is necessary; taking the constant function at 0 doesn't work! Of course, this particular condition is automatically satisfied for any continuous, periodic function that vanishes somewhere, but is not identically 0.)

That is true but in Trigonometry Sine the function one studies and so using this result in a trigonometry course is nice.

As 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.

I 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).

Depending 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.

> 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

How about: one plus the product of a list of primes has a prime factor not in the list.

Yup, that works!

I like that version better anyway. Thanks for helping me improve it!

Yes! 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.

I would have been fine with "would have to be prime"; I like the edit Mike suggested even better.

We know it can be written out as a haiku: https://xkcd.com/622/!

While 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?

Couldn't you just change "divisors' product" to "factorial's"? I guess that it does some violence to the metre.

You could work with it and get the original last line back:

  Factorial of
  top prime, plus one: factor that!
  Q.E.D., bitches!

But then you can't exclaim Q.E.D., bitches! and it would be a terrible cartoon. :)

It's restored in a version further down in the thread.

It's not the factorial either, that would include composites in the product too.

Euclid didn't use the factorial in his original proof, but it still produces a logically correct argument and it has fewer syllables. Metri causa. :-)

Using 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.

I'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.

This 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.

Explanation:

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 <.

Here's an video with some explanation:

https://www.youtube.com/watch?v=-v6yPtM4VLA

> 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?

If 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.

A question that came to mind for me from this: is there any sequence k such that all 0<kₓ<1 and the product of all kₓ converges to something greater than 0? While each partial product must be smaller than the preceding one, is it possible to make k grow fast enough toward 1 that the rate of diminution of the partial products slows enough that they converge to a positive limit?

I'm pretty sure that the answer is yes, but not certain!

Yes, here is an example:

Xn = exp(-1/(2^(n+2)))

∏Xn -> exp(-1/2)

Thanks! That's awesome.

As a clarification for anyone reading this later, "where the value becomes closer" means "where the value becomes (and thereafter remains) closer".

Correct. For example the series (1/n)(1/n+1)(1/n+2)... converges to zero as n-> ∞ (actually the term is "diverges to zero" for products)

You can play around with different series on Wolfram Alpha https://www.wolframalpha.com/input/?i=infinite+product+1%2Fn

Consider 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.

Yes. 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.

Yes -- 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.

If 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.

Rarely you can find a proof that assumes the axiom of choice in such an obvious way.

Can you expand? Many proofs assume the axiom of choice, and I'm missing how this one does.

It doesn't. For one thing, the axiom of choice is only necessary in situations with infinite sets, and this has none.

Of 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.

> 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

> intuitionistic logic has no interpretation as a two-valued logic

One thing to note is that theorem provers/proof assistants like Coq and Agda are based on constructive mathematical foundations (calculus of constructions). Type theory (related to types in programming languages, lambda calculus is one potential example) is also fundamentally constructive.

Not a proof.

Should be re-titled: "One-Line proof that I use circular arguments."

One real numbers: https://www.youtube.com/watch?v=fXdFGbuAoF0&index=5&list=PLI...

How does the periodicity of the sine function depend upon the infinitude of primes?

It's stated in the only english text of the "proof":

>If the set of primes is ﬁnite

All conclusions are true when your premise is false:

https://en.wikipedia.org/wiki/Truth_table#Logical_implicatio...

"the set of primes is finite"?

What is "the set of primes" ??????

Because real numbers and infinities are a fairy tale.

This enlightening video makes it clear:

https://youtu.be/4DNlEq0ZrTo?list=PLIljB45xT85Bfc-S4WHvTIM7E...

This 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.

(For anyone else reading this who might be misled, note that OP's position is generally considered to be "crank" mathematics)

For anyone who might be misled, here are some links that people can use to judge for themselves how "crank" someone is:

Professor Norman Wildberger's homepage:

http://web.maths.unsw.edu.au/~norman/

...a paper by Wildberger tackling some of the issues in this thread:

Set Theory: Should You Believe?

http://web.maths.unsw.edu.au/~norman/papers/SetTheory.pdf

Some interesting works by Gregory Chaitin

Meta Math! The Quest for Omega

https://arxiv.org/abs/math/0404335

Exploring Randomness

https://www.cs.auckland.ac.nz/~chaitin/ait/

How Real are Real Numbers?

https://arxiv.org/abs/math/0411418

People who are interested in ultrafinitism would also want to check out Doron Zeilberger

http://www.math.rutgers.edu/~zeilberg/

and

Edward Nelson

https://web.math.princeton.edu/~nelson/

It is definitely not a standard or mainstream view, but it could be a flavor of https://en.wikipedia.org/wiki/Finitism which has been defended by a very small but not infinitesimal :-) number of professional mathematicians and which isn't a logically inconsistent position.

Personally, I am an ultrafinitist.

By that I mean that I believe that physical systems can be completely described by constructive mathematics based on intuitionistic logic[2] operating on computable reals[3]. I believe that any other kind of mathematics, e.g. classical logic with axiom of choice can create unphysical models.

That being said, I don't object to classical logic as a purely abstract concept. Everything proved in ZFC is certainly true in ZFC! And I don't think any finitist will contest that.

[1] https://en.wikipedia.org/wiki/Ultrafinitism

[2] https://en.wikipedia.org/wiki/Intuitionistic_logic

[3] https://en.wikipedia.org/wiki/Computable_number

What a rigorous way to defend your position! Calling names!

I bet you are an infinitely good Cantorian ! Did you speak with God recently?

You got as much rigor as you gave. Disproving every wacky position with a careful analysis is impossible, nobody has that much time.

Indeed, there are an almost infinite number of crank theories because they don't require logic, evidence, or proof - just belief. One crank can churn out a hundred nonsense theories in the time it takes someone to validate one scientific idea or mathematical proof.

This has a corollary in the startup world: everyone has an idea, what matters is execution.

Uhhhh...no. Take a look at Dedekind cuts.

The linked video is largely a critique of Dedekind cuts, arguing that they don't in general let us recognize, distinguish, or perform arithmetic on most real numbers. (Almost all of the informational input to a Dedekind cut for a randomly chosen real couldn't be written, remembered, or specified in any way by a human being.)

I think the presenter in the video is trying to justify a kind of finitist attitude based on the inaccessibility and unspecifiability of reals-in-general to us. This could also be advocating a position something like

https://en.wikipedia.org/wiki/Computable_number#Can_computab...

Edit: or perhaps https://en.wikipedia.org/wiki/Constructive_analysis (I didn't watch enough to understand exactly what alternative he proposes)

> Almost all of the informational input to a Dedekind cut for a randomly chosen real couldn't be written, remembered, or specified in any way by a human being.

Well, yes. The reals are uncountable.

Reply on news.ycombinator.com