The Factorization of a Polynomial Defined by Partitions^{∗}

1. Introduction It is best to work with unordered partitions. Thus if k is a positive integer, a partition of

length r of the interval [0, k] is a sequence, 0 = k_{0} < k_{1} < ⋯ < k_{r} = k, of positive integers. Set k′_{1} = k − k_{i}.

Fix k, and let x, Y, and Δ be three indeterminates. From the polynomial P_{k}(x, Y, Δ) given by

∑_{{k_{1},...,k_{r−1}}} x^{k−r} ∏_{i=1}^{r} (k′_{i} + Y + Δ(k_{i} − k_{i−1}))( ∏_{i=1}^{r−1} k_{i}k′_{1})^{−1}.

In the summation r is not fixed, so that the sum runs over all unordered partitions of k. The polynomial is of degree k in Y, and the coefficient of Y^{k} is ((k − 1)!)^{−2}.

It can be factored explicitly. For this it is convenient to write

Δ = h_{p,q}(m) = \frac{((m + 1)p − mq)^{2} − 1}{4m(m + 1)}.

Observe that if m ≠ 0, −1 then, given Δ, this equation can always be solved for p and q. Set

Y_{s}(m) = (((1 − k)^{2} − (p − q + s)^{2})m^{2} + 2((1 − k) − (p − q + s)p)m + 1 − p^{2})/4m(m + 1)
= h_{1,k}(m) − h_{p,q−s}(m),
Y′_{r}(m) = (((k − 1)^{2} − (p − r − q)^{2})m^{2} + 2((k − 1)k − (p − r − q)(p − r))m
+ k^{2} − (p − r)^{2})/4m(m + 1)
= h_{k,1}(m) − h_{p−r,q}(m).

Theorem 1.

(a) If m is defined by x = −m/(m + 1) and if Δ = h_{p,q}(m), then

P_{k}(x, Y, Δ) = ((k − 1)!)^{−2} ∏_{{|s|<k \atop s≡k−1(mod 2)}} (Y − Y_{s}(m)).

(b) If m is defined by x = −(m + 1)/m and if Δ = h_{p,q}(m), then

P_{k}(x, Y, Δ) = ((k − 1)!)^{−2} ∏_{{|r|<k \atop r≡k−1(mod 2)}} (Y − Y′_{r}(m)).

∗ Appeared in Commun. Math. Phys. vol. 124 (1989).

The purpose of this paper is to prove this theorem. As is explained in an appendix, it has its origins in the theory of the Virasoro algebra and conformally invariant quantum fields. Thanks are due to Y. Saint-Aubin for explaining to me the formulas (A.1), (A.2) proved by him and Benoit in [BSA], for they were the starting point of this paper, to W. Casselman for a number of conversations and, in particular, for checking the critical Identity 2.4 on the computer long before I was able to prove it, to Lyman Hurd for instruction in the use of the computer, and to W.-C. Hsiang for avuncular advice about the title.

2. Simple Reductions The two parts of the theorem are equivalent. They are both stated, because they are both to

be used in the Appendix. If m′ = −m − 1 then

\frac{m + 1}{m} = \frac{m′}{m′ + 1}

and

h_{p,q}(m) = h_{q,p}(m′)

for all p, q. Thus upon interchange of p and q the expression Y_{s}(m′) becomes Y′_{s}(m).

It is enough to prove the first statement of the theorem. We begin with a sequence of observations, stated as lemmas. To indicate the dependence of Y_{s}(m) on k we write Y_{s}^{k}(m).

Lemma 2.1.

Y_{s}^{k+2}(m) = Y_{s}^{k}(m) − 1 − (k + 1)x.
The difference Y_{s}^{k+2}(m) − Y_{s}^{k}(m) is seen upon inspection to be

\frac{((k + 1)^{2} − (k − 1)^{2})m^{2} − 2((k + 1) − (k − 1))m}{4m(m + 1)} = \frac{km − 1}{m + 1} = \frac{(k + 1)m}{m + 1} − 1.

Lemma 2.2. The product

(Y − Y_{k+1}^{k+2}(m))(Y − Y_{−k−1}^{k+2}(m))

is equal to

(Y + Δ)(Y + Δ + k + 1) + (k + 1)x(Y + (k + 2)Δ).

The lemma is tantamount to two assertions:

\begin{matrix}Y_{k+1}^{k+2}(m) + Y_{−k−1}^{k+2}(m) = −2Δ − (k + 1) − (k + 1)x; \\ Y_{k+1}^{k+2}(m) + Y_{−k−1}^{k+2}(m) = Δ(Δ + k + 1) + (k + 1)(k + 2)xΔ. \end{matrix}

The sum on the left of the first identity is equal to

( − 2(p − q)^{2}m^{2} − 4(k + 1)m − 4(p − q)pm + 2(1 − p^{2}))/4m(m + 1).

Since

Δ = ((p − q)^{2}m^{2} + 2(p − q)pm + p^{2} − 1)/4m(m + 1),

the first equality is immediate.

For the second, one observes that the product on the left is

\begin{matrix}(((p − q)^{2}m^{2} + 2((k + 1) + (p − q)p)m + p^{2} − 1)^{2} \\ − 4(k + 1)^{2}((p − q)m^{2} + pm)^{2})/16m^{2}(m + 1)^{2}. \end{matrix}

and this is

(Δ + \frac{k + 1}{2(m + 1)})^{2} − (k + 1)^{2}(Δ + 1/4m(m + 1))(m/m + 1).

The second equality follows. Lemma 2.3.

(a) P_{1}(x, Y, Δ) = Y − Y_{0}^{1}(m),

(b) P_{2}(x, Y, Δ) = (Y − Y_{−1}^{2}(m))(Y − Y_{1}^{2}(m)). The first assertion is clear; the second follows from the previous lemma and a direct calculation of P_{2}(x, Y, Δ) as

(Y + 1 + Δ)(Y + Δ) + x(Y + 2Δ).

Theorem 1(a) is thus seen to be equivalent to the validity of the following identity. Identity 2.4. The polynomial P_{k+2}(x, Y, Δ) is equal to the product of

(k(k + 1))^{−2}P_{k}(x, Y + 1 + (k + 1)x, Δ)  (2.a)

and

(Y + Δ)(Y + Δ + k + 1) + (k + 1)x(Y + (k + 2)Δ).

Fix r > −2 and consider on both sides of the identity the coefficient of x^{k−r}. On the left it is P_{k+2}^{r+2}(Y, Δ), the sum over all partitions {k_{1}, …, k_{r+1}} of [0, k + 2] into r + 2 intervals of the expression

∏_{i=1}^{r+2} (k′_{i} + Y + Δ(k_{i} − k_{i−1})) ∏_{i=1}^{r+2}(k_{i}k′_{i})^{−1}.

Since k_{i} − k_{i−1} = k′_{i−1} − k′_{i}, this equals

∏_{i=1}^{r+2} (Δ(Y + k′_{i−1}) + (1 − Δ)(Y + k′_{1})) ∏_{i=1}^{r+1}(k_{i}k′_{i})^{−1}.  (2.b)

If S_{k}^{r}(Y + 1, Δ) is the coefficient of x^{k−r} in (2.a) then the coefficient of x^{k−r} on the right side of the identity is

S_{k}^{r}(Y + 1, Δ)(Y + Δ)(Y + Δ + k + 1) + S_{k}^{r+1}(Y + 1, Δ)(k + 1)(Y + (k + 2)Δ).  (2.c)

We fix k and r, and show that the coefficients x^{k−r} on both sides of the identity are equal.

3. Further Reductions To calculate S_{k}^{r}(Y, Δ) we have to expand the products

x^{k−s} ∏_{i=1}^{s} (k′_{i} + Y + (k + 1)x + Δ(k_{i} − k_{i−1})),

retaining only the coefficient of x^{k−r}. Thus we obtain a sum over all partitions of k and over all subsets Σ with r elements of those partitions of

(k + 1)^{s−r} ∏_{i∈Σ} (k′_{i} + Y + Δ(k′_{i−1} − k′_{i})) ∏_{i=1}^{s−1}(k_{i}k′_{i})^{−1}.  (3.a)

Observe that r is fixed but that s varies from term to term in the sum. The notation i ∈ Σ is abusive. It is the interval I = [k_{i−1}, k_{i}] that belongs to Σ. Let e_{I} = k_{i−1}, e′_{I} = k′_{i}.

The union of the intervals I in Σ may or may not cover [0, k]. There will be a certain number g(Σ) of open intervals or gaps left uncovered. We divide the endpoints θ of the intervals in Σ into four types, the extreme, the bound, the left free, the right free. The corresponding sets will be denoted Θ^{e}, Θ^{b}, Θ^{lf}, Θ^{rf}. The endpoint θ will be said to be extreme if it is 0 or k, to be left free if it separates a gap on its left from an interval of Σ on its right, to be right free if it separates an interval on its left from a gap on its right, and to be bound if it is a common endpoint of two intervals in I.

