Неравенство Мюрхеда: мажорирование и симметричные суммы

Неравенство Мюрхеда - это удобный инструмент для сравнения симметричных сумм одночленов: оно говорит, что чем «равномернее» распределены показатели степеней, тем меньше соответствующая симметричная сумма. Формально сравнение наборов показателей задаётся отношением мажорирования, а сами суммы строятся симметризацией одночлена по всем перестановкам переменных. Из неравенства Мюрхеда как частные случаи вытекают неравенство между средним арифметическим и средним геометрическим (AM-GM) и многие олимпиадные оценки. Ниже разберём точную формулировку, как проверять мажорирование, доказательство и типичные применения. Если нужно сразу применить неравенство Мюрхеда к конкретной задаче, удобнее собрать постановку в форме ниже и продолжить разбор в чате.

Симметричная сумма и обозначение Мюрхеда

Пусть даны неотрицательные числа $x_1, \dots, x_n$ и набор показателей $a = (a_1, \dots, a_n)$. Симметричной суммой называют величину, в которой одночлен $x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$ суммируется по всем $n!$ перестановкам переменных:

$$[a] = \frac{1}{n!} \sum_{\sigma \in S_n} x_{\sigma(1)}^{a_1} x_{\sigma(2)}^{a_2} \cdots x_{\sigma(n)}^{a_n}.$$

Деление на $n!$ делает выражение симметричным средним, а не просто суммой, что удобно: при равных переменных $x_i = 1$ оно равно единице. Например, при $n = 2$ набор $a = (1, 0)$ даёт $[1,0] = \tfrac12(x_1 + x_2)$ - среднее арифметическое, а набор $a = (\tfrac12, \tfrac12)$ даёт $[\tfrac12,\tfrac12] = \sqrt{x_1 x_2}$ - среднее геометрическое. Так уже на двух переменных видно, что Мюрхед обобщает AM-GM.

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

Мажорирование: когда один набор «равномернее» другого

Главное понятие - мажорирование. Говорят, что набор $a$ мажорирует набор $b$ (пишут $a \succ b$), если после сортировки обоих по убыванию выполнены условия:

$$\sum_{i=1}^n a_i = \sum_{i=1}^n b_i, \qquad \sum_{i=1}^k a_i \ge \sum_{i=1}^k b_i \quad \text{для всех } k = 1, \dots, n.$$

Первое условие - равенство полных сумм (одинаковая суммарная степень одночлена), второе - все частичные суммы старшего набора не меньше. Содержательно мажорирование означает, что показатели $a$ «более неравномерны»: их масса сильнее сконцентрирована в больших компонентах, тогда как $b$ ближе к равномерному распределению. Классический пример: $(3, 0) \succ (2, 1) \succ (\tfrac32, \tfrac32)$ - степени постепенно выравниваются.

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

Формулировка неравенства Мюрхеда

Неравенство Мюрхеда связывает мажорирование наборов и порядок их симметричных сумм. Для неотрицательных $x_1, \dots, x_n$ и наборов с одинаковой суммой компонент:

$$a \succ b \quad \Longrightarrow \quad [a] \ge [b].$$

Иными словами, более неравномерный набор показателей даёт большую симметричную сумму. Верно и обратное при положительных переменных: если $[a] \ge [b]$ выполнено для всех положительных $x_i$, то $a \succ b$. Поэтому мажорирование - не просто достаточное, а критериальное условие для сравнения симметричных средних одной степени.

Самый яркий частный случай - AM-GM. Возьмём $a = (1, 0, \dots, 0)$ и $b = (\tfrac1n, \dots, \tfrac1n)$. Тогда $a \succ b$, а неравенство $[a] \ge [b]$ превращается в

$$\frac{x_1 + \dots + x_n}{n} \ge \sqrt[n]{x_1 \cdots x_n},$$

то есть в неравенство между средним арифметическим и геометрическим. Так Мюрхед даёт единый взгляд на целое семейство неравенств о средних, родственный подходу через выпуклость - см. неравенство Йенсена для выпуклых функций.

Доказательство через усреднение перестановок

Опорный шаг доказательства - это случай, когда наборы $a$ и $b$ отличаются «переносом массы» между двумя координатами. Если $b$ получается из $a$ заменой пары $(a_i, a_j)$ с $a_i > a_j$ на пару $(a_i - t,\ a_j + t)$, где $0 < t \le a_i - a_j$ (так называемое преобразование Робина–Худа, которое уменьшает неравномерность), то достаточно проверить элементарное неравенство для двух показателей. Зафиксировав остальные переменные, нужно показать, что для любых $u, v \ge 0$

$$u^{a_i} v^{a_j} + u^{a_j} v^{a_i} \ge u^{a_i - t} v^{a_j + t} + u^{a_j + t} v^{a_i - t}.$$

Это сводится к $(u^{p} - v^{p})(u^{q} - v^{q}) \ge 0$ с подходящими $p, q \ge 0$ - произведение двух сомножителей одного знака, что неотрицательно. Суммирование такого неравенства по всем перестановкам даёт $[a] \ge [b]$ для одного шага. Общий случай завершается ключевой теоремой: $a \succ b$ тогда и только тогда, когда $b$ получается из $a$ конечной цепочкой таких усредняющих преобразований (теорема Харди–Литлвуда–Пойа о бистохастических матрицах). Применяя одношаговую оценку вдоль цепочки, получаем неравенство в общем виде.

