Sage: Ticket #7711: integral() does not reduce coefficients in finite field
https://trac.sagemath.org/ticket/7711
<p>
Consider the following example:
</p>
<pre class="wiki">sage: P.<x,z> = PolynomialRing(GF(2147483647))
sage: Q.<y> = PolynomialRing(P)
sage: p=x+y+z
sage: p.integral()
1/2*y^2 + (x + z)*y
</pre><p>
Note the leading coefficient 1/2 is not reduced mod 2147483647.
</p>
<p>
For smaller p this seems to work:
</p>
<pre class="wiki">sage: P.<x,z> = PolynomialRing(GF(2147483629))
sage: Q.<y> = PolynomialRing(P)
sage: p=x+y+z
sage: p.integral()
-1073741814*y^2 + (x + z)*y
</pre><p>
It works also when the smaller ring P has only one variable:
</p>
<pre class="wiki">sage: P.<x> = PolynomialRing(GF(2147483647))
sage: Q.<y> = PolynomialRing(P)
sage: p=x+y
sage: p.integral()
1073741824*y^2 + x*y
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7711
Trac 1.1.6wasThu, 24 Dec 2009 07:07:56 GMTmilestone changed
https://trac.sagemath.org/ticket/7711#comment:1
https://trac.sagemath.org/ticket/7711#comment:1
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.3</em> to <em>sage-4.3.1</em>
</li>
</ul>
<p>
I'm declaring a total feature freeze on sage-4.3.
</p>
TicketAlexGhitzaSat, 02 Jan 2010 11:14:53 GMT
https://trac.sagemath.org/ticket/7711#comment:2
https://trac.sagemath.org/ticket/7711#comment:2
<p>
Note also that in Paul's first example we have:
</p>
<pre class="wiki">sage: p.integral().parent()
Univariate Polynomial Ring in y over Fraction Field of Multivariate Polynomial Ring in x, z over Finite Field of size 2147483647
</pre><p>
whereas in the second:
</p>
<pre class="wiki">sage: p.integral().parent()
Univariate Polynomial Ring in y over Multivariate Polynomial Ring in x, z over Finite Field of size 2147483629
</pre><p>
This is probably where the issue is.
</p>
TicketzimmermaFri, 05 Feb 2010 20:19:00 GMT
https://trac.sagemath.org/ticket/7711#comment:3
https://trac.sagemath.org/ticket/7711#comment:3
<p>
The bug is still there in 4.3.1.
</p>
TicketjenMon, 19 Mar 2012 18:28:17 GMTstatus, milestone changed; keywords set
https://trac.sagemath.org/ticket/7711#comment:4
https://trac.sagemath.org/ticket/7711#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>keywords</strong>
<em>rd2</em> added
</li>
<li><strong>milestone</strong>
changed from <em>sage-5.0</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
This is no longer an issue:
</p>
<pre class="wiki">sage: P.<x,z> = PolynomialRing(GF(2147483647))
sage: Q.<y> = PolynomialRing(P)
sage: p=x+y+z
sage: p.integral()
-1073741823*y^2 + (x + z)*y
sage: P(-1073741823*2)
1
</pre>
TicketjenMon, 19 Mar 2012 18:28:49 GMTstatus changed
https://trac.sagemath.org/ticket/7711#comment:5
https://trac.sagemath.org/ticket/7711#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketdsmMon, 19 Mar 2012 18:37:47 GMT
https://trac.sagemath.org/ticket/7711#comment:6
https://trac.sagemath.org/ticket/7711#comment:6
<p>
I don't agree that this has been fixed. In 5.0.beta8, I only have to go up to the next prime:
</p>
<pre class="wiki">
sage: def f(N):
....: P.<x,z> = PolynomialRing(GF(N))
....: Q.<y> = PolynomialRing(P)
....: p=x+y+z
....: return p.integral()
....:
sage: N = 2147483647
sage: f(N)
-1073741823*y^2 + (x + z)*y
sage: N = next_prime(N)
sage: N
2147483659
sage: f(N)
1/2*y^2 + (x + z)*y
</pre>
TicketjenMon, 19 Mar 2012 18:50:23 GMTstatus changed; keywords deleted
https://trac.sagemath.org/ticket/7711#comment:7
https://trac.sagemath.org/ticket/7711#comment:7
<ul>
<li><strong>keywords</strong>
<em>rd2</em> removed
</li>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Good catch. I'll change it back to "needs work."
</p>
TicketAlexGhitzaSat, 24 Mar 2012 03:20:45 GMTmilestone changed
https://trac.sagemath.org/ticket/7711#comment:8
https://trac.sagemath.org/ticket/7711#comment:8
<ul>
<li><strong>milestone</strong>
changed from <em>sage-duplicate/invalid/wontfix</em> to <em>sage-5.0</em>
</li>
</ul>
TicketAlexGhitzaSat, 24 Mar 2012 05:24:02 GMT
https://trac.sagemath.org/ticket/7711#comment:9
https://trac.sagemath.org/ticket/7711#comment:9
<p>
For large primes, Sage uses polydicts for representing multivariate polynomials, instead of using Singular. The trouble here is that dividing a polydict by another polydict automatically creates the fraction field, even when the denominator is actually an element of the coefficient ring.
</p>
<p>
The attached patch tries to detect this (relatively common) special case and perform the division in the coefficient ring instead of going to the fraction field of the ring of polynomials. This fixes the problems with <code>integral()</code> reported here.
</p>
TicketAlexGhitzaSat, 24 Mar 2012 05:25:24 GMTstatus changed; author set
https://trac.sagemath.org/ticket/7711#comment:10
https://trac.sagemath.org/ticket/7711#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Alex Ghitza</em>
</li>
</ul>
TicketzimmermaSat, 24 Mar 2012 08:59:58 GMT
https://trac.sagemath.org/ticket/7711#comment:11
https://trac.sagemath.org/ticket/7711#comment:11
<p>
Alex,
</p>
<p>
there is something I don't understand with your patch. You check that <code>right</code> is in the base
ring, but not <code>1/right</code>, thus what happens the base ring is not a field? Compare for example:
</p>
<pre class="wiki">sage: P.<x,z> = PolynomialRing(ZZ)
sage: Q.<y> = PolynomialRing(P)
sage: p=x+y+z
sage: t=p/2
sage: t.parent()
Univariate Polynomial Ring in y over Multivariate Polynomial Ring in x, z over Rational Field
sage: u=p.integral()
sage: u.parent()
Univariate Polynomial Ring in y over Fraction Field of Multivariate Polynomial Ring in x, z over Integer Ring
</pre><p>
Why do t and u have different parents?
</p>
<p>
Paul
</p>
TicketzimmermaSat, 24 Mar 2012 09:00:40 GMTstatus changed
https://trac.sagemath.org/ticket/7711#comment:12
https://trac.sagemath.org/ticket/7711#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
TicketzimmermaSat, 24 Mar 2012 09:01:07 GMTreviewer set
https://trac.sagemath.org/ticket/7711#comment:13
https://trac.sagemath.org/ticket/7711#comment:13
<ul>
<li><strong>reviewer</strong>
set to <em>Paul Zimmermann</em>
</li>
</ul>
TicketAlexGhitzaSat, 24 Mar 2012 09:08:16 GMT
https://trac.sagemath.org/ticket/7711#comment:14
https://trac.sagemath.org/ticket/7711#comment:14
<p>
I guess I always found the following strange:
</p>
<pre class="wiki">sage: type(3)
<type 'sage.rings.integer.Integer'>
sage: type(3/1)
<type 'sage.rings.rational.Rational'>
</pre><p>
and that influenced me in writing this patch. I don't however have a strong opinion about this, and I'm happy to change it to make things more consistent by working in the fraction field of base_ring. I'll replace the patch with one having this behavior soon.
</p>
TicketAlexGhitzaSat, 24 Mar 2012 09:28:11 GMT
https://trac.sagemath.org/ticket/7711#comment:15
https://trac.sagemath.org/ticket/7711#comment:15
<p>
By the way, the issue you point out with ZZ coefficients is apparently orthogonal to this patch. Multivariate polynomials over ZZ are handled by Singular, and the patch does not touch them. It only modifies the behavior for multivariate polynomials that are implemented as polydict's, such as the ones over finite fields of huge characteristic that this ticket started with.
</p>
<p>
Your ZZ example behaves the same with or without this patch. If you find it really bothersome, maybe it can be on a new ticket.
</p>
TicketAlexGhitzaSat, 24 Mar 2012 09:39:23 GMTstatus changed
https://trac.sagemath.org/ticket/7711#comment:16
https://trac.sagemath.org/ticket/7711#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
TicketzimmermaSat, 24 Mar 2012 09:52:44 GMT
https://trac.sagemath.org/ticket/7711#comment:17
https://trac.sagemath.org/ticket/7711#comment:17
<p>
Alex, can you add an example where your patch is called with coefficients in a ring?
</p>
<p>
About <code>3/1</code> giving a rational, this is ok for me. Indeed, you don't want the type of the result
to differ when the division is exact or not: <code>3/2</code> and <code>3/1</code> should give both rationals.
</p>
<p>
Paul
</p>
TicketAlexGhitzaSat, 24 Mar 2012 10:42:36 GMTstatus changed
https://trac.sagemath.org/ticket/7711#comment:18
https://trac.sagemath.org/ticket/7711#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
Alright, I'm starting to see what you are objecting to, and I agree with you. Just to make sure I get this right: even the documented examples from the docstring of integral are inconsistent in this way
</p>
<pre class="wiki"> EXAMPLES::
sage: R.<x> = ZZ[]
sage: R(0).integral()
0
sage: f = R(2).integral(); f
2*x
Note that since the integral is defined over the same base ring the
integral is actually in the base ring.
::
sage: f.parent()
Univariate Polynomial Ring in x over Integer Ring
If the integral isn't defined over the same base ring, then the
base ring is extended::
sage: f = x^3 + x - 2
sage: g = f.integral(); g
1/4*x^4 + 1/2*x^2 - 2*x
sage: g.parent()
Univariate Polynomial Ring in x over Rational Field
</pre><p>
We want Sage to be less clever and more consistent, so the integral of 2 should be 2x in QQ[x] rather than in ZZ[x].
</p>
<p>
Of course, this is fun to implement, because you might have something like:
</p>
<pre class="wiki">sage: A.<a, b> = PolynomialRing(ZZ)
sage: C.<c> = PolynomialRing(A)
sage: D.<d> = PowerSeriesRing(C)
sage: R.<x> = PolynomialRing(D)
sage: f = a*x^2 + c*x
sage: f.parent()
Univariate Polynomial Ring in x over Power Series Ring in d over
Univariate Polynomial Ring in c over Multivariate Polynomial Ring
in a, b over Integer Ring
</pre><p>
What I would like to do is have f.integral() live in
</p>
<pre class="wiki">Univariate Polynomial Ring in x over Power Series Ring in d over
Univariate Polynomial Ring in c over Multivariate Polynomial Ring
in a, b over Rational Field
</pre><p>
So I want to change to the fraction field at the very bottom of the chain of extensions. This means starting with R and going down to ZZ step by step, then changing ZZ to QQ and walking back up, changing all the intermediate rings along the way. It can get expensive, but I guess that's the price to pay for working with such monstrosities.
</p>
<p>
If my outline agrees with what you had in mind, I'll produce a new patch based on it.
</p>
TicketzimmermaSat, 24 Mar 2012 11:03:37 GMT
https://trac.sagemath.org/ticket/7711#comment:19
https://trac.sagemath.org/ticket/7711#comment:19
<p>
Alex,
</p>
<p>
in fact I guess your initial patch did what we want. Indeed with your latest example:
</p>
<pre class="wiki">sage: g=f/2
sage: g.parent()
Univariate Polynomial Ring in x over Power Series Ring in d over Univariate Polynomial Ring in c over Multivariate Polynomial Ring in a, b over Rational Field
</pre><p>
thus the fact of dividing f by an element of the base ring automatically extends it to the corresponding
fraction field if necessary.
</p>
<p>
Thus I suggest you revert to your first patch (sorry) and add the above example as test.
</p>
<p>
Paul
</p>
TicketwasSat, 24 Mar 2012 11:54:33 GMT
https://trac.sagemath.org/ticket/7711#comment:20
https://trac.sagemath.org/ticket/7711#comment:20
<p>
Does this patch break a major fundamental design decision in both Sage and Magma, namely that / is a constructor for elements of the fraction field. E.g., 3/1 has parent QQ.
</p>
TicketzimmermaSat, 24 Mar 2012 14:08:13 GMT
https://trac.sagemath.org/ticket/7711#comment:21
https://trac.sagemath.org/ticket/7711#comment:21
<p>
William, I don't think this patch (still not ready) will break anything, since I believe it will just
return f/c where f is a polynomial and c an element of the base ring.
</p>
<p>
Anyway your advice how to best solve this problem is welcome.
</p>
<p>
Paul
</p>
TicketAlexGhitzaSat, 24 Mar 2012 21:17:27 GMT
https://trac.sagemath.org/ticket/7711#comment:22
https://trac.sagemath.org/ticket/7711#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7711#comment:20" title="Comment 20">was</a>:
</p>
<blockquote class="citation">
<p>
Does this patch break a major fundamental design decision in both Sage and Magma, namely that / is a constructor for elements of the fraction field. E.g., 3/1 has parent QQ.
</p>
</blockquote>
<p>
Hi William, can you have a look at the docstring for p.integral() as it stands now and tell me whether you think it complies with this design decision? Here is an example:
</p>
<pre class="wiki">sage: S.<x> = ZZ[]
sage: p = 2*x
sage: p.integral()
x^2
sage: p.integral().parent()
Univariate Polynomial Ring in x over Integer Ring
</pre><p>
Behind the scenes Sage performed 2/2 and decided that the answer was 1 in ZZ rather than 1 in QQ, so this seems to break the convention. Also, the answer has a different parent than (3*x).integral(), which is the type of inconsistency that Paul was pointing out before. So should this stay the way it is, or should this be changed to be more consistent?
</p>
<p>
But it gets a tiny bit more complicated than this. Suppose your coefficients are not ZZ, but rather ZZ[y], where y is a vector of 200 variables. The integral of 2*x is still <code>x^2</code>, but where do we want this <code>x^2</code> to live? Possible answers are (a) ZZ[y][x], (b) Frac(ZZ[y])[x], (c) QQ[y][x].
The current behavior is (a) for 2*x and (b) for 3*x, and I am currently leaning toward changing both to (c). Here's why: you have p in R[x], where R is some coefficient ring. When you do p.integral(), you are not really dividing p by integers n, but rather the coefficients of p by integers n. So maybe we should look at what division by n in the coefficient ring R does:
</p>
<pre class="wiki">sage: R.<y0,y1,y2,y3> = ZZ[]
sage: S.<x> = R[]
sage: p = 2*y0
sage: p.parent()
Multivariate Polynomial Ring in y0, y1, y2, y3 over Integer Ring
sage: (p/2).parent()
Multivariate Polynomial Ring in y0, y1, y2, y3 over Rational Field
sage: p = 3*y0
sage: (p/2).parent()
Multivariate Polynomial Ring in y0, y1, y2, y3 over Rational Field
</pre><p>
So p/2 is not in the fraction field of R. This is what I would like integral() to do as well.
</p>
<p>
Thoughts?
</p>
TicketAlexGhitzaSat, 24 Mar 2012 23:17:14 GMT
https://trac.sagemath.org/ticket/7711#comment:23
https://trac.sagemath.org/ticket/7711#comment:23
<p>
OK, I have changed the patch to a new one that achieves objective (c) in the previous comment. It is also simpler and cleaner than the previous patches. <code>integral</code> now relies on the coefficient rings to do the right thing. They mostly do, except for polydict, whose behavior is fixed by the patch as well.
</p>
TicketAlexGhitzaSat, 24 Mar 2012 23:23:06 GMTstatus changed
https://trac.sagemath.org/ticket/7711#comment:24
https://trac.sagemath.org/ticket/7711#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
TicketzimmermaMon, 26 Mar 2012 07:49:49 GMT
https://trac.sagemath.org/ticket/7711#comment:25
https://trac.sagemath.org/ticket/7711#comment:25
<p>
Alex, I tried to apply your patch to sage-5.0.beta9 but it failed:
</p>
<pre class="wiki">
sage: hg_sage.import_patch("trac7711.patch")
cd "/localdisk/tmp/sage-5.0.beta9/devel/sage" && sage --hg import "/localdisk/tmp/sage-5.0.beta9/trac7711.patch"
applying /localdisk/tmp/sage-5.0.beta9/trac7711.patch
patching file sage/rings/polynomial/polynomial_element.pyx
Hunk #1 FAILED at 2369
1 out of 1 hunks FAILED -- saving rejects to file sage/rings/polynomial/polynomial_element.pyx.rej
abort: patch failed to apply
</pre><p>
For which version is this patch?
</p>
<p>
Paul
</p>
TicketAlexGhitzaMon, 26 Mar 2012 07:55:51 GMT
https://trac.sagemath.org/ticket/7711#comment:26
https://trac.sagemath.org/ticket/7711#comment:26
<blockquote class="citation">
<p>
For which version is this patch?
</p>
</blockquote>
<p>
It's based on sage-4.8. I have a sage-5.0.beta10 somewhere, I'll rebase it on that soon.
</p>
TicketzimmermaMon, 26 Mar 2012 07:57:22 GMT
https://trac.sagemath.org/ticket/7711#comment:27
https://trac.sagemath.org/ticket/7711#comment:27
<p>
it seems my sage-5.0.beta9 was corrupted. I'll compile sage-5.0.beta10 from source and try
again.
</p>
<p>
Paul
</p>
TicketAlexGhitzaMon, 26 Mar 2012 08:10:53 GMT
https://trac.sagemath.org/ticket/7711#comment:28
https://trac.sagemath.org/ticket/7711#comment:28
<p>
I tried on a clean sage-5.0.beta10 and the previous version of the patch did not apply correctly. I have rebased it now and it should work.
</p>
TicketzimmermaMon, 26 Mar 2012 15:04:59 GMT
https://trac.sagemath.org/ticket/7711#comment:29
https://trac.sagemath.org/ticket/7711#comment:29
<p>
replying to comment <a class="ticket" href="https://trac.sagemath.org/ticket/7711#comment:22" title="Comment 22">22</a>: I guess we should just return <code>p/2</code> and let the coercion
mechanism decide the corresponding parent. In such a way it will ensure that <code>p.integral()</code> and <code>p/2</code> have the same type.
</p>
<p>
Paul
</p>
TicketzimmermaMon, 26 Mar 2012 16:00:34 GMTstatus changed
https://trac.sagemath.org/ticket/7711#comment:30
https://trac.sagemath.org/ticket/7711#comment:30
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
</ul>
<p>
I confirm the rebased patch applies cleanly to sage-5.0.beta10.
</p>
<p>
However there is still an issue:
</p>
<pre class="wiki">sage: R.<x> = ZZ[]
sage: R(0).integral().parent()
Univariate Polynomial Ring in x over Integer Ring
sage: R(3).integral().parent()
Univariate Polynomial Ring in x over Rational Field
</pre><p>
Why do we get a different parent for zero?
</p>
<p>
Paul
</p>
TicketAlexGhitzaMon, 26 Mar 2012 21:43:57 GMTattachment set
https://trac.sagemath.org/ticket/7711
https://trac.sagemath.org/ticket/7711
<ul>
<li><strong>attachment</strong>
set to <em>trac7711.patch</em>
</li>
</ul>
TicketAlexGhitzaMon, 26 Mar 2012 21:46:19 GMTstatus changed
https://trac.sagemath.org/ticket/7711#comment:31
https://trac.sagemath.org/ticket/7711#comment:31
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
<p>
Ah, that's because the degree of R(0) is negative. Sorry. It's fixed in the new patch, and I've added <code>R(0).integral().parent()</code> to the doctests.
</p>
TicketzimmermaTue, 27 Mar 2012 11:41:00 GMTstatus changed
https://trac.sagemath.org/ticket/7711#comment:32
https://trac.sagemath.org/ticket/7711#comment:32
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I get only one doctest failure, but it also fails with vanilla sage-5.0.beta10 and seems
unrelated:
</p>
<pre class="wiki">sage -t "devel/sage-7711/sage/misc/sagedoc.py"
**********************************************************************
File "/localdisk/tmp/sage-5.0.beta10/devel/sage-7711/sage/misc/sagedoc.py", line 566:
sage: 'abvar/homology' in _search_src_or_doc('doc', 'homology', 'variety', interact=False)
Expected:
True
Got:
Warning, the following Sage documentation hasn't been built,
so documentation search results may be incomplete:
<BLANKLINE>
/localdisk/tmp/sage-5.0.beta10/devel/sage/doc/output/html/de/tutorial
...
</pre><p>
This patch not only fixes the original issue, but improves the coherence of Sage results.
Good job Alex!
</p>
<p>
Paul
</p>
TicketjdemeyerMon, 02 Apr 2012 15:23:49 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/7711#comment:33
https://trac.sagemath.org/ticket/7711#comment:33
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.0.beta12</em>
</li>
</ul>
Ticket