3
$\begingroup$

Question

Suppose $\lambda$ is a positive integer and I want to show that there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ performs at least $\lambda$ divisions.

Note

The variable $\phi$ is defined as $\phi := (1+\sqrt{5})/2$ where $\phi^2 = \phi + 1$, and the upper bound for the total number of divisions, $\lambda$, given by a theorem in my textbook is $\lambda \leq \log_2b/\log_2\phi + 1$.

Additionally, the values produced by Euclid's algorithm in my text given integers $a > b > 0$ is denoted as \begin{align*} r_0 & = a \\ r_1 & = b \\ r_0 & = r_1q_1 + r_2, \quad 1 \leq q_1 \leq r_0, \quad 1 \leq r_2 < r_1 \\ &\vdots \\ r_{i-1} & = r_iq_i + r_{i+1}, \quad 1 \leq q_i \leq r_{i-1}, \quad 1 \leq r_{i+1} < r_{i} \\ &\vdots\\ r_{\lambda-2} & = r_{\lambda-1}q_{\lambda-1} + r_\lambda, \quad 1 \leq q_{\lambda-1} \leq r_{\lambda-2}, \quad 1 \leq r_\lambda < r_{\lambda-1} \\ r_{\lambda-1} & = r_\lambda q_\lambda, \end{align*} where $r_\lambda$ is $\gcd(a,b)$ and the last non-zero remainder.

Current Work

If I proceed by induction, let $\lambda = 1$ be the base case. So then $$1 \geq \log_2b/\log_2\phi \implies \phi \approx 1.62 \geq b,$$ and as $b > 0$ it is necessarily true that $b = 1$. By letting $a$ be an arbitrary integer such that $a > b=1$, $$a = bq_1 + r_2$$ provides that $a = q_1$ for all integers $a>1$, and so for $\lambda = 1$ there exists integers $a,b$ satisfying the above conditions.

Assume that for some $\lambda \geq 1$, there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ performs at least $\lambda$ divisions.

Then for $\lambda+1$, we want $b$ to satisfy $$\lambda + 1 \geq \log_2b/\log_2\phi \implies \phi^{\lambda+1} \geq b.$$ Additionally by the upper bound on $\lambda$ given by $b$ we have that $$\lambda+1 \leq \log_2b/\log_2\phi + 1 \implies \phi^\lambda \leq b.$$ As $b$ is an integer, $$\lfloor\phi^\lambda\rfloor \leq b \leq \lceil\phi^{\lambda+1}\rceil.$$

From here I am not really sure where to go with this, moreover I don't know how i can apply the assumption for induction. Could anyone hint at something I may have overlooked if possible?

$\endgroup$
8
  • 1
    $\begingroup$ A hint: find for small $b$ the worst cases, the pairs $(a,b)$ which need the most divisions. You need only consider $1 < b < a < 2b$, of course. You may notice a pattern which pairs are worst for the Euclidean algorithm. $\endgroup$ Aug 29, 2013 at 22:38
  • $\begingroup$ Before jumping into playing with values, will there usually exist an $a$ for every positive integer $b$ that satisfies these worst case run-times, or is it more of a hit or miss if I pick a random $b$ to start testing relevant values of $a$? $\endgroup$
    – Alex
    Aug 29, 2013 at 22:53
  • $\begingroup$ Not for every $b$. But for $b$ in a well-known sequence. $\endgroup$ Aug 29, 2013 at 22:55
  • 1
    $\begingroup$ My next question is then is for the elements of the fibonacci sequence defined as $F_0=1$, $F_1=1$, and $F_{i+2}=F_{i+1}+F_i$ for $i=0,1,\dots$, is it reasonable for me to try and prove that $$\frac{\log F_{\lambda-1}}{\log \phi} \leq \lambda \leq \frac{\log F_{\lambda-1}}{\log \phi} +1$$ for all $i=1,2,\dots$? $\endgroup$
    – Alex
    Aug 30, 2013 at 1:22
  • $\begingroup$ How long did it take you to figure that out? Yes, you should definitely look in that direction. Binet's formula could be useful there. (And, just for completeness, you should have defined $F_0 = 0$, that is much nicer in general and standard.) $\endgroup$ Aug 30, 2013 at 1:27

