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

Другими словами, если ${\displaystyle x_{1}\leqslant x_{2}\leqslant \dots \leqslant x_{n}}$ и ${\displaystyle y_{1}\leqslant y_{2}\leqslant \dots \leqslant y_{n}}$ , то для произвольной перестановки ${\displaystyle \sigma }$ чисел ${\displaystyle \{1,2,\dots ,n\}}$ выполняется неравенство:

${\displaystyle x_{1}y_{n}+x_{2}y_{n-1}+\cdots +x_{n}y_{1}\leqslant x_{1}y_{\sigma (1)}+x_{2}y_{\sigma (2)}+\cdots +x_{n}y_{\sigma (n)}\leqslant x_{1}y_{1}+x_{2}y_{2}+\cdots +x_{n}y_{n}}$

В частности, если ${\displaystyle y_{i}=x_{i}}$ , то ${\displaystyle x_{1}x_{\sigma (1)}+\dots +x_{n}x_{\sigma (n)}\leq {x_{1}}^{2}+\dots {x_{n}}^{2}}$ независимо от упорядочивания ${\displaystyle x_{1},\dots ,x_{n}}$ .

Следствием перестановочного неравенства является неравенство Чебышёва для сумм .

Доказательство

Обозначим ${\displaystyle V(\sigma )=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)}}}$ . Для доказательства удобно несколько переформулировать утверждение:

${\displaystyle \arg \max \limits _{\sigma \in S_{n}}{V(\sigma )}=\sigma _{0}}$

Здесь ${\displaystyle S_{n}}$ — множество всех возможных перестановок , а ${\displaystyle \sigma _{0}:\ x\mapsto x}$ — тождественная перестановка .

Основная идея доказательства состоит в том, что если ${\displaystyle \sigma (i)>\sigma (j)}$ для некоторых ${\displaystyle i<j}$ , то, поменяв местами значения ${\displaystyle \sigma (i)}$ и ${\displaystyle \sigma (j)}$ , мы не уменьшим значение суммы ${\displaystyle V(\sigma )}$ .

Рассмотрим указанную сумму для некоторой перестановки ${\displaystyle \sigma \not =\sigma _{0}}$ и такой пары ${\displaystyle i,j}$ . Рассмотрим перестановку, образуемую из ${\displaystyle \sigma }$ инверсий этой пары.

${\displaystyle \sigma ':x\mapsto \left\{{\begin{matrix}\sigma (j),&x=i,\\\sigma (i),&x=j,\\\sigma (x),&x\not \in \{{i,j}\}.\end{matrix}}\right.}$

По определению,

${\displaystyle V(\sigma ')=V(\sigma )-x_{i}y_{\sigma (i)}-x_{j}y_{\sigma (j)}+x_{i}y_{\sigma (j)}+x_{j}y_{\sigma (i)}=V(\sigma )+(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})}$

Согласно выбору ${\displaystyle i,j}$ и предположению об упорядоченности ${\displaystyle x,y}$ , справедливо неравенство ${\displaystyle (x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})\geq 0}$ , так что ${\displaystyle V(\sigma ')\geq V(\sigma )}$ .

Следовательно, мы можем уменьшать число инверсий , не уменьшая значения ${\displaystyle V(\sigma )}$ (например, исправляя инверсии в порядке сортировки пузырьком ). В итоге такой процесс приведёт к превращению ${\displaystyle \sigma }$ в ${\displaystyle \sigma _{0}}$ , так что ${\displaystyle V(\sigma )\leq V(\sigma _{0})}$ .

Обобщения

Для нескольких перестановок

Пусть даны ${\displaystyle s}$ упорядоченных последовательностей ${\displaystyle x_{1}^{(i)}\leq x_{2}^{(i)}\leq \dots \leq x_{n}^{(i)},\ i=1,\dots ,s}$ . Обозначим ${\displaystyle V(\sigma _{1},\dots ,\sigma _{s})=x_{\sigma _{1}(1)}^{(1)}x_{\sigma _{2}(1)}^{(2)}\dots x_{\sigma _{s}(1)}^{(s)}+\dots +x_{\sigma _{1}(n)}^{(1)}x_{\sigma _{2}(n)}^{(2)}\dots x_{\sigma _{s}(n)}^{(s)}}$ . Тождественную перестановку по-прежнему будет обозначать как ${\displaystyle \sigma _{0}}$ .

Тогда ${\displaystyle V(\sigma _{1},\dots ,\sigma _{s})\leq V(\sigma _{0},\dots ,\sigma _{0})}$ для любого набора ${\displaystyle (\sigma _{1},\dots ,\sigma _{s})}$ .

Для выпуклых функций

Идея доказательства через пошаговое исправление инверсий применима для более широкого класса случаев, чем просто для скалярного произведения.

Пусть ${\displaystyle f}$ — выпуклая функция , ${\displaystyle x}$ и ${\displaystyle y}$ упорядочены по неубыванию. Тогда

${\displaystyle f(x_{1}+y_{\sigma (1)})+\dots +f(x_{n}+y_{\sigma (n)})\leq f(x_{1}+y_{1})+\dots f(x_{n}+y_{n})}$

Умножая все значения ${\displaystyle f}$ на ${\displaystyle -1}$ , можно вывести аналогичное неравенство, но со знаком в другую сторону, для вогнутых функций .

Следствия

• при ${\displaystyle f(x)=e^{x}}$ (выпуклая функция): обычное перестановочное неравенство для наборов ${\displaystyle e^{x_{1}},\dots ,e^{x_{n}}}$ и ${\displaystyle e^{y_{1}},\dots ,e^{y_{n}}}$

• при ${\displaystyle f(x)=x^{2}}$ (выпуклая функция): ${\displaystyle \sum \limits _{i}^{n}{(x_{i}^{2}+2x_{i}y_{\sigma (i)}+y_{\sigma (i)}^{2})}\leq \sum \limits _{i}^{n}{(x_{i}^{2}+2x_{i}y_{i}+y_{i}^{2})}}$

После сокращения обеих частей на ${\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2})}}$ , опять получаем обычное перестановочное неравенство.

• при ${\displaystyle f(x)=\log {x}}$ (вогнутая функция): ${\displaystyle \sum \limits _{i=1}^{n}{\ln(x_{i}+y_{\sigma (i)})}\geq \sum \limits _{i=1}^{n}{\ln(x_{i}+y_{i})}}$

После взятия экспоненты от обеих частей: ${\displaystyle \prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{i}+y_{i})}}$ ;

