The Borwein conjecture and partitions with prescribed hook differences

David M. Bressoud

Submitted: March 10, 1995; Accepted: May 11, 1995

Dedicated to Dominique Foata: teacher, mentor, and friend

Abstract

Peter Borwein has conjectured that certain polynomials have non-negative coefficients. In this paper we look at some generalizations of this conjecture and observe how they relate to the study of generating functions for partitions with prescribed hook differences. A combinatorial proof of the generating function for partitions with prescribed hook differences is given.

1 Introduction

In a personal communication to George Andrews in 1990, Peter Borwein made the following three conjectures. We use the notation

(a; q)_{n} = ∏_{j=0}^{n−1}(1 − a q^{j}),

\left[{N \atop M}\right] = \frac{(q^{N−M+1}; q)_{M}}{(q; q)_{M}} .

Conjecture 1 The polynomials A_{n}(q), B_{n}(q), and C_{n}(q) defined by

(q; q^{3})_{n}(q^{2}; q^{3})_{n} = A_{n}(q^{3}) − qB_{n}(q^{3}) − q^{2}C_{n}(q^{3})  (1)

have non-negative coefficients.

Conjecture 2 The polynomials A_{n}^{∗}(q), B_{n}^{∗}(q), and C_{n}^{∗}(q) defined by

(q; q^{3})_{n}^{2}(q^{2}; q^{3})_{n}^{2} = A_{n}^{∗}(q^{3}) − qB_{n}^{∗}(q^{3}) − q^{2}C_{n}^{∗}(q^{3})  (2)

have non-negative coefficients.

Conjecture 3 The polynomials A_{n}^{⋆}(q), B_{n}^{⋆}(q), C_{n}^{⋆}(q), D_{n}^{⋆}(q) and E_{n}^{⋆}(q) defined by

(q; q^{5})_{n}(q^{2}; q^{5})_{n}(q^{3}; q^{5})_{n}(q^{4}; q^{5})_{n}

= A_{n}^{⋆}(q^{5}) − qB_{n}^{⋆}(q^{5}) − q^{2}C_{n}^{⋆}(q^{5}) − q^{3}D_{n}^{⋆}(q^{5}) − q^{4}E_{n}^{⋆}(q^{5}) (3)

have non-negative coefficients.

George Andrews [1] has generalized the first two conjectures:

Conjecture 4 For m ≥ 1, the polynomials A^{†}(m, n, t, q), B^{†}(m, n, t, q), and C^{†}(m, n, t, q) defined by

(q; q^{3})_{m}(q^{2}; q^{3})_{m}(zq; q^{3})_{n}(zq^{2}; q^{3})_{n}

= ∑_{t=0}^{2n} z^{t} [A^{†}(m, n, t, q^{3}) − q B^{†}(m, n, t, q^{3}) − q^{2} C^{†}(m, n, t, q^{3})] (4)

have non-negative coefficients.

Dennis Stanton has discovered a generalization of the first conjecture. We can use the q-binomial theorem to expand (k odd, 1 ≤ a < k/2)

(q^{a}; q^{k})_{m}(q^{k−a}; q^{k})_{n} = ∑_{ν=(1−k)/2}^{(k−1)/2}(−1)^{ν}q^{k(ν^{2}+ν)/2−aν}F_{ν}(q^{k}),  (5)

where

F_{ν}(q) = ∑_{j=−∞}^{∞}(−1)^{j}q^{j(k^{2}j+2kν+k−2a)/2} \left[{m + n \atop m + ν + kj}\right] .  (6)

Each monomial in q^{k(ν^{2}+ν)/2−aν}F_{ν}(q^{k}) involves a power of q for which the exponent is congruent to −aν modulo k.

Conjecture 5 If a is relatively prime to k and m = n, then the coefficients of F_{ν}(q) are non-negative.

The polynomial F_{ν}(q) appears to be a special case of the generating function for partitions “with prescribed hook differences,” [2]. In particular, it is shown in that paper that if α + β < 2K and −K + β ≤ n − m ≤ K − α, then

G(α, β, K; q) = ∑_{j}(−1)^{j}q^{j[K(α+β)j+K(α−β)]/2} \left[{m + n \atop m + Kj}\right]  (7)

is the generating function for partitions inside an m × n rectangle with “hook difference conditions” specificed by α, β, and K. The polynomial F_{ν}(q) is simply the special case

K = k, α = ν + \frac{k + 1}{2} − \frac{a}{k} , β = −ν + \frac{k − 1}{2} + \frac{a}{k} .

