随机 Set Disjointness 下界：证明纲要

Alice 持有集合 $A\subseteq[n]$ ，Bob 持有 $B\subseteq[n]$ 。他们只想回答一个是非问题： $A$ 与 $B$ 有没有共同元素？答案只有一位，但在经典随机通信模型中，即使允许常数错误率，最坏情况下仍需要 $\Omega(n)$ 比特通信。

困难不在于答案很长，而在于双方必须排除分散在不同位置上的潜在交集。一个很短的交互记录会把许多输入对放在一起；下界的核心是证明：只要这块输入集合包含足够多的不相交输入，它就无法把“恰有一个交点”的输入全部排除。[1]

本文完整展开从矩形腐败引理到线性通信下界的推导，并解释引理采用的困难分布与组合机制。引理内部的组合估计是需要单独证明的非平凡部分；这里将其准确陈述为所调用的核心定理，而不把直觉解释当成完整证明。

形式陈述

任务与结论的口径

用特征向量 $x,y\in\{0,1\}^n$ 表示集合，约定

\operatorname{DISJ}_n(x,y)=1 \iff\sum_{i=1}^n x_i y_i=0.

也就是说，输出 $1$ 表示不相交。本文采用经典随机通信复杂度，允许任意轮次与公开随机数，要求每个输入对上的错误概率至多 $1/3$ ，成本是最坏通信长度。输出可先由 Bob 产生；为方便矩形证明，最后把这一个输出比特发给 Alice，只增加一比特。

上界很直接：Alice 把自己的 $n$ 位向量发给 Bob。因此，要得到 $\Theta(n)$ ，只需证明随机协议不能把成本降到 $o(n)$ 。改变错误率为任意固定 $0<\varepsilon<1/2$ 的常数，不改变这一级别；独立重复常数次并取多数即可相互转换。[1][2]

核心矩形引理：几乎全对的大矩形有多大

Razborov 型腐败引理断言：存在与 $n$ 无关的常数 $a,\gamma>0$ ，使充分大 $n=4m-1$ 下，每个组合矩形 $R$ 都满足

\boxed{\mu_1(R)\ge a\,\mu_0(R)-2^{-\gamma n}.}

常数的具体值取决于引理的标准化，线性下界只需要它们是正常数。[1][3]

当 $\mu_0(R)$ 明显大于指数小量时，引理要求 $R$ 在恰有一个交点的输入上也有可观质量。因此，它不可能成为一个既很大、又几乎不会错判的接受区域。

指数小的加性误差不能随意删除。例如只包含一个不相交输入对的单点矩形，满足 $\mu_1(R)=0$ 而 $\mu_0(R)>0$ 。引理允许这种极小的纯净矩形存在；下界来自覆盖大部分正确输入需要指数多个这样的矩形。

“大小”在这里是困难分布下的概率质量，不是矩形在整张 $2^n\times2^n$ 通信矩阵中占了多少格。混淆这两种大小，会让后面的求和失去依据。

直觉

固定随机数后，短协议为什么产生矩形

把协议的所有随机数固定，就得到确定性协议。考虑它的一条完整消息记录 $t$ ：所有产生该记录的输入对组成集合

R_t=\mathcal A_t\times\mathcal B_t,

称为组合矩形。

原因可以沿着协议树逐轮证明。初始可能输入是全部行与全部列的乘积。Alice 发言时，她的下一条消息只取决于自己的输入与已有记录，因此只筛掉一些行；Bob 发言时则只筛掉一些列。行筛选与列筛选交替进行，仍保留乘积结构。

若二进制协议深度至多为 $c$ ，叶子数不超过 $2^c$ ，这些叶子矩形互不相交并覆盖全部输入。加入最后输出比特后，每个叶子都有固定输出标签。若没有这一步，而 Bob 在相同记录下依自己的输入作不同输出，就不能直接把整片叶子矩形称作接受矩形。

对于一个有错误的确定性协议，标记为 $1$ 的矩形并不一定只含真正的 $1$ 输入。腐败方法正是定量研究：一个接受矩形里不得不混入多少真正的 $0$ 输入。

困难分布：不相交与恰好相交一次

先取 $n=4m-1$ ，限制双方输入都是大小为 $m$ 的集合。定义两个均匀分布：

\mu_0:\ |A|=|B|=m,\ A\cap B=\varnothing; \qquad \mu_1:\ |A|=|B|=m,\ |A\cap B|=1.

下标表示交点数，因此 $\mu_0$ 支持的是 DISJ 的 $1$ 输入， $\mu_1$ 支持的是 $0$ 输入。证明中始终保留这一区分，避免把分布下标误当作函数输出。

取混合分布 $\mu=(\mu_0+\mu_1)/2$ 。无论来自哪个分量，Alice 单独看到的 $A$ 都是在所有 $m$ 元子集中均匀分布，Bob 的边缘分布也一样。这由对底层元素的置换对称性得到。困难信息藏在两份集合的对应关系里，任何一方都不能只凭自己的输入分辨分量。

只分析这个受限输入族已经足够。一个能处理所有输入的协议，自然也必须处理该分布支持上的输入。对一般 $n$ ，选取不超过 $n$ 的最大 $4m-1$ 大小子宇宙并把其余坐标固定为零，即可保留线性级别的下界。

从引理到通信下界：把常数与错误全部算清

假设原随机协议使用 $c$ 比特，错误率至多 $1/3$ 。先用概率放大独立重复常数次并取多数，把错误降到一个小常数 $\delta$ ，再发送输出比特。记所得成本为 $c'\le kc+1$ ，其中 $k$ 只依赖所选的 $\delta$ ，与 $n$ 无关。

在分布 $\mu$ 下，协议平均错误也至多为 $\delta$ 。再对随机数平均，必有某种固定随机数，使得到的确定性协议在 $\mu$ 下错误至多为 $\delta$ 。这是 Yao 原理在下界中常用的固定随机数方向。

设这个确定性协议的所有接受叶子矩形为 $R_1,\ldots,R_\ell$ ，并记其不交并为 $\mathcal U$ 。由混合分布上的错误界，

\tfrac12\bigl(1-\mu_0(\mathcal U)\bigr) +\tfrac12\mu_1(\mathcal U)\le\delta.

因此两项分别满足

\mu_0(\mathcal U)\ge1-2\delta, \qquad \mu_1(\mathcal U)\le2\delta.

对每个接受矩形应用引理并相加，利用叶子矩形互不相交，得到

\begin{aligned} 2\delta &\ge\mu_1(\mathcal U) =\sum_{j=1}^{\ell}\mu_1(R_j)\\ &\ge a\sum_{j=1}^{\ell}\mu_0(R_j)-\ell2^{-\gamma n}\\ &\ge a(1-2\delta)-\ell2^{-\gamma n}. \end{aligned}

选择 $0<\delta\le a/[4(a+1)]$ ，括号中的剩余常数至少为 $a/2$ ，于是

\ell\ge\frac a2\,2^{\gamma n}.

