DISSECTING THE STANLEY PARTITION FUNCTION

ALEXANDER BERKOVICH AND FRANK G. GARVAN

Abstract. Let p(n) denote the number of unrestricted partitions of n. For i = 0, 2, let p_{i}(n) denote the number of partitions π of n such that O(π)−O(π′) ≡ i (mod 4). Here O(π) denotes the number of odd parts of the partition π and π′ is the conjugate of π. R. Stanley [13], [14] derived an infinite product representation for the generating function of p_{0}(n) − p_{2}(n). Recently, H. Swisher [15] employed the circle method to show that

(i)  lim_{n→∞} \frac{p_{0}(n)}{p(n)} = \frac{1}{2} ,

and that for sufficiently large n

(ii)

2p_{0}(n) > p(n),  if n ≡ 0, 1 (mod 4),
2p_{0}(n) < p(n),  otherwise.

In this paper we study the even/odd dissection of the Stanley product, and show how to use it to prove (i) and (ii) with no restriction on n. Moreover, we establish the following new result

|p_{0}(2n) − p_{2}(2n)| > |p_{0}(2n + 1) − p_{2}(2n + 1)|, n > 0.

Two proofs of this surprising inequality are given. The first one uses the Göllnitz-Gordon partition theorem. The second one is an immediate corollary of a new partition inequality, which we prove in a combinatorial manner. Our methods are elementary. We use only Jacobi’s triple product identity and some naive upper bound estimates.

1. Introduction

Let π denote a partition of some integer and π′ its conjugate. Let O(π) denote the number of odd parts of π and p_{i}(n) denote the number of partitions of n for which O(π) − O(π′) ≡ i (mod 4). It is easy to see that

(1.1)  n ≡ O(π) ≡ O(π′) (mod 2)

for any partition π of n, so that

(1.2)  p(n) = p_{0}(n) + p_{2}(n),

where p(n) is the number of unrestricted partitions of n. Obviously,

(1.3)  ∑_{n≥0}(p_{0}(n) + p_{2}(n))q^{n} = ∑_{n≥0} p(n)q^{n} = \frac{1}{(q; q)_{∞}} .

Date: March 1, 2005. 2000 Mathematics Subject Classification. Primary 11P81, 11P82, 11P83; Secondary 05A17,

05A19.

Key words and phrases. generating functions, Stanley’s partitions, even/odd dissection, upper bounds, asymptotic formulas, partition inequalities.

We use the standard notation

(1.4)  (a; q)_{∞} = lim_{L→∞}(a; q)_{L},
(1.5)  (a; q)_{L} = (a)_{L} = \begin{cases}1, & if L = 0, \\ ∏_{j=0}^{L−1}(1 − aq^{j}), & if L > 0, \end{cases}

(1.6)  (a_{1}, a_{2}, …, a_{n}; q)_{∞} = (a_{1}; q)_{∞}(a_{2}; q)_{∞} ⋯ (a_{n}; q)_{∞},

and

(1.7)  (a_{1}, a_{2}, …, a_{n}; q)_{L} = (a_{1}; q)_{L}(a_{2}; q)_{L} ⋯ (a_{n}; q)_{L}.

Recently, R. Stanley [13], [14] has shown that

(1.8)  ∑_{n≥0}(p_{0}(n) − p_{2}(n))q^{n} = \frac{(−q; q^{2})_{∞}}{(q^{4}, −q^{2}, −q^{2}; q^{4})_{∞}} .

G. Andrews [2] used (1.3) and (1.8) to show that

(1.9)  ∑_{n≥0} p_{0}(n)q^{n} = \frac{E^{2}(q^{2})E^{5}(q^{16})}{E(q)E^{5}(q^{4})E^{2}(q^{32})},

where E(q) := (q; q)_{∞}. Moreover, he proved that

(1.10)  p_{0}(5n + 4) ≡ 0 (mod 5),

which is a refinement of the famous Ramanujan congruence [11]

(1.11)  p(5n + 4) ≡ 0 (mod 5).

Various combinatorial proofs of (1.8) and its generalizations were given by A. Sills [12], C. Boulet [6] and A.J. Yee [16]. A combinatorial proof of (1.10) was found by A. Berkovich and F. Garvan [5]. In a recent paper [15], H. Swisher showed that (1.10) is just one of infinitely many similar congruences satisfied by p_{0}(n). In addition, she applied the Hardy-Ramanujan ‘circle method’ [8], [3] to the product in (1.9) to deduce two interesting corollaries: Corollary 1.1 (Swisher).

lim_{n→∞} \frac{p_{0}(n)}{p(n)} = \frac{1}{2}.

Corollary 1.2 (Swisher). If n is sufficiently large, then (a) p_{0}(n) > \frac{1}{2}p(n), if n ≡ 0, 1 (mod 4),

(b) p_{0}(n) < \frac{1}{2}p(n), if n ≡ 2, 3 (mod 4).

One object of this paper is to provide elementary proofs of Corollary 1.1, and Corollary 1.2 with the restriction “n is sufficiently large” removed. To this end we will prove a Dissection Theorem for the Stanley infinite product (1.8): Theorem 1.3 (Dissection Theorem).

