SIEVED PARTITION FUNCTIONS

AND Q-BINOMIAL COEFFICIENTS

Frank Garvan* and Dennis Stanton**

Abstract. The q-binomial coefficient is a polynomial in q. Given an integer t and a residue class r modulo t, a sieved q-binomial coefficient is the sum of those terms whose exponents are congruent to r modulo t. In this paper explicit polynomial identities in q^{t} are given for sieved q-binomial coefficients. As a limiting case, generating functions for the sieved partition function are found as multidimensional theta functions. A striking corollary of this representation is the proof of Ramanujan’s congruences mod 5, 7, and 11 by exhibiting symmetry groups of orders 5, 7, and 11 of explicit quadratic forms. We also verify the Subbarao conjecture for t = 3, t = 5, and t = 10.

1. Introduction.

The q-binomial coefficient

(1.1)  [ \begin{matrix}N \\ k \end{matrix} ]_{q} = \frac{(1 − q^{N}) ⋯ (1 − q^{N−k+1})}{(1 − q) ⋯ (1 − q^{k})} = ∑_{i≥0} a_{i}q^{i}

is a polynomial in q with integer coefficients. In this paper we shall consider the following families of polynomials formed from (1.1). Let t be a positive integer and consider the terms in (1.1) with residue class r modulo t:

(1.2)  ∑_{i≥0} a_{ti+r}q^{ti+r}.

We refer to (1.2) as a sieved q-binomial coefficient. We give explicit formulas (Theorems 1 and 2 of §2) for the sieved q-binomial coefficient as polynomials in q^{t}. Some limiting cases (Theorems 3A, 3B and 3C of §3) are expressions for sieved partition functions as multidimensional theta functions. In §4 the symmetry groups of the quadratic form of the theta function are computed. Applications of these groups to congruences for the partition function are given in §5.

To set the notation and explain the method, we shall now do the t = 2 case. For an integer N and complex numbers a and q, |q| < 1 let

(a; q)_{N} = ∏_{i=0}^{N−1} (1 − aq^{i}).

Typeset by AMS-TEX

*Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN 55455.

**School of Mathematics, University of Minnesota, Minneapolis, MN 55455. This work was partially supported by NSF grant DMS:8700995, and a grant from the Minnesota Supercomputer Institute.

We shall also allow N = ∞ and note that the generating function for all partitions of i, p(i), is

∑_{i=0}^{∞} p(i)q^{i} = (q; q)_{∞}^{−1} = (q)_{∞}^{−1}.

We next let t = 2 and r = 0, so that we want the even terms in the q-binomial coefficient. Recall the terminating q-binomial theorem

(1.3)  (−x; q)_{N} = ∑_{k=0}^{N} [ \begin{matrix}N \\ k \end{matrix} ]_{q} q^{\binom{k}{2}}x^{k}.

Suppose N is even. Since

(1.4)  (−x; q)_{N} + (−x; −q)_{N} = (−x; q^{2})_{N/2}{(−xq; q^{2})_{N/2} + (xq; q^{2})_{N/2}},

(1.3) clearly implies

(1.5) [ \begin{matrix}N \\ k \end{matrix} ]_{q} q^{\binom{k}{2}} + [ \begin{matrix}N \\ k \end{matrix} ]_{−q} (−q)^{\binom{k}{2}} = 2 ∑_{m=0}^{k/2} [ \begin{matrix}N/2 \\ 2m \end{matrix} ]_{q^{2}}[ \begin{matrix}N/2 \\ k − 2m \end{matrix} ]_{q^{2}}q^{4m^{2}+2\binom{k−2m}{2}}.

We obtain the following proposition.

Proposition 1. If N is even, then