1 Answer 1

2
$\begingroup$

As requested:

A hint: find for small $b$ the worst cases, the pairs $(a,b)$ which need the most divisions. You need only consider $1<b<a<2b$, of course. You may notice a pattern which pairs are worst for the Euclidean algorithm.

Before jumping into playing with values, will there usually exist an $a$ for every positive integer $b$ that satisfies these worst case run-times, or is it more of a hit or miss if I pick a random $b$ to start testing relevant values of $a$?

Not for every $b$. But for $b$ in a well-known sequence.


Since the answer is found, let's elaborate:

To find the worst cases, we can employ the computer, after all, computing is what it's for:

Simple Haskell code to find worst cases

module Euclidean where

euclideanLength :: Int -> Int -> Int
euclideanLength a b = go 0 a b
  where
    go l _ 0 = l
    go l n d = go (l+1) d (n `rem` d)


worst :: (Int -> Int -> Bool) -> Int -> [(Int,Int,Int)]
worst cmp mx = go 0 2 3
  where
    go m b a
        | b > mx    = []
        | a == 2*b  = go m (b+1) (b+2)
        | cmp n m   = (n,b,a) : go n b (a+1)
        | otherwise = go m b (a+1)
          where
            n = euclideanLength a b

and when we ask for cases which take at least as long as the longest found so far:

*Euclidean> worst (>=) 50
[(2,2,3),(2,3,4),(3,3,5),(3,4,7),(3,5,7),(4,5,8),(4,7,11),(4,7,12)
,(4,8,11),(5,8,13),(5,11,18),(5,11,19),(5,12,19),(5,13,18),(6,13,21)
,(6,18,29),(6,18,31),(6,19,30),(6,19,31),(6,21,29),(7,21,34),(7,29,47)
,(7,29,50),(7,30,49),(7,31,49),(7,31,50),(7,34,47),(8,34,55),(8,47,76)
,(8,47,81),(8,49,79),(8,49,80),(8,50,79),(8,50,81)]

Hmm, not too obvious (though if you look closely, it is discernible), let's ask for a strictly longer sequence:

*Euclidean> worst (>) 50
[(2,2,3),(3,3,5),(4,5,8),(5,8,13),(6,13,21),(7,21,34),(8,34,55)]

Houston, we have a pattern!

The worst cases are $a = F_{n+1},\; b = F_n$ with the Fibonacci numbers $F_n$.

Now that the worst cases are identified, it remains to

  • show that they meet the requirements, and
  • understand why they are the worst cases.

Defining the Fibonacci numbers $F_0 = 0,\; F_1 = 1,\; F_{n+2} = F_{n+1} + F_n,\, n \geqslant 0$, we see that $\lambda(F_{n+2}, F_{n+1}) = \lambda(F_{n+1},F_n) + 1$, and since $F_2 = 1$ needs one division, we have $\lambda(F_{n+1},F_n) = n-1$.

We want to show that

$$\frac{\log F_n}{\log \phi} \leqslant n-1 \leqslant \frac{\log F_n}{\log \phi} + 1,$$

or

$$(n-2)\log \phi \leqslant \log F_n \leqslant (n-1)\log \phi.$$

With Binet's formula, exponentiating that yields

$$\begin{align} \phi^{n-2} &\leqslant \frac{\phi^n - \psi^n}{\phi-\psi} \leqslant \phi^{n-1}\\ \iff \phi^{n-1} + \phi^{n-3} &\leqslant \phi^n - \psi^n \leqslant \phi^n + \phi^{n-2} \end{align}$$

since $\phi\cdot\psi = -1$. Using $\phi - 1 = \frac1\phi$, the left inequality becomes