(1.12)  \frac{(−q; q^{2})_{∞}}{(q^{4}, −q^{2}, −q^{2}; q^{4})_{∞}} = F_{0}(−q^{2}) + qF_{1}(−q^{2}),

where

(1.13)  F_{i}(q) = \frac{1}{E(q)} \frac{1}{(q^{1+2i}, q^{2}, q^{4}, q^{6}, q^{7−2i}; q^{8})_{∞}} ,

for i = 0, 1.

The proof of this theorem, given in the next section, requires only the Jacobi triple product identity:

(1.14)  ∑_{n=−∞}^{∞} q^{n^{2}}z^{n} = (q^{2}, −zq, −q/z; q^{2})_{∞}.

We will show that the Dissection Theorem immediately implies Corollary 1.2 with no restriction on n. In Section 3 we will use only elementary methods to prove the following upper bound: Lemma 1.4 (Upper Bound Lemma). For n ≥ 0 and i = 0, 1

(1.15)  |p_{0}(2n + i) − p_{2}(2n + i)| < exp\{\frac{π}{2} \sqrt{\frac{13n}{3}}\}.

Hardy and Ramanujan [8] established in their classical paper that

(1.16)  p(n) ∼ \frac{A}{n} exp\{π\sqrt{\frac{2n}{3}}\},

with A = \frac{1}{4\sqrt{3}}. An elementary proof of (1.16) (with undetermined A) was given later by Erdős [7]. Obviously, (1.15) and (1.16) along with (1.2) imply Corollary 1.1. In Section 4 we will sharpen the upper bound in (1.15) and prove the following new result

(1.17)  |p_{0}(2n) − p_{2}(2n)| > |p_{0}(2n + 1) − p_{2}(2n + 1)|,  n ≥ 1.

Our first proof of (1.17) makes use of a relation between F_{0}(q), F_{1}(q) and the Göllnitz-Gordon products. Also we show, using Meinardus’s Theorem, that

(1.18)  lim_{n→∞} \frac{p_{0}(2n) − p_{2}(2n)}{p_{0}(2n + 1) − p_{2}(2n + 1)} = 1 + \sqrt{2}.

In Section 5, we will establish a new partition inequality from which (1.17) follows as an easy corollary. We conclude with some conjectures.

2. Proof of the Dissection Theorem and the strong version of Corollary 1.2

We begin by observing that

(2.1)  E(q) = (q; q)_{∞} = (q, q^{2}; q^{2})_{∞},

and so

(2.2)  E(−q) = (−q, q^{2}; q^{2})_{∞}.

This allows us to rewrite the right side of (1.12) as

(2.3) RHS(1.12) = \frac{1}{(−q^{2}, q^{4}; q^{4})_{∞}} \{\frac{1}{(−q^{2}, q^{4}, q^{8}, q^{12}, −q^{14}; q^{16})_{∞}}

+\frac{q}{(−q^{6}, q^{4}, q^{8}, q^{12}, −q^{10}; q^{16})_{∞}} \}

= \frac{E(q^{16})}{(−q^{2}, q^{4}, q^{4}; q^{4})_{∞}} \{\frac{1}{(−q^{2}, −q^{14}; q^{16})_{∞}} + \frac{q}{(−q^{6}, −q^{10}; q^{16})_{∞}} \} ,

where we have used

(2.4)  (q^{4}; q^{4})_{∞} = (q^{4}, q^{8}, q^{12}, q^{16}; q^{16})_{∞}.

Next, we employ

(−q^{2}, −q^{6}, −q^{10}, −q^{14}; q^{16})_{∞} = (−q^{2}; q^{4})_{∞}, (2.5)

(−q, −q^{3}; q^{4})_{∞} = (−q; q^{2})_{∞}, (2.6)

and Jacobi’s triple product identity (1.14) to obtain

(2.7)  RHS(1.12) = \frac{(q^{16}, −q^{6}, −q^{10}; q^{16})_{∞} + q(q^{16}, −q^{2}, −q^{14}; q^{16})_{∞}}{(−q^{2}, q^{4}; q^{4})_{∞}^{2}}

= \frac{∑_{j=−∞}^{∞} q^{8j^{2}+2j} + q ∑_{j=−∞}^{∞} q^{8j^{2}−6j}}{(−q^{2}, q^{4}; q^{4})_{∞}^{2}} = \frac{∑_{j=−∞}^{∞} q^{2j^{2}+j}}{(−q^{2}, q^{4}; q^{4})_{∞}^{2}}

= \frac{(q^{4}, −q, −q^{3}; q^{4})_{∞}}{(−q^{2}, q^{4}; q^{4})_{∞}^{2}} = \frac{(−q; q^{2})_{∞}}{(q^{4}, −q^{2}, −q^{2}; q^{4})_{∞}} = LHS(1.12),

as asserted.

Before we move on we would like to point out that K. Alladi [1] studied even/odd splits of many classical series. In particular, he treated the Euler pentagonal series, the Gauss triangular series and the famous Rogers-Ramanujan series.

It follows from the Dissection Theorem that for i = 0, 1

(2.8) ∑_{n≥0}(p_{0}(2n + i) − p_{2}(2n + i))q^{n} = \frac{1}{E(−q)} \frac{1}{(−q^{1+2i}, q^{2}, q^{4}, q^{6}, −q^{7−2i}; q^{8})_{∞}} .

