Lower bounds for the polynomial calculus

We show that polynomial calculus proofs (sometimes also called Groebner pro ofs) of the pigeonhole principle PHPnm must have degree at least (n/2) + 1 over any field. This is the first non-trivial lower bound on the degree of polynomial calculus proofs obtained without using unproved complexity assum ptions. We also show that for some modifications of PHPnm, expressible by p olynomials of at most logarithmic degree, our bound can be improved to line ar in the number of variables. Finally, we show that for any Boolean functi on f(n) in n variables, every polynomial calculus proof of the statement "f (n) cannot be computed by any circuit of size t," must have degree Omega(t/ n). Loosely speaking, this means that low degree polynomial calculus proofs do not prove NP not subset of or equal to P/poly.