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

${\displaystyle 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\},}$

où A₁, … , A_n sont des parties d'un groupe abélien G et B est une partie de Gⁿ.

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 A₁ + … + A_n (notée nA si tous les A_k 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é

${\displaystyle A_{1}\dotplus \cdots \dotplus A_{n},}$

ou encore

${\displaystyle n^{\wedge }A}$

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

Théorème de Cauchy-Davenport

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

${\displaystyle |A+B|\geq \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

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

${\displaystyle |2^{\wedge }A|\geq \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,

${\displaystyle |n^{\wedge }A|\geq \min(p(F),~n|A|-n^{2}+1)}$,

où 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

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(x₁, … , x_n) un polynôme à coefficients dans un corps F et x₁^k₁…x_n^k_n un monôme de coefficient non nul dans f et de degré maximal. Pour toutes parties A₁, … , A_n de F telles que pour chaque i, |A_i| > k_i, 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

(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 {(a₁, … , a_n) ∈ Gⁿ | f(a₁, … , a_n) = 0} pour un certain polynôme f à coefficients dans cet anneau : voir par exemple (en) Noga Alon, « Combinatorial Nullstellensatz », Combin. Probab. Comput., vol. 8, n^os 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 » (n^o 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, n^o 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 », 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.,‎ 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, n^o 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, n^o 2,‎ 1994, p. 140-146 (DOI 10.1112/blms/26.2.140).
18. (en) Noga Alon, Melvyn B. Nathanson et Imre Ruzsa, « The polynomial method and restricted sums of congruence classes », J. Number Theor., vol. 56, n^o 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, n^o 3,‎ 2002, p. 239-249 (lire en ligne).
20. (en) Gyula Károlyi, « The Erdős-Heilbronn problem in abelian groups », Isr. J. Math., 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, n^o 4,‎ 1989, p. 393-395 (lire en ligne).

Voir aussi

Liens externes

• (en) Zhi Wei Sun, « An additive theorem and restricted sumsets », Math. Res. Lett., vol. 15, n^o 6,‎ 2006, p. 1263-1276 (arXiv math.CO/0610981)
• (en) Eric W. Weisstein, « Erdős-Heilbronn Conjecture », sur MathWorld

• Arithmétique et théorie des nombres