Replacing q by −q in (2.8) we find that

(2.9) ∑_{n≥0}(−1)^{n}(p_{0}(2n + i) − p_{2}(2n + i))q^{n} = \frac{1}{E(q)} \frac{1}{(q^{1+2i}, q^{2}, q^{4}, q^{6}, q^{7−2i}; q^{8})_{∞}} ,

for i = 0, 1. It is now obvious that for n ≥ 0 and i = 0, 1

(2.10)  (−1)^{n}(p_{0}(2n + i) − p_{2}(2n + i)) > 0.

Recalling (1.2), we see that for n ≥ 0 and i = 0, 1

(2.11)  (−1)^{n}(2p_{0}(2n + i) − p(2n + i)) > 0.

In other words, we have the following corollary: For n ≥ 0,

(a) p_{0}(n) > \frac{p(n)}{2}, if n ≡ 0, 1 (mod 4),
(b) p_{0}(n) < \frac{p(n)}{2}, if n ≡ 2, 3 (mod 4).

This corollary obviously implies Corollary 1.2.

3. Proof of the Upper Bound Lemma and Corollary 1.1

Let c_{n} denote |p_{0}(n) − p_{2}(n)|. Obviously,

(3.1)  c_{n} > 0,  n ≥ 0,

and

(3.2)  ∑_{n≥0} c_{2n+i}q^{n} = F_{i}(q),  i = 0, 1.

To obtain the upper bound (1.15) for the c_{n} we will employ the standard elementary argument [4, pp.316–318], [10]. Assume 0 < q < 1 so that

(3.3)  c_{2n+i}q^{n} < F_{i}(q), i = 0, 1 and n ≥ 0.

Clearly, (3.3) is a simple consequence of (3.1), (3.2), and so we have for n ≥ 0, i = 0, 1

(3.4)  log(c_{2n+i}) < log F_{i}(q) + ns,

where q = e^{−s} and s > 0. To proceed further we make use of

(3.5)  − log(1 − x) = ∑_{m≥1} \frac{x^{m}}{m} ,

(3.6)  \frac{1}{1 − x} = ∑_{n≥0} x^{n},

to find that for i = 0, 1

(3.7)  log F_{i}(q) = ∑_{m≥1} \frac{1}{m} \frac{1}{e^{sm} − 1} + ∑_{\begin{matrix}m≥1 \\ r∈S_{i} \end{matrix}} \frac{1}{m} \frac{e^{rms}}{e^{8sm} − 1},

where S_{i} = {1 + 2i, 2, 4, 6, 7 − 2i}. Next, we shall require the following inequalities:

(3.8)  \frac{1}{e^{x} − 1} < \frac{1}{x}, x > 0,

(3.9)  \frac{e^{rx} + e^{(8−r)x}}{e^{8x} − 1} < \frac{1}{4x}, x > 0, r = 2, 3, 4,

and

(3.10)  \frac{e^{x} + e^{7x} + e^{4x} + e^{2x} + e^{6x}}{e^{8x} − 1} < \frac{5}{8x}, x > 0.

We will prove (3.8)–(3.10) later. In the mean time we observe that these inequalities imply that

(3.11)  log F_{i}(q) < \frac{1}{s} ∑_{m≥1} \frac{1}{m^{2}} + \frac{5}{8s} ∑_{m≥1} \frac{1}{m^{2}} = \frac{13}{48} \frac{π^{2}}{s} .

Combining (3.4) and (3.11) we have for i = 0, 1 and s > 0 that

(3.12)  log c_{2n+i} < \frac{13}{48} \frac{π^{2}}{s} + ns.

To minimize the right side of (3.12) we choose s = π\sqrt{13/(48n)} to find

(3.13)  log c_{2n+i} < \frac{π}{2} \sqrt{\frac{13n}{3}}

for i = 0, 1 and n ≥ 0. The above inequality (3.13) is essentially (1.15), as desired. Obviously, (1.15) and (1.16) imply that

(3.14)  lim_{n→∞} \frac{c_{n}}{p(n)} = 0.

Next, using (1.2) and

(3.15)  p_{0}(2n + i) − p_{2}(2n + i) = c_{2n+i}(−1)^{n},

we get

(3.16)  \frac{p_{0}(2n + i)}{p(2n + i)} = \frac{1}{2} + (−1)^{n} \frac{c_{2n+i}}{p(2n + i)}.

Corollary 1.1 follows easily from (3.14) and (3.16). To complete the proof all we need is to verify (3.8)–(3.10). To this end we recall that

(3.17)  e^{x} = ∑_{n≥0} \frac{x^{n}}{n!} ,

and that

(3.18)  e^{x} − 1 > 0,  if x > 0.

This allows us to rewrite (3.8) as the obvious relation

(3.19)  1 + x < e^{x},  if x > 0,

and (3.9) as

(3.20)  4x (e^{(4−r)x} + e^{−(4−r)x}) < e^{4x} − e^{−4x},  if x > 0

with r = 2, 3, 4. For r = 2, 4 (3.20) can be reduced to the obvious relation

(3.21)  rx < \frac{e^{rx} − e^{−rx}}{2} ,  if x > 0.

For r = 3 it is equivalent to

