Approximating a real number by a fraction from one side

735 Views Asked by At

Dirichlet's approximation theorem tells us that for any real number $\alpha$, we have a sequence of rational approximations of $\alpha$ that are good for how big their denominator is. More precisely: given an integer $N \ge 1$, there exists a rational number $\frac pq$ with $1 \le q \le N$ such that $$\left|\alpha - \frac pq\right| < \frac1{qN}.$$

(This error is less than $\frac1{q^2}$, and Roth's theorem tells us that for algebraic numbers, the exponent here is best possible.)

The absolute values tell us that the fraction $\frac pq$ is either going to be slightly smaller or slightly larger than $\alpha$. What if I want to specify which one it is? For example, suppose I want to find $\frac pq$ such that $$\frac pq < \alpha < \frac pq + \epsilon.$$ How small can I make $\epsilon$ (related to $q$, or possibly some extra parameter $N$ as above)?

I'm a bit worried when it comes to numbers such as Liouville's constant $L = \sum_{k=1}^\infty 10^{-k!}$, which has extremely good approximations (by truncating the series), but all from below; similarly, $1-L$ will have extremely good approximations, but all from above.

1

There are 1 best solutions below

0
On BEST ANSWER

To summarize the answers in the comments:

A more quantitative version of Dirichlet's approximation theorem is Hurwitz's theorem (Wikipedia link), which guarantees the existence of infinitely many approximations $\frac pq$ such that $$\left|\alpha - \frac{p}{q}\right| < \frac1{\sqrt 5\,q^2},$$ which is tight: for some $\alpha$, no better approximation exists. Moreover, these approximations can be found from truncating the continued fraction expansion of $\alpha$.

This, by itself, does not guarantee us which side the approximation is on. However, the continued fraction convergents $\frac{h_n}{k_n}$ satisfy $$\frac{h_{2n}}{k_{2n}} < \alpha < \frac{h_{2n+1}}{k_{2n+1}}$$ and also $$\left|\alpha - \frac{h_n}{k_n}\right| < \frac1{k_n k_{n+1}}.$$ (See, e.g., this link.) So the even convergents give us a close approximation from below: $$\frac{h_{2n}}{k_{2n}} < \alpha < \frac{h_{2n}}{k_{2n}} + \frac1{k_{2n}^2}.$$ Similarly, the odd convergents give us a close approximation from above.

Asymptotically, this is the best error we can hope for. We could hope to improve the constant on $\frac{1}{q^2}$ to make it closer to Hurwitz's theorem. However, experimentally, it seems like the constant of $1$ is actually best possible. If I take $\alpha$ to be the infinite continued fraction $$\alpha = 1 + \frac{1}{100 + \frac1{1 + \frac1{100 + \frac1{\ddots}}}} = \frac{5 + \sqrt{26}}{10}$$ then the continued fraction convergents give errors of $\approx \frac{0.98}{q^2}$ from one side and $\approx \frac{0.0098}{q^2}$ from the other: we pay for good approximations from below with bad approximations from above.

This is not a proof, because I haven't said anything about the quality of other, non-continued-fraction approximations to $\frac{5 + \sqrt{26}}{10}$. But it's very suggestive of what the answer might be, isn't it?