# Denominator approximation sequence of a real number

For any positive integer $$[n]$$, let $$[n]=\{1,\ldots,n\}$$. Let $$r\in\mathbb{R}$$. We define for every positive integer $$n\in\mathbb{N}$$ the minimal difference from a rational with denominator $$\leq n$$ to $$r$$ by $$\text{md}_n(r)=\min\{|r-\frac{a}{b}|: a\in\mathbb{Z}, b\in[n] \},$$ and let $$d_n(r) = \min\{b\in[n]: \exists a\in\mathbb{Z}\big(|r-\frac{a}{b}| = \text{md}_n(r)\big)\}.$$

So, for every $$r\in\mathbb{R}$$ we get an increasing sequence of positive integers $$d(r) = (d_n(r))_{n\in\mathbb{N}}$$, which we call the denominator approximation sequence. (Does this concept have a proper name?)

For instance we have $$d_8(\pi)=d_9(\pi)=d_{10}(\pi) = 7$$, as $$\frac{22}{7}$$ is the best rational approximation to $$\pi$$ with denominator $$\leq 10$$. Note that $$r\in\mathbb{Q}$$ if and only if $$d(r)$$ is eventually constant.

Question. Given an integer sequence $$a$$ with $$a(n)\in[n]$$ for all $$n\in\mathbb{N}$$, is there $$r\in\mathbb{R}$$ with $$a = d(r)$$?

• If I understand correctly, not necessarily: $d_k(\sqrt{2}) = d_k(-\sqrt{2})$. – Mateusz Kwaśnicki Jul 12 at 11:31
• Just for the benefit of readers who may not notice the time-stamps: "Not necessarily" in the comment by @MateuszKwaśnicki refers to an earlier version of the question, not the new question that has been edited in to replace it. – Andreas Blass Jul 12 at 15:38
• Look up Joe Roberts's book Elementary Number Theory, which has a chapter on approximation by rationals and continued fractions. (I am recalling a BA 1 and BA 2 from that book as two varieties of best approximation.) The bibliography should be a good jumping off point. I suspect your md and d are easily derived (if not present) from material in that book, or from the pointers given by the book. Gerhard "Or A Reasonable, Rational Approximation" Paseman, 2019.07.12. – Gerhard Paseman Jul 12 at 16:56
• I suppose the question now should read "what sequences $a$ correspond to some $r \in \mathbb{R}$ so that $a = d(r)$"? As stated, this is clearly false: $a$ is necessarily non-decreasing, and it must have relatively large "gaps". For instance, $a(n) = n$ will not work. – Mateusz Kwaśnicki Jul 12 at 17:14

Look up rational approximation in Wikipedia to find answers to your questions. It is pretty lovely.

This question does not seem well thought through. Why not just list $$1,3,4,9,13$$ instead of $$1,1,3,4,4,4,4,4,9,9,9,9,13?$$

You need only consider $$0 \leq r \leq 1/2$$ since the sequences for $$r$$ and $$1-r$$ have the same denominators.

It seems odd to list only the denominators of the rational approximations rather than the approximations themselves.

Incorrect statement: If a certain rational $$\frac{a}{b}$$ appears in the sequence for $$r$$ then the sequence for $$\frac{a}{b}$$ itself is the same sequence truncated at $$\frac{a}{b}.$$

The correct description is more complicated and depends on considering which continued fractions can have one of $$\frac{a}{b}$$ as a semi-convergent.

I will suffice with describing the sequences including a $$60.$$ Some of the beauty of the result can be observed. For details read the article above or a number theory textbook (Roberts, cited above, is beautiful but hard to find in print.)

Near $$\frac{1}{60}$$ it is $$\mathbf{1,s,s+1,\cdots,60,\cdots} \ \$$ for some $$30 \leq s \leq 60.$$ One can take $$r=\frac1{2s}.$$

Near $$\frac{7}{60}$$ it is $$\mathbf{1,5,6,7,8,9,*}$$ with $$*$$ first $$17,60$$ then $$17,26,60$$ then $$17,26,43,60$$

near $$\frac{11}{60}$$ it is $$\mathbf {1,3,4,5,6,11,*}$$ with $$*$$ first $$60$$ then $$49,60$$ then $$38,49,60$$

and then $$\mathbf{1,3,4,5,11,*}$$ with $$*$$ first $$38,49,60$$ then $$27,38,49,60$$

Near $$\frac{13}{60}$$ it is $$\mathbf{1,3,4,5,9,14,23,*}$$ with $$*$$ first $$37,60$$ then $$60$$

Near $$\frac{17}{60}$$ it is $$\mathbf{1,2,3,4,7,*}$$ with $$*$$ the last $$5,4,3,2$$ or $$1$$ of $$32,39,46,53,60$$ in that order.

Near $$\frac{19}{60}$$ it is $$\mathbf{1,2,3,*,60}$$ with $$*$$ $$10,13,16,19$$ or $$10,13,16,19,41$$ or $$13,16,19,41$$

Near $$\frac{23}{60}$$ it is $$\mathbf{1,2,3,5,8,13,*}$$ with $$*$$ first $$34,47,60$$ then $$47,60$$ then $$60.$$

Finally, near $$\frac{29}{60}$$ it is $$\mathbf{1,2,15,17,19,21,23,*,60}$$ with $$*$$ first $$25,27,29$$ then $$25,27,29,31$$

and then it is $$\mathbf{1,2,17,19,21,23,25,27,29,31,60}$$

• I think the paragraph starting with "If a certain rational..." is not quite true: the sequence of best approximations for $1/4$ is $0/1$, $1/3$, $1/4$, while $1/4+\varepsilon$ will produce $0/1$, $\mathbf{1/2}$, $1/3$, $1/4$. – Mateusz Kwaśnicki Jul 13 at 10:11
• You are right, of course. I corrected it. – Aaron Meyerowitz Jul 14 at 8:21