Transinerovita

Permutační nerovnost nebo nerovnost o jednomonotónních sekvencích nebo „ trans- nerovnost “ říká, že tečkový součin dvou sad čísel je maximální možný, pokud jsou množiny jednomonotónní (to znamená, že obě jsou současně neklesající). nebo současně nerostoucí) a nejmenší možnou, pokud jsou množiny opačné monotonie (pak jedna je neklesající a druhá nerostoucí).

Jinými slovy, if a , pak pro libovolnou permutaci čísel platí následující nerovnost: $x_1\leqslant x_2 \leqslant \tečky\leqslant x_n$ $y_1\leqslant y_2 \leqslant \tečky\leqslant y_n$ $\sigma$ $\{1,2,\tečky,n\}$

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

Zejména pokud , pak bez ohledu na pořadí . $y_{i}=x_{i}$ $x_{1}x_{\sigma (1)}+\tečky +x_{n}x_{\sigma (n)}\leq {x_{1}}^{2}+\tečky {x_{n }}^{2}$ $x_{1},\tečky ,x_{n}$

Důsledkem permutační nerovnosti je Čebyševova nerovnost pro součty .

Důkaz

Označme . Pro důkaz je vhodné tvrzení poněkud přeformulovat: $V(\sigma )=\sum \limits _{i=1}^{n}{x_{i}y_{\sigma (i)))$

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

Zde je množina všech možných permutací a je totožná permutace . $S_{n}$ $\sigma _{0}:\x\mapsto x$

Hlavní myšlenkou důkazu je, že pokud pro některé , pak prohozením hodnot a nesnížíme hodnotu součtu . $\sigma (i)>\sigma (j)$ $i<j$ $\sigma (i)$ $\sigma (j)$ $V(\sigma )$

Zvažte uvedený součet pro nějakou permutaci a takový pár . Zvažte permutaci vytvořenou z inverzí tohoto páru. ${\displaystyle \sigma \not =\sigma _{0))$ $i,j$ $\sigma$

\sigma ':x\mapsto \left\{{\begin{matrix}\sigma (j),&x=i,\\\sigma (i),&x=j,\\\sigma (x), &x\ne \in \{{i,j}\}.\end{matrix}}\vpravo.

Podle definice,

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)})

Volbou a předpokladem uspořádání je nerovnost pravdivá , takže . $i,j$ $x, y$ $(x_{j}-x_{i})(y_{\sigma (i)}-y_{\sigma (j)})\geq 0$ $V(\sigma ')\geq V(\sigma )$

Proto můžeme snížit počet inverzí, aniž bychom snížili hodnotu (například fixací inverzí v bublinovém řazení ). V důsledku toho takový proces povede k transformaci na , takže . $V(\sigma )$ $\sigma$ $\sigma _{0}$ $V(\sigma )\leq V(\sigma _{0})$

Zobecnění

Pro více permutací

Nechat dané uspořádané sekvence . Označme . Identická permutace bude stále označena jako . $s$ $x_{1}^{(i)}\leq x_{2}^{(i)}\leq \dots \leq x_{n}^{(i)},\ i=1,\tečky , s$ ${\displaystyle V(\sigma _{1},\tečky ,\sigma _{s})=x_{\sigma _{1}(1)}^{(1)}x_{\sigma _{2}( 1)}^{(2)}\tečky x_{\sigma _{s}(1)}^{(s)}+\tečky +x_{\sigma _{1}(n)}^{(1) }x_{\sigma _{2}(n)}^{(2)}\tečky x_{\sigma _{s}(n)}^{(s)))$ $\sigma _{0}$

Pak pro jakoukoli sadu . $V(\sigma _{1},\tečky ,\sigma _{s})\leq V(\sigma _{0},\tečky ,\sigma _{0})$ $(\sigma _{1},\tečky ,\sigma _{s})$

Důkaz

Dokazuje se podobně jako obvyklá permutační nerovnost (speciální případ pro ). $s=2$

Bez ztráty obecnosti budeme předpokládat, že , protože jinak můžeme jednoduše vynásobit všechny permutace beze změny hodnoty součtu. $\sigma _{1}=\sigma _{0}$ ${\displaystyle \sigma _{1}^{-1))$

Pokud je alespoň jedna z permutací odlišná od , pak pro ni (označujeme ji ) existuje taková, že . ${\displaystyle \sigma _{1},\tečky ,\sigma _{s))$ $\sigma _{0}$ ${\displaystyle \sigma _{k))$ $i<j$ $\sigma _{k}(i)>\sigma _{k}(j)$

Pak, pokud ve všech permutacích z množiny, pro kterou jsou hodnoty \sigma (i) > \sigma (j) zaměněny , pak se hodnota nesníží, ale celkový počet inverzí mezi nimi se sníží. $\sigma$ $(\sigma _{1},\tečky ,\sigma _{s})$ $\sigma (i)$ $\sigma (j)$ $PROTI$ $(\sigma _{1},\tečky ,\sigma _{s})$

Provedením takových akcí nezbytným (konečným) počtem opakování se dostaneme k množině, aniž bychom snížili hodnotu . $(\sigma _{0},\tečky ,\sigma _{0})$ $PROTI$

Pro konvexní funkce

Myšlenka důkazu pomocí postupné korekce inverzí je použitelná pro širší třídu případů, než je pouze bodový součin.

Dovolit být konvexní funkce , a být uspořádány v non-klesající pořadí. Pak $F$ $X$ $y$

f(x_{1}+y_{\sigma (1)})+\tečky +f(x_{n}+y_{\sigma (n)})\leq f(x_{1}+y_{ 1})+\tečky f(x_{n}+y_{n})

Důkaz

Podle definice konvexní funkce, if , then , to je . Dosazením a přičtením obou hodnot dostaneme . Jinými slovy, čím větší je argument, tím větší je ohyb funkce směrem nahoru a tím cennější je přidat větší hodnotu, aby se maximalizoval součet. $x_{1}<x_{2},\ c>0$ $f(x_{1}+c)-f(x_{1})\leq f(x_{2}+c)-f(x_{2})$ $f(x_{1}+c)+f(x_{2})\leq f(x_{1})+f(x_{2}+c)$ ${\displaystyle c=c_{2}-c_{1))$ ${\displaystyle x_{1},x_{2))$ $c_{1}$ $f(x_{1}+c_{2})+f(x_{2}+c_{1})\leq f(x_{1}+c_{1})+f(x_{2}+ c_{2})$

Jako v důkazu obvyklé permutační nerovnosti volíme takovou, že . $i<j$ $\sigma (i)>\sigma (j)$

Poté, jak je popsáno výše, . To nám umožňuje provést indukci podobnou obvyklému případu. $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)})$

