Sage: Ticket #23621: Fix quotients of univariate polynomial rings over ZZ
https://trac.sagemath.org/ticket/23621
<p>
The quotient of <code>ZZ[x]</code> by the ideal <code>(x, 2)</code>
works fine using a multivariate polynomial ring:
</p>
<pre class="wiki">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]]
</pre><p>
but it fails using a univariate polynomial ring,
returning mathematically wrong answers:
</p>
<pre class="wiki">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]]
</pre><p>
Expected:
</p>
<pre class="wiki">[[True, True, True], [True, True, True], [True, True, True]]
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/23621
Trac 1.1.6roedFri, 18 Aug 2017 02:34:31 GMT
https://trac.sagemath.org/ticket/23621#comment:1
https://trac.sagemath.org/ticket/23621#comment:1
<p>
The problem is that <code>I</code> is just a generic ideal and doesn't implement a <code>reduce</code> method.
</p>
TicketroedFri, 18 Aug 2017 02:37:50 GMT
https://trac.sagemath.org/ticket/23621#comment:2
https://trac.sagemath.org/ticket/23621#comment:2
<p>
To solve this, I think one needs to implement a new class for ideals in <code>ZZ['x']</code> and set <code>_ideal_class_</code> appropriately on <code>R</code>. Of course, one can argue that the default behavior of the <code>reduce</code> method on a generic ideal should be to raise an error rather than just return the input unchanged.
</p>
TicketmderickxThu, 31 Aug 2017 08:18:31 GMT
https://trac.sagemath.org/ticket/23621#comment:3
https://trac.sagemath.org/ticket/23621#comment:3
<p>
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 <code>sage/rings/quotient_ring.py</code>.
</p>
<pre class="wiki">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
</pre><p>
And I think that this is a logic requirement to put on the reduce method.
</p>
TicketmderickxThu, 31 Aug 2017 08:34:09 GMT
https://trac.sagemath.org/ticket/23621#comment:4
https://trac.sagemath.org/ticket/23621#comment:4
<p>
Ok there are quite a few doctest failures. If I just make it raise an error. Ironically the first failure is
</p>
<pre class="wiki">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
</pre><p>
which was added to test that <a class="closed ticket" href="https://trac.sagemath.org/ticket/11068" title="enhancement: Basic implementation of one- and twosided ideals of non-commutative ... (closed: fixed)">#11068</a> is fixed, the ticket where the above text about "The only requirement is that the two-sided ideal I..." comes from.
</p>
TicketmderickxThu, 31 Aug 2017 08:42:53 GMT
https://trac.sagemath.org/ticket/23621#comment:5
https://trac.sagemath.org/ticket/23621#comment:5
<p>
The second failure points at <a class="new ticket" href="https://trac.sagemath.org/ticket/13999" title="defect: Ideal membership for univariate polynomial (new)">#13999</a> of which this ticket basically is a dupe.
</p>
TicketmderickxThu, 31 Aug 2017 08:59:47 GMT
https://trac.sagemath.org/ticket/23621#comment:6
https://trac.sagemath.org/ticket/23621#comment:6
<p>
All failures will probably be fixed if these three tests pass
</p>
<pre class="wiki">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]
</pre><pre class="wiki">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'])
</pre><pre class="wiki">sage: S = SteenrodAlgebra(2)
sage: I = S*[S.0+S.1]*S
sage: Q = S.quo(I)
sage: Q.0
Sq(1)
</pre><p>
I consider all three of them bugs, so this strengthens my believe that it is better to raise a <a class="missing wiki">NotImplementedError?</a>.
</p>
TicketmderickxSat, 02 Sep 2017 04:07:49 GMT
https://trac.sagemath.org/ticket/23621#comment:7
https://trac.sagemath.org/ticket/23621#comment:7
<p>
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.
</p>
TicketmderickxMon, 06 Dec 2021 17:13:56 GMTdescription changed
https://trac.sagemath.org/ticket/23621#comment:8
https://trac.sagemath.org/ticket/23621#comment:8
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/23621?action=diff&version=8">diff</a>)
</li>
</ul>
TicketslelievreTue, 07 Dec 2021 16:03:20 GMTsummary, description, milestone changed; cc, keywords set
https://trac.sagemath.org/ticket/23621#comment:9
https://trac.sagemath.org/ticket/23621#comment:9
<ul>
<li><strong>cc</strong>
<em>slelievre</em> added
</li>
<li><strong>keywords</strong>
<em>ideal</em> added
</li>
<li><strong>summary</strong>
changed from <em>Quotients of univariate polynomial rings over ZZ return mathematical incorrect answers</em> to <em>Fix quotients of univariate polynomial rings over ZZ</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/23621?action=diff&version=9">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-8.1</em> to <em>sage-9.5</em>
</li>
</ul>
TicketmkoeppeMon, 10 Jan 2022 00:37:38 GMTmilestone changed
https://trac.sagemath.org/ticket/23621#comment:10
https://trac.sagemath.org/ticket/23621#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>sage-9.5</em> to <em>sage-9.6</em>
</li>
</ul>
TicketmkoeppeTue, 03 May 2022 15:17:06 GMTmilestone changed
https://trac.sagemath.org/ticket/23621#comment:11
https://trac.sagemath.org/ticket/23621#comment:11
<ul>
<li><strong>milestone</strong>
changed from <em>sage-9.6</em> to <em>sage-9.7</em>
</li>
</ul>
Ticket