ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 1, Issue 1, 1995

PARITY OF THE PARTITION FUNCTION

KEN ONO

(Communicated by Don Zagier)

Abstract. Let p(n) denote the number of partitions of a non-negative integer n. A well-known conjecture asserts that every arithmetic progression contains infinitely many integers M for which p(M) is odd, as well as infinitely many integers N for which p(N) is even (see Subbarao [22]). From the works of various authors, this conjecture has been verified for every arithmetic progression with modulus t when t = 1, 2, 3, 4, 5, 10, 12, 16, and 40. Here we announce that there indeed are infinitely many integers N in every arithmetic progression for which p(N) is even; and that there are infinitely many integers M in every arithmetic progression for which p(M) is odd so long as there is at least one such M. In fact if there is such an M, then the smallest such M ≤ 10^{10}t^{7}. Using these results and a fair bit of machine computation, we have verified the conjecture for every arithmetic progression with modulus t ≤ 100, 000.

1. Introduction

A partition of a non-negative integer n is a non-increasing sequence of positive integers whose sum is n. Euler’s generating function for p(n), the number of partitions of an integer n, is:

(1)  ∑_{n=0}^{∞} p(n)q^{n} = ∏_{n=1}^{∞} \frac{1}{1 − q^{n}} .

Ramanujan discovered various surprising congruences for p(n) when n is in certain special arithmetic progressions; for example:

p(5n + 4) ≡ 0 mod 5,
p(7n + 5) ≡ 0 mod 7,

and

p(11n + 6) ≡ 0 mod 11.

There are now many proofs of these congruences (and their generalizations) in the literature (see [1, 2, 3, 4, 5, 6, 7, 11, 12, 23 ] for instance). Surprisingly there do

Received by the editors February 28, 1995, and, in revised form, May 3, 1995. 1991 Mathematics Subject Classification. Primary 05A17; Secondary 11P83. Key words and phrases. Parity conjecture, partitions, modular forms. The author is supported by NSF grant DMS-9508976.

\begin{matrix}c \\ ◯ \end{matrix}1995 American Mathematical Society

not seem to be any such congruences modulo 2 or 3. In fact the parity of p(n) seems to be quite random, and it is believed that the partition function is ‘equally often’ even and odd; that is, that p(n) is even for ∼ \frac{1}{2}x positive integers n ≤ x (see Parkin and Shanks [19]).

In [22] Subbarao made the following conjecture on the parity of p(n), for those integers n belonging to any given arithmetic progression:

Conjecture. For any arithmetic progression r (mod t), there are infinitely many integers M ≡ r (mod t) for which p(M) is odd, and there are infinitely many integers N ≡ r (mod t) for which p(N) is even.

From the works of Garvan, Kolberg, Hirschhorn, Stanton, and Subbarao (see [6, 9, 10, 13, 16, 22],), this conjecture has been proved for every arithmetic progression with modulus t when t = 1, 2, 3, 4, 5, 10, 12, 16 and 40.

Using very different methods, we go some way towards a proof of the conjecture. Using the theory of modular forms, we announce:

Main Theorem 1. For any arithmetic progression r (mod t), there are infinitely many integers N ≡ r (mod t) for which p(N) is even.

Main Theorem 2. For any arithmetic progression r (mod t), there are infinitely many integers M ≡ r (mod t) for which p(M) is odd, provided there is one such M. Furthermore, if there does exist an M ≡ r (mod t) for which p(M) is odd, then the smallest such M is less than C_{r,t}, where

C_{r,t} := \frac{2^{23}A · 3^{7}t^{6}}{d^{2}} ∏_{p|6t} (1 − \frac{1}{p^{2}} ) − A,

with d := gcd(24r − 1, t) and A > \frac{t}{24} is a power of 2.

From the two theorems we obtain an algorithm to determine the truth of our parity conjecture for any given arithmetic progression r (mod t): Compute p(N) (mod 2) for N = r, r + t, r + 2t, … for all such N up to C_{r,t}. As soon as we find one odd number we have verified the conjecture. If all these numbers are even then we have proved that the conjecture is false.

Ken Burrell (Universal Analytics, Inc.) ran an efficient version of this algorithm on a CRAY C-90, giving the following result:

Main Corollary. For all 0 ≤ r < t ≤ 10^{5}, there are infinitely many integers M ≡ r (mod t) for which p(M) is odd.

2. The main ideas

First we briefly recall essential preliminaries concerning modular forms. For more on the theory of modular forms see [15].

Let A = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ SL_{2}(ℤ) act on ℌ, the upper half of the complex plane, by

the linear fractional transformation Az = \frac{az+b}{cz+d}. If N is a positive integer, then we define the following congruence subgroups of SL_{2}(ℤ) of level N:

Γ_{0}(N) := \{( \begin{matrix}a & b \\ c & d \end{matrix} ) | ad − bc = 1, c ≡ 0 mod N\} .

and

Γ_{1}(N) := \{( \begin{matrix}a & b \\ c & d \end{matrix} ) | ad − bc = 1, a ≡ d ≡ 1 mod N, and c ≡ 0 mod N\} .

A meromorphic function f(z) on ℌ is called a modular function with positive integer weight k with respect to congruence subgroup Γ if

f (\frac{az + b}{cz + d}) = (cz + d)^{k}f(z)

for all z ∈ ℌ and all ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ. If f(z) is holomorphic on ℌ and at the cusps

of Γ (i.e. the rationals), then f(z) is known as a modular form of weight k with respect to Γ. If f(z) vanishes at the cusps of Γ, then f(z) is known as a cusp form.

We denote the finite dimensional space of modular forms (resp. cusp forms) of weight k with respect to Γ_{1}(N) by M_{k}(N) (resp. S_{k}(N)). In the variable q = e^{2πiz}, a holomorphic modular form f(z) ∈ M_{k}(N) admits a Fourier expansion of the form

f(z) = ∑_{n=0}^{∞} a(n)q^{n}.

Of particular interest are certain modular forms in M_{k}(N) with nice modular transformation properties with respect to Γ_{0}(N). If χ is a Dirichlet character mod N, then we say that a form f(z) ∈ M_{k}(N) (resp. S_{k}(N) ) is modular form of weight k with Nebentypus character χ if

f (\frac{az + b}{cz + d}) = χ(d)(cz + d)^{k}f(z)

for all z ∈ ℌ and all ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ_{0}(N). The space of such modular forms (resp.

cusp forms) is denoted by M_{k}(N, χ) (resp. S_{k}(N, χ)).

The Dedekind eta-function is the principal modular form of interest in this paper; it is defined by the infinite product

η(z) := q^{\frac{1}{24}} ∏_{n=1}^{∞}(1 − q^{n}).

A function f(z) is called an eta-product if it is expressible as a finite product of the form

f(z) = ∏_{δ|N} η^{r_{δ}}(δz)

where N and each r_{δ} is an integer. Probably the most famous of all eta-products is Ramanujan’s Δ−function, defined by Δ(z) := η^{24}(z) = q ∏_{n=1}^{∞}(1 − q^{n})^{24}. This is the unique normalized weight 12 cusp form on SL_{2}(ℤ). More generally, Gordon, Hughes, and Newman (see [8,17,18]) examined the general modular properties of eta-products.

We construct modular forms that are eta-products whose Fourier expansions modulo 2 are determined by the values of p(n) modulo 2.

Proposition 1. For a given positive integer t, let A > \frac{t}{24} be a power of 2. Define f_{t,A}(z) by

f_{t,A}(z) := \frac{η(24z)}{η(48z)}Δ^{A}(24tz) = ∑_{n≥1} a_{t}(n)q^{24n−1}.

Then f_{t,A}(z) is a cusp form in S_{12A}(1152t, (\frac{2}{d})). Moreover the Fourier expansion of f_{t,A}(z) mod 2 can be factored as:

(2) f_{t,A}(z) = ∑_{n=0}^{∞} a_{t}(n)q^{24n−1} ≡ (∑_{n=0}^{∞} p(n)q^{24n−1}) (∑_{n=0}^{∞} q^{24At(2n+1)^{2}}) mod 2.

Proof. Using the well known properties of the Dedekind eta-function, it is relatively straightforward to deduce that f_{t,A}(z) is a modular form of weight 12A. It is also straightforward to deduce that f_{t,A}(z) is a cusp form.

The essential feature of the cusp form f_{t,A}(z) is the convenient fact that f_{t,A}(z) is essentially the product of the generating function for p(n) and a theta function mod 2.

Since \frac{1}{1 − X^{n}} = \frac{1 + X^{n}}{1 − X^{2n}} ≡ \frac{1 − X^{n}}{1 − X^{2n}} mod 2, it follows that

∑_{n=0}^{∞} p(n)q^{n} ≡ ∏_{n=1}^{∞} \frac{1 − q^{n}}{1 − q^{2n}} mod 2.

In terms of the eta-functions, we find that

(3)  \frac{η(24z)}{η(48z)} = \frac{1}{q} ∏_{n=1}^{∞} \frac{1 − q^{24n}}{1 − q^{48n}} ≡ ∑_{n=0}^{∞} p(n)q^{24n−1} mod 2.

The following infinite product identity was proved by Jacobi:

\frac{η^{2}(16z)}{η(8z)} = q ∏_{n=1}^{∞} \frac{(1 − q^{16n})^{2}}{(1 − q^{8n})} = ∑_{n=0}^{∞} q^{(2n+1)^{2}}.

Therefore since (1 − X)^{2} ≡ (1 − X^{2}) mod 2, we find that (4)

Δ(z) = q ∏_{n=1}^{∞}(1−q^{n})^{24} = q ∏_{n=1}^{∞} \frac{(1 − q^{n})^{32}}{(1 − q^{n})^{8}} ≡ q ∏_{n=1}^{∞} \frac{(1 − q^{16n})^{2}}{(1 − q^{8n})} ≡ ∑_{n=0}^{∞} q^{(2n+1)^{2}} mod 2.

The factorization of f_{t,A}(z) now follows easily from (3) and (4). □

Serre [20] proved the following remarkable theorem regarding the divisibility of Fourier coefficients of holomorphic integer weight modular forms.

Theorem. (Serre) Let f(z) be a holomorphic modular form of positive integer weight k on some congruence subgroup of SL_{2}(ℤ) with Fourier expansion

f(z) = ∑_{n=0}^{∞} a(n)q^{n}

where a(n) are algebraic integers in some number field. If m is a positive integer, then there exists a positive constant α such that the set of integers n ≤ x for which a(n) is not divisible by m has cardinality ≪ \frac{x}{log^{α} x}.

With this theorem we obtain Main Theorem 1. For any arithmetic progression r (mod t), there are infinitely many integers N ≡ r (mod t) for which p(N) is even.

Proof. Comparing coefficients in (2), it is easy to deduce that

(5)  a_{t}(Atk^{2} + n) ≡ ∑_{i≥1, i odd} p(At(k^{2} − i^{2}) + n) mod 2.

Now suppose every N ≥ n_{0} for which N ≡ r (mod t) has the property that p(N) is odd. If k ≡ 1 mod 4, then every integer n ≡ r (mod t) in the interval [Atk^{2} + n_{0}, At(k + 2)^{2} + r − t] has the property that a_{t}(n) is odd since there are

\frac{k + 1}{2} many odd summands in (5). After combining all such intervals, we find a set of positive integers with positive density for which a_{t}(n) ≢ 0 mod 2. This would contradict Serre’s theorem. □

Now we need to establish that there are infinitely many M ≡ r (mod t) where p(M) is odd provided that there is at least one M. To do this we first deduce a technical lemma about the reduction modulo m of the Fourier expansions of holomorphic modular forms. Main Theorem 2 follows as a consequence, for if there were only finitely many M ≡ r (mod t) for which p(M) is odd, then the reduction mod 2 of the relevant modular form contradicts the lemma.

For a given positive integer m and formal power series f := ∑_{n∈ℤ} a(n)q^{n} with algebraic integer coefficients, we define Ord_{m}(f) to be the smallest integer n for which a(n) is not divisible by m. A special case of a theorem of Sturm [21] allows us to computationally determine whether m divides a(n) for every integer n (that is, to determine whether Ord_{m}(f) = ∞).

If f(z) = ∑_{n=0}^{∞} a(n)q^{n} ∈ M_{k}(N) for some positive integer N with algebraic integer Fourier coefficients from a fixed number field and m is a positive integer, then Sturm proved that if

Ord_{m}(f) > \frac{k}{12}N^{2} ∏_{p|N}(1 − \frac{1}{p^{2}} ),

then Ord_{m}(f) = ∞ (i.e. a(n) ≡ 0 mod m for all n). Now we prove the essential lemma about the reduction of a holomorphic modular form mod m.

Lemma 1. Let f(z) = ∑_{n=0}^{∞} a(n)q^{n} where the coefficients a(n) are algebraic integers in some number field. Let s and w be positive integers and b_{1}, b_{2}, … b_{s} distinct non-zero integers. If m is a positive integer and

f(z) ≡ ∑_{1≤i≤s} ∑_{n=0}^{∞} a_{i}(n)q^{wn^{2}+b_{i}} mod m

where a_{i}(n) ≢ 0 mod m for infinitely many n ≥ 0, then f(z) is not in M_{k}(N) for any pair of positive integers k, and N.

Proof. Suppose that f ∈ M_{k}(N) for some k and N. If p ≡ 1 (mod N) is prime, then the image of f under the Hecke operator T_{p} satisfies