$$\psi^n \leqslant \phi^{n-1}(\phi - 1) - \phi^{n-3} = \phi^{n-2}-\phi^{n-3} = \phi^{n-4},$$

upon division by $\phi^{n-4}$

$$(-1)^{n-4}\psi^{2n-4} \leqslant 1.$$

That's certainly true for $n \geqslant 2 \iff 2n-4 \geqslant 0$, since $\lvert\psi\rvert < 1$. The right inequality becomes, after subtracting $\phi^n$

$$-\psi^n \leqslant \phi^{n-2},$$

which holds since (for $n\geqslant 2$) we have $\lvert\psi^n\rvert < 1 \leqslant \phi^{n-2}$.

So part 1 is done.

Now, why do we get the longest division chains for successive Fibonacci numbers?

Informally, we want the sequence $r_k$ of remainders to decrease as slowly as possible. If we have a large quotient $q_k = \lfloor r_{k-1}/r_k\rfloor$ in the sequence, then $r_{k+1}$ is much smaller than $r_{k-1}$, which we don't want. So the quotients should be small, ideally all should be $1$ except for the first, which doesn't matter, and the last, which is $r_{\lambda-1}/r_\lambda > 1$.

More formally, we note that the Euclidean algorithm is almost exactly the continued fraction algorithm, the steps

$$\begin{align} r_{k-1} &= q_kr_k + r_{k+1}\\ r_k &= q_{k+1}r_{k+1} + r_{k+2} \end{align}$$

become upon division by $r_k$ resp. $r_{k+1}$

$$\begin{align} \frac{r_{k-1}}{r_k} &= q_k + \frac{r_{k+1}}{r_k}\\ \frac{r_k}{r_{k+1}} &= q_{k+1} + \frac{r_{k+2}}{r_{k+1}} \end{align}$$

which is the continued fraction algorithm. The sequence of quotients in the Euclidean algorithm for $a$ and $b$ is the sequence of partial quotients in the continued fraction expansion of $\frac{a}{b}$ (the one that does not end with $1$).

Now, if we have a simple continued fraction of length $\lambda$ not ending in $1$,

$$x = [a_0,\, a_1,\, \dotsc,\, a_{\lambda-1}],$$

for the convergents

$$\frac{p_n}{q_n} = [a_0,\,a_1,\, \dotsc,\, a_n],$$

we have the recursion

$$\begin{align}p_{n+1} &= a_{n+1}\cdot p_n + p_{n-1} & q_{n+1} &= a_{n+1}\cdot q_n + q_{n-1},\end{align}$$

starting with $p_{-2} = 0,\, p_{-1} = 1,\, q_{-2} = 1,\, q_{-1} = 0$.

We are only interested in the denominators $q_n$, for which we see $q_0 = a_0\cdot q_{-1} + q_{-2} = 1$, $q_1 = a_1\cdot q_0 + q_{-1} = a_1$, and from the recursion $q_{n+1} = a_{n+1}q_n + q_{n-1}$, it is clear that $a_0$ has no influence on $q_n$, and the denominator $q_{\lambda-1}$ will be minimal if $a_1 = a_2 = \dotsc = a_{\lambda-2} = 1$ and $a_{\lambda-1} = 2$.

Choosing $a_0 = 1$, we find the convergents

$$\frac{p_0}{q_0}=\frac11,\, \frac{p_1}{q_1}=\frac21,\, \frac{p_2}{q_2}=\frac32,\, \dotsc,\,\frac{p_n}{q_n} = \frac{F_{n+2}}{F_{n+1}},\, \dotsc,\, \frac{p_{\lambda-2}}{q_{\lambda-2}}=\frac{F_{\lambda}}{F_{\lambda-1}},\, \frac{p_{\lambda-1}}{q_{\lambda-1}} = \frac{F_{\lambda+2}}{F_{\lambda+1}}$$

and thus that $F_{\lambda+1}$ is indeed the smallest $b$ for which the Euclidean algorithm can take $\lambda$ divisions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .