Круговой многочлен

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Круговой многочлен, или многочлен деления кругамногочлен вида

\Phi_n(x)=\prod_k(x-\xi^k_n)

где

\xi^k_n=\cos\frac{2\pi k}n+i\sin\frac{2\pi k}n

представляет собой корень степени n из единицы, а произведение берётся по всем натуральным числам k, меньшим n, и взаимно простым с n.

Свойства[править | править вики-текст]

\prod_{d|n} \Phi_{d}(x)=x^n - 1
где произведение берется по всем положительным делителям d числа n, включая единицу и само n. Это можно переписать как

\Phi_n(x)=\frac{x^n - 1}{\prod_{d|n, \, d<n} \Phi_d(x)}.
\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}
  • В частности, если n=p — простое, то
\Phi_n(x)=\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+\cdots+1.
  • Коэффициенты кругового многочлена являются целыми числами.
  • Над полем рациональных чисел все многочлены \Phi_n(x) неприводимы, но над конечными простыми полями эти многочлены могут быть приводимы.
    • Например: над полем вычетов по модулю 11 имеет место соотношение:
\Phi_{12}(x)=x^4-x^2+1=(x^2+5x+1)(x^2-5x+1).

Примеры[править | править вики-текст]

Приведём сводку первых 30 круговых многочленов[1].

~\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} + 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} + 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

Из этой сводки можно сделать вывод, что коэффициенты кругового многочлена всегда равны \pm 1, но это предположение неверно. Первый контрпример даёт 105-й многочлен:

\begin{align}\Phi_{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\end{align}

Если nпростое число, то:

~\Phi_n(x) = 1+x+x^2+\cdots+x^{n-1}=\sum_{i=0}^{n-1} x^i.

Если n=2 p, где p — нечётное простое число, то:

~\Phi_{2p}(x) = 1-x+x^2-\cdots+x^{p-1}=\sum_{i=0}^{p-1} (-x)^i.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Примечания[править | править вики-текст]

  1. OEIS A013595.