Representing Boolean functions as polynomials modulo composite numbers

Abstract

Define the MOD _m -degree of a boolean functionF to be the smallest degree of any polynomialP, over the ring of integers modulom, such that for all 0–1 assignments$\vec x$,$F(\vec x) = 0$ iff$P(\vec x) = 0$. We obtain the unexpected result that the MOD _m -degree of the OR ofN variables is$O(\sqrt[\tau ]{N})$, wherer is the number of distinct prime factors ofm. This is optimal in the case of representation by symmetric polynomials. The MOD _n function is 0 if the number of input ones is a multiple ofn and is one otherwise. We show that the MOD _m -degree of both the MOD _n and$\neg MOD_n$ functions isN ^Ω(1) exactly when there is a prime dividingn but notm. The MOD _m -degree of the MOD _m function is 1; we show that the MOD _m -degree of$\neg MOD_m$ isN ^Ω(1) ifm is not a power of a prime,O(1) otherwise. A corollary is that there exists an oracle relative to which the MOD _m P classes (such as ⊕P) have this structure: MOD _m P is closed under complementation and union iffm is a prime power, and MOD _n P is a subset of MOD _m P iff all primes dividingn also dividem.