University of Toronto
Faculty of Arts and Sciences
MAT315H1 - S: Introduction to Number Theory
Winter 2023
Homework 9
1 Problems to be submitted
Make sure you follow all the indications as stated in the syllabus.
• In this homework we begin studying the last topic of the course: Partition Theory.
This theory is one among many subareas of number theory under the realm of additive number
theory, which is the area of number theory that studies the integers under addition.
In particular, partition theory studies the properties of partitions, which are the different ways
to write up a number as sum of positive integers. In the course we will mainly focus on how to
count them.
The main theorem for us will be the Pentagonal Number Theorem of Euler.
• The properties of partitions are incredibly diverse and all areas of mathematics come together
into this one topic to give spectacular results.
In particular, in order to count the number of partitions we will study the idea of generating
functions. Problem 1 and 2 of this homework work with this idea and how to use it so that you
familiarize with it. We will also study it in the course!
The role of generating functions is similar to the role the sums did in the previous homework:
it is an object that organizes and does the computations for us.
• Hidden in all of this theory is a jewel of mathematics: Ramanujan’s τ function. It codifies the
coefficients of a generating function which happens to be a cuspidal modular form (whatever
that is, we will not go into that in the course) and as such it opened the world of mathematics
to the study of these fundamental objects, which were (and continue to be) some of the most
important and fascinating objects in mathematics. (Their role cannot be underestimated. As
an example, they played a pivotal role in the proof of Fermat’s Last Theorem in 1994.)
Thus it can be said that the discovery of this τ function of Ramanujan marks one of the division
points between classical number theory and modern number theory!
1. (a) (3 points) There are 11 partitions of n = 6. Find them all and draw their Ferrer Diagrams next to
it.
(b) (2 points) For each of the 11 partitions you found in the first part, find its conjugate partition.
(c) (2 points) Prove that the number of partitions of n with three parts is the same as the same as the
number of partitions of n in which all parts are smaller or equal to three.
Hint: Use Ferrer Diagrams.
1
(d) (2 points) Prove that the number of partitions of n in which no part is a multiple of 3 is the same
as the number of partitions of n in which each part appears at most twice.
Hint: Use generating functions.
(e) (1 point) Using the partitions you found for n = 6, write all the partitions of each type that appears
in the previous two parts and verify indeed they are the same in quantity as stated in (c) and (d).
2. In this problem we see an example of the uses of generating functions in the theory of partitions. We
will use it to study partitions with certain property given by their Durfee Square and Durfee Rank.
The Durfee rank of a partition λ is the biggest positive integer m such that there are at least m parts
of λ of size at least m.
For example, for the partition 5+4+4+3+2+1 the Durfee rank is 3. This is because there are at least
three parts (i.e. 5, 4, 4, 3) of size at least 3, but there are not at least 4 parts of size at least 4 (there are
only three of those parts, 5, 4, 4).
In a Ferrers Diagram the biggest square, formed from the dots of the diagram, that can be drawn from
the upper left corner is called its Durfee square. See part (c) below for an example.
(a) (2 points) Make a drawing of all the Ferrer Diagrams of the partitions of 7 (there are 15 of them)
grouped by the size of its Durfee square. For all of these partitions, also compute its Durfee rank.
(b) (2 points) Prove that the Durfee rank of a partition is equal to the size of the length (measured in
dots) of its Durfee Square.
Hint: This is easy if you interpret the phrase there are at least m parts of size at least m geomet-
rically in the Durfee Square.
(c) (3 points) Let λ be a partition of n of Durfee rank k. To the right of the Durfee square there is a
partition λR of some integer and below of the Durfee square there is a partition λB of some integer.
For example, for the partition 5 + 4 + 4 + 3 + 2 + 1, its Ferrers Diagram is
In the above case: the Durfee Square is green so k = 3. The partition λR on the right is 2 + 1 + 1
and is a partition of 4 (colored red). The partition below λB is the partition 3 + 2 + 1 and is a
partition of 6 (colored blue).
Prove that λR is a partition with at most k parts and λB is a partition whose parts are all at most
k.
(d) (2 points) Let k be a positive integer. Using a Ferrers Diagram argument, prove that the number
of partitions of n with at most k parts is the same as the same as the number of partitions of n in
which all terms are smaller or equal to k.
Hint: You already did this in problem 1 for k = 3.
(e) (3 points) Justify that the generating function for the number of partitions of n in which all parts
are smaller or equal to k is
k∏
i=1
1
(1−Xi)
Page 2
(f) (6 points) For a fixed positive integer k, define by Dk(n) the number of partitions of n of Durfee
rank k (or equivalently, whose Durfee Square has side-length k). For this sequence, consider its
generating function
Dk(X) = Dk(0) +Dk(1)X +Dk(2)X
2 +Dk(3)X
3 + · · ·
Prove that
Dk(X) = X
k2
k∏
i=1
1
(1−Xi)2
Hint: To do this, invert the process of the previous part. Pick a possible λR and a possible λB , and
complete the Ferrers Diagram by putting the appropriate square. What is the generating function
of λB and λR?
(g) (2 points) Use this generating function to obtain the number of partitions of 15 with Durfee rank
3. Write all of these partitions down.
Hint: To generate the partitions remember what you did in part (d). It is like gluing pieces of a
puzzle!
This is easy if you pay attention to what the generating function is telling you. It is really cumber-
some if you search without any organiation since 15 has a total of 176 partitions!