2. Null subsets

We introduce the nullity of a finite subset of a field as the lacunarity of an associated polynomial. Let it be agreed that, throughout the paper, subsets are always understood to be non-empty.

Let $F$ be a field, and let $A\subseteq F$ be a finite subset. The characteristic polynomial of $A$ is the polynomial $\Pi _A\in F[X]$ given by

\begin{align*} \Pi _A(X)=\prod _{a\in A} (X-a). \end{align*}

Being $0$ -null is a void condition, so any finite subset satisfies it. A $1$ -null set is commonly known as a zero-sum set. Clearly, the condition of being $\lambda$ -null gets stronger as $\lambda$ increases.

In the next result, we collect several observations on the calculus of null sets. The straightforward arguments are left to the reader.

We interpret nullity as structure. There is a two-way correlation supporting this conceptual point. On the one hand, subsets with arithmetic structure exhibit high nullity. On the other hand, subsets with very high nullity tend to be rather constrained.

Example 2.6. Let $F$ be a field of positive characteristic $p$ . Let $A$ be a coset of a finite additive subgroup; discard the degenerate case when $A$ is a singleton, that is, a coset of the additive subgroup $\{0\}$ . Then $A$ is $\lambda$ -null for $\lambda =(1-p^{-1})|A|-1$ .

Indeed, note first that $|A|=p^e$ for some positive integer $e$ ; this is due to the fact that $A$ can be viewed as an affine space over the prime subfield of $F$ . The key point about the characteristic polynomial of $A$ is that it takes the form

(1) \begin{align} \Pi _A(X)=X^{p^e}+c_{e-1} X^{p^{e-1}}+\dots +c_1 X^p+c_0 X+c_{-1}. \end{align}

This fact is due to Oystein Ore [Reference Ore16]; see also [Reference Artin2], as well as [Reference Lidl and Niederreiter14, Thm.3.57] for the finite field case. We present another argument, which we believe to be new, in Example 4.2. The form of $\Pi _A(X)$ immediately implies that $A$ is $\lambda$ -null for $\lambda =p^e-(p^{e-1}+1)=(1-p^{-1})|A|-1$ .

This nullity level cannot be increased, in general, as the following example shows. Let ${\mathbb{F}}_q$ be a finite field with $q=p^{e+1}$ elements. Consider the trace map $\mathrm{Tr}\;:\;{\mathbb{F}}_q\to{\mathbb{F}}_p$ , given by $\mathrm{Tr}(a)=a+a^p+\dots +a^{p^e}$ . The subset $A=\{a\in{\mathbb{F}}_q\;:\;\mathrm{Tr}(a)=0\}$ is an additive subgroup of size $p^e$ . It is readily seen that its characteristic polynomial is $\Pi _A(X)=X^{p^e}+X^{p^{e-1}}+\dots +X^p+X$ .

3. The structured Combinatorial Nullstellensatz

The following is our first main result.

Theorem 3.1. Let $A_1,\dots,A_n$ be $\lambda$ -null finite subsets of a field $F$ . Assume that a polynomial $f\in F[X_1, \dots, X_n]$ contains a monomial $X_1^{k_1}\dots X_n^{k_n}$ with non-zero coefficient, such that $k_1\lt |A_1|,\dots, k_n\lt |A_n|$ and

\begin{equation*}\deg\!(f)\leq k_1+\dots +k_n +\lambda .\end{equation*}

Then $f(a)\neq 0$ for some grid point $a\in A_1\times \dots \times A_n$ .

The usual Combinatorial Nullstellensatz, Theorem 1.1, corresponds to the case $\lambda =0$ of the above theorem.

Theorems 1.2, 1.3, and 1.4 from the Introduction are immediate applications of the above theorem. If each one of $A_1,\dots,A_n$ is a zero-sum subset, then they are jointly $1$ -null. If each one of $A_1,\dots,A_n$ is a coset of a finite multiplicative subgroup then, by Example 2.5, they are jointly $\lambda$ -null for $\lambda =\min \{|A_1|,\dots, |A_n|\}-1$ . If each one of $A_1,\dots,A_n$ is a coset of a finite additive subgroup and the ambient field $F$ has characteristic $p$ , then, by Example 2.6, they are jointly $\lambda$ -null for $\lambda =(1-p^{-1})\min \{|A_1|,\dots, |A_n|\}-1$ .

We give a proof of Theorem 3.1 by exploiting an algebraic result of Alon [Reference Alon1, Thm.1.1] which is closely related to the Combinatorial Nullstellensatz. This algebraic result also goes under the name of Combinatorial Nullstellensatz, though it is much less used, and it is indeed a Nullstellensatz in the sense this term is employed in algebraic geometry; see [Reference Clark7] for more on this point. In a subsequent section, we will also obtain Theorem 3.1 as a consequence of Theorem 6.2.

Proof. Arguing by contradiction, let us assume that $f(a)= 0$ for all grid points $a\in A_1\times \dots \times A_n$ . Then by [Reference Alon1, Thm.1.1], the following holds: there are polynomials $h_1,\dots,h_n\in F[X_1,\dots, X_n]$ so that

