5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steven Stadnicki Jun 4 '18 at 23:10
  • $\begingroup$ @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. $\endgroup$ – Hans Jun 4 '18 at 23:17
  • $\begingroup$ 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$. $\endgroup$ – Steven Stadnicki Jun 4 '18 at 23:27
  • $\begingroup$ @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. $\endgroup$ – Hans Jun 5 '18 at 0:25
  • $\begingroup$ @StevenStadnicki: Do you have a proof? If so, could you please write it up? I am eager to see it. Thank you. $\endgroup$ – Hans Jun 5 '18 at 1:34
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you very much, Steven. I will examine your answer carefully. Do you think the answer to my second question is likely affirmative? $\endgroup$ – Hans Jun 5 '18 at 19:03
  • $\begingroup$ I think so, if only because there's no reason to believe they should be the same. $\endgroup$ – Steven Stadnicki Jun 5 '18 at 19:15
  • $\begingroup$ \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. $\endgroup$ – Hans Jun 5 '18 at 20:29
  • $\begingroup$ @Hans Exactly that, yes. $\endgroup$ – Steven Stadnicki Jun 5 '18 at 20:55
  • $\begingroup$ Actually $$c_{(i+1)p+r}=[a_1,\cdots, a_p, [a_1,\cdots, a_{ip}, [a_1, \cdots,a_r]]]$$ is better. $\endgroup$ – Hans Jun 5 '18 at 21:03
0
$\begingroup$

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')}.$$

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