Kreisteilung abstrakt

Zu Beginn dieses abstrakten Kapitels soll nun endlich das Geheimnis über die Verteilung der Vorzeichen bei den Wurzeln ganz konkret gelüftet werden. Wir gehen hier nämlich pragmatisch vor, schließlich sind die Gaußschen Perioden Summen von Einheitswurzeln $\zeta^k,$ die durch \[\zeta^k = \cos(2k\pi/p) + \I\sin(2k\pi/p)\] gegeben sind. Die Werte der Perioden sind reell. Das haben wir am Beispiel des Siebzehnecks gesehen und wir werden es in Kürze allgemein beweisen. Daher kann man für jede Periode einen Referenzwert durch Aufsummieren der entsprechenden Cosinus-Ausdrücke ausrechnen, insbesondere, wenn man ohnehin für die Periodenbildung ein Computerprogramm schreibt. Das Vorzeichen wird einfach so gesetzt, dass der Quadratwurzelausdruck mit dem zugehörigen Referenzwert übereinstimmt.

Am Beispiel der gerade berechneten Perioden $p_{3,0}$ und $p_{3,4}$ für das Siebzehneck sei das erläutert: Man hat einerseits \[p_{3,0} = \zeta^1 + \zeta^{16} = \cos(2\pi/17) + \cos(32\pi/17) = 1,86494 \eqncomma\] \[p_{3,4} = \zeta^{13} +\zeta^{4} = \cos(26\pi/17) + \cos(8\pi/17) = 0,18453 \eqndot\] und andererseits \[p_{3,0}^{\pm} = \tfrac{p_{2,0} + \sqrt{p_{2,0}^2 - 4p_{2,1}}}{2}\eqncomma\] \[p_{3,4}^{\pm} = \tfrac{p_{2,0} - \sqrt{p_{2,0}^2 - 4p_{2,1}}}{2}\eqndot\] wobei das $\pm$ andeuten soll, dass die Vorzeichensetzung vorläufig ist.

Diese Ausdrücke $p_{3,0}^{\pm}$ und $p_{3,4}^{\pm}$ kann man ebenfalls numerisch ausrechnen, wenn man die Werte für $p_{2,0}$ usw. einsetzt. Es kommt im Rahmen der Rechengenauigkeit entweder \[p_{3,0}^{\pm} = 1,86494 \quad \text{und} \quad p_{3,4}^{\pm} = 0,18453\] oder \[p_{3,0}^{\pm} = 0,18453 \quad \text{und} \quad p_{3,4}^{\pm} = 1,86494\] heraus. Im ersten Fall kann man die Vorzeichen für die Wurzeln so lassen, wie sie probeweise gesetzt wurden, im zweiten Fall muss man sie vertauschen.

Dieses Verfahren hat den weiteren Vorteil, dass man bei jedem Schritt kontrollieren kann, ob der Quadratwurzelausdruck richtig berechnet wurde, denn nach Wahl des richtigen Vorzeichens muss er im Rahmen der Rechengenauigkeit mit dem Referenzwert übereinstimmen. Man beachte, dass zum Zeitpunkt der Berechnung von Perioden einer bestimmten Stufe alle Perioden kleinerer Stufe schon bekannt sind und für die numerische Berechnung des aktuellen Quadratwurzelausdrucks verwendet werden können.

Hauptsatz

Wir nähern uns nun im Stil etwas den üblichen Mathematik-Lehrbüchern an. Dort wird nämlich zunächst der Satz  oder das Theorem , das man zeigen will, formuliert, anschließend folgt der Beweis. Oft fällt dabei die Kernaussage gleichsam vom Himmel und der Leser muss sich im Nachhinein die Motivation für das Vorgehen selbst zurechtlegen. Nach der Vorbereitung durch den konkreten Fall des Siebzehnecks ergibt sich jedoch die Formulierung des abstrakten Theorems beinahe von selbst, und wir wollen es hier in mehreren Schritten beweisen.

Wer sich mit dem experimentellen Beweis durch das Programm begnügt, kann den Rest des Kapitels getrost überspringen. Für das Verständnis des Java-Programms ist dieser Teil nicht erforderlich, er enthält aber natürlich schöne  Mathematik.

