Циклотомический полином
Неприводимый многочлен, корни которого являются корнями n-й степени из единицы

В математике n -й циклотомический многочлен для любого положительного целого числа n — это единственный неприводимый многочлен с целыми коэффициентами , который является делителем и не является делителем для любого k < n . Его корни — все n-е примитивные корни из единицы , где k пробегает положительные целые числа, меньшие n , и взаимно просты с n (а i — мнимая единица ). Другими словами, n-й циклотомический многочлен равен х н − 1 {\displaystyle x^{n}-1} х к − 1 {\displaystyle x^{k}-1} е 2 я π к н {\displaystyle е^{2i\pi {\frac {k}{n}}}}

Ф н ( х ) = ∏ нод ( к , н ) = 1 1 ≤ к ≤ н ( х − е 2 я π к н ) . {\displaystyle \Phi _{n}(x)=\prod _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(xe^{2i\pi { \frac {k}{n}}}\right).}

Его также можно определить как монический многочлен с целыми коэффициентами, который является минимальным многочленом над полем рациональных чисел любого примитивного корня степени n из единицы ( является примером такого корня). е 2 я π / н {\displaystyle e^{2i\пи /n}}

Важное соотношение, связывающее циклотомические многочлены и первообразные корни из единицы, заключается в следующем:

∏ г ∣ н Ф г ( х ) = х н − 1 , {\displaystyle \prod _{d\mid n}\Phi _{d}(x)=x^{n}-1,}

показывая, что является корнем тогда и только тогда, когда он является d- м примитивным корнем из единицы для некоторого d , который делит n . [1] х {\displaystyle x} х н − 1 {\displaystyle x^{n}-1}  

Примеры

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

Ф н ( х ) = 1 + х + х 2 + ⋯ + х н − 1 = ∑ к = 0 н − 1 х к . {\displaystyle \Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}.}

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

Ф 2 п ( х ) = 1 − х + х 2 − ⋯ + х п − 1 = ∑ к = 0 п − 1 ( − х ) к . {\displaystyle \Phi _{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}.}

Для n до 30 циклотомические многочлены имеют вид: [2]

