# Hardy-Littlewood Circle Method

## Theorem

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

Let:

- $\ds \map T s = \sum_{a \mathop \in \AA} s^a$

be the generating function for $\AA$.

For $N \in \N$, let $\map {r_{\AA, \ell} } N$ be the number of solutions $\tuple {x_1, \ldots, x_\ell} \in \AA^\ell$ to the equation:

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

Then:

- $\ds \forall \rho \in \openint 0 1: \map {r_{\AA, \ell} } N = \oint_{\size s \mathop = \rho} \frac {\map T s^\ell} {s^{N + 1} } \rd s$

## Proof

We have:

- $\ds \map T s^\ell = \sum_{N \mathop = 0}^\infty \map {r_{\AA, \ell} } N s^N$

and:

- $\map {\dfrac {\d^N} {\d s^N} } {\map T s^\ell} = N! \cdot \map {r_{\AA, \ell} } N + \map \OO s$

so:

- $\map {r_{\AA, \ell} } N = \dfrac 1 {N!} \dfrac {\d^N} {\d s^N} \bigintlimits {\map T s^\ell} {s \mathop = 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$:

- $\ds \valueat {\frac {\d^N} {\d s^N} \map f s} {s \mathop = a} = \frac {N!} {2 \pi i} \oint_\gamma \frac {\map f s} {\paren {s - a}^{N + 1} } \rd s$

Since $\map T s$ is defined by a generating function, $\map T s^\ell$ has a Taylor series about $s = 0$ which converges for all $\size s < 1$.

Applying Cauchy's formula:

\(\ds \map {r_{\AA, \ell} } N\) | \(=\) | \(\ds \frac 1 {N!} \frac {\d^N} {\d s^N} \bigintlimits {\map T s^\ell} {s \mathop = 0} {}\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds \frac 1 {2 \pi i} \oint_\gamma \frac {\map T s^\ell} {s^{N + 1} } \rd s\) |

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.