Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 3K / a / Solution

The Reed-Muller code is spanned by the evaluation vectors of the square-free monomialsform a basis: every Boolean function has a unique algebraic normal form, so the monomials remain independent after evaluation on ${\mathbb{F}}_2^d$. ThusInduction using the decomposition $(u,u+v)$, with $u\in \mathrm{RM}(d-1,r)$ and $v\in \mathrm{RM}(d-1,r-1)$, gives the lower bound $2^{d-r}$ for every nonzero weight. The monomial $x_1\cdots x_r$ attains it, so the minimum distance is