04 June 2009

Odd periods in continued fractions

Here's a question. Why is the period of the quotients in the continued fraction of N1/2 "usually" even? For example, if N runs over the ninety non-squares less than 100, then only 20 times does the continued fraction expansion of N1/2 have an odd period. Of the 992 non-squares less than 1024, 157 have an odd period. Of the 9900 squares less than 104, 1322 have an odd period. This is a sign that something is going on under the hood -- naively you'd expect half the periods to be odd.

Arnold has observed this, but only empirically; I first observed it from this problem from Project Euler.

The period of the continued fraction of N1/2 is odd if and only if x2 - Ny2 = -1 has solutions in integers. All such integers, it turns out, have no prime factors congruent to 3 mod 4, which is pretty rare for large numbers. (The number of positive integers less than N with no prime factors congruent to 3 mod 4 is about N(log N)-1/2.) For integers having no prime factors congruent to 3 mod 4, though, a paper of Etienne Fouvry and Jurgen Kluners shows that asymptotically at least 52% of such numbers have odd period, and at most two-thirds do.

3 comments:

Emmanuel Kowalski said...

The paper(s) of Fouvry and Klueners have links to the original conjecture of P. Stevenhagen -- based on strong heuristics -- that proposed a conjecture and model for this problem:

"The Number of Real Quadratic Fields Having Units of Negative Norm", in Experimental Math. (1993)

Arnold, unfortunately, ignores this completely.

Michael Lugo said...
This comment has been removed by the author.
Michael Lugo said...

Emmanuel, thanks for the pointer.