计算bunching coefficient

hbghlyj

多元对称和(Symmetric sum)之间比较大小, 比如: 对任意$x,y,z\ge0$成立 $\sum_{\text {sym}}x^{2} y^{2}\ge\sum_{\text {sym}}x^{2} y z$. 一般地, 我们有:
If $s = (s_1,\cdots, s_n)$ and $t=\left(t_1, \ldots, t_n\right)$ are two nonincreasing sequences, we say that $s$ majorizes $t$ (written as $s\succ t$) if $s_1+\cdots+s_n=t_1+\cdots+t_n$ and $s_1+\cdots+s_i \geq t_1+\cdots+t_i$ for $i=1, \ldots, n$.
If $s$ and $t$ are sequences of nonnegative reals such that $s$ majorizes $t$, then
\[
\sum_{\text {sym}} x_1^{s_1} \cdots x_n^{s_n} \geq \sum_{\text {sym}} x_1^{t_1} \cdots x_n^{t_n} .
\]
证明 1. 见Kadelburg, Zoran; Đukić, Dušan; Lukić, Milivoje; Matić, Ivan (2005), "Inequalities of Karamata, Schur and Muirhead, and some applications" (PDF)
证明 2. 使用AM-GM证明. 这种技巧在 AOPS 上称为bunching.
如果 $s\succ t$, 则存在一组非负数 $k_\sigma$(称为bunching coefficient), 其中 $\sigma$ 遍历 $\{1, \ldots, n\}$ 的置换, 满足
\begin{align*}
\sum_\sigma k_\sigma&=1\\
\sum_\sigma k_\sigma\left(s_{\sigma_1}, \ldots, s_{\sigma_n}\right)&=\left(t_1, \ldots, t_n\right)
\end{align*}
使用加权AM-GM不等式:
\begin{align*}
\sum_\sigma x_1^{s_{\sigma(n)}} \cdots x_n^{s_{\sigma(n)}} &=\sum_{\sigma, \tau} k_\tau x_1^{s_{\sigma(\tau(1))}} \cdots x_n^{s_{\sigma(\tau(n))}} \\
& \geq \sum_\sigma x_1^{\sum_\tau k_\tau s_{\sigma(\tau(1))}} \cdots x_n^{\sum_\tau k_\tau s_{\sigma(\tau(n))}} \\
&=\sum_\sigma x_1^{t_{\sigma(1)}} \cdots x_n^{t_{\sigma(n)}}
\end{align*}

例子

对于 $(5,2,1)\succ(3,3,2)$, bunching coefficient不唯一, 对 $(\frac12,\frac12,0,0,\cdots)$, 可以验证:
\[
(3,3,2)=\frac12(5,1,2)+\frac12(1,5,2)
\]
对于 $(5,3,1)\succ(4,2.5,2.5)$, bunching coefficient不唯一, 比如:
$$(4,2.5,2.5)=0.125(1, 5, 3)+0.625(5, 1, 3)+0.25(3, 5, 1)$$

为了证明 bunching coefficient 的存在性, 我们先陈述几个定义和定理:
如果一个矩阵的元素均为非负, 且每列和为1, 称为 stochastic matrix 或 Markov matrix (谱半径必为1. 证明见lecture33.pdf)
如果一个矩阵和它的转置均为stochastic matrix, 称为 doubly stochastic matrix.
易知, 置换矩阵都是doubly stochastic matrix. 从而, 置换矩阵的非负线性组合都是doubly stochastic matrix. 逆命题也成立:
(Birkhoff-von Neumann theorem) 任何doubly stochastic matrix可以表示为置换矩阵的非负线性组合. 等价于, doubly stochastic matrix属于置换矩阵形成的凸包, 称为Birkhoff polytope. 这个定理可以由Hall婚姻定理证明, 参见Doubly stochastic matrix.
(Muirhead's inequality) 如果$a\prec b$, 那么存在doubly stochastic matrix使得 $a = Pb$.
由Birkhoff-von Neumann theorem推出:
(bunching coefficient的存在性) 如果$a\prec b$, 那么能够将$a$表示为$b$的全部置换的非负线性组合(称为conical combination). 等价于, 如果$a\prec b$, 那么$a$属于$b$的全部置换形成的凸包.
$n!>n+1$, 所以将$a$表示为$b$的全部置换的线性组合的系数(且要求系数和为1)是不唯一的. 所以bunching coefficient一般情况下是不唯一的, 只有“当$a$在凸包的$n$维边界上且该边界恰好有$n+1$个顶点”时才是唯一的.[比如直线上把一个点表示为2个点的线性组合, 要求系数之和为1, 是唯一的, 平面上把一个点表示为3个点的线性组合, 要求系数之和为1, 是唯一的; 在空间中, 把一个点表示为4个点的线性组合, 要求系数之和为1, 是唯一的. 点$a$在这个凸包的一条棱, 或一个三角形的面上等等, 就是唯一的]
当$n=2$时,可以画图看看:

$a_1\ge a_2,b_1\ge b_2⇒(a_1,a_2)$与$(b_1,b_2)$都在$y=x$下方
$a_1\le b_1⇒(a_1,a_2)$在$(b_1,b_2)$左边
$a_1+b_1=a_2+b_2⇒(a_2,b_2)$在直线$x+y=a_1+b_1$上
从图中看出, $(a_1,a_2)$的集合是从$(b_1,b_2)$到$\left(\frac{b_1+b_2}2,\frac{b_1+b_2}2\right)$的线段, 所以一定在$(b_1,b_2)$到$(b_2,b_1)$的线段上, 即$(b_1,b_2)$与$(b_2,b_1)$的凸包.
当$n=3$时因为$a_1+a_2+a_3=b_1+b_2+b_3$, 可以把$(a_1,a_2,a_3),(b_1,b_2,b_3)$看作平面上的点到正三角形三边的距离.

$a_1\ge a_2\ge a_3\ge0,b_1\ge b_2\ge b_3\ge0⇒(a_1,a_2,a_3)$与$(b_1,b_2,b_3)$在右图的绿色区域内
$a_1\le b_1⇒(a_1,a_2,a_3)$距离边1比$(b_1,b_2,b_3)$更近. $a_1+a_2\le b_1+b_2⇒a_3\ge b_3⇒(a_1,a_2,a_3)$距离边3比$(b_1,b_2,b_3)$更远. 因此$(a_1,a_2,a_3)$的集合为右图的褐色区域 这个区域包含于点$(b_1,b_2,b_3),(b_1,b_3,b_2)\cdots(b_3,b_2,b_1)$形成的凸包(一个凸六边形)

hbghlyj

设$\bar b=\frac{b_1+\cdots+b_n}n$.
看看$n=3$情形的图, 从正三角形中心$P(\bar b,\bar b,\bar b)$发出一条过$(a_1,a_2,a_3)$的射线, 会与六边形的某条边相交于一点$Q$. 因为$(a_1,a_2,a_3)$在线段$PQ$上, 所以可以表示为$P$与$Q$的非负线性组合. 又因为$P$与$Q$都可以表示成六个蓝点的非负线性组合, 所以$(a_1,a_2,a_3)$可以表示为六个蓝点[即$(b_1,b_2,b_3)$的全部置换]的非负线性组合.证毕.
对于一般的$n$, 如何证明 bunching coefficient 的存在性呢?
对$n$归纳, 设命题对$<n$都成立.
设$α_i=a_i-\bar b$, $B_i=b_i-\bar b$, 那么$\sum α_i=\sum B_i=0$, 且$α_i\prec B_i$[相当于$n=3$时,把正三角形的中心移到原点]. 令$A_i=tα_i(t>1)$[相当于把$(A_1,\cdots,A_n)$关于原点缩放], 那么$\sum A_i=0$ 且 $A_i\prec B_i$.
现在增大$t$直至$A_i\prec B_i$的定义中的某一个不等式变为等式[相当于$(A_1,\cdots,A_n)$到了边界上],
即存在$k∈\{1, \ldots, n\}$使
\[\left\{\begin{aligned}
A_1&\leq B_1\\
&\vdots\\
A_1+\cdots+A_{k-1} &\leq B_1+\cdots+B_{k-1}\\
A_1+\cdots+A_k &=B_1+\cdots+B_k\\
A_1+\cdots+A_{k+1} &\leq B_1+\cdots+B_{k+1}\\
&\vdots\\
A_1+\cdots+A_{n-1}&\le B_1+\cdots+B_{n-1}\\
A_1+\cdots+A_n&=B_1+\cdots+B_n(=0)\end{aligned}
\right.\]
由第$1,\cdots,k-1$个不等式及$A_1+\cdots+A_k =B_1+\cdots+B_k$知, $(A_1,\cdots,A_k)\prec(B_1,\cdots,B_k)$.
从第$k+1,\cdots,n-1$个不等式及最后一个等式两端消去$A_1+\cdots+A_k$与$B_1+\cdots+B_k$得
\[\left\{\begin{aligned}
A_{k+1} &\leq B_{k+1}\\
A_{k+1}+A_{k+2} &\leq B_{k+1}+B_{k+2}\\
&\vdots\\
A_{k+1}+\cdots+A_{n-1}&\le B_{k+1}+\cdots+B_{n-1}\\
A_{k+1}+\cdots+A_n&=B_{k+1}+\cdots+B_n\end{aligned}
\right.\]所以$(A_{k+1},\cdots,A_n)\prec(B_{k+1},\cdots,B_n)$
由归纳假设, 存在bunching coefficients $λ_σ$ 与 $μ_τ$ 使得
\begin{align*}
λ_σ\ge0,&\sum_σ λ_σ=1,\\
(A_1,\cdots,A_k)=&\sum_σλ_σ(B_{σ(1)},\cdots,B_{σ(k)})\\
μ_τ\ge0,&\sum_τ μ_τ=1,\\
(A_{k+1},\cdots,A_n)=&\sum_τμ_τ(B_{τ(k+1)},\cdots,B_{τ(n)})\\
\end{align*}
其中$σ$遍历$\{1,\cdots,k\}$的全部置换, $τ$遍历$\{k+1,\cdots,n\}$的全部置换. 因此
\[(A_1,\cdots,A_n)=\sum_{σ,τ}λ_σμ_τ(B_{σ(1)},\cdots,B_{σ(k)},B_{τ(k+1)},\cdots,B_{τ(n)})\]
把$A_i$按定义代回去, 得到
\[(α_1,\cdots,α_n)=\frac1t\sum_{σ,τ}λ_σμ_τ(B_{σ(1)},\cdots,B_{σ(k)},B_{τ(k+1)},\cdots,B_{τ(n)})\]
把$α_i,B_i$按定义代回去, 得到
\[(a_1,\cdots,a_n)=\left(1-\frac1t\sum_{σ,τ}λ_σμ_τ\right)(\bar b,\bar b,\cdots,\bar b)+\frac1t\sum_{σ,τ}λ_σμ_τ(b_{σ(1)},\cdots,b_{σ(k)},b_{τ(k+1)},\cdots,b_{τ(n)})\]
因为$\sum_σ λ_σ=\sum_τ μ_τ=1$,所以$\sum_{σ,τ}λ_σμ_τ=\sum_σ(λ_σ\sum_τ μ_τ)=\sum_σλ_σ=1$,代入上式:
\[(a_1,\cdots,a_n)=\left(1-\frac1t\right)(\bar b,\bar b,\cdots,\bar b)+\frac1t\sum_{σ,τ}λ_σμ_τ(b_{σ(1)},\cdots,b_{σ(k)},b_{τ(k+1)},\cdots,b_{τ(n)})\]
因为$t>1$,所以$1-\frac1t>0$. 最后, $(\bar b,\bar b,\cdots,\bar b)$显然可以写成$(b_1,\cdots,b_n)$的$n$个轮换的平均数. 证毕.

hbghlyj

因为证明过程中$α_i=a_i-\bar b$可为负, 需要把命题加强为对任意实数序列$(a_1,\cdots,a_n),(b_1,\cdots,b_n)$成立, 再对$n$归纳.

hbghlyj

...现在增大$t$直至$A_i\prec B_i$的定义中的某一个不等式变为等式
...

这里有一个漏洞: 如果$α_1+\cdots+α_i≤0$, 不管怎么增大$t$, 左端只会越来越小, 不会导致某一个不等式变为等式
从$n=3$的那个图来看, 应该是不会发生这种情况的: 从正三角形中心出发的射线必与六边形的边相交.
下面补上漏洞:
假设存在$i∈\{1,2,\cdots,n\}$使$α_1+\cdots+α_i≤0$, 由$α_1\ge\cdots\geα_i$知$0≥α_i$, 则$0≥a_i≥α_{i+1}≥\cdots≥α_n$, 从而$0=α_1+\cdots+α_n≤α_1+\cdots+α_i≤0$, 所以等号成立$α_1+\cdots+α_i=α_{i+1}=\cdots=α_n=0$.
但是$α_1≥\cdots≥α_i≥α_{i+1}=0$, 所以$α_1=\cdots=α_i=0$, 因此$α_1,\cdots,α_n$均为0, 因此$a_1=\cdots=a_n=\bar b$, 命题显然成立: $(b_1,\cdots,b_n)$的全部置换的平均是$(\bar b,\cdots,\bar b)$.

hbghlyj

1. f[{a_,a_},{a_,a_},{x1_,x2_}]:=x1^a x2^a;
2. f[{a1_,a2_},{b1_,b2_},{x1_,x2_}]:=x x1^b1 x2^b2+y x1^b2 x2^b1/.Solve[{b1 x+b2 y==a1,b2 x+b1 y==a2},{x,y}][[1]];
3. f[{a_,a_,a_},{b1_,b2_,b3_},{x1_,x2_,x3_}]:=(x1^b1 x2^b2 x3^b3+x1^b3 x2^b1 x3^b2+x1^b2 x2^b3 x3^b1)/3;
4. f[{a1_,a2_,a3_},{b1_,b2_,b3_},{x1_,x2_,x3_}]:=Block[{m=(b1+b2+b3)/3,α1=a1-m,α2=a2-m,α3=a3-m,B1=b1-m,B2=b2-m,B3=b3-m,t1=B1/α1,t2=(B1+B2)/(α1+α2),temp=If[t1>t2,t=t2;(x1 x2)^m f[{t α1,t α2},{B1,B2},{x1,x2}] x3^b3,t=t1;x1^b1 (x2 x3)^m f[{t α2,t α3},{B2,B3},{x2,x3}]]},Assuming[Element[{x1,x2,x3},PositiveReals],Simplify[temp]]/t+(1-1/t)f[{m,m,m},{b1,b2,b3},{x1,x2,x3}]];
5. check[expr_]:=Total[Function[a,(a/.{x1->1,x2->1,x3->1})Exponent[a,#]&/@{x1,x2,x3}]/@(List@@Expand[expr])];

Copy the Code

验证

1. f[{1,1},{2,0},{x1,x2}]

Copy the Code

输出$\frac{\text{x1}^2}{2}+\frac{\text{x2}^2}{2}$

1. f[{5,3},{6,2},{x1,x2}]

Copy the Code

输出$\frac{3 \text{x1}^6 \text{x2}^2}{4}+\frac{\text{x1}^2 \text{x2}^6}{4}$

1. {a1,a2,a3}={4,5/2,5/2};
2. {b1,b2,b3}={5,3,1};
3. f[{a1,a2,a3},{b1,b2,b3},{x1,x2,x3}]
4. check[%]=={a1,a2,a3}

Copy the Code

输出$\frac{1}{4} \text{x1}^5 \text{x2} \text{x3} \left(\text{x2}^2+\text{x3}^2\right)+\frac{1}{6} \left(\text{x1}^5\text{x2}^3 \text{x3}+\text{x1} \text{x2}^5 \text{x3}^3+\text{x1}^3 \text{x2} \text{x3}^5\right)$
True

1. {a1,a2,a3}={3,3,2};
2. {b1,b2,b3}={5,2,1};
3. f[{a1,a2,a3},{b1,b2,b3},{x1,x2,x3}]
4. check[%]=={a1,a2,a3}

Copy the Code

输出
$\frac{1}{5} \text{x1}^2 \text{x2}^2 \left(\text{x1}^3+\text{x2}^3\right) \text{x3}+\frac{1}{5} \left(\text{x1}^5\text{x2}^2 \text{x3}+\text{x1} \text{x2}^5 \text{x3}^2+\text{x1}^2 \text{x2} \text{x3}^5\right)$
True

1. {a1,a2,a3}={7/2,5/2,2};
2. {b1,b2,b3}={4,3,1};
3. f[{a1,a2,a3},{b1,b2,b3},{x1,x2,x3}]
4. check[%]=={a1,a2,a3}

Copy the Code

输出
$\frac{1}{16} \text{x1}^4 \text{x2} \text{x3} \left(7 \text{x2}^2+3 \text{x3}^2\right)+\frac{1}{8} \left(\text{x1}^4 \text{x2}^3 \text{x3}+\text{x1} \text{x2}^4 \text{x3}^3+\text{x1}^3 \text{x2} \text{x3}^4\right)$
True

1. {a1,a2,a3}={1,0,-1};
2. {b1,b2,b3}={2,-1,-1};
3. f[{a1,a2,a3},{b1,b2,b3},{x1,x2,x3}]
4. check[%]=={a1,a2,a3}

Copy the Code

输出
$\frac{2 \text{x1}^3+\text{x2}^3}{3 \text{x1} \text{x2} \text{x3}}$
True

1. {a1,a2,a3}={7/2,3,5/2};
2. {b1,b2,b3}={5,3,1};
3. f[{a1,a2,a3},{b1,b2,b3},{x1,x2,x3}]
4. check[%]=={a1,a2,a3}

Copy the Code

输出
$\frac{1}{4} \text{x1}^5 \text{x2}^3 \text{x3}+\frac{1}{4} \left(\text{x1}^5 \text{x2}^3 \text{x3}+\text{x1} \text{x2}^5 \text{x3}^3+\text{x1}^3\text{x2} \text{x3}^5\right)$
True

1. {a1,a2,a3}={1,1,1};
2. {b1,b2,b3}={5/3,2/3,2/3};
3. f[{a1,a2,a3},{b1,b2,b3},{x1,x2,x3}]
4. check[%]=={a1,a2,a3}

Copy the Code

输出
$\frac{1}{3} \left(\text{x1}^{5/3} \text{x2}^{2/3} \text{x3}^{2/3}+\text{x1}^{2/3} \text{x2}^{5/3} \text{x3}^{2/3}+\text{x1}^{2/3} \text{x2}^{2/3}\text{x3}^{5/3}\right)$
True

1. ClearAll[a1,a2,a3,b1,b2,b3];
2. list={a1,a2,a3,b1,b2,b3}/. FindInstance[{a1,a2,a3,b1,b2,b3}∈ImplicitRegion[{a1>=a2>=a3,b1>=b2>=b3,a1<=b1,a1+a2<=b1+b2,a1+a2+a3==b1+b2+b3},{a1,a2,a3,b1,b2,b3}],{a1,a2,a3,b1,b2,b3},Reals,10];
3. For[i=1,i<=10,i++,{a1,a2,a3,b1,b2,b3}=list[[i]];Print[check[f[{a1,a2,a3},{b1,b2,b3},{x1,x2,x3}]]=={a1,a2,a3},{a1,a2,a3,b1,b2,b3}]]

Copy the Code

输出(全True).
最后让$a_1,a_2,a_3$不同, $b_1,b_2,b_3$也不同, 验证一下:

1. ClearAll[a1,a2,a3,b1,b2,b3];
2. list={a1,a2,a3,b1,b2,b3}/. FindInstance[{a1,a2,a3,b1,b2,b3}∈ImplicitRegion[{a1>a2>a3,b1>b2>b3,a1<=b1,a1+a2<=b1+b2,a1+a2+a3==b1+b2+b3},{a1,a2,a3,b1,b2,b3}],{a1,a2,a3,b1,b2,b3},Reals,10];
3. For[i=1,i<=10,i++,{a1,a2,a3,b1,b2,b3}=list[[i]];Print[check[f[{a1,a2,a3},{b1,b2,b3},{x1,x2,x3}]]=={a1,a2,a3},{a1,a2,a3,b1,b2,b3}]]

Copy the Code

输出(全True).

hbghlyj

5#只验证了$n=3$的情况
如何把上述算法对任意大的$n$写成程序呢
math.stackexchange.com/questions/214948/whats … rmutation-matrices-f