MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


I am interested in the asymptotic behavior of the function $p_o(n)$ defined as the number of partitions of $n$ into odd prime parts A099773 - .

I couldn't find any paper or book studying the mentioned quantity but the amount of literature available to me is quite limited and I am wondering if someone could tell me what the asymptotic behavior of $p_o(n)$ is and perhaps point out a relevant reference for me to read.


share|cite|improve this question
Note that OP has asked a related question previously,… – Gerry Myerson Jul 6 '11 at 23:47
As far as I can tell, the claim by Michael is correct. I would now like to find a concise reference stating that the number of partitions of $n$ into odd primes is asymptotically equivalent to the number of partitions of $n$ into primes so that it can be included in a paper unrelated to number theory! – Jernej Jul 7 '11 at 20:04
up vote 7 down vote accepted

Flajolet and Sedgewick, Analytic Combinatorics (link goes to free, legal downloadable PDF of book), section VIII.6 treats the asymptotics of various types of partitions. They get that the number of partitions of $n$ into prime parts, which they denote $P_n^{(\Pi)}$ (and which is A000607) satisfies $\log P_n^{(\Pi)} \sim (2\pi/\sqrt{3}) \sqrt{n/\log n}$ (Here $f(n) \sim g(n)$ has the usual meaning $\lim_{n \to \infty} f(n)/g(n) = 1$.)

I believe (but have not explicitly checked) that if you disallow any finite number of primes this asymptotic formula still holds; in particular it should hold in the case you're asking about.

Edited to add: The logarithmic growth rate comes from a saddle-point estimate which can in turn be derived from the rate of growth of $\prod_{n \ge 1} 1/(1-z^{p_n})$ (where $p_n$ is the $n$th prime) as $z \to 1^-$ along the real axis. As stated after the equation (73) in F&S, p. 580, $$ \sum_{n \ge 1} e^{-tp_n} \sim {t \over \log t} $$ and it's from this that the asymptotic result is derived. (Note that $z \to 1^-$ corresponds to $t \to 0^+$.) But if we omit the single term $e^{-2t}$ from that sum it won't change the asymptotic behavior at 0.

This isn't a full proof, though. The result is also a little bit counterintuitive, since one expects that a random partition of $n$ into primes, for large $n$, will contain at least one 2, and therefore leaving the 2s out should reduce the count considerably. But on the logarithmic scale this appears to be negligible.

share|cite|improve this answer
Thank you for your reply.The book is a very useful reference! I've skimmed through section VIII.6 but couldn't find anything that would explicitly imply that disallowing a constant amount of parts still yields the same asymptotics. I assume it is possible to conclude the fact from the analysis derived in the proofs but the machinery used there is too heavy for me. Anyone happens to see a simple argument why that holds? – Jernej Jul 7 '11 at 1:39
I've edited the answer to give some more detail. – Michael Lugo Jul 7 '11 at 3:30
Hello! I now see the gist of the saddle point analysis - thanks! I would still like to find a paper/book citing this fact though. The problem is that I need to include this fact in a paper (pretty much unrelated to number theory) so I do not wish to introduce all these concepts and actually prove the propriety but simply state it and give a valid reference point for it. Perhaps there is a way to bound the number of prime partitions with odd and even parts and from there conclude that the stated asymptotics still holds? – Jernej Jul 7 '11 at 12:55
That is counterintuitive. Isn't the number of partitions into odd prime parts (call this $p(n)$ ) just the sum of $p_o(n-2j)$ for $0 \le j \le \lfloor \frac{n-3}{2} \rfloor?$ The limited data at the OEIS does not make it seem that $p_o$ grows at a dramatic rate. Is there an asymptotic estimate for $\frac{p(n)}{p_o(n)}?$ – Aaron Meyerowitz Jul 8 '11 at 6:00

I think I found the answer I was looking for in some old paper by Erdos.

On page 448 he says:

Let $a_1 < a_2 < ...$ be an infinite sequence of integers of density $\alpha$ such that the a's have no common factor. Denote by $p'(n)$ the number of partitions of $n$ into the a's. Then $$\log(p'(n)) = c(\alpha n)^{1/2}.$$ where $c = \pi \sqrt{\frac{2}{3}}$

I just have to make sure what precisely he meant with the term density as in the classical sense density of a sequence is defined as a number and in this case the asymptotic identity he derived makes no sense. If someone knows what is the precise definition of density in this case, let me know it as a comment please!

share|cite|improve this answer
I believe Erdos means the usual asymptotic density. The "no common factor" condition just means that there is not some m which divides all the $a_i$. So for example if $a_n = 2n$, this formula does not give the logarithmic order of the number of partitions of $n$ into even parts; but if $a_n = 2n-1$ it does give the logarithmic order of the number of partitions into odd parts, with $\alpha = 1/2$. – Michael Lugo Jul 7 '11 at 15:36
This is not so useful, because the density of the primes is $0$. So this formula tells you that $\log p'(n) = o(\sqrt{n})$, which is consistent with Michael's answer, but it doesn't give you a precise rate of growth. – David Speyer Jul 7 '11 at 16:01
Although in some suitably generalized and handwavy sense the density of the primes is one over log... – Michael Lugo Jul 7 '11 at 19:27
Yeah, I somehow hoped that by "density" he meant "that" density of primes which sounded plausible as one would then obtain the required identity. The search for a reference containing this fact is thus still on! – Jernej Jul 7 '11 at 20:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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