Ask Your Question
1

Show the polynomials in the Groebner Basis as they are found

asked 2012-02-29 09:08:42 -0500

process91 gravatar image

updated 2012-02-29 15:35:50 -0500

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, 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 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?

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
1

answered 2012-02-29 22:13:00 -0500

Simon King gravatar image

After 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.

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.

edit flag offensive delete link more

Comments

Thanks, that is useful. Unfortunately the radicalMemberShip function uses RAM even faster than the groebner function does, but that's my problem to solve.

process91 gravatar imageprocess91 ( 2012-03-01 03:52:09 -0500 )edit
1

answered 2012-02-29 09:28:54 -0500

Simon King gravatar image

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.

edit flag offensive delete link more

Comments

Even 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.

Volker Braun gravatar imageVolker Braun ( 2012-02-29 09:49:39 -0500 )edit

I 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.

process91 gravatar imageprocess91 ( 2012-02-29 15:42:42 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2012-02-29 09:08:42 -0500

Seen: 414 times

Last updated: Feb 29 '12