Approximating reals with rationals

Question

I don't have any particular motivation for this question, it just popped into my head.

We play the following game: you give me a real number between 0 and 1, and I have to do my best to approximate it as a rational number with a limit on the size of the denominator. More formally, you choose $x \in [0,1]$, and I have to come up with a pair of integers $p,q \leq N$ that minimize the error: $$ E = \bigg| x - \frac{p}{q} \bigg| $$

For a given $N$, how should you choose $x$ to make me incur the largest possible error?

I made a plot to see how all the possible fractions fall on the number line for each $N$ between 1 and 100. It has a rather interesting pattern which seems to have a fractal nature. For any $N$, the hardest choices of $x$ seem to be at the extremes of the interval: between 0 and the smallest possible fraction larger than 0, and between 1 and the largest possible fraction smaller than $1$.

Answer 1

The rationals with denominator less than $N$ form part of the Farey sequence. The largest gap is between $0$ and $\frac 1N$ and again from $\frac {N-1}N$ to $1$. The smallest gap is from $\frac 1N$ to $\frac 1{N-1}$ and again from $\frac{N-2}{N-1}$ to $\frac {N-1}N$, a gap of $\frac 1{N(N-1)}$ To find the best rational approximation to a given $x$, you find its continued fraction and quit with the last convergent with denominator less than $N$, and see if a small adjustment can improve it.

Answer 2

Certainly, if $x = \frac{1}{2N}$, then that forces an error of $\frac{1}{2N}$ or more - since $\frac{p}{q}$ with $q \le N$ is either equal to 0, or else $\frac{p}{q} \ge \frac{1}{N}$.

Now, given any other $x \in [0, 1]$, consider the continued fraction expansion of $x$, $$x = [a_0, a_1, a_2, \ldots] = a_0 + \frac{1} {a_1 + \frac{1} {a_2 + \ddots}}.$$ Certainly, if $x$ is a rational number with denominator $\le N$, then we can approximate $x$ with error 0, so let us exclude that case. Otherwise, if some truncation $\frac{p_k}{q_k} = [a_0, a_1, \ldots, a_k]$ has denominator $2 \le q_k \le N$, then choose the largest such $k$. Then $q_{k+1} > N$, and so $\left| x - \frac{p_k}{q_k} \right| \le \frac{1}{q_k q_{k+1}} < \frac{1}{2N}$. The only other cases are $x = [0, M, \ldots]$ with $M > N$, or $x = [0, 1, M, \ldots]$ with $M > N - 1$. In the first case, $0 < x < \frac{1}{N}$, so either $\frac{0}{1}$ or $\frac{1}{N}$ is within $\frac{1}{2N}$ of $x$; in the second case, $1 - \frac{1}{N} < x < 1$, so either $\frac{N-1}{N}$ or $\frac{1}{1}$ is within $\frac{1}{2N}$ of $x$.

Answer 3

The ordered set of fractions you can choose is by definition the Farey sequence of order $N$. All Farey sequences have the property that any two adjacent fractions $\frac ab<\frac cd$ are separated by a gap of $\frac1{bd}$. I thus want to find adjacent fractions with $bd$ as small as possible for the given $N$, and then choose the number midway between those two fractions.

Now I argue that except if $b=1$ or $d=1$, two adjacent fractions must have $bd>N$. The natural number inequality $x+y<xy$ holds whenever $x,y>1$ and $(x,y)\ne(2,2)$. If $bd\le N$, the mediant $\frac{a+c}{b+d}$ of the assumed-adjacent fractions would come between them in the Farey sequence of order $N$ – contradiction. For $b=d=2$ there is only one selectable fraction with denominator $2$, so we cannot speak of two such fractions being adjacent in the first place.

Now $b=1$ or $d=1$ means the largest gap I desire lies at the endpoints. Accordingly, to induce the largest approximation error I choose $\frac1{2N}$ or $1-\frac1{2N}$, which incurs the largest error of $\frac1{2N}$.