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