Русская Википедия:Круговой многочлен

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

<math>\Phi_n(x)=\prod_k(x-\xi^k_n)</math>

где

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

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

Свойства

  • Коэффициенты кругового многочлена являются целыми числами.
  • Степень кругового многочлена <math>\mathop{\mathrm{deg}}\, \Phi_n=\varphi(n)</math>, где <math>\varphi</math> — функция Эйлера.
  • Круговой многочлен удовлетворяет соотношению
<math>\prod_{d|n} \Phi_{d}(x)=x^n - 1</math>
где произведение берется по всем положительным делителям <math>d</math> числа <math>n</math>, включая единицу и само <math>n</math>. Это равенство можно переписать в следующем виде:
<math>

\Phi_n(x)=\frac{x^n - 1}{\prod_{d|n, \, d<n} \Phi_d(x)}. </math>

  • Для многочлена <math>\Phi_n(x)</math> можно указать явное выражение через функцию Мёбиуса:
<math>\Phi_n(x)=\prod_{d|n}(x^d-1)^{\mu(n/d)}</math>
  • Частный случай предыдущей формулы: если <math>n=p</math> — простое число, то
<math>\Phi_n(x)=\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+\cdots+1</math>
  • Если <math>n=2m</math>, где <math>m</math> — нечётное число, большее одного то:
<math>\Phi_{2m}(x) = \Phi_{m}(-x)</math>
  • Если <math>m</math> - максимальное натуральное число, делящее <math>n</math>, и свободное от квадратов (радикал <math>n</math>), и <math>d=n/m</math>, то
<math>\Phi_n(x) = \Phi_m(x^d)</math>
  • Если <math>p</math> - простое число, не делящее <math>n</math>, то
<math>\Phi_{pn}(x) = \frac{\Phi_n(x^p)}{\Phi_n(x)}</math>
  • Над полем рациональных чисел все многочлены <math>\Phi_n(x)</math> неприводимы, но над конечными простыми полями эти многочлены могут быть приводимы.Так, если <math>p</math> - простое число, то по модулю <math>p</math> многочлен <math>\Phi_{p-1}(x)</math> разлагается на линейные множители, а многочлен <math>\Phi_{p+1}(x)</math> раскладывается в произведение (различных) многочленов степени 2 (неприводимых над кольцом <math>\mathbb{Z}_p</math>), со свободными членами, равными 1.
    • Например:
<math>\Phi_{8}(x)=x^4+1=(x^2+4x+1)(x^2-4x+1)\pmod{7}</math>
<math>\Phi_{12}(x)=x^4-x^2+1=(x^2+5x+1)(x^2-5x+1)\pmod{11}</math>
<math>\Phi_{14}(x)=(x^2-6x+1)(x^2-5x+1)(x^2-3x+1)\pmod{13}</math>
  • Более общим является следующий факт: Если p — простое число, n — натуральное, то многочлен <math>\Phi_{\Phi_n(p)}(x)</math> по модулю p раскладывается в произведение многочленов степени n. Если n ещё и простое, то многочлены степени n, участвующие в разложении, неприводимы над кольцом <math>\mathbb{Z}_p</math>.

Примеры

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

<math>\Phi_1(x) = x - 1</math>
<math>\Phi_2(x) = x + 1</math>
<math>\Phi_3(x) = x^2 + x + 1</math>
<math>\Phi_4(x) = x^2 + 1</math>
<math>\Phi_5(x) = x^4 + x^3 + x^2 + x +1</math>
<math>\Phi_6(x) = x^2 - x + 1</math>
<math>\Phi_7(x) = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1</math>
<math>\Phi_8(x) = x^4 + 1</math>
<math>\Phi_9(x) = x^6 + x^3 + 1</math>
<math>\Phi_{10}(x) = x^4 - x^3 + x^2 - x + 1</math>
<math>\Phi_{11}(x) = x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1</math>
<math>\Phi_{12}(x) = x^4 - x^2 + 1</math>
<math>\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</math>
<math>\Phi_{14}(x) = x^6 - x^5 + x^4 - x^3 + x^2 - x + 1</math>
<math>\Phi_{15}(x) = x^8 - x^7 + x^5 - x^4 + x^3 - x + 1</math>
<math>\Phi_{16}(x) = x^8 + 1</math>
<math>\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</math>
<math>\Phi_{18}(x) = x^6 - x^3 + 1</math>
<math>\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</math>
<math>\Phi_{20}(x) = x^8 - x^6 + x^4 - x^2 + 1</math>
<math>\Phi_{21}(x) = x^{12} - x^{11} + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1</math>
<math>\Phi_{22}(x) = x^{10} - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1</math>
<math>\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</math>
<math>\Phi_{24}(x) = x^8 - x^4 + 1</math>
<math>\Phi_{25}(x) = x^{20} + x^{15} + x^{10} + x^5 + 1</math>
<math>\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</math>
<math>\Phi_{27}(x) = x^{18} + x^9 + 1</math>
<math>\Phi_{28}(x) = x^{12} - x^{10} + x^8 - x^6 + x^4 - x^2 + 1</math>
<math>\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</math>
<math>\Phi_{30}(x) = x^8 + x^7 - x^5 - x^4 - x^3 + x + 1</math>

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

<math>\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}</math>

Приложения

Одним из важнейших приложений круговых многочленов является теорема о мультипликативной группе конечного поля:

Теорема. Мультипликативная группа <math>K^*</math> конечного поля <math>K</math> является циклической группой.

Доказательство. Пусть поле <math>K</math> состоит из <math>n+1</math> элемента, тогда его мультипликативная группа (группа обратимых элементов) <math>K^*</math> содержит все элементы поля, кроме нуля, то есть состоит из <math>n</math> элементов. По теореме Лагранжа порядок элемента группы делит порядок этой группы, следовательно, для любого элемента <math>a\in K^*</math> выполнено <math>a^n = 1</math>, то есть все элементы из <math>K^*</math> являются корнями уравнения <math>x^n-1=0</math>. Тогда

<math>\prod\limits_{a\in K^*}(x-a) = x^n-1</math>,

так как все корни левой части являются корнями правой части и степени и старшие члены обоих многочленов равны.

Так как

<math>x^n - 1 = \prod\limits_{d|n}\Phi_d(x)</math> и <math>\deg \Phi_d(x) =\varphi(d)\geqslant 1</math>,

то многочлен <math>\Phi_n(x)</math> имеет ровно <math>\varphi(n)</math> корней в <math>K</math> (и, значит, хотя бы один). Его корни являются элементами группы <math>K^*</math> порядка <math>n</math>, то есть циклическая группа, образованная любым из них, содержит <math>n</math> различных элементов и должна совпадать со всей группой <math>K^*</math>, откуда следует цикличность этой группы.

См. также

Литература

Примечания

Шаблон:Примечания

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ OEIS Шаблон:OEIS short.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Круговой_многочлен&oldid=10202256