2
$\begingroup$

It is a well-known result that the partial fraction expansion of $\sqrt{n}$ for some non-square natural number $n$ is periodic of the form

$$[a_0, \overline{a_1, a_2, \ldots, a_{l-1}, 2a_0}]$$ where $a_0 = \lfloor\sqrt{n}\rfloor$ and $a_1, \ldots, a_{l-1}$ is palindromic.

However, here is something that I could not find anywhere explicitly: Is anything more known about the size of the $a_1, \ldots, a_{l-1}$? Are they always ${}\leq a_0$? Looking at the first $10^5$ or so examples seems to suggest so.

If not that, are they at least ${}<2a_0$?

$\endgroup$
  • $\begingroup$ Related: web.math.princeton.edu/mathlab/jr02fall/Periodicity/… $\endgroup$ – dan_fulea Jul 2 '18 at 11:01
  • $\begingroup$ Once upon a time, I thought I had a proof of just this, but recently I tried to recreate it, and got stumped. Another “fact” I thought I had a proof of is that $a_0$ may appear only once in the period, and thus in the center. $\endgroup$ – Lubin Jul 3 '18 at 4:24
  • $\begingroup$ Here is the same question for $n$ prime: math.stackexchange.com/questions/2593032 $\endgroup$ – punctured dusk Jul 3 '18 at 6:43
  • $\begingroup$ @Lubin It is true, also that $a_0$ can occur at most once in a period. It is however the kind of fiddly proof that is easy to forget. I had to dig out my old write-up on continued fractions to see how to prove it. $\endgroup$ – Daniel Fischer Jul 6 '18 at 13:05
2
$\begingroup$

It is more convenient to look at this in terms of

$$\omega = \sqrt{n} + \lfloor \sqrt{n}\rfloor = \bigl[\overline{q_0,q_1,\dotsc,q_{l-1}}\bigr]\,.$$

It is clear that we have $q_0 = 2a_0$ and $q_k = a_k$ for $k \geqslant 1$, since $\omega$ differs from $\sqrt{n}$ exactly by the integer $a_0$.

Proposition: The partial quotients of the simple continued fraction expansion of $\omega$ satisfy $q_k \leqslant a_0$ for $k \not\equiv 0 \pmod{l}$, where $l$ is the minimal period of the continued fraction expansion. Additionally, $q_k = a_0$ can happen at most once per period, in the middle.

Proof: We can write the complete quotients of $\omega$ in the form $$\omega_k = \frac{\sqrt{n} + b_k}{c_k}$$ with integers $b_k, c_k$ satisfying

  1. $0 < b_k < \sqrt{n}$,
  2. $0 < c_k < \sqrt{n} + b_k$, and
  3. $c_k \mid (n - b_k^2)$.

This is proved by induction. The base case $k = 0$ is immediate, for $$\omega_0 = \omega = \frac{\sqrt{n} + \lfloor \sqrt{n}\rfloor}{1}\,,$$

i.e. $b_0 = \lfloor \sqrt{n}\rfloor$ and $c_0 = 1$. For the induction step, we note that $b_{k+1} = q_{k}c_{k} - b_{k}$ and $c_{k+1} = \frac{n - b_{k+1}^2}{c_{k}}$. Since $b_{k+1} \equiv -b_k \pmod{c_k}$, we have $$(n - b_{k+1}^2) \equiv (n - b_{k}^2) \equiv 0 \pmod{c_{k}}$$ by the induction hypothesis, so $c_{k+1}$ is an integer (that $b_{k+1}$ is an integer is obvious). And by the continued fraction algorithm \begin{align} \omega_{k+1} &= \frac{1}{\omega_k - q_k} \\ &= \biggl(\frac{\sqrt{n} + b_k}{c_k} - q_k\biggr)^{-1} \\ &= \biggl(\frac{\sqrt{n} - (q_kc_k - b_k)}{c_k}\biggr)^{-1} \\ &= \frac{c_k}{\sqrt{n} - b_{k+1}} \\ &= \frac{c_k(\sqrt{n} + b_{k+1})}{n - b_{k+1}^2} \\ &= \frac{\sqrt{n} + b_{k+1}}{c_{k+1}}\,. \end{align}

Thus it is immediate that 3. holds for $k+1$ if it holds for $k$, and 2. follows from 1. since we always have $\omega_{k+1} > 1$. To see that 1. holds, note that $b_{k+1} < \sqrt{n}$ is equivalent to $\omega_k - q_k = \omega_k - \lfloor \omega_k\rfloor > 0$, which is true because $\omega_k$ is irrational. And \begin{align} && 0 &< b_{k+1} \\ &\iff& 0 &< q_k c_k - b_k \\ &\iff& \frac{b_k}{c_k} &< q_k\,. \end{align}

If $b_k < c_k$, then this is true because $q_k = \lfloor \omega_k\rfloor \geqslant 1$. And if $c_k \leqslant b_k$, then $c_k < \sqrt{n}$ and thus $$q_k = \biggl\lfloor \frac{\sqrt{n} + b_k}{c_k}\biggr\rfloor \geqslant \biggl\lfloor \frac{c_k + b_k}{c_k}\biggr\rfloor = 1 + \biggl\lfloor \frac{b_k}{c_k}\biggr\rfloor > \frac{b_k}{c_k}\,.$$

