Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such: $p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)$, which is of degree $n$.
But how could I show, what seems obvious, that if $p$ is a polynomial that represents the OR function exactly (so $\forall x \in \{0,1\}^n : p(x) = \bigvee_{i = 1}^n x_i$), then $\deg(p) \ge n$?
Let $f\colon \{0,1\}^n \to \{0,1\}$ be a boolean function. If it has a polynomial representation $P$ then it has a multilinear polynomial representation $Q$ of degree $\deg Q \leq \deg P$: just replace any power $x_i^k$, where $k \geq 2$, by $x_i$. So we can restrict our attention to multilinear polynomials.
Claim: The polynomials $\{ \prod_{i \in S} x_i : S \subseteq [n] \}$, as functions $\{0,1\}^n \to \mathbb{R}$ form a basis of for the space of all functions $\{0,1\}^n \to \mathbb{R}$.
Proof: We first show that the polynomials are linearly independent. Suppose that $f = \sum_S c_S \prod_{i \in S} x_i = 0$ for all $(x_1,\ldots,x_n) \in \{0,1\}^n$. We prove by (strong) induction on $|S|$ that $c_S = 0$. Suppose that $c_T = 0$ for all $|T| < k$, and let us be given a set $S$ of cardinality $k$. For all $T \subset S$ we know by induction that $c_T = 0$, and so $0 = f(1_S) = c_S$, where $1_S$ is the input which is $1$ on the coordinates of $S$. $~\qquad\square$
The claim shows that the multilinear representation of a function $f\colon \{0,1\}^n \to \{0,1\}$ is unique (indeed, $f$ doesn't even have to be $0/1$-valued). The unique multilinear representation of OR is $1-\prod_i(1-x_i)$, which has degree $n$.
Let $p$ be a polynomial such that for all $x\in \{0,1\}^n$, $p(x) = \sf{OR}(x)$. Consider the symmetrization of the polynomial $p$: $$q(k) = \frac{1}{\binom{n}{k}} \sum_{x: |x| = k} p(x).$$ Note that, since the OR function is a symmetric boolean function, we have that for $k = 1, 2, \ldots, n$, $q(k) = 1$, and $q(0) = 0$. Since $q-1$ is a non-zero polynomial, and it has at least $n$ 0's, it must have degree at least $n$. Therefore, $p$ must also have degree $n$.
Symmetrization is often used in the study of the approximate degree of boolean functions and quantum query complexity. See, for example, http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf.
Yuval and Henry have given two different proofs of this fact. Here's a third proof.
First, as in Yuval's answer we restrict our attention to multilinear polynomials. Now you have already exhibited a degree $n$ multilinear polynomial that equals the OR function. Now all we need to show is that this polynomial is unique, and hence you have found the one and only representation of the OR function as a polynomial. Consequently, its degree is $n$.
Claim: If two multilinear polynomials p and q are equal on the hypercube, then they are equal everywhere.
Proof: Let r(x) = p(x) - q(x), and we know that r(x)=0 for all x in $\{0,1\}^n$. We want to show that r(x) is identically zero. Toward a contradiction, assume it is not, and pick any monomial in r with a nonzero coefficient that has minimal degree. Set all the variables outside this monomial to be 0 and all the variables in this monomial to be 1. r(x) is nonzero on this input, but this input is Boolean, which is a contradiction.
