A Constant Term Identity Featuring The Ubiquitous (And Mysterious) Andrews-Mills-Robbins-Rumsey Numbers 1,2,7,42,429, ...

Doron Zeilberger* *

Appeared in: J. Comb. Theory Series A 66 (1994), 17-27.

If A = B then B = A (Axiom satisfied by the equality relation)

Abstract: George Andrews’s recent proof of the Mills-Robbins-Rumsey conjectured formula for the number of totally symmetric self-complementary plane partitions is used to derive a new multivariate constant term identity, reminiscent of, but not implied by, Macdonald’s BC_{n}- Dyson identity. The method of proof consists in translating to the language of constant terms an expression of Doran for the desired number in terms of sums of minors of a certain matrix. The question of a direct proof of the identity, which would furnish an alternative proof of the Mills-Robbins-Rumsey conjecture, is raised, and a prize is offered for its solution.

0. Prologue

Sometimes, it may occur to mathematician X, in his attempt at proving a conjectured equality A = B, to introduce another quantity C, and to attempt to prove the two lemmas A = C and C = B. The original conjecture A = B would then follow by the transitivity of the = relation. Alas, it might happen that, after the successful completion by X of the first part of his program, but before finishing the second part, the conjecture A = B is proved by his rival Y by a completely different method. Should X let thousands of hours, fifty yellow pads, and ten ball-point pens go unrecorded in the archival literature? Certainly not! All that X has to do is promote the equality C = B from the status of lemma to that of theorem and observe that its proof follows immediately from his own lemma A = C, Y’s theorem A = B, and the symmetry and transitivity of the equality relation. To be on the safe side, X should argue also that in addition to the intrinsic interest of C = B, the method of proof of the lemma A = C is interesting, and might lead to the proof of other conjectures.

The above scenario happened with the following specialization.

X= Your faithful servant.

Y= George Andrews.

A:= The number of totally symmetric self complementary plane partitions (TSSCPP) whose 3D Ferres diagrams fit inside [0, 2n]^{3}.

B := ∏_{i=0}^{n−1} \frac{(3i + 1)!}{(n + i)!} ,

the Andrews-Mills-Robbins-Rumsey sequence 1,2,7,42,429, ... [A3],[MRR1],[MRR2],[Ro1].

* Department of Mathematics, Temple University, Philadelphia, PA19122. Supported in part by NSF grant DMS8800663.

C := CT ∏_{1<=i<j<=n}(1 − x_{i}/x_{j}) ∏_{i=1}^{n}(1 + x_{i}^{−1})^{n−i}{∏_{i=1}^{n}(1 − x_{i})^{−1} ∏_{1<=i<j<=n}(1 − x_{i}x_{j})^{−1}} ,

where ”CT” stands for the phrase ”the constant term of”, i.e., the coefficient of x_{1}^{0}...x_{n}^{0}.

1. Introduction

George Andrews[A1] has recently proved the following conjecture of Mills, Robbins, and Rumsey[MRR2] (see also [Ro1],[S])

Theorem A=B: (Andrews[A1]) A = B.

In this paper we will prove

Theorem C=B: C = B.

This identity closely resembles Macdonald’s [Macd2] celebrated BC_{n}-Dyson identity, but doesn’t seem to be implied by it. Its mere existence seems to indicate that Macdonald’s identities and conjectures are far from being the only explicitly evaluable constant term expressions, and that there are still many more that are waiting to be discovered. Even more exciting is the possibility that there exists a common generalization of Macdonald’s constant term identities and the present one. Section 7 presents yet another such identity. We refer the readers to [Gu] and [Ga-Go] for an update on the status of Macdonald’s constant term conjectures.

In the constant term C, we view the rational function inside the braces as a power series in positive powers of x_{1}, ..., x_{n}. When this gets multiplied by the Laurent polynomial in front of the braces, one gets a well defined Laurent series, with a well defined constant term.

Theorem C=Bwould follow from Andrews’s theorem A=B and the following lemma:

Lemma A=C: A = C.

I am offering 25 US dollars for a direct proof of theorem C=B, that does not use Andrews’s theorem A=B. Such a proof, combined with my lemma A=C would, of course, give a new proof of theorem A=B.

The readers are welcome to look up the definition of TSSCPP in [MRR2] or [S], if they wish, but the present paper can be understood without it, provided one is willing to believe Doran’s[Do] result, to be recalled shortly, that the number of these creatures, whatever they are, equals the sum of minors of a certain matrix. In fact the larger message of this paper is in introducing a new and potentially useful method for expressing sums of minors of matrices whose entries are binomial coefficients in terms of constant terms of rational functions, the Mills-Robbins-Rumsey conjecture being the instructive example by which this method is being illustrated. The present method can be viewed as a determinantal extension of Egorychev’s[E] method of ”integral representation” (which is tantamount to ”constant term”) for binomial coefficients sums. MacMahon’s celebrated master theorem[MacM] that expresses a certain determinant as a certain constant term also comes to mind, but at first sight only appears to be a distant cousin.

2. Doran’s Sum of Minors expression for the Number of TSSCPP

To prove lemma A = C, we need a result of Bill Doran[Do] (no relation). Let D be the sum of all the n × n minors of the following n × (2n − 1) matrix:

X_{i,j} := ({i − 1 \atop j − i}) , 1 <= i <= n , 1 <= j <= 2n − 1 .

Theorem A=D(Doran[Do]): A = D. It remains to prove that D = C. I will prove a more general result. Let D′ be the sum of all the n × n minors of the n × (2n + m − 1) matrix X given by

X_{i,j} := ({m + i − 1 \atop j − i}) , 1 <= i <= n , 1 <= j <= 2n + m − 1 .

and let C′ be given by

C′ := CT ∏_{1<=i<j<=n}(1 − x_{i}/x_{j}) ∏_{i=1}^{n}(1 + x_{i}^{−1})^{m+n−i}{∏_{i=1}^{n}(1 − x_{i})^{−1} ∏_{1<=i<j<=n}(1 − x_{i}x_{j})^{−1}} .

I will prove Lemma D’=C’: D′ = C′. The proof of this lemma will be given in the next section. Assuming it for the moment, we have Corollary D=C: D = C. Proof:Take m = 0 in Lemma D’=C’. Completion of the proof of Lemma A=C: Combine Doran’s[Do] Lemma A = D and Corollary D = C.

3. Proof of Lemma D’=C’: We will have a fairly long string of equalities. Whenever the equality requires explanation we will label the equal sign with an integer, and give the explanation in section 4, under the heading of that integer. Some readers may prefer to consult section 4 simultaneously.

D′ := ∑_{1<=j_{1}<j_{2}<...<j_{n}<=2n+m−1} det({m + i − 1 \atop j_{r} − i})_{1<=i<=n , 1<=r<=n} =

∑_{0<=j_{1}<j_{2}<...<j_{n}<=2n+m−2} det({m + i − 1 \atop j_{r} − i + 1})_{1<=i<=n , 1<=r<=n}

=^{(1)} ∑_{0<=j_{1}<j_{2}<...<j_{n}<=2n+m−2} ∑_{πϵS_{n}} sgn(π) ∏_{r=1}^{n}({m + π(r) − 1 \atop j_{r} − π(r) + 1})

=^{(2)} ∑_{0<=j_{1}<j_{2}<...<j_{n}<=2n+m−2} ∑_{πϵS_{n}} sgn(π)CT [∏_{r=1}^{n} \frac{(1 + x_{r})^{m+π(r)−1}}{x_{r}^{j_{r}−π(r)+1}} ]

= ∑_{0<=j_{1}<j_{2}<...<j_{n}<=2n+m−2} CT [\begin{matrix}∏ & {n \atop r=1} & (1 + x_{r})^{m} \\ x_{r} & j^{r} \end{matrix} ∑_{πϵS_{n}} sgn(π) ∏_{r=1}^{n}[(1 + x_{r})x_{r}]^{π(r)−1}]

=^{(3)} CT [∏_{r=1}^{n} (1 + x_{r})^{m} ∏_{1<=i<j<=n}[(1 + x_{i})x_{i} − (1 + x_{j})x_{j}] ∑_{0<=j_{1}<j_{2}<...<j_{n}<=2n+m−2} x_{1}^{−j_{1}}...x_{n}^{−j_{n}}]

=^{(4)} CT [∏_{r=1}^{n} (1 + x_{r})^{m} ∏_{1<=i<j<=n}[(1 + x_{i})x_{i} − (1 + x_{j})x_{j}] ∑_{0<=j_{1}<j_{2}<...<j_{n}<∞} x_{1}^{−j_{1}}...x_{n}^{−j_{n}}]

=^{(5)} CT [∏_{r=1}^{n} (1 + x_{r}^{−1})^{m} ∏_{1<=i<j<=n}[(1 + x_{i}^{−1})x_{i}^{−1} − (1 + x_{j}^{−1})x_{j}^{−1}] ∑_{0<=j_{1}<=j_{2}<=...<=j_{n}<∞} x_{1}^{j_{1}}...x_{n}^{j_{n}}]

=^{(6)} CT [∏_{r=1}^{n} (1 + x_{r}^{−1})^{m} ∏_{1<=i<j<=n}[(1 + x_{i}^{−1})x_{i}^{−1} − (1 + x_{j}^{−1})x_{j}^{−1}]·

(1 − x_{n})^{−1}(1 − x_{n}x_{n−1})^{−1}...(1 − x_{n}x_{n−1}...x_{1})^{−1}]

=^{(7)} \frac{1}{n!}CT [∏_{r=1}^{n} (1 + x_{r}^{−1})^{m} ∏_{1<=i<j<=n}[(1 + x_{i}^{−1})x_{i}^{−1} − (1 + x_{j}^{−1})x_{j}^{−1}]·

∑_{πϵS_{n}} sgn(π)π[(1 − x_{n})^{−1}(1 − x_{n}x_{n−1})^{−1}...(1 − x_{n}x_{n−1}...x_{1})^{−1}]]

=^{(8)} \frac{1}{n!}CT [∏_{r=1}^{n} (1 + x_{r}^{−1})^{m} ∏_{1<=i<j<=n}[(1 + x_{i}^{−1})x_{i}^{−1} − (1 + x_{j}^{−1})x_{j}^{−1}]·

\frac{∏_{1<=i<j<=n}(x_{j} − x_{i})}{∏_{i=1}^{n}(1 − x_{i}) ∏_{1<=i<j<=n}(1 − x_{i}x_{j})}]

=^{(3)} \frac{1}{n!}CT [∏_{r=1}^{n} (1 + x_{r}^{−1})^{m} ∏_{1<=i<j<=n}(x_{j} − x_{i}) ∏_{i=1}^{n}(1 − x_{i})^{−1} ∏_{1<=i<j<=n}(1 − x_{i}x_{j})^{−1}·

∑_{πϵS_{n}} sgn(π) ∏_{r=1}^{n}[(1 + x_{r}^{−1})x_{r}^{−1}]^{π(r)−1} ]

=^{(9)} CT [∏_{r=1}^{n} (1 + x_{r}^{−1})^{m} ∏_{1<=i<j<=n}(x_{j} − x_{i}) ∏_{i=1}^{n}(1 − x_{i})^{−1} ∏_{1<=i<j<=n}(1 − x_{i}x_{j})^{−1}·

∏_{r=1}^{n}[(1 + x_{r}^{−1})x_{r}^{−1}]^{r−1} ]

= CT [∏_{r=1}^{n} (1 + x_{r}^{−1})^{m+r−1} ∏_{1<=i<j<=n}(1 − x_{i}/x_{j}) ∏_{i=1}^{n}(1 − x_{i})^{−1} ∏_{1<=i<j<=n}(1 − x_{i}x_{j})^{−1} ] , QED .

4. Explanations Of The Above Equalities

1. The definition of the determinant.

2. The binomial theorem and the fact that CT [f(x)g(y)] = CT [f(x)]CT [g(y)] .

3. The Vandermonde determinant identity:

∑_{πϵS_{n}} sgn(π) ∏_{r=1}^{n} y_{r}^{π(r)−1} = ∏_{1<=i<j<=n}(y_{i} − y_{j}) .  (V)

See [Ge] and [A2], sec. 4.4 for Gessel’s beautiful combinatorial proof.

4. The added terms are of higher degree then the polynomial in front of the sigma, and so add 0 to the constant term.

5. We make the transformation x_{i} → x_{i}^{−1}, i = 1, ..., n, which obviously does not change the constant term. We also changed the summation range from 0 < j_{1} < ... < j_{n} < ∞ to 0 <= j_{1} <= ... <= j_{n} < ∞, which doesn’t change anything, since the extra monomials all have at least two of their exponents equal, and hence their contribution to the constant term is zero, thanks to the anti-symmetry of the kernel.

6. Here we used

∑_{0<=j_{1}<=j_{2}<=...<=j_{n}<∞} x_{1}^{j_{1}}...x_{n}^{j_{n}} = (1 − x_{n})^{−1}(1 − x_{n}x_{n−1})^{−1}...(1 − x_{n}x_{n−1}...x_{1})^{−1} .

