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

$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, 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é

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

ou encore

$n^{\wedge }A$

lorsque tous les A_k sont égaux à A.

Théorème de Cauchy-Davenport

Démontré par Augustin Louis Cauchy et redécouvert par Harold Davenport qui s'aperçut plus tard de l'antériorité de Cauchy, 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 :

$|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.

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.

Conjecture d'Erdős-Heilbronn

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

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

$|2^{\wedge }A|\geq \min(p,~2|A|-3)$.

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

$|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, Qing-Hu Hou et Zhi Wei Sun en 2002 et Gyula Károlyi en 2004.

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 puis développée par Alon, Nathanson et Ruzsa. 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).

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