Add a method `divides` to Polynomial #19171

bgrenet · 2015-09-09T09:24:04Z

The generic method divides that can be found in src/sage/structure/element.pyx uses quo_rem (via %) to test if an element divides another one: return (x % self) == 0.

For polynomials, depending on the implementations, the method quo_rem may raise an error if the divisor is not monic (see #16649 for more on this).

This ticket aims at implementing a method divides for the class Polynomial, so that it catches the errors in quo_rem to return False when it is needed.

Example of a problematic behavior:

sage: R.<x> = PolynomialRing(ZZ, implementation="FLINT")
sage: p = 2*x + 1
sage: q = R.random_element(10)
sage: p.divides(q)
False
sage: R.<x> = PolynomialRing(ZZ, implementation="NTL")
sage: p = R(p)
sage: q = R(q)
sage: p.divides(q)
Traceback (most recent call last):
...
ArithmeticError: division not exact in Z[x] (consider coercing to Q[x] first)

Depends on #16649
Depends on #25277

Component: commutative algebra

Keywords: polynomial, division

Author: Bruno Grenet

Branch/Commit: 94c0390

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/19171

The text was updated successfully, but these errors were encountered:

bgrenet · 2015-09-09T09:24:24Z

Dependencies: 16649

bgrenet · 2015-09-09T09:24:59Z

Changed dependencies from 16649 to #16649

bgrenet · 2015-09-09T11:48:26Z

Branch: u/bruno/t19171_divides_poly

bgrenet · 2015-09-09T11:48:45Z

New commits:

`98b7ca1`	`Rebased on 6.9beta1`
`6d0da24`	`One last zero_element removed + correct one doctest`
`dbfb518`	`Remove useless colons`
`331c713`	`#19171: New method divides`

bgrenet · 2015-09-09T11:48:45Z

Commit: 331c713

sagetrac-git · 2016-05-22T16:09:49Z

Changed commit from 331c713 to 27040e0

sagetrac-git · 2016-05-22T16:09:49Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`27040e0`	`#19171: New method divides`

sagetrac-git · 2016-05-23T09:38:41Z

Changed commit from 27040e0 to 9a189c7

sagetrac-git · 2016-05-23T09:38:41Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`9a189c7`	`#19171: New method divides`

bgrenet · 2016-05-23T09:41:21Z

comment:8

I added some noise with two forced pushes (due to some mistake I made), but there is really only one commit! Now the ticket passes the tests (as far as I can tell) and is very ready for review!

videlec · 2016-07-11T18:56:19Z

comment:9

You would better use coerce_binop from sage.structure.element rather than a manually handled coercion.

Why is this code specific to polynomials?

videlec · 2016-07-11T18:56:31Z

Reviewer: Vincent Delecroix

sagetrac-git · 2016-07-18T13:21:20Z

Changed commit from 9a189c7 to ac43c02

sagetrac-git · 2016-07-18T13:21:20Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`d03a75e`	`#19171: New method divides`
`ac43c02`	`19171: Use coerce_binop`

bgrenet · 2016-07-18T16:49:31Z

comment:12

Replying to @videlec:

You would better use coerce_binop from sage.structure.element rather than a manually handled coercion.

Done.

Why is this code specific to polynomials?

I tried to explain the reasons in the description: For polynomials over (say) ZZ, the euclidean division is not well defined. The problem occurs when the leading coefficient is not invertible. There are several ways to deal with this problem, and different implementations in Sage use different conventions (see #16649 for pointers on this). As a result, testing divisibility by invoking self % p == 0 can lead to ArithmeticError for polynomials: But when this exception is raised, we know that self does not divide p.¹ That's why I decided to add this new method which only differs from the generic one by the fact it catches the exception.

I could have changed the generic method instead to catch an ArithmeticError and return False in such case, but though I am pretty confident that it makes sense for polynomials, I am much less confident concerning other rings.

¹ "We know" is maybe a too strong assumption. In #16649, I did changes that ensure that the assumption holds for all current implementations of polynomials in Sage. (This was not the case before.) Yet, future implementations may break this rule. This may imply that we shouldn't simply rely on quo_rem to test divisibility.

bgrenet · 2018-06-12T16:02:16Z

comment:37

The difficulties with rings such as Zmod(6) let me think that we should indeed restrict to polynomials over integral domains. The problem being that I actually do not know for instance how to test divisibility over Zmod(6).

If we decide this, the problem with PolynomialRing(ZZ, 'x', implementation="NTL") remains since quo_rem cannot be used there without catching an exception, which is not very appealing... Should we convert first the polynomial to polynomials over the fraction field of the base ring?

videlec · 2018-06-16T17:31:16Z

comment:38

Replying to @bgrenet:

The difficulties with rings such as Zmod(6) let me think that we should indeed restrict to polynomials over integral domains. The problem being that I actually do not know for instance how to test divisibility over Zmod(6).

There is #25277 for that (it is merged in beta3 already). So you can test for division... but you can not divide yet.

If we decide this, the problem with PolynomialRing(ZZ, 'x', implementation="NTL") remains since quo_rem cannot be used there without catching an exception, which is not very appealing... Should we convert first the polynomial to polynomials over the fraction field of the base ring?

It is fine to catch an exception, but it should be clear what it means.

bgrenet · 2018-06-18T14:42:01Z

comment:39

Replying to @videlec:

Replying to @bgrenet:

The difficulties with rings such as Zmod(6) let me think that we should indeed restrict to polynomials over integral domains. The problem being that I actually do not know for instance how to test divisibility over Zmod(6).

There is #25277 for that (it is merged in beta3 already). So you can test for division... but you can not divide yet.

I meant testing divisibility of polynomials over Zmod(6). I am not sure that it can be reduced to simply testing divisibility of elements of Zmod(6), I think you need to perform some divisions.

videlec · 2018-06-18T20:31:15Z

comment:40

Replying to @bgrenet:

Replying to @videlec:

Replying to @bgrenet:

The difficulties with rings such as Zmod(6) let me think that we should indeed restrict to polynomials over integral domains. The problem being that I actually do not know for instance how to test divisibility over Zmod(6).

There is #25277 for that (it is merged in beta3 already). So you can test for division... but you can not divide yet.

I meant testing divisibility of polynomials over Zmod(6). I am not sure that it can be reduced to simply testing divisibility of elements of Zmod(6), I think you need to perform some divisions.

A far from efficient method consist in

testing divisibility of leading coefficients b_m | a_n
if yes, test all possible quotients q so that a_n = q b_m

But for that, you need a method that return all quotients. Hence my remark.

bgrenet · 2018-06-19T13:34:32Z

comment:41

So do you agree with me that we should better abandon non-integral rings (at least for now)?

videlec · 2018-06-19T14:48:41Z

comment:42

Replying to @bgrenet:

So do you agree with me that we should better abandon non-integral rings (at least for now)?

yes

sagetrac-git · 2018-06-19T15:21:14Z

Branch pushed to git repo; I updated commit sha1. New commits:

`fbc129c`	`Merge branch 'u/bruno/t19171_divides_poly' of git://trac.sagemath.org/sage into ticket/19171`
`213ccd8`	`Add degree test and lc test`

sagetrac-git · 2018-06-19T15:21:14Z

Changed commit from 5bac984 to 213ccd8

sagetrac-git · 2018-06-19T15:22:20Z

Branch pushed to git repo; I updated commit sha1. New commits:

`235735f`	`19171: only for integral domains`

sagetrac-git · 2018-06-19T15:22:20Z

Changed commit from 213ccd8 to 235735f

bgrenet · 2018-06-19T15:23:16Z

comment:45

Is the proposed solution ok for you?

videlec · 2018-06-19T21:45:57Z

comment:46

You are not doing the right thing on non-integral domains. You should test is_integral_domain much earlier. With the ticket applied

sage: R.<x> = Zmod(6)[]
sage: (2*x +1).divides(3)
False
sage: (2*x + 1) * 3 == 3
True

(testing divisibility of leading coefficient is not even valid... I was wrong)

You need a line break after TESTS::

It should be documented that this method only works for integral domains. And the examples with Zmod(6) (raising error) should be in the EXAMPLES block rather than TESTS.

sagetrac-git · 2018-07-04T14:56:54Z

Changed commit from 235735f to 94c0390

sagetrac-git · 2018-07-04T14:56:54Z

Branch pushed to git repo; I updated commit sha1. New commits:

`94c0390`	`19171: Divides implemented only for integral domains`

bgrenet · 2018-07-04T15:04:46Z

comment:48

I've followed your advice, and changed my mind: My idea was to give an answer (for non-integral domains) as long as I am able to do so. The problem with the divisibility of leading coefficients made me adopt the opposite viewpoint: Divisibility is not implemented for non-integral domains, that's it. I am not sure that an implementation which only works in some uninteresting cases would be helpful to anyone!

videlec · 2018-08-03T19:20:18Z

comment:49

update milestone 8.3 -> 8.4

videlec · 2018-08-23T03:53:38Z

comment:50

ok

vbraun · 2018-08-26T09:38:16Z

Changed branch from u/bruno/t19171_divides_poly to 94c0390

bgrenet added this to the sage-6.9 milestone Sep 9, 2015

bgrenet added c: basic arithmetic labels Sep 9, 2015

bgrenet added the s: needs review label Sep 9, 2015

bgrenet added c: commutative algebra and removed c: basic arithmetic labels May 22, 2016

bgrenet modified the milestones: sage-6.9, sage-7.3 May 22, 2016

videlec added s: needs work and removed s: needs review labels Jul 11, 2016

bgrenet added s: needs review and removed s: needs work labels Jul 18, 2016

videlec modified the milestones: sage-8.0, sage-8.3 May 12, 2018

bgrenet added s: needs review and removed s: needs work labels Jul 4, 2018

videlec modified the milestones: sage-8.3, sage-8.4 Aug 3, 2018

videlec added s: positive review and removed s: needs review labels Aug 23, 2018

vbraun removed the s: positive review label Aug 26, 2018

vbraun closed this as completed in 71e8975 Aug 26, 2018

bgrenet mentioned this issue Dec 29, 2022

More capable method valuation for polynomials #19172

Open

defeo mentioned this issue Jan 26, 2019

Regression in .divides() for generic polynomials #27064

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add a method `divides` to Polynomial #19171

Add a method `divides` to Polynomial #19171

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

sagetrac-git mannequin commented May 22, 2016

sagetrac-git mannequin commented May 22, 2016

sagetrac-git mannequin commented May 23, 2016

sagetrac-git mannequin commented May 23, 2016

bgrenet commented May 23, 2016

videlec commented Jul 11, 2016

videlec commented Jul 11, 2016

sagetrac-git mannequin commented Jul 18, 2016

sagetrac-git mannequin commented Jul 18, 2016

bgrenet commented Jul 18, 2016

bgrenet commented Jun 12, 2018

videlec commented Jun 16, 2018

bgrenet commented Jun 18, 2018

videlec commented Jun 18, 2018

bgrenet commented Jun 19, 2018

videlec commented Jun 19, 2018

sagetrac-git mannequin commented Jun 19, 2018

sagetrac-git mannequin commented Jun 19, 2018

sagetrac-git mannequin commented Jun 19, 2018

sagetrac-git mannequin commented Jun 19, 2018

bgrenet commented Jun 19, 2018

videlec commented Jun 19, 2018

sagetrac-git mannequin commented Jul 4, 2018

sagetrac-git mannequin commented Jul 4, 2018

bgrenet commented Jul 4, 2018

videlec commented Aug 3, 2018

videlec commented Aug 23, 2018

vbraun commented Aug 26, 2018

Add a method divides to Polynomial #19171

Add a method divides to Polynomial #19171

Comments

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

bgrenet commented Sep 9, 2015

sagetrac-git mannequin commented May 22, 2016

sagetrac-git mannequin commented May 22, 2016

sagetrac-git mannequin commented May 23, 2016

sagetrac-git mannequin commented May 23, 2016

bgrenet commented May 23, 2016

videlec commented Jul 11, 2016

videlec commented Jul 11, 2016

sagetrac-git mannequin commented Jul 18, 2016

sagetrac-git mannequin commented Jul 18, 2016

bgrenet commented Jul 18, 2016

bgrenet commented Jun 12, 2018

videlec commented Jun 16, 2018

bgrenet commented Jun 18, 2018

videlec commented Jun 18, 2018

bgrenet commented Jun 19, 2018

videlec commented Jun 19, 2018

sagetrac-git mannequin commented Jun 19, 2018

sagetrac-git mannequin commented Jun 19, 2018

sagetrac-git mannequin commented Jun 19, 2018

sagetrac-git mannequin commented Jun 19, 2018

bgrenet commented Jun 19, 2018

videlec commented Jun 19, 2018

sagetrac-git mannequin commented Jul 4, 2018

sagetrac-git mannequin commented Jul 4, 2018

bgrenet commented Jul 4, 2018

videlec commented Aug 3, 2018

videlec commented Aug 23, 2018

vbraun commented Aug 26, 2018

Add a method `divides` to Polynomial #19171

Add a method `divides` to Polynomial #19171