7
$\begingroup$

Ok, so it is quite amazing how the continued fractions for $\sqrt[2]{x}$ are always periodic for all whole numbers of $x$ (and where $x$ is not a perfect square): Here is a link I suggest at looking at: http://mathworld.wolfram.com/PeriodicContinuedFraction.html ...


The following is in the simple continued fraction form: $$\sqrt x = a_1+ \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{a_4 + \cfrac{1}{a_5 + \cfrac{1}{a_6 + \cfrac{1}{a_7 + \cdots}}}}}}$$

For example:

The continued fraction of $\sqrt 7$ is as follows: $[2;1,1,1,4,1,1,1,4,1,1,1,4,\ldots]$ the period in this case is $4$... and the continued fraction can be written as:

$$[2;\overline{1,1,1,4}]$$


Some other examples:

$\sqrt2 = [1;\overline{2}]$ Period is 1

$\sqrt3 = [1;\overline{1,2}]$ Period is 2

$\sqrt{13} = [3;\overline{1,1,1,1,6}]$ Period is 5

$\sqrt{97} = [9;\overline{1,5,1,1,1,1,1,1,5,1,18}]$ Period is 11


There are many other sources which show this... but why does this not work for others, such as cubic roots? I have written a java program to compute the continued fraction for the nth root of the numbers between $1$ and $100$ (excluding perfect squares,etc...) for the first 100 terms. Here are the results:

$\sqrt[2]{x}$: http://pastebin.com/ZcasfRyP

$\sqrt[3]{x}$: http://pastebin.com/XG9UF8hR

$\sqrt[4]{x}$: http://pastebin.com/Edp307SE

$\sqrt[5]{x}$: http://pastebin.com/9SwwPqUa


As you can see no period...

So why is it periodic for square roots, but not for others? An extension of the question: https://math.stackexchange.com/questions/1898902/periodic-continued-fractions-of-non-square-root-numbers-sqrtax-where-a

Kind Regards

Joshua Lochner

$\endgroup$
  • $\begingroup$ You've done a lot of work for this, and it's a good quality post and question in general. I hope you get the answer you're looking for! $\endgroup$ – Brevan Ellefsen Aug 20 '16 at 22:14
  • $\begingroup$ @BrevanEllefsen: the OP did a lot of work on writing up the question, but didn't look at the Wikipedia article on periodic continued fractions. which would have saved him or her the trouble. $\endgroup$ – Rob Arthan Aug 20 '16 at 22:17
  • $\begingroup$ Periodicity means that you can write for example, with $x=\sqrt{3}: $x=1+1/(1+1/2+x))$. But this yields a quadratic equation (it is important to remember this fact), which have (in general) a squlre root in the expression of its zeros, ans not a cubic root, etc... $\endgroup$ – Jean Marie Aug 20 '16 at 22:17
  • $\begingroup$ @BrevanEllefsen Thank you :) $\endgroup$ – Joshua Lochner Aug 20 '16 at 22:18
  • $\begingroup$ @RobArthan I have checked that out, but I would like to know 1. Why does this happen... and 2. Is there another way to write continued fractions of these irrational numbers? $\endgroup$ – Joshua Lochner Aug 20 '16 at 22:19
2
$\begingroup$

It's because periodicity of a simple continued fraction amounts to a quadratic equation. I will illustrate this by means of an example: $$ 7 + \cfrac 1 {2 + \cfrac 1 {3+\cfrac 1 {9 + \cdots\vphantom{\dfrac 1 1}}}} $$ and assume $2,\,3,\,9$ repeats. We have $$ 7,\ \overbrace{2,3,9,}\ \overbrace{2,3,9,}\ \overbrace{2,3,9,}\ \overbrace{2,3,9,}\ \ldots $$ This is $$ -2 + \left(9 + \cfrac 1 {2 + \cfrac 1 {3+\cfrac 1 {9 + \cdots\vphantom{\dfrac 1 1}}}} \right) \tag 1 $$ so that $9,\ 2,\ 3$ repeats right from the beginning.

Let $x = {}$the continued fraction in $(1)$, with $9,\ 2,\ 3$ repeating.

Then we get $$ x = 9 + \cfrac 1 {2 + \cfrac 1 {3 + \cfrac 1 x}} $$ Then, since $\dfrac 1 {3+\cfrac 1 x} = \dfrac x {3x+1}$, we have $$ x = 9 + \cfrac 1 {2 + \cfrac x {3x+1}}. $$ Now multiply the numerator and denominator of the fraction after $9+\cdots$ by $3x+1$, getting $$ x = 9 + \dfrac{3x+1}{7x+2} $$ so $$ x = \frac{66x+ 19}{7x+2}. $$ Multiply both sides by $7x+2$: $$ x(7x+2) = 66x+19. $$ And there you have a quadratic equation.

