GAZETA MATEMATICA

SERIA B
PENTRU TINERET
PUBLICAT
IE LUNARA
Fondat
a n anul 1895
ANUL CXVI nr. 11

noiembrie 2011

ARTICOLE S
I NOTE MATEMATICE
APPLICATIONS OF COMBINATORIAL
NULLSTELLENSATZ1)
3)
Andrei Frimu2) and Marcel Teleuca
Abstract. The Combinatorial Nullstellensatz is a powerful algebraic
method with numerous applications to combinatorial number theory, additive combinatorics, and graph theory. Noga Alon was among the first
who acknowledged the power of the Nullstellensatz, as for example, it can
be used to give a simple and ellegant proof of the Cauchy-Davenport theorem. To further illustrate the power of the Combinatorial Nullstellensatz,
we present a simple proof of the Erd
os-Heilbronn conjecture, which was
an open problem for three decades. We shall also illustrate some other
applications, such as the beautiful IMO 2007 Problem 6.
Keywords: root of a polynomial, Cauchy-Davenport, Erd
os-Heilbronn,
Chevalley, Permanent, Erd
os-Ginsburg-Ziv.
MSC : 05E99, 05A99.

1. Introduction
In 2007, at the International Mathematical Olympiad, held in Vietnam,
problem 6 was a difficult, nevertheless extremely beautiful combinatorics
problem, being solved by only five contestants. We present first a powerful
method with applications to many combinatorics problems and then solve
the above mentioned problem.
2. The main tools
We first introduce a simple generalization of a well known theorem
stating that all single variable polynomials of degree k cannot have more
than k distinct zeros.
1)

Nullstellensatz = teorema zerourilor (denumire n german

a, dat
a de Hilbert).

2) Student, Massachusetts Institute of Technology

3) Lyceum ,,Orizont, Chisin
au, Republic of Moldova

490

Articole si Note Matematice

Lemma 1. Let f = f (x1 , . . . , xn ) be a polynomial with coefficients in

an arbitrary field F , so that the degree of f in xi is at most ti , 1 i n.
Let S1 , . . . , Sn be subsets of F of size at least ti + 1. If f (s1 , . . . , sn ) = 0 for
all (s1 , . . . , sn ) S1 Sn , then f 0.
Proof. We use induction on n, the number of variables. For n = 1, the
lemma simply says that a polynomial of degree t in 1 variable vanishing at
t + 1 points is the zero polynomial. Assume now that the lemma is true for
n 1 variables, where n 2. Consider f as a polynomial in xn :
fn (xn ) = f (x1 , . . . , xn ) =

tn
X

gi (x1 , . . . , xn1 )xin .

i=0

The polynomial fn vanishes at the tn +1 points of Sn . Since deg fn = tn ,

we conclude fn 0, or gi (x1 , . . . , xn1 ) = 0, for every i. Since this holds
for all (n 1) -tuples (x1 , . . . , xn1 ) S1 Sn1 , by the induction
hypothesis, we have that gi 0, for every i = 0, tn . This implies f 0. 
We introduce the two main results used in the paper, which have been
presented first in [1]:
Theorem 1. Let F be an arbitrary field and f = f (x1 , . . . , xn ) be a
polynomial in F (x1 , . . . , xn ). Let S1 , . . .Y
, Sn be nonempty subsets of F .
Define the polynomials gi (xi ) =
(xi s). If f (s1 , . . . , sn ) = 0 for
sSi

all (s1 , . . . , sn ) S1 . . . Sn , then there exist polynomials h1 , . . . , hn

F (x1 , . . . , xn ) with deg hi deg f deg gi so that:
f = h1 g1 + . . . + hn gn .

Proof. Define ti = |Si | 1. Consider the following algorithm:

mn
1
If there is a monomial cxm
1 xn in f so that mi > ti for some i, then
mi (ti +1)
i
i
replace the factor xm
of the monomial by xm
gi (xi ). Since
i
i xi
m1
n is replaced by
deg gi = ti + 1 and gi is monic, the monomial x1 xm
n
several monomials of total degree less than m1 + . . . + mn . Thus, at each
step, the sum of the degrees of all monomials in f strictly decreases. Since
this sum is finite, the algorithm ends in a finite number of steps.
Let f be the polynomial obtained in the end. The transformation


mi (ti +1)
mi
m1
m1
n
n
gi (xi ) xm
cx1 xm
n corresponds to subn 7 cx1 xi xi
m (t +1)

i
i
1
stracting a term of the form hi gi from f , where hi = cxm
1 xi

