25
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Are the other determinants "circulant"? $\endgroup$
    – Igor Rivin
    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$
    – Suvrit
    Aug 2, 2013 at 4:50
  • $\begingroup$ Some motivation: mathoverflow.net/questions/270207/… $\endgroup$
    – YCor
    Jun 18, 2017 at 16:42

3 Answers 3

22
$\begingroup$

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.

$\endgroup$
10
  • 2
    $\begingroup$ +1: so we have yet another candidate for the phenomenon of eventual counterexamples :-) $\endgroup$
    – Suvrit
    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$ 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$ 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$ 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$ Nov 14, 2013 at 16:30
15
$\begingroup$

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.

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.

http://www.numdam.org/item?id=AIF_1978__28_4_1_0

$\endgroup$
3
  • 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$
    – Suvrit
    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$ 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$
    – Suvrit
    Aug 2, 2013 at 4:22
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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