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.

  • $\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$ – Gerhard Paseman Apr 16 '15 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$ – Nikita Sidorov Apr 16 '15 at 19:06

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.

  • $\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$ – Gerald Edgar Apr 16 '15 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 '15 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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