Chain fraction

In mathematics and especially the number theory is a continued fraction (continued break) an expression of the form

${\ displaystyle a + {\ cfrac {b} {c + {\ cfrac {d} {e + {\ cfrac {f} {\ ddots}}}}}} \ quad.}$

A continued fraction ( English continued fraction is therefore) a mixed fraction of the form in which the denominator again has the shape of a mixed fraction, with this construction so continues further. ${\ displaystyle a + {\ tfrac {b} {x}}}$${\ displaystyle x}$

Any real number can be expressed as a continued fraction with whole numbers . Continued fractions can therefore be referred to as a number system , like the decimal system . However, they are not primarily used for arithmetic, but are used to solve approximation problems: In number theory, for example, they provide approximations for real numbers by expressing them using a fraction of whole numbers, and in numerical mathematics they are used to approximate Functions, similar to how this is also achieved using power series . ${\ displaystyle a, b, c, d, e, f, \ dotsc}$

Regular continued fractions , also called regular or simple continued fractions , are of particular importance . Such a regular (regular / simple) continued fraction ( English regular / simple continued fraction ) is characterized by the fact that all counters have the value . A regular continued fraction is therefore determined by the sequence , and it is written as . ${\ displaystyle (b, d, f, \ dotsc)}$${\ displaystyle 1}$${\ displaystyle a, c, e, \ dotsc}$${\ displaystyle [a; c, e, \ dotsc]}$

In addition, the negative- regular continued fractions, which are closely related to regular continued fractions, play a role. With them all counters are also all the same, but the same . ${\ displaystyle (b, d, f, \ dotsc)}$${\ displaystyle -1}$

Continued fractions also play a major role in number theory. For example, in 1844 Joseph Liouville showed with her help that transcendent numbers exist. In addition to number theory, continued fractions are used in cryptography , algebraic geometry , topology , function theory , numerical mathematics and in the analysis of chaotic systems .

Together with Leonhard Euler, Joseph-Louis Lagrange is considered to be the founder of the continued fraction theory.

history

 ${\ displaystyle {\ sqrt {2}} = 1 + {\ cfrac {1} {2 + {\ cfrac {1} {2 + {\ cfrac {1} {2 + {\ cfrac {1} {2+ { \ cfrac {1} {\ ddots}}}}}}}}}}}$ Regular continued fraction ${\ displaystyle {\ cfrac {4} {\ pi}} = 1 + {\ cfrac {1 ^ {2}} {3 + {\ cfrac {2 ^ {2}} {5 + {\ cfrac {3 ^ { 2}} {7 + {\ cfrac {4 ^ {2}} {9 + {\ cfrac {5 ^ {2}} {\ ddots}}}}}}}}}}}$ Lambert's chain fraction for${\ displaystyle 4 / \ pi}$ ${\ displaystyle \ tan (z) = {\ cfrac {z} {1 - {\ cfrac {z ^ {2}} {3 - {\ cfrac {z ^ {2}} {5 - {\ cfrac {z ^ {2}} {7 - {\ cfrac {z ^ {2}} {\ ddots}}}}}}}}}}}}$ Lambert's continued fraction for the tangent

Continued fractions have been used since the 16th century to find “good approximate fractions” for irrational numbers . The best known example is the approximation for . ${\ displaystyle 22/7}$${\ displaystyle \ pi}$

Deliciae physico-mathematicae, 1636

Rafael Bombelli used continued fractions as early as 1579 to calculate square roots. In 1613 Pietro Cataldi published a book in which, among other things, chain fractions appear. 1636 there are continued fractions in the book "Deliciae Physico-Mathematicae" by Daniel Schwenter and from 1655 in several books by John Wallis . Out of the need to approximate fractions with large denominators and natural constants, Christiaan Huygens first dealt with continued fractions in the 17th century. He used the orbital times of the planets to calculate the gear ratio of the gears for his gear model of the solar system. Huygens determined the relationship between Saturn and Earth for the orbit around the sun as

${\ displaystyle {\ frac {77 \, 708 \, 431} {2 \, 640 \, 858}} \ approx 29 {,} 425448.}$

The regular continued fraction for this begins with . If one approximates this ratio with the approximate fraction that results from using only the first four entries, then the error is only , da ${\ displaystyle [29; 2,2,1,5,1,4, \ dotsc]}$${\ displaystyle 0 {,} 003123}$

${\ displaystyle 29 + {\ cfrac {1} {2 + {\ cfrac {1} {2 + {\ cfrac {1} {1}}}}}} = {\ cfrac {206} {7}} \ approx 29 {,} 428571.}$

In Leonhard Euler's correspondence, however, continued fractions first appear in a completely different context, namely in connection with the Riccatian differential equation . Soon, however, Euler became interested in continued fractions for their own sake. Namely, he discovered the following three important properties:

1. Every rational number can be represented by a finite regular continued fraction (which can be calculated using the Euclidean algorithm ).
2. Periodic regular continued fractions represent quadratic irrational numbers; Euler was the first to prove this.
3. The expansion of any real number into a regular continued fraction provides the best rational approximations for this number.

Huygens had already gained some of these findings, but Euler was not aware of his work. Euler's work - and based on it that of Joseph-Louis Lagrange  - founded the theory of continued fractions.

For rational approximation exists next to the algorithm of Euler also an algorithm of Lord William Brouncker . Euler showed around 1759 that the two algorithms are identical. Johann Heinrich Lambert used continued fractions in his work from 1766 to show the irrationality of . Its continued fraction expansion of the tangent function is shown in the figure on the right. ${\ displaystyle \ pi}$

Moritz Abraham Stern created the first systematic summary of the theory of continued fractions in 1832. The theory developed rapidly in the 19th century and so Oskar Perron published a summary of the state of knowledge in 1913, which is still considered a standard work today (new edition 1954/57).

Further important applications were and are: Proof of the irrationality or the transcendence of special numbers and the determination of leap years (since a year with 365.24219 days is slightly shorter than 365¼ days, a further correction is required every four years in addition to the leap day; the the best choice for this can be justified with continued fractions).

definition

Concept of continued fraction

A (infinite) continued fraction is a continued fraction of the form

${\ displaystyle b_ {0} + {\ cfrac {a_ {1}} {b_ {1} + {\ cfrac {a_ {2}} {b_ {2} + {\ cfrac {a_ {3}} {b_ { 3} + {\ cfrac {a_ {4}} {\; \, \ ddots}}}}}}}} \ quad}$ or (regular case) ${\ displaystyle b_ {0} + {\ cfrac {1} {b_ {1} + {\ cfrac {1} {b_ {2} + {\ cfrac {1} {b_ {3} + {\ cfrac {1} {\; \, \ ddots}}}}}}}}}$

with and for . ${\ displaystyle b_ {0} \ in \ mathbb {Z}}$${\ displaystyle a_ {i}, b_ {i} \ in \ mathbb {N}}$${\ displaystyle i \ in \ mathbb {N}}$

The fractions, or are called partial fractions , are called the -th partial counter and the -th partial denominator . The partial counters and partial denominators are also called elements of the continued fraction (following Oskar Perron ) . ${\ displaystyle {\ tfrac {a_ {i}} {b_ {i}}}}$${\ displaystyle {\ tfrac {1} {b_ {i}}}}$${\ displaystyle a_ {i}}$${\ displaystyle i}$${\ displaystyle b_ {i}}$${\ displaystyle i}$

A continued fraction that does not continue after a partial fraction is a finite continued fraction . ${\ displaystyle {\ tfrac {a_ {i}} {b_ {i}}}}$

A more formal definition can be found in the section Representation as a composition of images .

Regular continued fractions are by far the most important continued fraction type in number theory. When approximating (real or complex) functions one also uses continued fractions with unknowns, see for example Lambert's continued fraction for the tangent function in the section “History”. Sometimes you need a finite regular continued fraction where the last entry is a real (non-integer) number. This enables, for example, the spelling etc. for the golden number . General continued fractions are also sometimes used. ${\ displaystyle b_ {n}}$${\ displaystyle \ textstyle \ phi = [1; \ phi] = [1; 1, \ phi]}$${\ displaystyle a_ {i} \ in \ mathbb {Z}}$

