5 ms·

Rational Math Catches Slippery Irrational Numbers

51 points by rfreytag 7y ago

msla 7y ago
I'm surprised this doesn't mention Cauchy sequences. It seems to get close, but never quite hit the mark. Anyway, a Cauchy sequence is one where the terms of the sequence eventually become arbitrarily close to one another; that is, you can pick an epsilon, an arbitrary small number, and after a certain point, the difference between elements of the sequence is less than epsilon. The intuition is an infinite list of rational numbers which, when plotted, look like a ping-pong ball endlessly bouncing around a given point, getting closer and closer... to what? Well, it depends on the precise sequence, but that end-point might not exist in the rationals. If it's a_n/2 + 1/a_n, it converges to the square root of 2, but we've known for a long time that that's irrational, so the ping-pong ball bounces forever, from one rational to another, getting closer and closer to a spot that doesn't exist... What if it did exist? What if all those spots existed? Well, if you have that, the set is now Cauchy-complete, also known as a complete metric space; if you have that, plus the field axioms (so addition, subtraction, multiplication, and division all work as you expect), plus ordering (so greater-than and less-than always work), plus the Archimedean axiom (no infinitesimal or infinite numbers), you have the real numbers. The reals are the unique Cauchy-complete Archimedian ordered field; every other set with those properties is isomorphic to the reals.
- heyitsguay 7y ago
  Great layman explanation! I'd suggest one extremely minor modification to your ping-pong metaphor: Cauchy sequences don't necessarily have to bounce back and forth between being smaller than your target point and being larger than your target point. They can always increase, or always decrease, too. To give a concrete example, one possible Cauchy sequence for the square root of 2 would just be {1, 1.4, 1.41, 1.414, 1.4142, 1.41421, ...}
- addcninblue 7y ago
  I'd also like to add one more clarification: Cauchy sequences require _any two_ elements after N (the "certain point" mentioned above) to be within epsilon of each other. Why? I won't explain it fully, but hopefully a counterexample can convince you so: Take the common harmonic series (a_n = 1+1/2+1/3+...+1/n) Each successive element differs from the previous by 1/n. Therefore, informally we can see that their pairwise differences gets arbitrarily small. However, this sequence is _unbounded_: The infinite sum of the harmonic series tends to infinity. It therefore cannot be Cauchy. (Cauchy "bounces around a fixed point")
  - msla 7y ago
    That is a very good point.
- steerablesafe 7y ago
  > The reals are the unique Cauchy-complete Archimedian ordered field; every other set with those properties is isomorphic to the reals. One can also arrive at the reals by constructing from the rationals through completion. https://en.wikipedia.org/wiki/Complete_metric_space#Completion https://en.wikipedia.org/wiki/Complete_metric_space#Completi... Edit: There is a nice wiki page about the different approaches https://en.wikipedia.org/wiki/Construction_of_the_real_numbers https://en.wikipedia.org/wiki/Construction_of_the_real_numbe...
pierrebai 7y ago
There must be a subtlety I don't understand. To cover the number line at precision of at least 10^n, just cover it with intervals of 1/10^n, surely? IOW, to approximate an irrational number to 10 decimal places... use 10 decimal places? Geen, use 11 decimal places just to be double-sure and not have to worry. What am I missing?
- zodiac 7y ago
  The "aim" is to cover an interval with "simple" rationals (where a rational with a smaller denominator is defined as simpler)
