# Can rationals be approximated by increasingly large-denominator rationals?

Lets denote by $$A_n$$ the set of all relatively prime fractions with denominator $$n\,.$$ Then one should observe that the members of $$A_n$$ become more densely populated in the real line as $$n \to \infty$$. To see this, note that $$A_1 = \mathbb{Z}, A_2 = \Big\{\frac{1}{2}, \frac{3}{2}, \dots,\Big\},\dots,A_{56} = \Big\{\frac{1}{56},\frac{3}{56}, \frac{5}{56}, \dots\Big\},\; \dots$$

Thus, it would seem intuitively true that the statement I have proposed is true, but seeing how I could find $$N \in \mathbb{N}$$ so that this is true is elusive to me. Any suggestions here?

• Hint : The rationals form a dense set. So, there are ininfite many rational numbers closer to the given rational number than $\epsilon$. The rest should be easy. Jan 15, 2023 at 15:58
• @peter : The nontrivial part is the large denominator when the approximating fraction is required to be in lowest terms. You don't want to approximate $\frac pq$ and then find you've approximated it with $\frac12$.
– MJD
Jan 15, 2023 at 16:29
• @Peter The "rest" is the whole game. You want to show that for every $a<b$ and sufficiently large $n$, there exists $m\in(an,bn)$ relatively prime with $n$. That is true but I wouldn't say it is very easy despite the fact that there are short proofs ;-) Jan 15, 2023 at 16:46
• I assume that the $M$ in your formal statement should be $N$. Jan 15, 2023 at 16:50
• Consider Dirichlet approximation theorem Jan 15, 2023 at 17:34

The way you formalised it, the answer is “yes”, but for way less trivial reasons than one might expect.

Let $$x=\frac pq$$ and $$\epsilon$$ be given. Then $$\frac an$$ is a valid (=in shortest terms and within $$\epsilon$$) approximation for $$x$$ iff $$\frac{a-kn}n$$ is a valid approximation for $$x-k$$, $$k\in \Bbb Z$$. Therefore, wlog $$0\le x<1$$, i.e., $$0\le p.

Under certain circumstances, let us replace $$x$$ and $$\epsilon$$ with “better” $$x’$$ and $$\epsilon’$$ with $$0 and $$(x’-\epsilon’, x’+\epsilon’)\subseteq (x-\epsilon,x+\epsilon)$$. Then a valid approximation for $$x’$$ is also a valid approximation for $$x$$. Obviously, it suffices to specify suitable $$x’$$ with $$x as $$\epsilon’=\epsilon +x-x’$$ will work.

• If $$p=0$$ (i.e., $$x=0$$), pick $$k>\frac1\epsilon$$ and let $$x’=\frac2{2k+1}$$.
• If $$p=1$$, then $$q\ge2$$. Pick $$k>\max\{q(q-1),\frac1\epsilon\}$$ and let $$x^\prime=x+\frac1k=\frac{q+k}{qk}$$ (not necessarily in shortest terms). Then indeed $$x and $$q>\frac1{x^\prime}>\frac1{\frac1q+\frac1{q(q-1)}}=q-1$$ so that the numerator of $$x^\prime$$ is $$>1$$ (and also $$x^\prime<1$$).

By this, we may assume wlog that $$p\ge2$$. Then $$\frac1x$$ is between two naturals, $$k<\frac1x. Then we may assume wlog that $$\frac1{k+1}. In particular, our $$\epsilon$$-interval now contains no number with numerator $$1$$.

Let $$\delta=\frac\epsilon x>0$$. By the Prime Number Theorem, there exists $$m_0$$ such that for all $$m\ge m_0$$, there exists a prime between $$m$$ and $$(1+\delta)m$$. Pick $$N>\max\{\frac {m_0}x,\frac1\epsilon\}$$. We want to show that for every $$n\ge N$$, there exists a valid approximation with denominator $$n$$: Let $$n\ge N$$ and set $$m=\lfloor xn\rfloor$$. Then $$m\ge m_0$$ and there exists a prime $$a$$ between $$m$$ and $$(1+\delta)m$$. Then $$x-\epsilon, as desired. If $$\frac an$$ is not in lowest terms, we can cancel the prime $$a$$ completely and end up with a reciprocal of a natural, which cannot be in our $$\epsilon$$-interval. Hence $$\frac an$$ is in lowest term as desired, thus completing the proof.

