互异的排列点积

《European Journal of Combinatorics》：Distinct permutation dot products

　　

摘要

我们证明：对于任意两个实数集合 A={a1,…,an} 和 B={b1,…,bn}，当我们在所有置换 π∈Sn 上取遍时，形如 ∑i=1n aibiπ(i) 的和总取到 Ω(n3) 个不同的值。

一个重要的工具是 Littlewood–Offord 理论中 Halász 反集中定理的一个"支撑型"版本，它本身可能具有独立兴趣。

1. 引言

设 A={a1,…,an}?R 和 B={b1,…,bn}?R 为 n 个不同实数的集合。对 π∈Sn 定义置换点积

S(π)?∑i=1n aibπ(i)，Σ(A,B)?{S(π):π∈Sn}。

等价地，写作 a=(a1,…,an)∈Rn 和 b=(b1,…,bn)∈Rn，则 S(π)=〈a,bπ〉，其中 bπ=(bπ(1),…,bπ(n))∈Rn，所以 Σ(A,B) 就是固定线性泛函在 b 的置换轨道上取到的值集合。几何上，|Σ(A,B)| 也可以理解为：为覆盖多面体 conv{bπ:π∈Sn}（即置换多面体）的顶点所需的、法向量为 (a1,…,an) 的（互相平行的）超平面数目。

在本文中，我们确定 |Σ(A,B)| 的最小值，其中 A,B 遍历所有 n 个不同实数的集合。

定理 1.1 设 A,B?R 为 n 个不同实数的集合。则 |Σ(A,B)|≥cn3，其中 c>0 为绝对常数。

不难看出，定理 1.1 在常数 c 的精确取值之外是最优的。事实上，若 A=B={1,2,…,n}，则对任意置换 π∈Sn，

n(n+1)(n+2)/6=∑i=1n i(n+1?i)≤S(π)=∑i=1n iπ(i)≤∑i=1n i2=n(n+1)(2n+1)/6。

这可由重排不等式得到（参见 [6]）。因此 |Σ([n],[n])| 的量级为 n3。

从某种意义说，定理 1.1 与一个新的 Erd?s–Moser 型置换定理相关，后者最近出现在关于置换反集中模型的两篇独立工作中：作者与 Hunter 和 Zhu 的工作 [7]，以及 Do、Nguyen、Phan、Tran 和 Vu 的工作 [3]。该结果表述如下：

定理 1.2 (HPZ、DNPTV) 对所有元素两两不同、大小为 n 的集合 A,B?R，以及 Sn 上均匀随机的置换 π，有

supx∈R P(S(π)=x)≤n?5/2+o(1)。

一个平凡的观察是 |Σ(A,B)|≥1/supx∈R P(S(π)=x)，因此定理 1.2 立即蕴含 |Σ(A,B)|≥n5/2?o(1)。然而，定理 1.2 本身也是紧的（在次多项式因子之外），因为存在 A=B=[n] 的情形。因此，定理 1.1 的意义在于把这一初步估计改进为正确的立方量级。

从整体上说，定理 1.1 的证明在精神上与 [7] 中定理 1.2 的证明相似，但局部细节完全不同（有时甚至更为简洁）。

证明概要

基本思想如下。固定一个基准置换 π0，并注意到将 π0 与一个不相交的换位 (ij) 复合会使 S(π) 改变一个矩形面积 (ai?aj)(bπ0(j)?bπ0(i))∈(A?A)(B?B)。

选取许多不相交的换位会产生 Σ(A,B) 中某个子集和集合 Σ(D) 的一个（平移），其中 D?(A?A)(B?B) 是"交换增量"集合。

