9
$\begingroup$

As you know, the worst case for the Euclidean algorithm in $\mathbb Z$ is two consecutive Fibonacci numbers. As any online GCD calculator that shows the steps of the Euclidean algorithm will demonstrate, computing $\gcd(F_n, F_{n + 1})$ results in a listing in descending order of the Fibonacci numbers from $F_{n - 1}$ all the way down to 0 (assuming $n$ is positive to begin with, some of the online calculators refuse to do anything with negative numbers like $-89$ or $-144$).

What is the worst case for $\mathbb Z[i]$, the Euclidean domain of Gaussian integers?

The first thing I tried was $\gcd(F_n i, F_{n + 1})$, but it pretty much boils down to the same thing as in $\mathbb Z[i]$.

The second thing I tried was Googling. First result was Wikipedia. Ugh.

That's when I decided to ask the question here. I'm getting a warning that this question "appears subjective and is likely to be closed."

But I think there is an objective criterion here for what constitutes a bad case for the Euclidean algorithm.

$\endgroup$
3
  • 4
    $\begingroup$ This question is indeed probably far more objective than most questions beginning "What is the worst..." $\endgroup$ – Misha Lavrov Oct 14 '18 at 23:38
  • 3
    $\begingroup$ A few thoughts: clearly(?) you're going to need every partial quotient to be a unit; elsewise you can get 'closer' while still maintaining the same number of steps. At the same time, you should be able to follow the usual proof by induction that if $\gcd(s_n, s_{n+1})$ is a unit and $s_{n+2}=\alpha s_{n+1}+\beta s_{n+2}$ then $\gcd(s_{n+1}, s_{n+2})$ is also a unit. At the same time, you need to control the sequence of units chosen such that e.g. no other (unit) multiple of $s_{n+1}$ can be subtracted from $s_{n+2}$ to yield a smaller magnitude than $s_n$. $\endgroup$ – Steven Stadnicki Oct 15 '18 at 0:54
  • 2
    $\begingroup$ I wonder whether the Fibonacci polynomials are the worst case for the Euclidean algorithm in $\mathbb Q[x]$. It seems so... $\endgroup$ – lhf Oct 15 '18 at 1:43
8
$\begingroup$

The paper below attacks exactly this problem:

Heinrich Rolletschek, On the Number of Divisions of the Euclidean Algorithm Applied to Gaussian Integers, Journal of Symbolic Computation 2 (1986), no. 3, 261–291.

He proves an analogue of Lamé's theorem about the maximum number of steps but it seems that finding pairs that attain this maximum remains an open problem. (Or at least was in 1986.)

$\endgroup$
2

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.