8.5 Ergänzungen *

Zur Gruppentheorie lassen sich ganze Bücher schreiben, und auch wenn dieser Abschnitt mit Ergänzungen sehr lang ist, kratzen wir im Grunde nur an der Oberfläche. Immerhin spannen wir einen weiten Bogen, beginnend mit kleinen Ergänzungen zur allgemeinen Theorie, über Anwendungen der Gruppentheorie auf abstrakte Fragen der Zahlentheorie mit dem quadratischen Reziprozitätsgesetz als einem besonders schönen Ergebnis, zu alltagsnahen (wenn vielleicht auch nicht sehr wichtigen) Themen wie dem 15-Puzzle und Rubiks Zauberwürfel. Vielleicht weckt das ja Ihr Interesse, das eine oder andere Thema weiterzuverfolgen.

8.5.1 Elementare Zahlentheorie

Viele Ergebnisse der »elementaren Zahlentheorie« lassen sich leicht aus der Theorie der Gruppen herleiten. Wir beginnen damit, ein kleines bisschen mehr Gruppentheorie zu behandeln. Ein wichtiger Begriff ist die Ordnung eines Gruppenelements, die im folgenden Lemma definiert wird.

Lemma 8.54

Sei $G$ eine endliche Gruppe. Für jedes $g\in G$ existiert $n\in \mathbb N_{{\gt} 0}$, so dass $g^n = 1$. Das kleinste solche $n$ nennen wir die Ordnung des Elements $g$, und wir bezeichnen diese Zahl mit $\operatorname{ord}(g)$.

Die Ordnung von $g$ ist gleich der Anzahl der Elemente der von $g$ erzeugten Untergruppe $\langle g\rangle $ von $G$.

Beweis

Sei $g\in G$. Weil $G$ endlich ist, ist klar, dass $i {\lt} j\in \mathbb N$ existieren mit $g^i = g^j$, und es folgt $g^{j-i} = 1$.

Es ist noch zu zeigen, dass $\langle g\rangle = \operatorname{ord}(g)$ gilt. Wir schreiben $n= \operatorname{ord}(g)$. Mit dem obigen Argument, angewandt auf die Gruppe $\langle g\rangle $, ist dann klar, dass $n \le \# \langle g\rangle $ ist. Andererseits ist $\{ g^i;\ i=0,\dots , n-1\} $ eine Gruppe, die $g$ enthält (denn $g^{-1} = g^{n-1}$, und allgemeiner $g^i = g^j$ für alle $i,j\in \mathbb Z$ mit $n \, |\, (i-j)$ – man kann also jeden Exponenten durch seinen Rest bei Division durch $n$ ersetzen). Da $\langle g\rangle $ keine echten Untergruppen hat, die $g$ enthalten, folgt die Behauptung.

Die Ordnung des neutralen Elements einer endlichen Gruppe $G$ ist $1$, und alle anderen Elemente haben Ordnung ${\gt} 1$. Der folgende Satz zeigt, dass die Ordnung eines Elements $g\in G$ immer ein Teiler von $\# G$ ist. Die Zahl $\# G$, die Anzahl der Elemente von $G$, bezeichnet man auch als die Ordnung der Gruppe $G$.

Satz 8.55 Satz von Lagrange

Sei $G$ eine endliche Gruppe und $H$ eine Untergruppe von $G$. Dann ist $\# H$ ein Teiler von $\# G$.

Insbesondere gilt: Ist $g\in G$, so ist die Ordnung von $g$ ein Teiler von $\# G$.

Beweis

Wir verwenden für den Beweis den Begriff der Äquivalenzrelation aus Abschnitt 3.14.2.

Für $g, g^\prime \in G$ setzen wir

\[ g\sim g^\prime \quad :\Longleftrightarrow \quad g^{-1} g^\prime \in H. \]

Da $H$ eine Untergruppe ist, ist dies eine Äquivalenzrelation auf $G$. Die Reflexivität gilt, weil $H$ das neutrale Element enthält, die Symmetrie folgt daraus, dass für jedes Element aus $H$ auch sein Inverses in $H$ liegt, und die Transitivität ergibt sich daraus, dass $H$ unter der Bildung von Produkten abgeschlossen ist.

Also ist $G$ die disjunkte Vereinigung der Äquivalenzklassen. Die Behauptung des Satzes folgt nun daraus, dass in dieser speziellen Situation jede Äquivalenzklasse genau $\# H$ Elemente haben. Denn ist $X\subseteq G$ irgendeine der Äquivalenzklassen und $x\in X$, so ist die Abbildung

\[ H\longrightarrow X,\quad h\mapsto xh, \]

eine Bijektion. Wegen $x^{-1}xh = h\in H$ gilt $x\sim xh$, also liegt $xh$ in $X$. Weil $G$ eine Gruppe ist, ist klar, dass die Abbildung injektiv ist. Ist schließlich $x^\prime \in X$ irgendein Element, dann ist $x\sim x^\prime $, also $h := x^{-1} x^\prime \in H$, und $x^\prime = xh$ im Bild der obigen Abbildung.

Als direkte Folgerung erhalten wir:

Korollar 8.56 Satz von Euler

Sei $n \ge 1$ eine natürliche Zahl. Wir definieren $\varphi (n) = \# (\left.\mathbb Z\middle /n\right.)^\times $, die Anzahl der Elemente von $\left.\mathbb Z\middle /n\right.$, die ein multiplikatives Inverses besitzen. Dies ist die Anzahl der zu $n$ teilerfremden Zahlen zwischen $1$ und $n-1$. Siehe Ergänzung 8.9.

Die Funktion $\varphi \colon \mathbb N_{\ge 1}\to \mathbb N_{\ge 1}$ heißt die Eulersche $\varphi $-Funktion.

Dann gilt für alle $a\in \mathbb Z$, die zu $n$ teilerfremd sind, dass

\[ a^{\varphi (n)} \equiv 1\mod n, \]

mit anderen Worten: $a^{\varphi (n)}$ hat Rest $1$ bei Division durch $n$.

Ist $n$ eine Primzahl, so ist $\varphi (n) = n-1$, und die Aussage des Korollars ist genau die des kleinen Fermatschen Satzes (Satz 4.21), für den wir hier einen neuen Beweis erhalten.

Satz 8.57

Seien $m, n\in \mathbb N$, $m,n\ge 1$, so dass $\operatorname{ggT}(m,n) = 1$.

Die Abbildung

\[ \left.\mathbb Z\middle /(mn)\right. \to \left.\mathbb Z\middle /m\right.\times \left.\mathbb Z\middle /n\right.,\quad a \mapsto (a,a), \]

ist ein Isomorphismus von (additiven) Gruppen.
Die Abbildung aus Teil (1) liefert durch Einschränkung einen Isomorphismus

\[ \left.\mathbb Z\middle /(mn)\right.^\times \to (\left.\mathbb Z\middle /m\right.)^\times \times (\left.\mathbb Z\middle /n\right.)^\times \]

von (multiplikativen) Gruppen. Insbesondere gilt $\varphi (mn) = \varphi (m)\varphi (n)$ für alle teilerfremden natürlichen Zahlen $m,n\ge 1$.

Die Aussage in Teil (1) ist auch unter dem Namen chinesischer Restsatz bekannt. Die letzte Aussage von Teil (2) bezeichnet man auch als die Multiplikativität der $\varphi $-Funktion. Es ist aber zu beachten, dass diese Multiplikativität nur für teilerfremde Zahlen $m$, $n$ gilt, wie man leicht an Beispielen sieht.

Beweis

zu (1). Das Bild eines Elements $a\in \left.\mathbb Z\middle /(mn)\right.$ ist das Paar $(a,a)$, wo hier der linke Eintrag als Restklasse in $\left.\mathbb Z\middle /m\right.$, der rechte als Restklasse in $\left.\mathbb Z\middle /n\right.$ zu verstehen ist. Die Abbildung ist unabhängig davon, wie wir ein Element von $\left.\mathbb Z\middle /(mn)\right.$ durch eine ganze Zahl repräsentieren, also wohldefiniert, und es ist klar, dass es sich um einen Gruppenhomomorphismus handelt. Da beide Seiten $mn$ Elemente haben, genügt es, die Injektivität zu zeigen. Diese ist aber klar, denn wenn $a$ auf $(0,0)$ abgebildet wird, so bedeutet das gerade, dass $m\, |\, a$ und $n\, |\, a$; da $m$ und $n$ teilerfremd sind, impliziert das $mn\, |\, a$, also ist das Element $a$ in $\left.\mathbb Z\middle /(mn)\right.$ gleich $0$.

zu (2). Ist $f$ die Abbildung aus Teil (1), so gilt jedenfalls $f(\left.\mathbb Z\middle /(mn)\right.^\times ) \subseteq (\left.\mathbb Z\middle /m\right.)^\times \times (\left.\mathbb Z\middle /n\right.)^\times $, denn aus $ab=1$ folgt $f(a)f(b) = f(ab) = f(1) = 1$. Die Injektivität überträgt sich direkt, und es bleibt nur noch die Surjektivität zu zeigen.

Sei dazu $(b,c)\in (\left.\mathbb Z\middle /m\right.)^\times \times (\left.\mathbb Z\middle /n\right.)^\times $. Wir zeigen, dass eine ganze Zahl $a$ existiert, die teilerfremd ist zu $mn$, und deren Restklasse in $\left.\mathbb Z\middle /m\right.$ (bzw. $\left.\mathbb Z\middle /n\right.$) gleich $b$ (bzw. gleich $c$) ist. Da die Abbildung $f$ bijektiv ist, gibt es sowieso nur einen Kandidaten: Wir bezeichnen mit $a\in \left.\mathbb Z\middle /(mn)\right.$ das eindeutig bestimmte Urbild von $(b,c)$ unter $f$ wie in Teil (1). Es ist dann zu zeigen, dass $\operatorname{ggT}(a,mn)=1$. Da die Bilder $b$ und $c$ von $a$ in $\left.\mathbb Z\middle /m\right.$ und $\left.\mathbb Z\middle /n\right.$ nach Voraussetzung »teilerfremd« zu $m$ bzw. $n$ sind, folgt aber, dass $a$ zu $m$ und zu $n$ teilerfremd ist. Da auch $m$ und $n$ unter sich teilerfremd sind, liefert das die Behauptung.

Dass in dieser Situation $\varphi (mn)=\varphi (m)\varphi (n)$ gilt, folgt, indem wir die Anzahl der Elemente in der linken und rechten Seite vergleichen.

Bemerkung 8.58 Das RSA-Verfahren

Die Multiplikativität der $\varphi $-Funktion zusammen mit dem Satz von Euler (Korollar 8.56) sind die Grundlage des RSA-Verfahrens (vergleiche Bemerkung 4.22), dessen Prinzip das folgende ist:

Alice wählt als privaten Schlüssel zwei verschiedene, große Primzahlen $p$ und $q$ aus, berechnet das Produkt $N = pq$ und sucht eine zu $\varphi (N) = (p-1)(q-1)$ teilerfremde Zahl $e$. Weil sie $\varphi (N)$ kennt, kann Sie $a,b\in \mathbb Z$ mit $ae + b\varphi (N) = 1$ finden.

Als öffentlichen Schlüssel veröffentlicht sie die Zahlen $N$ und $e$.

Bob, der Alice eine Nachricht schicken möchte, zerlegt die Nachricht in Teile, die sich als Elemente $M\in \left.\mathbb Z\middle /N\right.$ schreiben lassen, und schickt Alice jeweils die Zahl $C = M^e \in \left.\mathbb Z\middle /N\right.$.

Empfängt Alice die Nachricht $C$, so berechnet sie

\[ C^a = M^{ea} = M^{ae + b\varphi (N)} = M\quad \text{in}\ \left.\mathbb Z\middle /N\right.. \]

Im zweiten Schritt wird der Satz von Euler verwendet, der impliziert, dass $M^{\varphi (N)}=1$ ist. Dass Alice $M$ aus $C$ rekonstruieren kann, zeigt die Durchführbarkeit des Verfahrens.

Die Sicherheit von RSA beruht darauf, dass es nicht mit akzeptablem Aufwand möglich ist, aus den Informationen $N$ und $e$ allein eine Zahl $a$ mit $ae =1\in \left.\mathbb Z\middle /N\right.^\times $ zu berechnen. Eine offensichtliche Möglichkeit, dies zu tun, wäre, die Zahl $N$ in ihre Primfaktoren zu zerlegen und daraus $\varphi (N)$ zu berechnen. Danach ist es einfach, $a$ zu finden (und Alice muss ja zu Beginn diese Rechnung durchführen). Man kann (und muss) $N$ so groß wählen, dass die Faktorisierung von $N$ mit allen bekannten Verfahren zu lange dauern würde.

Ergänzung 8.59 Primitivwurzeln

Die multiplikative Gruppe eines endlichen Körper $\mathbb F_p$ ist immer eine zyklische Gruppe, d.h. sie lässt sich von einem einzigen Element erzeugen. Allgemeiner gilt das folgende Resultat.

Theorem 8.60

Sei $G\subseteq K^\times $ eine endliche Untergruppe der multiplikativen Gruppe eines Körpers $K$. Dann ist $G$ zyklisch.

Wir benutzen im Beweis das folgende Lemma:

Lemma 8.61

Sei $G$ eine endliche kommutative Gruppe.

