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

Sun, Zhi-Wei¹

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

Electronic research announcements of the American Mathematical Society, Tome 09 (2003), pp. 51-60.

Résumé

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 $A=\{a_{s}(\mathrm {mod}\ n_{s})\}_{s=1}^{k}$ covers some integers exactly $2p-1$ times and others exactly $2p$ times, where $p$ is a prime, then for any $c_{1},\cdots ,c_{k}\in \mathbb {Z}/p\mathbb {Z}$ there exists an $I\subseteq \{1,\cdots ,k\}$ such that $\sum _{s\in I}1/n_{s}=p$ and $\sum _{s\in I}c_{s}=0$.

Détail

DOI : 10.1090/S1079-6762-03-00111-2

Bibliographie

[1] Alford, W. R., Granville, Andrew, Pomerance, Carl There are infinitely many Carmichael numbers Ann. of Math. (2) 1994 703 722

[2] Alon, Noga Combinatorial Nullstellensatz Combin. Probab. Comput. 1999 7 29

[3] Alon, N., Dubiner, M. Zero-sum sets of prescribed size 1993 33 50

[4] Alon, N., Friedland, S., Kalai, G. Regular subgraphs of almost regular graphs J. Combin. Theory Ser. B 1984 79 91

[5] Germay, R. H. J. Généralisation de l’équation de Hesse Ann. Soc. Sci. Bruxelles Sér. I 1939 139 144

[6] Alon, Noga, Füredi, Zoltán Covering the cube by affine hyperplanes European J. Combin. 1993 79 83

[7] Alon, Noga, Nathanson, Melvyn B., Ruzsa, Imre Adding distinct congruence classes modulo a prime Amer. Math. Monthly 1995 250 255

[8] Alon, Noga, Nathanson, Melvyn B., Ruzsa, Imre The polynomial method and restricted sums of congruence classes J. Number Theory 1996 404 417

[9] Alon, N., Tarsi, M. A nowhere-zero point in linear mappings Combinatorica 1989 393 395

[10] Caro, Yair Zero-sum problems—a survey Discrete Math. 1996 93 113

[11] Crocker, Roger On the sum of a prime and of two powers of two Pacific J. Math. 1971 103 107

[12] Dasgupta, Samit, Károlyi, Gyula, Serra, Oriol, Szegedy, Balázs Transversals of additive Latin squares Israel J. Math. 2001 17 28

[13] Dias Da Silva, J. A., Hamidoune, Y. O. Cyclic spaces for Grassmann derivatives and additive theory Bull. London Math. Soc. 1994 140 146

[14] Everett, C. J., Jr. Annihilator ideals and representation iteration for abstract rings Duke Math. J. 1939 623 627

[15] Erdős, P., Heilbronn, H. On the addition of residue classes 𝑚𝑜𝑑𝑝 Acta Arith. 1964 149 159

[16] Gao, W. D. Two addition theorems on groups of prime order J. Number Theory 1996 211 213

[17] Hou, Qing-Hu, Sun, Zhi-Wei Restricted sums in a field Acta Arith. 2002 239 249

[18] Kemnitz, Arnfried On a lattice point problem Ars Combin. 1983 151 160

[19] Nathanson, Melvyn B. Additive number theory 1996

[20] Olson, John E. A combinatorial problem on finite Abelian groups. I J. Number Theory 1969 8 10

[21] Porubský, Štefan On 𝑚 times covering systems of congruences Acta Arith. 1976 159 169

[22] Rónyai, Lajos On a conjecture of Kemnitz Combinatorica 2000 569 573

[23] Sun, Zhi Wei Covering the integers by arithmetic sequences Acta Arith. 1995 109 129

[24] Sun, Zhi-Wei Covering the integers by arithmetic sequences. II Trans. Amer. Math. Soc. 1996 4279 4320

[25] Sun, Zhi-Wei Exact 𝑚-covers and the linear form ∑^{𝑘}_{𝑠 Acta Arith. 1997 175 198

[26] Sun, Zhi-Wei On covering multiplicity Proc. Amer. Math. Soc. 1999 1293 1300

[27] Sun, Zhi-Wei On integers not of the form ±𝑝^{𝑎}±𝑞^{𝑏} Proc. Amer. Math. Soc. 2000 997 1002

[28] Sun, Zhi-Wei Algebraic approaches to periodic arithmetical maps J. Algebra 2001 723 743

[29] Zhang, Ming Zhi A note on covering systems of residue classes Sichuan Daxue Xuebao 1989 185 188

[30] Zhang, Ming Zhi Irreducible systems of residue classes that cover every integer exactly 𝑚 times Sichuan Daxue Xuebao 1991 403 408