Read an Excerpt

Cambridge University Press
0521841186 - Integer Partitions - by George E. Andrews and Kimmo Eriksson
Excerpt

Chapter 1

Introduction

Mathematics as a human enterprise has evolved over a period of ten thousand years. Rock carvings suggest that the concepts of small counting numbers and addition were known to prehistoric cavemen. Later, the ancient Greeks invented such things as rational numbers, geometry, and the idea of mathematical proofs. Arab and Chinese mathematicians developed the handy positional system for writing numbers, as well as the foundation of algebra, counting with unknowns. From the Renaissance and onward, mathematics has evolved at an accelerating pace, including such immensely useful innovations as analytical geometry, differential calculus, logic, and set theory, until today's fruitful joint venture of mathematics and computers, each supporting the other.

We will delve into, or at least touch upon, many of these modern developments - but really, this book is about mathematical statements of a kind that would have made sense already to the cavemen! One could imagine a petroglyph or cave painting of the following kind:

The concepts involved here are just small counting numbers, equality of numbers, addition of numbers, and the distinction between odd and even numbers. What is shown in the table is that for at least up to four animals, they can be lined up in rows of odd lengths in as many ways as in rows of different lengths. Written on today's blackboard instead of prehistoric rock, the table would have a more efficient design:

The fact that there will always be as many items in the left column as in the right one was first proved by Leonhard Euler in 1748. But it is quite possible that someone observed the phenomenon earlier for small numbers, since it takes no more advanced mathematics than humans have accessed since the Stone Age. Nowadays, objects such as 3 + 1 or 5 + 5 + 3 + 2 are called integer partitions. Stating it differently, an integer partition is a way of splitting a number into integer parts. By definition, the partition stays the same however we order the parts, so we may choose the convention of listing the parts from the largest part down to the smallest.

Euler's surprising result can now be given a more precise formulation: Every number has as many integer partitions into odd parts as into distinct parts. The table continues for five and six:

EXERCISES

Statements of the flavor "every number has as many integer partitions of this sort as of that sort" are called partition identities. The above partition identity of Euler was the first, but there are many, many more. It is an intriguing fact that there are so many different and unexpected partition identities. Here is another, very famous, example: Every number has as many integer partitions into parts of size 1, 4, 6, 9, 11, 14,... as into parts of difference at least two.

The numbers 1, 4, 6, 9, 11, 14,... are best described as having last digit 1, 4, 6, or 9. Another way to put it is that when these numbers are divided by 5, the remainder is 1 or 4. Counting with remainders is called modular arithmetic and will appear several times in this book. In fact, it is striking that partition identities, their proofs and consequences, involve such a wide range of both elementary and advanced mathematics, and even modern physics. We hope that you will find integer partitions so compellingly attractive that they will lure you to learn more about these related areas too.

The last identity above was found independently by Leonard James Rogers in 1894 and Srinivasa Ramanujan in 1913. The tale of this identity is rich and has some deeply human aspects, one of which is that Rogers was a relatively unknown mathematican for a long time until the amazing prodigy Ramanujan rediscovered his results twenty years later, thereby securing eternal fame (at least among mathematicians) also for Rogers. The field of integer partitions comes with an unusually large supply of life stories and anecdotes that are romantic or astonishing, or simply funny. They are best presented, and best appreciated, in conjunction with the mathematics itself. Welcome to the wonderful world of integer partitions!

Chapter 2

Euler and beyond

In this chapter, we will show how identities such as Euler's, and many more, can be proved by the bijective method. However, although the bijective method is elegant and easy to understand, it is not the method Euler himself used. Euler worked with an analytic tool called generating functions, which is very powerful but demands a bit more mathematical proficiency. We will return to Euler's method in Chapter 5.

2.1 Set terminology

We will need some concepts from set theory. In particular, a set is a collection of distinct objects, usually called elements. We can describe a set by listing its elements within curly brackets. For example, {1, 2, 4, 5} is a set of four elements, all of which are integers. It is important to remember that the order of the elements implied by the list is not part of the set; thus the lists {4, 5, 2, 1} and {1, 2, 4, 5} describe the same set.

If you discard some elements of a set and retain the rest, you obtain a subset. The symbol ⊂ means "is a subset of." For instance, {2, 5} ⊂ {1, 2, 4, 5}.

The intersection of two sets N and N′ is the set of those elements that lie in both sets, denoted by N ∩ N′. Two sets are disjoint if they have no element in common, that is, if their intersection is empty. The union of two sets N and N′ is the set N ∪ N′ containing all elements found in any or both of these sets. Thus if N = {1, 4} and N′ = {2, 4, 5}, then their intersection is N ∩ N′ = {4} and their union is N ∪ N′ = {1, 2, 4, 5}. Intersections and unions are conveniently illustrated by so-called Venn diagrams, such as:

The number of elements in a set N is denoted by |N| and is often called the cardinality (or just the size) of the set.

EXERCISE

2.2 Bijective proofs of partition identities