Having established $b_k \leqslant \lfloor\sqrt{n}\rfloor = a_0$ and $c_k > 0$ for all $k$, we see that

$$q_k = \biggl\lfloor \frac{\sqrt{n} + b_k}{c_k}\biggr\rfloor = \biggl\lfloor \frac{a_0 + b_k}{c_k}\biggr\rfloor \leqslant \biggl\lfloor \frac{2a_0}{c_k}\biggr\rfloor\,.$$

Thus $q_k \leqslant a_0$ unless $c_k = 1$. But if $c_k = 1$, then clearly $q_k = a_0 + b_k$, $b_{k+1} = a_0 = b_1$ and $c_{k+1} = n - a_0^2 = c_1$, i.e. $\omega_{k+1} = \omega_1$, which means $k$ is a multiple of the minimal period $l$.

Additionally, we see that $q_r = a_0$ if and only if $c_r = 2$ and $b_r = a_0$. Then we have $b_{r+1} = a_0 = b_r$ and $$c_rc_{r+1} = n - b_{r+1}^2 = n - b_r^2 = c_{r-1}c_r\,,$$ whence $c_{r+1} = c_{r-1}$. From this one finds $$b_{r+m} = b_{r+1-m} \qquad\text{and}\qquad c_{r+m} = c_{r-m}$$ as well as $q_{r+m} = q_{r-m}$ for $0 \leqslant m \leqslant r$ using the recursion $b_{k+1} = q_kc_k - b_k$ and $c_kc_{k+1} = n - b_{k+1}^2$. Thus if $q_r = a_0$, then $c_{2r} = c_0 = 1$ and $2r$ is a multiple of $l$. So $q_k = a_0$ can happen at most once in a period, and if it happens the period has even length and $q_{l/2} = a_0$.

$\endgroup$
  • $\begingroup$ Thanks! I figured out a proof very much like this as well in the mean time, except for the ‘$a_0$ can happen at most once’ part, but I did not have the time to write it up in prose yet. $\endgroup$ – Manuel Eberl Jul 6 '18 at 17:03
0
$\begingroup$

I am more comfortable with the Lagrange cycle description of this. The "partial quotients" are the absolute values of my $\delta$ in the example below. A "reduced" form is an ordered triple $\langle A,B,C \rangle$ that stands for the quadratic form $A x^2 + B xy + C y^2.$ The original description of "reduced" had more square roots in it, it suffices to say $$ AC < 0 \; \; \; \mbox{AND} \; \; \; B > |A+C| $$ as long as the discriminant is correct, $B^2 - 4 AC = \Delta.$ For Pell equation we have $\Delta = 4n$ from the (non-reduced) form $x^2 - n y^2.$ It follows that $B^2 < \Delta$ so $B < 2 \sqrt n \; .$

Given a reduced form $\langle A,B,C \rangle,$ the number I call $\delta$ has $$ \delta C > 0 \; \; \; \mbox{AND} \; \; \; |\delta| = \left\lfloor \; \left| \; \frac{B + \sqrt \Delta}{2C} \; \right| \; \right\rfloor \; \; . $$ I should emphasize that we find the integer part of $\sqrt \Delta$ once and for all, and use that every time $\delta$ is calculated. So this is integer arithmetic.

Now the numerator is less than $4 \sqrt n \; .$ IF $|C| = 1,$ then we are allowed to have $|\delta|$ as large as $2 \sqrt n.$ There is a special case for forms that do represent $-1,$ which happens when $n \equiv 1 \pmod 4$ is prime for example. I have my software continue to $x^2 - n y^2 = 1.$

Other than that, the vast majority of the time (and for you, all the time if you are just doing the continued fraction) we have $|C| \geq 2,$ therefore $|\delta| < \sqrt n \; .$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell 103


0  form   1 20 -3   delta  -6
1  form   -3 16 13   delta  1
2  form   13 10 -6   delta  -2
3  form   -6 14 9   delta  1
4  form   9 4 -11   delta  -1
5  form   -11 18 2   delta  9
6  form   2 18 -11   delta  -1
7  form   -11 4 9   delta  1
8  form   9 14 -6   delta  -2
9  form   -6 10 13   delta  1
10  form   13 16 -3   delta  -6
11  form   -3 20 1   delta  20
12  form   1 20 -3

 disc 412
Automorph, written on right of Gram matrix:  
3338  67257
22419  451718


 Pell automorph 
227528  2309157
22419  227528

Pell unit 
227528^2 - 103 * 22419^2 = 1 

=========================================

  2 
477^2 - 103 * 47^2 = 2 

=========================================

Probably more familiar, although still done with integer operations only:

Method described by Prof. Lubin at Continued fraction of $\sqrt{67} - 4$

