Полиномиальные кольца: структура, свойства и алгоритмы факторизации.

Введение

Алгебраическая структура

В математике, особенно в области алгебры, кольцо многочленов или алгебра многочленов — это кольцо (которое также является коммутативной алгеброй), образованное из множества многочленов от одной или нескольких переменных (традиционно также называемых неопределёнными) с коэффициентами в другом кольце, часто в поле. Зачастую термин "кольцо многочленов" неявно относится к частному случаю кольца многочленов от одной переменной над полем. Важность таких колец многочленов обусловлена большим числом свойств, которые они имеют общими с кольцом целых чисел. Кольца многочленов встречаются и часто являются фундаментальными во многих разделах математики, таких как теория чисел, коммутативная алгебра и алгебраическая геометрия. В теории колец многие классы колец, такие как области однозначной факторизации, регулярные кольца, групповые кольца, кольца формальных степенных рядов, многочлены Оре, градуированные кольца, были введены для обобщения некоторых свойств колец многочленов. Тесно связанным понятием является кольцо полиномиальных функций на векторном пространстве и, в более общем случае, кольцо регулярных функций на алгебраическом многообразии.

Факторизация

За исключением факторизации, все предыдущие свойства K[X] являются эффективными, поскольку их доказательства, как описано выше, связаны с алгоритмами для проверки свойства и вычисления многочленов, существование которых утверждается. Более того, эти алгоритмы эффективны, так как их вычислительная сложность является квадратичной функцией от размера входных данных. Ситуация совершенно иная для факторизации: доказательство единственности факторизации не дает никаких указаний на метод факторизации. Уже для целых чисел неизвестен алгоритм, работающий на классическом компьютере, для их разложения на множители за полиномиальное время. Это лежит в основе криптосистемы RSA, широко используемой для безопасной интернет-коммуникации. В случае K[X] факторы и методы их вычисления сильно зависят от K. Над комплексными числами все неприводимые факторы (те, которые нельзя разложить на множители дальше) имеют степень один, тогда как над действительными числами существуют неприводимые многочлены степени 2, а над рациональными числами – неприводимые многочлены любой степени. Например, многочлен неприводим над рациональными числами, разлагается как над действительными числами и как над комплексными числами. Существование алгоритма факторизации также зависит от базового поля. В случае действительных или комплексных чисел теорема Абеля — Руффини показывает, что корни некоторых многочленов, а следовательно, и неприводимые факторы, не могут быть вычислены точно. Поэтому алгоритм факторизации может вычислять только приближения факторов. Различные алгоритмы были разработаны для вычисления таких приближений, см. Поиск корней многочленов. Существует пример поля K, для которого существуют точные алгоритмы арифметических операций в K, но не может существовать алгоритма для определения, является ли многочлен вида неприводимым или является произведением многочленов меньшей степени. С другой стороны, над рациональными числами и над конечными полями ситуация лучше, чем для целочисленной факторизации, поскольку существуют алгоритмы факторизации с полиномиальной сложностью. Они реализованы в большинстве систем компьютерной алгебры общего назначения.

Except for factorization, all previous properties of K[X] are effective, since their proofs, as sketched above, are associated with algorithms for testing the property and computing the polynomials whose existence are asserted. Moreover these algorithms are efficient, as their computational complexity is a quadratic function of the input size. The situation is completely different for factorization: the proof of the unique factorization does not give any hint for a method for factorizing. Already for the integers, there is no known algorithm running on a classical computer for factorizing them in polynomial time. This is the basis of the RSA cryptosystem, widely used for secure Internet communications. In the case of K[X], the factors, and the methods for computing them, depend strongly on K. Over the complex numbers, the irreducible factors (those that cannot be factorized further) are all of degree one, while, over the real numbers, there are irreducible polynomials of degree 2, and, over the rational numbers, there are irreducible polynomials of any degree. For example, the polynomial is irreducible over the rational numbers, is factored as over the real numbers and, and as over the complex numbers. The existence of a factorization algorithm depends also on the ground field. In the case of the real or complex numbers, Abel–Ruffini theorem shows that the roots of some polynomials, and thus the irreducible factors, cannot be computed exactly. Therefore, a factorization algorithm can compute only approximations of the factors. Various algorithms have been designed for computing such approximations, see Root finding of polynomials. There is an example of a field K such that there exist exact algorithms for the arithmetic operations of K, but there cannot exist any algorithm for deciding whether a polynomial of the form is irreducible or is a product of polynomials of lower degree. On the other hand, over the rational numbers and over finite fields, the situation is better than for integer factorization, as there are factorization algorithms that have a polynomial complexity. They are implemented in most general purpose computer algebra systems.

