Kreisteilungspolynom

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Algebra werden Kreisteilungspolynome (auch: Zykotomische Polynome) verwendet, um Unterteilungen des Einheitskreises in gleiche Teile zu untersuchen. Unter dem n-ten Kreisteilungspolynom \Phi_n versteht man dasjenige ganzzahlige Polynom größten Grades mit Leitkoeffizient 1, das x^n - 1 teilt, jedoch zu allen x^d - 1 mit d < n teilerfremd ist. Seine Nullstellen über \mathbb{C} sind genau die primitiven n-ten Einheitswurzeln e^{2 \pi \cdot \mathrm i k / n}, wobei k die zu n teilerfremden Zahlen zwischen 1 und n durchläuft.

Die Bezeichnung „Kreisteilungspolynom“ stammt vom geometrischen Problem der Kreisteilung, also der Konstruktion eines regelmäßigen Vielecks unter Beschränkung auf die Euklidischen Werkzeuge Zirkel und Lineal. Für welche n-Ecke dies gelingt, findet sich im Artikel konstruierbares Polygon.

Eigenschaften[Bearbeiten]

Die Zerlegung des n-ten Kreisteilungspolynoms in Linearfaktoren ergibt

 \Phi_n(x) = \!\!\!\! \prod_{1 \leq k \leq n\atop \operatorname{ggT}(k, n) = 1} 
 \!\!\!\! \left(x - e^{2 \pi \cdot \mathrm i k / n}\right)

Daher ist der Grad von  \Phi_n gleich \varphi(n), der Anzahl der zu n teilerfremden Zahlen unterhalb n. Die hierdurch definierte Funktion \varphi hat als Eulersche Phi-Funktion in der Zahlentheorie eine erhebliche Bedeutung.

Umgekehrt gilt die Produktdarstellung

x^n - 1 =\prod_{1\leq k\leq n} \left(x- e^{2 \pi \cdot \mathrm i k / n} \right)= \prod_{d \mid n} \prod_{1 \leq k \leq n\atop \operatorname{ggT}(k, n) = d} \left(x- e^{2 \pi \cdot \mathrm i k / n} \right) =\prod_{d \mid n} \Phi_{n/d}(x) =  \prod_{d\mid n} \Phi_d(x)

Das n-te Kreisteilungspolynom hat ganzzahlige Koeffizienten, liegt also in \mathbb{Z}[x]. Es ist dort und in \mathbb{Q}[x] ein irreduzibles Polynom, folglich Minimalpolynom jeder primitiven n-ten Einheitswurzel. Somit ist der Restklassenring \mathbb Q[x]/(\Phi_n) sogar ein Körper, und zwar der kleinste, worin der Einheitskreis der komplexen Ebene derart in n gleich lange Teile zerlegt werden kann, dass sämtliche Unterteilungspunkte zu dem Körper gehören. Er wird daher Kreisteilungskörper genannt.

Verallgemeinerung[Bearbeiten]

Der Begriff des Kreisteilungspolynoms kann auf die Einheitswurzeln über einem beliebigen Körper verallgemeinert werden. Auf diese Weise ergeben sich insbesondere alle endlichen Körper als Kreisteilungskörper über ihrem Primkörper.

Das Koeffizientenproblem[Bearbeiten]

Die ersten Kreisteilungspolynome lauten:

~\Phi_1(x) = x-1
~\Phi_2(x) = x+1
~\Phi_3(x) = x^2 + x + 1
~\Phi_4(x) = x^2 + 1
~\Phi_5(x) = x^4 + x^3 + x^2 + x + 1
~\Phi_6(x) = x^2 - x + 1
~\Phi_7(x) = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
~\Phi_8(x) = x^4 + 1
~\Phi_9(x) = x^6 + x^3 + 1
~\Phi_{10}(x) = x^4 - x^3 + x^2 - x + 1
~\Phi_{11}(x) = x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
~\Phi_{12}(x) = x^4 - x^2 + 1
~\Phi_{13}(x) = x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1
~\Phi_{14}(x) = x^6 - x^5 + x^4 - x^3 + x^2 - x + 1
~\Phi_{15}(x) = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1
~\Phi_{16}(x) = x^8 + 1

Damit folgt aus der Produktdarstellung (siehe oben):

\frac {x^n - 1}{x - 1} = x^{n-1} + x^{n-2} + \dots + x^2 + x + 1 für alle n
\frac {x^n - 1}{x + 1} = x^{n-1} - x^{n-2} + \dots + x^2 - x + 1 für alle geraden n

d. h. es entsteht ein Polynom des Grades n-1, das sämtliche Exponenten von X in absteigender Folge bis 0 enthält. Ist n eine zusammengesetzte Zahl, so läßt sich das Polynom in \mathbb{Z} weiter zerlegen. Ist n eine Primzahl, so ist das Polynom irreduzibel über ~\mathbb{Z} und ~\mathbb{Q} – aber nicht unbedingt über \mathbb{R} und niemals über \mathbb{C}, denn nach dem Gaußschen Fundamentalsatz der Algebra lässt sich jedes Polynom in lineare und quadratische Glieder zerlegen, z. B.

~\Phi_3(x) = x^2 + x + 1 = (x + \tfrac {1}{2} + \tfrac {1}{2}\sqrt{3}i)(x + \tfrac {1}{2} - \tfrac {1}{2} \sqrt{3}i) (kubische Einheitswurzel)
~\Phi_4(x) = x^2 + 1 = (x + i)(x - i)

Sogar zerlegbar in \mathbb{R} :

\begin{align} \Phi_5(x) &= x^4 + x^3 + x^2 + x + 1 = (x^2 + (\tfrac {1}{2} + \tfrac {1}{2}\sqrt{5})x + 1)(x^2 + (\tfrac {1}{2} - \tfrac {1}{2}\sqrt{5})x + 1)\\
&= \left(x + \tfrac{1}{4} + \tfrac{1}{4}\sqrt{5} + \tfrac{1}{4}\left(\sqrt{10+2\sqrt{5}}\right) i\right) \left(x + \tfrac{1}{4} + \tfrac{1}{4}\sqrt{5} - \tfrac{1}{4}\left(\sqrt{10+2\sqrt{5}}\right) i\right)\\
&\qquad \left(x + \tfrac{1}{4} - \tfrac{1}{4}\sqrt{5} + \tfrac{1}{4}\left(\sqrt{10+2\sqrt{5}}\right) i\right) \left(x + \tfrac{1}{4} - \tfrac{1}{4}\sqrt{5} - \tfrac{1}{4}\left(\sqrt{10+2\sqrt{5}}\right) i\right)                                                  
\end{align}

Ist n eine einfache ungerade Primzahl, so besteht \Phi_n(x) aus einer Summe mit lauter Plus-Gliedern, die alle Potenzen von n-1 abwärts bis 0 enthält. Ist n das Doppelte einer ungeraden Primzahl (d. h. n = 2p), so enthält \Phi_n(x) dieselben Potenzen, aber als alternierende Summe; vgl. \Phi_5(x) oder \Phi_7(x) mit \Phi_{10}(x) oder \Phi_{14}(x) oben. Man kann also die Kreisteilungspolynome regelrecht in eine gerade und eine ungerade Gruppe einteilen, die sich nur durch die Vorzeichen unterscheiden.

Ist n eine Primzahlpotenz, also pm mit p als Primzahl, dann gilt

\Phi_n(x) = \sum_{0\le k\le p-1}x^{kp^{m-1}}..

Also:

~\Phi_5(x) = x^4 + x^3 + x^2 + x +1
~\Phi_{25}(x) = x^{20} + x^{15} + x^{10} + x^5 + 1
~\Phi_{125}(x) = x^{100} + x^{75} + x^{50} + x^{25} + 1
~\Phi_{49}(x) = x^{42} + x^{35} + x^{28} + x^{21} + x^{14} + x^7 + 1 zu ~\Phi_7(x)


