ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 23 Oct 2018 12:16:38 +0200Reducing the Coefficients of a Polynomial Modulo an Idealhttps://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/I have a polynomial in two variables $t_1$ and $t_2$ (say $2t_1 + at_2$) defined over a ring which is itself a polynomial ring (say $\mathbf{Z}[a]$). I'd like to reduce the coefficients of the polynomial modulo an ideal of the latter ring (say $(2)$ or $(a)$ or $(2,a)$). When I execute
M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(a)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))
I get `2*t1`, as I would expect. On the other hand, the code
M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(2)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))
gives me a type error ("`polynomial must have unit leading coefficient`"). And the input
M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(2,a)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))
gives the output `2*t1 + abar*t2` rather than the `0` I would have expected. What should I do to get the outputs I would expect (namely `2*t1`, `abar*t2`, and `0`, respectively)?Fri, 19 Oct 2018 03:16:14 +0200https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/Answer by rburing for <p>I have a polynomial in two variables $t_1$ and $t_2$ (say $2t_1 + at_2$) defined over a ring which is itself a polynomial ring (say $\mathbf{Z}[a]$). I'd like to reduce the coefficients of the polynomial modulo an ideal of the latter ring (say $(2)$ or $(a)$ or $(2,a)$). When I execute</p>
<pre><code>M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(a)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))
</code></pre>
<p>I get <code>2*t1</code>, as I would expect. On the other hand, the code</p>
<pre><code>M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(2)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))
</code></pre>
<p>gives me a type error ("<code>polynomial must have unit leading coefficient</code>"). And the input</p>
<pre><code>M.<a> = PolynomialRing(ZZ)
R.<t1,t2> = PolynomialRing(M)
m = M.ideal(2,a)
(2*t1 + a*t2).change_ring(QuotientRing(M,m))
</code></pre>
<p>gives the output <code>2*t1 + abar*t2</code> rather than the <code>0</code> I would have expected. What should I do to get the outputs I would expect (namely <code>2*t1</code>, <code>abar*t2</code>, and <code>0</code>, respectively)?</p>
https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/?answer=44031#post-id-44031The explanation can be found in the [documentation for `QuotientRing`](http://doc.sagemath.org/html/en/reference/rings/sage/rings/quotient_ring.html#sage.rings.quotient_ring.QuotientRing):
> ASSUMPTION:
>
> `I` has a method `I.reduce(x)` returning the normal form of elements $x \in R$. In other words, it is required that `I.reduce(x)==I.reduce(y)` $\iff x-y \in I$, and `x-I.reduce(x) in I`, for all $x,y \in R$.
That is, elements of a `QuotientRing` are represented by normal forms (usually obtained by polynomial division).
We can see that $(2) \subset \mathbf{Z}[x]$ in Sage does not possess such a method:
R.<x> = ZZ[]
I = R.ideal(2)
I.reduce??
This shows the source code of `I.reduce` which is the default implementation `lambda f: return f`, which doesn't satisfy the property that `QuotientRing` assumes: e.g. `I.reduce(2) != I.reduce(0)` but $2 \in I$.
The implementation of `I.reduce` is the same for `I = R.ideal(2,x)` which explains your last result.
Note that $\mathbf{Z}[x]$ is not a [Euclidean ring](https://en.wikipedia.org/wiki/Euclidean_domain) because not every ideal is principal (e.g. the ideal $(2,x)$ is a non-principal), so it is impossible to have a normal form for elements in a quotient via naive polynomial division in $\mathbf{Z}[x]$, in general. There is a theory of Groebner bases for univariate polynomial rings over PIDs which would apply to $\mathbf{Z}[x]$, but it doesn't seem to be implemented in Sage.
Of course not all is lost, because the ideals you consider are nice enough, e.g. $\mathbf{Z}[x]/(2) \cong \mathbf{F}_2[x]$ and $\mathbf{Z}[x]/(2,x) \cong \mathbf{F}_2[x]/(x) \cong \mathbf{F}_2$ and the objects on the right-hand sides *can* be represented easily in Sage:
sage: (2*t1 + a*t2).change_ring(GF(2)[a])
a*t2
sage: (2*t1 + a*t2).change_ring(GF(2)[a].quotient(a))
0
Or, if you prefer the name `abar` for the image of `a` in the quotient:
sage: S.<abar> = GF(2)[]
sage: (2*t1 + a*t2).change_ring(S)
abar*t2
sage: (2*t1 + a*t2).change_ring(S.quotient(abar))
0Mon, 22 Oct 2018 21:18:23 +0200https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/?answer=44031#post-id-44031Comment by Annie Carter for <p>The explanation can be found in the <a href="http://doc.sagemath.org/html/en/reference/rings/sage/rings/quotient_ring.html#sage.rings.quotient_ring.QuotientRing">documentation for <code>QuotientRing</code></a>:</p>
<blockquote>
<p>ASSUMPTION:</p>
<p><code>I</code> has a method <code>I.reduce(x)</code> returning the normal form of elements $x \in R$. In other words, it is required that <code>I.reduce(x)==I.reduce(y)</code> $\iff x-y \in I$, and <code>x-I.reduce(x) in I</code>, for all $x,y \in R$.</p>
</blockquote>
<p>That is, elements of a <code>QuotientRing</code> are represented by normal forms (usually obtained by polynomial division).</p>
<p>We can see that $(2) \subset \mathbf{Z}[x]$ in Sage does not possess such a method:</p>
<pre><code>R.<x> = ZZ[]
I = R.ideal(2)
I.reduce??
</code></pre>
<p>This shows the source code of <code>I.reduce</code> which is the default implementation <code>lambda f: return f</code>, which doesn't satisfy the property that <code>QuotientRing</code> assumes: e.g. <code>I.reduce(2) != I.reduce(0)</code> but $2 \in I$.</p>
<p>The implementation of <code>I.reduce</code> is the same for <code>I = R.ideal(2,x)</code> which explains your last result.</p>
<p>Note that $\mathbf{Z}[x]$ is not a <a href="https://en.wikipedia.org/wiki/Euclidean_domain">Euclidean ring</a> because not every ideal is principal (e.g. the ideal $(2,x)$ is a non-principal), so it is impossible to have a normal form for elements in a quotient via naive polynomial division in $\mathbf{Z}[x]$, in general. There is a theory of Groebner bases for univariate polynomial rings over PIDs which would apply to $\mathbf{Z}[x]$, but it doesn't seem to be implemented in Sage.</p>
<p>Of course not all is lost, because the ideals you consider are nice enough, e.g. $\mathbf{Z}[x]/(2) \cong \mathbf{F}_2[x]$ and $\mathbf{Z}[x]/(2,x) \cong \mathbf{F}_2[x]/(x) \cong \mathbf{F}_2$ and the objects on the right-hand sides <em>can</em> be represented easily in Sage:</p>
<pre><code>sage: (2*t1 + a*t2).change_ring(GF(2)[a])
a*t2
sage: (2*t1 + a*t2).change_ring(GF(2)[a].quotient(a))
0
</code></pre>
<p>Or, if you prefer the name <code>abar</code> for the image of <code>a</code> in the quotient:</p>
<pre><code>sage: S.<abar> = GF(2)[]
sage: (2*t1 + a*t2).change_ring(S)
abar*t2
sage: (2*t1 + a*t2).change_ring(S.quotient(abar))
0
</code></pre>
https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/?comment=44033#post-id-44033Is there any hope if the ring of coefficients has more than one variable? The application I'm interested in is when the coefficient ring has the form $\mathbf{Z}[a_1, \ldots, a_n]$ and I reduce modulo some power of a maximal ideal of the form $(p, a_1, \ldots, a_n)$ with $p$ a prime.Mon, 22 Oct 2018 23:18:12 +0200https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/?comment=44033#post-id-44033Comment by rburing for <p>The explanation can be found in the <a href="http://doc.sagemath.org/html/en/reference/rings/sage/rings/quotient_ring.html#sage.rings.quotient_ring.QuotientRing">documentation for <code>QuotientRing</code></a>:</p>
<blockquote>
<p>ASSUMPTION:</p>
<p><code>I</code> has a method <code>I.reduce(x)</code> returning the normal form of elements $x \in R$. In other words, it is required that <code>I.reduce(x)==I.reduce(y)</code> $\iff x-y \in I$, and <code>x-I.reduce(x) in I</code>, for all $x,y \in R$.</p>
</blockquote>
<p>That is, elements of a <code>QuotientRing</code> are represented by normal forms (usually obtained by polynomial division).</p>
<p>We can see that $(2) \subset \mathbf{Z}[x]$ in Sage does not possess such a method:</p>
<pre><code>R.<x> = ZZ[]
I = R.ideal(2)
I.reduce??
</code></pre>
<p>This shows the source code of <code>I.reduce</code> which is the default implementation <code>lambda f: return f</code>, which doesn't satisfy the property that <code>QuotientRing</code> assumes: e.g. <code>I.reduce(2) != I.reduce(0)</code> but $2 \in I$.</p>
<p>The implementation of <code>I.reduce</code> is the same for <code>I = R.ideal(2,x)</code> which explains your last result.</p>
<p>Note that $\mathbf{Z}[x]$ is not a <a href="https://en.wikipedia.org/wiki/Euclidean_domain">Euclidean ring</a> because not every ideal is principal (e.g. the ideal $(2,x)$ is a non-principal), so it is impossible to have a normal form for elements in a quotient via naive polynomial division in $\mathbf{Z}[x]$, in general. There is a theory of Groebner bases for univariate polynomial rings over PIDs which would apply to $\mathbf{Z}[x]$, but it doesn't seem to be implemented in Sage.</p>
<p>Of course not all is lost, because the ideals you consider are nice enough, e.g. $\mathbf{Z}[x]/(2) \cong \mathbf{F}_2[x]$ and $\mathbf{Z}[x]/(2,x) \cong \mathbf{F}_2[x]/(x) \cong \mathbf{F}_2$ and the objects on the right-hand sides <em>can</em> be represented easily in Sage:</p>
<pre><code>sage: (2*t1 + a*t2).change_ring(GF(2)[a])
a*t2
sage: (2*t1 + a*t2).change_ring(GF(2)[a].quotient(a))
0
</code></pre>
<p>Or, if you prefer the name <code>abar</code> for the image of <code>a</code> in the quotient:</p>
<pre><code>sage: S.<abar> = GF(2)[]
sage: (2*t1 + a*t2).change_ring(S)
abar*t2
sage: (2*t1 + a*t2).change_ring(S.quotient(abar))
0
</code></pre>
https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/?comment=44034#post-id-44034There is hope because such a quotient is a finite (coefficients and the exponent of each variable can be bounded) commutative ring, so it should be possible to do calculations in it. (For a power $k > 1$ of the maximal ideal it is not a domain because $p^k = 0$ whereas $p \neq 0$.) It would be a good question to ask (e.g. on this site as a new question) how to represent this kind of ring inside Sage.Tue, 23 Oct 2018 00:21:46 +0200https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/?comment=44034#post-id-44034Comment by rburing for <p>The explanation can be found in the <a href="http://doc.sagemath.org/html/en/reference/rings/sage/rings/quotient_ring.html#sage.rings.quotient_ring.QuotientRing">documentation for <code>QuotientRing</code></a>:</p>
<blockquote>
<p>ASSUMPTION:</p>
<p><code>I</code> has a method <code>I.reduce(x)</code> returning the normal form of elements $x \in R$. In other words, it is required that <code>I.reduce(x)==I.reduce(y)</code> $\iff x-y \in I$, and <code>x-I.reduce(x) in I</code>, for all $x,y \in R$.</p>
</blockquote>
<p>That is, elements of a <code>QuotientRing</code> are represented by normal forms (usually obtained by polynomial division).</p>
<p>We can see that $(2) \subset \mathbf{Z}[x]$ in Sage does not possess such a method:</p>
<pre><code>R.<x> = ZZ[]
I = R.ideal(2)
I.reduce??
</code></pre>
<p>This shows the source code of <code>I.reduce</code> which is the default implementation <code>lambda f: return f</code>, which doesn't satisfy the property that <code>QuotientRing</code> assumes: e.g. <code>I.reduce(2) != I.reduce(0)</code> but $2 \in I$.</p>
<p>The implementation of <code>I.reduce</code> is the same for <code>I = R.ideal(2,x)</code> which explains your last result.</p>
<p>Note that $\mathbf{Z}[x]$ is not a <a href="https://en.wikipedia.org/wiki/Euclidean_domain">Euclidean ring</a> because not every ideal is principal (e.g. the ideal $(2,x)$ is a non-principal), so it is impossible to have a normal form for elements in a quotient via naive polynomial division in $\mathbf{Z}[x]$, in general. There is a theory of Groebner bases for univariate polynomial rings over PIDs which would apply to $\mathbf{Z}[x]$, but it doesn't seem to be implemented in Sage.</p>
<p>Of course not all is lost, because the ideals you consider are nice enough, e.g. $\mathbf{Z}[x]/(2) \cong \mathbf{F}_2[x]$ and $\mathbf{Z}[x]/(2,x) \cong \mathbf{F}_2[x]/(x) \cong \mathbf{F}_2$ and the objects on the right-hand sides <em>can</em> be represented easily in Sage:</p>
<pre><code>sage: (2*t1 + a*t2).change_ring(GF(2)[a])
a*t2
sage: (2*t1 + a*t2).change_ring(GF(2)[a].quotient(a))
0
</code></pre>
<p>Or, if you prefer the name <code>abar</code> for the image of <code>a</code> in the quotient:</p>
<pre><code>sage: S.<abar> = GF(2)[]
sage: (2*t1 + a*t2).change_ring(S)
abar*t2
sage: (2*t1 + a*t2).change_ring(S.quotient(abar))
0
</code></pre>
https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/?comment=44038#post-id-44038So it seems a normal form for an element of $\mathbf{Z}[a_1,\ldots,a_n]/(p,a_1,\ldots,a_n)^k$ would be a polynomial of degree $\lt k$ in $a_1,\ldots,a_n$ where the coefficients of monomials of degree $d$ are reduced modulo $p^{k-d}$. (Exercise: count how many such polynomials there are.) If this satisfies the desired properties (I guess so) then you could implement this as `reduce` (and if you make it a method for a custom class then you could use `QuotientRing`).Tue, 23 Oct 2018 12:16:38 +0200https://ask.sagemath.org/question/43982/reducing-the-coefficients-of-a-polynomial-modulo-an-ideal/?comment=44038#post-id-44038