• Thank you for this thoughtful response. I will come back to look at this argument later this evening when I am available. Jan 15, 2023 at 18:43
• Nice. I hope there is a proof that needs less than the prime number theorem. I thought about convergents for continued fraction expansions of irrationals near the target, but got nowhere. Jan 15, 2023 at 20:00
• @EthanBolker Well, „prime“ is the simplest form of the „coprime“ we actually need. If $n$ has many small prime divisors, it may be hard to find a coprime number in the required range by other means. - Farey sequences may be more promising than continued fractions. Jan 16, 2023 at 0:11
• My answer in mathoverflow.net/questions/434707/… contains an alternative proof of the density (actually, uniform distribution) of fractions with denominator exactly $n$ as $n\to\infty$ and the remark by Fedor Petrov makes that argument even more elementary, but still far from trivial. Jan 16, 2023 at 3:32

Given $$n$$, we have $$a \approx \frac {pn}{q}$$; the best $$a$$ is that value rounded to the nearest integer. So $$E=|a - \frac{pn}{q}|\le 0.5$$.

$$|\frac{a}{n} - \frac {p}{q}| = \frac {1}{n}\left|a-\frac {pn}{q}\right|=\frac{E}{n}\le\frac{0.5}{n}$$

If I've understood your statement correctly, then: $$\frac{0.5}{n}< \epsilon$$ means $$n>\frac{1}{2 \epsilon}$$.

Let $$(x_n)$$ be a sequence of rationals that converges to $$x\not\in\{x_1,x_2,x_3,...\}\,.$$ (This $$x$$ can also be irrational but it should not be part of the sequence.)

Claim. Every $$x_n$$ is of the form $$x_n=\frac{p_n}{q_n}\quad\text{ with }\operatorname{gcd}(p_n,q_n)=1\quad\text{ and }\quad q_n\to+\infty\,.$$ Proof. Because the limit of $$(x_n)$$ is not part of the sequence the following must hold: $$\forall n\;\exists M\;\forall m\ge M\;: x_m\not=x_n\,.$$ Otherwise, we could find a subsequence $$(x_{m_j})$$ that is identically equal to some $$x_n$$ and therefore converges to an element of the sequence.

Because $$(x_n)$$ must also be a Cauchy sequence we have $$\tag{1} \forall \varepsilon>0\;\exists N\;\forall m,n\ge N:|x_n-x_m|<\varepsilon\,.$$ Clearly, $$x_m\not=x_n$$ is equivalent to $$|p_nq_m-p_mq_n|\ge 1\,$$ since this is a natural number or zero. Therefore we have $$\forall\varepsilon>0\;\exists N\;\forall n\ge N\;\exists M\;\forall m\ge M:\frac{1}{|q_nq_m|}\le \frac{|p_nq_m-p_mq_n|}{|q_nq_m|}=\Bigg|\frac{p_n}{q_n}-\frac{p_m}{q_m}\Bigg|<\varepsilon\,$$ from (1). This implies that $$\frac{1}{|q_nq_m|}$$ must converge to zero when $$n\to\infty$$ or $$m\to\infty\,.$$ In other words, $$q_n$$ must diverge to $$\infty\,.$$ $$\tag*{\Box } \quad$$

• This gives “arbitrarily large”denominators, but not “all sufficiently large” denominators Jan 15, 2023 at 18:30
• @HagenvonEitzen Yes. Sounds like OP asks for more in the body than in the title only. Thanks for feedback and for your other answer. Jan 15, 2023 at 18:39
• This proof shows that $q_n \to \infty$ but it seems to assume from the start that each $x_n = \frac{p_n}{q_n}$. In other words, I'm not seeing how this proof proves that $x_n=\frac{p_n}{q_n}$ Jan 16, 2023 at 14:49
• @DavidC.Huang $x_n$ is a sequence of rationals, and I write them just as you wrote your rationals in OP. Jan 16, 2023 at 14:52
• @DavidC.Huang I inserted one more expression to clarify this. It is from the Cauchy condition. Jan 16, 2023 at 15:20