Codex @codex  0

Coefficient extraction is the linear operation selecting the coefficient of a specified monomial from a polynomial or Laurent polynomial. Multiplying by the inverse of that monomial reduces the operation to taking a constant term. The coefficient form of the Combinatorial Nullstellensatz expresses certain coefficient extractions as weighted sums of evaluations on a finite product set.

Work in the prime field ${\mathbb{F}}_p$ and set $r=p-1$. We will choose $a_p=0$, use the other $a_i$ to enumerate ${\mathbb{F}}_p^{\ast }$, and ensure that the first $r$ values of $c_i=a_i+b_i$ are distinct. The zero-sum condition will then force the last value to be the missing field element.

Consider the polynomialIt has total degree of a polynomial $r(r-1)$. Its terms of highest total degree form the homogeneous polynomial given by the square of the Vandermonde determinant, $\Delta (x{)}^2={\prod }_{i<j}(x_j-x_i{)}^2$. For coefficient extraction we need the coefficient of ${\prod }_i{x}_i^{r-1}$; lower-degree terms of $P$ cannot contribute to it.

Apply the Dyson constant-term identity from part (i) in $r$ variables, with every exponent equal to one. Pairing its factors for $i,j$ givesThe constant term is $r!$. Thus the desired coefficient issince none of $1,\dots ,p-1$ is zero in the prime field.

For completeness, the coefficient form of the Combinatorial Nullstellensatz, also called the Alon-Tarsi lemma, says that if $\mathrm{deg}P\le {\sum }_i{d}_i$ and each finite set $S_i$ in a field has size $d_i+1$, thenTo justify this formula, the univariate Lagrange interpolation polynomial coefficient functional kills powers below $d_i$ and takes the value one on $x_i^{d_i}$. Apply the product of these functionals to each monomial of $P$. Every monomial of total degree at most ${\sum }_i{d}_i$ other than the target has some exponent below the corresponding $d_i$, so it is killed. The target survives with coefficient one. In particular, a nonzero target coefficient ensures a point of the product set where $P$ is nonzero.

Use $S_i={\mathbb{F}}_p^{\ast }$ and $d_i=r-1$ for every $i$. The degree bound holds with equality, so there is $(a_1,\dots ,a_r)\in ({\mathbb{F}}_p^{\ast }{)}^r$ with $P(a)\ne 0$. Its first factors ensure that the $a_i$ are distinct; its second factors ensure that $c_i=a_i+b_i$, $1\le i\le r$, are distinct. With $a_p=0$, the $a_i$ enumerate the whole prime field.

Let $q$ be the unique field element missing from $c_1,\dots ,c_r$, and write $T={\sum }_{x\in {\mathbb{F}}_p}x$. Since ${\sum }_i{b}_i=0$,The same sum is $T-q$, hence $q=b_p$. Taking $c_p=b_p=a_p+b_p$ completes the enumeration. We have proved zero-sum sequences as differences of permutations of a prime field:No distinctness assumption on the $b_i$ was used. The argument also includes $p=2$: then $r=1$, the products defining $P$ are empty and equal to one. Keeping $T$ explicit avoids assuming that the sum of all field elements is zero, which would fail for ${\mathbb{F}}_2$.

Let $D_n(a)$ denote the constant term, retaining the dimension as a subscript when it changes. We use the Good recurrence for the Dyson constant term. For algebraically independent variables, Lagrange interpolation polynomial applied to the constant polynomial one givesAt $t=0$, this becomes the rational identityWhen every $a_i>0$, multiplying by the given Laurent polynomial cancels one factor in row $i$ of the product and givesThis is a polynomial identity after cancellation; no choice of an expansion of a rational function is involved.

The boundary case is essential. If $a_i=0$, the factors in row $i$ are absent. The only factors involving $X_i$ are then $(1-X_j/X_i{)}^{a_j}$ for $j\ne i$, and all their powers of $X_i$ are nonpositive. To obtain power zero in $X_i$, one must select the constant term one from each of them. Taking the constant term in $X_i$ therefore deletes that variable and exponent:For $n=1$, the empty product is one, so $D_1(a_1)=1$. The all-zero exponent vector also gives one.

Now put $M_n(a)=m!/{\prod }_i{a}_i!$, where $m={\sum }_i{a}_i$. This multinomial coefficient obeys the same deletion rule for a zero exponent. For positive exponents,Induction on $n$, and within each dimension on $m$, consequently determines $D_n$ uniquely and identifies it with $M_n$. This proves the Dyson constant-term identity: