# Representing OR with polynomials

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$?

-
Are you talking about real polynomials? Or polynomials modulo 2? If you want to talk about modulo 6 (or other composite numbers), then the question becomes more interesting. –  Igor Shinkar Feb 24 at 9:38

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.

-
It seems to me that in order for your proof to work, you need to show that the degree of q is at most the degree of p. This is not clear to me. How do you show this? –  matthon Feb 28 at 16:46
Let d = deg(p). Then q is a sum of degree d polynomials, hence the degree of q is at most d. –  Henry Yuen Feb 28 at 17:42