THE NUMBER OF PARTITIONS INTO DISTINCT PARTS MODULOPOWERS OF 5
JEREMY LOVEJOY
Abstract. We establish a relationship between the factorization of 24n+1 and the 5-divisibilityof Q(n), where Q(n) is the number of partitions of n into distinct parts. As an application we
explicitly exhibit an abundance of infinite families of congruences for Q(n) modulo powers of 5.

1. Introduction
A partition of a natural number n into distinct parts is a decreasing sequence of naturalnumbers whose sum is n. The number of such partitions is denoted Q(n), and we adopt theusual conventions that Q(0) = 1 and Q(α) = 0 whenever α is not a natural number. The typesof questions we consider about partition functions like Q(n) have been greatly influenced by thework of Ramanujan, who observed that for certain small primes p, the p-divisibility of 24n − 1 isrelated to the p-divisibility of p(n), where p(n) denotes the number of ordinary partitions of n.
In particular, he conjectured the existence of three infinite families of congruences in arithmetic
progressions for p(n). If β` (j) denotes the inverse of 24 modulo `j , then for all non-negative
integers n we havep(5j n + β5 (j)) ≡ 0jp(7 n + β7 (j)) ≡ 0(mod 5j ),[j/2]+1(mod 7(1.1)
),

(1.2)

andp(11j n + β11 (j)) ≡ 0(mod 11j ).

(1.3)

Ramanujan himself had a proof of (1.1) [4], while (1.2) was proven by Watson [16]. The thirdfamily was not proven until 1967 by Atkin [2], who developed an idea of Lehner [10] intoa technique which could theoretically be utilized to obtain a proof of any simple family of
congruences in arithmetic progressions for the Fourier coefficients of a modular function modulo
powers of a prime.
Applying many of these ideas, Rødseth [14] uncovered an infinite family of congruences forthe number of partitions into distinct parts. He proved that for all non-negative integers n wehaveQ(52j+1 n + γ2j+1 ) ≡ 0 (mod 5j )(1.4)
andQ(510j n + γ10j ) ≡ 0 (mod 55j ),1991 Mathematics Subject Classification. 11P83, 11F33.
The author thanks the NSF for its generous support.
1(1.5)

2JEREMY LOVEJOY

where γj is the inverse of −24 modulo 5j ,25[(j+1)/2] − 1.
24
The congruences (1.4) were subsequently rediscovered by Gordon and Hughes [6], but to ourknowledge no further families have been identified. Recent works [1, 7, 11] p-adically relating
certain values of Q(n) to Fourier coefficients of holomorphic modular forms guarantee that forany modulus M coprime to 3, there are indeed infinitely many independent congruences of theform Q(an + b) ≡ 0 (mod M ). However, it was believed that to explicitly identify examples inthis theory would require a case-by-case computation of the action of the Hecke operators T (p)(see Proposition 5 for the definition) on the relevant forms. This is true in general, although forthe modulus 5 it turns out that there is a significant amount of regularity. Our main theorems
demonstrate that the 5-divisibility of 24n + 1 is not the only factor which determines the 5divisibility of Q(n).
γj =Theorem 1. Let j ≥ 1 and let p be a prime for which
If ordp (n) is odd, thenp 6≡ {1, 11, 13, 23, 37, 47, 49, 59} (mod 120).

(1.6)

µ 2j
¶
5 n−1
Q
≡ 0 (mod 5j ).
24

(1.7)

Corollary 2. Let p be any prime satisfying (1.6) and let m be any odd natural number. If b isan integer with b < 24p, (b, p) = 1, and b ≡ p (mod 24), then for all non-negative integers n wehave
Q(52j pm+1 n + (52j pm b − 1)/24) ≡ 0 (mod 5j )(1.8)
To illustrate Corollary 2, if we take p = 7, m = 1, and b = 31, then for all non-negativeintegers n
Q(1225n + 226) ≡ 0 (mod 5),
Q(30625n + 5651) ≡ 0 (mod 25),..
.
2j
Q(5 · 49n + kj ) ≡ 0 (mod 5j ),where kj = (52j · 217 − 1)/24.
It is readily verified that all congruences in Corollary 2 are independent and not implied by
the family of Rødseth, with the exception of the cases p = 5 and 5 | j, which are containedin (1.4) and (1.5). It will of course be noted that Theorem 1 is a far stronger statement thanCorollary 2; however, the congruences in arithmetic progressions being of particular interest in
the subject, we have chosen to emphasize the corollary.
Our methods shall also reveal the following theorem, which improves Theorem 1 in certain
cases:
Theorem 3. Let j ≥ 0 and let p be a prime for whichp ≡ {61, 71, 73, 83, 87, 97, 109, 119} (mod 120).

(1.9)

3

If ordp (n) is odd, then

µ 10j+1¶
5n−1Q≡ 0 (mod 55j+1 ).
24(1.10)

