Unification of zerosum problems, subset sums and covers of
Author:
ZhiWei Sun
Journal:
Electron. Res. Announc. Amer. Math. Soc. 9 (2003), 5160
MSC (2000):
Primary 11B75; Secondary 05A05, 05C07, 11B25, 11C08, 11D68, 11P70, 11T99, 20D60
Published electronically:
July 10, 2003
MathSciNet review:
1988872
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In combinatorial number theory, zerosum 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ösGinzburgZiv 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
(95k:11114), http://dx.doi.org/10.2307/2118576
 [A99]
Noga
Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput.
8 (1999), no. 12, 7–29. Recent trends in
combinatorics (Mátraháza, 1995). MR 1684621
(2000b:05001), http://dx.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. 119136.
 [AD]
N.
Alon and M.
Dubiner, Zerosum 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
(94j:11016)
 [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
(86d:05064a), http://dx.doi.org/10.1016/00958956(84)900479
 [AFK2]
N.
Alon, S.
Friedland, and G.
Kalai, Every 4regular graph plus an edge contains a 3regular
subgraph, J. Combin. Theory Ser. B 37 (1984),
no. 1, 92–93. MR 762898
(86d:05064b), http://dx.doi.org/10.1016/00958956(84)900480
 [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
(94a:52039), http://dx.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 (95k:11009), http://dx.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
(96k:11011), http://dx.doi.org/10.1006/jnth.1996.0029
 [AT]
N.
Alon and M.
Tarsi, A nowherezero point in linear mappings, Combinatorica
9 (1989), no. 4, 393–395. MR 1054015
(92a:11147), http://dx.doi.org/10.1007/BF02125351
 [C]
Yair
Caro, Zerosum problems—a survey, Discrete Math.
152 (1996), no. 13, 93–113. MR 1388634
(97c:05156), http://dx.doi.org/10.1016/0012365X(94)003086
 [Cr]
Roger
Crocker, On the sum of a prime and of two powers of two,
Pacific J. Math. 36 (1971), 103–107. MR 0277467
(43 #3200)
 [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
(2002j:05027), http://dx.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
(95i:11007), http://dx.doi.org/10.1112/blms/26.2.140
 [E]
P.
Erdös, On integers of the form 2^{𝑘}+𝑝 and
some related problems, Summa Brasil. Math. 2 (1950),
113–123. MR 0044558
(13,437i)
 [EGZ]
P. Erdös, A. Ginzburg and A. Ziv, Theorem in the additive number theory, Bull. Research Council Israel 10 (1961), 4143.
 [EH]
P.
Erdős and H.
Heilbronn, On the addition of residue classes
𝑚𝑜𝑑𝑝, Acta Arith. 9
(1964), 149–159. MR 0166186
(29 #3463)
 [G]
W.
D. Gao, Two addition theorems on groups of prime order, J.
Number Theory 56 (1996), no. 2, 211–213. MR 1373547
(96m:11008), http://dx.doi.org/10.1006/jnth.1996.0013
 [HS]
QingHu
Hou and ZhiWei
Sun, Restricted sums in a field, Acta Arith.
102 (2002), no. 3, 239–249. MR 1884717
(2003e:11025), http://dx.doi.org/10.4064/aa10233
 [K]
Arnfried
Kemnitz, On a lattice point problem, Ars Combin.
16 (1983), no. B, 151–160. MR 737118
(85c:52022)
 [LS]
J. X. Liu and Z. W. Sun, Sums of subsets with polynomial restrictions, J. Number Theory 97 (2002), 301304.
 [N]
Melvyn
B. Nathanson, Additive number theory, Graduate Texts in
Mathematics, vol. 165, SpringerVerlag, New York, 1996. Inverse
problems and the geometry of sumsets. MR 1477155
(98f:11011)
 [O]
John
E. Olson, A combinatorial problem on finite Abelian groups. I,
J. Number Theory 1 (1969), 8–10. MR 0237641
(38 #5922)
 [PS]
H. Pan and Z. W. Sun, A lower bound for , J. Combin. Theory Ser. A 100 (2002), 387393.
 [P]
Štefan
Porubský, On 𝑚 times covering systems of
congruences, Acta Arith. 29 (1976), no. 2,
159–169. MR 0399033
(53 #2884)
 [PS]
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. 581627.
 [R]
Lajos
Rónyai, On a conjecture of Kemnitz, Combinatorica
20 (2000), no. 4, 569–573. MR 1804827
(2001k:11025), http://dx.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
(96k:11013)
 [S96]
ZhiWei
Sun, Covering the integers by arithmetic
sequences. II, Trans. Amer. Math. Soc.
348 (1996), no. 11, 4279–4320. MR 1360231
(97c:11011), http://dx.doi.org/10.1090/S0002994796016741
 [S97]
ZhiWei
Sun, Exact 𝑚covers and the linear form
∑^{𝑘}_{𝑠=1}𝑥_{𝑠}/𝑛_{𝑠},
Acta Arith. 81 (1997), no. 2, 175–198. MR 1456240
(98h:11019)
 [S99]
ZhiWei
Sun, On covering multiplicity, Proc. Amer. Math. Soc. 127 (1999), no. 5, 1293–1300. MR 1486752
(99h:11012), http://dx.doi.org/10.1090/S0002993999048170
 [S00]
ZhiWei
Sun, On integers not of the form
±𝑝^{𝑎}±𝑞^{𝑏}, Proc. Amer. Math. Soc. 128 (2000), no. 4, 997–1002. MR 1695111
(2000i:11157), http://dx.doi.org/10.1090/S0002993999055021
 [S01]
ZhiWei
Sun, Algebraic approaches to periodic arithmetical maps, J.
Algebra 240 (2001), no. 2, 723–743. MR 1841354
(2002f:11009), http://dx.doi.org/10.1006/jabr.2000.8721
 [S03]
Z. W. Sun, A unified theory of zerosum 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
(92c:11003)
 [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
(92j:11001)
 [AGP]
 W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. Math. 139 (1994), 703722. MR 95k:11114
 [A99]
 N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), 729. MR 2000b:05001
 [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. 119136.
 [AD]
 N. Alon and M. Dubiner, Zerosum sets of prescribed size, in: Combinatorics, Paul Erdös is Eighty, János Bolyai Math. Soc., Budapest, 1993, pp. 3350. MR 94j:11016
 [AFK1]
 N. Alon, S. Friedland and G. Kalai, Regular subgraphs of almost regular graphs, J. Combin. Theory Ser. B 37 (1984), 7991. MR 86d:05064a
 [AFK2]
 N. Alon, S. Friedland and G. Kalai, Every regular graph plus an edge contains a regular subgraph, J. Combin. Theory Ser. B 37 (1984), 9293. MR 86d:05064b
 [AF]
 N. Alon and Z. Füredi, Covering the cube by affine hyperplanes, European J. Combin. 14 (1993), 7983. MR 94a:52039
 [ANR1]
 N. Alon, M. B. Nathanson and I. Z. Ruzsa, Adding distinct congruence classes modulo a prime, Amer. Math. Monthly 102 (1995), 250255. MR 95k:11009
 [ANR2]
 N. Alon, M. B. Nathanson and I. Z. Ruzsa, The polynomial method and restricted sums of congruence classes, J. Number Theory 56 (1996), 404417. MR 96k:11011
 [AT]
 N. Alon and M. Tarsi, A nowherezero point in linear mappings, Combinatorica 9 (1989), 393395. MR 92a:11147
 [C]
 Y. Caro, Zerosum problemsa survey, Discrete Math. 152 (1996), 93113. MR 97c:05156
 [Cr]
 R. Crocker, On a sum of a prime and two powers of two, Pacific J. Math. 36 (1971), 103107. MR 43:3200
 [DKSS]
 S. Dasgupta, G. Károlyi, O. Serra and B. Szegedy, Transversals of additive Latin squares, Israel J. Math. 126 (2001), 1728. MR 2002j:05027
 [DH]
 J. A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994), 140146. MR 95i:11007
 [E]
 P. Erdös, On integers of the form and some related problems, Summa Brasil. Math. 2 (1950), 113123. MR 13:437i
 [EGZ]
 P. Erdös, A. Ginzburg and A. Ziv, Theorem in the additive number theory, Bull. Research Council Israel 10 (1961), 4143.
 [EH]
 P. Erdös and H. Heilbronn, On the addition of residue classes mod p, Acta Arith. 9 (1964), 149159. MR 29:3463
 [G]
 W. D. Gao, Two addition theorems on groups of prime order, J. Number Theory 56 (1996), 211213. MR 96m:11008
 [HS]
 Q. H. Hou and Z. W. Sun, Restricted sums in a field, Acta Arith. 102 (2002), 239249. MR 2003e:11025
 [K]
 A. Kemnitz, On a lattice point problem, Ars Combin. 16 (1983), 151160. MR 85c:52022
 [LS]
 J. X. Liu and Z. W. Sun, Sums of subsets with polynomial restrictions, J. Number Theory 97 (2002), 301304.
 [N]
 M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Graduate texts in mathematics; 165), SpringerVerlag, New York, 1996. MR 98f:11011
 [O]
 J. E. Olson, A combinatorial problem on finite abelian groups (I), J. Number Theory 1 (1969), 810. MR 38:5922
 [PS]
 H. Pan and Z. W. Sun, A lower bound for , J. Combin. Theory Ser. A 100 (2002), 387393.
 [P]
 S. Porubský, On times covering systems of congruences, Acta Arith. 29 (1976), 159169. MR 53:2884
 [PS]
 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. 581627.
 [R]
 L. Rónyai, On a conjecture of Kemnitz, Combinatorica 20 (2000), 569573. MR 2001k:11025
 [S95]
 Z. W. Sun, Covering the integers by arithmetic sequences, Acta Arith. 72 (1995), 109129. MR 96k:11013
 [S96]
 Z. W. Sun, Covering the integers by arithmetic sequences II, Trans. Amer. Math. Soc. 348 (1996), 42794320. MR 97c:11011
 [S97]
 Z. W. Sun, Exact covers and the linear form , Acta Arith. 81 (1997), 175198. MR 98h:11019
 [S99]
 Z. W. Sun, On covering multiplicity, Proc. Amer. Math. Soc. 127 (1999), 12931300. MR 99h:11012
 [S00]
 Z. W. Sun, On integers not of the form , Proc. Amer. Math. Soc. 128 (2000), 9971002. MR 2000i:11157
 [S01]
 Z. W. Sun, Algebraic approaches to periodic arithmetical maps, J. Algebra 240 (2001), 723743. MR 2002f:11009
 [S03]
 Z. W. Sun, A unified theory of zerosum problems, subset sums and covers of , preprint, Nanjing University, March 1, 2003. arXiv:math.NT/0305369
 [Z89]
 M. Z. Zhang, A note on covering systems of residue classes, J. Sichuan Univ. (Nat. Sci. Ed.) 26 (1989), Special Issue, 185188. MR 92c:11003
 [Z91]
 M. Z. Zhang, On irreducible exactly times covering system of residue classes, J. Sichuan Univ. (Nat. Sci. Ed.) 28 (1991), 403408. MR 92j:11001
Similar Articles
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
ZhiWei Sun
Affiliation:
Department of Mathematics, Nanjing University, Nanjing 210093, People’s Republic of China
Email:
zwsun@nju.edu.cn
DOI:
http://dx.doi.org/10.1090/S1079676203001112
PII:
S 10796762(03)001112
Keywords:
Zerosum,
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