Lemma 3.1. The coefficient S_{k}^{r}(Y + 1, Δ) is the sum over all Σ with r elements of the product of

(k + 1)^{g(Σ)−2} ∏_{I∈Σ} (Δ(Y + k + 2 − (e_{I} + 1)) + (1 − Δ)(Y + e′_{I} + 1))

and

{∏_{Θ^{e}} k ∏_{Θ^{b}} θ(k − θ) ∏_{Θ^{lf}}(k − θ)(k + 1 + θ) ∏_{Θ^{rf}} θ(θ + 1)}^{−1} .

The product in the first factor is obtained by writing

k′_{i} + Y + 1 + Δ(k′_{i−1} − k′_{i}) = Δ(Y + k + 2 − (e_{I} + 1)) + (1 − Δ)(Y + e′_{I} + 1).

The factor (k + 1)^{−2} is extracted from the factor (k(k + 1))^{−2} in (2.a). Ignoring it, we have to evaluate the sum over all partitions containing a given Σ of

k^{−2}(k + 1)^{s−r}( ∏_{i=1}^{s−1} k_{k}k′_{i})^{−1}.  (3.b)

The partitions containing Σ are obtained by partitioning all the gaps. Thus the sum of the expressions (3.b) is the product of

{∏_{Θ^{e}} k ∏_{Θ^{b}} θ(k − θ)}^{−1}

with the product over all gaps of

(a(a + h)a′(a′ + h))^{−1} ∑_{A} ∏_{j∈A}(a + j)^{−1}(a′ + h − j)^{−1}(a + a′ + h + 1)^{|A|+1}.  (3.c)

Here a is the left endpoint of the gap, a′ is the distance of its right endpoint from k, and h its length, so that k = a + a′ + h. If one of a or a′ is 0, it is to be omitted from the factor preceding the sum, which runs over all subsets of {1, …, h − 1}.

The expansion (3.c) is the product of k + 1 with

(a(a + h)a′(a′ + h))^{−1} ∏_{j=1}^{h−1} (1 + \frac{a + a′ + h + 1}{(a + j)(a′ + h − j)}).

Upon simplification this become

(a(a + h)a′(a′ + h))^{−1} ∏_{j=1}^{h−1} \frac{(a + j + 1)(a′ + h − j + 1)}{(a + j)(a′ + h − j)} = \frac{1}{aa′} · \frac{1}{(a + 1)(a′ + 1)}.

The lemma follows. Notice that if, for example, a = 0 then it is to be omitted, and a + 1 = 1; so the right side of this equality is 1/a′(a′ + 1).

The expression (2.b) is equal to

∏_{I} (Δ(Y + k + 2 − e_{I}) + (1 − Δ)(Y + e′_{I})) ∏_{i=1}^{r+1}(k_{i}k′_{i})^{−1}.

The first product is over the intervals in the partitions. We expand this product by writing each of the linear factors in the first product as a sum of four terms: Δ(Y +k+2); −Δe_{I}; (1−Δ)Y; (1−Δ)e′_{I}. To these we attach respectively the labels: (−1, 0); (−1, 1); (1, 0); (1, 1); or often, and preferably, the symbols: ⊖ ⟵; ⟵; ⊖ ⟶; ⟶. The labels or the symbols are to be regarded as attached to the interval defining the linear factor, so that the label may be written (α(I), μ(I)). The first term defines the direction of the arrow. The whole collection of symbols defines a diagram

→⟶ ⊖ ⟵⟵,  (3.d)

the lengths of the arrows being the lengths of the partitions. Let a′, a, b′, b be the number of arrows of the four types, so that a′ + a + b′ + b = r + 2. Then P_{k+2}^{r+2}(Y, Δ) may be written as

∑_{a′,a,b′,b}(−1)^{a}Δ^{a′+a}(1 − Δ)^{b′+b}(Y + k + 2)^{a′}Y^{b′}P_{k+2}(a′, a, b′, b).

The expression P_{k+2}(a′, a, b′, b) is the sum over all diagrams (3.d) for which a′, a, b′, b have the given values of

∏_{I} A(I),

where

A(I) = e_{I}^{μ(I)−1}e_{I}′^{−1}

if I is negatively oriented, and

A(I) = e′_{I}^{μ(I)−1}e_{I}^{−1}

if it is positively oriented. It is again understood that e_{I} or e′_{I} is suppressed if it is 0. Moreover, those diagrams for which the initial interval is of type ← or the final interval of type → are excluded from the sum.

It is clear from Lemma 3.1 that S_{k}^{r}(Y + 1, Δ) has a similar expansion

∑_{a′,a,b′,b}(−1)^{a}Δ^{a′+a}(1 − Δ)^{b′+b}(Y + k + 2)^{a′}Y^{b′}S_{k}(a′, a, b′, b),

where now the constraint on a′, a, b′, b is that a′ + a + b′ + b = r. If any of a′, a, b′, b is negative then S_{k}(a′, a, b′, b) is understood to be 0.

Observe that (Y + Δ)(Y + Δ + k + 1) is equal to the sum of

Δ^{2}(Y + k + 2)^{2} + 2Δ(1 − Δ)Y (Y + k + 2) + (1 − Δ)^{2}Y^{2},
−Δ(1 − Δ)(k + 1)^{2} − Δ(1 − Δ)Y (k + 1) + Δ(1 − Δ)(Y + k + 2)(k + 1),

and

−Δ^{2}(Y + k + 2)(k + 1) + (1 − Δ)^{2}(k + 1),

while

Y + (k + 2)Δ = Δ(Y + k + 2) + (1 − Δ)Y.

Thus the identity is a result of the following lemma.

Lemma 3.2. P_{k+2}(a′, a, b′, b) is equal to the sum of the four expressions:

\begin{matrix}S_{k}(a′ & − 2, a, b′, b) + 2S_{k}(a′ − 1, a, b′ − 1, b) + S_{k}(a′, a, b′ − 2, b); \\ (k + 1)^{2}S_{k}(a′, a − 1, & b′, b − 1) + (k + 1)S_{k}(a′, a, b′ − 1, b − 1) + (k + 1)S_{k}(a′ − 1, a − 1, b′, b); \\ (k & + 1)S_{k}(a′ − 1, a, b′, b − 1) + (k + 1)S_{k}(a′, a − 1, b′ − 1, b); \end{matrix}

and

(k + 1)S_{k}(a′, a, b′ − 1, b) + (k + 1)S_{k}(a′ − 1, a, b′, b).

If we ignore the length of the arrows in (3.d) we obtain diagrams in which only the direction and the type of arrow is significant. Given such a diagram, we let P (∗) be the sum over all partitions and labelings of type ∗ of ∏_{I} A(I). To each diagram ∗ we can attach integers a′(∗), a(∗), b′(∗), and b(∗). Then

P_{k+2}(a′, a, b′, b) = ∑ P_{k+2}(∗),

the sum being over all diagrams with the given values of a′, a, b′, and b. For example, recalling the conditions on the extreme arrows, we see that

P_{k+2}(0, 1, 1, 1)

equals

P_{k+2}(⟶⟼ ⊖ ⟵) + P_{k+2}(⟶⟵ ⟼ ⊖ ) + P_{k+2}( ⊖ ⟶⟼⟵).

In the same way,

S_{k}(a′, a, b′, b) = ∑ S_{k}(∗).

4. A Special Case If a′ = b′ = 0 then Lemma 3.2 reduces to

P_{k+2}(0, a, 0, b) = (k + 1)^{2}S_{k}(0, a − 1, 0, b − 1).

This is implied immediately by the following proposition.

Proposition 4.1. If a′(∗) = b′(∗) = 0 then

P_{k+2}(→ ∗ ←) = (k + 1)^{2}S_{k}(∗).

The abstract diagram → ∗ ← is obtained by juxtaposing a sequence of diagrams of the form

\underrightarrow{θ_{0}  θ_{1}} ⋯ \underrightarrow{θ_{i−1}} \underleftarrow{θ_{i}  θ_{i+1}} ⋯ \underleftarrow{θ_{s}} ,  (4.a)

in which a sequence of positively directed arrows is followed by a sequence of negatively directed arrows. The contribution to P (→∗←) from a concrete diagram, one in which the endpoints of all arrows have been fixed, is the product over the diagrams (4.a) of

\frac{1}{θ_{0}} \frac{1}{θ_{1}} ⋯ \frac{1}{θ_{i−1}} (θ_{i+1} − θ_{i−1} − 1)\frac{1}{k + 2 − θ_{i+1}} ⋯ \frac{1}{k + 2 − θ_{s−1}} \frac{1}{k + 2 − θ_{s}} .

Notice that θ_{i} does not occur here and the only condition on the sequence θ_{0}, θ_{1}, …, θ_{i−1}, θ_{i+1} ⋯ θ_{s−1} is that

