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.

About these ads

Tags: , , , , , , ,

One Response to “Hardy and Wright, Chapter 10”

  1. Hardy and Wright, Chapter 11 (part 1) « ∑idiot’s Blog Says:

    […] ∑idiot’s Blog The math fork of sumidiot.blogspot.com « Hardy and Wright, Chapter 10 […]

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


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: