[proofplan] Part (i) is a dimension-count plus a spanning argument. The total number of wedge products of length $\leq d$ is $\sum_{s=0}^d \binom{d}{s} = 2^d = \dim \mathbb{F}_2^n$, so it suffices to show spanning. We show that for every point $p \in X$ the point-indicator $\mathbb{1}_{\{p\}}$ is an element of $\mathrm{RM}(d, d)$ by exhibiting it as a single wedge product $y_1 \wedge \cdots \wedge y_d$ where each $y_i \in \{v_i, v_0 + v_i\}$; expanding by distributivity writes $\mathbb{1}_{\{p\}}$ as an $\mathbb{F}_2$-linear combination of wedge products of length $\leq d$. Since the point-indicators span $\mathbb{F}_2^n$, the wedge products span $\mathbb{F}_2^n$. Part (ii) is then immediate: the generating set of $\mathrm{RM}(d, r)$ is a subset of the basis from (i), so it is linearly independent, and its cardinality is $\sum_{s=0}^{r} \binom{d}{s}$. [/proofplan] [step:Identify $\mathbb{F}_2^n$ with functions on $X$ and record the two algebraic operations] We identify coordinates of $\mathbb{F}_2^n$ with points of $X = \mathbb{F}_2^d$ via $\Phi$. Under this identification: - Vector addition in $\mathbb{F}_2^n$ corresponds to pointwise addition of functions modulo 2. - The operation $\wedge$ is pointwise multiplication: $(u \wedge v)(p) = u(p) \cdot v(p)$ for $p \in X$. In particular, because $\mathbb{F}_2 = \{0, 1\}$, pointwise multiplication is the pointwise AND; thus $u \wedge v$ is the indicator of $\{p : u(p) = 1 \text{ and } v(p) = 1\}$ whenever $u, v$ are $\{0,1\}$-valued. - The all-ones vector $v_0 = \mathbf{1}$ is the multiplicative identity: $v_0 \wedge u = u$ for all $u$. - Distributivity holds: $u \wedge (v + w) = u \wedge v + u \wedge w$, because pointwise multiplication distributes over pointwise addition. The generator $v_i$ for $1 \leq i \leq d$ is, by definition, the indicator of the hyperplane $H_i := \{p \in X : p_i = 0\}$. Writing a point as $p = (p_1, \dots, p_d)$: \begin{align*} v_i(p) = \mathbb{1}_{\{p_i = 0\}} = 1 - p_i = 1 + p_i \pmod{2}. \end{align*} [/step] [step:Prove the count of wedge products equals $n = 2^d$] The wedge products indexed by $0 \leq s \leq d$ and $1 \leq i_1 < \cdots < i_s \leq d$ are in bijection with subsets of $\{1, \dots, d\}$: the empty subset corresponds to $s = 0$ (giving $v_0$), and a size-$s$ subset $\{i_1, \dots, i_s\}$ corresponds to the wedge product $v_{i_1} \wedge \cdots \wedge v_{i_s}$. The total count is \begin{align*} \sum_{s=0}^{d} \binom{d}{s} = 2^d = n. \end{align*} Since this equals $\dim \mathbb{F}_2^n$, to prove part (i) it suffices to show that these wedge products **span** $\mathbb{F}_2^n$; linear independence then follows for free because a spanning set of size $\dim \mathbb{F}_2^n$ in a space of dimension $\dim \mathbb{F}_2^n$ is automatically a basis. [/step] [step:Reduce spanning to producing every point-indicator] The point-indicators $\{\mathbb{1}_{\{p\}} : p \in X\}$ span $\mathbb{F}_2^n$ because any $f \in \mathbb{F}_2^n$ decomposes as \begin{align*} f = \sum_{p \in X} f(p) \cdot \mathbb{1}_{\{p\}}. \end{align*} Therefore, to show the wedge products span $\mathbb{F}_2^n$, it suffices to show that each $\mathbb{1}_{\{p\}}$ is an $\mathbb{F}_2$-linear combination of wedge products $v_{i_1} \wedge \cdots \wedge v_{i_s}$ with $0 \leq s \leq d$. [/step] [step:Construct each point-indicator as a single wedge product] Fix $p = (p_1, \dots, p_d) \in X$. Define, for each $i \in \{1, \dots, d\}$, \begin{align*} y_i \in \mathbb{F}_2^n, \qquad y_i := \begin{cases} v_i & \text{if } p_i = 0, \\ v_0 + v_i & \text{if } p_i = 1. \end{cases} \end{align*} We claim that $y_i$ is the indicator of the set $\{q \in X : q_i = p_i\}$. Indeed, $v_i$ is the indicator of $\{q : q_i = 0\}$, and $v_0 + v_i$ is the indicator of the complementary set $\{q : q_i = 1\}$ because for $q \in X$, \begin{align*} (v_0 + v_i)(q) = 1 + v_i(q) = 1 + \mathbb{1}_{\{q_i = 0\}} = \mathbb{1}_{\{q_i = 1\}}, \end{align*} using $1 + 1 = 0$ in $\mathbb{F}_2$. Now take the wedge (pointwise product) of all $y_i$: \begin{align*} y_1 \wedge y_2 \wedge \cdots \wedge y_d. \end{align*} Evaluating at a point $q \in X$ gives, by the multiplicative identity $\wedge \leftrightarrow$ AND, \begin{align*} (y_1 \wedge \cdots \wedge y_d)(q) = \prod_{i=1}^{d} y_i(q) = \prod_{i=1}^{d} \mathbb{1}_{\{q_i = p_i\}} = \mathbb{1}_{\{q = p\}}. \end{align*} Therefore $y_1 \wedge \cdots \wedge y_d = \mathbb{1}_{\{p\}}$. [guided] The construction is engineered so that each $y_i$ "detects" the correct value of the $i$-th coordinate of $p$. Because $\wedge$ is pointwise AND on $\{0,1\}$-valued vectors, taking the wedge of $d$ such detectors gives the indicator of the unique point whose coordinates match $p$ in every slot — namely $p$ itself. Why did we have to introduce $v_0 + v_i$? Because the bare generator $v_i$ only detects $p_i = 0$, not $p_i = 1$. In $\mathbb{F}_2$, the indicator of $\{q_i = 1\}$ is exactly the complement of the indicator of $\{q_i = 0\}$, and complementation is written as "$\text{NOT} = 1 + \text{(thing)}$", i.e., $v_0 + v_i$. This is why $v_0 = \mathbf{1}$ plays the role of the identity: it is needed to flip bits. A clean way to verify $y_i = \mathbb{1}_{\{q_i = p_i\}}$: examine both cases. - If $p_i = 0$: $y_i = v_i = \mathbb{1}_{\{q_i = 0\}}$. Matches because we want $q_i = 0 = p_i$. - If $p_i = 1$: $y_i = v_0 + v_i$. For $q \in X$, $(v_0 + v_i)(q) = 1 + \mathbb{1}_{\{q_i = 0\}}$. When $q_i = 0$, this is $1 + 1 = 0$; when $q_i = 1$, this is $1 + 0 = 1$. So $y_i = \mathbb{1}_{\{q_i = 1\}} = \mathbb{1}_{\{q_i = p_i\}}$. Taking the wedge of all $y_i$ then asserts "$q_1 = p_1$ AND $q_2 = p_2$ AND $\cdots$ AND $q_d = p_d$", which is equivalent to $q = p$. [/guided] [/step] [step:Expand the wedge product by distributivity to conclude $\mathbb{1}_{\{p\}} \in \mathrm{RM}(d, d)$] By the previous step, $\mathbb{1}_{\{p\}} = y_1 \wedge y_2 \wedge \cdots \wedge y_d$ where each $y_i \in \{v_i,\ v_0 + v_i\}$. Expanding this product by distributivity of $\wedge$ over $+$: \begin{align*} y_1 \wedge \cdots \wedge y_d = \sum_{(z_1, \dots, z_d)} z_1 \wedge \cdots \wedge z_d, \end{align*} where the sum runs over all choices $(z_1, \dots, z_d) \in \{v_0, v_1\} \times \{v_0, v_2\} \times \cdots \times \{v_0, v_d\}$ — one factor selected from each $y_i$ when $y_i = v_0 + v_i$, and simply $v_i$ when $y_i = v_i$. More precisely, let $S := \{i : p_i = 1\}$; then \begin{align*} y_1 \wedge \cdots \wedge y_d = \bigwedge_{i \notin S} v_i \ \wedge\ \bigwedge_{i \in S} (v_0 + v_i) = \sum_{T \subseteq S} \bigwedge_{i \in S \setminus T} v_i \ \wedge\ \bigwedge_{i \in T} v_0 \ \wedge\ \bigwedge_{i \notin S} v_i. \end{align*} Since $v_0$ is the multiplicative identity, $\bigwedge_{i \in T} v_0 = v_0$ (treated as the empty restriction, so it disappears from the product). Hence each term is a wedge product of a subset of $\{v_1, \dots, v_d\}$, which is one of the generators of $\mathrm{RM}(d, d)$. Therefore $\mathbb{1}_{\{p\}}$ is an $\mathbb{F}_2$-linear combination of wedge products of length $\leq d$, i.e., \begin{align*} \mathbb{1}_{\{p\}} \in \mathrm{RM}(d, d). \end{align*} Since $p \in X$ was arbitrary and $\{\mathbb{1}_{\{p\}} : p \in X\}$ spans $\mathbb{F}_2^n$, we conclude $\mathrm{RM}(d, d) = \mathbb{F}_2^n$. In particular, the wedge products span $\mathbb{F}_2^n$. [/step] [step:Conclude that the wedge products form a basis, proving (i)] The family of wedge products indexed by subsets of $\{1, \dots, d\}$ has cardinality $2^d = \dim \mathbb{F}_2^n$ (Step 2) and spans $\mathbb{F}_2^n$ (Step 5). A spanning set of cardinality equal to the dimension of the ambient space is a basis. This proves (i). [/step] [step:Deduce part (ii) from the basis property] By definition, $\mathrm{RM}(d, r)$ is the $\mathbb{F}_2$-span of the wedge products with length $s \leq r$. These wedge products form a subset of the basis from (i) and are therefore linearly independent. Their cardinality is \begin{align*} \#\{(s; i_1, \dots, i_s) : 0 \leq s \leq r,\ 1 \leq i_1 < \cdots < i_s \leq d\} = \sum_{s=0}^{r} \binom{d}{s}. \end{align*} A linearly independent spanning set of $\mathrm{RM}(d, r)$ is a basis, so \begin{align*} \operatorname{rank}(\mathrm{RM}(d, r)) = \dim_{\mathbb{F}_2} \mathrm{RM}(d, r) = \sum_{s=0}^{r} \binom{d}{s}. \end{align*} This proves (ii) and completes the proof. [/step]