Can we get good rational approximations in all residue classes?

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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$.

Answer 4

The theory of approximation by rationals under congruence constraints is extensively studied in this paper.