Znane wszystkim Małe Twierdzenie Fermata mówi o rozwiązaniach (mod ), a teoria reszt kwadratowych o  (mod ). Teoria liczb jest nie tylko piękną sztuką, ale także łączy się z innymi działami nauki, między innymi z kryptografią, topologią czy geometrią algebraiczną. W tym artykule chciałbym zaprezentować przykład zastosowania równań diofantycznych w teorii grafów.

Musimy zacząć od ustalenia kilku ważnych oznaczeń. Jak zwykle  to zbiór liczb całkowitych. Przez  oznaczać będziemy zbiór wszystkich reszt z dzielenia przez  a przez  zbiór wielomianów o zmiennych  i o współczynnikach całkowitych.

Mówimy, że -tka liczb całkowitych  jest rozwiązaniem modulo  wielomianu  jeżeli (mod ). Na przykład, para  jest rozwiązaniem modulo  wielomianu

Rozwiązanie  modulo  nazywamy istotnym, jeśli jego współrzędne są liczbami z przedziału od 0 do (czyli  dla ). W powyższym przykładzie rozwiązanie  jest istotne, zaś  już nie. Z własności kongruencji wiemy, że jeżeli  jest rozwiązaniem, to  jest rozwiązaniem istotnym. Ponadto, żeby znaleźć wszystkie rozwiązania modulo  danego równania, wystarczy znać rozwiązania istotne.

Stopniem jednomianu nazywamy sumę wykładników jego czynników, czyli, na przykład,  ma stopień 4. Stopniem wielomianu (oznaczamy go ) nazywamy najwyższy spośród stopni jego jednomianów; wobec tego dla  mamy

Będziemy wykorzystywać następującą nieoczywistą zależność (której dowód Czytelnik Wnikliwy z pewnością spróbuje znaleźć sam):

(1)

Teraz możemy już zaprezentować tytułowe twierdzenie.

Zanim zobaczymy dowód twierdzenia, warto przyjrzeć się kilku przykładom i wnioskom. Twierdzenie Chevalleya–Warninga jest ważnym narzędziem w badaniu rozwiązalności równań diofantycznych.

Rozpatrzmy, na przykład, równanie  Jego stopień jest równy dwa, a są trzy zmienne. Zatem z powyższego twierdzenia liczba rozwiązań istotnych jest podzielna przez  Ten wielomian ma trywialne rozwiązanie  i   więc musi istnieć także pewne rozwiązanie nietrywialne, tzn. takie, które ma przynajmniej jedną współrzędną niezerową. Na przykład, dla  mamy następujące cztery rozwiązania istotne:  i 

Rozumując podobnie, udowodnimy teraz, że równanie (mod ) ma rozwiązanie. W tym celu przyjrzyjmy się równaniu (mod ).

Tak samo jak w poprzednim przykładzie możemy uzasadnić, że istnieje nietrywialne rozwiązanie  modulo  Załóżmy bez straty ogólności, że  Wtedy (gdzie  jest odwrotnością  modulo ). A stąd wnioskujemy, że równanie (mod ) ma rozwiązanie.

Zwróćmy jeszcze uwagę na pewną delikatną kwestię mogącą wzbudzać niepokój. Weźmy, na przykład, równanie  Ma ono dokładnie jedno istotne rozwiązanie – trywialne. Liczba zmiennych jest równa stopniowi wielomianu, więc nie możemy stosować twierdzenia Chevalleya–Warninga. Ale  równoważne naszemu, ma już trzy zmienne i stopień równy 2. Czy zatem otrzymaliśmy sprzeczność w matematyce? Nie: zmieniła nam się liczba zmiennych i zbiór rozwiązań jest już trójelementowy:

Dowód. Przejdźmy do dowodu twierdzenia. Główny pomysł to wyrażenie liczby wspólnych rozwiązań w postaci ładnej funkcji – najlepiej także wielomianu.

Wykażemy najpierw, że wielomian

przystaje do 1 modulo  jeżeli  jest wspólnym rozwiązaniem  i przystaje do 0 w przeciwnym przypadku. Dlaczego tak jest? Z Małego Twierdzenia Fermata  lub  modulo  w zależności od tego, czy  dzieli  czy nie. Zatem -ty czynnik  przystaje do  dla rozwiązania  modulo  a do  w przeciwnej sytuacji.

Wynika stąd, że liczba istotnych rozwiązań przystaje modulo  do

Musimy udowodnić, że ta suma jest podzielna przez

Niech  będzie pewnym jednomianem  Wykażemy najpierw, że

(2)

Zauważmy, że

Suma wszystkich wykładników  jest mniejsza niż  gdyż

(ostatnia nierówność wynika z założeń twierdzenia). Dlatego istnieje przynajmniej jeden wykładnik  mniejszy niż  Dla  wzór (2) jest prawdziwy, ponieważ -ty czynnik w powyższym iloczynie jest równy  Natomiast dla  ze wzoru (1) otrzymujemy

zatem także i cały iloczyn jest podzielny przez

Ponieważ  jest sumą swoich jednomianów, to również

co należało wykazać.

---

Użyjemy teraz twierdzenia Chevalleya–Warninga do rozwiązania problemu z teorii grafów. Stopniem wierzchołka grafu będziemy nazywali liczbę krawędzi z niego wychodzących. Zakładamy, że graf nie ma pętelek (krawędzi o tym samym początku i końcu). Mówimy, że graf jest -regularny, jeżeli stopień każdego wierzchołka jest równy  Badanie takich grafów pasjonowało wielu matematyków, szczególnie że – ze względu na swoją symetrię – naturalnie pojawiają się one w licznych problemach. Ciągle istnieje wiele nierozwiązanych hipotez dotyczących tej klasy grafów.

Idea dowodu polega na opisaniu świata kombinatorycznego równaniami diofantycznymi. Niech  będzie zbiorem krawędzi, a   zbiorem wierzchołków  Niech  będzie (niekoniecznie spójnym) podgrafem  zawierającym wszystkie jego wierzchołki (jak na rysunku). Krawędzi w   o końcach  przypiszmy pewną niezerową liczbę  jeżeli ta krawędź leży w   i zero w przeciwnym przypadku. Stopień -tego wierzchołka w  (oznaczany dalej ) przystaje modulo  na mocy Małego Twierdzenia Fermata, do

I odwrotnie, zauważmy, że każdy wybór liczb  daje nam pewien podgraf (zakładamy, że zawiera on wszystkie wierzchołki ). Kluczowe w dowodzie jest spostrzeżenie, że wystarczy znaleźć nietrywialny podgraf (lub równoważnie liczby  nie wszystkie zerowe), którego każdy wierzchołek ma stopień podzielny przez (czyli ). Dlaczego? Nietrywialny podgraf  ma nietrywialną spójną składową. Nietrywialna spójna składowa takiego  będzie właśnie szukanym -podgrafem:  i   więc  jest równy 0 lub  ale w tej nietrywialnej spójnej składowej każdy wierzchołek będzie miał stopień  bo wierzchołki stopnia 0 są izolowane.

Udało nam się sprowadzić nasz problem do rozwiązania układu równań diofantycznych

Tych wielomianów jest  każdy ma stopień  i zależy od zmiennych (dla wszystkich  połączonych krawędzią w  ). Suma stopni tych wielomianów jest równa  Liczba zmiennych jest taka sama jak liczba krawędzi w   czyli (każdy wierzchołek  ma stopień  i każda krawędź ma dwa końce) – to więcej niż  Ponieważ ten układ równań diofantycznych ma trywialne rozwiązanie oraz  więc z twierdzenia Chevalleya–Warninga istnieje szukane rozwiązanie nietrywialne.

Powyższe twierdzenie zostało także udowodnione dla  będącego potęgą liczby pierwszej, ale do tej pory nie wiadomo, czy jest ono prawdziwe dla dowolnej liczby naturalnej.

Łącząc otrzymany przez nas rezultat z argumentami kombinatorycznymi, można wykazać, że dla  każdy -regularny graf bez pętelek zawiera podgraf -regularny.

Warto jeszcze zwrócić uwagę, że nie przypadkiem udało nam się opisać zagadnienie kombinatoryczne za pomocą układu równań diofantycznych. Można udowodnić metatwierdzenie, że każdy skończony problem kombinatoryczny (np. dotyczący grafów) można sprowadzić do rozwiązania pewnego równania diofantycznego modulo (formalnie, każdy podzbiór w   jest zbiorem zer pewnego wielomianu). Niestety, rozwiązanie takiego równania diofantycznego jest prawie zawsze dużo trudniejsze niż rozwiązanie zagadnienia, od którego wyszliśmy.