En théorie additive des nombres et en combinatoire, une somme restreinte d'ensembles un ensemble de la forme
où 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 commutatifLa partie B est alors souvent choisie de la forme {(a, … , a) ∈ G | f(a, … , a) = 0} pour un certain polynôme f à coefficients dans cet anneau : voir par exemple ., comme l'anneau ℤ des entiers ou un anneau ℤ/nℤ.
Si l'ensemble B qu'on exclut est vide, est simplement la somme d'ensembles usuelle (notée si tous les sont égaux à un même ensemble ).
Si B est l'ensemble des n-uplets d'éléments non tous distincts, alors est noté
ou encore
lorsque tous les sont égaux à ..
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.Une démonstration, « essentiellement celle de », est présentée dans . :
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 SPour un énoncé légèrement plus général, voir ..
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. Zhi-Wei Sun, « On some conjectures of Erdős-Heilbronn, Lev and Snevily », pdf : exposé de présentation. de dater comme eux de 1964 en l'attribuant à Erdős et HeilbronnDans 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 : , Conjecture 2. :
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).. la démontrèrent, prouvant même. que pour toute partie finie A d'un corps F,
,
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 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. l'a reformulée par le principe suivant, qu'il considère comme une variante du Nullstellensatz de Hilbert :
Soient f(x, … , x) un polynôme à coefficients dans un corps F et x…x un monôme de coefficient non nul dans f et de degré maximal. Pour toutes parties A, … , A de F telles que pour chaque i, |A| > k, 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
Voir aussi Liens externes
Catégorie:Théorie analytique des nombres Catégorie:Combinatoire Catégorie:Augustin Louis Cauchy