7Alon's combinatorial Nullstellensatz
III Combinatorics
7 Alon’s combinatorial Nullstellensatz
Alon’s combinatorial Nullstellensatz is a seemingly unexciting result that has
surprisingly many useful consequences.
Theorem
(Alon’s combinatorial Nullstellensatz)
.
Let
F
be a field, and let
S
1
, . . . , S
n
be non-empty finite subsets of
F
with
|S
i
|
=
d
i
+ 1. Let
f ∈
F
[
X
1
, . . . , X
n
] have degree
d
=
P
n
i=1
d
i
, and let the coefficient of
X
d
1
1
···X
d
n
n
be non-zero. Then f is not identically zero on S = S
1
× ··· × S
n
.
Its proof follows from generalizing facts we know about polynomials in one
variable. Here
R
will always be a ring;
F
always a field, and
F
q
the unique field
of order q = p
n
. Recall the following result:
Proposition
(Division algorithm)
.
Let
f, g ∈ R
[
X
] with
g
monic. Then we can
write
f = hg + r,
where deg h ≤ deg f − deg g and deg r < deg g.
Our convention is that deg 0 = −∞.
Let
X
= (
X
1
, . . . , X
n
) be a sequence of variables, and write
R
[
X
] =
R[X
1
, . . . , X
n
].
Lemma.
Let
f ∈ R
[
X
], and for
i
= 1
, . . . , n
, let
g
i
(
X
i
)
∈ R
[
X
i
]
⊆ R
[
X
]
be monic of degree
deg g
i
=
deg
X
i
g
i
=
d
i
. Then there exists polynomials
h
1
, . . . , h
n
, r ∈ R[X] such that
f =
X
f
i
g
i
+ r,
where
deg h
i
≤ deg f − deg d
i
deg
X
i
r ≤ d
i
− 1
deg
X
i
h
i
≤ deg
X
i
f − d
i
deg
X
i
r ≤ deg
X
i
f
deg
X
j
h
i
≤ deg
X
j
f deg r ≤ deg f
for all i, j.
Proof.
Consider
f
as a polynomial with coefficients in
R
[
X
2
, . . . , X
n
], then divide
by g
1
using the division algorithm. So we write
f = h
1
g
1
+ r
1
.
Then we have
deg
X
1
h
1
≤ deg
X
1
f − d
1
deg
X
1
r
1
≤ d
1
− 1
deg h
1
≤ deg f deg
X
j
r
1
≤ deg
X
j
f
deg
X
j
h
1
≤ deg
X
j
f deg r ≤ deg f.
Then repeat this with f replaced by r
1
, g
1
by g
2
, and X
1
by X
2
.
We also know that a polynomial of one variable of degree
n ≥
1 over a field
has at most n zeroes.
Lemma.
Let
S
1
, . . . , S
n
be non-empty finite subsets of a field
F
, and let
h ∈ F
[
X
]
be such that
deg
X
i
h < |S
i
|
for
i
= 1
, . . . , n
. Suppose
h
is identically 0 on
S = S
1
× ··· × S
n
⊆ F
n
. Then h is the zero polynomial.
Proof.
Let
d
i
=
|S
i
|−
1. We induct on
n
. If
n
= 1, then we are done. For
n ≥
2,
consider
h
as a one-variable polynomial in
F
[
X
1
, . . . , X
n−1
] in
X
n
. Then we can
write
h =
d
n
X
i=0
g
i
(X
1
, . . . , X
n−1
)X
i
m
.
Fix (
x
1
, . . . , x
n−1
)
∈ S
1
× ···S
n−1
, and set
c
i
=
g
i
(
x
1
, . . . , x
n−1
)
∈ F
. Then
P
d
n
i=0
c
i
X
i
n
vanishes on
S
n
. So
c
i
=
g
i
(
x
1
, . . . , x
n−1
) = 0 for all (
x
1
, . . . , x
n−1
)
∈
S
1
× ··· × S
n−1
. So by induction, g
i
= 0. So h = 0.
Another fact we know about polynomials in one variables is that if
f ∈ F
[
X
]
vanishes at z
1
, . . . , z
n
, then f is a multiple of
Q
n
i=1
(X −z
i
).
Lemma. For i = 1, . . . , n, let S
i
be a non-empty finite subset of F, and let
g
i
(X
i
) =
Y
s∈S
i
(X
i
− s) ∈ F[X
i
] ⊆ F [X].
Then if
f ∈ F
[
X
] is identically zero on
S
=
S
1
× ··· × S
n
, then there exists
h
i
∈ F[X], deg h
i
≤ deg f − |S
i
| and
f =
n
X
i=1
h
i
g
i
.
Proof. By the division algorithm, we can write
f =
n
X
i=1
h
i
g
i
+ r,
where
r
satisfies
deg
X
i
r < deg g
i
. But then
r
vanishes on
S
1
×···×S
n
, as both
f and g
i
do. So r = 0.
We finally get to Alon’s combinatorial Nullstellensatz.
Theorem
(Alon’s combinatorial Nullstellensatz)
.
Let
S
1
, . . . , S
n
be non-empty
finite subsets of
F
with
|S
i
|
=
d
i
+ 1. Let
f ∈ F
[
X
] have degree
d
=
P
n
i=1
d
i
,
and let the coefficient of
X
d
1
1
···X
d
n
n
be non-zero. Then
f
is not identically zero
on S = S
1
× ··· × S
n
.
Proof.
Suppose for contradiction that
f
is identically zero on
S
. Define
g
i
(
X
i
)
and h
i
as before such that
f =
X
h
i
g
i
.
Since the coefficient of
X
d
1
1
···X
d
n
n
is non-zero in
f
, it is non-zero in some
h
j
g
j
.
But that’s impossible, since
deg h
j
≤
n
X
i=1
d
i
!
− deg g
j
=
X
i6=j
d
i
− 1,
and so h
j
cannot contain a X
d
1
1
···
ˆ
X
j
d
j
···X
d
n
n
term.
Let’s look at some applications. Here
p
is a prime,
q
=
p
k
, and
F
q
is the
unique field of order q.
Theorem (Chevalley, 1935). Let f
1
, . . . , f
m
∈ F
q
[X
1
, . . . , X
n
] be such that
m
X
i=1
deg f
i
< n.
Then the f
i
cannot have exactly one common zero.
Proof.
Suppose not. We may assume that the common zero is 0 = (0
, . . . ,
0).
Define
f =
m
Y
i=1
(1 − f
i
(X)
q−1
) − γ
n
Y
i=1
Y
s∈F
×
q
(X
i
− s),
where γ is chosen so that F (0) = 0, namely the inverse of
Q
s∈F
×
q
(−s)
m
.
Now observe that for any non-zero
x
, the value of
f
i
(
x
)
q−1
= 1, so
f
(
x
) = 0.
Thus, we can set
S
i
=
F
q
, and they satisfy the hypothesis of the theorem. In
particular, the coefficient of
X
q −1
1
···X
q −1
n
is
γ 6
= 0. However,
f
vanishes on
F
n
q
.
This is a contradiction.
It is possible to prove similar results without using the combinatorial Null-
stellensatz. These results are often collectively refered to as Chevalley–Warning
theorems.
Theorem
(Warning)
.
Let
f
(
X
) =
f
(
X
1
, . . . , X
n
)
∈ F
q
[
X
] have degree
< n
.
Then N (f), the number of zeroes of f is a multiple of p.
One nice trick in doing these things is that finite fields naturally come with
an “indicator function”. Since the multiplicative group has order
q −
1, we know
that if x ∈ F
q
, then
x
q −1
=
(
1 x 6= 0
0 x = 0
.
Proof. We have
1 − f(x)
q −1
=
(
1 f(x) = 0
0 otherwise
.
Thus, we know
N(f ) =
X
x∈F
n
q
(1 − f(x)
q−1
) = −
X
x∈F
n
q
f(x)
q −1
∈ F
q
.
Further, we know that if k ≥ 0, then
X
x∈F
n
q
x
k
=
(
−1 k = q − 1
0 otherwise
.
So let’s write
f
(
x
)
q −1
as a linear combination of monomials. Each monomial
has degree
< n
(
q −
1). So there is at least one
k
such that the power of
X
k
in
that monomial is
< q −
1. Then the sum over
X
k
vanishes for this monomial.
So each monomial contributes 0 to the sum.
We can use Alon’s combinatorial Nullstellensatz to effortlessly prove some of
our previous theorems.
Theorem
(Cauchy–Davenport theorem)
.
Let
p
be a prime and
A, B ⊆ Z
p
be
non-empty subsets with |A|+ |B| ≤ p + 1. Then |A + B| ≥ |A| + |B| − 1.
Proof.
Suppose for contradiction that
A
+
B ⊆ C ⊆ Z
p
, and
|C|
=
|A|
+
|B|−
2.
Let’s come up with a polynomial that encodes the fact that
C
contains the sum
A + B. We let
f(X, Y ) =
Y
c∈C
(X + Y − c).
Then f vanishes on A × B, and deg f = |C|.
To apply the theorem, we check that the coefficient of
X
|A|−1
Y
|B|−1
is
|C|
|A|−1
,
which is non-zero in
Z
p
, since
C < p
. This contradicts Alon’s combinatorial
Nullstellensatz.
We can also use this to prove Erd¨os–Ginzburg–Ziv again.
Theorem
(Erd¨os–Ginzburg–Ziv)
.
Let
p
be a prime and
a
1
, . . . , a
2p+1
∈ Z
p
.
Then there exists I ∈ [2p − 1]
(p)
such that
X
i∈I
a
i
= 0 ∈ Z
p
.
Proof. Define
f
1
(X
1
, . . . , X
2p−1
) =
2p−1
X
i=1
X
p−1
i
.
f
2
(X
1
, . . . , X
2p−1
) =
2p−1
X
i=1
a
i
X
p−1
i
.
Then by Chevalley’s theorem, we know there cannot be exactly one common
zero. But 0 is one common zero. So there must be another. Take this solution,
and let
I
=
{i
:
x
i
6
= 0
}
. Then
f
1
(
X
) = 0 is the same as saying
|I|
=
p
, and
f
2
(X) = 0 is the same as saying
P
i∈I
a
i
= 0.
We can also consider restricted sums. We set
A
·
+ B = {a + b : a ∈ A, b ∈ B, a 6= b}.
Example. If n 6= m, then
[n]
·
+ [m] = {3, 4, . . . , m + n}
[n]
·
+ [n] = {3, 4, . . . , 2n − 1}
From this example, we show that if
|A| ≥
2, then
|A
·
+ A|
can be as small as
2|A| − 3. In 1964, Erd¨os and Heilbronn
Conjecture
(Erd¨os–Heilbronn, 1964)
.
If 2
|A| ≤ p
+ 3, then
|A
·
+ A| ≥
2
|A|−
3.
This remained open for 30 years, and was proved by Dias da Silva and
Hamidoune. A much much simpler proof was given by Alon, Nathanson and
Ruzsa in 1996.
Theorem.
Let
A, B ⊆ Z
p
be such that 2
≤ |A| < |B|
and
|A|
+
|B| ≤ p
+ 2.
Then A
·
+ B ≥ |A| + |B| − 2.
The above example shows we cannot do better.
Proof. Suppose not. Define
f(X, Y ) = (X − Y )
Y
c∈C
(X + Y − c),
where A
·
+ B ⊆ C ⊆ Z
p
and |C| = |A| + |B| − 3.
Then deg g = |A| + |B| − 2, and the coefficient of X
|A|−1
Y
|B|−1
is
|A| + |B| − 3
|A| − 2
−
|A| + |B| − 3
|A| − 1
6= 0.
Hence by Alon’s combinatorial Nullstellensatz,
f
(
x, y
) is not identically zero on
A × B. A contradiction.
Corollary
(Erd¨os–Heilbronn conjecture)
.
If
A, B ⊆ Z
p
, non-empty and
|A|
+
|B| ≤ p + 3, and p is a prime, then |A
·
+ B| ≥ |A| + |B| − 3.
Proof. We may assume 2 ≤ |A| ≤ |B|. Pick a ∈ A, and set A
0
= A \ {a}. Then
|A
·
+ B| ≥ |A
0
·
+ B| ≥ |A
0
| + |B| − 2 = |A| + |B| − 3.
Now consider the following problem: suppose we have a circular table
Z
2n+1
.
Suppose the host invites
n
couples, and the host, being a terrible person, wants
the
i
th couple to be a disatnce
d
i
apart for some 1
≤ d
i
≤ n
. Can this be done?
Theorem. If 2n + 1 is a prime, then this can be done.
Proof.
We may wlog assume the host is at 0. We want to partition
Z
p
\{
0
}
=
Z
×
p
into
n
pairs
{x
i
, x
i
+
d
i
}
. Consider the polynomial ring
Z
p
[
X
1
, . . . , X
n
] =
Z
p
[
X
].
We define
f(x) =
Y
i
X
i
(X
i
+d
i
)
Y
i<j
(X
i
−X
j
)(X
i
+d
i
−X
j
)(X
i
−X
j
−d
j
)(X
i
+d
i
−X
j
−d
j
).
We want to show this is not identically zero on Z
n
p
First of all, we have
deg f = 4
n
2
+ 2n = 2n
2
.
So we are good. The coefficient of X
2n
1
···X
2n
n
is the same as that in
Y
X
2
i
Y
i<j
(X
i
− X
j
)
4
=
Y
X
2
i
Y
i6=j
(X
i
− X
j
)
2
=
Y
X
2n
i
Y
i6=j
1 −
X
i
X
j
2
.
This, we are looking for the constant term in
Y
i6=j
1 −
X
i
X
j
2
.
By a question on the example sheet, this is
2n
2, 2, . . . , 2
6= 0 in Z
p
.
Our final example is as follows: suppose we are in
Z
p
, and
a
1
, . . . , a
p
and
c
1
, . . . , c
p
are enumerations of the elements, and
b
i
=
c
i
− a
i
. Then clearly we
have
P
b
i
= 0. Is the converse true? The answer is yes!
Theorem.
If
b
1
, . . . , b
p
∈ Z
p
are such that
P
b
i
= 0, then there exists numer-
ations
a
1
, . . . , a
p
and
b
1
, . . . , b
p
of the elements of
Z
p
such that for each
i
, we
have
a
i
+ b
i
= c
i
.
Proof.
It suffices to show that for all (
b
i
), there are distinct
a
1
, ··· , a
p−1
such
that a
i
+ b
i
6= a
j
+ b
j
for all i 6= j. Consider the polynomial
Y
i<j
(X
i
− X
j
)(X
i
+ b
i
− X
j
− b
j
).
The degree is
2
p − 1
2
= (p − 1)(p − 2).
We then inspect the coefficient of
X
p−2
1
···X
p−2
p−1
, and checking that this is
non-zero is the same as above.