为使 Σ(D) 尽可能大，我们先发展一个来自 Littlewood–Offord 理论的 Halász 不等式的"支撑版本"，用以通过加法能量 E2(D) 给出 |Σ(D)| 的下界（第 2 节）。或许值得指出：Halász 定理本身在技术上也能给出以 E2(D) 表达 |Σ(D)| 的下界，但该估计同样不够好，原因与定理 1.2 无法直接推出定理 1.1 的原因完全一致。最后，我们证明：可以从池子 (A?A)(B?B) 中选取 m?n/log n 个不相交的交换增量，使得能量 E2(D)?m2。这一选取用到 Roche–Newton 与 Rudnev 的一个定理 [9, Theorem 1']，其又依赖于 Guth 与 Katz 在 [4] 中给出的 R3 中点-线配置定理（另见 [2]，那里有一个仅依赖 Szemerédi–Trotter 定理的较简证明）。把这些拼在一起即可得到略弱的界 |Σ(D)|?m5/E2(D)?m3?n3/(log n)3/2。我们将在第 3 节（不相交换位把子集和嵌入）与第 4 节（一个有损失的估计）中首先讨论此论证。

该初步估计中的对数损失来源于：单换位增量集合 (A?A)(B?B) 最多小至 n2/(log n)δ0+o(1)，其中 δ0=0.86071… 为 Erd?s–Tenenbaum–Ford 常数（例如 A=B=[n] 时即如此）。为完成定理 1.1 的证明，我们通过改用一对不相交换位的乘积作为"交换增量"来绕过这一障碍。由此得到的增量是两个矩形面积之和，因而落在集合 (A?A)(B?B)+(A?A)(B?B) 中。

要点在于：这个扩张恰好是二次大的，且没有对数损失。之后的论证与上述策略类似：我们从池子 (A?A)(B?B)+(A?A)(B?B) 中提取一个略大的集合 D，其中含 m?n（而不是 n/log n）个不相交的交换增量，且加法能量 E2(D)?m2。然后我们的支撑型 Halász 定理将其转化为下界 |Σ(D)|?m5/E2(D)?m3?n3，正是所需结果。我们将在第 5 节中讨论这些内容。

最后但同样重要的是，我们指出：为证明 |(A?A)(B?B)+(A?A)(B?B)|?|A||B|，我们不再需要 Guth–Katz 定理或 Szemerédi–Trotter 定理。证明将完全初等，但某种程度上受到 Solymosi 著名的"扇形论证"[10] 的启发。

记号

我们用 [N] 表示集合 {1,…,N}。f?g 表示存在常数 C 使得 f≤Cg，其中常数 C 可能依赖 ? 下标。f?g 表示 f?g 且 f?g，下标处理方式相同。

2. 一个支撑型 Halász 定理

对有限集合 D?R，形式地定义其子集和集合 Σ(D)?{∑x∈S x:S?D}。

对整数 k≥1，定义第 k 阶加法能量 Ek(D)?#{(a1,…,ak,b1,…,bk)∈D2k:a1+?+ak=b1+?+bk}。

这是一个在加性组合中几乎处处出现的基本参数，参见例如 [11]。我们现在可以陈述本节的主定理。

定理 2.1 设 D?R 为有限集且 |D|=m，令 k≥1 固定。则

|Σ(D)|?k m2k+1/Ek(D)。

定理 2.1 既恢复又改进了子集和集合的初等二次下界。取 k=1 并利用 E1(D)=m，可得 |Σ(D)|?m2。对等差数列这是紧的：若 D=[m]，则 Σ(D)={0,1,…,m(m+1)/2}。更一般地，对每个固定的 k 都有 Ek([m])?km2k?1，故定理 2.1 右端在此高能量情形下仍为 m2 量级。因此，关于加法能量的依赖（至多重在一个依赖 k 的常数上）是紧的。

在另一端，低能量情形，若 D 为 Sidon 集，则 E2(D)?m2，由定理 2.1 在 k=2 时得 |Σ(D)|?m3。这也是紧的，因为存在大小 m?n1/2、位于 [n] 中的 Sidon 集 D：事实上若 D?[n]，则 Σ(D)?[|D|n]，而 |D|n?m3。这一关于 Sidon 集子集和的特别估计由 Balogh–Lavrov–Shakan–Wagner [1] 得到。从这个意义上说，定理 2.1 在一般二次界与 Sidon 型加性结构下的三次界之间起到了插值作用。

定理 2.1 应与 Halász 定理相应的点质量版本 [5] 作比较，后者仅给出 |Σ(D)| 的多项式有损失下界。更多细节参见例如 [8, Corollary 6.3] 及其所引文献。

定理 2.1 的证明

设 m=|D|。当 m≤2 时，调整隐含常数后结果显然，故设 m≥3。至少 ?m/2? 个 D 的元素具有相同的"弱符号"；必要时用 ?D 替换 D，可假设至少 ?m/2? 个元素非负。丢弃零（若出现），得到 D 的正元素子集 P?D，满足 |P|=M≥?m/2??1≥m/3。

由于 Σ(P)?Σ(D) 且 Ek(P)≤Ek(D)，只需证明 |Σ(P)|?k M2k+1/Ek(D)。

写 P={p10。对 t≥0 定义

Lt?pM?kt+1+pM?kt+2+?+pM，L0?0，

以及剩余前缀 Pt?{p1,…,pM?kt}。

设 k∧Pt 为 Pt 中 k 个不同元素之和的集合：

k∧Pt?{x1+?+xk:x1,…,xk∈Pt 互不相同}。

定义"块" St?Lt+k∧Pt?Σ(P)。

证明的主要思想在某种意义上可由以下简单观察给出。

引理 2.2 对 t=0,1,…,M/k?1，集合 St 两两不相交。

证明 k∧Pt 的最大元素为 Pt 中 k 个最大元素之和，即 pM?kt+?+pM?kt?k+1。因此

max(St)=Lt+pM?kt+?+pM?kt?k+1=Lt+1。

St+1 中每个元素等于 Lt+1 加上 k 个正元素之和，故严格大于 Lt+1=max(St)。这表明 max(St)0 足够小，使得任何满足 |At|,|Bt|≥n/2 的子网格 At×Bt 都满足 |(At?At)(Bt?Bt)|≥R。

在此阶段，δt 表示一个抽样的矩形面积值，此时尚未相对于基准置换定义。抽样完成后，我们将选择 π0，使这些值恰为引理 3.2 中的增量。

算法

初始化 A0?A，B0?B。对 t=1,2,…,m 依次执行如下步骤：

(1) 令 Pt?1?At?1×Bt?1，并从 Pt?1 的矩形面积集合中任选一个不含 0 的子集 Ut?1?R(Pt?1)?{0}，满足 |Ut?1|=R。

(2) 从 Ut?1?{δ1,…,δt?1} 中均匀随机选取 δt。

(3) 选一对点 p=(ajt,bpt),q=(ait,bqt)∈Pt?1，使得

δt=R(p,q)=(ait?ajt)(bqt?bpt)。

(4) 从 At?1 与 Bt?1 中删去已用元素：

At?At?1?{ait,ajt}，Bt?Bt?1?{bpt,bqt}。

(5) 重复。

经过 m 步后，下标对 (it,jt) 互不相交，点 (pt,qt) 互不相交，且 D?{δ1,…,δm} 大小为 m。此外，由于 m=o(n)，此过程不会过早终止。我们还始终维持 |At|,|Bt|≥n/2 的性质，故由 R 的定义，总能找到满足 |Ut?1|=R 的 Ut?R(Pt?1)?{0}。

引理 4.2 对上述构造的 D，有

E[E2(D)]?m2+m4/R。

特别地，若 m=cR 且 c 足够小，则 m4/R?c2m2，故 E[E2(D)]?m2，由 Markov 不等式可得 E2(D)?m2 的实现。由 (3) 知 m 的量级为 n/log n。

证明 写 E2(D)=Ttriv+Tnontriv，其中 Ttriv 统计满足 x1+x2=x3+x4 且 (x1,x2,x3,x4)=(x,y,x,y) 或 (x,y,y,x) 的解的个数。

然后 $T_{\text{triv}} \leq 2m^2$。现在固定一个有序指标四元组 $(\alpha, \beta, \gamma, \delta) \in [m]^4$，它不属于上述两种平凡模式。令 $t^* := \max\{\alpha, \beta, \gamma, \delta\}$。以时刻 $t^*-1$ 为止的历史为条件，所有 $t < t^*$ 的 $\delta_t$ 均已确定，而 $\delta_{t^*}$ 在一个大小 $\geq R/2$ 的集合上均匀分布（因为 $t^* \leq m \ll R$ 且我们排除了之前选过的值）。等式 $\delta_\alpha + \delta_\beta = \delta_\gamma + \delta_\delta$ 迫使 $\delta_{t^*}$ 至多等于某一个指定值，因此
$$\mathbb{P}\left(\delta_\alpha + \delta_\beta = \delta_\gamma + \delta_\delta \mid \text{到 } t^*-1 \text{ 为止的历史}\right) \ll \frac{1}{R}.$$
对 $O(m^4)$ 个非平凡指标四元组求和，得 $E\, T_{\text{nontriv}} \ll m^4/R$。因此 $E\, E_2(D) \ll m^2 + m^4/R$。$\square$

**定理 1.1 的有损版本**

设 $D = \{\delta_1, \ldots, \delta_m\}$ 为上述构造的一个确定性结果，由引理 4.2 保证 $E_2(D) \ll m^2$。回顾 $m \asymp n/\log n$。

我们现在将这些增量实现为某个基置换 $\pi_0$ 的不相交对换增量。定义 $\pi_0 \in S_n$ 使得 $\pi_0(i_t) = p_t$，$\pi_0(j_t) = q_t$（$t = 1, \ldots, m$），在剩余指标上任意延拓。则
$$(a_{i_t} - a_{j_t})(b_{\pi_0(j_t)} - b_{\pi_0(i_t)}) = (a_{i_t} - a_{j_t})(b_{q_t} - b_{p_t}) = \delta_t,$$
由引理 3.2 得 $|\Sigma(A,B)| \geq |\Sigma(D)|$。

应用定理 2.1（取 $k=2$）：
$$|\Sigma(D)| \gg \frac{m^5}{E_2(D)} \gg m^3 \asymp \frac{n^3}{(\log n)^{3/2}}.$$
综合以上结果，我们得到 $|\Sigma(A,B)| \gg n^3/(\log n)^{3/2}$。$\square$

## 5. 定理 1.1 的证明：去除对数损失

如第 1 节已提及的，第 4 节论证中的对数损失源于单次对换增量集 $(A-A)(B-B)$ 可以小到 $n^2/(\log n)^{\delta_0 + o(1)}$，其中 $\delta_0 = 0.86071\ldots$ 为 Erd?s–Tenenbaum–Ford 常数。绕过此障碍的一个简单方法是使用两个不相交对换的乘积作为单个"立方体方向"。所得增量是两个矩形面积之和，因此属于双面积集 $(A-A)(B-B) + (A-A)(B-B)$。

关键要点在于，这个扩张集的大小是二次的，且没有对数损失。我们将此重要的初步观察记录为一个引理。

**引理 5.1** 设 $A, B \subset \mathbb{R}$ 为有限集，$|A|, |B| \geq 2$。则
$$|(A-A)(B-B) + (A-A)(B-B)| \geq |A|\,|B|^2.$$

我们注意到引理 5.1 在主导常数意义下是最优的。事实上，不难看出当 $A = B = [n]$ 时，$(A-A)(B-B) + (A-A)(B-B) \subset [-2(n-1)^2, 2(n-1)^2]$。

**证明** 写 $A = \{a_1 < a_2 < \cdots < a_n\}$，$B = \{b_1 < b_2 < \cdots < b_m\}$，令 $\delta := \min_i (a_{i+1} - a_i)$ 和 $M := b_m - b_1$。直观地，$\delta$ 表示 $A$ 中最小的间隙，$M$ 为集 $B$ 的直径。特别地，$\delta \in A - A$，$M \in B - B$。此外，令 $P := \{b_i - b_1 : 1 \leq i \leq m\} \subseteq B - B$，$P' := \{a_{2j-1} - a_1 : 1 \leq j \leq \lceil n/2 \rceil\} \subseteq A - A$。我们有 $|P| = m$，$|P'| = \lceil n/2 \rceil$。此外 $P \subset [0, M]$，且 $P'$ 中任意两个不同元素之差至少为 $2\delta$。

我们现在考虑 $(A-A)(B-B) + (A-A)(B-B)$ 的如下特殊子集：
$$T := \delta P + M P' = \{\delta x + My : x \in P, y \in P'\}.$$

由于 $\delta \in A - A$ 且 $P \subseteq B - B$，有 $\delta P \subseteq (A-A)(B-B)$；类似地 $M P' \subseteq (A-A)(B-B)$。因此确实有 $T \subseteq (A-A)(B-B) + (A-A)(B-B)$。

关键思想在于映射 $P \times P' \to T$，$(x, y) \mapsto \delta x + My$ 是单射。事实上，若 $\delta x_1 + M y_1 = \delta x_2 + M y_2$，则 $M(y_1 - y_2) = \delta(x_2 - x_1)$。若 $y_1 \neq y_2$，则 $|y_1 - y_2| \geq 2\delta$，故 $|M(y_1 - y_2)| \geq 2\delta M$，而 $x_1, x_2 \in P \subseteq [0, M]$ 给出 $|\delta(x_2 - x_1)| \leq \delta M$，矛盾。因此 $y_1 = y_2$，从而 $x_1 = x_2$。

由此得
$$|(A-A)(B-B) + (A-A)(B-B)| \geq |T| \geq |P| \cdot |P'| = m \cdot \lceil n/2 \rceil \geq mn^2/2. \quad \square$$

有了引理 5.1，从此刻起的计划将简单地是将第 4 节中完全相同的证明策略加以执行，只是将 $(A-A)(B-B)$ 替换为 $(A-A)(B-B) + (A-A)(B-B)$。

我们需要处理的第一个技术难点是：在之前的配对对换论证中，我们所需要的略多于 $|(A-A)(B-B)|$ 的大小作为输入。类似地，这里我们同样需要每个增量 $\delta_t$ 来自单个交换生成元 $\sigma_t = (i_t j_t)(k_t \ell_t)$，即 $\delta_t$ 必须具有如下表示：
$$\delta_t = (a_i - a_j)(b_p - b_q) + (a_k - a_\ell)(b_r - b_s),$$
其中 $A$-指标 $\{i, j, k, \ell\}$ 互不相同，$B$-指标 $\{p, q, r, s\}$ 互不相同（使得两个基础对换是不相交的）。

下面的引理提供了引理 5.1 的这一技术性细化。

**引理 5.2** 设 $A, B \subset \mathbb{R}$ 为有限集，$|A| = n \geq 4$，$|B| = m \geq 4$。则存在一个集合 $U(A,B) \subseteq (A-A)(B-B) + (A-A)(B-B)$，满足
$$|U(A,B)| \geq (m-3)\left(\lceil n/2 \rceil - 2\right) \geq nm/8,$$
且 $U(A,B)$ 中每个元素 $u$ 都可通过表示
$$u = (a_i - a_j)(b_p - b_q) + (a_k - a_\ell)(b_r - b_s)$$
实现，其中 $i, j, k, \ell$ 互不相同，$p, q, r, s$ 互不相同。

**证明** 证明几乎与引理 5.1 相同（仅有一些额外的簿记工作），但为方便读者我们给出完整证明。

如引理 5.1 的证明中一样，写 $A = \{a_1 < \cdots < a_n\}$，$B = \{b_1 < \cdots < b_m\}$，定义 $\delta := \min_{1 \leq t \leq n-1}(a_{t+1} - a_t) > 0$，$M := b_m - b_1 > 0$。

设 $P := \{b_i - b_2 : 3 \leq i \leq m-1\} \subseteq B - B$，则 $|P| = m - 3$，且 $P$ 中每个元素 $x$ 通过 $b_i - b_2$（$3 \leq i \leq m-1$）表示，所用指标在 $\{2, 3, \ldots, m-1\}$ 中，故与 $\{1, m\}$ 不相交。

选取指标 $s \in [n-1]$ 使得 $a_{s+1} - a_s = \delta$，再取一个锚点 $a_\star \in A \setminus \{a_s, a_{s+1}\}$。具体地，若 $a_1 \notin \{a_s, a_{s+1}\}$ 则取 $a_\star = a_1$，否则取 $a_\star = a_n$。设 $I$ 为奇数指标 $2j-1$（$1 \leq j \leq \lceil n/2 \rceil$）的集合，从 $I$ 中删除对应于元素 $\{a_s, a_{s+1}\}$ 的指标以及锚点指标本身。定义 $P' := \{a_t - a_\star : t \in I\} \subseteq A - A$。

奇数指标集共有 $\lceil n/2 \rceil$ 个元素。由于 $s$ 和 $s+1$ 奇偶性相反，删除对应于 $a_s$ 和 $a_{s+1}$ 的指标至多移除其中一个；删除锚点指标至多再移除一个。故 $|P'| \geq \lceil n/2 \rceil - 2$。此外 $P'$ 中任意两个不同元素之差至少为 $2\delta$。

如引理 5.1 的证明一样，考虑
$$U := \delta P + M P' = \{\delta x + My : x \in P, y \in P'\} \subset (A-A)(B-B) + (A-A)(B-B).$$

