maximal algebraic degree of a balanced Boolean functions

Question

While I was studying some cryptography maths, about balanced boolean functions i felt in a proposition that says

"The maximal algebraic degree of a balanced Boolean 
 functions of n variables is n − 1"

Why is this true??

Answer 1

Let True $=1$ and False $=0$ as usual. The addition of Boolean functions is XOR, so equivalent to addition modulo two.

When there are $n$ Boolean variables, call them $x_1,x_2,\ldots,x_n$, we see that any monomial function $x_{i_1}x_{i_2}\cdots x_{i_k}$, $1\le i_1<i_2\cdots<i_k\le n,$ of degree $k$ evaluates to True exactly $2^{n-k}$ times: those $k$ variables must all be true, but we can pick the truth values of the other $n-k$ variables as we wish. We observe that this is an even number, iff $k<n$.

Another key observation is that if $p(x_1,\ldots,x_n)$ and $q(x_1,\ldots,x_n)$ are Boolean functions such that they both evaluate to True an even number of times, then so does there sum $p+q$. This is because if $p$ evaluates to True $\ell$ times, $q$ evaluates to True $m$ times, and they both evaluate to True simultaneously $s$ times, then $p+q$ evaluates to True $(\ell-s)+(m-s)=\ell+m-2s$ times. If both $\ell$ and $m$ are even this is an even number proving the claim. Also observe that if exactly one of $p$, $q$ evaluates to True an odd number of times, then so does there sum.

From these two observations we get by induction on the number of terms that any polynomial of degree $\le n-1$ evaluates to True an even number of times. We also conclude that any polynomial of degree $n$ evaluate to True an odd number of times. This is because a polynomial of degree $n$, say $p$, can be written as $$ p(x_1,x_2,\ldots,x_n)=q(x_1,x_2,\ldots,x_n)+x_1x_2\cdots x_n, $$ with $\deg q<n$. Therefore no Boolean function of degree $n$ is balanced, when $n>1$ (a trivial exception is, when $n=1$, so let's assume that is not the case).

To complete the claim we need to prove the existence of Boolean polynomial of degree $n-1$ that is balanced, i.e. evaluates to True exactly $2^{n-1}$ times. We can do this recursively. When $n=2$ the polynomial $p_2(x_1,x_2)=x_2$ works, and when $n=3$, the polynomial $p_3(x_1,x_2,x_3)=x_1+x_1x_3+x_2x_3$ works. Assume that $n\ge3$ and that we have found a balanced polynomial $p_n(x_1,x_2,\ldots,x_n)$ of degree $n-1$. Let us define $$ p_{n+1}(x_1,x_2,\ldots,x_n,x_{n+1}):=p_n(x_1,x_2,\ldots,x_n)x_{n+1}+x_1(1+x_{n+1}). $$ I claim that this works. Here the first term is obviously of degree $(n-1)+1=n$, and the second term is of degree $2<n$, so there cannot be a cancellation of the highest degree terms, and thus $\deg p_{n+1}=n$. The presence of the complementary factors, $x_{n+1}$ and $(1+x_{n+1})$, means that the two terms never evaluate to True simultaneously. OTOH, either of the two terms evaluates to True $2^{n-2}$ times, the former by the induction hypothesis (when $x_{n+1}=1$), the latter by a direct observation (when $x_{n+1}=0$). Therefore $p_{n+1}$ is balanced, and we're done.