对称协正三次型的零点算法

Zero point algorithm for symmetric co-positive cubic forms

摘要

协正二次型 （或协正矩阵）的判定是NP难问题，因而协正二次型零点的计算也是NP难的. 但对称协正二次型零点的计算存在高效算法. 类比于此，研究了更广泛的对称三次型，建立了一个计算对称协正三次型零点的算法. 这个算法的时间复杂度关于变元数n是O（n）.

Abstract

The determination of co-positive quadratic forms （or co-positive matrices） is an NP-hard problem， so the calculation of zero points of co-positive quadratic forms is also NP-hard. However， there exists a more efficient algorithm for computing zero points of symmetric co-positive quadratic forms. By analogy， this paper studied the more extensive symmetric cubic forms. The main work was to establish an algorithm for calculating zero points of symmetric co-positive cubic forms. The time complexity of this algorithm was O（n） with respect to the number of variables n.

关键词

对称形式 / 协正形式 / 三次形式 / 实零点

Key words

symmetric form / co-positive form / cubic form / real zero point

1 引言

协正型 ^［1］是指一类在非负向量上取值非负的齐次多项式. 为了清晰表述这一概念，首先需要引入一些基本的记号和术语.

用{\mathrm{\Delta }}_n记标准单形，即

\begin{array}{l}{\mathrm{\Delta }}_n:=\{x\in {\mathbb{R}}^n:x_{\mathrm{1}}+\cdots +x_n=\mathrm{1},x_i\ge \mathrm{0},\\ i=\mathrm{1},\dots ,n\},\end{array}

型（齐次多项式） f\in \mathbb{R}[x_{\mathrm{1}},\cdots ,x_n]被称为是协正的，如果f在标准单形上的值都是非负的，即

\underset{x\in {\mathrm{\Delta }}_n}{\forall }f(x)\ge \mathrm{0}.

Z(f,{\mathrm{\Delta }}_n)表示f在标准单形上的零点， 即

Z(f,{\mathrm{\Delta }}_n):=\{x\in {\mathrm{\Delta }}_n:f(x)=\mathrm{0}\}.

一般地， Z(f,S) 表示f在点集S\subseteq {\mathbb{R}}^n 上的零点.

协正型，尤其是协正低次型是近年来组合优化^［2］、非凸优化^［3］、多项式优化^［4-6］、张量分析^［7-8］等理论领域的前沿研究方向. 本文将深入探究协正三次型的零点算法.

S_{(n,k)} 记x_{\mathrm{1}},\dots ,x_n 的第k 个Newton 幂和， 即

S_{(n,k)}=x_{\mathrm{1}}^k+\cdots +x_n^k.

根据对称多项式基本定理， 对称三次型可以表示为如下形式

f=a_{\mathrm{0}}{S}_{(n,\mathrm{3})}+a_{\mathrm{1}}{S}_{(n,\mathrm{1})}{S}_{(n,\mathrm{2})}+a_{\mathrm{2}}{S}_{(n,\mathrm{1})}^{\mathrm{3}},(a_{\mathrm{0}},a_{\mathrm{1}},a_{\mathrm{2}})\in {\mathbb{R}}^{\mathrm{3}}\backslash (\mathrm{0,0},\mathrm{0}).

当n\ge \mathrm{3} 时，上述表示是唯一的.

对称三次型有两个基本问题： 1） a_{\mathrm{0}},a_{\mathrm{1}},a_{\mathrm{2}} 满足什么条件时， f 是协正的；2） 如果f是协正的， 如何找到零点集Z(f,{\mathrm{\Delta }}_n).

关于第1个问题，1987年，Choi M D等在文献［9］中讨论了对称三元六次偶型（等价于对称协正三元三次型，即n=\mathrm{3}的情况）. 1999 年，Harris W R 在文献［10］中讨论对称三元偶形式时，也给出了类似的结果. 2005年， Timofte ^［11］获得了一般的结果. 他证明了如下定理.

定理1.1^［11］ 　对称三次型f\in \mathbb{R}[x_{\mathrm{1}},\cdots ,x_n]是协正的，当且仅当

f(\underset{k}{\underset{}{\underbrace{\mathrm{1},\dots ,\mathrm{1}}}},\mathrm{0},\dots ,\mathrm{0})\ge \mathrm{0},k=\mathrm{1},\dots ,n.

利用本文的引理2.7，我们将给出定理1.1 （推论2.8）的另一个证明.

