[proofplan] We induct on the number of variables $n$. The base case $n = 1$ is the classical fact that a nonzero polynomial of degree $d$ over a field has at most $d$ roots: a polynomial of degree at most $|S_1| - 1$ vanishing at all $|S_1|$ points of $S_1$ must be the zero polynomial. For the inductive step, we expand $h$ as a polynomial in $X_n$ with coefficients in $\mathbb{F}[X_1, \ldots, X_{n-1}]$, fix an arbitrary point in $S_1 \times \cdots \times S_{n-1}$ to reduce to the one-variable base case and conclude each coefficient vanishes on $S_1 \times \cdots \times S_{n-1}$, then invoke the induction hypothesis to show each coefficient is the zero polynomial. [/proofplan] [step:Base case: a univariate polynomial vanishing on more points than its degree is zero] Let $n = 1$. Set $d_1 = |S_1| - 1$. We have $h \in \mathbb{F}[X_1]$ with $\deg_{X_1} h \leq d_1$ and $h(s) = 0$ for every $s \in S_1$, where $|S_1| = d_1 + 1$. A nonzero polynomial of degree at most $d_1$ over a field has at most $d_1$ roots (since $\mathbb{F}[X_1]$ is a principal ideal domain, so each root contributes a linear factor, and the product of $d_1 + 1$ distinct linear factors has degree $d_1 + 1 > d_1$). Since $h$ vanishes at $d_1 + 1$ points but has degree at most $d_1$, the polynomial $h$ must be identically zero. [guided] The base case rests on the fundamental property of polynomials over a field: a nonzero polynomial of degree $d$ has at most $d$ roots. This follows from the fact that $\mathbb{F}[X_1]$ is a Euclidean domain (hence a unique factorisation domain), and each root $\alpha \in \mathbb{F}$ of $h$ gives a factor $(X_1 - \alpha)$ dividing $h$. If $h$ had $d + 1$ distinct roots $\alpha_1, \ldots, \alpha_{d+1}$, then $(X_1 - \alpha_1) \cdots (X_1 - \alpha_{d+1})$ would divide $h$, but this product has degree $d + 1 > d = \deg h$, a contradiction unless $h = 0$. Here $h$ has degree at most $d_1 = |S_1| - 1$ and vanishes at all $|S_1| = d_1 + 1$ elements of $S_1$. Since $d_1 + 1 > d_1 \geq \deg h$, the polynomial $h$ is the zero polynomial. [/guided] [/step] [step:Express $h$ as a polynomial in $X_n$ and evaluate at a generic point of $S_1 \times \cdots \times S_{n-1}$] Assume the result holds for $n - 1$ variables, and let $h \in \mathbb{F}[X_1, \ldots, X_n]$ satisfy $\deg_{X_i} h < |S_i|$ for each $i = 1, \ldots, n$ and $h|_{S_1 \times \cdots \times S_n} = 0$. Set $d_n = |S_n| - 1$. Write $h$ as a polynomial in $X_n$ with coefficients in $\mathbb{F}[X_1, \ldots, X_{n-1}]$: \begin{align*} h = \sum_{j=0}^{d_n} g_j(X_1, \ldots, X_{n-1})\, X_n^j. \end{align*} This expansion has at most $d_n + 1 = |S_n|$ terms because $\deg_{X_n} h \leq d_n$. Fix an arbitrary point $(x_1, \ldots, x_{n-1}) \in S_1 \times \cdots \times S_{n-1}$. Evaluating $h$ at this point yields a univariate polynomial in $X_n$: \begin{align*} h(x_1, \ldots, x_{n-1}, X_n) = \sum_{j=0}^{d_n} g_j(x_1, \ldots, x_{n-1})\, X_n^j \in \mathbb{F}[X_n]. \end{align*} This polynomial has degree at most $d_n = |S_n| - 1$ and vanishes at every $x_n \in S_n$ (since $h$ vanishes on $S_1 \times \cdots \times S_n$). By the base case ($n = 1$), each coefficient $g_j(x_1, \ldots, x_{n-1}) = 0$. [guided] The key idea is dimension reduction. By writing $h$ as a polynomial in $X_n$, we reduce the $n$-variable vanishing problem to a one-variable vanishing problem (in $X_n$) parametrised by points in the first $n - 1$ variables. Fix any $(x_1, \ldots, x_{n-1}) \in S_1 \times \cdots \times S_{n-1}$. The specialisation $X_n \mapsto h(x_1, \ldots, x_{n-1}, X_n)$ is a polynomial of degree at most $d_n$ in one variable over $\mathbb{F}$. It vanishes at every $x_n \in S_n$, and $|S_n| = d_n + 1$. The base case forces this polynomial to be identically zero, which means every coefficient $g_j(x_1, \ldots, x_{n-1})$ equals zero in $\mathbb{F}$. Why does the degree bound $\deg_{X_n} h \leq d_n$ matter? Without it, the specialised polynomial could have degree higher than $d_n$, and vanishing at $d_n + 1$ points would not force it to be zero. The degree condition $\deg_{X_n} h < |S_n| = d_n + 1$ ensures the specialised polynomial has degree at most $d_n$, making the root-count argument sharp. [/guided] [/step] [step:Apply the induction hypothesis to each coefficient $g_j$] The previous step shows that for every $j \in \{0, 1, \ldots, d_n\}$, the polynomial $g_j \in \mathbb{F}[X_1, \ldots, X_{n-1}]$ vanishes on all of $S_1 \times \cdots \times S_{n-1}$. Each $g_j$ satisfies $\deg_{X_i} g_j \leq \deg_{X_i} h < |S_i|$ for $i = 1, \ldots, n-1$ (since the monomial $g_j(X_1, \ldots, X_{n-1}) X_n^j$ appears in $h$, the partial degrees of $g_j$ in $X_i$ cannot exceed those of $h$). By the induction hypothesis (for $n - 1$ variables, with the sets $S_1, \ldots, S_{n-1}$), each $g_j$ is the zero polynomial. Since every coefficient $g_j = 0$, the polynomial $h = \sum_{j=0}^{d_n} g_j X_n^j$ is the zero polynomial. [guided] We have shown that each coefficient $g_j$ vanishes on the entire grid $S_1 \times \cdots \times S_{n-1}$. To apply the induction hypothesis, we need to verify that $g_j$ satisfies the degree conditions: $\deg_{X_i} g_j < |S_i|$ for each $i = 1, \ldots, n - 1$. Since $g_j(X_1, \ldots, X_{n-1}) X_n^j$ is a summand of $h$, the partial degree of $g_j$ in $X_i$ (for $i \leq n - 1$) satisfies $\deg_{X_i} g_j \leq \deg_{X_i} h$. The hypothesis on $h$ gives $\deg_{X_i} h < |S_i|$ for each $i$, so $\deg_{X_i} g_j < |S_i|$. Thus the induction hypothesis applies to each $g_j$ with the sets $S_1, \ldots, S_{n-1}$, and we conclude $g_j = 0$ for every $j$. The induction closes: $h = \sum_{j=0}^{d_n} 0 \cdot X_n^j = 0$. The proof is complete. [/guided] [/step]