rational approximation | ∑idiot's Blog

Posts Tagged ‘rational approximation’

Rational Approximations

November 3, 2009

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.

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$ ).
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:farey, mablowrimo, rational approximation
Posted in Uncategorized | Leave a Comment »

Hardy and Wright, Chapter 10

May 29, 2009

We decided to split the reading of chapter 10 into two weeks (chapter 9 here, in case you missed it). It’s a longish chapter, and I really like continued fractions (though I’m not particularly sure why, they’re just fun) and some of the other readers thought it might be worth it to spend more time reading it carefully.

Our first meeting covered the first few sections, which only involved basic definitions, and the theorem that every real number has an essentially unique continued fraction expansion, and the expansion is finite if and only if the number is rational. Eric stated that he was unimpressed so far, and didn’t see what I was so fascinated by. None of us seemed to have any questions about the reading, so I gave a glimpse of things to come (relation of periodic continued fractions to quadratics, and rational approximations). I also mentioned that there are some interesting tie-ins to the “modular group” ( $SL_2(\mathbf{Z})$ ), Farey sequences, and Ford circles (which have come up before). Eric has been reading about hypergeometric series, and said there are some interesting formulas there related to continued fractions. He also asked if there was some relation to surreal numbers, because continued fractions approximate numbers from the left and right, alternatingly.

We picked up, the second week, in section 10.10 “A lemma”, defining an equivalence relation on reals. The relation works out to be that two numbers are equivalent if the tail of their continued fractions are the same. Chris corrected a misinterpretation Eric brought up, about canonical representatives of equivalence classes. I had wondered if the equivalence meant that, in terms of periodic continued fractions representing “quadratic” numbers, two numbers $(a_1+\sqrt{b})/d_1$ and $(a_2+\sqrt{b})/d_2$ would always be equivalent. In fact, I thought I had decided they were. But an example in the book shows that this is not the case ( $\sqrt{5}=[2,\dot{4}]$ while $(\sqrt{5}+1)/2=[\dot{1}]$ , dots representing the repeating part). Eric pointed out that two points were related if there are in the orbit of the modular group acting on $\mathbb{R}$ as a subset of $\mathbb{C}$ , acting as linear fractional transformations.

We spent a little while talking about periodic continued fractions, how the two directions of the proof that they are equivalent to “quadratics” go. I think the proof that any quadratic has a periodic continued fraction is fascinating. It gives no indication how long the period will be, or when it will start.

Next I mentioned that there’s a convenient algorithm for finding the continued fraction for a “quadratic surd”, and that I intend to post some python code here implementing it (and other fun functions for playing with continued fractions). While it’s essentially the normal algorithm, taking floors and then reciprocals, there’s some convenience in having quadratics around, because you can “rationalize the numerator” and sorts of things. Not mentioned in the text, but stated at both Wikipedia and Mathworld (links below), is that Lagrange showed that the continued fraction for $\sqrt{D}$ has a period smaller than $2D$ , that the period begins after a single non-repeating term, and that the last term in the period is twice $a_0$ (the first term of the continued fraction). All of these things are true of the examples given in the text. And, while finding links… holy crap! the repeating part, besides the last numeral, is palindromic! Is there no end to the fascination!?

I’ll go ahead and just direct you to the Wikipedia page on (periodic) continued fractions, and similarly the Mathworld page (periodic) continued fractions. All (and undoubtedly many others) make for fascinating reading.

Our next main focus was on approximation by convergents. Chris pointed out how remarkable the final theorem is, that any time a fraction is sufficiently close to a number (in terms of it’s denominator), it is automatically a convergent. I mentioned one thing I read about in Rademacher’s “Higher Mathematics from an Elementary Point of View” (which I love), which was that the existence of infinitely many $p/q$ such that $|p/q-x|<\frac{1}{2q^2}$ (corollary of theorem 183) can be interpreted as saying that a vertical line at $x$ passes through infinitely many Ford circles.

I then tried to explain the difference between Theorems 181 and Theorems 182, and point out that there are two reasonable definitions of “closest rational approximation”. I had read about these in Khinchin’s “Continued Fractions” (which I also love). I bumbled it a bit, but believe I was saying true things throughout. Basically, the story goes… convergents are best rational approximations in the stronger sense (thm 182), and mediants of successive convergents are best rational approximations in the weaker sense (thm 181). In fact, choose an irrational (for convenience) $x$ , and let $\square$ denote the operation “mediant”. For any $n$ , define $m_{n,1}=(p_n/q_n)\square (p_{n+1}/q_{n+1})$ , and then iteratively $m_{n,k}=m_{n,k-1}\square (p_{n+1}/q_{n+1})$ . The last of these mediants that is on the same side of $x$ as $p_n/q_n$ will be $p_{n+2}/q_{n+2}$ . Continued fractions rock.

It’s really best to think about these lemmas with an actual continued fraction example. I, personally, used $61/45=[1;2,1,4,3]$ , and looked at the mediants $m_{1,k}$ , between the first and second convergent.

We finished with me trying to explain something that I thought was quite surprising. Let $f_k(x)=n_k(x)/k$ denote the closest rational to $x$ , with denominator $k$ (let’s not require the fraction in reduced terms). I was quite surprised, honestly (and convinced Eric he should be too), that for a chosen $x$ , the sequence of such rationals will not be successively better approximations to $x$ . Having had the chance to go through an example with Eric, and then a few hours to mull it over, I’ve since realized this it not particularly surprising at all. Suppose $x$ lies in $[1/4,1/3]$ . Half of these $x$ will be better approximated by 1/3 than 1/4.

So, anyway, I guess that’s all I have to say about continued fractions by now. Perhaps Eric will show us sometime about fun relationships between hypergeometric series and continued fractions. If you haven’t already stopped reading this post to go find all sorts of other interesting things to read about continued fractions, either online or in Rademacher’s or Khinchin’s books, you can now.

Tags:hardy and wright, number theory, farey sequence, ford circle, continued fraction, modular group, lagrange, rational approximation
Posted in Uncategorized | 1 Comment »

∑idiot's Blog

Posts Tagged ‘rational approximation’

Rational Approximations

Hardy and Wright, Chapter 10

Top Posts

Archives

About

Follow “∑idiot's Blog”