Some zero-sum problems and Ramsey-type results in

Some zero-sum problems and Ramsey-type
results in Additive Combinatorics
Sukumar Das Adhikari
July 12, 2013
Abstract
The early Ramsey-type results preceding the result of Ramsey
(these include results of Schur, van der Waerden and Hilbert) belong
to the area of combinatorial number theory. In the first two sections
of this article, we shall take up these results and some generalizations
of them. We shall try to have a glimpse of applications of elementary
algebraic and topological methods in dealing with these problems. In
the last two sections, we take up zero-sum problems in additive combinatorics. Here we shall see proofs of some early results, including
the EGZ theorem, by various methods; we shall also discuss some
generalizations.
Some notations and terminologies. Here the symbols Z+ , N, Z, Q and
R will denote respectively the set of positive integers, the set of non-negative
integers, the set of integers, the set of rationals and the set of real numbers.
For any prime power q, Fq will denote the finite field with q elements and
the symbol F∗q will denote the multiplicative group of non-zero elements of
Fq . In general, for any field K, K ∗ will denote the multiplicative group of
its non-zero elements. For a finite Set A, |A| will be the number of elements
of A. If r ∈ Z+ , then an r-colouring of a set S is a map χ : S → {1, · · · , r}.
Since S = χ−1 (1) ∪ χ−1 (2) ∪ · · · ∪ χ−1 (r), an r-colouring of a set S is nothing
but a partition of S into r parts. If s is an element of S, then χ(s) is called
the colour of s. A set T ⊂ S is called monochromatic with respect to a
colouring χ if χ is constant on T . For two non-zero integers a, b, we shall
consider gcd (a, b) to be positive.
1
1
Early Ramsey-type theorems and
some generalizations: Part I
In most of the early Ramsey-type results, one sees that if a large structure is
divided into finitely many parts, at least one of the parts will retain certain
regularity properties of the original structure. Sometimes, if the ‘size’ of a
substructure is big enough, certain regularities are unavoidable. “Complete
disorder is impossible”: the philosophy of Ramsey Theory is often described
by this statement of Motzkin. To become acquainted with many facets of
the theory, one may look into the Graham-Rothschild-Spencer monograph
[37] and the collection of articles [53] edited by Ne˘set˘ril and R¨odl. We also
refer to a recent article of Soifer [68] giving detailed history of the emergence
of the subject.
Theorem 1. (Generalized pigeonhole principle) Let A and B be finite
nonempty sets where B = {b1 , b2 , · · · , br }. Let f be a function from A to B.
Then, for non-negative integers a1 , a2 , · · · , ar , the equality
|A| = a1 + a2 + · · · + ar − r + 1
would imply that ∃ i ∈ {1, · · · , r} such that |f −1 (bi )| ≥ ai .
Proof: If there is no such i, then
|A| =
r
X
i=1
|f
−1
r
r
X
X
(bi )| ≤
(ai − 1) =
ai − r
i=1
i=1
– a contradiction to our assumption.
Remark 1. Clearly, it is interesting only when |A| > |B|; when |A| = |B|+1,
it follows that there is bi ∈ B with |f −1 (bi )| ≥ 2, which is the commonly
known version of the pigeonhole principle.
Exercise 1. Show that given any five integer lattice points on the plane the
midpoint of the line segment determined by some two distinct points among
them will also be an integer lattice point.
Exercise 2. (Mantel) Let n ≥ 2 be a positive integer. Show that if a simple
graph G of order 2n contains n2 + 1 edges, then G contains a triangle.
2
Exercise 3. (Erd˝os and Szekeres) Given a sequence of mn + 1 distinct real
numbers, show that if it does not contain a monotone increasing subsequence
of length m + 1, then it must contain a monotone decreasing subsequence of
length n + 1.
A well-known example. If you have a party of at least 6 people, you can
guarantee that there will be a group of 3 people who all know each other, or
a group of 3 people who all do not know each other.
Proof by graphs:
(joining by red line when two people know each other)
3
The following result [59] generalizes the above example.
Theorem 2. (Ramsey’s Theorem) Let k, r, l(≥ k) be positive integers.
Then there exists a positive integer n = n(k, r, l) such that for any r-colouring
of the k-subsets of the set [n] = {1, 2, · · · , n}, there is an l-subset of [n] all
of whose k- subsets are of the same colour.
We shall give a proof of the following general version.
Theorem 3. (Generalized Ramsey’s Theorem) Given positive integers
k, r, l1 , · · · , lr , there exists a positive integer n = n(k, r; l1, · · · , lr ) such that
for any r-colouring of the k-subsets of the set [n] with colours c1 , · · · , cr , for
some i ∈ {1, · · · , r}, there is an li -subset of [n] all of whose k- subsets are of
the colour ci .
Proof: Once a positive integer n = n(k, r; l1, · · · , lr ) exists satisfying the
requirement for positive integers k, r, l1 , · · · , lr , we assume that we are taking
the smallest such n.
For k = 1, it is Theorem 1.
Let k > 1 and assume that the numbers n(k − 1, r; l1, · · · , lr ) are defined
for all li ’s.
Again, for any given k, if li = k for all i ∈ {1, · · · , r}, then the result
follows trivially.
Assuming that the numbers
ai = n(k, r; l1 , · · · , li−1 , li − 1, li+1 , · · · , lr )
are defined for i = 1, · · · , r, we have to show that n(k, r; l1 , l2 , · · · , lr ) exists.
Let n = 1 + n(k − 1, r; a1 , · · · , ar ).
Let an r-colouring c of the k-subsets of the set [n] with colours c1 , · · · , cr
be given. Let m ∈ [n] and Y = [n] \ {m}. An induced r-colouring c∗ of
the (k − 1)-subsets of Y is now defined in the following manner. Given a
(k − 1)-subset S of Y , the colour of S is c∗i if and only if that of S ∪ {m} is
ci in the original colouring.
By the definition of n, for some i there is a set Ai (⊂ [n] \ {m}) of size ai
all of whose (k − 1)-subsets have the same colour c∗i in the c∗ - colouring.
By the definition of ai , the set Ai will contain either a set of size lj all of
whose k-subsets have colour cj for some j 6= i or a set X say of size li − 1 all
of whose k-subsets have colour ci .
4
In the first case we are through. In the second case, X ∪ {m} is a set
of size li . Given a k-subset K of X ∪ {m}, if m does not belong to K then
by the assumption in the above paragraph, K is of colour ci . On the other
hand, if m ∈ K, then since all (k − 1) -subsets of Ai are of colour c∗i , so is
the set K \ {m} and therefore by the definition of the induced colouring c∗ ,
K is of colour ci . This completes the proof.
The following theorem of Erd˝os and Szekeres [25] played a major role
in popularizing Ramsey’s theorem and the subsequent emergence of a new
branch of Combinatorics; we leave its proof as an exercise.
Theorem 4. (Erd˝
os-Szekeres Theorem) For a given positive integer n(≥
3), there is an integer N = N(n) such that any collection of N or more points
in the plane, no three on a line, has a subset of n points forming a convex
n-gon.
Now we take up a result of Schur [67], which appeared in 1916. This is
one among the Ramsey-type results which appeared before Ramsey’s 1930
paper. After the branch of combinatorics called Ramsey theory grew up,
with hindsight, one could see the unifying feature of the seemingly unrelated
results of early Ramsey theory.
Theorem 5. (Schur’s Theorem) Given a positive integer r, there is N(r) ∈
Z+ , such that for any r-colouring of [N(r)], ∃ x, y, z ∈ [N(r)] of the same
colour such that x + y = z; the situation is described by saying that the
equation x + y = z has a monochromatic solution.
Proof: Let N(r) = n(2, r, 3), where n(k, r, l) is as in Theorem 2.
Let χ : [N(r)] → [r] an r-colouring.
This induces an r-colouring χ∗ of the collection of 2-element subsets of
[N(r)] as follows:
χ∗ ({i, j}) = χ(|i − j|), i 6= j ∈ [N].
By definition of N(r), ∃ a 3-element subset {a, b, c} of [N(r)] with a <
b < c such that χ∗ ({a, b}) = χ∗ ({b, c}) = χ∗ ({c, a}), that is, χ(b − a) =
χ(c − b) = χ(c − a).
Since (b − a) + (c − b) = (c − a), we get a monochromatic solution of
x + y = z.
5
Remark 2. From the above proof of Schur’s theorem, in the monochromatic
solution {x, y, z} one may have x = y. For a proof of a strong version giving
a monochromatic solution with distinct integers {x, y, z}, one may see [68].
Remark 3. Schur [67] used Theorem 5 to show that for any m ∈ Z+ , ∃
M = M(m) ∈ Z+ such that for primes p > M, the congruence
xm + y m ≡ z m
(mod p)
always has nontrivial solutions.
We now state van der Waerden’s theorem [72], which is yet another
Ramsey-type result which appeared before Ramsey’s paper.
Theorem 6. (van der Waerden’s Theorem) Given k, r ∈ Z+ , there exists
W (k, r) ∈ Z+ such that for any r-colouring of {1, 2, · · · W (k, r)}, there is a
monochromatic arithmetic progression of k terms.
Exercise 4. From Theorem 6 deduce that given k, r, s ∈ Z+ , there exists
N = N(k, r, s) ∈ Z+ such that for any r-colouring of [N], there are a, d ∈ Z+
such that the set
{a, a + d, · · · , a + kd} ∪ {sd} ⊂ [N]
is monochromatic.
Schur’s theorem and van der Waerden’s Theorem give rise to the natural
question about the existence of monochromatic solutions of the general linear
homogeneous equation
(1)
c1 x1 + · · · + cn xn = 0,
ci (6= 0) ∈ Z.
The following abridged version of a theorem of Rado (see [56], [57], [58])
answers to that question.
Theorem 7. (Rado) For n ≥ 2, equation (1) has monochromatic solution
for any finite colouring
Pof Z, if and only if there is a non-empty subset I ⊂
{1, · · · , n}, such that i∈I ci = 0.
j
Proof: Fix a prime p > 0. For q ∈ Q∗ , write q = pba , where j ∈ Z, a ∈
Z, b ∈ Z+ , gcd(a, b) = 1 and p does not divide ab. The super modulo colour
Sp on Q∗ is defined by:
Sp (q) =
a
(mod p) ∈ F∗p .
b
6
Now, Sp is a (p − 1)-colouring of Q∗ with the property that
Sp (x) = Sp (y) ⇒ Sp (αx) = Sp (αy) ∀ α ∈ Q∗ .
P
Assume that for no non-empty subset I of {1, · · · , n}, i∈I ci ≡ 0 (mod p),
and if possible let x1 , · · · , xn ∈ Z+ be a monochromatic solution w.r.t. Sp
of equation (1). We can assume that gcd (x1 , · · · , xn ) = 1. Rearranging the
indices if necessary, there is k, with n ≥ k ≥ 1 such that
p 6 |xi
and p|xi
for
for
i = 1, · · · , k
k < i ≤ n.
Reducing equation (1) modulo p, we have
¯0 =
k
X
c¯i x¯i =
i=1
k
X
i=1
c¯i
!
x¯1 .
P
Since p 6 |x1 , the above implies ki=1 c¯i = ¯0, which is a contradiction to
our assumption.
P Therefore, if there
P is no non-empty subset I ⊂ {1, · · · , n}, such that
c
=
0
then
{
6 I ⊂ [n]} is a set consisting P
of finitely
i∈I i
i∈I ci : ∅ =
many non-zero integers and hence some prime p will not divide i∈I ci for
any (∅ =
6 )I ⊂ [n] and by the above observation, there is no monochromatic
solution w.r.t. Sp of the equation (1).
This proves that the condition is necessary.
Now, reordering if necessary, we assume that for some k ≥ 2,
(2)
c1 + · · · + ck = 0.
Suppose that a finite colouring of Z+ is given.
If k = n, then x1 = · · · = xn = 1 would be monochromatic solution to
equation (1). So we assume k < n.
Let
(3)
A = gcd (c1 , · · · , ck ) and B = ck+1 + · · · + cn ,
where B can be assumed to be nonzero, for otherwise once again x1 = · · · =
xn = 1 would be a monochromatic solution. We have A > 0 and multiplying
by (−1), if necessary, we can also assume that B > 0.
7
Writing − t =
B
,
gcd (A, B)
we have
−At =
(4)
AB
= BD, say.
gcd (A, B)
Also, ∃λ1 , · · · , λk ∈ Z such that
c1 λ1 + · · · + ck λk = At.
(5)
We choose l ∈ Z+ such that γi = l + λi ≥ 1 ∀ i = 1, · · · k. Let r ∈ Z+
be such that r ≥ max γi . Now, by Exercise 4, there are a and d such that
{a + d, · · · , a + rd} ∪ {dD} is monochromatic.
Let
a + γi d 1 ≤ i ≤ k
(6)
xi =
dD
k < i.
Now,
n
X
ci xi = (a + ld)(c1 + · · · + ck ) + d
k
X
i=1
i=1
ci λi + dD
n
X
ci
i=k+1
= 0 + dAt + dDB
(by equations (2), (3) and (5))
= 0.
(by equation (4))
In other words, equation (6) provides us with a monochromatic solution to
equation (1).
Schur’s theorem, as in Remark 2, can be restated by saying that given
a positive integer r, there is a positive integer n = n(r) such that for any
r-colouring of [n], ∃ x, y with x < y, such that the elements x, y and x + y
are in [n] and are of the same colour.
The above statement is generalized in the following theorem:
Theorem 8. (Folkman-Sanders) Given any two positive integers r and
k, there is a positive integer n = n(r, k) such that ifP[n] is r-coloured, there
are positive
P integers a1 < a2 < · · · < ak satisfying 1≤i≤k ai ≤ n such the
elements i∈I ai are identically coloured as I varies over different non-empty
subsets of {1, 2, · · · , k}.
8
As has been observed in [37], the Folkman-Sanders theorem also follows
from Rado’s theorem (apart from the original papers of Rado, the complete
statement of Rado’s theorem can be found in [37]). One comes to know from
Soifer [68] that Arnautov was yet another mathematician to discover this
result independently and Soifer calls it Arnautov- Folkman-Sanders theorem.
At the end of this section, we take up a theorem of Hilbert [44] which is
generally accepted to be the earliest Ramsey-type theorem. We give a proof
of a theorem of Hilbert [44] by topological methods. We shall not have much
scope to dwell on the application of dynamical systems to Ramsey Theory,
an interesting area which is very active today (see [28] and [14] for instance).
Let T be a continuous map of a topological space X into itself. Then a
point x ∈ X is called a recurrent point for T if for any neighbourhood V of
x, ∃ n ≥ 1 with T n (x) ∈ V .
Now, let X be a compact topological space and T : X → X a continuous
map. Let F denote the family of nonempty closed subsets of X invariant
under T . Ordering by inclusion, we observe that because of compactness of
X, by the finite intersection property, the intersection of a totally ordered
chain in F belongs to F . Hence, by Zorn’s lemma, F has a minimal element
Y0 .
Let y ∈ Y0 and Y ={T n (y) : n ≥ 1}, the forward orbit closure of y. Now,
Y0 being T invariant, {T n (y) : n ≥ 1} ⊂ Y0 and therefore, Y0 being closed,
{T n (y) : n ≥ 1} ⊂ Y0 . But by definition, Y is nonempty and closed. Further,
since T is continuous, Y is invariant under T . Therefore, Y ∈ F and by
minimality Y = Y0 . Hence y ∈ Y which means that each neighbourhood of
y contains T n (y) for some n ≥ 1.
Thus each point of the non-empty set Y0 is a recurrent point for T and
we have proved the following:
Proposition 1. For a continuous map T from a compact topological space
X into itself, the set of recurrent points for T is nonempty.
Let Ω be the collection of sequences made of finitely many symbols. In
other words, if we denote the finite set of symbols by Λ, then Ω consists of
all maps f : Z+ → Λ.
For a, b ∈ Λ the metric d defined below gives the discrete topology on Λ.
0 if a = b
d(a, b) =
1 if a 6= b.
9
+
The space Ω = ΛZ
ω, ω ′ ∈ Ω one defines
with the product topology is metrizable. If for
D(ω, ω ′) =
∞
X
d (ω(n), ω ′(n))
n=1
2n
,
then it is easy to verify that the metric D corresponds to the product topology
on Ω. By Tychonoff’s theorem, (Ω, D) is therefore compact.
Also the semigroup Z+ acts on the elements of Λ in the obvious way by
shifting. That is by the action of n ∈ Z+ , an element ω ∈ Ω goes to ω ′ ∈ Ω
where ω ′ (m) = ω(m + n). The map on Ω corresponding to n = 1 (which in
fact determines the action of the semigroup Z+ ) will be called the shift map
and we shall denote it by σ. The map σ : Ω → Ω is continuous.
The space Ω endowed with the metric D and the Z+ action is a symbolic
flow in the terminology of Dynamical Systems. In a symbolic flow, by saying
that a point is recurrent one means that it is recurrent for the shift map.
Λ is sometimes called the alphabet and a finite sequence of elements in Λ
is called a word. It is clear that two points ω, ω ′ ∈ Ω are close if they agree
on a large initial block of numbers (1, 2, · · · , N). Hence it follows that:
Proposition 2. In a symbolic flow, a sequence ω ∈ Ω is recurrent if and
only if every word occurring in ω occurs a second time.
Consequently, a most general recurrent point ω will look like:
(7)
ω = [(aω (1) a)ω (2) (aω (1) a)]ω (3) [(aω (1) a)ω (2) (aω (1) a)] · · ·
where a = ω(1) ∈ Λ and ω (i) ’s are arbitrary words composed of elements
of Λ.
Theorem 9. (Hilbert) Given a finite colouring on Z+ and a positive in+
teger l, one can find l elements m1 ≤ mP
such that if
2 ≤ · · · ≤ ml in Z
l
P (m1 , · · · , ml ) denotes the set of sums
i=1 c(i)mi , c(i) = 0 or 1, then
infinitely many translates of P (m1 , · · · , ml ) are of the same colour.
Proof: Let χ : Z+ → {c1 , c2 , · · · , cq } be a q-colouring on Z+ . Let Λ =
{1, 2, · · · , q} and Ω be defined as above. We consider the element ξ ∈ Ω
where
ξ(n) = i ⇐⇒ n ∈ χ−1 (ci ), i = 1, 2 · · · q.
10
Case I. (ξ is a recurrent point)
Let ξ has the form given in (7) and
ω0
ω1
ω2
···
ωn
= a
= ω0 ω (1) ω0
= ω1 ω (2) ω1
···
= ωn−1 ω (n) ωn−1
Now, denoting the length of the word ωn ω (n+1) by mn+1 , we see that if
some symbol occurs at position p in wn , then it occurs at positions p and
p + mn+1 in ωn+1 = ωn ω (n+1) ωn . Thus the symbol a occurs at positions
1, 1 + m1 , 1 + m2 , 1 + m1 + m2 and in general at positions belonging to
1 + P (m1 , · · · ml ) for any l. Since every finite configuration occurs infinitely
often in ξ, it is now clear that χ−1 (a) contains infinitely many translates of
P (m1 , · · · ml ).
Case II. (ξ is not a recurrent point)
In this case we consider the forward orbit closure X of ξ in Ω. The shift
operator takes points of X to X and therefore by Proposition 1 there is a
recurrent point say w for the shift operator σ in X. Let w be of the form
given in (7). Therefore, there exists a sequence of positive integers {nk } such
that σ nk (ξ) → w. If a is the leading symbol in w, then arguing as before, a
occurs at positions belonging to 1 + P (m1, · · · ml ). Choose k such that σ nk (ξ)
agrees with w for (1 + m1 + · · · + ml ) terms. Then ξ(nk + p) = a whenever
p ∈ (1 + P (m1 , · · · ml )). One can assume that nk → ∞. For, otherwise, a
finite translate of ξ would be recurrent and one could then invoke the first
case. Therefore we obtain that 1+nk +P (m1 , · · · ml ) ∈ χ−1 (a) for a sequence
{nk } where nk → ∞ and this proves the theorem.
The following result of Hindman [45] implies Arnautov-Folkman-Sanders
theorem (Theorem 8) as well as Hilbert’s theorem (Theorem 9); this was first
conjectured by Sanders in his Ph.D. thesis [64].
Theorem 10. (Hindman ) Given any finite colouring of Z+ , there always
exist an infinite subset of Z+ all the finite sums of which are of the same
colour.
11
The proof of Hindman was later simplified by Baumgartner [13]. Furstenberg and Weiss [29] used the notion of proximality to establish Hindman’s
theorem. The Graham-Rothschild-Spencer monograph [37] contains two
topological proofs of Hindman’s theorem; one of them is the FurstenbergWeiss proof, the other being the ultrafilter-proof due to Glazer. The proof
of Baumgartner is also available in [37].
2
Early Ramsey-type theorems and
some generalizations: Part II
The theorem of van der Waerden was a prelude to a very important theme
where interplay of several areas of Mathematics would be seen.
The following result (see Anderson [11], see also [48], [1]) generalizes van
der Waerden’s Theorem to higher dimensions.
Theorem 11. (Gr¨
unwald) Let d, r ∈ Z+ , the set of positive integers. Then
given any finite set S ⊂ (Z+ )d , and an r-colouring of (Z+ )d , there exists a
positive integer ‘a’ and a point ‘v’ in (Z+ )d such that the set aS + v is
monochromatic.
Proof: The theorem will follow from the following statement:
A(S): Given any finite set S ⊂ (Z+ )d , for each k ∈ Z+ , ∃ n = n(k) such
def
that for every k-colouring of Bn = {(a1 , . . . , ad ) : ai ∈ Z+ , 1 ≤ ai ≤ n}, Bn
contains a monochromatic subset of the form aS + v for some a ∈ Z+ and
v ∈ Bn .
Since A(S) is obviously true if |S| = 1, it is enough to show that A(S) ⇒
A(S ∪ {s}) for any s ∈ (Z+ )d .
For the induction procedure, once A(S) is established for a given S, we
prove the following intermediate statement C(p) corresponding to a positive
integer p. Once C(p) is established for any positive integer p, it will lead to
the statement A(S ∪ {s}) and we shall be through.
C(p): Let S ⊂ (Z+ )d be fixed for which A(S) is true. Then for given
k ∈ Z+ and s ∈ (Z+ )d , ∃n = n(p, k, s) ∈ Z+ such that for each k-colouring
of Bn , there are positive integers a0 , a1 , . . . , ap and a point u ∈ (Z+ )d such
12
that the each of the (p + 1) sets
def
Tq = u +
X
X
ai S +
0≤i<q
q≤i≤p
ai
!
s, 0 ≤ q ≤ p,
are monochromatic subsets of Bn .
C(0) holds trivially and we have to show that C(p) ⇒ C(p + 1).
Let n = n(p, k, s) be the integer specified for C(p). Now, given a kcolouring of (Z+ )d , we define the associated colouring of (Z+ )d such that
two points u and v will have the same colour in this new colouring iff the
lattice points in the cubes u + Bn and v + Bn are identically coloured in the
original k- colouring of (Z+ )d .
def
Clearly, this associated colouring of (Z+ )d is a k ′ - colouring where k ′ =
k .
Now, from A(S), it follows that ∃ an integer n′ = n′ (k ′ ) such that for
every k ′ -colouring of Bn′ , Bn′ contains a monochromatic subset of the form
a′ S + v ′ for some a′ (6= 0) ∈ Z+ and v ′ ∈ Bn′ .
Let N = n + n′ + 1. Let a k-colouring of BN be given. In an arbitrary
way we extend this to a k-colouring of (Z+ )d . Now, corresponding to the
associated k ′ - colouring of (Z+ )d , Bn′ contains a monochromatic subset of
the form a′ S + v ′ . This means that the |S|-cubes Bn + a′ t + v ′ , t ∈ S are
coloured identically in the original k- colouring. We observe that all these
cubes lie in BN . By C(p), for any t ∈ S, the cube Bn + a′ t + v ′ contains
monochromatic sets
!
X
X
Tq (t) = a′ t + v ′ + u +
ai S +
ai s, 0 ≤ q ≤ p.
nd
0≤i<q
q≤i≤p
Setting b0 = a′ and bi = ai−1 , 1 ≤ i ≤ p + 1, we claim that the sets
!
X
X
Tq′ = (v ′ + u) +
bi S +
bi s, 0 ≤ q ≤ p + 1
0≤i<q
q≤i≤p+1
are monochromatic.
For q = 0,
T0′ =(v ′ + u) +
X
0≤i≤p+1
13
bi
!
s
is a singleton and the claim is established.
For q ≥ 1, Tq′ = ∪t∈S Tq−1 (t). Since Bn + a′ t + v ′ are identically coloured
for different t’s belonging to S, it follows that the monochromatic sets Tq−1 (t)
are of the same colour and hence Tq′ = ∪t∈S Tq−1 (t) is a monochromatic subset
of BN .
Thus C(p + 1) holds with n(p + 1, k, s) = N.
Now that C(p) is established for all integers p ≥ 0, the particular case
p = k gives us an integer n = n(k, k, s) such that given any k-colouring of
Bn , ∃(k + 1) monochromatic sets T0 , . . . , Tk in Bn . By pigeonhole principal,
two of these sets, say Tr , Tq with r < q are of the same colour.
Writing
!
!
X
X
X
Tr = u +
ai S +
ai s +
ai s
0≤i<r
r≤i<q
q≤i<k+1
X
X
and
Tq = u +
X
ai S +
0≤i<r
ai S +
r≤i<q
q≤i<k+1
ai
!
s,
and choosing s0 ∈ S (S being nonempty), it follows that the set
T =u+
X
0≤i<r
ai
!
s0 +
X
!
ai (S ∪ {s}) +
r≤i<q
X
q≤i<k+1
ai
!
s
is contained in BN and is monochromatic.
P
P
P
Setting a =
a
and
v
=
u
+
a
s
+
a
s,
i
i
0
i
r≤i<q
0≤i<r
q≤i<k+1
T = a(S ∪ {s}) + v and this establishes A(S ∪ {s}).
We discuss the theorem of Hales and Jewett [40] which reveals the combinatorial nature of van der Waerden’s theorem. As has been said in [37]:
“the Hales-Jewett theorem strips van der Waerden’s theorem of its unessential elements and reveals the heart of Ramsey theory”.
Let
Ctn = {x1 x2 . . . xn : xi ∈ {1, 2, . . . t}},
the collection of words of length n over the alphabet of t symbols 1, 2, . . . t.
14
A combinatorial line in Ctn is a set of t points in Ctn ordered as X1 , X2 , . . . ,
Xt where Xi = xi1 xi2 . . . xin such that for j belonging to a nonempty subset
I of {1, . . . n} we have xsj = s for 1 ≤ s ≤ t and x1j = · · · = xtj = cj for
some cj ∈ {1, . . . t} for j belonging to the complement (possibly empty) of I
in {1, . . . n}.
For example, for t = 3 and n = 5, the following is a combinatorial line in
C35 :
11122
21222
31322
Theorem 12. (Hales-Jewett) Given any two positive integers r and t,
there exists a positive integer n = HJ(r, t) such that if Ctn is r-coloured then
there exists a monochromatic combinatorial line.
Observing the above example of the combinatorial line in C35 , if we identify
the collection of words in C35 with the set of integers in their usual expression in decimal system, it is easy to see that the above combinatorial line
corresponds to a three term arithmetic progression with common difference
10100.
Thus, if we consider an r-colouring of Ctn (with suitably large t), induced
from a given r-colouring of the integers which have base d representation with
d ≥ t, Hales-Jewett Theorem would imply the existence of a monochromatic
arithmetic progression of t terms.
Erd˝os and Turan [26] conjectured that any subset of Z+ with positive
upper natural density contains arithmetic progressions of arbitrary length,
¯
where, for A ∈ Z+ , the upper natural density d(A)
of A is defined by
|A ∩ [N]|
¯
d(A)
= lim sup
,
N
N →∞
where [N] denotes the set {1, 2, . . . , N}.
Remark 4. In connection with Schur’s theorem, the situation is quite different; though the set of even integers and the set of odd integers have the
same upper natural density 1/2 in Z+ , there is no solution of x + y = z in
the subset of odd positive integers.
15
Towards the above mentioned conjecture of Erd˝os and Turan, in 1953
Roth [63] proved that any subset A of the set Z+ of positive integers with
positive upper natural density will always contain a three-term arithmetic
progression. Later, Szemer´edi first improved [69] Roth’s result to that of A
possessing a four-term arithmetic progression and finally in 1974, in a famous
paper [70] proved the general Erd¨os-Turan conjecture by a sophisticated combinatorial argument. Later, Furstenberg [27] gave an ergodic theoretic proof
of Szemer´edi’s theorem which opened up the subject of Ergodic Ramsey
Theory (see [28], [14] and [50]). There have been other important proofs of
Szemer´edi’s theorem since then.
Defining rk (n) to be the smallest integer such that whenever A ⊂ [n] satisfies |A| > rk (n), A contains an arithmetic progression of k terms, Szemer´edi’s
result [70] implies that
rk (n) = o(n).
For the case k = 3, Roth’s proof [63] gave r3 (n) = O log nlog n ; successive improvements in this direction were obtained by Heath-Brown [43],
Szemer´edi [71] and Bourgain [17], the result of Bourgain being
s
!
log log n
.
r3 (n) = O n ·
log n
Regarding estimates of rk (n) for k > 3, Gowers [35] has made a remarkable breakthrough while establishing
n
r4 (n) <
for some absolute constant d > 0,
(log log n)d
where the method seems to go through for rk (n) for k ≥ 4. Apart from the
original paper [35], we recommend the two beautiful articles [36] and [17] for
getting an idea as well as the background of the proof.
Conjecture (Erd˝
os). If A ⊂ Z+ satisfies
X1
= ∞,
a
a∈A
then A contains arithmetic progressions of arbitrary length.
The Green-Tao Theorem [38] we have seen a major breakthrough. Green
and Tao showed that the set of primes contains arithmetic progressions of
arbitrary length.
16
3
Zero-sum problems: Part I
Considering the sums s1 = a1 , s2 = a1 + a2 , · · · , sn = a1 + · · · + an , if no
si is 0 (mod n), then at least two of the si ’s are equal modulo n. Thus, ∃
nonempty I ⊂ {1, · · · , n} such that
(8)
X
ai = 0
(mod n).
i∈I
A generalization of the above problem to an arbitrary finite abelian group
G, is to determine the Davenport’s constant D(G) which is the smallest
positive integer s such that for any sequence g1 , g2 , · · · , gs of (not necessarily
P distinct) elements of G, there is a nonempty I ⊂ {1, · · · , s} such that
∈I gi = 0.
This constant, though attributed to Davenport, seems to have been first
studied by K. Rogers [61] in 1962. This particular reference was somehow
missed-out by most of the authors in this area.
Apart from its interest in zero-sum problems of additive number theory
and non-unique factorization in algebraic number theory (see [34]), this constant has other applications. One of the most important applications of this
can be seen in the proof of the infinitude of Carmichael numbers by Alford,
Granville and Pomerance [3], where some knowledge of zero-sum sequences
in the group of units of Zn is required. Zero-sum results have been also seen
to be useful in an interesting paper of Br¨
udern and Godinho [18].
Given a finite abelian
P group G = Zn1 × Zn2 × · · · × Znr , with n1 |n2 | · · · |nr ,
writing M(G) = 1+ ri=1 (ni −1), it is trivial to see that M(G) ≤ D(G) ≤ |G|.
When G = Zn , observing that the sequence
(1, 1, . . . , 1)
| {z }
(n−1) times
does not have any non-empty subsequence whose sum is zero, one has the
equality
(9)
D(Zn ) = n.
It is known that D(G) = |G| holds if and only if G = Zn .
17
Olson [54] [55] proved that D(G) = M(G) for all finite abelian groups of
rank 2 and for all p-groups.
In the following theorem, we write the result of Olson [54] in the case for
abelian p-groups; we shall see a proof of this in the next section.
Theorem 13. (Olson) For a finite abelian p-group G = Zpr1 × Zpr2 ×
· · · × ZprP
m , given a sequence S = (s1 , s2 , · · · , sk ) of elements in G, such that
ri
k ≥ 1+ m
i=1 (p − 1), writing fe (S) for the number of subsequences of even
length of S which sum up to zero and fo (S) for the number of subsequences
of odd length which sum up to zero, we have
fe (S) − fo (S) ≡ −1
(mod p).
In particular, we have
D(G) = M(G) = 1 +
m
X
(pri − 1).
i=1
We take up generalization of the problem in another direction, where one
asks about zero-sum subsequence of a prescribing size.
In this particular direction, a theorem of Erd˝os, Ginzburg and Ziv [24]
(henceforth, referred to as the EGZ theorem) says that
Theorem 14. (EGZ theorem) For any positive integer n, any sequence
a1 , a2 , · · · , a2n−1 of 2n − 1 integers has a subsequence of n elements whose
sum is 0 modulo n.
A prototype of zero-sum theorems, the EGZ theorem continues to play a
central role in the development of this area of combinatorics.
The article [7] of Alon and Dubiner contains five proofs of Theorem 14,
among other things. One may also find several proofs in the books [1], [52],
[34]. Here we shall see some of these proofs.
We observe that it is enough to prove Theorem 14 when n = p, a prime.
The case n = 1 is trivial.
Assume that the result is true when n is a prime and proceed by induction
on the number of prime factors (counted with multiplicity) of n.
If n > 1 is not a prime, we write n = mp where p is prime and assume
that the result is true for all integers with number of prime factors less than
that of n.
18
Since each subsequence of 2p−1 members of the sequence a1 , a2 , · · · , a2n−1
has a subsequence of p elements whose sum is 0 modulo p, we go on repeatedly
omitting such subsequences of p elements having sum equal to 0 modulo p.
After removing 2m − 2 such sequences one after another, we are left with
2pm − 1 − (2m − 2)p = 2p − 1 elements and we can have at least one more
subsequence of p elements with the property that sum of its elements is equal
to 0 modulo p.
Thus, one can find 2m − 1 pairwise
P disjoint subsets I1 , I2 , · · · , I2m−1 of
{1, 2, · · · , 2mp − 1} with |Ii | = p and j∈Ii aj ≡ 0 (mod p) for each i.
P
Writing bi = p1 j∈Ii aj , by the induction hypothesis, this new sequence
has a subsequence of m elements whose sum is divisible by m. The union
of the corresponding sets Ii will supply the desired subsequence of mp = n
elements of the original sequence such that the sum of the elements of this
subsequence is divisible by n.
We state a couple of theorems which will be used by us.
We shall need the following generalized version of Cauchy-Davenport inequality [20], [21] (one can also look into [49] or [52] for instance):
Theorem 15. (Cauchy-Davenport) Let A1 , A2 , · · · , Ah be non-empty subsets of Fp , the finite field with p elements. Then
!
h
h
X
X
Aj | ≥ min p,
|Aj | − h + 1 .
|
j=1
j=1
Another result which will be required is the following, for a proof of which,
one may look into [1], [46] or [52] for instance.
Theorem 16. (Chevalley-Warning) Let fi (x1 , x2 , · · · , xn ), i = 1, · · · , r,
be r polynomials in Fq [x1 , x2 , · · · , xn ] such that the sum of the degrees of
these polynomials is less than n and fi (0, 0, · · · , 0) = 0, i = 1, · · · , r. Then
there exists (α1 , α2 , · · · , αn ) ∈ Fnq with not all αi ’s zero, which is a common
solution to the system fi (x1 , x2 , · · · , xn ) = 0, i = 1, · · · , r.
Proofs of Theorem 14 in the case n = p, a prime:
Proof I. This proof involves an application of Theorem 15.
19
Consider representatives modulo p in the interval 0 ≤ aj ≤ p − 1 for the
given elements and rearranging, if necessary, we assume that
0 ≤ a1 ≤ a2 ≤ · · · ≤ a2p−1 ≤ p − 1.
We can assume that
aj 6= aj+p−1 , for j = 1, · · · , p − 1,
for otherwise, the p elements aj , aj+1 , · · · , aj+p−1 being equal, the result holds
trivially.
Writing Aj := {aj , aj+p−1}, for j = 1, · · · , p − 1, by Theorem 15,
!
p−1
p−1
X
X
|Aj | − (p − 1) + 1 = p.
Aj | ≥ min p,
|
j=1
j=1
This implies that −a2p−1 ∈
Pp−1
j=1
Aj , and we are through.
Proof II. Following Alon [4] (also see [7]), we now give a proof by applying
Theorem 16.
Given a sequence a1 , a2 , · · · , a2p−1 with ai ∈ Fp , consider the system of
polynomial equations:
2p−1
X
ai xp−1
= 0,
i
i=1
2p−1
X
xp−1
= 0.
i
i=1
Since the sum of degrees of the two equations is 2(p−1) which is less than
2p − 1 and x1 = x2 = · · · = x2p−1 = 0 is a solution, we can apply Theorem
16. Thus there is a nontrivial solution (α1 , · · · , α2p−1) of the above system.
By Fermat’s little theorem,
writing I = {i : αi 6= 0}, from the first
P
equation it follows that i∈I ai = 0 and from the second equation we have
|I| = p.
Proof III. By Theorem 13 of Olson, the sequence
(a1 , 1), (a2, 1), · · · , (a2p−1 , 1)
20
of 2p − 1 elements in Zp ⊕ Zp has a non-empty zero-sum subsequence and the
desired result follows once again by observing that there is only one multiple
of p among the integers 1, 2, . . . , 2p − 1.
Proof IV. We start with the following definition.
Given an n by n matrix A = (aij ) over a field F , its permanent, denoted
by per A, is defined by
X
per A =
a1 α(1) a2 α(2) · · · an α(n) ,
where the summation is taken over all permutations α of [n].
The following is a variant of the permanent lemma; the statement here is
not as in [5]; the statement in [5] is a slightly extended version of a lemma
first proved in [9] (see also [8]).
The permanent lemma. (Alon) Let A = [ai,j ] be a m × m matrix over
Fp such that per A 6= 0.
PmThen for any c1 , · · · , cm ∈ Fp , there are ǫ1 , ǫ2 , · · · , ǫm ∈ {0, 1} such that
j=1 ǫj ai,j 6= ci for all 1 ≤ i ≤ m.
Proof: By induction on m it is rather easy to observe that if
X
Y
xi
P (x1 , · · · , xm ) =
bU
U ⊂[m]
i∈U
is a multilinear polynomial over a commutative ring with identity such that
P (x1 , · · · , xm ) = 0 for each (x1 , · · · , xm ) ∈ {0, 1}m, then P is identically
zero, that is, bU = 0 for all U ⊂ [m].
If possible let the lemma be false. Then there are no ǫ1 , ǫ2 , · · · , ǫm as
above.
We consider the polynomial
!
m
m
Y
X
P (x1 , · · · , xm ) =
ai,j xj − ci .
i=1
j=1
By our assumption, P (x1 , · · · , xm ) = 0 for each (x1 , · · · , xm ) ∈ {0, 1}m.
From P (x1 , · · · , xm ), we obtain the multilinear polynomial P ′ (x1 , · · · , xm )
by first writing P in the standard formQas a sum of monomials andQthen replacing each monomial of the form bU i∈U xδi i , with δi ≥ 1, by bU i∈U xi .
21
Clearly, P ′ (x1 , · · · , xm ) = P (x1 , · · · , xm ) = 0 for each (x1 , · · · , xm ) ∈
{0, 1}m. Therefore, by the observation made in the beginning of the proof,
P ′ is identically zero.
Qm
′
But, the coefficient
of
i=1 xi in P (x1 , · · · , xm ) (which is the same as
Qm
the coefficient of i=1 xi in P (x1 , · · · , xm )) is per A 6= 0 and we arrive at a
contradiction.
Hence the lemma.
Following the treatment in [7], we shall now see how to derive the EGZ
theorem from the above lemma.
For a prime p, we are given a sequence a1 , a2 , · · · , a2p−1 , of elements in
Fp . We identify them with the integers in the set 0, 1, · · · , p − 1 representing
them (mod p) and by rearranging the elements, if necessary, we assume that
a1 ≤ a2 ≤ · · · ≤ a2p−1 .
If there is an i ≤ p − 1, such that ai = ai+p−1 (which means that ai =
ai+1 = · · · = ai+p−1 ), then taking I = {i, i + 1, · · · , i + p − 1}, the theorem is
established.
If there is no such i, we define
bi = ai − ai+p−1 (6= 0) ∀ i, 1 ≤ i ≤ p − 1.
c1 , c2 , · · · , cp−1 be the set of all elements in Fp besides the element
Let
P2p−1 − j=p aj .
Let A = [ai,j ] be the (p − 1) × (p − 1) matrix over Fp defined by ai,j = bj
for all 1 ≤ i, j ≤ p − 1, so that
per A = (p − 1)! ·
p−1
Y
bj 6= 0.
j=1
Therefore,
Pp−1by the permanent lemma, there are ǫ1 , ǫ2 , · · · , ǫp−1 ∈ {0, 1}
such that j=1 ǫj ai,j 6= ci for all 1 ≤ i ≤ p − 1 and hence
p−1
X
2p−1
ǫj ai,j = −
a2p−1 +
aj .
j=p
j=1
Rearranging,
X
p−1
X
(aj+p−1 + ǫi (aj − aj+p−1)) = 0.
j=1
22
Since each term ai+p−1 + ǫi (ai − ai+p−1 ) is either ai+p−1 or ai , this gives a
p-subset of the sequence {ai } the sum of whose elements is 0, as required.
If G is a finite abelian group with exp(G) = n, then the Erd˝os-GinzburgZiv constant s(G) is defined to be the least integer k such that any sequence
S with length |S| ≥ k of elements in G has a zero-sum subsequence of length
exp(G) = n.
In general, for a finite abelian group G with exp(G) = n, smn (G) is defined
(see [31], for instance) to be the least integer k such that any sequence S with
length k of elements in G has a zero-sum subsequence of length mn. Putting
m = 1, one observes that the constant s(G) is the same as sn (G). We shall
use the notation E(G) for the constant s|G| (G).
Harborth [42] and Kemnitz [47] had considered the problem of determining s(G) where G = Zdn ; that is, the problem of finding the smallest natural
number k such that any sequence of k elements in Zdn has a subsequence of
length n summing up to 0, the identity element of the group Zdn .
In geometric terms, s Zdn is the smallest positive integer k such that
given a sequence x1 , x2 , . . . , xk of elements of Zd , not necessarily distinct,
there exists a subsequence xi1 , xi2 , . . . , xin of length n such that its centroid
(xi1 + xi2 + · · · + xin )/n also belongs to Zd .
Observing that the number of elements of Zdn having coordinates 0 or 1
is 2d and considering a sequence where each of these elements are repeated
(n − 1) times, we observe that
(10)
1 + 2d (n − 1) ≤ s(Zdn ).
Again, observing that in any sequence of 1 + nd (n − 1) elements of Zdn ,
there will be at least one element appearing at least n times, we have
(11)
s(Zdn ) ≤ 1 + nd (n − 1).
EGZ theorem says that in the case d = 1, the lower bound 2n − 1 given
by (10) is the exact value of s(Zn ).
There is an early survey on the zero-sum problems by Caro [19]. For
recent developments, one may look into the expository article of Gao and
Geroldinger [31], the book of Geroldinger and Halter-Koch [34] and the survey of Geroldinger [33].
That the trivial lower bound in (10) is the exact value in the case d = 2
as well, that is
s(Z2n ) = 4n − 3,
23
had been known as the Kemnitz Conjecture in the literature.
Kemnitz [47] had verified the conjecture when n is of the form 2e 3f 5g 7h .
For general n, Alon and Dubiner [7] obtained the upper bound
s(Z2n ) ≤ 6n − 5.
Later R´onyai [62] proved that
s(Z2p ) ≤ 4p − 2,
for a prime p, and using this one easily obtains
s(Z2n ) ≤
41
n,
10
by induction on the number of primes dividing n and using the following
inequality of Harborth [42]:
(12)
s(Zdmn ) ≤ min(s(Zdn ) + n(s(Zdm ) − 1), s(Zdm ) + m(s(Zdn ) − 1)).
Finally, Reiher [60] established the Kemnitz Conjecture (see Savchev and
Chen [65] for the related structural analysis).
Geroldinger and Halter-Koch [34] have a more general result which says
that for positive integers m, n with m|n,
s(Zm ⊕ Zn ) = 2m + 2n − 3.
Theorem 17. (Reiher) For a positive integer n, we have
s(Z2n ) = 4n − 3.
Proof. It suffices to show that s(Z2p ) ≤ 4p − 3.
Let X be a sequence of 4p − 3 elements of Z2p .
For any subsequence J of X, let (n, J) denote the number of zero-sum
subsequences of J of length n.
In particular, we have (p, X) = 0 and hence by a result of Alon and
Dubiner [7], (3p, X) = 0.
Now, we deduce the following consequence of Theorem 13.
For any subsequence J = (a1 , b1 ), (a2 , b2 ), · · · , (a(3p−3) , b(3p−3) ) of X, we
have
(13)
1 − (p − 1, J) + (2p − 1, J) + (2p, J) ≡ 0
24
(mod p).
The proof of the statement (13) is as follows. We consider the sequence
J1 consisting of the 3p − 3 elements in (Z/pZ)3 given by (a1 , b1 , 1), · · · ,
(a3p−3 , b3p−3 , 1) along with the element (0, 0, 1) . Now the length of J1 is 3p −
2 ≥ 1 + 3(p − 1), hence we can apply Theorem 13 of Olson. Since the third
co-ordinate of all the above elements is 1, any subsequence of even length of
J1 which sums up to zero has to be of length 2p while any subsequence of odd
length of J1 which sums up to zero has to be of length p. Any subsequence
of length 2p of J1 which sums up to zero and which does not involve the last
term (0, 0, 1) gives a subsequence of length 2p of J which sums up to zero
and vice versa. However any subsequence of length 2p of J1 which sums up
to zero and which involves the last term (0, 0, 1) actually gives a subsequence
of length 2p − 1 of J which sums up to zero and vice versa. Similar is the
case for the zero-sum subsequences of length p. Now using the above result
of Olson and keeping in mind the fact that (p, J) = 0, we get the desired
result.
Now,
X
[1 − (p − 1, I) + (2p − 1, I) + (2p, I)] ≡ 0 (mod p).
where I runs over all possible subsequences I of length 3p − 3 of X.
Therefore,
2p − 2
3p − 2
4p − 3
(2p − 1, X)
(p − 1, X) +
−
p−2
2p − 2
3p − 3
2p − 3
(2p, X) ≡ 0 (mod p),
+
p−3
which gives
(14)
3 − 2(p − 1, X) + (2p − 1, X) + (2p, X) ≡ 0 (mod p).
Further,
(15)
(2p, J) ≡ −1
(mod p),
for any subsequence J of X of length 3p − 2 or 3p − 1, and
(16)
(2p, X) ≡ −1
25
(mod p),
by considering the relevant sequences in (Z/pZ)3 obtained by putting 1 in
the last coordinate and using Theorem 13.
Once again following the argument employed in deducing (13) and using
(16), we have
(17)
(p − 1, X) − (2p − 1, X) + (3p − 1, X) ≡ 0
(mod p).
Finally, we prove that
(18)
(p − 1, X) ≡ (3p − 1, X) (mod p).
We proceed as follows. Let θ denote the number of partitions of X =
A ∪ B ∪ C into disjoint subsequences A, B and C where A is a zero-sum
subsequence of length p − 1 and C is a zero-sum subsequence of length 2p.
We count θ in two different ways.
First,
X
θ=
(2p, X \ A),
A
where the summation runs over all zero-sum subsequences of length p − 1.
Using (15), this gives
(19)
θ ≡ −(p − 1, X) (mod p).
Again,
θ=
X
(2p, A′ ),
A′
where the summation runs over all zero-sum subsequences of length 3p − 1
and by using (15), we have
(20)
θ ≡ −(3p − 1, X) (mod p).
From (19) and (20), we get (18).
Now, adding (14) and (17), by (18), we have
(2p, X) ≡ −3
– contradicting (16).
26
(mod p),
4
Zero-sum problems: Part II
In this section we deal with some results for general finite abelian groups and
bounds for some of the combinatorial constants in the case of higher ranks.
We start with the following result of Bollob´as and Leader [16] which
clearly implies the EGZ theorem by taking r = n − 1.
Theorem 18. (Bollob´
as and Leader) Let G be an abelian group of order
n and r be a positive integer. Let A denote the sequence (a1 , a2 , · · · , an+r ) of
n + r not necessarily distinct elements of G. Then, if 0 is not an n-sum, the
number of distinct n-sums of A is at least r + 1.
A simple proof of the above theorem has been given by Yu [73] using the
following generalization of Cauchy-Davenport Theorem (Theorem 15) due to
Scherk [66].
Scherk’s Lemma. Let A and B be two subsets of a finite abelian group G.
Suppose 0 ∈ A∩B and suppose that the only solution of a+ b = 0, a ∈ A, b ∈
B is a = b = 0. Then,
|A + B| ≥ |A| + |B| − 1.
Proof: We closely follow the proof of Scherk [66].
The result is obvious for |B| = 1. Let |B| = n > 1 and assume that the
result holds for |B| ≤ n − 1.
Choose b (6= 0) ∈ B.
Since by our assumption, 0 6∈ A+ b and 0 ∈ A, from the equality |A+ b| =
|A|, it follows that ∃t ∈ A such that t + b 6∈ A.
Let
def
B1 = {g ∈ B | t + g 6∈ A}.
Since b ∈ B1 , the set B1 is non-empty. Also, since t ∈ A, we have 0 6∈ B1 ,
and hence B1 ( B.
Let
def
A1 = t + B1 ⊂ A + B,
def
A2 = A ∪ A1 ,
def
B2 = B \ B1 .
27
Now, A1 ∩ A = ∅ and |A1 | = |B1 | and therefore,
(21)
|A2 | + |B2 | = |A| + |A1 | + |B2 | = |A| + |B1 | + |B2 | = |A| + |B|.
We claim that
(22)
A2 + B2 ⊂ A + B.
Let a2 ∈ A2 , b2 ∈ B2 . If a2 ∈ A, then a2 + b2 ∈ A + B2 ⊂ A + B. If
a2 ∈ A1 , then a2 + b2 = (t + b′ ) + b2 , for some b′ ∈ B1 . Now, (t + b′ ) + b2 =
(t + b2 ) + b′ ∈ A + B1 ⊂ A + B. This establishes the claim (22).
We observe that 0 ∈ A ⊂ A2 and since 0 6∈ B1 , 0 ∈ B2 . Now, if possible
let a2 + b2 = 0 with a2 ∈ A2 , b2 ∈ B2 . If a2 ∈ A1 , then arguing as before,
a2 + b2 = (t + b2 ) + b′ , where (t + b2 ) ∈ A and b′ ∈ B1 ⊂ B and hence
0 = a2 + b2 = (t + b2 ) + b′ would imply b′ = 0, contradicting the fact that
0 6∈ B1 . Therefore, a2 ∈ A. Since B2 ⊂ B, we have a2 = b2 = 0. Since
B1 ( B, by the induction hypothesis,
|A2 + B2 | ≥ |A2 | + |B2 | − 1,
and therefore from (21) and (22),
|A + B| ≥ |A2 + B2 | ≥ |A2 | + |B2 | − 1 = |A| + |B| − 1.
At this point, we introduce some more notations. Given a sequence S =
(x1 , . . . , xk ) of elements
of an abelian group G, for any 1 ≤ l ≤ k, we shall
P
use the notation l (S) to denote the set of all l-sums of S (by an l-sum
P one
means a sum xi1 P
+ · · · + xil of a subsequence P
of length l of S) and
≤l (S)
P
to denote ∪1≤t≤l t (S). One simply writes (S) in place
P of k (S), the
set of sums of all the subsequences of S. We shall write
S to denote the
sum of all elements of S and |S| to denote the length k of S (since it will be
understood from the context, the notation will not create confusion with the
cardinality of a finite set).
The deduction of the following from Scherk’s Lemma is not difficult; we
leave it as an exercise.
Lemma 1. Let S be a sequence of n elements in an abelian group G of
order n and let h be the maximum number that any element of G occurs in
S. Then
X
(S).
0∈
≤h
28
Now, we state the following result of Gao [30] (see also [34], Proposition
5.7.9).
Theorem 19. For a finite abelian group G of order n, we have
(23)
E(G) = D(G) + n − 1,
where as has been stated before, E(G) = s|G| (G).
Since it is trivial to observe that for a finite abelian group G of order n
D(G) ≤ n, from the above theorem it follows that E(G) ≤ 2n − 1. It should
be noted that from the EGZ theorem, by induction on the rank it follows
that for a finite abelian group G of order n, E(G) ≤ 2n − 1.
Proof of Theorem 19. It is easy to observe that by appending a sequence of
n − 1 zeroes to a sequence of length D(G) − 1 with no zero-sum subsequence
(which exists by the definition of D(G)), the resulting sequence of length
D(G) + n − 2 will have no zero-sum subsequence of length n and hence
E(G) ≥ D(G) + n − 1.
We proceed to establish that
(24)
E(G) ≤ D(G) + n − 1.
Let A be any
Psequence of m = D(G) + n − 1 elements of G and we have to
show that 0 ∈ n (A). We can assume that 0 is the most repeated element
in the sequence and arrange A to be of the form
A = (a1 , a2 , . . . , am−h , 0, 0, . . . , 0),
| {z }
h times
with all ai 6= 0.
Clearly, we can assume that h ≤ n.
Let W be aPsubsequence of (a1 , a2 , . . . , am−h ), maximal subject to the
condition that
W = 0.
From the maximality of W and the definition of D(G), it is easy to observe
that m − h − |W | < D(G), so that |W | > m − h − D(G) = n − h − 1.
P
If |W | ≤ n, then appending n − |W | ≤ h zeros, we see that 0 ∈ n (A).
29
If |W | ≥ n + 1, repeatedly applying Lemma 1 to W , we findP
a system
of disjoint subsequences W1 , W2 , . . . , Wv satisfying the conditions
Wi = 0
and |Wi | ≤ h, for each i such that
|W − W1 − · · · Wv | ≤ n − 1
and
|W − W1 − · · · Wv−1 | ≥ n.
Therefore,
n − 1 ≥ |W − W1 − · · · Wv | ≥ n − |Wv | ≥ n − h.
Writing W0 = W − W1 − · · · Wv , we have P
n − 1 ≥ |W0 | ≥ n − h and
as before, appending n − |W0 | ≤ h zeros, 0 ∈ n (A). This completes the
proof.
The following result of Hamidoune [41] confirmed a conjecture of Caro
[19] with some conditions. When n is prime it had already been observed
by Alon, Bialostocki and Caro [6]; later Grynkiewicz [39] established the
conjecture of Caro in full generality.
Theorem 20. Let G be an abelian group of order n and k a positive integer.
Let (w1 , w2 , ..., wk ) be a sequence of integers where each wi is co-prime to n.
Then, given a sequence S : (x1 , x2 , ..., xk+n−1 ) of elements of G, if x1 is the
most repeated element in the sequence, we have
!
k
k
X
X
wi xσ(i) =
wi x1 ,
1
1
for some permutation σ of {1, 2, . . . , k + n − 1}.
Remark 5. Taking G = Z/nZ, k = n and wi = 1, for all i, in the above
theorem, we get the EGZ theorem.
The following result of Adhikari, Chintamani, Moriya and Paul [2], in the
spirit of Theorem 18 of Bollob´as and Leader, implies the above theorem.
Theorem 21. Let (w1 , w2 , ..., wk ) be a sequence of integers where each wi is
co-prime to n. Then, given a sequence A : (x1 , x2 , ..., xk+r ) of elements of G,
30
where
Pk 1 ≤ r ≤ n − 1, if 0 is the most repeated element in the sequence, and
1 wi xσ(i) 6= 0, for all permutations σ of [k + r], we have
( k
)
X
wi xσ(i) : σ is a permutation of [k + r] ≥ r + 1.
1
Now, we turn to the constant s(Zdn ) general d. The following result of
Alon and Dubiner [10] says that for any fixed d, the growth of s(Zdn ) is linear
in n.
Theorem 22. (Alon and Dubiner) There is an absolute constant c > 0
so that
(25)
s(Zdn ) ≤ (cd log2 d)d n, for all n.
Alon and Dubiner conjecture the existence of an absolute constant c such
that
s(Zdn ) ≤ cd n, for all n and d.
Harborth [42] proved that s(Z33 ) = 19; this is strictly greater than the
corresponding lower bound given in (10), namely, 17.
The following result of Elsholtz [23] shows that for d ≥ 3 and an odd
integer n ≥ 3, the lower bound given in (10) is strictly less than the exact
value of s(Zdn ).
Theorem 23. (Elsholtz) For an odd integer n ≥ 3, one has the following
inequality:
d
s(Zdn ) ≥ (1.125)[ 3 ] (n − 1)2d + 1.
The above result implies that s(Z3n ) ≥ 9n − 8. It has been conjectured
(see Gao and Thangadurai [32]) that s(Z3n ) = 9n − 8.
An improvement of Theorem 23 has been obtained in [22]. The new
ingredient in the proof in [22], is a lower bound for s(Z4n ), namely, s(Z4n ) ≥
20n − 19 and the authors conjecture that this lower bound give the precise
value for all odd n ≥ 4.
We now give a proof of the following; we shall closely follow the original
proof of Olson [54].
31
Proof of Theorem 13. We use multiplicative notation for G in this proof.
Since an obvious example shows that the right hand side is a lower bound for
D(G), a combinatorial interpretation of the following observation establishes
the theorem.
P
Observation: If k ≥ 1 + ri=1 (pei − 1), then given a sequence g1 , . . . , gk of
elements of G, in the group-ring R of G over Zp one has
(1 − g1 )(1 − g2 ) · · · (1 − gk ) = 0.
(26)
If x1 , . . . , xr is the standard basis for G, where xi is of order pei , then
since each gj can be can be written as a product of these basis elements,
applying the identity 1 − uv = (1 − u) + u(1 − v) repeatedly, the left hand
side in equation (26) can be expressed as a sum of elements of the form
g
r
Y
(1 − xtii ), where g ∈ G and
r
X
ti = k > (pei − 1).
i=1
i=1
Since k > (pei − 1), ti ≥ pei for some i, which would imply that
(1 − xtii ) = 0.
Hence equation (26) holds.
In the remaining part, we talk about some general results about Davenport constant. Emde Boas and Kruyswijk [15], Baker and Schmidt [12] and
Meshulam [51] gave upper bounds for Davenport constant which involves the
exponent of the group and the cardinality of the group G. The best known
bound is due to Emde Boas and Kruyswijk [15]:
|G|
(27)
D(G) ≤ m 1 + log
,
m
where m is the exponent of G. We here sketch a proof by Alford, Granville
and Pomerance [3] which involves modifying the above Proof of Theorem 13.
Sketch of the proof of (27): Let g1 , g2 , . . . , gk be a sequence of elements
of G where
|G|
.
k ≥ m 1 + log
m
32
We choose a prime q ≡ 1 (mod m).
Our aim is to find elements a1 , a2 , . . . , ak ∈ F∗q , such that in the group
ring Fq [G] we have
(28)
(a1 − g1 )(a2 − g2 ) · · · (ak − gk ) = 0.
If no subsequence of g1 , P
g2, . . . , gk has product equal to 1, writing (a1 −
g1 )(a2 − g2 ) · · · (ak − gk ) = g∈G kg g, k1 = a1 a2 . . . ak 6= 0 would then contradict equation (28).
ˆ to a ring
Extending any character χ : G → F∗q in the character
groupPG,
P
homomorphism χ : Fq [G] → Fq by defining χ( g∈G kg g) =
g∈G kg χ(g),
from the orthogonality relations of group characters, it follows that for b ∈
ˆ
Fq [G], b = 0 if and only if χ(b) = 0 for all χ ∈ G.
Applying the greedy algorithm one finds a1 , a2 , . . . , ak ∈ F∗q so that for
ˆ there exists j, 1 ≤ j ≤ k, such that χ(gj ) = aj implying that
each χ ∈ G,
!
k
Y
χ
(ai − gi ) = 0,
i=1
which in turn imply the equality in (28).
References
[1] S. D. Adhikari, Aspects of combinatorics and combinatorial number theory, Narosa, New Delhi, 2002.
[2] S. D. Adhikari, Mohan N. Chintamani, Bhavin K. Moriya and Prabal Paul, Weighted sums in Finite abelian groups, Uniform Distribution
Theory, 3, No. 1, 105–110 (2008).
[3] W. R. Alford, A. Granville and C. Pomerance, There are infinitely many
Carmichael numbers, Annals of Math., 139 (2), no. 3, 703-722 (1994).
[4] N. Alon, Tools from higher algebra, Handbook of combinatorics, Vol. 1,
2, 17491783, Elsevier, Amsterdam, 1995.
[5] N. Alon, Combinatorial Nullstellensatz, Recent trends in combinatorics
(M´atrah´aza, 1995), Combin. Probab. Comput. 8, 7–29 (1999).
33
[6] N. Alon, A. Bialostocki and Y. Caro, The Extremal cases in the Erd˝osGinzburg-Ziv theorem, unpublished.
[7] N. Alon and M. Dubiner, Zero-sum sets of prescribed size, Combinatorics, Paul Erd˝os is eighty (Volume 1), Keszthely (Hungary), 33–50,
(1993).
[8] N. Alon, N. Linial and Meshulam, Additive bases of vector spaces over
prime fields, J. Combinatorial Theory, Ser A 57, 203–210 (1991).
[9] N. Alon and Tarsi, A nowhere-zero point in linear mappings, Combinatorica 9, 393-395 (1989).
[10] N. Alon and M. Dubiner, A lattice point problem and additive number
theory, Combinatorica 15, 301–309 (1995).
[11] P. G. Anderson, A generalization of Baudet’s conjecture (van der Waerden’s Theorem), Amer. Math. Monthly, 83, 359–361, (1976).
[12] R. C. Baker and W. Schmidt, Diophantine problems in variables restricted to the values of 0 and 1, J. Number Theory, 12 (1980), 460-486.
[13] J. Baumgartner, A short proof of Hindman’s theorem, J. Combinatorial
Theory, Ser A 17, 384–396 (1974).
[14] V. Bergelson, Ergodic Ramsey Theory - an Update, London Mathematical Society Lecture Note Series 228, Cambridge University Press, 1996.
[15] P. van Emde Boas and D. Kruswjik, A combinatorial problem on finite
abelian group III, Z. W.1969-008 (Math. Centrum, Amsterdam).
[16] B. Bollob´as and I. Leader, The number of k-sums modulo k, J. Number
Theory, 78, no. 1, 27–35 (1999).
[17] J. Bourgain, On triples in arithmetic progression, Geom. Funct. Anal.,
9, no. 5, 968–984 (1999).
[18] J. Br¨
udern and H. Godinho, On Artin’s conjecture, II: Pairs of additive
forms, Proc. London Math. Soc. (3) 84 (2002), no. 3, 513–538.
[19] Y. Caro, Zero-sum problems - a survey, Discrete Math. 152, 93-113
(1996).
34
´
[20] A. L. Cauchy, Recherches sur les nombres, J. Ecole
polytech., 9, (1813)
99–116.
[21] H. Davenport, On the addition of residue classes, J. London Math. Soc.,
10, (1935) 30–32.
[22] Y. Edel, C. Elsholtz, A. Geroldinger, S. Kubertin and L. Rackham, Zerosum problems in finite abelian groups and affine caps, Quart. J. Math.
58, 159–186 (2007).
[23] C. Elsholtz, Lower bounds for multidimensional zero sums, Combinatorica, 24, no. 3, 351–358 (2004).
[24] P. Erd˝os, A. Ginzburg and A. Ziv, Theorem in the additive number
theory, Bull. Research Council Israel, 10F, 41–43 (1961).
[25] P. Erd˝os and G. Szekeres, A Combinatorial Problem in Geometry, Compositio Math. 2, 464–470 (1935).
[26] P. Erd˝os and P. Turan, On some sequences of integers, J. London Math.
Soc. 11, 261–264 (1936).
[27] H. Furstenberg, Ergodic behaviour of diagonal measures and a theorem of
Szemer´edi on arithmetic progressions, J. d’Analyse Math. 31, 204–256
(1977).
[28] H. Furstenberg, Recurrence in Ergodic Theory and Combinatorial Number Theory, Princeton University Press, 1983.
[29] H. Furstenberg and B. Weiss, Topological dynamics and combinatorial
number theory, J. Analyse Math., 34, 61–85 (1978).
[30] W. D. Gao, A combinatorial problem on finite abelian groups, J. Number
Theory, 58, 100–103 (1996).
[31] W. D. Gao and A. Geroldinger, Zero-sum problems in finite abelian
groups: a survey, Expo. Math. 24, 337–369 (2006).
[32] W. D. Gao and R. Thangadurai, On zero-sum sequences of prescribed
length, Aequationes Math. 72, 201–212 (2006).
35
[33] A. Geroldinger, Additive group theory and non-unique factorizations, in:
A. Geroldinger, I. Ruzsa (Eds.), Combinatorial number theory and additive group theory, in: Adv. Courses Math. CRM Barcelona, Birkh¨auser
Verlag, Basel, 2009.
[34] A. Geroldinger and F. Halter-Koch, Non-unique factorizations: Algebraic, combinatorial and analytic theory. Pure and Applied Mathematics
(Boca Raton), 278, Chapman & Hall/CRC, Boca Raton, FL, 2006.
[35] W. T. Gowers, A new proof of Szemer´edi’s theorem for arithmetic progressions of length four, GAFA, 8, 529–551 (1998).
[36] W. T. Gowers, Fourier analysis and Szemer´edi’s theorem, Proceedings
of the International Congress of Mathematicians, Vol. I (Berlin, 1998).
Doc. Math., Extra Vol. I, 617–629 (1998).
[37] R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey Theory, 2nd
Edition, John Wiley & Sons, 1990.
[38] B. Green and T. Tao, The primes contain arbitrarily long arithmetic
progressions, Annals of Math. (2) 167, no. 2, 481–547 (2008).
[39] D. J. Grynkiewicz, A weighted Erd˝os-Ginzburg-Ziv theorem, Combinatorica, 26, no. 4, 445–453 (2006).
[40] A. W. Hales and R. I. Jewett, Regularity and positional games, Trans.
Amer. Math. Soc. 106, 222–229 (1963).
[41] Y. O. Hamidoune, On weighted sums in abelian groups, Discrete Math.,
162, 127-132 (1996).
[42] H. Harborth, Ein Extremalproblem f¨
ur Gitterpunkte, J. Reine Angew.
Math. 262/263, 356–360 (1973).
[43] D. R. Heath-Brown, Integer sets containing no arithmetic progressions,
J. London Math. Soc. (2) 35, 385–394 (1987).
¨
[44] D. Hilbert, Uber
die Irreduzibilit¨at ganzer rationaler Funktionen mit ganzahligen Koeffizienten, J. Math. 110 , 104–129 (1892).
[45] N. Hindman, Finite sums from sequences within cells of a partition of
N, J. Combinatorial Theory, Ser A 17, 1–11 (1974).
36
[46] Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern
Number Theory, 2nd edition, Springer-Verlag, (1990).
[47] A. Kemnitz, On a lattice point problem, Ars Combin. 16b, 151–160
(1983).
[48] M. Lothaire, Combinatorics on Wards, Addison - Wesley, 1983.
[49] H. B. Mann, Addition Theorems in Group Theory and Number Theory,
R. E. Krieger Publishing Company, Huntington, New York, 1976.
[50] R. McCutcheon, Elemental methods in ergodic Ramsey theory, Springer,
Lect. Notes Math., Vol. 1722, 1999.
[51] R. Meshulam, An uncertainty inequality and zero subsums, Discrete
Math., 84, No. 2, 197–200 (1990).
[52] Melvyn B. Nathanson, Additive Number Theory: Inverse Problems and
the Geometry of Sumsets, Springer, 1996.
[53] J. Ne˘set˘ril and V. R¨odl (Eds.), Mathematics of Ramsey Theory,
Springer-Verlag, 1990.
[54] J. E. Olson, A combinatorial problem in finite abelian groups, I, J. Number Theory, 1, 8-10 (1969).
[55] J. E. Olson, A combinatorial problem in finite abelian groups, II, J.
Number Theory, 1, 195-199 (1969).
[56] R. Rado, Verallgemeinerung eines Satzes von van der Waerden mit Anwendungen auf ein problem der Zalentheorie, Sonderausgabe aus den
Sitzungsbericten der Preuss, Akad. der Wiss. Phys. -Math. klasse 17,
1–10 (1933).
[57] R. Rado, Studien zur Kombinatorik, Math. Z. 36, 424 –480, 1933.
[58] R. Rado, Some recent results in combinatorial analysis, Congr`es International des Mathematiciens, Oslo, 1936.
[59] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc.
(2) 30, 264–285 (1930).
37
[60] C. Reiher, On Kemnitz’s conjecture concerning lattice points in the
plane, Ramanujan J. 13, 333–337 (2007).
[61] K. Rogers, A Combinatorial problem in Abelian groups, Proc. Cambridge
Phil. Soc., 59, 559-562 (1963).
[62] L. R´onyai, On a conjecture of Kemnitz, Combinatorica, 20 (4), 569–573
(2000).
[63] K. F. Roth, On certain sets of integers, J. London Math. Soc. 28, 104–
109 (1953).
[64] J. H. Sanders, A generalization of Schur’s theorem, Ph.D. Dissertation,
Yale University, 1968.
[65] S. Savchev and Fang Chen, Kemnitz conjecture revisited, Discrete Math.
297, 196–201 (2005).
[66] P. Scherk, Solution to Problem 4466, Amer. Math. Monthly, 62, 46–47
(1955).
¨
[67] I. Schur, Uber
die Kongruenz xm + y m ≡ z m (mod p), Jber. Deutsch.
Math. Verein. 25, 114–117 (1916).
[68] A. Soifer, Ramsey Theory before Ramsey, Prehistory and Early History:
An essay in 13 parts, in: A. Soifer (Eds.), Ramsey Theory : Yesterday,
Today, and Tomorrow, Progress in Mathematics, Vol. 285, Birkh¨auser,
2011.
[69] E. Szemer´edi, On sets of integers containing no four elements in arithmetic progression, Acta. Math. Acad. Sci. Hungar. bf 20, 89–104 (1969).
[70] E. Szemer´edi, On sets of integers containing no k elements in arithmetic
progression, Acta. Arith. bf 27, 199–245 (1975).
[71] E. Szemer´edi, Integer sets containing no arithmetic progressions, Acta.
Math. Hungar.,56, 155–158 (1990).
[72] B. L. van der Waerden, Beweis einer Baudetschen Vermutang, Nieuw
Arch. Wisk. 15, 212–216 (1927).
[73] Hong Bing Yu, A simple proof of a theorem of Bollob´as and Leader,
Proc. American Math. Soc. 131, no. 9, 2639–2640 (2003).
38

Download Report