A Proof of George Andrews’ and Dave Robbins’ q-TSPP Conjecture

(modulo a finite amount of routine calculations) ^{1}

By Manuel KAUERS, Christoph KOUTSCHAN, and Doron ZEILBERGER

Pour Pierre Leroux, In Memoriam

Preface: Montréal, May 1985

In the historic conference Combinatoire Énumérative [LL] wonderfully organized by Gilbert Labelle and Pierre Leroux there were many stimulating lectures, including a very interesting one by Pierre Leroux himself, who talked about his joint work with Xavier Viennot [LV], on solving differential equations combinatorially! During the problem session of that very same colloque, chaired by Pierre Leroux, Richard Stanley raised some intriguing problems about the enumeration of plane partitions, that he later expanded into a fascinating article [Sta1]. Most of these problems concerned the enumeration of symmetry classes of plane partitions, that were discussed in more detail in another article of Stanley [Sta2]. All of the conjectures in the latter article have since been proved (see Dave Bressoud’s modern classic [B]), except one, that, so far, resisted the efforts of the greatest minds in enumerative combinatorics. It concerns the proof of an explicit formula for the q-enumeration of totally symmetric plane partitions, conjectured independently by George Andrews and Dave Robbins ([Sta2], [Sta1] (conj. 7), [B] (conj. 13)). In this tribute to Pierre Leroux, we describe how to prove that last stronghold.

q-TSPP: The Last Surviving Conjecture About Plane Partitions

Recall that a plane partition π is an array π = (π_{ij}), i, j ≥ 1, of positive integers π_{ij} with finite sum |π| = ∑ π_{ij}, which is weakly decreasing in rows and columns. By stacking π_{ij} unit cubes on top of the ij location, one gets the 3D Ferrers diagram, that can be identified with the plane-partition, and is a left-, up-, and bottom- justified structure of unit cubes, and we can refer to the locations (i, j, k) of the individual unit cubes.

A plane partition is totally symmetric iff whenever (i, j, k) is occupied (i.e. π_{ij} ≥ k), it follows that all its (up to 5) permutations: {(i, k, j), (j, i, k), (j, k, i), (k, i, j), (k, j, i)} are also occupied. In 1995, John Stembridge [Ste] proved Ian Macdonald’s conjecture that the number of totally symmetric plane partitions (TSPPs) whose 3D Ferrers diagram is bounded inside the cube [0, n]^{3} is given by the nice product-formula

1 Accompanied by Maple packages TSPP and qTSPP available from

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/qtspp.html. The work of M. Kauers and C. Koutschan was supported in part by the Austrian FWF grants SFB F1305, P19462-N18, and P20162-N18.

The work of D. Zeilberger was supported in part by the United States of America National Science Foundation.

First Written: Aug. 2, 2008. This version: Aug. 5, 2008 .

∏_{1≤i≤j≤k≤n} \frac{i + j + k − 1}{i + j + k − 2} .

Ten years after Stembridge’s completely human-generated proof, George Andrews, Peter Paule, and Carsten Schneider [APS] came up with a computer-assisted proof, that, however required lots of human ingenuity and ad hoc tricks, in addition to a considerable amount of computer time.

Way back in the early-to-mid eighties (ca. 1983), George Andrews and Dave Robbins independently conjectured a q-analog of this formula, namely that the orbit-counting generating function ([B], p. 200, [Sta1], p. 289) is given by

∏_{1≤i≤j≤k≤n} \frac{1 − q^{i+j+k−1}}{1 − q^{i+j+k−2}} .

In this article we will show how to prove this conjecture (modulo a finite amount of routine computer calculations that may be already feasible today (with great technical effort), but that would most likely be routinely checkable on a standard desktop in twenty years).

Soichi Okada’s Crucial Insight

Our starting point is an elegant reduction, by Soichi Okada [O], of the q-TSPP statement, to the problem of evaluating a certain “innocent-looking” determinant. This is also listed as Conjecture 46 (p. 42) in Christian Krattenthaler’s celebrated essay [K] on the art of determinant evaluation.

Okada’s Determinant (Shown by Okada to imply the q-TSPP conj.)

Let, as usual, δ(α, β) be the Kronecker delta function (δ(α, β) = 1 when α = β and δ(α, β) = 0 when α ≠ β), and let, also as usual,

\left[{a \atop b}\right] = \frac{(1 − q^{a})(1 − q^{a−1}) ⋯ (1 − q^{a−b+1})}{(1 − q^{b})(1 − q^{b−1}) ⋯ (1 − q)} .

Define the discrete function a(i, j) by:

a(i, j) = q^{i+j−1} (\left[{i + j − 2 \atop i − 1}\right] + q \left[{i + j − 1 \atop i}\right]) + (1 + q^{i})δ(i, j) − δ(i, j + 1) .

Soichi Okada ([O], see also [K], Conj. 46) proved that the following conjectured determinant evaluation would imply the q-TSPP conjecture.

For any nonnegative integer n, there holds:

