Как получаются симметричные неравенстваДворянинов С. В., Ясиновый Э. А. Как получаются симметричные неравенства // Квант. — 1985. — № 7. — С. 33—36.
Текст статьиДворянинов С. В., Ясиновый Э. А. Как получаются симметричные неравенства // Квант. — 1985. — № 7. — С. 33—36.
Во многих задачниках по алгебре и анализу, на математических олимпиадах, а иногда и на экзаменах встречаются задачи, в которых требуется доказать неравенство с несколькими переменными. Самые простые из них доступны ученикам 5—6 класса. Разнообразным методам их доказательства, общим теоремам о замечательных неравенствах посвящены многочисленные математические статьи, обзоры, монографии. Немало статей о неравенствах накопилось и в портфеле нашего «Математического кружка».
В этой заметке рассказывается о теореме Мюрхеда про неравенства, связывающие симметрические многочлены специального вида (суммы всевозможных одночленов с одинаковыми показателями). Эта теорема, доказанная в 1903 году, замечательна не только своей общностью и окончательностью, но и тем, что возникающие в связи с ней комбинаторные понятия («диаграммы Юнга» и их сравнение — «мажоризация») столь же естественно появляются в различных разделах теоретической и прикладной математики, активно развивающихся в последнее время.
Введение
Мы будем заниматься неравенствами такого типа:
$$
\begin{gather*}
x^2+y^2\ge2xy,\tag1\\
x^5+y^5\ge x^3y^2+y^3x^2,\tag2\\
x^2+y^2+z^2\ge xy+yz+zx,\tag3\\
x^3+y^3+z^3\ge3xyz,\tag4\\
x^2y^2+y^2z^2+z^2x^2\ge x^2yz+y^2xz+z^2xy,\tag5\\
x^4+y^4+z^4+w^4\ge4xyzw.\tag6
\end{gather*}
$$
Эти неравенства справедливы при всех неотрицательных значениях входящих в них букв. Для случая двух переменных такие неравенства легко доказать группировкой слагаемых и разложением на множители. Докажем, например, что при любых неотрицательных $x$ и $y$ выполнено неравенство (2). Для этого рассмотрим разность
$$
x^5+y^5-x^3y^2-y^3x^2=x^3(x^2-y^2)-y^3(x^2-y^3)=(x^3-y^3)(x^2-y^2).
$$
Последнее произведение, очевидно, неотрицательно; обе скобки не меньше 0 при $x\ge y\ge 0$ и не больше $0$ при $y\ge x\ge0$.
Более трудно додуматься до симметричного доказательства неравенства с тремя или большим числом переменных. Продемонстрируем общую идею пока на одном примере (5). Здесь удобно, перенеся все члены в левую часть неравенства, умножить их на 2 и собрать в три группы:
$$
\begin{gather*}
x^2(y^2-2yz+z^2)+y^2(x^2-2xz+z^2)+z^2(x^2-2xy+y^2)=\\
=x^2(y-z)^2+y^2(x-z)^2+z^2(x-y)^2\ge0.
\end{gather*}
$$
Упражнение 1. Постарайтесь доказать неравенства (1), (3) и (6).
Чтобы научиться доказывать всевозможные неравенства такого типа и сформулировать общую теорему, необходимо познакомиться с некоторыми новыми понятиями. Сейчас мы их опишем.
Симметризация одночлена
Пусть у нас есть несколько неотрицательных переменных — для определённости, три переменных $x$, $y$ и $z$. Кроме того, пусть задан набор из такого же количества целых неотрицательных чисел, $a=(k;j;i)$, где $k\ge j\ge i$; назовём их показателями. Нарисуем таблицу из трёх квадратов и в верхнем правом углу каждого напишем соответствующий показатель. В эти квадраты впишем наши три буквы $x$, $y$, $z$ и, глядя на таблицу, напишем одночлен $x^ky^jz^i$. Теперь в ту же таблицу впишем переменные в другом порядке; получим, например, такой одночлен $y^kx^jz^i$, и т. д. (рис. 1). (Нетрудно сосчитать, сколько всего разных одночленов у нас получится. В первый квадрат можно поместить любую из трёх букв $x$, $y$, $z$ — это даёт три варианта; во второй квадрат — любую из двух оставшихся букв, так что всего имеется $3\cdot2=6$ вариантов.) Затем сложим все написанные одночлены; получившийся многочлен от трёх переменных $x$, $y$, $z$ обозначим через $T_{(k;j;i)}(x,y,z)$, или $T_a(x,y,z)$, или просто $T_a$ ($T$ — от слова «таблица»). Этот многочлен будет, как говорят, симметрическим — он не меняется при любых перестановках переменных. Степень каждого его одночлена равна $s=k+j+i$.
Рис. 1
Например,
$$
\begin{gather*}
T_{(2;1;0)}(x,y,z)=x^2y+y^2x+z^2x+x^2z+y^2z+z^2y;\\
T_{(3;1;1)}(x,y,z)=x^3yz+y^3xz+z^3xy+x^3zy+y^3zx+z^3yx=2(x^3yz+y^3zx+z^3xy);\\
T_{(2;2;2)}(x,y,z)=6x^2y^2z^2.
\end{gather*}
$$
Последние два примера показывают, что когда среди показателей есть равные, в многочлене $T_a$ можно привести подобные члены и записать его короче.
Если набор показателей $\alpha=(\alpha_1;\alpha_2;{\ldots};\alpha_n)$ состоит из $n$ чисел, то надо нарисовать таблицу с $n$ квадратами и взять $n$ переменных $x_1$, $x_2$, $\ldots$, $x_n$. При этом в многочлене $T_\alpha(x_1,{\ldots},x_n)$ до приведения подобных будет $n!=1\cdot2\cdot{\ldots}\cdot n$ одночленов.
Итак, каждому набору целых чисел $\alpha=(\alpha_1;\alpha_2;{\ldots};\alpha_n)$, где $\alpha1\ge\alpha_2\ge{\ldots}\ge\alpha_n\ge0$ соответствует многочлен $T_\alpha$ — «симметризация» одночлена с показателями $\alpha_1$, $\alpha_2$, $\ldots$, $\alpha_n$.
Будем каждый такой набор $\alpha$ изображать в виде лесенки из $n$ ступенек: высота каждой ступеньки равна соответствующему показателю, ширина — единице. Такую лесенку удобно рисовать на клетчатой бумаге; общее число клеточек — «кирпичей» $1\times1$, из которых состоит лесенка, равно $s=\alpha_1+\ldots+\alpha_n$ — степени многочлеHa $T_\alpha$. На рисунке 2 изображены лесенки, соответствующие некоторым из многочленов $T_\alpha$, встречающихся в наших неравенствах.
Рис. 2
Научное название этих лесенок, которые оказываются полезными в разных задачах комбинаторики, алгебры и анализа — «диаграммы Юнга» (см. [3]).
Упражнение 2. Напишите многочлены $T_\alpha$, и нарисуйте соответствующие им лесенки для следующих наборов $\alpha$: $(3;2)$, $(3;2;1)$, $(3;3;0;0)$, $(4;1;1;0)$, $(5;0;0;0;0)$, $(1;1;1;1;1)$.
Сравнение диаграмм Юнга
На рисунке 3 изображены пары лесенок, соответствующие неравенствам (1)—(6) из введения. Мы видим, что большему из двух многочленов соответствует более крутая лесенка: вторую, более пологую, можно получить из первой, свалив несколько кирпичей направо — вниз (см. рис. 4). Сформулируем точнее, что означают здесь слова «более крутая», — сначала для лесенок из трёх ступеней.
Рис. 3Рис. 4
Пусть $\alpha=(\alpha_1;\alpha_2;\alpha_3)$ и $\beta=(\beta_1;\beta_2;\beta_3)$ — два набора целых чисел с одинаковой суммой $s=\alpha_1+\alpha_2+\alpha_3=\beta_1+\beta_2+\beta_3$; $\alpha_1\ge\alpha_2\ge\alpha_3\ge0$ и $\beta_1\ge\beta_2\ge\beta_3\ge0$. Будем считать, что $\alpha\succ\beta$ ($\alpha$ мажорирует$\beta$), если выполнено такое условие: $\beta$ можно получить из $\alpha$, проделав несколько раз (быть может, один раз или ни одного) операцию
$$
\begin{gather*}
(k;j;i)\\
\swarrow\qquad\downarrow\qquad\searrow\\
(k-1;j+1;i)\enspace(k-1;j;i+1)\enspace(k;j-1;i+1)\tag{*}
\end{gather*}
$$
Этому условию можно придать и другую, эквивалентную форму: $\alpha\succ\beta$, если выполнены условия
$$
\left\{\begin{array}{l}
\alpha_1\ge\beta_1,\\
\alpha_1+\alpha_2\ge\beta_1+\beta_2,\\
\alpha_1+\alpha_2+\alpha_3=\beta_1+\beta_2+\beta_3.
\end{array}\right.\tag{**}
$$
Аналогично, для невозрастающих наборов целых неотрицательных чисел $\alpha=(\alpha_1;\alpha_2;{\ldots};\alpha_n)$ и $\beta=(\beta_1;\beta_2;{\ldots};\beta_n)$ будем писать $\alpha\succ\beta$, если
$$
\left\{\begin{array}{l}
\alpha_1\ge\beta_1,\\
\alpha_1+\alpha_2\ge\beta_1+\beta_2,\\
.\quad.\quad.\quad.\quad.\quad.\quad.\quad.\\
\alpha_2+\alpha_2+\ldots+\alpha_{n-1}\ge\beta_1+\beta_2+\beta_{n-1},\\
\alpha_2+\alpha_2+\ldots+\alpha_{n-1}+\alpha_n=\beta_1+\beta_2+\beta_{n-1}+\beta_n.
\end{array}\right.
$$
Например, $(4;2;1)\succ(3;2;2)$, поскольку $4\ge3$, $4+2\ge3+2$, $4+2+1=3+2+2$.
Отношение $\succ$ между наборами аналогично отношению порядка между числами: $\alpha\ge\alpha$ для любого $\alpha$; если $\alpha\ge\beta$, $\beta\ge\gamma$, то $\alpha\ge\gamma$. Однако порядок между наборами лишь частичный — бывает, что два набора с одинаковой суммой не сравнимы (см. упра жнение 6).
Упражнение 3. Проверьте, что для пар диаграмм Юнга на рис. З выполнены условия (*) и (**).
Упражнение 4. Докажите, что условия (*) и (**) эквивалентны (т. е. если выполнены неравенства (**), то набор $\beta$ можно получить из $\alpha$ «сваливанием кирпичей», и обратно).
Упражнение 5. Нарисуйте все лесенки из $s=4$ кирпичей в порядке убывания, начиная от самой крутой $(4;0;0;0)$ и кончая самой пологой $(1;1;1;1)$; то же — для лесенок из 5 кирпичей.
Упражнение 6.
Проверьте, что диаграммы Юнга $(4;1;1)$ и $(3;3;0)$ не сравнимы, — ни одна из них не мажорирует другую. Есть ли ещё такие несравнимые наборы с суммой 6?
Найдите все такие пары наборов для $s=7$.
Теорема Мюрхеда
Теперь всё готово для формулировки основной теоремы.
Пусть $\alpha=(\alpha_1;\alpha_2;{\ldots};\alpha_n)$ и $\beta=(\beta_1;\beta_2{\ldots};\beta_n)$ — два набора показателей с одинаковой суммой. Если $\alpha\succ\beta$, то при всех неотрицательных $x_1$, $x_2$, $\ldots$, $x_n$
$$
T_\alpha(x_1,x_2,{\ldots},x_n)\ge T_\beta(x_1,x_2,{\ldots},x_n).
$$
Обратно, если выполнено такое неравенство, то $\alpha\succ\beta$.
Мы не будем приводить формального доказательства теоремы в общем виде (его можно найти в книгах [1], [2] — вторая из них целиком посвящена различным вариантам отношения «мажоризации», его применениям и обобщениям), вместо этого опишем его основные идеи и продемонстрируем их на конкретных примерах.
Доказательство второй части утверждения теоремы — необходимости условия $\alpha\succ\beta$ вытекает из того простого факта, что из двух многочленов от одной переменной $t$ (с положительными старшими коэффициентами) при больших значениях больше тот, у которого больше степень (см. упражнение 8).
Рис. 5
Доказательство достаточности условия $\alpha\succ\beta$ основано на двух идеях. Первая — «сваливание кирпичей»: два набора $\alpha\succ\beta$ можно соединить цепочкой наборов так, что соседние наборы в этой цепочке отличаются лишь в двух местах, так что от каждого набора к следующему можно перейти, «свалив кирпич» с одной ступеньки на другую на соответствующей лесенке. Вторая — «симметричная группировка»: разность многочленов для соседних наборов можно записать как сумму (по всем парам переменных $x$, $y$) одинаковых групп вида
$$
(x^{p+r}y^q+y^{p+r}x^q-x^py^{q+r}-y^px^{q+r})Z
$$
(см. рис. 5), где $Z$ — произведение остальных переменных, соответствующих одинаковым показателям в соседних. наборах. Последнее выражение раскладывается на множители и, как легко видеть, при $p\ge q$, $r\ge 0$ неотрицательно. (Проверьте!)
Всё это станет понятным для тех, кто внимательно, подробно выписывая все выкладки, разберёт несколько примеров. Мы приведём два.
Неравенство между средними
Неравенство между средним арифметическим и средним геометрическим трёх неотрицательных чисел
$$
\dfrac{a_1+a_2+a_3}3\ge\!\sqrt[\scriptstyle3~]{a_1a_2a_3}
$$
после переобозначений $a_1=x^3$, $a_2=y^3$, $a_3=z^3$ превращается в неравенство (4), которое уже упоминалось выше. Покажем, как оно доказывается по способу Мюрхеда. Глядя на рисунок 4, а, мы видим, что нужно доказать два неравенства:
$$
T_{(3;0;0)}(x,y,z)\ge T_{(2;1;0)}(x,y,z)\ge T_{(1;1;1)}(x,y,z).
$$
Рассмотрим первое из них и составим разность
$$
R_1=T_{(3;0;0)}(x,y,z)-T_{(2;1;0)}(x,y,z)=2(x^3+y^3+z^3)-x^2y-y^2z-z^2x-x^2z-y^2x-z^2y.
$$
Сгруппируем теперь слагаемые по четыре по следующему принципу: для каждой пары переменных в одну группу включаются слагаемые, в которых показатели при этих переменных меняются с $(3;0)$ на $(2;1)$ (а общий показатель в наборах здесь 0 на последнем месте). Получим
$$
\begin{gather*}
R_1=(y^3+z^3-y^2z-z^2y)+(x^3+y^3-x^2y-y^2x)+(z^3+x^3-z^2x-x^2z)=\\
=(y^2-z^2)(y-z)+(x^2-y^2)(x-y)+(z^2-x^2)(z-x)\ge0
\end{gather*}
$$
при всех неотрицательных $x$, $y$, $z$.
Теперь докажем второе неравенство
$$
R_2=T_{(2;1;0)}(x,y,z)-T_{(1;1;1)}(x,y,z)=x^2y+y^2z+z^2x+x^2z+y^2z+z^2y-6xyz.
$$
Здесь в показателях общая единица на втором месте, а $(2;0)$ превращается в $(1;1)$. В соответствии с этим, получим:
$$
\begin{gather*}
R_2=x(y^2+z^2-2yz)+y(z^2+x^2-2zx)+z(y^2+z^2-2yz)=\\
=x(y-z)^2+y(z-x)^2+z(x-y)^2\ge0.
\end{gather*}
$$
Это и доказывает неравенство (4).
В этой задаче (из «Задачника «Кванта» №9, 1982) требовалось для положительных $a$, $b$, $c$ доказать неравенства
$$
a+b+c\le\dfrac{a^2+b^2}{2c}+\dfrac{b^2+c^2}{2a}+\dfrac{c^2+a^2}{2a}\le\dfrac{a^3}{bc}+\dfrac{b^3}{ac}+\dfrac{c^3}{ab}.
$$
Читатели предложили несколько различных методов их решения. Один из них — способ Мюрхеда (к другим мы надеемся вернуться в одном из следующих номеров «Кванта»). Умножив данные неравенства на $2abc$, мы приведём их к такому «мюрхедовскому» виду:
$$
\begin{gather*}
2(a^4+b^4+c^4)\ge a^3b+b^3a+b^c+c^3b+c^3a+a^3c,\tag7\\
a^3b+b^3a+b^c+c^3b+c^3a+a^3c\ge2(a^2bc+b^2ac+c^2ab).\tag8
\end{gather*}
$$
Соответствующие диаграммы Юнга изображены на рисунке 4, б. Разность левой и правой части каждого неравенства можно записать, как и выше, в виде суммы трёх групп по четыре одночлена. Экономя место, мы запишем только одну группу — две другие получаются заменой букв $a$, $b$, $c$на $b$, $a$, $a$и $c$, $a$, $b$.
Упражнение 7. Выпишите все неравенства Мюрхеда для многочленов степени 4.
Упражнение 8. Пусть $T_{(\alpha_1;\alpha_2;\alpha_3)}(x,y,z)\ge T_{(\beta_1;\beta_2;\beta_3)}(x,y,z)$ для всех неотрицательных $x$, $y$, $z$. Докажите, что тогда выполнены неравенства (**). (Указание. Рассмотрите несколько случаев: $x=y=z=t$; $x=y=t$, $z=1$; $x=t$, $y=z=1$ и сравните степени полученных многочленов от $t$.)
Упражнение 9. Докажите следующие неравенства (для неотрицательных $x$, $y$, $z$, $v$):
Упражнение 10. Выведите из теоремы Мюрхеда неравенство для средних арифметического и геометрического $n$ неотрицательных чисел.
Сколько «кирпичей» нужно свалить, чтобы от набора $(n;0;{\ldots};0)$ из $n$ чисел перейти к набору $(1;1;{\ldots};1)$?
Упражнение 11. Сформулируйте и докажите теорему Мюрхеда для любых неотрицательных (не обязательно целых) показателей.
Упражнение 12. Для некоторых наборов показателей (с чётной суммой $s$) неравенство, о котором идёт речь в теореме Мюрхеда, верно для всех, а не только для неотрицательных значений переменных. Постарайтесь описать все такие случаи.
Литература
Харди Г. Г., Литтльвуд Д. E., Полиа Г. Неравенства. — М.: ИЛ, 1948.
Маршалл А., Олкин И. Неравенства: теория мажоризации и её приложения. — M.: Мир, 1983.
Заочные математические олимпиады. — М.: Наука, 1981. — Задачи 5—9.
