ARITHMETIC PROPERTIES FOR HYPER M–ARY PARTITION FUNCTIONS

Kevin M. Courtright

Department of Mathematics, The Pennsylvania State University, University Park, PA 16802

                             kmc260@psu.edu

James A. Sellers

Department of Mathematics, The Pennsylvania State University, University Park, PA 16802

                          sellersj@math.psu.edu

Received: 3/3/04, Accepted: 4/23/04, Published: 4/23/04

Abstract

Numerous functions which enumerate partitions into powers of a fixed number m have been studied ever since Churchhouse’s original work in the late 1960’s on the unrestricted binary partition function. In particular, Calkin and Wilf recently considered the hyperbinary partition function (as they “recounted the rationals”). In this paper, we first prove an unexpected partition congruence satisfied by the hyperbinary partition function. We then consider a natural generalization of hyperbinary partitions, which we call hyper m–ary partitions, and prove surprising arithmetic properties for these via elementary means.

1. Introduction

In a recent note, Calkin and Wilf [2] utilized the enumerating function for hyperbinary partitions, h_{2}(n), to “recount the rationals.” Here h_{2}(n) is the number of ways of writing n as a sum of powers of 2, wherein each power of 2 is allowed to be used as a part at most twice.

Our first goal in this note is to study h_{2}(n) from a different perspective, that of partition congruences in arithmetic progressions, and Section is devoted to this. Then, in Section , we consider a natural generalization of h_{2}(n), denoted h_{m}(n), which is the number of partitions of n into parts which are powers of m ≥ 2 wherein each power of m is allowed to be used as a part at most m times. We close by proving a surprising infinite family of arithmetic results for h_{m}(n) for m ≥ 3 which imply infinitely many partition congruences in arithmetic progressions.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 4 (2004), #A06 2

2. A Congruence for Hyperbinary Partitions

We now focus our attention on arithmetic properties of the function h_{2}(n). Such a perspective is not at all new. Beginning with Churchhouse’s groundbreaking work on the (unrestricted) binary partition function [3], numerous authors have considered arithmetic properties for a wide variety of related binary partition functions [7], [8], [10].

It appears that very few congruences in arithmetic progressions exist for h_{2}(n). Indeed, only one such congruence is evident (based on extensive computational evidence). We prove that congruence here.

Theorem 2.1. For all n ≥ 0, h_{2}(3n + 2) ≡ 0 (mod 2).

Proof. Rather than resorting to the usual proof techniques (such as generating function dissections or bijective arguments), we prove this result by contradiction, using the following recurrences (for n ≥ 0) provided by Calkin and Wilf [2] (and the fact that h_{2}(0) = 1):

h_{2}(2n + 1) = h_{2}(n) and h_{2}(2n + 2) = h_{2}(n + 1) + h_{2}(n)  (1)

These quickly follow from the fact that the generating function for h_{2}(n) is given by

H_{2}(q) := ∑_{n≥0} h_{2}(n)q^{n} = ∏_{i≥0}(1 + q^{2^{i}} + q^{2·2^{i}}),

which means

H_{2}(q) = (1 + q + q^{2})H_{2}(q^{2}).

We assume, to contradict, that N is the smallest positive integer such that h_{2}(3N +2) is odd. We then consider three cases:

Case 1: N = 2J + 1 for some integer J

Then h_{2}(3N + 2) = h_{2}(6J + 5)
= h_{2}(3J + 2)

by (1). This yields a contradiction, as J is clearly less than N.

Case 2: N = 4J for some integer J

Then h_{2}(3N + 2) = h_{2}(12J + 2)
= h_{2}(6J + 1) + h_{2}(6J) by (1)
= h_{2}(3J) + h_{2}(3J) + h_{2}(3J − 1) by (1)
≡ h_{2}(3J − 1) (mod 2)
= h_{2}(3(J − 1) + 2).

This again yields a contradiction.

Case 3: N = 4J + 2 for some integer J

Then h_{2}(3N + 2) = h_{2}(12J + 8)
= h_{2}(6J + 4) + h_{2}(6J + 3) by (1)
= h_{2}(3J + 2) + h_{2}(3J + 1) + h_{2}(3J + 1) by (1)
≡ h_{2}(3J + 2) (mod 2).

This is a contradiction and the proof is complete.

We close this section with two remarks. First, it is clear that results involving h_{2}(n) and geometric progressions exist in abundance. For example, one can easily prove by induction that h_{2}(2^{n−1}(2^{m} − 1)) = mn − (m − 1) for all m ≥ 0 and n ≥ 1. In contrast, a result involving an arithmetic progression, such as Theorem 2.1, is quite unexpected.

Secondly, Theorem 2.1 can be strengthened. Calkin and Wilf note that, for all n ≥ 0, gcd(h_{2}(n + 1), h_{2}(n)) = 1. Hence, the theorem implies that h_{2}(3n + 1) and h_{2}(3n + 3) must be odd for all n ≥ 0. Therefore, we know

h_{2}(ℓ) ≡ 0 (mod 2) if and only if ℓ ≡ 2 (mod 3)

for all nonnegative integers ℓ.

3. A Natural Generalization

Soon after Churchhouse [3] wrote his landmark paper on the unrestricted binary partition function b_{2}(n), which enumerates the partitions of n into parts which are powers of 2, Andrews [1], Gupta [6], and Rødseth [9] proved all of Churchhouse’s results and generalized his work by considering b_{m}(n), the enumerating function for partitions of n into parts which are powers of m for some fixed m ≥ 2. Since that time, numerous authors have considered related m–ary partition functions; see [4], [5], [8], [10], and [11] for examples.

