2
$\begingroup$

What is the growth rate in n of the denominator of the rational $r_n$, $n=1,2,3,\ldots$ in $1>r_n>1-e^{-n}$ with the smallest denominator?

If $I_n$ is a (sufficiently random) sequence of disjoint intervals in R>0, whose lenght (ie elementary measure) is given by a f(n) decreasing to 0, with $\sum_n f(n) = \infty$, what is the expected growth rate of the lowest denominator of all rationals in $I_n$ ?

  • 2
    I don't know if it was intended that way, but the tone of the response to Srivatsan is very hostile.2011-12-23

2 Answers 2

1

As Srivatsan's comment suggests, if $1/m\lt\alpha\lt1/(m+1)$, then $1\gt1-(1/m)\gt1-\alpha\gt1-(1/(m+1))$, and the smallest denominator you can use is $m$, which is roughly $1/\alpha$. So the growth rate, in your question, is asymptotically $e^n$.

The second question seems harder.

1

I'm not sure what probability model you want to use for your sequence of disjoint intervals: note that since $\sum_n f(n) = \infty$, the sequence must be unbounded. But let me take $I_n = [a_n, b_n]$ with $b_n = a_n + f(n)$ and $a_{n+1}$ uniformly distributed in $[b_n, b_n + 1]$. Since there are $\phi(k)$ rationals with denominator $k$ (in lowest terms) in an interval of length 1 with irrational endpoints, the expected number of such rationals in $[a_n, b_n]$ is $f(n) \phi(k)$. The expected number of rationals with a denominator $\le m$ is $f(n) \sum_{k=1}^m \phi(k) \approx \frac{3 m^2}{\pi^2} f(n)$ as $m \to \infty$. If $m(n) \le c/ \sqrt{f(n)}$ with $c <\pi/\sqrt{3}$, the probability of $I_n$ containing a rational with denominator $\le m(n)$ is bounded away from 1, so almost surely infinitely many $I_n$ will have smallest denominator $> m(n)$.