结果族 116：Uniform black-box noncommutative identity testing across characteristics · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
想象无数台只做加减乘的计算器在流水线上出厂，说明书只印三个参数：素数 @@M@@p@@、变量数 @@M@@n@@、电路规模 @@M@@s@@。这篇论文造了一台”信号发生器”：输入这三个数字，它吐出一组固定矩阵。凡是这个型号里”并非恒为零”的计算器，吃进这组信号，输出必不为零——哪怕是 @@M@@p=2@@ 这种最别扭的算术世界也不例外。
关键词卡片
@@M@@x_1x_2@@ 与 @@M@@x_2x_1@@ 不再相同。@@M@@p@@（characteristic @@M@@p@@）：@@M@@p@@ 个 1 相加得零的算术世界，如有限域 @@M@@\mathbb F_p@@。@@M@@s@@ 限制门的个数。看个具体例子
先看为什么必须用矩阵：@@M@@f=x_1x_2-x_2x_1@@ 不是零多项式，但代入任何标量 @@M@@a,b@@ 都得 @@M@@ab-ba=0@@——标量会漏检，矩阵不会。
定理（数字版）：机器输入二进制素数 @@M@@p@@ 与一进制的 @@M@@n,s@@，在 @@M@@C(n+s+L+1)^k@@ 比特时间内输出维度 @@M@@O(n^3s^6)@@ 的 @@M@@\mathbb F_p@@ 矩阵元组；特征 @@M@@p@@ 的一切域（含任意扩域与 @@M@@p=2@@）上、规模 @@M@@\le s@@ 的非零公式代入必非零，同一元组还适用于无圈代数路径程序。
为什么值得关心
正特征是此前的空白：老方法里的”积分”要除以正整数，在 @@M@@\mathbb F_p@@ 里寸步难行。本文改用乘法位移绕开障碍，补齐了非交换黑盒恒等测试版图的正特征半壁。
暂无形式化证明（AI 结果待核验）
第一级台阶
入门导读把论文比作一台”信号发生器”：它不认识任何一台具体的计算器，只读说明书上的型号参数。翻译成半数学的说法：对象是只做加法与乘法、且乘法讲究先后顺序的算术表达式；发生器是这样一个过程——输入素数、变量个数、规模上限三个数，产出一组固定尺寸的方阵；”万能试纸有效”是指：凡是真不为零的表达式，代入这组方阵后算出的矩阵仍不为零，哪怕算术世界本身是别扭的特征二。
第二级台阶
用本科术语精确化：非交换多项式是自由代数 @@M@@F\langle x_1,\dots,x_n\rangle@@ 的元素，以字母的有序字为基，乘法是字的拼接。非交换公式是一棵树：叶上放变量或标量，内部节点做二元加法或按序乘法；规模 @@M@@s@@ 是全部节点数，没有除法门，也不共享子表达式。恒等测试（PIT）问这样的表达式是否恒为零；打击点（hitting point）就是先于公式选定的矩阵元组 @@M@@(T_1,\dots,T_n)@@，使该尺寸下一切非零公式代入后非零。
第三级台阶
定理 1 在此陈述：一台确定性图灵机输入二进制的素数 @@M@@p@@（素性是承诺）与一进制的 @@M@@n,s@@，在 @@M@@(n+s+L+1)^{O(1)}@@ 比特时间内输出维数 @@M@@d=O(n^3s^6)@@ 的 @@M@@\mathbb F_p@@ 矩阵元组。假设”无除法、树形、规模 @@M@@\le s@@“分别挡住了逆元无定义、子表达式共享导致的计数失控、以及首个非零系数出现过晚的麻烦。结论是：对特征 @@M@@p@@ 的一切域 @@M@@F@@（含任意扩域与 @@M@@p=2@@），非零公式的代入值必非零；推论还覆盖把 @@M@@s@@ 换成顶点数的无圈代数路径程序。
对任意素数 @@M@@p@@，一台确定性算法仅凭 @@M@@p@@、变量数 @@M@@n@@ 与公式规模 @@M@@s@@，在多项式比特时间内输出一组 @@M@@O(n^3s^6)@@ 维的 @@M@@\mathbb F_p@@ 矩阵，它同时检测特征 @@M@@p@@ 的一切域（含任意扩域与 @@M@@p=2@@）上所有规模至多 @@M@@s@@ 的非零非交换公式。
多项式恒等测试（polynomial identity testing, PIT）问：给定由算术运算组成的多项式，判断它是否恒为零。在非交换设定里变量必须取矩阵值——标量代入会抹去换位子 @@M@@x_1x_2-x_2x_1@@ 这类非零多项式。黑盒模型只允许代入求值，于是自然要问：能否在看到公式之前就选定一组矩阵（打击点，hitting point），使该尺寸下任何非零公式代入后都非零？Raz–Shpilka（2005）对给出描述的公式已有白盒确定性多项式时间测试；Forbes–Shpilka（2013）构造了拟多项式大小的黑盒打击集，但要求域基数足够大，且把有限打击集块对角拼接成单一元组时维度随集合大小膨胀。特征零的姊妹篇给出维度 @@M@@2ns^2@@ 的单个有理矩阵打击点，但其证明依赖形式积分与求导：形式积分要除以正整数，普通微分在特征 @@M@@p@@ 下消灭 @@M@@p@@ 次幂，互异的整数极点位置也可能在有限域中重合，而且把有理元组模 @@M@@p@@ 归约并不自动保持打击性质。本文补齐正特征这一半。
定理 1：存在确定性图灵机与绝对常数 @@M@@C,k@@，输入二进制的素数 @@M@@p@@（素性是承诺）与一进制的 @@M@@n,s@@，输出维数 @@M@@d=O(n^3s^6)@@ 与元组 @@M@@(T_1,\ldots,T_n)\in\Mat_d(\mathbb F_p)^n@@，满足：对特征 @@M@@p@@ 的任何域 @@M@@F@@、任何由规模 @@M@@\le s@@ 的无除法非交换公式（noncommutative formula）计算的非零多项式 @@M@@f@@，同一元组视为 @@M@@F@@ 上矩阵后仍有 @@M@@f(T_1,\ldots,T_n)\ne0@@。以 @@M@@L=\lceil\log_2p\rceil@@ 记特征的比特长，则运行时间与输出长度均不超过 @@M@@C(n+s+L+1)^k@@。生成器看不到公式与系数，其保证对 @@M@@\mathbb F_p@@ 的一切扩域一致成立，对 @@M@@p=2@@ 也不需要任何特征与规模之间的关系。推论还把同样构造推广到 @@M@@m@@ 顶点的无圈代数路径程序（acyclic algebraic path program），维数 @@M@@d=O(n^3m^6)@@。
整个证明保留”字级数 + 矩阵系统”的组织，但把特征零版本中的微分算子换成无穷阶乘法位移（multiplicative shift）。先在 @@M@@K=F(t)@@ 上定义 @@M@@\sigma(g)(z)=g(tz)@@，再对每个字母 @@M@@i@@ 定义算子 @@M@@\mathcal J_i@@：要求 @@M@@\mathcal J_i(g)@@ 零常数项且 @@M@@(\sigma-1)\mathcal J_i(g)=\frac{z}{1-(1+t)^iz}\,g@@。作用在 @@M@@z^r@@ 系数上相当于除以 @@M@@t^r-1@@——由于 @@M@@t@@ 超越，它在任何特征下都非零，这正绕开了”积分要除以正整数”的障碍。由 @@M@@h_\epsilon=1@@、@@M@@h_{iw}=\mathcal J_i(h_w)@@ 递归定义字级数后，论文用极小关系论证证明它们线性无关：若存在有理函数系数的关系式，对其施加 @@M@@\sigma@@ 再相减可逐层降阶，最终化归为一个极点障碍——@@M@@\sigma(R)-R@@ 不可能恰有一个极点落在无穷位移轨道 @@M@@\{t^j\alpha\}@@ 中，而各字母对应的极点 @@M@@(1+t)^{-i}@@ 分属两两不交的轨道，用 @@M@@t=0@@ 与 @@M@@t=-1@@ 处的赋值即可判别。于是 @@M@@f\ne0@@ 蕴含 @@M@@h_f\ne0@@。
再利用公式的小规模性控制 @@M@@h_f@@ 首个非零系数最晚出现的位置。先把规模 @@M@@s@@ 的公式化为至多 @@M@@2s@@ 个顶点的无圈路径程序，得到严格上三角矩阵 @@M@@B_1,\ldots,B_n\in\Mat_m(F)@@（@@M@@m\le2s@@）与行、列向量 @@M@@u,v@@，使每个字的系数写成 @@M@@f_w=uB_wv@@；令 @@M@@H=\sum_wB_wh_w@@，则 @@M@@H(0)=I@@、@@M@@\sigma(H)=(P/Q)H@@，且 @@M@@P,Q@@ 的 @@M@@z@@-次数至多 @@M@@n@@。接着证明可复用的阶数界（order bound）：@@M@@uHv\ne0@@ 蕴含 @@M@@\ord_z(uHv)\le n\binom m2@@。其证明把微分系统的行列式法（Moura 型重数估计）搬到逐次位移：在分量张成的空间中取首阶 @@M@@c_i@@ 互异的基，其 Casoratian（逐次位移行列式）的首项是 @@M@@t^{c_i}@@ 上的 Vandermonde 行列式，因 @@M@@t@@ 的乘法阶无穷，它在包括特征 2 在内的一切域中非零；再用有理次数界控制相关子式的阶数。
最后两步完成有限化。先取截断长度 @@M@@N=1+n\binom{2s}{2}@@，把 @@M@@\mathcal J_i@@ 实现为显式的 @@M@@N\times N@@ 有理矩阵 @@M@@U_i@@，元素为 @@M@@(1+t)^{i(r-q-1)}/(t^r-1)@@，阶数界保证 @@M@@f(U)\ne0@@。再”下降”回素域：公分母 @@M@@D(t)=\prod_{r=1}^{N-1}(t^r-1)@@ 一次性清除所有出现的分母，剩余 @@M@@t@@-次数不超过 @@M@@E=1+\binom N2+n(N-1)@@；模 @@M@@t^E@@ 截断后，把 @@M@@\mathbb F_p[t]/(t^E)@@ 上的乘法实现为 @@M@@E\times E@@ 矩阵（每块为移位型 Toeplitz 阵），得到 @@M@@d=NE=O(n^3s^6)@@ 的素域矩阵，下降引理保证非零性对任何扩域系数保持。文末给出逐条目计算的显式算法：@@M@@(t^r-1)^{-1}@@ 用模 @@M@@t^E@@ 的几何级数展开，全部运算在图灵机上有 @@M@@C(n+s+L+1)^k@@ 的比特界。
本文暂无形式化证明，按 OpenAI 官方声明，”未经形式化的结果可能有问题”，请以社区核验为准。它是本族三篇中的正特征支柱：特征零姊妹篇（维度 @@M@@2ns^2@@）提供同一证明骨架的原型，本文以乘法位移替换其中的解析工具，并把阶数界与素域下降直接在给定特征内证明。代价是维度增大（@@M@@O(n^3s^6)@@ 对 @@M@@2ns^2@@），但不需要 @@M@@p@@ 的任何下界，且同一元组对该特征下全部域一致有效。
问 1：证明里最要害、也最脆弱的一环是哪里？
答：字级数 @@M@@\{h_w\}@@ 的线性无关性（words 一节）。它靠”极小关系 + 极点障碍”论证：对有理函数 @@M@@R@@，差 @@M@@\sigma(R)-R@@ 不可能恰有一个极点落在无穷位移轨道 @@M@@\{t^j\alpha\}@@ 中，而各字母对应的极点 @@M@@(1+t)^{-i}@@ 分属两两不交的轨道。这是”非零公式 ⇒ 非零级数”整条链条的根；轨道不相交的判别依赖 @@M@@t@@ 超越这一事实，消项细节最容易被生成式证明写错。
问 2：为什么必须假设”无除法”？去掉会怎样？
答：证明把公式系数写成 @@M@@f_w=uB_wv@@ 的无圈路径程序表示，再对字级数做阶数控制，全程没有为逆元素留位置。含逆门的非交换有理公式需要另一套处理，本文未展开（结果族中另有一篇处理有理公式）。
问 3：与已有工作相比，真正的新意是什么？
答：Forbes–Shpilka 的拟多项式打击集需要域基数假设，且把有限打击集块对角拼成单一元组时维数随集合大小膨胀；本文给出单个多项式维数元组，只依赖 @@M@@(p,n,s)@@，不需要 @@M@@p@@ 的任何下界，并对特征 @@M@@p@@ 的一切扩域一致成立。相对特征零姊妹篇（维度 @@M@@2ns^2@@），新意是把积分与微分换成乘法位移 @@M@@\sigma(g)(z)=g(tz)@@——系数上相当于除以 @@M@@t^r-1@@，因 @@M@@t@@ 超越在任何特征非零——从而首次覆盖正特征。
问 4：特征 2 被反复点名，卡点究竟在哪？
答：阶数界（order 一节）把微分系统的行列式法搬到逐次位移：取首阶 @@M@@c_i@@ 互异的基，其移位行列式的首项是 @@M@@t^{c_i}@@ 上的 Vandermonde 行列式；普通交错论证在特征 2 会退化，这里靠 @@M@@t@@ 的乘法阶无穷保证诸 @@M@@t^{c_i}@@ 在包括特征 2 的任何域中互异。引言强调对 @@M@@p=2@@ 不需要特征与规模的任何关系，这正落在该论证上。
问 5：这种 AI 生成证明最可能的出错模式是什么？
答：三处高危。一是符号组合断言的逐项核对，如 Vandermonde 首项与有理次数界的常数；二是”下降”步骤——公分母 @@M@@D(t)=\prod_{r=1}^{N-1}(t^r-1)@@ 清分母后剩余 @@M@@t@@-次数不超过 @@M@@E=1+\binom N2+n(N-1)@@ 的界若算错，模 @@M@@t^E@@ 截断可能把非零性截没；三是”同一元组对一切扩域保持打击性质”的下降引理。论文给出显式算法与比特界，但均需人工复算；本文未形式化。
问 6：谁会用到它，下游推论是什么？
答：做非交换 PIT 与去随机化的人：黑盒测试的打击集被压成单个多项式规模元组，评估一个公式只需一次矩阵代入；对 @@M@@m@@ 顶点无圈代数路径程序的推论（维数 @@M@@O(n^3m^6)@@）直接服务代数分支程序的黑盒测试。论文未讨论向交换 PIT 的推广。
总评
这项工作把非交换黑盒恒等测试补齐到任意正特征，以乘法位移干净绕开”积分除以整数”的障碍，是真实的方法进步；最大风险在于极点障碍、阶数界、素域下降这条长引理链未经形式化核验，任何一环算错都足以推翻定理。