FINITE HURWITZ BRAID GROUP ACTIONS ON

SEQUENCES OF EUCLIDEAN REFLECTIONS

Stephen P. Humphries

Abstract. We prove that if r_{1}, …, r_{n} are Euclidean reflections corresponding to a linearly independent set of vectors, then the group < r_{1}, …, r_{n} > is finite if and only if the natural Hurwitz braid group action on such ordered sets of reflections has finite orbit and we characterise the orbits for this action. We apply this to give a representation of the braid group on n strands onto the alternating or symmetric groups of degree (n + 1)^{n−2} (for most n) which is relevant to the Morse theory of polynomials, as studied by Catanese, Paluszny and Wajnryb.

§1. Introduction

A left self-distributive system (LD-system) [De] is a set U, together with an action of the set on itself, satisfying : a(bc) = (ab)(ac). A fundamental example of such an LD-system is when U is a group and the action is by conjugation. This was first considered by Hurwitz [Hur] and has applications to Galois theory [Vo]. Each such LD-system gives rise to a representation of the braid group B_{n}. Here B_{n} is the group with (standard) generators σ_{1}, …, σ_{n−1} and relations [Bi, p. 18]:

σ_{i}σ_{i+1}σ_{i} = σ_{i+1}σ_{i}σ_{i+1}, for i = 1, …, n − 2,
σ_{i}σ_{j} = σ_{j}σ_{i},  for |i − j| > 1.

Given n ≥ 2 and an LD-system U there is an action of the braid group B_{n} =< σ_{1}, …, σ_{n−1} > on the product U^{n} where, in the conjugation case, the braid generator σ_{i}, 1 ≤ i < n, acts as follows:

σ_{i}(s_{1}, s_{2}, …, s_{n}) = (s_{1}, …, s_{i−1}, s_{i+1}, s_{i+1}^{−1}s_{i}s_{i+1}, s_{i+2}, …, s_{n})
σ_{i}^{−1}(s_{1}, s_{2}, …, s_{n}) = (s_{1}, …, s_{i−1}, s_{i}s_{i+1}s_{i}^{−1}, s_{i}, s_{i+2}, …, s_{n}).  (1.1)

We will be interested in the case where U is a finite reflection group and (s_{1}, s_{2}, …, s_{n}) is a minimal set of generating reflections.

Recall that to every vector v ∈ ℝ^{n}, v ≠ (0, …, 0), there is an associated reflection r_{v} whose action on ℝ^{n} is given by:

r_{v}(w) = w − 2\frac{(v, w)}{\sqrt{(v, v)(w, w)}}v.

In what follows we will adopt the standard terminology for finite reflection groups ([GB, Hu]). Thus an irreducible finite reflection group W =< S > will have a certain type X_{n} where n = |S| is the minimal number of generating reflections. We prove:

Typeset by AMS-TEX

Theorem 1.1. Let n ≥ 3, v_{1}, v_{2}, …, v_{n} ∈ ℝ^{n} with ∥v_{i}∥ = 1 for i = 1, …, n and v_{1}, v_{2}, …, v_{n} linearly independent. Then the B_{n}-orbit of (r_{v_{1}}, r_{v_{2}}, …, r_{v_{n}}) is finite if and only if the group < r_{v_{1}}, r_{v_{2}}, …, r_{v_{n}} > is finite.

The proof of the above result includes an analysis of the B_{n}-orbits of the irreducible finite reflection groups W. In fact it is most natural to define the equivalence relation generated by the B_{n} action together with the action of W by conjugation on such n-tuples of reflections in W. We call this BC_{n}-equivalence. This has been considered by Brieskorn [Br] in relation to singularities.

One may wonder whether, for a generating sequence S = (s_{1}, s_{2}, …, s_{n}) of a group G, the fact that the B_{n}-orbit of S is finite is enough to be able to conclude that G is finite. This however is not the case, since any infinite group generated by a finite union of finite conjugacy classes will give a counterexample to this idea. For example, take a finite group H generated by a conjugacy class C = {c_{1}, …, c_{n}} and such that there is a relation r(c_{1}, …, c_{n}) in these generators having exponent 1 (for example a non-abelian finite simple group). Let G = H ×ℤ. If ℤ =< t >, then the elements tC = {tc_{1}, …, tc_{n}} ⊂ G form a finite conjugacy class in G and since r(tc_{1}, …, tc_{n}) = t we see that they generate G. Thus the B_{n} orbit of (tc_{1}, …, tc_{n}) is contained in (tC)^{n} and so is finite.

For S = (s_{1}, s_{2}, …, s_{n}) as above we define the Coxeter element Π(S) of S to be the product s_{1}s_{2} … s_{n}. The Coxeter element of a finite reflection group W is Π(S) where S is a base of W (defined below). Note from (1.1) that the Coxeter element of S is invariant under the B_{n} action. Further, the conjugacy class of the Coxeter element is not changed under BC_{n}-equivalence. We will let BC_{n}(S)| denote the number of BC_{n} classes of S.

To establish notation we here give the families of finite reflection groups [GB]:

Figure 1.

We prove:

Theorem 1.2. Let n ≥ 1 and let W =< S > be a finite reflection group. If W has type A_{n} or B_{n}, then there is one BC_{n} equivalence class of n reflections generating W.

If W has type D_{n}, n ≥ 4, then |BC_{n}(D_{n})| = n − 2. These are distinguished by their Coxeter elements.

If W has type I_{3}, then |BC_{3}(I_{3})| = 3. These are distinguished by their Coxeter elements. If W has type I_{4}, then |BC_{4}(I_{4})| = 11. These are distinguished by their Coxeter elements. If W has type F_{4}, then |BC_{4}(F_{4})| = 2. These are distinguished by their Coxeter elements. If W has type E_{6}, then |BC_{6}(E_{6})| = 3. These are distinguished by their Coxeter elements. If W has type E_{7}, then |BC_{7}(E_{7})| = 5. These are distinguished by their Coxeter elements. If W has type E_{8}, then there are at least 9 BC_{8} classes which are distinguished by their

Coxeter elements.

We will later give specific representatives for the BC_{n} classes.

Combining the above with a result of Howlett [Ho] (see also [Co; Theorem 12]) we have:

Corollary 1.3. Let n ≥ 3. Let W =< r_{1}, …, r_{n} >, where r_{i} = r_{v_{i}} with v_{1}, …, v_{n} linearly independent. Then the following are equivalent:

(i) W is finite; (ii) the product r_{1} … r_{n} is finite; (iii) the B_{n} orbit of (r_{1}, …, r_{n}) is finite.

The action of B_{n} on the set of sequences S of reflections generating finite groups gives interesting finite representations of the braid groups. Let O_{n}(S) denote the B_{n}-orbit of such an S, |S| = n, | < S > | < ∞, and let P O_{n}(S) denote the set of equivalence classes in O_{n}(S) determined by conjugacy. Then B_{n} acts on P O_{n}(S) and we have permutation representations:

B_{n} → Sym(O_{n}(S)) → Sym(P O_{n}(S)).

Let ρ_{n} : B_{n} → Sym(P O_{n}(S)) denote the composition.

We now consider the above representation in each of the cases A_{n}, B_{n} etc. The A_{n} case has connections with the work of Catanese, Paluszy and Wajnryb on the space of generic polynomials [CP, CW]; see also [Lo]. We also note that the isotropy subgroup for the action of B_{n} on a Coxeter system of an irreducible finite reflection group is determined in [Do].

If < S >= W (A_{n}) ≅ S_{n+1}, then we will show that P O_{n}(S) can be naturally identified with the set E_{n} of trees with n labeled edges (with vertices not labeled). There are (n+1)^{n−2} of these [SSV, S]. It was this action of B_{n} on E_{n} that has been studied in connection with certain questions about the Morse theory of polynomials in [CW, CP, Lo].

Theorem 1.4. Consider the B_{n} action on P O_{n}(S) where < S >= S_{n+1}. Then the action gives a representation of B_{n} of degree (n + 1)^{n−2} which is 2-transitive for all n ≥ 3. If (n + 1)^{n−2} is not of the form

q, \frac{q^{d} − 1}{q − 1} (for d ≥ 2), 2^{d−1}(2^{d} ± 1) (for d ≥ 3),

where q is a prime power, then the B_{n} action is that of the symmetric or alternating group of degree (n + 1)^{n−2}. Specifically, if n > 3 and (n + 1)^{n−2} is not of the above form, then we get the alternating group A_{(n+1)^{n−2}} when n ≡ 1, 2, 3 mod 4 and the symmetric group S_{(n+1)^{n−2}} otherwise.

The above result uses the classification of 2-transitive permutation groups [Cam], which, in turn, depends on the classification of finite simple groups.

