# Quadratic surd continued fraction convergent ratio limit

Given a quadratic surd $\sqrt d$ where $d$ is a natural number and not a perfect square. $(c_i)_{i=1}^\infty$ is the sequence of convergents of the continued fraction of $\sqrt d$. Let $s_i:=\frac{c_{i+1}-\sqrt d}{c_i-\sqrt d},\,\forall i\in\mathbf N$. Let $n$ be the period of the continued fraction. Are the followings true?

1. $l_r:=\lim_\limits{i\rightarrow\infty}s_{in+r}$ exists for any $r\in\{0,1,\cdots,n-1\}$.

2. For $n\le 2$, $l_0=l_1$.

3. For $n\ge 3$, there exists at least two distinct $l_r$'s.

Conjecture 1. is proved below. However, conjectures 2. and 3. still await proofs.

• Also, how much investigating have you done? I suspect both are 'generically' true but haven't really dug closely; it should be possible to find explicit expressions for relatively small $d$, though, that would make these rather straightforward. – Steven Stadnicki Jun 4 '18 at 23:10
• @StevenStadnicki: Thanks for spotting the typo. I have corrected it. These conjectures come from a numerical experiment. It is hard to compute $r_i$ for large $i$ as $p_i$ and $q_i$ grow large quickly. – Hans Jun 4 '18 at 23:17
• Well, there should be a relatively 'straightforward' expressions for the various $c_{r+p}$ as a linear fractional expression in $c_r$ (one expression for each modulo class of $r$) - just iterate one period of the CF, shifted appropriately - and you should be able to prove convergence algebraically by looking at the expressions for adjacent values of $r$. – Steven Stadnicki Jun 4 '18 at 23:27
• @StevenStadnicki: I tried this approach before. Looking at it again, I still find obstacles to reaching the goal, since the recursion function depends on $ip+r$. I tried to find a linear fractional recursion $c_{(i+1)p+r}=\frac{a_rc_{ip+r}+b_r}{c_{ip+r}+d_r}$ but failed. You probably see a trick I do not. – Hans Jun 5 '18 at 0:25
• @StevenStadnicki: Do you have a proof? If so, could you please write it up? I am eager to see it. Thank you. – Hans Jun 5 '18 at 1:34

I'll show how to tackle the first question on an example with $r=0$. For concreteness' sake, let's look at the continued fraction for $\sqrt{7}$: $\sqrt{7}=[2; \overline{1, 1, 1, 4}]$. Then the critical insight here is that if $c_{4n}$ is the $4n$'th convergent, then the $4(n+1)$th convergent is $\displaystyle c_{4(n+1)}=2+\frac1{1+}\frac1{1+}\frac1{1+}\frac1{2+c_{4n}}$. Now, we can unwind this term-by-term: \begin{align} c_{4(n+1)} &= 2+\frac1{1+}\frac1{1+}\frac1{1+}\frac1{2+c_{4n}} \\ &= 2+\frac1{1+}\frac1{1+}\frac{2+c_{4n}}{3+c_{4n}} \\ &= 2+\frac1{1+}\frac{3+c_{4n}}{5+2c_{4n}} \\ &= 2+\frac{5+2c_{4n}}{8+3c_{4n}} \\ &= \frac{21+8c_{4n}}{8+3c_{4n}}. \\ \end{align} Finding an expression for the $(4(n+1)-1)$th convergent in terms of the $(4n-1)$th is a little bit trickier, but it's still possible; the trick is that if $c_{4i-1}$ is the $4i-1$th convergent to $\sqrt{7}$, then $d_i=1+\dfrac1{2+c_{4i-1}}$ is the $4i$th convergent to $1+\dfrac{1}{2+\sqrt{7}} = [\overline{1, 4, 1, 1}]$. Now it's all just algebra (which I will hopefully get right): \begin{align} d_{4(n+1)} &=1+\frac1{4+}\frac1{1+}\frac1{1+}\frac1{d_{4n}} \\ &= 1+\frac1{4+}\frac1{1+}\frac{d_{4n}}{1+d_{4n}} \\ &= 1+\frac1{4+}\frac{1+d_{4n}}{1+2d_{4n}} \\ &= 1+\frac{1+2d_{4n}}{5+9d_{4n}} \\ &= \frac{6+11d_{4n}}{5+9d_{4n}}. \end{align}

