Mnoho částek

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 11. května 2018; kontroly vyžadují 7 úprav .

Množina součtů  je koncept aditivní kombinatoriky , odpovídající Minkowského součtu konečných množin .

Definice

Nechť je  libovolná grupa a  jsou konečné množiny. Pak je jejich součet množinou

Pro jednu množinu se její množina součtů nazývá . Vícenásobné součty jsou zkráceny [1]

Související definice

Podobně je pro libovolnou operaci definována množina rozdílů , množina produktů , množina kvocientů a podobně. Například sada produktů je definována takto [2] :

Hodnota se nazývá konstanta zdvojení [3] a množiny, pro které je omezena, mají malé zdvojnásobení [4] . V souvislosti s teorémem součtu o součinu se často uvažuje o množinách s malým multiplikativním zdvojením , tedy takové, pro které je omezená hodnota [5] .

Vlastnosti

Mocnina množiny součtů souvisí s aditivní energií pomocí nerovnosti [6] , proto se k jejímu odhadu často používá druhá jmenovaná.

Součty jedné množiny

Freimanův teorém považuje velikost za indikátor strukturovanosti množiny (pokud je konstanta zdvojení omezená, pak je struktura podobná zobecněné aritmetické progresi ). [7] [8]

Věta o součtu o součinu se vztahuje k velikosti množiny součtů a množiny produktů. Hlavní hypotéza říká, že pro . [9] Kombinace součtu a součinu v jednom výrazu vedla ke vzniku aritmetické kombinatoriky .

Studujeme vliv aplikace konvexní funkce prvek po prvku na sčítatelné množiny na velikost množiny součtů. Pro konvexní posloupnosti jsou známy dolní meze na a . [10] Obecněji, pro konvexní funkci a množinu, problém odhadu a některé podobné jsou někdy považovány za zobecnění věty o součtu-součinu, protože a proto je funkce konvexní. [jedenáct]

Součty několika množin

Nerovnost Plünnecke-Rouge uvádí, že růst (zvětšení velikosti s ohledem na sčítatelné množiny) násobných součtů v průměru (vzhledem k ) výrazně nepřevyšuje růst .

Rougeova trojúhelníková nerovnost dává do souvislosti velikosti libovolných množin a ukazuje, že normalizovanou velikost rozdílu množin lze považovat za pseudometriku, která odráží blízkost struktury těchto množin. [12]

Struktura

Jednou ze základních otázek aditivní kombinatoriky je: jakou strukturu mohou nebo by měly mít množiny součtů. Od začátku roku 2020 není znám žádný netriviálně rychlý algoritmus, který by určil, zda lze danou velkou množinu reprezentovat jako nebo . Jsou však známy některé dílčí výsledky o struktuře součtových množin.

Například množiny součtů reálných čísel nemohou mít malé multiplikativní zdvojení, tedy pokud , tak pro některé . [13] A ve skupině zbytků modulo a prime jsou pouze množiny, které lze reprezentovat jako . [14] [15]

Je známo, že pokud  jsou husté množiny přirozených čísel, pak obsahuje dlouhé aritmetické posloupnosti . [16] Nicméně jsou známy příklady hustých množin se silnou horní hranicí délky takových progresí. [17] [18]

Viz také

Literatura

Poznámky

  1. Freiman, 1966 , str. 7-8
  2. Tao, Wu, 2006 , str. 54, str. 92
  3. Tao, Wu, 2006 , str. 57
  4. Tao, Wu, 2006 , str. 240
  5. Tao, Wu, 2006 , str. 188; Shkredov, 2013 , § 5
  6. Podle Cauchyho-Bunyakovského nerovnosti , , kde  je počet zobrazení
  7. Freiman, 1966 .
  8. Tato otázka se často nazývá inverzní problém aditivní kombinatoriky (viz např. Freiman, 1966 , oddíl 1.8, s. 19)
  9. Erdős, Szemeredi, 1983 ; Shakan, 2019
  10. Shkredov, Schoen, 2011 .
  11. Elekes, Nathanson, Ruzsa, 2000 .
  12. Tao, Wu, 2006 , str. 60
  13. Shkredov, Zhelezov, 2016 , následek 2
  14. Alon, Granville, Ubis, 2010 .
  15. Zatímco celkový počet sad v této skupině je zjevně
  16. Bourgain to poprvé dokázal v Bourgain, 1990 . Nejlepší výsledek za rok 2020 byl získán v Green, 2002 a následně potvrzen novou, obecnější metodou v Croot, Laba, Sisask, 2013
  17. Ruzsa, 1991 .
  18. Přehled výsledků na toto téma lze nalézt v Croot, Ruzsa , Schoen, 2007