Somme restreinte d'ensembles

De testwiki
Version datée du 4 octobre 2022 à 13:27 par imported>Herr Satz (utilisation modèle {{Planetmath}} ad hoc)
(diff) ← Version précédente | Version actuelle (diff) | Version suivante → (diff)
Aller à la navigation Aller à la recherche

En théorie additive des nombres et en combinatoire, une somme restreinte d'ensembles Modèle:Refsou un ensemble de la forme

S={a1+⋯+an|a1∈A1,…,an∈An et (a1,…,an)∉B},

où Modèle:Math sont des parties d'un groupe abélien G et B est une partie de [[Produit cartésien#Multiplets|GModèle:Exp]].

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, Modèle:Math est simplement la somme d'ensembles usuelle Modèle:Math (notée Modèle:Math si tous les Modèle:Math sont égaux à un même ensemble Modèle:Math).

Si B est l'ensemble des n-uplets d'éléments non tous distincts, alors Modèle:Math est noté

A1∔⋯∔An,

ou encore

n∧A

lorsque tous les Modèle:Math sont égaux à Modèle:Math[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]Modèle:,[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]Modèle:,[8] :

|A+B|≥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]Modèle:,[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∧A|≥min⁡(p,2|A|−3).

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

|n∧A|≥min⁡(p(F),n|A|−n2+1),

où p(F) désigne la caractéristique de F si celle-ci est non nulle, et p(F) = Modèle:Math sinon.

Diverses généralisations ont été données par Noga Alon, Melvyn Nathanson et Modèle:Lien 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]. Modèle:Harvsp l'a reformulée par le principe suivant, qu'il considère comme une variante du Nullstellensatz de Hilbert :

Soient f(xModèle:Ind, … , xModèle:Ind) un polynôme à coefficients dans un corps F et xModèle:IndModèle:Exp…xModèle:IndModèle:Exp un monôme de coefficient non nul dans f et de degré maximal. Pour toutes parties AModèle:Ind, … , AModèle:Ind de F telles que pour chaque i, |AModèle:Ind| > kModèle:Ind, 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

Modèle:Traduction/Référence Modèle:Reflist

Voir aussi

Liens externes

Modèle:Portail

  1. ↑ La partie B est alors souvent choisie de la forme {(aModèle:Ind, … , aModèle:Ind) ∈ GModèle:Exp | f(aModèle:Ind, … , aModèle:Ind) = 0} pour un certain polynôme f à coefficients dans cet anneau : voir par exemple Modèle:Article.
  2. ↑ Modèle:Ouvrage.
  3. ↑ Modèle:Article.
  4. ↑ Modèle:Article.
  5. ↑ Modèle:Article.
  6. ↑ Modèle:Harvsp.
  7. ↑ Modèle:Harvsp.
  8. ↑ Une démonstration, « essentiellement celle de Modèle:Article », est présentée dans Modèle:Planetmath.
  9. ↑ Pour un énoncé légèrement plus général, voir Modèle:MathWorld.
  10. ↑ Modèle:Harvsp.
  11. ↑ Modèle:Article, Modèle:P..
  12. ↑ Modèle:Harvsp.
  13. ↑ Modèle: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 : Modèle:Article, Conjecture 2.
  15. ↑ Modèle:Lien web.
  16. ↑ Modèle:Article.
  17. ↑ Modèle:Article.
  18. ↑ 18,0 et 18,1 Modèle:Article.
  19. ↑ Modèle:Article.
  20. ↑ Modèle:Article.
  21. ↑ Modèle:Article.
Récupérée de "https://fr.wiki.beta.math.wmflabs.org/w/index.php?title=Somme_restreinte_d%27ensembles&oldid=13256"