Ist n ein Produkt zweier ungerader Primzahlen, dann treten die ersten Unregelmäßigkeiten auf. Scheinbar willkürlich fehlen Potenzen im Polynom, d. h. haben Koeffizient 0. Dabei sind sogar große Lücken möglich wie bei \Phi_{91}(x) = \Phi_{7 \cdot 13}(x) (s. u.), ein Polynom 72. Grades mit nur 23 Summanden. Aber wenn man genauer hinschaut, dann ist die Summe noch immer streng alternierend und absolut symmetrisch aufgebaut. So fehlen bei  \Phi_8(x) eben die dritthöchste Potenz x^6 und ebenso die drittniedrigste x^2. Dieser symmetrische Aufbau gilt übrigens für alle Kreisteilungspolynome \Phi_n(x) mit n>1. Polynome mit dieser Art von Symmetrie nennt man palindromische Polynome.


~\Phi_{15}(x) = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1
~\Phi_{21}(x) = x^{12} - x^{11} + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1

Bei der geraden Version haben wir dagegen eine blockweise Verteilung der Vorzeichen, wie sie uns auch bei höheren Graden begegnen wird:

~\Phi_{30}(x) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1
~\Phi_{42}(x) = x^{12} + x^{11} - x^9 - x^8 + x^6 - x^4 - x^3 + x + 1
\begin{align} \Phi_{182}(x) = & \quad x^{72} + x^{71} - x^{65} - x^{64} - x^{59} + x^{57} + x^{52} - x^{50} + x^{46} + x^{43} - x^{39} - x^{36} - x^{33} + x^{29} + x^{26} - x^{22} \\
& + x^{20} + x^{15} - x^{13} - x^8 - x^7 + x + 1
\end{align}


Das wichtigste allerdings ist, dass bis hierhin als Koeffizienten nur -1, 0 und +1 aufgetreten sind. Und den Mathematikern schien dies so selbstverständlich, das niemand auf die Idee kam, es könnte auch ganz anders weitergehen. Und so es ist kaum glaublich, dass noch 1941 eine Entdeckung im Bereich der Schulmathematik gemacht werden konnte, in einem so elementaren Bereich wie dem Faktorisieren von Summen. Jedenfalls zerlegte der sowjetische Mathematiker Walentin Iwanow das Polynom  x^{105} - 1 und erhielt u.a. ein Polynom 48. Grades, das zur allgemeinen Überraschung zweimal den Koeffizienten -2 enthielt. [1]

\begin{align} \Phi_{105}(x) = & \quad x^{48} + x^{47} + x^{46} - x^{43} - x^{42} - 2 x^{41} - x^{40} - x^{39} + x^{36} + x^{35} + x^{34} + x^{33} + x^{32} + x^{31} - x^{28} - x^{26} \\
& - x^{24} - x^{22} - x^{20} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} - x^9 - x^8 - 2 x^7 - x^6 - x^5 + x^2 + x + 1
\end{align}

Die Entdeckung an dieser Stelle war auch kein Zufall, denn 105 ist das kleinstmögliche Produkt von drei verschiedenen ungeraden Primzahlen 3·5·7, und anstelle der alten, widerlegten Vermutung stellte er eine Behauptung auf:

  1. Bei Exponenten mit nur zwei verschiedenen ungeraden Primfaktoren enthält \Phi_n(x) nur die Koeffizienten -1, 0 und +1.
  2. Bei drei verschiedenen ungeraden Primfaktoren tritt auch der Koeffizient -2 auf.
  3. Bei vier und mehr verschiedenen ungeraden Primfaktoren können die Koeffizienten jeden beliebigen positiven oder negativen Wert annehmen.

Auch bei \Phi_{105}(x) fällt wieder die blockweise Verteilung der Vorzeichen auf: 3x Plus , 5x Minus, 6x Plus, 5x Minus, 6x Plus, 5x Minus, 3x Plus. Dabei scheint die Zahl der positiven Glieder am Anfang und Ende dem kleinsten Primfaktor zu entsprechen: \Phi_{105}(x) = \Phi_{3 \cdot 5 \cdot 7}(x) mit drei, \Phi_{385}(x) = \Phi_{5 \cdot 7 \cdot 11}(x) mit fünf, \Phi_{1001}(x) = \Phi_{7 \cdot 11 \cdot 13}(x) mit eben 7 Positivgliedern usw. Die gerade Version zeigt eine kleinteilige Verteilung der Vorzeichen, die streckenweise fast alternierend ist:

\begin{align} \Phi_{210}(x) = & \quad x^{48} - x^{47} + x^{46} + x^{43} - x^{42} + 2 x^{41} - x^{40} + x^{39} + x^{36} - x^{35} + x^{34} - x^{33} + x^{32} - x^{31} - x^{28} - x^{26} \\
& - x^{24} - x^{22} - x^{20} - x^{17} + x^{16} - x^{15} + x^{14} - x^{13} + x^{12} + x^9 - x^8 + 2 x^7 - x^6 + x^5 + x^2 - x + 1
\end{align}

Nicht klar ist, welche Exponenten Iwanow überprüft hat. Und während \Phi_{105}(x) noch in zwei bis drei Stunden von Hand auszurechnen ist, wächst der Rechenaufwand bei höheren Exponenten rapide an; immerhin war 1941 der Computer noch nicht erfunden und es herrschte Krieg. Und so sind seine Behauptungen 1 und 3 noch heute gültig, während seine 2. Behauptung gleich beim nächsten Exponenten versagt. Denn \Phi_{165}(x) = \Phi_{3 \cdot 5 \cdot 11}(x) präsentiert uns gleich zehnmal den Koeffizienten +2, aber keinmal -2. Und \Phi_{231}(x) = \Phi_{3 \cdot 7 \cdot 11}(x) hat sogar nur die Koeffizienten -1, 0 und +1 –- ebenso wie viele danach.

\begin{align} \Phi_{165}(x) = & \quad x^{80} + x^{79} + x^{78} - x^{75} - x^{74} - x^{73} - x^{69} - x^{68} - x^{67} + x^{65} + 2 x^{64} + 2 x^{63} + x^{62} - x^{60} - x^{59} - x^{58} \\
& - x^{54} - x^{53} - x^{52} + x^{50} + 2 x^{49} + 2 x^{48} + 2 x^{47} + x^{46} - x^{44} - x^{43} - x^{42} - x^{41} - x^{40} - x^{39} - x^{38} \\
& - x^{37} - x^{36} + x^{34} + 2 x^{33} + 2 x^{32} + 2 x^{31} + x^{30} - x^{28} - x^{27} - x^{26} - x^{22} - x^{21} - x^{20} + x^{18} + 2 x^{17} \\
& + 2 x^{16} + x^{15} - x^{13} - x^{12} - x^{11} - x^7 - x^6 - x^5 + x^2 + x + 1
\end{align}


Dafür bringt \Phi_{385}(x) = \Phi_{5 \cdot 7 \cdot 11}(x) in seinen 177 Summanden nicht nur den erwartbaren Eingangsblock mit 5 positiven Gliedern, sondern zum ersten Mal treten -2 und +2 im Polynom gemeinsam auf. Und als Höhepunkt überrascht uns der zentrale Mittelblock mit den drei Mittelgliedern mit Koeffizient -3.

\begin{align} \Phi_{385}(x) = & \quad x^{240} + x^{239} + x^{238} + x^{237} + x^{236} - x^{233} - x^{232} - x^{231} - x^{230} - 2 x^{229} [\dots] \\
& [\dots] + x^{134} + x^{133} + 2 x^{132} + 2 x^{131} + 2 x^{130} + 2 x^{129} + 2 x^{128} + x^{127} + x^{126} - x^{124} - 2 x^{123} -  2 x^{122} - 3 x^{121} \\
&  - 3 x^{120} - 3 x^{119} - 2 x^{118} - 2 x^{117} - x^{116} +  x^{114} + x^{113} + 2 x^{112} + 2 x^{111} + 2 x^{110} + 2 x^{109} + 2 x^{108} + x^{107} + x^{106} [\dots] \end{align}