$$ \sqrt { 103} = 10 + \frac{ \sqrt {103} - 10 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {103} - 10 } = \frac{ \sqrt {103} + 10 }{3 } = 6 + \frac{ \sqrt {103} - 8 }{3 } $$ $$ \frac{ 3 }{ \sqrt {103} - 8 } = \frac{ \sqrt {103} + 8 }{13 } = 1 + \frac{ \sqrt {103} - 5 }{13 } $$ $$ \frac{ 13 }{ \sqrt {103} - 5 } = \frac{ \sqrt {103} + 5 }{6 } = 2 + \frac{ \sqrt {103} - 7 }{6 } $$ $$ \frac{ 6 }{ \sqrt {103} - 7 } = \frac{ \sqrt {103} + 7 }{9 } = 1 + \frac{ \sqrt {103} - 2 }{9 } $$ $$ \frac{ 9 }{ \sqrt {103} - 2 } = \frac{ \sqrt {103} + 2 }{11 } = 1 + \frac{ \sqrt {103} - 9 }{11 } $$ $$ \frac{ 11 }{ \sqrt {103} - 9 } = \frac{ \sqrt {103} + 9 }{2 } = 9 + \frac{ \sqrt {103} - 9 }{2 } $$ $$ \frac{ 2 }{ \sqrt {103} - 9 } = \frac{ \sqrt {103} + 9 }{11 } = 1 + \frac{ \sqrt {103} - 2 }{11 } $$ $$ \frac{ 11 }{ \sqrt {103} - 2 } = \frac{ \sqrt {103} + 2 }{9 } = 1 + \frac{ \sqrt {103} - 7 }{9 } $$ $$ \frac{ 9 }{ \sqrt {103} - 7 } = \frac{ \sqrt {103} + 7 }{6 } = 2 + \frac{ \sqrt {103} - 5 }{6 } $$ $$ \frac{ 6 }{ \sqrt {103} - 5 } = \frac{ \sqrt {103} + 5 }{13 } = 1 + \frac{ \sqrt {103} - 8 }{13 } $$ $$ \frac{ 13 }{ \sqrt {103} - 8 } = \frac{ \sqrt {103} + 8 }{3 } = 6 + \frac{ \sqrt {103} - 10 }{3 } $$ $$ \frac{ 3 }{ \sqrt {103} - 10 } = \frac{ \sqrt {103} + 10 }{1 } = 20 + \frac{ \sqrt {103} - 10 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccccccccccc} & & 10 & & 6 & & 1 & & 2 & & 1 & & 1 & & 9 & & 1 & & 1 & & 2 & & 1 & & 6 & & 20 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 10 }{ 1 } & & \frac{ 61 }{ 6 } & & \frac{ 71 }{ 7 } & & \frac{ 203 }{ 20 } & & \frac{ 274 }{ 27 } & & \frac{ 477 }{ 47 } & & \frac{ 4567 }{ 450 } & & \frac{ 5044 }{ 497 } & & \frac{ 9611 }{ 947 } & & \frac{ 24266 }{ 2391 } & & \frac{ 33877 }{ 3338 } & & \frac{ 227528 }{ 22419 } \\ \\ & 1 & & -3 & & 13 & & -6 & & 9 & & -11 & & 2 & & -11 & & 9 & & -6 & & 13 & & -3 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 103 \cdot 0^2 = 1 & \mbox{digit} & 10 \\ \frac{ 10 }{ 1 } & 10^2 - 103 \cdot 1^2 = -3 & \mbox{digit} & 6 \\ \frac{ 61 }{ 6 } & 61^2 - 103 \cdot 6^2 = 13 & \mbox{digit} & 1 \\ \frac{ 71 }{ 7 } & 71^2 - 103 \cdot 7^2 = -6 & \mbox{digit} & 2 \\ \frac{ 203 }{ 20 } & 203^2 - 103 \cdot 20^2 = 9 & \mbox{digit} & 1 \\ \frac{ 274 }{ 27 } & 274^2 - 103 \cdot 27^2 = -11 & \mbox{digit} & 1 \\ \frac{ 477 }{ 47 } & 477^2 - 103 \cdot 47^2 = 2 & \mbox{digit} & 9 \\ \frac{ 4567 }{ 450 } & 4567^2 - 103 \cdot 450^2 = -11 & \mbox{digit} & 1 \\ \frac{ 5044 }{ 497 } & 5044^2 - 103 \cdot 497^2 = 9 & \mbox{digit} & 1 \\ \frac{ 9611 }{ 947 } & 9611^2 - 103 \cdot 947^2 = -6 & \mbox{digit} & 2 \\ \frac{ 24266 }{ 2391 } & 24266^2 - 103 \cdot 2391^2 = 13 & \mbox{digit} & 1 \\ \frac{ 33877 }{ 3338 } & 33877^2 - 103 \cdot 3338^2 = -3 & \mbox{digit} & 6 \\ \frac{ 227528 }{ 22419 } & 227528^2 - 103 \cdot 22419^2 = 1 & \mbox{digit} & 20 \\ \end{array} $$

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