Somme restreinte d'ensembles

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

S=\{a_1+\cdots+a_n~|~a_1\in A_1,\ldots,a_n\in A_n\text{ et }(a_1,\ldots,a_n)\notin B\},

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é

A_1\dotplus\cdots\dotplus A_n,

ou encore

n^{\wedge} A

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

Théorème de Cauchy-Davenport[modifier | modifier le code]

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] :

|A+B|\ge\min(p,~|A|+|B|-1).

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 | modifier le code]

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ℤ,

|2^\wedge A|\ge\min(p,~2|A|-3).

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,

|n^\wedge A|\ge\min(p(F),~n|A|-n^2+1),

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 (de) 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 | modifier le code]

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 | modifier le code]

(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, no 1-2,‎ 1999, 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),‎ 1996 (lire en ligne), p. 13
  3. A. Cauchy, « Recherches sur les nombres », JEP, vol. 9,‎ 1813, p. 99-123 (lire en ligne)
  4. (en) H. Davenport, « On the addition of residue classes », J. London Math. Soc., vol. 10,‎ 1935, p. 30-32
  5. (en) H. Davenport, « A historical note », J. London Math. Soc., vol. 22,‎ 1947, 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,‎ 1995, 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 », 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.,‎ 1980, 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,‎ 1964, 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,‎ 2011, 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,‎ 1994, 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,‎ 1996, 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,‎ 2002, p. 239-249 (lire en ligne).
  20. (en) Gyula Károlyi, « The Erdős-Heilbronn problem in abelian groups », Isr. J. Math. (en), vol. 139,‎ 2004, 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,‎ 1989, p. 393-395 (lire en ligne)

Liens externes[modifier | modifier le code]