J. Symbolic Computation (2005) 14, 000–100

A Proof of the Two Parameter q-Cases of the Macdonald - Morris Constant Term Root System

Conjecture for S(F_{4}) and S(F_{4})^{∨} via Zeilberger’s Method

FRANK G. GARVAN^{†} AND GASTON H. GONNET^{‡}

†Department of Mathematics, University of Florida, Gainesville, FL 32611, U.S.A. ‡Informatik, ETH, Zurich, Switzerland 8092

(Received 18 December 2005)

Doron Zeilberger has described a method for settling the q-case of the Macdonald-Morris root system constant term conjecture for any specific root system provided there is sufficient computer time, memory space and some luck. He illustrated the method by proving the S(G_{2})^{∨} case. His method involves finding and solving a linear system of equations. We remove the element of luck by showing that it is always possible to construct a triangular system. We apply the method to the so far open S(F_{4}) and S(F_{4})^{∨} cases. A consequence of our triangularity result is that, in the equal parameter case, the Macdonald-Morris constant terms (for a fixed root system) form a q-hypergeometric sequence.

1. Introduction

In 1982, Macdonald (1982) presented a collection of constant term conjectures relating to root systems. The most general of these conjectures (Macdonald, 1982, Conj. 3.3) is cast in the language of affine root systems S(R) and has the form

C.T. ∏_{α∈R^{+}}(q^{ε_{α}}x^{α}; q^{u_{α}})_{k_{α}}(q^{u_{α}−ε_{α}}x^{−α}; q^{u_{α}})_{k_{α}} = a certain explicit product.  (1.1)

Here C.T. means constant term in the Laurent polynomial in the x^{±α}; R is the underlying root system; k_{α} are nonnegative integers satisfying k_{α} = k_{β} whenever ∥α∥ = ∥β∥; ε_{α}, u_{α} are certain constant integers associated with the affine root system and (a; q)_{k} is the standard q-notation

(a)_{k} = (a; q)_{k} = (1 − a)(1 − aq) ⋯ (1 − aq^{k−1}).

The results of this paper were first announced in Macdonald’s constant term conjectures for exceptional root systems, Bulletin (new series) A. M. S., 24 (1991), 343–347.

The research for this paper was done while the first author was a postdoctoral fellow at the Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN 55455, and later as a Macquarie University Research Fellow at the School of Mathematics, Macquarie University, Sydney, NSW 2109, Australia.

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 2005 Academic Press Limited

We note that, except for R = BC_{n}, all ε_{α} ≡ 0. The right sides of (1.1) are spelled out explicitly in Morris’ thesis (Morris, 1982, Appendix C).

The S(A_{n}) case is a special case of Andrews’ q-Dyson conjecture (Andrews, 1975) which was proved by Zeilberger and Bressoud (1985). We should point out that Stembridge (1988) has found a short and elementary proof of the S(A_{n}) case. The S(G_{2}) case was proved independently by Habsieger (1986) and Zeilberger (1987). Zeilberger (1988) proved the S(G_{2})^{∨} and Kadell (to appear) proved the S(BC_{n}) case (and hence the S(B_{n}) and S(D_{n}) cases). Recently, Gustafson (1990) has proved the remaining infinite family cases S(B_{n})^{∨}, S(C_{n}) and S(C_{n})^{∨} using his q-analog of Selberg’s beta integral (Gustafson, to appear, eq. (2); Gustafson, 1990). We should also mention that the q = 1 case of (1.1) for F_{4} has been proved by Garvan (1990), the q = 1 case of (1.1) for all root systems was proved by Opdam (1989) and that in (Garvan, 1989) one of us presented an algorithmic approach for handling the related Macdonald-Mehta integrals. Hence, the S(F_{4}), S(F_{4})^{∨}, S(E_{6}), S(E_{7}) and S(E_{8}) cases of (1.1) have remained open.

Zeilberger (1988) presented a method for handling (1.1):

… a method that systematically handles the Macdonald conjectures for any given, fixed, root system, provided there are sufficient computer resources, and, for the time being, some luck.. . . Besides, I am almost sure that the element of luck can be disposed with, and that the method can be proved to constitute an effective method for settling the Macdonald and Macdonald-Morris conjectures for any given root system. …

In this paper we show how to dispose of the element of luck in Zeilberger’s method. His method involves an algorithm whose input is a vector and whose output is a linear equation. This algorithm comes from a certain q-functional. The problem is to find a set of inputs that will give a system with full rank, and then solve this system on a computer. We show that it is always possible to choose the q-functional and the set of inputs so that the the linear system is triangular. This phenomenon of triangularity has also been observed independently by Stembridge (1988).

In §2 we describe Zeilberger’s method. In §3 we prove the triangularity result mentioned above, for the S(R) case. The proof, for the S(R)^{∨} case, is completed in §6. We also prove an interesting triangularity result for the q = 1 case thus removing the element of luck in our method described in (Garvan, 1990). In §§4,5 and 7 we apply the method to the so far open S(F_{4}) and S(F_{4})^{∨} cases.

Our method boils down to showing that a certain seemingly monstrous rational function in q, s and t is in fact identically zero. This is done through the computer algebra package MAPLE. However, when we first embarked on this project in 1988 we could not simplify this rational function to zero, in either the S(F_{4}) or S(F_{4})^{∨} cases, without running out of memory. We then tried an interpolation approach. Later, on Wednesday November 14 16:32:08 MET 1990, using the newest Maple version V, we proved the S(F_{4}) case directly without using any interpolation. The S(F_{4})^{∨} case was proved using the interpolation approach. The computations were done at Waterloo and later at ETH. The machines used were watdragon (VAX 8650), watmum (VAX 785), watsol (SUN 4), daisy (MIPS R2000) and fioni (DEC 3100).

The q-cases of Macdonald’s Conjecture for F_{4} via Zeilberger’s Method 3

Let the affine root system S be fixed and consider the equal parameter case of (1.1), i.e. k_{α} ≡ a. A consequence of our triangularity results is that the sequence of constant terms on the left side of (1.1) for a = 0, 1, …, is a q-hypergeometric sequence (see (Zeilberger, to appear)). More importantly, the method constitutes an effective algorithm for verifying (1.1) for a fixed affine root system with parameters not necessarily equal. In §8 we discuss these results as well as prospects for S(E_{6}), S(E_{7}), S(E_{8}).

1.1. notation

Let R be an irreducible root system of rank ℓ embedded in the Euclidean space E. Let B = {γ_{1}, γ_{2}, …, γ_{ℓ}} be a ℤ-basis for R, i.e. a basis for E that satisfies

R ⊂ ⊕_{i=1}^{ℓ} ℤγ_{i}.

Usually we take B to be a base Δ for R. Zeilberger (1988) takes B to be the standard basis {e_{i}}_{i=1}^{ℓ}. Let Λ denote the root lattice. For β ∈ Λ we let c_{i}(β) be the i-th coordinate of β with respect to B so that

β = ∑_{i=1}^{ℓ} c_{i}(β)γ_{i}, (c_{i}(β) ∈ ℤ).

We define

x^{β} := ∏_{i=1}^{ℓ} x_{i}^{c_{i}(β)}.

We should point out that the left side of (1.1) is well-defined being independent of the choice of B.

For α ∈ R the reflection w_{α} through the hyperplane orthogonal to α is given by w_{α}(β) = β − ⟨β, α⟩α where ⟨β, α⟩ = 2(β, α)/(α, α). The group W = W (R) generated by the w_{α} (α ∈ R) is called the Weyl group of R. W acts on monomials by

w(x^{β}) = x^{w(β)}, (w ∈ W, β ∈ Λ),

and by linearity on Laurent polynomials.

A Laurent polynomial G is symmetric with respect to the Weyl group W if w(G) = G for every w in W. The sign of an element w of W, written sgn(w), is defined as (−1)^{n(w)}, where n(w) is the number of positive roots that w turns into negative roots; i.e. as |w(R^{+}) ∩ R^{−}|. A Laurent polynomial G is anti-symmetric if for any w in the Weyl group W, w(G) = sgn(w)G.

The fundamental chamber C is given by

C = C(Δ) := {β ∈ E : (α, β) > 0 for all α ∈ Δ}.

For α ∈ E we call α a bad guy if it lies on a reflecting hyperplane; i.e. there is a β ∈ R such that (β, α) = 0; otherwise, α is a good guy. Δ defines a natural partial order on E: define β ≺ α iff α − β has nonnegative coefficients with respect to Δ.

2. Zeilberger’s Method

We describe Zeilberger’s method when the root system, R, is irreducible and has at most two root lengths, so that all ε_{α} ≡ 0. The only irreducible root system with more than two root lengths is BC_{n}, for which (1.1) is already known. The method can be easily modified to handle the BC_{n} case as well. Let

