Неприводимый многочлен

Многочлен без нетривиальной факторизации

В математике неприводимый многочлен — это, грубо говоря, многочлен , который не может быть разложен на множители в произведение двух непостоянных многочленов . Свойство неприводимости зависит от природы коэффициентов , которые принимаются для возможных множителей, то есть кольца , к которому предположительно принадлежат коэффициенты многочлена и его возможные множители. Например, многочлен x ² − 2 является многочленом с целыми коэффициентами, но, поскольку каждое целое число также является действительным числом , он также является многочленом с действительными коэффициентами. Он неприводим, если его рассматривать как многочлен с целыми коэффициентами, но он факторизуется так, как если бы его рассматривали как многочлен с действительными коэффициентами. Говорят, что многочлен x ² − 2 неприводим над целыми числами, но не над действительными числами. ${\displaystyle \left(x-{\sqrt {2}}\right)\left(x+{\sqrt {2}}\right)}$

Неприводимость полиномов можно рассматривать для полиномов с коэффициентами в области целостности , и существует два общих определения. Чаще всего полином над областью целостности R называется неприводимым , если он не является произведением двух полиномов, коэффициенты которых находятся в R , и которые не являются единицей в R. Эквивалентно, для этого определения неприводимый полином является неприводимым элементом в кольце полиномов над R. Если R является полем, два определения неприводимости эквивалентны. Для второго определения полином является неприводимым, если его нельзя разложить на многочлены с коэффициентами в той же области, оба из которых имеют положительную степень. Эквивалентно, полином является неприводимым, если он неприводим над полем дробей области целостности. Например, полином является неприводимым для второго определения, но не для первого. С другой стороны, неприводимо в для двух определений, в то время как приводимо в ${\displaystyle 2(x^{2}-2)\in \mathbb {Z} [x]}$ ${\displaystyle x^{2}-2}$ ${\displaystyle \mathbb {Z} [x]}$ ${\displaystyle \mathbb {R} [x].}$

Многочлен, неприводимый над любым полем, содержащим коэффициенты, является абсолютно неприводимым . Согласно основной теореме алгебры , одномерный многочлен абсолютно неприводим тогда и только тогда, когда его степень равна единице. С другой стороны, при наличии нескольких неизвестных существуют абсолютно неприводимые многочлены любой степени, например, для любого положительного целого числа n . ${\displaystyle x^{2}+y^{n}-1,}$

Полином, который не является неприводимым, иногда называют приводимым полиномом . ^{[1] [2]}

Неприводимые многочлены естественным образом появляются при изучении факторизации многочленов и расширений алгебраических полей .

Полезно сравнивать неприводимые многочлены с простыми числами : простые числа (вместе с соответствующими отрицательными числами равной величины) являются неприводимыми целыми числами . Они демонстрируют многие общие свойства концепции «неприводимости», которые в равной степени применимы к неприводимым многочленам, такие как по существу уникальная факторизация на простые или неприводимые множители. Когда кольцо коэффициентов является полем или другой уникальной областью факторизации , неприводимый многочлен также называется простым многочленом , потому что он порождает простой идеал .

Определение

Если F — поле, то непостоянный многочлен неприводим над F, если его коэффициенты принадлежат F и его нельзя разложить на множители в произведение двух непостоянных многочленов с коэффициентами в F.

Полином с целыми коэффициентами или, в более общем смысле, с коэффициентами в уникальной области факторизации R иногда называют неприводимым (или неприводимым над R ), если он является неприводимым элементом кольца полиномов , то есть он необратим , не равен нулю и не может быть разложен на множители в произведение двух необратимых полиномов с коэффициентами в R. Это определение обобщает определение, данное для случая коэффициентов в поле, поскольку над полем непостоянные полиномы — это в точности полиномы, которые необратимы и не равны нулю.

Часто используется другое определение, гласящее, что многочлен неприводим над R, если он неприводим над полем дробей R (полем рациональных чисел , если R — целые числа). Это второе определение не используется в этой статье. Эквивалентность двух определений зависит от R.

Простые примеры

Следующие шесть многочленов демонстрируют некоторые элементарные свойства приводимых и неприводимых многочленов:

${\displaystyle {\begin{aligned}p_{1}(x)&=x^{2}+4x+4\,={(x+2)^{2}}\\p_{2}(x)&=x^{2}-4\,={(x-2)(x+2)}\\p_{3}(x)&=9x^{2}-3\,=3\left(3x^{2}-1\right)\,=3\left(x{\sqrt {3}}-1\right)\left(x{\sqrt {3}}+1\right)\\p_{4}(x)&=x^{2}-{\frac {4}{9}}\,=\left(x-{\frac {2}{3}}\right)\left(x+{\frac {2}{3}}\right)\\p_{5}(x)&=x^{2}-2\,=\left(x-{\sqrt {2}}\right)\left(x+{\sqrt {2}}\right)\\p_{6}(x)&=x^{2}+1\,={(x-i)(x+i)}\end{aligned}}}$

Над целыми числами первые три многочлена приводимы (третий приводим, так как множитель 3 необратим в целых числах); последние два — неприводимы. (Четвертый, конечно, не является многочленом над целыми числами.)

Над рациональными числами первые два и четвертый многочлены приводимы, но остальные три многочлена неприводимы (как многочлен над рациональными числами, 3 является единицей и , следовательно, не считается множителем).

Над действительными числами первые пять многочленов приводимы, но неприводимы. ${\displaystyle p_{6}(x)}$

Над комплексными числами все шесть многочленов приводимы.

Над комплексными числами

Над комплексным полем и, в более общем случае, над алгебраически замкнутым полем одномерный многочлен неприводим тогда и только тогда, когда его степень равна единице. Этот факт известен как основная теорема алгебры в случае комплексных чисел и, в общем случае, как условие алгебраической замкнутости.

Отсюда следует, что каждый непостоянный одномерный многочлен можно разложить на множители

${\displaystyle a\left(x-z_{1}\right)\cdots \left(x-z_{n}\right)}$

где — степень, — старший коэффициент, а — нули многочлена (не обязательно различные и не обязательно имеющие явные алгебраические выражения ). ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle z_{1},\dots ,z_{n}}$

Существуют неприводимые многомерные многочлены любой степени над комплексными числами. Например, многочлен

${\displaystyle x^{n}+y^{n}-1,}$

которая определяет кривую Ферма , неприводима для любого положительного n .

По сравнению с реалами

Над полем вещественных чисел степень неприводимого одномерного многочлена равна либо единице, либо двум. Точнее, неприводимые многочлены — это многочлены первой степени и квадратичные многочлены , имеющие отрицательный дискриминант. Отсюда следует, что любой непостоянный одномерный многочлен может быть разложен на множители как произведение многочленов степени не выше двух. Например, множители по вещественным числам и не могут быть разложены дальше, так как оба множителя имеют отрицательный дискриминант: ${\displaystyle ax^{2}+bx+c}$ ${\displaystyle b^{2}-4ac.}$ ${\displaystyle x^{4}+1}$ ${\displaystyle \left(x^{2}+{\sqrt {2}}x+1\right)\left(x^{2}-{\sqrt {2}}x+1\right),}$ ${\displaystyle \left(\pm {\sqrt {2}}\right)^{2}-4=-2<0.}$

Уникальное свойство факторизации

Каждый многочлен над полем F может быть разложен на множители в произведение ненулевой константы и конечного числа неприводимых (над F ) многочленов. Это разложение единственно с точностью до порядка множителей и умножения множителей на ненулевые константы, произведение которых равно 1.

Над уникальной областью факторизации та же теорема верна, но более точно формулируется с использованием понятия примитивного многочлена. Примитивный многочлен — это многочлен над уникальной областью факторизации, такой, что 1 является наибольшим общим делителем его коэффициентов.

Пусть F — уникальная факторизационная область. Неконстантный неприводимый многочлен над F является примитивным. Примитивный многочлен над F является неприводимым над F тогда и только тогда, когда он неприводим над полем дробей F . Каждый многочлен над F может быть разложен в произведение ненулевой константы и конечного числа неконстантных неприводимых примитивных многочленов. Ненулевая константа сама может быть разложена в произведение единицы F и конечного числа неприводимых элементов F . Оба факторизации являются уникальными с точностью до порядка множителей и умножения множителей на единицу F .

Именно эта теорема мотивирует тот факт, что определение неприводимого многочлена над областью уникальной факторизации часто предполагает, что многочлен не является константой.

Все алгоритмы , которые в настоящее время реализованы для разложения многочленов по целым и рациональным числам, используют этот результат (см. Факторизация многочленов ).

