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

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!

• It seems r(n) is the sum over all partitions p of n of the product d(a) for a ranging over the members of p, and d being the divisor function. As d(1)=1, perhaps there is a simplification of the sum or the product terms that may give you some good estimates? – The Masked Avenger Mar 10 '14 at 16:53
• As another twist, consider the related function s(n) which counts those representation that do not have 1*1 as a summand, so s(3)=2. Then r(n) = 1 + sum s(i) for i at most n. Perhaps s(n) will be tractable. – The Masked Avenger Mar 10 '14 at 17:00
• I just realized that I assumed a product always has the form ab for a and b some numbers. If ab*c is allowed, then I don't know how to approach r(n) at all. – The Masked Avenger Mar 10 '14 at 17:07
• I think this is oeis.org/A006171 and a reference and some formulas are given there, but I see no asymptotics. – Gerry Myerson Mar 11 '14 at 4:00
• One can get an asymptotic formula for problems like this by using the saddle point method. This is classical, but one reference may be these course notes: math.berkeley.edu/~moorxu/oldsite/notes/155/155main.pdf , see page 44 and following. That deals with the partition problem with generating function $\Gamma(s)\zeta(s)\zeta(s+1)$ (see page 47); you need to make similar calculations with $\Gamma(s)\zeta(s)^2\zeta(s+1)$. There won't be the modular forms miracle as with partitions, but one doesn't need that for an asymptotic. – Lucia Mar 16 '14 at 14:25

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.
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.