主題
Search

分圓多項式

一個由下式給出的多項式

Phi_n(x)=product_(k=1)^n^'(x-zeta_k),
(1)

其中 zeta_k 是 單位根 在 C 中，由下式給出

zeta_k=e^(2piik/n)
(2)

並且 k 遍歷與 n 互質 的整數。如果乘積改為對 本原單位根 取，則可以省略素數，因此

Phi_n(x)=product_(k=1; primitive zeta_k)^n(x-zeta_k).
(3)

符號 F_n(x) 也經常遇到。Dickson等人 (1923) 和 Apostol (1975) 給出了分圓多項式的廣泛參考書目。

對於 n>1 的分圓多項式也可以定義為

Phi_n(x)=product_(d|n)(1-x^(n/d))^(mu(d))
(4)

其中 mu(d) 是 莫比烏斯函式，乘積對 d 的 n 的除數取 (Vardi 1991, p. 225)。

Cyclotomic polynomial roots

Phi_n(x) 是一個 整係數多項式 和一個 不可約多項式，其 多項式次數 為 phi(n)，其中 phi(n) 是 尤拉函式。分圓多項式由 Wolfram 語言 命令返回Cyclotomic[n, x]。分圓多項式的根位於 單位圓 上，在 複平面 中，如上圖所示，為前幾個分圓多項式。

Cyclotomic

前幾個分圓多項式是

Phi_1(x)=x-1
(5)
Phi_2(x)=x+1
(6)
Phi_3(x)=x^2+x+1
(7)
Phi_4(x)=x^2+1
(8)
Phi_5(x)=x^4+x^3+x^2+x+1
(9)
Phi_6(x)=x^2-x+1
(10)
Phi_7(x)=x^6+x^5+x^4+x^3+x^2+x+1
(11)
Phi_8(x)=x^4+1
(12)
Phi_9(x)=x^6+x^3+1
(13)
Phi_(10)(x)=x^4-x^3+x^2-x+1.
(14)
CyclotomicPhiReIm
CyclotomicPhiContours

分圓多項式 Phi_7(z) 如上圖所示，在 複平面 中。

在透過原點的任何直線上，分圓多項式的值在 單位圓盤 外部嚴格遞增。

如果 p 是一個 奇素數，則

Phi_p(x)=(x^p-1)/(x-1)
(15)
=x^(p-1)+x^(p-2)+...+x+1
(16)
Phi_(2p)(x)=(x^(2p)-1)/(x^p-1)(x-1)/(x^2-1)
(17)
=x^(p-1)-x^(p-2)+...-x+1
(18)
Phi_(4p)(x)=(x^(4p)-1)/(x^(2p)-1)(x^2-1)/(x^4-1)
(19)
=x^(2p-2)-x^(2p-4)+...-x^2+1
(20)

(Riesel 1994, p. 306)。類似地，對於 p 再次是一個 奇素數，

x^p-1=Phi_1(x)Phi_p(x)
(21)
x^(2p)-1=Phi_1(x)Phi_2(x)Phi_p(x)Phi_(2p)(x)
(22)
x^(4p)-1=Phi_1(x)Phi_2(x)Phi_4(x)Phi_p(x)Phi_(2p)(x)Phi_(4p)(x).
(23)

對於 n 的前幾個剩餘值，

x-1=Phi_1(x)
(24)
x^2-1=Phi_1(x)Phi_2(x)
(25)
x^4-1=Phi_1(x)Phi_2(x)Phi_4(x)
(26)
x^8-1=Phi_1(x)Phi_2(x)Phi_4(x)Phi_8(x)
(27)
x^9-1=Phi_1(x)Phi_3(x)Phi_9(x)
(28)
x^(15)-1=Phi_1(x)Phi_3(x)Phi_5(x)Phi_(15)(x)
(29)
x^(16)-1=Phi_1(x)Phi_2(x)Phi_4(x)Phi_8(x)Phi_(16)(x)
(30)
x^(18)-1=Phi_1(x)Phi_2(x)Phi_3(x)Phi_6(x)Phi_9(x)Phi_(18)(x)
(31)

