ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 03 Apr 2016 05:07:21 -0500How to implement the multivariable division algorithm without passing to Grobner bases?http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/ Hi,
I'm new to Sage, and I'm wondering how to implement the multivariable division algorithm in Sage. I pulled up the "Multivariate Polynomials via libSINGULAR" page of the Sage Reference Manual v7.1, but it wasn't helpful.
What I'm wanting is a generalization of the quo_rem command that can take in more than one argument on the right and follows the division algorithm with respect to a fixed monomial ordering and the order that the polynomials are entered in.
Is there any set of commands that does that for me? If so, would you please include the code, say for the following example?
> Divide the polynomial y*x^2 + x*y^2 +
> y^2 by xy-1 and y2 -1 (in that order)
> using the lexicographic ordering with
> x>y. I would like to process more
> complicated examples, perhaps with
> that order and dividing by 8 things at
> once rather than 2.
I've learned about the p.mod(I) and p.reduce(I) commands where p is a polynomial and I is an ideal. The problem with those is that they seem to pass to a Grobner basis for I to get a "canonical" remainder rather than the remainder we'd get from the given order of the polynomials, as I tested switching the order of the polynomials in defining an ideal I and it did not change my answer for p.mod(I) or p.reduce(I).
Thanks!Thu, 31 Mar 2016 14:00:13 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/Answer by B r u n o for <p>Hi,
I'm new to Sage, and I'm wondering how to implement the multivariable division algorithm in Sage. I pulled up the "Multivariate Polynomials via libSINGULAR" page of the Sage Reference Manual v7.1, but it wasn't helpful.
What I'm wanting is a generalization of the quo_rem command that can take in more than one argument on the right and follows the division algorithm with respect to a fixed monomial ordering and the order that the polynomials are entered in.
Is there any set of commands that does that for me? If so, would you please include the code, say for the following example?</p>
<blockquote>
<p>Divide the polynomial y<em>x^2 + x</em>y^2 +
y^2 by xy-1 and y2 -1 (in that order)
using the lexicographic ordering with
x>y. I would like to process more
complicated examples, perhaps with
that order and dividing by 8 things at
once rather than 2.</p>
</blockquote>
<p>I've learned about the p.mod(I) and p.reduce(I) commands where p is a polynomial and I is an ideal. The problem with those is that they seem to pass to a Grobner basis for I to get a "canonical" remainder rather than the remainder we'd get from the given order of the polynomials, as I tested switching the order of the polynomials in defining an ideal I and it did not change my answer for p.mod(I) or p.reduce(I).</p>
<p>Thanks!</p>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?answer=32937#post-id-32937 It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:
sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
Now if you want a more general function, you can implement it as follows:
sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
You may also want to keep the quotients:
sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
Fri, 01 Apr 2016 04:29:10 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?answer=32937#post-id-32937Comment by B r u n o for <p>It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
</code></pre>
<p>Now if you want a more general function, you can implement it as follows:</p>
<pre><code>sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
</code></pre>
<p>You may also want to keep the quotients:</p>
<pre><code>sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
</code></pre>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32973#post-id-32973I do not understand your question about `L`. Note that Python is dynamically typed, but its variables are untyped: This means that the functions I defined could be *in principle* applied to variables `p` and `L` of any type. For instance, `p` could be an integer and `L` a list of integers, it would work. It works as soon as what appears in the function is defined for the `p` and the `L` you provide. In `list_quo_rem` for instance, you need that `p` has a method `quo_rem`, that `L` is iterable (that is, Python understand `for q in L`), and that Python understands `p.quo_rem(q)` for `q` in `L`. Even though it wouldn't make much sense, you could apply the function with `p` an integer, and `L=GF(17).list_of_elements_of_multiplicative_group()` (that is the list of nonzero elements of `GF(17)`).Sun, 03 Apr 2016 05:07:21 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32973#post-id-32973Comment by rmg512 for <p>It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
</code></pre>
<p>Now if you want a more general function, you can implement it as follows:</p>
<pre><code>sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
</code></pre>
<p>You may also want to keep the quotients:</p>
<pre><code>sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
</code></pre>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32965#post-id-32965Also, for what it's worth, this is the problem I'm tackling:
Take the 3-adic valuation on Q and extend it to a discrete valuation v on Q(x) by assigning the value v(x)=1/2, and then extend that by setting v(x^2+1)=3, where we define the value of a polynomial f(x) by using the decomposition f(x)=\sum a_i(x)(x^2+1)^i where each a_i(x) is of degree less than 2, which is unique and therefore makes the valuation work. Do the same in the variable y and the polynomial y^3+y+1 to get a discrete valuation w. My research question: what discrete valuations are there that extend both of these valuations v and w to a discrete valuation on Q(x,y)? Is there a canonical choice? To do this, I'm needing to break up any polynomial f(x,y) as a sum of a_{ij}(x,y)(x^2+1)^i(y^3+y+1)^j, not written uniquely.Sat, 02 Apr 2016 19:06:35 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32965#post-id-32965Comment by rmg512 for <p>It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
</code></pre>
<p>Now if you want a more general function, you can implement it as follows:</p>
<pre><code>sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
</code></pre>
<p>You may also want to keep the quotients:</p>
<pre><code>sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
</code></pre>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32964#post-id-32964Thanks, Bruno!
A question about the things you've defined: you're defining these things for L an arbitrary list, right? How does one set this code up so that your definitions of list_quo_rem and remainder recognize that L is an arbitrary list?Sat, 02 Apr 2016 18:57:47 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32964#post-id-32964Comment by B r u n o for <p>It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
</code></pre>
<p>Now if you want a more general function, you can implement it as follows:</p>
<pre><code>sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
</code></pre>
<p>You may also want to keep the quotients:</p>
<pre><code>sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
</code></pre>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32959#post-id-32959You can use the permutation groups. Suppose you have a list `L` of polynomials (which can be `I.gens()` for some ideal), then you can do the following:
sage: S = SymmetricGroup(len(L))
sage: for s in S: # = for each permutation of the elements
....: print list_quo_rem(p, s(L))Sat, 02 Apr 2016 08:14:58 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32959#post-id-32959Comment by rmg512 for <p>It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
</code></pre>
<p>Now if you want a more general function, you can implement it as follows:</p>
<pre><code>sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
</code></pre>
<p>You may also want to keep the quotients:</p>
<pre><code>sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
</code></pre>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32948#post-id-32948As a corollary question: would you happen to know how I could get all possible remainders from all possible orders with one command? If I'm dividing 5 or 6 things at once, iterating the program you've written to get all possible remainders isn't very practical to type out. It looks like I might need to do that to test the examples I've come up with to test my conjecture. Thanks!Fri, 01 Apr 2016 14:27:49 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32948#post-id-32948Comment by rmg512 for <p>It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
</code></pre>
<p>Now if you want a more general function, you can implement it as follows:</p>
<pre><code>sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
</code></pre>
<p>You may also want to keep the quotients:</p>
<pre><code>sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
</code></pre>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32947#post-id-32947Great! That makes sense. Thanks again!Fri, 01 Apr 2016 14:03:24 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32947#post-id-32947Comment by B r u n o for <p>It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
</code></pre>
<p>Now if you want a more general function, you can implement it as follows:</p>
<pre><code>sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
</code></pre>
<p>You may also want to keep the quotients:</p>
<pre><code>sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
</code></pre>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32946#post-id-32946The object `L` in my code is any [iterable](https://docs.python.org/2/glossary.html#term-iterable), a list for instance. If you work with an ideal `I`, `I.gens()` is such an iterable so you can call `remainder(p, I.gens())` for instance.Fri, 01 Apr 2016 13:29:22 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32946#post-id-32946Comment by rmg512 for <p>It seems that there is no method readily available for what you want. Though, it is not too hard to write it. For instance, if you simply want the remainder in this long division, you can act as follows where you see that the order matters:</p>
<pre><code>sage: R.<x,y> = PolynomialRing(QQ, order="lex")
sage: p = x*y^2+x*x*y+y**2
sage: q = x*y-1
sage: r = y^2-1
sage: p % q % r
x + y + 1
sage: p % r % q
2*x + 1
</code></pre>
<p>Now if you want a more general function, you can implement it as follows:</p>
<pre><code>sage: def remainder(p, L):
....: r = p
....: for q in L:
....: r = r % q
....: return r
....:
sage: remainder(p, [q, r])
x + y + 1
sage: remainder(p, [r, q])
2*x + 1
</code></pre>
<p>You may also want to keep the quotients:</p>
<pre><code>sage: def list_quo_rem(p, L):
....: r = p
....: quo = []
....: for q in L:
....: Q, R = r.quo_rem(q)
....: quo.append(Q)
....: r = R
....: return (quo, r)
....:
sage: list_quo_rem(p, [q, r])
([x + y, 1], x + y + 1)
sage: list_quo_rem(p, [r, q])
([x + 1, x], 2*x + 1)
</code></pre>
http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32944#post-id-32944Thank you so much! I wish I could at least award you karma for this, but it seems I can't since I don't have enough myself.
One more question: How are we defining the object L? Is it the ideal generated by the pair q and r, is it an ordered list, or is it something else?
Thanks again!Fri, 01 Apr 2016 11:00:31 -0500http://ask.sagemath.org/question/32932/how-to-implement-the-multivariable-division-algorithm-without-passing-to-grobner-bases/?comment=32944#post-id-32944