Hardy and Wright, Chapter 11 (part 1)

Now that we’ve got continued fractions under our belt, from chapter 10, we can go on and start looking at “Approximation of Irrationals by Rationals”, chapter 11. One of the (many) cool things about continued fractions, is that they provide “best” rational approximations. We decided, yet again, to split the chapter into two weeks.

In our meeting today, discussing the content of 11.1-11.9, we spent most of our time trying to sort out some typos and see how a few of the inequalities came about. In particular, a typo on page 211, in the theorem that at least one in three consecutive convergents is particularly close to a starting irrational, took us quite a while to sort out.

Eric brought up a comment from the chapter notes that is quite fascinating. The first several sections talk about “the order of an approximation”. Given an irrational \xi, is there a constant K (depending on \xi) so that there are infinitely many approximations with |p/q-\xi|<K/q^n? This would be an order n approximation. In theorem 191, they show that an algebraic number of degree n (solution to polynomial of that degree) is not approximable to any order greater than n (which seems to be a slightly weaker (by 1) statement than Lioville’s Approximation Theorem). The note Eric pointed out was about Roth’s theorem which states that, in fact, no algebraic number can be approximated to order greater than 2. According to the Mathworld page, this earned Roth a Fields medal.

This reminded me about some things I had seen about the irrationality measure of a number. Roth’s theorem, reworded, says something like: every algebraic number has irrationality 1 (in which case it is rational) or 2. So if a number has irrationality measure larger than 2, you know it is transcendental. Apparently, finding the irrationality measure of a particular value is quite a trick. According to the Mathworld page, e has irrationality measure 2, so you can’t use that to decide about it being transcendental.

The whole thing is interesting, as pointed out in H&W, because you think of algebraic numbers as sort of nice (it doesn’t get much nicer than polynomials), but, in terms of rational approximations, they are the worst.

About these ads

Tags: , , , , , ,

