Representing Boolean functions as polynomials modulo composite numbers
David A. Mix Barrington, Richard Beigel, Steven Rudich · 1992
Define the MOD~-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all O-1 assignments 5, F(o?) = O iff P(~= O.We obtain the unexpected result that the MOD,r,-degree of the OR of N variables is 0(~), where r is the number of distinct prime factors of m.This is optimal in the case of representation by symmetric polynomials.The MOD,, function is O if the number of input ones is a multiple of n and is 1 otherwise.We show that the MOD~-degree of both the MOD. and lMODn functions is N$)(l) exactly when there is a prime dividing n but not m.The MOD~-degree of the MOD~function is 1;we show that the MODrn,-degree of lMODm is NtiflJ if m is not a power of a prime, O(1) otherwise.A corollary is that there exists an oracle relative to which the MODm P classes (such as @P) have this structure: MODm P is closed under complement and union iff m is a prime power, and MOD.P is a subset of MODmP iff all primes dividing n also divide m.