Salut !
I disagree with John and Jeroen that xgcd should not be defined or
should return an error for non-PID UFDs. For now, I checked the
possibilities for the rings of polynomials over a UFD.
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].
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.
I checked the following textbooks:
- Cohen's "A course in computational algebraic number theory": there is
a remark and an exercise about Bézout coefficients for polynomials over
UFD, in the same vein as the second possibility I mentioned above.
- von zur Gathen and Gerhard's "Modern Computer Algebra": The extended
Euclidean algorithm and Bézout coefficients are defined for PID only.
- Knuth's "The Art of Computer Programming Vol. 2: Semi-numerical
algorithms": As in "Modern Computer Algebra".
Cheers,
Bruno
Le 26/01/2015 13:59, mmarco a écrit :
Anyways, we should take into account that, even when both gcd and xgcd
are well defined, their definition coincide and everything is happy...
there are still defined only up to product of a unit. So there is yet
another possible source of inconsistency.
El domingo, 25 de enero de 2015, 21:05:00 (UTC+1), vdelecroix escribió:
Hello,
On sage-support somebody reported the following strange behavior
sage: gcd(6/1,2/1)
2
sage: xgcd(6/1,2/1)
(1, 1/6, 0)
I opened #17671 for that and it comes from the fact that there is a
custom gcd for QuotientFields but no associated xgcd. I did it and it
work fine.
But, in order to get this behavior fixed once for all I introduced a
test "_test_gcd_vs_xgcd" in the category CommutativeRings to check
compatibility between gcd and xgcd if they are implemented. But it
appear that some polynomial ring just fail:
sage: TestSuite(Zmod(10)['a']).run()
Failure in _test_gcd_vs_xgcd:
...
AssertionError: The methods gcd and xgcd disagree:
gcd(a,2*a^2 + 2) = 1
xgcd(a,2*a^2 + 2) = (2, 8*a, 1)
------------------------------------------------------------
The following tests failed: _test_gcd_vs_xgcd
My question is: do we have a use case where gcd and xgcd should
disagree?
Vincent
PS: On a related note, the following looks very wrong to me
{{{
sage: x = polygen(ZZ)
sage: (x+2).gcd(x+4)
1
}}}
--
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
<mailto:sage-devel+unsubscr...@googlegroups.com>.
To post to this group, send email to sage-devel@googlegroups.com
<mailto: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.
--
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.