(3.22)  2x < \frac{e^{3x} − e^{−3x}}{2} − \frac{e^{x} − e^{−x}}{2} ,  if x > 0,

which follows from

(3.23)  0 < ∑_{n>0} \frac{3^{2n+1} − 1}{(2n + 1)!}x^{2n+1},  if x > 0.

To prove (3.10) we rewrite it as

(3.24)  8x (\frac{e^{3x} + e^{−3x}}{2} + \frac{e^{2x} + e^{−2x}}{2} + \frac{1}{2}) < 5\frac{e^{4x} − e^{−4x}}{2} .

Using (3.17) we can reduce it to

(3.25)  8x ∑_{n>0} \frac{9^{n} + 4^{n}}{(2n)!} x^{2n} < 5 ∑_{n>0} \frac{(4x)^{2n+1}}{(2n + 1)!},  if x > 0,

which follows from

(3.26)  8(2n + 1)(9^{n} + 4^{n}) < 20(16)^{n},  (n ≥ 1).

Finally, (3.26) can be easily proven by a straightforward induction argument.

4. Further Observations

It is possible to sharpen the upper bound in (1.15) with a little more effort. To this end we note that for i = 0, 1

∑_{n≥0}(c_{2(n+1)+i} − c_{2n+i})q^{n+1} + c_{i} = (1 − q)F_{i}(q) (4.1)

= \frac{1}{(q^{2}; q)_{∞}} \frac{1}{(q^{1+2i}, q^{2}, q^{4}, q^{6}, q^{7−2i}; q^{8})_{∞}} .

This means that for n ≥ 0

(4.2)  c_{2(n+1)+i} − c_{2n+i} ≥ 0.

Again we assume 0 < q < 1. So, instead of (3.3), we have the inequality

(4.3)  \frac{c_{2n+i}q^{n}}{1 − q} ≤ ∑_{k≥n} c_{2k+i}q^{k} ≤ F_{i}(q).

Letting q = e^{−s} and taking logarithms we obtain

(4.4)  log c_{2n+i} ≤ F_{i}(q) + ns + log(1 − e^{−s}),

for i = 0, 1, n ≥ 0 and s > 0. Moreover, for s > 0 we have

(4.5)  log(1 − e^{−s}) < log s.

It follows from (3.11), (4.4), (4.5) that

(4.6)  log c_{2n+i} < \frac{13π^{2}}{48s} + ns + log s,

for i = 0, 1, n ≥ 0 and s > 0. Evaluating the right side of (4.6) at

s = \frac{π}{2} \sqrt{\frac{13}{12}} \frac{1}{\sqrt{n}},

we get, instead of (1.15), the sharper upper bound

(4.7)  c_{2n+i} < \frac{π}{2} \sqrt{\frac{13}{12}} \frac{1}{\sqrt{n}} exp\{\frac{π}{2} \sqrt{\frac{13n}{3}}\},

for n ≥ 0 and i = 0, 1. It would be difficult to improve on (4.7) using only elementary methods. However, applying Meinardus’s Theorem [9] (see also Th. 6.1 in [3]) to the products F_{0}(q), F_{1}(q), we obtain

(4.8)  c_{2n+i} ∼ \frac{\sqrt{\frac{13}{6}}}{32 sin((2i + 1)π/8)} \frac{1}{n} exp\{\frac{π}{2} \sqrt{\frac{13n}{3}}\}  (i = 0, 1),

as n → ∞. It follows that

(4.9)  lim_{n→∞} \frac{p_{0}(2n) − p_{2}(2n)}{p_{0}(2n + 1) − p_{2}(2n + 1)} = cot \frac{π}{8} = 1 + \sqrt{2}.

Also, it is clear that for sufficiently large n

(4.10)  c_{2n} > c_{2n+1}.

Remarkably, (4.10) holds for all n ≥ 1. In order to prove this, we note that

(4.11) ∑_{n≥0} (c_{2n} − c_{2n+1}) q^{n} = F_{0}(q) − F_{1}(q) = \frac{1}{E(q)(q^{2}; q^{4})_{∞}} \{G_{0}(q) − G_{1}(q)\} ,

where

(4.12)  G_{i}(q) := \frac{1}{(q^{1+2i}, q^{4}, q^{7−2i}; q^{8})_{∞}} .

According to the Göllnitz-Gordon partition theorem (see Th. 7.11 with k = 2 in [3]) G_{i}(q), with i = 0, 1, is the generating function for partitions into parts differing by at least 2 and having no consecutive even parts. In addition, at most 1 − i parts are ≤ 2. It is now clear that the coefficients in the expansion

(4.13)  G_{0}(q) − G_{1}(q) = ∑_{k≥0} b_{k}q^{k}

are all nonnegative. It is easy to check that

(4.14)  b_{0} = b_{3} = 0, b_{1} = b_{2} = 1.

Moreover, for k ≥ 4

(4.15)  b_{k} > 0.

This is because for k ≥ 4 there is at least one partition, namely 1 + (k − 1), which is generated by G_{0}(q) but not by G_{1}(q). Next, it is obvious that

(4.16)  d_{k} > 0,

for k ≥ 0. Here the d_{k} are given by

(4.17)  \frac{1}{E(q)(q^{2}; q^{4})_{∞}} = ∑_{k≥0} d_{k}q^{k}.

