Opened 5 years ago

Last modified 2 weeks ago

#23621 new defect

Fix quotients of univariate polynomial rings over ZZ

Reported by: Maarten Derickx Owned by:
Priority: critical Milestone: sage-9.8
Component: commutative algebra Keywords: ideal
Cc: Samuel Lelièvre Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Samuel Lelièvre)

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]]

Change History (12)

comment:1 Changed 5 years ago by David Roe

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

comment:2 Changed 5 years ago by David Roe

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.

comment:3 Changed 5 years ago by Maarten Derickx

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.

Last edited 5 years ago by Maarten Derickx (previous) (diff)

comment:4 Changed 5 years ago by Maarten Derickx

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.

Last edited 5 years ago by Maarten Derickx (previous) (diff)

comment:5 Changed 5 years ago by Maarten Derickx

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

comment:6 Changed 5 years ago by Maarten Derickx

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?.

comment:7 Changed 5 years ago by Maarten Derickx

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.

comment:8 Changed 10 months ago by Maarten Derickx

Description: modified (diff)

comment:9 Changed 10 months ago by Samuel Lelièvre

Cc: Samuel Lelièvre added
Description: modified (diff)
Keywords: ideal added
Milestone: sage-8.1sage-9.5
Summary: Quotients of univariate polynomial rings over ZZ return mathematical incorrect answersFix quotients of univariate polynomial rings over ZZ

comment:10 Changed 9 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:11 Changed 5 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:12 Changed 2 weeks ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.