## Rational Approximations

Suppose $x$ is an irrational in the interval $(0,1)$, and fix a positive integer $n$. Let’s see what I can say about rational approximations to $x$ whose denominator is no bigger than $n$.

First of all, $x$ lies in one of the intervals $[j/n,(j+1)/n]$, where $0\leq j. Since $x$ is irrational, it won’t be an endpoint of such an interval, nor will it be the midpoint. Which is to say, it is closer to one end than the other. More explicitly, we can say that $|x-j/n|<1/(2n)$ for some $0\leq j\leq n$.

Instead of requiring the denominator of a rational approximation to actually be $n$, what if we just ask that it be no bigger than $n$? Then we’re asking how well rationals in the $n$-th Farey sequence, $F_n$, approximate $x$.

Instead of thinking about $|x-p/q|$, let’s multiply everything by $q$, and so look at $|qx-p|$ (we’ll divide by that $q$ again soon enough). So now we’re not asking about rational approximations, as such, but asking about pairs of integers, $p$ and $q$ with $0\leq p\leq q\leq n$, so that $qx$ is “pretty close” to the integer $p$.

Let’s re-phrase once more. Consider all of the multiples $x,2x,3x,\ldots,nx$ of $x$. All of these are irrationals, but could now be bigger than 1 (our original $x$ was less than 1). I don’t want to think about things bigger than 1, so let me trim all of these multiples $qx$ down to just the “fractional part”. Which is to say, I’ll now think about all of the values $qx-\lfloor qx\rfloor$ (the “floor” notation picks out the “greatest integer less than”), which are all irrationals in the interval $(0,1)$. Now for each $q$ I have an integer $\lfloor qx\rfloor$, and let me denote this integer by $p_q$. You might note that $p_q$ is always less than $n$.

So now I am thinking about the $n$ irrational values $qx-p_q$ in the interval $(0,1)$. I’ll think about them in comparison to the rational points $0,1/n,2/n,\ldots,1$, like I did before. Following Rademacher (as most of my content has been and will be), we distinguish two cases.

1. Suppose some $qx-p_q$ falls in the interval $(0,1/n)$. Then $|qx-p_q|< 1/n$, and so $|x-p_q/q|<1/(qn)\leq 1/q^2$ (since $q\leq n$).
2. If $(0,1/n)$ is free of our points, then by the pidgeon-hole principle, some interval $(j/n,(j+1)/n)$ contains two values, say $ax-p_a$ and $bx-p_b$ (arrange notation so that $a, forcing also $p_a). Then $|(bx-p_b)-(ax-p_a)|< 1/n$, which we re-arrange to say that $|(b-a)x-(p_b-p_a)|< 1/n$. Letting $q=b-a$ and $p=p_b-p_a$, we have $|qx-p|< 1/n$, which we again re-write, as in case (1), to say that $|x-p/q|< 1/q^2$.

We have, therefore, improved the “order” of our approximation. To begin with, we said that rational approximations could be found with $|x-j/n|< 1/(2n)$. I think of this as a “order 1” approximation, since the denominator of the error is a linear function of the denominator of the rational approximation. We have now improved this so that $|x-p/q|< 1/q^2$, which I would therefore call an “order 2” approximation. If you are a little more careful with your inequalities, you can improve the bound to $|x-p/q|< 1/(2q^2)$ (an error that I think I’ll probably end up mentioning again tomorrow), basically for the same reason there is a coefficient of 2 in the order 1 approximation, I guess.

I should probably be a little (a lot) more careful in what I am saying with the above. I chose an irrational $x$ and an integer $n$, and said that an “order 2” rational approximation could be found. The stronger claim is that, in fact, infinitely many order 2 rational approximations can be found, if you let $n$ increase. Suppose your first order 2 approximation gives you $|x-p/q|< 1/q^2$, when you have bounded the denominator by $n$. Find a new $N$ so that $1/N< 1/q^2$. Then go through the process above, using $N$ as the new bound on the denominator. When you find $|x-p'/q'|< 1/(q'N)\leq 1/(q')^2$ with that process, then you’ve found a new rational approximation (since it is closer to $x$ then $p/q$ was) that is still order 2 (since that’s what the process does for you).

So, can order 2 be improved on? Can you find order 3, or higher? It turns out, “no”, in general (and the golden ratio is an example). You can improve the coefficient of 2 in the order 2 approximation to $\sqrt{5}$, but that’s apparently the best you can do, in general. There’s more than can be said along these lines. The Roth-Liouville irrationality measure might be fun to talk about (it earned Roth a Fields medal, so it must be ok), as would continued fractions. I’m not sure how much these are related to my stated goal of understanding the link between Farey sequences and the Riemann hypothesis, so for now, perhaps I’ll leave them alone.

For some reason, I thought it might be fun to make a visualization about rational approximations using $F_5$. Here is a picture of the rationals in $F_5$, as a subset of $[0,1]$:

$\begin{picture}(200,10) \put(0,0){\line(1,0){200}}\multiput(0,0)(40,0){6}{\circle*{3}}\multiput(50,0)(50,0){3}{\circle*{3}}\multiput(67,0)(67,0){2}{\circle*{3}}\end{picture}$

Here’s a graph of the function taking $x$ to “the rational in $F_5$ closest to $x$“:

$\begin{picture}(200,200) \put(0,0){\line(1,0){200}}\put(0,0){\line(0,1){200}}\multiput(0,0)(40,0){6}{\circle*{3}}\multiput(50,0)(50,0){3}{\circle*{3}}\multiput(67,0)(67,0){2}{\circle*{3}}\put(20,40){\line(1,0){25}}\put(45,50){\line(1,0){13}}\put(58,67){\line(1,0){16}}\put(74,80){\line(1,0){16}}\put(90,100){\line(1,0){20}}\put(110,120){\line(1,0){16}}\put(126,133){\line(1,0){16}}\put(142,150){\line(1,0){13}}\put(155,160){\line(1,0){25}}\put(180,200){\line(1,0){20}}\end{picture}$