Consider GCD ring theoretically. If a and b are elements of a ring R (which really should be an integral domain), GCD(a,b) is the smallest ideal in R containing a and b, and is the set of elements of the form ax + by as x and y range over R. An ideal containing 1 can only be the entire ring. If the ring is a field, then the only ideals are {0} and the entire field. GCD(a,b) depends on the containing ring R. If we take R to be the real numbers, then GCD(1,π) is R, which is also the ideal (a) for any nonzero a. So one can let GCD(1,π) be any nonzero real number. -- Gene
Continuing in this abstract vein, I think I'd argue for letting GCD(x,y) evaluate to itself ("GCD(x,y)") in the event that the ideal generated by x and y is non-principal. Imagine a situation in which the ideal generated by x and y is principal, as is the ideal generated by x, y, and z, but the ideal generated by y and z is not. We'd like our computer algebra system to give the same output when evaluating GCD(GCD(x,y),z) or GCD(x,GCD(y,z)). On the other hand, I think it'd be too much to expect a GCD routine to have too many nice formal properties if we're going to subject it to such abuse. Come to think of it, if we're really going to use a GCD routine in rings other than Z, we need a general rule for breaking ties between elements of the ring and their associates. It's clear how to do this in Z[i] or Q[x,y], but unclear to me how to do this in general. Anyway, while there are things about Mathematica that I don't like, I respect its tendency to answer hard questions by repeating the question back to me (as if to say, "You tell me!"). Jim Propp On Thu, Nov 28, 2013 at 1:27 PM, Eugene Salamin <gene_salamin@yahoo.com>wrote:
Consider GCD ring theoretically. If a and b are elements of a ring R (which really should be an integral domain), GCD(a,b) is the smallest ideal in R containing a and b, and is the set of elements of the form ax + by as x and y range over R. An ideal containing 1 can only be the entire ring. If the ring is a field, then the only ideals are {0} and the entire field. GCD(a,b) depends on the containing ring R. If we take R to be the real numbers, then GCD(1,π) is R, which is also the ideal (a) for any nonzero a. So one can let GCD(1,π) be any nonzero real number.
-- Gene _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think a tie between a ring element and its associates is something we have to accept theoretically, even if there are situations where we need to choose a unique associate. Agreed, that GCD(x,y) isn't AFAIK much use when the ideal Rx + Ry is non-principal (R being the ring). Anyway, I think GCD makes the most sense only in principal ideal domains. Hmm, I think we've been tacitly assuming the ring is commutative. What if it isn't? Take for example the ring Li of Lipschitz quaternions := Z + Zi + Zj + Zk. Or the ring Hu of Hurwitz quaternions := Li[(1+i+j+k)/2]. --Dan On 2013-11-28, at 11:03 AM, James Propp wrote:
Continuing in this abstract vein, I think I'd argue for letting GCD(x,y) evaluate to itself ("GCD(x,y)") in the event that the ideal generated by x and y is non-principal.
Imagine a situation in which the ideal generated by x and y is principal, as is the ideal generated by x, y, and z, but the ideal generated by y and z is not. We'd like our computer algebra system to give the same output when evaluating GCD(GCD(x,y),z) or GCD(x,GCD(y,z)).
On the other hand, I think it'd be too much to expect a GCD routine to have too many nice formal properties if we're going to subject it to such abuse. Come to think of it, if we're really going to use a GCD routine in rings other than Z, we need a general rule for breaking ties between elements of the ring and their associates. It's clear how to do this in Z[i] or Q[x,y], but unclear to me how to do this in general.
Anyway, while there are things about Mathematica that I don't like, I respect its tendency to answer hard questions by repeating the question back to me (as if to say, "You tell me!").
I don't have my Knuth in front of me, but I think Knuth already talked about the non-commutative case, including matrices of various sorts. Also, doesn't Hurwitz talk about gcd's over his quaternions? At 12:05 PM 11/28/2013, Dan Asimov wrote:
Anyway, I think GCD makes the most sense only in principal ideal domains.
Hmm, I think we've been tacitly assuming the ring is commutative. What if it isn't?
Take for example the ring Li of Lipschitz quaternions := Z + Zi + Zj + Zk.
Or the ring Hu of Hurwitz quaternions := Li[(1+i+j+k)/2].
GCD over Lipschitz quaternions is discussed in detail in http://arxiv.org/abs/1202.3198 Left and right GCD are distinct functions, defined up to a (right and left resp) unit factor, in {1, -1, i, -i, j, -j, k, -k} . WFL On 11/28/13, Henry Baker <hbaker1@pipeline.com> wrote:
I don't have my Knuth in front of me, but I think Knuth already talked about the non-commutative case, including matrices of various sorts.
Also, doesn't Hurwitz talk about gcd's over his quaternions?
At 12:05 PM 11/28/2013, Dan Asimov wrote:
Anyway, I think GCD makes the most sense only in principal ideal domains.
Hmm, I think we've been tacitly assuming the ring is commutative. What if it isn't?
Take for example the ring Li of Lipschitz quaternions := Z + Zi + Zj + Zk.
Or the ring Hu of Hurwitz quaternions := Li[(1+i+j+k)/2].
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Dan Asimov -
Eugene Salamin -
Fred Lunnon -
Henry Baker -
James Propp