fix content of polynomials

[videlec]

There is an inconsistency between several implementations of methods content for polynomials which either return the gcd of the coefficients or the ideal generated by the coefficients.

To remove the inconsistency, we implement two distinct methods:

• content returns the gcd of the coefficients;
• content_ideal returns the ideal generated by the coefficients.

In a period of deprecation, for (most) univariate polynomial rings, content is a deprecated alias for content_ideal. In the future, content will be defined everywhere as described above.

CC: @sagetrac-mkosters @loefflerd

Component: commutative algebra

Keywords: polynomial, content

Work Issues: followup ticket mentioned in source code, update ticket summary

Author: Bruno Grenet

Branch/Commit: 017adb6

Reviewer: Julian Rüth

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

[bgrenet]

comment:2

The content of a polynomial is sometimes defined as the gcd of its coefficients, and sometimes as the ideal generated by the coefficients. In SageMath, we have inconsistencies between polynomial rings:

• For Flint, NTL, p-adics and multivariate polynomial rings, content returns the gcd of the coefficients.

• The generic implementation (for the class rings.polynomial.polynomial_element.Polynomial) returns an ideal. This is means that for polynomials over weird rings, and for all sparsely represented univariate polynomials, content returns an ideal.

I propose to make all the implementations return a element of the base ring rather than an ideal.

Rationale:

• This means changing only one method.
• This is consistent with MuPAD, Maple, Mathematica (though the name of the function is different) and Magma (also for the multivariate case)
• This is the definition taken for instance by von zur Gathen and Gerhard in Modern Computer Algebra or Cohen in A course in Computational Number Theory.

P.S.: I cc the author and reviewer of #12218 in which the generic content was implemented.

[bgrenet]

comment:3

Addendum: One could also let the possibility of having the ideal, with one of the following two propositions. I am not sure this is useful.

• Add a keyword ideal so that an ideal is returned if ideal is set to True (defaut False).
• Create a new method content_ideal or ideal_content for today's behavior of the generic implementation.

[kedlaya]

comment:4

I'm okay with having a method content_ideal for the generic behavior. But what is supposed to be returned by content when the content ideal is not principal? This is certainly likely to happen if the base ring is the ring of integers in a number field. Perhaps it is best if content is only implemented in those cases where it has a sensible definition at the level of elements.

[bgrenet]

comment:5

Replying to @kedlaya:

I'm okay with having a method content_ideal for the generic behavior. But what is supposed to be returned by content when the content ideal is not principal? This is certainly likely to happen if the base ring is the ring of integers in a number field. Perhaps it is best if content is only implemented in those cases where it has a sensible definition at the level of elements.

Of course, this is a difficulty... Well, I propose then to implement content for polynomials over principal ideal domains (so that it returns a element of the domain, not an ideal), and content_ideal more generally. And of course to add a deprecation warning for content over non principal ideal domains. We may also add a warning (no deprecation) for the new behavior of content in the generic implementation.

I'll work on a proposal and let you tell me what you think about it.

[bgrenet]

comment:6

I am trying to provide some code for this. I'd like opinions on two points:

1. To avoid future inconsistencies, I plan to implement not only content and content_ideal, but also the related primitive_part and is_primitive for all polynomial rings with consistent semantics. Do you think it is appropriate to do so in this ticket, or do you think that it's better to stick with content and content_ideal only?

2. What should it be the semantic for fields?

---

Remarks for the semantics for fields:

Currently, there is a method is_primitive which uses three distinct (and documented!) semantics:

• An irreducible polynomial of degree m over F_p is primitive if its roots generate F_p^m;
• A polynomial over a ring is primitive if its coefficients generate the unit ideal;
• Primitivity is undefined for polynomials over an infinite field, that is an exception is raised.

I guess that there should not be any opposition for content_ideal to return the unit ideal. For content, I see three possibilities (there may be more):