Ganz analog wie beim Siebzehneck ergibt sich daraus die Darstellung einer Gaußschen Periode der Stufe $k$ in Form eines Quadratwurzelausdrucks aus Perioden der Stufe $k-1$. Daher ist das folgende Korollar eine direkte Folge des Theorems:

Wir haben damit sozusagen die exakte Beschreibung des Abstiegs (oder besser des Aufstiegs ?) von der Periode $0$-ter Stufe, der Summe aller Einheitswurzeln $\zeta^{p-1}+\zeta^{p-2}+\dots+\zeta^2+\zeta=-1,$ zur Periode höchster Stufe, die nur noch aus den beiden Summanden $\zeta + \zeta^{p-1}$ besteht und mit $2cos(2\pi/p)$ identisch ist. Dabei besteht jeder Schritt nur aus dem Einsetzen von Quadratwurzeln und der Bildung von Linearkombinationen aus Perioden einer niedrigeren Stufe. Jeder Schritt des Abstiegs lässt sich somit als Konstruktion mit Zirkel und Lineal realisieren, so dass die Folge von Wurzelausdrücken nichts anderes als die Konstruk­tions­anwei­sung für das regelmäßige $p$-Eck darstellt.

Das Produkt Gaußscher Perioden

Wie erwähnt, gibt es für die Aussage zur Summe der Gaußschen Perioden nichts zu beweisen. Wir können uns auf die Aussage zum Produkt beschränken. Es gibt dafür eine ganze Reihe von sehr ähnlich strukturierten Beweisen, angefangen mit dem Original in [Gauß 1801], an das sich [Bachmann 1872] stark anlehnt. In [Bewersdorff 2013] wird der letzgenannte Beweis in moderne Notation übersetzt und vereinfacht.

Allerdings wollen wir noch etwas mehr zeigen. Für die Aufstellung der Gleichungen zur Lösung des Kreisteilungsproblems reicht es aus, wenn das Produkt der Perioden eine Linearkombination mit rationalen  Koeffizienten ist – und damit geben sich die Beweise in den genannten Büchern zufrieden. Im obigen Theorem haben wir aber die Koeffizienten als natürliche Zahlen  einschließlich $0$ vorausgesetzt – und das ist für uns notwendig, damit der sehr einfache Algorithmus, den wir in dem Java-Programm verwenden wollen, funktioniert.

Unser Ansatz wird in [Gottlieb 1999] verfolgt. Dort wird allerdings kein allgemeiner Beweis geführt sondern die Methode nur für den Fall des 257-Eck erläutert. Wir orientieren uns daher anfangs an [Bachmann 1872] und [Bewersdorff 2013] und später an [Gottlieb 1999].

Weil die Darstellung sonst sehr verwirrend wäre, verwenden wir statt des festen primitiven Elements $3$ in diesem Abschnitt ein allgemeines primitives Element $\omega.$ Wir haben es daher mit folgenden Größen zu tun:

Definition von $p_{n,m}$

Für die Gaußsche Periode $p_{n,m}$ suchen wir nun einen handhabbaren Ausdruck. Die 1te Periode haben wir dadurch erhalten, dass wir die $0$te Periode in Summanden mit geraden und ungeraden Potenzen von $\omega$ aufgespalten haben. Zur Vereinfachung schreiben wir jetzt nur die Menge der Exponenten, d.h. die Potenzen des primitiven Elements, und verwenden für diese Menge die gleiche Bezeichnung wie für die Periode, nur mit einem Stern versehen: \[p_{1,0}^*:= \{\omega^0, \omega^2, \dots, \omega^{2^N-2}\}\eqncomma\] \[p_{1,1}^*:= \{\omega^1, \omega^3, \dots, \omega^{2^N-1}\}\eqndot\] oder kurz: \[p_{1,0}^* = \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 0\pmod 2\}\eqncomma\] \[p_{1,1}^* = \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 1\pmod 2\}\eqndot\] Wenn wir zur 2ten Periode übergehen, entnehmen wir aus der Menge der Potenzen, die zu $p_{1,0}$ gehören, wieder die an 1ter, 3ter, 5ter Stelle usw. bzw. die an 2ter, 4ter, 6ter Stelle usw., wir betrachten also jetzt die $k$-ten Potenzen des Primitiven Elements, aufgeteilt$\pmod 4$: \[p_{2,0}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 0\pmod 4\}\eqncomma\] \[p_{2,2}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 2\pmod 4\}\eqncomma\] \[p_{2,1}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 1\pmod 4\}\eqncomma\] \[p_{2,3}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv 3\pmod 4\}\eqndot\] allgemein: \[p_{n,m}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv m\pmod{2^n}\}\eqndot\] woraus folgt \[p_{n,m}=\sum_{\omega^k \in p_{n,m}^*}{\zeta^{\omega^k}}\eqncomma\] und damit ist endlich die merkwürdige Reihenfolge der Nummerierung der $p_{n,m}$ erklärt.

