Let $d$ be a positive, non-square integer, and define $c_d$ to be the smallest positive number with the following property: for all pairs of co-prime integers $(p,q)$ with $q > 0$, the inequality

$$\displaystyle \left \lvert \frac{p}{q} - \sqrt{d} \right \rvert > \frac{c_d}{q^2}$$

holds. The existence of such a number follows from Lagrange's theorem that the continued fraction expansion of a quadratic irrational is eventually periodic.

It follows from Hurwitz's theorem that $c_d < \dfrac{1}{\sqrt{5}}$ for all $d$.

Does anyone have a reference for the size of $c_d$? One can assume that the fundamental solution $(u_0, v_0)$ to the equation $x^2 - dy^2 = \pm 4$ is known.


Edit: I answered a different question than the one asked. The question asks for the least $c_d = q^2|\sqrt{d}-p/q|$. I evaluated the liminf.

If $d = a^2+b$ with $1\le b \le 2a$ then the simple continued fraction for $\sqrt{d}$ is preperiodic, and the period ends with $2a$, which is the largest coefficient, with $a$ being the second largest, and the rest of the period is a palindrome. I believe these classical results are in Hardy and Wright, An Introduction to the Theory of Numbers.

We can represent $\sqrt{d}$ as a terminating simple continued fraction if we allow the last coefficient to be irrational, containing the rest of the simple continued fraction, instead of an integer.

$\alpha = [a_0;a_1,...,a_n,...] = [a_0;a_1,...,a_n,[a_{n+1};a_{n+2},...]]$. Let $a_{n+1}' = [a_{n+1};a_{n+2},...]$.

If $[a_0;a_1,...,a_n] = p_n/q_n$ and then $\alpha = \frac{a_{n+1}'p_n + p_{n-1}}{a_{n+1}'q_n + q_{n-1}}$ so $$\bigg|\alpha - \frac{p_n}{q_n}\bigg| = \frac{1}{q_n(a_{n+1}'q_n + q_{n-1})} = \frac{1}{q_n^2} \frac{1}{a_{n+1}' + \frac{q_{n-1}}{q_n}}$$

So, we want to determine the liminf of $\frac{1}{a_{n+1}' + q_{n-1}/q_n}$ For $\alpha = \sqrt{a^2+b}$, or equivalently, the limsup of the reciprocal $a_{n+1}' + q_{n-1}/q_n$. The only values greater than $2a$ occur just before the period ends, when the next coefficient is $2a$, where $a_{n+1}' = a+\sqrt{a^2+b}$. The continued fraction of $q_{n-1}/q_n$ is $[0;a_n,a_{n-1},...,a_1]$ so the limit is $\sqrt{a^2+b}-a$, which means $$\frac{1}{a_{n+1}' + q_{n-1}/q_n} \to \frac{1}{2\sqrt{a^2+b}} = \frac{1}{2\sqrt{d}} = c_d.$$

If we want the infimum instead of the liminf, we get slightly lower values. Then $$c_d = \frac{1}{\frac{p}{q} + \sqrt{d}}$$

where (p,q) is the smallest nontrivial solution to $p^2-dq^2=1$. This is a convergent to the simple continued fraction just before the end of the first period if the period is even, and just before the end of the second period if the period is odd.

For example, $\sqrt{3} = [1; \overline{1,2}]$ has an even period length, so $[1;1]=2 \gt \sqrt{3}$. Then $c_3=1^2|2-\sqrt{3}| = \frac{1}{2+\sqrt{3}} \lt \frac{1}{2\sqrt{3}}$. $\sqrt{2} = [1;\overline{2}]$, so $p/q = [1;2] = 3/2 \gt \sqrt{2}$, and $c_2=2^2(3/2-\sqrt{2}) = \frac{1}{3/2 + \sqrt{2}} \lt \frac{1}{2\sqrt{2}}$.

The computation above still applies. The only candidates are convergents just before the period ends. If $p_n/q_n$ is the convergent just before the period ends, then $q_n^2|p_n/q_n - \sqrt{d}| = \frac{1}{a_{n+1}' + q_{n-1}/q_n}$ and $q_{n-1}/q_n$ has a continued fraction that consists of $0$ followed by repetitions of the period of the simple continued fraction for $\sqrt{d}$, with the last $2a$ missing. This is a convergent to the simple continued fraction of the fractional part $\sqrt{d}-\lfloor \sqrt{d} \rfloor$. When $n$ is odd, $q_{n-1}/q_n > \sqrt{d}-\lfloor \sqrt{d} \rfloor$, and the odd convergents decrease toward $\sqrt{d} - \lfloor \sqrt{d} \rfloor$ so the maximum occurs at the first occurence of an odd index just before a period ends.

  • 2
    $\begingroup$ Well, Noam Elkies answered the right question, correctly, faster, and in far fewer words. This proof might be helpful, though. $\endgroup$ – Douglas Zare Aug 8 '16 at 1:13

This feels like the kind of thing that's easier to figure out than find in the literature. Seems that the optimal $c_d$ comes from the minimal positive solution of $p^2 - d \, q^2 = +1$, and is thus less than $\frac1{2\sqrt d}$ but very close to $\frac1{2\sqrt d}$ if the fundamental solution is at all large.

  • $\begingroup$ Can you elaborate on the statement "Seems that the optimal $c_d$ comes from the minimal positive solution of $p^2 - dq^2 = +1$"? This seems to be close to exactly what I want $\endgroup$ – Stanley Yao Xiao Aug 7 '16 at 22:29
  • 2
    $\begingroup$ Well $q^2 \left| \frac p q - \sqrt d \right|$ is approximately $|p^2 - d \, q^2| / (2 \sqrt d)$ for large $p,q$, and since we can attain $p^2 - d \, q^2 = \pm 1$ that's the way to go (once we check that even small solutions of $p^2 - d \, q^2 = 2$ can't do better). Units of norm $-1$ do a bit worse than $1 / (2 \sqrt d)$, and units of norm $+1$ do a bit better, the difference decreasing with $p$ and $q$. So the smallest $+1$ solution yields the best $c_d$. $\endgroup$ – Noam D. Elkies Aug 7 '16 at 23:37
  • 1
    $\begingroup$ (and if you want the $\liminf$, not the smallest number that works for all $(p,q)$, then the same argument gives $1/(2\sqrt d)$, as Douglas Zare meanwhile wrote as well. The $1 / \sqrt 5$ bound is attained only by irrationals equivlent to the Golden Ratio, which doesn't arise here, not even for $d=5$.) $\endgroup$ – Noam D. Elkies Aug 7 '16 at 23:38

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.