Freiman–Ruzsa-tétel

A matematikában a Freiman–Ruzsa-tétel vagy Freiman-tétel az additív számelmélet kombinatorikai eredménye. Az olyan, egész számokból álló halmazok szerkezetével foglalkozik, amelyek belső, páronként vett összegeik jelentős részét tartalmazzák („small doubling” tulajdonsággal rendelkeznek).

Formálisan:

Legyen A egész számok véges halmaza, úgy, hogy az

$A+A\,$ összeghalmaz kicsi,

abban az értelemben, hogy

$|A+A|<c|A|\,$

Valamely $c$ konstansra. Létezik egy

$c'|A|$ hosszúságú n-dimenziós számtani sorozat,

ami tartalmazza A-t úgy, hogy c' és n kizárólag c-től függjön.

Tekintsünk egy egyszerű esetet. A következő egyenlőtlenség

$|A+A|\geq 2|A|-1$

akkor veszi fel az egyenlőséget, ha A egy számtani sorozat elemeiből áll.

Az eredmény Gregory Freiman (1964, 1966) nevéhez köthető. Az iránta való megújult érdeklődés és alkalmazásai Ruzsa Z. Imre 1994-es új bizonyításához köthető.

Később Green és Ruzsa általánosították a tételt tetszőleges Abel-csoportra: ilyenkor az A halmaz egy általánosított számtani sorozat és egy részcsoport összegével fedhető le. (Az ilyen halmazokat nevezik mellékosztály-sorozatnak.)

Kapcsolódó szócikkek

• Markov-spektrum

Jegyzetek

• Freiman, G.A. (1964). „Addition of finite sets” (english. russian original nyelven). Sov. Math., Dokl. 5, 1366–1370. o. 
• Freiman, G. A.. Foundations of a Structural Theory of Set Addition (russian nyelven). Kazan: Kazan Gos. Ped. Inst., 140. o. (1966) 
• Freiman, G. A. (1999). „Structure theory of set addition”. Astérisque 258, 1–33. o. 
• Nathanson, Melvyn B.. Additive Number Theory: Inverse Problems and Geometry of Sumsets, Graduate Texts in Mathematics. Springer (1996). ISBN 0-387-94655-1 
• Ruzsa, Imre Z. (1994). „Generalized arithmetical progressions and sumsets”. Acta Mathematica Hungarica 65, 379–388. o. DOI:10.1007/bf01876039. 
• Ruzsa, Imre Z. (2007). „Freiman’s theorem in an arbitrary abelian group”. London Math. Soc. 75, 163–175. o. DOI:10.1112/jlms/jdl021. 

Ez a szócikk átvesz anyagokat a(z) Freiman's theorem című PlanetMath-bejegyzésből, ami Creative Commons Attribution/Share-Alike License alatt van.