4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ How do you define the degree of a function? $\endgroup$
    – Rammus
    Apr 15 at 20:09
  • $\begingroup$ Definition added :) $\endgroup$ Apr 16 at 6:01
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ But is $g(i,i)$ not undefined? $\endgroup$ Apr 16 at 12:08
  • 1
    $\begingroup$ No because you've already cancelled the $z-i$ terms in both the numerator and denominator. $\endgroup$
    – DaftWullie
    Apr 16 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.