|
Unification of zero-sum problems, subset sums and covers of
Author(s):
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
Posted:
July 10, 2003
Retrieve article in:
PDF DVI PostScript
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
.
References:
-
- [AGP]
- W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. Math. 139 (1994), 703-722. MR 95k:11114
- [A99]
- N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8 (1999), 7-29. 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. 119-136.
- [AD]
- N. Alon and M. Dubiner, Zero-sum sets of prescribed size, in: Combinatorics, Paul Erdös is Eighty, János Bolyai Math. Soc., Budapest, 1993, pp. 33-50. MR 94j:11016
- [AFK1]
- N. Alon, S. Friedland and G. Kalai, Regular subgraphs of almost regular graphs, J. Combin. Theory Ser. B 37 (1984), 79-91. 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), 92-93. MR 86d:05064b - [AF]
- N. Alon and Z. Füredi, Covering the cube by affine hyperplanes, European J. Combin. 14 (1993), 79-83. 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), 250-255. 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), 404-417. MR 96k:11011
- [AT]
- N. Alon and M. Tarsi, A nowhere-zero point in linear mappings, Combinatorica 9 (1989), 393-395. MR 92a:11147
- [C]
- Y. Caro, Zero-sum problems--a survey, Discrete Math. 152 (1996), 93-113. MR 97c:05156
- [Cr]
- R. Crocker, On a sum of a prime and two powers of two, Pacific J. Math. 36 (1971), 103-107. MR 43:3200
- [DKSS]
- S. Dasgupta, G. Károlyi, O. Serra and B. Szegedy, Transversals of additive Latin squares, Israel J. Math. 126 (2001), 17-28. 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), 140-146. MR 95i:11007
- [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 mod p, Acta Arith. 9 (1964), 149-159. MR 29:3463
- [G]
- W. D. Gao, Two addition theorems on groups of prime order, J. Number Theory 56 (1996), 211-213. MR 96m:11008
- [HS]
- Q. H. Hou and Z. W. Sun, Restricted sums in a field, Acta Arith. 102 (2002), 239-249. MR 2003e:11025
- [K]
- A. Kemnitz, On a lattice point problem, Ars Combin. 16 (1983), 151-160. MR 85c:52022
- [LS]
- J. X. Liu and Z. W. Sun, Sums of subsets with polynomial restrictions, J. Number Theory 97 (2002), 301-304.
- [N]
- M. B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Graduate texts in mathematics; 165), Springer-Verlag, New York, 1996. MR 98f:11011
- [O]
- J. E. Olson, A combinatorial problem on finite abelian groups (I), J. Number Theory 1 (1969), 8-10. MR 38:5922
- [PS]
- H. Pan and Z. W. Sun, A lower bound for
, J. Combin. Theory Ser. A 100 (2002), 387-393. - [P]
- S. Porubský, On
times covering systems of congruences, Acta Arith. 29 (1976), 159-169. MR 53:2884 - [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]
- L. Rónyai, On a conjecture of Kemnitz, Combinatorica 20 (2000), 569-573. MR 2001k:11025
- [S95]
- Z. W. Sun, Covering the integers by arithmetic sequences, Acta Arith. 72 (1995), 109-129. MR 96k:11013
- [S96]
- Z. W. Sun, Covering the integers by arithmetic sequences II, Trans. Amer. Math. Soc. 348 (1996), 4279-4320. MR 97c:11011
- [S97]
- Z. W. Sun, Exact
-covers and the linear form , Acta Arith. 81 (1997), 175-198. MR 98h:11019 - [S99]
- Z. W. Sun, On covering multiplicity, Proc. Amer. Math. Soc. 127 (1999), 1293-1300. MR 99h:11012
- [S00]
- Z. W. Sun, On integers not of the form
, Proc. Amer. Math. Soc. 128 (2000), 997-1002. MR 2000i:11157 - [S01]
- Z. W. Sun, Algebraic approaches to periodic arithmetical maps, J. Algebra 240 (2001), 723-743. MR 2002f:11009
- [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]
- M. Z. Zhang, A note on covering systems of residue classes, J. Sichuan Univ. (Nat. Sci. Ed.) 26 (1989), Special Issue, 185-188. MR 92c:11003
- [Z91]
- M. Z. Zhang, On irreducible exactly
times covering system of residue classes, J. Sichuan Univ. (Nat. Sci. Ed.) 28 (1991), 403-408. MR 92j:11001
Similar Articles:
Retrieve articles in Electronic Research Announcements
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:
10.1090/S1079-6762-03-00111-2
PII:
S 1079-6762(03)00111-2
Keywords:
Zero-sum,
subset sums,
covers of $\mathbb{Z}$
Received by editor(s):
March 20, 2003
Posted:
July 10, 2003
Additional Notes:
The website {\tt 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
Copyright of article:
Copyright
2003,
American Mathematical Society
|