Finally, we shall have occasion to mention the following companions to the original theoremof Rødseth, which is (1.4) when r = 1:
Theorem 4. For r = 1, 3, 4, and for all non-negative integers n we haveQ(52j+1 n + γ2j + r52j ) ≡ 0 (mod 5j )(1.11)In the following section we indicate some required preliminaries about modular forms andHecke operators, and in §3 we deduce the main results.
2. Modular forms and Hecke Operators
For positive integers k, N , and any Dirichlet character χ, let Mk (Γ0 (N ), χ) denote the finitedimensional C-vector space of modular forms of weight k, level N , and character χ. With theexception of Proposition 5 below, we shall not require any precise details about modular forms,so we omit an elemenatary discussion and instead refer the interested reader to [13]. For anyf (z) ∈ Mk (Γ0 (N ), χ), we identify f with its Fourier series in the variable q := e2πiz .
Proposition 5 ([13]). Let p denote a prime and ψ a Dirichlet character modulo M . If f =Pa(n)q n is the Fourier expansion of a modular form in Mk (Γ0 (N ), χ), then´X³f | T (p) :=a(pn) + χ(p)pk−1 a(n/p) q n(2.1)
is also the Fourier expansion of a modular form in Mk (Γ0 (N ), χ), andXf ⊗ ψ :=ψ(n)a(n)q n(2.2)

is the Fourier expansion of a modular form in Mk (Γ0 (N M 2 ), χψ 2 ).
The linear operators T (p) in (2.1) are the well-known Hecke operators for integer weight
modular forms. It turns out that many modular forms of interest have the property thatf (z) | T (p) = a(p)f (z)(2.3)

whenever p - N . Such a function is called an eigenform.
3. Proof of the Main Results
We begin by defining some relevant η-products, where η(z) := q 1/24
some lemmas about their Fourier coefficients modulo 5.

Q∞

Definition 6. For any positive i ≤ 23 which is coprime to 6, letη 16 (24z) η i (48z) Xfi (z) = 8× i=ai (n)q n
η (48z)η (24z)n=1 (1−qn ), and proving(3.1)

Observe that the coefficients ai (n) are supported on those natural numbers n for which n ≡ i(mod 24).
Lemma 7. We have(i) If i = 1 or 11 and n ≡ 0, 2, 3 (mod 5), then ai (n) ≡ 0 (mod 5),

4JEREMY LOVEJOY(ii) If i = 13 or 23 and n ≡ 0, 1, 4 (mod 5), then ai (n) ≡ 0 (mod 5).
Proof. We give details only for the function f1 (z) - the remaining cases are analogous. Thereis a simple criterion for deciding when an η-product is a holomorphic modular form (see, forexample, [11], √Th. 4). We¡ • ¢ find that f1 (z) ∈ M4 (Γ0 (1152), χ2 ), where χ2 denotes the Kronecker
symbol for Q( 2). If 5 denotes the Legendre symbol, then by Proposition 5 the function
defined by³•´g1 (z) = f1 − f1 ⊗(3.2)
5
is a modular form in M4 (Γ0 (28800), χ2 ) and has Fourier expansion
XX
a1 (n)q n .
(3.3)
a1 (n)q n +g1 (z) = 2n≡2,3n≡0(mod 5)(mod 5)

By a theorem of Sturm [15], we need only demonstrate the desired congruence for n ≤ 23040.
This is easily handled by machine computation.
¤Lemma 8.
(i) If p is a prime such that p ≡ 5, 7 (mod 12), thenf1 (z) | T (p) ≡ 0 (mod 5).

(3.4)(ii) If p is a prime such that p ≡ 1, 11 (mod 24) and p ≡ 2, 3 (mod 5) or if p is a prime
such that p ≡ 13, 23 (mod 24) and p ≡ 1, 4 (mod 5), thenfi (z) | T (p) ≡ 0 (mod 5).

(3.5)

Proof. Gordon and Sinor [8] have proven that if√√√√√√√(α1 , α5 , ..., α23 ) = (1, −2i 35, 2 110, 4i 154, −8i 77, 16 55, 16i 70, 32 2),
theng(z) =X

αi fi (z)

(3.6)
(3.7)

is a modular form in M4 (Γ0 (1152), χ2 ) and an eigenform for the Hecke operators T (p). (Wealert the reader that the function g is misprinted in [8].) Since the Fourier coefficients ai (n) aresupported on those n for which n ≡ i (mod 24), the fi (z) are simply permuted, up to constantmultiples, by the action of the Hecke operators. In particular, we havefi | T (p) =αp αpi ap (p)αi

× fpi ,

(3.8)

where x denotes the residue class of x modulo 24. The fact that 5 | αp 2 when p ≡ 5, 7 (mod 12)
establishes part (i) of the Lemma, while part (ii) follows from the vanishing modulo 5 of theappropriate ap (p) as indicated in Lemma 7.
¤Proof of the Main Results. In the course of establishing the family of congruences (1.4) and(1.5), Rødseth [14] proves the congruence∞X
n=0

Q(52j n + γ2j )q 24n+1 ≡ cj 5j−1 f1 (z)(mod 5j ),(3.9)

