Wie man Diophantische Gleichungen löst

Wie man Diophantische
Gleichungen löst
Anna-Maria Chiavetta
Seminar
28. Oktober 2013
Inhaltsverzeichnis
1. Einführung in das Thema
2. Lösbarkeit Diophantischer Gleichungen
- Beispielgleichung
3. Ein anderer Blickwinkel
- Höhenfunktion
4. Nadeln im Heuhaufen
5. Schlussfolgerung
1. Diophantische Gleichungen
F(x1,x2,...,xn) = 0
F ist ein Polynom mit ganzzahligen Koeffizienten.
Die Lösungen sind ausℤoder ℚ, je nach Bedarf.
Benannt nach Diophantos von Alexandria
Beispiele
• x³+y³+z³ = 29
• x³+y³+z³ = 30
•
•
•
•
•
(x,y,z)=(3,1,1)
(x,y,z)=(4,-3,-2)
x =2220422932
y =-2218888517
z =-283059965
• x³+y³+z³ = 31
• x³+y³+z³ = 33
•
•
•
• Unbekannt
Keine Lösung
a³≡ -1;0;1 mod 9
=> Summe aus 3
Kubikzahlen ist
≢ 4;5 mod 9
2. Lösbarkeit Diophantischer
Gleichungen
• David Hilberts 10. Problem:
Entscheidung der Lösbarkeit einer
Diophantischen Gleichung
• Er versuchte eine Methode zu finden, um
nach endlich vielen Operationen eine
Entscheidung treffen zu können.
• (Er sucht einem Algorithmus)
Kann man die Lösbarkeit zeigen?
• Der Beweis zu zeigen, dass es solch ein
Algorithmus gibt, ist einfach:
• Algorithmus finden und aufschreiben!
• Zu zeigen,dass es keinen Algorithmus gibt ist
ein Problem:
• Alle möglichen Algorithmen betrachten und
zeigen, dass keiner das Problem löst.
Theorem 1
(Davis, Putnam, Robinson, Matiyasevich)
Die Lösbarkeit Diophantischer
Gleichungen ist unentscheidbar
• Die Lösbarkeit kann immer gezeigt werden
beim Durchsuchen abzählbar vieler
Möglichkeiten
• Probleme treten auf wenn,
- Keine Lösung existiert.
- Endlich viele Lösungen existieren und alle
Lösungen gefunden werden sollen.
Sollen wir jetzt aufgeben?
• Nein!
• Wir wollen versuchen Algorithmen zu
finden, für bestimmte Arten von
Gleichungen.
(z.B.: für Polynome in 2 Variablen)
Das Pascalsche Dreick
Beispielgleichung
• Wir suchen eine ganzzahlige Lösung
für:
(1)
• Nebenbedingungen:
1 < k ≤ y/2, 1 < l ≤ x/2 und k < l
Lösungen
F steht für die Fibonacci-Zahlen
(F0=0, F1=1, Fn+2=Fn+1 + Fn)
• Gleichung (1) hängt nicht in polynomialer
Weise von k und l ab, deshalb ist sie nach
unserer Definition keine Diophantische
Gleichung.
• Wir nehmen k und l konstant,
(k,l) ∊ {(2,3),(2,4),(2,6),(2,8),(3,4),(3,6),(4,6)}
(sind schon vollständig gelöst)
• Noch ungelöst ist der Fall (k,l) = (2,5)
oder
60y(y-1) = x(x-1)(x-2)(x-3)(x-4)
(2)
Lösungen suchen:
• x = 0,1,2,3,4,5,6,7,15 und 19
• Sind dies nun alle Lösungen?
• Wenn ja, wie können wir das Beweisen?
• Nun müssen wir überlegen was über die
Lösungensmengen solcher Gleichungen
bekannt ist.
• 1929 bewies Carl Ludwig Siegel hierfür, das
erst wichtige Ergebnis.
Theorem 2 (Siegel)
Sei F ein irreduzibles Polynom in 2
Variablen x und y mit ganzzahligen
Koeffizienten. Wenn die Lösungen von
F(x,y)=0 nicht rational parametrisiert
werden können, dann hat F(x,y)=0 nur
endlich viele ganzzahlige Lösungen.
• Rationale Parametrisierung:
• Ist ein Paar f(t), g(t) rationaler
Funktionen nicht beide Konstant, s.d.
F(f(t),g(t))=0 ist.
• Dies kann algorithmisch geprüft werden.
• Theorem 2 und sein Beweis sind
ineffizient, da es keine Schranke für die
Größe der Lösungen gibt. ( bis 1960)
• Alan Baker entwickelt die „Linearformen
in Logarithmen“!
• => für (2) gilt
• |x| < 10^10^10^10^600
(3)
• (Obere Schranke) => endliches Problem
• Wir wollen nun die vollständige Liste der
Lösungen
• Druch Verbesserungen und Verfeinerungen
wurde die Schranke reduziert auf:
• |x| < 10^10^600
(4)
3. Ein anderer Blickwinkel
• Eine geometrische Interpretation
• F(x,y)=0 ist eine Teilmenge der Ebene, die
aus den Punkten besteht, deren
Koordinanten die Gleichung erfüllen.
• F ist ein Polynom
• => Die Lösungsmenge ist eine ebene
algebraische Kurve
• C(ℤ) ist die Menge der ganzzahligen Punkte
auf der Kurve C
Kurve C in R²
Wir sind nur an den
ganzzahligen Punkten auf
C interessiert.
Die algebraische Geometrie sagt uns:
• C kann in ein anderes Objekt J
eingebettet werden, wobei J eine
Fläche darstellt.
• Dies nennt man die Jacobi-Varietät
• Eigenschaften von J:
• J ist eine Gruppe
• Die Menge J(ℤ) ist eine abelsche
Gruppe
Theorem 3 (Weil)
Wenn J die Jacobi-Varietät einer Kurve
ist, dann ist die abelsche Gruppe J(ℤ)
endlich erzeugt.
• D.h. wir wollen eine explizite
Beschreibung der Gruppe durch
Erzeuger und Relationen finden.
Wozu?
• Um die Elemente von J(ℤ), welche im Bild
von C liegen in den Griff zu bekommen.
• Explizites Erzeugendensystem algorithmisch
bestimmen
• => es können alle ganzzahligen Lösungen
gefunden werden.
• Allerdings ist unbekannt ob dies immer
möglich ist.
Zu unserer Beispielgleichung
• Es ist möglich:
• J(ℤ) ist eine freie abelsche Gruppe vom
Rang 6:
• J(ℤ)=ℤP1+ℤP2+ℤP3+ℤP4+ℤP5+ℤP6 (5)
mit bekannten P1,...,P6 ∊ J(ℤ)
• Sei i : C à J eine Einbettung von C in J
• J ist ein hoch dimensionaler Raum
• Die ganzzahligen Punkte darauf sind durch
eine Anzahl von Koordinaten gegeben.
=> Höhenfunktion
Eigenschaften:
h: J(ℤ) à ℝ≥0
• h(i(x,y)) ≈ log |x|, für (x,y) ∊ C(ℤ)
(6)
• (Zeigt das Verhalten der Punkte auf der Kurve)
• h(n1P1+n2P2+n3P3+n4P4+n5P5+n6P6) ≈
n1²+n2²+n3²+n4²+n5²+n6²
(7)
• (Zeigt die Verträglichkeit mit der Gruppenstruktur
auf J)
• => h ist eine positiv definite quadratische Form auf
J(ℤ) bis auf einen beschränkten Fehler.
• Wir kombinieren nun die Ausage (4) mit (6) u. (7)
Lemma 1
Wenn (x,y) ∊ C(ℤ) ist, dann haben wir
i(x,y) = n1P1+n2P2+n3P3+n4P4+n5P5+n6P6
mit nj ∊ℤ, welche |nj| <10^300 erfüllt.
• Die gegebene Schranke ist nicht genau.
• Durch die Gruppenstruktur kann die
Schranke von 10^10^600 auf 10^1800
verkleinert werden.
• => diese Zahlen kann nun ein Computer
dastellen.
4. Nadeln im Heuhaufen
• H={(n1+n2+n3+n4+n5+n6) ∊ℤ⁶:
|nj| < 10^300}
• 10^1800 Halme und eine
kleine Anzahl an Nadeln
• Wir wollen Bedingungen
an die Position der
Nadeln stellen, um einen
großen Teil des
Heuhaufens
auszuschließen.
• An dieser Stelle benutzen wir, dass die
Gruppenstruktur auf J geometrisch definiert
ist.
• Die Objekte C, J und i sind über ℤ definiert.
• Ihre Gleichungen modulo p betrachten, wobei
p eine Primzahl ist.
• Körperℤ/pℤ bezeichen wir als Fp
• C(Fp) und J(Fp) sind die Mengen der Punkte
die die Gleichungen mod p erfüllen.
• Dann ist J(Fp) bis auf endlich viel p wieder
abelsch und sie enthält das Bild i(C(Fp)) auf
C(Fp)
• Gruppe J(Fp) endlich => Menge C(Fp) endlich
• Die senkrechten Abbildungen erhält man durch
reduzieren der Koordinaten mod p
• Die geometrische Natur der Gruppenstruktur
implizert, dass die rechte senkrechte Abbildung ein
Gruppenhomomorphismus ist.
• αp ist ein Gruppenhomomorphismus, welcher durch
das Bild der Erzeuger P1...P6 von J(ℤ) festgelegt ist.
Lemma 2
Seien (x,y) ∊ C(ℤ) und n1,n2,n3,n4,n5,n6 ∊ℤ
mit
i(x,y) = n1P1+n2P2+n3P3+n4P4+n5P5+n6P6
Dann ist αp(n1,n2,n3,n4,n5,n6) ∊ ip(C(Fp))
• Die Teilmenge ʎp=αp^-1 (ip(C(Fp))) ∊ℤ⁶
ist eine Vereinigung von #C(Fp)
Nebenklassen einer Untergruppe vom
Index #J(Fp) inℤ⁶.
• # C(Fp) ≈ p und #J(Fp) ≈ p²
• => H ∩ ʎp hat nur 1/p mal so viele
Elemente, wie H.
• Nun kombinieren wir die
Einschränkungen vieler Primzahlen.
• Wir nennen S eine große, endliche
Menge von Primzahlen und setzen,
• ʎs = ∩ ʎp mit p ∊ S und erhalten
i(C(ℤ)) ⊂ ʎs∩H.
• Je größer wir nun S wählen, umso
kleiner wird ʎs∩H .
• Wir haben eine Reduktion der
Heuhaufengröße erreicht und jetzt ist
ein Computer in der Lage uns ein
Ergebnis zu liefern.
5. Schlussfolgerung
(Bugeaud, Mignotte, Siksek,Stoll, Tengely)
• Seien x,y ganze Zahlen, die die Gleichung
erfüllen. Dann ist x ∊ {0,1,2,3,4,5,6,7,15,19}
Vielen Dank
Quellenangabe:
- Einladung in die Mathematik (2013)
ISBN 978-3-642-25798-8
- http://www.lachmeister.de/lustige_bilder/images/lustigesbild_nadel-im-heuhaufen.jpg

Download Report