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

Полином без нетривиальной факторизации

В математике неприводимым многочленом называют , грубо говоря, многочлен , который нельзя разложить на произведение двух непостоянных многочленов . Свойство неприводимости зависит от природы коэффициентов , принимаемых за возможные факторы, т. е. от поля , которому предположительно принадлежат коэффициенты многочлена и его возможные факторы. Например, многочлен 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 .

Над реальными событиями

В поле действительных чисел степень неприводимого одномерного многочлена равна единице или двум . Точнее, неприводимые многочлены - это многочлены первой степени и квадратичные многочлены , имеющие отрицательный дискриминант . Отсюда следует, что каждый непостоянный одномерный многочлен можно разложить на множители как произведение многочленов степени не выше двух. Например, факторы над действительными числами as и не могут быть факторизованы дальше, поскольку оба фактора имеют отрицательный дискриминант: ${\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 N(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 нередуцибилис , неприводимая кубика с тремя действительными корнями.
• Квадратное уравнение § Квадратичная факторизация

Примечания

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

Рекомендации

• Ланг, Серж (2002), Алгебра , Тексты для выпускников по математике , том. 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.

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

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