Continued fraction

Let $x=[a_0,a_1,a_2,\cdots]$ be a real number. Then the following properties hold:

1. For any $k\in\mathbf Z$, $x+k=[a_0+k,a_1,a_2,\cdots]$;
2. For a real number $x>1$, $a_0>0$, and its reciprocal is $x^{-1}=[0,a_0,a_1,a_2,\cdots]$.

For a continued fraction $x=[a_0,a_1,a_2,\cdots]$, suppose its $k$-th convergent $x_k$ can be written as the fraction $\dfrac{p_k}{q_k}$. Then

The recurrence starts from the (formal) fractions

The numerator and denominator of the convergent $x_k$ can be viewed as multivariate polynomials in $a_0, a_1, \cdots, a_k$:

By the definition of a convergent,

Comparing this with the preceding expression, set $Q_k(a_0, \cdots, a_k) = P_{k-1}(a_1, \cdots, a_k)$ without loss of generality. Then the convergent can be written as

and the polynomial $P_k$ satisfies the recurrence

Since

the starting values are

If we set

it can be verified that the recurrence also holds for $k=0,1$. This is equivalent to defining the formal fractions $r_{-1}=\dfrac{1}{0}$ and $r_{-2}=\dfrac{0}{1}$.

The polynomial sequence $P_k$ satisfying the recurrence above is called the continuant². It can be written in determinant form:

This is the determinant of a tridiagonal matrix. Expanding from the upper-left corner verifies that it satisfies the recurrence and initial conditions above. Conversely, expanding from the lower-right corner gives the recurrence

which is what we needed to prove.

Suppose the real number $x=[a_0,a_1,a_2,\cdots]$ has a convergent with index $k$, namely $\dfrac{p_k}{q_k}$. Then the ratios of the numerators and denominators of two adjacent convergents are respectively

If $a_0=0$=0, interpret the first continued fraction as truncated at the penultimate term, namely $[a_k,a_{k-1},\cdots,a_2]$.

Dividing the two sides of the recurrences for $p_k$ and $q_k$ by $p_{k-1}$ and $q_{k-1}$ respectively gives

Iterating these two equations gives two continued fractions. Substituting the initial values $\dfrac{p_0}{p_{-1}}=a_0$ and $\dfrac{q_1}{q_0}=a_1$ completes the result. When $a_0=0$, interpret the resulting continued fraction as a formal expression; its remainder is

Thus, the last two terms can be omitted directly. For a rigorous proof, simply observe that this expression can be regarded as the limit as $a_0\rightarrow 0$.

The reciprocal of a convergent of a real number $x>0$ is a convergent of $x^{-1}$.

Without loss of generality, let $x>1$ and let its continued fraction representation be $[a_0,a_1,a_2,\cdots]$. Then the continued fraction representation of $x^{-1}$ is $[0,a_0,a_1,a_2,\cdots]$. Their convergents can be obtained from the recurrence. For $x$, the initial conditions are $x_{-2}=\dfrac{0}{1}$ and $x_{-1}=\dfrac{1}{0}$; for $y=x^{-1}$, the initial conditions are $y_{-1}=\dfrac{1}{0}$ and $y_{0}=\dfrac{0}{1}$. Therefore, $x_{-2}=(y_{-1})^{-1}$ and $x_{-1}=(y_0)^{-1}$. The recurrence gives $x_k=y_{k+1}^{-1}$. This shows that the reciprocals of the convergents of $x$ are convergents of $y=x^{-1}$. The case $0<x\le 1$ can be discussed similarly.

Let $x_k=\dfrac{p_k}{q_k}$ be a convergent of the real number $x$ with index $k$. Then

Therefore, the difference between two adjacent convergents is

By the recurrence,

This is exactly $p_{k+1}q_k − p_kq_{k+1} = (−1)^k$. Dividing both sides by $q_{k+1}q_k$ gives the result for $x_{k+1}-x_k$.

Let $x_k=\dfrac{p_k}{q_k}\neq x$ be the convergent of the real number $x$ with index $k$. Then

