Opened 8 years ago

Closed 5 years ago

# fix content of polynomials

Reported by: Owned by: Vincent Delecroix major sage-8.1 commutative algebra polynomial, content Michiel Kosters, David Loeffler Bruno Grenet Julian Rüth N/A followup ticket mentioned in source code, update ticket summary 017adb6 017adb67f3a274526c94b79d3d8683723dc14e80

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.

### comment:1 Changed 8 years ago by For batch modifications

Milestone: sage-6.3 → sage-6.4

### comment:2 Changed 7 years ago by Bruno Grenet

Cc: Michiel Kosters David Loeffler added new → needs_info

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.

### comment:3 Changed 7 years ago by Bruno Grenet

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.

### comment:4 follow-up:  5 Changed 7 years ago by Kiran 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.

### comment:5 in reply to:  4 Changed 7 years ago by Bruno Grenet

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.

### comment:6 follow-up:  7 Changed 7 years ago by Bruno Grenet

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?
1. 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 Fp is primitive if its roots generate Fpm;
• 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!

Last edited 7 years ago by Bruno Grenet (previous) (diff)

### comment:7 in reply to:  6 Changed 7 years ago by Kiran Kedlaya

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.

### comment:8 Changed 7 years ago by Bruno Grenet

Authors: Vincent Delecroix → Bruno Grenet → u/bruno/content → 78d45b9b13fcf242d0f7de248a9891f6a64298a6 modified (diff) polynomial content added needs_info → needs_review

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.")
```

### comment:9 follow-up:  11 Changed 6 years ago by Julian Rüth

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?

### comment:10 Changed 6 years ago by Julian Rüth

Reviewers: → Julian Rüth needs_review → needs_info

### comment:11 in reply to:  9 ; follow-up:  12 Changed 6 years ago by Bruno Grenet

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?

### comment:12 in reply to:  11 Changed 6 years ago by Julian Rüth

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.

### comment:13 Changed 6 years ago by git

Commit: 78d45b9b13fcf242d0f7de248a9891f6a64298a6 → 57077e53525ae33a8b10c77df307b89709f42c43

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

 ​57077e5 `16613: Deprecate content`

### comment:14 Changed 6 years ago by git

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

 ​618a016 `16613: doctest fix`

### comment:15 Changed 6 years ago by Bruno Grenet

Status: needs_info → needs_review

Ok, I've deprecated `content` when it existed and returned an ideal, and we'll perform the complete switch later on.

### comment:16 Changed 6 years ago by Julian Rüth

Status: needs_review → needs_info

Does `SEEALSO: :meth:content` still make sense?

### comment:17 Changed 6 years ago by git

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

 ​cb9bbe6 `Merge branch 'u/bruno/content' of git://trac.sagemath.org/sage into t/16613/content` ​78415d7 `Remove unwanted SEEALSO (+ remove trailing spaces)`

### comment:18 Changed 6 years ago by Bruno Grenet

Status: needs_info → needs_review

Removed irrelevant SEEALSO.

### comment:19 Changed 6 years ago by Travis Scrimshaw

Milestone: sage-6.4 → sage-7.6

My 2 cents: I don't like the deprecation of `content` then only to replace it by something that has different functionality. I am close to considering this a bug, and as such, we do not need to deprecate. So the idea of using a temporary flag, which we then deprecate after we remove the ability to return an ideal from `content`, is the best way forward IMO. It's two steps, but it is the most consistent with Sage's policies.

### comment:20 Changed 5 years ago by git

Commit: 78415d78151d2b7632c98cd41b681c4501275faa → 00127fdfb079b324f140cf01c354914acf98b865

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

 ​16681f3 `Merge branch 'develop' into 16613_content` ​00127fd `Merge branch 'u/bruno/content' of git://trac.sagemath.org/sage into 16613_content`

### comment:21 Changed 5 years ago by Bruno Grenet

I've merged `develop` (8.0.beta11) into this ticket's branch since it did not apply.

Now I agree with Travis that the deprecation is a bit a pity. It will force users to make two changes instead of one when they need the content (as a value rather than an ideal): Now they write `p.content().gen()`, they need to change to `p.content_ideal().gen()` due to the current deprecation warning, and in some months (years?) they'll finally be able to write `p.content()` to avoid the useless construction of the ideal. I'm strongly in favor of having a way for users to directly use the new semantic.

As such, I would go for making `content` return a value without any deprecation. If the there's enough time left, this backward incompatible change may occur with the new release 8.0.

### comment:22 Changed 5 years ago by Frédéric Chapoton

Status: needs_review → needs_work

does not apply

### comment:23 Changed 5 years ago by git

Commit: 00127fdfb079b324f140cf01c354914acf98b865 → 61d122a792a764472bbbc52b8562b4a616a51d8a

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

 ​61d122a `Merge branch 'develop' into 16613_content`

Applies again!

### comment:25 Changed 5 years ago by Bruno Grenet

Status: needs_work → needs_review

### comment:26 Changed 5 years ago by Frédéric Chapoton

failing doctests, see patchbot reports

### comment:27 Changed 5 years ago by git

Commit: 61d122a792a764472bbbc52b8562b4a616a51d8a → 953e5aea98a4a0f5f6095b192607307669dfa8b1

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

 ​953e5ae `16613: Fix doctest due to bad merge`

### comment:28 Changed 5 years ago by Bruno Grenet

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

### comment:29 Changed 5 years ago by git

Commit: 953e5aea98a4a0f5f6095b192607307669dfa8b1 → 84fbcf39cfab762038d64105408f863e7e1efd2b

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

 ​84fbcf3 `19171: Doctest fix after merge`

### comment:30 follow-up:  34 Changed 5 years ago by Julian Rüth

Status: needs_review → needs_info → followup ticket mentioned in source code

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.

### comment:31 Changed 5 years ago by Julian Rüth

Work issues: followup ticket mentioned in source code → followup ticket mentioned in source code, update ticket summary

### comment:32 Changed 5 years ago by Samuel Lelièvre

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.

### comment:33 Changed 5 years ago by 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`

### comment:34 in reply to:  30 Changed 5 years ago by Bruno Grenet

Description: modified (diff) sage-7.6 → sage-8.1 needs_info → needs_review

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 slelievre: 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!).

### comment:35 Changed 5 years ago by Travis Scrimshaw

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.

### comment:36 Changed 5 years ago by Julian Rüth

Status: needs_review → positive_review

### comment:37 Changed 5 years ago by Volker Braun

Branch: u/bruno/content → 017adb67f3a274526c94b79d3d8683723dc14e80 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.