We now describe the results of [CP], [CW]. Let P ∈ ℂ[z] be a polynomial of degree n + 1. Then P is lemniscate generic if, when y_{1}, …, y_{n} are the roots of the derivative P′(z), we have (i) P (y_{i}) ≠ 0 and (ii) |P (y_{i})| = |P (y_{j})| only when i = j. Let L_{n} be the set of such, considered as a subset of ℂ^{n+1}, the space of all polynomials of degree n + 1. To P ∈ L_{n} we associate the big lemniscate configuration, this being the union of the singular level sets of |P |, considered up to homeomorphism. This is invariant as P moves in a connected component of L_{n}. Let E_{n} be the set of isomorphism classes of edge-labeled trees on n edges. Then [CP, CW] there is a natural mapping from E_{n} to the set of big lemniscate configurations. There is also a natural action of B_{n} on E_{n}; the same as constructed above. Let Λ_{n} =< (σ_{1}^{2}, (σ_{2}σ_{1})^{3}, (σ_{3}σ_{2}σ_{1})^{4}, …, (σ_{n−1} … σ_{2}σ_{1})^{n} >≅ ℤ^{n−1}. Then the main result of [CP] is: There is a natural bijection between:

(i) π_{0}(L_{n}); (ii) The set of big lemniscate configurations; (iii) The set of Λ_{n}-orbits on E_{n}; (iv) The set

{(x_{0}, x_{1}, …, x_{n})|x_{i} ∈ ℕ, 0 ≤ x_{i} ≤ i, no integer occurs three times in the sequence}.

In our notation E_{n} is just P O_{n}(S), where S is of type A_{n}.

We recall [Bi] the natural permutation representation B_{n} → S_{n} given by σ_{i} ↦ (i, i + 1). For the B_{n} case we have:

Theorem 1.5. Consider the B_{n} action on P O_{n}(S), n ≥ 3, where < S > is of type B_{n}. Then this action gives a representation of B_{n} of degree n^{n−1} which is transitive. The action is not primitive and there is a block system, having n blocks, such that the action of B_{n} on the blocks gives the permutation representation π_{n} : B_{n} → S_{n}.

The action in the D_{n} case is more complicated. For the remaining cases we use MAGMA [MA] to get the following result, where we also indicate some of the representatives of the different BC_{n} classes:

Theorem 1.6. (I_{3}) Let G =< a, b, c|a^{2}, b^{2}, c^{2}, (ab)^{5}, (bc)^{3}, (ac)^{2} > be of type I_{3}. There are three BC_{3} orbits with the following representatives:

(i) S = (a, b, c). Then |P O_{3}(S)| = 10 and ρ_{3}(B_{3}) = S_{10}. (ii) S = (a, b, cbacbcabc). Then |P O_{3}(S)| = 18 and the B_{3} action gives a transitive but imprimitive representation into S_{18}. There is a unique set of blocks of size two and the action on these blocks is that of the alternating group A_{9}. The kernel is ℤ_{2}^{9}. (iii) S = (a, c, cbacbcabc). Then |P O_{3}(S)| = 10 and ρ_{3}(B_{3}) = S_{10}.

(I_{4}) Let G =< a, b, c, d|a^{2}, b^{2}, c^{2}, d^{2}, (ab)^{5}, (bc)^{3}, (ac)^{2}, (ad)^{2}, (bd)^{2}, (cd)^{3} > be of type I_{4}. There are 11 BC_{4} orbits with representatives:

(i) S = (a, b, c, d). Then |P O_{4}(S)| = 90 and ρ_{4}(B_{4}) = S_{90}. (ii) S = (a, b, c, babcdcbab). Then |P O_{4}(S)| = 10 and ρ(B_{4}) = S_{10}. (iii) S = (a, b, c, dcbabcdcbabcd). Then |P O_{4}(S)| = 160 and ρ_{4}(B_{4}) = A_{160}. (iv) S = (a, b, c, dcababcdcbabacd). Then |P O_{4}(S)| = 135 and ρ_{4}(B_{4}) = S_{135}.

(v) S = (a, b, c, dcbabcababcdcbabacbabcd). Then |P O_{4}(S)| = 288. The action is not primitive and has a unique block system with blocks of size two. The action on the 144 blocks gives a representation of B_{4} onto A_{144}. (vi) S = (a, b, c, babcdcbabacbabcdcbabcababcdcbab). Then |P O_{4}(S)| = 90. The action is not primitive and has a unique block system with blocks of size two. The action on the 45 blocks gives a representation of B_{4} onto S_{45}. The kernel of the action on the blocks is ℤ_{2}^{44}.

(vii) S = (a, b, acbabca, badcbabcdab). Then |P O_{4}(S)| = 18. The action is not primitive and has a unique block system with blocks of size two. The action on the 9 blocks gives a representation of B_{4} onto A_{9}. The kernel of the action on the blocks is ℤ_{2}^{9}. (viii) S = (a, b, d, cbabacbadcbabcdabcababc). Then |P O_{4}(S)| = 160 and ρ_{4}(B_{4}) = A_{160}. (ix) S = (a, b, cbabc, cdcbabacbabcdcbabcababcdc). Then |P O_{4}(S)| = 135 and ρ_{4}(B_{4}) = S_{135}.

(x) S = (a, c, dcbabcd, babacbabcdcbabcabab). Then |P O_{4}(S)| = 90 and ρ_{4}(B_{4}) = S_{90}. (xi) S = (a, c, babcbab, ababcdcbabacbabcdcbabcababcdcbaba). Then |P O_{4}(S)| = 10 and ρ_{4}(B_{4}) = S_{10}.

(F_{4}) Let G =< a, b, c, d|a^{2}, b^{2}, c^{2}, d^{2}, (ab)^{3}, (bc)^{4}, (ac)^{2}, (ad)^{2}, (bd)^{2}, (cd)^{3} > be of type F_{4}. There are two BC_{4} orbits with the following representatives:

(i) S = (a, b, c, d). Then |P O_{4}(S)| = 72 and ρ_{4}(B_{4}) is not primitive. (ii) S = (a, b, c, bcdcb). Then |P O_{4}(S)| = 18 and ρ_{4}(B_{4}) is not primitive.

(E_{6}) Let G = < a, b, c, d, e, f|a^{2}, b^{2}, c^{2}, d^{2}, e^{2}, f^{2}, (ab)^{3}, (bc)^{3}, (ac)^{2}, (ad)^{2}, (bd)^{2}, (cd)^{3}, (ae)^{2}, (af)^{2}, (be)^{2}, (bf)^{2}, (ce)^{2}, (cf)^{3}, (de)^{3}, (df)^{2}, (ef)^{2} > be of type E_{6}. There are three BC_{6} orbits:

(i) S = (a, b, c, d, e, f). Then |P O_{6}(S)| = 3456 and ρ_{6}(B_{6}) = A_{3456}. (ii) S = (a, b, c, d, e, cfabcdedcbafc). Then |P O_{6}(S)| = 1080 and ρ_{6}(B_{6}) = A_{1080}. (iii) S = (a, b, c, d, e, bacbedcfcdebcab). Then |P O_{6}(S)| = 6561 = 3^{8} and ρ_{6}(B_{6}) = A_{6561}.

(E_{7}) Let G = < a, b, c, d, e, f, g|a^{2}, b^{2}, c^{2}, d^{2}, e^{2}, f^{2}, g^{2}, (ab)^{3}, (bc)^{3}, (ac)^{2}, (ad)^{2}, (bd)^{2}, (cd)^{3}, (ae)^{2}, (af)^{2}, (be)^{2}, (bf)^{2}, (ce)^{2}, (cf)^{3}, (de)^{3}, (df)^{2}, (ef)^{2}, (ag)^{2}, (bg)^{2}, (cg)^{2}, (dg)^{2}, (eg)^{3}, (fg)^{2} > be of type E_{7}. There are five BC_{7} orbits with the following representatives :

(i) (a, b, c, d, e, f, g); (ii) (a, b, c, d, e, f, cdegedc); (iii) (a, b, c, d, e, f, cbfcdegedcfbc); (iv) (a, b, c, d, e, deged, cbdcgcdbc); (v) (a, b, c, d, e, bdcfcdb, cbfcdegedcfbc).

(E_{8}) Let G = < a, b, c, d, e, f, g, h > be of type E_{8} (relations as for E_{7}, with the only non-commutator relation involving h being (gh)^{3}). The following represent nine different BC_{8} classes, with non-conjugate Coxeter elements:

(i) (a, b, c, d, e, f, g, h); (ii) (a, b, c, d, e, f, g, cdeghgedc); (iii) (a, b, c, d, e, f, g, cbfcdeghgedcfbc); (iv)(a, b, c, d, e, f, g, efcbadcbfcdeghgedcfbcdabcfe);

(v) (a, b, c, d, e, f, adcbfcdeghgedcfbcda, h); (vi)(a, b, c, d, e, f, cbfcdeghgedcfbc, cdegedc); (vii) (a, b, c, d, e, f, adcbfcdeghgedcfbcda, cbfcdegedcfbc); (xiii) (a, b, c, d, e, gedcbfcdeghgedcfbcdeg, bdcfcdb, g); (ix) (d, c, e, b, bdcfcdb, defcbadcbfcdeghgedcfbcdabcfed, acbdcfcdbca, ege).

§2 The n odd case

In this section we prove Theorem 1.1 in the case where n ≥ 3 is odd.

Since v_{1}, v_{2}, …, v_{n} are linearly independent we may use them as a basis; relative to this basis we see that each r_{i} = r_{v_{i}} has the following form:

r_{i} = ( \begin{matrix}1 & 0 & … & 0 & … & 0 & 0 \\ 0 & 1 & … & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ... & ⋮ & … & ⋮ & ⋮ \\ a_{i1} & a_{i2} & … & −1 & … & a_{in−1} & a_{in} \\ ⋮ & ⋮ & … & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & … & 0 & … & 1 & 0 \\ 0 & 0 & … & 0 & … & 0 & 1 \end{matrix} ) .  (2.1)

Here a_{ij} = −2(v_{i}, v_{j}) = −2cosθ_{ij} and the non-zero off-diagonal entries of r_{i} occur in the ith row.

Given any sequence S = (r_{1}, r_{2}, …, r_{n}) of reflections in GL(n, ℝ) we define the graph Γ(S) to have n vertices w_{i} and an edge from w_{i} to w_{j} if r_{i} and r_{j} do not commute. We will assume that the graph Γ(S) is connected, this condition corresponding to the irreducibility of the group W =< S > [Hu].

Lemma 2.1. (i) For 1 ≤ i < j ≤ n there is α ∈ B_{n} such that α(r_{1}, …, r_{n}) = (…, r_{i}, r_{j}, …) (with r_{i} occurring in the ith position and r_{j} in the (i + 1)th position). (ii) For 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n there is α ∈ B_{n} such that

α(r_{1}, …, r_{n}) = (… r_{i_{1}}, r_{i_{2}}, …, r_{i_{k}} …).

(with r_{i_{1}} occurring in the i_{1}th position and then r_{i_{1}}, r_{i_{2}}, r_{i_{3}}, … occurring consecutively). (iii) For 1 ≤ i_{1} < i_{2} < ⋯ < i_{k} ≤ n and 1 ≤ t ≤ n − r + 1 there is α ∈ B_{n} such that

α(r_{1}, …, r_{n}) = (…, r_{i_{1}}, r_{i_{2}}, …, r_{i_{k}}, …).

(with r_{i_{1}} occurring in the tth position). (iv) For all (g_{1}, g_{2}, …, g_{n}) ∈ W^{n} we have

σ_{1}σ_{2} … σ_{n−1}(g_{1}, g_{2}, …, g_{n}) = g_{n}^{−1}(g_{n}, g_{1}, g_{2}, …, g_{n−1})g_{n}.

Proof. (i) Since σ_{j}(r_{1}, r_{2}, …, r_{n}) = (r_{1}, …, r_{j−1}, r_{j+1}, r_{j}^{r_{j+1}}, r_{j+2}, …, r_{n}), we can move r_{j} one position closer to r_{i}. Repeating this gives (i) and repeating (i) gives (ii). Now (iii) follows since we can first assume that we have (ii) and then move this sequence of elements up or down. For example the braid σ_{n−1} … σ_{i_{1}+1}σ_{i_{1}}σ_{i_{1}−1} moves the sequence down by one. Lastly, (iv) is proved by induction on n. □

Lemma 2.2. For 1 ≤ i ≠ j ≤ n, each θ_{ij} is a rational multiple of 2π.

Proof. Relative to the basis v_{i}, v_{j} the reflections r_{i} and r_{j} are represented as

( \begin{matrix}−1 & 0 \\ a_{ij} & 1 \end{matrix} ) , ( \begin{matrix}1 & a_{ij} \\ 0 & −1 \end{matrix} ) ,

(respectively), with a_{ij} = −2cos(θ_{ij}). Now by Lemma 2.1 (i) we may assume that j = i + 1. Now note that σ_{i}^{2k}(r_{i}) = (r_{i}r_{i+1})^{k}r_{i}(r_{i}r_{i+1})^{−k} is a reflection corresponding to the vector (r_{i}r_{i+1})^{k}(v_{i}) and that σ_{i}^{2k}(r_{i+1}) = (r_{i}r_{i+1})^{k}r_{i+1}(r_{i}r_{i+1})^{−k} is the reflection corresponding to the vector (r_{i}r_{i+1})^{k}(v_{i+1}).

We note that r_{i}r_{i+1} is a rotation by angle 2θ_{ii+1}. Thus if r_{i}r_{i+1} has infinite order, then the fact that v_{i}, v_{i+1} are linearly independent means that there are infinitely many of the vectors {(r_{i}r_{i+1})^{k}(v_{i}), (r_{i}r_{i+1})^{k}(v_{i+1})}_{k}, contradicting the fact that the B_{n} orbit is finite. □

Thus we may modify the graph Γ(S), S = (r_{1}, …, r_{n}), by attaching to the edge between the ith and the jth vertex the label m where r_{i}r_{j} has order m. Let Γ(S)_{ij} denote this number.

Proposition 2.3. Assume that Γ(S) is connected, that |S| > 1 is odd and that the B_{n} orbit of S is finite. Then < S > is an irreducible finite reflection group.

Proof. Suppose that S = (r_{1}, …, r_{n}). Then Π(S) = r_{1}r_{2} … r_{n}. We will need a result of Howlett [Ho]. Recall that a Coxeter group is a group having a presentation of the form < x_{1}, …, x_{n}|x_{i}^{2}, (x_{i}x_{j})^{m_{ij}}, 1 ≤ i ≠ j ≤ n >. Here, if we put m_{ii} = 1 for all i ≤ n, the matrix (m_{ij}) is a symmetric with entries in {1, 2, 3, … ∞}. Howlett’s result says that an arbitrary Coxeter group is finite if and only if the Coxeter element x_{1}x_{2} … x_{n} is of finite order. Now the group < S > is a quotient of a Coxeter group. Thus we see that < S > is finite if and only if Π(S) has finite order. We will now show that Π(S) has finite order.

Let Δ^{2} = (σ_{1}σ_{2} … σ_{n−1})^{n} ∈ B_{n}. Then by Lemma 2.1 (iv) we have

Δ^{2k}(r_{1}, …, r_{n}) = Π(S)^{k}(r_{1}, …, r_{n})Π(S)^{−k}

for all k ∈ ℤ. Since we are assuming that the B_{n}-orbit of S is finite we see that there must be some N ∈ ℕ such that

Π(S)^{N}r_{i}Π(S)^{−N} = r_{i}

for all 1 ≤ i ≤ n. We may assume that N is even. This shows that Π(S) must belong to the centre of < S >. But since Γ(S) is connected it follows that < S > is irreducible [Hu] and so Π(S) must be a scalar matrix (by Schur’s lemma). The next result shows that, since n is odd, Π(S)^{2} has 1 as an eigenvalue and since N is even we see that the diagonal matrix Π(S)^{N} must be the identity. Thus Π(S)^{2} has finite order. We now show that Π(S)^{2} has 1 as an eigenvalue. In fact we will show that Π(S) has −1 as an eigenvalue.

If M is an n × n matrix, then by M_{ij} we mean the matrix obtained from M by deleting the ith row and the jth column.

Recall [A] that if M = (m_{ij}) is an n × n antisymmetric matrix with n even, then there is an integral polynomial P = P (m_{ij}) such that det(M) = P^{2}. Now let M = (m_{ij}) be an n × n antisymmetric matrix with n odd. Then for each 1 ≤ i ≤ n there are integer polynomials p_{i}(m_{rs}) such that det(M_{ii}) = p_{i}^{2}. The polynomials p_{i} are clearly determined up to sign. However we will need to assume that for α ∈ S_{n} we have p_{α(1)} = α(p_{1}) and that in p_{1} the coefficient of m_{23}m_{45} … m_{n−1n} is 1. This now determines the p_{i} uniquely. We will call p_{i} = p_{i}(M) the ith Pfaffian of M.

In the next few results we will assume that the a_{ij} are algebraically independent over ℚ (any other case is just a quotient of this case). So we fix S with (2.1) giving the action of the reflections and defining the a_{ij}. Let M = (a_{ij}) be the n × n antisymmetric matrix

M = ( \begin{matrix}0 & a_{12} & a_{13} & … \\ −a_{12} & 0 & a_{23} & … \\ −a_{13} & −a_{23} & 0 & … \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} ) .

It suffices now to prove:

Lemma 2.4. Suppose that n > 1 is odd. Then Π(S) has −1 as an eigenvalue. The corresponding eigenvector is

(p_{1}, −p_{2}, p_{3}, −p_{4}, …, p_{n})^{T} ,

where p_{i} is the ith Pfaffian of M.

Proof. We will need the following result, where adj(M) is the classical adjoint matrix of M:

Lemma 2.5. Let M = (a_{ij}) be the antisymmetric n × n matrix defined above, where n is odd. Then

adj(M) = (p_{1}, −p_{2}, …, −p_{n})^{T} (p_{1}, −p_{2}, …, −p_{n}).

Proof. Recall that for any n × n matrix M we have rank(adj(M)) = n, 1, 0 depending on whether rank(M) = n, n − 1, r < n − 1. Since n is odd and M is a generic anti-symmetric matrix we have det(M) = 0, rank(M) = n − 1 and so we see that adj(M) is a rank 1 matrix and so has the form v^{T} w for some n-vectors v, w. Now we note that the i, i entry of adj(M) is the determinant of the matrix M_{ii}. This is p_{i}^{2}.

Next note that since M is antisymmetric and n is odd, then adj(M) is a symmetric matrix. Let v = (v_{1}, …, v_{n}), w = (w_{1}, …, w_{n}). Then adj(M)_{ii} = p_{i}^{2} implies that v_{i}, w_{i} ≠ 0. Now v, w are determined up to a scalar multiple and so we may scale so that v_{1} = p_{1}. Then we have v_{1}w_{1} = p_{1}^{2} and so w_{1} = p_{1}. Now for 1 < i ≤ n we have p_{1}w_{i} = v_{1}w_{i} = v_{i}w_{1} = v_{i}p_{1} and so w_{i} = v_{i}. We also have p_{i}^{2} = w_{i}v_{i} = v_{i}^{2}, showing that v_{i} = w_{i} = ±p_{i} for all 1 < i ≤ n. It remains to determine the sign. This we do by looking at the sign of some monomials occurring in the p_{i}.

Now p_{1} has the term m_{23}m_{45} … m_{n−1n} and p_{2} has the term m_{13}m_{45} … m_{n−1n}. But in det(M_{1,2}) the term m_{23}m_{13}(m_{45} … m_{n−1n})^{2} occurs and so in adj(M) the 1, 2 entry contains −m_{23}m_{13}(m_{45} … m_{n−1n})^{2}. Thus v = (p_{1}, −p_{2}, …) and the rest follows similarly. □

Since Madj(M) = det(M)I_{n}, where I_{n} denotes the identity matrix if rank n, we now see that

M(p_{1}, −p_{2}, p_{3}, …, −p_{n})^{T} = 0.

In particular for each 1 ≤ r ≤ n we have

∑_{i=1}^{r−1} −a_{ir}(−1)^{i+1}p_{i} + ∑_{i=r+1}^{n} a_{ri}(−1)^{i+1}p_{i} = 0.  (2.2)

Let I_{nk}, 1 ≤ k ≤ n, be the n × n diagonal matrix diag(1, 1, …, 1, −1, −1, …, −1) where there are n + 1 − k of the −1s. Then I_{nn+1} = I_{n} and we have

Lemma 2.6. Let n > 1 be odd. Let r_{i} be given by (2.1) and let p_{i} = p_{i}(M) denote the Pfaffians as constructed above and let P = (p_{1}, −p_{2}, p_{3}, …, p_{n})^{T}. Then for all 1 ≤ k ≤ n we have

r_{k}I_{nk+1}P = I_{nk}P.

In particular we have r_{1}r_{2} … r_{n}(P) = −P.

Proof. The last statement follows from the first since I_{nn+1} = I_{n}, I_{n1} = −I_{n} and

r_{1} … r_{n−2}r_{n−1}r_{n}(P) = r_{1} … r_{n−2}r_{n−1}r_{n}I_{n+1}(P)
= r_{1} … r_{n−2}r_{n−1}I_{nn}(P)
= r_{1} … r_{n−2}I_{nn−1}(P)
= ⋯ = I_{n1}P = −P.

The first statement is proved as follows. Let J_{i} be the n × n diagonal matrix

J_{i} = diag(1, …, 1, −1, 1, …, 1),

with the −1 in the ith position. Thus I_{nk} = J_{k}I_{nk+1}. Now r_{i} = J_{i} + K_{i} defines the matrix K_{i} and we have K_{i}I_{ni+1}P = 0 by (2.2). Thus

r_{k}I_{nk}(P) = (J_{k} + K_{k})I_{nk}(P)
= I_{nk−1}(P),

as required. □

As explained above, this now completes the proof of Proposition 2.3 and of Theorem 1.1 if n is odd. □

Proposition 2.7. Suppose that W is an irreducible finite reflection group generated by a set of reflections S. Then for s, s′ ∈ S, s ≠ s′, the order of ss′ is one of 2, 3, 4, 5.

If |S| ≥ 5, then for s, s′ ∈ S, s ≠ s′ the order of ss′ is one of 2, 3, 4.

Proof. This follows from the classification of irreducible finite reflection groups [GB] by considering each case separately:

If W has type A_{n}, then W = S_{n+1} and the reflections are the transpositions (ij) and if (ij) ≠ (rs), the order of (ij)(rs) is 2 or 3.

If W has type B_{n}, then W is the group of signed permutations and the reflections are the transpositions (ij) and the elements ϵ_{i}, i = 1, …, n, where ϵ_{i}(i) = −i, ϵ_{i}(j) = j, j ≠ i. One finds that the orders are 2, 3 or 4.

When W has type D_{n}, then W is a subgroup of the B_{n} case and so this case follows from the last.

The remaining cases I_{3}, I_{4}, E_{6}, E_{7}, E_{8} are each checked using MAGMA [MA]; the orders for I_{3}, I_{4} are 2, 3, 5, while those for E_{6}, E_{7}, E_{8} are 2, 3. □

Corollary 2.8. Suppose that n ≥ 3 and that Γ(S) is connected. Then each Γ(S)_{ij} is in the set {2, 3, 4, 5}. If n ≥ 5 and Γ(S) is connected, then each Γ(S)_{ij} is in the set {2, 3, 4}.

Proof. Since n ≥ 3 and Γ(S) is connected, any edge of Γ(S) is in a full subgraph of Γ(S) which has three vertices and is connected. The first result now follows from Lemma 2.1 together with Proposition 2.7. The second follows likewise by considering connected subgraphs with 5 vertices. □

§3 Braid groups and finite reflection groups

Recall [GB] that given an irreducible finite reflection group W =< S >, S = (r_{1}, …, r_{n}), r_{i} = r_{v_{i}}, v_{i} ∈ ℝ^{n}, the set of roots is the set of all images of the elements of v_{1}, …, v_{n} under W; this is denoted by Δ. We will let R(Δ) denote the set of all reflections in W. Further, we may partition Δ = Δ^{+} ∪ Δ^{−} so that −Δ^{−} = Δ^{+}. Then a base is a subset Π ⊂ Δ such that Π is a basis for ℝ^{n} and such that for v ∈ Δ^{+} the coordinates of v relative to Π are all positive.

In this section we prove Theorem 1.2. This will be by a case-by-case analysis. In each case we will use a standard description of the finite reflection groups as a group of permutations; see [GB, §5.3] for example.

First consider type A_{n}. Here W ≅ S_{n+1} and we may take R(Δ) to be the set of transpositions in S_{n+1}. So we will deal with sequences T = (t_{1}, …, t_{n}) of such transpositions. To such a sequence T we associate a graph Γ(T) with vertices 1, 2, …, n + 1 and with an edge {i, j}, j ≠ i if (i, j) ∈ {t_{1}, …, t_{n}}. For type A_{n} any base corresponds to a T such that Γ(T) is a line graph (a line graph being a graph isomorphic to Γ(((1, 2), (2, 3), …, (k, k + 1)))) for some k. Thus we need to show that for any T as above there is α ∈ B_{n} such that Γ(α(T)) is a line graph.

In any case we note that Γ(T) is a graph with n + 1 vertices and n edges, which is connected since < T >= S_{n+1}, and so must be a tree. Conversely, we note that if T is a sequence of n transpositions such that Γ(T) is connected, then < T >= S_{n+1}. For the hypothesis here easily shows that < T > is a transitive subgroup of S_{n+1} and any transitive subgroup of S_{n+1} containing a transposition is S_{n+1}.

Now for T = (t_{1}, …, t_{n}) we let Γ^{∗}(T) denote the graph Γ(T) only where we label the edge {r, s} by i if t_{i} = (r, s). The proof will now consist of various steps. If i ≤ n and K is a subgraph of Γ^{∗}(S), then we will let K_{i} denote the edge of K that is labeled i. An edge is free if it is adjacent to no more than one other edge.

In Figure 2 we indicate how the generators σ_{k}^{±1} act on the graphs Γ^{∗}(T). In Figure 2 (i) we give the case where the edges labeled k and k + 1 are disjoint. In Figure 2 (ii), (iii) we give the action of σ_{k}^{±1} in the case where these edges are adjacent in Γ^{∗}(T).

Figure 2.

In the following we will think of edges of Γ(S) as being given by pairs {i, j} of their vertices. Thus, as in the next result, it makes sense to think of an edge as belonging to both Γ(S) and to Γ(α(S)) for α ∈ B_{n}.

Lemma 3.1. Suppose that L is a line subgraph of Γ^{∗}(T) with free edges e_{i} = Γ^{∗}(T)_{i}, e_{j} = Γ^{∗}(T)_{j}, j ≥ i. Let v ∈ e_{j} be an end vertex of L. Let W be the union of the closures of the connected components of Γ^{∗}(T) \ L that contain v and suppose that if k < i, then e_{k} is in W. Then there is α ∈ B_{n} such that Γ^{∗}(α(T))_{i} contains the vertex v and Γ^{∗}(α(T))_{r} = e_{r} for every r < i.

Proof. We will be inducting on q, the number of edges of L. If q = 1, then i = j and we are done (take α = id); so assume inductively that q > 1.

Let e_{m} = Γ^{∗}(T)_{m} be the unique edge of L which is adjacent to e_{i}. Then by hypothesis m > i. We now show how to reduce to the case where m = i + 1. If we have m = i + 1, then we act by σ_{i}^{−1} and we have reduced q by 1 (see Figure 2).

To reduce to the case m = i + 1 we assume that m > i + 1 and consider four cases:

a) Γ^{∗}(T)_{m} and Γ^{∗}(T)_{m−1} are disjoint;

b) not a) and Γ^{∗}(T)_{m−1} is an edge of L;

c) not a), not b), and all of Γ^{∗}(T)_{i}, Γ^{∗}(T)_{m}, Γ^{∗}(T)_{m−1} share a vertex;

d) Γ^{∗}(T)_{i} and Γ^{∗}(T)_{m−1} are disjoint, but Γ^{∗}(T)_{m} and Γ^{∗}(T)_{m−1} share a vertex. If a), then σ_{m−1} has the effect of interchanging the labels on Γ^{∗}(T)_{m} and Γ^{∗}(T)_{m−1}; thus

we are done in this case.

If b), then we do σ_{m−1}^{−1}, which actually reduces the length of a line graph between Γ^{∗}(T)_{i} and Γ^{∗}(T)_{j}.

For c) or d) we likewise do σ_{m−1}^{−1}. This proves Lemma 3.1. □

Now we describe the various steps in the proof of Theorem 1.2 in the A_{n} case: Step 1: Find α ∈ B_{n} such that Γ^{∗}(αT)_{1} is a free edge of the tree Γ^{∗}(αT).

If Γ^{∗}(T)_{1} is already a free edge then we are done. If not, then let L ⊂ Γ^{∗}(T) be a line graph whose free edges are Γ^{∗}(T)_{1} and a free edge of Γ^{∗}(T). Using Lemma 3.1 we can find α ∈ B_{n} such that Γ^{∗}(αT)_{1} is a free edge of Γ^{∗}(αT).

We now assume that Γ^{∗}(T) satisfies Step 1. Step 2: Find α ∈ B_{n} such that Γ^{∗}(αT)_{1} = Γ^{∗}(T)_{1} is a free edge of Γ^{∗}(αT) and Γ^{∗}(αT)_{2} is adjacent to Γ^{∗}(αT)_{1}.

If Γ^{∗}(T)_{2} is already adjacent to Γ^{∗}(T)_{1}, then we are done. If not, then let L_{1} be a line graph having Γ^{∗}(T)_{1} and Γ^{∗}(T)_{2} as its free edges and let L be the line graph L_{1} \ Γ^{∗}(T)_{1}. An application of Lemma 3.1 shows that there is α ∈ B_{n} which fixes Γ^{∗}(T)_{1} and such that Γ^{∗}(αT)_{2} is adjacent to Γ^{∗}(αT)_{1} = Γ^{∗}(T)_{1}, as required.

We now assume that Γ^{∗}(T) satisfies Step 1 and Step 2. Step 3: This is an inductive step. Let us assume that Γ^{∗}(T)_{1} is a free edge of Γ^{∗}(T) and that L′ is a line graph with edges Γ^{∗}(T)_{1}, Γ^{∗}(T)_{2}, …, Γ^{∗}(T)_{k}, k ≥ 2. This step will consist of showing that we can increase k (if k < n + 1). To simplify notation we may, by a conjugacy, also assume that T = (t_{1}, …, t_{n}) where t_{i} = (ii + 1) for i ≤ k so that Γ^{∗}(T)_{i} has vertices v_{i}, v_{i+1}.

Now let L be a line subgraph of Γ^{∗}(T) \ L′ such that one free edge is Γ^{∗}(T)_{k+1}, while the end vertex at the other end of L is v_{r+1} for some r ≤ k. Let Γ^{∗}(T)_{s} be the edge of L with end vertex v_{r+1} in it. Then we must have s ≥ k + 1 and so we can apply Lemma 3.1 to find α ∈ B_{n} such that α fixes L′ but Γ^{∗}(αT)_{k+1} is now adjacent to v_{r+1}.

If r = k, then we are done. So we assume that r < k.

We now consider the graph L′ ∪ Γ^{∗}(αT)_{k+1}. This graph has edges labeled 1, 2, …, r, r + 1, r + 2, …, k − 1, k, k + 1. Now if we do σ_{r+2} … σ_{k−1}σ_{k}, then the edges will now be labeled 1, 2, …, r, r + 1, r + 3, …, k, k + 1, r + 2 (respectively). Now we act by σ_{r+1} and we are done since the image of the graph L′ ∪ Γ^{∗}(αT_{k+1}) is now a line graph with edges labeled 1, 2, …, k + 1.

We illustrate the above in Figure 3, for the case r = k − 3.

Figure 3.

This completes the proof of Theorem 1.2 for the A_{n} case.

The next case is W (B_{n}). Here W (B_{n}) is the group of all signed permutations of ±1, ±2, …, ±n and the reflections are in two conjugacy classes. We define y_{1} = 1, y_{2} = 2, …, y_{n} = n, y_{n+1} = −1, y_{n+2} = −2, …, y_{2n} = −n, and let

γ_{i} = (y_{i}, y_{n+i}), β_{ij} = (y_{i}, y_{j})(y_{n+i}, y_{n+j}), for 1 ≤ i ≠ j ≤ n.

Any conjugate of γ_{i} is some γ_{j}, while if we let β_{ij}^{+} = β_{ij} and β_{ij}^{−} = γ_{i}β_{ij}γ_{i} = γ_{j}β_{ij}γ_{j}, then any W (B_{n})-conjugate of some β_{ij}^{±} is some β_{rs}^{±}. We also have γ_{i}β_{rs}γ_{i} = β_{rs} if i ≠ r, s. The reflections are thus the γ_{i}, 1 ≤ i ≤ n and the β_{ij}^{±} where we may assume that ≤ i < j ≤ n.

The standard set of generators for W (B_{n}) is the sequence (γ_{1}, β_{12}, β_{23}, …, β_{n−1n}). Now let (δ_{1}, δ_{2}, …, δ_{n}) be a set of reflection generators so that δ_{i} ∈ {γ_{1}, …, γ_{n}, β_{12}^{+}, …, β_{n−1n}^{+}, β_{12}^{−}, …, β_{n−1n}^{−}}. Let π = π_{n} : W (B_{n}) → S_{n} be the projection so that π(γ_{i}) = id, π(β_{ij}) = (ij). Since n − 1 is the smallest number of transpositions that S_{n} can be generated by we see that n − 1 of the δ_{i} must be of the form β_{ij}^{±}, with the other being one of the γ_{i}. Thus we may now assume (Lemma 2.1) that (up to an action of the braid group B_{n}) we have δ_{1} = γ_{i}, i ≤ n and δ_{k} ∈ {β_{ij}^{ϵ}} for k ≥ 2 and ϵ = ±.

Now we must have < π(δ_{2}), …, π(δ_{n}) >= S_{n} and so from the W (A_{n−1}) ≅ S_{n} case proved above we see that there is α ∈< σ_{2}, …, σ_{n−1} >⊂ B_{n} such that

α(δ_{1}, …, δ_{n}) = (γ_{i}, β_{u_{1}u_{2}}^{ϵ_{1}}, β_{u_{2}u_{3}}^{ϵ_{2}}, …, β_{u_{n−1}u_{n}}^{ϵ_{n−1}}).

Here u_{j} ≤ n are distinct and ϵ_{j} = ± for all j ≤ n − 1.

We now show how to reduce the number of β_{ij}^{−}s in S = (γ_{i}, β_{u_{1}u_{2}}^{ϵ_{1}}, β_{u_{2}u_{3}}^{ϵ_{2}}, …, β_{u_{n−1}u_{n}}^{ϵ_{n−1}}). Suppose that r ≤ n − 1 is the largest such number with ϵ_{r} = −. Then we conjugate each element of S by γ_{u_{r}} and we have reduced r. Continue until all the ϵ_{k} are +. Thus we now have (γ_{i}, β_{u_{1}u_{2}}, β_{u_{2}u_{3}}, …, β_{u_{n−1}u_{n}}) and this in turn is conjugate to (γ_{i}, β_{12}, β_{23}, …, β_{n−1n}) for some i.

Let C = β_{12}β_{23} … β_{n−1n} = (1, n, n − 1, …, 3, 2). Then there is k ≤ n such that

C^{k}(γ_{i}, β_{12}, β_{23}, …, β_{n−1n})C^{−k} = (γ_{1}, C^{k}β_{12}C^{−k}, C^{k}β_{23}C^{−k}, …, C^{k}β_{n−1n}C^{−k}).

But the effect of the braid Π = (σ_{2}σ_{3} … σ_{n−1})^{n−1} on all but the first coordinate is to conjugate those coordinates by C. Further this braid fixes the first coordinate. Thus there is some m ∈ ℤ such that Π^{m}(γ_{1}, C^{k}β_{12}C^{−k}, C^{k}β_{23}C^{−k}, …, C^{k}β_{n−1n}C^{−k}) = (γ_{1}, β_{12}, β_{23}, …, β_{n−1n}), as required. This concludes the W (B_{n}) case.

Next we consider W (D_{n}), n ≥ 8. This is the subgroup of index 2 in W (B_{n}) generated by the β_{ij}^{±}. Here the reflections are the β_{ij}^{±} and the standard set of generators for W (D_{n}) is the sequence (β_{12}, β_{23}, …, β_{n−1n}, β_{n−1n}^{−}). We note that the cases n < 8 can be checked using MAGMA [MA].

Let S = (r_{1}, …, r_{n}) be a generating sequence and let π = π_{n} : W (S) → S_{n} be the epimorphism. Let S′ = π(S). Then Γ(S′) is a connected graph with exactly one cycle, which we denote by C(S′). Let q = q(S) ≤ n be maximal such that Γ(S′)_{q} is an edge of C(S′). We aim to get q = n by acting on S by an element of B_{n}. If q = n, then we are done. If q < n, then we consider two cases (showing in each case how to increase q):

(i) Γ(S′)_{q+1} is disjoint from Γ(S′)_{q}; here we act on S (and so on S′) by σ_{q} and note that q(σ_{q}(S)) = q + 1. (ii) If Γ(S′)_{q+1} is adjacent to Γ(S′)_{q}, then Γ(S′)_{q+1} cannot be an edge of Γ(S′) by the maximality of q. We then check that q(σ_{q}(S)) > q(S).

By the above we may assume that q(S) = n. Thus Γ(π(r_{1}, …, r_{n−1})) is a tree. From the A_{n−1} case considered above we see that there is α ∈ B_{n−1} < B_{n} such that π(α(r_{1}, …, r_{n−1})) is conjugate to (β_{12}, β_{23}, …, β_{n−1n}); so we may assume that πS = (β_{12}, β_{23}, …, β_{n−1n}, β_{rs}) and thus S = (β_{12}^{ϵ_{1}}, β_{23}^{ϵ_{2}}, …, β_{n−1n}^{ϵ_{n−1}}, β_{rs}^{ϵ_{n}}).

Now the element (σ_{1} … σ_{n−2})^{n−1} has the effect of conjugating the first n − 1 of the elements of S by β_{12}^{ϵ_{1}}β_{23}^{ϵ_{2}} … β_{n−1n}^{ϵ_{n−1}}. Doing this (up to conjugacy) has the effect of acting on the indices r, s by (1, n, n − 1, n − 2, …, 3, 2) and so we may assume that r < s = n. Thus we now have S = (β_{12}^{ϵ_{1}}, β_{23}^{ϵ_{2}}, …, β_{n−1n}^{ϵ_{n−1}}, β_{rn}^{ϵ_{n}}).

Now suppose that ϵ_{i} = − and that this choice of i is minimal. Assume that i < n − 1. Then γ_{i}γ_{i+2} ∈ W (D_{n}) and if we conjugate by γ_{i}γ_{i+2}, then we have increased i. Thus we may assume that we have S = (β_{12}, β_{23}, …, β_{n−2,n−1}, β_{n−1n}^{ϵ_{n−1}}, β_{rn}^{ϵ_{n}}) and we note that at least one of ϵ_{n−1}, ϵ_{n} is −, otherwise S just generates a symmetric group.

We also note that if r = n − 1, then ϵ_{n−1} ≠ ϵ_{n} (else r_{n−1} = r_{n}) and so we have a base. If r < n − 1 and ϵ_{n−1} = − = ϵ_{n}, then we conjugate by γ_{n} and see that we have

S = (β_{12}, β_{23}, …, β_{n−2,n−1}, β_{n−1n}, β_{rn}) which generates a subgroup of S_{n} i.e. a proper subgroup of D_{n}. Thus we must have ϵ_{n−1} ≠ ϵ_{n}.

Now if r = 1, then using the action of a power of (σ_{1}σ_{2} … σ_{n−1})^{n} together with conjugation we see that this case is equivalent to the case r = n − 1. Thus we may now assume that 1 < r ≤ n − 1 and that ϵ_{n−1} ≠ ϵ_{n}.

Next we show that S_{1} = (β_{12}, β_{23}, …, β_{n−2,n−1}, β_{n−1n}^{−}, β_{rn}) and S_{2} = (β_{12}, β_{23}, …, β_{n−2,n−1}, β_{n−1n}, β_{rn}^{−}) are equivalent. This is accomplished by first acting on S_{2} by α = σ_{n−1}^{−1}σ_{n−2}^{−1} … σ_{r}^{−1} and noting that the result is conjugate to S_{1}. Thus we may assume that we have S_{2} for some value of 1 < r < n. We let S(r) = (β_{12}, β_{23}, …, β_{n−2,n−1}, β_{n−1n}, β_{rn}^{−}).

Lastly we show that each of the S(r) are inequivalent. This will follow from the fact that the products P (r) = β_{12}β_{23} … β_{n−2,n−1}β_{n−1n}β_{rn}^{−} are pair-wise non-conjugate for 1 < r < n. To see this we note that P (r) is a product of two cycles, one being of length r and containing no −1s, the other of length n − r with some −1s. This is enough to guarantee that the P (r) are pair-wise non-conjugate. There are thus n − 2 possibilities. This concludes the W (D_{n}) case.

The remaining cases (I_{3}, I_{4}, F_{4}, E_{6}, E_{7}, E_{8}) are each checked using MAGMA [MA].

We now indicate the reflection matrices that generate the BC_{n}-classes listed in Theorem 1.2.

For A_{n} we have

M(A_{n}) = ( \begin{matrix}2 & −1 & 0 & 0 & 0 & … & 0 & 0 \\ −1 & 2 & −1 & 0 & 0 & … & 0 & 0 \\ 0 & −1 & 2 & −1 & 0 & … & 0 & 0 \\ 0 & 0 & −1 & 2 & −1 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & 0 & … & 2 & −1 \\ 0 & 0 & 0 & 0 & 0 & … & −1 & 2 \end{matrix} ) .  (3.1)

Then the reflections s_{1}, …, s_{n} ∈ S are represented by the matrices m_{1}, …, m_{n} where m_{i} is equal to the identity except in the ith row which is equal to the ith row of M(A_{n}), except that the ii entry is −1.

For type B_{n} we have

M(B_{n}) = ( \begin{matrix}2 & −1 & 0 & 0 & 0 & … & 0 & 0 & 0 \\ −1 & 2 & −1 & 0 & 0 & … & 0 & 0 & 0 \\ 0 & −1 & 2 & −1 & 0 & … & 0 & 0 & 0 \\ 0 & 0 & −1 & 2 & −1 & … & 0 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & 0 & … & 2 & −1 & 0 \\ 0 & 0 & 0 & 0 & 0 & … & −1 & 2 & −\sqrt{2} \\ 0 & 0 & 0 & 0 & 0 & … & 0 & −\sqrt{2} & 2 \end{matrix} ) .  (3.2)

The reflections in this case are defined as in the A_{n} case.

For type D_{n} we have n − 2 cases indexed by 1 < r < n − 1:

M_{r}(D_{n}) = ( \begin{matrix}2 & −1 & 0 & 0 & 0 & 0 & … & 0 & 0 \\ −1 & 2 & −1 & 0 & 0 & 0 & … & 0 & 0 \\ 0 & −1 & 2 & −1 & 0 & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ... & ... & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & … & −1 & 2 & −1 & 0 & … & 0 & (−1)^{n+r+1} \\ 0 & … & 0 & −1 & 2 & −1 & … & 0 & (−1)^{n+r+1} \\ 0 & … & 0 & 0 & −1 & 2 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & 0 & 0 & … & 2 & −1 \\ 0 & 0 & 0 & (−1)^{n+r+1} & (−1)^{n+r+1} & 0 & … & −1 & 2 \end{matrix} ) ,

(3.3)

where the two (−1)^{n+r+1}s in the nth column are in rows r − 1 and r.

One can also easily write down matrices for the cases I_{3}, I_{4}, F_{4}, E_{6}, E_{7}, E_{8} using the BC_{n} representatives given in Theorem 1.6.

§4 The n even cases

Suppose in this section that n = |S| ≥ 4 is even and that (by induction) Theorem 1.1 is true for all k < n. We may assume this since the results of §2 (the odd case) show that Theorem 1.1 is true when |S| = 3.

Further, we may assume that n > 9, since using the results of previous sections we may easily check the cases n = 4, 6, 8.

Given a sequence S = (s_{1}, …, s_{n}), s_{i} = s_{v_{i}}, ∥v_{i}∥ = 1, of generating reflections we let M(S) denote the matrix (2v_{i}.v_{j}) as in §3. Corollary 2.8 shows that the only possible entries of M(S) are 0, ±1, ±\sqrt{2}.

Lemma 4.1. Let W =< S > and assume that Γ(S) is connected. Then there is α ∈ B_{n} such that if α(S) = (s′_{1}, s′_{2}, …, s′_{n}), then Γ((s′_{1}, s′_{2}, …, s′_{n−1})) is connected.

Proof. Suppose that Γ((s_{1}, s_{2}, …, s_{n−1})) is not connected (if it is then we are done). Let I_{1} ∪ ⋯ ∪ I_{r} be the connected components of Γ((s_{1}, s_{2}, …, s_{n−1})). Then by Lemma 2.1 there is α_{1} ∈ B_{n−1} such that all of the elements of I_{1} are in positions 1, 2, …, |I_{1}| of α_{1}(S). Now since I_{1} and I_{t}, t ≠ 1 are disjoint in Γ(S) we see that ab = ba for a ∈ I_{1}, b ∈ I_{t}. Thus I_{1}, I_{2}, …, I_{r} are still the components of α_{1}(S) − {s_{n}}. We may thus repeat to get α_{2} ∈ B_{n−1} such that all of the elements of I_{1} are in positions 1, 2, …, |I_{1}| of α_{2}α_{1}(S) and all of the elements of I_{2} are in positions |I_{1}| + 1, …, |I_{1}| + |I_{2}| of α_{2}α_{1}(S). Continuing we see that there is β ∈ B_{n−1} such that the above is true and that the last |I_{r}| elements of β(s_{1}, …, s_{n−1}) are those in I_{r}. We may also assume that s_{n−1} ∈ I_{r}. Thus replacing S by β(S) and by induction we may assume that each component of Γ((s_{1}, s_{2}, …, s_{n−1})) is in standard form in the positions indicated above. In particular (see Lemma 2.1 (iv)) we may assume that Γ((I_{r} \ {s_{n−1}})) is connected. Thus if Γ(S)_{n} and Γ(S)_{n−1} are disjoint, then acting by σ_{n−1} gives the result since the action of σ_{n−1} just interchanges the labels on these edges.

If Γ(S)_{n} and Γ(S)_{n−1} are not disjoint, then acting by σ_{n−1}^{2} replaces S = (…, s_{n−1}, s_{n}) by (…, s_{n}s_{n−1}s_{n}, s_{n}s_{n−1}s_{n}s_{n−1}s_{n}) and we note that Γ(σ_{n−1}^{2}(S) \ {s_{n}s_{n−1}s_{n}s_{n−1}s_{n}}) is now connected since s_{n}s_{n−1}s_{n} does not commute with some element of each of the I_{1}, …, I_{r−1} and does not commute with s_{n}s_{n−1}s_{n}s_{n−1}s_{n} either. □

Given S = (s_{1}, …, s_{n}) we let S(1, 2, …, n − 1) = (s_{1}, …, s_{n−1}). By Lemma 4.1 we may assume that Γ(S(1, 2, …, n − 1)) is connected. Since |S(1, 2, …, n − 1)| = n − 1 is odd we see from §2 that < S(1, 2, …, n−1) > is an irreducible finite reflection group and that there is α ∈ B_{n−1} < B_{n} such that α(S(1, 2, …, n − 1)) is in one of the canonical forms determined in Theorem 1.2 and §3. We now consider each case separately. Before doing so we will need:

Lemma 4.2. Suppose that W =< S >, S = (s_{1}, s_{2}, …, s_{n}) has finite B_{n}-orbit. Then

(i) for any S′ = {t_{1}, …, t_{r}} ⊂ {s_{1}, s_{2}, …, s_{n}} we have det(t_{i}.t_{j}) ≠ 0. (ii) If Γ(S) is connected and P = s_{i}s_{i+1} … s_{i+k}, k ≥ 1, does not have finite order, then the B_{n}-orbit of S is infinite.

Proof. (i) follows since the t_{i} are linearly independent. (ii) follows from Proposition 2.3 applied to < σ_{i}, σ_{i+1}, …, σ_{i+k−1} >. □

Given a sequence S = (s_{1}, …, s_{n}), s_{i} = s_{v_{i}}, ∥v_{i}∥ = 1 of generating reflections we let M(S) denote the matrix (v_{i}.v_{j}) as in §3. By Proposition 2.7 the entries of M(S) are in the set \{0, ±1, ±\sqrt{2}\}. We let γ(S) denote the labeled graph with vertices v_{1}, …, v_{n} and with an edge between v_{i} and v_{j} if v_{i}.v_{j} ≠ 0 and with the label being v_{i}.v_{j}. THE A_{n} CASE :

First assume that Γ(S(1, …, n − 1)) is of type A_{n−1} so that by Theorem 1.2 we may assume that Γ(S(1, …, n − 1)) is a line graph with n − 1 edges. Thus the homomorphism W (S(1, …, n − 1)) → S_{n} induced by sending s_{i} to the transposition (i, i + 1) is an isomorphism. The matrix (3.1) shows what M(S(1, …, n − 1)) looks like.

We will first determine what happens if we have at least one label equal to ±\sqrt{2}.

Lemma 4.3. Assume the above set-up and that ±\sqrt{2} occurs in the last column of M(S).

(i) If there are 1 ≤ t ≠ r ≤ n − 1 such that M(S)_{tn} = ±\sqrt{2}, M(S)_{rn} = ±1, then the B_{n}-orbit of S is infinite.

(ii) If there is 1 < t < n − 1 such that M(S)_{tn} = ±\sqrt{2}, M(S)_{t−1,n} = M(S)_{t+1,n} = 0, then the B_{n}-orbit of S is infinite.

(iii) If there are 1 ≤ t < u − 1 < n − 1 such that M(S)_{tn} = ±\sqrt{2}, M(S)_{u,n} = ±\sqrt{2}, then the B_{n}-orbit of S is infinite.

(iv) If none of (i), (ii) (iii) occur, then there is 1 ≤ t < r ≤ n − 1 such that M(S)_{un} = 0 for u = 1, …, t−1; M(S)_{un} = ±\sqrt{2} for u = t, …, r and M(S)_{un} = 0 for u = r+1, …, n−1. If |t − r| > 2 or if t = r ≠ 1, n − 1, then the B_{n}-orbit of S is infinite. In all other cases < S >= W (B_{n}).

Proof. (i) Assume that |t − r| is minimal among all such choices. Assume t < r (the other case is similar). Thus we must have M(S)_{un} = 0 for all t < u < r. Further, by conjugating by diag(1, 1, …, 1, ±1) we may assume that M(S)_{tn} = \sqrt{2}. Thus if r − t > 1, then we may act by σ_{r−1}^{−1} and reduce r − t. Thus we assume r = t + 1. Now by Lemma 2.1 we can move s_{t}, s_{t+1} into the n − 2, n − 1 positions. Thus we now have

M((s_{n−2}, s_{n−1}, s_{n})) = ( \begin{matrix}2 & −1 & \sqrt{2} \\ −1 & 2 & ±1 \\ \sqrt{2} & ±1 & 2 \end{matrix} ) ,

so that

s_{n−2}s_{n−1}s_{n} = ( \begin{matrix}2 ∓ \sqrt{2} & ±\sqrt{2} & ±1 − \sqrt{2} \\ ±\sqrt{2} − 1 & 0 & ∓1 \\ \sqrt{2} & ±1 & −1 \end{matrix} ) .

One checks that this matrix has an eigenvalue greater than 1; thus we see that the < σ_{n−2}, σ_{n−1} >-orbit of (s_{n−2}, s_{n−1}, s_{n}) is infinite (Lemma 4.2).

(ii) In this situation Lemma 2.1 allows us to assume that t = n−2. Again we may assume that M(S)_{tn} = \sqrt{2}. Here P = s_{n−3}s_{n−2}s_{n−1}s_{n} has infinite order (P^{2} − I_{4} has rank 1 and all eigenvalues of P^{2} are 1) and so Lemma 4.2 gives the result.

(iii) In view of (i) and (ii) above we may assume that M(S)_{tn} = \sqrt{2} and that M(S)_{yn} = 0 for t < y < u. As in (ii), if u − t > 2, then acting by σ_{u−1} reduces u − t. Thus we may assume that u = t + 2 and then that u = n − 1 (Lemma 2.1). One calculates the products P = s_{n−3}s_{n−2}s_{n−1}s_{n} in this situation and shows that they are infinite.

(iv) The first statement follows easily since we are assuming that ±\sqrt{2} occurs in the last column of M(S). We may now conjugate so as to have M(S)_{tn} = \sqrt{2}. If M(S)_{t+1,n} = −\sqrt{2}, then one shows that the B_{n}-orbit is infinite by looking only at s_{t}, s_{t+1}, s_{n} (which one moves into the n−2, n−1, n positions). It follows similarly that we can now assume M(S)_{u,n} = \sqrt{2} for all t ≤ u ≤ r.

Now one checks that if M(S)_{u,n} = \sqrt{2} for all u = t, t + 1, t + 2, then we have an infinite < σ_{n−3}, σ_{n−2}, σ_{n−1} >-orbit (after moving s_{t}, s_{t+1}, s_{t+2} into the n−3, n−2, n−1 positions). Thus we now may assume that r = t + 1.

Now let α = (σ_{1}σ_{2} … σ_{t})(σ_{1}σ_{2} … σ_{t−1}) … (σ_{1}σ_{2})(σ_{1}). Then α(S) has matrix

( \begin{matrix}2 & −1 & −1 & −1 & … & −1 & 0 & … & 0 & −\sqrt{2} \\ −1 & 2 & −1 & −1 & … & −1 & 0 & … & 0 & 0 \\ −1 & −1 & 2 & −1 & … & −1 & 0 & … & 0 & 0 \\ −1 & −1 & −1 & 2 & … & −1 & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & … & ⋮ & ⋮ \\ −1 & −1 & −1 & −1 & … & 2 & −1 & … & ⋮ & 0 \\ 0 & 0 & 0 & 0 & … & −1 & 2 & ... & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ... & −1 & 0 \\ 0 & 0 & 0 & 0 & … & … & … & −1 & 2 & 0 \\ −\sqrt{2} & 0 & 0 & 0 & … & … & … & … & 0 & 2 \end{matrix} )  (4.1)

where the last −1 in the first row is in column t + 2. Now let β = σ_{2}σ_{3} … σ_{t}. Then the matrix of βα(S)) is

( \begin{matrix}2 & 0 & 0 & 0 & … & 0 & 0 & … & 0 & −\sqrt{2} \\ 0 & 2 & −1 & −1 & … & −1 & 0 & … & 0 & 0 \\ 0 & −1 & 2 & −1 & … & −1 & 0 & … & 0 & 0 \\ 0 & −1 & −1 & 2 & … & −1 & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & … & ⋮ & ⋮ \\ 0 & −1 & −1 & −1 & … & 2 & −1 & … & ⋮ & 0 \\ 0 & 0 & 0 & 0 & … & −1 & 2 & ... & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ... & −1 & 0 \\ 0 & 0 & 0 & 0 & … & … & … & −1 & 2 & 0 \\ −\sqrt{2} & 0 & 0 & 0 & … & … & … & … & 0 & 2 \end{matrix} )

where the last −1 in the second row is in column t + 3. Now let γ = σ_{k}^{−1} … σ_{3}^{−1}σ_{2}^{−1}. Then the matrix of γβα(S) is as in (4.1) except that now the last −1 in the first row is in column t + 1. Repeating these last steps shows that these reflections generate W (B_{n}). This concludes the proof of Lemma 4.3 and so of all cases where ±\sqrt{2} occurs. □

Now assume that only 0, ±1s occur in M(S).

Let L_{m} denote the line graph with m vertices in the order 1, 2, …, m and K_{m} the complete graph. For a graph Γ with m vertices let M(Γ) denote the m × m matrix whose ij entry is −1 if ij is an edge of Γ and is otherwise 0. If Γ_{1}, Γ_{2} are graphs with vertices v_{1}, …, v_{m} and w_{1}, …, w_{t}, then by Γ_{1} ∗Γ_{2} we mean the graph with vertices v_{1}, …, v_{m}, w_{1}, …, w_{t}, with edges those of Γ_{1}, Γ_{2} together with an edge between v_{m} and w_{1}. Thus L_{n+m} ≅ L_{n} ∗ L_{m}, for example. For r ≥ s ≥ 1 let

σ_{rs} = σ_{r}σ_{r−1} … σ_{s}; Σ_{rs} = σ_{rs}σ_{r,s−1}σ_{r,s−2} … σ_{rr}.

Now we may describe the present situation by giving the vector V (S) = (v_{i}.v_{n}), S = (r_{v_{1}}, …, r_{v_{n}}), of length n − 1 since the matrix M(s_{1}, …, s_{n−1}) is M(A_{n−1}). Here the entries of V (S) are 0, −1, 1. We will say that V(S) is finite if the corresponding group generated by reflections is finite (otherwise V (S) is infinite). Note that by Lemma 2.1 if a subsequence of V (S) is infinite, then V (S) is infinite. We also note that V (S) ≠ (0, …, 0) as we are assuming that < S > is irreducible. By conjugating by diag(1, 1, …, 1, ±1) (if necessary) we may assume that the first non-zero entry of V (S) is −1. We define λ(S) to be the number of non-zero entries in V (S). We define an equivalence relation on 1, …, n − 1; this is generated by having i and i + 1 related if v_{i}.v_{n} and v_{i+1}.v_{n} are both non-zero. We will call the equivalence classes components. There is a dual equivalence relation where i and i+1 are related if v_{i}.v_{n} and v_{i+1}.v_{n} are both zero. We will call these equivalence classes dual components. We let c(S) denote the number of components.

Lemma 4.4.

(i) For n ≥ 8, V (S) = (−1, …, −1) is infinite. (ii) If there are 1 ≤ r < s ≤ n − 1 and ϵ = ±1 with s − r even, v_{r}.v_{n} = ϵ, v_{s}.v_{n} = ϵ and v_{i}.v_{n} = 0 for r < i < s, then V (S) is infinite. (iii) If v_{i}.v_{n} = 0, n > i > 1, and σ_{i}(S) = (w_{1}, …, w_{n}) then V (w_{1}, … w_{i}, w_{i+2}, …, w_{n}) = (v_{1}.v_{n}, v_{2}.v_{n}, …, v_{i}.v_{n}, −v_{i+2}.v_{n}, …, −v_{n−1}.v_{n}). (iv) If there are 1 ≤ r < s ≤ n − 1 and ϵ = ±1 with s − r odd, v_{r}.v_{n} = ϵ, v_{s}.v_{n} = −ϵ and v_{i}.v_{n} = 0 for r < i < s, then V (S) is infinite.

v) If λ(S) ≥ 8, then V (S) is infinite. (vi) Let σ = σ_{n−2}σ_{n−3} … σ_{1}. Then

V (σ(S)) = (v_{1}.v_{n} − v_{2}.v_{n} + v_{3}.v_{n} − ⋯ + (−1)^{n}v_{n−1}.v_{n}, v_{1}.v_{n}, v_{2}.v_{n}, v_{3}.v_{n}, …, v_{n−2}.v_{n}).

Proof. (i) One checks that for n = 8 the product of all the reflections has infinite order and is not a diagonal matrix.

(ii) One checks that (1, 1, …, 1) is in the nullspace of M(v_{r}, …, v_{s}), contradicting Lemma 4.2 (i).

(iii) One checks this using the action given in §1.

(iv) Using (iii) one can reduce this case to (ii), from which the result follows.

(v) If λ(S) ≥ 8, then using (iii) we can reduce to V (S) = (±1, ±1, ±1, ±1, ±1, ±1, ±1, ±1). If two of these signs are different, then we can assume that they are adjacent and the result follows from (iv). If they are all the same, then the result follows from (i).

(vi) One inducts. □

From (v) above we now need only check the cases 0 < λ(S) ≤ 7. Further, by (vi) we may assume that v_{1}.v_{n} = 0. We will use the notation 1^{6} for the sequence 1, 1, 1, 1, 1, 1 etc.

Lemma 4.5. The following cases are all infinite:

(i) (0, 1^{7}).

(ii) (0, 1^{6}, 0), (0, 1^{5}, 0, −1), (0, 1^{4}, 0, −1^{2}),

(0, 1^{3}, 0, −1^{3}), (0, 1^{2}, 0, −1^{4}), (0, 1, 0, −1^{5}), (0, 0, −1^{6}).

(iii) (0, 1^{5}, 0).

(iv) (0, 1^{4}, 0, −1, 0), (0, 1^{4}, 0, 0, 1), (0, 0, 1^{4}, 0, −1), (0, 1, 0, −1^{4}, 0), (0, 1, 0, 0, 1^{4}), (0, 0, 1, 0, 1^{4}).

(v) (0, 1^{2}, 0, −1^{3}, 0), (0, 1^{2}, 0, 0, 1^{3}), (0, 0, 1^{2}, 0, −1^{3}), (0, 1^{3}, 0, −1^{2}).

(vi) (0, 1^{3}, 0, −1, 0, 1), (0, 1, 0, −1^{3}, 0, 1), (0, 1, 0, −1, 0, 1^{3}).

(vii) (0, 1^{2}, 0, −1^{2}, 0, 1), (0, 1^{2}, 0, −1, 0, 1^{2}), (0, 1, 0, −1^{2}, 0, 1^{2}).

(viii) (0, 1^{2}, 0, −1, 0, 1, 0, −1), (0, 1, 0, −1^{2}, 0, 1, 0, −1),

(0, 1, 0, −1, 0, 1^{2}, 0, −1), (0, 1, 0, −1, 0, 1, 0, −1^{2}). (ix) (0, 1, 0, −1, 0, 1, 0, −1, 0, 1).

(x) (0, 1^{3}, 0, −1, 0, 0), (0, 1^{3}, 0, 0, 1, 0), (0, 1, 0, −1^{3}, 0, 0), (0, 1, 0, 0, 1^{3}, 0),

(0, 0, 1, 0, −1^{3}, 0), (0, 0, 1, 0, 0, 1^{3}), (0, 0, 1^{3}, 0, −1, 0), (0, 0, 1^{3}, 0, 0, 1).

(xi) (0, 1^{2}, 0, −1, 0, 1, 0), (0, 1^{2}, 0, −1, 0, 0, −1), (0, 1^{2}, 0, 0, 1, 0, −1), (0, 1, 0, −1^{2}, 0, 1),

(0, 1, 0, −1, 0, 1^{2}), (0, 1, 0, 0, 1, 0, 1^{2}), (0, 1, 0, 0, 1, 0, −1, −1). (xii) (0, 1, 0, −1, 0, 1, 0, −1).

(xiii) (0, 1^{3}, 0^{4}), (0, 0, 1^{3}, 0, 0), (0^{4}, 1^{3}, 0). (xiv) (0, 1, 0, −1, 0, 1, 0), (0, 1, 0, 0, 1, 0, −1), (0, 1, 0, −1, 0, 0, 0, 1)

(0, 0, 1, 0, −1, 0, 0, 1), (0, 0, 1, 0, 0, 1, 0, −1), (0, 0, 0, 1, 0, −1, 0, 1).

Proof. One checks in each case that the corresponding product of reflections has infinite order and is not a scalar matrix. □

Lemma 4.5 (i) together with Lemma 4.4 (iii) shows that all the λ(S) = 7 cases are infinite. Assume that λ(S) = 6. Here we use Lemma 4.5 (ii), noting that each case with λ(S) = 6

can now be reduced to one of these cases. This does λ(S) = 6.

Now assume that λ(S) = 5. Then the c(S) equivalence classes determine a partition of 5. If c(S) = 1, then Lemma 4.5 (iii) does this case.

If c(S) = 2 and the partition is 5 = 4 + 1, then Lemma 4.5 (iv) does this case. If c(S) = 2 and the partition is 5 = 3 + 2, then Lemma 4.5 (v) does this case. This does the c(S) = 2 cases.

If c(S) = 3 and the partition is 5 = 3 + 1 + 1, then Lemma 4.5 (vi) does this case. If c(S) = 3 and the partition is 5 = 2 + 2 + 1, then Lemma 4.5 (vii) does this case. This does the c(S) = 3 cases.

If c(S) = 4 and the partition is 5 = 2 + 1 + 1 + 1, then Lemma 4.5 (viii) does this case. If c(S) = 5 and the partition is 5 = 1 + 1 + 1 + 1 + 1, then Lemma 4.5 (ix) does this case. This concludes all of the λ(S) = 5 cases. Now assume that λ(S) = 4. Lemma 4.5 (x) does the partition 4 = 3 + 1. Lemma 4.5 (xi)

does the partition 4 = 2 + 1 + 1. Lemma 4.5 (xii) does the partition 4 = 1 + 1 + 1 + 1.

We are thus left (in the case λ(S) = 4) with the partitions 4 = 4 and 4 = 2+2; we deal with these simultaneously in the following way. Let σ be as in Lemma 4.4 (vi). Then by that same result we see that there is k ∈ ℤ such that V (σ^{k}(S)) = (0, …, 0, ±1, ±1, 0, …, 0, −1, −1, 0) (in the 4 = 4 partition case there are no 0s between ϵ(= −1) and −1); thus V (σ^{k+1}(S)) = (0, …, 0, ±1, ±1, 0, …, 0, −1, −1) and so, V (σ^{k+2}(S)) = (0, …, 0, ±1, ±1, 0, …, 0, −1). So the following result gives what we need:

Lemma 4.6. Let ϵ = ±1 and let V (S) = (0, …, 0, ϵ, ϵ, 0, …, 0, −1), where the first two non-zero entries are in positions u, u + 1 ≤ n − 2. Then

(i) < S > is infinite if ϵ = −1 and n − u is even, or ϵ = 1 and n − u is odd. (ii) < S > is finite otherwise.

Proof. (i) follows from Lemma 4.4. (ii) follows from the standard form (3.3) in the D_{n} case if u < n − 3; while if u = n − 3, then M(σ_{n−1}(S)) is the standard form for M(A_{n}). □

This completes the cases where λ(S) = 4.

Assume that λ(S) = 3. The partition 3 = 2 + 1 is essentially the content of Lemma 4.6 and Lemma 4.5 (xiv) does the partition 3 = 1 + 1 + 1. If c(S) = 1, then Lemma 4.5 (xiii) does this case except for (0^{n−3}, 1^{3}) which is covered by Lemma 4.6.

Lemma 4.7. Assume that λ(S) = 2 and that the non-zero entries of V (S) are in positions 1 ≤ r < s ≤ n − 1. Then either S is BC_{n}-equivalent to S′ with λ(S′) = 1 or < S > is infinite.

Proof. We first note that (0^{2}, 1, 0^{2}, 1, 0^{2}) is infinite and so this reduces us to considering the cases (a) s = r + 1, r + 2; (b) r = 1, 2; (c) s = n − 2, n − 1.

If (a), then Lemma 4.4 (vi) shows acting by σ^{k} for some k ∈ ℤ will reduce λ(S) to 1. This also applies if r = 1, s = n, n − 1 or r = 2, s = n. For (b) (but not (a)), the following infinite cases (which are easily checked) give the result:

(1, 0^{2}, 1, 0^{3}), (1, 0^{3}, −1, 0^{2}), (1, 0^{6}, 1, 0),
(0, 1, 0^{2}, 1, 0^{3}), (0, 1, 0^{3}, −1, 0), (0, 1, 0^{5}, −1).

For (c) we use the transposes of (b). □

Lastly, if λ(S) = 1 and the non-zero entry is in entry r, then (since n ≥ 10) < S > is finite if and only if r = 1, 2, n − 2, n − 1.

This concludes the A_{n} case.

THE B_{n} CASE :

So assume that Γ(S(1, …, n − 1)) is of type B_{n}. See (3.2) for the standard form of M(B_{n−1}). Again we consider the vector V (S), which has entries 0, ±1, ±\sqrt{2}. The presence of the \sqrt{2} in M(S_{n−1}) now prohibits many more cases. First we note that we have the following equivalent of Lemma 4.4:

Lemma 4.8.

(i) If there are 1 ≤ r < s ≤ n − 2 and ϵ = ±1 with s − r even, v_{r}.v_{n} = ϵ, v_{s}.v_{n} = ϵ and v_{i}.v_{n} = 0 for r < i < s, then V (S) is infinite. (ii) If v_{i}.v_{n} = 0, n − 1 > i > 1, and σ_{i}(S) = (w_{1}, …, w_{n}) then V (w_{1}, … w_{i}, w_{i+2}, …, w_{n}) = (v_{1}.v_{n}, v_{2}.v_{n}, …, v_{i}.v_{n}, −v_{i+2}.v_{n}, …, −v_{n−1}.v_{n}).

(iii) If there are 1 ≤ r < s ≤ n − 2 and ϵ = ±1 with s − r odd, v_{r}.v_{n} = ϵ, v_{s}.v_{n} = −ϵ and v_{i}.v_{n} = 0 for r < i < s, then V (S) is infinite. (iv) Let σ = σ_{n−2}σ_{n−3} … σ_{1}. Then

V (σ(S)) = (v_{1}.v_{n} − v_{2}.v_{n} + v_{3}.v_{n} − ⋯ + (−1)^{n}\sqrt{2}v_{n−1}.v_{n},
v_{1}.v_{n}, v_{2}.v_{n}, v_{3}.v_{n}, …, v_{n−3}.v_{n}, \sqrt{2}v_{n−2}.v_{n} − v_{n−1}.v_{n}).

Proof. This is similar to the proof of Lemma 4.4. □

First we will show that ±\sqrt{2} does not occur in the entries of V (S). First assume that V (S) = (…, \sqrt{2}). One checks that

(…, 1, \sqrt{2}), (…, −1, −1, \sqrt{2}), (…, ±\sqrt{2}, \sqrt{2}), (…, ±\sqrt{2}, −1, \sqrt{2})

are all infinite and so the only cases that could possibly be finite are (0, 0, …, 0, −1, \sqrt{2}). If one uses the σ as in Lemma 4.8 (iv) this case becomes M(B_{n}) and so we are done.

If ±\sqrt{2} occurs in a position other than the last, then we can use Lemma 4.8 (iv) to put the \sqrt{2} into the n − 2 position of V (S). We then note that

(…, \sqrt{2}, 0), (…, \sqrt{2}), (…, 1, \sqrt{2}, −1), (…, −1, \sqrt{2}, 1), (…, 0, 0, \sqrt{2}, −1)

are all infinite. Thus all the cases where ±\sqrt{2} occurs in V (S) are infinite.

We may now assume that the only entries in V (S) are 0, ±1. Noting that

(…, 0, 1, 0), (…, 0, ±1, 1), (…, ±1, ±1, ±1), (…, 0^{3}, 1)

are all infinite leaves us with the case (1, 0, …, 0), which clearly gives W (B_{n}). This concludes the B_{n} case.

THE D_{n} CASE :

So assume that Γ(S(1, …, n−1)) is of type D_{n}. Again we consider the vector V (S), which has entries 0, ±1, ±\sqrt{2}. Here we may assume that M(S(1, …, n − 1)) has type M_{r}(D_{n−1}) as given in (3.3). The analogue of Lemma 4.4 in this case is:

Lemma 4.9.

(i) If there are 1 ≤ r < s ≤ n − 2 and ϵ = ±1 with s − r even, v_{r}.v_{n} = ϵ, v_{s}.v_{n} = ϵ and v_{i}.v_{n} = 0 for r < i < s, then V (S) is infinite. (ii) If v_{i}.v_{n} = 0, n − 1 > i > 1, and σ_{i}(S) = (w_{1}, …, w_{n}) then V (w_{1}, … w_{i}, w_{i+2}, …, w_{n}) = (v_{1}.v_{n}, v_{2}.v_{n}, …, v_{i}.v_{n}, −v_{i+2}.v_{n}, …, −v_{n−1}.v_{n}). (iii) If there are 1 ≤ r < s ≤ n − 2 and ϵ = ±1 with s − r odd, v_{r}.v_{n} = ϵ, v_{s}.v_{n} = −ϵ and v_{i}.v_{n} = 0 for r < i < s, then V (S) is infinite. (iv) Let σ = σ_{n−2}σ_{n−3} … σ_{1}. Then

V (σ(S)) =(v_{1}.v_{n} − v_{2}.v_{n} + v_{3}.v_{n} − ⋯ + (−1)^{r+n}v_{n−1}.v_{n}, v_{1}.v_{n}, v_{2}.v_{n}, v_{3}.v_{n}, …, v_{r−2}.v_{n},
, v_{r−1}.v_{n} + (−1)^{r+n}v_{n−1}.v_{n}, v_{r}.v_{n} + (−1)^{r+n}v_{n−1}.v_{n}, v_{r+1}.v_{n}, …
, v_{r−1}.v_{n} − (−1)^{r+n}(v_{n−2}.v_{n} − v_{n−1}.v_{n})).

Proof. This is similar to the proof of Lemma 4.4. □

We first consider the case where ±\sqrt{2} occurs in V (S). By applying Lemma 4.3 to (s_{1}, s_{3}, … s_{n−2}, s_{n}) we see that either a) V (S) = (\sqrt{2}, 0, …, 0, ∗); or b) (0, …, 0, \sqrt{2}, ∗) (where ∗ ∈ \{0, ±1, ±\sqrt{2}\}); or c) there is 1 < t < n − 1 such that V (S) = (0, …, 0, \sqrt{2}, \sqrt{2}, 0, …, 0, ∗), with the first \sqrt{2} in the t − 1 position.

For a) we note that (\sqrt{2}, 0^{4}, ∗) is infinite for r = 2, 3 and for all ∗ ∈ \{0, ±1, ±\sqrt{2}\}. This does case a) and b) is similar.

For c) we note that (0^{a}, \sqrt{2}, \sqrt{2}, 0^{b}, ∗) is infinite for all a, b ≥ 0, a + b = 4, and for all 1 < r < 6. This does c).

We now assume that the entries of V (S) are in {0, ±1}.

We may now apply Lemma 4.6 to (s_{1}, s_{2}, …, s_{n−2}, s_{n}), since (s_{1}, s_{2}, …, s_{n−2}) is in standard form for type A_{n−2}. We deduce that V (S) is of the form a) (0, …, 0, ϵ, ϵ, 0, …, 0, 1, ∗);

b) (0, …, 0, 1, 1, ∗); or c) (0, …, 0, 1, 0, …, 0, ∗).

From the fact that (0^{a}, 1^{2}, 0^{b}, ±1, ∗) is infinite for all a, b ≥ 0, a + b = 0 we see that all a) cases are infinite. For b) we have that (0^{5}, 1^{2}, ∗) is infinite except in the case (0^{5}, 1^{2}, 0). For c) one notes that (1, 0, …, 0) and (0, … 0, , 1, 1) are finite and that all other cases are infinite.

We now note that (0, …, 1, 1, 0), (0, …, 0, 1, 1) are both in the B_{n}-orbit of (1, 0, …, 0) (use Lemma 4.9 (iv)), and that (1, 0, …, 0) gives a base for the D_{n} case.

This completes the proof of Theorem 1.1. □

§5 The A_{n} representation of B_{n}

Fix n ≥ 3 and let P O_{n}(A_{n}) denote the set of conjugacy classes as in §1. Each [S] ∈ P O(A_{n}) can be represented by a labeled graph Γ([S]) as follows: Let Γ′(S) be the graph with vertices 1, 2, …, n + 1 and an edge {i, j} labeled k if (ij) is the kth entry of S. We get Γ([S]) by forgetting the labels on the vertices (or equivalently by taking the S_{n+1}- orbit of Γ′(S)). It is clear that P O(A_{n}) is in bijective correspondence with the set of edge-labeled trees with n edges. In this section it will be convenient to redefine the B_{n} action: σ_{i}(s_{1}, s_{2}, …, s_{n}) = (s_{1}, …, s_{i−1}, s_{i}s_{i+1}s_{i}^{−1}, s_{i}, s_{i+2}, …, s_{n}); σ_{i}^{−1}(s_{1}, s_{2}, …, s_{n}) = (s_{1}, …, s_{i−1}, s_{i+1}, s_{i+1}^{−1}s_{i}s_{i+1}, s_{i+2}, …, s_{n}). This works since σ_{i} ↦ σ_{i}^{−1} extends to an isomorphism of B_{n}.

We have shown in Theorem 1.2 that B_{n} acts transitively on P O(A_{n}). Now let Γ_{0} = Γ([(12), (23), …, (n, n + 1)]) and define δ_{s} = σ_{1}σ_{2} … σ_{s−1}, τ_{s} = δ_{s}^{s+1}, 1 < s ≤ n as in [CW], except that their action was on the right and ours is on the left. Let H_{n} =< τ_{2}, τ_{3}, …, τ_{n} > . Then as in [CW] we note that H_{n} stabilises Γ_{0}.

We also let u_{rs} = (σ_{r}σ_{r+1} … σ_{s−1})^{s−r+2} for 1 ≤ r < s < n so that u_{1s} = τ_{s}. Then < u_{rs} >= H_{n}. We will also let

H_{n3} =< u_{i,j}|1 ≤ i < j ≤ n, j − i ≤ 2 > .

If Γ is an edge-labeled graph and Q is a subset of the edge labels, then we let Γ_{Q} denote the full labeled subgraph of Γ having only the edges with labels in Q. We next prove that H_{n} acts transitively on the complement of Γ_{0}; in fact we prove:

Proposition 5.1. The group H_{n3}, n ≥ 3, acts transitively on P O(A_{n}) \ {Γ_{0}}.

Proof. Let St_{n} = ((1, n + 1), (2, n + 1), …, (n, n + 1)), so that Γ(St_{n}) is the star graph with n edges. Proposition 5.1 will follow directly from:

Lemma 5.2. Each graph in P O(A_{n}) \ {Γ_{0}}, is equivalent under H_{n3} to the star graph.

Proof. We prove Lemma 5.2 by induction on n ≥ 3, the case n = 3 being easy to check.

Lemma 5.3. (i) For 1 ≤ i < n the action of σ_{i} on P O(A_{n}) is a permutation with 2−cycles and 3-cycles, the 2-cycles are when Γ_{{i,i+1}} has two components. The element u_{i,i+1} = σ_{i}^{3} has order 2 and u_{i,i+1}(Γ) = (i, i + 1)(Γ) if Γ_{{i,i+1}} has two components. (ii) The element u_{i,i+2} acts on P O(A_{n}) so as to have three and nine cycles. The nine-cycles are when Γ_{{i,i+1,i+2}} has two components. Also, u_{i,i+2} fixes Γ if and only if Γ_{{i,i+1,i+2}} is the standard line graph with these labels.

Proof. Each case is easily checked. See Figure 4 for (ii). □

Figure 4.

In order to proceed inductively we first need to show that there is some α ∈ H_{n3} such that the subgraph Γ(α([S]))_{n−1} of Γ(α([S])) with edges labeled 1, 2, …, n − 1 is connected. If Γ([S])_{n−1} is not connected, then let the two components be L([S]) and R([S]), where the edge labeled 1 is in L([S]). The idea will be to increase the size of L([S]). We first show that we can do this if the subgraph R([S]) with the nth edge attached is not a line graph with adjacent edges in increasing order.

For m ≤ n we will let e_{m} = e_{m}(Γ([S])) denote the edge of Γ([S]) that is labeled m.

Now let m be the largest label of an edge in R([S]). If m ≠ n − 1, then e_{m+1} is in L([S]) and so the two edges e_{m}, e_{m+1} are disjoint. Thus by Lemma 5.3 (i) if we act by u_{m,m+1} ∈ H_{n3}, then we have increased m. We may thus assume that m = n − 1.

If e_{n}, e_{n−1} are not connected (do not form a connected subgraph), then acting by u_{n−1,n} permutes the labels on e_{n}, e_{n−1} and so increases the size of L([S]). So now assume that e_{n}, e_{n−1} are connected.

Now let m be the largest label of an edge of R \ {e_{n−1}}, so that m < n − 1. Then, as in the above, we may reduce to the case m = n − 2. If now e_{n−2} is not connected to e_{n} ∪ e_{n−1}, then acting by u_{n−2,n}^{3} ∈ H_{n3} will increase the size of L([S]) (see Figure 4). If e_{n} ∪ e_{n−1} ∪ e_{n−2} has a trivalent vertex, then acting by u_{n−2,n} will increase the size of L (see Figure 4). This deals with all the cases where e_{n}, e_{n−1}, e_{n−2} is not a line graph. So we now assume that e_{n}, e_{n−1}, e_{n−2} is a line graph.

We continue this process showing at each stage that we can either increase the size of L([S]) or that e_{n}, e_{n−1}, …, e_{k} are all in R([S]) and form a line graph. We indicate how one does this. So suppose that e_{n}, e_{n−1}, …, e_{k} are all in R([S]) and that they form a line graph. Assume that there are edges in R([S]) other than these and let m be the largest label of such an edge. Note that m < k. We show that we may assume that m = k − 1. For if not, then e_{k−1} is in L([S]) and acting by u_{k−1,k} will increase m.

Thus we assume that m = k − 1. Now if e_{k−1} is disjoint from all of e_{n}, e_{n−1}, …, e_{k}, then acting by u_{n−1,n}u_{n−2,n−1} … u_{k−1,k} will increase the size of L([S]) (this action only changes the labels on the graph, the label of the edge e_{n} being changed to k − 1). If e_{k−1} is not disjoint from all of e_{n}, e_{n−1}, …, e_{k}, but together they do not form a line graph, then (since all these graphs are trees) there is a unique p with n ≥ p > k such that e_{k−1} meets e_{p} and e_{p−1}. Again (using Figure 4) we see that acting by u_{n−1,n}u_{n−3,n−1} … u_{k,k+2}u_{k−1,k+1} will increase the size of L([S]) (the edge labeled n − 1 in the resulting graph is now a part of the resulting L). This completes the proof that either we can increase the size of L([S]) or that R([S]) is a line graph as indicated. We now deal with this latter case.

So suppose that R([S]) is a line graph with edges labeled n, n − 1, …, m, m > 1. Then e_{m−1} is an edge of L([S]). Suppose first that e_{m−1} is disjoint from e_{n} ∪ e_{n−1} ∪ ⋯ ∪ e_{m}. Then using Figure 4 we see that acting by

u_{n−2,n}^{3}u_{n−3,n−1}u_{n−4,n−2} … u_{m−1,m+1}