satisfies deg hi = m1 + . . . + mn (ti + 1) deg f deg gi . Hence

n
xm
n

f = f h1 g1 . . . hn gn ,
for some polynomials h1 , . . . , hn F [x1 , . . . , xn ] satisfying deg hi deg f
deg gi . Since f was obtained at the end of the algorithm, every xi appears
in f with exponent at most ti . Since gi (xi ) = 0 if xi Si , it follows that

 , Combinatorial Nullstellensatz
Andrei Frimu and M. Teleuca

491

f(s1 , . . . , sn ) = f (s1 , . . . , sn ) = 0 whenever (s1 , . . . , sn ) S1 Sn .

Lemma 1 implies f 0, or f = h1 g1 + . . . + gn hn , as desired.
Theorem 2 (Combinatorial Nullstellensatz). Let F be an arbitrary field and f = f (x1 , . . . , xn ) be a polynomial in F (x1 , . . . , xn ). Assume
that f has degree t1 + . . . + tn , where ti are nonnegative integers, and that
the coefficient of xt11 xtnn is nonzero. If S1 , . . . , Sn are subsets of F so that
|Si | > ti , then there is a n-tuple (s1 , . . . , sn ) S1 Sn so that:
f (s1 , . . . , sn ) 6= 0.
Proof. We may assume |Si | = ti +1. Assume that there is no (s1 , . . . , sn )
S1 Sn so that f (s1 , . . . , sn ) 6= 0. Theorem 1 implies (under the same
notations) that
n
X
hi gi ,
f=
i=1

where deg hi deg f deg gi .

By assumption, it follows that the coefficient of xt11 xtnn in the righthand side is non-zero. However, deg hi gi deg f and a monomial in hi gi
has full degree t1 + . . . + tn only when we select xiti +1 in the expansion
Q
(xi s) = xtii +1 + (lower order terms). Thus, every monomial
gi (xi ) =
sSi

in h1 g1 + . . . + hn gn of degree t1 + . . . + tn is divisible by xtii +1 for some i.

Therefore, the coefficient of xt11 xtnn in the right-hand side is zero, which
gives a contradiction.
An alternative proof for the Combinatorial Nullstellensatz can be found
in [6].
3. Problem 6 of I.M.O. 2007
We now have all the tools necessary to present the solution of the elegant
problem of I.M.O. 2007, mentioned in the Introduction.
I.M.O. 2007. Problem 6. Let n be a positive integer. Consider
S = {(x, y, z)| x, y, z {0, 1, . . . , n}, x + y + z > 0}

as a set of (n + 1)3 1 points in three-dimensional space. Determine the

smallest number of planes, the union of which contains S but does not include
(0, 0, 0).
Proof. It is easy to see that 3n planes given by the equations x+y+z = i,
i = 1, 3n are sufficient. We shall prove that 3n is the minimum number of
required planes.
Assume by contradiction that there exist planes P1 , . . . , Pk , k 3n 1,
covering S but not passing through (0, 0, 0). Each plane Pi is defined by an
equation ai x + bi y + ci z + di = 0, where di 6= 0, since 0 = (0, 0, 0)
/ Pi .

492
Then

Articole si Note Matematice

Pi covers S if and only if g(x, y, z) =

k
Y

(ai x + bi y + ci z + di )

i=1

vanishes at every point of S. Since the union of the planes does not contain
0, g(0, 0, 0) 6= 0.
To apply the Combinatorial Nullstellensatz, we use the field F = R.
Nonetheless, our domain of interest S is not in the form S1 S2 S3 for
some S1 , S2 , S3 R.
n
Y
Consider the polynomial f (x, y, z) = g(z, y, z) c (x i)(y i)(z i),
i=1

g(0, 0, 0)
. It is clear that f vanishes at all
where the constant c equals
(1)3n (n!)3
points of S {0} = S1 S2 S3 , where S1 = S2 = S3 = {0, 1, . . . , n}.
Since k < 3n, we have deg f = 3n. The coefficient of xn y n z n in f equals
c 6= 0. By the Combinatorial Nullstellensatz, there exists a point (x0 , y0 , z0 )
S1 S2 S3 , so that f (x0 , y0 , z0 ) 6= 0, an obvious contradictoin.
4. Cauchy-Davenport Theorem
The Cauchy-Davenport Theorem is a well known theorem in additive
combinatorics and combinatorial number theory, being one of the first nontrivial results concerning bounds for cardinalities of sum sets.

