Combinatorial Nullstellensatz

[mol_ksiazkowy]

Rozwiązać elementarnie zadanie(bez CN):


Zadanie*
Każdemu wierzchołkowi \(\displaystyle{ 2n}\) kąta przypisano dwie różne liczby. Udowodnić, że można z każdego wierzchołka usunąć po jednej liczbie w taki sposób, aby pozostałe liczby w każdych dwóch sąsiednich wierzchołkach były różne.

Rozwiązanie:
Niech zbiór \(\displaystyle{ S_i}\) to zbiór liczb na \(\displaystyle{ i}\) tym wierzchołku. Niech \(\displaystyle{ P(x_1,..., x_{2n}) = (x_1-x_2)(x_2-x_3)...(x_{2n-1} - x_{2n})(x_{2n} - x_{1})}\) to wielomian
stopnia \(\displaystyle{ 2n}\) bo współczynnik przy składniku \(\displaystyle{ x_1...x_{2n}}\) jest równy \(\displaystyle{ 2}\). Z Combinatorial Nullstellensatz: istnieje \(\displaystyle{ (a_1, ..., a_{2n}) \in S_1 \times ... \times S_{2n}}\) takie, że \(\displaystyle{ P(a_1,..., a_{2n}) \neq 0}\) czyli \(\displaystyle{ a_1 \neq a_2 , \ ... \ a_{2n} \neq a_1}\) koniec dowodu.


Combinatorial Nullstellensatz:
Jeśli \(\displaystyle{ F}\) jest ciałem oraz \(\displaystyle{ P \in F[x_1,...,x_n]}\) jest niezerowym wielomianem stopnia \(\displaystyle{ \sum_{j=1}^n m_j}\) a współczynnik przy \(\displaystyle{ x_1^{m_1}...x_n^{m_n}}\) jest
różny od zera, to dla dowolnych zbiorów \(\displaystyle{ S_1,...,S_n \subset F}\) takich , że \(\displaystyle{ |S_j| > m_j}\) dla \(\displaystyle{ 1 \leq j \leq n}\) istnieją \(\displaystyle{ c_j \in S_j}\) takie, że \(\displaystyle{ P(c_1,...,c_n) \neq 0}\)

Jest to jest uogólnienie twierdzenia, że wielomian jednej zmiennej stopnia \(\displaystyle{ n}\) o współczynnikach rzeczywistych ma niw więcej niż \(\displaystyle{ n}\) pierwiastków.
Typowym zastosowaniem Combinatorial Nullstellensatz jest dowód twierdzenia Erdősa-Ginzburga-Ziva.
Stosowany jest także w geometrii; przy odpowiedniej interpetacji algebraicznej.

por:
... ellensatz/

* Dla \(\displaystyle{ n}\) nieparzystych oczywiście fałszywe: wystarczy każdemu wierzchołkowi przypisać liczby \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\).