DETERMINANT IDENTITIES AND A GENERALIZATION

OF THE NUMBER OF TOTALLY SYMMETRIC

SELF-COMPLEMENTARY PLANE PARTITIONS

C. Krattenthaler^{†}

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria. e-mail: KRATT@Pap.Univie.Ac.At

      WWW: http://radon.mat.univie.ac.at/People/kratt

Submitted: September 16, 1997; Accepted: November 3, 1997

Abstract. We prove a constant term conjecture of Robbins and Zeilberger (J. Combin. Theory Ser. A 66 (1994), 17–27), by translating the problem into a determinant evaluation problem and evaluating the determinant. This determinant generalizes the determinant that gives the number of all totally symmetric self-complementary plane partitions contained in a (2n)×(2n)×(2n) box and that was used by Andrews (J. Combin. Theory Ser. A 66 (1994), 28–39) and Andrews and Burge (Pacific J. Math. 158 (1993), 1–14) to compute this number explicitly. The evaluation of the generalized determinant is independent of Andrews and Burge’s computations, and therefore in particular constitutes a new solution to this famous enumeration problem. We also evaluate a related determinant, thus generalizing another determinant identity of Andrews and Burge (loc. cit.). By translating some of our determinant identities into constant term identities, we obtain several new constant term identities.

1. Introduction. I started work on this paper originally hoping to find a proof of the following conjecture of Robbins and Zeilberger [16, Conjecture C’=B’] (caution: in the quotient defining B′ it should read (m + 1 + 2j) instead of (m + 1 + j)), which we state in an equivalent form.

1991 Mathematics Subject Classification. Primary 05A15, 15A15; Secondary 05A17, 33C20.. Key words and phrases. determinant evaluations, constant term identities, totally symmetric

self-complementary plane partitions, hypergeometric series. †Supported in part by EC’s Human Capital and Mobility Program, grant CHRX-CT93-0400 and the Austrian Science Foundation FWF, grant P10191-MAT

Typeset by AMS-TEX

Conjecture. Let x and n be nonnegative integers. Then

CT (\frac{∏_{0≤i<j≤n−1}(1 − z_{i}/z_{j}) ∏_{i=0}^{n−1}(1 + z_{i}^{−1})^{x+n−i−1}}{∏_{0≤i<j≤n−1}(1 − z_{i}z_{j}) ∏_{i=0}^{n−1}(1 − z_{i})} )

= \{ \begin{matrix}∏_{i=0}^{n−1} \frac{(3x+3i+1)!}{(3x+2i+1)! (x+2i)!} ∏_{i=0}^{(n−2)/2}(2x + 2i + 1)! (2i)! & if n is even  (1.1a) \\ 2^{x} ∏_{i=1}^{n−1} \frac{(3x+3i+1)!}{(3x+2i+1)! (x+2i)!} ∏_{i=1}^{(n−1)/2}(2x + 2i)! (2i − 1)! & if n is odd.  (1.1b) \end{matrix}

Here, CT(Expr) means the constant term in Expr, i.e., the coefficient of z_{1}^{0}z_{2}^{0} ⋯ z_{n}^{0} in Expr.

I thought this might be a rather boring task since in the case x = 0 there existed already a proof of the Conjecture (see [16]). This proof consists of translating the constant term on the left-hand side of (1.1) into a sum of minors of a particular matrix (by a result [16, Corollary D=C] of Zeilberger), which is known to equal the number of totally symmetric self-complementary plane partitions contained in a (2n)×(2n)×(2n) box (by a result of Doran [4, Theorem 4.1 + Proof 2 of Theorem 5.1]). The number of these plane partitions had been calculated by Andrews [1] by transforming the sum of minors into a single determinant (using a result of Stembridge [15, Theorem 3.1, Theorem 8.3]) and evaluating the determinant. Since Zeilberger shows in [16, Lemma D’=C’] that the translation of the constant term in (1.1) into a sum of minors of some matrix works for generic x, and since Stembridge’s result [15, Theorem 3.1] still applies to obtain a single determinant (see (2.2)), my idea was to evaluate this determinant by routinely extending Andrews’s proof of the totally symmetric selfcomplementary plane partitions conjecture, or the alternative proofs by Andrews and Burge [2]. However, it became clear rather quickly that this is not possible (at least not routinely). In fact, the aforementioned proofs take advantage of a few remarkable coincidences, which break down if x is nonzero. Therefore I had to devise new methods and tools to solve the determinant problem in this more general case where x ≠ 0.

In the course of the work on the problem, the subject became more and more exciting as I came across an increasing number of interesting determinants that could be evaluated, thus generalizing several determinant identities of Andrews and Burge [2], which appeared in connection with the enumeration of totally symmetric selfcomplementary plane partitions. In the end, I had found a proof of the Conjecture, but also many more interesting results. In this paper, I describe this proof and all further results.

The proof of the Conjecture will be organized as follows. In Theorem 1, item (3) in Section 1 it is proved that the constant term in (1.1) equals the positive square root of a certain determinant, actually of one determinant, namely (2.2a), if n is even, and of another determinant, namely (2.2b), if n is odd. In addition, Theorem 1 provides two more equivalent interpretations of the constant term, in particular a combinatorial interpretation in terms of shifted plane partitions, which reduces to totally symmetric self-complementary plane partitions for x = 0.

The main idea that we will use to evaluate the determinants in Theorem 1 will be to generalize them by introducing a further parameter, y, see (3.1) and (4.1). The generalized determinants reduce to the determinants of Theorem 1 when y = x. Many of our arguments do not work without this generalization. In Section 3 we study the two-parameter family (3.1) of determinants that contains (2.2a) as special case. If y = x + m, with m a fixed integer, Theorem 2 makes it possible to evaluate the resulting determinants. This is done for a few cases in Corollary 3, including the case y = x (see (3.69)) that we are particularly interested in. Similarly, in Section 4 we study the two-parameter family (4.1) of determinants that contains (2.2b) as special case. Also here, if y = x + m, with m a fixed integer, Proposition 5 makes it possible to evaluate the resulting determinants. This is done for two cases in Corollary 6, including the case y = x (see (4.42)) that we are particularly interested in. This concludes the proof of the Conjecture, which thus becomes a theorem. It is restated as such in Theorem 11. However, even more is possible for this second family of determinants. In Theorem 8, we succeed in evaluating the determinants (4.1) for independent x and y, taking advantage of all previous results in Section 4.

There is another interesting determinant identity, which is related to the aforementioned determinant identities. This is the subject of Section 5. It generalizes a determinant identity of Andrews and Burge [2]. Finally, in Section 6 we translate our determinant identities of Sections 4 and 5 into constant term identities which seem to be new. Auxiliary results that are needed in the proofs of our Theorems are collected in the Appendix.

Since a first version of this article was written, q-analogues of two of the determinant evaluations in this article, Theorems 8 and 10, were found in [9]. No q-analogues are known for the results in Section 3. Also, it is still open whether the q-analogues of [9] have any combinatorial meaning. Another interesting development is that Amdeberhan (private communication) observed that Dodgson’s determinant formula (see [18, 17]) can be used to give a short inductive proof of the determinant evaluation in Theorem 10 (and also of its q-analogue in [9]), and could also be used to give an inductive proof of the determinant evaluation in Theorem 8 (and its q-analogue in [9]) provided one is able to prove a certain identity featuring three double summations.

2. Transformation of the Conjecture into a determinant evaluation problem. In Theorem 1 below we show that the constant term in (1.1) equals the positive square root of some determinant, one if n is even, another if n is odd. Also, we provide a combinatorial interpretation of the constant term in terms of shifted plane partitions. Recall that a shifted plane partition of shape (λ_{1}, λ_{2}, …, λ_{r}) is an array π of integers of the form

π_{1,1} π_{1,2} π_{1,3} . . . . . . . . . . . . . . . . . . . . . . . . . . . π_{1,λ_{1}}
π_{2,2} π_{2,3} . . . . . . . . . . . . . . . . . . . . π_{2,λ_{2}}
...  ⋮  ...
π_{r,r} … π_{r,λ_{r}}

such that the rows and columns are weakly decreasing. Curiously enough, we need this combinatorial interpretation to know that we have to choose the positive root once the determinant is evaluated.

Theorem 1. Let x and n be nonnegative integers. The constant term in (1.1) equals (1) the sum of all n × n minors of the n × (2n − 1) matrix

(\binom{x + i}{j − i})_{0≤i≤n−1, 0≤j≤2n+x−2} ,  (2.1)

(2) the number of shifted plane partitions of shape (x + n − 1, x + n − 2, …, 1), with entries between 0 and n, where the entries in row i are at least n − i, i = 1, 2, …, n − 1,

(3) the positive square root of

det_{0≤i,j≤n−1} ( ∑_{x+2i−j<r≤x+2j−i} \binom{2x+i+j}{r})  if n is even, (2.2a)
2^{2x} det_{0≤i,j≤n−2} (\frac{(2x+i+j+1)! (3x+3i+4)(3x+3j+4)(3j−3i)}{(x+2i−j+2)! (x+2j−i+2)!}) if n is odd, (2.2b)

if the sums in (2.2a) are interpreted by

∑_{r=A+1}^{B} Expr(r) = \{ \begin{matrix}∑_{r=A+1}^{B} Expr(r) & A < B \\ 0 & A = B \\ − ∑_{r=B+1}^{A} Expr(r) & A > B. \end{matrix}  (2.3)

Proof. ad (1). This was proved by Zeilberger [16, Lemma D’=C’]. (Note that we have performed a shift of the indices i, j in comparison with Zeilberger’s notation.)

ad (2). Fix a minor of the matrix (2.1),

det_{0≤i,j≤n−1} (\binom{x + i}{λ_{j} − i})

say. By the main theorem of nonintersecting lattice paths [6, Cor. 2; 15, Theorem 1.2] (see Proposition A1) this determinant has an interpretation in terms of nonintersecting lattice paths. By a lattice path we mean a lattice path in the plane consisting of unit horizontal and vertical steps in the positive direction. Furthermore, recall that a family of paths is called nonintersecting if no two paths of the family have a point in common. Now, the above determinant equals the number of all families (P_{0}, P_{1}, …, P_{n−1}) of nonintersecting lattice paths, where P_{i} runs from (−2i, i) to (x−λ_{i}, λ_{i}), i = 0, 1, …, n−1. An example with x = 2, n = 5, λ_{1} = 1, λ_{2} = 3, λ_{3} = 4, λ_{4} = 7, λ_{5} = 9 is displayed in Figure 1.a. (Ignore P_{−1} for the moment.)

Hence, we see that the sum of all minors of the matrix (2.1) equals the number of all families (P_{0}, P_{1}, …, P_{n−1}) of nonintersecting lattice paths, where P_{i} runs from (−2i, i) to some point on the antidiagonal line x_{1} +x_{2} = x (x_{1} denoting the horizontal coordinate, x_{2} denoting the vertical coordinate), i = 0, 1, …, n − 1. Next, given such

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; x_{1}; x_{2}; P_{−1}; P_{0}; P_{1}; P_{2}; P_{3}; P_{4}; x_{1} + x_{2} = x]

a. nonintersecting lattice paths

⟶
[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; x_{1}; x_{2}; P′_{0}; P′_{1}; P′_{2}; P′_{3}; P′_{4}; x_{1} + x_{2} = x]

b. noncrossing lattice paths

5 5 5 5 4 4
4 3 3 3 3
3 3 3 2
3 1 1
1 1

0

d. shifted plane partition

⟵

[figure: •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; •; 0; 1; 1; 1; 1; 2; 3; 3; 3; 3; 3; 3; 3; 3; 4; 4; 4; 5; 5; 5; 5]

c. filling of the regions

Figure 1

a family (P_{0}, P_{1}, …, P_{n−1}) of nonintersecting lattice paths, we shift P_{i} by the vector (i, −i), i = 0, 1, …, n−1. Thus a family (P′_{0}, P′_{1}, …, P′_{n−1}) of lattice paths is obtained, where P′_{i} runs from (−i, 0) to some point on the line x_{1} + x_{2} = x, see Figure 1.b. The new paths may touch each other, but they cannot cross each other. Therefore, the paths P′_{0}, P′_{1}, …, P′_{n−1} cut the triangle that is bordered by the x_{1}-axes, the line x_{1} + x_{2} = x, the vertical line x_{1} = −n + 1 into exactly n + 1 regions. We fill these regions with integers as is exemplified in Figure 1.c. To be more precise, the region to the right of P′_{0} is filled with 0’s, the region between P′_{0} and P′_{1} is filled with 1’s, …, the region between P′_{n−2} and P′_{n−1} is filled with (n − 1)’s, and the region to the left of P′_{n−1} is filled with n’s. Finally, we forget about the paths and reflect the array of integers just obtained in an antidiagonal line, see Figure 1.d. Clearly, a shifted plane partition of shape (x+n−1, x+n−2, …, 1) is obtained. Moreover, it has the desired property that the entries in row i are at least n − i, i = 1, 2, …, n − 1. It is easy to see that each step can be reversed, which completes the proof of (2).

ad (3). It was proved just before that the constant term in (1.1) equals the number of all families (P_{0}, P_{1}, …, P_{n−1}) of nonintersecting lattice paths, where P_{i} runs from (−2i, i) to some point on the antidiagonal line x_{1} + x_{2} = x, i = 0, 1, …, n − 1.

Now, let first n be even. By a theorem of Stembridge [15, Theorem 3.1] (see Proposition A2, with A_{i} = (−2i, i), i = 0, 1, …, n − 1, I = (the lattice points on the line x_{1} + x_{2} = x)), the number of such families of nonintersecting lattice paths equals the Pfaffian

Pf_{0≤i<j≤n−1} (Q(i, j)),  (2.4)

where Q(i, j) is the number of all pairs (P_{i}, P_{j}) of nonintersecting lattice paths, P_{i} running from (−2i, i) to some point on the line x_{1} + x_{2} = x, and P_{j} running from (−2j, j) to some point on the line x_{1} + x_{2} = x.

In order to compute the number Q(i, j) for fixed i, j, 0 ≤ i < j ≤ n − 1, we follow Stembridge’s computation in the proof of Theorem 8.3 in [15]. We define b_{kl} to be the number of all pairs (P_{i}, P_{j}) of intersecting lattice paths, where P_{i} runs from (−2i, i) to (x − k, k), and where P_{j} runs from (−2j, j) to (x − l, l). Since the total number of lattice paths from (−2i, i) to x_{1} +x_{2} = x is 2^{x+i}, it follows that 2^{2x+i+j} −Q(i, j) is the number of pairs of intersecting lattice paths from (−2i, i) and (−2j, j) to x_{1} +x_{2} = x. Hence,

2^{2x+i+j} − Q(i, j) = ∑_{k,l} b_{kl} = ∑_{k<l} b_{lk} + ∑_{k≥l} b_{lk},

the last equality being a consequence of the fact that b_{kl} = b_{lk}, which is proved by the standard path switching argument (find the first meeting point and interchange terminal portions of the paths from thereon, see the proofs of [6, Cor. 2; 15, Theorem 1.2]). When k ≤ l, every path from (−2i, i) to (x − l, l) must intersect every path from (−2j, j) to (x − k, k), so we have b_{kl} = \binom{x+i}{l−i}\binom{x+j}{k−j}. Thus,

2^{2x+i+j} − Q(i, j) = ∑_{0≤k<l≤x+2i−j} \binom{x + i}{l + j − i}\binom{x + j}{k}

+ ∑_{0≤k≤l≤x+2i−j} \binom{x + i}{l + j − i}\binom{x + j}{k}.

Now we replace l by x + 2i − j − l in the first sum and k by x + 2i − j − k in the second sum. This leads to

2^{2x+i+j} − Q(i, j) = ∑_{k+l<x+2i−j} \binom{x + i}{l}\binom{x + j}{k}

+ ∑_{k+l≥x+2i−j} \binom{x + i}{l + j − i}\binom{x + j}{k + 2j − 2i}.

For fixed values of r = k + l both sums can be simplified further by the Vandermonde sum (see e.g. [7, sec. 5.1, (5.27)]), so

2^{2x+i+j} − Q(i, j) = ∑_{r<x+2i−j} \binom{2x + i + j}{r} + ∑_{r≥x+2i−j} \binom{2x + i + j}{r + 3j − 3i},

and finally, after replacement of r by 2x+i+j−r in the first sum, and by 2x+4i−2j−r in the second sum,

Q(i, j) = 2^{2x+i+j} − ∑_{r>x+2j−i} \binom{2x + i + j}{r} − ∑_{r≤x+2i−j} \binom{2x + i + j}{r}

= ∑_{x+2i−j<r≤x+2j−i} \binom{2x + i + j}{r}.  (2.5)

As is well-known, the square of a Pfaffian equals the determinant of the corresponding skew-symmetric matrix (see e.g. [15, Prop. 2.2]). The quantity Q(i, j), as given by (2.5), has the property Q(i, j) = −Q(j, i), due to our interpretation (2.3) of limits of sums. Hence, the square of the Pfaffian in (2.4) equals det_{0≤i<j≤n−1} (Q(i, j)), which in view of (2.5) is exactly (2.2a). That the Pfaffian itself is the positive square root of the determinant is due to the combinatorial interpretation in item (2) of the Theorem. Thus, item (3) is established for even n.

Now let n be odd. Still, by the proof of (2), the constant term in (1.1) equals the number of all families (P_{0}, P_{1}, …, P_{n−1}) of nonintersecting lattice paths, where P_{i} runs from (−2i, i) to some point on the antidiagonal line x_{1}+x_{2} = x, i = 0, 1, …, n−1. However, to apply Theorem 3.1 of [15] again we have to add a “dummy path” P_{−1} of length 0, running from (2x, −x) to (2x, −x), say (cf. the Remark after Theorem 3.1 in [15]; however, we order all paths after the dummy path). See Figure 1.a for the location of P_{−1}. We infer that the constant term in (1.1) equals

Pf_{−1≤i<j≤n−1} (Q(i, j)),  (2.6)

where Q(i, j) is the number of all pairs (P_{i}, P_{j}) of nonintersecting lattice paths, P_{i} running from (−2i, i) to the line x_{1} + x_{2} = x if i ≥ 0, P_{−1} running from (2x, −x) to x_{1} +x_{2} = x (hence, to (2x, −x)), and P_{j} running from (−2j, j) to the line x_{1} +x_{2} = x. If 0 ≤ i < j ≤ n − 1, then Q(i, j) = ∑_{x+2i−j<r≤x+2j−i} \binom{2x+i+j}{r} according to the computation that led to (2.5). Moreover, we have Q(−1, j) = 2^{x+j} since a pair (P_{−1}, P_{j}) is nonintersecting for any path P_{j} running from (−2j, j) to x_{1} + x_{2} = x. The latter fact is due to the location of P_{−1}, see Figure 1.a. Therefore, the square of the Pfaffian in (2.6) equals

det_{−1≤i,j≤n−1} (............................................................ . . . . .. . . . .. . . . .. . . . . 0 −2^{x+i}  2^{x+j}_{∑_{x+2i−j<r≤x+2j−i} \binom{2x+i+j}{r}}  i = −1 i ≥ 0 ) . j = −1  j ≥ 0  (2.7)

We subtract 2 times the (j − 1)-st column from the j-th column, j = n − 1, n − 2, …, 2, in this order, and we subtract 2 times the (i − 1)-st row from the i-th row, i = n − 1, n − 2, …, 2. Thus, by simple algebra, the determinant in (2.7) is turned into

det_{−1≤i,j≤n−1} (^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....}^{.....} . . . . .. . . . .. . . . .. . . . .. . . . .  . . . . .. . . . .. . . . .. . . . .. . . . . 0  0 ^{. . . . . . . . . . . . . . . . . . . . .} 0 0⋮0 −2^{x} 2^{x} ∗  ∗ ^{. . . . . . . . . . . . . . . . . . . . .} ∗ ∗⋮∗ _{\frac{(2x+i+j−1)! (3x+3i+1)(3x+3j+1)(3j−3i)}{(x+2i−j+1)! (x+2j−i+1)!}}  i=−1 i=0 i≥1 ) . j =−1 j =0  j ≥1

(2.8)

By expanding this determinant along the top row, and the resulting determinant along the left-most column, we arrive at (2.2b), upon rescaling row and column indices.

Thus the proof of Theorem 1 is complete. □

Remark. Mills, Robbins and Rumsey [10, Theorem 1 + last paragraph of p. 281] showed that shifted plane partitions of shape (n−1, n−2, …, 1), where the entries in row i are at least n − i and at most n, i = 1, 2, …, n − 1, are in bijection with totally symmetric self-complementary plane partitions contained in a (2n) × (2n) × (2n) box. Hence, by item (2) of Theorem 1, the number (1.1) generalizes the number of these plane partitions, to which it reduces for x = 0.

The idea that is used in the translation of item (1) into item (2) of Theorem 1 is due to Doran [4, Proof of Theorem 4.1], who did this translation for x = 0. However, our presentation is modelled after Stembridge’s presentation of Doran’s idea in [15, Proof of Theorem 8.3].

3. A two-parameter family of determinants. The goal of this section is to evaluate the determinant in (2.2a). We shall even consider the generalized determinant

D(x, y; n) := det_{0≤i,j≤n−1} ( ∑_{x+2i−j<r≤y+2j−i} \binom{x + y + i + j}{r}),  (3.1)

for integral x and y, which reduces to (2.2a) when y = x. In fact, many of our arguments essentially require this generalization and would not work without it. Recall that the sums in (3.1) have to be interpreted according to (2.3).

The main result of this section, Theorem 2 below, allows to evaluate D(x, y; n) when the difference m = y − x is fixed. It is done explicitly for a number of cases in the subsequent Corollary 3, including the case m = 0 which gives the evaluation of (2.2a) that we are particularly interested in. For the sake of brevity, Theorem 2 is formulated only for y ≥ x (i.e., for m ≥ 0). The corresponding result for y ≤ x is easily obtained by taking advantage of the fact

D(x, y; n) = (−1)^{n}D(y, x; n),  (3.2)

which results from transposing the matrix in (3.1) and using (2.3).

Theorem 2. Let x, m, n be nonnegative integers with m ≤ n. Then, with the usual notation (a)_{k} := a(a + 1) ⋯ (a + k − 1), k ≥ 1, (a)_{0} := 1, of shifted factorials, there holds

D(x, x + m; n) = det_{0≤i,j≤n−1} ( ∑_{x+2i−j<r≤x+m+2j−i} \binom{2x + m + i + j}{r})

= ∏_{i=1}^{n−1} (\frac{(2x + m + i)! (3x + m + 2i + 2)_{i} (3x + 2m + 2i + 2)_{i}}{(x + 2i)! (x + m + 2i)!} )

