Premium
Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
Author(s) -
Beame Paul,
Impagliazzo Russell,
Krajíček Jan,
Pitassi Toniann,
Pudlák Pavel
Publication year - 1996
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/s3-73.1.1
Subject(s) - mathematics , cardinality (data modeling) , upper and lower bounds , combinatorics , algebraic number , discrete mathematics , polynomial , mathematical proof , element (criminal law) , proof complexity , mathematical analysis , geometry , computer science , data mining , political science , law
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