1
$\begingroup$

I need a reference for the following question:

Let $\mathcal{P}$ be a finite set of $k$ primes and let $f(n)$ be the number of partitions of $n$ into parts whose prime factors are restricted to the set $\mathcal{P}$. Then $f(n)<Ce^{\ln(n)^{k+1}}$ for some constant $C$.

It feels very classical, but I have not managed to track it down.

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $\mathcal{P}=\{p_1,p_2,\ldots,p_k\}$. Then the generating function of $f(n)$ is \begin{align} G_{f}(t):=\sum_{n\ge 0}f(n)e^{-nt}=\prod_{\ell_1,\ell_2,\ldots,\ell_k\ge 0}\frac{1}{1-\exp\left(-t\prod_{1\le j\le k}p_j^{\ell_j}\right)}, \end{align} where $t>0$. This means $$f(n)\le G_f(t)e^{nt}$$ for any integer $n>0$ and any real number $t>0$. On the other hand, using part integration, \begin{align*} \log G_{f}(t)&=-\sum_{\ell_1,\ell_2,\ldots,\ell_k\ge 0}\log\left(1-\exp\left(-t\prod_{1\le j\le k}p_j^{\ell_j}\right)\right)\\ &=-\int_{1-}^{\infty}\log\left(1-\exp\left(-t x\right)\right)\,dS(x)\\ &=\int_{1}^{\infty}\frac{tS(x)}{e^{xt}-1}\,dx, \end{align*} where $$S(x)=\sum_{\substack{\prod_{1\le j\le k}p_j^{\ell_j}\le x,\;\ell_1,\ell_2,\ldots,\ell_k\ge 0}}1.$$ Clearly,

$$S(x)\le \prod_{1\le j\le k}\left(1+\left\lfloor\frac{\log x}{\log p_1}\right\rfloor\right)=\frac{(\log x)^k}{\prod_{1\le j\le k}\log p_j}+O\left((\log x)^{k-1}\right).$$ Thus one can from above obtain \begin{align*} \log G_{f}(t) &\le \frac{\log^{k+1}(1/t)}{(k+1)\prod_{1\le j\le k}\log p_j}+O(\log^k(1/t)). \end{align*} Taking $t=1/n$ then there exist a constant $C_k>0$ such that $$f(n)\le G_f(t)e^{nt}\le \exp\left(1+\frac{\log^{k+1}n}{(k+1)\prod_{1\le j\le k}\log p_j}+O(\log^kn)\right)\le C_k e^{\log^{k+1}n}$$ by note that $(k+1)\prod_{1\le j\le k}\log p_j>1$.

$\endgroup$
2
  • $\begingroup$ Thank you so much for your answer! The argument you made is along my lines of thought also, and definitely feels that it should be out there in the literature somewhere. $\endgroup$
    – Vlad Matei
    Aug 9, 2020 at 12:53
  • $\begingroup$ If there is only a prime number of $p $, there will be a lot of literature. For example, see [Mahler, K. (1940), On a Special Functional Equation. Journal of the London Mathematical Society, s1-15: 115-123. doi:10.1112/jlms/s1-15.2.115]. Otherwise, there seems to be no such literature. Of course, using [Richmond, L. B. Asymptotic relations for partitions. J. Number Theory 7 (1975), no. 4, 389–405.], we can also get a more accurate asymptotic formula than your result through more complicated calculation. $\endgroup$
    – Zhou
    Aug 10, 2020 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.