Definition. If G is an abelian group and A, B G are finite, then

A + B := {a + b | a A, b B}.
Theorem (Cauchy-Davenport). Let A, B be subsets of Zp . Then
|A + B| min{p, |A| + |B| 1}.

Proof. Assume first |A| + |B| 1 p. We must show A + B = Zp . To

see this, note that |A| + |B| > p implies that, for every x Zp , the sets A
and {x} B intersect. Consequently, every x can be written as x = a + b for
some a A, b B.
Assume now that |A| + |B| < p and that |A + B| |A| + |B| 2. Let
C be a set with |A| +Y
|B| 2 elements, so that A + B C. Consider the
polynomial f (x, y) =
(x + y c) of degree |A| + |B| 2. Since A + B C,
cC

f (a, b) 
= 0 whenever 
a A and b B. The coefficient of x|A|1 y |B|1 in f
|A| + |B| 2
equals
. Since |A| + |B| 2 < p, this coefficient is nonzero in
|A| 1
Zp . By the Combinatorial Nullstellensatz, there is an a A and b B with
f (a, b) 6= 0, which is a contradiction.
s-Heilbronn conjecture
5. Further into the Erdo

The Erd
os-Heilbronn conjecture, stated below, though very simplelooking and similar to the Cauchy-Davenport theorem, had been an open

 , Combinatorial Nullstellensatz
Andrei Frimu and M. Teleuca

493

problem from its enunciation in 1964 for 30 years. Finally in 1994, the conjecture was successfully proven by J.A. Dias da Silva and Y. O. Hamidoune
(see [3]).
Definition. If G is an abelian group and A, B G are finite, then
b := {a + b|a A, b B, a 6= b}.
A+B
Theorem (Erd
os-Heilbronn conjecture). Let A be a nonempty
subset of Zp . Then
b min{p, 2|A| 3}.
|A+A|
Surprisingly, a solution for a problem that has stood open for three
decades, requires only half a page. This illustrates the power of the Combinatorial Nullstellensatz. We shall provide a more generalized statement
b min(p, |A| + |B| 3). The Erd
from [6] that |A+B|
os-Heilbronn conjecture
follows immediately.
Theorem. Let p be a prime and F = Fp be a prime field. Let A, B be
two nonempty subsets of F . Then
b min(p, |A| + |B| 3).
|A+B|

If |A| =
6 |B|, then the stronger conclusion

b min(p, |A| + |B| 2)

|A+B|

holds.
Proof. If |A| = 1 or |B| = 1 then the second inequality clearly holds.
Assume that |A|, |B| 2 and note that if |A| = |B|, then by taking B to
B = B \ {b}, where b is any element of B, the second inequality applied for
A and B trivializes the first inequality.
That is, we may assume |A| 6= |B|. The case when |A| + |B| 2 p
and p is an odd prime is handled by the following lemma. The case p = 2 is
obvious as we assumed |A|, |B| 2.
Lemma. Let G be a finite additive group of odd order and A, B be
b = G.
nonempty subsets of G. If |A| + |B| 2 |G|, then A+B
Proof. Let g be any element of G and define C = {g} B. Note that
|B| = |C|. Then |A| + |C| = |A| + |B| p + 2. Using the well-known formula
|X Y | + |X Y | = |X| + |Y |, we conclude
|G| + |A C| |A C| + |A C| = |A| + |C| p + 2,

implying |A C| 2.
Let x, y be distinct elements of A C. Since C = {g} B, there are
distinct elements bx , by B so that x + bx = y + by = g. We claim that
either x 6= bx or y 6= by . Assume that this is false. Then x + x = y + y = g.
This implies 2(x y) = 0. Since x 6= y, x y is nonzero of order 2. This is
impossible because G has odd order.

We return to the proof of the Erd
os-Heilbronn conjecture. Suppose
b < |A| + |B| 2.
now that |A| + |B| 2 < p and assume contrary that |A+B|

494

Articole si Note Matematice

b
Let C be a set with |A| + |B| 3 elements containing A+B.
Consider the
polynomial
Y
f (x, y) = (x y)
(x + y c).
cC

It is easy to see that whenever a A and b B, f (a, b) = 0. We have

deg f = |C| + 1 = |A| + |B| 2. Define m = |A| and n = |B|. By our
assumption, m 6= n. The coefficient of xm1 y n1 in f equals

 

m+n3
(m + n 3)!
m+n3
(m + n 3)!

=
=
m2
(m 2)!(n 1)! (m 1)!(n 2)!
m1
(m + n 3)!
(m n),
=
(m 1)!(n 1)!

