A Congruence Modulo 3 for Partitions into Distinct Non-Multiples of Four

Michael D. Hirschhorn School of Mathematics and Statistics UNSW Sydney 2052 Australia

               m.hirschhorn@unsw.edu.au

James A. Sellers Department of Mathematics Penn State University University Park, PA 16802 USA

                   sellersj@psu.edu

Abstract

In 2001, Andrews and Lewis utilized an identity of F. H. Jackson to derive some new partition generating functions as well as identities involving some of the corresponding partition functions. In particular, for 0 < a < b < k, they defined W_{1}(a, b; k; n) to be the number of partitions of n in which the parts are congruent to a or b mod k and such that, for any j, kj + a and kj + b are not both parts. Our primary goal in this note is to prove that W_{1}(1, 3; 4; 27n + 17) ≡ 0 (mod 3) for all n ≥ 0. We prove this result using elementary generating function manipulations and classic results from the theory of partitions.

1 Introduction

In 2001, Andrews and Lewis [3] utilized an identity of F. H. Jackson to derive some new partition generating functions as well as identities involving some of the corresponding partition functions. In particular, for 0 < a < b < k, they defined W_{1}(a, b; k; n) to be the number of partitions of n in which the parts are congruent to a or b mod k and such that, for any j, kj + a and kj + b are not both parts. One of the identities that they proved was the following:

Theorem 1. The number of partitions of n into odd parts in which no part appears more than three times equals W_{1}(1, 3; 4; n).

Their proof of this theorem is extremely straightforward and involves elementary generating function manipulations.

Our focus in this note will be on this particular function W_{1}(1, 3; 4; n) (\underline{A070048} in [5]). Thus, for the remainder of this paper, we will abbreviate W_{1}(1, 3; 4; n) by W (n). Our primary goal is then to prove the following unexpected congruence:

Theorem 2. For all n ≥ 0 we have W (27n + 17) ≡ 0 (mod 3).

In Section 2, we will prove Theorem 2 via elementary generating function dissections. Prior to doing so, we make a few comments here regarding W (n) and also set some relevant notation.

First, Andrews and Lewis [3] prove that

∑_{n≥0}^{∞} W (n)q^{n} = ∏_{n≥1} (1 + q^{2n+1} + q^{2(2n+1)} + q^{3(2n+1)}) .

(Indeed, this is their generating function version of Theorem 1.) Note that the right-hand side of the above can be factored:

∑_{n≥0}^{∞} W (n)q^{n} = ∏_{n≥1}(1 + q^{2n+1})(1 + q^{2(2n+1)})  (1)

This factorization will be very useful in Section 2. Using additional generating function manipulations, it is also easy to see that

∑_{n≥0}^{∞} W (n)q^{n} = ∏_{n≥1} \frac{1 + q^{n}}{1 + q^{4n}} .

Thus, W (n) can also be interpreted as the number of partitions into distinct parts, none of which is divisible by 4. This is an interesting interpretation given the recent work of Andrews, Hirschhorn, and Sellers [2] on the function ped(n) which counts the number of partitions of n into parts which are not divisible by 4 [5, A001935].

With these brief introductory comments in hand, we now set some standard notation which will be used heavily in Section 2. Namely, we define

(a; q)_{n} := (1 − a)(1 − aq) ⋯ (1 − aq^{n−1}),

(a; q)_{∞} := lim_{n→∞}(a; q)_{n},

and

(a_{1}, a_{2}, …, a_{k}; q)_{∞} := (a_{1}; q)_{∞}(a_{2}; q)_{∞} ⋯ (a_{k}; q)_{∞}.

Later in the paper, we will shorten notation even further by defining f_{k} as

f_{k} := (q^{k}; q^{k})_{∞}.  (2)

2 Proof of Theorem 2

We begin with the generating function found in (1) and rewrite it using the notation found at the end of Section 1.

∑_{n≥0} W (n)q^{n} = ∏_{n≥1}(1 + q^{2n−1})(1 + q^{2(2n−1)}) = (−q; q^{2})_{∞}(−q^{2}; q^{4})_{∞}

We then have

(−q; q^{2})_{∞}(−q^{2}; q^{4})_{∞}

= (−q, −q^{3}, −q^{5}; q^{6})_{∞}(−q^{2}, −q^{6}, −q^{10}; q^{12})_{∞}
= \frac{(−q^{3}; q^{6})_{∞}}{(q^{6}; q^{6})_{∞}} (−q, −q^{5}, q^{6}; q^{6})_{∞} \frac{(−q^{6}; q^{12})_{∞}}{(q^{12}; q^{12})_{∞}} (−q^{2}, −q^{10}, q^{12}; q^{12})_{∞}
= \frac{(q^{6}; q^{12})_{∞}}{(q^{3}; q^{6})_{∞}(q^{6}; q^{6})_{∞}} \frac{(q^{12}; q^{24})_{∞}}{(q^{6}; q^{12})_{∞}(q^{12}; q^{12})_{∞}} (−q, −q^{5}, q^{6}; q^{6})_{∞}(−q^{2}, −q^{10}, q^{12}; q^{12})_{∞}
= \frac{1}{(q^{3}; q^{3})_{∞}(q^{24}; q^{24})_{∞}} ∑_{m,n=−∞}^{∞} q^{3m^{2}+2m+6n^{2}+4n}

via Jacobi’s Triple Product Identity [1, Theorem 2.8].

We now split the sum above into three sums according to the residue of m + 2n modulo 3: • if m + 2n ≡ 0 (mod 3), write m = t − 2u, n = t + u

• if m + 2n ≡ −1 (mod 3), write m = t − 2u − 1, n = t + u

• if m + 2n ≡ 1 (mod 3), write m = t − 2u, n = t + u − 1 Then the sum above becomes

∑_{m,n=−∞}^{∞} q^{3m^{2}+2m+6n^{2}+4n} = ∑_{t,u=−∞}^{∞} q^{3(t−2u)^{2}+2(t−2u)+6(t+u)^{2}+4(t+u)}

+ ∑_{t,u=−∞}^{∞} q^{3(t−2u−1)^{2}+2(t−2u−1)+6(t+u)^{2}+4(t+u)}

+ ∑_{t,u=−∞}^{∞} q^{3(t−2u)^{2}+2(t−2u)+6(t+u−1)^{2}+4(t+u−1)}

which, upon simplification, gives

∑_{m,n=−∞}^{∞} q^{3m^{2}+2m+6n^{2}+4n}

= ∑_{t,u=−∞}^{∞} q^{9t^{2}+6t+18u^{2}} + q ∑_{t,u=−∞}^{∞} q^{9t^{2}+18u^{2}+12u} + q^{2} ∑_{t,u=−∞}^{∞} q^{9t^{2}−6t+18u^{2}−12u}

= \frac{f_{6}^{2}f_{9}f_{36}}{f_{3}f_{12}f_{18}} \frac{f_{36}^{5}}{f_{18}^{2}f_{72}^{2}} + q \frac{f_{18}^{5}}{f_{9}^{2}f_{36}^{2}} \frac{f_{12}^{2}f_{18}f_{72}}{f_{6}f_{24}f_{36}} + q^{2} \frac{f_{6}^{2}f_{9}f_{36}}{f_{3}f_{12}f_{18}} \frac{f_{12}^{2}f_{18}f_{72}}{f_{6}f_{24}f_{36}}
= \frac{f_{6}^{2}f_{9}f_{36}^{6}}{f_{3}f_{12}f_{18}^{3}f_{72}^{2}} + q \frac{f_{12}^{2}f_{18}^{6}f_{72}}{f_{6}f_{9}^{2}f_{24}f_{36}^{3}} + q^{2} \frac{f_{6}f_{9}f_{12}f_{72}}{f_{3}f_{24}}

using the notation in (2) above. It follows that

∑_{n≥0} W (n)q^{n} = \frac{f_{2}f_{4}}{f_{1}f_{8}} = \frac{f_{6}^{2}f_{9}f_{36}^{6}}{f_{3}^{2}f_{12}f_{18}^{3}f_{24}f_{72}^{2}} + q \frac{f_{12}^{2}f_{18}^{6}f_{72}}{f_{3}f_{6}f_{9}^{2}f_{24}^{2}f_{36}^{3}} + q^{2} \frac{f_{6}f_{9}f_{12}f_{72}}{f_{3}^{2}f_{24}^{2}} .  (3)

In the same way, it can be shown that the reciprocal of the generating function for W (n) is given by

\frac{f_{1}f_{8}}{f_{2}f_{4}} = (q; q^{2})_{∞}(−q^{4}; q^{4})_{∞}
= \frac{f_{3}f_{9}^{2}f_{24}^{2}f_{36}^{2}}{f_{6}^{2}f_{12}^{3}f_{18}f_{72}} − q \frac{f_{3}^{2}f_{18}^{2}f_{24}^{2}f_{36}^{2}}{f_{6}^{3}f_{9}f_{12}^{3}f_{72}} − 2q^{5} \frac{f_{3}^{2}f_{18}^{2}f_{24}f_{72}^{2}}{f_{6}^{3}f_{9}f_{12}^{2}f_{36}} .

