Approximation of a real number with a rational (motivation)

Measuring intervals, continued fractions, Beatty sequences and cutting sequences

The process of approximating a given quantity expressed as the length of a segment with a ruler marked with segments of unit length is a familiar one. We may visualize it by superposing a series of intervals of the unknown length r on top of a series of unit intervals. If r is rational marks in the top and bottom series will coincide sooner or later. For example, if r=7/5we may picture it as follows:

The approximation process

Ruler[7, 5]

[Graphics:../HTMLFiles/NumberTheory_213.gif]

-Graphics -

-Graphics -

If r is a more complex fraction, for example 31/27 we get

Ruler[31, 27]

[Graphics:../HTMLFiles/NumberTheory_218.gif]

-Graphics -

We may see some pretty close approximates, like the point where 21 intervals on the top almost coincides with 24 intervals in the bottom. It is well known (Lagrange) that the sequence of best approximates -in the sense that there are no other rationals of lesser height that get closer to r, are the convergents of the continued fraction expansion of r.

{N[23/19], N[7/6], N[24/21], N[31/27]}

{1.21053, 1.16667, 1.14286, 1.14815}

The point 23/19looks like a very good approximation in the diagram but when we look at the numbers we realize that it is not better than the convergents of similar height (complexity).

ContinuedFractionForm[ContinuedFraction[31/27]]

1 + 1/(6 + 1/(1 + 1/3))

Convergents[%]

{1, 7/6, 8/7, 31/27}

If r is irrational the edges on the top and bottom of the rulers will never coincide exactly, although they may get arbitrarily close. We may see the edges on the top as a sequence of multiples of r, and if we focus on the floors of those numbers; i.e., RowBox[{RowBox[{{⌊i r⌋}, _, RowBox[{(, RowBox[{i, =, RowBox[{0, Cell[]}]}], )}]}], ^, ∞}], we get what is often called a homogeneous Beatty sequence, and is sometimes known as the spectrum of r. Beatty sequences have been very well studied and have many interesting properties, particularly we can find pairs of Beatty sequences that partition the integers.

Sequences of differences between consecutive terms of a Beatty sequence like {⌊ (i + 1) r⌋ - ⌊i r⌋} _ (i = 0)^∞are related to the so called cutting sequences defined by the pattern of intersections of horizontal and vertical segments of the integral grid with a line passing through the origin, with irrational slope.

τ = (1 + 5^(1/2))/2

1/2 (1 + 5^(1/2))

Overscript[τ, _] = (1 - 5^(1/2))/2

1/2 (1 - 5^(1/2))

ContinuedFractionForm[ContinuedFraction[τ, 10]]

1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + 1/(1 + 1/1))))))))

Convergents[τ, 12]

{1, 2, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55, 144/89, 233/144}

%//N

{1., 2., 1.5, 1.66667, 1.6, 1.625, 1.61538, 1.61905, 1.61765, 1.61818, 1.61798, 1.61806}

ListPlot[Table[{i, Convergents[τ, #][[i]]}, {i, #}], PlotRange→All, Prolog→PointSize[0.025], PlotStyle→ {RGBColor[1, 0, 0]}] & @ 7

[Graphics:../HTMLFiles/NumberTheory_240.gif]

-Graphics -

Line plot

[Graphics:../HTMLFiles/NumberTheory_243.gif]

-Graphics -

Show[%, Graphics[{RGBColor[1, 0, 0], Map[Disk[{Denominator[#], Numerator[#]}, 0.15] &, Convergents[13/8]]}]]

[Graphics:../HTMLFiles/NumberTheory_246.gif]

-Graphics -

The cutting sequence corresponding to the figure given above is determined by the differences between consecutive terms of the Beatty sequence {⌊i τ⌋} _ (i = 1)^∞.

Table[⌊ (i + 1) (1 + 5^(1/2))/2⌋ - ⌊i (1 + 5^(1/2))/2⌋, {i, 1, 21}]/.{2→H, 1→V}

{H, V, H, H, V, H, V, H, H, V, H, H, V, H, V, H, H, V, H, V, H}

This sequence can also be generated by a simple rewriting system which depends on the coefficients of the continued fraction of r. In this particular example r is the Golden Ratio whose expansion has all coefficients equal to 1.

T[n_] := Flatten[Append[T[n - 1], T[n - 2]]]

T[0] := {V}

T[1] := {H}

T[7]

{H, V, H, H, V, H, V, H, H, V, H, H, V, H, V, H, H, V, H, V, H}

The approximation of τ by the convergents of its continued fraction can be visualized by a real function interpolating the convergents. This polynomial is derived from Binet's formula for the n-th Fibonacci term:

ℱ_n=1/5^(1/2)(τ^n-Overscript[τ, _]^n).

Since the convergents of τ are given by quotients of consecutive Fibonacci terms the function

f(n)=|(τ^n - Overscript[τ, _]^n)/(τ^(n - 1) - Overscript[τ, _]^(n - 1))|, n>1,n∈R,

will interpolate the convergents when n becomes an integer, as can be seen in the following plots.

In[98]:=

Clear[τ] ;

In[99]:=

τ = (1 + 5^(1/2))/2 ;

In[101]:=

Overscript[τ, _] = (1 - 5^(1/2))/2 ;

In[133]:=

[Graphics:../HTMLFiles/NumberTheory_265.gif]

We now superimpose the points corresponding to the convergents.

Show[Graphics/@{%, PointSize[0.025], RGBColor[1, 0, 0], ListPlot[Prepend[Convergents[τ, 10], 0], DisplayFunction→Identity]}] ;

[Graphics:../HTMLFiles/NumberTheory_267.gif]

The following complex valued function also interpolates the convergents.

In[226]:=

f[n_] := τ - Abs[(τ^n - Overscript[τ, _]^n)/(τ^(n - 1) - Overscript[τ, _]^(n - 1)) - τ] ^(π  n)

In[227]:=

[Graphics:../HTMLFiles/NumberTheory_270.gif]

When superimposed all odd convergents lie to the left of τ and all even convergents lie to the right.

[Graphics:../HTMLFiles/NumberTheory_271.gif]

Out[227]=

-Graphics -

Created by Mathematica  (June 3, 2006) Valid XHTML 1.1!