Opened 5 years ago
Closed 4 years ago
#22983 closed defect (fixed)
polynomial quotient rings are unique parents
Reported by:  Julian Rüth  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  commutative algebra  Keywords:  sd86.5, sd87 
Cc:  Merged in:  
Authors:  Julian Rüth  Reviewers:  David Roe 
Report Upstream:  N/A  Work issues:  
Branch:  966c36b (Commits, GitHub, GitLab)  Commit:  966c36b92266ffbaadec4bd43e0f08f086eb5fd3 
Dependencies:  #23851  Stopgaps: 
Description (last modified by )
Currently quotient rings are not unique parents which sometimes causes trouble with
sage: R.<x> = QQ[] sage: R.quo(x) is R.quo(x) False sage: R.quo(x) == R.quo(x) True
The changes proposed here make the creation go through a factory which makes sure that the parents are unique.
Change History (39)
comment:1 Changed 5 years ago by
Description:  modified (diff) 

comment:2 Changed 5 years ago by
Branch:  → u/saraedum/polynomial_quotient_rings_are_unique_parents 

comment:3 Changed 5 years ago by
Commit:  → 054945da4a2caea28416c684d236fce4cbe88124 

comment:4 Changed 5 years ago by
nbruin: You are right. It should be documented. I'll fix that.
I believe that your example should produce two different rings (at least for the time being.) These could be ==
equal but not is
equal. However, getting ==
to work for them would require a change of the hash function which is (hard and) not the scope of this ticket.
comment:5 followup: 6 Changed 5 years ago by
Current R.quo(x1)
and R.quo(2*x2)
prints in the same way.
sage: R.<x>= QQ[] sage: R.quo(x+1) Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x + 1 sage: R.quo(2*x+2) Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x + 1
So I would say rather that the two constructions should return the same ring; it should be easy, it suffices to make the defining polynomial monic because creating the key.
comment:6 Changed 5 years ago by
Replying to caruso:
Currently
R.quo(x1)
andR.quo(2*x2)
prints in the same way.sage: R.<x>= QQ[] sage: R.quo(x+1) Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x + 1 sage: R.quo(2*x+2) Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x + 1So I would say rather that the two constructions should return the same ring; it should be easy, it suffices to make the defining polynomial monic because creating the key.
I agree. However, this is already happening automagically: quo
creates a (principal) ideal and takes its generator as the modulus which is the same x+1
in both of your examples.
At the same time, if someone insists to create a quotient with the modulus x + 1
and one with the modulus 2*x + 2
by calling PolynomialQuotientRing
directly, then these should be distinct because .modulus()
is going to have a different value for the two, i.e., they are distinguishable. I'll add a doctest to clarify this.
comment:7 Changed 5 years ago by
Commit:  054945da4a2caea28416c684d236fce4cbe88124 → f6a1cd8a84d48f4c043b770d2f437701eb8e3089 

Branch pushed to git repo; I updated commit sha1. New commits:
f6a1cd8  Document normalization of modulus

comment:8 Changed 5 years ago by
Status:  new → needs_review 

comment:9 Changed 5 years ago by
Doctests in rings/polynomial
pass for me. Let's see what the patchbot thinks about everything else.
comment:10 Changed 5 years ago by
Ok.
It's a bit weird and confusing that the function PolynomialQuotientRing
does not have the same behaviour than the method quo
(and even QuotientRing
), isn't it?
sage: R.<x> = QQ[] sage: QuotientRing(R, 2*x+2) Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus x + 1 sage: PolynomialQuotientRing(R, 2*x+2) Univariate Quotient Polynomial Ring in xbar over Rational Field with modulus 2*x + 2
I would be in favour of uniformizing this... but it's definitely for another ticket.
I'll try to review your ticket soon.
comment:11 followup: 12 Changed 5 years ago by
Why did you remove "in one variable" in the doctest.
sage: R.<x,y> = QQ[] sage: PolynomialQuotientRing(R, x^2+y+1) ... TypeError: ring must be a polynomial ring
comment:12 Changed 5 years ago by
Replying to caruso:
Why did you remove "in one variable" in the doctest.
sage: R.<x,y> = QQ[] sage: PolynomialQuotientRing(R, x^2+y+1) ... TypeError: ring must be a polynomial ring
Because it already says "univariate" there.
comment:13 Changed 5 years ago by
Keywords:  sd86.5 added 

comment:14 Changed 5 years ago by
Reviewers:  → David Roe 

