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

Preliminaries

Let $f:\{0,1\}^n\to\{0,1\}$ 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 $S\subset \{0,1,2,...,m-1\}$ such that for all $x\in\{0,1\}^n$,

\begin{displaymath}f(x)=0\Longleftrightarrow \big(P(x)\bmod{m}\big)\in S.\end{displaymath}

Here $(a \bmod{m})$ denotes the smallest non-negative $b\equiv a\bmod{m}$.

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 $\{0,1\}^n$). Let $\hbox{OR}_n:\{0,1\}^n\to\{0,1\}$ denote the n-variable OR-function:

\begin{displaymath}\hbox{OR}_n(x_1,x_2,\ldots,x_n)=\cases{0, \hbox{ if }x_1=x_2=\cdots=x_n=0\cr
1 \hbox{ otherwise}.}\end{displaymath}

Suppose that the polynomial P weakly represents ORn modulo a prime p. Without loss of the generality we may assume that for $x\in\{0,1\}^n$,

\begin{displaymath}P(x)\equiv 0\bmod{p}\iff x=(0,0,...,0).\end{displaymath}

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

\begin{displaymath}\bigg\lceil{n\over p-1}\bigg\rceil.\end{displaymath}

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 $m=p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r}$ 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 $k^{\hbox{th}}$ elementary symmetric polynomial, i.e. the sum of all multilinear monomials of degree k, formed from variables x1,x2,...,xn. For $x\in\{0,1\}^n$, the weight of x is defined as $\hbox{\rm wt}(x)=\sum_{i=1}^nx_i$. If $\hbox{\rm wt}(x)=\ell$, then

\begin{displaymath}s_k(x)={\ell\choose k}.\end{displaymath}

Since the value of sk(x) depends only on $\hbox{\rm wt}(x)$, with some abuse of the notation we shall write sk(x) as sk(j) where $j=\hbox{\rm wt}(x)$. 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 $s_k(j)\equiv s_k(j+p^e)\pmod{p}.$

Proof. We need to prove

\begin{displaymath}{j+p^e\choose k}\equiv{j\choose k}\pmod{p}.\end{displaymath}

This is immediate from the identity

\begin{displaymath}{u+v\choose t}=\sum^t_{w=0}{u\choose w}{v\choose t-w},\end{displaymath}

and the elementary fact that for any $1\le\ell<p^e$, p is a divisor of ${p^{e}\choose \ell}.$ $\Box$


Now, for i=1,2,...,r, let ei be the smallest integer that satisfies

\begin{displaymath}p_i^{e_i}>\lceil n^{1/r}\rceil.\end{displaymath}

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

\begin{displaymath}G_i(x)=\sum^{p_i^{e_i}-1}_{j=1}(-1)^{j+1}s_j(x).\end{displaymath}

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, $G_i\bmod{p_i}$ is periodic with period piei. And now, by the Chinese Remainder Theorem, there exists a polynomial P which satisfies

\begin{displaymath}P\equiv G_i\pmod{p_i}\end{displaymath}

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 $x\in\{0,1\}^n$, if $\hbox{\rm wt}(x)\ne 0$ then there exists an i, $1\leq i\leq r$, such that $\hbox{\rm wt}(x)\not\equiv 0
\bmod{p_i^{e_i}}$, so $P(x)\not\equiv0 \bmod{p_1p_2...p_r}$. In addition, P(0,0,...,0)=0. Consequently, P weakly represents the OR function for all inputs in $\{0,1\}^n$ 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 $\{0,1\}^n$ modulo m. $\Box$


Example. Let m=6, and let

\begin{displaymath}G_1(x)=\sum^{2^3-1}_{j=1}(-1)^{j+1}s_j(x),\end{displaymath}

and

\begin{displaymath}G_2(x)=\sum^{3^2-1}_{j=1}(-1)^{j+1}s_j(x).\end{displaymath}

Then

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

weakly represents OR71 modulo 6 (or modulo $6\ell$ for any integer $\ell$), and its degree is only 8.

Corollary 2.4   Let $m=p_1^{\alpha_1}p_2^{\alpha_2}...p_r^{\alpha_r}$. Then there exists an explicitly constructible polynomial P' with n variables and of degree O(n1/r) which is equal to 0 on $x=(0,0,\ldots,0)
\in\{0,1\}^n$, it is nonzero mod m for all other $x\in\{0,1\}^n$, and for all $x\in\{0,1\}^n$ and for all $i\in\{1,\ldots,r\}$, $P(x)\equiv0\pmod{p_i^{\alpha_i}}$ or $P(x)\equiv1\pmod{p_i^{\alpha_i}}$.

Proof:    Let us consider first the easy case, when ${\alpha_1}={\alpha_2}=\cdots={\alpha_r}=1$. 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 $\{0,1\}^n$. Then we need the modulus-amplifying polynomials Ri of degree $2\alpha_i$ of Beigel and Tarui [3], with the following properties:

\begin{displaymath}N\equiv 0 \pmod{p_i} \Longrightarrow R_i(N)\equiv 0 \pmod{p_i^{\alpha_i}}\end{displaymath}

and

\begin{displaymath}N\equiv 1 \pmod{p_i} \Longrightarrow R_i(N)\equiv 1 \pmod{p_i^{\alpha_i}}.\end{displaymath}

Now, set $G'_i=R_i\circ G_i$ and construct P' by applying the Chinese Remainder Theorem to the G'i. $\Box$
next up previous
Next: The Lower Bound Up: Superpolynomial Size Set-Systems with Previous: Introduction
Vince Grolmusz
1999-11-08