Vynásobením všech hodnot pomocí můžeme odvodit podobnou nerovnost, ale se znaménkem v opačném směru pro konkávní funkce . $F$ $-jeden$

Důsledky

for (konvexní funkce): obvyklá permutační nerovnost pro množiny a $f(x)=e^{x}$ $e^{x_{1)),\tečky ,e^{x_{n))$ $e^{y_{1}},\tečky ,e^{y_{n}}$

at (konvexní funkce): $f(x)=x^{2}$ $\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})}$

Po zmenšení obou částí o , opět získáme obvyklou permutační nerovnost. ${\displaystyle \sum \limits _{i=1}^{n}{(x_{i}^{2}+y_{i}^{2)))))$

pro (konkávní funkce): ${\displaystyle f(x)=\log {x))$ $\sum \limits _{i=1}^{n}{\ln(x_{i}+y_{\sigma (i)})}\geq \sum \limits _{i=1}^{ n}{\ln(x_{i}+y_{i})}$

Po převzetí exponentu z obou částí: ; $\prod _{i=1}^{n}{(x_{i}+y_{\sigma (i)})}\geq \prod _{i=1}^{n}{(x_{ i}+y_{i})}$

pro (konkávní funkce): $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))))$

Neúspěšné pokusy o zobecnění

V roce 1946 byl publikován pokus (Scripta Mathematica 1946, 12(2), 164-169) zobecnit nerovnost takto:

For a dvě sady reálných čísel a , $n\ge 3$ $x_1\leqslant\cdots\leqslant x_n$ $y_1\leqslant\cdots\leqslant y_n$

x_1 y_{\sigma (1)} + \cdots + x_n y_{\sigma (n)} \leqslant x_1 y_{\pi(1)} + \cdots + x_n y_{\pi(n)}

pokud je počet inverzí v permutaci menší než v permutaci . $\pi$ $\sigma$

Později se však ukázalo, že toto zobecnění platí pouze pro . Protože pro toto zobecnění existují protipříklady, jako například: $n=3$ $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.}

Důsledky

Permutační nerovnost je zajímavá tím, že umožňuje intuitivně kombinovat na společném základě navenek zcela nepodobné číselné nerovnosti používané v různých oblastech matematiky.

Tato část se zabývá sadami čísel délek a předpokládá, že zápis pro označuje , tedy indexové smyčky. $n$ $x_{i}$ $i>n$ ${\displaystyle x_{in))$

Cauchyho-Bunyakovského nerovnost

