Oct 122017
 

齐次多项式(Homogeneous polynomial)在数学中有其特殊的重要性.

在代数几何, Homogeneous polynomial 尤其受到偏爱.

实数域上的的 \(n\) 元多项式环, 以 \(\Bbb R[x_1, x_2,\dotsc, x_n]\) 表之.

Hilbert 限制在齐次多项式.

定义 5.1 设 \(p\in \Bbb R[x_1, x_2,\dotsc, x_n]\), 其次数 \(\leqslant d\). 把 \(n+1\) 元 \(d\) 次齐次多项式

\begin{equation}\overline{p}(x_0, x_1,\dotsc, x_n)=x_0^dp\Big(\frac{x_1}{x_0}, \frac{x_2}{x_0},\dotsc, \frac{x_n}{x_0}\Big)\end{equation}

称为是 \(p\) 的齐次化(Homogenization). 具体来说, 当  \(p=\sum cx_1^{d_1}x_2^{d_2}\dotsm x_n^{d_n}\), 那么

\begin{equation}\begin{split}\overline{p}(x_0, x_1,\dotsc, x_n )&=x_0^d\sum c\Big(\frac{x_1}{x_0}\Big)^{d_1}\Big(\frac{x_2}{x_0}\Big)^{d_2} \dotsm \Big(\frac{x_n}{x_0}\Big)^{d_n}\\&=\sum cx_0^{d-d_1-d_2-\dotsb-d_n}x_1^{d_1}x_2^{d_2}\dotsm x_n^{d_n} \\&=\sum cx_0^{d_0}x_1^{d_1}x_2^{d_2}\dotsm x_n^{d_n},\end{split}\end{equation}

这里 \(d_0=d-d_1-d_2-\dotsb-d_n\).

定理 5.2  设 \(p\in \Bbb R[x_1, x_2,\dotsc, x_n]\), 其次数 \(\leqslant d\). 如果 \(d\) 为偶数, 那么

  • \(p\) 非负当且仅当 \(\overline{p}\)  非负;
  • \(p\) 是多项式的平方和当且仅当 \(\overline{p}\)  能表成 \(\frac d2\) 次齐次多项式的平方和.

引理 5.3  假定 \(p\), \(p_1\), \(p_2\), \(\dotsc\), \(p_k\in \Bbb R[x_1, x_2,\dotsc, x_n]\) 都是多项式, \(p=p_1^2+p_2^2+\dotsm+p_k^2\).  如果 \(p_1\), \(p_2\), \(\dotsc\), \(p_k\) 不全是零多项式, 那么

  1. \(p\ne0\);
  2. \(\deg(p)=2\max\{\deg(p_l)|l=1, 2, \dotsc, k\}\);
  3. 如果 \(p\) 是 \(d\) 次齐次多项式, 则诸 \(p_l\) 皆是 \(\dfrac d2\) 次齐次多项式.

Proof   不妨 \(p_1\ne0\). 于是, 存在 \(x\in\Bbb R^n\), 使得 \(p_1(x)\ne0\). 然后

\[p(x)=p_1^2(x)+p_2^2(x)+\dotsm+p_k^2(x)\ge0\]

蕴涵 \(p(x)\ne0\).

写 \(p_l\) 为 \(p_l=p_{l0}+p_{l1}+p_{l2}+\dotsb+p_{ld}\), 这里 \(p_{li}\) 是 \(p_l\) 的 \(i\) 次齐次成分, \(d=\max\{\deg(p_l)|l=1, 2, \dotsc, k\}\). 很明显, \(\deg(p)\leqslant2d\); 1 表明 \(p\) 的 \(2d\) 次齐次成分 \(p^2_{1d}+p^2_{2d}+\dotsb+p^2_{kd}\ne0\), 因为有某 \(l\) 使得 \(p_{ld}\ne0\).

第 3 部分的证明与 2 完全类似, 考虑诸 \(p_l\) 的最低次齐次成分即可.  \(\Box\)

Proof   当 \(p\) 非负之时, 要证明 \(\overline{p}\) 非负, 若 \(x_0\ne0\), 由 \((1)\) 式即可; 若 \(x_0=0\), 由

\begin{equation}\overline{p}(0, x_1,\dotsc, x_n)=\lim_{h\to0}\overline{p}(h, x_1,\dotsc, x_n)\end{equation}

立得.

当 \(\overline{p}\) 非负之时, 只要注意

\begin{equation}p(x_1,\dotsc, x_n)=\overline{p}(1, x_1,\dotsc, x_n)\end{equation}

即知 \(p\) 非负.

如果\(p\) 是多项式的平方和, \(p=\sum\limits_{l=1}^kp_l^2\), 那么依据引理 5.3, \(\deg(p_l)\leqslant\dfrac d2\). 然后

\begin{equation}\overline{p}=\sum_{l=1}^k\Bigg(x_0^{\frac d2}p_l\Big(\frac{x_1}{x_0}, \frac{x_2}{x_0},\dotsc, \frac{x_n}{x_0} \Big)\Bigg)^2 \end{equation}

说明  \(\overline{p}\)  能表成 \(\frac d2\) 次齐次多项式的平方和.

如果  \(\overline{p}\)  能表成多项式的平方和, \(\overline{p}=\sum\limits_{l=1}^kh_l^2\),

\begin{equation}p=\overline{p}(1, x_1,\dotsc, x_n)=\sum_{l=1}^k\Big(h_l(1, x_1,\dotsc, x_n)\Big)^2\end{equation}

说明 \(p\)  能表成多项式的平方和.       \(\Box\)

现在, 很容易的, 我们顺便建立二次多项式非负与平方和的联系.

定理 5.4 设二次多项式 \(p\in \Bbb R[x_1, x_2,\dotsc, x_n]\) 非负, 那么 \(p\) 能写成多项式的平方和.

有了定理 5.2, 这个定理就是很显然的了: 只需要考虑与 \(p\) 对应的二次齐次多项式 \(\overline{p}\) 就够了. \(\overline{p}\) 是二次型. 依据高等代数的正定二次型的理论, 我们断言定理 5.4 为真.

Sep 242017
 

1971 IMO P1   Prove that the following assertion is true for \(n = 3\) and \(n = 5\), and that it is false for every other natural number \(n\gt2\):

If \(x_1\), \(x_2\), \(\dotsc\), \(x_n\) are arbitrary real numbers, then

\begin{equation}A_n(x)= \sum_{i=1}^n\prod_{j\ne i}\Big(x_i-x_j\Big)\geqslant 0.\end{equation}

Anneli Lax  and Peter Lax 1978 年在 [1] 指出: \(A_5(x)\) 不能表成二次型的平方和.

说明 \(A_5(x)\geqslant0\) 是不难的. 几个网站和无数的竞赛辅导书给的答案都是一致的:

无妨 \(x_1\geqslant x_2\geqslant x_3\geqslant x_4\geqslant x_5\). \((1)\) 的前两项的和

\begin{equation}\begin{split}&\hspace3.25ex(x_1-x_2)(x_1-x_3)(x_1-x_4)(x_1-x_5)+(x_2-x_1)(x_2-x_3)(x_2-x_4)(x_2-x_5)\\&=(x_1-x_2)\Big((x_1-x_3)(x_1-x_4)(x_1-x_5)-(x_2-x_3)(x_2-x_4)(x_2-x_5)\Big)\\&\geqslant0,\end{split}\end{equation}

最后的不等式是因为 \(x_1-x_j\geqslant x_2-x_j\geqslant0\), \(j=3\), \(4\), \(5\).

同理, \((1)\) 的最后两项的和亦然 \(\geqslant0\).

至于 \((1)\) 的中间那项

\begin{equation}(x_3-x_1)(x_3-x_2)(x_3-x_4)(x_3-x_5)\geqslant0,\end{equation}

因了 \((x_3-x_1)(x_3-x_2)\geqslant0\), \((x_3-x_4)(x_3-x_5)\geqslant0\).

证明 \(A_5(x)\geqslant0\) 的途径不止这一种: 左边展开再证明局部的不等式应该也是可以的, 不过需要耐心; 使用导数是解决此类问题的普遍办法.

定理 4.1

  • 设 \(x_1\), \(x_2\), \(x_3\), \(x_4\), \(x_5\) 是实数, 有 \(A_5(x)\geqslant0\) 为真 ;
  • \(A_5(x)\) 不能写成多项式的平方和.

依据定理 2.2, 假定 \(A_5\) 能写成

\begin{equation}A_5=\sum Q_j^2,\end{equation}

此处的 \(Q_j\) 都是二次型. 显而易见, 当 \(A_5=0\) 时, \( Q_j=0\) 皆真.

\begin{equation}x_1=x_2,\;\; x_3=x_4=x_5,\end{equation}

或者对 \((5)\) 的指标进行置换得到的条件为真的时刻, 就符合每个 \(x_j\) 与其余的一个 \(x_k\) 相等.

Lemma 4.2  二次型 \(Q\), 只要条件 \((5)\) 或者 \((5)\) 的指标进行置换得到的条件任何一个为真, 总能导致 \(Q=0\), 那么二次型 \(Q\equiv0\).

若 Lemma 成立, 结合在\(A_5=0\) 蕴涵 \( Q_j=0\) 皆真, 我们知道 \((4)\) 中的 \(Q_j\equiv0\). 故而, \((4)\) 不能成立, 从而也就证明了定理 4.1.

Proof of the Lemma  记

\begin{equation}Q(x)=\sum c_{jk}x_jx_k,\;\; c_{jk}=c_{kj}.\end{equation}

根据假定, 当 \(x_1=x_2=y\), \(x_3=x_4=x_5=z\) 时,

\begin{equation}\begin{split}Q&=(c_{11}+2c_{12}+c_{22})y^2\\&+2(c_{13}+c_{14}+c_{15}+c_{23}+c_{24}+c_{25})yz\\&+(c_{33}+c_{44}+c_{55}+2c_{34}+2c_{35}+c_{45})z^2=0.\end{split}\end{equation}

既然无论 \(y\), \(z\) 为谁, 此皆为真, 于是

\begin{equation}c_{11}+2c_{12}+c_{22}=0;\end{equation}

\begin{equation}c_{13}+c_{14}+c_{15}+c_{23}+c_{24}+c_{25}=0;\end{equation}

\begin{equation}c_{33}+c_{44}+c_{55}+2c_{34}+2c_{35}+c_{45}=0.\end{equation}

这几个式子的指标置换得到的关系式也是成立的, 从 \((8)\) 式, 使用置换 \((12345)\to(34125)\), 则

\begin{equation}c_{33}+2c_{34}+c_{44}=0.\end{equation}

从 \((10)\) 式减去 \((11)\) 式,

\begin{equation}c_{55}+2c_{35}+2c_{45}=0.\end{equation}

考虑所有保持 \(5\) 不动的置换, 从 \((12)\) 式得到的关系式也是对的, 从而

\begin{equation}c_{j5}+c_{k5}=-\frac12 c_{55}\end{equation}

当 \(j\ne k\) 且 \(j\), \(k\ne5\). 进而

\begin{equation}c_{15}=c_{25}=c_{35}=c_{45}.\end{equation}

交换 \(1\) 和 \(5\), 以及 \(2\) 和 \(5\), 从 \((14)\) 式可得

\begin{equation}c_{51}=c_{21}=c_{31}=c_{41}.\end{equation}

\begin{equation}c_{12}=c_{52}=c_{32}=c_{42}.\end{equation}

根据 \( c_{jk}\) 的对称性, 从而

\begin{equation}c_{1j}=c_{2j}=c_{12}\qquad    j=3, 4,5.\end{equation}

带入 \((9)\) 式, 导致 \(6c_{12}=0\), 亦即 \(c_{12}=0\).  既然 \(1\), \(2\) 这一对数能换成别的任意的数, 于是

\begin{equation}c_{jk}=0 \qquad    j\ne k.\end{equation}

带入 \((12)\) 式, 定出 \(c_{55}=0\).  既然 \(5\) 能换成别的任意的数, 于是

\begin{equation}c_{jj}=0.\end{equation}

这便完成了引理的证明.

References

  1. Anneli Lax, Peter Lax, On sums of squares, Linear Algebra and its applications, 20, 71-75 (1978)
Sep 232017
 

M.D. Choi, T.-Y. Lam 1977 年举了一个例子: The Choi-Lam polynomial \(Q(x, y, z, w) =x^2y^2+y^2z^2+z^2x^2+w^4-4xyzw\) 不能写成多项式的平方和. 与 The Motzkin polynomial 一样, Choi-Lam 多项式也会在以后的证明成为关键角色.

后面的定理 5.2 说明 \(x^2y^2+y^2z^2+z^2x^2+w^4-4xyzw\) 不能写成多项式的平方和实际就是下面定理的后半部分:

定理 3.1 Choi-Lam 多项式

\begin{equation} Q(x, y,z) =x^2y^2+y^2z^2+z^2x^2+1-4xyz,\end{equation}

那么

  • \(Q(x, y,z)\geqslant0\) 为真对任意实数 \(x\), \(y\),  \(z\);
  • \(Q(x, y,z)\) 不能写成多项式的平方和.

方法是完全照搬的. 如果 \(Q(x, y, z)\) 是一些次数(至多)为 \(2\) 的多项式的平方和:

\begin{equation} Q(x, y, z) =\sum_{l=1}^k\Big(a_l+b_lx+c_ly+d_lz+e_lx^2+f_ly^2+g_lz^2+h_lxy+i_lyz+j_lzx\Big)^2,\end{equation}

这里 \(a_l\), \(b_l\), \(c_l\), \(d_l\), \(e_l\), \(f_l\), \(g_l\), \(h_l\), \(i_l\) 和 \(j_l\) 都是实常数, \(l=1\), \(2\), \(\dotsc\), \(k\).

\((1)\) 没有 \(x^4\), \(y^4\), \(z^4\) 项, 因此\((2)\) 的右边的这些项的系数为 \(0\). 于是

\[\sum_{l=1}^ke_l^2=\sum_{l=1}^kf_l^2=\sum_{l=1}^kg_l^2=0,\]

故 \(e_l=f_l=g_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\).

\((1)\) 没有 \(x^2\) 项, 因此\((2)\) 的右边的 \(x^2\) 项的系数为 \(0\). 于是

\[\sum_{l=1}^k\Big(b_l^2+2a_le_l\Big)=0,\]

故 \(b_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\).

同样的, \((1)\) 没有 \(y^2\), \(z^2\) 项, 因此 \(\sum\limits_{l=1}^kc_l^2=0\). 于是 \(c_l=d_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\).

注意 \((1)\) 中的 \(xyz\) 项的系数是 \(-4\), 故

\[2\sum_{l=1}^k\Big(b_li_l+c_lj_l+d_lh_l\Big)=-4.\]

但这是不可能的, 因  \(b_l=c_l=d_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\), 故而 \(Q(x, y, z)\) 不能写成多项式的平方和.

类似定理 2.1, 我们也可以使用定理 2.2 来直接证明 \(Q(x, y, z, w) =x^2y^2+y^2z^2+z^2x^2+w^4-4xyzw\) 不能写成多项式的平方和:

\begin{equation} Q(x, y, z, w) =\sum\Big(A_lx^2+B_lxy+C_lxz+D_ly^2+E_lxw+F_lz^2+G_lyz+H_lyw+I_lzw+J_lw^2\Big)^2.\end{equation}

比较两端 \(x^4\), \(y^4\), \(z^4\) 的系数, 得 \(A_l=D_l=F_l=0\).

比较两端 \(x^2w^2\) 的系数, 得