× \frac{(2x + m)!}{(x + ⌊m/2⌋)! (x + m)!} · ∏_{i=0}^{⌊n/2⌋−1}(2x + 2 ⌈m/2⌉ + 2i + 1) · P_{1}(x; m, n), (3.3)

where P_{1}(x; m, n) is a polynomial in x of degree ≤ ⌊m/2⌋. If n is odd and m is even, the polynomial P_{1}(x; m, n) is divisible by (2x + m + n). For fixed m, the polynomial P_{1}(x; m, n) can be computed explicitly by specializing x to − ⌊(m + n)/2⌋+t−1/2, t = 0, 1, …, ⌊m/2⌋, in the identity (3.67). This makes sense since for these specializations the determinant in (3.67) reduces to a determinant of size at most 2t + 1, as is elaborated in Step 6 of the proof, and since a polynomial of degree ≤ ⌊m/2⌋ is uniquely determined by its values at ⌊m/2⌋ + 1 distinct points.

Proof. The proof is divided into several steps. Our strategy is to transform D(x, x + m; n) into a multiple of another determinant, namely D_{B}(x, x + m; n), by (3.6), (3.8) and (3.10), which is a polynomial in x, then identify as many factors of the new determinant as possible (as a polynomial in x), and finally find a bound for the degree of the remaining polynomial factor.

For big parts of the proof we shall write y for x+m. We feel that this makes things more transparent.

Step 1. Equivalent expressions for D(x, y; n). First, in the definition (3.1) of D(x, y; n) we subtract 2 times the (j − 1)-st column from the j-th column, j = n − 1, n − 2, …, 1, in this order, and we subtract 2 times the (i − 1)-st row from the i-th row, i = n − 1, n − 2, …, 1. By simple algebra we get

D(x, y; n)

= det_{0≤i,j≤n−1}(..................................................................................... . . . . .. . . . .. . . . .. . . . .^{∑_{x<r≤y} \binom{x+y}{r}}  ^{\frac{(x+y+j)! (x+2y+3j+1)}{(x−j+1)! (y+2j)!}} −\frac{(x+y+i)! (2x+y+3i+1)}{(x+2i)! (y−i+1)!} _{\frac{(x+y+i+j−1)! (y−x+3j−3i)}{(x+2i−j+1)! (y+2j−i+1)!}}_{×(2x+y+3i+1)(x+2y+3j+1)}  i=0 i≥1 ) . j =0  j ≥1  (3.4)

On the other hand, if in the definition (3.1) of D(x, y; n) we subtract 1/2 times the (j + 1)-st column from the j-th column, j = 0, 1 …, n − 2, in this order, and if we subtract 1/2 times the (i + 1)-st row from the i-th row, i = 0, 1, …, n − 2, we get

D(x, y; n)

= det_{0≤i,j≤n−1}( ..................................................................................... . . . . .. . . . .. . . . .. . . . .^{\frac{1}{4} \frac{(x+y+i+j+1)! (y−x+3j−3i)}{(x+2i−j+2)! (y+2j−i+2)!}}^{×(2x+y+3i+4)(x+2y+3j+4)}  ^{\frac{1}{2} \frac{(x+y+i+n)! (2x+y+3i+4)}{(x+2i−n+3)! (y+2n−i−2)!}} −\frac{1}{2} \frac{(x+y+j+n)! (x+2y+3j+4)}{(x+2n−j−2)! (y+2j−n+3)!} _{∑_{x+n−1<r≤y+n−1} \binom{x+y+2n−2}{r}}  i≤n−2 i=n−1 ) . j ≤n−2  j =n−1  (3.5)

Step 2. An equivalent statement of the Theorem. We consider the expression (3.4). We take as many common factors out of the i-th row, i = 0, 1, …, n − 1, as possible, such that the entries become polynomials in x and y. To be precise, we take

\frac{(x + y + i)! (2x + y + 3i + 1)}{(x + 2i)! (y + 2n − i − 1)!}

out of the i-th row, i = 1, 2, …, n − 1, and we take

\frac{(x + y)!}{⌊(x + y)/2⌋! (y + 2n − 2)!}

out of the 0-th row. Furthermore, we take (x + 2y + 3j + 1) out of the j-th column, j = 1, 2, …, n − 1. This gives

D(x, y; n)

= \frac{(x + y)!}{⌊(x + y)/2⌋! (y + 2n − 2)!} ∏_{i=1}^{n−1} \frac{(x + y + i)! (2x + y + 3i + 1) (x + 2y + 3i + 1)}{(x + 2i)! (y + 2n − i − 1)!}

× det_{0≤i,j≤n−1}(........................................................................... . . . . .. . . . .. . . . .. . . . . S(x, y; n)  ^{(x+y+1)_{j} (x−j+2)_{⌊(y−x)/2⌋+j−1}}^{×(y+2j+1)_{2n−2j−2}}_{−(y−i+2)_{2n−2}}  _{(x+y+i+1)_{j−1} (x+2i−j+2)_{j−1}}_{×(y+2j−i+2)_{2n−2j−2} (y−x+3j−3i)}  i=0 i≥1 ) , j =0  j ≥1  (3.6)

where S(x, y; n) is given by

S(x, y; n) = ∑_{r=1}^{⌊(y−x)/2⌋}(x + r + 1)_{⌊(y−x)/2⌋−r} (y − r + 1)_{2n+r−2}

+ ∑_{r=0}^{⌈(y−x)/2⌉−1}(x + r + 1)_{⌊(y−x)/2⌋−r} (y − r + 1)_{2n+r−2}. (3.7)

For convenience, let us denote the determinant in (3.6) by D_{A}(x, y; n). In fact, there are more factors that can be taken out of D_{A}(x, y; n) under the restriction that the entries of the determinant continue to be polynomials. To this end, we multiply the i-th row of D_{A}(x, y; n) by (y + 2n − i)_{i−1}, i = 1, 2, …, n − 1, divide the j-th column by (y + 2j + 1)_{2n−2j−2}, j = 1, 2, …, n − 1, and divide the 0-th column by (y + 1)_{2n−2}. This leads to

∏_{i=1}^{n−1}(y + 2n − i)_{i−1} ∏_{j=1}^{n−1} \frac{1}{(y + 2j + 1)_{2n−2j−2}} · \frac{1}{(y + 1)_{2n−2}} · D_{A}(x, y; n)

= det_{0≤i,j≤n−1}(...................................................................... . . . . .. . . . .. . . . .. . . . . T (x, y)  ^{(x+y+1)_{j} (x−j+2)_{⌊(y−x)/2⌋+j−1}}_{−(y−i+2)_{i−1}}  _{(x+y+i+1)_{j−1} (x+2i−j+2)_{j−1}}_{×(y+2j−i+2)_{i−1} (y−x+3j−3i)}  i= 0 i≥1 ) , j =0  j ≥1  (3.8)

where T (x, y) is given by

T (x, y) = ∑_{r=1}^{⌊(y−x)/2⌋}(x + r + 1)_{⌊(y−x)/2⌋−r} (y − r + 1)_{r}

+ ∑_{r=0}^{⌈(y−x)/2⌉−1}(x + r + 1)_{⌊(y−x)/2⌋−r} (y − r + 1)_{r}, (3.9)

or, if we denote the determinant in (3.8) by D_{B}(x, y; n),

D_{A}(x, y; n) = (y + 1)_{2n−2} ∏_{i=1}^{n−1}(y + 2i + 1)_{n−i−1} · D_{B}(x, y; n).  (3.10)

A combination of (3.3), (3.8), and (3.10) then implies that Theorem 2 is equivalent to the statement:

With D_{B}(x, y; n) the determinant in (3.8), there holds

D_{B}(x, y; n) = ∏_{i=1}^{n−1} ((2x + y + 2i + 2)_{i−1} (x + 2y + 2i + 2)_{i−1})

× ∏_{i=0}^{⌊n/2⌋−1}(2x + 2 ⌈(y − x)/2⌉ + 2i + 1) · P_{1}(x; y − x, n), (3.11)

where P_{1}(x; y − x, n) satisfies the properties that are stated in Theorem 2.

Recall that y = x + m, where m is a fixed nonnegative integer. In the subsequent steps of the proof we are going to establish that (3.11) does not hold only for integral x, but holds as a polynomial identity in x. In order to accomplish this, we show in Step 3 that the first product on the right-hand side of (3.11) is a factor of D_{B}(x, y; n), then we show in Step 4 that the second product on the right-hand side of (3.11) is a factor of D_{B}(x, y; n), and finally we show in Step 5 that the degree of D_{B}(x, y; n) is at most 2\binom{n−1}{2} + ⌊n/2⌋ + ⌊(y − x)/2⌋, which implies that the degree of P_{1}(x; y − x, n) is at most ⌊(y − x)/2⌋ = ⌊m/2⌋. Once this is done, the proof of Theorem 2 will be complete (except for the statement about P_{1}(x; y −x, n) for odd n and even m, which is proved in Step 4, and the algorithm for computing P_{1}(x; y − x, n) explicitly, which is described in Step 6).

Step 3. ∏_{i=1}^{n−1} ((2x+y+2i+2)_{i−1} (x+2y+2i+2)_{i−1}) is a factor of D_{B}(x, y; n). Here we consider the auxiliary determinant \overline{D}_{B}(x, y, ȳ; n), which arises from D_{B}(x, y; n) (the determinant in (3.8)) by replacing each occurence of y by ȳ, except for the entries in the 0-th row, where we only partially replace y by ȳ,

\overline{D}_{B}(x, y, ȳ; n)

:= det_{0≤i,j≤n−1}(...................................................................... . . . . .. . . . .. . . . .. . . . . T (x, y)  ^{(x+ȳ+1)_{j} (x−j+2)_{⌊(y−x)/2⌋+j−1}}_{−(ȳ−i+2)_{i−1}}  _{(x+ȳ+i+1)_{j−1} (x+2i−j+2)_{j−1}}_{×(ȳ+2j−i+2)_{i−1} (ȳ−x+3j−3i)}  i=0 i≥1 ) , j =0  j ≥1  (3.12)

with T (x, y) given by (3.9). Clearly, \overline{D}_{B}(x, y, ȳ; n) is a polynomial in x and ȳ (recall that y = x + m) which agrees with D_{B}(x, y; n) when ȳ = y. We are going to prove that

\overline{D}_{B}(x, y, ȳ; n) = ∏_{i=1}^{n−1} ((2x + ȳ + 2i + 2)_{i−1} (x + 2ȳ + 2i + 2)_{i−1}) · P_{2}(x, y, ȳ; n), (3.13)

where P_{2}(x, y, ȳ; n) is a polynomial in x and ȳ. Obviously, when we set ȳ = y, this implies that ∏_{i=1}^{n−1} ((2x + y + 2i + 2)_{i−1} (x + 2y + 2i + 2)_{i−1}) is a factor of D_{B}(x, y; n), as desired.

To prove (3.13), we first consider just one half of this product, ∏_{i=1}^{n−1}(2x + ȳ+ 2i + 2)_{i−1}. Let us concentrate on a typical factor (2x + ȳ + 2i + l + 1), 1 ≤ i ≤ n − 1, 1 ≤ l < i. We claim that for each such factor there is a linear combination of the rows that vanishes if the factor vanishes. More precisely, we claim that for any i, l with 1 ≤ i ≤ n − 1, 1 ≤ l < i there holds

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 1)_{2i−2s}}{(−x − 2i − l + s)_{i−s}}

· (row s of \overline{D}_{B}(x, y, −2x − 2i − l − 1; n)) = (row i of \overline{D}_{B}(x, y, −2x − 2i − l − 1; n)). (3.14)

To see this, we have to check

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 1)_{2i−2s}}{(−x − 2i − l + s)_{i−s}}

· (−2x − 2i − l − s + 1)_{s−1} = (−2x − 3i − l + 1)_{i−1}, (3.15)

which is (3.14) restricted to the 0-th column, and

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 1)_{2i−2s}}{(−x − 2i − l + s)_{i−s}}
× (−x − 2i − l + s)_{j−1} (x + 2s − j + 2)_{j−1}
× (−2x − 2i − l + 2j − s + 1)_{s−1} (−3x − 2i − l + 3j − 3s − 1)

= (−x − i − l)_{j−1} (x + 2i − j + 2)_{j−1} (−2x − 3i − l + 2j + 1)_{i−1} (−3x − l + 3j − 5i − 1), (3.16)

which is (3.14) restricted to the j-th column, 1 ≤ j ≤ n − 1. Equivalently, in terms of hypergeometric series (cf. the Appendix for the definition of the F -notation), this means to check

2 \frac{(1 − 2i − 2l − 2x)_{l−1}(1 + 2l + x)_{2i−2l}}{(−2i − x)_{i−l}}

×_{5}F_{4}[ \begin{matrix}1 − \frac{2i}{3} + \frac{2l}{3}, −\frac{i}{2} + \frac{l}{2}, \frac{1}{2} − \frac{i}{2} + \frac{l}{2}, −2i − x, 2i + 2l + 2x \\ −\frac{2i}{3} + \frac{2l}{3}, 1 − i + l, \frac{1}{2} + l + \frac{x}{2}, 1 + l + \frac{x}{2} \end{matrix} ; 1]

= (−2x − 3i − l + 1)_{i−1} (3.17)

and

2 \frac{(−x − 2i)_{j−1}}{(−x − 2i)_{i−l}} (−3x − 4l + 3j − 2i − 1) (−2x − 2l + 2j − 2i + 1)_{l−1}

× (x − j + 2l + 2)_{2i+j−2l−1} ·_{6}F_{5}[ \begin{matrix}\frac{4}{3} + \frac{2i}{3} − j + \frac{4l}{3} + x, 1 − \frac{2i}{3} + \frac{2l}{3}, \\ \frac{1}{3} + \frac{2i}{3} − j + \frac{4l}{3} + x, −\frac{2i}{3} + \frac{2l}{3}, \end{matrix}

\begin{matrix}−\frac{i}{2} + \frac{l}{2}, \frac{1}{2} − \frac{i}{2} + \frac{l}{2}, −1 − 2i + j − x, 2i − 2j + 2l + 2x \\ 1 − i + l, 1 − \frac{j}{2} + l + \frac{x}{2}, \frac{3}{2} − \frac{j}{2} + l + \frac{x}{2} \end{matrix} ; 1]

= (−3x − l + 3j − 5i − 1) (1 − 3i + 2j − l − 2x)_{i−1}

× (−i − l − x)_{j−1}(2 + 2i − j + x)_{j−1} (3.18)

Now, the identity (3.17) holds since the _{5}F_{4}-series in (3.17) can be summed by Corollary A5, and the identity (3.18) holds since the _{6}F_{5}-series in (3.18) can be summed by Lemma A6.

The product ∏_{i=1}^{n−1}(2x + ȳ + 2i + 2)_{i−1} consists of factors of the form (2x + ȳ + a), 4 ≤ a ≤ 3n − 3. Let a be fixed. Then the factor (2x + ȳ + a) occurs in the product ∏_{i=1}^{n−1}(2x + ȳ + 2i + 2)_{i−1} as many times as there are solutions to the equation

a = 2i + l + 1, with 1 ≤ i ≤ n − 1, 1 ≤ l < i.  (3.19)

For each solution (i, l), we subtract the linear combination

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 1)_{2i−2s}}{(−x − 2i − l + s)_{i−s}}

· (row s of \overline{D}_{B}(x, y, ȳ; n)) (3.20)

of rows of \overline{D}_{B}(x, y, ȳ; n) from row i of \overline{D}_{B}(x, y, ȳ; n). Then, by (3.14), all the entries in row i of the resulting determinant vanish for ȳ = −2x − 2i − l − 1. Hence, (2x + ȳ + 2i + l + 1) = (2x + ȳ + a) is a factor of all the entries in row i, for each solution (i, l) of (3.19). By taking these factors out of the determinant we obtain

