**Title:** Representing Boolean Functions as Polynomials Modulo Composite Integers
**Authors:** David Barrington, Richard Beigel, and Steven Rudich

**Abstract:**
Define the MOD_{m}-*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 0-1
assignments **x** , *F*(**x**) = 0 iff
*P*(**x**) = 0. We obtain the unexpected result that
the MOD_{m}-degree of the OR of *N* variables is
O(*N*^{1/r}), where r is the number of distinct
prime factors of *m*. 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 of *n*
and is one otherwise. We show that the MOD_{m}-degree
of both the MOD_{n} and ¬MOD_{n}
functions is *N*^{Ω(1)} exactly when there is a
prime dividing *n* but not *m*. The
MOD_{m}-degree of the MOD_{m} function
is 1; we show that the MOD_{m}-degree of
¬MOD_{m} is *N*^{Ω(1)} if
*m* 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 PARITYP) have this structure:
MOD_{m}P is closed under complementation and union iff
*m* is a prime power, and MOD_{n}P ⊆
MOD_{m}P iff all primes dividing *n* also divide
*m*.

Download Full Paper