can I find the closest rational to any given real, if I assume that the denominator is not larger than some fixed n

Question

Given $n\in\mathbb{N}$ and $r\in\mathbb{R}$(or $r\in\mathbb{Q}$), is that possible to find a rational $\frac{a}{b}$such that, $b<n$ and $\frac{a}{b}$ is the "closest" rational to r?

With "closest" I mean when $\frac{a}{b}>r$ it is the smallest rational with $b<n$ and likewise for $\frac{a}{b}<r$ it is the largest rational with $b<n$

Approach: I can see there is infinite many real/rational that close to $r$ by Archimedean property, but will that be the case such that given any $\epsilon>0$, for $|r-\frac{a}{b}|<\epsilon$, the set $\{\frac{a}{b}: b<n\}$ is bounded?

Answer 1

A method to help you is called Farey Fractions. You can get a deeper understanding by reading the Wikipedia article, but here's the main theorem you need:

Theorem: If $p=\frac{a}{b}$ and $q=\frac{c}{d}>p$ are fractions in lowest terms and there's no fraction between them with smaller denominator than either, then $bc-ad=1$, and the fraction with smallest denominator between $p$ and $q$ is $\frac{a+c}{b+d}$.

So suppose you want to approximate $\pi$ up to denominator $40$. The method is to take two fractions that bound it, say $\frac{3}{1}$ and $\frac{4}{1}$, and find their "mediant" (the fraction described above). Then replace the worse bound with this number. For example, we then get $\frac{7}{2}$, $\frac{10}{3}, \ldots \frac{22}{7}, \frac{25}{8}$, and then we have to start adding $\frac{22}{7}$ and $\frac{25}{8}$ together since now $\frac{25}{8}$ is a better lower bound for $\pi$ than $\frac{3}{1}$ is. We then get $\frac{47}{15}, \frac{69}{22}, \frac{91}{29}, \frac{113}{36}$, and then here we stop because the new denominator would be $43$ which is too large.

So our conclusion is that $\frac{113}{36}<\pi<\frac{22}{7}$ and these are the best approximations above and below $\pi$ with denominator less than $40$; you can see that $\frac{22}{7}\approx 3.1428\ldots$ is much closer than $\frac{113}{36}\approx3.1388\ldots$, so your answer is $\frac{22}{7}$.

Answer 2

If you are given a real number, indeed the rationals "closest to it" on both the left and right will exist, and they will be very easy to find.

For example, let us consider $n=10$ and the real number $\pi$. We want to find the closest rationals to $\pi$ with denominator less than $10$. For this, we do something very simple : calculate the lcm of $1,...,10$ : this is $2520$. Now, multiply $\pi$ by $2520$ up to some decimal places : you would get $7916.81$. Hence, you conclude that $\frac{7916}{2520} < \pi < \frac{7917}{2520}$.

Now, what you are going to do is very simple : find the biggest number less than $7916$ which is a multiple of any one of the following : $$ 2520,1260,840,630,504,420,360,315,280,252 $$

These are the quotients when $2520$ is divided by $1,...,10$ respectively. I found it : it is $7875 = 315 \times 25$. Hence, $\frac{7875}{2520} = \frac{25}{8}$ is the closest fraction to $\pi$ with denominator less than $10$, from the left.

From the right, we must find the smallest multiple of one of these numbers, which is greater than $7917$. Again, you can locate this : it is just $7920= 22 \times 360$. This simplifies to the popular fraction $\frac{7920}{2520} = \frac{22}{7}$.

Hence, $\frac{25}{8} < \pi < \frac{22}{7}$ are the best approximations you will get with denominator less than $10$. It's not difficult to see that there was anything special about $\pi$ or $10$ here.

This is not the efficient way to do this, but at least existence of rationals satisfying the above criteria is now put to bed.