KATHY O’HARA’S CONSTRUCTIVE PROOF OF THE UNIMODALITY OF THE GAUSSIAN POLYNOMIALS

By Doron Zeilberger, Department of Mathematics, Drexel University, Philadelphia, PA19104.

Current Address (1990-): Department of Mathematics, Temple University, Philadelphia, PA19122. zeilberg@math.temple.edu

Appeared in: Amer. Math. Monthly 96 (1989), 590-602.

1.Introduction

Kathy O’Hara[6][7] has recently solved a long-standing open problem in combinatorics: to find a direct combinatorial proof that the ”Gaussian polynomials”

G(b, a) := \frac{(1 − q^{a+b})(1 − q^{a+b−1})...(1 − q^{a+1})}{(1 − q^{b})(1 − q^{b−1})...(1 − q)}  (1)

are unimodal . A polynomial p(q) = c_{0} + c_{1}q + ... + c_{n}q^{n} is unimodal if its coefficients are increasing up to a point and then they are decreasing: i.e. there is an integer r such that c_{0} ≤ c_{1} ≤ ... ≤ c_{r} ≥ c_{r+1} ≥ ...c_{n}. ( The fact that G(b, a) is a polynomial will be shown below .)

For example G(2, 2) = (1 − q^{4})(1 − q^{3})/(1 − q^{2})(1 − q) = 1 + q + 2q^{2} + q^{3} + q^{4}, which is indeed unimodal: 1 ≤ 1 ≤ 2 ≥ 1 ≥ 1.

The best way to learn a topic is by teaching it. Similarly, the best way to understand a new proof is by writing an expository paper about it. This was the original motivation of the present paper. Once written, I thought that it would be nice if all the readers of this Monthly had the opportunity to savor this elegant proof. All the central ideas and constructions are O’Hara’s, but I have made a few minor improvements and shortcuts that I believe to make the argument clearer. I would like to thank Kathy O’Hara for stimulating conversations and correspondence.

The unimodality of the Gaussian polynomials (1) received several ’fancy’ proofs, the first one by Sylvester[13]. The most elementary proof before O’Hara’s was that of Proctor[8] who only used linear algebra. The reader is urged to look up Proctor’s beautiful paper[8] for the history and significance of this problem. I should also mention White’s[15] elegant proof that uses Polya theory.

What does it mean to give a direct combinatorial proof? The coefficients of the Gaussian polynomials G(b,a) have a well known combinatorial interpretation. Namely, the coefficient of q^{k} in G(b,a), let us call it c_{k}(b, a), equals the number of ”partitions of k that have at most a parts and whose largest part is ≤ b ”. In other words, c_{k}(b, a) equals the number of elements in the set

U_{k}(b, a) := {p = (p_{1}, ..., p_{a}); 0 ≤ p_{1} ≤ ... ≤ p_{a} ≤ b, p_{1} + ... + p_{a} = k}.  (2)

For example U_{0}(2, 2)=00, U_{1}(2, 2)=01, U_{2}(2, 2)=11, 02, U_{3}(2, 2)=12, U_{4}(2, 2)=22, whose number of elements are 1, 1, 2, 1, 1 respectively, the same as the coefficients of G(2,2).

The proof of this combinatorial interpretation is as follows ([2],3.2). U_{k}(b, a) can be partitioned into two disjoint subsets: those elements p for which p_{a} ¡b, whose number is equal to the cardinality of U_{k}(b − 1, a), and those elements p for which p_{a} = b, whose number is equal to the cardinality of U_{k−b}(b, a − 1). Thus ( for any finite set A, |A| will denote its number of elements),

|U_{k}(b, a)| = |U_{k}(b − 1, a)| + |U_{k−b}(b, a − 1)|.  (3)

Now, it is readily checked that the Gaussian polynomials (1) satisfy the recurrence

G(b, a) = G(b − 1, a) + q^{b}G(b, a − 1),

which translates to the following recurrence in terms of the coefficients

c_{k}(b, a) = c_{k}(b − 1, a) + c_{k−b}(b, a − 1).  (4)

Since both |U_{k}(b, a)| and c_{k}(b, a) satisfy the same recurrence ( (3) and (4) are identical), and their boundary values match (check!), they are identical.

In particular it follows from this combinatorial interpretation that G(b, a) is indeed a polynomial, and that its degree is ab, since U_{k}(b, a) is certainly empty for k > ab.

It is readily seen that the coefficients of G(b, a) are symmetric with respect to the middle coefficient : c_{k} = c_{ab−k} . This also follows from the obvious bijection

U_{k}(b, a) ↔ U_{ab−k}(b, a),

given by

(p_{1}, ..., p_{a}) ↔ (b − p_{a}, ..., b − p_{1}).

It follows that in order to prove that G(b,a) is unimodal it is enough to show that

|U_{k}(b, a)| ≤ |U_{k+1}(b, a)|  (5)

for every k in the range 0 ≤ k < ab/2.

A direct combinatorial proof of (5) will consist in exhibiting an explicit injection ( one-to-one and into mapping) from U_{k}(b, a) into U_{k+1}(b, a) for 0 ≤ k < ab/2.

2.Posets

We will need some standard definitions and elementary results from the the theory of partially ordered sets (POSETS). All that we will need will be presented here, but the reader who wishes to know more about posets is referred to chapter 2 of Stanton and White’s excellent textbook [12], and to Greene and Kleitman’s well written survey article[4].

A poset (P, ≤) is a set P with an order relation ≤ which has the following properties:

(i) a ≤a for all aϵP , (ii) a≤b and b≤a implies a=b, and (iii) a≤b and b≤c implies a≤c.