\[\sum\Big(2A_lJ_l+E_l^2\Big)=0.\]

故 \(E_l=0\). 类似的推理, \(H_l=I_l=0\).

此时, \((3)\) 已经是如下

\begin{equation} Q(x, y, z, w) =\sum\Big(B_lxy+C_lxz+G_lyz+J_lw^2\Big)^2.\end{equation}

比较上式两端 \(xyzw\) 的系数, 矛盾!

Sep 202017
 

T. Motzkin 1967 年举了一个例子: The Motzkin polynomial \(M(x, y, z)=x^4y^2+x^2y^4+z^6-3x^2y^2z^2\) 不能写成多项式的平方和. 后面的定理 5.2 说明这事与定理 2.1 的第二部分是等价的.

Theorem 2.1  Motzkin 多项式

\begin{equation} M(x, y) =x^4y^2+x^2y^4-3x^2y^2+1,\end{equation}

那么

  • \(M(x, y)\geqslant0\) 对任意实数 \(x\), \(y\) 成立;
  • \(M(x, y)\) 不能写成多项式的平方和;
  • \(M(x, y)\) 可以表示为有理函数的平方和.

\(M(x, y)\geqslant0\) 是显然的, 因为我们有算术几何平均不等式.

定理的第二部分, 如果 \(M(x, y)\) 是一些次数(至多)为 \(3\) 的多项式的平方和:

\begin{equation} M(x, y) =\sum_{l=1}^k\Big(a_l+b_lx+c_ly+d_lx^2+e_lxy+f_ly^2+g_lx^3+h_lx^2y+i_lxy^2+j_ly^3\Big)^2,\end{equation}

这里 \(a_l\), \(b_l\), \(c_l\), \(d_l\), \(e_l\), \(f_l\), \(g_l\), \(h_l\), \(i_l\), 和 \(j_l\) 都是实常数, \(l=1\), \(2\), \(\dotsc\), \(k\).

\((1)\) 没有 \(x^6\), \(y^6\) 项, 因此\((2)\) 的右边的 \(x^6\), \(y^6\) 项的系数都为 \(0\). 于是

\[\sum_{l=1}^kg_l^2=\sum_{l=1}^kj_l^2=0,\]

故 \(g_l=j_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\).

\((1)\) 没有 \(x^4\) 项导出

\begin{equation}\sum_{l=1}^k\Big(d_l^2+2b_lg_l\Big)=0.\end{equation}

由于 \(g_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\), 于是

\[\sum_{l=1}^kd_l^2=0.\]

至此, \(d_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\).

同理, \(f_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\).

\((1)\) 没有 \(x^2\) 项, 因此\((2)\) 的右边的 \(x^2\) 项的系数为 \(0\). 于是

\[\sum_{l=1}^k \Big(b_l^2+2a_ld_l\Big)=0,\]

故 \(b_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\).

同样的, \((1)\) 没有 \(y^2\) 项, 因此  \(c_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\).

注意 \((1)\) 中的 \(x^2y^2\) 项的系数是 \(-3\), 故

\[\sum_{l=1}^k\Big(e_l^2+2b_li_l+2c_lh_l+2d_lf_l\Big)=-3.\]

既然  \(b_l=c_l=d_l=0\), \(l=1\), \(2\), \(\dotsc\), \(k\),

\begin{equation}\sum_{l=1}^ke_l^2=-3.\end{equation}

这是不可能的! 故而 \(M(x, y)\) 不能写成多项式的平方和.

当然, 也可以采用类似的手段来直接证明 \(x^4y^2+x^2y^4+z^6-3x^2y^2z^2\) 不能写成多项式的平方和.

我们先指出

定理 2.2 设 \(G\), \(g_1\), \(g_2\), \(\dotsc\), \(g_m\in\Bbb R[x_1, x_2,\dotsc, x_n]\), 且 \(G\) 是 \(t\) 次齐次多项式. 如果

\begin{equation}G=\sum_{i=1}^mg_i^2,\end{equation}

那么, \(t\) 是偶数, 且 \(g_1\), \(g_2\), \(\dotsc\), \(g_m\) 都是 \(\dfrac t2\) 次齐次多项式.

定理 2.2 其实是引理 5.3 的最后一部分.  我们用来推导 \(M(x, y, z)\) 不能写成多项式的平方和.

\begin{equation}M(x,y,z)=\sum\Big(A_lx^3+B_lx^2y+C_lx^2z+D_lxy^2+E_lxyz+F_lxz^2+G_ly^3+H_ly^2z+I_lyz^2+J_lz^3\Big)^2,\end{equation}

令 \(x=1\), \(y=z=0\), 得 \(A_l=0\). 再比较两端 \(x^4z^2\) 的系数, 得

\[\sum\Big(C_l^2+2A_lF_l\Big)=0.\]

于是, \(C_l=0\).

比较两端 \(x^2z^4\) 的系数, 得

\[\sum\Big(F_l^2+2C_lJ_l\Big)=0.\]

于是, \(F_l=0\).

同样的推导, \(G_l=H_l=I_l=0\).

此时, \((6)\) 已经是如下

\begin{equation}M(x,y,z)=\sum\Big(B_lx^2y+D_lxy^2+E_lxyz+J_lz^3\Big)^2.\end{equation}

