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

  • $\begingroup$ $T$ transforms length $n$ to length $2n-1$. $\endgroup$ – Gerry Myerson Mar 7 '12 at 12:02

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


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

  • $\begingroup$ $\alpha$ and $\beta$ are not integers. $\endgroup$ – Ewan Delanoy Mar 7 '12 at 8:51
  • $\begingroup$ 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$ $\endgroup$ – matovitch Mar 7 '12 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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