Симметрические многочлены: основная теорема

Симметрический многочлен это многочлен от нескольких переменных, который не меняется при любой перестановке этих переменных: поменяйте местами $x$ и $y$ в выражении $x^2 + y^2$, и оно останется прежним. Основная теорема о симметрических многочленах утверждает нечто гораздо более сильное: любой такой многочлен можно единственным образом записать через несколько простейших симметрических многочленов, которые называют элементарными. Это превращает работу с симметрией в почти механическую процедуру и лежит в основе теоремы Виета, теории Галуа и формул для степенных сумм. Ниже разберём строгие определения, элементарные симметрические многочлены, сам алгоритм выражения и места, где чаще всего ошибаются. Чтобы сразу собрать разбор под своё выражение, соберите запрос в форме ниже.

Что такое симметрический многочлен

Формально многочлен $f(x_1, x_2, \dots, x_n)$ называется симметрическим, если для любой перестановки $\sigma$ индексов выполняется равенство

$f(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)}) = f(x_1, x_2, \dots, x_n).$

Иначе говоря, переменные в нём полностью равноправны: ни одна не выделена. Простейшие примеры для двух переменных это сумма $x + y$, произведение $xy$ и сумма квадратов $x^2 + y^2$. А вот $x^2 + y$ симметрическим не является: перестановка превращает его в $y^2 + x$, и это уже другой многочлен.

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

Рассчитать для своей задачи

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

Ключевые образующие это элементарные симметрические многочлены $e_1, e_2, \dots, e_n$. Многочлен $e_k$ это сумма всех произведений переменных, взятых по $k$ штук без повторений. Для трёх переменных $x, y, z$ они выглядят так:

$$\begin{aligned} e_1 &= x + y + z, \\ e_2 &= xy + xz + yz, \\ e_3 &= xyz. \end{aligned}$$

Каждое слагаемое в $e_k$ это произведение ровно $k$ различных переменных, а всего таких слагаемых столько, сколько способов выбрать $k$ переменных из $n$. По определению $e_0 = 1$, а при $k > n$ многочлен $e_k$ считается нулевым: нельзя выбрать больше переменных, чем их есть.

Эти многочлены не случайны: они появляются как коэффициенты, если раскрыть произведение $(t - x)(t - y)(t - z)$. Это прямая связь с теоремой Виета, к которой мы вернёмся ниже. А пока важно главное: именно через $e_1, \dots, e_n$ основная теорема обещает выразить вообще любой симметрический многочлен.

Формулировка основной теоремы

Основная теорема о симметрических многочленах звучит так: каждый симметрический многочлен от переменных $x_1, \dots, x_n$ единственным образом представляется в виде многочлена от элементарных симметрических многочленов $e_1, \dots, e_n$. То есть для любого симметрического $f$ существует такой многочлен $P$, что

$f(x_1, \dots, x_n) = P(e_1, e_2, \dots, e_n),$

и этот $P$ определён однозначно. Утверждение распадается на две части: существование выражения (любой симметрический многочлен в принципе выражается) и единственность (выражение ровно одно). Существование даёт практический алгоритм, а единственность означает, что $e_1, \dots, e_n$ алгебраически независимы, то есть никакое нетривиальное многочленное соотношение их не связывает.

Рассчитать для своей задачи

Как выражают многочлен через элементарные

Существование выражения доказывается конструктивным алгоритмом, который заодно служит и способом счёта. Удобнее всего упорядочить мономы лексикографически: моном $x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$ сравнивается с другим по первой отличающейся степени. У симметрического многочлена берут старший по этому порядку моном $x_1^{a_1} \cdots x_n^{a_n}$, причём в силу симметрии показатели можно считать невозрастающими: $a_1 \ge a_2 \ge \dots \ge a_n$.

Затем из этого старшего монома собирают подходящее произведение элементарных симметрических многочленов:

$e_1^{\,a_1 - a_2}\, e_2^{\,a_2 - a_3} \cdots e_{n-1}^{\,a_{n-1} - a_n}\, e_n^{\,a_n}.$

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

Маленький пример для двух переменных: возьмём $x^2 + y^2$. Здесь $e_1 = x + y$, $e_2 = xy$. Замечаем, что $e_1^2 = x^2 + 2xy + y^2$, поэтому $x^2 + y^2 = e_1^2 - 2e_2$. Аналогично сумма кубов даёт $x^3 + y^3 = e_1^3 - 3 e_1 e_2$. Эти короткие тождества постоянно выручают на олимпиадах и в задачах на симметрию.

Связь с теоремой Виета и корнями уравнения