Над целыми числами и конечными полями

Неприводимость многочлена над целыми числами связана с неприводимостью над полем элементов (для простого числа ). В частности, если одномерный многочлен f над неприводим над для некоторого простого числа , которое не делит старший коэффициент f (коэффициент при наибольшей степени переменной), то f неприводим над (то есть не является произведением двух непостоянных многочленов с целыми коэффициентами). Критерий Эйзенштейна является вариантом этого свойства, где также задействована неприводимость над. ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {F} _{p}}$ ${\displaystyle p}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle p^{2}}$

Обратное, однако, неверно: существуют многочлены произвольно большой степени, которые неприводимы над целыми числами и приводимы над любым конечным полем. ^[3] Простой пример такого многочлена: ${\displaystyle x^{4}+1.}$

Связь между неприводимостью над целыми числами и неприводимостью по модулю p глубже предыдущего результата: на сегодняшний день все реализованные алгоритмы факторизации и неприводимости над целыми числами и над рациональными числами используют факторизацию над конечными полями в качестве подпрограммы .

Число неприводимых мономических многочленов степени n над полем для степени простого числа q определяется функцией подсчета ожерелий Моро : ^{[4] [5]} ${\displaystyle \mathbb {F} _{q}}$

${\displaystyle M(q,n)={\frac {1}{n}}\sum _{d\mid n}\mu (d)q^{\frac {n}{d}},}$

где μ — функция Мёбиуса . При q = 2 такие полиномы обычно используются для генерации псевдослучайных двоичных последовательностей .

В некотором смысле, почти все многочлены с коэффициентами ноль или единица неприводимы над целыми числами. Точнее, если предположить версию гипотезы Римана для дзета-функций Дедекинда , вероятность неприводимости над целыми числами для многочлена со случайными коэффициентами в {0, 1} стремится к единице, когда степень увеличивается. ^{[6] [7]}

Алгоритмы

Уникальное свойство факторизации многочленов не означает, что факторизация данного многочлена всегда может быть вычислена. Даже неприводимость многочлена не всегда может быть доказана вычислением: существуют поля, над которыми не может существовать алгоритма для определения неприводимости произвольных многочленов. ^[8]

Алгоритмы факторизации многочленов и решения вопроса о неприводимости известны и реализованы в системах компьютерной алгебры для многочленов над целыми числами, рациональными числами, конечными полями и конечно порожденными расширениями полей этих полей. Все эти алгоритмы используют алгоритмы факторизации многочленов над конечными полями .

Расширение поля

Понятия неприводимого многочлена и расширения алгебраического поля тесно связаны следующим образом.

Пусть x — элемент расширения L поля K. Этот элемент называется алгебраическим , если он является корнем ненулевого многочлена с коэффициентами в K. Среди многочленов, корнем которых является x , есть ровно один, который является моническим и имеет минимальную степень, называемый минимальным многочленом x . Минимальный многочлен алгебраического элемента x из L неприводим и является единственным моническим неприводимым многочленом, корнем которого является x . Минимальный многочлен x делит любой многочлен, имеющий x в качестве корня (это теорема Абеля о неприводимости ).

Обратно, если — одномерный многочлен над полем K , пусть — фактор-кольцо кольца многочленов по идеалу, порожденному P. Тогда L является полем тогда и только тогда, когда P неприводимо над K. В этом случае, если x — образ X в L , минимальный многочлен x — это фактор-кольцо P по его старшему коэффициенту . ${\displaystyle P(X)\in K[X]}$ ${\displaystyle L=K[X]/P(X)}$ ${\displaystyle K[X]}$

Примером вышесказанного является стандартное определение комплексных чисел как ${\displaystyle \mathbb {C} =\mathbb {R} [X]\;/\left(X^{2}+1\right).}$

Если многочлен P имеет неприводимый множитель Q над K , имеющий степень больше единицы, можно применить к Q предыдущую конструкцию алгебраического расширения, чтобы получить расширение, в котором P имеет по крайней мере на один корень больше, чем в K . Итерируя эту конструкцию, в конечном итоге получаем поле, над которым P разлагается на линейные множители. Это поле, уникальное с точностью до изоморфизма полей , называется полем расщепления P .

Над целостной областью

