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, is real and irrational.
Recall that the (simple) continued fraction of is given by
where the are defined recursively using the following algorithm:
- Let .
- Given , set .
- Let .
We denote the continued fraction above by and note that for . The fraction is understood as the limit of the convergents , typically denoted with , and relatively prime.
It is well known that the sequence is strictly increasing and converges to , while the sequence is strictly decreasing, also converging to .
If satisfies a polynomial equation of degree 2 with rational coefficients, we say that is a quadratic irrational. The following is a famous theorem of Lagrange:
Theorem 1 (Lagrange) The continued fraction of is eventually periodic iff is a quadratic irrational.
That is eventually periodic means that, in the notation above, there is a smallest positive integer such that for all sufficiently large, say . We then write
and call the length of the period of .
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 for some (non-square) positive integer . Then we can take in the expression above, i.e., . Moreover, , and is symmetric.
In fact, the theorem holds iff is a (non-square) positive rational. For example,
In what follows, I restrict my attention to of the form , an integer.
It is natural to ask whether something can be said about the length of the period , or about its parity.
2. The length of the period
About the first question, Sierpinski remarks that . Significant improvements have been made here. For an example, I quote from MathReviews:
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 , the length of the period of the simple continued fraction expansion for , is .
The last upper estimate for is , where 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 .
In the present paper the authors prove that for “most” , the relation 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 the length of the period of a quadratic irrational generating an order with fundamental unit , then
The bound mentioned above comes from estimating (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 be the field . There is a unique positive integer such that is a square free integer. Let
Clearly, . 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 are precisely the numbers of the form , where . The following is not the usual definition but coincides with it for our purposes:
Definition 3 An order of is a subring containing 1 and such that for some , .
A unit of an order is an element of that divides 1, i.e., such that for some , we have . One can check that there is a unit that generates all units in in the sense that for any unit there is an such that . We call the fundamental unit of .
In fact, let
be the conjugate of . The discriminant of is . Every element of has the form
for some integers .
If is a unit, then . Letting , , and , accordingly, we see that
From the basic theory of the Pell equation, there is a fundamental solution to this equation, in the sense that for any solution , we have
for some . We can take .
3. The parity of
Results on the parity of the length of the period of the continued fraction of are very interesting. In is a prime number, it is a classical result that is odd iff or . (See also Aicardi’s third paper below.)
When is not a prime, we do not have a full characterization of the parity of , but there is a significant amount of recent research in the area, starting with work of V.I. Arnold, who proved:
Theorem 4 If is odd, then 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 . 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:
- If is divisible by a prime , or by 4, then is even.
- If is odd, then the sum of the elements of the period of the continued fraction of is even. A partial converse holds: If the sum is even, and is prime, then is is odd.
Additional results require more notation. Given an irrational with , we can write
for some integers relatively prime. The discriminant of is . For such , write for the parity of the length of the period of its continued fraction.
Theorem 6 If are irrationals with the same discriminant, then and have the same parity.
Theorem 7 Let be irrational, where is square free. Let be the discriminant of . Then:
- If , is even,
- if , then is odd iff for some integer such that is odd.
- If , then is odd iff or for some odd integer such that is odd.
I do not know of additional results, but numerical evidence suggests that the density of integers with even is rather small. Aicardi computed for , finding that for about of the integers in this range, we have that is even.
Typeset using LaTeX2WP. Here is a printable version of this post.
[…] A few nice additional results on continued fractions, with references, are given in this blog entry. […]