Read-only forum archive

the largest degree of variable when computing Groebner Basis

the largest degree of variable when computing Groebner Basis

gepo · Fri Oct 15, 2010 6:53 am

When I compute some Groebner Basis, I found the degree of some variables went up very quickly.
Then I want to know whether there is a largest degree of variables when computing Groebner Basis.

Thanks a lot.
Gepo

Re: the largest degree of variable when computing Groebner Basis

etienne · Fri Oct 15, 2010 11:46 am

This is fact of Groebner basis, If you look in the book of Cox Little O'shea "ideals, varietes and algo", they are some examples where the degree become very big with some order and very small with an other.
I think that it is an open problem to bound the degree of the elements of a groebner basis.
Etienne
PS I am not a specialist of that topic, I just read the book above


gepo wrote:
When I compute some Groebner Basis, I found the degree of some variables went up very quickly.
Then I want to know whether there is a largest degree of variables when computing Groebner Basis.

Thanks a lot.
Gepo

Re: the largest degree of variable when computing Groebner Basis

gepo · Fri Oct 15, 2010 7:09 pm

I am also reading the book. But it seems it did not mention too much on this topic.
Hope someone could give us some clues.

etienne wrote:
This is fact of Groebner basis, If you look in the book of Cox Little O'shea "ideals, varietes and algo", they are some examples where the degree become very big with some order and very small with an other.
I think that it is an open problem to bound the degree of the elements of a groebner basis.
Etienne
PS I am not a specialist of that topic, I just read the book above


gepo wrote:
When I compute some Groebner Basis, I found the degree of some variables went up very quickly.
Then I want to know whether there is a largest degree of variables when computing Groebner Basis.

Thanks a lot.
Gepo

Re: the largest degree of variable when computing Groebner Basis

John Perry · Mon Oct 18, 2010 1:21 pm

gepo wrote:
When I compute some Groebner Basis, I found the degree of some variables went up very quickly.
Then I want to know whether there is a largest degree of variables when computing Groebner Basis.

Thanks a lot.
Gepo


The answer (which I don't know) depends on the term ordering. What ordering are you using? Using dp would keep the degree lower than using lp.

Re: the largest degree of variable when computing Groebner Basis

gepo · Fri Oct 22, 2010 11:27 pm

I tried both.
The thing I want to know is whether there is a theoretical bound for the degree.

Thanks
Gepo
John Perry wrote:
gepo wrote:
When I compute some Groebner Basis, I found the degree of some variables went up very quickly.
Then I want to know whether there is a largest degree of variables when computing Groebner Basis.

Thanks a lot.
Gepo


The answer (which I don't know) depends on the term ordering. What ordering are you using? Using dp would keep the degree lower than using lp.

Re: the largest degree of variable when computing Groebner Basis

John Perry · Sat Oct 23, 2010 9:35 pm

gepo wrote:
I tried both.
The thing I want to know is whether there is a theoretical bound for the degree.


A paper written by Bardet, Faugere, and Salvy might be helpful. It's titled, "Asymptotic Expansion of the Degree of Regularity for Semi-Regular Sequences of Equations". They repeat an precise, sharp formula for regular systems that dates back to Lazard (1983). You can download it from Faugere's web page; they seem to have presented it at MEGA 2005, but I don't find any reference to a journal publication.

Older than this is a paper by Mayr & Meyer, titled (I think) "The Complexity of the Word Problem for Commutative Semigroups and Polynomial Ideals".

There's also a paper by Y. N. Lakshman, "On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal".

Hope at least one of these helps.

Re: the largest degree of variable when computing Groebner Basis

daniel · Fri Dec 03, 2010 2:24 pm

In Dube's paper "The structure of polynomial ideals and Gröbner bases" [MR Number mr=1053942]there is a bound on the degree of the polynomials in a groebner basis. It depends on the degree d of the polynomials one starts with and on the number n of variables in the polynomial ring. Then for every monomial ordering there is a Groebner basis of degree less or equal to 2((d^2/2)+d)^{2^{n-1}}.
If I recall correctly this bound does not even need the characteristic of the ground field to be zero (unlike the previous bound by Moeller Mora Bayer Giusti...).

This bound is also mentioned (without reference i think) in the book "Modern Computer Algebra" - Gerhard, Gathen ( around p.590 ?)