Przeskocz do treści

Delta mi!

Loading

Combinatorial Nullstellensatz w teorii liczb

Jacek Dymel

o artykule ...

  • Publikacja w Delcie: wrzesień 2017
  • Publikacja elektroniczna: 1 września 2017
  • Autor: Jacek Dymel
    Afiliacja: Nauczyciel, V Liceum Ogólnokształcące im. Augusta Witkowskiego w Krakowie
  • Wersja do druku [application/pdf]: (83 KB)

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.

obrazek

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

i jest różny od 0 w | Zp, gdyż | 2 A Ponieważ zbiór | A ma moc większą niż wykładnik |x oraz | B = A to z Combinatorial Nullstellensatz wynika, że istnieją takie elementy a ∈A, że | f(a,b) ≠ 0. Otrzymaliśmy sprzeczność z własnością  f (a,b) = 0 dla dowolnych | 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.

obrazek

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ł.



Do czytania

Czytelnikom, którzy nawet teraz odczuwają niedosyt Combinatorial Nullstellensatz, polecam lekturę pozycji wymienionych poniżej:

[1]
T. Andreescu, G. Dospinescu, Problems from the book. XYZ Press, 2008.
[2]
T. Bartnicki, Combinatorial nullstellensatz, czyli o algebrze w kombinatoryce, Matematyka Społeczeństwo Nauczanie, nr 38 (2007), str. 14-18.