Continued Fractions

 

Definition and Background

A continued fraction is a representation of a number \(x\) in the form \[ x=a_0+\cfrac{b_0}{a_1+\cfrac{b_1}{a_2+\cfrac{b_2}{a_3+\cfrac{b_3}{\ddots}}}} \] Often, the b's are taken to be all 1's and the a's are integers. This is called the canonical or simple form. There are numerous ways of representing continued fractions. For instance, \[ x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\ddots}}}} \] can be represented as \[ x=a_0+\overset{\infty}{\underset{k=1}{\mathrm{K}}}\frac{1}{a_k} \] Or as \[ \left [ a_0;a_1,a_2,a_3,... \right] \]

Construction Algorithm

The continued fraction terms can be determined as follows: Given \(x\), set \(x_0=x\). Then \[ a_k=\left \lfloor x_k \right \rfloor \] \[ x_{k+1}=\frac{1}{x_k-a_k} \] Continue until \(x_k=a_k\).

Convergents

The convergents of a continued fraction are the rational numbers resulting from taking the first n terms of the continued fraction. Let \(P_n\) and \(Q_n\) be the numerators and deominators respectively of the nth convergent (the one that includes \(a_n\)). It is not difficult to show that \[ P_n=a_nP_{n-1}+P_{n-2} \] \[ Q_n=a_nQ_{n-1}+Q_{n-2} \] An alternate way of saying this is that \[ \begin{bmatrix} a_n & 1\\ 1 & 0 \end{bmatrix} \begin{bmatrix} P_{n-1} & Q_{n-1}\\ P_{n-2} & Q_{n-2} \end{bmatrix} = \begin{bmatrix} P_{n} & Q_{n}\\ P_{n-1} & Q_{n-1} \end{bmatrix} \] Where \[ \begin{bmatrix} P_{-1} & Q_{-1}\\ P_{-2} & Q_{-2} \end{bmatrix}= \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} \] And therefore \[ {}^L\prod^n_{k=0} \begin{bmatrix} a_k & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} P_{n} & Q_{n}\\ P_{n-1} & Q_{n-1} \end{bmatrix} \] Let \[p_n=\frac{P_n}{P_{n-1}}\] \[q_n=\frac{Q_n}{Q_{n-1}}\] Then \[p_n=a_n+\frac{1}{p_{n-1}}\] \[q_n=a_n+\frac{1}{q_{n-1}}\] We find that \[ \frac{P_{n+1}}{Q_{n+1}}=a_0+\sum_{k=0}^{n}\frac{(-1)^k}{Q_kQ_{k+1}} \] And thus \[ \left | x- \frac{P_{n}}{Q_{n}}\right |<\frac{1}{Q_nQ_{n+1}} \] As \(a_n \geq 1\), \(Q_n \geq F_n\) i.e. the nth Fibonacci number. This, then, implies Hurwitz's theorem: For any irrational number x, there exist infinitely many ratios \(P/Q\) such that \[ \left | x-\frac{P}{Q} \right |<\frac{k}{Q^2} \] Only if \(k \geq 1/\sqrt{5}\).

Periodic Continued Fractions

Suppose that for \(k \geq N\), \(a_{k+M}=a_k\). Let \[ [a_0;a_1,a_2,...a_{N-2}]=\frac{P_{Y1}}{Q_{Y1}} \] \[ [a_0;a_1,a_2,...a_{N-1}]=\frac{P_{Y2}}{Q_{Y2}} \] \[ \left [a_N;a_1,a_2,...a_{N+M-2} \right ]=\frac{P_{Z1}}{Q_{Z1}} \] \[ \left [a_N;a_1,a_2,...a_{N+M-1} \right ]=\frac{P_{Z2}}{Q_{Z2}} \] Then x satisfies the formula \[ x=\frac{P_{Y2}\cdot y+P_{Y1}}{Q_{Y2} \cdot y+Q_{Y1}} \] Where y satisfies \[ y=\frac{P_{Z2}\cdot y+P_{Z1}}{Q_{Z2} \cdot y+Q_{Z1}} \] Thus a continued fraction will be eventually periodic if and only if it is the solution of some quadratic polynomial.

Generic Continued Fractions