Seien $a,b\in G$ Elemente mit $\operatorname{ord}(a) = m$, $\operatorname{ord}(b) = n$ und $\operatorname{ggT}(m,n)=1$. Dann gilt $\operatorname{ord}(ab) = mn$.
Sei $n$ die größte Zahl, die als Ordnung eines Elements von $G$ auftritt. Dann gilt für alle $a\in G$, dass $\operatorname{ord}(a)\, |\, n$.

Beweis

Wir schreiben die Gruppe $G$ multiplikativ.

zu (1). Es ist klar, dass $(ab)^{mn} = 1$ gilt.

Zunächst bemerken wir, dass $a^i = b^j$ für $i,j\in \mathbb Z$ nur gelten kann, wenn $a^i = 1 = b^j$ ist (also $i$ von $m$ und $j$ von $n$ geteilt werden). Denn es folgt $a^{in} = b^{jn} = 1$, also $m\, |\, in$, wegen der Teilerfremdheit von $m$ und $n$ also $m\, |\, i$, und analog $n\, |\, j$.

Ist nun $(ab)^i = 1$ für eine ganze Zahl $i$, so haben wir $a^i b^i = (ab)^i = 1$, also folgt aus der Vorbemerkung, dass $m\, |\, i$ und $n\, |\, i$. Weil $m$ und $n$ teilerfremd sind, impliziert das $mn \, |\, i$. Insgesamt folgt $\operatorname{ord}(ab)=mn$.

zu (2). Sei $n$ wie im Lemma beschrieben, sei $b\in G$ ein Element mit $\operatorname{ord}(b) = n$ und sei $a\in G$. Sei $k = \operatorname{ggT}(n, \operatorname{ord}(a))$, $i = \operatorname{ord}(a)/k$. Dann hat $a^k$ die Ordnung $i$, und $\operatorname{ggT}(i, n)=1$. Aus Teil (1) folgt, dass das Element $ab$ die Ordnung $in$ hat. Nach Definition von $n$ folgt $i=1$, also $k = \operatorname{ord}(a)$, und das bedeutet genau, dass $\operatorname{ord}(a)\, |\, n$.

Beweis des Theorems

Neben dem Lemma ist die entscheidende Zutat für den hier gegebenen Beweis, dass eine Polynomfunktion der Form $x\mapsto \sum _{i=0}^d a_ix^i$ höchstens $d$ Nullstellen in $K$ haben kann (Satz 4.25).

Sei also $G\subseteq K^\times $ eine endliche Untergruppe und sei $n$ die maximale Ordnung eines Elements von $G$. Wir wollen zeigen, dass $n = \# G$ gilt. Aus Teil (2) des Lemmas folgt, dass für alle Elemente $a\in G$ gilt, dass $\operatorname{ord}(a)\, |\, n$, also $a^n = 1$. Alle Elemente von $G$ sind also Nullstellen der Polynomfunktion $x\mapsto x^n-1$. Es folgt $\# G\le n$. Andererseits wissen wir wegen Satz 8.55, dass $n\le \# G$ gilt.

Es gibt verschiedene andere Beweise dieses Resultats. (In dieser Quelle wird speziell der Fall $K=\mathbb F_p$ betrachtet; einige der Beweise liefern aber das Ergebnis in der allgemeinen Form.)

Wenn die Restklasse von $a\in \mathbb Z$ die Gruppe $\mathbb F_p^\times $ erzeugt, dann sagt man auch, $a$ sei eine Primitivwurzel modulo $p$. Der Satz sagt aus, dass stets eine Primitivwurzel modulo $p$ existiert. Es ist aber nicht einfach, systematisch eine solche zu finden. Eine Vermutung von E. Artin (1898–1962) besagt, dass für jede ganze Zahl $a\ne -1$, die keine Quadratzahl ist, die Restklasse von $a$ für unendlich viele Primzahlen $p$ eine Primitivwurzel ist. Es gibt keine einzige Zahl $a$, für die man die Vermutung bisher beweisen konnte! Es ist aber bekannt, dass die Artinsche Vermutung aus der »verallgemeinerten Riemannschen Vermutung«, einer Variante der berühmten Riemannschen Vermutung, folgt.

Ergänzung 8.62 Quadratische Reste

Sei $p$ eine ungerade Primzahl. Es ist eine interessante Frage, wie man feststellen kann, ob eine Gleichung der Form $X^2 = a$ in $\mathbb F_p$ lösbar ist. Hier kann man $a$ als Element in $\mathbb F_p$ betrachten, oder als ganze Zahl und dann implizit zur Restklasse in $\mathbb F_p$ übergehen. Mit anderen Worten: Für $a\in \mathbb Z$ wird gefragt, ob eine ganze Zahl $n\in \mathbb Z$ existiert, so dass $n^2-a$ durch $p$ teilbar ist.

Wir betrachten die Abbildung $\mathbb F_p^\times \to \mathbb F_p^\times $, $x\mapsto x^2$. Wie man unmittelbar nachprüft, handelt es sich um einen Gruppenhomomorphismus. Dieser ist nicht injektiv, denn für $a$ im Bild, etwa $a = x^2$ gilt auch $a = (-x)^2$. Allerdings sind dann $x$ und $-x$ die einzigen Urbilder von $a$, da quadratische Gleichungen über einem Körper höchstens zwei Lösungen haben. Da nach Voraussetzung $p {\gt} 2$ ist, gilt $x\ne -x$. Alle Elemente des Bildes haben also genau zwei Urbilder, und wir sehen, dass das Bild dieser Abbildung $(p-1)/2$ Elemente umfasst, mit anderen Worte, dass für genau $(p-1)/2$ Elemente $a\in \mathbb F_p^\times $ die Gleichung $X^2 - a$ lösbar ist.

Nach Satz 4.21 ist $x^{p-1} = 1$ für alle $x\in \mathbb F_p^\times $, also $x^{\frac{p-1}{2}}\in \{ 1, -1\} $. Ist $a = x^2$, so folgt $a^{\frac{p-1}{2}} = x^{p-1} = 1$.

Andererseits haben wir in Theorem 8.60 gesehen, dass die Gruppe $\mathbb F_p^\times $ zyklisch ist. Es gibt also ein Element $x\in \mathbb F_p^\times $ von Ordnung $p-1$. Für dieses kann nicht $x^{\frac{p-1}{2}} = 1$ gelten. Das bedeutet, dass der Gruppenhomomorphismus $\mathbb F_p^\times \to \{ 1, -1\} $, $x\mapsto x^{\frac{p-1}{2}}$, surjektiv ist. Für alle Elemente im Bild eines Gruppenhomomorphismus stimmen die Anzahlen der Urbildmengen überein; es werden also $\frac{p-1}{2}$ Elemente auf $1$, und ebenso $\frac{p-1}{2}$ Elemente auf $-1$ abgebildet. Wir haben bereits gesehen, dass genau die Hälfte der Elemente von $\mathbb F_p^\times $ ein Quadrat ist, und es folgt:

