In der Algebra werden Kreisteilungspolynome (auch: Zyklotomische Polynome) verwendet, um Unterteilungen des Einheitskreises in gleiche Teile zu untersuchen. Unter dem
-ten Kreisteilungspolynom
versteht man dasjenige ganzzahlige Polynom größten Grades mit Leitkoeffizient 1, das
teilt, jedoch zu allen
mit
teilerfremd ist. Seine Nullstellen über
sind genau die primitiven
-ten Einheitswurzeln
, wobei
die zu
teilerfremden Zahlen zwischen
und
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
-Ecke dies gelingt, findet sich im Artikel konstruierbares Polygon.
Eigenschaften
Die Zerlegung des
-ten Kreisteilungspolynoms in Linearfaktoren ergibt
![{\displaystyle \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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ea91407ae56b7f8afd0f43b18ac9e0a30b4d455)
Daher ist der Grad von
gleich
, der Anzahl der zu
teilerfremden Zahlen unterhalb
. Die hierdurch definierte Funktion
hat als Eulersche Phi-Funktion in der Zahlentheorie eine erhebliche Bedeutung.
Umgekehrt gilt die Produktdarstellung
![{\displaystyle 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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3dde3a532202fc04fcfe0342db663b4f8b4b7bdb)
Das
-te Kreisteilungspolynom hat ganzzahlige Koeffizienten, liegt also in
. Es ist dort und in
ein irreduzibles Polynom, folglich Minimalpolynom jeder primitiven
-ten Einheitswurzel. Somit ist der Restklassenring
sogar ein Körper, und zwar der kleinste, worin der Einheitskreis der komplexen Ebene derart in
gleich lange 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.
Beispiele
Ist n eine Primzahl (z. B. n=2, 3, 5, 7, 11, 13), dann gilt
![{\displaystyle ~\Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{i=0}^{n-1}x^{i}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd1cc3eb53e921e95a671152e5efd4426020381a)
Allgemeiner: Ist
eine Primzahlpotenz (z. B. n=2, 3, 4, 5, 7, 8, 9, 11, 13, 16), dann gilt
![{\displaystyle ~\Phi _{n}(x)=1+x^{p^{m-1}}+x^{2p^{m-1}}+\cdots +x^{(p-1)p^{m-1}}=\sum _{i=0}^{p-1}x^{ip^{m-1}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00eb4ee4b2cad474305b75f4eb0e7ae56640e106)
Ist n=2p das Doppelte einer ungeraden Primzahl p (z. B. n=6, 10, 14), dann gilt
![{\displaystyle ~\Phi _{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{i=0}^{p-1}(-x)^{i}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4e93d4d9770ab8ad67bda4a7fdb70aea652b2c2)
Mit diesen Regeln lassen sich (mit Ausnahme von n=12 und n=15) die folgenden Kreisteilungspolynome bestimmen:
![{\displaystyle ~\Phi _{1}(x)=x-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/169698f29af658e950d8f135e549c53a8677f982)
![{\displaystyle ~\Phi _{2}(x)=x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/367473847157aae5f40e5b8f68b38fcc73409d04)
![{\displaystyle ~\Phi _{3}(x)=x^{2}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd64046a9a22d7b7ed36956b37b2e8945f6c5531)
![{\displaystyle ~\Phi _{4}(x)=x^{2}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/996f0bb31a7467607c10cd7a6387770f75fe0a3d)
![{\displaystyle ~\Phi _{5}(x)=x^{4}+x^{3}+x^{2}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad20a48077fd01f0b9858409c07c0b134893f3ad)
![{\displaystyle ~\Phi _{6}(x)=x^{2}-x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e822ed4b3921a3d48a1547bbcda1b2e3b99213f6)
![{\displaystyle ~\Phi _{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4f8f22a9c19a16d8a8cedb2def7213188a06bcb1)
![{\displaystyle ~\Phi _{8}(x)=x^{4}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf7ab37c04511e3d052e52262a5fa71912b6fe5b)
![{\displaystyle ~\Phi _{9}(x)=x^{6}+x^{3}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b454b9cc85ec7f81bc16ca74e992a80891f7145)
![{\displaystyle ~\Phi _{10}(x)=x^{4}-x^{3}+x^{2}-x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a176221934d38a3e2314675677ee9c962cc5341a)
![{\displaystyle ~\Phi _{11}(x)=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee3154ab49346aa850f8002d0eccb65e894f4cea)
![{\displaystyle ~\Phi _{12}(x)=x^{4}-x^{2}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a88a2884c59a72019cf337e5baf2f089b7fe0aaa)
![{\displaystyle ~\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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3453e50c772e93edfa6b3f3d73b76d4ee4072e36)
![{\displaystyle ~\Phi _{14}(x)=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e310bc9102e1b147faef2702ea414901e7f37583)
![{\displaystyle ~\Phi _{15}(x)=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64f9251c157283616e18e822bb1329deb3967cb3)
![{\displaystyle ~\Phi _{16}(x)=x^{8}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51309215c1af1a48e66f7625e9d45d0bfe4dca9b)
Einige weitere Beispiele, die sich mit den obigen Regeln berechnen lassen:
![{\displaystyle ~\Phi _{25}(x)=x^{20}+x^{15}+x^{10}+x^{5}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50836677dbe83ae1512549a63a7080ab2535d672)
![{\displaystyle ~\Phi _{49}(x)=x^{42}+x^{35}+x^{28}+x^{21}+x^{14}+x^{7}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b909cab62421c903f11fa207de9addb06fb4497)
![{\displaystyle ~\Phi _{125}(x)=x^{100}+x^{75}+x^{50}+x^{25}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e9fb55be6b4c06379663b88e1f59f7958023b64)
Weitere Berechnungsmöglichkeiten
Wie eingangs erwähnt, gilt die Produktdarstellung
.
Sind nun die Kreisteilungspolynome
für d<n bekannt, so lässt sich
per Polynomdivision berechnen. Für n=21 ergibt sich so beispielsweise
![{\displaystyle ~(x^{21}-1)=\Phi _{1}(x)\cdot \Phi _{3}(x)\cdot \Phi _{7}(x)\cdot \Phi _{21}(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76e7afbc49f9191263e6aec3c49a20e7f20507b5)
also
.
Ein anderer Ansatz folgt aus der multiplikativen Version der Möbius-Inversion, welche die Gleichung
![{\displaystyle ~\Phi _{n}(x)=\prod _{d\mid n}(x^{d}-1)^{\mu (n/d)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5637fb434bbab7104ad86451ece3e118dab3b171)
liefert, wobei
die Möbiusfunktion bezeichnet. Für n=21 ergibt sich so
.
Wie man sieht, lässt sich dieser Ausdruck mit weniger Aufwand als im vorigen Beispiel vereinfachen. Außerdem sind keine Kenntnisse über andere Kreisteilungspolynome notwendig.
Ein weiterer Ansatz folgt zusammen mit der Fourierdarstellung von Funktionen des größten gemeinsamen Teilers ebenso aus der Möbius-Inversion, welche die Gleichung
![{\displaystyle ~\Phi _{n}(x)=\prod \limits _{k=1}^{n}{(x^{\operatorname {ggT} (k,n)}-1)^{\cos({\frac {2\pi k}{n}})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa84f4410ac4fd6242edc3f506cac6de410d17c4)
ergibt.[1]
Das Koeffizientenproblem
Auffällig ist, dass in allen bisherigen Beispielen als Koeffizienten nur −1, 0 und +1 aufgetreten sind. Tatsächlich hat A. Migotti 1883 zeigen können, dass dies immer der Fall ist, sofern n das Produkt von zwei unterschiedlichen Primzahlen ist.[2] Andererseits war spätestens seit 1931 bekannt, dass dies nicht immer so ist: Issai Schur zeigte in einem Brief an Edmund Landau, dass die Koeffizienten in Kreisteilungspolynomen beliebig groß werden können.[3]
Das kleinste n, für das ein Koeffizient ungleich −1, 0 oder +1 möglich ist, ist
. Und tatsächlich tritt hier der Koeffizient −2 auf. Mit einer der oben beschriebenen Methoden lässt sich das folgende Kreisteilungspolynom leicht berechnen:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d54a9b78f44d73cc4cd447a684e05fca8c8a6228)
Das erste Kreisteilungspolynom mit einem Koeffizienten, der vom Betrag her größer als 2 ist, tritt für
auf:
![{\displaystyle {\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}[\dots ]\\&[\dots ]+x^{134}+x^{133}+2x^{132}+2x^{131}+2x^{130}+2x^{129}+2x^{128}+x^{127}+x^{126}-x^{124}-2x^{123}-2x^{122}-3x^{121}\\&-3x^{120}-3x^{119}-2x^{118}-2x^{117}-x^{116}+x^{114}+x^{113}+2x^{112}+2x^{111}+2x^{110}+2x^{109}+2x^{108}+x^{107}+x^{106}[\dots ]\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/194c4f92125aed8cf03125ac3d94e9617efc545b)
Siehe auch OEIS A013594[4].
Weblinks
Einzelnachweise
- ↑ Wolfgang Schramm: Eine alternative Produktdarstellung für die Kreisteilungspolynome. In: Elemente der Mathematik. 70. Jahrgang, Nr. 4. Schweizerische Mathematische Gesellschaft, 2015, S. 137–143 (ems-ph.org [abgerufen am 10. Oktober 2015]).
- ↑ A. Migotti, Zur Theorie der Kreisteilungsgleichung. Sitzber. Math.-Naturwiss. Classe der Kaiser. Akad. der Wiss., Wien 87 (1883), 7–14.
- ↑ Emma Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial. Bull. Amer. Math. Soc. 42 (1936), no. 6, 389–392.
- ↑ OEIS A013594