比较两端 \(x^2y^2z^2\) 的系数即能得出矛盾!

至于, 定理 2.1 的最后部分

\begin{equation}\Big(x^2+1\Big) M(x, y)=x^2\Big(y^2-1\Big)^2+x^2y^2\Big(x^2-1\Big)^2+\Big(x^2y^2-1\Big)^2\end{equation}

或者, 稍微复杂

\begin{equation}\Big(x^2+y^2+1\Big) M(x, y)=x^2\Big(y^2-1\Big)^2+y^2\Big(x^2-1\Big)^2+\Big(x^2y^2-1\Big)^2+\frac14x^2y^2\Big(x^2-y^2\Big)^2+\frac34x^2y^2\Big(x^2+y^2-2\Big)^2\end{equation}

甚至, 直接

\begin{equation}M(x, y)=\frac{x^2y^2(x^2 + y^2 -2)^2(x^2 + y^2 +1) +(x^2 – y^2)^2}{(x^2 + y^2)^2}\end{equation}

说明 \(M(x, y)\) 可以写成有理函数的平方和.

Sep 192017
 

设 \(p\) 是实系数的 \(n\) 元多项式, \(S\) 是 \(n\) 维 Euclidean space \(\Bbb R^n\) 的子集. 我们说 \(p\) 在 \(S\) 上是非负的(non-negative), 如果对于任意的 \(x\in S\), 有 \(p(x)\geqslant0\).

我们下面关注的重点是 \(\Bbb R^n\) 上的非负(non-negative)多项式, 即对于任意的 \(x\in \Bbb R^n\), 有 \(p(x)\geqslant0\).

要探讨的, 非负多项式是否就是可以表为多项式的平方和的那些多项式? 这是一个古老的问题, 与 Hilbert’s seventeenth problem 有关, 早已有答案: 回答”差不多”是肯定的. 换言之, 非负多项式确实可以表示成平方和, 但一般而言是有理函数而不是多项式的平方和.

先从简单的情形一元多项式开始.

Theorem 1.1 \(p(x)\geqslant0\) 对所有的实数 \(x\) 为真, 则存在一元多项式 \(f(x)\) 和 \(g(x)\), 使得 \(p(x)=f^2(x)+g^2(x)\) 恒成立.

这是一个平凡的结果, 估计可以在很多的高等代数的书上找到, 使用一下实系数多项式的因式分解标准式即可.

我们可以按照这个步骤来验证:

\begin{equation} p=a\prod_{i=1}^k(x-a_i)^{m_i}\prod_{j=1}^l\Big(x^2+2b_jx+c_j\Big),\end{equation}

这里诸 \(a_i\) 皆是实数, 诸 \(x^2+2b_jx+c_j\) 都无实根.

那么, 以下三条陈述相互等价:

  1. \(p(x)\geqslant0\) on \(\Bbb R\);
  2. \(a\gt0\), 且诸 \(m_i\) 都是偶数;
  3. 存在多项式 \(f(x)\) 和 \(g(x)\), 使得 \(p(x)=f^2(x)+g^2(x)\).

事实上, 很容易说明 \( 1 \implies  2 \implies 3 \implies 1\).

定理 1.1 其实是基于 \(\Bbb C[x]\) 与 Gaussian integers \(\Bbb Z[i]\) 的一个类比. 把 \(\Bbb C[x]\) 视为 Euclidean domain \(\Bbb R[x]\) 添加 \(i\) 得到的二次扩张; \(\Bbb Z[i]\) 看作 Euclidean domain \(\Bbb Z\) 添加 \(i\) 得到的二次扩张. 在这个类比, 线性多项式类似 \(3\pmod4\) 的质数, 后者依旧是 \(\Bbb Z[i]\) 中的质数; 二次不可约多项式类似非 \(3\pmod4\) 的质数, 后者不是 \(\Bbb Z[i]\) 中的质数. 非 \(0\) 整数 \(n\in Z\) 是两个整数的平方和当且仅当其为正并且每个 \(3\pmod4\) 的质数因子在标准分解式出现偶数次. 类似的, 多项式 \(p\in\Bbb R[x]\) 是两个多项式的平方和当且仅当取值非负并且每个线性因子出现偶数次.

多元多项式的情形复杂得多. 我们不能指望 Theorem 1.1 可以简单的推广到多元多项式. 事实上, 只在很少的情况下, 非负多元多项式可以写成多项式的平方和.

一般来说, 如果 \(R[i]\) 和 \(R\) 都是唯一因子分解整环(Gauss domain), 那么 \(R\) 中的某些质数在 \(R[i]\) 有两个共轭, 但 \(R\) 中其余的那些质数依旧是 \(R[i]\) 的质数. 这使得我们总能对 \(R\) 中那些能写成两个平方和的元素予以某种刻画. 这些道理对多元多项式环 \(R=\Bbb R[x]\) 确实是适用. 但是, 出现问题的地方即在于对于 \(\Bbb R[x]\) 的非负多项式 \(p\), 其不可约因子不一定出现偶数次.

Aug 192012
 

Euclidean algorithm, 也就是常说的辗转相除法, 通过有限步骤来找出两个整数 \(a,b\) 的最大公约数 \((a,b)\).

