6
$\begingroup$

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).$

  • 0
    In the paper by H and R they give a number of elementary bounds before they get into their famous stuff.2012-08-19
  • 0
    Sorry, what is the "natural way" to assign a partition to a subset of $\{ 1, ... \lfloor \sqrt{n} \rfloor \}$?2012-08-19
  • 1
    @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)$2012-08-19
  • 10
    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!)2012-08-19

2 Answers 2