ON THE LENGTH OF THE CONTINUED FRACTION OF \sqrt{q}

J. B. Conrey

The formula for the class number of a real quadratic field of discriminant d is given by

h(d) = \frac{L(1, χ_{d})\sqrt{d}}{log ϵ_{d}}

where χ_{d} is the quadratic character associated with the field and ϵ_{d} is the fundamental unit of the field. It was conjectured by Gauss that this class number is 1 for infinitely many d. Numerical evidence strongly supports Gauss’ conjecture. However, in this direction it is only known that h(d) < cd^{1/2}(log d)^{−3} holds for some c > 0 and infinitely many d.

The Riemann Hypothesis for L(s, χ_{d}), implies that

\frac{1}{log log d} ≪ L(1, χ_{d}) ≪ log log d.

Thus, the main part of the order of magnitude of h(d) is controlled by log ϵ_{d}.

We can give an explicit formula for ϵ_{d} in terms of the continued fraction of \sqrt{d}. Consider the continued fraction expansion of \sqrt{d}. It is known that the expansion is periodic after the first term, and that the last term of the period is equal to twice the first term of the expansion. Also, the periodic part, except for the last term, is symmetric. Thus, we can express the continued fraction expansion of \sqrt{d} as

\sqrt{d} = [n; \overline{a_{1}, a_{2}, …, a_{k−1}, a_{k}, a_{k−1}, …, a_{2}, a_{1}, 2n}]

or as

\sqrt{d} = [n; \overline{a_{1}, a_{2}, …, a_{k−1}, a_{k}, a_{k}, a_{k−1}, …, a_{2}, a_{1}, 2n}]

where n = [\sqrt{d}]. In most of what we do it won’t matter which of these two forms appear, so we will write either simply as

\sqrt{d} = [n; \overline{a_{1}, a_{2}, …, a_{2}, a_{1}, 2n}]

Then the fundamental unit ϵ_{d} is given by

ϵ_{d} = (n, a_{1}, a_{2}, …, a_{2}, a_{1}) + \sqrt{d}(a_{1}, …, a_{1})

where the (.) notation can be defined recursively by () = 1, (x) = x, and

(a_{1}, …, a_{k}) = a_{k}(a_{1}, …, a_{k−1}) + (a_{1}, …, a_{k−2}).

Typeset by AMS-TEX

Supported in part by an NSF grant

It is easy to see that

F_{k+1} ≤ (a_{1}, …, a_{k}) ≤ F_{k+1}(max{a_{1}, …, a_{k}})^{k}

where F_{k} is the kth Fibonacci number, so that

ℓ(d) ≪ log ϵ_{d} ≪ ℓ(d) log d

where ℓ(d) denotes the length of the period of the continued fraction expansion of \sqrt{d}, which, for this paper, we take to be the number of a_{i}, ignoring the 2n at the end of the period. Hence, a good estimate for h(d) really hinges on the length of the continued fraction expansion of \sqrt{d}.

Approaches in the past have included attempts to construct thin sets of d for which ℓ(d) is large. Yamamoto has done this; his work leads to the bound for h(d) mentioned above. In general, it is difficult to unhinge log ϵ_{d} from h(d).

In this paper, we study the distribution of the numbers ℓ(d). That is, for a fixed value ℓ, we calculate the number c_{ℓ}(N) of d < (N + 1)^{2} for which ℓ(d) = ℓ. We conjecture that for each ℓ there exists a c_{ℓ} > 0 such that

c_{ℓ}(N) ∼ c_{ℓ}N(log N)^{s_{ℓ}}

where s_{ℓ} is 0 in the case that the norm of the fundamental unit is -1 (i.e. ℓ even) and is 1 in the case that the norm of the fundamental unit is 1 (the case where ℓ is odd). Moreover, we conjecture that the ratios c_{ℓ}(N)/(N log N) are uniformly bounded. We present some numerical evidence to support this conjecture. We remark that this conjecture implies that h(d) ≪ (log d)^{3} for a positive proportion of d.

We are able to verify this conjecture for 0 ≤ ℓ ≤ 4. Also, we can obtain reasonable bounds for c_{5}(N). In addition, we analyze the structure of the problem and indicate a method which could give some insight into the general case.

Basic Properties of (.) The first few values of (.) are:

() = 1  (x) = x  (x, y) = xy + 1  (x, y, z) = xyz + x + z

(x, y, z, w) = xyzw + xw + zw + xy + 1

The connection between the [.] and the (.) notations is given by

[b_{0}; b_{1} …, b_{k}] = \frac{(b_{0}, …, b_{k})}{(b_{1}, …, b_{k})}.  (1)

Next, there is a more general recursion formula:

(b_{1}, …, b_{k}) = (b_{1}, …, b_{r})(b_{r+1}, …, b_{k}) + (b_{1}, …, b_{r−1})(b_{r+2}, …, b_{k}) (2)

