Dimension-dependent bounds for Grobner bases of polynomial ideals

Given a basis F of a polynomial ideal I in K[x(1),...,x(n)] with degrees deg(F) <= d, the degrees of the reduced Grobner basis G w.r.t. any admissible monomial ordering are known to be double exponential in the number of indeterminates in the worst case, i.e. deg(G) = d(2 theta(n)). This was established in Mayr and Meyer (1982) and Dube (1990). We modify both constructions in order to give worst case bounds depending on the ideal dimension proving that deg(G) = d(n theta(1)2 theta(r)) for r-dimensional ideals (in the worst case). (C) 2011 Elsevier Ltd. All rights reserved.