f(z)|T_{p} = ∑_{n≥0}(a(pn) + p^{k−1}a(n/p)) q^{n}

≡ ∑_{\begin{matrix}i,n \\ p|wn^{2}+b_{i} \end{matrix}} a_{i}(n) q^{(wn^{2}+b_{i})/p} + p^{k−1} ∑_{i,n} a_{i}(n) q^{(wn^{2}+b_{i})p} (mod m) , (6)

and f|T_{p} again belongs to M_{k}(N). We claim that Ord_{m}(f|T_{p}) < ∞ for every sufficiently large prime p and Ord_{m}(f|T_{p}) > C for almost every p, for any given constant C. Taking C = \frac{kN^{2}}{12} ∏_{l|N}(1 − l^{−2}) gives a contradiction to Sturm’s theorem.

To see that Ord_{m}(f|T_{p}) < ∞, we observe that only finitely many of the infinitely many exponents on the right-hand side of (6) can coincide, so that the expression cannot vanish identically modulo m. Indeed, if (wn^{2} + b_{i})p^{±1} = (wl^{2} + b_{j})p^{±1} for some n ≠ l, then w(n + l)(n − l) = b_{j} − b_{i} implies that both n and l are bounded, while if (wn^{2} + b_{i})p = (wl^{2} + b_{j})p^{−1} then w(pn + l)(pn − l) = b_{j} − p^{2}b_{i} gives the same conclusion if no b_{j} is divisible by p^{2}.

For the reverse direction, we observe that if C < p < x and Ord_{m}(f|T_{p}) = h < C, then we must have h = (wn^{2} + b_{i})/p for some n and i and that this n is then bounded by \sqrt{Cx − b_{i}}. Since each triple (n, i, h) gives at most one prime p = (wn^{2} + b_{i})/h and the number of i’s and h’s is bounded, this shows that for x → ∞ there are O(\sqrt{x}) primes p < x and congruent to 1 modulo N with Ord_{m}(f|T_{p}) < C, and this proves the claim since the total number of primes < x in this congruence class is ≫ x/ log x by Dirichlet’s theorem.

□

The following lemma follows from the standard fact that if f(z) ∈ M_{k}(N), then f (z + \frac{s}{t}) ∈ M_{k}(Nt^{2}).

Lemma 2. Let f(z) = ∑_{n=0}^{∞} a(n)q^{n} be a modular form in M_{k}(N, χ) and let d := gcd(r, t). Then

f_{r,t}(z) = ∑_{n≡r mod t} a(n)q^{n}

is the Fourier expansion of a modular form in M_{k} (\frac{Nt^{2}}{d} ) .

We now combine these facts to establish the main theorem of this section.

Main Theorem 2. For any arithmetic progression r ( mod t), there are infinitely many integers M ≡ r (mod t) for which p(M) is odd, provided there is one such M. Furthermore, if there does exist an M ≡ r (mod t) for which p(M) is odd, then the smallest such M is less than C_{r,t}. where

C_{r,t} := \frac{2^{23}A · 3^{7}t^{6}}{d^{2}} ∏_{p|6t} (1 − \frac{1}{p^{2}} ) − A.

where d := gcd(24r − 1, t) and A > \frac{t}{24} is a power of 2.

Proof. Recall from Proposition 1 that

f_{t,A}(z) := \frac{η(24z)}{η(48z)}Δ^{A}(24tz) = ∑_{n≥1} a_{t}(n)q^{24n−1} ∈ S_{12A}(1152t, χ).

and

f_{t,A}(z) ≡ ∑_{n=0}^{∞} p(n)q^{24n−1} ∑_{n=0}^{∞} q^{24At(2n+1)^{2}} mod 2.

Let d := gcd(24r − 1, t). Therefore by Lemma 2 we define

f_{24r−1,24t}(z) = ∑_{n≡24r−1 mod 24t} a_{t}(n)q^{n} ∈ S_{12A} (\frac{2^{13} · 3^{4}t^{3}}{d} ) ,

which when reduced mod 2 is:

f_{24r−1,24t}(z) ≡ ∑_{n≡r mod t} p(n)q^{24n−1} ∑_{n=0}^{∞} q^{24At(2n+1)^{2}} mod 2.

Note that the arithmetic progression r mod t corresponds to the arithmetic progression 24r − 1 mod 24t. If p(M) is odd for at least one M ≡ r (mod t) but only finitely many, then the mod 2 factorization above contradicts Lemma 1. This proves that if p(M) is odd for at least one M ≡ r (mod t), then p(M) is odd for infinitely many such M.

