Proof. If \(b=x_1x_2\dots x_m\) is a binary word, \(v_{i_1}v_{i_2}\dots v_{i_r}(b)=1\) if and only if \(x_{i_1}=x_{i_2}=\dots = x_{i_r}=1.\) Hence the number of binary words in \(V^m\) where this monomial has value \(1\) is equal to the number of ways to choose the bits \(x_j\) where \(j\notin \{i_1,\dots ,i_r\}.\) There are \(2\) choices (\(0\) or \(1)\) for each one of those \(m-r\) bits, hence the total number of such binary words is \(2^{m-r},\) and \(w(v_{i_1}\dots v_{i_r}) = \#\{b\in V^m: v_{i_1}\dots v_{i_r}(b)=1\} =2^{m-r}.\) □

Proof. First, we prove by contradiction that monomials are linearly independent.

Assume for contradiction that a non-empty linear combination (i.e., a sum, as we are working over \(\F _2)\) of monomials equals the zero Boolean function:

\[ v_{S_1}+v_{S_2}+\dots + v_{S_k}=0, \qquad k\ge 1, \]

where \(S_1,\dots S_k\) are some subsets of the index set \(\{1,\dots ,m\}.\) Without the loss of generality, assume that \(v_{S_k}\) has the highest degree:

\[ \deg v_{S_i} \le \deg v_{S_k}, \quad \text {i.e.,}\quad \# S_i \le \#S_k \quad \text {for all $i=1,\dots ,k-1.$} \]

Note that if \(S,T\subseteq \{1,\dots ,m\}\) then \(v_Sv_T=v_{S\cup T}.\) Let now \(T=\{1,\dots ,m\}\setminus S_k,\) the complement of the set \(S_k.\) Multiplying both sides by \(v_T,\) we obtain

\begin{equation*} \tag {$*$} v_{S_1\cup T}+v_{S_2\cup T}+\dots + v_{S_k\cup T} = 0. \end{equation*}

We have \(S_k\cup T=\{1,\dots ,m\}.\) If \(i<k\) then the set \(S_i\) cannot contain \(S_k,\) and so \(S_i\cup T\ne \{1,\dots ,m\}\) and \(\deg v_{S_i\cup T}<m.\) Rewrite (\(*)\) as

\[ v_{S_1\cup T}+v_{S_2\cup T}+\dots + v_{S_{k-1}\cup T} = v_1v_2\dots v_m. \]

The left-hand side is a sum of monomials of degree less than \(m.\) By Lemma 11.1, these monomials have value vectors of even weight. A sum of vectors of even weight is a vector of even weight: we know that the binary even weight code is linear. But the right-hand side is the monomial \(v_1\dots v_m\) which by Lemma 11.1 has weight \(1,\) which is odd. This contradiction proves that monomials are linearly independent.

It remains to show that the monomials are a spanning set in the Boolean algebra. There are \(2^m\) monomials, so we can form \(2^{(2^m)}\) linear combinations of monomials by putting a coefficient of \(0\) or \(1\) in front of each monomial. All these linear combinations are distinct, by linear independence. On the other hand, there are \(2^{(2^m)}\) Boolean functions on \(V^m.\) Hence every Boolean function is a linear combination of monomials.

A basis is a set which is linearly independent and spanning, so the Theorem is proved. □

Proof. Length \(=2^m\) by construction: a value vector is made up of \(2^m\) bits obtained by evaluating the given function on the \(2^m\) binary words in \(V^m.\)

Value vectors of monomials of degree \(0,1,\ldots ,r\) span \(\RM (r,m)\) by definition of \(\RM (r,m),\) and are linearly independent by Theorem 11.2, hence form a basis of \(\RM (r,m).\) The number of monomials of degree \(d\) is the same as the number of \(d\)-element subsets of \(\{1,\ldots ,m\},\) which is \(\binom md,\) so the total number of monomials in the basis of \(\RM (r,m)\) — i.e., the dimension of \(\RM (r,m)\) — is as stated.

Minimum distance: the code \(\RM (r,m)\) contains monomials of degree \(r,\) for example, \(v_1v_2\dots v_r.\) By Lemma 11.1, these have weight \(2^{m-r}.\) Hence \(d(\RM (r,m)) = w(\RM (r,m))\) is at most \(2^{m-r}.\)

It remains to show that \(w(\RM (r,m))\ge 2^{m-r}.\) We do this by induction in \(m.\)

Base case \(m=1.\) According to the Examples above, the two possible codes are \(\RM (0,1)=\mathrm {Rep}(2,\F _2)\) of weight \(2=2^{1-0}\) and \(\RM (1,1)=\F _2^{2^m}\) of weight \(1=2^{1-1}.\) So the inequality \(w(\RM (r,m))\ge 2^{m-r}\) is satisfied when \(m=1.\)

Inductive step. Assume \(w(\RM (r,m-1))\ge 2^{m-1-r}\) for all \(r=0,\dots ,m-1.\) This means that the weight of any non-zero polynomial of degree \(\le r\) in \(v_1,\dots ,v_{m-1}\) is at least \(2^{m-1-r}:\)

\begin{equation*} \tag {$\dagger $} h\ne 0, \ \deg h \le r \quad \implies \quad \# \{ y\in V^{m-1}: h(y)=1\}\ge 2^{m-1-r}. \end{equation*}

The set \(V^m\) of binary words of length \(m\) splits into two subsets,

\begin{equation*} V^{m-1}0 = \{x_1\dots x_m: x_m=0\} \quad \text {and}\quad V^{m-1}1 = \{x_1\dots x_m: x_m=1\} \end{equation*}

of words that end in \(0\) and words that end in \(1,\) respectively. We need to take a polynomial \(0\ne f\colon V^m \to \F _2\) of degree \(\le r\) and prove that \(w(f)\ge 2^{m-r}.\) We have

\begin{equation*} \tag {$\ddagger $} w(f) = \#\{b\in V^{m-1}0: f(b)=1\} + \#\{b\in V^{m-1}1: f(b)=1\}. \end{equation*}

Each monomial in \(f\) contains a copy of \(v_m\) or none, so we can write

\[ f = g + hv_m, \]

where \(g,\) \(h\) are polynomials in \(v_1,\dots ,v_{m-1}.\)

The case \(h=0.\) Here \(g\) is a non-zero polynomial of degree \(\le r\) in \(v_1,\dots ,v_{m-1},\) and so \(r\le m-1.\) By (\(\dagger ),\) there are at least \(2^{m-1-r}\) words \(y\in V^{m-1}\) where \(g(y)=1.\) For each such word \(y\) we have \(y0\in V^{m-1}0,\) \(y1\in V^{m-1}1\) and \(f(y0)=f(y1)=1,\) and so \(y\) contributes twice when counting the weight of \(f\) in (\(\ddagger ).\) Hence \(w(f)=2w(g)\) and so \(w(f)\ge 2\times 2^{m-1-r}=2^{m-r}.\)

The case \(h\ne 0.\) We note that the values of \(f\) on \(V^{m-1}0\) are the same as the values of \(g\) on \(V^{m-1},\) because \(hv_m|_{V^{m-1}0}=0.\) Furthermore, the values of \(f\) on \(V^{m-1}1\) are the same as the values of \(g+h\) on \(V^{m-1},\) because on \(V^{m-1}1\) we have \(v_m=1.\) Hence (\(\ddagger )\) gives \(w(f) = w(g)+w(g+h).\)

By the triangle inequality, \(w(\ul a + \ul b)\le w(\ul a)+ w(\ul b)\) for any vectors \(\ul a,\ul b.\) Hence \(w(g)+w(g+h)\ge w(g+(g+h))=w(h).\) Here \(\deg h\le r-1\) because \(\deg hv_m\le r,\) so the inductive hypothesis (\(\dagger )\) applies and gives \(w(h)\ge 2^{m-1-(r-1)}=2^{m-r}.\) We proved that \(w(f)\ge 2^{m-r},\) as required.

To conclude, by induction \(w(\RM (r,m))\ge 2^{m-r}\) for all \(m\) and all \(r\le m.\) □

Proof. If \(f,g\colon V^m \to \F _2\) are Boolean functions, the definition of inner product means that

\[ \ul f \cdot \ul g = \sum _{b\in V^m} f(b)g(b) = \sum _{b\in V^m} (fg)(b). \]

If \(f\) is a monomial of degree \(\le r\) and \(g\) is a monomial of degree \(\le m-1-r,\) then \(fg\) is a monomial of degree \(\le m-1.\) By Lemma 11.1, there are exactly \(2^{m-\deg fg}\) words \(b\in V^m\) such that \((fg)(b)=1.\) Since \(m-\deg fg\ge 1,\) \(2^{m-\deg fg}\) is an even number, and so the sum \(\sum _{b\in V^m} (fg)(b)\) is zero in \(\F _2.\) This shows that \(f\) is orthogonal to \(g.\)

Since monomials \(f\) of degree \(\le r\) span \(\RM (r,m),\) this shows that \(g\in \RM (r,m)^\perp .\) Thus, \(\RM (m-1-r,m)\) is spanned by elements of \(\RM (r,m)^\perp ,\) so \(\RM (m-1-r,m) \subseteq \RM (r,m)^\perp .\)

We will now compare the dimensions. We have \(\dim \RM (m-1-r,m)= \binom m0 + \dots +\binom {m}{m-1-r}.\) Using the relation \(\binom mi=\binom {m}{m-i},\) we rewrite this as \(\binom mm + \binom m{m-1}+\dots +\binom m{r+1}.\) Finally, \(\dim \RM (m-1-r,m) + \dim \RM (r,m) = \sum _{i=0}^m\binom mi = 2^m,\) the length of the Reed-Muller codes. Hence \(\dim \RM (m-1-r,m) = 2^m - \dim \RM (r,m) = \dim \RM (r,m)^\perp .\)

Thus, \(\RM (r,m)^\perp \) contains subspace \(\RM (m-1-r,m)\) of the same dimension as \(\RM (r,m)^\perp ,\) hence a subset \(\RM (m-1-r,m)\) of the same cardinality as \(\RM (r,m)^\perp .\) We conclude that \(\RM (r,m)^\perp = \RM (m-1-r,m).\) □