Freimansova věta - Freimans theorem - Wikipedia

v aditivní kombinatorika, Freimanova věta je ústředním výsledkem, který označuje přibližnou strukturu množin, jejichž souprava je malý. To zhruba uvádí, že pokud ${ displaystyle | A + A | / | A |}$ je tedy malý ${ displaystyle A}$ mohou být obsaženy v malém zobecněný aritmetický postup.

Prohlášení

Li ${ displaystyle A}$ je konečná podmnožina ${ displaystyle mathbb {Z}}$ s ${ displaystyle | A + A | leq K | A |}$, pak ${ displaystyle A}$ je obsažen nanejvýš v generalizovaném aritmetickém postupu dimenze ${ displaystyle d (K)}$ a maximálně velikost ${ displaystyle f (K) | A |}$, kde ${ displaystyle d (K)}$ a ${ displaystyle f (K)}$ jsou konstanty pouze v závislosti na ${ displaystyle K}$.

Příklady

Pro konečnou množinu ${ displaystyle A}$ celých čísel vždy platí

${ displaystyle | A + A | geq 2 | A | -1,}$

s rovností přesně kdy ${ displaystyle A}$ je aritmetický postup.

Obecněji předpokládejme ${ displaystyle A}$ je podmnožinou konečné konečné generalizované aritmetické progrese ${ displaystyle P}$ dimenze ${ displaystyle d}$ takhle ${ displaystyle | P | leq C | A |}$ pro některé skutečné ${ displaystyle C geq 1}$. Pak ${ displaystyle | P + P | leq 2 ^ {d} | P |}$, aby

${ displaystyle | A + A | leq | P + P | leq 2 ^ {d} | P | leq C2 ^ {d} | A |.}$

Historie Freimanovy věty

Tento výsledek je způsoben Gregory Freiman (1964,1966).^[1] Velký zájem o něj a aplikace vycházel z nového důkazu od Imre Z. Ruzsa (1994). Mei-Chu Chang prokázal nové polynomiální odhady velikosti aritmetických progresí vznikajících ve větě v roce 2002.^[2] Současné nejlepší hranice poskytl Tom Sanders.^[3]

Nástroje použité v důkazu

Zde uvedený důkaz navazuje na důkaz uvedený v přednáškách Yufei Zhao.^[4]

Nerovnost Plünnecke-Ruzsa

Ruzsa pokrývající lemma

Lemma pokrývající Ruzsu uvádí následující:

Nechat ${ displaystyle A}$ a ${ displaystyle S}$ být konečné podmnožiny abelianské skupiny s ${ displaystyle S}$ neprázdný, a nechť ${ displaystyle K}$ být kladné reálné číslo. Pak pokud ${ displaystyle | A + S | leq K | S |}$, existuje podmnožina ${ displaystyle T}$ z ${ displaystyle A}$ maximálně ${ displaystyle K}$ prvky takové, že ${ displaystyle A subseteq T + S-S}$.

Toto lemma poskytuje vázané množství kopií ${ displaystyle S-S}$ člověk musí pokrýt ${ displaystyle A}$, odtud název. Důkaz je v zásadě a chamtivý algoritmus:

Důkaz: Nechat ${ displaystyle T}$ být maximální podmnožinou ${ displaystyle A}$ takové, že sady ${ displaystyle t + S}$ pro ${ displaystyle A}$ jsou všechny disjunktní. Pak ${ displaystyle | T + S | = | T | cdot | S |}$, a také ${ displaystyle | T + S | leq | A + S | leq K | S |}$, tak ${ displaystyle | T | leq K}$. Navíc pro všechny ${ displaystyle a v A}$, některé jsou ${ displaystyle t v T}$ takhle ${ displaystyle t + S}$ protíná se ${ displaystyle a + S}$, jako jinak přidání ${ displaystyle a}$ na ${ displaystyle T}$ je v rozporu s maximálností ${ displaystyle T}$. Tím pádem ${ displaystyle a v T + S-S}$, tak ${ displaystyle A subseteq T + S-S}$.

Freimanské homomorfismy a lemma modelování Ruzsy

Nechat ${ displaystyle s geq 2}$ být kladné celé číslo a ${ displaystyle Gamma}$ a ${ displaystyle Gamma '}$ být abelianské skupiny. Nechat ${ displaystyle A subseteq Gamma}$ a ${ displaystyle B subseteq Gamma '}$. Mapa ${ displaystyle varphi dvojtečka A až B}$ je Freiman ${ displaystyle s}$-homomorfismus, pokud

