A High-Tech Proof of the Mills-Robbins-Rumsey Determinant Formula

Marko Petkovšek and Herbert S. Wilf^{1} Submitted: MArch 14, 1995; Accepted: October 3, 1995

Dedicated to Dominique Foata on his sixtieth birthday

The formula in question states that

det (\binom{i + j + μ}{2i − j}_{i,j=0}^{n−1} ) = 2^{−n} ∏_{k=0}^{n−1} Δ_{2k}(2μ),  (1)

where μ is an indeterminate, Δ_{0}(μ) = 2 and for j = 1, 2, …,

Δ_{2j}(μ) = \frac{(μ + 2j + 2)_{j}(\frac{1}{2}μ + 2j + \frac{3}{2})_{j−1}}{(j)_{j}(\frac{1}{2}μ + j + \frac{3}{2})_{j−1}} ,  (2)

with (x)_{j} = x(x + 1) ⋯ (x + j − 1) being the usual rising factorial.

The evaluation (1) was found by Mills, Robbins and Rumsey [3] in connection with some of their work on plane partitions. Their original proof was “quite complicated.” In [1], George Andrews gave another proof. The main idea of his proof was to exhibit a triangular matrix E_{n}, with 1’s on the diagonal, for which M_{n}E_{n} is triangular, where M_{n} is the matrix on the left side of (1). He then showed that the diagonal entries of M_{n}E_{n} were indeed the Δ’s of (2) above, proving the theorem.

For further developments in the theory of this interesting determinant see Andrews and Burge [2]. For the combinatorial context in which determinants such as (1) arise, see the article [6] of Robbins. Zeilberger’s algorithm, which we used to prove this result, is in [7]. The particular implementation of it that we used, due to Peter Paule and Markus Schorn, is described in [4]. A discussion of the whole field of computer proofs of identities is in the book [5].

Though the idea was beautiful and simple, its execution was anything but. Indeed, the proofs of the triangularity of the product and of the nature of its diagonal entries required an argument that proved, by twenty simultaneous inductions, twenty formidable hypergeometric identities!

We give here a short computer-assisted proof. This proof is conceptually very simple. The intrinsic depth of the problem is reflected only in the very large polynomial that is contained in the proof certificate.

The Proof

The triangularizing matrix that Andrews discovered is the matrix E_{n} = (e_{i,j}(μ))_{i,j=0}^{n−1}, where e_{i,j} = 0 if i > j, and

e_{i,j}(μ) = \frac{1}{(−4)^{j−i}} \frac{(2j − i − 1)!(2μ + 3j + 1)!(μ + i)!(μ + i + j − \frac{1}{2})!}{(j − i)!(i − 1)!(2μ + 2j + i + 1)!(μ + j)!(μ + 2j − \frac{1}{2})!},  (3)

otherwise. E_{n} is an upper triangular matrix with unit diagonal. Define L_{n} = M_{n}E_{n}. We show first that L_{n} is lower triangular by writing (L_{n})_{i,j} = ∑_{k} F (i, j, k, μ) and calling Zeilberger’s algorithm. If we abbreviate (L_{n})_{i,j} by f(i), then that algorithm returns the recurrence

\begin{matrix}(2 + i + μ) (−i + 2 j + μ) (1 + i + 2 j + μ) f(i) \\ + 2 (−12 − 26 i − 18 i^{2} − 4 i^{3} + 11 j + 5 i j + 22 j^{2} + 10 i j^{2} − 7 i μ \\ − 4 i^{2} μ + 26 j μ + 10 i j μ + 8 j^{2} μ + 7 μ^{2} + 2 i μ^{2} + 8 j μ^{2} + 2 μ^{3}) f(i + 1) \\ + 4 (3 + 2 i) (−2 − i + j) (5 + 2 i + 2 j + 2 μ) f(i + 2) = 0 \end{matrix} (4)

1 Supported in part by the Office of Naval Research of order 2 that f satisfies. Because of the indeterminacy in the formula (3) when i ≥ 2j, this recurrence for f(i) is valid only for i < 2j, but we need it only for i < j.

The recurrence (4) is certified by^{2} the rational function

R_{1}(i, k) = \frac{(k−1)(k−2j)(2k+μ−i−1)(−i+2k+μ)(1+2j+k+2μ)(−4−2i+16k+9ik+10μ+6iμ+3kμ+2μ^{2})}{(−4−2i+k)(−3−2i+k)(−2−2i+k)(−1−2i+k)}.

From (4), to prove that L_{n} is lower triangular we fix some column j. It is easy to check that f(0) and f(1) vanish. But then (4) tells us that f(i + 2) vanishes as long as its coefficient in (4) is not zero, i.e., as long as i ≤ j − 3.

It remains to establish that the ith diagonal entry of L_{n} is \frac{1}{2}Δ_{2i}(2μ), and this is harder, even for computers. This assertion is identical with the statement that dd(i) =^{def} ∑_{k} F F (i, k, μ) = 1 for all i, μ, where F F (i, k, μ) is

\frac{2(2μ + 2i + 1)!(μ + 2i + \frac{1}{2})!(2i − 1)!(μ + i + k)!(−1)^{i−k}(μ + k)!(μ + k + i − \frac{1}{2})!}{(2i − k)(μ − i + 2k)!(μ + 3i − \frac{1}{2})!(i − 1)!(μ + i + \frac{1}{2})!(k − 1)!(2μ + 2i + k + 1)!4^{i−k}(i − k)!(μ + i)!}. (5)

We call Zeilberger’s algorithm once more (using the implementation by Peter Paule and Markus Schorn) and it returns a recurrence of order 2 that is satisfied by the sums dd(i). That recurrence is

p(i) dd(i) − (p(i) + q(i)) dd(i + 1) + q(i) dd(i + 2) = 0  (6)

where

p(i) = (1 + 2 i) (1 + 3 i + μ) (2 + 3 i + μ) (3 + 3 i + μ) (3 + 4 i + 2 μ) (5 + 4 i + 2 μ) r(i + 1),
q(i) = (5 + 3 i + 2 μ) (6 + 3 i + 2 μ) (7 + 3 i + 2 μ) (7 + 6 i + 2 μ) (9 + 6 i + 2 μ) (11 + 6 i + 2 μ) r(i),
r(i) = 354 + 1808 i + 3394 i^{2} + 2772 i^{3} + 828 i^{4} + 791 μ + 3021 i μ + 3762 i^{2} μ + 1524 i^{3} μ
+ 655 μ^{2} + 1660 i μ^{2} + 1028 i^{2} μ^{2} + 238 μ^{3} + 300 i μ^{3} + 32 μ^{4}.

This recurrence is certified by^{2} a rational function R_{2}(i, k) whose numerator is of the form

(1 + 2i)(−1 + k)(−2i + k)(−1 − i + 2k + μ)(−i + 2k + μ)(3 + 4i + 2μ)(5 + 4i + 2μ)P_{15}(i, k, μ),

where P_{15} is a certain (quite unpleasantly large) polynomial of degree 15 in its arguments, and whose denominator is

\begin{matrix}(−4 − 2i + k)(−3 − 2i + k)(−2 − 2i + k)(−1 − 2i + k)(−2 − i + k)(−1 − i + k)(1 + 6i + 2μ)× \\ (3 + 6i + 2μ)(5 + 6i + 2μ)(2 + 2i + k + 2μ)(3 + 2i + k + 2μ)(4 + 2i + k + 2μ). \end{matrix}

The polynomial P_{15} is in the “Comments” file associated with this paper. Hence any reader who wishes to do so can cut-and-paste it from there and verify that it does indeed certify the recurrence. It can also be computed by using the Paule-Schorn implementation of Zeilberger’s algorithm.

To verify that the diagonal entries are as required we need to check that dd(0) = dd(1) = 1, both of which are trivial, and then check that the recurrence (6) admits only the solution dd(i) = 1. This will surely be true unless the coefficient q(i) of the term dd(i + 2) should vanish for some nonnegative integer i. Now q(i) is given above in completely factored form over the field of rational numbers. (We rely on our computer algebra systems for the truth of this fact.) Since we see no linear factors of the form ai + b with rational a and b, q(i) has no rational zeros. Note that being an indeterminate, μ is transcendental over the rationals.

A note on certification. We quickly review here the meaning of an assertion of the form “The recurrence xxx is certified by the rational function R(n, k).” Suppose we are interested in a sum f(n) = ∑_{k} F (n, k), and we assert that the sum f(n) satisfies a recurrence L_{n}f(n) = 0, where L_{n} is some linear difference operator

2 See “A note on certification” below. in n with polynomial coefficients. To certify such an assertion by giving a rational function R(n, k) means precisely the following. Write out the equation

L_{n}F (n, k) = G(n, k + 1) − G(n, k),  (7)

where F is the given summand and G = RF. This equation can now be routinely (though possibly tediously) checked because it does not involve any summation. Hence one can cancel out all of the factorials in it and verify the polynomial identity that remains. Having verified (7), we can sum it over all integer k, provided that F either has finite support or vanishes at ±∞, and immediately find that f(n) does indeed satisfy the claimed recurrence L_{n}f(n) = 0. Hence the rational function R(n, k), by itself, implicitly contains the complete proof.

References

1. George E. Andrews, Pfaff’s method (I): The Mills-Robbins-Rumsey determinant, preprint, 1993.

2. G. E. Andrews and W. H. Burge, Determinant identities, Pacific J. Math. 158 (1993), 1-14.

3. W. H. Mills, D. P. Robbins and H. Rumsey, Enumeration of a symmetry class of plane partitions, Discrete Math. 67 (1987), 43-55.

4. P. Paule and M. Schorn, A Mathematica Version of Zeilberger’s Algorithm for Proving Binomial Coefficient Identities, RISC-Linz Report Series 93-36, J. Kepler University, Linz (1993).

5. Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger, A = B, A. K. Peters, Wellesley, MA, 1995 (to appear).

6. David P. Robbins, The story of 1, 2, 7, 42, 429, 7436, …, The Mathematical Intelligencer 13 (1991), 12–19.

7. Doron Zeilberger, The method of creative telescoping, J. Symbolic Comp. 11 (1991), 195-204.

University of Ljubljana, 61111 Ljubljana, Slovenia University of Pennsylvania, Philadelphia, PA 19104-6395, USA