It follows from (4.11), (4.14), (4.15), (4.16) that

(4.18)  c_{2n} > c_{2n+1}, if n ≥ 1.

In other words,

(4.19)  |p_{0}(2n) − p_{2}(2n)| > |p_{0}(2n + 1) − p_{2}(2n + 1)|, if n ≥ 1,

as asserted earlier.

We note that (4.18) can be proven directly without any appeal to the Göllnitz-Gordon partition theorem. In fact, all we need is to show that

(4.20)  e_{j} ≥ 0, if j ≥ 2,

where the e_{j} are given in the expansion

(4.21)  \frac{1}{(q, q^{7}; q^{8})_{∞}} − \frac{1}{(q^{3}, q^{5}; q^{8})_{∞}} = q + ∑_{j≥2} e_{j}q^{j}.

In the next section we will establish a new partition inequality, which immediately implies (4.20).

5. A Partition Inequality

Theorem 5.1. Let A_{L,i}(n) denote the number of partitions of n into parts ≡ ±(1 + 2i) (mod 8), such that the largest part ≤ 8L − 2i − 1. Then

(5.1)  A_{L,0}(n) ≥ A_{L,1}(n),

where inequality is strict for L ≥ 1, n ≠ 0, 3, 5, 6.

Obviously, the generating function for A_{L,i}(n) is given by

(5.2)  ∑_{n≥0} A_{L,i}(n)q^{n} = \frac{1}{(q^{1+2i}, q^{7−2i}; q^{8})_{L}} ,

and so (4.20) follows from (5.1) in the limit as L → ∞.

To proceed further we shall require the following

\underline{Notation.} Let |π| denote the norm (sum of parts) of a partition π. Let ν(π, i) and μ(π, i) denote the number of parts of π congruent to i (mod 8) and equal to i, respectively. Let π_{i}^{L} denote some partition generated by (5.2).

We are now ready to prove (5.1) for L = 1. We consider π_{1}^{1}. To define a corresponding partition π_{0}^{1} we consider three cases.

\underline{Case 1:} μ(π_{1}^{1}, 3) ≥ μ(π_{1}^{1}, 5). Obviously, π_{1}^{1} consists of μ(π_{1}^{1}, 5) pairs of the form (3 + 5) and of μ(π_{1}^{1}, 3) − μ(π_{1}^{1}, 5) unpaired 3’s. Let us rewrite each pair as (1 + 7) and each unpaired 3 as (1 + 1 + 1). In this way we obtain a partition π_{0}^{1} such that |π_{1}^{1}| = |π_{0}^{1}| and, in addition, μ(π_{0}^{1}, 1) ≥ μ(π_{0}^{1}, 7), and 3 | (μ(π_{0}^{1}, 1) − μ(π_{0}^{1}, 7)).

\underline{Case 2:} μ(π_{1}^{1}, 5) > μ(π_{1}^{1}, 3), and 3 ∤ (μ(π_{1}^{1}, 5)−μ(π_{1}^{1}, 3)). This time we have μ(π_{1}^{1}, 3) pairs of the form (3 + 5) and μ(π_{1}^{1}, 5) − μ(π_{1}^{1}, 3) unpaired 5’s. As before, we rewrite each pair as (1 + 7). We replace each unpaired 5 by (1 + 1 + 1 + 1 + 1). In this way we create a partition π_{0}^{1} such that |π_{1}^{1}| = |π_{0}^{1}| and, in addition, μ(π_{0}^{1}, 1) > μ(π_{0}^{1}, 7), 5 | (μ(π_{0}^{1}, 1) − μ(π_{0}^{1}, 7)), and 3 ∤ (μ(π_{0}^{1}, 1) − μ(π_{0}^{1}, 7)).

\underline{Case 3:} μ(π_{1}^{1}, 5) > μ(π_{1}^{1}, 3), and 3 | (μ(π_{1}^{1}, 5) − μ(π_{1}^{1}, 3)). Again, we rewrite each pair (3+5) as (1+7), and each but the last two unpaired 5’s as (1+1+1+1+1). The last two 5’s we replace by 7+1+1+1. This way we obtain a partition π_{0}^{1} such that |π_{1}^{1}| = |π_{0}^{1}| and, in addition, μ(π_{0}^{1}, 1) > μ(π_{0}^{1}, 7) > 0, and μ(π_{0}^{1}, 1) − μ(π_{0}^{1}, 7) ≡ 7 (mod 15).

Clearly, cases 1, 2, and 3 above describe a map from the partitions generated by \frac{1}{(1−q^{3})(1−q^{5})} to the partitions generated by \frac{1}{(1−q)(1−q^{7})}. It is important to observe that this map is 1–1 but not onto. This means that A_{1,0}(n) ≥ A_{1,1}(n), for all n ≥ 0. We show that this inequality is strict for n ≥ 7, by constructing a partition counted by A_{1,0}(n) but which is not the image of some partition counted by A_{1,1}(n). First, we observe that in each case π_{0}^{1} satisfies

(5.3)  μ(π_{0}^{1}, 1) ≥ μ(π_{0}^{1}, 7).

