Hardy-Littlewood Circle Method

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let:

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

be the generating function for $\mathcal A$.


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

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


Then:

$\displaystyle \forall \rho \in \left({0 \,.\,.\, 1}\right): r_{\mathcal A, \ell} \left({N}\right) = \oint_{ \left\vert{s}\right\vert \mathop = \rho} \frac {T \left({s}\right)^\ell} {s^{N + 1} } \, \mathrm d s$


Proof

We have:

$\displaystyle T \left({s}\right)^\ell = \sum_{N \mathop = 0}^\infty r_{\mathcal A, \ell} \left({N}\right) 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} \left({N}\right) + O \left({s}\right)$

so:

$\displaystyle r_{\mathcal A, \ell} \left({N}\right) = \frac 1 {N!} \frac {\mathrm d^N} {\mathrm d s^N} \left[{T \left({s}\right)^\ell}\right]_{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 \left.{\frac {\mathrm d^N} {\mathrm d s^N} f \left({s}\right)}\right\vert_{s \mathop = 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 $\left\vert{s}\right\vert < 1$.


Applying Cauchy's formula:

\(\displaystyle r_{\mathcal A, \ell} \left({N}\right)\) \(=\) \(\displaystyle \frac 1 {N!} \frac {\mathrm d^N} {\mathrm d s^N} \left[{T \left({s}\right)^\ell}\right]_{s \mathop = 0}\)
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 {2 \pi i} \oint_\gamma \frac {T \left({s}\right)^\ell} {s^{N+1} } \, \mathrm d 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.