= Dual of a Reed-Muller code
{c}
For $0\le r<d$, the standard binary <bilinear form> gives
$$
\operatorname{RM}(d,r)^\perp=\operatorname{RM}(d,d-r-1).
$$
Indeed, the product of representing <polynomials> has <polynomial degree> at most $d-1$. Each square-free <monomial> in that product omits at least one of the $d$ variables and therefore takes the value $1$ an even number of times on $\mathbb F_2^d$. Summing the product over all evaluation points gives zero in the <field with two elements>, proving orthogonality. The <dimensions> of the two <Reed-Muller codes> add to $2^d$, by the symmetry $\binom dj=\binom d{d-j}$, so containment is equality.
At $r=d$, the <Reed-Muller code> is the full vector space and its <dual code> is zero. The same displayed identity holds if $\operatorname{RM}(d,-1)$ denotes the zero code, as in the boundary convention for <Reed-Muller codes>.
Back to article page