In this question we consider the partition function $p(n)$ - that is, the number of ways to express $n$ as a sum of positive integers.

One easy exercise is to show that $$ p(n) \geq 2^{\lfloor \sqrt{n} \rfloor}$$ for all $n > 1.$

The bound is rather stupid since one just takes a subset of $\{1,\ldots,\lfloor \sqrt{n} \rfloor \}$ and assigns to it a partition of $n$ in the natural way. So every partition is of a very specific way.

I was wondering what are some others lower bounds for $p(n)$ one could derive as an exercise using just elementary combinatorial and number theoretical facts ? What is the next bound one could try to obtain after the stated one?

This is meant just for practice otherwise one could readily use Hardy and Ramanujan’s results about the asymptotic of $p(n).$

  • $\begingroup$ In the paper by H and R they give a number of elementary bounds before they get into their famous stuff. $\endgroup$ – marty cohen Aug 19 '12 at 15:39
  • $\begingroup$ Sorry, what is the "natural way" to assign a partition to a subset of $\{ 1, ... \lfloor \sqrt{n} \rfloor \}$? $\endgroup$ – Qiaochu Yuan Aug 19 '12 at 17:00
  • 1
    $\begingroup$ @QiaochuYuan Given a subset $X = \{x_1,\ldots,x_k\}$ you assing to $X$ the partition $X = x_1+\cdots+x_k + (n - \sum_{i=1}^k x_i)$ $\endgroup$ – Jernej Aug 19 '12 at 17:14
  • 10
    $\begingroup$ Okay. Well, this lower bound is not so stupid; it already gives the correct asymptotic value of $\log p(n)$ up to a multiplicative constant. (One must not confuse a simple argument with a stupid one!) $\endgroup$ – Qiaochu Yuan Aug 19 '12 at 18:33

The argument you give generalizes to show that $$p(n) \ge (k+1)^{ \lfloor \sqrt{ n/k } \rfloor }$$

for any positive integer $k$. We repeat the same argument, but instead of subsets of $\{ 1, 2, ... \lfloor \sqrt{n} \rfloor \}$ we allow multisubsets of $\{ 1, 2, ... \lfloor \sqrt{n/k} \rfloor \}$, where each element occurs with multiplicity $0$ through $k$.

So how much better is this? The actual asymptotic value of $\log p(n)$ is known to be $\pi \sqrt{ 2n/3 }$, so $C \sqrt{n}$ where $C \approx 2.565...$. The argument you give shows that $C \ge \log 2 \approx 0.693...$. The generalization above shows that $C \ge \frac{\log (k+1)}{\sqrt{k}}$. Some numerical experimentation shows that this attains a maximum at $k = 4$, giving $C \ge \frac{\log 5}{2} \approx 0.805...$. So this is a little better, but still a long way to go.

Edit #2: Here is an argument along the above lines which gives $C \ge \sqrt{2} \approx 1.414...$. We will now allow the positive integer $k$ to occur with a multiplicity from $0$ to $m_k - 1$ for some $m_k \ge 1$. This produces a partition in the same way as above provided that the sum constraint $\sum k (m_k - 1) \le n$ is satisfied, and we get $\prod m_k$ partitions this way. A heuristic calculation using Lagrange multipliers suggests that we want $m_k$ to be proportional to $\frac{1}{k}$; we will in fact take

$$m_k = \left\lfloor \frac{m}{k} \right\rfloor$$

if $k \le t$ (and $m_k = 1$ otherwise) for some $m, t$ satisfying certain constraints. First, since we must have $m_k \ge 1$, we need $m \ge t$. Second, the sum constraint $\sum k (m_k - 1) \le n$ gives

$$mt - \frac{t(t+1)}{2} \le n.$$

We will choose $m, t$ later. First, taking the logarithm of the number of partitions gives

$$\sum_{k=1}^t \log \left\lfloor \frac{m}{k} \right\rfloor.$$

We can write this as approximately (ignoring floors now)

$$\sum_{k=1}^t (\log m - \log k) = t \log m - \sum_{k=1}^t \log k.$$

(This is an overestimate but I believe it does not affect the asymptotic.) The estimate $\log n! \approx n \log n - n + O(\log n)$ gives that this is asymptotically

$$t \left( \log \frac{m}{t} + 1 \right) + O(\log t).$$

Now to optimize $m, t$. First, we can replace the sum constraint with a constraint

$$mt - \frac{t^2}{2} \le n$$

which is easier to deal with. Taking $t = a \sqrt{n}$ gives

$$m \le \left( \frac{1}{a} + \frac{a}{2} \right) \sqrt{n}$$

so we can just take $m$ to be this value (ignoring floors again); the constraint $m \ge t$ is now equivalent to the constraint $a \le \sqrt{2}$. The logarithm of the number of partitions we get now takes the form

$$a \sqrt{n} \left( \log \left( \frac{1}{2} + \frac{1}{a^2} \right) + 1 \right) + O(\log n)$$

which gives

$$C \ge a \left( \log \left( \frac{1}{2} + \frac{1}{a^2} \right) + 1 \right).$$

Some numerical experiments suggest that the RHS is increasing for $a \le \sqrt{2}$, and taking $a = \sqrt{2}$ gives $C \ge \sqrt{2}$ as desired.

I do not think this type of argument can be pushed substantially further without some new idea.

  • $\begingroup$ Hmm. On second thought, ignoring the floors might be more dangerous than I expected. This ought to be fixable by alternately taking the floor and ceiling instead of just taking the floor, but this seems messy to write up and the argument does not get as close as I would like to the true asymptotic anyway (it would be nice if we could at least get $C \ge 2$ by reasonably elementary means). $\endgroup$ – Qiaochu Yuan Aug 19 '12 at 23:56

In the paper On elementary lower bounds for the partition function - http://www.renyi.hu/~maroti/partition.pdf‎ it is shown that $$ \frac{e^{2\sqrt{n}}}{14}<p(n) $$ for all $n\ge 1$, by elementary methods (like counting involutions in finite groups etc.).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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