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.^[1]

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ő.^[2] 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.)^[3]

Kapcsolódó szócikkek

Markov-spektrum

Jegyzetek

Sablon:Reflist

Sablon:PlanetMath attribution

↑ Nathanson (1996) p.251
↑ Nathanson (1996) p.252
↑ B. Green and I. Ruzsa, Freiman’s theorem in an arbitrary abelian group, Jour. London Math. Soc. 75 (2007), no. 1, 163–175. arXiv:math/0505198

[1] Nathanson (1996) p.251

[2] Nathanson (1996) p.252

[3] B. Green and I. Ruzsa, Freiman’s theorem in an arbitrary abelian group, Jour. London Math. Soc. 75 (2007), no. 1, 163–175. arXiv:math/0505198

[1]

[2]

[3]

Freiman–Ruzsa-tétel

Kapcsolódó szócikkek

Jegyzetek

Navigációs menü

Keresés