For n = 1 this is just the sum of an infinite geometric series. Assuming this is true for n − 1 variables, x_{2}, ..., x_{n}, we have

∑_{0<=j_{1}<=j_{2}<=...<=j_{n}<∞} x_{1}^{j_{1}}...x_{n}^{j_{n}} =

[ ∑_{j_{1}=0}^{∞} (x_{1}...x_{n})^{j_{1}}] · [ ∑_{0<=j_{2}−j_{1}<=...<=j_{n}−j_{1}<∞} x_{2}^{j_{2}−j_{1}}...x_{n}^{j_{n}−j_{1}}]

= (1 − x_{1}...x_{n})^{−1}(1 − x_{2}...x_{n})^{−1}...(1 − x_{n})^{−1} .

7. Here we ”averaged” over all the images under the symmetric group, noting that the constant term is not affected. More explicitly, for any Laurent series f(x_{1}, ..., x_{n}) let the symmetric group act naturally by:

π(f)(x_{1}, ..., x_{n}) = f(x_{π(1)}, ..., x_{π(n)}) ,

and let

f^{#} = \frac{1}{n!} ∑_{πϵS_{n}} π(f) ,

then CT (f) = CT (f^{#}). We also used the obvious fact that if f^{&} denotes the ”anti-symmetrizer”:

f^{&} = \frac{1}{n!} ∑_{πϵS_{n}} sgn(π)π(f) ,

then if g is anti-symmetric, then

(gf)^{#} = g(f^{&}) .

8. Here we used the identity:

∑_{πϵS_{n}} sgn(π) π[(1 − x_{n})^{−1}(1 − x_{n}x_{n−1})^{−1}...(1 − x_{n}x_{n−1}...x_{1})^{−1}] =  (L)

\frac{∏_{1<=i<j<=n}(x_{j} − x_{i})}{∏_{i=1}^{n}(1 − x_{i}) ∏_{1<=i<j<=n}(1 − x_{i}x_{j})} .

This is easily seen to be equivalent to Littlewood’s identity that sums all the Schur functions (e.g. [Macd1], ex I.5.4, p. 45). Here I give another proof which, incidentally, also proves Littlewood’s identity. Let’s call the left side of (L) f(x_{1}, ..., x_{n}), and its right side g(x_{1}, ..., x_{n}). Separating the sum over S_{n} in the definition of f into the n subsets of S_{n}, according to the values of π(n), we have (chopping π(n) = i amounts to losing n − i inversions)

f(x_{1}, ..., x_{n}) = (1 − x_{1}x_{2}...x_{n})^{−1} ∑_{i=1}^{n}(−1)^{(n−i)}f(x_{1}, x_{2}, ..., x̂_{i}, ...x_{n}) .

Since f(x_{1}) = g(x_{1}) is obviously true, f = g is true for n = 1. (L) would follow by induction if we can prove that

g(x_{1}, ..., x_{n}) = (1 − x_{1}x_{2}...x_{n})^{−1} ∑_{i=1}^{n}(−1)^{(n−i)}g(x_{1}, x_{2}, ..., x̂_{i}, ...x_{n}) ,

which is equivalent to

(1 − x_{1}...x_{n}) = ∑_{i=1}^{n} (−1)^{n−i} g(x_{1}, ..., x̂_{i}, ..., x_{n})/g(x_{1}, ..., x_{n}) .

But it is readily seen that

(−1)^{n−i} \frac{g(x_{1}, ..., x̂_{i}, ..., x_{n})}{g(x_{1}, ..., x_{n})} = (1 − x_{i}) ∏_{1<=j<=n,j≠i}(1 − x_{i}x_{j})/(x_{i} − x_{j}) .x_{n}

It thus remains to prove that

(1 − x_{1}...x_{n}) = ∑_{i=1}^{n}(1 − x_{i}) ∏_{1<=j<=n,j≠i}(x_{i} − x_{j})/(1 − x_{i}x_{j}) .

This is a rational function identity resembling those of Good[Go], Gustafson and Milne[Gu-Mi], Gross and Richards [Gr-Ri], and Milne [Mi]. It is easily proved by Lagrange-interpolating the degree-n polynomial (in z) f(z) := (1 − zx_{1})...(1 − zx_{n}) at the n + 1 points 1, x_{1}, ..., x_{n}, then substituting z = 0 and finally making trivial adjustments.

9. This is (7) in reverse.

5. Robbins’s Conjectured Expression For D’, And a More General (and hence easier) Constant Term Conjecture Dave Robbins[Ro2], in a private communication, made the following conjecture regarding the sum of minors D‘. Let B′(m, n) be defined by B′(0, n) = B(n), and

\frac{B′(m + 1, n)}{B′(m, n)} = 2 ∏_{j=1}^{n−1} \frac{(2m + j + 2)(3m + 2n + 2 + j)}{(m + 1 + j)(3m + 2 + 2j)} ,

then

Conjecture D’=B’ (Robbins[Ro2]): D′ = B′.

Conjecture D’=B’ would, of course, follow from the following constant term conjecture

Conjecture C’=B’: C′ = B′.

C’=B’, being more general than C=B, should be easier to prove. Its proof will, in particular, solve the 25 dollars problem stated above.

6. Sums of Minors of Generalized Binomial Coefficients Matrices

Our approach for expressing the sums of minors of the matrix X took advantage of the fact that its entries were representable as constant terms as follows:

X_{i,j} = CT \frac{(1 + x)^{m+i−1}}{x^{j−i}} = CT [\frac{(1 + x)^{m}((1 + x)x)^{i−1}}{x^{j−1}} ] .

Scanning the proof of D’=C’ given in section 3, we see that it is still valid when (1+x)^{m} is replaced by a general polynomial f(x) and (1 + x)x is replaced by a general polynomial g(x). We thus have

General Theorem: Let f(x) and g(x) be polynomials and consider the n × ( deg(f) + (n − 1)deg(g) + 1) matrix whose entries are given by

X_{i,j :=}CT [\frac{f(x)g(x)^{i−1}}{x^{j−1}} ] .

The sum of all its n × n minors equals

CT ∏_{1<=i<j<=n}(x_{j} − x_{i}) ∏_{i=1}^{n} f(x_{i}^{−1})g(x_{i}^{−1})^{n−i}{∏_{i=1}^{n}(1 − x_{i})^{−1} ∏_{1<=i<j<=n}(1 − x_{i}x_{j})^{−1}} =

\frac{1}{n!}CT ∏_{1<=i<j<=n}(x_{j}−x_{i}) ∏_{i=1}^{n} f(x_{i}^{−1}) ∏_{1<=i<j<=n}(g(x_{j}^{−1}) − g(x_{i}^{−1}))\{∏_{i=1}^{n}(1−x_{i})^{−1} ∏_{1<=i<j<=n}(1−x_{i}x_{j})^{−1}\} .

Proof: Do a global ”replace” in section 3, replacing (1+x )^{m} by f(x) and x (1+x ) by g(x). (Here we used the MATHEMATICA convention of transformation rules where ”x ” means ”anything, to be called x”.) The second equality follows from explanation 4 of section 4.

7. Another Constant Term Identity

Taking f(x) = (1 + x)^{m}, g(x) = (1 + x), the matrix X becomes

X_{i,j} := ({m + i − 1 \atop j − 1}) , 1 <= i <= n , 1 <= j <= n + m .  (∗)

The sum of its n × n minors can be computed explicitly, since each minor is nothing but a Schur function evaluated at x_{1} = x_{2} = ... = x_{n} = 1, by the Jacobi-Trudi formula (e.g. [Macd1], p.25, (3.5)), and these can be summed (q = 1 in [Macd1], p.52, (4), see also [De1][De2] for a superb exposition about summing Schur functions) to yield

∏_{j=0}^{n−1} ∏_{i=1}^{m} \frac{2i + j}{i + j} ,

as observed empirically by Dave Robbins[Ro2]. Combining the general theorem with the above, we get the following elegant multi-variate constant term identity.

IDENTITY:

\frac{1}{n!}CT ∏_{1<=i≠j<=n}( 1− \frac{x_{i}}{x_{j}} ) ∏_{i=1}^{n}(1+x_{i}^{−1})^{m}\{∏_{i=1}^{n}(1−x_{i})^{−1} ∏_{1<=i<j<=n}(1−x_{i}x_{j})^{−1}\} = ∏_{j=0}^{n−1} ∏_{i=1}^{m} \frac{2i + j}{i + j} .

I am offering 5 US dollars for a direct proof of this identity.

REFERENCES

[A1] Andrews, George E., Plane Partitions V: the T.S.S.C.P.P conjecture, preprint.

[A2] Andrews, George E., q-SERIES: THEIR DEVELOPMENT AND APPLICATIONS IN ANAL-YSIS, NUMBER THEORY, COMBINATORICS, PHYSICS, AND COMPUTER ALGEBRA, CBMS 66, AMS, Providence, 1986.

[A3] Andrews, George E., Plane Partitions III: the weak Macdonald conjecture, Invent. Math. 53 (1979), 193-225.

[De1] De’sarme’nien, Jacques, La de’monstration des identite’s de Gordon et MacMahon et de deux identite’s nouvelles, Se’m. Lotharingien de Combinatoire, 15 (1986), ed. by A. Kerber, Publications IRMA, Strasbourg.

[De2] De’sarme’nien, Jacques, Une ge’ne’ralisation des formules de Gordon et de MacMahon, C.R. Acad. Sci. Paris, Ser. I 309 (1989), 269-272.

[Do] Doran, William F., A connection between alternating sign matrices and totally symmetric, self-complementary plane partitions, preprint.

[E] Egorychev, G. P., INTEGRAL REPRESENTATION AND THE COMPUTATION OF COM-BINATORIAL SUMS, American Mathematical Society Translations 59, AMS, Providence, 1984.

[Ga-Go] Garvan, Frank G., and Gonnet, Gaston, Macdonald’ constant term conjectures for exceptional root systems, Bulletin (new series) of the Amer. Math. Soc, to appear.

[Ge] Gessel, Ira, Tournaments and Vandermonde’s determinant, J. Graph Theory 3(1979), 305-307.

[Go] Good, Irving J., Short proof of a conjecture of Dyson, J. Math. Phys. 11(1970), 1884. [Gr-Ri] Gross, Kenneth I., and Richards, Donald St. P., Constant term identities and hypergeometric functions on spaces of hermitian matrices, preprint.

[Gu] Gustafson, Robert A., A generalization of Selberg’s beta integral, Bulletin (new series) of the Amer. Math. Soc. 22(1990), 97-105. [Gu-Mi] Gustafson, Robert A., and Milne, Stephen C., Schur functions, Good’s identity, and hypergeometric series well poised in SU(n), Adv. in Math. 57(1985), 209-225.

[MRR1] Mills, William H., Robbins, David P., and Rumsey, Howard, Proof of the Macdonald conjecture, Invent. Mat 66(1982), 73-87.

[MRR2] Mills, William H., Robbins, David P., and Rumsey, Howard, Self complementary totally symmetric plane partitions, J. Combin. Theory Ser. A 42(1986), 277-292.

[MacM] MacMahon, Percy A., Combinatory Analysis, Vol. 1, Cambridge University Press, London, 1916. (Reprinted: Chelsea, New York, 1960).

[Macd1] Macdonald, Ian G., SYMMETRIC FUNCTIONS AND HALL POLYNOMIALS, Oxford University Press, Oxford, 1979.

[Macd2] Macdonald, Ian G., Some conjectures for root systems, SIAM J. Math. Anal. 13(1982), 988-1007.

[Mi] Milne, Stephen C., A q-analog of the Gauss Summation Theorem for hypergeometric series in U(n), Adv. Math. 72(1988) 59–131.

[Ro1] Robbins, David P., The story of 1, 2, 7, 42, 429, 7436, ..., to appear in The Mathematical Intelligencer.

[Ro2] Robbins, David P., private communication.

[S] Stanley, Richard, A baker’s dozen of conjectures concerning plane partitions, in: COMBINA-TOIRE ENUMERATIVE, ed. by G. Labelle and P. Leroux, Lecture Notes in Mathematics 1234, Springer, Berlin, 1986. Feb, 1991. Revised: Mar, 1991. EPILOGUE: Some Philosophical (and Technical) Ramblings On Andrews’s Proof, In Particular, And Of The Whole Genre, In General Note: This epilogue to “A Constant Term Identity .. 1,2,7,42,429, ” was NOT included in the original version, published in JCT(A) 66 (1994), 17-27, to comply with the request of the editor, George Andrews.

1. Comments On Andrews’s Presentation Of His Proof George Andrews’s great achievement is obscured by the apparent complexity of his proof, that seems very brute-force-ish and uninspiring, and that contains a sequence of seven hair-raising lemmas. I claim that Andrews’s proof can be made much more streamlined and palatable by clearly separating the inspiration part from the perspiration part, especially since the latter will be soon completely doable by computers, and is already so to a large extent. Furthermore, there is no point in actually presenting the computer-generated proofs of the claimed identities, since they are readily reproducible. All one has to do is report that they were successfully proved by the author’s computer.

Andrews’s method consists in a slight (but crucial) change in a determinant expression of Stembridge[Ste] for the desired number. Calling the (modified) Stembridge matrix M(n), Andrews pulls out of the hat a lower triangular matrix, R(n) with certain closed form coefficients, such that V (n) := M(n) · R(n) is lower triangular, with certain explicitly given diagonal terms. Since both V (n), and R(n) are lower triangular, their determinants are easy to compute (namely the product of the diagonal entries), and it follows that det(M(n)) = det(V (n))/det(R(n)).

Andrews’s breakthrough, in addition to modifying the Stembridge matrix, was in the actual finding of the miracle matrix R(n), which was experimental mathematics par excellenceproof that M(n) · R(n) is indeed lower-triangular, and the computation of its diagonal entries are purely routine, at least in principle, thanks to the holonomic theory in [Z1]. Furthermore, since the above task is equivalent to proving a certain double-sum hypergeometric identity, the proof of the above matrix product will also become purely routine, in practice, once Herb Wilf and I will be successful in our current efforts at generalizing our WZ method[W-Z1][W-Z2] and my ”fast” [Z2] algorithm to multiple sums. Under this optimistic hypothesis, a modern rendition of Andrews’s proof will go as follows. Exhibit the matrix R(n), and state

Andrews’s Theorem: V (n) := M(n) · R(n) is a lower-triangular matrix, and its diagonal terms are

v(i, i) = −({3i + 1 \atop i})^{2}/({2i \atop i})^{2} .

Proof(2000 version): Routine. QED

Consequently, all of section 3, and a large part of section 4 of [A1] will seem in a few years a quaint waste of paper. But even, at this very moment, Andrews’s paper can be shortened considerably, if one adopts the above convention that there is no point in reproducing purely routine calculations done by readily available software. To do the WZ method, all one needs is MACSYMA or MAPLE, on which Gosper’s algorithm is built-in, and my more general algorithm[Z2][Z3] for evaluating single-sum hypergeometric series, implemented via MAPLE programs, are free for the asking. Consequently, whenever one makes use of the WZ method[W-Z1], or of my more general ”fast” algorithm[Z2][Z3], it’s enough to report that the program was indeed run, and the outcome was positive. All those who really want to ”see” the proof (i.e. the certificate) are welcome to run the program themselves.

More specifically, lemmas 2-6 of [A1] are currently purely routine. In fact, for one of these lemmas, lemma 2, Andrews did make use of the WZ method. Andrews writes (my capitals):

”The underlying hypergeometric series ... is not one of the well-known summable series. Consequently, we MUST rely on the WZ-method([W-Z1]).”

It turns out that lemmas 3-6, being single hypergeometric sums, are also doable by either [W-Z1] or [Z2], so one MAY do them that way, without bothering to derive them from known identities. Consequently, even today, it would have been legitimate to only state lemmas 2-6, and proclaim their proofs as routine.

Similar remarks apply to Andrews’s previous proofs in his continuing saga on plane partitions (see

[A1] for references).

2.A Modern Rendition Of The Robbins-Mills-Rumsey Proofs of Andrews’s and Macdonald’s Plane Partition Conjectures

Like Andrews’s proofs, the Mills-Robbins-Rumsey[MRR2] ingenious proofs of the generating function for cyclically symmetric plane partitions, conjectured by Macdonald([Macd1], p. 53), and of a conjecture of Andrews (see [MRR2]) can be shrunk to few lines, if one isolates the purely routine identities that are being used, and refrains from presenting their readily producible proofs.

In [MRR], they present a method for evaluating determinants of the form d(m) := det(a_{i,j})_{1<=i<=m,1<=j<=m}, for a certain explicitly given double-indexed sequence a_{i,j} (1 <= i < ∞, 1 <= j < ∞). The way they do it is to exhibit a doubly indexed sequence C_{j}^{(m)}, 1 <= j <= m < ∞, such that, for every fixed m, the vector C_{j}^{(m)}, j = 1, ..., m, is proportional to the cofactors of the last row in (a_{m,j})_{1<=j<=m}. To show that this is indeed true, they prove that

∑_{j=1}^{m} a_{i,j}C_{j}^{(m)} = 0 .  (i)

Then they evaluate

∑_{j=1}^{m} a_{m,j}C_{j}^{(m)} = e(m) , say  (ii)

that in their case turns out to be closed form, and finally they prove

C_{m}^{(m)} = f(m) (another explicit expression) .  (iii)

Since the actual cofactor of a_{m,m} in (a_{i,j})_{1<=i<=m,1<=j<=m} is det(a_{i,j})_{1<=i<=m−1,1<=j<=m−1} = d(m − 1), if follows that

\frac{d(m)}{d(m − 1)} = \frac{e(m)}{f(m)} .

In general, whenever, a_{i,j} and C_{j}^{(m)} are holonomic, all the above claims are routinely verifiable([Z1]) albeit only in principle (today). If a_{i,j} is closed form, and so is C_{j}^{(m)}, then (i)-(iii) are routinely provable also in practice. However, in the specific determinants evaluated in [MRR1], C_{i}^{(m)} turns out to be given by a single sum, so (i) and (ii) are double sums, and a priori it seems that one has to wait a few years before they become routinely verifiable. However, it turns out, that in the two cases considered in [MRR1], both inner sums of (i) and (ii) are explicitly summable (and hence can be found, from scratch, by [Z2][Z3]), and hence the whole thing is routinely verifiable, even today.

All the above also applies to q-analogs, and q-binomial coefficients, using the theory of q-holonomic functions, and q-creative telescoping[Z4]. Let’s illustrate the above remarks by giving new renditions of the q = 1 case of Andrews’s conjecture, and of the generating function for cyclically symmetric plane partitions.

Theorem([MRR1]): Let

a_{i,j} := δ_{i,j} + ({i + j \atop j − 1}) ,

with the above notation,

\frac{d(m)}{d(m − 1)} = \frac{({3m+1 \atop m})}{({2m \atop m})} .

Proof(1990 version of the proof in [MRR1]): Introduce

C_{j}^{(m)} := ∑_{i=1}^{m}(−1)^{i+j}({m + 1 \atop i − j})({m + i \atop i})({2m − i \atop m − i}) ,

e(m) := ({3m + 1 \atop m}) , f(m) := ({2m \atop m}) .

(i),(ii),(iii) are routinely provable, and indeed were proved, by my computer, Shalosh B. Ekhad. The theorem follows by the above general remarks. QED

Next, let’s give a modern rendition of the determinant evaluation that implies the generating function for cyclically symmetric plane partitions ([MRR1]). Here one has q- (alias basic) hypergeometric identities, but these too, are routinely verifiable[Z4] (for single sums). Once again the double sums that occur have explicitly evaluable inner sums, so everything below is indeed routine, even toady.

Recall that the q-analogs of the binomial coefficients, the so-called Gaussian polynomials are denoted by

[{m \atop n}],

and defined by

[{m \atop n}] := \frac{(1 − q^{m−n+1})...(1 − q^{m})}{(1 − q)...(1 − q^{n})} .

Theorem([MRR1]): Let ω be a primitive cubic root of unity, and let

a_{i,j} := δ_{i,j} + ωq^{i−1}[{i + j − 2 \atop j − 1}] ,

with the above notation for d(m)

\frac{d(m)}{d(m − 1)} = \frac{(1 − ω^{2}q^{m−1})[{3m−2 \atop m−1}]}{(1 − ωq^{m−1})[{2m−2 \atop m−1}]} .

Proof(1990 version of the proof in [MRR1]): Introduce

V (α, β)_{j} := q^{j(m−1)+β)}[{m − 2 + j \atop j − α}][{2m − 2 − j \atop m − β − j}] ,

L_{j} := V (0, 2)_{j} + ωV (0, 0)_{j} + ω^{2}V (2, 0) ,

and, finally,

C_{j}^{(m)} := ω^{−1} ∑_{i=1}^{m} q^{j(1−m)}[{−m + i − j \atop i − j}]L_{i} ,

e(m) := \frac{(1 + ω)(1 − ω^{2}q^{m−1})(1 − q^{m−1})}{(1 − ωq^{m−1})(1 − q^{m})[{3m−2 \atop m−1}]} ,

f(m) := [{2m − 2 \atop m − 1}] .

(i),(ii),(iii) are routinely provable[Z4], and indeed were proved, by my computer, Shalosh B. Ekhad. The theorem follows by the above general remarks. QED