# Partition Function : Some Properties & A New Bound on p(n)

Sarbajit Mazumdar, Jyotishka Ray Choudhury

► To cite this version:

Sarbajit Mazumdar, Jyotishka Ray Choudhury. Partition Function : Some Properties & A New Bound on p(n). 2018. hal-01815249

HAL Id: hal-01815249

https://hal.science/hal-01815249

Preprint submitted on 13 Jun 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Partition Function : Some Properties & A
New Bound on $p(n)$

Sarbajit Mazumdar & Jyotishka Ray Choudhury

December 2017 - June 2018

West Bengal, India

## Abstract

This small project comprises of some introductory properties and topics of the *partition function* $p(n)$. Actually in this project, we have tried to show a new bound on the partition function and some simplified proofs of various properties of the same. In **section 6** we give a simplified proof of **MacMahon's Identity's** using **Euler's Partition Theorem** and in **Section 7**, we have shown an upper bound on $p(n)$ with the help of simple algebra and basic properties of inequality. In **section 8**, we have shown a **lower bound** using the basics of **Dilogarithm** and **Hurwitz Zeta function**.

## 1 Introduction

We start by defining partitions in a few simple words.

A *Partition of a positive integer* $n$ is a way of writing that integer as a sum of positive integers, where the order of the summands is considered to be irrelevant. For example, the positive integer 4 can be partitioned in exactly 5 different ways: $4, (3+1), (2+2), (2+1+1), (1+1+1+1)$.

## 2 Definition

In this section, we'll define 'Partition' again formally. A *Partition of a positive integer* $n$ is a way of writing that integer as a sum of positive integers, where the order of the summands is considered to be irrelevant. The *Partition Function* signifies the total number of partitions of a positive integer.

The partition function of a positive integer $n$ is denoted by $p(n)$. So, by simple calculations, we can find that $p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11$ and $p(7) = 11$. It is to be noted that $p(0)$ is considered to be 1 conventionally though it is not a positive integer.

Throughout this article, we'll denote the number of summands in any particular partition of an integer by the term "length of partition".
There are also some formal notations which, we think, should be mentioned as we'll use these notations in our article later.

$p_m(n)$: The number of partitions of $n$ of length no longer than $m$

$p^o(n)$: The number of partitions of $n$ into odd parts

$p^d(n)$: The number of partitions of $n$ into distinct parts

$q^e(n)$: The number of partitions of $n$ into an even number of distinct parts

$q^o(n)$: The number of partitions of $n$ into an odd number of distinct parts We'll follow the conventions that $p_m(0) = p^o(0) = p^d(0) = q^e(n) = 1$ and $q^o(0) = 0$.

# 3 Some Quick Facts and Observations

The partition function is considered as one of the toughest number-theoretic functions. The interesting thing about this is that the number of partitions of first few positive integers can be easily calculated, but as the value of $n$ increases, the partition function grows very rapidly and soon, it becomes impossible to compute easily. From the early beginning of Mathematics (especially, number theory), no mathematician could find out a precise formula for $p(n)$. In the eighteenth century, Leonhard Euler found a generating function for $p(n)$. In 1918, Srinivasa Ramanujan, the great Indian mathematician, came up with a formula for approximating the value of $p(n)$, which is considered as a major breakthrough in number theory. Ramanujan expressed the formula as

$$p(n) \approx \frac{e^{c\sqrt{n}}}{4n\sqrt{3}}$$

where $e$ = Euler's Number and the constant $c = \pi\sqrt{\frac{2}{3}}$.

There are many other ways to define $p(n)$ as generating functions.

# 4 Generating Functions of $p(n)$

Generating functions can be used to deal with some problems involving partitions. Here we derive the generating function for the number of partitions of a positive integer $n$.

Consider partitioning $n$ into addends that are equal to 1. The generating function for this is $1 \cdot x^0 + 1 \cdot x + 1 \cdot x^2 + \dots$ since there is only one way to represent $n$ as the sum of 1's.

Consider partitioning numbers using just 2's as summands. There is one way to partition 0 into 2's, zero ways to partition 1 into 2's, one way to partition 2 into 2's, and so forth. Therefore, the generating function for this type of partition is $1 + x^2 + x^4 + \dots$.

