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
    Commented 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
    Commented Aug 10, 2020 at 1:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .