多项式转化为初等对称多项式表达式的算法

.·.·.

zeroieme 发表于 2019-3-8 13:25
明白！我昨天说的是最笨的办法！
你能帮忙找文献，有什么人定义过哪个结果合理么？ 觉得有个方向 ...

你让一个统计系的学渣帮你找数学系的论文……
可能是想多了

zeroieme

.·.·. 发表于 2019-3-8 16:45
你让一个统计系的学渣帮你找数学系的论文……
可能是想多了

这里其他大佬对我的话题都没兴趣。看您热心助人，就切磋一下。

zeroieme

在解析几何的暴力计算时发现的小技巧，想总结成可靠的算法。但经过几天思考，发现往更多变量推广超出我的数学水平，希望各位老大指点 @gxqcn @wayne @mathe @hujunhua 其他没@到的老大也请赐教
下面我尽能力表达我的想法：
假设多项式\(P\left(x_1,x_2,\cdots,x_n\right)\)，此多项式\(P\left(\cdots\right)=0\)是某命题的条件。P不是\(\left\{x_1,\cdots,x_n\right\}\)的对称多项式而所求几何命题中\(\left\{x_1,\cdots,x_n\right\}\)是等价的。 比如三角形三边长a、b、c与面积S的公式。那么方程\(P\left(x_1,x_2,\cdots,x_n\right)=0\)中\(x_i\)交换也成立（这是猜想），最多包含了\(n!\)种交换方式。并且，这些交换构造出来的方程可以帮助我们降低方程的次数。

最简单的例子二元多项式
\(P(x,y)=\frac{1}{2} (P(x,y)+P(y,x))+\frac{1}{2} (P(x,y)-P(y,x))=\frac{1}{2} (P(x,y)+P(y,x))+\frac{x-y}{2}\frac{P(x,y)-P(y,x)}{x-y}\)
这里\(\frac{1}{2} (P(x,y)+P(y,x))\)我称为\(P\)的中心对称多项式，\(\frac{x-y}{2}\frac{P(x,y)-P(y,x)}{x-y}\)我称为P的一阶对称余式，它是一次非对称因子\(x-y\)与另一对称多项式\(\frac{P(x,y)-P(y,x)}{x-y}\)的乘积。并且中心对称多项式与对称余式都是原方程\(P=0\)交换后的线性组合，他们是等价方程。对称余式中的对称因子比原方程降低了次数。

zeroieme

当多项式到三元时变的复杂了。\(P(x,y,z)\)可以分成以下部分的和
\(\frac{1}{6} (P(x,y,z)+P(x,z,y)+P(y,x,z)+P(y,z,x)+P(z,x,y)+P(z,y,x))\) 中心对称多项式
\(\frac{x-y}{9}(\frac{(x-z) (y-z) (P(x,y,z)-P(y,x,z))+(x-y) (y-z) (P(x,z,y)-P(z,x,y))+(x-y) (x-z) (P(y,z,x)-P(z,y,x))}{(x-y) (x-z) (y-z)})  \)一阶对称余式
\(\frac{x-z}{9}(\frac{(x-z) (y-z) (P(x,z,y)-P(y,z,x))+(x-y) (x-z) (P(y,x,z)-P(z,x,y))+(x-y) (y-z) (P(x,y,z)-P(z,y,x))}{(x-y) (x-z) (y-z)}) \)一阶对称余式
\(\frac{y-z}{9}(\frac{(x-y) (x-z) (P(x,y,z)-P(x,z,y))+(x-y) (y-z) (P(y,x,z)-P(y,z,x))+(x-z) (y-z) (P(z,x,y)-P(z,y,x))}{(x-y) (x-z) (y-z)})\)一阶对称余式
\(\frac{1}{27} (x-y) (x+y-2 z)(\frac{(x+y-2 z) (P(x,y,z)-P(y,x,z))-(x-2 y+z) (P(x,z,y)-P(z,x,y))-(2 x-y-z) (P(y,z,x)-P(z,y,x))}{(x-y) (x-z) (y-z)}) \)二阶对称余式
\(\frac{1}{27} (y-z) (2 x-y-z)(\frac{(2 x-y-z) (P(x,y,z)-P(x,z,y))+(x-2 y+z) (P(y,x,z)-P(y,z,x))-(x+y-2 z) (P(z,x,y)-P(z,y,x))}{(x-y) (x-z) (y-z)}) \)二阶对称余式
\(-\frac{1}{27} (x-z) (x-2 y+z)(\frac{-(x+y-2 z) (P(x,z,y)-P(y,z,x))+(2 x-y-z) (P(y,x,z)-P(z,x,y))+(x-2 y+z) (P(x,y,z)-P(z,y,x))}{(x-y) (x-z) (y-z)})\) 二阶对称余式
\(\frac{1}{6} (x-y) (x-z) (y-z)(\frac{P(x,y,z)-P(x,z,y)-P(y,x,z)+P(y,z,x)+P(z,x,y)-P(z,y,x)}{(x-y) (x-z) (y-z)}) \)三阶对称余式

mathe

对于这种需要各种对称情况的\(P\left(x_1,x_2,\cdots,x_n\right)=0\)都需要满足的方程表达时，
我们可以先分成两类
i) $x_1,x_2,...,x_n$互不相等
ii)$x_1,x_2,...,x_n$至少两个元素相等
第一种，由于$x_1 != x_2$，所以我们得出\(Q_{1,2}(x_1,x_2,x_3\cdots,x_n)=\frac{P\left(x_1,x_2,x_3\cdots,x_n\right)-P\left(x_2,x_1,x_3,\cdots,x_n\right)}{x_1-x_2}=0\)
同样，我们可以继续利用$x_1!=x_3$得出\(Q_{1,2,3}(x_1,x_2,x_3\cdots,x_n)=\frac{P\left(x_1,x_2,x_3,x_4\cdots,x_n\right)-P\left(x_3,x_2,x_2,x_4\cdots,x_n\right)}{x_1-x_3}=0\)
这样递推到$Q_{1,2,3,...,n}(x_1,x_2,\cdots,x_n)$,总体次数会降低很多次，并且给出了n个变量互不相等时需要满足的条件。特别的Q降低为0次多项式$c=0$（其中$c$是非零常数）时代表不存在n个变量互不相等的情况。而另外计算过程中可能会出现$0=0$的情况，代表被处理之前的多项式已经满足对称性了，我们保留前一个多项式即可。
而上面过程处理完后$x_1$和后面任意一个变量交换都会有表达式不变，然后我们可能需要继续$x_2$和后面各个变量依次处理，...
最后处理完$O(n^2)$轮后就变成全对称多项式了。

而对于第二种情况，我们需要根据不同元素之间相等的情况进行分类。
比如有最大k个元素相等（余下n-k个元素相互之间相等数目不超过k）,由于全对称性，我们就假设$x_1=x_2=...=x_k$
于是我们可以将变量数目降阶为\(Q(x_1,x_{k+1},x_{k+2},...,x_n)=P(x_1,x_1,...,x_1,x_{k+1},x_{k+2},...,x_n)\)
但是这时我们可以继续将$x_1$和其它变量交换位置，会得出最多$C_n^k$个不同的表达式，正常情况表达式数目远远大于变量数目，会很容易确定下次数远远更低的多项式。
其中这个多项式中$x_1$是特殊的，余下变量对称。
最后我们可以继续前面过程对余下n-k个对称的变量做处理即可（唯一需要注意的是余下的变量中，相等元素数目不超过k）。

比如我们对三个变量$x_1,x_2,x_3$处理全对称公式$P(x_1,x_2,x_3)=x_1^4-4x_2x_3=0$
那么我们可以得出三个变量互不相等时$Q_{1,2}(x_1,x_2,x_3)=x^3+x^2y+xy^2+y^3+4z$
$Q_{1,2,3}(x_1,x_2,x_3)= x_1^2+x_2^2+x_3^2 + x_1x_2+x_2x_3+x_3x_1- 4$
而最后处理$x_2=x_3$这个条件时，我们会发现$Q_{1,2,3}(x_1,x_2,x_3)-Q_{1,2,3}(x_1,x_3,x_2)=0$,说明只需要保留结果$Q_{1,2,3}(x_1,x_2,x_3)$即可。

另外如果特殊情况$x_1=x_2=x_3$,那么我们得出$P(x_1,x_1,x_1)=x_1^4-4x_1^2=0$,所以$x_1=x_2=x_3=0$或$x_1=x_2=x_3=2$或$x_1=x_2=x_3=-2$
如果$x_1=x_2 != x_3$,我们得出$P(x_1,x_1,x_3)=x_1^4-4x_1x_3=0, P(x_3,x_1,x_1)=x_3^4-4x_1^2=0$
所以我们得出$x_1=0,x_3=0$(不满足$x_1!=x_3$淘汰)或$x_3={x_1^3}/4且x_3^4=4x_1^2$,所以这时可以时$x_1=x_2=2 \exp(\frac{i h\pi}5),x_3=2\exp(\frac{i 3h\pi}5)$,其中$h$是0,1,2,...,9中任选一个

zeroieme

mathe 发表于 2019-3-25 08:28
对于这种需要各种对称情况的\(P\left(x_1,x_2,\cdots,x_n\right)=0\)都需要满足的方程表达时，
我们可以先 ...

谢谢您的回复，看来我还是说不清楚。
不如举个例子，
假设在三角形中
三角形面积与三角形三边长的方程是 \(A(S,a,b,c)=0\)
三角形内切圆半径与三角形三边长的方程是 \(B(r,a,b,c)=0\)
三角形外接圆半径与三角形三边长的方程是 \(C(R,a,b,c)=0\)
构造方程 \(P(a,b,c,S,R,r)=a A+3b^2 B+5c^3 C=0\)。若\(\left\{a=a_1,b=b_1,c=c_1,S=S_1,r=r_1,R=R_1\right\}\)是方程 \(P=0\)的一组解，而且\(\left\{a=b_1,b=c_1,c=a_1,S=S_1,r=r_1,R=R_1\right\}\)也应当是方程的一组解，否则是增根。因为本质上P是由3个a、b、c的对称多项式A、B、C构造起来的，所以把P交换变量形成的方程组跟对称多项式方程组\(\left\{A=0,B=0,C=0\right\}\)是等价的。

于是我希望利用P中a、b、c系数之间的不对称尽可能把对称多项式A、B、C“拆”出来。
Mathematica的SymmetricReduction函数达不到这一要求，我用不断 \(\frac{P(\cdots,a,b,c)-P(\cdots,b,a,c)}{a-b}\)   \(\frac{P(\cdots,a,b,c)-P(\cdots,c,b,a)}{a-c}\) 是可以达到拆开对称多项式这目的。
这方法是我思考的起点。我想搞清楚的是：
i)这样交换变量对减降次的最大效果是几次。二元交换只能降1次，我曾经猜想n元交换只能降n-1次，但纯符号计算后三元交换能降3次。往更多变量推广计算更困难。
ii)n元多项式P至多有 \(C_n^k\)个轮换形式，其实多少个是独立的，或者说能拆出多少个对称多项式？
iii)快速拆解的算法，曾经自以为找到一种，结果发现达不到原始对减的效果。部分对称多项式混在一起没拆开。

@mathe的回复提供了一个结果是对减算法可以在 \(O(n^2)\)轮完成彻底拆分，希望没理解错。

mathe

前面我的思路有问题，但是这个题目的确复杂度不算高。
假设计算中我们维护一个函数形式$f(X_1,X_2,...,X_t;S)$,其中$X_i$是对集合${x_1,x_2,...,x_n}$的划分，代表一个子集内任意变量交换函数不变，S代表其它参数。
另外此多项式函数关于变量$x_1,x_2,...,x_n$的次数看出一个参数d.
于是上面每次挑选两个被划分到不同子集的变量变换，要么结果非零，于是d减少1,这时t最多加1;要么结果为0,保持原多项式，这时d不变，但是可以合并两个子集，也就是t减1。
所以必然在不超过2d+n次以内结束

