Parity Considerations for the Mex-Related Partition Functions of Andrews and Newman

Robson da Silva Departamento de Ciência e Tecnologia Universidade Federal de São Paulo São José dos Campos, SP, 12247–014 Brazil

                silva.robson@unifesp.br

James A. Sellers^{1} Department of Mathematics and Statistics University of Minnesota, Duluth Duluth, MN 55812 USA

                  jsellers@d.umn.edu

Abstract

In a recent paper, Andrews and Newman extended the mex-function to integer partitions and proved many partition identities connected with these functions. In this paper, we present parity considerations of one of the families of functions they studied, namely p_{t,t}(n). Among our results, we provide complete parity characterizations of p_{1,1}(n) and p_{3,3}(n).

1 Introduction

Andrews and Newman [2] recently generalized the minimal excludant function (mex-function) to apply to integer partitions. Given a partition λ of n, they defined the mex-function mex_{A,a}(λ) to be the smallest integer congruent to a modulo A that is not part of λ. They denote the number of partitions λ of n satisfying

1Corresponding author.

mex_{A,a}(λ) ≡ a (mod 2A)

by p_{A,a}(n). For example, consider n = 5, A = 3, and a = 2. In the table below, we list the seven partitions λ of n = 5 and the corresponding values of mex_{3,2}(λ) for each λ:

Partition λ mex_{3,2}(λ)
5  2
4+1  2
3+2  5
3+1+1  2
2+2+1  5
2+1+1+1  5
1+1+1+1+1  2

Table 1: Values of mex_{3,2}(λ) for partitions λ of n = 5

We see that four of the partitions in Table 1 satisfy mex_{3,2}(λ) ≡ 2 (mod 6). Therefore, p_{3,2}(5) = 4.

Andrews and Newman proved [2, Lemma 9] that the generating function for p_{t,t}(n) is given by

∑_{n=0}^{∞} p_{t,t}(n)q^{n} = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{tn(n+1)/2},  (1)

where we use the following standard q-series notation:

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

and

(a; q)_{∞} = lim_{n→∞}(a; q)_{n}, |q| < 1.

The two functions p_{1,1}(n) [7, \underline{A064428}] and p_{3,3}(n) [7, \underline{A260894}] play an important role in [2]. Indeed, Andrews and Newman proved the following connections between these two functions and the enumeration of partitions according to their rank and their crank. (In 1944, Dyson [4] defined the rank of a partition as the largest part minus the number of parts. For instance, the rank of the partition 7 + 6 + 6 + 3 + 2 is 7 − 5 = 2. He also conjectured the existence of a statistic, the crank of a partition, which would provide a combinatorial proof of Ramanujan’s congruence p(11n + 6) ≡ 0 (mod 11). In 1988, Andrews and Garvan [1] presented the definition of the crank of a partition. Given a partition λ, we let l(λ) denote the largest part of λ, w(λ) denote the number of ones in λ, and μ(λ) denote the number of parts of λ larger than w(λ). The crank c(λ) of λ is given by

c(λ) = \begin{cases}l(λ), & if w(λ) = 0; \\ μ(λ) − w(λ), & if w(λ) > 0. \end{cases}

For example, c(7 + 6 + 6 + 3 + 2) = 7 and c(7 + 6 + 6 + 3 + 2 + 1 + 1) = 4 − 2 = 2.)

Theorem 1 ([2], Theorem 2). p_{1,1}(n) equals the number of partitions of n with non-negative crank.

Theorem 2 ([2], Theorem 3). p_{3,3}(n) equals the number of partitions of n with rank ≥ −1.

In this paper, we present parity results for p_{t,t}(n) for several odd values of t. In Section 2, we present complete parity characterizations for p_{1,1}(n) and p_{3,3}(n) which are available to us thanks to the lacunarity of the corresponding generating functions modulo 2. Unfortunately, the generating function for p_{t,t}(n) modulo 2, for t > 3, fails to be as lacunary. Even so, a set of congruences modulo 2 for p_{t,t}(2kn + j), t = 5, 7, 11, 13, 17, 19, 23, is presented in Section 3. All of the proof techniques required to prove these parity results are elementary, including classical generating function manipulations and well–known results of Euler and Jacobi.

2 Parity characterizations of p_{1,1}(n) and p_{3,3}(n)

In order to prove the parity characterization for p_{1,1}(n), we need the following well-known identities.

Lemma 3. The following identities hold:

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

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

Proof. Equation (2) is Jacobi’s identity [3, Eq. (1.3.24)]. Equation (3) is Euler’s pentagonal number theorem [3, Eq. (1.3.18)].

With the above in hand, we now present the characterization modulo 2 for p_{1,1}(n).

Theorem 4. For all n ≥ 1, we have

p_{1,1}(n) ≡ \begin{cases}1 (mod 2), & if n = k(3k ± 1) for some k; \\ 0 (mod 2), & otherwise. \end{cases}

Proof. Taking k = 1 in (1), we find that

∑_{n=0}^{∞} p_{1,1}(n)q^{n} = \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞}(−1)^{n}q^{n(n+1)/2}

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

From Jacobi’s identity (2), we have

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

Using this fact and (4) we obtain an expression for the generating function for p_{1,1}(n) modulo 2:

∑_{n=0}^{∞} p_{1,1}(n)q^{n} ≡ (q; q)_{∞}^{2} ≡ (q^{2}; q^{2})_{∞} (mod 2).  (5)

In order to complete the proof, we make use of Euler’s pentagonal number theorem (3) to obtain

∑_{n=0}^{∞} p_{1,1}(n)q^{n} ≡ (q^{2}; q^{2})_{∞} ≡ ∑_{k=−∞}^{∞} q^{k(3k−1)} (mod 2)

≡ ∑_{k=1}^{∞} q^{k(3k+1)} + ∑_{k=0}^{∞} q^{k(3k−1)} (mod 2),

which completes the proof.

With Theorem 4 in hand, we can now prove a number of corollaries for specific arithmetic progressions.

Corollary 5. For all n ≥ 0, we have p_{1,1}(2n + 1) ≡ 0 (mod 2).

Proof. Note that 2n + 1 can never be represented as k(3k ± 1) because k(3k ± 1) is always even (it is twice a pentagonal number for any value k). Thus, by Theorem 4, the result follows.

Corollary 6. Let p ≥ 5 be prime, and let r, 1 ≤ r ≤ p−1, be such that 12r+1 is a quadratic non–residue modulo p. Then, for all n ≥ 0, we have p_{1,1}(pn + r) ≡ 0 (mod 2).

Proof. Note that, if pn + r = k(3k ± 1) for some k, then 12(pn + r) + 1 = (6k ± 1)^{2}. Notice also that

12(pn + r) + 1 = 12pn + 12r + 1 ≡ 12r + 1 (mod p)

but 12r + 1 is assumed to be a quadratic non–residue modulo p. Therefore, such a representation cannot exist. So by Theorem 4, we have p_{1,1}(pn + r) ≡ 0 (mod 2) for all n ≥ 0.

We discuss now the parity characterization of p_{3,3}(n). By (1) and Ramanujan’s theta function

ψ(q) = ∑_{n=0}^{∞} q^{n(n+1)/2} = \frac{(q^{2}; q^{2})_{∞}^{2}}{(q; q)_{∞}} ,  (6)

we have

∑_{n=0}^{∞} p_{3,3}(n)q^{n} ≡ \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞} q^{3n(n+1)/2} (mod 2)

= \frac{1}{(q; q)_{∞}} \frac{(q^{6}; q^{6})_{∞}^{2}}{(q^{3}; q^{3})_{∞}} (by (6))

≡ \frac{1}{(q; q)_{∞}} \frac{(q^{3}; q^{3})_{∞}^{4}}{(q^{3}; q^{3})_{∞}} (mod 2)

= \frac{(q^{3}; q^{3})_{∞}^{3}}{(q; q)_{∞}} .

The generating function for the number of 3-core partitions [5, Theorem 1], denoted by a_{3}(n) [7, \underline{A033687}], is given by

∑_{n=0}^{∞} a_{3}(n)q^{n} = \frac{(q^{3}; q^{3})_{∞}^{3}}{(q; q)_{∞}} .

So, p_{3,3}(n) ≡ a_{3}(n) (mod 2) for all n ≥ 0. Thanks to the work of Hirschhorn and Sellers [5, Theorem 6] on a closed formula for a_{3}(n), we have the following parity characterization for p_{3,3}(n):

Theorem 7. For all n ≥ 1, we have

p_{3,3}(n) ≡ \begin{cases}1 (mod 2), & if 3n + 1 is a square; \\ 0 (mod 2), & otherwise. \end{cases}

This characterization can be applied rather easily to prove several infinite families of parity results for p_{3,3}(n). We share a number of these corollaries here.

Corollary 8. For all m ≥ 0 and all n ≥ 0, we have

p_{3,3} (4^{m+1}n + \frac{7 · 4^{m} − 1}{3}) ≡ 0 (mod 2)

and

p_{3,3} (4^{m+1}n + \frac{10 · 4^{m} − 1}{3}) ≡ 0 (mod 2).

Proof. Note first that

3 (4^{m+1}n + \frac{7 · 4^{m} − 1}{3}) + 1 = 4^{m}(12n + 7)

after straightforward simplification. Note that 4^{m} is a square while 12n + 7 cannot be. (This is clear since 12n + 7 ≡ 3 (mod 4) and all squares are either 0 or 1 modulo 4). Thus

3 (4^{m+1}n + \frac{7 · 4^{m} − 1}{3}) + 1

is not a square, and the result is proved thanks to Theorem 7.

Next, note that

3 (4^{m+1}n + \frac{10 · 4^{m} − 1}{3}) + 1 = 4^{m}(12n + 10)

after straightforward simplification. Note that 4^{m} is a square while 12n + 10 cannot be. (This is clear since 12n + 10 ≡ 2 (mod 4) and all squares are either 0 or 1 modulo 4). Thus

3 (4^{m+1}n + \frac{10 · 4^{m} − 1}{3}) + 1

is not a square, and the result is proved thanks to Theorem 7.

Corollary 9. For all m ≥ 0 and all n ≥ 0, we have

p_{3,3} (2 · 4^{m+1}n + \frac{13 · 4^{m} − 1}{3}) ≡ 0 (mod 2).

Proof. Note that

3 (2 · 4^{m+1}n + \frac{13 · 4^{m} − 1}{3}) + 1 = 4^{m}(24n + 13)

after straightforward simplification. Note that 4^{m} is a square while 24n + 13 cannot be. (This is clear since 24n + 13 ≡ 5 (mod 8) and all squares are either 0, 1 or 4 modulo 8). Thus

3 (2 · 4^{m+1}n + \frac{13 · 4^{m} − 1}{3}) + 1

is not a square, and the result is proved thanks to Theorem 7.

Corollary 10. Let p ≥ 5 be prime, and let r, 1 ≤ r ≤ p−1 be such that 3r +1 is a quadratic non–residue modulo p. Then, for all n ≥ 0, we have p_{3,3}(pn + r) ≡ 0 (mod 2).

Proof. Note that 3(pn + r) + 1 can never be square. This is because

3(pn + r) + 1 = 3pn + 3r + 1 ≡ 3r + 1 (mod p)

and 3r + 1 is assumed to be a quadratic non–residue modulo p. So by Theorem 7, it follows that p_{3,3}(pn + r) ≡ 0 (mod 2) for all n ≥ 0.

3 Additional congruences

We now consider parity results for p_{t,t}(n) for t ≥ 5. While characterizations modulo 2 for these functions do not appear to be readily available, we can still prove a significant set of Ramanujan–like congruences for several of these functions.

Theorem 11. For all n ≥ 0, we have

p_{5,5}(10n + j) ≡ 0 (mod 2), j ∈ {2, 6},
p_{7,7}(14n + j) ≡ 0 (mod 2), j ∈ {7, 9, 13},
p_{11,11}(22n + j) ≡ 0 (mod 2), j ∈ {2, 8, 12, 14, 16},
p_{13,13}(26n + j) ≡ 0 (mod 2), j ∈ {2, 10, 16, 18, 20, 22},
p_{17,17}(34n + j) ≡ 0 (mod 2), j ∈ {11, 15, 17, 19, 25, 27, 29, 33},
p_{19,19}(38n + j) ≡ 0 (mod 2), j ∈ {2, 8, 10, 20, 24, 28, 30, 32, 34},
p_{23,23}(46n + j) ≡ 0 (mod 2), j ∈ {11, 15, 21, 23, 29, 31, 35, 39, 41, 43, 45}.

Proof. Let t ≥ 5 be an odd number. Taking (1) modulo 2, we have

∑_{n=0}^{∞} p_{t,t}(n)q^{n} ≡ \frac{1}{(q; q)_{∞}} ∑_{n=0}^{∞} q^{tn(n+1)/2} (mod 2)

≡ \frac{(q^{t}; q^{t})_{∞}^{3}}{(q; q)_{∞}} (mod 2)  (by (6)).  (7)

On the other hand, the generating function for t-core partitions [7, \underline{A175595}] is given by

∑_{n=0}^{∞} a_{t}(n)q^{n} = \frac{(q^{t}; q^{t})_{∞}^{t}}{(q; q)_{∞}} .

Thus, from (7) we know

