Somme restreinte d'ensembles

En théorie additive des nombres et en combinatoire, une somme restreinte d'ensembles est[réf. souhaitée] un ensemble de la forme

A1, … , An sont des parties d'un groupe abélien G et B est une partie de Gn.

Le groupe G considéré est souvent le groupe additif d'un anneau commutatif[1], comme l'anneau ℤ des entiers ou un anneau ℤ/n.

Si l'ensemble B qu'on exclut est vide, S est simplement la somme d'ensembles usuelle A1 + … + An (notée nA si tous les Ak sont égaux à un même ensemble A).

Si B est l'ensemble des n-uplets d'éléments non tous distincts, alors S est noté

ou encore

lorsque tous les Ak sont égaux à A[2].

Théorème de Cauchy-Davenport

modifier

Démontré par Augustin Louis Cauchy[3] et redécouvert par Harold Davenport[4] qui s'aperçut plus tard de l'antériorité de Cauchy[5],[6], ce théorème assure que pour tout nombre premier p et pour toutes parties non vides A et B du corps fini ℤ/pℤ, on a l'inégalité suivante sur les cardinaux[7],[8] :

 

Un corollaire immédiat est que pour toute suite S de p – 1 éléments non nuls de ℤ/pℤ (non nécessairement distincts), tout élément de ℤ/pℤ est somme d'une sous-suite (éventuellement vide) de S[9].

On peut également en déduire le théorème d'Erdős-Ginzburg-Ziv : pour tout entier naturel n, toute suite de 2n – 1 éléments de ℤ/nℤ contient n termes de somme nulle[10].

Conjecture d'Erdős-Heilbronn

modifier

En 1980, Paul Erdős et Ronald Graham ont formulé la conjecture suivante[11], qu'il est d'usage[12],[13] de dater comme eux de 1964 en l'attribuant à Erdős et Heilbronn[14] :

pour tout nombre premier p et toute partie A du corps ℤ/pℤ,

 .

En 1994, José António Dias da Silva et Yahya Ould Hamidoune (1948-2011)[15],[16] la démontrèrent, prouvant même[17] que pour toute partie finie A d'un corps F,

 ,

p(F) désigne la caractéristique de F si celle-ci est non nulle, et p(F) = sinon.

Diverses généralisations ont été données par Noga Alon, Melvyn Nathanson et Imre Z. Ruzsa (en) en 1996[18], Qing-Hu Hou et Zhi Wei Sun en 2002[19] et Gyula Károlyi en 2004[20].

Nullstellensatz combinatoire

modifier

Un outil puissant pour minorer les cardinaux de diverses sommes restreintes d'ensembles est une méthode polynomiale, introduite en 1989 par Alon et Tarsi[21] puis développée par Alon, Nathanson et Ruzsa[18]. Alon (1999) l'a reformulée par le principe suivant, qu'il considère comme une variante du Nullstellensatz de Hilbert :

Soient f(x1, … , xn) un polynôme à coefficients dans un corps F et x1k1xnkn un monôme de coefficient non nul dans f et de degré maximal. Pour toutes parties A1, … , An de F telles que pour chaque i, |Ai| > ki, il existe dans leur produit un n-uplet en lequel f ne s'annule pas.

Alon décrit de nombreuses applications de ce principe, parmi lesquelles des démonstrations de théorèmes classiques comme celui de Cauchy-Davenport présenté ci-dessus ou celui de Chevalley-Warning.

Notes et références

modifier
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Restricted sumset » (voir la liste des auteurs).
  1. La partie B est alors souvent choisie de la forme {(a1, … , an) ∈ Gn | f(a1, … , an) = 0} pour un certain polynôme f à coefficients dans cet anneau : voir par exemple (en) Noga Alon, « Combinatorial Nullstellensatz », Combin. Probab. Comput., vol. 8, nos 1-2,‎ , p. 7-29 (lire en ligne).
  2. (en) Melvyn B. Nathanson, Additive Number Theory : Inverse Problems and Geometry of Sumsets, Springer, coll. « GTM » (no 165), (lire en ligne), p. 13.
  3. A. Cauchy, « Recherches sur les nombres », JEP, vol. 9,‎ , p. 99-123 (lire en ligne).
  4. (en) H. Davenport, « On the addition of residue classes », J. London Math. Soc., vol. 10,‎ , p. 30-32.
  5. (en) H. Davenport, « A historical note », J. London Math. Soc., vol. 22,‎ , p. 100-101.
  6. Nathanson 1996, p. 73.
  7. Nathanson 1996, p. 44.
  8. Une démonstration, « essentiellement celle de (en) Noga Alon, Melvyn B. Nathanson et Imre Ruzsa, « Adding Distinct Congruence Classes Modulo a Prime », Amer. Math. Month., vol. 102, no 3,‎ , p. 250-255 (lire en ligne) », est présentée dans (en) « Proof of Cauchy-Davenport theorem », sur PlanetMath.
  9. Pour un énoncé légèrement plus général, voir (en) Eric W. Weisstein, « Cauchy-Davenport Theorem », sur MathWorld.
  10. Nathanson 1996, p. 48.
  11. (en) P. Erdős et R. L. Graham, « Old and new problems and results in combinatorial number theory », L'Enseign. Math.,‎ , p. 1-128 (lire en ligne), p. 95.
  12. Nathanson 1996, p. 77.
  13. (en) Zhi-Wei Sun, « On some conjectures of Erdős-Heilbronn, Lev and Snevily », pdf : exposé de présentation.
  14. Dans l'article mentionné par Erdős et Graham, la conjecture portait en réalité sur une minoration, en fonction de |A|, du nombre de sommes distinctes obtenues en additionnant les éléments de parties quelconques de A : (en) P. Erdös et H. Heilbronn, « On the addition of residue classes modulo p », Acta Arith., vol. 9,‎ , p. 149-159 (lire en ligne), Conjecture 2.
  15. Alain Plagne, « Yahya Ould Hamidoune, grand Mauritanien, homme singulier, mathématicien d'exception », sur École polytechnique.
  16. Alain Plagne, « Yahya Ould Hamidoune the Mauritanian mathematician: 1948-11 March 2011 », Combin. Probab. Comput., vol. 20, no 5,‎ , p. 641-645 (DOI 10.1017/S0963548311000332).
  17. (en) J. A. Dias da Silva et Y. O. Hamidoune, « Cyclic spaces for Grassman derivatives and additive theory », Bull. London Math. Soc., vol. 26, no 2,‎ , p. 140-146 (DOI 10.1112/blms/26.2.140).
  18. a et b (en) Noga Alon, Melvyn B. Nathanson et Imre Ruzsa, « The polynomial method and restricted sums of congruence classes », J. Number Theor., vol. 56, no 2,‎ , p. 404-417 (lire en ligne).
  19. (en) Qing-Hu Hou et Zhi-Wei Sun, « Restricted sums in a field », Acta Arith., vol. 102, no 3,‎ , p. 239-249 (lire en ligne).
  20. (en) Gyula Károlyi, « The Erdős-Heilbronn problem in abelian groups », Isr. J. Math., vol. 139,‎ , p. 349-359 (DOI 10.1007/BF02787556).
  21. (en) Noga Alon et Michael Tarsi, « A nowhere-zero point in linear mappings », Combinatorica, vol. 9, no 4,‎ , p. 393-395 (lire en ligne).

Voir aussi

modifier

Liens externes

modifier