Detailansicht
On Hilbert's tenth problem over rings of algebraic integers
Tim Benedikt Herbstrith
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Mathematik
Betreuer*in
Christoph Baxa
DOI
10.25365/thesis.60905
URN
urn:nbn:at:at-ubw:1-10840.32361.203352-3
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
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.
Abstract
(Englisch)
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.
Schlagwörter
Schlagwörter
(Englisch)
Hilbert's Problems Algebraic Number Theorie Computability Theory Theoretical Computer Science
Schlagwörter
(Deutsch)
Hilbertprobleme Algebraische Zahlentheorie Berechenbarkeitstheorie Theoretische Informatik
Autor*innen
Tim Benedikt Herbstrith
Haupttitel (Englisch)
On Hilbert's tenth problem over rings of algebraic integers
Paralleltitel (Deutsch)
Das zehnte Hilbertproblem über Ringe ganzalgebraischer Zahlen
Publikationsjahr
2019
Umfangsangabe
iii, 118 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Christoph Baxa
Klassifikationen
31 Mathematik > 31.10 Mathematische Logik, Mengenlehre ,
31 Mathematik > 31.14 Zahlentheorie
AC Nummer
AC15700502
Utheses ID
53813
Studienkennzahl
UA | 066 | 821 | |