θ_{0} < θ_{1} < ⋯ < θ_{i−1} < θ_{i+1} < ⋯ < θ_{s−1} < θ_{s}.

Notice that 1/θ_{0} is suppressed if θ_{0} = 0 and 1/k + 2 − θ_{s} is suppressed if θ_{s} = k + 2. On the other hand, the abstract diagram ∗ begins with a sequence

→ ⋯ →,

that is then followed by a sequence of diagrams

← ⋯ ⟵⟼ ⋯ →,

and finally by a sequence

← ⋯ ← .

Any or all of these sequences may be empty.

The expression (k + 1)^{2}S_{k}(∗) will be treated using Lemma 3.1. Since we have multiplied by (k + 1)^{2} the factor (k + 1)^{g(Σ)−2} may be replaced by (k + 1)^{g(Σ)}.

There are two simple but important relations to note before beginning:

∑_{θ<j<η} \frac{1}{(k − θ)j} · \frac{k + 1}{(j + 1)(k + 1 − η)} + \frac{1}{k − θ} · \frac{1}{η} = \frac{1}{(θ + 1)(k + 1 − η)} :  (4.b)
∑_{θ<j<η} \frac{1}{η(k − j)} · \frac{k + 1}{(k + 1 − j)(θ + 1)} + \frac{1}{(k − θ)η} = \frac{1}{(θ + 1)(k + 1 − η)}.  (4.c)

Since

\frac{1}{j(j + 1)} = \frac{1}{j} − \frac{1}{j + 1}, \frac{1}{(k − j)(k − j + 1)} = \frac{1}{k − j} − \frac{1}{k − j + 1},

the left-hand sides are easily calculated and found to be equal to the right-hand sides.

We next calculate a factor of that part of S_{k}(∗) obtained from diagrams whose first segment is

\underrightarrow{η_{1} θ_{1}}  \underrightarrow{η_{s} θ_{s}}

with θ_{1}, …, θ_{s} given. Fixing θ_{1} and summing over the possible η_{1}, we obtain a contribution

(k + 1 − θ_{1})\{ ∑_{η_{1}=1}^{θ_{1}−1} \frac{k + 1}{(k + 1 − η_{1})(k − η_{1})} · \frac{1}{θ_{1}} + \frac{1}{k · θ_{1}} \} = 1.

The factor k + 1 − θ_{1} comes from the product in the first term of Lemma 3.1. The factor (k + 1) in the numerator in the sum comes from the first gap, which is present if η_{1} > 0 but not if η_{1} = 0. The factor 1/θ_{1} is there whether θ_{1} is right free or bound. If θ_{1} is right free the additional factor 1/(θ_{1}+1) will be part of the contribution attached to the second arrow. The factor (k+1−η_{1})(k−η_{1}) is there because η_{1} is left free if it is positive. If η_{1} = 0 then it is extreme and contributes 1/k.

Passing on to the contribution from the second arrow, we fix θ_{1} and θ_{2}, and form the sum,

(k + 1 − θ_{2})\{ ∑_{η_{2}=θ_{1}+1}^{θ_{2}−1} \frac{k + 1}{(k + 1 + η_{2})(k − η_{2})} · \frac{1}{θ_{2}} + \frac{1}{(k − θ_{1})θ_{2}} \} = \frac{1}{θ_{1} + 1}.

Continuing, we obtain as the contribution from the initial segment, except for a supplementary factor arising from the last arrow that is to be treated later,

\frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s−1} + 1},

where 0 < θ_{1} < ⋯ < θ_{s}. In the same way the contribution of the final segment

\underleftarrow{η_{1}} ⋯ \underleftarrow{η_{t}}

is

\frac{1}{(k + 1 − η_{1})} ⋯ \frac{1}{(k + 1 − η_{t−1})}.

We now turn our attention to the contribution of one of the intermediate segments

← ⋯ ← → ⋯ → .

First of all, fix θ, η and consider the total contribution of

θ i_{⟵} j η_{⟶}

for all possible i, j. It is

\frac{(η − θ − 1)}{(k − θ)η}.

Once again, if θ is left free we do not include the factor 1/(k + 1 − θ), and if η is right free we do not include the factor 1/(η + 1), nor do we include a factor (k + 1) from a gap at either end.

For a fixed i and j the contribution is

\begin{matrix}\frac{θ + 1}{k − θ} · \frac{1}{i(i + 1)} · \frac{1}{(k − j)(k + 1 − j)} · \frac{(k + 1 − η)}{η} · (k + 1), i < j, \\ \frac{θ + 1}{k − θ} · \frac{1}{i(k − j)} · \frac{k + 1 − η}{η} , i = j. \end{matrix}

Fixing j and summing over i we obtain

∑_{0<j<η} \frac{1}{(k − j)} · \frac{1}{(k + 1 − j)} \frac{k + 1 − η}{η} = \frac{(η − θ − 1)}{(k − θ)η}.

This is not a very useful form in which to have the contribution. To transform it, we prove some simple lemmas. To have some notation, set

f_{θ}(θ_{1}) = \frac{k + 1}{(θ + 1)(k + 1 − θ_{1})}  θ > θ_{1},
= 1  θ = θ_{1}.

Set

g_{η}(η_{1}) = \frac{k + 1}{(k + 1 − η)(η_{1} + 1)}  η_{1} > η
= 1  η_{1} = η.

Lemma 4.2. If θ and η are given, θ < η then

∑_{θ≤θ_{1}<η_{1}≤η} f_{θ}(θ_{1})\frac{(η_{1} − θ_{1} − 1)}{(k − θ_{1})η_{1}}g_{η}(η_{1})

is equal to

\frac{1}{(θ + 1)(k + 1 − η)} ∑_{θ<θ_{2}<η} \frac{θ_{2}(k − θ_{2})}{(θ_{2} + 1)(k + 1 − θ_{2})}.

To calculate the sum over θ_{1}, η_{1} we write

η_{1} − θ_{1} − 1 = (k − θ_{1}) + η_{1} − (k + 1),

obtaining three sums that we easily evaluate using (4.b) and (4.c).

\begin{matrix}∑_{θ_{1}} ∑_{η_{1}} \frac{f_{θ}(θ_{1})g_{η}(η_{1})}{η_{1}} = \frac{1}{(θ + 1)(k + 1 − η)}\{ ∑_{θ<θ_{1}<η} \frac{(k + 1)(k − θ_{1})}{(k + 1 − θ_{1})(θ_{1} + 1)} + k − θ\}, \\ ∑_{η_{1}} ∑_{θ_{1}} \frac{f_{θ}(θ_{1})g_{η}(η_{1})}{(k − θ_{1})} = \frac{1}{(θ + 1)(k + 1 − η)}\{ ∑_{θ<η_{1}<η} \frac{(k + 1)η_{1}}{(k + 1 − η_{1})(η_{1} + 1)} + η\}, \end{matrix}

− ∑_{θ_{1}} ∑_{η_{1}} \frac{f_{θ}(θ_{1})(k + 1)g_{η}(η_{1})}{(k − θ_{1})η_{1})} = \frac{1}{(θ + 1)(k + 1 − η)} · \{ − ∑_{θ<θ_{1}<η} \frac{(k + 1)^{2}}{(k + 1 − θ_{1})(θ_{1} + 1)} − (k + 1)\}.

Replace in all three sums the right variable of summation by θ_{2}. Note also that

∑_{θ<θ_{2}<η} \frac{(k + 1 − θ_{2})(θ_{2} + 1)}{(k + 1 − θ_{2})(θ_{2} + 1)} = η − θ − 1 = (k − θ) + η − (k + 1).

Then to complete the proof of the lemma, we have only to observe that

(k + 1)(k − θ_{2}) + (k + 1)θ_{2} − (k + 1)^{2} + (k + 1 − θ_{2})(θ_{2} + 1) = θ_{2}(k − θ_{2}).

Note that

∑_{η=θ+1}^{θ′−1} \frac{(k − θ)(k + 1 − θ′)}{(k + 1 − η)(k − η)} = (θ′ − θ − 1) = ∑_{η=θ+1}^{θ′−1} \frac{(θ + 1)θ′}{η(η + 1)} .  (4.d)

Lemma 4.3. If θ and η are given, η > θ, and

\begin{aligned}A & = ∑_{θ<θ_{1}<···<θ_{s}<η} \frac{η · (θ_{1} − θ − 1)}{θ_{1}} · \frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s} + 1}, \\ B & = ∑_{θ<θ_{1}<···<θ_{s}<η} \frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s} + 1}(η − θ_{s} − 1), \end{aligned}

then A = B.

Set

\begin{aligned}A′ & = ∑_{θ<θ_{1}<···<θ_{s}<η} \frac{η(θ + 1)}{θ_{1}} · \frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s+1}} , \\ B′ & = ∑_{θ<θ_{1}<···<θ_{s}<η} \frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s−1} + 1}. \end{aligned}