∑_{n=0}^{∞} p_{t,t}(n)q^{n} ≡ \frac{(q^{t}; q^{t})_{∞}^{3}}{(q; q)_{∞}} (mod 2)

= \frac{1}{(q^{t}; q^{t})_{∞}^{t−3}} ∑_{n=0}^{∞} a_{t}(n)q^{n}.

Since t is odd, we then know

∑_{n=0}^{∞} p_{t,t}(n)q^{n} ≡ \frac{1}{(q^{2t}; q^{2t})_{∞}^{(t−3)/2}} ∑_{n=0}^{∞} a_{t}(n)q^{n} (mod 2).  (8)

The t-dissection of (8) yields, for each r ∈ {0, 1, …, t − 1},

∑_{n=0}^{∞} p_{t,t}(tn + r)q^{n} ≡ \frac{1}{(q^{2}; q^{2})_{∞}^{(t−3)/2}} ∑_{n=0}^{∞} a_{t}(tn + r)q^{n} (mod 2).

Now, after 2-dissecting both sides of the last expression we are left with

∑_{n=0}^{∞} p_{t,t}(2tn + r)q^{n} ≡ \frac{1}{(q; q)_{∞}^{(t−3)/2}} ∑_{n=0}^{∞} a_{t}(2tn + r)q^{n} (mod 2),  (9)

∑_{n=0}^{∞} p_{t,t}(2tn + t + r)q^{n} ≡ \frac{1}{(q; q)_{∞}^{(t−3)/2}} ∑_{n=0}^{∞} a_{t}(2tn + t + r)q^{n} (mod 2).  (10)

Lastly, thanks to Radu and Sellers ([6, Theorem 1.4]) we know that, for all n ≥ 0, we have

a_{5}(10n + j) ≡ 0 (mod 2), j ∈ {2, 6},
a_{7}(14n + j) ≡ 0 (mod 2), j ∈ {7, 9, 13},
a_{11}(22n + j) ≡ 0 (mod 2), j ∈ {2, 8, 12, 14, 16},
a_{13}(26n + j) ≡ 0 (mod 2), j ∈ {2, 10, 16, 18, 20, 22},
a_{17}(34n + j) ≡ 0 (mod 2), j ∈ {11, 15, 17, 19, 25, 27, 29, 33},
a_{19}(38n + j) ≡ 0 (mod 2), j ∈ {2, 8, 10, 20, 24, 28, 30, 32, 34},
a_{23}(46n + j) ≡ 0 (mod 2), j ∈ {11, 15, 21, 23, 29, 31, 35, 39, 41, 43, 45}.

This, combined with (9) and (10), implies the results of this theorem.

4 Closing thoughts

Several remarks are in order as we close. First, Andrews and Newman [2] introduce a second family of functions which they denote by p_{2t,t}(n). The reader is referred to [2] for the details of this family of functions. Our hope was that this family would also satisfy various Ramanujan–like congruence properties. Unfortunately, based on extensive computations, this does not appear to be the case.

Secondly, we close with two potential paths for future work. Namely, it would be nice to have combinatorial proofs of these parity results. It would also be gratifying to have a fully elementary proof of Theorem 11 (since Radu and Sellers relied on modular forms to carry out their proof of their parity results for t–core partition functions which were mentioned in the proof of Theorem 11).

5 Acknowledgments

The first author was supported by FAPESP (grant no. 2019/14796-8).

References

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

[2] G. E. Andrews and D. Newman, The minimal excludant in integer partitions, J. Integer Sequences 23 (2020), Article 21.2.3.

[3] B. C. Berndt, Number Theory in the Spirit of Ramanujan, American Mathematical Society, 2006.

[4] F. J. Dyson, Some guesses in the theory of partitions, Eureka 8 (1944), 10–15.

[5] M. D. Hirschhorn and J. A. Sellers, Elementary proofs of various facts about 3-cores, Bull. Aust. Math. Soc. 79 (2009), 507–512.

[6] S. Radu and J. A. Sellers, Parity results for broken k-diamond partitions and (2k + 1)- cores, Acta Arith. 146 (2011), 43–52.

[7] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2020.

2010 Mathematics Subject Classification: Primary 11P83; Secondary 05A17. Keywords: partition, parity, mex-function.

(Concerned with sequences \underline{A033687}, \underline{A064428}, \underline{A175595}, and \underline{A260894}.)

Received May 28 2020; revised version received June 5 2020. Published in Journal of Integer Sequences, June 5 2020.

Return to Journal of Integer Sequences home page.