Can we get good rational approximations in all residue classes?

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?

• 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

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.

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

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$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8522684,"math_prob":0.99973494,"size":5785,"snap":"2019-43-2019-47","text_gpt3_token_len":1787,"char_repetition_ratio":0.13873032,"word_repetition_ratio":0.0022883294,"special_character_ratio":0.32376838,"punctuation_ratio":0.126369,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998951,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-10-16T18:26:10Z\",\"WARC-Record-ID\":\"<urn:uuid:2ff61571-3ecc-4a24-bd39-6f9aa29536b6>\",\"Content-Length\":\"133551\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:51c65f57-bbe2-4a6a-a3da-01147b6fed1f>\",\"WARC-Concurrent-To\":\"<urn:uuid:bc787bbc-c47a-4b8f-a73f-22c18e12a5cb>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://mathoverflow.net/questions/171457/can-we-get-good-rational-approximations-in-all-residue-classes/171476\",\"WARC-Payload-Digest\":\"sha1:LUZEORJ35LC2I3V4XSTFP6HF6BQIBOMC\",\"WARC-Block-Digest\":\"sha1:EG7QUHDE6GJTLH6AZZSDJ3VXTIJ4XE4S\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-43/CC-MAIN-2019-43_segments_1570986669057.0_warc_CC-MAIN-20191016163146-20191016190646-00082.warc.gz\"}"}