Relationship between Dirichlet's Approximation Theorem and Convergents

Question

For any real number $r$, the convergents to the continued fraction expansion of $r$ satisfy Dirichlet's approximation inequality of $|r - \frac{p}{q}| < \frac{1}{q^2}$.

Does this go the other way? That is, if given some rational number $p/q$, we have that $|r - \frac{p}{q}| < \frac{1}{q^2}$, does that necessarily mean that it is a convergent of the continued fraction expansion of $r$?

It does seem, from this page, that we have a similar result that the convergents, and only the convergents, minimize $|r - \frac{p}{q}| \cdot q$ among all smaller rationals, so we would need to show that whenever this happens, we also have $|r - \frac{p}{q}| \cdot q < \frac{1}{q}$.

EDIT: Legendre has also proven that if $|r - \frac{p}{q}| < \frac{1}{2q^2}$ then $p/q$ is a convergent of $r$. So the main question is what happens if for whatever $p/q$ we have that $\frac{1}{2q} < |r - \frac{p}{q}| < \frac{1}{q}$: can we determine that $p/q$ is a convergent, or a semiconvergent, or anything at all?

Answer 1

Three results summarize how good continued fractions are at approximating. Here, suppose that $\frac{p_0}{q_0}, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \dots$ are the continued fraction approximants to $r \notin Q$.

1. The statement you quote: for all $n \in \mathbb N$, $|r - \frac{p_n}{q_n}| < \frac1{q_n^2}$.
2. Legendre's theorem: if $|r - \frac pq| < \frac1{2q^2}$, then $\frac pq = \frac{p_n}{q_n}$ for some $n \in \mathbb N$.
3. Hurwitz's theorem: there are infinitely many $n \in \mathbb N$ such that $|r - \frac{p_n}{q_n}| < \frac1{\sqrt5 q_n^2}$. (In particular, there is such a value of $n$ among any three consecutive natural numbers).

However, there are other approximations that are good enough for Dirichlet, but not good enough for Legendre. As pointed out in the comments by @halbaroth, there is a fourth result that characterizes such approximations:

4. Fatou's theorem: if $|r - \frac pq| < \frac1{q^2}$, then $\frac pq \in \{ \frac{p_n}{q_n}, \frac{p_{n+1}+p_n}{q_{n+1}+q_n}, \frac{p_{n+2}-p_{n+1}}{q_{n+2}-q_{n+1}}\}$ for some $n \in \mathbb N$.

The intuition here is that the continued fraction approximants satisfy the recursion $\frac{p_n}{q_n} = \frac{a_n p_{n-1} + p_{n-2}}{a_n q_{n-1} + q_{n-2}}$. So we often get some extra approximations along the way by replacing $a_n$ with some $k \in \{1, 2, \dots, a_n -1\}$. These are all okay approximations, but the only ones that meet Fatou's standards are $k=1$ and $k = a_n - 1$: the ones that are closest to $\frac{p_{n-1}}{q_{n-1}}$ or $\frac{p_n}{q_n}$.

For example, the first few continued fraction approximants to $\sqrt{2}$ are $$1,\frac{3}{2},\frac{7}{5},\frac{17}{12},\frac{41}{29},\frac{99}{70},\dots$$ The first few fractions $\frac pq$ with $|\sqrt2 - \frac pq| < \frac1{q^2}$ are $$1, \frac32, \color{red}{\frac43}, \frac75, \color{red}{\frac{10}7}, \frac{17}{12}, \color{red}{\frac{24}{17}}, \frac{41}{29}, \color{red}{\frac{58}{41}}, \frac{99}{70}, \dots$$ The extra fractions appearing in the gaps are the ones Fatou suggests: for example, $\frac{58}{41} = \frac{41 + 17}{29+12} = \frac{99-41}{70-29}$.

In the case of $\sqrt2$, the error $|\sqrt2 - \frac pq|$ turns out to be approximately $\frac1{2\sqrt2 q^2}$ for the fractions in black and approximately $\frac1{\sqrt2 q^2}$ for the fractions in red, so all of these are good enough.

This does not have to happen; in the case of $\pi$, for example, in between $\frac{22}{7}$ and $\frac{333}{106}$ we have a sequence of approximations $\frac{25}{8}, \dots, \frac{311}{99}$. Fatou promises us only the first and last of these have a chance of being good, but actually, $|\pi - \frac{25}{8}| \approx \frac{1}{0.94 \cdot 8^2}$ and $|\pi - \frac{311}{99}| \approx \frac1{0.57 \cdot 99^2}$: neither is good enough. Fatou does not promise that any of these approximations will satisfy the inequality $|r - \frac pq| < \frac1{q^2}$ - only that nothing else will.

Additionally, the approximations $\frac{p_{n+1}+p_n}{q_{n+1}+q_n}$ and $\frac{p_{n+2}-p_{n+1}}{q_{n+2}-q_{n+1}}$ can, in some cases, get arbitrarily close to the constant of Legendre's theorem. For this, consider $x = 50 + 5\sqrt{102}$: this has continued fraction expansion $[100;2,100,2,100,2,\dots]$. (I hope it is clear how I got this example.) Two consecutive continued fraction approximants to $x$ are $\frac{40601}{404}$ and $\frac{4080300}{40601}$. The first of these is very good: $404^2|x - \frac{40601}{404}| \approx \frac{1}{101}$. The second of these is still decent: $40601^2|x-\frac{4080300}{40601}| \approx \frac1{2.02}$. Well, if we add these together, the result $\frac{4120901}{41005}$ is nearly as good: $41005^2|x - \frac{4120901}{41005}| \approx \frac1{1.98}$.

Answer 2

The answer above is great; I just wanted to summarize in some more succinct terms:

1. The answer to my original question is no. There can be "false positives" for which $|r - p/q| < 1/q^2$, but which are not convergents. One example is, if we're trying to approximate $\log_2(3/2)$, that $10/17$ has the required property but is only a semiconvergent. So this is necessary but not sufficient.

2. I also talked about how if $|r - p/q| < 1/(2q^2)$, then we know we have a convergent. This also does not go the other way, because now there can be "false negatives." Another good example is $24/41$, which is also convergent of $\log_2(3/2)$ but which doesn't have the required property. So this is sufficient but not necessary, and now we get "false negatives" if we are looking for convergents.

3. There is an important result of Fatou which basically says, paraphrasing slightly, that if we do have $|r - p/q| < 1/(2q^2)$, which again is sufficient but not necessary, the "extra" rationals satisfying this property which are not convergents are all semiconvergents that are directly adjacent to some convergent.

4. I was hoping for some magic $k$ such that if the error is less than $1/(kq^2)$, that's necessary and sufficient to make it a convergent. But, it appears that non-convergents can get arbitrarily close to the $1/(2q^2)$ bound, and going the other way, convergents can get arbitrarily close to the $1/(q^2)$ bound.