Aufspalten von Perioden

Wir wollen nun zeigen, wie die Aufspaltung einer Periode $p_{n-1,m}$ sich in dieser Notation darstellt. Es ist \[p_{n-1,m}^*= \{\omega^k: 0\leq k\lt 2^N, \quad k \equiv m\pmod{2^{n-1}}\}\eqncomma\] oder nach Definition der Kongruenzrelation ($\omega^k$ ist dabei$\pmod{p}$ zu reduzieren): \[p_{n-1,m}^*= \{\omega^k: k = m + x2^{n-1}, \quad x=0,1,2,\dots\}\eqndot\] Die Aufspaltung trennt gerade und ungerade Werte von $x$: \[p_{n,m_0}^*= \{\omega^k: k = m + x2^{n-1}, \quad x=0,2,4,\dots\}\eqncomma\] und \[p_{n,m_1}^*= \{\omega^k: k = m + x2^{n-1}, \quad x=1,3,5,\dots\}\eqndot\] In der ersten Menge nehmen wir einen $2$er-Faktor des geraden $x$ mit zu der Potenz $2^{n-1}$, wodurch $x$ die Werte $0,1,2,\dots$ annimmt. \[p_{n,m_0}^*= \{\omega^k: k = m + x2^{n}, \quad x=0,1,2,\dots\}\eqndot\] In der zweiten Menge, für ungerades $x$, spalten wir auf: $x2^{n-1}=2^{n-1}+(x-1)2^{n-1},$ wodurch $x-1$ gerade wird und analog wie oben behandelt werden kann: \[p_{n,m_1}^*= \{\omega^k: \quad k = m + 2^{n-1} + x2^{n}, \quad x=0,1,2,\dots\}\eqndot\] Wenn wir alles in die Schreibweise mit Kongruenzen zurückübersetzen, sehen wir: \[p_{n,m_0}^*=p_{n,m}^*\] und \[p_{n,m_1}^*=p_{n,m+2^{n-1}}^*\eqndot\]

