<p>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.</p>

<p><strong>Claim:</strong> 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}$.</p>

<p><strong>Proof:</strong> 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| &lt; 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$</p>

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

CC BY-SA 3.0
2014-02-21T06:08:12.077Z
2014-02-21T06:08:12.077Z
Yuval Filmus
<p>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$.</p>

<p>Symmetrization is often used in the study of the approximate degree of boolean functions and quantum query complexity. See, for example, <a href="http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf">http://www.math.uwaterloo.ca/~amchilds/teaching/w11/l19.pdf</a>.</p>

CC BY-SA 3.0
2014-02-28T16:46:16.787Z
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
CC BY-SA 3.0
2014-02-28T17:42:56.047Z
Let d = deg(p). Then q is a sum of degree d polynomials, hence the degree of q is at most d.
Henry Yuen
CC BY-SA 3.0
2014-02-21T05:56:02.313Z
2014-02-21T22:59:57.063Z
2014-02-21T22:59:57.063Z
Henry Yuen
<p>Yuval and Henry have given two different proofs of this fact. Here's a third proof. </p>

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

<p>Claim: If two multilinear polynomials p and q are equal on the hypercube, then they are equal everywhere.</p>

<p>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.</p>

CC BY-SA 4.0
2018-05-27T17:27:38.673Z
2018-05-27T17:27:38.673Z
Robin Kothari
<p>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$.</p>

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

CC BY-SA 3.0
2014-02-24T09:38:52.187Z
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
<cc.complexity-theory><co.combinatorics><lower-bounds><polynomials>
Representing OR with polynomials
matthon
# Representing OR with polynomials

(Asked by: username_0 on 2014-02-21)

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

**Tags:** cc.complexity-theory, co.combinatorics, lower-bounds, polynomials

> **Comments:**
> **username_1**: 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.  

---

## 3 answers

### Answer by username_2 on 2014-02-21. Score: 30

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


---

### Answer by username_3 on 2014-02-21. Score: 26

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

> **Comments:**
> **username_0**: 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?  
> **username_3**: Let d = deg(p). Then q is a sum of degree d polynomials, hence the degree of q is at most d.  

---

### Answer by username_4 on 2018-05-27. Score: 3

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.


---

