23
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Igor Shinkar Feb 24 '14 at 9:38
30
$\begingroup$

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

$\endgroup$
26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – matthon Feb 28 '14 at 16:46
  • $\begingroup$ Let d = deg(p). Then q is a sum of degree d polynomials, hence the degree of q is at most d. $\endgroup$ – Henry Yuen Feb 28 '14 at 17:42
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.