Obliczeniowa teoria równań diofantycznych

Skrypt jest tutaj. (dobrze jest go przeczytać przed rozpoczęciem rozwiązywania zadań kwalifikacyjnych)

Uwaga do zadań kwalifikacyjnych: przez chwilkę w zadaniu piątym był błąd, więc jeśli ktoś przypadkiem zaczął robić je już 30. maja i zmartwił się, że nie wychodzi, to już jest poprawione. :)

Dziesiąty problem Hilberta pyta, czy istnieje ogólny algorytm potrafiący rozstrzygnąć, czy dane równanie diofantyczne ma rozwiązanie w liczbach całkowitych.

W latach 50. próbowano pokazać, że zbiór trójek \((b^c,b,c)\in\mathbb{Z}^3\) jest diofantyczny (to znaczy, że istnieje wielomian \(P(a,b,c,x_1,...,x_n)\) o współczynnikach całkowitych, taki, że równanie \(P(a,b,c,x_1,...,x_n) = 0\) ma rozwiązania w liczbach całkowitych wtedy i tylko wtedy, gdy \(a = b^c\)), ale nawet osłabiona hipoteza (że istnieje zbiór diofantyczny par \((a,b)\) taki, że \(b<a^a\) i dla każdego \(k > 0\) istnieje taka para \((a,b)\) w tym zbiorze, że \(b>a^k\)) pozostawała nierozwiązana. Później okazało się, że rozstrzygnięcie, czy wykładnicze równanie diofantyczne (to znaczy takie, które może mieć też niewiadome w wykładnikach) ma rozwiązania, jest niemożliwe, co wraz z powyższą hipotezą dawałoby, że nierozstrzygalne są również zwykłe równania diofantyczne. W 1970 roku pokazano, że zbiór \(\{(a,b)\in\mathbb{Z}^2: b=F_{2a}\}\) jest diofantyczny (liczby Fibonacciego jak wiadomo rosną wykładniczo), co dało negatywną odpowiedź na 10. problem Hilberta.

Podczas warsztatów pokażemy wspólnie z uczestnikami, że nie istnieje algorytm, który stwierdza, czy dane równanie diofantyczne ma rozwiązanie (najpierw pokażemy, że zbiór \(a=b^c\) jest diofantyczny, a potem przy użyciu tego wyniku zredukujemy jakiś nierozwiązywalny problem, na przykład problem stopu, do problemu znajdowania rozwiązań równań diofantycznych).

Dowód będzie podzielony na kolejne kroki, które uczestnicy będą mogli przeprowadzić sami.

W ramach ciekawostek, jeśli starczy czasu, wspomnimy też o następujących zagadnieniach:

• jak wykorzystać fakt, że funkcja wykładnicza jest diofantyczna, by pokazać, że diofantyczny jest również zbiór liczb pierwszych i współczynników dwumianowych
• definiowaniu liczb całkowitych wewnątrz liczb wymiernych

Wymagania: 

• warto wiedzieć czym są wielomiany
• znajomość pojęć ze skryptu

Będą one sprawdzone w zadaniach kwalifikacyjnych, które już są dostępne.

Wszystkie pytania i rozwiązania zadań kwalifikacyjnych należy kierować na maile:

• mejlaklukowskiego@gmail.com (Adam Klukowski)
• elvenpath98@gmail.com (Asia Jasińska)