New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
Congruence properties for the partition function

Communicated by Richard A. Askey, University of Wisconsin, Madison, WI (received for review August 15, 2000)
Abstract
Eighty years ago, Ramanujan conjectured and proved some striking congruences for the partition function modulo powers of 5, 7, and 11. Until recently, only a handful of further such congruences were known. Here we report that such congruences are much more widespread than was previously known, and we describe the theoretical framework that appears to explain every known Ramanujantype congruence.
1. Introduction and Statement of Results.
Let p(n) denote the usual partition function; p(n) is the number of ways to write a positive integer n as the sum of a nonincreasing sequence of positive integers. As usual, we agree that p(0) = 1 and that p(t) = 0 if t ∉ ℤ_{≥0}. Many of the most interesting arithmetic properties of this function were suggested (and often proved) by Ramanujan. Notice that if δ_{ℓ} is defined by 1.1 then the celebrated Ramanujan congruences may be written succinctly in the form Countless papers have been written on these three congruences and their extensions (already conjectured, and in some cases proved, by Ramanujan) to arbitrary powers of 5, 7, and 11 [see the fundamental works of Andrews, Atkin, Dyson, Garvan, Kim, Ramanujan, Stanton, and SwinnertonDyer (1–10)]. Each of these extensions lies within the class −δ_{ℓ} (mod ℓ). The important role that this class plays in the theory is illustrated by the work of Kiming and Olsson (ref. 11, theorem 1), who proved that if ℓ ≥ 5 is prime and p(ℓn + β) ≡ 0 (mod ℓ) for all n, then β ≡ −δ_{ℓ} (mod ℓ).
Work of Atkin, Newman, O'Brien, and SwinnertonDyer (12, 14, 15, 16) produced further congruences modulo ℓ^{m} for primes ℓ ≤ 31 and small m. The examples discovered by Atkin and Newman in refs. 12 and 16 show that not every congruence lies within the progression −δ_{ℓ} (mod ℓ). For example, we have 1.2 We have shown (13, 17) that if ℓ ≥ 5 is prime and m is any positive integer, then there are infinitely many congruences of the form As in the case of Ramanujan's congruences, all of these arithmetic progressions lie within the class −δ_{ℓ} (mod ℓ). To summarize, the current state of knowledge consists of a systematic theory of congruences within the progressions −δ_{ℓ} (mod ℓ), as well as some sporadic examples of congruences that fall outside of this class. In view of this, it is natural to wonder what role the class −δ_{ℓ} (mod ℓ) truly plays.
In this paper, we show that in general this class is not as distinguished as might have been expected. In fact, we prove that it is only one of (ℓ + 1)/2 classes modulo ℓ in which the partition function enjoys similar congruence properties. The results in this paper include the main results in refs. 13 and 17 as special cases and provide a theoretical framework that (to our knowledge) explains every known congruence for the partition function.
For each prime ℓ ≥ 5, define the integer ɛ_{ℓ} ∈ {±1} by 1.3 and let S_{ℓ} denote the set of (ℓ + 1)/2 integers 1.4 Theorem 1. If ℓ ≥ 5 is prime, m is a positive integer, and β ∈ S_{ℓ}, then a positive proportion of the primes Q ≡ −1 (mod 24ℓ) have the property that for all n ≡ 1 − 24β (mod 24ℓ) with gcd(Q, n) = 1.
Note that the case when β ≡ −δ_{ℓ} (mod ℓ) already contains the main results in refs. 13 and 17.
In general, there is no simple description of the set of primes Q occurring in Theorem 1. However, as Atkin (12) showed, when ℓ = 5, 7, or 13, the situation can be made quite explicit. For example, Atkin proved the following (see ref. 12 for analogous results when ℓ = 7 or 13).
Theorem 2 [Atkin (12)].
(1) Suppose ℓ ≡ 4 (mod 5) is prime and n is a positive integer with ℓ∤n. If n ≡ 23ℓ (mod 120) or n ≡ 47ℓ (mod 120), then
(2) Suppose ℓ ≡ 3 (mod 5) is a prime exceeding 3, and n is a positive integer with (−n/ℓ) = −1. If n ≡ 23 (mod 120) or n ≡ 47 (mod 120), then We should remark that Newman (16) discovered the simplest example of the congruences described in the first part of Theorem 2 (i.e., the case where ℓ = 19). Notice that in either part of Theorem 2, fixing n in an appropriate residue class modulo 120ℓ yields a Ramanujantype congruence. For example, if ℓ = 13, then the second part of Theorem 2 implies, for every integer n, that 1.5 Arguing in this manner from Theorem 1, we obtain
Theorem 3. If ℓ ≥ 5 is prime, m is a positive integer, and β ∈ 𝒮_{ℓ}, then there are infinitely many nonnested arithmetic progressions {An + B} ⊆ {ℓn + β}, such that for every integer n we have If M is an integer coprime to 6, then Theorem 3 and the Chinese Remainder Theorem guarantee the existence of congruences modulo ℳ.
In Section 2, we construct half integral weight cusp forms whose coefficients capture the relevant values of the partition function, and in Section 3 we prove Theorem 1. The proof requires certain facts arising from the theory of Galois representations associated to modular forms and Shimura's theory of half integral weight modular forms. In Section 4, we consider those progressions ℓn + β for β ∉ 𝒮_{ℓ}. We give heuristics that cast doubt on the existence of congruences within these progressions.
2. Half integral weight cusp forms and the partition function.
We assume familiarity with standard notation and facts from the theory of integral and half integral weight modular forms. Throughout, we agree that q := e^{2πiz}, and we identify a modular form f(z) with its Fourier expansion f(z) = ∑a(n)q^{n}. Recall Dedekind's etafunction 2.1 Theorem 2.1. Suppose ℓ ≥ 5 is prime and m is a positive integer. If β ∈ S_{ℓ}, then there is an integer λ_{ℓ,m}and a modular form F_{ℓ,m,β}(z) ∈ S_{(2λℓ,m}_{+1)/2}(Γ_{1}(576ℓ^{5})) ∩ ℤ[[q]] such that Proof: If ℓ ≥ 5 is prime and t is a positive integer, then 2.2 where χ_{ℓ,t} := ((−1)^{(ℓt}^{−1)/2}ℓ^{t}/•). By using standard facts, it can be shown that if ℓ ∤ a and 0 ≤ b < t, then ord_{a/ℓb}(E_{ℓ,t}(z)) > 0. Hence, E_{ℓ,t}(z) vanishes at those cusps of Γ_{0}(ℓ^{t}), which are not equivalent to ∞. Also, because (1 − X)^{ℓ} ≡ (1 − X^{ℓ}) (mod ℓ), for every m > 0 we have 2.3 If ℓ ≥ 5 is prime, then define f_{ℓ}(z) = ∑a_{ℓ}(n)q^{n} by 2.4 Because ∑p(n)q^{n}=∏(1−q^{n})^{−1}, 2.1 and 2.4 imply that 2.5 Define f̃_{ℓ}(z) by 2.6 By standard facts, we have f̃_{ℓ}(z) ∈ M_{(ℓ−1)/2}(Γ_{0}(ℓ^{3}), ()). By 2.3 and 2.6, if m′ is sufficiently large, then f_{ℓ,m′}(z) := E(z)f̃_{ℓ}(z) is a cusp form on Γ_{0}(ℓ^{3}) with character χ_{ℓ,t}⋅() for which 2.7 and 2.8 By 2.5 and 2.7, we have 2.9 Now 2.8 shows that (f_{ℓ,m′}(z)/η^{ℓ}(ℓz))^{24} vanishes at ∞. Therefore, if m′ is sufficiently large, then this form vanishes at every cusp. It follows that f_{ℓ,m′}(24z)/η^{ℓ}(24ℓz) is a cusp form on Γ_{0}(576ℓ^{3}). We have the general fact that if f(z) = ∑a(n)q^{n} ∈ S_{λ+½}(Γ_{1}(N)), and r and t are positive integers, then ∑_{n≡r (mod t)}a(n)q^{n} ∈ S_{λ+½}(Γ_{1}(Nt^{2})). Theorem 2.1 follows by applying this fact to f_{ℓ,m′}(24z)/η^{ℓ}(24ℓz). □
3. Proof of Theorems 1 and 2.
We begin with some general facts. Suppose that λ ∈ ℤ, and that f(z) = ∑a(n)q^{n} ∈ S_{λ+½}(Γ_{1}(N)) has algebraic coefficients. We have a decomposition 3.1 further, we may write f(z) = ∑_{χ even}α_{fχ}f_{χ}(z), where each α_{fχ} is algebraic, and each form f_{χ}(z) ∈ S_{λ+½}(Γ_{0}(N), χ) has algebraic integer coefficients. Suppose that the Fourier expansion of such a form is given by f_{χ}(z) = ∑a_{χ}(n)q^{n}. If p is prime, then the action of the usual Hecke operator T_{χ}(p^{2}) on f_{χ} is described by 3.2 Using 3.1 and 3.2, we define the operator T(p^{2}) on S_{λ+½}(Γ_{1}(N)) via linearity. In particular, if f(z) = ∑a(n)q^{n} ∈ S_{λ+½}(Γ_{1}(N)) and p ≡ −1 (mod N) is prime, then 3.3 Lemma 3.1. Suppose that f(z) = ∑a(n)q^{n} ∈ S_{λ+½}(Γ_{1}(N)) has algebraic integer coefficients. If M is a positive integer, then a positive proportion of the primes p ≡ −1 (mod MN) have the property that f(z)  T(p^{2}) ≡ 0 (mod M).
Proof: Write f(z) = ∑_{χ even}α_{fχ}f_{χ}(z) as above and choose a positive integer 𝒟 such that each Dα_{fχ} is an algebraic integer. After replacing M by DM, we see that it will suffice to prove that a positive proportion of the primes p ≡ −1 (mod MN) have the property that f_{χ}(z)  T(p^{2}) ≡ 0 (mod M) for every character χ.
Fix a number field K such that the coefficients of each form f_{χ} and the values of each character χ belong to the ring of integers 𝒪_{K}. If t is an integer, then let χ_{t} denote the usual Kronecker character for ℚ(). For each form f_{χ} and for every positive squarefree integer t, we have the Shimura lift (18) 3.4 defined by S_{t}(f_{χ})(z) := ∑ A_{χ, t}(n)q^{n}, where the A_{χ,t}(n) are given by 3.5 If M, k, and N are positive integers, then let S_{k}(Γ_{1}(N))_{𝒪K}_{/M} [respectively (resp) S_{k}(Γ_{0}(N), χ)_{𝒪K}_{/M}] denote the reductions modulo M of those forms in S_{k}(Γ_{1}(N)) [resp S_{k}(Γ_{0}(N), χ)] with coefficients in 𝒪_{K}, and let T(p) [resp T_{χ}(p)] denote the usual integralweight Hecke operator. Serre (ref. 19, 6.4) proved that a positive proportion of the primes p ≡ −1 (mod MN) have By using a straightforward modification of the same argument, one can show that a positive proportion of the primes p ≡ −1 (mod MN) have After 3.4, we conclude that a positive proportion of the primes p ≡ −1 (mod MN) have Because the Shimura correspondence commutes with the action of the Hecke algebra, it follows that if p is such a prime, then 3.6 Lemma 3.1 follows from 3.5 and 3.6. □
Proof of Theorem 1: We apply Lemma 3.1 to the forms F_{ℓ,m,β}(z) given in Theorem 2.1. Fix a prime ℓ and an integer β ∈ S_{ℓ} and write By Lemma 3.1, a positive proportion of the primes Q ≡ −1 (mod 24ℓ) have the property that F_{ℓ,m,β}(z)  T(Q^{2}) ≡ 0 (mod ℓ^{m}). After replacing n by Qn in definition 3.3, we see that if n ≡ 1 − 24β (mod 24ℓ) and gcd(Q, n) = 1, then because Q^{3}n ≡ 24β − 1 (mod 24ℓ). Theorem 1 follows. □
4. Final Remarks.
One naturally questions whether Theorem 1 can be extended to the remaining residue classes modulo ℓ. Suppose that β ∈ {0, … , ℓ − 1}. If we could produce a cusp form F_{ℓ,m,β}(z) as in Theorem 2.1, then we would obtain the statment of Theorem 1 for β. Because F_{ℓ,m,0}(z) would necessarily have a pole at infinity, this approach seems hopeless when β = 0. The situation, however, is less clear when β ≠ 0. For every prime ℓ ≥ 5 and every m, it is straightforward to show that there exists an integral weight modular form H_{ℓ,m}(z) such that However, to construct H_{ℓ,m}(z) requires the twists of f_{ℓ}(z) by all of the Dirichlet characters modulo ℓ; it results that H_{ℓ,m}(z) is a form on Γ_{1}(ℓ^{3}). By contrast, the form that we constructed in 2.6 required only a single quadratic twist and so remained on Γ_{0}(ℓ^{3}).
It is clear that if we had the analog for Γ_{1}(ℓ^{t}) of the form E_{ℓ,t}(z) used in the proof of Theorem 2.1, then we could prove Theorem 1 for all nonzero β. By using the work of Hecke, it is possible to construct an Eisenstein series on Γ_{1}(ℓ^{t}) that has the proper cusp conditions (in fact, up to scalar multiplication, exactly one such series exists). It remains to determine whether this series can be defined over the algebraic numbers, and, if so, to determine the ℓadic nature of its coefficients. Unfortunately, the answers to both of these problems seem to depend on the arithmetic of certain unknown values of Dirichlet Lfunctions at positive integral arguments. Although many of these values can be described in terms of generalized Bernoulli numbers, the remaining values are (up to unknown algebraic factors) values of certain regulators defined via canonical maps from higher Kgroups into Minkowskitype spaces (20).
We conclude by remarking that computer calculations seem to cast some doubt on whether such forms exist in general. If they did, this evidence suggests a contradiction to Serre's famous result (ref. 19, theorem 4.7) that if M is any given integer, then almost all of the coefficients of an integral weight modular form with integer coefficients are multiples of M.
Acknowledgments
S.A. is supported by a National Science Foundation grant. K.O. is supported by a National Science Foundation Presidential Early Career Award, an Alfred P. Sloan Foundation Research Fellowship, and a David and Lucile Packard Research Fellowship.
 Received August 15, 2000.
 Accepted September 17, 2001.
 Copyright © 2001, The National Academy of Sciences
References
 ↵
 Andrews G E,
 Garvan F

 Atkin A O L

 Berndt B C,
 Ono K

 Dyson F J
 ↵
 Garvan F,
 Kim D,
 Stanton D

 Ramanujan S

 Ramanujan S

 Ramanujan S
 ↵
 Ramanujan S
 ↵
 Kiming I,
 Olsson J
 ↵
 Atkin A O L
 ↵
 ↵
 Atkin A O L,
 O'Brien J N
 ↵
 Atkin A O L,
 SwinnertonDyer H P F
 ↵
 Newman M
 ↵
 ↵
 ↵
 Serre JP
 ↵
 Beilinson A A