The computation of the constant C_{r,t} follows easily from the bound in Sturm’s theorem.

□

This theorem then proves that if 0 ≤ r < t, and if p(M) is ever odd for an M ≡ r (mod t) (hence infinitely often), then the first odd value must occur where M < C_{r,t}. It is easy to verify that C_{r,t} < 10^{10}t^{7} since \frac{t}{12} > 2^{j} when we choose the minimal j such that 2^{j} > \frac{t}{24}. As a consequence of the two main theorems we find that the conjecture holds for an arithmetic progression r (mod t) provided there is at least one N ≡ r mod t for which p(N) is odd. By computing p(n) mod 2 for all n ≤ 5, 000, 000 we found that every arithmetic progression with modulus t ≤ 100, 000 contains an integer M for which p(M) is odd. Therefore we obtain:

Main Corollary. For all 0 ≤ r < t ≤ 10^{5}, there are infinitely many integers M ≡ r (mod t) for which p(M) is odd.

3. Acknowledgements

I am indebted Ken T. Burrell ( Universal Analytics, Inc.) whose computations are the content of the Main Corollary. The computations were completed on a CRAY C-90 at the San Diego Supercomputing Center. I am indebted to Andrew Granville for his advice regarding this research. I also thank the referee whose comments improved the paper in many ways. In particular, the proof of Lemma 1 is an improved version of the original proof as suggested by the referee.

References

1. G. Andrews, The Theory of Partitions, Addison-Wesley, 1976.

2. G. Andrews and F. Garvan, Dyson’s crank of a partition, Bull. Am. Math. Soc. 18 (1988), 167-171.

3. A.O.L. Atkin, Proof of a conjecture of Ramanujan, Glasgow Math. J. 8 (1967), 14-32.

4. F. Garvan, A simple proof of Watson’s partition congruence for powers of 7, J. Australian Math. Soc. (A) 36 (1984), 316-334.

5. F. Garvan, New combinatorial interpretations of Ramanujan’s partition congruences mod 5, 7 and 11, Trans. Am. Math. Soc. 305 (1988), 47-77.

6. F. Garvan and D. Stanton, Sieved partition functions and q−binomial coefficients, Math. Comp. 55 191 (1990), 299-311.

7. F. Garvan and D. Stanton, Cranks and t−cores, Invent. Math. 101 (1990), 1-17.

8. B. Gordon and K. Hughes, Multiplicative properties of η−products II, A tribute to Emil Grosswald: Number Theory and related analysis, Cont. Math. 143 (1993), Amer. Math. Soc., 415-430.

9. M. Hirschhorn, On the residue mod 2 and mod 4 of p(n), Acta Arithmetica 38 (1980), 105-109.

10. , On the parity of p(n) II, J. Combin. Theory (A) 62 (1993), 128-138.

11. , Ramanujan’s partition congruences, Discrete Math. 131 (1994), 351-355.

12. M. Hirschhorn and D.C. Hunt, A simple proof of the Ramanujan conjecture for powers of 5, J. Reine Angew. Math. 336 (1981), 1-17.

13. M. Hirschhorn and M. Subbarao, On the parity of p(n), Acta Arith. 50 4 (1988), 355-356.

14. M. Knopp, Modular functions in analytic number theory, Markham, 1970.

15. N. Koblitz, Introduction to elliptic curves and modular forms, Springer-Verlag, 1984.

16. O. Kolberg, Note on the parity of the partition function, Math. Scand. 7 (1959), 377-378.

17. M. Newman, Construction and application of a certain class of modular functions, Proc. London Math. Soc. (3) 7 (1956), 334-350.

18. M. Newman, Construction and application of a certain class of modular functions II, Proc. London Math. Soc. (3) 9 (1959), 373-387.

19. T. R. Parkin and D. Shanks, On the distribution of parity in the partition function, Math. Comp. 21 (1967), 466-480.

20. J.-P. Serre, Divisibilité des coefficients des formes modulaires de poids entier, C.R. Acad. Sci. Paris (A) 279 (1974), 679-682.

21. J. Sturm, On the congruence of modular forms, Springer Lect. Notes 1240 (1984), Springer-Verlag.

22. M. Subbarao, Some remarks on the partition function, Amer. Math. Monthly 73 (1966), 851-854.

23. G.N. Watson, Ramanujan’s Vermutung über Zerfällungsanzahlen, J. Reine Angew. Math. vol 179 (1938), 97-128.

Department of Mathematics, The University of Illinois, Urbana, Illinois 61801 E-mail address: ono@symcom.math.uiuc.edu