ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 31 Mar 2020 06:36:33 -0500Polynomial division in quotient rings?https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/I have a working example shown below to help explain my question.
R.<x> = GF(2)[];
I = R.ideal([x^2 - 1])
S.<u> = R.quotient_ring(I)
f = x^2 + x
g = x
print(f.quo_rem(g))
f = u^2 + u
g = u
print(f.quo_rem(g))
The first quo_rem call works fine, but the second does not. Is polynomial division not supported for quotient rings, or am I calling it the wrong way? I'm specifically interested in doing this for multivariate polynomials, but I can't seem to get it to work for a single variable either.
Related to the question, I am interested in understanding this division in quotient rings better. If the operation isn't supported in sage, any sort of references/algorithms on how to do such a calculation would be very helpful and appreciated.Sat, 28 Mar 2020 18:49:43 -0500https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/Answer by rburing for <p>I have a working example shown below to help explain my question.</p>
<pre><code>R.<x> = GF(2)[];
I = R.ideal([x^2 - 1])
S.<u> = R.quotient_ring(I)
f = x^2 + x
g = x
print(f.quo_rem(g))
f = u^2 + u
g = u
print(f.quo_rem(g))
</code></pre>
<p>The first quo_rem call works fine, but the second does not. Is polynomial division not supported for quotient rings, or am I calling it the wrong way? I'm specifically interested in doing this for multivariate polynomials, but I can't seem to get it to work for a single variable either.</p>
<p>Related to the question, I am interested in understanding this division in quotient rings better. If the operation isn't supported in sage, any sort of references/algorithms on how to do such a calculation would be very helpful and appreciated.</p>
https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?answer=50424#post-id-50424The problem is that in such rings the quotient and remainder are not well-defined in general.
Consider the following example: divide $f = x^2 y + xy^2 + y^2$ by $y^2-1$ in the ring $\mathbb{Q}[x,y]/\langle xy-1\rangle$.
On the one hand, $$f = (x+1)(y^2-1) + 2x + 1 + x(xy-1),$$ so $(x+1)$ is "a quotient" and $2x+1$ is "a remainder" (and $x(xy-1)$ is zero in this ring).
On the other hand, $$f = 1\cdot(y^2-1) + x + y + 1 + (x+y)(xy-1),$$ so $1$ is "a quotient" and $x+y+1$ is "a remainder" (and $(x+y)(xy-1)$ is zero in this ring).
The problem is basically that division in a polynomial ring by *several* polynomials ($y^2-1$ and $xy-1$ in the example) is a priori not well-defined. For one, the problem is underdetermined. Choosing a monomial ordering and an ordering of the polynomials to be divided by allows you to define an unambiguous (multivariate) division algorithm. Unfortunately its output will depend on the orderings chosen. Furthermore, while a remainder of zero will mean that the input belongs to the ideal generated by the polynomials to be divided by, the converse is not necessarily true. Groebner bases were invented to address these issues. See for example the book *Ideals, Varieties, and Algorithms* by Cox, Little, and O'Shea. In fact I took the example from there; I just (slightly artificially) rephrased it to be about a quotient ring. If you are only interested in "a remainder" (any), then you can use the division algorithm of Theorem 3 in that book. If you want more, you have to read more. Good luck.
---
SageMath can find the remainder using the multivariate division algorithm:
sage: R.<x,y> = PolynomialRing(QQ,2,order='lex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
2*x + 1
sage: R.<x,y> = PolynomialRing(QQ,2,order='invlex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
y + x + 1
To find the quotient(s), I'm not sure if there is built-in method in SageMath. But it's not difficult to implement the division algorithm in SageMath, because things like monomial orderings and getting the leading term/coefficient, etc. are already there. There is also a trick to get the quotient(s) by adding extra variables to track what happens in the reduction. It goes something like this:
sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='lex(2),lex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(x + 1, x)
sage: rem.subs({c1:0,c2:0})
2*x + 1
sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='invlex(2),invlex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(1, y + x)
sage: rem.subs({c1:0,c2:0})
y + x + 1Sun, 29 Mar 2020 13:27:56 -0500https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?answer=50424#post-id-50424Comment by rburing for <p>The problem is that in such rings the quotient and remainder are not well-defined in general.</p>
<p>Consider the following example: divide $f = x^2 y + xy^2 + y^2$ by $y^2-1$ in the ring $\mathbb{Q}[x,y]/\langle xy-1\rangle$.</p>
<p>On the one hand, $$f = (x+1)(y^2-1) + 2x + 1 + x(xy-1),$$ so $(x+1)$ is "a quotient" and $2x+1$ is "a remainder" (and $x(xy-1)$ is zero in this ring).</p>
<p>On the other hand, $$f = 1\cdot(y^2-1) + x + y + 1 + (x+y)(xy-1),$$ so $1$ is "a quotient" and $x+y+1$ is "a remainder" (and $(x+y)(xy-1)$ is zero in this ring).</p>
<p>The problem is basically that division in a polynomial ring by <em>several</em> polynomials ($y^2-1$ and $xy-1$ in the example) is a priori not well-defined. For one, the problem is underdetermined. Choosing a monomial ordering and an ordering of the polynomials to be divided by allows you to define an unambiguous (multivariate) division algorithm. Unfortunately its output will depend on the orderings chosen. Furthermore, while a remainder of zero will mean that the input belongs to the ideal generated by the polynomials to be divided by, the converse is not necessarily true. Groebner bases were invented to address these issues. See for example the book <em>Ideals, Varieties, and Algorithms</em> by Cox, Little, and O'Shea. In fact I took the example from there; I just (slightly artificially) rephrased it to be about a quotient ring. If you are only interested in "a remainder" (any), then you can use the division algorithm of Theorem 3 in that book. If you want more, you have to read more. Good luck.</p>
<hr>
<p>SageMath can find the remainder using the multivariate division algorithm:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ,2,order='lex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
2*x + 1
sage: R.<x,y> = PolynomialRing(QQ,2,order='invlex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
y + x + 1
</code></pre>
<p>To find the quotient(s), I'm not sure if there is built-in method in SageMath. But it's not difficult to implement the division algorithm in SageMath, because things like monomial orderings and getting the leading term/coefficient, etc. are already there. There is also a trick to get the quotient(s) by adding extra variables to track what happens in the reduction. It goes something like this:</p>
<pre><code>sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='lex(2),lex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(x + 1, x)
sage: rem.subs({c1:0,c2:0})
2*x + 1
sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='invlex(2),invlex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(1, y + x)
sage: rem.subs({c1:0,c2:0})
y + x + 1
</code></pre>
https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50442#post-id-50442By the way, the quotients are generally non-unique in the sense that [syzygys](https://en.wikipedia.org/wiki/Linear_relation) between the generators can exist.Tue, 31 Mar 2020 06:36:33 -0500https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50442#post-id-50442Comment by rburing for <p>The problem is that in such rings the quotient and remainder are not well-defined in general.</p>
<p>Consider the following example: divide $f = x^2 y + xy^2 + y^2$ by $y^2-1$ in the ring $\mathbb{Q}[x,y]/\langle xy-1\rangle$.</p>
<p>On the one hand, $$f = (x+1)(y^2-1) + 2x + 1 + x(xy-1),$$ so $(x+1)$ is "a quotient" and $2x+1$ is "a remainder" (and $x(xy-1)$ is zero in this ring).</p>
<p>On the other hand, $$f = 1\cdot(y^2-1) + x + y + 1 + (x+y)(xy-1),$$ so $1$ is "a quotient" and $x+y+1$ is "a remainder" (and $(x+y)(xy-1)$ is zero in this ring).</p>
<p>The problem is basically that division in a polynomial ring by <em>several</em> polynomials ($y^2-1$ and $xy-1$ in the example) is a priori not well-defined. For one, the problem is underdetermined. Choosing a monomial ordering and an ordering of the polynomials to be divided by allows you to define an unambiguous (multivariate) division algorithm. Unfortunately its output will depend on the orderings chosen. Furthermore, while a remainder of zero will mean that the input belongs to the ideal generated by the polynomials to be divided by, the converse is not necessarily true. Groebner bases were invented to address these issues. See for example the book <em>Ideals, Varieties, and Algorithms</em> by Cox, Little, and O'Shea. In fact I took the example from there; I just (slightly artificially) rephrased it to be about a quotient ring. If you are only interested in "a remainder" (any), then you can use the division algorithm of Theorem 3 in that book. If you want more, you have to read more. Good luck.</p>
<hr>
<p>SageMath can find the remainder using the multivariate division algorithm:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ,2,order='lex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
2*x + 1
sage: R.<x,y> = PolynomialRing(QQ,2,order='invlex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
y + x + 1
</code></pre>
<p>To find the quotient(s), I'm not sure if there is built-in method in SageMath. But it's not difficult to implement the division algorithm in SageMath, because things like monomial orderings and getting the leading term/coefficient, etc. are already there. There is also a trick to get the quotient(s) by adding extra variables to track what happens in the reduction. It goes something like this:</p>
<pre><code>sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='lex(2),lex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(x + 1, x)
sage: rem.subs({c1:0,c2:0})
2*x + 1
sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='invlex(2),invlex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(1, y + x)
sage: rem.subs({c1:0,c2:0})
y + x + 1
</code></pre>
https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50441#post-id-50441The `reduce` method does division by a list of polynomials when you pass a list; the "problems" that can occur are the ones I mentioned before. A (reduced) Groebner basis is used only when you pass an ideal instead, or a list which happens to be such a basis. In the "trick", the monomial ordering is chosen such that the $c_i$ are smaller than all the original variables, so in the division algorithm (which eliminates leading terms) the $c_i$ will be introduced in favor of the originals. In the result actually arbitrary powers of $c_i$ can appear (just try reducing an expression which is a polynomial in the original generators), so this is more appropriate for a [subalgebra test](https://mathematica.stackexchange.com/a/213090/39559). It is easier just to program the division algorithm.Tue, 31 Mar 2020 06:19:46 -0500https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50441#post-id-50441Comment by hshackle for <p>The problem is that in such rings the quotient and remainder are not well-defined in general.</p>
<p>Consider the following example: divide $f = x^2 y + xy^2 + y^2$ by $y^2-1$ in the ring $\mathbb{Q}[x,y]/\langle xy-1\rangle$.</p>
<p>On the one hand, $$f = (x+1)(y^2-1) + 2x + 1 + x(xy-1),$$ so $(x+1)$ is "a quotient" and $2x+1$ is "a remainder" (and $x(xy-1)$ is zero in this ring).</p>
<p>On the other hand, $$f = 1\cdot(y^2-1) + x + y + 1 + (x+y)(xy-1),$$ so $1$ is "a quotient" and $x+y+1$ is "a remainder" (and $(x+y)(xy-1)$ is zero in this ring).</p>
<p>The problem is basically that division in a polynomial ring by <em>several</em> polynomials ($y^2-1$ and $xy-1$ in the example) is a priori not well-defined. For one, the problem is underdetermined. Choosing a monomial ordering and an ordering of the polynomials to be divided by allows you to define an unambiguous (multivariate) division algorithm. Unfortunately its output will depend on the orderings chosen. Furthermore, while a remainder of zero will mean that the input belongs to the ideal generated by the polynomials to be divided by, the converse is not necessarily true. Groebner bases were invented to address these issues. See for example the book <em>Ideals, Varieties, and Algorithms</em> by Cox, Little, and O'Shea. In fact I took the example from there; I just (slightly artificially) rephrased it to be about a quotient ring. If you are only interested in "a remainder" (any), then you can use the division algorithm of Theorem 3 in that book. If you want more, you have to read more. Good luck.</p>
<hr>
<p>SageMath can find the remainder using the multivariate division algorithm:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ,2,order='lex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
2*x + 1
sage: R.<x,y> = PolynomialRing(QQ,2,order='invlex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
y + x + 1
</code></pre>
<p>To find the quotient(s), I'm not sure if there is built-in method in SageMath. But it's not difficult to implement the division algorithm in SageMath, because things like monomial orderings and getting the leading term/coefficient, etc. are already there. There is also a trick to get the quotient(s) by adding extra variables to track what happens in the reduction. It goes something like this:</p>
<pre><code>sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='lex(2),lex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(x + 1, x)
sage: rem.subs({c1:0,c2:0})
2*x + 1
sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='invlex(2),invlex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(1, y + x)
sage: rem.subs({c1:0,c2:0})
y + x + 1
</code></pre>
https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50440#post-id-50440That's much appreciated, thank you. One final question on the extra variables that you add, just to make sure I'm understanding - the reduce function does the reduction in a reduced Groeber basis, and this procedure should cause problems if the original basis isn't a Groeber basis, correct? It seems that if the original basis isn't a Groebner basis, we get higher powers of c1 and c2 in the remainder (although there's always only one unique power of c1 and c2 involved in the remainder). Taking the coefficients corresponding to these higher powers of c1 and c2 seem to still give sensible answers for the quotients in the cases that I've considered, but I haven't been able to convince myself that this is always the correct thing to do.Mon, 30 Mar 2020 18:00:57 -0500https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50440#post-id-50440Comment by rburing for <p>The problem is that in such rings the quotient and remainder are not well-defined in general.</p>
<p>Consider the following example: divide $f = x^2 y + xy^2 + y^2$ by $y^2-1$ in the ring $\mathbb{Q}[x,y]/\langle xy-1\rangle$.</p>
<p>On the one hand, $$f = (x+1)(y^2-1) + 2x + 1 + x(xy-1),$$ so $(x+1)$ is "a quotient" and $2x+1$ is "a remainder" (and $x(xy-1)$ is zero in this ring).</p>
<p>On the other hand, $$f = 1\cdot(y^2-1) + x + y + 1 + (x+y)(xy-1),$$ so $1$ is "a quotient" and $x+y+1$ is "a remainder" (and $(x+y)(xy-1)$ is zero in this ring).</p>
<p>The problem is basically that division in a polynomial ring by <em>several</em> polynomials ($y^2-1$ and $xy-1$ in the example) is a priori not well-defined. For one, the problem is underdetermined. Choosing a monomial ordering and an ordering of the polynomials to be divided by allows you to define an unambiguous (multivariate) division algorithm. Unfortunately its output will depend on the orderings chosen. Furthermore, while a remainder of zero will mean that the input belongs to the ideal generated by the polynomials to be divided by, the converse is not necessarily true. Groebner bases were invented to address these issues. See for example the book <em>Ideals, Varieties, and Algorithms</em> by Cox, Little, and O'Shea. In fact I took the example from there; I just (slightly artificially) rephrased it to be about a quotient ring. If you are only interested in "a remainder" (any), then you can use the division algorithm of Theorem 3 in that book. If you want more, you have to read more. Good luck.</p>
<hr>
<p>SageMath can find the remainder using the multivariate division algorithm:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ,2,order='lex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
2*x + 1
sage: R.<x,y> = PolynomialRing(QQ,2,order='invlex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
y + x + 1
</code></pre>
<p>To find the quotient(s), I'm not sure if there is built-in method in SageMath. But it's not difficult to implement the division algorithm in SageMath, because things like monomial orderings and getting the leading term/coefficient, etc. are already there. There is also a trick to get the quotient(s) by adding extra variables to track what happens in the reduction. It goes something like this:</p>
<pre><code>sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='lex(2),lex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(x + 1, x)
sage: rem.subs({c1:0,c2:0})
2*x + 1
sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='invlex(2),invlex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(1, y + x)
sage: rem.subs({c1:0,c2:0})
y + x + 1
</code></pre>
https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50436#post-id-50436You're welcome! I added details about the implementation in SageMath.Mon, 30 Mar 2020 05:22:37 -0500https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50436#post-id-50436Comment by hshackle for <p>The problem is that in such rings the quotient and remainder are not well-defined in general.</p>
<p>Consider the following example: divide $f = x^2 y + xy^2 + y^2$ by $y^2-1$ in the ring $\mathbb{Q}[x,y]/\langle xy-1\rangle$.</p>
<p>On the one hand, $$f = (x+1)(y^2-1) + 2x + 1 + x(xy-1),$$ so $(x+1)$ is "a quotient" and $2x+1$ is "a remainder" (and $x(xy-1)$ is zero in this ring).</p>
<p>On the other hand, $$f = 1\cdot(y^2-1) + x + y + 1 + (x+y)(xy-1),$$ so $1$ is "a quotient" and $x+y+1$ is "a remainder" (and $(x+y)(xy-1)$ is zero in this ring).</p>
<p>The problem is basically that division in a polynomial ring by <em>several</em> polynomials ($y^2-1$ and $xy-1$ in the example) is a priori not well-defined. For one, the problem is underdetermined. Choosing a monomial ordering and an ordering of the polynomials to be divided by allows you to define an unambiguous (multivariate) division algorithm. Unfortunately its output will depend on the orderings chosen. Furthermore, while a remainder of zero will mean that the input belongs to the ideal generated by the polynomials to be divided by, the converse is not necessarily true. Groebner bases were invented to address these issues. See for example the book <em>Ideals, Varieties, and Algorithms</em> by Cox, Little, and O'Shea. In fact I took the example from there; I just (slightly artificially) rephrased it to be about a quotient ring. If you are only interested in "a remainder" (any), then you can use the division algorithm of Theorem 3 in that book. If you want more, you have to read more. Good luck.</p>
<hr>
<p>SageMath can find the remainder using the multivariate division algorithm:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ,2,order='lex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
2*x + 1
sage: R.<x,y> = PolynomialRing(QQ,2,order='invlex')
sage: (x^2*y+x*y^2+y^2).reduce([y^2-1,x*y-1])
y + x + 1
</code></pre>
<p>To find the quotient(s), I'm not sure if there is built-in method in SageMath. But it's not difficult to implement the division algorithm in SageMath, because things like monomial orderings and getting the leading term/coefficient, etc. are already there. There is also a trick to get the quotient(s) by adding extra variables to track what happens in the reduction. It goes something like this:</p>
<pre><code>sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='lex(2),lex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(x + 1, x)
sage: rem.subs({c1:0,c2:0})
2*x + 1
sage: R.<x,y,c1,c2> = PolynomialRing(QQ,4,order='invlex(2),invlex(2)')
sage: rem = (x^2*y+x*y^2+y^2).reduce([y^2-1-c1,x*y-1-c2])
sage: rem.coefficient(c1), rem.coefficient(c2)
(1, y + x)
sage: rem.subs({c1:0,c2:0})
y + x + 1
</code></pre>
https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50434#post-id-50434Thanks! This is very helpful. Do you if the division algorithm they reference (or in general, division by several polynomials) is implemented in Sage?Sun, 29 Mar 2020 23:08:02 -0500https://ask.sagemath.org/question/50406/polynomial-division-in-quotient-rings/?comment=50434#post-id-50434