7
$\begingroup$

I was studying some properties of partitions into primes and came across a surprising property. But before I talk about them, I am giving a definition.

Definition. A $k$-tuple $\lambda=(\lambda_1,\lambda_2,...,\lambda_k)$ is called a prime partition of a positive integer $n$ if the following hold:
a) $\lambda_1, \lambda_2, \dots, \lambda_k$ are distinct primes.
b) $\lambda_1 + \lambda_2 + \cdots + \lambda_k = n$.
c) $\lambda_1 < \lambda_2 < \cdots < \lambda_k$.

For example, one of the prime partitions of $10$ is $(2,3,5)$. Now, define $q(n)$ to be the number of all possible prime partitions of $n$. The values of $q(n)$ from $1$ to $20$ are: $$ 0, 1, 1, 0, 2, 0, 2, 1, 1, 2, 1, 2, 2, 2, 2, 3, 2, 4, 3, 4, \dots$$ The generating function of $q(n)$ is $$\prod_{p\,\text{ prime}}^{\infty}\frac1{1-n^p}$$ The question
I was (aimlessly) plotting functions in mathematica related to this function, and, after 15 minutes of plotting, I noticed that $$\log q(n)\sim\pi\sqrt{\frac{2}{3}\pi(n)}$$ where $\pi(n)$ is the prime counting function. This seems a bit hard to prove. I used the prime number theorem to get $$\log q(n)\sim\pi\sqrt{\frac23\frac n{\log n}}$$ I don't think that this would have an easy proof. Any article/proof of this might help. Another question: is there an asymptotic formula even stronger than this?
Note: I don't know about this result, I got it accidentally.

$\endgroup$
5
  • 1
    $\begingroup$ No answer, just more information and background on the topic and the generating function: math.stackexchange.com/questions/89240/prime-partition EDIT: I found the following article, where you're question is answered and discussed: arxiv.org/abs/1609.06497 $\endgroup$
    – jojobo
    Commented Dec 21, 2020 at 7:56
  • 1
    $\begingroup$ This sequence is to found as oeis.org/A000586 but this entry doesn't provide any asymptotic equivalent. $\endgroup$
    – Jean Marie
    Commented Dec 21, 2020 at 8:01
  • $\begingroup$ Nitpick: I think you missed a condition in your definition of "prime partition": you want to insist that the primes are listed in (say) increasing order, or else you want not tuples of primes but sets of primes. Otherwise the numbers need to be somewhat larger to account for permutations. $\endgroup$
    – Gareth McCaughan
    Commented Dec 21, 2020 at 16:44
  • 2
    $\begingroup$ This article academic.oup.com/qjmath/article-abstract/5/1/241/1519252 by Roth & Szekeres (found in the references to the article jojobo cited) proves a rather general theorem that gives such asymptotics for partitions using other sets of numbers besides the primes. $\endgroup$
    – Gareth McCaughan
    Commented Dec 21, 2020 at 16:49
  • $\begingroup$ Since you're not allowing repetition of the prime parts, I believe the generating function should have $(1+n^p)$ rather than $1/(1-n^p)$. Note that the arXiv paper @jojobo mentions allows for repeated prime parts. $\endgroup$
    – Brian Hopkins
    Commented Dec 27, 2020 at 22:39

1 Answer 1

Reset to default
0
$\begingroup$

This is a compilation of the comments which, together, answer your question.

Your sequence $q(n)$ is in the On-Line Encyclopedia of Integer Sequences as A000586. Since you require the primes to be distinct, the generating function is $$ \sum_{n=1}^\infty q(n)x^n = \prod_{p \text{ prime}}^\infty (1+x^p); $$ the generating function you gave would allow for arbitrary repetition of prime parts (discussed in OEIS A000607).

The OEIS entry does include an asymptotic formula, which follows from Roth & Szekeres 1954 as Gareth suggested. It is exactly what you found: $$ \log q(n) \sim \pi \sqrt{\frac{2n}{3 \log(n)}}.$$

$\endgroup$

You must log in to answer this question.