轮消除引理

Alice 的首消息在看到全部 $m$ 个块后产生，却不知道哪个块会被问到。固定公共币后，对独立块用互信息公理库互信息Mutual information用联合分布相对独立边缘乘积的 KL 散度量化统计依赖。链式法则有

Bob 已知目标之前的前缀，平均到一块仍只有 $a/m$ 信息。这说明短首消息对一个未知目标难以很有用。真正把“平均信息少”变成逐输入错误的协议，需要分布限制和极小极大步骤；不能只选一个平均好坐标，就声称对所有输入已得到新协议。

在 Greater-Than 中，Bob 用已知前缀抹去更高位的差异，用全一后缀处理目标块相等的情况。这样一份大整数比较协议可以解决索引块比较。轮消除把这个协议削成一份更短整数的比较协议；如果删光消息后仍有至少一 bit 输入，就与零消息不可能性矛盾。

三块输入的比较，包括相等情形 ​

取 $m=3$、每块两位。Alice 的块为 $01,11,10$，所以 $\hat{x}=011110$。Bob 取 $i=2$，已知第一块为 $01$。

第二行说明为什么后缀要取全一。目标块相等时，Alice 的剩余后缀不可能更大；若 Bob 随意填零，后缀反而可能把假答案变成真答案。

首消息的平均信息，不等于完整消除定理 ​

若 $a=1,m=4256$，上述独立分布下至少存在一个位置 $i$，满足

固定所选位置后，将条件互信息写成条件KL 散度公理库KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。的平均。以 bit 计散度，Pinsker 界为 $\mathrm{TV}(P,Q)\le \sqrt{(\ln 2)D_{\mathrm{KL},2}(P\Vert Q)/2}$；再由Jensen 不等式公理库Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。把平方根移到平均之外，相应平均条件分布的总变差至多

这解释了为何首消息可望被近似替代，但没有独自证明逐输入协议、后续本地状态的正确模拟或固定错误版本。下文明确引用 MNSW 可变错误引理，再核算放大到固定错误的预算。

若 Alice 事先知道 $i$，一 bit 可以全部描述目标块，平均论证失效。若各块完全相关，独立坐标解释也失效。Bob 已知前缀是 $P_m(f)$ 的正式输入条件，不能从引理中悄悄删掉，却继续使用依赖该前缀的嵌入。

为什么每次消除仍保持错误率 $1/3$ ​

MNSW 的可变错误版本（Lemma13）为：取 $0<\eta <1$、$\delta >0$，若

则 $P_m(f)$ 的 $[t,a,b{]}_A$、错误 $\delta$ 协议，产生 $f$ 的 $[t-1,a,b{]}_B$、错误 $\eta$ 协议。[1] 这里将该引理作为已知工具，不把前面的信息直觉当作它的完整证明。

从错误 $1/3$ 开始，使用独立重复与多数表决公理库概率放大Probability amplification · Error reduction独立重复并多数表决可把有界错误概率指数降低。：对每个输入使用独立公共币运行 $99$ 份协议。把同一轮的消息并列发送，条数仍为 $t$，单消息预算变成 $99a,99b$；原固定输出者对 $99$ 个结果多数表决。每个固定输入的重复错误独立同分布，其参数至多 $1/3$，因此多数出错概率由参数 $1/3$ 的二项尾概率公理库二项分布Binomial distribution固定次数独立同概率 Bernoulli 试验中成功总数的离散分布。上界：

这是 $\eta =1/3$ 所要求的 $\delta$ 界。并且对每个整数 $a\ge 1$，

因为 $60(99\ln 2+\ln 5)<4214<4256$，且常数项可由 $a$ 倍吸收。于是可变错误引理适用于 $m=Ra$，输出错误重新为 $1/3$。每次迭代先做这个放大，再消除，故错误预算不是不断累加成 $t/3$。

所查作者稿 Lemma14 的显示公式漏写了消息数中的“$-1$”；其引言、Lemma13和“跳过首消息”的证明均给出 $t-1$。本文采用这一与证明一致的形式。[1]

Greater-Than 的自归约与角色恢复 ​

