Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If $\alpha$ is an irrational, and I'm trying to judge the suitability of of a rational $p/q$ as its approximation by the error $\Delta = |\alpha - p/q|$. For a given denominator $q$, I am finding a $p$ for which the error $\Delta$ is minimized. Why is this error "certainly less than $1/2q$ " ?

share|cite|improve this question
    
If you use convergents of the continued fraction you get particularly good approximations. You can see en.wikipedia.org/wiki/Continued_fraction for information, especially the section "Best rational approximations". If you quit just before a large value in the continued fraction, it is even better. – Ross Millikan Aug 7 '11 at 1:44
    
@Ross that was precisely the motivation for this question. I encountered the problem when trying to prove the result. – kuch nahi Aug 7 '11 at 1:52
up vote 7 down vote accepted

Fix denominator $q$. If $\alpha -p/q$ is greater than $\frac{1}{2q}$ than $\frac{(p+1)}{q}$ is a better approximation.

[EDIT] Equality is impossible since $\alpha$ is assumed irrational.

share|cite|improve this answer
    
Excellent. Thanks! – kuch nahi Aug 7 '11 at 1:39

You can find approximations with error less than $\frac{1}{q^2}$ with continued fractions. The following can be proven with a simple pigeonhole proof.

Approximation Lemma: Let $x$ be any real number and $N$ be a positive integer. Then there are integers $p$ and $q$ with $0 < q \le N$ so that $|p - qx| < \frac{1}{N}$.

Proof: Break up the unit interval $[0,1)$ into $N$ equal subintervals. Notice which subinterval contains the residues $\pmod{1}$ of $kx$ for $0\le k\le N$. There are $N+1$ residues distributed among $N$ subintervals; thus, there must be at least one subinterval with at least two residues, $(k_1 x - j_1)$ and $(k_2 x - j_2)$. We may assume that $k_2 > k_1$. Let $q = k_2 - k_1$ and $p = j_2 - j_1$, then $0 < q \le N$ and, because both residues are in the same subinterval, $|p - qx| = |(k_1 x - j_1) - (k_2 x - j_2)| < \frac{1}{N}$. QED

share|cite|improve this answer
    
This is known as Dirichlet's Approximation Theorem. – robjohn Dec 22 '15 at 10:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.