notation

The shorthand for a general continued fraction is

${\ displaystyle b_ {0} + {\ frac {a_ {1} |} {| b_ {1}}} + {\ frac {a_ {2} |} {| b_ {2}}} + {\ frac { a_ {3} |} {| b_ {3}}} + \ cdots}$

Based on the sum and product signs and led Gauss also the following notation for this one: ${\ displaystyle \ sum}$${\ displaystyle \ prod}$

${\ displaystyle b_ {0} + {\ underset {i = 1} {\ overset {\ infty} {\ mathbf {K}}}} {\ frac {a_ {i}} {b_ {i}}} \, .}$

A regular continued fraction is often written in the following way:

${\ displaystyle [b_ {0}; b_ {1}, b_ {2}, \ dotsc]}$

${\ displaystyle b_ {0}}$is only listed separately because it is over, but the following are always only off . ${\ displaystyle \ mathbb {Z}}$${\ displaystyle b_ {i}}$${\ displaystyle \ mathbb {N}}$

The notation for finite continued fractions is accordingly

${\ displaystyle b_ {0} + {\ frac {a_ {1} |} {| b_ {1}}} + {\ frac {a_ {2} |} {| b_ {2}}} + \ cdots + { \ frac {a_ {n} |} {| b_ {n}}} \ ,, \ quad b_ {0} + {\ underset {i = 1} {\ overset {n} {\ mathbf {K}}}} {\ frac {a_ {i}} {b_ {i}}} \ ,, \ quad [b_ {0}; b_ {1}, \ dotsc, b_ {n}] \ ,.}$

Representation as a composition of images

A continued fraction can also be represented as a composition of images . This provides a more formal definition than the one given so far. ${\ displaystyle T_ {i} \ colon \ mathbb {R} \ to \ mathbb {R}}$

For this you bet and receive ${\ displaystyle T_ {i} (x) = {\ tfrac {a_ {i}} {b_ {i} + x}}}$

${\ displaystyle b_ {0} + {\ underset {i = 1} {\ overset {n} {\ mathbf {K}}}} {\ frac {a_ {i}} {b_ {i}}}: = b_ {0} + T_ {1} \ circ T_ {2} \ circ \ cdots \ circ T_ {n-1} \ circ T_ {n} (0).}$

Infinite continued fractions are defined by looking at the limit values in the Infinite Continued Fractions section .

Finite continued fractions

Finite continued fractions and their approximate fractions

From now on we only consider regular continued fractions. If you break off the chain fraction after the -th link for a , it is called ${\ displaystyle [b_ {0}; b_ {1}, \ dotsc, b_ {N}]}$${\ displaystyle n}$${\ displaystyle n \ leq N}$

${\ displaystyle {\ frac {p_ {n}} {q_ {n}}} = [b_ {0}; b_ {1}, \ dotsc, b_ {n}]}$

its -th approximate fraction (or -th convergent ). The first approximate fractions are apparently ${\ displaystyle n}$${\ displaystyle n}$

${\ displaystyle {\ frac {p_ {0}} {q_ {0}}} = {\ frac {b_ {0}} {1}}, \ quad {\ frac {p_ {1}} {q_ {1} }} = b_ {0} + {\ cfrac {1} {b_ {1}}} = {\ frac {b_ {0} b_ {1} +1} {b_ {1}}}, \ quad {\ frac {p_ {2}} {q_ {2}}} = b_ {0} + {\ cfrac {1} {b_ {1} + {\ cfrac {1} {b_ {2}}}}} = {\ frac {b_ {0} b_ {1} b_ {2} + b_ {0} + b_ {2}} {b_ {1} b_ {2} +1}}}$.

In the example 41/29 = [1; 2,2,2,2] these are the fractions . The third approximate fraction is and the fourth is the same , i.e. identical to the initial fraction . ${\ displaystyle {\ tfrac {1} {1}}, {\ tfrac {3} {2}}, {\ tfrac {7} {5}}}$${\ displaystyle {\ tfrac {17} {12}}}$${\ displaystyle {\ tfrac {41} {29}}}$

With complete induction one proves the formation law for the approximate fractions ( and are also defined pro forma for , so that the formulas are correct): ${\ displaystyle p_ {n}}$${\ displaystyle q_ {n}}$${\ displaystyle n = {- 1}, {- 2}}$${\ displaystyle n = 0}$

 ${\ displaystyle p_ {n} = b_ {n} p_ {n-1} + p_ {n-2} \,}$ ${\ displaystyle p _ {- 1} = 1 \,}$ ${\ displaystyle p _ {- 2} = 0 \,}$ ${\ displaystyle q_ {n} = b_ {n} q_ {n-1} + q_ {n-2} \,}$ ${\ displaystyle q _ {- 1} = 0 \,}$ ${\ displaystyle q _ {- 2} = 1 \,}$

as well as the relationship

${\ displaystyle q_ {n} p_ {n-1} -p_ {n} q_ {n-1} = (- 1) ^ {n} \,}$.

From this it follows that approximate fractions are always in abbreviated form (if and both were greater than divisible by a natural number , then the right-hand side would also have to be divisible by this number, which is not the case). If one divides by , it follows: ${\ displaystyle p_ {n}}$${\ displaystyle q_ {n}}$${\ displaystyle 1}$${\ displaystyle q_ {n} q_ {n-1}}$

 ${\ displaystyle {\ frac {p_ {n-1}} {q_ {n-1}}} - {\ frac {p_ {n}} {q_ {n}}} = {\ frac {(-1) ^ {n}} {q_ {n} q_ {n-1}}}.}$ (1)

For example, one has the relationship for the second and third approximate fractions of${\ displaystyle 41/29}$

${\ displaystyle {\ frac {7} {5}} - {\ frac {17} {12}} = {\ frac {(-1) ^ {3}} {60}} = {\ frac {-1} {60}}}$.

One shows in a similar way

${\ displaystyle q_ {n} p_ {n-2} -p_ {n} q_ {n-2} = (- 1) ^ {n-1} b_ {n}}$

and

 ${\ displaystyle {\ frac {p_ {n-2}} {q_ {n-2}}} - {\ frac {p_ {n}} {q_ {n}}} = {\ frac {(-1) ^ {n-1} b_ {n}} {q_ {n} q_ {n-2}}}.}$ (2)

These formulas are fundamental to the infinite continued fraction convergence questions discussed below .

Matrix display

The law of formation for the approximate fractions can also be written elegantly in matrix form . One then obtains (again to be proven with complete induction):

${\ displaystyle {\ begin {pmatrix} b_ {0} & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} b_ {1} & 1 \\ 1 & 0 \ end {pmatrix}} \ cdots {\ begin {pmatrix } b_ {n} & 1 \\ 1 & 0 \ end {pmatrix}} = {\ begin {pmatrix} p_ {n} & p_ {n-1} \\ q_ {n} & q_ {n-1} \ end {pmatrix}} .}$

Since the determinant of each of the matrices is on the left , it immediately follows ${\ displaystyle -1}$

${\ displaystyle p_ {n} q_ {n-1} -q_ {n} p_ {n-1} = (- 1) ^ {n + 1}}$

and multiplication by again shows the equation given above. ${\ displaystyle -1}$

By transposing both sides of the equation it now follows (since the transposition of the product on the left reverses the order of its factors) that and hold. ${\ displaystyle [b_ {n}; b_ {n-1}, \ dotsc, b_ {0}] = {\ tfrac {p_ {n}} {p_ {n-1}}}}$${\ displaystyle [b_ {n}; b_ {n-1}, \ dotsc, b_ {1}] = {\ tfrac {q_ {n}} {q_ {n-1}}}}$

Example: The convergents of loud , , and . It applies ${\ displaystyle [1; 1,2,3] = {\ tfrac {17} {10}}}$${\ displaystyle {\ tfrac {1} {1}}}$${\ displaystyle {\ tfrac {2} {1}}}$${\ displaystyle {\ tfrac {5} {3}}}$${\ displaystyle {\ tfrac {17} {10}}}$