Главная причина, по которой основная теорема так важна, это связь с корнями многочлена. Если $x_1, \dots, x_n$ корни приведённого многочлена $t^n + c_{n-1} t^{n-1} + \dots + c_0$, то по теореме Виета его коэффициенты с точностью до знака совпадают с элементарными симметрическими многочленами от корней:

$c_{n-k} = (-1)^k\, e_k(x_1, \dots, x_n).$

Отсюда следует мощное практическое правило: любая симметрическая функция корней выражается через коэффициенты уравнения, а значит вычисляется без нахождения самих корней. Хотите узнать $x_1^2 + x_2^2 + x_3^2$, не решая кубическое уравнение? Запишите эту сумму через $e_1, e_2$, а их возьмите прямо из коэффициентов. Этот приём роднит основную теорему с обычной теоремой Виета: для квадратного случая та же логика разбирается в материале про теорему Виета для приведённого уравнения, где сумма и произведение корней это как раз $e_1$ и $e_2$.

Рассчитать для своей задачи

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

Вторая половина теоремы, единственность выражения, не менее важна, чем существование. Она равносильна утверждению, что элементарные симметрические многочлены алгебраически независимы над основным полем: если многочлен $Q(e_1, \dots, e_n)$ тождественно равен нулю как функция от исходных переменных, то $Q$ это нулевой многочлен. Доказывается это снова через лексикографический старший моном: разным наборам показателей у произведений $e_1^{b_1} \cdots e_n^{b_n}$ отвечают разные старшие мономы, поэтому они не могут сократиться.

Из единственности следует, что кольцо симметрических многочленов от $n$ переменных изоморфно кольцу многочленов от $n$ независимых переменных $e_1, \dots, e_n$. Это и есть строгая форма утверждения, что $e_k$ образуют свободный базис: симметрия от $n$ переменных устроена ровно так же, как обычная алгебра от $n$ переменных, только переменные теперь это элементарные симметрические многочлены.

Частые ошибки

• Считают симметрическим то, что симметрическим не является. Многочлен должен быть инвариантен при любой перестановке. $x^2 + y$ меняется при обмене $x$ и $y$, поэтому он не симметричен, хотя на вид и компактен.
• Путают элементарные симметрические со степенными суммами. $e_2 = xy + xz + yz$ это не то же самое, что $p_2 = x^2 + y^2 + z^2$. Их связывает тождество $p_2 = e_1^2 - 2 e_2$, но это разные объекты.
• Берут не старший моном в алгоритме. Алгоритм требует именно лексикографически старший моном с невозрастающими показателями; ошибка в выборе ломает убывание и зацикливает процесс.
• Забывают про знак в теореме Виета. Коэффициенты связаны с $e_k$ через множитель $(-1)^k$, и пропуск этого знака даёт неверный ответ для нечётных $k$.
• Думают, что выражение неоднозначно. По основной теореме представление через $e_k$ ровно одно; если получилось два разных, где-то ошибка в счёте.

FAQ

Сколько элементарных симметрических многочленов у $n$ переменных? Ровно $n$ штук: $e_1, e_2, \dots, e_n$, где $e_k$ это сумма всех произведений переменных по $k$ без повторений. Дополнительно по соглашению $e_0 = 1$, а при $k > n$ многочлен $e_k$ равен нулю. Этого набора из $n$ образующих достаточно, чтобы выразить любой симметрический многочлен.

Чем основная теорема отличается от теоремы Виета? Теорема Виета связывает коэффициенты конкретного уравнения с элементарными симметрическими многочленами от его корней. Основная теорема о симметрических многочленах это более общее утверждение: она говорит, что вообще любой симметрический многочлен выражается через элементарные, и притом единственным образом. Виета это её частный случай, применённый к коэффициентам.

Зачем нужны степенные суммы, если есть элементарные многочлены? Степенные суммы $p_k = x_1^k + \dots + x_n^k$ тоже образуют систему образующих над полем нулевой характеристики и часто удобнее в задачах про корни. Их связь с $e_k$ задают формулы Ньютона, которые позволяют переходить от одного набора к другому. На практике выбирают тот набор, в котором ответ записывается короче.

Коротко

Симметрический многочлен не меняется при перестановке переменных, и основная теорема утверждает, что любой такой многочлен единственным образом выражается через элементарные симметрические многочлены $e_1, \dots, e_n$ - суммы всех произведений переменных по $k$ штук. Существование выражения даёт конструктивный алгоритм через лексикографически старший моном, а единственность означает алгебраическую независимость $e_k$. Через теорему Виета элементарные многочлены совпадают (с точностью до знака) с коэффициентами уравнения, поэтому любая симметрическая функция корней вычисляется прямо из коэффициентов, без нахождения самих корней.