About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
The independence of the modulo p counting principles
Abstract
If p is a prime and n is a positive integer then the mod p counting principle for n (CPp>n) is the following statement: There are no two equivalence relations $ and Φ on Ψ set A of size n with the following properties: (a) each class of Φ contains exactly p elements, and (b) each class of with one exception contains exactly p elements, the exceptional class contains 1 element. We will always assume that p is constant and n is suficiently large. If we associate Boolean vari-Ables xa,b> ya,b with all pairs formed from the elements of A then CPp>n can be expressed as a Boolean formula of constant depth and polynomial size. (We may think that aΦb iff x<a,b = 1 aΨb iff Va,b = 1.) This formula is a tautology. We show that if p. q are distinct primes then there is no constant depth polynomial (in n) size Frege proof of CPpn even if we are allowed to use CPqn as an axiom schema. (We get the axiom schema from CPq by replacing in every possible way the variables in CPn by constant depth polynomial size fromulae formed from the variables used in the Frege proof. This schema says the if we define the partitions Φ,Ψ in an arbi-Trary but constant depth poly-size way they cannot contradict CPq<n). The new part of the proof (compared to earlier results about the Pigoenhole and Parity Principles) is the reduction of the problem to a theorem about the representations of the symmetric group over the field with p elements (or as we will formulate below a theorem about symmetric systems of linear equations), and the proof of this theorem.