We can proceed in this manner to find that the generating function for the number of ways to partition $n$ into addends equal to $k$ is $1 + x^k + x^{2k} + x^{3k} + \dots$.

Now, we generate every partition of $n$ by choosing some number of parts to be equal to 1, some other number of parts to be equal to 2, and so on. Thus, we get the generating function for the partition function of $n$ by multiplying the generating functions for
partitions into just 1's, partitions into just 2's, and so on. This gives us the expression

$$ (1 + x + x^2 + \cdots + x^n)(1 + x^2 + x^4 + \cdots + x^{2n})(1 + x^3 + x^6 + \cdots + x^{3n}) \cdots = 1 + \sum_{n=1}^{\infty} p(n) x^n $$

Using the formula for the sum of an infinite geometric sequence we can express this in the more compact form

$$ 1 + \sum_{n=1}^{\infty} p(n) x^n = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^3} \cdots = \prod_{n \ge 1} \frac{1}{1-x^n} $$

# 5 Theorems and Corollaries

Here we have submitted some theorems and corollaries:

(1) The number of partitions of $n$ in which the part 1 consists minimum $j$ times is $p(n-j)$.

**Proof:** Suppose we take a partition of $n$ now if the particular partition contains at least one 1 in the summand then we just pulled it into the right hand side and we find a completely different partition of $(n-1)$ and now similarly, if there exist at least two 1's in a partition of $n$ the we just pulled it into the right hand side then we find a completely different partition of $(n-2)$ and inductively, if there is $j$ 1's then $(n-j)$ gives us a completely different partition. So we can conclude that this process only valid for those partitions in which at least one 1 occurs otherwise there is a chance of repetition and over counting. So by inductively we can conclude that the number of 1's in the partitions of $n$ is $p(n-j)$. An example clears it completely. Suppose $p(5) := 5, 4+1, 2+2+1, 3+2, 3+1+1, 1+1+1+1+1, 2+1+1+1+1$ now if we take any partition of 5 which at least contains one 1 is $p(4) = 5$ because we simply pulled one 1 from every partition of 5 which consists at least one 1 and we get 5 distinct partitions which is actually $p(5-1) = p(4) = 5$

(2) The number of partitions of $n$ in which 1 doesn't occur as a summand is $F(n)$. Then we have $F(n) = p(n) - p(n-1)$.

**Proof:** After proving (1) this is very easy to show. the number of partitions of $n$ in which 1 occur at least one time is $p(n-1)$ so the rest i.e. $p(n) - p(n-1)$ is the number of partitions in which 1 does not occur as a summand.

(3) Show that the number of partitions of a number into parts which have at most one of each distinct even parts (e.g. $1+1+1+2+3+4$) equals the number of partitions of the number in which each part can appear at most three times (e.g. $1+1+1+2+2+4+4+4$).

**Proof:** We'll consider the two given statements as two distinct cases and by using generating functions, we'll show that the two statements are actually equivalent.

**First Case:** The first statement says that 2, 4, 6, ... can appear in the partitions either 0 or 1 time. So, the contributing factors of the even numbers are

$$ 2 \to 1 + x^2 $$
$$4 \rightarrow 1 + x^4$$

For the odd integers, there are no certain bounds. So, the contributing factors of the odd integers are

$$1 \rightarrow 1 + x + x^2 + x^3 + \dots = \frac{1}{1-x}$$ $$3 \rightarrow 1 + x^3 + x^6 + x^9 + \dots = \frac{1}{1-x^3}$$

So, the combined contributing factor is

$$\frac{(1+x^2)(1+x^4)(1+x^6)\dots}{(1-x)(1-x^3)(1-x^5)\dots}$$

**Second Case:** According to the second statement, the summands can be used at most 3 times in each partition, so the contributing factors in the generating function are

$$1 \rightarrow 1 + x + x^2 + x^3 = \frac{1-x^4}{1-x}$$ $$2 \rightarrow 1 + x^2 + x^4 + x^6 = \frac{1-x^8}{1-x^2}$$ $$3 \rightarrow 1 + x^3 + x^6 + x^9 = \frac{1-x^{12}}{1-x^3}$$

Hence, the combined contributing factor is

