Associated Topics || Dr. Math Home || Search Dr. Math

Discussion of Euclidean Functions of Z

Date: 06/10/2008 at 17:00:38
From: Joe
Subject: Euclidean Functions of Z

The common example is of course the absolute value function, but it
seems to me like some other, VERY weird Euclidean functions can be
constructed.

I am reading Introduction to Algebra by Peter Cameron.  (So I do
know *some* abstract algebra.)  Anyways, the book led me to ask this
question.  Not sure if there is any "nice" answer.

Date: 06/13/2008 at 07:06:48
From: Doctor Jacques
Subject: Re: Euclidean Functions of Z

Hi Joe,

There are indeed many possible Euclidean functions on Z.  The
definition of a Euclidean function only involves inequalities;
therefore, any function that respects those inequalities can be used
as a valid Euclidean function.  To be more explicit:

Assume f : Z \ {0} -> N is a Euclidean function, and g is another
function from Z \ {0} to N such that g(a) <= g(b) if and only if
f(a) <= f(b).  Then g is also a Euclidean function.  Note that this
implies that f(a) = f(b) if and only if g(a) = g(b), which means that
g(n) is an injective function of f(n), and that function is strictly
increasing.

In particular, with f(n) = |n|, we see that any strictly increasing
function of |n| is a valid Euclidean function for Z.  This gives
plenty of functions, for example g(n) = a|n|^k + b, with a > 0 and
k >= 1.  These functions satisfy the relations:

g(a) = g(-a)                 [1]
|a| < |b| ==> g(a) < g(b)    [2]

However, these functions are not really "interesting", in the sense
that they lead to the same division algorithm.  A more interesting
question would be if there can be any other Euclidean functions that
are not strictly increasing functions of |n| ?

A first observation is that, as a |(-a) and (-a)|a, any Euclidean
function g must satisfy:

g(a) <= g(-a)
g(-a) <= g(a)

which reduces to g(a) = g(-a).  In other words, g(a) must be a
function of |a|, i.e., g must satisfy [1].

A Euclidean function places restrictions on how the quotient of a
division is computed in the Euclidean algorithm.  Usually, when we
divide a by b, the quotient is computed by truncating the rational
quotient toward 0.  If a and b are positive, the quotient is the
integer part of a/b.  If we want a Euclidean function g to be
compatible with that rule, then g must satisfy [2] as well.  To see
this, assume that:

0 < a < b

The division of a by b gives:

a = 0*b + a

i.e., the quotient is 0 and the remainder is a.  By the definition of
a Euclidean function, this means that we must have g(a) < g(b), and g
must satisfy [2] (the case of negative numbers is taken care of by
noticing that, as we already saw, g must also satisfy [1]).

The conclusion is that, if we restrict ourselves to the standard way
of computing the integer quotient of a division, [1] and [2] are
necessary and sufficient conditions for g to be a Euclidean function.

However, there may be another way to compute the quotient of a
division.  The important thing is to ensure that the gcd algorithm
terminates after a finite number of steps, and this will be the case
if the remainder is smaller than the divisor (in absolute value).
This can also be achieved by rounding the rational quotient to the
nearest integer instead of truncating it toward 0.  For example, if we
divide 11 by 7, we can write, as usual:

11 = 1*7 + 4

but we can also write:

11 = 2*7 + (-3)

In this case, the remainder is -3; as |-3| < |7|, this will also
ensure that the gcd algorithm will terminate (in fact, as the
remainder is smaller in this case, the algorithm will often terminate
in fewer steps).  If you are only interested in computing the gcd, you
may ignore the signs; if you use the extended algorithm, for example
to compute modular inverses, then you must carefully take the sign
into account.

If we use this modification of the algorithm, when we divide a by b,
we will always have:

a = b*q + r
|r| <= [|b/2|]

instead of merely |r| < |b| ([x] denotes the integer part of x).  In
terms of the corresponding Euclidean function, this translates to:

g([b/2]) < g(b)   [3]

instead of [2].  Of course, any function that satisfies [2] will also
satisfy [3], but, if we replace [2] by [3], we can allow g to grow
more slowly.

Let us build the "smallest" possible function g that satisfies [1]
and [3].  Because of [1], we can limit ourselves to positive integers.
We start by defining, arbitrarily, g(1) = 1.  Now, [3] implies that we
must have g(2) > g(1) = 1, and the smallest possible value is
g(2) = 2.  In the same way, we must have g(3) > 1, and we can take
g(3) = 2 also.

We must then have g(4) > g(2) = 2, and we take g(4) = 3.  In the same
way, we have g(5) = g(6) = g(7) = 3.

The pattern that emerges is that g(n) increases by 1 whenever n is a
power of 2.  Specifically, given n, there is a unique integer k such
that:

2^k <= n < 2^(k+1)

and we have g(n) = k+1.  More formally, we have:

g(n) = 1 + [log_2(n)]      [4]

where log_2 is the base 2 logarithm.  More intuitively, g(n) is the
number of bits required to write n in binary.

This function g does not satisfy [2]: it is really new, in the sense
that it implies a modification of the gcd algorithm.  Note that a
function that increases more slowly leads to a faster algorithm
(which means that the modified algorithm is interesting in itself,
since it is usually faster).

From this function g, you can again define a whole set of valid
Euclidean functions:  any strictly increasing function of g(n) will
do.

Please feel free to write back if you require further assistance.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
Associated Topics:
College Modern Algebra
High School Functions

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search