Fix quotients of univariate polynomial rings over ZZ

[koffie]

The quotient of ZZ[x] by the ideal (x, 2) works fine using a multivariate polynomial ring:

sage: R.<x> = PolynomialRing(ZZ, 1)
sage: I = R.ideal([x, 2])
sage: I
Ideal (x, 2) of Multivariate Polynomial Ring in x over Integer Ring
sage: S = R.quo(I)
sage: [[S(a) == S(b) for b in (0, 2, x)] for a in (0, 2, x)]
[[True, True, True], [True, True, True], [True, True, True]]

but it fails using a univariate polynomial ring, returning mathematically wrong answers:

sage: R.<x> = ZZ[]
sage: I = R.ideal([x, 2])
sage: I
Ideal (x, 2) of Univariate Polynomial Ring in x over Integer Ring
sage: S = R.quo(I)
sage: 
sage: [[S(a) == S(b) for b in (0, 2, x)] for a in (0, 2, x)]
[[True, False, False], [False, True, False], [False, False, True]]

Expected:

[[True, True, True], [True, True, True], [True, True, True]]

CC: @slel

Component: commutative algebra

Keywords: ideal

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

[roed314]

comment:1

The problem is that I is just a generic ideal and doesn't implement a reduce method.

[roed314]

comment:2

To solve this, I think one needs to implement a new class for ideals in ZZ['x'] and set _ideal_class_ appropriately on R. Of course, one can argue that the default behavior of the reduce method on a generic ideal should be to raise an error rather than just return the input unchanged.

[koffie]

comment:3

Yeah I totally agree that it should raise an error, because this implementation does not satisfy the assumption on reduce in other parts of the code. For example this is an excerpt from sage/rings/quotient_ring.py.

The only requirement is that the two-sided ideal `I`
provides a ``reduce`` method so that ``I.reduce(x)`` is the normal
form of an element `x` with respect to `I` (i.e., we have
``I.reduce(x) == I.reduce(y)`` if `x-y \in I`, and
``x - I.reduce(x) in I``). H

And I think that this is a logic requirement to put on the reduce method.

[koffie]

comment:4

Ok there are quite a few doctest failures. If I just make it raise an error. Ironically the first failure is

sage: sage: MS = MatrixSpace(GF(5),2,2)
....: sage: I = MS*[MS.0*MS.1,MS.2+MS.3]*MS
....: sage: Q = MS.quo(I)
....: sage: Q.0*Q.1   # indirect doctest
....: 
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...
NotImplementedError: reduce not implemented for Twosided Ideal 
(
  [0 1]
  [0 0],

  [0 0]
  [1 1]
)
 of Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 5

which was added to test that #11068 is fixed, the ticket where the above text about "The only requirement is that the two-sided ideal I..." comes from.

[koffie]

comment:5

The second failure points at #13999 of which this ticket basically is a dupe.

[koffie]

comment:6

All failures will probably be fixed if these three tests pass

sage: MS = MatrixSpace(GF(5),2,2)
sage: I = MS*[MS.0*MS.1,MS.2+MS.3]*MS
sage: Q = MS.quo(I)
sage: Q.0*Q.1   # indirect doctest
[0 1]
[0 0]

sage: R.<x> = PolynomialRing(ZZ)
sage: I = R.ideal([4 + 3*x + x^2, 1 + x^2])
sage: S = R.quotient_ring(I);
sage: TestSuite(S).run(skip=['_test_nonzero_equal', '_test_elements', '_test_zero'])

sage: S = SteenrodAlgebra(2)
sage: I = S*[S.0+S.1]*S
sage: Q = S.quo(I)
sage: Q.0
Sq(1)

I consider all three of them bugs, so this strengthens my believe that it is better to raise a NotImplementedError.

[koffie]

comment:7

I think that all the matrix space examples will not give any interesting doctest, since matrix rings over fields are simple and hence there are no two sided ideals. Although this means that the reduce function is very easy to implement! I don't know enough about Steenrod algebra's in order to create a meaningful reduce method.

[koffie]

Description changed:

--- 
+++ 
@@ -2,10 +2,7 @@

sage: R. = ZZ[] sage: I = R.ideal([x,2]); I -Ideal (x, 2) of Univariate Polynomial Ring in x over Integer Ring sage: S = R.quo(I) -sage: S(x) -xbar sage: S(x)==S(0) False sage: S(2)==S(2)

[slel]

Description changed:

--- 
+++ 
@@ -1,25 +1,31 @@
+The quotient of `ZZ[x]` by the ideal `(x, 2)`
+works fine using a multivariate polynomial ring:
+
+```
+sage: R.<x> = PolynomialRing(ZZ, 1)
+sage: I = R.ideal([x, 2])
+sage: I
+Ideal (x, 2) of Multivariate Polynomial Ring in x over Integer Ring
+sage: S = R.quo(I)
+sage: [[S(a) == S(b) for b in (0, 2, x)] for a in (0, 2, x)]
+[[True, True, True], [True, True, True], [True, True, True]]
+```
+but it fails using a univariate polynomial ring,
+returning mathematically wrong answers:

sage: R. = ZZ[] -sage: I = R.ideal([x,2]); I +sage: I = R.ideal([x, 2]) +sage: I +Ideal (x, 2) of Univariate Polynomial Ring in x over Integer Ring sage: S = R.quo(I) -sage: S(x)==S(0) -False -sage: S(2)==S(2) -True -sage: S(2)==S(0) -False +sage: +sage: [[S(a) == S(b) for b in (0, 2, x)] for a in (0, 2, x)] +[[True, False, False], [False, True, False], [False, False, True]] + +Expected: + + +[[True, True, True], [True, True, True], [True, True, True]]

-Note that if you create the quotient as a multivariate polynomial ring, then it works fine!
-
-```
-sage: R.<x> = PolynomialRing(ZZ,1)
-sage: I = R.ideal([x,2]); I
-Ideal (x, 2) of Multivariate Polynomial Ring in x over Integer Ring
-sage: S = R.quo(I)
-sage: S(x)==0
-True
-sage: S(2)==0
-True
-```

[slel]

Changed keywords from none to ideal