6 ms·

Math Bite: Irrationality of √m (1999)

88 points by luisb 11y ago

vog 11y ago
That proof is really great! It's always nice to see alternatives to well-known proofs. This demonstrates that you can always tackle problems from different angles. However, I slightly disagree with the introduction of the proof: | The really interesting thing about this proof is that it doesn't use divisibility, just mathematical induction in its "Z is well-ordered" form. That's quite a bold statement. It would mean that this proof should generalize to other well-ordered sets that do not provide any notion of divisibility. However, I don't see that. (Does anyone else see how this proof could work on such a generalized setting?) Instead, it seems that this proof introduces the concept of "divisibility" through the backdoor, by calculating with fractions and making use of the basic fraction laws, which are based on divisibility. In particular, the equation 1 / (sqrt(m) - n) = (sqrt(m) + n) / (m - n^2) makes use of the fact that you can extend and cancel fractions. Moreover, these fractions are not even fractions in Z, but in R, or at least in Z[sqrt(m)]. So there's still a lot of specialized structure involved in this proof. Nevertheless, great proof!
- deleted 11y ago
  [deleted]
- jfarmer 11y ago
  By "doesn't use divisibility" I assume the author means that the point of contradiction doesn't rest on the "divisibility properties" of the integer, not that division is never used. In particular, this proof doesn't rely on the fundamental theorem of arithmetic.
  - vog 11y ago
    > I assume the author means that the point of contradiction doesn't rest on the "divisibility properties" of the integer I see what the author meant by that. I just think it was stated in a slightly exaggerated way. The "divisibility properties" of the integers are still used. That part has just has been moved to another corner of the proof, by transforming fractional equations. One of the comments in the article is quite interesting here: | Theodor Estermann proved the irrationality of 2√ without relying on the prime factorization of m. I believe that this statement is more correct. The "traditional" proof uses not just divisibility, but prime factorization, which is quite a strong property. And that is something the alternative proof doesn't make use of. Maybe the introduction should have been stated that way.
    - jameshart 11y ago
      Indeed - I think the claim that alpha can be expressed as p/q with some 'lowest q' seems to rest on divisibility properties.
      - jfarmer 11y ago
        No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element. And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle holds (it's equivalent to the axiom schema of induction). [1]: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic
    - jfarmer 11y ago
      As near as I can tell, this proof would work in any well-ordered integral domain D where D's field of fractions would the role of the rationals. The analogue of the standard proof would require that D also be a unique factorization domain (or maybe the slightly weaker condition that any two elements have a GCD). It might be the case that all these properties together "force" D to be a UFD or that the author snuck another property of the integers in there, but I've only taken a cursory look.
- contravariant 11y ago
  >> The really interesting thing about this proof is that it doesn't use divisibility, just mathematical induction in its "Z is well-ordered" form. >That's quite a bold statement. It would mean that this proof should generalize to other well-ordered sets that do not provide any notion of divisibility. It doesn't, for the somewhat obvious reason that divisibility makes sense in any set that has a notion of 'multiplication'. The proof itself doesn't use any statements of the form 'x is divisible by y' though, not even implicitly as far as I can tell. Even fraction laws don't really count as 'using' divisibility. Since fractions can be defined in a way that doesn't directly use divisibility (although the concepts are obviously related). Being well ordered is a far more restrictive property than 'having a notion of divisibility'. > Moreover, these fractions are not even fractions in Z, but in R, or at least in Z[sqrt(m)]. So there's still a lot of specialized structure involved in this proof. According to the proof the fractions are in Q not R.
  - vog 11y ago
    > According to the proof the fractions are in Q not R. That's a circular argument. During the proof this is not given, only after the proof.
    - contravariant 11y ago
      During the proof it is assumed, this assumption leads to a contradiction, hence the assumption 'sqrt(m) is in Q' is false. The reason this is not a circular argument is that they don't assume the thing they're trying to prove, but rather it's negation.
      - vog 11y ago
        You are right. My bad.
2sk21 11y ago
Discovering wonderful sites like this is why I read Hacker News!
- avian 11y ago
  Yes, such wonderful sites that must put annoying bouncing "Click here to see more" and "Join our newsletter" things around everything. By the way, this particular note appears to be taken from "Biscuits of Number Theory". Compare with this scan from Google Books: https://books.google.si/books?id=_g5TvMCJQB4C&pg=PA109&lpg=PA109&dq=harley+flanders+irrationality&source=bl&ots=ShlKfjMAQg&sig=jBwurdoANm2e5cCgo-jn0Fa0DGg&hl=sl&sa=X&ved=0ahUKEwiq2Nys5PHJAhXFFSwKHWr2C-YQ6AEIJjAA#v=onepage&q=harley%20flanders%20irrationality&f=false https://books.google.si/books?id=_g5TvMCJQB4C&pg=PA109&lpg=P...
tempodox 11y ago
The print is too small and the document cannot be scaled, only pixellated. This makes it quite unusable for me. Too bad, math deserves better.
- iand 11y ago
  It's pixelated because the paper is a scan of a 17 year old paper. The Fermat's Library site is designed to allow people to annotate and comment on old classic papers, most of them from before digitisation of journals.
deleted 11y ago
[deleted]
jamesfisher 11y ago
I don't understand. The end of the proof says r/p is a fraction, presumably because r must be an integer. But why must r be an integer? There seems to be an implicit assumption that m is an integer, but the explicit assumptions only give the much weaker statement that "m is not a perfect square".
- vog 11y ago
  > why must r be an integer? r is a shorthand for (m-n^2)q-2np, which is an integer because m,n,p,q are all integers. > There seems to be an implicit assumption that m is an integer, but the explicit assumptions only give the much weaker statement that "m is not a perfect square". Yes, it would have been more explicit to say "m is an integer that is not a perfect square." On the other hand, this is pretty clear from the context. This is like looking at a computer program and saying "foo has no side-effect" without stating that "foo is a function".
JerTheRipper 11y ago
I'm trying to work this out in my head, but I believe that this holds if m is a rational such that its numerator and denominator are not both perfect squares (e.g., √(2/3) is irrational but √(4/9) is rational). Am I wrong?
- tribe 11y ago
  When this proof has been presented to me in the past, I believe we assume that m is a positive integer. This is mentioned in one of the comments, but I agree that it should be more clear in statement of the theorem.
- plookn 11y ago
  Good point! The only part we need to check is the base case. Since the result holds for n=0, I'd say you're right.
brlewis 11y ago
> We may assume that q is as small as possible (Estermann's key idea) Making the denominator as small as possible uses divisibility.
- fluxion 11y ago
  Not necessarily. Strictly mathematically a (non-negative) fraction q/p is just the equivalence class of all non-negative integer pairs (s, t), t != 0, such that qt = sp As such we may make q as small as possible by finding a representative in the equivalence class where the numerator is smallest (using the well ordering principle of the of the natural numbers). You can identify this pair uniquely (when the fraction is not 0) by using divisibility but that isn't required here.
  - brlewis 11y ago
    By the same reasoning, divisibility does not use divisibility. Instead of asking if x is divisible by y you create a set of all products of the form ny where n is an integer, then check to see if x is a member of that set. I don't buy it. qt = sp looks too much like x = ny to me.
- jfarmer 11y ago
  No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element. And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle holds (it's equivalent to the axiom schema of induction). [1]: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic
  - brlewis 11y ago
    alpha = p/q where p and q are positive integers. It's finding the set of all possible q that uses divisibility, not finding the least member of that set.

88 points by luisb 11y ago

vog 11y ago

That proof is really great! It's always nice to see alternatives to well-known proofs. This demonstrates that you can always tackle problems from different angles. However, I slightly disagree with the introduction of the proof: | The really interesting thing about this proof is that it doesn't use divisibility, just mathematical induction in its "Z is well-ordered" form. That's quite a bold statement. It would mean that this proof should generalize to other well-ordered sets that do not provide any notion of divisibility. However, I don't see that. (Does anyone else see how this proof could work on such a generalized setting?) Instead, it seems that this proof introduces the concept of "divisibility" through the backdoor, by calculating with fractions and making use of the basic fraction laws, which are based on divisibility. In particular, the equation 1 / (sqrt(m) - n) = (sqrt(m) + n) / (m - n^2) makes use of the fact that you can extend and cancel fractions. Moreover, these fractions are not even fractions in Z, but in R, or at least in Z[sqrt(m)]. So there's still a lot of specialized structure involved in this proof. Nevertheless, great proof!

deleted 11y ago
[deleted]
jfarmer 11y ago
By "doesn't use divisibility" I assume the author means that the point of contradiction doesn't rest on the "divisibility properties" of the integer, not that division is never used. In particular, this proof doesn't rely on the fundamental theorem of arithmetic.
- vog 11y ago
  > I assume the author means that the point of contradiction doesn't rest on the "divisibility properties" of the integer I see what the author meant by that. I just think it was stated in a slightly exaggerated way. The "divisibility properties" of the integers are still used. That part has just has been moved to another corner of the proof, by transforming fractional equations. One of the comments in the article is quite interesting here: | Theodor Estermann proved the irrationality of 2√ without relying on the prime factorization of m. I believe that this statement is more correct. The "traditional" proof uses not just divisibility, but prime factorization, which is quite a strong property. And that is something the alternative proof doesn't make use of. Maybe the introduction should have been stated that way.
  - jameshart 11y ago
    Indeed - I think the claim that alpha can be expressed as p/q with some 'lowest q' seems to rest on divisibility properties.
    - jfarmer 11y ago
      No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element. And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle holds (it's equivalent to the axiom schema of induction). [1]: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic
  - jfarmer 11y ago
    As near as I can tell, this proof would work in any well-ordered integral domain D where D's field of fractions would the role of the rationals. The analogue of the standard proof would require that D also be a unique factorization domain (or maybe the slightly weaker condition that any two elements have a GCD). It might be the case that all these properties together "force" D to be a UFD or that the author snuck another property of the integers in there, but I've only taken a cursory look.
contravariant 11y ago
>> The really interesting thing about this proof is that it doesn't use divisibility, just mathematical induction in its "Z is well-ordered" form. >That's quite a bold statement. It would mean that this proof should generalize to other well-ordered sets that do not provide any notion of divisibility. It doesn't, for the somewhat obvious reason that divisibility makes sense in any set that has a notion of 'multiplication'. The proof itself doesn't use any statements of the form 'x is divisible by y' though, not even implicitly as far as I can tell. Even fraction laws don't really count as 'using' divisibility. Since fractions can be defined in a way that doesn't directly use divisibility (although the concepts are obviously related). Being well ordered is a far more restrictive property than 'having a notion of divisibility'. > Moreover, these fractions are not even fractions in Z, but in R, or at least in Z[sqrt(m)]. So there's still a lot of specialized structure involved in this proof. According to the proof the fractions are in Q not R.
- vog 11y ago
  > According to the proof the fractions are in Q not R. That's a circular argument. During the proof this is not given, only after the proof.
  - contravariant 11y ago
    During the proof it is assumed, this assumption leads to a contradiction, hence the assumption 'sqrt(m) is in Q' is false. The reason this is not a circular argument is that they don't assume the thing they're trying to prove, but rather it's negation.
    - vog 11y ago
      You are right. My bad.

2sk21 11y ago

Discovering wonderful sites like this is why I read Hacker News!

avian 11y ago
Yes, such wonderful sites that must put annoying bouncing "Click here to see more" and "Join our newsletter" things around everything. By the way, this particular note appears to be taken from "Biscuits of Number Theory". Compare with this scan from Google Books: https://books.google.si/books?id=_g5TvMCJQB4C&pg=PA109&lpg=PA109&dq=harley+flanders+irrationality&source=bl&ots=ShlKfjMAQg&sig=jBwurdoANm2e5cCgo-jn0Fa0DGg&hl=sl&sa=X&ved=0ahUKEwiq2Nys5PHJAhXFFSwKHWr2C-YQ6AEIJjAA#v=onepage&q=harley%20flanders%20irrationality&f=false https://books.google.si/books?id=_g5TvMCJQB4C&pg=PA109&lpg=P...

tempodox 11y ago

The print is too small and the document cannot be scaled, only pixellated. This makes it quite unusable for me. Too bad, math deserves better.

iand 11y ago
It's pixelated because the paper is a scan of a 17 year old paper. The Fermat's Library site is designed to allow people to annotate and comment on old classic papers, most of them from before digitisation of journals.

deleted 11y ago

[deleted]

jamesfisher 11y ago

I don't understand. The end of the proof says r/p is a fraction, presumably because r must be an integer. But why must r be an integer? There seems to be an implicit assumption that m is an integer, but the explicit assumptions only give the much weaker statement that "m is not a perfect square".

vog 11y ago
> why must r be an integer? r is a shorthand for (m-n^2)q-2np, which is an integer because m,n,p,q are all integers. > There seems to be an implicit assumption that m is an integer, but the explicit assumptions only give the much weaker statement that "m is not a perfect square". Yes, it would have been more explicit to say "m is an integer that is not a perfect square." On the other hand, this is pretty clear from the context. This is like looking at a computer program and saying "foo has no side-effect" without stating that "foo is a function".

JerTheRipper 11y ago

I'm trying to work this out in my head, but I believe that this holds if m is a rational such that its numerator and denominator are not both perfect squares (e.g., √(2/3) is irrational but √(4/9) is rational). Am I wrong?

tribe 11y ago
When this proof has been presented to me in the past, I believe we assume that m is a positive integer. This is mentioned in one of the comments, but I agree that it should be more clear in statement of the theorem.
plookn 11y ago
Good point! The only part we need to check is the base case. Since the result holds for n=0, I'd say you're right.

brlewis 11y ago

> We may assume that q is as small as possible (Estermann's key idea) Making the denominator as small as possible uses divisibility.

fluxion 11y ago
Not necessarily. Strictly mathematically a (non-negative) fraction q/p is just the equivalence class of all non-negative integer pairs (s, t), t != 0, such that qt = sp As such we may make q as small as possible by finding a representative in the equivalence class where the numerator is smallest (using the well ordering principle of the of the natural numbers). You can identify this pair uniquely (when the fraction is not 0) by using divisibility but that isn't required here.
- brlewis 11y ago
  By the same reasoning, divisibility does not use divisibility. Instead of asking if x is divisible by y you create a set of all products of the form ny where n is an integer, then check to see if x is a member of that set. I don't buy it. qt = sp looks too much like x = ny to me.
jfarmer 11y ago
No, it follows directly from the fact that the positive integers are well-ordered, i.e., any set of positive integers has a least element. And in case one is tempted to think that well-ordering and divisibility are somehow equivalent, consider Presburger arithmetic[1]. It's not even possible to define a general notion of divisibility or primality in that context, but I'm almost positive the well-ordering principle holds (it's equivalent to the axiom schema of induction). [1]: https://en.wikipedia.org/wiki/Presburger_arithmetic https://en.wikipedia.org/wiki/Presburger_arithmetic
- brlewis 11y ago
  alpha = p/q where p and q are positive integers. It's finding the set of all possible q that uses divisibility, not finding the least member of that set.