Combinatorial Nullstellensatz w teorii liczb

W Delcie 7/2017 przedstawiliśmy kilka "olimpijskich" zastosowań twierdzenia Combinatorial Nullstellensatz. Okazuje się, że zamiast "zwykłych" wielomianów wielu zmiennych możemy rozważać wielomiany o współczynnikach będących resztami z dzielenia przez pewną liczbę pierwszą $|p;$ z dodawaniem i mnożeniem modulo $p:$ Poniżej przedstawimy trzy klasyczne twierdzenia, których proste dowody są oparte na Combinatorial Nullstellensatz w wersji "resztowej". Twierdzenia te są szczególnie bliskie zastosowaniom olimpijskim.

Twierdzenie Combinatorial Nullstellensatz można sformułować następująco:

Twierdzenie 5 (Combinatorial Nullstellensatz). Niech $|P(x1,x2,...,xn)$ będzie niezerowym wielomianem $|n$ zmiennych stopnia $n |Pi 1mi,$ w którym współczynnik przy $m m x11 ...xnn$ jest różny od zera. Wówczas dla dowolnych zbiorów $S1,...,Sn ⊂ R$ spełniających warunki $| S > m i i$ dla $1⩽ i ⩽n,$ istnieją takie $|c ∈S , i i$ że $|P(c ,...,c ) ≠ 0. 1 n$

Okazuje się, że zamiast "zwykłych" wielomianów wielu zmiennych możemy rozważać wielomiany o współczynnikach będących resztami z dzielenia przez pewną liczbę pierwszą $p,$ z dodawaniem i mnożeniem modulo $|p.$ Zbiór tych reszt wraz z tak określonymi operacjami oznaczać będziemy jako $Zp.$ Dla $p = 5$ będziemy zatem mieli, na przykład,

$3⋅4 = 2, (3xy +4x2) + 2xy = −x2, (3x + y)(3x − y) =− x2− y2.$

Poniżej przedstawimy trzy klasyczne twierdzenia, których proste dowody są oparte na Combinatorial Nullstellensatz w wersji "resztowej". Twierdzenia te są szczególnie bliskie zastosowaniom olimpijskim.

