Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 3K (Coding and Cryptography)

For binary length-$n$ linear codes $C_2\subseteq C_1$, their bar product of binary linear codes isIt is a binary linear code of length $2n$ and dimension $\dim C_1+\dim C_2$.

The code $\mathrm{RM}(d,0)$ is the binary repetition code of length $2^d$, whileis the full binary code. For $0<r<d$, the Reed-Muller bar-product recursion isThus its rank $k(d,r)$ satisfies Pascal's recursionwith the stated boundary values. Therefore

A square-free monomial in $d$ variables of degree $j\le d-1$ evaluates to one at exactly $2^{d-j}$ points of ${\mathbb{F}}_2^d$, an even number. Since parity of Hamming weight is a linear functional over ${\mathbb{F}}_2$, every sum of such evaluation words also has even weight. Hence every word in $\mathrm{RM}(d,d-1)$ has even weight.

If $f$ and $g$ have degrees at most $r$ and $d-r-1$, then $fg$ has degree at most $d-1$. The binary inner product of their evaluation words is the parity of the weight of the evaluation of $fg$, and is therefore zero. ThusFinally, binomial symmetry givesso the inclusion has equal dimensions andThis is the Dual of a Reed-Muller code.