• при ${\displaystyle f(x)={\frac {1}{x}}}$ (вогнутая функция): ${\displaystyle \sum \limits _{i=1}^{n}{\frac {1}{x_{i}+y_{\sigma (i)}}}\geq \sum \limits _{i=1}^{n}{\frac {1}{x_{i}+y_{i}}}}$

Неудачные попытки обобщения

В 1946 году была опубликована (Scripta Mathematica 1946, 12(2), 164—169) попытка следующего обобщения неравенства:

Для ${\displaystyle n\geq 3}$ и двух наборов вещественных чисел ${\displaystyle x_{1}\leqslant \cdots \leqslant x_{n}}$ и ${\displaystyle y_{1}\leqslant \cdots \leqslant y_{n}}$ , ${\displaystyle x_{1}y_{\sigma (1)}+\cdots +x_{n}y_{\sigma (n)}\leqslant x_{1}y_{\pi (1)}+\cdots +x_{n}y_{\pi (n)}}$ если число инверсий в перестановке ${\displaystyle \pi }$ меньше чем в перестановке ${\displaystyle \sigma }$ .

Однако впоследствии оказалось, что это обобщение верно только для ${\displaystyle n=3}$ . Начиная с ${\displaystyle n=4}$ для этого обобщения существуют контрпримеры, как например:

${\textstyle 0\cdot 0+1\cdot 1+2\cdot 10+3\cdot 2=27<31=0\cdot 2+1\cdot 1+2\cdot 0+3\cdot 10.}$

Следствия

Перестановочное неравенство интересно тем, что позволяет интуитивно объединить на общей основой внешне совершенно непохожие, применяемые в разных областях математики, числовые неравенства.

В этом разделе рассматриваются наборы чисел длины ${\displaystyle n}$ и подразумевается, что обозначение ${\displaystyle x_{i}}$ при ${\displaystyle i>n}$ обозначает ${\displaystyle x_{i-n}}$ , то есть зацикленность индексов.

Неравенство Коши — Буняковского

Согласно перестановочному неравенству, для любого ${\displaystyle k}$ выполняется ${\displaystyle \sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{a_{i}^{2}}}$ .

Из этого выводится частный случай неравенства Коши-Буняковского:

${\displaystyle \left({\sum \limits _{i=0}^{n-1}{a_{i}}}\right)^{2}=\sum \limits _{i=0}^{n-1}\sum \limits _{j=0}^{n-1}{a_{i}a_{j}}=\sum \limits _{i=0}^{n-1}\sum \limits _{j=0}^{n-1}{a_{i}a_{i+j}}\leq \sum \limits _{j=0}^{n-1}{\sum \limits _{i=1}^{n}{a_{i}^{2}}}=n\sum \limits _{i=1}^{n}{a_{i}^{2}}}$

Аналогично, разбивая сумму на ${\displaystyle n^{k-1}}$ частей по всем возможным ${\displaystyle (k-1)}$ -мерным сдвигам индексов и используя обобщение на несколько перестановок, выводится более общее неравенство для целых ${\displaystyle k}$ :

${\displaystyle \left({\sum \limits _{i=0}^{n-1}{a_{i}}}\right)^{k}\leq n^{k-1}\sum \limits _{i=0}^{n-1}{a_{i}^{k}}}$

Общее неравенство Коши-Буняковского

${\displaystyle 2(a_{1}b_{1}+\dots +a_{n}b_{n})=a_{1}b_{1}+\dots +a_{n}b_{n}+b_{1}a_{1}+\dots +b_{n}a_{n}\leq a_{1}^{2}+\dots +a_{n}^{2}+b_{1}^{2}+\dots +b_{n}^{2}}$

Если нормировать значения ${\displaystyle a_{i}}$ и ${\displaystyle b_{i}}$ таким образом, чтобы выполнялось ${\displaystyle a_{1}^{2}+\dots +a_{n}^{2}=b_{1}^{2}+\dots +b_{n}^{2}=1}$ , то как следствие получается неравенство Коши-Буняковского. Для этого достаточно разделить все ${\displaystyle a_{i}}$ на ${\displaystyle {\sqrt {a_{1}^{2}+\dots +a_{n}^{2}}}}$ , а все ${\displaystyle b_{i}}$ на ${\displaystyle {\sqrt {b_{1}^{2}+\dots +b_{n}^{2}}}}$ . Поскольку неравенство Коши-Буняковского допускает такие деления без изменения истинности, то это доказывает утверждение.

Неравенства о средних

Квадратичное и арифметическое

Неравенство между средним квадратичным и средним арифметическим элементарно выводится из доказанного выше частного случая неравенства Коши-Буняковского.

Арифметическое и геометрическое

Неравенство между арифметическим и геометрическим средним гласит, что

${\displaystyle {\sqrt[{n}]{x_{1}\dots x_{n}}}\leq {\frac {x_{1}+\dots +x_{n}}{n}}}$

Умножая обе части на ${\displaystyle n}$ и рассматривая ${\displaystyle n}$ -ые степени переменных, увидим, что это то же самое, что

${\displaystyle nx_{1}\dots x_{n}\leq x_{1}^{n}+\dots x_{n}^{n}}$

${\displaystyle x_{1}x_{2}\dots x_{n-1}x_{n}+x_{2}x_{3}\dots x_{n}x_{1}+\dots +x_{n}x_{1}\dots x_{n-2}x_{n-1}\leq x_{1}^{n}+\dots x_{n}^{n}}$

Последнее же неравенство легко получается из обобщения перестановочного неравенство на несколько перестановок при ${\displaystyle \sigma _{k}(i)=i+(k-1)}$

Геометрическое и гармоническое

Приведём неравенство к тому же виду, что и предыдущее:

${\displaystyle {\sqrt[{n}]{x_{1}\dots x_{n}}}\geq {\frac {n}{{\frac {1}{x_{1}}}+\dots {\frac {1}{x_{n}}}}}}$

${\displaystyle {\frac {1}{x_{1}}}+\dots {\frac {1}{x_{n}}}\geq {\frac {n}{\sqrt[{n}]{x_{1}\dots x_{n}}}}}$

Рассматривая ${\displaystyle n}$ -ые степени переменных, получаем

${\displaystyle n\left({\frac {1}{x_{1}}}\right)\dots \left({\frac {1}{x_{n}}}\right)\leq \left({\frac {1}{x_{1}}}\right)^{n}+\dots \left({\frac {1}{x_{n}}}\right)^{n}}$

Последнее неравенство легко получить прямым применением перестановочного неравенства для нескольких перестановок.

Ссылки

• Л. В. Радзивиловский. // Математическое Просвещение . — 2006. — № 10 .
• В. И. Мурашко, С. М. Горский, Я. И. Сандрыгайло. // ПФМТ. — 2018. — Вып. 37 , № 4 . — С. 98–102 .
• Yue Kwok Choy,