\overline{D}_{B}(x, y, ȳ; n) = (2x + ȳ + a)^{#(solutions (i,l) of (3.19))} · D_{B}^{(a)}(x, y, ȳ; n),  (3.21)

where D_{B}^{(a)}(x, y, ȳ; n) is a determinant whose entries are rational functions in x and ȳ, the denominators containing factors of the form (x + c) (which come from the coefficients in the linear combination (3.20)). Taking the limit x → −c in (3.21) then reveals that these denominators cancel in the determinant, so that D_{B}^{(a)}(x, y, ȳ; n) is actually a polynomial in x and ȳ. Thus we have shown that each factor of ∏_{i=1}^{n−1}(2x+ ȳ + 2i + 2)_{i−1} divides \overline{D}_{B}(x, y, ȳ; n) with the right multiplicity, hence the complete product divides \overline{D}_{B}(x, y, ȳ; n).

The reasoning that ∏_{i=1}^{n−1}(x + 2ȳ+ 2i + 2)_{i−1} is a factor of \overline{D}_{B}(x, y, ȳ; n) is similar. Also here, let us concentrate on a typical factor (x + 2ȳ + 2j + l + 1), 1 ≤ j ≤ n − 1, 1 ≤ l < j. This time we claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 1 ≤ j ≤ n − 1, 1 ≤ l < j there holds

∑_{s=l}^{⌊(j+l)/2⌋} \frac{(2j − 3s + l)}{(j − s)} \frac{(j − 2s + l + 1)_{s−l}}{(s − l)!} (ȳ + 2s + 1)_{2j−2s}

· (column s of \overline{D}_{B}(−2ȳ − 2j − l − 1, y, ȳ; n))
= (column j of \overline{D}_{B}(−2ȳ − 2j − l − 1, y, ȳ; n)). (3.22)

This means to check

∑_{s=l}^{⌊(j+l)/2⌋} \frac{(2j − 3s + l)}{(j − s)} \frac{(j − 2s + l + 1)_{s−l}}{(s − l)!} (ȳ + 2s + 1)_{2j−2s}

× (−ȳ − 2j − l)_{s} (−2ȳ − 2j − l − s + 1)_{⌊(y−x)/2⌋+s−1}

= (−ȳ − 2j − l)_{j} (−2ȳ − 3j − l + 1)_{⌊(y−x)/2⌋+j−1}, (3.23) which is (3.22) restricted to the 0-th row, and

∑_{s=l}^{⌊(j+l)/2⌋} \frac{(2j − 3s + l)}{(j − s)} \frac{(j − 2s + l + 1)_{s−l}}{(s − l)!} (ȳ + 2s + 1)_{2j−2s}

× (−ȳ − 2j − l + i)_{s−1} (−2ȳ − 2j − l + 2i − s + 1)_{s−1}
× (ȳ + 2s − i + 2)_{i−1} (3ȳ + 2j + l − 3i + 3s + 1)

= (−ȳ−2j −l +i)_{j−1} (−2ȳ−3j −l +2i+1)_{j−1} (ȳ+2j −i+2)_{i−1} (3ȳ+5j +l −3i+1), (3.24)

which is (3.22) restricted to the i-th row, 1 ≤ i ≤ n − 1. If we plug

(−ȳ − 2j − l)_{s} = \frac{(−ȳ − 2j − l)_{j}}{(−ȳ − 2j − l + s)_{j−s}}

into (3.23), we see that (3.23) is equivalent to (3.15) (replace x by ȳ and i by j). Likewise, by plugging

(−ȳ − 2j − l + i)_{s−1} = \frac{(−ȳ − 2j − l + s)_{i−1}}{(−ȳ − 2j − l + s)_{j−s}} \frac{(−ȳ − 2j − l + i)_{j−1}}{(−ȳ − j − l)_{i−1}}

into (3.24), we see that (3.24) is equivalent to (3.16) (replace x by ȳ and interchange i and j). By arguments that are similar to the ones above, it follows that ∏_{i=1}^{n−1}(x + 2ȳ + 2i + 2)_{i−1} divides \overline{D}_{B}(x, y, ȳ; n).

Altogether, this implies that ∏_{i=1}^{n−1} ((2x+ȳ+2i+2)_{i−1}(x+2ȳ+2i+2)_{i−1}) divides \overline{D}_{B}(x, y, ȳ; n), and so, as we already noted after (3.13), the product ∏_{i=1}^{n−1} ((2x + y + 2i + 2)_{i−1}(x + 2y + 2i + 2)_{i−1}) divides D_{B}(x, y; n), as desired.

Step 4. ∏_{i=0}^{⌊n/2⌋−1}(2x+2 ⌈(y − x)/2⌉+2i+1) is a factor of D_{B}(x, y; n). We consider (3.5). In the determinant in (3.5) we take

\frac{1}{2} \frac{(x + y + i + 1)! (2x + y + 3i + 4)}{(x + 2i + 2)! (y + 2n − 2)!}

out of the i-th row, i = 0, 1, …, n − 2, we take

\frac{(x + y + n)!}{(x + 2n − 2)! (y + 2n − 2)!}

out of the (n − 1)-st row, and we take

\frac{1}{2}(y + 2j + 3)_{2n−2j−4} (x + 2y + 3j + 4)

out of the j-th column, j = 0, 1, …, n − 2. Then we combine with (3.6) and (3.10) (recall that D_{B}(x, y; n) is the determinant in (3.6)), and after cancellation we obtain

D_{B}(x, y; n) = (\frac{1}{2})^{2n−2} \frac{(x + y + 1)_{n}}{(⌊(x + y)/2⌋ + 1)_{2n−2−⌊(y−x)/2⌋} (y + 1)_{2n−2}}

× det_{0≤i,j≤n−1}(................................................................................ . . . . .. . . . .. . . . .. . . . .^{(x+y+i+2)_{j} (x+2i−j+3)_{j}}^{×(y+2j−i+3)_{i} (y−x+3j−3i)} ^{(x+y+i+2)_{n−1} (x+2i−n+4)_{n−1}}^{×(y+2n−i−1)_{i}}_{−(x+y+n+1)_{j} (x+2n−j−1)_{j}}_{×(y+2j−n+4)_{n−1}}  U(x, y; n)  i≤n−2 i=n−1 ) , j ≤n−2  j =n−1  (3.25)

where

U(x, y; n) = ∑_{r=0}^{y−x−1}(x + y + n + 1)_{n−2} (x + n + r)_{n−r−1} (y + n − r)_{r+n−1}.

The determinant on the right-hand side of (3.25) has polynomial entries. Note that in case of the (n−1, n−1)-entry this is due to n−r −1 ≥ n−(y −x−1)−1 = n−m ≥ 0 (recall that y = x + m), the last inequality being an assumption in the statement of the Theorem. The product in the numerator of the right-hand side of (3.25) consists of factors of the form (x+y +a) = (2x+m+a) with integral a. Some of these factors cancel with the denominator, but all factors of the form (2x + 2b + 1), with integral b, do not cancel, and so because of (3.25) divide D_{B}(x, y; n). These factors are

∏_{i=0}^{⌈(m+n)/2⌉−⌈m/2⌉−1}(2x + 2 ⌈m/2⌉ + 2i + 1)

(with m = y − x, of course). Since

⌈(m + n)/2⌉ − ⌈m/2⌉ − 1 = \{ \begin{matrix}⌊n/2⌋ & n odd, m even \\ ⌊n/2⌋ − 1 & otherwise, \end{matrix}

it follows that ∏_{i=0}^{⌊n/2⌋−1}(2x + 2 ⌈m/2⌉ + 2i + 1) is a factor of D_{B}(x, y; n), and if n is odd and m is even (2x + m + n) is an additional factor of D_{B}(x, y; n).

Summarizing, so far we have shown that the equation (3.11) holds, where P_{1}(x; y − x, n) = P_{1}(x; m, n) is some polynomial in x, that has (2x + m + n) as a factor in case that n is odd and m is even. It remains to show that P_{1}(x; m, n) is a polynomial in x of degree ≤ ⌊m/2⌋, and to describe how P_{1}(x; m, n) can be computed explicitly.

Step 5. P_{1}(x; m, n) is a polynomial in x of degree ≤ ⌊m/2⌋. Here we write x + m for y everywhere. We shall prove that D_{A}(x, x + m; n) (which is defined to be the determinant in (3.6)) is a polynomial in x of degree at most 2\binom{n}{2} + \binom{n−1}{2} + ⌊n/2⌋ + ⌊m/2⌋. By (3.10) this would imply that D_{B}(x, x+m; n) is a polynomial in x of degree at most 2\binom{n−1}{2} + ⌊n/2⌋ + ⌊m/2⌋, and so, by (3.11), that P_{1}(x; m, n) is a polynomial in x of degree at most ⌊m/2⌋, as desired.

Establishing the claimed degree bound for D_{A}(x, x + m; n) is the most delicate part of the proof of the Theorem. We need to consider the generalized determinant

\overline{D}_{A}(x, z(1), z(2), …, z(n − 1); n) = \overline{D}_{A}(n)

which arises from D_{A}(x, x + m; n) by replacing each occurence of i in row i by an indeterminate, z(i) say, i = 1, 2, …, n − 1,

\overline{D}_{A}(x, z(1), z(2), …, z(n − 1); n)

:= det_{0≤i,j≤n−1}( ..................................................................................... . . . . .. . . . .. . . . .. . . . . S(x, x + m; n)  ^{(2x+m+1)_{j} (x−j+2)_{⌊m/2⌋+j−1}}^{×(x+m+2j+1)_{2n−2j−2}}_{−(x+m−z(i)+2)_{2n−2}} _{(2x+m+z(i)+1)_{j−1} (x+2z(i)−j+2)_{j−1}}_{×(x+m+2j−z(i)+2)_{2n−2j−2} (m+3j−3z(i))}  i=0 i≥1 ) , j =0  j ≥1  (3.26)

where S(x, x + m; n) is given by (3.7).

This determinant is a polynomial in x, z(1), z(2), …, z(n − 1). We shall prove that the degree in x of this determinant is at most 2\binom{n}{2} + \binom{n−1}{2} + ⌊n/2⌋ + ⌊m/2⌋, which clearly implies our claim upon setting z(i) = i, i = 1, 2, …, n − 1.

Let us denote the (i, j)-entry of \overline{D}_{A}(n) by A(i, j). In the following computation we write S_{n} for the group of all permutations of {0, 1, …, n − 1}. By definition of the determinant we have

\overline{D}_{A}(n) = ∑_{σ∈S_{n}} sgn σ ∏_{j=0}^{n−1} A(σ(j), j),

and after expanding the determinant along the 0-th row,

\overline{D}_{A}(n) = A(0, 0) ∑_{σ∈S_{n−1}} ∏_{j=0}^{n−2} A(σ(j) + 1, j + 1)

+ ∑_{ℓ=1}^{n−1}(−1)^{ℓ}A(0, ℓ) ∑_{σ∈S_{n−1}} sgn σ ∏_{j=0}^{n−2} A(σ(j) + 1, j + χ(j ≥ ℓ)), (3.27)

where χ(A)=1 if A is true and χ(A)=0 otherwise. Now, by Lemma A10 we know that for i, j ≥ 1 we have

A(i, j) = ∑_{p,q≥0} 2^{j}α_{p,q}(j) x^{p} z(i)^{q},  (3.28)

where α_{p,q}(j) is a polynomial in j of degree ≤ 2(2n − 3 − p − q) + q − 1. It should be noted that the range of the sum in (3.28) is actually

0 ≤ p ≤ 2n − 4, 0 ≤ q ≤ 2n − 3, p + q ≤ 2n − 3.  (3.29)

Furthermore, by Lemma A9 we know that for j ≥ 1 we have

A(0, j) = ∑_{p≥0} 2^{j}β_{p}(j) x^{p},  (3.30)

where β_{p}(j) is a polynomial in j of degree ≤ 2(2n + ⌊m/2⌋ − 3 − p). Also, for i ≥ 1 let

A(i, 0) = −(x + m − z(i) + 2)_{2n−2} = ∑_{p,q≥0} γ_{p,q} x^{p} z(i)^{q}.  (3.31)

Plugging (3.28) and (3.31) into (3.27), and writing z̄(i) instead of z(i+1) for notational convenience, we get

\overline{D}_{A}(n) = A(0, 0)_{∑_{p_{0},...,p_{n−2}≥0} ; q_{0},...,q_{n−2}≥0}2^{\binom{n}{2}}x^{p_{0}+···+p_{n−2}} ∏_{j=0}^{n−2} α_{p_{j},q_{j}}(j + 1) ∑_{σ∈S_{n−1}} sgn σ ∏_{j=0}^{n−2} z̄(σ(j))^{q_{j}}

+ ∑_{ℓ=1}^{n−1}(−1)^{ℓ}A(0, ℓ)_{∑_{p_{0},...,p_{n−2}≥0} ; q_{0},...,q_{n−2}≥0}2^{\binom{n}{2}−ℓ}x^{p_{0}+···+p_{n−2}}γ_{p_{0},q_{0}} ∏_{j=1}^{n−2} α_{p_{j},q_{j}}(j + χ(j ≥ ℓ))

× ∑_{σ∈S_{n−1}} sgn σ ∏_{j=0}^{n−2} z̄(σ(j))^{q_{j}}

= A(0, 0)_{∑_{p_{0},...,p_{n−2}≥0} ; q_{0},...,q_{n−2}≥0}2^{\binom{n}{2}}x^{p_{0}+···+p_{n−2}} ∏_{j=0}^{n−2} α_{p_{j},q_{j}}(j + 1) det_{0≤i,j,≤n−2}(z̄(i)^{q_{j}})

+ ∑_{ℓ=1}^{n−1}(−1)^{ℓ}A(0, ℓ)_{∑_{p_{0},...,p_{n−2}≥0} ; q_{0},...,q_{n−2}≥0}2^{\binom{n}{2}−ℓ}x^{p_{0}+···+p_{n−2}}γ_{p_{0},q_{0}} ∏_{j=1}^{n−2} α_{p_{j},q_{j}}(j + χ(j ≥ ℓ))

× det_{0≤i,j,≤n−2}(z̄(i)^{q_{j}}). (3.32)

The determinants in (3.32) vanish whenever q_{j_{1}} = q_{j_{2}} for some j_{1} ≠ j_{2}. Hence, in the sequel we may assume that the summation indices q_{0}, q_{1}, …, q_{n−2} are pairwise distinct, in both terms on the right-hand side of (3.32). In particular, we may assume that in the first term the pairs (p_{0}, q_{0}), (p_{1}, q_{1}), …, (p_{n−2}, q_{n−2}) are pairwise distinct, and that in the second term the pairs (p_{1}, q_{1}), (p_{2}, q_{2}), …, (p_{n−2}, q_{n−2}) are pairwise distinct. What we do next is to collect the summands in the inner sums that are indexed by the same set of pairs. So, if in addition we plug (3.30) into (3.32), we obtain

\overline{D}_{A}(n) = A(0, 0) ∑_{\{(p_{0},q_{0}),...,(p_{n−2},q_{n−2})\}}2^{\binom{n}{2}}x^{p_{0}+···+p_{n−2}}

× ∑_{τ∈S_{n−1}} det_{0≤i,j≤n−2}(z̄(i)^{q_{τ(j)}}) ∏_{j=0}^{n−2} α_{p_{τ(j)},q_{τ(j)}}(j + 1)

+ ∑_{p,p_{0},q_{0}≥0} ∑_{\{(p_{1},q_{1}),...,(p_{n−2},q_{n−2})\}}2^{\binom{n}{2}}x^{p+p_{0}+···+p_{n−2}}γ_{p_{0},q_{0}} ∑_{ℓ=1}^{n−1}(−1)^{ℓ}β_{p}(ℓ)

× ∑_{τ∈S̃_{n−2}} det_{0≤i,j≤n−2}(z̄(i)^{q_{τ(j)}}) ∏_{j=1}^{n−2} α_{p_{τ(j)},q_{τ(j)}}(j + χ(j ≥ ℓ)) (3.33)

where S̃_{n−2} denotes the group of all permutations of {0, 1, …, n − 1} that fix 0. Clearly, we have

det_{0≤i,j≤n−2}(z̄(i)^{q_{τ(j)}}) = sgn τ det_{0≤i,j≤n−2}(z̄(i)^{q_{j}}).  (3.34)

Moreover, there holds

∑_{ℓ=1}^{n−1}(−1)^{ℓ}β_{p}(ℓ) ∑_{τ∈S̃_{n−2}} sgn τ ∏_{j=1}^{n−2} α_{p_{τ(j)},q_{τ(j)}}(j + χ(j ≥ ℓ))

= ∑_{ℓ=1}^{n−1}(−1)^{ℓ}β_{p}(ℓ) det_{1≤i,j≤n−2} (α_{p_{i},q_{i}}(j + χ(j ≥ ℓ)))

= (−1)^{n−1} det_{1≤i,j≤n−1} ( \begin{matrix}α_{p_{i},q_{i}}(j) & i≤n−2 \\ β_{p}(j) & i=n−1 \end{matrix} ) ,  (3.35)

the step from the last line to the next-to-last line being just expansion of the determinant along the bottom row. Using (3.34) and (3.35) in (3.33) then yields

\overline{D}_{A}(n) = A(0, 0) ∑_{\{(p_{0},q_{0}),...,(p_{n−2},q_{n−2})\}}2^{\binom{n}{2}}x^{p_{0}+···+p_{n−2}}

× det_{0≤i,j≤n−2}(z̄(i)^{q_{j}}) det_{0≤i,j≤n−2} (α_{p_{i},q_{i}}(j + 1))

+ (−1)^{n−1} ∑_{p,p_{0},q_{0}≥0} ∑_{\{(p_{1},q_{1}),...,(p_{n−2},q_{n−2})\}}2^{\binom{n}{2}}x^{p+p_{0}+···+p_{n−2}}γ_{p_{0},q_{0}}

× det_{0≤i,j≤n−2}(z̄(i)^{q_{j}}) det_{1≤i,j≤n−1} ( \begin{matrix}α_{p_{i},q_{i}}(j) & i≤n−2 \\ β_{p}(j) & i=n−1 \end{matrix} ) . (3.36)

We treat the two terms on the right-hand side of (3.36) separately. Recall that we want to prove that the degree in x of \overline{D}_{A}(n) is at most 2\binom{n}{2} + \binom{n−1}{2} + ⌊n/2⌋ + ⌊m/2⌋.

What regards the first term,

A(0, 0) ∑_{\{(p_{0},q_{0}),...,(p_{n−2},q_{n−2})\}}2^{\binom{n}{2}}x^{p_{0}+···+p_{n−2}}

× det_{0≤i,j≤n−2}(z̄(i)^{q_{j}}) det_{0≤i,j≤n−2} (α_{p_{i},q_{i}}(j + 1)), (3.37)

we shall prove that the degree in x is actually at most 2\binom{n}{2} + \binom{n−1}{2} + ⌊(n − 1)/2⌋ + ⌊m/2⌋. Equivalently, when disregarding A(0, 0) = S(x, x + m; n), whose degree in x is 2n − 2 + ⌊m/2⌋ (see (3.7)), this means to prove that the degree in x of the sum in (3.37) is at most 3\binom{n−1}{2} + ⌊(n − 1)/2⌋.

So we have to examine for which indices p_{0}, …, p_{n−2}, q_{0}, …, q_{n−2} the determinants in (3.37) do not vanish. As we already noted, the first determinant does not vanish only if the indices q_{0}, q_{1}, …, q_{n−2} are pairwise distinct. So, without loss of generality we may assume

0 ≤ q_{0} < q_{1} < ⋯ < q_{n−2}.  (3.38)

Turning to the second determinant in (3.37), we observe that because of what we know about α_{p_{i},q_{i}}(j + 1) (cf. the sentence containing (3.28)) each row of this determinant is filled with a single polynomial evaluated at 1, 2, …, n − 1. Let M be some nonnegative integer. If we assume that among the polynomials α_{p_{i},q_{i}}(j + 1), i = 0, 1, …, n − 2, there are M + 1 polynomials of degree less or equal M − 1, then the determinant will vanish. For, a set of M + 1 polynomials of maximum degree M − 1 is linearly dependent. Hence, the rows in the second determinant in (3.37) will be linearly dependent, and so the determinant will vanish. Since the degree of α_{p_{i},q_{i}}(j + 1) as a polynomial in j is at most 2(2n − 3 − p_{i} − q_{i}) + q_{i} − 1 (again, cf. the sentence containing (3.28)), we have that

the number of integers 2(2n − 3 − p_{i} − q_{i}) + q_{i} − 1, i = 0, 1, …, n − 2, that are less or equal M − 1 is at most M.

(3.39)

Now the task is to determine the maximal value of p_{0} + p_{1} + ⋯ + p_{n−2} (which is the degree in x of the sum in (3.37) that we are interested in), under the conditions (3.38) and (3.39), and the additional condition

0 ≤ p_{i} ≤ 2n − 4, 0 ≤ q_{i} ≤ 2n − 3, p_{i} + q_{i} ≤ 2n − 3,  (3.40)

which comes from (3.29). We want to prove that this maximal value is 3\binom{n−1}{2} + ⌊(n − 1)/2⌋. To simplify notation we write

ε_{i} = 2n − 3 − p_{i} − q_{i}.  (3.41)

Thus, since

∑_{i=0}^{n−2} p_{i} = (n − 1)(2n − 3) − ∑_{i=0}^{n−2}(q_{i} + ε_{i}),

we have to prove that the minimal value of

q_{0} + q_{1} + ⋯ + q_{n−2} + ε_{0} + ε_{1} + ⋯ + ε_{n−2},  (3.42)

under the condition (3.38), the condition that

ε_{i} ≥ 0, i = 0, 1, …, n − 2,  (3.43)

(which comes from the right-most inequality in (3.40) under the substitution (3.41)), the condition that

the number of integers 2ε_{i} + q_{i} − 1, i = 0, 1, …, n − 2, that are less or equal M − 1 is at most M,

(3.44)

(which is (3.39) under the substitution (3.41)), and the condition

if q_{0} = 0, then ε_{0} ≥ 1,  (3.45)

(which comes from (3.40) and (3.41)), is \binom{n−1}{2} + ⌈(n − 1)/2⌉.

As a first, simple case, we consider q_{0} ≥ 1. Then, from (3.38) it follows that the sum ∑_{i=0}^{n−2} q_{i} alone is at least \binom{n}{2} = \binom{n−1}{2} + (n − 1), which trivially implies our claim. Therefore, from now on we assume that q_{0} = 0. Note that this in particular implies ε_{0} ≥ 1, because of (3.45).

Next, we apply (3.44) with M = 2. In particular, since among the first three integers 2ε_{i} + q_{i} − 1, i = 0, 1, 2, only two can be less or equal 1, there must be an i_{1} ≤ 2 with 2ε_{i_{1}} + q_{i_{1}} − 1 ≥ 2. Without loss of generality we choose i_{1} to be minimal with this property. Now we apply (3.44) with M = 2ε_{i_{1}} + q_{i_{1}}. Arguing similarly, we see that there must be an i_{2} ≤ 2ε_{i_{1}} + q_{i_{1}} with 2ε_{i_{2}} + q_{i_{2}} − 1 ≥ 2ε_{i_{1}} + q_{i_{1}}. Again, we choose i_{2} to be minimal with this property. This continues, until we meet an i_{k} ≤ 2ε_{i_{k−1}} + q_{i_{k−1}} with 2ε_{i_{k}} + q_{i_{k}} − 1 ≥ n − 2. That such an i_{k} must be found eventually is seen by applying (3.44) with n − 2.

Let us collect the facts that we have found so far: There exists a sequence i_{1}, i_{2}, …, i_{k} of integers satisfying

0 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n − 2  (3.46)

(this is because of the minimal choice for each of the i_{j}’s),

i_{1} ≤ 2, i_{2} ≤ 2ε_{i_{1}} + q_{i_{1}}, …, i_{k} ≤ 2ε_{i_{k−1}} + q_{i_{k−1}},  (3.47)

and

2ε_{i_{k}} + q_{i_{k}} − 1 ≥ n − 2.  (3.48)

The other inequalities are not needed later.

Now we turn to the quantity (3.42) that we want to bound from above. We have

∑_{i=0}^{n−2} q_{i} + ∑_{i=0}^{n−2} ε_{i} = ∑_{i=0}^{n−2}(q_{i} − i) + \binom{n − 1}{2} + ∑_{i=0}^{n−2} ε_{i}.  (3.49)

the electronic journal of combinatorics 4 (1997), #R27 22

For convenience, we write q̃_{i} for q_{i} − i in the sequel. Because of (3.38) we have

q̃_{i} ≥ 0, i = 0, 1, …, n − 2,  (3.50)

and

q̃_{i} ≥ q̃_{j}, for i ≥ j.  (3.51)

For a fixed i let s be maximal such that i_{s} ≤ i. Then, because of (3.51), there holds

q_{i} − i = q̃_{i} = (q̃_{i} − q̃_{i_{s}}) + (q̃_{i_{s}} − q̃_{i_{s−1}}) + ⋯ + (q̃_{i_{2}} − q̃_{i_{1}}) + q̃_{i_{1}}
≥ (q̃_{i_{s}} − q̃_{i_{s−1}}) + ⋯ + (q̃_{i_{2}} − q̃_{i_{1}}) + q̃_{i_{1}}.

Using this, (3.50) and (3.48), in (3.49), we obtain

∑_{i=0}^{n−2} q_{i} + ∑_{i=0}^{n−2} ε_{i} ≥ \binom{n − 1}{2} + (n − 1 − i_{1}) q̃_{i_{1}} + ∑_{s=2}^{k}(n − 1 − i_{s})(q̃_{i_{s}} − q̃_{i_{s−1}})

+ ∑_{i=0}^{n−2} ε_{i} − ε_{i_{k}} + \frac{n − 1 − q_{i_{k}}}{2} . (3.52)

Now, by (3.47) we have for q_{i_{k}} that

q_{i_{k}} = q̃_{i_{k}} + i_{k} = q̃_{i_{1}} + ∑_{s=2}^{k}(q̃_{i_{s}} − q̃_{i_{s−1}}) + i_{k}  (3.53)

≤ q̃_{i_{1}} + ∑_{s=2}^{k}(q̃_{i_{s}} − q̃_{i_{s−1}}) + 2ε_{i_{k−1}} + q_{i_{k−1}}.

A similar estimation holds for q_{i_{k−1}}, etc. Thus, by iteration we arrive at

q_{i_{k}} ≤ kq̃_{i_{1}} + ∑_{s=2}^{k}(k − s + 1)(q̃_{i_{s}} − q̃_{i_{s−1}}) + 2(ε_{i_{1}} + ⋯ + ε_{i_{k−1}}) + i_{1}.

Using this inequality in (3.52), we get

∑_{i=0}^{n−2} q_{i} + ∑_{i=0}^{n−2} ε_{i} ≥ \binom{n − 1}{2} + \frac{n − 1}{2}  (3.54a)

+ (n − 1 − i_{1} − \frac{k}{2} ) q̃_{i_{1}} + ∑_{s=2}^{k}(n − 1 − i_{s} − \frac{k − s + 1}{2}) (q̃_{i_{s}} − q̃_{i_{s−1}}) (3.54b)

+ ∑_{i=0}^{n−2} ε_{i} − ∑_{s=1}^{k} ε_{i_{s}} − \frac{i_{1}}{2} .  (3.54c)

By (3.50), (3.51), and since because of (3.46) we have

n − 1 − i_{s} − \frac{k − s + 1}{2} ≥ n − 1 − (n − 2 − k + s) − \frac{k − s + 1}{2} = \frac{k − s + 1}{2} ≥ 0, (3.55)

all terms in the line (3.54b) are nonnegative. If i_{1} = 0, then by (3.43) the line (3.54c) is nonnegative. If 1 ≤ i_{1} ≤ 2 (i_{1} cannot be larger because of (3.47)), then ε_{0} occurs in the line (3.54c). As we already noted, we have ε_{0} ≥ 1 since we are assuming that q_{0} = 0 in which case (3.45) applies. So, ε_{0} − i_{1}/2 ≥ 0, which in combination with (3.43) again implies that the line (3.54c) is nonnegative.

Hence, we conclude

∑_{i=0}^{n−2} q_{i} + ∑_{i=0}^{n−2} ε_{i} ≥ \binom{n − 1}{2} + \frac{n − 1}{2},

which is what we wanted.

The reasoning for the second term om the right-hand side of (3.36),

(−1)^{n−1} ∑_{p,p_{0},q_{0}≥0} ∑_{\{(p_{1},q_{1}),...,(p_{n−2},q_{n−2})\}}2^{\binom{n}{2}}x^{p+p_{0}+···+p_{n−2}}γ_{p_{0},q_{0}}

× det_{0≤i,j≤n−2}(z̄(i)^{q_{j}}) det_{1≤i,j≤n−1} ( \begin{matrix}α_{p_{i},q_{i}}(j) & i≤n−2 \\ β_{p}(j) & i=n−1 \end{matrix} ) , (3.56)

is similar, only slightly more complicated. We shall prove that the degree in x in (3.56) is at most 2\binom{n}{2} + \binom{n−1}{2} + ⌊n/2⌋ + ⌊m/2⌋, which by the discussion in the first paragraph of Step 5 is what we need.

So, we have to determine the maximal value of p+p_{0} +⋯+p_{n−2} such that the determinants in (3.56) do not vanish. Basically, we would now more or less run through the same arguments as before. Differences arise mainly in the considerations concerning the second determinant (which is slightly different from the second determinant in (3.37)). What has to be used here is that β_{p}(j) is a polynomial in j of degree ≤ 2(2n + ⌊m/2⌋ − 3 − p) (see the sentence containing (3.30)). If we make again the substitutions

ε_{i} = 2n − 3 − p_{i} − q_{i}, i = 1, 2, …, n − 2,  (3.57)

and in addition the substitutions

ε_{0} = 2n − 2 − p_{0} − q_{0},  (3.58)

and

ε = 2n + ⌊m/2⌋ − 3 − p,  (3.59)

we obtain eventually the following conditions that are necessary to make these two determinants not vanish: There must hold

0 ≤ q_{1} < q_{2} < ⋯ < q_{n−2}, and q_{0} is distinct from the other q_{i}’s,  (3.60)

(this is the substitute for (3.38)),

ε_{i} ≥ 0, i = 0, 1, …, n − 2, and ε ≥ 0,  (3.61)

(this is the substitute for (3.43)), and finally,

the number of integers in the set {2ε_{i} + q_{i} − 1 : i = 1, 2, …, n − 2} ∪ {2ε} that are less or equal M − 1 is at most M,

(3.62)

(this is the substitute for (3.44)). Since by the substitutions (3.57)–(3.59) we have

p + ∑_{i=0}^{n−2} p_{i} = 2\binom{n}{2} + 2\binom{n − 1}{2} + (n − 1) + ⌊\frac{m}{2}⌋ − ε − ∑_{i=0}^{n−2}(q_{i} + ε_{i}),

the task is to prove that the minimal value of

q_{0} + q_{1} + ⋯ + q_{n−2} + ε + ε_{0} + ε_{1} + ⋯ + ε_{n−2},  (3.63)

equals \binom{n−1}{2} + ⌈(n − 2)/2⌉.

Next in the arguments for the first term on the right-hand side of (3.36) came the sequence of applications of (3.44). Hence, now we apply (3.62) repeatedly. Actually, there is only one slight change, with the start. Namely, first we apply (3.62) with M = 2ε + 1. Since then 2ε is already less or equal M − 1, among the first 2ε + 1 integers 2ε_{i} + q_{i} − 1, i = 1, 2, …, 2ε + 1, only 2ε can be less or equal 2ε. Hence there must be an i_{1} ≤ 2ε + 1 with 2ε_{i_{1}} + q_{i_{1}} − 1 ≥ 2ε + 1. Continuing in the same manner as before, we obtain a sequence i_{1}, i_{2}, …, i_{k} of integers satisfying

1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n − 2,  (3.64)
i_{1} ≤ 2ε + 1, i_{2} ≤ 2ε_{i_{1}} + q_{i_{1}}, …, i_{k} ≤ 2ε_{i_{k−1}} + q_{i_{k−1}},  (3.65)

and

2ε_{i_{k}} + q_{i_{k}} − 1 ≥ n − 2.  (3.66)

Now we turn to the quantity (3.63) that we want to bound from above. We want to parallel the computation (3.49)–(3.54). However, since by (3.60) the q_{i}’s are slightly unordered (in comparison with (3.38)), we have to modify the definition of q̃_{i}. Namely, let t be the uniquely determined integer such that q_{t} < q_{0} < q_{t+1}, if existent, or t = 0 if q_{0} < q_{1}, or t = n − 2 if q_{n−2} < q_{0}. Then we define

q̃_{i} := \{ \begin{matrix}q_{0} − t & if i = 0, \\ q_{i} − i + 1 & if 1 ≤ i ≤ t \\ q_{i} − i & if i > t. \end{matrix}

If we modify (3.49) accordingly,

∑_{i=0}^{n−2} q_{i} + ∑_{i=0}^{n−2} ε_{i} = (q_{0} − t) + ∑_{i=1}^{t}(q_{i} − i + 1) + ∑_{i=t+1}^{n−2}(q_{i} − i) + \binom{n − 1}{2} + ∑_{i=0}^{n−2} ε_{i},

all subsequent steps that lead to (3.54) can be performed without difficulties. (A little detail is that in (3.53) the equality q_{i_{k}} = q̃_{i_{k}} + i_{k} has to be replaced by the inequality q_{i_{k}} ≤ q̃_{i_{k}} + i_{k}.) Also, the estimation (3.55) still holds true because of (3.64). Hence, when we use the first inequality in (3.65), together with (3.50), (3.51), (3.55), (3.61), in (3.54), we obtain

∑_{i=0}^{n−2} q_{i} + ε + ∑_{i=0}^{n−2} ε_{i} ≥ \binom{n − 1}{2} + \frac{n − 1}{2} + ∑_{i=0}^{n−2} ε_{i} + ε − ∑_{s=1}^{k} ε_{i_{s}} − \frac{2ε + 1}{2}

≥ \binom{n − 1}{2} + \frac{n − 2}{2},

which is what we wanted.

The proof that the degree of the polynomial P_{1}(x; m, n) is at most ⌊m/2⌋ is thus complete.

Step 6. An algorithm for the explicit computation of P_{1}(x; m, n). Also here, we write x + m for y everywhere. A combination of (3.11) and (3.25) yields

P_{1}(x; m, n) = (\frac{1}{2})^{2n−2} \frac{∏_{i=1}^{⌊(m+n)/2⌋−⌊m/2⌋}(2x + 2 ⌊m/2⌋ + 2i)}{(x + ⌊m/2⌋ + 1)_{2n−2−⌊m/2⌋} (x + m + 1)_{2n−2}}

× ∏_{i=1}^{n−1} \frac{1}{(3x + m + 2i + 2)_{i−1} (3x + 2m + 2i + 2)_{i−1}}

× det_{0≤i,j≤n−1}(................................................................................ . . . . .. . . . .. . . . .. . . . .^{(2x+m+i+2)_{j} (x+2i−j+3)_{j}}^{×(x+m+2j−i+3)_{i} (m+3j−3i)} ^{(2x+m+i+2)_{n−1} (x+2i−n+4)_{n−1}}^{×(x+m+2n−i−1)_{i}}_{−(2x+m+n+1)_{j} (x+2n−j−1)_{j}}_{×(x+m+2j−n+4)_{n−1}}  U(x, x + m; n)  i≤n−2 i=n−1 ) . j ≤n−2  j =n−1  (3.67)

By Step 5, we know that the degree of P_{1}(x; m, n) is at most ⌊m/2⌋. Hence, if we are able to determine the value of P_{1}(x; m, n) at ⌊m/2⌋ + 1 different specializations, then we can compute P_{1}(x; m, n) explicitly, e.g. by Lagrange interpolation.

The specializations that we choose are of the form −v − 1/2, where v is some nonnegative integer. The first thing to be observed is that if we set x = −v − 1/2, v integral, in (3.67), then the denominator on the right-hand side of (3.67) does not vanish. So, everything is well-defined for this type of specialization.

Next, we observe that for x = −v − 1/2 “usually” (this will be specified in a moment) a lot of entries in the determinant in (3.67) will vanish. More precisely, since (2x + m + i + 2)_{j}, which is a term in each entry of the determinant except for the (n − 1, n − 1)-entry, vanishes if i ≤ −2x − m − 2 = 2v − m − 1 and i + j ≥ −2x − m − 1 = 2v − m, the determinant takes on the form

det_{0≤i,j≤n−1}( ∗ ∗  ∗ ∗  0 0  0 0 ∗  M^{...}^{...}^{...} . . . . . . . . . ⋮⋮  ⋮  ^{← i=2v−m−1} ) .^{j =2v−m−1}^{↓}  (3.68)

Obviously, this picture makes sense only if −1 ≤ 2v − m − 1 ≤ n − 1, or equivalently, if m/2 ≤ v ≤ (m + n)/2. It should be observed that this constraint is met by the choices v = ⌊(m + n)/2⌋ , ⌊(m + n)/2⌋−1, …, ⌊(m + n)/2⌋−⌊m/2⌋ that are suggested in the statement of Theorem 2. In particular, for the lower bound this is because of the assumption m ≤ n.

Because of the 0-matrix in the upper-right block of the matrix in (3.68), it follows that the determinant in (3.68) equals the product of the determinant of the upper-left block times det(M). Since the upper-left block is a triangular matrix, we obtain for the determinant in (3.68) an expression of the type

(product of the elements along the antidiagonal i + j = 2v − m − 1)

× det_{(m+n−2v)×(m+n−2v)}(M).

In the notation of the statement of the Theorem, i.e., with v = ⌊(m + n)/2⌋ − t, the dimension of det(M) is (m + n) − 2 ⌊(m + n)/2⌋ + 2t, which is less or equal 2t + 1.

Summarizing, we have seen that for x = − ⌊(m + n)/2⌋ + t − 1/2, t = 0, 1, …, ⌊m/2⌋, the determinant in (3.67) reduces to a (well-defined) multiple of a determinant of dimension at most 2t+1. Since we assume m to be some fixed, explicit nonnegative integer, and since 2t+1 ≤ m+1 (m+1 being a fixed bound), this determinant can be computed explicitly (at least in principle), and so also the explicit value of P_{1}(x; m, n) at x = − ⌊(m + n)/2⌋+t−1/2, t = 0, 1, …, ⌊m/2⌋. So, the value of P_{1}(x; m, n) can be computed explicitly for ⌊m/2⌋ + 1 distinct specializations, which suffices to compute P_{1}(x; m, n) explicitly by Lagrange interpolation.

This finishes the proof of Theorem 2. □

We have used Theorem 2 to evaluate the determinant D(x, x + m; n) for m = 0, 1, 2, 3, 4. This is the contents of the next Corollary.

Corollary 3. Let x and n be nonnegative integers. Then the determinant

D(x, x + m; n) = det_{0≤i,j≤n−1} ( ∑_{x+2i−j<r≤x+m+2j−i} \binom{2x + m + i + j}{r})

for m = 0 equals

\{ \begin{matrix}∏_{i=0}^{n−1} (\frac{i! (2x + i)! (3x + 2i + 2)_{i}^{2}}{(x + 2i)!^{2}} ) \frac{∏_{i=0}^{n/2−1}(2x + 2i + 1)}{(n − 1)!!} & n even \\ 0 & n odd \end{matrix}

= \{ \begin{matrix}∏_{i=0}^{n−1} \frac{(3x + 2i + 2)_{i}^{2}}{(x + 2i)!^{2}} ∏_{i=0}^{n/2−1} ((2i)!^{2} (2x + 2i + 1)!^{2}) & n even \\ 0 & n odd, \end{matrix} (3.69)

for m = 1, n ≥ 1, equals

∏_{i=0}^{n−1} (\frac{i! (2x + i + 1)! (3x + 2i + 3)_{i} (3x + 2i + 4)_{i}}{(x + 2i)! (x + 2i + 1)!} ) \frac{∏_{i=0}^{⌊n/2⌋−1}(2x + 2i + 3)}{(2 ⌊n/2⌋ − 1)!!}, (3.70)

for m = 2, n ≥ 2, equals

∏_{i=0}^{n−1} (\frac{i! (2x + i + 2)! (3x + 2i + 4)_{i} (3x + 2i + 6)_{i}}{(x + 2i)! (x + 2i + 2)!} ) \frac{∏_{i=0}^{⌊n/2⌋−1}(2x + 2i + 3)}{(2 ⌊n/2⌋ − 1)!!}

× \frac{1}{(x + 1)} · \{ \begin{matrix}(x + n + 1) & n even \\ (2x + n + 2) & n odd, \end{matrix} (3.71)

for m = 3, n ≥ 3, equals

∏_{i=0}^{n−1} (\frac{i! (2x + i + 3)! (3x + 2i + 5)_{i} (3x + 2i + 8)_{i}}{(x + 2i)! (x + 2i + 3)!} ) \frac{∏_{i=0}^{⌊n/2⌋−1}(2x + 2i + 5)}{(2 ⌊n/2⌋ − 1)!!}

× \frac{1}{(x + 1)} · \{ \begin{matrix}(x + 2n + 1) & n even \\ (3x + 2n + 5) & n odd, \end{matrix} (3.72)

and for m = 4, n ≥ 4, equals

∏_{i=0}^{n−1} (\frac{i! (2x + i + 4)! (3x + 2i + 6)_{i} (3x + 2i + 10)_{i}}{(x + 2i)! (x + 2i + 4)!} ) \frac{∏_{i=0}^{⌊n/2⌋−1}(2x + 2i + 5)}{(2 ⌊n/2⌋ − 1)!!}

× \frac{1}{(x + 1)(x + 2)} · \{ \begin{matrix}(x^{2} + (4n + 3)x + 2(n^{2} + 4n + 1)) & n even \\ (2x + n + 4)(2x + 2n + 4) & n odd. \end{matrix} (3.73)

□

At this point we remark that (3.69) combined with Theorem 1, item (3), (2.2a), settles the “n even” case of the Conjecture in the introduction, see Theorem 11.

We have computed P_{1}(x; m, n) for further values of m. Together with the cases m = 0, 1, 2, 3, 4 that are displayed in Corollary 3, the results suggest that actually a stronger version of Theorem 2 is true.

Conjecture. Let x, m, n be nonnegative integers with m ≤ n. Then

D(x, x + m; n) = det_{0≤i,j≤n−1} ( ∑_{x+2i−j<r≤x+m+2j−i} \binom{2x + m + i + j}{r})

= ∏_{i=1}^{n−1} (\frac{i! (2x + m + i)! (3x + m + 2i + 2)_{i} (3x + 2m + 2i + 2)_{i}}{(x + 2i)! (x + m + 2i)!} )

× \frac{(2x + m)!}{(x + ⌊m/2⌋)! (x + m)!} · \frac{∏_{i=0}^{⌊n/2⌋−1}(2x + 2 ⌈m/2⌉ + 2i + 1)}{(2 ⌊n/2⌋ − 1)!!} · P_{3}(x; m, n), (3.74)

where P_{3}(x; m, n) is a polynomial in x of exact degree ⌊m/2⌋. In addition, if the cases n even and n odd are considered separately, the coefficient of x^{e} in P_{3}(x; m, n) is a polynomial in n of degree ⌊m/2⌋ − e with positive integer coefficients.

Note that P_{3}(x; m, n) = P_{1}(x; m, n) · (2 ⌊n/2⌋ − 1)!!/ ∏_{i=0}^{n−1} i! (compare (3.74) and (3.3)).

Possibly, this Conjecture (at least the statement about the degree of P_{3}(x; m, n)) can be proved by examining the considerations in Step 5 and Step 6 of the proof of Theorem 2 in more detail.

4. Another two-parameter family of determinants. The goal of this section is to evaluate the determinant in (2.2b). We shall consider the generalized determinant

E(x, y; n) := det_{0≤i,j≤n−1} (\frac{(x + y + i + j − 1)! (y − x + 3j − 3i)}{(x + 2i − j + 1)! (y + 2j − i + 1)!}) ,  (4.1)

for integral x and y. (On the side, we remark that E(x, y; n) would also make sense for complex x and y if the factorials are interpreted as the appropriate gamma functions. Proposition 4 below, together with its proof, actually holds in this more general sense. This applies also to Proposition 5, as long as m is a nonnegative integer, to Corollary 6, to Theorems 8 and 9, and their proofs.) E(x, y; n) reduces to the determinant in (2.2b) when n is replaced by n − 1 and y is set equal to x, apart from the factor ∏_{i=0}^{n−1}(3x + 3i + 4)^{2} that can be taken out of the determinant in (2.2b).

Ultimately, in Theorem 8 at the end of this section, we shall be able to evaluate the determinant E(x, y; n) completely, for independent x and y. This is different from the determinant D(x, y; n) of the previous section. But, there is a long way to go. The first result of this section, Proposition 4, describes how the determinant E(x, y; n) factors for independent x and y, however, leaving one factor undetermined. It provides the ground work for the subsequent Proposition 5 that makes it possible to evaluate E(x, y; n) when the difference m = y −x is fixed. This is then done explicitly for two cases in Corollary 6. This includes the case m = 0 which gives the evaluation of the determinant in (2.2b) that we are particularly interested in. The rest of the section is then dedicated to the complete evaluation of the determinant E(x, y; n), for independent x and y. This is finally done in Theorem 8. Before, in Lemma 7, we collect information about the polynomial factor P_{4}(x, y; n) in the factorization (4.2) of E(x, y; n). The proof of Theorem 8 then combines this information with the evaluation of E(x, x + 1; n), which is the second case of Corollary 6.

Proposition 4. Let x, y, n be nonnegative integers. Then

E(x, y; n) = det_{0≤i,j≤n−1} (\frac{(x + y + i + j − 1)! (y − x + 3j − 3i)}{(x + 2i − j + 1)! (y + 2j − i + 1)!})

= ∏_{i=0}^{n−1} (\frac{(x + y + i − 1)! (2x + y + 2i + 1)_{i} (x + 2y + 2i + 1)_{i}}{(x + 2i + 1)! (y + 2i + 1)!} ) · P_{4}(x, y; n), (4.2)

where P_{4}(x, y; n) is a polynomial in x and y of degree n.

Proof. Again, the proof is divided into several steps. The strategy is very similar to the proof of Theorem 2. First, we transform E(x, x + m; n) into a multiple of another determinant, namely E_{B}(x, y; n), by (4.3)–(4.5), which is a polynomial in x and y, then identify as many factors of the new determinant as possible (as a polynomial in x and y), and finally find a bound for the degree of the remaining polynomial factor.

Step 1. An equivalent statement of the Theorem. We take as many common factors out of the i-th row of E(x, y; n), i = 0, 1, …, n − 1, as possible, such that the entries become polynomials in x and y. To be precise, we take

\frac{(x + y + i − 1)!}{(x + 2i + 1)! (y + 2n − i − 1)!}

out of the i-th row, i = 0, 1, …, n − 1. This gives

E(x, y; n) = ∏_{i=0}^{n−1} \frac{(x + y + i − 1)!}{(x + 2i + 1)! (y + 2n − i − 1)!}

× det_{0≤i,j≤n−1} ((x + y + i)_{j} (x + 2i − j + 2)_{j} (y + 2j − i + 2)_{2n−2j−2} (y − x + 3j − 3i)). (4.3)

For convenience, let us denote the determinant in (4.3) by E_{A}(x, y; n). In fact, there are more factors that can be taken out of E_{A}(x, y; n) under the restriction that the entries of the determinant continue to be polynomials. To this end, we multiply the i-th row of E_{A}(x, y; n) by (y + 2n − i)_{i}, i = 0, 1, …, n − 1, and divide the j-th column by (y + 2j + 2)_{2n−2j−2}, j = 0, 1, …, n − 1. This leads to

∏_{i=0}^{n−1}(y + 2n − i)_{i} ∏_{j=0}^{n−1} \frac{1}{(y + 2j + 2)_{2n−2j−2}} · E_{A}(x, y; n)

= det_{0≤i,j≤n−1} ((x + y + i)_{j} (x + 2i − j + 2)_{j} (y + 2j − i + 2)_{i} (y − x + 3j − 3i)), (4.4)

or, if we denote the determinant in (4.4) by E_{B}(x, y; n),

E_{A}(x, y; n) = ∏_{i=0}^{n−1}(y + 2i + 2)_{n−i−1} · E_{B}(x, y; n).  (4.5)

A combination of (4.2), (4.4), and (4.5) then implies that Proposition 4 is equivalent to the statement:

With E_{B}(x, y; n) the determinant in (4.4), there holds

E_{B}(x, y; n) = ∏_{i=0}^{n−1} ((2x + y + 2i + 1)_{i} (x + 2y + 2i + 1)_{i}) · P_{4}(x, y; n), (4.6)

where P_{4}(x, y; n) is a polynomial in x and y of degree n.

Step 2. ∏_{i=0}^{n−1} ((2x + y + 2i + 1)_{i} (x + 2y + 2i + 1)_{i}) is a factor of E_{B}(x, y; n). There are not many differences to Step 3 of the proof of Theorem 2. So we shall be brief here.

We first consider just one half of this product, ∏_{i=0}^{n−1}(2x + y + 2i + 1)_{i}. Let us concentrate on a typical factor (2x + y + 2i + l + 1), 0 ≤ i ≤ n − 1, 0 ≤ l < i. We claim that for each such factor there is a linear combination of the rows that vanishes if the factor vanishes. More precisely, we claim that for any i, l with 0 ≤ i ≤ n − 1, 0 ≤ l < i there holds

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 2)_{2i−2s}}{(−x − 2i − l + s − 1)_{i−s}}

· (row s of E_{B}(x, −2x − 2i − l − 1; n)) = (row i of E_{B}(x, −2x − 2i − l − 1; n)). (4.7)

Restricting (4.7) to the j-th column, it is seen that this means to check

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 2)_{2i−2s}}{(−x − 2i − l + s − 1)_{i−s}}
× (−x − 2i − l + s − 1)_{j} (x + 2s − j + 2)_{j}
× (−2x − 2i − l + 2j − s + 1)_{s} (−3x − 2i − l + 3j − 3s − 1)

= (−x − i − l − 1)_{j} (x + 2i − j + 2)_{j} (−2x − 3i − l + 2j + 1)_{i} (−3x − l + 3j − 5i − 1).

This is easily done by observing that it is equivalent to (3.16). Arguments that are similar to those after (3.18) then show that the complete product ∏_{i=0}^{n−1}(2x+y+2i+1)_{i} divides E_{B}(x, y; n).

The reasoning that ∏_{i=0}^{n−1}(x + 2y + 2i + 1)_{i} is a factor of E_{B}(x, y; n) is similar. Also here, let us concentrate on a typical factor (x + 2y + 2j + l + 1), 0 ≤ j ≤ n − 1, 0 ≤ l < j. This time we claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 0 ≤ j ≤ n − 1, 0 ≤ l < j there holds

∑_{s=l}^{⌊(j+l)/2⌋} \frac{(2j − 3s + l)}{(j − s)} \frac{(j − 2s + l + 1)_{s−l}}{(s − l)!} (y + 2s + 2)_{2j−2s}

· (column s of E_{B}(−2y − 2j − l − 1, y; n))

= (column j of E_{B}(−2y − 2j − l − 1, y; n)). (4.8)

Restricting to the i-th row, we see that this means to check

∑_{s=l}^{⌊(j+l)/2⌋} \frac{(2j − 3s + l)}{(j − s)} \frac{(j − 2s + l + 1)_{s−l}}{(s − l)!} (y + 2s + 2)_{2j−2s}

× (−y − 2j − l + i − 1)_{s} (−2y − 2j − l + 2i − s + 1)_{s}
× (y + 2s − i + 2)_{i} (3y + 2j + l − 3i + 3s + 1)

= (−y − 2j − l + i − 1)_{j} (−2y − 3j − l + 2i + 1)_{j} (y + 2j − i + 2)_{i} (3y + 5j + l − 3i + 1).

The observation that this summation is equivalent to (3.24) with ȳ = y establishes the claim. Similarly to as before, this eventually shows that the complete product ∏_{i=0}^{n−1}(x + 2y + 2i + 1)_{i} divides E_{B}(x, y; n).

Altogether, this implies that ∏_{i=0}^{n−1} ((2x + y + 2i + 1)_{i}(x + 2y + 2i + 1)_{i}) divides E_{B}(x, y; n), as desired.

Step 3. P_{4}(x, y; n) is a polynomial in x and y of degree n. We shall prove that E_{A}(x, y; n) (which is defined to be the determinant in (4.3)) is a polynomial in x and y of (total) degree 3\binom{n}{2}+n. By (4.5) this would imply that E_{B}(x, y; n) is a polynomial in x and y of degree 2\binom{n}{2} + n, and so, by (4.6), that P_{4}(x, y; n) is a polynomial in x and y of degree n, as desired.

Here we need to consider the generalized determinant

\overline{E}_{A}(x, y, z(0), z(1), …, z(n − 1); n) = \overline{E}_{A}(n)

which arises from E_{A}(x, y; n) by replacing each occurence of i in row i by an indeterminate, z(i) say, i = 0, 1, …, n − 1,

\overline{E}_{A}(x, y, z(0), z(1), …, z(n − 1); n) = \overline{E}_{A}(n)

:= det_{0≤i,j≤n−1} ((x + y + z(i))_{j} (x + 2z(i) − j + 2)_{j}

· (y + 2j − z(i) + 2)_{2n−2j−2} (y − x + 3j − 3z(i))). (4.9)

This determinant is a polynomial in x, y, z(0), z(1), …, z(n − 1). We shall prove that the degree in x and y of this determinant is 3\binom{n}{2} + n, which clearly implies our claim upon setting z(i) = i, i = 0, 1, …, n − 1.

Obviously, the total degree of \overline{E}_{A}(n) in x, y, z(0), z(1), …, z(n − 1) is at most 4\binom{n}{2}+n. However, actually it is exactly equal to this upper bound, since the monomial

y^{3\binom{n}{2}+n}z(0)^{0}z(1)^{1} ⋯ z(n − 1)^{n−1}

occurs only in the product of the main diagonal of the determinant with nonzero coefficient, and therefore cannot cancel. On the other hand, when z(i_{1}) = z(i_{2}) for some i_{1} ≠ i_{2}, the rows i_{1} and i_{2} in \overline{E}_{A}(n) are identical. Hence \overline{E}_{A}(n) vanishes in this case. This shows that the product ∏_{0≤i<j≤n−1}(z(j)−z(i)) divides \overline{E}_{A}(n). Therefore, the degree in x and y of \overline{E}_{A}(n) equals (4\binom{n}{2} + n) − \binom{n}{2} = 3\binom{n}{2} + n, which is what we need.

This finishes the proof of Proposition 4. □

As we already mentioned, it is possible to compute the polynomial P_{4}(x, y; n) explicitly, see Theorem 8. However, we are not yet in the position to do so. First we restrict ourselves to the situation that was studied in Section 3 for the determinant (3.1), namely when the difference m = y − x is a fixed integer. In this situation, it turns out that the degree of P_{4}(x, y; n) = P_{4}(x, x + m; n), now as a polynomial in x of course, shrinks significantly. To be precise, the degree can be at most ⌊n/2⌋. We prove this fact in Proposition 5 below. Moreover, we identify several factors of P_{4}(x, x + m; n), which will be of great help in the proof of Corollary 6.

Proposition 5. Let x, m, n be nonnegative integers with m ≤ n. Then,

E(x, x + m; n) = det_{0≤i,j≤n−1} (\frac{(2x + m + i + j − 1)! (m + 3j − 3i)}{(x + 2i − j + 1)! (x + m + 2j − i + 1)!})

= ∏_{i=0}^{n−1} (\frac{(2x + m + i − 1)! (3x + m + 2i + 1)_{i} (3x + 2m + 2i + 1)_{i}}{(x + 2i + 1)! (x + m + 2i + 1)!} )

× (x + m)_{⌊n/2⌋−⌊m/2⌋} · P_{5}(x; m, n), (4.10)

where P_{5}(x; m, n) is a polynomial in x of degree ≤ ⌊m/2⌋.

Proof. Much of the required work has already been done. In particular, if we set y = x + m in (4.2) and compare with (4.10), we obtain

P_{4}(x, x + m; n) = (x + m)_{⌊n/2⌋−⌊m/2⌋} · P_{5}(x; m, n).  (4.11)

So what remains to prove is that (x + m)_{⌊n/2⌋−⌊m/2⌋} is a factor of P_{4}(x, x + m; n), and that the degree of P_{4}(x, x + m; n) is at most ⌊n/2⌋. The first fact is established in Step 1, the second in Step 2.

Step 1. (x + m)_{⌊n/2⌋−⌊m/2⌋} is a factor of P_{4}(x, x + m; n). Fix an integer v,

m ≤ v ≤ \frac{m + n − 1}{2}.  (4.12)

We shall show that x + v is a factor of P_{4}(x, x + m; n), or equivalently, that x = −v is a zero of P_{4}(x, x + m; n). The polynomial P_{4}(x, x + m; n) is defined by (4.6), with y = x + m, i.e., by

E_{B}(x, x + m; n) = ∏_{i=0}^{n−1} ((3x + m + 2i + 1)_{i} (3x + 2m + 2i + 1)_{i}) · P_{4}(x, x + m; n), (4.13)

where E_{B}(x, x+m; n) is the determinant in (4.4) with y = x+m. So, we would like to set x = −v in (4.13), prove that E_{B}(−v, −v + m; n) equals 0, that the product on the right-hand side of (4.13) is nonzero, and conclude that therefore P_{4}(−v, −v + m; n) must be 0. However, the product on the right-hand side of (4.13) unfortunately (usually) is 0 for x = −v. This makes it necessary to cancel first all factors (x + v) that occur in the product, and only then set x = −v.

To accomplish this, we have to “generate” these factors on the left-hand side. This is done by reading through Step 2 of the proof of Proposition 4 with y = x + m. To make this more precise, observe that x + v divides a typical factor 3x + m + 2i + l + 1, 0 ≤ i ≤ n − 1, 0 ≤ l < i, of the first half of the product in (4.13) if and only if 3v = m + 2i + l + 1. So, for each solution (i, l) of

3v = m + 2i + l + 1, with 0 ≤ i ≤ n − 1, 0 ≤ l < i,  (4.14)

we subtract the linear combination

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 2)_{2i−2s}}{(−x − 2i − l + s − 1)_{i−s}}
· (row s of E_{B}(x, x + m; n)) (4.15)

of rows of E_{B}(x, x + m; n) from row i of E_{B}(x, x + m; n). Let us denote the resulting determinant by Ẽ_{B}(x; m, n). By (4.7), the effect is that (3x+m+2i+l+1) = (3x+3v) (the equality being due to (4.14)), and hence (x + v), is a factor of each entry of the i-th row of Ẽ_{B}(x; m, n), for each solution (i, l) of (4.14). For later use we record that the (i, j)-entry of Ẽ_{B}(x; m, n), (i, l) a solution of (4.14), reads

(2x + m + i)_{j} (x + 2i − j + 2)_{j} (x + m + 2j − i + 2)_{i} (m + 3j − 3i)

− ∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 2)_{2i−2s}}{(−x − 2i − l + s − 1)_{i−s}}