本文将主要讨论第2个问题. 一般地，计算多变量协正型的零点是困难的，即使对于低次的情况也是如此.在二次协正型的非对称情况，可以证明计算其零点是NP难问题. 注意到二次协正型的判定（等价于协正矩阵的判定）已经是NP难问题^［12-13］，而计算其零点是建立在协正性基础之上的（零点属性+任意非零点的符号蕴含了协正性），所以它也是NP难的. 令人惊讶的是，在三次对称的情况，计算其零点存在线性时间复杂度的算法.

本文的主要理论结果是证明了三次对称协正型的零点集Z(f,{\mathrm{\Delta }}_n)只有\mathrm{2}n+\mathrm{1}种可能. 详细的论证在第二节给出. 第三节，给出了计算Z(f,{\mathrm{\Delta }}_n)的快速算法. 最后是总结和进一步工作计划.

2 主要定理及其证明

在给出主要定理之前，还需要定义一些记号并建立几个引理.

定义2.1 　设集合J\ne \mathrm{\varnothing }是\{\mathrm{1},\dots ,n\}的子集，其补集J^c=\{\mathrm{1},\dots ,n\}\backslash J.

① 标准单形的面F_J=\{x\in {\mathrm{\Delta }}_n:x_{j^{\text{'}}}=\mathrm{0},j^{\text{'}}\in J^c\}.

② 面F_J 的相对内部F_J^o=\{x\in F_J:x_j>\mathrm{0},j\in J\}.

③ 型f\in \mathbb{R}[x_{\mathrm{1}},\dots ,x_n]相对于面F_J的子型f_J=f{{|}_{x_{j^{\text{'}}}}}_{=\mathrm{0},j^{\text{'}}\in J^c}

④ 面F_{\{\mathrm{1},\dots ,k\}}的中心c_k=(\underset{k}{\underbrace{\frac{\mathrm{1}}{k},\dots ,\frac{\mathrm{1}}{k}}},\mathrm{0},\dots ,\mathrm{0}),k=\mathrm{1},\dots ,n，并约定c_{n+\mathrm{1}}=c_{\mathrm{1}}.

⑤ \mathrm{c}\mathrm{h}S记点集S\subseteq {\mathbb{R}}^n的凸包.

引理2.2　 设{\alpha }_{\mathrm{1}},\dots ,{\alpha }_n\in {\mathbb{R}}^n(n\ge \mathrm{2})是仿射独立的. a,b\in \mathbb{R}不相等， \gamma \in {\mathbb{R}}^n. 又设

{\beta }_{\mathrm{1}}=\left({\alpha }_{\mathrm{1}},a\right),\dots ,{\beta }_n=\left({\alpha }_n,a\right),{\beta }_{n+\mathrm{1}}=\left(\gamma ,b\right).

则{\beta }_{\mathrm{1}},\dots ,{\beta }_{n+\mathrm{1}} 也是仿射独立的.

证明　 注意到{\alpha }_{\mathrm{1}},\dots ,{\alpha }_n 仿射独立等价于凸包\mathrm{c}\mathrm{h}\{{\alpha }_{\mathrm{1}},\dots ,{\alpha }_n\}是(n-\mathrm{1})-单形.于是\mathrm{c}\mathrm{h}\{{\beta }_{\mathrm{1}},\dots ,{\beta }_n\} 也是(n-\mathrm{1})-单形并且位于超平面x_{n+\mathrm{1}}-a=\mathrm{0}上。因为a\ne b，所以{\beta }_{n+\mathrm{1}}并不位于超平面x_{n+\mathrm{1}}-a=\mathrm{0}上.所以\mathrm{c}\mathrm{h}\{{\beta }_{\mathrm{1}},\dots ,{\beta }_n,{\beta }_{n+\mathrm{1}}\}是一个n-单形.也就是说{\beta }_{\mathrm{1}},\dots ,{\beta }_{n+\mathrm{1}}是仿射独立的.

定义2.3

① P_n 记集合\{\mathrm{1,2},\dots ,n\}上的全对称置换群.

② 给定点p=(p_{\mathrm{1}},\dots ,p_n)\in {\mathbb{R}}^n和置换\sigma \in P_n， p_{\sigma }记点(p_{\sigma (\mathrm{1})},\dots ,p_{\sigma (n)}).

引理2.4　 对n\ge \mathrm{2}，如果p\in {\mathrm{\Delta }}_n不是标准单形{\mathrm{\Delta }}_n的中心（p\ne c_n），则存在n个置换{\sigma }_{\mathrm{1}},\dots ,{\sigma }_n\in P_n 使得凸包\mathrm{c}\mathrm{h}\left\{p_{{\sigma }_{\mathrm{1}}},\dots ,p_{{\sigma }_n}\right\}是一个(n-\mathrm{1})-单形.

证明　 将对变元数n实施归纳法.

当n=\mathrm{2}时，假设p=(p_{\mathrm{1}},p_{\mathrm{2}})\in {\mathrm{\Delta }}_{\mathrm{2}}不是标准单形{\mathrm{\Delta }}_{\mathrm{2}}的中心，即p\ne (\mathrm{1}/\mathrm{2,1}/\mathrm{2}).于是， \mathrm{c}\mathrm{h}\left\{p_{\sigma },\sigma \in P_{\mathrm{2}}\right\}=\mathrm{c}\mathrm{h}\left\{(p_{\mathrm{1}},p_{\mathrm{2}}),(p_{\mathrm{2}},p_{\mathrm{1}})\right\}.注意到(p_{\mathrm{1}},p_{\mathrm{2}})\ne (p_{\mathrm{2}},p_{\mathrm{1}})，所\mathrm{c}\mathrm{h}\left\{p_{\sigma },\sigma \in P_{\mathrm{2}}\right\}是一条线段，即\mathrm{1}-单形.

现在假设n\ge \mathrm{3}时结论是对的.下面证明当n+\mathrm{1}时结论仍然是对的.

设p\in {\mathrm{\Delta }}_{n+\mathrm{1}}不是标准单形{\mathrm{\Delta }}_{n+\mathrm{1}}的中心. 于是存在i,j,k满足p_i\ne p_j且p_i\ne p_k.不失一般性，我们假设p_{\mathrm{1}}\ne p_n并且p_{\mathrm{1}}\ne p_{n+\mathrm{1}}. 令p^{\text{'}}=(p_{\mathrm{1}}/A,\dots ,p_n/A),A={\displaystyle \sum _{i=\mathrm{1}}^n}{p}_i. 因为p_{\mathrm{1}}\ne p_n，所以p^{\text{'}}不是{\mathrm{\Delta }}_n的中心. 由归纳假设，存在n个置换{\sigma }_{\mathrm{1}},\dots ,{\sigma }_n\in P_n满足\mathrm{c}\mathrm{h}\{p_{{\sigma }_{\mathrm{1}}}^{\mathrm{\text{'}}},\dots ,p_{{\sigma }_n}^{\mathrm{\text{'}}}\}是一个(n-\mathrm{1})-单形. 所以\mathrm{c}\mathrm{h}\{A{p}_{{\sigma }_{\mathrm{1}}}^{\mathrm{\text{'}}},\dots ,A{p}_{{\sigma }_n}^{\mathrm{\text{'}}}\}也是一个(n-\mathrm{1})-单形. 构造点q({\sigma }_{\mathrm{1}})=(A{p}_{{\sigma }_{\mathrm{1}}}^{\mathrm{\text{'}}},p_{n+\mathrm{1}}),\dots ,q({\sigma }_n)=(A{p}_{{\sigma }_n}^{\mathrm{\text{'}}},p_{n+\mathrm{1}}),q({\sigma }_{n+\mathrm{1}})=(p_{n+\mathrm{1}},p_n,\dots ,p_{\mathrm{1}}). 明显地， q({\sigma }_i),i=\mathrm{1},\dots ,n+\mathrm{1}都是p的置换. 由引理2.2， \mathrm{c}\mathrm{h}\{q({\sigma }_{\mathrm{1}}),\dots ,q({\sigma }_{n+\mathrm{1}})\}是一个n-单形. 根据归纳法原理，完成了引理的证明.

引理2.5　 对n\ge \mathrm{2}， 如果p\in {\mathrm{\Delta }}_n不是标准单形{\mathrm{\Delta }}_n的中心， 则

\mathrm{d}\mathrm{i}\mathrm{m}\mathrm{c}\mathrm{h}\left\{p_{\sigma },\sigma \in P_n\right\}=n-\mathrm{1}.

证明　 根据引理2.4， \mathrm{c}\mathrm{h}\left\{p_{\sigma },\sigma \in P_n\right\} 包含了(n-\mathrm{1})-单形，所以\mathrm{d}\mathrm{i}\mathrm{m}\mathrm{c}\mathrm{h}\left\{p_{\sigma },\sigma \in P_n\right\}\ge n-\mathrm{1}.另一方面，\mathrm{c}\mathrm{h}\left\{p_{\sigma },\sigma \in P_n\right\}\subseteq {\mathrm{\Delta }}_n，所以\mathrm{d}\mathrm{i}\mathrm{m}\mathrm{c}\mathrm{h}\left\{p_{\sigma },\sigma \in P_n\right\}\le \mathrm{d}\mathrm{i}\mathrm{m}{\mathrm{\Delta }}_n=n-\mathrm{1}.

综合上述，得到\mathrm{d}\mathrm{i}\mathrm{m}\mathrm{c}\mathrm{h}\left\{p_{\sigma },\sigma \in P_n\right\}=n-\mathrm{1}.

引理2.6　 设f\in \mathbb{R}[x_{\mathrm{1}},\cdots ,x_n]是对称协正三次型， F是{\mathrm{\Delta }}_n的一个面，则Z(f,F^o)是一个凸集.

证明　 设p,q\in Z(f,F^o)，只需证\lambda p+\mu q\in Z(f,F^o)(\lambda \ge \mathrm{0},\mu \ge \mathrm{0},\lambda +\mu =\mathrm{1})即可.

设F=F_J,J\subseteq \{\mathrm{1},\dots ,n\}.注意到p,q\in F^o意味着对j\notin J有p_j=q_j=\mathrm{0}，对j\in J有p_j>\mathrm{0},q_j>\mathrm{0}.

子型f_J如果是\mathrm{0}型，则显然有\lambda p+\mu q\in Z(\mathrm{0},F^o)=Z(f_J,F^o)=Z(f,F^o).

如果f_J不是\mathrm{0}型， 则f_J也是协正型， 并且p,q都是f_J的极小值点. 由于f_J也是三次型， 所以p,q都是f_J的2重点. 考虑直线l:=\lambda p+\mu q， 看到f在l上的取值必须是0. 否则直线l与三次型f_F的相交重数将大于等于4（与p,q各相交2次）. 这样证明了\{\lambda p+\mu q\}\bigcap F^o\subseteq Z(f_J,F^o)=Z(f,F^o).

引理 2.7　 设f\in \mathbb{R}[x_{\mathrm{1}},\dots ,x_n]是三次对称协正型， F是{\mathrm{\Delta }}_n的一个面. 则有

① Z(f,F^o)=\mathrm{\varnothing }或c或F^{\mathrm{0}}， c是面F的中心.

② 如果Z(f,F^o)=F^o，则\mathrm{d}\mathrm{i}\mathrm{m}(F)\le \mathrm{1}.即F只能是单形{\mathrm{\Delta }}_n的棱或顶点.

证明　 由对称性，不失一般性，假设面 F=F_J,J=\left\{\mathrm{1},...,k\right\},\mathrm{1}\le k\le n.

首先要证明Z(f,F^o)是 \mathrm{\varnothing },c,F^o中的一个.

假设Z(f,F^o)\ne \mathrm{\varnothing }并且Z(f,F^o)\ne c.则只需证明Z(f,F^o)=F^o.

断言1： \mathrm{d}\mathrm{i}\mathrm{m}Z\left(f,F^o\right)=\mathrm{d}\mathrm{i}\mathrm{m}{F}^o.

断言的证明：明显地\mathrm{d}\mathrm{i}\mathrm{m}Z\left(f,F^o\right)\le \mathrm{d}\mathrm{i}\mathrm{m}{F}^o.因此只需证\mathrm{d}\mathrm{i}\mathrm{m}Z\left(f,F^o\right)\ge \mathrm{d}\mathrm{i}\mathrm{m}{F}^o.

令p\in Z(f,F^o)满足p\ne c.注意到p={(\stackrel{\sim }{p},\underset{n-k}{\underbrace{\mathrm{0},\dots ,\mathrm{0}}})}^{\mathrm{\top }}， \stackrel{\sim }{p}=\left(p_{\mathrm{1}},...,p_k\right)满足p_i\ne p_j,\mathrm{1}\le i\ne j\le k.由对称性，对每个置换\sigma \in P_k，设p(\sigma )={(\stackrel{\sim }{p_{\sigma }},\underset{n-k}{\underbrace{\mathrm{0},\dots ,\mathrm{0}}})}^{\mathrm{\top }}\inZ(f,F^o).由引理2.6， Z(f,F^o)是凸集，于是有Z(f,F^o)\supseteq \mathrm{c}\mathrm{h}(p(\sigma ),\sigma \in P_k). 因此\mathrm{d}\mathrm{i}\mathrm{m}Z(f,F^o)\ge \mathrm{d}\mathrm{i}\mathrm{m}\mathrm{c}\mathrm{h}(p(\sigma ),\sigma \in P_k).从引理2.5 \mathrm{d}\mathrm{i}\mathrm{m}\mathrm{c}\mathrm{h}(p(\sigma ),\sigma \in P_k)=k-\mathrm{1}=\mathrm{d}\mathrm{i}\mathrm{m}{F}^o. 所以\mathrm{d}\mathrm{i}\mathrm{m}Z(f,F^o)\ge \mathrm{d}\mathrm{i}\mathrm{m}{F}^o.

熟知如果f_J不恒为\mathrm{0}，则.现在\mathrm{d}\mathrm{i}\mathrm{m}Z\left(f,F^o\right)=\mathrm{d}\mathrm{i}\mathrm{m}{F}^o，于是f_J恒为\mathrm{0}.所以Z(f,F^o)=Z(f_J,F^o)=Z(\mathrm{0},F^o)=F^o.

如果Z(f,F^o)=F^o，则\mathrm{d}\mathrm{i}\mathrm{m}F\le \mathrm{1}.

回忆对称三次型的另一个表示形式， 使用单项式基

注意到，上述表示不能消去任何单项式.

如果f不是\mathrm{0}型， 则b_{\mathrm{0}},b_{\mathrm{1}},b_{\mathrm{2}}至少有一个不是\mathrm{0}. 注意到

\begin{array}{l}f(x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},\mathrm{0},\dots ,\mathrm{0})=b_{\mathrm{0}}(x_{\mathrm{1}}^{\mathrm{3}}+x_{\mathrm{2}}^{\mathrm{3}}+x_{\mathrm{3}}^{\mathrm{3}})+\\ b_{\mathrm{1}}\left(x_{\mathrm{1}}{x}_{\mathrm{2}}(x_{\mathrm{1}}+x_{\mathrm{2}})+x_{\mathrm{1}}{x}_{\mathrm{3}}(x_{\mathrm{1}}+x_{\mathrm{3}})+\right.\\ \left.x_{\mathrm{2}}{x}_{\mathrm{3}}(x_{\mathrm{2}}+x_{\mathrm{3}})\right)+b_{\mathrm{2}}{x}_{\mathrm{1}}{x}_{\mathrm{2}}{x}_{\mathrm{3}}.\end{array}

因此f(x_{\mathrm{1}},x_{\mathrm{2}},x_{\mathrm{3}},\mathrm{0},\dots ,\mathrm{0})是非\mathrm{0}多项式. 即对k\ge \mathrm{3}， f(x_{\mathrm{1}},\dots ,x_k,\mathrm{0},\dots ,\mathrm{0})都是非\mathrm{0}多项式，由此推出.

因此如果Z(f,F^o)=F^o， 则k\le \mathrm{2}. 即 \mathrm{d}\mathrm{i}\mathrm{m}{F}^o=\mathrm{d}\mathrm{i}\mathrm{m}F\le \mathrm{1}.

推论2.8 （定理1.1）　 三次对称型f\in \mathbb{R}[x_{\mathrm{1}},\cdots ,x_n]是协正的当且仅当

f(\underset{k}{\underbrace{\mathrm{1},\dots ,\mathrm{1}}},\mathrm{0},\dots ,\mathrm{0})\ge \mathrm{0},k=\mathrm{1},\dots ,n.

证明“\Rightarrow”： f是三次对称协正型\Rightarrowf(\underset{k}{\underbrace{\mathrm{1},\dots ,\mathrm{1}}},\mathrm{0},\dots ,\mathrm{0})\ge \mathrm{0},k=\mathrm{1},\dots ,n，是显然的.

下面给出另一个方向“\Leftarrow”的证明. 我们来证明它的等价命题， 即

如果f不是协正的，则f(\underset{k}{\underbrace{\mathrm{1},\dots ,\mathrm{1}}},\mathrm{0},\dots ,\mathrm{0}),k=\mathrm{1},\dots ,n中至少有一个小于\mathrm{0}.

设函数f在标准单形{\mathrm{\Delta }}_n上的最小值为\lambda， 因为f不是协正的， 所以. 构造一个新的对称三次型

\stackrel{\sim }{f}=f-\lambda (x_{\mathrm{1}}+\cdots +x_n{)}^{\mathrm{3}}.

显然\stackrel{\sim }{f}是协正的并且Z(\stackrel{\sim }{f},{\mathrm{\Delta }}_n)\ne \mathrm{\varnothing }. 注意到Z(\stackrel{\sim }{f},{\mathrm{\Delta }}_n)有如下分解式

Z(\stackrel{\sim }{f},{\mathrm{\Delta }}_n)=\underset{J\subseteq \{\mathrm{1},\cdots ,n\}}{\cup }Z(\stackrel{\sim }{f},F_J^o).

根据引理2.7， Z(\stackrel{\sim }{f},{\mathrm{\Delta }}_n)至少包含了c_{\mathrm{1}},\dots ,c_n中的一个 （注意c_{\mathrm{1}},c_{\mathrm{2}}\in F_{\{\mathrm{1,2}\}},\mathrm{d}\mathrm{i}\mathrm{m}{F}_{\{\mathrm{1,2}\}}=\mathrm{1}）. 也就是存在正整数t满足\stackrel{\sim }{f}(c_t)=\mathrm{0}， 即

因为齐次性， .

定义2.9　 设S是{\mathbb{R}}^n的子集， \overline{S}=\underset{\sigma \in P_n}{\cup }\left\{\sigma \left(x\right):x\in S\right\}称为S的置换闭包.

例如(\mathrm{1}/\mathrm{2,1}/\mathrm{2,0})的置换闭包是

\overline{(\mathrm{1}/\mathrm{2},\mathrm{1}/\mathrm{2},\mathrm{0})}=\{(\mathrm{1}/\mathrm{2},\mathrm{1}/\mathrm{2},\mathrm{0}),(\mathrm{1}/\mathrm{2},\mathrm{0},\mathrm{1}/\mathrm{2}),(\mathrm{0},\mathrm{1}/\mathrm{2},\mathrm{1}/\mathrm{2})\}.

引理2.10　 记n元三次对称型^［3］

f_{n,k}=\left\{\begin{array}{lll}k(k+\mathrm{1})S_{(n,\mathrm{3})}-(\mathrm{2}k+\mathrm{1})S_{(n,\mathrm{1})}{S}_{(n,\mathrm{2})}+S_{(n,\mathrm{1})}^{\mathrm{3}}& \mathrm{i}\mathrm{f}& k=\mathrm{1},\dots ,n-\mathrm{1}\\ -k{S}_{(n,\mathrm{3})}+(k+\mathrm{1})S_{(n,\mathrm{1})}{S}_{(n,\mathrm{2})}-S_{(n,\mathrm{1})}^{\mathrm{3}}& \mathrm{i}\mathrm{f}& k=n\end{array}\right.

这里n\ge \mathrm{3}并且\mathrm{1}\le k\le n. 有

① f_{n,k}是协正的.

② f_{n,k}的零点由下式给出

Z(f_{n,k},{\mathrm{\Delta }}_n)=\left\{\begin{array}{lll}\overline{\mathrm{c}\mathrm{h}(e_{\mathrm{1}},e_{\mathrm{2}})}& \mathrm{i}\mathrm{f}& k=\mathrm{1};\\ \overline{\left\{c_k,c_{k+\mathrm{1}}\right\}}& \mathrm{i}\mathrm{f}& k=\mathrm{2},\dots ,n.\end{array}\right.

③ g_{n,k}=f_{n,k}+f_{n,k+\mathrm{1}}的零点由下式给出

Z(g_{n,k},{\mathrm{\Delta }}_n)=\overline{\{c_{k+\mathrm{1}}\}},k=\mathrm{1},\dots ,n .

证明　 ①使用推论2.8，直接验证可得.

②使用引理2.7，对{\mathrm{\Delta }}_n的面和面的中心进行检查即可.

③ 因为协正性， 我们有

Z(g_{n,k},{\mathrm{\Delta }}_n)=Z(f_{n,k},{\mathrm{\Delta }}_n)\bigcap Z(f_{n,k+\mathrm{1}},{\mathrm{\Delta }}_n).

由②的结论立得.

定理2.11　 f\in \mathbb{R}[x_{\mathrm{1}},\dots ,x_n]是三次对称协正型.则Z(f,{\mathrm{\Delta }}_n)是下面\mathrm{2}n+\mathrm{1}个点集之一：

\begin{array}{l}\mathrm{\varnothing },C_{\mathrm{1}},\dots ,C_n,C_{\mathrm{2}}\bigcup C_{\mathrm{3}},C_{\mathrm{3}}\bigcup C_{\mathrm{4}},\dots ,\\ C_n\cup C_{\mathrm{1}},L,\end{array}（2.1）

这里C_k=\overline{\{c_k\}}， L=\overline{\mathrm{c}\mathrm{h}(e_{\mathrm{1}},e_{\mathrm{2}})}.

证明　 根据引理2.8，如果Z(f,{\mathrm{\Delta }}_n)\ne \mathrm{\varnothing }，则Z(f,{\mathrm{\Delta }}_n)是C_{\mathrm{1}},\cdots ,C_n,L的组合并集.

断言1：不存在三次对称协正型f满足.

利用型

f=a_{\mathrm{0}}{S}_{(n,\mathrm{3})}+a_{\mathrm{1}}{S}_{(n,\mathrm{1})}{S}_{(n,\mathrm{2})}+a_{\mathrm{2}}{S}_{(n,\mathrm{1})}^{\mathrm{3}},（2.2）

通过简单的计算， 有

f(c_i)=a\frac{\mathrm{1}}{i^{\mathrm{2}}}+b\frac{\mathrm{1}}{i}+c.

根据假设f(c_i)=\mathrm{0},f(c_j)=\mathrm{0},f(c_k)=\mathrm{0}， 获得关于a_{\mathrm{0}},a_{\mathrm{1}},a_{\mathrm{2}}的齐次线性方程组

\left(\begin{array}{ccc}\frac{\mathrm{1}}{i^{\mathrm{2}}}& \frac{\mathrm{1}}{i}& \mathrm{1}\\ \frac{\mathrm{1}}{j^{\mathrm{2}}}& \frac{\mathrm{1}}{j}& \mathrm{1}\\ \frac{\mathrm{1}}{k^{\mathrm{2}}}& \frac{\mathrm{1}}{k}& \mathrm{1}\end{array}\right)\left(\begin{array}{c}{a}_{\mathrm{0}}\\ a_{\mathrm{1}}\\ a_{\mathrm{2}}\end{array}\right)=\mathrm{0}.

它有非零解的充分必要条件是行列式

D=\left|\begin{array}{ccc}\frac{\mathrm{1}}{i^{\mathrm{2}}}& \frac{\mathrm{1}}{i}& \mathrm{1}\\ \frac{\mathrm{1}}{j^{\mathrm{2}}}& \frac{\mathrm{1}}{j}& \mathrm{1}\\ \frac{\mathrm{1}}{k^{\mathrm{2}}}& \frac{\mathrm{1}}{k}& \mathrm{1}\end{array}\right|=\mathrm{0}.

但是， 当时

D=\frac{(k-j)(i-k)(i-j)}{ijk}\ne \mathrm{0}.

所以满足条件的f不存在.

断言2： 不存在三次对称协正型f满足

假设存在满足要求的f， 则f(c_i)=\mathrm{0},f(c_j)=\mathrm{0}. 解出a_{\mathrm{0}},a_{\mathrm{1}},a_{\mathrm{2}}. 得到

a_{\mathrm{0}}=ij{a}_{\mathrm{2}},a_{\mathrm{1}}=-(i+j)a_{\mathrm{2}}.

代入（2.2）， 有

f=a_{\mathrm{2}}\left(ij{S}_{n,\mathrm{3}}-(i+j)S_{(n,\mathrm{1})}{S}_{(n,\mathrm{2})}+S_{(n,\mathrm{1})}^{\mathrm{3}}\right).

如果a_{\mathrm{2}}>\mathrm{0}， 考虑， 计算

所以f不是协正的.

如果， 则考虑f(c_{\mathrm{1}}),f(c_n). 由于所以(i,j)\ne (\mathrm{1},n). 计算

f(c_{\mathrm{1}})=a_{\mathrm{2}}(j-\mathrm{1})(i-\mathrm{1}),f(c_n)=a_{\mathrm{2}}(j-n)(i-n).

看到， ， 至少有一个成立，即f也不是协正的.

断言3：不存在三次对称协正型f满足C_i\bigcup L\subseteq Z(f,{\mathrm{\Delta }}_n),\mathrm{3}\le i\le n.

注意到c_{\mathrm{1}},c_{\mathrm{2}}\in L，根据断言1知道断言3成立.

断言4：如果C_{\mathrm{1}}\bigcup C_{\mathrm{2}}\subseteq Z(f,{\mathrm{\Delta }}_n)，则L\subseteq Z(f,{\mathrm{\Delta }}_n).

根据f(c_{\mathrm{1}})=\mathrm{0},f(c_{\mathrm{2}})=\mathrm{0}， 得到线性方程组

\left\{\begin{array}{l}{a}_{\mathrm{0}}-a_{\mathrm{1}}+a_{\mathrm{2}}=\mathrm{0}\\ a_{\mathrm{0}}/\mathrm{4}-a_{\mathrm{1}}/\mathrm{2}+a_{\mathrm{2}}=\mathrm{0}.\end{array}\right.

它的解是： a_{\mathrm{0}}=\mathrm{2}{a}_{\mathrm{2}},a_{\mathrm{1}}=-\mathrm{3}{a}_{\mathrm{2}}. 代入（2.2）， 有

f=a_{\mathrm{2}}\left(\mathrm{2}{S}_{(n,\mathrm{3})}-\mathrm{3}{S}_{(n,\mathrm{1})}{S}_{(n,\mathrm{2})}+S_{(n,\mathrm{1})}^{\mathrm{3}}\right).

计算

f(\mu e_{\mathrm{1}}+(\mathrm{1}-\mu )e_{\mathrm{2}})=a_{\mathrm{2}}\left(\mathrm{2}({\mu }^{\mathrm{3}}+{(\mathrm{1}-\mu )}^{\mathrm{3}})-\mathrm{3}({\mu }^{\mathrm{2}}+{(\mathrm{1}-\mu )}^{\mathrm{2}})+\mathrm{1}\right)=\mathrm{0}.

所以\mathrm{c}\mathrm{h}(e_{\mathrm{1}},e_{\mathrm{2}})\subseteq Z(f,{\mathrm{\Delta }}_n). 由对称性L=\overline{\mathrm{c}\mathrm{h}(e_{\mathrm{1}},e_{\mathrm{2}})}\subseteq Z(f,{\mathrm{\Delta }}_n).

根据上面的断言1， 2， 3， 4， 推得： Z(f,{\mathrm{\Delta }}_n)只可能是下面的集合之一

C_{\mathrm{1}},\dots ,C_n,C_{\mathrm{2}}\bigcup C_{\mathrm{3}},C_{\mathrm{3}}\bigcup C_{\mathrm{4}},\dots ,C_n\cup C_{\mathrm{1}},L

另一方面， 根据引理2.10， 很容易构造相应的三次对称协正型f，使得Z(f,{\mathrm{\Delta }}_n)是（2.1）之一.

3 算法

根据定理2.11建立如下算法，它的功能是判定对称三次型的协正性并计算其零点.

算法Co-Sy-Cu-Zeros 的正确性与终止性证明主要从定理2.11获得. 很明显其时间复杂度是O(n)，其中n是变元个数.

4 结论与进一步的工作

利用对称性，成功地证明了对称协正三次型的零点只有有限多种可能，并建立了线性时间复杂度的算法.

鉴于对称协正三次型在控制论、优化理论、分子结构等学科中的应用，这类多项式值得进一步深入研究.下一步的工作是研究其更深入的性质，例如对角单调性^［14］和差分代换的平凡性^［15］.

参考文献

[1] SHAKED-MONDERER N， BERMAN A. Copositive and Completely Positive Matrices［M］. WORLD SCIENTIFIC， 2021.

[2] DIEHL M， GLINEUR F， JARLEBRING E， et al. Recent Advances in Optimization and its Applications in Engineering： The 14th Belgian-French-German Conference on Optimization［M］. Berlin， Heidelberg： Springer， 2010： 3-20.

[3] GABL M， ANSTREICHER K M. Solving nonconvex optimization problems using outer approximations of the set-copositive cone［J］. Mathematical Programming， 2025： 1-24.

[4] POWERS V. Certificates of Positivity for Real Polynomials： Theory， Practice， and Applications［M］. Cham： Springer International Publishing， 2021.

[5] OERTEL A， SCHÜRMANN A.On Computing the Copositive Minimum and its Representatives［EB/OL］. arXiv： math.NT /2509.23696， 2025.

[6] STURMFELS B， TELEK M L. Copositive geometry of Feynman integrals［J］. Letters in Mathematical Physics， 2025， 115（3）： 74.

[7] QI L Q， LUO Z Y. Tensor Analysis： Spectral Theory and Special Tensors［M］. Philadelphia， PA： Society for Industrial and Applied Mathematics， 2017.

[8] LI M. A review on copositivity criteria for symmetric tensors［J］. Journal of Technology Innovation and Engineering， 2025， 1（6）： 1-10. DOI：doi.org/10.63887/jtie.2025.1.6.11 .

[9] CHOI M D， LAM T Y， REZNICK B. Even symmetric sextics［J］. Mathematische Zeitschrift， 1987， 195（4）： 559-580.

[10] HARRIS W R. Real even symmetric ternary forms［J］. Journal of Algebra， 1999， 222（1）： 204-245.

[11] TIMOFTE V. On the positivity of symmetric polynomial functions. Part I： General results［J］. Journal of Mathematical Analysis and Applications， 2003， 284（1）： 174-190.

[12] MURTY K G， KABADI S N. Some NP-complete problems in quadratic and nonlinear programming［J］. Mathematical Programming， 1987， 39（2）： 117-129.

[13] XU J， YAO Y. An algorithm for determining copositive matrices［J］. Linear Algebra and Its Applications， 2011， 435（11）： 2784-2792.

[14] 姚勇， 王挽澜， 秦小林. 齐次可微函数的对角递减性与一类不等式的证明［J］. 西南民族大学学报（自然科学版）， 2020， 46（5）： 542-550.

[15] 杨路， 姚勇. 差分代换矩阵与多项式的非负性判定［J］. 系统科学与数学， 2009， 29（9）： 1169-1177.

基金资助

中央高校一般项目(ZYN2025111)