15 Responses to “Hardy and Wright, Chapter 11 (part 1)”

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

    [...] ∑idiot’s Blog The math fork of sumidiot.blogspot.com « Hardy and Wright, Chapter 11 (part 1) [...]

  2. Tom Joad Says:

    Do you know any specific examples, or even just an existence proof, of a number that has irrationality measure that is greater than 2 but still finite? (It’s easy enough to construct numbers that have infinite irrationality measure, or measure that is greater than 2 but it’s not clear if the measure is finite. Some well-known numbers like pi have finite irrationality measure, but it might be =2.)

    • sumidiot Says:

      Hmm, good question. Mathworld’s Irrationality Measure page only indicates upper bounds for some numbers… That’s the best I know off the top of my head. I’ll think about it some more though.

      • Tom Joad Says:

        Thanks – at least now I know it wasn’t a dumb question! Here’s a candidate: x=.100100001…. This is defined as following. Take the sequence of integers n(1)=1, n(2)=4, … n(k)=3*n(k-1)+1
        then x=sum(10^(-n(k)). The partial sums of the series are of the form p/q where q=10^(-n(k)). And 0<abs(x-p/q)=3. But I haven’t shown that the irrationality measure is =3, or even that it is finite.

      • Tom Joad Says:

        Sorry, something went wrong and part of that last comment got lost. It should have read “And 0<abs(x-p/q)=3. But I haven’t shown that the irrationality measure is =3, or even that it is finite.”

      • Tom Joad Says:

        Sumidiot, I apologize – twice now, the text that occurred between a “less than” and a “greater than” has disappeared. The text editor must think it is a pair of brackets and disappeared it. I was trying to point out that the partial sums of that series x=sum(10^(-n(k)) are themselves approximations showing that x has irrationality measure at least 3, I’ll try one more time: “And 0<abs(x-p/q)<1/q^3 . So the irrationality measure of x is at least 3. But I haven’t shown that the irrationality measure is equal to 3, or even that it is finite." Hope that text comes through OK. Again, I apologize for the multiple postings,

    • Tom Joad Says:

      Well, as we used to say when I was growing up in Arkansas, “if it had been a snake it would have bit me”.

      We were looking at the number x=sum(10^(-n(k))), where n(1)=1 and n(k)=3*n(k-1)+1. In other words , x=0.1001000000001…(26 zeros)…1…. The partial sums of this series are of the form s(k)/t(k) where t(1)=10 and t(k+1)=10t(k)^3.

      Our intuition is that the only convergents of the simple continued fraction for x, that satisfy the inequality abs(x-p/q)<1/q^3, are exactly the partial sums of the series x=sum(10^(-n(k))). This intuition turns out to be correct.

      Consider the inequality 1/(2q(n)q(n+1))<abs(x-p(n)/q(n))<1/(q(n)q(n+1)). This inequality holds for all terms p(n)/q(n) in the sequence of convergents to x, where x is irrational. (it is Theorem 3.8 in C.D. Olds' book.) We use the inequality a couple of times in what follows.

      Now let p(n)/q(n)) be a convergent which satisfies abs(x-p(n)/q(n))<1/q(n)^3. Then we have 1/(2q(n)q(n+1))<1/q(n)^3, and therefore (q(n)^2)/2<q(n+1). "If p(n)/q(n) is a 'very good' approximation, then q(n+1) becomes 'very large'."

      We can now see (by contradiction) that none of the convergents that lie between the partial sums s(k)/t(k) and s(k+1)/t(k+1) are "as good as" the partial sums. For let p(m)/q(m) be a convergent, where t(k)<q(m)<t(k+1). And suppose for purposes of contradiction that p(m)/q(m) is "very good", i.e. that abs(x-p(m)/q(m))<1/q(m)^3. Then q(m) will be "too large". We would have (t(k)^2)/2<q(m) and (q(m)^2)/2<q(m+1)≤t(k+1). Combining these two inequalities, we get [(t(k)^2)/2]^2]/2≤t(k+1). That yields (t(k)^4)/8≤10t(k)^3. This yields the contradiction (except in the trivial case t(1)=10).

      Now we can see that the irrationality measure of x is 3. As we have seen, only the partial sums s(k)/t(k) satisfy the inequality abs(x-s(k)/t(k))<1/t(k)^3. And these partial sums actually satisfy abs(x-s(k)/t(k))=(0.1+e)/t(k)^3 where e approaches 0 as k become large. So we cannot substitute anything larger than 3 for the exponent in the inequality.

      Thanks very much for helping me with this. I think I should apologize for luring you into it. I have time to mess around with something like this, but you don't. Happy New Year, and let 2010 be the year of "the dissertation, the dissertation, and nothing but the dissertation!"

      • sumidiot Says:

        Nice!

        And no need to apologize. It’s good for me. Surely. :) I’ll see what I can do about that dissertation. Hopefully I can occasionally find some other fun things to post about here for your amusement.

  3. sumidiot Says:

    @Tom Joad, I haven’t wrestled with the inequalities enough, but it looks like your idea is sound. Constructing x as you do seems to give those lower bounds for the irrationality measure, as you point out, and it feels like there is reason for some optimism that 3 might be an upper bound as well, in your example.

    Somewhat similarly, I was thinking about constructing x using the continued fraction expansion, which might make checking upper bounds easier as well. If you’ve got a copy of Khinchin’s (delightful) “Continued Fractions” book, equation (34) is (in my edition anyway) \frac{1}{q_k(a_{k+1}+2)}<\left| x-\frac{p_k}{q_k}\right|\leq \frac{1}{q_k^2a_{k+1}}. I think, then, choosing a_{k+1}=q_k^c, where c=n-2, might just show that x has irrationality measure n. I could, of course, be wrong. These are my first (maybe we're up to second now) guesses.

    A limited preview of Khinchin's book is on Google Books, if you don't have a copy. Here’s the page with the inequality I mentioned.

  4. Tom Joad Says:

    Sumidiot, thanks for the hint. I saw that you suggested looking at the a(k), and went to my copy of Continued Fractions by C D Olds (which I’ve had for 45 years) and worked out the answer – then came back and saw that it was close to what you had suggested to begin with. Here’s my version of your answer:

    There are recursive equations for the convergents of a simple continued fraction –
    p(k)=p(k-2)+a(k)*p(k-1)
    q(k)=q(k-2)+a(k)*q(k-1)
    Furthermore, according to wolfram.com on irrationality measure, the irrationality measure m is given by
    m=1+lim_sup{log(q(k)/log(q(k-1)}.

    We can start out (for instance) with
    p(1)/q(1)=0/1
    p(2)/q(2)=1/2
    Then recursively set
    a(k)=q(k-1) for k>2

    Then we get
    p(k)=q(k-1)*p(k-1)+p(k-2);
    q(k)=q(k-2)+q(k-1)^2.

    It’s pretty easy to see that for this recursively defined number with convergents
    c(k)=p(k)/q(k)
    the irrationality measure is exactly 3.

    The specific transcendental number that we get with this definition isn’t particularly pretty – it starts out 0.592643049….

    I used some of the same ideas to look further at our original candidate x=sum(10^(-n(k)). The partial sums of the series are themselves convergents because they satisfy the inequality abs(x-p/q)<1/(2*q^2). But unfortunately they are not sequential convergents. The best I could do, using that lim_sup formula from wolfram.com, was to see that the irrationality measure of x is no greater than 4. So the measure is somewhere in the interval [3,4] – and almost certainly equal to 3. At least x it is a simple example of a number with a finite irrationality measure greater than 2.

    I'm not certain of all this – I'm a retired engineer, not a mathematician.

    • Tom Joad Says:

      When I said “It’s pretty easy to see … the irrationality measure is exactly 3″, I was referring to that formula m=1+lim_sup{log(q(k))/log(q(k-1))}. (Sorry, I left out some parentheses in the last post.) In this case, we have m=1+lim_sup{log(q(k-2)+q(k-1)^2)/log(q(k-1))} The quotient of logs approaches 2 monotonically from above quite rapidly. So m=3.

      For the original candidate x=sum(10^(-n(k))), if if x(n)/y(n) and x(n+1)/y(n+1) are two consecutive partial sums, then 1+log(y(n+1))/log(y(n)) approaches 4 in the limit. Also, log(y(n+1)/log(y(n)) is strictly greater than log(q(k+1))/log(q(k)) for all convergents p(k)/q(k) with q(k)<y(n). So the irrationality measure of x is no greater than 4. (We already know it is at least 3.)

      Hope this is correct….

      • Tom Joad Says:

        Oops, careless. Regarding x=sum(10^(-n(k))), should have said “Also, log(y(n+1)/log(y(n)) is greater than or equal to log(q(k+1))/log(q(k)) for all convergents p(k)/q(k) with y(n)<=q(k)<y(n+1). So the irrationality measure of x is no greater than 4." Oh well, as I said, I'm not a mathematician.

  5. sumidiot Says:

    Sorry it has taken me so long to get back to these comments. It’s all quite fun, so I wanted to give it an honest look.

    First up, the lim_sup you point out. I don’t know how many times I’ve looked at that wolfram page on irrationality measures, but that lim_sup never stuck in my mind. So thanks for bringing it up. Also, I think the second lim_sup, about ln(a(k+1))/ln(q(k)), is even easier to calculate in the continued fraction example above.

    I think I agree with the things you are saying above. I don’t think I’ve thought quite enough about your very last comment, about y(n)\leq q(k)<y(n+1), but I still agree that the irrationality measure of x is no greater than 4. Here's my thought process:

    As you say, the partial sums are convergents to x. As they form an increasing sequence of convergents to x, they must be convergents of what Khinchin calls even-order (the 0th, 2nd, 4th, 6th, etc, convergents). This is because the even-order convergents are all less than x, while odd-order convergents are all bigger than x.

    My gut reaction is that the partial sums are consecutive even-order convergents, but I could be wrong. Either way, as you point out, if the partial sums have values s(n)/t(n) (I'll switch away from x(n) and y(n) so I don't confuse myself), then the limit of \ln(t(n+1))/\ln(t(n)) is 3. Suppose s(n)/t(n) is the m-th convergent, p(m)/q(m), and latex s(n+1)/t(n+1) is the M-th convergent (as they are even, we could write m=2k and M=2K for some k,K, but I won't use that). Then \ln(t(n+1))/\ln(t(n))=\ln(q(M))/\ln(q(m)) which we could write as \dfrac{\ln q(M)}{\ln q(M-1)}\dfrac{\ln q(M-1)}{\ln q(M-2)}\cdots\dfrac{\ln q(m+1)}{\ln q(m)}. This product goes to 3 (from above) in the limit, putting an upper bound of 3 on the lim_sup that Mathworld suggests we calculate.

    I don't see how to go any further down this road, actually explicitly determining the irrationality measure, without figuring out more about the convergents to x. Namely, are the partial sums actually consecutive even-order convergents? And what are the missing convergents?

  6. sumidiot Says:

    My gut instinct was wrong. I no longer believe that the partial sums are consecutive even-order convergents (though they are still even-order).

    I decided this based on some playing with Wolfram|Alpha, for example convergents of the 4th partial sum. Some more playing with some computer tools, getting convergents for bigger partial sums, could likely point out the pattern for all of the convergents.

  7. Tom Says:

    Just thought I’d point you to the following paper by Brisebarre, in which he mentions (halfway down page 2) a way to construct a family of reals with any given irrationality measure.
    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.76.3977&rep=rep1&type=pdf

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: