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.Thu, 01 Mar 2012 03:52:09 -0600Show the polynomials in the Groebner Basis as they are foundhttp://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/This is more a question about singular, since that is what Sage uses to computer the Groebner Basis. In Singular, you can use option(prot) and then, upon using the groebner function of your choice, you will see verbose output. From the [Singular manual](http://www.singular.uni-kl.de/Manual/latest/sing_330.htm#SEC370), we are told that when "s" is printed in the verbose output, a new element of the standard basis has been found. It is sometimes enough, and in particular very useful for my needs, to know that a certain polynomial is in the groebner basis.
I am working with an overdetermined system of polynomials for which the full groebner basis is too difficult to compute, however it would be valuable for me to be able to print out the groebner basis elements as they are found so that I may know if a particular polynomial is in the groebner basis. Is there any way to do this?
----------
My question is above, but more details specifically related to my problem are below, which may be useful in providing an alternate answer.
The problem is as follows: I have a system of (not necessarily homogeneous) multivariate polynomials $f_1(x_1,\dots,x_n)=0,\dots f_m(x_1,\dots,x_n)=0$. I would like to prove that a few of the $x_i$ must be equal to zero. I was able to uncomment lines 240, 241, and 242 in [this toy implementation library of Faugere's f5 algorithm for Singular](http://www.math.usm.edu/perry/Research/f5_library.lib) and remove the "lead" function around the to-be-printed output on line 241. After just a couple of seconds while running this command, $x_7^5$ was printed out as a member of the basis.
This would seem to imply that $x_7$ must equal zero. The toy library is useful in this regard, since it was able to be modified to print out the members of the basis as they were discovered, however it is still a toy implementation and is not as efficient as slimgb, for instance. My question is, how can I get this same behavior from slimgb?Wed, 29 Feb 2012 09:08:42 -0600http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/Answer by Simon King for <p>This is more a question about singular, since that is what Sage uses to computer the Groebner Basis. In Singular, you can use option(prot) and then, upon using the groebner function of your choice, you will see verbose output. From the <a href="http://www.singular.uni-kl.de/Manual/latest/sing_330.htm#SEC370">Singular manual</a>, we are told that when "s" is printed in the verbose output, a new element of the standard basis has been found. It is sometimes enough, and in particular very useful for my needs, to know that a certain polynomial is in the groebner basis.</p>
<p>I am working with an overdetermined system of polynomials for which the full groebner basis is too difficult to compute, however it would be valuable for me to be able to print out the groebner basis elements as they are found so that I may know if a particular polynomial is in the groebner basis. Is there any way to do this?</p>
<hr/>
<p>My question is above, but more details specifically related to my problem are below, which may be useful in providing an alternate answer.</p>
<p>The problem is as follows: I have a system of (not necessarily homogeneous) multivariate polynomials $f_1(x_1,\dots,x_n)=0,\dots f_m(x_1,\dots,x_n)=0$. I would like to prove that a few of the $x_i$ must be equal to zero. I was able to uncomment lines 240, 241, and 242 in <a href="http://www.math.usm.edu/perry/Research/f5_library.lib">this toy implementation library of Faugere's f5 algorithm for Singular</a> and remove the "lead" function around the to-be-printed output on line 241. After just a couple of seconds while running this command, $x_7^5$ was printed out as a member of the basis.</p>
<p>This would seem to imply that $x_7$ must equal zero. The toy library is useful in this regard, since it was able to be modified to print out the members of the basis as they were discovered, however it is still a toy implementation and is not as efficient as slimgb, for instance. My question is, how can I get this same behavior from slimgb?</p>
http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?answer=13318#post-id-13318After you reformulated your question, it seems to me that what you want to do is test "radical membership" of some of the `x_i`. That's to say: You want to know whether there is some integer `n` such that `x_i^n` belongs to the ideal.
Actually, the Gröbner basis of an ideal is *not* enough to solve that radical membership! In Singular, radical membership can be tested as explained [here](http://www.singular.uni-kl.de/Manual/latest/sing_1824.htm#SEC1900).
That functionality is provided by some library of Singular. If you want to do the same in Sage, without using a Singular sub-process, you can meanwhile do as follows:
First, we define some ideal, and show that the Gröbner basis does not immediately show that some power of `y` vanishes:
sage: P.<x,y> = QQ[]
sage: I = P*[x*y^3+y^5, x*y^6]
sage: I.groebner_basis()
[x^3*y^3, x^2*y^4, y^5 + x*y^3]
Next, we import some stuff that is needed to benefit from Singular library functions in Sage, load the library, define the Singular function, and test for radical membership of `y` in `I`:
sage: from sage.libs.singular import lib, singular_function
sage: lib("tropical.lib")
sage: rad_mem = singular_function("radicalMemberShip")
sage: rad_mem(y,I)
skipping text from `parameter`
1
I don't know where the text "skipping text ..." comes from - anyway, the answer of the function is `1`, and that means that indeed some power of `y` belongs to `I`. Let us verify it:
sage: y in I
False
sage: y^2 in I
False
sage: y^3 in I
False
sage: y^7 in I
False
sage: y^8 in I
True
However, no power of `x` belongs to `I`:
sage: rad_mem(x,I)
0
I hope this is enough to solve your problem. In particular, I believe that looking at some protocol output of slimgb would certainly not solve your problem: As demonstrated above, the Gröbner basis does, in general, not directly provide the radical membership information for variables).
Also, as much as I know, there is no option to make slimgb or std or another Singular function make print the polynomials being considered.Wed, 29 Feb 2012 22:13:00 -0600http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?answer=13318#post-id-13318Comment by process91 for <p>After you reformulated your question, it seems to me that what you want to do is test "radical membership" of some of the <code>x_i</code>. That's to say: You want to know whether there is some integer <code>n</code> such that <code>x_i^n</code> belongs to the ideal.</p>
<p>Actually, the Gröbner basis of an ideal is <em>not</em> enough to solve that radical membership! In Singular, radical membership can be tested as explained <a href="http://www.singular.uni-kl.de/Manual/latest/sing_1824.htm#SEC1900">here</a>.</p>
<p>That functionality is provided by some library of Singular. If you want to do the same in Sage, without using a Singular sub-process, you can meanwhile do as follows:</p>
<p>First, we define some ideal, and show that the Gröbner basis does not immediately show that some power of <code>y</code> vanishes:</p>
<pre><code>sage: P.<x,y> = QQ[]
sage: I = P*[x*y^3+y^5, x*y^6]
sage: I.groebner_basis()
[x^3*y^3, x^2*y^4, y^5 + x*y^3]
</code></pre>
<p>Next, we import some stuff that is needed to benefit from Singular library functions in Sage, load the library, define the Singular function, and test for radical membership of <code>y</code> in <code>I</code>:</p>
<pre><code>sage: from sage.libs.singular import lib, singular_function
sage: lib("tropical.lib")
sage: rad_mem = singular_function("radicalMemberShip")
sage: rad_mem(y,I)
skipping text from `parameter`
1
</code></pre>
<p>I don't know where the text "skipping text ..." comes from - anyway, the answer of the function is <code>1</code>, and that means that indeed some power of <code>y</code> belongs to <code>I</code>. Let us verify it:</p>
<pre><code>sage: y in I
False
sage: y^2 in I
False
sage: y^3 in I
False
sage: y^7 in I
False
sage: y^8 in I
True
</code></pre>
<p>However, no power of <code>x</code> belongs to <code>I</code>:</p>
<pre><code>sage: rad_mem(x,I)
0
</code></pre>
<p>I hope this is enough to solve your problem. In particular, I believe that looking at some protocol output of slimgb would certainly not solve your problem: As demonstrated above, the Gröbner basis does, in general, not directly provide the radical membership information for variables).</p>
<p>Also, as much as I know, there is no option to make slimgb or std or another Singular function make print the polynomials being considered.</p>
http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?comment=20190#post-id-20190Thanks, that is useful. Unfortunately the radicalMemberShip function uses RAM even faster than the groebner function does, but that's my problem to solve.Thu, 01 Mar 2012 03:52:09 -0600http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?comment=20190#post-id-20190Answer by Simon King for <p>This is more a question about singular, since that is what Sage uses to computer the Groebner Basis. In Singular, you can use option(prot) and then, upon using the groebner function of your choice, you will see verbose output. From the <a href="http://www.singular.uni-kl.de/Manual/latest/sing_330.htm#SEC370">Singular manual</a>, we are told that when "s" is printed in the verbose output, a new element of the standard basis has been found. It is sometimes enough, and in particular very useful for my needs, to know that a certain polynomial is in the groebner basis.</p>
<p>I am working with an overdetermined system of polynomials for which the full groebner basis is too difficult to compute, however it would be valuable for me to be able to print out the groebner basis elements as they are found so that I may know if a particular polynomial is in the groebner basis. Is there any way to do this?</p>
<hr/>
<p>My question is above, but more details specifically related to my problem are below, which may be useful in providing an alternate answer.</p>
<p>The problem is as follows: I have a system of (not necessarily homogeneous) multivariate polynomials $f_1(x_1,\dots,x_n)=0,\dots f_m(x_1,\dots,x_n)=0$. I would like to prove that a few of the $x_i$ must be equal to zero. I was able to uncomment lines 240, 241, and 242 in <a href="http://www.math.usm.edu/perry/Research/f5_library.lib">this toy implementation library of Faugere's f5 algorithm for Singular</a> and remove the "lead" function around the to-be-printed output on line 241. After just a couple of seconds while running this command, $x_7^5$ was printed out as a member of the basis.</p>
<p>This would seem to imply that $x_7$ must equal zero. The toy library is useful in this regard, since it was able to be modified to print out the members of the basis as they were discovered, however it is still a toy implementation and is not as efficient as slimgb, for instance. My question is, how can I get this same behavior from slimgb?</p>
http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?answer=13317#post-id-13317Do you know the degree of the polynomial you are looking for? Then it might make sense to compute a truncated Gröbner basis out to that degree -- in particular if your polynomial system happens to be homogeneous.Wed, 29 Feb 2012 09:28:54 -0600http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?answer=13317#post-id-13317Comment by process91 for <p>Do you know the degree of the polynomial you are looking for? Then it might make sense to compute a truncated Gröbner basis out to that degree -- in particular if your polynomial system happens to be homogeneous.</p>
http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?comment=20194#post-id-20194I added more information about my problem to my original question. I'm not sure this will totally address my problem, but I will try it now.Wed, 29 Feb 2012 15:42:42 -0600http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?comment=20194#post-id-20194Comment by Volker Braun for <p>Do you know the degree of the polynomial you are looking for? Then it might make sense to compute a truncated Gröbner basis out to that degree -- in particular if your polynomial system happens to be homogeneous.</p>
http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?comment=20196#post-id-20196Even if the ideal not homogeneous it might be useful to compute the truncated Groebner Basis in this case. Especially if you already suspect that your polynomial is in the ideal.Wed, 29 Feb 2012 09:49:39 -0600http://ask.sagemath.org/question/8759/show-the-polynomials-in-the-groebner-basis-as-they-are-found/?comment=20196#post-id-20196