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.
-
$\begingroup$ Are the other determinants "circulant"? $\endgroup$– Igor RivinCommented Aug 1, 2013 at 19:42
-
$\begingroup$ 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... $\endgroup$– SuvritCommented Aug 2, 2013 at 4:50
-
$\begingroup$ Some motivation: mathoverflow.net/questions/270207/… $\endgroup$– YCorCommented Jun 18, 2017 at 16:42
3 Answers
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.
-
2$\begingroup$ +1: so we have yet another candidate for the phenomenon of eventual counterexamples :-) $\endgroup$– SuvritCommented Aug 1, 2013 at 18:15
-
9$\begingroup$ 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$. $\endgroup$ Commented Aug 2, 2013 at 18:46
-
1$\begingroup$ @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. $\endgroup$ Commented Aug 2, 2013 at 21:34
-
5$\begingroup$ 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 $\endgroup$ Commented Nov 2, 2013 at 3:09
-
5$\begingroup$ And very important! In the comment immediately above, "This is easily fixed by ... " replace the ... with "replacing all $n$'s with $n-1/24$ and multiplying the first term in the expansion by $(1-1/(c \sqrt{n-1/24}))$." This $n-1/24$ in place of $n$ is essential otherwise the relative error is still $O(n^{-1/2})$. $\endgroup$ Commented Nov 14, 2013 at 16:30
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.
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.
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)
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.
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.
UPDATE 11-23-15:
Igor and I were recently informed of work by Jean-Louis Nicolas which also contains a proof of the log-concavity of the partition numbers:
Sur les entiers N pour lesquels il y a beaucoup de groupes abéliens d’ordre N, Annales de l’institut Fourier, tome 28, no 4 (1978), p. 1-16.
-
3$\begingroup$ 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! $\endgroup$– SuvritCommented Aug 1, 2013 at 21:32
-
1$\begingroup$ 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. $\endgroup$ Commented Aug 2, 2013 at 3:47
-
$\begingroup$ 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! $\endgroup$– SuvritCommented Aug 2, 2013 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.
