[proofplan] We divide out each variable successively using the one-variable [Division Algorithm for Monic Polynomials](/theorems/2613). At stage $k$, we treat the current polynomial as a univariate polynomial in $X_k$ with coefficients in $R[X_1, \ldots, \widehat{X_k}, \ldots, X_n]$ and divide by the monic polynomial $g_k(X_k)$. The remainder from each stage becomes the dividend for the next. After $n$ stages, the accumulated quotients $h_1, \ldots, h_n$ and the final remainder $r$ satisfy the stated identity and degree bounds. [/proofplan] [step:Divide by $g_1$ in the variable $X_1$] View $f$ as an element of $S_1[X_1]$ where $S_1 = R[X_2, \ldots, X_n]$. The polynomial $g_1(X_1) \in R[X_1] \subseteq S_1[X_1]$ is monic of degree $d_1$ in $X_1$. By the [Division Algorithm for Monic Polynomials](/theorems/2613) applied in the ring $S_1[X_1]$, there exist $h_1, r_1 \in S_1[X_1] = R[X_1, \ldots, X_n]$ such that \begin{align*} f = h_1 g_1 + r_1, \end{align*} with $\deg_{X_1} r_1 < d_1$ and $\deg_{X_1} h_1 \leq \deg_{X_1} f - d_1$. Since the division algorithm in $X_1$ does not modify coefficients in $X_2, \ldots, X_n$ (it only performs operations in the coefficient ring $S_1$), we have $\deg_{X_j} h_1 \leq \deg_{X_j} f$ and $\deg_{X_j} r_1 \leq \deg_{X_j} f$ for every $j \geq 2$. For the total degree, the division algorithm subtracts multiples of $g_1$ from $f$, and each such multiple has total degree at most $\deg f$ (since $g_1$ is monic of degree $d_1$ and the multiplier has total degree at most $\deg f - d_1$), so $\deg h_1 \leq \deg f - d_1$ and $\deg r_1 \leq \deg f$. [guided] The strategy is to treat $f$ as a polynomial in one variable at a time and apply the univariate division algorithm repeatedly. At the first stage, we single out $X_1$. Formally, consider the ring $S_1 = R[X_2, \ldots, X_n]$. Every polynomial in $R[X_1, \ldots, X_n]$ can be viewed as a polynomial in $X_1$ whose coefficients lie in $S_1$. The polynomial $g_1(X_1) \in R[X_1]$ is monic of degree $d_1$ in $X_1$, so it is also monic of degree $d_1$ when viewed in $S_1[X_1]$. The ring $S_1$ is a commutative ring with identity (as a polynomial ring over $R$), so the [Division Algorithm for Monic Polynomials](/theorems/2613) applies in $S_1[X_1]$. The algorithm produces $h_1, r_1 \in S_1[X_1] = R[X_1, \ldots, X_n]$ with $f = h_1 g_1 + r_1$ and $\deg_{X_1} r_1 < d_1$, $\deg_{X_1} h_1 \leq \deg_{X_1} f - d_1$. Why do the partial degrees in $X_j$ ($j \geq 2$) not increase? The division algorithm for univariate polynomials over a ring works by repeatedly subtracting $(\text{leading coefficient of dividend}) \cdot X_1^{d-d_1} \cdot g_1$ where $d = \deg_{X_1}(\text{current dividend})$. The "leading coefficient of the dividend" is an element of $S_1 = R[X_2, \ldots, X_n]$ whose partial degrees in $X_j$ are bounded by $\deg_{X_j} f$. Multiplying by $X_1^{d - d_1} g_1$ does not introduce any power of $X_j$ for $j \geq 2$, since $g_1 \in R[X_1]$ involves only $X_1$. So each subtraction step preserves the bound $\deg_{X_j}(\text{remainder}) \leq \deg_{X_j} f$. For the total degree: $h_1 g_1$ has total degree $\deg h_1 + d_1$ (since $g_1$ is monic, the leading terms do not cancel), and since $f = h_1 g_1 + r_1$ with $\deg r_1 \leq \deg f$, we get $\deg h_1 + d_1 \leq \deg f$, i.e., $\deg h_1 \leq \deg f - d_1$. [/guided] [/step] [step:Iterate: divide $r_{k-1}$ by $g_k$ in the variable $X_k$ for $k = 2, \ldots, n$] Set $r_0 = f$. Having obtained $r_{k-1}$ at stage $k-1$, view $r_{k-1}$ as an element of $S_k[X_k]$ where $S_k = R[X_1, \ldots, \widehat{X_k}, \ldots, X_n]$. Since $g_k(X_k)$ is monic of degree $d_k$ in $X_k$, the [Division Algorithm for Monic Polynomials](/theorems/2613) in $S_k[X_k]$ gives \begin{align*} r_{k-1} = h_k g_k + r_k, \end{align*} with $\deg_{X_k} r_k < d_k$ and $\deg_{X_k} h_k \leq \deg_{X_k} r_{k-1} - d_k$. We verify the degree bounds propagate. By induction on $k$: - **Partial degree in $X_k$:** $\deg_{X_k} h_k \leq \deg_{X_k} r_{k-1} - d_k \leq \deg_{X_k} f - d_k$, since the division steps for $g_1, \ldots, g_{k-1}$ did not increase the partial degree in $X_k$ (each $g_i$ for $i < k$ involves only $X_i$, not $X_k$). - **Partial degree in $X_j$ for $j \neq k$:** The division by $g_k$ in $X_k$ does not modify partial degrees in other variables, so $\deg_{X_j} h_k \leq \deg_{X_j} r_{k-1} \leq \deg_{X_j} f$ and $\deg_{X_j} r_k \leq \deg_{X_j} r_{k-1} \leq \deg_{X_j} f$. - **Total degree:** $\deg r_{k-1} \leq \deg f$ (by induction), so $\deg h_k \leq \deg r_{k-1} - d_k \leq \deg f - d_k$ and $\deg r_k \leq \deg r_{k-1} \leq \deg f$. [guided] At each stage $k = 1, 2, \ldots, n$, we perform a univariate division in the variable $X_k$. The input at stage $k$ is the remainder $r_{k-1}$ from the previous stage (with $r_0 = f$). We view $r_{k-1}$ as a polynomial in $X_k$ with coefficients in $S_k = R[X_1, \ldots, \widehat{X_k}, \ldots, X_n]$ and divide by $g_k(X_k)$, which is monic of degree $d_k$. The critical observation is that dividing by $g_k$ in the variable $X_k$ does not disturb the partial degrees in any other variable $X_j$ with $j \neq k$. This is because $g_k \in R[X_k]$ involves only $X_k$: when we subtract a multiple $c(X_1, \ldots, \widehat{X_k}, \ldots, X_n) \cdot X_k^e \cdot g_k$ from the remainder, the coefficient $c$ comes from the existing coefficients of $r_{k-1}$ (which already satisfy $\deg_{X_j} c \leq \deg_{X_j} f$), and $g_k$ contributes no power of $X_j$. So the bound $\deg_{X_j} r_k \leq \deg_{X_j} f$ is maintained. Similarly, previous divisions by $g_1, \ldots, g_{k-1}$ did not increase the partial degree in $X_k$: each $g_i$ for $i < k$ involves only $X_i$, not $X_k$. Therefore the bound $\deg_{X_k} r_{k-1} \leq \deg_{X_k} f$ holds at the start of stage $k$, and after division we get $\deg_{X_k} h_k \leq \deg_{X_k} f - d_k$. For the total degree, since $r_{k-1}$ has total degree at most $\deg f$ and $g_k$ is monic of degree $d_k$, the quotient $h_k$ satisfies $\deg h_k \leq \deg f - d_k$ and the new remainder satisfies $\deg r_k \leq \deg f$. [/guided] [/step] [step:Assemble the decomposition $f = \sum_{i=1}^n h_i g_i + r$] Setting $r = r_n$, we unwind the chain of divisions: \begin{align*} f &= h_1 g_1 + r_1 \\ &= h_1 g_1 + h_2 g_2 + r_2 \\ &\;\;\vdots \\ &= \sum_{i=1}^{n} h_i g_i + r_n = \sum_{i=1}^{n} h_i g_i + r. \end{align*} The remainder $r = r_n$ satisfies $\deg_{X_i} r < d_i$ for each $i = 1, \ldots, n$: the bound $\deg_{X_k} r_k < d_k$ was established at stage $k$, and subsequent divisions by $g_{k+1}, \ldots, g_n$ (in variables $X_{k+1}, \ldots, X_n$) do not increase $\deg_{X_k} r_k$ because those $g_i$ involve only $X_i \neq X_k$. The bounds $\deg r \leq \deg f$, $\deg h_i \leq \deg f - d_i$, $\deg_{X_i} h_i \leq \deg_{X_i} f - d_i$, and $\deg_{X_j} h_i \leq \deg_{X_j} f$ were verified at each stage. [/step]