Lemma 8.63 Kriterium von Euler

Sei $a\in \mathbb F_p^\times $. Es gibt genau dann ein Element $x\in \mathbb F_p^\times $ mit $x^2 = a$, wenn $a^{\frac{p-1}{2}} = 1$.

Definition 8.64 Legendre-Symbol

Wir definieren für eine ungerade Primzahl $p$ und eine zu $p$ teilerfremde ganze Zahl $a$ das Legendre-Symbol

\[ \left(\frac{a}{p}\right) := \begin{cases} 1 & \text{falls die Restklasse von}\ a\ \text{in}\ \mathbb F_p\ \text{ein Quadrat ist},\\ -1 & \text{sonst}. \end{cases} \]

Wir betrachten hier $1$ und $-1$ als ganze Zahlen, damit wir die Legendre-Symbole für verschiedene Primzahlen vergleichen können. Die Restklasse von $\left(\frac{a}{p}\right)$ in $\mathbb F_p^\times $ ist nach dem Eulerschen Kriterium gleich $a^{\frac{p-1}{2}}$. Das Legendre-Symbol ist »als Ganzes« zu verstehen, der waagerechte Strich ist kein Bruchstrich (und dementsprechend kann man auch die Klammern nicht weglassen).

Aus dem Euler-Kriterium folgt, dass die Abbildung $a\mapsto \left(\frac ap\right)$ ein Gruppenhomomorphismus $\mathbb F_p^\times \to \{ 1, -1\} $ ist, mit anderen Worten: Sind $a, b\in \mathbb Z$ zu $p$ teilerfremd, so gilt

\[ \left(\frac{ab}{p}\right) = \left(\frac ap\right) \left(\frac bp\right). \]

Sind $p$ und $q$ verschiedene ungerade Primzahlen, dann gibt es einen außerordentlich überraschenden Zusammenhang zwischen $\left( \frac{p}{q} \right)$ und $\left( \frac{q}{p} \right)$, das sogenannte quadratische Reziprozitätsgesetz. Es ist alles andere als offensichtlich, dass die beiden Eigenschaften – ob $p$ ein Quadrat in $\mathbb F_q^\times $ ist einerseits, und ob $q$ ein Quadrat in $\mathbb F_p^\times $ ist andererseits – etwas miteinander zu tun haben. Und doch kann man diese Eigenschaften in verblüffender Weise verbinden. Die Aussage wurde bereits von Euler und Legendre vermutet. Den ersten Beweis hat Gauß um 1800 gegeben; er hat später noch mehrere andere Beweise gefunden und diesen Satz sein »goldenes Theorem« (theorema aureum) genannt.

Theorem 8.65 Quadratisches Reziprozitätsgesetz

Seien $p$ und $q$ verschiedene ungerade Primzahlen. Dann gilt

\[ \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}. \]

Mit anderen Worten: Die Legendre-Symbole $\left( \frac{p}{q} \right)$ und $\left( \frac{q}{p} \right)$ sind gleich, es sei denn, sowohl $p$ als auch $q$ haben bei Division durch $4$ den Rest $3$, und dann sind sie verschieden.

Es gibt viele Beweise des quadratischen Reziprozitätsgesetzes. Wir skizzieren einen »trickreichen« Beweis nach G. Rousseau (J. Austral. Math. Soc. Ser. A 51 no. 3 (1991), 423–425.) Einen besonders durchsichtigen Beweis kann man mit den Methoden der Galois-Theorie geben, wie sie in der Algebra-Vorlesung erarbeitet werden.

Beweis

Wir betrachten die Gruppe

\[ G = (\left.\mathbb Z\middle /p\right.)^\times \times (\left.\mathbb Z\middle /q\right.)^\times \cong (\left.\mathbb Z\middle /pq\right.)^\times \]

(Satz 8.57).

Sei

\begin{align*} P_1 & = (\left.\mathbb Z\middle /p\right.)^\times \times \{ 1, \dots , \frac{q-1}{2} \} \subset G,\\ P_2 & = \{ 1, \dots , \frac{pq-1}{2} \} \subset (\left.\mathbb Z\middle /pq\right.)^\times \cong G \end{align*}

In beiden Fällen liegt für $x$ in $G$ genau eines der Elemente $x$, $-x$ in $P_i$. (Wir benutzen hier, dass der Isomorphismus $G\cong (\left.\mathbb Z\middle /pq\right.)^\times $ aus Satz 8.57 verträglich ist mit der Bildung des Negativen.)

Das Produkt über alle Elemente in $P_1$ und das Produkt über alle Elemente in $P_2$ unterscheiden sich also nur um das Vorzeichen.

Nun haben wir

