Bound on total divisions of Euclid's Algorithm.

Question

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?

Answer 1

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.