The Elegance Of Continued Fractions

Number theory, or higher arithmetic, is the branch of mathematics that studies natural numbers and similar objects. It’s uses stretch from the theoretical to the practical; from investigations of the properties of integers to stability questions as important as “Will the planets continue to orbit in well-defined zones without collision?”[1] Depending on the object of study and the methods used, the discipline of number theory can be subdivided into several different fields. Each of these uses a wide array of sophisticated tools to investigate its research questions. One of the most important and elegant – as well as highly effective – tools used by the number theorists, however, is the continued fraction.

What is a continued fraction?

Continued fractions are used when number theorists desire a “mathematically pure” representation of a real number.[2] While continued fractions are not the only possible representation of real numbers in terms of a sequence of integers (others include the decimal expansion and the so-called Engel expansion), they are a very common such representation and arise frequently in number theory. Ordinary continued fractions can be seen as discrete dynamical systems on [0,1].  Their expansions are used to find the best Diophantine approximations to a real number 0.[3]

The simple continued fraction representation (which is usually what is meant when the term “continued fraction” is used without qualification) of a number is given by the mathematical expression:

where a₀, a₁, a₂, … are all integers and a₁, a₂, … are all positive integers.[4] The values of a₁, a₂, etc. are referred to as “terms” or “partial quotients.”[5] Simple continued fractions can also be written in several different compact forms, such as:

Or even in a form as simple as x = [a₀; a₁, a₂, a₃, …].’[6] Any real number can be presented in the form of a continued function, but a number can only be represented as a continued function if it is rational. If and only if a number is a quadratic irrationality, it may be represented in the form of a circulating continued fraction.

            A simple continued fraction is a continued fraction in which the value of b_n = 1 for all n. The value of a_n is a positive integer for all n ≥ 1. a₁ can be any integer value, including 0.

This fraction may also be represented by [a₁; a₂, a₃…].

History of Continued Fractions

Continued fractions (or, in archaic terms, anthyphairetic ratios) have a long and illustrious history. Because they were developed based on Euclid’s algorithm, some scholars date their birth to around 300 BC, during the life of this great mathematician,[7] although he probably did not use them specifically.[8] In medieval India, the concept popped up in the Aryabhatiya of 499 AD, which gave a description of the integral solution to the equation ay + bx = c using continued fractions.[9] The first modern use of continued fractions dates back to the sixteenth century, when Italian algebraist Rafael Bombelli (known for developing the concept of complex numbers) published the following approximation of the square root of 13 in his Algebra[10]:

                                 4

3  +  —–

          4

   6 + —

          6

The study was continued in the early seventeenth century with contributions from mathematicians C. Schwenter and Christiaan Huygens.[11] The first thorough analysis, as well as the birth of term ‘continued fraction,’ however, did not arise until the mid-seventeenth century, when John Wallis published his Arithmetica Infinitorum.[12]

Uses of Continued Fractions

In order to demonstrate the beauty and elegance of the continued fraction, a few different examples of its uses will be given below.

Continued Fraction Expansion

            In continued fraction expansion, any nonzero real number x can be represented as a continued fraction [a₀; a₁, a₂, a₃, … ], where:

a₀ = [x], x₀ = x – a₀

For rational number x, this expression will end reaching zero x_n, for some n. In this case x is the finite continued fraction x = [a₀; a₁, …, a_n].  For irrational x, all values x_n will be zero and the process of expansion can be continued without limits. In this case x is presented as continued fraction x = [a₀; a₁, a₂, a₃, … ].

The numbers a₁, a₂, …, a_n, … are incomplete quotients, where a₁ Î Z, and a₂, …, a_n, … Î N. Numbers:

Are called approximants of continued fraction α.

The continued fraction can be finite and infinite. In the first case it represents an irrational number, in the second case it is clear that all its proper fractions are rational numbers.

The value of a continued fraction is the limit of infinite succession. Its proper fraction is given by α = lim δ_n, where n → ∞.

            α Î R – real number between two whole numbers: a ≤ α < a + 1. Let us take the arbitrary произвольное real number α Î R, q₁ = ë α û. Then α = q₁ + β₁, 0 ≤ β₁ < 1, therefore:

If, then, α₁ – is not whole, then:

For example, let us expand number α = √ 2 into the form of a continued fraction.

We have q₁ = ë √ 2 û = 1, β₁ = √ 2 – 1, т.e. α = 1 + (√ 2 – 1). Then,

q₂ =  ë √ 2 + 1 û = 1, β₂ = √ 2 – 1,

As β₁ = β₂, this process repeats and, if it is not stopped, we receive a continued infinite fraction: 

Proper Fractions

The proper fraction for continued fraction x = [a₀; a₁, a₂, a₃, …], is called continued fraction [a₀; a₁, …, a_n], which value is equal to some rational number P_n / q_n. Proper fractions with even numbers make up ascending sequence, the limits of which are equal to x.

Similarly, proper fractions with odd numbers make up decreasing sequence, the limit of which is also equal to x.

Eiler derived recurrence formula for calculating numerators and denominators of proper fractions:

Thus, values P_n and q_n are presented in continuant values:

Successions { P_n } and { q_n } are increasing.

Numerators and denominators of proper fractions are connected with the correlation:

p_nq_n – 1 – q_np_n – 1 = ( – 1)^{n – 1},

which can be presented in the following way: that leads to: 

Approximation of real numbers with the help of rational ones

            In addition to the above examples, continued fractions provide an excellent opportunity to find good rational approximations of real numbers. If a real number x is expanded into a continued fraction, then its proper fractions will be presented as:

Therefore, the measure of irrationality of any irrational number is not less than 2.

            In this way, it can be seen that continued fractions provide, in many cases, a series of “best” rational approximations for irrational numbers. This true for both numbers as well as functions, which may also be written as continued fractions in order to get a series of “best” rational approximations of that function.

Additionally, continued fractions can be useful in proving certain properties of special numbers like e and π. This is because quadratic surds have periodic continued fractions, so when it is suspected that a number represents an unknown quadratic surd, then it may be possible to find an exact representation of its tabulated numerical value.[13]

Furthermore, continued fractions can be very useful when trying to find commensurabilities between events with different periods. As one example, the Greek calendrical Metonic cycle consisted of 235 lunar months (about 19 solar years), and 235/19 represented the sixth convergent of the ratio of the lunar phase period (synodic) and the solar period (365.2425/29.53059). Continued fractions were also used by the ancient Greeks for the calculation of gear ratios.[14]

Any rational number can be presented in the form of a finite continued fraction in two ways, for instance: 9/4 = [2; 3, 1] = [2; 4]. The number is presented as a continued fraction only if it is an irrational decision of quadratic equation with whole factors. For example, √ 2 = [1; 2, 2, 2, …]; golden section ø = [1; 1, 1, 1, …].

For some numbers, one can find more complex patterns. For example, for building natural logarithms:

e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, …, 1, 1, 2(n-1), 1, 1, 2n, …]

However, the number π does not illustrate a similar pattern:

            π = [3; 7, 15, 1, 191, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15…]

The Euclidean Algorithm

            Finally, the Euclidian algorithm is a recursive function that allows the greatest common denominator of two integers a and b to be located. Given integers a and b, we can find q₁ and r₁ such that:

b = a q₁ + r₁, 0 ≤ r₁ < │a│

If one continues the sequence, eventually the remainder must converge to zero. The last two terms of the sequence are thus:

r_n-2 = r_n-1q_n + r_n

r_n-1 = r_nq_n+1

The value r_n can then be shown to be the greatest common denominator of a and b.[15]

Conclusion

            As has been shown through looking at these many examples, continued fractions are one of number theory’s most fascinating and elegant tools. In the beginning, continued fractions were developed in order to help in the approximation of irrational numbers. In the years since that time, they have become important tools for solving problems in probability theory and analysis as well as in number theory. Their beauty comes not just because they offer us solutions to specific problems, but also because they offer a new way of representing real numbers – a way that is obscured by more traditional decimal system representations.[16]

BIBLIOGRAPHY

Burr, Stefan Andrus. The Unreasonable Effectiveness of Number Theory: American Mathematical Society Short Course (Providence, R.I.: American Mathematical Society, 1992).

Herkommer, Mark. “Continued Fractions” in Number Theory: A Programmer’s Guide (Texas: McGraw-Hill, 1998),  available at http://www.petrospec-technologies.com/Herkommer/contfrac.htm.

Math.uiuc, “Guide to Graduate Students in Number Theory,” available at http://www.math.uiuc.edu/ResearchAreas/numbertheory/guide.html

Math.utk, “Continued Fractions,” available at http://archives.math.utk.edu/articles/atuyl/confrac/intro.html.

Mathworld, “Continued Fraction,” available at http://mathworld.wolfram.com/ContinuedFraction.html

Wikipedia, “Continued Fraction,” available at http://en.wikipedia.org/wiki/Continued_fraction.

Wikipedia, “Number Theory,” available at http://en.wikipedia.org/wiki/Number_theory.

[1] Stefan Andrus Burr, The Unreasonable Effectiveness of Number Theory: American Mathematical Society short course (Providence, R.I.: American Mathematical Society, 1992), 38.

[2] Wikipedia, “Continued Fraction,” available at http://en.wikipedia.org/wiki/Continued_fraction.

[3] Burr, above note 1, at 38.

[4] Wikipedia, above note 2.

[5] Math.utk, “Continued Fractions,” available at http://archives.math.utk.edu/articles/atuyl/confrac/intro.html.

[6] Wikipedia, above note 2.

[7] Ibid.

[8] Ibid.

[9] Wikipedia, “Number Theory,” available at http://en.wikipedia.org/wiki/Number_theory.

[10] Mark Herkommer, “Continued Fractions,” in Number Theory: A Programmer’s Guide (Texas: McGraw-Hill, 1998),  available at http://www.petrospec-technologies.com/Herkommer/contfrac.htm.

[11] Ibid.

[12] Julian Havil 2003, 93.

[13] Continued Fraction, 2008.

[14] Ibid.

[15] Mathworld, “Continued Fractions,” available at http://mathworld.wolfram.com/ContinuedFraction.html.

[16] Herkommer, above footnote 9.