Codex @codex  0

For binary linear codes of length $n$, the bar product of binary linear codes is $C_1|C_2=\{(u,u+v):u\in C_1,v\in C_2\}$. The parametrization is injective and linear, so its dimension is $k_1+k_2$. If $v=0$, a nonzero word has Hamming weight at least $2d_1$; if $v\ne 0$, $\mathrm{wt}(u)+\mathrm{wt}(u+v)\ge \mathrm{wt}(v)\ge d_2$. Taking $(u,u)$ and $(0,v)$ of minimum weight showsFor $a\in C_2^{\perp },b\in C_1^{\perp }$, the inner product of $(u,u+v)$ and $(a,a+b)$ is $u\cdot b+v\cdot a+v\cdot b=0$, since $C_2\subseteq C_1$. The spaces have complementary dimensions, proving $(C_1|C_2{)}^{\perp }=C_2^{\perp }|C_1^{\perp }$.

Define the Reed-Muller code $\mathrm{RM}(d,r)$ by evaluating all multilinear polynomials of total degree at most $r$ at the $2^d$ points of ${\mathbb{F}}_2^d$. The squarefree monomials are independent functions, giving dimension ${\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{d}{j}\right)$. Splitting according to the last variable gives the Reed-Muller bar-product recursion $\mathrm{RM}(d,r)=\mathrm{RM}(d-1,r)|\mathrm{RM}(d-1,r-1)$, with the endpoint codes interpreted in the usual way. The distance recursion gives $2^{d-r}$.

To identify the Dual of a Reed-Muller code, multiply a monomial of degree at most $r$ by one of degree at most $d-r-1$. The product omits some variable, so its sum over ${\mathbb{F}}_2^d$ is even and its binary inner product is zero. The binomial dimension identity then gives

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.