ON BERGERON’S POSITIVITY PROBLEM
FOR q-BINOMIAL COEFFICIENTS

arXiv:1709.06187v1 [math.CO] 18 Sep 2017

FABRIZIO ZANELLO


a+d
Abstract. F. Bergeron recently asked the intriguing question whether b+c
b q−
d q has
nonnegative coefficients as a polynomial in q, whenever a, b, c, d are positive integers, a is the
smallest, and ad = bc. We conjecture that, in fact, this polynomial is also always unimodal,
and combinatorially show our conjecture for a ≤ 3 and any b, c ≥ 4. The main ingredient
will be a novel (and rather technical) application of Zeilberger’s KOH theorem.

1. Introduction
An interesting problem recently posed by F. Bergeron [1], which naturally arose in his
studies of the q-Foulkes conjecture, is whether the coefficients of the symmetric polynomial


b+c
a+d
−
always form a nonnegative sequence, for any choice of positive integers a, b, c, d
b q
d q

where a is the smallest and ad = bc. Here, m+n
as usual denotes the q-binomial coefficient
m q

(1 − q)(1 − q 2 ) · · · (1 − q m+n )
.
(1 − q)(1 − q 2 ) · · · (1 − q m ) · (1 − q)(1 − q 2 ) · · · (1 − q n )

It is easily seen that m+n
is a symmetric polynomial in q of degree mn.
m q
In this note, we conjecture the following stronger fact, and provide a combinatorial proof
of our conjecture for a ≤ 3 and any b, c ≥ 4. Recall that a sequence of numbers is unimodal
if it does not increase strictly after a strict decrease.
Conjecture 1.1. Fix any positive integers a, b, c, d such that a is the smallest and ad = bc.
Then the coefficients of the symmetric polynomial




a+d
b+c
−
d
b
q
q
are nonnegative and unimodal.



Notice that symmetry is clear, since both b+c
and a+d
are symmetric polynomials of
b q
d q
the same degree, bc = ad. Also note that the case a = 1 of the conjecture is trivial, thanks

to the unimodality of b+c
(see e.g. [3, 5, 7, 10, 13]). In this note, first we apply a recent
b q
result of Pak-Panova [4], that we reproved combinatorially in [12], to provide a short proof
of Conjecture 1.1 when a = 2, for any values of b and c. Then, we employ Zeilberger’s KOH
theorem [13] to settle the case a = 3.
2010 Mathematics Subject Classification. Primary: 05A15; Secondary: 05A17, 05A20.
Key words and phrases. q-binomial coefficient; unimodality; positivity; KOH theorem.
1

2

F. ZANELLO

Unimodality results for suitable differences of two q-binomial coefficients have also appeared, for instance, in the work of Reiner and Stanton ([6], Theorems 1 and 5), who employed interesting methods of representation theory in their proofs. See also their Conjecture
9 (or [9], Conjecture 7), which provides a broad family of possible further identities, and is
still wide open to this day. It would be interesting to investigate whether our combinatorial
approach via the KOH theorem, which appears to be new in this context, might also help
with the Reiner-Stanton conjecture.
2. Proof of the conjecture for a ≤ 3
We begin with a proof of Conjecture 1.1 for a = 2. Notice that even this “simplest” case,
which we are now able to show rather easily, heavily relies on the strict unimodality of a


q-binomial coefficient b+c
(i.e., b+c
is unimodal and its coefficients are strictly increasing
b q
b q
through degree ⌊bc/2⌋, except from degree 0 to 1). This fact was established only recently.

is strictly unimodal if and only if
Lemma 2.1 ([4, 12]). Assume c ≥ b ≥ 2. Then b+c
b q
b = c = 2 or b ≥ 5, with the following nine exceptions:
(b, c) = (5, 6), (5, 10), (5, 14), (6, 6), (6, 7), (6, 9), (6, 11), (6, 13), (7, 10).
Proposition 2.2. Conjecture 1.1 is true when a = 2.
Proof. Let



X
d+2
=
ai q i
2
q
0≤i≤2d



X
b+c
=
bi q i ,
and
b
q
0≤i≤bc

where we can assume that c ≥ b ≥ 3. Proving the result is tantamount to showing that
bi − bi−1 ≥ ai − ai−1 , for all i ≤ d = bc/2.
It is easy to see directly that, for i ≤ d, ai = ⌈(i + 1)/2⌉. Hence, ai − ai−1 = 1 if i is even,

and ai − ai−1 = 0 if i is odd. Thus, it suffices to show that b+c
is strictly increasing in all
b q
even degrees up to bc/2.
If b ≥ 5, the result follows from Lemma 2.1, since one can easily verify computationally
that all nine exceptional q-binomial coefficients of the lemma satisfy the inequality bi−1 < bi
when i ≤ bc/2 is even.
If b ≤ 4, the conclusion can be obtained in a few different ways. For a combinatorial proof,
one can rely on the fact that in a symmetric chain decomposition of the poset L(b, c), for
b = 3, 4 (we can assume c even when b = 3), at least one new chain is introduced in every
even degree ≤ bc/2 (see [2, 11]). When b = 4, notice that the result also immediately follows

from [8], Lemma 2.1 (b).
Before proving Conjecture 1.1 for a = 3, we recall Zeilberger’s KOH theorem [13]. It
rephrases, in algebraic terms, O’Hara’s celebrated combinatorial proof of the unimodality of
q-binomial coefficients [3], by decomposing these latter into suitable finite sums of unimodal,
symmetric polynomials with nonnegative coefficients.

ON BERGERON’S POSITIVITY PROBLEM FOR q-BINOMIAL COEFFICIENTS

3

Fix positive integers m and n, and for any partition λ = (λ1 , λ2 , . . . ) ⊢ m, set Yi =
P
1≤j≤i λj for i ≥ 1, and Y0 = 0.

P
Lemma 2.3 ([13]). We have m+n
= λ⊢m Fλ (q), where
m q
Y j(n + 2) − Yj−1 − Yj+1
P
2 i≥1 (λ2i )
.
Fλ (q) = q
λ
−
λ
j
j+1
q
j≥1
Theorem 2.4. Conjecture 1.1 is true when a = 3.
Proof. Let



X
d+3
ai q i
=
3
q
0≤i≤3d



X
b+c
bi q i ,
=
and
b
q
0≤i≤bc

where b, c ≥ 4. We can assume that b ≡ 0 (mod 3). With some abuse of notation, define
the first difference of a q-binomial coefficient as its truncation in the middle degree; i.e., we


P
denote by (1−q) d+3
the polynomial 1+ 1≤i≤3d/2 (ai −ai−1 )q i , and similarly, (1−q) b+c
=
3
b
q
q
P
i
1 + 1≤i≤bc/2 (bi − bi−1 )q .
Thus, showing the result is equivalent to proving that




b+c
d+3
,
≤ (1 − q)
(1 − q)
b
3
q
q
P
P i
where inequalities between polynomials are defined degreewise (i.e., by
αi q i ≤
βi q we
mean αi ≤ βi for all i).

By Lemma 2.3, we can decompose d+3
as
d q









3d + 1
2d − 1
d+3
2 d−1
6 d−1
,
+
+q
=q
1
1
1
3
3
q
q
q
q
q
where the first term on the right side corresponds to the partition (3) of 3, the second to
(2, 1), and the third to (1, 1, 1).
By iterating Lemma 2.3 a total of b/3 times on the right side, standard computations give

us that d+3
equals:
3 q







X
2d − 8i − 1
6i 3d − 12i + 1
6i+2 d − 4i − 1
2b d − 4b/3 + 3
.
+q
q
+
(1) q
1
1
1
3
q
q
q
q
b−3
0≤i≤

3

If we now consider the partition (3, 3, . . . , 3) of b, we see that its contribution to the KOH

decomposition of b+c
, by Lemma 2.3, is given by:
b q




3
b
d
−
4b/3
+
3
(c
+
2)b/3
−
(b
−
3)
−
b
·2·
2b
)
(
,
=q
q3 2
3
3
q
q
which is precisely the first summand in (1).

4

F. ZANELLO

Thus, by (1), we want to show that
(2) 






X
X
3d − 12i + 1 
2d − 8i − 1
d − 4i − 1
(1−q) 
≤ (1−q)
Fλ (q),
+ q 6i
q 6i+2
1
1
1
q
q
q
b−3
0≤i≤

3


where the sum on the right is as in the KOH decomposition of b+c
, and is indexed over
b q
all partitions λ ⊢ b, λ 6= (3, 3, . . . , 3).
We have:







X
3d − 12i + 1 
2d − 8i − 1
d − 4i − 1
(1 − q) 
+ q 6i
q 6i+2
1
1
1
q
q
q
b−3
0≤i≤

=

X

3

(1 − q)q 6i+2 (1 + q + · · · + q d−4i−2 ) ·

0≤i≤ b−3
3

=

X

1 − q 3d−12i+1
1 − q 2d−8i−1
+ (1 − q)q 6i ·
1−q
1−q

(1 + q + · · · + q d−4i−2 )(q 6i+2 − q 2d−2i+1 ) + (q 6i − q 3d−6i+1 ).

0≤i≤ b−3
3

Note that both 2d − 2i + 1 and 3d − 6i + 1 are larger than bc/2 = 3d/2 for all of our indices
i, since c ≥ 4. Thus, since the first difference is defined to be up to degree bc/2 = 3d/2, the
last displayed formula becomes:
X
(q 6i + q 6i+2 + q 6i+3 + · · · + q d+2i ).
(3)
0≤i≤ b−3
3

It is the polynomial in (3) that we will bound with the first difference of suitable families

of terms appearing in the KOH decomposition of b+c
. We begin by dominating
b q
X
(q 6i+2 + q 6i+3 + · · · + q d+2i ).
1≤i≤ b−3
3

Hence, for now, we are not concerned with (q 2 + q 3 + · · · + q d ) +
Consider the following partitions of b:

P

0≤i≤ b−3
3

q 6i .

i,j
i,j
i,j
i,j
i,j
λi,j = (λi,j
1 = 3, . . . , λi = 3, λi+1 = 2, . . . , λi+j = 2, λi+j+1 = 1, . . . , λb−2i−j = 1),

for any indices
1 ≤ i ≤ (b − 3)/3 and 1 ≤ j ≤ ⌊b/2 − 2i(c − 1)/c⌋.
Since b ≥ 6 (because b ≡ 0 (mod 3)) and
b/2 − 2i(c − 1)/c ≤ (b − 3i)/2
for c ≥ 4, all partitions λi,j contain at least one part of each size 1, 2, and 3.

ON BERGERON’S POSITIVITY PROBLEM FOR q-BINOMIAL COEFFICIENTS

We want to show that
X
(1 − q)Fλi,j (q) ≥
i,j

X

5

(q 6i+2 + q 6i+3 + · · · + q d+2i ).

1≤i≤ b−3
3

Employing Lemma 2.3, the contribution of λi,j to the KOH decomposition of

b+c
b q



is

Fλi,j (q) =




(c + 2)(b − 2i − j) − 2b + 1
(c + 2)(i + j) − 6i − 4j + 1
6i+2j (c + 2)i − 6i + 1
q
1
1
1
q
q
q




bc − 2ci − 4i − cj − 2j + 1
ci − 4i + cj − 2j + 1
ci − 4i + 1
.
= q 6i+2j
1
1
1
q
q
q
For all i and j as above, we have
(6i + 2j) + (bc − 2ci − 4i − cj − 2j + 1) = bc − 2ci + 2i − cj + 1 > bc/2.
Therefore,



q 6i+2j − q bc−2ci+2i−cj+1
ci − 4i + cj − 2j + 1
ci − 4i + 1
·
(1 − q)Fλi,j (q) = (1 − q)
1
1
1−q
q
q



ci − 4i + cj − 2j + 1
6i+2j ci − 4i + 1
=q
1
1
q
q
= (1 + q + · · · + q ci−4i )(q 6i+2j + q 6i+2j+1 + · · · + q ci+2i+cj ).
Thus, our goal is to show that
X
(4)
(1 + q + · · · + q ci−4i )(q 6i+2j + · · · + q ci+2i+cj ) ≥
i,j

X

(q 6i+2 + · · · + q d+2i ).

1≤i≤ b−3
3

We first consider the case c = 4. For any given index i = 1, . . . , (b − 3)/3, the contribution
of i to the left side of (4), which is given by
X
(q 6i+2j + · · · + q 6i+4j ),
j

clearly dominates the contribution of i to the right side, since the largest degree that appears
on the left side is
6i + 4⌊b/2 − 3i/2⌋ ≥ d + 2i = (4b/3) + 2i.
Also notice the following fact, which will be useful later on: When b > 6 is even, the
coefficient of degree 2b − 6 on the left side of (4), say l2b−6 , is strictly greater than the
corresponding coefficient on the right side, say r2b−6 . Indeed, a standard computation shows
that r2b−6 = 2. As for l2b−6 , one can see that it is at least 4, by considering the contribution,
to the degree 2b − 6 coefficient on the left side of (4), of the following four pairs of indices
(i, j):
((b − 6)/3, 2), ((b − 6)/3, 3), ((b − 9)/3, 3), ((b − 9)/3, 4).

6

F. ZANELLO

This completes the proof that
(5)

l2b−6 > r2b−6 .

Now let c > 4. We consider the two sets of indices
1 ≤ i ≤ ⌊b/6⌋ and ⌊b/6⌋ + 1 ≤ i ≤ (b − 3)/3
separately. When i ≤ ⌊b/6⌋, we have that
X
1 · (q 6i+2j + · · · + q ci+2i+cj ) ≥ (q 6i+2 + · · · + q d+2i ),
j

since
ci + 2i + c⌊b/2 − 2i(c − 1)/c⌋ ≥ d + 2i
for any i ≤ ⌊b/6⌋.
Fix now an index i, ⌊b/6⌋ + 1 ≤ i ≤ (b − 3)/3. We want to bound the sum contributed
by i to the right side of (4) with the sum contributed by i − ⌊b/6⌋ to the left side, of course
without employing terms already used for i ≤ ⌊b/6⌋.
A quick thought tells us that we are done whenever the following inequality is true:
X
(6)
(q + · · · + q (c−4)(i−⌊b/6⌋) )(q 6(i−⌊b/6⌋)+2j + · · · + q (c+2)(i−⌊b/6⌋)+cj ) ≥ (q 6i+2 + · · · + q d+2i ).
j

Clearly, (6) is verified if we show that for each i = ⌊b/6⌋ + 1, . . . , (b − 3)/3, the left
side begins in degree no larger, and ends in degree no smaller, than the right side. Since
j ≤ ⌊b/2 − 2i(c − 1)/c⌋, standard computations give us that this is indeed the case for any
c ≥ 5, if we assume b ≥ 18 when c = 5 (the theorem is immediate to check directly for b < 18
when c = 5). This shows (4).
In order to complete the proof of the theorem, it remains to bound
X
(q 2 + q 3 + · · · + q d ) +
q 6i ,
1≤i≤ b−3
3


using the KOH contribution to b+c
provided by some new family of partitions of b.
b q
We consider the following partitions:
µi = (µi1 = 2, . . . , µii = 2, µii+1 = 1, . . . , µib−i = 1),
where 1 ≤ i ≤ ⌈b/2⌉ − 1. By Lemma 2.3, the KOH contribution of µi to b+c
b



(c + 2)(b − i) − 2b + 1
(c + 2)i − 4i + 1
Fµi (q) = q 2i
1
1
q
q



bc − ci − 2i + 1
ci − 2i + 1
.
= q 2i
1
1
q
q
We have
2i + (bc − ci − 2i + 1) = bc − ci + 1 > bc/2,



q

is:

ON BERGERON’S POSITIVITY PROBLEM FOR q-BINOMIAL COEFFICIENTS

7

for all 1 ≤ i ≤ ⌈b/2⌉ − 1 and all c. Thus,
(1 − q)Fµi (q) = (1 − q)q 2i (1 + q + · · · + q ci−2i ) ·

1 − q bc−ci−2i+1
1−q

= (1 + q + · · · + q ci−2i )(q 2i − q bc−ci+1 ) = q 2i + q 2i+1 + · · · + q ci .
Since c(⌈b/2⌉ − 1) ≥ d = bc/3 for any c ≥ 4, it follows that
X
X
(1 − q)Fµi (q) =
q 2i + q 2i+1 + · · · + q ci ≥ q 2 + q 3 + · · · + q d .
1≤i≤⌈b/2⌉−1

1≤i≤⌈b/2⌉−1

We now want to check when
(7)

X

q 2i + q 2i+1 + · · · + q ci

1≤i≤⌈b/2⌉−1

P
also simultaneously dominates
q 6i ; that is, when in (7) the coefficients in each
1≤i≤ b−3
3
degree 6, 12, . . . , 2b − 6 are at least 2.
Notice that every even power of q that appears in (7) for a given index i < (b − 3)/3 also
appears for i + 1, with the only exception of q 2i . This, however, appears for i − 1 if i ≥ 2,
so the total number of times it is present in (7) is again at least 2. We conclude that a
coefficient equal to 1 in some degree n ≡ 0 (mod 6), if it exists, can only be contributed by
i = (b − 3)/3, and such a degree n must be in the range:
c(⌈b/2⌉ − 2) + 1 ≤ n ≤ c(⌈b/2⌉ − 1).
It follows that the theorem is proven whenever c(⌈b/2⌉−2)+1 > 2b−6. This is immediately
verified to be the case for any c ≥ 6. When c = 5, the only exception is b = n = 6, but for
b = 6 the theorem can easily be checked directly. Finally, when c = 4, the only exceptions
are b even and n = 2b − 6. If b = 6 the theorem is again verified directly; if b > 6, we employ

inequality (5). The proof of the theorem is complete.
3. Acknowledgements
I am indebted to Richard Stanley for informing me of Bergeron’s positivity problem,
and for several helpful discussions during his visit to Michigan Tech in October 2016. In
particular, it was during one of those discussions that we came up with the unimodality
Conjecture 1.1. A final version of this note was drafted during a visiting professorship at
MIT in Fall 2017, for which I am (once again) grateful to Richard. This work was done while
I was partially supported by a Simons Foundation grant (#274577).
References
[1] F. Bergeron: The q-Foulkes Conjecture, Talk delivered at Bowdoin College, ME, on September 24, 2016.
Slides available at this link.
[2] B. Lindström: A partition of L(3, n) into saturated symmetric chains, European J. Combin. 1 (1980),
61–63.

8

F. ZANELLO

[3] K. O’Hara: Unimodality of Gaussian coefficients: a constructive proof, J. Combin. Theory Ser. A 53
(1990), 29–52.
[4] I. Pak and G. Panova: Strict unimodality of q-binomial coefficients, C. R. Math. Acad. Sci. Paris 351
(2013), no. 11-12, 415–418. See also a corrigendum at this link.
[5] R. Proctor: Solution of two difficult combinatorial problems using linear algebra, Amer. Math. Monthly
89 (1982), no. 10, 721–734.
[6] V. Reiner and D. Stanton: Unimodality of differences of specialized Schur functions, J. Algebraic Combin. 7 (1998), 91–107.
[7] R.P. Stanley: Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic
Discrete Methods 1 (1980), no. 2, 168–184.
[8] R.P. Stanley and F. Zanello: Unimodality of partitions with distinct parts inside Ferrers shapes, European J. Combin. 49 (2015), 194–202.
[9] D. Stanton: Open positivity conjectures for integer partitions, Trends Math. 2 (1999), 19–25. Available
at this link.
[10] J.J. Sylvester: Proof of the hitherto undemonstrated fundamental theorem of invariants, Collect. Math.
papers, Vol. 3, Chelsea, New York (1973), 117–126.
[11] D. West: A symmetric chain decomposition of L(4, n), European J. Combin. 1 (1980), 379–383. See
also Stanford University report STAN-CS-79-763 (1979), 15 pp..
[12] F. Zanello: Zeilberger’s KOH theorem and the strict unimodality of q-binomial coefficients, Proc. Amer.
Math. Soc. 143 (2015), no. 7, 2795–2799.
[13] D. Zeilberger: Kathy O’Hara’s constructive proof of the unimodality of the Gaussian polynomials, Amer.
Math. Monthly 96 (1989), no. 7, 590–602.
Department of Mathematics, MIT, Cambridge, MA 02139; and Department of Mathematical Sciences, Michigan Tech, Houghton, MI 49931
E-mail address: zanello@mit.edu

