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
© Copyright 2025 ExpyDoc