Reed–Muller code

Reed–Muller code

Theorem. Let \(0 \le r \le m\). Then, \[C_{r,m}= \{\text{truth table of \(P\)}\colon P \in \mathbb{F}_{2}[x_{1},\dotsc,x_{m}], P \text{ is multilinear}, \deg(P) \le r\}\] is a linear \((n=2^{m}, k=\sum_{t \le r}\binom{m}{t}, d=2^{m-r})\) code. Encoding is polynomial-time.

Before proving, consider a toy example. Let \(m=2\). Here we use polynomials in two variables. The set \(C_{1,2}\) is shown below, its distance is two. The set \(C_{0,2}\) consists of its first two vectors, distance is four.

Proof.

• Linearity.  The sum of two polynomials of degree \(\le r\) has degree \(\le r\).


• Dimension.  Basis: truth tables of all multilinear monomials of degree \(\le r\): \[\{1\} \cup \{x_{1},\dotsc,x_{m}\} \cup \{x_{1}x_{2},\dotsc,x_{m-1}x_{m}\} \cup \dotsb \cup \{x_{i_1}\dotsb x_{i_r}\colon 1\le i_{1}<\dotsb<i_{r}\le m\}.\] Hence \(k=\sum_{t \le r}\binom{m}{t}\).


• Encoding.  Map \(\phi:\{0,1\}^{k} \to \{0,1\}^{n}\): input bits are coefficients of a degree-\(\le r\) polynomial; output is its truth table.


• Distance.  Since the code is linear, it suffices to show any nonzero codeword has weight \(\ge 2^{m-r}\), which follows from the lemma below.

◼

Lemma. Let \(P \in \mathbb{F}_{2}[x_{1},\dotsc,x_{m}]\) be a nonzero multilinear polynomial of degree \(\le r\). Then, \[|\{x \in \{0,1\}^{m} \colon P(x)=1\}| \ge 2^{m-r}.\]

Proof. Induction on \(m\). Base: \(m=1\), then \(P\in\{1,x_{1},1\oplus x_{1}\}\), checked directly. Step \(m-1\to m\): without loss of generality, assume \(P\) depends on \(x_{m}\). Then \[P(x)=Q(x_{1},\dotsc,x_{m-1})\oplus x_{m} R(x_{1},\dotsc,x_{m-1}),\] where \(R\neq0\), \(\deg R \le r-1\). By induction, \(R=1\) on at least \(2^{m-r}\) points. Each such \((v_{1},\dotsc,v_{m-1})\) extends to \((v_{1},\dotsc,v_{m-1},1\oplus Q(v))\), and \[P(v_{1},\dotsc,v_{m-1},1\oplus Q(v))=Q\oplus1\oplus Q=1.\]◼