596 – Continued fractions | A kind of library

596 – Continued fractions

This term, Summer Hansen is taking a reading course with me on Pell’s equation. Our basic reference is:

Jacobson and Williams, Solving the Pell equation. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York, 2009. xx+495 pp. ISBN: 978-0-387-84922-5.

We are allowing a rather organic approach to the material, taking as many detours as it seems appropriate. The topic of continued fractions naturally came up. What follows is just a short compendium of results I found interesting while reading on the subject.

1. Simple continued fractions

Throughout this note, ${x}$ is real and irrational.

Recall that the (simple) continued fraction of ${x}$ is given by

$\displaystyle x=a_0+\frac1{a_1+\frac1{a_2+\frac1{\ddots}}},$

where the ${a_i}$ are defined recursively using the following algorithm:

Let ${x_0=x}$ .
Given ${x_n}$ , set ${a_n=\lfloor x_n\rfloor}$ .
Let ${x_{n+1}=\frac1{x_n-a_n}}$ .

We denote the continued fraction above by ${[a_0;a_1,\dots]}$ and note that ${a_i>0}$ for ${i>0}$ . The fraction is understood as the limit of the convergents ${[a_0,\dots,a_n]}$ , typically denoted ${p_n/ q_n}$ with ${q_n>0}$ , ${p_n,q_n\in{\mathbb Z}}$ and relatively prime.

It is well known that the sequence ${(p_{2n}/q_{2n}\mid n\ge0)}$ is strictly increasing and converges to ${x}$ , while the sequence ${(p_{2n+1}/q_{2n+1}\mid n\ge0)}$ is strictly decreasing, also converging to ${x}$ .

If ${x}$ satisfies a polynomial equation of degree 2 with rational coefficients, we say that ${x}$ is a quadratic irrational. The following is a famous theorem of Lagrange:

Theorem 1 (Lagrange) The continued fraction of ${x}$ is eventually periodic iff ${x}$ is a quadratic irrational.

That ${x}$ is eventually periodic means that, in the notation above, there is a smallest positive integer ${s}$ such that ${a_{n+s}=a_n}$ for all ${n}$ sufficiently large, say ${n\ge k+1}$ . We then write

$\displaystyle x=[a_0;a_1,\dots,a_k,\overline{a_{k+1},\dots,a_{k+s}}]$

and call ${s}$ the length of the period of ${x}$ .

The following is Theorem 3 in page 317 of Sierpinski, Elementary theory of numbers. Second edition. Edited and with a preface by Andrzej Schinzel. North-Holland Mathematical Library, 31. North-Holland Publishing Co., Amsterdam; PWN—Polish Scientific Publishers, Warsaw, 1988. xii+515 pp. ISBN: 0-444-86662-0.

Theorem 2 Suppose that ${x=\sqrt n}$ for some (non-square) positive integer ${n}$ . Then we can take ${k=0}$ in the expression above, i.e., ${x=[a_0;\overline{a_1,\dots,a_s}]}$ . Moreover, ${a_s=2\lfloor \sqrt n\rfloor=2a_0}$ , and ${a_1,\dots,a_{s-1}}$ is symmetric.

In fact, the theorem holds iff ${n}$ is a (non-square) positive rational. For example,

$\displaystyle \sqrt{\frac53}=[1;\overline{3,2}]$

and

$\displaystyle \sqrt{1000} = [31; \overline{1, 1, 1, 1, 1, 6, 2, 2, 15, 2, 2, 15,2,2,6,1,1,1,1,1,62}].$

In what follows, I restrict my attention to ${x}$ of the form ${\sqrt n}$ , ${n}$ an integer.

It is natural to ask whether something can be said about the length of the period ${s}$ , or about its parity.

2. The length of the period

About the first question, Sierpinski remarks that ${s<2n}$ . Significant improvements have been made here. For an example, I quote from MathReviews:

MR1042614 (91c:11045).

Rockett, Andrew M.; Szüsz, Peter.
On the lengths of the periods of the continued fractions of square-roots of integers.
Forum Math. 2 (1990), no. 2, 119–123.