Wenn man jetzt Iwanows 3. Behauptung überprüfen will und sich die Polynome bei Exponenten mit vier ungeraden Primfaktoren ansehen will, dann passiert zunächst nichts Neues: \Phi_{1155}(x) = \Phi_{3 \cdot 5 \cdot 7 \cdot 11}(x) empfängt uns mit einem Polynom 480. Grades, in dem die Koeffizienten -2, +2, -3 und +3 gemeinsam vorkommen. Eine genauere Überprüfung zeigt, dass diese vier Koeffizienten gemeinsam bereits im Polynom \Phi_{770}(x) = \Phi_{2 \cdot 5 \cdot 7 \cdot 11}(x) auftreten. In der Literatur und besonders in den OEIS-Listen wird generell kein Unterschied zwischen Minus und Plus gemacht und nur die Beträge verzeichnet. In OEIS A013594[2] werden sie in Verbindung gebracht mit den Exponenten ihres erstmaligen Auftretens. Dabei ist der Koeffizient der Stellenzahl der Folge, der eigentliche Exponent das Folgenglied. Bei 2 und 3 sieht man die bereits bekannten 105 bzw. 385, an vierter Stelle tritt 1365 auf. Dahinter verbirgt sich ein Polynom mit Grad 576, in dem -4 gleich achtmal (und schön symmetrisch) als Koeffizient auftritt. Dass bei steigendem Exponenten auch die Koeffizienten mit der Zeit mitwachsen, ist eigentlich logisch; aber die Art und Weise ist schon überraschend und erschreckend zugleich. Eine Rekordmarke wird drei- oder viermal nur um wenige Prozent überboten und bleibt in derselben Größenordnung, um beim nächsten Rekord um gleich mehrere Zehnerpotenzen in die Höhe zu schnellen. In der A013594-Folge und in der erweiterten Liste der Koeffizienten bis 1000[3] wiederholen sich die Rekordexponenten Dutzende oder Hunderte mal. Die Serie mit Exponent 26565 setzt noch weiter fort bis 59, aber dann springt bei \Phi_{40755}(x) der Rekord urplötzlich auf 359, und praktisch alle Koeffizienten dazwischen sind vertreten. Bei \Phi_{255255}(x) = \Phi_{3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17}(x), dem kleinstmöglichen n mit 6 verschiedenen ungeraden Primfaktoren, ist -532 erreicht (bei 92160.Grad).[4] Die 1000er-Liste endet ab 585 mit einer langen Serie vom Exponent 285285, und würde man sie in den Tausenderbereich fortschreiben, ginge das weiter bis zur neuen Rekordhöhe 1182. Dann aber würde die Liste vollends langweilig, denn beim Exponent 327845, der auch vorher zwischendurch auftaucht, springt der Rekord auf 31010. Wegen dieser blockartigen Sprünge ist auch keine angemessene graphische Darstellung möglich, da andauernd die Maßstäbe gewechselt werden müssen. Es wäre wünschenswert zu überprüfen, ob alle Koeffizienten zwischen 1183 und 31010 in \Phi_{327845}(x) auftreten; ganz sicher kann es nicht mehr bei \Phi_{1181895}(x) sein, denn der Rekordkoeffizient liegt bei mehr als 14 Millionen, und es ist das erste Mal, dass er den Exponenten n übersteigt. OEIS A160340[5] nennt die Liste der ersten 42 Rekordexponenten, die dazugehörige Liste der Koeffizienten steht in [6] auf der letzten Seite. Die Suche, die nur mit Großcomputern zu bewältigen ist, geht jedoch weiter, und den Rekord hält seit 15. Jan. 2011 \Phi_{99.660.932.085}(x) = \Phi_{3 \cdot 5 \cdot 11 \cdot 13 \cdot 19 \cdot 29 \cdot 37 \cdot 43 \cdot 53}(x) mit einem 88stelligen Koeffizienten. Da so genaue Angaben vorliegen, muss das Polynom in seiner vollen länge bekannt sein. Offenbar sind Polynome ganz besonders rekordverdächtig, wenn die zugehörigen Exponenten eine Faktorzerlegung aus den kleinsten Primzahlen haben; der Primfaktor 5 tritt bei allen Rekordhaltern auf. Bei Primfaktoren im Tausender- oder Millionenbereich ist dagegen der höchste auftretende Koeffizient 1 oder 2 …

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Theo Kempermann: Zahlentheoretische Kostproben. Frankfurt ²2005, S. 26, mit falscher Angabe des Koeffizienten als 2
  2. OEIS A013594
  3. Liste der Koeffizienten bis 1000
  4. Volkmar Felsch und Eckart Schmidt: Über Perioden in den Koeffizienten der KreisteilungspolynomeFn p(x). In: Math. Zeitschrift, Bd. 106, 1968, S. 267.
  5. OEIS A160340
  6. Rekordkoeffizienten (PDF; 253 kB)