# Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n

Here is a question from Computational Complexity by Arora and Barak:

Show that representing OR of $$n$$ variables $$x_1,x_2,\dots,x_n$$ exactly over a polynomial in $$GF(q)$$ requires degree exactly $$n$$. (This is Exercise 6 in the chapter on circuit lower bounds.)

How do I approach this problem?

• What have you tried? Have you tried the case $n=2$? $n=3$? We discourage questions that are just the statement of an exercise-style task and a request for us to solve it. – D.W. Oct 10 '20 at 19:29
• – D.W. Oct 10 '20 at 19:30
• Yes, my approach actually is convert the domain for $\{0,1\}^n->\{-1,1\}^n$ by taking $y=1-2x, x \in \{0,1\}^n$. Thus all the polynomials can be represented as multinomials. But the arithmetization of OR gives us a n degree multinomial directly, and we are asking whether there is another multinomial of less degree computing OR. This is where I am stuck. Also the transformation we are doing here does not change the degree. – roydiptajit Oct 10 '20 at 19:40
• You've restated the problem. I suggest that you try to prove it for $n=2$ first, and see how much progress you can make. – D.W. Oct 10 '20 at 20:05
• Here is what I have thought. I tried to approach for AND. For n=2, lets suppose we have a degree 1 polynomial computing AND. If we take the monomials containing $x_1$, and take $x_1=0$, we get the result zero. So, the other monomials in which $x_1$ is not present will be zero automatically. Similar with $x_1$, so we can conclude $x_1,x_2$ are present in the same monomial. But that makes its degree 2. Now, if we consider OR circuit of degree 1 and convert to AND by negating the variables, we get a contradiction as negating variable wont change degree. But this is not very formal only intuitive – roydiptajit Oct 11 '20 at 5:46

Let $$AND:\{0,1\}^n\mapsto\{0,1\}$$ be a polynomial in $$GF(q), q\geq 2$$. Notice that the polynomial can't have a constant term (the constant term is zero), because $$AND(0,...,0) = 0$$. Meaning we can write the polynomial as: $$AND(x_1,...,x_n) = \sum_{S\subseteq[1,n], S\neq \emptyset}a_S\prod_{j\in S}x_j$$ We now claim that every non-zero summand in $$AND$$ contains $$x_i$$. Suppose that there are a set of summands not containing $$x_i$$. Choose the smallest (by amount of different parameters contained) of them. Notice that this term is uniquely identified by a set $$U \subset [1,n]\backslash\{i\}$$. Now set $$x_u = 1, u\in U$$ and $$x_v = 0, v\notin U$$ and that there is no proper subsets of $$U$$ whose associated term is non-zero, because $$|U|$$ was chosen to be minimal. $$AND(x_1,...,x_n) = a_U$$ This implies $$a_U = 0$$, because $$i\notin U \land x_i = 0$$. Repeat for all other summands (in increasing order by size). Thus all non-zero terms contain $$x_i$$. This applies to all $$i\in[1,n]$$, hence the degree of $$AND$$ is $$n$$.
We can denote $$OR$$ as $$OR(x_1,...,x_n) = 1-AND(1-x_1,...,1-x_n)$$ and likewise $$AND(x_1,...,x_n) = 1-OR(1-x_1,...,1-x_n)$$ by De Morgan's Law. Thus $$AND$$ and $$OR$$ must have the same degree.
Let $$f\colon \{0,1\}^n \to \mathit{GF}(q)$$. Then $$f(x) = \sum_{y \in \{0,1\}^n} f(y) \prod_{i\colon y_i=0} (1-x_i) \prod_{i\colon y_i=1} x_i.$$ This shows that any function from $$\{0,1\}^n$$ to $$\mathit{GF}(q)$$ can be represented as a multilinear polynomial.
Now let us show that the representation is unique. This follows from dimension considerations (the space of all such functions has dimension $$2^n$$, which coincides with the dimension of the space of multilinear polynomials), but we can also prove it directly. If some function has two different representations $$P,Q$$, then $$P-Q$$ is a non-zero multilinear polynomial that vanishes on $$\{0,1\}^n$$. Let $$m$$ be a monomial in $$P-Q$$ of minimal degree, appearing with coefficient $$c \neq 0$$, and let $$y \in \{0,1\}^n$$ be the point defined as follows: $$y_i = 1$$ if $$x_i$$ appears in $$m$$, and $$y_i = 0$$ otherwise. Then $$(P-Q)(y) = cm(y) = c \neq 0$$, contradiction.
Suppose that $$P$$ is a polynomial representing the OR function. If $$P$$ is not multilinear, we can replace every occurrence of $$x_i^d$$ for $$d \geq 1$$ with $$x_i$$, obtaining another representation $$Q$$ of OR whose degree is at most the degree of $$P$$. According to the above, this representation is unique, and so it must be the following: $$Q(x) = 1-\prod_{i=1}^n (1-x_i).$$ Thus $$\deg(P) \geq \deg(Q) = n$$.