Strassen's Degree Bound：计算对称多项式的复杂度下界

· · 算法·理论

先前在 LA 群里看到 EI 提及一个叫做 Strassen's Degree Bound 的东西，可以证明计算 \prod(X+a_i) 的算法存在 \mathcal{O}(n\log n) 的复杂度下界。我出于好奇就搜了下，发现有篇初等证明 An elementary proof for strassen's degree bound。最近花了点时间学了学，遂将论文概要整理于此。

Strassen's Degree Bound 说的是：现有 k 个 n 元多项式 f_1,f_2,\cdots,f_k\in \mathbb C[x_1,x_2,\cdots,x_n]，如果对于几乎所有的 k 元组 (\eta_1,\eta_2,\cdots,\eta_k)\in\mathbb C^k，方程组

\begin{cases}f_1(\xi_1,\xi_2,\cdots,\xi_n)=\eta_1\\ f_2(\xi_1,\xi_2,\cdots,\xi_n)=\eta_2\\\cdots\\f_k(\xi_1,\xi_2,\cdots,\xi_n)=\eta_k\\\end{cases}

都至少有 d 组解 (\xi_1,\cdots,\xi_n)，那么任何计算出 f_1,f_2,\cdots,f_k 的程序都至少需要 \log _ 2d 次乘法或除法。

我们先看下这个定理是怎么推出计算 \prod(X+a_i) 有下界 \mathcal O(n\log n) 的。

首先令 k=n，然后取 f_i 为 \prod(X+a_i) 展开式中 X^{i-1} 项的系数。例如 n=2 时就是 f_1=a_1a_2,f_2=a_1+a_2。可以发现，在绝大多数情况下，对于 n 元组 (\eta_1,\eta_2,\cdots,\eta_n)，方程组

\begin{cases}\xi_1\xi_2\cdots \xi_n=\eta_1\\\cdots\\ \sum_{i\neq j}\xi_i\xi_j=\eta_{n-1}\\\sum_i\xi_i=\eta_n\\\end{cases}\tag{1}

至少有 n! 组解。这是因为，只要 \eta_1,\cdots,\eta_n 对应的多项式方程 \sum_i\eta_iX^{i-1}=0 没有重根，设其根为 (-\xi_1,-\xi_2,-\cdots,-\xi_n)，则由韦达定理，(\xi_1,\xi_2,\cdots,\xi_n) 是 (1) 的解，且任取置换 \sigma，(\xi_{\sigma_1},\xi_{\sigma_2},\cdots,\xi_{\sigma_n}) 也是 (1) 的解，故 (1) 至少有 n! 组解。

那么根据 Strassen's Degree Bound 可知，计算出所有 f_1,\cdots,f_n 至少需要 \log_2n!\sim n\log n 次乘法或除法，即得复杂度下界 \mathcal O(n\log n)。

现在我们看一下如何证明 Strassen's Degree Bound，下面的证明均来自此篇论文，本文只做简要概述。

注：下文均在一个给定的域 K 上讨论。

引理 1. 对于 f_0,f_1,f_2,\cdots,f_k\in K[x_1,x_2,\cdots,x_k]，且 n_i=\deg f_i\ge 1，则存在一个非零多项式 B(z_0,z_1,\cdots,z_k)\in K[z_0,\cdots,z_k]，使得 B 中 z_0 的次数不超过 N=n_1n_2\cdots n_k，且

B(f_0,f_1,\cdots,f_k)=0.

证明. 我们设 B(z_0,z_1,\cdots,z_k)=\sum_{v_0,v_1,\cdots,v_k}b_{v_0,\cdots,v_k}z_0^{v_0}\cdots z_k^{v_k}，其中 v_0\le N，且我们希望 n_0v_0+n_1v_1+\cdots +n_kv_k\le d。

在此约束下，令 z_i=f_i，然后把 f_i^{v_i} 展开为单项式之和，即

B(f_0,f_1,\cdots,f_k)=\sum_{u_1,u_2,\cdots, u_k} c_{u_1,\cdots,u_k}x_1^{u_1}\cdots x_k^{u_k}.\tag{2}

其中每个 c 均为若干个 b 的线性组合，且 u_1+u_2+\cdots+u_k\le d。

想要让 (2) 式等于 0，只需找到一组非零的 b，使得每个 c 均为 0 即可。这是一个齐次线性方程组，只需未知数的数量（即 b 的个数）多于方程条数（即 c 的个数），那非零解总是存在的。

