Metoda wielomianowa w kombinatoryce

W matematyce metoda wielomianów jest algebraicznym podejściem do problemów kombinatorycznych , które obejmuje uchwycenie pewnej struktury kombinatorycznej za pomocą wielomianów i przystąpienie do sporu o ich właściwości algebraiczne. Ostatnio metoda wielomianowa doprowadziła do opracowania niezwykle prostych rozwiązań kilku długotrwałych otwartych problemów. Metoda wielomianowa obejmuje szeroki zakres konkretnych technik wykorzystywania wielomianów i pomysłów z obszarów takich jak geometria algebraiczna do rozwiązywania problemów kombinatorycznych. Podczas gdy kilka technik jest zgodnych z ramami metody wielomianowej, takich jak Alon Combinatorial Nullstellensatz , były znane od lat 90. XX wieku, dopiero około 2010 roku opracowano szersze ramy dla metody wielomianowej.

Przegląd matematyczny

Wiele zastosowań metody wielomianowej opiera się na tym samym podejściu wysokiego poziomu. Podejście jest następujące:

• Osadź problem kombinatoryczny w przestrzeni wektorowej.
• Uchwyć hipotezy problemu, konstruując wielomian niskiego stopnia, który jest równy zeru na pewnym zbiorze
• Po skonstruowaniu wielomianu spieraj się o jego właściwości algebraiczne, aby wywnioskować, że pierwotna konfiguracja musi spełniać pożądane właściwości.

Przykład

Jako przykład przedstawiamy dowód Dvira hipotezy Kakeyi pola skończonego przy użyciu metody wielomianowej.

$.$$polu$ skończonym : Niech będzie polem skończonym z elementami Niech ${\ Displaystyle K \ subseteq \ mathbb {F} _ {q} ^ {n}}$ będzie zbiorem Kakeya, tj. dla każdego wektora ${\ Displaystyle y \ in \ mathbb {F } _ {q} ^ {n}}$ istnieje ${\ Displaystyle x \ in \ mathbb {F} _ {q} ^ {n}}$ takie, że ${\ Displaystyle K}$ zawiera linię ${\ Displaystyle \ {x + ty, t \ in \ mathbb {F} _ {q} \}}$ . $n}> 0$ zbiór ma rozmiar co najmniej $c_ {n} q ^ {n}}$$displaystyle$ gdzie jest stałą, która zależy tylko do na ${\ displaystyle n}$ .

Dowód: podany przez nas $\ displaystyle c_ {n} q ^ {n-1}$ pokaże, że ma rozmiar co najmniej do $}$ . Granicę można uzyskać tą samą metodą $.$

$,$ że mamy zestaw z

${\ Displaystyle | K | < {q + n-3 \ wybierz n-1}}$

Rozważmy zbiór jednomianów postaci ${\ Displaystyle x_ {1} ^ {d_ {1}} x_ {2} ^ {d_ {2}} \ kropki x_ { n} ^ {d_ {n}}}$ stopnia dokładnie ${\ Displaystyle q-2}$ . Są dokładnie takie jednomiany ${\ Displaystyle {q + n-3 \ wybierz n-1}} .$ Zatem istnieje niezerowy jednorodny wielomian ${\ Displaystyle P (x_ {1}, x_ {2}, \ kropki, x_ {n})}$ stopnia ${\ Displaystyle q-2},$ że znika we wszystkich punktach w ${\ displaystyle K}$ . Zauważ, że dzieje się tak, ponieważ znalezienie takiego wielomianu sprowadza się do rozwiązania układu ${\ displaystyle | K|}$ równania liniowe dla współczynników.

$zbiorem$ użyjemy właściwości, że $. }$$Kakeya,$ aby pokazać, że wszystkich . Oczywiście ${\ Displaystyle P (0,0 \ kropki, 0) = 0}$ . Następnie dla ${\ Displaystyle y \ neq 0}$ istnieje , że linia $}$${\ Displaystyle \ {x + ty, t \ w \ mathbb {F} _ {q} \}}$ jest zawarte w ${\ Displaystyle K}$ . Ponieważ ${\ Displaystyle P}$ jest jednorodny, jeśli dla pewnego ${\ Displaystyle P (z) = 0}$${\ Displaystyle Z \ in \ mathbb {F} _ {q} ^ { n}}$ następnie ${\ Displaystyle P (cz) = 0}$ dla dowolnego ${\ Displaystyle c \ in \ mathbb {F} _ {q}}$ . W szczególności

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

dla wszystkich niezerowych ${\ displaystyle t \ in \ mathbb {F} _ {q}}$ . Jednak $+ y)}$${ \ displaystyle q-1}$ jest wielomianem stopnia $\$ t $t}$ , ale ma co najmniej pierwiastki odpowiadające niezerowym elementom ${\ displaystyle \ mathbb {F} _ {q}}$ więc musi być identycznie zerem. W szczególności, podłączając, wnioskujemy, że $= {\ displaystyle t = 0}$$= 0} t$ .

Pokazaliśmy, że ${\ Displaystyle P (y) = 0}$ dla wszystkich ${\ Displaystyle y \ in \ mathbb {F} _ {q} ^ {n}}$ ale ${\ displaystyle P}$ ma stopień mniejszy niż w $lematu$ ze zmiennych, więc jest to niemożliwe na mocy – Zippela Wnioskujemy, że faktycznie musimy mieć

${\ Displaystyle | K | \ geq {q + n-3 \ wybierz n-1} \ sim {\ Frac {q ^ {n-1}} {(n-1)!}}}$

Podział wielomianowy

Odmiana metody wielomianowej, często nazywana dzieleniem wielomianowym, została wprowadzona przez Gutha i Katza w ich rozwiązaniu problemu różnych odległości Erdősa . Podział wielomianowy polega na użyciu wielomianów do podzielenia podstawowej przestrzeni na regiony i sporze o geometryczną strukturę podziału. Argumenty te opierają się na wynikach geometrii algebraicznej ograniczającej liczbę przypadków między różnymi krzywymi algebraicznymi. Technika dzielenia wielomianów została wykorzystana do dostarczenia nowego dowodu twierdzenia Szemerédiego – Trottera za pomocą wielomianowego twierdzenia o kanapce z szynką i został zastosowany do różnych problemów w geometrii padania.

Aplikacje

Kilka przykładów długotrwałych otwartych problemów, które zostały rozwiązane metodą wielomianową, to:

• Hipoteza Kakeya o skończonym polu autorstwa Dvira
• Problem zestawu czapek autorstwa Ellenberga i $Gijswijta$ z oryginalną strukturą opracowaną na podstawie analogicznego problemu Croot, Lev i
• Problem różnych odległości Erdősa autorstwa Gutha i Katza
• Problem stawów w 3D autorstwa Gutha i Katza. Ich argument został później uproszczony przez Elekesa, Kaplana i Sharira

Zobacz też

• Kombinatoryczny Nullstellensatz

Linki zewnętrzne

• Ankieta dotycząca metody wielomianowej przeprowadzona przez Terence'a Tao
• Ankieta dotycząca metody wielomianowej przeprowadzona przez Larry'ego Gutha