将多项式表为SOS

hbghlyj

n元对称式$f(x_1,x_2,\cdots,x_n)$能表为SOS的必要条件是把$x_3,\cdots,x_n$都替换为$x_2$后能被$(x_1-x_2)^2$整除.

将多项式表为SOS的代码如下(弹出输入框)

1. ee = Input[]
2. moduleGroebnerBasis[polys_, vars_, cvars_, opts___] :=
3. Module[{newpols, rels, len = Length[cvars], gb, j, k, rul},
4.   rels = Flatten[Table[cvars[[j]]*cvars[[k]], {j, len}, {k, j, len}]];
5.   newpols = Join[polys, rels];
6.   gb = GroebnerBasis[newpols, Join[cvars, vars], opts];
7.   rul = Map[(# :> {}) &, rels];
8.   gb = Flatten[gb /. rul];
9.   Collect[gb, cvars]]
11. conversionMatrix[polys_, vars_] :=
12. Module[{aa, coords, pmat, len = Length[polys], newpolys, mgb, gb,
13.    convmat, fvar, rvars}, coords = Array[aa, len + 1];
14.   fvar = First[coords];
15.   rvars = Rest[coords];
16.   pmat = Transpose[Join[{polys}, IdentityMatrix[len]]];
17.   newpolys = pmat.coords;
18.   mgb = moduleGroebnerBasis[newpolys, vars, coords];
19.   gb = mgb /. Join[{fvar -> 1}, Thread[rvars -> 0]] /. 0 :> Sequence[];
20.   convmat = Select[mgb, ! FreeQ[#, fvar] &] /. fvar -> 0;
21.   {gb, convmat /.
22.     Thread[rvars -> Table[UnitVector[len, j], {j, len}]]}]
23. vars = Variables[ee];
24. diffsq = Flatten[
25.    Table[(vars[[j]] - vars[[i]])^2, {j, 2, Length[vars]}, {i, 1,
26.      j - 1}]];
27. {gb, cmat} = conversionMatrix[diffsq, vars];
28. {vec, rem} = PolynomialReduce[ee, gb, vars];
29. gvec = vec.cmat;
30. gvec.diffsq

Copy the Code

-------
对于三元情况,我们把代码中间的两行修改为
vars = {a, b, c};
diffsq = {(b - c)^2, (c - a)^2, (a - b)^2};
检验SOS定理的条件的代码如下:
{Sa,Sb,Sc}=gvec;
AllTrue[{Sb, Sb + Sc, Sb + Sa},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sa, Sa + Sb, Sa + Sc},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sc, Sc + Sb, Sa + Sc},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sa, Sb, Sc},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sa + Sb + Sc, Sa Sb + Sb Sc + Sc Sa},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sa, Sc, Sa + 2 Sb, Sc + 2 Sb},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sb, Sc, Sb + 2 Sa, Sc + 2 Sa},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sb, Sa, Sb + 2 Sc, Sa + 2 Sc},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sc, Sa, a^2 Sb + b^2 Sa},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
AllTrue[{Sb, Sa, b^2 Sa + a^2 Sb},
FindInstance[{# < 0, a >= 0, b >= 0, c >= 0}, {a, b, c}] === {} &]
-------
注意到恒等式$\sum(a-b)(a-c)(b-c)^2=0$
所以四次或以上多项式的SOS表示都不唯一
这个恒等式可以推广为$\sum(a-b)(a-c)(b-c)^2 g(a,b,c)=0$,如果g(a,b,c)是关于b,c对称的多项式.
另外$S_a(b-c)^2+S_b(c-a)^2=(S_a-k(c-a)^2)(b-c)^2+(S_b+k(b-c)^2)(c-a)^2$①
多项式的SOS表示不唯一的问题可以归结为"把0整理成SOS有多少形式"
若只考虑轮换的话就不存在①这个问题
$g(a,b,c)(b-c)^2+g(b,c,a)(c-a)^2+g(c,a,b)(a-b)^2=0$
待定系数然后解线性方程组得g为齐次二次多项式时的全部解为
$g(a,b,c)=a^2 + k b^2 - k c^2 - (2 k+1) a b +
   b c + ( 2 k-1) a c$
例如$\sum (a^2 + b^2 - c^2 - 3 a b + b c + c a) (b -c)^2=0$
g为齐次三次多项式时的全部解为$g(a,b,c)=a^3+ k_1b^3-k_1c^3+k_2a^2 b+ k_3a b^2 - (5 k_1+2 k_2+3 k_3+3)a^2 c+ (5 k_1+k_2+3 k_3+2)a b c+ (5 k_1+k_2+2 k_3+1)a c^2-(3 k_1+k_2+2 k_3+1)b^2 c -(2 k_1+k_3)b c^2 $
g为齐次四次多项式时的全部解为$a^4+ k_1 b^4-k_1 c^4 +a^3 b k_2+a^3 c (-k_2-1)+a b^2 c \left(-\frac{k_1}{2}-k_2-\frac{1}{2}\right)+a b^3 \left(-\frac{3 k_1}{2}-\frac{1}{2}\right)+a b c^2 \left(\frac{k_1}{2}+k_2+\frac{1}{2}\right)+a c^3 \left(\frac{3 k_1}{2}-\frac{1}{2}\right)+b^3 c \left(\frac{k_1}{2}+\frac{1}{2}\right)+b c^3 \left(\frac{1}{2}-\frac{k_1}{2}\right)$
然后考虑非轮换的情形:
例如$(c-a)^{2}\left(\frac{a^{2}}{2}+\frac{a c}{2}-b^{2}\right)+(b-a)^{2}\left(-\frac{a^{2}}{2}-a b+\frac{a c}{2}+c^{2}\right)+(c-b)^{2}\left(-\frac{a^{2}}{2}+a b-\frac{a c}{2}\right)=0$
0的非轮换的多项式SOS表示是否均能通过①的方法化为轮换的多项式SOS表示呢?
----------------------
sos-proof-of-the-am-gm-inequality

青青子衿

回复 1# hbghlyj

好神奇，马克一下

hbghlyj

青青子衿 发表于 2021-5-15 01:09
好神奇，马克一下

由于过了很久，都看不懂了能否解释一下1#的代码