円周法

これにより、純粋に組合せ論的な数え上げ問題を、ある解析的積分の大きさに関する問いに置き換えることができる:その積分が正であることを示せれば、表現が存在することになる。

まず直交関係を用いる:$\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)$、これは指数 $m=a_1+\cdots+a_k$ ごとにまとめた、$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)$ を、$F_A$ が大きくなる小さい $q$ の良い近似 $a/q$ の周りの短い区間であるメジャーアークと、残りのマイナーアークに分割することを可能にする。

$0,\{\alpha\},\{2\alpha\},\dots,\{Q\alpha\},1$ という $Q+2$ 個の数を考える。ここで $\{x\}$ は $x$ の小数部分であり、すべて $[0,1]$ に属する。$[0,1]$ を長さ $1/(Q+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$ とできる。以上で証明が完了する。これは有限で構成的な鳩の巣論法であり、未証明の評価には一切頼っていない。