加性能量 | Codeboy's Blog

形式陈述

设 $G$ 是用加法记号书写的阿贝尔群， $A,B\subseteq G$ 是非空有限集。和集是 $A+B=\{a+b:a\in A,b\in B\}$ ，两集合的加性能量定义为

E(A,B)=\#\{(a,b,a',b')\in A\times B\times A\times B:a+b=a'+b'\}.

这里计数的是有序四元组；自能量记为 $E(A)=E(A,A)$ 。令

r_{A+B}(s)=\#\{(a,b)\in A\times B:a+b=s\},

则有三个基本关系：

\sum_{s\in G}r_{A+B}(s)=|A||B|,\qquad E(A,B)=\sum_{s\in G}r_{A+B}(s)^2,

\frac{|A|^2|B|^2}{|A+B|} \le E(A,B) \le \min\{|A|^2|B|,\ |A||B|^2\}.

前两个等式来自按和分组：每个有序对恰好落入一个组；和为 $s$ 的组内，从 $r_{A+B}(s)$ 个有序对中独立选两次，恰有 $r_{A+B}(s)^2$ 个碰撞。对这些组求和，就数遍定义中的四元组。

下界是在非零支撑 $A+B$ 上使用Cauchy–Schwarz 不等式：

(|A||B|)^2 =\left(\sum_{s\in A+B}r_{A+B}(s)\cdot1\right)^2 \le |A+B|\sum_{s\in A+B}r_{A+B}(s)^2.

等号当且仅当所有非零的 $r_{A+B}(s)$ 相同，即每个可达的和都有一样多的表示。上界则利用群中的消去律：固定 $(a,a',b)$ 后， $b'=a+b-a'$ 唯一确定，最多得到 $|A|^2|B|$ 个合法四元组；固定 $(a,b,b')$ 同理给出另一个上界。

这些计数结论只要求集合有限，环境群可以无限。后面的 Fourier 表示另要求 $G$ 有限。

直觉

和集大小回答“能得到多少种和”，能量回答“不同输入会多频繁地得到同一个和”。例如一个和有 $10$ 种表示，它给能量贡献 $100$ ；把这 $10$ 种表示分散到十个不同的和，每个只贡献 $1$ ，合计便只有 $10$ 。平方把表示次数的集中放大了。

更精确地，独立、均匀地抽取 $a,a'\in A$ 和 $b,b'\in B$ ，则

\Pr(a+b=a'+b')=\frac{E(A,B)}{|A|^2|B|^2}.

这里的独立抽样允许重复抽到同一元素；它与有序四元组的计数完全一致。因此归一化能量就是两次加法输出的碰撞概率。若和的分布在 $A+B$ 上均匀，碰撞概率为 $1/|A+B|$ ；若分布更集中，概率就更大，这正是前述下界及其等号条件。

把集合写成指示函数 $1_A$ 与 $1_B$ ，分组计数又成为离散卷积：

(1_A*1_B)(s)=\sum_{x\in G}1_A(x)1_B(s-x)=r_{A+B}(s).

所以能量是“表示次数这个信号”的平方和。卷积先把所有相加路径汇总，平方和再测量汇总结果的集中程度。

例子与边界

在同一个群 $G=\mathbb Z/20\mathbb Z$ 中，比较三个各有四个元素的集合。所有加法均按模 $20$ 计算；以下区间与稀疏集的和都小于 $20$ ，没有绕回。

集合	非零表示次数 $r_{A+A}$	$\lvert A+A\rvert$	$E(A)$	碰撞概率 $E(A)/4^4$
子群 $H=\{0,5,10,15\}$	四个和各有 $4$ 次	$4$	$64$	$1/4$
区间 $I=\{0,1,2,3\}$	在 $0,\ldots,6$ 上依次为 $1,2,3,4,3,2,1$	$7$	$44$	$11/64$
稀疏集 $S=\{0,1,4,6\}$	四个和各有 $1$ 次，六个和各有 $2$ 次	$10$	$28$	$7/64$

子群的机制是封闭性：对每个 $s\in H$ 和每个 $a\in H$ ， $s-a$ 都仍在 $H$ ，因此恰有四种表示。它同时达到能量的上下界。区间的机制是重叠：越靠近中间的和，可选的第一项越多，故能量为 $1+4+9+16+9+4+1=44$ 。其表示次数不均匀，所以 Cauchy–Schwarz 下界 $4^4/7$ 严格小于 $44$ 。

