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

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

${\displaystyle \Phi _{n}(x)=\prod _{k}(x-\xi _{n}^{k})}$

где

${\displaystyle \xi _{n}^{k}=\cos {\frac {2\pi k}{n}}+i\sin {\frac {2\pi k}{n}}}$

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

Свойства

• Коэффициенты кругового многочлена являются целыми числами.
• Степень кругового многочлена ${\displaystyle \mathop {\mathrm {deg} } \,\Phi _{n}=\varphi (n)}$, где ${\displaystyle \varphi }$ — функция Эйлера.
• Круговой многочлен удовлетворяет соотношению

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

где произведение берется по всем положительным делителям ${\displaystyle d}$ числа ${\displaystyle n}$, включая единицу и само ${\displaystyle n}$. Это равенство можно переписать в следующем виде:

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

• Для многочлена ${\displaystyle \Phi _{n}(x)}$ можно указать явное выражение через функцию Мёбиуса:

${\displaystyle \Phi _{n}(x)=\prod _{d|n}(x^{d}-1)^{\mu (n/d)}}$

• Частный случай предыдущей формулы: если ${\displaystyle n=p}$ — простое число, то

${\displaystyle \Phi _{n}(x)={\frac {x^{p}-1}{x-1}}=x^{p-1}+x^{p-2}+\cdots +1}$

• Если ${\displaystyle n=2m}$, где ${\displaystyle m}$ — нечётное число, большее единицы, то:

${\displaystyle \Phi _{2m}(x)=\Phi _{m}(-x)}$

• Если ${\displaystyle m}$ — максимальное натуральное число, делящее ${\displaystyle n}$, и свободное от квадратов (радикал ${\displaystyle n}$), и ${\displaystyle d=n/m}$, то

${\displaystyle \Phi _{n}(x)=\Phi _{m}(x^{d})}$

• Если ${\displaystyle p}$ — простое число, не делящее ${\displaystyle n}$, то

${\displaystyle \Phi _{pn}(x)={\frac {\Phi _{n}(x^{p})}{\Phi _{n}(x)}}}$

• Над полем рациональных чисел все многочлены ${\displaystyle \Phi _{n}(x)}$ неприводимы, но над конечными простыми полями эти многочлены могут быть приводимы. Так, если ${\displaystyle p}$ — простое число, то по модулю ${\displaystyle p}$ многочлен ${\displaystyle \Phi _{p-1}(x)}$ разлагается на линейные множители, а многочлен ${\displaystyle \Phi _{p+1}(x)}$ раскладывается в произведение (различных) многочленов степени 2 (неприводимых над кольцом ${\displaystyle \mathbb {Z} _{p}}$), со свободными членами, равными 1.
  • Например:

${\displaystyle \Phi _{8}(x)=x^{4}+1=(x^{2}+4x+1)(x^{2}-4x+1){\pmod {7}}}$

${\displaystyle \Phi _{12}(x)=x^{4}-x^{2}+1=(x^{2}+5x+1)(x^{2}-5x+1){\pmod {11}}}$

${\displaystyle \Phi _{14}(x)=(x^{2}-6x+1)(x^{2}-5x+1)(x^{2}-3x+1){\pmod {13}}}$

• Более общим является следующий факт: Если p — простое число, n — натуральное, то многочлен ${\displaystyle \Phi _{\Phi _{n}(p)}(x)}$ по модулю p раскладывается в произведение многочленов степени n. Если n ещё и простое, то многочлены степени n, участвующие в разложении, неприводимы над кольцом ${\displaystyle \mathbb {Z} _{p}}$.
• При ${\displaystyle x\geqslant 1}$

${\displaystyle |x-1|^{\varphi (n)}\leqslant \Phi _{n}(x)\leqslant |x+1|^{\varphi (n)}}$

Примеры

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

${\displaystyle \Phi _{1}(x)=x-1}$

${\displaystyle \Phi _{2}(x)=x+1}$

${\displaystyle \Phi _{3}(x)=x^{2}+x+1}$

${\displaystyle \Phi _{4}(x)=x^{2}+1}$

${\displaystyle \Phi _{5}(x)=x^{4}+x^{3}+x^{2}+x+1}$

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

${\displaystyle \Phi _{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1}$

${\displaystyle \Phi _{8}(x)=x^{4}+1}$

${\displaystyle \Phi _{9}(x)=x^{6}+x^{3}+1}$

${\displaystyle \Phi _{10}(x)=x^{4}-x^{3}+x^{2}-x+1}$

${\displaystyle \Phi _{11}(x)=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1}$

${\displaystyle \Phi _{12}(x)=x^{4}-x^{2}+1}$

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

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

${\displaystyle \Phi _{15}(x)=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1}$

${\displaystyle \Phi _{16}(x)=x^{8}+1}$

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

${\displaystyle \Phi _{18}(x)=x^{6}-x^{3}+1}$

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

${\displaystyle \Phi _{20}(x)=x^{8}-x^{6}+x^{4}-x^{2}+1}$

${\displaystyle \Phi _{21}(x)=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x^{3}-x+1}$

${\displaystyle \Phi _{22}(x)=x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1}$

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

${\displaystyle \Phi _{24}(x)=x^{8}-x^{4}+1}$

${\displaystyle \Phi _{25}(x)=x^{20}+x^{15}+x^{10}+x^{5}+1}$

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

${\displaystyle \Phi _{27}(x)=x^{18}+x^{9}+1}$

${\displaystyle \Phi _{28}(x)=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1}$

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

${\displaystyle \Phi _{30}(x)=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1}$

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

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

Приложения

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

Теорема. Мультипликативная группа ${\displaystyle K^{*}}$ конечного поля ${\displaystyle K}$ является циклической группой.

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

${\displaystyle \prod \limits _{a\in K^{*}}(x-a)=x^{n}-1}$,

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

Так как

${\displaystyle x^{n}-1=\prod \limits _{d|n}\Phi _{d}(x)}$ и ${\displaystyle \deg \Phi _{d}(x)=\varphi (d)\geqslant 1}$,

то многочлен ${\displaystyle \Phi _{n}(x)}$ имеет ровно ${\displaystyle \varphi (n)}$ корней в ${\displaystyle K}$ (и, значит, хотя бы один). Его корни являются элементами группы ${\displaystyle K^{*}}$ порядка ${\displaystyle n}$, то есть циклическая группа, образованная любым из них, содержит ${\displaystyle n}$ различных элементов и должна совпадать со всей группой ${\displaystyle K^{*}}$, откуда следует цикличность этой группы.

См. также

• Круговое поле

Примечания

1. Математическая энциклопедия, 1979.
2. OEIS A013595.

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987.
• Ван дер Варден Б. Л. Алгебра. М.: Мир, 1975.
• Деления круга многочлен // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1979. — Т. 2. — Стб. 81—82. — 1104 с.