(2) \begin{align} f=h_1\cdot \Pi _{A_1}{\kern-1pt}(X_1)+\dots +h_n\cdot \Pi _{A_n}{\kern-1pt}(X_n), \end{align}

and, furthermore, the total degree of each polynomial $h_i$ satisfies

(3) \begin{align} \deg\!(h_i)\leq \deg\!(f)-\deg\!( \Pi _{A_i})=\deg\!(f)-|A_i|. \end{align}

From (2), we deduce that the monomial $X_1^{k_1}\dots X_n^{k_n}$ appears with a non-zero coefficient in some product $h_i\cdot \Pi _{A_i}(X_i)$ . Now we use the hypothesis that $A_i$ is $\lambda$ -null: $\Pi _{A_i}(X_i)$ has the lacunary form

\begin{equation*}\Pi _{A_i}(X_i)=X_i^{|A_i|}+\sum _{r=0}^{|A_i|-\lambda -1} c_r X_i^r.\end{equation*}

In the product $h_i\cdot \Pi _{A_i}(X_i)$ , the monomial $X_1^{k_1}\dots X_n^{k_n}$ cannot arise from $X_i^{|A_i|}$ , the leading term of $\Pi _{A_i}(X_i)$ , since $k_i\lt |A_i|$ . Therefore a term of much lower order, $X_i^r$ for some $r\lt |A_i|-\lambda$ , is involved. This means that the monomial $X_1^{k_1}\dots X_i^{k_i-r}\dots X_n^{k_n}$ appears with a non-zero coefficient in $h_i$ . But then

\begin{align*} \deg\!(h_i)&\geq k_1+\dots +(k_i-r)+\dots +k_n\\[5pt] &\gt k_1+\dots +k_n +\lambda -|A_i|\geq \deg\!(f)-|A_i| \end{align*}

in contradiction with (3).

As an illustration, we prove a structured version of the well-known Cauchy–Davenport inequality. (Let us recall it: if ${\mathbb{F}}_p$ is a finite field with $p$ elements, where $p$ is a prime, and $A, B\subseteq{\mathbb{F}}_p$ , then the sumset $A+B=\{a+b\;:\;a\in A, b\in B\}$ satisfies $A+B={\mathbb{F}}_p$ , or $|A+B|\geq |A|+|B|-1$ .) At this point, we need to introduce a natural notation: given a subset $A\subseteq F$ , we put

\begin{equation*}\lambda (A)=\max \{\lambda\;:\;A \textrm { is } \lambda \textrm {-null}\}.\end{equation*}

Theorem 3.2. Let ${\mathbb{F}}_p$ be a finite field with $p$ elements, where $p$ is a prime, and let $A, B\subseteq{\mathbb{F}}_p$ . Then the sumset $A+B\subseteq{\mathbb{F}}_p$ satisfies

\begin{align*} \lambda (A+B)\geq \min \{\lambda (A),\lambda (B)\}, \end{align*}

or

\begin{align*} |A+B|\geq |A|+|B|+\lambda (A+B). \end{align*}

Informally, this says that a sumset of structured sets is either fairly structured, or else not too small.

Proof. We adapt the argument of [Reference Alon1, Thm.3.2]. Put $C\;:\!=\;A+B$ , and consider the polynomial

\begin{equation*}f=\prod _{c\in C} (X+Y-c)\in {\mathbb {F}}_p[X,Y].\end{equation*}

Then $f$ vanishes over the grid $A\times B$ .

Arguing by contradiction, let us assume that $\lambda (C)\lt \min \{\lambda (A),\lambda (B)\}$ and $|C|\lt |A|+|B|+\lambda (C)$ . Set $\mu \;:\!=\;\lambda (C)+1$ . Then $\mu \leq \min \{\lambda (A),\lambda (B)\}$ and $|C|\leq |A|+|B|+\lambda (C)-1=(|A|-1)+(|B|-1)+\mu$ . Choose non-negative integers $k$ and $\ell$ satisfying $k\leq |A|-1$ , $\ell \leq |B|-1$ , and $|C|=k+\ell +\mu$ .

We may apply Theorem 3.1 since $A$ and $B$ are $\mu$ -null, and $\deg\!(f)=k+\ell +\mu$ , where $k\lt |A|$ and $\ell \lt |B|$ . As $f$ vanishes over the grid $A\times B$ , it follows that the coefficient of $X^{k}Y^{\ell }$ in $f$ is zero. Now let us find, explicitly, the coefficient of $X^kY^\ell$ . Suppose that the characteristic polynomial of $C$ expands as $\Pi _C(Z)=\sum _{r=0}^{|C|} e_rZ^{|C|-r}$ . Then

\begin{align*} f=\Pi _C(X+Y)=\sum _{r=0}^{|C|} e_r(X+Y)^{|C|-r}. \end{align*}

The monomial $X^kY^\ell$ appears in the expansion of $(X+Y)^{k+\ell }$ , which corresponds to $r=\mu$ . Hence, the coefficient of $X^kY^\ell$ equals

\begin{align*} \binom{k+\ell }{k}e_\mu . \end{align*}

