3
$\begingroup$

I read a blogpost that mentions that for golden ratio, the sets of best rational approximations of the first kind and the second kind are the same.

Is this true? If so, why? Are there other numbers like this?

From looking around the internet, I see that if $p/q$ is a best rational approximation of the second kind, then it is a best approximation of the first kind. However, I have no idea how the other direction works.

Definitions used:

  • $a/b$ is best approximation of $x$ of the first kind if for any fraction $c/d$, $1\le d\le b$ and $a/b \ne c/d$ we have $|x-a/b|<|x-c/d|$
  • $a/b$ is best approximation of $x$ of the second kind if for any fraction $c/d$, $1\le d\le b$ and $a/b \ne c/d$ we have $|bx-a|<|dx-c|$
$\endgroup$
  • $\begingroup$ I assume you mean $1\le d\le b$ in both definitions? $\endgroup$ – Hagen von Eitzen May 19 '14 at 21:42
  • $\begingroup$ Yes, thank you, it is fixed now. $\endgroup$ – BoZenKhaa May 19 '14 at 21:47
  • $\begingroup$ It should be $\lvert bx-a\rvert < \lvert dx - c\rvert$ for the second kind. $\endgroup$ – Daniel Fischer May 19 '14 at 22:05
  • $\begingroup$ Of course, thank you. Now this is getting embarrassing. $\endgroup$ – BoZenKhaa May 19 '14 at 22:12
4
$\begingroup$

Every best approximation of the second kind is a convergent, and every convergent, except possibly the $0$-th convergent, is a best approximation of the second kind.

If $x_n = \frac{p_n}{q_n}$ is the $n$-th convergent of $x$, we have

$$x_0 < x_2 < \dotsc < x_{2k} < x_{2k+2} < \dotsc < x < \dotsc < x_{2k+1} < x_{2k-1} < \dotsc < x_3 < x_1,$$

so successive convergents lie on different sides of $x$. If there are any best approximations of the first kind that aren't also best approximations of the second kind, their denominator must lie between the denominators of two successive convergents, say between $q_{n}$ and $q_{n+1}$. I'll ignore the case $n = 0$ here to be able to use the convergent $x_{n-1}$, that case is handled by similar considerations. Since $\frac{a}{b}$ is supposed to be a best approximation (of the first kind), it must lie between the two convergents $x_{n-1}$ and $x_n$.

The unique fraction with the smallest denominator lying between $x_{n-1}$ and $x_n$ is the mediant $\frac{p_n + p_{n-1}}{q_n + q_{n-1}}$. If the $n+1^{\text{st}}$ partial quotient in the (simple) continued fraction expansion of $x$ is $1$, that is already the $n+1^{\text{st}}$ convergent $x_{n+1}$, so in that case, there cannot be any best approximations of the first kind that have a denominator between $q_n$ and $q_{n+1}$.

That already settles the first part of the question, for the golden ratio

$$\varphi = \frac{1+\sqrt{5}}{2} = [1;\overline{1}],$$

every convergent is the fraction with the smallest denominator lying between the two previous convergents, and thus every best approximation (of the first kind) is a convergent, hence a best approximation of the second kind [with the exception of the $0$-th convergent, $1$, which is not a best approximation].

For the further question whether there are other numbers with the property that all best approximations of the first kind are also best approximations of the second kind - excepting the obvious cases $\varphi + k$ for $k\in\mathbb{Z}$ - we must look a bit closer at the possible best approximations of the first kind. So let us suppose the mediant $\mu_1 := \frac{p_n + p_{n-1}}{q_n+q_{n-1}}$ is not already the next convergent. If $\mu_1$ is not a best approximation of the first kind, since it lies between $x_{n-1}$ and $x$, the next candidate for a best approximation is the mediant of $\mu_1$ and $x_n$, which is the fraction with the smallest denominator lying between $\mu_1$ and $x_n$, that is, $\mu_2 := \frac{p_n + (p_n+p_{n-1})}{q_n + (q_n+q_{n-1})} = \frac{2p_n + p_{n-1}}{2q_n + q_{n-1}}$. Continuing, while we have not yet found a new best approximation, the candidates are