for any r with 0 ≤ r ≤ k. One can prove this easily by induction. Suppose all such rules hold for expressions (.) with fewer than k arguments. Then,

(b_{1}, …, b_{k}) = b_{k}(b_{1}, …, b_{k−1}) + (b_{1}, …, b_{k−2})

= b_{k}{(b_{1}, …, b_{r})(b_{r+1}, …, b_{k−1}) + (b_{1}, …, b_{r−1})(b_{r+2}, …, b_{k−1})}

+ (b_{1}, …, b_{k−2})
= (b_{1}, …, b_{r}){(b_{r+1}, …, b_{k}) − (b_{r+1}, …, b_{k−2})}
+ (b_{1}, …, b_{r−1}){(b_{r+2}, …, b_{k}) − (b_{r+2}, …, b_{k−2})}
+ (b_{1}, …, b_{k−2})
= (b_{1}, …, b_{r})(b_{r+1}, …, b_{k}) + (b_{1}, …, b_{r−1})(b_{r+2}, …, b_{k})
+ {(b_{1}, …, b_{k−2}) − (b_{1}, …, b_{r})(b_{r+1}, …, b_{k−2})
− (b_{1}, …, b_{r−1})(b_{r+2}, …, b_{k−2})}

as desired. A particular case of this with r = 1 shows that the basic recursion formula can be applied from the front of an expression (.):

(b_{1}, …, b_{k}) = b_{1}(b_{2}, …, b_{k}) + (b_{3}, …, b_{k}).  (3)

This leads to the fact that (.) is unchanged when the arguments are reversed:

(b_{1}, …, b_{k}) = (b_{k}, …, b_{1})  (4)

as is easily seen by induction: Assuming the reversal property for lengths smaller than k, we have

\begin{aligned}(b_{1}, …, b_{k}) & = b_{k}(b_{1}, …, b_{k−1}) + (b_{1}, …, b_{k−2}) \\ & = b_{k}(b_{k−1}, …, b_{1}) + (b_{k−2}, …, b_{1}) \end{aligned}

= (b_{k}, …, b_{1}).

Finally, we show that

(b_{1}, …, b_{k})(b_{2}, …, b_{k+1}) − (b_{1}, …, b_{k+1})(b_{2}, …, b_{k}) = (−1)^{k}.  (5)

For the left hand side of the above is

= (b_{1}, …, b_{k}){(b_{2}, …, b_{k})b_{k+1} + (b_{2}, …, b_{k−1})}
− (b_{1}, …, b_{k+1})(b_{2}, …, b_{k})
= (b_{2}, …, b_{k}){(b_{1}, …, b_{k+1}) − (b_{1}, …, b_{k−1})}
+ (b_{1}, …, b_{k})(b_{2}, …, b_{k−1}) − (b_{1}, …, b_{k+1})(b_{2}, …, b_{k})
= −{(b_{1}, …, b_{k−1})(b_{2}, …, b_{k}) − (b_{1}, …, b_{k})(b_{2}, …, b_{k−1})}
= ⋯ = (−1)^{k−1}{(b_{1})(b_{2}) − (b_{1}b_{2})()} = (−1)^{k}.

Using these properties we can prove

4 J. B. CONREY

Lemma 1. Suppose that

\sqrt{q} = [n; \overline{a_{1}, a_{2}, …, a_{2}, a_{1}, 2n}].

Then

q = \frac{(n, a_{1}, …, a_{1}, n)}{(a_{1}, …, a_{1})}.

q = n^{2} + \frac{(2n, a_{1}, a_{2}, …, a_{2})}{(a_{1}, …, a_{1})}.

Proof. It is easy to see that

\sqrt{q} = [n; a_{1}, a_{2}, …, a_{2}, a_{1}, n + \sqrt{q}].

By (1), we have

\sqrt{q} = \frac{(n, a_{1}, …, a_{1}, n + \sqrt{q})}{(a_{1}, …, a_{1}, n + \sqrt{q})}.

By the recursive property, we then find

\sqrt{q} = \frac{(n + \sqrt{q})(n, a_{1}, …, a_{1}) + (n, a_{1}, …, a_{2})}{(n + \sqrt{q})(a_{1}, …, a_{1}) + (a_{1}, …, a_{2})}

which leads to

\sqrt{q} = \frac{\sqrt{q}(n, a_{1}, …, a_{1}) + (n, a_{1}, …, a_{1}, n)}{\sqrt{q}(a_{1}, …, a_{1}) + (a_{1}, …, a_{1}, n)}.

Now we have an equation

\sqrt{q} = \frac{A\sqrt{q} + B}{C\sqrt{q} + A} .

This expression simplifies to q = B/C. Thus, we have the formula

q = \frac{(n, a_{1}, …, a_{1}, n)}{(a_{1}, …, a_{1})}.

We remark that the point of this paper really is to count how often the expression

