Combinatorial Proof that $p(n)/(1+\epsilon)^n \to 0$

195 Views Asked by At

I was thinking this morning about the identity $ \prod_{n=1}^{\infty} \left( \frac{1}{1-q^n} \right) = \sum_{n=0}^{\infty} p(n) q^n$. The product on the left converges for $|q|<1$, which implies the convergence of the series for $|q|<1$. Given $\epsilon >0$, let $q = \frac{1}{1+\epsilon} <1$. Then, the series must converge at $q$, implying that the $n^{th}$ term converges to $0$, which tells us that $\frac{p(n)}{(1+e)^n} \to 0$ as $n \to \infty$.

I want a combinatorial proof that this is true. Note this means that something that relies on this generating function proof (i.e. using the asymptotic formula for $p(n)$) is not allowed.

1

There are 1 best solutions below

1
On BEST ANSWER

Probability sort of counts as combinatorics. Let $r > 1$, and consider the experiment where we generate a multiset by choosing $K_i$ copies of $i$ independently for each $i \ge 1$, where $K_i$ is the geometric distribution with parameter $1 - r^{-i}$ (that is, $\Pr[K_i = k] = r^{-ik}(1 - r^{-i})$).

Any particular partition of $n$, say with $k_i$ copies of $i$ for each $i$, is generated by the experiment with probability

$$ \prod_{i = 1}^\infty r^{-ik_i}(1 - r^{-i}) = r^{-n} \prod_{i = 1}^\infty (1 - r^{-i}), $$

which is the same for each partition of $n$, so it can’t be more than $\frac{1}{p(n)}$. Thus

$$ \begin{align*} p(n) &\le r^n \prod_{i = 1}^\infty \frac{1}{1 - r^{-i}} \\ &= r^n \exp \sum_{i=1}^\infty -\ln (1 - r^{-i}) \\ &= r^n \exp \sum_{i=1}^\infty \sum_{k=1}^\infty \frac{r^{-ik}}{k} \\ &= r^n \exp \sum_{k=1}^\infty \frac{1}{k(r^k - 1)} \\ &< r^n \exp \sum_{k=1}^\infty \frac{1}{k^2(r - 1)} \\ &= r^n \exp \frac{\pi^2}{6(r - 1)}. \\ \end{align*} $$

We already get the desired result from $p(n) = O(r^n)$ for all $r > 1$. The tightest bound we can prove this way is at $r = 1 + \frac{\pi}{\sqrt{6n}}$, where

$$ \ln p(n) < n \ln r + \frac{\pi^2}{6(r - 1)} < n(r - 1) + \frac{\pi^2}{6(r - 1)} = \pi\sqrt{\frac23 n}, \\ p(n) < \exp\left(\pi\sqrt{\frac23 n}\right), $$

nearly matching the known asymptotic formula $p(n) \sim \frac{1}{4n\sqrt 3} \exp\left(\pi\sqrt{\frac23 n}\right)$.