O zastosowaniach Combinatorial Nullstellensatz

Zadanie 6 z 48. Międzynarodowej Olimpiady Matematycznej (IMO) z 2007 roku było jednym z najtrudniejszych w historii Międzynarodowej Olimpiady Matematycznej.

Oto treść zadania.

Zadanie. Niech $|n$ będzie dodatnią liczbą naturalną. Przyjmijmy, że

S = {(x,y,z) x,y,z ∈{0, 1,...,n},x + y +z > 0}

jest zbiorem $(n + 1)3 − 1$ punktów w przestrzeni trójwymiarowej. Wyznacz najmniejszą możliwą liczbę płaszczyzn, których suma mnogościowa zawiera $S,$ ale do której nie należy $(0,0,0).$

Zadanie rozwiązało tylko pięciu zawodników: Konstantin Matwiejew z Rosji, Peter Scholze z Niemiec, Danylo Radczenko z Ukrainy, Iurie Boreico z Mołdawii i Pietro Verteci z Włoch. W zasadzie tylko znajomość twierdzenia Combinatorial Nullstellensatz (kombinatoryczne twierdzenie o rozmieszczeniu zer, nawiązujące do twierdzenia Hilberta o zerach), któremu poświęcony jest ten artykuł, umożliwiała szybkie rozwiązanie zadania. Noga Alon opublikował swój artykuł Combinatorial Nullstellensatz [1] w 1999 roku, a już w 2007 roku kilku uczestników IMO stosowało metodę w nim opisaną. Wspomniane twierdzenie jest naturalnym uogólnieniem dobrze znanego uczniom twierdzenia, że wielomian jednej zmiennej stopnia $|n$ o współczynnikach rzeczywistych ma co najwyżej $n$ pierwiastków rzeczywistych, a jego treść jest następująca:

Dowód. Przeprowadzimy indukcję ze względu na stopień wielomianu $|P.$ Nietrudny dowód początku indukcji $(degP = 1)$ pozostawiam Czytelnikowi Spragnionemu Ćwiczeń jako ćwiczenie.

Załóżmy teraz, że $k > 1,$ oraz że teza zachodzi dla wszystkich wielomianów stopnia niższego niż $k.$ Niech wielomian $P$ ma stopień $k.$ Bez straty ogólności można przyjąć, że $|m1$ Wybierzmy $|a∈ S1.$ Podobnie, jak w przypadku wielomianów jednej zmiennej, możemy podzielić wielomian $|P$ przez wielomian $(x1− a),$ otrzymując

