Unification of zero-sum problems, subset sums and covers of

Author:
Zhi-Wei Sun

Journal:
Electron. Res. Announc. Amer. Math. Soc. **9** (2003), 51-60

MSC (2000):
Primary 11B75; Secondary 05A05, 05C07, 11B25, 11C08, 11D68, 11P70, 11T99, 20D60

DOI:
https://doi.org/10.1090/S1079-6762-03-00111-2

Published electronically:
July 10, 2003

MathSciNet review:
1988872

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In combinatorial number theory, zero-sum problems, subset sums and covers of the integers are three different topics initiated by P. Erdös and investigated by many researchers; they play important roles in both number theory and combinatorics. In this paper we announce some deep connections among these seemingly unrelated fascinating areas, and aim at establishing a unified theory! Our main theorem unifies many results in these three realms and also has applications in many aspects such as finite fields and graph theory. To illustrate this, here we state our extension of the Erdös-Ginzburg-Ziv theorem: If covers some integers exactly times and others exactly times, where is a prime, then for any there exists an such that and .

**[AGP]**W. R. Alford, Andrew Granville, and Carl Pomerance,*There are infinitely many Carmichael numbers*, Ann. of Math. (2)**139**(1994), no. 3, 703–722. MR**1283874**, https://doi.org/10.2307/2118576**[A99]**Noga Alon,*Combinatorial Nullstellensatz*, Combin. Probab. Comput.**8**(1999), no. 1-2, 7–29. Recent trends in combinatorics (Mátraháza, 1995). MR**1684621**, https://doi.org/10.1017/S0963548398003411**[A03]**N. Alon,*Discrete mathematics: methods and challenges*, in: Proceedings of the International Congress of Mathematicians (Beijing, 2002), Vol. I, Higher Education Press, Beijing, 2003, pp. 119-136.**[AD]**N. Alon and M. Dubiner,*Zero-sum sets of prescribed size*, Combinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993, pp. 33–50. MR**1249703****[AFK1]**N. Alon, S. Friedland, and G. Kalai,*Regular subgraphs of almost regular graphs*, J. Combin. Theory Ser. B**37**(1984), no. 1, 79–91. MR**762897**, https://doi.org/10.1016/0095-8956(84)90047-9

N. Alon, S. Friedland, and G. Kalai,*Every 4-regular graph plus an edge contains a 3-regular subgraph*, J. Combin. Theory Ser. B**37**(1984), no. 1, 92–93. MR**762898**, https://doi.org/10.1016/0095-8956(84)90048-0**[AFK2]**N. Alon, S. Friedland, and G. Kalai,*Regular subgraphs of almost regular graphs*, J. Combin. Theory Ser. B**37**(1984), no. 1, 79–91. MR**762897**, https://doi.org/10.1016/0095-8956(84)90047-9

