人类都是吃白饭的 || 前沿数学 writeup (1)

· · 算法·理论

本文暂时是一个 writeup, 没有什么过于层级化的梗概, 只用一些比较碎的小标题.

OpenAI 在 2026 年 10 月 2 日证明了一个结果: 特征 0 代数闭域 F 上的矩阵乘法的时间复杂度指数 \omega 满足

\omega_F \le \dfrac 9 4.

事实上这个结果可以改造成任意特征的.

读完这个结果后我的第一感受是, 人类这么多年在干 AI 的活, 反而是 AI 这个是新思路. 原来 TCS 界都是吃白饭的蓝色大肥鱼吗?

我们研究的三重张量指的是 U \otimes V \otimes W \to F 的线性映射, 这个空间我们记作 \mathfrak M(U,V,W).

下面把拉回关系定义成三重张量上的序关系. 考虑 A \in \mathfrak M(U,V,W), B \in \mathfrak M(U',V',W'), 记 A \succeq B, 若存在 \alpha : U' \to U, \beta : V' \to V, \gamma : W' \to W, 使得:

B(\omega) = A((\alpha \otimes \beta \otimes \gamma) \omega).

记 A \sim B, 若 A \succeq B 且 B \succeq A. 如果附加上 \alpha, \beta, \gamma 都是同构, 则记 A \simeq B.

将张量空间商掉 \sim, 得到

\mathcal S = \left(\bigcup_{U,V,W \in F\textsf{-Vect}} \mathfrak M(U,V,W)\middle)\right/{\large\sim}.

在 \mathcal S 上定义出加法 (张量的直和) 和乘法 (张量的张量积), 这个加法和乘法有单位元:

\begin{aligned} 0 : \{0\} \otimes \{0\} \otimes \{0\} \to F, & \\ 1 : F \otimes F \otimes F \to F, &\qquad a \otimes b \otimes c \mapsto a \cdot b \cdot c. \end{aligned}

这使得 \mathcal S 成为有序的半环.

张量的 CP 分解秩是将其分解为秩 1 张量 T = \sum a \otimes b \otimes c 的最少分解个数, 等价地有优美的表述:

\mathrm{R}(T) = \min\{m \in \mathbb Z_{\ge 0} : m \succeq T\}.

所以说, 张量秩是张量序结构的一个缩影, 而序结构远远比 \mathbb Z_{\ge 0} 来得大. 那么我们设有序半环的同态

\chi : \mathcal S \to \mathbb R_{\ge 0}

这个东西称为张量特征.

迹配对

考虑 3 个 N 维空间 U,V,W, 则有迹配对

\begin{aligned} \mathrm{Hom}(V,U) \times \mathrm{Hom}(W,V) \times \mathrm{Hom}(U,W) \to F \\ f \otimes g \otimes h \mapsto \mathrm{tr}(f \circ g \circ h). \end{aligned}

这个张量称为矩阵乘法张量 T_N. 很显然有

N^2 \le \mathrm R(T_N) \le N^3.

设

\nu = \inf \left\{\dfrac{\log \mathrm R(T_N)}{\log N} : N \in \mathbb Z_{>1}\right\}.

定理. 对于每一个 d, 存在一个张量特征 \chi 使得 \chi(T_d) \ge \left\lfloor d^\nu \right\rfloor.

证明. 这里有一些很恶心的拓扑学论证.

自然配对

由于 \mathrm{Hom}(U,V) = U^\vee \times V, 所以 \chi(T_N) 事实上可以分解为

\chi(F \times V \times V^\vee \to F) \cdot \chi(V \times V^\vee \times F \to F) \cdot \chi(V^\vee \times F \times V \to F).

三个张量分别记作 B_X,B_Y,B_Z. 利用单调递增的积性函数一定是幂函数, 可以写出: \chi(B_X(V)) = (\dim V)^{e_X}, 同理定义 e_Y, e_Z, 因此 \chi(T_d) = d^{e_X+e_Y+e_Z}.

为了彰显对称性, 我们让 e_X,e_Y,e_Z 向其平均值 t = \dfrac{e_X+e_Y+e_Z}{3} 靠拢, 这样 \chi(T_d) = d^{3t}. 于是我们定义张量特征的平均化

\Phi(T) = \left(\prod_{\pi \in \mathfrak S_3} \chi(\pi T)\right)^{1/6t},

进而 \Phi(B_X) = \Phi(B_Y) = \Phi(B_Z) = \dim V.

多项式算法

注意到有的时候我们会考虑类似子集卷积的做法, 把域扩展到某个更大的多项式环去. 因此我们这样定义:

记 A \succeq_\varepsilon B, 若存在一个张量 Q \in \mathfrak M \underset{F}{\otimes} F[\varepsilon], 满足 A \underset{F}{\otimes} F[\varepsilon, \frac 1\varepsilon] \succeq Q, 且 Q(0) = B. 为了完整性, 我们写一下:

命题. 若 A \succeq_t B, 则 \chi(A) \ge \chi(B).

证明. 实际上就是在证明延拓到多项式这个方法的复杂度. 形式化地写, 设 L = \deg Q + 1, 则 \deg Q^{\otimes n} < nL, 在 nL 个不同的一般点 \varepsilon \in F^\times 求值 (由于 F[\varepsilon,\frac 1\varepsilon] 能在除了 t = 0 以外的任意点求值), 通过 \mathrm{ev}_\varepsilon \circ \alpha, \beta, \gamma 可以得到 A^{\otimes n} \succeq Q(t)^{\otimes n}, 进而根据 Lagrange 插值有

nL \cdot A^{\otimes n} \succeq \bigoplus_{\varepsilon\ \text{取}\ nL\ \text{个不同非 0 点值}} Q^{\otimes n}(\varepsilon) \succeq Q^{\otimes n}(0) = B^{\otimes n},

进而

nL \cdot \chi(A)^n \ge \chi(B)^n \implies \chi(A) \ge \chi(B).

匹配和

一般的张量加法是 v \otimes w + v \otimes w' = v \otimes (w+w'), 这个和在我们研究的张量应该有性质交叉.

