提取(正交)恒等式

首先利用正交关系:$\int_0^1 e(m\alpha)\, d\alpha$$=1$(当 $m=0$ 时),$=0$(当 $m\neq 0$ 时):写 $e(m\alpha)=\cos(2\pi m\alpha)+i\sin(2\pi m\alpha)$,当 $m\neq0$ 时这恰好是正弦/余弦波在 $[0,1)$ 上整数个周期,积分为 $0$;当 $m=0$ 时被积函数是常数 $1$。

现在展开生成函数的 $k$ 次幂:$F_A(\alpha)^k=\Big(\sum_{a\in A}e(a\alpha)\Big)^k=\sum_{(a_1,\dots,a_k)\in A^k} e\big((a_1+\cdots+a_k)\alpha\big)$,这是对取自 $A$ 的所有有序 $k$ 元组按指数 $m=a_1+\cdots+a_k$ 分组后的一个有限和。

两边乘以 $e(-n\alpha)$,再在 $[0,1)$ 上逐项积分(因为是有限和,积分与求和可交换,故合法):$\int_0^1 F_A(\alpha)^k e(-n\alpha)\,d\alpha=\sum_{(a_1,\dots,a_k)\in A^k}\int_0^1 e\big((a_1+\cdots+a_k-n)\alpha\big)\,d\alpha$。

由正交关系,右边每一项恰好当 $a_1+\cdots+a_k=n$ 时为 $1$,否则为 $0$。于是整个和恰好收缩为满足 $a_1+\cdots+a_k=n$ 的元组个数,即 $r_k(n)$。这就精确地(无任何近似)证明了该恒等式:它是一个恒等式,而不是渐近公式。