Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
For the first question, isn't the answer trivially $\approx e^n$? – Srivatsan Dec 23 '11 at 16:51
I ask question, dont respond with question please. – gfhbvcncnbgf Dec 23 '11 at 17:04
I don't know if it was intended that way, but the tone of the response to Srivatsan is very hostile. – Gerry Myerson Dec 23 '11 at 18:01

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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