Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
4  
For the first question, isn't the answer trivially $\approx e^n$? –  Srivatsan Dec 23 '11 at 16:51
2  
I ask question, dont respond with question please. –  gfhbvcncnbgf Dec 23 '11 at 17:04
2  
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
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.