DIVISIBILITY AND DISTRIBUTION OF PARTITIONS INTO DISTINCT PARTS

JEREMY 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 sum is 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)

∑_{n=0}^{∞} Q(n)q^{n} = ∏_{n=1}^{∞} (1 + q^{n}) = 1 + q + q^{2} + 2q^{3} + 2q^{4} + 3q^{5} + ...  (1)

A problem that naturally arises in the study of a combinatorial function such as Q(n) is that of divisibility 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 is randomly 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 2^{k} for any natural number k. Except in a few cases [1], it seems hopeless that combinatorial arguments will settle these problems in general, and so we must turn to the analysis 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 value of Q(n) is ≫ log log X. Since the number of primes p < X is asymptotically X/log X, this is a sparse subset of the prime numbers. Moreover, Rickert’s theorem does not preclude the possibility that every prime p dividing Q(n) does so only once. Using the theory of modular forms, we will establish the following

Theorem 1. For any prime number p ≥ 5,

lim inf_{N→∞} \frac{#\{n < N : Q(n) ≡ 0 (mod p)\}}{N} ≥ \frac{1}{p}  (2)

Date: July 25, 2000.

1991 Mathematics Subject Classification. Primary 11P83; Secondary 05A17.

Since 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 the Ramanujan type modulo powers of 5 and 7 using methods based on Atkin’s work on the classical partition 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 n

Q(an + b) ≡ 0 (mod p)  (3)

It turns out that the values of a guaranteed by Theorem 2 are typically quite large. In §4 we present a few of the simplest such congruences. These supercombinatorial congruences arise from an inherent regularity of the generating function rather than some combinatorial property of 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 many n such that p(n) ≡ r (mod M). Although this question remains open, Ono [10] has found a 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 primes p ≥ 5 and prove the following

Theorem 3. Let p ≥ 5 be prime. Suppose there is one n_{0} ≡ −24^{−1} (mod p) such that p ∤ Q(n_{0}). Then

#\{n < N : Q(n) ≡ r (mod p)\} ≫_{p} \begin{cases}N & if r ≡ 0 (mod p) \\ \frac{N}{log N} & if r ≢ 0 (mod p) \end{cases}

Moreover, if such an n_{0} exists then n_{0} ≤ 32p(p − 1).

2. Preliminaries

In many instances the generating functions for combinatorial objects turn out to be closely related to modular forms, particularly to products of η functions (Recall that η(z) := q^{1/24}(q; q)_{∞} where (q; q)_{∞} := ∏_{n=1}^{∞} (1 − q^{n}) and q := e^{2πiz}). For this reason, we frequently use the following fact recorded in [3, 7, 8]

Theorem 4 (Gordon, Hughes, Ligozat, Newman). Let

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

be a product of η functions which satisfies the following criteria (i)

∑_{δ|N} δr_{δ} ≡ 0 (mod 24)

(ii)

∑_{δ|N} \frac{N}{δ} r_{δ} ≡ 0 (mod 24)

(iii)

∑ r_{δ} ∈ 2ℤ^{+}

(iv) For each d|N,

∑_{δ|N} \frac{(d, δ)^{2}r_{δ}}{δ} ≥ 0

Then, f(z) ∈ M_{k}(Γ_{0}(N), χ) where k = \frac{1}{2}∑ r_{δ} and

χ(ℓ) = (\frac{(−1)^{k} ∏ δ^{r_{δ}}}{ℓ} ) .

Here M_{k}(Γ_{0}(N), χ) is the finite dimensional ℂ - vector space of holomorphic modular forms of weight k, level N, and Nebentypus character χ. The condition (iv) ensures that f has nonnegative orders at the cusps. If f actually has positive orders at all cusps, then it is a cusp form, and we denote the corresponding space of cusp forms by S_{k}(Γ_{0}(N), χ). We use the notation M_{k}(Γ_{0}(N), χ)_{m} and S_{k}(Γ_{0}(N), χ)_{m} to denote the same spaces except the coefficients in the Fourier expansions of the relevant 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 the interested reader to [6] for a more detailed overview of modular forms.

Proposition 5. Suppose that f(z) = ∑_{n=0}^{∞} a(n)q^{n} is a modular form in M_{k}(Γ_{0}(N), χ).

(i) For any positive integer t,

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

is the Fourier expansion of a modular form in M_{k}(Γ_{0}(tN), χ) (ii) For any prime p,

f(z) | T (p) := ∑_{n=0}^{∞} a(pn) + χ(p)p^{k−1}a(n/p)

is the Fourier expansion of a modular form in M_{k}(Γ_{0}(N), χ) Moreover, both statements remain true if M_{k}(Γ_{0}(N), χ) is replaced by S_{k}(Γ_{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 M_{k}(Γ_{0}(N), χ)_{p}, where the operator U(p) acts on series expansions by

∑_{n=0}^{∞} a(n)q^{n} | U(p) := ∑_{n≡0 (mod p)} a(n)q^{\frac{n}{p}}

The following useful criterion allows us to check congruences for modular forms with a finite computation.

Proposition 6 (Sturm). Suppose f(z) = ∑_{n=0}^{∞} a(n)q^{n} ∈ M_{k}(Γ_{0}(N), χ) satisfies

(i) a(n) ∈ ℤ for all n (ii) a(n) ≡ 0 (mod m) for all n ≤ 1 + \frac{kN}{12} ∏_{p|N} (1 + \frac{1}{p})

Then, a(n) ≡ 0 (mod m) for all n.

We wish to study the function ∑_{n=0}^{∞} Q(n)q^{n} in the context of modular forms, but unfortunately this is almost certainly not the Fourier expansion of a modular form modulo any prime p ≠ 2. However, for primes p ≥ 5, it turns out that for a properly chosen function h_{p}(n),

∑_{n=0}^{∞} Q((h_{p}(n))q^{n}

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 S_{k}(Γ_{0}(2), χ), then

g(z) := \frac{f(z)}{η^{8}(z)η^{8}(2z)}

is a holomorphic modular form in M_{k−8}(Γ_{0}(2), χ)

Proof: By Theorem 4, η^{8}(z)η^{8}(2z) is a cusp form of weight 8 and level 2 and has the minimal order of vanishing of 1 at the cusps. Also, η^{8}(z)η^{8}(2z) can have no zeroes in the upper half plane. Therefore,

\frac{f(z)}{η^{8}(z)η^{8}(2z)}

is a modular function which is holomorphic for Im z > 0 and has nonnegative orders at the cusps. That is, g(z) is in M_{k−8}(Γ_{0}(2), χ).

Theorem 8. Let p ≥ 5 be prime and let χ be the quadratic character defined by χ(d) = (\frac{2}{d}). Then,

F_{p}(z) := ∑_{n=0}^{∞} Q (\frac{pn − 1}{24}) q^{n} ∈ S_{4(p−1)}(Γ_{0}(1152), χ)_{p}

Proof : Let

a = 16 − (p mod 24)
b = (p mod 24) − 8

Using Theorem 4 we can check that

f_{p}(z) := η^{pa+1}(2z)η^{pb−1}(z) ∈ S_{4p}(Γ_{0}(2))

and therefore

f_{p}(z) | U(p) ≡_{p} f_{p}(z) | T (p) ∈ S_{4p}(Γ_{0}(2))_{p}

By Lemma 7,

f_{p}(z) | U(p) ≡ η^{8}(z)η^{8}(2z)g_{p}(z) (mod p)

where g_{p}(z) ∈ M_{4p−8}(Γ_{0}(2)). To prove the theorem we will write f_{p}(z) | U(p) (mod p) in a second way.

f_{p}(z) | U(p) = \frac{η(2z)}{η(z)}η^{a}(2pz)η^{b}(pz) | U(p)
= ∑_{n=0}^{∞} Q(n)q^{n+ \frac{p(2a+b)+1}{24}} | U(p) ∏_{n=1}^{∞} (1 − q^{2n})^{a}(1 − q^{n})^{b}

Therefore,

∑ Q(n)q^{\frac{n}{p} + \frac{p(2a+b)+1}{24p}} = \frac{f_{p}(z) | U(p)}{∏_{n=1}^{∞} (1 − q^{2n})^{a}(1 − q^{n})^{b}}
≡ q^{\frac{(2a+b)}{24}} η^{8−a}(2z)η^{8−b}(z)g_{p}(z) (mod p)

and so

∑ Q(n)q^{\frac{24n+1}{24p}} ≡ η^{8−a}(2z)η^{8−b}(z)g_{p}(z) (mod p)  (4)

One can verify using Theorem 4 that

η^{8−a}(48z)η^{8−b}(24z) ∈ S_{4}(Γ_{0}(1152), χ)

and so replacing q by q^{24} in (4) gives the result. Remark 9. Let

σ_{p} = −24^{−1} (mod p)
r_{p} = p (mod 24)

Then we also have the following representation for F_{p}(z):

F_{p}(z) = ∑_{n=0}^{∞} Q (pn + σ_{p}) q^{24n+r_{p}}

3. Divisibility of Q(n)

Theorem 8 reveals for any prime p ≥ 5 that certain values of Q(n) are actually Fourier coefficients modulo p of modular forms. The role of modular forms in number theory is deep and detailed, and in particular there have been many observations on the arithmetic properties of their Fourier coefficients. Theorem 1 is now an immedaite corollary of the following result of Serre [13]:

Theorem 10. Suppose that

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

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). Then

lim_{N→∞} δ_{m}(N) = 1

Theorem 1 makes clear that Q(n) is divisible by p for almost every n in a certain arithmetic progression modulo p, but tells nothing about Q(n) outside of this progression. Here we shall take the naive view that Q(n) is randomly distributed modulo p for n ≢ σ_{p} (mod p). Let δ_{p}(N) denote the proportion of n ≤ N such that Q(n) is divisible by p.

Conjecture 11. For primes p ≥ 5,

lim_{N→∞} δ_{p}(N) = \frac{2}{p} − \frac{1}{p^{2}}

For example, we have computed δ_{5}(1000000) = .34856 and the predicted value for lim_{N→∞} δ_{5}(N) is \frac{9}{25}.

It is interesting to compare the rather unexpected behavior of Q(n) modulo primes p ≥ 5 with the theorems of Gordon and Ono [5], who show that δ_{m}(N) → 1 if m is a power of 2. This results from the fact that the values of Q(n) are congruent modulo m to the Fourier coefficients of (integer weight) modular forms, while in the case of primes p ≥ 5, this is true only the for the values Q (pn + σ_{p}) modulo p.

4. Congruences for Q(n)

Since Q(pn+σ_{p}) ≡ 0 (mod p) for almost all n, it is not surprising that congruences in arithmetic subprogressions are eventually common. In [13], Serre proved the following wonderful result concerning Hecke operators and reductions modulo M of cusp forms, which yields the proof of Theorem 2.

Theorem 12. A positive proportion of primes p ≡ −1 (mod N) satisfy f(z) | T (p) ≡ 0 (mod M) for all f ∈ S_{k}(Γ_{0}(N), χ)_{M} Proof of Theorem 2 : Let m denote any prime such that

∑_{n=0}^{∞} Q (\frac{pn − 1}{24}) | T (m) ≡ 0 (mod p)  (5)

Then,

Q (\frac{pnm − 1}{24}) + m^{4(p−1)−1} (\frac{2}{m}) Q ( \frac{\frac{pn}{m} − 1}{24}) ≡ 0 (mod p)  (6)

for all n. So, whenever (n, m) = 1, we have

Q (\frac{pnm − 1}{24}) ≡ 0 (mod p)  (7)

To construct congruences in arithmetic progressions modulo p, we simply let n = 24mk + β, where β ≡ p^{−1}m^{−1} (mod 24) and m ∤ β. Then equation 7 becomes

Q (pm^{2}k + \frac{pmβ − 1}{24}) ≡ 0 (mod p)  (8)

From Serre, we know that a positive proportion of the primes m ≡ −1 (mod 1152) satisfy (5), which establishes the theorem.

In light of Sturm’s criterion, finding such values of m amounts to a finite computation. For example, we have found that (5) holds for the pairs (p, m) = (5, 61) and (7, 37). Notice that although Serre’s theorem guarantees infinitely many m ≡ −1 (mod 1152), we typically find that (5) holds for smaller values of m. From this data, we may write down the following examples of congruences for Q(n):

Q(18605n + 216) ≡ 0 (mod 5)
Q(9583n + 205) ≡ 0 (mod 7)

5. Distribution of Q(n)

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. However, using the following theorem of Serre, we can do better by proving Theorem 3.

Theorem 13. Suppose that F (z) := ∑_{n=1}^{∞} a(n)q^{n} is an integer weight cusp form with coefficients in ℤ. If m is a positive integer, then there is a set of primes S_{m} of positive density with the property that

a(np^{r}) ≡ (r + 1)a(n) (mod m)

whenever p ∈ S_{m}, r is a positive integer, and n is coprime to p.

Proof of Theorem 3 : Fix p ≥ 5 and let S_{p} denote the set of primes for F_{p}(z) guaranteed by Theorem 13. The case r ≡ 0 (mod p) follows from Theorem 1. Otherwise recall the assumption that there is some n_{0} = (n − 1)/24 such that

Q (\frac{n − 1}{24}) ≡ a ≠ 0 (mod p)

Hence there exists a prime ℓ ∈ S_{p} such that for 1 ≤ b ≤ p the p numbers

Q (\frac{nℓ^{b} − 1}{24}) ≡ (b + 1)a (mod p)

cover all of the residue classes modulo p. Because p is odd, for all but possibly finitely many primes m ∈ S_{p} we know that that the p numbers

Q (\frac{nℓ^{b}m − 1}{24}) ≡ 2Q (\frac{nℓ^{b} − 1}{24}) ≡ 2(b + 1)a (mod p)

cover all of the residue classes modulo p. Since S_{p} contains a positive proportion of the primes m, we have

#\{n ≤ N : Q(n) ≡ r (mod p)\} ≫ π(N) ≫ \frac{N}{log N}

The upper bound on n_{0} 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 all primes 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.

6. Examples

In view of the small dimensions for spaces of cusp forms of low weight and with the help of Sturm’s criterion, it is worthwhile to write down explicitly F_{p}(z) modulo p for some small primes p.

Proposition 14.

∑_{n=0}^{∞} Q(5n + 1)q^{n} ≡ \frac{(q; q)_{∞}^{11}}{(q^{2}; q^{2})_{∞}^{3}} (mod 5)

Proof: Using Sturm’s theorem, we find that

\frac{η^{56}(2z)}{η^{16}(z)}|U(5) ≡ \frac{η^{38}(z)η^{8}(2z)}{η^{6}(5z)} (mod 5)
≡ η^{8}(z)η^{8}(2z) (mod 5)

and therefore

F_{5}(z) ≡ \frac{η^{11}(24z)}{η^{3}(48z)} (mod 5)

9

and the proposition follows.

Using very similar computations, we can find relationships modulo 7 and 11. We employ the classical weight k Eisenstein series E_{k}(z) defined by

E_{k}(z) := 1 − \frac{2k}{B_{k}} ∑_{n=1}^{∞} σ_{k−1}(n)q^{n}

where B_{k} is the kth Bernoulli number and

σ_{k−1}(n) := ∑_{d|n} d^{k−1}

Proposition 15.

∑_{n=0}^{∞} Q(7n + 2)q^{n} ≡ \frac{(q; q)_{∞}^{9}}{(q^{2}; q^{2})_{∞}} (2E_{8}(z) − E_{8}(2z)) (mod 7)

Proposition 16.

∑_{n=0}^{∞} Q(11n + 5)q^{n} ≡ 7(q; q)_{∞}^{5}(q^{2}; q^{2})_{∞}^{3}(E_{6}(2z) + E_{6}(z)) (mod 11)

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 in Math. 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, Divisibilité de certaines fonctions arithmé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.

The Pennsylvania State University, University Park, PA 16802

 E-mail address: lovejoy@math.psu.edu