Le 26/01/2015 14:41, Vincent Delecroix a écrit :
Hello,
2015-01-26 14:22 UTC+01:00, Bruno Grenet <bruno.gre...@gmail.com>:
In the special case of univariate polynomials over ZZ, I think there are
two possibilities for xgcd:
- either xgcd(p,q) = (g,u,v) where g = gcd(p,q) = up+vq with u,v in QQ[x];
- or xgcd(p,q) = (g×r, u, v) where g = gcd(p,q), r = res(p,q), g×r =
up+vq with u,v in ZZ[x].
Note that this second solution is precisely what we have in Sage right now
{{{
sage: x = polygen(ZZ)
sage: (x+2).xgcd(x+4)
(2, -1, 1)
}}}
Only the function `xgcd` is badly documented not the method of
polynomials. (And in the case when p and q are coprime over QQ, the
first term obtained from xgcd is the resultant.)
In the function `xgcd`, we have the following note:
| One exception is if `a` and `b` are not in a PID, e.g., they are
both polynomials over the integers, then this function can't in
general return ``(g,s,t)`` as above, since they need not exist.
Instead, over the integers, we first multiply `g` by a divisor of
the resultant of `a/g` and `b/g`, up to sign.
|
|The documentation seems OK to me.|
More generally, Bézout coefficients seem to be usually defined only for
PID, and this motivates the first solution (in general, replace ZZ by a
UFD R and QQ by its field of fractions K). The second solution has the
advantage of staying in the same polynomial ring, and it has a clear
definition. I would go for the second solution, with an updated
documentation.
Do you know in which context this second definition of Bézout
coefficients make sense? I guess we need the fraction field to be a
PID (or more generally a Bézout ring).
I do not understand your question, since the fraction field is always...
a field, so in particular a PID and a Bézout ring. All you need is to be
able to define a GCD (you need to have a GCD domain, in particular UFDs
and Bézout domains are GCD domains) and the resultant (you only need a
commutative ring for this). Of course, I am only talking of polynomial
rings.
Consider a GCD domain R, and polynomials over R. Let p,q in R[X] and g
their GCD. Then p/g and q/g being coprime, their resultant r is nonzero.
If I am not mistaken, then you can define Bézout coefficients (u,v) in
R[X] for p and q so that g×r = up+vq.
I am not tempted with a version of xgcd that has its member in another
ring... but for mysterious backward compatibility reasons we also have
{{{
sage: gcd(3.0, 6.0)
3
sage: gcd(3.0, 6.0).parent()
Integer Ring
}}}
And I would like the above behavior to be modified within #17671.
I agree with you. There is an incoherence between the two cases
`gcd(RR(3),RR(6)).parent()` which returns `Integer Ring` and
`gcd(QQ(3),QQ(6)).parent()` which return `Rational Field`. And I prefer
the second case.
Bruno
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
