Simpler proof for nonlinearity of majority function (Q2022506)

Let \(V_n = \mathrm{GF}(2)^n\), where \(\mathrm{GF}(2)\) denotes the field of \(2\) elements. The Hamming weight of a vector \(v\in V_n\) is denoted \(wt(v)\). Any function \(f: V_n\to \mathrm{GF}(2)\) may be identified with the vector of its values, which we also denote by \(f\) when there is no confusion. This function \(f\) may also be identified with a (unique) polynomial in \(n\) variables, called its algebraic normal form. If each term in this polynomial is (total) degree at most \(1\) then we call such a function affine. The distance between two functions, \(f\) and \(g\), is defined to be the Hamming weight of their sum, \(d(f,g)=wt(f+g)\). The nonlinearity of \(f:V_n\to \mathrm{GF}(2)\) is its minimum distance to an affine function, denoted \[ N(f)=\min_{a\text{ affine}} d(f,a). \] The first lemma in the paper under review states the following interesting result: If \(f:V_n\to \mathrm{GF}(2)\) has Hamming weight no larger than \(2^{n-2}\) then \(N(f)=wt(f).\) Roughly speaking, \(\mathrm{GF}(2)\)-valued functions which are zero at least 75\% of the time have nonlinearity equal to their Hamming weight. This paper is devoted to the nonlinearity of the majority function, \(M_n:V_n\to \mathrm{GF}(2)\), defined by \[ M_n(v)= \begin{cases}1, & \text{if } wt(v)\geq \frac{n-1}{2}+1\ \ \ (n\text{ odd}),\\ 1, & \text{if } wt(v)\geq \frac{n}{2}\ \ \ (n\text{ even}),\\ 0, & \text{otherwise}. \end{cases} \] The goal of the paper is to gives a simple proof of the following result. \textbf{Theorem}: If \(n\) is odd then \(N(M_n)=2^{n-1}- \binom{n-1}{\frac{n-1}{2}}\). If \(n\) is even then \(N(M_n)=2^{n-1}-\frac{1}{2}\cdot \binom{n}{\frac{n}{2}}\). For further details, see the well-written paper itself.