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.

  • $\begingroup$ 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)$. $\endgroup$ May 31, 2023 at 13:03
  • $\begingroup$ 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? $\endgroup$ Jun 1, 2023 at 20:27
  • $\begingroup$ I guess I'm really interested in the asymptotic behavior, i.e., if we replace 100 with a parameter. $\endgroup$ Jun 1, 2023 at 20:33
  • $\begingroup$ So, you take large parameter $T$ (for 100), and after that asymptotics in $m$, right? $\endgroup$ Jun 2, 2023 at 6:30
  • $\begingroup$ yeah, that is what I was thinking $\endgroup$ Jun 3, 2023 at 0:29

1 Answer 1


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<r_1<\ldots<r_K=1$ 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<n/T$. 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<n/T$ gives you at most $4/T^2$.

On the other hand, if $m<n/(3T)$, say, then $mM\leqslant mTn\leqslant n^2/3$ and thus $1/bd\geqslant 3/n^2$. Therefore, each of these intervals (with $m<n/(3T)$) give contribution at least $1/n^2$, and there are about $$2\sum_{m<n/(3T)} \varphi(m)\sim \zeta(2)\frac{n^2}{9T^2}$$ such intervals that gives lower bound also of order $1/T^2$.

So, $$c_1/T^2<f(T,n)<c_2/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.

  • $\begingroup$ Super cool, the $\Theta(1/T^2)$ is perfect. Thanks so much! $\endgroup$ Jun 4, 2023 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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