[proofplan] For (i), we use the fact that the last-coordinate hyperplane $\{p \in X : p_d = 0\}$ partitions $X$ into two halves of size $2^{d-1}$, inducing a splitting $\mathbb{F}_2^{2^d} = \mathbb{F}_2^{2^{d-1}} \oplus \mathbb{F}_2^{2^{d-1}}$. We track how each Reed-Muller generator $v_i$ and each wedge product splits under this decomposition. The generators $v_1, \dots, v_{d-1}$ have equal first and second halves, while $v_d$ is all-ones on the first half and zero on the second. A case analysis on whether a wedge product involves $v_d$ shows that the image of $\mathrm{RM}(d, r)$ under the splitting is exactly the bar product $\mathrm{RM}(d-1, r) \mid \mathrm{RM}(d-1, r-1)$. A final reparameterisation converts the natural form $(w + w', w)$ produced by the decomposition into the bar-product form $(x \mid x + y)$. For (ii), we induct on $d$, using (i) together with the rank-and-distance formula for the bar product; the two base cases $r = 0$ and $r = d$ are the repetition code (distance $2^d$) and the full space (distance $1$), respectively. [/proofplan] [step:Split coordinates according to the value of the last variable $x_d$] Define the partition of $X = \mathbb{F}_2^d$ into the two cosets of the hyperplane $\{x_d = 0\}$: \begin{align*} X_0 := \{p \in X : p_d = 0\}, \qquad X_1 := \{p \in X : p_d = 1\}. \end{align*} Each is in natural bijection with $\mathbb{F}_2^{d-1}$ via the coordinate-forgetting map $\iota: X_\varepsilon \to \mathbb{F}_2^{d-1}$, $p \mapsto (p_1, \dots, p_{d-1})$. We choose the enumeration of $X$ so that $X_0$ comes first (coordinates $1, \dots, 2^{d-1}$ of $\mathbb{F}_2^n$) and $X_1$ comes second (coordinates $2^{d-1} + 1, \dots, 2^d$). Under this enumeration every $v \in \mathbb{F}_2^n$ splits uniquely as \begin{align*} v = (v' \mid v''), \qquad v', v'' \in \mathbb{F}_2^{2^{d-1}}, \end{align*} where $v'$ is the first half (values on $X_0$) and $v''$ the second half (values on $X_1$). The splitting map $\Psi: \mathbb{F}_2^n \to \mathbb{F}_2^{2^{d-1}} \times \mathbb{F}_2^{2^{d-1}}$, $v \mapsto (v', v'')$, is an $\mathbb{F}_2$-linear isomorphism that intertwines pointwise addition and pointwise multiplication componentwise: $(v + w)' = v' + w'$, $(v \wedge w)' = v' \wedge w'$, and likewise for the $''$-half. [/step] [step:Describe how each generator $v_i$ splits under $\Psi$] Recall $v_i$ is the indicator of $\{p \in X : p_i = 0\}$ for $1 \leq i \leq d$, and $v_0 = \mathbf{1}$. **Case $1 \leq i \leq d - 1$.** The condition $p_i = 0$ does not involve the last coordinate $p_d$, so the indicator value at $p$ depends only on $(p_1, \dots, p_{d-1}) = \iota(p)$. Hence $v_i(p)$ is the same for the two points $p \in X_0$ and $p' \in X_1$ with $\iota(p) = \iota(p')$. Translating via $\Psi$: \begin{align*} v_i' = v_i'' = \tilde v_i \in \mathbb{F}_2^{2^{d-1}}, \end{align*} where $\tilde v_i$ is the indicator on $\mathbb{F}_2^{d-1}$ of the hyperplane $\{q \in \mathbb{F}_2^{d-1} : q_i = 0\}$ — the corresponding Reed-Muller generator in dimension $d - 1$. Thus $\Psi(v_i) = (\tilde v_i, \tilde v_i)$. **Case $i = d$.** The condition $p_d = 0$ holds exactly on $X_0$ and fails exactly on $X_1$. Hence $v_d$ is $1$ on every coordinate of the first half and $0$ on every coordinate of the second half: \begin{align*} \Psi(v_d) = (\mathbf{1}, \mathbf{0}) \in \mathbb{F}_2^{2^{d-1}} \times \mathbb{F}_2^{2^{d-1}}, \end{align*} where $\mathbf{1}$ is the all-ones vector and $\mathbf{0}$ the zero vector in $\mathbb{F}_2^{2^{d-1}}$. **Case $i = 0$.** $v_0 = \mathbf{1}$, so $\Psi(v_0) = (\mathbf{1}, \mathbf{1})$. Correspondingly, in $\mathbb{F}_2^{d-1}$ the all-ones vector is $\tilde v_0$, so $\Psi(v_0) = (\tilde v_0, \tilde v_0)$, which is consistent with the first case upon treating $v_0$ as the empty wedge product. [/step] [step:Compute the $\Psi$-image of a wedge product not involving $v_d$] Fix a wedge product $P = v_{i_1} \wedge \cdots \wedge v_{i_s}$ with $1 \leq i_1 < \cdots < i_s \leq d - 1$ and $0 \leq s \leq r$. Since $\Psi$ is a ring homomorphism with respect to pointwise addition and multiplication on both sides, \begin{align*} \Psi(P) = \Psi(v_{i_1}) \wedge \cdots \wedge \Psi(v_{i_s}) = (\tilde v_{i_1}, \tilde v_{i_1}) \wedge \cdots \wedge (\tilde v_{i_s}, \tilde v_{i_s}) = (\tilde P, \tilde P), \end{align*} where $\tilde P := \tilde v_{i_1} \wedge \cdots \wedge \tilde v_{i_s} \in \mathrm{RM}(d-1, s) \subseteq \mathrm{RM}(d-1, r)$. As the generators $(i_1, \dots, i_s)$ range over all such tuples with length at most $r$, the images $\tilde P$ range over a generating set for $\mathrm{RM}(d-1, r)$ (by definition of Reed-Muller). Hence \begin{align*} \Psi\bigl(\operatorname{span}\{P : P \text{ wedge product not involving } v_d,\ \text{length} \leq r\}\bigr) = \{(w, w) : w \in \mathrm{RM}(d-1, r)\}. \end{align*} We call the set $\{(w, w) : w \in \mathrm{RM}(d-1, r)\}$ the **diagonal copy** of $\mathrm{RM}(d-1, r)$. [/step] [step:Compute the $\Psi$-image of a wedge product involving $v_d$] Fix a wedge product $Q = v_d \wedge v_{i_1} \wedge \cdots \wedge v_{i_{s-1}}$ with $1 \leq i_1 < \cdots < i_{s-1} \leq d - 1$ and $1 \leq s \leq r$. Applying $\Psi$ as a ring homomorphism: \begin{align*} \Psi(Q) = \Psi(v_d) \wedge \Psi(v_{i_1}) \wedge \cdots \wedge \Psi(v_{i_{s-1}}) = (\mathbf{1}, \mathbf{0}) \wedge (\tilde v_{i_1}, \tilde v_{i_1}) \wedge \cdots \wedge (\tilde v_{i_{s-1}}, \tilde v_{i_{s-1}}). \end{align*} Pointwise multiplication acts componentwise; on the first component we get $\mathbf{1} \wedge \tilde v_{i_1} \wedge \cdots \wedge \tilde v_{i_{s-1}} = \tilde Q'$ where $\tilde Q' := \tilde v_{i_1} \wedge \cdots \wedge \tilde v_{i_{s-1}} \in \mathrm{RM}(d-1, s-1)$ (because $\mathbf{1}$ is the multiplicative identity); on the second component we get $\mathbf{0} \wedge \tilde v_{i_1} \wedge \cdots \wedge \tilde v_{i_{s-1}} = \mathbf{0}$. Thus \begin{align*} \Psi(Q) = (\tilde Q',\ \mathbf{0}), \qquad \tilde Q' \in \mathrm{RM}(d-1, s-1) \subseteq \mathrm{RM}(d-1, r-1). \end{align*} As $Q$ ranges over all such products of length $s$ with $1 \leq s \leq r$, $\tilde Q'$ ranges over a generating set for $\mathrm{RM}(d-1, r-1)$. Therefore \begin{align*} \Psi\bigl(\operatorname{span}\{Q : Q \text{ wedge product involving } v_d,\ \text{length} \leq r\}\bigr) = \{(w', \mathbf{0}) : w' \in \mathrm{RM}(d-1, r-1)\}. \end{align*} [guided] Why does the second component vanish in this case? Because $\Psi(v_d) = (\mathbf{1}, \mathbf{0})$, and pointwise multiplication by $\mathbf{0}$ on the right half annihilates anything. So every wedge product involving $v_d$ loses its right half entirely. The left half, in contrast, is multiplied by $\mathbf{1}$ and therefore preserved. This creates the asymmetry that powers the bar-product decomposition: products not involving $v_d$ live in the "diagonal" slot $(w, w)$, while products involving $v_d$ live in the "left-only" slot $(w', \mathbf{0})$. The right-hand slot is never directly populated by a single wedge product; it is built out of the $(w, w)$ contributions combined with left-shifts from $(w', \mathbf{0})$. [/guided] [/step] [step:Combine the two cases to get the image of $\mathrm{RM}(d, r)$] Every wedge product generator of $\mathrm{RM}(d, r)$ either involves $v_d$ or does not. Hence $\mathrm{RM}(d, r)$ is the $\mathbb{F}_2$-span of the union of the two generating sets from Steps 3 and 4. Since $\Psi$ is $\mathbb{F}_2$-linear, the image $\Psi(\mathrm{RM}(d, r))$ is the $\mathbb{F}_2$-span of the images: \begin{align*} \Psi(\mathrm{RM}(d, r)) = \operatorname{span}_{\mathbb{F}_2}\bigl( \{(w, w) : w \in \mathrm{RM}(d-1, r)\} \cup \{(w', \mathbf{0}) : w' \in \mathrm{RM}(d-1, r-1)\} \bigr). \end{align*} A generic element of this span is \begin{align*} (w, w) + (w', \mathbf{0}) = (w + w',\ w), \qquad w \in \mathrm{RM}(d-1, r),\ w' \in \mathrm{RM}(d-1, r-1). \end{align*} Therefore \begin{align*} \Psi(\mathrm{RM}(d, r)) = \{(w + w',\ w) : w \in \mathrm{RM}(d-1, r),\ w' \in \mathrm{RM}(d-1, r-1)\}. \end{align*} [/step] [step:Reparameterise to obtain the bar-product form $(x \mid x + y)$] Recall the definition of the bar product: \begin{align*} \mathrm{RM}(d-1, r) \mid \mathrm{RM}(d-1, r-1) = \{(x \mid x + y) : x \in \mathrm{RM}(d-1, r),\ y \in \mathrm{RM}(d-1, r-1)\}. \end{align*} This requires the containment $\mathrm{RM}(d-1, r-1) \subseteq \mathrm{RM}(d-1, r)$, which holds because every generator $\tilde v_{i_1} \wedge \cdots \wedge \tilde v_{i_{s-1}}$ of $\mathrm{RM}(d-1, r-1)$ (with $s - 1 \leq r - 1$, so $s - 1 \leq r$) is itself a generator of $\mathrm{RM}(d-1, r)$. Define the reparameterisation \begin{align*} \Theta: \mathrm{RM}(d-1, r) \times \mathrm{RM}(d-1, r-1) &\to \mathrm{RM}(d-1, r) \times \mathrm{RM}(d-1, r-1), \\ (w, w') &\mapsto (x, y) := (w + w',\ w'). \end{align*} This is a well-defined $\mathbb{F}_2$-linear map: because $\mathrm{RM}(d-1, r-1) \subseteq \mathrm{RM}(d-1, r)$, we have $w + w' \in \mathrm{RM}(d-1, r)$, and $y = w'$ stays in $\mathrm{RM}(d-1, r-1)$. It is a bijection with inverse $(x, y) \mapsto (x - y, y) = (x + y, y)$, since addition is self-inverse in $\mathbb{F}_2$. Under $\Theta$, the image computed in Step 5 becomes \begin{align*} \{(w + w',\ w) : (w, w') \in \mathrm{RM}(d-1, r) \times \mathrm{RM}(d-1, r-1)\} = \{(x,\ x + y) : (x, y) \in \mathrm{RM}(d-1, r) \times \mathrm{RM}(d-1, r-1)\}, \end{align*} because $w = (w + w') + w' = x + y$ and $w + w' = x$. Concatenating instead of tupling in the target space gives \begin{align*} \Psi(\mathrm{RM}(d, r)) = \{(x \mid x + y) : x \in \mathrm{RM}(d-1, r),\ y \in \mathrm{RM}(d-1, r-1)\} = \mathrm{RM}(d-1, r) \mid \mathrm{RM}(d-1, r-1). \end{align*} Since $\Psi$ is an isomorphism that we used merely to recoordinatise $\mathbb{F}_2^n$, we conclude \begin{align*} \mathrm{RM}(d, r) = \mathrm{RM}(d-1, r) \mid \mathrm{RM}(d-1, r-1), \end{align*} proving (i). [guided] The reparameterisation is the bookkeeping step that turns the decomposition produced by $\Psi$ — where the codewords naturally look like $(w + w', w)$ — into the standard bar-product form $(x \mid x + y)$. Setting $x = w + w'$ and $y = w'$: - $x$ replaces $w + w'$ in the first slot. - $x + y = (w + w') + w' = w$ replaces $w$ in the second slot (using $w' + w' = 0$). This works cleanly because the map $(w, w') \mapsto (w + w', w')$ is an $\mathbb{F}_2$-linear bijection on the pair space: it just adds the second coordinate to the first, a unimodular operation. The inverse recovers $w = x + y$ from $(x, y)$. Why do we need $\mathrm{RM}(d-1, r-1) \subseteq \mathrm{RM}(d-1, r)$? Because in the new parameterisation we want $x = w + w' \in \mathrm{RM}(d-1, r)$. Since $w \in \mathrm{RM}(d-1, r)$ already and $w' \in \mathrm{RM}(d-1, r-1)$, closure under addition within $\mathrm{RM}(d-1, r)$ requires $w'$ to also live there — which is exactly the containment. It holds because any wedge product of length $\leq r - 1$ is a wedge product of length $\leq r$. [/guided] [/step] [step:Establish the base cases for induction on $d$ in part (ii)] Two boundary cases of $\mathrm{RM}(d, r)$ are handled directly. **Base 1: $r = 0$, any $d \geq 0$.** By definition, $\mathrm{RM}(d, 0)$ is spanned by the single generator $v_0 = \mathbf{1}$. Thus $\mathrm{RM}(d, 0) = \{\mathbf{0}, \mathbf{1}\}$, the binary repetition code of length $2^d$. The only nonzero codeword is $\mathbf{1}$, with weight $2^d = 2^{d - 0}$. So $d(\mathrm{RM}(d, 0)) = 2^{d-0} = 2^{d-r}$. **Base 2: $r = d$, any $d \geq 0$.** By part (i) of the [Rank of Reed-Muller Codes theorem](/theorems/1665), $\operatorname{rank}(\mathrm{RM}(d, d)) = \sum_{s=0}^{d} \binom{d}{s} = 2^d = n$, so $\mathrm{RM}(d, d) = \mathbb{F}_2^n$. The minimum distance of $\mathbb{F}_2^n$ is the smallest nonzero weight, attained by the standard basis vectors with weight $1 = 2^0 = 2^{d-d}$. So $d(\mathrm{RM}(d, d)) = 1 = 2^{d-r}$. [/step] [step:Induct on $d$ to establish $d(\mathrm{RM}(d, r)) = 2^{d-r}$ for $0 < r < d$] We induct on $d \geq 1$. The case $d = 1$ is covered by the base cases: $(d, r) \in \{(1, 0), (1, 1)\}$ are the two options, both handled. Assume the result holds for $d - 1$, for all values of $r$ in the allowed range. Fix $0 < r < d$. By part (i), $\mathrm{RM}(d, r) = \mathrm{RM}(d-1, r) \mid \mathrm{RM}(d-1, r-1)$. Note that both codes on the right are nonzero: $\mathrm{RM}(d-1, r)$ contains $\mathbf{1}$, and $\mathrm{RM}(d-1, r-1)$ contains $\mathbf{1}$ (since $r - 1 \geq 0$). Apply the [Rank and Distance of Bar Product formula](/theorems/1666), which requires $\mathrm{RM}(d-1, r-1) \subseteq \mathrm{RM}(d-1, r)$ (verified in Step 6), to obtain \begin{align*} d(\mathrm{RM}(d, r)) = \min\bigl\{\,2 \cdot d(\mathrm{RM}(d-1, r)),\ d(\mathrm{RM}(d-1, r-1))\,\bigr\}. \end{align*} **Computing the first argument of the minimum.** The pair $(d-1, r)$ with $0 < r < d$ falls in one of the cases covered by the inductive hypothesis or the base cases: - If $r < d - 1$: inductive hypothesis gives $d(\mathrm{RM}(d-1, r)) = 2^{(d-1)-r}$. - If $r = d - 1$: base case 2 (with $d' = d - 1$) gives $d(\mathrm{RM}(d-1, d-1)) = 1 = 2^{0} = 2^{(d-1)-(d-1)} = 2^{(d-1)-r}$. In either case, $d(\mathrm{RM}(d-1, r)) = 2^{(d-1)-r} = 2^{d-1-r}$, so $2 \cdot d(\mathrm{RM}(d-1, r)) = 2 \cdot 2^{d-1-r} = 2^{d-r}$. **Computing the second argument of the minimum.** The pair $(d-1, r-1)$ with $0 < r < d$, so $0 \leq r - 1 < d - 1$: - If $r - 1 > 0$: inductive hypothesis gives $d(\mathrm{RM}(d-1, r-1)) = 2^{(d-1)-(r-1)} = 2^{d-r}$. - If $r - 1 = 0$: base case 1 (with $d' = d - 1$) gives $d(\mathrm{RM}(d-1, 0)) = 2^{d-1} = 2^{(d-1)-0} = 2^{d - r}$ since $r = 1$. In either case, $d(\mathrm{RM}(d-1, r-1)) = 2^{d-r}$. **Taking the minimum.** Both arguments of the minimum equal $2^{d-r}$, so \begin{align*} d(\mathrm{RM}(d, r)) = \min\{\,2^{d-r},\ 2^{d-r}\,\} = 2^{d-r}. \end{align*} This closes the induction. [guided] The induction works because the bar product $\mathrm{RM}(d-1, r) \mid \mathrm{RM}(d-1, r-1)$ has two distance contributions — $2 \cdot d(\mathrm{RM}(d-1, r))$ and $d(\mathrm{RM}(d-1, r-1))$ — and both, when computed via the inductive hypothesis, come out equal to $2^{d-r}$. The equality is not coincidental: the exponent decreases by 1 in the $C_1$ slot of the bar product (from $(d-1) - r$ to $(d-1) - r$, then doubled) and by 0 in the $C_2$ slot (from $(d-1) - (r-1) = d - r$, no doubling). That is, doubling $2^{d-1-r}$ and leaving $2^{d-r}$ alone give the same value, exactly because $2 \cdot 2^{d-1-r} = 2^{d-r}$. This is the sense in which Reed-Muller codes are "naturally balanced" for the bar-product construction: the minimum-distance budgets of the two sub-codes align perfectly under doubling. Any asymmetry would have left one of the two arguments strictly smaller, and the minimum-distance recursion would exhibit a different growth rate. [/guided] [/step] [step:Collect the two parts of the theorem] Step 6 establishes part (i). Steps 7 and 8 establish part (ii) by induction on $d$, with base cases $r = 0$ and $r = d$ handled separately, and the inductive step using part (i) together with the bar-product rank-and-distance formula. This completes the proof. [/step]