映射 $(x, y) \mapsto \delta x + My$ 在 $P \times P'$ 上仍是单射，因此
$$|U| \geq |P| \cdot |P'| \geq (m-3)\left(\lceil n/2 \rceil - 2\right).$$

最重要的是，注意 $U$ 中每个 $u = \delta x + My$ 都可以通过不相交指标来实现：写 $x = b_i - b_2$（$3 \leq i \leq m-1$），写 $y = a_t - a_\star$（其中 $a_t \notin \{a_s, a_{s+1}\}$ 且 $a_\star \notin \{a_s, a_{s+1}\}$）。则
$$u = (a_{s+1} - a_s)(b_i - b_2) + (a_t - a_\star)(b_m - b_1),$$
其中 $A$-指标 $\{s, s+1, t, \star\}$ 由构造互不相同，而 $B$-指标 $\{i, 2, m, 1\}$ 也互不相同。取 $U(A,B) := U$ 即完成证明。$\square$

**配对对换给出立方体和子集和**

下面这个引理是引理 3.2 在每个生成元为两个不相交对换的乘积时的类比。要点在于配对对换仍然在 $\Sigma(A,B)$ 内部给出了 $\Sigma(D)$ 的一个平移。

**引理 5.3** 固定一个基置换 $\pi_0 \in S_n$。设
$$\sigma_t := (i_t j_t)(k_t \ell_t), \quad t = 1, \ldots, m,$$
为置换，其中所有指标 $i_t, j_t, k_t, \ell_t$ 跨所有 $t$ 互不相同（故支集两两不相交，$\sigma_t$ 彼此交换）。定义
$$\delta_t := (a_{i_t} - a_{j_t})(b_{\pi_0(j_t)} - b_{\pi_0(i_t)}) + (a_{k_t} - a_{\ell_t})(b_{\pi_0(\ell_t)} - b_{\pi_0(k_t)}), \quad D := \{\delta_1, \ldots, \delta_m\}.$$