× (2x + m + s)_{j} (x + 2s − j + 2)_{j} (x + m + 2j − s + 2)_{s} (m + 3j − 3s). (4.16)

Similar considerations concern the second half of the product in (4.13). Omitting the details, for each solution (j, l) of

3v = 2m + 2j + l + 1, with 0 ≤ j ≤ n − 1, 0 ≤ l < j,  (4.17)

we subtract the linear combination

∑_{s=l}^{⌊(j+l)/2⌋} \frac{(2j − 3s + l)}{(j − s)} \frac{(j − 2s + l + 1)_{s−l}}{(s − l)!} (x + m + 2s + 2)_{2j−2s}

· (column s of Ẽ_{B}(x; m, n))

of columns of Ẽ_{B}(x; m, n) (we definitely mean Ẽ_{B}(x; m, n), and not E_{B}(x; m, n)) from column j of Ẽ_{B}(x, x + m; n). By (4.8), each entry of the j-th column of the new determinant will have (x + v) as a factor. We remark that entries that were changed by a row and column operations will now have (x + v)^{2} as a factor. Now we take (x + v) out of the i-th row, for each solution (i, l) of (4.14), and we take (x + v) out of the j-th column, for each solution (j, l) of (4.17). We denote the resulting determinant by \overline{E}_{B}(x; m, n). Thus, we have