我们断言，只要 d 充分大，那 b 的个数必然大于 c 的个数，即约束条件 v_0\le N,\sum_i n_iv_i\le d 的解的个数大于约束条件 \sum u_i\le d 的解的个数。

对于后者，隔板法告诉我们解的个数为 \binom{d+k}{k}。对于前者，我们可以枚举 v_0 的值，那么只需估计 n_1v_1+\cdots+n_kv_k\le d-n_0v_0 的解数。我们设 \sum_{i\ge 1}n_iv_i\le q 有 S(q) 组解。

断言 S(q)\ge \binom{q+k}{k}/N，证明如下。对于每个 u_1+\cdots+u_k\le q 的解，我们可以取 v_i=\lfloor u_i/n_i\rfloor，则 n_1v_1+\cdots+n_kv_k\le q。但是这样的构造并非单射，不同的 u=(u_1,\cdots,u_k) 可能会得到相同的 v。不过，对于确定的 v，我们可以证明至多只有 N 个 u 会得到它。这是因为 0\le u_i-nv_i\le n_i-1，所以 u_i 至多只有 n_i 种选择，即 u 至多有 N=n_1\cdots n_k 种选择。故 S(q) 大于等于 u 的解数除以 N。

因此，第一个约束条件的解数为

\sum_{v_0\le N}S(d-n_0v_0)\ge \frac 1N\sum _ {v_0\le N} \binom{d-n_0v_0+k}{k}\sim\frac{N+1}{N}\frac{d^k}{k!}\quad (d\rightarrow\infty).

而第二个约束条件的解数为 \binom{d+k}{k}\sim d^k/k!。当 d 足够大时，b 的个数必然大于 c 的个数，故方程 c\equiv 0 有非零解，即存在 B\neq 0 使得 B(f_0,\cdots, f_k)=0 且 \deg_{z_0}B\le N。\Box

接着我们形式化地定义下什么是「计算」。

我们称 C 是一个计算过程，是说 C 是一个序列 q_1,q_2,\cdots,q_n,\cdots,q_k，其中 q_i\in K(x_1,\cdots,x_n)，且 \forall m\le n,q_m=x_m，而对于 m>n，q_m 为以下运算之一：

\begin{aligned}&q_m=q_i\circ q_j,\qquad i,j<m,\circ\in\{+,-,\times,\div\}\\ &q_m=c_mq_i,\text{\ \ \ or\ \ \ } q_m=c_m,\quad i<m,c_m\in K.\end{aligned}\tag{3}

计算过程 C 的长度就定义为序列中 \times,\div 的使用次数之和，记为 L(C)。

对于集合 G=\{g_1,\cdots,g_s\},g_i\in K(x_1,\cdots,x_n)，如果计算过程 C 包含 G，则称 C 计算 G。G 的复杂度 L(G) 就定义为

L(G)=\min_{\text{计算过程 }C}\{L(C):C\text{ 计算 }G\}.

例如，L(\{x_1x_2+x_2x_3+x_1x_3,x_1x_2x_3\})=3，其计算过程 C 可为

&q_4=q_1+q_2=x_1+x_2,\\ & q_5=q_1\times q_2=x_1x_2,\\ & q_6=q_3\times q_4=x_1x_3+x_2x_3,\\ & q_7=q_5+ q_6=x_1x_2+x_1x_3+x_2x_3,\\ & q_8=q_3\times q_5=x_1x_2x_3.\\ \end{aligned}

定理 2. 若计算过程 C 计算 G=\{g_1,\cdots,g_n\}\subseteq K(x_1,\cdots,x_n)，记 l=L(C)，则任给多项式 f_0\in K[x_1,\cdots,x_n]，均存在非零多项式 B(z_0,\cdots,z_n)，使得 z_0 的次数不超过 2^l，且

B(f_0,g_1,\cdots,g_n)=0.

证明. 此处我们简要地刻画下证明思路，具体操作见原论文。

设 C=\{q_1,\cdots,q_k\}，则任给 i\le n，存在 r_i 使得 g_i=q_{r_i}。引入额外的未定元 x_{n+1},\cdots,x_k，并按如下规则构造序列 f：对于 m\le n，令 f_m=x_{r_m}，对于 m>n，参照 (3) 式定义为

\begin{aligned}&f_m=x_m-(x_i\circ x_j),\qquad \circ\in\{+,-,\times \},\\&f_m=x_mx_j-x_i, \qquad \qquad\! q_m=q_i/q_j,\\&f_m=x_m-\alpha _ m x_i, \text{\ or\ }f_m=x_m-\alpha_m.\end{aligned}