稀疏集的四个对角和是 $0,2,8,12$ ，六个不同元素的无序和是 $1,4,6,5,7,10$ ，十个数互不相同。每个对角和只对应 $(a,a)$ ，每个非对角和却对应 $(a,b)$ 与 $(b,a)$ 两个有序对，因此 $E(S)=4\cdot1^2+6\cdot2^2=28$ 。这是一种 Sidon 型现象：无序二元组的和全都不同，能量仍须保留交换次序产生的碰撞。

若大小为 $m$ 的集合具有这种无序和唯一性，同样计数得到 $E(A)=2m^2-m$ 。事实上，这也是任意阿贝尔群中的普遍下界： $(a,b,a,b)$ 与 $(a,b,b,a)$ 各有 $m^2$ 个，只有 $a=b$ 时两类重合，共重合 $m$ 个。等号要求没有额外碰撞，恰好就是允许重复元素的无序二元组具有不同的和。二阶元素会增加碰撞：在 $\mathbb Z/2\mathbb Z$ 中取整个群，两个对角和都为 $0$ ，两个非对角有序对的和都为 $1$ ，故能量为 $2^2+2^2=8$ ，严格高于 $2m^2-m=6$ 。

大能量也未必迫使整个集合有小和集。令 $m\ge2$ ，在

G=(\mathbb Z/m\mathbb Z)\times(\mathbb Z/(m+1)\mathbb Z)

中取两条坐标轴的并

A=\{(x,0):x\in\mathbb Z/m\mathbb Z\} \cup\{(0,y):y\in\mathbb Z/(m+1)\mathbb Z\}.

两轴只在原点相交，故 $|A|=2m$ 。横轴本身已贡献 $m^3$ 个碰撞，所以 $E(A)\ge |A|^3/8$ ；另一方面每个 $(x,y)$ 都是两轴各取一点的和，因此 $A+A=G$ ，并有 $|A+A|/|A|=(m+1)/2$ 。能量可以由集合内的一个子群提供，而整个和集仍随 $m$ 增长到二次规模。

推论与应用

首先，小倍增必然给出大能量：若 $|A+A|\le K|A|$ ，基本下界立即化为

E(A)\ge \frac{|A|^3}{K}.

因此可以用碰撞数量捕捉加法结构；前面的坐标轴例子也说明，反向推断需要更细致地寻找集合中的结构部分。

有限群上，能量还有精确的频域表达。设 $N=|G|$ 。一个特征标是取值于复数单位圆的函数 $\chi:G\to\mathbb C$ ，满足 $\chi(x+y)=\chi(x)\chi(y)$ ；所有特征标在逐点乘法下组成对偶群 $\widehat G$ 。本页固定不归一化的变换与卷积：

\widehat f(\chi)=\sum_{x\in G}f(x)\overline{\chi(x)}, \qquad (f*g)(s)=\sum_{x\in G}f(x)g(s-x).

要从这些定义得到恒等式，需要先说明特征标为何足以描述所有函数。有限阿贝尔群结构定理给出

G\cong\prod_{j=1}^d\mathbb Z/n_j\mathbb Z, \qquad N=\prod_{j=1}^d n_j

（该结构定理见 Dummit–Foote 第 5 章，也见阿贝尔群条目中的有限生成结构）。选定这种坐标后，对每组 $0\le k_j<n_j$ 定义

\chi_k(x)=\exp\left(2\pi i\sum_{j=1}^d\frac{k_jx_j}{n_j}\right).

改变 $x_j$ 的整数代表只会使指数增加 $2\pi i$ 的整数倍，所以定义良好。不同的 $k$ 在某个坐标生成元处取不同值，因此给出 $N$ 个不同的特征标；反过来，任意特征标在第 $j$ 个生成元上的值必须是 $n_j$ 次单位根，且这些值决定它在全群上的值，所以以上列表已经穷尽所有特征标。对偶群的坐标取决于所选分解，无须把 $G$ 与 $\widehat G$ 预先认作同一个集合。

再证明正交性。若 $\eta$ 是非平凡特征标，取 $h$ 使 $\eta(h)\ne1$ ；平移置换全群，故