${\ displaystyle {\ begin {pmatrix} 1 & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} 1 & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} 2 & 1 \\ 1 & 0 \ end {pmatrix} } {\ begin {pmatrix} 3 & 1 \\ 1 & 0 \ end {pmatrix}} = {\ begin {pmatrix} 17 & 5 \\ 10 & 3 \ end {pmatrix}}}$

and the transposition

${\ displaystyle {\ begin {pmatrix} 3 & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} 2 & 1 \\ 1 & 0 \ end {pmatrix}} {\ begin {pmatrix} 1 & 1 \\ 1 & 0 \ end {pmatrix} } {\ begin {pmatrix} 1 & 1 \\ 1 & 0 \ end {pmatrix}} = {\ begin {pmatrix} 17 & 10 \\ 5 & 3 \ end {pmatrix}}}$

results as well . ${\ displaystyle [3; 2,1,1] = {\ tfrac {17} {5}}}$${\ displaystyle [3; 2,1] = {\ tfrac {10} {3}}}$

Finite Continued Fractions and the Euclidean Algorithm

Reshaping from 17/10 to [1; 1,2,3] geometrically illustrated

The conversion of a rational number into a continued fraction is done with the help of the Euclidean algorithm.

As an example, we calculate as follows: ${\ displaystyle {\ tfrac {17} {10}} = [1; 1,2,3]}$

{\ displaystyle {\ begin {aligned} 17 & = 1 \ cdot 10 + 7 \\ 10 & = 1 \ cdot 7 + 3 \\ 7 & = 2 \ cdot 3 + 1 \\ 3 & = 3 \ cdot 1 \ end {aligned} }}

See also the section Continued Fractional Decomposition in the article on the Euclidean algorithm. This procedure is illustrated in the figure. From the following chain of equations it can be seen that the continued fraction expansion is created by repeatedly inserting the equations of the Euclidean algorithm:

${\ displaystyle {\ frac {17} {10}} = 1 + {\ dfrac {7} {10}} = 1 + {\ dfrac {\ \ 1 \ \} {\ dfrac {10} {7}}} = 1 + {\ dfrac {1} {1 + {\ dfrac {3} {7}}}} = 1 + {\ dfrac {1} {1 + {\ dfrac {1} {\ dfrac {7} {3 }}}}} = 1 + {\ dfrac {1} {1 + {\ dfrac {1} {2 + {\ dfrac {1} {3}}}}}}}$

The graphical process can be explained as follows: You start with a large rectangle. You put as many squares the length of the side into it as possible (in this example this only works once). A large rectangle now remains uncovered, to which one applies the consideration further. The number of squares used in each case are the denominators of the continued fraction. ${\ displaystyle 17 \ times 10}$${\ displaystyle 10}$${\ displaystyle 10 \ times 7}$

Infinite continued fractions

Infinite continued fractions: convergence and approximate fractions

The approximate fractions with an even index form a rising sequence, those with an uneven index a falling sequence. Both converge against .${\ displaystyle \ alpha}$

For an (infinite) sequence , the continued fraction is only defined if the sequence of approximate fractions converges . In this case, the infinite continued fraction has value . ${\ displaystyle b_ {0}, b_ {1}, \ dotsc}$${\ displaystyle [b_ {0}; b_ {1}, \ dotsc]}$${\ displaystyle (p_ {n} / q_ {n}) _ {n}}$ ${\ displaystyle [b_ {0}; b_ {1}, \ dotsc]}$${\ displaystyle \ lim _ {n \ to \ infty} [b_ {0}; b_ {1}, \ dotsc, b_ {n}]}$

Since only regular continued fractions are dealt with here, the following applies: Every infinite continued fraction converges.

This can be seen as follows: The sequence of approximate fractions with even indices, i.e. due to equation (2), is monotonically increasing , while the sequence with odd indices is monotonically decreasing, see figure. In addition, since any odd approximate fraction is larger than any even, both sequences are monotonic and bounded and therefore converge. However, due to equation (1), your two limit values ​​are the same (since they can be arbitrarily large, the difference tends towards 0). ${\ displaystyle p_ {0} / q_ {0}, p_ {2} / q_ {2}, \ dotsc}$${\ displaystyle p_ {1} / q_ {1}, p_ {3} / q_ {3}, \ dotsc}$${\ displaystyle q_ {n}}$

Now consider ${\ displaystyle \ alpha = [b_ {0}; b_ {1}, \ dotsc].}$

The difference between and the -th approximate fraction can be estimated from the formulas given above : ${\ displaystyle \ alpha}$${\ displaystyle n}$

 ${\ displaystyle {\ frac {b_ {n + 2}} {q_ {n} q_ {n + 2}}} <\ left | \ alpha - {\ frac {p_ {n}} {q_ {n}}} \ right | <{\ frac {1} {q_ {n} q_ {n + 1}}}.}$ (3)

As an example for equation (3) consider the continued fraction of the square root of 2. In the section Periodic Continued Fractions it is shown that . ${\ displaystyle {\ sqrt {2}} = [1; 2,2, \ dotsc]}$

The first approximation breaks this infinite chain breakdown are , , , , and Equation (3) states in this case : ${\ displaystyle 1/1}$${\ displaystyle 3/2}$${\ displaystyle 7/5}$${\ displaystyle 17/12}$${\ displaystyle 41/29}$${\ displaystyle n = 2}$

${\ displaystyle {\ frac {2} {5 \ cdot 29}} <\ left | {\ sqrt {2}} - {\ frac {7} {5}} \ right | <{\ frac {1} {5 \ cdot 12}}}$.

It is now clear that every rational number has a finite continued fraction and that every finite continued fraction represents a rational number. This representation is ambiguous, as you can write the end of the continued fraction in two ways without changing the value: You can switch between the representations and . But every irrational number has a unique representation: ${\ displaystyle [\ dotsc, b_ {n} +1]}$${\ displaystyle [\ dotsc, b_ {n}, 1]}$

Theorem (rational and irrational numbers, uniqueness of representation):

Every real number can be represented as a (regular) continued fraction. For irrational numbers the continued fraction representation is infinite and unique. Rational numbers correspond to finite continued fractions, and every rational number has exactly two continued fraction representations.

For the proof of the statement that every infinite continued fraction represents an irrational number, the following applies: If one considers and assumes that would be rational, then is ${\ displaystyle \ alpha = [b_ {0}; b_ {1}, \ dotsc]}$${\ displaystyle \ alpha = c / d}$

${\ displaystyle 0 <\ left | {\ frac {c} {d}} - {\ frac {p_ {n}} {q_ {n}}} \ right | <{\ frac {1} {q_ {n} q_ {n + 1}}}}$

and multiplication with and gives ${\ displaystyle d}$${\ displaystyle q_ {n}}$

${\ displaystyle 0 <| cq_ {n} -dp_ {n} | <{\ frac {d} {q_ {n + 1}}}}$.

Since they become arbitrarily large for increasing and the number between the amount bars is always a whole number, this produces a contradiction. Thus is not rational. ${\ displaystyle q_ {n + 1}}$${\ displaystyle n}$${\ displaystyle \ alpha}$

Infinite continued fractions and the generalized Euclidean algorithm

For irrational numbers a generalization of the Euclidean algorithm is used. This also works for rational numbers; we therefore check in every step whether the algorithm aborts: ${\ displaystyle \ alpha}$

1. Is not an integer, you have to set ( integer part of ) and the rest to the inverse, that is .${\ displaystyle \ alpha}$${\ displaystyle b_ {0} = \ lfloor \ alpha \ rfloor}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha _ {1}}$${\ displaystyle \ alpha _ {1} = 1 / (\ alpha -b_ {0})}$
2. If not all, then you put and .${\ displaystyle \ alpha _ {1}}$${\ displaystyle b_ {1} = \ lfloor \ alpha _ {1} \ rfloor}$${\ displaystyle \ alpha _ {2} = 1 / (\ alpha _ {1} -b_ {1})}$

This process continues until an integer is obtained (of course this only happens if the starting value is rational). In the case of an irrational one , the process does not break off. The numbers are called full quotients . It applies ${\ displaystyle \ alpha _ {n}}$${\ displaystyle \ alpha}$${\ displaystyle \ alpha _ {n}}$

${\ displaystyle \ alpha = [b_ {0}; b_ {1}, \ dotsc, b_ {n}, \ alpha _ {n + 1}]}$.

