10
$\begingroup$

Let $d\ge 2$ and let $$ \sqrt d =[a_0; \overline{a_1,\dots, a_\ell, 2a_0}] $$ be its continued fraction expansion. Clearly, if $d=n^2+1$, then $\ell=0$, which gives the lower bound for $\ell$.

Question. What is the best known upper bound for $\ell=\ell(d)$ as a function of $d$?

For instance, $\ell(d)=O(d)$ is fairly trivial, following from the well-known algorithm (see [Rockett-Szusz], for instance). However, I suspect something like $O(\sqrt d)$ (or $O(\sqrt d\log d$) must be known.

$\endgroup$
2
  • $\begingroup$ What can you say about numbers $d$ where $l$ is 1 or 2? Is it conceivable that the upper bound is constant? Gerhard "If You Dream, Dream Big" Paseman, 2015.04.16 $\endgroup$ Apr 16, 2015 at 18:37
  • 1
    $\begingroup$ No, this is not possible. For instance, $\ell(2^{2k+1}\asymp 5^k$, according to E. Golubeva (1990). Apparently, this was already known in the 19th century. $\endgroup$ Apr 16, 2015 at 19:06

1 Answer 1

13
$\begingroup$

It is known that $\ell(d)=O(\sqrt{d}\log d)$ and $\ell(d)=\Omega(\sqrt{d}/\log\log d)$.

See Cohn's paper (free access) for more details.

For numerical results and some further historical comments see Williams's paper.

$\endgroup$
4
  • $\begingroup$ That $\Omega$ is not consistent with the cases of $\ell=0$ in the question. I think it actually says $\ell(d)$ is not $o(\sqrt{d}/\log\log d)$. $\endgroup$ Apr 16, 2015 at 21:53
  • $\begingroup$ @GeraldEdgar: In analytic number theory, $f(x)=\Omega(g(x))$ means that $f(x)=o(g(x))$ is false, and I followed that convention. See en.wikipedia.org/wiki/… $\endgroup$
    – GH from MO
    Apr 16, 2015 at 22:34
  • $\begingroup$ @GHfromMO Is there a relation between length of periods and factoring? $\endgroup$
    – VS.
    Feb 13, 2020 at 15:12
  • $\begingroup$ @VS.: I don't know. $\endgroup$
    – GH from MO
    Feb 13, 2020 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.