Lower bounds for the polynomial calculus and the Grobner basis algorithm

Razborov (1996) recently proved that polynomial calculus proofs of the pige onhole principle PHPnm must have degree at least [n/2] + 1 over any field. We present a simplified proof of the same result. Furthermore, we show a matching upper bound on polynomial calculus proofs o f the pigeonhole principle for any field of sufficiently large characterist ic, and an [n/2] + 1 lower bound for any subset sum problem over the field of reals. We show that these degree lower bounds also translate into lower bounds on the number of monomials in any polynomial calculus proof, and hence on the running time of most implementations of the Grobner basis algorithm.