Если R — область целостности , элемент f из R , который не является ни нулем, ни единицей, называется неприводимым, если нет неединиц g и h с f = gh . Можно показать, что каждый простой элемент неприводим; ^[9] обратное неверно в общем случае, но верно в областях однозначной факторизации . Кольцо многочленов F [ x ] над полем F (или любой областью однозначной факторизации) снова является областью однозначной факторизации. Индуктивно это означает, что кольцо многочленов от n неопределенностей (над кольцом R ) является областью однозначной факторизации, если то же самое верно для R .

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

• Лемма Гаусса (многочлен)
• Теорема о рациональном корне , метод определения, имеет ли многочлен линейный множитель с рациональными коэффициентами.
• Критерий Эйзенштейна
• Критерий неприводимости Перрона
• Теорема Гильберта о неприводимости
• Критерий неприводимости Кона
• Неприводимая компонента топологического пространства
• Факторизация многочленов над конечными полями
• Функция четвертой степени § Приводимые квартики
• Кубическая функция § Факторизация
• Casus irreducibilis , неприводимая кубическая функция с тремя действительными корнями
• Квадратное уравнение § Квадратичная факторизация

Примечания

1. Галлиан 2012, стр. 311
2. Mac Lane & Birkhoff 1999 не дают явного определения «приводимому», но используют его в нескольких местах. Например: «В настоящее время мы отмечаем только, что любой приводимый квадратичный или кубический многочлен должен иметь линейный множитель» (стр. 268).
3. Дэвид Даммит; Ричард Фут (2004). "гл. 9, Предложение 12". Абстрактная алгебра . Wiley. стр. 309. ISBN 0-471-43334-9.
4. Якобсон, Натан (1985). "4.13 Конечные поля". Основная алгебра I (PDF) . Нью-Йорк: WH Freeman and Company. ISBN 0-7167-1480-9.
5. Chebolu, Sunil; Mináč, Ján (2011). «Подсчет неприводимых многочленов над конечными полями с использованием принципа включения-исключения» (PDF) . Mathematics Magazine . 84 (5): 369–371. doi :10.4169/math.mag.84.5.369 . Получено 03.04.2023 .
6. Брейяр, Эммануэль; Варжу, Петер П. (2018). «Неприводимость случайных полиномов большой степени». Акта Математика . 223 (2): 195–249. arXiv : 1810.13360 . doi :10.4310/ACTA.2019.v223.n2.a1. S2CID  119173838.
7. Хартнетт, Кевин. «Во Вселенной уравнений практически все являются простыми». Журнал Quanta . Получено 13.01.2019 .
8. Фрелих, А.; Шеферсон, Дж. К. (1955), «О факторизации полиномов за конечное число шагов», Mathematische Zeitschrift , 62 (1): 331–4, doi : 10.1007/BF01180640, ISSN  0025-5874, S2CID  119955899
9. Рассмотрим p — простое число, которое является приводимым: p = ab . Тогда p | ab ⇒ p | a или p | b . Скажем, p | a ⇒ a = pc , тогда имеем: p = ab = pcb ⇒ p (1 − cb ) = 0. Поскольку R — область, то cb = 1. Поэтому b — единица, а p — неприводимо.

Ссылки

• Ланг, Серж (2002), Алгебра , Graduate Texts in Mathematics , т. 211 (пересмотренное третье издание), Нью-Йорк: Springer-Verlag, ISBN 978-0-387-95385-4, г-н  1878556. Эта классическая книга охватывает большую часть содержания данной статьи.
• Галлиан, Джозеф (2012), Современная абстрактная алгебра (8-е изд.), Cengage Learning, ISBN 978-1285402734
• Лидл, Рудольф; Нидеррайтер, Харальд (1997), Конечные поля (2-е изд.), Cambridge University Press , ISBN 978-0-521-39231-0, стр. 91.
• Мак Лейн, Сондерс ; Биркгофф, Гарретт (1999), Алгебра (3-е изд.), Американское математическое общество, ISBN 9780821816462
• Менезес, Альфред Дж .; Ван Оршот, Пол К.; Ванстоун , Скотт А. (1997), Справочник по прикладной криптографии , CRC Press , ISBN 978-0-8493-8523-0, стр. 154.

Внешние ссылки

• Вайсштейн, Эрик В. «Неприводимый многочлен». MathWorld .
• неприводимый многочлен в PlanetMath .
• Информация о примитивных и неприводимых многочленах, (комбинаторный) сервер объектов.