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.

Improve this question
$\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$
    – Gerhard Paseman
    Commented 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$
    – Nikita Sidorov
    Commented Apr 16, 2015 at 19:06

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Gerald Edgar
    Commented 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
    Commented Apr 16, 2015 at 22:34
  • $\begingroup$ @GHfromMO Is there a relation between length of periods and factoring? $\endgroup$
    – VS.
    Commented Feb 13, 2020 at 15:12
  • $\begingroup$ @VS.: I don't know. $\endgroup$
    – GH from MO
    Commented Feb 13, 2020 at 15:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .