Alon’s Combinatorial Nullstellensatz

Rohan Goyal
May 2020

Thanks to Shourya Pandey for his help in the making of this handout and letting me
blatantly copy and paste some of his notes here.

Definition (Field). A field F is any structure in which you can add, subtract, multiply
divide(except by 0) and operations are commutative, associative and multiplication,
addition are distributive 1 . Some common useful examples here are Common helpful
examples are R, Q, Z/pZ.

Definition. F[x1 , x2 , · · · xn ] is the set of all polynomials with variables x1 , x2 , · · · xn and

coefficients in F.

§1 The Theorem

Theorem 1.1 (Combinatorial Nullstellensatz)

Let F be a field, and let f ∈ F[x1 , x2 , · · · , xn ] be a polynomial on n variables
x1 , x2 , · · · , xn of degree t1 + t2 + · · · + tn , where each ti is a non-negative integer. If
S1 , S2 , · · · , Sn are non-empty subsets of F such that |Si | = ti + 1, then there exists
an (s1 , s2 , · · · , sn ) ∈ S1 × S2 × · · · × Sn such that

f (s1 , s2 , · · · , sn ) 6= 0

if the coefficient of x1 t1 x2 t2 · · · xn tn in f is non-zero.

I believe this is a very nice theorem that you should try to prove yourself. So, here I
am writing a small walkthrough of the proof which you can use. Else, feel free to skip to
Section 4 and read the proof directly in all it’s glory.

Walkthrough of the proof. Begin by considering the case n = 1 and what that represents.

i Resolve the n = 1 case.

ii Can induction finish if every term of f had maximum power of xi as si ? If yes, can
we reduce all f to such a case?

iii Observe that if you have a set X = {1, 2, 3} then you can replace f (x) = x3 with
f (x) = x3 − (x − 1)(x − 2)(x − 3) = 6x2 − 11x + 6 while preserving value of f in S.

1
This means that you can define operations +, · and have elements 0, 1 such that ∀ f, f1 , f2 ∈ F, f +0 = f ,
f · 1 = f, f1 · f2 is defined, f1 + f2 is defined. If there is an element f then there is also an element
−f such that f + (−f ) = 0, for every f except 0, there exists a unique f −1 such that f · f −1 = 1

1
Rohan Goyal (May 2020) Alon’s Combinatorial Nullstellensatz

iv For n > 1, try to do a similar replacement argument which does not change the
value of f in S1 × S2 × S3 × · × Sn but reduces the degree of any term which has
degree of xi > si .

v When you finish the replacement process, use induction.

Feel free to skip down to Section 4 if you weren’t able to show this.

2
Rohan Goyal (May 2020) Alon’s Combinatorial Nullstellensatz

§2 Example Problems
Let’s first try to show this nice result to build some intuition for the usage of Combinatorial
Nullstellensatz

Example 2.1 (Cauchy-Davenport)

Let p be an odd prime number. Consider non-empty subsets A, B of Zp . Prove that

|A + B| ≥ min(p, |A| + |B| − 1)

The case |A| + |B| − 1 > p does not require CN so we ignore that.

Key Idea. If a set C has upto |A| + |B| − 2 elements, then we can describe a polynomial
f (x, y) which does not evaluate to 0 for all values as x, y vary over A, B.

Proof. Observe that if we can show that A + B 6⊆ C for all sets C of size |A| + |B| − 1,
we will be done. Why?
Now, for any set C of size |A| + |B| − 2, consider the following polynomial,
Y
f (x, y) = (x + y − c)
c∈C

and the coefficient of the term x|A|−1 y |B|−1 . Clearly it is |A|+|B|−2

|A|−1
6≡ 0 (mod p) and
thus by Combinatorial Nullstellensatz, we must have that f does not evaluate to 0 for all
(x, y) with x ∈ A, y ∈ B so we are done!

Exercise 2.2. Find the equality case.

Now, how would an example section be complete without an IMO problem!?

Example 2.3 (IMO 2007/6)

Let n > 1 be an integer. In the space, consider the set

S = {(x, y, z) | x, y, z ∈ {0, 1, · · · , n}, x + y + z > 0}

Find the smallest number of planes that jointly contain all (n + 1)3 − 1 points of S,
but none of the planes contain the point (0, 0, 0).

Walkthrough. I will give a small walkthrough of this problem if you wish to attempt on
your own but are having some trouble. Else, feel free to jump to the solution.

