Log-rank 猜想

秩小意味着所有行落在低维实向量空间，却不直接告诉双方如何只用少量 bit 找到当前格。上界路线要把“低维”转成“存在一个足够大的单色矩形”：协议先用少量通信定位该矩形，删去或限制一批行列，使剩余矩阵秩或尺寸下降，然后递归。只证明一个大矩形还不够；递归每层损失若过大，深度仍会是 $\sqrt{r}$ 而非 $\mathrm{polylog}r$。

猜想的困难恰在这种局部到全局的转换。线性相关允许正负系数相消，而单色矩形要求许多离散条目完全一致。实秩记录代数自由度，协议树记录可由双方局部识别的组合结构；两者之间没有已知的无损翻译。

取二 bit Equality，行列按 $00,01,10,11$ 排列，则

Alice 发送自己的两 bit，Bob 比较后再发送一 bit 使双方知道输出，总通信至多 $3$；若只要求 Bob 输出，则为 $2$。这可复算实例与猜想相容，但没有证明一般上界：单位矩阵的行结构过于简单。

边界一是“实秩”不能漏写。矩阵 $J-I$ 在三阶时实秩为 $3$，在特征 $2$ 上秩为 $2$，同一数表产生不同参数。边界二是不能把猜想写成 $D=O(\log r)$；已知构造给出超线性的 $D$ 与 $\log r$ 间隔，所以即便猜想成立，指数 $C$ 也不由基础秩下界确定。边界三是它与近似秩公理库近似秩Approximate rank · Entrywise approximate rank在逐项最大绝对误差约束内寻找最低实秩矩阵，量化通信矩阵可被低维实矩阵近似的程度。口径相反：本页用精确实秩猜确定性上界，近似秩则放宽逐项数值并形成随机/量子模型的代数下界。两页因此镜像标注对照，而不是互相推出。

若猜想成立，任何能证明 $r\le 2^{(\log N{)}^{O(1)}}$ 的 $N\times N$ 总函数矩阵都会自动得到 polylogarithmic 确定性协议；这会把协议设计归约为实秩估计。反过来，寻找反例必须同时保持实秩很低并排除所有浅协议树，单纯展示秩下界不紧不够。

当前 $O(\sqrt{r})$ 上界也有实际含义：它比逐行发送的 $O(r)$ 型代数协议更强，并把改进猜想归结为更大的低秩单色子矩形或更高效的递归势能。该结论不自动适用于有错误协议、关系问题、partial function 或其他域；每次迁移都必须重建矩阵参数与协议模型的量词。