Théorème de Freiman

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, le théorème de Freiman est un résultat combinatoire de théorie 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 (en) elle-même « pas trop grosse ».

Énoncé[modifier | modifier le code]

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

pour tout ensemble A d'entiers tel que card(A + A) ≤ c card(A), il existe des entiers a, q1, … , qn, l1, … , ln tels que

A\subset Q=\{a+x_1q_1+\ldots+x_nq_n~|~\forall i=1,\ldots,n,~0\le x_i<l_i\}\quad\text{et}\quad\text{card}(Q)\le 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].

Notes et références[modifier | modifier le code]

(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 (de), Additive Number Theory: Inverse Problems and Geometry of Sumsets, Springer, coll. « GTM » (no 165),‎ 1996 (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 » (no 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 (de), Bernard Landreau et Alexander A. Yudin, Structure Theory of Set Addition, SMF, coll. « Astérisque » (no 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, no 1,‎ 1992, p. 105-111 (DOI 10.1007/BF02454387)
  8. (en) I. Z. Ruzsa, « Generalized arithmetical progressions and sumsets », Acta Math. Hungar., vol. 65, no 4,‎ 1994, p. 379-388 (DOI 10.1007/BF01876039), Zbl 0816.11008

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

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