Topologie von Flächen CXXXIV

” Wenn CD aber AB nicht misst, und man nimmt bei AB, CD abwechselnd immer das kleinere vom größeren weg, dann muss (schließlich) eine Zahl übrig bleiben, die die vorangehende misst.”
(Aus Euklid, Die Elemente)

Der euklidische Algorithmus – der älteste bekannte nicht-triviale Algorithmus und sicherlich einer der am häufigsten verwendeten.

Eigentlich berechnet man mit dem euklidischen Algorithmus den größten gemeinsamen Teiler zweier ganzer Zahlen.
(Man kann mit dem Euklidischen Algorithmus z.B. auch den größten gemeinsamem Teiler zweier Polynome oder zweier Gaußscher Zahlen berechnen.
Allgemein, wenn man Elemente in einem Ring betrachten, z.B. dem Ring Z der ganzen Zahlen, dem Ring Z[i] der Gaußschen Zahlen oder dem Ring R[x] der Polynome in x, dann kann man versuchen, größte gemeinsame Teiler mit dem euklidischen Algorithmus zu berechnen. Diejenigen Ringe, in denen der euklidische Algorithmus immer funktioniert, heißen per Definition euklidische Ringe. Beispiele für euklidische Ringe sind die drei obengenannten. Viele, aber nicht alle, Hauptidealringe sind euklidisch.)

Praktische Bedeutung hat der euklidische Algorithmus heute vor allem, weil er in RSA verwendet wird, d.h. praktisch jedesmal wenn man seine Daten im Internet verschlüsselt übertragen will. Was inzwischen wohl Millionen mal täglich passieren dürfte.
(Allerdings soll in den nächsten 10 Jahren die Verschlüsselung im Internet von RSA auf Elliptische-Kurven-Kryptographie umgestellt werden.)

Auch beim Verständnis der Selbstabbildungen von Flächen, also einem eigentlich topologischen (und nicht zahlentheoretischen) Thema, benutzt man den euklidischen Algorithmus.

Vor zwei Wochen hatten wir über Dehn-Twists geschrieben, das ist die unten veranschaulichte Selbstabbildung eines Zylinder, bei der die grüne Kurve ‘einmal um die rote Kurve herumgedreht’ (getwistet) wird.

Man denke sich den Zylinder als Teil einer geschlossenen Fläche (z.B. eines Torus). Man bekommt dann eine Selbstabbildung der geschlossenen Fläche: außerhalb des Zylinders wird einfach jeder Punkt auf sich selbst abgebildet.

Letzte Woche hatten wir über Selbstabbildungen des Torus geschrieben:

Zu jeder 2×2-Matrix
[a b]
[c d]
mit ganzzahligen Einträgen hat man eine Selbstabbildung des Torus, die den oben abgebildeten Meridian a auf aa+cb, und die Longitude b auf ba+db abbbildet.
(Und jeder Homöomorphismus des Torus ist homotop zu einer solchen, durch eine ganzzahlige 2×2-Matrix gegebenen Abbildung.)

Die Dehn-Twists am Meridian bzw. der Longitude entsprechen dabei gerade den Matrizen
[1 1]
[0 1]
bzw.
[1 0]
[1 1].
(Movable Type hat noch immer kein LaTeX, deshalb diese komischen Matrizen.)

Man kann nun den euklidischen Algorithmus benutzen, um zu beweisen, daß jede ganzzahlige 2×2-Matrix (mit Determinante 1) sich als ein Produkt aus diesen beiden Matrizen schreiben läßt.
Auf die Topologie übertragen bedeutet das: jede Selbstabbildung des Torus ist (modulo Homotopie) eine Hintereinanderausführung einer Reihe von Dehn-Twists an Longitude und Meridian.

Wie kommt der euklidische Algorithmus ins Spiel?
Zunächst ist
[1 n] === [1 1]ⁿ
[0 1] === [0 1]
und
[1 0] === [1 0]ⁿ
[n 1] === [1 1].
Man muß also zeigen, daß jede ganzzahlige Matrix ein Produkt solcher oberer und unterer Dreiecksmatrizen ist.
Und weil jede ganzzahlige Matrix mit erster Zeile [1 0] (und Determinante 1) von obiger Form ist, genügt es zu zeigen, daß man aus einer beliebigen ganzzahligen Matrix durch Multiplikation mit negativen Potenzen der obigen Dreiecksmatrizen eine Matrix mit erster Zeile [1 0] bekommen kann.
Nun ist aber
[a b] [1 -n] === [a b-na]
[c d] [ 0 1] === [********]
und
[a b] [ 1 0] === [a-nb b]
[c d] [-n 1] === [********],
die Umformung der ersten Zeile entspricht also gerade einem Schritt im euklidischen Algorithmus (für ein passend gewähltes n). Weil man mit dem euklidischen Algorithmus jedes Paar ganzer Zahlen [a b] letztlich in das Paar [1 0] umformen kann, kann man also jede ganzzahlige Matrix aus SL(2,Z) durch Multiplikation mit oberen und unteren Dreiecksmatrizen in eine Matrix überführen, deren erste Zeile [1 0] ist, also wieder eine untere Dreiecksmatrix.
Womit bewiesen wäre, daß man jede Matrix aus SL(2,Z) als Produkt aus oberen und unteren Dreicksmatrizen schreiben kann. Also jede Selbstabbildung des Torus als Produkt aus Dehn-Twists an Meridian und Longitude. (Jedenfalls ‘modulo Homotopie’.)

Teil 1, Teil 2, Teil 3, Teil 4, Teil 5, Teil 6, Teil 7 , Teil 8, Teil 9 , Teil 10 ,Teil 11, Teil 12, Teil 13, Teil 14, Teil 15, Teil 16, Teil 17, Teil 18, Teil 19, Teil 20, Teil 21, Teil 22, Teil 23, Teil 24, Teil 25, Teil 26, Teil 27, Teil 28, Teil 29, Teil 30, Teil 31, Teil 32, Teil 33, Teil 34, Teil 35, Teil 36, Teil 37, Teil 38, Teil 39, Teil 40, Teil 41, Teil 42, Teil 43, Teil 44, Teil 45, Teil 46, Teil 47, Teil 48, Teil 49, Teil 50, Teil 51, Teil 52, Teil 53, Teil 54, Teil 55, Teil 56, Teil 57, Teil 58, Teil 59, Teil 60, Teil 61, Teil 62, Teil 63, Teil 64, Teil 65, Teil 66, Teil 67, Teil 68, Teil 69, Teil 70, Teil 71, Teil 72, Teil 73, Teil 74, Teil 75, Teil 76, Teil 77, Teil 78, Teil 79, Teil 80, Teil 81, Teil 82, Teil 83, Teil 84, Teil 85, Teil 86, Teil 87, Teil 88, Teil 89, Teil 90, Teil 91, Teil 92, Teil 93, Teil 94, Teil 95, Teil 96, Teil 97, Teil 98, Teil 99, Teil 100, Teil 101, Teil 102, Teil 103, Teil 104, Teil 105, Teil 106, Teil 107, Teil 108, Teil 109, Teil 110, Teil 111, Teil 112, Teil 113, Teil 114, Teil 115, Teil 116, Teil 117, Teil 118, Teil 119, Teil 120, Teil 121, Teil 122, Teil 123, Teil 124, Teil 125, Teil 126, Teil 127, Teil 128, Teil 129, Teil 130, Teil 131, Teil 132, Teil 133