If a ≤ b and a ≠ b , we write a < b. We say that b covers a if a < b and there is no c such that a < c < b. We shall write a → b for ”b covers a”. A poset is ranked if each element aϵP can be assigned a non-negative integer, rank(a), so that a → b implies rank(b) = rank(a) + 1. The set L_{i} = {aϵP; rank(a) = i} is called the set of rank i, or a level set.

A good way to visualize a poset P is in terms of its Hasse diagramof the poset and the cover relations are indicated by edges: a → b is denoted by an edge from a to b. By the transitivity of the order relation ( property (iii)) these cover relations completely imply the order relation on P. Figures 1(a) and 1(b) illustrate examples of Hasse diagrams of a ranked and a non-ranked poset respectively.

&&&&&&&&&&&&&&&&&&( figure 1 here)

A finite ranked poset is rank unimodal if the numbers w_{i} = |L_{i}| ( sometimes called the Whitney numbersof the posets) satisfy, for some k: w_{0} ≤ w_{1} ≤ ... ≤ w_{k} ≥ w_{k+1} ≥ .... A poset is rank symmetric if there is an integer m such that w_{i} = 0 for i > m and w_{i} = w_{m−i}. We will call this integer m the rank of P: rank(P) := m.

A maximal symmetric chain in a rank symmetric poset is a sequence of elements (a_{1}, ..., a_{r}), such that a_{1} → a_{2} → ... → a_{r}, and rank(a_{1}) + rank(a_{r}) = rank(P) , (i.e. the middle rank of the chain coincides with the middle rank of the poset .) A maximal symmetric chain decomposition (SCD) of a rank symmetric poset P, is a partition of the set P into a disjoint union of maximal symmetric chains:

P = ∪_{i=1}^{L}C_{i}.

Every chain in an SCD of a rank symmetric poset of rank m must contain exactly one element of the middle rank [ m/2 ]. Thus the number of chains ,L, in an SCD is equal to the cardinality of the middle rank , w_{[m/2]}.

Let us illustrate all these notions in terms of a simple example: B_{3}, the three dimensional Boolean lattice. It consists of the 2^{3} = 8 0-1 vectors with 3 components: 000, 001, 010, 100, 011, 101, 110,

111. The order is defined by (a, b, c) ≤ (a′, b′, c′) if and only if a ≤ a′, b ≤ b′, c ≤ c′. The rank is defined by rank(a,b,c)= a+b+c. The level sets are L_{0}= 000, L_{1}= 001,010,100, L_{2}=011,101,110, and L_{3}=111. Their cardinalities are respectively w_{0}=1, w_{1}=3, w_{2}=3, and w_{3}=1. Thus B_{3} is rank unimodal: 1 ≤ 3 = 3 ≥ 1, and rank symmetric of rank 3 : w_{i} = w_{3−i}. It also has an SCD, consisting of the 3 (= w_{1}) chains: 000 → 001 → 011 → 111, 010 → 110, 100 → 101.

&&&&&&&&&&&&&&&&&&&(figure 2 here )

Every SCD induces an injection L_{k} → L_{k+1}, for k < m/2, given by

p → successor of p in the chain ”to” which p belongs.  (6)

In particular the property of having an SCD implies rank unimodality and , because the chains are symmetric, also rank-symmetry. In fact , it also implies something else. A ranked poset has the Sperner propertyif the maximal size of an antichain ( a set of elements of P that are pairwise unrelated) equals the size of the largest level set, w_{[m/2]}. A poset that possesses an SCD is Sperner.

This follows from the facts that the largest level set is certainly an antichain (as are all level sets ), and every conceivable antichain can have at most one representative from every one of the w_{[m/2]} chains.

3. Young’s Lattice U(b,a)

How does this tie in with the problem of the unimodality of the Gaussian polynomials? It is readily seen that the sets of partitions U_{k}(b, a) introduced at the beginning are the level sets of the poset U(b, a) consisting of all partitions with ≤ a parts and whose parts are ≤ b :

U(b, a) := {p = (p_{1}, ..., p_{a}); 0 ≤ p_{1} ≤ ... ≤ p_{a} ≤ b},

where the rank of an element p in U(b,a) is defined to be the sum of its parts: rank(p) = p_{1}+...+p_{a}. The natural order relation is p ≤ q if and only if p_{i} ≤ q_{i} for i = 1, ..., a. Under this order U(b,a) is called Young’s lattice. The problem of proving the unimodality of the Gaussian polynomials is thus equivalent to showing that the poset U(b,a) is rank-unimodal. Furthermore, an explicit construction of an SCD for U(b,a) would imply, by (6), a constructive proof of this unimodality.

More generally, Given a partition λ, the Young lattice Y_{λ}, corresponding to λ is defined to be the set of all partitions p such that p ≤ λ, with the same definition of ≤ and rank as before. The U(b,a) are the special cases of λ = b^{a} ( b repeated a times). U(b,a) is rank-unimodal, but what about Y_{λ} for general λ ? Of course Y_{λ} is no longer rank symmetric, but it appears to be rank unimodal for small λ. For example for λ = 12, Y_{12}=00, 01, 02, 11 , 12 , and L_{0}= 00, L_{1}=01, L_{2} = 02, 11 , L_{3}= 12. So w_{0}= 1, w_{1}=1, w_{2}=2, and w_{3}=1, and since 1 ≤ 1 ≤ 2 ≥ 1, Y_{12} is rank unimodal.

The same phenomenon turns out to be true for much larger λ, so it was reasonable to conjecture that Y_{λ}, although obviously not rank symmetric, is nevertheless rank unimodal. It came as a great surprise when Dennis Stanton[11] , assisted by computer, found a counterexample: for λ= (4,4,8,8), Y_{λ} is not rank-unimodal. Furthermore, Stanton proved something that no computer can do by itself: he found infinite families of counterexamples, the simplest one being (4, 4, 2k, 2k) for k ≥ 4.

