Discussion of Euclidean Functions of Z

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

Please help me give a description of all 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/