** Next:** The Lower Bound
** Up:** Superpolynomial Size Set-Systems with
** Previous:** Introduction

Let
be a Boolean function and let *m* be a
positive integer. *Barrington*, *Beigel* and *Rudich*
[2] gave the following definition:

**Definition 2.1**
The polynomial

*P* with integer coefficients

*weakly represents*
the Boolean function

*f* modulo

*m* if there exists an

such that for all

,

Here

denotes the smallest non-negative

.

We are interested in the smallest degree of polynomials representing
*f* modulo *m*. Without loss of generality we may assume *P* is
multilinear (since *x*_{i}^{2}=*x*_{i} over ).
Let
denote the
*n*-variable OR-function:

Suppose that
the polynomial *P* weakly represents OR_{n} modulo a prime *p*. Without
loss of the generality we may assume that for
,

Then

1-*P*^{p-1}(1-*x*_{1},1-*x*_{2},...,1-*x*_{n})

is exactly the *n*-variable AND function, which can uniquely be written
as a multilinear monomial

*x*_{1}*x*_{2}*x*_{3}...*x*_{n}.

Consequently, if the polynomial *P* weakly represents OR_{n} over *GF*(*p*),
then its degree is at least

*Tardos* and *Barrington* [9] proved that the same
conclusion holds if *p* is a prime power.
On the other hand, *Barrington, Beigel* and *Rudich*
[2] proved that the conclusion fails for composite moduli with at
least two distinct prime divisors:

**Theorem 2.2** (Barrington, Beigel, Rudich)
Given

where the

*p*_{i} are distinct primes, there exists
an explicitly constructible polynomial

*P* of degree

*O*(

*n*^{1/r}) which weakly represents

*OR*_{n} modulo

*m*.

For completeness, we reproduce here a short proof of this theorem.

**Proof.** Let *S*_{k}(*x*) denote the
elementary symmetric polynomial, *i.e.* the sum of all multilinear
monomials of degree *k*, formed from variables
*x*_{1},*x*_{2},...,*x*_{n}. For
,
the *weight* of *x* is defined as
.
If
,
then

Since the
value of *s*_{k}(*x*) depends only on
,
with some abuse of the notation
we shall write *s*_{k}(*x*) as *s*_{k}(*j*) where
.
Using this notation, one can formulate the following observation made in
[2]:

**Lemma 2.3**
[

2] Let

*k* be a positive integer,

*p* be
a prime and let

*e* be the
smallest integer satisfying

*k*<

*p*^{e}. Then

**Proof.** We need to prove

This is immediate from the identity

and the elementary fact that for any ,
*p* is a divisor of

Now, for *i*=1,2,...,*r*, let *e*_{i} be the smallest integer that satisfies

We define, for *i*=1,2,...,*r*, the symmetric polynomial *G*_{i}(*x*) by

One can easily
prove (using the binomial expansion of
(1-1)^{piei-1}), that
*G*_{i} correctly computes over the integers the OR function for inputs
of weight at most *p*_{i}^{ei}-1. Consequently, *G*_{i} correctly
computes modulo *p*_{i} the OR function for inputs of weight at most
*n*^{1/r}, and, additionally,
is periodic with period
*p*_{i}^{ei}.
And now, by the Chinese Remainder Theorem, there exists a polynomial
*P* which satisfies

for *i*=1,2,...,*r*, and the degree of *P* is the maximum of the degrees
of polynomials *G*_{i}, *O*(*n*^{1/r}).
It is obvious that for ,
if
then there
exists an *i*, ,
such that
,
so
.
In
addition,
*P*(0,0,...,0)=0. Consequently, *P* weakly represents the OR
function for all inputs in
modulo *p*_{1}*p*_{2}...*p*_{r}. Since
*p*_{1}*p*_{2}...*p*_{r} is a divisor of *m*, if *P*(*x*) is not 0 modulo
*p*_{1}*p*_{2}...*p*_{r} then it is not 0 modulo *m*. Consequently, *P* weakly
represents the OR function for all inputs in
modulo *m*.

**Example.** Let *m*=6, and let

and

Then

*P*(*x*)=3*G*_{1}(*x*)+4*G*_{2}(*x*)

weakly represents *OR*_{71} modulo 6 (or modulo
for any integer ), and its degree is only 8.

**Corollary 2.4**
Let

.
Then there
exists an explicitly constructible polynomial

*P*' with

*n* variables
and of degree

*O*(

*n*^{1/r}) which is equal to 0 on

,
it is nonzero mod

*m* for all other

,
and for all

and for all

,

or

.

**
Proof: **Let us consider first the easy case, when
.
Then the statement is
immediate from Lemma 2.3 and from the fact that polynomials
*G*_{i} not only represent, but compute the OR function for inputs of
weight less than *p*_{i}^{ei}.
In the general case, let us observe that *G*_{i} is either 0 or 1 modulo
*p*_{i} on .
Then we need the modulus-amplifying polynomials
*R*_{i} of degree
of *Beigel* and *Tarui* [3],
with the following properties:

and

Now, set
and construct *P*' by applying
the Chinese Remainder Theorem to the *G*'_{i}.

** Next:** The Lower Bound
** Up:** Superpolynomial Size Set-Systems with
** Previous:** Introduction
*Vince Grolmusz*

*1999-11-08*