Симметричный полином

В математике симметричный полином — это полином $P (X 1, X 2, ..., X n)$ от $n$ переменных, такой, что если любую из переменных поменять местами, получается тот же полином. Формально $P$ является симметричным полиномом , если для любой перестановки $σ$ индексов $1, 2, ..., n$ имеет место $P (X σ(1), X σ(2), ..., X σ(n)) знак равно п (Икс 1, Икс 2, ..., Икс п)$ .

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

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

Примеры

Следующие полиномы от двух переменных X ₁ и X ₂ симметричны:

X_{1}^{3}+X_{2}^{3}-7

4X_{1}^{2}X_{2}^{2}+X_{1}^{3}X_{2}+X_{1}X_{2}^{3}+(X_{1 }+X_{2})^{4}

как и следующий многочлен от трех переменных X ₁ , X ₂ , X ₃ :

X_{1}X_{2}X_{3}-2X_{1}X_{2}-2X_{1}X_{3}-2X_{2}X_{3}

Есть много способов составить определенные симметричные полиномы от любого количества переменных (см. различные типы ниже). Пример несколько иного вкуса:

\prod _{1\leq i<j\leq n}(X_{i}-X_{j})^{2}

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

С другой стороны, полином от двух переменных

X_{1}-X_{2}

не симметричен, так как если поменять и получить другой полином, . Аналогично с тремя переменными $X_{1}$ $X_{2}$ $X_{2}-X_{1}$

X_{1}^{4}X_{2}^{2}X_{3}+X_{1}X_{2}^{4}X_{3}^{2}+X_{1}^ {2}X_{2}X_{3}^{4}

имеет симметрию только относительно циклических перестановок трех переменных, чего недостаточно, чтобы быть симметричным полиномом. Однако следующее симметрично:

X_{1}^{4}X_{2}^{2}X_{3}+X_{1}X_{2}^{4}X_{3}^{2}+X_{1}^ {2}X_{2}X_{3}^{4}+X_{1}^{4}X_{2}X_{3}^{2}+X_{1}X_{2}^{2}X_ {3}^{4}+X_{1}^{2}X_{2}^{4}X_{3}

Приложения

Теория Галуа

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

Это дает подход к решению полиномиальных уравнений путем инвертирования этого отображения, «нарушая» симметрию – учитывая коэффициенты многочлена (элементарные симметричные многочлены в корнях), как можно восстановить корни? Это приводит к изучению решений многочленов с использованием группы перестановок корней, первоначально в форме резольвент Лагранжа , позднее развитой в теории Галуа .

Связь с корнями монического одномерного многочлена

Рассмотрим монический многочлен от t степени n

P=t^{n}+a_{n-1}t^{n-1}+\cdots +a_{2}t^{2}+a_{1}t+a_{0}

с коэффициентами a _i в некотором поле K . Существует n корней x ₁ ,..., x _n из P в каком-то, возможно, большем поле (например, если K — поле действительных чисел , корни будут существовать в поле комплексных чисел ); некоторые корни могут быть равны, но тот факт, что у одного есть все корни, выражается соотношением

P=t^{n}+a_{n-1}t^{n-1}+\cdots +a_{2}t^{2}+a_{1}t+a_{0}=( t-x_{1})(t-x_{2})\cdots (t-x_{n}).

Сравнивая коэффициенты, находим, что

{\begin{aligned}a_{n-1}&=-x_{1}-x_{2}-\cdots -x_{n}\\a_{n-2}&=x_{1}x_ {2}+x_{1}x_{3}+\cdots +x_{2}x_{3}+\cdots +x_{n-1}x_{n}=\textstyle \sum _{1\leq i< j\leq n}x_{i}x_{j}\\&{}\ \,\vdots \\a_{1}&=(-1)^{n-1}(x_{2}x_{3} \cdots x_{n}+x_{1}x_{3}x_{4}\cdots x_{n}+\cdots +x_{1}x_{2}\cdots x_{n-2}x_{n}+ x_{1}x_{2}\cdots x_{n-1})=\textstyle (-1)^{n-1}\sum _{i=1}^{n}\prod _{j\neq i }x_{j}\\a_{0}&=(-1)^{n}x_{1}x_{2}\cdots x_{n}.\end{aligned}}