It suffices to show that A′ = B′. Clearly

B′ = ∑_{θ<θ_{1}<···<θ_{s−1}<η} \frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s−1} + 1} · (η − θ_{s−1} − 1),

and

A′ = ∑_{θ<θ_{2}<···<θ_{s}<η} η · (θ + 1)(\frac{1}{θ + 1} − \frac{1}{θ_{2}} )\frac{1}{θ_{2} + 1} ⋯ \frac{1}{θ_{s} + 1}.

Since

η(θ + 1)(\frac{1}{θ + 1} − \frac{1}{θ_{2}} ) = \frac{η(θ_{2} − θ − 1)}{θ_{2}},

the lemma follows by induction, for it is clearly true for s = 1, when B′ = η − θ − 1 = A′. Lemma 4.4. If θ and η are given, η > θ and

\begin{matrix}A = ∑_{θ<η_{s}<···<η_{1}<η} \frac{(k − θ)(η − η_{1} − 1)}{(k − η_{1})} \frac{1}{k + 1 − η_{1}} ⋯ \frac{1}{k + 1 − η_{s}} , \\ B = ∑_{θ<η_{s}<···<η_{1}<η} \frac{1}{(k + 1 − η_{1})} ⋯ \frac{1}{(k + 1 − η_{s})}(η_{s} − θ − 1) \end{matrix}

then A = B.

This is the previous lemma in another guise. Before we begin transforming the contributions of the intermediate segments, we treat the simplest case, that in which no intermediate sequence occurs in ∗. Then → ∗ ← has concrete diagrams of the form

\underrightarrow{θ_{1}} ⋯ \underrightarrow{θ_{s−1} θ_{s}} \underleftarrow{θ_{s+1}} ⋯ \underleftarrow{θ_{r+1}},

and P (→ ∗ ←) is the sum over 0 < θ_{1} < ⋯ < θ_{s−1} < θ_{s+1} ⋯ < θ_{r+1} < k + 2 of

\frac{1}{θ_{1}} ⋯ \frac{1}{θ_{s−1}} (θ_{s+1} − θ_{s−1} − 1)\frac{1}{k + 2 − θ_{s+1}} ⋯ \frac{1}{k + 2 − θ_{r+1}} .  (4.e)

The concrete diagrams of type ∗ with gaps are either of the form

\underrightarrow{θ_{1}} ⋯ \underrightarrow{θ_{s−1}} \underleftarrow{θ_{s+1}} ⋯ \underleftarrow{θ_{r+1}},

in which there is a gap between θ_{s−1} and θ_{s+1} or of the form

\underrightarrow{θ_{1}} ⋯ →← ⋯ \underleftarrow{θ_{r+1}}.

In the first case the supplementary factors arising from the two internal arrows are 1/(θ_{s−1} + 1) and 1/(k + 1 + θ_{s+1}), together with a factor k + 1 coming from the gap. This yields a contribution

(k + 1)\frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s−1} + 1} \frac{1}{k + 1 − θ_{s+1}} ⋯ \frac{1}{k + 1 − θ_{r+1}} 0 < θ_{1} < ⋯ < θ_{r+1} < k.  (4.f)

Substituting θ_{i} for θ_{i}+1 in this product we see that we obtain all possible sequences contributing to (4.e) except those for which θ_{1} = 1 or θ_{r+1} = k+1. Subtracting a term (4.f) from the corresponding term of (4.e) we obtain

\frac{1}{θ_{1}} ⋯ \frac{1}{θ_{s−1}} ( − θ_{s−1} − (k + 2 − θ_{s+1}))\frac{1}{k + 2 − θ_{s+1}} ⋯ \frac{1}{k + 2 − θ_{r+1}} .

Breaking this into parts, cancelling either θ_{s−1} or k + 2 − θ_{s+1}, and then taking account of the multiplicities with which the missing θ_{s−1} or θ_{s+1} could occur, we see that we have contributions

\frac{−1}{1} \frac{1}{θ_{1}} ⋯ \frac{1}{θ_{s−2}} (θ_{s+1} − θ_{s−2} − 1)\frac{1}{k + 2 − θ_{s+1}} ⋯ \frac{1}{k + 2 − θ_{r+1}} ,

where

0 < 1 < θ_{1} < ⋯ < θ_{s−2} < θ_{s+1} < ⋯ k + 1,

and

\frac{−1}{θ_{1}} ⋯ \frac{1}{θ_{s−1}} (θ_{s+2} − θ_{s−1} − 1)\frac{1}{(k + 2 − θ_{s+2})} ⋯ \frac{1}{k + 2 − θ_{r+1}} \frac{1}{(k + 2) − (k + 1)},

where

1 < θ_{1} < ⋯ < θ_{s−1} < θ_{s+2} < ⋯ < k + 2.

This accounts for all contributions to P (→ ∗ ←) except those for which θ_{1} = 1, θ_{k+1} = k + 1. However, concrete diagrams with no gap between θ_{s−1} and θ_{s+1} yield

\frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s−2} + 1} \frac{1}{k + 1 − θ_{s+2}} ⋯ \frac{1}{k + 1 − θ_{r+1}} .

Taking account of the multiplicity θ_{s+2}−θ_{s−2}−1 with which the missing θ_{s−1} = θ_{s+1} can occur, we see that we obtain exactly those contributions to P (→∗←) associated to sequences θ_{1} = 1, θ_{r+1} = k + 1.

We now suppose that there is at least one intermediate segment, and treat the contribution of the first of these together with that of the initial segment. The junction of the two segments has the form

\underrightarrow{θ_{1}} \underrightarrow{θ_{2}} \underrightarrow{θ_{s−1}} \underleftarrow{θ_{s+1}ξ_{s+1}} \underleftarrow{θ_{t} ξ_{1}} \underrightarrow{θ_{t} η_{t}} ⋯ \underrightarrow{θ_{μ} η_{μ}}.

The arrow following upon η_{μ} is of the form ←. Suppose it begins at η.

If u = 1 let η′ = η, but if u > 1 we let η′ = ν_{2}. If t = s + 1, let θ′ = θ_{s−1}; otherwise let it be ξ_{t−1}. If the initial segment is empty, take θ′ = 0. In the same way let η′ = k if it is otherwise undefined. Then Lemma 4.2 transforms the contribution of the interval [θ′, η′] to

∑_{θ′<θ′′<η′} \frac{θ′′}{θ′ + 1} · \frac{1}{(θ′′ + 1)(k + 1 − θ′′)} · \frac{k − θ′′}{k + 1 − η′} .  (4.g)

The (θ′′ + 1)(k + 1 − θ′′) in the denominator will not be touched. If t > s + 1 we take θ′′/(θ′ + 1) together with the rest of the contribution of the interval [θ_{t−1}, ξ_{t−1}] obtaining

\frac{θ′′}{ξ_{t−1} + 1} · \frac{1}{ξ_{t−1}} · \frac{θ_{t−1} + 1}{k − θ_{t−1}} .

Summing over ξ_{t−1} we obtain

\frac{θ′′ − θ_{t−1} − 1}{k − θ_{t−1}}.

The contributions of the other intervals [θ_{i}, ξ_{i}], s + 1 ≦ i < k − 1 then yield the sum of

∑_{θ_{s−1}<θ_{s+1}<···<θ_{t−1}<θ′′} \frac{θ′′ − θ_{t−1} − 1}{k − θ_{t−1}} · \frac{1}{k − θ_{t−1} + 1} ⋯ \frac{k + 1}{k − θ_{s+1} + 1},  (4.h)

and

∑_{θ_{s−1}<θ_{s+2}<···<θ_{t−1}<θ′′} \frac{θ′′ − θ_{t−1} − 1}{k − θ_{t−1}} · \frac{1}{k − θ_{t−1} + 1} ⋯ \frac{k + 1}{k − θ_{s+2} + 1} · (θ_{s−1} + 1).  (4.i)

The first factor is there so that in both cases we can use 1/(θ_{s−1} + 1) as the contribution from the final arrow in the initial segment.

If t − 1 is s + 1, this manner of expressing the contribution is not obviously meaningful. It is better to take it as

∑_{θ_{s−1}<θ_{t−1}<θ′′} (\frac{θ′′ − θ_{t−1} − 1}{k − θ_{t−1}}) (\frac{k + 1}{k + 1 − θ_{t−1}} ) + (\frac{θ′′ − θ_{s−1} − 1}{k − θ_{s−1}}) · (θ_{s−1} + 1).  (4.j)

Lemma 4.5. The sum (4.j) is equal to

∑_{θ_{s−1}<θ_{t−1}<θ′′} \frac{θ_{t−1}}{k + 1 − θ_{t−1}} .

Write the numerator in the first sum as

(k + 1)(k − θ_{t−1}) − (k + 1)(k + 1 − θ′′).