S:=\sum_x\eta(x)=\sum_x\eta(x+h)=\eta(h)S, \qquad S=0.

把 $\eta$ 取为 $\overline\chi\psi$ ，便有

\sum_{x\in G}\overline{\chi(x)}\psi(x) =\begin{cases}N,&\chi=\psi,\\0,&\chi\ne\psi.\end{cases}

于是 $N$ 个函数 $\chi/\sqrt N$ 在内积 $\langle f,g\rangle=\sum_x\overline{f(x)}g(x)$ 下正交规范。函数空间的维数正是 $N$ ，故它们构成正交规范基，从而给出展开与 Parseval 等式

f(x)=\frac1N\sum_{\chi\in\widehat G}\widehat f(\chi)\chi(x), \qquad \sum_x|f(x)|^2=\frac1N\sum_\chi|\widehat f(\chi)|^2.

卷积的变换则只需有限求和换序。令 $y=s-x$ ，利用特征标的乘法性，得到

\begin{aligned} \widehat{f*g}(\chi) &=\sum_{s,x}f(x)g(s-x)\overline{\chi(s)}\\ &=\sum_{x,y}f(x)g(y)\overline{\chi(x)}\,\overline{\chi(y)} =\widehat f(\chi)\widehat g(\chi). \end{aligned}

最后对 $r_{A+B}=1_A*1_B$ 使用 Parseval，就证明了

\boxed{E(A,B)=\frac1N\sum_{\chi\in\widehat G} |\widehat{1_A}(\chi)|^2|\widehat{1_B}(\chi)|^2}, \qquad \boxed{E(A)=\frac1N\sum_{\chi\in\widehat G}|\widehat{1_A}(\chi)|^4}.

这里的系数 $1/N$ 与前面两个不归一化定义配套。若改用平均值定义 Fourier 系数 $\widetilde f=\widehat f/N$ ，自能量便写成 $N^3\sum_\chi|\widetilde{1_A}(\chi)|^4$ ；这只是同一公式换了尺度。

用前面的子群做一次完整频域核算。在 $\mathbb Z/20\mathbb Z$ 上取 $\chi_k(x)=e^{2\pi ikx/20}$ ，则

\widehat{1_H}(\chi_k)=\sum_{j=0}^3e^{-2\pi ikj/4} =\begin{cases}4,&4\mid k,\\0,&4\nmid k.\end{cases}

若 $4\mid k$ ，四项全为 $1$ ；否则它们是公比不为 $1$ 、四次方为 $1$ 的等比数列，和为零。频率 $k=0,4,8,12,16$ 共五个，因此 $E(H)=5\cdot4^4/20=64$ ，与逐和计数完全相同。子群把加法碰撞集中在少数和上，也把 Fourier 系数集中在那些沿子群不改变相位的频率上。

在循环群上，这个恒等式可由FFT计算：对指示数组做一次 DFT，将各系数的模取四次方后求和，再除以群的阶。若处理整数集合，应先选足够大的循环长度，使所有整数和都落在同一个长度小于该周期的区间内；否则模加法会把不同整数和合并，计算到的是循环群中的能量。

小倍增还提供不同于能量的集合证书。Ruzsa 三角不等式与覆盖引理以固定表示的注入推出 $|A-A|\le |A+A|^2/|A|$ ，再把小和集转为少数差集平移的覆盖；四点整数集 $\{0,1,4,5\}$ 的例子逐项给出覆盖中心和相交见证。这与本页的碰撞计数相互补充，但不把大能量反向解释成整个集合的小倍增。

参考资料

Terence Tao and Van H. Vu, Additive Combinatorics, Cambridge University Press, 2006，§2.3（定义 2.8、引理 2.9 与推论 2.10，加性能量及和集界）；§4.1–4.2（有限群 Fourier 分析与式 (4.14)）。该书采用归一化 Fourier 系数，对应本页最后说明的 $N^3$ 版本。
Yufei Zhao, Graph Theory and Additive Combinatorics, Fall 2019，§7.12，定义 7.80、命题 7.84 与例 7.85，能量的组合解释及大能量与小倍增的关系。
David S. Dummit and Richard M. Foote, Abstract Algebra, 3rd ed., Wiley, 2004，第 5 章，有限生成阿贝尔群结构定理；本页用其有限情形逐个构造并穷尽特征标。

形式陈述 ​

反向链接

形式陈述