若 f : X \otimes \cdots, g : X \otimes \cdots, 将第 x 维匹配, 后两维用直和, 定义匹配和 f +_X g.

定理. 把匹配和的各个 X 拆分到各个直和项中. 形式化地: 若有 M 个张量 T_i \in \mathfrak M(X, Y_i, Z_i), 它们的匹配和为 T_\Sigma, 则有

T_\Sigma^{\oplus (M+n-1)} \succeq_\varepsilon \bigoplus_{0 \le i < M} (A_i \otimes B_X(n)).

证明. 我们希望第 i 部分只读取第 i 部分的数据, 而这类问题的一个原型是插值, 所以我们考虑 F[t]_{<M}. 那么就有同构 F[t]_{<M} \to F^M, 映射为 f \mapsto f(x_i), 其中 x_i\ (0 \le i < M) 为 F 中相异的 M 个复数.

构造一个空间 J = F[u]/(u^n). 现在规定一个精巧的作用 \sigma : F[t]_{<M} \otimes J \to J: (t, j) \mapsto (x_i + \varepsilon \cdot u) \cdot j, 其它多项式按照 t 的作用做延拓. 这个构造有两大好处: 若 \varepsilon = 0, 那么 (p, j) 的像就是 p(x_i) \cdot j, 也就是刚才所说的 F[t]_{<M} \to F^M 同构; 如果 \varepsilon \in F^\times, 那么 ((t - x_i)^s, 1) 的像就是 \varepsilon^s \cdot u^s. 因此对于一个具体的 \varepsilon \in F^\times 取值这给出了一个 F[t]_{<n} \to J 的同构, 换言之, 在 F[\varepsilon, \frac 1 \varepsilon] 上这就是同构.

现在考虑三个扩大后的空间

\widetilde{X} = X \otimes F[t]_{<M}, \quad\widetilde{Y} = \bigoplus_{0 \le i < M} (Y_i \otimes J), \quad\widetilde{Z} = \bigoplus_{0 \le i < M} (Z_i \otimes J^\vee)

