主题
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/

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上被引用

分圆多项式

请引用为

Weisstein, Eric W. "分圆多项式 (Cyclotomic Polynomial)." 来自 MathWorld--沃尔夫勒姆数学世界。 https://mathworld.net.cn/CyclotomicPolynomial.html

主题分类