具体说来, \(a,b\in\Bbb Z\), 我们假定 \(b>0\), 并记 \(r_0=a, r_1=b\). 据带余除法, 可有

\[r_0=q_1r_1+r_2,\quad 0<r_2<r_1, q_1=\left[\frac{r_0}{r_1}\right];\]

\[r_1=q_2r_2+r_3,\quad 0<r_3<r_2, q_2=\left[\frac{r_1}{r_2}\right];\]

\[\cdots  \cdots  \cdots  \cdots  \cdots  \cdots \cdots \cdots\]

\[r_{n-1}=q_nr_n,\quad q_n=\left[\frac{r_{n-1}}{r_n}\right].\]

\(\left[x\right]\) 表示不超过 \(x\) 的最大整数. \(r_n=(a,b).\)

我们把数列 \(r_0,r_1,r_2,\dotsc,r_n\) 冠名为(始于 \(a,b\) 的) Euclidean algorithm 余数数列.

记数列 \(\{s_i\},\{t_i\}\) 使得

\begin{equation}r_i=s_ia+t_ib( i=0,1,2,\dotsc,n).\end{equation}

\(\{s_i\},\{t_i\}\) 可由下面的递推关系定出:

\begin{equation}s_0=1,s_1=0,s_{i+1}=s_{i-1}-q_is_i,\end{equation}

\begin{equation}t_0=0,t_1=1,t_{i+1}=t_{i-1}-q_it_i,\end{equation}

\(i=1,2,\dotsc,n.\) 注意, 我们这里特意根据需要把 \(\{s_i\},\{t_i\}\) 往下都多算了一项 \( s_{n+1}, t_{n+1}\). 记 \(r_{n+1}=0\).

看来, 又可以和连分数(Continued fraction)扯上关系了, 这似乎也揭示了采用辗转相除法与连分数来证明Fermat的定理, 其本质没有区别. 由于连分数与辗转相除法的关系, 也不让人意外. 好吧, 我们先暂且不牵涉到连分数, 而继续探讨 \(r_i,s_i,t_i\) 的性质. 分别把 \(\{r_i\},\{q_i\},\{t_i\}\) 称为 \(r\)-数列, \(q\)-数列, \(t\)-数列.

首先要指出的是, 式 \((1)\) 对 \(i=n+1\) 也成立, 即我们有 \(r_{n+1}=s_{n+1}a+t_{n+1}b=0\). 进而

\begin{equation}t_ib\equiv r_i\pmod a\end{equation}

总是成立.

1.  如果 \(a>b,\) 则 \(q_i\geqslant1(i=1,2,\dotsc,n), q_n\geqslant2;\)
2.  \(\{s_i\},\{t_i\}\) 是交错的, 正负相间, 即 \(s_i=(-1)^i|s_i|,t_i=(-1)^{i+1}|t_i|,i=1,2,\dotsc,n+1;\)
3.  \(0=|s_1|<1=|s_2|<|s_3|<\dotsb<|s_{n+1}|;\)
4.  \(1=|t_1|\leqslant |t_2|<|t_3|<\dotsb<|t_{n+1}|;\)
5.  \(|s_{i+1}|=|s_{i-1}|+q_i|s_i|,|t_{i+1}|=|t_{i-1}|+q_i|t_i|,i=1,2,\dotsc,n;\)
6.  \(a=r_{i-1}|t_i|+r_i|t_{i-1}|, i=1,2,\dotsc,n+1;\)
7.  \(s_{n+1}=\dfrac{(-1)^{n+1}b}{(a,b)},t_{n+1}=\dfrac{(-1)^na}{(a,b)};\)
8.   如果 \((a,b)=1,\) 那么 \(|s_n|\leqslant \frac b2,|t_n|\leqslant \frac a2.\)