上面的作用 F[t]_{<M} \otimes J \to J 给出了 M 个自然的 F[t]_{<M} \otimes J \otimes J^\vee \to F 映射, 分别和 X \otimes Y_i \otimes Z_i \to F 做张量积后做匹配和, 得到的张量记作 \Phi, 它将我们所有的数据拼了起来.

现在考虑下面几个同态: 对于固定的 0 \le i < M,

\begin{aligned} \mu : F[t]_{<M} \otimes F[t]_{<n} \to F[t]_{<M+n-1}\ \text{为乘法映射}; \\ g : F[t]_{<n} \to J\ \text{如上文所述}, \quad \widetilde g = \mathrm{id}_{F[t]_{<M}} \otimes g; \\ \iota : F[t]_{<M+n-1} \to J, \quad p \mapsto \sigma(p, 1); \\ \sigma : F[t]_{<M} \otimes J \to J. \end{aligned}

则有一个交换图

\sigma \circ \widetilde g = \iota \circ \mu. $$ \Phi(x\otimes p,y\otimes j,z\otimes\varphi) = T_i(x,y,z) \cdot \langle\varphi,\sigma_i(p,j)\rangle. $$ 现在分别对 $Y_i$ 做 $g_i^{-1}$, $Z_i$ 做 $\iota_i^\vee$, 通过交换图做计算, 得到的张量正是 $\Phi$. 换言之, 我们用了 $$ \alpha = \mathrm{id}_{\widetilde{X}}, \quad\beta = \bigoplus_{0 \le i < M} (\mathrm{id}_{Y_i} \otimes g_i^{-1}), \quad \gamma = \bigoplus_{0 \le i < M} (\mathrm{id}_{Z_i} \otimes \iota_i^\vee) $$ 来拉回, 得到的结果是 $$ T_\Sigma \otimes \mu \succeq \Phi. $$ 然而, 根据 Lagrange 插值, $\mu$ 的张量秩 $\le M+n-1$, 因此 $(M+n-1) \succeq \mu$, 也即 $$ T_\Sigma \otimes (M+n-1) \succeq \Phi. $$ 再在 $\Phi$ 里带入 $\varepsilon = 0$, 则 $$ \Phi(x\otimes p,y\otimes j,z\otimes\varphi) = T_i(x,y,z) \cdot p(x_i) \cdot \langle \varphi, j \rangle. $$ 再施加最初 $F[t]_{<M} \to F^M$ 的同构下, 有 $$ \Phi_0 \simeq T_i(x,y,z) \cdot \mathrm{id}_{F^M} \cdot \langle \varphi,j\rangle = \bigoplus_{0 \le i < M} (T_i \otimes B_X(n)) $$ **推论.** 若对每个 $T_i$ 加以权值 $q_i$ ($q_i \in [0,1]$ 而 $\sum q_i = 1$), 则有加权的不等式 $$ \dfrac{\chi(T_\Sigma)}{\prod_i \chi(T_i)^{q_i}} \ge \left(\prod_i q_i^{q_i}\right)^{-e_X}. $$ *证明.* 若 $q \in \mathbb Q^M$, 令 $Nq \in \mathbb Z^M$, 展开 $T_\Sigma^{\otimes N}$, 考虑其中 $T_i$ 出现恰好 $Nq_i$ 次的项: $$ \mathcal S = \{ T_{a_0} \otimes \cdots \otimes T_{a_{N-1}} : a_i\ \text{在其中出现了}\ Nq_i\ \text{次} \}, $$ 则 $$ |\mathcal S| = \binom{N}{Nq_0,\dots,Nq_{M-1}}. $$ 显然 $\mathcal S$ 的限制和 $T_{\mathcal S} \preceq T_\Sigma$, 再根据上述定理, 有 $$ T_\mathcal S \otimes (2 |\mathcal S| - 1) \succeq_\varepsilon |\mathcal S| \otimes B_X(|\mathcal S|) \otimes \bigotimes_{0 \le i < M} T_i^{Nq_i}. $$ 进而 $$ \left( \dfrac{\chi(T_\Sigma)}{\prod_i \chi(T_i)^{q_i}} \right)^N \ge \dfrac{|\mathcal S|}{2 |\mathcal S|-1} \cdot |\mathcal S|^{e_X} $$ 当 $N \to \infty$ 时由 Stirling 近似即可. 若 $q$ 不是有理向量用有理向量逼近即可. 可以得到的进一步推论是 $$ \chi(T_\Sigma) \ge \left( \sum_{i\in I}\chi(T_i)^{1/e_X} \right)^{e_X} $$ ### 张量代数 固定二维空间 $E$. 根据将 $\operatorname{Sym}^d E$ 识别为至多 $d$ 次的多项式的想法, 可得 $$ C_{d,e} : \operatorname{Sym}^d E \times \operatorname{Sym}^e E \to \operatorname{Sym}^{d+e} E $$ 的秩为 $d+e+1$. 有一个自然的短正合列 $\mathcal L(n)$: $$ 0 \to \left(\text{$\bigwedge^2 E$} \otimes \operatorname{Sym}^{n-1} E\right) \to (E \otimes \operatorname{Sym}^n E) \to \operatorname{Sym}^{n+1} \to 0, $$ 其中 $$ \begin{aligned} \kappa : \left(\text{$\bigwedge^2 E$} \otimes \operatorname{Sym}^{n-1} E\right) \to (E \otimes \operatorname{Sym}^n E) \\ (u \wedge v) \otimes f \mapsto u f \otimes v - v f \otimes u. \end{aligned} $$ 现在假设: $V = (E \otimes \operatorname{Sym}^n E), W = \left(\bigwedge^2 E \otimes \operatorname{Sym}^{n-1} E\right)$, 我们现在的目标是: 把 $V$ 转化成 $V/\kappa(W) \oplus \kappa(W)$ ($\kappa$ 是单射, 所以 $\kappa(W) \simeq W$). 为了完成这件事, 我们构造一个辅助的 $F[\varepsilon]$-模 $$ \widetilde J_n = (V \oplus W) \otimes F[\varepsilon], $$ 则一个 $x \in W$ 有两个项: $(\kappa x, 0)$, $(0, x)$. 我们考虑令: $$ J_n = \widetilde J_n / \{(\kappa x, - \varepsilon x) : x \in W\}. $$ 这样, 当 $\varepsilon = 0$ 时, $J_n \simeq V/W \oplus W$, 而 $\varepsilon \in F^\times$ 时, 我们相当于把 $V \oplus W$ 的 $V$ 里的 $\kappa(W)$ 部分嵌入到 $W$ 里. 现在观察短正合列 $$ 0 \to \left(W \otimes F[\varepsilon]\right) \to J_n \to (\operatorname{Sym}^{n+1} E \otimes F[\varepsilon]) \to 0, $$ 由于左右都是自由的, 所以正合列分裂, $J_n$ 是左右的两个空间的直和, 所以 $J_n$ 也是自由 $F[\varepsilon]$-模, 秩为 $2n + 2$. 由于 $\kappa$ 和乘法相容, 有自然定义的乘法 $$ \operatorname{Sym}^p E \otimes J_q \to J_{p+q}, $$ 不难计算, 得到 $\varepsilon \in F^\times$ 的时候这个乘法是 $C_{p,q} \otimes B_X(2)$; 如果 $\varepsilon = 0$ 的时候这个乘法是 $C_{p,q+1} +_{X} C_{p,q-1}$. 可知: $$ 2 \cdot \Phi(C_{p,q}) \ge \Phi(C_{p,q+1}) + \Phi(C_{p,q-1}). $$ ### 另一个估计引理 **引理.** $$ \Phi(C_{a, 3h + a - 1}) \ge 3 \cdot \Phi(C_{a, h}). $$ *证明.* 设 $V_r = F[x]_{< r}$. 设 $d = a + h - 1$, 则 $3h + a - 1 = h + d + h$. 固定一个输入 $u \in V_a$, 利用 $p \mapsto u \cdot p$ 考虑线性映射 $M : V_{2h + d} \to V_{2d + h}$, 则令 $$ \begin{aligned} V_{2h + d} = V_h \oplus x^h V_d \oplus x^{h+d} V_h, \\ V_{2d+h} = V_d \oplus x^d V_h \oplus x^{h+d} V_d. \end{aligned} $$ 在这样的分块下, 定义分块矩阵 $$ \begin{aligned} A = \begin{pmatrix} \mathrm{id} \\ & t \cdot \mathrm{id} \\ && \mathrm{id} \end{pmatrix} \in \mathrm{End}(V_{2h+d}), \\ B = \begin{pmatrix} \mathrm{id} \\ & t^{-1} \cdot \mathrm{id} \\ && \mathrm{id} \end{pmatrix} \in \mathrm{End}(V_{2d+h}). \end{aligned} $$ 则 $N = B \cdot M \cdot A$ 满足: 当 $t \to 0$ 时, $N$ 是一个分块对角矩阵, 当 $t \in F^\times$ 时, $A,B$ 可逆, 故 $M,N$ 同构. 下面计算 $N$ 在 $t = 0$ 的分块对角阵, 左上和右下的两块是容易的, 难点在于识别 $$ D : x^h V_d \to x^d V_h, \quad p \mapsto \pi(u \cdot p) = x^d \cdot \pi_{<d}(u \cdot p / x^d), $$ 即 $$ x^h \cdot p \mapsto x^d \cdot \pi_{<d} (x^{h-d} \cdot u \cdot p), $$ 引入: $\chi \in V_h$, 则可以识别 $\langle x^d \cdot \pi_{<d} (x^{h-d} \cdot u \cdot p), \chi \rangle$ 为 $[x^{d-1}] (u \cdot p \cdot \chi)

. 这说明 D 也等价于 C_{a,h} (的某个换位). 进而

\Phi(C_{a, 3h + a - 1}) \ge 3 \cdot \Phi(C_{a, h}).

开始估计

定义 P(x,y) = \Phi(C_{x,y}). 对于一个固定的 x, P(x,-) 是上凸的. 这意味着有不等式

D(x,y) - D(x,y-1) \ge \dfrac{D(x,y') - D(x,y)}{y' - y}.

设 \Delta(x) = P(x,x). 考虑到

\begin{aligned} P(a,4a-1) - P(a,a) \ge 2 \Delta(a) \implies \\ P(a,a) - P(a-1,a-1) \ge \dfrac{2 \Delta(a)}{3a-1}, \end{aligned}

可知

\Delta(a) - \Delta(a-1) \ge \dfrac{2 \Delta(a)}{3a-1} + \dfrac{2 \Delta(a-1)}{3a-4}.

即

\dfrac{\Delta(a)}{\Delta(a-1)} \ge \dfrac{3a-1}{3a-3} \cdot \dfrac{3a-2}{3a-4}.

令 x = \dfrac 1 {a-1} 得到

\dfrac{\Delta(a)}{\Delta(a-1)} \ge \left(1 + \dfrac {2x}3 \right)^2 \ge (1+x)^{4/3}.

进而 \Delta(a) \ge a^{4/3}.

需要记住: P(a,b) = \Phi(C_{a,b}), 而 \chi(C_{a,b}) \le \mathrm R(C_{a,b}) = a+b-1, 因此 P(a,b) \le (a+b-1)^{1/t}, 进而 1/t \ge 4/3, 即 t \le \dfrac 34, 进而

矩阵乘法张量的任意特征

\lim_{n \to \infty}\dfrac{\log \chi(T_n)}{\log n} \le \dfrac 94.

后记

看起来这里就有很多很平凡的推广, 比如说如果让 E 不是二维空间了考虑其 Koszul 复形等等. 无一例外, 做不到比 \dfrac 94 更低.

但是总之, OpenAI 的这篇论文给了我们一个非常新的方向, 在此之前我认为人类是吃白饭的, 从 \omega \le \log_2 7 开始就在路径依赖, 没什么问题.

事实上, 张量特征是性质更好的张量秩, 导致下界分析或者本文中的综合分析也成为可能. 匹配和这一节的引理证明是我把我的证明顶替掉 OpenAI 的, 这导致了 F 现在可以是任意特征的代数闭域.