DIVISIBILITY AND DISTRIBUTION OF PARTITIONS INTO DISTINCTPARTSJEREMY LOVEJOY
Abstract. We study the generating function for Q(n), the number of partitions of a natural
number n into distinct parts. Using the arithmetic properties of Fourier coefficients of integer
weight modular forms, we prove several theorems on the divisibility and distribution of Q(n)modulo primes p ≥ 5.

1. Introduction
A partition of n into distinct parts is a decreasing sequence of positive integers whose sumis n. The number of such partitions of n is denoted by Q(n), and it is an easy combinatorial
exercise [2] to determine the generating function for Q(n)∞∞XYnQ(n)q =(1 + q n ) = 1 + q + q 2 + 2q 3 + 2q 4 + 3q 5 + ...
(1)
n=0

n=1

A problem that naturally arises in the study of a combinatorial function such as Q(n) is that ofdivisibility and distribution. Given a natural number M , describe the behavior of Q(n) modulo
M . In the absence of any combinatorial intuition, the naive assumption is that such a function israndomly distributed among the congruence classes modulo M , although this is not necessarily
the case. For example, Gordon and Ono [5] have shown that almost all of the values of Q(n)are divisible by 2k for any natural number k. Except in a few cases [1], it seems hopelessthat combinatorial arguments will settle these problems in general, and so we must turn to theanalysis of generating functions.
Using an asymptotic formula for Q(n) derived using the Hardy - Ramanujan - Rademacher
circle method, Rickert [12] has shown that the number of primes p < X which divide some valueof Q(n) is À log log X. Since the number of primes p < X is asymptotically X/log X, thisis a sparse subset of the prime numbers. Moreover, Rickert’s theorem does not preclude thepossibility that every prime p dividing Q(n) does so only once. Using the theory of modularforms, we will establish the following:
Theorem 1. For any prime number p ≥ 5,1#{n < N : Q(n) ≡ 0 (mod p)}≥(2)
lim inf
N →∞NpSince the discovery by Ramanujan of congruences in arithmetic progressions for the ordinary
partition function, there has been extensive interest in such congruences for combinatorial functions. For partitions into distinct parts, Gordon and Hughes [4] established congruences of theDate: January 21, 2004.
1991 Mathematics Subject Classification. Primary 11P83; Secondary 05A17.
1

2JEREMY LOVEJOY

Ramanujan type modulo powers of 5 and 7 using methods based on Atkin’s work on the classicalpartition function p(n). Here we use a decidedly different technique to demonstrate
Theorem 2. For any prime p ≥ 5, there are infinitely many distinct arithmetic progressions
an + b such that for all nonnegative integers nQ(an + b) ≡ 0 (mod p)(3)

It turns out that the values of a guaranteed by Theorem 2 are typically quite large, and in §4
we present a few of the simplest such congruences. These extracombinatorial congruences arise
from an inherent regularity of the generating function rather than some combinatorial propertyof partitions with distinct parts.
In the 1960’s Newman [9] made a famous conjecture about the distribution of the ordinary
partition function p(n) modulo M . He predicted that for any r there will be infinitely manyn such that p(n) ≡ r (mod M ). Although this question remains open, Ono [10] has founda computational technique for verifying that a given prime larger than 5 satisfies Newman’s
conjecture, and subsequently the conjecture has been proven for all primes M below 1000. In
the case of partitions into distinct parts, Ono and Penniston [11] have shown that the answer
to Newman’s question is affirmative if M is any power of 2. We consider Q(n) modulo primesp ≥ 5 and prove the following
Theorem 3. Let p ≥ 5 be prime. Suppose there is one n0 ≡ −24−1 (mod p) such that p - Q(n0 ).
Then(Nif r ≡ 0 (mod p)#{n < N : Q(n) ≡ r (mod p)} ÀpNif r 6≡ 0 (mod p)log NMoreover, if such an n0 exists then n0 ≤ 32p(p − 1).
2. Preliminaries
In many instances the generating functions for combinatorial objects turn out to be closely
related to modular
particularly to products of η functions (Recall that η(z) := q 1/24 (q; q)∞
Qforms,∞where (q; q)∞ := n=1 (1 − q n ) and q := e2πiz ). For this reason, we often make use the following
fact recorded in [3, 7, 8]:Theorem 4 (Gordon, Hughes, Ligozat, Newman). Let
Yf (z) =η rδ (δz)
1≤δ|N

be a product of η functions which satisfies the following criteria(i )Xδrδ ≡ 0 (mod 24)
δ|N(ii )XN
δ|Nδrδ ≡ 0 (mod 24)

3(iii )X(iv ) For each d|N ,rδ ∈ 2Z+

X (gcd(d, δ))2 rδ
δ|NThen, f (z) ∈ Mk (Γ0 (N ), χ) where k = 12

δ≥0Prδ andQµ¶(−1)k δ rδχ(`) =.
`Here Mk (Γ0 (N ), χ) is the finite dimensional C - vector space of holomorphic modular forms ofweight k, level N , and character χ. The condition (iv) ensures that f has nonnegative orders atthe cusps. If f actually has positive orders at all cusps, then it is a cusp form, and we denote thecorresponding space of cusp forms by Sk (Γ0 (N ), χ). We use the notation Mk (Γ0 (N ), χ)m andSk (Γ0 (N ), χ)m to denote the same spaces except the coefficients in the Fourier expansions of therelevant forms with integer coefficients are reduced modulo m. Before proving a key theorem,
we record some useful facts about modular forms and their Fourier coefficients, and refer theinterested reader to [6] for a more detailed overview of modular forms.
PnProposition 5. Suppose that f (z) = ∞n=0 a(n)q is a modular form in Mk (Γ0 (N ), χ).
(i) For any positive integer t,
f (tz) =∞Xa(n)q tn

n=0

is the Fourier expansion of a modular form in Mk (Γ0 (tN ), χ)(ii) For any prime p,∞ ³´Xf (z) | T (p) :=a(pn) + χ(p)pk−1 a(n/p) q nn=0

is the Fourier expansion of a modular form in Mk (Γ0 (N ), χ)
Moreover, both statements remain true if Mk (Γ0 (N ), χ) is replaced by Sk (Γ0 (N ), χ).
The operator T (p) is the Hecke operator for the prime p. Notice that modulo p, f (z) | T (p) ≡f (z) | U (p) on Mk (Γ0 (N ), χ)p , where the operator U (p) acts on series expansions by∞XXa(n)q n | U (p) :=n=0n≡0na(n)q p(mod p)

The following useful criterion allows us to check congruences for modular forms with a finitecomputation.
PnProposition 6 (Sturm). Suppose f (z) = ∞n=0 a(n)q ∈ Mk (Γ0 (N ), χ) satisfies(i ) a(n) ∈ Z for all nQ
1(ii ) a(n) ≡ 0 (mod m) for all n ≤ 1 + kN
p|N (1 + p )12Then, a(n) ≡ 0 (mod m) for all n.

4JEREMY LOVEJOYPn
We wish to study the function ∞n=0 Q(n)q in the context of modular forms, but unfortunately this is almost certainly not the Fourier expansion of a modular form modulo any prime
p 6= 2. However, for primes p ≥ 5, it turns out that for a properly chosen function hp (n),∞XQ((hp (n))q nn=0

is the Fourier expansion of a cusp form modulo p. This is the content of Theorem 8, whose
proof depends on the following observation.
Lemma 7. If f (z) is a cusp form in Sk (Γ0 (2)), theng(z) :=f (z)η 8 (z)η 8 (2z)is a holomorphic modular form in Mk−8 (Γ0 (2))
Proof: By Theorem 4, η 8 (z)η 8 (2z) is a cusp form of weight 8 and level 2 and has the minimalorder of vanishing of 1 at the two cusps of Γ0 (2). Also, η 8 (z)η 8 (2z) can have no zeroes in theupper half plane. Therefore,f (z)η 8 (z)η 8 (2z)is a modular function which is holomorphic for Im z > 0 and has nonnegative orders at thecusps. That is, g(z) is in Mk−8 (Γ0 (2), χ).
¤¡2¢
Theorem 8. Let p ≥ 5 be prime and let χ be the quadratic character defined by χ(d) = d .
Then,µ¶∞X
pn − 1 nFp (z) :=Q
q ∈ S4(p−1) (Γ0 (1152), χ)p24
n=0

Proof : For a prime p ≥ 5, leta := 16 − (p mod 24)
b := (p mod 24) − 8
andfp (z) :=η(2z) aη (2pz)η b (pz).
η(z)

Using Theorem 4 we can check that
η pa+1 (2z)η pb−1 (z) ∈ S4p (Γ0 (2))
and therefore
fp (z) | U (p) ≡p fp (z) | T (p) ∈ S4p (Γ0 (2))pBy Lemma 7,fp (z) | U (p) ≡ η 8 (z)η 8 (2z)gp (z)(mod p)5where gp (z) ∈ M4p−8 (Γ0 (2)). To prove the theorem we will write fp (z) | U (p) (mod p) in asecond way.
η(2z) aη (2pz)η b (pz) | U (p)
η(z)
! ∞
Ã∞
YX
p(2a+b)+1a=Q(n)q n+ 24| U (p)(1 − q 2n ) (1 − q n )bfp (z) | U (p) =n=0n=1

Therefore,XnQ(n)q p+p(2a+b)+124p=Q∞

n=1 (1 − q≡ q
and soX

fp (z) | U (p)(2a+b)
242n )a (1 − q n )b

η 8−a (2z)η 8−b (z)gp (z) (mod p)

24n+1Q(n)q 24p ≡ η 8−a (2z)η 8−b (z)gp (z) (mod p)(4)

One can verify using Theorem 4 thatη 8−a (48z)η 8−b (24z) ∈ S4 (Γ0 (1152), χ)and so replacing q by q 24 in (4) gives the result.

¤Remark 9. Let
σp = −24−1 (mod p)
rp = p (mod 24)
Then we also have the following representation for Fp (z):Fp (z) =∞XQ (pn + σp ) q 24n+rp .

n=0

3. Divisibility and Distribution of Q(n)Theorem 8 reveals that for any prime p ≥ 5 certain values of Q(n) are actually Fourier
coefficients modulo p of modular forms. The role of modular forms in number theory is deepand detailed, and in particular there have been many observations on the arithmetic propertiesof their Fourier coefficients. Theorem 1 is now an immediate corollary of the following result ofSerre [13]:Theorem 10. Suppose thatf (z) =∞Xa(n)q nn=0

is an integral weight holomorphic modular form with integer coefficients. For any positive integers m and N , let δm (N ) denote the proportion of n ≤ N for which a(n) ≡ 0 (mod m).
Thenlim δm (N ) = 1
N →∞6JEREMY LOVEJOY

Although Theorem 10 makes it clear that Q(n) is divisible by p for almost every n in acertain arithmetic progression modulo p, notice that it says nothing about Q(n) outside of thisprogression.
Since Q(pn + σp ) ≡ 0 (mod p) for almost all n, it is not surprising that congruences inarithmetic subprogressions are eventually common. In [13], Serre proved the following wonderfulresult about the behavior of the Fourier coefficients modulo M of integer weight cusp forms,
which yields the proof of Theorem 2.
PnTheorem 11. Suppose that F (z) := ∞n=1 a(n)q is an integer weight cusp form with coefficients in Z. If m is a positive integer, then there is a set of primes Sm of positive density withthe property thata(n`r ) ≡ (r + 1)a(n) (mod m)whenever ` ∈ Sm , r is a positive integer, and n is coprime to `.
Proof of Theorem 2 : Apply Theorem 11 with m = p and r = p − 1 to the form Fp (z). Then,a positive proportion of the primes ` satisfyµ¶pn`p−1 − 1Q
≡ 0 (mod p)(5)24whenever gcd(n, `) = 1 and n ≡ p (mod 24). To construct congruences in arithmetic progressions modulo p, we simply let n = 24`k + p. Then equation (5) becomesµ¶p2 `p−1 − 1pQ p` k +≡ 0 (mod p)(6)
24
for all nonnegative integers k.
¤
Since the vector space of reductions mod M of integral weight cusp forms contains no nonzero
polynomials [5], we can already say that if there is one n ≡ −24−1 (mod p) for which Q(n) is
not a multiple of p, then there are infinitely many such n. We can do better, however, by using
Theorem 11 to prove Theorem 3.
Proof of Theorem 3 : Fix p ≥ 5 and let Sp denote the set of primes for Fp (z) guaranteed by
Theorem 11. The case r ≡ 0 (mod p) follows from Theorem 1. Otherwise recall the assumptionthat there is some n0 = (n − 1)/24 such thatQ(n0 ) ≡ a 6= 0(mod p)

Hence there exists a prime ` ∈ Sp such that for 1 ≤ b ≤ p the p numbersµ b¶n` − 1Q≡ (b + 1)a (mod p)
24
cover all of the residue classes modulo p. Because p is odd, for all but possibly finitely many
primes m ∈ Sp we know that that the p numbers¶µ b¶µ bn` − 1n` m − 1≡ 2Q≡ 2(b + 1)a (mod p)
Q24
24
cover all of the residue classes modulo p. Since Sp contains a positive proportion of the primes
m, we haveN#{n ≤ N : Q(n) ≡ r (mod p)} À π(N ) Àlog N

7

The upper bound on n0 follows easily from Sturm’s criterion.
¤For primes p ≥ 5, Theorem 3 provides an easy computational technique for verifying Newman’s question, and it has been checked for all such primes p < 1000. It is likely true for allprimes p ≥ 5. In fact, unless there is a congruence Q(pn + σp ) ≡ 0 (mod p) for all natural
numbers n, Newman’s conjecture is true for Q(n) modulo p.
4. Examples
In view of the small dimensions of spaces of cusp forms with low weight, it is possible in somecases to write down Fp (z) modulo p explicitly in terms of well known modular forms.
Proposition 12.

∞XQ(5n + 1)q n ≡n=0(q; q)11∞(q 2 ; q 2 )3∞(mod 5)

Proof: Using Sturm’s theorem, we find thatη 56 (2z)|U (5) ≡η 16 (z)η 38 (z)η 8 (2z)
η 6 (5z)(mod 5)≡ η 8 (z)η 8 (2z) (mod 5)
and therefore
F5 (z) ≡η 11 (24z)η 3 (48z)(mod 5).

¤Using similar computations, we discover nice expressions for F7 (z) and F11 (z). We employ
the classical weight k Eisenstein series Ek (z) defined by∞

Ek (z) := 1 −2k X
σk−1 (n)q n
Bkn=1where Bk is the kth Bernoulli number and
σk−1 (n) :=Xdk−1 .

d|nProposition 13.
∞X
n=0

Q(7n + 2)q n ≡(q; q)9∞
(2E8 (z) − E8 (2z)) (mod 7).
(q 2 ; q 2 )∞Proposition 14.
∞
X

Q(11n + 5)q n ≡ 7(q; q)5∞ (q 2 ; q 2 )3∞ (E6 (2z) + E6 (z)) (mod 11).

n=0

Applying the theory of Hecke operators allows one to explicitly identify congruences in arithmetic progressions for Q(n). For example, we find that
Fp (z) | T (`) ≡ 0 (mod p)

8JEREMY LOVEJOY

for the pairs (p, `) = (5, 73), (5, 97), (5, 193), (5, 313), (5, 337), (7, 673). Hence for these pairs (p, `)we haveµ¶µ pn¶pn` − 1−1
` −1+` Q
≡ 0 (mod p)
(7)
Q
24
24
for all nonnegative integers n with n ≡ p (mod 24). Replacing n by 24`n + p in (7) yields thefollwing congruences:
Theorem 15. For all nonnegative integers n we haveQ(26645n + 76)
Q(47045n + 101)
Q(186245n + 201)
Q(489845n + 326)
Q(567845n + 351)
Q(3170503n + 1374)

≡≡
≡
≡≡
≡

000000(mod 5)(mod 5)(mod 5)(mod 5)(mod 5)(mod 7)

References[1] K. Alladi, Partition identities involving gaps and weights, Trans. Amer. Math. Soc. 349 (1997), 5001-5019.
[2] G.E. Andrews, ”The Theory of Partitions,” Cambridge Univ. Press, Cambridge, 1998.
[3] B. Gordon and K. Hughes, Multiplicative properties of η-products II, Cont. Math. 143 (1993), 415-430.
[4] B. Gordon and K. Hughes, Ramanujan congruences for q(n), ”Analytic Number Theory,” Lecture Notes inMath. 899 Springer, New York, 1981, pp. 333-359.
[5] B. Gordon And K. Ono, Divisibility of certain partition functions by powers of primes, Ramanujan J. 1(1997), 25-34[6] N. Koblitz, ”Introduction to Elliptic Curves and Modular Forms,” Springer-Verlag, New York, 1984.
[7] G. Ligozat, Courbes modulaires de genre 1, Bull. Soc. Math. France, [Memoire 43] (1972), 1-80.
[8] M. Newman, Construction and application of a certain class of modular functions II, Proc. London Math.
Soc. 9 (1959), 353-387.
[9] M. Newman, Periodicity modulo m and divisibility properties of the partition function, Trans. Amer. Math.
Soc. 97 (1960), 225-236.
[10] K. Ono, Distribution of the partition function modulo m, Ann. of Math. 151 (2000), 1-15.
[11] K. Ono and D. Penniston, The 2-adic behavior of the number of partitions into distinct parts, J. Comb. Th.
Ser. A, accepted for publication.
[12] J. Rickert, Divisibility of restricted partition functions, preprint.
[13] J.P. Serre, Divisibilité de certaines fonctions arithmétiques, L’Ensign. Math. 22 (1976), 227-260.
[14] J. Sturm, On the Congruence Properties of Modular Forms, ”Number Theory,” Lecture Notes in Math. 1240
(1984), Springer-Verlag, New York, 1984, pp. 275-280.
Department of Mathematics, University of Wisconsin, Madison, WI 53706
E-mail address: lovejoy@math.wisc.edu