3
$\begingroup$

Hello!

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 - http://oeis.org/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.

Thanks!

Improve this question
$\endgroup$
2
  • $\begingroup$ Note that OP has asked a related question previously, mathoverflow.net/questions/58408/… $\endgroup$
    – Gerry Myerson
    Commented Jul 6, 2011 at 23:47
  • $\begingroup$ 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! $\endgroup$
    – Jernej
    Commented Jul 7, 2011 at 20:04

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Jernej
    Commented Jul 7, 2011 at 1:39
  • $\begingroup$ I've edited the answer to give some more detail. $\endgroup$
    – Michael Lugo
    Commented Jul 7, 2011 at 3:30
  • $\begingroup$ 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? $\endgroup$
    – Jernej
    Commented Jul 7, 2011 at 12:55
  • $\begingroup$ 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)}?$ $\endgroup$
    – Aaron Meyerowitz
    Commented Jul 8, 2011 at 6:00
1
$\begingroup$

I think I found the answer I was looking for in some old paper by Erdos. http://www.renyi.hu/~p_erdos/1942-02.pdf

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 http://en.wikipedia.org/wiki/Asymptotic_density 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!

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Michael Lugo
    Commented Jul 7, 2011 at 15:36
  • $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Commented Jul 7, 2011 at 16:01
  • $\begingroup$ Although in some suitably generalized and handwavy sense the density of the primes is one over log... $\endgroup$
    – Michael Lugo
    Commented Jul 7, 2011 at 19:27
  • $\begingroup$ 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! $\endgroup$
    – Jernej
    Commented Jul 7, 2011 at 20:06

You must log in to answer this question.

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