Somme restreinte d'ensembles
# 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_1,$ … , $A_n$ sont des parties d'un groupe abélien G et B est une partie de $G^n.$

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_1$ + … + $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_1,$ … , $x_n)$ un polynôme à coefficients dans un corps F et $x_1^{k1}…x_n^{kn}$ un monôme de coefficient non nul dans f et de degré maximal. Pour toutes parties $A_1,$ … , $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.