Since we know that this is a generating function, it follows that the coefficients are non-negative.

The only problem with this analysis is that the hook difference conditions defined in [2] only make sense for integer values of α, β, and K. In section 2, we will examine these hook difference conditions, and in section 3 we will consider what is involved in extending the definition to non-integer values. We are not able to show that F_{ν}(q) is a generating function. However, it is possible to construct a family of partition generating functions, A_{m,n}(q), that are remarkably close to A_{n}(q) when m = n. Furthermore, it appears that conjecture 5 can be strengthened to the following.

Conjecture 6 Let α and β be positive rational numbers and K an integer greater than 1 such that αK and βK are integers. If 1 ≤ α + β ≤ 2K − 1 (with strict inequalities when K = 2) and −K + β ≤ n − m ≤ K − α, then G(α, β, K; q) has non-negative coefficients.

This conjecture is justified heuristically by the arguments of section 3. Several special cases have been verified. For K = 2 and m = n, this author has proven identities that imply the conjecture for α = 1, β = 1/2 and α = 3/2, β = 1 [4]:

G(1, 1/2, 2; q) = ∑_{j=0}^{m} q^{jm} \left[{m \atop j}\right] ,  (8)

G(3/2, 1, 2; q) = ∑_{j=0}^{m} q^{j^{2}} \left[{m \atop j}\right] .  (9)

Mourad Ismail and Dennis Stanton [5] have proven that the conjecture holds if

α + β = K  and  α − β = m − n + 1.

Experimentally, it appears that the bounds on n − m are sharp. For example, A_{n}(q) = G(5/3, 4/3, 3; q) with m = n. The conjecture states that G(5/3, 4/3, 3; q) has non-negative coefficients when |n − m| ≤ 1:

m n G(5/3, 4/3, 3; q)
2 1 1 + q + q^{2}
2 1 + q + 2q^{2} + q^{3} + q^{4}
3 1 + q + 2q^{2} + 2q^{3} + 2q^{4} + q^{6}
4 1 + q + 2q^{2} + 2q^{3} + 3q^{4} + q^{5} + q^{6} − q^{9} − q^{10}
3 1 1 + q + q^{2} + q^{3} − q^{4}
2 1 + q + 2q^{2} + 2q^{3} + q^{4} + q^{5} + q^{6}
3 1 + q + 2q^{2} + 3q^{3} + 2q^{4} + 2q^{5} + 3q^{6} + 2q^{7} + q^{8} + q^{9}
4 1 + q + 2q^{2} + 3q^{3} + 3q^{4} + 3q^{5} + 4q^{6} + 3q^{7} + 3q^{8} + 2q^{9} + q^{10} + q^{12}
5 1 + q + 2q^{2} + 3q^{3} + 3q^{4} + 4q^{5} + 5q^{6} + 4q^{7} + 4q^{8} + 3q^{9} + 2q^{10} − q^{13}
−q^{14} − q^{15} − q^{16} − q^{17}
4 2 1 + q + 2q^{2} + 2q^{3} + 2q^{4} + q^{5} + q^{6} − q^{9}
3 1 + q + 2q^{2} + 3q^{3} + 3q^{4} + 2q^{5} + 4q^{6} + 3q^{7} + 3q^{8} + 2q^{9} + q^{10} + q^{11}
+q^{12}
4 1 + q + 2q^{2} + 3q^{3} + 4q^{4} + 3q^{5} + 5q^{6} + 5q^{7} + 6q^{8} + 5q^{9} + 5q^{10} + 3q^{11}
+4q^{12} + 3q^{13} + 2q^{14} + q^{15} + q^{16}
5 1 + q + 2q^{2} + 3q^{3} + 4q^{4} + 4q^{5} + 6q^{6} + 6q^{7} + 8q^{8} + 7q^{9} + 8q^{10} + 6q^{11}
+6q^{12} + 5q^{13} + 5q^{14} + 3q^{15} + 3q^{16} + q^{17} + q^{18} + q^{20}
6 1 + q + 2q^{2} + 3q^{3} + 4q^{4} + 4q^{5} + 7q^{6} + 7q^{7} + 9q^{8} + 9q^{9} + 10q^{10} + 8q^{11}

+9q^{12} + 6q^{13} + 6q^{14} + 4q^{15} + 3q^{16} − q^{19} − 2q^{20} − 2q^{21} − 2q^{22} − 2q^{23}

