For binary linear codes of length , the bar product of binary linear codes is . The parametrization is injective and linear, so its dimension is . If , a nonzero word has Hamming weight at least ; if , . Taking and of minimum weight shows
For , the inner product of and is , since . The spaces have complementary dimensions, proving .
Define the Reed-Muller code by evaluating all multilinear polynomials of total degree at most at the points of . The squarefree monomials are independent functions, giving dimension . Splitting according to the last variable gives the Reed-Muller bar-product recursion , with the endpoint codes interpreted in the usual way. The distance recursion gives .
To identify the Dual of a Reed-Muller code, multiply a monomial of degree at most by one of degree at most . The product omits some variable, so its sum over is even and its binary inner product is zero. The binomial dimension identity then gives
Work over the finite field . Reduce polynomials modulo , so their monomials are square-free. The binary Reed-Muller code consists of the evaluation vectors of polynomials of degree at most at all points of , in a fixed order. This is a linear code of length and dimension , for . Square-free monomials give independent evaluation functions, as follows inductively by splitting according to the last variable.
The minimum Hamming distance of a linear code equals its least nonzero Hamming weight. The result is
Here is the repetition code, while is the full binary vector space and has distance one. For the induction step, write , where and . Its evaluation vector is , the Reed-Muller bar-product recursion. If , its nonzero Hamming weight is at least , with the full-space endpoint treated as above. If , every position where contributes exactly one to the sum of the two weights; hence the weight is at least . The monomial is one exactly on points, attaining the bound. Degrees greater than give the same full code; the zero code at negative degree has no nonzero word whose weight could define a finite minimum.
The code is the binary repetition code of length , while
is the full binary code. For , the Reed-Muller bar-product recursion is
Thus its rank satisfies Pascal's recursion
with the stated boundary values. Therefore