Od Prouheta–Tarry'ego–Escotta do Thuego–Morse'a

Do jednych z najstarszych problemów w historii matematyki należy niewątpliwie zaliczyć równania diofantyczne, czyli równania o dziedzinie rozwiązań ograniczonej do liczb całkowitych. Obecną nazwę zawdzięczają one Diofantosowi, greckiemu matematykowi żyjącemu w III wieku naszej ery w Aleksandrii. Swoje rozważania na temat takich równań Diofantos zawarł w serii ksiąg pod tytułem Arytmetyka. Studiując jedną z nich, Pierre de Fermat - żyjący w XVII wieku francuski prawnik i matematyczny samouk - uznał, że pewne zawarte w niej równanie nie może mieć rozwiązań, o czym raczył poinformować przyszłych czytelników w słynnej uwadze, zamieszczonej na marginesie (czytanej przezeń książki oraz niniejszego artykułu).

Mowa, rzecz jasna, o równaniu $n n n |x + y = z$ dla $|n > 2,$ które czekało na rozwiązanie (a właściwie dowód jego braku) ponad 300 lat. Dopiero w 1993 roku, po kilku latach intensywnych prac, Andrew Wiles zakończył wysiłek pokoleń matematyków, dowodząc postawionej na początku drugiej połowy XX wieku hipotezy Shimury-Taniyamy. Po licznych poprawkach jego rozumowanie zostało w roku 1995 oficjalnie opublikowane na łamach Annals of Mathematics, a w 2016 roku został on uhonorowany prestiżową Nagrodą Abela.

Wielkie Twierdzenie Fermata dotyczy prostego w sformułowaniu równania diofantycznego, którego rozwiązanie wymaga zastosowania bardzo zaawansowanych narzędzi matematycznych. W niniejszym artykule chciałbym przedstawić zgoła przeciwną sytuację: pozornie skomplikowane równanie diofantyczne przeanalizujemy przy użyciu metod elementarnych. Rozważmy następujący układ równań diofantycznych:

Q ak = Q bk, dla k = 1,...,n. a>A b>B

gdzie $A$ oraz $B |$ są pewnymi dwoma równolicznymi i rozłącznymi skończonymi zbiorami liczb całkowitych oraz $|n⩾ 1$ jest liczbą naturalną. Należy więc dla ustalonego wykładnika $n$ znaleźć takie dwa równoliczne i rozłączne zbiory liczb całkowitych $A$ i $B, |$ by sumy liczb z tych zbiorów w potęgach mniejszych lub równych $|n$ były równe. Problem ten pochodzi od Eulera i Goldbacha, współcześnie znany jest pod nazwą problemu Prouheta-Tarry'ego-Escotta. Prouhet zajmował się tym układem w połowie XIX wieku, pozostali na początku XX wieku podali wiele interesujących rozwiązań.

Przyjrzyjmy się kilku przykładom. Znalezienie szczególnego rozwiązania dla małych $|n$ (dla $n = 2$ jest nim, na przykład, $A$ oraz $B = {1,2,6}$ ) nie nastręcza większych kłopotów. Dla większych wykładników poziom trudności obliczeń wzrasta bardzo szybko, np. dla $|n = 9$ przykładowe rozwiązanie to

$pict$

Polecam Czytelnikowi próbę znalezienia jakiegokolwiek rozwiązania dla $|n = 3$ (przykładowe można znaleźć na końcu artykułu). Wydaje się, że problem Prouheta-Tarry'ego-Escotta jest trudny do rozwikłania, nawet jeśli postanowimy wspomóc się komputerem. Tymczasem czeka na nas ogromna niespodzianka. Okazuje się bowiem, że jesteśmy w stanie prosto skonstruować pewne rozwiązania dla dowolnej potęgi $n.$ Ponadto żaden komputer nie będzie nam do tego potrzebny.