对每个 $I \subseteq [m]$，令 $\pi_I = \pi_0 \circ \prod_{t \in I} \sigma_t$。则
$$S(\pi_I) = S(\pi_0) + \sum_{t \in I} \delta_t.$$

特别地，$\Sigma(A,B)$ 包含 $\Sigma(D)$ 的一个平移，因此 $|\Sigma(A,B)| \geq |\Sigma(D)|$。

**证明** 由于支集不相交，$\sigma_t$ 彼此交换，且乘积 $\prod_{t \in I} \sigma_t$ 良定义。此外，切换 $\sigma_t$ 仅影响四个位置 $\{i_t, j_t, k_t, \ell_t\}$，且它是两个不相交交换 $(i_t j_t)$ 和 $(k_t \ell_t)$ 的复合。对每个交换应用引理 3.1 并将两个增量相加，得 $S(\pi_0 \circ \sigma_t) - S(\pi_0) = \delta_t$。

由于支集不相交，当同时施加多个 $\sigma_t$ 时这些增量可加，从而得到 $S(\pi_I)$ 的所述公式。平移包含关系随之立得。$\square$

我们现在终于准备好完成定理 1.1 的证明。

**定理 1.1 的证明** 粗略地说，我们要通过结合引理 5.2、引理 5.3 以及辅助性的 Halász 定理 2.1 来完成论证。

设 $m := \lfloor n/32 \rfloor$。我们迭代地构造不相交配对对换及其增量 $\delta_1, \ldots, \delta_m$。初始化 $A_0 := A$，$B_0 := B$。对 $t = 1, \ldots, m$ 执行以下步骤。由于 $4m \leq n/8$，有 $|A_{t-1}|, |B_{t-1}| \geq n - 4(t-1) \geq 7n/8 \geq 4$。对 $(A_{t-1}, B_{t-1})$ 应用引理 5.2，得到集合
$$U_{t-1} := U(A_{t-1}, B_{t-1}) \subseteq (A_{t-1} - A_{t-1})(B_{t-1} - B_{t-1}) + (A_{t-1} - A_{t-1})(B_{t-1} - B_{t-1}),$$
满足 $|U_{t-1}| \geq |A_{t-1}|\,|B_{t-1}|/8 \geq n^2/16$。

从 $U_{t-1} \setminus \{\delta_1, \ldots, \delta_{t-1}\}$ 中均匀随机选取 $\delta_t$，并固定其一个不相交表示
$$\delta_t = (a_{i_t} - a_{j_t})(b_{p_t} - b_{q_t}) + (a_{k_t} - a_{\ell_t})(b_{r_t} - b_{s_t}),$$
其中 $i_t, j_t, k_t, \ell_t$ 互不相同且 $p_t, q_t, r_t, s_t$ 互不相同（由引理保证）。删除已用元素：
$$A_t := A_{t-1} \setminus \{a_{i_t}, a_{j_t}, a_{k_t}, a_{\ell_t}\}, \quad B_t := B_{t-1} \setminus \{b_{p_t}, b_{q_t}, b_{r_t}, b_{s_t}\}.$$

