Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs

The so‐called weak form of 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 if and only if 1 is in theideal generated by the polynomialsQ i ( x ¯ ) . We shall prove a lower bound on the degrees of polynomialsP i ( x ¯ )such that∑ iP 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 CountCount q N ( 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 CountCount q q n + 1do not have polynomial size, constant‐depth Frege proofs from substitution instances of CountCount p m , where m ≢ 0 (mod p ). We give a new proof of this theorem based on the lower bound for Hilbert's Nullstellensatz. Furthermore our technique enables us to extend the independence results for counting principles to composite numbers p and q . This improved lower bound together with new upper bounds yield an exact characterization of when Count q can be proved efficiently from Count p , for all values of p and q