A nicer proof of Lagrange's 'best approximations' law?

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.

Solutions Collecting From Web of "A nicer proof of Lagrange's 'best approximations' law?"

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