Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Here is a question from Computational Complexity by Arora and Barak:
Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$. (This is Exercise 6 in the chapter on circuit lower bounds.)
How do I approach this problem?
Let $AND:\{0,1\}^n\mapsto\{0,1\}$ be a polynomial in $GF(q), q\geq 2$. Notice that the polynomial can't have a constant term (the constant term is zero), because $AND(0,...,0) = 0$. Meaning we can write the polynomial as: $$AND(x_1,...,x_n) = \sum_{S\subseteq[1,n], S\neq \emptyset}a_S\prod_{j\in S}x_j$$ We now claim that every non-zero summand in $AND$ contains $x_i$. Suppose that there are a set of summands not containing $x_i$. Choose the smallest (by amount of different parameters contained) of them. Notice that this term is uniquely identified by a set $U \subset [1,n]\backslash\{i\}$. Now set $x_u = 1, u\in U$ and $x_v = 0, v\notin U$ and that there is no proper subsets of $U$ whose associated term is non-zero, because $|U|$ was chosen to be minimal. $$AND(x_1,...,x_n) = a_U$$ This implies $a_U = 0$, because $i\notin U \land x_i = 0$. Repeat for all other summands (in increasing order by size). Thus all non-zero terms contain $x_i$. This applies to all $i\in[1,n]$, hence the degree of $AND$ is $n$.
We can denote $OR$ as $OR(x_1,...,x_n) = 1-AND(1-x_1,...,1-x_n)$ and likewise $AND(x_1,...,x_n) = 1-OR(1-x_1,...,1-x_n)$ by De Morgan's Law. Thus $AND$ and $OR$ must have the same degree.
Let $f\colon \{0,1\}^n \to \mathit{GF}(q)$. Then $$ f(x) = \sum_{y \in \{0,1\}^n} f(y) \prod_{i\colon y_i=0} (1-x_i) \prod_{i\colon y_i=1} x_i. $$ This shows that any function from $\{0,1\}^n$ to $\mathit{GF}(q)$ can be represented as a multilinear polynomial.
Now let us show that the representation is unique. This follows from dimension considerations (the space of all such functions has dimension $2^n$, which coincides with the dimension of the space of multilinear polynomials), but we can also prove it directly. If some function has two different representations $P,Q$, then $P-Q$ is a non-zero multilinear polynomial that vanishes on $\{0,1\}^n$. Let $m$ be a monomial in $P-Q$ of minimal degree, appearing with coefficient $c \neq 0$, and let $y \in \{0,1\}^n$ be the point defined as follows: $y_i = 1$ if $x_i$ appears in $m$, and $y_i = 0$ otherwise. Then $(P-Q)(y) = cm(y) = c \neq 0$, contradiction.
Suppose that $P$ is a polynomial representing the OR function. If $P$ is not multilinear, we can replace every occurrence of $x_i^d$ for $d \geq 1$ with $x_i$, obtaining another representation $Q$ of OR whose degree is at most the degree of $P$. According to the above, this representation is unique, and so it must be the following: $$ Q(x) = 1-\prod_{i=1}^n (1-x_i). $$ Thus $\deg(P) \geq \deg(Q) = n$.