Similar to the law of formation for the approximate fractions, one proves:

 ${\ displaystyle \ alpha = {\ frac {p_ {n} \ cdot \ alpha _ {n + 1} + p_ {n-1}} {q_ {n} \ cdot \ alpha _ {n + 1} + q_ { n-1}}}.}$ (4)

Examples: We calculate the continued fraction expansion from to the second digit: ${\ displaystyle \ pi}$

${\ displaystyle \ alpha _ {0} = \ pi \,}$so ,${\ displaystyle b_ {0} = 3 \,}$
${\ displaystyle \ alpha _ {1} = 1 / (\ pi -3) = 7 {,} 0625 \ ldots}$so ,${\ displaystyle b_ {1} = 7 \,}$
${\ displaystyle \ alpha _ {2} = 1/0 {,} 0625 \ ldots = 15 {,} 996 \ ldots}$so .${\ displaystyle b_ {2} = 15 \,}$

So it is . There are more places in the article circle number , but a pattern has not yet been discovered in the regular continued fraction expansion of . ${\ displaystyle [3; 7.15, \ dotsc]}$${\ displaystyle \ pi}$

In contrast, there is a clear pattern in the continued fraction of Euler's number : ${\ displaystyle e}$

${\ displaystyle e = [2; 1,2,1,1,4,1,1,6,1,1,8,1,1,10,1, \ dotsc]}$.

Again, there is no pattern for the third root of : ${\ displaystyle 2}$

${\ displaystyle {\ sqrt [{3}] {2}} = [1; 3,1,5,1,1,4,1,1,8,1,14, \ dotsc]}$

As an example of using Equation (4), consider the successive approximate fractions 17/12 and 41/29 of . ${\ displaystyle {\ sqrt {2}} = [1; {\ overline {2}}]}$

Since the full quotients are equal , the following applies: ${\ displaystyle n> 0}$${\ displaystyle [2; {\ overline {2}}] = 1 + {\ sqrt {2}}}$

${\ displaystyle {\ sqrt {2}} = {\ frac {41 \ cdot (1 + {\ sqrt {2}}) + 17} {29 \ cdot (1 + {\ sqrt {2}}) + 12} }}$

As mentioned in the History section, Euler found that periodic continued fractions (such as the square root of or the golden number) correspond to square irrational numbers, and Lagrange later showed that all of these numbers have periodic continued fractions. The next but one section is dedicated to this topic. ${\ displaystyle 2}$

Equivalent numbers

Two real numbers are called equivalent if there are integers with such that . That is, they are linked to determinants (elements of the special linear group ) by an integer Möbius transformation . It is easy to see that this definition actually provides an equivalence relation on the real numbers: with the reflexivity is shown, with follows the symmetry, and the transitivity can be calculated explicitly. ${\ displaystyle x, y}$${\ displaystyle a, b, c, d}$${\ displaystyle ad-bc = \ pm 1}$${\ displaystyle y = {\ tfrac {ax + b} {cx + d}}}$${\ displaystyle \ pm 1}$${\ displaystyle \ operatorname {SL} (2, \ mathbb {Z})}$${\ displaystyle a = d = 1, b = c = 0}$${\ displaystyle x = {\ tfrac {b-dy} {- a + cy}}}$

Every rational number is equivalent to 0, so all rational numbers form an equivalence class. Therefore, this classification of real numbers is mainly of interest for irrational numbers. The relationship to their regular continued fraction expansions is given by Serret's theorem :

Theorem: Two irrational numbers are equivalent if and only if their continued fraction representations and are such that there are natural numbers and such that applies to all . ${\ displaystyle x, y}$${\ displaystyle x = [u_ {0}; u_ {1}, u_ {2}, \ dotsc]}$${\ displaystyle y = [v_ {0}; v_ {1}, v_ {2}, \ dotsc]}$${\ displaystyle h}$${\ displaystyle k}$${\ displaystyle i \ in \ mathbb {N}}$ ${\ displaystyle u_ {h + i} = v_ {k + i}}$

The correspondence in their continued fraction representations except for a different initial sequence leads to asymptotically equal approximation properties for equivalent numbers. An example is given in the section Theorems about quadratic approximability (Equation 5).

Other infinite continued fractions

In analysis, there are also infinite continued fractions that deviate from the regularity conditions mentioned above, whereby the partial denominators and the partial numerators form sequences of real or complex numbers that meet certain convergence conditions.

In this context, the case is repeatedly dealt with in which all the subscribers (except for the 0th) are the same . A classic example of this is provided by Leonhard Euler 's continued fraction representation of the logarithm of , namely: ${\ displaystyle 1}$${\ displaystyle 2}$

${\ displaystyle \ ln 2 = {\ cfrac {1} {1 + {\ cfrac {1} {1 + {\ cfrac {4} {1 + {\ cfrac {9} {1 + {\ cfrac {16} { 1 + {\ cfrac {25} {1 + {\ cfrac {36} {1 + {\ cfrac {49} {1+ \ dotsb}}}}}}}}}}}}}}}}}}$,

in which the partial counters emerge from the sequence of square numbers from the 2nd .

Periodic continued fractions

Continued fraction of the square root of 13 in Euler's
De usu novi algorithmi in problemate Pelliano solvendo from 1767

In the decimal representation of real numbers, periodic representations correspond to the rational numbers. A distinction is made between purely periodic decimal fractions, e.g. B. , and those with a previous period, such as at . ${\ displaystyle 1/3 = 0, \ mathbf {3} 3333 \ ldots}$${\ displaystyle 1/6 = 0 {,} 1 \ mathbf {6} 666 \ ldots}$

Periodic representations also play a special role in continued fractions. As Euler and Lagrange found, they correspond to the quadratic irrational numbers (irrational solutions of quadratic equations with rational coefficients). In particular, the continued fractions of those real numbers that are neither rational nor quadratic irrational numbers are non-periodic.

A continued fraction is called periodic if there are numbers such that the partial denominators apply to all . The minimum with this property is called the period of the continued fraction, which is then in the form ${\ displaystyle n, k}$${\ displaystyle b_ {j + k} = b_ {j}}$${\ displaystyle j \ geq n + 1}$${\ displaystyle k}$

${\ displaystyle x = [b_ {0}; b_ {1}, \ dotsc, b_ {n}, {\ overline {b_ {n + 1}, \ dotsc, b_ {n + k}}}]}$

is written. If minimal is also chosen, the sequence is called the previous period and its length. ${\ displaystyle n}$${\ displaystyle b_ {0}, \ dotsc, b_ {n}}$${\ displaystyle n + 1}$

Euler-Lagrange theorem

Theorem: Every periodic continued fraction is a quadratic irrational number and vice versa.

The first part of the theorem is easier to prove and comes from Euler, while the converse is more difficult and was only proved later by Lagrange.

Examples

