Application of the LLL algorithm to diophantine approximation

Głównym celem pracy jest przedstawienie algorytmu LLL, jego zmodyfikowanej wersji ILLL oraz przedstawienie ich zastosowania w aproksymacji diofantycznej. Metody te zostaną użyte do znalezienia ciągu czasów, w których wielokrotność punktu znajduje się blisko punktu kratowego, oraz do jego porównania z ciągiem czasów najlepszych przybliżeń wprowadzonym przez Lagariasa. Dokonujemy tego porównania dla losowo wybranych punktów kwadratu i sześcianu jednostkowego przy użyciu normy euklidesowej i normy supremum oraz dla pewnych szczególnych punktów rozważanych przez Huberta--Messaoudiego przy wykorzystaniu normy Rauzy’ego; porównanie to ma charakter eksperymentalny. Na początku pracy zostaną przedstawione podstawowe fakty dotyczące teorii krat oraz teorii ułamków łańcuchowych oraz dokładne opisy działania algorytmów LLL i ILLL. W dalszej części pracy zostanie przedstawione zastosowanie tych algorytmów do aproksymacji diofantycznej oraz wyniki eksperymentów. W wyniku powyższych eksperymentów formułujemy problem względnego asymptotycznego zachowania rozważanych ciągów.

The aim of the thesis is to present the LLL algorithm, its modified version ILLL, and their application to diophantine approximation. These methods will be used to find a sequence of times at which a multiple of a given point is close to a lattice point, and to compare it with the sequence of best approximations introduced by Lagarias. We do this for randomly selected points in a unit square and unit cube using the Euclidean norm and the supremum norm, and for certain points considered by Hubert--Messaoudi using the Rauzy norm; the comparison is experimental. The thesis begins with some basic facts on lattices and continued fractions, as well as detailed descriptions of the LLL and ILLL algorithms. We apply these algorithms to diophantine approximation, and present the results of the experiments. These results enable us to formulate a question concerning the relative asymptotic behaviour of these sequences.