Discussion of Euclidean Functions of ZDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/