Zanim przedstawimy rozwiązanie, dla dowolnej liczby naturalnej $n$ określmy rekurencyjnie pewne skończone ciągi zer i jedynek. Rozpoczniemy od definicji negatywu ciągu zero-jedynkowego, czyli zamianie każdego występującego w nim zera na jedynkę i odwrotnie. Negatyw ciągu $A$ będziemy oznaczali przez $A-$ ; dla przykładu, jeżeli $A |$ to $|A= 10100.$ Niech teraz $0 |x = 01.$ Gdy mamy już zdefiniowane $n x ,$ to przyjmujemy $---- |x n+1 = x n x n ,$ to znaczy do ciągu $|x j$ dopisujemy z prawej strony jego negatyw. Przykład:

x 1 = x 0 x 0 - = 0101 = 0110.

Tak zdefiniowane ciągi posłużą nam do rozwiązania problemu. Dla ustalonej liczby naturalnej $n$ podzielimy teraz zbiór ${0,...,2n+1− 1}$ na takie dwa rozłączne zbiory, że odpowiednie sumy zgadzają się dla potęg od 0 do $|n.$ Niech

An

są to zatem numery tych wyrazów ciągu $x n ,$ które są równe odpowiednio 0 lub 1. Wtedy $An$ i $Bn |$ są poszukiwanymi zbiorami. Dowód będzie przebiegał indukcyjnie względem $|n.$ Dla $|n = 0$ mamy

x n = 01 oraz A0

Wykonamy teraz krok indukcyjny. Załóżmy, że mamy już zdefiniowane $|A$ oraz $|B n−1$ spełniające tezę. Niech

̃An = {2n +i i∈ Bn−1} oraz ̃Bn−1 = {2n + i i ∈An

Wtedy $An$ i analogicznie $Bn = Bn−1 ∪̃Bn −1.$ Równości te wynikają wprost z definicji ciągu $x n$ i są kluczową obserwacją wykorzystywaną w kroku indukcyjnym. Jeżeli teraz $|k⩽ n,$ to, oznaczając przez $S j$ sumę $| j$ -tych potęg liczb ze zbioru $An$ (dla $| j⩽ n −1$ równą sumie $| j$ -tych potęg liczb ze zbioru $Bn −1$ ), mamy:

$pict$

Analogicznie moglibyśmy udowodnić tę samą równość dla sumy $|k$ -tych potęg liczb ze zbioru $|B , n$ co kończy dowód indukcyjny.

Zaprezentowana metoda ma jedną zaletę - pozwala w prosty sposób skonstruować jakiekolwiek rozwiązanie. Problemem jest jednak jej optymalność. Zwróćmy uwagę na to, że dla $n = 9$ otrzymujemy w ten sposób zbiory $A$ i $B |$ złożone z $512$ elementów każdy, a tymczasem widzieliśmy wcześniej rozwiązanie, w którym zbiory $|A$ oraz $|B$ były "zaledwie" dziesięcioelementowe. Okazuje się, że rozwiązania dla wykładnika $|n$ muszą być zbiorami złożonymi z co najmniej $n + 1$ liczb całkowitych. Rozwiązanie, które spełnia to oszacowanie jako równość, nazywamy idealnym. Największym wykładnikiem, dla którego znane jest idealne rozwiązanie, jest $n = 11,$ a jest nim para dwunastoelementowych zbiorów

$pict$

Ciągi skończone $n x ,$ które posłużyły nam do konstrukcji rozwiązań, są początkowymi fragmentami pewnego nieskończonego ciągu zero-jedynkowego, zwanego ciągiem Thuego-Morse'a. Formalnie ciąg ten, oznaczany dalej przez $|x,$ można zdefiniować jako $n ∞ |x = (x n )n 1.$ Jedną z ciekawych własności ciągu $x$ jest to, że nie zmienia się on pod wpływem operacji podstawień $|0 01,1 10.$ Wynika to z faktu, że wykonanie tej operacji na ciągu $|x n$ daje nam w rezultacie ciąg $|x n+1 ,$ czego nietrudno dowieść za pomocą indukcji. Oczywiście, nie jest to jedyna jego interesująca cecha, jednak na zaprezentowanie wszystkich nie starczyłoby miejsca na marginesie tego artykułu, ani nawet w całym numerze Delty.

Oto rozwiązanie (idealne) dla $n = 3$