1. Be . Then it holds that is the root of the quadratic equation , from which it follows (since the other zero is negative). Hence the golden number (see also the article golden ratio ).${\ displaystyle x = [1; {\ overline {1}}]}$${\ displaystyle x = 1 + {\ tfrac {1} {x}}}$${\ displaystyle x}$${\ displaystyle x ^ {2} -x-1 = 0}$${\ displaystyle x = {\ tfrac {1 + {\ sqrt {5}}} {2}}}$${\ displaystyle x}$
2. Be . We look at . Then is what and what follows. There must be. Therefore applies .${\ displaystyle x = [1; {\ overline {2}}]}$${\ displaystyle y = x-1}$${\ displaystyle y = {\ tfrac {1} {2 + y}}}$${\ displaystyle y ^ {2} + 2y = 1}$${\ displaystyle y + 1 = \ pm {\ sqrt {2}}}$${\ displaystyle y> 0}$${\ displaystyle y + 1 = {\ sqrt {2}}}$${\ displaystyle x = {\ sqrt {2}}}$
3. Be . We look at . Then is , well , from which and it follows. There must be. Therefore applies .${\ displaystyle x = [1; {\ overline {1,2}}]}$${\ displaystyle y = x-1}$${\ displaystyle y = {\ tfrac {1} {1 + {\ frac {1} {2 + y}}}}}$${\ displaystyle y = {\ tfrac {2 + y} {3 + y}}}$${\ displaystyle y ^ {2} + 2y + 1 = 3}$${\ displaystyle y + 1 = \ pm {\ sqrt {3}}}$${\ displaystyle y> 0}$${\ displaystyle y + 1 = {\ sqrt {3}}}$${\ displaystyle x = {\ sqrt {3}}}$
4. The so-called " noble numbers " have a special form of periodic infinite continued fractions : their continued fraction expansion always ends with . The golden number is probably the most prominent example of a noble number.${\ displaystyle [\ dotsc, {\ overline {1}}]}$
5. The continued fractions of irrational square roots of rational numbers greater than 1 have a special symmetry: For every rational number that is not the square of a rational number, the following applies${\ displaystyle r> 1}$
${\ displaystyle {\ sqrt {r}} = [b_ {0}; {\ overline {b_ {1}, b_ {2}, \ dotsc, b_ {2}, b_ {1}, 2b_ {0}}} ] {\ text {with}} b_ {0}> 0}$
and conversely, the square of every continued fraction of this form is a rational number.
The previous period is always long , the periodic block is symmetrical and ends with . Besides the roots of and, examples are :${\ displaystyle 1}$${\ displaystyle 2b_ {0}}$${\ displaystyle 2}$${\ displaystyle 3}$
${\ displaystyle {\ sqrt {7}} = [2; {\ overline {1,1,1,4}}]}$
${\ displaystyle {\ sqrt {14}} = [3; {\ overline {1,2,1,6}}]}$
The continued fraction of the square root of in a work by Euler on Pell's equation is shown on the right. The golden number from example 1 does not have this shape. Another “against” example of this type is .${\ displaystyle 13}$${\ displaystyle {\ sqrt {3}} + {\ tfrac {1} {2}} = [2; {\ overline {4,3}}]}$

Pell's equation

Periodic continued fractions are used to solve Pell's equation . ${\ displaystyle x ^ {2} -d \ cdot y ^ {2} = \ pm 1}$

Best approximations

Two possibilities of the best approximation

In the introduction it was mentioned that the determination of “good approximate fractions” is an important application of continued fractions. It is true that every approximate fraction of the continued fraction expansion of a real number is a particularly good rational approximation of this number.

Since any irrational number can be approximated with arbitrary precision using rational numbers, there is no absolute best approximation to an irrational number. Instead, a distinction is made between two types of "record approximations":

Definition: A fraction is a best approximation of the first kind for the real number , if for all fractions with and the following applies: ${\ displaystyle a / b}$${\ displaystyle \ alpha}$${\ displaystyle c / d}$${\ displaystyle d \ leq b}$${\ displaystyle a / b \ neq c / d}$

${\ displaystyle \ left | \ alpha - {\ frac {a} {b}} \ right | <\ left | \ alpha - {\ frac {c} {d}} \ right |.}$

You can only get a better approximate fraction if you use larger denominators than allowed. ${\ displaystyle b}$

(For the sake of simplicity, we limit ourselves to positive real numbers and therefore only consider natural numbers as numerators and denominators.) Next: ${\ displaystyle a, b, c, d}$

A fraction is the best approximation of the 2nd kind for the real number , if for all fractions with and the following applies: ${\ displaystyle a / b}$${\ displaystyle \ alpha}$${\ displaystyle c / d}$${\ displaystyle d \ leq b}$${\ displaystyle a / b \ neq c / d}$

${\ displaystyle \ left | b \ cdot \ alpha -a \ right | <\ left | d \ cdot \ alpha -c \ right |}$

Both terms of best approximation are used - depending on the application.

The stronger condition is the second: Suppose there is a fraction with and , then multiplication with yields the inequality . This shows that a fraction that is not a best approximation of the 1st kind cannot be a best approximation of the 2nd kind either. It follows that every kind of best approximation is also a kind of best approximation. ${\ displaystyle c / d}$${\ displaystyle d \ leq b}$${\ displaystyle \ left | \ alpha - {\ tfrac {c} {d}} \ right | \ leq \ left | \ alpha - {\ tfrac {a} {b}} \ right |}$${\ displaystyle d \ leq b}$${\ displaystyle \ left | d \ cdot \ alpha -c \ right | \ leq \ left | b \ cdot \ alpha -a \ right |}$

Example: We consider . The convergents , , loud , and and they make the best approximations second type the full list. However, it is more of best approximations first type, namely and . This topic is covered in the next two sections. ${\ displaystyle 17/10 = [1; 1,2,3]}$${\ displaystyle p_ {1} / q_ {1}}$${\ displaystyle p_ {2} / q_ {2}}$${\ displaystyle p_ {3} / q_ {3}}$${\ displaystyle 2/1}$${\ displaystyle 5/3}$${\ displaystyle 17/10}$${\ displaystyle 3/2}$${\ displaystyle 12/7}$

Approximate fractions are the best approximations

The usefulness of the approximate fractions is shown in the following theorem:

Theorem (Lagrange): For every real number the following applies: Every approximation fraction with is a best approximation of the 2nd kind (and therefore also a best approximation of the 1st kind). ${\ displaystyle p_ {n} / q_ {n}}$${\ displaystyle n> 0}$

This does not always apply to a 0th approximation fraction, because it has, for example, the value , but the integer represents a better approximation with a denominator . ${\ displaystyle 17/10}$${\ displaystyle 1}$${\ displaystyle 2}$${\ displaystyle 1}$

This theorem can be reversed in the case of best approximations of the 2nd kind:

Theorem: Every best approximation of the 2nd type of a real number is an approximate fraction of its (regular) continued fraction expansion.

However, this does not apply to approximations of the first type, as shown in example 17/10 above. One can, however, characterize the additional fractions that occur: They arise as mediants (Farey sums) of approximate fractions and are called secondary approximate fractions . More on this in the next section.

Adjacent approximation fractions in Lagrange's Additions au mémoire sur la résolution des équations numériques from 1770 (page 567)

Example: Suppose you are looking for the smallest natural number for which the distance from from the nearest whole number is less than . Due to the last sentence, the approximate fraction denominator of must be included in the sequence . The first denominator are as already above figured out . Due to the periodic part denominators, these can easily be continued by recursion (a Lucas sequence ) with etc. The approximate fraction is the same and it applies so that the distance is too smaller than the required accuracy. So what you are looking for is the same because the accuracy of for is not reached ( ). ${\ displaystyle q}$${\ displaystyle q \ cdot {\ sqrt {2}}}$${\ displaystyle 1/1000}$${\ displaystyle q}$${\ displaystyle q_ {n}}$${\ displaystyle {\ sqrt {2}} = [1; 2,2, \ dotsc]}$${\ displaystyle 1,2,5,12,29}$${\ displaystyle q_ {n} = 2 \ cdot q_ {n-1} + q_ {n-2}}$${\ displaystyle 70,169,408,985}$${\ displaystyle p_ {7} / q_ {7}}$${\ displaystyle 577/408}$${\ displaystyle 408 \ cdot {\ sqrt {2}} = 576 {,} 99913}$${\ displaystyle 577}$${\ displaystyle q}$${\ displaystyle 408}$${\ displaystyle 1/1000}$${\ displaystyle p_ {6} / q_ {6}}$${\ displaystyle 239/169}$${\ displaystyle 169 \ cdot {\ sqrt {2}} = 239 {,} 00209}$

The same question for the golden number leads to checking for elements of the Fibonacci sequence and the result is what belongs to the approximate fraction . In the case of the circle number , the third approximation fraction ( ) already fulfills this condition. ${\ displaystyle \ phi}$${\ displaystyle f_ {n} \ cdot \ phi}$${\ displaystyle f_ {n}}$${\ displaystyle q = 610}$${\ displaystyle p_ {15} / q_ {15}}$${\ displaystyle \ pi}$${\ displaystyle 355/113}$

Approximation from above and below, approximate fractions

As early as 1770, Lagrange had dealt with the topic of which approximations of the first type occur in addition to the approximation fractions (see figure on the right). He was led to the “fractions secondaires”, which in German are called secondary approximations .

These are mediants of neighboring approximate fractions:

Definition: For two positive fractions , with is the median (or the farey sum ) of the two fractions. The mediant has the easy-to-show property that . ${\ displaystyle a / b}$${\ displaystyle c / d}$${\ displaystyle a / b ${\ displaystyle (a + c) / (b + d)}$${\ displaystyle a / b <(a + c) / (b + d)

Because of this property, the formation of the mediator can be repeated (iterated) and breaks in the form are obtained

${\ displaystyle {\ frac {a + r \ cdot c} {b + r \ cdot d}},}$

which form an ascending sequence. For the following definition of the approximate fractions, iterated medians of adjacent approximate fractions are formed:

Definition: The fractions belonging to a continued fraction

${\ displaystyle {\ frac {p_ {n, r}} {q_ {n, r}}} = {\ frac {r \ cdot p_ {n + 1} + p_ {n}} {r \ cdot q_ {n +1} + q_ {n}}}, \, r = 1, \ dotsc, b_ {n + 2} -1}$

are called approximate fractions. They lie between the -th and the -th approximation fraction. For even numbers they form a rising sequence and for odd numbers a falling sequence. ${\ displaystyle n}$${\ displaystyle (n + 2)}$${\ displaystyle n}$${\ displaystyle n}$

Note: in the special case one uses , and gets a decreasing sequence that is greater than . ${\ displaystyle n = {- 1}}$${\ displaystyle p _ {- 1} = 1}$${\ displaystyle q _ {- 1} = 0}$${\ displaystyle p_ {1} / q_ {1}}$

Theorem (Lagrange 1798): Every best approximation of the first kind of a real number is an approximate fraction or a secondary approximation fraction of its continued fraction expansion.

A characterization of the set of approximate fractions and minor approximate fractions can be obtained as follows:

Theorem (Lagrange 1798): For every real number we have: ${\ displaystyle \ alpha}$

a) Every fraction that lies between and an approximation or an approximation fraction has a larger denominator than this. ${\ displaystyle \ alpha}$

b) Conversely, if a fraction is of the type that every fraction between and has a denominator greater than , then it is an approximate or a minor approximate fraction. ${\ displaystyle a / b}$${\ displaystyle \ alpha}$${\ displaystyle a / b}$${\ displaystyle b}$${\ displaystyle a / b}$

In other words: If one only considers approximating fractions larger than (or conversely smaller than ), the record approximations are completely described by the set of approximate or secondary approximation fractions. ${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$

(Minor) approximation fractions of (explanation in text)${\ displaystyle \ pi}$

In the definition of the best approximation of the first kind, however, the approximations from above and below are considered simultaneously. The analysis of this situation (refinement of the penultimate sentence) shows:

Theorem: Let it be the number of approximate fractions between the -th and the -th approximation fraction. Then the following applies: If even, then the second half of the approximate fractions results in the best approximations of the first type, but the first half does not. The same applies - with the exception of the middle element - if is odd. There is a more complicated condition for the mean fraction that we do not specify here. ${\ displaystyle m = b_ {n + 2} -1}$${\ displaystyle n}$${\ displaystyle (n + 2)}$${\ displaystyle m}$${\ displaystyle m}$

Examples:

a) We consider the simple example . The approximate fractions are , and . In addition to the proximity openings for are , , , (greater than ) and it is the fraction (between and ). ${\ displaystyle [1; 5,2] = 13/11}$${\ displaystyle 1/1}$${\ displaystyle 6/5}$${\ displaystyle 13/11}$${\ displaystyle n = {- 1}}$${\ displaystyle 2/1}$${\ displaystyle 3/2}$${\ displaystyle 4/3}$${\ displaystyle 5/4}$${\ displaystyle 6/5}$${\ displaystyle n = 0}$${\ displaystyle 7/6}$${\ displaystyle 1/1}$${\ displaystyle 13/11}$

b) For the loop number are the first approximation breaks , , and . The side convergents are for the breaks , , , , , . They form a falling sequence and the last three are best approximations of the first kind. (The first three are further away from than the approximate fraction ). For one finds the side convergents , , , , , , , , , , , , , . These fractions form an increasing sequence and the last seven are the best approximations of the first kind. ${\ displaystyle \ pi = [3; 7,15,1,292, \ dotsc]}$${\ displaystyle 3/1}$${\ displaystyle 22/7}$${\ displaystyle 333/106}$${\ displaystyle 355/113}$${\ displaystyle n = {- 1}}$${\ displaystyle 4/1}$${\ displaystyle 7/2}$${\ displaystyle 10/3}$${\ displaystyle 13/4}$${\ displaystyle 16/5}$${\ displaystyle 19/6}$${\ displaystyle \ pi}$${\ displaystyle p_ {0} / q_ {0} = 3/1}$${\ displaystyle n = 0}$${\ displaystyle 25/8}$${\ displaystyle 47/15}$${\ displaystyle 69/22}$${\ displaystyle 91/29}$${\ displaystyle 113/36}$${\ displaystyle 135/43}$${\ displaystyle 157/50}$${\ displaystyle 179/57}$${\ displaystyle 201/64}$${\ displaystyle 223/71}$${\ displaystyle 245/78}$${\ displaystyle 267/85}$${\ displaystyle 289/92}$${\ displaystyle 311/99}$${\ displaystyle 14}$

These (minor) approximate fractions are illustrated in the figure on the right: On the -axis is plotted against on the -axis. In addition to the approximations from below (red) and from above (blue), the graph also contains the limit , the meaning of which will become clear in the next section. It can be clearly seen that only the second half of the approximate fractions provide a better approximation than . You can also see that the approximation through is exceptionally good (reason for this: the next part denominator is very large). ${\ displaystyle y}$${\ displaystyle \ log _ {10} | \ pi -p / q |}$${\ displaystyle q}$${\ displaystyle x}$${\ displaystyle 1 / ({\ sqrt {5}} \ cdot q ^ {2})}$${\ displaystyle n = 0}$${\ displaystyle 22/7}$${\ displaystyle 355/113}$${\ displaystyle 292}$

In this section we present results that lead on to the topic of “ Diophantine approximation ”.

From equation (3) it follows because : For every irrational number there are infinitely many fractions with ${\ displaystyle q_ {n + 1}> q_ {n}}$${\ displaystyle \ alpha}$${\ displaystyle a / b}$

${\ displaystyle \ left | \ alpha - {\ frac {a} {b}} \ right | <{\ frac {1} {b ^ {2}}}.}$

Conversely, for every real number : ${\ displaystyle \ alpha}$

Theorem ( Legendre ): If a fraction satisfies the inequality, then it is an approximate fraction of . ${\ displaystyle a / b}$${\ displaystyle \ left | \ alpha - {\ tfrac {a} {b}} \ right | <{\ tfrac {1} {2b ^ {2}}},}$${\ displaystyle a / b}$${\ displaystyle \ alpha}$

However, this inequality is not satisfied by every approximate fraction. But the following applies:

Theorem ( Vahlen , 1895): Of every two successive approximate fractions of the real number , at least one satisfies the inequality ${\ displaystyle \ alpha}$

${\ displaystyle \ left | \ alpha - {\ frac {p_ {n}} {q_ {n}}} \ right | <{\ frac {1} {2 \, q_ {n} ^ {2}}}. }$

In particular, there are infinitely many fractions with this property for the irrational . ${\ displaystyle \ alpha}$

If you include three approximate fractions in the selection, the following even applies:

Theorem ( Émile Borel , 1903): Of every three consecutive approximate fractions of the real number , at least one satisfies the inequality ${\ displaystyle \ alpha}$

${\ displaystyle \ left | \ alpha - {\ frac {p_ {n}} {q_ {n}}} \ right | <{\ frac {1} {{\ sqrt {5}} \, q_ {n} ^ {2}}}.}$

In particular, for irrational there are infinitely many fractions with this property. ${\ displaystyle \ alpha}$

Given these results, one might suspect that the condition can be further exacerbated by including four or more consecutive approximate fractions. But this is not the case:

Theorem ( Hurwitz , 1891, see also theorem of Hurwitz ): Be the golden number . Then for every real number with there are only a finite number of fractions with ${\ displaystyle \ phi = [1; 1, \ dotsc]}$${\ displaystyle c}$${\ displaystyle c> {\ sqrt {5}}}$${\ displaystyle a / b}$