−q^{24} − q^{25} − q^{26}

I wish to acknowledge Dennis Stanton’s contribution to this paper in the form of many fruitful discussions.

2 Partitions with prescribed hook differences

Given a partition λ whose ith largest part is λ_{i}, we define λ′_{i} to be the ith largest part in the conjugate partition (λ′_{i} is the number of parts that are greater than or equal to i). We say that λ fits inside an m×n rectangle if m ≥ λ′_{1} and n ≥ λ_{1}. If (i, j) ∈ λ (equivalently, if λ_{i} ≥ j), then we define the hook difference at position (i, j) to be λ_{i} − λ′_{j}. The diagonal δ is the set of all positions (i, j) ∈ λ for which i − j = δ. The following proposition is a special case of theorem 1 in [2].

Proposition 1 If −K + β ≤ n − m ≤ K − α where α, β, and K are positive integers, α + β < 2K, then G(α, β, K; q) as defined in equation (7) is the generating function for partitions inside an m × n rectangle for which the hook differences on diagonal α − 1 are less than or equal to K − α − 1 and the hook differences on diagonal 1 − β are greater than or equal to β + 1 − K.

The proof of this proposition given in [2] relies on recurrences and does not lend itself to non-integer values of α or β. However, as we shall demonstrate, there is a combinatorial proof of this proposition that uses the approach of [3]. It is this proof that appears to be amenable to generalization.

Proof: We shall use the Frobenius representation of a partition,

λ = ( \begin{matrix}a_{1}, & a_{2}, & …, & a_{t} \\ b_{1}, & b_{2}, & …, & b_{t} \end{matrix} ) ,

where a_{i} = λ_{i} − i, b_{i} = λ′_{i} − i, and t is the largest integer for which λ_{t} ≥ t. We note that a_{1} > a_{2} > ⋯ > a_{t} ≥ 0, b_{1} > b_{2} > ⋯ > b_{t} ≥ 0, and the number being partitioned is t + ∑(a_{i} + b_{i}). We want to show that G(α, β, K; q) is the generating function for partitions whose Frobenius representation satisfies

a_{1} < n,  b_{1} < m
a_{i} − b_{i−α+1} ≤ K − 2α,  b_{i} − a_{i−β+1} ≤ K − 2β, for all i. (10)

We shall say that a partition has an (α, β, K) positive oscillation of length j, j ≥ 1, if we can find a sequence i_{1} < i_{2} < ⋯ < i_{j} for which

