通信矩阵与组合矩形

一条固定 transcript 只能让 Alice 的消息筛行、Bob 的消息筛列。比如当前可能集为 $A\times B$，下一位由 Alice 发出；固定该位为 $0$ 后，只留下 $A_0=\{x\in A:\varphi (x,t)=0\}$，Bob 的候选集仍为整个 $B$。新区域是 $A_0\times B$。下一位由 Bob 发出时则只缩小第二个因子。这解释了矩形为何在每一步保持，而不只是最终图形恰好像矩形。

筛选规则依赖此前记录 $t$ 并不破坏证明，因为分析一条固定 transcript 时，$t$ 已经固定。组合矩形的“形状”来自双方知识分离，而不是矩阵坐标上的连续性；交叉闭合正是可直接检验的乘积证据。

Equality 矩阵中的非连续矩形 ​

令 $X=Y=\{00,01,10,11\}$，$f(x,y)=1$ 当且仅当 $x=y$。$M_f$ 的对角线为 $1$，其余位置为 $0$。取

$A$ 与 $B$ 在字典序中都不是连续区间，但 $A\times B$ 的四个输入对全部满足 $x\ne y$，因此这是一个 $0$-单色组合矩形。把它画在矩阵上会得到四个分散格；“分散”不妨碍其乘积结构。

相反，只取两个对角格

并不是矩形。它的行、列投影都是 $\{00,11\}$，若 $S=A\times B$，就还必须含有 $(00,11)$ 与 $(11,00)$；这两个交叉格恰好缺失。$S$ 虽然是 $1$-单色集合，却不是单色矩形，说明“所有值相同”只是矩形下界工具的一半条件。

transcript 为什么切出矩形 ​

上面的逐步筛选论证对每条固定 transcript 都成立，完整的树深归纳见协议树与 transcript理路协议树与通信 transcriptProtocol tree · Communication transcript用逐 bit 的有根树表示完整通信策略，并把一次执行产生的根叶路径区分为 transcript。。现在进一步假定叶结点标记一个公开输出，就能把矩形结构转为下界工具。

如果协议正确计算 $f$，叶结点只有一个输出，于是 $A_t\times B_t$ 必须单色。所有可达叶的矩形两两不交，并覆盖整个 $X\times Y$，因为每个输入对沿确定规则到达唯一叶。这给出从通信协议到单色矩形划分的方向；反向从任意矩形集合构造低通信协议，则还需要能让双方逐步识别所属矩形，不能只靠“矩形数量很少”一句话完成。

对于关系问题，矩阵单元可能包含多个合法输出，而不是单一值。此时一个叶标记 $z$，只需保证其矩形内每个输入都允许 $z$。若预先为每个输入选定唯一合法输出，就把关系收紧成了一个函数：计算该函数一定能解原关系，反向却不成立，所以最优成本只可能不变或增加。例如原关系在每个输入都允许 $0$ 和 $1$，恒输出 $0$ 无需通信；若分析者选定 Equality 作为唯一输出，便人为引入了非零通信需求。

单色性还依赖输出约定。若只有 Bob 输出，一个 transcript 矩形内的答案可以随 $y$ 改变；例如 $f(x,y)=y_1$ 完全无需消息，但整个输入矩阵并不单色。让 Bob 最后公开发送答案，才恢复本页使用的单色叶结论；布尔输出至多多花一 bit。

边界与后续用途 ​

从单色矩形划分导出通信下界，可以衡量矩形数目、覆盖结构、代数秩或概率质量。这些度量把“每条通信记录能隔离多大的输入区域”转成需要多少通信比特的限制。

随机协议固定随机币后也得到矩形叶，但不同随机选择产生不同划分，而且单棵树可能有错误叶。因此确定性单色划分结论不能原样套用到允许错误的协议；需要结合输入分布和近单色条件重新计量。

矩阵表示还依赖输入编码。若同一抽象对象有不同私有输入划分，行列集合会改变，组合矩形族也随之改变。通信下界属于“函数加输入分割加协议模型”的整体，而不是脱离模型后只属于函数名字。