Phương pháp vòng tròn

Điều này cho phép ta thay một bài toán đếm tổ hợp thuần tuý bằng câu hỏi về độ lớn của một tích phân giải tích: nếu chứng minh được tích phân dương, thì chắc chắn tồn tại một cách biểu diễn.

Trước hết, dùng hệ thức trực giao: $\int_0^1 e(m\alpha)\, d\alpha$$=1$ nếu $m=0$, và $=0$ nếu $m\neq 0$: viết $e(m\alpha)=\cos(2\pi m\alpha)+i\sin(2\pi m\alpha)$, khi $m\neq0$ đây là trọn vẹn một số nguyên chu kỳ của sóng sin/cos trên $[0,1)$ nên tích phân bằng $0$; khi $m=0$ hàm dưới dấu tích phân là hằng số $1$.

Bây giờ khai triển luỹ thừa $k$ của hàm sinh: $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ột tổng hữu hạn trên mọi bộ $k$ phần tử có thứ tự lấy từ $A$, nhóm theo số mũ $m=a_1+\cdots+a_k$.

Nhân cả hai vế với $e(-n\alpha)$ rồi lấy tích phân từng số hạng trên $[0,1)$ (hợp lệ vì tổng hữu hạn nên tích phân và tổng giao hoán được): $\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$.

Theo hệ thức trực giao, mỗi số hạng bên phải bằng $1$ đúng khi $a_1+\cdots+a_k=n$ và bằng $0$ trong mọi trường hợp khác. Vậy toàn bộ tổng suy biến về đúng số bộ có $a_1+\cdots+a_k=n$, tức là $r_k(n)$. Điều này chứng minh định danh một cách chính xác tuyệt đối, không hề xấp xỉ: đây là một đẳng thức, không phải một công thức tiệm cận.

Điều này bảo đảm mọi điểm trên đường tròn đều nằm gần một số hữu tỉ có mẫu số nhỏ, và đó chính là điều cho phép ta chia $[0,1)$ thành các cung lớn — những khoảng ngắn quanh các xấp xỉ tốt $a/q$ với $q$ nhỏ, nơi $F_A$ lớn — và các cung nhỏ, phần còn lại.

Xét $Q+2$ số $0,\{\alpha\},\{2\alpha\},\dots,\{Q\alpha\},1$, trong đó $\{x\}$ là phần thập phân của $x$; tất cả đều nằm trong $[0,1]$. Chia $[0,1]$ thành $Q+1$ khoảng con bằng nhau, mỗi khoảng dài $1/(Q+1)$: $[0,\tfrac1{Q+1}), [\tfrac1{Q+1},\tfrac2{Q+1}),\dots$.

Ta có $Q+2$ số nhưng chỉ $Q+1$ khoảng con, nên theo nguyên lý chuồng bồ câu, hai trong số các số $\{j\alpha\}$ và $\{i\alpha\}$ (với $0\le i<j\le Q$, cho phép $i=0$ nên $\{i\alpha\}=0$) rơi vào cùng một khoảng con, do đó sai khác nhau ít hơn $1/(Q+1)$: $|\{j\alpha\}-\{i\alpha\}|<\tfrac{1}{Q+1}$.

Đặt $q=j-i$, vậy $1\le q\le Q$. Vì $\{j\alpha\}-\{i\alpha\} = (j\alpha - i\alpha) - (\lfloor j\alpha\rfloor - \lfloor i\alpha\rfloor) = q\alpha - a$ với số nguyên $a=\lfloor j\alpha\rfloor-\lfloor i\alpha\rfloor$, ta được $|q\alpha - a| < \tfrac{1}{Q+1}$, tức là $\left|\alpha-\dfrac aq\right| < \dfrac{1}{q(Q+1)}$.

Cuối cùng, nếu $\gcd(a,q)=d>1$, chia cả $a$ và $q$ cho $d$: phân số thu được có mẫu số còn nhỏ hơn và khoảng cách tới $\alpha$ bằng hoặc nhỏ hơn, nên ta có thể giả sử $\gcd(a,q)=1$ mà không mất tính tổng quát. Chứng minh hoàn tất; đây là lập luận chuồng bồ câu hữu hạn, mang tính dựng, không cần dựa vào bất kỳ ước lượng chưa được chứng minh nào.