which is nonzero modulo p because m + n 2 < p and m 6= n. The Combinatorial Nullstellensatz implies the existence of (a, b) A B such that
f (a, b) 6= 0, which is again a contradiction.
6. The Chevalley Theorem
The Chevalley-Warning theorem is a useful tool describing the number
of common zeroes of a collection of polynomials over a finite field F under
certain conditions. We state the theorem here without a proof.
Theorem (The Chevalley-Warning Theorem). Let F be a finite
field with q = pr elements and P1 , . . . , Pm polynomials in F[x1 , . . . , xn ], so
m
X
deg Pi . Then the number of common solutions (a1 , . . . , an ) Fn
that n >
i=1

to the system of equations

P1 (x1 , . . . , xn ) = 0, P2 (x1 , . . . , xn ) = 0, . . . , Pm (x1 , . . . , xm ) = 0

is divisible by the characteristic p of the field.
The Chevalley Theorem is an easy consequence of the Chevalley-Warning Theorem, and hence, also known as the Weak Chevalley-Warning Theorem. However, the Chevalley Theorem can be verified independently with
the CN as a tool.
Theorem (The Chevalley Theorem). Let F be an arbitrary finiet
m
X
field and P1 , . . . , Pm be polynomials in F[x1 , . . . , xn ] so that n >
deg Pi . If
i=1

the polynomials P1 , . . . , Pm have a common zero (a1 , . . . , an ), then they have

another one.
Proof. Recall the fact that if F is a finite field, then it has q = pr
elements, where p is a prime number and r is a positive integer. We shall
use the fact that the nonzero elements of F form a multiplicative group F
of order q 1, hence xq1 = 1, for every x F .

 , Combinatorial Nullstellensatz
Andrei Frimu and M. Teleuca

495

Assume now that the polynomials P1 , . . . , Pm have no other common

zero. Consider the polynomial
n
m
Y
Y
Y


(xj a),
1 Pi (x1 , . . . , xn )q1 c
f (x1 , . . . , xn ) =
j=1 aF\{aj }

i=1

where c is chosen so that f (a1 , . . . , an ) = 0. Clearly c is well defined and

nonzero. We claim that f (s1 , . . . , sn ) = 0 for every (s1 , . . . , sn ) Fn . Indeed,
if (s1 , . . . , sn ) = (c1 , . . . , cn ) this is true by the choice of c; otherwise, there
is a polynomial Pi so that Pi (s1 , . . . , sn ) 6= 0 (if not, (s1 , . . . , sn ) is another

q1
common root). Then 1 Pi (s1 , . . . , sn )
= 0, leading to f (s1 , . . . , sn ) = 0.
m
Y


1Pi (x1 , . . . , xn )q1 has degree (q 1)
Notice that the polynomial
i=1

(deg P1 + . . . + deg Pm ) < n(q 1), the polynomial c

n
Y

(xj a) has

j=1 aF\{aj }

degree n(q 1) and the monomial x1q1 xnq1 has nonzero coefficient c.
Hence we have met the requirements of the Combinatorial Nullstellensatz, when applied for S1 = . . . = Sn = F. This proves the existence of
(s1 , . . . , sn ) Fn so that f (s1 , . . . , sn ) 6= 0, a contradiction.
7. The Permanent Lemma
We present a nice application of the Combinatorial Nullstellensatz, the
Permanent Lemma, as described in [1]. The theorem will be implemented as
a tool in another proof of the Erd
os-Ginzburg-Ziv Theorem.
Definition. The permanent
Per(A) of an n n matrix A = (aij )
X
is defined to be Per(A) =
a1(1) a2(2) an(n) , where Sn denotes the
Sn

symmetric group.
Lemma (The Permanent Lemma). Let F be a field and A = (aij )
be an n n matrix with entries in F so that Per(A) 6= 0F . For any vector
b = (b1 , . . . , bn ) Fn and any sets S1 , . . . , Sn , each containing 2 elements,
there is a vector x = (x1 , . . . , xn ) S1 Sn so that (Ax)i 6= bi .
Proof. Consider the polynomial

n
n
Y
X
bi +
f (x1 , . . . , xn ) =
aij xj .
i=1

j=1

We have deg f = n. Setting t1 = . . . = tn = 1 we have that the coefficient

of xt11 xtnn is Per(A) 6= 0 and |Si | = 2 > ti = 1. The Combinatorial
Nullstellensatz implies the existence of (x1 , . . . , xn ) S1 Sn so that
n
X
aij xj 6= bi , as
f (x1 , . . . , xn ) 6= 0. This means that for every i, (Ax)i =
j=1

desired.

496

Articole si Note Matematice

s-Ginzburg-Ziv Constant and the EGZ Theorem

8. The Erdo
One may be familiar with combinatorial number theory problems such
as: given n integers, show that some of these have a sum divisible by n.
The Erd
os-Ginzburg-Ziv Theorem is such a problem, with a more restricted
condition: given N integers, what is the minimum possible value of N such
that there exists some n of these integers whose sum is divisible by n. This
beautiful problem has been discussed for the first time in 1961 (see [5]).
Notice that N > 2n 2 because among 2n 2 integers, n 1 of which are
divisible by n and n 1 of which are congruent to 1 modulo n, no n elements
have sum divisible by n.
Definition. Let G be a finite additive abelian group G. The Erd
osGinzburg-Ziv constant of G, denoted by EGZ(G) is the smallest integer t so
that among any t elements of G, there are |G| elements that add up to 0.
We will investigate the EGZ constant for cyclic groups Zm and prove
that EGZ(Zm ) = 2m 1. It has been proven that EGZ(G) 2|G| 1
with equality if and only if G = Zm (see [2]). J.E. Olson has extended
the definition of EGZ constant to non-abelian groups and has proved that
EGZ(G) 2|G| 1 still holds (see [5]).
Theorem (The EGZ Theorem). Let m be a positive integers. Among
any 2m 1 integers there are m whose sum is divisible by m. In terms of
the EGZ constant, the theorem asserts that EGZ(Zm ) = 2m 1.
We provide three proofs of this classical result in this section. One of
them is based on the Chevalley-Warning theorem, and another is based on
the Permanent Lemma. All proofs start by showing that the result follows
by induction on the number of prime factors (with multiplicity) in the prime
decomposition of m. Hence, after the induction step has been shown, we are
left with proving the EGZ theorem in the case m is a prime number.
Lemma. If the EGZ Theorem holds for all prime numbers m, then it
is true for every positive integer m.
Proof (induction step). It suffices to show that the theorem has a
multiplicative property; that is, if the EGZ Theorem holds for m = a and
m = b (a, b N), then the theorem is also true when m = ab.
Let X = (x1 , . . . , x2ab1 ) be a collection of 2ab1 integers. By the EGZ
theorem for m = a, we conclude that there are a of them, say xa(2b1)+1 , . . . ,
x2ab1 with sum divisible by a. Denote this sum by z1 and the collection of
these a numbers by Y1 .
Proceed similarly with the a(2b 1) 1 numbers x1 , . . . , xa(2b1)1 . Let
Y2 be the collection of the selected a numbers with sum z2 divisible by a.
Clearly Y1 and Y2 are disjoint as subcollections of X. In the end, we obtain
2b 1 disjoint collections Y1 , . . . , Y2b1 each consisting of a numbers adding
up z1 , . . . , z2b1 , all multiples of a. Let zi = yi a. Applying the EGZ for b
and the numbers y1 , . . . , y2b1 , we find b of them, say y1 , . . . , yb , with sum

 , Combinatorial Nullstellensatz
Andrei Frimu and M. Teleuca

divisible by b. Then,

