円分多項式

円分多項式（えんぶんたこうしき、英: cyclotomic polynomial, 独: Kreisteilungspolynom）とは1の冪根に関連のある多項式である。具体的には次の式で定義される多項式 Φn(x) を指す。 Φ n ( x ) = ∏ gcd ⁡ ( k , n ) = 1 1 ≤ k ≤ n ( x − e 2 π i k / n ) . {\displaystyle \Phi _{n}\left(x\right)=\prod _{\stackrel {1\leq k\leq n}{\operatorname {gcd} \left(k,n\right)=1}}\left(x-e^{2\pi ik/n}\right).} この定義からは明らかではないが、これは整数を係数に持つ多項式で、さらに有理数体上の既約多項式である。多項式 xn − 1 は次のように円分多項式の積として既約分解される。 x n − 1 = ∏ d ∣ n Φ d ( x ) . {\displaystyle x^{n}-1=\prod _{d\mid n}\Phi _{d}\left(x\right).\,} 一般に n 次方程式は代数的閉体において、重根を含め n 個の根を持つ。特に、複素数体は代数的閉体であるから、方程式 xn − 1 = 0 は複素数の範囲で n 個の根を持つ。 実際 e2πik/n は k を 1 から n まで変化させると方程式 xn − 1 = 0 の n 個の異なる根をすべて与える。複素平面上にあるこれらの根は単位円の弧を n 等分する。これが円分多項式と呼ばれる所以である。 例えば、x4 − 1 = 0 は i, −1, −i, 1 の4つの根を持ち、k = 1, 2, 3, 4 に対応する。1 と −1 は2乗すると 1 になるので、x2 − 1 = 0 の根でもある。一方、i, −i は4乗しなければ 1 とならない。この2つを根に持つ方程式が Φ4(x) = x2 + 1 である。このように n 乗して初めて 1 となる複素数（1 の原始 n 乗根）全てを根に持ち、最高次数の項の係数が 1 である多項式が円分多項式 Φn(x) である。 n 乗して初めて 1 になる条件は k と n が互いに素なことであるため、冒頭の定義が与えられる。定義からすぐに得られる帰納的関係式 Φ n ( x ) = x n − 1 ∏ d ∣ n ,   d ≠ n Φ d ( x ) {\displaystyle \Phi _{n}(x)={\frac {x^{n}-1}{\prod _{d\mid n,\ d\neq n}\Phi _{d}(x)}}} またはメビウスの反転公式により得られる Φ n ( x ) = ∏ d ∣ n ( x n / d − 1 ) μ ( d ) {\displaystyle \Phi _{n}(x)=\prod _{d\mid n}(x^{n/d}-1)^{\mu (d)}\,} が計算上は有用である。 実際に円分多項式を計算すると以下のようになる。 Φ 1 = x − 1 Φ 2 = ( x 2 − 1 ) / Φ 1 = x + 1 Φ 3 = ( x 3 − 1 ) / Φ 1 = x 2 + x + 1 Φ 4 = ( x 4 − 1 ) / Φ 1 Φ 2 = x 2 + 1 Φ 5 = ( x 5 − 1 ) / Φ 1 = x 4 + x 3 + x 2 + x + 1 Φ 6 = ( x 6 − 1 ) / Φ 1 Φ 2 Φ 3 = x 2 − x + 1 Φ 7 = ( x 7 − 1 ) / Φ 1 = x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 Φ 8 = ( x 8 − 1 ) / Φ 1 Φ 2 Φ 4 = x 4 + 1 Φ 9 = ( x 9 − 1 ) / Φ 1 Φ 3 = x 6 + x 3 + 1 Φ 10 = ( x 10 − 1 ) / Φ 1 Φ 2 Φ 5 = x 4 − x 3 + x 2 − x + 1 Φ 11 = ( x 11 − 1 ) / Φ 1 = x 10 + x 9 + x 8 + x 7 + x 6 + x 5 + x 4 + x 3 + x 2 + x + 1 Φ 12 = ( x 12 − 1 ) / Φ 1 Φ 2 Φ 3 Φ 4 Φ 6 = x 4 − x 2 + 1 {\displaystyle {\begin{aligned}\Phi _{1}&&&=x-1\\\Phi _{2}&=(x^{2}-1)/\Phi _{1}&&=x+1\\\Phi _{3}&=(x^{3}-1)/\Phi _{1}&&=x^{2}+x+1\\\Phi _{4}&=(x^{4}-1)/\Phi _{1}\Phi _{2}&&=x^{2}+1\\\Phi _{5}&=(x^{5}-1)/\Phi _{1}&&=x^{4}+x^{3}+x^{2}+x+1\\\Phi _{6}&=(x^{6}-1)/\Phi _{1}\Phi _{2}\Phi _{3}&&=x^{2}-x+1\\\Phi _{7}&=(x^{7}-1)/\Phi _{1}&&=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{8}&=(x^{8}-1)/\Phi _{1}\Phi _{2}\Phi _{4}&&=x^{4}+1\\\Phi _{9}&=(x^{9}-1)/\Phi _{1}\Phi _{3}&&=x^{6}+x^{3}+1\\\Phi _{10}&=(x^{10}-1)/\Phi _{1}\Phi _{2}\Phi _{5}&&=x^{4}-x^{3}+x^{2}-x+1\\\Phi _{11}&=(x^{11}-1)/\Phi _{1}&&=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{12}&=(x^{12}-1)/\Phi _{1}\Phi _{2}\Phi _{3}\Phi _{4}\Phi _{6}&&=x^{4}-x^{2}+1\\\end{aligned}}} 円分多項式の次数はその性質上オイラーの φ 関数を用いれば φ(n) に等しい。また、上記の例では係数が 1, −1, 0 しか現れないが、必ずそうなるわけではない。実際 Φ105(x) がそうでない最小の例で係数に −2 が現れる。 円分多項式の係数の大きさについて知られている最良の結果は次のものである。 Φ n ( x ) = ∑ m = 0 φ ( n ) a n m x m {\displaystyle \Phi _{n}(x)=\sum _{m=0}^{\varphi (n)}a_{nm}x^{m}} とおく。このとき、定数 c2 > c1 > 0 が存在して、十分大きい m に対して、 c 1 m 1 / 2 ( log ⁡ m ) − 1 / 4 < log ⁡ max n | a n m | < c 2 m 1 / 2 ( log ⁡ m ) − 1 / 4 {\displaystyle c_{1}m^{1/2}(\log m)^{-1/4}<\log \max _{n}\vert a_{nm}\vert <c_{2}m^{1/2}(\log m)^{-1/4}} を満たす。 n が素数のときは係数が全て 1 の n − 1 次の多項式となる。 任意の円分多項式の全ての根は、いくつかの有理数から出発して四則と冪根を繰り返すことにより表せることが知られている。実際、Φn(x) のガロア群は Z/nZ の乗法群である。特に n がフェルマー素数のときは、冪根として平方根を用いるだけで表すことが可能であるため、長さ 1 の線分が与えられれば、定規とコンパスを使用して半径 1 の円弧を n 等分する線分が作図可能である。 a を整数とし、g を a の p を法とする位数とするとき、p が Φn(a) の素因数であることは n = gpe (e ≥ 0) と書けることと同値である。よって、Φn(a) の素因数は n の約数であるか、または n を法として 1 と合同である。このことから、任意の整数 n に対して、n を法として 1 と合同である素数が無限に多く存在することが導かれる。これはディリクレの算術級数定理の特別な場合である。 Φn(a) は少数の例外を除いて必ず n を法として 1 と合同である素因数を持つ。実際、 Φ n ( x , y ) = ∑ m = 0 φ ( n ) a n m x m y φ ( n ) − m {\displaystyle \Phi _{n}(x,y)=\sum _{m=0}^{\varphi (n)}a_{nm}x^{m}y^{\varphi (n)-m}} とおくと、次のことが知られている。 a , b を p と互いに素な整数とし、g を p が ag − bg を割り切る最小の g とするとき、p が Φn(a, b) の素因数であることは n = gpe (e ≥ 0) と書けることと同値である。 a > b を p と互いに素な正の整数とする。Φn(a, b) は Φ6(2, 1) = 3, Φ1(a, a − 1) = 1, Φ2(a, b) = a + b, （最後の場合において、a, b は奇数で a + b は2の冪）となる場合を除いて、必ず n を法として 1 と合同である素因数を持つ。 なお、この場合には、そのような素因数を p とし、n = gpe (e ≥ 0) とおくと、p > n より e = 0, すなわち g = n でなければならない。すなわち、n は p が an − bn を割り切る最小の n である。この結果はさらに一般化される（リュカ数列を参照）。 ^ H. L. Montgomery and R. C. Vaughan, The order of magnitude of the m th coefficients of cyclotomic polynomials, Glasgow Math. J. 27 (1985), 143–159. ^ Zsigmondy 1892, Carmichael 1913, Kanold 1950など、多くの数学者がこの証明を発表している。 R. D. Carmichael, On the numerical factors of the arithmetic forms α n ± β n {\displaystyle \alpha ^{n}\pm \beta ^{n}} , Ann. of Math. 15 (1913), 30–70. H.-J. Kanold, Sätze über Kreisteilungspolynome und ihre Anwendungen auf einige zahlentheoretische Probleme I, J. reine angew. Math. 187(1950), 169–182. K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math. 3(1892), 265–284.