# Do best lower approximations of a quadratic irrational always form a linear recurrence sequence?

Let $\theta$ be an irrational number and let

$${\cal L}= \bigg\lbrace (a,b) \in {\mathbb Z} \times {\mathbb N}^{*} \bigg| \frac{a}{b} \leq \theta \bigg\rbrace$$

and

$${\cal B}= \bigg\lbrace (a,b) \in {\cal L} \bigg| \forall (a',b') \in {\cal L}, \ b'\leq b \Rightarrow \frac{a'}{b'} \leq \frac{a}{b} \bigg\rbrace$$

so that $\cal B$ corresponds to the best lower approximations of $\theta$. The elements of $\cal B$ can be arranged in an increasing sequence with increasing denominators, $\frac{a_1}{b_1}<\frac{a_2}{b_2}<\frac{a_3}{b_3} < \ldots$ with $b_1<b_2<b_3< \ldots$.

For example, when $\theta=\sqrt{5}$, the sequence is $\frac{2}{1}<\frac{11}{5}<\frac{20}{9}< \ldots$. The sequences $(a_n)$ and $(b_n)$ are linear recurrent sequences of degree $8$, with characteristic polynomial $X^8-18X^4+1=(X^4-4X^2-1)(X^4+4X^2-1)$.

Note that contrary to what might be excepted, this degree 8 has nothing to do with the period of the standard continued fraction for $\theta$, which equals $1$ (we have $\sqrt{5}=2+\frac{1}{\phi}$ with $\phi=4+\frac{1}{\phi}$) .

My question is, are the sequences $(a_n)$ and $(b_n)$ always evantually linear recurrent if $\theta$ is a quadratic irrational ?

-
Possibly related: math.leidenuniv.nl/~hwl/PUBLICATIONS/1993g/art.pdf – Aryabhata Feb 23 '12 at 18:18
@ Aryabhata : it is very related indeed. Many thanks! – Ewan Delanoy Feb 23 '12 at 19:11

I finally found a complete answer to my question. My sequence is not the same thing as the convergents of the standard continued fraction of $\theta$ ; indeed, many terms in my sequence are not convergents and many convergents are not in my sequence. However, the two sequences share near-identical properties as we are going to see.

For any $m\geq 1$, enote by $l_m$ ($u_m$, respectively) the largest (smallest) fraction with denominator $\leq m$ that is smaller (larger) than $\theta$. Thus the set $\lbrace l_m | m \geq 1\rbrace$ is the same thing as the set $\lbrace \frac{a_n}{b_n} | n \geq 1\rbrace$, and for every $n$ we have $\frac{a_n}{b_n}=l_{b_n}$. On the other side of $\theta$, $u_{b_n}$ can be written as a reduced fraction $\frac{c_n}{d_n}$. It is well-known that $b_nc_n-a_nd_n=1$. To find the next term $\frac{a_{n+1}}{b_{n+1}}$, we use mediants : let $v_0=\frac{c_n}{d_n}$, and for $k \geq 1$ let $v_{k}$ be the mediant of $v_{k-1}$ and $\frac{a_n}{b_n}$. Then one has $v_k=\frac{c_n+ka_n}{d_n+kb_n}$ for all $k$, and there is a unique $k_n$ such that $v_{k_n} > \theta > v_{k_n+1}$. Then the next pair of near-values around $\theta$, $(\frac{a_{n+1}}{b_{n+1}},\frac{c_{n+1}}{d_{n+1}})$ is exactly $(v_{k_{n+1}},v_{k_n})$. We deduce the recurrence formulas

$$a_{n+1}=c_n+(k_{n}+1)a_n \\ b_{n+1}=d_n+(k_{n}+1)b_n \\ c_{n+1}=c_n+k_{n}a_n \\ d_{n+1}=d_n+k_{n}b_n \\$$

which can be rewritten more elegantly as a matrix equality : if we put

$$K_n= \left( \begin{matrix} k_n+1 & 1 \\ k_n & 1 \end{matrix} \right), M_n= \left( \begin{matrix} a_{n} & b_{n} \\ c_{n} & d_{n} \end{matrix} \right)$$ then we have $M_{n+1}=K_nM_n$ for all $n\geq 1$. Also, $k_n$ can be written as $\lfloor \rho_n \rfloor$, where $\rho_n=\frac{c_n-d_n\theta}{b_n\theta-a_n}$. If we put

$$\left( \begin{matrix} a & b \\ c & d \end{matrix} \right) \star x=\frac{cx-d}{bx-a},$$ then this defines a group action of $GL_2({\mathbb Q})$ on $\mathbb Q$ : $A \star (B \star x)=(AB) \star x$ for any matrices $A,B$ and any $x\in {\mathbb Q}$. We deduce $$\rho_{n+1}=M_{n+1}\star\theta=K_nM_n \star \theta=K_n \star \rho_n$$ In other words, the sequence $(\rho_n)$ satisfies the recurrence relation

$$\rho_{n+1}=f(\rho_n), \ {\rm with} \ f(x)=\frac{x-\lfloor x \rfloor}{\lceil x\rceil-x}$$

If $\theta$ is a quadratic irrational, it can be written in the familiar "Legendre" form $\frac{p+\sqrt{D}}{q}$ where $p,q,D$ are integers with $D$ a nonsquare, and $q$ divides $D-p^2$. Then, by induction, each $\rho_n$ is again of the form $\frac{p_n+\sqrt{D}}{q_n}$ where $p_n$ and $q_n$ are integers and $q_n$ divides $D-p_n^2$. So $r_n=\frac{D-p_n^2}{q_n}$ is an integer, and we have $|q_nr_n| \leq |D|$, $|q_n| \leq D, |r_n| \leq |D|, |p_n^2| \leq |D|+|q_nr_n| \leq |D|+|D|^2$. So there are only finitely many possible values for the pair $(p,q)$, so the sequence $(\rho_n)$ takes its values in a finite set. Since it also satisfies $\rho_{n+1}=f(\rho_n)$, it is eventually periodic. Then $(k_n)$ is also eventually periodic, and it is easily deduced that the vector $(a_n,b_n,c_n,d_n)$ satisfies a linear recurrence relation (for more details see the article linked by Aryabhata in the comments).

-