Arithmetic properties of restricted partition functions

Christopher C. Mihelich

mihelich@fas.harvard.edu

(617) 493-2083

under the direction of Professor William Stein

April 1, 2002

Introduction. A partition of an integer n is a representation of n as the unordered sum of several positive integers; for example, the different partitions of 4 are represented by the expressions

4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.

The unrestricted partition function, denoted by p(n), is the number of partitions of n. Mathematicians have also studied a vast variety of restricted partition functions, which count only those partitions of a number n that satisfy some auxiliary arithmetic constraint. Here we shall be concerned with the functions p_{k}(n) for integral k ≥ 2, which are the numbers of partitions of n into parts indivisible by k. In particular, the function p_{2}(n), which has received much more attention from researchers than the other p_{k}(n), counts partitions of n into odd parts and will be called the odd-partition function in this paper. In the literature it is more often denoted Q(n) and called the distinct-partition function on account of a well-known theorem of Euler that a positive integer n has the same number of partitions into odd parts as of partitions into distinct parts.

Partition functions satisfy many intriguing combinatorial identities, some of them much more surprising and difficult to prove than Euler’s theorem quoted above, and such identities remain an active field of research. But early in the twentieth century, partition theory acquired a new aspect when the Indian prodigy Ramanujan stunned his British hosts, who had just shown him a table of computed values of p(n), by noting that every fifth value was a multiple of five, every seventh was a multiple of seven, and every eleventh was a multiple of eleven. More precisely, the congruences

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

now known as the Ramanujan congruences, appeared to hold for all n. Thitherto it had occurred to no one that a partition function might have properties like that. Ramanujan’s paper [22] proved the congruences (1) and inaugurated the arithmetic study of partition functions.

Ramanujan further conjectured congruences analogous to (1) modulo higher powers of 5, 7, and 11, and partition theorists needed several decades to prove them all. The correct congruences (Ramanujan guessed incorrectly for powers of 7) are that

p(n) ≡ 0 (mod 5^{a})  if 24n ≡ 1 (mod 5^{a});  (2)
p(n) ≡ 0 (mod 7^{1+⌊a/2⌋}) if 24n ≡ 1 (mod 7^{a}); and  (3)
p(n) ≡ 0 (mod 11^{a})  if 24n ≡ 1 (mod 11^{a}).  (4)

Ramanujan himself managed to sketch a proof of (2), although his untimely death in 1920 prevented him from publishing the manuscript containing it (his so-called “lost manuscript,” which Berndt and Ono have recently edited [5]). The first published proofs of (2) and (3) in their full generality were given in 1937 by Watson [26]. Three decades later A. O. L. Atkin, using improved techniques and aided by computing machines, managed to dispose of the general case of (4), settling the remainder of Ramanujan’s conjecture. It remained unclear, however, whether analogues of Ramanujan’s congruences might exist for many primes other than 5, 7, and 11. Ahlgren and Ono [1] have very recently answered this question in the affirmative, proving that p(n) is divisible throughout some arithmetic progression by any given number relatively prime to 6 (previously Ono had proven this claim in [18] for prime moduli other than 2 and 3). The behavior of p(n) modulo powers of the primes 2 and 3, which are often troublesome in any business involving modular forms, appears much less regular and is ill understood. It is known (see references in [18]) that p(n) is infinitely often even and infinitely often odd, but it is infuriating that we still do not know whether p(n) is infinitely often divisible by 3.

Ahlgren and Ono’s investigations differ considerably from those of their predecessors of the 1970s and before by their use of power tools developed in the 1970s. In that decade the modern algebraic approach to modular forms, now renowned for its successful application to Fermat’s conjecture, began to develop, and Serre obtained several deep theorems on the divisibility of Fourier coefficients of modular forms that have stood in the foreground in much recent work. Ono’s paper [18], for instance, depends on the Shimura lift of modular forms of half-integer weight and on deep theorems of Serre about the divisibility of Fourier coefficients of modular forms, both modern tools devised in the 1970s. Before these tools, the use of modular forms in partition theory was basically a matter of elementary (though often intricate) complex analysis.

Arithmetic research on the odd-partition function p_{2}(n), whose divisibility properties are not entirely analogous to those of p(n), began later but crossed similarly from classical into modern methods. In 1969 Rødseth [23], using purely analytical methods, proved that p_{2}(n) enjoys congruence properties modulo powers of 5 in Ramanujan’s style, of which the first is

p_{2}(125n + 26) ≡ 0 (mod 5).

We might then expect similar congruences modulo powers of 7, but Rødseth also proved that the natural analogues of Ramanujan’s powers-of-7 congruences do not hold for p_{2}(n). The odd-partition function also strongly differs from p(n) in its behavior at 2. Whereas the parity of p(n) appears irregular, the number p_{2}(n) is almost always even: a rather short argument using a theorem of Euler shows that p_{2}(n) is odd if and only if n is pentagonal. Rødseth proved much more; in fact p_{2}(n) is often divisible by rather high powers of 2. For instance, whenever 24n + 1 has odd valuation at a prime congruent to 23 modulo 24, the quantity p_{2}(n) must be divisible by 2^{11}. This is a surprising property, but the full truth is more surprising: the following theorem, proven by Gordon and Ono in 1997 [8], shows that p_{2}(n) is usually divisible by any given power of 2.

Theorem 1 (Gordon and Ono, 1997) Let N ≥ 2 be an integer and suppose that ℓ is a prime such that ℓ^{v_{ℓ} N} ≥ \sqrt{N}. Then for each positive integer κ we have

#\{n ≤ L : v_{ℓ} p_{N}(n) < κ\} = O_{N,κ} (\frac{L}{log^{α} L})

for some positive constant α = α(N).

The form of the error bound reflects the dependence of Gordon and Ono’s proof on a theorem of Serre [24] that if the Fourier coefficients of a holomorphic modular form of integral weight on some congruence subgroup lie in some algebraic-integer ring, then they are almost always divisible by any given positive integer with the same qualitative bound on the number of exceptions as appears in Theorem 1. The proof in [8] constructs for each κ a holomorphic integer-weight form on some congruence subgroup whose Fourier coefficients are congruent modulo ℓ^{κ} to the values of p_{ℓ}(n), whence p_{ℓ}(n) inherits the desired ℓ-adic behavior from the coefficients of that holomorphic form by way of Serre’s theorem.

Gordon and Ono’s theorem is certainly a strong result, an apt illustration of the power in partition theory of Serre’s theorems on the divisibility properties of modular forms. But it also showcases the principal drawback to basing one’s analysis on Serre’s theorems: the results are totally inexplicit. Gordon and Ono’s theorem tells us that if we fix a power of 2, the value of p_{2}(n) will almost always be divisible by that power of 2. Their theorem does not, however, tell specifically which n have the property that p_{2}(n) is divisible by a large power of 2: the only answer it will give is “most of them,” which is nothing if not vague. The impossibility of squeezing any concrete examples of large values of v_{2} p_{2}(n) out of Gordon and Ono’s result is fairly frustrating, especially in view of how much better Rødseth’s work mentioned earlier did for small powers of 2.

In this paper we shall demonstrate that classical techniques, especially those of Rødseth in the work cited above, can be applied to prove an explicit lower bound on the valuation at ℓ of p_{N}(n) for certain small values of N. Specifically, we shall show the following:

Theorem 2 Let N ∈ {2, 3, 4, 5, 7, 9} and let ℓ be the prime dividing N. Write N′ = 24/(N − 1). For each integer n, the valuation at ℓ of p_{N}(n) is at least one-fourth of the number of primes p ≢ 1 (mod N′) such that v_{p}(N′n + 1) is odd.

This estimate will be proved by means of the elementary theory of modular forms and will be used in combination with the prime-number theorem and Dirichlet’s theorem on primes in arithmetic progressions to prove Theorem 1 without invoking Serre’s theory.

The bound in Theorem 2 is not sharp, but for the odd-partition function at least, it is possible to evaluate the valuation of p_{2}(n) exactly in favorable circumstances. One such circumstance is a restriction on the prime factors of 24n + 1:

Theorem 3 Suppose that 24n+1 is the product of 2s distinct primes congruent modulo 24 to 5 and 2t distinct primes congruent modulo 24 to 7. Then v_{2} p_{2}(n) = 2s + 3t.

We can also exhibit necessary and sufficient conditions, in terms of the prime factorization of 24n + 1, for v_{2} p_{2}(n) to equal any specific value not greater than 4, by virtue of the following theorem:

Theorem 4 Suppose that v_{2} p_{2}(n) < 5 and write N′ := 24n + 1. Let s_{i} denote the number of primes congruent modulo 24 to i at which N′ has odd valuation. Then s_{11} = s_{13} = s_{17} = s_{19} = s_{23} = 0 and

v_{2} p_{2}(n) = s_{1} + s_{5} + \frac{3}{2}s_{7} + ∑_{{p prime \atop v_{p} N′≡1(2)}} v_{2} (\frac{v_{p} N′ + 1}{2}) .

The terms on the right-hand side of Theorem 4 are nonnegative integers, so it is straightforward to enumerate the classes of N′ for which v_{2} p_{2}(n) = κ for each 0 ≤ κ ≤ 4, as we shall do later. Perhaps the prettiest example of these results is that

v_{2} p_{2} (\frac{p^{15} − 1}{24}) = 4 for each prime p ≡ 1 (mod 24).

Finally, it is evident from Theorem 4 that p_{2}(n) is odd whenever (in fact, exactly when) N′ is square, and if N′ is prime, then v_{2} p_{2}(n) = 1. Combining these observations with Theorem 3, we have:

Corollary 5 As n ranges through all nonnegative integers, the quantity v_{2} p_{2}(n) assumes each nonnegative integral value infinitely often.

Notation. We pause here to declare several notations that will appear without further comment in much of the sequel.

We write ℍ for the upper half-plane

ℍ := {x + iy : y > 0}

and denote by τ a variable that assumes values in ℍ. We put q = e^{2πiτ}, which takes nonzero values in the open unit disc and approaches zero as the imaginary part of τ increases without bound. The power notation q^{r} denotes the branch e^{2πirτ}.

The notation (a, b) means the greatest common divisor of a and b, and we write “a and b are relatively prime” as a ⊥ b. If p is prime and r is rational, then v_{p} r denotes the valuation of r at p, with the convention that v_{p} 0 = +∞. We shall also require clamped valuations v_{p}^{≤κ} ...

We shall occasionally write x ↑(y) in place of x^{y} when the exponent y is syntactically complicated.

1 Preliminaries concerning modular forms

In this section we recall what we shall later require of the theory of modular forms, a class of complex-analytic functions on the upper half-plane ℍ := {x + iy : y > 0} with stringent symmetry properties. Research on partitions frequently turns on the theory of modular forms because the generating functions of partition functions are often closely related to modular forms. For instance, the generating function in q of the unrestricted partition function is precisely q^{1/24}/η(τ), where η(τ) is a modular form that we shall discuss in detail below.

This section may be divided into two parts. The first of these recalls the fundamentals of the theory of modular forms. I carefully chose the word “recall” here because we shall sketch or omit many proofs on the ground that there are already several good sources for this material in your local mathematics library. Shimura’s book [25], a treatise by a revered expert in the algebraic side of the theory of modular forms that has the virtues of developing theory in considerable generality and of omitting or outsourcing relatively few details, is worth reading even though it is not always an easy read and does not deal with divisibility properties of Fourier coefficients of modular forms. The books of Apostol [3] and of Knopp [12] are gentler and more analytic introductions to modular forms. Knopp’s book is particularly good for an aspiring partition theorist because it spends several chapters on self-contained proofs of Ramanujan’s congruences modulo powers of 5 and 7; its main drawback is that it does not treat the Hecke operators, which are crucially important in partition theory as well as in other applications of the theory of modular forms. Apostol does treat the Hecke operators and some aspects of the analytic theory that Knopp omits; his book’s principal weakness is its relative lack of generality, as it deals mainly with forms on the full modular group and is thus of narrower scope than either Shimura’s or Knopp’s. A final reference is Diamond and Im’s survey article [7], which covers (without proofs) the algebraic theory of modular forms from its basics to some of the much more sophisticated ideas concerning the modularity of elliptic curves that were used in the renowned proof of Fermat’s conjecture; this article does a good job of showing the reader what theory is available and giving him references that will enable him to locate all of it.

The second part, which is more specialized, discusses properties of the η-function and of certain important linear operators on spaces of modular forms. We shall omit most of the proofs in this part for a different reason: they are all easy and of roughly the same character, usually just exercises in matrix manipulation and basic number theory, sometimes long but never hard. The interested reader might find it instructive to prove those results of this section which he does not recognize.^{1}

The concept of modular form. Any class of functions with strong symmetry properties is likely to find importance in mathematics. The first examples a student learns are trigonometric functions on the real line such as sin x, a function arising from Euclidean planar geometry whose importance profoundly transcends the context in which it arose—think of Fourier analysis—because of its symmetry property, namely its invariance under the group 2πℤ of translations of the real line.

Modular forms may be considered a similar example of functions that are important because of their symmetry. They are a class of complex-analytic functions on the upper half-plane ℍ that are almost invariant under large groups of automorphisms of ℍ. Modular forms originally arose in the theory of elliptic functions, which mathematicians do not discuss much these days, just as mathematicians do not often think of sin x as the length of one side of a certain triangle, although that was its original definition. The symmetry properties of modular forms have exalted them above their original source, and in particular are the principal reason why partition functions enjoy such beautiful properties.

The group of automorphisms of ℍ in question is the modular group SL_{2}(ℤ) of 2 × 2 matrices of integer entries and determinant 1. A matrix A = ({a \atop c} {b \atop d}) ∈ SL_{2}(ℤ) acts on τ ∈ ℍ by the rule

Aτ := \frac{aτ + b}{cτ + d},

which one easily checks is a group action by analytic automorphisms. For each subgroup Γ of SL_{2}(ℤ) of finite index, a modular function on Γ is a meromorphic function f(τ) on ℍ that enjoys the symmetry property

f(Aτ) = f(τ) for all A ∈ Γ  (5)

and that is “meromorphic at the cusps” in a sense that we shall explain in a moment. Aside from that last technical condition, this definition is a natural analogue of the symmetry property of the trigonometric functions. The definition of a modular form, however, allows somewhat less elegant behavior: specifically, a modular form f(τ) satisfies not necessarily (5) but only

f(Aτ) = ν_{f} ( \begin{matrix}a & b \\ c & d \end{matrix} ) (cτ + d)^{k}f(τ) for all A = ( \begin{matrix}a & b \\ c & d \end{matrix} ) ∈ Γ,

where k is real and ν_{f}({a \atop c} {b \atop d}) is a function on Γ that assumes complex values of modulus 1. One calls k the weight of f and ν_{f}({a \atop c} {b \atop d}) the multiplier system of f; thus a modular function is a form of weight 0 and trivial multiplier system ν_{f}({a \atop c} {b \atop d}) ≡ 1. The considerable generality in the definition of a modular form is useful mainly to avoid excluding the Dedekind η-function, a modular form of weight 1/2 and a fairly complicated multiplier system that is of central importance in applications of modular forms to partition theory. We write A_{k}(Γ, ν) for the complex vector space of modular forms on Γ of weight k and multiplier system ν, or just A_{k}(Γ) when ν ≡ 1 is the trivial multiplier system.

Any modular form f satisfies f(τ +p) = f(τ) for the least positive integer p such that the translation (^{1} {p \atop 1}) is contained in Γ; there exists such an integer because otherwise the translations would represent infinitely many distinct cosets of Γ in SL_{2}(ℤ), contradicting the assumption that Γ has finite index. Thus f has a Fourier series

1Unless, of course, he is the thesis examiner, in which case he will probably ask me to prove them.

f(τ) = ∑_{i} c(i)q^{i/p},

which we may ...

[Precise definition of modular forms and important subgroups.]

[Properties of modular forms. Periodicity, Fourier series already handled above. Define order at points, both analytic and group-relative. A holomorphic function is constant. Univalent functions and their importance.]

Dedekind’s η-function. So far we have discussed few examples of modular forms. Here we discuss the most important modular form of all, namely Dedekind’s function η(τ), in terms of which most if not all of the forms that partition theorists care about can be expressed. Dedekind’s function is so central in partition theory because many of the generating functions in q of restricted partition functions are closely related to η(τ). So that these relations shall be apparent, we pause before defining η(τ) to discuss the generating functions of the partition functions we have introduced.

Let us define the product

ϕ(τ) = ∏_{i≥1}(1 − q^{i}),

which converges rather rapidly for τ ∈ ℍ and represents an analytic function there, and let P (τ) and P_{N}(τ) denote the generating functions in q of p(n) and p_{N}(n) respectively. That is, put

P (τ) := ∑_{i} p(i)q^{i};
P_{N}(τ) := ∑_{i} p_{N}(i)q^{i}.

These generating functions can be expressed concisely in terms of ϕ as follows:

Proposition 6 We have P (τ) = 1/ϕ(τ) and P_{N}(τ) = ϕ(Nτ)/ϕ(τ).

Proof. We treat P (τ) first. The partitions of n are in bijection with sequences (a_{1}, a_{2}, …) of nonnegative integers, all but finitely many of which are zero, such that ∑_{i} ia_{i} = n. The correspondence is simply that a sequence (a_{i}) represents the partition of n into a_{1} ones, a_{2} twos, and so forth. Now if we expand the product

\frac{1}{ϕ(τ)} = ∏_{i≥1} \frac{1}{1 − q^{i}} = ∏_{i≥1} ∑_{j≥0} q^{ij}  (6)

without collecting terms of the same degree, then the general term in the expansion is

q ↑(1j_{1} + 2j_{2} + ⋯)

for some nonnegative integers j_{i}. Thus the coefficient of q^{n} in 1/ϕ(τ) is exactly the number of sequences (j_{i}) of nonnegative integers such that ∑_{i} ij_{i} = n. This number is just p(n), as we have noted; hence P (τ) = 1/ϕ(τ).

To treat P_{N}(τ), we note that ϕ(Nτ)/ϕ(τ) is exactly the product in (6) with all the factors with N | i suppressed. By similar combinatorial reasoning, the coefficient of q^{n} in this is the number of partitions of n with no parts divisible by N, as desired. □

Dedekind’s η-function is defined by appending a factor of q^{1/24} to ϕ(τ): we put

η(τ) := e^{iπτ/12}ϕ(τ) = q^{1/24} ∏_{i≥1}(1 − q^{i}).

Thus P (τ) = q^{1/24}/η(τ) and P_{N}(τ) = q^{(1−N)/24}η(Nτ)/η(τ). The reason for multiplying by q^{1/24} is that the product is, rather surprisingly, a modular form:

Theorem 7 For each ({a \atop c} {b \atop d}) ∈ SL_{2}(ℤ) we have

η (\frac{aτ + b}{cτ + d}) = ν_{η} ( \begin{matrix}a & b \\ c & d \end{matrix} ) (cτ + d)^{1/2}η(τ),

where ν_{η}({a \atop c} {b \atop d}) is a certain 24^{th} root of 1 given below.

The canonical reference for this theorem is Rademacher’s paper [21]. Other derivations using classical analysis may be found, for instance, written out in Apostol [3] and sketched in exercises in Andrews [2, ch. 5]. It is also possible to prove the theorem by induction on the length of ({a \atop c} {b \atop d}) as a word in the generators (^{1} {1 \atop 1}) and (_{1} ^{−1}) of SL_{2}(ℤ), although this is less enlightening; see for example Knopp [12].

The multiplier system ν_{η}({a \atop c} {b \atop d}) is not an unimportant detail. Partition theorists use the η-function as a building block to construct interesting modular forms on some Γ_{0}(N) whose multiplier system is at worst a Nebentypus character, and the proof that the multiplier system is in fact so civilized always requires analyzing expressions involving ν_{η}({a \atop c} {b \atop d}). Several explicit expressions for ν_{η}({a \atop c} {b \atop d}) are available. Of these the most elegant, but unfortunately also the least convenient in applications, is Rademacher’s expression in terms of the Dedekind sums: when c > 0 one has

ν_{η} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = exp(−\frac{πi}{4} + πi\frac{a + d}{12c} − πi ∑_{1≤μ<c}((\frac{μ}{c}))((\frac{aμ}{c}))),

where ((x)) = x − ⌊x⌋ − 1/2. The main deficiency of this expression is that its form does not proclaim that ν_{η}({a \atop c} {b \atop d}) is a 24^{th} root of 1; it looks like a 24c^{th} root in general, and this makes it difficult to simplify products of values of ν_{η}({a \atop c} {b \atop d}) that are suspected of being equal to ±1. More useful forms of the multiplier system express it as the product of some sort of Jacobi symbol and the complex exponential of 1/24 times a polynomial in the integers a, b, c, d, which is much more amenable to number-theoretic analysis. The cost (aside from elegance) is that these forms usually distinguish several cases or impose restrictions on a, b, c, d. Petersson [20] gives the general formula

ν_{η} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = \{ \begin{matrix}(\frac{d}{c})^{∗} exp \frac{iπ}{12}((a + d)c − bd(c^{2} − 1) − 3c) & if c is odd, \\ (\frac{c}{d})_{∗} exp \frac{iπ}{12}((a + d)c − bd(c^{2} − 1) + 3d − 3 − 3cd) & if c is even, \end{matrix}

where the modified Jacobi symbols (m/n)^{∗} and (m/n)_{∗} are given by

(\frac{m}{n})^{∗} = (\frac{m}{|n|});
(\frac{m}{n})_{∗} = (\frac{m}{|n|}) × \{ \begin{matrix}−1 & if m ≤ 0 and n < 0; \\ 1 & otherwise. \end{matrix}

A similar formula had appeared previously in Weber [27]. Newman [16] is willing to assume that a, c > 0 and a ⊥ 6, and he obtains the more concise formula

ν_{η} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = (\frac{c}{a}) exp \frac{iπ}{12}a(c − b − 3) for a, c > 0 and a ⊥ 6.

Using Newman’s formula requires working around a restriction, while using Petersson’s formulae requires keeping track of two cases, one for each possible parity of c, during a long computation. Because either choice is somewhat annoying, I prefer to use the following form of Petersson’s formulae. We define (m n) to equal (m/n)^{∗} when n is odd and (n/m)_{∗} when n is even; this function is not totally multiplicative in its second argument, but its multiplicative properties, which we shall derive in a moment, are pleasant enough for (m n) to be manipulated much like a Jacobi symbol. I claim now that

ν_{η} ( \begin{matrix}a & b \\ c & d \end{matrix} ) = (d c) exp \frac{iπ}{12}((a + d − 3)c − bd(c^{2} − 1) + 3(d − 1)(1 − c)^{3}) (7)

regardless of the parity of c. Indeed, if c is odd, then (1 − c)^{3} is a multiple of 8, and the last term inside the exponential above vanishes modulo 24. If instead c is even, then (1 − c)^{2} ≡ 1 (mod 8), and therefore

−3c + 3(d − 1)(1 − c)^{3} ≡ −3c + 3(d − 1)(1 − c) = 3d − 3 − 3cd (mod 24),

as required.

If converting Petersson’s formulae to (7) seems a cheap dodge, that is because it is a cheap dodge: we suppressed the distinction between (d/c)^{∗} and (c/d)_{∗} by defining a notation that represents either one as needed, and we effaced the difference between the polynomials in the complex exponentials by using a trick of arithmetic modulo 8. But although it is a cheap dodge, I find that using (7) in place of Petersson’s formulae cleans up many arguments somewhat. The uniform expression in (7) does not usually eliminate the need to consider cases modulo 2 or 3 at some point in an investigation, but it tends to delay the need to do so until the expressions involved have been thoroughly simplified, leaving less manipulation to be duplicated for the several cases. Moreover, using the notation (m n) sometimes allows the final answer to be expressed more uniformly than it could be with the conventional Jacobi symbol.

We pause to put on record the multiplicative properties of (m n), which it seems appropriate to prove here because the function (· ·) does not appear to have been defined before, and I expect its use could somewhat simplify existing treatments of the properties of η-products.

Lemma 8 Suppose that n, m_{1}, …, m_{r} are nonzero integers such that each m_{i} is relatively prime to n. Then (m_{1} … m_{r} n) = (m_{1} n) ⋯ (m_{r} n).

Suppose that m, n_{1}, …, n_{r} are nonzero integers with each n_{i} relatively prime to m. Then (m n_{1} … n_{r}) = (m n_{1}) ⋯ (m n_{r}) ζ, where ζ = −1 if all of the conditions

1. m ≡ 3 (mod 4),

2. some n_{r} is even, and

3. the number of i such that n_{i} ≡ 3 (mod 4) is odd

are satisfied, while ζ = 1 otherwise.

Proof. The functions (m/n)^{∗} and (n/m)_{∗} are both completely multiplicative in each argument. This observation is sufficient to prove the first claim in general, and it disposes of the cases of the second claim in which all the n_{i} have the same parity. Because condition 3 above means exactly that the product of the odd n_{i} is congruent modulo 4 to 3, it is sufficient to prove the second claim in the case when r = 2, the integer n_{1} is odd, and n_{2} is even.

For this purpose we write

m = sμ, n_{1} = s_{1}ν_{1}, n_{2} = s_{2}ν_{2},

where s, s_{1}, s_{2} ∈ {±1} and μ, ν_{1}, ν_{2} > 0, and compute straightforwardly that

(m n_{1}) (m n_{2}) (m n_{1}n_{2}) = (\frac{m}{n_{1}} )^{∗}(\frac{n_{2}}{m} )_{∗}(\frac{n_{1}n_{2}}{m} )_{∗}
= (\frac{s}{ν_{1}} ) (\frac{μ}{ν_{1}} ) (\frac{s_{2}}{μ} ) (\frac{ν_{2}}{μ} ) (−1)^{(s−1)(s_{2}−1)/4}

× (\frac{s_{1}}{μ} ) (\frac{s_{2}}{μ} ) (\frac{ν_{1}}{μ} ) (\frac{ν_{2}}{μ} ) (−1)^{(s−1)(s_{1}s_{2}−1)/4}

= (\frac{μ}{ν_{1}} ) (\frac{ν_{1}}{μ} ) (\frac{s}{ν_{1}} ) (\frac{s_{1}}{μ} ) (−1)^{(s−1)(s_{1}s_{2}+s_{2}−2)/4}. (8)

In the last expression, the products of Jacobi symbols can be rewritten using the reciprocity law for the Jacobi symbol. Moreover

s_{1}s_{2} + s_{2} − 2 ≡ s_{1} + 1 − 2s_{2} ≡ s_{1} − 1 (mod 4),

so the power of −1 appearing above is exactly (−1)^{(s−1)(s_{1}−1)/4}. Thus the last expression in (8) equals

(−1) ↑(\frac{1}{4}(ν_{1} − 1)(μ − 1) + \frac{1}{4}(ν_{1} − 1)(s − 1) + \frac{1}{4}(s_{1} − 1)(μ − 1) + \frac{1}{4}(s − 1)(s_{1} − 1))

= (−1) ↑((ν_{1} + s_{1} − 2)(μ + s − 2)/4)
= (−1) ↑((\frac{ν_{1} + s_{1}}{2} − 1) (\frac{μ + s}{2} − 1)) ,  (9)

which is −1 if and only if ν_{1} + s_{1} ≡ 0 (mod 4) and μ + s ≡ 0 (mod 4). Multiplying these congruences by s_{1} and s respectively, we find that they hold precisely when

s_{1}ν_{1} + 1 ≡ sμ + 1 ≡ 0 (mod 4).

But this means exactly that n_{1} ≡ m ≡ 3 (mod 4), as desired. □

Analytic properties of η-products. An η-product of level N is a function of the form

f(τ) = ∏_{δ|N} η(δτ)^{α_{δ}}

for some integers α_{δ}; most modular forms important in partition theory arise naturally as η-products or as linear combinations of η-products. ...

Linear operators on spaces of modular forms. Let A = ({a \atop c} {b \atop d}) ∈ GL_{2}^{+}(ℚ) be any matrix with rational entries and positive determinant. For any subgroup Γ of SL_{2}(ℤ) of finite index and any integer k, we can make A into a linear function on A_{k}(Γ) by setting

f(τ) | A := (det A)^{k/2}(cτ + d)^{−k}f(Aτ).

It is easily verified that f | AB = (f | A) | B. One might have been tempted to define f(τ) | A as simply f(Aτ), but the official definition has better invariance properties. For instance, we have f | B = f for all B ∈ Γ, for the factor (cτ + d)^{−k} in the definition cancels the (cτ +d)^{k} coming from the modularity property of f. Thus f | A is unchanged if A is multiplied on the left by an element of Γ. Moreover the power of the determinant in the definition ensures that f | rA = f | A for any rational r > 0, which is desirable because rA and A represent the same fractional linear transformation.

More generally, we can define an action of the group algebra ℂ[GL_{2}^{+}(ℚ)] on each A_{k}(Γ) by letting

f | (∑_{i} α_{i}A_{i}) = ∑_{i} α_{i}f | A_{i}.

There are several important classes of linear functions on modular-form spaces that are constructed in this way from collections of matrices. Here we shall define the ones we need and state their most important properties and uses; the proofs are all fairly straightforward, if sometimes tedious, exercises in matrix algebra and will be omitted.

We have said nothing so far about the range of elements of ℂ[GL_{2}^{+}(ℚ)]. There is no reason why a general element of ℂ[GL_{2}^{+}(ℚ)] should map A_{k}(Γ) back into itself; in general an element ∑_{i} α_{i}A_{i} maps A_{k}(Γ) only into A_{k}(Γ′), where

Γ′ = Γ ∩ ⋂_{i} A_{i}^{−1}ΓA_{i}.

Most such operators that are important, though, do map A_{k}(Γ_{0}(N)) into itself or at worst into A_{k}(Γ_{0}(N)′) with some other level N′.

We should finally note that although these operators need not respect the group of invariance of a modular form, they all map holomorphic forms to holomorphic forms and cusp forms to cusp forms. This is important in more algebraic investigations because the holomorphic forms or cusp forms of a given weight on a given group form a finite-dimensional vector space to which all the machinery of linear algebra applies. Particularly elegant cases are those in which a given M_{k}(Γ) or S_{k}(Γ) is one-dimensional, in which case the nonzero elements of that space are eigenvectors of any transformation, such as the Hecke operators defined below, that maps that vector space into itself. One thereby finds that the Fourier coefficients of those forms have strong multiplicativity properties. We shall not need this device in the sequel, but you may find a full discussion of one such case in Apostol’s treatment of the Hecke operators on M_{∗}(SL_{2}(ℤ)) in [3].

The operators U_{M}^{L}. The operators U_{M}^{L} defined for M, L ≥ 1 and M ⊥ L by the formula

U_{M}^{L} = M^{k/2−1} ∑_{0≤i<M} \binom{1 Li}{M};

in most applications L = 1 and M is prime. These operators are useful in arithmetic investigations because if f(τ) is a modular form with f(τ + L) = f(τ), then the Fourier coefficients of f(τ) | U_{M}^{L} comprise every M^{th} Fourier coefficient of f(τ): specifically, if f(τ) = ∑_{i} c(i)q^{i/L}, then

f(τ) | U_{M}^{L} = \frac{1}{M} ∑_{0≤j<M} ∑_{i} c(i) exp 2πii (\frac{τ + Lj}{M} ) /L

= ∑_{i} c(i)q^{i/(ML)} · \frac{1}{M} ∑_{0≤j<M} exp 2πiij/M

= ∑_{i} c(i)q^{i/(ML)} × \{ \begin{matrix}1 & if M | i, \\ 0 & otherwise \end{matrix}
= ∑_{i} c(Mi)q^{i/L}.

Usually f(τ) will be a modular form with Nebentypus on some Γ_{0}(N), in which case f(τ + 1) = f(τ) and we can take L = 1; other values of L can be useful when f is an η-product with a more complicated multiplier system. When L = 1 we use the more conventional notation U_{M} instead of U_{M}^{1}.

If the coefficients c(i) represent an arithmetic function of interest and one wants to prove special properties of c(i) when i is divisible by a large power of a prime p, the operator U_{p} may be the only operator needed in the proof. Atkin’s proof of Ramanujan’s congruences modulo powers of 5 and 7, which is presented in detail in Knopp [12], uses the operators U_{5} and U_{7} in this way, applying them iteratively to appropriate modular forms to extract the subsequences of {p(n)} that appear in the statement of the congruences.

The operators U_{M}^{L} exhibit a reasonable degree of respect for the level of a modular form. Specifically we have:

Proposition 9 Let N, M, L ≥ 1 be integers with L ⊥ NM, and let χ be a character of ℤ/(MN). Then for each integer k we have

U_{M}^{L} : A_{k}(Γ_{0}(M^{2}N), χ) → A_{k}(Γ_{0}(MN), χ).

...

[Special operators: U, Hecke operators, S, level-reducers. Interactions of different operators. Hecke eigenforms and their arithmetic importance.]

[Effect of special operators on eta products.]

2 The behavior of p_{2}(n) modulo 32

The methods that Rødseth employed in his 1969 paper [23], which we extend in the next section to prove Gordon and Ono’s theorem for six of the restricted partition functions p_{N}(n), give the most satisfying results on v_{2} p_{2}(n) presently known. First, however, in this section we consider several other methods for analyzing the 2-adic behavior of p_{2}(n). This survey will serve to show how much more powerful Rødseth’s methods are than their competition, and in the case of p_{2}(n) at least, the other methods provide supplementary information that will sharpen our later results.

We first evaluate p_{2} modulo 2 and 4 by methods involving classical analysis and the arithmetic of imaginary quadratic number fields, but nothing from the theory of modular forms. Thereafter we shall sketch an approach based on constructing simultaneous eigenforms of the Hecke operators by analytic methods of Newman [17] and of Gordon and Sinor [9], which I have used in [15] to determine precisely when v_{2} p_{2}(n) is 0, 1, 2, 3, or 4. Lovejoy [14] had previously used the same eigenform to advantage in his study of the divisibility of p_{2}(n) by powers of 5.

Jacobi’s triple product. Although modular forms are the partition theorist’s weapon of choice, it is possible to analyze the 2-adic behavior of p_{2}(n) to some nontrivial extent without modular forms. In particular, the parity of p_{2}(n) (which is usually even, as was noted above) can be evaluated elementarily in the following way.

Because (1 − x)^{2} ≡ 1 − x^{2} (mod 2), we have

\frac{ϕ(2τ)}{ϕ(τ)^{2}} = ∏_{i≥1} \frac{1 − q^{2i}}{(1 − q^{i})^{2}} ≡ 1 (mod 2),

and therefore ϕ(2τ)/ϕ(τ) ≡ ϕ(τ) (mod 2). Consequently p_{2}(n) has the same parity as the coefficient of q^{n} in ϕ(τ). But this coefficient vanishes except when n is a pentagonal number, by virtue of the surprising equation

ϕ(τ) = ∑_{i∈ℤ}(−1)^{i}q^{i(3i−1)/2},  (10)

originally obtained by Euler. Therefore p_{2}(n) is odd exactly when n is pentagonal. The result of (10) is a special case of the following classic theorem of Jacobi:

Theorem 10 (Jacobi’s triple-product theorem) For |q| < 1 and z ≠ 0 we have

∏_{i≥1}(1 − q^{2i})(1 + zq^{2i−1})(1 + z^{−1}q^{2i−1}) = ∑_{i} z^{i}q^{i^{2}}.

If we specialize z in Theorem 10 to a monomial in q, as we shall do in a moment, we can obtain infinite-product representations of many series of the form ∑_{i}(−1)^{i}q^{Q(i)}, where Q(i) is a quadratic form. Such series are called theta series on account of their similarity to the four theta functions on which the theory of elliptic functions rests (see, e.g., Whittaker and Watson [28]).

Jacobi obtained his triple-product theorem, and many more similarly frightening identities, in his groundbreaking research [11] on the theory of elliptic functions, the context in which modular forms first arose. Some of his identities are easy to verify— I will not say to derive—with the aid of complex analysis. For instance, if one can rearrange an identity into the form f = 0, where f is a modular function on some Γ_{0}(N), and prove that f vanishes somewhere and has no poles in ℍ and at cusps, then one has proven the identity. This sort of verification, however, typically leaves one with little insight into whence the identity came in the first place. It is a testament to Jacobi’s brilliance that he managed to discover and prove results like the triple-product theorem by means solely of clever algebraic manipulation.

To obtain (10) from Theorem 10, replace q by q^{3/2} and put z = −q^{1/2}. This transforms the series in Theorem 10 to the series in (10), while the triple product becomes

∏_{i≥1}(1 − q^{3i})(1 − q^{3i−1})(1 − q^{3i−2}) = ∏_{i≥1}(1 − q^{i}) = ϕ(τ),

as desired. There is one more case of Jacobi’s theorem that we shall need, specifically his triangular-number theorem

∏_{i≥1}(1 − q^{i})^{3} = ∑_{i≥0}(−1)^{i}(2i + 1)q^{i(i+1)/2}.  (11)

This identity follows from Theorem 10 by a limiting argument: replace q by q^{1/2} and let z = −tq^{1/2}. The triple product in this setting equals

∏_{i≥1}(1 − q^{i})(1 − tq^{i})(1 − t^{−1}q^{i−1}) = (1 − t^{−1}) ∏_{i≥1}(1 − q^{i})(1 − tq^{i})(1 − t^{−1}q^{i}).

Now divide by 1 − t^{−1} and let t approach 1. The product then becomes the product in (11). Noting that i(i + 1)/2 is preserved by the replacement i ↦ −(i + 1), we find that the doubly infinite sum in Jacobi’s theorem becomes

lim_{t→1} \frac{1}{1 − t^{−1}} ∑_{i} t^{i}(−1)^{i}q^{i(i+1)/2} = lim_{t→1} \frac{1}{1 − t^{−1}} ∑_{i≥0}(−1)^{i}(t^{i} − t^{−i−1})q^{i(i+1)/2}

= ∑_{i≥0}(−1)^{i} lim_{t→1} \frac{t^{i}(1 − t^{−(2i+1)})}{1 − t^{−1}}q^{i(i+1)/2}
= ∑_{i≥0}(−1)^{i}(2i + 1)q^{i(i+1)/2},

yielding the result desired.

The pentagonal- and triangular-number theorems are useful in partition arithmetic because several important η-products are congruent modulo a relevant prime to a pentagonal or triangular series or to the product of two such θ-series. We have already seen the example ϕ(2τ)/ϕ(τ) ≡ ϕ(τ) (mod 2), which proved that p_{2}(n) is even exactly when n is not pentagonal, or equivalently,^{2} when 24n + 1 is not square. Using Jacobi’s triangular series in place of Euler’s pentagonal series, we can show similarly that

\frac{ϕ(4τ)}{ϕ(τ)} ≡ ϕ(τ)^{3} ≡ ∑_{i≥0} q^{i(i+1)/2} (mod 2),

whence p_{4}(n) is even exactly when n is not triangular, or equivalently, when 8n + 1 is not square. In both of these cases, one can say that the parity of p_{N}(n) depends on the number of representations of a certain linear polynomial in n by the unary quadratic form λ^{2}—a trivial problem, of course. The problem is less trivial when the generating function in question factors modulo a prime ℓ as the product of two θ-series, as does the generating function of p_{3}(n) modulo 3: indeed

\frac{ϕ(3τ)}{ϕ(τ)} ≡ ϕ(τ) · ϕ(τ) ≡ ∑_{i,j}(−1)^{i+j}q^{i(3i−1)/2+j(3j−1)/2} (mod 3).  (12)

In these cases a positive-definite binary quadratic form is involved. Analyzing the representation of integers by such forms is a question of ideal factorization in the integer ring of an imaginary quadratic number field (see [10] for the form λ^{2} + μ^{2} and [6] for a much more detailed and general treatment) and is tractable in a few instances. In particular, for ℓ ∈ {3, 5, 7} it is possible to obtain conditions under which p_{ℓ}(n) vanishes modulo ℓ by using ideal theory in a suitable quadratic field, but we will not give the details.

The residue of p_{2}(n) modulo 4. Most elementary arguments based on the Frobenius congruence ϕ(ℓτ)/ϕ(τ) ≡ ϕ(τ)^{ℓ−1} (mod ℓ) do not extend readily to the modulus ℓ^{2}, where the Frobenius congruence does not hold. It is, however, possible to evaluate p_{2}(n) modulo 4 by modifying the argument we used to evaluate the parity of p_{2}(n) and invoking a result in the ideal theory of ℤ[\sqrt{−6}]. We will state and prove this theorem in full, in part because we shall need the result later.

2For n = i(3i − 1)/2 is equivalent to 24n + 1 = (6i − 1)^{2}.

Theorem 11 The residue of p_{2}(n) modulo 4 is given by the following rules.

• If 24n + 1 is a square, let l be the integer such that 24n + 1 = (6l − 1)^{2}. Then

p_{2}(n) ≡ (−1)^{l+r} (mod 4), where r = ∑_{p≡1,5,7,11(24)} v_{p}(6l − 1).

• If 24n + 1 = p^{4a+1}m^{2} for some integers a, m and a prime p ≡ 1 (mod 24) that does not divide m, then p_{2}(n) ≡ 2 (mod 4).

• In all other cases p_{2}(n) ≡ 0 (mod 4).

The latter part of the proof of Theorem 11 depends on the following formula for the number of representations of an integer n by the quadratic form λ^{2} + 6μ^{2}:

Lemma 12 Let n be a positive integer. If v_{p} n is odd for any prime p ≡ 13, 17, 19, 23 (mod 24) or if

∑_{p=2,3 or p≡5,11(24)} v_{p} n

is odd, then n cannot be expressed in the form λ^{2} + 6μ^{2} with λ, μ ∈ ℤ. Otherwise the number of ordered pairs (λ, μ) of integers such that n = λ^{2} + 6μ^{2} is

2 ∏_{p≡1,5,7,11(24)}(v_{p} n + 1).

For a proof of Lemma 12 see [15]. Proof of Theorem 11. Our analysis of p_{2}(n) modulo 2 departed from the Frobenius congruence 1 − x^{2} ≡ (1 − x)^{2} (mod 2). This congruence is not true modulo 4, but we can profitably use the identity

1 − x^{2} = (1 − x)^{2} + 2x(1 − x)  (13)

in its place. Using (13) we may write

\frac{ϕ(2τ)}{ϕ(τ)^{2}} = ∏_{i≥1} \frac{(1 − q^{i})^{2} + 2q^{i}(1 − q^{i})}{(1 − q^{i})^{2}} = ∏_{i≥1}(1 + 2\frac{q^{i}}{1 − q^{i}} ).  (14)

Expanding the rightmost product in (14) and dropping terms divisible by 4, we find that

\frac{ϕ(2τ)}{ϕ(τ)^{2}} ≡ 1 + 2 ∑_{i≥1} \frac{q^{i}}{1 − q^{i}} (mod 4).  (15)

The sum in (15) can be greatly simplified, for if we expand each summand as a geometric series, we can deduce easily that

∑_{i≥1} \frac{q^{i}}{1 − q^{i}} = ∑_{i≥1} ∑_{j≥1} q^{ij} = ∑_{i≥1} d(i)q^{i},

where d(n) denotes the number of positive divisors of n. Now it is well known that d(n) is odd exactly when n is square,^{3} and therefore

\frac{ϕ(2τ)}{ϕ(τ)^{2}} ≡ 1 + 2 ∑_{i≥1} q^{i^{2}} (mod 4),

whence

\frac{ϕ(2τ)}{ϕ(τ)} ≡ ϕ(τ) + 2 ∑_{i≥1} ϕ(τ)q^{i^{2}} (mod 4).  (16)

Equating the n^{th} coefficients of both sides of (16) yields

p_{2}(n) ≡ [q^{n}] ϕ(τ) + 2 ∑_{i≥1} [q^{n−i^{2}}] ϕ(τ)

≡ \{ \begin{matrix}(−1)^{l} & if n = l(3l − 1)/2; \\ 0 & otherwise \end{matrix}\} + 2#\{i ≥ 1 | n − i^{2} is pentagonal\}. (17)

Let us suppose first that n is not pentagonal (and hence that 24n + 1 is not square). Then (17) shows that p_{2}(n) ≡ 2 or 0 (mod 4) according as n has an odd or even number of representations in the form i^{2} + l(3l − 1)/2 with i ≥ 1. Now the equation

n = i^{2} + l(3l − 1)/2

means exactly that

24n + 1 = (6l − 1)^{2} + 6(2i)^{2}.  (18)

Because 24n + 1 is not square, all representations 24n + 1 = λ^{2} + 6μ^{2} have λ and μ nonzero; therefore, these representations may be partitioned into quadruples (±λ, ±μ). Exactly one choice of the second sign makes μ ≥ 1. Moreover, a finite verification using the fact that the squares modulo 24 are 0, 1, 4, 9, 12, and 16 shows that μ must always be even and λ ≡ ±1 (mod 6). Thus exactly one choice of the first sign makes λ ≡ −1 (mod 6), and exactly one in four of the representations of 24n + 1 by the form λ^{2} + 6μ^{2} are of the restricted type in (18). By Lemma 12 there are no such representations unless both

1. 24n + 1 has even valuation at each prime p ≡ 13, 17, 19, 23 (mod 24); and

2. ∑_{p≡5,11(24)} v_{p}(24n + 1) is even,

in which case there are exactly^{4}

\frac{1}{2} ∏_{p≡1,5,7,11(24)}(v_{p}(24n + 1) + 1)  (19)

representations. The product in (19) is divisible by 4 unless v_{p}(24n + 1) ≡ 1 (mod 4) for exactly one prime p, while 24n+1 has even valuation at all other primes. Such numbers are of the form p^{4a+1}m^{2} with p not dividing m; by considering residues modulo 24, we see that p ≡ 1 (mod 24). We have thus proven Theorem 11 for nonpentagonal n.

3The shortest proof is that δ ↦ n/δ is an involution of the set of positive divisors of n, and it fixes one point or no points according as \sqrt{n} is an integer or not.

4This quantity is an integer: it would be a half-integer only if v_{p}(24n + 1) were odd for all p ≡ 1, 5, 7, 11 (mod 24). Then by condition 1, it would follow that 24n + 1 is square, contrary to hypothesis.

For pentagonal n with 24n + 1 = (6l − 1)^{2}, the argument is the same except that there is an additional term (−1)^{l} and the two trivial representations 24n + 1 = λ^{2} + 6μ^{2} with μ = 0 must be counted out. We omit the easy calculations. □

In [15] I have proven by methods of analytic number theory, departing from the result of Theorem 11, that p_{2}(i(3i − 1)/2) is asymptotically equidistributed in (ℤ/4)^{∗}. We should also note that the residue of p_{2}(n) modulo 8 has been exactly computed by Ono and Penniston [19]. The answer is fairly complicated, and it is likely that such exact formulae as may exist for the residue of p_{2}(n) with respect to higher powers of 2 are quite long and unwieldy.

The eigenform approach. A more powerful, though still limited, approach to analyzing v_{2} p_{2}(n) depends on the fact that the Fourier coefficients of eigenforms of the Hecke operators T_{p} are multiplicative. We sketch this theory briefly here; for more details see Newman [17] and Gordon and Sinor [9] for the techniques used to construct eigenforms, as well as my paper [15] for their application to v_{2} p_{2}(n).

Suppose that f(τ) = ∑_{i} c(i)q^{i} is an eigenform of level N of all Hecke operators T_{M}, where M ⊥ N, and suppose that c(1) = 1 (one says then that f is a normalized eigenform). Equating coefficients of q in the equation f | T_{M} = λ_{M}f shows that the eigenvalue λ_{M} is simply c(M). ...

Let us write

f(τ) := \frac{η(48τ)}{η(24τ)} = ∑_{i} c(i)q^{i};

this function is a form of weight 0 and character (2/·) on the group Γ_{0}(2 · 24^{2}), and we have

c(i) = p_{2} (\frac{i − 1}{24}) .

Suppose for a moment that f(τ) were an eigenform of the Hecke operators T_{p} for all primes p ≠ 2, 3. In fact there are several good reasons why f(τ) is not an eigenform of any Hecke operator, but let us briefly pretend otherwise.

...

Although we will not prove it here, this result remains valid with v_{2}^{≤4} replaced by v_{2}^{≤5}. My proof of this claim in [15] evaluates the difference a_{1}(24n + 1) − p_{2}(n) modulo 32 using the fact that

\frac{η^{8}(48τ)}{η^{16}(24τ)} ≡ 1 + 16 ∑_{i≥1}(q^{i^{2}} + q^{2i^{2}}) (mod 32)

in combination with the ideal theory of ℤ[(1+\sqrt{−3})/2] and ℤ[\sqrt{−6}]. It is also possible to prove the stronger version by combining these arguments with those of Rødseth’s method, presented in the next section.

We should note in closing that the eigenform method is naturally limited by the fact that although Hecke eigenforms are plentiful, they are usually not η-products, and in particular very few of them are η-products congruent modulo a large prime power to a generating function of interest. Thus I doubt that it is practicable to analyze v_{2}^{≤κ} p_{2}(n) completely by this method for κ much larger than 5. Numerical evidence, moreover, shows that for κ ≥ 5, the n for which v_{2} p_{2}(n) = κ are not characterized precisely by any condition on the factorization of 24n + 1 that does not distinguish between primes that are congruent modulo 24. For instance, a computation of the first several million values of p_{2}(n) has revealed that there are pairs of primes p ≡ q ≡ 11 (mod 24) for which

v_{2} p_{2} (\frac{pq − 1}{24})

assumes any desired value from 5 through 18, as well as 20. It seems likely, therefore, that precise conditions for v_{2} p_{2}(n) = κ for any κ ≥ 5 will be considerably more complicated and harder to prove.

3 Main theorems on p_{N}(n)

The eigenform method has the virtue of producing exact results when it works, but unfortunately it is based on equations but on congruences modulo a fixed power of 2, and therefore it can evaluate v_{2} p_{2}(n) only when that valuation is small. By contrast, the methods employed by Rødseth [23] to obtain certain limited lower bounds on v_{2} p_{2}(n) do not involve congruences, but attack a generating function of p_{2}(n) directly by cleverly constructing a useful expression for its images under the Hecke operators. For this reason it turns out to be possible to extend Rødseth’s techniques to establish nontrivial lower bounds on v_{2} p_{2}(n) that are unbounded as n ranges through the integers. In this section we shall indicate how to generalize Rødseth’s method to prove, in particular, an explicit lower bound on v_{2} p_{2}(n) that is strong enough to prove the conclusion Gordon and Ono’s theorem for p_{2}(n). It appears that no such constructive proof of any case of Gordon and Ono’s theorem has been given before.

The techniques of this section will prove Gordon and Ono’s theorem not only for p_{2}(n), but in fact for p_{N}(n) for

N = 2, 3, 4, 5, 7, 9.

For such N we write N = ℓ^{e}, where ℓ is the prime divisor of N and e = 1 or 2 as appropriate; and by N′ we denote the integer 24/(N − 1). The crux of the proof is a lower bound on v_{ℓ} p_{N}(n) in terms of the factorization of N′n + 1: specifically

v_{ℓ} p_{N}(n) ≥ \frac{1}{4}#\{p ≢ 1 (mod N′) | v_{p}(N′n + 1) is odd\}.  (20)

This is not the best estimate that can be proven, but it is sufficient for the purpose. When we have this estimate, we shall be able to conclude the proof quickly by applying standard asymptotic theorems of prime-number theory. We will postpone this part and speak first of the estimate of (20).

Before proceeding, we introduce some notation that will be of continual use throughout this section. By [ ; [n] ; ] we denote an unspecified rational number, integral at ℓ, whose valuation at ℓ is at least n; in particular, if n ≤ 0, then [ ; [n] ; ] just represents an unspecified ℓ-integral rational number. We write f(τ) for the function

f(τ) := \frac{η(Nτ)}{η(τ)} = ∑_{i} p_{N}(i)q^{i+1/N′},

which is roughly the generating function of the sequence p_{N}(i). The function f(τ) is not a q-series with integer exponents, but the function

f(N′τ) = \frac{η(N′Nτ)}{η(N′τ)} = ∑_{i} p_{N}(i)q^{N′i+1}

does have integer exponents, and it is easily checked that f(N′τ) is a form of weight 0 on Γ_{0}(N′^{2}N) with Nebentypus character d ↦ (d N). Finally, we write γ_{r}(i) for the coefficient of q^{i} in f(N′τ)^{r} if r and i are nonnegative integers, while γ_{r}(i) = 0 in other cases. In particular γ_{1}(N′i + 1) = p_{N}(i).

To motivate what follows, let us take N = 2 (the case that Rødseth studied) and consider what we can deduce directly from the relevant theorems of Rødseth’s 1969 paper. His main result [23, Theorem 1] is that whenever p ≠ 2, 3 is prime, there is an identity

γ_{1}(pn) + (\frac{2}{p}) γ_{1}(n/p) = ∑_{i≥0} [ ; [(p − 1)/2 − 12i] ; ] γ_{p−24i}(n),  (21)

where the undetermined coefficients depend only on the prime p, not on n. It is easy to verify that (21) can be rewritten as

γ_{1}(pn) + (\frac{2}{p}) γ_{1}(n/p) = ∑_{i≥0} [ ; [(⟨p⟩_{24} − 1)/2 + 12i] ; ] γ_{⟨p⟩_{24}+24i}(n),  (22)

a form that is more useful than that of (21) because it places the 2-adically dominant terms first rather than last in the summation. Restricting attention to primes p ≡ 1 (mod 24) in (22) leads to an interesting discovery: if we reduce (22) modulo 2^{12}, we find that

γ_{1}(pn) + (\frac{2}{p}) γ_{1}(n/p) ≡ [ [0] ] γ_{1}(n) (mod 2^{12}).  (23)

We have already observed that f(24τ) is not an eigenform of any T_{p}, but (23) shows that f(24τ) looks modulo 2^{12} like an eigenform for all p ≡ 1 (mod 24). Moreover, the coefficient [ [0] ] has the exact value γ_{1}(p), as we can see by setting n = 1 in (22): we have γ_{1}(1) = 1 and γ_{r}(1) = 0 for all r > 1 because the Fourier series of f(24τ)^{r} begins with q^{r}. We know that v_{2} γ_{1}(p) = 1 by Theorem 11. Mimicking the arguments of the eigenform method, we can show that

v_{2}^{≤12} γ_{1}(p^{a}m) = v_{2}^{≤12}(v_{2} a + 1) + v_{2}^{≤12} γ_{1}(m) for p ≡ 1 (mod 24) and p ⊥ m,

an improvement on one of the results of that section; in particular, we have

v_{2} p_{2} (\frac{p^{2047} − 1}{24}) = 11 for each prime p ≡ 1 (mod 24).

Although Rødseth did not state them, there are analogues of (22) (which we shall prove below) with γ_{1} replaced by γ_{r} for other values of r; using them much as in the eigenform method, one can obtain nontrivial lower bounds, not exceeding 12, on v_{2} p_{2}(n).

What is less obvious is that one can profitably deal with these identities directly without reducing them modulo a fixed power of two. For each nonnegative integer n and each prime p, the identities describe the values of all the γ_{r}(pn) for positive integers r in terms of the values of γ_{r′}(n) and γ_{r′}(n/p) for all r, as well as a slew of undetermined coefficients whose valuations at 2 have been estimated from below. Using these identities recursively, one can express γ_{1}(n) for each n in terms of the undetermined coefficients and the values of γ_{r}(1). But the values of γ_{r}(1) are trivially evaluated: we have γ_{1}(1) = 1 and γ_{r}(1) = 0 for r > 1. Thus γ_{1}(n) will be expressed as a polynomial in the undetermined coefficients. The valuation at 2 of the terms of this polynomial can be bounded nontrivially from below in most cases using the estimates on the valuations of the coefficients in the identities, thus yielding in particular a lower bound on v_{2} p_{2}(n).

We now return to the more general setting N ∈ {2, 3, 4, 5, 7, 9} and prove the identities at the heart of this method, after doing which we shall sketch how these identities can be applied to prove Gordon and Ono’s theorem for these values of N.

Generalized Rødseth identities. We wish to evaluate f(N′τ)^{r} | T_{p} for all p ⊥ N′, as Rødseth did for N = 2 and r = 1. If the prime p does not divide the product NN′, then we can generalize Rødseth’s method of proof to establish the following identity of the desired type:

Lemma 13 Let p be a prime not dividing NN′, and let r be a positive integer relatively prime to N′. Then

γ_{r}(pn) + (p N)^{r} γ_{r}(n/p) = ∑_{i} [[(p − 1)er/2 − N′ei/2]] γ_{pr−N′i}(n),

where the coefficients are independent of n.

If N ∈ {2, 3, 4, 9}, any prime not dividing N′ does not divide N either, and Lemma 13 will be sufficient for our purposes. If N ∈ {5, 7}, however, the prime ℓ = N does not divide N′, yet does divide N, and hence Lemma 13 does not apply to it. We shall deal with these exceptions by a different method later. Proof of Lemma 13. The statement of the lemma is equivalent to the equation in power series

f(N′τ) | T_{p} = ∑_{i} [[(p − 1)er/2 − N′ei/2]] f(N′τ)^{pr−N′i},

which is what we shall prove.

The first device of the proof is akin to the device used by Newman and his successors to construct eigenforms: given an η-product modular on Γ_{0}(N) with an unpleasant multiplier system, construct from it a modular function on Γ_{0}(pN), then apply the level-reducing operator L_{N,p} to obtain a function on Γ_{0}(N). In our context, the initial, unruly modular form is f(τ)^{r}. We shall verify that the function

g(τ) := f(τ)^{r}f(pτ)^{−pr}

is modular on Γ_{0}(pN), whence g(τ) | L_{N,p} is modular on Γ_{0}(N). From this point forward all the analysis takes place on the group Γ_{0}(N), which has two pleasant properties that make Rødseth’s method work. First, there are relatively few cusp classes. Indeed, for the prime values of N under consideration, we have only i∞ and 0 to consider; for N = 4 there is also 1/2, and for N = 9 there are 1/3 and 2/3. Second, and more importantly, the Riemann surface associated to Γ_{0}(N) has genus 0, hence supports a univalent function; in fact, we can take this function to be

Φ_{N}(τ) := f(τ)^{N′},

which has its zero at i∞ and its pole at 0. The existence of this beautiful univalent function pays dividends when we verify that

h(τ) := g(τ) | L_{N,p}

is holomorphic except at i∞, for then it follows that h(τ) equals a polynomial in Φ_{N}(τ)^{−1} with integer coefficients. This equation is essentially the Rødseth identity, in which the variety of powers of f on the right side arises from the variety of powers of Φ_{N}^{−1} in the polynomial expression for h. It will remain then only to analyze the valuation at ℓ of the undetermined coefficients. For this we shall apply the operator S_{N,p}^{0} to the equation between h and a polynomial in Φ_{N}^{−1}. This transformation causes h and Φ_{N}^{−1} to emit large powers of ℓ, and equating coefficients in the resulting equation will give us the valuation estimates we need.

Proceeding from the outline to the proof, we first show that g(τ) is modular on Γ_{0}(pN). Clearly its weight is 0. In the notation of [ref], we have

∑_{δ|pN} δα_{δ} = r(N − 1)(1 − p^{2}).

Now p^{2} ≡ 1 (mod 24) if p ≥ 5. When p = 3 we have 1 − p^{2} = −8, but N must be 4 or 7, whence N − 1 is a multiple of 3. Similarly, when p = 2 we have N = 9, so that (N − 1)(1 − p^{2}) = −24. In all cases the sum is a multiple of 24. The companion sum

∑_{δ|pN} \frac{pN}{δ} α_{δ} = r(1 − N)(p − p) = 0

needs no comment. It remains only to check that

∏_{δ|pN} δ^{|α_{δ}|} = (N^{1+p}p^{2p})^{r}

is a square. But this is obvious unless p = 2, and in that case N = 9. Hence g ∈ A_{0}(Γ_{0}(pN)), and therefore h ∈ A_{0}(Γ_{0}(N)).

Now by definition

h(τ) = g(τ) | S_{p,N}^{0} + g(τ) | U_{p}.  (24)

We cannot presently simplify the term involving U_{p}, but we can use [ref] to evaluate the term involving S_{p,N}^{0}. I claim that

(\frac{η(Nτ)}{η(τ)}) (\frac{η(pτ)}{η(Npτ)})^{p} | S_{p,N}^{0} = (N p) (\frac{η(τ)}{η(Nτ)})^{p} (\frac{η(Npτ)}{η(pτ)}) ,  (25)

whence g(τ) | U_{p} is the r^{th} power of the right side of (25). To prove this, we first note that

∑_{δ|p,ϵ|N} δ(N/ϵ)α_{δ,ϵ} = (N − 1)(p^{2} − 1) ≡ 0 (mod 24)

and

∑_{δ|p,ϵ|N}(p/δ)Nα_{δ,ϵ} = 0,

so that [ref] applies. We have ∏(p/δ)^{α_{δ,ϵ}} = p^{1−1} = 1. It remains to check that the root of unity involved is (N p). For this we compute that

∏_{ϵ|N} (∏_{δ|p}(−p/δ)^{|α_{δ,ϵ}|} N/ϵ) = (p N) (p 1) = (p N) ,
∑_{δ|p,ϵ|N}(N/ϵ)α_{δ,ϵ} = (N − 1)(p − 1),

and

∑_{δ|p,ϵ|N}(1 − N/ϵ)^{3}(p/δ + 1)α_{δ,ϵ} = (1 − N)^{3}(p − 1),

whence the root of unity arising in [ref] equals

(p N) exp \frac{πi}{4}N(N − 1)(N − 2)(p − 1).  (26)

We must prove that the expression in (26) is exactly (N p). For this we distinguish three cases. If N is even, then 8 | N(N − 1)(N − 2), whence the exponential in (26) is trivial, and moreover (p N) = (N p) = (N/p). If N = 9 and p = 2, then again the exponential in (26) is trivial, and (p N) = (N p) = 1 because N is square. In the remaining case N and p are both odd. One verifies then that the exponential equals

(−1)^{(p−1)(N−1)/4} = (\frac{p}{N} ) (\frac{N}{p} ) ,

and therefore the expression of (26) equals

(\frac{p}{N} ) (\frac{p}{N} ) (\frac{N}{p} ) = (\frac{N}{p} ) = (N p) ,

as claimed.

The result of (24) now reads

h(τ) = (N p)^{r} (\frac{η(τ)}{η(Nτ)})^{pr} (\frac{η(Npτ)}{η(pτ)})^{r} + (\frac{η(Nτ)}{η(τ)})^{r} (\frac{η(pτ)}{η(Npτ)})^{pr} | U_{p}.  (27)

... When N is a square rather than a prime, there are also cusps ip/ℓ with 1 ≤ i < ℓ to analyze. In these cases one applies S_{N,p}^{ip/ℓ} to (27) instead of S_{N,p}^{0} and uses the quasicommutativity result [ref] in conjunction with ...

□

It is convenient to use the result of Lemma 13 in a slightly different form. Write r = N′t + s, where t ≥ 0 and 0 ≤ s < N′. Thus

γ_{N′t+s}(pn)+(p N)^{N′t+s} γ_{N′t+s}(n/p) = ∑_{i} [ ; [(e/2)((p − 1)(N′t + s) − N′i)] ; ] γ_{pN′t+ps−N′i}(n).

(28)

In (28) replace i by i_{0} − j, where i_{0} is the integer

i_{0} = \frac{ps − ⟨ps⟩_{N′}}{N′} + (p − 1)t.

Then (28) becomes

γ_{N′t+s}(pn)+(p N)^{N′t+s} γ_{N′t+s}(n/p) = ∑_{j} [ ; [(e/2)(⟨ps⟩_{N′} − s + N′j)] ; ] γ_{N′(t+j)+⟨ps⟩_{N′}} (n).

(29)

The advantage of this form is that the most important terms in the identity turn out to be those in which the value inside [ ; [·] ; ] is near zero. Our reindexing has placed these terms near j = 0, in the center of the summation range, whereas before the reindexing these crucial terms appeared at variable positions in the summation range. When one recursively substitutes the recurrences of (29) one into another, the fact that the dominant terms always appear near the zero index makes it easier to keep track of them.

Obtaining the valuation estimates. Here we sketch how the identities of (29) ... ...

Completing the proof.

4 Conclusion

The constructive proof of several cases of Gordon and Ono’s theorem shows clearly that of Rødseth is the strongest tool presently available for effectively analyzing the arithmetic of restricted partition functions. One should not, however, disdain the elementary and eigenform methods, for they do provide information that Rødseth’s method never will. The proof of Corollary 5, in fact, depends on all three. When

n = p_{1} … p_{2s}q_{1} … q_{2t},

where p_{i} ≡ 5 (mod 24) and q_{j} ≡ 7 (mod 24) are distinct primes, Rødseth’s method naturally gives the lower bound

v_{2} p_{2}(n) ≥ 2s + 3t,  (30)

but not an exact equation. To know that equality holds, we must know that certain coefficients [ [0] ], [ [2] ], and [ [3] ] in the Rødseth identities have in fact exact valuations 0, 2, and 3 respectively at the prime 2. This information comes not from Rødseth’s method, but rather from the eigenform method. Moreover, the expression 2s+3t does not assume the value 1, and neither Rødseth’s method nor the eigenform method will prove by itself that v_{2} p_{2}(n) = 1 infinitely often. We proved this by the elementary methods based on Jacobi’s triple product and the theory of representations by binary quadratic forms.

It is natural to ask whether Rødseth’s method extends to other values of N. It appears to fail even for N = 13 and 25, even though in both of those cases the Riemann surface associated to Γ_{0}(N) has genus zero, and the N′^{th} power of f(τ) is a univalent function. The problem here is that Rødseth’s method will not prove that primes p ≡ 1 (mod N′) dividing n contribute anything to the valuation of p_{N}(n). We saw this clearly in the case N = 2, for which Rødseth’s method yields the trivial estimate v_{2} p_{2}((p − 1)/24) ≥ 0 for each prime p ≡ 1 (mod 24), even though we could prove by other methods that the exact valuation is 1 in each case. For the values of N that we treated, this deficiency did not ruin the proof of Gordon and Ono’s result, for after throwing out all p ≡ 1 (mod N′), there still remains a positive proportion of the primes to contribute to the valuation. Unfortunately, when N = 13 or 25 we have N′ = 2 or 1 respectively, and all the relevant primes are congruent modulo N′ to 1. Therefore Rødseth’s method yields the trivial estimate v_{ℓ} p_{N}(n) ≥ 0 for each n. I do not see how to work around this problem.

There are other values of N for which Γ_{0}(N) has a univalent function, and one can always take this function to be an η-product with its zero at i∞ and its pole at 0. I suspect that it may be possible to extend Rødseth’s method to handle a few of these cases, although the arguments will have to be changed somewhat because the univalent function is no longer a power of the generating function being analyzed. Moreover the function h constructed in the proof of the Rødseth identities can have poles at cusps other than i∞, and so it will probably have to be defined differently to make the machinery work.

Finally, although levels with nonzero genus are much harder to handle with classical analytic methods, Atkin’s proof [4] of Ramanujan’s congruences modulo powers of 11, in which the group Γ_{0}(11) of genus 1 is involved, leaves some hope that one or two cases of genus 1 might be amenable to an application of Rødseth’s techniques. But such an application, if it is indeed possible, would undoubtedly involve much more formidable complications of detail.

Acknowledgments. I am most grateful to Professor William Stein of Harvard University for his guidance during my senior-thesis work. I owe my prior interest in and knowledge of partition theory to Professor John Rickert of Rose-Hulman University, who directed an REU on partition arithmetic in which I took part, and to the NSF, which generously funded that program.

References

[1] S. Ahlgren and K. Ono, Congruence properties for the partition function, Proc. Natl. Acad. Sci. USA 98 (2001) 12882–4.

[2] G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976; third printing, Cambridge University Press, 1998.

[3] T. M. Apostol, Modular Functions and Dirichlet Series in Number Theory, 2^{nd} ed., New York, Springer-Verlag, 1997.

[4] A. O. L. Atkin, Proof of a conjecture of Ramanujan, Glasgow Math. J. 8 (1967) 14–32.

[5] B. C. Berndt and K. Ono, Ramanujan’s unpublished manuscript on the partition and tau functions with proofs and commentary, Séminaire Lotharingien de Combinatoire (1999), 42.

[6] D. A. Cox, Primes of the Form x^{2} +ny^{2}: Fermat, Class Field Theory, and Complex Multiplication, New York, John Wiley and Sons, 1989.

[7] F. Diamond and J. Im, Modular forms and modular curves, in V. Kumar Murty, ed., CMS Conference Proceedings 17 (1995) 39–133.

[8] B. Gordon and K. Ono, Divisibility of certain partition functions by powers of primes, Ramanujan J. 1 (1997) 25–34.

[9] B. Gordon and D. Sinor, Multiplicative properties of η-products, Lecture Notes in Math. 1395, New York, Springer-Verlag, 1989, pp. 173–200.

[10] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5^{th} ed., New York, Oxford University Press, 1993.

[11] C. G. J. Jacobi, Fundamenta nova theoriae functionum ellipticarum, Königsberg, Bornträger, 1829.

[12] M. I. Knopp, Modular Functions in Analytic Number Theory, Chicago, Markham, 1970.

[13] G. Ligozat, Courbes modulaires de genre 1, Bull. Soc. Math. France 43 (1972) 1–80.

[14] J. Lovejoy, The number of partitions into distinct parts modulo powers of 5, Bull. London Math. Soc., to appear.

[15] C. Mihelich, The order at 2 of the odd-partition function, Rose-Hulman Technical

Report Series, to appear; www.fas.harvard.edu/~cmihelic/ord2p2.pdf.

[16] M. Newman, Construction and application of a certain class of modular functions II, Proc. London Math. Soc. 9 (1959) 353–87.

[17] M. Newman, Modular forms whose coefficients possess multiplicative properties, Ann. of Math. 70 (1959) 478–89.

[18] K. Ono, The distribution of the partition function modulo m, Ann. of Math. 151 (2000) 293–307.

[19] K. Ono and D. Penniston, The 2-adic behavior of the number of partitions into distinct parts, J. Comb. Th. Ser. A 92 (2000) 138–57.

[20] H. Petersson, Über Modulfunktionen und Partitionprobleme, Abh. Deut. Akad. Wiss. Berlin (1954), no. 2, 59 pp.

[21] H. Rademacher, Zur Theorie der Modulfunktionen, J. reine angew. Math. 167 (1932) 312–36.

[22] S. Ramanujan, Congruence properties of partitions, Proc. London Math. Soc. 19 (1919) 207–10.

[23] Ø. Rødseth, Congruence properties of the partition functions q(n) and q_{0}(n), Arbok Univ. Bergen Mat.-Naturv. Ser. (1969), no. 13, 27 pp.

[24] J-P. Serre, Divisibilité de certaines fonctions arithmétiques, L’Enseign. Math. 22 (1976), 227–60.

[25] G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton University Press, 1971.

[26] G. N. Watson, Ramanujans Vermutung über Zerfällungsanzahlen, J. reine angew. Math. 179 (1938) 97–128.

[27] H. Weber, Elliptische Funktionen und algebraische Zahlen, Braunschweig, Friedrich Vieweg und Sohn, 1891.

[28] E. T. Whittaker and G. N. Watson, A Course of Modern Analysis, reissued by Cambridge University Press, 1996.