Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The classic Hurwitz theorem for rational approximations (in simplest form; the constant can of course be improved) gives infinitely many approximations $\frac mn$ to an irrational $\alpha$ with $|\frac mn-\alpha|\lt\frac1{n^2}$. Just recently, in trying to answer a question related to rational approximation of $\pi$ I tripped over a limitation of this theorem: it tells us nothing about the specific $m,n$ of an approximation. I'm interested in $n$ particularly, and wondering if there are any 'Dirichlet-style' results that say that for any irrational $\alpha$ and for any $a, d$ we can get good approximations (in the sense above) with $n\equiv a\pmod d$. Is this a known result?

share|improve this question
The best rational approximations are the continued fractions of $\alpha$. –  Christian Remling Jun 10 '14 at 2:31
@ChristianRemling More specifically, the convergents of that continued fraction - but it's possible to have 'good' approximations that aren't convergents, and it's certainly not true that convergents have to be in all residue classes. (For instance, the convergents for $\sqrt{2}$ have no $n\equiv 3\bmod 4$) –  Steven Stadnicki Jun 10 '14 at 2:35
Do you want $m$ and $n$ to be coprime? –  Douglas Zare Jun 10 '14 at 3:14
You may check this paper fq.math.ca/Scanned/34-1/elsner.pdf and references given there. –  duje Jun 10 '14 at 5:17
Although this answers a somewhat different question: it is known that almost all $\alpha$ satisfy a `Dirichlet-style' result as you mention. In fact, we know good asymptotics for how often $n$ should fall into a given arithmetic progression. See, for example, Ch.4 of Glyn Harman's Metric Number Theory. –  Joseph Vandehey Jun 10 '14 at 21:17

3 Answers 3

up vote 19 down vote accepted

The answer is no. Take $\alpha=\sqrt{2}$ and note that if $|\sqrt{2}-m/n|\le 1/n^2$ then we have $0<|2n^2-m^2| \le (\sqrt{2}n+m)/n \le 3$. Now suppose we want $n\equiv 4\pmod p$ say. Then we must have that $32-m^2 \equiv b \pmod p$ for some $|b|\le 3$. But we can find a prime $p$ for which the numbers $29$ to $35$ are all quadratic non-residues $\pmod p$ (for example, choose $p$ so that $2, 7, 11, 29, 31$ are all non-residues $\pmod p$, and $3, 5, 17$ are residues). Thus there are no good approximations to $\sqrt{2}$ with $n\equiv 4\pmod p$ for such a prime $p$. One can clearly vary this argument a fair bit.

share|improve this answer
Excellent - thank you! –  Steven Stadnicki Jun 10 '14 at 6:54

The idea I suggested in the comments works. Let $\phi$ denote the golden ratio

$$ \frac{\sqrt{5} + 1}{2} = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1+\cdots}}}$$

Because there are no coefficients of the continued fraction greater than $1$, no terms of the Farey sequence fall between the $n$th and $(n+1)$st convergents until the $(n+2)$nd convergent. This means any other fraction $\frac{p}{q}$ with $F_{n+1} \lt q \le F_{n+2}$ is separated from $\phi$ by at least $\frac{1}{q F_{n+1}} \gt \frac{1}{q^2}$. So, the only reduced good approximations are convergents, ratios of Fibonacci numbers.

Since $|\phi - \frac{F_{n+1}}{F_n}| \approx \frac{1}{\sqrt{5}F_n^2} \gt \frac{1}{(2F_n)^2}$, only reduced fractions can be good approximations.

The Fibonacci sequence does not hit every arithmetic progression. $F_{17} = 1597$ is prime, and the Fibonacci numbers repeat mod $1597$ with period $68$. Anything not hit in that period, such as $4,6,7,9... \mod 1597$, can't be the congruence class of the denominator of a good approximation to $\phi$. Similarly, no good approximation has a denominator that is $4 \mod 233$.

A slight extension works for many other quadratic irrationals. For example,

$$\sqrt{10} = 3+\cfrac{1}{6+\cfrac{1}{6+\cfrac{1}{6+\cdots}}} = [3; \bar 6].$$

The reduced good approximations with denominators between $q_n$ and $q_{n+1}$ must fall between $\frac{p_n}{q_n}$ and $\frac{p_{n+1}}{q_{n+1}}$, so the candidate reduced good approximations are $3, 4, [3;2], [3;3], ... [3; 6, 6, ...,6, a],... $ where $1\le a \le 6$. Many of these are too far away to be good approximations. The set of denominators smaller than $q_{n+1}$ of reduced good approximations has $6$ elements for each convergent, and these are linear combinations of convergents, e.g., the denominator of $[3;6,6,...,6,4]$ is $4q_n + q_{n-1}$.

I chose $281$ because it is a factor of a denominator of an early convergent. Mod $281$, the denominators of convergents repeat with period $20$, and hit only the $9$ classes $0,\pm1, \pm6, \pm37, \pm53 \mod 281$. Linear combinations $aq_{n+1}+q_n$ with $1\le a \le 6$ cover $45$ congruence classes. The convergents satisfy $|\sqrt{10} - \frac{p_n}{q_n}| \approx \frac{1}{2\sqrt{10}q_n^2}$ and $4 \lt 2\sqrt{10} \lt 9$, so we also have to consider unreduced approximations from doubling both the numerator and denominator of convergents, e.g., $|\sqrt{10}-\frac{38}{12}| \lt \frac{1}{144}$. That adds only $4$ more congruence classes. There are no good approximations to $\sqrt{10}$ with denominators congruent to $8,9,10,11,14, ... \mod 281$.

share|improve this answer

Just to make sure that it's not hidden in the comments for future readers, I want to point out that the paper "On the Approximation of Irrational Numbers With Rationals Restricted By Congruence Relations" actually gives a positive answer to a slight extension of my question (where rather than just having $\left|\frac mn-\alpha\right|\lt \frac1{n^2}$ one has that the difference is bounded for $\frac{C}{n^2}$ for some $C$ possibly dependent on the congruence parameters), which was actually sufficient to show what I was originally after. The precise statement is:

For any irrational $\xi$, any $s\geq 1$, and integers $a, b$, there are infinitely many integers $m, n$ satisfying $\displaystyle\left|\xi-\frac{m}{n}\right|\lt\frac{2s^2}{n^2}$, $m\equiv a\pmod s$, $n\equiv b\pmod s$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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