a_{i_{1}} − b_{i_{1}−α+1} > K − 2α,
b_{i_{2}} − a_{i_{2}−β+1} > K − 2β,
⋮
\{ \begin{matrix}a_{i_{j}} − b_{i_{j}−α+1} > K − 2α, & j odd, \\ b_{i_{j}} − a_{i_{j}−β+1} > K − 2β, & j even. \end{matrix}  (11)

A partition has an (α, β, K) negative oscillation of length j, j ≥ 1, if we can find a sequence i_{1} < i_{2} < ⋯ < i_{j} for which

b_{i_{1}} − a_{i_{1}−β+1} > K − 2β,
a_{i_{2}} − b_{i_{2}−α+1} > K − 2α,
⋮
\{ \begin{matrix}a_{i_{j}} − b_{i_{j}−α+1} > K − 2α, & j even, \\ b_{i_{j}} − a_{i_{j}−β+1} > K − 2β, & j odd. \end{matrix}  (12)

Lemma 1 If α, β, and K are positive integers with α+β < 2K and if −K+β ≤ n − m ≤ K − α, then the generating function for partitions inside an m × n rectangle with an (α, β, K) positive oscillation of length j is

f_{α,β,K}^{+}(j; q) = q^{j[K(α+β)j+K(α−β)]/2} \left[{m + n \atop m + Kj}\right] .  (13)

By conjugating the partition (interchanging the as and bs in the Frobenius representation), this lemma implies that the generating function for partitions inside an m × n rectangle with an (α, β, K) negative oscillation of length j is

f_{α,β,K}^{−}(j; q) = q^{j[K(α+β)j−K(α−β)]/2} \left[{m + n \atop m − Kj}\right] .  (14)

Lemma 1 thus implies that

G(α, β, K; q) = \left[{m + n \atop m}\right] + ∑_{j=1}^{∞}(−1)^{j} [f_{α,β,K}^{+}(j; q) + f_{α,β,K}^{−}(j; q)] .  (15)

Proposition 1 is an immediate consequence of equation (15): \left[{m+n \atop m}\right] is the generating function for all partitions that sit inside an m × n box, and if such a partition has a positive or negative oscillation and if j is the length of the longest such oscillation, then the alternating sum will count it with a total weight of

−2 ⌊\frac{j}{2}⌋ + 2 ⌊\frac{j − 1}{2}⌋ + (−1)^{j} = −1.

Proof of lemma 1: Let λ be a partition into at most m + Kj parts, each part less than or equal to n − Kj. If i is greater than the number of parts in λ, then we define λ_{i} = 0. We let t be the largest integer (≥ 0) such that

λ_{2⌈j/2⌉α+2⌊j/2⌋β+t} ≥ t,  (16)

and then define sequences a_{1}, …, a_{μ} and b_{1}, …, b_{μ}, μ = ⌈j/2⌉α + ⌊j/2⌋β + t, as follows. If j is even, then

a_{i} = { λ_{i} + jK − i,  1 ≤ i ≤ α, ; λ_{i+α+β} + (j − 2)K + α + β − i,  α + 1 ≤ i ≤ 2α + β, ; λ_{i+2(α+β)} + (j − 4)K + 2(α + β) − i, 2α + β + 1 ≤ i ≤ 3α + 2β, ; ⋮ ; λ_{i+j(α+β)/2} + j(α + β)/2 − i, ; j(α + β)/2 − β + 1 ≤ i ≤ j(α + β)/2 + t,

(17)

b_{i} = \{ λ_{α+i} + (j − 1)K + α − i,  1 ≤ i ≤ α + β, ; λ_{2α+β+i} + (j − 3)K + 2α + β − i,  α + β + 1 ≤ i ≤ 2(α + β), ; λ_{3α+2β+i} + (j − 5)K + 3α + 2β − i, 2(α + β) + 1 ≤ i ≤ 3(α + β), ; ⋮ ; λ_{j(α+β)/2−β+i} + K + j(α + β)/2 − β − i, ; (\frac{j}{2} − 1)(α + β) + 1 ≤ i ≤ j(α + β)/2, ; λ′_{i−j(α+β)/2} − j(α + β)/2 − i, ; j(α + β)/2 + 1 ≤ i ≤ j(α + β)/2 + t.

We note that

\frac{j}{2}(α + β) + t + ∑_{i}(a_{i} + b_{i}) = ∑_{i=1}^{j(α+β)+t} λ_{i} + ∑_{i=1}^{t} λ′_{i} − t[j(α + β) + t]

+\frac{j}{2}[K(α + β)j + K(α − β)]

= ∑_{i≥1} λ_{i} + \frac{j}{2}[K(α + β)j + K(α − β)].

(19)

If j is odd then,

a_{i} = { λ_{i} + jK − i,  1 ≤ i ≤ α, ; λ_{i+α+β} + (j − 2)K + α + β − i,  α + 1 ≤ i ≤ 2α + β, ; ⋮ ; λ_{i+(j−1)(α+β)/2} + K + (j − 1)(α + β)/2 − i, ; (j − 1)(α + β)/2 − β + 1 ≤ i ≤ α + (j − 1)(α + β)/2, ; λ′_{i−α−(j−1)(α+β)/2} − α − (j − 1)(α + β)/2 − i, ; α + (j − 1)(α + β)/2 + 1 ≤ i ≤ α + (j − 1)(α + β)/2 + t,

(20)

b_{i} = { λ_{α+i} + (j − 1)K + α − i,  1 ≤ i ≤ α + β, ; λ_{2α+β+i} + (j − 3)K + 2α + β − i, α + β + 1 ≤ i ≤ 2(α + β), ; ⋮ ; λ_{α+(j−1)(α+β)/2+i} + α + (j − 1)(α + β)/2 − i, ; (j − 1)(α + β)/2 + 1 ≤ i ≤ (j − 1)(α + β)/2 + α + t.

(21)

Here we have that

α + \frac{j − 1}{2}(α + β) + t + ∑_{i}(a_{i} + b_{i}) = ∑_{i=1}^{(j+1)α+(j−1)β+t} λ_{i} + ∑_{i=1}^{t} λ′_{i}

− t[(j + 1)α + (j − 1)β + t]

+ \frac{j}{2}[K(α + β)j + K(α − β)]

= ∑_{i≥1} λ_{i} + \frac{j}{2}[K(α + β)j + K(α − β)].

(22)

The α_{i} and β_{i} are non-negative integers because of the choice of t. Since λ_{1} ≤ n − jK and n − m ≤ K − α, we have that

a_{1} = λ_{1} + jK − 1 < n,  (23)

b_{1} = λ_{α+1} + (j − 1)K + α − 1 < m.  (24)

Furthermore, if we take i_{1} = α, i_{2} = α + β, i_{3} = 2α + β, i_{4} = 2α + 2β, …, i_{j} = ⌈j/2⌉α + ⌊j/2⌋β, then these sequences satisfy the inequalities in (11) that characterize a partition with an (α, β, K) positive oscillation of length j. The only reason why these sequences might not represent a partition with an (α, β, K) positive oscillation of length j is that we might have

b_{j(α+β)/2} ≤ b_{j(α+β)/2+1}

when j is even or

a_{α+(j−1)(α+β)/2} ≤ a_{α+(j−1)(α+β)/2+1}

when j is odd.

2.1 Combinatorial proof of equivalence: first direction

We now perform a shifting operation that is done, successively, for each integer value of r from j down through 1. Initially, we take i_{j+1} to be ∞, i_{r} = ⌈r/2⌉α+ ⌊r/2⌋β for j ≥ r ≥ 1. Our objective is to define a bijection between the pairs of sequences given above and the pairs of sequences that give the Frobenius representation for partitions inside an m×n rectangle with an (α, β, K) positive oscillation of length j.

If r is even:

τ = b_{i_{r}} − a_{i_{r}−β+1},  (25)
κ = max{ν | i_{r} < ν ≤ i_{r+1} − α, b_{ν} − a_{ν−β+1} > τ},  (26)
γ(ν) = max{b_{i} − a_{i−β+1} − τ | ν ≤ i ≤ κ}.  (27)

If the set that defines κ is empty, then we do no shifting for this value of r. Otherwise, for i_{r} < ν ≤ κ, we set

b_{ν} ⟵ b_{ν} − γ(ν),  (28)
a_{ν−β} ⟵ a_{ν−β} + γ(ν),  (29)

and then reset the value of i_{r} to κ.

If r is odd:

τ = a_{i_{r}} − b_{i_{r}−α+1},  (30)
κ = max{ν | i_{r} < ν ≤ i_{r+1} − β, a_{ν} − b_{ν−α+1} > τ},  (31)
γ(ν) = max{a_{i} − b_{i−α+1} − τ | ν ≤ i ≤ κ}.  (32)

If the set that defines κ is empty, then we do no shifting for this value of r. Otherwise, for i_{r} < ν ≤ κ, we set

a_{ν} ⟵ a_{ν} − γ(ν),  (33)
b_{ν−α} ⟵ b_{ν−α} + γ(ν),  (34)

and then reset the value of i_{r} to κ.

We claim that this shifting procedure yields a pair of sequences that give the Frobenius representation for a partition inside an m × n rectangle with an (α, β, K) positive oscillation of length j.

If j is even, then after doing the shift for r = j, the new value of b_{j(α+β)/2} is strictly larger than the new value of b_{j(α+β)/2+1}. To see this, we observe that the value of b_{j(α+β)/2} does not change, and if the old value of b_{j(α+β)/2+1} is greater than or equal to the old value of b_{j(α+β)/2}, then

γ(j(α +β)/2+1) ≥ b_{j(α+β)/2+1} −a_{j(α+β)/2−β+2} −(b_{j(α+β)/2} − a_{j(α+β)/2−β+1}) ,

(35)

so that the new value of b_{j(α+β)/2+1} equals

b_{j(α+β)/2+1} − γ(j(α + β)/2 + 1) ≤ b_{j(α+β)/2} + a_{j(α+β)/2−β+2} − a_{j(α+β)/2−β+1}
< b_{j(α+β)/2}.  (36)

The function γ is weakly decreasing, and so the new values of a_{ν−β} are still strictly decreasing. We do need to verify that

b_{ν} − γ(ν) > b_{ν+1} − γ(ν + 1).

This will be true if γ(ν) = γ(ν + 1). If these values of γ are not equal, then by definition:

γ(ν) = b_{ν} − a_{ν−β+1} − τ,  γ(ν + 1) ≥ b_{ν+1} − a_{ν−β+2} − τ. (37)

It follows that

b_{ν} − γ(ν) = a_{ν−β+1} + τ > a_{ν−β+2} + τ ≥ b_{ν+1} − γ(ν + 1). (38)

We note that after the shift for r = j, the value of a_{j(α+β)/2−β} might be less than or equal to the new value of a_{j(α+β)/2−β+1} which will be bounded by

a_{j(α+β)/2−β+1} < λ′_{1} − jα − (j − 2)β − K.  (39)

After the next shift, for r = j − 1, the new value of a_{j(α+β)/2−β} will be strictly greater than the new value of a_{j(α+β)/2−β+1}.

The same argument holds mutatis mutandis if j is odd and for each successive value of r. If r is even, then the new value of a_{⌈r/2⌉α+⌊r/2⌋β−β+1} is bounded by

a_{⌈r/2⌉α+⌊r/2⌋β−β+1} < λ′_{1} − rα − (r − 2)β − (j − r + 1)K.  (40)

If r is odd, then the new value of b_{⌈r/2⌉α+⌊r/2⌋β−α+1} is bounded by

b_{⌈r/2⌉α+⌊r/2⌋β−α+1} < λ′_{1} − (r − 1)α − (r − 1)β − (j − r + 1)K. (41)

We observe that the value of a_{1} is left unchanged and so is strictly less than n, and that the final value of b_{1} (after the shift that corresponds to r = 1) is strictly less than λ′_{1} − jK ≤ m.

2.2 Combinatorial proof of equivalence: other direction

To see that we do, in fact, have a bijection we note that we can uniquely reconstruct the values of τ, κ, and γ(ν) for each shift as r runs from 1 back up to j. We first choose the sequence i_{1} < i_{2} < ⋯ < i_{j} maximally. That is to say, we find the largest integer i_{j} for which b_{i_{j}} − a_{i_{j}−β+1} > K − 2β (if j is even) or a_{i_{j}} − b_{i_{j}−α+1} > K − 2α (if j is odd), and then after each i_{r} is chosen, we choose the largest possible value for i_{r−1}. To reverse the shifting process, we perform the following operation for each r from 1 through j.

If r is even:

τ^{∗} = max{b_{ν} − a_{ν−β+1} | r(α + β)/2 ≤ ν ≤ i_{r}},  (42)
κ^{∗} = min{ν | r(α + β)/2 ≤ ν ≤ i_{r}, b_{ν} − a_{ν−β+1} = τ^{∗}},  (43)
γ^{∗}(ν) = min{τ^{∗} − (b_{i} − a_{i−β+1}) | r(α + β)/2 ≤ i < ν}.  (44)

For r(α + β)/2 < ν ≤ κ^{∗}, we set

b_{ν} ⟵ b_{ν} + γ^{∗}(ν),  (45)
a_{ν−β} ⟵ a_{ν−β} − γ^{∗}(ν).  (46)

If r is odd:

τ^{∗} = max{a_{ν} − b_{ν−α+1} | ⌈r/2⌉α + ⌊r/2⌋β ≤ ν ≤ i_{r}},  (47)
κ^{∗} = min{ν | ⌈r/2⌉α + ⌊r/2⌋β ≤ ν ≤ i_{r}, a_{ν} − b_{ν−α+1} = τ^{∗}}, (48)
γ^{∗}(ν) = min{τ^{∗} − (a_{i} − b_{i−α+1}) | ⌈r/2⌉α + ⌊r/2⌋β ≤ i < ν}.  (49)

For ⌈r/2⌉α + ⌊r/2⌋β < ν ≤ κ^{∗}, we set

a_{ν} ⟵ a_{ν} + γ^{∗}(ν),  (50)
b_{ν−α} ⟵ b_{ν−α} − γ^{∗}(ν).  (51)

It is left to the reader to verify that this does uniquely reverse the shifting done in section 2.1. To prove that we have a bijection between pairs of sequences generated by f_{α,β,K}^{+}(j; q) and partitions inside an m × n rectangle with an (α, β, K) positive oscillation of lenth j, we need to verify that if we start with an arbitrary partition, we get a pair of sequences generated by f_{α,β,K}^{+}(j; q). The only condition on these sequences that is not straightforward to verify is that they are strictly decreasing with the possible exception that if j is even then we might have b_{j(α+β)/2+1} ≥ b_{j(α+β)/2} and if j is odd then we might have a_{⌈j/2⌉α+⌊j/2⌋β+1} ≥ a_{⌈j/2⌉α+⌊j/2⌋β}.

We observe that in applying the shift given above for r = 1, the new value for a_{α} might be less than or equal to the new value for a_{α+1}. If j = 1, there is no problem. If j is larger than 1, then on the r = 2 shift we replace a_{α+1} with

a_{α+1} ⟵ a_{α+1} − (τ^{∗} − b_{α+β} + a_{α+1}) = b_{α+β} − τ^{∗}.

We note that if the new value of a_{α+1} is greater than or equal to the new value of a_{α}, then the value of b_{1} after the r = 1 shift is strictly less than its original value. This implies that after the r = 1 shift we have a_{α} − b_{1} > K − 2α. We combine this observation with the following inequalities:

b_{1} − b_{α+β} ≥ α + β − 1,  (52)
τ^{∗} ≥ K − 2β,  (53)
2K > α + β,  (54)

to see that

b_{α+β} − τ^{∗} < a_{α}.  (55)

The new value of a_{α+1} after the r = 2 shift is strictly less than a_{α}. This argument continues to hold for each r < j so that after all of the shifting we have at most one pair of consecutive elements in the sequences for which we do not have strict decrease.

Q.E.D.

3 Prescribed Hook Differences with non-integer parameters

We want to define a prescribed hook difference condition when α and β are not integers. While there does not seem to be hope for doing this in general, the particular case

α = ν + \frac{K + 1}{2} − \frac{a}{K} ,  β = −ν + \frac{K − 1}{2} + \frac{a}{K}  (56)

does hold promise. In particular, let

α = \overline{α} − a/K,  β = \overline{β} + a/K,  (57)

where \overline{α} and \overline{β} are positive integers and a is a positive integer less than or equal to min\{\overline{α}, \overline{β}\}. Let \{\overline{a}_{i}\} and \{\overline{b}_{i}\} be the pair of sequences generated by

f_{\overline{α},\overline{β},K}^{+}(j; q) = q^{j[K(\overline{α}+\overline{β})j+K(\overline{α}−\overline{β})]/2} \left[{m + n \atop m + Kj}\right]

as given in equations (17–18) and (20–21). We now define

a_{i} = \overline{a}_{i} − \{ \begin{matrix}1, & if \overline{α} − a + 1 ≤ (i mod \overline{α} + \overline{β}) ≤ \overline{α} \\ & and i ≤ ⌈j/2⌉(\overline{α} + \overline{β}) − \overline{β}, \\ 0, & otherwise, \end{matrix}  (58)

b_{i} = \overline{b}_{i} − \{ \begin{matrix}1, & if \overline{α} + \overline{β} − a + 1 ≤ (i mod \overline{α} + \overline{β}) ≤ \overline{α} + \overline{β}, \\ & and i ≤ ⌊j/2⌋(\overline{α} + \overline{β}), \\ 0, & otherwise, \end{matrix} (59)

where (i mod \overline{α} + \overline{β}) is the least positive residue of i modulo (\overline{α} + \overline{β} = α + β). We have subtracted a total of aj from the pair of sequences. We are left with a pair of sequences generated by

f_{α,β,K}^{+}(j; q) = q^{j[K(α+β)j+K(α−β)]/2} \left[{m + n \atop m + Kj}\right] .

To get a pair of sequences generated by f_{α,β,K}^{−}(j; q), we find the sequences generated by f_{β,α,K}^{+}(j; q) and then interchange the as and bs. This means that we start with the pair of sequences generated by f_{\overline{β},\overline{α},K}^{+}(j; q) and then add aj to them by defining

a_{i} = \overline{a}_{i} + \{ \begin{matrix}1, & if \overline{β} + 1 ≤ (i mod \overline{β} + \overline{α}) ≤ \overline{β} + a \\ & and i ≤ ⌊j/2⌋(\overline{β} + \overline{α}), \\ 0, & otherwise, \end{matrix}  (60)

b_{i} = \overline{b}_{i} + \{ \begin{matrix}1, & if 1 ≤ (i mod \overline{β} + \overline{α}) ≤ a, \\ & and i ≤ ⌈j/2⌉\overline{β} + ⌊j/2⌋\overline{α}, \\ 0, & otherwise. \end{matrix}  (61)

It is not clear to what partitions these pairs of sequences correspond. The sequences generated by f_{α,β,K}^{+}(j; q) satisfy a weakened form of the oscillating condition. If we set i_{r} = ⌈r/2⌉\overline{α} + ⌊r/2⌋\overline{β}, then

a_{i_{r}} − b_{i_{r}−\overline{α}+1} ≥ K − 2\overline{α},  j odd,  (62)
b_{i_{r}} − a_{i_{r}−\overline{β}+1} ≥ K − 2\overline{β},  j even.  (63)

We also introduce additional inequalities:

a_{i_{r}−a} > a_{i_{r}−a+1},  j odd,  (64)
b_{i_{r}−a} > b_{i_{r}−a+1},  j even.  (65)

3.1 A_{m,n}(q): a related partition generating function

If we restrict our attention to the polynomial A_{n}(q) = G(5/3, 4/3, 3; q) given in conjecture 1—see equations (2) and (7)—then we have

K = 3, a = 1, , \overline{α} = 2, \overline{β} = 1.

A family of partitions whose generating function appears to be very closely related to A_{n}(q) consists of those that fit inside an m × n rectangle and satisfy the following conditions for all i such that λ_{i} ≥ i:

either λ_{i} − λ′_{i} ≥ 0  or λ_{i} = λ_{i+1},  (66)
either λ_{i+1} − λ′_{i} ≤ −1 or λ_{i} = λ_{i+1}.  (67)

These two conditions can be combined into

either λ_{i} = λ_{i+1} or λ_{i} ≥ λ′_{i} > λ_{i+1}.  (68)

If we designate the generating function for these partitions by A_{m,n}(q), then we have a simple recursion from which they can be computed:

A_{m,n} = 0, if m < 0 or n < 0,  (69)
A_{m,n} = 1, if mn = 0, m ≥ 0, n ≥ 0  (70)
A_{1,n} = \left[{n + 1 \atop 1}\right] , if n ≥ 0,  (71)
A_{m,n} = A_{m−1,n} + A_{m,n−1} − A_{m−1,n−1}
+ q^{m+n−1} [A_{m−1,n−1} − A_{m−1,n−2} + χ(m ≤ n)A_{m−1,m−2}] ,
if m ≥ 2, n ≥ 1.  (72)

We compare A_{n,n} with A_{n}:

A_{n}(q) − A_{n,n}(q) = 0, n ≤ 4,  (73)
A_{5}(q) − A_{5,5}(q) = q^{11} − q^{12} − q^{13} + q^{14},  (74)
A_{6}(q) − A_{6,6}(q) = q^{11} − q^{13} − q^{15} + q^{17} + q^{19} − q^{21} − q^{23} + q^{25}, (75)
A_{7}(q) − A_{7,7}(q) = q^{11} − q^{15} − q^{16} + q^{19} + q^{20} + 2q^{22} − q^{23} − 2q^{24}

− 2q^{25} − q^{26} + 2q^{27} + q^{29} + q^{30} − q^{33} − q^{34} + q^{38}. (76)

It is easily verified by induction that

A_{m,n}(1) = \{ \begin{matrix}2 × 3^{n−1}, & m = n, \\ 3^{min(m,n)}, & |m − n| = 1. \end{matrix}  (77)

so that in fact

A_{n}(1) = A_{n,n}(1).  (78)

As n increases, the coefficients of A_{n}(q) − A_{n,n}(q) do increase, but remain substantially less than the coefficients of either A_{n}(q) or A_{n,n}(q). Plots of these coefficients for n = 8, 10, 12, 15, and 18 are included in the file borwein.ps. While we do get coefficients on the order of 4000 when n = 18, this is less than 1/500 of the corresponding coefficient in either A_{n}(q) or A_{n,n}(q).

One interesting pattern does emerge. For 5 ≤ n ≤ 17,

P_{n}(q) = \frac{A_{n}(q) − A_{n,n}(q)}{q^{11}(1 − q)(1 − q^{2})}

is a symmetric, unimodal, monic polynomial of degree n^{2} − 25 with strictly positive coefficients. The fact that it is symmetric and monic of degree n^{2} − 25 follows from the fact that both A_{n,n}(q) and A_{n}(q) are symmetric polynomials. There is no apparent reason why it should be unimodal with strictly positive coefficients.

References

[1] George E. Andrews, On a conjecture of Peter Borwein, preprint.

[2] George E. Andrews et al, Partitions with prescribed hook differences, Europ. J. Combinatorics (1987) 8, 341–350.

[3] David M. Bressoud, Extension of the partition sieve, J. Number Theory (1980) 12, 87–100.

[4] David M. Bressoud, Some identities for terminating q series, Math. Proc. Camb. Phil. Soc. (1981) 89, 211–223.

[5] Mourad Ismail and Dennis Stanton, private communication.

Department of Mathematics and Computer Science, Macalester College, Saint Paul, MN 55105, USA