Number Partitions: Euler’s Astonishing Insight

In 1740, French mathematician Philippe Naudé wrote to Leonhard Euler asking in how many ways a positive integer can be written as a sum of distinct numbers. In his investigations of this, Euler established the theory of partitions, for which he used the term partitio numerorum.

Many of Euler’s results in number theory involved divergent series. He was courageous in manipulating these but had remarkable insight and, almost invariably, his findings, although not rigorously established, were valid.

Partitions

In number theory, a partition of a positive integer ${n}$ is a way of writing ${n}$ as a sum of positive integers. The order of the summands is ignored: two sums that differ only in their order are considered the same partition.

The partition function, ${p(n)}$ , is the number of possible partitions of ${n}$ . For example, ${p(4)=5}$ since the integer ${4}$ has five partitions:

$\displaystyle 4 \,, \quad 3+1 \,, \quad 2+2 \,, \quad 2+1+1 \,, \quad 1+1+1+1 \,.$

The values of ${p(n)}$ for ${n}$ from ${1}$ to ${10}$ are

$\displaystyle 1, 2, 3, 5, 7, 11, 15, 22, 30, 42.$

A wonderful asymptotic formula for ${p(n)}$ was obtained by G. H. Hardy and Srinivasa Ramanujan in 1918:

$\displaystyle p(n) \sim \frac{1}{4n{\sqrt {3}}} \exp \left( \pi\sqrt{\frac {2n}{3}} \right) \quad\mbox{as}\quad n\rightarrow \infty \,.$

Twenty years later, a complete asymptotic expansion was presented by Hans Rademacher.

Euler’s Brilliant Reasoning

Restricted partitions satisfy some additional condition. Notable among these are distinct partitions, where each summand is different, and odd partitions, where each summand is odd. For each positive number, the number of partitions with odd parts is equal to the number of partitions with distinct parts, denoted by ${d(n)}$ . This result was proved by Leonhard Euler in 1748.

A simple trial gives the number of distinct partitions for the first 10 numbers. For example the number 6 can be expressed as

$\displaystyle 6\,,\quad 5+1\,,\quad 4+2\,,\quad 3+2+1\,.$

A recurrence relation would seem to be involved but, based on an examination of the sequence ${(1,1,2,2,2, 4,5,6, 8,10)}$ , no such relationship appears obvious.

Euler also examined another partition, into odd numbers but allowing repetitions. Thus, for the number 6 we get

$\displaystyle 5+1\,,\quad 3+3\,,\quad 3+1+1+1\,,\quad 1+1+1+1+1+1\,.$

so, again there are four possibilities. This is no coincidence, as Euler was quick to show.

Let us denote by ${d(n)}$ the number of distinct partitions of ${n}$ and by ${o(n)}$ the number of partitions in odd numbers. Euler proved that, for all ${n}$ these two quantities are equal.

Euler quickly realized that, for the question raised by Philippe Naud\'{e}, a generating function could be written down easily — that is, easily for Euler, but amazing for mere mortals — that leads to the answer. He went far beyond answering Naudé‘s question and his proof was a truly bravura performance.

Distinct Partitions

Euler saw that, if he defined an infinite power series

$\displaystyle p(x) = 1 + d(1) x + d(2) x^2 + d(1) x^3 + d(4) x^4 + \dots \,, \ \ \ \ \ (1)$

he could construct it from simple factors. He wrote down the infinite product

$\displaystyle (1 + x) (1 + x^2) (1 + x^3) (1 + x^4) \dots \,, \ \ \ \ \ (2)$

and formally multiplied all the factors to deduce the coefficient of each power of ${x}$ .

Take for example the sixth power of ${x}$ . This can be obtained as follows

Take the term ${x^6}$ from the factor ${(1+x^6)}$ and ${1}$ from all other factors.
Take the term ${x^5}$ from ${(1+x^5)}$ , ${x}$ from ${(1+x)}$ and ${1}$ from all other factors.
Take the term ${x^4}$ from ${(1+x^4)}$ , ${x^2}$ from ${(1+x^2)}$ and ${1}$ from all other factors.
Take the term ${x^3}$ from ${(1+x^3)}$ , ${x^2}$ from ${(1+x^2)}$ , ${x}$ from ${(1+x)}$ and ${1}$ otherwise.

