4 ms·

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 ap

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.
- AnimalMuppet 7y ago
  > Within 1/(10 q^2) is only sometimes possible. For any q?
  - btilly 7y ago
    For any q? Yes. The hardest real number to approximate with rationals is (1+sqrt(5))/2. Its approximations that come closest are of the form fib(n+1)/fib(n) where fib(n) is the n'th fibonacci number. The error converges to 1/(sqrt(5) fib(n)^2). None are within 1/(10 q^2). To learn more about this, read up on continued fractions.

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.

AnimalMuppet 7y ago
> Within 1/(10 q^2) is only sometimes possible. For any q?
- btilly 7y ago
  For any q? Yes. The hardest real number to approximate with rationals is (1+sqrt(5))/2. Its approximations that come closest are of the form fib(n+1)/fib(n) where fib(n) is the n'th fibonacci number. The error converges to 1/(sqrt(5) fib(n)^2). None are within 1/(10 q^2). To learn more about this, read up on continued fractions.