Here $r_{k+1}$ is the remainder of the real number $x$ with index $k+1$. Consequently,

Since $x=[a_0,a_1,\cdots,a_k,r_{k+1}]$, and the difference formula for convergents also holds for formal continued fractions, we have

where $r_{k+1}q_k+q_{k-1}$ is the denominator of the $k+1$-th convergent of this formal continued fraction obtained from the recurrence.

To complete the following inequality estimate, we only need to note that when $x_k\neq x$, we always have

so

Therefore,

To obtain the outer bounds, also note that $q_k\le q_{k+1}$.

For any real number $x$, if the numerator and denominator of the convergent $x_k=\dfrac{p_k}{q_k}$ are given by the recurrence, then $\dfrac{p_k}{q_k}$ is a reduced fraction, that is, $\gcd(p_k,q_k)=1$.

Apply Bézout's identity to the difference formula.

Although this problem is usually solved using the extended Euclidean algorithm, it can also be solved using continued fractions.

Suppose that $\dfrac{A}{B}=[a_0, a_1, \cdots, a_k]$. We proved above that $p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}$. Replacing $p_k$ and $q_k$ with $A$ and $B$ gives

where $g = \gcd(A, B)$. If $g$ divides $C$, one solution is $x = (-1)^{k-1}\dfrac{C}{g} q_{k-1}$ and $y = (-1)^{k}\dfrac{C}{g} p_{k-1}$; otherwise, there is no solution.

C++

// Return (x,y) such that Ax+By=C.
// Assume that such (x,y) exists.
auto dio(int A, int B, int C) {
  std::vector<int> p, q;
  std::tie(p, q) = convergents(fraction(A, B));
  C /= A / p.back();
  int t = p.size() % 2 ? -1 : 1;
  return std::make_pair(t * C * q.end()[-2], -t * C * p.end()[-2]);
}

Python

# Return (x, y) such that Ax+By=C.
# Assume that such (x, y) exists.
def dio(A, B, C):
    p, q = convergents(fraction(A, B))
    C //= A // p[-1]  # divide by gcd(A, B)
    t = (-1) if len(p) % 2 else 1
    return t * C * q[-2], -t * C * p[-2]

For an irrational number $x$, there exist infinitely many reduced fractions $\dfrac{p}{q}$ such that

holds.

By the error estimate for convergents, for an irrational number $x$, the convergent with index $k$, $x_k=\dfrac{p_k}{q_k}$ satisfies

Checking the proof of the error formula shows that equality cannot hold for any irrational number $x$. Therefore, the numerators and denominators of all its convergents satisfy the requirement.

For an irrational number $x$, there exist infinitely many reduced fractions $\dfrac{p}{q}$ such that

holds, and the $\sqrt{5}$ on the right-hand side cannot be replaced by a larger real number.

Borel actually proved that among any three consecutive convergents of an irrational number $x$, at least one necessarily satisfies the condition above. Since there are infinitely many convergents and all are reduced fractions, the first part of Hurwitz's theorem follows.

We argue by contradiction. Suppose that there is an irrational number $x$ and three of its convergents $x_{k-1},x_k,x_{k+1}$ such that

hold. Since adjacent convergents must lie on opposite sides of $x$, the difference formula gives

This can be written as an inequality for the quotient $\dfrac{q_{k}}{q_{k-1}}$:

The left-hand side is rational and the right-hand side is irrational, so equality cannot hold. Since $q_k\ge q_{k-1}$, we obtain

Similarly, we can prove

However, by the recurrence and the two inequalities, we have

This contradicts the definition of a simple continued fraction. Hence Borel's conclusion holds.

To show that this bound is the best possible, it suffices to find an $x$ such that for every $C>\sqrt{5}$, only finitely many reduced fractions $\dfrac{p}{q}$ satisfy

We now prove that $\phi=\dfrac{\sqrt{5}+1}{2}$ is such an $x$.³

Let $\phi'=\dfrac{-\sqrt{5}+1}{2}$ be the conjugate root of $\phi$. Both are roots of the equation $x^2-x-1=0$. Thus, for every real number $x$,

