Hardy-Littlewood Circle Method

Theorem

Let $\mathcal A$ be a subset of the non-negative integers.

Let:

$\displaystyle T \left({s}\right) = \sum_{a \in \mathcal A} s^a $

be the generating function for $\mathcal A$.

For $N \in \N$, let $r_{\mathcal A, \ell}(N)$ be the number of solutions $(x_1, \ldots, x_\ell) \in \mathcal A^\ell$ to the equation:

$x_1 + \cdots + x_\ell = N$

Then

$\displaystyle r_{\mathcal A, \ell}(N) = \oint_{|s| = \rho} \frac {T \left({s}\right)}{s^{N+1}} \ \mathrm d s$

for any $\rho \in \left({0 .. 1}\right)$.

Proof

We have:

$\displaystyle T \left({s}\right)^\ell = \sum_{N = 0}^\infty r_{\mathcal A,\ell}(N) s^N $

and:

$\displaystyle \frac{\mathrm d^N}{\mathrm d s^N} \left[ T \left({s}\right)^\ell \right] = N! \cdot r_{\mathcal A,\ell}(N) + O \left({s}\right)$

so:

$\displaystyle r_{\mathcal A, \ell}(N) = \frac 1 {N!} \frac{\mathrm d^N}{\mathrm d s^N} \left[ T \left({s}\right)^\ell \right]_{s = 0} $

Now recall Cauchy's Integral Formula for Derivatives for a complex function $f$ holomorphic on a domain $D$, and a path $\gamma \subseteq D$ winding once around $a$:

$\displaystyle \frac{\mathrm d^N}{\mathrm d s^N} f \left({s}\right) \Big|_{s = a} = \frac{ N! }{2 \pi i} \oint_{\gamma} \frac{f \left({s}\right)} {\left({ s - a }\right)^{N+1}} \ \mathrm d s$

Since $T \left({s}\right)$ is defined by a generating function, $T \left({s}\right)^\ell$ has a Taylor series about $s = 0$ which converges for all $|s| < 1$. Applying Cauchy's formula we have

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle r_{\mathcal A, \ell}(N)\)	\(=\)	\(\displaystyle \frac 1 {N!} \frac{\mathrm d^N}{\mathrm d s^N} \left[ T \left({s}\right)^\ell \right]_{s = 0}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac 1 {2 \pi i} \oint_\gamma \frac{T \left({s}\right)}{ s ^{N+1} } \ \mathrm d s\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

where $\gamma$ a circle about zero of radius $\rho$ for any $\rho < 1$.

$\blacksquare$

Source of Name

This entry was named for Godfrey Harold Hardy and John Edensor Littlewood.