6
$\begingroup$

Let $p_N/q_N$ be the $N^\text{th}$ convergent of the continued fraction for some irrational number $\alpha$. It turns out that for any other approximation $p/q$ (with $q \le q_N$) which isn't a convergent |\alpha q - p| > |\alpha q_{N-1} - p_{N-1}|. I'm wondering if there are any nice proofs for this result?


In my book this is proved by picking $x,y$ that solves

$ \begin{pmatrix} p_N & p_{N-1} \\ q_N & q_{N-1} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} p \\ q \end{pmatrix} $

since $x$ and $y$ have opposite sign, as well as $\alpha q_N - p_N$ and $\alpha q_{N-1} - p_{N-1}$ have opposite sign we can conclude that $|\alpha q - p| = |x (\alpha q_N - p_N) + y (\alpha q_{N-1} - p_{N-1})| = |x| |\alpha q_N - p_N| + |y| |\alpha q_{N-1} - p_{N-1}|$ which proves the theorem.

I am looking for different proofs than this one.

  • 0
    This is from the book *Exploring the Number Jungle* by Edward Burger (It's a really good book!). I just got the idea that this result has probably been proven in all kinds of different ways and I hope to see some of the best.2010-08-13

1 Answers 1

8

Of course there is a nicer proof! In fact, it's almost obvious if one thinks about geometric interpretation of continued fraction: consider the line $y=\alpha x$; then the best approximation (i.e. approximation that minimizes $|\alpha q-p|=q|\alpha-\frac{p}{q}|$) is the point of integer lattice nearest to this line; finally observe that convergents with even/odd numbers of the continued fraction give coordinates of [verices of] the convex hull of [points of] lattice lying over/under the line.


One can also (as J. M. suggests) take a look at Lorentzen, Waadeland. Continued Fractions with Applications, I.2.1 (esp. figure 1 and the text near it; there are no words "convex hull" there but implicitly everything is explained, more or less).

Upd. One more reference is Davenport's "The Higher Arithmetics" (section IV.12).


Finally, an illustration (from Arnold's book).

  • Bold line $y=\alpha x$ (on the picture $\alpha=\frac{10}7$) is approximated by vectors $e_i$ corresponding to convergents (namely, $e_i$ ends at $(p_i,q_i)$);
  • each vector (starting from $e_3$) is a linear combination of two preciding ones: $e_{i+2}=e_i+a_{i-1}e_{i+1}$, where $a$ is the maximal integer s.t. the new vector still doesn't intersect the line;
  • this is exactly the algorithm for representing $\alpha$ by a continued fraction: $\alpha=[a_0,a_1,\dots]$.

geometry of continued fractions

  • 0
    This is a nice picture, but it doesn't convince me of anything. _Why_ do the vertices of the convex hulls correspond to the convergents? Why not some other rational approximation?2016-11-20