设 $m\ell \le L$。从 $P_m({\mathrm{GT}}_{\ell })$ 构造大比较输入：

Bob 能构造自己的输入，因为他确实知道全部前缀块。两串更高位完全相同：若 $x_i\ne y$，首次差异就在目标块，决定整串大小；若 $x_i=y$，Alice 的后缀至多为全一，故整串严格大于为假。因此

若 $m\ell <L$，再给两串末尾都补 $L-m\ell$ 个零，相当于同乘一个二的幂，比较结果不变。这不是先发送前缀：所有补齐在本地完成，额外通信为零。

消除后 Bob 先说。为再次使用 Alice 先说的同一版本，在长度为 $\ell$ 的新实例 $(x,y)$ 上，令旧 Alice 持有 $\bar{y}$，旧 Bob 持有 $\bar{x}$；交换执行角色。因为逐位取反对应整数 $z\mapsto 2^{\ell }-1-z$，有

旧 Bob 现在是新 Alice，所以新协议恢复 Alice 先说。等号仍映成等号，无需取反输出。输出者随角色映射，仍是预先指定的一方；两方每条消息都用同一上限时，交换不会改变预算。

把所有参数迭代到底 ​

先设原协议 Alice 先说；若原来 Bob 先说，先做上述角色变换即可。设 $L_0=L$。第 $j$ 步开始时维持：

对 $j<t$，取整数

只要 $L_{j+1}\ge 1$，先把 $P_{m_j}({\mathrm{GT}}_{L_{j+1}})$ 嵌入 ${\mathrm{GT}}_{L_j}$，再应用固定错误引理，最后恢复角色，就得到表中下一行。每一步都同步更新消息数、位长、消息预算和先手。

对正整数分母，$\lfloor \lfloor x/a\rfloor /b\rfloor =\lfloor x/(ab)\rfloor$。归纳得到

假设 $L\ge (Rc{)}^t{C}^{t(t-1)/2}$，则所有中间位长都至少为一，整个迭代合法，最终得到非平凡 GT 的零消息协议。

若由 Bob 输出，固定 $y=0$，比较 $x=0$ 与 $x=1$。他的本地输入和公共币分布完全一样，但正确答案相反，不可能在两个输入上均以至少 $2/3$ 的概率正确。若由 Alice 输出，固定 $x=1$，比较 $y=0$ 与 $y=1$，同理矛盾。因此必须有

例如 $t=2$ 时，消除链是

预算从 $c$ 变成 $Cc$，再变成 $C^{2}c$；若 $L\ge R^{2}C{c}^2$，最后一位仍存在。最坏总通信 $K$ 必然上界每一条消息，所以代入 $c=K\ge 1$ 也得到同一形式的总通信下界。它没有额外的 $t$ 倍因子，因为原假设只给单消息上限，没有要求每条都达到上限。

与其他通信工具的连接 ​

轮数—通信量权衡公理库轮数—通信量权衡Round-communication tradeoff · Round-sensitive communication complexity固定消息条数、首发者、单消息预算与错误后，刻画增加交互如何降低完成同一通信任务的总 bit 数。保留一个16位、两消息、最坏14 bit的实际比较轨迹，展示多轮如何定位首次不同块；本页则给固定消息数的完整下界链。指针追逐公理库指针追逐通信问题Pointer chasing communication problem · Pointer jumping problem双方交替持有二部图两侧的指针函数，追踪固定起点的第 k 个顶点以显露起始方与轮数的价值。也对消息方向敏感，但其规模更新和专门下界需另行证明，不能把 GT 的嵌入直接挪过去。

轮消除也可用于数据结构：查询端发送地址、存储端返回内容，一次 cell probe 对应两条消息。转移时仍需分别保留两方长度与先手。交互协议压缩公理库交互协议压缩Interactive protocol compression · Interactive compression利用 transcript 的内部信息成本模拟交互协议，并区分单次期望通信、轮数损失与多副本摊销极限。允许以额外交互换通信量，而此处明确限制消息条数；平均低信息直觉不会自动给出同轮数、同最坏长度的任意协议压缩。