Минимальный полином

Если θ является элементом ассоциативной K-алгебры L, то вычисление значения многочлена в θ является единственным алгебраическим гомоморфизмом φ из K[X] в L, который отображает X в θ и не изменяет элементы K (является тождественным отображением на K). Оно заключается в подстановке θ вместо X в каждом многочлене. То есть, образ этого гомоморфизма вычисления является субалгеброй, порожденной θ, которая обязательно коммутативна. Если φ инъективен, то субалгебра, порожденная θ, изоморфна K[X]. В этом случае эта субалгебра часто обозначается K[θ]. Неоднозначность обозначений, как правило, несущественна из-за изоморфизма. Если гомоморфизм вычисления не инъективен, это означает, что его ядро является ненулевым идеалом, состоящим из всех многочленов, обращающихся в нуль при подстановке θ вместо X. Этот идеал состоит из всех кратных некоторому моному, который называется минимальным полиномом для θ. Термин "минимальный" обусловлен тем, что его степень минимальна среди степеней элементов идеала. Существует два основных случая, когда рассматриваются минимальные полиномы. В теории полей и теории чисел элемент θ поля расширения L поля K называется алгебраическим над K, если он является корнем некоторого многочлена с коэффициентами в K. Минимальный полином над K для θ, таким образом, является момоническим многочленом минимальной степени, имеющим θ в качестве корня. Поскольку L является полем, этот минимальный полином обязательно неприводим над K. Например, минимальный полином (как над действительными, так и над рациональными числами) комплексного числа i равен. Циклотомические полиномы являются минимальными полиномами корней из единицы. В линейной алгебре квадратные матрицы размера n×n над K образуют ассоциативную K-алгебру конечной размерности (как векторное пространство). Следовательно, гомоморфизм вычисления не может быть инъективным, и каждая матрица имеет минимальный полином (не обязательно неприводимый). По теореме Кейли–Гамильтона, гомоморфизм вычисления отображает в нуль характеристический полином матрицы. Отсюда следует, что минимальный полином делит характеристический полином, и, следовательно, степень минимального полинома не превосходит n.

If θ is an element of an associative K algebra L, the polynomial evaluation at θ is the unique algebra homomorphism φ from K[X] into L that maps X to θ and does not affect the elements of K itself (it is the identity map on K). It consists of substituting X with θ in every polynomial. That is,

The image of this evaluation homomorphism is the subalgebra generated by θ, which is necessarily commutative. If φ is injective, the subalgebra generated by θ is isomorphic to K[X]. In this case, this subalgebra is often denoted by K[θ]. The notation ambiguity is generally harmless, because of the isomorphism. If the evaluation homomorphism is not injective, this means that its kernel is a nonzero ideal, consisting of all polynomials that become zero when X is substituted with θ. This ideal consists of all multiples of some monic polynomial, that is called the minimal polynomial of θ. The term minimal is motivated by the fact that its degree is minimal among the degrees of the elements of the ideal. There are two main cases where minimal polynomials are considered. In field theory and number theory, an element θ of an extension field L of K is algebraic over K if it is a root of some polynomial with coefficients in K. The minimal polynomial over K of θ is thus the monic polynomial of minimal degree that has θ as a root. Because L is a field, this minimal polynomial is necessarily irreducible over K. For example, the minimal polynomial (over the reals as well as over the rationals) of the complex number i is The cyclotomic polynomials are the minimal polynomials of the roots of unity. In linear algebra, the n×n square matrices over K form an associative K algebra of finite dimension (as a vector space). Therefore the evaluation homomorphism cannot be injective, and every matrix has a minimal polynomial (not necessarily irreducible). By Cayley–Hamilton theorem, the evaluation homomorphism maps to zero the characteristic polynomial of a matrix. It follows that the minimal polynomial divides the characteristic polynomial, and therefore that the degree of the minimal polynomial is at most n.

