二元等幂和的代数相关（一种非线性相关）

青青子衿

\begin{align*}
\begin{split}
1\,2\,3
\end{split}&&
\begin{split}
1\,2\,4\\
1\,3\,4\\
2\,3\,4\\
\end{split}&&
\begin{split}
1\,2\,5\\
1\,3\,5\\
1\,4\,5\\
2\,3\,5\\
2\,4\,5\\
3\,4\,5\\
\end{split}
\end{align*}
\begin{align*}
p_{\overset{\,}{k}}\,\colon=
\begin{cases}
p_{\overset{\,}{k}}(x,y)\triangleq\,x^k+y^k\\
\,\\
p_{\overset{\,}{k}}(u,v)\triangleq\,u^k+v^k\\
\end{cases}
\end{align*}
\begin{split}
&\small(x^2+y^2)^6&\small-4(x^2+y^2)^3(x^3+y^3)^2&\small-4(x^3+y^3)^4&\small+12 (x^2+y^2)(x^3+y^3)^2(x^4+y^4)&\small-3(x^2+y^2)^2(x^4+y^4)^2&\small-2(x^4+y^4)^3&\equiv0\\
&\small(u^2+v^2)^6&\small-4(u^2+v^2)^3(u^3+v^3)^2&\small-4(u^3+v^3)^4&\small+12 (u^2+v^2)(u^3+v^3)^2(u^4+v^4)&\small-3(u^2+v^2)^2(u^4+v^4)^2&\small-2(u^4+v^4)^3&\equiv0\\
&{p_{\overset{\,}{2}}}\!^6&-4{p_{\overset{\,}{2}}}\!^3{p_{\overset{\,}{3}}}\!^2&-4{p_{\overset{\,}{3}}}\!^4&+12 {p_{\overset{\,}{2}}}{p_{\overset{\,}{3}}}\!^2{p_{\overset{\,}{4}}}&-3{p_{\overset{\,}{2}}}\!^2{p_{\overset{\,}{4}}}\!^2&\small-2{p_{\overset{\,}{4}}}\!^3&\equiv0
\end{split}
\[ 2\left({p_{\overset{\,}{2}}}\!^2-{p_{\overset{\,}{4}}}\right)^3=\left({p_{\overset{\,}{2}}}\!^3-3{p_{\overset{\,}{2}}}{p_{\overset{\,}{4}}}+2{p_{\overset{\,}{3}}}\!^2\right)^2 \]
...

1. [1,2,3]   
2.    (x + y)^3 - 3 (x + y)*(x^2 + y^2) + 2 (x^3 + y^3) // Expand
3. [1,2,4]   
4.    (x + y)^4 - 2 (x + y)^2*(x^2 + y^2) - (x^2 + y^2)^2 + 2 (x^4 + y^4) // Expand
5. [1,3,4]   
6.    (x + y)^6 - 8 (x + y)^3*(x^3 + y^3) - 2 (x^3 + y^3)^2 + 9 (x + y)^2* (x^4 + y^4) // Expand
7. [2,3,4]   
8.    (x^2 + y^2)^6 - 4 (x^2 + y^2)^3*(x^3 + y^3)^2 - 4 (x^3 + y^3)^4
9.    + 12 (x^2 + y^2)*(x^3 + y^3)^2*(x^4 + y^4)
10.    - 3 (x^2 + y^2)^2*(x^4 + y^4)^2 - 2 (x^4 + y^4)^3 // Expand

复制代码

...

1. Resultant[x^3 + x - p, x^2 + x - q, x] // Factor

复制代码

...
\begin{align*}
P(\,p_{\overset{\,}{1}}\,,\,p_{\overset{\,}{2}}\,,\,p_{\overset{\,}{3}})&={p_{\overset{\,}{1}}}\!^3-3p_{\overset{\,}{1}}p_{\overset{\,}{2}}+2p_{\overset{\,}{3}}\\
\,\\
P(\,p_{\overset{\,}{1}}\,,\,p_{\overset{\,}{2}}\,,\,p_{\overset{\,}{4}})&={p_{\overset{\,}{1}}}\!^4-2{p_{\overset{\,}{1}}}\!^2p_{\overset{\,}{2}}-{p_{\overset{\,}{2}}}\!^2+2p_{\overset{\,}{4}}\\
\,\\
P(\,p_{\overset{\,}{1}}\,,\,p_{\overset{\,}{3}}\,,\,p_{\overset{\,}{4}})&={p_{\overset{\,}{1}}}\!^6-8{p_{\overset{\,}{1}}}\!^3p_{\overset{\,}{3}}-2{p_{\overset{\,}{3}}}\!^2+9{p_{\overset{\,}{1}}}\!^2p_{\overset{\,}{4}}\\
\end{align*}
另外，如何求出\(\,\left\{u^3+v^3,u^4+v^4,u^5+v^5\right\}\,\)（实际上几何背景也由此可知，即化参数曲面为隐式曲面）
（好像可以借助Dixon结式）
pdfs.semanticscholar.org/074d/652f97d07a2d5150764c2f448a6d98d3ab3b.pdf

青青子衿

回复 1# 青青子衿
找到解决方法了！
（即求出“多项式理想”）

2. eq1 = u^3 + v^3 - a;
3. eq2 = u^4 + v^4 - b;
4. eq3 = u^5 + v^5 - c;
5. GroebnerBasis[{eq1, eq2, eq3}, {a, b, c}, {u, v}]

复制代码

...
...

1. Eliminate[{x == u^2 + v^2, y == u^3 + v^3, z == u^4 + v^4},
2. {u, v}] /. {x :> u^2 + v^2, y :> u^3 + v^3, z :> u^4 + v^4}

复制代码

...
...

1. {a^10 - 5 a^6 b^3 - 25 a^2 b^6 + 60 a^3 b^4 c
2. - 30 a^4 b^2 c^2 +18 b^5 c^2 + 4 a^5 c^3
3. - 40 a b^3 c^3 + 15 a^2 b c^4 + 2 c^6}

复制代码

...
\begin{gather*}
\color{black}{
\begin{cases}   
\begin{split}        
x&=&\,&\color{blue}{u^3+v^3}\\         
y&=&\,&\color{gold}{u^4+v^4}\\      
z&=&\,&\color{silver}{u^5+v^5}      
\end{split}  
\end{cases}}\\
\,\\
\Downarrow\\
\,\\
\color{red}{x^{10}-5x^6y^3-25x^2y^6+60x^3y^4z  
-30x^4y^2z^2+18y^5z^2+4x^5z^3  
-40xy^3z^3 + 15x^2yz^4+2z^6=0}\,
\end{gather*}
更多元的情形：
\begin{align*}
6\left(u^{\color{red}5}+v^{\color{red}5}+w^{\color{red}5}\right)=&\phantom{+1}\left(u+v+w\right)^{\color{red}5}\\
&-{\color{red}5}\left(u+v+w\right)^3\left(u^2+v^2+w^2\right)\\
&+{\color{red}5}\left(u+v+w\right)^2\left(u^3+v^3+w^3\right)\\
&+ {\color{red}5}\left(u^2+v^2+w^2\right)\left(u^3+v^3+w^3\right)
\end{align*}
eq1 = u^1 + v^1 + w^1 - a;
eq2 = u^2 + v^2 + w^2 - b;
eq3 = u^3 + v^3 + w^3 - c;
eq4 = u^5 + v^5 + w^5 - d;
GroebnerBasis[{eq1, eq2, eq3, eq4}, {a, b, c, d}, {u, v, w}]
{a^5 - 5 a^3 b + 5 a^2 c + 5 b c - 6 d}

eq1 = p^1 + q^1 + u^1 + v^1 - a;
eq2 = p^2 + q^2 + u^2 + v^2 - b;
eq3 = p^3 + q^3 + u^3 + v^3 - c;
eq4 = p^4 + q^4 + u^4 + v^4 - d;
eq5 = p q u v - e;
GroebnerBasis[{eq1, eq2, eq3, eq4, eq5}, {a, b, c, d, e}, {p, q, u, v}]
{a^4 - 6 a^2 b + 3 b^2 + 8 a c - 6 d - 24 e}

blog.sina.com.cn/s/blog_7ac9421701017iua.html

青青子衿

回复 2# 青青子衿
((u + v)^3 - 4 (u^3 + v^3)) -
  3 (u + v) ((u + v)^2 - 2 (u^2 + v^2)) // Expand
幂简洁形式：
\begin{align*}
{p_{\overset{\,}{1}}}\!^3-3p_{\overset{\,}{1}}p_{\overset{\,}{2}}+2p_{\overset{\,}{3}}=0
&&
\Longleftrightarrow
&&
3p_{\overset{\,}{1}}({p_{\overset{\,}{1}}}^2-2p_{\overset{\,}{2}})&=({p_{\overset{\,}{1}}}\!^3-4p_{\overset{\,}{3}})\\
{p_{\overset{\,}{1}}}\!^4-2{p_{\overset{\,}{1}}}\!^2p_{\overset{\,}{2}}-{p_{\overset{\,}{2}}}\!^2+2p_{\overset{\,}{4}}=0
&&
\Longleftrightarrow
&&
2({p_{\overset{\,}{1}}}\!^4+p_{\overset{\,}{4}})&=({p_{\overset{\,}{1}}}\!^2+p_{\overset{\,}{2}})^2\\
{p_{\overset{\,}{1}}}\!^6-8{p_{\overset{\,}{1}}}\!^3p_{\overset{\,}{3}}-2{p_{\overset{\,}{3}}}\!^2+9{p_{\overset{\,}{1}}}\!^2p_{\overset{\,}{4}}=0
&&
\Longleftrightarrow
&&
9{p_{\overset{\,}{1}}}^2({p_{\overset{\,}{1}}}\!^4+p_{\overset{\,}{4}})&=2(2{p_{\overset{\,}{1}}}\!^3+p_{\overset{\,}{3}})^2\\
\end{align*}
\begin{align*}
\operatorname{Reslt}\left(\left.
\begin{matrix}
p_{\overset{\,}{2}}(u,v)\\
p_{\overset{\,}{3}}(u,v)\\
p_{\overset{\,}{4}}(u,v)
\end{matrix}
\right|\{u,v\}\right)=0  
&&   
\Longleftrightarrow   
&&   
2\left({p_{\overset{\,}{2}}}\!^2-{p_{\overset{\,}{4}}}\right)^3=\left({p_{\overset{\,}{2}}}\!^3-3{p_{\overset{\,}{2}}}{p_{\overset{\,}{4}}}+2{p_{\overset{\,}{3}}}\!^2\right)^2
\end{align*}

青青子衿

回复 3# 青青子衿
\begin{align*}  
{p_{\overset{\,}{1}}}\!^5-5p_{\overset{\,}{1}}{p_{\overset{\,}{2}}}\!^2+4p_{\overset{\,}{5}}=0  
&&
\Longleftrightarrow
&&
p_{\overset{\,}{1}}(5{p_{\overset{\,}{2}}}\!^2-{p_{\overset{\,}{1}}}^4)&=4p_{\overset{\,}{5}}\\

{p_{\overset{\,}{1}}}\!^6-5{p_{\overset{\,}{1}}}\!^3p_{\overset{\,}{3}}+9p_{\overset{\,}{1}}p_{\overset{\,}{5}}-5{p_{\overset{\,}{3}}}\!^2=0  
&&
\Longleftrightarrow
&&
9p_{\overset{\,}{1}}({p_{\overset{\,}{1}}}^5+4p_{\overset{\,}{5}})&=5({p_{\overset{\,}{1}}}\!^3+2p_{\overset{\,}{3}})^2\\

\end{align*}

\begin{align*}
\operatorname{Reslt}\left(\left.
\begin{matrix}
p_{\overset{\,}{1}}(u,v)\\
p_{\overset{\,}{4}}(u,v)\\
p_{\overset{\,}{5}}(u,v)
\end{matrix}
\right|\{u,v\}\right)=0
&&  
\Longleftrightarrow  
&&  
10\,p_{\overset{\,}{1}}\!({p_{\overset{\,}{1}}}\!^4+p_{\overset{\,}{4}})({p_{\overset{\,}{1}}}\!^5+4p_{\overset{\,}{5}})&=(3{p_{\overset{\,}{1}}}\!^5+5p_{\overset{\,}{1}}p_{\overset{\,}{4}}+2p_{\overset{\,}{5}})^2\\   
\end{align*}

\begin{gather*}
\operatorname{Reslt}\left(\left.
\begin{matrix}
p_{\overset{\,}{2}}(u,v)\\
p_{\overset{\,}{3}}(u,v)\\
p_{\overset{\,}{5}}(u,v)
\end{matrix}
\right|\{u,v\}\right)=0\\
\\
\Updownarrow   
\\   
5p_2\left(p_2 p_3-p_5\right) \left({p_2}^4-3 {p_3}^2 p_2+3 p_3 p_5\right)= {p_2}^5p_5+{p_3}^5-2 {p_5}^3  
\end{gather*}

\begin{align*}
\operatorname{Reslt}\left(\left.
\begin{matrix}
p_{\overset{\,}{2}}(u,v)\\
p_{\overset{\,}{4}}(u,v)\\
p_{\overset{\,}{5}}(u,v)
\end{matrix}
\right|\{u,v\}\right)=0  
&&   
\Longleftrightarrow   
&&   
2\,({p_{\overset{\,}{2}}}\!^2-p_{\overset{\,}{4}})^5&=({p_{\overset{\,}{2}}}\!^5-5p_{\overset{\,}{2}}{p_{\overset{\,}{4}}}\!^2+4{p_{\overset{\,}{5}}}\!^2)^2\\   
\end{align*}

1. Resultant[
2.   w^3 - (3 p^2 - 3 g q) w - (g^4 + 2 p^3 -  3 g p q),
3.     (g^4 p - 9 p^4 + 9 g p^2 q - g^2 q^2) w^2 +
4.     (g^4 p^2 - 18 p^5 - 2 g^5 q + 27 g p^3 q - 8 g^2 p q^2) w
5.     + (g^8 - 3 g^4 p^3 - 9 p^6 + 18 g p^4 q - 7 g^2 p^2 q^2), w] // Factor

复制代码

\left(2{p_{\overset{\,}{2}}}\!^6-6{p_{\overset{\,}{2}}}\!^3{p_{\overset{\,}{3}}}\!^2+{p_{\overset{\,}{3}}}\!^4+3{p_{\overset{\,}{2}}}\!^2p_{\overset{\,}{3}}p_{\overset{\,}{5}}\right)^2
=\left(2{p_{\overset{\,}{2}}}\!^4-3p_{\overset{\,}{2}}{p_{\overset{\,}{3}}}\!^2+p_{\overset{\,}{3}}p_{\overset{\,}{5}}\right)^2\left({p_{\overset{\,}{2}}}\!^4-3p_{\overset{\,}{2}}{p_{\overset{\,}{3}}}\!^2+2p_{\overset{\,}{3}}p_{\overset{\,}{5}}\right)

hbghlyj

$\DeclareMathOperator{\lt}{lt}$Gröbner basis -- 维基百科
Gröbner基算法可以看作是计算多项式最大公约数的欧几里德算法和线性系统的高斯消元法的对于多元非线性系统的推广.
下面是Formal definition这一节的第一段的翻译
一个域上的多项式环$R$中的理想$I$关于某个单项式序的Gröbner基$G$是$I$的满足下面任一性质的生成集:

• $I$中多项式的首项所产生的理想等于$G$的首项所产生的理想;
• $I$中任何多项式的首项都可以被$G$中某个多项式的首项整除;
• 多项式环$R$中的任何多项式除以$G$的多元除法的余式唯一;
• 理想$I$中任何多项式除以$G$的多元除法的余式为0.

以上所有性质都是等价的.最后两个性质允许在商环$R/I$中使用与模算术相同的功能进行计算.Gröbner基的存在性是交换代数的一个重要事实,并且对于任何由有限生成集给出的理想都有效.
下面是Examples of reduction这一节的翻译
在本节的示例中,多项式具有三个不定元$x,y,z$.我们使用的单项式序是$x\succ y\succ z$的字典序(即用于比较两个单项式,首先比较$x$的指数,只有当$x$的指数相等时,才比较$y$的指数;并且仅当其他指数相等时才比较$z$的指数).为了清楚地了解约化过程,必须以降序重写多项式.例如,将$P=xy^{3}z^{5}+x^{2}y^{6}+x^{4}yz+y^{2}z^{5}+yz^{4}+y^{3}+z^{3}+xy+xz+z^{2}+z$写成$P=x^{4}yz+x^{2}y^{6}+xy^{3}z^{5}+xy+xz+y^{3}+y^{2}z^{5}+yz^{4}+z^{3}+z^{2}+z$.所以$P$的首项是$\operatorname {lm} (P)=x^{4}yz$.
考虑$f=2x^{3}-x^{2}y+y^{3}+3y$被$G=\{g_{1},g_{2}\}$约化的过程,其中$g_{1}=x^{2}+y^{2}-1,g_{2}=xy-2$.
第一步,我们约去第一项或者第二项,然而,约去某一项会以增加较低次项为代价.如果不是约去首项的话,有可能后面的约化过程中会产生已经约去的项的同次项,导致我们必须再约化一次.所以我们最好是每次都约去(对于所指定的单项式序而言的)首项.
$f$的首项$2x^{3}$被$g_{1}$整除,所以第一步是将$f$加上$g_{1}$的$-2x$倍.$$f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}=f-2xg_{1}=-x^{2}y-2xy^{2}+2x+y^{3}+3y.$$因为$f_{1}$的首项$-x^{2}y$既是$g_{1}$的倍式也是$g_{2}$的倍式,我们有两种选择.如果选择$g_{2}$,我们得到一个可以再次被$g_{2}$约化的多项式:$$f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}\;{\overset {xg_{2}}{\longrightarrow }}\;-2xy^{2}+y^{3}+3y\;{\overset {2yg_{2}}{\longrightarrow }}\;f_{2}=+y^{3}-y.$$更进一步的约化是不可能的.所以可以认为$f_{2}$是$f$的完全约化结果.然而,对于第二种选择我们得到不同的结果:$$f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}\;{\overset {yg_{1}}{\longrightarrow }}\;-2xy^{2}+2x+2y^{3}+2y\;{\overset {2yg_{2}}{\longrightarrow }}\;f_{3}=+2x+2y^{3}-2y.$$所以,$f$的完全约化结果是$f_{2}$或$f_{3}$.
Buchberger算法就是为了解决这种“不唯一性”造成的困难的.粗略地说它将一些多项式加入$G$使得任何多项式$f$被$G$完全约化的结果唯一.
于此,Buchberger算法的第一步就是将多项式$g_{3}=yg_{1}-xg_{2}=2x+y^{3}-y$加入$G$.
的确,$f_{3}$可以被$g_{3}$进一步约化为$f_{2}$.然而,Buchberger算法还没完,因为$xy$被$g_2,g_3$完全约化的结果不唯一.
下面是Example and counterexample这一节的翻译
设$R=\mathbb {Q} [x,y]$为有理系数二元多项式环,考虑由$f(x,y)=x^{2}-y,g(x,y)=x^{3}-x$生成的理想$I=\langle f,g\rangle$.
那么$k(x,y) = −xf(x,y) + g(x,y) = xy − x,h(x,y) = xk(x,y) − (y - 1)f(x,y) = y^2 − y$也属于$I$.在$x>y$的字典序下$\lt(f) = x^2,\lt(g) = x^3,\lt(h) = y^2$(lt表示leading term,“首项”)
由$\{\lt(f),\lt(g)\}$只包含$x^2$的倍式,而不包含$\lt(h) = y^2$,故$\{f, g\}$不是$I$的Gröbner基.
另一方面,可以看出$\{f, k, h\}$是$I$的Gröbner基.
首先,$f$和$g$,与$h$,$k$以及$I$中的所有其他多项式在$(x,y)$平面上有以下三个共同零点:$\{(1,1),(−1,1),(0,0)\}$.这些点不共线,所以$I$不包含一次多项式.$I$也不包含形如$m(x,y) = cx + p(y)$的多项式(其中$c$是非零有理数,$p$是只含$y$的多项式),原因是这种$m$对于$y$的同一个值不能取两个不同的零点,此处,这两个不同的零点是(1,1)和(−1,1).
所以在$I$中,除了零多项式外只有首项≥2的多项式,所以它们的首项被下面的3个单项式中至少一个所整除:$\{x^2, xy, y^2\} = \{\lt(f),\lt(k),\lt(h)\}$.
这意味着$\{f, k, h\}$是$I$在字典序$x \succ y$下的一个Gröbner基.

hbghlyj

mathmu - 代数方程组求解

如果只从几何证明的角度,吴方法无疑比Gröbner基要高效很多,正是如此,吴方法在几何证明领域中在世界上都是十分有名的.然而,吴方法毕竟相当于一种不完全的约化,其除法用的是伪除法,因而在解方程、多项式理想计算等方面不如Gröbner基.

SymPy - groebner
msri.org/people/members/chillar/files/gbapplfinal.pdf
math.colorado.edu/~rohi1040/expository/groebner_bases.pdf
ijstr.org/final-print/aug2019/A-Review-On-Groebner-Basis-And-Its-Applications.pdf
people.math.carleton.ca/~cingalls/studentProjects/alithesis.pdf

hbghlyj

相关问题:
Complete generating sets for the following. Groebner basis

hbghlyj

青青子衿 发表于 2019-5-4 14:38
（好像可以借助Dixon结式）pdfs.semanticscholar.org/074d/652f97d07a2d5150764c2f448a6d98d3ab3b.pdf

Wolfram library
Wolfram Function Repository