The first term yields

∑_{θ_{s−1}<θ_{t−1}<θ′′} \frac{k + 1}{k + 1 − θ_{t−1}} .

The second may easily be summed in closed form to yield

−(k + 1)(k + 1 − θ′′) (\frac{1}{k + 1 − θ′′} − \frac{1}{k − θ_{s−1}} ) .

Adding to this the final term in (4.j) we obtain

( − (k + 1)(θ′′ − θ_{s−1} − 1) + (θ′′ − θ_{s−1} − 1)(θ_{s−1} − 1))/(k − θ_{s−1}) = −(θ′′ − θ_{s−1} − 1).

Since

θ′′ − θ_{s−1} − 1 = ∑_{θ′_{s−1}<θ_{t−1}<θ′′} \frac{k + 1 − θ_{t−1}}{k + 1 − θ_{t−1}} ,

the lemma follows.

To deal with the case that t − 1 > s + 1, we use Lemma 4.4 to write (4.h) as

∑_{θ_{s−1}<θ_{s+1}<···<θ_{t−1}<θ′′} (k + 1) (\frac{θ_{s+2} − θ_{s+1} − 1}{k − θ_{s+1}}) (\frac{1}{k + 1 − θ_{t−1}} ) ⋯ (\frac{1}{k + 1 − θ_{s+1}} ) ,

and (4.i) as

∑_{θ_{s−1}<θ_{s+2}<···<θ_{t−1}<θ′′} (\frac{θ_{s+2} − θ_{s+1} − 1}{k − θ_{s+1}}) (θ_{s−1} + 1) (\frac{1}{k + 1 − θ_{t−1}} ) ⋯ (\frac{1}{k + 1 − θ_{s+2}} ) .

Applying Lemma 4.5 we obtain

∑_{θ_{s−1}<θ_{s+1}<···<θ_{t−1}<θ′′} θ_{s+1} (\frac{1}{k + 1 − θ_{t−1}} ) ⋯ (\frac{1}{k + 1 − θ_{s−1}} ) .

Thus the conclusion is the same in all cases.

We put these contributions together with the contributions from the initial segment, writing θ_{s+1} as θ_{s+1} − θ_{s−1} − 1 + θ_{s−1} + 1. This yields a sum of two terms. The first is

\frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s−1} + 1}(θ_{s+1} − θ_{s−1} − 1) \frac{1}{k + 1 − θ_{s+1}} ⋯ \frac{1}{k + 1 − θ_{t−1}} ;

the second, in which the multiplicity of the missing θ_{s−1} is taken into account, is

\frac{1}{θ_{1} + 1} ⋯ \frac{1}{θ_{s−2} + 1}(θ_{s+1} − θ_{s−2} − 1)\frac{1}{k + 1 − θ_{s+1}} ⋯ \frac{1}{k + 1 − θ_{t−1}} .

Observe that upon replacing θ_{i} + 1 by θ_{i} these products correspond exactly to the initial contributions to P (→ ∗ ←), the second corresponding to θ_{1} = 1.

We now return to (4.g), and work towards the right; only the contribution (k −θ′′)/(k +1−η′) being pertinent. If there is only one intermediate segment, so that the complete diagram ∗ has the form

\underrightarrow{θ_{1}} ⋯ \underrightarrow{θ_{s−1}} \underleftarrow{θ_{s+1}} \underleftarrow{θ_{t}} \underrightarrow{η_{1}} \underrightarrow{η_{μ}} \underleftarrow{η_{μ+2}} ⋯ \underrightarrow{η_{r}}

then the contribution from the right is treated like that from the left and is the sum of

(\frac{1}{η_{2}} ) ⋯ (\frac{1}{η_{u} + 1}) (η_{u+2} − η_{u} − 1) (\frac{1}{k + 1 − η_{u+2}} ) ⋯ (\frac{1}{k + 1 − η_{v}} )

and

(\frac{1}{η_{2} + 1}) ⋯ (\frac{1}{η_{u} + 1}) (η_{u+3} − η_{u} − 1) (\frac{1}{k + 1 − η_{u+3}} ) ⋯ (\frac{1}{k + 1 − η_{v}} ) .

The second corresponds to the contribution to P (→∗←) in which the final θ is k + 1. Putting all contributions together, first multiplying the two parts and then adding over all possible sequences, and not forgetting (θ′′ + 1)^{−1}(k + 1 − θ′′)^{−1} from (4.g) we see that we obtain P (→∗←).

Suppose, however, that there is a second intermediate segment. so that where they abut the diagram has the form

⟵\underrightarrow{θ_{1}} ⋯ \underrightarrow{θ_{s}} \underleftarrow{η_{1}} ⋯ \underleftarrow{η_{t}} \underrightarrow{ν}

The contribution up to η_{1} is calculated as before. For example, if s = 1 it, or rather the part coming from the right of θ′′, is

\frac{k − θ′′}{k + 1 − η_{1}} .

More generally, using Lemma 4.3 and the obvious modification of Lemma 4.5, we obtain

(\frac{1}{θ_{2} + 1}) ⋯ (\frac{1}{θ_{s} + 1}) (\frac{k − θ_{s}}{k + 1 − η_{1}} ) .

The product

(\frac{1}{θ_{2} + 1}) ⋯ (\frac{1}{θ_{s} + 1})

corresponds exactly to what we need for the comparison with the contributions to P (→∗←). The final factor is to be put together with the contribution from η_{1} on to yield

∑_{θ_{s}<η_{1}<···η_{t}<ν} (\frac{k − θ_{s}}{k + 1 − η_{1}} ) (\frac{1}{k + 1 − η_{2}} ) ⋯ (\frac{1}{k + 1 − η_{t}} ) (\frac{ν − η_{t} − 1}{(k − η_{t})ν}) .

The final factor is the contribution previously calculated for a diagram ←→. Lemma 4.4 replaces this with

(η_{1} − θ_{s} − 1) (\frac{1}{k + 1 − η_{1}} ) ⋯ (\frac{1}{k + 1 − η_{t}} ) · \frac{1}{ν} .

The initial terms correspond exactly to what is needed for the comparison. Keep the final two for proceeding further to the right. Choose θ′, η′ as for (4.g). Thus θ′ is either η_{t−1} or θ_{s}. Then we have a contribution

∑_{θ′<η_{t}<ν≦η′} \frac{1}{(k + 1 − η_{t})} \frac{1}{ν} f_{η′}(ν).  (4.k)

The sum is over η_{t} and ν.

Lemma 4.6. The sum (4.k) is equal to

∑_{θ′<θ′′<η′} \frac{1}{(θ′′ + 1)(k + 1 − θ′′)} · \frac{k − θ′′}{k + 1 − η′} .

This is an immediate consequence of (4.b). The factor 1/(θ′′ + 1)(k + 1 − θ′′) is what we need for the comparison with the contribution to P (→ ∗ ←). The factor

\frac{k − θ′′}{k + 1 − η′} ,

which we have seen before, is what we need to treat the second intermediate segment like the first, and then inductively to proceed all across the diagram, thereby proving the proposition.

5. Completion of the Proof The proof of Lemma 3.2 will now be reduced to Proposition 4.1. Although the value of P (∗)

or S(∗) depends on the directions of the uncircled arrows in ∗ it does not depend on the directions of the circled arrows. They are important only when calculating P_{k+2}(a′, a, b′, b) or S_{k}(a′, a, b′, b). Thus we sometimes indicate a circled arrow simply by the symbol ⊖ −.

Lemma 5.9.

(a) P ( ⊖ −) = \frac{1}{k+1}P (→←).

(b) P (∗ ⊖ −) = \frac{1}{k+1}P (∗ →←) + \frac{1}{k+1}P (∗ ←),

(c) P ( ⊖ − ∗) = \frac{1}{k+1}P (→← ∗) + \frac{1}{k+1}P (→ ∗),

(d) P (∗_{1} ⊖ − ∗_{2}) = \frac{1}{k+1}P (∗_{1} →← ∗_{2}) + \frac{1}{k+1}P (∗_{1} → ∗_{2}) + \frac{1}{k+1}P (∗_{1} → ∗_{2}).

(e) S(∗_{1} ⊖ − ∗_{2}) = \frac{1}{k+1}S(∗_{1} ←→ ∗_{2}) + \frac{1}{k+1}S(∗_{1} ← ∗_{2}) + \frac{1}{k+1}S(∗_{1} → ∗_{2}).

In the formula (e) for S both ∗_{1} and ∗_{2} may be empty, but in the formula (d) for P they must not be, as ∗ must not be in formulas (b) and (c). Since P ( ⊖ −) = 1, P (→←) = k + 1, the first formula is clear. Consider the second. The contribution of a concrete diagram

{θ \atop ∗ ⊖ −}

is of the form A · 1/θ. The contribution of

θ_{∗ ⟶} θ′_{⟵}

