8 ms·

Formalising a new proof that the square root of two is irrational

103 points by ColinWright 4y ago

ta123456789 4y ago
It's a nice proof, but probably not new. Same proof for example here: https://mathoverflow.net/a/32031 https://mathoverflow.net/a/32031
graycat 4y ago
Let's have a simple proof so that we don't have to argue about more complicate issues: For integers p, q with q not 0, suppose 2 = (p/q)^2 Then 2 q^2 = p^2 and the left size has an odd number of factors of 2 and the right side has an even number of factors of 2, a contradiction. Therefore such p, q do not exist, and 2 does not have a rational square root. Done.
- tromp 4y ago
  It is simple if you can assume unique factorization of positive integers [1]. [1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme...
  - hgsgm 4y ago
    Which is proven in a similar way as OP's proof.
    - ColinWright 4y ago
      ... but genuinely requires a lot more work to do carefully and properly. People underestimate how much work it is to create a non-handwavey proof of the FTA. Tim Gowers has written about this (although I don't have the reference to hand, and I'm on a train with a dodgy connection).
  - graycat 4y ago
    > It is simple if you can assume unique factorization of positive integers [1]. Since the fundamental theorem of arithmetic is a classic and fundamental pillar of math, in writing math is it not appropriate to say "if you can assume".
- jameshart 4y ago
  I don’t think you can make assumptions about how factors combine on multiplication (ie that multiplying by two adds one factor of two) in a context where integers can have rational noninteger roots. If we can have x=(a/b)^2 and y=(b/c)^2, then xy=(a/c)^2 so any factors of b^2 have somehow dropped out, rather than being added in to the factors of the product. Obviously in the end this all ends up contradicting the fundamental theorem of arithmetic, but it’s not clear this doesn’t wind up being circular.
- raldi 4y ago
  > and the left size has an odd number of factors of 2 and the right side has an even number of factors of 2, a contradiction. Can you explain this step further?
  - graycat 4y ago
    If I had explained it further, then the proof would have been longer! Right, we need the Fundamental Theorem of Arithmetic, that each integer factors uniquely into a product of prime numbers; right, that statement leaves out a little about the order of the factors. Well, 2 is prime number. So however many factors of 2 q has, q^2 has twice that many and, thus, an even number of factors of 2. Same argument for p^2; it also has an even number of factors of 2. But then 2 q^2 has an odd number of factors of 2. Uh, more generally, we can keep arithmetic simple or make it complicated. E.g., multiplication of integers is associative so that (2 x 3) x 4 = 2 x (3 x 4) The intermediate results are different, but the final results are the same. So there is a little something there (matrix multiplication is also associative, with more there -- right, easily function composition is associative so regard a matrix as a function and matrix multiplication as function composition). We can keep the Fundamental Theorem of Arithmetic simple, e.g., ask a 4rd grader, or make it complicated: To make arithmetic complicated, we can take a college course in abstract algebra that proves all this. Then for still more complicated we can go through axiomatic set theory before the abstract algebra course. Then in the set theory course we can get to undecidable issues. I went through all that. Instead, what I wanted was differential geometry as background for general relativity, partial differential equations for the various applications, but I'd put up with exterior algebra, of course the inverse and implicit function theorems (proved in Fleming's book and an exercise in Rudin's), fluid flow, Maxwell's equations, Schroedinger's equation, Fourier theory, Lebesgue integration, Leibniz's rule (differentiation under the integral sign; there's a simple proof if assume enough continuity and a more general proof from Lebesgue theory), how come, with Lagrange, action is stationary, on and on. I was willing to take arithmetic as okay!
    - raldi 4y ago
      Sounds like the crux is that 2(x^2) = y^2 can never be true for any integers x and y because any square of an integer must have an even number of 2's in its prime factorialization, and any doubled square of an integer must have an odd number.
hiq 4y ago
https://www.cambridge.org/core/journals/mathematical-gazette/article/abs/593-the-irrationality-of-2/18BADD0AB7114F1809B9F3EF6F82D20F https://www.cambridge.org/core/journals/mathematical-gazette... https://en.wikipedia.org/wiki/Theodor_Estermann https://en.wikipedia.org/wiki/Theodor_Estermann
- deleted 4y ago
  [deleted]
jhncls 4y ago
Burkard Polster and Marty Ross at Mathologer have some wonderful videos visually proving the irrationality of many roots. [0] https://youtu.be/yk6wbvNPZW0 https://youtu.be/yk6wbvNPZW0
janm31415 4y ago
I might be missing something, but as I see it here: by assumption, √2 is rational. Then k(√2-1) √2 is a positive integer. This does not mean that k(√2 - 1) belongs to K, with K the set of positive integers {n: n√2 ∈ ℤ}, as k(√2 - 1) is not necessarily an integer. The proof can be fixed I think with K the set of rational numbers {q: q√2 ∈ ℤ}
- johnnny 4y ago
  k * √2 is an integer, and k is an integer, by construction of K and the initial assumption that K is not empty. Therefore their difference k * √2 - k = k * (√2 - 1) is an integer.
  - janm31415 4y ago
    correct, I missed that.
    - johnnny 4y ago
      As fro your further edit: assuming √2 is rational, then the set of ~~rational~~ integers {q: q√2 ∈ ℤ} does not admit a minimum, indeed it contains arbitrarily small numbers, so we can't pick k the smallest member of that set.
SideQuark 4y ago
I always liked the simple to follow proof: Assume √2=m/n, and take m,n reduced so that 2 does not divide both (i.e., cancel 2's out of the fraction). . Then 2nn = mm. Then 2 divides the left hand side, so 2 must divide the right hand side, so 2 must divide m. Then 22 = 4 divides the right hand side, so divides the left hand side, so 2 must divide the (n*n) part. But then 2 divides n, contradicting that 2 does not divide both m and n. This works without much changes for sqrt of any non-square.
wedn3sday 4y ago
So, do we throw this guy off the cliff too?
- schoen 4y ago
  For people who don't get the reference: https://en.wikipedia.org/wiki/Irrational_number#Ancient_Greece https://en.wikipedia.org/wiki/Irrational_number#Ancient_Gree...
- fluoridation 4y ago
  I thought they'd thrown him off a boat to drown.
peace177 4y ago
[dead]
nanis 4y ago
> Recently, somebody shared on Twitter a new proof As far as I can tell there is no link to this tweet in this post which is bad form to say the list. The post has multiple links promoting author's other posts, but not to the raison d'etre for this post. Clarification: The post does link to a Tumbler post which one might infer had been mentioned in the tweet, but without a link to said tweet, it's odd. It is common to give credit to the work that led to one's discovery of related work. PS: Apparently, the author is Director of Research, Computer Laboratory, University of Cambridge which makes this lack of proper citation even more perplexing. PPS: Compare the intro paragraph of this post to one that properly cites related work[1] with actual links to the referenced works: >> Yesterday I came a across a new (new to me, that is) proof of the irrationality of \sqrt{2}. I found it in the paper “Irrationality From The Book,” by Steven J. Miller, David Montague, which was recently posted to arXiv.org. PPPS: It is especially ironic that the author has also wrote this at some point[2]: >>> Many people write their related work section in a wholly passive mockery of English, never mentioning the names of their colleagues: ... It’s discourteous and reads badly. Reference numbers are not names, so why do you keep forcing your reader to look them up in the bibliography? The direct way is also clearer: ... [1]: https://divisbyzero.com/2009/10/06/tennenbaums-proof-of-the-irrationality-of-the-square-root-of-2/ https://divisbyzero.com/2009/10/06/tennenbaums-proof-of-the-... [2]: https://www.cl.cam.ac.uk/~lp15/Pages/Scream.html https://www.cl.cam.ac.uk/~lp15/Pages/Scream.html
- ajb 4y ago
  An academic paper should cite sources because such a paper makes a claim to originality of its own. So it is 'bad form' not to cite sources because you would be implying that their work is yours. A blog post does not necessarily claim originality and in particular this one does not, it's showing how a proof can be automated. Of course, it's a good idea to cite sources anyway and it's a convenience for the reader, as well as a courtesy to the authors. But it's not a moral failing. If blog posts were as onerous to write as journal articles, there would be no advantage to blogging.
- adunk 4y ago
  The first sentence in the blog post contains a link to the proof itself, which seems to have been posted to tumblr: https://theapproximatepresent.tumblr.com/post/51484587425/a-favourite-proof-of-mine-first-demonstrated-to https://theapproximatepresent.tumblr.com/post/51484587425/a-... I'm not sure it is necessary for the author also post the link to the tweet that referred to the tumblr post, since the tumblr post is where the actual proof is.
bdrum 4y ago
Looks very cool, but what I've wondered - there is any other tool like Isabelle? upd. https://en.wikipedia.org/wiki/Proof_assistant https://en.wikipedia.org/wiki/Proof_assistant
- ykonstant 4y ago
  In the mathematical community, the best known proof assistants are Coq, Lean and Isabelle.
tromp 4y ago
The new proof rephrased: Let K be the set of positive integers k such that k √2 is an integer. Suppose K is non-empty, denote its minimum as k. Consider the positive integer k' = k √2 - k = k (√2 - 1). Then k' < k and k' is also in K since k' √2 = 2 k - k √2, contradicting non-emptyness of K.
- xurukefi 4y ago
  That's an interesting proof, because I can easily follow it mechanically, but I have absolute no intuition for it.
  - pfortuny 4y ago
    The minimum k is the denominator of the supposed irreducible fraction p/q=sqrt(2). He is stating that then there is a different irreducible fraction r/s=sqrt(2). This is because you would have p^2=2q^2 with p and q mutually prime, which is impossible. Instead of irreducible fractions with coprime numbers, he is doing the “dual” using the minimum possible value of the denominator.
- deleted 4y ago
  [deleted]
- scotty79 4y ago
  [deleted]
  - pfortuny 4y ago
    Notice thay you know sqrt(2)<2 (this is easy), which does not happen in your case.
  - deleted 4y ago
    [deleted]
- phkahler 4y ago
  Love a proof by infinite descent! But you do make the assumption that (√2 - 1) is positive and less than 1. Root 2 can be negative.

103 points by ColinWright 4y ago

It's a nice proof, but probably not new. Same proof for example here: https://mathoverflow.net/a/32031 https://mathoverflow.net/a/32031

graycat 4y ago

Let's have a simple proof so that we don't have to argue about more complicate issues: For integers p, q with q not 0, suppose 2 = (p/q)^2 Then 2 q^2 = p^2 and the left size has an odd number of factors of 2 and the right side has an even number of factors of 2, a contradiction. Therefore such p, q do not exist, and 2 does not have a rational square root. Done.

tromp 4y ago
It is simple if you can assume unique factorization of positive integers [1]. [1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme...
- hgsgm 4y ago
  Which is proven in a similar way as OP's proof.
  - ColinWright 4y ago
    ... but genuinely requires a lot more work to do carefully and properly. People underestimate how much work it is to create a non-handwavey proof of the FTA. Tim Gowers has written about this (although I don't have the reference to hand, and I'm on a train with a dodgy connection).
- graycat 4y ago
  > It is simple if you can assume unique factorization of positive integers [1]. Since the fundamental theorem of arithmetic is a classic and fundamental pillar of math, in writing math is it not appropriate to say "if you can assume".
jameshart 4y ago
I don’t think you can make assumptions about how factors combine on multiplication (ie that multiplying by two adds one factor of two) in a context where integers can have rational noninteger roots. If we can have x=(a/b)^2 and y=(b/c)^2, then xy=(a/c)^2 so any factors of b^2 have somehow dropped out, rather than being added in to the factors of the product. Obviously in the end this all ends up contradicting the fundamental theorem of arithmetic, but it’s not clear this doesn’t wind up being circular.
raldi 4y ago
> and the left size has an odd number of factors of 2 and the right side has an even number of factors of 2, a contradiction. Can you explain this step further?
- graycat 4y ago
  If I had explained it further, then the proof would have been longer! Right, we need the Fundamental Theorem of Arithmetic, that each integer factors uniquely into a product of prime numbers; right, that statement leaves out a little about the order of the factors. Well, 2 is prime number. So however many factors of 2 q has, q^2 has twice that many and, thus, an even number of factors of 2. Same argument for p^2; it also has an even number of factors of 2. But then 2 q^2 has an odd number of factors of 2. Uh, more generally, we can keep arithmetic simple or make it complicated. E.g., multiplication of integers is associative so that (2 x 3) x 4 = 2 x (3 x 4) The intermediate results are different, but the final results are the same. So there is a little something there (matrix multiplication is also associative, with more there -- right, easily function composition is associative so regard a matrix as a function and matrix multiplication as function composition). We can keep the Fundamental Theorem of Arithmetic simple, e.g., ask a 4rd grader, or make it complicated: To make arithmetic complicated, we can take a college course in abstract algebra that proves all this. Then for still more complicated we can go through axiomatic set theory before the abstract algebra course. Then in the set theory course we can get to undecidable issues. I went through all that. Instead, what I wanted was differential geometry as background for general relativity, partial differential equations for the various applications, but I'd put up with exterior algebra, of course the inverse and implicit function theorems (proved in Fleming's book and an exercise in Rudin's), fluid flow, Maxwell's equations, Schroedinger's equation, Fourier theory, Lebesgue integration, Leibniz's rule (differentiation under the integral sign; there's a simple proof if assume enough continuity and a more general proof from Lebesgue theory), how come, with Lagrange, action is stationary, on and on. I was willing to take arithmetic as okay!
  - raldi 4y ago
    Sounds like the crux is that 2(x^2) = y^2 can never be true for any integers x and y because any square of an integer must have an even number of 2's in its prime factorialization, and any doubled square of an integer must have an odd number.

hiq 4y ago

https://www.cambridge.org/core/journals/mathematical-gazette/article/abs/593-the-irrationality-of-2/18BADD0AB7114F1809B9F3EF6F82D20F https://www.cambridge.org/core/journals/mathematical-gazette... https://en.wikipedia.org/wiki/Theodor_Estermann https://en.wikipedia.org/wiki/Theodor_Estermann

deleted 4y ago
[deleted]

jhncls 4y ago

Burkard Polster and Marty Ross at Mathologer have some wonderful videos visually proving the irrationality of many roots. [0] https://youtu.be/yk6wbvNPZW0 https://youtu.be/yk6wbvNPZW0

janm31415 4y ago

I might be missing something, but as I see it here: by assumption, √2 is rational. Then k(√2-1) √2 is a positive integer. This does not mean that k(√2 - 1) belongs to K, with K the set of positive integers {n: n√2 ∈ ℤ}, as k(√2 - 1) is not necessarily an integer. The proof can be fixed I think with K the set of rational numbers {q: q√2 ∈ ℤ}

johnnny 4y ago
k * √2 is an integer, and k is an integer, by construction of K and the initial assumption that K is not empty. Therefore their difference k * √2 - k = k * (√2 - 1) is an integer.
- janm31415 4y ago
  correct, I missed that.
  - johnnny 4y ago
    As fro your further edit: assuming √2 is rational, then the set of ~~rational~~ integers {q: q√2 ∈ ℤ} does not admit a minimum, indeed it contains arbitrarily small numbers, so we can't pick k the smallest member of that set.

SideQuark 4y ago

I always liked the simple to follow proof: Assume √2=m/n, and take m,n reduced so that 2 does not divide both (i.e., cancel 2's out of the fraction). . Then 2nn = mm. Then 2 divides the left hand side, so 2 must divide the right hand side, so 2 must divide m. Then 22 = 4 divides the right hand side, so divides the left hand side, so 2 must divide the (n*n) part. But then 2 divides n, contradicting that 2 does not divide both m and n. This works without much changes for sqrt of any non-square.

wedn3sday 4y ago

So, do we throw this guy off the cliff too?

schoen 4y ago
For people who don't get the reference: https://en.wikipedia.org/wiki/Irrational_number#Ancient_Greece https://en.wikipedia.org/wiki/Irrational_number#Ancient_Gree...
fluoridation 4y ago
I thought they'd thrown him off a boat to drown.

peace177 4y ago

[dead]

nanis 4y ago

> Recently, somebody shared on Twitter a new proof As far as I can tell there is no link to this tweet in this post which is bad form to say the list. The post has multiple links promoting author's other posts, but not to the raison d'etre for this post. Clarification: The post does link to a Tumbler post which one might infer had been mentioned in the tweet, but without a link to said tweet, it's odd. It is common to give credit to the work that led to one's discovery of related work. PS: Apparently, the author is Director of Research, Computer Laboratory, University of Cambridge which makes this lack of proper citation even more perplexing. PPS: Compare the intro paragraph of this post to one that properly cites related work[1] with actual links to the referenced works: >> Yesterday I came a across a new (new to me, that is) proof of the irrationality of \sqrt{2}. I found it in the paper “Irrationality From The Book,” by Steven J. Miller, David Montague, which was recently posted to arXiv.org. PPPS: It is especially ironic that the author has also wrote this at some point[2]: >>> Many people write their related work section in a wholly passive mockery of English, never mentioning the names of their colleagues: ... It’s discourteous and reads badly. Reference numbers are not names, so why do you keep forcing your reader to look them up in the bibliography? The direct way is also clearer: ... [1]: https://divisbyzero.com/2009/10/06/tennenbaums-proof-of-the-irrationality-of-the-square-root-of-2/ https://divisbyzero.com/2009/10/06/tennenbaums-proof-of-the-... [2]: https://www.cl.cam.ac.uk/~lp15/Pages/Scream.html https://www.cl.cam.ac.uk/~lp15/Pages/Scream.html

ajb 4y ago
An academic paper should cite sources because such a paper makes a claim to originality of its own. So it is 'bad form' not to cite sources because you would be implying that their work is yours. A blog post does not necessarily claim originality and in particular this one does not, it's showing how a proof can be automated. Of course, it's a good idea to cite sources anyway and it's a convenience for the reader, as well as a courtesy to the authors. But it's not a moral failing. If blog posts were as onerous to write as journal articles, there would be no advantage to blogging.
adunk 4y ago
The first sentence in the blog post contains a link to the proof itself, which seems to have been posted to tumblr: https://theapproximatepresent.tumblr.com/post/51484587425/a-favourite-proof-of-mine-first-demonstrated-to https://theapproximatepresent.tumblr.com/post/51484587425/a-... I'm not sure it is necessary for the author also post the link to the tweet that referred to the tumblr post, since the tumblr post is where the actual proof is.

bdrum 4y ago

Looks very cool, but what I've wondered - there is any other tool like Isabelle? upd. https://en.wikipedia.org/wiki/Proof_assistant https://en.wikipedia.org/wiki/Proof_assistant

ykonstant 4y ago
In the mathematical community, the best known proof assistants are Coq, Lean and Isabelle.

tromp 4y ago

The new proof rephrased: Let K be the set of positive integers k such that k √2 is an integer. Suppose K is non-empty, denote its minimum as k. Consider the positive integer k' = k √2 - k = k (√2 - 1). Then k' < k and k' is also in K since k' √2 = 2 k - k √2, contradicting non-emptyness of K.

xurukefi 4y ago
That's an interesting proof, because I can easily follow it mechanically, but I have absolute no intuition for it.
- pfortuny 4y ago
  The minimum k is the denominator of the supposed irreducible fraction p/q=sqrt(2). He is stating that then there is a different irreducible fraction r/s=sqrt(2). This is because you would have p^2=2q^2 with p and q mutually prime, which is impossible. Instead of irreducible fractions with coprime numbers, he is doing the “dual” using the minimum possible value of the denominator.
deleted 4y ago
[deleted]
scotty79 4y ago
[deleted]
- pfortuny 4y ago
  Notice thay you know sqrt(2)<2 (this is easy), which does not happen in your case.
- deleted 4y ago
  [deleted]
phkahler 4y ago
Love a proof by infinite descent! But you do make the assumption that (√2 - 1) is positive and less than 1. Root 2 can be negative.