MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Minimum input for GroebnerBasis

  • To: mathgroup at smc.vnet.net
  • Subject: [mg90407] Re: [mg90388] Minimum input for GroebnerBasis
  • From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
  • Date: Tue, 8 Jul 2008 07:48:00 -0400 (EDT)
  • References: <200807080625.CAA18049@smc.vnet.net>

Your question seems to be based on a misunderstanding of what a  
Groebner basis is. A GrobenerBasis is a basis (i.e. a se t of  
generators) for the ideal generated by a set of polynomials and in  
general is not, a subset of the set of polynomials that you started  
from. (If you do not know what an ideal is it will be hard to  
understand the rest of this so I suggest you look up any textbook of  
modern abstract algebra or even simply polynomial algebra.) Only in  
rare cases a subset of the original set of generators is a Groebner  
basis. (Of course there is a trivial way to produce such cases, which  
I describe at the end).

Next, turning to your example: the claim that Q is a Groebner basis  
for the ideal generated by P is false (at least for the default  
Lexicographic Order). A Groebner basis for an ideal is defined a set  
of generators of the ideal with the property that, for any element of  
the ideal, it's leading term (with respect to the given monomial  
order!) is divisible by the leading term of some element of the basis.  
So consider the ideal generated by

  {x + y + 1, 2 x + 2 y + 2, x - y}

Now, the element (x + y + 1)-(x-y) = 2y+1 is in the ideal. It's  
leading term is 2y. Now consider the set Q = {x + y + 1, x - y}. With  
the lexicographic ordering (x comes before y) the leading terms of  
both elements of Q are x. But 2y is not divisible by x. So Q is not a  
GrobenerBasis for this ordering. (It also does not satisfy the so  
called "Buchberger criterion"). On the other hand, {1 + 2 y, 1 + 2 x}  
is a Grobner basis and 2y is divisible by the leading term of 1+2y,  
which is 2y.

What is true is that the set {x + y + 1, x - y} and the set {x + y +  
1, 2 x + 2 y + 2, x - y} generate the same ideal (or if you prefer not  
to mention ideals you can say that they have the corresponding systems  
of equations ahve the same set of solutions). In other words, the set  
{x + y + 1, x - y} is a basis for the ideal generated by {x + y + 1, 2  
x + 2 y + 2, x - y}. A basis, yes, but a Groebner basis, no. This is  
the main point

Next, a few more remarks of a more general nature, which may be  
related to your question. A Groebner basis is defined only for a given  
monomial order. There is no such thing as "the Groebner basis" there  
is only a Groebner basis for some specific order. If you look at the  
options MonomialOrder in Mathematica's GroebnerBasis function you will  
see its default value.

In[3]:= Options[GroebnerBasis, MonomialOrder]
Out[3]= {MonomialOrder -> Lexicographic}

the Lexicographic order is the default. It is not necessarily the best  
order for all purposes (but it is the most suited for using  
elimination).

You can check that in many cases the number of elements in a Groebner  
basis for an ideal with respect to one order will be different form  
the number of elements in a Groebner basis for the same ideal with  
respect to a different monomial order. For example:

  Length[GroebnerBasis[{x y + z - x z, x^2 - z, 2 x^3 - x^2 y z - 1},  
{x, y, z},
    MonomialOrder -> Lexicographic]]
3

Length[GroebnerBasis[{x y + z - x z, x^2 - z, 2 x^3 - x^2 y z - 1},  
{x, y, z},
    MonomialOrder -> DegreeLexicographic]]
4


In general, for a given monomial order a Groebner basis can have any  
finite number of elements, since once you have a Groebner basis for an  
ideal, you can just adjoin to it any element of the ideal and it will  
still be a Groebner basis. But, if you require that a Groebner basis  
be a reduced one, that is, have the property that for any two  
polynomials in the basis no monomial appearing in one of them is a  
multiple of the leading term of the other than such a basis will be  
minimal - that is, if you remove any polynomial from it it will no  
longer be a Groebner basis (with respect to the given monomial order  
of course). In fact, such a reduced Groebner basis is unique if you  
add the requirement that the leading coefficient of each element in  
the Groebner basis is 1. Most computer algebra systems (including  
Mathematica) return a reduced Groebner basis, but not necessarily a  
monic one. So the Groebner basis returned by Mathematica is already a  
minimal one, in other words it has the property that if you remove  
anything from it it will no longer be a Groebner basis.


Andrzej Kozlowski


On 8 Jul 2008, at 15:25, TuesdayShopping wrote:

> Given a finite set of polynomials P in variables belonging to V, we  
> compute the GroebnerBasis G. What is the set of polynomials Q (Q is  
> a subset of P), such that (a) Q produces the same GroebnerBasis G;  
> and, (b) if any element from the set Q is removed, Q will no longer  
> produce G. In other words, Q is the minimum set of polynomials (from  
> P) required, in order to produce the Groebner Basis G. If there are  
> several Q's possible, we will want the one with the smallest number  
> of polynomials in in it. If there are several with the same number,  
> will want the first one we encounter. Question is how do we find Q  
> in Mathematica?
>
> For example, P can be {x + y + 1, 2 x + 2 y + 2, x - y}
>
> GroebnerBasis[{x + y + 1, 2 x + 2 y + 2, x - y}, {x,y}] is {1 + 2 y,  
> 1 + 2 x}
>
> Q is {x + y + 1, x - y}
>



  • Prev by Date: VectorFieldPlot scaling
  • Next by Date: How to show tick labels w/o showi the tick marks?
  • Previous by thread: Minimum input for GroebnerBasis
  • Next by thread: Re: Re: Minimum input for GroebnerBasis