Twierdzenie 6 (Cauchy'ego-Davenporta). Dla dowolnej liczby pierwszej $|p$ i dowolnych zbiorów $|A,$ zachodzi nierówność

A

gdzie $A$

Dowód. Przyjmijmy najpierw, że $| A$ Niech $c$ będzie dowolnym elementem zbioru $Zp.$ Zdefiniujmy dla elementu $|c$ zbiór $={c−b b∈B}.C$ Zbiór $C$ jest równoliczny ze zbiorem $B,$ zatem $| A$ To oznacza, że istnieje element wspólny zbiorów $A$ i $. C |$ Niech elementem wspólnym będzie $|a0∈ A$ oraz $. c | − b0∈ C$ Wówczas $|a0 = c− b0,$ czyli $a0 + b0 = c.$ Wobec dowolności wyboru $c$ otrzymujemy, że $A$

Załóżmy teraz, że $A$ Dla dowodu nie wprost przypuśćmy, że $| A$ Wówczas w $Zp$ istnieje zbiór $⊃A+ C$ spełniający warunek $= A+ C$ Rozważmy wielomian

f (x,y) = M (x +y − c) c> C

o współczynnikach z $|Zp.$ Jego stopień jest równy $A$ a współczynnik przy $SAS− 1 SBS−1 x y$ jest przystający do $SAS+SBS− 2 |( SSA−1 )$ modulo $p.$ To wyrażenie nie jest podzielne przez $p,$ ponieważ $A$ jest zatem (modulo $|p$ ) różne od 0. Na podstawie Combinatorial Nullstellensatz istnieją takie elementy $|a∈ A,$ że $| f(a,b) ≠ 0.$ To jest niemożliwe, gdyż $A$ Zatem $| A$

Twierdzenie 7 (Erdősa-Heilbronna). Dla dowolnej liczby pierwszej $p$ i dla dowolnego zbioru $|A$ zachodzi nierówność:

A

gdzie $A$

Dowód. Dla $p = 2$ twierdzenie jest oczywiste. Załóżmy więc, że $|p⩾ 2.$ Niech $2 A$ Wykażemy, że $A$ Wybierzmy dowolny element $m∈Zp.$ Rozbijmy zbiór $Zp$ na pary elementów, których suma w $Zp$ jest równa $m.$ Otrzymujemy $p−1 2$ par oraz jeden element, który tworzy parę sam ze sobą. Wobec założenia $A$ na podstawie zasady Dirichleta, do zbioru $A$ należą dwa różne elementy jednej z par, a więc $m∈A$ co należało dowieść. Niech teraz $|2 A$ Wybierzmy dowolny element $a ∈ A$ i zdefiniujmy $|B = A/{a}.$ Łatwo zauważyć, że $A |$ Potrzeba jeszcze pokazać, że $A$ Wykażemy, że w tym przypadku $A$ Dla dowodu nie wprost przyjmiemy, że istnieje taki podzbiór $⊂Z, |C p$ że $=2 A4 C$ oraz $|A$ Rozważmy wielomian

f(x,y) = (x −y) M (x + y −c) c>C

o współczynnikach z $|Z . p$ Jest to wielomian stopnia $2 A$ a współczynnik przy $SAS− 1 SAS−2 x y$ jest równy

(2 A )− (2 A ) = ----(2 A--------- A A ( A

Twierdzenie 8 (Erdősa-Ginzburga-Ziva). Niech $|n∈ N+.$ Wówczas wśród dowolnych $2n − 1$ liczb całkowitych można wybrać $|n$ liczb, których suma jest podzielna przez $n.$

Dowód. Najpierw wykażemy, że twierdzenie jest prawdziwe, jeśli $|n$ jest liczbą pierwszą; zgodnie z notacyjną tradycją przyjmijmy oznaczenie $|p = n.$ Niech $a ,...,a 1 2p−1$ będą danymi liczbami całkowitymi. Bez straty ogólności można założyć, że $0 ⩽a1 ⩽⋅⋅⋅⩽ a2p−1⩽ p− 1,$ gdyż możemy rozważyć tylko reszty z dzielenia liczb $a1,...,a2p−1$ przez $n.$ Rozważmy dwa przypadki.

Przypadek 1. Jeżeli $ai+p−1 = ai$ dla pewnego $|i∈ {1,...,p},$ to twierdzenie jest oczywiste: wybieramy liczby $ai = ai+1 = ⋅⋅⋅= ai+p−1,$ których suma jest podzielna przez $|p.$

Przypadek 2. Niech $|ai+p− 1 > ai$ dla dowolnej liczby $|i∈ {1,...,p}.$ W tym przypadku rozważmy dwuelementowe zbiory

S1 = {a1,ap}, S2 = {a2,ap+1},...,Sp−1 = {ap −1,a2p−2}

oraz zbiór jednoelementowy $|S = {a }. p 2p−1$ Zdefiniujmy wielomian

p− 1 P (x1,...,xp) = (x1 + ...+ xp) −1.

Wielomian $|P$ jest stopnia $|p− 1$ i współczynnik przy jednomianie $|x1⋅...⋅xp−1$ jest równy $|(p− 1)!.$ Nie jest on równy $0,$ gdyż na podstawie twierdzenia Wilsona $(p −1)!≡ −1 (mod p).$ Na podstawie Combinatorial Nullstellensatz istnieje taki element $(s1,s2,...,sp)∈ S1× S2× ⋅⋅⋅×Sp,$ że $|P(s1,...,sp)≠ 0.$ Gdyby suma $s = s1 +...+ sp$ nie była podzielna przez $|p,$ to na podstawie Małego Twierdzenia Fermata $p$ byłoby dzielnikiem $|sp−1− 1,$ co nie jest prawdą, gdyż $P (s1,...,sp)≠ 0.$ Wobec tego suma $|s = s1 +s2 +...+ sp$ jest podzielna przez $|p.$

Teraz wykażemy, że twierdzenie jest prawdziwe dla dowolnej dodatniej liczby naturalnej $n.$ Każda liczba naturalna $n$ ma jednoznaczny rozkład, z dokładnością do kolejności, na iloczyn liczb pierwszych. Udowodniliśmy twierdzenie dla każdej liczby pierwszej. Zatem wystarczy wykazać, że twierdzenie jest prawdziwe dla dowolnego iloczynu liczb pierwszych. Wobec tego wystarczy wykazać, że jeżeli twierdzenie jest prawdziwe dla dwóch liczb naturalnych $|a$ i $b,$ to jest prawdziwe dla ich iloczynu $|ab.$

Załóżmy, że twierdzenie jest prawdziwe dla dwóch dodatnich liczb naturalnych $a$ i $b.$ Wykażemy, że jest także prawdziwe dla ich iloczynu $|ab.$ Spośród $2ab − 1$ liczb wybierzmy $|2a −1$ liczb. Spośród nich można wybrać $a$ liczb, których suma jest podzielna przez $a.$ Zatem pozostaje $|2ab −1 −a$ liczb. Ponownie wybierzmy $|2a− 1$ spośród nich. Wśród nich jest $|a$ liczb, których suma jest podzielna przez $a.$ Pozostaje $|2ab− 1− 2a$ liczb. Postępujemy analogicznie $2b − 1$ razy. Otrzymujemy w ten sposób $2b − 1$ zbiorów, z których każdy zawiera $|a$ elementów, a suma tych elementów w każdym z tych zbiorów jest podzielna przez $|a.$ Potraktujmy sumę wybranych elementów każdego z tych zbiorów jako jedną liczbę i podzielmy ją przez $a.$ Otrzymujemy $2b − 1$ liczb, spośród których możemy wybrać $b$ liczb, których suma jest podzielna przez $b.$ Zatem uzyskaliśmy $|ab$ liczb, których suma jest podzielna przez $ab,$ co kończy dowód twierdzenia, jak również cały artykuł.