Условие равенства

Равенство $[a] = [b]$ при $a \succ b$ и $a \ne b$ (как мультимножества показателей) достигается только в тривиальных ситуациях. Если все переменные равны, $x_1 = \dots = x_n$, то любая симметричная сумма равна $x^{s}$, где $s$ - общая степень, и все $[a]$ совпадают. При различных положительных $x_i$ равенство возможно лишь когда наборы $a$ и $b$ совпадают с точностью до перестановки. Это та же логика, что в AM-GM: среднее арифметическое равно среднему геометрическому ровно тогда, когда все числа одинаковы. Поэтому в олимпиадных задачах после применения Мюрхеда точку равенства ищут среди равных переменных.

Как применять Мюрхеда к олимпиадным неравенствам

Типовая схема работы с симметричным неравенством такая. Сначала раскрывают обе части до симметричных сумм одночленов одинаковой полной степени (однородность обязательна - если степени разные, неравенство нормируют, например условием $x_1 + \dots + x_n = 1$ или $x_1 x_2 x_3 = 1$). Затем для каждой пары сумм проверяют мажорирование наборов показателей: если левый набор мажорирует правый, неравенство Мюрхеда даёт нужную оценку напрямую. Когда мажорирования между крайними наборами нет, помогает разложение SOS (сумма квадратов) или применение Мюрхеда к промежуточным наборам и сложение нескольких оценок.

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

Например, неравенство $x^3 + y^3 + z^3 \ge x^2 y + y^2 z + z^2 x$ для неотрицательных переменных не доказывается одним Мюрхедом напрямую (правая часть не симметрична), но его симметризованная версия $x^3 + y^3 + z^3 \ge x^2 y + \dots$ по всем шести членам сразу следует из $(3,0,0) \succ (2,1,0)$. Близкая по духу техника - оценка дробей через метод, описанный в материале про неравенство Гёльдера для интегралов, который тоже опирается на сравнение взвешенных сумм.

Ещё один показательный пример - оценка $x^2 y^2 + y^2 z^2 + z^2 x^2 \le x^4 + y^4 + z^4$. Здесь полная степень равна четырём в обеих частях, симметричные суммы соответствуют наборам $b = (2, 2, 0)$ слева и $a = (4, 0, 0)$ справа. Сортируем и проверяем частичные суммы: $4 \ge 2$, $4 + 0 \ge 2 + 2$, $4 + 0 + 0 = 2 + 2 + 0$ - все условия мажорирования выполнены, значит $a \succ b$ и $[a] \ge [b]$, что и даёт требуемое. Этот приём - записать обе части как наборы показателей и формально проверить четыре строки условий - экономит много выкладок по сравнению с прямой алгебраической оценкой и почти не оставляет места для ошибки.

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

• Сравнивают наборы разной полной степени. Мюрхед применим только к симметричным суммам одночленов одинаковой суммарной степени; иначе сравнение бессмысленно. Сначала проверьте однородность и при необходимости нормируйте.
• Путают мажорирование с покомпонентным сравнением. Условие $a \succ b$ - это про частичные суммы отсортированных наборов, а не про неравенства $a_i \ge b_i$ покоординатно.
• Применяют к несимметричным выражениям. Если в неравенстве есть фиксированный порядок переменных (как $x^2 y$ без полной симметрии), напрямую Мюрхед не работает - нужна симметризация или другой метод.
• Забывают про неотрицательность переменных. Формулировка требует $x_i \ge 0$; при отрицательных значениях дробные показатели и сам вывод теряют смысл.
• Считают мажорирование достаточным для строгого неравенства всегда. Равенство возможно при равных переменных, поэтому в задачах на минимум точку равенства нужно отдельно указывать.

FAQ

Чем неравенство Мюрхеда отличается от AM-GM? AM-GM - это частный случай Мюрхеда для наборов $(1, 0, \dots, 0)$ и $(\tfrac1n, \dots, \tfrac1n)$. Мюрхед же сравнивает любые два набора показателей одинаковой степени, связанные мажорированием, поэтому покрывает целое семейство неравенств о средних.

Можно ли применять Мюрхеда к нецелым показателям? Да. Набор показателей может состоять из любых неотрицательных вещественных чисел; важно лишь равенство полных сумм и выполнение условий мажорирования по частичным суммам. Дробные показатели как раз дают средние степенные.

Что делать, если мажорирования между наборами нет? Тогда напрямую Мюрхед неприменим. Часто помогает разложить разность в сумму квадратов (метод SOS), нормировать неравенство дополнительным условием или применить Мюрхеда к промежуточным наборам и сложить полученные оценки.

Коротко

Неравенство Мюрхеда сравнивает симметричные суммы одночленов: если набор показателей $a$ мажорирует набор $b$ (одинаковая полная степень, все частичные суммы старшего набора не меньше), то $[a] \ge [b]$. Это критериальное условие, обобщающее AM-GM, доказывается усреднением по перестановкам через преобразования Робина–Худа, а равенство достигается лишь при равных переменных. На практике неравенство раскрывают до симметричных сумм, проверяют мажорирование наборов и при его наличии получают оценку напрямую.