# Two definitions of the Reed-Muller code

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

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

• 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? Jun 16, 2017 at 17:12
• (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? Jun 16, 2017 at 17:15