另一方面 $\ell\le2^{c'}$ ，所以

c'\ge\gamma n+\log_2(a/2)=\Omega(n).

由于 $c'\le kc+1$ 且 $k$ 为常数，原成本同样满足 $c=\Omega(n)$ 。与发送整个输入的上界结合，得到

R_{1/3}(\operatorname{DISJ}_n)=\Theta(n).

这段推导的关键并非“某个矩形必然出错”，而是所有接受矩形合起来要覆盖接近一的 $\mu_0$ 质量，同时只容许很小的 $\mu_1$ 质量。每个矩形的指数小例外相加后，强迫矩形数量达到指数级。

核心引理为什么与矩形结构有关

一种经典证明安排把底层宇宙随机分成

T_A\ \dot\cup\ T_B\ \dot\cup\{i\}, \qquad |T_A|=|T_B|=2m-1.

Alice 从 $T_A\cup\{i\}$ 中选 $m$ 个元素，Bob 从 $T_B\cup\{i\}$ 中选 $m$ 个元素。两侧的普通元素彼此分离，因此唯一可能的公共元素就是 $i$ 。若各自均匀选择，则双方各以概率 $1/2$ 包含 $i$ ：三种包含模式不相交，只有双方都包含时恰有一个交点。

现在考虑矩形 $R=\mathcal A\times\mathcal B$ 。固定一次分割，记 $p_0,p_1$ 为 Alice 在“不含 $i$ ／含 $i$ ”两种条件下选入 $\mathcal A$ 的概率；记 Bob 对应的概率为 $q_0,q_1$ 。由于固定分割后双方分别抽样，矩形出现概率分解成这些单方概率的乘积。

对随机分割取平均，置换对称性给出

\mu_0(R)=E[p_0q_0],\qquad \mu_1(R)=E[p_1q_1].

例如第一式只使用双方都不含 $i$ 的模式；其无条件输入对仍均匀分布在不相交的 $m$ 元集合对上。

于是引理转成一个问题：如果很多分割下 $p_0q_0$ 不小，能否让几乎所有分割下的 $p_1q_1$ 都很小？一个并非指数稀少的集合族，不能持续强迫大量随机选中的元素都被排除；熵与组合计数把这种直觉变为定量约束，再控制异常分割的加权贡献，得到腐败不等式。[3]

这最后的“异常分割贡献控制”正是难点。单纯声称随机交换有混合性，或只引用某个图的谱隙，并不能自动得到所需的指数小加性误差。完整阅读引理证明时，应追踪的对象是条件密度、集合族大小与坏分割的概率质量。

例子与边界

这条证明排除了什么，又没有声称什么

随机指纹对相等性有效，并不意味着它也能把集合不相交压到对数通信。相等性是比较两个整体对象；DISJ 要发现的是跨两方对应位置上的一个潜在共同元素。区别体现在困难分布与矩形结构中，而非“都可以哈希”这一表面相似性。

本文的矩形论证针对经典通信。量子消息不再对应同样的确定性矩形分割，不能把经典 $\Omega(n)$ 原封不动移植过去。其他输入限制，例如集合很稀疏、宇宙结构特殊或有额外承诺，也应重新检查困难分布是否仍可嵌入。

进一步学习可沿两条线推进：一条进入腐败与矩形界，补全核心组合引理；另一条进入信息复杂度，研究同一下界如何由必须揭示的输入信息推出。

推论与应用

一个具体应用：单遍精确去重需要线性空间

设一个单遍流算法可以精确计算不同元素的数量，并以至少 $2/3$ 的概率正确，工作内存为 $s$ 比特。Alice 先把集合 $A$ 的元素送入算法，然后把当前内存状态发给 Bob；Bob 接着输入 $B$ 的元素，读取最终去重计数。

在上述困难输入上， $|A|=|B|=m$ ，所以

|A\cup B|= \begin{cases} 2m,&A\cap B=\varnothing,\\ 2m-1,&|A\cap B|=1. \end{cases}

这就用 $s$ 比特通信解决了 DISJ 的困难承诺问题，故 $s=\Omega(n)$ 。算法随机数可由公开随机数实现，状态传递保留了流计算的继续执行能力。

这里用的是精确计数：一个只保证常数相对误差的估计算法，不必区分 $2m$ 与 $2m-1$ ，因此不能直接套用这个归约。流的遍数、输出精度与随机成功标准，都必须在归约前后保持一致。

CONGEST的完整割模拟把本页的公共币线性通信下界用于四色四环检测。图族直径至多3，但每轮跨割容量有限，精确模拟推出 $\Omega(N/\log N)$ 轮；颜色、输出节点和初始知识都是归约的一部分。

参考资料

[1] Alexander A. Razborov, “On the Distributional Complexity of Disjointness”, Theoretical Computer Science 106(2), 385–390, 1992，DOI: 10.1016/0304-3975(92)90260-M。本文使用其矩形腐败论证的常见等价标准化。

[2] Bala Kalyanasundaram and Georg Schnitger, “The Probabilistic Communication Complexity of Set Intersection”, SIAM Journal on Discrete Mathematics 5(4), 545–557, 1992。

[3] Princeton COS 598D, Communication Complexity, Lecture 6: Razborov's Lemma, 2008。课程讲义，介绍随机分割、条件密度与核心引理的证明。本文统一以交点数标记 $\mu_0,\mu_1$ ，并重新展开概率权重与最终求和。

[4] Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997，随机通信、矩形下界与归约方法。

形式陈述 ​

任务与结论的口径 ​

核心矩形引理：几乎全对的大矩形有多大 ​

固定随机数后，短协议为什么产生矩形 ​

困难分布：不相交与恰好相交一次 ​

从引理到通信下界：把常数与错误全部算清 ​

核心引理为什么与矩形结构有关 ​

这条证明排除了什么，又没有声称什么 ​

一个具体应用：单遍精确去重需要线性空间 ​

反向链接