TR97-042 Authors: Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Publication: 22nd September 1997 15:04

Downloads: 2106

Keywords:

Razborov~\cite{Razborov96} recently proved that polynomial

calculus proofs of the pigeonhole principle $PHP_n^m$ must have

degree at least $\ceiling{n/2}+1$ over any field. We present a

simplified proof of the same result. The main

idea of our proof is the same as in the original proof

of Razborov: we want to describe explicitly the vector space of

the polynomials derivable in a low degree polynomial calculus

refutation of the pigeonhole principle, and the description uses

the pigeon dance as before. We are able to avoid some of the

technical machinery, due to the simple counting argument which

shows that the set of polynomials, which generates the vector

space of consequences, forms its basis.

Furthermore we show a matching upper bound on the polynomial

calculus proofs of the pigeonhole principle for any field of

sufficiently large characteristic,

and an $\ceiling{n/2}+1$ lower bound for any subset sum problem

over the field of reals.