\frac{(n, a_{1}, …, a_{1}, n)}{(a_{1}, …, a_{1})}

is an integer. We write this in a slightly different form. Corollary. With the above notation,

q = n^{2} + \frac{(2n, a_{1}, a_{2}, …, a_{2})}{(a_{1}, …, a_{1})}.

Proof. We note that by several applications of the recursion formula, at least once from each end, we have

(n, a_{1}, …, a_{1}, n) = n(a_{1}, …, a_{1}, n) + (a_{2}, …, a_{1}, n)

= n^{2}(a_{1}, …, a_{1}) + n(a_{1}, …, a_{2}) + n(a_{2}, …, a_{1}) + (a_{2}, …, a_{2})

= n^{2}(a_{1}, …, a_{1}) + 2n(a_{1}, …, a_{2}) + (a_{2}, …, a_{2})
= n^{2}(a_{1}, …, a_{1}) + (2n, a_{1}, …, a_{2}).

The statement of the Corollary now follows.

In order to count the q with a given length of continued fraction expansion, we will instead count the number of n and a_{i} for which

(a_{1}, …, a_{1}) | (2n, a_{1}, a_{2}, …, a_{2}).

In order to be sure that this gives an accurate count for the q, we need to know that each q can be expressed in at most one way as

q = n^{2} + \frac{(2n, a_{1}, a_{2}, …, a_{2})}{(a_{1}, …, a_{1})}.

Strictly speaking, this is not completely true. If we accidentally took two periods instead of 1 from the continued fraction expansion of \sqrt{q} we would arrive at a different expression. However, in that expression, at least one of the a_{i} would be equal to 2n. However, it is known that the a_{i} that form the smallest period satisfy a_{i} ≤ n. With this extra proviso, the expression for q above is unique, since all of the steps in the proofs of Lemma 1 and its Corollary are reversible.

Lemma 2. Let q be a positive integer, q not equal to a perfect square. Then there is a unique positive integer n and a unique symmetric tuple (a_{1}, …, a_{1}) of positive integers with a_{i} ≤ n such that

q = \frac{(n, a_{1}, …, a_{1}, n)}{(a_{1}, …, a_{1})} = n^{2} + \frac{(2n, a_{1}, a_{2}, …, a_{2})}{(a_{1}, …, a_{1})}.

We can now give an expression for c_{ℓ}(N), namely

c_{ℓ}(N) = ∑_{n≤N} ∑_{\begin{matrix}a_{1},...,a_{k}≤n \\ (a_{1},...,a_{1})|(2n,a_{1},...,a_{2}) \end{matrix}} 1

where k = [ℓ/2]. This expression can be rewritten as

c_{ℓ}(N) = ∑_{a_{1},...,a_{k}≤N} ∑_{\begin{matrix}max\{a_{i}\}≤n≤N \\ (2n,a_{1},...,a_{2})≡0 mod (a_{1},...,a_{1}) \end{matrix}} 1.

The congruence condition can be expressed as

2n(a_{1}, …, a_{2}) ≡ −(a_{2}, …, a_{2}) mod (a_{1}, …, a_{1}).

Now applying (5) we find that

(a_{1}, …, a_{2})(a_{2}, …, a_{1}) − (a_{1}, …, a_{1})(a_{2}, …, a_{2}) = (−1)^{ℓ−1}.

In particular,

(a_{1}, …, a_{2})^{2} ≡ (−1)^{ℓ−1} mod (a_{1}, …, a_{1}).

Thus, our problem is reduced to counting the sets of a_{i} ≤ N and n ≤ N with n ≥ a_{i} for each i such that

2n ≡ (−1)^{ℓ}(a_{1}, …, a_{2})(a_{2}, …, a_{2}) mod (a_{1}, …, a_{1}).

We give some examples for small ℓ.

Proposition. We have the following estimates:

c_{0}(N) = N
c_{1}(N) ∼ \frac{3}{2}N log N
c_{2}(N) ∼ (\frac{π}{4} coth \frac{π}{2} − \frac{1}{2}) N
c_{3}(N) < 2ζ(2)N log N
c_{4}(N) ≪ N
c_{5}(N) ≪ N log^{3} N.

Proof.

For ℓ = 0 we have \sqrt{q} = [n; \overline{2n}] so that q = n^{2} + 1 and so c_{0}(N) = N.

For ℓ = 1 we have \sqrt{q} = [n; \overline{x, 2n}] so that

q = n^{2} + \frac{2n}{x}

and

c_{1}(N) = ∑_{n≤N} ∑_{\begin{matrix}x≤n \\ x|2n \end{matrix}} 1

= ∑_{n≤N}(d(2n) − 1).

This sum can be evaluated elementarily, or we can observe that

\begin{aligned}∑_{n=1}^{∞} \frac{d(2n)}{n^{s}} & = 2^{s} ∑_{n even} \frac{d(n)}{n^{s}} \\ & = 2^{s} (ζ(s)^{2} − (1 − 2^{−s})^{2}ζ(s)^{2}) \end{aligned}

