## Hardy and Wright, Chapter 10

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.