Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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


$$ {\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 ?

share|improve this question
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
add comment

1 Answer

up vote 0 down vote accepted

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).

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.