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?



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

  • $\begingroup$ 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? $\endgroup$ – noamgot Jun 7 '18 at 16:31
  • $\begingroup$ Which part are you concerned about? $\endgroup$ – Christopher Jun 7 '18 at 16:44
  • $\begingroup$ 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... $\endgroup$ – noamgot Jun 7 '18 at 16:46
  • $\begingroup$ 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? $\endgroup$ – Christopher Jun 7 '18 at 16:51
  • $\begingroup$ 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. $\endgroup$ – noamgot Jun 7 '18 at 16:56

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.