Recall that $\mu =\lambda (C)+1$ , which implies that $e_\mu \neq 0$ . Also $k+\ell \lt |C|\leq p$ , which implies that the above binomial coefficient is non-zero in ${\mathbb{F}}_p$ . We have therefore obtained a contradiction.

In principle, the key instance of Theorem 3.1 is when $k_1=|A_1|-1,\dots, k_n=|A_n|-1$ . If one knows this particular case, then one can generalize to arbitrary $k_1\lt |A_1|,\dots, k_n\lt |A_n|$ . The simplest way would be to trim the grid, as in [Reference Alon1], which would be legitimate if we worked over arbitrary grids. Over structured grids, the germane idea is to adapt the polynomial by a degree-raising trick – namely, consider the polynomial

\begin{align*} X_1^{|A_1|-k_1-1}\dots X_n^{|A_n|-k_n-1} f(X_1,\dots,X_n). \end{align*}

The general form of Theorem 3.1 is more flexible in applications, and the proof of Theorem 3.2 above is a case in point. Moving forward, in Section 6, it will be convenient to adopt the case $k_1=|A_1|-1,\dots, k_n=|A_n|-1$ as the main case of interest; this will simplify the formulas appearing therein. However, one should keep in mind the degree-raising trick.

4. Nullity and symmetric moments

We now turn to a different viewpoint on nullity. Again, let $F$ be a field and let $A\subseteq F$ be a finite subset. If $A$ has $m$ elements, and $g(X_1,\dots,X_m)$ is a symmetric polynomial in $m$ variables, then we may evaluate $g$ on $A$ by setting

\begin{equation*}g(A)=g(a_1,\dots,a_m)\end{equation*}

where $a_1,\dots,a_m$ is an enumeration of $A$ . This is unambiguous: the evaluation $g(A)$ depends only on the set $A$ , and not on the actual enumeration of $A$ , since the polynomial $g$ is symmetric.

The elementary symmetric polynomials and the complete symmetric polynomials of degree $r$ in $m$ variables are given by

\begin{align*} e_r(X_1,\dots,X_m)=\sum _{1\leq i_1\lt \dots \lt i_r\leq m} X_{i_1}\dots X_{i_r},\\[5pt] h_r(X_1,\dots,X_m)=\sum _{k_1+\dots +k_m=r} X_1^{k_1}\dots X_m^{k_m}. \end{align*}

By convention, $e_0(X_1,\dots,X_m)=1$ and $h_0(X_1,\dots,X_m)=1$ . Note, in addition, that $e_r(X_1,\dots,X_m)=0$ when $r\gt m$ .

By evaluating the elementary symmetric polynomials and the complete symmetric polynomials on $A$ , one obtains the elementary moments $e_r(A)$ , respectively the complete moments $h_r(A)$ . We may give an alternate description of the nullity of $A$ , in terms of these symmetric moments.

The zeroth moments cannot partake in vanishing, as $e_0(A)=h_0(A)=1$ .

Proof. The equivalence of (i) and (ii) is immediate from Viète’s formula:

(4) \begin{align} \Pi _A(X)=\prod _{a\in A} (X-a)=\sum _{i=0}^{|A|} (\!-\!1)^i e_{i}(A)\: X^{|A|-i}. \end{align}

The elementary and the complete symmetric polynomials are entwined by the identity

\begin{align*} \sum _{i=0}^r (\!-\!1)^i e_{r-i}(X_1,\dots,X_m)\: h_{i}(X_1,\dots,X_m)=0. \end{align*}

Evaluating on a finite subset $A$ gives

(5) \begin{align} \sum _{i=0}^r (\!-\!1)^i e_{r-i}(A)\: h_{i}(A)=0. \end{align}

This relation bridging the two types of moments implies, in particular, the equivalence of (ii) and (iii). The argument uses an obvious induction.

As the proof shows, it is evident that the nullity of $A$ is reflected in the vanishing of elementary moments of $A$ . The purpose of the above lemma is to uncover the less evident link between the nullity of $A$ and the vanishing of complete moments of $A$ . This link will be of key importance for an upcoming result, Theorem 6.2.

Example 4.2. Let $F$ be a field of characteristic $p$ , where $p$ is a prime, and let $A\subseteq F$ be a coset of a finite additive subgroup. We show that $e_r(A)=0$ for all $1\leq r\leq |A|-2$ such that $|A|-r$ is not a power of $p$ . In view of (4), this precisely translates into the statement, made in Example 2.6, that the characteristic polynomial $\Pi _A(X)$ takes the form (1).

Let $k\leq |A|-1$ . Consider the polynomial

\begin{align*} \Delta _k(X)=e_k(X+A)-e_k(A) \end{align*}

where $X+A$ is the translate of the subset $A$ by the indeterminate $X$ . Then $\Delta _k(X)$ has degree at most $k$ , and it admits $|A|$ roots – namely, the elements of the finite additive subgroup underlying $A$ . Therefore $\Delta _k(X)$ is the zero polynomial. Let us put $\Delta _k(X)$ in standard form, so that we can equate its coefficients to $0$ . We have