i First, try to show the much easier upper bound and find a construction with 3n
planes.

ii Now, assume that we have k < 3n planes that just work, then consider the
polynomials-
k
Y
P (x) = (ai x + bi y + ci z + di )
i=1
3n
Y
Q(x) = (x + y + z − i)
i=1

3
Rohan Goyal (May 2020) Alon’s Combinatorial Nullstellensatz

iii Consider Q − cP where c is some constant and figure out what we need it to satisfy
to finish by CN.

iv Kill the problem by CN.

n
Q
You could also choose Q as (x − i)(y − i)(z − i) and do the same trick.
i=1

If you couldn’t finish, you can read this nicely written proof.

Proof. (writeup by Shourya Pandey)

Let us first try obvious upper bounds. The existence of 3n planes that satisfy the
conditions of the problem is easy to find; simply take the planes x = i, y = i, and z = i
for all 1 ≤ i ≤ n. See if you can find other constructions (I can think of one more
construction).
Let us now try proving that this is indeed the answer. We know that the equation of a
plane is of the form ax + by + cz + d = 0, for some a, b, c, d ∈ R, where not all of a, b, c
are 0. Somehow, the problem can be associated to CN, because we have n + 1 choices for
each of x, y, z, similar to what we had in the theorem statement. This would seem to
suggest that we should try to make some polynomial of degree n + n + n = 3n, such that
it has a non-zero xn y n z n term. The 3n bound we got before may not be a coincidence.
Of course, this all is just ”wishful thinking”.

Suppose the answer to the question was k < 3n. Now, we wish to apply CN and
get a contradiction. The obvious way of getting a contradiction (via CN) is to construct
a polynomial f as in the theorem statement, such that f (s1 , s2 , · · · , sn ) = 0 for all
s1 ∈ S1 , s2 ∈ S2 , · · · , sn ∈ Sn . So our aim is to find a polynomial f ∈ F(x, y, z) such that

• f has degree n + n + n = 3n.

• xn y n z n has a non-zero coefficient in f .

• f (a, b, c) = 0 for all a, b, c ∈ {0, 1, 2, · · · , n}

If we are able to do this, then we are done, as we have contradicted the statement of
CN.
Let us return to our assumption that k < 3n planes work. Suppose the k planes that
satisfy the conditions of the problem were ai x + bi y + ci z + di = 0, where 1 ≤ i ≤ k.
Consider the polynomial P ∈ R[x, y, z] defined as
k
Y
P (x, y, z) = (ai x + bi y + ci z + di )
i=1

This function satisfies P (a, b, c) for all (a, b, c) ∈ {0, 1, · · · , n}3 except at (0, 0, 0). Great.
Let us try to think of another obvious polynomial that is 0 for all (a, b, c) ∈ {0, 1, · · · , n}3
except at (0, 0, 0), and such that it has degree 3n and a non-zero coefficient of
xn y n z n . The reason for this will be clear in some time. There are several candidates
here. One of them, inspired by the observation that 1 ≤ x + y + z ≤ 3n for all points in
{0, 1, · · · , n}3 other than (0, 0, 0), is
3n
Y
Q(x, y, z) = (x + y + z − i)
i=1

4
Rohan Goyal (May 2020) Alon’s Combinatorial Nullstellensatz

Another possibility is to choose the polynomial

n
Y
R(x, y, z) = (x − i)(y − i)(z − i)
i=1

which comes from our construction before. Note that both of them satisfy what we
wanted (why?)

But what do we do with this? Consider the polynomial

f (x, y, z) = Q(x, y, z) + αP (x, y, z)

where α = − Q(0,0,0)
P (0,0,0) . We are done! This polynomial checks all items in the list we made
before.

5
Rohan Goyal (May 2020) Alon’s Combinatorial Nullstellensatz

§3 Exercises
Note. Try to develop an intuition for the approach used in Combinatorial Nullstellensatz.
We try to construct a polynomial P which satisfies some set of condition we set up which
are equivalent to the problem and we can set P so that it vanishes for the values we want
like in the IMO 2007/6 where set up P − cQ to vanish at (0, 0, 0) and manipulated it
into working for us. We often also need that the coefficients we want is non-zero and
may have to tinker with the coefficients a bit.

Note. The problems in this handout mostly lie on the tougher side and the later problems
may take substantial periods of time to solve so please don’t worry and just try to enjoy
this cute technique.