In order to formulate partition identities precisely and concisely, some notation is needed. Let p(n) denote the number of integer partitions of a given number n. The function p(n) is called the partition function. For example, we have p(4) = 5, since there are five partitions of the number four:

4, 3+1, 2+2, 2+1+1 and 1+1+1+1.

In partition identities, we are often interested in the number of partitions that satisfy some condition. We denote such a number by p(n | [condition]). For example, Euler's identity takes the form

Now let us reflect a moment on how such an identity can be proved. For every single value of n, we can verify the identity by listing the partitions of both kinds, counting them, and finding the numbers to be equal. But the identity is stated for an infinite range of values of n, so we cannot verify it case by case; instead we must find some general argument that holds for each and every positive value of n. A natural idea would be to find a general way of counting the partitions, yielding an explicit expression, the same for both sides of the identity. In other words, if we could show that p(n | odd parts) equals, say, n² + 2 (or some other expression), and if we likewise could show that p(n | distinct parts) equals the same number, then we would of course have proved that the identity holds. But can we find such an expression for these functions? From the partition tables in the previous chapter, including Exercise 1, we can compute the first few values:

The tabulated values do not seem to suggest any simple function such as a polynomial in n. Consequently this approach fails to prove the identity. But we fail because we try to accomplish more than we actually need! If we want to verify that the number of objects of a type X is equal to the number of objects of a type Y, then we do not need to find the actual numbers - it is enough to pair them up and show that every object of type X is paired with a unique object of type Y and vice versa. The "cave paintings" of Chapter 1 constitute such a pairing between partitions of n into odd parts and partitions of n into distinct parts, for n = 2, 3, 4. Such a one-to-one pairing between two sets is called a bijection. Hence, in order to prove a partition identity, we just need to find a bijection between the partitions in question.

It is not obvious what a bijection between partitions could look like. An integer partition of n is just a collection of parts summing up to n, so a bijection between partitions must be described in terms of operations on parts. A simple operation is splitting an even part into two equal halves. The inverse of this operation is merging two equal parts into one part twice as large. This gives an immediate bijective proof of a partition identity:

Study how the bijection works for n = 6:

EXERCISE

2.3 A bijection for Euler's identity

Returning to Euler's identity, what must a bijection look like? It must have the property that when we feed it a collection of odd parts, it delivers a collection of distinct parts with the same sum. Its inverse must do the converse.

From odd to distinct parts: If parts are distinct, there are no two copies of the same part. Hence, if the input to the bijection contains two copies of a part, then it must do something about it. As we have seen above, a natural thing to do is to merge the two parts into one part of double size. We can repeat this procedure until all parts are distinct - since the number of parts decreases at every operation, this must occur at the latest when only one part remains. For example,

Tracing our steps back to odd parts: The inverse of merging two equal parts is the splitting of an even part into two equal halves. Repeating this procedure must eventually lead to a collection of odd parts - since the size of some parts decreases at every operation, this must occur at the latest when all parts equal one. For example,

It might seem that there is an arbitrariness in the order in which we choose to split (or merge) the parts. However, it is clear that splitting one part does not interfere with the splitting of other parts, so the order in which parts are split does not affect the result. Neither does the order of merging, since merging is the inverse of splitting.

Above, we have described a procedure of repeated merging of pairs of equal parts that we can feed any partition into odd parts, and that will result in a partition into distinct parts. Inverting every step gives a procedure of repeated splitting of even parts that takes any partition into distinct parts and results in a partition into odd parts. Hence, this procedure is a bijection proving Euler's identity. For n = 6, the bijection works as follows:

A common feeling among combinatorial mathematicians is that a simple bijective proof of an identity conveys the deepest understanding of why it is true. Test your own understanding on a few exercises!

EXERCISES

2.4 Euler pairs

The merging/splitting technique for proving Euler's identity is versatile. We can let it operate on other sets of partitions, say A and B, as long as the splitting process takes all partitions in A to partitions in B and the merging process takes all partitions in B to A.

For instance, let A be the set of partitions of n into parts of size one. The number of partitions in A is p(n | parts in {1}) = 1, since the only partition of n satisfying the condition is the sum 1 + 1 + ⋯ + 1 of n ones. The merging process will merge pairs of ones into twos, then merge pairs of twos into fours, then merge pairs of fours into eights, and so on until all parts are distinct. Consequently, the corresponding set B must be the set of partitions of n into distinct parts in {1, 2, 4, 8, ...} (powers of two). Now we must check that the splitting process will take every partition in B to A. Clearly any power of two (say 2^k) is split into a pair of powers of two (2^k-1 + 2^k-1). Since the only power of two that is odd is 2⁰ = 1, the process will go on until all remaining parts are ones.

Hence, we have a bijection that proves that for any n ≥ 1,

And since the left-hand expression has the value one, we have proved that every positive integer has a unique partition into distinct powers of two. This is called the binary representation of integers. For example,

where (b_kb_k-1... b₀)₂ is the number written with binary digits (bits). This is the common mode for computers to store numbers in memory.