Полиномиальное выражение

Полиномиальное выражение – это выражение, построенное из скаляров (элементов K), неопределённых и операций сложения, умножения и возведения в неотрицательную целую степень. Поскольку все эти операции определены в полиномиальном выражении, оно представляет собой многочлен, то есть элемент K[x]. Определение многочлена как линейной комбинации мономов является конкретным полиномиальным выражением, которое часто называют канонической формой, нормальной формой или развёрнутой формой многочлена. Для заданного полиномиального выражения можно вычислить развёрнутую форму представляемого им многочлена, раскрывая скобки с помощью дистрибутивного закона во всех произведениях, содержащих сумму в качестве одного из множителей, а затем используя коммутативность (за исключением произведения двух скаляров) и ассоциативность для преобразования членов полученной суммы в произведения скаляра и монома; после этого каноническая форма получается путём приведения подобных членов. Различие между полиномиальным выражением и многочленом, который оно представляет, относительно недавнее и в основном обусловлено развитием компьютерной алгебры, где, например, проверка того, представляют ли два полиномиальных выражения один и тот же многочлен, может быть нетривиальной задачей.

Категорическая характеристика

Если K – коммутативное кольцо, то кольцо многочленов K[X₁, …, Xₙ] обладает следующим универсальным свойством: для каждой коммутативной K-алгебры A и каждой n-кортежа (x₁, …, xₙ) элементов A существует единственный алгебраический гомоморфизм из K[X₁, …, Xₙ] в A, который отображает каждый Xᵢ в соответствующий xᵢ. Этот гомоморфизм является гомоморфизмом подстановки, заключающимся в замене Xᵢ на xᵢ в каждом многочлене. Как и в случае любого универсального свойства, это однозначно определяет пару (K[X₁, …, Xₙ], A) с точностью до уникального изоморфизма. Это также можно интерпретировать в терминах сопряжённых функторов. Более точно, пусть SET и ALG будут категориями множеств и коммутативных K-алгебр соответственно (здесь и далее морфизмы определены тривиально). Существует забывающий функтор, отображающий алгебры в их базовые множества. С другой стороны, отображение K[X₁, …, Xₙ] → A определяет функтор в противоположном направлении. (Если X бесконечно, K[X] – множество всех многочленов от конечного числа элементов X.) Универсальное свойство кольца многочленов означает, что F и POL являются сопряжёнными функторами. Это можно также выразить, сказав, что кольца многочленов являются свободными коммутативными алгебрами, поскольку они являются свободными объектами в категории коммутативных алгебр. Аналогично, кольцо многочлена с целыми коэффициентами является свободным коммутативным кольцом над своим набором переменных, поскольку коммутативные кольца и коммутативные алгебры над целыми числами – это одно и то же.

Несколько неопределенных по поле

Многочленные кольца в нескольких переменных над полем фундаментальны в инвариантной теории и алгебраической геометрии. Некоторые из их свойств, такие как описанные выше, могут быть сведены к случаю одной переменной, но это не всегда возможно. В частности, из-за геометрических приложений, многие интересные свойства должны быть инвариантными относительно аффинных или проективных преобразований переменных. Это часто означает, что нельзя выбрать одну из переменных для рекуррентного соотношения относительно переменных. Теорема Безу, теорема Гильберта о нулях и гипотеза Якоби — одни из наиболее известных свойств, специфичных для многомерных многочленов над полем.