Problem 3.1 (Russia 2007/9.5). Two distinct real numbers are written at each vertex
of a 100-gon. Prove that one can select one number from each vertex so that no two
adjacent vertices have the same number

Problem 3.2 (Alon’s Hyperplane Problem). Let H1 , H2 , · · · Hm be a family of hyper-

planes in Rn that cover all the vertices of the unit cube except one. Prove that m ≥ n.

Problem 3.3 (Erdős-Heilbronn). Let p be an odd prime number. For any subset A of
Zp , prove that

|{{x + y | x ∈ A, y ∈ A, x 6= y}| ≥ min(p, 2|A| − 3)

Problem 3.4 (NIMO-Winter 2014/8). Define the function ξ : Z2 → Z by ξ(n, k) = 1

when n ≤ k and ξ(n, k) = −1 when n > k, and construct the polynomial
1000
Y 1000
!
X
P (x1 , . . . , x1000 ) = ξ(n, k)xk .
n=1 k=1

(a) Determine the coefficient of x1 x2 . . . x1000 in P .

(b) Show that if x1 , x2 , . . . , x1000 ∈ {−1, 1} then P (x1 , x2 , . . . , x1000 ) = 0.

Problem 3.5 (TSTST 2011/9). Let n be a positive integer. Suppose we are given
2n + 1 distinct sets, each containing finitely many objects. Place each set into one of
two categories, the red sets and the blue sets, so that there is at least one set in each
category. We define the symmetric difference of two sets as the set of objects belonging
to exactly one of the two sets. Prove that there are at least 2n different sets which can
be obtained as the symmetric difference of a red set and a blue set.

Problem 3.6. Let G be a simple undirected graph, such that the average degree of G
greater than 2p − 2 and maximum degree is at most 2p − 1. Prove that G has a p-regular
subgraph.

Problem 3.7 (Troi-Zannier). Let p be a prime and let S1 , S2 , · · · Sk ⊂ Fp , each containing

k
P
0. Suppose that (|Si | − 1) ≥ p. Then, for any elements a1 , a2 , · · · ak ∈ Fp , the equation
i=1
k
P
xi ai has a solution in (x1 , x2 , · · · xk ) ∈ S1 × S2 × · · · × Sk other than the trivial solution.
i=1

Problem 3.8 ((Erdős-Ginzburg-Ziv)). Prove that any multiset of 2n − 1 integers has a

subset of size n the sum of whose elements is a multiple of n. Prove that this is not true
if we take only 2n − 2 integers. Be careful, Zn is not a field for all n!

6
Rohan Goyal (May 2020) Alon’s Combinatorial Nullstellensatz

Problem 3.9 (Alon). Let p be a prime, and let G = (V, E) be a graph on a set of
|V | > d(p − 1) vertices. Then, there is a nonempty subset U of G such that the number
of cliques of d vertices of G that intersect U is 0 (mod p).

Problem 3.10 (Chevalley-Warning). Let p be an odd P prime number. Let f1 , f2 , · · · , fk

k
be polynomials in Zp [x1 , x2 , · · · , xn ] such that n > i=1 deg(fi ). Show that if the
polynomials f1 , f2 , · · · , fk have a common zero (c1 , c2 , · · · , cn ). then they have another
common zero.

Problem 3.11 (Shirazi-Verstraëte). Let G = (V, E) be a simple undirected P graph. For

each set v ∈ V , we have a bad set B(v) of positive integers. Prove that if v∈V |B(v)| <
|E|, then we can delete some, but not all, edges of G such that the resultant graph G
satisfies degv 6∈ B(v) for all v.

Problem 3.12. In the previous problem, suppose we allow 0 ∈ B(v) as well. Prove that
if |B(v)| ≤ degv
2 for all v, then we can still delete some (but this time, possibly all) edges
of G such that the resultant graph G satisfies degv 6∈ B(v) for all v.

Problem 3.13. Let p be a prime, and let A1 , A2 , · · · Ak be nonempty subsets of Zp . If

|Ai | =
6 |Aj | for all 1 ≤ i < j ≤ k then
 
X k+1
|{a1 + a2 + · · · ak |ai ∈ Ai , ai 6= aj }| ≥ min p, |Ai | − +1
2

Problem 3.14. Suppose p is an odd prime and d is a natural number. Prove that any
integer is the sum of d d-th powers modulo p.

Problem 3.15 (Alon). Let p be a prime and let h = h(x0 , x1 , · · · , xk ) be a polynomial

over Zp . Let A0 , A1 , · · · Ak be nonempty subsets of Zp , where |Ai | = ci + 1 and define
k k
xci i in
P Q
m= ci − deg h. If the coefficient of
i=0 i=0

(x0 + x1 + · · · xk )m · h(x1 , x2 , · · · xm )

is nonzero (in Zp ) then

|{a0 + a1 + · · · ak |ai ∈ Ai , h(a0 , a1 , · · · ak ) 6= 0}| ≥ m + 1

and hence m < p.

Problem 3.16 (Alon-Knuth). Let n ≥ 2 be an even integer, and let v1 , v2 , · · · , vk ∈

{1, −1}n be k vectors, each of length n, such that any v ∈ {1, −1}n is perpendicular to
at least one vi . Prove that k ≥ n and that this bound is sharp.

7
Rohan Goyal (May 2020) Alon’s Combinatorial Nullstellensatz

§4 Proof of Combinatorial Nullstellensatz

Proof. (Writeup by Shourya Pandey) Consider the case where the degree of each xi is at
most ti . Since the degree of f is t = t1 + t2 + · · · + tn , this means the only monomial
with degree t is xt11 xt22 · · · xtnn . Let us interpret the polynomial f has a polynomial only in
xn , with coefficients from x1 , x2 , x3 , · · · , xn−1 . Then, this polynomial has degree tn in xn .
Consider the coefficient of xtnn . This is a polynomial f 0 ∈ F[x1 , x2 , · · · , xn−1 ], with degree
t1 + t2 + · · · + tn−1 , and such that xi has degree at most ti in f 0 . By induction, there is a
setting of x1 , x2 , · · · , xn−1 from S1 , S2 , · · · , Sn−1 respectively, such that f 0 evaluates to
not zero. Take this substitution in f . This gives us a polynomial g ∈ F[xn ] of degree tn .
Since xn can take tn + 1 values, one of these values keeps g non-zero, and the proof is
finished.

Now, we want to get rid of the assumption that the degree of xi is not at most ti .
Note that we are only concerned with the value of xi in Si , for all i. Consider S1 for now.
Suppose S1 = {a1 , a2 , · · · , at1 +1 }. Then note that for any x1 ∈ S1 ,

(x1 − a1 )(x1 − a2 ) · · · (x1 − at1 +1 ) = 0

which means that we can do the following.

This means we can replace all occurrences of xd1 , for d ≥ t1 + 1, with a polynomial of
degree at most t1 (how?), while keeping the evaluation of the polynomial the same in S1 .
Also note that this substition will not alter the coefficient of xt11 xt22 · · · xtnn (why?) We do
this process of ”degree reduction” for all variables, and arrive at a polynomial p such
that f (s1 , s2 , · · · , sn ) = p(s1 , s2 , · · · , sn ), and such that p falls in the category of the first
paragraph. This finishes the proof.

8
Rohan Goyal (May 2020) Alon’s Combinatorial Nullstellensatz

§5 References
These recources were used in making of this handout. I also recommend reading them to
delve deeper into CN and gain a better understanding.

• http://www.tau.ac.il/~nogaa/PDFS/null2.pdf

• https://www.tau.ac.il/~nogaa/PDFS/annr3.pdf

• https://drive.google.com/file/d/1MXe7vCTWOZVmNg6SW3IYs24Fn6xiMLdw/view?
usp=sharing

• https://web.evanchen.cc/handouts/BMC_Combo_Null/BMC_Combo_Null.pdf

• https://web.evanchen.cc/handouts/SPARC_Combo_Null_Slides/SPARC_Combo_
Null_Slides.pdf

• https://en.wikipedia.org/wiki/Restricted_sumset

§5.1 Acknowledgements
Thanks to Shourya for letting me copy some of his notes blatantly and lending the LaTeX
to his notes on Combo Null.
Thanks to Pranjal for helping me understand Combinatorial Nullstellensatz better and
the motivation to use in solving problems.
Thanks to Evan for his handouts which have made a wide array of theory better accessible
and understandable for students.
And of course, thanks to Noga Alon for developing this cute technique, I highly suggest
reading his paper on combo null referenced above. It is very easily accesible and easy to
understand.
Thanks to Ritam for proofreading as well.
Thanks to Arindam for recommending additional resources that are quite helpful.