= Solution
The standard name is the <Reed-Muller code>. For $0\leq d\leq 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_mh$ and the two restrictions $g,g+h$. Thus the monomials of degree at most $d$ are independent and
$$
\boxed{\dim RM(m,d)=\sum_{j=0}^d\binom mj,\qquad R=2^{-m}\sum_{j=0}^d\binom mj.}
$$
For minimum weight, use the same splitting. A nonzero $h$ has weight at least $2^{m-d}$ by induction, and $\operatorname{wt}(g)+\operatorname{wt}(g+h)\geq\operatorname{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, so
$$
\boxed{d_{\min}=\operatorname{wt}_{\min}=2^{m-d}.}
$$
Here 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 $\langle x,y\rangle=0$. This proves the asserted inclusion in the <dual code>. Finally
$$
\sum_{j=0}^{m-r-1}\binom mj=2^m-\sum_{j=0}^r\binom mj,
$$
by binomial symmetry. The dimensions agree with that of the <orthogonal> complement, proving \b[$RM(m,r)^\perp=RM(m,m-r-1)$] for $0\leq r<m$.
Back to article page
