Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 2 / 12H (Coding and Cryptography)

The standard name is the Reed-Muller code. For $0\le d\le m$, evaluate all multilinear polynomials over ${\mathbb{F}}_2$ of total degree at most $d$ at every point of ${\mathbb{F}}_2^m$. These evaluation vectors form $RM(m,d)$, of length $2^m$. Distinct multilinear polynomials have distinct evaluations: induct on the variables using $f=g+x_{m}h$ and the two restrictions $g,g+h$. Thus the monomials of degree at most $d$ are independent andFor minimum weight, use the same splitting. A nonzero $h$ has weight at least $2^{m-d}$ by induction, and $\mathrm{wt}(g)+\mathrm{wt}(g+h)\ge \mathrm{wt}(h)$. If $h=0$, the two identical halves give the same lower bound by induction on $g$. The endpoint $d=m$ has minimum weight one, and $d=0$ is the repetition code. A product of $d$ distinct variables has exactly $2^{m-d}$ nonzero evaluations, soHere distance equals minimum nonzero weight because the code is linear.

Every monomial of degree at most $d-1$ in $d$ variables has an even number of ones, and parity is additive over ${\mathbb{F}}_2$. Thus every word of $RM(d,d-1)$ has even weight. If $x\in RM(m,r)$ and $y\in RM(m,m-r-1)$, their coordinatewise product is an evaluation of degree at most $m-1$, even after reducing $X_i^2=X_i$. Its weight is therefore even, so $⟨x,y⟩=0$. This proves the asserted inclusion in the dual code. Finallyby binomial symmetry. The dimensions agree with that of the orthogonal complement, proving $RM(m,r{)}^{\perp }=RM(m,m-r-1)$ for $0\le r<m$.