На самом деле это всего лишь примеры формул Виеты . Они показывают, что все коэффициенты многочлена задаются через корни с помощью симметричного полиномиального выражения : хотя для данного многочлена P могут быть качественные различия между корнями (например, лежат ли они в базовом поле K или нет, будучи простыми или кратными корни), ничто из этого не влияет на то, как корни встречаются в этих выражениях.

Теперь можно изменить точку зрения, приняв в качестве основных параметров для описания P корни, а не коэффициенты , и рассматривая их как неопределенные, а не как константы в соответствующем поле; тогда коэффициенты a _i становятся просто конкретными симметричными полиномами, заданными приведенными выше уравнениями. Эти многочлены без знака известны как элементарные симметричные многочлены от x ₁ , ..., x _n . Основной факт, известный как фундаментальная теорема о симметричных многочленах , гласит, что любой симметричный многочлен от n переменных может быть задан полиномиальным выражением в терминах этих элементарных симметричных многочленов. Отсюда следует, что любое симметричное полиномиальное выражение в корнях монического многочлена может быть выражено как многочлен от коэффициентов многочлена, и, в частности, что его значение лежит в базовом поле K , которое содержит эти коэффициенты. Таким образом, при работе только с такими симметричными полиномиальными выражениями в корнях нет необходимости знать что-либо конкретное об этих корнях или выполнять вычисления в каком-либо более широком поле, чем K , в котором могут находиться эти корни. Фактически значения самих корней становятся весьма несущественными, и необходимые отношения между коэффициентами и симметричными полиномиальными выражениями могут быть найдены путем вычислений только в терминах симметричных полиномов. Примером таких отношений являются тождества Ньютона , которые выражают сумму любой фиксированной степени корней через элементарные симметричные многочлены. $(-1)^{ni}$

Особые виды симметричных многочленов

Существует несколько типов симметричных полиномов от переменных X ₁ , X ₂ , ..., X _n , которые являются фундаментальными.

Элементарные симметричные полиномы

Для каждого неотрицательного целого числа k элементарный симметричный многочлен e _k ( X ₁ , ..., X _n ) представляет собой сумму всех различных произведений k различных переменных. (Некоторые авторы вместо этого обозначают его через σ _k .) При k = 0 существует только пустой продукт , поэтому e ₀ ( X ₁ , ..., X _n ) = 1, а при k > n вообще не может быть никаких продуктов. формируется, поэтому e _k ( X ₁ , X ₂ , ..., X _n ) = 0 в этих случаях. Остальные n элементарных симметричных многочленов являются строительными блоками для всех симметричных многочленов от этих переменных: как упоминалось выше, любой симметричный многочлен от рассматриваемых переменных может быть получен из этих элементарных симметричных многочленов только с помощью умножения и сложения. На самом деле имеются следующие более подробные факты:

любой симметричный многочлен P от X ₁ , ..., X _n можно записать как полиномиальное выражение от многочленов e _k ( X ₁ , ..., X _n ) с 1 ≤ k ≤ n ;
это выражение единственно с точностью до эквивалентности полиномиальных выражений;
если P имеет целые коэффициенты, то полиномиальное выражение также имеет целые коэффициенты.

Например, для n = 2 соответствующими элементарными симметричными полиномами являются e ₁ ( X ₁ , X ₂ ) = X ₁ + X ₂ и e ₂ ( X ₁ , X ₂ ) = X ₁X ₂ . Тогда первый полином в списке примеров выше можно записать как

X_{1}^{3}+X_{2}^{3}-7=e_{1}(X_{1},X_{2})^{3}-3e_{2}(X_{ 1},X_{2})e_{1}(X_{1},X_{2})-7

(доказательство того , что это всегда возможно, см. в фундаментальной теореме о симметричных многочленах ).

Мономиальные симметричные многочлены

Степени и произведения элементарных симметричных многочленов представляют собой довольно сложные выражения. Если кто-то ищет базовые аддитивные строительные блоки для симметричных многочленов, более естественным выбором будет взять те симметричные многочлены, которые содержат только один тип монома , и только те копии, которые необходимы для получения симметрии. Любой моном из X ₁ , ..., X _n можно записать как X ₁^{α ₁} ... X _n^{α _n} , где показатели степени α _i являются натуральными числами (возможно, нулевыми); записывая α = (α ₁ ,...,α _n ), это можно сократить до X ^α . Мономиальный симметричный полином m _α ( X ₁ , ..., X _n ) определяется как сумма всех мономов x ^β , где β пробегает все различные перестановки (α ₁ ,...,α _n ). Например, у одного есть

