4
$\begingroup$

I have posted this question at stackexchange (502413), without responses until now.

In the papers by T. Motzkin: The Euclidean Algorithm, Bull. AMS 55, 1949, pp. 1142--1146 and P. Samuel: About Euclidean Rings, Journ. of Alg. 19, 1971, pp. 282--301, it is shown that among all the Euclidean algorithms on a given domain (wlog: taking values in one fixed well-ordered set), there is a unique smallest one in the sense that it takes smallest values. In fact, it is the pointwise infimum of all Euclidean algorithms. Samuel just calls this the "smallest" algorithm, but Motzkin calls it the "fastest" algorithm and remarks on "faster" algorithms (p. 1142/3):

(under certain additional conditions, indeed less algorithm steps are needed).

This remark confuses me. The following is my attempt to interpret it, which leads to two questions.

I assume that by "algorithm steps" we are talking about the classical application of the Euclidean algorithm, namely, to compute gcd's. (Maybe this is already a complete misinterpretation, but I do not know what else "algorithm steps" could refer to.) So say we have two elements $a,b$ of a ring which is Euclidean with respect to several norms. Let us take these norms as $\mathbb{N}_0$-valued as in the classical definition. If we want to find a $\gcd(a,b)$, we can use any Euclidean algorithm. Now the following observation is nearly trivial: Using a Euclidean algorithm w.r.t. a norm $|\cdot|$, at most $\min (|a|, |b|) (\pm 1$, according to conventions) steps are needed to arrive at a gcd, because at each step, the norm of the divisor is strictly smaller than that of the divisor of the previous step. So when we have $|\cdot |_1 \le | \cdot |_2$ in the sense of Motzkin and Samuel, we can expect a tendency that using $|\cdot|_1$ might need less algorithm steps to arrive at a gcd.

Question: Beyond this tendency, can we say anything specific? That is, what might Motzkin have in mind as "certain additional conditions"?

There is a complication which should be resolved before: Even if we use only one Euclidean norm, usually there is no uniqueness assumption about the divisor and remainder term, and choosing them differently leads to varying numbers of steps.

Easy example: The ring of integers $\mathbb{Z}$ is Euclidean w.r.t. the usual absolute value. To compute $\gcd(8,3)$, we can go through
$8 = 2 \cdot 3 + 2$
$3 = 1 \cdot 2 + 1$
$2 = 2 \cdot 1 + 0$
but we need one step less with
$8 = 3 \cdot 3 + (-1)$
$3 = -3 \cdot (-1) + 0$.

One obvious guess is that in each division-with-remainder step, one takes a smallest among all possible remainders -- like in the example, where $|-1| < |2|$. Motzkin seems to suggest this in the 2nd paragraph on p. 1144. I think I have an ad hoc argument why this works for the ring $\mathbb{Z}$, but I do not see a general principle.

Question for starters: For a fixed Euclidean norm, is it true that taking a minimal remainder in each step leads to a minimal number of steps (for this norm)?

Added: A colleague has turned my attention to this arxiv post from which I have learned that Kronecker had predated my "ad hoc argument" and given a positive answer to the 2nd question for $(\mathbb{Z}, | \cdot |)$; an elaboration of which can be found in A. W. Goodman, W. M. Zaring: Euclid's Algorithm and the Least-Remainder Algorithm, Amer. Math. Monthly 59 (1952), pp. 156-159. Searching through citations of this, no one in that camp seems to have investigated other Euclidean domains than $(\mathbb{Z}, | \cdot |)$.

$\endgroup$
4
  • $\begingroup$ If you compare algorithms, you should not do this by looking at crude upper bounds on the number on steps; what you need are upper bounds that are attained (worst case) or bounds on the average number of steps. $\endgroup$ Sep 24, 2013 at 15:42
  • $\begingroup$ As for your last question I think you can easily come up with counterexamples. $\endgroup$ Sep 24, 2013 at 15:44
  • $\begingroup$ What Motzkin calls an algorithm is not an algorithm in the sense of a calculating routine. It is a norm on the ring with certain order theoretic properties (none concerning calculability). He calls one 'faster' than another if it consistently gives results closer in that order to the GCD. In general there need not be any calculating routine and in any case none needs to be specified. His parenthetic remark says that under further conditions this will agree with the idea of requiring fewer steps. Probably the further conditions relate to the classical Euclidean algorithm computinge gcd's. $\endgroup$ Sep 24, 2013 at 16:22
  • $\begingroup$ Thanks for the comments. Colin McLarty: Sure. My question then would be how your last two sentences could be made precise. Franz Lemmermeyer (1st comment): Sure. My question is whether anything in this direction can be said, exactly because the trivial bound mentioned in my question is worthlessly crude. Sorry for not being clear enough on this. $\endgroup$ Sep 26, 2013 at 10:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.