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
n1
] in
X
n
. Then we can
write
h =
d
n
X
i=0
g
i
(X
1
, . . . , X
n1
)X
i
m
.
Fix (
x
1
, . . . , x
n1
)
S
1
× ···S
n1
, and set
c
i
=
g
i
(
x
1
, . . . , x
n1
)
F
. Then
P
d
n
i=0
c
i
X
i
n
vanishes on
S
n
. So
c
i
=
g
i
(
x
1
, . . . , x
n1
) = 0 for all (
x
1
, . . . , x
n1
)
S
1
× ··· × S
n1
. 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
sS
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)
q1
) γ
n
Y
i=1
Y
sF
×
q
(X
i
s),
where γ is chosen so that F (0) = 0, namely the inverse of
Q
sF
×
q
(s)
m
.
Now observe that for any non-zero
x
, the value of
f
i
(
x
)
q1
= 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
xF
n
q
(1 f(x)
q1
) =
X
xF
n
q
f(x)
q 1
F
q
.
Further, we know that if k 0, then
X
xF
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
cC
(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
iI
a
i
= 0 Z
p
.
Proof. Define
f
1
(X
1
, . . . , X
2p1
) =
2p1
X
i=1
X
p1
i
.
f
2
(X
1
, . . . , X
2p1
) =
2p1
X
i=1
a
i
X
p1
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
iI
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
cC
(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
p1
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
p2
1
···X
p2
p1
, and checking that this is
non-zero is the same as above.