zeroieme

mathe 发表于 2019-3-25 17:33
前面我的思路有问题，但是这个题目的确复杂度不算高。
假设计算中我们维护一个函数形式$f(X_1,X_2,...,X_t ...

17#是讨论变量变换的“深度”？从14#的三元符号化分拆结果看，存在一个与仅与可交换变量数n有关的界限函数Fswap(n)，同时每次结果非零，d减少1。那么至多就是降到0次，结果为常数或者0。所以深度是Fswap(n)与多项式次数d的最小值。

还有个“广度”问题。在未进行变换之前\(\left\{x_1,\cdots,x_n\right\}\) 划分为 $(X_1,\cdots,X_t)$，它们的有\(C_t^2\)种可能变换，有没必要全进行 ？进行每次“平行变换”降次后结果可合并。

我还是先尝试计算4元多项式的分拆结果。

zeroieme

您又误会了，17#的方法只能获得1个对称多项式。即使连同变量交换“计算路径”上的中间结果，也只有少于$O(n)$个方程。我想要的是一个等价方程组。

设$\Phi _n(x,y,z,\phi _n)=0$是${x,y,z}$的隐函数并且符合${x,y,z}$对称。
隐函数
\(P(x,y,z)=a_1 \Phi _1 x^3+a_2 \Phi _2 x^2 y+a_5 \Phi _5 x^2 z+a_3 \Phi _3 x y^2+a_{10} \Phi _{10} x y z+a_6 \Phi _6 x z^2+a_4 \Phi _4 y^3+a_8 \Phi _8 y^2 z+a_9 \Phi _9 y z^2+a_7 \Phi _7 z^3=0\)
是多个对称隐函数$\Phi _n(x,y,z,\phi _n)=0$的混叠。

利用$\Phi _n(x,y,z,\phi _n)$的对称性可得${P(x,y,z)=0,P(x,z,y)=0,\cdots,P(z,x,y)=0}$是$\Phi _n(x,y,z,\phi _n)$的方程组。
接着是我开话题的目的，通过对${P(x,y,z),P(x,z,y),\cdots,P(z,x,y)}$线性组合，转化为多个对称多项式，既降低方程总次数，也能通过换元为基本对称多项式进一步降低方程复杂性。

利用14#结论，\(P(x,y,z)=a_1 \Phi _1 x^3+a_2 \Phi _2 x^2 y+a_5 \Phi _5 x^2 z+a_3 \Phi _3 x y^2+a_{10} \Phi _{10} x y z+a_6 \Phi _6 x z^2+a_4 \Phi _4 y^3+a_8 \Phi _8 y^2 z+a_9 \Phi _9 y z^2+a_7 \Phi _7 z^3\)可分成

\(\left\{2 a_1 \left(\sigma _1^3-3 \sigma _2 \sigma _1+3 \sigma _3\right) \Phi _1+a_2 \left(\sigma _1 \sigma _2-3 \sigma _3\right) \Phi _2+a_3 \left(\sigma _1 \sigma _2-3 \sigma _3\right) \Phi _3+2 a_4 \left(\sigma _1^3-3 \sigma _2 \sigma _1+3 \sigma _3\right) \Phi _4+a_5 \left(\sigma _1 \sigma _2-3 \sigma _3\right) \Phi _5+a_6 \left(\sigma _1 \sigma _2-3 \sigma _3\right) \Phi _6+2 a_7 \left(\sigma _1^3-3 \sigma _2 \sigma _1+3 \sigma _3\right) \Phi _7+a_8 \left(\sigma _1 \sigma _2-3 \sigma _3\right) \Phi _8+a_9 \left(\sigma _1 \sigma _2-3 \sigma _3\right) \Phi _9+6 a_{10} \sigma _3 \Phi _{10},a_1 \left(2 \sigma _1^2-3 \sigma _2\right) \Phi _1+a_2 \sigma _2 \Phi _2-a_3 \sigma _2 \Phi _3-a_4 \left(2 \sigma _1^2-3 \sigma _2\right) \Phi _4+2 a_5 \sigma _2 \Phi _5+a_6 \left(\sigma _1^2-2 \sigma _2\right) \Phi _6-2 a_8 \sigma _2 \Phi _8-a_9 \left(\sigma _1^2-2 \sigma _2\right) \Phi _9,a_1 \left(2 \sigma _1^2-3 \sigma _2\right) \Phi _1+2 a_2 \sigma _2 \Phi _2+a_3 \left(\sigma _1^2-2 \sigma _2\right) \Phi _3+a_5 \sigma _2 \Phi _5-a_6 \sigma _2 \Phi _6-a_7 \left(2 \sigma _1^2-3 \sigma _2\right) \Phi _7-a_8 \left(\sigma _1^2-2 \sigma _2\right) \Phi _8-2 a_9 \sigma _2 \Phi _9,a_2 \left(\sigma _1^2-2 \sigma _2\right) \Phi _2+2 a_3 \sigma _2 \Phi _3+a_4 \left(2 \sigma _1^2-3 \sigma _2\right) \Phi _4-a_5 \left(\sigma _1^2-2 \sigma _2\right) \Phi _5-2 a_6 \sigma _2 \Phi _6-a_7 \left(2 \sigma _1^2-3 \sigma _2\right) \Phi _7+a_8 \sigma _2 \Phi _8-a_9 \sigma _2 \Phi _9,\sigma _1 \left(3 a_1 \Phi _1+a_2 \Phi _2-a_3 \Phi _3-3 a_4 \Phi _4-a_5 \Phi _5-2 a_6 \Phi _6+a_8 \Phi _8+2 a_9 \Phi _9\right),\sigma _1 \left(2 a_2 \Phi _2+a_3 \Phi _3-3 a_4 \Phi _4-2 a_5 \Phi _5-a_6 \Phi _6+3 a_7 \Phi _7-a_8 \Phi _8+a_9 \Phi _9\right),-\sigma _1 \left(3 a_1 \Phi _1-a_2 \Phi _2-2 a_3 \Phi _3+a_5 \Phi _5-a_6 \Phi _6-3 a_7 \Phi _7+2 a_8 \Phi _8+a_9 \Phi _9\right),a_2 \Phi _2-a_3 \Phi _3-a_5 \Phi _5+a_6 \Phi _6+a_8 \Phi _8-a_9 \Phi _9\right\}\)
8个对称多项式，其中\(\left\{\sigma _1=x+x+y,\sigma _2=x y+x z+y z,\sigma _3=x y z\right\}\)

但上面结果存在重复。最后得到的结果是以下6个对称多项式
\(\left\{a_1 \left(\sigma _1^2-\sigma _2\right) \left(\sigma _1^2-2 \sigma _2\right) \sigma _3 \Phi _1+a_7 \left(\sigma _1^2-\sigma _2\right) \left(\sigma _2 \sigma _1^3-\sigma _3 \sigma _1^2-3 \sigma _2^2 \sigma _1+5 \sigma _2 \sigma _3\right) \Phi _7-a_8 \sigma _2 \left(\sigma _3 \sigma _1^2-\sigma _1 \sigma _2^2+\sigma _2 \sigma _3\right) \Phi _8+a_9 \sigma _2 \left(\sigma _1^2-2 \sigma _2\right) \left(\sigma _1 \sigma _2-2 \sigma _3\right) \Phi _9+a_{10} \left(\sigma _1^2-\sigma _2\right) \sigma _2 \sigma _3 \Phi _{10},a_2 \left(\sigma _1^2-\sigma _2\right) \sigma _3 \Phi _2-a_7 \left(\sigma _1^2-\sigma _2\right) \left(\sigma _1^3-3 \sigma _2 \sigma _1+3 \sigma _3\right) \Phi _7+a_8 \left(\sigma _3 \sigma _1^2-\sigma _1 \sigma _2^2+\sigma _2 \sigma _3\right) \Phi _8-a_9 \left(\sigma _2 \sigma _1^3-\sigma _3 \sigma _1^2-2 \sigma _2^2 \sigma _1+3 \sigma _2 \sigma _3\right) \Phi _9-a_{10} \left(\sigma _1^2-\sigma _2\right) \sigma _3 \Phi _{10},a_3 \left(\sigma _1^2-\sigma _2\right) \left(\sigma _1^2-2 \sigma _2\right) \sigma _3 \Phi _3+a_7 \left(\sigma _1^2-\sigma _2\right) \sigma _2 \left(\sigma _1^3-3 \sigma _2 \sigma _1+3 \sigma _3\right) \Phi _7-a_8 \left(\sigma _3 \sigma _1^4-2 \sigma _2 \sigma _3 \sigma _1^2-\sigma _1 \sigma _2^3+3 \sigma _2^2 \sigma _3\right) \Phi _8+a_9 \sigma _2 \left(\sigma _1^2-2 \sigma _2\right) \left(\sigma _1 \sigma _2-2 \sigma _3\right) \Phi _9+a_{10} \left(\sigma _1^2-\sigma _2\right) \sigma _2 \sigma _3 \Phi _{10},a_4 \left(\sigma _1^2-\sigma _2\right) \Phi _4-a_7 \left(\sigma _1^2-\sigma _2\right) \Phi _7+a_8 \sigma _2 \Phi _8-a_9 \sigma _2 \Phi _9,a_5 \left(\sigma _1^2-\sigma _2\right) \sigma _3 \Phi _5-a_7 \left(\sigma _1^2-\sigma _2\right) \left(\sigma _1^3-3 \sigma _2 \sigma _1+3 \sigma _3\right) \Phi _7+a_8 \sigma _1 \left(\sigma _1 \sigma _3-\sigma _2^2\right) \Phi _8-a_9 \left(\sigma _1^2-2 \sigma _2\right) \left(\sigma _1 \sigma _2-\sigma _3\right) \Phi _9-a_{10} \left(\sigma _1^2-\sigma _2\right) \sigma _3 \Phi _{10},a_6 \left(\sigma _1^2-\sigma _2\right) \left(\sigma _1^2-2 \sigma _2\right) \sigma _3 \Phi _6+a_7 \left(\sigma _1^2-\sigma _2\right) \sigma _2 \left(\sigma _1^3-3 \sigma _2 \sigma _1+3 \sigma _3\right) \Phi _7-a_8 \sigma _2 \left(2 \sigma _3 \sigma _1^2-\sigma _1 \sigma _2^2-\sigma _2 \sigma _3\right) \Phi _8-a_9 \sigma _1 \left(\sigma _1^2-2 \sigma _2\right) \left(\sigma _1 \sigma _3-\sigma _2^2\right) \Phi _9+a_{10} \left(\sigma _1^2-\sigma _2\right) \sigma _2 \sigma _3 \Phi _{10}\right\}\)

所以我的需求是把\({P(x,y,z)=0,P(x,z,y)=0,\cdots,P(z,x,y)=0}\)转化成\(\left\{P_1\left(\sigma _1,\sigma _2,\sigma _3\right)=0,P_2\left(\sigma _1,\sigma _2,\sigma _3\right)=0,\cdots,P_n\left(\sigma _1,\sigma _2,\sigma _3\right)=0\right\}\)

zeroieme

mathe 发表于 2019-3-25 17:33
前面我的思路有问题，但是这个题目的确复杂度不算高。
假设计算中我们维护一个函数形式$f(X_1,X_2,...,X_t ...

解是否存在

我是这么看的：如上16#、17#说P是由多个隐函数叠加成的。改变自变量${x_1,x_2,...,x_n}$，必然改变函数变量${f_1,f_2,...,f_n}$。所以解是必然存在的。
现在的目标是把多个叠加的隐函数区分出来，就象红豆绿豆黄豆黑豆混在一起要重新分开。
首先，交换可交换变量这个算法区分能力有多大？自变量${x_1,x_2,...,x_n}$，如果划分为$(X_1,X_2,...,X_k)$，则有$k!$种交换，是否具有区分$k!$个叠加的隐函数的能力？


说到这里，不多不少很困难。先实现不会丢失信息的快速方法，容忍存在非独立的方程，可以在后续计算剔除。