has the effect of increasing the size of L([S]). So now we may assume that e_{m−1} is not disjoint from e_{n}, e_{n−1}, …, e_{m}. Thus e_{m−1} must be adjacent to e_{n} and we have a line subgraph e_{m−1}, e_{n}, e_{n−1}, …, e_{m}. Here we first act by u_{n−1,n−2}u_{n−2,n−3} … u_{m−1,m} so as to obtain the line subgraph e_{n−1}, e_{n}, e_{n−2}, e_{n−3}, …, e_{m−1}. One now acts on this by u_{n−2,n}^{2} and notes (using Figure 4) that we have increased the size of L([S]).

Thus we may now assume that the subgraph e_{1}, e_{2}, …, e_{n−1} is connected. Hence by induction we assume that the subgraph e_{1}, e_{2}, …, e_{n−1} is a star graph with central vertex v say. We consider the following possibilities:

(i) v is a vertex of e_{n}; (ii) e_{n} is adjacent to e_{n−1}; (iii) e_{n} is adjacent to e_{k} with k ≥ 3; (iv) e_{n} is adjacent to e_{k} with k = 1, 2.

If we have (i), then we are done. If (ii), then one checks that

u_{n−3,n−1}^{2}u_{n−2,n}u_{n−2,n−1}u_{n−2,n−1}u_{n−3,n−1} ∈ H_{n3}

transforms this case to the star graph.

If (iii), then we first act by u_{k+1,k+2}u_{k+2,k+3} … u_{n−2,n−1}u_{n−1,n}, which does nothing except permute the edge labels so that the the edge that was labeled n is now labeled k + 1. Now proceed as in (ii), acting by

u_{k−2,k}^{2}u_{k−1,k+1}u_{k−1,k}u_{k−1,k}u_{k−2,k} ∈ H_{n3}.

This is possible since k ≥ 3.

If (iv) and e_{n} is adjacent to e_{1}, then we act by u_{24}u_{13}^{2}u_{24}^{3}u_{23} ∈ H_{n3}. If (iv) and e_{n} is adjacent to e_{2}, then we act by u_{24}u_{34}u_{13}u_{23}u_{13}u_{24} ∈ H_{n3}.

This completes the proof of Proposition 5.1. □

Thus the image of B_{n} is a 2-transitive group of degree (n + 1)^{n−2}.

A computer calculation using MAGMA [MA] shows that (i) for n = 3 we get 4 classes of edge-labeled graphs, the action of B_{3} being that of the alternating group A_{4}; (ii) for n = 4 we get 25 classes of edge-labeled graphs, the action of B_{4} being that of the symmetric group S_{25}; (iii) for n = 5 we get 216 classes of edge-labeled graphs, the action of B_{5} being that of the alternating group A_{216}; (iv) for n = 6 we get 2401 classes of edge-labeled graphs, the action of B_{6} being that of the alternating group A_{2401}. So now assume that n ≥ 7.

Now 2-transitive groups have been classified; see [Cam pp. 194-197] for a description of the possibilities. Apart from a few cases of low degree (less than or equal to 276), which we need not consider since we are assuming that n > 6, (so that (n + 1)^{n−2} > 2401), the possible degrees of such a 2-transitive group are n for the alternating and symmetric groups, together with

q, 2^{4d+2} + 1, q^{3} + 1, \frac{q^{d} − 1}{q − 1} (where d ≥ 2), 2^{d−1}(2^{d} ± 1) (where d ≥ 3).

Here q is a prime power.

We now show that n^{n−3} = 1 + p^{s} is not possible if n > 4 and p is a prime. For if n^{n−3} − 1 = p^{s}, then n − 1 = p^{r} and so we have (p^{r} + 1)^{p^{r}−2} = 1 + p^{s}, where s ≥ 2r since n > 4. Expanding the left hand side using the binomial theorem we get

p^{2r}X + (p^{r} − 2)p^{r} + 1 = 1 + p^{s}.

Dividing by p^{r} we get p^{r}X + (p^{r} − 2) = p^{s−r}. Now since s ≥ 2r, we see that p^{r} divides 2, which gives n ≤ 3, a contradiction. This eliminates the cases 2^{4d+2} + 1, q^{3} + 1 from the above list.

Let

H_{n4} =< {u_{i,i+1}}_{1≤i<n}, {u_{i,i+2}^{3}}_{1≤i<n−1}, {u_{i,i+3}^{4}}_{1≤i<n−2} > .

Proposition 5.4. The elements of H_{n4} fix Γ(St_{n}) and Γ_{0}.

Proof. One can easily check this statement for each generator of H_{n4}. In fact one need only check the cases i = 1. The result follows. □

We conjecture that H_{n4} acts transitively on P O(A_{n}) \ {Γ_{0}, Γ(ST_{n})}. This would show that ρ_{n}(B_{n}) is 3-transitive for all n ≥ 3.

Let n ≥ 4. We now investigate whether the image of B_{n} is the alternating group or the symmetric group in the cases considered in Theorem 1.4. Note that each of the generators σ_{i}, i < n, is conjugate to σ_{1}. Thus we need only check whether the image of σ_{n−1}, say δ_{n−1}, is an even or an odd permutation. Now note that the effect of δ_{n−1} on an edge-labeled graph Γ is to permute the labels n − 1, n on the edges labeled n − 1, n if those edges are disjoint, and is otherwise the identity. Now it is easy to check that since n ≥ 4, δ_{n−1} cannot fix any graph Γ where the edges labeled n − 1 and n are disjoint; this shows that number of such graphs is even. Thus δ_{n−1} is an even permutation if and only if the number of two cycles in δ_{n−1} is a multiple of 2 if and only if the number of graphs Γ with the edges labeled n − 1 and n disjoint is a multiple of 4. Denote this latter number by ζ_{n}.

We now calculate the number ζ′_{n} of graphs Γ which have the property that the edges labeled n − 1 and n are adjacent. Then we have (n + 1)^{n−2} = ζ_{n} + ζ′_{n}, which gives the first statement of

Lemma 5.5. For n ≥ 4 we have ζ_{n} = (n + 1)^{n−2} − ζ′_{n} and

ζ′_{n} = ∑ ; \begin{matrix}a, b, c ≥ 0 \\ a + b + c = n − 2 \end{matrix} \binom{n − 2}{a}\binom{n − 2 − a}{b}(a + 1)^{a−1}(b + 1)^{b−1}(c + 1)^{v−1}.

(Here the convention is that x^{y} = 1 if y < 0.)

We have

ζ′_{n} ≡ 0 mod 4 if n ≡ 1, 3 mod 4;
ζ′_{n} ≡ 3 mod 4 if n ≡ 0 mod 4;
ζ′_{n} ≡ 1 mod 4 if n ≡ 2 mod 4.

Proof. Let Γ be a graph with n edges labeled 1, 2, …, n and let e_{i} be the edge of Γ labeled i. Assume that e_{n−1} and e_{n} are adjacent in Γ. Let u, v be the vertices of e_{n−1} and v, w the vertices of e_{n}. Let A be the component of Γ \ {u} that does not contain e_{n−1}; let B be the component of Γ \ {v} that does not contain e_{n−1}; let C be the component of Γ \ {w} that does not contain e_{n−1}. Let a denote the number of edges of A, b denote the number of edges of B, and c the number of edges of C. Then we have a + b + c = n − 2 where a, b, c ≥ 0. The possibilities for Γ come from the possibilities for each of A, B, C. We will think of A, B, C as rooted trees with roots u, v, w and numbers of edges a, b, c edges respectively. Since A is a tree and has a edges, there are \binom{n−2}{a} ways of choosing the labels for the edges of A. Further, for a given such choice of labels for the edges of A there are (a + 1)^{a−1} rooted trees [S] and so there are \binom{n−2}{a}(a + 1)^{a−1} total possibilities for A.

Given such a choice of labels for A there are then \binom{n−2−a}{b} choices for a set of labels for the edges of B and so \binom{n−2−a}{b}(b + 1)^{b−1} total possibilities for B. Having chosen labels for A, B, the set of labels for C is now determined since a + b + c = n − 2. Thus there are (c + 1)^{c−1} possibilities for C. All of these choices are independent and so the formula for ζ′_{n} given in Lemma 5.5 follows.

Assume that n > 5 is odd. We consider each choice of a, b, c ≥ 0 where a + b + c = n − 2. Then at least one of a, b, c is odd. If a is odd and a ≥ 3, then (a + 1)^{a−1} ≡ 0 mod 4. Similarly for b, c. Thus we may assume that either a is even or a < 3 and similarly for b, c. One now checks that all possible choices of a, b, c give a summand of ζ′_{n} which is a multiple of 4. Thus ζ′_{n} ≡ 0 mod 4. The rest of the cases are similar. One uses the fact that if n ≡ 2 mod 4 and a is odd, then \binom{n−2}{a} ≡ 0 mod 4 and \binom{n}{a} ≡ 0 mod 2. □

Corollary 5.6. Let n > 3. Then

ζ_{n} ≡ 0 if n ≡ 1, 2, 3 mod 4;
ζ_{n} ≡ 2 if n ≡ 0 mod 4. □

§6 The P O(B_{n}) case

In this section we prove Theorem 1.5.

Recall that each element of P O(B_{n}) is a conjugacy class of some sequence S = (s_{1}, …, s_{n}) of n reflections generating W (B_{n}). These reflections are the γ_{i} and the β_{rs}^{±} and in S we have exactly one of the γ_{i}. Since no γ_{i} is conjugate to a β_{rs}^{±}, the position of this γ_{i} in S is independent of which W (B_{n})-conjugate of S one chooses; denote this position by τ(S). Let R_{u} be the set of all [S] ∈ P O(B_{n}) such that τ(S) = u. Then R_{1}, …, R_{n} is a set of blocks for the B_{n} action on P O(B_{n}). Further it is easily seen that σ_{i}(R_{j}) = R_{(i,i+1)j} and so the action of B_{n} on these blocks is that of the full symmetric group S_{n}.

We now show that the degree of this representation is n^{n−1}. As in the proof of the B_{n} case in §3 we note that any set S = (s_{1}, …, s_{n}) of generating reflections in the B_{n} case can be conjugated to the form (δ_{1}, …, δ_{n}), where n − 1 of the δ_{i} have the form β_{rs}^{+} and the remaining one is γ_{j}. Further, it is easy to see that this representative of the conjugacy class of S is unique. Thus removing the γ_{j} from the sequence S results in a set S′ of n − 1 reflections which generate S_{n}. We have seen in Theorem 1.4 that (up to conjugacy) there are n^{n−3} of these. Thus the number of elements of P O(B_{n}) will be equal to n^{n−3} multiplied by the number of ways of inserting the γ_{j} into S′. Since there are n places to put the γ_{j} and there are n choices of j, we thus see that the number of elements of P O(B_{n}) is n^{n−1}, as required. This completes the proof of Theorem 1.5 □

References

[A] Artin E., Geometric Algebra, New York: Interscience, 1957.

[Bi] Birman J., Braids, Links and Mapping class Groups, Ann. Math. Studies 82 (1974).

[Br] Brieskorn, E., Automorphic sets and braids and singularities, Braids, Contemp. Math., vol. 78, Amer. Math. Soc., 1988, pp. 45-115.

[Cam] Cameron P.J., Permutation Groups, London Mathematical Society Student Texts, vol. 45, Cambridge, 1999.

[CP] Catanese, F; Paluszny, M., Polynomial-Lemniscates, trees and braids, Topology 30 (1991), 623-640.

[CW] Catanese, F; Wajnryb, B., The fundamental group of generic polynomials, Topology 30 (1991), 641-651.

[Co] Coxeter H.S.M., Discrete groups generated by reflections, Ann. Math. 35 (1934), 588-621.

[De] Dehornoy, Patrick, Braids and self-distributivity, Progress in Mathematics, vol. 192, Birkhäuser Verlag, Basel, 2000.

[Do] Dörner, Axel, Isotropieuntergruppen der artinschen Zopfgruppen., Dissertation, Rheinische Friedrich-Wilhelms-Universität Bonn, Bonn. Bonner Mathematische Schriften 255. (1993.), Universität Bonn, Mathematisches Institut, Bonn, 1-146.

[GB] Grove, L. C.; Benson, C. T., Finite reflection groups, Second edition. Graduate Texts in Mathematics, vol. 99, Springer-Verlag, New York, 1985.

[Ho] Howlett, Robert B., Coxeter groups and M-matrices, Bull. London Math. Soc. 14 (1982), 137-141.

[Hu] Humphreys, James E., Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, 1990.

[Hur] Hurwitz A., Ueber Riemann’sche Flachen mit gegebenen Verzweigungspunkten, Math. Ann. 39 (1891), 1-61.

[Lo] Looijenga, E, The complement of the bifurcation variety of a simple singularity, Invent. Math. 23 (1974), 105-116.

[MA] Bosma W., Cannon J., MAGMA (University of Sydney), 1994.

[SSV] Shapiro M., Shapiro B. and A.Vainshtein, Ramified coverings of S^{2} with one degenerate branching point and enumeration of edge-ordered graphs, Topics in singularity theory, Amer. Math. Soc. Transl. 180 (1997), 219-227.

[S] Stanley R.P., Enumerative Combinatorics, see Problem 5.27, Cambridge, 1999.

[Vo] Völklein, H, Groups as Galois groups. An introduction, Cambridge Studies in Advanced Mathematics, vol. 53, Cambridge University Press, Cambridge, 1996.