And since $d_{4n}=\dfrac{3+c_{4n-1}}{2+c_{4n-1}}$, $c_{4n-1}=\dfrac{3-2d_{4n}}{-1+d_{4n}}$; so $c_{4(n+1)-1}=\dfrac{3-2\frac{6+11d_{4n}}{5+9d_{4n}}}{-1+\frac{6+11d_{4n}}{5+9d_{4n}}}$ $=\dfrac{3(5+9d_{4n})-2(6+11d_{4n})}{(-5-9d_{4n})+6+11d_{4n}}$ $=\dfrac{3+5d_{4n}}{1+2d_{4n}}$ $=\dfrac{3+5\frac{3+c_{4n-1}}{2+c_{4n-1}}}{1+2\frac{3+c_{4n-1}}{2+c_{4n-1}}}$ $=\dfrac{3(2+c_{4n-1})+5(3+c_{4n-1})}{(2+c_{4n-1})+2(3+c_{4n-1})}$ $=\dfrac{21+8c_{4n-1}}{8+3c_{4n-1}}$. Notably, this is the same formula that holds for $c_{4n}$; this should generically be the case (but I haven't proved it).

Finally, let's look at $r_{4(i+1)-1}$ (to use the original notation). Then $r_{4(i+1)-1} = \dfrac{c_{4(i+1)}-\sqrt{7}}{c_{4(i+1)-1}-\sqrt{7}}$. Let's look first at the denoninator here: $c_{4(i+1)-1}-\sqrt{7}$ $=\dfrac{21+8c_{4i-1}}{8+3c_{4i-1}}-\sqrt{7}$ $= \dfrac1{8+3c_{4i-1}}(21+8c_{4i-1}-\sqrt{7}(8+3c_{4i-1})$ $= \dfrac1{8+3c_{4i-1}}(8c_{4i-1}-8\sqrt{7}+21-3\sqrt{7}c_{4i-1})$ $=\dfrac1{8+3c_{4i-1}}(8(c_{4i-1}-\sqrt{7})+3\sqrt{7}(\sqrt{7}-c_{4i-1}))$ $=\dfrac1{8+3c_{4i-1}}(8-3\sqrt{7})(c_{4i-1}-\sqrt{7})$. Since we have a similar formula in the numerator, we get ultimately $r_{4(i+1)-1} = \dfrac{8+3c_{4i-1}}{8+3c_{4i}}r_{4i-1}$. Now, $\dfrac{8+3c_{4i-1}}{8+3c_{4i}} = 1-\dfrac{3(c_{4i-1}-c_{4i})}{8+3c_{4i}}$; but it's well-known that the difference between successive convergents $c_{4i-1}=\dfrac{a_{4i-1}}{b_{4i-1}}$ and $c_{4i}=\dfrac{a_{4i}}{b_{4i}}$ has magnitude $|c_{4i-1}-c_{4i}|=\dfrac1{b_{4i-1}b_{4i}}$ and that the denominator of convergents $b_i$ grows exponentially with $i$; this means that $r_{4(i+1)-1}=(1-O(K^{-i}))r_{4i-1}$ for some constant $K$ and guarantees convergence of the infinite product (and thus existence of the limit).

It would take a bit more knowledge of continued fractions (or a lot more digging and effort) to fill in the gaps here in the general case, but it shouldn't be too complicated: note that in the "magic formula" $c_{4n+1}=\dfrac{21+8c_{4n}}{8+3c_{4n}}$ we have $\left(\begin{smallmatrix}21\\8\end{smallmatrix}\right)=\left(\begin{smallmatrix}0&7\\1&0\end{smallmatrix}\right)\left(\begin{smallmatrix}8\\3\end{smallmatrix}\right)$ and the $\langle8, 3\rangle$ here are the components of the 'fundamental solution' $8^2-7\cdot 3^2=1$ of the Pell equation $x^2-7y^2=1$, which of course is intimately related to the continued fraction expansion of $\sqrt{7}$. I strongly suspect that a similar argument should work canonically for all quadratic surds, and that you'll find $c_{(n+1)p}=\dfrac{D\hat{b}+\hat{a}c_{np}}{\hat{a}+\hat{b}c_{np}}$ where $(\hat{a}, \hat{b})$ are the fundamental solution to the Pell equation $a^2-Db^2=1$.

• Thank you very much, Steven. I will examine your answer carefully. Do you think the answer to my second question is likely affirmative? – Hans Jun 5 '18 at 19:03
• I think so, if only because there's no reason to believe they should be the same. – Steven Stadnicki Jun 5 '18 at 19:15
• \begin{align}c_{(i+1)p+r}&=[a_1, a_2, \cdots, a_r, [a_{r+1}, \cdots,a_{r+(i+1)p}]] \\ &=[a_1,\cdots, a_r, [a_{r+1}, \cdots,a_{r+p},[a_{r+p+1}, \cdots,a_{r+(i+1)p}]]]\\&=[a_1,\cdots, a_r,c^{(r)}_{(i+1)p}] \\&=[a_1, \cdots, a_r,[a_{r+1},\cdots, a_{r+p},c^{(r)}_{(i+1)p}]]\end{align} the subscripts of $a$ is of mod$(p)$. Just need the relations of the cyclic transform of $[a_1,\cdots,a_p]$. I should have realzed this. I was hoping to get this kind of recursion but only looking at the recursion formulea of the numerators and denominators instead of directly at the definition of the convergents. – Hans Jun 5 '18 at 20:29
• @Hans Exactly that, yes. – Steven Stadnicki Jun 5 '18 at 20:55
• Actually $$c_{(i+1)p+r}=[a_1,\cdots, a_p, [a_1,\cdots, a_{ip}, [a_1, \cdots,a_r]]]$$ is better. – Hans Jun 5 '18 at 21:03

Here is my proof to conjecture #1. The principle idea is inspired and reminded by the example @StevenStadnicki set in his answer, even though it is what I should have realized before that.

Instead of the quadratic surd $\sqrt d$ per se, we look at the equivalent purely periodic continued fraction $\alpha := [\overline{a_1,a_2,\cdots,a_n}]$ of period $n$. Define function $$L_i(c):=[a_1,a_2,\cdots,a_i, c]=\frac{cp_i+p_{i-1}}{cq_i+q_{i-1}}$$ where $(p_i,q_i)$ is the numerator and denominator of the convergent $c_i$. Note $c_{(i+1)n+r}=L_n(c_{in+r})$ and $L_n(\alpha)=\alpha$. $$L_i(u)-L_i(v)=\frac{(u-v)(p_iq_{i-1}-p_{i-1}q_i)}{(uq_i+q_{i-1})(vq_i+q_{i-1})}=\frac{(-1)^i(u-v)}{(uq_i+q_{i-1})(vq_i+q_{i-1})},$$ as $$p_iq_{i-1}-p_{i-1}q_i=(-1)^i\implies c_i-c_{i-1}=\frac{(-1)^i}{q_iq_{i-1}}. \tag1$$ So $$s_{(i+1)n+r}=\frac{L_n(c_{in+r+1})-L_n(\alpha)}{L_n(c_{in+r})-L_n(\alpha)}=\frac{c_{in+r}q_n+q_{n-1}}{c_{in+r+1}q_n+q_{n-1}}s_{in+r} =\left(1+\frac{\frac{(-1)^{in+r}}{q_{_{in+r+1}}q_{in+r}}}{c_{in+r+1}+\frac{q_{n-1}}{q_n}}\right)s_{in+r}.\tag2$$ From $$q_i=a_iq_{i-1}+q_{i-2}\tag3$$ we have $$\frac{q_n}{q_{n-1}}=[a_n,a_{n-1},\cdots,a_2].$$ It can be easily seen from Eq. (1) that $$|c_i-\alpha|<\frac1{q_i^2}.$$ From Eq. (3), $$q_{in+r}>n^i+r.$$ Actually we have a precise computation of the growth of $(q_k)_{k=1}^\infty$ due to the finiteness of $(a_k)_{k=1}^n$. $$\begin{bmatrix} q_{in+r+1} \\ q_{in+r} \end{bmatrix} =\begin{bmatrix} b_1 & b_2 \\ b_3 & b_4 \end{bmatrix} \begin{bmatrix} q_{(i-1)n+r+1} \\ q_{(i-1)n+r} \end{bmatrix} =\begin{bmatrix} b_1 & b_2 \\ b_3 & b_4 \end{bmatrix}^i \begin{bmatrix} q_{r+1} \\ q_r \end{bmatrix}.$$ $q_{in+r}$ grows precisely exponentially. So from Eq. (3) $r_{in+r}$ converges oscillatorily exponentially as $i\rightarrow\infty$.

Proof to conjecture $2.$:

Define $$P(x):=\frac{\lfloor\sqrt d\rfloor x+d}{x+\lfloor\sqrt d\rfloor}.$$ Obviously $P(\sqrt d)=\sqrt d$.

By Theorem Plus of Square Root, Continued Fractions and the Orbit of $\frac10$ on $\partial H^2$ by Julian Rose, Krishna Shankar and Justin Thomas. The continued fraction of $\sqrt d$ is of period $2$ iff $P^i(\infty)=c_i$ for all convergents $\{c_i\}_{i=1}^\infty$.

$$\frac{P(c_i)-P(\sqrt d)}{c_i-\sqrt d}=-\frac{\sqrt d-\lfloor\sqrt d\rfloor}{c_i+\lfloor\sqrt d\rfloor}.$$ So $$l_0=l_1=-\frac{\sqrt d-\lfloor\sqrt d\rfloor}{\sqrt d+\lfloor\sqrt d\rfloor}.$$

Attempt at proving Conjecture 3:

A fraction linear transform $L$ with integer coefficients with fixed points $\pm\sqrt d$ is of the form $L(x)=\frac{ax+cd}{cx+a}$ for some integers $a$ and $c$. Of course $L_n(x)=\frac{(x+a_1)p_n+p_{n-1}}{(x+a_1)q_n+q_{n-1}}$ where $p_i$ and $q_i$ are the numerators and denominators of the convergents, $a_1=\lfloor \sqrt d \rfloor$, and $n$ is the period of the continued fraction, is one such fractional linear transformation. Let $\alpha=\sqrt d+\lfloor \sqrt d \rfloor$ and $\alpha'=\sqrt d-\lfloor \sqrt d \rfloor$ be its conjugate. A linear fractional transformation $f$ preserves the cross ratio, i.e. $$\frac{(x_3-x_1)(x_4-x_2)}{(x_3-x_2)(x_4-x_1)}=\frac{(f(x_3)-f(x_1))(f(x_4)-f(x_2))}{(f(x_3)-f(x_2))(f(x_4)-f(x_1))}.$$ With $f=L_n$ and $L_n(\alpha)=\alpha$, $L_n(\alpha')=\alpha'$ we have $$\frac{(c_{r+1}-\alpha)(c_r- \alpha')}{(c_r- \alpha)(c_{r+1}-\alpha')}=\frac{(L_n^k(c_{r+1})-\alpha)(L_n^k(c_r)-\alpha')}{(L_n^k(c_r)-\alpha)(L_n^k(c_{r+1})-\alpha')},\ \forall k\in\mathbf N$$ From the proof of Conjecture #1 and $\lim_{k\to\infty}L_n^k(c_r)=\alpha$, we know the right hand side converges to $l_r$ as $k\to\infty$. So we have an explicit expression for $$l_r = \frac{(c_{r+1}-\alpha)(c_r- \alpha')}{(c_r- \alpha)(c_{r+1}-\alpha')}.$$