b
[

497

Yi is a subcollection of X with ab elements adding

i=1

up to z1 + . . . + zb = a(y1 + . . . + yb ), divisible by ab.


We now continue in three different ways. Two of them use the tools
developed above. Assume m = p is a prime number.
Proof using the Chevalley-Warning theorem. We follow the proof given
in [7].
Let a1 , . . . , a2p1 be integers and consider them as elements of Fp . De+ . . . + xp1
fine the polynomials f (x1 , . . . , x2p1 ) = xp1
2p1 and
1
+ . . . + a2p1 xp1
g(x1 , . . . , x2p1 ) = a1 xp1
2p1 .
1
We have deg f + deg g = 2p 2 < 2p 1, and (0, 0, . . . , 0) is a common zero
of f and g. By the Chevalley theorem, f and g have another common zero
(s1 , . . . , s2p1 ).
Let M be the (multi)set of nonzero elements among s1 , . . . , s2p1 . We
evaluate f and g at (s1 , . . . , s2p1 ). Using Fermats Little Theorem (or the
fact that p 1 is the order of the multiplicative group of Fp ), we have
2p1
P p1
P
ai .
f (s1 , . . . , s2p1 ) =
si = |M | and g(s1 , . . . , sn ) =
1i2p1 & si M

i=1

Since f (s1 , . . . , s2p1 ) X

= 0, it follows that |M | = 0 in Fp , or |M | = p.
Then g(s1 , . . . , sn ) = 0 =
s implies that the elements of M are the p
sM

numbers we are looking for.

Proof using the Permanent Lemma. Let a1 a2 . . . a2p1 be
2p 1 integers modulo p. If there is an index i so that ai+1 = ap+i , then
ai+1 = . . . = ap+i and these are the p numbers we are looking for. Otherwise,
let A = (aij ) be a (p 1) (p 1) matrix with aij = 1 for all i, j = 1, p 1.
Define Si = {ai+1 , ap+i , for 1 i p 1. Let b = (b1 , . . . , bp1 ), where
{b1 , . . . , bp1 } = Zp \ {a1 }. Using the Permanent Lemma, there are is a
vector x = (x1 , . . . , xp1 ) S1 Sp1 so that (Ax)i = x1 +. . .+xp1 6= bi
for every i = 1, p 1. Then we must have x1 + . . . + xp1 = a1 , implying
x1 + . . . + xp1 + a1 = 0.

A beautiful elementary combinatorial solution of the EGZ theorem in

the case m = prime has appeared in the russian journal Kvant, in the issues
7 and 8 of 1971, as part of the solution for problem M 45. The core of the
solution is an elementary proof of the existence of the vector (x1 , . . . , xp1 )
constructed in the proof of EGZ theorem using the Permanent Lemma. We
reproduce here a sketch of the solution:
Let p be a prime number and r an integer
Xso that 0 < r < p. Consider
r integers b1 , . . . , br ; 0 < bi < p and all sums
bi , where I ranges over the
iI

498

Articole si Note Matematice

subsets of {1, 2, . . . , r}. Define this sum to be 0 for I = . It can be proved

by induction that there exist at least r + 1 distinct numbers among these
sums. As in the proof using the permanent lemma, consider 2p 1 integers
modulo p : a1 a2 . . . a2p1 . Consider the numbers b1 = ap+1 a2 ,
b2 = ap+2 a3 , . . . , bp1 = a2p1 ap . If one of these numbers is zero, say
bi = 0, then we have that ai+1 = . . . = ap+i and {ai+1 , . . . , ap+i } add up
to 0.
Assume now bi > 0 for every 1 i p 1. Consider the number
a1 + . . . + ap x (mod p). If x = 0, we areXdone. Otherwise, by the
lemma, there exists I {1, . . . , p 1} so that
bi x (mod p). Then
E = a1 + . . . + ap +

X
iI

iI

bi 0 (mod p). Since bi = ap+i ai+1 , we conclude

that E includes a1 and exactly one number from each pair {ap+i , ai+1 } for
1 i p 1, finishing the proof.
9. Proposed problems
Problem 1. Let p be a prime number and G a graph with at least
2p 1 vertices. Prove that there is a subset U of vertices of G, so that the
number of edges having at least one endpoint in U , is divisible by p.
Problem 2. [Troi-Zannier]. Let k be a positive integer and p be a
prime number. S1 , . . . , Sn are subsets of {0, 1, . . . , p 1} containing 0, so
n
X
that
(|Sj | 1) 1 + k(p 1). Then for any integers aij , 1 i n,
j=1

1 j k there are xi Si , not all zero so that aj1 x1 + . . . + ajn xn 0

(mod p) for every 1 j k.
References

[1] N. Alon. Combinatorial Nullstellensatz. Combinatorics, Probability and Computing,

(8): 729, 1999.
[2] A. Bialostocki. Erd
os-Ginzburg-Ziv theorem. SpringerLink, Encyclopedia of Mathematics. http://eom.springer.de/e/e110100.htm.
[3] J.A. Dias da Silva and Y.O. Hamidoune, Cyclic spaces for Grassman derivatives and
additive theory, Bulletin of London Mathematical Society, 26: 140146, 1994.
[4] Vesselin Dimitrov, Combinatorial Nullstellensatz, St. Petersburg Olympiad 2005.
[5] Ginzburg A. Erd
os, P. and A. Ziv, Theorem in the additive number theory, Bull.
Research Council Israel, 10F: 4143, 1961.
[6] T. Tao and V. Vu. Additive Combinatorics. Cambridge University Press, 2006.
[7] Zhi-Wei Sun, On Zero-Sum Problems,
http://math.nju.edu.cn/ zwsun/zerosum.pdf.