\[ \prod _{x\in P_1} x = \left( ((p-1)!)^{\frac{q-1}{2}}, \left(\frac{q-1}{2}!\right)^{p-1} \right) = \left( ((p-1)!)^{\frac{q-1}{2}}, ((q-1)!)^{\frac{p-1}{2}} \, (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \right) \]

Um das Produkt über alle Elemente in $P_2$ auszurechnen, müssen wir alle die Zahlen von $1$ bis $\frac{pq-1}{2}$ multiplizieren, die zu $p$ und $q$ teilerfremd sind. Wir können das folgendermaßen schreiben: $\prod _{x\in P_2} x$ ist die Restklasse der ganzen Zahl

\[ \frac{1\cdots (p-1)\cdot (p+1)\cdots (2p-1)\cdot \cdots \cdot (\frac{q-3}{2}p+1)\cdot \cdots \cdot (\frac{q-1}{2}p -1) (\frac{q-1}{2}p+1) \cdots (\frac{q-1}{2}p + \frac{p-1}{2})}{q\cdot 2q\cdot \cdots \cdot \frac{p-1}{2}q} \]

(im Zähler multiplizieren wir alle Zahlen von $1$ bis $\frac{pq-1}{2}$ bis auf die Vielfachen von $p$, und teilen dann durch alle Vielfachen von $q$; weil $p$ und $q$ verschiedene Primzahlen sind, gibt es keine Überschneidung). Die Restklasse dieses Elements in $\left.\mathbb Z\middle /p\right.$ ist

\[ \frac{((p-1)!)^{\frac{q-1}{2}}}{q^{\frac{p-1}{2}}} = ((p-1)!)^{\frac{q-1}{2}} \, \left(\frac{q}{p}\right), \]

wobei wir das Euler-Kriterium (Lemma 8.63) sowie die Tatsache, dass $\left(\frac{q}{p}\right)\in \{ 1, -1\} $ ist, benutzt haben. Streng genommen steht hier die Restklasse des Legendre-Symbols in $\left.\mathbb Z\middle /p\right.$. Analog erhalten wir als die Restklasse von $\prod _{x\in P_2} x$ in $\left.\mathbb Z\middle /q\right.$ das Element

\[ \frac{((q-1)!)^{\frac{p-1}{2}}}{p^{\frac{q-1}{2}}} = ((q-1)!)^{\frac{p-1}{2}} \, \left(\frac{p}{q}\right). \]

In $G$ können wir also schreiben

\[ \prod _{x\in P_2} x = \left( ((p-1)!)^{\frac{q-1}{2}} \, \left(\frac{q}{p}\right), ((q-1)!)^{\frac{p-1}{2}} \, \left(\frac{p}{q}\right)\right). \]

Weil sich $\prod _{x\in P_1} x$ und $\prod _{x\in P_2} x$ höchstens um das Vorzeichen unterscheiden, erhalten wir

\[ \left( ((p-1)!)^{\frac{q-1}{2}}, ((q-1)!)^{\frac{p-1}{2}} \, (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \right) = \varepsilon \left( ((p-1)!)^{\frac{q-1}{2}} \, \left(\frac{q}{p}\right), ((q-1)!)^{\frac{p-1}{2}} \, \left(\frac{p}{q}\right)\right) \]

für $\varepsilon \in \{ 1, -1\} $. Wir multiplizieren diese Gleichung mit dem Inversen von $((p-1)!)^{\frac{q-1}{2}}, ((q-1)!)^{\frac{p-1}{2}}$ und erhalten das quadratische Reziprozitätsgesetz

\[ \left( \frac{p}{q} \right) \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}. \]

Das quadratische Reziprozitätsgesetz wird vervollständigt durch die sogenannten Ergänzungssätze:

Satz 8.66 Ergänzungssätze zum quadratischen Reziprozitätsgesetz

Sei $p$ eine ungerade Primzahl.

Es gilt

\[ \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = \begin{cases} 1 & p \equiv 1 \mod 4,\\ -1 & p \equiv 3 \mod 4.\\ \end{cases} \]
Es gilt

\[ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = \begin{cases} 1 & p \equiv 1 \mod 8\quad \text{oder}\quad p \equiv 7 \mod 8,\\ -1 & p \equiv 3 \mod 8\quad \text{oder}\quad p \equiv 5 \mod 8.\\ \end{cases} \]

Beweis

Teil (1) ist ein Spezialfall des Eulerschen Kriteriums. Der Beweis des zweiten Teils ist nicht besonders schwierig (jedenfalls wesentlich leichter als der Beweis des Reziprozitätsgesetzes selbst), aber wir lassen ihn an dieser Stelle aus.

Mit dem Reziprozitätsgesetz, den Ergänzungssätzen und der Multiplikativität des Legendre-Symbols kann man leicht entscheiden, ob eine Zahl ein quadratischer Rest in $\mathbb F_p$ ist:

Beispiel 8.67

Um festzustellen, ob die Gleichung $X^2 - 137$ in $\mathbb F_{211}$ eine Lösung hat, rechnen wir

\begin{align*} \left(\frac{137}{211}\right) & = \left(\frac{211}{137}\right) = \left(\frac{74}{137}\right) = \left(\frac{2}{137}\right) \, \left(\frac{37}{137}\right) = \left(\frac{2}{137}\right) \, \left(\frac{137}{37}\right) = \left(\frac{26}{37}\right) = \left(\frac{2}{37}\right) \, \left(\frac{13}{37}\right)\\ & = -\left(\frac{37}{13}\right) = -\left(\frac{11}{13}\right) = -\left(\frac{13}{11}\right) = -\left(\frac{2}{11}\right) = 1, \end{align*}

die obige Gleichung ist also lösbar.

Mehr Informationen auf Wikipedia: deutsch, englisch (und wesentlich ausführlicher, auch zur Geschichte des quadratischen Reziprozitätsgesetzes).

Eine weitreichende Verallgemeinerung des quadratischen Reziprozitätsgesetzes ist das Artinsche Reziprozitätsgesetz, ein Kernstück der sogenannten Klassenkörpertheorie. Die Suche nach Verallgemeinerungen der Klassenkörpertheorie bestimmt maßgeblich die heutige algebraische Zahlentheorie.

Ergänzung 8.68 Die Fibonacci-Zahlen modulo $p$

Für einen »spielerischen« Abschluss des Abschnitts über Zahlentheorie kommen wir noch einmal auf die Fibonacci-Zahlen (Beispiel 5.60) zu sprechen und beweisen:

Satz 8.69

Sei $p$ eine Primzahl. Dann teilt $p$ die Fibonacci-Zahl $F_{2p(p^2-1)}$.

Beweis

Für $p=2$ kann man die Behauptung direkt verifizieren ($F_{12} = 144$ ist gerade). Wir setzen im folgenden voraus, dass $p$ ungerade ist. Wir betrachten

\[ G = \left\{ A\in GL_2(\mathbb F_p);\ \det (A) \in \{ 1, -1\} \right\} , \]

eine Untergruppe von $GL_2(\mathbb F_p)$. Hier benutzen wir die Determinante einer $(2\times 2)$-Matrix,

\[ \det \left( \begin{pmatrix} a & b \\ c & d \end{pmatrix} \right) = ad - bc, \]

siehe Beispiel 5.56 oder Kapitel 9 für eine systematische Behandlung. Um zu sehen, dass $G$ eine Untergruppe von $GL_2(\mathbb F_p)$ ist, muss man wissen, dass sich die Determinante multiplikativ verhält: $\det (AB)=\det (A)\det (B)$. Im $(2\times 2)$-Fall kann man das natürlich anhand der gegebenen Formel direkt nachrechnen.

Die Gruppe $G$ hat $2p(p^2-1)$ Elemente: Die erste Spalte der Matrix kann irgendein Vektor aus $\mathbb F_p^2$ sein, der nicht Null ist. Die zweite Spalte muss linear unabhängig zur ersten sein, alle $p$ Vielfache der ersten Spalte fallen damit schon einmal heraus. Von den verbleibenden $p^2-p$ Elementen führen genau $\frac{p^2-p}{(p-1)/2} = 2p$ Elemente zu einer Determinante $1$ oder $-1$ (denn wenn wir die zweite Spalte um ein Skalar abändern, ändert sich die Determinante um denselben Faktor).

Nun ist $A:=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \in G$, und aus Satz 8.55 folgt, dass $A^{2p(p^2-1)} = E_2$ in $G$ gilt. Andererseits folgt aus den Überlegungen in Beispiel 5.60, dass

\[ \begin{pmatrix} \overline{F}_{n+1} \\ \overline{F}_n \end{pmatrix} = A^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} \]

ist, wobei $\overline{F}_n$ die Restklasse der Fibonacci-Zahl $F_n$ in $\mathbb F_p$ bezeichnet. Es folgt $\overline{F}_{2p(p^2-1)} = 0$, und das ist genau die Behauptung.

Quelle: https://mathoverflow.net/a/53643

