Hardy-Littlewood Circle Method

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let:

$\displaystyle \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:

$\displaystyle \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:

$\displaystyle \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$:

$\displaystyle \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:

\(\displaystyle \map {r_{\AA, \ell} } N\) \(=\) \(\displaystyle \frac 1 {N!} \frac {\d^N} {\d s^N} \bigintlimits {\map T s^\ell} {s \mathop = 0} {}\)
\(\displaystyle \) \(=\) \(\displaystyle \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.