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

# Preliminaries

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 xi2=xi over ).

Let denote the n-variable OR-function:

Suppose that the polynomial P weakly represents ORn modulo a prime p. Without loss of the generality we may assume that for ,

Then

1-Pp-1(1-x1,1-x2,...,1-xn)

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

x1x2x3...xn.

Consequently, if the polynomial P weakly represents ORn 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 pi are distinct primes, there exists an explicitly constructible polynomial P of degree O(n1/r) which weakly represents ORn modulo m.

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 x1,x2,...,xn. For , the weight of x is defined as . If , then

Since the value of sk(x) depends only on , with some abuse of the notation we shall write sk(x) as sk(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<pe. 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 ei be the smallest integer that satisfies

We define, for i=1,2,...,r, the symmetric polynomial Gi(x) by

One can easily prove (using the binomial expansion of (1-1)piei-1), that Gi correctly computes over the integers the OR function for inputs of weight at most piei-1. Consequently, Gi correctly computes modulo pi the OR function for inputs of weight at most n1/r, and, additionally, is periodic with period piei.

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 Gi, O(n1/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 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

and

Then

P(x)=3G1(x)+4G2(x)

weakly represents OR71 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(n1/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 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 [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