E_{B}(x, x + m; n) = (x + v)^{#(solutions (i,l) of (4.14))+#(solutions (j,l) of (4.17))}\overline{E}_{B}(x; m, n).

Plugging this into (4.13), we see that now all factors (x + v) can be cancelled on both sides, so that we obtain

\overline{E}_{B}(x; m, n) = C(x; m, n) P_{4}(x, x + m; n),

for some C(x; m, n) that does not vanish for x = −v. Hence, if we are able to prove that \overline{E}_{B}(−v; m, n) = 0, it would follow that P_{4}(−v, −v + m; n) = 0, which is what we want to establish.

So we are left with showing that \overline{E}_{B}(−v; m, n) = 0. This will be implied by the following two claims: The matrix of which \overline{E}_{B}(−v; m, n) is the determinant has a block form (see (4.18)), where

Claim 1. the upper-right block, consisting of the entries that are in one of the rows 0, 1, …, 2v − m and one of the columns 2v − m + 1, 2v − m + 2, …, n − 1, is a zero matrix, and where

Claim 2. the determinant of the upper-left block, N, consisting of the entries that are in one of the rows 0, 1, …, 2v − m and one of the columns 0, 1, …, 2v − m, equals 0.

N 0 ∗ ∗ _{← i=2v−m}^{j =2v−m}^{↓}  (4.18)

For, the determinant of a block matrix of the form (4.18) equals the product of the determinants of the upper-left block and the lower-right block, the first determinant being equal to 0 by Claim 2.

Claim 1 is most obvious for all the entries that did not change in the transition from E_{B}(x, x + m; n) to \overline{E}_{B}(x; m, n). For, the (i, j)-entry of E_{B}(x, x + m; n), by its definition in (4.4), is

(−2v + m + i)_{j} (−v + 2i − j + 2)_{j} (−v + m + 2j − i + 2)_{i} (m + 3j − 3i). (4.19)

Clearly, if 0 ≤ i ≤ 2v − m and 2v − m + 1 ≤ j ≤ n − 1, we have (−2v + m + i)_{j} = 0, and so the complete expression in (4.19) is 0.

On the other hand, let us consider an (i, j)-entry of \overline{E}_{B}(x; m, n) that changed in the transition from E_{B}(x, x + m; n) to \overline{E}_{B}(x; m, n). First we want to know, where such an entry could be located. If it changed under a row operation, then (i, l) is a solution of (4.14), for some l. By (4.14) we have

m + 2i + 1 ≤ m + 2i + l + 1 = 3v and 3v = m + 2i + l + 1 ≤ m + 3i,

and so,

v − \frac{m}{3} ≤ i ≤ \frac{3v − m − 1}{2}.  (4.20)

If the (i, j)-entry changed under a column operation, then (j, l) is a solution of (4.17), for some l. Similar arguments then give, using (4.17), that

v − \frac{2m}{3} ≤ j ≤ \frac{3v − 2m − 1}{2}.  (4.21)

In particular we have j < 2v − m, so an (i, j)-entry that is located in the upper-right block, which we are currently interested in, did not change under a column operation.

But it could have changed under a row operation. Such an (i, j)-entry is given by (4.16) divided by (x + v). (Recall that (4.16) was the expression for an (i, j)-entry that changed under a row operation before we factored (x + v) out of the i-th row.) Thus, it can be written as

\frac{(2x + m + i)_{2v−m−i+1}}{(x + v)} ((2x + 2v + 1)_{i+j−2v+m−1} (x + 2i − j + 2)_{j}

· (x + m + 2j − i + 2)_{i} (m + 3j − 3i) − ∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!}

· \frac{(x + 2s + 2)_{2i−2s}}{(−x − 2i − l + s − 1)_{i−s}} (2x + m + s)_{i−s} (2x + 2v + 1)_{j+s−2v+m−1}

(x + 2s − j + 2)_{j} (x + m + 2j − s + 2)_{s} (m + 3j − 3s)). (4.22)

We have to show that (4.22) vanishes for x → −v. Because of the denominators, it is not even evident that (4.22) is well-defined when x → −v. However, by (4.20) we have 2v − m − i ≥ (v − m + 1)/2 ≥ 0, the last inequality being due to our assumption v ≥ m. Hence,

\frac{(2x + m + i)_{2v−m−i+1}}{(x + v)} = (2x + m + i)_{2v−m−i} · 2,

and so the first term in (4.22) is well-defined when x → −v. Furthermore, the denominator in the sum in (4.22) (neglecting the terms that do not depend on x) when x → −v becomes

(v − 2i − l + s − 1)_{i−s} = (v − 2i − l + s − 1) ⋯ (v − i − l − 2).  (4.23)

By (4.14) and (4.20) we have v−i−l−2 = −2v+i+m−1 ≤ \frac{1}{2}(−v+m−3) < 0, again the last inequality being due to our assumption v ≥ m. Therefore, all the terms in (4.23) are nonzero, which means that the denominator in the sum in (4.22) is nonzero when x → −v. Hence, (4.22) is well-defined for x → −v. To demonstrate that it actually vanishes for x → −v, we show that the second term in (4.22) (the term in big parentheses) equals 0 for x = −v.

To see this, set x = −v, and by (4.14) replace l by 3v − 2i − m − 1 in the sum (4.22), and then convert it into hypergeometric notation, to obtain

2 (3 + 6i + 3j + 4m − 9v) (1)_{v+j−2i−2} × (−4v + 2i + 2j + 2m + 3)_{3v−2i−m−1}(5v − 4i − j − 2m)_{−6v+6i+j+2m+2}

×_{6}F_{5}[ \begin{matrix}−2i − j − \frac{4m}{3} + 3v, \frac{1}{3} − 2i − \frac{2m}{3} + 2v, −\frac{1}{2} − \frac{3i}{2} − \frac{m}{2} + \frac{3v}{2} , \\ −1 − 2i − j − \frac{4m}{3} + 3v, −\frac{2}{3} − 2i − \frac{2m}{3} + 2v, −3i − m + 3v, \end{matrix}

\begin{matrix}−\frac{3i}{2} − \frac{m}{2} + \frac{3v}{2} , −1 − 2i + j + v, −2 − 2i − 2j − 2m + 4v \\ −2i − \frac{j}{2} − m + \frac{5v}{2} , \frac{1}{2} − 2i − \frac{j}{2} − m + \frac{5v}{2} \end{matrix} ; 1] . (4.24)

The _{6}F_{5}-series can be summed by means of Lemma A6. Then, after simplification, (4.24) becomes

(i + j − 2v + m − 1)! (−v + 2i − j + 2)_{j} (−v + m + 2j − i + 2)_{i} (m + 3j − 3i),

which is exactly the first term in big parentheses in (4.22) for x = −v. Therefore, the term in big parentheses in (4.22) vanishes for x = −v. This settles Claim 1.

Next we turn to Claim 2. We have to prove that the determinant of the matrix N, consisting of the entries of \overline{E}_{B}(−v; m, n) that are in one of the rows 0, 1, …, 2v − m and one of the columns 0, 1, …, 2v−m (recall (4.18)), equals 0. We do this by locating enough zeros in the matrix N.

We concentrate on the entries that did not change in the transition from E_{B}(x, x+ m; n) to \overline{E}_{B}(x; m, n). For the location of the various regions in the matrix N that we are going to describe, always consult Figure 2 which gives a rough sketch.

N = [figure: i = 0; i = ⌈ \frac{v−1}{2} ⌉; i = ⌈v − \frac{m}{3} ⌉ − 2 + χ(m ≡ 0(3)); i = ⌊ \frac{3v−m−1}{2} ⌋ + 1; i = 2v − m; 0; j =; j =; _{⌈ \frac{v−m−1}{2} ⌉}; ⌈v − \frac{2m}{3} ⌉ − 1; j =; j =; ⌊_{\frac{3v−2m−1}{2}} ⌋ + 1; 2v − m; j =; i = \frac{v+j−2}{2}; j = \frac{v−m+i−2}{2}; i + j = 2v − m; I; II; IV; III]

Figure 2

By earlier considerations, an (i, j)-entry did not change if i is outside the range (4.20), i.e.,

0 ≤ i ≤ ⌈v − \frac{m}{3}⌉ − 1 or ⌊\frac{3v − m − 1}{2}⌋ + 1 ≤ i ≤ n − 1,  (4.25)

and if j is outside the range (4.21), i.e.,

0 ≤ j ≤ ⌈v − \frac{2m}{3}⌉ − 1 or ⌊\frac{3v − 2m − 1}{2}⌋ + 1 ≤ j ≤ n − 1.  (4.26)

As we already noted, such an (i, j)-entry is given by (4.19). The first term in (4.19) vanishes if and only if

i ≤ 2v − m and i + j > 2v − m.  (4.27)

The second term in (4.19) vanishes if and only if

⌈\frac{v − 1}{2}⌉ ≤ i ≤ \frac{v + j − 2}{2}.  (4.28)

The third term in (4.19) vanishes if and only if

⌈\frac{v − m − 1}{2}⌉ ≤ j ≤ \frac{v − m + i − 2}{2}.  (4.29)

Finally, the fourth term in (4.19) vanishes if and only if

m ≡ 0 (mod 3) and i = j + \frac{m}{3}.  (4.30)

Now we claim that in the following four regions of N all the entries are 0, except for the case v = m = 1, which we treat separately. Again, to get an idea of the location of these regions, consult Figure 2.

Region I: All (i, j)-entries with

⌈\frac{v − 1}{2}⌉ ≤ i ≤ ⌈v − \frac{m}{3}⌉ − 2 + χ(m ≡ 0 (mod 3))

and ⌈\frac{v − m − 1}{2}⌉ ≤ j ≤ ⌈v − \frac{2m}{3}⌉ − 1, (4.31)

where again χ(A)=1 if A is true and χ(A)=0 otherwise.

Region II: All (i, j)-entries with

⌈\frac{v − 1}{2}⌉ ≤ i ≤ ⌈v − \frac{m}{3}⌉ − 2 + χ(m ≡ 0 (mod 3))

and ⌊\frac{3v − 2m − 1}{2}⌋ + 1 ≤ j ≤ 2v − m. (4.32)

Region III: All (i, j)-entries with

⌊\frac{3v − m − 1}{2}⌋ + 1 ≤ i ≤ 2v − m and ⌈\frac{v − m − 1}{2}⌉ ≤ j ≤ ⌈v − \frac{2m}{3}⌉ − 1. (4.33)

Region IV: All (i, j)-entries with

⌊\frac{3v − m − 1}{2}⌋ + 1 ≤ i ≤ 2v − m and ⌊\frac{3v − 2m − 1}{2}⌋ + 1 ≤ j ≤ 2v − m. (4.34)

Instantly we observe that all four regions satisfy (4.25) and (4.26). So, all the entries in these regions are given by (4.19). Hence, to verify that all these entries are 0 we have to show that for each entry one of (4.27)–(4.30) is true. Of course, we treat the four regions separately.

ad Region I. First let i ≤ ⌈v − m/3⌉ − 2. In case that i ≤ j + m/3, we have

i ≤ \frac{i + j + \frac{m}{3}}{2} ≤ \frac{⌈v − \frac{m}{3}⌉ − 2 + j + \frac{m}{3}}{2} ≤ \frac{v − \frac{m}{3} + \frac{2}{3} − 2 + j + \frac{m}{3}}{2} = \frac{v + j − 2}{2} + \frac{1}{3}.

Combined with (4.31), this implies that (4.28) is satisfied. On the other hand, in case that i > j + m/3, or equivalently,

i ≥ j + \frac{m}{3} + \frac{1}{3},  (4.35)

we have, using the last inequality in (4.31),

j ≤ \frac{i + j − \frac{m}{3} − \frac{1}{3}}{2} ≤ \frac{i + ⌈v − \frac{2m}{3}⌉ − 1 − \frac{m}{3} − \frac{1}{3}}{2}

≤ \frac{i + v − \frac{2m}{3} + \frac{2}{3} − 1 − \frac{m}{3} − \frac{1}{3}}{2} = \frac{v − m + i − 2}{2} + \frac{2}{3}.

Combined with (4.31), this implies that (4.29) is satisfied, unless j = (v−m+i−1)/2. But if we plug this into (4.35), we obtain i ≥ v − m/3 − 1/3, a contradiction to our assumption i ≤ ⌈v − m/3⌉ − 2.

Collecting our results so far, we have seen that if m ≡ 1, 2 (mod 3), then each (i, j)-entry in region I satisfies (4.28) or (4.29). If m ≡ 0 (mod 3), region I also contains entries from row i = v − m/3 − 1. First let j ≤ v − (2m)/3 − 2. Then it is immediate that (4.29) is satisfied. If j = v − (2m)/3 − 1, then (4.30) is satisfied. This shows that if m ≡ 0 (mod 3) then an (i, j)-entry in region I satisfies (4.28), (4.29), or (4.30).

ad Region II. Here, by (4.32), we have

i + j ≥ ⌈\frac{v − 1}{2}⌉ + ⌊\frac{3v − 2m − 1}{2}⌋ + 1 = 2v − m.

Hence, (4.27) is satisfied, except when i = ⌈(v − 1)/2⌉ and j = ⌊(3v − 2m − 1)/2⌋+1. But in that case there holds (4.28), apart from a few exceptional cases. For, if v ≠ 0, 2 (and v ≥ 0 of course) then

⌈\frac{v − 1}{2}⌉ ≤ \frac{v + ⌊\frac{v−1}{2}⌋ − 1}{2}.

By the assumption v ≥ m it follows that

⌈\frac{v − 1}{2}⌉ ≤ \frac{v + (⌊\frac{3v−2m−1}{2}⌋ + 1) − 2}{2},  (4.36)

which is nothing but (4.28) with the current choices of i and j. Thus, (4.28) is satisfied except when v = m = 0, or v = 2 and m = 0, 1, 2. (There are no more cases because v ≥ m.) Starting from the back, the case v = m = 2 does not bother us, since in that case region II is empty (there is no i satisfying (4.32)). By inspection, it is seen that (4.36), and hence (4.28), also holds if v = 2 and m = 0 or 1. Finally, in case v = m = 0 we have i = ⌈(v − 1)/2⌉ = 0 and j = ⌊(3v − 2m − 1)/2⌋ + 1 = 0. Hence, (4.30) is satisfied.

ad Region III. By (4.33) we have

i + j ≥ ⌊\frac{3v − m − 1}{2}⌋ + 1 + ⌈\frac{v − m − 1}{2}⌉ = 2v − m.

Hence again, (4.27) is satisfied, except when i = ⌊(3v − m − 1)/2⌋ + 1 and j = ⌈(v − m − 1)/2⌉. In that case there holds (4.29), apart from a few special cases. For, if w is a positive integer, then

⌈\frac{w − 1}{2}⌉ ≤ \frac{w + ⌊\frac{w−1}{2}⌋}{2}.

Setting w = v − m in this inequality we obtain for v > m and v ≥ 1 the inequality

⌈\frac{v − m − 1}{2}⌉ ≤ \frac{v − m + (⌊\frac{3v−m−1}{2}⌋ + 1) − 2}{2}.  (4.37)

This is exactly (4.29) with the current choices for i and j. Thus, (4.29) is satisfied except when v = m or v = 0. (Recall that there are no more cases because of v ≥ m.) But (4.37), and hence (4.29), holds in more cases. Namely, by inspection, if v = m, then (4.37) holds for v ≥ 2. So, the only cases in which (4.37) is not true are v = m = 0 and v = m = 1. The case v = m = 0 does not bother us, since in that case region III is empty (there is no j satisfying (4.33)). The case v = m = 1 is the exceptional case that is treated separately.

ad Region IV. By (4.34) we have

i + j ≥ ⌊\frac{3v − m − 1}{2}⌋ + 1 + ⌊\frac{3v − 2m − 1}{2}⌋ + 1 ≥ 3v − \frac{3m}{2} + 1 > 2v − m,

the last inequality being again due to the assumption v ≥ m. Hence, (4.27) is satisfied.

Consequently, if we are not in the case v = m = 1, then the rows ⌈(v − 1)/2⌉ , …, ⌈v − m/3⌉−2+χ(m ≡ 0 (mod 3)), ⌊(3v − m − 1)/2⌋+1, …, 2v−m are rows with zeros in columns ⌈(v − m − 1)/2⌉ , …, ⌈v − (2m)/3⌉−1, ⌊(3v − 2m − 1)/2⌋+1, …, 2v− m. These are

⌈v − \frac{m}{3}⌉ − 1 + χ(m ≡ 0 (mod 3)) − ⌈\frac{v − 1}{2}⌉ + 2v − m − ⌊\frac{3v − m − 1}{2}⌋ (4.38)

rows, containing possibly nontrivial entries in only

⌈\frac{v − m − 1}{2}⌉ + ⌊\frac{3v − 2m − 1}{2}⌋ − ⌈v − \frac{2m}{3}⌉ + 1  (4.39)

columns. By simple algebra, the difference between (4.38) and (4.39) equals

m + ⌈−\frac{m}{3}⌉ + ⌈−\frac{2m}{3}⌉ + χ(m ≡ 0 (mod 3)).  (4.40)

As is easily verified, the expression (4.40) equals 1 always. So we have found N + 1 rows (with N the expression in (4.39)) that actually live in ℝ^{N} (ℝ denoting the set of real numbers). Hence, they must be linearly dependent. This implies that the determinant of N must be 0.

Finally we settle the case v = m = 1. The matrix N then is a 2 × 2 matrix (cf. Figure 2) in which column 1 vanishes. For, i = 0 and j = 1 satisfy (4.25), (4.26), and (4.28), while i = 1 and j = 1 satisfy (4.25), (4.26), and (4.27). Hence, det(N) = 0.

Altogether, this establishes that P_{4}(x, x + m; n) vanishes for x = −v, m ≤ v ≤ (n + m − 1)/2, so that (x + m)_{⌊(n−m+1)/2⌋} is a factor of P_{4}(x, x + m; n). Since

⌊\frac{n − m + 1}{2}⌋ = \{ \begin{matrix}⌊\frac{n}{2}⌋ − ⌊\frac{m}{2}⌋ + 1 & n odd, m even \\ ⌊\frac{n}{2}⌋ − ⌊\frac{m}{2}⌋ & otherwise, \end{matrix}

it follows that (x + m)_{⌊n/2⌋−⌊m/2⌋} is a factor of P_{4}(x, x + m; n), as desired.

Step 2. The degree of P_{4}(x, x + m; n) is at most ⌊n/2⌋. Fortunately, this was, implicitly, already proved in Step 5 of the proof of Theorem 2. To see this, we examine parts of Step 5 in more detail and relate them to P_{4}(x, x + m; n).

First we go back to (3.37). In what follows after (3.37), it is shown that the degree in x of the polynomial (3.37) is at most 2\binom{n}{2} + \binom{n−1}{2} + ⌊(n − 1)/2⌋ + ⌊m/2⌋. Now, a closer look at the manipulations before (3.37) unfolds that (3.37) equals the first term on the right-hand side of (3.27). However, this first term on the right-hand side of (3.27) is nothing else but the (0, 0)-entry of the determinant in (3.26) times the minor of the same determinant consisting of rows 1, 2, …, n − 1, and columns 1, 2, …, n − 1. This minor is

det_{1≤i,j≤n−1} ((2x + m + z(i) + 1)_{j−1} (x + 2z(i) − j + 2)_{j−1}

· (x + m + 2j − z(i) + 2)_{2n−2j−2} (m + 3j − 3z(i)))

= det_{0≤i,j≤n−2} ((2x + m + z(i + 1) + 1)_{j} (x + 2z(i + 1) − j + 1)_{j}

· (x + m + 2j − z(i + 1) + 4)_{2n−2j−4} (m + 3j + 3 − 3z(i + 1))). (4.41)

The (0, 0)-entry of the determinant in (3.27) is S(x, x + m; n), which by its definition (3.7) is a polynomial in x of degree 2n − 2 + ⌊m/2⌋ (as is also remarked after (3.37)). So, the degree in x of the determinant in (4.41) is at most 3\binom{n−1}{2} + ⌊(n − 1)/2⌋. Now it should be noted that upon replacing n by n + 1, x by x − 1, and upon setting z(i + 1) = i + 1, i = 0, 1, …, n − 1, the right-hand side of (4.41) turns into the determinant in (4.3) with y = x + m, which by definition is E_{A}(x, x + m; n). Hence, the degree in x of E_{A}(x, x + m; n) is at most 3\binom{n}{2} + ⌊n/2⌋, and so, by (4.5) and (4.6), the degree in x of P_{4}(x, x + m; n) is at most ⌊n/2⌋.

This finishes the proof of Proposition 5. □

In the next step, we use Proposition 5 to evaluate the determinant E(x, x + m; n) for m = 0 and m = 1. The case m = 0 is the one that we need for the evaluation of the determinant in (2.2b), the case m = 1 is needed for the evaluation of E(x, y; n), for independent x and y, in the proof of Theorem 8.

Corollary 6. Let x and n be nonnegative integers. Then the determinant

E(x, x + m; n) = det_{0≤i,j≤n−1} (\frac{(2x + m + i + j − 1)! (m + 3j − 3i)}{(x + 2i − j + 1)! (x + m + 2j − i + 1)!})

for m = 0 equals

\{ \begin{matrix}\frac{n!}{(n/2)!} ∏_{i=0}^{n−1} (\frac{i! (2x + i − 1)! (3x + 2i + 1)_{i}^{2}}{(x + 2i + 1)!^{2}} ) · (x)_{n/2} & n even \\ 0 & n odd \end{matrix}

= \{ \begin{matrix}∏_{i=0}^{n−1} \frac{(3x + 2i + 1)_{i}^{2}}{(x + 2i + 1)!^{2}} ∏_{i=0}^{n/2−1} ((2x + 2i)!^{2} (2i + 1)!^{2}) & n even \\ 0 & n odd, \end{matrix} (4.42)

and for m = 1, n ≥ 1, equals

\frac{n!}{⌊n/2⌋!} ∏_{i=0}^{n−1} (\frac{i! (2x + i)! (3x + 2i + 2)_{i} (3x + 2i + 3)_{i}}{(x + 2i + 1)! (x + 2i + 2)!} ) · (x + 1)_{⌊n/2⌋}.  (4.43)

Proof. By Proposition 5 we know exactly how E(x, x + m; n) factors, except for the polynomial P_{5}(x; m, n). However, also by Proposition 5, for m = 0, 1 the degree of P_{5}(x; m, n) is at most 0. Hence, P_{5}(x; m, n) is a constant for m = 0 and for m = 1.

A combination of (4.6), with y = x + m, and (4.11) yields

P_{5}(x; m, n) = \frac{1}{(x + m)_{⌊n/2⌋−⌊m/2⌋}} ∏_{i=0}^{n−1} \frac{1}{(3x + m + 2i + 1)_{i} (3x + 2m + 2i + 1)_{i}}

× det_{0≤i,j≤n−1} ((2x + m + i)_{j} (x + 2i − j + 2)_{j} (x + m + 2j − i + 2)_{i} (m + 3j − 3i)). (4.44)

Thus, the (constant) value of P_{5}(x; m, n) can be determined, by finding an appropriate special value for x, which allows to evaluate the determinant in (4.44).

We choose x = − ⌊(n + m)/2⌋ + 1/2, m = 0, 1. With this choice for x, the denominator on the right-hand side of (4.44) does not vanish. So, everything is well-defined for this specialization. In addition, since (2x + m + i)_{j}, which is a term in each entry of the determinant, vanishes if i ≤ −2x − m = 2 ⌊(n + m)/2⌋ − m − 1 and i + j ≥ −2x − m + 1 = 2 ⌊(n + m)/2⌋ − m, for m = 0 and m = 1 the determinant takes on the form (3.68), where the submatrix M is empty or a 1×1 matrix. Therefore the determinant can be easily evaluated for this specialization. This gives P_{5}(x; m, n) for m = 0 and m = 1. Substitution of these values for P_{5}(x; m, n) into (4.10) yields the expressions (4.42) and (4.43). □

The evaluation for the special case m = x = 0 is implicitly in [2]. (It is equivalent to the determinant evaluation for det(v(n)) in Section 4 of [2].)

At this point we remark that (4.42) combined with Theorem 1, item (3), (2.2b), settles the “n odd” case of the Conjecture in the Introduction, see Theorem 11.

To be able to evaluate the determinant E(x, y; n) of (4.1) completely, for independent x and y, we need one more auxiliary result. It locates several zeros of the polynomial factor P_{4}(x, y; n) of E(x, y; n) (recall (4.2)).

Lemma 7. If u, v are nonnegative integers with u+v ≤ n−1, then P_{4}(−u, −v; n) = 0, with P_{4}(x, y; n) the polynomial in (4.2).

Proof. Let u, v be nonnegative integers with u+v ≤ n−1. The polynomial P_{4}(x, y; n) is defined by (4.6),

E_{B}(x, y; n) = ∏_{i=0}^{n−1} ((2x + y + 2i + 1)_{i} (x + 2y + 2i + 1)_{i}) · P_{4}(x, y; n), (4.45)

where E_{B}(x, y; n) is the determinant in (4.4). What we would like to do is to set x = −u and y = −v in (4.45), prove that E_{B}(−u, −v; n) equals 0, that the product on the right-hand side of (4.45) is nonzero, and conclude that therefore P_{4}(−u, −v; n) must be 0. However, the product on the right-hand side of (4.45) unfortunately (usually) is 0 for x = −u and y = −v. So we are in exactly the same situation as in Step 1 of Proposition 5. The specialization of P_{4}(x, y; n) that we are considering here is very different, though. Curiously enough, the arguments of Step 1 of Proposition 5 can still be used here, word by word, with suitable replacements of parameters. To get convinced that this is indeed the case, it will suffice to do the very beginning. Soon it will become clear that everything runs in parallel with Step 1 of Proposition 5.

To begin with, we set y = −v in (4.45). Before setting x = −u, we have to cancel all factors of the form x+u that occur in the product on the right-hand side of (4.45). To accomplish this, we have to “generate” these factors on the left-hand side. Here, this is done by reading through Step 2 of the proof of Proposition 4 with y = −v. To make this more precise, observe that x + u divides a typical factor 2x − v + 2i + l + 1, 0 ≤ i ≤ n − 1, 0 ≤ l < i, of the first half of the product in (4.45) if and only if 2u = −v + 2i + l + 1. Therefore, if we recall (4.7), for each solution (i, l) of

2u = −v + 2i + l + 1, with 0 ≤ i ≤ n − 1, 0 ≤ l < i,  (4.46)

we subtract the linear combination

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 2)_{2i−2s}}{(−x − 2i − l + s − 1)_{i−s}}
· (row s of E_{B}(x, −v; n)) (4.47)

of rows of E_{B}(x, −v; n) from row i of E_{B}(x, −v; n). By (4.7), the effect is that (2x − v + 2i + l + 1) = 2(x + u) (the equality being due to (4.46)), is a factor of each entry of the i-th row of the new determinant, for each solution (i, l) of (4.46).

Now it should be observed that (4.46) is exactly equivalent to (4.14) with the replacements v → u and m → u−v, while (4.47) is exactly (4.15) with the replacements m → y−x and y → −v, and the determinant E(x, −v; n) that we are considering here is exactly the determinant E(x, x+m; n) that is considered in Step 1 of Proposition 5, with the same replacements. This observation makes it apparent that similar replacements in the rest of Step 1 of Proposition 5 will produce a valid proof of Lemma 7. In particular, in (4.17), in the statements of Claim 1 and Claim 2, in (4.20), (4.21), Figure 2, (4.25)–(4.40), the replacements v → u and m → u − v yield what we need here. We leave the details to the reader. □

Now we are in the position to prove the promised full evaluation of the determinant E(x, y; n).

Theorem 8. Let x, y, n be nonnegative integers. Then

E(x, y; n) = det_{0≤i,j≤n−1} (\frac{(x + y + i + j − 1)! (y − x + 3j − 3i)}{(x + 2i − j + 1)! (y + 2j − i + 1)!})

= ∏_{i=0}^{n−1} (\frac{i! (x + y + i − 1)! (2x + y + 2i + 1)_{i} (x + 2y + 2i + 1)_{i}}{(x + 2i + 1)! (y + 2i + 1)!} )

· ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(x)_{k} (y)_{n−k}.  (4.48)

Proof. Obviously, the Theorem is equivalent to the assertion that with

P_{6}(x, y; n) = ( ∏_{i=0}^{n−1} i!) · ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(x)_{k} (y)_{n−k}  (4.49)

there holds P_{4}(x, y; n) = P_{6}(x, y; n), where P_{4}(x, y; n) is the polynomial in (4.2). For the proof of this assertion we check the following properties for P_{6}(x, y; n):

(1) P_{6}(x, y; n) is a polynomial in x and y of (total) degree n.

(2) P_{6}(−u, −v; n) = 0 for all nonnegative integers u and v with u + v ≤ n − 1.

(3) P_{6}(y, x; n) = (−1)^{n}P_{6}(x, y; n).

(4) P_{6}(x, x + 1; n) = \frac{n!}{⌊n/2⌋!}( ∏_{i=0}^{n−1} i!) · (x + 1)_{⌊n/2⌋}.

It should be noted that all these properties are also satisfied by P_{4}(x, y; n). This is because of Proposition 4 for (1), because of Lemma 7 for (2), because of

E(x, y; n) = (−1)^{n}E(y, x; n)  (4.50)

(if combined with (4.2)) for (3) (identity (4.50) results from transposing the matrix in (4.1)), and because of (4.43) (if combined with (4.2)) for (4). Since we also show that

(5) The conditions (1)–(4) determine a polynomial in x and y uniquely, the assertion follows.

ad (1). This is obvious from the definition (4.49).

ad (2). We have (−u)_{k} = 0 for k > u. Hence, if k > u the corresponding summand in the sum in (4.49) vanishes for x = −u and y = −v. Now let k ≤ u. Because of u + v ≤ n − 1 it follows that k < n − v, or equivalently, n − k > v. But this implies (−v)_{n−k} = 0. Therefore also any summand with k ≤ u vanishes for x = −u and y = −v. Thus, P_{6}(−u, −v; n) = 0, as desired.

ad (3). This is obvious from the definition (4.49).

ad (4). Setting y = x + 1 in (4.49), we get

\frac{P_{6}(x, x + 1; n)}{∏_{i=0}^{n−1} i!} = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(x)_{k} (x + 1)_{n−k},

or in hypergeometric notation (cf. the Appendix for the definition of the F -notation),

\frac{P_{6}(x, x + 1; n)}{∏_{i=0}^{n−1} i!} = (x + 1)_{n} ·_{2}F_{1}[ \begin{matrix}−n, x \\ −n − x \end{matrix}; −1] .

Next we use the contiguous relation

2F_{1}[ \begin{matrix}a, b \\ c \end{matrix}; z] = _{2}F_{1}[ \begin{matrix}a, b + 1 \\ c \end{matrix}; z] − \frac{az}{c}_{2}F_{1}[ \begin{matrix}a + 1, b + 1 \\ c + 1 \end{matrix} ; z]  (4.51)

to obtain

\frac{P_{6}(x, x + 1; n)}{∏_{i=0}^{n−1} i!} = (x + 1)_{n} (_{2}F_{1}[ \begin{matrix}−n, 1 + x \\ −n − x \end{matrix}; −1] + \frac{n}{n + x}_{2}F_{1}[ \begin{matrix}1 − n, 1 + x \\ 1 − n − x \end{matrix}; −1] ).

To the _{2}F_{1}-series we apply the quadratic transformation (see [11, (3.2)])

2F_{1}[ \begin{matrix}a, b \\ 1 + a − b \end{matrix}; z] = (1 + z)^{−a}_{2}F_{1}[ \begin{matrix}\frac{a}{2}, \frac{1}{2} + \frac{a}{2} \\ 1 + a − b \end{matrix}; \frac{4z}{(1 + z)^{2}} ].  (4.52)

This gives

\frac{P_{6}(x, x + 1; n)}{∏_{i=0}^{n−1} i!} = (x + 1)_{n} lim_{z→−1} ((1 + z)^{n}_{2}F_{1}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2} \\ −n − x \end{matrix} ; \frac{4z}{(1 + z)^{2}} ]

+ \frac{n}{n + x}(1 + z)^{n−1}_{2}F_{1}[ \begin{matrix}\frac{1}{2} − \frac{n}{2}, 1 − \frac{n}{2} \\ 1 − n − x \end{matrix} ; \frac{4z}{(1 + z)^{2}} ] ).

Now, when performing the limit, only one term survives on the right-hand side, either in the first _{2}F_{1}-series or in the second, depending on whether n is odd or even. After simplification, it is seen that both cases result in

\frac{P_{6}(x, x + 1; n)}{∏_{i=0}^{n−1} i!} = \frac{n!}{⌊n/2⌋!}(x + 1)_{⌊n/2⌋},

which is what we want.

ad (5). Let Q(x, y) be a polynomial in x and y satisfying conditions (1)–(4). Because of (1), Q(x, y) can be written in the form

Q(x, y) = _{∑_{i,j≥0} ; i+j≤n}a_{ij} (x)_{i} (y)_{j},  (4.53)

with uniquely determined coefficients a_{ij}. Now, in (4.53) we set x = 0 and y = −v, 0 ≤ v ≤ n − 1. Because of (2), we obtain 0 = ∑_{j=0}^{v} a_{0j} (−v)_{j}. From this system of equations we get a_{0j} = 0 for 0 ≤ j ≤ n − 1. Similarly, by using (2) with x = −1, −2, …, −(n − 1), we get a_{ij} = 0 whenever i + j ≤ n − 1.

Thus, Q(x, y) can be written in the form

Q(x, y) = ∑_{k=0}^{n} b_{k} (x)_{k} (y)_{n−k},  (4.54)

where we set b_{k} := a_{k,n−k}.

Now we apply (3). Since the coefficients b_{k} in the expansion (4.54) are uniquely determined, we get b_{k} = (−1)^{n}b_{n−k}, and so

Q(x, y) = ∑_{k=0}^{⌊n/2⌋} b_{k} (x)_{k} (y)_{n−k} + ∑_{k=0}^{⌈n/2⌉−1} b_{n−k} (x)_{n−k} (y)_{k}

= ∑_{k=0}^{⌊n/2⌋} b_{k} (x)_{k} (y)_{n−k} + (−1)^{n} ∑_{k=0}^{⌈n/2⌉−1} b_{k} (x)_{n−k} (y)_{k}.

Finally we set y = x + 1 in this equation and use condition (4). This leads to

\frac{n!}{⌊n/2⌋!}( ∏_{i=0}^{n−1} i!)(x + 1)_{⌊n/2⌋} = (x + 1)_{⌊n/2⌋} ∑_{k=0}^{⌊n/2⌋} b_{k} (x)_{k} (x + ⌊n/2⌋ + 1)_{n−k−⌊n/2⌋}

+ (−1)^{n}(x + 1)_{⌊n/2⌋} ∑_{k=0}^{⌈n/2⌉−1} b_{k} x · (x + ⌊n/2⌋ + 1)_{n−k−⌊n/2⌋−1} (x + 1)_{k},

and after cancellation,

\frac{n!}{⌊n/2⌋!}( ∏_{i=0}^{n−1} i!) = ∑_{k=0}^{⌊n/2⌋} b_{k} (x)_{k} (x + ⌊n/2⌋ + 1)_{⌈n/2⌉−k}

+ (−1)^{n} ∑_{k=1}^{⌈n/2⌉} b_{k−1} (x)_{k} · (x + ⌊n/2⌋ + 1)_{⌈n/2⌉−k}. (4.55)

We distinguish between n being even or odd. First let n be even. It is straightforward to see that the polynomials

(x)_{k} (x + n/2 + 1)_{n/2−k}, k = 0, 1, …, n/2,

are linearly independent. Hence, by comparison of coefficients, equation (4.55) is equivalent to a system of equations of the form

b_{0} = c_{0}, b_{1} + b_{0} = c_{1}, b_{2} + b_{1} = c_{2}, …, b_{n/2} + b_{n/2−1} = c_{n/2},

where c_{0}, c_{1}, …, c_{n/2} are certain uniquely determined constants. This system of equations has a unique solution, which implies that Q(x, y) is uniquely determined.

The case of odd n is handled similarly. Here, the polynomials

(x)_{k} (x + (n + 1)/2)_{(n+1)/2−k}, k = 0, 1, …, (n + 1)/2,

are linearly independent. Hence, equation (4.55) is equivalent to a system of equations of the form

b_{0} = c′_{0}, b_{1} + b_{0} = c′_{1}, b_{2} + b_{1} = c′_{2}, …,

b_{(n−1)/2} + b_{(n−3)/2} = c′_{(n−1)/2}, b_{(n−1)/2} = c′_{(n+1)/2}

where c′_{0}, c′_{1}, …, c′_{(n+1)/2} are certain uniquely determined constants. Again, this system of equations has a unique solution, which implies that Q(x, y) is uniquely determined also in this case.

This completes the proof of the Theorem. □