(Riesel 1994, p. 307)。

對於 p 一個與 n 互質的 素數，

Phi_(np)(x)=(Phi_n(x^p))/(Phi_n(x)),
(32)

但是如果 p|n,

Phi_(np)(x)=Phi_n(x^p)
(33)

(Nagell 1951, p. 160)。

對於 無平方因子 的 n，Phi_n(x) 的顯式方程由下式給出

Phi_n(x)=sum_(j=0)^(phi(n))a_(nj)z^(phi(n)-j),
(34)

其中 phi(n) 是 尤拉函式，a_(nj) 使用 遞推關係 計算

a_(nj)=-(mu(n))/jsum_(m=0)^(j-1)a_(nm)mu(GCD(n,j-m))phi(GCD(n,j-m)),
(35)

其中 a_(n0)=1，其中 mu(n) 是 莫比烏斯函式，GCD(m,n) 是 m 和 n 的 最大公約數。

多項式 x^n-1 可以分解為

x^n-1=product_(d|n)Phi_d(x).
(36)

此外，

x^n+1=(x^(2n)-1)/(x^n-1)
(37)
=(product_(d|2n)Phi_d(x))/(product_(d|n)Phi_d(x)).
(38)

分圓多項式倒數的 係數

1/(1+x+x^2)=1-x+x^3-x^4+x^6-x^7+x^9-...
(39)
=sum_(n=0)^(infty)c_nx^n
(40)

也可以從下式計算

c_n=1-2|_1/3(n+2)_|+|_1/3(n+1)_|+|_1/3n_|
(41)
=1-3|_1/3(n+2)_|+|_n_|
(42)
=2/(sqrt(3))sin[2/3pi(n+1)],
(43)

其中 |_x_| 是 向下取整函式。

對於 p 素數，

Phi_p(x)=sum_(k=0)^(p-1)x^k,
(44)

即，係數都是 1。第一個係數不是 +/-1 和 0 的分圓多項式是 Phi_(105)(x)，其係數為 -2，對於 x^7 和 x^(41)。這是因為 105 是第一個具有三個不同 奇素數 因子的數字，即 105=3·5·7 (McClellan 和 Rader 1979, Schroeder 1997)。n 的最小值，對於這些值，Phi_n(x) 具有一個或多個係數 +/-1, +/-2, +/-3, ... 分別是 0, 105, 385, 1365, 1785, 2805, 3135, 6545, 6545, 10465, 10465, 10465, 10465, 10465, 11305, ... (OEIS A013594)。

對於 m,n>1，如果 Phi_m(x)+Phi_n(x) 可以分解，那麼因子包含一個分圓多項式。例如，

Phi_7(x)+Phi_(22)(x)=(x^2+1)(x^8-x^7+2x^4+2)
(45)
=Phi_4(x)(x^8-x^7+2x^4+2).
(46)

這個觀察結果已經檢查到 m,n=150 (Nicol 2000)。如果 m 和 n 是素數，那麼 C_m+C_n 是不可約的。

Migotti (1883) 表明，對於 p 和 q 不同的 素數，Phi_(pq)(x) 的 係數 只能是 0, +/-1。Lam 和 Leung (1996) 考慮了

Phi_(pq)(x)=sum_(k=0)^(pq-1)a_kx^k
(47)

對於 p,q 素數。將 尤拉函式 寫成

phi(pq)=(p-1)(q-1)=rp+sq
(48)

並令

0<=k<=(p-1)(q-1),
(49)

則

1. a_k=1 當且僅當 對於一些 i in [0,r] 和 j in [0,s], k=ip+jq

2. a_k=-1 當且僅當 對於 i in [r+1,q-1] 和 j in [s+1,p-1], k+pq=ip+jq

3. 否則 a_k=0。

