8
$\begingroup$

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$.

enter image description here

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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