Let us go back to the rank unimodality of U(b,a), which we saw was equivalent to the unimodality of the Gaussian polynomials G(b,a). The rank unimodality itself was first established by Sylvester[13], as a spin-off of a deep theorem in the theory of invariants. But what about a constructive proof, or better still, an explicit construction of an SCD for U(b,a) ? As we saw, such an SCD would imply the Sperner property.

Even the mere existence of an SCD for U(b,a) is still an open problem. However to deduce the Sperner property, as well as rank unimodality, you don’t quite need a symmetric chain decomposition. It is enough to have a maximal chain decomposition all whose chains pass through the largest level setfrom algebraic geometry, proved the existence of such a chain decomposition for the poset U(b,a) as well as for some other posets, among them the posets M(n) of all strict partitions whose largest part is ≤ n:

M(n) := {p = (p_{1}, ..., p_{i}); 0 ≤ i ≤ n, 0 < p_{1} < ... < p_{i} ≤ n},

with the same rank and order relation definitions as for U(b,a).

Stanley’s proofs for U(b,a) and M(n) were subsequently simplified by Proctor[8]. Incidentally, the Spernerity of M(n) , that Stanley discovered almost as an afterthought , trying to apply the ”hard Lefschetz” hammer to as many nails as possible, turned out to be equivalent to a long standing conjecture of Erdos and Moser. Stanley found out about it, quite by accident, from Larry Harper, during a phone call whose original purpose was to discuss a house sublet during a sabbatical leave! ( see Proctor[8] for this fascinating story of serendipity).

However, Both Stanley’s proof and Proctor’s simplifications were non-constructive, existence, proofs. It is still an open problem to find an explicit construction of an SCD for U(b,a), (or even that of a non-symmetric decomposition as above) . To date such a construction is only known when a or b are either 3 or 4 (see Lindstrom[5], West[14], Riess[9]).

In order to get a constructive proof of the unimodality of G(b, a) we would have to define explicit injections U_{k}(b, a) → U_{k+1}(b, a) for k < ba/2. However the existence of an SCD in Young’s lattice U(b,a) would entail that these injections, given by (6), are ”nice”: they map each partition of k not just to an arbitrary partition of k+1, but to one that is covered by itPerhaps this is asking for too much?

It turns out that the problem of constructing not necessarily ”nice” injections can be formulated in terms of an SCD for a modified poset. Just change the order relation! Now that ”everything goes”, we can define a new order:

p < q if and only if rank(p) < rank(q) ,

and an SCD with respect to this new order will still yield explicit injections U_{k} → U_{k+1}.

¿From now on we will forget all about the natural order and will tacitly assume that U(b,a) is equipped with this new, trivial, order.

&&&&&&&&&&&&&&&&&&&&&&( Fig. 3 here )

4. Three Lemmas

We will need three simple lemmas.

LEMMA 1: Let P be a rank-symmetric ranked poset of rank m and let us define P̄ to be the same poset ( i.e. the same set and the same order relation), but with the rank defined by

r̄ank(p) = rank(p) + α,

for some integer α. Then P̄ is a rank-symmetric ranked poset of rank m + 2α.

( We say that P̄ is the shift of P by α.)

PROOF: We have w_{i} = w̄_{α+i}. Thus w_{i} = w_{m−i} implies w̄_{α+i} = w̄_{m−i+α} = w̄_{(m+2α)−(α+i)} .

A mapping π : P → Q between two posets P and Q is a rank preserving, order preserving bijection if:

(i) π is a bijection between P and Q as sets, (ii) rank (π(p))= rank(p), and (iii) if p ≤ p′ then π(p) ≤ π(p′).

LEMMA 2 : Let P and Q be ranked posets. Let π : P → Q be a rank preserving, order preserving bijection from P to Q, then if P has an SCD, so does Q. Furthermore, if we know π explicitly, and the SCD for P is explicit, then the SCD for Q can be constructed explicitly.

PROOF: If P = unionfrom1toLC_{i} is an SCD for P, then Q = unionfrom1toLπ(C_{i}) is an SCD for Q.

If P and Q are posets then their cartesian product (P × Q, ≤) is defined by

P × Q = {(p, q); pϵP, qϵQ},

and the order relation is defined by (p, q) ≤ (p′, q′) if and only if p ≤ p′ and q ≤ q′. If P and Q are ranked, then P × Q is made into a ranked poset by defining the rank by rank(p, q) = rank(p) + rank(q). Of course (p, q) → (p′, q′) if and only if either p → p′ and q = q′ or p = p′ and q → q′.

LEMMA 3 ([3]): If P and Q are rank-symmetric ranked posets, of rank m and m’ respectively, and we know how to construct SCDs for both P and Q, then there is an explicit way to construct an SCD for P timesQ, and P × Q is a ranked, rank-symmetric poset of rank m+m’.

PROOF : Let P = unionfromi = 1toLC_{i} and Q = unionfromj = 1toMD_{j} be the SCDs for P and Q respectively. Then

P × Q = ∪fromi = 1toL ∪ fromj = 1toMC_{i} × D_{j}.

Let C_{i} = p_{1} → ... → p_{r} and D_{j} = q_{1} → ... → q_{s} . We claim that C_{i} × D_{j} can be decomposed into a union of min(r,s) maximal symmetric chains of P × Q. Indeed, the following chains exhaust C_{i} × D_{j}, 1 ≤ l ≤ min(r, s) :

