Aditivní kombinatorika - Additive combinatorics

Aditivní kombinatorika je oblast kombinatorika v matematice. Jednou z hlavních oblastí studia aditivní kombinatoriky jsou inverzní problémy: vzhledem k velikosti souprava A + B je malý, co můžeme říci o strukturách ${displaystyle A}$ a ${displaystyle B}$? V případě celých čísel klasická Freimanova věta poskytuje částečnou odpověď na tuto otázku, pokud jde o vícerozměrné aritmetické posloupnosti.

Dalším typickým problémem je najít dolní mez pro ${displaystyle | A + B |}$ ve smyslu ${displaystyle | A |}$ a ${displaystyle | B |}$. To lze považovat za inverzní problém s danou informací ${displaystyle | A + B |}$ je dostatečně malý a strukturální závěr je pak v té formě ${displaystyle A}$ nebo ${displaystyle B}$ je prázdná množina; v literatuře se však tyto problémy někdy považují také za přímé problémy. Mezi příklady tohoto typu patří Domněnka Erdős – Heilbronn (pro omezená částka ) a Cauchy – Davenportova věta. Metody používané při řešení těchto otázek často pocházejí z mnoha různých oborů matematiky, včetně kombinatorika, ergodická teorie, analýza, teorie grafů, teorie skupin, a lineární algebraika a polynomiální metody.

Historie aditivní kombinatoriky

Ačkoli aditivní kombinatorika je poměrně nová větev kombinatoriky (ve skutečnosti termín aditivní kombinatorika byl vytvořen Terence Tao a Van H. Vu ve své knize z roku 2000), což je extrémně starý problém Cauchy – Davenportova věta je jedním z nejzásadnějších výsledků v této oblasti.

Cauchy – Davenportova věta

Předpokládejme to A a B jsou konečné podmnožiny ${displaystyle mathbb {Z} / pmathbb {Z}}$ pro nejlepšího ${displaystyle p}$, pak platí následující nerovnost.

${displaystyle | A + B | geq min (| A | + | B | -1, p)}$

Vosperova věta

Nyní máme nerovnost pro mohutnost množiny ${displaystyle A + B}$, je přirozené se ptát na inverzní problém, konkrétně za jakých podmínek ${displaystyle A}$ a ${displaystyle B}$ platí rovnost? Na tuto otázku odpovídá Vosperova věta. Předpokládejme to ${displaystyle | A |, | B | geq 2}$ (to znamená vyloučení okrajových případů) a

${displaystyle | A + B | leq | A | + | B | -1leq p-2,}$

pak ${displaystyle A}$ a ${displaystyle B}$ jsou aritmetické průběhy se stejným rozdílem. To ilustruje struktury, které jsou často studovány v aditivní kombinatorice: kombinatorická struktura ${displaystyle A + B}$ ve srovnání s algebraickou strukturou aritmetických postupů.

Nerovnost Plünnecke – Ruzsa

Užitečná věta v aditivní kombinatorice je Nerovnost Plünnecke – Ruzsa. Tato věta dává horní mez na mohutnosti ${displaystyle | nA-mA |}$ pokud jde o zdvojnásobující konstantu ${displaystyle A}$. Například pomocí nerovnosti Plünnecke – Ruzsa můžeme dokázat verzi Freimanovy věty v konečných polích.

Základní pojmy

Operace na soupravách

Nechat A a B být konečné podmnožiny abelianské skupiny, pak je množina součtů definována jako

${displaystyle A + B = {a + b: ain A, bin B}.}$

Například můžeme psát ${displaystyle {1,2,3,4} + {1,2,3} = {2,3,4,5,6,7}}$. Podobně můžeme definovat sadu rozdílů A a B být

${displaystyle A-B = {a-b: ain A, bin B}.}$

Zde uvádíme další užitečné notace.

${displaystyle kA = underbrace {A + A + cdots + A} _ {k {ext {terms}}}}$

${displaystyle kcdot A = {ka: ain A}}$

Zdvojnásobující konstanta

Nechat A být podmnožinou abelianské skupiny. Konstanta zdvojnásobení měří, jak velká je nastavená suma ${displaystyle | A + A |}$ je ve srovnání s původní velikostí |A|. Definujeme zdvojnásobující konstantu A být

${displaystyle K = {dfrac {| A + A |} {| A |}}.}$

Ruzsa vzdálenost

Nechat A a B být dvě podmnožiny abelianské skupiny. Definujeme Ruzsovu vzdálenost mezi těmito dvěma množinami jako veličinu

${displaystyle d (A, B) = log {dfrac {| A-B |} {sqrt {| A || B |}}}.}$

Nerovnost trojúhelníku Ruzsa nám říká, že vzdálenost Ruzsy se řídí nerovností trojúhelníku:

${displaystyle d (B, C) leq d (A, B) + d (A, C).}$

Nicméně od té doby ${displaystyle d (A, A)}$ nemůže být nula, všimněte si, že Ruzsova vzdálenost není ve skutečnosti metrikou.

Reference

Citace

• Tao, T., & Vu, V. (2012). Aditivní kombinatorika. Cambridge: Cambridge University Press.
• Green, B. (2009, 15. ledna). Recenze knihy Additive Combinatorics. Citováno z https://www.ams.org/journals/bull/2009-46-03/S0273-0979-09-01231-2/S0273-0979-09-01231-2.pdf.