Markov–Lukács 区间非负多项式证书

形式陈述

在 $[0,1]$ 上， $x(1-x)$ 非负，却不可能是若干实多项式平方的和，因为后一种表达在整条实线上都非负，而前者在区间外会变负。若要交出区间专属的代数证书，就必须把端点位置写进表达式。

设 $a<b$ 为实数， $p\in\mathbb R[x]$ ， $n$ 为非负整数。这里的多项式按完整系数表给定。Markov–Lukács定理给出两种等价形式，次数约束是上限，不要求最高项非零。

若 $\deg p\le2n$ ，则

p(x)\ge0\quad(a\le x\le b) \quad\Longleftrightarrow\quad p(x)=A(x)^2+(x-a)(b-x)B(x)^2, \tag{1}

其中 $A,B$ 可取实多项式， $\deg A\le n$ 、 $\deg B\le n-1$ 。当 $n=0$ 时省去 $B$ 项，只剩非负常数是一个实数的平方。

若 $\deg p\le2n+1$ ，则

p(x)\ge0\quad(a\le x\le b) \quad\Longleftrightarrow\quad p(x)=(x-a)A(x)^2+(b-x)B(x)^2, \tag{2}

其中 $\deg A,\deg B\le n$ 。零多项式取 $A=B=0$ ；“次数不超过”也包含这个情形，不必为零多项式人为指定次数。

两式都是多项式恒等式，而非仅在几个点上相等。右侧在区间外不必非负。等价命题不要求 $p$ 严格为正，因此允许内部偶重零点和端点零点；不能用只覆盖严格正函数的表示结果省略边界。

从圆周上的模平方得到准确次数

先在 $[-1,1]$ 证明偶数上限情形。令 $Q(e^{it})=p(\cos t)$ 。因为 $\cos t=(e^{it}+e^{-it})/2$ ，它是阶数至多 $2n$ 、具有实且对称Laurent系数的非负三角多项式。若 $Q$ 非零，Fejér–Riesz分解给出规范因子 $h$ ，满足

Q(e^{it})=|h(e^{it})|^2,\qquad \deg h\le2n, \qquad h(0)>0,

且 $h$ 在开单位圆盘内无零点。把 $h$ 的全部系数共轭，仍是同一个实对称谱的规范因子；规范唯一性故使 $h$ 的系数全为实数。零谱则直接取零因子。

现在将频率移到中心，令 $F(t)=e^{-int}h(e^{it})$ 。它的频率都在 $[-n,n]$ ，系数为实数。因此实部是余弦组合，虚部是正弦组合。Chebyshev余弦表示给 $\cos(kt)=T_k(\cos t)$ ；同时由正弦加法公式递推可得

\sin(kt)=\sin t\,U_{k-1}(\cos t),\qquad k\ge1,

其中 $U_0=1$ 、 $U_1=2x$ 、 $U_{j+1}=2xU_j-U_{j-1}$ ，故 $\deg U_j=j$ 。把负频率的正弦符号也计入，得到实多项式 $A,B$ ，使

F(t)=A(\cos t)+i\sin t\,B(\cos t), \qquad \deg A\le n,\quad\deg B\le n-1.

取模平方， $p(x)=A(x)^2+(1-x^2)B(x)^2$ 在所有 $x=\cos t\in[-1,1]$ 上成立。两侧是多项式，在无限多个点相等便是系数恒等式。这也解释了为什么必须先移频：直接拆 $h$ 的实虚部只会得到较松的次数界。

对奇数上限 $\deg p\le2n+1$ ，将偶数结论用于 $(1+x)p(x)$ ，得到

(1+x)p(x)=C(x)^2+(1-x^2)D(x)^2, \qquad \deg C\le n+1,\quad\deg D\le n.

代 $x=-1$ ，有 $C(-1)=0$ ，因此 $C=(1+x)E$ 且 $\deg E\le n$ 。在多项式环中约去公共因子 $1+x$ ，得到 $p=(1+x)E^2+(1-x)D^2$ ，包括原先被约去的端点，因为这是恒等式。

一般区间令 $x=c+ru$ ，其中 $c=(a+b)/2$ 、 $r=(b-a)/2>0$ 。偶数式的 $1-u^2=(x-a)(b-x)/r^2$ ，将 $1/r$ 吸收到 $B$ ；奇数式的 $1+u=(x-a)/r$ 、 $1-u=(b-x)/r$ ，将 $1/\sqrt r$ 吸收到两个因子。这样得到(1)、(2)，且次数不变。反方向只需观察各项在区间内非负。

从平方改写成可核验的矩阵

令 $v_j(x)=(1,x,\ldots,x^j)^{\mathsf T}$ 。平方和可写为 $v_j^{\mathsf T}Gv_j$ ，其中 $G\succeq0$ 为实对称半正定矩阵：每个平方的系数向量 $u$ 贡献 $uu^{\mathsf T}$ ；反过来对 $G$ 作非负谱分解，就得到有限平方和。因此(1)也等价于存在

p=v_n^{\mathsf T}G_0v_n+(x-a)(b-x)v_{n-1}^{\mathsf T}G_1v_{n-1}, \qquad G_0,G_1\succeq0. \tag{3}

奇数情形则为

p=(x-a)v_n^{\mathsf T}G_av_n+(b-x)v_n^{\mathsf T}G_bv_n, \qquad G_a,G_b\succeq0. \tag{4}

这里允许每项有多个平方，仍是同一个充要条件。定理保证存在单平方的特殊表示，但求证书时没有必要额外强求每个Gram矩阵秩一。

把 $(x-a)(b-x)=-ab+(a+b)x-x^2$ 展开。偶数情形第 $k$ 个系数必须满足

p_k=\sum_{i+j=k}(G_0)_{ij} -ab\sum_{i+j=k}(G_1)_{ij} +(a+b)\sum_{i+j=k-1}(G_1)_{ij} -\sum_{i+j=k-2}(G_1)_{ij}. \tag{5}

不存在的下标之和按零计算。奇数式同样逐系数展开。这就是有限线性等式加PSD条件；求解者与检查者可以分开，检查者只需核全部系数和PSD证据。

直觉

平方负责提供不会变号的基本材料；端点因子负责说明材料只需在哪个区域非负。偶数公式把两个端点同时放进 $(x-a)(b-x)$ ，奇数公式则把它们分别分配给两个平方。余弦映射把区间折成圆周，模平方中的实部平方与虚部平方恰好产生这两种结构。

图只能帮助定位负值或零点。真正可以传给另一位检查者的是恒等式、次数和PSD或负点证据；调整绘图网格不会改变这些代数条件。

例子与边界

一个参数族同时检查非负性与降次

在 $[0,1]$ 令

q(x)=x^2-x+\frac16,\qquad p_\gamma(x)=q(x)^2+\gamma x(1-x)(x-\tfrac12)^2. \tag{6}

当 $\gamma\ge0$ ，这是(1)的直接证书， $A=q$ 、 $B=\sqrt\gamma(x-1/2)$ 。若希望只交有理矩阵，可以把 $\gamma$ 作为Gram权重，不必近似其平方根。

$q$ 的两个根为 $x_\pm=1/2\pm\sqrt3/6$ ，都在开区间中。那里 $x_\pm(1-x_\pm)=1/6$ 、 $(x_\pm-1/2)^2=1/12$ ，所以 $p_\gamma(x_\pm)=\gamma/72$ 。因此负参数必不合法，准确条件为 $\gamma\ge0$ 。

在 $\gamma=1$ 时，四次项和三次项相消，实际只剩

p_1(x)=\frac1{12}(x-\tfrac12)^2+\frac1{144}. \tag{7}

故最小值恰为 $1/144$ ，在 $x=1/2$ 达到。继续使用四次上限的Gram表示当然合法，但不能据输入数组的长度宣布实际次数仍为四。

Gram表示不唯一

在 $[-1,1]$ 上，对任意 $0\le\alpha\le1$ ，

1+x^2=(1-\alpha)+(1+\alpha)x^2+\alpha(1-x^2).

对应 $G_0=\operatorname{diag}(1-\alpha,1+\alpha)$ 、 $G_1=(\alpha)$ 。因此同一多项式有连续多份合法Gram矩阵。表示的非唯一不影响它们认证同一条逐点不等式。

充分的正系数检查，不是充要条件

$(x-1/2)^2$ 在 $[0,1]$ 非负，但它的二次Bernstein系数为 $(1/4,-1/4,1/4)$ ，中间为负。Bernstein基的非负性让全部非负系数成为容易检查的充分条件，却没有使给定次数下的系数条件变为必要。这里平方证书立即通过。

若 $a=b$ ，题目只问 $p(a)\ge0$ ，上述除以区间长度的证明不适用，(1)、(2)也不能继续作为同一恒等式刻画。例如只检查零点处的一次多项式 $p(x)=x$ ，并不会使它成为全实线平方。若 $a>b$ ，应先纠正输入，而非把空区间上的真命题解释成存在同样的平方表示。

推论与应用

全局最小值有准确的有限证书。 对固定 $p$ 和非退化紧区间，极值定理给出 $m=\min_{[a,b]}p$ 。把(3)或(4)中的 $p$ 换为 $p-\tau$ ，最大化 $\tau$ ，得到

m=\max\{\tau:\ p-\tau\text{具有相应PSD Gram表示}\}. \tag{8}

任何可行表示都证明 $\tau\le m$ ；而 $p-m\ge0$ ，定理保证 $\tau=m$ 确实可行。因此这里不仅没有间隙，而且最大值取得。这个论证针对一元区间的完整非负表示，不需要把任意半正定规划都宣布强对偶，也不同于Max-Cut半正定松弛中扩大可行集后只获得界。

要证明候选最优值 $\tau$ ，可以交两样东西： $p-\tau$ 的Gram恒等式，以及一个 $x_*\in[a,b]$ 满足 $p(x_*)=\tau$ 。前者提供全局下界，后者提供达到者。对多项式残差 $e$ ，分别认证 $M-e$ 与 $M+e$ ，就有 $|e|\le M$ ；这是全区间误差认证的另一种完整多项式路径，而非仅在有限网格上测误差。

有限Gram检查的稠密算术成本由矩阵PSD分解的 $O(n^3)$ 与系数收集的 $O(n^2)$ 主导；这不是求解任意证书的复杂度承诺。有理数实现还须计算分子分母位长。带舍入残差的“几乎PSD、几乎相等”也不是准确证书，除非另有误差界覆盖它。

最后，把非负多项式送入一个候选矩泛函，会得到非负数。有限区间矩定理正是把上述全部平方探针组织成两个PSD矩阵，从而判定某张有限矩表是否真的来自支撑受限的正测度。

参考资料

Victoria Powers、Bruce Reznick，Polynomials that are positive on an interval，Transactions of the AMS 352 (2000), 4677–4692，作者稿§2，尤其印刷页5的次数奇偶表示。
E. de Klerk、G. Elabwabi、D. den Hertog，Optimization of univariate functions on bounded intervals by interpolation and semidefinite programming，2006，Theorem3.1与§3.1：Gram表示和区间最小值。

形式陈述 ​

从圆周上的模平方得到准确次数 ​

从平方改写成可核验的矩阵 ​

一个参数族同时检查非负性与降次 ​

Gram表示不唯一 ​

充分的正系数检查，不是充要条件 ​

反向链接