[proofplan]
We prove $\mathcal{B}$ is a basis of $C$ in three steps: containment, linear independence, and spanning. Containment is immediate because $g \in C$ and $C$ is an ideal. Linear independence follows from the fact that the polynomials $X^i g(X)$ for $0 \leq i \leq n - k - 1$ have pairwise distinct degrees strictly less than $n$, so their reductions modulo $X^n - 1$ are these same polynomials, and distinct-degree polynomials are linearly independent. For spanning, every codeword has the form $f(X) g(X) \bmod (X^n - 1)$ for some $f \in \mathbb{F}_2[X]$; polynomial division lets us take $\deg f < n - k$, and such $f$ expands as $\mathbb{F}_2$-linear combinations of $1, X, \ldots, X^{n-k-1}$, giving the spanning property.
[/proofplan]
[step:Verify that $X^i g(X) \in C$ for $0 \leq i \leq n - k - 1$]
By the theorem "Existence and Uniqueness of the Generator Polynomial", $C = (g)$ as an ideal of $\mathbb{F}_2[X]/(X^n - 1)$. In particular, for every $f \in \mathbb{F}_2[X]$, we have $fg \bmod (X^n - 1) \in C$. Taking $f = X^i$ for $0 \leq i \leq n - k - 1$ gives $X^i g \bmod (X^n - 1) \in C$. Hence $\mathcal{B} \subseteq C$.
Moreover, for $0 \leq i \leq n - k - 1$, we have $\deg(X^i g) = i + k \leq (n - k - 1) + k = n - 1 < n$, so $X^i g$ is already its own reduction modulo $X^n - 1$. We identify each basis candidate with a polynomial of degree $< n$ in $\mathbb{F}_2[X]$.
[/step]
[step:Prove linear independence by comparing leading monomials]
Suppose $\lambda_0, \lambda_1, \ldots, \lambda_{n-k-1} \in \mathbb{F}_2$ satisfy
\begin{align*}
\sum_{i=0}^{n-k-1} \lambda_i X^i g(X) = 0 \quad \text{in } \mathbb{F}_2[X]/(X^n - 1).
\end{align*}
By Step 1, each $X^i g$ has degree $i + k < n$, so the sum on the left, viewed as a polynomial in $\mathbb{F}_2[X]$, has degree at most $n - 1 < n$ and therefore equals its own reduction modulo $X^n - 1$. Thus
\begin{align*}
\sum_{i=0}^{n-k-1} \lambda_i X^i g(X) = 0 \quad \text{in } \mathbb{F}_2[X].
\end{align*}
If not all $\lambda_i$ are zero, let $I := \max\{ i : \lambda_i \neq 0 \}$. Then the coefficient of $X^{I + k}$ in the sum equals $\lambda_I \cdot 1 = \lambda_I$, because:
- The polynomial $\lambda_I X^I g(X)$ has leading term $\lambda_I X^{I + k}$ (the generator $g$ is monic of degree $k$ by its definition in Theorem 1669).
- For $i < I$, the polynomial $\lambda_i X^i g(X)$ has degree $i + k < I + k$, hence contributes $0$ to the coefficient of $X^{I + k}$.
So the coefficient of $X^{I + k}$ in the sum is $\lambda_I \neq 0$, contradicting that the sum is the zero polynomial. Hence all $\lambda_i = 0$, and $\mathcal{B}$ is linearly independent over $\mathbb{F}_2$.
[guided]
The linear independence is a clean consequence of degree-watching. The candidate basis consists of polynomials whose "leading monomials" are
\begin{align*}
X^k,\ X^{k+1},\ X^{k+2},\ \ldots,\ X^{n-1}
\end{align*}
— a pairwise distinct list of monomials, all of degree $\leq n - 1$.
Why does distinctness of leading monomials imply linear independence? Consider a hypothetical non-trivial dependence
\begin{align*}
\sum_{i=0}^{n-k-1} \lambda_i X^i g(X) = 0.
\end{align*}
The first thing to verify is that this equation in $\mathbb{F}_2[X]/(X^n - 1)$ is the same as an equation in $\mathbb{F}_2[X]$ — otherwise the ambient relation $X^n \equiv 1$ could allow cancellations that do not occur in $\mathbb{F}_2[X]$. But each summand $X^i g(X)$ has degree $i + k \leq n - 1 < n$, so the whole sum has degree $< n$, and reduction modulo $X^n - 1$ leaves it unchanged. The equation therefore holds already in $\mathbb{F}_2[X]$.
Now, suppose $\lambda_I$ is the coefficient of the highest surviving term, $I = \max\{i : \lambda_i \neq 0\}$. The polynomial $\lambda_I X^I g(X)$ has leading term $\lambda_I X^{I + k}$, since $g$ is monic of degree $k$. The other summands with $i < I$ have strictly smaller degrees $i + k < I + k$ and cannot contribute to the coefficient of $X^{I + k}$. Reading off this coefficient from the zero polynomial gives $\lambda_I = 0$, contradiction.
The conclusion: all $\lambda_i = 0$, so $\mathcal{B}$ is linearly independent over $\mathbb{F}_2$.
[/guided]
[/step]
[step:Prove spanning using polynomial division by a degree-$(n - k)$ polynomial]
Let $c \in C$. By the theorem "Existence and Uniqueness of the Generator Polynomial", there exists $f \in \mathbb{F}_2[X]$ such that $c = fg \bmod (X^n - 1)$. We show that $c$ can be written as an $\mathbb{F}_2$-linear combination of the elements of $\mathcal{B}$.
Recall $g \mid X^n - 1$, and write $X^n - 1 = g(X) h(X)$ with $h \in \mathbb{F}_2[X]$. Then $\deg h = n - k$ because $\deg(X^n - 1) = n$ and $\deg g = k$.
Divide $f$ by $h$ in $\mathbb{F}_2[X]$ (note $h$ is monic — both $X^n - 1$ and $g$ are monic, so $h = (X^n - 1)/g$ is monic, and division by a monic polynomial is well-defined):
\begin{align*}
f(X) = q(X) h(X) + r(X), \qquad \deg r < \deg h = n - k \quad \text{or } r = 0.
\end{align*}
Multiplying by $g$:
\begin{align*}
f(X) g(X) = q(X) h(X) g(X) + r(X) g(X) = q(X)(X^n - 1) + r(X) g(X).
\end{align*}
Reducing modulo $X^n - 1$:
\begin{align*}
c = f g \bmod (X^n - 1) = r(X) g(X) \bmod (X^n - 1).
\end{align*}
Since $\deg(rg) < (n - k) + k = n$, the reduction is trivial and $c = r(X) g(X)$ as elements of $\mathbb{F}_2[X]/(X^n - 1)$.
Write $r(X) = \sum_{i=0}^{n-k-1} r_i X^i$ with $r_i \in \mathbb{F}_2$ (and $r_i = 0$ for $i \geq \deg r + 1$). Then
\begin{align*}
c = r(X) g(X) = \sum_{i=0}^{n-k-1} r_i \, X^i g(X),
\end{align*}
an $\mathbb{F}_2$-linear combination of elements of $\mathcal{B}$. Hence $\mathcal{B}$ spans $C$.
[/step]
[step:Combine to conclude $\mathcal{B}$ is a basis and determine $\dim C$]
By Step 1, $\mathcal{B} \subseteq C$. By Step 2, $\mathcal{B}$ is linearly independent in $\mathbb{F}_2[X]/(X^n - 1)$. By Step 3, $\mathcal{B}$ spans $C$. Therefore $\mathcal{B}$ is a basis of $C$ as an $\mathbb{F}_2$-vector space.
Since $|\mathcal{B}| = n - k$,
\begin{align*}
\dim_{\mathbb{F}_2} C = n - k,
\end{align*}
completing the proof.
[/step]
