Diophantische Gleichung

In der algebraischen Zahlentheorie ist eine diophantische Gleichung (benannt nach dem griechischen Mathematiker Diophantos von Alexandria, um 250) eine Gleichung der Form $f(x_{1},x_{2},x_{3},\dotsc ,x_{n})=0$ , wobei eine gegebene Polynomfunktion mit ganzzahligen Koeffizienten ist und nur ganzzahlige Lösungen gesucht werden. Diese Einschränkung der Lösungsmenge ist sinnvoll und nötig, wenn Teilbarkeitsfragen beantwortet werden sollen, wenn es sich um Probleme der Kongruenzarithmetik handelt oder wenn bei Problemen in der Praxis nur ganzzahlige Lösungen sinnvoll sind, z.B. für die Stückzahlverteilung bei der Herstellung von mehreren Produkten.

Beispiele

$X^{2}-Y=0$ besitzt als Lösung die Zahlenpaare …, (–3, 9), (−2, 4), (–1, 1), (0, 0), (1, 1), (2, 4), (3, 9), …; allgemein: $(X,Y)=\left(n,n^{2}\right)$ mit $n\in\Z.$
$X^{4}+Y^{2}+Z^{{20}}=-7$ ist unlösbar, weil die linke Seite der Gleichung (als Summe von Quadraten) niemals negativ ist.
besitzt keine Lösung, weil 4 nicht durch 3 teilbar ist und es daher keine ganze Zahl gibt, deren 3-Faches 4 ergibt.

Lineare diophantische Gleichung

→ Hauptartikel: Lineare diophantische Gleichung

Diophantische Gleichungen, in denen keine höheren als erste Potenzen der Unbekannten vorkommen, nennt man linear. Für sie gibt es Algorithmen, mit deren Hilfe man stets nach endlich vielen Schritten alle Lösungen findet.

Berühmte diophantische Gleichungen

Pythagoreische Tripel

→ Hauptartikel: Pythagoreisches Tripel

Die unendlich vielen ganzzahligen Lösungen von $X^{2}+Y^{2}=Z^{2}$ bilden die sogenannten pythagoreischen Tripel. Man findet sie im Wesentlichen durch den Ansatz

$X=u^{2}-v^{2}$

$Z=u^{2}+v^{2}$

Fermats letzter Satz

→ Hauptartikel: Großer fermatscher Satz

Wenn man obige Gleichung zu $X^{n}+Y^{n}=Z^{n}$ verallgemeinert, erhält man eine diophantische Gleichung vom Grad . Als Fermats letzten Satz bezeichnet man die von Pierre de Fermat vor 400 Jahren aufgestellte Behauptung, dass sie für n>2 keine ganzzahlige Lösung besitzt (außer den trivialen Lösungen, bei denen eine der Zahlen 0 ist), was erst 1994 von Andrew Wiles bewiesen wurde.

Pellsche Gleichung

Neben den linearen diophantischen Gleichungen ist die sogenannte Pellsche Gleichung

$x^{2}-Dy^{2}=1$

besonders wichtig, wobei für ein gegebenes natürliches zunächst das kleinste Wertepaar (x,y) zu suchen ist, aus dem sich dann alle anderen Paare leicht finden lassen. Wenn eine Quadratzahl ist, hat diese Gleichung nur die trivialen Lösungen $(x,y) = (\pm 1,0)$ , ansonsten hat sie unendlich viele Lösungen. Die Auflösung der Pellschen Gleichung ist gleichbedeutend mit dem Aufsuchen der Einheiten im Ring der algebraisch ganzen Zahlen des quadratischen Zahlkörpers $K=\mathbb {Q} ({\sqrt {D}})$ , der aus dem rationalen Zahlkörper $\mathbb {Q}$ durch Adjunktion einer Quadratwurzel aus entsteht.

Einige allgemeine Lösungsmethoden und Endlichkeitssätze für Klassen diophantischer Gleichungen

Axel Thue zeigte 1908, dass die Gleichung

$f(x,y)=c$

mit einer irreduziblen Form f(x,y) vom Grad größer oder gleich 3 in zwei Variablen ^[1] und einer ganzen Zahl nur endlich viele Lösungen hat (solche Gleichungen werden Thue-Gleichungen genannt). Das baute auf seinen Abschätzungen algebraischer Zahlen durch rationale auf (solche Untersuchungen werden diophantische Approximationen genannt) und ist nicht effektiv (das heißt, man erhält daraus kein Lösungsverfahren). Für den Grad 2 gilt der Satz nicht (die Pellsche Gleichung mit unendlich vielen Lösungen).

Alan Baker gab 1968 eine effektive obere Grenze für die Lösungen von Thue-Gleichungen mit seiner Methode der linearen Formen in Logarithmen algebraischer Zahlen und ein effizienter Algorithmus zu ihrer Lösung wurde 1989 durch De Weger und Tzanakis angegeben.

1929 bewies Carl Ludwig Siegel, dass für Gleichungen, die algebraische Kurven vom topologische Geschlecht g>0 beschreiben, nur endlich viele ganzzahlige Lösungen existieren. Auch dieser Beweis war nicht-effektiv und benutzte diophantische Approximationen. Betrachtet man statt der ganzen Zahlen den Körper der rationalen Zahlen, entspricht der Satz von Siegel der Vermutung von Mordell.

1938 fand Thoralf Skolem eine ziemlich allgemeine Lösungsmethode für diophantische Gleichungen der Form $P(x_{1},\dotsc ,x_{n})=0$ mit einem irreduziblen Polynom , das in einer Erweiterung des Körpers der rationalen Zahlen in m > n Faktoren zerfällt und eine weitere Zusatzbedingung erfüllt. Darunter fällt auch Thues Gleichung für den Fall, dass nicht alle Wurzeln von $f(x,1)=0$ reell sind. Skolems Methode beruht auf p-adischer Analysis (lokale Methode) und nicht auf diophantischen Approximationen wie Thues Methode.

