# Simultaneously approximating all $x \in [0,1]$ with fractions of bounded denominator

Dirichlet's theorem says that all numbers $$x\in [0,1]$$ can be approximated by infinitely many fractions $$p/q \in \mathbb{Q}$$ with error $$|x - p/q| \le 1/q^2$$.

I am interested in the following question: Fix $$m>0$$. Let $$S(m)$$ denote the set of $$x\in [0,1]$$ for which no fraction $$p/q \in \mathbb{Q}$$ with $$q<100\sqrt{m}$$ approximates $$x$$ with error smaller than $$1/m$$, i.e., $$|x-p/q| > 1/m$$ for any such choice of $$p,q$$. What bounds are there for the measure of $$S(m)$$?

EDIT: Let $$\Phi(q)$$ denote the set of numbers smaller than $$q$$ coprime to $$q$$. And let $$I(q) = \bigcup_{p\in \Phi(q)} [p/q, p/q+1/m]$$ For $$q_1,q_2<\sqrt{m}$$ the sets $$I(q_1),I(q_2)$$ will be disjoint. This can give a simple lower bound (by analyzing $$\sum_{k<\sqrt{m}} \phi(k)$$, which is a well known problem). I'm interested in if anything stronger than this bound can be given.

• Note that if $m<40000$ then $S(m)$ is empty since for any $x$ and any $q$ there exists $p$ such that $|x-(p/q)|\le1/(2q)$. May 31, 2023 at 13:03
• It is about some constant depending on 100. Small if 100 is large. What kind of bound (and from which side) would make you happy? Jun 1, 2023 at 20:27
• I guess I'm really interested in the asymptotic behavior, i.e., if we replace 100 with a parameter. Jun 1, 2023 at 20:33
• So, you take large parameter $T$ (for 100), and after that asymptotics in $m$, right? Jun 2, 2023 at 6:30
• yeah, that is what I was thinking Jun 3, 2023 at 0:29

Fix $$T$$ ($$T=100$$ in your example) and denote by $$S_T(n)$$ the set of numbers $$x\in [0,1]$$ such that $$|x-p/q|>1/n^2$$ whenever $$p,q$$ are integers and $$1\leqslant q\leqslant Tn$$ (so, my $$n$$ is your $$\sqrt{m}$$).
Let $$0=r_0 be Farey sequence of all irreducible fractions with denominator at most $$Tm$$. Denote $$\delta_i=r_{i+1}-r_i$$ for $$i=0,1,\ldots,K-1$$ the gap between corresponding Farey fractions. Then $$S_T(n)\cap [r_{i},r_{i+1}]$$ has length $$\max(\delta_i-2/n^2,0)$$, so, the measure of $$S_T(n)$$ equals $$f(T,n):=\sum_{i:\delta_i>2/n^2} (\delta_i-2/n^2).$$ Recall that if $$r_i=a/b$$, $$r_{i+i}=c/d$$ are irreducible fractions, then $$\delta_i=1/(bd)$$ and $$b+d>Tn$$. Denote $$M=\max(b,d)$$, $$m=\min(b,d)$$. Then $$M> Tn/2$$, and the inequality $$1/(Mm)=\delta_i>2/n^2$$ yields $$1/m>2M/n^2>T/n$$, so, $$m. And $$\delta_i=1/(mM)\leqslant 2/(Tnm)$$. Thus, for fixed $$m$$, the fractions with denominator $$m$$ give a contribution at most $$2\varphi(m)\left(\frac{2}{Tnm}-\frac2{n^2}\right)\leqslant \frac4{Tn}.$$ Summing up over $$m gives you at most $$4/T^2$$.
On the other hand, if $$m, say, then $$mM\leqslant mTn\leqslant n^2/3$$ and thus $$1/bd\geqslant 3/n^2$$. Therefore, each of these intervals (with $$m) give contribution at least $$1/n^2$$, and there are about $$2\sum_{m such intervals that gives lower bound also of order $$1/T^2$$.
So, $$c_1/T^2 for some universal explicit constants $$c_1,c_2$$. If you care on sharp constant, please let me know, this requires more accurate analysis but looks doable.
• Super cool, the $\Theta(1/T^2)$ is perfect. Thanks so much! Jun 4, 2023 at 0:16