- mauricioc 7y ago
  Sure, using a denominator of 10^n gives 1/10^n precision, which is pretty good. And this is fine for applications! However, defining goodness in terms of absolute error makes the resulting problem of "how good an approximation can we get?" become trivial, because the answer is "arbitrarily good, always". A different measure of goodness takes into consideration not only the distance between the real number and its rational approximation, but how big the denominator of the approximation is. Note that, in the scheme you describe, a denominator of q guarantees an error of 1/q. But if you are allowed to choose both the numerator and the denominator of the rational approximation, then perhaps you can make the denominator smaller? It turns out you can! Dirichlet showed that for every irrational alpha there are infinitely many "good approximations" of the form p/q where |alpha - p/q| < 1/q^2. It turns out the golden ratio shows that you can't do better than 1/(sqrt(5) * q^2) if you want the result to hold for every irrational number. This leads to the problem of identifying "interesting" sets of irrational numbers that allow approximations substantially better than Dirichlet's bound (this is the problem of Diophantine approximation [0]). Klaus Roth got his Fields Medal primarily for a result in this area [1]. [0] https://en.wikipedia.org/wiki/Diophantine_approximation https://en.wikipedia.org/wiki/Diophantine_approximation [1] https://en.wikipedia.org/wiki/Roth%27s_theorem https://en.wikipedia.org/wiki/Roth%27s_theorem
- btilly 7y ago
  The question isn't how to approximate a given number to desired accuracy. It is whether we should be able to approximate it to desired accuracy relative to the denominator. Getting an approximation p/q of x within 1/q is easy. Getting it within 1/q^2 takes work. Within 1/(10 q^2) is only sometimes possible.
deleted 7y ago
[deleted]
btilly 7y ago
I find that quanta entertains but does not inform. See https://en.wikipedia.org/wiki/Duffin%E2%80%93Schaeffer_conjecture https://en.wikipedia.org/wiki/Duffin%E2%80%93Schaeffer_conje... for the conjecture in question. Basically it is about under what measures of "a surprisingly good approximation" we would expect to find infinitely many surprisingly good approximations for any random real we pick. Where the definition of a surprisingly good approximation is "within a bound dependent on the denominator". Obviously you can get a better approximation by simply taking a larger denominator. The question is whether you get a good approximation relative to the size of the denominator. We probably aren't surprised to find that with a denominator of size q we can get within 1/q of an arbitrary rational. But we likely are surprised to find that we can get within 1/(100 q^2). In fact there are no approximations that good of the golden ratio (1 + sqrt(5))/2. But it is unusual, almost all real numbers can be approximated that well. But 355/113 is such a good approximation of pi. The conjecture is about the existence, not how to find them. (In practice continued fractions are usually the right way to do it.)

51 points by rfreytag 7y ago

msla 7y ago

I'm surprised this doesn't mention Cauchy sequences. It seems to get close, but never quite hit the mark. Anyway, a Cauchy sequence is one where the terms of the sequence eventually become arbitrarily close to one another; that is, you can pick an epsilon, an arbitrary small number, and after a certain point, the difference between elements of the sequence is less than epsilon. The intuition is an infinite list of rational numbers which, when plotted, look like a ping-pong ball endlessly bouncing around a given point, getting closer and closer... to what? Well, it depends on the precise sequence, but that end-point might not exist in the rationals. If it's a_n/2 + 1/a_n, it converges to the square root of 2, but we've known for a long time that that's irrational, so the ping-pong ball bounces forever, from one rational to another, getting closer and closer to a spot that doesn't exist... What if it did exist? What if all those spots existed? Well, if you have that, the set is now Cauchy-complete, also known as a complete metric space; if you have that, plus the field axioms (so addition, subtraction, multiplication, and division all work as you expect), plus ordering (so greater-than and less-than always work), plus the Archimedean axiom (no infinitesimal or infinite numbers), you have the real numbers. The reals are the unique Cauchy-complete Archimedian ordered field; every other set with those properties is isomorphic to the reals.

heyitsguay 7y ago
Great layman explanation! I'd suggest one extremely minor modification to your ping-pong metaphor: Cauchy sequences don't necessarily have to bounce back and forth between being smaller than your target point and being larger than your target point. They can always increase, or always decrease, too. To give a concrete example, one possible Cauchy sequence for the square root of 2 would just be {1, 1.4, 1.41, 1.414, 1.4142, 1.41421, ...}
addcninblue 7y ago
I'd also like to add one more clarification: Cauchy sequences require _any two_ elements after N (the "certain point" mentioned above) to be within epsilon of each other. Why? I won't explain it fully, but hopefully a counterexample can convince you so: Take the common harmonic series (a_n = 1+1/2+1/3+...+1/n) Each successive element differs from the previous by 1/n. Therefore, informally we can see that their pairwise differences gets arbitrarily small. However, this sequence is _unbounded_: The infinite sum of the harmonic series tends to infinity. It therefore cannot be Cauchy. (Cauchy "bounces around a fixed point")
- msla 7y ago
  That is a very good point.
