Cyclotomic polynomial

The cyclotomic polynomials are monic polynomials with integer coefficients that are irreducible over the field of the rational numbers. Except for n equal to 1 or 2, they are palindromes of even degree.

The degree of ${\displaystyle \Phi _{n}}$, or in other words the number of nth primitive roots of unity, is ${\displaystyle \varphi (n)}$, where ${\displaystyle \varphi }$ is Euler's totient function.

The fact that ${\displaystyle \Phi _{n}}$ is an irreducible polynomial of degree ${\displaystyle \varphi (n)}$ in the ring${\displaystyle \mathbb {Z} [x]}$هي نتيجة غير بديهية منسوبة إلى غاوس . ^{[ 4 ]} وبحسب التعريف المُختار، فإن قيمة الدرجة أو عدم الاختزال هي النتيجة غير البديهية. ويُعدّ إثبات حالة العدد الأولي n أسهل من الحالة العامة، وذلك بفضل معيار أيزنشتاين .

العلاقة الأساسية التي تتضمن كثيرات الحدود الدائرية هي

${\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 للوحدة هو جذر بدائي من الرتبة d للوحدة لـ d فريد يقسم n .

تسمح صيغة انعكاس موبيوس${\displaystyle \Phi _{n}(x)}$يُعبَّر عنه ككسر نسبي صريح:

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

أين${\displaystyle \mu }$هي دالة موبيوس .

يوفر هذا صيغة تكرارية لكثير الحدود الدائري${\displaystyle \Phi _{n}(x)}$والتي يمكن حسابها عن طريق القسمة${\displaystyle x^{n}-1}$بواسطة كثيرات الحدود الدائرية${\displaystyle \Phi _{d}(x)}$بالنسبة للقواسم الصحيحة d التي تقسم n ، بدءًا من${\displaystyle \Phi _{1}(x)=x-1}$:

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

وهذا يوفر خوارزمية لحساب أي${\displaystyle \Phi _{n}(x)}$بشرط توفر تحليل وقسمة كثيرات الحدود إلى عواملها الصحيحة . تحتوي العديد من أنظمة الجبر الحاسوبية ، مثل SageMath و Maple و Mathematica و PARI/GP ، على دالة مدمجة لحساب كثيرات الحدود الدائرية.

كما ذُكر أعلاه، إذا كان n = p عددًا أوليًا، فإن

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

إذا كان n عددًا فرديًا أكبر من واحد، فإن

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

على وجه الخصوص، إذا كان n = 2p ضعف عدد أولي فردي، فإن (كما ذكر أعلاه)

${\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}})\;.}$

يمكن تطبيق هذه الصيغ بشكل متكرر للحصول على تعبير بسيط لأي متعدد حدود حلقي${\displaystyle \Phi _{n}(x)}$من حيث كثير الحدود الدائري ذو الدليل الخالي من المربعات : إذا كان q هو حاصل ضرب القواسم الأولية لـ n ( جذره )، فإن ^{[ 5 ]}

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

يسمح هذا بإعطاء صيغ لكثير الحدود الدائري من الرتبة n عندما يكون لـ n عامل أولي فردي واحد على الأكثر: إذا كان p عددًا أوليًا فرديًا، و${\displaystyle \ell }$إذا كان m و m عددين صحيحين موجبين، فإن

${\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 بشكل مماثل إلى حساب متعددة الحدود الدائرية رقم n. ${\displaystyle \Phi _{q}(x),}$حيث q هو حاصل ضرب القواسم الأولية الفردية المختلفة للعدد n . وللتعامل مع هذه الحالة، يكون لدينا أنه بالنسبة لـ p عدد أولي ولا يقسم n ، ^{[ 6 ]}

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

لقد كانت مشكلة تحديد مقدار معاملات كثيرات الحدود الدائرية موضوعًا لعدد من الأبحاث. ^{[ 7 ]}

إذا كان للعدد n عاملان أوليان فرديان مختلفان على الأكثر، فقد أثبت ميغوتي أن معاملات${\displaystyle \Phi _{n}}$جميعها تنتمي إلى المجموعة {1، -1، 0}. ^{[ 8 ]}

أول متعددة حدود حلقية لناتج ثلاثة عوامل أولية فردية مختلفة هي${\displaystyle \Phi _{105}(x);}$معاملها هو -2 (انظر أعلاه ). والعكس غير صحيح:${\displaystyle \Phi _{231}(x)=\Phi _{3\times 7\times 11}(x)}$لا تحتوي إلا على معاملات في {1، -1، 0}.

إذا كان n ناتج ضرب عدة عوامل أولية فردية مختلفة، فقد ترتفع المعاملات إلى قيم عالية جدًا. على سبيل المثال،${\displaystyle \Phi _{15015}(x)=\Phi _{3\times 5\times 7\times 11\times 13}(x)}$تتراوح معاملاته من -22 إلى 23؛ كذلك${\displaystyle \Phi _{255255}(x)=\Phi _{3\times 5\times 7\times 11\times 13\times 17}(x)}$، أصغر عدد n يحتوي على 6 أعداد أولية فردية مختلفة، له معاملات تصل قيمتها إلى 532.

لنفترض أن A ( n ) يمثل القيمة المطلقة القصوى لمعاملات${\displaystyle \Phi _{n}(x)}$من المعروف أنه لأي قيمة موجبة لـ k ، فإن عدد قيم n حتى x التي تحقق A ( n ) > nk يساوي على الأقل c ( k ) ⋅x، وذلك لقيمة موجبة لـ c ( k ) تعتمد على k وقيمة x كبيرة بما ^فيه الكفاية. في الاتجاه المعاكس، لأي دالة ψ( n ) تؤول إلى اللانهاية مع n، فإن A ( n ) تكون محدودة من الأعلى بـ nψ ^{( n )} لجميع قيم n تقريبًا . ^{[ 9 ]}

تنص مجموعة من نظريات باتمان وفون على ما يلي ^{[ 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)}}$