\begin{align*} e_k(X+A)&=\sum _{B\subseteq A, \: |B|=k\:} \prod _{b\in B} (X+b)=\sum _{B\subseteq A, \: |B|=k\:} \sum _{r=0}^k e_{r}(B)\: X^{k-r}. \end{align*}

As

\begin{align*} \sum _{B\subseteq A, \: |B|=k\:} e_{r}(B)=\binom{|A|-r}{k-r}\: e_{r}(A), \end{align*}

we deduce that

\begin{align*} \Delta _k(X)=e_k(X+A)-e_k(A)=\sum _{r=0}^{k-1} \binom{|A|-r}{k-r}\: e_{r}(A)\: X^{k-r}. \end{align*}

Thus, in $F$ ,

(6) \begin{align} \binom{|A|-r}{k-r}\: e_{r}(A)=0, \qquad 0\leq r\leq k-1. \end{align}

Consider now some $r\in \{1,\dots, |A|-\!2\}$ such that $|A|-r$ is not a power of $p$ . By a well-known property of binomial coefficients, due to Fine [Reference Fine9], there exists $j\in \{1,\dots,|A|-r-1\}$ such that

\begin{align*} \binom{|A|-r}{j} \not \equiv 0 \mod p. \end{align*}

Set $k=j+r$ . Note that $r\lt k\leq |A|-\!1$ , so we are in position to invoke (6). We infer that $e_{r}(A)=0$ , as desired.

Furthermore, we claim that $e_{|A|-1}(A)\neq 0$ . We have $e_{|A|-1}(A)=e_{|A|-1}(c+A)$ for all $c\in F$ since $\Delta _{|A|-1}(X)$ is the zero polynomial. By definition, $A$ is a translate of a finite additive subgroup $A'$ . Thus $e_{|A|-1}(A)=e_{|A|-1}(A')$ . The advantage in replacing the coset $A$ by its underlying subgroup $A'$ , is that we can easily compute

