Kreisteilungspolynom

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. Für welche $n$ dies unter Beschränkung auf die „Euklidischen Werkzeuge“ Zirkel und Lineal gelingt, findet sich im Artikel „Konstruierbare Polygone“.

Eigenschaften

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 $\phi (n)$, der Anzahl der zu $n$ teilerfremden Zahlen unterhalb $n$. Die hierdurch definierte Funktion $\phi$ 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$ gleichlange Teile zerlegt werden kann, dass sämtliche Unterteilungspunkte zu dem Körper gehören. Er wird daher Kreisteilungskörper genannt.

Verallgemeinerung

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

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$

Ebenso gilt:

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

$~\Phi _{4}(X)=X^{2}+1=(X+i)(X-i)$

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

$\Phi _{n}(X)=\sum _{0\leq k\leq 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 scheinbaren 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*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 auch die drittniedrigste $X^{2}$. Dies gilt übrigens für alle Kreisteilungspolynome, egal welchen Grades !

$~\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$

${\begin{aligned}\Phi _{91}(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^{13}-X^{8}+X^{7}-X+1\end{aligned}}$

Das wichtigste allerdings ist, dass bis hierhin als Koeffizienten nur -1, 0 und +1 aufgetreten sind. Und den Mathematikern schien 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 das Faktorisieren von Summen. Jedenfalls zerlegte der sowjetrussische Mathematiker W.Iwanow das Polynom $x^{105}-1$ und erhielt u.a. ein Polynom 48.Grades, das zur allgemeinen Überraschung zweimal den Koeffizienten -2 enthielt.

${\begin{aligned}\Phi _{105}(X)=&\quad X^{48}+X^{47}+X^{46}-X^{43}-X^{42}-2X^{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}-2X^{7}-X^{6}-X^{5}+X^{2}+X+1\end{aligned}}$

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 des alten Meinung stellte er nun einen neuen Satz:

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.

Nicht klar ist, welche Exponenten Iwanow alle ü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 der 1941 der Computer noch nicht erfunden (und es war Weltkrieg !). 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*5*11}(X)$ präsentiert uns gleich zehnmal den Koeffizienten +2, aber keinmal -2. Und $\Phi _{231}(X)=\Phi _{3*7*11}(X)$ hat sogar nur die Koeffizienten -1, 0 und +1 - ebenso wie viele danach.

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

Dafür bringt $\Phi _{385}(X)=\Phi _{5*7*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{aligned}\Phi _{385}(X)=&\quad X^{240}+X^{239}+X^{238}+X^{237}+X^{236}-X^{233}-X^{232}-X^{231}-X^{230}-2X^{229}[...]\\&[...]+X^{126}-X^{124}-2X^{123}-2X^{122}-3X^{121}-3X^{120}-3X^{119}-2X^{118}-2X^{117}-X^{116}+X^{114}[...]\end{aligned}}$

Dass bei anwachsendem Exponenten n auch mit der Zeit höhere Koeffizienten der Polynome erscheinen, ist nur natürlich; die Art und Weise ist aber erstaunlich und erschreckend zugleich. In OEIS A013594 werden die Koeffizienten bzw. dessen Beträge (es wird kein Unterschied zwischen - und + gemacht) in Verbindung gebracht mit den Exponenten ihres erstmaligen Auftretens. Bei 2 und 3 sieht man die bereits bekannten Exponenten 105 bzw. 385. Die weiteren Zahlen und das mehrfache Auftreten desselben Exponenten zeigen, dass der Anstieg sprunghaft geschieht; die lange Folge des Exponenten 26565 setzt sich in der erweiterten Liste der Koeffizienten bis 1000 noch weiter fort bis 59. Bei $\Phi _{40755}$ springt der Rekord urplötzlich auf 359, und praktisch alle Koeffizienten dazwischen sind vertreten. Bei $\Phi _{255255}(X)=\Phi _{3*5*7*11*13*17}(X)$, dem kleinstmöglichen n mit 6 verschiedenen ungeraden Primfaktoren, ist -532 erreicht (bei 92160.Grad). Die Liste endet ab 585 mit einer langen Serie mit 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 ! Eine Rekordmarke wird drei- oder viermal nur um wenige Prozent überboten, bleibt auf jeden Fall in der gleichen Größenordnung, um dann bei einem neuen Rekord gleich um mehrere Zehnerpotenzen in die Höhe zu schnellen. 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 nennt die Liste der ersten 42 Rekordexponenten, die dazugehörige Liste der Koeffizienten steht in Rekordkoeffizienten 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*5*11*13*19*29*37*43*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 rekordträchtig, wenn die Exponenten eine Faktorzerlegung aus den kleinsten Primzahlen haben; bei Primfaktoren im Tausender- oder Millionenbereich ist der höchste auftretende Koeffizient 1 oder 2 !