${ displaystyle varphi (a_ {1}) + cdots + varphi (a_ {s}) = varphi (a_ {1} ') + cdots + varphi (a_ {s}')}$

kdykoli ${ displaystyle a_ {1} + cdots + a_ {s} = a_ {1} '+ cdots + a_ {s}'}$ pro všechny ${ displaystyle a_ {1}, ldots, a_ {s}, a_ {1} ', ldots, a_ {s}' v A}$.

Pokud navíc ${ displaystyle varphi}$ je bijekce a ${ displaystyle varphi ^ {- 1} dvojtečka B až A}$ je Freiman ${ displaystyle s}$-homomorfismus, tedy ${ displaystyle varphi}$ je Freiman ${ displaystyle s}$-izomorfismus.

Li ${ displaystyle varphi}$ je Freiman ${ displaystyle s}$-homomorfismus, tedy ${ displaystyle varphi}$ je Freiman ${ displaystyle t}$-homomorfismus pro jakékoli kladné celé číslo ${ displaystyle t}$ takhle ${ displaystyle 2 leq t leq s}$.

Potom lemma modelování Ruzsa uvádí následující:

Nechat ${ displaystyle A}$ být konečnou množinou celých čísel a nechat ${ displaystyle s geq 2}$ být kladné celé číslo. Nechat ${ displaystyle N}$ být kladné celé číslo takové, že ${ displaystyle N geq | sA-sA |}$. Pak existuje podmnožina ${ displaystyle A '}$ z ${ displaystyle A}$ alespoň s mohutností ${ displaystyle | A | / s}$ takhle ${ displaystyle A '}$ je Freiman ${ displaystyle s}$-izomorfní s podmnožinou ${ displaystyle mathbb {Z} / N mathbb {Z}}$.

Poslední prohlášení znamená, že existuje nějaký Freiman ${ displaystyle s}$-homomorfismus mezi těmito dvěma podmnožinami.

