Hypersurface missing just one point

Question

Let $\mathbb F_q$ be a finite field and $n$ an integer.

What is the minimal degree $d = d(q,n)$ of a polynomial $f \in \mathbb F_q[X_1,\dots,X_n]$ such that the set $Z(f)$ of zeros of $f$ in the affine space $\mathbb F_q^n$ has cardinality $q^n-1$, that is misses exactly one point?

It is clear that $d$ is finite, more precisely $d(q,n) \leq n(q-1)$. Indeed, for $f = \prod_{i=1}^n \prod_{\alpha \in \mathbb F_q^\ast} (X_i-\alpha)$, $Z(f)$ is the complement of the origin.

It is also easy to see that $d(q,n) \geq q$, because if $f$ is a polynomial of degree $d<q$, the cardinality of $Z(f)$ is divisible by the characteristic $p$ of $\mathbb F_q$ (Chevalley-Warning), and $\leq d q^{n-1}$ (Schwartz-Zippel), which gives two independent proofs that it cannot be $q^n-1$.

One has $d(2,2)=2$ (e.g. $f(x,y)=xy$ has three zeros) and $d(2,3)=3$ (the zeros of the degree 3 polynomial $f(x,y,z)=1+x+y+z+xy+xz+yz+xyz$ are everything but the origin, and it is not hard to see that you can't do that with a degree 2 polynomial).

But what is the value of $d$ in general?

Answer 1

It's $n(q-1)$. We must have

$$\sum_{x_1,\dots,x_n \in \mathbb F_q}f(x_1,\dots,x_n)=f(0,\dots,0) \neq 0$$

but

$$\sum_{x_1,\dots,x_n \in \mathbb F_q} \prod_i x_i^{e_i}$$

vanishes unless each $e_i$ is a positive multiple of $q-1$, so vanishes for all monomials of degree $<n(q-1)$, so unless the degree of $f$ is at least $n(q-1)$ that sum is zero.

Answer 2

The argument Will Sawin gives is very elegant. However, I think it deserves saying that somewhat surprisingly, there is a much more general result valid in all characteristics:

Theorem. Let $k$ be a field, let $n \in \mathbb Z_{> 0}$, and let $S_1, \ldots, S_n \subseteq k$ be nonempty finite sets. If $f \in k[x_1,\ldots,x_n]$ is a polynomial vanishing on all but one of the points in $S_1 \times \ldots \times S_n \subseteq k^n$ (but not on the last point), then $$\deg f \geq \sum_i \left(\left|S_i\right|-1\right).$$

Conversely, one can easily get a polynomial of that degree vanishing at all points of $S_1 \times \ldots \times S_n$ except $(s_1,\ldots,s_n)$ by setting $$g = \prod_i \prod_{s \in S_i\setminus\{s_i\}} (x_i - s).$$ This corresponds to taking a union of hyperplanes.

Proof of theorem. It is a well-known consequence of Alon's combinatorial Nullstellensatz. Indeed, let $f$ be the polynomial from the statement of the theorem, and let $g$ be as above. Normalising $f$, we may assume $f(s_1,\ldots,s_n) = g(s_1,\ldots,s_n)$.

Now $f - g$ vanishes at all points of $S_1 \times \ldots \times S_n$. Hence, by Theorem 1.2 of Alon's paper, the coefficient of $x_1^{t_1} \cdots x_n^{t_n}$ in $f - g$ is zero (where $t_i = |S_i| - 1$). However, its coefficient in $g$ is $1$. Hence, it also has to appear in $f$ with coefficient $1$, thus $\deg f \geq \sum t_i$. $\square$

(Remark. The case $k = \mathbb R$, $n = 3$, and $S_i = \{0, \ldots, m\}$ is (essentially) IMO 2007, problem 6.)

Answer 3

An even further generalisation of this result is the Alon-Füredi theorem, which says that if a polynomial $f$ does not vanish completely on the "grid" $S = S_1 \times \dots \times S_n$ where $S_i$'s are finite subsets of an arbitrary field $F$, then $f$ does not vanish on at least $\min \prod y_i$ points of the grid as $y_i$'s ranges over integers satisfying $\sum y_i = \sum |S_i| - \deg f$ and $1 \leq y_i \leq |S_i|$.

Clearly, when $\deg f < \sum (|S_i| - 1)$, this minimum value is at least $2$, thus proving that a polynomial vanishing on all points of the grid except one must have degree at least $\sum (|S_i| - 1)$ (and you can easily think of examples of this degree satisfying the condition). In general, this theorem gives you an explicit bound (it is easy to describe what the minimum value is) on the number of non-zeros of an arbitrary polynomial that does not vanish on the grid completely.

Alon-Füredi also works in much more generality, where you can replace $F$ by any commutative ring with identity assuming that for all $i$, for all distinct $a, b$ in $S_i$, the element $a - b$ is not a zero divisor of the ring. In fact, one can generalise further by imposing extra conditions on the degrees of individual variables in the polynomial, see On Zeros of a Polynomial in a Finite Grid. The proof of Alon-Füredi and its generalisation is an easy induction argument using basic properties of single variable polynomials.