円分多項式

数学において、任意の正の整数nに対するn次円分多項式は、整数係数を持つ唯一の既約多項式であり、の約数であり、任意のk < nに対しての約数ではない。その根はすべて1 のn次原始根であり、ここでk はnより小さい正の整数上でnと互いに素である( iは虚数単位)。言い換えると、n次円分多項式は ${\displaystyle x^{n}-1}$${\displaystyle x^{k}-1}$ ${\displaystyle e^{2i\pi {\frac {k}{n}}}}$

${\displaystyle \Phi _{n}(x)=\prod _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(xe^{2i\pi { \frac {k}{n}}}\right).}$

これは、任意の原始n乗根(はそのような根の一例) の有理数体上の最小多項式である、整数係数の単項多項式として定義することもできます。${\displaystyle e^{2i\pi /n}}$

円分多項式と原始根を結びつける 重要な関係は

${\displaystyle \prod _{d\mid n}\Phi _{d}(x)=x^{n}-1,}$

はの根であるためには、それがn を割り切る何らかのdに対してd次の原始根となることが必要であることを示している。^[1]${\displaystyle x}$${\displaystyle x^{n}-1}$ 

nが素数であれば、

${\displaystyle \Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}.}$

n = 2 p（pは2以外の 素数）の場合、

${\displaystyle \Phi _{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}.}$

nが30までの場合、円分多項式は次のようになる: ^[2]

${\displaystyle {\begin{aligned}\Phi _{1}(x)&=x-1\\\Phi _{2}(x)&=x+1\\\Phi _{3}(x)&=x^{2}+x+1\\\Phi _{4}(x)&=x^{2}+1\\\Phi _{5}(x)&=x^{4}+x^{3}+x^{2}+x+1\\\Phi _{6}(x)&=x^{2}-x+1\\\Phi _{7}(x)&=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{8}(x)&=x^{4}+1\\\Phi _{9}(x)&=x^{6}+x^{3}+1\\\Phi _{10}(x)&=x^{4}-x^{3}+x^{2}-x+1\\\Phi _{11}(x)&=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{12}(x)&=x^{4}-x^{2}+1\\\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\\\Phi _{14}(x)&=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1\\\Phi _{15}(x)&=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1\\\Phi _{16}(x)&=x^{8}+1\\\Phi _{17}(x)&=x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{18}(x)&=x^{6}-x^{3}+1\\\Phi _{19}(x)&=x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{20}(x)&=x^{8}-x^{6}+x^{4}-x^{2}+1\\\Phi _{21}(x)&=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x^{3}-x+1\\\Phi _{22}(x)&=x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1\\\Phi _{23}(x)&=x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}\\&\qquad \quad +x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{24}(x)&=x^{8}-x^{4}+1\\\Phi _{25}(x)&=x^{20}+x^{15}+x^{10}+x^{5}+1\\\Phi _{26}(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\\\Phi _{27}(x)&=x^{18}+x^{9}+1\\\Phi _{28}(x)&=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1\\\Phi _{29}(x)&=x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}\\&\qquad \quad +x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Phi _{30}(x)&=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1.\end{aligned}}}$

105番目の円分多項式は、105が3つの異なる奇数の素数の積（3×5×7）の最小の正の整数であり、この多項式が1、0、または-1以外の係数を持つ最初の多項式であるため興味深いです。 ^[3]

${\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}-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が1 または 2 の場合を除いて、それらは偶数次数の 回文です。

の次数、つまりn番目の原始根の数は であり、ここで はオイラーのトーティエント関数です。 ${\displaystyle \Phi _{n}}$${\displaystyle \varphi (n)}$${\displaystyle \varphi }$

が環の次数 の既約多項式であるという事実は、ガウスによる重要な結果です。^{[4]選択した定義に応じて、重要な結果となるのは次数の値か既約性のどちらかです。}アイゼンシュタインの基準のおかげで、 nが素数の場合は一般の場合よりも証明が容易です。 ${\displaystyle \Phi _{n}}$${\displaystyle \varphi (n)}$ ${\displaystyle \mathbb {Z} [x]}$

円分多項式に関する基本的な関係は

${\displaystyle {\begin{aligned}x^{n}-1&=\prod _{1\leqslant k\leqslant n}\left(x-e^{2i\pi {\frac {k}{n}}}\right)\\&=\prod _{d\mid n}\prod _{1\leqslant k\leqslant n \atop \gcd(k,n)=d}\left(x-e^{2i\pi {\frac {k}{n}}}\right)\\&=\prod _{d\mid n}\Phi _{\frac {n}{d}}(x)=\prod _{d\mid n}\Phi _{d}(x).\end{aligned}}}$

これは、各n乗根は、nを割り切る唯一のdに対して原始的なd乗根であることを意味します。

メビウスの反転公式により、明示的な有理分数として表現 できます。${\displaystyle \Phi _{n}(x)}$

${\displaystyle \Phi _{n}(x)=\prod _{d\mid n}(x^{d}-1)^{\mu \left({\frac {n}{d}}\right)},}$

ここで、 はメビウス関数です。 ${\displaystyle \mu }$

これは、円分多項式 の再帰式を提供します。これは、 から始めて、n を割り切る適切な約数d の円分多項式で割ることで計算できます。 ${\displaystyle \Phi _{n}(x)}$ ${\displaystyle x^{n}-1}$${\displaystyle \Phi _{d}(x)}$${\displaystyle \Phi _{1}(x)=x-1}$

${\displaystyle \Phi _{n}(x)={\frac {x^{n}-1}{\prod _{\stackrel {d|n}{{}_{d<n}}}\Phi _{d}(x)}}.}$

これは、整数因数分解と多項式の除算が利用できる場合に、任意の を計算するアルゴリズムを提供します。SageMath 、Maple、Mathematica、PARI/GPなどの多くのコンピュータ代数システムには、円分多項式を計算する組み込み関数があります。 ${\displaystyle \Phi _{n}(x)}$

上で述べたように、n = pが素数であれば、

${\displaystyle \Phi _{p}(x)=1+x+x^{2}+\cdots +x^{p-1}=\sum _{k=0}^{p-1}x^{k}\;.}$

nが1より大きい奇数の整数である 場合、

${\displaystyle \Phi _{2n}(x)=\Phi _{n}(-x)\;.}$

特に、n = 2 pが奇数の素数の2倍である場合、（上記のように）

${\displaystyle \Phi _{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}\;.}$

n = p ^mが素数累乗（pは素数）の場合、

${\displaystyle \Phi _{p^{m}}(x)=\Phi _{p}(x^{p^{m-1}})=\sum _{k=0}^{p-1}x^{kp^{m-1}}\;.}$

より一般的には、n = p ^m rでrが pと互いに素であるとき、

${\displaystyle \Phi _{p^{m}r}(x)=\Phi _{pr}(x^{p^{m-1}})\;.}$

これらの公式は、繰り返し適用することで、任意の円分多項式を平方自由指数の円分多項式で表す簡単な表現を得ることができます。qがnの素因数の積（その根号）である場合、^[5]${\displaystyle \Phi _{n}(x)}$

${\displaystyle \Phi _{n}(x)=\Phi _{q}(x^{n/q})\;.}$

これにより、 nが最大で1つの奇数の素因数を持つ場合のn次の円分多項式の公式を与えることができる。pが奇数の素数で、hとkが正の整数である場合、

${\displaystyle \Phi _{2^{m}}(x)=x^{2^{m-1}}+1\;,}$

${\displaystyle \Phi _{p^{m}}(x)=\sum _{j=0}^{p-1}x^{jp^{m-1}}\;,}$

${\displaystyle \Phi _{2^{\ell }p^{m}}(x)=\sum _{j=0}^{p-1}(-1)^{j}x^{j2^{\ell -1}p^{m-1}}\;.}$

nの他の値については、 n番目の円分多項式の計算は同様に次のように簡略化される 。ここで、q はnの異なる奇数の素因数の積である。この場合に対処するには、p が素でありn を割り切れない場合、次の式が成り立つ。^[6]${\displaystyle \Phi _{q}(x),}$

${\displaystyle \Phi _{np}(x)=\Phi _{n}(x^{p})/\Phi _{n}(x)\;.}$

円分多項式の係数の大きさを制限する問題は、多くの研究論文の対象となってきた。^[7]

nに最大2つの異なる奇数の素因数がある場合、ミゴッティはの係数がすべて集合{1, −1, 0}に含まれることを示した。^[8]${\displaystyle \Phi _{n}}$

3 つの異なる奇数の素因数の積の最初の円分多項式は係数が -2 になります (上記参照)。逆は成り立ちません。係数は {1, -1, 0} の範囲にのみ存在します。 ${\displaystyle \Phi _{105}(x);}$${\displaystyle \Phi _{231}(x)=\Phi _{3\times 7\times 11}(x)}$

n がさらに異なる奇数の素因数の積である場合、係数は非常に高い値に増加することがあります。たとえば、の係数は -22 から 23 までの範囲になります。また、6 つの異なる奇数の素数を持つ最小のnである の係数の大きさは最大 532 になります。 ${\displaystyle \Phi _{15015}(x)=\Phi _{3\times 5\times 7\times 11\times 13}(x)}$${\displaystyle \Phi _{255255}(x)=\Phi _{3\times 5\times 7\times 11\times 13\times 17}(x)}$

A ( n ) を の係数の絶対値の最大値とする。任意の正のkに対して、 A ( n ) > n ^kとなるxまでのnの数は、kとx が十分に大きいかどうかに依存する正のc ( k ) に対して少なくともc ( k )⋅ xであることが知られている。逆に、nとともに無限大に向かう任意の関数 ψ( n )に対して、ほとんどすべてのnに対してA ( n ) はn ^{ψ( n )}によって上界が定められる。^[9]${\displaystyle \Phi _{n}(x)}$

ベイトマンとヴォーンの定理の組み合わせは^{[7] 10}である 。一方で、任意の に対して、${\displaystyle \varepsilon >0}$

${\displaystyle A(n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}}$

十分に大きい正の整数に対して、そして一方では、 ${\displaystyle n}$

${\displaystyle A(n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)}}$

無限個の正の整数 に対して となります。これは特に、一変数多項式(具体的には無限個の正の整数 に対して) が、係数が元の係数よりも超多項式的に大きい因子 ( など) を持つ可能性があることを意味します。これは、一般的なLandau-Mignotte 境界からそれほど離れていません。 ${\displaystyle n}$${\displaystyle x^{n}-1}$${\displaystyle n}$${\displaystyle \Phi _{n}}$

nを奇数、平方根なし、3より大きいとすると、次の式が成り立ちます。 ^{[10] [11]}

${\displaystyle 4\Phi _{n}(z)=A_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nz^{2}B_{n}^{2}(z)}$

整数係数の特定の多項式A _n ( z ) とB _n ( z ) について、次数φ ( n )/2 の A n ( z ) と次数_φ ( n ) / 2 − 2のB _n ( z ) です。さらに、次数が偶数のときはA _n ( z ) は回文であり、次数が奇数のときは逆回文です。同様に、B _n ( z ) はnが合成数でn ≡ 3 (mod 4) のときは逆回文です。

最初のいくつかのケースは

${\displaystyle {\begin{aligned}4\Phi _{5}(z)&=4(z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{2}+z+2)^{2}-5z^{2}\\[6pt]4\Phi _{7}(z)&=4(z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{3}+z^{2}-z-2)^{2}+7z^{2}(z+1)^{2}\\[6pt]4\Phi _{11}(z)&=4(z^{10}+z^{9}+z^{8}+z^{7}+z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1)\\&=(2z^{5}+z^{4}-2z^{3}+2z^{2}-z-2)^{2}+11z^{2}(z^{3}+1)^{2}\end{aligned}}}$

nを奇数、平方数なし、3より大きいものとする。すると^[11]

${\displaystyle \Phi _{n}(z)=U_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nzV_{n}^{2}(z)}$

整数係数の多項式U _n ( z )とV _n ( z )、つまり次数φ ( n )/2のU _n ( z )と次数φ ( n )/2 − 1のV _n ( z )に対して、これは次のようにも書ける 。

${\displaystyle \Phi _{n}\left((-1)^{\frac {n-1}{2}}z\right)=C_{n}^{2}(z)-nzD_{n}^{2}(z).}$

nが偶数で、平方根がなく、2より大きい場合（これによりn /2は奇数になる）、

${\displaystyle \Phi _{\frac {n}{2}}(-z^{2})=\Phi _{2n}(z)=C_{n}^{2}(z)-nzD_{n}^{2}(z)}$

C _n ( z ) とD _n ( z ) は整数係数で、C _n ( z )_は次数φ ( n )、D _n ( z ) は次数φ ( n ) − 1です。C n ( z ) とD _n ( z ) はどちらも回文です。

最初のいくつかのケースは次のとおりです。

