[proofplan] We combine the [Multivariate Division Lemma](/theorems/2614) with the [Vanishing Criterion for Low-Degree Polynomials](/theorems/2615). First, divide $f$ by the vanishing polynomials $g_1, \ldots, g_n$ using the multivariate division lemma to write $f = \sum h_i g_i + r$ where $r$ has low partial degrees. Since $f$ and every $g_i$ vanish on $S$, the remainder $r$ also vanishes on $S$. The vanishing criterion then forces $r = 0$, yielding the desired decomposition. [/proofplan]

[step:Divide $f$ by the vanishing polynomials using the Multivariate Division Lemma]For each $i = 1, \ldots, n$, the polynomial $g_i(X_i) = \prod_{s \in S_i}(X_i - s)$ is monic of degree $d_i := |S_i|$ in $X_i$. By the [Multivariate Division Lemma](/theorems/2614) applied to $f$ and the monic polynomials $g_1, \ldots, g_n$, there exist $h_1, \ldots, h_n, r \in \mathbb{F}[X_1, \ldots, X_n]$ such that \begin{align*} f = \sum_{i=1}^{n} h_i g_i + r, \end{align*} with the following bounds: \begin{align*} \deg h_i &\leq \deg f - d_i = \deg f - |S_i|, \\ \deg_{X_i} r &\leq d_i - 1 = |S_i| - 1, \quad \text{for each } i = 1, \ldots, n, \\ \deg r &\leq \deg f. \end{align*}[/step]

[guided]The [Multivariate Division Lemma](/theorems/2614) requires that each $g_i(X_i)$ be a monic polynomial in $X_i$ over $R$, viewed as an element of $R[X_1, \ldots, X_n]$. Here $R = \mathbb{F}$ is a field. Each $g_i(X_i) = \prod_{s \in S_i}(X_i - s)$ is indeed monic in $X_i$: it is a product of $|S_i|$ monic linear factors in $X_i$, so its leading coefficient (as a polynomial in $X_i$) is $1$. Its degree in $X_i$ is $d_i = |S_i|$. The multivariate division lemma produces the decomposition $f = \sum h_i g_i + r$ where the remainder $r$ has $\deg_{X_i} r < d_i = |S_i|$ for each $i$. This bound on the partial degrees of $r$ is exactly the hypothesis needed to apply the vanishing criterion in the next step.[/guided]

[step:Show the remainder $r$ vanishes on $S = S_1 \times \cdots \times S_n$] Let $(x_1, \ldots, x_n) \in S_1 \times \cdots \times S_n$. For each $i$, since $x_i \in S_i$, the factor $(X_i - x_i)$ appears in the product $g_i(X_i) = \prod_{s \in S_i}(X_i - s)$, so $g_i(x_i) = 0$. Evaluating the decomposition at $(x_1, \ldots, x_n)$: \begin{align*} f(x_1, \ldots, x_n) = \sum_{i=1}^{n} h_i(x_1, \ldots, x_n)\, g_i(x_i) + r(x_1, \ldots, x_n). \end{align*} The left-hand side is zero (since $f$ vanishes on $S$ by hypothesis), and each term $h_i(x_1, \ldots, x_n) \cdot g_i(x_i) = h_i(x_1, \ldots, x_n) \cdot 0 = 0$. Therefore $r(x_1, \ldots, x_n) = 0$. Since $(x_1, \ldots, x_n) \in S$ was arbitrary, $r$ vanishes identically on $S$. [/step]

[step:Apply the Vanishing Criterion to conclude $r = 0$]The remainder $r \in \mathbb{F}[X_1, \ldots, X_n]$ satisfies $\deg_{X_i} r \leq |S_i| - 1 < |S_i|$ for each $i = 1, \ldots, n$ (from the division lemma), and $r$ vanishes on $S = S_1 \times \cdots \times S_n$ (from the previous step). The sets $S_1, \ldots, S_n$ are non-empty finite subsets of the field $\mathbb{F}$, so the hypotheses of the [Vanishing Criterion for Low-Degree Polynomials](/theorems/2615) are satisfied. The criterion gives $r = 0$. Therefore \begin{align*} f = \sum_{i=1}^{n} h_i g_i, \end{align*} with $\deg h_i \leq \deg f - |S_i|$ for each $i$, as required.[/step]

[guided]This is where the two preceding results fit together. The [Multivariate Division Lemma](/theorems/2614) produces a decomposition with a remainder $r$ satisfying $\deg_{X_i} r < |S_i|$. The [Vanishing Criterion for Low-Degree Polynomials](/theorems/2615) says that a polynomial with such low partial degrees that vanishes on the grid $S_1 \times \cdots \times S_n$ must be identically zero. Since $r$ vanishes on $S$ (because $f$ and every $g_i$ vanish there), the vanishing criterion forces $r = 0$. The result is that $f$ lies in the ideal $(g_1, \ldots, g_n)$ of $\mathbb{F}[X_1, \ldots, X_n]$, with the explicit degree bound $\deg h_i \leq \deg f - |S_i|$ on each coefficient. This ideal is precisely the vanishing ideal of the grid $S = S_1 \times \cdots \times S_n$ (restricted to polynomials that split as a sum involving the individual vanishing polynomials $g_i$), and the decomposition makes the membership constructive.[/guided]