据 \(5,\) 数列 \(\{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 是一个始于 \(|t_{n+1}|,|t_n|\) 的Euclidean algorithm 余数数列.

利用 \(5\) 以及 \(r_i\) 的性质, 进行归纳可得 \(6\). 事实上, 奠基显然. 假定 \(6\) 对 \(i\) 成立\((1\leqslant i\leqslant n),\) 那么
\begin{equation}\begin{split}a & =r_{i-1}|t_i|+r_i|t_{i-1}|\\& =(q_ir_i+r_{i+1})|t_i|+r_i|t_{i-1}|\\& =r_i(q_i|t_i|+|t_{i-1}|)+r_{i+1}|t_i|\\& =r_i|t_{i+1}|+r_{i+1}|t_i|,\end{split}\end{equation}
这就得出了结果.

由 \(6\), 我们有

\[a=r_n|t_{n+1}|+r_{n+1}|t_n|=|t_{n+1}|d,\]

这里 \(d=r_n=(a,b).\) 根据 \(2\), 就得到了 \(t_{n+1}=\dfrac{(-1)^na}d.\)  然后, 因为 \(s_{n+1}a+t_{n+1}b=0\), 所以 \(s_{n+1}=\dfrac{(-1)^{n+1}b}d.\)

\[|s_{n+1}| =|s_{n-1}|+q_n|s_n|\geqslant q_n|s_n|\geqslant 2|s_n|,\]

利用 \(7,\) 就得到 \(|s_n|\leqslant \frac b2.\) 同理可得 \(|t_n|\leqslant \frac a2.\)

做了这么多准备工作, 终于可以进行我们最重要的事情, 证明 Fermat 的平方和定理了. 为此, 还需要建立一条定理:

定理(Aubry 1913, Thue 1902, Vinogradov 1926)  \(a>b>0, (a,b)=1.\) 有 \(x,y\) 使

\begin{equation}bx\equiv y\pmod a,\end{equation}

且 \(1\leqslant |x|,|y|\leqslant \sqrt a.\)

事实上, \(r_0=a>\sqrt a>1=r_n,\) 必有 \(k(1\leqslant k \leqslant n)\) 使得

\begin{equation}r_{k-1}>\sqrt a\geqslant r_k,\end{equation}

根据 \(6\), 得

\[a=r_{k-1}|t_k|+r_k|t_{k-1}|\geqslant r_{k-1}|t_k|>\sqrt a|t_k|,\]

于是 \(|t_k|<\sqrt a.\) 最后, \((4)\) 说明

\[bt_k\equiv r_k\pmod a,\]

故此, \((t_k,r_k)\) 符合我们的要求.

现在, Fermat 的平方和定理呼之欲出. 下面是 Serret 于 \(1848\) 年给出的证明:

质数 \(p\equiv1\pmod4, u^2+1=lp, 1\leqslant u<\frac p2.\)

令 \(r_0=p, r_1=u.\) 选取 \(k\) 使得 \(r_{k-1}>\sqrt p>r_k,\) 此时

\[r_k\equiv ut_k\pmod p, 1\leqslant |t_k|<\sqrt p.\]

于是 \(r_k^2+t_k^2=p.\)

我们继续往前走, 探讨这种情况下, 可以得到的更精细的结果. 下面几条性质都假定 \(r_0=p, r_1=u,\) 谈到的 \(r\)-数列, \(q\)-数列, \(t\)-数列以及\(\{|t_i|:i=n+1,n,\dotsc,1\}\), 也是相应的由 \(p,u\) 得到的.

9.   \(n\) 是偶数;
10.  数列 \(\{|t_i|:i=n+1,n,\dotsc,1\}\) 与 \(r\)-数列相同, 即 \(|t_{n+1-i}|=r_i(i=0,1,2,\dotsc, n+1);\)
11.  \(q\)-数列是对称的, 即 \(q_i=q_{n+1-i}(i=1,2,\dotsc, n);\)
12.   \(p\bigm|(r_i^2+t_i^2)(i=0,1,2,\dotsc,n+1);\)
13.   \(r_{\frac n2-1}>\sqrt p>r_{\frac n2}.\)

这些性质导出 Fermat 平方和是很容易的. 实际上, 若记 \(k=\frac n2,\) 则

\[p\bigm|(r_k^2+t_k^2),\quad |t_k|=r_{k+1},\quad r_{k-1}>\sqrt p>r_k>r_{k+1}.\]

故此 \(r_k^2+r_{k+1}^2=p.\)

现在来证明 \(2\bigm|n.\) 从 \((4),\) 以及 \(r_n=1\) 可得

\[t_nu\equiv 1\pmod p.\]

从而

\[t_n\equiv -u\pmod p,\]

也就是 \(p\bigm|(t_n+u).\) 结合

\[|t_n+u|\leqslant |t_n|+|u|<p,\]

可得 \(t_n+u=0, t_n=-u.\) 另一方面, 由 \(2\) 可知 \[t_n=(-1)^{n+1}|t_n|.\]

故而 \(2\bigm|n.\) 由 \(7\) 可有

\[ t_{n+1}=(-1)^n|t_{n+1}|=p.\]

从 \(\{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 是一个始于 \(|t_{n+1}|=p,|t_n|=u\) 的Euclidean algorithm 余数数列, 知晓 \(\{|t_i|:i=n+1,n,\dotsc,1\}\) 与 \(r\)-数列相同, 因此, 其相应的商组成的数列与 \(q\)-数列一致; 另一方面, 从 \(5\) 看出这些商组成的数列刚好与 \(q\)-数列顺序相反, 于是, \(q_i=q_{n+1-i}(i=1,2,\dotsc, n).\)

再次根据 \((4),\) 得

\[(t_iu)^2\equiv r_i^2\pmod p,\]

这就是 \(p\bigm|(r_i^2+t_i^2).\)

既然 \(2\bigm|n,\) 可设 \(n=2k.\) 由 \(6,10\), 得

\[p=r_k|t_{k+1}|+r_{k+1}|t_k|=r_k^2+r_{k+1}^2,\]

于是 \(\sqrt p>r_k.\) 由

\[r_{k-1}=q_kr_k+r_{k+1}\geqslant r_k+r_{k+1}\]

可得

\[r_{k-1}^2>r_k^2+r_{k+1}^2=p,\]

于是 \(r_{k-1}>\sqrt p.\) 综合起来, 就完成了证明.

下面换一个想法, 不利用 \(6,7,8,\) 来证明 \(10, 9,13\). 先介绍 Euler 的一个从连分数中来的公式.

Euler 公式  假定 \((a,b)=1,a=q_1b+r_2.\) 采用归纳法, 假设已有 \(b=f(q_2,q_3,\dotsc,q_n),\)\( r_2=f(q_3,q_4,\dotsc,q_n),\) 来指出有一个函数 \(f,\) 使得 \(a=f(q_1,q_2,\dotsc,q_n).\) 函数 \(f\) 是一些乘积的和: \(q_1,q_2,q_3,\dotsc,q_n\) 的积; 去掉 \(q_1,q_2,\dotsc,q_n\) 的任意连续两项后得到的积; 再去掉 \(q_1,q_2,\dotsc,q_n\) 的任意两个不同的连续两项后得到的积, 依次类推. 比如, \(n=5\) 时, 有

\[f(q_1,q_2,\dotsc,q_5)=q_1q_2q_3q_4q_5+q_3q_4q_5+q_1q_4q_5+q_1q_2q_5+q_1q_2q_3+q_5+q_3+q_1.\]

\(n\) 为偶数时, 把 \(q_1,q_2,\dotsc,q_n\) 全部去掉时, 约定积是 \(1\).

现在回到初始值 \(p,u.\) 先指出 \(10\) 的合理.

首先, 必定 \(t_{n+1}=\pm p.\) 类似前面已经指出的, \(\{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 是一个Euclidean algorithm 余数数列, 其相应的商组成的数列,从 \(5,\) 刚好与 \(q\)-数列顺序相反; 但是把自变量顺序颠倒, Euler 公式是不变的, 因此, \(|t_{n+1}|=p,\) 因为 \(p\) 与 \(|t_{n+1}|\) 都是这些商的同一个函数值. 再据 \((4), t_nu\equiv 1\pmod p.\) 于是 \(t_n\equiv -u\pmod p;\)  因 \(|t_n|<p,\) 所有 \(t_n=-u\) 或者 \(t_n=p-u.\) 但 \(t_n=p-u\) 的不可能的, 否则 \(\{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 就成了 \(p,p-u,u,\dotsc,\) 比 \(r\)-数列长, 矛盾. \(t_n=-u. \{|t_{n+1}|,|t_n|,\dotsc,|t_1|\}\) 的头两项是 \(p,u,\) 其必定与 \(r\)-数列相同. 现在 \(t_n<0, t\)-数列正负相间, 所以 \(n\) 是偶数.

利用 \(q\)-数列的对称性, 使用Euler 公式可说明, \(f(q_{\frac n2+1},\dotsc,q_n)^2\) 的每一项都会在 \(f(q_1,q_2,\dotsc,q_n)\) 中出现. 于是, \(r_{\frac n2}^2=f(q_1,\dotsc,q_{\frac n2})f(q_{\frac n2+1},\dotsc,q_n),\) 并且这式子中的每一项也会现身于 \(f(q_1,q_2,\dotsc,q_n)=p.\) 故此, \(r_{\frac n2}^2<p, p\) 是质数, 等号不能成立. 同样, 可以说明 \(f(q_1,q_2,\dotsc,q_n)\) 的每一项也会出现在 \(r_{\frac n2-1}^2=f(q_1,\dotsc,q_{\frac n2+1})f(q_{\frac n2},q_{\frac n2+1},\dotsc,q_n)\) 中, 于是 \(r_{\frac n2-1}^2>p.\)

Aug 182012
 

这里将在有理数域 \(\Bbb Q\) 中来考察 Fermat 的平方和, 慢慢走向椭圆曲线(elliptic curve).

首先指出, \(n\in\Bbb N\) 是否两个有理数的平方和, 与其是否两个整数的平方和, 是一码事.

定理  设 \(n\in\Bbb N\), 则下面两件事情等价:

  1. 存在 \(x,y\in\Bbb Q,\) 使得 \(n=x^2+y^2\);
  2. 存在 \(x,y\in\Bbb N,\) 使得 \(n=x^2+y^2\).

只要说明 \(1\Rightarrow2\) 即可. 事实上, 这可归结到, 若有 \(q,n,a,b\in\Bbb N\) 使得

\[q^2n=a^2+b^2,\]

则 \(n\) 可表成两个整数的平方和. 可以认为 \((a,b)=1,\) 并且 \(n\) 不是完全平方. 记 \(l\in\Bbb N^+\) 使得

\[l^2<n<(l+1)^2.\]

于 \(au+bv\) 中, 令 \(u,v\) 分别取 \(0,1,2,\dotsc,l\), 共 \(l+1\) 个值, 则得 \((l+1)^2>n\) 个差数, 故其必有两个数于\(\mod n\) 同余. 设

\[au+bv\equiv au^\prime+bv^\prime\pmod n,\]

\[n\bigm|(ax+by),\]

这里 \(x=u-u^\prime,y=v-v^\prime\), 满足 \( |x|,|y|\leqslant l\). 于是, 更有

\[n\bigm|(ax+by)(ax-by)=a^2x^2-b^2y^2.\]

此外, 显然

\[n\bigm|(a^2+b^2)y^2=a^2y^2+b^2y^2,\]

故而

\[n\bigm|((a^2x^2-b^2y^2)+(a^2y^2+b^2y^2))=a^2(x^2+y^2).\]

因为 \((a,n)=1\), 所以 \(n\bigm|(x^2+y^2)\). 注意到 \(0<x^2+y^2<2n,\) 就得出了 \(n=x^2+y^2.\)

从二平方和定理来看, 本定理是显然的, 但我们没有这样做, 完全避开了它.

 

现在, Hilbert符号(Hilbert symbol)可以登堂了.