In the same vein, we now generalize hyperbinary partitions in the obvious way, letting h_{m}(n) be the number of partitions of n into powers of m wherein each power of m is allowed to be used as a part at most m times. Unlike the comment made in the previous section (that h_{2}(n) appears to satisfy only one congruence in an arithmetic progression), it is clear that h_{m}(n) behaves much differently for m ≥ 3. Indeed, we now prove that h_{m}(n) satisfies infinitely many congruences in arithmetic progressions when m ≥ 3.

For fixed m ≥ 2, the generating function for h_{m}(n) is given by

H_{m}(q) := ∑_{n≥0} h_{m}(n)q^{n} = ∏_{i≥0}(1 + q^{m^{i}} + q^{2m^{i}} + … + q^{m·m^{i}}).

Hence,

H_{m}(q) = (1 + q + q^{2} + … + q^{m})H_{m}(q^{m}),

from which we obtain the following recurrences:

h_{m}(mn) = h_{m}(n) + h_{m}(n − 1),  (2)
h_{m}(mn + r) = h_{m}(n) for 1 ≤ r ≤ m − 1  (3)

Armed with (2) and (3), and the fact that h_{m}(0) = 1, we can prove the following theorem which implies infinitely many congruence properties for the functions h_{m}(n) for m ≥ 3.

Theorem 3.1. Let m ≥ 3 and j ≥ 1 be fixed integers and let k be some integer between 2 and m − 1. Then, for all n ≥ 0,

h_{m}(m^{j}n + m^{j−1}k) = jh_{m}(n).

Proof. We prove this result by induction on j using the recurrences (2) and (3).

The basis case occurs when j = 1. In that case, the left–hand side of Theorem 3.1 is h_{m}(mn + k). Since 2 ≤ k ≤ m − 1, we see that h_{m}(mn + k) = h_{m}(n) by (3) above. This is the right–hand side of Theorem 3.1 when j = 1.

Next, assume h_{m}(m^{j}n + m^{j−1}k) = jh_{m}(n) for some positive integer j. We then wish to prove h_{m}(m^{j+1}n + m^{j}k) = (j + 1)h_{m}(n). We have

h_{m}(m^{j+1}n + m^{j}k) = h_{m}(m^{j}n + m^{j−1}k) + h_{m}(m^{j}n + m^{j−1}k − 1) by (2)
= jh_{m}(n) + h_{m}(m^{j}n + m^{j−1}k − 1)
= jh_{m}(n) + h_{m}(m(m^{j−1}n + m^{j−2}k − 1) + m − 1)
= jh_{m}(n) + h_{m}(m^{j−1}n + m^{j−2}k − 1) by (3)
= ⋮
= jh_{m}(n) + h_{m}(mn + k − 1)
= jh_{m}(n) + h_{m}(n) by (3).

This last equality is true since 2 ≤ k ≤ m−1, so that k −1 is clearly not a multiple of m. The last quantity above is clearly equal to (j + 1)h_{m}(n), which completes the proof.

We close with two comments. First, Theorem 3.1 clearly implies that for all m ≥ 3, j ≥ 1, k between 2 and m − 1, and n ≥ 0,

h_{m}(m^{j}n + m^{j−1}k) ≡ 0 (mod j).

Secondly, Theorem 3.1 can also be used to find additional results (of similar form) by iterative substitution. For example, one of the special cases of Theorem 3.1 is that, for all n ≥ 0, h_{3}(9n + 6) = 2h_{3}(n). Replacing n by 9n + 6 in this equality yields h_{3}(81n + 60) = 2h_{3}(9n + 6) = 4h_{3}(n). Because 60 is not divisible by 27, we see that this identity is different from any identity obtained by substituting m = 3 and j = 4 in Theorem 3.1.

References

[1] G. E. Andrews, Congruence properties of the m-ary partition function, J. Number Theory 3 1971, 104–110.

[2] N. Calkin and H. Wilf, Recounting the rationals, Amer. Math. Monthly 107 (2000), no. 4, 360–363.

[3] R. F. Churchhouse, Congruence properties of the binary partition function, Proc. Camb. Phil. Soc. 66 (1969), 371–376.

[4] G. Dirdal, Congruences for m-ary partitions, Math. Scand. 37 (1975), no. 1, 76–82.

[5] L. L. Dolph, A. Reynolds, and J. A. Sellers, Congruences for a restricted m-ary partition function, Discrete Math. 219 (2000), no. 1-3, 265–269.

[6] H. Gupta, On m-ary partitions, Proc. Cambridge Philos. Soc. 71 (1972), 343–345.

[7] H. Gupta, A direct proof of the Churchhouse conjecture concerning binary partitions, Indian J. Math. 18 (1976), 1–5.

[8] B. Reznick, Some binary partition functions, Analytic number theory (Allerton Park, IL, 1989), 451–477, Progr. Math., 85, Birkhauser Boston, Boston, MA, 1990.

[9] Ø. J. Rødseth, Some arithmetical properties of m-ary partitions, Proc. Cambridge Philos. Soc. 68 1970, 447–453.

[10] Ø. J. Rødseth and J. A. Sellers, Binary Partitions Revisited, J. Comb. Thy. Series A 98 (2002), 33–45.

[11] Ø. J. Rødseth and J. A. Sellers, On m-ary partition function congruences: a fresh look at a past problem, J. Number Theory 87 (2001), no. 2, 270–281.