Перестановочное неравенство, или неравенство об одномонотонных последовательностях, или «транснеравенство», утверждает, что скалярное произведение двух наборов чисел является максимально возможным, если наборы одномонотонны (то есть оба одновременно неубывающие или одновременно невозрастающие), и минимально возможным, если наборы противоположной монотонности (то есть один неубывающий, а другой невозрастающий).
Другими словами, если и , то для произвольной перестановки чисел выполняется неравенство:
В частности, если , то независимо от упорядочивания .
Основная идея доказательства состоит в том, что если для некоторых , то, поменяв местами значения и , мы не уменьшим значение суммы .
Рассмотрим указанную сумму для некоторой перестановки и такой пары . Рассмотрим перестановку, образуемую из инверсий этой пары.
По определению,
Согласно выбору и предположению об упорядоченности , справедливо неравенство , так что .
Следовательно, мы можем уменьшать число инверсий, не уменьшая значения (например, исправляя инверсии в порядке сортировки пузырьком). В итоге такой процесс приведёт к превращению в , так что .
Обобщения
Для нескольких перестановок
Пусть даны упорядоченных последовательностей . Обозначим . Тождественную перестановку по-прежнему будет обозначать как .
Тогда для любого набора .
Доказательство
Доказывается аналогично обычному перестановочному неравенству (частному случаю этого при ).
Не ограничивая общности, будем предполагать, что , поскольку иначе можно просто умножить все перестановки на , не изменив значение суммы.
Если хотя бы одна из перестановок отлична от , то для неё (обозначим её ) существуют такие, что .
Тогда, если во всех перестановках из набора , для которых \sigma (i) > \sigma (j), поменять местами значения и , то значение не уменьшиться, а общее количество инверрсий среди станет меньше.
Производя такие действия нужное (конечное) количество раз, придём к набору , не уменьшив значение .
Для выпуклых функций
Идея доказательства через пошаговое исправление инверсий применима для более широкого класса случаев, чем просто для скалярного произведения.
По определению выпуклой функции, если , то , то есть . Подствляя и прибавляя к обоим величину , получаем . Иными словами, чем больше аргумент, тем больше изгиб функции вверх, и тем более ценнее для максимизации суммы прибавлять большее значение именно туда.
Как и в доказательстве обычного перестановочного неравенства, выберем такие, что .
Тогда, как описано выше, . Это позволяет провести индукцию, аналогичную обычному случаю.
Умножая все значения на , можно вывести аналогичное неравенство, но со знаком в другую сторону, для вогнутых функций.
Следствия
при (выпуклая функция): обычное перестановочное неравенство для наборов и
при (выпуклая функция):
После сокращения обеих частей на , опять получаем обычное перестановочное неравенство.
В 1946 году была опубликована (Scripta Mathematica 1946, 12(2), 164—169) попытка следующего обобщения неравенства:
Для и двух наборов вещественных чисел и ,
если число инверсий в перестановке меньше чем в перестановке .
Однако впоследствии оказалось, что это обобщение верно только для . Начиная с для этого обобщения существуют контрпримеры, как например:
Следствия
Перестановочное неравенство интересно тем, что позволяет интуитивно объединить на общей основой внешне совершенно непохожие, применяемые в разных областях математики, числовые неравенства.
В этом разделе рассматриваются наборы чисел длины и подразумевается, что обозначение при обозначает , то есть зацикленность индексов.
Согласно перестановочному неравенству, для любого выполняется .
Из этого выводится частный случай неравенства Коши-Буняковского:
Аналогично, разбивая сумму на частей по всем возможным -мерным сдвигам индексов и используя обобщение на несколько перестановок, выводится более общее неравенство для целых :
Общее неравенство Коши-Буняковского
Если нормировать значения и таким образом, чтобы выполнялось , то как следствие получается неравенство Коши-Буняковского. Для этого достаточно разделить все на , а все на . Поскольку неравенство Коши-Буняковского допускает такие деления без изменения истинности, то это доказывает утверждение.
Неравенство между средним квадратичным и средним арифметическим элементарно выводится из доказанного выше частного случая неравенства Коши-Буняковского.
Арифметическое и геометрическое
Неравенство между арифметическим и геометрическим средним гласит, что
Умножая обе части на и рассматривая -ые степени переменных, увидим, что это то же самое, что
Последнее же неравенство легко получается из обобщения перестановочного неравенство на несколько перестановок при
Геометрическое и гармоническое
Приведём неравенство к тому же виду, что и предыдущее:
Рассматривая -ые степени переменных, получаем
Последнее неравенство легко получить прямым применением перестановочного неравенства для нескольких перестановок.