(p_{1}, q_{l}) → ... → (p_{r−l+1}, q_{l}) → (p_{r−l+1}, q_{l+1}) → ... → (p_{r−l+1}, q_{s}).  (7)

These chains are symmetric, ( and the rank of P × Q is m+m’ ) since

rank(p_{1}, q_{l}) + rank(p_{r−l+1}, q_{s}) = rank(p_{1}) + rank(q_{l}) + rank(p_{r−l+1}) + rank(q_{s}) =
rank(p_{1}) + rank(q_{1}) + l − 1 + rank(p_{r}) − (l − 1) + rank(q_{s}) =
(rank(p_{1}) + rank(p_{r})) + (rank(q_{1}) + rank(q_{s})) = m + m′.””

A good way to picture these chains is as follows. Arrange C_{i} × D_{j} in rectangular form:

(p_{1}, q_{1})(p_{2}, q_{1})...(p_{r}, q_{1})
(p_{1}, q_{2})(p_{2}, q_{2})...(p_{r}, q_{2})

…

(p_{1}, q_{s}) (p_{2}, q_{s}) ...(p_{r}, q_{s}) ,

then the chains are obtained by successively ”peeling off” the chain that is obtained by going from left to right along the top row and continuing all the way down the rightmost column.

&&&&&&&&&&&&&&&&&&&&&&&&&( Fig. 4 here)

5. The Art of Constructing Symmetric Chain Decompositions

How does one go about constructing SCDs for a family of posets such as U(b, a)? One approach would be to discover a recursive decomposition that expresses U(b, a) in terms of U(b′, a′) for b′ < b or a′ < a. This by itself is not hard. For example by the proof of the combinatorial interpretation of the Gaussian polynomials G(b, a) given at the beginning , there is a bijection

U(b, a) ↔ U(b − 1, a) ∪ Ũ(b, a − 1),

where Ũ(b, a − 1) is the poset U(b, a − 1) shifted by b.

However this decomposition is useless for our purposes, since neither U(b − 1, a) nor Ũ(b, a − 1) have the same rank (as rank-symmetric posets) as the original poset U(b, a). While U(b, a) has rank ab, U(b − 1, a) has rank a(b − 1) = ab − b, and Ũ(b, a − 1) has rank (a − 1)b + 2b = ab + b . In other words the chains of the first subposets, if they exist, would be ”too high”, while those of the second one would be ”too low”, while we need all the chains to be ”smack in the middle”. It follows that we can only use a decomposition of a poset into smaller subposets if all these smaller subposets are rank-symmetric posets of the same rank asthe original poset.

Another possibility might have been to express U(b,a) as the cartesian product of smaller U(b’,a’). For example, for the Boolean lattice B_{n}, we have B_{n} = {0, 1} × B_{n−1}, and applying lemma 3 recursively gives an SCD for B_{n} ( [3]). This does not seem to be possible for U(b, a). O’Hara’s ingenuity consisted in dividing and conquering: She found a refinement of U(b, a), a certain doubly indexed family of subposets, U(b, a; m, d), that empirically also appeared to be rank-unimodal, rank-symmetric and of the same rank , ab, as U(b,a). She then discoved a ”structure theorem” for these smaller subposets, that expressed each of them in terms of the operations ”union” and ”cartesian product” of posets U(b′, a′; m′, d′) for a′ < a.

It was thus possible to use the three lemmas to recursively construct an SCD for each of these U(b, a; m, d) in terms of those of smaller a. The base cases a = −1, a = 0, anda = 1 being trivial, this showed that each of these U(b, a; m, d) had an SCD, and by taking union over all conceivable m and d, it was possible to construct an SCD for U(b,a) itself. We will now present the details.

6. O’Hara’s Construction

Recall that

U(b, a) := {p = (p_{1}, ..., p_{a}); 0 ≤ p_{1} ≤ ... ≤ p_{a} ≤ b}.

Henceforth, for convenience reason p_{i} = 0 for i ≤ 0 and p_{i} = b for i > a.

Define:

spread(p) := max{p_{i} − p_{i−2}; 2 ≤ i ≤ a + 1}.

M(p) := {2 ≤ i ≤ a + 1; p_{i} − p_{i−2} = spread(p)}.

Partition M(p) into

M(p) = ∪D_{j}

where the D_{j} are maximally connected intervals, and define the degree of p, deg(p), by

deg(p) := ∑_{j}[\frac{|D_{j}| + 1}{2}].

For example for a=13, b=10, and p= 1 2 2 3 4 5 6 6 6 7 8 8 10 , spread(p)=2, M(p)= 2, 5, 6, 7, 11, 13, 14 = 2 union 5, 6, 7 union 11 union 13, 14 ; deg(p)=[(1+1)/2]+ [(3+1)/2]+ [(1+1)/2]+ [(2+1)/2]= 1+2+1+1=5. Note that for p in U(b,a), deg(p) ≤ [(a + 1)/2], m ≤ b. We now define the following subposets:

U(b, a; m, d) := {pϵU(b, a); spread(p) = manddeg(p) = d}.
Ū(b, a; m) = {pϵU(b, a); spread(p) ≤ m}.

We make the reasonable convention that U(b,0) contains a single partition: the ”empty partition”. If a is negative, then U(b,a) is the empty set. We will also make the convention that the cartesian product of the empty poset with a poset P , ϕ × P, is isomorphic to P, and its elements will be denoted by (-,p). Everything would follow from the following theorem. THEOREM:( The O’Hara Structure Theorem) Let a,b,m,d, be positive integers. The mapping σ :

σ : Ū(b − md, a − 2d; m − 1) × U(ma + 2m − 2b, d) → U(b, a; m, d),

to be defined below, is an order preserving bijection such that for every qϵŪ(b − md, a − 2d; m − 1) and rϵU(ma + 2m − 2b, d), we have

rank(σ(q, r)) = rank(q, r) + 2bd − md(d + 1).  (8)

Before defining σ and proving the theorem ( i.e. showing that σ does indeed what it is supposed to do), let us show how the theorem implies an algorithm for constructing an SCD for any U(b,a; m,d) and thus, by taking the union over all feasible m and d, for U(b,a). The cases a = −1 and a = 0 are trivial. U(b, −1) is the empty set. U(b, 0) only contains one element, the empty partition, and thus has an SCD. The case a=1 is not much harder, all the U(b, 1; m, d) are empty except when m = b and d = 1, so U(b, 1) = U(b, 1; b, 1) and there is an SCD consisting of the single chain : 0 → 1 → ... → b.

We can assume , recursively,that we know how to construct an SCD for Ū(b−md, a−2d; m−1), since it is a union of certain U(b′, a′; m′, d′) for a′ = a−2d < a. We can also assume that we know how to construct an SCD for U(ma+2m−2b, d), since d ≤ [(a+1)/2] < a for a > 1. Thus, by lemma 3, we know how to construct an SCD for their cartesian product Ū(b − md, a − 2d; m − 1) × U(ma + 2m − 2b, d) . This poset has rank (b−md)(a−2d)+(ma+2m−2b)d , and when shifted by 2bd−md(d+1), lemma 1 tells us that it has rank (b − md)(a − 2d) + (ma + 2m − 2b)d + 2(2bd − md − md^{2}) = ba. The theorem tells us that σ is a rank preserving , order preserving bijection between this shifted poset and U(b, a; m, d). It follows from lemma 2 that U(b, a; m, d) has an SCD, and that its rank is ab . Since all the U(b, a; m, d) have the same rank as U(b, a), (i.e. ab), an SCD for U(b,a) is obtained by combining all the chains of the SCDs for the constituent U(b,a;m,d).

7. Proof of the O’Hara Structure Theorem

In order to prove the theorem we have to: (i)Define the mapping σ . (ii)Define its alleged inverse π . (iii)Prove that σ is well defined .

(iv)Prove that π is well defined . (v)Prove that the composition σπ is the identity mapping on U(b, a; m, d) . (vi) Prove that the composition πσ is the identity mapping on Ū(b − md, a − 2d; m − 1) × U(ma + 2m − 2b, d) . (vii)Prove that (8) is correct . (viii)Prove that σ is order preserving .

It is easier, pedagogically, to start with the definition of π. So we will perform the eight tasks above in the following order : (ii),(i), (iv), (iii), (v),(vi),(vii),(viii).

(ii) DEFINITION OF π : U(b, a; m, d) → Ū(b − md, a − 2d; m − 1) × U(ma + 2m − 2b, d) .

Let p = (p_{1}, ..., p_{a}) be in U(b, a; m, d). We will define π(p) = (q(p), r(p)) = (q, r).

Let

t + 1 = maxM(p) = max{2 ≤ i ≤ a + 1; p_{i} − p_{i−2} = m},

Define a partition p′ = (p′_{1}, ..., p′_{a−2}) by:

p′_{i} = \{{p_{i,}1 ≤ i ≤ t − 2 \atop p_{i+2} − m, t − 1 ≤ i ≤ a − 2}

[ we will show that p′ϵU(b − m, a − 2; m, d − 1) when d > 1 and p′ϵŪ(b − m, a − 2; m − 1) when d = 1.]

Let,

q(p) := \{{p′, d = 1 \atop q(p′), d > 1[recursively]}

and,

r′ := \{{empty, d = 1 \atop r(p′), d > 1[recursively]}

[ We will show that r′ has d − 1 parts ]. r(p) = r = (r_{1}, ..., r_{d}), is defined by:

r_{i} = \{{p_{t} + p_{t+1} + m(a − t + 1) − 2b, i = 1 \atop r′_{i−1}, 2 ≤ i ≤ d.}

(ii) DEFINITION OF σ ¯: U(b − md, a − 2d; m − 1) × U(ma + 2m − 2b, d) → U(b, a; m, d). Let qϵŪ(b − md, a − 2d; m − 1) and rϵU(ma + 2m − 2b, d), we will have to define σ(q, r) = p, say. Let r′ be the partition with d − 1 parts obtained from r by deleting the first part: r′_{i} = r_{i+1}, for 1 ≤ i ≤ d − 1. [ Obviously r’ belongs to U(ma + 2m − 2b, d − 1)]. Let

p′ := \{{q, d = 1 \atop σ(q, r′), d > 1}.

[ We will show that p′ has a − 2 parts.] We will now define a certain integer t, 1 ≤ t ≤ a. If r_{1}=0, let t=a. Otherwise let t be the [unique] integer that satisfies

p′_{t−1} + p′_{t} − mt < r_{1} − m(a + 2) + 2b ≤ p′_{t−2} + p′_{t−1} − m(t − 1).  (9)

We define p = π(q, r) by

p_{i} = {p′_{i}, 1 ≤ i ≤ t − 1
r_{1} − p′_{t−1} − m(a − t + 2) + 2b, i = t
p′_{i−2} + m, t + 1 ≤ i ≤ a

(iv) PROOF THAT π IS WELL DEFINED p′ is a genuine partition, since p′_{t−1} = p_{t+1} − m = p_{t−1} ≥ p_{t−2} = p′_{t−2}. Here we have used the fact that t + 1ϵM(p) , and thus p_{t+1} − m = p_{t−1}. Now it is readily seen that M(p′) = M(p) − {t + 1} if t does not belong to M(p) and M(p′) = M(p) − {t, t + 1} if t belongs to M(p). In either case deg(p′) = deg(p) − 1 and spread(p′) = m, if d ¿1, and spread(p′) < m if d = 1. So p′ϵU(b − m, a − 2; m, d − 1) if d > 1 and p′ϵŪ(b − m, a − 2; m − 1) if d = 1. If d = 1, q is obviously in Ū(b − md, a − 2d; m − 1), and if d > 1 it belongs, by the inductive hypothesis to Ū(b − m − m(d − 1), a − 2 − 2(d − 1); m − 1)= Ū(b − md, a − 2d; m − 1).

Let t′ + 1 = maxM(p′) . Of course t′ ≤ t − 2 . It remains to show that r is a genuine partition in U(m(a + 2) − 2b, d) . By the inductive hypothesis r′ belongs to U(m(a − 2 + 2) − 2(b − m), d − 1) = U(m(a + 2) − 2b, d − 1) , and to show that r is a bona fide element of U(m(a + 2) − 2b, d) we will have to show that:

when d > 1: 0 ≤ r_{1} ≤ r_{2}, i.e. 0 ≤ r_{1} ≤ r′_{1}, i.e.

0 ≤ p_{t} + p_{t+1} + m(a − t + 1) − 2b ≤ p′_{t′} + p′_{t′+1} + m((a − 2) − t′ + 1) − 2(b − m);  (10)

when d = 1, we have to show r_{1} ≤ m(a + 2) − 2b, i.e.

0 ≤ p_{t} + p_{t+1} + m(a − t + 1) − 2b ≤ m(a + 2) − 2b.  (11)

Making the convention that t′ = −1 when d = 1, (11) becomes encompassed by (10), so it suffices to prove (10), but for d ≥ 1.

The left side of (10) is equivalent to:

(b − m) + b − p_{t} − p_{t+1} ≤ m(a − t),  (10.a)

and the right side of (10) is equivalent to

p_{t} + p_{t+1} − p′_{t′} − p′_{t′+1} ≤ m(t − t′).  (10.b)

Both of these inequalities follow easily from lemma 4 below . (10.a) follows upon taking A = a, B = t, and noting that p_{a+1} = b, and p_{a} ≤ b − m. (10.b) follows upon taking A = t and B = t′, and noting that since t′ ≤ t − 2, p′_{t′} = p_{t′} and p′_{t′+1} = p_{t′+1}.

LEMMA 4 : Let A ≥ B, then

p_{A} + p_{A+1} − p_{B} − p_{B+1} ≤ m(A − B).

PROOF: If A − B is even then

p_{A} + p_{A+1} − p_{B} − p_{B+1} = [p_{A} − p_{B}] + [p_{A+1} − p_{B+1}] = [(p_{A} − p_{A−2}) + ... + (p_{B+2} − p_{B})]+

[(p_{A+1} − p_{A−1}) + ... + (p_{B+3} − p_{B+1})] ≤ m(A − B)/2 + m(A − B)/2 = m(A − B).

Similarly, if A − B is odd:

p_{A} + p_{A+1} − p_{B} − p_{B+1} = [p_{A} − p_{B+1}] + [p_{A+1} − p_{B}] = [(p_{A} − p_{A−2}) + ... + (p_{B+3} − p_{B+1})]+

[(p_{A+1} − p_{A−1}) + ... + (p_{B+2} − p_{B})] ≤ m(A − B − 1)/2 + m(A + 1 − B)/2 = m(A − B) .

(iii) PROOF THAT σ IS WELL DEFINED

Let qϵŪ(b − md, a − 2d; m − 1) and rϵU(m(a + 2) − 2b, d). We will prove that p = σ(q, r) is indeed a partition that belongs to U(b,a;m,d).

Since r′ϵU(m(a + 2) − 2b, d − 1) = U(m(a − 2 + 2) − 2(b − m), d − 1) and qϵŪ(b − md, a − 2d; m − 1) = Ū((b − m) − m(d − 1), (a − 2) − 2(d − 1), m − 1), it follows by the induction hypothesis, for d > 1, that p′ belongs to U(b−m, a−2; m, d−1). If d=1, then of course p′ belongs to Ū(b−m, a−2; m−1).

Now we claim that

p′_{a−1} + p′_{a} − ma ≤ r_{1} − m(a + 2) + 2b ≤ p′_{−1} + p′_{0} − m(1 − 1)

i.e. ( since p′_{−1} = p′_{0} = 0 and p′_{a−1} = p′_{a} = b − m )

2b − m(a + 2) ≤ r_{1} − m(a + 2) + 2b ≤ 0.

This is equivalent to 0 ≤ r_{1} ≤ m(a + 2) − 2b, which is obvious.

Now it is readily seen that the closed (discrete) interval [2b − m(a + 2), 0] can be partitioned as follows into a union of a single point and half open intervals:

[2b − m(a + 2), 0] = {2b − m(a + 2)} ∪ ∪fromt = atot = 1(p′_{t−1} + p′_{t} − mt, p′_{t−2} + p′_{t−1} − m(t − 1)],

So the t that was defined in the definition of σ is well defined. Now let us show that p is a genuine partition. We must show that p_{t} ≥ p_{t−1} and p_{t+1} ≥ p_{t}, both of which follow easily from (9). Furthermore, p_{a} = p′_{a−2} + m ≤ b − m + m = b, so pϵU(b, a). Also t + 1ϵM(p) , while t may or may not be in M(p).

Now since

r_{1} − m(a + 2) + 2b ≤ r_{2} − m(a − 2 + 2) + 2(b − m)

the ” previous t”, let us call it t′, that was obtained in the previous step out of r_{2}, satisfies t′ ≤ t−2 . (if d = 1, then t′ = −1 .) Thus M(p) = M(p′)union{t + 1} or M(p) = M(p′)union{t, t + 1}. (If d=1, M(p’) is empty. ) If d > 1, deg(p)=deg(p’)+1=d-1+1=d. Of course spread(p)=m, and if d = 1, deg(p) = 1, since M(p) consists of either t or t t+1 , so in either case pϵU(b, a; m, d).

(vi) PROOF THAT πσ IS THE IDENTITY

Let p = σ(q, r). We have to show that π(p) = (q, r). We have just seen that M(p) = M(p′)union t or M(p) = M(p′)union{t, t + 1}. In either case t + 1 = maxM(p), so the ” t obtained in doing π(p)”, is the same as ” the t obtained in doing σ(q, r)”. By the inductive hypothesis, if p′ = σ(q, r′), then π(p′) = (q, r′).

Finally, ” the r_{1} obtained from π(p)” is p_{t} + p_{t+1} + m(a − t + 1) − 2b = r_{1} − p′_{t−1} − m(a − t + 2) + 2b + p′_{t−1} + m + m(a − t + 1) − 2b = r_{1,}

as it should.

(v) PROOF THAT σπ IS THE IDENTITY Let (q, r) = π(p), we have to show that σ(q, r) = p. We have that p_{t} + p_{t+1} = r_{1} − m(a − t + 1) + 2b. But p_{t+1} = p_{t−1} + m, since t + 1ϵM(p). So p_{t} = r_{1} − m(a − t + 2) + 2b − p_{t−1}. Now t may or may not be in M(p), thus p_{t} − p_{t−2} ≤ m, which yields the right side of (9), and t + 2 does not belong to M(p), so p_{t+2} − p_{t} < m, which yields the left side of (9). Thus the ”t obtained in doing σ(π(p))” is the same as the ”t obtained in doing π(p). The rest follows from the inductive hypothesis. (vii) Proof That

rankσ(q, r) = rank(q, r) + 2bd − md − md^{2}.  (8)

We have

rankσ(q, r) = rank(p) = p_{1} + ... + p_{a} = p′_{1} + ... + p′_{t−1}+

(r_{1} − p′_{t−1} − m(a − t + 2) + 2b) + (p′_{t−1} + m) + ... + (p′_{a−2} + m) = rank(p′) + r_{1} + 2(b − m).

If d = 1, p′ = q and r = r_{1}, so

rankσ(q, r) = rank(q) + rank(r) + 2(b − m),

which agrees with (8) when d = 1. When d > 1, using the inductive hypothesis gives:

ranksigma(q, r) = ranksigma(q, r′) + r_{1} + 2(b − m) =
rank(q) + rank(r′) + 2(b − m)(d − 1) − m(d − 1)d + r_{1} + 2(b − m) =
rank(q) + rank(r) + 2bd − md(d + 1) = rank(q, r) + 2bd − md(d + 1).””

(viii) PROOF THAT σ IS ORDER PRESERVING Immediate from (vii). (Recall that the order we took on U(b,a) is the trivial one in which p < q if and only if rank(p) < rank(q).)

8. Examples (i)Example of π : U(5, 5; 2, 2) → Ū(1, 1; 1) × U(4, 2) .

Let a = 5, b = 5, m = 2 and d = 2, p = 12244. Here t = 4, and r_{1} = 4 + 4 + 2(5 − 4 + 1) − 2(5) = 2 ; p’=122. Now a = 3, b = 3, t = 1, and ”r_{1}”= r_{2} = 1 + 2 + 2(3 − 1 + 1) − 2(3) = 3; p′′=( ”current p′”)=0. So q = 0ϵŪ(1, 1; 1) and r = 23ϵU(4, 2). Summing up: π(12244) = (0, 23).

(ii) Example of σ : Ū(1, 1; 1) × U(4, 2) → U(5, 5; 2, 2) .

Let us try and find σ(0, 23), and see if we get the input of (i) back.

We have q = 0, r = 23. We start with a = 3, b = 3 , d = 1, m = 2. 2b − m(a + 2) = −4. The intervals (p′_{t−1} + p′_{t} − mt, p′_{t−2} + p′_{t−1} − m(t − 1)], for t = 1 is (−3, 0], and since r_{1} − m(a + 2) + 2b= 3 − 2(3 + 2) + 2(3) = −1, and −1 falls in (-3,0], t = 1. p_{1} = 3 − 0 − 2(3 − 1 + 2) + 2(3) = 1 ; p_{2} = 2, and p_{3} = p′_{1} + 2 = 2. So the output from the first stage was p = 122, which is the ”current p′” of the second stage. Now a = 5, b = 5, m = 2,and r_{1} = 2, 2b − m(a + 2) = 2(5) − 2(5 + 2) = −4. The intervals (p′_{t−1} + p′_{t} − mt, p′_{t−2} + p′_{t−1} − m(t − 1)], for t = 5, 4, 3, 2, 1 are respectively: (−4, 3], (−3, −2], (−2, −1], (−1, −1], and(−1, 0]. r_{1} − m(a + 2) + 2b = 2 − 4 = −2 falls in the interval (−3, −2], so t = 4. p_{1} = 1, p_{2} = 2, p_{3=2} , and p_{4} = 2 − 2 − 2(5 − 4 + 2) + 2(5) = 4, p_{5} = p′_{3} + m = 2 + 2 = 4. So σ(0, 23) = 12244.

(iii) The O’Hara SCD for U(4,3)

We have:

U(4, 3) = U(4, 3; 4, 1) ∪ U(4, 3; 3, 1) ∪ U(4, 3; 2, 2)

(a)U(4,3;4,1)

U(4, 3; 4, 1) ≡ Ū(0, 1; 3) × U(12, 1) = U(0, 1) × U(12, 1) = 0×0 → 1 → 2 → ... → 12. Ū(0, 1; 3) × U(12, 1) consists of the single chain (0, 0) → (0, 1) → ...(0, 12). Applying σ to it yields the SCD for U(4, 3; 4, 1) consisting of the single chain: 000 → 001 → 002 → 003 → 004 → 014 → 024 → 034 → 044 → 144 → 244 → 344 → 444.

(b) U(4,3;3,1)

U(4, 3; 3, 1) ≡ Ū(1, 1; 2) × U(7, 1) = U(1, 1) × U(7, 1) = 0 → 1 × 0 → 1 → ... → 7 .

Applying the procedure of Lemma 3, we get the following SCD for Ū(1, 1; 2) × U(7, 1) consisting of the two chains:

(0, 0) → (1, 0) → (1, 1) → (1, 2) → (1, 3) → (1, 4) → (1, 5) → (1, 6) → (1, 7),

and

(0, 1) → (0, 2) → (0, 3) → (0, 4) → (0, 5) → (0, 6) → (0, 7).

Applying σ yields the following SCD for U(4, 3; 3, 1):

011 → 111 → 112 → 113 → 114 → 124 → 134 → 234 → 334
012 → 013 → 023 → 033 → 133 → 233 → 333.

(c)U(4,3;2,2)

U(4, 3; 2, 2) ≡ Ū(0, −1; 1) × U(2, 2) = ϕ × U(2, 2) ≡ U(2, 2) .

An SCD for U(2,2) can be obtained recursively from the O’Hara construction, or better still, by inspection:

00 → 01 → 02 → 12 → 22,
11.

Applying σ yields the following SCD for U(4,3;2,2):

022 → 122 → 222 → 223 → 224,
123.

Combining (a),(b), and (c) , we get that the O’Hara algorithm produces the following SCD for U(4,3):

000 → 001 → 002 → 003 → 004 → 014 → 024 → 034 → 044 → 144 → 244 → 344 → 444
011 → 111 → 112 → 113 → 114 → 124 → 134 → 234 → 334
012 → 013 → 023 → 033 → 133 → 233 → 333
022 → 122 → 222 → 223 → 224

123

9. Prospects

I am sure that O’Hara’s breakthrough will lead to further work in this area. It would be nice to find another decomposition of U(b,a) in which the analog of σ would be also order preserving with respect to the natural, Young’s lattice, order. It would also be interesting to find an O’Hara-style constructive proof of Stanley’s[10] result that the posets M(n) are rank-unimodal. This fact is equivalent to the unimodality of the polynomial (1 + t)(1 + t^{2})...(1 + t^{n}).

More generally, Almkvist[1] conjectured that the polynomials

∏_{v=1}^{n} \frac{1 − t^{rv}}{1 − t^{v}}

are unimodal when r is even and r ≥ 1 and when r is odd and n ≥ 11. Almkvist[1] developed an intersting analytical method that is capable, at least in principle, of proving this conjecture for every specific r. Assisted by computer, he proved his conjecture for 3 ≤ r ≤ 20 and r = 100, 101. The conjecture is still open for general r. This is equivalent to the rank-unimodality of the poset of partitions in which each part can appear at most r − 1 times, and whose largest parts are ≤ n. An O’Hara-style proof would be particularly gratifying since it would demonstrate that combinatorics is also capable of proving new results. REFERENCES 1.Almkvist, Gert, Proof of a conjecture about unimodal polynomials, preprint. [ Almkvist’s address is : PL 500, S24300 Hoor, Sweden]. 2.Andrews, George, ”The Theory of Partitions”, Addison-Wesley, Reading, Mass., 1976. 3.deBruijn,N.,Tenbergen,C. van E ., and Kruyswijk,D., On the set of divisors of a number, Nieuw Arch. Wisk.(2)23 (1952), 191-193. 4.Greene, Curtis, and Kleitman, Daniel, Proof techniques in the theory of finite sets, in ”Studies in Combinatorics”, ed. by G.-C.Rota, Mathematical Association of America,1978, 22-79. 5.Lindstrom,B., A partition of L(3,n) into saturated chains, Europ. J. Comb. 1 (1980), 61-63. 6.O’Hara, Kathleen M., Unimodality of Gaussian coefficients: a constructive proof, research announcement, preprint, University of Iowa. 7.O’Hara, Kathleen M., Unimodality of Gaussian coefficients: a constructive proof, preprint, University of Iowa. 8.Proctor, Robert, Solution of two difficult combinatorial problems with linear algebra, Amer. Math. Monthly 89 (1982), 721-734. 9.Riess,W., Zwei Optimierungprobleme auf Ordnungen, Arbeitsberichte des Instituts fur mathematische Maschinen und Datenverarbeitungen 11 (1978), no. 5, Erlangen. 10.Stanley, Richard P., Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic and Discrete Methods, 1 (1980), 164-184. 11.Stanton, Dennis, Unimodality and Young’s lattice, preprint, University of Minnesota. 12.Stanton, Dennis, and White, Dennis, ”Constructive Combinatorics”, Springer-Verlag, New York, 1986. 13.Sylvester, James J., Proof of the hitherto undemonstrated fundamental theorem of invariants, ”Collected Math. Papers”, vol. 3, Chelsea, New York, 1973, 117-126. 14.West, Dougless B., A symmetric chain decomposition of L(4,n), Europ. J. Comb. 1 (1980), 379-383. 15.White, Dennis E., Monotonicity and unimodality of the pattern inventory, Advances in Math. 38 (1980), 101-108. January 1988.