Polynomiální metoda v kombinatorice - Polynomial method in combinatorics - Wikipedia

V matematice polynomiální metoda je algebraický přístup k kombinatorika problémy, které zahrnují zachycení nějaké kombinatorické struktury pomocí polynomů a pokračování argumentů o jejich algebraických vlastnostech. Polynomiální metoda v poslední době vedla k vývoji pozoruhodně jednoduchých řešení několika dlouhodobých otevřených problémů^[1]. Metoda polynomu zahrnuje širokou škálu specifických technik pro použití polynomů a nápadů z oblastí, jako je algebraická geometrie, k řešení kombinatorických problémů. Zatímco několik technik, které následují rámec polynomiální metody, jako je Alon Kombinatorický Nullstellensatz^[2], jsou známy od 90. let, až kolem roku 2010 byl vyvinut širší rámec pro polynomiální metodu.

Matematický přehled

Mnoho použití metody polynomu se řídí stejným přístupem na vysoké úrovni. Přístup je následující:

• Vložte nějaký kombinatorický problém do vektorového prostoru.
• Zachyťte hypotézy problému konstrukcí polynomu nízkého stupně, který je na určité množině nulový
• Po konstrukci polynomu se dohadujte o jeho algebraických vlastnostech, abyste odvodili, že původní konfigurace musí splňovat požadované vlastnosti.

Příklad

Jako příklad uvedeme Dvirův důkaz Konečná dohad Kakeya pole pomocí polynomiální metody^[3].

Konečná pole Kakeya dohad: Nechte ${ displaystyle mathbb {F} _ {q}}$ být konečným polem s ${ displaystyle q}$ elementy. Nechat ${ displaystyle K subseteq mathbb {F} _ {q} ^ {n}}$ být sadou Kakeya, tj. pro každý vektor ${ displaystyle y in mathbb {F} _ {q} ^ {n}}$tady existuje ${ displaystyle x in mathbb {F} _ {q} ^ {n}}$ takhle ${ displaystyle K}$ obsahuje řádek ${ displaystyle {x + ty, t in mathbb {F} _ {q} }}$. Pak sada ${ displaystyle K}$ má velikost alespoň ${ displaystyle c_ {n} q ^ {n}}$kde ${ displaystyle c_ {n}> 0}$ je konstanta, na které záleží jen ${ displaystyle n}$.

Důkaz: Důkaz, který poskytneme, to ukáže ${ displaystyle K}$ má velikost alespoň ${ displaystyle c_ {n} q ^ {n-1}}$. Vázaný z ${ displaystyle c_ {n} q ^ {n}}$ lze získat stejnou metodou s trochou další práce.

Předpokládejme, že máme sadu Kakeya ${ displaystyle K}$ s

${ displaystyle | K | <{q + n-3 vyberte n-1}}$

Zvažte sadu monomiálů formuláře ${ displaystyle x_ {1} ^ {d_ {1}} x_ {2} ^ {d_ {2}} tečky x_ {n} ^ {d_ {n}}}$ stupně přesně ${ displaystyle q-2}$. Existují přesně ${ displaystyle {q + n-3 vyberte n-1}}$ takové monomily. Existuje tedy nenulová hodnota homogenní polynom ${ displaystyle P (x_ {1}, x_ {2}, tečky, x_ {n})}$ stupně ${ displaystyle q-2}$ který zmizí ve všech bodech ${ displaystyle K}$. Všimněte si to proto, že nalezení takového polynomu se redukuje na řešení systému ${ displaystyle | K |}$ lineární rovnice pro koeficienty.

Nyní použijeme vlastnost, která ${ displaystyle K}$ je Kakeya, který to má ukázat ${ displaystyle P}$ musí zmizet na všech ${ displaystyle mathbb {F} _ {q} ^ {n}}$. Jasně ${ displaystyle P (0,0 tečky, 0) = 0}$. Dále pro ${ displaystyle y neq 0}$, tady je ${ displaystyle x}$ takové, že linka ${ displaystyle {x + ty, t in mathbb {F} _ {q} }}$ je obsažen v ${ displaystyle K}$. Od té doby ${ displaystyle P}$ je homogenní, pokud ${ displaystyle P (z) = 0}$ pro některé ${ displaystyle z in mathbb {F} _ {q} ^ {n}}$ pak ${ displaystyle P (cz) = 0}$ pro všechny ${ displaystyle c in mathbb {F} _ {q}}$. Zejména

${ displaystyle P (tx + y) = P (t (x + t ^ {- 1} y)) = 0}$

pro všechny nenulové ${ displaystyle t in mathbb {F} _ {q}}$. Nicméně, ${ displaystyle P (tx + y)}$ je polynom stupně ${ displaystyle q-2}$ v ${ displaystyle t}$ ale má alespoň ${ displaystyle q-1}$ kořeny odpovídající nenulovým prvkům ${ displaystyle mathbb {F} _ {q}}$ takže to musí být shodně nula. Zejména připojení ${ displaystyle t = 0}$ odvodíme ${ displaystyle P (y) = 0}$.

Ukázali jsme to ${ displaystyle P (y) = 0}$ pro všechny ${ displaystyle y in mathbb {F} _ {q} ^ {n}}$ ale ${ displaystyle P}$ má stupeň menší než ${ displaystyle q-1}$ v každé z proměnných, takže to je nemožné Schwartz – Zippelovo lemma. Dedukujeme, že to vlastně musíme mít

${ displaystyle | K | geq {q + n-3 zvolit n-1} sim { frac {q ^ {n-1}} {(n-1)!}}}$

Polynomiální rozdělení

Variaci polynomiální metody, často nazývaná polynomiální rozdělení, zavedli Guth a Katz ve svém řešení Erdőův problém se značnými vzdálenostmi^[4]. Polynomiální rozdělení zahrnuje použití polynomů k rozdělení podkladového prostoru do oblastí a dohadování se o geometrické struktuře oddílu. Tyto argumenty se spoléhají na výsledky z algebraické geometrie ohraničující počet výskytů mezi různými algebraickými křivkami. Technika polynomiálního dělení byla použita k poskytnutí nového důkazu Szemerédi – Trotterova věta přes polynomiální šunková sendvičová věta a byl aplikován na řadu problémů v geometrii dopadu^[5][6].

Aplikace

Několik příkladů dlouhodobých otevřených problémů, které byly vyřešeny pomocí polynomiální metody, jsou:

• The Kakeya domněnka konečného pole^[3] podle Dvir
• The sada čepic problém Ellenberga a Gijswijta^[7] s původním rámcem vyvinutým na analogickém problému ${ displaystyle mathbb {Z} _ {4} ^ {n}}$ Croot, Lev a Pach^[8]

• The Erdőův problém se značnými vzdálenostmi Guth a Katz^[4]
• Problém kloubů ve 3D od Guth a Katz^[9]. Jejich argumenty později zjednodušili Elekes, Kaplan a Sharir^[10]

Viz také

• Kombinatorický Nullstellensatz

Reference

Externí odkazy

• Průzkum polynomiální metody Terence Tao
• Průzkum polynomiální metody Larry Guth