${\displaystyle {\begin{aligned}\Phi _{3}(-z)&=\Phi _{6}(z)=z^{2}-z+1\\&=(z+1)^{2}-3z\\[6pt]\Phi _{5}(z)&=z^{4}+z^{3}+z^{2}+z+1\\&=(z^{2}+3z+1)^{2}-5z(z+1)^{2}\\[6pt]\Phi _{6/2}(-z^{2})&=\Phi _{12}(z)=z^{4}-z^{2}+1\\&=(z^{2}+3z+1)^{2}-6z(z+1)^{2}\end{aligned}}}$

シスター・バイター予想は、 3つの奇数素数を持つ3元円分多項式の係数の最大サイズ（絶対値）に関するものである。 ^[12]${\displaystyle A(pqr)}$ ${\displaystyle \Phi _{pqr}(x)}$${\displaystyle p\leq q\leq r}$

素数pの元を持つ有限体上で、 pの倍数でない任意の整数nに対して、円分多項式は次数dの既約多項式に因数分解されます。ここではオイラーのトーティエント関数、dはnを法とするpの乗法位数です。特に、が既約となるのは、p がn を法とする原始根である場合、つまりp はn を割り切れず、n を法とするその乗法位数がの次数 である場合のみです。^[13]${\displaystyle \Phi _{n}}$${\displaystyle {\frac {\varphi (n)}{d}}}$${\displaystyle \varphi (n)}$${\displaystyle \Phi _{n}}$ ${\displaystyle \varphi (n)}$${\displaystyle \Phi _{n}}$

これらの結果はp進整数に対しても成り立ちます。これは、ヘンゼルの補題により、 p個の元を持つ体上の因数分解をp進整数上の因数分解に持ち上げることができるためです。

x が任意の実数値を取る場合、任意のn ≥ 3に対して(これは、 n ≥ 3に対して、円分多項式の根がすべて非実数であるという事実から導かれます)。 ${\displaystyle \Phi _{n}(x)>0}$

x に整数値が与えられたときに円分多項式が取る値を調べるには、 n = 1および n = 2の場合は自明であるため (および) 、 n ≥ 3 の場合のみを考慮すれば十分です。 ${\displaystyle \Phi _{1}(x)=x-1}$${\displaystyle \Phi _{2}(x)=x+1}$

n ≥ 2 の場合、

${\displaystyle \Phi _{n}(0)=1,}$

${\displaystyle \Phi _{n}(1)=1}$nが素数累乗でない場合、

${\displaystyle \Phi _{n}(1)=p}$がk ≥ 1の素数累乗である場合。${\displaystyle n=p^{k}}$

円分多項式がxの他の整数値に対して取る値は、素数を法と する乗法順序と強く関連しています。${\displaystyle \Phi _{n}(x)}$

より正確には、素数pとpと互いに素な整数bがある場合、 pを法とするbの乗法位数は、 p がnの約数となる最小の正の整数nです。 b > 1 の場合、 pを法とするbの乗法位数は、数値基数bでの1/ pの表現の最短周期でもあります( 「一意の素数」を参照してください。これが表記法の選択を説明しています)。 ${\displaystyle b^{n}-1.}$

乗法順序の定義は、n がp を法とするbの乗法順序である場合、p はの約数であることを意味します。逆は真ではありませんが、次のようになります。 ${\displaystyle \Phi _{n}(b).}$

n > 0が正の整数でb > 1が整数である場合、（証明については下記を参照）

${\displaystyle \Phi _{n}(b)=2^{k}gh,}$

どこ

• k は負でない整数で、 bが偶数のときは常に 0 になります。(実際、 nが 1 でも 2 でもない場合は、 kは 0 か 1 になります。また、 nが2 の累乗でない、 k は常に 0 になります)
• g は1 またはnの最大の奇数素因数です。
• hは奇数で、 nと互いに素であり、その素因数はちょうど奇数の素数pであり、 n はpを法としてbの乗法順序となります。

これは、 pが奇数の素因数である場合、nはp − 1の約数であるか、pがnの約数であるかのいずれかであることを意味する。後者の場合、は${\displaystyle \Phi _{n}(b),}$${\displaystyle p^{2}}$${\displaystyle \Phi _{n}(b).}$

ジグモンディの定理によれば、 b > 1かつh = 1となる のは

${\displaystyle {\begin{aligned}\Phi _{1}(2)&=1\\\Phi _{2}\left(2^{k}-1\right)&=2^{k}&&k>0\\\Phi _{6}(2)&=3\end{aligned}}}$