Problème de la somme nulle
En théorie des nombres, les problèmes de la somme nulle forment une classe de questions combinatoires. Dans un groupe abélien fini G, le problème de la somme nulle est de déterminer, pour tout entier n > 0, le plus petit entier k tel que toute suite de k éléments de G contienne une sous-suite de n termes de somme 0.
En 1961, Paul Erdős, Abraham Ginzburg et Abraham Ziv ont démontré[1] que pour G égal au groupe additif de l'anneau ℤ/nℤ, ce plus petit k vaut 2n – 1. Ce résultat, appelé le théorème d'Erdős-Ginzburg-Ziv ou « théorème EGZ », peut se déduire du théorème de Cauchy-Davenport[2].
Il possède des généralisations comme le théorème d'Olson[3], la conjecture de Kemnitz (démontrée par Christian Reiher en 2003) et le « théorème EGZ pondéré » (démontré par David J. Grynkiewicz en 2005[4]).
Notes et références
- (en) P. Erdős, A. Ginzburg et A. Ziv, « Theorem in the additive number theory », Bull. Res. Council Israel, vol. 10F,‎ , p. 41-43 (lire en ligne)
- (en) Melvyn B. Nathanson, Additive Number Theory : Inverse Problems and Geometry of Sumsets, New York/Berlin/Heidelberg, Springer, coll. « GTM » (no 165), , 293 p. (ISBN 0-387-94655-1, lire en ligne), p. 48, Zbl. 0859.11003
- (en) J. E. Olson, « An addition theorem modulo p », J. Combin. Theory, vol. 5,‎ , p. 45-52
- (en) D. J. Grynkiewicz, « A Weighted Erdős-Ginzburg-Ziv Theorem », Combinatorica, vol. 26, no 4,‎ , p. 445-453 (DOI 10.1007/s00493-006-0025-y)
Liens externes
- (en) J. D. Bovey, P. Erdős et I. Niven, « Conditions for a zero sum modulo », Canad. Math. Bull., vol. 18,‎ , p. 27-29 (lire en ligne)
- (en) P. Hao, « On a Congruence modulo a Prime », Amer. Math. Month., vol. 113,‎ , p. 652-654 (lire en ligne)
- (en) Zhi Wei Sun, Covering Systems, Restricted Sumsets, Zero-sum Problems and their Unification (page web de synthèse via des liens)