P (x1,...,xn) = (x1− a)Q(x1,

gdzie $R(x2, ...,xn) = P(a, x2,...,xn)$ jest wielomianem $n − 1$ zmiennych, natomiast $Q$ musi zawierać nieznikający jednomian postaci $xm1 |1 xm22⋯ xmnn$ oraz $|degQ$ Dla dowodu nie wprost załóżmy, że wielomian $P$ nie spełnia tezy. Wówczas dla dowolnych $a ∈ S,...,a ∈S 2 2 n n$ zachodzi równość $P (a,a2,...,an) = 0,$ co oznacza, że także $R(a2, ...,an) = 0.$

Wybierzmy teraz dowolnie $|a ∈S ∖{a}. 1 1$ Otrzymujemy równości:

0 = P(a1,...,an) = (a1 − a)Q(a1,

Ponieważ $(a1 −a) ≠ 0$ oraz $R(a2,...,an) = 0,$ więc $|Q(a1,$ Wielomian $|Q$ ma stopień $k | − 1$ i niezerowy współczynnik przy $xm1 xm2⋯ xmn 1 2 n$ oraz przyjmuje wartość zero dla wszystkich $a1 ∈S1 ∖{a}, a2∈ S2,...,$ $an ∈Sn,$ co jest sprzeczne z założeniem indukcyjnym. Uzyskana sprzeczność kończy dowód indukcyjny.

Poniżej przedstawię zastosowania Combinatorial Nullstellensatz do zadań olimpijskich, aby w końcu pokazać rozwiązanie zadania z IMO z 2007 roku, które było pretekstem do opowiedzenia o tej metodzie.

Zadanie (Rosja 2007). W każdy wierzchołek wypukłego $|2n$ -kąta wpisano dwie różne liczby rzeczywiste. Udowodnić, że można z każdego wierzchołka usunąć po jednej liczbie w taki sposób, aby liczby w każdych dwóch sąsiednich wierzchołkach były różne.

Dowód. Niech $S (i = 1,...,2n) i$ będzie dwuelementowym zbiorem liczb wpisanych w $i$ -ty wierzchołek. Określmy wielomian $|P(x1,...,xn) == (x1− x2)(x2 −x3)⋯ (x2n− x1).$ Wielomian $|P$ jest stopnia $2n,$ współczynnik przy wyrażeniu $x1⋯ x2n,$ które jest stopnia $2n,$ jest równy $|2.$ Na podstawie Combinatorial Nullstellensatz istnieją $|a1∈ S1,$ $|a2∈ S2,...,$ $a2n∈ S2n,$ takie że $P (a1,...,a2n) ≠ 0.$ To oznacza, że każda z różnic: $(a1− a2),(a2− a3),...$ , $|(a2n− a1)$ jest różna od 0, czyli istnieje taki wybór liczb ze zbiorów $|S1,...,S2n,$ że $|a ≠ a ,a ≠ a ,...,a ≠ a . 1 2 2 3 2n 1$

Zadanie (5th NIMO Winter Contest 2014). Zdefiniujmy taką funkcję $|ξ Z2 Z,$ że $|ξ(n,k) = 1,$ gdy $n ⩽ k$ oraz $ξ(n,k) = −1,$ gdy $|n > k$ i zdefiniujmy wielomian

10001000 P (x1,...,x1000) = M ( Q ξ(n,k)xk). n 1 k 1

Wyznacz współczynnik przy $|x1⋯x1000$ w wielomianie $|P.$

Rozwiązanie. Zauważmy, że wielomian $P$ jest stopnia $|1000.$ Załóżmy, że współczynnik przy $|x1x2⋯ x1000$ jest różny od $|0.$ Zdefiniujmy zbiory $S1 = S2 =⋅⋅⋅= S1000 = {− 1,1}.$ Wówczas korzystając z Combinatorial Nullstellensatz, otrzymujemy takie elementy $|c ∈S , i i$ gdzie $|i∈{1,...,1000},$ że $P (c,...,c )≠ 0. 1 1000$ Z drugiej strony sumy częściowe $C1$ definiują pewien "spacer po liczbach całkowitych", kończący się na $|C$ Liczba $|C$ musi być parzysta, dlatego spacer ten w pewnym momencie osiągnie $C/2,$ zatem dla pewnego $|k⩽ 1000$ zachodzi $Ck$ Oznacza to jednak, że $k$ -ty czynnik w definicji wielomianu $P$ wynosi 0, co przeczy stwierdzeniu $|P(c1,...,c1000) ≠0.$ Zatem współczynnik przy $x1x2⋯ x1000$ musi być równy $0.$

Przejdziemy teraz do rozwiązania przytoczonego na początku artykułu zadania 6 z IMO 2007, które jest trudniejsze niż poprzednie zadania.

Rozwiązanie (Danylo Radczenko). Niech $k ∈N+$ i $k < 3n.$ Weźmy $|k$ parami różnych płaszczyzn, których suma mnogościowa zawiera zbiór $|S$ i żadna z tych płaszczyzn nie przechodzi przez punkt $(0,0,0).$ Niech $|i$ -ta płaszczyzna będzie określona równaniem $aix + biy + ciz = di,$ gdzie $|a2i + b2i + c2i≠ 0$ oraz $di ≠0.$ Rozważmy wielomian $P$ postaci

k n P(x,y,z) = M (aix + biy +ciz− di)− α M (x − j)(y − j)(z− j), i 1 j 1

gdzie $α$ jest tak dobrane, że $|P(0,0,0) = 0.$ Wielomian $|P(x,y,z)$ przyjmuje wartość 0 dla każdego elementu należącego do zbioru $|S.$ Dla $|k < 3n$ współczynnik przy $n n n |x y z$ nie jest równy $0,$ gdyż jest równy $|α≠ 0.$ Dla zbiorów $S1 = S2 = S3 == {0,1,...,n}$ zachodzą warunki: $S1 > n,$ $| S2 > n, S3 > n,$ więc na podstawie Combinatorial Nullstellensatz istnieje taki punkt $|(a,b,c)∈ {0,1,...,n}3,$ że $|P(a,b,c) ≠ 0.$ Zatem istnieje punkt $|(a,b,c)∈ S,$ dla którego $P(a, b,c)≠ 0.$ Otrzymaliśmy sprzeczność. Wobec tego $|k ⩾3n.$

Wystarczy jeszcze wskazać przykład $3n$ płaszczyzn, które spełniają warunki zadania. Są nimi

x = 1,x = 2,...,x = n,y = 1,y = 2,...,y = n,z = 1,z = 2,...,z = n. ◻

Powyższe zadanie jest pewną wariacją na temat problemu, jaki postawił Peter Komjáth: ile potrzeba hiperpłaszczyzn, aby pokryć wszystkie, z wyjątkiem jednego, wierzchołki kostki jednostkowej w przestrzeni $|n$ -wymiarowej. Rozwiązanie tego problemu pojawiło się przed 1993 rokiem, ale dopiero Noga Alon i Zoltan Füredi w 1993 roku w pracy [2] przedstawili krótkie i eleganckie rozumowanie. Poniższy dowód pochodzi z pracy [1].

Twierdzenie. Niech $|H1,$ będzie rodziną hiperpłaszczyzn w $Rn,$ których suma zawiera wszystkie, z wyjątkiem jednego, wierzchołki kostki jednostkowej, czyli zbiór $|{0,1}n.$ Wówczas $|m$

Dowód. Bez straty ogólności możemy przyjąć, że usuniętym wierzchołkiem jest punkt $(0,...,0).$ Niech hiperpłaszczyzna $Hi$ dana będzie równaniem $⟨ai,x⟩= bi,$ gdzie $x = (x1,...,xn)$ i $⟨a, b⟩$ jest standardowym iloczynem skalarnym $|a$ i $b.$ Dla każdego $|i∈{1,...,m}$ zachodzi warunek $|bi≠ 0,$ gdyż żadna z hiperpłaszczyzn nie przechodzi przez punkt $|(0,...,0).$ Załóżmy dla dowodu nie wprost, że $|m$ i zdefiniujmy wielomian

m n m P (x) = (−1)n+m+1M b jM (xi− 1)+ M (⟨ ai,x⟩ − bi). j 1 i 1 i 1

Wielomian $|P$ ma stopień $n$ i współczynnik przy $x1⋯ xn$ równy

m (−1)n+m+1M b j, j 1

zatem różny od 0. Na podstawie Combinatorial Nullstellensatz dla $|m1$ oraz $|S1 = ... = Sn = {0,1},$ istnieje taki punkt $|c∈ {0,1}n,$ że $P (c)≠ 0.$ Punkt $|c$ jest różny od $|(0,...,0),$ gdyż wielomian $|P$ przyjmuje wartość 0 dla $x = (0,...,0),$ a zatem punkt $|c$ należy do zadanego zbioru i nie należy do żadnej z hiperpłaszczyzn. Otrzymaliśmy sprzeczność, wobec tego $m$ Teraz wystarczy wskazać $|n$ hiperpłaszczyzn spełniających warunki zadania; są one zadane równaniami $x1 = 1,...,xn = 1.$

Mam nadzieję, że powyższe przykłady przekonały Cię, Drogi Czytelniku, o użyteczności Combinatorial Nullstellensatz w rozwiązywaniu problemów z pozoru z nim niezwiązanych. Na zakończenie chciałbym zauważyć, że to wspaniałe twierdzenie jest słuszne dla wielomianów o współczynnikach z dowolnego ciała. Dotychczas używaliśmy jedynie ciała liczb rzeczywistych. Drugim w kolejności naturalnym wyborem ciała jest ciało $|Zp$ - ciało reszt z dzielenia przez liczbę pierwszą $p$ z dodawaniem i mnożeniem modulo $|p.$ Zastosowanie Combinatorial Nullstellensatz w tej sytuacji prowadzi do niezwykle eleganckich dowodów bardzo pięknych twierdzeń z teorii liczb. Niestety, w tym artykule brakuje już miejsca na przedstawienie przykładów, obiecuję jednak zaprezentować je w numerze wrześniowym w nadziei, że oczekiwanie zaostrzy apetyt nie tylko Czytelnika Bardzo Zainteresowanego.