As a corollary of (3), we see

∑_{n≥0} W (3n + 2)q^{n} = \frac{f_{2}f_{3}f_{4}f_{24}}{f_{1}^{2}f_{8}^{2}} = \frac{f_{3}}{f_{1}^{3}} \frac{f_{24}}{f_{8}^{3}} f_{1}f_{2}f_{4}f_{8} ≡ f_{1}f_{2}f_{4}f_{8} (mod 3).

This is the first significant step in proving Theorem 2. Now we must continue the process of dissecting the generating function for W (n) (on our way to a statement about the generating function for W (27n + 17) modulo 3). Thus, we now consider the 3-dissection of

∑_{n≥0} a_{n}q^{n} := f_{1}f_{2}f_{4}f_{8}.

In the same manner as the work above, it can be proven that

f_{1}f_{2} = \frac{f_{6}f_{9}^{4}}{f_{3}f_{18}^{2}} − qf_{9}f_{18} − 2q^{2} \frac{f_{3}f_{18}^{4}}{f_{6}f_{9}^{2}} .

Replacing q by q^{4} in the above yields

f_{4}f_{8} = \frac{f_{24}f_{36}^{4}}{f_{12}f_{72}^{2}} − q^{4}f_{36}f_{72} − 2q^{8} \frac{f_{12}f_{72}^{4}}{f_{24}f_{36}^{2}} .

If we multiply these two expressions, extract those terms in which the power of q is 2 modulo 3, divide by q^{2} and replace q^{3} by q, we find that

∑_{n≥0} a_{3n+2}q^{n} = −2\frac{f_{1}f_{6}^{4}f_{8}f_{12}^{4}}{f_{2}f_{3}^{2}f_{4}f_{24}^{2}} + qf_{3}f_{6}f_{12}f_{24} − 2q^{2} \frac{f_{2}f_{3}^{4}f_{4}f_{24}^{4}}{f_{1}f_{6}^{2}f_{8}f_{12}^{2}} .

So we have

∑_{n≥0} W (9n + 8)q^{n}

≡ ∑_{n≥0} a_{3n+2}q^{n} (mod 3)

≡ \frac{f_{1}f_{6}^{4}f_{8}f_{12}^{4}}{f_{2}f_{3}^{2}f_{4}f_{24}^{2}} + qf_{3}f_{6}f_{12}f_{24} + q^{2} \frac{f_{2}f_{3}^{4}f_{4}f_{24}^{4}}{f_{1}f_{6}^{2}f_{8}f_{12}^{2}} (mod 3)
= \frac{f_{6}^{4}f_{12}^{4}}{f_{3}^{2}f_{24}^{2}} (\frac{f_{1}f_{8}}{f_{2}f_{4}} ) + qf_{3}f_{6}f_{12}f_{24} + q^{2} \frac{f_{3}^{4}f_{24}^{4}}{f_{6}^{2}f_{12}^{2}} (\frac{f_{2}f_{4}}{f_{1}f_{8}} )
= \frac{f_{6}^{4}f_{12}^{4}}{f_{3}^{2}f_{24}^{2}} (\frac{f_{3}f_{9}^{2}f_{24}^{2}f_{36}^{2}}{f_{6}^{2}f_{12}^{3}f_{18}f_{72}} − q \frac{f_{3}^{2}f_{18}^{2}f_{24}^{2}f_{36}^{2}}{f_{6}^{3}f_{9}f_{12}^{3}f_{72}} − 2q^{5} \frac{f_{3}^{2}f_{18}^{2}f_{24}f_{72}^{2}}{f_{6}^{3}f_{9}f_{12}^{2}f_{36}} )

+qf_{3}f_{6}f_{12}f_{24}

+q^{2} \frac{f_{3}^{4}f_{24}^{4}}{f_{6}^{2}f_{12}^{2}} (\frac{f_{6}^{2}f_{9}f_{36}^{6}}{f_{3}^{2}f_{12}f_{18}^{3}f_{24}f_{72}^{2}} + q \frac{f_{12}^{2}f_{18}^{6}f_{72}}{f_{3}f_{6}f_{9}^{2}f_{24}^{2}f_{36}^{3}} + q^{2} \frac{f_{6}f_{9}f_{12}f_{72}}{f_{3}^{2}f_{24}^{2}} ) .

Modulo 3, this provides us with a 3-dissection of the generating function for W (9n + 8). If we now identify only those terms above where the power on q is congruent to 1 modulo 3, it follows that

