Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Somme restreinte d'ensembles
Résumé
En théorie additive des nombres et en combinatoire, une somme restreinte d'ensembles un ensemble de la forme
où A, ... , A 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 Z des entiers ou un anneau Z/nZ.
Si l'ensemble B qu'on exclut est vide, S est simplement la somme d'ensembles usuelle A + ... + A (notée nA si tous les A 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é
ou encore
lorsque tous les A sont égaux à A.
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 Z/pZ, on a l'inégalité suivante sur les cardinaux :
Un corollaire immédiat est que pour toute suite S de p – 1 éléments non nuls de Z/pZ (non nécessairement distincts), tout élément de Z/pZ 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 Z/nZ contient n termes de somme nulle.
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 Z/pZ,
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.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.