\begin{align*} e_{|A|-1}(A')=\sum _{B\subseteq A^{\prime}, \: |B|={|A|-1}\:} \prod _{b\in B} b=\prod _{b\in A^{\prime}\setminus \{0\}} b \end{align*}

since all but one of the indexing subsets $B$ contain $0$ . The latter product is evidently non-zero.

Let us point out that $e_{|A|-1}(A)$ is the coefficient of $X$ in the characteristic polynomial $\Pi _A(X)$ . Firstly, by (4), this coefficient equals $(\!-\!1)^{|A|-1}\:e_{|A|-1}(A)$ . But $(\!-\!1)^{|A|-1}=1$ in $F$ ; this is clearly true if $p=2$ , whereas for $p\gt 2$ we recall that $|A|$ is odd, being a power of $p$ .

5. Vandermonde subsets

There is yet another fundamental family of symmetric polynomials, the power-sum polynomials

\begin{align*} p_r(X_1,\dots,X_m)=X_1^{r}+\dots + X_m^{r}. \end{align*}

By evaluating them on a finite subset $A\subseteq F$ , we obtain the power-sum moments $p_r(A)$ . These moments are actually classical, whereas the consideration of their elementary and complete counterparts appears to be new.

This terminology resonates with the notion of Vandermonde subset of a finite field, as studied by Peter Sziklai and Marcella Takáts [Reference Sziklai and Takáts19]. The Vandermonde condition shares some general features with nullity: any finite subset is $0$ -Vandermonde; being $\lambda$ -Vandermonde gets stronger as $\lambda$ increases; being $\lambda$ -Vandermonde is stable under the operations indicated in Lemma 2.2.

Linking the power-sum polynomials to the elementary symmetric polynomials is Newton’s formula:

\begin{align*} re_r(X_1,\dots,X_m)+\sum _{i=1}^r (\!-\!1)^i e_{r-i}(X_1,\dots,X_m)\: p_{i}(X_1,\dots,X_m)=0 \end{align*}

for $1\leq r\leq m$ . Evaluating on a finite subset $A$ gives

(7) \begin{align} re_r(A)+\sum _{i=1}^r (\!-\!1)^i e_{r-i}(A)\: p_{i}(A)=0, \qquad 1\leq r\leq |A|. \end{align}

While being $\lambda$ -null and being $\lambda$ -Vandermonde are not equivalent, the two notions can be related by using (7).

In the following example, we illustrate how the nullity and the Vandermonde parameter can be rather different.

Vandermonde subsets are not the main focus of this paper, but they are worth mentioning on two accounts. Firstly, we believe that the power-sum moments are useful for a more systematic study of nullity – a study that we do not attempt herein. For instance, the power-sum viewpoint makes it obvious that, in formally real fields, one can only speak of $1$ -nullity. This observation is not immediate from Definition 2.1. Secondly, Vandermonde subsets fit our main theme – the interplay between polynomials and structured grids. To wit, we have the following pair of results.

Theorem 5.4. Let $A_1,\dots,A_n$ be $\lambda$ -Vandermonde finite subsets of a field $F$ . Let $f\in F[X_1, \dots, X_n]$ be a polynomial with the property that the degree of each variable is at most $\lambda$ . Then

\begin{equation*}\sum _{a\in A_1\times \dots \times A_n} f(a)=f(0) |A_1|\dots |A_n|.\end{equation*}

Theorem 5.5. Let $F$ be a field of characteristic $p$ . Let $A_1,\dots,A_n$ be $\lambda$ -Vandermonde finite subsets of $F$ , such that $p$ divides $|A_1|,\dots, |A_n|$ . Let $f\in F[X_1, \dots, X_n]$ be a polynomial whose degree satisfies $\deg\!(f)\lt n(\lambda +1)$ . Then

\begin{equation*}\sum _{a\in A_1\times \dots \times A_n} f(a)=0.\end{equation*}

Theorems 5.4 and 5.5 are closely related, and we give a joint proof below. But they work somewhat differently: in Theorem 5.5, the underlying grid is a bit more structured, allowing for the degree requirement on $f$ to be relaxed.

Proof of Theorems 5.4 and 5.5. Let $f_{d_1,\dots,d_n}$ denote the coefficient of $X_1^{d_1}\dots X_n^{d_n}$ in $f$ . So

\begin{align*} f=\sum _{d_1,\dots,d_n} f_{d_1,\dots,d_n} \:X_1^{d_1}\dots X_n^{d_n} \end{align*}

where each of $d_1,\dots,d_n$ runs over the non-negative integers. Then

(8) \begin{align} \sum _{a\in A_1\times \dots \times A_n} f(a)=\sum _{d_1,\dots,d_n} f_{d_1,\dots,d_n} \Big ( \sum _{a_1\in A_1}a_1^{d_1}\Big )\dots \Big ( \sum _{a_n\in A_n} a_n^{d_n}\Big ). \end{align}

As $A_1,\dots,A_n$ are $\lambda$ -Vandermonde, we may restrict the summation on the right-hand side of (8) to those tuples satisfying $d_i=0$ or $d_i\gt \lambda$ , for each $i$ .

The degree assumption of Theorem 5.4 is that $f_{d_1,\dots,d_n}=0$ , except possibly when $d_i\leq \lambda$ for each $i$ . Thus, on the right-hand side of (8), only the term corresponding to $d_1=\dots =d_n=0$ remains. We obtain

\begin{equation*}\sum _{a\in A_1\times \dots \times A_n} f(a)=f(0) |A_1|\dots |A_n|.\end{equation*}

Consider now the setup of Theorem 5.5. The cardinality assumption on the sets $|A_1|$ , $\dots$ , $|A_n|$ means that the indexing on the right-hand side of (8) can be further restricted to those tuples satisfying $d_i\gt \lambda$ , for each $i$ . On the other hand the degree assumption on $f$ is that $f_{d_1,\dots,d_n}=0$ when $d_1+\dots +d_n \geq n(\lambda +1)$ . Therefore

\begin{equation*}\sum _{a\in A_1\times \dots \times A_n} f(a)=0\end{equation*}

in this case.

In light of Example 5.3, Theorem 5.5 applies when $A_1,\dots,A_n$ are (cosets of) finite additive subgroups. We deduce the following consequence.

Corollary 5.6. Let $F$ be a field of characteristic $p$ , and let $A_1,\dots,A_n$ be finite additive subgroups of $F$ . Let $f\in F[X_1, \dots, X_n]$ be a polynomial whose degree satisfies

\begin{equation*}\deg\!(f)\lt n\:\big (\!\min \{|A_1|,\dots,|A_n|\}-1\big ).\end{equation*}

Then

\begin{equation*}\sum _{a\in A_1\times \dots \times A_n} f(a)=0.\end{equation*}

We strengthen the above corollary in the next section.

6. The complete coefficient theorem

For the purposes of this section, it will be convenient to introduce a notation. Let $F$ be a field. For each point $a=(a_1,\dots,a_n)$ in a finite grid $A_1\times \dots \times A_n\subseteq F^n$ , put

\begin{align*} w_a=\frac{1}{\Pi '_{\!\!A_1}\kern-1pt(a_1)\dots \Pi'_{\!\!A_n}\kern-1pt(a_n)}. \end{align*}

In this formula, $\Pi '_{\!\!A_1}, \dots, \Pi '_{\!\!A_n}$ are the formal derivatives of the characteristic polynomials of $A_1$ , $\dots$ , $A_n$ . Given a finite subset $A\subseteq F$ , we have $\Pi '_{\!\!A}(a)\neq 0$ for each $a\in A$ since $\Pi _A$ is, by definition, a separable polynomial. We can actually write down an explicit formula:

\begin{align*} \Pi '_{\!\!A}(a)= \prod _{b\in A, b\neq a} (a-b). \end{align*}

We can now state the following Coefficient Theorem.

Theorem 6.1 ([Reference Schauz18, Reference Lasoń13, Reference Karasev and Petrov11]). Let $A_1,\dots,A_n$ be finite subsets of a field $F$ . Assume that $f\in F[X_1, \dots, X_n]$ is a polynomial whose degree satisfies

\begin{equation*}\deg\!(f)\leq (|A_1|-1)+\dots +(|A_n|-1).\end{equation*}

Then the coefficient of the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ in $f$ equals

\begin{align*} \sum _{a\in A_1\times \dots \times A_n} w_a\: f(a). \end{align*}

Our second main result is a generalization of Theorem 6.1, that we term the Complete Coefficient Theorem.

Theorem 6.2. Let $A_1,\dots,A_n$ be $\lambda$ -null finite subsets of a field $F$ . Assume that $f\in F[X_1, \dots, X_n]$ is a polynomial whose degree satisfies

\begin{equation*}\deg\!(f)\leq (|A_1|-1)+\dots +(|A_n|-1)+\lambda .\end{equation*}

Then the coefficient of the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ in $f$ equals

\begin{align*} \sum _{a\in A_1\times \dots \times A_n} w_a\: f(a). \end{align*}

The key role in the proof of the theorem is played by the following fact.

Lemma 6.3 (Sylvester’s identity, cf. [Reference Bhatnagar4]). Let $A$ be a finite subset of a field $F$ , and let $d$ be a non-negative integer. Then

\begin{align*} \sum _{a\in A} \frac{a^{d}}{\Pi '_{\!\!A}(a)}=\begin{cases} 0 & \textrm{ if } 0\leq d\lt |A|-1,\\[5pt] h_{d-|A|+1}(A) & \textrm{ if } d\geq |A|-1. \end{cases} \end{align*}

Proof of Theorem 6.2. Consider the monomial expansion

\begin{align*} f=\sum _{d_1,\dots,d_n} f_{d_1,\dots,d_n} \:X_1^{d_1}\dots X_n^{d_n} \end{align*}

where $d_1,\dots,d_n$ run over the non-negative integers. We can then write

\begin{align*} \sum _{a\in A_1\times \dots \times A_n} w_a\: f(a)=\sum _{d_1,\dots,d_n} f_{d_1,\dots,d_n} \left( \sum _{a_1\in A_1} \frac{a_1^{d_1}}{\Pi '_{\!\!A_1}(a_1)}\right)\dots \left( \sum _{a_n\in A_n} \frac{a_n^{d_n}}{\Pi '_{\!\!A_n}(a_n)}\right). \end{align*}

By Sylvester’s identity, the right-hand sum equals

\begin{align*} &\sum _{d_1\geq |A_1|-1,\dots, d_n\geq |A_n|-1} f_{d_1,\dots,d_n}\cdot h_{d_1-|A_1|+1}(A_1) \dots h_{d_n-|A_n|+1}(A_n)\\[5pt] & \quad=\sum _{r_1\geq 0,\dots, r_n\geq 0} f_{r_1+|A_1|-1,\dots, r_n+ |A_n|-1}\cdot h_{r_1}{\kern-1pt}(A_1) \dots h_{r_n}(A_n). \end{align*}

We need to show that the latter sum equals $f_{|A_1|-1,\dots, |A_n|-1}$ . This is precisely the contribution of the multiindex $(r_1,\dots,r_n)=(0,\dots,0)$ , as $h_0(A)=1$ for any finite subset $A$ . Next, we check that the contribution of a multiindex $(r_1,\dots,r_n)\neq (0,\dots,0)$ vanishes. If $ r_1+\dots +r_n\gt \lambda$ , then $f_{r_1+|A_1|-1,\dots, r_n+ |A_n|-1}=0$ by the degree hypothesis on $f$ . If $r_1+\dots +r_n\leq \lambda$ , then we argue that some $h_{r_i}(A_i)$ vanishes. Indeed, let $i$ be an index for which $r_i\neq 0$ . Then $1\leq r_i\leq \lambda$ . It follows from the $\lambda$ -nullity of $A_i$ , as interpreted through Lemma 4.1, that $h_{r_i}(A_i)=0$ .

Theorem 6.2 might seem daunting, due to the complicated formula of the weight function $w$ . On the one hand, here are two applications in which the weights’ formula is actually irrelevant. Firstly, keep the hypotheses of Theorem 6.2 and assume further that the coefficient of the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ in $f$ is non-zero; then $f$ cannot vanish at each point of the grid $A_1\times \dots \times A_n$ . This is the key case, $k_1=|A_1|-1$ , $\dots$ , $k_n=|A_n|-1$ , of Theorem 3.1. Secondly, if we now assume the coefficient of the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ to be zero, we obtain the following consequence.

Corollary 6.4. Let $A_1,\dots,A_n$ be $\lambda$ -null finite subsets of a field $F$ . Assume that $f\in F[X_1, \dots, X_n]$ is a polynomial whose degree satisfies

\begin{equation*}\deg\!(f)\leq (|A_1|-1)+\dots +(|A_n|-1)+\lambda .\end{equation*}

If the coefficient of the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ in $f$ is zero, then $f$ cannot vanish at all but one point of the grid $A_1\times \dots \times A_n$ .

Over finite fields, the previous corollary yields results in the spirit of Chevalley’s theorem. (Let us recall it: if ${\mathbb{F}}_q$ is a finite field of characteristic $p$ , and $f\in{\mathbb{F}}_q[X_1,\dots,X_n]$ is a polynomial of degree less than $n$ , then $f$ cannot have a single zero in ${\mathbb{F}}_q^n$ .) We illustrate the idea on the following geometric example.

Example 6.5. Let $A_1,\dots,A_n$ be subsets of a finite field ${\mathbb{F}}_q$ , not all singletons. We are interested in the following slicing feature of the grid $A_1\times \dots \times A_n\subseteq{\mathbb{F}}_q^n$ :

(PP) no plane in ${\mathbb{F}}_q^n$ intersects the grid in a single point.

A plane $\pi \subseteq{\mathbb{F}}_q^n$ has an associated polynomial $f_\pi \in{\mathbb{F}}_q[X_1,\dots,X_n]$ of degree $q-1$ whose support is $\pi$ . Namely, if $\pi$ is given by the equation $c_1x_1+\dots +c_nx_n=0$ , then $f_\pi =1-(c_1X_1+\dots +c_nX_n)^{q-1}$ satisfies $f_\pi (x)\neq 0$ if and only if $x\in \pi$ . The intersection of $\pi$ and the grid $A_1\times \dots \times A_n$ consists of those points in the grid where $f_\pi$ does not vanish. We aim to apply Corollary 6.4 to polynomials of the form $f_\pi$ . By requiring that $(|A_1|-1)+\dots +(|A_n|-1)\neq q-1$ , we ensure that the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ does not appear in $f_\pi$ .

The unstructured outcome is the following: if the grid is large, in the sense that

\begin{equation*}(|A_1|-1)+\dots +(|A_n|-1)\gt q-1,\end{equation*}

then (PP) holds. The structured upshot of Corollary 6.4 deals with smaller null grids: if $A_1,\dots,A_n$ are $\lambda$ -null and

\begin{equation*}q-1-\lambda \leq (|A_1|-1)+\dots +(|A_n|-1)\lt q-1,\end{equation*}

then (PP) holds.

On the other hand, we can use Theorem 6.2 over structured grids whose weight function $w$ ends up having a much simpler form. Here are two key examples.

1. (i) Let $A\subseteq F^*$ be a finite multiplicative subgroup. Then the characteristic polynomial of $A$ is of the form $\Pi _A=X^{|A|}-c$ , hence

   \begin{align*} \Pi '_{\!\!A}(a)=|A|\: a^{|A|-1}=|A|\: a^{-1} \end{align*}
   for each $a\in A$ . It follows that, for a grid $A_1\times \dots \times A_n$ defined by finite multiplicative subgroups $A_1,\dots,A_n \subseteq F^*$ , we have
   \begin{align*} w_a=\frac{1}{\Pi '_{\!\!A_1}(a_1)\dots \Pi '_{\!\!A_n}(a_n)}=\frac{a_1\dots a_n}{|A_1\times \dots \times A_n|} \end{align*}
   for each grid point $a=(a_1,\dots,a_n)$ .

2. (ii) Let $A\subseteq F$ be a finite additive subgroup. Then

   \begin{align*} \Pi '_{\!\!A}(a)= \prod _{b\in A, b\neq a} (a-b)=\prod _{b\in A\setminus \{0\}} b \end{align*}
   for each $a\in A$ . Thus, for a grid $A_1\times \dots \times A_n$ defined by finite additive subgroups $A_1,\dots,A_n \subseteq F$ , we have
   \begin{align*} w_a=\frac{1}{\Pi '_{\!\!A_1}(a_1)\dots \Pi '_{\!\!A_n}(a_n)}=\left(\prod _{b_1\in A_1\setminus \{0\}} b_1^{-1}\right)\dots \left(\prod _{b_n\in A_n\setminus \{0\}} b_n^{-1}\right) \end{align*}
   for each grid point $a=(a_1,\dots,a_n)$ . The notable feature in this case is that the weights are constant over the grid. This continues to hold when $A_1,\dots,A_n \subseteq F$ are cosets of finite additive subgroups.

We deduce the following high nullity instances of Theorem 6.2.

Corollary 6.6 (Multiplicative grids). Let $A_1,\dots,A_n$ be finite multiplicative subgroups of $F$ . Assume that $f\in F[X_1, \dots, X_n]$ is a polynomial whose degree satisfies

\begin{align*} \deg\!(f)\leq (|A_1|-1)+\dots +(|A_n|-1)+\min \{ |A_1|,\dots, |A_n|\}-1. \end{align*}

Then the coefficient of the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ in $f$ equals the averaged sum

\begin{align*} \frac{1}{|A_1\times \dots \times A_n|}\sum _{(a_1,\dots,a_n)\in A_1\times \dots \times A_n} a_1\dots a_n f(a_1,\dots,a_n). \end{align*}

Corollary 6.7 (Additive grids). Let $F$ have characteristic $p$ , and let $A_1,\dots,A_n$ be cosets of finite additive subgroups of $F$ . Assume that $f\in F[X_1, \dots, X_n]$ is a polynomial whose degree satisfies

\begin{align*} \deg\!(f)\leq (|A_1|-1)+\dots +(|A_n|-1)+(1-p^{-1})\min \{ |A_1|,\dots, |A_n|\}-1. \end{align*}

If the coefficient of the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ in $f$ is zero, then

\begin{align*} \sum _{a\in A_1\times \dots \times A_n} f(a)=0. \end{align*}

Note that, in the above corollary, the assumptions on $f$ are fulfilled when $\deg\!(f)\lt (|A_1|-1)+\dots +(|A_n|-1)$ ; we thus see that Corollary 6.7 significantly strengthens Corollary 5.6.

Over finite fields, Corollary 6.7 yields results in the spirit of Warning’s theorem. (Recall, this is a refinement of Chevalley’s theorem, stating the following: if ${\mathbb{F}}_q$ is a finite field of characteristic $p$ , and $f\in{\mathbb{F}}_q[X_1,\dots,X_n]$ is a polynomial of degree less than $n$ , then the number of zeroes of $f$ in ${\mathbb{F}}_q^n$ is a multiple of $p$ .) As a simple illustration, we discuss a variation on Example 6.5.

Example 6.8. Let $A_1,\dots,A_n$ be additive subgroups of a finite field ${\mathbb{F}}_q$ of characteristic $p$ . The slicing feature of the grid $A_1\times \dots \times A_n\subseteq{\mathbb{F}}_q^n$ that we are now interested in is

1. (PP $_p$ ) the number of points in which each plane in ${\mathbb{F}}_q^n$ intersects the grid is a multiple of $p$ .

Clearly, property (PP $_p$ ) is stronger than property (PP), considered in Example 6.5; but the grid is also assumed to be more structured.

Consider again the polynomial $f_\pi \in{\mathbb{F}}_q[X_1,\dots,X_n]$ of degree $q-1$ associated to a plane $\pi \subseteq{\mathbb{F}}_q^n$ . As $f_\pi$ takes the value $1$ on $\pi$ , respectively the value $0$ off $\pi$ , we obtain

\begin{align*} \sum _{a\in A_1\times \dots \times A_n} f_\pi\kern-1pt (a)=N_\pi \cdot 1 \end{align*}

where $N_\pi$ denotes the size of the intersection of $\pi$ with the grid. We wish to apply Corollary 6.7 to $f_\pi$ . To ensure that the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ does not appear in $f_\pi$ , we require that $(|A_1|-1)+\dots +(|A_n|-1)\neq q-1$ . If, in addition, we also have that

\begin{equation*}q-1\lt (|A_1|-1)+\dots +(|A_n|-1)+(1-p^{-1})\min \{ |A_1|,\dots, |A_n|\}.\end{equation*}

then $N_\pi \equiv 0$ mod $p$ for each plane $\pi$ , meaning that (PP $_p$ ) holds.

The coefficient theorem 6.1 is designed to determine the coefficient of a top-degree monomial. The complete coefficient theorem 6.2 reaches into the lower-degree monomials of a polynomial. In fact, all coefficients could be uncovered by an evaluation over a suitable structured grid. The ‘complete’ designation of Theorem 6.2 owes largely to this fact, but also to the crucial use of complete symmetric polynomials in its proof.

We illustrate this ‘complete’ viewpoint by the following multivariable interpolation theorem.

Theorem 6.9. Let $A_1,\dots,A_n$ be $\lambda$ -null finite subsets of a field $F$ , neither one a singleton. If $f\in F[X_1, \dots, X_n]$ is a polynomial of degree at most $\lambda$ , then

\begin{align*} f=\sum _{k_1+\dots +k_n\leq \lambda } \!\bigg (\sum _{a\in A_1\times \dots \times A_n} a_1^{|A_1|-k_1-1}\dots a_n^{|A_n|-k_n-1}\: w_a \:f(a)\bigg ) X_1^{k_1}\dots X_n^{k_n}. \end{align*}

Proof. Let $(k_1,\dots,k_n)$ be a tuple of non-negative integers satisfying $k_1+\dots +k_n\leq \lambda$ ; in particular, $k_i\leq \lambda \leq |A_i|-1$ for each $i$ . We have to show that

\begin{equation*}f_{k_1,\dots,k_n}=\sum _{a\in A_1\times \dots \times A_n} a_1^{|A_1|-k_1-1}\dots a_n^{|A_n|-k_n-1}\: w_a \:f(a),\end{equation*}

where $f_{k_1,\dots,k_n}$ denotes the coefficient of $X_1^{k_1}\dots X_n^{k_n}$ in $f$ . We employ the degree-raising trick. Put

\begin{equation*}\tilde {f}=X_1^{|A_1|-k_1-1}\dots X_n^{|A_n|-k_n-1} f.\end{equation*}

Then $f_{k_1,\dots,k_n}$ is the coefficient of the monomial $X_1^{|A_1|-1}\dots X_n^{|A_n|-1}$ in $\tilde{f}$ , and

\begin{align*} \deg\!(\tilde{f})&= (|A_1|-k_1-1)+\dots +(|A_n|-k_n-1)+\deg\!(f)\\[5pt] &\leq (|A_1|-1)+\dots +(|A_n|-1)+\lambda . \end{align*}

Hence, by Theorem 6.1, we have that

\begin{align*} f_{k_1,\dots,k_n}=\sum _{a\in A_1\times \dots \times A_n} w_a\: \tilde{f}(a). \end{align*}

Upon reverting to the original polynomial $f$ , we obtain the desired formula.