单色矩形划分数

形式陈述 ​

划分数的定义 ​

设 $f:X\times Y\to Z$，其中 $X,Y$ 有限。一个单色矩形划分是矩形族

$$\mathcal{R}=\{A_1\times B_1,\dots ,A_k\times B_k\},$$

满足三项条件：每个矩形上 $f$ 恒定；不同矩形两两不交；它们的并恰为 $X\times Y$。$f$ 的单色矩形划分数定义为

$$\chi (f)=\underset{\mathcal{R}}{min}|\mathcal{R}|.$$

这里的块是组合矩形公理库通信矩阵与组合矩形Communication matrix · Combinatorial rectangle将两方函数排成输入行列矩阵，并以行集和列集的笛卡尔积刻画协议能够共同隔离的区域。，行集和列集无需连续。划分必须给每个输入对唯一归属；允许重叠的 cover 是另一个量，不能用同一个 $\chi (f)$ 表示。

与确定性通信的基本关系 ​

本页固定如下确定性 bit 协议口径：每个发送位都进入双方可见的 public transcript；执行必须停在双方都能由完整 transcript 识别的公开叶，叶标签就是双方输出；为了让叶或输出标签成为公开信息而发送的位也计入最坏通信。记这一口径下的最小最坏成本为 $D^{\mathrm{cc}}(f)$。输出集合 $Z$ 使用固定长编码，长度为 ${\ell }_Z=\lceil {\log }_2|Z|\rceil$。

在这个“双方输出、公开叶、输出通信计费”的 convention 下，有精确的初等夹逼

$$\boxed{{\displaystyle \lceil {\log }_2\chi (f)\rceil \le D^{\mathrm{cc}}(f)\le \chi (f)+{\ell }_Z}}.$$

左侧是最常用的协议下界：若任何单色划分都需要很多块，协议就必须产生足够多 transcript。右侧说明一个已知划分至少可以被编码成某条协议，但它不声称只用 $\log \chi (f)$ bit；双方通常不能各自判断输入属于哪个矩形。若另定义只要求 Bob 输出的 $D_{\mathrm{Bob}}^{\mathrm{cc}}(f)$，下面构造可省掉最后的 ${\ell }_Z$ bit，但那是另一套成本口径，不能与框中同一个符号混用。

下界证明：叶矩形形成划分 ​

设确定性协议 $\mathrm{\Pi }$ 最坏发送 $c$ bit。把消息展开成逐 bit 的协议树公理库协议树与通信 transcriptProtocol tree · Communication transcript用逐 bit 的有根树表示完整通信策略，并把一次执行产生的根叶路径区分为 transcript。后，深度至多 $c$ 的二叉树最多有 $2^c$ 个可达叶。

每个输入对沿唯一根叶路径终止，所以叶的输入集两两不交并覆盖 $X\times Y$。协议树的矩形归纳说明，每个叶输入集是 $A_t\times B_t$；协议零误差正确又保证同一叶只有一个正确输出，因此该矩形单色。可达叶由此给出一个单色矩形划分。

于是

$$\chi (f)\le \mathrm{\#}\{\text{可达叶}\}\le 2^c.$$

两边取二进制对数得到 $c\ge \lceil {\log }_2\chi (f)\rceil$。再对所有正确协议取最小值，便得左侧结论。证明没有把输出值的种数当成叶数；同一个输出往往需要许多不同叶矩形。

上界证明：发送行成员向量 ​

取一个含 $k=\chi (f)$ 个矩形的最优划分，公开编号为 $R_j=A_j\times B_j$。Alice 根据 $x$ 计算长度 $k$ 的 bit 向量

$$u(x{)}_j=\mathbf{1}[x\in A_j]$$

并把整个向量发给 Bob。Bob 已知 $y$，因此能检查哪些 $j$ 同时满足 $u(x{)}_j=1$ 与 $y\in B_j$。由于矩形族划分 $X\times Y$，恰有一个编号满足两项条件；Bob 输出该矩形的单色标签。

Bob 随后发送该矩形的输出标签，使答案成为公开 transcript 的一部分。通信共 $k+{\ell }_Z$ bit，所以 $D^{\mathrm{cc}}(f)\le \chi (f)+{\ell }_Z$。协议可能很低效：Alice 要检查全部行集，消息长度也与块数线性相关。它的作用是给出无额外结构时可靠的存在性上界，而不是把任意划分自动压缩成对数通信。

例子与边界 ​

XOR 的紧例 ​

令 $X=Y=\{0,1\}$，$f(x,y)=x\oplus y$。通信矩阵为

$$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$$

任意含两个格的单色候选若取同一行或同一列，两个值不同；若取对角线的同色格，交叉闭合又会迫使纳入异色格。因此每个单色矩形至多含一个格，$\chi (f)=4$。

下界给出 $D^{\mathrm{cc}}(f)\ge {\log }_{2}4=2$。Alice 发送 $x$，Bob 算出异或；若要求双方都知道输出，Bob 再发送结果，共 $2$ bit，恰好达到该口径的下界。若约定只由 Bob 输出，则只需 Alice 的一 bit，说明输出方和是否计回传必须先与 $D^{\mathrm{cc}}$ 的 convention 对齐；同一矩阵不能替未声明的协议口径做决定。

Partition 不是 cover ​

一个 $1$-矩形 cover 只要求所有 $1$-输入至少落入某块，块之间可以重叠，也不必处理 $0$-输入。重叠意味着同一输入可能拥有多份证书，无法直接成为确定性协议叶的唯一归属。非确定性通信更自然地对应这种 cover。

反过来，确定性叶一定形成整张矩阵的划分。拿 cover 大小代替 $\chi (f)$ 会省掉“互不相交”和“覆盖所有输出”两项约束，得到的对数未必是确定性下界。证明中应明确对象是 cover 还是 partition，而不是笼统写“用若干矩形覆盖”。

经典理论还能在特定设置中改进初等上界，但那需要额外的矩形选择与递归论证。本页的结论只使用定义即可完整证明，因而是后续比较各种矩形度量时最稳固的基线。

参考资料

• Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Sections 1.2–1.3.
• Alfred V. Aho, Jeffrey D. Ullman, and Mihalis Yannakakis, “On Notions of Information Transfer in VLSI Circuits,” STOC, 1983, pp. 133–139.
• Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapters 1–2.