Ф 1 ( х ) = х − 1 Ф 2 ( х ) = х + 1 Ф 3 ( х ) = х 2 + х + 1 Ф 4 ( х ) = х 2 + 1 Ф 5 ( х ) = х 4 + х 3 + х 2 + х + 1 Ф 6 ( х ) = х 2 − х + 1 Ф 7 ( х ) = х 6 + х 5 + х 4 + х 3 + х 2 + х + 1 Ф 8 ( х ) = х 4 + 1 Ф 9 ( х ) = х 6 + х 3 + 1 Ф 10 ( х ) = х 4 − х 3 + х 2 − х + 1 Ф 11 ( х ) = х 10 + х 9 + х 8 + х 7 + х 6 + х 5 + х 4 + х 3 + х 2 + х + 1 Ф 12 ( х ) = х 4 − х 2 + 1 Ф 13 ( х ) = х 12 + х 11 + х 10 + х 9 + х 8 + х 7 + х 6 + х 5 + х 4 + х 3 + х 2 + х + 1 Ф 14 ( х ) = х 6 − х 5 + х 4 − х 3 + х 2 − х + 1 Ф 15 ( х ) = х 8 − х 7 + х 5 − х 4 + х 3 − х + 1 Ф 16 ( х ) = х 8 + 1 Ф 17 ( х ) = х 16 + х 15 + х 14 + х 13 + х 12 + х 11 + х 10 + х 9 + х 8 + х 7 + х 6 + х 5 + х 4 + х 3 + х 2 + х + 1 Ф 18 ( х ) = х 6 − х 3 + 1 Ф 19 ( х ) = х 18 + х 17 + х 16 + х 15 + х 14 + х 13 + х 12 + х 11 + х 10 + х 9 + х 8 + х 7 + х 6 + х 5 + х 4 + х 3 + х 2 + х + 1 Ф 20 ( х ) = х 8 − х 6 + х 4 − х 2 + 1 Ф 21 ( х ) = х 12 − х 11 + х 9 − х 8 + х 6 − х 4 + х 3 − х + 1 Ф 22 ( х ) = х 10 − х 9 + х 8 − х 7 + х 6 − х 5 + х 4 − х 3 + х 2 − х + 1 Ф 23 ( х ) = х 22 + х 21 + х 20 + х 19 + х 18 + х 17 + х 16 + х 15 + х 14 + х 13 + х 12 + х 11 + х 10 + х 9 + х 8 + х 7 + х 6 + х 5 + х 4 + х 3 + х 2 + х + 1 Ф 24 ( х ) = х 8 − х 4 + 1 Ф 25 ( х ) = х 20 + х 15 + х 10 + х 5 + 1 Ф 26 ( х ) = х 12 − х 11 + х 10 − х 9 + х 8 − х 7 + х 6 − х 5 + х 4 − х 3 + х 2 − х + 1 Ф 27 ( х ) = х 18 + х 9 + 1 Ф 28 ( х ) = х 12 − х 10 + х 8 − х 6 + х 4 − х 2 + 1 Ф 29 ( х ) = х 28 + х 27 + х 26 + х 25 + х 24 + х 23 + х 22 + х 21 + х 20 + х 19 + х 18 + х 17 + х 16 + х 15 + х 14 + х 13 + х 12 + х 11 + х 10 + х 9 + х 8 + х 7 + х 6 + х 5 + х 4 + х 3 + х 2 + х + 1 Ф 30 ( х ) = х 8 + х 7 − х 5 − х 4 − х 3 + х + 1. {\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\\ \Фи _{8}(x)&=x^{4}+1\\\Phi _{9}(x)&=x^{6}+x^{3}+1\\\Phi _{10}(x)&=x^{4}-x^{3}+x^{ 2}-x+1\\\Фи _{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\\\Фи _{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\\\Фи _{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\\\Фи _{18}(x)&=x^{6}-x^{3}+1\\\Phi _{19}(x)&=x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12} +х^{11} +x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x ^{2}+x+1\\\Фи _{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\\\Фи _{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 \ четверка +x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+ x^{3}+x^{2}+x+1\\\Фи _{24}(x)&=x^{8}-x^{4}+1\\\Phi _{25}(x)&=x^{20}+x^{15}+x^{ 10}+x^{5}+1\\\Фи _{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\\\Фи _{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 + х^{14}+х^{13}+х^{12}+х^{11}+х^{10}+х^{9}+х^{8}+х^{7}+х^ {6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\\\Фи _{30}(x)&=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1.\end{align}}}

Случай 105-го циклотомического многочлена интересен, поскольку 105 — это наименьшее положительное целое число, являющееся произведением трех различных нечетных простых чисел (3×5×7), и этот многочлен — первый, имеющий коэффициент, отличный от 1, 0 или −1: [3]

Ф 105 ( х ) = х 48 + х 47 + х 46 − х 43 − х 42 − 2 х 41 − х 40 − х 39 + х 36 + х 35 + х 34 + х 33 + х 32 + х 31 − х 28 − х 26 − х 24 − х 22 − х 20 + х 17 + х 16 + х 15 + х 14 + х 13 + х 12 − х 9 − х 8 − 2 х 7 − х 6 − х 5 + х 2 + х + 1. {\displaystyle {\begin{aligned}\Фи _{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{align}}}

Характеристики

Фундаментальные инструменты

Циклотомические многочлены — это монические многочлены с целыми коэффициентами, неприводимые над полем рациональных чисел. За исключением n, равного 1 или 2, они являются палиндромами четной степени.

Степень , или, другими словами, число n- ных первообразных корней из единицы, равна , где — функция Эйлера . Ф н {\displaystyle \Фи _{n}} φ ( н ) {\displaystyle \varphi (n)} φ {\displaystyle \varphi}

Тот факт, что является неприводимым многочленом степени в кольце , является нетривиальным результатом Гаусса . [ 4] В зависимости от выбранного определения, нетривиальным результатом является либо значение степени, либо неприводимость. Случай простого n доказать легче, чем общий случай, благодаря критерию Эйзенштейна . Ф н {\displaystyle \Фи _{n}} φ ( н ) {\displaystyle \varphi (n)} З [ х ] {\displaystyle \mathbb {Z} [x]}

Фундаментальное соотношение, включающее циклотомические полиномы, имеет вид

x n − 1 = ∏ 1 ⩽ k ⩽ n ( x − e 2 i π k n ) = ∏ d ∣ n ∏ 1 ⩽ k ⩽ n gcd ( k , n ) = d ( x − e 2 i π k n ) = ∏ d ∣ n Φ n d ( x ) = ∏ d ∣ n Φ d ( 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-й степени из единицы является примитивным корнем d- й степени из единицы для уникального d, делящего n .

Формула обращения Мёбиуса позволяет выразить в виде явной рациональной дроби: Φ n ( x ) {\displaystyle \Phi _{n}(x)}

Φ n ( x ) = ∏ d ∣ n ( x d − 1 ) μ ( n d ) , {\displaystyle \Phi _{n}(x)=\prod _{d\mid n}(x^{d}-1)^{\mu \left({\frac {n}{d}}\right)},}

где - функция Мёбиуса . μ {\displaystyle \mu }

Циклотомический многочлен может быть вычислен путем (точного) деления на циклотомические многочлены собственных делителей n, ранее вычисленные рекурсивно тем же методом: Φ n ( x ) {\displaystyle \Phi _{n}(x)} x n − 1 {\displaystyle x^{n}-1}

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

(Напомним, что .) Φ 1 ( x ) = x − 1 {\displaystyle \Phi _{1}(x)=x-1}

Эта формула определяет алгоритм вычисления для любого n , при условии, что доступны целочисленная факторизация и деление многочленов . Многие системы компьютерной алгебры , такие как SageMath , Maple , Mathematica и PARI/GP , имеют встроенную функцию для вычисления циклотомических многочленов. Φ n ( x ) {\displaystyle \Phi _{n}(x)}

Простые случаи для вычислений

Как отмечено выше, если n — простое число, то

Φ n ( x ) = 1 + x + x 2 + ⋯ + x n − 1 = ∑ k = 0 n − 1 x k . {\displaystyle \Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}\;.}

Если n — нечетное целое число, большее единицы, то

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

В частности, если n = 2 p — дважды нечетное простое число, то (как отмечено выше)

Φ n ( x ) = 1 − x + x 2 − ⋯ + x p − 1 = ∑ k = 0 p − 1 ( − x ) k . {\displaystyle \Phi _{n}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}\;.}

Если n = p m — степень простого числа (где p — простое число), то

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

В более общем случае, если n = p m r, где r взаимно просто с p , то

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

Эти формулы можно применять многократно, чтобы получить простое выражение для любого циклотомического многочлена через циклотомический многочлен с индексом, свободным от квадратов : Если q является произведением простых делителей n (его радикала ), то [5] Φ n ( x ) {\displaystyle \Phi _{n}(x)}

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

Это позволяет вывести формулы для n- го циклотомического многочлена, когда n имеет не более одного нечетного простого множителя: Если p — нечетное простое число, а h и k — положительные целые числа, то

Φ 2 h ( x ) = x 2 h − 1 + 1 , {\displaystyle \Phi _{2^{h}}(x)=x^{2^{h-1}}+1\;,}
Φ p k ( x ) = ∑ j = 0 p − 1 x j p k − 1 , {\displaystyle \Phi _{p^{k}}(x)=\sum _{j=0}^{p-1}x^{jp^{k-1}}\;,}
Φ 2 h p k ( x ) = ∑ j = 0 p − 1 ( − 1 ) j x j 2 h − 1 p k − 1 . {\displaystyle \Phi _{2^{h}p^{k}}(x)=\sum _{j=0}^{p-1}(-1)^{j}x^{j2^{h-1}p^{k-1}}\;.}

Для других значений n вычисление n-го циклотомического многочлена аналогично сводится к вычислению, где q — произведение различных нечетных простых делителей n . Чтобы иметь дело с этим случаем, для p — простого числа, не делящего n , [6] Φ q ( x ) , {\displaystyle \Phi _{q}(x),}

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

Целые числа, появляющиеся как коэффициенты

Проблема ограничения величины коэффициентов циклотомических полиномов была предметом ряда исследовательских работ. Несколько обзорных работ дают обзор. [7]

Если n имеет не более двух различных нечетных простых множителей, то Миготти показал, что все коэффициенты находятся в наборе {1, −1, 0}. [8] Φ n {\displaystyle \Phi _{n}}

Первый циклотомический многочлен для произведения трех различных нечетных простых множителей имеет коэффициент −2 (см. его выражение выше). Обратное неверно: имеет коэффициенты только в {1, −1, 0}. Φ 105 ( x ) ; {\displaystyle \Phi _{105}(x);} Φ 231 ( x ) = Φ 3 × 7 × 11 ( x ) {\displaystyle \Phi _{231}(x)=\Phi _{3\times 7\times 11}(x)}

Если n является произведением большего количества различных нечетных простых множителей, коэффициенты могут увеличиваться до очень больших значений. Например, имеет коэффициенты от −22 до 23, наименьшее n с 6 различными нечетными простыми числами имеет коэффициенты величиной до 532. Φ 15015 ( x ) = Φ 3 × 5 × 7 × 11 × 13 ( x ) {\displaystyle \Phi _{15015}(x)=\Phi _{3\times 5\times 7\times 11\times 13}(x)} Φ 255255 ( x ) = Φ 3 × 5 × 7 × 11 × 13 × 17 ( x ) {\displaystyle \Phi _{255255}(x)=\Phi _{3\times 5\times 7\times 11\times 13\times 17}(x)}

Пусть A ( n ) обозначает максимальное абсолютное значение коэффициентов Φ n . Известно, что для любого положительного k число n вплоть до x с A ( n ) > n k не меньше c ( k ) ⋅ x для положительного c ( k ), зависящего от k и достаточно большого x . В противоположном направлении, для любой функции ψ( n ), стремящейся к бесконечности с n , мы имеем A ( n ) ограниченное сверху n ψ( n ) для почти всех n . [9]

Комбинация теорем Бейтмана и Вона утверждает [7] : 10  что, с одной стороны, для каждого , мы имеем ε > 0 {\displaystyle \varepsilon >0}

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

для всех достаточно больших положительных целых чисел , а с другой стороны, мы имеем n {\displaystyle n}

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

для бесконечного числа положительных целых чисел . Это подразумевает, в частности, что одномерные многочлены (конкретно для бесконечного числа положительных целых чисел ) могут иметь множители (например ), коэффициенты которых суперполиномиально больше исходных коэффициентов. Это не слишком далеко от общей границы Ландау-Миньотта . n {\displaystyle n} x n − 1 {\displaystyle x^{n}-1} n {\displaystyle n} Φ n {\displaystyle \Phi _{n}}

Формула Гаусса

Пусть n нечетное, бесквадратное и больше 3. Тогда: [10] [11]

4 Φ n ( z ) = A n 2 ( z ) − ( − 1 ) n − 1 2 n z 2 B n 2 ( z ) {\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 не является составным и ≡ 3 (mod 4), в этом случае он является антипалиндромным.

Первые несколько случаев

4 Φ 5 ( z ) = 4 ( z 4 + z 3 + z 2 + z + 1 ) = ( 2 z 2 + z + 2 ) 2 − 5 z 2 4 Φ 7 ( z ) = 4 ( z 6 + z 5 + z 4 + z 3 + z 2 + z + 1 ) = ( 2 z 3 + z 2 − z − 2 ) 2 + 7 z 2 ( z + 1 ) 2 4 Φ 11 ( z ) = 4 ( z 10 + z 9 + z 8 + z 7 + z 6 + z 5 + z 4 + z 3 + z 2 + z + 1 ) = ( 2 z 5 + z 4 − 2 z 3 + 2 z 2 − z − 2 ) 2 + 11 z 2 ( z 3 + 1 ) 2 {\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]

Φ n ( z ) = U n 2 ( z ) − ( − 1 ) n − 1 2 n z V n 2 ( z ) {\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. Это также можно записать

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

Если n четное, бесквадратное и больше 2 (это делает n /2 нечетным),

Φ n 2 ( − z 2 ) = Φ 2 n ( z ) = C n 2 ( z ) − n z D n 2 ( z ) {\displaystyle \Phi _{\frac {n}{2}}\left(-z^{2}\right)=\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 ) оба являются палиндромами.

Вот первые несколько случаев:

Φ 3 ( − z ) = Φ 6 ( z ) = z 2 − z + 1 = ( z + 1 ) 2 − 3 z Φ 5 ( z ) = z 4 + z 3 + z 2 + z + 1 = ( z 2 + 3 z + 1 ) 2 − 5 z ( z + 1 ) 2 Φ 6 / 2 ( − z 2 ) = Φ 12 ( z ) = z 4 − z 2 + 1 = ( z 2 + 3 z + 1 ) 2 − 6 z ( z + 1 ) 2 {\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}}}

Гипотеза сестры Бейтер

Гипотеза сестры Бейтер касается максимального размера (по абсолютной величине) коэффициентов тернарных циклотомических полиномов , где — три простых числа. [12] A ( p q r ) {\displaystyle A(pqr)} Φ p q r ( x ) {\displaystyle \Phi _{pqr}(x)} 3 ≤ p ≤ q ≤ r {\displaystyle 3\leq p\leq q\leq r}

Циклотомические многочлены над конечным полем и надп-адические целые числа

Над конечным полем с простым числом элементов p для любого целого числа n , не кратного p , циклотомический многочлен разлагается на неприводимые многочлены степени d , где — функция Эйлера , а d — мультипликативный порядок p по модулю n . В частности, является неприводимым тогда и только тогда, когда p — примитивный корень по модулю n , то есть p не делит n , а его мультипликативный порядок по модулю n равен , степени . [13] Φ n {\displaystyle \Phi _{n}} φ ( n ) d {\displaystyle {\frac {\varphi (n)}{d}}} φ ( n ) {\displaystyle \varphi (n)} Φ n {\displaystyle \Phi _{n}} φ ( n ) {\displaystyle \varphi (n)} Φ n {\displaystyle \Phi _{n}}

Эти результаты верны также и для целых p -адических чисел , поскольку лемма Гензеля позволяет поднять факторизацию над полем с p элементами до факторизации над целыми p -адическими числами.

Полиномиальные значения

Если x принимает любое действительное значение, то для любого n ≥ 3 (это следует из того факта, что корни циклотомического многочлена все недействительны, при n ≥ 3 ). Φ n ( x ) > 0 {\displaystyle \Phi _{n}(x)>0}

Для изучения значений, которые может принимать циклотомический многочлен, когда x имеет целое значение, достаточно рассмотреть только случай n ≥ 3 , поскольку случаи n = 1 и n = 2 тривиальны (имеется и ). Φ 1 ( x ) = x − 1 {\displaystyle \Phi _{1}(x)=x-1} Φ 2 ( x ) = x + 1 {\displaystyle \Phi _{2}(x)=x+1}

Для n ≥ 2 имеем

Φ n ( 0 ) = 1 , {\displaystyle \Phi _{n}(0)=1,}
Φ n ( 1 ) = 1 {\displaystyle \Phi _{n}(1)=1} если n не является степенью простого числа ,
Φ n ( 1 ) = p {\displaystyle \Phi _{n}(1)=p} если — степень простого числа с k ≥ 1 . n = p k {\displaystyle n=p^{k}}

Значения, которые может принимать циклотомический многочлен для других целых значений x, тесно связаны с мультипликативным порядком по модулю простого числа. Φ n ( x ) {\displaystyle \Phi _{n}(x)}

Точнее, если задано простое число p и целое число b , взаимно простое с p , то мультипликативный порядок числа b по модулю p — это наименьшее положительное целое число n, такое что p является делителем Для b > 1 мультипликативный порядок числа b по модулю p также является наименьшим периодом представления числа 1/ p в системе счисления с основанием b (см. Уникальное простое число ; это объясняет выбор обозначения). b n − 1. {\displaystyle b^{n}-1.}

Из определения мультипликативного порядка следует, что если n — мультипликативный порядок b по модулю p , то p — делитель Обратное неверно, но имеет место следующее. Φ n ( b ) . {\displaystyle \Phi _{n}(b).}

Если n > 0 — положительное целое число, а b > 1 — целое число, то (доказательство см. ниже)

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

где

  • k — неотрицательное целое число, всегда равное 0, когда b четное. (На самом деле, если n не равно ни 1, ни 2, то k равно либо 0, либо 1. Кроме того, если n не является степенью 2 , то k всегда равно 0)
  • g равен 1 или наибольшему нечетному простому множителю числа n .
  • h нечетно, взаимно просто с n , и его простые множители — это в точности нечетные простые числа p, такие что n — это мультипликативный порядок b по модулю p .

Это означает, что если p — нечетный простой делитель, то либо n — делитель p − 1 , либо p — делитель n . В последнем случае не делит Φ n ( b ) , {\displaystyle \Phi _{n}(b),} p 2 {\displaystyle p^{2}} Φ n ( b ) . {\displaystyle \Phi _{n}(b).}

Теорема Зигмонди подразумевает, что единственными случаями, когда b > 1 и h = 1, являются

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

Из вышеприведенной факторизации следует, что нечетные простые множители

Φ n ( b ) gcd ( n , Φ n ( b ) ) {\displaystyle {\frac {\Phi _{n}(b)}{\gcd(n,\Phi _{n}(b))}}}

являются в точности нечетными простыми числами p такими, что n является мультипликативным порядком b по модулю p . Эта дробь может быть четной только тогда, когда b нечетно. В этом случае мультипликативный порядок b по модулю 2 всегда равен 1 .

Существует много пар ( n , b ) с b > 1 , таких что является простым числом. Фактически, гипотеза Буняковского подразумевает, что для каждого n существует бесконечно много b > 1, таких что является простым числом. См. OEIS : A085398 для списка наименьших b > 1, таких что является простым числом (наименьшее b > 1, такое что является простым числом, составляет около , где — постоянная Эйлера–Маскерони , а — функция Эйлера ). См. также OEIS : A206864 для списка наименьших простых чисел вида с n > 2 и b > 1 , и, в более общем смысле, OEIS : A206942 для наименьших положительных целых чисел этого вида. Φ n ( b ) {\displaystyle \Phi _{n}(b)} Φ n ( b ) {\displaystyle \Phi _{n}(b)} Φ n ( b ) {\displaystyle \Phi _{n}(b)} Φ n ( b ) {\displaystyle \Phi _{n}(b)} γ ⋅ φ ( n ) {\displaystyle \gamma \cdot \varphi (n)} γ {\displaystyle \gamma } φ {\displaystyle \varphi } Φ n ( b ) {\displaystyle \Phi _{n}(b)}

Доказательства
  • Значения Если — степень простого числа, то Φ n ( 1 ) . {\displaystyle \Phi _{n}(1).} n = p k + 1 {\displaystyle n=p^{k+1}}
Φ n ( x ) = 1 + x p k + x 2 p k + ⋯ + x ( p − 1 ) p k and Φ n ( 1 ) = p . {\displaystyle \Phi _{n}(x)=1+x^{p^{k}}+x^{2p^{k}}+\cdots +x^{(p-1)p^{k}}\qquad {\text{and}}\qquad \Phi _{n}(1)=p.}
Если n не является степенью простого числа, пусть у нас есть и P является произведением для k , делящего n и отличного от 1. Если p является простым делителем кратности m в n , то делим P ( x ) , и их значения в 1 являются m множителями, равными p числа Поскольку m является кратностью p в n , p не может делить значение в 1 других множителей Таким образом, нет простого делителя P ( x ) = 1 + x + ⋯ + x n − 1 , {\displaystyle P(x)=1+x+\cdots +x^{n-1},} P ( 1 ) = n , {\displaystyle P(1)=n,} Φ k ( x ) {\displaystyle \Phi _{k}(x)} Φ p ( x ) , Φ p 2 ( x ) , ⋯ , Φ p m ( x ) {\displaystyle \Phi _{p}(x),\Phi _{p^{2}}(x),\cdots ,\Phi _{p^{m}}(x)} n = P ( 1 ) . {\displaystyle n=P(1).} P ( x ) . {\displaystyle P(x).} Φ n ( 1 ) . {\displaystyle \Phi _{n}(1).}
  • Если n является мультипликативным порядком b по модулю p , то по определению, если тогда p будет делить другой множитель и , таким образом, будет делить, показывая, что в таком случае n не будет мультипликативным порядком b по модулю p . p ∣ Φ n ( b ) . {\displaystyle p\mid \Phi _{n}(b).} p ∣ b n − 1. {\displaystyle p\mid b^{n}-1.} p ∤ Φ n ( b ) , {\displaystyle p\nmid \Phi _{n}(b),} Φ k ( b ) {\displaystyle \Phi _{k}(b)} b n − 1 , {\displaystyle b^{n}-1,} b k − 1 , {\displaystyle b^{k}-1,}
  • Другие простые делители являются делителями n . Пусть p будет простым делителем таким, что n не будет мультипликативным порядком b по модулю p . Если k является мультипликативным порядком b по модулю p , то p делит и и Результирующий элемент и может быть записан как , где P и Q являются многочленами. Таким образом, p делит этот результирующий элемент. Так как k делит n , а результирующий элемент двух многочленов делит дискриминант любого общего кратного этих многочленов, p делит также дискриминант Таким образом , p делит n . Φ n ( b ) {\displaystyle \Phi _{n}(b)} Φ n ( b ) {\displaystyle \Phi _{n}(b)} Φ n ( b ) {\displaystyle \Phi _{n}(b)} Φ k ( b ) . {\displaystyle \Phi _{k}(b).} Φ n ( x ) {\displaystyle \Phi _{n}(x)} Φ k ( x ) {\displaystyle \Phi _{k}(x)} P Φ k + Q Φ n , {\displaystyle P\Phi _{k}+Q\Phi _{n},} n n {\displaystyle n^{n}} x n − 1. {\displaystyle x^{n}-1.}
  • g и h взаимно просты . Другими словами, если p — простой общий делитель n ,то n не является мультипликативным порядком b по модулю p . По малой теореме Ферма мультипликативный порядок b является делителем p − 1 и, следовательно, меньше n . Φ n ( b ) , {\displaystyle \Phi _{n}(b),}
  • g является свободным от квадратов . Другими словами, если p является простым общим делителем n ине делитПустьn = pm . Достаточно доказать, чтоне делит S ( b ) для некоторого многочлена S ( x ) , который кратенВозьмем Φ n ( b ) , {\displaystyle \Phi _{n}(b),} p 2 {\displaystyle p^{2}} Φ n ( b ) . {\displaystyle \Phi _{n}(b).} p 2 {\displaystyle p^{2}} Φ n ( x ) . {\displaystyle \Phi _{n}(x).}
S ( x ) = x n − 1 x m − 1 = 1 + x m + x 2 m + ⋯ + x ( p − 1 ) m . {\displaystyle S(x)={\frac {x^{n}-1}{x^{m}-1}}=1+x^{m}+x^{2m}+\cdots +x^{(p-1)m}.}
Мультипликативный порядок b по модулю p делит gcd( n , p − 1) , который является делителем m = n / p . Таким образом, c = b m − 1 является кратным p . Теперь,
S ( b ) = ( 1 + c ) p − 1 c = p + ( p 2 ) c + ⋯ + ( p p ) c p − 1 . {\displaystyle S(b)={\frac {(1+c)^{p}-1}{c}}=p+{\binom {p}{2}}c+\cdots +{\binom {p}{p}}c^{p-1}.}
Так как p — простое число и больше 2, то все члены, кроме первого, являются кратными. Это доказывает, что p 2 . {\displaystyle p^{2}.} p 2 ∤ Φ n ( b ) . {\displaystyle p^{2}\nmid \Phi _{n}(b).}


Приложения

Используя , можно дать элементарное доказательство бесконечности простых чисел, сравнимых с 1 по модулю n , [14] что является частным случаем теоремы Дирихле об арифметических прогрессиях . Φ n {\displaystyle \Phi _{n}}

Доказательство

Предположим, что есть конечный список простых чисел, сравнимых по модулю Пусть и рассмотрим . Пусть будет простым множителем (чтобы увидеть это, разложим его на линейные множители и заметим, что 1 — ближайший корень из единицы к ). Поскольку мы знаем, что — новое простое число, которого нет в списке. Покажем, что p 1 , p 2 , … , p k {\displaystyle p_{1},p_{2},\ldots ,p_{k}} 1 {\displaystyle 1} n . {\displaystyle n.} N = n p 1 p 2 ⋯ p k {\displaystyle N=np_{1}p_{2}\cdots p_{k}} Φ n ( N ) {\displaystyle \Phi _{n}(N)} q {\displaystyle q} Φ n ( N ) {\displaystyle \Phi _{n}(N)} Φ n ( N ) ≠ ± 1 {\displaystyle \Phi _{n}(N)\neq \pm 1} N {\displaystyle N} Φ n ( x ) ≡ ± 1 ( mod x ) , {\displaystyle \Phi _{n}(x)\equiv \pm 1{\pmod {x}},} q {\displaystyle q} q ≡ 1 ( mod n ) . {\displaystyle q\equiv 1{\pmod {n}}.}

Пусть будет порядком по модулю Поскольку имеем . Таким образом . Покажем, что . m {\displaystyle m} N {\displaystyle N} q . {\displaystyle q.} Φ n ( N ) ∣ N n − 1 {\displaystyle \Phi _{n}(N)\mid N^{n}-1} N n − 1 ≡ 0 ( mod q ) {\displaystyle N^{n}-1\equiv 0{\pmod {q}}} m ∣ n {\displaystyle m\mid n} m = n {\displaystyle m=n}

Предположим от противного, что . Так как m < n {\displaystyle m<n}

∏ d ∣ m Φ d ( N ) = N m − 1 ≡ 0 ( mod q ) {\displaystyle \prod _{d\mid m}\Phi _{d}(N)=N^{m}-1\equiv 0{\pmod {q}}}

у нас есть

Φ d ( N ) ≡ 0 ( mod q ) , {\displaystyle \Phi _{d}(N)\equiv 0{\pmod {q}},}

для некоторых . Тогда это двойной корень d < n {\displaystyle d<n} N {\displaystyle N}

∏ d ∣ n Φ d ( x ) ≡ x n − 1 ( mod q ) . {\displaystyle \prod _{d\mid n}\Phi _{d}(x)\equiv x^{n}-1{\pmod {q}}.}

Таким образом, должен быть корень производной, поэтому N {\displaystyle N}

d ( x n − 1 ) d x | N ≡ n N n − 1 ≡ 0 ( mod q ) . {\displaystyle \left.{\frac {d(x^{n}-1)}{dx}}\right|_{N}\equiv nN^{n-1}\equiv 0{\pmod {q}}.}

Но и поэтому Это противоречие так . Порядок которого есть , должен делиться . Таким образом q ∤ N {\displaystyle q\nmid N} q ∤ n . {\displaystyle q\nmid n.} m = n {\displaystyle m=n} N ( mod q ) , {\displaystyle N{\pmod {q}},} n {\displaystyle n} q − 1 {\displaystyle q-1} q ≡ 1 ( mod n ) . {\displaystyle q\equiv 1{\pmod {n}}.}

Смотрите также

Ссылки

  1. ^ Роман, Стивен (2008), Продвинутая линейная алгебра , Graduate Texts in Mathematics (Третье изд.), Springer, стр. 465 §18, ISBN 978-0-387-72828-5
  2. ^ Слоан, Н. Дж. А. (ред.), «Последовательность A013595», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
  3. ^ Брукфилд, Гэри (2016), «Коэффициенты циклотомических полиномов», Mathematics Magazine , 89 (3): 179–188, doi :10.4169/math.mag.89.3.179, JSTOR  10.4169/math.mag.89.3.179, MR  3519075
  4. ^ Ланг, Серж (2002), Алгебра , Graduate Texts in Mathematics , т. 211 (пересмотренное третье издание), Нью-Йорк: Springer-Verlag, ISBN 978-0-387-95385-4, г-н  1878556
  5. ^ Кокс, Дэвид А. (2012), «Упражнение 12», Теория Галуа (2-е изд.), John Wiley & Sons, стр. 237, номер домена : 10.1002/9781118218457, ISBN 978-1-118-07205-9.
  6. ^ Вайсштейн, Эрик В. , «Циклотомический многочлен», MathWorld
  7. ^ ab Санна, Карло (2021), «Обзор коэффициентов циклотомических многочленов», arXiv : 2111.04034 [math.NT]
  8. ^ Айзекс, Мартин (2009), Алгебра: курс для выпускников , AMS Bookstore, стр. 310, ISBN 978-0-8218-4799-2
  9. ^ Майер, Хельмут (2008), "Анатомия целых чисел и циклотомических многочленов", в De Koninck, Jean-Marie; Granville, Andrew ; Luca, Florian (ред.), Анатомия целых чисел. Основано на семинаре CRM, Монреаль, Канада, 13-17 марта 2006 г. , CRM Proceedings and Lecture Notes, т. 46, Providence, RI: American Mathematical Society , стр. 89–95, ISBN 978-0-8218-4406-9, Збл  1186.11010
  10. ^ Гаусс, Д.А., Статьи 356-357
  11. ^ ab Riesel, Hans (1994), Простые числа и компьютерные методы факторизации (2-е изд.), Бостон: Birkhäuser, стр. 309–316, 436, 443, ISBN 0-8176-3743-5
  12. ↑ Бейтер, Мэрион (апрель 1968 г.), «Величина коэффициентов циклотомического многочлена », The American Mathematical Monthly , 75 (4): 370–372, doi :10.2307/2313416, JSTOR  2313416 F p q r ( x ) {\displaystyle F_{pqr}(x)}
  13. ^ Лидл, Рудольф; Нидеррайтер, Харальд (2008), Конечные поля (2-е изд.), Cambridge University Press, стр. 65.
  14. ^ С. Ширали. Теория чисел . Ориент Блэксван, 2004. с. 67. ISBN 81-7371-454-1 . 

Дальнейшее чтение

Книга Гаусса Disquisitiones Arithmeticae [ Арифметические исследования ] была переведена с латыни на французский, немецкий и английский языки. Немецкое издание включает все его работы по теории чисел: все доказательства квадратичной взаимности, определение знака суммы Гаусса, исследования биквадратичной взаимности и неопубликованные заметки.

  • Гаусс, Карл Фридрих (1801), Disquisitiones Arithmeticae (на латыни), Лейпциг: Gerh. Флейшер
  • Гаусс, Карл Фридрих (1807) [1801], Recherches Arithmétiques (на французском языке), перевод Пуле-Делиля, A.-C.-M., Париж: Courcier
  • Гаусс, Карл Фридрих (1889) [1801], Untersuchungen über höhere Arithmetik Карла Фридриха Гаусса (на немецком языке), перевод Мазера, Х., Берлин: Springer; Переиздано в 1965 г., Нью-Йорк: Челси, ISBN 0-8284-0191-8 
  • Гаусс, Карл Фридрих (1966) [1801], Disquisitiones Arithmeticae , перевод Кларка, Артура А., Нью-Хейвен: Йель, doi : 10.12987/9780300194258, ISBN 978-0-300-09473-2; Исправленное издание 1986, Нью-Йорк: Springer, doi :10.1007/978-1-4939-7560-0, ISBN 978-0-387-96254-2 
  • Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Берлин: Springer, doi : 10.1007/978-3-662-12893-0, ISBN 978-3-642-08628-1
  • Вайсштейн, Эрик В. , «Циклотомический многочлен», MathWorld
  • «Циклотомические многочлены», Энциклопедия математики , EMS Press , 2001 [1994]
  • Последовательность OEIS A013595 (Треугольник коэффициентов циклотомического полинома Phi_n(x) (экспоненты в порядке возрастания))
  • Последовательность OEIS A013594 (Наименьший порядок циклотомического полинома, содержащего n или −n в качестве коэффициента)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Cyclotomic_polynomial&oldid=1255495071"