N. Alon, S. Friedland, and G. Kalai,*Every 4-regular graph plus an edge contains a 3-regular subgraph*, J. Combin. Theory Ser. B**37**(1984), no. 1, 92–93. MR**762898**, https://doi.org/10.1016/0095-8956(84)90048-0**[AF]**Noga Alon and Zoltán Füredi,*Covering the cube by affine hyperplanes*, European J. Combin.**14**(1993), no. 2, 79–83. MR**1206612**, https://doi.org/10.1006/eujc.1993.1011**[ANR1]**Noga Alon, Melvyn B. Nathanson, and Imre Ruzsa,*Adding distinct congruence classes modulo a prime*, Amer. Math. Monthly**102**(1995), no. 3, 250–255. MR**1317846**, https://doi.org/10.2307/2975012**[ANR2]**Noga Alon, Melvyn B. Nathanson, and Imre Ruzsa,*The polynomial method and restricted sums of congruence classes*, J. Number Theory**56**(1996), no. 2, 404–417. MR**1373563**, https://doi.org/10.1006/jnth.1996.0029**[AT]**N. Alon and M. Tarsi,*A nowhere-zero point in linear mappings*, Combinatorica**9**(1989), no. 4, 393–395. MR**1054015**, https://doi.org/10.1007/BF02125351**[C]**Yair Caro,*Zero-sum problems—a survey*, Discrete Math.**152**(1996), no. 1-3, 93–113. MR**1388634**, https://doi.org/10.1016/0012-365X(94)00308-6**[Cr]**Roger Crocker,*On the sum of a prime and of two powers of two*, Pacific J. Math.**36**(1971), 103–107. MR**0277467****[DKSS]**Samit Dasgupta, Gyula Károlyi, Oriol Serra, and Balázs Szegedy,*Transversals of additive Latin squares*, Israel J. Math.**126**(2001), 17–28. MR**1882032**, https://doi.org/10.1007/BF02784149**[DH]**J. A. Dias da Silva and Y. O. Hamidoune,*Cyclic spaces for Grassmann derivatives and additive theory*, Bull. London Math. Soc.**26**(1994), no. 2, 140–146. MR**1272299**, https://doi.org/10.1112/blms/26.2.140**[E]**P. Erdös,*On integers of the form**and some related problems*, Summa Brasil. Math.**2**(1950), 113-123. MR**13:437i****[EGZ]**P. Erdös, A. Ginzburg and A. Ziv,*Theorem in the additive number theory*, Bull. Research Council Israel**10**(1961), 41-43.**[EH]**P. Erdős and H. Heilbronn,*On the addition of residue classes 𝑚𝑜𝑑𝑝*, Acta Arith.**9**(1964), 149–159. MR**0166186****[G]**W. D. Gao,*Two addition theorems on groups of prime order*, J. Number Theory**56**(1996), no. 2, 211–213. MR**1373547**, https://doi.org/10.1006/jnth.1996.0013**[HS]**Qing-Hu Hou and Zhi-Wei Sun,*Restricted sums in a field*, Acta Arith.**102**(2002), no. 3, 239–249. MR**1884717**, https://doi.org/10.4064/aa102-3-3**[K]**Arnfried Kemnitz,*On a lattice point problem*, Ars Combin.**16**(1983), no. B, 151–160. MR**737118****[LS]**J. X. Liu and Z. W. Sun,*Sums of subsets with polynomial restrictions*, J. Number Theory**97**(2002), 301-304.**[N]**Melvyn B. Nathanson,*Additive number theory*, Graduate Texts in Mathematics, vol. 165, Springer-Verlag, New York, 1996. Inverse problems and the geometry of sumsets. MR**1477155****[O]**John E. Olson,*A combinatorial problem on finite Abelian groups. I*, J. Number Theory**1**(1969), 8–10. MR**0237641**, https://doi.org/10.1016/0022-314X(69)90021-3**[PS]**H. Pan and Z. W. Sun,*A lower bound for*, J. Combin. Theory Ser. A**100**(2002), 387-393.**[P]**Štefan Porubský,*On 𝑚 times covering systems of congruences*, Acta Arith.**29**(1976), no. 2, 159–169. MR**0399033****[P-S]**S. Porubský and J. Schönheim,*Covering systems of Paul Erdös: past, present and future*, in: Paul Erdös and his Mathematics. I (edited by G. Halász, L. Lovász, M. Simonvits, V. T. Sós), Bolyai Soc. Math. Studies 11, Budapest, 2002, pp. 581-627.**[R]**Lajos Rónyai,*On a conjecture of Kemnitz*, Combinatorica**20**(2000), no. 4, 569–573. MR**1804827**, https://doi.org/10.1007/s004930070008**[S95]**Zhi Wei Sun,*Covering the integers by arithmetic sequences*, Acta Arith.**72**(1995), no. 2, 109–129. MR**1347259****[S96]**Zhi-Wei Sun,*Covering the integers by arithmetic sequences. II*, Trans. Amer. Math. Soc.**348**(1996), no. 11, 4279–4320. MR**1360231**, https://doi.org/10.1090/S0002-9947-96-01674-1**[S97]**Zhi-Wei Sun,*Exact 𝑚-covers and the linear form ∑^{𝑘}_{𝑠=1}𝑥_{𝑠}/𝑛_{𝑠}*, Acta Arith.**81**(1997), no. 2, 175–198. MR**1456240****[S99]**Zhi-Wei Sun,*On covering multiplicity*, Proc. Amer. Math. Soc.**127**(1999), no. 5, 1293–1300. MR**1486752**, https://doi.org/10.1090/S0002-9939-99-04817-0**[S00]**Zhi-Wei Sun,*On integers not of the form ±𝑝^{𝑎}±𝑞^{𝑏}*, Proc. Amer. Math. Soc.**128**(2000), no. 4, 997–1002. MR**1695111**, https://doi.org/10.1090/S0002-9939-99-05502-1**[S01]**Zhi-Wei Sun,*Algebraic approaches to periodic arithmetical maps*, J. Algebra**240**(2001), no. 2, 723–743. MR**1841354**, https://doi.org/10.1006/jabr.2000.8721**[S03]**Z. W. Sun,*A unified theory of zero-sum problems, subset sums and covers of*, preprint, Nanjing University, March 1, 2003. arXiv:math.NT/0305369**[Z89]**Ming Zhi Zhang,*A note on covering systems of residue classes*, Sichuan Daxue Xuebao**26**(1989), no. Special Issue, 185–188 (Chinese, with English summary). MR**1059702****[Z91]**Ming Zhi Zhang,*Irreducible systems of residue classes that cover every integer exactly 𝑚 times*, Sichuan Daxue Xuebao**28**(1991), no. 4, 403–408 (Chinese, with English summary). MR**1148826**

Retrieve articles in *Electronic Research Announcements of the American Mathematical Society*
with MSC (2000):
11B75,
05A05,
05C07,
11B25,
11C08,
11D68,
11P70,
11T99,
20D60

Retrieve articles in all journals with MSC (2000): 11B75, 05A05, 05C07, 11B25, 11C08, 11D68, 11P70, 11T99, 20D60

Additional Information

**Zhi-Wei Sun**

Affiliation:
Department of Mathematics, Nanjing University, Nanjing 210093, People’s Republic of China

Email:
zwsun@nju.edu.cn

DOI:
https://doi.org/10.1090/S1079-6762-03-00111-2

Keywords:
Zero-sum,
subset sums,
covers of $\mathbb{Z}$

Received by editor(s):
March 20, 2003

Published electronically:
July 10, 2003

Additional Notes:
The website http://pweb.nju.edu.cn/zwsun/csz.htm is devoted to the topics covered by this paper.

Supported by the Teaching and Research Award Fund for Outstanding Young Teachers in Higher Education Institutions of MOE, and the National Natural Science Foundation of P. R. China.

Dedicated:
In memory of Paul Erdös

Communicated by:
Ronald L. Graham

Article copyright:
© Copyright 2003
American Mathematical Society