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<n. 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<b, forcing also p_a<p_b). 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}


Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: