Re: Re: Minimum input for GroebnerBasis
- To: mathgroup at smc.vnet.net
- Subject: [mg90439] Re: [mg90407] Re: [mg90388] Minimum input for GroebnerBasis
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Wed, 9 Jul 2008 04:55:22 -0400 (EDT)
- References: <885117.62449.qm@web46201.mail.sp1.yahoo.com>
If I understand you correctly, given a set of ideal generators, you
want to find a minimal subset which generates the same ideal. Is that right?
Just of hand, I can't think of anything simpler than computing the
Grobner bases (with respect to Lex) of all finite subsets, which
obviously has a very high complexity. But why do you want to do this?
If you are intending to use this for some other purpose the chances
are that this is not the right way to go about the problem. Note that
an ideal can have a basis that is unshortenable, in the sense that no
proper subset of the basis generates yet at the same time there may be
a different basis for the same ideal with fewer elements. Here is an
example.
Let P= {x y (y-1),x y (x-1), x (y-1) (x-1)}. It is easy to prove that
no subset of this generates, since each of the generators defines a
union of three lines, and the variety (set of zeros) corresponding to
P is the intersection of the three sets of three lines. You can easily
see that this is always going to be smaller than the intersection of
less then three of these sets. But
GroebnerBasis[P, {x, y, z}]
{x*y^2 - x*y, x^2 - x}
which has only two generators.
Andrzej Kozlowski
On 9 Jul 2008, at 00:48, Tuesday Shopping wrote:
> Thanks for the input Andrzej. I should have been more precise in
> posing my question.
>
> In the example in my post I did not claim that Q is the
> GroebnerBasis for P. I claimed that (a) Q is a subset of P and (b)
> that P and Q produce the same GroebnerBasis {1 + 2 y, 1 + 2 x}.
> which is clearly not a subset of P.
>
> In other words, P and Q generate the same Ideal; and that Ideal has
> a GroebnerBasis G which is equal to {1 + 2 y, 1 + 2 x}
>
> When I say "the GroebnerBasis" (not "a GroebnerBasis") I am implying
> a reduced GroebnerBasis for Lexicographic ordering, which are
> default in Mathematica 6. Since, for a given Ideal, for a given
> monomial ordering, the reduced GroebnerBasis is unique, I used the
> term "the GroebnerBasis", instead of "a GroebnerBasis".
>
> To pose my question in terms of Ideals, what I am aiming to do is,
> find the minimum set of polynomials (subset of P) that generate the
> same Ideal.
>
> To put in your own words, in your post, you mentioned: "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". You did notice that the first
> set in this statement has fewer elements than the second. Then, my
> quest is to make the first set have the smallest number of elements.
>
> To pose the question in terms of generators, the question becomes
> "given a generator P, that generates Ideal I, how do I get a
> generator Q such that (a) Q is a subset of P (b) Q generates the I
> (c) there is no other generator R (R is a subset of P), that has
> fewer elements than Q.
>
> Once again thanks for your input and I will appreciate if you could
> comment on some possibilities in solving my problem. Currently I
> have an algorithm that is rather inefficient:
>
> Answer= {} // empty set
> G1= GroebnerBasis(P).
> Q = P
> loop:
> Q = Q after removing element F that has not been tried so far.
> G = GroebnerBasis(Q)
> if(G1 is not equal to G) {add F to Answer; add F back to Q}
> goto loop if there are more elements in Q that have not been tried.
>
> Even this alorithm gives a set that eliminates redundant input, but
> it is not the true minimum. It depends on in what order we select an
> element for removal.
>
>
>> 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}
>>
>
> --- On Tue, 7/8/08, Andrzej Kozlowski <akoz at mimuw.edu.pl> wrote:
> From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
> Subject: [mg90407] Re: [mg90388] Minimum input for GroebnerBasis
> To: mathgroup at smc.vnet.net
> Date: Tuesday, July 8, 2008, 11:48 AM
>
> 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}
>>
>
>
>
>