8.5.2 Darstellungstheorie

Unter einer Darstellung einer Gruppe $G$ versteht man einen Gruppenhomomorphismus $\rho \colon G\to \operatorname{Aut}(V)$, wo $V$ ein Vektorraum (über einem Körper $K$, den man zu Beginn fixiert) ist. Ist $V$ ein endlich-dimensionaler Vektorraum, so liefert die Wahl einer Basis von $V$ einen Isomorphismus $\operatorname{Aut}(V)\cong GL_n(K)$ (Beispiel 8.15). Wenn man sich auf endlich-dimensionale Vektorräume einschränkt, kann man also genauso gut Gruppenhomomorphismen $G\to GL_n(K)$ studieren.

Jedem Element $g\in G$ wird also ein Automorphismus $\rho (g)\colon V\to V$ zugeordnet. Man sagt auch, dass die Gruppe $G$ mittels dieser Automorphismen auf dem Vektorraum $V$ wirke.

Ist die Abbildung $\rho \colon G \to \operatorname{Aut}(V)$ injektiv, so kann man $G$ mit einer Untergruppe von $\operatorname{Aut}(V)$ identifizieren und die Gruppe $G$ so sehr explizit realisieren. Manchmal kann man $G$ dann sogar als die Symmetriegruppe einer Teilmenge (wie in Abschnitt 8.1.6) sehen.

Je nachdem, welcher Art die Gruppe $G$ ist, sind unterschiedliche Darstellungen von Interesse. Bei Gruppen wie $G=GL_n(\mathbb R)$ wird man in der Regel nur solche $\rho $ betrachten, die stetig sind oder ähnliche Bedingungen erfüllen, die die »analytische« Natur der Gruppe $G$ reflektieren. Bei endlichen Gruppen $G$ ist es ein großer Unterschied, ob die Charakteristik des Grundkörpers $K$ ein Teiler der Gruppenordnung $\# G$ ist (sofern die Charakteristik von $K$ nicht $0$ ist).

8.5.3 Verschiedenes

Beispiel 8.70 Das 15-Puzzle

Das »15-Puzzle« ist ein Schiebepuzzle mit 15 quadratischen Teilen, die in 4 Zeilen mit je 4 Teilen angeordnet sind; ein Feld bleibt dabei frei. Man kann dann die Position verändern, indem man eines der Teile, die zu dem freien Feld benachbart sind, dort hin verschiebt.

$\includegraphics[width=7.4cm]{figures/p15-3}$

Während eine offensichtliche Aufgabe ist, die Ausgangsstellung wiederherzustellen, nachdem sie durch mehrere Züge der oben beschriebenen Art durcheinander gebracht wurde, ist eine interessantere Frage die folgende: Stellen wir uns die 15 Teile durchnummeriert von 1 bis 15 und aufsteigend angeordnet (1, 2, …) vor, so dass das Feld rechts unten frei ist. Ist es möglich, durch eine Folge von Zügen dieselbe Position mit dem einzigen Unterschied, dass die Teile 14 und 15 vertauscht sind, zu erreichen? Allgemeiner kann man fragen, ob alle Permutationen der Teile durch eine Folge der oben beschriebenen Züge erreichbar sind; oder – wenn nicht – welche erreichbar sind.

Das Puzzle fand ab ca. 1880 eine große Verbreitung in den USA; es wurde sogar ein Preisgeld für eine positive Antwort auf die oben gestellte Frage ausgesetzt. Allerdings zeigt die folgende Überlegung, dass das Problem nicht lösbar ist:

Wir definieren für jede mögliche Position $P$ des Puzzles eine Zahl $i(P)\in \{ 1, -1\} $ wie folgt: Sei $\sigma \in S_{15}$ die Permutation, so dass (von oben nach unten, und von links nach rechts gelesen) die Zahlen $1,\dots , 15$ in der Reihenfolge $\sigma (1), \sigma (2), \dots , \sigma (15)$ auftreten. Hierbei wird das leere Feld übersprungen. Dann setzen wir

\[ i(P) = \begin{cases} -\operatorname{sgn}(\sigma ) & \text{wenn sich das leere Feld in Reihe 1 oder Reihe 3 befindet,}\\ \operatorname{sgn}(\sigma ) & \text{wenn sich das leere Feld in Reihe 2 oder Reihe 4 befindet.}\\ \end{cases} \]

Es ist dann leicht zu sehen, dass jeder mögliche Verschiebe-Zug die Zahl $i(P)$ nicht ändert: In der Tat, verschiebt man innerhalb einer Zeile, dann ändern sich weder $\sigma $ noch der Zeilenindex des leeren Feldes. Verschiebt man innerhalb einer Spalte, dann ändert sich der Zeilenindex des leeren Feldes, und $\sigma $ ändert sich um eine Transposition.

\includegraphics[width=7.4cm]{figures/p15-2} — Abbildung 8.2 Lässt sich die Ausgangsstellung (rechts) aus der links dargestellten Position durch Verschieben der Steine herstellen?

\includegraphics[width=7.4cm]{figures/p15-1} — Abbildung 8.2 Lässt sich die Ausgangsstellung (rechts) aus der links dargestellten Position durch Verschieben der Steine herstellen?

Da für die Position $P$, wo alle Teile $1$ bis $15$ in aufsteigender Reihenfolge angeordnet sind, $i(P)=1$ gilt, aber für die Position $i(P^\prime )$, wo im Vergleich dazu nur 14 und 15 vertauscht sind, $i(P^\prime )=-1$ ist, kann es keine Zugfolge geben, die diese beiden Positionen ineinander überführt.

Man kann auch zeigen, dass man zwei Positionen $P_1$ und $P_2$ genau dann ineinander überführen kann, wenn $i(P_1)=i(P_2)$ gilt. Das kann man auch mit ganz elementaren Überlegungen zeigen, lässt sich aber nicht in einem Absatz abhandeln. Allerdings ist auch diese Tatsache schon lange bekannt, siehe [W. Johnson, W. Story, Notes on the “15” Puzzle, Amer. J. Math. 2, no. 4 (1879), 397–404]. Siehe auch [ Jo ] 7.4.

Ergänzung 8.71 Rubiks Zauberwürfel

Die Theorie der Gruppen ist nützlich, um Rubiks Zauberwürfel mathematisch zu analysieren. Dazu stellen wir uns den Würfel selbst im Raum fixiert vor (d.h. dass die sechs Mittelplättchen des Würfels sich nicht bewegen, sondern höchstens »mitdrehen« in den Bildern hier zeigt das grüne Mittelplättchen immer nach vorne, das gelbe nach oben, das rote nach links, usw.). Wir nummerieren alle anderen Plättchen durch (von $1$ bis $48$). Jede Verdrehung, die man mit dem Würfel dann machen kann, entspricht einer Permutation der Zahlen von $1$ bis $48$.