m_{(3,1,1)}(X_{1},X_{2},X_{3})=X_{1}^{3}X_{2}X_{3}+X_{1 }X_{2}^{3}X_{3}+X_{1}X_{2}X_{3}^{3}

m_{(3,2,1)}(X_{1},X_{2},X_{3})=X_{1}^{3}X_{2}^{2}X_{3} +X_{1}^{3}X_{2}X_{3}^{2}+X_{1}^{2}X_{2}^{3}X_{3}+X_{1}^{2 }X_{2}X_{3}^{3}+X_{1}X_{2}^{3}X_{3}^{2}+X_{1}X_{2}^{2}X_{3 }^{3}.

Очевидно, что m _α = m _β , когда β является перестановкой α, поэтому обычно рассматриваются только те m _α , для которых α ₁ ≥ α ₂ ≥ ... ≥ α _n , другими словами, для которых α является разбиением целого числа . Эти мономиальные симметричные многочлены образуют базис векторного пространства : каждый симметричный многочлен P можно записать как линейную комбинацию мономиальных симметричных многочленов. Для этого достаточно разделить различные типы одночленов, входящих в P. В частности, если P имеет целые коэффициенты, то и линейная комбинация будет такой же.

Элементарные симметричные многочлены являются частными случаями мономиальных симметричных многочленов: для 0 ≤ k ≤ n имеет место

e_{k}(X_{1},\ldots,X_{n})=m_{\alpha }(X_{1},\ldots,X_{n})

где α — разбиение k на k частей 1 (за которыми следуют n − k нулей).

Симметричные полиномы со степенной суммой

Для каждого целого числа k ≥ 1 особый интерес представляет мономиальный симметричный многочлен m _{( k ,0,...,0)} ( X ₁ , ..., X _n ). Это симметричный полином суммы степеней, определяемый как

p_{k}(X_{1},\ldots ,X_{n})=X_{1}^{k}+X_{2}^{k}+\cdots +X_{n}^{k }.

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

Любой симметричный многочлен от X ₁ , ..., X _n можно выразить в виде полиномиального выражения с рациональными коэффициентами в степенной сумме симметричных многочленов p ₁ ( X ₁ , ..., X _n ), ..., p _n ( Х ₁ , ..., Х _н ).

В частности, остальные полиномы суммы степеней p _k ( X ₁ , ..., X _n ) для k > n могут быть выражены таким образом в первых n полиномах суммы степеней; например

p_{3}(X_{1},X_{2})=\textstyle {\frac {3}{2}}p_{2}(X_{1},X_{2})p_{1} (X_{1},X_{2})-{\frac {1}{2}}p_{1}(X_{1},X_{2})^{3}.

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

m_{(2,1)}(X_{1},X_{2})=X_{1}^{2}X_{2}+X_{1}X_{2}^{2}

имеет выражение

m_{(2,1)}(X_{1},X_{2})=\textstyle {\frac {1}{2}}p_{1}(X_{1},X_{2})^{3}-{\frac {1}{2}}p_{2}(X_{1},X_{2})p_{1}(X_{1},X_{2}).

Используя три переменные, получаем другое выражение

{\begin{aligned}m_{(2,1)}(X_{1},X_{2},X_{3})&=X_{1}^{2}X_{2}+X_{1}X_{2}^{2}+X_{1}^{2}X_{3}+X_{1}X_{3}^{2}+X_{2}^{2}X_{3}+X_{2}X_{3}^{2}\\&=p_{1}(X_{1},X_{2},X_{3})p_{2}(X_{1},X_{2},X_{3})-p_{3}(X_{1},X_{2},X_{3}).\end{aligned}}

Соответствующее выражение было справедливо и для двух переменных (достаточно установить X ₃ равным нулю), но, поскольку оно включает p ₃ , его нельзя было использовать для иллюстрации утверждения для n = 2. Пример показывает, что независимо от того, выражение для данного мономиального симметричного полинома через первые n полиномов суммы степеней включает рациональные коэффициенты, может зависеть от n . Но рациональные коэффициенты всегда необходимы для выражения элементарных симметричных полиномов (кроме постоянных и e ₁ , совпадающего с первой степенной суммой) через степенные полиномы суммы. Тождества Ньютона предоставляют явный метод для этого; оно предполагает деление на целые числа до n , что объясняет рациональные коэффициенты. Из-за этих разделений указанное утверждение, вообще говоря, неверно, когда коэффициенты берутся из поля конечной характеристики ; однако это справедливо для коэффициентов в любом кольце , содержащем рациональные числа.