On the basis of computer calculations [B. D. Beach and H. C. Williams, in Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 1971), 133-146, Louisiana State Univ., Baton Rouge, 1971; MR0321880 (48 #245); D. R. Hickerson, Pacific J. Math. 46 (1973), 429-432; MR0321881 (48 #246)] it was once conjectured that ${s}$ , the length of the period of the simple continued fraction expansion for ${\sqrt n}$ , is ${O(\sqrt n)}$ .

The last upper estimate for ${s}$ is ${O(\sqrt n\log (n/a^2))}$ , where ${n/a^2}$ is squarefree; it was found by R. G. Stanton, C. Sudler, Jr. and Williams [ibid. 67 (1976), no. 2, 525-536; MR0429724 (55 #2735)]. Using the unproven zeta-hypothesis, E. V. Podsypanin [Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 82 (1979), 95-99; MR0537024 (80h:12002)] has shown that ${s=O(\sqrt n\log\log n)}$ .

In the present paper the authors prove that for “most” ${n}$ , the relation ${s=O(\sqrt n)}$ holds. The proof is based on Chebyshev’s inequality in probability theory and on Selberg’s upper bound sieve.

Reviewed by Oto Strauch

Actually, Podsypanin’s result is somewhat more precise, but understanding his bound requires knowledge of algebraic number theory. Namely, he proves that if ${s}$ the length of the period of a quadratic irrational generating an order with fundamental unit ${\varepsilon}$ , then

$\displaystyle s<\log\varepsilon/(\log(1+5^{1/2})/2).$

The bound mentioned above comes from estimating ${\log\varepsilon}$ (assuming the Riemann hypothesis).

Orders and units are discussed in detail in Chapter 4 of the Jacobson-Williams book. Here I just review the definitions.

Let ${K}$ be the field ${{\mathbb Q}(\sqrt n)}$ . There is a unique positive integer ${a}$ such that ${n_0=n/ a^2}$ is a square free integer. Let

$\displaystyle \omega=\left\{\begin{array}{cl} \sqrt{n_0}&\mbox{ if }n_0\not\equiv1\pmod4,\\ \displaystyle \frac{1+\sqrt{n_0}}2&\mbox{ if }n_0\equiv1\pmod4. \end{array} \right.$

Clearly, ${K={\mathbb Q}(\omega)}$ . Recall that an algebraic integer is a number that is a root of a polynomial with integer coefficients. One can check that the algebraic integers that belong to ${K}$ are precisely the numbers of the form ${a+b\omega}$ , where ${a,b\in{\mathbb Z}}$ . The following is not the usual definition but coincides with it for our purposes:

Definition 3 An order of ${K}$ is a subring ${{\mathcal O}\subseteq K}$ containing 1 and such that for some ${m \in{\mathbb Z}}$ , ${{\mathcal O}=\{a+bm\omega\mid a,b\in{\mathbb Z}\}}$ .

A unit of an order ${{\mathcal O}}$ is an element ${\eta}$ of ${{\mathcal O}}$ that divides 1, i.e., such that for some ${\alpha\in{\mathcal O}}$ , we have ${1=\eta\alpha}$ . One can check that there is a unit ${\varepsilon}$ that generates all units in ${{\mathcal O}}$ in the sense that for any unit ${\eta}$ there is an ${n\in{\mathbb Z}}$ such that ${\eta=\pm\epsilon^n}$ . We call ${\varepsilon}$ the fundamental unit of ${{\mathcal O}}$ .

In fact, let

$\displaystyle \bar\omega=\left\{\begin{array}{cl} -\sqrt{n_0}&\mbox{ if }n_0\not\equiv1\pmod4,\\ \displaystyle \frac{1-\sqrt{n_0}}2&\mbox{ if }n_0\equiv1\pmod4, \end{array} \right.$

be the conjugate of ${\omega}$ . The discriminant of ${{\mathcal O}}$ is ${\Delta=m^2(\omega- \bar\omega)^2\in{\mathbb Z}}$ . Every element of ${{\mathcal O}}$ has the form

$\displaystyle x+\left(\frac{\Delta+\sqrt{\Delta}}2\right)y$

for some integers ${x,y}$ .

If ${\eta}$ is a unit, then ${(2x+y\Delta)^2-y^2\Delta=\pm4}$ . Letting ${X=2x+y\Delta}$ , ${Y=y}$ , and ${ \sigma=\pm1}$ , accordingly, we see that

$\displaystyle X^2-\Delta Y^2=4\sigma.$

From the basic theory of the Pell equation, there is a fundamental solution ${(X_1,Y_1,\sigma_1)}$ to this equation, in the sense that for any solution ${(Z',Y',\sigma')}$ , we have

$\displaystyle \frac{X'+Y'\sqrt{\Delta}}2=\pm\left(\frac{X_1+Y_1\sqrt{\Delta}}2\right)^n$

for some ${n\in{\mathbb Z}}$ . We can take ${\varepsilon=(X_1+Y_1\sqrt{\Delta})/2}$ .

3. The parity of ${s}$

Results on the parity of the length ${s=s(n)}$ of the period of the continued fraction of ${\sqrt n}$ are very interesting. In ${n=p}$ is a prime number, it is a classical result that ${s}$ is odd iff ${p=2}$ or ${p\equiv 1\pmod 4}$ . (See also Aicardi’s third paper below.)

When ${n}$ is not a prime, we do not have a full characterization of the parity of ${s(n)}$ , but there is a significant amount of recent research in the area, starting with work of V.I. Arnold, who proved:

Theorem 4 If ${s(n)}$ is odd, then ${n}$ is a sum of two squares. The converse does not hold.

This can be found in Vladimir I. Arnold, Lengths of periods of continued fractions of square roots of integers, Funct. Anal. Other Math. (2009) 2, 151–164.

Arnold’s results and conjectures have been extended by Francesca Aicardi in a series of papers:

Symmetries of quadratic form classes and of quadratic surd continued fractions. Part I: A Poincaré tiling of the de Sitter world, Bull. Braz. Math. Soc., New Series (2009) 40(3), 301–340.
Symmetries of quadratic form classes and of quadratic surd continued fractions. Part II: Classification of the periods’ palindromes, Bull. Braz. Math. Soc., New Series (2010) 41(1), 83–124.
The continued fractions of the square roots of integers: on the parity of the length of their period, Funct. Anal. Other Math. (2010) 3, 1–19.
Red numbers and quadratic field, Funct. Anal. Other Math. (2011) 3 103–112.

The first two papers establish the theoretical framework used in the other two to obtain results on the parity of ${s}$ . The terminology “red” is Arnold’s, who calls an integer red iff its period is odd.

Among the results obtained by Aicardi, I mention the following:

Theorem 5

If ${n}$ is divisible by a prime ${p\equiv 3\pmod 4}$ , or by 4, then ${s(n)}$ is even.

If ${s(n)}$ is odd, then the sum of the elements of the period of the continued fraction of ${\sqrt n}$ is even. A partial converse holds: If the sum is even, and ${n}$ is prime, then ${s(n)}$ is is odd.

Additional results require more notation. Given an irrational ${x=a+b\sqrt D}$ with ${a,b\in{\mathbb Q}}$ , we can write

$\displaystyle x=\frac{-k+\sqrt{k^2-4mn}}{2m}$

for some integers ${m,k,n}$ relatively prime. The discriminant of ${x}$ is ${\Delta=k^2-4mn}$ . For such ${x}$ , write ${s(x)}$ for the parity of the length of the period of its continued fraction.

Theorem 6 If ${r,t\in{\mathbb Q}(\sqrt n)}$ are irrationals with the same discriminant, then ${s(r)}$ and ${s(t)}$ have the same parity.

Theorem 7 Let ${x\in{\mathbb Q}(\sqrt n)}$ be irrational, where ${n}$ is square free. Let ${\Delta(x)}$ be the discriminant of ${x}$ . Then:

If ${n\equiv 3\pmod 4}$ , ${s(x)}$ is even,

if ${n\equiv 2\pmod 4}$ , then ${s(x)}$ is odd iff ${\Delta(x)=4l^2n}$ for some integer ${l}$ such that ${s(l^2n)}$ is odd.

If ${n\equiv 1\pmod 4}$ , then ${s(x)}$ is odd iff ${\Delta(x)=4l^2n}$ or ${l^2n}$ for some odd integer ${l}$ such that ${s(l^2n)}$ is odd.

I do not know of additional results, but numerical evidence suggests that the density of integers ${n}$ with ${s(n)}$ even is rather small. Aicardi computed ${s(n)}$ for ${n<50000}$ , finding that for about ${3\%}$ of the integers ${n}$ in this range, we have that ${s(n)}$ is even.

Typeset using LaTeX2WP. Here is a printable version of this post.

This entry was posted on Monday, October 10th, 2011 at 5:52 pm and is filed under 496/596: Independent study. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to 596 – Continued fractions

Analysis – Some remarks on continued fractions | A kind of library says:

September 18, 2013 at 3:47 pm

[…] A few nice additional results on continued fractions, with references, are given in this blog entry. […]

Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library