Substituting the reduced fraction $\dfrac{p}{q}$ gives

For $C>\sqrt{5}$, we can directly solve for $q<\sqrt{C(C-\sqrt{5})}$, so there cannot be infinitely many solutions satisfying the inequality above.

Every first-kind best approximation is an intermediate fraction.

Since $a_0\le x\le a_0+1$, a first-kind best approximation must lie between $x_{1,0}=a_0$ and $x_{0,1}=a_0+1$. All intermediate fractions can be ordered from small to large as

Intermediate fractions of the same order occur consecutively, and there are no gaps between intermediate fractions of different orders. This means that any rational number lying between $x_{1,0}=a_0$ and $x_{0,1}=a_0+1$, namely $\dfrac{p}{q}$ must lie between two intermediate fractions $x_{k,t}$ and $x_{k,t+1}$ of the same order. Suppose without loss of generality that it is not an intermediate fraction and is smaller than $x$, so

On the one hand,

On the other hand,

Therefore,

In other words, the denominator of the rational number $\dfrac{p}{q}$ is larger than the denominator of $x_{k,t+1}$, but it is not a better approximation:

Therefore, it cannot be a first-kind best approximation. This shows that a fraction that is not an intermediate fraction cannot be a first-kind best approximation; equivalently, every first-kind best approximation is an intermediate fraction.

Every convergent is a first-kind best approximation. In addition, let $0<t<a_{k+1}$. Then the intermediate fraction $x_{k,t}$ is a first-kind best approximation if and only if $t>\dfrac{a_{k+1}}{2}$, or $t=\dfrac{a_{k+1}}{2}$ and $r_{k+2}>\dfrac{q_k}{q_{k-1}}$.

We will show below that every convergent is a second-kind best approximation, and hence is necessarily a first-kind best approximation. The key issue is the intermediate fractions that are not convergents.

As stated earlier, the denominator of an intermediate fraction $x_{k,t}$ lies between those of $x_k$ and $x_{k+1}$ and increases as $t$ increases, while $x_{k,t}$ gradually approaches $x_{k+1}$ and hence gets closer to $x$. For example, when $x_{k,t}<x$, its relative positions with the neighboring intermediate fractions satisfy

Since the denominator of $x_k$ is smaller than that of $x_{k,t}$, the necessary condition for $x_{k,t}$ to be a first-kind best approximation is that it, relative to $x_k$, give a closer approximation to $x$. This is also sufficient: as a convergent, no fraction with a denominator smaller than that of $x_k$ is a closer approximation. An intermediate fraction with a denominator larger than that of $x_k$ is necessarily of the same order as $x_{k,t}$ and, having a smaller denominator, is necessarily farther from $x$. Direct calculation gives the errors of the convergent and intermediate fraction:

Here we used $r_{k+1}\ge a_{k+1}>t$. Thus, $x_{k,t}$ is closer than $x_k$ to $x$ and is a first-kind best approximation if and only if

There are three possible cases:

1. If $t<\dfrac{a_{t+1}}{2}$, then $2t<a_{t+1}$. Since both sides are integers, $2t\le a_{k+1}-1$, so $2t+\dfrac{q_{k-1}}{q_k}\le 2t+1\le a_{k+1}\le r_{t+1}$. In this case, $x_{k,t}$ is not a first-kind best approximation;
2. If $t>\dfrac{a_{t+1}}{2}$, then $2t>a_{t+1}$. Since both sides are integers, $2t\ge a_{t+1}+1>r_{t+1}$. In this case, $x_{k,t}$ is a first-kind best approximation;
3. If $a_{t+1}$ is even, there is a third case, namely $t=\dfrac{a_{t+1}}{2}$. The condition above is equivalent to $\dfrac{1}{r_{k+1}}=r_{k+1}-a_{k+1}<\dfrac{q_{k-1}}{q_k}$, or $r_{k+2}>\dfrac{q_k}{q_{k-1}}$.