Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $p(n)$ denote the number of partitions of a positive integer $n$. It seems to me that we have for all $n>25$ $$ p(n)^2>p(n-1)p(n+1). $$ In other words, the sequence $(p(n))_{n\in \mathbb{N}}$ is log-concave, or satisfies $PF_2$, with $$ \det \begin{pmatrix} p(n) & p(n+1) \cr p(n-1) & p(n) \end{pmatrix}>0 $$ for $n>25$. Is this true ? I could not find a reference in the literature so far. On the other hand, the partition function is really studied a lot. So it seems likely that this is known.
Similarly, property $PF_3$, with the corresponding $3\times 3$ determinant, seems to hold for all $n>221$, too, and also $PF_4$ for all $n>657$.
The question is also motivated from the study of Betti numbers for nilpotent Lie algebras, in particular filiform nilpotent Lie algebras.

share|improve this question
    
Are the other determinants "circulant"? –  Igor Rivin Aug 1 '13 at 19:42
    
Maybe it's worth noting that $p(n)$ is a convex sequence, so it's log-concavity makes it feel like some sort of exponential... –  Suvrit Aug 2 '13 at 4:50

3 Answers 3

up vote 16 down vote accepted

The first two terms of the Hardy-Ramanujan formula give $$p(n) = \frac{1}{4 \sqrt{3} n} \exp(\pi \sqrt{2n/3}) + O \left(\exp(\pi \sqrt{n/6} ) \right)$$ so $$\log p(n) = \pi \sqrt{2/3} \sqrt{n} - \log n - \log (4 \sqrt{3}) + O(\exp(-\pi \sqrt{n/6} ) ).$$ So $$\log p(n+2) - 2 \log p(n+1) + \log p(n) = $$ $$ \pi \sqrt{2/3} \left( \sqrt{n+2} - 2\sqrt{n+1} + \sqrt{n} \right) - \left( \log(n+2) - 2 \log(n+1) + \log n \right) + O(\exp(-\pi \sqrt{n/6} ) )$$ $$= \left[ \left( \frac{- \pi \sqrt{2/3}}{4} \right) n^{-3/2} + O(n^{-5/2}) \right] + O(n^{-2}) + O(\exp(-\pi \sqrt{n/6} ) ).$$ So this quantity is negative for $n$ sufficiently large.

The larger determinants seem harder; there is probably a smarter way to do this.


With the help of Mathematica, I set $q(n) = a \exp(c \sqrt{n})/n$ and computed that $$\det \begin{pmatrix} q(n) & q(n+1) & q(n+2) \\ q(n-1) & q(n) & q(n+1) \\ q(n-2) & q(n-1) & q(n) \end{pmatrix} = q(n)^3 \left( \frac{c^3}{32 n^{9/2}} + O(n^{-10/2}) \right).$$ The error in approximating $p(n)$ by $q(n)$ (for $a = 1/(4 \sqrt{3})$ and $c = \pi \sqrt{2/3}$) will be exponentially smaller than $n^{-9/2}$, so the $3 \times 3$ determinant is positive for $n$ large.

The $4 \times 4$ determinant vanishes to order at least $n^{-12/2}$, and I gave up waiting for the computation to finish when I asked for more terms.

share|improve this answer
1  
+1: so we have yet another candidate for the phenomenon of eventual counterexamples :-) –  Suvrit Aug 1 '13 at 18:15
    
Presumably the higher determinants reduce (asymptotically) to the same question for the main term of the asymptotic expansion. How would one go to check that a function satisfies $PF_k$ (in the OP's notation)? –  Igor Rivin Aug 1 '13 at 19:44
5  
Since this answer was accepted, I feel obligated to point out that this does not answer the original question, which was about all $n > 25$. This answer addresses log-concavity of the partition function for all $n>n_0$ for some unspecified $n_0$. If this was the intended question, I suggest editing the original question to reflect this, otherwise a casual reader might confuse the asymptotic analysis as a rigorous proof for all $n>25$. –  Stephen DeSalvo Aug 2 '13 at 18:46
1  
@Stephen DeSalvo: I have accepted the answer, although it does not completely answer the question. I do not think that accepting is only possible if everything is answered - often this is not possible. The reference of Janoski's thesis is almost an answer. Unfortunately I am not yet convinced. –  Dietrich Burde Aug 2 '13 at 21:34
2  
The asymptotic expansion for $p(n)$ in the first line is wrong. The error term is actually $O(\exp(\pi \sqrt{2n/3})/\sqrt{n})$. This fact completely negates even this asymptotic argument, since the Big-Oh error term is larger than the $n^{-3/2}$, which is the rate of decay of log-concavity. This is easily fixed by multiplying the first term in the expansion by $(1-1/c\sqrt{n}))$, where $c = \pi \sqrt{2/3}$. This does not affect the final answer (in this case!), but without it the argument as written is invalid. See for example Section 6.2 of arxiv.org/pdf/1310.7982v1.pdf –  Stephen DeSalvo Nov 2 '13 at 3:09