Důkazní skica: Vyberte prvočíslo ${ displaystyle q}$ dostatečně velký na to, aby${ displaystyle q}$ redukční mapa ${ displaystyle pi _ {q} dvojtečka mathbb {Z} až mathbb {Z} / q mathbb {Z}}$ je Freiman ${ displaystyle s}$-izomorfismus z ${ displaystyle A}$ na jeho obraz v ${ displaystyle mathbb {Z} / q mathbb {Z}}$. Nechat ${ displaystyle psi _ {q} tlustý mathbb {Z} / q mathbb {Z} do mathbb {Z}}$ být zvedací mapou, která vezme každého člena ${ displaystyle mathbb {Z} / q mathbb {Z}}$ svému jedinečnému zástupci v ${ displaystyle {1, ldots, q } subseteq mathbb {Z}}$. Pro nenulovou hodnotu ${ displaystyle lambda in mathbb {Z} / q mathbb {Z}}$, nechť ${ displaystyle cdot lambda colon mathbb {Z} / q mathbb {Z} do mathbb {Z} / q mathbb {Z}}$ být násobením ${ displaystyle lambda}$ mapa, což je Freiman ${ displaystyle s}$-izomorfismus. Nechat ${ displaystyle B}$ být obrazem ${ displaystyle ( cdot lambda circ pi _ {q}) (A)}$. Vyberte vhodnou podmnožinu ${ displaystyle B '}$ z ${ displaystyle B}$ alespoň s mohutností ${ displaystyle | B | / s}$ takové, že omezení ${ displaystyle psi _ {q}}$ na ${ displaystyle B '}$ je Freiman ${ displaystyle s}$-izomorfismus na svůj obraz, a nechť ${ displaystyle A ' subseteq A}$ být předobrazem ${ displaystyle B '}$ pod ${ displaystyle cdot lambda circ pi _ {q}}$. Pak omezení ${ displaystyle psi _ {q} circ cdot lambda circ pi _ {q}}$ na ${ displaystyle A '}$ je Freiman ${ displaystyle s}$-izomorfismus na svůj obraz ${ displaystyle psi _ {q} (B ')}$. Nakonec existuje nějaká volba nenulové ${ displaystyle lambda}$ takové, že omezení modulo-${ displaystyle N}$ snížení ${ displaystyle mathbb {Z} do mathbb {Z} / N mathbb {Z}}$ na ${ displaystyle psi _ {q} (B ')}$ je Freiman ${ displaystyle s}$-izomorfismus na svůj obraz. Výsledek následuje po sestavení této mapy s dřívějším Freimanem ${ displaystyle s}$-izomorfismus.

Bohrovy množiny a Bogolyubovovo lemma

Ačkoli Freimanova věta platí pro množiny celých čísel, lemma modelování Ruzsa umožňuje modelovat množiny celých čísel jako podmnožiny konečných cyklické skupiny. Je tedy užitečné nejprve pracovat v nastavení a konečné pole a poté zobecnit výsledky na celá čísla. Následující lemma dokázal Bogolyubov:

Nechat ${ displaystyle A in mathbb {F} _ {2} ^ {n}}$ a nechte ${ displaystyle alpha = | A | / 2 ^ {n}}$. Pak ${ displaystyle 4A}$ obsahuje podprostor o ${ displaystyle mathbb {F} _ {2} ^ {n}}$ alespoň dimenze ${ displaystyle n- alpha ^ {- 2}}$.

Zobecnění tohoto lemmatu na libovolné cyklické skupiny vyžaduje analogický pojem „podprostoru“: Bohrův soubor. Nechat ${ displaystyle R}$ být podmnožinou ${ displaystyle mathbb {Z} / N mathbb {Z}}$ kde ${ displaystyle N}$ je prime. The Bohrova sada dimenze ${ displaystyle | R |}$ a šířka ${ displaystyle epsilon}$ je

${ displaystyle operatorname {Bohr} (R, epsilon) = {x in mathbb {Z} / N mathbb {Z}: forall r in R, | rx / N | leq epsilon },}$

kde ${ displaystyle | rx / N |}$ je vzdálenost od ${ displaystyle rx / N}$ na nejbližší celé číslo. Následující lemma zobecňuje Bogolyubovovo lemma:

Nechat ${ displaystyle A in mathbb {Z} / N mathbb {Z}}$ a ${ displaystyle alpha = | A | / N}$. Pak ${ displaystyle 2A-2A}$ obsahuje maximálně Bohrovu sadu dimenzí ${ displaystyle alpha ^ {- 2}}$ a šířka ${ displaystyle 1/4}$.

Zde je rozměr Bohrovy množiny analogický s kodimenzionální sady v ${ displaystyle mathbb {F} _ {2} ^ {n}}$. Důkaz lemmatu zahrnuje Fourierova analytika metody. Následující tvrzení se týká Bohrových sad zpět k zobecněným aritmetickým postupům, které nakonec vedou k důkazu Freimanovy věty.

Nechat ${ displaystyle X}$ být Bohr ${ displaystyle mathbb {Z} / N mathbb {Z}}$ dimenze ${ displaystyle d}$ a šířka ${ displaystyle epsilon}$. Pak ${ displaystyle X}$ obsahuje správný zobecněný aritmetický postup dimenze nanejvýš ${ displaystyle d}$ a velikost alespoň ${ displaystyle ( epsilon / d) ^ {d} N}$.

Důkaz tohoto návrhu se používá Minkowského věta, zásadní výsledek v geometrie čísel.

Důkaz

Nerovností Plünnecke-Ruzsa, ${ displaystyle | 8A-8A | leq K ^ {16} | A |}$. Podle Bertrandův postulát, existuje prime ${ displaystyle N}$ takhle ${ displaystyle | 8A-8A | leq N leq 2K ^ {16} | A |}$. U lemmatu modelování Ruzsa existuje podmnožina ${ displaystyle A '}$ z ${ displaystyle A}$ alespoň mohutnosti ${ displaystyle | A | / 8}$ takhle ${ displaystyle A '}$ je Freiman 8-izomorfní s podmnožinou ${ displaystyle B subseteq mathbb {Z} / N mathbb {Z}}$.

Zobecněním Bogolyubovova lemmatu ${ displaystyle 2B-2B}$ obsahuje správný zobecněný aritmetický postup dimenze ${ displaystyle d}$ nejvíce ${ displaystyle (1 / (8 cdot 2K ^ {16})) ^ {- 2} = 256K ^ {32}}$ a velikost alespoň ${ displaystyle (1 / (4d)) ^ {d} N}$. Protože ${ displaystyle A '}$ a ${ displaystyle B}$ jsou Freiman 8-izomorfní, ${ displaystyle 2A'-2A '}$ a ${ displaystyle 2B-2B}$ jsou Freiman 2-izomorfní. Pak obraz pod 2-izomorfismem správné generalizované aritmetické progrese v ${ displaystyle 2B-2B}$ je správný zobecněný aritmetický postup v ${ displaystyle 2A'-2A ' subseteq 2A-2A}$ volala ${ displaystyle P}$.

Ale ${ displaystyle P + A subseteq 3A-2A}$, od té doby ${ displaystyle P subseteq 2A-2A}$. Tím pádem

${ displaystyle | P + A | leq | 3A-2A | leq | 8A-8A | leq N leq (4d) ^ {d} | P |}$

tak podle krymského lemmatu Ruzsa ${ displaystyle A subseteq X + P-P}$ pro některé ${ displaystyle X subseteq A}$ mohutnosti nanejvýš ${ displaystyle (4d) ^ {d}}$. Pak ${ displaystyle X + P-P}$ je obsažen ve zobecněném aritmetickém postupu dimenze ${ displaystyle | X | + d}$ a maximálně velikost ${ displaystyle 2 ^ {| X |} 2 ^ {d} | P | leq 2 ^ {| X | + d} | 2A-2A | leq 2 ^ {| X | + d} K ^ {4} | A |}$, vyplnění důkazu.

Zobecnění

Výsledek kvůli Ben Green a Imre Ruzsa zobecnil Freimanovu větu na libovolné abelianské skupiny. Použili analogický pojem k obecným aritmetickým postupům, které nazývali cosetovy pokroky. A cosetova progrese skupiny abelianů ${ displaystyle G}$ je sada ${ displaystyle P + H}$ pro správnou generalizovanou aritmetickou posloupnost ${ displaystyle P}$ a podskupina ${ displaystyle H}$ z ${ displaystyle G}$. Dimenze tohoto postupu cosetu je definována jako dimenze ${ displaystyle P}$a jeho velikost je definována jako mohutnost celé sady. Green a Ruzsa ukázali následující:

Nechat ${ displaystyle A}$ být konečný soubor v abelianské skupině ${ displaystyle G}$ takhle ${ displaystyle | A + A | leq K | A |}$. Pak ${ displaystyle A}$ je obsažen maximálně v cosetově progresi dimenze ${ displaystyle d (K)}$ a maximálně velikost ${ displaystyle f (K) | A |}$, kde ${ displaystyle f (K)}$ a ${ displaystyle d (K)}$ jsou funkce ${ displaystyle K}$ které jsou nezávislé na ${ displaystyle G}$.

Green a Ruzsa poskytli horní hranici ${ displaystyle d (K) = CK ^ {4} log (K + 2)}$ a ${ displaystyle f (K) = e ^ {CK ^ {4} log ^ {2} (K + 2)}}$ pro nějakou absolutní konstantu ${ displaystyle C}$.^[5]

Terence Tao (2010) také zobecnili Freimanovu větu na řešitelné skupiny omezené odvozené délky.^[6]

Rozšíření Freimanovy věty na libovolnou neaabelianskou skupinu je stále otevřené. Výsledky pro ${ displaystyle K <2}$, když sada má velmi malé zdvojnásobení, jsou označovány jako Kneser věty.^[7]

Viz také

• Markovovo spektrum
• Nerovnost Plünnecke-Ruzsa
• Kneserova věta (kombinatorika)

Reference

• Freiman, G.A. (1964). "Přidání konečných množin". Sov. Math., Dokl. 5: 1366–1370. Zbl  0163.29501.
• Freiman, G. A. (1966). Základy strukturní teorie sčítání množin (v Rusku). Kazan: Kazan Gos. Ped. Inst. str. 140. Zbl  0203.35305.
• Freiman, G. A. (1999). "Strukturní teorie přidávání množin". Astérisque. 258: 1–33. Zbl  0958.11008.
• Nathanson, Melvyn B. (1996). Teorie aditivních čísel: Inverzní problémy a geometrie sumersetů. Postgraduální texty z matematiky. 165. Springer. ISBN  978-0-387-94655-9. Zbl  0859.11003.
• Ruzsa, Imre Z. (1994). Msgstr "Zobecněné aritmetické postupy a součty". Acta Mathematica Hungarica. 65 (4): 379–388. doi:10.1007 / bf01876039. Zbl  0816.11008.
• Tao, Terence (2010). "Freimanova věta pro řešitelné skupiny". Přispět. Disk. Matematika. 5 (2): 137–184. doi:10.11575 / cdm.v5i2.62020.

Tento článek obsahuje materiál z Freimanovy věty PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.