Wir verwenden die übliche Notation für die möglichen »Züge«, die man ausführen kann:

$\mathsf{F}$ – Drehung der vorderen Ebene (front) um $90^\circ $ im Uhrzeigersinn,
$\mathsf{B}$ – Drehung der hinteren Ebene (back) um $90^\circ $ im Uhrzeigersinn,
$\mathsf{R}$ – Drehung der rechten Ebene (right) um $90^\circ $ im Uhrzeigersinn,
$\mathsf{L}$ – Drehung der linken Ebene (left) um $90^\circ $ im Uhrzeigersinn,
$\mathsf{U}$ – Drehung der oberen Ebene (up) um $90^\circ $ im Uhrzeigersinn,
$\mathsf{D}$ – Drehung der unteren Ebene (down) um $90^\circ $ im Uhrzeigersinn,

Es hat sich eingebürgert, statt $\mathsf{F}^{-1}$ kürzer $\mathsf{F}^\prime $ zu schreiben, und wir folgen dieser Konvention. Also ist $\mathsf{F}^\prime $ die Drehung der vorderen Ebene um $90^\circ $ gegen den Uhrzeigersinn. Wie in jeder multiplikativ geschriebenen Gruppe steht $\mathsf{F}^2$ für $\mathsf{FF}$.

Wenn mehrere Züge nacheinander ausgeführt werden, lesen wir die Zugfolge $\mathsf{F}\, \mathsf{R}^\prime $ von links nach rechts: Drehe erst die vordere Ebene einmal im Uhrzeigersinn, dann die rechte Ebene einmal gegen den Uhrzeigersinn. Die Folge $\mathsf{U}\, \mathsf{R}\, \mathsf{F}$ ergibt also:

$\includegraphics[width=14cm]{rubik/erklaerung-notation-cropped}$

Weil wir bei Permutationen die entgegengesetzte Konvention verwenden – $\sigma \tau $ bedeutet, erst die Permutation $\tau $ anzuwenden, und dann $\sigma $, muss man ein bisschen aufpassen, welche Permutationen in $S_{48}$ zu den oben beschriebenen Elementen $\mathsf{F}$, $\mathsf{B}$, $\mathsf{R}$, … gehören sollen. Wenn die Drehung $\mathsf{F}$ das Plättchen $i$ des Würfels auf die Position $j$ bewegt, dann soll für $\mathsf{F}$ als Permutation betrachtet gelten, dass $\mathsf{F}$$(j) = i$ ist; das ist gerade das Inverse der Permutation, die auf den Plättchen induziert wird. Diese Definition führt dazu, dass die Konvention, Züge auf den Würfel von links nach rechts anzuwenden, kompatibel ist mit der Multiplikation von Permutationen in der symmetrischen Gruppe.

Wir können damit die Zauberwürfelgruppe $G$ als die Untergruppe von $\subset S_{48}$ definieren, die von den Permutationen erzeugt wird, die zu den oben aufgelisteten Zauberwürfeldrehungen gehören.

Natürlich lassen sich bei weitem nicht alle Permutationen aus der $S_{48}$ durch Verdrehungen des Zauberwürfels realisieren. Man kann zeigen, dass die Anzahl der Elemente von $G$ gleich

\[ 43\, 252\, 003\, 274\, 489\, 856\, 000 \]

ist, also ungefähr $43\cdot 10^{36}$, $43$ Trillionen. Dies ist also die Anzahl möglicher Positionen des Zauberwürfels. Das ist eine ganze Menge, aber viel weniger als $\# S_{48}= 48! \approx 12 \cdot 10^{60}$, in Ziffern ausgeschrieben:

\[ 12\, 413\, 915\, 592\, 536\, 072\, 670\, 862\, 289\, 047\, 373\, 375\, 038\, 521\, 486\, 354\, 677\, 760\, 000\, 000\, 000. \]

Den Würfel lösen zu können, bedeutet sozusagen, ein Erzeugendensystem der Gruppe $G$ zu kennen, das kontrolliert einzelne Steine austauscht/bewegt, so dass man sich schrittweise von einer beliebigen Ausgangsposition zum Ursprungszustand des Würfels vorarbeiten kann. Je nachdem, wie viele Zugfolgen sich zu merken man bereit ist, kann man die Sache ziemlich schnell durchführen: Der Weltrekord liegt bei unter 4 Sekunden (für das Drehen des Würfels; eine (kurze) Zeit, in der sich der Löser den verdrehten Würfel vorher anschauen durfte, nicht mitgerechnet).

Es ist offensichtlich, dass die Gruppe $G$ nicht kommutativ, also insbesondere nicht zyklisch ist. Das bedeutet, dass es »leider« nicht ein Gruppenelement, also eine einzige Zugfolge gibt, die aus jeder Position, geeignet oft angewandt, die Ausgangsstellung wiederherstellen würde.

Hier ein einfaches »Kochrezept«, um den Zauberwürfel aus jeder Position wieder in die Ausgangsstellung zu »drehen«. Im wesentlichen handelt es sich um die Lösung die 1981 von der Zeitschrift Der Spiegel veröffentlicht wurde (Nr. 4/1981, S. 183/184). Siehe auch cube3x3.com. Es gibt natürlich viele Alternativen. Wenn es schneller gehen soll: Siehe die Links zu Speed-cubing-Verfahren weiter unten.

Wir verwenden die folgende Notation: ${}^gh := ghg^{-1}$ ist die Konjugation von $h$ mit $g$. Mit $[g,h] : = ghg^{-1}h^{-1}$ bezeichnen wir den sogenannten Kommutator der Elemente $g$, $h$, der sozusagen misst, ob $g$ und $h$ miteinander kommutieren. Zum Beispiel ist also ${}^{\mathsf F}[\mathsf{R}, \mathsf{U}]$ eine Kurzschreibweise für $\mathsf{F} \mathsf{R}\mathsf{U}\mathsf{R}^\prime \mathsf{U}^\prime \mathsf{F}^\prime $, und ${}^{\mathsf{L}^\prime \mathsf{U}}\mathsf{R}^\prime $ eine andere Art, das Element $\mathsf{L}^\prime \mathsf{U} \mathsf{R}^\prime \mathsf{U}^\prime \mathsf{L}$ zu schreiben. Mit diesen Bezeichnungen lassen sich alle Zugfolgen, die in dem folgenden Lösungsrezept benutzt werden, ziemlich kurz und strukturiert angeben. (Vergleiche zum Beispiel Lemma 8.37.)

\includegraphics[width=6cm]{rubik/mittlere-ebene-mirror-cropped}

\includegraphics[width=6cm]{rubik/mittlere-ebene-cropped}