k_{α} = \{ \begin{matrix}a, & α short, \\ b, & α long, \end{matrix}  (2.1)

u_{α} = \{ \begin{matrix}u_{s}, & α short, \\ u_{l}, & α long, \end{matrix}  (2.2)

and define

F′_{a,b}(x) := ∏_{α∈R^{+}}(x^{α}; q^{u_{α}})_{k_{α}}(q^{u_{α}}x^{−α}; q^{u_{α}})_{k_{α}},  (2.3)
H′_{a,b} := C.T. F′_{a,b}(x).  (2.4)

The Macdonald-Morris conjecture (1.1) asserts that H′_{a,b} has a nice explicit form. Instead of F′ and H′ we consider

F_{a,b}(x) := ∏_{α∈R^{+}}(x^{α}; q^{u_{α}})_{k_{α}}(q^{u_{α}}x^{−α}; q^{u_{α}})_{k_{α}−1},  (2.5)
H_{a,b} := C.T. F_{a,b}(x),  (2.6)

where a, b ≥ 1. It can be shown that H′_{a,b} and H_{a,b} satisfy

H′_{a,b} = H_{a,b} · W (q^{au_{s}}, q^{bu_{l}}),  (2.7)

where

W (t, s) = ∑_{w∈W} t^{n_{s}(w)}s^{n_{l}(w)}.  (2.8)

Here n_{s}(w) = |w(R_{short}^{+}) ∩ R^{−}| and n_{l}(w) = |w(R_{long}^{+}) ∩ R^{−}| for w in the Weyl group W, so that n(w) = n_{s}(w) + n_{l}(w). See (Zeilberger, 1988, §8) for a proof. We note that Macdonald (1972) has found that W (t, s) may be written as a nice product. The advantage of F_{a,b} over F′_{a,b} is that it is almost anti-symmetric. We have

F_{a,b}(x) = x^{δ}G_{a,b}(x),  (2.9)

where

G_{a,b}(x) := ∏_{α∈R^{+}}(x^{−α/2} − x^{α/2}) ∏_{α∈R}(q^{u_{α}}x^{α}; q^{u_{α}})_{k_{α}−1},  (2.10)

δ := \frac{1}{2} ∑_{α∈R^{+}} α,  (2.11)

and G_{a,b} is anti-symmetric. The proof of (2.7) depends on Zeilberger’s Crucial Lemma (Zeilberger, 1988, p. 995):

Crucial Lemma 2.1. Let G(x) be anti-symmetric with respect to the Weyl group W, let γ be any element of the root lattice Λ, and let w be any element of the Weyl group W. Then

(i)  C.T. (x^{w(γ)}G) = sgn(w)C.T. (x^{γ}G) ,

and

(ii) if γ is a bad guy (i.e. there exists a α ∈ R such that (γ, α) = 0) then
C.T. (x^{γ}G) = 0.

We let R′_{a,b} be the conjectured value of H′_{a,b} (i.e. the right side of (1.1)) and let

R_{a,b} := R′_{a,b}/W (q^{au_{s}}, q^{bu_{l}}).  (2.12)

Our goal is to prove H_{a,b} = R_{a,b} for a, b ≥ 1. The idea is to proceed by induction on a. We want to prove

\frac{H_{a+1,b}}{H_{a,b}} = \frac{R_{a+1,b}}{R_{a,b}} .  (2.13)

Once (2.13) is proved the problem of proving (1.1) for general a, b can be reduced to the smaller sub-root system R_{long}. This does not follow immediately. The problem is that we cannot plug a = 0 into (2.13) since (2.13) only makes sense for a ≥ 1. There is a way around this technical hitch.

Lemma 2.2. Suppose (2.13) is true for a, b ≥ 1 and (1.1) holds for S(R_{long}) then (1.1) holds for general a, b.

We leave the proof of Lemma 2.2 until the end of this section. We also need the following lemma which follows from (Carter, 1972, Prop. 2.3.4).

Lemma 2.3. Let α be a good guy (i.e. α does not lie on a reflecting hyperplane). Then there is a unique w in the Weyl group W and vector ρ in the fundamental chamber C such that α = w(ρ).

We now show how H_{a+1,b} can be expressed in terms of H_{a,b} and a certain finite number of “neighbouring” coefficients. Letting t = q^{a} we have

H_{a+1,b} = C.T. (x^{δ}G_{a+1,b})  (2.14)
= C.T. (x^{δ} ∏_{α∈Rshort}(1 − tx^{α})G_{a,b}) .

There are 5 steps:

Expansion Step 1. Expand x^{δ} ∏_{α∈Rshort}(1−tx^{α}) to get ∑_{ρ′∈S′} a_{ρ′}(t)x^{ρ′} for some finite subset S′ ⊂ δ + Λ.

Expansion Step 2. Discard the bad guys; i.e. all terms a_{ρ′}(t)x^{ρ′} for which ρ′ lies on a reflecting hyperplane. These terms contribute nothing to the constant term via the Crucial Lemma.

Expansion Step 3. For each good guy ρ′ find the unique w ∈ W and ρ ∈ C such that ρ′ = w(ρ). Here we have used Lemma 2.3.

Expansion Step 4. Again utilising the Crucial Lemma we replace each a_{ρ′}(t)x^{ρ′} by sgn(w)a_{ρ′}(t)x^{ρ}.

Expansion Step 5. Simplify to obtain an expression of the form

H_{a+1,b} = ∑_{ρ∈S} A_{ρ}(t)C.T. (x^{ρ}G_{a,b}) ,  (2.15)

for some finite subset S ⊂ (δ + Λ) ∩ C. Note: (1) If we let ρ_{0} := ∑_{α∈R_{short}^{+}} α then it is easily shown that we may take

S = {α ∈ (δ + Λ) ∩ C : α ≺ δ + ρ_{0}}  (2.16)

= \{δ + α : α ∈ Λ ∩ \overline{C}, α ≺ ρ_{0}\} .

(2) The polynomials A_{ρ}(t) are symmetric about t^{N}, where N = |R_{short}^{+}|. This follows easily from the fact that the function

f(t; x) := ∏_{α∈R_{short}}(1 − tx^{α})  (2.17)

satisfies

t^{2N}f(t^{−1}; x) = f(t; x).  (2.18)

One of the terms on the right side of (2.15) involves H_{a,b} since δ ∈ S and H_{a,b} = C.T. (x^{δ}G_{a,b}). The problem is to get each of the other terms in terms of H_{a,b}. For ρ ∈ (δ + Λ) ∩ C we define

H(ρ) = H_{a,b}(ρ) := C.T. (x^{ρ}G_{a,b}) ,  (2.19)

so that H(δ) = H_{a,b}. Zeilberger (1988, §§5,8) has an algorithm for generating linear equations whose unknowns are the H(ρ). The problem is to find |S| − 1 independent equations in the H(ρ) (ρ ∈ S), at least one of which involves H(δ) = H_{a,b}. For S(G_{2})^{∨} we have |S| = 4. Zeilberger solves this case by generating 3 independent equations by trial and error. In §3 we show that for S(R) case (i.e. all u_{α} = 1) a variant of his method will produce a triangular system of equations.

We describe Zeilberger’s algorithm. We let t = q^{au_{s}}, s = q^{bu_{l}}. His algorithm depends on the observation that the constant term of a Laurent polynomial G(x) is invariant under x_{i} ← q^{z_{i}}x_{i}. We remind the reader that in Zeilberger’s paper vectors are written in terms of the standard basis {e_{i}}_{i=1}^{ℓ}, so that x^{e_{i}} means x_{i}. We must first find a transformation x := (x_{1}, …, x_{ℓ}) ← q^{z}x := (q^{z_{1}}x_{1}, …, q^{z_{ℓ}}x_{ℓ}) so that

\frac{G_{a,b}(x ← q^{z}x)}{G_{a,b}(x)} = \frac{P (x, t, s, q)}{Q(x, t, s, q)},  (cf. (Zeilberger, 1988, (5.5))),  (2.20)

for some P, Q ∈ ℤ[x_{1}, …, x_{ℓ}, t, s, q]. x ← q^{z}x is the q-functional referred to in §1. We note that for the case u_{α} ≡ 1 we may take x_{1} ← qx_{1}. The transformation x_{1} ← qx_{1} is obviously related to Kadell’s (Kadell, to appear) q-derivative which was used to handle the S(BC_{n}) case.

The input of the algorithm is a vector β ∈ (δ + Λ) and the output is a homogeneous linear equation E_{β} in the H(ρ). There are 6 steps:

Equation Step 1. Cross-multiply (2.20), multiply both sides by x^{β} and then apply the functional C.T. to obtain

C.T. [x^{β}Q(x)G_{a,b}(x ← q^{z}x)] = C.T. [x^{β}P (x)G_{a,b}(x)] .  (2.21)

Equation Step 2. On the left side of (2.21) use the relation

C.T. [x^{γ}G_{a,b}(x ← q^{z}x)] = q^{−(γ,z)}C.T. [x^{γ}G_{a,b}(x)] .  (2.22)

Then bring everything to one side to obtain an equation of the form

∑_{γ′∈Ex′(β)} C.T. (a′_{γ′}(t, s, q)x^{γ′}G_{a,b}(x)) = 0,  (2.23)

for some finite subset Ex′(β) ⊂ δ + Λ.

Equation Step 3. Now use the Crucial Lemma, discarding all the bad γ′, i.e. those that are on a reflecting hyperplane.

Equation Step 4. Using Lemma 2.3, find w ∈ W, γ ∈ C, for each good guy γ′, such that γ′ = w(γ).

Equation Step 5. Again using the Crucial Lemma, replace each remaining term a′_{γ′}(t, s,

q) x^{γ′} by sgn(w)a′_{γ′}(t, s, q)x^{γ}.

Equation Step 6. Simplify to obtain an equation of the form

E_{β} : ∑_{γ∈Ex(β)} a_{γ}(t, s, q)H(γ) = 0,  (2.24)

where H(γ) is defined in (2.19), and Ex(β) is some finite subset of (δ + Λ) ∩ C. Proof of Lemma 2.2: Suppose (2.13) is true for a, b ≥ 1 and (1.1) holds for S(R_{long}). From (2.7), (2.12), (2.13) we know

\frac{H′_{a+1,b}}{H′_{a,b}} = \frac{R′_{a+1,b}}{R′_{a,b}}  (2.25)

holds for a, b ≥ 1. We would like to show that it holds for a = 0. The a = 0 case of (1.1) corresponds to the S(R_{long}) case and then the general result would follow by induction. First, we observe that the right side of (2.25) is a rational function in t, s, q where t = q^{au_{s}}, s = q^{bu_{l}}, i.e.

\frac{R′_{a+1,b}}{R′_{a,b}} = \frac{P (t, s, q)}{Q(t, s, q)},  (2.26)

for some polynomials P and Q. Let b ≥ 1 be fixed and define

K(t, q) := C.T. ∏_{α∈R_{short}^{+}} \frac{(x^{α}; q^{u_{s}})_{∞}(q^{u_{s}}x^{−α}; q^{u_{s}})_{∞}}{(tx^{α}; q^{u_{s}})_{∞}(q^{u_{s}}tx^{−α}; q^{u_{s}})_{∞}} ∏_{α∈Rlong^{+}}(x^{α}; q^{u_{l}})_{b}(q^{u_{l}}x^{−α}; q^{u_{l}})_{b},

(2.27)

so that

K(q^{au_{s}}, q) = H′_{a,b},  (2.28)

where H′_{a,b} is defined in (2.3), (2.4). An analog of K was considered by Stembridge (1988) in his proof of the S(A_{n}) case. A routine calculation shows that K(t, q) lies in the formal power series ring ℤ[t][[q]]. It follows from (2.25) and (2.28) that

Q(t, q^{bu_{l}}, q)K(tq^{u_{s}}, q) = P (t, q^{bu_{l}}, q)K(t, q)  (2.29)

for t = q^{au_{s}}, a ≥ 1. Hence (2.29) holds as an identity in ℤ[[q]][[t]] ⊃ ℤ[t][[q]] by (Stembridge, 1988, Lemma 3.2) and thus as an identity in ℤ[t][[q]]. Therefore, we may plug t = 1 in (2.29) and (2.25) holds for a = 0, as required. □

3. Triangularity Results and the S(R) Case

In this section we assume that R is an irreducible reduced root system (thus R ≠ BC_{ℓ}). We describe our variant of Zeilberger’s method that will yield the needed triangular system of equations for the S(R) case; i.e. all u_{α} ≡ 1. We also give some similar results for the q = 1 case of (1.1). Instead of writing vectors in terms of the e_{i} we write them in

terms of a base Δ = {γ_{1}, …, γ_{ℓ}} so that x^{γ_{i}} means x_{i}. Let β^{∼} denote the maximal root (Humphreys, 1972, Lemma A p. 52) of R with respect to the partial order ≺. If there are

two distinct root lengths then the maximal root β^{∼} is long (Humphreys, 1972, Lemma D p. 53). If there is one root length we consider all roots long. If there are two root lengths R also has a unique maximal short root (Humphreys, 1972, Ex. 11 p. 55) with respect

to the partial order ≺. We shall denote this root by β^{∧}. For β ∈ R^{+} we may write

β = ∑_{i=1}^{ℓ} c_{i}(β)γ_{i},  (3.1)

where c_{i}(β) ∈ ℕ. By inspection of the planches of (Bourbaki, 1968, pp. 250-275) we have the following lemma.

Lemma 3.1. Given an irreducible reduced root system R of rank ℓ, there is an integer i^{∗} = i^{∗}(R), 1 ≤ i^{∗} ≤ ℓ, that satisfies the following properties:

(i) β ∈ R^{+} ⇒ c_{i^{∗}}(β) = 0, 1, 2,

(ii) β ∈ R^{+} and c_{i^{∗}}(β) = 2 ⇒ β is the maximal root β^{∼},

(iii) c_{i^{∗}}(β^{∼}) = min_{j} c_{j}(β^{∼}).

We shall use the transformation x_{i^{∗}} ← qx_{i^{∗}}. Let S_{0} = {β ∈ R^{+} : c_{i^{∗}}(β) > 0}. By (Zeilberger, 1988, (5.3)-(5.5)) and Lemma 3.1 we find that

\frac{G_{a,b}(x_{i^{∗}} ← qx_{i^{∗}})}{G_{a,b}(x)} = \{ \begin{matrix}q^{−δ_{i^{∗}}} ∏_{α∈S_{0}} \frac{(1 − p(α)x^{α})}{(\frac{p(α)}{q} − x^{α})}, & if c_{i^{∗}}(β^{∼}) = 1, \\ q^{−δ_{i^{∗}}} \frac{(1 − sqx^{β^{∼}})}{(\frac{s}{q} − qx^{β^{∼}})} ∏_{α∈S_{0}} \frac{(1 − p(α)x^{α})}{(\frac{p(α)}{q} − x^{α})}, & if c_{i^{∗}}(β^{∼}) = 2, \end{matrix}  (3.2)

where δ_{i^{∗}} = c_{i^{∗}}(δ), and

p(α) = \{ \begin{matrix}t, & α short, \\ s, & α long. \end{matrix}  (3.3)

We will show that if we start with equation (3.2) and apply Zeilberger’s algorithm (Equation Steps 1–6) with β ∈ −S \ {−δ} the output will be an equation involving H(−β) and the other H(ρ) that are involved satisfy ρ ∈ S and ρ ≺ −β. Before we can prove this result we need another technical lemma.

Lemma 3.2. Let R be an irreducible reduced root system. Then for α ∈ \overline{C} ∩ Λ \ \{0\} we

have ⟨α, β⟩ ≥ 1 for β =β^{∼}, β^{∧} (the maximal root and the maximal short root).

If, in addition, α ≠β^{∧} then we have c_{i^{∗}}(α) ≥ c_{i^{∗}}(β^{∼}), where i^{∗} is defined as in Lemma 3.1.

Proof. Suppose α ∈ \overline{C} ∩ Λ \ \{0\}. Then (α, γ) ≥ 0 for all γ ∈ Δ (base). Since α ∈ \overline{C} we have α ≻ 0 (Bourbaki, 1968, p. 156, Lemma 6 p. 79). It follows that there is a

γ_{0} ∈ Δ such that (α, γ_{0}) > 0 since α ≠ 0. Now β^{∼} ≻ γ_{0} since β^{∼} is maximal and we have

(α, β^{∼}) ≥ (α, γ_{0}) > 0. It follows that ⟨α, β^{∼}⟩ ≥ 1 since ⟨α, β^{∼}⟩ ∈ ℤ. Similarly, it can be

shown that ⟨α, β^{∧}⟩ ≥ 1 by working in the dual R^{∨} and proceeding as in (Humphreys, 1972, Ex. 11 p. 55).

Now suppose, in addition, that α ≠β^{∧}. We want to show that

c_{i^{∗}}(α) ≥ c_{i^{∗}}(β^{∼}).  (3.4)

The idea is to use the tables (Bourbaki, 1968, pp. 250-275) for the fundamental weights (Humphreys, 1972, p. 67), treating each root system separately. Let ϖ_{1}, ϖ_{2}, …, ϖ_{ℓ} denote the fundamental weights as listed in (Bourbaki, 1968). Suppose α = ∑_{i=1}^{ℓ} k_{i}ϖ_{i} ∈

\overline{C} ∩ Λ \ \{0, β^{∧}\} then the k_{i} = ⟨α, ϖ_{i}⟩ ∈ ℕ (Humphreys, 1972, p. 67). There are 3 cases:

Case 1. R = A_{ℓ}, B_{ℓ}, C_{ℓ}, D_{ℓ}, E_{6}, E_{7} or E_{8}. We observe that for each of these root systems we have c_{i^{∗}}(ϖ_{j}) ≥ c_{i^{∗}}(β^{∼}) for all j. Now,

c_{i^{∗}}(α) = ∑_{j=1}^{ℓ} k_{j}c_{i^{∗}}(ϖ_{j})  (3.5)

≥ c_{i^{∗}}(β^{∼}) (∑_{j=1}^{ℓ} k_{j}) ≥ c_{i^{∗}}(β^{∼})

since α ≠ 0.

Case 2. R = F_{4}. In this case we have

ϖ_{1} =β^{∼}, ϖ_{4} =β^{∧}, ϖ_{2}, ϖ_{3} ≻β^{∼}, 2ϖ_{4} ≻ ϖ_{1},  (3.6)

and

c_{i^{∗}}(β^{∼}) = 2,  c_{i^{∗}}(β^{∧}) = 1,  (i^{∗} = 1).  (3.7)

If α ≠ 0, β^{∧} then k_{4} ≥ 2 or at least one of k_{1}, k_{2}, k_{3} > 0. In both cases α ≻β^{∼} so that

c_{i^{∗}}(α) ≥ c_{i^{∗}}(β^{∼}).

Case 3. R = G_{2}. In this case we have

ϖ_{1} =β^{∧}, ϖ_{2} =β^{∼}, 2ϖ_{1} ≻ ϖ_{2},  (3.8)

and

c_{i^{∗}}(β^{∼}) = 2,  c_{i^{∗}}(β^{∧}) = 1,  (i^{∗} = 2).  (3.9)

If α ≠ 0, β^{∧} then k_{1} ≥ 2 or k_{2} ≠ 0. In both cases α ≻β^{∼} so that c_{i^{∗}}(α) ≥ c_{i^{∗}}(β^{∼}). □

Let P and Q be the numerator and denominator of the right side of (3.3). We have

Theorem 3.3. Let β = −α − δ where α ∈ Λ ∩ \overline{C} and α ≠ 0. Then the equation

C.T. [x^{β}Q(x)G_{a,b}(x_{i^{∗}} ← qx_{i^{∗}})] = C.T. [x^{β}P (x)G_{a,b}(x)]  (3.10)

can be written as

E_{β} : ∑_{\begin{matrix}ρ≺α \\ ρ∈Λ∩\overline{C} \end{matrix}} p_{α,ρ}(t, s, q)H(ρ + δ) = 0,  (3.11)

where the p_{α,ρ}(t, s, q) = p_{α,ρ}(q^{a}, q^{b}, q) are certain polynomials in q and p_{α,α} ≢ 0.

Proof. We prove the result for the hard case c_{i^{∗}}(β^{∼}) = 2 leaving the details of the case

c_{i^{∗}}(β^{∼}) = 1 to the reader. We let

S_{1} = {β ∈ R_{short}^{+} : c_{i^{∗}}(β) > 0}  (3.12)

and

S_{2} = {β ∈ R_{long}^{+} : c_{i^{∗}}(β) > 0} ∪ {β^{∗}} ,  (3.13)

where β^{∗} is a copy of β^{∼} so that S_{2} is a multiset.

The right side of (3.10) is

C.T. x^{β}(1 − sqx^{β^{∗}}) ∏_{α∈S_{0}}(1 − p(α)x^{α}) G_{a,b}(x)  (3.14)

(where p(α) is defined in (3.3))

= C.T. ∑_{\begin{matrix}B⊂S_{1} \\ C⊂S_{2} \end{matrix}}(−1)^{|B|+|C|}t^{|B|}s^{|C|}q^{χ^{∗}(C)}x^{sum(B)+sum(C)+β} G_{a,b}(x),

where

χ^{∗}(C) = \{ \begin{matrix}1, & β^{∗} ∈ C, \\ 0, & β^{∗} ∉ C. \end{matrix}  (3.15)

Here sum(B) means the sum of all the elements of B. The left side of (3.10) is

C.T. q^{δ_{i^{∗}}} x^{β}(\frac{s}{q} − qx^{β^{∗}}) ∏_{α∈S_{0}}(\frac{p(α)}{q} − x^{α}) G_{a,b}(x_{i^{∗}} ← qx_{i^{∗}})  (3.16)
= C.T. q^{δ_{i^{∗}} −|S_{0}|−1}(s − q^{2}x^{β^{∗}}) ∏_{α∈S_{0}}(p(α) − qx^{α}) G_{a,b}(x_{i^{∗}} ← qx_{i^{∗}})
= C.T. q^{δ_{i^{∗}} −|S_{0}|−1} ∑_{\begin{matrix}B⊂S_{1} \\ C⊂S_{2} \end{matrix}}(−1)^{|B|+|C|}t^{|S_{1}|−|B|}s^{|S_{2}|−|C|}q^{|B|+|C|+χ^{∗}(C)}
·x^{sum(B)+sum(C)+β} G_{a,b}(x_{i^{∗}} ← qx_{i^{∗}})
= C.T. q^{δ_{i^{∗}} −|S_{0}|−1} ∑_{\begin{matrix}B⊂S_{1} \\ C⊂S_{2} \end{matrix}}(−1)^{|B|+|C|}t^{|S_{1}|−|B|}s^{|S_{2}|−|C|}q^{−β_{i^{∗}} −χ^{∼}(C)}
·x^{sum(B)+sum(C)+β} G_{a,b}(x),

by the obvious analogue of (2.22). Here χ^{∼} is given by

χ^{∼} (C) = \{ \begin{matrix}1, & β^{∼}∈ C, \\ 0, & β^{∼}∉ C \end{matrix} ,  (3.17)

and β_{i^{∗}} = c_{i^{∗}}(β). Hence bringing everything to one side and applying the transformation γ ↦ −γ (γ ∈ E) we find (3.10) is equivalent to

C.T. ∑_{\begin{matrix}B⊂S_{1} \\ C⊂S_{2} \end{matrix}}(−1)^{|B|+|C|} \{t^{|B|}s^{|C|}q^{χ^{∗}(C)} − t^{|S_{1}|−|B|}s^{|S_{2}|−|C|}q^{α_{i^{∗}} −χ^{∼}(C)}\} (3.18)
·x^{δ−sum(B)−sum(C)+α} G_{a,b}(x)
= 0,  (c.f. (2.21)).

We have used the fact that 2δ_{i^{∗}} = |S_{0}| + 1 and β = −α − δ. We have thus completed Equation Steps 1–2 of Zeilberger’s algorithm. We must show that after applying Equation Steps 3–6 we obtain an equation as given in (3.11). Let B ⊂ S_{1} and C ⊂ S_{2} then

δ − sum(B) − sum(C) + α = (α − m β^{∼}) + (δ − sum(B′)),  (3.19)

where m = 0 or 1 and B′ is some set (no repeated elements), B′ ⊂ S_{0} ⊂ R^{+}. Tossing

out the bad guys (Equation Step 3) we assume (α − m β^{∼}) + (δ − sum(B′)) is a good guy. Let w be that element of the Weyl group W such that

γ := w(α − m β^{∼}) + w(δ − sum(B′)) ∈ C,  (Step 4).  (3.20)

We now show that the vector γ given in (3.20) satisfies γ ≺ α + δ. This will mean that the only unknowns H(ρ + δ) appearing in the equation E_{β} (after Equation Steps 5–6) satisfy ρ ≺ α. Now

w(δ − sum(B′))  (3.21)
= δ − sum(B′′)  (for some B′′ ⊂ R^{+})
≺ δ.

Hence we need to show that

w(α − m β^{∼}) ≺ α,  (3.22)

for m = 0 or 1. There are two cases:

Case 1. w(β^{∼}) ≻ 0. We have

w(α − m β^{∼}) = w(α) − mw(β^{∼})  (3.23)
≺ w(α)
≺ α  (by (Bourbaki, 1968, Prop. 18 p. 158) since α ∈ \overline{C}).

Case 2. w(β^{∼}) ≺ 0. Since α ∈ \overline{C} ∩ Λ \ \{0\} we have

w(α − m β^{∼}) = w(α) − mw(β^{∼})  (3.24)
≺ w(α) − ⟨α, β^{∼}⟩w(β^{∼})  (by Lemma 3.2)
= ww_{β^{∼}}(α)
≺ α  (again by(Bourbaki, 1968, Prop. 18 p. 158)).

Equation (3.22) holds in both cases. Combining this with (3.21) we have γ ≺ α + δ, as required.

Finally, we must show that the coefficient of H(α + δ) in the equation E_{β} is non-zero.

Recall that we have assumed that c_{i^{∗}}(β^{∼}) = 2. Here the possibilities are R = E_{8}, F_{4} or G_{2}. There are two cases:

Case 1. α ≠β^{∧}. From Lemma 3.2 we have

α_{i^{∗}} = c_{i^{∗}}(α) ≥ 2.  (3.25)

By considering the term that corresponds to B = C = ϕ (the empty set) in the sum in (3.18) we find that the degree in q of the coefficient of H(α+δ) in E_{β} is a|S_{1}|+b|S_{2}|+α_{i^{∗}}. Hence the coefficient of H(α + δ) is non-zero.

Case 2. α =β^{∧}. Since E_{8} has only one root length we have only to check the result for F_{4} and G_{2}. We have verified the result in these two sub-cases by means of a machine computation. □

It is now clear what our triangular system is. We choose a linear extension ≤_{L} of the partial order ≺. We list the elements of S defined in (2.16):

α_{1} := δ + ρ_{0} ≥_{L} … ≥_{L} α_{|S|} := δ.  (3.26)

Let

h := ( H(α_{1}) ; ⋮ ; H(α_{|S|}) ) ,  (3.27)

and define the matrix

P := (p_{α_{i},α_{j}})_{1≤i≤|S|−1, 1≤j≤|S|−1} ,  (3.28)

where p_{α_{i},α_{j}} is the coefficient of H(α_{j} + δ) in the equation E_{−α_{i}−δ} (see (3.11)). Our system of equations is given by

P h = 0,  (3.29)

and P looks like

( \begin{matrix}p_{α_{1},α_{1}} & ⋯ & ⋯ & ⋯ & p_{α_{1},α_{|S|}} \\ 0 & ... & & & ⋮ \\ ⋮ & & ... & & ⋮ \\ 0 & ⋯ & 0 & p_{α_{|S|−1},α_{|S|−1}} & p_{α_{|S|−1},α_{|S|}} \end{matrix} ) ,  (3.30)

where each of the polynomials p_{α_{1},α_{1}}, …, p_{α_{|S|−1},α_{|S|−1}} on the main diagonal is ≢ 0. Hence P has full rank and each of the H(α_{i}) can be gotten in terms of H(α_{|S|}) = H(δ).

Recently, one of us (Garvan, 1990) found a computer proof of the q = 1 case of (1.1) for the root system F_{4}. Here the transformation x_{1} ← qx_{1} is not of much use. Instead, the fact that the derivatives of Laurent polynomial have no residues, was used. Corollary 3.5, below, contains an analog of Theorem 3.3 for this case. Let

M_{a,b}(x) := ∏_{α∈R}(1 − x^{α})^{k_{α}},  (3.31)

so that C.T. M_{a,b}(x) is the left side of (1.1) when q = 1. Let 1 ≤ i ≤ ℓ and α ∈ \overline{C} ∩ Λ. Then

0 = C.T. x_{i} \frac{∂}{∂x_{i}} x^{α}M_{a,b}(x)  (3.32)

= C.T. (c_{i}(α)x^{α}M_{a,b}(x) − ∑_{β∈R^{+}} k_{β}c_{i}(β)\frac{(1 + x^{β})}{(1 − x^{β})}x^{α}M_{a,b}(x)) ,

(c.f. (Garvan, 1990, (4.2)).

We shall find that each term on the right side of (3.32) can be gotten in terms of C.T. x^{ρ} M_{a,b}(x) where ρ ∈ \overline{C} ∩ Λ and ρ ≺ α. There are two problems with trying to proceed as in the proof of Theorem 3.3:

(i) We can’t use the Crucial Lemma since M is not anti-symmetric! (ii) How do we get rid of the denominator (1 − x^{β})?

In answer to (i) we note that M is symmetric with respect to the Weyl group W, so instead we may use

C.T. x^{w(α)}M_{a,b}(x) = C.T. x^{α}M_{a,b}(x),  for all w ∈ W .  (3.33)

This time there are no bad guys to kill off. In answer to (ii) we use an observation due to Kevin Kadell:

\frac{x^{α}}{1 − x^{β}} + w_{β} (\frac{x^{α}}{1 − x^{β}} ) ∈ ℤ[x_{1}^{±1}, …, x_{ℓ}^{±1}],  for β ∈ Δ.  (3.34)

Theorem 3.4. Let α ∈ \overline{C} ∩ Λ, β ∈ R^{+} and suppose k_{β} ≥ 1. Then there exist c_{α,ρ} ∈ ℕ such that

C.T. \frac{(1 + x^{β})}{(1 − x^{β})}x^{α}M_{a,b}(x)  (3.35)

= \{ \begin{matrix}−C.T. (x^{α}M_{a,b}(x) + ∑_{\begin{matrix}ρ≺α \\ ≠ \\ ρ∈\overline{C}∩Λ \end{matrix}}c_{α,ρ}x^{ρ}M_{a,b}(x)), & if (α, β) > 0, \\ 0, & if (α, β) = 0. \end{matrix}

Proof. There is a w ∈ W such that w(β) ∈ Δ = {γ_{1}, …, γ_{ℓ}}. Without loss of generality we may suppose that w(β) = γ_{1}. We note that under w_{γ_{1}} the only coefficient of the γ_{j} in w(α) that changes is the coefficient of γ_{1} which is given by

c_{1}(w_{γ_{1}}w(α)) = c_{1}(w(α)) − ⟨w(α), w(β)⟩  (3.36)
= c_{1}(w(α)) − ⟨α, β⟩.

We note that ⟨α, β⟩ ≥ 0 since α ∈ \overline{C} and β ∈ R^{+}. Recall that x^{γ_{j}} = x_{j} (1 ≤ j ≤ ℓ). We have

C.T. \frac{(1 + x^{β})}{(1 − x^{β})}x^{α}M_{a,b}(x) = C.T. \frac{(1 + x_{1})}{(1 − x_{1})}x^{w(α)}M_{a,b}(x),  (by (3.33)). (3.37)

As remarked above, we may use the reflection w_{γ_{1}} to kill the denominator (1 − x_{1}). This observation is due to Kevin Kadell, who used a special case of it in his proof of the BC_{n} case (Kadell, to appear). We have

C.T. \frac{(1 + x^{β})}{(1 − x^{β})}x^{α}M_{a,b}(x)  (3.38)
= \frac{1}{2}C.T. \{[\frac{(1 + x_{1})}{(1 − x_{1})}x^{w(α)} + w_{γ_{1}} (\frac{(1 + x_{1})}{(1 − x_{1})}x^{w(α)})] M_{a,b}(x)\}  (by (3.33))

= −\frac{1}{2}C.T. \{(\frac{(1 + x_{1})}{(1 − x_{1})}) x_{1}^{c_{1}(w(α))−⟨α,β⟩}(1 − x_{1}^{⟨α,β⟩}) ∏_{j=2}^{ℓ} x_{j}^{c_{j}(w(α))}M_{a,b}(x)\}

(by (3.36))

= \{ \begin{matrix}−C.T. ∑_{m=0}^{⟨α,β⟩−1} x^{w(α)−mγ_{1}}M_{a,b}(x), & if (α, β) > 0, \\ 0, & if (α, β) = 0. \end{matrix}

If (α, β) > 0 then for each 0 ≤ m ≤ (⟨α, β⟩ − 1) we choose w′ ∈ W such that

w′(w(α) − mγ_{1})) = w′w(α − mβ) ∈ \overline{C}.  (3.39)

By using an argument analogous to that used in proving (3.22) (in the proof of Theorem 3.3) we have

w′w(α − mβ) ≺ α.  (3.40)

In fact for 0 < m ≤ (⟨α, β⟩ − 1) we can show that

w′w(α − mβ) ⪵ α.  (3.41)

Equation (3.35) follows easily. □

From (3.32) and Theorem 3.4 we have

Corollary 3.5. Let α ∈ \overline{C} ∩ Λ, 1 ≤ i ≤ ℓ. Then there exist a_{α,ρ,i}, b_{α,ρ,i} ∈ ℕ such that

\{a ( ∑_{\begin{matrix}β∈R_{short}^{+} \\ (α,β)>0 \end{matrix}} c_{i}(β)) + b ( ∑_{\begin{matrix}β∈R_{long}^{+} \\ (α,β)>0 \end{matrix}} c_{i}(β)) + c_{i}(α)\} C.T. x^{α}M_{a,b}(x) (3.42)

+ C.T. ∑_{\begin{matrix}ρ⪵α \\ ρ∈Λ∩\overline{C} \end{matrix}} (a_{α,ρ,i}a + b_{α,ρ,i}b) x^{ρ}M_{a,b}(x)

= 0.

Remark (1) For each α ∈ \overline{C} ∩ Λ \ \{0\} and 1 ≤ i ≤ ℓ it can be shown that c_{i} > 0 so that C.T. x^{α}M_{a,b}(x) can be gotten in terms of C.T. x^{ρ}M_{a,b}(x) for ρ ⪵ α. Thus, it is possible to produce a triangular system of equations to be used in verifying (1.1) in the q = 1 case.

(2) Equation (3.42) has some nicer features than (3.11). Firstly, (3.11) depends on the special transformation x_{i^{∗}} ← qx_{i^{∗}} but (3.42) comes from \frac{∂}{∂x_{i}} where 1 ≤ i ≤ ℓ, not necessarily i = i^{∗}. Secondly, the coefficient of C.T. x^{α}M_{a,b}(x) is explicitly given in (3.42). All we know about the coefficient p_{α,α} in (3.12) is that it is non-zero. There may be something going on here. For R = F_{4} we have found that p_{α,α} seems to factor nicely. A list of some factorisations is given in Table IV.

4. Implementing the S(F_{4}) Case

Let {e_{1}, e_{2}, e_{3}, e_{4}} be the standard basis of ℝ^{4}. We follow (Garvan, 1990, §2) in the choice of representation of the roots of F_{4}, Weyl group, fundamental chamber, etc. We may take the set of vectors:

\begin{matrix}±2e_{i} (1 ≤ i ≤ 4), ±e_{i} ± e_{j} (1 ≤ i < j ≤ 4), \\ (±e_{1} ± e_{2} ± e_{3} ± e_{4}), \end{matrix}  (4.1)

as our set of roots for F_{4}. See (Bourbaki, 1968, p. 273 eqn. (V)). This set is usually known as F_{4}^{∨} but it can be shown that F_{4} (as in (Bourbaki, 1968, p. 272 eqn. (I))) and F_{4}^{∨} are isomorphic as root systems. The advantage of this set is that all components are integers.

We shall prove the S(F_{4}) case of (1.1):

Theorem 4.1. Let a, b ∈ ℕ. Then the constant term of

F′_{a,b}(x_{1}, x_{2}, x_{3}, x_{4})  (4.2)

:= ∏_{1≤i<j≤4}(x_{i}x_{j})_{a}(qx_{i}^{−1}x_{j}^{−1})_{a}(x_{i}x_{j}^{−1})_{a}(qx_{i}^{−1}x_{j})_{a}

· ∏_{1≤i≤4}(x_{i}^{2})_{b}(qx_{i}^{2})_{b} · ∏_{r_{2},r_{3},r_{4}=±1}(x_{1}x_{2}^{r_{2}}x_{3}^{r_{3}}x_{4}^{r_{4}})_{b}(qx_{1}^{−1}x_{2}^{−r_{2}}x_{3}^{−r_{3}}x_{4}^{−r_{4}})_{b}

is equal to

R′_{a,b} = \frac{(q)_{6a+6b}(q)_{4a+4b}(q)_{2a+6b}(q)_{4a+2b}(q)_{2a+4b}(q)_{4b}(q)_{3a}}{(q)_{5a+6b}(q)_{3a+5b}(q)_{3a+4b}(q)_{3a+3b}(q)_{2a+3b}(q)_{a+3b}(q)_{2a+b}}  (4.3)

·\frac{(q)_{3b}(q)_{2a}(q)_{2b}}{(q)_{a+2b}(q)_{a+b}(q)_{a}^{2}(q)_{b}^{3}} .

We now describe the Weyl group of F_{4}. Since C_{4} ⊂ F_{4} then H := W (C_{4}) < W (F_{4}). H is the group of signed permutations that act on the coordinates e_{1}, e_{2}, e_{3}, e_{4}. By considering left cosets every element w ∈ W (F_{4}) can be written

w = (τσ)^{k}h  (k = 0, 1, 2)  (4.4)

for some h ∈ H, where τ = w_{2e_{4}} and σ = w_{e_{1}−e_{2}−e_{3}−e_{4}}. See (Garvan, 1990, Lemma 2.11).

We take

γ_{1} := −e_{1} + e_{2} + e_{3} + e_{4}, γ_{2} := e_{1} − e_{2} − e_{3} + e_{4}, γ_{3} := e_{3} − e_{4}, γ_{4} := −e_{3} + e_{2}, (4.5)

as a base. See (Garvan, 1990, (2.16)). The corresponding fundamental chamber is

C = {(x_{1}, x_{2}, x_{3}, x_{4}) ∈ ℝ^{4} : x_{1} > x_{2} > x_{3} > x_{4} > 0,  (4.6)
x_{2} + x_{3} + x_{4} > x_{1}, x_{1} + x_{4} > x_{2} + x_{3}}.

The set of positive roots and their coordinates with respect to the Δ = {γ_{1}, γ_{2}, γ_{3}, γ_{4}} is given in Table I, in the Appendix. The root lattice is given by

Λ = {(x_{1}, x_{2}, x_{3}, x_{4}) ∈ ℤ^{4} : x_{1} + x_{2} + x_{3} + x_{4} ≡ 0 (mod 2)}.  (4.7)

Half the sum of the positive roots is

δ := (7, 4, 3, 2) = 8γ_{1} + 15γ_{2} + 21γ_{3} + 11γ_{4},  (4.8)

so that in this case δ + Λ = Λ. The bad guys are those elements (x_{1}, x_{2}, x_{3}, x_{4}) of Λ in which one component is zero or two components are equal or sum of two components is zero or r_{1}x_{1} + r_{2}x_{2} + r_{3}x_{3} + r_{4}x_{4} = 0 for some r_{i} = ±1, i = 1, 2, 3, 4.

From (Macdonald, 1972, p. 168) W (t, s) of (2.8) is given by

W (t_{1}, t_{2}) = ∏_{j=1}^{2}(1 + t_{j})(1 + t_{j} + t_{j}^{2})(1 + ut_{j}) ∏_{i=1}^{3}(1 + u^{i}),  (4.9)

where u = t_{1}t_{2}.

We let ≺ be the usual root order; i.e. α ≺ β for α, β ∈ Λ iff α − β = ∑_{i=1}^{4} c_{i}γ_{i} and all the c_{i} ≥ 0. We describe a nice linear extension of ≺ suggested by Dennis Stanton. The elements of \overline{C}∩Λ are partitions of even integers into at most four parts. For π_{1}, π_{2} ∈ \overline{C}∩Λ we define π_{1} ≤_{L} π_{2} iff the sum of parts of π_{1} is less than or equal to the sum of parts of π_{2} and if the sum of parts are equal then we require π_{1} to be “smaller” than π_{2} lexicographically. It is an easy exercise to show that ≤_{L} is a linear extension of ≺. The sum of the positive short roots is given by

ρ_{0} = (6, 4, 2, 0) = 6γ_{1} + 12γ_{2} + 18γ_{3} + 10γ_{4}.  (4.10)

There are 37 elements of S defined in (2.16):

S = {δ + v(i)}_{i=1}^{37},  (4.11)

where v(i) ≺ ρ_{0} and v(i) ∈ \overline{C} ∩ Λ. The 37 vectors v(i) are listed in Table II in order according to ≤_{L}. Let

F_{a,b}(x_{1}, x_{2}, x_{3}, x_{4}) :=  ∏_{1≤i<j≤4}(x_{i}x_{j})_{a}(qx_{i}^{−1}x_{j}^{−1})_{a−1}(x_{i}x_{j}^{−1})_{a}(qx_{i}^{−1}x_{j})_{a−1} (4.12)

· ∏_{r_{2},r_{3},r_{4}=±1}(x_{1}x_{2}^{r_{2}}x_{3}^{r_{3}}x_{4}^{r_{4}})_{b}(qx_{1}^{−1}x_{2}^{−r_{2}}x_{3}^{−r_{3}}x_{4}^{−r_{4}})_{b−1}

· ∏_{1≤i≤4}(x_{i}^{2})_{b}(qx_{i}^{2})_{b−1}

and

H_{a,b} = C.T. F_{a,b}.  (4.13)

We know H_{a,b} = H′_{a,b}/W (q^{a}, q^{b}). So if we let

R_{a,b} := R′_{a,b}/W (q^{a}, q^{b}),  (4.14)

then we must show that H_{a,b} = R_{a,b}. We proceed by induction on a; i.e. we want to show that

\frac{H_{a+1,b}}{H_{a,b}} = \frac{R_{a+1,b}}{R_{a,b}} .  (4.15)

This will be enough in view of Lemma 2.2 since the long roots of F_{4} are isomorphic to D_{4} and (1.1) is known for S(D_{n}) by Kadell (to appear).

A routine calculation gives (t = q^{a}, s = q^{b})

R_{a+1,b}/R_{a,b} = (1 − t^{2}q)(1 − t^{3}q^{2})(1 − t^{3}q)(1 − t^{2}s^{4}q)(1 − t^{4}s^{2}q^{3})  (4.16)
(1 + t^{2}sq)(1 − t^{4}s^{2}q)(1 + ts^{3}q)(1 − t^{2}s^{6}q)(1 − t^{4}s^{4}q^{3})
(1 + t^{2}s^{2}q)(1 − t^{4}s^{4}q)(1 − t^{6}s^{6}q^{5})(1 + t^{3}s^{3}q^{2})
(1 + t^{2}s^{2}q + t^{4}s^{4}q^{2})(1 − t^{2}s^{2}q)^{2}(1 + t^{3}s^{3}q)(1 − t^{6}s^{6}q)
(1 + t)(1 + t + t^{2})(1 + t^{2}s)(1 + ts^{2})(1 + ts)^{2}(1 + t^{2}s^{2})

(1 − ts + t^{2}s^{2})
/((1 − t^{2}s^{3}q^{2})(1 − t^{2}s^{3}q)(1 − t^{3}s^{4}q^{3})(1 − t^{3}s^{4}q^{2})
(1 − t^{3}s^{4}q)(1 − t^{3}s^{5}q^{3})(1 − t^{3}s^{5}q^{2})(1 − t^{3}s^{5}q)
(1 − t^{5}s^{6}q)(1 − t^{5}s^{6}q^{2})(1 − t^{5}s^{6}q^{3})(1 − t^{5}s^{6}q^{4})
(1 − t^{5}s^{6}q^{5})).

We have written a FORTRAN program to carry Expansion Steps 1–5 as in §2 for the case R = F_{4}. After running this program we find

H_{a+1,b} = ∑_{i=1}^{37} y[i] H(δ + v(i)),  (c.f. (2.15))  (4.17)

where H(ρ) = C.T. (x^{ρ}G_{a,b}), the v(i) are given in Table II, and the y[i] ∈ ℤ[t] are given in Table III.

Next we generate equations via Zeilberger’s Equation Steps 1–6 modified as in the proof of Theorem 3.3. For F_{4} we may take i^{∗} = 1. Recall that i^{∗} must satisfy the properties given in Lemma 3.1. S_{1}, S_{2} of (3.12), (3.13) are

S_{1} = {(0, 0, 1, 1), (0, 1, 0, 1), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (1, 1, 0, 0)},  (4.18)
S_{2} = {(1, −1, 1, 1), (0, 0, 2, 0), (−1, 1, 1, 1), (0, 0, 0, 2), (1, 1, −1, 1), (0, 2, 0, 0), (4.19)
(2, 0, 0, 0), (1, 1, 1, −1), (1, 1, 1, 1), (1, 1, 1, 1)^{∗}}.

Here β^{∼}= (1, 1, 1, 1) is the maximal (w.r.t. ≺) root and β^{∗} = (1, 1, 1, 1)^{∗} is a copy of (1, 1, 1, 1) so that S_{2} is a multiset. For C ⊂ S_{2} we define

χ^{∗}(C) = \{ \begin{matrix}1, & (1, 1, 1, 1)^{∗} ∈ C, \\ 0, & otherwise, \end{matrix}  (4.20)

and

χ^{∼} (C) = \{ \begin{matrix}1, & (1, 1, 1, 1) ∈ C, \\ 0, & otherwise. \end{matrix}  (4.21)

For 1 ≤ i ≤ 37 we define

un[i] := C.T. (x^{δ+v(i)}G_{a,b})/H_{a,b}  (4.22)
≡ H(δ + v(i))/H_{a,b},

so that un[1] ≡ 1 (by definition). Let c_{i} be the coefficient of γ_{1} when v(i) is written in terms of the γ_{j}. By taking α = v(i) in (3.18) we have

C.T. ∑_{\begin{matrix}B⊂S_{1} \\ C⊂S_{2} \end{matrix}}(−1)^{|B|+|C|}\{t^{|B|}s^{|C|}q^{χ^{∗}(C)} − t^{|S_{1}|−|B|}s^{|S_{2}|−|C|}q^{c_{i}−χ^{∼}(C)}\} (4.23)
·x^{δ−sum(B)−sum(C)+v(i)}G_{a,b}
= 0.

We note that (3.18) and hence (4.23) were obtained by applying Zeilberger’s Equation Steps 1-2 with x_{1} ← qx_{1} and where x_{i} means x^{γ_{i}}.

We have written a FORTRAN program whose input is an integer i, 2 ≤ i ≤ 37, and whose output is a linear equation of the form

un[i] = \frac{−1}{p_{i,i}} (∑_{j=1}^{i−1} p_{i,j}un[j]),  (4.24)

where the p_{i,j} ∈ ℤ[t, s, q] (t = q^{a}, s = q^{b}) and p_{i,i} ≢ 0. This program starts with equation (4.23) and incorporates Equation Steps 3-6 of Zeilberger’s algorithm. The form of (4.24) is guaranteed by Theorem 3.3. The output was written to a file in MAPLE code so that it could be used in MAPLE later. For 2 ≤ i ≤ 37 this program took about 5\frac{1}{2} hours to run on an Apollo. The file containing all the equations is about 747 kilobytes.

An interesting observation is that the polynomials p_{i,i} seem to factor very nicely. We list these factorisations in Table IV. The idea is to feed into MAPLE the equation un[1] = 1 together with our 36 equations for the un[i]. The values of the un[i] would be computed automatically by back substitution. Once this was done we would compute

R_{a+1,b}/R_{a,b} − ∑_{i=1}^{37} y[i]un[i].  (4.25)

If the value returned is 0 then by (4.17) we would have verified (4.15), as required.

Unfortunately, when we first tried this back in March 1988, MAPLE runs out of memory when trying to compute un[12]. At this point Maple failed because one of the polynomials it tried to represent while doing the computation had more than 2^{16} terms. We developed an interpolation approach to get around this problem. The details are given in the next section. However, much later using the latest version of MAPLE, version V, we were able to compute all the un[i] and (4.25) which happily returned zero thus proving the S(F_{4}) case. This was done on Wednesday November 14 16:32:08 MET 1990. Unfortunately, the S(F_{4})^{∨} case could not be done the same way. The S(F_{4})^{∨} case was proved using the interpolation approach.

5. Symbolic Computations

The main step of the computation is given by (4.24). In that step, we need to expand a sum of product of polynomials under a common denominator and then remove the gcd (greatest common divisor) between the numerator and denominator. Both the expansion and the gcd computations are steps which are likely to fail to compute. The expansion may produce polynomials which are too large to be represented. The gcd computation takes O(n^{3}) time, where n is the number of terms in a dense representation of the polynomials. Hence the gcd computation may be a step which makes the whole computation not feasible (not only in cost, but in waiting time).

The following paradox is apparent: Assuming that the present rate of improvement in computers, (a speed increase of a factor of 10 every 10 years) will continue, it is better to wait that to start computing.

The first question we asked was: is the gcd computation for each i necessary? The answer is yes by examples (actually for all values of i, (4.24) allowed some non-trivial gcd simplification). For example for i = 4 the factor (1 + s + s^{2})(t^{3}s^{4}q + 1) was cancelled, and for i = 24, (1 + s + s^{2})(t^{6}s^{8}q^{5} − 1) was cancelled.

We are able to predict precisely which factors can be eliminated in this gcd simplification. Let nun[i], resp. dun[i] denote the numerator, resp. denominator of un[i] before simplification. Then it seems that

gcd(nun[i], dun[i]) = \frac{p_{i,i}}{gcd(p_{i,i}, denom(R_{a+1,b}/R_{a,b}))}.  (5.1)

In other words, the gcd comes from those factors of p_{i,i} that do not occur in the denominator of R_{a+1,b}/R_{a,b}. However, we are unable to prove (5.1) and we can’t completely avoid this computation.

Can the un[i] be factored? (This could help controlling the size of the computation, as in general, a factored form is much smaller than an expanded form.) Although many un[i] factor, not all of them do, and furthermore there are very few, if any, common factors.

The first positive step towards a solution came from the simple observation that the un[i] form some natural classes, having each member of the class similar denominators. The classes were: {1, 2}, {3, 4}, {5, …, 8}, {9, 10, 11}, {12, …, 24}, {26, …, 31, 33, 34, 35} and {25, 32, 36, 37}. To take advantage of this classification we can perform the summation in (4.24) in two steps. First add terms within the classes, simplify (gcd elimination) and then add the results together.

The second positive step was to perform all additions of rational expressions of polynomials, one term at at time, i.e.

(((a + b) + c) + d) + e + …

and eliminate gcds after each individual addition. With these observations, the computation could be carried up to i = 24 inclusive; a significant improvement but unfortunately not enough.

As a by product of this exercise we learned a better technique to compute gcds. Let a(X) and b(X) be multivariate polynomials over ℤ[X]. There are various algorithms for computing gcds (see (Char et. al., 1984), (Knuth, 1981), (Wang, 1980) and (Zippel, 1979)) which are based directly or indirectly on Euclid’s algorithm. Of course, if a(X) and b(X) are fully factored, it is trivial to find the gcd, we simply make all factors primitive (with no integer divisors) and scan for matching (or complement-matching) terms. Factoring is, in general, much harder and time consuming than computing gcds.

But for this problem, we typically have one of the polynomials, (the one corresponding to the denominator) almost factored. The improved gcd algorithm is applicable when one of the polynomials is completely factored (or it is significantly smaller, so that factoring is insignificant compared to the gcd computation) and consists of trial synthetic divisions of the factors of one polynomial against the other.

Consequently, by keeping the denominators of un[i] factored we could significantly reduce the simplification time. It should be remarked that computing up to un[24] was using about 13 hours of cpu time on a relatively fast computer (a Digital VAX/8650, rated at 6,000,000 instructions per second).

At this point, back in 1988 when using the earlier version of MAPLE, it was almost impossible to make further progress since we perceived that un[25] had a numerator, which even factored, could not be represented due to its size. Two methods were devised to break this problem. Because one was successful, we never explored the second one to its full extent, although it is worth mentioning it as a potential solution for similar problems. Both methods are suitable for a situation where the goal is relatively trivial (prove that some expression is identically zero). The first method uses exact evaluation of polynomials over ℤ[X] and the second uses a technique of manipulation called “lazy evaluation”.

As mentioned before, we were later (November 1990) able to compute all of the un[i] and prove the result directly using the improved version of MAPLE. Hence we could avoid the evaluation method for the S(F_{4}) case. This presents a formidable task in symbolic computation, some of the solutions would require more than 0.75 Megabytes to print in their most compact representation.

As before, we had to take special computational care with the last steps of the computation. The final linear combination cannot be computed directly, as taking common denominators and expanding would produce monstrous expressions, impossible to represent with present day memories, and too time consuming to simplify. The technique we used was to do this addition pair by pair. At each step we would select the pair which had the highest degree gcd of their denominators. This meant, in practical terms, that the terms being added had almost equal denominators, and the expansion of the numerators was kept to a minimum. Each pair was immediately simplified (removing common gcd between numerator and denominator eliminated) and the process was repeated recursively. This process ended with a single term, 0, and the conjectured S(F_{4}) case was proved for a second time.

When we started these computations more than three years ago, the computers and symbolic computation technology were unable to handle such a big problem. A sign of the evolutions of these fields is the present solution. The methods that we described in this paper are still very valid in the sense that we will always find problems whose solutions are beyond the capacity of present day systems.

The evaluation method is needed for the S(F_{4})^{∨} case. In §§5.1,3 we show how the result may be proved using the evaluation method assuming un[i] is known exactly for i ≤ 24.

5.1. exact evaluation

For this method we use the well known theorem: Let p(x) be a polynomial over ℤ[x], of degree d. If p(0) = p(1) = p(2) = … = p(d) = 0 then p(x) is identically 0.

We need a lemma extending this theorem:

Lemma 5.1. If p(x, y, .., z) is a polynomial in ℤ[x, y, .., z] with degree d_{x} in x, then if

p(0, y, .., z) = p(1, y, .., z) = … = p(d_{x}, y, .., z) = 0  (5.2)

then p(x, y, .., z) is identically 0.

This can be proved by looking at the polynomial factors of each monomial in y, .., z. (Please note that we are talking about exact evaluation of polynomials over ℤ[X] in a symbolic computation system, and not about floating point or approximate evaluation.)

The main idea is to do all the computation for a sufficiently large number of values of one of the variables. The number of such evaluations should be larger than the degree (or an upper bound on the degree) of the numerator of the final result since in principle we the know the denominator of the final result. We must be careful to avoid evaluations that would produce a zero in the denominator.

A note on the complexity of operations is in order. Most algorithms in computer algebra use time and space proportional to the size of the problem they are solving. In particular, computing gcds requires time O(n^{3}) where n is the number of terms in the expanded representation of the input. A polynomial of degree d on k variables has (d + 1)^{k} terms. Computing gcds on such polynomials will cost

O((d + 1)^{3k}).  (5.3)

If we only want to test for zero on the final result, then d + 1 computations with k − 1 variables are sufficient, requiring

O((d + 1)(d + 1)^{3(k−1)}) = O((d + 1)^{3k−2})  (5.4)

(for this we assume that the O(n^{3}) computations dominate the total computation). Saving a factor of (d + 1)^{2}, where d is in the hundreds may be the difference between computing for few days or a few lifetimes.

We may write the result (4.25) as a rational function num^{∗}/den^{∗} where num^{∗}, den^{∗} are polynomials in q, s, t and den^{∗} is known precisely. The idea is to find a bound for the degrees of num^{∗} in s or t and show that num^{∗} is identically zero by evaluating (4.25) at enough values of s or t. The result will follow provided the number of evaluations is greater than the corresponding degree and that we check that den^{∗} does not vanish at any of these values. A rough estimate can be obtained by taking den^{∗} = ∏_{i=2}^{37} p_{i,i}. In this case it is a simple matter to show that

deg_{t} num^{∗} ≤ 240  and  deg_{s} num^{∗} ≤ 360.  (5.5)

With this estimate we would require 241 evaluations in t, but this is impractical. More accurate bounds will mean less computation. With a better choice of den^{∗} we can obtain the following bounds

deg_{t} num^{∗} ≤ 82  and  deg_{s} num^{∗} ≤ 85.  (5.6)

This is achieved by computing the un[i] precisely for i ≤ 24, and studying the form of the equations for the un[i] (i > 24) to get more precise bounds on the degrees. We give the details in §5.3. At one time we considered using a bootstrap technique to determine exact values for the degrees of the un[i] but we found that this would have required a prohibitive number of evaluations. Some details of this other approach are also given in §5.3.

Thus to prove the result via the evaluation method at least 83 distinct evaluations if t or 86 evaluations in s are needed. Since we were later able to avoid the evaluation method for the S(F_{4}) case we omit further details.

5.2. the “lazy evaluation” approach

The triangularity of the system, and the fact that we want to test for zero equivalence on a linear expression in the un[i], suggests another approach. Loosely speaking, what we did in the previous section is to solve sequentially for all un[i] from 1 to 37 and then compute the final answer. What we can do is compute backwards, i.e. start with equation (4.25) as an equations on the symbols un[i] and use the triangularity to substitute un[37] in terms of the other un[i], simplify, then substitute un[36], simplify, etc. Equation (4.25) is, at any step, a linear polynomial in all the unknowns un[i]. Hence, it can be kept separate, i.e. keep just the coefficients of the un[i].

The first observation is that if we continue the process to the very end, it is likely to be of the same complexity as the direct solution. So complete backward solution is not necessarily the goal, as the coefficients of the un[i] will now be the ones which may grow unboundedly. The most promising approach is to compute backwards just enough as to meet the forward computation, i.e. compute backwards until we obtain a polynomial in the first 24 un[i]. At this point we can substitute, simplify and add all the terms.

The success of the previous method killed any further investigation of this approach. The bottom line is that the main result is proven and there is no need to do additional expensive computations.

5.3. bounding the degree

In this section we explain how we came by the bounds for the degrees given in (5.6). We also discuss an alternative approach. It is clear from (3.18) that

deg_{t} p_{i,i} = |S_{1}| = 6,  deg_{s} p_{i,i} = |S_{2}| = 10,  (5.7)

and

deg_{t} p_{i,j} ≤ deg_{t} p_{i,i},  deg_{s} p_{i,j} ≤ deg_{s} p_{i,i},  (5.8)

for 2 ≤ i ≤ 37 and 1 ≤ j ≤ i. It follows from (4.24) that for 2 ≤ i ≤ 37 we have

deg_{x} numer(un[i]) ≤ deg_{x} denom(un[i])  (5.9)

where x = s or t. Recall that we are able to compute un[i] precisely for i ≤ 24. To obtain good estimates for the degrees of the remaining un[i] we study the equations for the un[i] more closely. We recall that each such equation (see (4.24) gives un[i] in terms of un[j] for 1 ≤ j < i. However closer examination of the actual equations reveals that quite often not all of the un[j] for 1 ≤ j < i are present. For example, for i = 26 un[j] is missing for j = 8, 15, 16, 19, 20, 21, 22, 23, 24, 25. For 2 ≤ i ≤ 37 we denote by M_{i} the set of j (1 ≤ j ≤ i for which un[j] is missing from the equation giving un[i]. For example, M_{26} = {8, 15, 16, 19, 20, …, 25}. A complete list of the M_{i} is given in Table VI. These were computed by running a modified version of the FORTRAN program that produced the equations. We denote by P_{i} the complement of M_{i} in the interval 1 ≤ j ≤ i; i.e. the set of j for which un[j] is present in the equation giving un[i]. We can now compute a reasonable multiple of the true denominator of each un[i] which we will call den^{∗}[i]. We define den^{∗}[i] recursively as follows:

if 1 ≤ i ≤ 24 then

den^{∗}[i] := denom(un[i])

else

den^{∗}[i] := p_{i,i} lcm_{j∈P_{i}} (den^{∗}[j]).

The den^{∗}[i] are easily computed and are given in Table X. We note that the algorithm for the lcm computation was not the usual one used in MAPLE. Here we kept all polynomials factored and the lcm was computed by scanning as in our gcd computations. It is easily seen that un[i]den^{∗}[i] ∈ ℤ[s, t, q]. We observe that

den^{∗} := lcm_{1≤i≤37} den^{∗}[i] = den^{∗}[37].  (5.10)

We let

num := ∑_{i=1}^{37} y[i] numer(un[i]) (\frac{den^{∗}}{denom(un[i])}) ,  (5.11)

and num ∈ ℤ[s, t, q]. Although we cannot compute num we can easily estimate its degrees. The y[i] are defined in (4.17) and are given in Table III. For 1 ≤ i ≤ 37 we have

deg_{t} y[i] ≤ 24,  deg_{s} y[i] = 0,  (5.12)
deg_{t} den^{∗} = 58,  deg_{s} den^{∗} = 85;  (5.13)

so that, by (5.9) we have

deg_{t} num ≤ 24 + 58 = 82  and  deg_{s} num ≤ 85.  (5.14)

We observe that den^{∗} is a multiple of the denominator of R_{a+1,b}/R_{a,b} (given in (4.16)) and that

deg_{t} (\frac{R_{a+1,b}}{R_{a,b}} ) = 24,  deg_{s} (\frac{R_{a+1,b}}{R_{a,b}} ) = 0.  (5.15)

Here degree of a rational function means degree of the numerator minus degree of the denominator. Hence

num^{∗} := den^{∗} \frac{R_{a+1,b}}{R_{a,b}} − num ∈ ℤ[s, t, q].  (5.16)

Now (4.25) is

\frac{R_{a+1,b}}{R_{a,b}} − ∑_{i=1}^{37} y[i]un[i] = \frac{num^{∗}}{den^{∗}} ,  (5.17)

where den^{∗} = den^{∗}[37] (see Table X),

deg_{t} num^{∗} ≤ 24 + 58 = 82  (5.18)

and

deg_{s} num^{∗} ≤ 85,  (5.19)

which are the estimates given in (5.6).

As mentioned before, at one time we considered using a bootstrap technique for determining the exact values for the degrees of the un[i]. We now discuss this technique and why it was abandoned. Suppose we know the degrees of the un[i] exactly for i < i_{0}. To determine the degree of un[i_{0}] we do enough substitutions in s to determine the degree in t and enough substitutions in t to determine the degree in s. For the sorts of rational functions we have this technique will work, but the number of substitutions required is too high to be practical.

The problem at hand is as follows: Suppose we are given a polynomial f(s, t, q) and we know g(s, t, q) for a finite set T of values of t. Also suppose f(s, t, q) divides g(s, t, q) for t ∈ T. By choosing the size of T large enough can we conclude that f divides g in ℤ[s, t, q]? How big must T be ?

We are able to answer these questions for a generic case. Let f and g have the form

f = b_{m}s^{m} + b_{m−1}s^{m−1} + … + b_{0},  (5.20)
g = a_{n}s^{n} + a_{n−1}s^{n−1} + … + a_{0},  (5.21)

where the b_{j} and a_{i} are in ℤ[t, q] and n ≥ m. Define

M := max{deg_{t} b_{m−1}, deg_{t} b_{m}b_{m−2}, …, deg_{t} b_{m}^{m−1}b_{0}}.  (5.22)

Lemma 5.2. Let f, g and M be as above. If

(i) b_{m} does not divide f or b_{m} = ±1, (ii) T is a set of integers (or rationals), (iii) t′ ∈ T implies b_{m}(t′, q) is not zero, (iv) |T | > deg_{t}g + (n + m − 1)deg_{t}b_{m} + (n − m + 1)M,

(v) f(s, t′, q) divides g(s, t′, q) for t′ ∈ T,

then f(s, t, q) divides g(s, t, q).

Proof. The idea is to divide f into g as a polynomial in s. The coefficients may be rational functions in t and q. We obtain something like

g(s, t, q) = f(s, t, q)u(s, t, q)(b_{m})^{−k_{1}} + r(s, t, q)(b_{m})^{−k_{2}},  (5.23)

where u and r are in ℤ[s, t, q], deg_{s} r < deg_{s} f and k_{1}, k_{2} are some nonnegative integers. We may assume that u and b_{m} are relatively prime. We know f divides g for t ∈ T. It follows by the uniqueness of the remainder that

r(s, t, q) = 0 for t ∈ T .

We would like to conclude that r(s, t, q) is identically zero. The problem is that the degree of r in t might be quite large compared with deg_{t} and deg_{s} of g! The right side of the inequality (iv) above is an estimate for deg_{t} r. So we have |T | > deg_{t} r. It follows that r is identically zero. Finally, from (i) it follows that we may take k_{1} = 0 and we are done.

□

Example. Let f = t^{3}s^{4}q^{3} + 1 and let g be the numerator of un[37] before cancellation. We suspect that f divides g. In this case m = 4, b_{m} = t^{3}q^{3} and we assume that n = 69 and deg_{t} g = 50. We get the bound

deg_{t} r ≤ 50 + 69(3) + (69 − 4 + 1)9 + 3(3) = 860,

which is quite large. Hence we must take |T | > 860 and t′ = 0 is not allowed.

6. Triangularity Results and the S(R)^{∨} Case

In this section we prove that the analog of Theorem 3.3 holds for the S(R)^{∨} case, where R is a reduced irreducible root system. The possibilities are S(B_{ℓ})^{∨}, S(C_{ℓ})^{∨}, S(F_{4})^{∨} and S(G_{2})^{∨}. In the S(R)^{∨} case, (1.1) has the form

C.T. ∏_{α∈R^{∨+}}(x^{α}; q^{u_{α}})_{k_{α}}(q^{u_{α}}x^{−α}; q^{u_{α}})_{k_{α}} = a certain explicit product.  (6.1)

The main difference between this and the S(R) case is that the product on the left side is over R^{∨+} instead of over R^{+}. Also, for S(R) we have u_{α} ≡ 1; but for S(R)^{∨} we have u_{s} = 1 and u_{l} = 2 (for S(B_{ℓ})^{∨}, S(C_{ℓ})^{∨}, S(F_{4})^{∨}) or u_{l} = 3 (for S(G_{2})^{∨}).

In §3 we handled the S(R) case by using the transformation x_{i^{∗}} ← qx_{i^{∗}}, where i^{∗} satisfied the properties of Lemma 3.1. This led to a triangular system of equations. The proof of the triangularity depended on the fact that our transformation added at most one extra product for each root in G_{a,b}, except for possibly one root. The possible exception

was the maximal root β^{∼}, which could give two extra factors.

This time, for S(R)^{∨}, we will use the transformation x_{i^{∗∗}} ← qx_{i^{∗∗}}, where i^{∗∗} is given below in Lemma 6.1. This transformation will have the property that at most one extra

product in G_{a,b} is produced for each root except possibly the maximal short root β^{∧}, which could give rise to two extra factors.

If Δ = {γ_{1}, …, γ_{ℓ}} is a base for R then Δ^{∨} = {γ_{1}^{∨}, …, γ_{ℓ}^{∨}} is a base for R^{∨}. This time we write vectors in terms of Δ^{∨} so that x^{γ_{i}^{∨}} means x_{i}, and for β ∈ R^{∨+} we may write

β = ∑_{i=1}^{ℓ} c_{i}(β)γ_{i}^{∨},

where c_{i}(β) ∈ ℕ. We have the following analog of Lemma 3.1.

Lemma 6.1. Let R be a reduced irreducible root system of rank ℓ. There is an integer i^{∗∗} = i^{∗∗}(R^{∨}), 1 ≤ i^{∗∗} ≤ ℓ, that satisfies the following properties:

(i) β ∈ R^{∨+} ⇒ c_{i^{∗∗}}(β) = 0, u_{β}, 2u_{β},

(ii) β ∈ R^{∨+} and c_{i^{∗∗}}(β) = 2u_{β} ⇒ β is the maximal short root β^{∧}.

Let S_{0}^{∨} = {β ∈ R^{∨+} : c_{i^{∗∗}}(β) > 0}. The analog of (3.2) is

\frac{G_{a,b}(x_{i^{∗∗}} ← qx_{i^{∗∗}})}{G_{a,b}(x)} = \{ \begin{matrix}q^{−δ_{i^{∗∗}}} ∏_{α∈S_{0}^{∨}} \frac{(1 − p(α)x^{α})}{(p(α)/q^{u_{α}} − x^{α})}, & if c_{i^{∗∗}}(β^{∧}) = u_{β^{∧}}, \\ q^{−δ_{i^{∗∗}}} \frac{(1 − tqx^{β^{∧}})}{(t/q − qx^{β^{∧}})} ∏_{α∈S_{0}^{∨}} \frac{(1 − p(α)x^{α})}{(p(α)/q^{u_{α}} − x^{α})}, & if c_{i^{∗∗}}(β^{∧}) = 2u_{β^{∧}}, \end{matrix}

(6.2)

where δ_{i^{∗∗}} = c_{i^{∗∗}}(δ), and

p(α) = \{ \begin{matrix}t = q^{au_{s}}, & α short, \\ s = q^{bu_{l}}, & α long. \end{matrix}  (6.3)

We note that c_{i^{∗∗}}(β^{∧}) = u_{β^{∧}} for S(B_{ℓ})^{∨}, S(C_{ℓ})^{∨} and c_{i^{∗∗}}(β^{∧}) = 2u_{β^{∧}} for S(F_{4})^{∨}, S(G_{2})^{∨}.

Let P and Q be the numerator and denominator of the right side of (6.2). The proof of the following theorem is analogous to that of Theorem 3.3.

Theorem 6.2. Consider the affine root system S(R)^{∨}. Let β = −α − δ where α ∈ Λ ∩ \overline{C} and α ≠ 0. Then the equation

C.T. [x^{β}Q(x)G_{a,b}(x_{i^{∗∗}} ← qx_{i^{∗∗}})] = C.T. [x^{β}P (x)G_{a,b}(x)]  (6.4)

can be written as

E_{β} : ∑_{\begin{matrix}ρ≺α \\ ρ∈Λ∩\overline{C} \end{matrix}} p_{α,ρ}(t, s, q)H(ρ + δ) = 0,  (6.5)

26 F.G. Garvan and G.H. Gonnet

where the p_{α,ρ}(t, s, q) = p_{α,ρ}(q^{au_{s}}, q^{bu_{l}}, q) are certain polynomials in q and p_{α,α} ≢ 0.

To aid the reader we give the analog of (3.18), for the case c_{i^{∗∗}}(β^{∧}) = 2u_{β^{∧}}. Let

S_{1}^{∨} = {β ∈ R_{short}^{∨+} : c_{i^{∗∗}}(β) > 0} ∪ {β^{∧}^{∗}}  (6.6)

and

S_{2}^{∨} = {β ∈ R_{long}^{∨+} : c_{i^{∗∗}}(β) > 0},  (6.7)

where β^{∧}^{∗} is a copy of β^{∧}, the maximal short root, so that S_{1}^{∨} is a multiset. We find that (6.4) is equivalent to

C.T. ∑_{\begin{matrix}B⊂S_{1}^{∨} \\ C⊂S_{2}^{∨} \end{matrix}}(−1)^{|B|+|C|} \{t^{|B|}s^{|C|}q^{χ^{∧}^{∗}(B)} − t^{|S_{1}^{∨}|−|B|}s^{|S_{2}^{∨}|−|C|}q^{α_{i^{∗∗}} −χ^{∧}(B)}\} (6.8)
·x^{δ−sum(B)−sum(C)+α} G_{a,b}(x)
= 0,

where

χ^{∧} (B) = \{ \begin{matrix}1, & β^{∧}∈ B, \\ 0, & otherwise, \end{matrix}  (6.9)

and

χ^{∧}^{∗} (B) = \{ \begin{matrix}1, & β^{∧}^{∗}∈ B, \\ 0, & otherwise. \end{matrix}  (6.10)
7. Implementing the S(F_{4})^{∨} Case

We shall prove the S(F_{4})^{∨} case of (1.1): Theorem 7.1. Let a, b ∈ ℕ. Then the constant term of

F′_{a,b}(x_{1}, x_{2}, x_{3}, x_{4})  (7.1)

:= ∏_{1≤i<j≤4}(x_{i}x_{j}; q)_{a}(qx_{i}^{−1}x_{j}^{−1}; q)_{a}(x_{i}x_{j}^{−1}; q)_{a}(qx_{i}^{−1}x_{j}; q)_{a}

· ∏_{1≤i≤4}(x_{i}^{2}; q^{2})_{b}(q^{2}x_{i}^{2}; q^{2})_{b}

· ∏_{r_{2},r_{3},r_{4}=±1}(x_{1}x_{2}^{r_{2}}x_{3}^{r_{3}}x_{4}^{r_{4}}; q^{2})_{b}(q^{2}x_{1}^{−1}x_{2}^{−r_{2}}x_{3}^{−r_{3}}x_{4}^{−r_{4}}; q^{2})_{b}

is equal to

R′_{a,b} = \frac{(q; q)_{6a+6b}(q; q)_{4a+4b}(q; q)_{2a+6b}(q; q)_{4a+2b}(q; q)_{4b}(q; q)_{3a}(q; q)_{2b}}{(q; q)_{5a+6b}(q; q)_{3a+6b}(q; q)_{3a+4b}(q; q)_{3a+2b}(q; q)_{a+4b}(q; q)_{a+2b}(q; q)_{a}^{3}} (7.2)

·\frac{(q^{2}; q^{2})_{3a+6b}(q^{2}; q^{2})_{2a+4b}(q^{2}; q^{2})_{3a+2b}(q^{2}; q^{2})_{a+4b}(q^{2}; q^{2})_{3b}(q^{2}; q^{2})_{2a}}{(q^{2}; q^{2})_{3a+5b}(q^{2}; q^{2})_{3a+3b}(q^{2}; q^{2})_{2a+3b}(q^{2}; q^{2})_{a+3b}(q^{2}; q^{2})_{2a+b}}

·\frac{(q^{2}; q^{2})_{a}}{(q^{2}; q^{2})_{a+b}(q^{2}; q^{2})_{b}^{3}} .

Let

F_{a,b}(x_{1}, x_{2}, x_{3}, x_{4})  (7.3)

:= ∏_{1≤i<j≤4}(x_{i}x_{j}; q)_{a}(qx_{i}^{−1}x_{j}^{−1}; q)_{a−1}(x_{i}x_{j}^{−1}; q)_{a}(qx_{i}^{−1}x_{j}; q)_{a−1}

· ∏_{1≤i≤4}(x_{i}^{2}; q^{2})_{b}(q^{2}x_{i}^{2}; q^{2})_{b−1}

· ∏_{r_{2},r_{3},r_{4}=±1}(x_{1}x_{2}^{r_{2}}x_{3}^{r_{3}}x_{4}^{r_{4}}; q^{2})_{b}(q^{2}x_{1}^{−1}x_{2}^{−r_{2}}x_{3}^{−r_{3}}x_{4}^{−r_{4}}; q^{2})_{b−1}

and

H_{a,b} := C.T. F_{a,b}.  (7.4)

We know

H_{a,b} = H′_{a,b}/W (q^{a}, q^{2b}),  (7.5)

where H′_{a,b} := C.T. F′_{a,b} and W (t_{1}, t_{2}) is given in (4.9). So if we let

R_{a,b} := R′_{a,b}/W (q^{a}, q^{2b}),  (7.6)

then we must show that H_{a,b} = R_{a,b}. Again we proceed by induction on a; i.e. we want to show that

\frac{H_{a+1,b}}{H_{a,b}} = \frac{R_{a+1,b}}{R_{a,b}} .  (7.7)

As before, this will be enough in view of Lemma 2.2 since the long roots of F_{4} are isomorphic to D_{4} and (1.1) is known for S(D_{4}) by Kadell (to appear). Hence, again all we need to show is (7.7). We let

G_{a,b}(x) := x^{−δ}F_{a,b}(x),  (7.8)

where δ is given by (4.8), F_{a,b} is defined in (7.3), and G_{a,b} is antisymmetric. A routine calculation gives (t = q^{a}, s = q^{2b})

R_{a+1,b}/R_{a,b} = (t^{3}q^{3} + t^{2}q^{2} + tq + 1)(−1 + t^{4}q^{2})(t^{3}sq^{3} + 1)(t^{3}sq^{2} + 1)  (7.9)
(t^{3}sq + 1)(−1 + t^{4}s^{4}q^{2})(t^{3}s^{3}q^{2} + 1)(t^{3}s^{3}q + 1)(−1 + t^{3}q^{2})
(−1 + t^{3}q)(−1 + t^{4}sq^{3})(−1 + t^{4}sq)(−1 + t^{2}s^{3}q)
(−1 + t^{4}s^{2}q^{3})(−1 + t^{4}s^{2}q^{2})(−1 + t^{4}s^{2}q)(−1 + t^{6}s^{3}q^{5})
(−1 + t^{6}s^{3}q^{3})(−1 + t^{6}s^{3}q)(1 + t)(1 + t + t^{2})(1 + ts^{2})
(1 + st^{2})(1 + ts)(1 + t^{2}s^{2})(1 + t^{3}s^{3})
/((−1 + t^{5}s^{3}q^{5})(−1 + t^{5}s^{3}q^{4})(−1 + t^{5}s^{3}q^{3})(−1 + t^{5}s^{3}q^{2})
((−1 + t^{5}s^{3}q)(−1 + t^{3}s^{2}q)(−1 + t^{3}s^{2}q^{2})(−1 + t^{3}s^{2}q^{3})
(−1 + t^{6}s^{5}q^{2})(−1 + t^{6}s^{5}q^{4})(−1 + t^{6}s^{5}q^{6})(−1 + t^{4}s^{3}q^{2})
(−1 + t^{4}s^{3}q^{4}))

We take the same base Δ = {γ_{1}, γ_{2}, γ_{3}, γ_{4}} and fundamental chamber as in §4. See (4.5), (4.6). We note that that part of the product in F_{a,b} that corresponds to the short roots is the same as in the S(F_{4}) case. This means that (4.17) holds, i.e. we have

H_{a+1,b} = ∑_{i=1}^{37} y[i] H(δ + v(i)),  (7.10)

where H(ρ) = C.T. (x^{ρ}G_{a,b}), the v(i) are the same as those in the S(F_{4}) case, and the y[i] are the exact same polynomials as in the S(F_{4}) case. See Tables II and III. Hence, as before, we need to find and solve 36 equations in the 37 unknowns H(δ + v(i)).

Next we generate equations via Zeilberger’s Equation Steps 1-6 modified using the results of §6. For S(F_{4})^{∨} we may take i^{∗∗} = 4. Recall that i^{∗∗} must satisfy the properties given in Lemma 6.1. S_{1}^{∨}, S_{2}^{∨} of (6.6), (6.7) are

S_{1}^{∨} = {(0, 1, −1, 0), (1, 0, −1, 0), (0, 1, 0, 1), (0, 1, 0, −1),  (7.11)
(1, 0, 1, 0), (1, 0, 0, 1), (1, 0, 0, −1), (0, 1, 1, 0),
(1, 1, 0, 0), (1, 1, 0, 0)^{∗}},

and

S_{2}^{∨} = {(1, 1, −1, 1), (1, 1, −1, −1), (0, 2, 0, 0), (2, 0, 0, 0),  (7.12)
(1, 1, 1, 1), (1, 1, 1, −1)}.

Here β^{∧}^{∗}= (1, 1, 0, 0)^{∗} is a copy of β^{∧}= (1, 1, 0, 0), the maximal short root, so that S_{1}^{∨} is a multiset. For B ⊂ S_{1}^{∨} we define

χ^{∧}^{∗} (B) = \{ \begin{matrix}1, & (1, 1, 0, 0)^{∗} ∈ B, \\ 0, & otherwise, \end{matrix}  (7.13)

and

χ^{∧} (B) = \{ \begin{matrix}1, & (1, 1, 0, 0) ∈ B, \\ 0, & otherwise. \end{matrix}  (7.14)

By taking α = v(i) in (6.8) we have

C.T. ∑_{\begin{matrix}B⊂S_{1}^{∨} \\ C⊂S_{2}^{∨} \end{matrix}}(−1)^{|B|+|C|}\{t^{|B|}s^{|C|}q^{χ^{∧}^{∗}(B)} − t^{|S_{1}^{∨}|−|B|}s^{|S_{2}^{∨}|−|C|}q^{d_{i}−χ^{∧}(B)}\} (7.15)
·x^{δ−sum(B)−sum(C)+v(i)}G_{a,b}
= 0,

where d_{i} = c_{4}(v(i)).

For 1 ≤ i ≤ 37, un[i] is defined as in (4.22). We have written a FORTRAN program whose input is an integer i, 2 ≤ i ≤ 37, and whose output is a linear equation in the un[j] of the same form as in (4.24). Everything proceeds as before. The classes with similar denominators are the same as before. This time, due to the fact that the degrees of the numerators are smaller, we were able to compute directly up to un[26]. From (7.15) we have

deg_{t} p_{i,i} = |S_{1}^{∨}| = 10,  deg_{s} p_{i,i} = |S_{2}^{∨}| = 6,  (7.16)

and the analogs of (5.8)–(5.9) hold. The sets of missing unknowns M_{i} are given in Table VII. The den^{∗}[i] (see Table XI), den^{∗}, num and num^{∗} are defined as before, except that den^{∗}[i] is assigned denom(un[i]) for i ≤ 26 (instead of i ≤ 24). The y[i] are the same as before and we have

deg_{t} den^{∗} = 113,  deg_{s} den^{∗} = 73;  (7.17)

so that

deg_{t} num ≤ 137  and  deg_{s} num ≤ 73.  (7.18)

As before, we observe that den^{∗} is a multiple of the denominator of R_{a+1,b}/R_{a,b} (given in (7.9)) and we have

deg_{t} num^{∗} ≤ 137,  deg_{s} num^{∗} ≤ 73.  (7.19)

To prove the result we computed all un[i] and the analog of (4.25) for s = 0, 1, 2, …, 47, 48 excluding s = 4, 9, 16, 25, 36 and for s = −1, −2, …, −39, −40, a total of 84 different values (by (7.19) at least 74 values were required). The final result (the analog of (4.25)) was zero for all these computations. Since these computations were first done, we have been able to compute exactly up to un[36]. This would allow even fewer evaluations necessary.

8. Further Results and Prospects

A consequence of our triangularity results is that a result “like” (1.1) must hold. To be precise, let’s fix the affine root system S and consider the equal parameter case of (1.1), i.e. k_{α} ≡ a. As in §2 let H_{a}′, R_{a}′ denote the left and right sides respectively of (1.1). It can be shown that the H_{a}′ satisfy a certain homogeneous linear recurrence with polynomial coefficients (in q and q^{a}) using I.N. Berstein’s theory of holonomic systems. See (Zeilberger, to appear). However, the bound on the order of this recurrence from the theory is quite large. On the other hand it is clear that the right sides of (1.1), i.e. the R_{a}′, satisfy a first order recurrence or if you like form a q-hypergeometric sequence. This means that there exist polynomials P (q, q^{a}), Q(q, q^{a}) such that

R_{a+1}′/R_{a}′ = P (q, q^{a})/Q(q, q^{a}).  (8.1)

From our triangularity results it follows that the left sides of (1.1) also form a qhypergeometric sequence. In fact we can give bounds on the degrees of the polynomials involved. We have

Theorem 8.1. The sequence {H_{a}′}_{a=0}^{∞} is a q-hypergeometric sequence, i.e. there exist polynomials U, V ∈ ℤ[q, t] (where t = q^{a}) such that

H_{a+1}′/H_{a}′ = U(q, t)/V (q, t),  (8.2)

and

degree_{t}(U) ≤ 2(|R_{short}| + u_{l}|R_{long}|) + (|S′_{1}| + u_{l}|S′_{2}|)(|S′| − 1)  (8.3)
degree_{t}(V) ≤ (|R_{short}| + u_{l}|R_{long}|) + (|S′_{1}| + u_{l}|S′_{2}|)(|S′| − 1)  (8.4)

where

S′ = {α ∈ (δ + Λ) ∩ C : α ≺ 3δ}  (8.5)

and for i = 1, 2 S′_{i} = S_{i} (resp. S_{i}^{∨}) for S = S(R) (resp. S(R^{∨})).

Remarks. If there is only one root length S′ coincides with S given in (2.16). S_{i} and S_{i}^{∨} are given in (3.12), (3.13) and (6.6), (6.7) respectively. We note also that, for fixed b, the H_{a,b}′ form a q-hypergeometric sequence, and upper bounds on the degrees of the polynomials involved can be calculated. We leave this as an exercise for the reader. We have omitted the proof of Theorem 8.1 since its proof is straightforward.

For the remaining exceptional cases S(E_{6}), S(E_{7}), S(E_{8}) we have the following table:

Affine root system  |S′_{1}| + u_{l}|S′_{2}|  |S′|
S(E_{6})  16  4679
S(E_{7})  27  60800
S(E_{8})  58  1055250

Hence the upper bounds given in Theorem 8.1 are a far cry from their “expected” values. S(E_{6}) might be in range with the help of a suitable computer and a sufficiently generous benefactor. However S(E_{8}) certainly is not. This would involve solving a triangular system involving 1055249 equations in 1055250 unknowns. If this isn’t bad enough each of the equations comes from calculating the analog of the sum given in (3.18), which, in this case, is a sum over 2^{58} subsets.

Acknowledgements. We would like to thank John Stembridge, Dennis Stanton, Kevin Kadell and Doron Zeilberger for helpful discussions. The first author would also like to thank John Stembridge for putting him in touch with the second author (via Ian Goulden and David Jackson) and his computer resources. We should point out that a weaker version of Theorem 3.4 had been found earlier by Kevin Kadell. A special mention should be made of Dennis Stanton, who suggested the “root order” was the right order for the triangularity results.

References

Andrews, G.E. (1975). Problems and prospects for basic hypergeometric functions. In: (Askey, R. ed.)

Theory and Applications of Special Functions, pp. 191–224. New York: Academic Press. Bourbaki, N. (1968). Groupes et algebres de Lie, Chapitres IV, V, VI. Paris: Herman. Carter, R.W. (1972) Simple Groups of Lie Type. London/New York: Wiley. Char, B.W., Geddes, K.O., Gonnet, G.H. (1984). GCDHEU: Heuristic polynomial GCD algorithm based

on integer GCD computation. In: Proceedings of Eurosam 84 , Lecture Notes in Computer Science 174, pp. 285–296. New York/Heidelberg/Berlin: Springer-Verlag.

Garvan, F.G. (1989). Some Macdonald-Mehta integrals by brute force. In: (Stanton, D. ed.) q-Series

and Partitions, IMA Vol. Math. Appl. 18, pp. 77-98. New York/Berlin: Springer. Garvan, F.G. (1990). A proof of the Macdonald-Morris root system conjecture for F_{4}. SIAM J. Math.

Anal. 21, 803–821. Gustafson, R.A. (1990). A generalization of Selberg’s beta integral. Bulletin (new series) Amer. Math.

Soc. 22, 97–105. Gustafson, R.A. (to appear). Some q-beta and Mellin-Barnes integrals on compact Lie groups and Lie

algebras. Trans. Amer. Math. Soc. Habsieger, L. (1986). La q-conjecture de Macdonald-Morris pour G_{2}. C. R. Acad Sci. 303, 211-213. Humphreys, J.E. (1972). Introduction to Lie Algebras and Representation Theory. New York/Heidelberg

Berlin: Springer-Verlag. Kadell, K.W.J. (to appear). A proof of the q-Macdonald-Morris conjecture for BC_{n}. Mem. Amer. Math.

Soc. Knuth, D.E. (1981). Seminumerical Algorithms, 2nd edition, The Art of Computer Programming, vol.

2. Menlo Park, California: Addison-Wesley. Macdonald, I.G. (1972). The Poincare series for a Coxeter group. Math. Anal. 199, 161–174. Macdonald, I.G. (1982). Some conjectures for root systems and finite reflection groups. SIAM J. Math.

Anal. 13, 988–1007. Morris, W.G. (1982). Constant term identities for finite and affine root systems, Ph. D. thesis, Univ. of

Wisconsin-Madison. Opdam, E.M. (1989). Some applications of hypergeometric shift operators. Inventiones Math. 98, 1–18. Stembridge, J.R. (1988). A short proof of Macdonald’s conjecture for the root system of type A. Proc.

Amer. Math. Soc. 102, 777-786.

Wang, P. (1980). The EEZ-GCD algorithm. SIGSAM Bulletin 14, 50–60. Zeilberger, D., Bressoud, D. (1985). A proof of Andrew’s q-Dyson conjecture. Discrete Math. 54, 201–224. Zeilberger, D. (1987). A proof of the G_{2} case of Macdonald’s root system-Dyson conjecture. SIAM J.

Math. Anal. 18, 880–883. Zeilberger, D. (1988). A unified approach to Macdonald’s root-system conjectures. SIAM J. Math. Anal.

19, 987–1013. Zeilberger, D. (to appear). A holonomic systems approach to special function identities. J. of Computa-

tional and Applied Math. Zippel, R. (1979) Probablistic algorithms for sparse polynomials. In: (Ng, ed.) Proceedings of Eurosam

79 , Lecture Notes in Computer Science 72, pp. 216–226. New York/Heidelberg/Berlin: Springer-Verlag.

Appendix: Tables

Table I. Positive roots of F_{4}.

Short roots  Long roots
coord. w.r.t. coord. w.r.t.  coord. w.r.t. coord. w.r.t.
the e_{i}  the base  the e_{i}  the base
1 -1 0 0  0 1 1 0  1 -1 1 1  1 2 2 0
0 0 1 1  1 1 1 0  1 -1 1 -1  0 1 2 0
0 0 1 -1  0 0 1 0  0 0 2 0  1 1 2 0
0 1 -1 0  0 0 0 1  -1 1 1 1  1 0 0 0
1 0 -1 0  0 1 1 1  1 -1 -1 1  0 1 0 0
0 1 0 1  1 1 1 1  0 0 0 2  1 1 0 0
0 1 0 -1  0 0 1 1  1 1 -1 1  1 2 2 2
1 0 1 0  1 2 3 1  1 1 -1 -1  0 1 2 2
1 0 0 1  1 2 2 1  0 2 0 0  1 1 2 2
1 0 0 -1  0 1 2 1  2 0 0 0  1 3 4 2
0 1 1 0  1 1 2 1  1 1 1 1  2 3 4 2
1 1 0 0  1 2 3 2  1 1 1 -1  1 2 4 2

Table II. The first 37 vectors in \overline{C} ∩ Λ.

coord. of  coord. of  coord. of coord. of
i  v(i) w.r.t. v(i) w.r.t.  i  v(i) w.r.t. v(i) w.r.t.
the e_{i}  the base  the e_{i}  the base
1  0 0 0 0  0 0 0 0  20 4 4 1 1  5 9 13 8
2  1 1 0 0  1 2 3 2  21 5 2 2 1  5 10 14 7
3  1 1 1 1  2 3 4 2  22 5 3 1 1  5 10 14 8
4  2 1 1 0  2 4 6 3  23 5 3 2 0  5 10 15 8
5  2 2 0 0  2 4 6 4  24 5 4 1 0  5 10 15 9
6  2 2 1 1  3 5 7 4  25 5 5 0 0  5 10 15 10
7  3 1 1 1  3 6 8 4  26 3 3 3 3  6 9 12 6
8  3 2 1 0  3 6 9 5  27 4 3 3 2  6 10 14 7
9  3 3 0 0  3 6 9 6  28 4 4 2 2  6 10 14 8
10 2 2 2 2  4 6 8 4  29 5 3 2 2  6 11 15 8
11 3 2 2 1  4 7 10 5  30 5 3 3 1  6 11 16 8
12 3 3 1 1  4 7 10 6  31 5 4 2 1  6 11 16 9
13 4 2 1 1  4 8 11 6  32 5 5 1 1  6 11 16 10
14 4 2 2 0  4 8 12 6  33 6 2 2 2  6 12 16 8
15 4 3 1 0  4 8 12 7  34 6 3 2 1  6 12 17 9
16 4 4 0 0  4 8 12 8  35 6 3 3 0  6 12 18 9
17 3 3 2 2  5 8 11 6  36 6 4 1 1  6 12 17 10
18 4 2 2 2  5 9 12 6  37 6 4 2 0  6 12 18 10
19 4 3 2 1  5 9 13 7

32 F.G. Garvan and G.H. Gonnet

Table III. The polynomials y[i] in (4.17).

i  y[i]
1  1 + 2t + 3t^{2} + 4t^{3} + 5t^{4} + 6t^{5} + 7t^{6} + 8t^{7} + 9t^{8} + 9t^{9} + 9t^{10} + 9t^{11} + 9t^{12} + 9t^{13}

+9t^{14} + 9t^{15} + 9t^{16} + 8t^{17} + 7t^{18} + 6t^{19} + 5t^{20} + 4t^{21} + 3t^{22} + 2t^{23} + t^{24}

2  −t − 2t^{2} − 3t^{3} − 4t^{4} − 5t^{5} − 6t^{6} − 7t^{7} − 7t^{8} − 8t^{9} − 8t^{10} − 8t^{11} − 8t^{12} − 8t^{13} − 8t^{14}

−8t^{15} − 7t^{16} − 7t^{17} − 6t^{18} − 5t^{19} − 4t^{20} − 3t^{21} − 2t^{22} − t^{23}

3  t^{2} + 2t^{3} + 3t^{4} + 4t^{5} + 5t^{6} + 5t^{7} + 5t^{8} + 5t^{9} + 6t^{10} + 6t^{11} + 6t^{12} + 6t^{13} + 6t^{14} + 5t^{15}
+5t^{16} + 5t^{17} + 5t^{18} + 4t^{19} + 3t^{20} + 2t^{21} + t^{22}
4  t^{2} + t^{3} + t^{4} + t^{5} + 2t^{6} + 2t^{7} + 3t^{8} + 3t^{9} + 4t^{10} + 3t^{11} + 3t^{12}

+3t^{13} + 4t^{14} + 3t^{15} + 3t^{16} + 2t^{17} + 2t^{18} + t^{19} + t^{20} + t^{21} + t^{22}

5  t^{4} + t^{5} + t^{6} + t^{7} + 2t^{8} + t^{9} + t^{10} + t^{11} + 2t^{12} + t^{13} + t^{14} + t^{15}
+2t^{16} + t^{17} + t^{18} + t^{19} + t^{20}
6  −t^{3} − t^{4} − 2t^{5} − 2t^{6} − 3t^{7} − 3t^{8} − 4t^{9} − 3t^{10} − 4t^{11} − 3t^{12}

−4t^{13} − 3t^{14} − 4t^{15} − 3t^{16} − 3t^{17} − 2t^{18} − 2t^{19} − t^{20} − t^{21}

7  −t^{3} − 2t^{4} − 3t^{5} − 3t^{6} − 4t^{7} − 4t^{8} − 5t^{9} − 5t^{10} − 7t^{11} − 7t^{12}

−7t^{13} − 5t^{14} − 5t^{15} − 4t^{16} − 4t^{17} − 3t^{18} − 3t^{19} − 2t^{20} − t^{21}

8  t^{4} + t^{5} + 2t^{6} + t^{7} + 2t^{8} + t^{9} + 3t^{10} + 2t^{11} + 4t^{12} + 2t^{13} + 3t^{14}
+t^{15} + 2t^{16} + t^{17} + 2t^{18} + t^{19} + t^{20}
9  −t^{5} − t^{6} − t^{7} − t^{9} − t^{10} − 2t^{11} − t^{12} − 2t^{13} − t^{14} − t^{15} − t^{17} − t^{18} − t^{19}
10  t^{4} + t^{5} + t^{6} + t^{7} + 2t^{8} + 2t^{9} + 2t^{10} + 2t^{11} + 3t^{12} + 2t^{13}
+2t^{14} + 2t^{15} + 2t^{16} + t^{17} + t^{18} + t^{19} + t^{20}
11  t^{4} + t^{5} + 2t^{6} + 2t^{7} + 4t^{8} + 3t^{9} + 4t^{10} + 3t^{11} + 5t^{12} + 3t^{13}
+4t^{14} + 3t^{15} + 4t^{16} + 2t^{17} + 2t^{18} + t^{19} + t^{20}
12  −t^{5} − t^{7} − t^{8} − 2t^{9} − 2t^{11} − t^{12} − 2t^{13} − 2t^{15} − t^{16} − t^{17} − t^{19}
13  t^{6} + t^{8} + 2t^{10} + t^{12} + 2t^{14} + t^{16} + t^{18}
14  −t^{5} − 2t^{6} − 3t^{7} − 2t^{8} − 4t^{9} − 4t^{10} − 5t^{11} − 3t^{12} − 5t^{13}
−4t^{14} − 4t^{15} − 2t^{16} − 3t^{17} − 2t^{18} − t^{19}
15  t^{6} + t^{8} + 2t^{10} + 2t^{12} + 2t^{14} + t^{16} + t^{18}
16  t^{8} + t^{12} + t^{16}
17  −t^{5} − t^{6} − 2t^{7} − 2t^{8} − 3t^{9} − 3t^{10} − 4t^{11} − 3t^{12} − 4t^{13} − 3t^{14} − 3t^{15} − 2t^{16} − 2t^{17}
−t^{18} − t^{19}
18  −t^{7} − t^{8} − 2t^{9} − t^{10} − t^{11} − t^{13} − t^{14} − 2t^{15} − t^{16} − t^{17}
19  t^{6} + t^{7} + 3t^{8} + 2t^{9} + 4t^{10} + 2t^{11} + 4t^{12} + 2t^{13} + 4t^{14} + 2t^{15} + 3t^{16} + t^{17} + t^{18}
20  −t^{7} − t^{8} − 2t^{9} − t^{10} − 2t^{11} − t^{12} − 2t^{13} − t^{14} − 2t^{15} − t^{16} − t^{17}
21  t^{8} + t^{10} + t^{12} + t^{14} + t^{16}
22  −t^{7} − t^{8} − 2t^{9} − t^{10} − 3t^{11} − 2t^{12} − 3t^{13} − t^{14} − 2t^{15} − t^{16} − t^{17}
23  −t^{9} − t^{11} + t^{12} − t^{13} − t^{15}
24  t^{8} + t^{9} + 2t^{10} + t^{11} + 2t^{12} + t^{13} + 2t^{14} + t^{15} + t^{16}
25  −t^{9} − t^{10} − t^{11} − t^{12} − t^{13} − t^{14} − t^{15}
26  t^{6} + 2t^{7} + 3t^{8} + 4t^{9} + 5t^{10} + 5t^{11} + 5t^{12} + 5t^{13} + 5t^{14} + 4t^{15} + 3t^{16} + 2t^{17} + t^{18}
27  −t^{7} − 2t^{8} − 3t^{9} − 3t^{10} − 4t^{11} − 4t^{12} − 4t^{13} − 3t^{14} − 3t^{15} − 2t^{16} − t^{17}
28  t^{8} + t^{9} + t^{10} + t^{11} + 2t^{12} + t^{13} + t^{14} + t^{15} + t^{16}
29  t^{8} + t^{9} + 2t^{10} + 2t^{11} + 3t^{12} + 2t^{13} + 2t^{14} + t^{15} + t^{16}
30  t^{10} + t^{14}
31  −t^{9} − t^{10} − 2t^{11} − t^{12} − 2t^{13} − t^{14} − t^{15}
32  t^{10} + t^{11} + t^{12} + t^{13} + t^{14}
33  −t^{9} − 2t^{10} − 3t^{11} − 3t^{12} − 3t^{13} − 2t^{14} − t^{15}
34  t^{10} + t^{11} + 2t^{12} + t^{13} + t^{14}
35  −t^{11} − t^{12} − t^{13}
36  −t^{11} − t^{12} − t^{13}
37  t^{12}

Table IV. Factorisations of p_{i,i}, the leading coefficients in (4.24).

\begin{matrix}i & p_{i,i} \\ 2 & 2(1 + s + s^{2})(1 + s^{2}t)(1 − s^{6}t^{5}q) \\ 3 & (1 − s^{5}t^{3}q)(1 + s^{5}t^{3}q) \\ 4 & (1 + s + s^{2})(1 − s^{4}t^{3}q)(1 + s^{4}t^{3}q) \\ 5 & (1 + s + s^{2})(1 + s^{2}t)(1 − s^{6}t^{5}q^{2}) \\ 6 & 1 − s^{10}t^{6}q^{3} \\ 7 & (1 + s)(1 − s^{3}t^{2}q)(1 + s^{3}t^{2}q + s^{6}t^{4}q^{2}) \\ 8 & (1 + s + s^{2})(1 − s^{8}t^{6}q^{3}) \\ 9 & (1 + s + s^{2})(1 + s^{2}t)(1 − s^{6}t^{5}q^{3}) \\ 10-12 & (1 − s^{5}t^{3}q^{2})(1 + s^{5}t^{3}q^{2}) \\ 13 & (1 + s)(1 − s^{9}t^{6}q^{4}) \\ 14-15 & (1 + s + s^{2})(1 − s^{4}t^{3}q^{2})(1 + s^{4}t^{3}q^{2}) \\ 16 & (1 + s + s^{2})(1 + s^{2}t)(1 − s^{6}t^{5}q^{4}) \\ 17-20 & 1 − s^{10}t^{6}q^{5} \\ 21-22 & (1 + s)(1 − s^{9}t^{6}q^{5}) \\ 23-24 & (1 + s + s^{2})(1 − s^{8}t^{6}q^{5}) \\ 25 & (1 + s + s^{2})(1 + s^{2}t)(1 − s^{6}t^{5}q^{5}) \\ 26-32 & (1 − s^{5}t^{3}q^{3})(1 + s^{5}t^{3}q^{3}) \\ 33-34,36 & (1 + s)(1 − s^{3}t^{2}q^{2})(1 + s^{3}t^{2}q^{2} + s^{6}t^{4}q^{4}) \\ 35,37 & (1 + s + s^{2})(1 − s^{4}t^{3}q^{3})(1 + s^{4}t^{3}q^{3}) \end{matrix}

Table V. Factorisations of p_{i,i}, the leading coefficients in the analog of (4.24) for S(F_{4})^{∨}.

\begin{matrix}i & p_{i,i} \\ 2 & (1 − s^{3}t^{5}q)(1 + s^{3}t^{5}q) \\ 3 & (1 + t + t^{2})(1 + st^{2})(1 − s^{5}t^{6}q^{2}) \\ 4 & (1 + t)(1 − s^{2}t^{3}q)(1 + s^{2}t^{3}q + s^{4}t^{6}q^{2}) \\ 5-6 & (1 − s^{3}t^{5}q^{2})(1 + s^{3}t^{5}q^{2}) \\ 7 & (1 + t + t^{2})(1 − s^{3}t^{4}q^{2})(1 + s^{3}t^{4}q^{2}) \\ 8 & 1 − s^{6}t^{10}q^{5} \\ 9,17 & (1 − s^{3}t^{5}q^{3})(1 + s^{3}t^{5}q^{3}) \\ 10 & (1 + t + t^{2})(1 + st^{2})(1 − s^{5}t^{6}q^{4}) \\ 11 & (1 + t)(1 − s^{6}t^{9}q^{5}) \\ 12-13 & (1 − s^{3}t^{5}q^{3})(1 + s^{3}t^{5}q^{3}) \\ 14 & (1 + t)(1 − s^{2}t^{3}q^{2})(1 + s^{2}t^{3}q^{2} + s^{4}t^{6}q^{4}) \\ 15,19 & 1 − s^{6}t^{10}q^{7} \\ 16,20,22,23,28,29 & (1 − s^{3}t^{5}q^{4})(1 + s^{3}t^{5}q^{4}) \\ 18 & (1 + t + t^{2})(1 − s^{3}t^{4}q^{3})(1 + s^{3}t^{4}q^{3}) \\ 21,27 & (1 + t)(1 − s^{6}t^{9}q^{7}) \\ 24 & 1 − s^{6}t^{10}q^{9} \\ 25 & (1 − s^{3}t^{5}q^{5})(1 + s^{3}t^{5}q^{5}) \\ 26 & (1 + t + t^{2})(1 + st^{2})(1 − s^{5}t^{6}q^{6}) \\ 30 & (1 + t)(1 − s^{6}t^{9}q^{8}) \\ 31,34 & (1 − s^{6}t^{10}q^{9}) \\ 32,36,37 & (1 − s^{3}t^{5}q^{5})(1 + s^{3}t^{5}q^{5}) \\ 33 & (1 + t + t^{2})(1 − s^{3}t^{4}q^{4})(1 + s^{3}t^{4}q^{4}) \\ 35 & (1 + t)(1 − s^{2}t^{3}q^{3})(1 + s^{2}t^{3}q^{3} + s^{4}t^{6}q^{6}) \end{matrix}

Table VI. Sets of missing unknowns in the equations for S(F_{4}).

\begin{matrix}i & M_{i} \\ 2-9,13,14,23 & \{\} \\ 10 & \{8, 9\} \\ 11 & \{9, 10\} \\ 12 & \{10, 11\} \\ 15,16 & \{14\} \\ 17 & \{14, 15, 16\} \\ 18 & \{15, 16, 17\} \\ 19 & \{16, 17, 18\} \\ 20 & \{14, 17, 18, 19\} \\ 21 & \{16, 20\} \\ 22 & \{21\} \\ 24,25 & \{21, 23\} \\ 26 & \{8, 15, 16, 19, 20, 21, 22, 23, 24, 25\} \\ 27 & \{16, 20, 22, 23, 24, 25, 26\} \\ 28 & \{21, 23, 24, 25, 26, 27\} \\ 29 & \{24, 25, 26, 27, 28\} \\ 30 & \{24, 25, 26, 27, 28, 29\} \\ 31 & \{25, 26, 27, 28, 29, 30\} \\ 32 & \{18, 21, 23, 26, 27, 28, 29, 30, 31\} \\ 33 & \{24, 25, 31, 32\} \\ 34 & \{25, 32, 33\} \\ 35 & \{25, 32\} \\ 36 & \{30, 33, 34, 35\} \\ 37 & \{33, 35\} \end{matrix}

Table VII. Sets of missing unknowns in the equations for S(F_{4})^{∨}.

\begin{matrix}i & M_{i} \\ 2-5,7-9,14,15,24 & \{\} \\ 6 & \{5\} \\ 10 & \{8, 9\} \\ 11,12 & \{9\} \\ 13 & \{9, 12\} \\ 16 & \{14\} \\ 17 & \{9, 12, 13, 14, 15, 16\} \\ 18,19 & \{15, 16\} \\ 20 & \{16\} \\ 21,22 & \{16, 20\} \\ 23 & \{16, 20, 22\} \\ 25 & \{21, 23\} \\ 26 & \{15, 16, 19, 20, 21, 22, 23, 24, 25\} \\ 27 & \{16, 20, 21, 22, 23, 24, 25\} \\ 28 & \{14, 15, 16, 20, 21, 22, 23, 24, 25\} \\ 29 & \{16, 20, 22, 23, 24, 25, 28\} \\ 30 & \{24, 25\} \\ 31 & \{16, 24, 25\} \\ 32 & \{25, 30\} \\ 33,34 & \{24, 25, 31, 32\} \\ 35 & \{25, 26, 32, 33\} \\ 36 & \{25, 32, 35\} \\ 37 & \{25, 32, 33, 36\} \end{matrix}

Table VIII. Polynomials that occur as factors in the factorisations of the den^{∗}[i] for S(F_{4}).

Factor number  Factor
1  1 + s + s^{2}
2  1 + s^{2}t
3  1 − s^{6}t^{5}q
4  1 − s^{5}t^{3}q
5  1 − s^{4}t^{3}q
6  1 − s^{6}t^{5}q^{2}
7  1 + s
8  1 − s^{3}t^{2}q
9  1 − s^{6}t^{5}q^{3}
10  1 − s^{5}t^{3}q^{2}
11  1 − s^{4}t^{3}q^{2}
12  1 − s^{6}t^{5}q^{4}
13  1 − s^{6}t^{5}q^{5}
14  1 − s^{5}t^{3}q^{3}
15  1 + s^{5}t^{3}q^{3}
16  1 − s^{3}t^{2}q^{2}
17  1 + s^{3}t^{2}q^{2} + s^{6}t^{4}q^{4}
18  1 − s^{4}t^{3}q^{3}
19  1 + s^{4}t^{3}q^{3}

Table IX. Polynomials that occur as factors in the factorisations of the den^{∗}[i] for S(F_{4})^{∨}.

Factor number  Factor
1  1 − s^{3}t^{5}q
2  1 + t + t^{2}
3  1 − s^{5}t^{6}q^{2}
4  1 + t
5  1 − s^{2}t^{3}q
6  1 − s^{3}t^{5}q^{2}
7  1 − s^{3}t^{4}q^{2}
8  1 − s^{3}t^{5}q^{3}
9  1 − s^{5}t^{6}q^{4}
10  1 − s^{2}t^{3}q^{2}
11  1 − s^{3}t^{5}q^{4}
12  1 + s^{3}t^{5}q^{4}
13  1 − s^{6}t^{9}q^{7}
14  1 − s^{6}t^{10}q^{9}
15  1 − s^{3}t^{5}q^{5}
16  1 + s^{3}t^{5}q^{5}
17  1 − s^{5}t^{6}q^{6}
18  1 − s^{6}t^{9}q^{8}
19  1 − s^{3}t^{4}q^{4}
20  1 + s^{3}t^{4}q^{4}
21  1 − s^{2}t^{3}q^{3}
22  1 + s^{2}t^{3}q^{3} + s^{4}t^{6}q^{6}

Table X. Factorisations and degrees of the den^{∗}[i]. The entry in the i-th row and j-th column in the main part of the table gives the power of the j-th polynomial from Table VIII in the factorisation of den^{∗}[i].

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 deg_{t} deg_{s} deg_{q}
2  1  5  6  1
3  1 1  8  11  2
4  1 1 1  11  15  3
5  1 1 1 1  16  21  5
6  1 1 1 1  16  21  5
7  1 1 1 1  1  18  24  6
8  1 1 1 1  1  18  24  6
9  1 1 1 1  1 1  23  30  9
10  1 1 1 1  1  1  21  29  8
11  1 1 1 1  1  1  21  29  8
12  1 1 1 1  1 1 1  26  35  11
13  1 1 1 1  1 1 1  26  35  11
14  1 1 1 1  1 1 1 1  29  39  13
15  1 1 1 1  1 1 1 1  29  39  13
16  1 1 1 1  1 1 1 1 1  34  45  17
17  1 1 1 1  1 1 1  26  35  11
18  1 1 1 1  1 1 1 1  29  39  13
19  1 1 1 1  1 1 1 1  29  39  13
20  1 1 1 1  1 1 1 1 1  34  45  17
21  1 1 1 1  1 1 1 1  29  39  13
22  1 1 1 1  1 1 1 1 1  34  45  17
23  1 1 1 1  1 1 1 1 1  34  45  17
24  1 1 1 1  1 1 1 1 1  34  45  17
25 1 1 1 1 1 1  1 1 1 1 1 1  40  55  22
26  1 1 1 1  1 1 1 1  1 1  35  49  19
27  1 1 1 1  1 1 1 1  1 1  35  49  19
28  1 1 1 1  1 1 1 1 1  1 1  40  55  23
29  1 1 1 1  1 1 1 1 1  1 1  40  55  23
30  1 1 1 1  1 1 1 1 1  1 1  40  55  23
31  1 1 1 1  1 1 1 1 1  1 1  40  55  23
32 1 1 1 1 1 1  1 1 1 1 1 1 1 1  46  65  28
33  1 1 1 1 1 1 1 1 1 1  1 1 1 1  46  65  29
34  1 1 1 1 1 1 1 1 1 1  1 1 1 1  46  65  29
35 1  1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1  52  75  35
36 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  52  75  34
37 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  58  85  40

Table XI. Factorisations and degrees of the den^{∗}[i] for S(F_{4})^{∨}. The entry in the i-th row and j-th column in the main part of the table gives the power of the j-th polynomial from Table IX in the factorisation of den^{∗}[i].

i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 deg_{t} deg_{s} deg_{q}
2 1  5  3  1
3 1 1  11  8  3
4 1 1 1  14 10  4
5 1 1 1 1  19 13  6
6 1 1 1 1  19 13  6
7 1 1 1 1 1  23 16  8
8 1 1 1 1 1  23 16  8
9 1 1 1 1 1 1  28 19 11
10 1 1 1 1 1 1  29 21 12
11 1 1 1 1 1 1  29 21 12
12 1 1 1 1 1 1 1  34 24 15
13 1 1 1 1 1 1 1  34 24 15
14 1 1 1 1 1 1 1 1  37 26 17
15 1 1 1 1 1 1 1 1  37 26 17
16 1 1 1 1 1 1 1 1 1  42 29 21
17 1 1 1 1 1 1 1  34 24 15
18 1 1 1 1 1 1 1 1  37 26 17
19 1 1 1 1 1 1 1 1  37 26 17
20 1 1 1 1 1 1 1 1 1  42 29 21
21 1 1 1 1 1 1 1 1  37 26 17
22 1 1 1 1 1 1 1 1 1  42 29 21
23 1 1 1 1 1 1 1 1 1  42 29 21
24 1 1 1 1 1 1 1 1 1  42 29 21
25 1 1 1 1 1 1 1 1 1  1  47 32 26
26 1 1 1 1 1 1 1 1  1  43 31 23
27 1 1 1 1 1 1 1 1 1  1  1  53 37 30
28 1 1 1 1 1 1 1 1 1 1 1 1  1  63 43 38
29 1 1 1 1 1 1 1 1 1 1 1 1  1  63 43 38
30 1 1 2 1 1 1 1 1 1 1 1 1  1 1  73 49 46
31 1 1 2 1 1 1 1 1 1 1 1 1 1  1 1  83 55 55
32 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1  93 61 65
33 1 1 1 2 1 1 1 1 1 1 1 1 1  1 1 1 1  83 55 54
34 1 1 1 2 1 1 1 1 1 1 1 1 1 1  1 1 1 1  93 61 63
35 1 1 1 3 1 1 1 1 1 1 1 1 1 1  1 1 1 1 1 1 103 67 72
36 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  103 67 73
37 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 113 73 82