steerablesafe 7y ago
> The reals are the unique Cauchy-complete Archimedian ordered field; every other set with those properties is isomorphic to the reals. One can also arrive at the reals by constructing from the rationals through completion. https://en.wikipedia.org/wiki/Complete_metric_space#Completion https://en.wikipedia.org/wiki/Complete_metric_space#Completi... Edit: There is a nice wiki page about the different approaches https://en.wikipedia.org/wiki/Construction_of_the_real_numbers https://en.wikipedia.org/wiki/Construction_of_the_real_numbe...

pierrebai 7y ago

There must be a subtlety I don't understand. To cover the number line at precision of at least 10^n, just cover it with intervals of 1/10^n, surely? IOW, to approximate an irrational number to 10 decimal places... use 10 decimal places? Geen, use 11 decimal places just to be double-sure and not have to worry. What am I missing?

zodiac 7y ago
The "aim" is to cover an interval with "simple" rationals (where a rational with a smaller denominator is defined as simpler)
mauricioc 7y ago
Sure, using a denominator of 10^n gives 1/10^n precision, which is pretty good. And this is fine for applications! However, defining goodness in terms of absolute error makes the resulting problem of "how good an approximation can we get?" become trivial, because the answer is "arbitrarily good, always". A different measure of goodness takes into consideration not only the distance between the real number and its rational approximation, but how big the denominator of the approximation is. Note that, in the scheme you describe, a denominator of q guarantees an error of 1/q. But if you are allowed to choose both the numerator and the denominator of the rational approximation, then perhaps you can make the denominator smaller? It turns out you can! Dirichlet showed that for every irrational alpha there are infinitely many "good approximations" of the form p/q where |alpha - p/q| < 1/q^2. It turns out the golden ratio shows that you can't do better than 1/(sqrt(5) * q^2) if you want the result to hold for every irrational number. This leads to the problem of identifying "interesting" sets of irrational numbers that allow approximations substantially better than Dirichlet's bound (this is the problem of Diophantine approximation [0]). Klaus Roth got his Fields Medal primarily for a result in this area [1]. [0] https://en.wikipedia.org/wiki/Diophantine_approximation https://en.wikipedia.org/wiki/Diophantine_approximation [1] https://en.wikipedia.org/wiki/Roth%27s_theorem https://en.wikipedia.org/wiki/Roth%27s_theorem
btilly 7y ago
The question isn't how to approximate a given number to desired accuracy. It is whether we should be able to approximate it to desired accuracy relative to the denominator. Getting an approximation p/q of x within 1/q is easy. Getting it within 1/q^2 takes work. Within 1/(10 q^2) is only sometimes possible.

deleted 7y ago

[deleted]

btilly 7y ago

I find that quanta entertains but does not inform. See https://en.wikipedia.org/wiki/Duffin%E2%80%93Schaeffer_conjecture https://en.wikipedia.org/wiki/Duffin%E2%80%93Schaeffer_conje... for the conjecture in question. Basically it is about under what measures of "a surprisingly good approximation" we would expect to find infinitely many surprisingly good approximations for any random real we pick. Where the definition of a surprisingly good approximation is "within a bound dependent on the denominator". Obviously you can get a better approximation by simply taking a larger denominator. The question is whether you get a good approximation relative to the size of the denominator. We probably aren't surprised to find that with a denominator of size q we can get within 1/q of an arbitrary rational. But we likely are surprised to find that we can get within 1/(100 q^2). In fact there are no approximations that good of the golden ratio (1 + sqrt(5))/2. But it is unusual, almost all real numbers can be approximated that well. But 355/113 is such a good approximation of pi. The conjecture is about the existence, not how to find them. (In practice continued fractions are usually the right way to do it.)