$f(x)$和$g(x)$为多项式,设$n=\max(\deg(f),\deg(g))$,关于$x,a$的$n-1$次对称多项式$$\delta (x,a)=\frac{1}{x-a}\left|
\begin{array}{cc}
f(x) & g(x) \\
f(a) & g(a) \\
\end{array}\right|$$称为$f,g$的Dixon多项式.任何$f,g$的公共根是$δ(x,a)$的根,对任意的$a$.因此,$δ(x,a)$中$a$的各项系数均为0.$$M\left[
\begin{array}{c}
1 \\
x \\
\vdots  \\
x^{n-1} \\
\end{array}
\right]=\left[
\begin{array}{c}
0 \\
0 \\
\vdots  \\
0 \\
\end{array}
\right]$$其中,$n×n$矩阵$M$的列是$a^i$的系数.这导出了关于新的变量$v_1,v_2,⋯,v_n$的齐次方程组,它们分别等于$x^0,x^1,\ldots ,x^{n-1}$,出现在$a^i$的系数中.
$$M\left[
\begin{array}{c}
v_1 \\
v_2 \\
\vdots  \\
v_{n} \\
\end{array}
\right]=\left[
\begin{array}{c}
0 \\
0 \\
\vdots  \\
0 \\
\end{array}
\right]$$方程组(1)有非平凡解,当且仅当其行列式$D=0$.$D$称为$f,g$的Dixon结式,$M$称为Dixon矩阵.

Dixon结式$D$的值为零是 $f$ 和 $g$ 存在公共根的必要条件.

