Théorème de Freiman

En mathématiques, le théorème de Freiman est un résultat combinatoire de théorie additive des nombres dû à Gregory Freiman (en)[1],[2],[3],[4] selon lequel, pour un ensemble fini A d'entiers, si la somme de A avec lui-même n'est « pas trop grosse » par rapport à A, alors A est inclus dans une progression arithmétique généralisée elle-même « pas trop grosse ».

Énoncé

Pour toute constante c > 0, il existe un entier naturel n et une constante c' tels que[5] :

pour tout ensemble fini A d'entiers tel que card(A + A) ≤ c card(A), il existe des entiers a, q₁, … , q_n, l₁, … , l_n tels que

${\displaystyle A\subset Q=\{a+x_{1}q_{1}+\ldots +x_{n}q_{n}~|~\forall i=1,\ldots ,n,~0\leq x_{i}<l_{i}\}\quad {\text{et}}\quad {\text{card}}(Q)\leq c'{\text{card}}(A).}$

Un cas simple instructif est le suivant[6] : on a toujours card(A + A) ≥ 2 card(A) – 1, avec égalité si et seulement si A est une progression arithmétique.

L'intérêt pour ce théorème et ses généralisations et applications a été ravivé par une nouvelle preuve due à Imre Z. Ruzsa (en)[7],[8]. En 2002, Mei-Chu Chang a donné de nouvelles estimations polynomiales de la taille des progressions arithmétiques qui apparaissent dans le théorème[9].

Green et Ruzsa ont généralisé le théorème pour un groupe abélien arbitraire[10] : ici, A peut être contenu dans la somme d'une progression arithmétique généralisée et d'un sous-groupe.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Freiman's theorem » (voir la liste des auteurs).

1. (en) Melvyn B. Nathanson, Additive Number Theory : Inverse Problems and Geometry of Sumsets, New York/Berlin/Heidelberg, Springer, coll. « GTM » (n^o 165), 1996, 293 p. (ISBN 0-387-94655-1, lire en ligne), p. 252, Zbl. 0859.11003.
2. (en) G. A. Freiman, « Addition of finite sets », Sov. Math. Dokl., vol. 5,‎ 1964, p. 1366-1370 – traduit du russe, dans Dokl. Akad. Nauk SSSR, vol. 158, 1964, p. 1038-1041, Zbl. 0163.29501.
3. (en) G. A. Freiman, Foundations of a Structural Theory of Set Addition, AMS, coll. « Translations of Mathematical Monographs » (n^o 37), 1973 – traduit du russe, Kazan Gos. Ped. Inst., 1966, 140 p., Zbl 0203.35305.
4. (en) G. A. Freiman, « Structure Theory of Set Addition », dans Jean-Marc Deshouillers, Bernard Landreau et Alexander A. Yudin, Structure Theory of Set Addition, SMF, coll. « Astérisque » (n^o 258), 1999, p. 1-33, Zbl 0958.11008.
5. Nathanson 1996, p. 231.
6. Nathanson 1996, p. 14-17.
7. (en) I. Z. Ruzsa, « Arithmetical progressions and the number of sums », Period. Math. Hungar., vol. 25, n^o 1,‎ 1992, p. 105-111 (DOI 10.1007/BF02454387).
8. (en) I. Z. Ruzsa, « Generalized arithmetical progressions and sumsets », Acta Math. Hungar., vol. 65, n^o 4,‎ 1994, p. 379-388 (DOI 10.1007/BF01876039), Zbl 0816.11008.
9. (en) Mei-Chu Chang, « A polynomial bound in Freiman's theorem », Duke Math. J., vol. 113, n^o 3,‎ 2002, p. 399-419 (DOI 10.1215/s0012-7094-02-11331-3, MR 1909605).
10. (en) Ben Green et Imre Z. Ruzsa, « Freiman's theorem in an arbitrary abelian group », J. London Math. Soc., vol. 75, n^o 1,‎ 2007, p. 163-175 (DOI 10.1112/jlms/jdl021, arXiv math/0505198).

Voir aussi

Articles connexes

• Théorème d'Erdős-Szemerédi
• Théorème de Kneser (combinatoire)
• Spectre de Markov

Lien externe

(en) Hamidoune’s Freiman-Kneser theorem for nonabelian groups, 12 mars 2011, sur le blog de Terence Tao