$$\mu_k = \frac{kp_n + p_{n-1}}{kq_n+q_{n-1}},$$

$k = 1,2,3,\dotsc$. If $a_{n+1}$ is the $n+1^{\text{st}}$ partial quotient of the continued fraction expansion of $x$, then $\mu_{a_{n+1}} = x_{n+1}$ is the next convergent, and we know that is a best approximation of the second kind, so we need only be concerned with $k < a_{n+1}$.

So let's see when $\mu_k$ is a best approximation. Since $x_n$ and $\mu_k$ lie on different sides of $x$, $\mu_k$ is a best approximation if and only if $\lvert \mu_k - x_n\rvert < 2\lvert x-x_n\rvert$. Now,

$$\left\lvert\frac{kp_n+p_{n-1}}{kq_n+q_{n-1}} - \frac{p_n}{q_n}\right\rvert = \frac{1}{q_n(kq_n+q_{n-1})}$$

and

$$\left\lvert x - \frac{p_n}{q_n}\right\rvert = \frac{1}{q_n q_{n+1}'},$$

where $q_{n+1}' = a_{n+1}'q_n + q_{n-1}$ and $a_{n+1}'$ is the $n+1^{\text{st}}$ complete quotient of $x$, i.e. $x = \frac{a_{n+1}'p_n+p_{n-1}}{a_{n+1}'q_n+q_{n-1}}$. We have $a_{n+1} = \lfloor a_{n+1}'\rfloor < a_{n+1}'$ (unless $x$ is rational and we're at the end of the continued fraction expansion).

So the condition is $q_{n+1}' < 2(kq_n+q_{n-1})$, or equivalently $(a_{n+1}' - 2k)q_n < q_{n-1}$. The condition is certainly not fulfilled if $2k < a_{n+1}$, since then the left hand side is larger than $q_n$. It is certainly fulfilled if $2k > a_{n+1}$, since then the left hand side is negative. Thus whenever the continued fraction expansion of $x$ has partial quotients $a_{n+1} \geqslant 3$, there are best approximations to $x$ of the first kind that are not best approximations of the second kind (choose a $k$ between $a_{n+1}/2$ and $a_{n+1}$).

The nontrivial case is thus $a_{n+1} = 2$, when $\mu_1$ may or may not be a best approximation, for $x$ such that all partial quotients (except maybe the $0$-th) are either $1$ or $2$ [since if there are larger partial quotients, there are best approximations of the first kind which aren't convergents].

To avoid best approximations of the first but not the second kind, we want $a_{n+1}'-2$ large when $a_{n+1} = 2$, and that is achieved when $a_{n+2} = 1$. The simplest continued fraction whose partial quotients are all $1$ or $2$ and where no two successive partial quotients equal $2$ is

$$x = \frac{1+\sqrt{3}}{2} = [1;\overline{2,1}],$$

where the odd-indexed partial quotients are $2$ and the even-indexed are $1$. Conveniently, we have $a_{2m+1}' = \sqrt{3}+1$, and

$$\frac{q_{2m}}{q_{2m-1}} = [a_{2m}; a_{2m-1}, a_{2m-2},\dotsc, a_2,a_1] = [1;2,1,2,\dotsc,1,2]$$

is itself a convergent of $x$, with odd index, hence $\frac{q_{2m}}{q_{2m-1}} > x$, therefore

$$\frac{q_{2m}}{q_{2m-1}} > \frac{1+\sqrt{3}}{2} \iff (\sqrt{3}-1)q_{2m} > q_{2m-1},$$

which means that there are no best approximations to $x$ which aren't convergents. Thus we have established the existence of a further group of numbers with the property that all best approximations of the first kind are also best approximations of the second kind. The complete classification of such numbers is beyond the scope of this answer (and possibly beyond me).

$\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.