例1.(数值系数,有公共根)
$
\begin{array}{c}
f(x)=x^3-2 x^2-11 x+12=(x-1) (x+3) (x-4) \\
g(x)=x^2+3 x-4=(x+4) (x-1) \\
\end{array}$
解:Dixon多项式
$\delta =\frac{1}{x-a}\left|
\begin{array}{ccc}
x^3-2 x^2-11 x+12 &  & x^2+3 x-4 \\
a^3-2 a^2-11 a+12 &  & a^2+3 a-4 \\
\end{array}
\right|=$
$a^2 x^2-4 a^2+3 a x^2+a x+3 (a x)^2-4 a-4 x^2-4 x+8$
令$a$的各项系数为0得,$$\left\{
\begin{array}{c}
-4 x^2-4 x+8=0 \\
3 x^2+x-4=0 \\
x^2+3 x-4=0 \\
\end{array}\right.$$
Dixon结式$$D=\left|
\begin{array}{ccc}
8 & -4 & -4 \\
-4 & 1 & 3 \\
-4 & 3 & 1 \\
\end{array}
\right|=0$$
因此$f(x),g(x)$有公共根,这个公共根实际上是$x=1$.


例2.(数值系数,无公共根)
$$
\begin{array}{c}
f(x)=x^3-2 x^2-11 x+12=(x-1) (x+3) (x-4) \\
g(x)=x^2+5 x+4=(x+4) (x+1) \\
\end{array}
$$
解:$$D=\left|
\begin{array}{ccc}
-104 & -20 & 4 \\
-20 & 5 & 5 \\
4 & 5 & 1 \\
\end{array}
\right|=800≠0$$因此$f(x),g(x)$无公共根.

例3.(参数系数,得到所有根)
\begin{aligned}f(x)&=-A^3-2 A^2+A x^2-A x+3 A+3 x^2-3 x\\
&=(A+3) (A+x-1) (x-A)\\
g(x)&=3 A^2+4 A x+x^2=(3 A+x) (A+x)\end{aligned}
解:
$$D=\left|
\begin{array}{ccc}
4 A^4+5 A^3-21 A^2 &  & 4 A^3+11 A^2-3 A \\
4 A^3+11 A^2-3 A &  & 4 A^2+13 A+3 \\
\end{array}
\right|=-8 \left(A^2 (2 A+1)\right) (A+3)^2$$
令$D=0$,解得$$A=-3,-3,-\frac{1}{2},0,0$$
另一方面,由$f(x,A)=0,g(x,A)=0$解得
$$(x,A)=(9,-3),(3,-3),(0,0),\left(\frac{3}{2},-\frac{1}{2}\right)$$
注意到,$A$的所有解都满足$D=0$.在$D=0$中,$A=0$这个根的重数为2,但是,当$A=0$时,方程的解是唯一的.
在这个例子中,方程组的所有解都可以由 Dixon 结式的零点得到.

例4.(参数系数,得不出任何信息)
\begin{aligned}
f(x)&=A^2+A x^2-(A x)^2-4 (A x)+3 A+3 x^2-3 x\\
&=(A+3)(x-1)(x-A)\\
g(x)&=x^2+xA-x-A=(x-1)(x+A)
\end{aligned}
解:$$D=\left|
\begin{array}{ccc}
2 A^2+6 A &  & -2 A^2-6 A \\
-2 A^2-6 A &  & 2 A^2+6 A \\
\end{array}
\right|$$我们发现$D$恒为零.
实际上,$f(x,A)=0,g(x,A)=0$的解为$(x,A)=(3,-3),(1,A),(0,0)$.
这次,$D$的零点并未提供关于原方程组的解的任何信息.

hbghlyj

对于三个多项式组成的二元方程组:\begin{cases}f(x,y)=0\\g(x,y)=0\\h(x,y)=0\end{cases}Dixon多项式$δ$定义为
$$\delta (x,y,a,b)=\frac{1}{(x-a) (y-b)}\begin{vmatrix}f(x, y) & g(x, y) & h(x, y) \\ f(a, y) & g(a, y) & h(a, y) \\ f(a, b) & g(a, b) & h(a, b)\end{vmatrix}$$像上一节一样,令$a^ib^j$的系数为0,得到的系数矩阵的行列式定义为Dixon结式.
Dixon 证明了,对于三个generic二次多项式，$D=0$是公共根存在的必要条件。此外，$D$不恒为零。
Dixon方法容易推广到$n$个变元的$n+1$个generic $n$次多项式.

定义:如果多项式的所有系数都是相互独立的参数，则称为generic多项式。如果每个变量的最大次幂为$n$，则称多项式为$n$次多项式。

$n+1$个$n$元多项式,$p_j(x_1,⋯x_n),j=1,⋯,n+1$称为generic $n$ degree,如果存在整数$k_1,⋯,k_n$使
$$p_j=\sum_{i_1=0}^{k_1}\ldots \sum_{i_n=0}^{k_n}a_{j,i_1,\ldots ,i_n}x_1^{i_1}\ldots x_n^{i_n},\quad1\leq j\leq n+1$$
例子:下面的三个多项式是generic $n$ degree.
\begin{array}{c}
p_1=a_5 x^2 y+a_4 x^2+a_3 x y+a_1 x+a_2 y+a_0 \\
p_2=b_5 x^2 y+b_4 x^2+b_3 x y+b_1 x+b_2 y+b_0 \\
p_3=c_5 x^2 y+c_4 x^2+c_3 x y+c_1 x+c_2 y+c_0 \\
\end{array}而下面的三个多项式不是generic $n$ degree.
\begin{array}{c}
q_1=(a x)^2+x^2 y+3 x \\
q_2=-(a x)^2+x y+y \\
q_3=b+c_1 x+c_2 y \\
\end{array}
因为$q_1$中,系数3不是未定元,所以$q_1$不是generic,而且没有$x^0 y^0$的系数(所以不是$n$ degree)

Dixon 的方法适用于具有符号变量的多项式，它允许仅通过一次计算同时消除一组未知数。这一特征，以及所产生的判别的相对较小的尺寸（与其他产生的方法相比）使得该方法非常有吸引力。

不幸的是，如果多项式不是generic和 $n$ degree，那么事情可能会出错。
在以下示例中，我们说明了 Dixon 方法及其对不一定是generic或$n$ degree的多项式的局限性。

例5.
\begin{array}{c}
f(x)=x y+3 x-3 y-9=(x-3) (y+3) \\
g(x)=x y-3 x+3 y-9=(x+3) (y-3) \\
h(x)=x y+2 x-2 y-4=(x-2) (y+2) \\
\end{array}
解:Dixon结式是$30y+30a$,Dixon矩阵$M$为\begin{matrix}&\scriptsize\mathclap{\begin{array}{cc}x^0y^0&x^0y^1\end{array}}\\\mathclap{\scriptsize
\begin{array}{c}
&a^0 b^0 \\
&a^1 b^0 \\
\end{array}}&
\begin{bmatrix}
0 & 30 \\
30 & 0 \\
\end{bmatrix}\end{matrix}Dixon结式$D=\det(M)=-900≠0$,所以我们期望方程组是无解的,实际上,的确是无解的.

例6.
\begin{array}{c}
f(x)=x y+3 x-y^2-3 y=(y+3) (x-y) \\
g(x)=x^2+4 x y+3 y^2=(x+3 y) (x+y) \\
h(x)=x^2-x y-2 y^2=(x-2 y) (x+y) \\
\end{array}
解:Dixon矩阵
\begin{matrix}
&\small
\mathclap{\begin{array}{cccccc}
& x^0 y^0 & x^0 y^1 & x^0 y^2 & x^1 y^0 & x^1 y^1 & x^1 y^2 \\
\end{array}}
\\\mathclap{
\begin{array}{c}
a^0 b^0 \\
a^0 b^1 \\
a^1 b^0 \\
a^1 b^1 \\
a^2 b^0 \\
a^2 b^1 \\
\end{array}}
&
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 15 & 0 & 15 & 0 \\
0 & 0 & -15 & 0 & -15 & 0 \\
0 & 15 & 0 & -15 & -10 & 0 \\
0 & 15 & 10 & -15 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 \\
\end{bmatrix}
\end{matrix}它的行列式$D$恒为零,并非提供关于方程组的解的任何信息.
另一方面,方程组有解$(x,y)=(0,0),(3,-3)$

注:我们可以通过删除零行和零列来减小 Dixon 矩阵的大小，就像在 [Kapur, Saxena, and Yang 1994] 中所做的那样。在稀疏多项式或稀疏 Dixon 多项式的情况下，这通常会减小矩阵的大小。在这种情况下，我们可以写，
$$M=\left[
\begin{array}{cccc}
0 & 15 & 0 & 15 \\
0 & -15 & 0 & -15 \\
15 & 0 & -15 & -10 \\
15 & 10 & -15 & 0 \\
\end{array}
\right]$$（请注意，此处的行列式仍然为零。）但是，这可能会导致一些临时问题，这些问题将在第 3 节中解决。

从现在开始，我们从 Dixon 矩阵中删除零列和行，但仍称其为 Dixon 矩阵。

例7.
\begin{array}{c}
f(x)=x y-3 y=(x-3) y \\
g(x)=x y-3 x=x (y-3) \\
h(x)=x y-2 y=(x-2) y \\
\end{array}
解:Dixon多项式为$3ya$.
Dixon矩阵$M=\left[
\begin{array}{cc}
0 & 0 \\
0 & 3 \\
\end{array}
\right]$经删去零行(列)后变为\begin{matrix}&x^0y^1\\a^1b^0&[3]\end{matrix}它的行列式非零.但这并不意味着原方程组无解!原方程组有平凡解$x=y=0$.
在例 7 中，我们看到新 Dixon 矩阵的行列式为零甚至不是方程组有解的必要条件。正如预期的那样，原Dixon 矩阵的行列式为零。

例8.\begin{array}{r}f=x y+x A+x-A^{2}-A+y^{2}+y \\ =y+A+1-A+x+y \\ g=x^{2}+x A-x+x y+y A-y \\ =x+y x-1+A \\ h=x^{2}+x y+2 x-x A-y A-2 A \\ =x+y+2 x-A\end{array}
解:Dixon矩阵为
\begin{matrix}&\mathclap{
\begin{array}{cccccc}
   x^0 y^0 &&&& x^0 y^1 &&&& x^0 y^2&&&&x^1 y^0 &&&& x^1 y^1
\end{array}}\\
\begin{array}{c}
a^0 b^0 \\
a^0 b^1 \\
a^1 b^0 \\
a^1 b^1 \\
a^2 b^0 \\
\end{array}&
\begin{bmatrix}
2 A^2-2 A & 2 A^3+A^2+A & 2 A & 2 A^3+A^2+A & 2 A \\
2 A^2-2 A & 4 A-2 & 2 A-1 & 2 A & 2 A-1 \\
2 A^2 & -2 A^2+5 A-4 & 2 A-3 & -2 A^2+3 A-2 & 2 A-3 \\
2 A & 2 A-1 & 0 & 2 A-3 & 0 \\
2 A & 2 A-1 & 0 & 2 A-3 & 0
\end{bmatrix}\end{matrix}行列式恒为0.实际上,方程组$f(x,y,A)=0,h(x,y,A)=0,g(x,y,A)=0$有解$$(x,y,A)=(0,-2,1),(3,-5,-2),(0,0,0),\left(\frac{1}{2},-\frac{3}{2},\frac{1}{2}\right),\left(\frac{1}{2},0,\frac{1}{2}\right)$$我们看到，在这种情况下，结式如预期的那样为 0，但由于它同样为零，因此不会提供有关方程组的解的信息。

例9.
\begin{array}{c}
f=x (c-2 a)-a x y+(a x)^2+a y+3 c-3 \\
g=2 a^2 x^2-2 a^2 x y-a^3-(a y)^2 \\
h=8 a x-4 a^2 \\
\end{array}
解:Dixon矩阵经移除零行(列)后变为
$$M=\left[\left(
\begin{array}{ccc}
4 a^4 c+24 a^3 c-16 a^5-24 a^3 & -12 a^5 & 12 a^5 \\
8 a^4 c+48 a^3 c+4 a^5-48 a^3 & 24 a^4 & -24 a^4 \\
\end{array}
\right)\right]$$这次$M$连方阵都不是,其行列式未定义.


Dixon方法的可能的问题:

Dixon 的方法仅适用于generic n 次多项式。如果此条件不满足，则可能会面临以下问题：

1.Dixon矩阵是奇异的,其行列式恒为零(例6,8)
2.移除零行(列)后,行列式为零不是方程组有解的必要条件(例7).
3. 移除零行(列)后,连方阵都不是,所以其行列式未定义(例9).

hbghlyj

wseas.us/e-library/conferences/athens1999/Papers/154.pdf
Kapur、Saxena 和 Yang 在一定的前提条件下成功地解决了这三个问题。让我们描述一下他们的主要定理和算法。假设我们有一个包含 $n$ 个变量的 $n+1$ 个多项式的方程组，使得多项式的系数本身就是有限个参数的多项式。令 $M$ 为如前得到的 Dixon 矩阵。令 $M'$ 是一个阶梯形矩阵，通过使用除行缩放之外的初等行变换从 $M$ 获得。 （这样的归约总是可能的。）令 $D$ 是 $M'$ 的所有pivot的乘积。

前提条件：假设Dixon 矩阵中,单项式$1=x_1^0 x_2^0 \ldots$对应的列不是其余列的线性组合。 （在我们的符号中，这是 Dixon 矩阵的第一列。）

定理 10：[Kapur-Saxena-Yang] 如果前提条件为真，则 $D=0$ 是公共零点存在的必要条件。这个定理产生了一个简单的算法来获得必要条件 $D=0$，我们称之为 Kapur-Saxena-Yang结式。
算法（计算 Kapur-Saxena-Yang 结式）
输入：一组多项式，具有数字或参数系数。
1. 计算 Dixon 矩阵 M。如果前提条件成立，则继续。
2. 行约简 M(不经过行缩放)得到行阶梯形 M'
3. 计算M'的pivot的乘积 D.
输出： D 是 Kapur-Saxena-Yang Dixon 结式。它为零是给定的方程组有解的必要条件。
实践中,对前提条件的检测是简单的,它等价于M 的简化行阶梯形的第一行为[1 0 0 ⋯ 0] 。


现在让我们通过计算 Kapur-Saxena-Yang Dixon 结式 D 来重做例 3、4、8、9。

例11(重做例3)
解：由于 Dixon 矩阵的第一列不是第二列的标量倍数，因此适用定理的前提条件。因此，我们可以继续约简而不经过行缩放来得到$$\left[
\begin{array}{cc}
4 A^4+5 A^3-21 A^2 & 4 A^3+11 A^2-3 A \\
0 & -\frac{8 \left(2 A^2+7 A+3\right)}{4 A-7} \\
\end{array}\right]$$
计算pivot之积:$D=-8 A^2 (A+3)^2 (2 A+1)$
令$D=0$解得$A=-3,-3,-\frac{1}{2},0,0$(答案和以前一样)

在下一个例子中，前提条件不满足，因此该定理不适用。但是，如果我们照常进行行归约，我们会得到方程组的某些解的 $A$值！
例12(重做例4)
解:前提条件不满足，因此该定理不适用。但是，如果我们照常进行行归约，我们会得到
$\left[
\begin{array}{cc}
2 A^2+6 A & -2 A^2-6 A \\
0 & 0 \\
\end{array}
\right]$
令pivot之积$2 A^2+6 A=2 A(A+3)$为零,解得$A=0,-3$.
实际上,方程组的解为$(x,A)=(3,-3),(0,0),(1,A)$,这次只有 (1,A) 没有从Dixon结式获得。

例13(重做例8)
解：首先我们通过证明 Dixon 矩阵 $M$ 的第一列不是剩余列的线性组合来证明定理的前提条件成立
实际上，如果我们在 M 中令 A=-1 并进行行约简，我们得到：
$M_{\{A=-1\}}=\left[
\begin{array}{ccccc}
4 & -2 & -2 & -2 & -2 \\
4 & -6 & -3 & -2 & -3 \\
2 & -11 & -5 & -7 & -5 \\
-2 & -3 & 0 & -5 & 0 \\
-2 & -3 & 0 & -5 & 0 \\
\end{array}
\right]\left[
\begin{array}{ccccc}
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 \\
\end{array}
\right]$
我们看到从$M_{\{A=-1\}}{\bf w}=0$能推出$w_1=0$,所以$M$的第一列不是其他列的线性组合.所以，前提条件成立并且定理适用。
Dixon 矩阵的行归约产生作为pivot乘积的 Dixon-Kapur-Saxena-Yang 结式：
$D=8 (2 A-1)^2 (A (1-A)) (A+2)$
令$D=0$得$A=-2,0,1,\frac{1}{2},\frac{1}{2}$

方程组$f(x,y,A)=0, h(x,y,A)=0, g(x,y,A)=0$的解为\begin{array}{c}
(x,y,A)=(0,-2,1),(3,-5,-2),(0,0,0),\left(\frac{1}{2},-\frac{3}{2},\frac{1}{2}\right),\left(\frac{1}{2},0,\frac{1}{2}\right) \\
\end{array}这一次，解的所有 $A$ 值都被 $D$ 检测到。回想一下，在这种情况下，经典的 Dixon 结式恒为零，并且没有产生关于解的信息。

例14(重做例9)回想一下，Dixon 矩阵是矩形的。由于第一列不是其余列的线性组合，因此前提条件成立并且定理适用。归约后pivot之积产生 Dixon 结式：
$D=48 a^7 \left(a^3-8 a^2+14 a c+2 (a c)^2-12 a+12 c-12\right)$

让我们研究最后一个前提条件不满足的例子。在这种情况下，只有平凡解被检测到。
例15\begin{array}{c}f=x y z \\ g=x^{2}-z^{2} \\ h=x+y+z\end{array}我们消去$x,y$.Dixon多项式为$-a^2 x z-a^2 y z-a^2 z^2-x (a z)^2-(a z)^3+(y z)^3$.
Dixon矩阵$$M=\left[
\begin{array}{ccc}
0 & z^3 & 0 \\
-z^3 & 0 & -z^2 \\
-z^2 & -z & -z \\
\end{array}
\right]$$的行列式恒为0。请注意，在这种情况下，前提条件不满足（第一列是最后一列的 $z$ 倍），因此该定理不适用。如果我们约简并取pivot的乘积，我们会得到$z^6$，在 $z=0$ 时为 0。实际上,方程组的解为$(x,y,z)=(-z,0,z),\quad z$任意.


经典的 Dixon 结式及其 K-S-Y 推广都存在一个问题:结式往往含有无关因式。在本节中，我们找到了一些简单例子的无关因式。我们通过 K-S-Y 方法和使用 Gröbner 基 [Buchberger 1985] 计算结果并比较答案。关于纯字典顺序的 Gröbner 基的结果总是没有无关因式。但，这种 Gröbner 基的计算比较耗费资源。 Mathematica 的 GroebnerBasis 命令可以有效地计算对于纯反向字典顺序的 Gröbner 基，但即使如此，对于具有超过 3 或 4 个变量的次数 >3 的多项式方程组，人们也很少能计算结式。对于一般多项式，如果 $f$ 和 $g$ 都不是常数，则无关因式（不管符号）为$i^{|\deg  f-\deg  g|}$
其中 $I$ 是最高次多项式的首项系数（参见 [Kapur 和 Lakshman]）。
非generic多项式的示例 非generic多项式的无关因式更难预测，如表 1 所示。模式变得越来越复杂，尤其是对于多元多项式。

更复杂的情形 在表2中,我们展示了无关因式更难预测的示例。在第四个和第五个例子中，额外的因式是整个 Dixon 结式！ Bruno Buchberger 在他的几篇出版物中使用了最后一个示例来解释如何计算 Gröbner 基。
其中,@=$64 z^5+48 z^4+1100 z^3+225 z^2+3812 z-1796$

hbghlyj

青青子衿 发表于 2019-11-5 04:31
\left(2{p_{\overset{\,}{2}}}\!^6-6{p_{\overset{\,}{2}}}\!^3{p_{\overset{\,}{3}}}\!^2+{p_{\overset{\,}{3}}}\!^4+3{p_{\overset{\,}{2}}}\!^2p_{\overset{\,}{3}}p_{\overset{\,}{5}}\right)^2
=\left(2{p_{\overset{\,}{2}}}\!^4-3p_{\overset{\,}{2}}{p_{\overset{\,}{3}}}\!^2+p_{\overset{\,}{3}}p_{\overset{\,}{5}}\right)^2\left({p_{\overset{\,}{2}}}\!^4-3p_{\overset{\,}{2}}{p_{\overset{\,}{3}}}\!^2+2p_{\overset{\,}{3}}p_{\overset{\,}{5}}\right)

这里没加$$，只显示了代码