Let x be uniformly chosen between 0 and 1. We define a sequence of random variables as follows \[ \xi_0=x \] \[ \xi_{n+1}=\frac{1}{\xi_n}-\left \lfloor \frac{1}{\xi_n} \right \rfloor \] Clearly, if \[x=[0;a_1,a_2,a_3,...] \] Then \[\xi_n=[0;a_{n+1},a_{n+2},a_{n+3},...]\] Let us assume that, asymptotically, the \(\xi\)'s approach a single distribution. Based on our definitions, this would imply that \[ P(\xi_{n+1} < z)=\sum_{k=1}^{\infty} P \left (\frac{1}{k} < \xi_n < \frac{1}{k+z} \right ) \] Differentiating both sides gives the required relationship: \[ f_\xi(z)=\sum_{k=1}^{\infty}\frac{f_\xi\left ( \tfrac{1}{k+z} \right )}{(k+z)^2} \] Let us test the function \[ f_\xi(z)=\frac{A}{1+z} \] \[ \sum_{k=1}^{\infty}\frac{A}{1+\tfrac{1}{k+z}}\frac{1}{(k+z)^2}=\sum_{k=1}^{\infty}\frac{1}{(1+k+z)(k+z)} \] \[ \sum_{k=1}^{\infty}\frac{1}{(1+k+z)(k+z)}=\sum_{k=1}^{\infty}\frac{1}{k+z}-\frac{1}{k+z+1}=\frac{A}{1+z} \] It can be proved more rigorously that this is indeed the asymptotic probability density function, with \(A=1/\ln(2)\). Thus \[ P(\xi_{n} < z)=\log_2(1+z) \] From this we can easily find the asymptotic density function for the continued fraction terms. The probability that \(a_{n+1}=k\) is the same as the probability that \(\left \lfloor \tfrac{1}{\xi_n} \right \rfloor=k\). This is then \[ P(a_{n+1}=k)=P\left ( \frac{1}{k+1} < \xi_n \leq \frac{1}{k} \right )=\log_2(1+\tfrac{1}{k})-\log_2(1+\tfrac{1}{k+1}) \] \[ P(a_{n+1}=k)=\log_2\left ( \frac{(k+1)^2}{k(k+2)} \right )=\log_2\left ( 1+\frac{1}{k(k+2)} \right ) \] This is called the Gauss-Kuzmin Distribution.

From this we can then easily find the asymptotic geometric mean of the terms \[ \underset{n \to \infty}{\lim}\sqrt[n]{\prod_{k=1}^{n}a_k}=\exp\left (\underset{n \to \infty}{\lim} \frac{1}{n}\sum_{k=1}^{\infty} \ln(a_k)\right )=\exp\left ( E(\ln(a_k)) \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{\prod_{k=1}^{n}a_k}= \exp\left (\sum_{j=1}^{\infty}P(a_k=j)\ln(j) \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{\prod_{k=1}^{n}a_k}= \prod_{j=1}^\infty \left ( 1+\frac{1}{j(j+2)} \right )^{\log_2(j)}=2.685452001...=K_0 \] This value is called Khinchin's Constant.

Let us now look at the asymptotic behavior of the convergents. Namely, we wish to examine the asymptotic behavior of the denominators. First note that \[ \xi_n=\frac{1}{\xi_{n-1}}-a_n \] If we let \(y_n=1/\xi_n\), we then have \[ y_{n-1}=a_n+\frac{1}{y_n} \] From above we have that \[q_n=a_n+\frac{1}{q_{n-1}}\] As, asymptotically, \(\xi_n \sim \xi_{n-1}\), this implies that, asymptotically, \(y_n \sim y_{n-1} \sim 1/\xi_n\) and therefore \(q_n \sim q_{n-1} \sim 1/\xi_n\). Thus \[ f_q(z)=\left\{\begin{matrix} \frac{1}{z^2}\frac{1}{\ln(2)}\frac{1}{1+1/z} \\ 0 \end{matrix}\right.\; \; \begin{matrix} z > 1 \\ z \leq 1 \end{matrix} \] As \[ Q_n=\prod_{k=1}^{n}q_k \] We have \[ \underset{n \to \infty}{\lim}\sqrt[n]{Q_n}=\underset{n \to \infty}{\lim}\sqrt[n]{\prod_{k=1}^{n}q_k}=\exp\left (\underset{n \to \infty}{\lim}\frac{1}{n}\sum_{k=1}^{\infty}\ln(q_k) \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{Q_n}=\exp\left (E(\ln(q_n)) \right )= \exp\left (\int_{1}^{\infty}\ln(z)\frac{1}{z^2}\frac{1}{\ln(2)}\frac{1}{1+1/z}dz \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{Q_n}= \exp\left (-\frac{1}{\ln(2)}\int_{0}^{1}\frac{\ln(z)}{1+z}dz \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{Q_n}=\exp\left ( \frac{\pi^2}{12\ln(2)} \right )=3.275823... \] This value (or sometimes its natural log) is called Levy's constant.

We want to know how efficient continued fractions are for representing numbers relative to place-value expansions. Suppose we are working in base b. We want to find how many terms in the continued fraction expansion are required to obtain an approximation good to m base-b digits. We will have obtained such an approximation when the error is less than \(b^{-m}\) but greater than \(b^{-(m+1)}\). From above we have \[ \left | x- \frac{P_{n}}{Q_{n}}\right |<\frac{1}{Q_nQ_{n+1}} \] Thus \[ b^{-(m+1)} < \left | x- \frac{P_{n}}{Q_{n}}\right | < \frac{1}{Q_nQ_{n+1}} < \frac{1}{Q_n^2} \leq b^{-m} \] Rearranging, we have \[ b^m \leq Q_n^2 < b^{m+1} \] \[ b^{\frac{m}{2n}} \leq \sqrt[n]{Q_n} < b^{\frac{m+1}{2n}} \] Thus, as the center expression approaches a limit for large n, it follows that \(m/n\) does as well. Namely, by rearranging, we find that for n the number of continued fraction terms needed to express x in base b up to m decimal places, \[ \underset{m,n \to \infty}{\lim}\frac{m}{n}=\frac{\pi^2}{6\ln(2)\ln(b)} \] This is known as Loch's Theorem. In particular, for base 10, this implies that each continued fraction term provides on average 1.03064... digits of precision. In fact, base 10 is the largest integral base for which the continued fraction is more efficient.