# Degree of $N$-bit Majority function is larger or equal to $N/2$

I am looking to prove that the $$N$$-bit Majority function $$f$$, which is 1 if its input $$x \in \{0, 1\}^N$$ has Hamming weight $$> N/2$$, and 0 if its input has Hamming weight $$\leq N/2$$ has degree $$\text{deg}f\geq N/2$$. We assume that $$N$$ is even. Any hints or suggestions are most welcome.

Note that an $$N$$-variate multilinear polynomial $$p$$ is a function $$p: \mathbb{C}^{N} \rightarrow \mathbb{C}$$ we can write as $$p\left(x_{0}, \ldots, x_{N-1}\right)=\sum_{S \subseteq\{0, \ldots, N-1\}} a_{S} \prod_{i \in S} x_{i}$$ for some $$a_{S}\in \mathbb{C}$$. The degree of $$p$$ is defined as $$\operatorname{deg}(p)=\max \left\{|S|: a_{S} \neq 0\right\} .$$ Moreover, we may use that every function $$f:\{0,1\}^{N} \rightarrow \mathbb{C}$$ has a unique representation as such a polynomial.

• How do you define the degree of a function? Apr 15 at 20:09
• Definition added :) Apr 16 at 6:01

I suppose I would start as follows: let $$z=\sum_ix_i.$$ This is simply a variable telling me how many 1s there are. Since this is the only information that I need to determine the function $$f$$, I should be able to work just with this. There's also an ingredient of symmetry in there, but is maybe not quite of a sufficiently rigorous footing yet.
Having done this, I simply want to find a function $$f(z)$$ whose value is 0 of $$z\leq N/2$$. This means it has at least $$N/2+1$$ zeros, and must have degree at least $$N/2+1$$. Explicitly, part of the function would be $$z(z-1)(z-2)\ldots(z-N/2)$$ I could construct the whole function by letting $$g(z,i)=\frac{\prod_{j=0}^{N}(z-j)}{z-i}$$ and calculating $$f(z)=\sum_{i=N/2+1}^N\frac{g(z,i)}{g(i,i)},$$ since each term in this sum evaluates to 0 for all values of $$z=0,1,2,\ldots,N$$ except for the specific term $$i$$, which evaluates to 1. This is a polynomial of degree no more than $$N$$, satisfying the values at $$N$$ points, and hence must be the unique polynomial of no more than degree $$N$$.
• But is $g(i,i)$ not undefined? Apr 16 at 12:08
• No because you've already cancelled the $z-i$ terms in both the numerator and denominator. Apr 16 at 12:24