再配置不等式

数学において、並べ替え不等式^[1]は、実数 のあらゆる選択 と数のあらゆる 順列に対して、$${\displaystyle x_{1}\leq \cdots \leq x_{n}\quad {\text{ および }}\quad y_{1}\leq \cdots \leq y_{n}}$$ ${\displaystyle \sigma}$${\displaystyle 1,2,\ldots n}$

非公式には、これらのタイプの合計では、大きな値と大きな値を組み合わせることで最大の合計が達成され、小さな値と大きな値を組み合わせることで最小の合計が達成されることを意味します。これは、が異なる 場合に形式化することができ、次のようになります。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle x_{1},}$

1. （ 1 ）の上限は、の順序を保つ順列に対してのみ達成される。つまり、は等しい -値の添え字を順列化できる。 の場合、すべての順列は の順序を保つ。ならば、そのような順列は恒等順列だけである。${\displaystyle \sigma}$${\displaystyle y_{1},\ldots ,y_{n},}$$${\displaystyle y_{\sigma (1)}\leq \cdots \leq y_{\sigma (n)},}$$${\displaystyle (y_{1},\ldots ,y_{n})=(y_{\sigma (1)},\ldots ,y_{\sigma (n)}).}$${\displaystyle \sigma}$${\displaystyle y}$${\displaystyle y_{1}=\cdots =y_{n}}$${\displaystyle y_{1},\ldots ,y_{n}.}$${\displaystyle y_{1}<\cdots <y_{n},}$${\displaystyle \sigma}$
2. 同様に、( 1 )の下限は、の順序を逆にする順列に対してのみ達成され、つまり、すべてに対してが、これを実現する唯一の順列であることを意味する。${\displaystyle \sigma}$${\displaystyle y_{1},\ldots ,y_{n},}$$${\displaystyle y_{\sigma (1)}\geq \cdots \geq y_{\sigma (n)}.}$$${\displaystyle y_{1}<\cdots <y_{n},}$${\displaystyle \sigma (i)=n-i+1}$${\displaystyle i=1,\ldots ,n,}$

再配置不等式( 1 )は算術幾何平均不等式などの不等式とは異なり、実数の符号に関して何の仮定もしていないことに注意する。

算術平均-幾何平均不等式、コーシー-シュワルツの不等式、チェビシェフの和不等式など、多くの重要な不等式は並べ替え不等式によって証明できます。

簡単な例として、実数を考えてみましょう。( 1 )をすべて の場合に適用すると、 ${\displaystyle x_{1}\leq \cdots \leq x_{n}}$${\displaystyle y_{i}:=x_{i}}$${\displaystyle i=1,\ldots ,n,}$$${\displaystyle x_{1}x_{n}+\cdots +x_{n}x_{1}\leq x_{1}x_{\sigma (1)}+\cdots +x_{n}x_{\sigma (n)}\leq x_{1}^{2}+\cdots +x_{n}^{2}}$$${\displaystyle \sigma}$${\displaystyle 1,\ldots ,n.}$

並べ替え不等式は、次のように直感的に理解できます。10 ドル札の山、20 ドル札の山、さらに 100 ドル札の山があるとします。好きな山から 7 枚取り、その後山を消すことができます。2 回目のラウンドでは、別の山から 5 枚取り、その後山を消すことができます。最後のラウンドでは、最後の山から 3 枚取ります。利益を最大化するには、どの順番で山を選びますか。明らかに、最も良い方法はドルを稼ぐことです。これは、並べ替え不等式 ( 1 )の上限がシーケンスとに対して示していることとまったく同じです。この意味で、これは貪欲アルゴリズムの例として考えることができます。 ${\displaystyle 7\cdot 100+5\cdot 20+3\cdot 10}$${\displaystyle 3<5<7}$${\displaystyle 10<20<100.}$

と仮定し、幅と高さの長方形を幅の列と高さの行に分割して、小さな長方形を作成します。各列から 1 つ、各行から 1 つ、これらの長方形を取ります。並べ替え不等式 ( 1 ) は、対角線または反対角線上の長方形を取ることで、選択範囲の合計面積を最適化することを示しています。 ${\displaystyle 0<x_{1} <\cdots <x_{n}}$${\displaystyle 0<y_{1}<\cdots <y_{n}.}$${\displaystyle x_{1}+\cdots +x_{n}}$${\displaystyle y_{1}+\cdots +y_{n},}$${\displaystyle n}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle y_{1},\ldots ,y_{n},}$${\displaystyle \textstyle n^{2}}$${\displaystyle n}$

下限値とそれに対応する等式についての議論は、上限値の結果を に適用することによって得られる 。したがって、( 1 ) の上限値を証明し、等式が成立する場合を議論すれば十分である。 の順列は有限個しかないので、 ( 1 ) の中間項が最大となる順列が少なくとも 1 つ存在する。この性質を持つ順列が複数ある場合、σ は次を満たす 整数の数が最大となる順列を表すものとする。$${\displaystyle -y_{n}\leq \cdots \leq -y_{1}.}$$${\displaystyle 1,\ldots ,n,}$${\displaystyle \sigma}$$${\displaystyle x_{1}y_{\sigma (1)}+\cdots +x_{n}y_{\sigma (n)}}$$${\displaystyle i}$${\displaystyle \{1,\ldots ,n\}}$${\displaystyle y_{i}=y_{\sigma (i)}.}$

ここで、が の順序を維持しなければならないことを背理法で証明します（これで（ 1 ）の上限は終わりです。なぜなら、恒等式はその性質を持っているからです）。 が存在し、すべてのおよびに対してとなると仮定します。したがって、ギャップを埋めるため に となるが存在しなければなりません。したがって、${\displaystyle \sigma}$${\displaystyle y_{1},\ldots ,y_{n}}$${\displaystyle j\in \{1,\ldots ,n-1\}}$${\displaystyle y_{i}=y_{\sigma (i)}}$${\displaystyle i\in \{1,\ldots ,j-1\}}$${\displaystyle y_{j}\neq y_{\sigma (j)}.}$${\displaystyle y_{j}<y_{\sigma (j)}}$${\displaystyle k\in \{j+1,\ldots ,n\}}$${\displaystyle y_{j}=y_{\sigma (k)}}$

これは、

この製品を拡張して並べ替えると、

これは（ 3 ）と同等である。したがって、値を交換すること によって生じる順列は 、少なくとも1つの追加点を持ち、その点が と比較して順序を維持し、つまり を満たし、また（ 4）により（ 1）で最大値に達する。これは、$${\displaystyle \tau (i):={\begin{cases}\sigma (i)&{\text{for }}i\in \{1,\ldots ,n\}\setminus \{j,k\},\\\sigma (k)&{\text{for }}i=j,\\\sigma (j)&{\text{for }}i=k,\end{cases}}}$$${\displaystyle \sigma }$${\displaystyle \sigma (j)}$${\displaystyle \sigma (k),}$${\displaystyle \sigma ,}$${\displaystyle j}$${\displaystyle y_{j}=y_{\tau (j)},}$${\displaystyle \sigma .}$

すると、( 2 )、( 3 )、( 4 )に厳密な不等式が存在するため、最大値はの順序を維持した順列によってのみ達成され、他の順列は最適にはなり得ない。 ${\displaystyle x_{1}<\cdots <x_{n},}$${\displaystyle y_{1}\leq \cdots \leq y_{n},}$${\displaystyle \sigma }$

上で述べたように、( 1 )の上限を扱えば十分である。数学的帰納法による証明では、 次の式 から 始める。${\displaystyle n=2.}$$${\displaystyle x_{1}\leq x_{2}\quad {\text{ and }}\quad y_{1}\leq y_{2}}$$

これは次の式と同等である。

したがって、( 1 )の上限はに対して真です。 すると、 の 場合に限り、 ( 5 ) と ( 6 )で厳密な不等式が得られます。したがって、 の順序を維持する唯一の順列である恒等式のみが最大値を与えます。 ${\displaystyle n=2.}$${\displaystyle x_{1}<x_{2},}$${\displaystyle y_{1}<y_{2}.}$${\displaystyle y_{1}<y_{2},}$

帰納的仮説として、再配置不等式（ １ ）の上限がに対して成り立ち、 の場合、の順列がの順序を保つ場合にのみ等式が存在すると仮定する。${\displaystyle n-1}$${\displaystyle n\geq 3}$${\displaystyle x_{1}<\cdots <x_{n-1}}$${\displaystyle \sigma }$${\displaystyle 1,\ldots ,n-1}$${\displaystyle y_{1},\ldots ,y_{n-1}.}$

ここで、 （ 1 ）の真ん中で並べ替えると最大の結果が得られるような、有限個の順列からaを取ることを考えます。2つのケースがあります。 ${\displaystyle x_{1}\leq \cdots \leq x_{n}}$${\displaystyle y_{1}\leq \cdots \leq y_{n}.}$${\displaystyle \sigma }$${\displaystyle 1,\ldots ,n}$

• であり、帰納法の仮定を用いると、（ １ ）の上限は等式で真であり、の場合の順序は保たれる。${\displaystyle \sigma (n)=n,}$${\displaystyle y_{n}=y_{\sigma (n)}}$${\displaystyle \sigma }$${\displaystyle y_{1},\ldots ,y_{n-1},y_{n}}$${\displaystyle x_{1}<\cdots <x_{n}.}$
• の場合、 が存在する と の値を交換することによってから生じる順列を定義すると、2 つのサブケースが存在することになります。${\displaystyle k:=\sigma (n)<n,}$${\displaystyle j\in \{1,\dots ,n-1\}}$${\displaystyle \sigma (j)=n.}$$${\displaystyle \tau (i)={\begin{cases}\sigma (i)&{\text{for }}i\in \{1,\ldots ,n\}\setminus \{j,n\},\\k&{\text{for }}i=j,\\n&{\text{for }}i=n,\end{cases}}}$$${\displaystyle \sigma }$${\displaystyle j}$${\displaystyle n.}$

1. またはの場合、 の値のこの交換は( 1 )の中間の項には影響しません。 は同じ合計を与えるので、最初のケースを に適用することで続行できます。の場合、 の順序が の場合にのみ、置換によっての順序が維持されることに注意してください。${\displaystyle x_{k}=x_{n}}$${\displaystyle y_{k}=y_{n},}$${\displaystyle \sigma }$${\displaystyle \tau }$${\displaystyle \tau .}$${\displaystyle x_{1}<\cdots <x_{n},}$${\displaystyle \tau }$${\displaystyle y_{1},\ldots ,y_{n}}$${\displaystyle \sigma }$
2. であり、はと等価であり、 は最適ではないことが示されるので、このケースは の選択により発生しない。${\displaystyle x_{k}<x_{n}}$${\displaystyle y_{k}<y_{n},}$${\displaystyle 0<(x_{n}-x_{k})(y_{n}-y_{k}),}$${\displaystyle x_{k}y_{n}+x_{n}y_{k}<x_{k}y_{k}+x_{n}y_{n}}$${\displaystyle \sigma }$${\displaystyle \sigma .}$

単純な一般化では、より多くのシーケンスを考慮に入れます。非負の実数の有限順序シーケンス と、の 順列と、の別の順列があると仮定します。 $${\displaystyle 0\leq x_{1}\leq \cdots \leq x_{n}\quad {\text{and}}\quad 0\leq y_{1}\leq \cdots \leq y_{n}\quad {\text{and}}\quad 0\leq z_{1}\leq \cdots \leq z_{n}}$$${\displaystyle y_{\sigma (1)},\ldots ,y_{\sigma (n)}}$${\displaystyle y_{1},\dots ,y_{n}}$${\displaystyle z_{\tau (1)},\dots ,z_{\tau (n)}}$${\displaystyle z_{1},\dots ,z_{n}.}$$${\displaystyle x_{1}y_{\sigma (1)}z_{\tau (1)}+\cdots +x_{n}y_{\sigma (n)}z_{\tau (n)}\leq x_{1}y_{1}z_{1}+\cdots +x_{n}y_{n}z_{n}.}$$

標準的な並べ替え不等式（1）とは異なり、このステートメントでは数値が非負であることが必要であることに注意してください。同様のステートメントは、すべての数値が非負である任意の数のシーケンスに対しても当てはまります。

再配置不等式の別の一般化は、すべての実数 と、その導関数が 不等式を 満たす ような の連続微分可能関数の任意の選択に対して、不等式が^[2]の任意の順列 に対して成立することを述べています。 実数と実数の線形関数を取ると、標準的な再配置不等式 ( 1 ) が回復されます。 ${\displaystyle x_{1}\leq \cdots \leq x_{n}}$ ${\displaystyle f_{i}:[x_{1},x_{n}]\to \mathbb {R} }$${\displaystyle i=1,2,\ldots ,n}$${\displaystyle f'_{1},\ldots ,f'_{n}}$$${\displaystyle f'_{1}(x)\leq f'_{2}(x)\leq \cdots \leq f'_{n}(x)\quad {\text{ for all }}x\in [x_{1},x_{n}],}$$$${\displaystyle \sum _{i=1}^{n}f_{n-i+1}(x_{i})\leq \sum _{i=1}^{n}f_{\sigma (i)}(x_{i})\leq \sum _{i=1}^{n}f_{i}(x_{i})}$$ ${\displaystyle f_{\sigma (1)},\ldots ,f_{\sigma (n)}}$${\displaystyle f_{1},\ldots ,f_{n}.}$${\displaystyle y_{1}\leq \cdots \leq y_{n}}$${\displaystyle f_{i}(x):=xy_{i}}$${\displaystyle x}$${\displaystyle i=1,\ldots ,n,}$

• ハーディ・リトルウッド不等式
• チェビシェフの和不等式