∑_{m=0}^{k/2} [ \begin{matrix}N/2 \\ 2m \end{matrix} ]_{q^{2}}[ \begin{matrix}N/2 \\ k − 2m \end{matrix} ]_{q^{2}}q^{4m^{2}+2\binom{k−2m}{2}−\binom{k}{2}} = \{ \begin{matrix}∑_{i} a_{2i}q^{2i} for k ≡ 0 or 1 mod 4 \\ ∑_{i} a_{2i+1}q^{2i+1} for k ≡ 2 or 3 mod 4. \end{matrix}

The corresponding cases for the difference in (1.4) are the following.

Proposition 2. If N is even, then

∑_{m=0}^{k/2} [ \begin{matrix}N/2 \\ 2m + 1 \end{matrix} ]_{q^{2}}[ \begin{matrix}N/2 \\ k − 2m − 1 \end{matrix} ]_{q^{2}}q^{(2m+1)^{2}+2\binom{k−2m−1}{2}−\binom{k}{2}} =

∑_{i} a_{2i}q^{2i} for k ≡ 2 or 3 mod 4

∑_{i} a_{2i+1}q^{2i+1} for k ≡ 0 or 1 mod 4.

Propositions 1 and 2 are evaluations of special well-poised _{4}ϕ_{3}’s in the theory of basic hypergeometric series. It is easy to give the relevant versions of Propositions 1 and 2 for N odd, but we do not do so here.

2. Sieved q-binomial coefficients.

In this section we follow the outline of §1 for a general t, and find an expression for the sieved q-binomial coefficients (1.2). We must replace the −q in (1.4) by a sum over all t th roots of unity, so let ω = exp(2πi/t). It is clear from (1.3) that

(2.1)  ∑_{i=0}^{t−1}(−x; ω^{i}q)_{N} = ∑_{k=0}^{N} ∑_{i=0}^{t−1} [ \begin{matrix}N \\ k \end{matrix} ]_{ω^{i}q} (ω^{i}q)^{\binom{k}{2}}x^{k}.

If N is a multiple of t, it is easy to see that

(2.2)  ∑_{i=0}^{t−1}(−x; ω^{i}q)_{N} = (−x; q^{t})_{N/t} ∑_{i=0}^{t−1} ∏_{k=1}^{t−1}(−xω^{ki}q^{k}; q^{t})_{N/t}

The coefficient of x^{k} in (2.2) yields

∑_{i=0}^{t−1} [ \begin{matrix}N \\ k \end{matrix} ]_{ω^{i}q} (ω^{i}q)^{\binom{k}{2}} = ∑_{n_{1},...,n_{t}} ∏_{i=1}^{t} [ \begin{matrix}N/t \\ n_{i} \end{matrix} ]_{q^{t}} ∑_{p=0}^{t−1} θ^{p}

where

θ = ω^{∑_{i=2}^{t}(i−1)n_{i}}.

The result is the following theorem. Note that the residue class chosen from the q-binomial coefficient depends upon the value of \binom{k}{2} mod t.

Theorem 1. Let N be a multiple of t, and \binom{k}{2} ≡ t − r mod t, 1 ≤ r ≤ t. If a_{i} is

the coefficient of q^{i} in the q-binomial coefficient [ \begin{matrix}N \\ k \end{matrix} ]_{q}, then

∑_{i=0}^{∞} a_{ti+r}q^{ti+r} = ∑_{n_{1},...,n_{t}} ∏_{i=1}^{t} [ \begin{matrix}N/t \\ n_{i} \end{matrix} ]_{q^{t}} q^{t(∑_{i=1}^{t} \binom{n_{i}}{2}+m)−\binom{k}{2}},

where the summation parameters satisfy n_{1} + ⋯ + n_{t} = k and n_{2} + 2n_{3} + ⋯ + (t − 1)n_{t} = tm, for some integer m.

The residue class r in Theorem 1 is determined by k and t. For a given N,k, and t, one would like a version for any residue class r. This can be done by inserting the appropriate roots of unity in the left side of (2.1). We give such a version for k ≡ 0 mod 2t.

Theorem 2. Let N be a multiple of t, k be a multiple of 2t, and 1 ≤ r ≤ t − 1. If

a_{i} is the coefficient of q^{i} in the q-binomial coefficient [ \begin{matrix}N \\ k \end{matrix} ]_{q}, then

∑_{i=0}^{∞} a_{ti}q^{ti+t−r} = ∑_{n_{1},...,n_{t}} ∏_{i=1}^{t} [ \begin{matrix}N/t \\ n_{i} \end{matrix} ]_{q^{t}} q^{t(∑_{i=1}^{t} \binom{n_{i}}{2}+m)−\binom{k}{2}},

where the summation parameters satisfy n_{1} + ⋯ + n_{t} = k and n_{2} + 2n_{3} + ⋯ + (t − 1)n_{t} = tm + r, for some integer m.

3. Sieved partition functions.

Theorems 1 and 2 are polynomial identities which imply generating functions for sieved partition functions. In this section we take the appropriate limits to obtain these identities: Theorems 3A, 3B, and 3C.

To see this, recall that the q-binomial coefficient (1.1) is the generating function for partitions which lie inside a k × (N − k) rectangle. If N → ∞, we obtain all partitions with at most k parts. Next if k → ∞, we find all partitions. We will apply this sequence of limits to Theorems 1 and 2 for our results on the sieved partition function.

First we take the t = 2 case to demonstrate the technique. Let k ≡ 0 mod 4 in Proposition 1. If N → ∞, we find that the right side becomes

∑_{m=0}^{k/2} \frac{q^{8m^{2}−4km+2m+k^{2}/2−k/2}}{(q^{2}; q^{2})_{2m}(q^{2}; q^{2})_{k−2m}} .

The exponent of q is a quadratic polynomial in m whose minimum occurs at m = k/4 − 1/8, 2(m − k/4) + 8(m − k/4)^{2}. Thus replacing m by m + k/4 and letting k → ∞, we find

(3.1)  ∑_{i=0}^{∞} p(2i)q^{i} = \frac{1}{(q)_{∞}^{2}} ∑_{m=−∞}^{∞} q^{4m^{2}+m}.

For k ≡ 2 mod 4, Proposition 1 implies

(3.2)  ∑_{i=0}^{∞} p(2i + 1)q^{i} = \frac{1}{(q)_{∞}^{2}} ∑_{m=−∞}^{∞} q^{4m^{2}−3m}.

We do the same sequence of steps for Theorems 1 and 2, which are t−1 fold sumsthe summation parameters being m, n_{3}, …, n_{t}. The N → ∞ limit of both theorems is easily computed by replacing the q-binomial coefficients by a single product in the denominator. For the k → ∞ limit, one must again find the minimum value of the quadratic function of m, n_{3}, …, n_{t} in the exponent of q, and then shift the domain of these summation parameters so that the minimum occurs at the origin. For Theorem 2, it can be shown that a minimum value occurs at m = (t − 1)k/2t, n_{i} = k/t, i ≠ r + 2, …, n_{r+2} = k/t − 1, or at m = (t − 1)k/2t, n_{i} = k/t, i ≠ r + 1, …, n_{r+2} = k/t − 1. Explicitly computing the Taylor series of the exponent of q at these values, shifting the parameters, and taking the limit on k gives the following two theorems.

Theorem 3A. Let 1 ≤ r ≤ t − 2. Then

∑_{n=0}^{∞} p(tn + t − r)q^{n} = \frac{1}{(q)_{∞}^{t}} ∑_{m,n_{3},...,n_{t}=−∞}^{∞} q^{Q(m,n_{3},...,n_{t})+LA(m,n_{3},...,n_{t})},

where

Q(m, n_{3}, …, n_{t}) = t^{2}m^{2}+∑_{i=3}^{t}(i^{2}−3i+3)n_{i}^{2}+∑_{i=3}^{t}(3−2i)tmn_{i}+ ∑_{3≤i<j≤t}(2ij−3i−3j+5)n_{i}n_{j},

LA(m, n_{3}, …, n_{t}) = ∑_{i=3,i≠r+2}^{t}(1 − i)n_{i} + (−r − 2)n_{r+2} + (1 + t)m.

Theorem 3B. Let 2 ≤ r ≤ t − 1. Then

∑_{n=0}^{∞} p(tn + t − r)q^{n} = \frac{1}{(q)_{∞}^{t}} ∑_{m,n_{3},...,n_{t}=−∞}^{∞} q^{Q(m,n_{3},...,n_{t})+LB(m,n_{3},...,n_{t})},

where Q(m, n_{3}, …, n_{t}) is given in Theorem 3A, and

LB(m, n_{3}, …, n_{t}) = ∑_{i=3,i≠r+1}^{t}(i − 2)n_{i} + (r − 2)n_{r+1} + (1 − t)m.

Note that for different r, the right sides of Theorems 3A (3B) differ only in the special linear term related to r. A linear change of variables shows that Theorems 3A and 3B are equivalent where they overlap, 2 ≤ r ≤ t − 2.

The result which follows from Theorem 1 for r = 0 is

Theorem 3C. We have

∑_{n=0}^{∞} p(tn)q^{n} = \frac{1}{(q)_{∞}^{t}} ∑_{m,n_{3},...,n_{t}=−∞}^{∞} q^{Q(m,n_{3},...,n_{t})+LC(m,n_{3},...,n_{t})},

where Q(m, n_{3}, …, n_{t}) is given in Theorem 3A, and LC(m, n_{3}, …, n_{t}) = m.

We note that Kolberg [5] has also obtained representations for the generating functions for p(tn + r). His representations are in terms of t × t determinants of theta-functions and are different from our results. For the cases t = 2, 3, 5, 7 his determinants simplify to nice linear combinations of certain infinite products. For example, Kolberg’s [5, (3.1)] is (3.3)

∑_{n=0}^{∞} p(3n)q^{n} = \frac{(q^{3}; q^{3})_{∞}(q^{9}; q^{9})_{∞}^{2}(q^{4}; q^{9})_{∞}^{2}(q^{5}; q^{9})_{∞}^{2}}{(q)_{∞}^{4}} − q \frac{(q^{9}; q^{9})_{∞}^{2}}{(q)_{∞}^{3}(q^{4}; q^{9})_{∞}(q^{5}; q^{9})_{∞}} .

We can find similar identities by diagonalizing the quadratic form Q and applying the Jacobi triple product identity [1, p.21]. For example, let t = 3 in Theorem 3C

∑_{n=0}^{∞} p(3n)q^{n} = \frac{1}{(q)_{∞}^{3}} ∑_{m,s=−∞}^{∞} q^{3s^{2}+m−9ms+9m^{2}}.

There are several ways to diagonalize this form. One is to note that Q(m + s, 2s) and Q(m + s, 2s + 1) are diagonal, and we find the following evaluation.

\begin{aligned}∑_{n=0}^{∞} p(3n)q^{n} = \frac{(q^{18}; q^{18})_{∞}(q^{6}; q^{6})_{∞}}{(q)_{∞}^{3}} & \{(−q^{7}; q^{18})_{∞}(−q^{11}; q^{18})_{∞}(−q^{3}; q^{6})_{∞}^{2} \\ & + 2q^{2}(−q^{2}; q^{18})_{∞}(−q^{16}; q^{18})_{∞}(−q^{6}; q^{6})_{∞}^{2}\} \end{aligned} (3.4)

There are also versions of (3.4) for 3n + 1 and 3n + 2. Equating the right sides of (3.3) and (3.4) gives rise to a surprising theta-function identity.

4. Symmetry groups.

It is natural to ask if Theorems 3A, 3B, or 3C imply congruences for the partition function p(n); for example the Ramanujan congruences for p(5n + 4), p(7n + 5), and p(11n + 6). In this section we find the symmetry groups for Theorems 3A-3C which will imply congruence theorems in §5.

How would Ramanujan’s congruences follow from Theorems 3A and 3B? We take as an example p(5n + 4) ≡ 0 mod 5. Consider Q(m, n_{3}, n_{4}, n_{5}) + LA(m, n_{3}, n_{4}, n_{5}) from Theorem 3A with t = 5 and r = 1. Suppose there exists an affine transformation T : ℤ^{4} → ℤ^{4}, T x = Mx + τ, such that

(1) T^{5} = identity,

(2) T has no fixed points in ℤ^{4},

(3) T preserves the form Q + LA. Then each orbit of T on the vectors (m, n_{3}, n_{4}, n_{5}) must consist of five vectors. This clearly implies Ramanujan’s congruence.

Thus we should compute the symmetry group G of the form Q + LA, and see if G contains a cycle of order five with property (2). For any of the forms in Theorems 3A, 3B, and 3C, we define G to be the set of affine transformations which preserve the form and the lattice ℤ^{t−1}. Table 1 lists these groups. We let ℤ_{n} denote the cyclic group of order n, and 𝔻_{n} denote the dihedral group of order 2n.

3n  ℤ_{2}  4n  ℤ_{2}  5n  𝔻_{6}  6n  ℤ_{2}  7n  𝔻_{8}
3n+1 ℤ_{2}  4n+1 ℤ_{2}  5n+1 𝔻_{4}  6n+1 ℤ_{2}  7n+1 𝔻_{6}
3n+2 ℤ_{2}  4n+2 ℤ_{2}  5n+2 𝔻_{4}  6n+2 ℤ_{2}  7n+2 𝔻_{8}
4n+3 ℤ_{2}  5n+3 𝔻_{6}  6n+3 ℤ_{2}  7n+3 𝔻_{6}
5n+4 𝔻_{5}  6n+4 ℤ_{2}  7n+4 𝔻_{6}
6n+5 ℤ_{2}  7n+5 𝔻_{7}
7n+6 𝔻_{8}

Table 1

The groups in Table 1 were found in the following way. Let L be the linear form LA, LB, or LC for Theorems 3A, 3B, and 3C respectively. Any element of G must permute the set of vectors {(m, n_{3}, …, n_{t})} on which Q + L is constant. Let the Q + L = 0 term correspond to a set V with p(r) such vectors, including the zero vector. (The five vectors for p(5n + 4) are given in §5.) If V contains at least t − 1 independent vectors, then any permutation of V induces at most one affine transformation of ℤ^{t−1}, which may or may not preserve Q + L. For small values of t the permutations can be checked by hand; large values of t require a computer.

The following proposition is in agreement with Table 1.

Proposition 3. For any r and t, the symmetry group of the forms Q+LA, Q+LB, or Q + LC contains ℤ_{2}.

Proof. Let x denote the column vector (m, n_{3}, …, n_{t}), and let L be a linear form on x. Let m(Q) be the symmetric matrix such that Qx = transpose(x)m(Q)x. It is easy to verify that T x = Mx + τ has order two, and preserves Q + L and the lattice ℤ^{t−1} if, and only if,

(1) M^{2} = I,

(2) M and τ have integral entries,

(3) Mτ = −τ,

(4) M preserves Q, QMx = Qx, (5) transpose(τ) = (LM − L)(2m(Q))^{−1}. We now give the (t − 1) × (t − 1) matrix M and the vector τ. The matrix

(2m(Q))^{−1} can be found explicitly, so that the verifications of (1)-(5) are tedious. M is independent of the residue class r. The only non-zero entries in rows 2 through t − 3 are the -1’s at (i, t − 1 − i).

M = ( \begin{matrix}1 & 0 & 0 & ⋯ & 0 & 0 & 0 \\ 0 & 0 & 0 & ⋯ & −1 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & −1 & ⋯ & 0 & 0 & 0 \\ 0 & −1 & 0 & ⋯ & 0 & 0 & 0 \\ −t & 2 & 3 & ⋯ & t − 3 & t − 2 & t − 1 \\ t & −1 & −2 & ⋯ & −(t − 4) & −(t − 3) & −(t − 2) \end{matrix} )

The vector τ does depend upon the residue class r and the form L. For r = 0 and L = LC, it is easy to see that τ = 0. For Theorem 3B, τ has at most three non-zero entries:

(1) if 2 ≤ r ≤ t − 3 and 2r + 1 ≠ t, the non-zero entries are τ_{r} = τ_{t−1−r} = 1 and τ_{t−1} = −1,

(2) if 2r + 1 = t, the non-zero entries are τ_{r} = 2 and τ_{t−1} = −1,

(3) if r = t − 2, the non-zero entries are τ_{t−2} = 1 and τ_{t−1} = −1,

(4) if r = t − 1, then τ = 0. The final residue class is r = 1 in Theorem 3A. In this case the non-zero entries are τ_{2} = 1, τ_{t−3} = 1, and τ_{t−2} = −1. □

5. Congruences.

The groups listed in §4 can be used to derive congruence theorems. We do so in this section, proving the Ramanujan congruences and verifying the Subbarao conjecture for t = 3 and t = 5. The basic idea is that elements of G of order k should give us information about p(tn + r) mod k. This information is given in the next proposition.

Proposition 4. Let g ∈ G have order p^{a}, for some prime p. If F P is the fixed point set of g in ℤ^{t−1}, then

∑_{n=0}^{∞} p(tn + r)q^{n} ≡ \frac{1}{(q)_{∞}^{t}} ∑_{(m,n_{3},...,n_{t})∈F P} q^{Q(m,n_{3},...,n_{t})+LA(m,n_{3},...,n_{t})} mod p.

For the first application of Proposition 4 and Table 1 we take p(5n + 4) ≡ 0 mod 5. Table 1 shows that the symmetry group for 5n + 4 contains an element g of order five. Thus we need F P (g) = ∅.

Here is the explicit construction of g = T. The five vectors which correspond to p(4) in Theorem 3A are (−1, 1, −1, −1), (0, 1, 1, −1), (0, 2, −1, 0), (0, 0, 0, 0), and (0, 1, 0, 0). We then take the unique affine transformation which cycles these five vectors in this order; it is T x = Mx + τ, where the matrix M and the vector τ are

M = ( \begin{matrix}4 & −1 & −2 & −3 \\ −1 & 0 & 1 & 0 \\ 2 & −1 & −2 & −2 \\ 5 & −1 & −2 & −3 \end{matrix} ) , τ = ( \begin{matrix}0 \\ 1 \\ 0 \\ 0 \end{matrix} ) .

It is easy to verify that T has no fixed points in ℤ^{4}.

The transformation T satisfies another nice property,

(5.1)  x + T x + T^{2}x + T^{3}x + T^{4}x = (−1, 5, −1, 2).

Clearly (5.1) implies that we could insert −5m, n_{3},−5n_{4}, or −5n_{5}/2 on the right side of Theorem 3A, which directly proves Ramanujan’s congruence.

Corollary 1. We have

∑_{n=0}^{∞} p(5n + 4)q^{n} = \frac{−5}{(q)_{∞}^{5}} ∑_{m,n_{3},n_{4},n_{5}=−∞}^{∞} mq^{Q(m,n_{3},n_{4},n_{5})+LA(m,n_{3},n_{4},n_{5})},

where Q and LA are given in Theorem 3A.

The proofs for p(7n + 5) and p(11n + 6) are similar. Note that corresponding dihedral groups contain a seven cycle and an eleven cycle. The corresponding affine transformations again have no fixed points. The analogues of the right side of (5.1) are (−2, 1, 7, −1, −2, −3) and (−5, 3, 2, 1, 0, 10, −2, −3, −4, −5), so we obtain the next two corollaries.

Corollary 2. We have

∑_{n=0}^{∞} p(7n + 5)q^{n} = \frac{7}{(q)_{∞}^{7}} ∑_{m,n_{3},...,n_{7}=−∞}^{∞} n_{3}q^{Q(m,n_{3},...,n_{7})+LA(m,n_{3},...,n_{7})},

where Q and LA are given in Theorem 3A.

Corollary 3. We have

∑_{n=0}^{∞} p(11n + 6)q^{n} = \frac{11}{(q)_{∞}^{11}} ∑_{m,n_{3},...,n_{11}=−∞}^{∞} n_{5}q^{Q(m,n_{3},...,n_{11})+LA(m,n_{3},...,n_{11})},

where Q and LA are given in Theorem 3A.

The next application is to consider the mod 2 behavior of p(tn + r). We take the element g of order two in the proof of Proposition 3, for which it can be shown that dimension(F P (g)) = ⌊t/2⌋. Thus, from Proposition 4, the generating function for p(tn + r) mod 2 is a ⌊t/2⌋-fold sum.

For t = 3 the sets F P (g) are

F P (g) = \{ \begin{matrix}\{(2m, 3m) : m ∈ ℤ\} for r = 0, \\ \{(2m, 3m) : m ∈ ℤ\} for r = 1, \\ \{(m, 3m − 1) : m ∈ ℤ\} for r = 2. \end{matrix}

An explicit computation of the form and the Jacobi triple product identity give the next proposition.

Proposition 5. We have

∑_{n=0}^{∞} p(3n + 2)q^{n} ≡ \frac{1}{(q)_{∞}^{3}} ∑_{m=−∞}^{∞} q^{9m^{2}−8m+1} ≡ \frac{q(q^{18}; q^{18})_{∞}(−q; q^{18})_{∞}(−q^{17}; q^{18})_{∞}}{(q)_{∞}^{3}} mod 2,

∑_{n=0}^{∞} p(3n + 1)q^{n} ≡ \frac{1}{(q)_{∞}^{3}} ∑_{m=−∞}^{∞} q^{9m^{2}−4m} ≡ \frac{(q^{18}; q^{18})_{∞}(−q^{5}; q^{18})_{∞}(−q^{13}; q^{18})_{∞}}{(q)_{∞}^{3}} mod 2,

∑_{n=0}^{∞} p(3n)q^{n} ≡ \frac{1}{(q)_{∞}^{3}} ∑_{m=−∞}^{∞} q^{9m^{2}+2m} ≡ \frac{(q^{18}; q^{18})_{∞}(−q^{7}; q^{18})_{∞}(−q^{11}; q^{18})_{∞}}{(q)_{∞}^{3}} mod 2.

For t = 4 or t = 5 the set F P (g) is two-dimensional, and cannot be evaluated by the Jacobi triple product identity. However, there are other available involutions in the appropriate dihedral group for t = 5. One may hope that for each residue class r, there is at least one involution g such that dimension(F P (g)) = 1. This is true for t = 5, r ≠ 4, and we obtain product identities analogous to Proposition

5. For p(5n + 4), each of the five involutions has a two-dimensional fixed point set. However, the generating function for F P of one these involutions is obviously diagonalizable to give the mod 2 version of Ramanujan’s generating function for p(5n + 4).

We next use these identities and Proposition 5 to verify the following conjecture for t = 3 and t = 5. A variant of this conjecture is given in [7, p. 854, §5]. Its history is given in §6.

Subbarao’s Conjecture. For 0 ≤ r ≤ t − 1, p(tn + r) is infinitely often even, and infinitely often odd.

Theorem 4. Subbarao’s conjecture holds for t = 3 and t = 5.

Before proving Theorem 4, we give a technical lemma for establishing Subbarao’s Conjecture.

Lemma 1. Let 0 ≤ r ≤ t − 1, and let Q_{1}(n) (Q_{2}(y)) be non-negative quadratic functions in one (several) variable(s), with Q_{1}(n) strictly increasing. Suppose

∑_{n=0}^{∞} q^{Q_{1}(n)} ∑_{n=0}^{∞} p(tn + r)q^{n} ≡ ∑_{y} q^{Q_{2}(y)} mod 2.

If there exists an integer s, an odd integer j, and an integer 0 ≤ i ≤ j − 1 such that (1) the equation Q_{2}(y) = Q_{1}(jm + i) + s has no integral solutions y,

(2) p(st + r) ≡ 1 mod 2, then Subbarao’s Conjecture holds for r and t.

Proof. If we find the coefficient of q^{M} we see that

∑_{n=0}^{∞} p(t(M − Q_{1}(n)) + r) ≡ |{y : Q_{2}(y) = M}| mod 2.

Next let M = Q_{1}(k)+s, and assume that p(tn+r) mod 2 is eventually the constant c. Then for large values of k,

p(ts + r) + kc ≡ |{y : Q_{2}(y) = Q_{1}(k) + s}| mod 2.

By (1), there is no solution y for the right side if k ≡ i mod j, so p(ts + r) + kc ≡ 0 mod 2. If c = 0, this contradicts (2); if c = 1, then (2) implies k must be odd. However we can take k to be even, by taking k = 2mj + i for i even, or taking k = 2mj + j + i for i odd. □

Proof of Theorem 4. Here is an outline of our proof. We will use Propositions 4 and 5 for the generating function identity assumed in Lemma 1. Then we must find an odd residue class which is missed by the quadratic function function on the right side, and hit by the quadratic function on the left side. Hopefully this class will yield a viable choice for s in (2).

For the generating functions, Proposition 4 implies

(5.2)  (q)_{∞}^{t} ∑_{n=0}^{∞} p(tn + r)q^{n} ≡ ∑_{x∈F P (g)} q^{(Q+L)x} mod 2,

for an appropriate form L. Thus we need to eliminate (q)_{∞}^{t} to apply Lemma 1. Jacobi’s identity will do this for t = 3 and t = 5,

(q)_{∞}^{3} = ∑_{n=0}^{∞}(−1)^{n}(2n + 1)q^{n(n+1)/2}

≡ ∑_{n=0}^{∞} q^{n(n+1)/2} mod 2.

For t = 5 we use

(q)_{∞}^{5} = (q)_{∞}^{6}/(q)_{∞} ≡ (q^{2}; q^{2})_{∞}^{3}/(q)_{∞} mod 2

and the Euler Pentagonal Number Theorem [1, 1.3.1].

For t = 3 (5.2) becomes

(5.3)  ∑_{n=0}^{∞} q^{n(n+1)/2} ∑_{n=0}^{∞} p(3n + r)q^{n} ≡ ∑_{x∈F P (g)} q^{(Q+L)x} mod 2

while the t = 5 version of (5.2) is

(5.4) ∑_{n=0}^{∞} q^{n(n+1)} ∑_{n=0}^{∞} p(5n + r)q^{n} ≡ ∑_{n=−∞}^{∞} q^{n(3n+1)/2} ∑_{x∈F P (g)} q^{(Q+L)x} mod 2.

We now apply Lemma 1 with Q_{1}(n) = n(n + 1)/2 and Q_{2}(x) = (Q + L)(x) for t = 3; and Q_{1}(n) = n(n + 1) and Q_{2}(x, n) = n(3n + 1)/2 + (Q + L)(x) for t = 5. Here is the list of the appropriate values for s, j, and i, and the form Q + L in Lemma 1.

(1) 3n: Q + L = 9m^{2} + 2m, s = 0, i = 3, j = 5,

(2) 3n + 1: Q + L = 9m^{2} − 4m, s = 0, i = 1, j = 5,

(3) 3n + 2: Q + L = 9m^{2} − 8m + 1, s = 1, i = 4, j = 5,

(4) 5n: Q + L = 5m^{2} + 2m, s = 0, i = 6, j = 49,

(5) 5n + 1: Q + L = 10m^{2} + 4m, s = 1, i = 3, j = 49,

(6) 5n + 2: Q + L = 10m^{2} + 8m + 1, s = 1, i = 0, j = 49,

(7) 5n + 3: Q + L = 5m^{2} + 4m, s = 2, i = 4, j = 49.

The remaining case is p(5n + 4), which has been done by Kolberg [6]. □

6. Remarks.

Ramanujan [3, p.288-289] gave elementary proofs of the congruences for p(5n+4) and p(7n + 5), while Winquist [8] gave such a proof for p(11n + 6). Our proof is also elementary, and extends to mod 2 results.

Unfortunately we are unable to give a geometric interpretation for the elements in the symmetry group G. It would be very interesting to have some geometric intuition for these elements, as opposed to our computational approach. For example, one could hope for reasonable version of a fundamental domain for the five cycle in 5n + 4 which would give Ramanujan’s generating function [5, (4.21)]. Such a fundamental domain, together with a bijection proving Theorems 3A, 3B, and 3C, may be related to the crank of Andrews and Garvan [2]. For 11n + 6 the group G is again the dihedral group of order 22. One may also hope for an interpretation of Atkin’s congruence theorem [1, p.160].

The first proof of a result analogous to Subbarao’s conjecture is due to Kolberg [6], who proved the t = 1 case. Kolberg and Subbarao did the t = 2 case (see [7, p. 854], where Subbarao also mentions the t = 4 case). One can try to apply Lemma 1 to prove the Subbarao Conjecture for values of t besides 3 or 5. For t = 4, where the fixed point set is two dimensional, a slight variation of Lemma 1 gives the Subbarao Conjecture for t = 16. Recently Hirschhorn and Subbarao [4] did this case. We could not find appropriate residue classes for the three variable quadratic functions which occur for t = 6. However, for t = 7, the eight cycle for r = 0, 2, or 6 (see Table 1) has a one dimensional fixed point set, and we find a one variable quadratic function. Lemma 1, with modulus 169, gives the Subbarao conjecture in these cases. In fact since Q_{1}(n) is always divisible by 8, we also get the t = 56 case, when r ≡ 0, 2 or 6 mod 7. Similar reasoning shows that we can establish the t = 10 case from our t = 5 theorem. Kolberg [6] has done the 7n + 5 case. No other cases are known.

Proposition 6. Subbarao’s conjecture holds for t = 10, and t = 56 and r ≡ 0, 2, or 6 mod 7.

For t = 5 Kolberg gave the generating function for p(5n + r) as a sum of two infinite products [5, (4.17)-(4.21)]. The mod 2 versions for 5n+1, 5n+2 and 5n+4 agree with our results. Note that 3 divides the order of the groups for 5n + 2 and 5n + 3. We could find a mod 3 result which agrees with Kolberg’s mod 3 versions for 5n + 2 and 5n + 3.

References

1. G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Vol. 2 (G.-C. Rota ed.), Addison-Wesley, Reading, Mass., 1976, (Reissued: Cambridge Univ. Press, London and New York, 1985)..

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

3. G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford, London, 1979.

4. M. D. Hirschhorn and M. V. Subbarao, On the parity of p(n), preprint.

5. O. Kolberg, Some identities involving the partition function, Math. Scand. 5 (1957), 77-92.

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

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

8. L. Winquist, Elementary proof of p(11m + 6) ≡ 0 (mod 11), J. Comb. Th. 6 (1969), 56-59.