The statement referenced by Igor Rivin http://www.math.clemson.edu/~janoski/ResearchStatement.pdf uses the phrase

Computationally looking at p(n) we see that for n ≥ 26 the partition function is log-concave [2].

I had seen this reference before probably about the same time this research statement was first released, and I am skeptical for two reasons.

  1. The phrasing "Computationally..." would seem to indicate some type of calculation. This cannot involve a computer since it would have to hold for all n larger than 26, and I am not aware of any simplification that allows one to only consider a finite number of cases. It would have been helpful to at least expound on the type of computations involved.

  2. I checked for the promised reference, and indeed I found it on the CV of the author, http://www.math.clemson.edu/~janoski/VitaTex.pdf, but it refers to the quote below. I did a quick google search and I could find no reference or anything pointing to a publication.

    Brian Bowers, Neil Calkin, Kerry Gannon, Janine E. Janoski, Katie Joes, Anna Kirkpatrick, The Log Concavity of the Partition Function, (in preparation)

  3. Asymptotics will not provide the answer here, since n sufficiently large doesn't hold up unless you can provide a concrete n and test everything less than it, and I don't believe the Hardy-Ramanujan asymptotic expansion yields any guaranteed error estimates.

  4. It may be possible to use DH Lehmer's estimates to obtain a proof. In two papers (1937 and 1939) he investigated the coefficients of both the Hardy-Ramanujan asymptotic expansion and the Hardy-Ramanujan-Rademacher expansion. He provided guaranteed error bounds on the remainder terms in the asymptotic expansions so that, for example, his Theorem 13 says that for n>600, only $2/3 \sqrt n$ terms of the Hardy-Ramanujan asymptotic series are needed to estimate p(n) to the nearest integer.

At present, I don't believe the matter is completely settled, despite the overwhelming computational evidence.

UPDATE 11-1-13:

Igor Pak and I have just uploaded a preprint to the ArXiv: http://arxiv.org/abs/1310.7982 . In it we prove the log-concavity of the partition numbers for all $n>25$, and Section 6.3 addresses Janoski's thesis.

share|improve this answer
3  
But it seems that in the thesis: math.clemson.edu/~janoski/reu/2012/thesis.pdf from Janoski, there is a proof; I've only skimmed it as of now (pg. 7 onwards), but maybe you can judge better if that delivers on the promise. Thanks! –  Suvrit Aug 1 '13 at 21:32
    
I find pages 9 and 10 of the proof highly suspect. On page 9, there is an inequality about 1/3 of the way down that I do not believe is true. There appears to be a positivity and monotonicity assumption placed on the coefficients $A_k(n)$ that is simply not true. I believe counterexamples to the inequality are n=27, 36, 87, 744. These are just a few that I checked by eye in Mathematica. –  Stephen DeSalvo Aug 2 '13 at 3:47
    
Very interesting; I don't know, however, if Janoski's whole approach is flawed or it is rescueable. I'd like to see a version based on PF though! –  Suvrit Aug 2 '13 at 4:22

This paper from a J. Janoski at Clemson seems to indicate that despite the fact that partitions have been studied half-to-death, the log concavity is still somewhat open (AND the asymptotic way of doing it is the only way known). Note that a related unimodality theorem of Szekeres (for partitions into $k$ parts) is only proved using asymptotics, and not a bijective correspondence, so the "book proofs" of both facts still elude us.

share|improve this answer

Your Answer

 
discard

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.