5where cj is an integer such that 5 | cj if and only if 5 | j. Then (1.4) is easily deduced from(3.9) upon replacing n by 5n + 1 and appealing to Lemma 7 (i) in the case n ≡ 0 (mod 5). Byapplying the full strength of Lemma 7 (i) to (3.9), we obtain Theorem 4.
By the definition of the Hecke operators and an application of Lemma 8 to (3.9), we have¶¶µ µ¶¶µ µn/p − 1
pn − 152j − 152j − 12j
32j
Q 5++ χ(p)p Q 5+
≡ 0 (mod 5j ) (3.10)2424
2424for the relevant primes p. The case ordp (n) = 1 of Theorem 1 is immediate and the fullstatement follows by induction. When m is odd and n is replaced by pm (24pn + b) in (1.7), wehave Corollary 2. Finally, it is also shown in [14] that if j ≡ 1 (mod 5), then∞XQ(52j−1 n + γ2j−1 )q 24n+5 ≡ bj 5j−1 f11 (z)(mod 5j ),(3.11)

n=0where 5 - bj . Using Lemma 8 (ii) and arguing as above gives Theorem 3.

¤

4. Concluding Remarks
Because of ongoing interest in the arithmetic properties of partition functions, we have elected
to focus the present investigation on Q(n). However, it is important to recognize that themethods used here are applicable in many of the studies of families of congruences in arithmetic
progressions for the Fourier coefficients of modular functions modulo powers of primes. Atkin,Gordon, Hughes, [3, 5, 9] and others have made several such studies of the values of pk (n), where∞Xn=0n

pk (n)q =∞Y(1 − q n )k ,(4.1)

n=1

and invariably one finds an equation analogous to (3.9) as a key ingredient in their proofs. It
is a simple observation about the relevant modular form appearing in such an equation thatallows one to pass to a single family of congruences, but a more detailed investigation, asexemplified here or in [12], will always yield considerably more information. In some cases there
are apparently only accidents, but in various situations one finds CM forms, eigenforms (asin [12]), and other forms of integer and half-integer weight whose Fourier coefficients possessparticular properties. Undoubtedly there is much more waiting to be discovered in the works
cited above.
References[1] S. AHLGREN and J. LOVEJOY, ‘The arithmetic of the number of partitions into distinct parts’, Mathematika (to appear).
[2] A.O.L. ATKIN, ‘Proof of a conjecture of Ramanujan’, Glasgow Math J. 8 (1967) 14-32.
[3] A.O.L. ATKIN, ‘Ramanujan congruences for p−k (n)’, Canad. J. Math. 20 (1968) 67-78.
[4] B.C. BERNDT and K. ONO, ‘Ramanujan’s unpublished manuscript on the partition and tau functions withproofs and commentary’, Sem. Lothar. Combin. 42 (The Andrews Festschrift) (1999) Art. B42c, 63pp.
[5] B. GORDON, ‘Ramanujan congruences for p−k (mod 11r )’, Glasgow Math. J. 24 (1983) 107-123.
[6] B. GORDON and K. HUGHES, ‘Ramanujan congruences for q(n)’, Analytic Number Theory, Lecture Notes
in Mathematics 899 (Springer, New York, 1981), pp. 333-359.
[7] B. GORDON and K. ONO, ’Divisibility of certain partition functions by powers of primes’, Ramanujan J. 1(1997) 25-34.

6JEREMY LOVEJOY[8] B. GORDON and D. SINOR, ‘Multiplicative properties of η-products’, Number Theory, Madras 1987, Lecture
Notes in Mathematics 1395 (Springer-Verlag, New York, 1989), pp. 173 - 200.
[9] K. HUGHES, ‘Ramanujan congruences for p−k (n) modulo powers of 17’, Canad. J. Math. 43 (1991) 506-525.
[10] J. LEHNER, ‘Proof of Ramanujan’s Partition Congruence for the modulus 113 ’, Proc. Amer. Math. Soc. 1(1950) 172-181.
[11] J. LOVEJOY, ‘Divisibility and distribution of partitions into distinct parts’, Adv. Math. 158 (2001) 253-263.
[12] J. LOVEJOY and K. ONO, ‘Extension of Ramanujan’s congruences for the partition function modulo powersof 5’, J. Reine Angew. Math. (to appear).
[13] N. KOBLITZ, Introduction to Elliptic Curves and Modular Forms (Springer-Verlag, New York, 1984).
[14] Ø. RØDSETH, ‘Congruence properties of the partition functions q(n) and q0 (n)’, Arbok Univ. Bergen Mat.Natur. Ser. 13 (1969), 27pp.
[15] J. STURM, ‘On the congruence properties of modular forms’, Number Theory, Lecture Notes in Mathematics
1240 (Springer-Verlag, New York, 1987), pp. 275-280.
[16] G.N. WATSON, ‘Ramanujan’s Vermutung über Zerfällungsanzahlen’, J. Reine Angew. Math. 179 (1938) 97- 128.
Projet ”Theorie des Nombres”, Institut de Mathematiques de Jussieu, Case 247, 4 Place Jussieu,75252 Paris CEDEX 05
E-mail address: lovejoy@math.jussieu.fr