Status:  needs_review → positive_review 
Tests all pass for me, and it looks good.
comment:16 Changed 5 years ago by
Replying to vbraun:
Merge conflict
For me, trac is showing it as still merging cleanly. Is there a new beta against which the merge is failing, or a ticket?
comment:17 Changed 5 years ago by
Status:  needs_work → positive_review 

We do not get a merge conflict for that one.
comment:19 Changed 5 years ago by
Commit:  f6a1cd8a84d48f4c043b770d2f437701eb8e3089 → 19af05916a1eb3f1fc89ba430b45afb23592dc8e 

Branch pushed to git repo; I updated commit sha1. New commits:
19af059  Merge branch 'develop' into t/22983/polynomial_quotient_rings_are_unique_parents

comment:20 Changed 5 years ago by
Status:  needs_work → positive_review 

Still no conflicts. What are we doing wrong?
comment:21 Changed 5 years ago by
Status:  positive_review → needs_work 

Random failures on some of the build bots:
sage t long src/sage/rings/polynomial/polynomial_quotient_ring.py ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1355, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units Failed example: L.S_units([]) Expected: [(1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] Got: [(1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1359, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units Failed example: L.S_units([K.ideal(1/2*a  3/2)]) Expected: [((1/6*a  1/2)*b^2 + (1/3*a  1)*b + 4/3*a, +Infinity), (1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] Got: [((1/6*a  1/2)*b^2 + (1/3*a  1)*b + 4/3*a, +Infinity), (1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1364, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units Failed example: L.S_units([K.ideal(2)]) Expected: [((1/2*a  1/2)*b^2 + (a + 1)*b + 3, +Infinity), ((1/6*a + 1/2)*b^2 + (1/3*a + 1)*b  5/6*a + 1/2, +Infinity), ((1/6*a + 1/2)*b^2 + (1/3*a + 1)*b  5/6*a  1/2, +Infinity), (1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] Got: [((1/2*a  1/2)*b^2 + (a + 1)*b + 3, +Infinity), ((1/6*a + 1/2)*b^2 + (1/3*a + 1)*b  5/6*a + 1/2, +Infinity), ((1/6*a + 1/2)*b^2 + (1/3*a + 1)*b  5/6*a  1/2, +Infinity), (1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1445, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units Failed example: L.units() Expected: [(1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] Got: [(1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] ********************************************************************** 2 items had failures: 3 of 18 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units 1 of 23 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units [385 tests, 4 failures, 1.59 s]
comment:22 Changed 5 years ago by
Commit:  19af05916a1eb3f1fc89ba430b45afb23592dc8e → b04e7e9f5067b001f1d58ca72c0724ebfd7df715 

Branch pushed to git repo; I updated commit sha1. New commits:
b04e7e9  Merge branch 'develop' into t/22983/polynomial_quotient_rings_are_unique_parents

comment:23 Changed 5 years ago by
Keywords:  sd87 added 

comment:24 Changed 5 years ago by
Commit:  b04e7e9f5067b001f1d58ca72c0724ebfd7df715 → 272e7e310373cb911d9c78cef5ab622bf37d073d 

Branch pushed to git repo; I updated commit sha1. New commits:
272e7e3  Merge remotetracking branch 'origin/develop' into HEAD

comment:25 Changed 5 years ago by
Commit:  272e7e310373cb911d9c78cef5ab622bf37d073d → 806d5afe806f90f2dc21e08fbee02c7640142b41 

Branch pushed to git repo; I updated commit sha1. New commits:
806d5af  Pickling now works

comment:26 Changed 5 years ago by
Status:  needs_work → needs_review 

Let's see what the patchbots think now. I expect some of the S_units
tests to disagree. I don't understand why they are not stable as I don't see anything happening in the implementation that would be random after my changes.
comment:27 Changed 5 years ago by
Status:  needs_review → needs_work 

Some S_units
fail. Let's make the tests less strict and add a _test_S_units
instead.
comment:28 Changed 5 years ago by
Commit:  806d5afe806f90f2dc21e08fbee02c7640142b41 → 820b0a2c47f66cc5fdf6466ef378f5e18c89d6b0 

comment:29 Changed 5 years ago by
Status:  needs_work → needs_review 

I thought for a while that the behaviour of these doctests was random. Actually it is not. It is consistent over all patchbot runs with the same base version of Sage. Caching the polynomial rings flips some signs, I am not sure why. Anyway, the result is still correct and it is not random, so there is no need for a
_test_S_units()
which would be hard to write anyway.
comment:30 Changed 5 years ago by
Commit:  820b0a2c47f66cc5fdf6466ef378f5e18c89d6b0 → 4660c1865961462098d01470773ca1ac95a96d4c 

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

comment:32 Changed 4 years ago by
Milestone:  sage8.0 → sage8.3 

comment:33 Changed 4 years ago by
Status:  positive_review → needs_work 

I still get failing tests. Random failures during high load. It looks like the tests depend on whether a garbage collection is forced due to low memory.
File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1445, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units Failed example: L.S_units([]) Expected: [(1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] Got: [(1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1449, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units Failed example: L.S_units([K.ideal(1/2*a  3/2)]) Expected: [((1/6*a  1/2)*b^2 + (1/3*a  1)*b + 4/3*a, +Infinity), (1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] Got: [((1/6*a  1/2)*b^2 + (1/3*a  1)*b + 4/3*a, +Infinity), (1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1454, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units Failed example: L.S_units([K.ideal(2)]) Expected: [((1/2*a  1/2)*b^2 + (a + 1)*b + 3, +Infinity), ((1/6*a + 1/2)*b^2 + (1/3*a + 1)*b  5/6*a + 1/2, +Infinity), ((1/6*a + 1/2)*b^2 + (1/3*a + 1)*b  5/6*a  1/2, +Infinity), (1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] Got: [((1/2*a  1/2)*b^2 + (a + 1)*b + 3, +Infinity), ((1/6*a + 1/2)*b^2 + (1/3*a + 1)*b  5/6*a + 1/2, +Infinity), ((1/6*a + 1/2)*b^2 + (1/3*a + 1)*b  5/6*a  1/2, +Infinity), (1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1535, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units Failed example: L.units() Expected: [(1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] Got: [(1/2*a + 1/2, 6), ((1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, +Infinity), (2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2, +Infinity)] ********************************************************************** File "src/sage/rings/polynomial/polynomial_quotient_ring.py", line 1544, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units Failed example: L.unit_group().gens_values() Expected: [1/2*a + 1/2, (1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, 2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2] Got: [1/2*a + 1/2, (1/3*a  1)*b^2  4/3*a*b  5/6*a + 7/2, 2/3*a*b^2 + (2/3*a  2)*b  5/6*a  7/2] ********************************************************************** 2 items had failures: 3 of 18 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.S_units 2 of 23 in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic.units [451 tests, 5 failures, 2.92 s]  sage t long src/sage/rings/polynomial/polynomial_quotient_ring.py # 5 doctests failed 
comment:34 Changed 4 years ago by
Branch:  u/saraedum/polynomial_quotient_rings_are_unique_parents 

Commit:  4660c1865961462098d01470773ca1ac95a96d4c 
comment:35 Changed 4 years ago by
Branch:  → u/saraedum/22983 

comment:36 Changed 4 years ago by
Commit:  → 966c36b92266ffbaadec4bd43e0f08f086eb5fd3 

Branch pushed to git repo; I updated commit sha1. New commits:
966c36b  Merge develop and 22983

comment:37 Changed 4 years ago by
Not the first time, something like this has happened: https://trac.sagemath.org/ticket/23851#comment:5
New commits:
054945d  Make polynomial quotient rings unique parents

f6a1cd8  Document normalization of modulus

19af059  Merge branch 'develop' into t/22983/polynomial_quotient_rings_are_unique_parents

b04e7e9  Merge branch 'develop' into t/22983/polynomial_quotient_rings_are_unique_parents

272e7e3  Merge remotetracking branch 'origin/develop' into HEAD

806d5af  Pickling now works

f1f2fa5  Merge remotetracking branch 'trac/u/saraedum/polynomial_quotient_rings_are_unique_parents' into trac22983

4660c18  Fix doctests

697d02e  Merge remotetracking branch 'trac/u/saraedum/polynomial_quotient_rings_are_unique_parents' into HEAD

966c36b  Merge develop and 22983

comment:38 Changed 4 years ago by
Dependencies:  → #23851 

Status:  needs_work → positive_review 
The issue has been fixed in #23851. Since I did not change anything, I am setting this back to positive review.
comment:39 Changed 4 years ago by
Branch:  u/saraedum/22983 → 966c36b92266ffbaadec4bd43e0f08f086eb5fd3 

Resolution:  → fixed 
Status:  positive_review → closed 
Does this fully solve the problem, though? One could give different generators for the same ideal. Should we be getting identical results for those, e.g.,
R.quo(x1)
andR.quo(2*x2)
(provided2
is invertible inR
...). It might be worth documenting the choice made.I suspect that for higher rank polynomial rings, normalizing the ideal representation might be too expensive (although computing in those rings would be expensive anyway).
New commits:
Make polynomial quotient rings unique parents