The circle method

This is what lets us replace a purely combinatorial counting problem by a question about the size of an analytic integral: if we can show the integral is positive, a representation must exist.

First note the orthogonality relation $\int_0^1 e(m\alpha)\, d\alpha$$=1$ if $m=0$, and $=0$ if $m\neq 0$: writing $e(m\alpha)=\cos(2\pi m\alpha)+i\sin(2\pi m\alpha)$, for $m\neq0$ this is a full number of periods of a sine/cosine wave over $[0,1)$, which integrates to $0$; for $m=0$ the integrand is the constant $1$.

Now expand the $k$-th power of the generating function: $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 finite sum over all ordered $k$-tuples from $A$, grouped by the exponent $m=a_1+\cdots+a_k$.

Multiply both sides by $e(-n\alpha)$ and integrate term by term over $[0,1)$ (legitimate because the sum is finite, so integration and summation commute): $\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$.

By the orthogonality relation, each summand on the right is $1$ exactly when $a_1+\cdots+a_k=n$ and $0$ otherwise. So the whole sum collapses to exactly the count of tuples with $a_1+\cdots+a_k=n$, i.e. $r_k(n)$. This proves the identity exactly, with no approximation involved: it is an identity, not an asymptotic.

This guarantees that every point on the circle sits close to some low-denominator rational, which is exactly what lets us partition $[0,1)$ into major arcs — short intervals around the good approximations $a/q$ with $q$ small, where $F_A$ is large — and minor arcs, the leftover set.

Consider the $Q+2$ numbers $0,\{\alpha\},\{2\alpha\},\dots,\{Q\alpha\},1$, where $\{x\}$ denotes the fractional part of $x$; all lie in $[0,1]$. Partition $[0,1]$ into $Q+1$ equal subintervals of length $1/(Q+1)$: $[0,\tfrac1{Q+1}), [\tfrac1{Q+1},\tfrac2{Q+1}),\dots$.

We have $Q+2$ numbers and only $Q+1$ subintervals, so by the pigeonhole principle two of the numbers $\{j\alpha\}$ and $\{i\alpha\}$ (with $0\le i<j\le Q$, allowing $i=0$ so $\{i\alpha\}=0$) land in the same subinterval, hence differ by less than $1/(Q+1)$: $|\{j\alpha\}-\{i\alpha\}|<\tfrac{1}{Q+1}$.

Set $q=j-i$, so $1\le q\le Q$. Since $\{j\alpha\}-\{i\alpha\} = (j\alpha - i\alpha) - (\lfloor j\alpha\rfloor - \lfloor i\alpha\rfloor) = q\alpha - a$ for the integer $a=\lfloor j\alpha\rfloor-\lfloor i\alpha\rfloor$, we get $|q\alpha - a| < \tfrac{1}{Q+1}$, i.e. $\left|\alpha-\dfrac aq\right| < \dfrac{1}{q(Q+1)}$.

Finally, if $\gcd(a,q)=d>1$, divide both $a$ and $q$ by $d$: the resulting fraction has an even smaller denominator and the same (or a smaller) distance to $\alpha$, so we may take $\gcd(a,q)=1$ without loss of generality. This completes the proof; it is a finite, constructive pigeonhole argument, with no appeal to any unproved estimate.