For m > r the partition (7^{m}, 1^{r}) does not satisfy (5.3), and so this is the desired partition for the case n = 7m+r, m > r and r = 0, 1, …, 6. To complete the proof of our assertion we need to examine integers, which are not of the form 7m + r for some m > r and 0 ≤ r < 7. It is easy to check that all such integers form the set S̃_{1} ⋃ S̃_{2} ⋃ S̃_{3}. Here,

S̃_{1} :={1, 2, 4, 8, 11, 13, 16, 17, 19, 26, 32, 34, 41},
S̃_{2} :={9, 10, 12, 24, 25, 27, 40},
S̃_{3} :={18, 20, 33, 48}.

If n ∈ S̃_{1}, then the desired partition is (1^{n}). If n ∈ S̃_{2}, then the desired partition is (7^{1}, 1^{(n−7)}). Finally, if n ∈ S̃_{3}, then the desired partitions are (7^{2}, 1^{4}), (7^{2}, 1^{6}), (7^{4}, 1^{5}), (7^{4}, 1^{20}). To see that this is indeed the case we observe that all constructed partitions satisfy 3 ∤ (μ(π_{0}^{1}, 1) − μ(π_{0}^{1}, 7)), 5 ∤ (μ(π_{0}^{1}, 1) − μ(π_{0}^{1}, 7)), (μ(π_{0}^{1}, 1) − μ(π_{0}^{1}, 7)) ≢ 7 (mod 15).

It remains to prove (5.1) for L > 1. We start by removing the multiples of 8 from each part of π_{1}^{L}. Next, we assemble the extracted multiples of 8 from the parts congruent to 3, 5 (mod 8) into two vectors 8v⃗_{3} and 8v⃗_{5}. The vectors v⃗_{3}, v⃗_{5} have nonnegative integer components, arranged in nondecreasing order. The dimensions of these vectors are ν(π_{1}^{L}, 3) and ν(π_{1}^{L}, 5), respectively. Having extracted the multiples of 8 from the parts of π_{1}^{L}, we obtain a partition π_{1}^{1}. Next we convert π_{1}^{1} into π_{0}^{1} using the map described above. Then we need to reattach the multiples of 8 to the parts of π_{0}^{1}. The procedure depends on the same three cases we considered earlier.

\underline{Case 1.} We add the components of 8v⃗_{3}, 8v⃗_{5} to the parts of π_{0}^{1} that are equal to 1, 7, respectively. This way we create a partition π_{0}^{L} that satisfies ν(π_{0}^{L}, 1) ≥ ν(π_{0}^{L}, 7), 3 | (ν(π_{0}^{L}, 1) − ν(π_{0}^{L}, 7)), and μ(π_{0}^{L}, 1) ≥ \frac{2}{3}(ν(π_{0}^{L}, 1) − ν(π_{0}^{L}, 7)). To understand this inequality observe that μ(π_{0}^{L}, 1) ≥ ν(π_{0}^{L}, 1) − ν(π_{1}^{L}, 3) = 3(ν(π_{1}^{L}, 3) − ν(π_{1}^{L}, 5)) + ν(π_{1}^{L}, 5) − ν(π_{1}^{L}, 3) = 2(ν(π_{1}^{L}, 3) − ν(π_{1}^{L}, 5)) = \frac{2}{3}(ν(π_{0}^{L}, 1) − ν(π_{0}^{L}, 7)). And so, μ(π_{0}^{L}, 1) ≥ \frac{2}{3}(ν(π_{0}^{L}, 1) − ν(π_{0}^{L}, 7)), as claimed.

\underline{Case 2.} We add the components of 8v⃗_{3}, 8v⃗_{5} to the parts of π_{0}^{1} that are equal to 7, 1, respectively. This way we obtain a partition π_{0}^{L} such that ν(π_{0}^{L}, 1) ≥ ν(π_{0}^{L}, 7), 5 | (ν(π_{0}^{L}, 1)−ν(π_{0}^{L}, 7)), 3 ∤ (ν(π_{0}^{L}, 1)−ν(π_{0}^{L}, 7)), and μ(π_{0}^{L}, 1) ≥ \frac{4}{5}(ν(π_{0}^{L}, 1)−ν(π_{0}^{L}, 7)).

\underline{Case 3.} As in Case 2, we add the components of 8v⃗_{3}, 8v⃗_{5} to the parts of π_{0}^{1} that are equal to 7, 1, respectively, and obtain a partition π_{0}^{L} such that ν(π_{0}^{1}, 1) > ν(π_{0}^{1}, 7), ν(π_{0}^{1}, 1) − ν(π_{0}^{1}, 7) ≡ 7 (mod 15), μ(π_{0}^{L}, 7) > 0 and μ(π_{0}^{L}, 1) ≥ \frac{1}{5}(4(ν(π_{0}^{L}, 1) − ν(π_{0}^{L}, 7)) − 3).

