The Erdo˝s-Ginzburg-Ziv constant and 7 1 progression-free subsets 0 2 n Ga´bor Hegedu˝s a J O´buda University 6 Kiscelli utca 82, Budapest, Hungary, H-1032 ] O [email protected] C . January 9, 2017 h t a m [ Abstract 2 EllenbergandGijswijtgaverecentlyanewexponentialupperbound v 8 for the size of three-term arithmetic progression free sets in (Zp)n, 3 where p is a prime. Petrov summarized their method and generalized 0 their result to linear forms. 1 0 In this short note we use Petrov’s result to give new exponential . 1 upper bounds for the Erd˝os-Ginzburg-Ziv constant of finite Abelian 0 groups of high rank. Our main results depend on a conjecture about 7 Property D. 1 : v i X r 1 Introduction a Let A denote an additive finite Abelian group. We denote by s(A) the smallest integer ℓ ∈ N such that every sequence S over G of length |S| ≥ ℓ has a zero–sum subsequence of length |T| = exp(A). Here s(A) is the Erd˝os-Ginzburg-Ziv constant of A. 0 Keywords. Erd˝os-Ginzburg-Ziv constant, zero-sum sequence, finite abelian groups 2010 Mathematics Subject Classification: 11B50, 11B75, 20K01 1 Erd˝os, Ginzburg and Ziv determined precisely s(A) in the special case A = Z , where m > 1 is an arbitrary integer (see [10]). m Let g(A) denote the smallest integer ℓ ∈ N such that every square-free sequence S over G of length |S| ≥ ℓ has a zero–sum subsequence of length |T| = exp(A). The precise value of s(A) is known only for groups with rank at most two. We have Theorem 1.1 If A = Z ⊕Z , where 1 ≤ n |n , then s(A) = 2n +2n −3. n1 n2 1 2 1 2 Let A := (Z )n with k,n ∈ N and k ≥ 2. The inverse problem associated k with s(A) asks for the structure of sequences of length s(A)−1 that do not have a zero-sum subsequence of length k. The standing conjecture that every group A := (Z )n satisfies the following Property D (see [13], Conj. 7.2). k Property D: Every sequence S over A of length |S| = s(A) − 1 that has no zero-sum subsequence of length k has the form S = Tk−1 for some sequence T over A. We collected the most important cases, when Property D is satisfied. Theorem 1.2 The following Abelian groups has Property D: (i) A = (Z )n, where k = 2, n ≥ 1 is arbitrary; k (ii) A = (Z )n, where k = 3, n ≥ 1 is arbitrary; k (iii) A = (Z )n, where n = 1, k ≥ 2 is arbitrary. k Harborth proved the following inequality in [15]. Theorem 1.3 Let k ≥ 2, n ≥ 1 be arbitrary integers. Let A := (Z )n. Then k (k −1)2n +1 ≤ s(A) ≤ (k −1)kn +1. Harborth determined the Erd˝os-Ginzburg-Ziv constant s(A) in the fol- lowing special case in [15]. Theorem 1.4 Let a ≥ 1, n ≥ 1 be arbitrary integers. Let k := 2a. Let A := (Z )n. Then k s(A) = (k −1)2n +1. Alon and Dubiner proved the following upper bound for s(A) in [1]. 2 Theorem 1.5 Let k ≥ 2, n ≥ 1 be arbitrary integers. Let A := (Z )n. k There exists an absolute constant c > 0 such that for all k s(A) ≤ (cnlog n)nk. 2 Our main result is the following upper bound for s(A), where A := (Z )n p and p > 2 is a prime. Theorem 1.6 Let p > 2 be a prime. Suppose that the group A := (Z )n p satisfies Property D. Then (1− (p−2)2 )n+1 s(A) ≤ (p−1)p 2p2ln(p) +1. We give the proof of Theorem 1.6 in Section 3. Meshulam proved the following result in [17] Corollary 1.3. Theorem 1.7 Let n ≥ 1 be an arbitrary integer. Let A = (Z )n. Then 3 3n s(A) = O( ). n Harborth expressed s(A) in the following special case in [15], Hilfsatz 3. Theorem 1.8 Let n ≥ 1 be an arbitrary integer. Let A = Z n. Then 3 s(A) = 2g(A)−1. We can confirm Alon and Dubiner’s conjecture (see [2]) using Ellenberg– Gijswijt’s result about three term arithmetic progression. Corollary 1.9 Let n ≥ 1 be an arbitrary integer. Let A = (Z )n. Then 3 s(A) ≤ 2·(2.765)n. Proof. Let B ⊆ A be a set of vectors without three term arithmetic pro- gression. It is easy to verify that |B| ≤ g(A)−1. The result follows from Theorem 1.8 and Theorem 2.5 . First we generalize Theorem 1.6 to prime powers. 3 Theorem 1.10 Let p > 2 be a prime and r ≥ 1 be an integer. Suppose that the group A := (Z )n satisfies Property D. Then there exists a constant p 1 < c(pr) < pr depending on pr such that s((Z )n) ≤ c(pr)n. pr Specially pr −1 s((Z )n) ≤ d(p)n , (1) pr p−1 for each r ≥ 1, where d(p) depends only on p. The proof of Theorem 1.10 appears in Section 3. The following result was proved in [8] as Theorem 1.4. Theorem 1.11 LetA := Z ... Z , wherer := r(G)and 1 < n |...|n . Let c ,...,c ∈ N be integerns1Lsuch tLhat fnorr all primes p ∈ P with p|n1 and r 1 r r all 1 ≤ i ≤ r we have s(Z i) ≤ c (p−1)+1. p i Then r s(A) ≤ (c −c )n −c +1, X r+1−i r−i i r i=1 where c = 0. In particular, if n = ... = n = n, then s(A) ≤ c (n−1)+1. 0 1 r r We use later the following easy Corollary. Corollary 1.12 Let P denote a non-empty, finite set of odd primes and let k ∈ N be a product of prime powers with primes from P. Let m be a power of 2. Suppose that for each p ∈ P there exists a 1 < c(p) < p depending only on p such that s((Z )n) ≤ c(p)n(p−1)+1 p for each n ≥ 1. Then there exists a 1 < c(k) < k depending only of k such that s((Z )n) ≤ 2n(m−1)k +c(k)n(k −1)+1. mk For the reader’s convenience we give the proof of Corollary1.12 in Section 3. But this proof is very similar to the proof of [8] Corollary 4.5(3). Finally we generalize Theorem 1.6 to arbitrary integer modulus. 4 Theorem 1.13 Let P denote a non-empty, finite set of odd primes and let k ∈ N be a product of prime powers with primes from P. Let m be a power of 2. Suppose that the groups A := (Z )n satisfy p p Property D for each p ∈ P. Then there exists a 1 < c(k) < k depending only of k such that s((Z )n) ≤ 2n(m−1)k +c(k)n(k −1)+1. mk Proof of Theorem 1.13: Theorem 1.13 follows from Theorem 1.6 and Corollary 1.12. 2 Preliminaries 2.1 Combinatorial number theory Let G denote a finite Abelian group. If |G| > 1, then it is well–known that there exist uniquely determined integers 1 < n |n |...|n such that 1 2 r G ∼= Z ⊕...⊕Z . n1 nr and exp(G) = n is called the exponent of G and r(G) = r the rank of G. r Recall that G isa p-group if exp(G) = pk fora p primenumber andk ∈ N, and G is an elementary p-group if exp(G) = p. We denote by F(G) the free abelian monoid with basis G. An element S ∈ F(G) is called a sequence over G and we can write as: l S = gνg(S) = g , Y Y i g∈G i=1 where ν (S) ∈ N, and l ∈ N and g ∈ G. g i Here |S| = l ∈ N is the length, σ(S) = l g ∈ G is the sum and Pi=1 i supp(S) = {g ∈ G : ν (S) > 0} is the support of S. Moreover, ν (S) is g g called the multiplicity of g in S. Recall that a sequence is called a zero-sum sequence if σ(S) = 0, it is called squarefree if ν (S) ≤ 1 for each g ∈ G. As usual, a sequence T is g called a subsequence of S if T divides S in F(G). We use later the following result (see [5] Proposition 3.1). 5 Theorem 2.1 Let G be a finite Abelian group and let H ≤ G be a subgroup such that exp(G) = exp(H)exp(G/H). Then s(G) ≤ exp(G/H)(s(H)−1)+s(G/H) 2.2 Upper bounds for the space of monomials Let n,m ≥ 1, D ≥ 2 be fixed integers. Let L := span({xα = xα1 ...xαn : α ≤ D −1 for each 1 ≤ i ≤ n}). n,D 1 n i Let L := span({xα ∈ L : deg(xα) ≤ k}). n,D,k n,D Theorem 2.2 Let (m−2)2 c := 1− . 2m2ln(D) Then dim(L ) ≤ Dcn. n,D,n(D−1) m The proof of Theorem 2.2 is based on Hoeffding inequality and a very slight generalization of the proof of [14] Lemma 1. 2.3 Progression-free sets and Petrov’s result Ellenberg and Gijswijt achieved the following breakthrough very recently in [9] on the upper bounds of progression free subsets in (Z )n, where p is a p prime. Theorem 2.3 Let p be a fixed prime. Let (a ,a ,a ) ∈ (Z )3 be a fixed 1 2 3 p vector. Suppose that p divides a and a 6≡ 0 (mod p).. Let F ⊆ (Z )n be an arbitraPryi suibset sa3tisfying the following property: if p b ,b ,b ∈ F are arbitrary vectors such that there exist 1 ≤ i < j ≤ 3 with 1 2 3 b 6= b , then i j a b +a b +a b 6= 0. 1 1 2 2 3 3 Then |F| ≤ 3·dim(L ). n,p,n(p−1) 3 6 Later Petrov proved the following generalization of the Theorem 2.3 in [19]. Theorem 2.4 Let p be a prime, m ≥ 1 be an integer. Let (a ,...,a ) ∈ 1 m (Z )m be a fixed vector. Suppose that p divides a and a 6≡ 0 (mod p). pLet F ⊆ (Z )n be an arbitrary subset satisfyPingi tihe follomwing property: if p b ,...,b ∈ F are arbitrary vectors such that there exist 1 ≤ i < j ≤ m 1 m with b 6= b , then i j m a b 6= 0. X i i i=1 Then |F| ≤ m·dim(L ). n,p,n(p−1) m The following Corollary is a direct consequence of Theorem 2.2. Corollary 2.5 Let p be a prime, m ≥ 1 be an integer. Let (a ,...,a ) ∈ 1 m (Z )m be a fixed vector. Suppose that p divides a . pLet F ⊆ (Z )n be an arbitrary subset satisfyPingi thie following property: if p b ,...,b ∈ F are arbitrary vectors such that there exist 1 ≤ i < j ≤ m 1 m with b 6= b , then i j m a b 6= 0. X i i i=1 Then (1− (m−2)2 )n |F| ≤ mp 2m2ln(p) . Proof. This follows from Theorem 2.4 and Theorem 2.2. Finally we use in the proof of our main results the following clear consequence. Corollary 2.6 Let p be a prime, r ≥ 2 be an integer. Suppose that p divides r. Let F ⊆ (Z )n be an arbitrary subset satisfying the following property: if p b ,...,b ∈ F are arbitrary vectors such that there exist 1 ≤ i < j ≤ r with 1 r b 6= b , then i j b +...+b 6= 0. 1 r Then (1− (r−2)2 )n |F| ≤ rp 2r2ln(p) . 7 Proof. Let m := r and a = 1 for each 1 ≤ i ≤ r. Then we can apply i Corollary 2.5. 3 Proofs Proof of Theorem 1.6: Let S be a sequence of length s(A) − 1 that does not have a zero-sum subsequence of length p. Then it follows from Property D that S has the form S = Tp−1 for some sequence T over A. Clearly T does not have a zero- sum subsequence of length p. Hence T is a square-free sequence, and there exists a subset F ⊆ Z n such that F = supp(T). Hence if (a ,...,a ) ∈ Fp p 1 r is an arbitrary vector such that there exist 1 ≤ i < j ≤ m with a 6= a , then i j a +...+a 6= 0. 1 p Here we used that S = Tp−1 is a sequence of length s(A) −1 that does not have a zero-sum subsequence of length p. We can apply Corollary 2.6 with the choice r := p and we get (1− (p−2)2 )n |F| ≤ p·p 2p2ln(p) . Since S = Tp−1, F = supp(T) and S is a sequence of length s(A)−1, hence we get our result. Proof of Theorem 1.10: We can prove by induction on the exponent r. If r = 1, then Theorem 1.6 gives the result. Suppose that our inequality (1) is true for a fixed r. We will prove that (1) is true for r+1. Namely it follows from Theorem 1.6 and the inductional hypothesis that s((Z )n) ≤ p·s((Z )n)+s((Z )n) ≤ pr+1 pr p pr −1 pr −1 ≤ d(p)n +d(p)n = d(p)n +1 = (cid:16) (cid:17) p−1 p−1 8 pr+1 −1 d(p)n . p−1 Proof of Corollary 1.12: Let A := (Z )n and H := kA ≡ (Z )n. Then clearly A/H ≡ (Z )n. mk m k Define c(k) := max{c(p) : p ∈ P}. Clearly 1 < c(k) < k, since 1 < c(p) < p for each p ∈ P. But then s(Z ) ≤ ... ≤ s((Z n)) ≤ c(p)n(p−1)+1 ≤ c(k)n(p−1)+1 p p for each p ∈ P. It follows from Theorem 1.11 that s(A/H) = s((Z )n) ≤ c(k)n(k −1)+1. k On the other hand it follows from Theorem 1.4 that s(H) = s((Z )n) ≤ 2n(m−1)+1. m Finally Theorem 2.1 gives that s(A) ≤ exp(A/H)(s(H)−1)+s(A/H) ≤ 2n(m−1)k +c(k)n(k −1)+1. Acknowledgements. I am indebted to Lajos Ro´nyai for his useful re- marks. References [1] N. Alon, and M. Dubiner. Zero-sum sets of prescribed size. Combina- torics, Paul Erdos is Eighty 1 33-50 (1993) [2] N.AlonandM.Dubiner.Alatticepointproblemandadditivenumber theory. Combinatorica, 15(3), 301-309. (1995). 9 [3] L. Babai and P. Frankl, Linear algebra methods in combinatorics, manuscript, September 1992. [4] J. Blasiak, T. Church, H. Cohn, J. A. Grochow and C. Umans. On cap sets and the group-theoretic approach to matrix multiplication. arXiv preprint (2016). arXiv:1605.06702. [5] Chi, R., Ding, S., W.Gao, A.Geroldinger andA. W.Schmid, Onzero- sum subsequences of restricted size. IV. Acta Mathematica Hungarica, 107(4), .337-344. (2005) [6] E. Croot, V. Lev, and P. Pach. Progression-free sets in Zn are expo- 4 nentially small. arXiv preprint arXiv:1605.01506 (2016). [7] M. Deza, P. Frankl and N. M. Singhi. On functions of strengtht. Com- binatorica 3.3-4 (1983): 331-339. [8] Y. Edel, C. Elsholtz, A. Geroldinger, S. Kubertin and L. Rackham, Zero-sum problems in finite abelian groups and affine caps. The Quar- terly J. of Math. 58(2), 159-186 (2007). [9] J. S. Ellenberg and D. Gijswijt. ”On large subsets of Fn q with no three-term arithmetic progression. 2016.” arXiv preprint arXiv:1605.09223. [10] P. Erd˝os, A. Ginzburg and A. Ziv, Theorem in the additive number theory. Bull. Res. Council Israel, 10, 41-43 (1961). [11] Y. Fan, W. Gao and Q. Zhong, . On the ErdsGinzburgZiv constant of finite abelian groups of high rank. Journal of Number Theory, 131(10), 1864-1874 (2011). [12] P. Frankl, P. and R. M. Wilson (1981). Intersection theorems with geometric consequences. Combinatorica, 1(4), 357-368. [13] W. Gao and A. Geroldinger, Zero-sum problems in finite abelian groups: a survey. Expositiones Mathematicae, 24(4), 337-369 (2006).. [14] D. Gijswijt. Asymptotic upper bounds on progression-free sets in Fp n , 2016. URL:http://homepage.tudelft.nl/64a8q/progressions.pdf. 10