Podle permutační nerovnosti pro libovolné , . $k$ $\sum \limits _{i=0}^{n-1}{a_{i}a_{i+k}}\leq \sum \limits _{i=0}^{n-1}{ a_{i}^{2}}$

Z toho je odvozen zvláštní případ Cauchy-Bunyakovského nerovnosti:

\left({\sum \limits _{i=0}^{n-1}{a_{i))}\right)^{2}=\sum \limits _{i=0}^{ n-1}\součet \limits _{j=0}^{n-1}{a_{i}a_{j}}=\součet \limits _{i=0}^{n-1}\součet \ limity _{j=0}^{n-1}{a_{i}a_{i+j}}\leq \sum \limits _{j=0}^{n-1}{\součet \limits _{ i=1}^{n}{a_{i}^{2}}}=n\součet \limits _{i=1}^{n}{a_{i}^{2}}

Podobně, rozdělením součtu přes všechny možné posuny -rozměrného indexu a použitím zobecnění přes několik permutací se získá obecnější nerovnost pro celá čísla : ${\displaystyle n^{k-1))$ $(k-1)$ $k$

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

Obecná Cauchy-Bunyakovského nerovnost

2(a_{1}b_{1}+\tečky +a_{n}b_{n})=a_{1}b_{1}+\tečky +a_{n}b_{n}+b_{ 1}a_{1}+\tečky +b_{n}a_{n}\leq a_{1}^{2}+\tečky +a_{n}^{2}+b_{1}^{2}+ \dots +b_{n}^{2}

Pokud jsou hodnoty a normalizovány takovým způsobem, že v důsledku toho se získá Cauchy-Bunyakovského nerovnost. K tomu stačí vydělit vše , a vše . Vzhledem k tomu, že nerovnost Cauchy-Bunyakovského umožňuje taková rozdělení, aniž by se změnila pravda, toto tvrzení potvrzuje. $a_{i}$ $bi}$ $a_{1}^{2}+\tečky +a_{n}^{2}=b_{1}^{2}+\tečky +b_{n}^{2}=1$ $a_{i}$ ${\displaystyle {\sqrt {a_{1}^{2}+\dots +a_{n}^{2))))$ $bi}$ ${\displaystyle {\sqrt {b_{1}^{2}+\dots +b_{n}^{2))))$

Průměrné nerovnosti

Kvadratická a aritmetika

Nerovnost mezi středním kvadratickým a aritmetickým průměrem je elementárně odvozena z konkrétního případu Cauchy-Bunyakovského nerovnosti dokázaného výše.

Aritmetika a geometrická

Nerovnost mezi aritmetickým a geometrickým průměrem to říká

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

Vynásobením obou částí a uvážením tých mocnin proměnných vidíme, že je to stejné jako $n$ $n$

{\displaystyle nx_{1}\tečky x_{n}\leq x_{1}^{n}+\tečky x_{n}^{n))

x_{1}x_{2}\tečky x_{n-1}x_{n}+x_{2}x_{3}\tečky x_{n}x_{1}+\tečky +x_{n} x_{1}\tečky x_{n-2}x_{n-1}\leq x_{1}^{n}+\tečky x_{n}^{n}

Poslední nerovnost lze snadno získat zobecněním permutační nerovnosti na několik permutací pro $\sigma _{k}(i)=i+(k-1)$

Geometrické a harmonické

Přivedeme nerovnost do stejného tvaru jako předchozí:

{\sqrt[{n}]{x_{1}\tečky x_{n))}\geq {\frac {n}({\frac {1}{x_{1))}+\tečky { \frac {1}{x_{n}}}}}

{\frac {1}{x_{1}}}+\tečky {\frac {1}{x_{n}}}\geq {\frac {n}{\sqrt[{n}]{x_ {1}\dots x_{n}}}}

Uvážíme -li th mocniny proměnných, dostaneme $n$

n\left({\frac {1}{x_{1))}\right)\tečky \left({\frac {1}{x_{n))}\right)\leq \left({ \frac {1}{x_{1}}}\right)^{n}+\tečky \left({\frac {1}{x_{n}}}\right)^{n}

Poslední nerovnost lze snadno získat přímou aplikací permutační nerovnosti pro několik permutací.

Odkazy

L. V. Radzivilovský. Zobecnění permutační nerovnosti a mongolské nerovnosti // Matematické vzdělávání . - 2006. - č. 10 .
V. I. Muraško, S. M. Gorskij, Ya. I. Sandrygailo. KφKψ-konvexní funkce a zobecnění klasických nerovnic // PFMT. - 2018. - Vydání. 37 , č. 4 . — S. 98–102 .
Yue Kwok Choy, Nerovnost přeskupení