In den obigen Mengen haben wir keine Grenzen für $x$ spezifiziert. Das ist auch nicht nötig, weil wir gefordert hatten, dass $\omega^k\pmod{p}$ reduziert wird. Dadurch ergeben sich die Grenzen automatisch, denn wir können zeigen, dass $\omega^{m+x2^n}\pmod{p}$ alle verschieden sind, wenn $0 \leq x \leq 2^{N-n} - 1.$ Dazu wenden wir die erste bemerkenswerte Eigenschaft aus dem vorangehenden Kapitel an, nämlich dass $\omega^{m+x2^n} \equiv \omega^{m+x'2^n} \pmod{p}$ genau dann, wenn $m+x2^n \equiv m+x'2^n \pmod{p-1}.$ Daher können wir rechnen: \begin{align*} m+2^nx &\equiv m+2^nx' \pmod{2^N}\\ 2^nx &\equiv 2^nx' \pmod{2^N}\\ \end{align*} Hier kann man natürlich nicht einfach kürzen, denn $2^N$ ist keine Primzahl und somit ist der Restklassenring $\mathbb{Z}/{2^N}\mathbb{Z}$ kein Körper. Wir können aber die im vorigen Kapitel abgeleitete Divisionsregel in Restklassen mit $\gcd(2^n,2^N) =2^n$ benutzen und erhalten \[ x \equiv x' \pmod{2^{N-n}} \eqndot \] Folglich gibt es $2^{N-n}$ verschiedene Exponenten $\omega^k\pmod{p},$ und wir haben tatsächlich eine komplette Gaußsche Periode.

Gaußsche Perioden sind reelle Zahlen

Nach dieser Vorbereitung sind wir jetzt in der Lage, allgemein zu zeigen, dass der numerische Wert derartiger Perioden reell ist. Wie wir gesehen haben, ist dies eine unverzichtbare Voraussetzung dafür, dass die Wurzelausdrücke für die Perioden wirklich konstruierbare Punkte darstellen.

Unter Verwendung der oben eingeführten Notation schreiben wir eine Periode $n$-ter Stufe in Form der folgenden Summe: \[p_{n,m} = \sum_{\genfrac{}{}{0pt}{1}{0\leq k \lt 2^N}{k \equiv m\pmod{2^n}}}\zeta^{\omega^k}\eqndot \] Zu jeder Einheitswurzel $\zeta^{\omega^k}$ ist $\zeta^{-\omega^k}$ die konjugiert komplexe Wurzel. Aufgrund der im vorigen Kapitel abgeleiteten zweiten bemerkenswerten Eigenschaft eines primitiven Elements ist aber \[-\omega^k \equiv \omega^{(p-1)/2}\omega^k \equiv \omega^{(p-1)/2+k}\pmod{p} \] und wegen $(p-1)/2 = 2^N/2 = 2^{N-1}$ haben wir \[-\omega^k \equiv \omega^{2^{N-1}+k}\pmod{p} \eqndot\] Nun ist $2^n$ ein Teiler von $2^{N-1}$ so dass mit $k \equiv m\pmod{2^n}$ gilt $k + 2^{N-1} \equiv m\pmod{2^n}.$ Am Wert der obigen Summe ändert sich folglich nichts, wenn wir $k' = k+2^{N-1}$ als neuen Summationsindex nehmen (lediglich die Grenzen verschieben sich), also statt der Einheitswurzeln ihre Konjugierten summieren. Daher ist $p_{n,m}$ zu sich selbst konjugiert und mithin reell.

Beweis des Theorems – Schritt Eins

Wie wir oben gesehen haben führt die Aufspaltung von $p_{n-1,m}$ auf die beiden Perioden $p_{n,m}$ und $p_{n,m+2^{n-1}}$ und genau das Produkt dieser Perioden interessiert uns.

Wir erinnern uns, was wir eigentlich zeigen wollen, nämlich, dass \[ p_{n,m} \cdot p_{n,m+2^{n-1}} = c_0\,p_{n-1,0} + c_1\,p_{n-1,1} + \dots + c_g\,p_{n-1,g} \] mit $c_0, c_1, \dots , c_g \in \mathbb{N}_o.$ In anderen Worten: Das Produkt der beiden uns interessierenden Perioden der Stufe $n$ ist als Linearkombination aus Perioden der Stufe $n-1$ mit positiven ganzen Koeffizienten (oder 0) darstellbar.

Um eine Idee zu bekommen, wie man das Theorem beweisen kann, gehen wir zurück zum Beispiel des 17-Ecks und erinnern uns, wie wir dort herausgefunden haben, dass das Produkt $p_{1,0} \cdot p_{1,1}$ genau is $4$ mal die Periode $p_{0,0}$ ist. Wir haben die verschiedenen Produkte oder genauer ihre Exponenten in der Multiplikationstabelle gezählt. Wenn man die entsprechenden Felder mit einem Bleistift markiert hat (sofern erforderlich), konnte man sehen, dass die Multiplikationstabelle in $4$ disjunkte Bereiche zerfällt, deren jeder alle Einheitswurzeln (oder Exponenten) der Periode $p_{0,0}$ enthält. Wenn man die Felder so einfärbt, dass alle, die zur selben Instanz der Periode $p_{0,0}$ gehören, gleich gefärbt sind, bekommt man folgende Tabelle:

Natürlich haben wir hier nicht irgendwie die Exponenten den Perioden zugeordnet. Das wäre ziemlich dumm und hilft uns nicht beim allgemeinen Beweis – wir werden das Färbeschema gleich erläutern. Aber zunächst müssen wir uns vergewissern, dass jedes Feld tatsächlich eine Einheitswurzel (genauer deren Exponenten) enthält, die zu einer Periode niedrigerer Stufe gehört (in dem Beispiel $p_{0,0}$), insbesondere darf der Exponent nicht $0$ sein.

Dass das wirklich passieren kann, sieht man, wenn man zwei andere Perioden aus dem vorangehenden Kapitel multipliziert. nehmen wir etwa $p_{1,0} \cdot p_{1,0} = p_{1,0}^2$:

Man beachte, dass der Exponent $0$ die Einheitswurzel $\zeta^0 = 1$ ergibt. Wenn man hier wieder mit spitzem Bleistift auszählt, findet man $$p_{1,0}^2 = 3p_{1,0}+4p_{1,1}+8 = 3p_{1,0}+4p_{1,1}-8(p_{1,0} + p_{1,1}) = -5p_{1,0} - 4p_{1,1},$$ wobei die Zahl $8$ durch $-8\cdot p_{0,0}$ ersetzt wurde^[1]. So erhält man immerhin eine Darstellung des Produkts als Linearkombination von Perioden der gleichen Stufe mit ganzzahligen Koeffizienten. Als ersten Schritt werden wir jetzt beweisen, dass diese schwächere Darstellung tatsächlich immer möglich ist:

Beweis von Lemma 1

Dazu erinnern wir uns, dass die Anzahl der Summanden der Periode der Stufe $0$ gleich $2^N$ ist, in der Stufe $1$ ist dies $2^N/2 = 2^{N-1}$ usw. in der Stufe $n$ also $2^{N-n}.$ Mit der oben eingeführten Notation haben wir für die Potenzen von $\omega^k$: \[p_{n,m}^* = \{\omega^m, \omega^{m+2^n}, \omega^{m+2\cdot 2^n}, \dots, \omega^{m+(2^{N-n}-1)2^n}\}\]

Zur Abkürzung setzen wir \[L_n := 2^{N-n}-1\eqncomma\] da der Ausdruck $2^{N-n}-1,$ also die um eins verminderte Anzahl der Summanden der Periode $n$-ter Stufe sehr häufig vorkommt und sehr umständlich zu schreiben ist. Das $N$ als Exponent der Fermatsche Primzahl $p=2^N+1$ sei ein für alle Mal fixiert, es geht daher in die Abkürzung nicht ein.

Damit ergibt sich für die Periode selbst: \[p_{n,m} = \zeta^{\omega^m}+\zeta^{\omega^{m+2^n}}+\zeta^{\omega^{m+2\cdot 2^n}}+\dots+\zeta^{\omega^{m+L_n 2^n}} \] Dies schreibt man kürzer: \[p_{n,m} = \sum_{s=0}^{L_n}\zeta^{\omega^{m+s 2^n}} = \sum_{s=0}^{L_n}\zeta^{\omega^{m}\omega^{s 2^n}} \] Für das Produkt zweier Perioden hat man somit: \begin{align*} p_{n,m}p_{n,k} &= (\sum_{s=0}^{L_n}\zeta^{\omega^{m}\omega^{s 2^n}})(\sum_{t=0}^{L_n}\zeta^{\omega^{k}\omega^{t 2^n}})\\ &= \sum_{s=0}^{L_n}\sum_{t=0}^{L_n}\zeta^{\omega^{m}\omega^{s 2^n}+\omega^{k}\omega^{t 2^n}}\\ \end{align*} Wir ersetzen nun den Summationsindex in der zweiten Summe durch $t=s+h$ und summieren über $h.$ Das ändert am Wert der Summe nichts, da die Exponenten von $\omega$ ohnehin nur$\pmod{p}$ ausgewertet werden: $$ \begin{align*} p_{n,m}p_{n,k} &= \sum_{s=0}^{L_n}\sum_{h=0}^{L_n}\zeta^{(\omega^{m}+\omega^{k}\omega^{h 2^n})\omega^{s 2^n}}\\ &= \sum_{h=0}^{L_n}\sum_{s=0}^{L_n}\zeta^{(\omega^{m}+\omega^{k}\omega^{h 2^n})\omega^{s 2^n}}\\ &= \sum_{h=0}^{L_n} p_{n,m_h}^{\circ}\\ \end{align*} $$ Wir schreiben $p_{n,m_h}^{\circ}$ für den Ausruck unter dem Summenzeichen, um anzudeuten, dass wir noch nicht wissen, ob es sich dabei wirklich um eine Gaußsche Periode handelt. Voraussetzung dafür ist nämlich, dass für den Term im Exponenten gilt \[\omega^{m}+\omega^{k}\omega^{h 2^n} \not\equiv 0 \pmod{p} \eqncomma\] denn dann folgt aus der Definition des primitiven Elements $\omega,$ dass eine Darstellung der Form \[\omega^{m}+\omega^{k}\omega^{h 2^n} \equiv \omega^{m_h} \pmod{p}\] existiert mit einem geeigneten Exponenten $m_h.$ In diesem Fall können wir folglich für $p_{n,m_h}^{\circ}$ die Gaußsche Periode $p_{n,m_h}$ einsetzen.

Im anderen Fall, falls $\omega^{m}+\omega^{k}\omega^{h 2^n} \equiv 0 \pmod{p}$ ist, sind in der Summe der Einheitswurzeln alle Exponenten $0,$ alle Potenzen also $1$ und wir haben $p_{n,m_h}^{\circ}=2^{N-n}.$

Nun ist aber die Summe aller  Gaußschen Perioden der Stufe $n$ gleich der Gaußschen Periode der Stufe $0$ und diese hatte den Wert $-1,$ daher lässt sich $2^{N-n}$ schreiben als \[2^{N-n} = -2^{N-n}\sum_{s=0}^{2^n-1} p_{n,s} \] und wir haben insgesamt eine Darstellung des Produkts zweier beliebiger  Gaußscher Perioden der Stufe $n$ als Linearkombination von Perioden der Stufe $n$ mit ganzzahligen Koeffizienten  gefunden. ∎

Die Frage ist allerdings, unter welchen Bedingungen der Fall $\omega^{m}+\omega^{k}\omega^{h 2^n} \equiv 0 \pmod{p}$ überhaupt vorkommen kann. Wir formen um: \begin{align*} \omega^{m}+\omega^{k}\omega^{h 2^n} &\equiv 0 \pmod{p} \\ \omega^{m} &\equiv -\omega^{k+h 2^n} \pmod{p} \\ \end{align*} Nun ist aber per Definitionem $\omega^{k+h 2^n} \in p_{n,k}^*$ und, wie wir weiter oben gesehen haben, damit auch $-\omega^{k+h 2^n} \in p_{n,k}^*$ und folglich $\omega^{m} \in p_{n,k}^*.$ Der Fall $\omega^{m}+\omega^{k}\omega^{h 2^n} \equiv 0 \pmod{p}$ kann also nur dann eintreten, wenn $p_{n,m} = p_{n,k},$ wenn wir also zwei gleiche Perioden multipliziert haben. Wenn also $m \neq k$ gilt, sind die Vorzeichen in de Summe \[p_{n,m}p_{n,k} = \sum_{h=0}^{L_n} p_{n,m_h} \] positiv oder $0$ und wir haben

Das gilt insbesondere für $p_{n,m}p_{n,m+2^{n-1}},$ den Fall, der uns am meisten interessiert. Wir wissen zudem, wie oft jede Periode $p_{n,m_h}$ in der Summe vorkommt, nämlich so oft, wie es verschiedene Lösungen der Kongruenz^[2] \[\omega^{m_h} \equiv \omega^{m}+\omega^{k}\omega^{h 2^n} \pmod{p}\] für den gleichen Wert von $m_h\pmod{p}$ und unterschiedliche Werte von $h$ gibt. Diese Vielfachheit des Summanden $p_{n,m_h}$ ist auf jeden Fall eine positive ganze Zahl oder $0.$

Beweis des Theorems – Schritt Zwei

Das Produkt ist eine Summe von Summanden der Form \[\zeta^{\omega^a}\zeta^{\omega^b} = \zeta^{\omega^a+\omega^b}\eqncomma\] wobei die Exponenten$\pmod{p}$ zu nehmen sind. Speziell interessieren wir uns für \[a \equiv m\pmod{2^n} \quad \text{und} \quad b \equiv m+2^{n-1}\pmod{2^n}\] oder nach Definition der Kongruenz \[a = 2^nx+m\] und \[b = 2^ny+m+2^{n-1}\] mit geeigneten $x,y \in \mathbb{N}_o.$

Wenn wir unsere Multiplikationstafel für diesen generellen Fall $p_{n,m} \cdot p_{n,m+2^{n-1}}$ aufschreiben, erhalten wir

Wegen Lemma 2 wissen wir, dass in unserem speziellen Fall der Term $\omega^a+\omega^b = \omega^{2^nx + m} + \omega^{2^ny+m+2^{n-1}}$ nicht $0$ sein kann, also gibt es ein $\omega^s$ mit $\omega^s = \omega^a + \omega^b,$ wobei dieses $\omega^s$ Exponent eines Summanden einer Periode der Stufe $n$ ist. Weil diese Periode Tochter einer Periode der Stufe $n-1$ ist, ist $\omega^s$ somit auch Exponent eines Summanden einer Periode der Stufe $n-1.$ Folglich können wir unsere Abzählung auf jeden Fall mit einem Summanden aus einer Periode der Stufe $n-1$ beginnen, wenn wir irgendein Produkt aus der Multiplikationstabelle herausgreifen. Aber wir wissen schon, wie man in solch einer Periode von einem Summanden zum nächsten kommt, nämlich indem man den Summanden (die Einheitswurzel) mit $\omega^{2^{n-1}}$ potenziert oder äquivalent den Exponenten mit $\omega^{2^{n-1}}$ multipliziert.

Wir betrachten also jetzt, wie sich $\omega^s$ verhält, wenn man das Produkt $\omega^s \cdot \omega^{2^{n-1}}$ berechnet: $$ \begin{align*} \omega^{s+2^{n-1}} &\equiv (\omega^a+\omega^b)\omega^{2^{n-1}}&\pmod{p}\\ &\equiv \omega^{2^nx+m+2^{n-1}} + \omega^{2^ny+m+2^{n-1}+2^{n-1}}&\pmod{p}\\ &\equiv \omega^{2^nx+m+2^{n-1}} + \omega^{2^ny+m+2^{n}}&\pmod{p}\\ &\equiv \omega^{2^n(y+1)+m}+\omega^{2^nx+m+2^{n-1}}&\pmod{p}\\ &\equiv \omega^{a'}+\omega^{b'}&\pmod{p} \end{align*} $$ wobei $a'$ and $b'$ Exponenten sind, die in $p_{m,n}$ bzw. $p_{m,n+2^{n-1}}$ vorkommen.

Wenn man diese Multiplikation wiederholt, erhält man $\omega^{s+2(2^{n-1})},$ bei nochmaliger Wiederholung $\omega^{s+3(2^{n-1})}$ usw. Mit anderen Worten, die Exponenten von $\omega$ wandern durch die ganze Restklasse von $s \pmod{2^{n-1}},$ daher wandern die zugehörigen Einheitswurzeln durch die Summanden der Periode $p_{n-1,s}.$

Für jede Multiplikation kann man die obige Rechnung ganz analog ausführen und beobachten, wie sich dabei $x$ und $y$ verändern. Man erhält folgende Tabelle: \[ \begin{array}{ccccccccc} \omega^s &\rightarrow& \omega^{s+2^{n-1}} &\rightarrow& \omega^{s+2(2^{n-1})} &\rightarrow& \omega^{s+3(2^{n-1})} &\rightarrow& \dots \\ x &\rightarrow& y+1 &\rightarrow& x+1 &\rightarrow& y+2 &\rightarrow& \dots \\ y &\rightarrow& x &\rightarrow& y+1 &\rightarrow& x+1 &\rightarrow& \dots \\ \end{array} \] Weil die $x$ und $y$ als Spalten- bzw. Zeilenindex in der Multiplikationstabelle aufgefasst werden können, ist dies genau das System, nachdem wir unser Beispiel oben eingefärbt haben. Man greift ein Feld in Spalte $x$ und Zeile $y$ heraus, das zu einem Produkt mit Exponenten $\omega^s$ gehört, dann springt man zum Feld $(y+1,x),$ das zu $\omega^s \cdot \omega^{2^{n-1}}$ gehört, dann zu $(y+1,x+1)$ usw. Da die $x$ und $y$ die Exponenten einer Periode der Stufe $n$ durchnummerieren, müssen sie natürlich$\pmod{2^{N-n}}$ genommen werden. Das ist aber gerade Höhe und Breite der Multiplikationstabelle. Wenn man also bei dem obigen Verfahren die Tabelle rechts (unten) verlässt, muss man sie auf gleicher Höhe (Breite) links (oben) wieder betreten. Der Prozess wiederholt sich also nach $2^{N-n+1}$ Schritten und wir haben eine komplette Periode der Stufe $n-1$ gefärbt. Anschließend greifen wir ein Feld heraus, das noch nicht gefärbt wurde und wiederholen den ganzen Prozess.

Es ist sehr instruktiv, dem Weg eines bestimmten Produkts in dem obigen Beispiel zu folgen, wenn man sukzessiv die Multiplikationen mit $\omega^{2^{n-1}}$ ausführt. Da in dem Beispiel zwei Perioden der Stufe $1$ multipliziert werden, ist der Faktor einfach das primitive Element $3$ und die Multiplikation wird $\pmod{17}$ ausgeführt, mit anderen Worten, man macht einen Schritt nach rechts in der Reihe der Exponenten der $0$ten Gaußschen Periode: \[ 1,3,9,{10},{13},{5},{15},{11},{16},{14},{8},{7},{4},{12},{2},{6} \] und von $6$ zurück zu $1.$ Wenn man etwa mit der hellblau unterlegten $7,$ die zu dem Paar $(11,13)$ gehört, beginnt und weiter zu den hellblau unterlegten $4, 12$ usw. geht, machen die Sprünge hin und her über die Diagonale die obige Rechnung geradezu sinnlich erfahrbar.

Bleibt zu zeigen, dass der geschilderte Prozess die Multiplikationstabelle tatsächlich in disjunkte Mengen aufspaltet. Dass jede dieser Mengen die Exponenten einer Periode der Stufe $n-1$ enthält, ist schon aufgrund der Konstruktion klar. Um die Disjunktheit zu zeigen, bemerken wir, dass die Folge \[ \begin{array}{ccccccccc} \omega^s &\rightarrow& \omega^{s+2^{n-1}} &\rightarrow& \omega^{s+2(2^{n-1})} &\rightarrow& \omega^{s+3(2^{n-1})} &\rightarrow& \dots \\ x &\rightarrow& y+1 &\rightarrow& x+1 &\rightarrow& y+2 &\rightarrow& \dots \\ y &\rightarrow& x &\rightarrow& y+1 &\rightarrow& x+1 &\rightarrow& \dots \\ \end{array} \] in zwei Folgen zerlegt werden kann: \[ \begin{array}{ccccccccc} \omega^s &\rightarrow& \omega^{s+2(2^{n-1})} &\rightarrow& \omega^{s+4(2^{n-1})} &\rightarrow& \omega^{s+6(2^{n-1})} &\rightarrow& \dots \\ x &\rightarrow& x+1 &\rightarrow& x+2 &\rightarrow& y+3 &\rightarrow& \dots \\ y &\rightarrow& y+1 &\rightarrow& y+2 &\rightarrow& y+3 &\rightarrow& \dots \\ \end{array} \] und \[ \begin{array}{ccccccccc} \omega^{s+2^{n-1}} &\rightarrow& \omega^{s+3(2^{n-1})} &\rightarrow& \omega^{s+5(2^{n-1})} &\rightarrow& \omega^{s+7(2^{n-1})} &\rightarrow& \dots \\ y+1 &\rightarrow& y+2 &\rightarrow& y+3 &\rightarrow& y+4 &\rightarrow& \dots \\ x &\rightarrow& x+1 &\rightarrow& x+2 &\rightarrow& x+3 &\rightarrow& \dots \\ \end{array} \] Das sind zwei diagonale Streifen in der Tabelle (wobei der Überlauf von rechts nach links bzw. unten nach oben zu berücksichtigen ist). Wenn man die Seitenlänge der Multiplikationstabelle mit $w$ bezeichnet, sind diese diagonalen Streifen Äquivalenzklassen der Relation $$ \begin{align*} (x,y) &\sim (x',y') :\iff \\ & \exists a \in \mathbb{N}_o \quad\text{mit}\quad x' - x \equiv a\pmod{w} \quad\text{und}\quad y'-y \equiv a\pmod{w} \\ \end{align*} $$ Zur Übung sollte man beweisen, dass dies wirklich eine Äquivalenzrelation ist.