$$\frac{(1-x^4)(1-x^8)(1-x^{12})\dots}{(1-x)(1-x^2)(1-x^3)\dots} = \frac{1}{(1-x)(1-x^3)\dots} \cdot \frac{1-x^4}{1-x^2} \cdot \frac{1-x^8}{1-x^4}\dots = \frac{(1+x^2)(1+x^4)(1+x^6)(1+x^8)\dots\dots}{(1-x)(1-x^3)(1-x^5)(1-x^7)\dots\dots}$$

Observe that, the resulting generating functions in both cases are equal.

Thus, we conclude that both the statements are equivalent, i.e. the number of partitions of a number into parts which have at most one of each distinct even parts equals the number of partitions of the number in which each part can appear at most three times.

(4) For every positive integer $n \ge 1$, prove that $p^o(n) = p^d(n)$.

**Proof:** This problem can be solved by logical reasoning, which is a bit complicated. So, we'll use generating functions to kill the problem.
To find the generating function for $p^o(n)$, we calculated the contributing factors of each of the odd numbers and then multiply them. We have,

$$1 \rightarrow 1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}$$

$$3 \rightarrow 1 + x^3 + x^6 + x^9 + \cdots = \frac{1}{1-x^3}$$

$$5 \rightarrow 1 + x^5 + x^{10} + x^{15} + \cdots = \frac{1}{1-x^5}$$

Therefore, the combined generating function for $p^o(n)$ is

$$\frac{1}{(1-x)(1-x^3)(1-x^5)\cdots}$$

In case of $p^d(n)$, the distinct summands can be used in any partition of $n$ exactly 0 or 1 time. So, their contributing factors are

$$1 \rightarrow 1 + x$$

$$2 \rightarrow 1 + x^2$$

$$3 \rightarrow 1 + x^3$$

$$4 \rightarrow 1 + x^4$$

So, their combined contributing factor is

$$(1+x)(1+x^2)(1+x^3)(1+x^4)\cdots$$

$$= \frac{(1-x^2)(1-x^4)(1-x^6)\cdots}{(1-x)(1-x^2)(1-x^3)(1-x^4)\cdots}$$

Notice that, the numerator consists of the numbers of the form $(1 - x^{2f})$ and the denominator contains the numbers of the form $(1 - x^f)$, where $f \in \mathbb{N}$. So, the numbers in the numerator and the numbers of the form $(1 - x^{2f})$ in the denominator gets cancelled out. So, the final outcome is

$$\frac{1}{(1-x)(1-x^3)(1-x^5)\cdots}$$

which is identical to the generating function of $p^o(n)$.

Hence, it is proved that $p^o(n) = p^d(n)$.

(5) Prove that for every positive integer $n$ the number of ways to write $n$ as the sum of ordered pairs is $2^{n-1}$.

**Proof:** Let us consider an ordered sum

$$a_1 + a_2 + \cdots + a_k = n$$
where $a_i \ge 1$ which is represented by $n$ 1's in a row separated by $(k-1)$ “strokes” /

$$ \underbrace{11\cdots1}_{a_1} / \underbrace{11\cdots1}_{a_2} / \underbrace{11\cdots1}_{a_3} / \cdots / \underbrace{11\cdots1}_{a_k} $$

To obtain all such displays ($\forall 1 \le k \le n$), line up $n$ 1's and for each $n$ spaces between adjacent pairs, either put a stroke or do not put in a stroke. and this can be done $2*(2*(2*\cdots*2)) = 2^{n-1}$ ways.

$$ \underbrace{(n-1)\text{times}} $$

# 6 Formal Power Series and Euler's Identity

(1) Euler's Identity: For any positive integer $n$,

$$ \prod_{n=1}^{\infty} (1 - x^n) = 1 + \sum_{j=1}^{\infty} (-1)^j \left( x^{\frac{3j^2+j}{2}} + x^{\frac{3j^2-j}{2}} \right) $$

From this theorem, we can easily derive an useful identity which is known as **MacMachon's Identity** which is as follows.

$$ p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - \cdots \infty $$

Here we submit a rigorous proof of this identity by using **Euler's Partition Theorem**.

**Proof:** We know that