to P (∗ →←) is A · (1/θ)(k + 1 − θ), while that of

θ_{∗ ⟵}

to P (∗ ←) is A. The formula (c) is of course proved in exactly the same way. For (d) the verification is also similar. The diagram

∗_{1} \begin{matrix}θ_{1} θ_{2} \\ ⊖ − \end{matrix} ∗_{2}

contributes a term A · (1/θ_{1}) · (1/k + 2 − θ_{2}) · B. The contributions of the three diagrams appearing on the right are respectively:

A · \frac{1}{θ_{1}} · \frac{1}{k + 2 − θ_{2}} · (θ_{2} − θ_{1} − 1) · B; A · \frac{1}{θ_{1}} · B; A · \frac{1}{k + 2 − θ_{2}} · B.

Proving the final formula is just a little less simple because we cannot operate entirely with concrete diagrams. The pertinent part of the concrete diagram for the left side of (e) is

{θ  θ_{1}  θ_{2}  η \atop |  | ⊖ −|  |.}

θ_{1} and θ_{2} are the endpoints of ⊖ − and θ and η are the closest endpoints of the arrows in ∗_{1} or ∗_{2}. If ∗_{1} is empty then θ = 0 and if ∗_{2} is empty then η = k.

The contribution from the interior of the interval [θ, η] is

∑_{θ≦θ_{1}<η_{1}≦η} f_{θ}(θ_{1}) · \frac{1}{(k − θ_{1})η_{1}} · g_{η}(η_{1}).

By this we mean that the factors 1/θ and 1/(k − η) are not taken into account.

On the other hand, replacing the undirected arrow ⊖ − in the interval θ_{1}, θ_{2} by the directed arrow →, we obtain

∑_{θ≦θ_{1}<η_{1}≦η} f_{θ}(θ_{1}) · \frac{k + 1 − η_{1}}{(k − θ_{1})η_{1}} g_{η}(η_{1}).

Taking instead ←, we obtain

∑_{θ≦θ_{1}<η_{1}≦η} f_{θ}(θ_{1}) · \frac{θ_{1} + 1}{(k − θ_{1})η_{1}} g_{η}(η_{1}).

Next, inside the same interval [θ, η] we insert two opposing arrows

θ_{|}  θ_{1}  η_{1}_{⟵}  θ_{2}  η_{2}_{⟶}  η_{|} .

We have to take the sum

∑_{θ≦θ_{1}<η_{1}≦θ_{2}<η_{2}≦η} f_{θ}(θ_{1}) (\frac{θ_{1} + 1}{(k − θ_{1})η_{1}} ) g_{θ_{2}}(η_{1}) (\frac{k + 1 − η_{2}}{(k − θ_{2})η_{2}} ) g_{η}(η_{2}).

Use (4.b) to sum over η_{1} to obtain

∑_{θ≦θ_{1}<θ_{2}<η_{2}≦η} f_{θ}(θ_{1}) (\frac{1}{k + 1 − θ_{2}} ) (\frac{k + 1 − η_{2}}{(k − θ_{2})η_{2}} ) g_{η}(η_{2}).

Then sum over θ_{2} to obtain

∑_{θ≦θ_{1}<η_{2}≦η} f_{θ}(θ_{1})\frac{η_{2} − θ_{1} − 1}{(k − θ_{1})η_{1}}g_{η}(η_{2}).

The last formula of the lemma follows immediately on replacing η_{2} in this sum by η_{1}, for

(θ_{1} + 1) + (k + 1 − η_{1}) + (η_{1} − θ_{1} − 1) = k + 1.

It is clear that the expansion permitted by this lemma can be iterated so that P_{k+2}(a′, a, b′, b) becomes a weighted sum of P (∗), where ∗ is a diagram with no circled arrows, and with its extreme arrows pointing inwards. The diagrams that we obtain have distinguished subdiagrams of the type →←, →, or ←, each provided with a supplementary orientation. Suppose there are c, c_{+}, c_{−} distinguished subdiagrams of the three types with negative orientation and d, d_{+}, d_{−} with positive orientation. Then a′ = c + c_{+} + c_{−}, d′ = d + d_{+} + d_{−}. In addition, P (∗) is to be provided with the weight (k + 1)^{−a′−b′}. Since the weight is independent of ∗ it can often be ignored. Each ∗ that occurs is actually of the form → ∗_{1} ← with a′_{1} = a′, b′_{1} = b′. By Proposition 4.1 we may replace (k + 1)^{−a′−b′}P (∗) by (k + 1)^{2−a′−b′}S(∗_{1}).

There are many types of diagrams that contribute to the sum of Lemma 3.2, and it is best to introduce a supplementary lable, because the same diagram ∗_{2} may contribute more than once. This supplementary label is one of the diagrams:

\begin{matrix}⊖ ⟶ ⊖ ⟶; & ⊖ ⟵ −⊖ ⟶; & ⊖ ⟶ ⊖ ⟵; & ⊖ ⟵ ⊖ ⟵; & ⟶ ⊖ ⟵ \\ ⟶ ⊖ ⟶; & ⊖ ⟶ ⟵; & ⊖ ⟵ ⟵; & ⟶ ⟵; & ⊖ ⟵ −⊖ ⟶ . \end{matrix}

Each of the diagrams defines two numbers e′, the number of negatively oriented circled arrows, and f′, the number of positively oriented circled arrows. If a′_{2} = a′(∗_{2}), b′_{2} = b′(∗_{2}) then a′_{2} + e′ = a′, b′_{2} + f′ = b′ and the weight attached to the contribution with the double label is (k + 1)^{2−e′−f′}.

For example, the term 2S_{k}(a′−1, a, b′−1, b) is the sum of contributions from pairs (∗_{2}, ⊖ ⟶ ⊖ ⟵) and pairs (∗_{2}, ⊖ ⟵ ⊖ ⟶ ), while S_{k}(a′, a, b′ − 1, b) is the sum of contributions from pairs (∗^{2}, ⊖ ⟶ ).

Using the lemma to expand, we obtain the common weight (k + 1)^{2−a′−b′}. The terms of the expansion are labeled by the same supplementary diagram ∗′_{3}, and by a diagram ∗_{3} with no circled arrows but with a certain number of distinguished subdiagrams of the form ←→, →, or ←. Each of these subdiagrams is provided with an orientation, corresponding to the orientation of the circled arrow from which it arose. Let there be i, i_{+}, i_{−} negatively oriented arrows of the three types and j, j_{+}, j_{−} positively oriented. Then a′_{2} = i + i_{+} + i_{−}, b′_{2} = j + j_{+} + j_{−}.

We have to establish a bijection between the diagrams ∗_{1}, taken with multiplicity, and the diagrams (∗_{3}, ∗′_{3}), also taken with multiplicity. Suppose ∗_{1} is obtained from ∗ =→ ∗_{1} ←. Thus ∗ is obtained by introducing one of the three diagrams →←, →, ←, in place of each of the circled arrows.

Let D_{1}, …, D_{s} be the introduced diagrams of the form →←, so that ∗ has the form

→ ⋯ \underleftrightarrow{D_{1}} \underleftrightarrow{D_{s}} ⋯ ← .

Thus there are s + 1 sequences S_{i} of arrows, from the beginning to the beginning of D_{1}, from the end of D_{1} to the beginning of D_{2}, and so on. In S_{i}, 1 ≦ i < s, let there be p_{i} positively directed arrows and q_{i} negatively directed arrows. Let p′_{i} of the p_{i} arrow arise from positively directed circled arrows by the substitution of → for ⊖ ⟶, let p′′_{i} arise from negatively directed circled arrows, and let p′′_{i} be original arrows. Define q′_{i}, q′′_{i}, q′′′_{i} similarly. Define p_{s}, q_{s}, p′_{s}, p′′_{s}, p′′′_{s}, q′_{s}, q′′_{s}, q′′′_{s} in the same way, except that the two end sequences are put together for the counting. Then the multiplicity with which the diagram with given locations of the D_{i} and given S_{i}, as well as given p′_{i}, p′′_{i}, p′′′_{i}, q′_{i}, q′′_{i}, q′′′_{i} contributes is

∏_{i=1}^{s} \frac{p_{i}!}{p′_{i}!p′′_{i}!p′′′_{i}!} · \frac{q_{i}!}{q′_{i}!q′′_{i}!q′′′_{i}!}.

Between the center of D_{i} and that of D_{i+1}, 1 ≦ i < s there is at least one diagram ←→. Let the first be E_{i}. If there is such a diagram after D_{s}, let E_{s} be the first. Consider the number of ways of assigning to the arrows between the centers of D_{i} and D_{i+1} that do not lie in E_{i} both circles and circled directions, and in such a way that the total number of each is as before . The number is

\frac{p_{i}!}{p′_{i}!p′′_{i}!p′′′_{i}!} · \frac{q_{i}!}{q′_{i}!q′′_{i}!q′′′_{i}!}.

Notice that we have begun to describe the diagrams ∗_{3} for which E_{1}, …, E_{s−1}, and E_{s} if it has been assigned, are the diagrams ←→ introduced in the expansion.

If E_{s} does not exist, then the multiplicity with which we can make the various assignments up to the center of D_{1} and after the center of D_{s} is

\frac{p_{s}!}{p′_{s}!p′′_{s}!p′′′_{s}!} · \frac{q_{s}!}{q′_{s}!q′′_{s}!q′′′_{s}!}.

Notice that the extreme arrows of ∗ no longer play a role; they are replaced by the first arrow of D_{1} and the last of D_{s}.

To make the comparison, we note that if E_{s} does not exist then D_{s} is determined as the final subdiagram of the form →←. We also agree that E_{i} and D_{i}, 1 ≦ i < s are to be obtained from circled arrows with the same orientation. Moreover if E_{s} does not exist, then we take ∗′_{3} to be ⊖ ⟶ or ⊖ ⟵, according to the circled orientation of the arrow yielding D_{s}. We finally note that D_{i} is determined by E_{i}. We simply move to the left from E_{i} to the first diagram →←.

Thus the bijection with multiplicity is established between diagrams ∗_{1} in which D_{s} is the final diagram →← in ∗ and diagrams (∗_{3}, ∗′_{3}) in which ∗′_{3} has only a single arrow.

If D_{s} is not the final diagram →← then E_{s} exists, and we take it as coming from a circled arrow with the same orientation as D_{s}. The only difference in the counting of the multiplicities is that for the contribution to S_{s} we remove the arrows in E_{s} as well as the extreme arrows and only add the first arrow of D_{1} and the last of D_{s}. To make the count come out correctly, we adjoin the supplementary ∗′_{3} with two arrows, each of which has three states that can be interpreted as circled with positive orientation, circled with negative orientation, and uncircled. Observe that this argument is also valid for the case that s = 0.

A pair of tables for the case r = 1, a′ = a = b = 1, b′ = 0 may help. Diagrams with the same lable, which lies between (i) and (v), are matched in the bijection.

Initial  Expanded ∗  ∗_{1}  s
⟶ ⊖ ⟵⟵  ⟶⟶⟵⟵  ⟶⟵  1  (i)
⟶⟶⟵  ⟶  0  (iv)
⟶⟵⟵  ⟵  0  (v)
⟶⟵ ⊖ ⟵  ⟶⟵⟶⟵  ⟵⟶  1  (ii)
⟶⟵⟵  ⟵  0  (v)
⊖ ⟵⟶⟵  ⟶⟵⟶⟵  ⟵⟶  1  (iii)
⟶⟶⟵  ⟶  0  (iv)
Initial ∗_{2}  Expanded ∗_{3}  ∗′_{3}
⟶ ⟵  ⟶⟵  ⊖ ⟵  (i)
⟵⟶  ⟵⟶  ⊖ ⟵  (ii)
⊖ ⟵  ⟵⟶  ⟶⟵  (iii)
⟵  ⟶⟵  (v)
⟶  ⟶⟵  (iv)
⟵  ⟵  ⟶ ⊖ ⟵  (v)
⟶  ⟶  ⟶⟵  (iv)

Appendix

The Virasoro algebra 𝔤 as an infinite-dimensional Lie algebra over C with basis L_{k}, k ∈ Z, and C and is defined by the conditions:

(i) C is central (ii) [L_{i}, L_{j}] = (i − j)L_{i+j} + δ_{i,−j} \frac{i(i^{2}−1)}{12}C. The facts reviewed below can be found in [4]. The Verma modules are infinite-dimensional vector spaces V_{h,c} on which 𝔤 acts and are at-

tached to two real parameters h and c. They are defined by the condition that they be universal with respect to the following property.

V_{h,c} is generated by a vector v_{ϕ} satisfying:

Cv_{ϕ} = cv_{ϕ}, L_{0}v_{ϕ} = hv_{ϕ}, L_{n}v_{ϕ} = 0, n > 0.

Thus V_{h,c} has a basis

v_{k_{1},k_{2},...,k_{r}} = L_{−k_{1}} ⋯ L_{−k_{r}}v_{ϕ}, k_{1} ≧ ⋯ ≧ k_{r} > 0.

However it may have other convenient bases as well. It carries a unique hermitian form ⟨u, v⟩ satisfying

(i) ⟨v_{ϕ}, v_{ϕ}⟩ = 1; (ii) ⟨L_{k}u, v⟩ = ⟨u, L_{−k}v⟩.

Let P (n) be the number of partitions of n. Then the space V_{n} spanned by {v_{k_{1},...,k_{r}}|Σk_{i} = n} has dimension P (n). If { , } is the hermitian form defined by {v_{k_{1},...,k_{r}}, v_{l_{1},...,l_{s}}} = 0 unless r = s, k_{1} = l_{1}, …, k_{r} = l_{r} then the matrix H_{n}(h, c) of ⟨ , ⟩ on V_{n} with respect to { , } is a polynomial in h and c whose determinant is a constant times

∏_{pq≦n}(h − h_{p,q})^{P (n−pq)}.

If we introduce m by the condition c = 1 − 6/m(m + 1), then

h_{p,q} = h_{p,q}(m) = \frac{((m + 1)p − mq)^{2} − 1}{4m(m + 1)} p, q ∈ N.

In particular if n = pq then det H_{n} vanishes on the curve h = h_{p,q}(m). A null vector is obtained by taking some row c_{k_{1},...,k_{r}}(m) of the matrix adjoint to H_{n}, and then setting

w_{p,q}(m) = ∑_{k_{1}+···+k_{r}=m} c_{k_{1},...,k_{r}}(m)v_{k_{1},...,k_{r}}.

Choose the row so that the vector (c_{k_{1},...,k_{r}}(m)) does not vanish identically. Since the coordinates of this vector are rational functions of m, we may write (c_{k_{1},...,k_{r}}(m)) as the product of a rational function of m and a vector u_{p,q}(m) = (d_{k_{1},...,k_{r}}(m)) with coefficients that are polynomials in m whose greatest common divisor is 1. To stress the dependence on p, q, for it is important, I write

d_{k_{1},...,k_{r}}(m) = d_{k_{1},...,k_{r}}^{p,q}(m).

To pass to a more convenient notation we take this p, q to be p′, q′ and with another p, q we set Δ = h_{p,q}(m). We form the rational functions of m, Y, Δ defined by

a_{k_{1},...,k_{r}}(m, Y, Δ) = (k_{r} + ⋯ + k_{2} + y + Δk_{1})(k_{r} + ⋯ + k_{3} + Y + Δk_{2}) ⋯ (Y + Δk_{r})

and by

P_{p′,q′}(m, Y, Δ) = ∑_{k_{1}+···+k_{r}=p′q′^{k_{1}≧···≧kr >0}} a_{k_{1},...,k_{r}}(m, Y, Δ)d_{k_{1},...,k_{r}}^{p′,q′}(m).

The highest power of Y that appears in P_{p′,q′}(m, Y, Δ) is Y^{n}, where n = p′q′, and it appears with coefficient d_{1,...,1}^{p′,q′}(m).

On the other hand, set

Y_{r,s}^{p′,q′} = h_{p′,q′}(m) − h_{p−r,q−s}(m).

Conjecture. If Δ = h_{p,q}, then

P_{p′,q′}(m, Y, Δ) = d_{1,...,1}^{p′,q′}(m) ∏_{{r+1≡p′(mod 2),|r|<p′ \atop s+1≡q′(mod 2),|s|<q′}} (Y − Y_{r,s}^{p′,q′}(m)).

It is important to observe that p, q and p′, q′ play utterly different roles in this identity. Before explaining the significance of this conjecture, I observe that for generic m the null space of H_{n}(h, c), h = h_{p′,q′}(m), c = c(m) is of dimension 1. Moreover, for all k_{1}, …, k_{r} such that Σk_{i} = n the vector

v_{k_{1},...,k_{r}} = L_{−k_{1}} ⋯ L_{−k_{r}}v_{ϕ}

lies in V_{n}, whether k_{1}, …, k_{r} are in decreasing order or not. In addition, it is not difficult to show that

∑_{{k_{1}+···+kr =n \atop k_{1}≥0}} e_{k_{1},...,k_{r}}a_{k_{1},...,k_{r}}(m, Y, Δ)

depends only on the vector

∑_{k_{1}+···+k_{r}=n} e_{k_{1},...,k_{r}}v_{k_{1},...,k_{r}}.

Thus if

∑ e_{k_{1},...,k_{r}}(m)v_{k_{1},...,k_{r}}

is any vector with values in the null space of H_{n}(c, h) the function

P (m, Y, Δ) = ∑ e_{k_{1},...,k_{r}}(m)a_{k_{1},...,k_{r}}(m, Y, Δ)

