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

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