$$ p(n) = \sum_{k=1}^{\infty} p(k) \cdot x^k = \prod_{k \ge 1} \frac{1}{1 - x^k} $$

Now, the left hand side of Euler's formula is

$$ \prod_{k=1}^{\infty} \frac{1}{1-x^k} = \frac{1}{\prod_{k=1}^{\infty} (1-x^k)} = \frac{1}{p(n)} $$

So, according to the formula of Euler the identity reforms into

$$ \left\{ 1 + \sum_{j=1}^{\infty} (-1)^j \left( x^{\frac{3j^2+j}{2}} + x^{\frac{3j^2-j}{2}} \right) \right\} \left\{ \sum_{k=1}^{\infty} p(k) \cdot x^k \right\} = 1 $$

Now, if we expand the summation of the 1st bracket, we get the following

$$ (1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \cdots \infty) \left\{ \sum_{k=1}^{\infty} p(k) \cdot x^k \right\} = 1 $$

Now, equating co efficient of $x^n$ on both side, we get in L.H.S.,

$$ p(n) - p(n-1) - p(n-2) + p(n-5) + p(n-7) - p(n-12) - p(n-15) + \cdots \infty = 0 $$

And thus

$$ p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - \cdots \infty $$

Q.E.D.
# 7 An Upper Bound on $p(n)$

Here we give a crude bound for $p(n)$ which involves exponential functions. Here we submit a simple algebraic proof of the upper bound of $p(n)$.

**Claim:** If $n \ge 1$, then we have $p(n) < e^{\frac{2n\pi}{\sqrt{6n}}}$

**Proof:** Let

$$f(x) := \prod_{k \ge 1} \frac{1}{1 - x^k} = 1 + \sum_{k=1}^{\infty} p(k) \cdot x^k$$

and here $0 < x < 1$. Then we have $p(n) \cdot x^n < f(x)$ by taking logarithm in both sides, we get

$$\log_e f(x) > \log_e p(n) + n \log_e x$$

which is equivalent to

$$\log_e p(n) < \log_e f(x) + n \log_e \frac{1}{x}$$

Now,

$$\log_e f(x) = \log_e \prod_{k \ge 1}^{\infty} \frac{1}{1 - x^k} = \sum_{k=1}^{\infty} \log_e \frac{1}{1 - x^k} = - \sum_{k=1}^{\infty} \log_e (1 - x^k)$$

$$\text{Now, for } 0 < x < 1, \quad \log_e(1-x^k) = -\sum_{m=1}^{\infty} \frac{(x^k)^m}{k} = -\sum_{m=1}^{\infty} \frac{x^{mk}}{k}$$

Now, putting the value of the summation, we get

$$\log_e f(x) = - \sum_{k=1}^{\infty} \log_e (1-x^k) = \sum_{k=1}^{\infty} \sum_{m=1}^{\infty} \frac{x^{mk}}{m} = \sum_{m=1}^{\infty} \sum_{k=1}^{\infty} \frac{x^{mk}}{m} = \sum_{m=1}^{\infty} \frac{1}{m} \sum_{k=1}^{\infty} x^{mk}$$

Therefore, we obtain

$$\log_e f(x) = \sum_{m=1}^{\infty} \frac{x^m}{m(1-x^m)} \cdots (1)$$

We know that,

$$\frac{1-x^m}{1-x} = 1 + x + x^2 + x^3 + \cdots$$

For $0 < x < 1$ and $m > 1$,

$$1 > x^{m-1}$$

$$x > x^{m-1}$$

∴

$$x^{m-2} > x^{m-1}$$

Adding all these and adding $x^{m-1}$ on both sides, we get

$$\frac{1-x^m}{1-x} > mx^{m-1}$$
and now a trivial inequality is

$$m > \frac{1-x^m}{1-x} > mx^{m-1}$$

which leads to

$$\frac{m(1-x)}{x^m} > \frac{1-x^m}{x^m} > \frac{mx^{m-1}}{x^m} \\ \Rightarrow \frac{m(1-x)}{x^m} > \frac{1-x^m}{x^m} > \frac{m(1-x)}{x}$$

now reversing the inequality we get...

$$\frac{x^m}{m(1-x)} < \frac{x^m}{1-x^m} < \frac{x}{m(1-x)}$$