= 2(1 − 2^{−s−1})ζ(s)^{2}

so that

c_{1}(N) = ∑_{n≤N} d(2n) + O(N) ∼ \frac{3}{2}N log N.

For ℓ = 2 we have \sqrt{q} = [n; \overline{x, x, 2n}] so that

q = n^{2} + \frac{(2n, x)}{(x, x)} = n^{2} + \frac{2nx + 1}{x^{2} + 1}

and using x^{2} ≡ −1 mod x^{2} + 1,

c_{2}(N) = ∑_{x≤N} ∑_{\begin{matrix}x≤n≤N \\ 2n≡x mod x^{2}+1 \end{matrix}} 1

= ∑_{n≤N} ∑_{\begin{matrix}x≤n,M≥1 \\ 2n=x+M(x^{2}+1) \end{matrix}} 1.

The condition M ≥ 1 is necessary to ensure that x ≤ n. Note that x and M must both be even. We substitute x = 2y, M = 2L and find that

c_{2}(N) = ∑_{n≤N} ∑_{\begin{matrix}y≤n/2 \\ n=y+L(4y^{2}+1) \end{matrix}} 1

= ∑_{y+L(1+4y^{2}≤N} 1 = ∑_{1+y+4y^{2}≤N} ∑_{L≤ \frac{N−y}{1+4y^{2}}} 1

= ∑_{1+y+4y^{2}≤N} (\frac{N − y}{1 + 4y^{2}} + O(1))

= N ∑_{y=1}^{∞} \frac{1}{1 + 4y^{2}} + O(N^{1/2} log N).

Hence,

c_{2}(N) = N (\frac{π}{4} coth \frac{π}{2} − \frac{1}{2}) + O(n^{1/2})

in a fairly straightforward way through Cauchy’s Theorem applied to a contour integral of (cot πz)/(1 + 4z^{2}). Note that the constant here is = 0.356 ….

For ℓ = 3 we have \sqrt{q} = [n; \overline{x, y, x, 2n}] so that

q = n^{2} + \frac{(2n, x, y)}{(x, y, x)} = n^{2} + \frac{2n(1 + xy) + y}{2x + x^{2}y} .

This leads to

c_{3}(N) = ∑_{x,y≤N} ∑_{\begin{matrix}x,y≤n≤N \\ 2n≡−y(1+xy) mod 2x+x^{2}y \end{matrix}} 1.

The condition on n requires that

2n = Lx(2 + xy) − y(1 + xy) = y + (Lx − y)(2 + xy)

for some L. Let M = Lx − y. Clearly, M > 0, or else 2n = y + M(xy + 2) < 0. Also, M > 0 ensures that x, y ≤ n. Our sum is now

c_{3}(N) = ∑_{\begin{matrix}0<y+M(xy+2)<2N \\ y+M(xy+2) even \\ M+y≡0 mod x \end{matrix}} 1.

We handle this sum with the following lemma.

Lemma 3. We have

∑_{\begin{matrix}kmn≤x \\ m+n≡0 mod k \end{matrix}} 1 = ζ(2)x log x + O(x)  (6)

where the sum is over positive integers k, m, n.

Proof. We consider the generating function

∑_{m+n≡0 mod k} \frac{1}{(kmn)^{s}} = ∑_{k} \frac{1}{k^{s}} ∑_{a=1}^{k} ∑_{n≡−a mod k} \frac{1}{n^{s}} ∑_{m≡a mod k} \frac{1}{m^{s}} .

In the innermost sum we replace m by mk+a, factor out k^{−s}, and add and subtract a term (m + 1)^{−s} to see that the above is

= ∑_{k} \frac{1}{k^{2s}} ∑_{a=1}^{k−1} ∑_{n≡−a mod k} \frac{1}{n^{s}} ∑_{m=0}^{∞} (\frac{1}{(m + a/k)^{s}} − \frac{1}{(m + 1)^{s}} )

+ ζ(s)^{2}ζ(2s).

Note that the term corresponding to a = k is 0. The sum over m is

= ∑_{m=0}^{∞} ∫_{m+a/k}^{m+1} su^{−s−1} du

and is majorized by

∫_{a/k}^{∞} su^{−s−1} du = (a/k)^{−s}.

Thus, the generating function is ζ(s)^{2}ζ(2s) plus a term which is majorized by

∑_{k} \frac{1}{k^{s}} ∑_{a=1}^{k−1} \frac{1}{a^{s}} ∑_{n≡−a mod k} \frac{1}{n^{s}} .

This expression is, in turn, majorized by

∑_{k} \frac{1}{k^{s}} ∑_{a=1}^{k−1} \frac{1}{a^{s}} (\frac{1}{(k − a)^{s}} + k^{−s}ζ(s)) .

It is not difficult to see that this function has a simple pole at s = 1 with a bounded residue. Thus, we conclude that

∑_{\begin{matrix}k,m,n \\ k|m+n \end{matrix}} \frac{1}{(kmn)^{s}} = ζ(s)^{2}ζ(2s) + Z(s)

for a function Z(s) which has at worst a simple pole at s = 1. From this analysis the claim follows.

We apply the claim to the sum in question, and obtain an upper bound

c_{3}(N) ≤ ∑_{\begin{matrix}Mxy≤2N \\ M+x≡0 mod y \end{matrix}} 1 ∼ 2ζ(2)N log N + O(N).

It should be possible to get an asymptotic formula here with more work. Next we take up the case of ℓ = 4. Here we have \sqrt{q} = [n; \overline{x, y, y, x, 2n}] and

q = n^{2} + \frac{(2n, x, y, y)}{(x, y, y, x)} = n^{2} + \frac{2n(x + y + xy^{2}) + (1 + y^{2})}{(1 + xy)^{2} + x^{2}}.

Then,

c_{4}(N) = ∑_{x,y≤N} ∑_{\begin{matrix}x,y≤n≤N \\ 2n≡(1+y^{2})(x+y+xy^{2}) mod ((1+xy)^{2}+x^{2}) \end{matrix}} 1

Here we are only aiming for an upper bound of the order of magnitude N, so we immediately make some simplifying assumptions. First of all,

c_{4}(N) ≤ ∑_{0<(1+y^{2})(x+y+xy^{2})−M((1+xy)^{2}+x^{2})<2N} 1

where x and y are positive integers ≤ N and M is any integer. (Clearly, the complicated expression in the condition of summation is supposed to be 2n. We have relaxed the condition that this expression is even and that x and y be smaller than n which is why we have an inequality rather than equality.) The terms with M < 0 make a contribution which is

≪ ∑_{|M|x^{2}y^{2}≤2N} 1 ≪ N.

The terms with M = 0 contribute

≪ ∑_{xy^{4}≤2N} 1 ≪ N.

Now we consider the terms with M > 0. We let

g = y^{2} + 1 − Mx  (7)

and

h = gy − M.  (8)

We then have to estimate

∑_{0<gx+h(1+xy)<2N} 1

where x and y are positive integers ≤ N and g and h are constrained by the equations (7) and (8). We claim that g > 0 and h ≥ 0. First of all, 2n = g(x + y + xy^{2}) − M(1 + xy), so that M > 0 and 2n > 0 imply that g > 0. Next, suppose that h < 0. Then, gy < M ≤ Mx ≤ y^{2} so that g ≤ y. But, 2n = h(1 + xy) + gx > 0 implies that gx > (−h)(1 + xy) > (−h)xy ≥ xy so that g > y. This contradiction implies that h ≥ 0.

We now estimate the contribution from the terms with h = 0. This condition implies that M = gy so that g(1 + xy) = y^{2} + 1 or y^{2} − gxy + (1 − g) = 0. Thus, each pair (g, x) leads to at most 2 values of y. In fact, most pairs (g, x) will not give a solution y since that requires the discriminant g^{2}x^{2} + 4g − 4 will not usually be a square. In fact,

g^{2}x^{2} + 4g − 4 = u^{2}

implies that

(gx − u)(gx + u) = 4 − 4g.

We may as well assume that u ≥ 0. Then (gx + u) | (4 − 4g) implies that x ≤ 4. Thus, we see that the contribution from these h = 0 terms is

≪ ∑_{\begin{matrix}gx≤2N \\ g^{2}x^{2}+4g−4= square \end{matrix}} 1 ≪ ∑_{\begin{matrix}gx≤2N \\ x≤4 \end{matrix}} 1 ≪ N.

Now we turn our attention to the case g > 0, h > 0. Eliminating M from (7) and (8) gives

g(1 + xy) = y^{2} + 1 + xh.

Thus, given h, x, and y, the value of g is determined. Also, we see that

hx ≡ −1 − y^{2} mod (1 + xy)

whence

h ≡ y^{3} + y mod (1 + xy).

Thus, the sum in question is

≪ ∑_{\begin{matrix}hxy≪N \\ h≡y^{3}+y mod (1+xy) \end{matrix}} 1.

We remark that this sum is trivially

≪ ∑_{xy≪N} (\frac{N}{(xy)^{2}} + 1) ≪ N log N.

So, we are trying to save a log N.

We can do this, but the argument is rather lengthy, and we omit it for the time being.

Now let us consider the case ℓ = 5. We have

\sqrt{q} = [n; \overline{x, y, z, y, x, 2n}]

and

q = \frac{(n, x, y, z, y, x, n)}{(x, y, z, y, x)} = n^{2} + \frac{(2n, x, y, z, y)}{(x, y, z, y, x)}.

The condition that q is an integer translates to the congruence condition:

2n ≡ −(x, y, z, y)(y, z, y) mod (x, y, z, y, x).

So, we need to count how many n ≤ N satisfy the above for some set of x, y, z ≤ n. We will only be looking for an upper bound of the order of magnitude N log^{3} N.

We resort to a factorization that is available for odd ℓ. Namely, if ℓ = 2k − 1, then

(a_{1}, …, a_{k}, …, a_{1}) = (a_{1}, …, a_{k})(a_{k−1}, …, a_{1}) + (a_{1}, …, a_{k−1})(a_{k−2}, …, a_{1})
= (a_{1}, …, a_{k−1}){(a_{1}, …, a_{k}) + (a_{1}, …, a_{k−2})}.

Then, the congruence

2n ≡ −(a_{1}, …, a_{2})(a_{2}, …, a_{2}) mod (a_{1}, …, a_{1})

reduces to a pair of simultaneous congruences:

\{ \begin{matrix}2n & ≡ −R mod (a_{1}, …, a_{k−1}) \\ 2n & ≡ R mod \{(a_{1}, …, a_{k}) + (a_{1}, …, a_{k−2})\} \end{matrix}

where

R = (a_{2}, …, a_{k−1}){(a_{2}, … a_{k}) + (a_{2}, …, a_{k−2})}.

In the case ℓ = 5 this leads to

\{ \begin{matrix}2n & ≡ 2y + y^{2}z mod 1 + xy \\ 2n & ≡ −(2y + y^{2}z) mod 2x + z + xyz \end{matrix}

We can derive most of our bound from the second of these congruences, simply ignoring the first one except in one case. The second congruence implies that 2n = M(2x + z + xyz) − (2y + y^{2}z) for some M. Clearly, M > 0. Put g = Mx − y. Then,

2n = Mz + g(yz + 2).

We claim that g ≥ 0. Suppose that g < 0. Then Mx − y = g ≤ −1 so that y ≥ Mx + 1. Also, Mz + g(yz + 2) ≥ 1 so that

Mz ≥ (−g)(yz + 2) + 1 ≥ yz + 3 ≥ z(Mx + 1) + 3 ≥ Mxz + z + 3

which is a contradiction. Therefore, g ≥ 0. The terms with g > 0 contribute an amount which is

≪ ∑_{\begin{matrix}0<Mz+g(yz+2)<2N \\ g=Mx−y \end{matrix}} 1 ≪ ∑_{gxy≪N} ∑_{Mx=g+y} 1.

This sum can be handled similarly to the situation that arose in the ℓ = 3 case, leading to a bound O(N log^{3} N) by using

Lemma 4. We have

∑_{mn≤x} \frac{d(m + n)}{mn} ∼ \frac{1}{2}x log^{2} x.

Proof. The proof is almost the same as that of Lemma 3. The relevant generating function is

∑_{m,n} \frac{d(m + n)}{(mn)^{s}} = ∑_{m,n} \frac{1}{(mn)^{s}} ∑_{k|m+n} 1

= ∑_{k} ∑_{a=1}^{k} ∑_{n≡−a mod k} \frac{1}{n^{s}} ∑_{m≡a mod k} \frac{1}{m^{s}}

= ∑_{k} \frac{1}{k^{s}} ∑_{a=1}^{k−1} ∑_{n≡−a mod k} \frac{1}{n^{s}} ∑_{m=0}^{∞} (\frac{1}{(m + a/k)^{s}} − \frac{1}{(m + 1)^{s}} )

+ ζ(s)^{3}.

We continue as before and deduce the Lemma.

For the terms with g = 0, we need to use the first congruence as well. In this case, we have Mx = y and our system may be written as

\{ \begin{matrix}2n & ≡ (Mx, z, Mx) mod (x, Mx) \\ 2n & ≡ −(Mx, z, Mx) mod (x, Mx, z) + x \end{matrix}

This system simplifies to

\{ \begin{matrix}2n & ≡ −zM + 2Mx mod Mx^{2} + 1 \\ 2n & ≡ zM mod Mx^{2}z + 2x + z \end{matrix}

Then, 2n = zM + r(Mx^{2}z + 2x + z) for some r ≥ 0. The contribution of terms with r > 0 is

≪ ∑_{rzMx^{2}≪N} 1 ≪ N log^{2} N.

If r = 0, then 2n = Mz so that the first congruence implies that

2Mx ≡ 2Mz mod Mx^{2} + 1.

The contribution of these terms is

≪ ∑_{\begin{matrix}2n=Mz≪N \\ y=Mx≪N \\ 2x≡2z mod Mx^{2}+1 \end{matrix}} 1

≪ ∑_{Mx≪N} 1 + ∑_{\begin{matrix}Mx≪N,Mz≪N \\ z=x+s(Mx^{2}+1)/2 \end{matrix}} 1 ≪ N log N.

Larger ℓ.

We can begin the ℓ = 6 case, but can’t quite estimate the relevant sums. Perhaps it is instructive to include our partial work here. We have

\sqrt{q} = [n; \overline{x, y, z, z, y, x, 2n}].

We have to count the number of x, y, z, M such that

0 < 2n = (x, y, z, z, y)(y, z, z, y) − M(x, y, z, z, y, x) << N.

Note, the terms with M ≤ 0 contribute ≪ N. We let

g = (y, z, z, y) − Mx.

Clearly, if m ≤ 0 then g > 0. Now,

2n = g(x, y, z, z, y) − M(x, y, z, z).

Therefore, if M > 0, then g > 0. Hence, it is always the case that g > 0. Next, we let

h = M − gy.

Then,

2n = g(x, y, z) − h(x, y, z, z).

Note that g(1 + xy) = (y, z, z, y) − hx; in particular, g | (y, z, z, y) − hx, and that M is determined once g, h, y are given. Thus, the terms here with h < 0 contribute

≪ ∑_{hxyz^{2}≪N} (.(y, z, z, y) − hx) ≪ N^{1+ϵ}.

If h = 0, then M = gy and these terms contribute

≪ ∑_{gxyz≪N} 1 ≪ N log^{3} N.

Let

i = g − hz.

Note that if h ≤ 0, then i > 0. Also,

2n = i(x, y, z) − h(x, y).

So, if h > 0, then i > 0. Thus, in all cases i > 0. Now, let

j = h − iz.

Then

2n = ix − j(x, y).

Finally, let k = i − jy. Then,

2n = kx − j.

We claim that j < 0. For, we calculate that

\begin{aligned}M & = h + gy = (h + (i + hz)y = h(1 + yz) + iy = h(y, z) + iy \\ & = (iz + j)(y, z) + iy = i(z(y, z) + y) + j(y, z) = i(y, z, z) + j(y, z) \end{aligned}

= (k + jy)(y, z, z) + j(y, z) = j(y, z, z, y) + k(y, z, z).

Thus,

g = (y, z, z, y) − Mx = (y, z, z, y)(1 − xj) − kx(y, z, z).

Suppose that j > 0. Then it must be the case that k < 0, since g > 0. But then 2n = kx − j < 0 which is a contradiction. Hence, j < 0 as claimed.

We also note that we can show that

k = q − n^{2} = \frac{(2n, x, y, z, z, y)}{(x, y, z, z, y, x)}.

This argument works in the general case, too. Consider

\sqrt{q} = [n; \overline{a_{1}, …, a_{1}, 2n}].

Let us consider the case that ℓ is even. We have to count the n ≤ N such that

2n = (a_{1}, …, a_{2})(a_{2}, …, a_{2}) − g_{0}(a_{1}, …, a_{1}).

Here, g_{0} is arbitrary. However, the terms with g_{0} ≤ 0 cause no difficulty. We make substitutions:

g_{1} = (a_{2}, …, a_{2}) − g_{0}a_{1}
g_{2} = g_{0} − g_{1}a_{2}
g_{3} = g_{1} − g_{2}a_{3}
…
g_{k} = g_{k−2} − g_{k−1}a_{k}
g_{k+1} = g_{k−1} − g_{k}a_{k}
…
g_{2k−1} = g_{2k−3} − g_{2k−2}a_{2}
g_{2k} = g_{2k−2} − g_{2k−1}a_{1}.

These substitutions lead to

2n = g_{1}(a_{1}, …, a_{2}) − g_{0}(a_{1}, …, a_{3})
= g_{1}(a_{1}, …, a_{4}) − g_{2}(a_{1}, …, a_{3})
= g_{3}(a_{1}, …, a_{4}) − g_{2}(a_{1}, …, a_{5})
= g_{3}(a_{1}, …, a_{6}) − g_{4}(a_{1}, …, a_{5})
…
= g_{k}(a_{1}, …, a_{k}) − g_{k−1}(a_{1}, …, a_{k−1})
= g_{k}(a_{1}, …, a_{k−2}) − g_{k+1}(a_{1}, …, a_{k−1})
…
= g_{2k−3}(a_{1}, a_{2}, a_{3}) − g_{2k−4}(a_{1}, a_{2})
= g_{2k−3}(a_{1}) − g_{2k−2}(a_{1}, a_{2})
= g_{2k−1}(a_{1}) − g_{2k−2} = −g_{2k}.

When we put all of the substitutions together, we can solve for g_{0} as follows:

g_{0} = g_{2} + g_{1}a_{2}
= g_{3}(a_{2}) + g_{2}(a_{2}, a_{3})
= g_{4}(a_{2}, a_{3}) + g_{3}(a_{2}, a_{3}, a_{4})
= …
= g_{2k−1}(a_{2}, …, a_{2}) + g_{2k−2}(a_{2}, …, a_{3})
= g_{2k}(a_{2}, …, a_{1}) + g_{2k−1}(a_{2}, …, a_{2}).

We claim that g_{1} > 0. For if g_{0} ≤ 0 then the assertion follows from the substitution equation for g_{1}; if g_{0} > 0, then the assertion follows from the equation for 2n in terms of g_{1} and g_{0}. Similarly, g_{i} > 0 for all odd i.

Now we claim that g_{2k−2} < 0. By combining

g_{1} = (a_{2}, …, a_{2}) − g_{0}a_{1}

and

g_{0} = g_{2k−1}(a_{2}, …, a_{2}) + g_{2k−2}(a_{2}, …, a_{3})

to eliminate g_{0}, we obtain

g_{1} = (a_{2}, …, a_{2})(1 − g_{2k−2}a_{1}) − g_{2k−1}a_{1}(a_{2}, …, a_{3}).

Thus, if g_{2k−2} > 0, then g_{2k−1} < 0. But then 2n = g_{2k−1}(a_{1}) − g_{2k−2} < 0 which is a contradiction. Therefore, g_{2k−2} < 0 as claimed.

Now let t = −g_{2k−2} > 0. The significance of this inequality is that we have an equation

2n = g_{2k−3}a_{1} − g_{2k−2}(a_{1}, a_{2}) = g_{2k−3}a_{1} + t(a_{1}, a_{2}),

in which all the terms are positive. To rephrase the original question, we have to count how many solutions (a_{1}, …, a_{k}, g_{0}, …, g_{2k−1} there are to

0 < g_{2k−3}a_{1} + t(a_{1}, a_{2}) ≪ N

subject to all of the substitution equations, and subject to 0 < a_{i} ≤ N for each i. It might be of interest to note also that

g_{2k−1} = q − n^{2} = \frac{(2n, a_{1}, …, a_{2})}{(a_{1}, …, a_{1})}.

To see this, recall, from the last expression for 2n that 2n = −g_{2k}. By the last formula for g_{0},

g_{0} = g_{2k}(a_{2}, …, a_{1}) + g_{2k−1}(a_{2}, …, a_{2})
= −2n(a_{2}, …, a_{1}) + g_{2k−1}(a_{2}, …, a_{2}).

But,

2n = (a_{1}, …, a_{2})(a_{2}, …, a_{2}) − g_{0}(a_{1}, …, a_{1}).

Eliminating g_{0} from these two equations gives

2n = (a_{1}, …, a_{2})(a_{2}, …, a_{2}) − g_{2k−1}(a_{1}, …, a_{1})(a_{2}, …, a_{2})
+ 2n(a_{1}, …, a_{1})(a_{2}, …, a_{2}).

This simplifies to

g_{2k−1}(a_{1}, …, a_{1})(a_{1}, …, a_{2}) = 2n(a_{1}, …, a_{2})^{2} + (a_{1}, …, a_{2})(a_{2}, …, a_{2})

or

g_{2k−1} = \frac{(2n, a_{1}, …, a_{2})}{(a_{1}, …, a_{1})}.

Concluding Remarks. Why should we expect the conjectures to be true? The simple answer is that when we count how many n ≤ N satisfy the congruence

2n ≡ (−1)^{ℓ}(a_{1}, …, a_{2})(a_{2}, …, a_{2}) mod (a_{1}, …, a_{1})

we expect there to be about

\frac{N}{(a_{1}, …, a_{1})}

solutions. When we sum this over all ℓ-tuples (a_{1}, …, a_{1}) with a_{i} ≤ N we get ≈ N for even ℓ and ≈ N log N for odd ℓ. The log N factor occurs in the odd case because the a_{k} in the middle of (a_{1}, …, a_{1}) appears only once and ∑_{a_{k}≤N} \frac{1}{a_{k}} ∼ log N.

The uniform boundedness of the implicit constants is suggested by the graphs below.

Two questions motivated by this work are as follows.

(1) Show that

∑_{max\{a_{i}\}≤N} \frac{1}{(a_{1}, …, a_{1})} ≪ N log^{s_{ℓ}}

holds uniformly in ℓ, where s_{ℓ} = 0 for ℓ even, and s_{ℓ} = 1 for ℓ odd.

(2) Let f_{3}(n) stand for the number of triples (x, y, z) of positive integers such

that

n = (x, y, z) = xyz + x + z.

Show that

f(n) ≪_{ϵ} n^{ϵ}

for any ϵ > 0.

Finally, we present some data in graphical form. The horizontal axis has lengths ℓ of continued fractions. Above each integer on the horizontal axis, there is a dot at the height which is equal to the number of q ≤ 10^{5} for which ℓ(q) = ℓ. The first graph has even ℓ, the second graph has odd ℓ, and the third graph has all ℓ. odd ℓ, and both combined.

18 J. B. CONREY ON THE LENGTH OF THE CONTINUED FRACTION OF \sqrt{q} 19 20 J. B. CONREY