1
$\begingroup$

I have read this from here

The simple continued fraction for $x$ generates all of the best rational approximations for $x$ according to three rules:

  1. Truncate the continued fraction, and possibly decrement its last term.

  2. The decremented term cannot have less than half its original value.

  3. If the final term is even, half its value is admissible only if the corresponding semiconvergent is better than the previous convergent.

It means the best rational approximations of $x$ are the convergents and some semi-convergents of the continued fraction. But I can't find the proof anywhere. How can I prove it?

The question was already asked here, but it doesn't have any answer.

$\endgroup$
3
  • $\begingroup$ It can be proved, for example, that if $|\alpha-(p/q)|<1/(2q^2)$ then $p/q$ is a convergent for the continued fraction for $\alpha$, and you'll find proofs in many intro number theory textbooks, but the proofs come after pages of development of the theory of continued fractions. I don't think anyone is going to write out a proof here. Also, the Wikipedia article you found does have a couple of footnotes pointing you to references --- have you checked them? $\endgroup$ Jul 7 '14 at 10:55
  • $\begingroup$ See also shreevatsa.wordpress.com/2011/01/10/… including the discussion following the essay. $\endgroup$ Jul 7 '14 at 11:00
  • 1
    $\begingroup$ I found this useful: books.google.com/… $\endgroup$ Jul 8 '14 at 3:52
2
$\begingroup$

I recently found myself in exactly the same situation you have apparently been in 5 years ago, so I tried to come up with a proof myself. As far as I can tell, I managed to find one, so here goes:

To summarize: Let $v$ be any real number with a simple continued fraction representation that has at least $n+1$ coefficients, with $n\geq 1$:

$$v =\lbrack a_0; a_1, \ldots, a_{n-1}, a_n, \ldots\rbrack$$

There might be more coefficients to follow after $a_n$, or there might not. In order to be able to express the exact value of $v$, let us define a real number ${a_n}' = \lbrack a_n; a_{n+1}, a_{n+2}, \ldots\rbrack$, so that:

$$v = \lbrack a_0; a_1, \ldots, a_{n-1}, {a_n}'\rbrack$$

Now, the objective is to find out out which condition must hold so that $\lbrack a_0; a_1, \ldots, a_{n-1}, x\rbrack$ is closer to $v$ than $\lbrack a_0; a_1, \ldots, a_{n-1}\rbrack$, given that $1\leq x\leq a_n$.

Due to the nature of simple continued fractions, the value of a simple continued fraction either increases or decreases with the increase of a coefficient, depending on whether this coefficient has an even or odd index. So if $n$ is even, we have:

$$\lbrack a_0; a_1, \ldots, a_{n-1}, x\rbrack \leq \lbrack a_0; a_1, \ldots, a_{n-1}, {a_n}'\rbrack < \lbrack a_0; a_1, \ldots, a_{n-1}\rbrack$$

Conversely, if $n$ is odd, we have:

$$\lbrack a_0; a_1, \ldots, a_{n-1}, x\rbrack \geq \lbrack a_0; a_1, \ldots, a_{n-1}, {a_n}'\rbrack > \lbrack a_0; a_1, \ldots, a_{n-1}\rbrack$$

With this information, we can now calculate the criterion that determines if $\lbrack a_0; a_1, \ldots, a_{n-1}, x\rbrack$ is a better approximation of $v$ than $\lbrack a_0; a_1, \ldots, a_{n-1}\rbrack$. If $\frac{h_i}{k_i}$ is the convergent corresponding to the coefficient $a_i$, this condition can be formally stated as:

$$\left\lvert\frac{{a_n}' h_{n-1} + h_{n-2}}{{a_n}' k_{n-1} + k_{n-2}} - \frac{x h_{n-1} + h_{n-2}}{x k_{n-1} + k_{n-2}}\right\rvert < \left\lvert\frac{h_{n-1}}{k_{n-1}}-\frac{{a_n}' h_{n-1} + h_{n-2}}{{a_n}' k_{n-1} + k_{n-2}}\right\rvert$$

