Slightly OT post, more about polynomial GCD than the original question: The flint fmpz_poly_xgcd function is badly named. It should be fmpz_poly_bezout. We might even change it in a later release.
The point is, the result of the Euclidean algorithm in the case of Z[x] is not the gcd, but the resultant. In fact, it is not possible in general to write sf + tg = gcd(f, g) in Z[x]. Everyone knows that you can compute gcd of polynomials over a field K. The ordinary Euclidean algorithm works for K[x]. Wikipedia claims that it is possible to compute gcd in R[x] for any unique factorisation domain R. But in thinking about it last night, I couldn't see why the algorithm doesn't work in any GCD domain R. (The notion of a Euclidean domain and GCD domain are pretty much designed for computers, since they are not so much algebraic definitions as practical ones.) You usually want an integral domain, because the "standard algorithm" requires taking the fraction field of R and you also want gcd to be defined uniquely up to multiplication by a unit, which it is in an integral domain. You need a GCD domain because you need to be able to take the GCD in R in order to compute the content of polynomials. The proof there relies on Gauss' lemma I think, which works in arbitrary GCD domains. Whether there is some issue with picking a standard representation of polynomials over a GCD domain, I'm not sure. Whilst the "standard algorithm" requires working in the fraction field, this is not what you want to do in practice. Given two polynomials f, g in R[x], you first remove their content and take the gcd of their content. Multiply by this at the end. Now you can write d^k*f = g*q + r where d is the leading coefficient of g and k = deg(f) - deg(g) + 1, such that r = 0 or deg(r) < deg(g). This operation is called pseudoremainder. Repeated application of this gives a Euclidean algorithm, though there is an even better version of this algorithm in Henri Cohen's book which divides through by a certain factor known to divide the content, so that things don't blow up too much (in case you happen to be working in a domain where blowup can be a problem). Don't divide by the content itself at each step, because this is known to be highly suboptimal. It doesn't matter that you have multiplied by d^k since you know the polynomial gcd you are looking for is primitive. When the algorithm terminates, just take the primitive part of the result. It turns out that one doesn't even need an integral domain. It is possible to define at least two Euclidean functions on Z/nZ for example, and similarly, one can compute polynomial gcd in Z/nZ[x]. This operation turns out to be useful when you don't want to ever factor the modulus n, which might be prohibitively costly. One has to be careful though. In Z/nZ the GCD is not even unique up to multiplication by a unit! So even if you have a notion of a canonical unit, you can't canonicalise the result. However, the obvious Euclidean functions that are defined on Z/nZ do provide an ordering, so you can at least define a "greatest" common divisor, as artificial and inefficient as that may be. Note that computing GCD in Z/nZ is not the same as computing it in Z/pZ for p prime and hoping for the best. Just for the record, flint required n to be prime when computing GCD of polynomials over Z/nZ. If anyone knows the reason why R is usually required to be a UFD when computing GCD in R[x], I'd be grateful for the reply. Another puzzle I have been trying to work out is to do with the definition of a Euclidean domain. Wikipedia lists two conditions (the second can be ensured if you have the first). I haven't worked out where in the algorithm you require the second condition. Wikipedia doesn't say. It looks like it is designed for the final step of the algorithm, but I haven't been able to guess the details. If anyone knows, I'd also be grateful for the reply. Another interesting question is whether some of the standard half-gcd algorithms (the correct ones, not the numerous incorrect ones in the literature) work whenever the standard variants of the Euclidean algorithm work. I don't see why not, with the proviso that you don't use Strassen 2x2 matrix multiplication and just stick with classical matrix multiplication. I'm sure the answers to my queries will pop into my mind as soon as I press "Post". But there really are a lot of subtle things to do with gcd that are not covered in textbooks, so I guess I shouldn't feel too embarrassed not knowing the answers off the top of my head. On Thursday, 12 February 2015 17:35:56 UTC+1, Bruno Grenet wrote: > > Le 12/02/2015 16:06, kcrisman a écrit : > > As a late postscript, is #8111 related to any of this discussion? I know > this was mostly about Bezout/xgcd stuff, but that ticket looks like it has > languished and could be connected. > > This is clearly the same kind of discussions. The point in #8111 is that > we rely on Flint's gcd function that returns the monic polynomial gcd. > There several possibilities that yield the desired result, and we may even > implement several of them: > > - Change the `gcd` method for QQ['x'] in the same way as we changed the > `gcd` method for QQ, so that it returns a more interesting result when the > inputs actually live in ZZ['x']. Note that this change may also be made for > other methods such as `content`, which always returns 1 for polynomials > over QQ. > > - Change the `reduce` method for rational functions over QQ['x'] in the > same way as above, so that it tests whether the inputs live in ZZ['x']. > > - Change the `reduce` method for rational functions over QQ['x'] so that > it returns monic numerator and denominator. This last solution is > orthogonal to the previous ones, but in this case we would have the > rational functions over QQ represented in a normal form, which is not the > case to date. > > The first and last solutions seem interesting to implement in any way. > > Best, > Bruno > > P.S.: There are other questions and conventions to take that are not fully > resolved around these questions of gcd, quo_rem, ... for polynomials. One > example is #16649 (and the pointers inside) that needs review (shameless > self plug). > > > - kcrisman > > > > > -- > > 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+...@googlegroups.com <javascript:>. > > To post to this group, send email to sage-...@googlegroups.com > <javascript:>. > > 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.
