Re: [sage-devel] Re: Factorization of multivariate integer polynomial
On Fri, 4 Oct 2013, Marco Streng wrote: Just take the factorization over QQ, then for each factor, make it a primitive integral polynomial, i.e., multiply by the lcm of the denominators of the coefficients and divide by the gcd of the numerators of the coefficients. Then you have a factorization into irreducible integral polynomials times some integer, factor that integer and you have the complete factorization over ZZ. Isn't that what Sage already does? I mean R.x = QQ[]; print (4*x^2-1).factor() R.x,y = QQ[]; print (4*x^2-1).factor() prints (4) * (x - 1/2) * (x + 1/2) (2*x - 1) * (2*x + 1) -- Jori Mäntysalo -- 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/groups/opt_out.
Re: [sage-devel] Re: Factorization of multivariate integer polynomial
On 7 October 2013 08:15, Jori Mantysalo jori.mantys...@uta.fi wrote: On Fri, 4 Oct 2013, Marco Streng wrote: Just take the factorization over QQ, then for each factor, make it a primitive integral polynomial, i.e., multiply by the lcm of the denominators of the coefficients and divide by the gcd of the numerators of the coefficients. Then you have a factorization into irreducible integral polynomials times some integer, factor that integer and you have the complete factorization over ZZ. Isn't that what Sage already does? I mean R.x = QQ[]; print (4*x^2-1).factor() R.x,y = QQ[]; print (4*x^2-1).factor() prints (4) * (x - 1/2) * (x + 1/2) (2*x - 1) * (2*x + 1) And also: sage: R.x = ZZ[]; print (4*x^2-1).factor() (2*x - 1) * (2*x + 1) sage: R.x,y = ZZ[]; print (4*x^2-1).factor() --- NotImplementedError Traceback (most recent call last) John -- Jori Mäntysalo -- 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/groups/opt_out. -- 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/groups/opt_out.
Re: [sage-devel] Re: Factorization of multivariate integer polynomial
On Mon, 7 Oct 2013, John Cremona wrote: sage: R.x,y = ZZ[]; print (4*x^2-1).factor() --- NotImplementedError Traceback (most recent call last) But that is just what I would like to implement, i.e. make few lines of code that converts polynomial to QQ, factors it and then convert back to ZZ. (But my first suggestion lacks .unit(), which need to be added.) -- Jori Mäntysalo -- 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/groups/opt_out.
Re: [sage-devel] Re: Factorization of multivariate integer polynomial
2013/10/7 Jori Mantysalo jori.mantys...@uta.fi On Mon, 7 Oct 2013, John Cremona wrote: sage: R.x,y = ZZ[]; print (4*x^2-1).factor() --**--** --- NotImplementedError Traceback (most recent call last) But that is just what I would like to implement, i.e. make few lines of code that converts polynomial to QQ, factors it and then convert back to ZZ. Great, when you do, make sure to mention the ticket number on this thread. (But my first suggestion lacks .unit(), which need to be added.) It's not just a matter of units. In polynomial rings over QQ, all non-zero constants are units. In polynomial rings over ZZ, only +/- 1 are units, prime numbers are primes, and composite numbers are neither units nor primes (hence need to be factored). This is correctly implemented for ZZ[x], QQ[x] and QQ[x,y]: sage: P.x = ZZ[] sage: p = -15*(3*x+2)*(7*x-5) sage: f = p.factor() sage: f.unit() -1 sage: list(f) [(3, 1), (5, 1), (3*x + 2, 1), (7*x - 5, 1)] sage: P.x = QQ[] sage: p = -15*(3*x+2)*(7*x-5) sage: f = p.factor() sage: f.unit() -315 sage: list(f) [(x - 5/7, 1), (x + 2/3, 1)] sage: P.x,y = QQ[] sage: p = -15*(3*x+2)*(7*x-5) sage: f = p.factor() sage: f.unit() -15 sage: list(f) [(3*x + 2, 1), (7*x - 5, 1)] -- Jori Mäntysalo -- 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+unsubscribe@**googlegroups.comsage-devel%2bunsubscr...@googlegroups.com . To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/**group/sage-develhttp://groups.google.com/group/sage-devel . For more options, visit https://groups.google.com/**groups/opt_outhttps://groups.google.com/groups/opt_out . -- 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/groups/opt_out.
[sage-devel] Re: Factorization of multivariate integer polynomial
If the integral polynomial is not monic then the roots need not be integral: sage: R.x = QQ[] sage: (4*x^2-1).factor() (4) * (x - 1/2) * (x + 1/2) So this would not be factorizable in ZZ[x] but is factorizable in QQ[x] On Friday, October 4, 2013 12:44:41 PM UTC+1, Jori Mantysalo wrote: $SAGE_ROOT/devel/sage-main/sage/rings/polynomial/multi_polynomial_libsingular.pyx contains if not self._parent._base.is_field(): raise NotImplementedError, Factorization of multivariate polynomials over non-fields is not implemented. It seems trivial to have at least working (but maybe slow) fix for ZZ: if not self._parent._base.is_field(): if type(self._parent._base)==sage.rings.integer_ring.IntegerRing_class: return sage.structure.factorization.Factorization ( [ (t[0].change_ring(sage.rings.integer_ring.ZZ), t[1]) for t in self.change_ring(sage.rings.rational_field.QQ).factor(proof) ] ) else: raise NotImplementedError, Factorization of multivariate polynomials over non-fields (except ZZ) is not implemented. However, this sounds TOO easy. Is there some untriviality lying somewhere? -- Jori M�ntysalo -- 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/groups/opt_out.
Re: [sage-devel] Re: Factorization of multivariate integer polynomial
On Fri, 4 Oct 2013, Volker Braun wrote: If the integral polynomial is not monic then the roots need not be integral: sage: R.x = QQ[] sage: (4*x^2-1).factor() (4) * (x - 1/2) * (x + 1/2) So this would not be factorizable in ZZ[x] but is factorizable in QQ[x] Of course. Duh. Anyways, is this possible path to (non-optimal) solution? Factor in QQ, get parts that are not integral polynomials and multiply them to get integral parts? It would of course be quite slow if polynomial happens to have many factors that must be check to find integral-producing products. -- Jori Mäntysalo -- 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/groups/opt_out.
Re: [sage-devel] Re: Factorization of multivariate integer polynomial
2013/10/4 Jori Mantysalo jori.mantys...@uta.fi On Fri, 4 Oct 2013, Volker Braun wrote: If the integral polynomial is not monic then the roots need not be integral: sage: R.x = QQ[] sage: (4*x^2-1).factor() (4) * (x - 1/2) * (x + 1/2) (4*x^2-1) = (2*x-1)*(2*x+1) ZZ[x] has unique factorization, and so does ZZ[x,y], and so does any multivariate polynomial ring over ZZ. Indeed, for any UFD R, the polynomial ring R[x] is again a UFD, hence by induction so are multivariate polynomial rings. So this would not be factorizable in ZZ[x] but is factorizable in QQ[x] Of course. Duh. Anyways, is this possible path to (non-optimal) solution? Factor in QQ, get parts that are not integral polynomials and multiply them to get integral parts? It would of course be quite slow if polynomial happens to have many factors that must be check to find integral-producing products. Just take the factorization over QQ, then for each factor, make it a primitive integral polynomial, i.e., multiply by the lcm of the denominators of the coefficients and divide by the gcd of the numerators of the coefficients. Then you have a factorization into irreducible integral polynomials times some integer, factor that integer and you have the complete factorization over ZZ. The only part that can be slow is the factorization of the integer in the end, the rest is very fast. It just requires a little bit more programming than what you wrote before. -- Jori Mäntysalo -- 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+unsubscribe@**googlegroups.comsage-devel%2bunsubscr...@googlegroups.com . To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/**group/sage-develhttp://groups.google.com/group/sage-devel . For more options, visit https://groups.google.com/**groups/opt_outhttps://groups.google.com/groups/opt_out . -- 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/groups/opt_out.