Полные однородные симметричные полиномы

Для каждого неотрицательного целого числа k полный однородный симметричный полином h _k ( X ₁ , ..., X _n ) представляет собой сумму всех различных мономов степени k от переменных X ₁ , ..., X _n . Например

h_{3}(X_{1},X_{2},X_{3})=X_{1}^{3}+X_{1}^{2}X_{2}+X_{1}^{2}X_{3}+X_{1}X_{2}^{2}+X_{1}X_{2}X_{3}+X_{1}X_{3}^{2}+X_{2}^{3}+X_{2}^{2}X_{3}+X_{2}X_{3}^{2}+X_{3}^{3}.

Полином h _k ( X ₁ , ..., X _n ) также является суммой всех различных мономиальных симметричных многочленов степени k в X ₁ , ..., X _n , например для данного примера

{\begin{aligned}h_{3}(X_{1},X_{2},X_{3})&=m_{(3)}(X_{1},X_{2},X_{3})+m_{(2,1)}(X_{1},X_{2},X_{3})+m_{(1,1,1)}(X_{1},X_{2},X_{3})\\&=(X_{1}^{3}+X_{2}^{3}+X_{3}^{3})+(X_{1}^{2}X_{2}+X_{1}^{2}X_{3}+X_{1}X_{2}^{2}+X_{1}X_{3}^{2}+X_{2}^{2}X_{3}+X_{2}X_{3}^{2})+(X_{1}X_{2}X_{3}).\\\end{aligned}}

Все симметричные многочлены от этих переменных можно составить из полных однородных: любой симметричный многочлен от X ₁ , ..., X _n можно получить из полных однородных симметричных многочленов h ₁ ( X ₁ , ..., X _n ) , ..., h _n ( X ₁ , ..., X _n ) посредством умножения и сложения. Точнее:

Любой симметричный полином P от X ₁ , ..., X _n можно записать как полиномиальное выражение от полиномов h _k ( X ₁ , ..., X _n ) с 1 ≤ k ≤ n .

Если P имеет целые коэффициенты, то полиномиальное выражение также имеет целые коэффициенты.

Например, для n = 2 соответствующими полными однородными симметричными полиномами являются $h 1 (X 1, X 2) = X 1 + X 2$ и $h 2 (X 1, X 2) = X 12 + X 1 X 2 + Х 22$ . Тогда первый полином в списке примеров выше можно записать как

X_{1}^{3}+X_{2}^{3}-7=-2h_{1}(X_{1},X_{2})^{3}+3h_{1}(X_{1},X_{2})h_{2}(X_{1},X_{2})-7.

Как и в случае степенных сумм, данное утверждение применимо, в частности, к полным однородным симметричным многочленам за пределами h _n ( X ₁ , ..., X _n ), позволяя выражать их через единицы до этой точки; снова полученные тождества становятся недействительными, когда количество переменных увеличивается.

Важным аспектом полных однородных симметричных многочленов является их связь с элементарными симметричными многочленами, которую можно выразить в виде тождеств

\sum _{i=0}^{k}(-1)^{i}e_{i}(X_{1},\ldots ,X_{n})h_{k-i}(X_{1},\ldots ,X_{n})=0

, для всех k > 0 и любого количества переменных n .

Поскольку e ₀ ( X ₁ , ..., X _n ) и h ₀ ( X ₁ , ..., X _n ) оба равны 1, можно выделить либо первый, либо последний член этих сумм; первый дает набор уравнений, позволяющий рекурсивно выражать последовательные полные однородные симметричные многочлены через элементарные симметричные многочлены, а второй дает набор уравнений, позволяющий делать обратное. Это неявно показывает, что любой симметричный многочлен может быть выражен через h _k ( X ₁ , ..., X _n ) с 1 ≤ k ≤ n : сначала выражается симметричный многочлен через элементарные симметричные многочлены, а затем выражает их через упомянутые полные однородные.

Полиномы Шура

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

Симметричные многочлены в алгебре

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

Переменные полиномы

Аналогом симметричных полиномов являются чередующиеся полиномы : полиномы, которые не являются инвариантными при перестановке элементов, а меняются в зависимости от знака перестановки .

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