These four choices correspond to the partitioning of 6 into distinct whole numbers, so the coefficient of ${x^6}$ is ${d(6)}$ . Clearly, this argument is general: the coefficient of ${x^n}$ is ${d(n)}$ and the infinite product (2) is equivalent to the infinite polynomial (1). Distinctiveness of the partition is guaranteed since each power of ${x}$ is found in only one factor.

Partitions in Odd Terms

Euler now introduced the infinite product

$\displaystyle q(x) = \left(\frac{1}{1-x}\right) \left(\frac{1}{1-x^3}\right) \left(\frac{1}{1-x^5}\right) \cdots \,, \ \ \ \ \ (3)$

with odd powers of ${x}$ in the denominator. Using the binomial theorem, we have

(1-x )^{-1} = 1 + (x)^1 + (x^2)^1 + (x^3)^1 + … (4)

(1-x^3)^{-1} = 1 + (x^3) + (x^3)^2 + (x^3)^3 + … (5)

(1-x^5)^{-1} = 1 + (x^5) + (x^5)^2 + (x^5)^3 + … (6)

We can multiply all the right hand sides to get ${q(x)}$ . Let us examine the coefficient of ${x^6}$ .

Pick ${x^6}$ from (4) and 1 elsewhere.
Pick ${x^5}$ from (6), ${x}$ from (1) and 1 elsewhere.
Pick ${x^3}$ from (4), ${x^3}$ from (5) and 1 elsewhere.
Pick ${x^6}$ from (5) and 1 elsewhere.

These choices correspond to the four ways of partitioning 6 into odd numbers. Formally, we can write the product as

$\displaystyle q(x) = 1 + o(1) x + o(2) x^2 + o(3) x^3 + o(4) x^4 + \dots \,. \ \ \ \ \ (4)$

Now comes Euler’s coup de grace: by multiplying ${q(x)}$ above and below by the “missing even terms”, he got

$\displaystyle q(x) = \frac{(1-x^2)(1-x^4)(1-x^6) \cdots}{(1-x)(1-x^2)(1-x^3)(1-x^4)(1-x^5) \cdots} \,.$

Then, factoring each term in the numerator and cancelling, he obtained

$\displaystyle q(x) = (1 + x) (1 + x^2) (1 + x^3) (1 + x^4) \dots \,. \ \ \ \ \ (5)$

But this is identical to the axpression (2) for ${p(x)}$ . Thus, Euler showed that the polynomials ${p(x)}$ and ${q(x)}$ are the same. So, their coefficients of each power of ${x}$ must be the same:

$\displaystyle o(n) = d(n) \,,$

or, in words, the number of partitions with odd parts is equal to the number of partitions with distinct parts.

Conclusion

Euler was able to give an immediate answer to Naudé ‘s question on the partition of numbers because he had already been studying the properties of power series. In studying the relationship between a series and a product, Euler made a momentous discovery, an identity relating a sum over all the numbers to a product over all the primes ${p}$ :

$\displaystyle \zeta(s) = \sum_{n=1}^\infty\frac{1}{n^s} = \prod_{p}\left( 1-\frac{1}{p^s}\right)^{-1} \,.$

In 1745 his old teacher Johann Bernoulli addressed him as Mathematicorum Princeps — the Prince of Mathematicians. Lagrange and Gauss were later to be honoured with this title, but Euler was the first (Shiu, 2007).

Acknowledgement

William Dunham (1994) describes Euler’s ingenuity as “simply astonishing”. This article owes much to the chapter on Euler in Dunham’s book.

Sources

${\bullet}$ Shiu, Peter, 2007: Euler’s Contribution to Number Theory. The Math. Gazette, 91, No. 522, 453-461.

${\bullet}$ Dunham, William, 1994: The Mathematical Universe. John Wiley & Sons. 314pp. ISBN: 978-0-4711-7661-9.

ThatsMaths