# Lower bounds for period length of continued fraction of square root

EDIT: Dror answered this to my complete satisfaction. The simple continued fraction for $$\sqrt{n^2 + 1}$$ has length exactly the same, no dependence on $n$!!!!! No lower bound of the type I wanted is possible. The adjacent reduced indefinite binary quadratic forms in the complete cycle are $$\langle 1, \; 2 n, \; -1 \rangle$$ $$\langle -1, \; 2 n, \; 1 \rangle$$ $$\langle 1, \; 2 n, \; -1 \rangle$$ for a cycle length of 2.

The first nontrivial solution to the $+1$ Pell equation becomes $$(2 n^2 + 1)^2 - ( n^2 + 1) (2 n)^2 = 1$$

So no lower bound on cycle lengths can depend only on the approximate size of the number of which one is taking the square root, and all my crap below is useless. Oh, well, I put in the effort to write the question carefully, and I got an answer. There is still Dror's idea of short c.f's for $\sqrt n$ where $n$ avoids this kind of special pattern.

EDIT: evidently Schinzel studied these "sleepers, creepers, jeepers, etc." with known very short continued fraction lengths. So Dror had explicitly asked me whether I wanted to disregard those but I could not recognize the terminology and gave a misleading answer. So my method may be useless, but the revised question stands.

ORIGINAL QUESTION: This question began with Dror Speiser's answer to

Upper bound of period length of continued fraction representation of very composite number square root

Dror has some ideas on how to proceed. Here is what I had in mind when I mentioned it. This is a really open-ended problem, but should not be thought of as an open problem yet because I just made it up.

What I have in mind is the definition of some measurement of shortness $S(n)$ for the period length of the continued fraction for $\sqrt n$ where $n$ is a positive integer. Then I am hoping an optimization problem and for a sequence of numbers $n_t$ in the style of the colossaly abundant numbers, whereby $S(n_t)$ would automatically be better than $S(k)$ for any $k < n.$ The payoff could be explicit factorizations for the $n_t.$

A very nice paper on this is J. L. Nicolas, On highly composite numbers, pp. 215-244 in Ramanujan Revisited, Editors G. E. Andrews et al., Academic Press 1988. See also

http://en.wikipedia.org/wiki/Superabundant_number

http://en.wikipedia.org/wiki/Colossally_abundant_number

http://en.wikipedia.org/wiki/Highly_composite_number

http://en.wikipedia.org/wiki/Superior_highly_composite_number

Let me give some detail.

(I) The first step, and I am not utterly certain this is known, is do we even know for sure that the period lengths increase without bound? This would appear to be explicit in Golubeva (1991),

(II) Next we need some explicit increasing lower bound $f(n).$ Let us define $l(n)$ as the period length of the continued fraction for $\sqrt n$ where $n$ is a positive integer. Again, I do not know whether such a bound $f(n) \leq l(n)$ is known.

(III) Third is some tiny (but increasing) function $g(n)$ that grows so slowly that for any real $t > 1,$ $$\lim_{n \rightarrow \infty} \frac{(g(n))^t}{l(n)} = 0.$$ If it turns out to be suitable, we could just take $g(n) = \log f(n).$

(IV) It follows that $$\frac{(g(n))^t}{l(n)}$$ achieves a maximum. If the maximum is achieved by only one value of $n,$ then that is the definition of $n_t.$ If the maximum is achieved at more than one value, take $n_t$ to be the largest of these (at least that is what is done with the superior highly composite numbers, although the point is not made clear in the Nicolas article).

(V) If I have got the order correct on the inequalities, we would hope to get a sequence $n_t$ that is constant on intervals $t_1 < t < t_2$ but eventually increases. The jump points at which $n_t$ increases would be of interest. With any luck, some reasonable measure of surprising shortness would be improving as the $n_t$ increase. Finally, the most optimistic part of this is the possibility that, as in Nicolas and Alaoglu and Erdos before that and Ramanujan before that, there is an explicit factorization of $n_t.$

Well, thanks for reading this far.

-
$l(n) < 3.76\sqrt{n}\log(n))$. See R. G. Stanton, C. Sudler, Jr., and H. C. Williams, An Upper Bound for the period of the Simple Continued Fraction for $\sqrt{D}$, Pacific Journal of Mathematics , Vol. 67, No. 2, 1976, pp. 525-536. I also distinctively remember reading a paper saying something like $\sqrt{D}/R_o < l(n) < \sqrt{D}R_o$ but can't find it again (where $o$ is the order with discriminant associated to $D$ (which might be $4D$)). –  Dror Speiser Apr 30 '10 at 19:27
What I remember about the lower bound to do with the regulator is obviously wrong (think of $n^2+1$). Maybe it was more like $R_o/log(\sqrt{D}) < l(n) < R_o log(\sqrt{D})$. –  Dror Speiser Apr 30 '10 at 19:53
You mean 1. I think the question is a bit hard to understand, that's why I didn't realize you were looking for a lowest bound over all continued fractions. I thought you wanted to go over abundant discriminants or something. All's well that ends well :) –  Dror Speiser Apr 30 '10 at 20:46
Yeah, I had mapped out this whole plan. Note that estimating things for $n!$ is still a valid problem, just not one I know anything about. –  Will Jagy Apr 30 '10 at 22:07
There are plenty more non-square $k > 1$ for which $\sqrt{k}$ has continued fraction of period-length at most 2: precisely the integers $k = v(vm^2 + 4)/4$ with integers $v, m \ge 1$ such that $vm$ is even. (Taking $v = 1$ gives the family $k = n^2 + 1$.) –  BCnrd May 1 '10 at 2:28