円分多項式

円分多項式（えんぶんたこうしき、英: cyclotomic polynomial, 独: Kreisteilungspolynom）とは、1の冪根に関連のある多項式である。具体的には次の式で定義される多項式 Φn(x) を指す。 Φ n ( x ) = ∏ 1 ≤ k ≤ n gcd ⁡ ( k , n ) = 1 ( x − e 2 π i k n ) . {\displaystyle \Phi _{n}(x)=\textstyle \prod \limits _{1\leq k\leq n \atop \operatorname {gcd} (k,n)=1}\left(x-e^{\frac {2\pi ik}{n}}\right).} この定義からは明らかではないが、これは係数が整数の多項式で、さらに有理数体上の既約多項式である。多項式 xn − 1 は次のように円分多項式の積として既約分解される。 x n − 1 = ∏ d ∣ n Φ d ( x ) . {\displaystyle x^{n}-1=\textstyle \prod \limits _{d\mid n}\Phi _{d}(x).} 英語の「cyclotomic」という言葉は古代ギリシャ語の「円 (cyclo)」と「分ける (tomos)」に由来する。 一般に 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 \limits _{d\mid n \atop d\neq n}\Phi _{d}(x)}}} またはメビウスの反転公式により得られる Φ n ( x ) = ∏ d ∣ n ( x n d − 1 ) μ ( d ) {\displaystyle \Phi _{n}(x)=\textstyle \prod \limits _{d\mid n}(x^{\frac {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 が現れる。 Φ 105 ( x ) = x 48 + x 47 + x 46 − x 43 − x 42 − 2 x 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 − 2 x 7 − x 6 − x 5 + x 2 + x + 1 {\displaystyle {\begin{aligned}\Phi _{105}(x)&=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}\\&\qquad \quad -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}}} 円分多項式の係数の大きさについて知られている最良の結果は次のものである。 Φ n ( x ) = ∑ m = 0 φ ( n ) a n m x m {\displaystyle \Phi _{n}(x)=\textstyle \sum \limits _{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}} を満たす。また max m | a n m | > exp ⁡ log ⁡ 2 log ⁡ n log ⁡ log ⁡ n {\displaystyle \max _{m}\vert a_{nm}\vert >\exp {\frac {\log 2\log n}{\log \log n}}} となる n が無数に存在する。 n が素数のときは係数が全て 1 の n − 1 次の多項式となる。 すべての整数は円分多項式の係数として現れる。さらに強く、どのような等差数列 ( s n + t ) n ≥ 1 ( s > t ≥ 0 ) {\displaystyle (sn+t)_{n\geq 1}(s>t\geq 0)} をとっても、すべての整数はある Φ s n + t {\displaystyle \Phi _{sn+t}} の係数として現れる。 任意の円分多項式の全ての根は、いくつかの有理数から出発して四則と冪根を繰り返すことにより表せることが知られている。実際、Φn(x) のガロア群は Z/nZ の乗法群である。特に n がフェルマー素数のときは、冪根として平方根を用いるだけで表すことが可能であるため、長さ 1 の線分が与えられれば、定規とコンパスを使用して半径 1 の円弧を n 等分する線分が作図可能である。 x が異なる円分多項式の差として表される多項式の根ならば 1/2 < x < 2 となる。このことから多項式 F, G の間に F ⪯ G {\displaystyle F\preceq G} を x > 2 となるすべての x について F ( x ) ≤ G ( x ) {\displaystyle F(x)\leq G(x)} となることと定義すると ⪯ {\displaystyle \preceq } は円分多項式の間の全順序を定めることが分かる。 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)=\textstyle \sum \limits _{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 である。この結果はさらに一般化される（リュカ数列を参照）。