لعدد لا نهائي من الأعداد الصحيحة الموجبة${\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 ) ذات المعاملات الصحيحة، فإن A _{_n} ( z ) من الدرجة φ ( n )/2، و B _{_n} ( z ) من الدرجة φ ( n )/2 - 2. علاوة على ذلك، تكون 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 ) ذات المعاملات الصحيحة، U _{_n} ( z ) من الدرجة φ ( n )/2، و V _{_n} ( z ) من الدرجة φ ( n )/2 - 1. يمكن كتابة ذلك أيضًا على النحو التالي:

${\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}}}$

تتعلق فرضية الأخت بيتر بالحجم الأقصى (بالقيمة المطلقة ) .${\displaystyle A(pqr)}$معاملات كثيرات الحدود الدائرية الثلاثية${\displaystyle \Phi _{pqr}(x)}$أين${\displaystyle p\leq q\leq r}$ثلاثة أعداد أولية فردية. ^{[ 12 ]}

إن العلاقات التكرارية الخطية ذات المعاملات الثابتة والتي تكون دورية هي بالضبط معاملات متسلسلة القوى للدوال الكسرية التي تكون مقاماتها عبارة عن نواتج لكثيرات الحدود الدائرية.

في نظرية الدوال المولدة التوافقية ، يحدد مقام الدالة الكسرية علاقة تكرارية خطية لمعاملات متسلسلة القوى الخاصة بها. على سبيل المثال، متتابعة فيبوناتشي لها دالة مولدة

${\displaystyle F(x)=F_{1}x+F_{2}x^{2}+F_{3}x^{3}+\cdots ={\frac {x}{1-x-x^{2}}},}$

ومساواة المعاملات على كلا الجانبين من${\displaystyle F(x)(1-x-x^{2})=x}$أعطِ${\displaystyle F_{n}-F_{n-1}-F_{n-2}=0}$ل${\displaystyle n\geq 2}$.

أي دالة كسرية يكون مقامها قاسمًا لـ${\displaystyle x^{n}-1}$تحتوي على متتالية متكررة من المعاملات دورية بفترة لا تتجاوز n . على سبيل المثال،

${\displaystyle P(x)=-{\frac {1+2x}{\Phi _{6}(x)}}={\frac {1+2x}{1-x+x^{2}}}=\sum _{n\geq 0}P_{n}x^{n}=1+3x+2x^{2}-x^{3}-3x^{4}-2x^{5}+x^{6}+3x^{7}+2x^{8}+\cdots }$

لها معاملات محددة بواسطة التكرار${\displaystyle P_{n}-P_{n-1}+P_{n-2}=0}$ل${\displaystyle n\geq 2}$، بدءًا من${\displaystyle P_{0}=1,P_{1}=3}$. لكن${\displaystyle 1-x^{6}=\Phi _{6}(x)\Phi _{3}(x)\Phi _{2}(x)\Phi _{1}(x)}$لذلك يمكننا أن نكتب

${\displaystyle P(x)={\frac {(1+2x)\Phi _{3}(x)\Phi _{2}(x)\Phi _{1}(x)}{1-x^{6}}}={\frac {1+3x+2x^{2}-x^{3}-3x^{4}-2x^{5}}{1-x^{6}}},}$

وهذا يعني${\displaystyle P_{n}-P_{n-6}=0}$ل${\displaystyle n\geq 6}$والمتتالية لها دورة 6 بقيم ابتدائية معطاة بمعاملات البسط.