Problème de la somme nulle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Théorème d'Erdős.

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) en 2003) et le « théorème EGZ pondéré » (démontré par David J. Grynkiewicz en 2005[4]).

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Zero-sum problem » (voir la liste des auteurs)

  1. (en) P. Erdős, A. Ginzburg et A. Ziv, « Theorem in the additive number theory », Bull. Res. Council Israel, vol. 10F,‎ 1961, p. 41-43 (lire en ligne)
  2. (en) Melvyn B. Nathanson, Additive Number Theory: Inverse Problems and Geometry of Sumsets, Springer, coll. « GTM » (no 165),‎ 1996 (ISBN 0-387-94655-1, lire en ligne), p. 48, Zbl. 0859.11003
  3. (en) J. E. Olson, « An addition theorem modulo p », J. Combin. Theory, vol. 5,‎ 1968, p. 45-52
  4. (en) D. J. Grynkiewicz, « A Weighted Erdős-Ginzburg-Ziv Theorem », Combinatorica, vol. 26, no 4,‎ 2006, p. 445-453 (DOI 10.1007/s00493-006-0025-y)

Liens externes[modifier | modifier le code]