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:n 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.