Opened 5 years ago

Last modified 2 months ago

#23621 new defect

Fix quotients of univariate polynomial rings over ZZ

Reported by: mderickx Owned by:
Priority: critical Milestone: sage-9.7
Component: commutative algebra Keywords: ideal
Cc: slelievre Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by slelievre)

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 (11)

comment:1 Changed 5 years ago by roed

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

comment:2 Changed 5 years ago by roed

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 mderickx

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 mderickx (previous) (diff)

comment:4 Changed 5 years ago by mderickx

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 mderickx (previous) (diff)

comment:5 Changed 5 years ago by mderickx

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

comment:6 Changed 5 years ago by mderickx

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 mderickx

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 7 months ago by mderickx

  • Description modified (diff)

comment:9 Changed 7 months ago by slelievre

  • Cc slelievre added
  • Description modified (diff)
  • Keywords ideal added
  • Milestone changed from sage-8.1 to sage-9.5
  • Summary changed from Quotients of univariate polynomial rings over ZZ return mathematical incorrect answers to Fix quotients of univariate polynomial rings over ZZ

comment:10 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6

comment:11 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.6 to sage-9.7
Note: See TracTickets for help on using tickets.