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

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ If I understand correctly, not necessarily: $d_k(\sqrt{2}) = d_k(-\sqrt{2})$. $\endgroup$
    – Mateusz Kwaśnicki
    Commented Jul 12, 2019 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
    Commented Jul 12, 2019 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
    Commented Jul 12, 2019 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
    Commented Jul 12, 2019 at 17:14

1 Answer 1

Reset to default
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}$

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .