Fundamental Polynomial Method

Settings

Let $\mathbb{F}$ be a field, Let ${\text{Poly}}_D({\mathbb{F}}^n)$ be the space of polynomials in $n$ variables, with coefficients in $\mathbb{F}$, and with total degree at most $D$. If the $n$ variables are $x_1,\dots ,x_n$, then ${\text{Poly}}_D({\mathbb{F}}^n)$ is the subset of the polynomial ring $\mathbb{F}[x_1,\dots ,x_n]$ consisting of polynomials of degree at most $D$. The space ${\text{Poly}}_D({\mathbb{F}}^n)$ is a vector space over the field $\mathbb{F}$.

Proposition

1. Suppose that $S\subseteq {\mathbb{F}}^n$ is a finite set. If $\text{Dim }{\text{Poly}}_D({\mathbb{F}}^n)>|S|$, then there is a non-zero polynomial $P\in {\text{Poly}}_D({\mathbb{F}}^n)$ which vanishes on $S$.
2. The dimension of ${\text{Poly}}_D({\mathbb{F}}^n)$ is $\left(\genfrac{}{}{0ex}{}{D+n}{n}\right)$. In particular, $\text{Dim }{\text{Poly}}_D({\mathbb{F}}^n)\ge D^n/n!$
3. If $S\subset {\mathbb{F}}^n$ and $|S|<\left(\genfrac{}{}{0ex}{}{D+n}{n}\right)$, then there is a non-zero polynomial $P\in {\text{Poly}}_D({\mathbb{F}}^n)$ that vanishes on $S$.
4. For any $n\ge 2$, for any finite set $S\subset {\mathbb{F}}^n$, there is a non-zero polynomial that vanishes on $S$ with degree $\le n|S{|}^{1/n}$.

Proposition

If $P\in {\text{Poly}}_D(\mathbb{F})$, and if $P$ vanishes at $D+1$ points, then $P$ is the zero polynomial.

Sketch of Proof The proposition we want follows from the combination of following lemmas.

1. If $P(x)\in {\text{Poly}}_D(\mathbb{F})$ is a polynomial in one variable and $x_1\in \mathbb{F}$, then we can write $P$ in the form $P(x)=(x-x_1)P_1(x)+r,$ where $P_1(x)\in {\text{Poly}}_{D-1}(\mathbb{F})$ and $r\in \mathbb{F}$.
2. If $P(x)\in {\text{Poly}}_D(\mathbb{F})$ is a polynomial over a field $\mathbb{F}$ and $P(x_1)=0$ for some $x_1\in \mathbb{F}$, then $P(x)=(x-x_1)P_1(x)$ for some polynomial $P_1\in {\text{Poly}}_{D-1}(\mathbb{F})$.

Vanishing Lemma

A line $l\subset {\mathbb{F}}^n$ is a 1-dimensional affine subspace. If $P\in {\text{Poly}}_D({\mathbb{F}}^n)$ and $P$ vanishes at $D+1$ points on a line $l$, then $P$ vanishes at every point of $l$.