Number of representations of an integer as an (arbitrary) sum of products

Question

If $n$ is a positive integer, let $r(n)$ denote the number of representations of $n$ as a sum of products of pairs of positive integers. (Here, the order of the terms in the sum does not matter, but products with the same answer are regarded as different, even if they contain the same two numbers in a different order.) For example,

r(1) = 1;

r(2) = 3:

2 = 2*1 = 1*2 = 1*1 + 1*1;

r(3) = 5:

3 = 3*1 = 1*3 = 2*1 + 1*1 = 1*2 + 1*1 = 1*1 + 1*1 + 1*1.

I would very much like to know whether the asymptotic of $r(n)$ is known, or whether it can be derived easily from known results/methods.

(Of course, the problem can be rephrased in terms of $\Lambda$-partitions. Recall that if $\Lambda$ is a non-decreasing sequence of positive integers, $$\Lambda_1 \leq \Lambda_2 \leq \ldots,$$ with $\Lambda_k \to \infty$ as $k \to \infty$, a $\Lambda$-partition of $n$ is a representation of $n$ as a sum $$n = \sum_{k=1}^{\infty} m_k \Lambda_k,$$ with $m_k \in \mathbb{N} \cup \{0\}$ for all $k$. If $\Lambda$ is the sequence with $d(s)$ copies of $s$ for every positive integer $s$, where $d(s)$ denotes the number of divisors of $s$, then $r(n)$ is the number of $\Lambda$-partitions of $n$.)

The generating function of $r(n)$ is given by

$$\sum_{n=0}^{\infty} r(n) z^n = \prod_{(k,l) \in \mathbb{N}^2} (1-z^{kl})^{-1},$$

and so the theorem of N. A. Brigham in [A General Asymptotic Formula for Partition Functions, Proc. Amer. Math. Soc., 1950] gives the asymptotic of $\log r(n)$:

$$\log r(n) \sim \sqrt{2\zeta(2) n \log n} = \pi \sqrt{\tfrac{1}{3} n \log n}.$$

Unfortunately, the more precise Tauberian theorem of Ingham [A Tauberian Theorem for Partitions, Ann. Math, 1941], which gives the asymptotic of $a(n)$ for a wide class of partition functions $a(n)$, does not seem to be applicable, since his function $R(u)$ (in his Theorem 2) grows like $u \log u$ in the above case, rather than like $u^{\beta}$+(small error) for some fixed $\beta >0$. The associated Dirichlet series

$$D(s) = \sum_{(i,j)\in \mathbb{N}^2} s^{-ij} = \zeta(s)^2$$

is the square of the Riemann zeta function. This has a pole of order 2 at $s=1$, so the theorem of Meinardus on $\Lambda$-partitions is not applicable, either.

I am not familiar enough with the area to know whether the Hardy-Littlewood circle method, or some other method, can be adapted to work in the case of $r(n)$. Any help would be greatly appreciated!

Answer 1

Put $F(z)= \prod_{n=1}^{\infty} (1-z^n)^{-d(n)}$, where $d(n)$ is the number of divisors of $n$. The problem asks for the asymptotics for $$ R(N) = \frac{1}{2\pi i} \int_{|z|=r} F(z) z^{-N} \frac{dz}{z}, $$ where the integral is taken over any circle with radius $r<1$. A standard way of obtaining asymptotics in such contexts is to use the saddle point method. Note that $$ \log F(z) = \sum_{n=1}^{\infty} d(n) \log (1-z^n)^{-1} = \sum_{n=1}^{\infty} z^{n} \sum_{ab=n} \frac{d(a)}{b}. $$ One chooses the radius $r$ so as to minimize $F(r)r^{-N}$: this is attained when $$ N= r\frac{F^{\prime}}{F}(r) =\sum_{n=1}^{\infty} r^{n} \sum_{ab=n} ad(a). $$ For such a value of $r$, the quantity $F(re^{i\theta})(re^{i\theta})^{-N}$ for small values of $\theta$ will look like $F(r)r^{-N}e^{-\frac{\theta^2}{2} F_2(r)}$ where $$ F_2(r) = \sum_{n=1}^{\infty} nr^{n} \sum_{ab=n} ad(a). $$ Then our integral is asymptotically the same as $$ \frac{1}{2\pi} \int_{-\pi}^{\pi} F(r)r^{-N} e^{-\frac{\theta^2}{2} F_2(r)} d \theta \sim \frac{F(r) r^{-N}}{\sqrt{2\pi F_2(r)}}. $$ This is the desired asymptotic for $R(N)$, once we gain some understanding of how $r$ depends on $N$, and how the corresponding $F(r)$ and $F_2(r)$ behave.

Put $r=e^{-1/X}$. Then using Mellin transforms, our equation for $r$ becomes (for any $c>2$) $$ N = \sum_{n=1}^{\infty} e^{-n/X} \sum_{ab=n} ad(a) = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} X^s \Gamma(s) \zeta(s) \zeta(s-1)^2 ds. $$
The above can be evaluated by moving the line of integration to the left and computing the residues of the poles at $s=2$ (double pole), $s=1$ and $s=0$. Note that the integrand is regular at all other points (because the other poles of $\Gamma$ will cancel with corresponding trivial zeros of $\zeta(s)$), so the resulting asymptotic will be very accurate with an error of $O(X^{-A})$ for any natural number $A$. Thus a computation shows that $$ N= \zeta(2) X^2 \Big(\log X + \gamma + \frac{\zeta^{\prime}}{\zeta}(2)\Big) + \frac{X}{4} + \zeta(0) \zeta(-1)^2 + O(X^{-A}). \tag{1} $$ A similar calculation shows that $$ \log F(r) = \zeta(2) X \Big(\log X+ \gamma +\frac{\zeta^{\prime}}{\zeta}(2) \Big) + \frac 14 \log X + 2\zeta^{\prime}(0) \zeta(0). $$ (Note that $\zeta(0) \zeta(-1)^2 =-1/288$ and $2\zeta^{\prime}(0)\zeta(0) = \log \sqrt{2\pi}$.) Finally we have $$ F_2(r) =\sum_{n=1}^{\infty} nr^{n} \sum_{ab=n} ad(a) \sim 2XN. $$
Putting these together we get $$ R(N) \sim \frac{1}{\sqrt{2} X^{\frac 14} N^{\frac 12}} \exp\Big(\frac{2N}{X} -\frac 14\Big). $$ Here $X$ is given in terms of $N$ by (1), and it is easy to see that $X \sim \sqrt{12N/(\pi^2 \log N)}$; one can of course compute $X$ much more precisely, and it is a close relative of the Lambert $W$-function. Warning: I think the constants above are correct, but wouldn't swear to them. In any case the method of proof should be clear. For details along these lines for the partition function, see for example the course notes linked in my comment above.

Answer 2

Put $$ H(z) = \sum_{n\geq 1}r(n)z^n = \prod_{n=1}^\infty\left(1-\tau(n)z^n\right)^{-1} = \exp\left(\sum_{n=1}^\infty\sum_{\nu=1}^\infty\frac{\tau(n)z^{n\nu}}{\nu}\right), $$ and $f(t)=H(e^{-t})$. Then by the Mellin transform $$ e^{-t} = \int_{2-i\infty}^{2+\infty}t^{-s}\Gamma(s)\;ds $$ we get $$ \log f(t) = \frac{1}{2\pi i}\int_{2-i\infty}^{2+i\infty} t^{-s}\Gamma(s)\zeta^2(s)\;ds. $$ Shifting the path of integration to the left yields $\log f(t)= (c_1\log t+c_2)t+\mathcal{O}(t^{-c})$ (Note that $\zeta(s)\Gamma(s)$ can be bounded using the functional equation). Then some elementary calculus yields $$ \log r(n) = [z^n]\exp\big(c_1(1-z)\log(1-z)+c_2(1-z)\big) + \mathcal{O}(n^{-c}), $$ where $[z^n]f(z)$ means "the coefficient of $z^n$ in $f(z)$". After some more computation one should arrive at an asymptotic series of the form $$ \log r(n) \approx y\left(1+\sum_{\nu\geq 1}a_\nu n^{-\nu}\right), $$ where $y$ is implicitly defined by some equation, which probably looks like $y^2P(\log y)+\mbox{smaller terms} = n$, where $P$ is a polynomial of degree of 2. Still not an asymptotics, but I possibly the best one could get.