We illustrate our map with the following example. Let π_{1}^{11} = (3, 19, 43, 45^{2}, 53, 85) be a partition of 293. Note that ν(π_{1}^{11}, 3) = 3, μ(π_{1}^{11}, 3) = 1, ν(π_{1}^{11}, 5) = 4, μ(π_{1}^{11}, 5) = 0. This partition gives rise to v⃗_{3} = (0, 2, 5), v⃗_{5} = (5, 5, 6, 10), π_{1}^{1} = (3^{3}, 5^{4}), π_{0}^{1} = (1^{8}, 7^{3}), π_{0}^{11} = (1^{4}, 7, 23, 41^{2}, 47, 49, 81). Note that ν(π_{0}^{11}, 1) = 8, μ(π_{0}^{11}, 1) = 4, ν(π_{0}^{11}, 7) = 3, μ(π_{0}^{11}, 7) = 1. And so, ν(π_{0}^{11}, 1) > ν(π_{0}^{11}, 7), 5 | (ν(π_{0}^{11}, 1)−ν(π_{0}^{11}, 7)), 3 ∤ (ν(π_{0}^{11}, 1)−ν(π_{0}^{11}, 7)), μ(π_{0}^{11}, 1) > \frac{4}{5}(ν(π_{0}^{11}, 1)−ν(π_{0}^{11}, 7)), as desired.

Once again, it is straightforward to verify that we have a 1–1 map from the partitions generated by \frac{1}{(q^{3},q^{5};q^{8})_{L}} to the partitions generated by \frac{1}{(q,q^{7};q^{8})_{L}}, which is not in general onto. This gives Theorem 5.2 below.

We also note the inequality (5.1) is strict for L ≥ 1 and n ≥ 7. The proof is similar to the L = 1 case. We observe in each case that

(5.4)  ν(π_{0}^{L}, 1) ≥ ν(π_{0}^{L}, 7).

As before, the partition (7^{m}, 1^{r}) does not satisfy (5.4) when m > r, and the remaining cases can be dealt with as before. And so we have proved the following

Theorem 5.2. Let A^{∼}_{L,0}(n) denote the number of partitions π^{∼}_{0}^{L} of n into parts ≡ ±1 (mod 8), such that the largest part ≤ 8L − 1, ν(π^{∼}_{0}^{L}, 1) ≥ ν(π^{∼}_{0}^{L}, 7) and such that either

(i) 3 | (ν(π^{∼}_{0}^{L}, 1) − ν(π^{∼}_{0}^{L}, 7)), and μ(π^{∼}_{0}^{L}, 1) ≥ \frac{2}{3}(ν(π^{∼}_{0}^{L}, 1) − ν(π^{∼}_{0}^{L}, 7)), or

(ii) 5 | (ν(π^{∼}_{0}^{L}, 1)−ν(π^{∼}_{0}^{L}, 7)), 3 ∤ (ν(π^{∼}_{0}^{L}, 1)−ν(π^{∼}_{0}^{L}, 7)), and μ(π^{∼}_{0}^{L}, 1) ≥ \frac{4}{5}(ν(π^{∼}_{0}^{L}, 1)−

ν(π^{∼}_{0}^{L}, 7)), or

(iii) ν(π^{∼}_{0}^{L}, 1)−ν(π^{∼}_{0}^{L}, 7) ≡ −8 (mod 15), μ(π^{∼}_{0}^{L}, 7) > 0 and μ(π^{∼}_{0}^{L}, 1) ≥ \frac{1}{5}(4(ν(π^{∼}_{0}^{L}, 1)−

ν(π^{∼}_{0}^{L}, 7)) − 3).

Then

(5.5)  A^{∼}_{L,0}(n) = A_{L,1}(n),

where A_{L,1}(n) is defined in Theorem 5.1.

Theorems 5.1 and 5.2 with n = 19 and L = 3 are illustrated below in Table 1. The four partitions counted by A_{3,1}(19) are listed in the first column. The first four partitions in the second column are the corresponding images of our map, and are the partitions counted by A^{∼}_{3,0}(19). The 8 partitions counted A_{3,0}(19) are listed in the second column.

(19^{1})  ⟶ (1^{2}, 17^{1})
(3^{1}, 5^{1}, 11^{1}) ⟶ (1^{3}, 7^{1}, 9^{1})
(3^{2}, 13^{1})  ⟶ (1^{4}, 15^{1})
(3^{3}, 5^{2})  ⟶ (1^{5}, 7^{2})
(1^{19})
(1^{12}, 7^{1})
(1^{10}, 9)
(1^{1}, 9^{2})
Table 1. Partitions of n = 19, enumerated by A_{3,1}, A^{∼}_{3,0} and A_{3,0}

We would like to emphasise that the technique developed in this sections is by no means limited to

\frac{1}{(q, q^{7}; q^{8})_{L}} − \frac{1}{(q^{3}, q^{5}; q^{8})_{L}} .

In a very similar fashion we can prove the following theorems: Theorem 5.3. Suppose L > 0, and 1 < r < m − 1. Then the coefficients in the q-expansion of the difference of the two finite products

\frac{1}{(q, q^{m−1}; q^{m})_{L}} − \frac{1}{(q^{r}, q^{m−r}; q^{m})_{L}}

are all nonnegative, if and only if r ∤ (m − r) and (m − r) ∤ r. Theorem 5.4. Let A_{m,r}^{L}(n) denote the number of partitions of n into parts ≡ ±r (mod m), with largest part ≤ max(Lm − r, Lm + r − m). Let Ã_{m,1}^{L}(n) denote the

number of partitions π^{∼}_{m}^{L} of n, counted by A_{m,1}^{L}(n) subject to additional conditions

that ν(π^{∼}_{m}^{L}, 1) ≥ ν(π^{∼}_{m}^{L}, m − 1), and

(i) r | (ν(π^{∼}_{m}^{L}, 1)−ν(π^{∼}_{m}^{L}, m−1)), and μ(π^{∼}_{m}^{L}, 1) ≥ \frac{r−1}{r}(ν(π^{∼}_{m}^{L}, 1)−ν(π^{∼}_{m}^{L}, m−1)),

or

(ii) (m − r) | (ν(π^{∼}_{m}^{L}, 1) − ν(π^{∼}_{m}^{L}, m − 1)), r ∤ (ν(π^{∼}_{m}^{L}, 1) − ν(π^{∼}_{m}^{L}, m − 1)), and

μ(π^{∼}_{m}^{L}, 1) ≥ \frac{m−r−1}{m−r}(ν(π^{∼}_{m}^{L}, 1) − ν(π^{∼}_{m}^{L}, m − 1)), or

(iii) ν(π^{∼}_{m}^{L}, 1) − ν(π^{∼}_{m}^{L}, m − 1) ≡ −m (mod \frac{r(m−r)}{gcd(r,m−r)}), μ(π^{∼}_{m}^{L}, m − 1) > 0 and

μ(π^{∼}_{m}^{L}, 1) ≥ \frac{1}{m−r} ((m − r − 1)(ν(π^{∼}_{m}^{L}, 1) − ν(π^{∼}_{m}^{L}, m − 1)) − r).

Here, ν(π^{∼}_{m}^{L}, i) and μ(π^{∼}_{m}^{L}, i) denote the number of parts of π^{∼}_{m}^{L} congruent to i (mod m) and equal to i, respectively. Then

Ã_{m,1}^{L}(n) = A_{m,r}^{L}(n),

provided 0 < r < m, r ∤ (m − r) and (m − r) ∤ r.

We plan to study more general partition inequalities in a later paper.

Finally, we offer a prize of 500 ¥ for an elementary proof of the following conjectures:

c_{2n} < \frac{\sqrt{\frac{13}{6}}}{32 sin(π/8)} \frac{1}{n} exp\{\frac{π}{2} \sqrt{\frac{13n}{3}}\}, for n ≥ 1, and

c_{2n+1} > \frac{\sqrt{\frac{13}{6}}}{32 cos(π/8)} \frac{1}{n} exp\{\frac{π}{2} \sqrt{\frac{13n}{3}}\}, for n ≥ 2.

Acknowledgements. We are grateful to Holly Swisher for sending us her preprint [15] prior to publication. We would also like to thank George Andrews, Krishna Alladi and Hamza Yesilyurt for helpful discussions.

Note Added. After this manuscript was submitted for publication, Dennis Eichhorn brought to our attention the paper by Kevin Kadell, JCT A86, no.2 (1999), pp. 390-394. In this paper the special case of our Theorem 5.4 with m = 5, r = 2 and L → ∞ is proven.

References

1. K. Alladi, Some new observations on the Göllnitz-Gordon and Rogers-Ramanujan identities, Trans. Amer. Math. Soc. 347 (1995), 897–914.

2. G. E. Andrews, On a partition function of Richard Stanley, Electronic J. Combin. 11(2) (2004), #R1.

3. 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)

4. T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New York, 1976.

5. A. Berkovich and F. G. Garvan, On the Andrews-Stanley refinement of Ramanujan’s partition congruence modulo 5 and generalizations Trans. Amer. Math. Soc., to appear.

6. C. E. Boulet, A four-parameter partition identity, 16th Annual International Conference on Formal Power Series and Algebraic Combinatorics, url: http://www.pims.math.ca/science/2004/fpsac/Papers/Boulet.pdf

7. P. Erdős, On an elementary proof of some asymptotic formulas in the theory of partitions Ann. of Math. (2) 43 (1942), 437–450.

8. G. H. Hardy and S. Ramanujan, Asymptotic formulae in combinatory analysis Proc. London Math. Soc. 17 (1918), 75–115.

9. G. Meinardus, Über das asymptotische Verhalten von Iterationsfolgen, Z. Angew. Math. Mech. 63 (1983), 70–72.

10. A. M. Odlyzko, Analytic methods in asymptotic enumeration, Discrete Math. 153 (1996), 229–238.

11. S. Ramanujan Some properties of p(n), the number of partitions of n Proc. Camb. Philos. Soc. 19 (1919), 207–210.

12. A. V. Sills, A combinatorial proof of a partition identity of Andrews and Stanley, Int. J. Math. Math. Sci., 2004, no. 47, 2495–2503.

13. R. P. Stanley, Problem 10969, Amer. Math. Monthly 109 (2002), 760.

14. R. P. Stanley, Some remarks on sign-balanced and maj-balanced posets, Adv. in Appl. Math., to appear.

15. H. Swisher, The Andrews-Stanley partition function and p(n), preprint submitted for publication.

16. A. J. Yee, On partition functions of Andrews and Stanley, J. Combin. Theory Ser. A 107 (2004), 313–321.

Department of Mathematics, University of Florida, Gainesville, Florida 32611-8105

E-mail address: alexb@math.ufl.edu

Department of Mathematics, University of Florida, Gainesville, Florida 32611-8105

E-mail address: frank@math.ufl.edu