I found two definitions Reed-Muller codes being used in literature. More specifically for any $n \in \mathbb{Z}^+$ and $1 \leq d \leq n$ we define the set $RM(d,n)$ in two possible ways,

1. $RM(d,n) = \{ f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2 \vert $f$ \text{ is a polynomial of degree at most } $d$\} $

2. $RM(d,n) = \{ f: \mathbb{F}_2^n \rightarrow \mathbb{F}_2 \text{ s.t} f(x) = (-1)^{P(x)} \vert $P$ \text{ is a polynomial of degree at most } $d$ \text{and with integer coefficients of magnitude at most }d \}$

  • Are these the same?
  • In the first definition how is "degree" defined? Is $f$ assumed to be a sum over monomials where each literal occurs with power $1$ and then the final answer of the polynomial is evaluated $mod$ $2$ or is $f$ to be thought of as a generic degree $d$ polynomial such that when its input is restricted to $\mathbb{F}_2^n$ its output gets restricted to $\mathbb{F}_2$?

1 Answer 1


They are the same.

  1. In the first definition, we identify $\mathbb{F}_2$ with elements $\{0,1\}$, with $+$ defined to be addition modulo 2 and $\times$ defined to be multiplication modulo 2.

  2. In the second definition, we identify $\mathbb{F}_2$ with elements $\{1,-1\}$ and $+$ defined to be multiplication modulo 2 and $\times$ defined as $x \times y = \max(x,y)$.

Both representations of $\mathbb{F}_2$ are isomorphic.

Degree is defined as usual for the polynomial ring $\mathbb{F}_2[x_1,\dots,x_n]$; see your favorite math textbook for the formal definition. Do note that $f$ is a multivariate polynomials, not a univariate polynomial.

The "integer coefficients of magnitude at most $d$" is weird and doesn't belong. The definition would make more sense with that phrase omitted. Pedantically speaking, that phrase makes no sense, as a polynomial over $\mathbb{F}_2$ by definition has coefficients in $\mathbb{F}_2$, so it makes no sense to speak of them as "integers", and they don't have a magnitude. (Alternatively, if we interpret it loosely/informally, that phrase becomes redundant and dead and ultimately has no effect.)

  • $\begingroup$ Thanks! I am not totally understanding your argument. (1) If the implicit representation of $\mathbb{F}_2$ is different in the two cases then shouldn't there be a difference in the implicit definitions of what is $P$ in the second definition and what is $f$ in the first definition? Could you please put in the definitions? (2) Is it clear that for every $f$ in the first case there is a $P$ in the second case and vice-versa? $\endgroup$ Jun 16, 2017 at 17:12
  • $\begingroup$ (3) The second definition is what Terence Tao uses here in his example $2.2$ at the bottom of page 2 here, arxiv.org/abs/0707.4269. Since his $P$ is defined as a map from $\mathbb{F}_2 \rightarrow \mathbb{F}_2$ he might have as well assumed that his coefficients are $\pm 1$ but he wants to additionally upperbound the coefficients by $k$ (what is $d$ here ). I guess for such a $P$ he is assuming an implicit ``mod 2" on the algebraic value of the $P$. Right? $\endgroup$ Jun 16, 2017 at 17:15

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.