Degree of polynomial expressing OR of n Boolean variables

587 Views Asked by At

The question goes something like

Show that the OR of $n$ variables cannot be expressed as a polynomial over $\mathbb{F}_p$ of degree less than $n$.

I do not have the slightest clue of how to proceed with the proof. Of course, there is one such construction which will give a polynomial of degree exactly $n$. But for the proof I guess we need an abstract tool which proves that any polynomial of degree less than $n$ will not correctly or fully express the OR of $n$ variables.

Source of the problem- Computational Complexity: A Modern Approach by Arora and Barak

1

There are 1 best solutions below

4
On

You have proven that OR, and any Boolean function, can be written as a polynomial over $\mathbb F_2$. You can say more; any Boolean function can be written as a multilinear polynomial. This is one where no squares $x_i^2$ appear. The is true for the simple reason that over $\mathbb F_2$, $x=x^2=x^3=\dots$, so higher powers are redundant.

A multlinear polynomial has terms that look like $x_{i_1}x_{i_2}\dots x_{i_k}$, where $\{i_1,i_2,\dots,i_k\}\subset [n]$ are $k$ distinct indices. There are $2^n$ possible terms, so there are $2^{2^n}$ multilinear polynomials. Since there are exactly $2^{2^n}$ Boolean functions, this implies that the representation you have is unique, so if you can find one representation of OR as an $n$ degree polynomial, you know that there are no others, so can conclude no representation has degree less than $n$.


Assuming that "exrpessing" OR as a polynomial $f$ over $\mathbb F_p$ means that $f(x_1,\dots,x_n)$, restricted to $\{0,1\}^n$, must be equal to $1$ if any inputs are $1$ and equal to $0$ otherwise, then here is a proof that OR requires a degree at least $ n$ polynomial.

Again, it suffices to consider multilinear polynomials, since $0^k=0$ and $1^k=1$ for all $k\ge 1$, so higher powers are redundant.

I will prove the stronger claim that any function $f:\{0,1\}^n\to \mathbb F_p$ can be represented uniquely as a multilinear polynomial over $\mathbb F_p$. For existence, for any $v\in \{0,1\}^n$, there exists a multilinear polynomial $g_v$ for which $g_v(v)=1$ and $g_v(w)=0$ for all $w\neq 0$. The construction of $f_v$ is the same as the construction of AND. Then, any function $f:\{0,1\}^n\to \mathbb F_p$ can be represented as $$f(x)=\sum_{v\in \{0,1\}^n}f(v)g_v(x)$$

For uniqueness, the last equation shows that $B=\{g_v:v\in \{0,1\}^n\}$ is a spanning set for the $\mathbb F_p$ vector space of functions $\{0,1\}^n\to \mathbb F_p$. The cardinality of $B$ is $2^n$, and the dimension of the vector space of functions $\{0,1\}^n\to \mathbb F_p$ is $2^n$. Basic linear algebra then implies that $B$ is a basis for this vector space, so the representation is unqiue. Therefore, OR is represented uniquely as a multilinear polynomial, so its degree $n$ representation is the only one.