经过 $m$ 步后，所使用的 $4m$ 个行指标和 $4m$ 个列指标两两不同。最后令
$$D := \{\delta_1, \ldots, \delta_m\} \subset (A-A)(B-B) + (A-A)(B-B).$$

引理 4.2 的证明可以原封不动地套用（将其中的池大小 $R$ 替换为这里的 $|U_{t-1}| \geq n^2/16$），得到
$$E\,E_2(D) \ll m^2 + \frac{m^4}{n^2}.$$

取 $m = \lfloor n/32 \rfloor$ 时，$m^4/n^2 \ll m^2$，因此 $E\,E_2(D) \ll m^2$，从而存在一个结果满足 $E_2(D) \ll m^2$。

对于这样一个结果，定义基置换 $\pi_0 \in S_n$：规定
$$\pi_0(i_t) = q_t, \quad \pi_0(j_t) = p_t, \quad \pi_0(k_t) = s_t, \quad \pi_0(\ell_t) = r_t \quad (t = 1, \ldots, m),$$
并在剩余指标上任意延拓。则
$$(a_{i_t} - a_{j_t})(b_{\pi_0(j_t)} - b_{\pi_0(i_t)}) = (a_{i_t} - a_{j_t})(b_{p_t} - b_{q_t}),$$
$(k_t, \ell_t)$ 对类似地有相同结论，因此由引理 5.3 得
$$|\Sigma(A,B)| \geq |\Sigma(D)|.$$

