On Hilbert's tenth problem over rings of algebraic integers

Hilberts zehntes Problem fragt, ob ein Algorithmus existiert, der zu gegebenen multivariaten Polynom mit ganzzahligen Koeffizienten entscheiden kann, ob dieses ganzzahlige Nullstellen besitzt. Obwohl das Problem breits im Jahr 1900 von Hilbert (1900) formuliert wurde, dauerte es bis 1970, bis Matijasevič (1970) beweisen konnte, dass es keinen solchen Algorithmus geben kann. Das Problem lässt sich direkt auf andere kommutative Ringe R mit 1 übertragen, indem Koeffizienten aus ℤ oder R und Nullstellen aus R gewählt werden. In dieser Masterarbeit werden wir uns vor allem mit dem Fall von Ringen ganzalgebraischer Zahlen beschäftigen. Wie eng Hilberts zehntes Problem mit anderen Entscheidungsproblemen verwandt ist, kommt allerdings erst dann zu Tage, wenn wir Hilberts Problem als die Frage der Entscheidbarkeit einer Theorie auffassen. Wir werden zum Beispiel erkennen, dass Matijasevic’ DPRM-Theorem sehr ähnlich zu Gödels Haupttheorem in seinem Beweis (Gödel 1931) des ersten Unvollständigkeitssatzes ist. Um Hilberts Problem in dieser Allgemeinheit verstehen zu können, werden im ersten Abschnitt Grundlagen der Berechenbarkeitstheorie und der Modelltheorie vorgestellt. Dabei werden wir auf das Halteproblem stoßen, dessen Unentscheidbarkeit die Schlüsselzutat für alle unsere Beweise der Unentscheidbarkeit sein wird. Weiters werden wir die für uns relevanten Begriffe und Resultate der algebraischen Zahlentheorie sowie der Geometrie der Zahlen wiederholen und teilweise beweisen. Nach diesen einführenden Kapiteln werden wir im zweiten Teil der Arbeit Hilberts zehntes Problem formalisieren und eine ausführlichere Betrachtung verwandter Probleme und der historischen Entwicklung dieser anstellen. Um das Problem schließlich negativ für ausgewählte Ringe zu entscheiden, werden wir diophantische Mengen über kommutativen Ringen mit 1 einführen und einige wichtige strukturelle Eigenschaften diophantischer Mengen beweisen. Das Hauptresultat dieser Arbeit ist, dass über einem Ring ganzalgebraischer Zahlen O_K, über dem die ganzen Zahlen ℤ eine diophantische Menge bilden, unabhängig davon, ob Koeffizienten aus ℤ oder O_K gewählt werden, das zehnte hilbertsche Problem unentscheidbar ist. Im letzten Abschnitt der Arbeit werden die Resultate von Denef (1980), Pheidas (1988) und Shlapentokh (1989) präsentiert. Diese konnten im Fall von total-reellen algebraischen Zahlkörpern K ≠ ℚ und algebraischen Zahlkörpern K mit mindestens einer reellen und genau einem Paar komplexer Einbettungen zeigen, dass ℤ über O_K eine diophantische Menge ist. Damit ist Hilberts zehntes Problem über O_K in diesen Fällen unentscheidbar. Für allgemeine Zahlkörper steht noch nicht fest, ob Hilberts Problem entscheidbar ist. Die Vermutung von Denef and Lipshitz (1978), dass für alle Zahlkörper K Hilberts zehntes Problem über O_K unentscheidbar ist, ist noch unbewiesen.Hilbert’s tenth problem asks, whether there exists an algorithm that can decide for a given multivariate polynomial p with integral coefficients, if p has integral roots. Even though the problem was already posed in 1900 by Hilbert (1900), it took until 1970 til Matijasevič (1970) could prove that such an algorithm cannot exist. The problem can be translated directly to other commutative rings R with 1 by letting the coefficients range over ℤ or R and consider roots in R. In this thesis we put special interest on the case of R being a ring of algebraic integers. How closely Hilbert’s tenth problem is related to other decision problems, will however only become apparent when we consider the problem as a question of decidability of a theory. For instance, we will see that Matijasevič’ DPRM-theorem ([thm:DPRM]) is very similar to Gödel’s central theorem in his proof (Gödel 1931) of the first incompleteness theorem. To understand Hilbert’s problem in this general setting, we introduce the basics of computability theory and model theory in the first part of this thesis. During these introductory sections we will present the halting problem. The undecidability of this fundamental problem will be the key ingredient in every proof of undecidability we will encounter. Furthermore, we will remind the reader of the relevant results of algebraic number theory and geometry of numbers. In a second step we will formalize Hilbert’s tenth problem and will extensively study related problems and their historical developments. In order to eventually answer the problem to the negative for selected rings, we will define Diophantine sets over commutative rings with 1 and prove some of their important structural properties. The main result of this thesis is, that Hilbert’s tenth problem is unsolvable over a ring of algebraic integers O_K if ℤ is Diophantine over O_K. This statement remains true whether we allow the polynomials to have coefficients in ℤ or O_K. In the final section of this thesis we will present the results of Denef (1980), Pheidas (1988), and Shlapentokh (1989). They where able to prove in the case of totally real number fields K ≠ ℚ and number fields of degree at least 3 over ℚ with exactly one pair of non-real embeddings, that ℤ is Diophantine over O_K. As a consequence, Hilbert’s tenth problem is undecidable over O_K. For general number fields it is not known whether Hilbert’s tenth problem is decidable over their ring of algebraic integers. The conjecture by Denef and Lipshitz (1978), that Hilbert’s tenth problem is undecidable over O_K for all algebraic number fields K, is still unproven