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.

This question is (remotely) related to How to find a "simple" fraction between two other fractions?, but is not answered in that older post.

Let $f_1=\frac{a}{b}$ and $f_2=\frac{c}{d}$ be two reduced fractions with $bc-ad > 1$ (and hence $\frac{a}{b} \lt \frac{c}{d}$) and $a,b,c,d$ positive. Then the theory of Farey sequences tells us that in-between $f_1$ and $f_2$ we may find a reduced fraction $\frac{x}{y}$ with low denominator, i.e. $y \leq {\rm max}(b,d)$. We know also that if we take mediants iteratively between $f_1$ and $f_2$, we eventually reconstruct the whole part of the Stern-Brocot tree between $f_1$ and $f_2$, so that we will eventually encounter fractions with low denominator.

Formally, let $T$ be the following transform on finite increasing sequences of reduced fractions :

$$ T\bigg(\frac{a_1}{b_1}\lt\frac{a_2}{b_2}\lt\frac{a_3}{b_3} \lt \ldots\lt\frac{a_n}{b_n}\bigg)= \bigg(\frac{a_1}{b_1}\lt\frac{a_1+a_2}{b_1+b_2}\lt\frac{a_2}{b_2}\lt\frac{a_2+a_3}{b_2+b_3}\lt \frac{a_3}{b_3} \lt \ldots\lt\frac{a_n}{b_n}\bigg) $$

so that $T$ transforms a sequence of length $n$ into a larger sequence, of length $2n+1$.

Then some iterate $T^N\bigg({\frac{a}{b}<\frac{c}{d}}\bigg)$ contains a fraction with low denominator. How fast is that fraction reached ? I am expecting two different sorts of answers :

  • Find a bound $N(m)$, such that one always finds a fraction with low denominator in $N(m)$ steps in the worst case (in terms of $m={\sf max}(b,d)$).

  • Find a bound $B(m)$ on the size of the denominators encountered before finding a low denominator.

    For example, I have computed that $N(10)=8$ and $B(10)=327$ (corresponding to the two worst cases $\frac{1}{10} < \frac{8}{9}$ and $\frac{1}{9} < \frac{9}{10}$ ).

share|improve this question
    
$T$ transforms length $n$ to length $2n-1$. –  Gerry Myerson Mar 7 '12 at 12:02
add comment

1 Answer

up vote 0 down vote accepted

(Je préfèrerais donner une réponse en français, mais ça ne serait pas aimable vis à vis des éventuels lecteurs anglophones.)

I founded a bound but it does not depend only on $m$ but on $bc-ad$. It is quite simple (and I won't be able to give a complex solution because of my young and limited knowledge) :

I expressed $\left(\begin{array}{c} y\\ x\end{array}\right)$ in the basis $\left(\left(\begin{array}{c} b\\ a\end{array}\right),\left(\begin{array}{c} d\\ c\end{array}\right)\right)$.

I obtained $\dfrac{\alpha}{bc-ad}\left(\begin{array}{c} b\\ a\end{array}\right)+\dfrac{\beta}{bc-ad}\left(\begin{array}{c} d\\ c\end{array}\right)=\left(\begin{array}{c} y\\ x\end{array}\right)$ so $\alpha\left(\begin{array}{c} b\\ a\end{array}\right)+\beta\left(\begin{array}{c} d\\ c\end{array}\right)=(bc-ad)\left(\begin{array}{c} y\\ x\end{array}\right)$

and $y\leq m$ so $x\leq \dfrac{mc}{d}$ and $x\geq \dfrac{ma}{b}$

if we note $n=min(b,d)$.

$\alpha\leq \dfrac{m}{n}(bc-ad)$ and $\beta\leq \dfrac{m}{n}(bc-ad)$.

Finally $N\leq max(\alpha,\beta)\leq \dfrac{m}{n} (bc-ad)$.

Assuming that the fractions are lower than $1$, $bc-ad\leq mn$.

$N(m)\leq m^2$

$B(m)\leq\mathcal{F}_{m^{2}}m$

where $\mathcal{F}$ is the fibonacci sequence. This is not wonderful but this is a start.

share|improve this answer
    
$\alpha$ and $\beta$ are not integers. –  Ewan Delanoy Mar 7 '12 at 8:51
    
It is a product of a matrice with integer coefficients with $\left(\begin{array}{c} x\\ y\end{array}\right)$ so there are integers...I think. $\alpha=yd-cx$ and $\beta=bx-ya$ –  matovitch Mar 7 '12 at 9:07
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.