最后，我们像之前一样对 $D$ 应用定理 2.1：
$$|\Sigma(D)| \gg \frac{m^5}{E_2(D)} \gg m^3 \gg n^3,$$
这完成了证明。$\square$

## 6. 结语

置换点积问题允许如下自然的矩阵推广。给定 $M = (m_{ij}) \in \mathbb{R}^{n \times n}$，定义
$$S_M(\pi) := \sum_{i=1}^n m_{i,\pi(i)}, \quad \Sigma(M) := \{S_M(\pi) : \pi \in S_n\}.$$
等价地，记 $P_\pi$ 为 $\pi$ 的置换矩阵，$\langle \cdot, \cdot \rangle_F$ 为 Frobenius 内积，则
$$S_M(\pi) = \langle M, P_\pi \rangle_F,$$
因此 $\Sigma(M)$ 是线性泛函 $X \mapsto \langle M, X \rangle_F$ 在 Birkhoff 多面体 $B_n = \mathrm{conv}\{P_\pi : \pi \in S_n\}$ 的顶点集上所取值的集合。

与排列多面体一样，Birkhoff 多面体 $B_n$ 也包含许多内嵌超立方体：如果固定一个基顶点 $P_{\pi_0}$ 和一组两两不相交的对换，则切换这些对换的任意子集产生 $2^m$ 个顶点，构成一个 $m$ 维立方体面的顶点集。在这样的映射 $X \mapsto \langle M, X \rangle_F$ 下对该立方体投影，便得到子集和集的一个平移，然后或许我们辅助性的 Halász 定理 2.1 可以再次被用来通过立方体方向上的增量集对 $\Sigma(M)$ 给出下界。

然而，与秩一情形 $m_{ij} = a_i b_j$ 不同，在对 $M$ 没有额外假设的情况下，$|\Sigma(M)|$ 的非平凡下界是不可能的。例如，固定两个向量 $u, v \in \mathbb{R}^n$，令 $m_{ij} = u_i + v_j$ 对所有 $1 \leq i, j \leq n$ 成立。则对每个 $\pi \in S_n$，
$$S_M(\pi) = \sum_{i=1}^n (u_i + v_{\pi(i)}) = \sum_{i=1}^n u_i + \sum_{j=1}^n v_j$$
与 $\pi$ 无关，因此 $|\Sigma(M)| = 1$。于是，找出 $M$ 迫使 $|\Sigma(M)|$ 呈现增长的自然几何条件将是有趣的，特别是以"正确"的方式将定理 1.1 推广到此设定中。

Cosmin Pohoata
Emory University, Atlanta, Georgia