$\endgroup$
4
$\begingroup$

The easiest way to show this is the contrapositive: if a continued fraction is periodic then its value is a quadratic.

To see this, note that if we have $y = [a_1; a_2, a_3, \ldots, a_n, x]$ for reals $x,y$ and integers $a_i$, then we can write $y=\dfrac{mx+n}{px+q}$ for some integers $m, n, p, q$. (This is easy to prove by induction - note that if $z=[a_2; a_3, \ldots, a_n, x]$ $= \dfrac {m'x+n'}{p'x+q'}$, then $y=a_1+\dfrac1z$ $=a_1+\dfrac{p'x+q'}{m'x+n'}$ $=\dfrac{a_1m'x+a_1n'+p'x+q'}{m'x+n'}$ $=\dfrac{(a_1m'+p')x+(a_1n'+q')}{m'x+n'}$ is clearly of the required form.)

Now, if the continued fraction for $x$ is periodic then we have $x=[a_1; a_2, a_3, \ldots, a_n, x]$, so by the above there are integers with $x=\dfrac{mx+n}{px+q}$. But now multiply both sides by $px+q$ to get $px^2+qx=mx+n$, or $px^2+(q-m)x-n=0$, so that $x$ is a solution to this quadratic equation.

To answer the question about patterns in the continued fractions of other numbers: to the best of my knowledge, nothing is known about the continued fractions of e.g. cube roots — not even whether their coefficients are bounded! — though it's known that they can't grow too quickly: this is a corollary of Roth's Theorem, which bounds the so-called irrationality measure of algebraic numbers (how well they can be approximated by rationals). On the other hand, there is a special class of (transcendental) numbers for which more information on the continued fraction representation is known: certain Liouville numbers have continued fractions with complicated recursive (almost fractal) structures; see http://mathworld.wolfram.com/LiouvillesConstant.html and some of the references there for a little more information on this.

$\endgroup$
2
$\begingroup$

The idea is quite simple. Suppose that $$x=[a_0;\overline{a_1 , \dots , a_k}]$$ is a real number whose continued fraction is periodic. Then it satisfies the equation $$x- a_0= \frac{1}{a_1+\frac{1}{\frac{\dots}{a_{k-1}\frac{1}{a_k+(x-a_0)}}}}$$ which can be transformed by a quadratic equation. with integer coefficients. For example, the number $x=[2; \overline{1,4}]$ satisfies $$x-2= \frac{1}{1+\frac{1}{4+\frac{1}{x-2}}}$$ which is equivalent to the quadratic equation $$(x-2)(5x-9)=4x-7$$

So, all periodic numbers must be quadratic.

$\endgroup$
  • $\begingroup$ Interesting comment! Thanks :) ... $\endgroup$ – Joshua Lochner Aug 20 '16 at 22:48
  • 1
    $\begingroup$ You don't need to write $$ a + \frac 1 {b+\frac 1 {c + \frac 1 {d + \frac 1 e}}}. $$ You can write $$ a + \cfrac 1 {b+\cfrac 1 {c + \cfrac 1 {d + \cfrac 1 e}}}. $$ This is done by using \cfrac{}{}. $\qquad$ $\endgroup$ – Michael Hardy Aug 20 '16 at 22:49
  • $\begingroup$ An extension of the question: math.stackexchange.com/questions/1898902/… $\endgroup$ – Joshua Lochner Aug 21 '16 at 18:51
2
$\begingroup$

it does not work because, given a strictly periodic continued fraction, we can construct the 2 by 2 matrix that comes from it. Then we get the integer quadratic form that goes with that automorphism matrix. Finally, we get the "quadratic irrational" larger than one that goes with that.

Alright, we are dealing with an indefinite binary quadratic form, $$ f(x,y) = A x^2 + B xy + C y^2, $$ with positive non-square discriminant $$ \Delta = B^2 - 4AC. $$ We find the minimum solution $(\tau, \sigma)$ to the Pell type equation $$ \tau^2 - \Delta \sigma^2 = 4. $$ Then the matrix that generates the ($+1$) automorphism group of the form is $$ P = \left( \begin{array}{rr} \frac{\tau - B \sigma}{2} & -C \sigma \\ A \sigma & \frac{\tau + B \sigma}{2} \end{array} \right) $$