${\ displaystyle \ left | \ phi - {\ frac {a} {b}} \ right | <{\ frac {1} {c \ b ^ {2}}}.}$

A tightening can only be achieved if one excludes the numbers that are too equivalent: ${\ displaystyle \ phi}$

Theorem (Hurwitz, 1891): For all irrational numbers that are not equivalent to , there are infinitely many fractions with ${\ displaystyle \ alpha}$${\ displaystyle \ phi}$${\ displaystyle a / b}$

 ${\ displaystyle \ left | \ alpha - {\ frac {a} {b}} \ right | <{\ frac {1} {{\ sqrt {8}} b ^ {2}}}.}$ (5)

The constant can be increased further by excluding equivalence classes . The resulting values form the so-called Lagrange spectrum. They converge to the number 3 and are related to the Markoff numbers . ${\ displaystyle c}$${\ displaystyle c}$

Properties of almost all irrational numbers

Examples of apparent, but so far not proven, convergence to the Chinchin constant,
red: (
circle number ), blue: ( Euler-Mascheroni constant ), green: ∛2 (cube root of 2). Black line: Chinchin constant${\ displaystyle \ pi}$
${\ displaystyle \ gamma}$

Evidently no convergence to the Chinchin constant,
red: (
Euler's number ), blue: √2 ( root 2 ), green: √3 ( root 3 ). Black line: Chinchin constant${\ displaystyle e}$

Chinchin constant

The so-called metric continued fraction theory deals with properties that typical real numbers have. It goes back to the article of the same name by Alexander Chintschin in the journal Compositio Mathematica from 1935, but Gauss also dealt with similar topics. Typical here is to be understood in the sense of the theory of measure: One formulates properties which, apart from a zero set , have all real numbers. In this case it is said that almost all real numbers have this property.

The result of Chinchin is: For almost all real numbers, for converges to the constant ${\ displaystyle \ textstyle {\ sqrt [{n}] {b_ {1} b_ {2} \ cdots b_ {n}}}}$${\ displaystyle n \ to \ infty}$

${\ displaystyle \ prod _ {r = 1} ^ {\ infty} \ left (1 + {\ frac {1} {r (r + 2)}} \ right) ^ {\ log _ {2} r} = 2 {,} 685452001 \ \ dots}$   (Follow A002210 in OEIS ).

The geometric mean of the partial denominators of almost every real number converges to a fixed constant. All rational numbers belong to the exceptions, since they only have a finite number of partial denominators - but they also only form a zero set of real numbers.

It is not known whether this so-called Chinchin constant is rational, algebraically irrational or transcendent.

The continued fraction expansions of numbers for which the limit value does not exist or is not equal to the Chinchin constant are usually particularly regular. This applies to real solutions of quadratic equations (periodic continued fraction expansion, e.g. the square root of ), Euler's number (pattern was mentioned above) and e.g. all numbers of the form or ( ). ${\ displaystyle 2}$${\ displaystyle e}$${\ displaystyle e ^ {1 / n}}$${\ displaystyle e ^ {2 / n}}$${\ displaystyle n \ in \ mathbb {N}}$

On the right are diagrams for the graphs of the function for three examples each. ${\ displaystyle \ textstyle n \ mapsto {\ sqrt [{n}] {b_ {1} b_ {2} \ cdots b_ {n}}}}$

Comparison of continued fraction representation and decimal representation

The von Lochs theorem says the following: For almost every real number between and one gets in the long run for every further link of a continued fraction -many valid decimal places . This means that the representation with continued fractions (for almost all numbers) is only slightly more efficient than the decimal representation. The Lochs constant is related to the Lévy constant (it is twice the logarithm of ten of the Lévy constant). ${\ displaystyle 0}$${\ displaystyle 1}$${\ displaystyle {\ tfrac {\ pi ^ {2}} {6 \ ln 2 \ ln 10}} \ approx 1 {,} 03064}$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ sqrt [{n}] {q_ {n}}} = e ^ {\ frac {\ pi ^ {2}} {12 \ ln 2}}}$

Related areas in number theory:

literature

• S. Astels: Linear fractional transformations and nonlinear leaping convergents of some continued fractions. In: springer.com. January 29, 2020, accessed on June 16, 2020 .
• Julian Rodemann: Number theory: murderer Christopher Havens solves math problem. In: Süddeutsche Zeitung . June 12, 2020, accessed June 16, 2020 .
• Jörg Arndt, Christoph Haenel: Π [Pi] . Algorithms, computers, arithmetic. 2nd, revised and expanded edition. Springer Verlag, Berlin, Heidelberg 2000, ISBN 3-540-66258-8 , pp. 64-68 .
• Claude Brezinski: History of Continued Fractions and Padé Approximants. Springer, Berlin 1991.
• Peter Bundschuh : Introduction to Number Theory. 6th edition. Springer, Berlin / Heidelberg 2008, ISBN 978-3-540-76490-8 .
• Alexander J. Chintschin : Continued Fractions. Teubner, Leipzig 1956, or Continued Fractions. Dover Publications, 1997 (Russian original 1935).
• Annie Cuyt, Vigdis Brevik Petersen, Brigitte Verdonk, Haakon Waadeland, William B. Jones: Handbook of Continued Fractions for Special Functions . With contributions by Franky Backeljauw, Catherine Bonan-Hamada. Verified numerical output: Stefan Becuwe, Annie Cuyt. Springer Verlag, Dordrecht 2008, ISBN 978-1-4020-6948-2 .
• Leonhard Euler: Introduction to the Analysis of the Infinite . Springer Verlag, Berlin / Heidelberg / New York 1983, ISBN 3-540-12218-4 (first part of the Introductio in Analysin Infinitorum - reprint of the Berlin 1885 edition).
• GH Hardy , EM Wright : An introduction to the theory of numbers. Oxford University Press, 2005 (1st edition 1938).
• Peter Henrici : Applied and Computational Complex Analysis. Volume 2, Wiley, 1991.
• Doug Hensley : Continued fractions. World Scientific, 2006.
• William B. Jones, WJ Throne: Continued Fractions. Analytic Theory and Applications. Cambridge University Press, 2009.
• Oleg Karpenkov: Geometry of Continued Fractions (=  Algorithms and Computation in Mathematics . Volume 26 ). Springer Verlag, Heidelberg, New York, Dordrecht, London 2013, ISBN 978-3-642-39367-9 , doi : 10.1007 / 978-3-642-39368-6 .
• Carl Knochendöppel: From the continued fractions and the Diophantine equations. Volk und Wissen publishing house, Berlin / Leipzig 1948.
• AN Khovanskii: The application of continued fractions and their generalizations to problems in approximation theory. Noordhoff, Groningen 1963 (Russian original 1956).
• Lisa Lorentzen, Haakon Waadeland: Continued fractions with applications (Studies in Computational Mathematics 3). North Holland, 1992.
• Heinz Lüneburg : About numbers and sizes. Three and a half thousand years of theory and practice. 2 volumes, Birkhäuser, Basel 2008.
• Hartmut Menzer: Number Theory . Five selected topics in number theory. Oldenbourg Verlag, Munich 2010, ISBN 978-3-486-59674-8 , p. 134-165 .
• Ivan M. Niven , Herbert S. Zuckerman: Introduction to Number Theory. 2 volumes, Bibliographisches Institut, Mannheim 1976 (English original: Wiley, 1960).
• Carl Douglas Olds : Continued fractions. (New Mathematical Library 9) Mathematical Association of America, 1963.
• Oskar Perron: The theory of continued fractions. 1st edition in one volume. Teubner, 1913, archive.org . 2nd edition 1929, 3rd edition in two volumes, Volume 1: Elementary Chain Fractions. 1954, Volume 2: Analytical-function-theoretical continued fractions. 1957.
• Oskar Perron: Irrational Numbers. Göschen's teaching library, volume 1. Walter de Gruyter, Berlin / Leipzig 1921, archive.org . 2nd edition 1939, 3rd edition 1947.
• Andrew M. Rockett, Peter Szüsz: Continued fractions. World Scientific, 1992.
• Asmus L. Schmidt : Complex continued fractions .
• Benedikt Sporer: Lower Analysis. 2nd Edition. Göschensche Verlagshandlung, Berlin / Leipzig, 1917.
• Hubert Stanley Wall: Analytic theory of continued fractions. Van Nostrand, New York 1948.