∑_{n≥0} W (27n + 17)q^{n} ≡ −\frac{f_{2}f_{4}f_{6}^{2}f_{12}^{2}}{f_{3}f_{24}} + f_{1}f_{2}f_{4}f_{8} + q \frac{f_{1}^{2}f_{3}f_{8}^{2}f_{24}}{f_{2}f_{4}} (mod 3)

≡ −\frac{f_{2}^{7}f_{4}^{7}}{f_{2}^{3}f_{8}^{3}} + f_{1}f_{2}f_{4}f_{8} + q \frac{f_{1}^{5}f_{8}^{5}}{f_{2}f_{4}} (mod 3)
= f_{1}f_{2}f_{4}f_{8} (−\frac{f_{2}^{6}f_{4}^{6}}{f_{1}^{4}f_{8}^{4}} + 1 + q \frac{f_{1}^{4}f_{8}^{4}}{f_{2}^{2}f_{4}^{2}} ) .

Our final goal is to prove that

−\frac{f_{2}^{6}f_{4}^{6}}{f_{1}^{4}f_{8}^{4}} + 1 + q \frac{f_{1}^{4}f_{8}^{4}}{f_{2}^{2}f_{4}^{2}} ≡ 0 (mod 3).  (4)

Thanks to Fine [4, Equation (32.29)], we know

\frac{f_{2}^{6}f_{4}^{6}}{f_{1}^{4}f_{8}^{4}} = 1 + 4 ∑_{n≥1} k(α)σ(m)q^{n},

where n = 2^{α}m, m odd, and

k(α) = \begin{cases}1, & if α = 0; \\ 2, & if α = 1; \\ 6, & if α ≥ 2. \end{cases}

Here σ(m) is usual sum-of-divisors function [5, A000203]. It follows that

\frac{f_{2}^{6}f_{4}^{6}}{f_{1}^{4}f_{8}^{4}} ≡ 1 + ∑_{n≥1} k(α)σ(m)q^{n} (mod 3)
≡ 1 + ∑_{m odd} σ(m)q^{m} + 2 ∑_{m odd} σ(m)q^{2m} (mod 3).  (5)

Also,

q \frac{f_{1}^{4}f_{8}^{4}}{f_{2}^{2}f_{4}^{2}} ,

which appears in [5, A121455], can be expanded by making use of the four triangles theorem [4, Equation (31.53)]:

q \frac{f_{1}^{4}f_{8}^{4}}{f_{2}^{2}f_{4}^{2}} = q (φ(−q)ψ(q^{4}))^{2}
= q(φ(q^{2})^{2} − 4qψ(q^{4})^{2})ψ(q^{4})^{2}
= qψ(q^{2})^{4} − 4q^{2}ψ(q^{4})^{4}
= ∑_{m odd} σ(m)q^{m} − 4 ∑_{m odd} σ(m)q^{2m}
≡ ∑_{m odd} σ(m)q^{m} + 2 ∑_{m odd} σ(m)q^{2m} (mod 3)  (6)

Here we have utilized φ(q) [5, A000122] and ψ(q) [5, A010054], two of Ramanujan’s famous theta series. In light of (4), (5), and (6), it follows that

∑_{n≥0} W (27n + 17)q^{n} ≡ 0 (mod 3).

3 Acknowledgements

The authors gratefully acknowledge George Andrews for directing our attention to Fine’s work [4].

References

[1] G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976; reprinted, Cambridge University Press, 1984, 1998.

[2] G. E. Andrews, M. D. Hirschhorn, and J. A. Sellers, Arithmetic properties of partitions with even parts distinct, Ramanujan J. 23 (2010), 169–181.

[3] G. E. Andrews and R. P. Lewis, An algebraic identity of F. H. Jackson and its implications for partitions, Discrete Math. 232 (2001), 77–83.

[4] N. J. Fine, Basic Hypergeometric Series and Applications, Mathematical Surveys and Monographs, 27, American Mathematical Society, 1988.

[5] The On-Line Encyclopedia of Integer Sequences, published electronically at

    http://oeis.org, 2014.

2010 Mathematics Subject Classification: 05A17, 11P83. Keywords: partition, congruence, distinct parts, non-multiples of four.

(Concerned with sequences \underline{A000122}, \underline{A000203}, \underline{A001935}, \underline{A010054}, \underline{A070048}, and \underline{A121455}.)

Received June 29 2014; revised versions received September 2 2014; September 4 2014. Published in Journal of Integer Sequences, September 4 2014.

Return to Journal of Integer Sequences home page.