Циклотомический полином

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

${\ displaystyle \ Phi _ {n} (x) = \ prod _ {\ stackrel {1 \ leq k \ leq n} {\ gcd (k, n) = 1}} \ left (xe ^ {2i \ pi { \ frac {k} {n}}} \ right).}$

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

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

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

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

Примеры [ править ]

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

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

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

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

Для n до 30 круговыми полиномами являются: ^[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\\\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}\\&\qquad \quad +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}\\&\qquad \quad +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.\end{aligned}}}$

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

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

Свойства [ править ]

Основные инструменты [ править ]

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

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

Тот факт, что полином степени в кольце является неприводимым, является нетривиальным результатом Гаусса . ^[2] В зависимости от выбранного определения, нетривиальным результатом является либо значение степени, либо неприводимость. Случай простого n легче доказать, чем общий случай, благодаря критерию Эйзенштейна .${\displaystyle \Phi _{n}}$${\displaystyle \varphi (n)}$ ${\displaystyle \mathbb {Z} [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}}}$

что означает , что каждый п -й корень из единицы примитивный д -ый корень из единицы для уникального д , делящего п .

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

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

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

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

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

(Вспомните это .)${\displaystyle \Phi _{1}(x)=x-1}$

Эта формула позволяет вычислить на компьютере для любого n , если доступны целочисленное разложение и деление многочленов . Многие системы компьютерной алгебры имеют встроенную функцию для вычисления круговых полиномов. Например, эта функция вызывается , набрав в SageMath , в Maple , в Mathematica , и в PARI / GP .${\displaystyle \Phi _{n}(x)}$cyclotomic_polynomial(n,x)numtheory[cyclotomic](n,x);Cyclotomic[n,x]polcyclo(n,x)

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

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

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

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

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

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

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

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

${\displaystyle \Phi _{n}(x)=\Phi _{p}(x^{p^{m-1}})=\sum _{i=0}^{p-1}x^{ip^{m-1}}.}$

В более общем смысле, если n = p ^m r с r взаимно простым с p , то

${\displaystyle \Phi _{n}(x)=\Phi _{pr}(x^{p^{m-1}}).}$

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

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

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

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

${\displaystyle \Phi _{p^{k}}(x)=\sum _{i=0}^{p-1}x^{ip^{k-1}}}$

${\displaystyle \Phi _{2^{h}p^{k}}(x)=\sum _{i=0}^{p-1}(-1)^{i}x^{i2^{h-1}p^{k-1}}}$

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

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

Целые числа в виде коэффициентов [ править ]

Проблема ограничения величины коэффициентов круговых многочленов была предметом ряда исследовательских работ.

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

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

Если n является произведением нескольких различных нечетных простых множителей, коэффициенты могут возрасти до очень высоких значений. Например, имеет коэффициенты от -22 до 23, наименьшее n с 6 разными нечетными простыми числами, имеет коэффициенты величиной до 532.${\displaystyle \Phi _{15015}(x)=\Phi _{3\times 5\times 7\times 11\times 13}(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 . ^[6]

Формула Гаусса [ править ]

Пусть n нечетное, бесквадратное и больше 3. Тогда: ^{[7] [8]}

${\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), и в этом случае он антипалиндромный.

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

${\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. Тогда ^[9]

${\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}}\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 ) оба палиндромные.

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

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

Циклотомические многочлены над конечным полем и над целыми p -адическими числами [ править ]

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

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

Значения полиномов [ править ]

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

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

При n ≥ 2 имеем

${\displaystyle \Phi _{n}(0)=1,}$

${\displaystyle \Phi _{n}(1)=1}$если n не является простой степенью ,

${\displaystyle \Phi _{n}(1)=p}$если - степень простого числа с k ≥ 1 .${\displaystyle n=p^{k}}$

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

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

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

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

${\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 . В последнем случае не делит${\displaystyle \Phi _{n}(b),}$${\displaystyle p^{2}}$${\displaystyle \Phi _{n}(b).}$

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

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

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

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

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

Есть много пар ( п , б ) с Ь > 1 таким образом, что является простым. На самом деле, Буняковская гипотеза предполагает , что для любого п , существует бесконечное число б > 1 такое , что первично. См. OEIS :  A085398 для списка наименьших b > 1, таких, что является простым (наименьшее b > 1, такое, что является простым, имеет значение около , где - константа Эйлера – Маскерони , а - функция Эйлера.${\displaystyle \Phi _{n}(b)}$${\displaystyle \Phi _{n}(b)}$${\displaystyle \Phi _{n}(b)}$${\displaystyle \Phi _{n}(b)}$${\displaystyle \lambda \cdot \varphi (n)}$${\displaystyle \lambda }$${\displaystyle \varphi }$). См. Также OEIS :  A206864 для списка наименьших простых чисел формы с n > 2 и b > 1 , и, в более общем плане, OEIS :  A206942 для наименьших положительных целых чисел этой формы.${\displaystyle \Phi _{n}(b)}$

Приложения [ править ]

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

См. Также [ править ]

• Циклотомическое поле
• Aurifeuillean факторизация
• Корень единства

Заметки [ править ]

Ссылки [ править ]

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

• Гаусс, Карл Фридрих (1986) [1801]. Disquisitiones Arithmeticae . Переведено на английский Кларком, Артуром А. (2-е изд. Корр.). Нью-Йорк: Спрингер . ISBN 0387962549.
• Гаусс, Карл Фридрих (1965) [1801]. Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae и другие статьи по теории чисел) . Перевод на немецкий язык Мазером Х. (2-е изд.). Нью-Йорк: Челси. ISBN 0-8284-0191-8.
• Леммермейер, Франц (2000). Законы взаимности: от Эйлера до Эйзенштейна . Берлин: Springer . DOI : 10.1007 / 978-3-662-12893-0 . ISBN 978-3-642-08628-1.
• Майер, Гельмут (2008), «Анатомия целых чисел и циклотомических многочленов», в Де Конинк, Жан-Мари; Гранвиль, Эндрю ; Лука, Флориан (ред.), Анатомия целых чисел. На основе семинара CRM, Монреаль, Канада, 13-17 марта 2006 г. , CRM Proceedings and Lecture Notes, 46 , Providence, RI: American Mathematical Society , pp. 89–95, ISBN 978-0-8218-4406-9, Zbl  1186,11010
• Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Бостон: Биркхойзер. ISBN 0-8176-3743-5.

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. "Циклотомический многочлен" . MathWorld .
• "Циклотомические многочлены" , Энциклопедия математики , EMS Press , 2001 [1994]
• Последовательность OEIS A013595 (Треугольник коэффициентов кругового полинома Phi_n (x) (показатели в порядке возрастания))
• Последовательность OEIS A013594 (наименьший порядок кругового многочлена, содержащего n или −n в качестве коэффициента)