Something very similar to this is needed for modular symbols, with the ring ZZ instead of polynomials, so there is likely to be a function somewhere which does this and could be adapted.
If no-one else is more explicit I'll look for a reference tomorrow. John On Wed, May 25, 2011 at 10:16 PM, Rob Beezer <goo...@beezer.cotse.net> wrote: > Thanks, Georg. I know Euclidean rings, but did not recognize the > requested function as a defining property. I usually teach them as > "admitting" the "degree" function. So that may help me go fishing. > > If anybody knows the code well enough to know such a thing is *not* > available, that'd be helpful as well. I have a short algorithm I can > implement, but I'd rather have something that already exists, is > tested and optimized. Right now I'm just stalling getting started > (this is a first step of a larger algorithm). > > Rob > > On May 25, 1:45 pm, "Georg S. Weber" <georgswe...@googlemail.com> > wrote: >> On 25 Mai, 08:18, Rob Beezer <goo...@beezer.cotse.net> wrote: >> >> > I'm wondering if Sage has the following function for polynomials over >> > a field. Mostly, I don't know if it is a common thing to expect, and >> > if so, I have no idea what it would be called. So a pointer would be >> > of real help, if it exists. The paper I am cribbing from is about >> > matrices over ZZ, but I suspect it generalizes to any PID, so I may >> > not be translating everything exactly right (eg the degree condition). >> >> > Input: p, q, r in F[x] with gcd(p, q, r) = 1 >> >> > Output: s in F[x] such that gcd(p + sq, r) = 1, degree(s) < >> > degree(r) >> >> > Thanks, >> > Rob >> >> Hi Rob, >> >> a partial (mathematicians) answer: the property in question is the >> defining property of "Euclidean rings" (look e.g. in van der Waerden's >> "Algebra I"). By definiton, such a ring is (or can be) equipped with a >> "degree" function such that the usual "Euclidean algorithm" can be >> made to work. Euclidean rings can easily shown to be PIDs (but there >> are PIDs that can't be equipped with any such a "Euclidean degree" >> function). Prime examples are the rational integers (degree == >> absolute value) and univariate polynomial rings over fields (degree == >> degree as polynomial). Now, what I do not know is whether in the >> hierarchy of rings in Sage, Euclidean rings show up as ancestors of >> PIDs, or whether there is some property "IsEuclidean()" and if so, >> "EuclideanDegreeFunction()", "EuclideanGCD()", "EuclideanXGCD()" or >> such. Hope this helps anyway! >> >> Cheers, >> Georg > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-devel > URL: http://www.sagemath.org > -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