具有 a_k=1 的項數為 (r+1)(s+1)，具有 a_k=-1 的項數為 (p-s-1)(q-r-1)。此外，假設 q>p，則 Phi_(pq) 的中間 係數 為 (-1)^r。

Lehmer (1936)、Diederichsen (1940) 和 Apostol (1970) 計算了分圓多項式的結式。已知如果 (m,n)=1，即 m 和 n 互質 (Apostol 1975)，則 rho(Phi_m(x),Phi_n(x))=1。Apostol (1975) 表明，對於正整數 m 和 n 以及任意非零複數 a 和 b，

rho(Phi_m(ax),Phi_n(bx))=b^(phi(m)phi(n))product_(d|n)[Phi_(m/delta)((a^d)/(b^d))]^(mu(n/d)phi(m)/phi(m/delta)),
(50)

其中 delta=GCD(m,d) 是 m 和 d 的 最大公約數，phi(n) 是 尤拉函式，mu(n) 是 莫比烏斯函式，乘積是對 n 的除數取的。如果 m 和 n 是不同的素數 p 和 q，則 (50) 簡化為

rho(Phi_q(ax),Phi_p(bx))={(a^(pq)-b^(pq))/(a^p-b^p)(a-b)/(a^q-b^q) for a!=b; a^((p-1)(q-1)) for a=b.
(51)

下表給出了 結式 rho(Phi_k(x), Phi_n(x)) (OEIS A054372)。

k\n1234567
10
220
3310
42210
551110
6134110
77111110

此表中連續行的 1 的數量由 0, 0, 1, 1, 3, 3, 5, 4, 6, 7, 9, ... 給出 (OEIS A075795)。

分圓多項式 Phi_6(x) 具有特別好的 麥克勞林級數

1/(Phi_6(x))=1+x-x^3-x^4+x^6+x^7-x^9-x^(10)+...,
(52)

其係數 1, 0, -1, -1, 0, 1, 1, 0, -1, -1, ... (OEIS A010892) 由求解遞推方程給出

a(n)=a(n-1)-a(n-2)
(53)

其中 a(0)=a(1)=1 (Wolfram 2002, p. 128)，給出顯式形式

a(n)=2/3sqrt(3)sin[1/3(n+1)pi].
(54)

有趣的是，任何滿足 線性遞推方程 的序列 b(n)

b(n)=b(n-1)-b(n-2)
(55)

都可以寫成

b(n)=b(0)a(n)+[b(1)-b(0)]a(n-1).
(56)

另請參閱

Aurifeuillean 分解, 高斯分圓公式, 盧卡斯定理, 莫比烏斯反演公式, 本原單位根, 單位根

相關 Wolfram 網站

http://functions.wolfram.com/Polynomials/Cyclotomic/

使用 探索

參考文獻

Apostol, T. M. "分圓多項式的結式 (Resultants of Cyclotomic Polynomials)." Proc. Amer. Math. Soc. 24, 457-462, 1970.Apostol, T. M. "分圓多項式 F_m(ax) 和 F_n(bx) 的結式 (The Resultant of the Cyclotomic Polynomials)." Math. Comput. 29, 1-6, 1975.Beiter, M. "分圓多項式 F_(pq)(x) 的中間係數 (The Midterm Coefficient of the Cyclotomic Polynomial)." Amer. Math. Monthly 71, 769-770, 1964.Beiter, M. "分圓多項式 F_(pq) 的係數幅度 (Magnitude of the Coefficients of the Cyclotomic Polynomial)." Amer. Math. Monthly 75, 370-372, 1968.Bloom, D. M. "關於分圓多項式的係數 (On the Coefficients of the Cyclotomic Polynomials)." Amer. Math. Monthly 75, 372-377, 1968.Brent, R. P. "關於計算分圓多項式的因子 (On Computing Factors of Cyclotomic Polynomials)." Math. Comput. 61, 131-149, 1993.Carlitz, L. "分圓多項式 F_(pq)(x) 中的項數 (The Number of Terms in the Cyclotomic Polynomial)." Amer. Math. Monthly 73, 979-981, 1966.Conway, J. H. 和 Guy, R. K. 數之書 (The Book of Numbers). New York: Springer-Verlag, 1996.de Bruijn, N. G. "關於迴圈群的分解 (On the Factorization of Cyclic Groups)." Indag. Math. 15, 370-377, 1953.Dickson, L. E.; Mitchell, H. H.; Vandiver, H. S.; 和 Wahlin, G. E. 代數數 (Algebraic Numbers). Bull Nat. Res. Council, Vol. 5, Part 3, No. 28. Washington, DC: National Acad. Sci., 1923.Diederichsen, F.-E. "關於算術等價性下整數群表示的約化 (Über die Ausreduktion ganzzahliger Gruppendarstellungen bei arithmetischer Äquivalenz)." Abh. Math. Sem. Hanisches Univ. 13, 357-412, 1940.Lam, T. Y. 和 Leung, K. H. "關於分圓多項式 Phi_(pq)(X) (On the Cyclotomic Polynomial)." Amer. Math. Monthly 103, 562-564, 1996.Lehmer, E. "關於分圓多項式的係數幅度 (On the Magnitude of the Coefficients of the Cyclotomic Polynomial)." Bull. Amer. Math. Soc. 42, 389-392, 1936.McClellan, J. H. 和 Rader, C. 數字訊號處理中的數論 (Number Theory in Digital Signal Processing). Englewood Cliffs, NJ: Prentice-Hall, 1979.Migotti, A. "關於分圓方程的理論 (Zur Theorie der Kreisteilungsgleichung)." Sitzber. Math.-Naturwiss. Classe der Kaiser. Akad. der Wiss., Wien 87, 7-14, 1883.Nagell, T. "分圓多項式 (The Cyclotomic Polynomials)" 和 "分圓多項式的素因子 (The Prime Divisors of the Cyclotomic Polynomial)." §46 和 48 in 數論導論 (Introduction to Number Theory). New York: Wiley, pp. 158-160 和 164-168, 1951.Nicol, C. "分圓多項式的和 (Sums of Cyclotomic Polynomials)." Apr. 26, 2000. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0004&L=nmbrthry&T=0&F=&S=&P=2317.Riesel, H. "分圓多項式 (The Cyclotomic Polynomials)" in Appendix 6. 素數與計算機分解方法，第二版 (Prime Numbers and Computer Methods for Factorization, 2nd ed.). Boston, MA: Birkhäuser, pp. 305-308, 1994.Schroeder, M. R. 科學與通訊中的數論：在密碼學、物理學、數字資訊、計算和自相似性中的應用，第三版 (Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity, 3rd ed.). New York: Springer-Verlag, p. 245, 1997.Séroul, R. "分圓多項式 (Cyclotomic Polynomials)." §10.8 in 數學家程式設計 (Programming for Mathematicians). Berlin: Springer-Verlag, pp. 265-269, 2000.Sloane, N. J. A. 序列 A013594, A010892, A054372, 和 A075795 在 "整數序列線上百科全書 (The On-Line Encyclopedia of Integer Sequences)." 中。Trott, M. "Mathematica 指南 附加材料：分圓多項式幅角的圖形 (Graphics of the Argument of Cyclotomic Polynomials)." http://www.mathematicaguidebooks.org/additions.shtml#N_2_03.Vardi, I. Mathematica 中的計算娛樂 (Computational Recreations in Mathematica). Redwood City, CA: Addison-Wesley, pp. 8 和 224-225, 1991.Wolfram, S. 一種新的科學 (A New Kind of Science). Champaign, IL: Wolfram Media, 2002.

在 上被引用

分圓多項式

請引用為

Weisstein, Eric W. "分圓多項式 (Cyclotomic Polynomial)." 來自 --沃爾夫勒姆數學世界。 https://mathworld.tw/CyclotomicPolynomial.html

主題分類