The Hessian matrix of the form is $$ H = \left( \begin{array}{rr} 2 A & B \\ B & 2C \end{array} \right) $$ and the automorphism matrices satisfy $$ P^T H P = H. $$ In the discussion below, the "quadratic irrational" that has that continued fraction comes from the quadratic formula going right to left, that is $$ \frac{-13 - \sqrt {345}}{-22} \approx 1.4351898 $$

Next, a CF that is "eventually periodic" is just a rearrangement of the quadratic irrational. Let me give a "reduced" quadratic form as example, give me a minute

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle 4 13 -11

  0  form              4          13         -11


           1           0
           0           1

To Return  
           1           0
           0           1

0  form   4 13 -11   delta  -1
1  form   -11 9 6   delta  2
2  form   6 15 -5   delta  -3
3  form   -5 15 6   delta  2     ambiguous  
4  form   6 9 -11   delta  -1
5  form   -11 13 4   delta  3
6  form   4 11 -14   delta  -1
7  form   -14 17 1   delta  17
8  form   1 17 -14   delta  -1     ambiguous  
9  form   -14 11 4   delta  3
10  form   4 13 -11


  form   4 x^2  + 13 x y  -11 y^2 

minimum was   1rep   x = 108   y = 155 disc 345 dSqrt 18  M_Ratio  20.25
Automorph, written on right of Gram matrix:  
-2029  -8008
-2912  -11493
=========================================

Given the matrix I call "Automorph," here is how we recover the form:

? m = [ 2029, 8008; 2912, 11493]
%2 = 
[2029 8008]

[2912 11493]

? matdet(m)
%3 = 1
? 2029 + 11493
%4 = 13522
? gcd(5,3)
%5 = 1
? gcd(2912, 8008)
%6 = 728
-
? tr = 2029 + 11493
%7 = 13522
? g = gcd(2912, 8008)
%8 = 728
? tr^2 - 4
%9 = 182844480

? rat = ( tr^2 - 4) / g^2
%12 = 345

? tr^2 - 345 * g^2
%14 = 4
? 
? a = 2912 / g
%16 = 4

? b = ( tr - 2 * 2029) / g
%18 = 13

? c = -8008 / g
%17 = -11

Given the purely periodic continued fraction with repeated part $$ 1,2,3,2,1,3,1,17,1,3, $$ the resulting matrix is the product of little 2 by 2 matrices:

? a1 = [0,1; 1,1]
%1 = 
[0 1]

[1 1]

? a2 = [0,1; 1,2]
%2 = 
[0 1]

[1 2]

? a3 = [0,1; 1,3]
%3 = 
[0 1]

[1 3]

? a17 = [0,1; 1,17]
%4 = 
[0 1]

[1 17]

? auto = a1 * a2 * a3 * a2 * a1 * a3 * a1 * a17 * a1 *a3
%5 = 
[2029 8008]

[2912 11493]

? 
$\endgroup$
  • 1
    $\begingroup$ I am sorry but it is very hard to follow you... I have a faint idea of what the matrix you are speaking about is but you should add a reference. About the program you give : I understand nothing. Please explain what you mean. $\endgroup$ – Jean Marie Aug 20 '16 at 22:21
  • $\begingroup$ @JeanMarie my favorite is Buell, Binary Quadratic Forms. Given the Hessian matrix $H$ of second partial derivatives, a matrix in the automorphism group of the form is some $P$ such that $P^T H P = H. $ Tell you what, could you give me, say, four positive integers, I will show you the resulting matrix and quadratic form that go with that strictly periodic continued fraction. $\endgroup$ – Will Jagy Aug 20 '16 at 22:44
  • 1
    $\begingroup$ Thanks for your answer and the reference. I understand a little now why you do that. But the output of your program is a little cryptic for the beotian (I think to me and to the OP, even more). A little reference, even not simple, as (iml.univ-mrs.fr/editions/biblio/files/lachaud/1988e.pdf) could be of some help for understanding what a quadratic form is and what it is here for. :) $\endgroup$ – Jean Marie Aug 20 '16 at 23:01
  • $\begingroup$ @JeanMarie thanks, that's nice. On page 33 he discusses the automorphism matrices. He does not seem to turn it around to say that a string of an even number of cf "digits" defines an automorphism matrix as a product of little 2 by 2 matrices, and this matrix can be used to reconstruct an underlying quadratic form. Finally, this gives a "quadratic irrational." I typed in more stuff in the answer above. $\endgroup$ – Will Jagy Aug 20 '16 at 23:25
  • 1
    $\begingroup$ Thanks : the explanations you give in your new version are very helpful. $\endgroup$ – Jean Marie Aug 20 '16 at 23:35

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.