If $n$ is even, the terms inside the absolute value delimiters are positive, otherwise, they are negative (unless $x={a_n}'$, in which case the left-hand side will be zero). So the inequation becomes:

$$\begin{aligned} (-1)^n\left (\frac{{a_n}' h_{n-1} + h_{n-2}}{{a_n}' k_{n-1} + k_{n-2}} - \frac{x h_{n-1} + h_{n-2}}{x k_{n-1} + k_{n-2}}\right ) &< (-1)^n\left (\frac{h_{n-1}}{k_{n-1}} - \frac{{a_n}' h_{n-1} + h_{n-2}}{{a_n}' k_{n-1} + k_{n-2}}\right ) \\ (-1)^n\left (2\cdot\frac{{a_n}' h_{n-1} + h_{n-2}}{{a_n}' k_{n-1} + k_{n-2}} - \frac{x h_{n-1} + h_{n-2}}{x k_{n-1} + k_{n-2}}\right ) &< (-1)^n\frac{h_{n-1}}{k_{n-1}} \end{aligned}$$

Since the denominators are all positive, we can multiply the inequation by the two denominators on the left-hand side. This is going to get a bit ugly, so I'll tackle the left- and right-hand side separately. First, the left-hand side:

$$\begin{aligned} &(-1)^n\left (2\cdot\frac{{a_n}' h_{n-1} + h_{n-2}}{{a_n}' k_{n-1} + k_{n-2}} - \frac{x h_{n-1} + h_{n-2}}{x k_{n-1} + k_{n-2}}\right ) ({a_n}' k_{n-1} + k_{n-2}) (x k_{n-1} + k_{n-2}) \\ = &(-1)^n\left ((2{a_n}' h_{n-1} + 2h_{n-2})(x k_{n-1} + k_{n-2}) - (x h_{n-1} + h_{n-2}) ({a_n}' k_{n-1} + k_{n-2})\right ) \\ = &(-1)^n\left ((2 {a_n}' x h_{n-1} k_{n-1} + 2x h_{n-2} k_{n-1} + 2{a_n}' h_{n-1} k_{n-2} + 2h_{n-2} k_{n-2}) - ({a_n}' x h_{n-1} k_{n-1} + {a_n}' h_{n-2} k_{n-1} + x h_{n-1} k_{n-2} + h_{n-2} k_{n-2})\right ) \\ = &(-1)^n\left ({a_n}' x h_{n-1} k_{n-1} + (2x - {a_n}') h_{n-2} k_{n-1} + (2{a_n}' - x) h_{n-1} k_{n-2} + h_{n-2} k_{n-2}\right ) \end{aligned}$$

Now comes the right-hand side:

$$\begin{aligned} &(-1)^n \frac{h_{n-1}}{k_{n-1}} ({a_n}' k_{n-1} + k_{n-2}) (x k_{n-1} + k_{n-2}) \\ = &(-1)^n \frac{h_{n-1}}{k_{n-1}}\left ({a_n}' x {k_{n-1}}^2 + x k_{n-1} k_{n-2} + {a_n}' k_{n-1} k_{n-2} + {k_{n-2}}^2\right ) \\ = &(-1)^n \frac{h_{n-1}}{k_{n-1}}\left ({a_n}' x {k_{n-1}}^2 + (x + {a_n}') k_{n-1} k_{n-2} + {k_{n-2}}^2\right ) \\ = &(-1)^n\left ({a_n}' x h_{n-1} k_{n-1} + (x + {a_n}') h_{n-1} k_{n-2} + \frac{h_{n-1} {k_{n-2}}^2}{k_{n-1}}\right ) \end{aligned}$$

By subtracting the right-hand side from the inequation, we get:

$$\begin{aligned} (-1)^n\left ((2x - {a_n}') h_{n-2} k_{n-1} + ({a_n}' - 2x) h_{n-1} k_{n-2} + h_{n-2} k_{n-2} - \frac{h_{n-1} {k_{n-2}}^2}{k_{n-1}}\right ) &< 0 \\ (-1)^n\left (({a_n}' - 2x) (h_{n-1} k_{n-2} - h_{n-2} k_{n-1}) + \frac{h_{n-2} k_{n-1}k_{n-2}-h_{n-1}{k_{n-2}}^2}{k_{n-1}}\right ) &< 0 \\ (-1)^n\left (({a_n}' - 2x) (h_{n-1} k_{n-2} - h_{n-2} k_{n-1}) + \frac{k_{n-2} (h_{n-2} k_{n-1} - h_{n-1} k_{n-2})}{k_{n-1}}\right ) &< 0 \\ (-1)^n(h_{n-1} k_{n-2} - h_{n-2} k_{n-1}) \left ({a_n}' - 2x - \frac{k_{n-2}}{k_{n-1}}\right ) &< 0 \end{aligned}$$

It is a well-known fact that $h_{i-1} k_i - h_i k_{i-1} = (-1)^i$ for all numerators and denominators of simple continued fraction convergents (including the two initial "theoretical" convergents $\frac{h_{-2}}{k_{-2}} = \frac{0}{1}$ and $\frac{h_{-1}}{k_{-1}} = \frac{1}{0}$). It thus follows that $h_{n-1} k_{n-2} - h_{n-2} k_{n-1} = -(-1)^{n-1} = (-1)^n$, and further that $(-1)^n (h_{n-1} k_{n-2} - h_{n-2} k_{n-1}) = (-1)^n \cdot (-1)^n = 1$. So the above inequation becomes:

$$\begin{aligned} {a_n}' - 2x - \frac{k_{n-2}}{k_{n-1}} &< 0 \\ {a_n}' - 2x &< \frac{k_{n-2}}{k_{n-1}} \\ \lbrack a_n - 2x; a_{n+1}, a_{n+2}, \ldots\rbrack &< \frac{k_{n-2}}{k_{n-1}} \end{aligned}$$

Now, the section you quoted from the Wikipedia article contains a reference to this document, which, in the second-to-last paragraph on page 28, contains a reference to a section in this document, where (on pp. 301 of the book, which corresponds to pp. 314 of the pdf) I learned about continuants (note that, even though this paragraph might read like it, they are not a well-kept, heavily guarded secret that had to be dug out from a cave in the middle of nowhere – you can easily find information about continuants via Google, the convoluted chain of references I gave was just to show how I became aquainted with them). A continuant is a multivariate polynomial recursively defined as follows:

$$\begin{aligned} K_0 &= 1 \\ K_1(x_1) &= x_1 \\ K_i(x_1, x_2, \ldots, x_i) &= K_{i-1}(x_1, x_2, \ldots, x_{i-1}) x_i + K_{i-2}(x_1, x_2, \ldots, x_{i-2}) \end{aligned}$$

So a continuant essentially abstracts the recursive formula by which the numerator and denominator of the convergents of simple continued fractions are calculated:

$$\lbrack a_0; a_1, \ldots, a_i\rbrack = \frac{K_{i+1}(a_0, a_1, \ldots, a_i)}{K_i(a_1, a_2, \ldots, a_i)}$$

We can apply this identity to our inequation above, provided that $n \geq 2$ (if $n=1$, then $\frac{k_{n-2}}{k_{n-1}}$ will simply evaluate to $0$):

$$\lbrack a_n - 2x; a_{n+1}, a_{n+2}, \ldots\rbrack < \frac{K_{n-2}(a_1, a_2, \ldots, a_{n-2})}{K_{n-1}(a_1, a_2, \ldots, a_{n-1})}$$

And now comes the key element in solving this problem. As Wikipedia puts it:

Continuants are invariant with respect to reversing the order of indeterminates.

Or, in simpler terms: $K_i(x_1, x_2, \ldots, x_i) = K_i(x_i, x_{i-1}, \ldots, x_1)$. I couldn't find a proof for this online, and I won't go into detail about it here (it's not terribly complicated to prove, but it's still outside the scope of this question), so let's just take it for granted for now (equation 6.131 in the reference above also says so, so you don't even have to take my word for it). Our inequation thus becomes:

$$\begin{aligned} \lbrack a_n - 2x; a_{n+1}, a_{n+2}, \ldots\rbrack &< \left (\frac{K_{n-1}(a_1, a_2, \ldots, a_{n-1})}{K_{n-2}(a_1, a_2, \ldots, a_{n-2})}\right )^{-1} \\ \lbrack a_n - 2x; a_{n+1}, a_{n+2}, \ldots\rbrack &< \left (\frac{K_{n-1}(a_{n-1}, a_{n-2}, \ldots, a_1)}{K_{n-2}(a_{n-2}, a_{n-3}, \ldots, a_1)}\right )^{-1} \\ \lbrack a_n - 2x; a_{n+1}, a_{n+2}, \ldots\rbrack &< {\lbrack a_{n-1}; a_{n-2}, \ldots, a_1\rbrack}^{-1} \\ \lbrack a_n - 2x; a_{n+1}, a_{n+2}, \ldots\rbrack &< \lbrack 0; a_{n-1}, a_{n-2}, \ldots, a_1\rbrack \end{aligned}$$

And there you have it. It is obvious that, if $a_n - 2x \geq 1$, then the left side will never be smaller than the right side, both in the trivial case $n=1$, where the right side is $0$, and when $n \geq 2$, so then, $\lbrack a_0; a_1, \ldots, a_{n-1}, x\rbrack$ cannot be closer to $v$ than $\lbrack a_0; a_1, \ldots, a_{n-1}\rbrack$. What is less obvious is that, if $a_n - 2x \leq -1$, the left side will only almost always be smaller than the right side, but not always, because there is one special case: If $n = 1$ and $a_1 - 2x = -1$, and if $a_2 = 1$ is the last coefficient in the simple continued fraction representation of $v$, then both the left side and the right side will be $0$ and $\lbrack a_0; x\rbrack$ will therefore only be equally close to $v = \lbrack a_0; a_1, 1\rbrack = \lbrack a_0; a_1 + 1\rbrack$ as $a_0$, but not closer. Of course, this can only happen if the continued fraction representation of $v$ is given in the longer, less common of the two possible forms, where the last coefficient is $1$. But still, I think it's important to note.

Finally, this shows that, if $a_n - 2x = 0$, it will never be possible to conclusively determine whether $\lbrack a_0; a_1, \ldots, a_{n-1}, x\rbrack$ is a better approximation of $v$ than $\lbrack a_0; a_1, \ldots, a_{n-1}\rbrack$ without knowing any coefficients beyond $a_n$, or whether there are any, except if $n=1$, in which case the inequation will necessarily be false.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.