det(a(i, j))_{1≤i,j≤n} = ∏_{1≤i≤j≤k≤n} (\frac{1 − q^{i+j+k−1}}{1 − q^{i+j+k−2}} )^{2} .

So in order to prove the q-TSPP conjecture, all we need is to prove Okada’s conjectured determinant evaluation.

The q-Holonomic Ansatz

In [Z3], an empirical (yet fully rigorous!) approach is described to (symbolically!) evaluate determinants A(n) := det(a(i, j))_{1≤i,j≤n}, where a(i, j) is a holonomic discrete function of i and j. Note that this is an approach, not a method! It is not guaranteed to always work (and probably usually doesn’t!).

Let’s first describe this approach in more general terms, not just within the holonomic ansatz.

Suppose that a(i, j) is given “explicitly” (as it sure is here), and we want to prove for all n ≥ 0 that

det(a(i, j))_{1≤i,j≤n} = Nice(n) ,

for some explicit expression Nice(n) (as it sure is here).

The approach is to pull out of the hat another “explicit” (possibly in a much broader sense of the word explicit) discrete function B(n, j), and then verify the identities

∑_{j=1}^{n} B(n, j)a(i, j) = 0 , (1 ≤ i < n < ∞) ,  (Soichi)
B(n, n) = 1 , (1 ≤ n < ∞) .  (Normalization)

If we could do that, then by uniqueness, it would follow that B(n, j) equals the co-factor of the (n, j) entry of the n × n determinant divided by the (n − 1) × (n − 1) determinant (that is the co-factor of the (n, n) entry in the n × n determinant). Finally one has to prove the identity

∑_{j=1}^{n} B(n, j)a(n, j) = Nice(n)/Nice(n − 1) .  (Okada)

While [Z3] was concerned with the holonomic ansatz ([Z1]), everything goes verbatim to the qholonomic ansatz. Recall that the nice features of both the holonomic and q-holonomic ansatzes are

(i) They are closed under addition and multiplication .

(ii) It is always algorithmically decidable whether A=B .

(iii) If F (i_{1}, i_{2}, …, i_{r}) is a q-holonomic function of its variables, then

G(i_{1}, …, i_{r−1}) := ∑_{i_{r}=−∞}^{∞} F (i_{1}, …, i_{r−1}, i_{r})

is q-holonomic in the surviving variables i_{1}, …, i_{r−1}. Furthermore, if one has a q-holonomic description of F, one can get a q-holonomic description of G.

What is a q-Holonomic Description?

A q-holonomic discrete function of one variable f(n) is determined in terms of a linear recurrence equation

f(n) = ∑_{r=1}^{R} a_{r}(q, q^{n})f(n − r) ,

where a_{r}(q, q^{n}) are certain rational functions of their arguments, together with the initial values

f(0), ..., f(R − 1) .

Analogously, A q-holonomic discrete function f(m, n) of two variables m and n is determined in terms of a linear recurrence equation

f(m, n) = ∑_{r=1}^{R} a_{r}(q, q^{m}, q^{n})f(m, n − r) ,

where a_{r}(q, q^{m}, q^{n}) are rational functions in their arguments, together with the initial values f(m, 0), ..., f(m, R−1) that should be given holonomic descriptions on their own right as holonomic functions of a single variable (as described above). This can be continued to discrete functions of any number of variables.

Note that while every holonomic discrete function can be described as above, not every function that is described as above, with arbitrary a_{r}’s is necessarily holonomic (usually it isn’t!). However there are efficient algorithms for deciding whether a candidate discrete function given as above is holonomic or not. One empirical way of doing this is to use the description to crank many values, and then “guess” a pure recurrence with polynomial coefficients in the other variable, m, that can be routinely proved a posteriori.

The Computational Challenge

A priori we don’t have a clue whether the normalized cofactors, let’s call them A′(n, j), are qholonomic. One has to hope. By cranking out enough values, one tries to guess a “q-holonomic” description as above. Without this guess, there is nothing one can do!

Using several clever tools of the trade in the art of efficient guessing -a straightforward brute-force approach is hopeless!-we were able to come up with a conjectured q-holonomic description of these normalized cofactors. It is contained in the Maple package qTSPP accompanying this article. The much easier q = 1 case (that would give a new proof to the already proved Stembridge theorem) is contained in the Maple package TSPP.

Note that once we have a conjectured q-holonomic description of the normalized cofactors, proving it rigorously is completely routine. Identity (Soichi) is a decidable q-holonomic identity and there exist algorithms of Chyzak, Salvy, and Takayama ([CS], [T]) to prove it. Also (Normalization) is automatically satisfied, it being part of the definition of B(n, j). Finally (Okada) is also of the form A = B where both sides are q-holonomic. The left side is holonomic because of the closure under multiplication and definite-summation, and the right side, Nice(n)/Nice(n − 1) is not just q-holonomic (a solution of some linear recurrence with polynomial coefficients (in q, q^{n}) ) but in fact closed-form (the defining recurrence is first-order).

The Semi-Rigorous Shortcut

We believe that even today, performing the above steps is feasible, but it would require a huge technical effort. But why bother? First, if we wait for twenty more years, Moore’s Law will probably enable us to finish up these finitely-many routine calculations with no sweat. Besides, since now we know for sure that a fully rigorous proof exists, do we really want to see it? It won’t give us any new insight. The beauty of the present approach is in the meta-insight, reducing the statement of the conjecture to a finite calculation. Furthermore, we know a priori that there exists an operator P (q, q^{n}, N) (where N is the shift operator in n: Nf(n):=f(n+1)) that annihilates the difference of the left and right sides of (Okada). If that operator has order L, say, then a completely rigorous proof would be to check (Okada) for 0 ≤ n ≤ L − 1. At present, we are unable to find P, and hence do not know the value of L. But it is very reasonable that L would be less than, say, 400, and checking the first 400 cases of (Okada) (and analogously for (Soichi)) is certainly doable (we did it for L = 100, and L = 400 for TSPP, but you are welcome to go further). These are done in procedures CheckqTSPP in the Maple package qTSPP, and CheckTSPP in the Maple package TSPP, respectively. The corresponding input and output files can be found in the webpage of this article mentioned above. As a technical aside, let’s confess that Maple running on our computer was only able to check (Soichi) and (Okada) for L ≤ 30, for symbolic q, but for random numerical choices of q it went up to L = 100, and it is easy to see that with sufficiently many choices of numerical q for a given L, one can prove it for symbolic q.

In 1993, Zeilberger [Z2] proposed the notion of semi-rigorous proof. At the time he didn’t have any natural examples. The present determinant evaluation, that was shown by Okada to imply a longstanding open problem in enumerative combinatorics, is an excellent example of a semi-rigorous proof that is (at least) as good as a rigorous proof. Let us conclude by promising that if any one is willing to pay us $10^{7} (ten million US dollars), we will be more than glad to fill-in-the details.

References

[APS] George E. Andrews, Peter Paule, and Carsten Schneider, Plane Partitions VI. Stembridge’s TSPP theorem, Adv.Appl.Math. 34 (2005), 709-739.

[B] David M. Bressoud, “Proofs and Confirmations”, Math. Assoc. America and Cambridge University Press (1999).

[CS] Frédéric Chyzak and Bruno Salvy, Non-commutative elimination in Ore algebras proves multivariate identities, J. of Symbolic Computation 26 (1998), 187-227.

[K] Christian Krattenthaler, Advanced Determinant Calculus, Sém. Lothar. Comb. 42 (1999), B42q. (“The Andrews Festschrift”, D. Foata and G.-N. Han (eds.))

[LL] G. Labelle and P. Leroux (editors), Combinatoire énumérative, Lecture Notes in Mathematics 1234. Springer Verlag, New York.

[LV] Pierre Leroux and G. X. Viennot, Combinatorial resolution of systems of differential equations, I. Ordinary differential equations. In Combinatoire énumérative, ed. G. Labelle and P. Leroux. Lecture Notes in Mathematics 1234, 285-293. Springer Verlag, New York.

[O] Soichi Okada, On the generating functions for certain classes of plane partitions, J. Comb. Theory, Series A 53 (1989), 1-23.

[Sta1] Richard Stanley, A baker’s dozen of conjectures concerning plane partitions. In Combinatoire énumérative, ed. G. Labelle and P. Leroux. Lecture Notes in Mathematics 1234, 285-293. Springer Verlag, New York.

[Sta2] Richard Stanley, Symmetries of plane partitions, J. Comb. Theory, Series A 43 (1986), 103-113.

[Ste] John Stembridge, The enumeration of totally symmetric plane partitions, Advances in Mathematics 111, 227-243 (1995).

[T] Nobuki Takayama, Gröbner basis, integration and transcendental functions. In “Proceedings of ISSAC’90” (1990), 152-156.

[Z1] Doron Zeilberger, A Holonomic systems approach to special functions identities, J. of Computational and Applied Math. 32, 321-368 (1990).

[Z2] Doron Zeilberger, Theorems for a price: Tomorrow’s semi-rigorous mathematical culture, Notices of the Amer. Math. Soc. 40 # 8, 978-981 (Oct. 1993). Reprinted: Math. Intell. 16, no. 4, 11-14 (Fall 1994).

[Z3] Doron Zeilberger, The HOLONOMIC ANSATZ II. Automatic DISCOVERY(!) and PROOF(!!) of Holonomic Determinant Evaluations, Annals of Combinatorics 11 (2007), 241-247.

Manuel Kauers, Research Institute for Symbolic Computation, J. Kepler Univ. Linz, Austria. mkauers@risc.uni-linz.ac.at .

Christoph Koutschan, Research Institute for Symbolic Computation, J. Kepler Univ. Linz, Austria. ckoutsch@risc.uni-linz.ac.at .

Doron Zeilberger, Mathematics Department, Rutgers University (New Brunswick), Piscataway, NJ, USA. zeilberg@math.rutgers.edu .