0
$\begingroup$

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)$?

$\endgroup$
  • 3
    $\begingroup$ If I understand correctly, not necessarily: $d_k(\sqrt{2}) = d_k(-\sqrt{2})$. $\endgroup$ – Mateusz Kwaśnicki Jul 12 at 11:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Andreas Blass Jul 12 at 15:38
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jul 12 at 16:56
  • 1
    $\begingroup$ 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. $\endgroup$ – Mateusz Kwaśnicki Jul 12 at 17:14
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Mateusz Kwaśnicki Jul 13 at 10:11
  • $\begingroup$ You are right, of course. I corrected it. $\endgroup$ – Aaron Meyerowitz Jul 14 at 8:21

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.