需注意的是，这些定义都是和 q 的定义相对应的。即如果 q_m=q_3+q_5，则 f_m=x_m-(x_3+x_5)，运算符和 i,j,\alpha 应与 q 一致。

则 \deg f_i 为 1 或 2，且仅有 l 个 f_i 次数为 2。应用引理 1 可知，存在非零多项式 B_0 使得

B_0(f_0,f_1,f_2,\cdots,f_k)=0,

且 \deg_{z_0}B_0\le 2^l。

为了让 B_0 能变成我们想要的 B，我们可以按如下过程调整 B_0。

从小到大枚举 m=n+1,n+2,\cdots,k-1,k，找到最大的 v 使得 z_m^v 整除 B_0，然后令 B_0\leftarrow B_0/z_m^v，置 z_m=0 得到新的 B_0。

一直操作下去就可以把 z_{n+1},\cdots,z_k 都干掉，并且可以证明，最后得到的 B_0 符合我们的要求。\Box

下面开始证明 Strassen's Degree Bound，这里我们只证 k=n 的情况，这种情况足够我们证明 \prod (X+a_i) 的复杂度下界了。一般情况请见原论文的定理 3.2。

定理 3. 对于代数闭域 K_0 和集合 G=\{g_1,\cdots,g_n\}\subseteq K_0(x_1,\cdots,x_n)，若对于几乎所有 (\eta_1,\cdots,\eta_n)\in K_0^n，方程组

\begin{cases}g_1(\xi_1,\xi_2,\cdots,\xi_n)=\eta_1\\ g_2(\xi_1,\xi_2,\cdots,\xi_n)=\eta_2\\\cdots\\g_n(\xi_1,\xi_2,\cdots,\xi_n)=\eta_n\end{cases}\tag4{}

至少有 d 组解，则 L(G)\ge \log_2 d。

证明. 取能计算 G 的最优计算过程 C，其长度为 l=L(G)。引入新的未定元 u_1,\cdots,u_n，将 C 视作域 K=K_0(u_1,\cdots,u_n) 上的计算过程。根据定理 2，取 f_0=u_1x_1+\cdots+u_nx_n，则存在多项式

B(z_0,\cdots,z_n)=\sum_{j=0}^M A_j(z_1,\cdots,z_n)z_0^j

使得 M\le 2^l,A_M\neq 0 且

\sum_{j=0}^M A_j(g_1(x_1,\cdots,x_n),\cdots,g_n(x_1,\cdots,x_n))\left(\sum_{i=1}^nu_ix_i\right)^j=0.\tag{5}

取合适的 (\eta_1,\cdots,\eta_n)，使得方程组 (4) 至少有 d 组解，且 A_M(\eta_1,\cdots,\eta_n)\neq 0。设 (4) 的 d 组解为 \xi_t=(\xi_{t,1},\cdots,\xi_{t,n}),1\le t\le d，依次令 x_j=\xi_{t,j}，代入 (5) 式得

\sum_{j=0}^M A_j(\eta_1,\cdots,\eta_n)\left(\sum_{i=1}^nu_i\xi_{t,i}\right)^j=0.

记 \nu_t=\sum_i \xi_{t,i}u_i，则 \nu_1,\nu_2,\cdots,\nu_d 为方程

h(y)=\sum_{j=0}^M A_j(\eta_1,\cdots,\eta_n)y^j=0

的 d 个互异的解。故 2^l\ge M\ge d，即 l\ge \log_2d。\Box

最后讲讲我对 Strassen's Degree Bound 的理解。这个理解不一定是对的，但比较形象。一般来讲，每次乘法都会使方程组的解翻倍。比如 x^2=2 就有两个解，而原先 x^3+x=5 有 3 个解，做一次乘法变成 (x^3+x)^2=5 就会翻倍，有 6 个解。除法类似。所以，如果一个方程组有 d 个解，那一定需要至少 \log_2 d 次乘法来使其达到 d 个解。

如果大家有兴趣的话，也可以试着想想求 n 元基本对称多项式至少要几次乘除法。比如 n=3，上文已经给了一种 3 次乘除法的做法，再根据 Strassen's Degree Bound 可知，这是最优做法。而 n=4，我们可以分别计算 (X+a_1)(X+a_2),(X+a_3)(X+a_4)，然后用 Karatsuba 算法合并起来，只需 5 次乘除法，也是最优的。