Now we can also say explicitly what the polynomial factor P_{5}(x; m, n) of E(x, x + m; n) in Proposition 5 is.

Theorem 9. Let x, m, n be nonnegative integers with m ≤ n. Then

E(x, x + m; n) = det_{0≤i,j≤n−1} (\frac{(2x + m + i + j − 1)! (m + 3j − 3i)}{(x + 2i − j + 1)! (x + m + 2j − i + 1)!})

= \frac{n!}{⌊n/2⌋!} ∏_{i=0}^{n−1} (\frac{i! (2x + m + i − 1)! (3x + m + 2i + 1)_{i} (3x + 2m + 2i + 1)_{i}}{(x + 2i + 1)! (x + m + 2i + 1)!} )

× (x + m)_{⌊n/2⌋−⌊m/2⌋} · ∑_{k≥0} \binom{m}{2k + χ(n is odd)}

× (⌊n/2⌋ − k + 1)_{k} (x + ⌈m/2⌉ + ⌊n/2⌋)_{⌊m/2⌋−k}, (4.56)

again with χ(A)=1 if A is true and χ(A)=0 otherwise.

Proof. We put y = x+m in Theorem 8. Comparison of (4.48) and (4.56) then reveals that we have to show

∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(x)_{k} (x + m)_{n−k}

= \frac{n!}{⌊n/2⌋!} ∑_{k≥0} \binom{m}{2k + χ(n is odd)}(⌊n/2⌋ − k + 1)_{k} (x + ⌈m/2⌉ + ⌊n/2⌋)_{⌊m/2⌋−k}. (4.57)

Actually, this was already done for the special case m = 1 when we checked condition (4) in the proof of Theorem 8. Therefore we have to generalize what we did there.

First we write the left-hand side of (4.57) in hypergeometric notation (cf. the Appendix for the definition of the F -notation),

(x + m)_{n} ·_{2}F_{1}[ \begin{matrix}−n, x \\ 1 − n − x − m \end{matrix}; −1] .

Iteration of the contiguous relation (4.51) then turns this expression into

(x + m)_{n} ∑_{k≥0} \binom{m}{k}\frac{(−n)_{k}}{(1 − n − x − m)_{k}} _{2}F_{1}[ \begin{matrix}−n + k, x + m \\ 1 + k − n − x − m \end{matrix}; −1] .

Now we can again apply the quadratic transformation (4.52) to obtain

∑_{k≥0} \binom{m}{k}\frac{(x + m)_{n} (−n)_{k}}{(1 − n − x − m)_{k}}

× lim_{z→−1} ((1 + z)^{n−k}_{2}F_{1}[ \begin{matrix}−\frac{n}{2} + \frac{k}{2} , −\frac{n}{2} + \frac{k}{2} + \frac{1}{2} \\ 1 + k − n − x − m \end{matrix} ; \frac{4z}{(1 + z)^{2}} ]) ,

and when expanding the _{2}F_{1}-series according to its definition and simplifying a little,

∑_{k≥0} \binom{m}{k} ∑_{ℓ≥0} \frac{(x + m)_{n} (−n)_{k+2ℓ}}{(1 − n − x − m)_{k+ℓ}} \frac{(−1)^{ℓ}}{ℓ!} lim_{z→−1}(1 + z)^{n−k−2ℓ}.

Now, the limit is nonzero only if n and k have the same parity and if ℓ = (n−k)/2, and in that case it is 1. By substituting 2k + χ(n is odd) for k and by little manipulation we arrive finally at the right-hand side of (4.57). Thus, (4.57) is established, and therefore the Theorem. □

In Section 3 we formulated a Conjecture about the “extra” polynomial factor P_{1}(x; m, n) that occurs in the evaluation of the determinant D(x, x + m; n) in Theorem 2. An analogous result seems to hold for the “extra” polynomial factor P_{5}(x; m, n) of E(x, x + m; n) as given in Proposition 5, which was identified as

\frac{n!}{⌊n/2⌋!}( ∏_{i=0}^{n−1} i!) · ∑_{k≥0} \binom{m}{2k + χ(n is odd)}(⌊n/2⌋ − k + 1)_{k} (x + ⌈m/2⌉ + ⌊n/2⌋)_{⌊m/2⌋−k}

by Theorem 9.

Conjecture. Let x, m, n be nonnegative integers with m ≤ n. Then the polynomial

∑_{k≥0} \binom{m}{2k + χ(n is odd)}(⌊n/2⌋ − k + 1)_{k} (x + ⌈m/2⌉ + ⌊n/2⌋)_{⌊m/2⌋−k}, (4.58)

a polynomial in x of exact degree ⌊m/2⌋, satisfies: If the cases n even and n odd are considered separately, its coefficient of x^{e} is a polynomial in n of degree ⌊m/2⌋ − e with positive integer coefficients.

5. A related determinant identity. In this section we derive a determinant identity that is somewhat related to the determinant identities of the previous sections (see the paragraph after the proof of Theorem 10 for an account of this relationship). Special cases of this identity appeared previously in the paper [2] of Andrews and Burge, also in connection with the enumeration of totally symmetric self-complementary plane partitions.

In [2, sec. 4], Andrews and Burge show that the determinants in (2.2) for x = 0 (which give the enumeration of totally symmetric self-complementary plane partitions) can be transformed by elementary row and column operations into the determinant

det_{0≤i,j≤n−1} (\binom{i + j + 1}{2j − i} + \binom{i + j}{2j − i − 1}) ,  (5.1)

and in Theorem 2 of their paper (see also [3, Theorem 3]) provide an evaluation even for

det_{0≤i,j≤n−1} (\binom{x + i + j + 1}{2j − i + 1} + \binom{x + i + j}{2j − i}) .  (5.2)

(We changed the notation of [2] slightly. In particular, we replaced x by x − 2.) Then they observe that the determinant (5.1) reduces to the determinant (5.2) with x = 2 and with n replaced by n − 1, and thus provide another proof of the totally symmetric self-complementary plane partitions conjecture. However, there is even a two-parameter generalization of (5.2), (namely the determinant in (5.4) below), that can be evaluated. This two-parameter generalization is the subject of our next theorem. We formulate it only for integral x and y. But in fact, with a generalized definition of factorials and binomials (cf. [7, sec. 5.5, (5.96), (5.100)]; see also the remarks after (4.1)), Theorem 10, together with its proof, would also hold for complex x and y.

Theorem 10. Let x, y, n be nonnegative integers. Then there holds

det_{0≤i,j≤n−1} (\frac{(x + y + i + j − 1)!}{(x + 2i − j)! (y + 2j − i)!})

= ∏_{i=0}^{n−1} \frac{i! (x + y + i − 1)! (2x + y + 2i)_{i} (x + 2y + 2i)_{i}}{(x + 2i)! (y + 2i)!} , (5.3)

or equivalently,

det_{0≤i,j≤n−1} (\binom{x + y + i + j}{y + 2j − i} + \binom{x + y + i + j − 1}{y + 2j − i − 1})

= ∏_{i=0}^{n−1} \frac{i! (x + y + i − 1)! (2x + y + 2i)_{i} (x + 2y + 2i)_{i+1}}{(x + 2i)! (y + 2i)!} . (5.4)

Proof. The equivalence of (5.3) and (5.4) is obvious from the simple fact

\binom{x + y + i + j}{y + 2j − i} + \binom{x + y + i + j − 1}{y + 2j − i − 1} = \frac{(x + y + i + j − 1)! (x + 2y + 3j)}{(x + 2i − j)! (y + 2j − i)!}.

We are going to prove (5.3). Our procedure is very similar to the preceding proofs of Theorems 2 and 4, only that things are much simpler here. Actually, in the research process it was the other way round. This proof was found first and provided (some of) the inspiration for the later proofs of Theorems 2 and 4.

Step 1. An equivalent statement of the Theorem. We take as many common factors out of the i-th row of the determinant in (5.3), i = 0, 1, …, n − 1, as possible, such that the entries become polynomials in x and y. Thus we obtain

∏_{i=0}^{n−1} \frac{(x + y + i − 1)!}{(x + 2i)! (y + 2n − i − 2)!}

× det_{0≤i,j≤n−1} ((x + y + i)_{j} (x + 2i − j + 1)_{j} (y + 2j − i + 1)_{2n−2j−2}).

Comparing with (5.3), we see that (5.3) is equivalent to

det_{0≤i,j≤n−1} ((x + y + i)_{j} (x + 2i − j + 1)_{j} (y + 2j − i + 1)_{2n−2j−2})

= ∏_{i=0}^{n−1} (i! (y + 2i + 1)_{n−i−1} (2x + y + 2i)_{i} (x + 2y + 2i)_{i}). (5.5)

Let us denote the determinant in (5.5) by P_{8}(x, y; n).

We are going to establish (5.5), and thus (5.3), by showing in Steps 2 and 3 that the right-hand side of (5.5) divides P_{8}(x, y; n) as a polynomial in x and y, by showing in Step 4 that the (total) degree in x and y of P_{8}(x, y; n) is 3\binom{n}{2}, so that P_{8}(x, y; n) is a constant multiple of the right-hand side of (5.5), and by showing that this constant equals 1, also in Step 4.

Step 2. ∏_{i=0}^{n−1}(y + 2i + 1)_{n−i−1} is a factor of P_{8}(x, y; n). We multiply the i-th row of P_{8}(x, y; n), which is the determinant in (5.5), by (y +2n−i−1)_{i}, i = 0, 1, …, n−1, and divide the j-th column by (y + 2j + 1)_{2n−2j−2}, j = 0, 1, …, n − 1. This leads to

P_{8}(x, y; n) = ∏_{i=0}^{n−1} \frac{1}{(y + 2n − i − 1)_{i}} ∏_{j=0}^{n−1}(y + 2j + 1)_{2n−2j−2}

× det_{0≤i,j≤n−1} ((x + y + i)_{j} (x + 2i − j + 1)_{j} (y + 2j − i + 1)_{i})

= ∏_{i=0}^{n−1}(y + 2i + 1)_{n−i−1} · det_{0≤i,j≤n−1} ((x + y + i)_{j} (x + 2i − j + 1)_{j} (y + 2j − i + 1)_{i}).

Since the determinant in the last line is a polynomial in x and y, we infer that ∏_{i=0}^{n−1}(y + 2i + 1)_{n−i−1} divides P_{8}(x, y; n).

Step 3. ∏_{i=0}^{n−1} ((2x + y + 2i)_{i} (x + 2y + 2i)_{i}) is a factor of P_{8}(x, y; n). We proceed in the spirit of Step 3 of the proof of Theorem 2. So it is not necessary to provide all the details. The basic ideas will suffice.

First, let us concentrate on a typical factor (2x+y+2i+l), 0 ≤ i ≤ n−1, 0 ≤ l < i, of the first half of the product, ∏_{i=0}^{n−1}(2x+y +2i)_{i}. We claim that for each such factor there is a linear combination of the rows that vanishes if the factor vanishes. More precisely, we claim that for any i, l with 0 ≤ i ≤ n − 1, 0 ≤ l < i there holds

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 1)_{2i−2s}}{(−x − 2i − l + s)_{i−s}} (−2x−2i−l+2n−s−1)_{s}

· (row s of P_{8}(x, −2x − 2i − l; n)) = (row i of P_{8}(x, −2x − 2i − l; n)).

Restricting to the j-th column, it is seen that this means to check

∑_{s=l}^{⌊(i+l)/2⌋} \frac{(2i − 3s + l)}{(i − s)} \frac{(i − 2s + l + 1)_{s−l}}{(s − l)!} \frac{(x + 2s + 1)_{2i−2s}}{(−x − 2i − l + s)_{i−s}} (−2x−2i−l+2n−s−1)_{s−i}

× (−x − 2i − l + s)_{j} (x + 2s − j + 1)_{j} (−2x − 2i − l + 2j − s + 1)_{2n−2j−2}

= (−x − i − l)_{j} (x + 2i − j + 1)_{j} (−2x − 3i − l + 2j + 1)_{2n−2j−2}.

This is easily done by observing that it is equivalent to (3.15) with x replaced by x − j. Arguments that are similar to those after (3.18) then show that the complete product ∏_{i=0}^{n−1}(2x + y + 2i)_{i} divides P_{8}(x, y; n).

The reasoning that ∏_{i=0}^{n−1}(x+2y+2i)_{i} is a factor of P_{8}(x, y; n) is similar. Also here, let us concentrate on a typical factor (x + 2y + 2j + l), 0 ≤ j ≤ n − 1, 0 ≤ l < j. This time we claim that for each such factor there is a linear combination of the columns that vanishes if the factor vanishes. More precisely, we claim that for any j, l with 0 ≤ j ≤ n − 1, 0 ≤ l < j there holds

∑_{s=l}^{⌊(j+l)/2⌋} \frac{(2j − 3s + l)}{(j − s)} \frac{(j − 2s + l + 1)_{s−l}}{(s − l)!} · (column s of P_{8}(−2y − 2j − l, y; n))

= (column j of P_{8}(−2y − 2j − l, y; n)).

Restricting to the i-th row, we see that this means to check

∑_{s=l}^{⌊(j+l)/2⌋} \frac{(2j − 3s + l)}{(j − s)} \frac{(j − 2s + l + 1)_{s−l}}{(s − l)!}
× (−y − 2j − l + i)_{s} (−2y − 2j − l + 2i − s + 1)_{s} (y + 2s − i + 1)_{2n−2s−2}

= (−y − 2j − l + i)_{j} (−2y − 3j − l + 2i + 1)_{j} (y + 2j − i + 1)_{2n−2j−2}. (5.6)

The observation that this summation is equivalent to (3.23) with y replaced by x + 2 and ȳ replaced by y − i establishes the claim. Similarly to as before, this eventually shows that the complete product ∏_{i=0}^{n−1}(x + 2y + 2i)_{i} divides P_{8}(x, y; n).

Altogether, this implies that ∏_{i=0}^{n−1} ((2x + y + 2i)_{i}(x + 2y + 2i)_{i}) divides P_{8}(x, y; n), as desired.

Step 4. P_{8}(x, y; n) is a polynomial in x and y of degree 3\binom{n}{2}, and the evaluation of the multiplicative constant. We consider the generalized determinant

\overline{P}_{8}(x, y, z(0), z(1), …, z(n − 1); n) = \overline{P}_{8}(x, y; n)

which arises from P_{8}(x, y; n) by replacing each occurence of i in row i by an indeterminate, z(i) say, i = 0, 1, …, n − 1,

\overline{P}_{8}(x, y, z(0), z(1), …, z(n − 1); n) = \overline{P}_{8}(n)

= det_{0≤i,j≤n−1} ((x + y + z(i))_{j} (x + 2z(i) − j + 1)_{j} (y + 2j − z(i) + 1)_{2n−2j−2}).

This determinant is a polynomial in x, y, z(0), z(1), …, z(n − 1) of (total) degree at most 4\binom{n}{2}.

When z(i_{1}) = z(i_{2}) for some i_{1} ≠ i_{2}, the rows i_{1} and i_{2} in \overline{P}_{8}(n) are identical. Hence \overline{P}_{8}(n) vanishes in this case. This shows that the product ∏_{0≤i<j≤n−1}(z(j) − z(i)) divides \overline{P}_{8}(n). Moreover, the argument in the second half of Step 3 shows that also ∏_{i=0}^{n−1}(x + 2y + 2i)_{i} divides \overline{P}_{8}(n), just replace i by z(i) in (5.6). Thus we obtain that

\overline{P}_{8}(n) = ∏_{0≤i<j≤n−1}(z(j) − z(i)) ∏_{i=0}^{n−1}(x + 2y + 2i)_{i} · Q(x, y, z(0), z(1), …, z(n − 1); n),

(5.7)

where Q(x, y, z(0), z(1), …, z(n−1); n) is a polynomial in x, y, z(0), z(1), …, z(n−1) of total degree at most 4\binom{n}{2} − 2\binom{n}{2} = 2\binom{n}{2}. By comparing coefficients of

y^{3\binom{n}{2}}z(0)^{0}z(1)^{1} ⋯ z(n − 1)^{n−1}

on both sides of (5.7), it is seen that the coefficient of y^{2\binom{n}{2}} in Q(x, y, z(0), z(1), …, z(n − 1); n) equals 1.

Now we set z(i) = i, i = 0, 1, …, n − 1, in (5.7). Then \overline{P}_{8}(n) on the left-hand side reduces to P_{8}(x, y; n). By Steps 2 and 3 we know that

∏_{i=0}^{n−1} ((y + 2i + 1)_{n−i−1} (2x + y + 2i)_{i})  (5.8)

divides P_{8}(x, y; n). Therefore, by (5.7), it also divides Q(x, y, 0, 1, …, n − 1; n). Since the degree in x and y of this factor is 2\binom{n}{2}, which at the same time is an upper bound for the degree in x and y of Q(x, y, 0, 1, …, n − 1; n), as we saw before, Q(x, y, 0, 1, …, n − 1; n) is a constant multiple of (5.8). Moreover, the coefficient of y^{2\binom{n}{2}} in (5.8) equals 1, which we already know to be the coefficient of y^{2\binom{n}{2}} in Q(x, y, 0, 1, …, n − 1; n). Hence, Q(x, y, 0, 1, …, n − 1; n) agrees with (5.8), which by (5.7) completes the proof of (5.5), and hence of the Theorem. □

It should be noted that the two-parameter determinant in (5.4) carries a strong relationship to the determinants D(x, y; n) in (3.1) and E(x, y; n) in (4.1). Namely, the (i, j)-entry of the determinant in (5.4), with x replaced by x + 1, equals the (i, j)- entry of D(x, y; n) minus 2 times the (i, j − 1)-entry of D(x, y; n), while (2x + y + 3i + 1)(x + 2y + 3j + 1) times the (i, j)-entry of E(x, y; n) equals the (i, j)-entry of the determinant in (5.4) with x replaced by x + 1 minus 2 times the (i − 1, j)-entry of the same determinant. So the determinant in (5.4) is somehow “in between” the determinants D(x, y; n) and E(x, y; n).

6. Constant term identities. In this section we translate some of our determinant identities into constant term identities.

Of course, we start by stating the Conjecture of the Introduction, now as a theorem.

Theorem 11. Let x and n be nonnegative integers. Then there holds

CT (\frac{∏_{0≤i<j≤n−1}(1 − z_{i}/z_{j}) ∏_{i=0}^{n−1}(1 + z_{i}^{−1})^{x+n−i−1}}{∏_{0≤i<j≤n−1}(1 − z_{i}z_{j}) ∏_{i=0}^{n−1}(1 − z_{i})} )

= \{ \begin{matrix}∏_{i=0}^{n−1} \frac{(3x+3i+1)!}{(3x+2i+1)! (x+2i)!} ∏_{i=0}^{(n−2)/2}(2x + 2i + 1)! (2i)! & if n is even \\ 2^{x} ∏_{i=1}^{n−1} \frac{(3x+3i+1)!}{(3x+2i+1)! (x+2i)!} ∏_{i=1}^{(n−1)/2}(2x + 2i)! (2i − 1)! & if n is odd. \end{matrix} (6.1)

Also, both the sum of all n × n minors of the n × (2n − 1) matrix (\binom{x+i}{j−i})_{0≤i≤n−1, 0≤j≤2n+x−2}, and the number of shifted plane partitions of shape

(x + n − 1, x + n − 2, …, 1), with entries between 0 and n, where the entries in row i are at least n − i, i = 1, 2, …, n − 1, equal the right-hand side in (6.1).

Proof. For even n, equation (6.1) follows from a combination of Theorem 1, item (3), (2.2a), and (3.69). For odd n, equation (6.1) follows from a combination of Theorem 1, item (3), (2.2b), and (4.42) or (4.56) with m = 0. The other claims are due to Theorem 1, items (1) and (2), respectively. □

Next we translate the determinant identities of Section 4 into constant term identities.

Theorem 12. Let x, y, m, n be nonnegative integers with m ≤ n. Then there holds

CT ( ∏_{i=0}^{n−1} ((1 + z_{i})^{x+y+i−1}(1 + 2z_{i})(z_{i} + 2)(z_{i} − 1)z_{i}^{−y−2n+i+1})

× ∏_{0≤i<j≤n−1} ((z_{i} − z_{j})(z_{i} + z_{j} + z_{i}z_{j})))

= ∏_{i=0}^{n−1} (\frac{i! (x + y + i − 1)! (2x + y + 2i + 1)_{i+1} (x + 2y + 2i + 1)_{i+1}}{(x + 2i + 1)! (y + 2i + 1)!} )

· ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}(x)_{k} (y)_{n−k}. (6.2)

If y = x + m, with m a fixed nonnegative integer, then the constant term in (6.2) equals

\frac{n!}{⌊n/2⌋!} ∏_{i=0}^{n−1} (\frac{i! (2x + m + i − 1)! (3x + m + 2i + 1)_{i+1} (3x + 2m + 2i + 1)_{i+1}}{(x + 2i + 1)! (x + m + 2i + 1)!} )

× (x + m)_{⌊n/2⌋−⌊m/2⌋} · ∑_{k≥0} \binom{m}{2k + χ(n is odd)}

× (⌊n/2⌋ − k + 1)_{k} (x + ⌈m/2⌉ + ⌊n/2⌋)_{⌊m/2⌋−k}. (6.3)

Proof. It is routine to verify that

\frac{(x + y + i + j − 1)! (2x + y + 3i + 1) (x + 2y + 3j + 1) (y − x + 3j − 3i)}{(x + 2i − j)! (y + 2j − i)!}

= CT ((1 + z)^{x+y+i+j−1}(1 + 2z)(z + 2)(z − 1)z^{−y−2j+i−1}).

Consequently, taking determinants we obtain

det_{0≤i,j≤n−1}(\frac{(x + y + i + j − 1)! (2x + y + 3i + 1) (x + 2y + 3j + 1) (y − x + 3j − 3i)}{(x + 2i − j)! (y + 2j − i)!})

(6.4)

= det_{0≤i,j≤n−1} (CT ((1 + z_{i})^{x+y+i+j−1}(1 + 2z_{i})(z_{i} + 2)(z_{i} − 1)z_{i}^{−y−2j+i−1}))

= CT ( ∏_{i=0}^{n−1} ((1 + z_{i})^{x+y+i−1}(1 + 2z_{i})(z_{i} + 2)(z_{i} − 1)z_{i}^{−y+i−1})

× det_{0≤i,j≤n−1} ((\frac{1 + z_{i}}{z_{i}^{2}} )^{j}))

= CT ( ∏_{i=0}^{n−1} ((1 + z_{i})^{x+y+i−1}(1 + 2z_{i})(z_{i} + 2)(z_{i} − 1)z_{i}^{−y−2n+i+1})

× ∏_{0≤i,j≤n−1} ((z_{i} − z_{j})(z_{i} + z_{j} + z_{i}z_{j}))),

where we used the Vandermonde determinant identity in the last step. Obviously, the last line agrees exactly with the left-hand side of (6.2). Thus, by taking factors that depend only on i, respectively only on j, out of the determinant in (6.4) and applying Theorems 8 and 9 to the resulting determinant, all the assertions of the Theorem follow immediately. □

Finally, we translate the determinant identity of Section 5 into a constant term identity.

Theorem 13. Let x, y, n be nonnegative integers. Then there holds

CT ( ∏_{i=0}^{n−1} ((1+z_{i})^{x+y+i−1}(1+2z_{i})z_{i}^{−y−2n+i+2}) ∏_{0≤i,j≤n−1} ((z_{i} −z_{j})(z_{i} +z_{j} +z_{i}z_{j})))

= ∏_{i=0}^{n−1} \frac{i! (x + y + i − 1)! (2x + y + 2i)_{i} (x + 2y + 2i)_{i+1}}{(x + 2i)! (y + 2i)!} . (6.5)

Proof. We observe

\binom{x + y + i + j}{y + 2j − i} + \binom{x + y + i + j − 1}{y + 2j − i − 1} = CT ((1 + z)^{x+y+i+j−1}(1 + 2z)z^{−y−2j+i}),

and then proceed in the same way as in the proof of Theorem 12. The reader will have no difficulties to fill in the details. □

Appendix

Here we provide auxiliary results that are needed in the proofs of our Theorems. We start by recalling the theorems about nonintersecting lattice paths that we

need in the proof of Theorem 1. The main theorem of nonintersecting lattice paths [6, Cor. 2; 15, Theorem 1.2] is the following.

Proposition A1. Let A_{0}, A_{1}, …, A_{n−1} and E_{0}, E_{1}, …, E_{n−1} be lattice points with the “compatibility” property that, given i < j and k < l, any lattice path from A_{i} to E_{l} meets any lattice path from A_{j} to E_{k}. Then the number of all families (P_{0}, P_{1}, …, P_{n−1}) of nonintersecting lattice paths, where P_{i} runs from A_{i} to E_{i}, i = 0, 1, …, n − 1, is given by the determinant

det_{0≤i,j≤n−1} (|P(A_{i} → E_{j})|),

where |P(A → E)| denotes the number of all lattice paths from A to E.

The second result about nonintersecting lattice paths is Stembridge’s enumeration [15, Theorem 3.1] of nonintersecting lattice paths when the end points of the lattice paths are allowed to vary.

Proposition A2. Let A_{0}, A_{1}, …, A_{n−1} be lattice points, and let I = {…, E_{k}, E_{k+1}, … } be a totally ordered set of lattice points, again with the “compatibility” property that, given i < j and k < l, any lattice path from A_{i} to E_{l} meets any lattice path from A_{j} to E_{k}. Then the number of all families (P_{0}, P_{1}, …, P_{n−1}) of nonintersecting lattice paths, where P_{i} runs from A_{i} to some point of I, i = 0, 1, …, n − 1, is given by the Pfaffian

Pf_{0≤i<j≤n−1} (Q(i, j)),

where Q(i, j) is the number of all pairs (P_{i}, P_{j}) of nonintersecting lattice paths, P_{i} running from A_{i} to some point of I, and P_{j} running from A_{j} to some point of I.

Next we prove some identities for hypergeometric series. We use the usual hypergeometric notation

rF_{s}[ \begin{matrix}a_{1}, …, a_{r} \\ b_{1}, …, b_{s} \end{matrix}; z] = ∑_{k=0}^{∞} \frac{(a_{1})_{k} ⋯ (a_{r})_{k}}{k! (b_{1})_{k} ⋯ (b_{s})_{k}} z^{k} ,

where the shifted factorial (a)_{k} is given by (a)_{k} := a(a + 1) ⋯ (a + k − 1), k ≥ 1, (a)_{0} := 1, as before.

To begin with, in Lemma A3 we quote a result of Andrews and Burge [2, Lemma 1]. This _{4}F_{3}-summation was derived in [2] from a similar _{4}F_{3}-summation due to Bailey. We provide an alternative proof here, showing that, in fact, Andrews and Burge’s summation follows easily from a transformation formula due to Singh. (The above mentioned _{4}F_{3}-summation of Bailey’s, as well as Lemma 2 of [2] do also follow from Singh’s transformation formula.)

Lemma A3. Let n be a positive integer. Then

4F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ 1 − n, \frac{B}{2} , \frac{1}{2} + \frac{B}{2} \end{matrix} ; 1] = \frac{(A + B)_{n}}{(B)_{n}} + \frac{(−A)_{n}}{(B)_{n}} .  (A.1)

Proof. In [12, main theorem], Singh proves the following transformation formula (actually a q-analogue thereof, see also [5, (3.10.13); Appendix (III.21)]):

4F_{3}[ \begin{matrix}a, b, c, d \\ \frac{1}{2} + a + b, \frac{c+d}{2}, \frac{1+c+d}{2} \end{matrix} ; 1] = _{3}F_{2}[ \begin{matrix}2a, 2b, c \\ \frac{1}{2} + a + b, c + d \end{matrix}; 1] ,

provided both series terminate.

Now, let first n be odd. In Singh’s transformation we choose a = −n/2 + ε, b = 1/2 − n/2, c = −A, and d = A + B. Thus, we obtain

4F_{3}[ \begin{matrix}−\frac{n}{2} + ε, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ 1 + ε − n, \frac{B}{2} , \frac{1}{2} + \frac{B}{2} \end{matrix} ; 1] = _{3}F_{2}[ \begin{matrix}2ε − n, 1 − n, −A \\ 1 + ε − n, B \end{matrix}; 1] .

Note that because n is odd both series do indeed terminate. We may express the sum on the right-hand side explicitly,

4F_{3}[ \begin{matrix}−\frac{n}{2} + ε, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ 1 + ε − n, \frac{B}{2} , \frac{1}{2} + \frac{B}{2} \end{matrix} ; 1] = ∑_{k=0}^{n−1} \frac{(−A)_{k} (1 − n)_{k} (2ε − n)_{k}}{(1)_{k} (B)_{k} (1 + ε − n)_{k}}

and then let ε tend to zero. This gives

4F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ 1 − n, \frac{B}{2} , \frac{1}{2} + \frac{B}{2} \end{matrix} ; 1] = ∑_{k=0}^{n−1} \frac{(−A)_{k} (−n)_{k}}{(1)_{k} (B)_{k}}

= ∑_{k=0}^{n} \frac{(−A)_{k} (−n)_{k}}{(1)_{k} (B)_{k}} − \frac{(−A)_{n} (−n)_{n}}{(1)_{n} (B)_{n}}

= _{2}F_{1}[ \begin{matrix}−A, −n \\ B \end{matrix}; 1] − \frac{(−A)_{n} (−n)_{n}}{(1)_{n} (B)_{n}} .

The _{2}F_{1}-series can be evaluated by the hypergeometric form of Vandermonde summation (see [13, (1.7.7); Appendix (III.4)]),

2F_{1}[ \begin{matrix}a, −n \\ c \end{matrix}; 1] = \frac{(c − a)_{n}}{(c)_{n}} ,

where n is a nonnegative integer. Applying this, we get

4F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ 1 − n, \frac{B}{2} , \frac{1}{2} + \frac{B}{2} \end{matrix} ; 1] = \frac{(A + B)_{n}}{(B)_{n}} − \frac{(−A)_{n} (−n)_{n}}{n! (B)_{n}} ,

which reduces to (A.1) since n is odd and thus (−n)_{n} = −n!.

The case that n is even is treated similarly. One would start by choosing a = −n/2, b = 1/2 − n/2 + ε, c = −A, and d = A + B in Singh’s transformation formula. We leave the details to the reader. □

From the _{4}F_{3}-summation in Lemma A3 we derive a summation for a _{5}F_{4}-series.

Lemma A4. Let n be a positive integer. Then

5F_{4}[ \begin{matrix}1 − \frac{2n}{3}, −\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ −\frac{2n}{3}, 1 − n, \frac{1}{2} + \frac{B}{2} , 1 + \frac{B}{2} \end{matrix} ; 1]

= \frac{1}{2} \frac{(A − B − 2n)}{(2A + B)} \frac{(−A)_{n}}{(1 + B)_{n}} + \frac{1}{2} \frac{(A + 2B + 2n)}{(2A + B)} \frac{(A + B)_{n}}{(1 + B)_{n}} . (A.2)

Proof. We transform the _{5}F_{4}-series by the contiguous relation

5F_{4}[ \begin{matrix}1 − \frac{2n}{3}, −\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ −\frac{2n}{3}, 1 − n, \frac{1}{2} + \frac{B}{2} , 1 + \frac{B}{2} \end{matrix} ; 1]

= \frac{3A (B + n)}{4n (2A + B)}_{4}F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, 1 − A, A + B \\ 1 − n, \frac{1}{2} + \frac{B}{2} , 1 + \frac{B}{2} \end{matrix} ; 1]

− \frac{3B (2A + B + \frac{n}{3})}{4n (2A + B)}_{4}F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −A, A + B \\ 1 − n, \frac{B}{2} , \frac{1}{2} + \frac{B}{2} \end{matrix} ; 1]

+ \frac{3 (B + \frac{5n}{3}) (A + B)}{4n (2A + B)}_{4}F_{3}[ \begin{matrix}−\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −A, 1 + A + B \\ 1 − n, \frac{1}{2} + \frac{B}{2} , 1 + \frac{B}{2} \end{matrix} ; 1] .

Now each of the _{4}F_{3}-series can be summed by means of Lemma 1. Some manipulation then leads to (A.2). □

The special case that is of particular importance in Step 3 of the proofs of Theorems 2 and 10, and in Step 2 of the proof of Proposition 4, is A = 2n + B.

Corollary A5. Let n be a positive integer. Then

5F_{4}[ \begin{matrix}1 − \frac{2n}{3}, −\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −2n − B, 2n + 2B \\ −\frac{2n}{3}, 1 − n, \frac{1}{2} + \frac{B}{2} , 1 + \frac{B}{2} \end{matrix} ; 1] = \frac{1}{2} \frac{(2n + 2B)_{n}}{(1 + B)_{n}} . (A.3) □

Finally we move one step further to a _{6}F_{5}-summation.

Lemma A6. Let n be a positive integer. Then

6F_{5}[ \begin{matrix}\frac{4}{3} + \frac{2n}{3} + B, 1 − \frac{2n}{3}, −\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −1 − 2n − B, 2n + 2B \\ \frac{1}{3} + \frac{2n}{3} + B, −\frac{2n}{3}, 1 − n, 1 + \frac{B}{2} , \frac{3}{2} + \frac{B}{2} \end{matrix} ; 1]

= \frac{1}{2} \frac{(1 + 5n + 3B)}{(1 + 2n + 3B)} \frac{(2n + 2B)_{n}}{(2 + B)_{n}} (A.4)

Proof. We use the contiguous relation

6F_{5}[ \begin{matrix}\frac{4}{3} + \frac{2n}{3} + B, 1 − \frac{2n}{3}, −\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −1 − 2n − B, 2n + 2B \\ \frac{1}{3} + \frac{2n}{3} + B, −\frac{2n}{3}, 1 − n, 1 + \frac{B}{2} , \frac{3}{2} + \frac{B}{2} \end{matrix} ; 1]

= \frac{4 (n + B) (1 + 2n + 2B)}{(1 + 4n + 3B) (1 + 2n + 3B)}

×_{5}F_{4}[ \begin{matrix}1 − \frac{2n}{3}, −\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −1 − 2n − B, 2 + 2n + 2B \\ −\frac{2n}{3}, 1 − n, 1 + \frac{B}{2} , \frac{3}{2} + \frac{B}{2} \end{matrix} ; 1]

+ \begin{matrix}(1 + B) & (1 + 2n + B) \\ (1 + 4n + 3B) & (1 + 2n + 3B) \end{matrix}_{5}F_{4}[ \begin{matrix}1 − \frac{2n}{3}, −\frac{n}{2}, \frac{1}{2} − \frac{n}{2}, −2n − B, 2n + 2B \\ −\frac{2n}{3}, 1 − n, \frac{1}{2} + \frac{B}{2} , 1 + \frac{B}{2} \end{matrix} ; 1] .

Each of the _{5}F_{4}-series can be summed by means of Corollary A5. After little manipulation we arrive at (A.4). □

The next Lemmas provide the means for finding degree bounds in Step 5 of the proof of Theorem 2 and Step 2 of the proof of Proposition 5.

As usual, given nonnegative integers n and k, we write

e_{k}(x_{1}, …, x_{n}) := ∑_{1≤i_{1}<···<i_{k}≤n} x_{i_{1}} ⋯ x_{i_{k}}

for the elementary symmetric function of order k in x_{1}, …, x_{n}. In particular, this definition implies e_{k}(x_{1}, x_{2}, …, x_{n}) ≡ 0 if n < k, since then the defining sum is empty. The following Lemma (together with its proof) holds with this understanding of the definition of elementary symmetric functions.

Lemma A7. Let a and n be fixed integers, n ≥ 0. Then, as k varies through the nonnegative integers, e_{k}(a, a + 1, …, a + n − 1) is a polynomial in n of degree 2k.

Proof. By induction on k. The assertion is trivially true for k = 0. If we assume that the assertion is true for k, we have

e_{k+1}(a, a + 1, …, a + n − 1) = ∑_{a≤i_{1}<···<i_{k+1}≤a+n−1} i_{1}i_{2} ⋯ i_{k+1}

= ∑_{0≤i_{k+1}≤n−1}(a + i_{k+1})e_{k}(a, a + 1, …, a + i_{k+1} − 1). (A.5)

By induction hypothesis, e_{k}(a, a + 1, …, a + i_{k+1} − 1) is some polynomial p(i_{k+1}) in i_{k+1} of degree 2k. Therefore e_{k+1}(a, a + 1, …, a + n − 1), which by (A.5) is the indefinite sum of a polynomial of degree 2k + 1, is a polynomial of degree 2k + 2 (cf. e.g. [8, sec. 32, Example on p. 103]). □

Lemma A8. Let a and p be fixed integers, p ≥ 0. Then, as j varies through the nonnegative integers, the coefficient of x^{j−p} in (x + a)_{j} is a polynomial in j of degree 2p.

Proof. By definition of shifted factorials we have

(x + a)_{j} = ∏_{i=0}^{j−1}(x + a + i)

= ∑_{p≥0} x^{j−p} e_{p}(a, a + 1, …, a + j − 1).

(Note that we need not give an upper bound for the sum, since e_{p}(a, a + 1, …, a + j − 1) ≡ 0 for p > j, see the paragraph before Lemma A7 that contains the definition of elementary symmetric functions). Therefore, by Lemma A7, the coefficient of x^{j−p} in (x + a)_{j} is a polynomial in j of degree 2p. □

Lemma A9. Let n, m, and p be fixed integers 0 ≤ p ≤ 2n + ⌊m/2⌋ − 3. Then, as j varies through the integers, 1 ≤ j ≤ n − 1, the coefficient of x^{p} in

(2x + m + 1)_{j} (x − j + 2)_{⌊m/2⌋+j−1} (x + m + 2j + 1)_{2n−2j−2}

is 2^{j} times a polynomial in j of degree ≤ 2(2n + ⌊m/2⌋ − 3 − p).

Proof. We have

(2x + m + 1)_{j} = ∑_{r≥0} x^{j−r}2^{j−r}b_{r}(j),

where, by Lemma A8, b_{r}(j) is a polynomial in j of degree 2r. Similarly, we have

(x − j + 2)_{⌊m/2⌋+j−1} = (−1)^{⌊m/2⌋+j−1}(−x − ⌊m/2⌋)_{⌊m/2⌋+j−1}

= (−1)^{⌊m/2⌋+j−1} ∑_{s≥0} x^{⌊m/2⌋+j−1−s}(−1)^{⌊m/2⌋+j−1−s}c_{s}(j)

= ∑_{s≥0} x^{⌊m/2⌋+j−1−s}(−1)^{s}c_{s}(j),

where, by Lemma A8, c_{s}(j) is a polynomial in (⌊m/2⌋ + j − 1) of degree 2s, and as such is a polynomial in j of degree 2s. Finally, we have

(x + m + 2j + 1)_{2n−2j−2} = (−x − m − 2n + 2)_{2n−2j−2}

= ∑_{t≥0} x^{2n−2j−2−t}(−1)^{t}d_{t}(j),

where, by Lemma A8, d_{t}(j) is a polynomial in 2n − 2j − 2 of degree 2t, and as such is a polynomial in j of degree 2t.

Putting things together we get

(2x + m + 1)_{j} (x − j + 2)_{⌊m/2⌋+j−1} (x + m + 2j + 1)_{2n−2j−2}

= ∑_{k≥0} x^{2n+⌊m/2⌋−3−k} 2^{j}_{∑_{r,s,t≥0} ; r+s+t=k}(−1)^{s+t}2^{−r}b_{r}(j) c_{s}(j) d_{t}(j).

Now, the (finite) range of the inner sum does not depend on j. Hence, by what we know about b_{r}(j), c_{s}(j), and d_{t}(j), the inner sum is a polynomial in j of degree at most 2r + 2s + 2t = 2k. By replacing k by 2n + ⌊m/2⌋ − 3 − p we get the assertion of the Lemma. □

Lemma A10. Let n, m, p, and q be fixed integers 0 ≤ p ≤ 2n − 4, 0 ≤ q ≤ 2n − 3, p + q ≤ 2n − 3. Then, as j varies through the integers, 1 ≤ j ≤ n − 1, the coefficient of x^{p}z^{q} in

(2x+m+z +1)_{j−1} (x+2z −j +2)_{j−1} (x+m+2j −z +2)_{2n−2j−2} (m+3j −3z) (A.6)

is 2^{j} times a polynomial in j of degree ≤ 2(2n − 3 − p − q) + q − 1.

Proof. We have

(2x + m + z + 1)_{j−1} = ∑_{r≥0}(2x + z)^{j−1−r}b_{r}(j)

= ∑_{r≥0} ∑_{h≥0} \binom{j − 1 − r}{h}2^{j−1−r−h}x^{j−1−r−h}z^{h}b_{r}(j),

where, by Lemma A8, b_{r}(j) is a polynomial in j − 1 of degree 2r, and as such a polynomial in j of degree 2r. Similarly, we have

(x + 2z − j + 2)_{j−1} = ∑_{s≥0}(x + 2z)^{j−1−s}c_{s}(j)

= ∑_{s≥0} ∑_{k≥0} \binom{j − 1 − s}{k}x^{j−1−s−k}2^{k}z^{k}c_{s}(j),

where, by Lemma A8, c_{s}(j) is a polynomial in j of degree 2s. Finally, we have

(x + m + 2j − z+2)_{2n−2j−2} = (−x + z − m − 2n + 1)_{2n−2j−2}

= ∑_{t≥0}(−x + z)^{2n−2j−2−t}d_{t}(j)

= ∑_{t≥0} ∑_{l≥0} \binom{2n − 2j − 2 − t}{l}(−1)^{t+l}x^{2n−2j−2−t−l}z^{l}d_{t}(j),

where, by Lemma A8, d_{t}(j) is a polynomial in 2n − 2j − 2 of degree 2t, and as such is a polynomial in j of degree 2t.

Putting things together we get

(2x + m + z + 1)_{j−1} (x + 2z − j + 2)_{j−1} (x + m + 2j − z + 2)_{2n−2j−2} (m + 3j − 3z)

= (m + 3j − 3z) ∑_{p,q≥0} x^{p}z^{q} 2^{j}_{∑_{r+s+t=2n−4−p−q} ; h+k+l=q}(−1)^{t+l} 2^{−1−r−h+k}

× \binom{j − 1 − r}{h}\binom{j − 1 − s}{k}\binom{2n − 2j − 2 − t}{l}b_{r}(j)c_{s}(j)d_{t}(j).

Again, the (finite) range of the inner sum does not depend on j. Hence, by what we know about b_{r}(j), c_{s}(j), and d_{t}(j), and since a binomial \binom{j+a}{ν} is a polynomial in j of degree ν, the inner sum is a polynomial in j of degree at most 2r +2s+2t+h+k +l = 2(2n − 4 − p − q) + q. Combining with (m + 3j − 3z), we see that the coefficient of x^{p}z^{q} in (A.6) is a polynomial in j of degree at most 2(2n − 3 − p − q) + q − 1, as desired. □

References

1. G. E. Andrews, Plane partitions V: The t.s.s.c.p.p. conjecture, J. Combin. Theory Ser. A 66 (1994), 28–39.

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

3. G. E. Andrews and D. W. Stanton, Determinants in plane partition enumeration, preprint.

4. W. F. Doran, A connection between alternating sign matrices and totally symmetric self-comp-lementary plane partitions, J. Combin. Theory Ser. A 64 (1993), 289–310.

5. G. Gasper and M. Rahman, Basic hypergeometric series, Encyclopedia of Mathematics And Its Applications 35, Cambridge University Press, Cambridge, 1990.

6. I. M. Gessel and X. Viennot, Determinants, paths, and plane partitions, preprint (1989).

7. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Massachusetts, 1989.

8. C. Jordan, Calculus of finite differences, 3rd edition, Chelsea Publ. Comp., New York, 1965.

9. C. Krattenthaler, Some q-analogues of determinant identities which arose in plane partition enumeration, Séminaire Lotharingien Combin. 36 (1996), paper B36e, 23 pp.

10. W. H. Mills, D. H. Robbins and H. Rumsey, Self–complementary totally symmetric plane partitions, J. Combin. Theory A 42 (1986), 277–292.

11. M. Rahman and A. Verma, Quadratic transformation formulas for basic hypergeometric series, Trans. Amer. Math. Soc. 335 (1993), 277–302.

12. V. N. Singh, The basic analogues of identities of the Cayley–Orr type, J. London Math. Soc. 34 (1959), 15–22.

13. L. J. Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.

14. R. P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth & Brooks/Cole, Pacific Grove, California, 1986.

15. J. R. Stembridge, Nonintersecting paths, pfaffians and plane partitions, Adv. in Math. 83 (1990), 96—131.

16. D. Zeilberger, A constant term identity featuring the ubiquitous (and mysterious) Andrews– Mills–Robbins–Rumsey numbers 1, 2, 7, 42, 429, …, J. Combin. Theory Ser. A 66 (1994), 17–27.

17. D. Zeilberger, Reverend Charles to the aid of Major Percy and Fields medalist Enrico, Amer. Math. Monthly 103 (1996), 501–502.

18. D. Zeilberger, Dodgson’s determinant-evaluation rule proved by TWO-TIMING MEN and WO-MEN, Elect. J. Combin. 4 (no. 2, “The Wilf Festschrift”) (1997), #R22, 2 pp.

Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.