Opened 5 years ago

Closed 4 years ago

# polynomial quotient rings are unique parents

Reported by: Owned by: saraedum major sage-8.3 commutative algebra sd86.5, sd87 Julian Rüth David Roe N/A 966c36b 966c36b92266ffbaadec4bd43e0f08f086eb5fd3 #23851

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.

### comment:1 Changed 5 years ago by caruso

• Description modified (diff)

### comment:2 Changed 5 years ago by saraedum

• Branch set to u/saraedum/polynomial_quotient_rings_are_unique_parents

### comment:3 Changed 5 years ago by nbruin

• Commit set to 054945da4a2caea28416c684d236fce4cbe88124

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(x-1)` and `R.quo(2*x-2)` (provided `2` is invertible in `R` ...). 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:

 ​054945d `Make polynomial quotient rings unique parents`

### comment:4 Changed 5 years ago by saraedum

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 follow-up: ↓ 6 Changed 5 years ago by caruso

Currently `R.quo(x-1)` and `R.quo(2*x-2)` 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.

Last edited 5 years ago by caruso (previous) (diff)

### comment:6 in reply to: ↑ 5 Changed 5 years ago by saraedum

Currently `R.quo(x-1)` and `R.quo(2*x-2)` 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.

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 git

• Commit changed from 054945da4a2caea28416c684d236fce4cbe88124 to f6a1cd8a84d48f4c043b770d2f437701eb8e3089

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

 ​f6a1cd8 `Document normalization of modulus`

### comment:8 Changed 5 years ago by saraedum

• Status changed from new to needs_review

### comment:9 Changed 5 years ago by saraedum

Doctests in `rings/polynomial` pass for me. Let's see what the patchbot thinks about everything else.

### comment:10 Changed 5 years ago by caruso

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 follow-up: ↓ 12 Changed 5 years ago by 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
```

### comment:12 in reply to: ↑ 11 Changed 5 years ago by saraedum

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:14 Changed 5 years ago by roed

• Reviewers set to David Roe
• Status changed from needs_review to positive_review

Tests all pass for me, and it looks good.

### comment:15 follow-up: ↓ 16 Changed 5 years ago by vbraun

• Status changed from positive_review to needs_work

Merge conflict

### comment:16 in reply to: ↑ 15 Changed 5 years ago by roed

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 saraedum

• Status changed from needs_work to positive_review

We do not get a merge conflict for that one.

### comment:18 Changed 5 years ago by vbraun

• Status changed from positive_review to needs_work

Wait for the next beta

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

• Commit changed from f6a1cd8a84d48f4c043b770d2f437701eb8e3089 to 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 saraedum

• Status changed from needs_work to positive_review

Still no conflicts. What are we doing wrong?

### comment:21 Changed 5 years ago by vbraun

• Status changed from positive_review to 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)]
**********************************************************************
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 git

• Commit changed from 19af05916a1eb3f1fc89ba430b45afb23592dc8e to 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:24 Changed 5 years ago by git

• Commit changed from b04e7e9f5067b001f1d58ca72c0724ebfd7df715 to 272e7e310373cb911d9c78cef5ab622bf37d073d

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

 ​272e7e3 `Merge remote-tracking branch 'origin/develop' into HEAD`

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

• Commit changed from 272e7e310373cb911d9c78cef5ab622bf37d073d to 806d5afe806f90f2dc21e08fbee02c7640142b41

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

 ​806d5af `Pickling now works`

### comment:26 Changed 5 years ago by saraedum

• Status changed from needs_work to 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 saraedum

• Status changed from needs_review to needs_work

Some `S_units` fail. Let's make the tests less strict and add a `_test_S_units` instead.

### comment:28 Changed 4 years ago by git

• Commit changed from 806d5afe806f90f2dc21e08fbee02c7640142b41 to 820b0a2c47f66cc5fdf6466ef378f5e18c89d6b0

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

 ​f1f2fa5 `Merge remote-tracking branch 'trac/u/saraedum/polynomial_quotient_rings_are_unique_parents' into trac-22983` ​820b0a2 `Fix doctests`

### comment:29 Changed 4 years ago by saraedum

• Status changed from needs_work to 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 4 years ago by git

• Commit changed from 820b0a2c47f66cc5fdf6466ef378f5e18c89d6b0 to 4660c1865961462098d01470773ca1ac95a96d4c

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

 ​4660c18 `Fix doctests`

### comment:31 Changed 4 years ago by roed

• Status changed from needs_review to positive_review

Looks good to me.

### comment:32 Changed 4 years ago by chapoton

• Milestone changed from sage-8.0 to sage-8.3

### comment:33 Changed 4 years ago by vbraun

• Status changed from positive_review to 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]
**********************************************************************
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 saraedum

• Branch u/saraedum/polynomial_quotient_rings_are_unique_parents deleted
• Commit 4660c1865961462098d01470773ca1ac95a96d4c deleted

### comment:35 Changed 4 years ago by saraedum

• Branch set to u/saraedum/22983

### comment:36 Changed 4 years ago by git

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

 ​966c36b `Merge develop and 22983`

### comment:37 Changed 4 years ago by saraedum

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 remote-tracking branch 'origin/develop' into HEAD` ​806d5af `Pickling now works` ​f1f2fa5 `Merge remote-tracking branch 'trac/u/saraedum/polynomial_quotient_rings_are_unique_parents' into trac-22983` ​4660c18 `Fix doctests` ​697d02e `Merge remote-tracking branch 'trac/u/saraedum/polynomial_quotient_rings_are_unique_parents' into HEAD` ​966c36b `Merge develop and 22983`

### comment:38 Changed 4 years ago by saraedum

• Dependencies set to #23851
• Status changed from needs_work to 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 vbraun

• Branch changed from u/saraedum/22983 to 966c36b92266ffbaadec4bd43e0f08f086eb5fd3
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.