Транснеравенство , также известное как перестановочное неравенство или неравенство об одномонотонных последовательностях , утверждает, что скалярное произведение двух наборов чисел является максимально возможным, если наборы одномонотонны (то есть оба одновременно неубывающие или одновременно невозрастающие), и минимально возможным, если наборы противоположной монотонности (то есть один неубывающий, а другой невозрастающий).
Другими словами, если
x
1
⩽
x
2
⩽
⋯
⩽
x
n
{\displaystyle x_{1}\leqslant x_{2}\leqslant \dots \leqslant x_{n}}
и
y
1
⩽
y
2
⩽
⋯
⩽
y
n
{\displaystyle y_{1}\leqslant y_{2}\leqslant \dots \leqslant y_{n}}
, то для произвольной перестановки
σ
{\displaystyle \sigma }
чисел
{
1
,
2
,
…
,
n
}
{\displaystyle \{1,2,\dots ,n\}}
выполняется неравенство:
x
1
y
n
+
x
2
y
n
−
1
+
⋯
+
x
n
y
1
⩽
x
1
y
σ
(
1
)
+
x
2
y
σ
(
2
)
+
⋯
+
x
n
y
σ
(
n
)
⩽
x
1
y
1
+
x
2
y
2
+
⋯
+
x
n
y
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}}
В частности, если
y
i
=
x
i
{\displaystyle y_{i}=x_{i}}
, то
x
1
x
σ
(
1
)
+
⋯
+
x
n
x
σ
(
n
)
≤
x
1
2
+
…
x
n
2
{\displaystyle x_{1}x_{\sigma (1)}+\dots +x_{n}x_{\sigma (n)}\leq {x_{1}}^{2}+\dots {x_{n}}^{2}}
независимо от упорядочивания
x
1
,
…
,
x
n
{\displaystyle x_{1},\dots ,x_{n}}
.
Следствием перестановочного неравенства является неравенство Чебышёва для сумм .
Доказательство
править
Обозначим
V
(
σ
)
=
∑
i
=
1
n
x
i
y
σ
(
i
)
{\displaystyle V(\sigma )=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)}}}
. Для доказательства удобно несколько переформулировать утверждение:
arg
max
σ
∈
S
n
V
(
σ
)
=
σ
0
{\displaystyle \arg \max \limits _{\sigma \in S_{n}}{V(\sigma )}=\sigma _{0}}
Здесь
S
n
{\displaystyle S_{n}}
— множество всех возможных перестановок , а
σ
0
:
x
↦
x
{\displaystyle \sigma _{0}:\ x\mapsto x}
— тождественная перестановка .
Основная идея доказательства состоит в том, что если
σ
(
i
)
>
σ
(
j
)
{\displaystyle \sigma (i)>\sigma (j)}
для некоторых
i
<
j
{\displaystyle i<j}
, то, поменяв местами значения
σ
(
i
)
{\displaystyle \sigma (i)}
и
σ
(
j
)
{\displaystyle \sigma (j)}
, мы не уменьшим значение суммы
V
(
σ
)
{\displaystyle V(\sigma )}
.
Рассмотрим указанную сумму для некоторой перестановки
σ
≠
σ
0
{\displaystyle \sigma \not =\sigma _{0}}
и такой пары
i
,
j
{\displaystyle i,j}
. Рассмотрим перестановку, образуемую из
σ
{\displaystyle \sigma }
инверсий этой пары.
σ
′
:
x
↦
{
σ
(
j
)
,
x
=
i
,
σ
(
i
)
,
x
=
j
,
σ
(
x
)
,
x
∉
{
i
,
j
}
.
{\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.}
По определению,
V
(
σ
′
)
=
V
(
σ
)
−
x
i
y
σ
(
i
)
−
x
j
y
σ
(
j
)
+
x
i
y
σ
(
j
)
+
x
j
y
σ
(
i
)
=
V
(
σ
)
+
(
x
j
−
x
i
)
(
y
σ
(
i
)
−
y
σ
(
j
)
)
{\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)})}
Согласно выбору
i
,
j
{\displaystyle i,j}
и предположению об упорядоченности
x
,
y
{\displaystyle x,y}
, справедливо неравенство
(
x
j
−
x
i
)
(
y
σ
(
i
)
−
y
σ
(
j
)
)
≥
0
{\displaystyle (x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})\geq 0}
, так что
V
(
σ
′
)
≥
V
(
σ
)
{\displaystyle V(\sigma ')\geq V(\sigma )}
.
Следовательно, мы можем уменьшать число инверсий , не уменьшая значения
V
(
σ
)
{\displaystyle V(\sigma )}
(например, исправляя инверсии в порядке сортировки пузырьком ). В итоге такой процесс приведёт к превращению
σ
{\displaystyle \sigma }
в
σ
0
{\displaystyle \sigma _{0}}
, так что
V
(
σ
)
≤
V
(
σ
0
)
{\displaystyle V(\sigma )\leq V(\sigma _{0})}
.
Для нескольких перестановок
править
Пусть даны
s
{\displaystyle s}
упорядоченных последовательностей
x
1
(
i
)
≤
x
2
(
i
)
≤
⋯
≤
x
n
(
i
)
,
i
=
1
,
…
,
s
{\displaystyle x_{1}^{(i)}\leq x_{2}^{(i)}\leq \dots \leq x_{n}^{(i)},\ i=1,\dots ,s}
. Обозначим
V
(
σ
1
,
…
,
σ
s
)
=
x
σ
1
(
1
)
(
1
)
x
σ
2
(
1
)
(
2
)
…
x
σ
s
(
1
)
(
s
)
+
⋯
+
x
σ
1
(
n
)
(
1
)
x
σ
2
(
n
)
(
2
)
…
x
σ
s
(
n
)
(
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)}}
. Тождественную перестановку по-прежнему будет обозначать как
σ
0
{\displaystyle \sigma _{0}}
.
Тогда
V
(
σ
1
,
…
,
σ
s
)
≤
V
(
σ
0
,
…
,
σ
0
)
{\displaystyle V(\sigma _{1},\dots ,\sigma _{s})\leq V(\sigma _{0},\dots ,\sigma _{0})}
для любого набора
(
σ
1
,
…
,
σ
s
)
{\displaystyle (\sigma _{1},\dots ,\sigma _{s})}
.
Доказывается аналогично обычному перестановочному неравенству (частному случаю этого при
s
=
2
{\displaystyle s=2}
).
Не ограничивая общности, будем предполагать, что
σ
1
=
σ
0
{\displaystyle \sigma _{1}=\sigma _{0}}
, поскольку иначе можно просто умножить все перестановки на
σ
1
−
1
{\displaystyle \sigma _{1}^{-1}}
, не изменив значение суммы.
Если хотя бы одна из перестановок
σ
1
,
…
,
σ
s
{\displaystyle \sigma _{1},\dots ,\sigma _{s}}
отлична от
σ
0
{\displaystyle \sigma _{0}}
, то для неё (обозначим её
σ
k
{\displaystyle \sigma _{k}}
) существуют
i
<
j
{\displaystyle i<j}
такие, что
σ
k
(
i
)
>
σ
k
(
j
)
{\displaystyle \sigma _{k}(i)>\sigma _{k}(j)}
.
Тогда, если во всех перестановках
σ
{\displaystyle \sigma }
из набора
(
σ
1
,
…
,
σ
s
)
{\displaystyle (\sigma _{1},\dots ,\sigma _{s})}
, для которых \sigma (i) > \sigma (j), поменять местами значения
σ
(
i
)
{\displaystyle \sigma (i)}
и
σ
(
j
)
{\displaystyle \sigma (j)}
, то значение
V
{\displaystyle V}
не уменьшиться, а общее количество инверрсий среди
(
σ
1
,
…
,
σ
s
)
{\displaystyle (\sigma _{1},\dots ,\sigma _{s})}
станет меньше.
Производя такие действия нужное (конечное) количество раз, придём к набору
(
σ
0
,
…
,
σ
0
)
{\displaystyle (\sigma _{0},\dots ,\sigma _{0})}
, не уменьшив значение
V
{\displaystyle V}
.
Для выпуклых функций
править
Идея доказательства через пошаговое исправление инверсий применима для более широкого класса случаев, чем просто для скалярного произведения.
Пусть
f
{\displaystyle f}
— выпуклая функция ,
x
{\displaystyle x}
и
y
{\displaystyle y}
упорядочены по неубыванию. Тогда
f
(
x
1
+
y
σ
(
1
)
)
+
⋯
+
f
(
x
n
+
y
σ
(
n
)
)
≤
f
(
x
1
+
y
1
)
+
…
f
(
x
n
+
y
n
)
{\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})}
По определению выпуклой функции, если
x
1
<
x
2
,
c
>
0
{\displaystyle x_{1}<x_{2},\ c>0}
, то
f
(
x
1
+
c
)
−
f
(
x
1
)
≤
f
(
x
2
+
c
)
−
f
(
x
2
)
{\displaystyle f(x_{1}+c)-f(x_{1})\leq f(x_{2}+c)-f(x_{2})}
, то есть
f
(
x
1
+
c
)
+
f
(
x
2
)
≤
f
(
x
1
)
+
f
(
x
2
+
c
)
{\displaystyle f(x_{1}+c)+f(x_{2})\leq f(x_{1})+f(x_{2}+c)}
. Подствляя
c
=
c
2
−
c
1
{\displaystyle c=c_{2}-c_{1}}
и прибавляя к обоим
x
1
,
x
2
{\displaystyle x_{1},x_{2}}
величину
c
1
{\displaystyle c_{1}}
, получаем
f
(
x
1
+
c
2
)
+
f
(
x
2
+
c
1
)
≤
f
(
x
1
+
c
1
)
+
f
(
x
2
+
c
2
)
{\displaystyle f(x_{1}+c_{2})+f(x_{2}+c_{1})\leq f(x_{1}+c_{1})+f(x_{2}+c_{2})}
. Иными словами, чем больше аргумент, тем больше изгиб функции вверх, и тем более ценнее для максимизации суммы прибавлять большее значение именно туда.
Как и в доказательстве обычного перестановочного неравенства, выберем
i
<
j
{\displaystyle i<j}
такие, что
σ
(
i
)
>
σ
(
j
)
{\displaystyle \sigma (i)>\sigma (j)}
.
Тогда, как описано выше,
f
(
x
i
+
y
σ
(
i
)
)
+
f
(
x
j
+
y
σ
(
j
)
)
≤
f
(
x
i
+
y
σ
(
j
)
)
+
f
(
x
j
+
y
σ
(
i
)
)
{\displaystyle f(x_{i}+y_{\sigma (i)})+f(x_{j}+y_{\sigma (j)})\leq f(x_{i}+y_{\sigma (j)})+f(x_{j}+y_{\sigma (i)})}
. Это позволяет провести индукцию, аналогичную обычному случаю.
Умножая все значения
f
{\displaystyle f}
на
−
1
{\displaystyle -1}
, можно вывести аналогичное неравенство, но со знаком в другую сторону, для вогнутых функций .
при
f
(
x
)
=
e
x
{\displaystyle f(x)=e^{x}}
(выпуклая функция): обычное перестановочное неравенство для наборов
e
x
1
,
…
,
e
x
n
{\displaystyle e^{x_{1}},\dots ,e^{x_{n}}}
и
e
y
1
,
…
,
e
y
n
{\displaystyle e^{y_{1}},\dots ,e^{y_{n}}}
при
f
(
x
)
=
x
2
{\displaystyle f(x)=x^{2}}
(выпуклая функция):
∑
i
n
(
x
i
2
+
2
x
i
y
σ
(
i
)
+
y
σ
(
i
)
2
)
≤
∑
i
n
(
x
i
2
+
2
x
i
y
i
+
y
i
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})}}
После сокращения обеих частей на
∑
i
=
1
n
(
x
i
2
+
y
i
2
)
{\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2})}}
, опять получаем обычное перестановочное неравенство.
при
f
(
x
)
=
log
x
{\displaystyle f(x)=\log {x}}
(вогнутая функция):
∑
i
=
1
n
ln
(
x
i
+
y
σ
(
i
)
)
≥
∑
i
=
1
n
ln
(
x
i
+
y
i
)
{\displaystyle \sum \limits _{i=1}^{n}{\ln(x_{i}+y_{\sigma (i)})}\geq \sum \limits _{i=1}^{n}{\ln(x_{i}+y_{i})}}
После взятия экспоненты от обеих частей:
∏
i
=
1
n
(
x
i
+
y
σ
(
i
)
)
≥
∏
i
=
1
n
(
x
i
+
y
i
)
{\displaystyle \prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{i}+y_{i})}}
;
при
f
(
x
)
=
1
x
{\displaystyle f(x)={\frac {1}{x}}}
(вогнутая функция):
∑
i
=
1
n
1
x
i
+
y
σ
(
i
)
≥
∑
i
=
1
n
1
x
i
+
y
i
{\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) попытка следующего обобщения неравенства:
Однако впоследствии оказалось, что это обобщение верно только для
n
=
3
{\displaystyle n=3}
. Начиная с
n
=
4
{\displaystyle n=4}
для этого обобщения существуют контрпримеры, как например:
0
⋅
0
+
1
⋅
1
+
2
⋅
10
+
3
⋅
2
=
27
<
31
=
0
⋅
2
+
1
⋅
1
+
2
⋅
0
+
3
⋅
10.
{\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.}
Перестановочное неравенство интересно тем, что позволяет интуитивно объединить на общей основой внешне совершенно непохожие, применяемые в разных областях математики, числовые неравенства.
В этом разделе рассматриваются наборы чисел длины
n
{\displaystyle n}
и подразумевается, что обозначение
x
i
{\displaystyle x_{i}}
при
i
>
n
{\displaystyle i>n}
обозначает
x
i
−
n
{\displaystyle x_{i-n}}
, то есть зацикленность индексов.
Согласно перестановочному неравенству, для любого
k
{\displaystyle k}
выполняется
∑
i
=
0
n
−
1
a
i
a
i
+
k
≤
∑
i
=
0
n
−
1
a
i
2
{\displaystyle \sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{a_{i}^{2}}}
.
Из этого выводится частный случай неравенства Коши-Буняковского:
(
∑
i
=
0
n
−
1
a
i
)
2
=
∑
i
=
0
n
−
1
∑
j
=
0
n
−
1
a
i
a
j
=
∑
i
=
0
n
−
1
∑
j
=
0
n
−
1
a
i
a
i
+
j
≤
∑
j
=
0
n
−
1
∑
i
=
1
n
a
i
2
=
n
∑
i
=
1
n
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}}}
Аналогично, разбивая сумму на
n
k
−
1
{\displaystyle n^{k-1}}
частей по всем возможным
(
k
−
1
)
{\displaystyle (k-1)}
-мерным сдвигам индексов и используя обобщение на несколько перестановок, выводится более общее неравенство для целых
k
{\displaystyle k}
:
(
∑
i
=
0
n
−
1
a
i
)
k
≤
n
k
−
1
∑
i
=
0
n
−
1
a
i
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}}}
Общее неравенство Коши-Буняковского
править
2
(
a
1
b
1
+
⋯
+
a
n
b
n
)
=
a
1
b
1
+
⋯
+
a
n
b
n
+
b
1
a
1
+
⋯
+
b
n
a
n
≤
a
1
2
+
⋯
+
a
n
2
+
b
1
2
+
⋯
+
b
n
2
{\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}}
Если нормировать значения
a
i
{\displaystyle a_{i}}
и
b
i
{\displaystyle b_{i}}
таким образом, чтобы выполнялось
a
1
2
+
⋯
+
a
n
2
=
b
1
2
+
⋯
+
b
n
2
=
1
{\displaystyle a_{1}^{2}+\dots +a_{n}^{2}=b_{1}^{2}+\dots +b_{n}^{2}=1}
, то как следствие получается неравенство Коши-Буняковского. Для этого достаточно разделить все
a
i
{\displaystyle a_{i}}
на
a
1
2
+
⋯
+
a
n
2
{\displaystyle {\sqrt {a_{1}^{2}+\dots +a_{n}^{2}}}}
, а все
b
i
{\displaystyle b_{i}}
на
b
1
2
+
⋯
+
b
n
2
{\displaystyle {\sqrt {b_{1}^{2}+\dots +b_{n}^{2}}}}
. Поскольку неравенство Коши-Буняковского допускает такие деления без изменения истинности, то это доказывает утверждение.
Квадратичное и арифметическое
править
Неравенство между средним квадратичным и средним арифметическим элементарно выводится из доказанного выше частного случая неравенства Коши-Буняковского.
Арифметическое и геометрическое
править
Неравенство между арифметическим и геометрическим средним гласит, что
x
1
…
x
n
n
≤
x
1
+
⋯
+
x
n
n
{\displaystyle {\sqrt[{n}]{x_{1}\dots x_{n}}}\leq {\frac {x_{1}+\dots +x_{n}}{n}}}
Умножая обе части на
n
{\displaystyle n}
и рассматривая
n
{\displaystyle n}
-ые степени переменных, увидим, что это то же самое, что
n
x
1
…
x
n
≤
x
1
n
+
…
x
n
n
{\displaystyle nx_{1}\dots x_{n}\leq x_{1}^{n}+\dots x_{n}^{n}}
x
1
x
2
…
x
n
−
1
x
n
+
x
2
x
3
…
x
n
x
1
+
⋯
+
x
n
x
1
…
x
n
−
2
x
n
−
1
≤
x
1
n
+
…
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}}
Последнее же неравенство легко получается из обобщения перестановочного неравенство на несколько перестановок при
σ
k
(
i
)
=
i
+
(
k
−
1
)
{\displaystyle \sigma _{k}(i)=i+(k-1)}
Геометрическое и гармоническое
править
Приведём неравенство к тому же виду, что и предыдущее:
x
1
…
x
n
n
≥
n
1
x
1
+
…
1
x
n
{\displaystyle {\sqrt[{n}]{x_{1}\dots x_{n}}}\geq {\frac {n}{{\frac {1}{x_{1}}}+\dots {\frac {1}{x_{n}}}}}}
1
x
1
+
…
1
x
n
≥
n
x
1
…
x
n
n
{\displaystyle {\frac {1}{x_{1}}}+\dots {\frac {1}{x_{n}}}\geq {\frac {n}{\sqrt[{n}]{x_{1}\dots x_{n}}}}}
Рассматривая
n
{\displaystyle n}
-ые степени переменных, получаем
n
(
1
x
1
)
…
(
1
x
n
)
≤
(
1
x
1
)
n
+
…
(
1
x
n
)
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}}
Последнее неравенство легко получить прямым применением перестановочного неравенства для нескольких перестановок.