non-zero polynomial after partial assignment

I'm learning about Reed-Muller code, and I encountered the following paper where it is proved that the minimal distance of the code is $d =2^{m-r}$.

To make a long story short, I am only interested in understanding a part of the proof that I did not understand:

Let $f(x_1, \dots, x_m)$ a non-zero polynomial over $\mathbb{F}_2$ (that is, the variables and their coefficients are either 0 or 1), where $deg(f) \leq r$, and $\forall i: deg(x_i) \leq 1$.

Without loss of generality, we can rewrite $f$ as follows: \begin{equation} f(x_1, \dots, x_m) = x_1 \cdots x_s + g(x_1, \dots, x_m) \end{equation} where $s \leq r$. Given any assignment of $x_1,\dots,x_m$, by applying it only on $x_{s+1},\dots,x_m$, we get a new polynomial over $x_1,\dots,x_s$: \begin{equation} \hat{f}(x_1, \dots, x_s) = x_1 \cdots x_s + \hat{g}(x_1, \dots, x_s) \end{equation}

The question: in the paper mentioned earlier they claim that $\hat{f}$ is a non-zero polynomial as well "since the term $x_1 x_2 \cdots x_s$ cannot be cancelled". I tried to understand why this statement is correct. If the assignment does not zero $f$ (the original), it is easy to see that if we assume in a way of contradiction that $\hat{f}$ is a zero polynomial we get a contradiction. However, for the case of an assignment that zeroes $f$ - I just didn't succeed to convince myself that it is true. Any explanations?

Thanks.

Your write-up misses the fact that $x_1 \cdots x_s$ is a maximum degree term in $f$. So suppose we have some term $h$ of $g$, and let $\hat{h}$ be the term of $\hat{g}$ given by applying our assignment of values to $x_{s+1}, \cdots, x_m$ to $h$. Since $x_1 \cdots x_s$ is a maximum degree term, we must have $\deg h \leq s$. Now if $\deg h < s$, then $\deg \hat h < s$ too. Alternatively we could have $\deg h = s$. In this case, we cannot have $h = x_1 \cdots x_s$, so our assignment of values to $x_{s+1}, \cdots, x_m$ reduces the degree of $h$. Therefore $\deg \hat h < s$ either way, so $\deg \hat g < s$ and $x_1 \cdots x_s$ is the unique term of degree $s$ or greater in $\hat f$.
• Thanks! I thought about that, but I though that since we're in $\mathbb{F}_2$ it might not be true. Can you clarify about that? – noamgot Jun 7 '18 at 16:31
• Each of the terms of $f$ ($x_1 \cdots x_s, g(x_1, \dots, x_m)$) is eventually evaluated to either 0 or 1. If we were in a different field then it was much clearer that indeed $x_1 \cdots x_s$ is greater than any other term, but that's not the case here. Hope that you understand what I mean... – noamgot Jun 7 '18 at 16:46
• Are you happy that $x_1 \cdots x_s$ has strictly higher degree than any other term in $\hat f$, and worried that that doesn't necessarily imply that $\hat f$ is non-zero? – Christopher Jun 7 '18 at 16:51
• As far as I understand, the evaluation of $\hat{f}$ is done modulo 2. So I guess the answer to your last comment is - yes. – noamgot Jun 7 '18 at 16:56