Somme restreinte d'ensembles

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]^,[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]^,[8] :

${\displaystyle |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[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].

En 1980, Paul Erdős et Ronald Graham ont formulé la conjecture suivante[11], qu'il est d'usage[12]^,[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ℤ,

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

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

${\displaystyle |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[18], Qing-Hu Hou et Zhi Wei Sun en 2002[19] et Gyula Károlyi en 2004[20].

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