Aus mathematischer Sicht interessanter als das Lösungsrezept an sich sind strukturelle Eigenschaften der Gruppe $G$. Dafür führen wir jetzt noch einige Beispiel an. Lemma 8.54 besagt in diesem Kontext, dass jede Zugfolge, wenn man sie oft genug wiederholt, wieder zur Ausgangsposition führt. Das kann eine ganze Weile dauern: Die maximale Ordnung eines Elements in $G$ ist $1260$, ein Beispiel für ein Element dieser Ordnung ist $\mathsf{R} \mathsf{U}^2 \mathsf{D}^\prime \mathsf{B} \mathsf{D}^\prime $.

Erst im Jahr 2014 wurde gezeigt, dass es in jeder Position des Zauberwürfels möglich ist, die Ausgangsstellung mit 26 oder weniger einzelnen Drehungen (also $\mathsf{F}$, $\mathsf{F}^\prime $, $\mathsf{R}$, …) wiederherzustellen. Wenn man auch Halbdrehungen (d.h. $\mathsf{F}^2$, usw.) zulässt, dann genügen $20$ Züge. Diese Zahl wird von »Cubern« auch als God’s number bezeichnet.

Wenn wir die »Orientierung« der einzelnen Würfelteile vernachlässigen und nur die Position der Teile betrachten, haben wir es nur mit den $8$ Eckteilen und $12$ Kantenteilen zu tun. Wir nummerieren die $20$ Positionen dieser Teile durch und können dann jedem Würfelzug eine Permutation dieser $20$ Positionen zuordnen. Wir erhalten damit einen Gruppenhomomorphismus $G\to S_{20}$ (wobei wir, ähnlich wie zu Beginn, die Elemente von $G$ auf die inverse Permutation abbilden).

Das Bild dieses Homomorphismus liegt in der Untergruppe $A_{20}$. Diese ist definiert als der Kern des Signum-Homomorphismus $\operatorname{sgn}\colon S_{20}\to \{ 1, -1\} $ und heißt die alternierende Gruppe.

Um zu zeigen, dass das Bild des Homomorphismus $G\to S_{20}$ in $A_{20}$ liegt, genügt es zu zeigen, dass die Erzeuger $\mathsf{F}, \mathsf{B}, \mathsf{L}, \mathsf{R}, \mathsf{U}, \mathsf{B}$ auf Elemente in $A_{20}$ abgebildet werden. Die Rechnung dafür ist für alle diese Elemente im Prinzip dieselbe; das Bild in $S_{20}$ ist jeweils ein Produkt von $2$ Zykeln der Ordnung $4$ ($4$ Ecksteine und $4$ Kantensteine werden jeweils zyklisch vertauscht), und dieses hat Signum $1$.

Da alle Transpositionen Signum $-1$ haben, enthält $A_{20}$ keine Transpositionen. Das genannte Ergebnis impliziert, dass es keine Zugfolge gibt, die zwei Würfelteile vertauscht, aber alle anderen Würfelteile am selben Platz belässt. Die in diesem Sinne einfachsten Zugfolgen sind also Zugfolgen, die alle bis auf drei Würfelteile an ihrem Platz lassen; ein Beispiel dafür ist das Element ${}^\mathsf {U}\mathsf{R}\, {}^\mathsf {L^\prime U}\mathsf{R^\prime }$ von $G$, das in Schritt (3c) des Lösungsrezepts vorkommt und (nur) drei der Ecksteine der oberen Ebene bewegt. (Die Zugfolgen in den Schritten (2) und (3b) vertauschen zwei Kantensteine, bewegen aber auch noch andere Steine.)

Der erwähnte Homomorphismus $G\to S_{20}$ ist nicht injektiv: Es gibt Zugfolgen, die den Würfel verändern, aber alle Steine an ihrem Platz lassen. Es wird also nur bei einigen Steinen die Orientierung verändert. Man kann auch zeigen, dass es nicht möglich ist, alle Steine an ihrem Platz zu lassen und nur bei einem einzigen die Orientierung zu verändern.

Man kann die Struktur der Zauberwürfelgruppe $G$ ganz explizit beschreiben, sie ist isomorph zur Gruppe

\[ ((\left.\mathbb Z\middle /3\right.)^7 \times (\left.\mathbb Z\middle /2\right.)^{11}) \rtimes ((A_8\times A_{12}) \rtimes \left.\mathbb Z\middle /2\right.), \]

wobei $\times $ das Produkt von Gruppen bezeichnet (Beispiel 8.5) und $\rtimes $ das halbdirekte (oder semi-direkte) Produkt – eine dem Produkt ähnliche Konstruktion, die wir hier nicht näher besprechen wollen. Die Gruppen $A_8$ und $A_{12}$ sind die alternierenden Gruppen, also der Kern der Signum-Abbildung auf $S_8$ bzw. auf $S_{12}$.

8.5.4 Gruppentheorie in anderen Disziplinen

Gruppentheorie spielt auch in vielen anderen Wissenschaften, besonders natürlich in den Naturwissenschaften, eine wichtige Rolle. Wir belassen es hier bei einigen Andeutungen und Literaturhinweisen:

Chemie. Symmetrieüberlegungen sind in mehreren Bereichen der Chemie essenziell, beispielsweise bei der Untersuchung von Molekülstrukturen, oder von Kristallen.

Literatur:

G. James, M. Liebeck, Representations and Characters of Groups, Cambridge Univ. Press 2005. Kapitel 32 (nach einer Menge Mathematik zur Vorbereitung) hat den Titel An application of representation theory to molecular vibration.

J. P. Serre, Linear representations of finite groups, Springer 1977. Dieser Klassiker (ursprünglich auf französisch, und es gab auch eine deutsche Übersetzung) ist aus einer Vorlesung entstanden, die für Chemiker∗innen gehalten wurde (allerdings wird die Verbindung zur Chemie im Buch selbst kaum thematisiert).

Physik. Aus der modernen Physik ist die Gruppentheorie nicht wegzudenken. Auch Matrixgruppen wie die $GL_n(\mathbb R)$ oder $GL_n(\mathbb C)$, und dazu verwandte Gruppen wie die orthogonale Gruppe (Definition 11.25) und »unitäre Gruppen«, die wir in der Linearen Algebra 2 genauer kennenlernen werden, spielen eine wichtige Rolle.

Anthropologie. Zum Abschluss noch ein etwas kurioses Beispiel, Gruppentheorie in der Anthropologie: https://mathoverflow.net/a/25743 und wesentlich ausführlicher: https://ncatlab.org/nlab/show/kinship. (Es geht um die Erklärung/Formalisierung von Systemen von Heiratsregeln und resultierenden Verwandtschaftsbeziehungen.)

Lineare Algebra I, WS 2020/21

Inhalt

8.5 Ergänzungen *

8.5.1 Elementare Zahlentheorie

8.5.2 Darstellungstheorie

8.5.3 Verschiedenes

8.5.4 Gruppentheorie in anderen Disziplinen