圆法

这使我们能把纯组合计数问题换成关于某个解析积分大小的问题:只要证明该积分为正,就必定存在一种表示。

首先利用正交关系:$\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)$。这就精确地(无任何近似)证明了该恒等式:它是一个恒等式,而不是渐近公式。

这保证了圆上每一点都靠近某个分母较小的有理数,这正是我们能把 $[0,1)$ 划分为主弧(围绕分母 $q$ 较小的良好逼近 $a/q$ 的短区间,在此 $F_A$ 较大)与次弧(其余部分)的原因。

考虑 $Q+2$ 个数 $0,\{\alpha\},\{2\alpha\},\dots,\{Q\alpha\},1$,其中 $\{x\}$ 表示 $x$ 的小数部分;它们都属于 $[0,1]$。将 $[0,1]$ 划分为 $Q+1$ 个长度为 $1/(Q+1)$ 的相等子区间:$[0,\tfrac1{Q+1}), [\tfrac1{Q+1},\tfrac2{Q+1}),\dots$。

我们有 $Q+2$ 个数却只有 $Q+1$ 个子区间,由鸽笼原理,必有两个数 $\{j\alpha\}$ 与 $\{i\alpha\}$($0\le i<j\le Q$,允许 $i=0$ 即 $\{i\alpha\}=0$)落入同一子区间,从而相差小于 $1/(Q+1)$:$|\{j\alpha\}-\{i\alpha\}|<\tfrac{1}{Q+1}$。

设 $q=j-i$,则 $1\le q\le Q$。因为 $\{j\alpha\}-\{i\alpha\} = (j\alpha - i\alpha) - (\lfloor j\alpha\rfloor - \lfloor i\alpha\rfloor) = q\alpha - a$(其中整数 $a=\lfloor j\alpha\rfloor-\lfloor i\alpha\rfloor$),故 $|q\alpha - a| < \tfrac{1}{Q+1}$,即 $\left|\alpha-\dfrac aq\right| < \dfrac{1}{q(Q+1)}$。

最后,若 $\gcd(a,q)=d>1$,将 $a$ 和 $q$ 同除以 $d$:所得分数分母更小,与 $\alpha$ 的距离相同或更小,因此不失一般性可设 $\gcd(a,q)=1$。证明完成;这是一个有限的、构造性的鸽笼论证,不依赖任何未经证明的估计。