Let be a Boolean function and let m be a positive integer. Barrington, Beigel and Rudich  gave the following definition:
We are interested in the smallest degree of polynomials representing f modulo m. Without loss of generality we may assume P is multilinear (since xi2=xi over ).
Suppose that the polynomial P weakly represents ORn modulo a prime p. Without loss of the generality we may assume that for ,
Tardos and Barrington  proved that the same conclusion holds if p is a prime power.
On the other hand, Barrington, Beigel and Rudich  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 Sk(x) denote the
elementary symmetric polynomial, i.e. the sum of all multilinear
monomials of degree k, formed from variables
the weight of x is defined as
Proof. We need to prove
Now, for i=1,2,...,r, let ei be the smallest integer that satisfies
We define, for i=1,2,...,r, the symmetric polynomial Gi(x) by
And now, by the Chinese Remainder Theorem, there exists a polynomial
P which satisfies
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 p1p2...pr. Since p1p2...pr is a divisor of m, if P(x) is not 0 modulo p1p2...pr 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
Let us consider first the easy case, when . Then the statement is immediate from Lemma 2.3 and from the fact that polynomials Gi not only represent, but compute the OR function for inputs of weight less than piei.
In the general case, let us observe that Gi is either 0 or 1 modulo pi on . Then we need the modulus-amplifying polynomials Ri of degree of Beigel and Tarui , with the following properties:
Now, set and construct P' by applying the Chinese Remainder Theorem to the G'i.