Lower bounds on Hilbert's Nullstellensatz and propositional proofs

The so called weak form of the Hilbert's Nullstellensatz says that a system of algebraic equations over a field, Q i (¯x) = 0, does not have a solution in the algebraic closure iff 1 is in the ideal generated by the polynomials Q i (¯x). We shall prove a lower bound on the degrees of polynomials P i (¯x) such that P i P i (¯x)Q i (¯x) = 1. This result has the following application. The modular counting principle states that no finite set whose cardinality is not divisible by q can be partitioned into q-element classes. For each fixed cardinality N , this principle can be expressed as a propositional formula Count N q (x e ; : : :) with underlying variables x e , where e ranges over q- element subsets of N . Ajtai [4] proved recently that, whenever p; q are two different primes, the propositional formulas Count qn+1 q do not have polynomial size, constant-depth Frege proofs from substitution instances of Count m p , m 6j 0 (mod p). We give a new proof of this theorem based on t..