now multiplying $\frac{1}{m}$ to both sides we get...

$$\frac{x^m}{m^2(1-x)} < \frac{x^m}{m(1-x^m)} < \frac{x}{m^2(1-x)}$$

now taking summation and using right hand side of our inequality we get..

$$\sum_{m=1}^{\infty} \frac{x^m}{m(1-x^m)} < \sum_{m=1}^{\infty} \frac{x}{m^2(1-x)}$$

From (1) we can obtain..

$$\log_e f(x) = \sum_{m=1}^{\infty} \frac{x}{m^2(1-x)}$$

now the right hand side has a closed result..

$$\log_e f(x) = \frac{\pi^2}{6} \cdot \frac{x}{1-x}$$

now let's take $\frac{x}{1-x} = \frac{1}{r}$ which gives us for $r > 0$

$$\log_e (1+r) < r$$

which implies..

$$n \log_e \frac{1}{x} < nr$$

now at the very first beginning of this section we have written a inequality that

$$\log_e p(n) < \log_e f(x) + n \log_e \frac{1}{x}$$

Putting value on this we get

$$\log_e p(n) < \frac{\pi^2}{6r} + nr$$
and the function attains maximum when

$$ \frac{\pi^2}{6r} = nr $$

which gives us

$$ r = \frac{\pi}{\sqrt{6n}} $$

So..

$$ \log_e p(n) < \frac{\pi^2}{6r} + nr < \frac{\pi^2}{6\frac{\pi}{\sqrt{6n}}} + n\frac{\pi}{\sqrt{6n}} = \frac{2n\pi}{\sqrt{6n}} $$

which gives us a clear upper bound for $p(n)$ i.e.

$$ p(n) < e^{\frac{2n\pi}{\sqrt{6n}}} $$

# 8 An Lower Bound on $p(n)$

For a simplified lower bound of $p(n)$ we can follow the right hand side of our inequality.. i.e.

$$ \log_e f(x) = \sum_{m=1}^{\infty} \frac{x^m}{m^2 \cdot (1-x)} $$

which gives us that

$$ \log_e p(n) > \log_e f(x) = \frac{1}{1-x} \sum_{m=1}^{\infty} \frac{x^m}{m^2} > \sum_{m=1}^{\infty} \frac{x^m}{m^2} = Li_2(x) $$

where $Li_2(x)$ is In mathematics, Spence's function, or dilogarithm,

$$ \mathrm{Li}_2(z) = - \int_0^z \frac{\ln(1-u)}{u} du, \quad z \in \mathbb{C} $$

A special approximation of Dilog can be got by Hurwitz zeta function defined as

$$ \zeta(s, q) = \sum_{n=0}^{\infty} \frac{1}{(q + n)^s} $$

where it is formally defined for complex arguments $s$ with $\mathrm{Re}(s) > 1$ and $q$ with $\mathrm{Re}(q) > 0$. as compared to the Dilog, Hurwitz calculated that

$$ \mathrm{Li}_s(z) > \frac{(2\pi)^{\frac{1}{s}}}{\Gamma(\frac{1}{s})} \zeta\left(1-s, \frac{1}{2} - \frac{\ln(-1/z)}{2\pi i}\right) > \frac{(2\pi)^{\frac{1}{s}}}{\Gamma(\frac{1}{s})} \zeta(1+s) $$

Simplifying it by $s = 2$ and $z = x + i \cdot 0$, we get

$$ \log_e p(n) > \mathrm{Li}_2(x) > \frac{\sqrt{2\pi n}}{\Gamma(\frac{1}{2})} \cdot \zeta(3) $$
as $\Gamma(\frac{1}{2})$ is $\sqrt{\pi}$ we get

$$p(n) > e^{\frac{\sqrt{2\pi n} \cdot \zeta(3)}{\sqrt{\pi}}}$$

By simplifying more we get

$$p(n) > e^{\sqrt{2n} \cdot \zeta(3)}$$

$\zeta(3)$ is **Apery's Constant**.

# 9 The Final Result

Hence we conclude that

$$e^{\frac{2n\pi}{\sqrt{6n}}} > p(n) > e^{\sqrt{2n} \cdot \zeta(3)}$$