Hilberts zehntes Problem

Im Jahr 1900 stellte David Hilbert das Problem der Entscheidbarkeit der Lösbarkeit einer diophantischen Gleichung als zehntes Problem seiner berühmten Liste von 23 mathematischen Problemen vor. 1970 bewies Juri Wladimirowitsch Matijassewitsch, dass die Lösbarkeit diophantischer Gleichungen unentscheidbar ist, es also keinen allgemeinen Algorithmus geben kann, der zu einer beliebigen diophantischen Gleichung feststellt, ob sie lösbar oder unlösbar ist. Wichtige Vorarbeiten dazu leisteten Martin Davis, Hilary Putnam und Julia Robinson. Von Davis (1953) stammt die Formulierung als Problem über diophantische Mengen und die Vermutung, dass diese identisch mit den rekursiv aufzählbaren Mengen sind, deren Beweis das 10. Hilbertproblem löste.

Eine diophantische Menge ist eine Menge von -Tupeln positiver ganzer Zahlen $x=(x_{1},\dotsc ,x_{n})$ , die eine Polynomgleichung

$P(x_{1},\dotsc ,x_{n},a_{1},\dotsc ,a_{m})=0$

erfüllen mit den ganzzahligen Parametern $(a_{1},\dotsc ,a_{m})$ :

$M=\{\,x\mid \exists a_{1},\dotsc ,a_{m}\colon P(x,a_{1},\dotsc ,a_{m})=0\,\}$

Zum Beispiel bilden die zusammengesetzten Zahlen eine diophantische Menge (das Polynom ist dann $x-(a+1)\,(b+1)$ mit den Parametern a,b ) und die geraden Zahlen (Polynom $x-a\cdot 2$ ). Man kann zur Definition auch Systeme von Polynomgleichungen $P_{i}=0$ verwenden, denn diese lassen sich über $\sum _{i}P_{i}^{2}=0$ auf den Fall einer einzigen Gleichung zurückführen. Entsprechend sind diophantische Funktionen $y=f(x_{1},\dotsc ,x_{n})$ durch die diophantischen Mengen $M=\{y,x_{1},\dotsc ,x_{n}\}$ gegeben. Putnam zeigte 1960, dass jede diophantische Menge natürlicher Zahlen sich als Wertemenge in den natürlichen Zahlen eines ganzzahligen Polynoms darstellen lässt.

Es ist manchmal schwierig zu zeigen, dass eine Menge diophantisch ist. Zum Beispiel bei der Menge der Primzahlen, im Gegensatz zu den zusammengesetzten Zahlen (denn das Komplement einer diophantischen Menge muss nach Martin Davis nicht diophantisch sein), bei den Potenzen von 2 und dem Wert der Faktoriellen . Julia Robinson scheiterte zunächst daran zu zeigen, dass $EXP=\{(a,b,c)\mid a=b^{c}\}$ diophantisch ist. Sie zeigte aber, dass dies folgen würde, wenn man eine diophantische Menge mit exponentiellem Wachstum finden könnte, das heißt solcher Mengen, in deren definierender Gleichung eine der Variablen als Exponent auftaucht. Genauer bedeutet dies, dass gilt (Hypothese von Julia Robinson, J. R.):

Es gibt eine diophantische Menge , sodass gilt:

Für $u,v\in D$ folgt $v\leq u^{u}$ .
Für beliebiges positives gibt es $u,v\in D$ , sodass $v>u^{k}$ .

Diophantische Mengen sind per definitionem rekursiv aufzählbar (es gibt einen Algorithmus, der bei Input aus dieser Menge stoppt).

Zusammen mit Davis und Putnam zeigte Robinson, dass die rekursiv aufzählbaren Mengen genau die exponentiellen diophantischen Mengen sind und der Satz

„Jede rekursiv aufzählbare Menge ist diophantisch“

folgen würde, wenn man die Existenz einer exponentiell wachsenden diophantischen Menge beweisen könnte (für die die Hypothese von Julia Robinson J. R. zutrifft). Das gelang 1970 Matiyasevich mit Hilfe von Fibonacci-Zahlen, einer exponentiell wachsenden Folge natürlicher Zahlen. Sein Beispiel bestand aus zehn polynomialen Gleichungen mit 15 Unbekannten.

Da es nach der Berechenbarkeitstheorie rekursiv aufzählbare Mengen gibt, die nicht entscheidbar sind (nach einem Argument basierend auf Cantor-Diagonalisierung wie beim Halteproblem), folgt, dass Hilberts zehntes Problem nicht lösbar ist.

Da die Primzahlen rekursiv aufzählbar sind, folgt außerdem, dass es eine diophantische Gleichung gibt, deren Lösung aus allen Primzahlen und nur aus diesen besteht.

Seit Thoralf Skolem war bekannt, dass sich alle diophantischen Gleichungen auf solche vierten oder kleineren Grades zurückführen lassen. Matyasevich gelang es außerdem zu zeigen, dass für die Darstellung diophantischer Mengen Polynome in neun und weniger Unbekannten ausreichen.

In Verbindung mit Gödels Unvollständigkeitsresultaten folgt auch, dass es in jedem Axiomensystem der Arithmetik diophantische Gleichungen gibt, die keine Lösung haben, was sich aber nicht innerhalb des Axiomensystems beweisen lässt.

Anmerkungen

↑ Anders ausgedrückt: $f(x,1)=0$ hat mindestens drei verschiedene Wurzeln.

Basierend auf einem Artikel in:

Wikipedia.de