Continued Fractions and Characteristic Recurrences

It's easy to find the best fractional approximations for the square
root of 2, based on the simple continued fraction.  This gives
convergents 7/5, 17/12, 41/29, and so on.  However, it's not so
easy to define the analagous sequence for CUBE root of 2.

Lagrange proved the simple continued fraction of an irrational
number is periodic if and only if the number is a quadratic
irrational, i.e., the root of a quadratic equation, such as
x^2 - 2 = 0.  As a result, the numerators and denominators of
successive convergents of the continued fraction for sqrt(N) can
always be generated by a simple second order linear recurrence.
This corresponds to the solutions of the basic "Pell equation"  
x^2 - Ny^2 = 1.  On the other hand, solutions of the analagous
equation x^3 - Ny^3 = 1 for cubes are less well-behaved.

Nevertheless, it's always possible to construct a linear recurring
sequence of integers s[0], s[1], s[2],... such that any specified
algebraic number is approached by some function of the ratio of
successive terms s[n+1]/s[n].  In particular, to construct a 
sequence for the rth root of N, let m denote the largest integer 
such that m^r < N.  Then we have the rth order recurrence relation

               r   / r \   (r-j)       (j-1)
    s[n]  =  SUM  (     ) m     (N-m^r)     s[n-j]
              j=1  \ j /

with the initial values s[0]=s[1]=..s[r-2]=0 and s[r-1]=1,
any by construction we have

      N^(1/r)  =   lim     m + (N-m^r) ------
                  n->inf               s[n+1]

For example, to construct the sequence for the cube root of 2
we have N=2 and r=3, so m=1 and the recurrence is

        s[n] = 3 s[n-1] + 3 s[n-2] + s[n-3]

The approximations for 2^(1/3) given by successive ratios of
terms in this sequence are listed below, along side the convergents
of the continued fraction

      generated by            convergents of
      linear recurrence       continued fraction  1/|N(N-DV)|

                   4/3 *                 4/3       1.135
                   5/4 *                 5/4       5.040
                 29/23 *               29/23       1.581
               223/177                 34/27       1.646
                                       63/50       4.021
               286/227 *             286/227       1.682
             3301/2620               349/277       1.533
               635/504 *             635/504       7.530
             5429/4309 *           5429/4309       0.940
             6064/4813 *           6064/4813      12.546
         723235/574032           90325/71691       0.924
         463753/368081           96389/76504       8.964
      10705243/8496757        1054215/836731       2.298
         957826/760227       2204819/1749966       1.368
     52819267/41922680       3259034/2586697       3.787
     15240955/12096754 *   15240955/12096754       8.806
  2345474521/186104361   186150494/147747745       1.834

Those marked with an asterisk are the same on both lists.  This
raises the interesting question of whether infinitely many
convergents occur in the sequence generated by the 3rd order

We might also wonder which of the above approximations is the
"best".  Obviously the absolute accuracy improves indefinitely,
but we can define a notion of "goodness" by considering the
ratio of how many digits of accuracy are achieved per digit
of the numerator and denominator.  One such measure for the
approximation N/D to the value V is 1/|N(N-DV)|.  The goodness
of each convergent is listed in the right hand column of the
table above.

It's interesting that the goodness of the continued fractions
never falls much below 1.0, whereas the linear recurrence
approximations can have very low values of "goodness".  For
example, the goodness of 723235/574032 is just 0.0122.  

I wonder what can be said about the distribution of "goodness" of
continued fraction convergents.  For example, how soon would we
expect a convergent with more goodness than 12.546, which is the
maximum for all the values listed in the table?

Return to MathPages Main Menu