is determined by the coefficient p(m, Δ) of Y^{n}. Provided that this is not zero, the conjecture is tantamount to

P (m, Y, Δ) = p(m, Δ) ∏_{r,s} (Y − Y_{r,s}^{p′,q′}(m)).

In the two extreme cases, p′ = 1 or q′ = 1, Benoit and Saint-Aubin [BSA] have found an explicit formula for e_{k_{1},...,k_{r}}(m):

a) q′ = 1

e_{k_{1},...,k_{r}}(m)( − \frac{(m + 1)}{m})^{n−r}\{ ∏_{i=1}^{r−1}(k_{1} + ⋯ + k_{i})(k_{i+1} + ⋯ + k_{r})\}^{−1},  (A.1)
b) p′ = 1
e_{k_{1},...,k_{r}}(m)( − \frac{m}{m + 1})^{n−r}\{ ∏_{i=1}^{r−1}(k_{1} + ⋯ + k_{i})(k_{i+1} + ⋯ + k_{r})\}^{−1}.  (A.2)

The conjecture in these extreme cases follows immediately from these formulas in Theorem 1.

The quotient of the Verma module V_{h,c} by the space of null vectors is an irreducible module M_{h,c}. Select two parameters Δ′, Δ′′, as well as a third parameter Δ. A primary holomorphic field attached to these parameters is a formal series.

Φ(z) = z^{Δ′′−Δ′−Δ} ∑_{k∈Z}φ_{k}z^{k}.

Here φ_{k} is a matrix φ_{k,n′′,n′}, n′ ≧ 0, n′′ ≧ 0, n′, n′′ ∈ Z and

φ_{k,n′′,n′} : M′_{n} → M′′_{n′′}.

We have set M′ = M_{Δ′,c}, M′′ = M_{Δ′′,c}, c = c(m), and

M′_{n′} = {v ∈ M′|L_{0}v = (Δ′ + n′)v}, M′′_{n′′} = {v ∈ M′′|L_{0}v = (Δ′′ + n′′)v}.

Moreover φ_{k,n′′,n′} = 0 unless k = n′′ − n′, so we write φ_{n′′,n′} for φ_{n′′−n′,n′′,n′}.

The formal series Φ(z) is said to define a primary holomorphic field of weight Δ if the identity

L_{k}Φ − ΦL_{k} = z^{k+1} \frac{d}{dz} Φ + Δ(k + 1)z^{k}Φ  (A.a)

is valid for all k ∈ Z. The formal identity translates immediately into real identities for the operators φ_{n′′,n′} between finite-dimensional vector spaces. Although it is usually ignored, a basic problem is to decide for what values of Δ′, Δ′′, and Δ a primary field exists. This is particularly important for the discrete series parameters m ≧ 2, m ∈ Z,

h = h_{a,b}(m), 1 ≦ a < m, 1 ≦ b < n + 1.

Thus Δ′, Δ′′, Δ are all to belong to this set, Δ′ = h_{p′,q′}, Δ′′ = h_{p′′,q′′}, Δ = h_{p,q}.

It appears that it is not difficult to prove the existence of Φ(z) satisfying (A.a) provided one can construct φ_{0,k}, φ_{k,0} for all k ≧ 0, satisfying the conditions implied by (A.a). It is moreover easy to see that φ_{n′′,n′} is the adjoint of the operator φ_{n′,n′′} attached not to Δ′, Δ′′ but to Δ′′, Δ′ and the same Δ. Thus the necessary and sufficient condition for the existence of Φ(z) is that φ_{0,k} exist for all k for the parameters Δ′, Δ′′ and φ_{0,k} for the parameters Δ′′, Δ′.

It is clearly enough to determine the conditions for the first problem. Normalize Φ so that φ_{0,0} : v′_{ϕ} → v′′_{ϕ}. A simple calculation shows that

φ_{0,k}v′_{k_{1},...,k_{r}} = a_{k_{1},...,k_{r}}(m, Δ′ − Δ′′, Δ)v′′_{ϕ}, k = ∑ k_{i}.

Thus a necessary and sufficient condition for the existence of φ_{0,k} is that

u = ∑ c_{k_{1},...,k_{r}}v′_{k_{1},...,k_{r}} = 0

imply that

∑ c_{k_{1},...,k_{r}}a_{k_{1},...,k_{r}}(m, Δ′ − Δ′′, Δ) = 0.  (A.b)

It will probably be easy to show that if the condition (A.b) is satisfied by one null vector, then it is satisfied for all null vectors obtained from it by repeatedly applying elements of the Virasoro algebra. After that, it should not be too difficult, using results of Feigin and Fuchs [FF], to show that for the discrete series it is enough to verify it for u = u_{p′,q′} and u = u_{m−p′,m+1−q′}. Provided that d_{1,...,1}^{p′,q′}(m) and d_{1,...,1}^{m−p′,m+1−q′}(m) are not zero, and this seems likely, although I am not at the moment clear as to how it is to be proved, then the conjecture implies that the operators φ_{0,k} exists for all k and only if

Δ′ − Δ′′ = Y_{r_{1},s_{1}}^{p′,q′}(m)  (A.c)

and

Δ′ − Δ′′ = Y_{r_{2},s_{2}}^{m−p′,m+1−q′}(m),  (A.d)

for some pairs r_{1}, s_{1}, r_{2}, s_{2} satisfying r_{1} ≡ p′ + 1, r_{2} ≡ m − p′ + 1, s_{1} ≡ q′ + 1, s_{2} ≡ m − q′ modulo 2, and |r_{1}| < p′, |s_{1}| < q′, |r_{2}| < m − p′, |s_{2}| < m + 1 − q′.

For the present it is sufficient to examine the first equation, our only purpose being to verify that it leads to explicit conditions on p, q, p′, q′, and p′′, q′′. Set p_{0} = p − r_{1}, q_{0} = q − s_{1}. Since

Δ′ − Δ′′ = h_{p′,q′} − h_{p′′,q′′},

we infer from (A.c) that

(p′′ − q′′)^{2}m^{2} + 2(p′′ + q′′)p′′m + p′′^{2} = (p_{0} − q_{0})^{2}m^{2} + 2(p_{0} − q_{0})p_{0}m + p_{0}^{2}.

This equation is readily seen to be equivalent to the condition that either

(p′′ − q′′) − (p_{0} − q_{0})m + (p′′ − p_{0}) = (p′′ − p_{0})(m + 1) − (q′′ − q_{0})m = 0

or

(p′′ − q′′) + (p_{0} − q_{0})m + (p′′ + p_{0}) = (p′′ + p_{0})(m + 1) − (q′′ + q_{0})m = 0.

The second equation is obtained from the first on substituting p′′ → m − p′′, q′′ → m + 1 − q′′.

Since all quantities involved are integers, all solutions of the first equation are of the form p′′ = p_{0} + am, q′′ = q_{0} + a(m + 1), a ∈ Z. Since 0 < p, p′, p′′ < m, 0 < q, q′, q′′ < (m + 1), the integer must be 0, ±1 although not all these values are necessarily allowed.

The conclusion is that the conjecture leads to explicit, albeit somewhat elaborate, necessary and sufficient conditions on p, q, p′, q′, p′′, q′′ for the existence of a primary conformally invariant holomorphic field. There is a close connection between the problems of existence and the problem of establishing fusion rules. The conditions derived from the conjecture are close to those the attentive reader of the discussion of fusion rules in [BPZ] would expect, although perhaps not exactly the same.

References

1. Belavin, A. A., Polyakov, A. M., Zamolodchikov, A. B.: Infinite conformal symmetry in twodimensional quantum field theory, Nucl. Phys. B241, 333-380 (1984).

2. Benoit, L., Saint-Aubin, Y.: Explicit expressions for the null vectors φ_{p,1} and φ_{1,q′} of the discrete series representations of the Virasoro algebra, Phys. Lett. B215, 517-522 (1978).

3. Feigin, B.L., Fuchs, D. B.: Verma modules over the Virasoro algebra, In: Topology, SLN 1060 (1982).

4. Kac, V., Raina, A.: Lectures on highest-weight representations of infinite-dimensional Lie algebras. Singapore: World Scientific 1987.

Note added in proof. After this paper was submitted two preprints came to my attention that render the combinatorial arguments in it superfluous from some points of view, although not necessarily redundant. First of all, G. Felder in BRST Approach to Minimal Models has used the BRST method to construct primary fields and the conjecture of the appendix follows readily from his conclusions. Moreover, B. L. Feigin and D. B. Fuchs in Cohomology of some nilpotent subalgebras of the Virasoro and Kac-Moody Lie algebras take the direct algebraic approach of the Appendix to the existence of primary fields, but deal with the whole matter much more efficiently, more generally, and more elegantly. It is in particular clear from their discussion that the conjecture is an easy consequence of results already in [3].