Two definitions of the Reed-Muller code

Question

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

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