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

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

Consequently, if the polynomial

*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:

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

**Proof.** We need to prove

This is immediate from the identity

and the elementary fact that for any ,

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)

And now, by the Chinese Remainder Theorem, there exists a polynomial
*P* which satisfies

for

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

weakly represents

**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}.