Commons : Continued fraction  - collection of images, videos, and audio files

Individual evidence

1. Oskar Perron speaks of "regular chain fractions". The designation of the regular continued fractions as "simple continued fractions" ( English simple continued fractions ) is due not least to Carl Douglas Olds' monograph back from the 1963rd See Arndt / Haenel: Pi , 2000, p. 65!
2. Oskar Perron systematically deals with other classes of continued fractions.
3. For use in cryptography see z. B. the book "Solving the Pell Equation" by M. Jacobson and Hugh C. Williams and on algebraic geometry the article The geometry of continued fractions and the topology of surface singularities by Patrick Popescu-Pampu, math.univ-lille1.fr ( PDF; 676 kB), in which the geometric representation by HJS Smith (1876) and Felix Klein (1895) and the Hirzebruch - Jung chain breaks are explained (these are similar to regular continued fractions, with subtraction being used here instead of addition. The fraction is written , for example, as .) For application in function theory see the book by HS Wall and for chaotic systems the website by John D. Barrow , Chaos in Numberland .${\ displaystyle 5/3}$${\ displaystyle 2-1 / 3}$
4. That this continued fraction is equal to the square root of 2 is shown in the section Periodic Continued Fractions.
5. Lambert's continued fraction representation of the tangent function, see Ebbinghaus u. a .: Numbers. 3rd edition, Springer, 1992, p. 122.
6. ↑ Specifying the relative error does not make sense here, since the approximation properties of a number do not change by adding whole numbers.
7. ^ Leonhard Euler and Chr. Goldbach, Correspondence.
8. ^ André Weil : Number Theory . Birkhäuser Verlag, Boston 1984, ISBN 0-8176-4565-9 .
9. Winfried Scharlau , Hans Opolka: From Fermat to Minkowski . Springer, 1980, ISBN 3-540-10086-5 .
10. Moritz Abraham Stern : Theory of continued fractions and their application . In: Journal for pure and applied mathematics . Volume 1833, Issue 10, 1833, pp. 1-22 , doi : 10.1515 / crll.1833.10.1 . There is also a summary of several articles in this journal in book form from 1834.
11. In older literature and are often interchanged so that the participants are named.${\ displaystyle a_ {i}}$${\ displaystyle b_ {i}}$${\ displaystyle a_ {i}}$
12. Oskar Perron: The doctrine of the continued fractions. Volume I: Elementary Continued Fractions . Scientific Book Society, Darmstadt 1977, p. 1 .
13. ↑ In addition to the spellings given here, there are (e.g. in Conway , Guy : The book of numbers. Springer, 1996), (e.g. in the book by Niven / Zuckerman) and (e.g. in Donald Knuth : The Art of Computer Programming . (Volume 2), Addison-Wesley, 1997).${\ displaystyle b_ {0} + {\ tfrac {1} {b_ {1} + {}}} {\ tfrac {1} {b_ {2} + {}}} {\ tfrac {1} {b_ {3 } + {}}} \ cdots}$${\ displaystyle \ langle b_ {0}, b_ {1}, b_ {2}, b_ {3}, \ dotsc \ rangle}$${\ displaystyle b_ {0} + / \! / b_ {1}, b_ {2}, b_ {3}, \ dotsc / \! /}$
14. See Alf van der Poorten : Symmetry and folding of continued fractions. Journal de Théorie des Nombres de Bordeaux 14 (2), 603-611 (2002).
15. For a current use of this illustration, see Dusa McDuff : Symplectic embeddings and continued fractions: a survey. Japanese Journal of Mathematics, 4 (2), 2009.
16. That would not be the case, for example, if any positive real numbers were allowed as part denominators. In this case, the following applies: The continued fraction converges exactly when the sum diverges.${\ displaystyle [b_ {0}; b_ {1}, \ dotsc]}$${\ displaystyle \ textstyle \ sum _ {i = 0} ^ {\ infty} b_ {i}}$
17. A. Hurwitz: About the approximate representation of irrational numbers through rational fractions. In: Mathematical Annals. Volume 39, 1891, p. 284.See also Hardy / Wright, Chapter 10.11.
18. See Perron (1929), chapter 2, sentence 23 (page 63).
19. See for example article Pringsheim's convergence criterion !
20. A detailed treatment of this topic was given in particular by Oskar Perron in Volume II of his Theory of Continued Fractions .
21. Leonhard Euler: Introduction to the Analysis of the Infinite . Springer Verlag, 1983, p. 302 .
22. ^ Joseph-Louis Lagrange: Additions au mémoire sur la résolution des équations numériques. Uvres complètes, tome 2, 581–652 (1770).
23. See Perron (1913), Chapter 3, Sentence 9  - Internet Archive .
24. For the source see Euler's De usu novi algorithmi in problemate Pelliano solvendo. At the bottom you can also see the number . The continued fraction expansion of its square root has a period : and Euler calculates it as the next example. A few pages later there is a complete list of periodic continued fractions for up to 120.${\ displaystyle 61}$${\ displaystyle 11}$${\ displaystyle {\ sqrt {61}} = [7; {\ overline {1,4,3,1,2,2,1,3,4,1,14}}]}$${\ displaystyle d}$
25. See Chintschin, sentence 17.
26. There is still an exceptional case for rational numbers , but it can be avoided if you only allow continued fractions whose last partial denominator is greater than . It is about . These can be written as or as . In the latter case, and this approximate fraction has the same distance to as the 0th approximate fraction . See Hardy and Wright, p. 194.${\ displaystyle \ alpha}$${\ displaystyle 1}$${\ displaystyle \ alpha = b_ {0} +1/2}$${\ displaystyle [b_ {0}; 2]}$${\ displaystyle [b_ {0}; 1,1]}$${\ displaystyle p_ {1} / q_ {1} = b_ {0} +1}$${\ displaystyle \ alpha}$${\ displaystyle b_ {0}}$
27. See Chintschin, sentence 16.
28. See Chintschin, sentence 15.
29. See Perron (1913), Chapter 2, sentences 20 and 21.
30. See for example the exercises to chapter 7.5 in the book by Niven / Zuckerman.
31. See Perron (1913), chapter 2, sentence 22.
32. Formulated more precisely, one would of course have to say that the graph also contains the logarithm of this bound.
33. See also the similar statement in the article Dirichletscher Approximation Theorem .
34. Legendre: Essai sur la théorie des nombres. 1798. In the edition of 1808 the proof can be found on page 21.
35. See Perron (1913), chapter 2, sentence 14.
36. See Perron (1913), chapter 2, sentence 15.
37. For proof, see for example Albrecht Beutelspacher , Bernhard Petri: The Golden Section. Bibliographical Institute 1989, p. 99.
38. Hurwitz , 1891, Mathematische Annalen 39 , About the approximate representation of the irrational numbers by rational fractions. Pp. 279-284.
39. See Michel Waldschmidt: Introduction to Diophantine methods irrationality and trancendence. (PDF; 700 kB), pages 24–26.
40. A. Khintchine : Metric continued fraction problems . (March 29, 1934), Compositio Mathematica 1, 1935, pp. 361-382.
41. The Gauss-Kuzmin the probability distribution of the partial denominator concerns of real numbers ( RO Kuzmin , 1928, also Paul Lévy , 1929). The following applies to all natural numbers : The measure of converges for against . For the limit value is about 41%, for about 17%. See the book by Chintschin.${\ displaystyle k}$${\ displaystyle M_ {n} (k) = \ {x \ in [0,1] \ mid n {\ text {-th partial denominator of}} x {\ text {is equal to}} k \}}$${\ displaystyle n \ to \ infty}$${\ displaystyle - \ log _ {2} \ left [1 - {\ tfrac {1} {(k + 1) ^ {2}}} \ right]}$${\ displaystyle k = 1}$${\ displaystyle k = 2}$
 This version was added to the list of articles worth reading on April 13, 2010 .