• Raise an exception;
• Return 1 (or more precisely self._parent.one());
• Return gcd(self.coefficients()) (knowing that gcd(2/3,4/5)=2/15 with the current semantics for gcd.
  And I would say that in all three cases, primitive_part should return self divided by its content, using for content the same semantic as above. Finally, the case of is_primitive is complicated because of the semantic for finite fields. One possibility could be to find another name for this semantic for finite fields but 1. I guess that "primitive" is really the word used in mathematics for this property, and 2. this may break some existing code (and given the current discussions on sage-devel, I doubt the community would favor this!).

P.S.: I really would like that we reach some consensus on the semantics before including any code in order to limit as much as possible future backward incompatible changes!

[kedlaya]

comment:7

It generally is best for the development workflow if individual tickets are as limited as possible. So I would vote in favor of creating a second ticket to deal with is_primitive and primitive_part after the status of content is resolved.

Regarding primitive, both uses seem to be quite entrenched in the mathematical literature, and so I think we are obliged to maintain the dichotomy.

[bgrenet]

Changed keywords from none to polynomial, content

[bgrenet]

Commit: 78d45b9

[bgrenet]

Branch: u/bruno/content

[bgrenet]

Changed author from Vincent Delecroix to Bruno Grenet

[bgrenet]

comment:8

Based on answers on this ticket and on sage-devel, I've implemented the solution with two methods content and content_ideal. Right now, there is now warning nor deprecation. If necessary, I can add a warning for the generic method content as follows:

from sage.warnings import warn
warn("This method now returns the gcd of the coefficients of the input polynomial. Use content_ideal()` to get the ideal generated by the coefficients.")

[saraedum]

comment:9

The changes look fine to me.
It is my understanding that we should deprecate, i.e., content() should say content() is not going to return an ideal but an element in the future. Use content_ideal() instead.

What do you think?

[saraedum]

Reviewer: Julian Rüth

[bgrenet]

comment:11

Replying to @saraedum:

The changes look fine to me.
It is my understanding that we should deprecate, i.e., content() should say content() is not going to return an ideal but an element in the future. Use content_ideal() instead.

Do you mean that right now, content() should still return an ideal but be deprecated, and that it should only later (in one year from now) return the gcd of the coefficients? What about changing the behavior right now, but with a warning? Another idea (to combine both in some sense) is the following:

• Make content() still return an ideal, with deprecation;
• Add right now a flag ideal=True to the method, so that people can already use the "new behavior" in their codes, using content(ideal=False);
• In one year: remove deprecation and make the default value of ideal to False, or even remove completely the ideal=... parameter, or make it useless.

What do you think?

[saraedum]

comment:12

Replying to @bgrenet:

Replying to @saraedum:

The changes look fine to me.
It is my understanding that we should deprecate, i.e., content() should say content() is not going to return an ideal but an element in the future. Use content_ideal() instead.

Do you mean that right now, content() should still return an ideal but be deprecated, and that it should only later (in one year from now) return the gcd of the coefficients?

Yes.

What about changing the behavior right now, but with a warning?

That would certainly break existing code. It points you to the place where you have to fix it so it would be fine with me. I am not sure what our policy is here.

Another idea (to combine both in some sense) is the following:

• Make content() still return an ideal, with deprecation;
• Add right now a flag ideal=True to the method, so that people can already use the "new behavior" in their codes, using content(ideal=False);
• In one year: remove deprecation and make the default value of ideal to False, or even remove completely the ideal=... parameter, or make it useless.

If we go for this we should remove that parameter completely after some time. I am also fine with this approach but I find it a bit weird to do deprecation by introducing something deprecated (the ideal parameter).

What do you think?

I think the first option (do not change content() at first but print a warning) is the cleanest option.

[sagetrac-git]

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

57077e5

16613: Deprecate content

[sagetrac-git]

Changed commit from 78d45b9 to 57077e5

[sagetrac-git]

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

618a016

16613: doctest fix

[fchapoton]

comment:26

failing doctests, see patchbot reports

[sagetrac-git]

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

953e5ae

16613: Fix doctest due to bad merge

[sagetrac-git]

Changed commit from 61d122a to 953e5ae

[bgrenet]

comment:28

Should be OK now (I'll watch the patchbot logs), I made a mistake during the merge.

[sagetrac-git]

Changed commit from 953e5ae to 84fbcf3

[sagetrac-git]

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

84fbcf3

19171: Doctest fix after merge

[saraedum]

comment:30

The implementation looks good to me.

What is the deprecation strategy now? Do we want this to go in and have a followup ticket (to be merged in a year) to have content return an element? If so, there should be such a ticket and a comment in the code.

Or do we want to change this without deprecation? We missed the 8.0 window, so I am slightly in favor of the two step change.

[saraedum]

Work Issues: followup ticket mentioned in source code

[saraedum]

Changed work issues from followup ticket mentioned in source code to followup ticket mentioned in source code, update ticket summary

[slel]

comment:32

In the docstring of content_ideal, it would be nice to include a hint such as:

When the base ring is a gcd ring, the content as a ring element
is the generator of the content ideal: f.content_ideal().gen()

with an example.

[sagetrac-git]

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

6453fc4	Merge branch 'u/bruno/content' of git://trac.sagemath.org/sage into t/16613/content
017adb6	16613: Add content_ideal().gen() example

[sagetrac-git]

Changed commit from 84fbcf3 to 017adb6

[bgrenet]

comment:34

Replying to @saraedum:

Or do we want to change this without deprecation? We missed the 8.0 window, so I am slightly in favor of the two step change.

I was in favor of a direct change with the argument of "the sooner the better" but the result was endless discussions and the ticket waits for 3 years! So in order for this ridiculously simple issue to be fixed at some point, let's say we implement the two phase change.

Replying to @slel:
Agree, done! Note that I put this comment only for univariate polynomial rings since in the multivariate case, a method content exists (and is linked).

Now needs review (again!).

[tscrim]

comment:35

I think we should just change the behavior (hopefully in an early beta) and put a .. NOTE:: if you do not want to go with the suggestion in comment:19.

[vbraun]

Changed branch from u/bruno/content to 017adb6