Sminaire Lotharingien de Combinatoire 61A (2009), Article B61A

ISOMETRY CLASSES OF GENERALIZED ASSOCIAHEDRA

NANTEL BERGERON, CHRISTOPHE HOHLWEG, CARSTEN LANGE, AND HUGH THOMAS^{∗}

Abstract. Let W be a finite Coxeter group. Generalized associahedra are convex polytopes constructed from a permutahedron of W and an orientation of the Coxeter graph of W. They play a fundamental role in the theory of finite type cluster algebras initiated by Fomin and Zelevinsky, and also appear in algebraic topology. In this article, we show that the isometries of these polytopes are given by certain automorphisms of oriented Coxeter graphs.

To the memory Pierre Leroux

1. Introduction

Studying homotopy theory of loop spaces, Jim Stasheff [10, 11] constructed a cell complex whose vertices correspond to the possible compositions of n binary operations. Furthermore this cell complex can be realized as a simple polytope, the associahedron (also called Stasheff polytope). There is a natural relation between the permutahedron (weak lattice on permutations) and the associahedron: the permutahedron can naturally be written as an intersection of halfspaces indexed by weights for the A_{n} root system. If one intersects a certain, carefully chosen subset of these halfspaces, one can obtain the associahedron (see Example 2.2 below). Shnider-Sternberg [9] and Loday [5] give us a beautiful explicit construction of the associahedron from the permutahedron along these lines.

Generalized associahedra were introduced by S. Fomin and A. Zelevinsky in their work on cluster algebras [2]. The geometry of these objects encodes nice algebraic structures. Therefore one important question is to find good polytopal realizations of the generalized associahedra. This was first answered in [1] by Chapoton, Fomin and Zelevinsky. Then, N. Reading [8] constructed a family of fans, the Cambrian fans {F_{c}} indexed by Coxeter elements c of a given finite Coxeter group W. More recently, we have constructed [3] a family of generalized associahedra Asso_{c}(W), one for each Cambrian fan F_{c}. These generalized associahedra are realized from the corresponding permutahedron by removing some halfspaces according to a rule specified by c, linking questions about generalized associahedra to questions about the better known permutahedron.

Date: March 17, 2009.

∗ This work is supported in part by CRC, NSERC and PAFARC. It is the results of a working session at the Algebraic Combinatorics Seminar at the Fields Institute with the active participation of Anouk Bergeron-Brlek, Philippe Choquette, Huilan Li, Trueman Machenry, Alejandra Premat, Muge Taskin and Mike Zabrocki.

It is now natural to ask how many distinct (up to isometry) generalized associahedra we get. This is what we answer here. Our main theorem (Theorem 2.3) describes completely the isometry classes of generalized associahedra as realized in [3]. The isometry classes depend of the choice of the starting permutahedron. As a byproduct we obtain a classification of the isometry classes of Cambrian fans (Corollary 2.6): the Cambrian fans indexed by Coxeter elements c and c′ are isometric if and only if μ(c′) = c or μ(c′) = c^{−1} for some μ an automorphism of the Coxeter graph of W. In Section 2 we introduce the necessary definitions and state our main theorem (Theorem 2.3). The proof is found in Section 4. Section 3 is dedicated to some auxiliary results needed for this proof. For most of the paper, we make the simplifying assumption that the Coxeter system in question is irreducible; in Section 5, we explain how to deal with the reducible case.

2. background and main theorem

We assume some basic familiarity with Coxeter groups and root systems and follow the notation of [4]. Let (W, S) be a finite Coxeter system acting by reflections on an ℝ-Euclidean space (V, ⟨·, ·⟩) with length function ℓ : W → ℕ. Without loss of generality, we assume that the action of W is essential relative to V, that is, has no nontrivial space fixed pointwise.

Let Φ be a root system corresponding to (W, S), with all roots having equal length. (In particular, we do not assume Φ is crystallographic.) The simple roots Δ form a basis of V, and the reflection s maps α_{s} to −α_{s} and fixes the hyperplane H_{s} = {v ∈ V | ⟨v, α_{s}⟩ = 0}. Let Δ^{∗} = {v_{s} | s ∈ S} be the set of fundamental weights of Δ, that is, ⟨v_{t}, α_{s}⟩ = 1 if s = t and ⟨v_{t}, α_{s}⟩ = 0 otherwise. As V is finite dimensional we identify V and V^{∗}.

2.1. The permutahedron. We now aim for a definition of the W -permutahedron and pick a point u ∈ V contained in the complement of the reflection hyperplanes of W. Without loss of generality, we choose

u := ∑_{s∈S} κ_{s}v_{s}, κ_{s} > 0.

For w ∈ W we write

M(e) := u and M(w) := w (M(e))

and obtain the permutahedron Perm_{u}(W) as convex hull of {M(w) | w ∈ W }. The index u will often be omitted for brevity. Equivalently, we have

Perm(W) = ⋂_{s∈S} ⋂_{x∈W} ℋ_{(x,s)}

where

ℋ_{(x,s)} := {v ∈ V | ⟨v, x(v_{s})⟩ ≤ ⟨M(e), v_{s}⟩}.

L M(e) H_{s_{1}} M(s_{1}) M(s_{1}s_{2})  M(s_{2}) M(s_{2}s_{1}) M(s_{1}s_{2}s_{1})  H_{s_{2}} H_{s_{1}s_{2}s_{1}}  α_{2}  α_{1} v_{s_{1}} v_{s_{2}}  H_{(e,s_{1})} = H_{(s_{2},s_{1})} H_{(s_{2},s_{2})} = H_{(s_{2}s_{1},s_{2})} H_{(e,s_{2})} = H_{(s_{1},s_{2})} H_{(s_{1},s_{1})} = H_{(s_{1}s_{2},s_{1})} H_{(s_{1}s_{2},s_{2})} = H_{(s_{1}s_{2}s_{1},s_{2})} H_{(s_{1}s_{2}s_{1},s_{1})} = H_{(s_{2}s_{1},s_{1})}

Figure 1. The permutahedron Perm(S_{3}) obtained as convex hull of the S_{3}-orbit of M(e) ∈ L or as intersection of the half spaces ℋ_{(x,s)}.

We also make use of the hyperplane H_{(x,s)} = {v ∈ V | ⟨v, x(v_{s})⟩ = ⟨M(e), v_{s}⟩}.

Denote by W_{I} the standard parabolic subgroup of W generated by I ⊆ S. Note that H_{(w,s)} = H_{(x,s)} if and only if w ∈ xW_{S\{s}}. Also, M(w) ∈ H_{(x,s)} if and only if H_{(x,s)} = H_{(w,s)}. Hence we have a simple way to describe the vertices:

{M(w)} = ⋂_{s∈S} H_{(w,s)}.

Example 2.1 (Realization of Perm(A_{2})). We consider the Coxeter group W = S_{3} of type A_{2} acting on ℝ^{2}. The reflections s_{1} and s_{2} generate W. The simple roots that correspond to s_{1} and s_{2} are α_{1} and α_{2}. They are normal to the reflection hyperplanes H_{s_{1}} and H_{s_{2}}. The dual vectors to the simple roots correspond to the vectors v_{1} and v_{2}. Fix a ray L = {μ(κ_{1}v_{1} + κ_{2}v_{2}) | μ > 0} where κ_{1}, κ_{2} > 0. We choose M(e) ∈ L and obtain the permutahedron as convex hull of the W -orbit of M(e). Alternatively, the permutahedron can be described as intersection of the half spaces ℋ_{(x,s)} with bounding hyperplanes H_{(x,s)} for x ∈ W and s ∈ S. All the objects are indicated in Figure 1.

2.2. Generalized associahedra. For c a Coxeter element in W, that is to say, the product of the simple reflections of W taken in some order, and I ⊆ S, we denote by c_{(I)} the subword of c obtained by taking only the simple reflections in I. So c_{(I)} is a Coxeter element of W_{I}. Reading defined the c-sorting word of w ∈ W in [6, Section 2] as the unique subword of the infinite word c^{∞} = cccccc … that is a reduced expression for w and is the lexicographically smallest sequence of positions occupied by this subword. In particular, the c-sorting word of w is such that w = c_{(K_{1})}c_{(K_{2})} … c_{(K_{p})} with non-empty K_{i} ⊆ S and ℓ(w) = ∑_{i=1}^{p} |K_{i}|. As example we consider the Coxeter group W = S_{4} of type A_{3} generated by the simple reflections S = {s_{1}, s_{2}, s_{3}}, where s_{1}, s_{3} commute, and the Coxeter element c = s_{2}s_{1}s_{3}. The c-sorting word of the longest element w_{0} ∈ W is s_{2}s_{1}s_{3}s_{2}s_{1}s_{3} = c_{(S)}c_{(S)}. If we choose the Coxeter element c = s_{1}s_{2}s_{3} instead of s_{2}s_{1}s_{3}, then the c-sorting word of w_{0} is s_{1}s_{2}s_{3}s_{1}s_{2}s_{1} = c_{(S)}c_{({s_{1},s_{2}})}c_{({s_{1}})}.

The sequence c_{(K_{1})}, …, c_{(K_{p})} associated to the c-sorting word for w is called the c-factorization of w. The c-factorization of w is independent of the chosen reduced word for c but depends on the Coxeter element c. In general the c-factorization does not yield a nested sequence K_{1}, …, K_{p} of subsets of S. An element w ∈ W is called c-sortable if K_{1} ⊇ K_{2} ⊇ … ⊇ K_{p}. Reading proves in [6] that the longest element w_{0} ∈ W is c-sortable for any chosen Coxeter element c.

Given a specific reduced word v, we say that u is a prefix up to commutation of v if some reduced word for u appears as a prefix of a word which can be obtained from v by the commutation of commuting reflections. In [3] we define an element w ∈ W to be a c-singleton if it is a prefix up to commutation of the c-factorization of w_{0}. We illustrate this notion by considering again the Coxeter group W = S_{4} and the Coxeter element c = s_{2}s_{3}s_{1}. The c-singletons are

\begin{matrix}e, & s_{2}s_{3}, & s_{2}s_{1}s_{3}s_{2}s_{1}, \\ s_{2}, & s_{2}s_{1}s_{3}, & s_{2}s_{1}s_{3}s_{2}s_{3}, and \\ s_{2}s_{1}, & s_{2}s_{1}s_{3}s_{2}, & w_{0} = s_{2}s_{3}s_{1}s_{2}s_{3}s_{1}. \end{matrix}

For example s_{2}s_{1} is a not a prefix of the c-factorization w_{0} = s_{2}s_{3}s_{1}s_{2}s_{3}s_{1}, but it is a prefix up to commutation because it appears as a prefix after commuting the simple reflections s_{1}, s_{3}.

The halfspace ℋ_{(x,s)} is said to be c-admissible if the hyperplane H_{(x,s)} contains M(w) for some c-singleton w. We have shown in [3] that the intersection of all c-admissible halfspaces ℋ_{(x,s)} is a generalized associahedron Asso_{c}(W) whose normal fan is the c-Cambrian fan F_{c} (see [8] for a definition of F_{c}).

Example 2.2. The Coxeter group W = S_{3} generated by the reflections s_{1} and s_{2} has two Coxeter elements: c_{1} = s_{1}s_{2} and c_{2} = s_{2}s_{1}. The c_{1}-singletons are e, s_{1}, s_{1}s_{2}, and s_{1}s_{2}s_{1} while the c_{2}-singletons are e, s_{2}, s_{2}s_{1},and s_{2}s_{1}s_{2}. Starting with the permutahedron Perm(S_{3}), we obtain the two associahedra Asso_{c_{1}}(S_{3}) and Asso_{c_{2}}(S_{3}) shown in Figure 2 as intersection of the c_{1}- and c_{2}-admissible halfspaces.

2.3. Main result. For most of the paper, we will assume that (W, S) is irreducible. The case where (W, S) is reducible requires a straightforward (but not immediate) extension of the results in the irreducible case; we describe this in the final section.

An automorphism of the Coxeter graph associated to (W, S) is a bijection μ on S such that the order of μ(s)μ(t) equals the order of st for all s, t ∈ S. In particular, μ induces an automorphism on W.

Let u = ∑_{s∈S} κ_{s}v_{s} be a point in V. We will say that u is balanced if κ_{s} = κ_{t} for all s, t ∈ S. An automorphism μ of the Coxeter graph is a u-automorphism if κ_{s} = κ_{μ(s)} for all s ∈ S. In particular, if u is balanced, then any automorphism of a Coxeter graph is a u-automorphism.

L M(e) M(s_{2}) M(s_{2}s_{1}) M(s_{1}s_{2}s_{1})  H_{s_{2}} H_{s_{1}s_{2}s_{1}} ^{L M(e) H_{s_{1}} M(s_{1}) M(s_{1}s_{2}) M(s_{1}s_{2}s_{1}) H_{s_{2}} H_{s_{1}s_{2}s_{1}}}

Figure 2. The two associahedra Asso_{c_{1}}(S_{3}) (left) and Asso_{c_{2}}(S_{3}) (right) obtained from the permutahedron Perm(S_{3}) by keeping the c-admissible halfspaces ℋ_{(x,s)}.

Theorem 2.3. Let (W, S) be an irreducible finite Coxeter system and c_{1}, c_{2} be two Coxeter elements in W. Suppose that u = ∑_{s∈S} κ_{s}v_{s} for some κ_{s} > 0. The following statements are equivalent.

(1) Asso_{c_{1}}(W) = φ (Asso_{c_{2}}(W)) for some linear isometry φ on V.

(2) There is a u-automorphism μ of the Coxeter graph of (W, S) such that μ(c_{2}) = c_{1} or μ(c_{2}) = w_{0}c_{1}^{−1}w_{0}.

Observe that w_{0}c^{−1}w_{0} may or may not equal c (for instance in A_{3} take c = s_{1}s_{3}s_{2}). So the second condition in Theorem 2.3 may be redundant and the associahedra may actually be identical (not just isometric). Moreover, if the coefficients κ_{s} are chosen generically, that is distinct, then the isometry classes are of cardinality 1 or 2. As stated in the next corollary, the isometry classes reach their maximal cardinality if u is balanced.

Corollary 2.4. Let (W, S) be an irreducible finite Coxeter system and c_{1}, c_{2} be two Coxeter elements in W. If u is balanced, then the following statements are equivalent.

(1) Asso_{c_{1}}(W) = φ (Asso_{c_{2}}(W)) for some linear isometry φ on V.

(2) There is an automorphism μ of the Coxeter graph of (W, S) such that μ(c_{2}) = c_{1} or μ(c_{2}) = c_{1}^{−1}.

Proof. It follows from Theorem 2.3 and a rewriting of the second assumption in accordance with the fact that the map s ↦ w_{0}sw_{0} is an automorphism of the Coxeter graph. □

If u is balanced, then Asso_{c_{1}}(W) = φ (Asso_{c_{2}}(W)) for some linear isometry φ on V if and only if there is a u-automorphism θ of the Bruhat ordering of (W, S) such that θ(c_{2}) = c_{1}. This follows by inspection for |S| = 1, 2 and, for |S| ≥ 3, from a characterization of automorphisms of Bruhat orderings due to van den Hombergh, see Section 8.8 of [4] and the fact that a Coxeter element c defines an orientation of the Coxeter graph Γ: orient the edge {s_{i}, s_{j}} from s_{i} to s_{j} if and only if s_{i} is to the left of s_{j} for any reduced word for c.

s_{1} s_{2} s_{3} s_{4} c = s_{4}s_{2}s_{1}s_{3}  s_{1} s_{2} s_{3} s_{4} c = s_{4}s_{3}s_{1}s_{2}  s_{1} s_{2} s_{3} s_{4} c = s_{2}s_{3}s_{1}s_{4} s_{1} s_{2} s_{3} s_{4} c = s_{3}s_{1}s_{2}s_{4}  s_{1} s_{2} s_{3} s_{4} c = s_{2}s_{1}s_{3}s_{4}  s_{1} s_{2} s_{3} s_{4} c = s_{4}s_{1}s_{2}s_{3}

Figure 3. Six Coxeter elements and their associated oriented Coxeter graphs of the Coxeter group of type D_{4} that yield isometric associahedra.

Theorem 2.3 combined with the classification of irreducible finite Coxeter groups yields that the cardinality of an isometry class in the case where u is balanced is either two, four, or six. We briefly discuss the situation.

Example 2.5. We use the notation and hypothesis of Corollary 2.4.

(1) Let (W, S) be a Coxeter system of type A_{n} (n ≥ 2), E_{6}, F_{4}, or I_{2}(m). Then there is precisely one non-trivial automorphism μ of the Coxeter graph. Hence there are either two or four elements in the isometry class of Asso_{c}(W). The cardinality equals two if μ(c) ∈ {c, c^{−1}} and equals four if μ(c) ∉ {c, c^{−1}}.

(2) Let (W, S) be a Coxeter system of type B_{n} (n ≥ 2), E_{7}, E_{8}, H_{3}, or H_{4}. Then the conjugation by w_{0} is the identity, and Id is the only automorphism of the associated Coxeter graph. So each isometry class has cardinality two, only the Coxeter elements c and c^{−1} yield isometric associahedra.

(3) Let (W, S) be a Coxeter system of type D. If |S| > 4 then there is only one non-trivial automorphism μ of the Coxeter graph and the isometry class of Asso_{c}(W) has cardinality two if μ(c) ∈ {c, c^{−1}} and four otherwise. If |S| = 4, the group of automorphisms of the Coxeter graph is generated by the non-trivial automorphisms μ and ν with μ^{2} = Id and ν^{3} = Id. The isometry class of Asso_{c}(W) consists either of two or six elements, see Figure 3 for six Coxeter elements that yield isometric associahedra.

Theorem 2.3 allows a classification of the isometric Cambrian fans as well. The proof will be given at the end of Section 4.

Corollary 2.6. The following propositions are equivalent:

(1) The Cambrian fans F_{c} and F_{c′} are isometric;

(2) Asso_{c}(W) and Asso_{c′}(W) are isometric if u is balanced;

(3) there is an automorphism μ of the Coxeter graph of (W, S) such that μ(c′) = c or μ(c′) = c^{−1}.

Remark 2.7. In fact, the condition that u be balanced in (2) above can be weakened to require only that u satisfies κ_{s} = κ_{w_{0}sw_{0}}, for all s ∈ S (see Eq. (1) in the proof).

3. Preliminary results

From now on, we fix u = ∑_{s∈S} κ_{s}v_{s} for some constants κ_{s} > 0. Remember that M(e) = u.

Let (W, S) be a Coxeter system and consider the polyhedron P defined by:

P := ⋂_{s∈S} ℋ_{(e,s)} ∩ ⋂_{s∈S} ℋ_{(w_{0},s)}.

Remark 3.1. In fact, P is a full-dimensional convex polytope because W acts essentially on V and the cones ⋂_{s∈S} ℋ_{(e,s)} and ⋂_{s∈S} ℋ_{(w_{0},s)} are strictly convex, pointed with apex M(e) and M(w_{0}), and both contain Perm(W). In other words, P is obtained from Perm(W) by removing, from the definition of Perm(W) as an intersection of halfspaces, all halfspaces ℋ_{(x,s)} that satisfy M(e) ∉ H_{(x,s)} and M(w_{0}) ∉ H_{(x,s)}.

Proposition 3.2. Let φ : V → V be a linear isometry that maps P to itself and has the fixed point M(e). Then φ induces a u-automorphism μ of the Coxeter graph of (W, S) such that φ(v_{s}) := v_{μ(s)} for every s ∈ S.

Proof. For φ satisfying our hypothesis, we have φ(M(e)) = M(e) ∈ H_{(e,s)}. Hence φ induces a bijection on the set {ℋ_{(e,s)} | s ∈ S}. Since v_{s} is a normal vector to ℋ_{(e,s)} for any s ∈ S, we have φ(v_{s}) = k_{s}v_{t_{s}} for some k_{s} > 0 and t_{s} ∈ S. Hence ∑_{s∈S} k_{s}κ_{s}v_{t_{s}} = φ(M(e)) = M(e) = ∑_{s∈S} κ_{s}v_{s} and then κ_{t_{s}} = k_{s}κ_{s}.

On the other hand, since φ is an isometry fixing P and M(e), it induces a bijection on the set of edges of P which have M(e) as one of their vertices. Each of these edges is contained in a line l_{s} := ⋂_{r∈S\{s}} H_{(e,r)}, for s ∈ S. So φ induces a bijection on the set {l_{s} | s ∈ S}. Since v_{r} is a fundamental weight of Δ, and is a normal vector of H_{(e,r)}, the hyperplane H_{(e,r)} is spanned by the simple roots {α_{u} | u ∈ S \ {r}}, and thus l_{s} is spanned by the simple root α_{s}. As the simple roots are all of the same length and φ preserves the norm of vectors, φ(α_{s}) = ±α_{r_{s}} for some r_{s} ∈ S. Now,

1 = ⟨v_{s}, α_{s}⟩ = ⟨φ(v_{s}), φ(α_{s})⟩ = ±k_{s}⟨v_{t_{s}}, α_{r_{s}}⟩.

We conclude that r_{s} = t_{s}, k_{s} = 1 and κ_{s} = κ_{t_{s}} for all s ∈ S. Therefore φ induces a bijection on the set {v_{s} | s ∈ S}. In other words φ(Δ^{∗}) = Δ^{∗}, and, since ϕ is an isometry, φ(Δ) = Δ and the angle between α_{s}, α_{r} is preserved. That is, φ induces a u-automorphism of the Coxeter graph of W, since the order of st in W is entirely determined by the angle between α_{s} and α_{t}, and since κ_{s} = κ_{t_{s}} for all s ∈ S. □

Remark 3.3. In the proof of the previous proposition, we have made use of the assumption (stated when we introduced the root system Φ) that all roots of Φ are of equal length. Note that this is not an important restriction, since any root system can be rescaled to have all its roots of equal length. For example, the vectors (1, 0) and (−1, 1) are simple roots for the crystallographic root system B_{2}. Instead of these, we would take (1, 0) and (−1/\sqrt{2}, 1/\sqrt{2}) as the simple roots. The reader should be well aware that the assumption that the simple roots are of the same length does not imply that the fundamental weights are of the same length, see for instance in A_{3}.

Proposition 3.4. For every u-automorphism μ of the Coxeter graph, there is a unique linear isometry φ_{μ} that fixes P and M(e) defined by φ_{μ}(α_{s}) := α_{μ(s)} for every s ∈ S.

Proof. The map φ_{μ} is well-defined since Δ is a basis of V. As μ is an automorphism of the Coxeter graph and ⟨α_{μ(s)}, α_{μ(t)}⟩ depends only on the order of st, we have ⟨α_{μ(s)}, α_{μ(t)}⟩ = ⟨α_{s}, α_{t}⟩ for s, t ∈ S. In other words φ_{μ} is an isometry since Δ is a basis of V.

From duality it is clear that v_{s} = ∑_{r∈S} ⟨v_{r}, v_{s}⟩α_{r}, for all s ∈ S. Moreover, the matrices [⟨v_{r}, v_{s}⟩]_{s,t} and [⟨α_{r}, α_{s}⟩]_{s,t} are inverse to each other and the permutation μ: S → S is such that [⟨α_{μ(r)}, α_{μ(s)}⟩]_{s,t} = [⟨α_{r}, α_{s}⟩]_{s,t}. Hence [⟨v_{μ(r)}, v_{μ(s)}⟩]_{s,t} = [⟨v_{r}, v_{s}⟩]_{s,t}. Thus, for s ∈ S we have

φ_{μ}(v_{s}) = ∑_{r∈S} ⟨v_{s}, v_{r}⟩α_{μ(r)} = ∑_{r∈S} ⟨v_{μ(s)}, v_{μ(r)}⟩α_{μ(r)} = ∑_{r′∈S} ⟨v_{μ(s)}, v_{r′}⟩α_{r′} = v_{μ(s)}.

Now as κ_{s} = κ_{μ(s)} for all s ∈ S, φ_{μ} fixes M(e), and therefore P. □

Similarly, for every isometry φ that fixes P and M(e) there is a u-automorphism μ such that φ(v_{s}) := v_{μ(s)} for every s ∈ S, by Proposition 3.2.

Corollary 3.5. Let μ be an automorphism of the Coxeter graph of (W, S) and φ be a linear isometry that maps P to itself and has M(e) as fixed point. Suppose that μ and φ are related via φ(v_{s}) = v_{μ(s)} for all s ∈ S. Then φ = φ_{μ} and μ is a u-automorphism. Moreover,

φ (w(v_{s})) = (μ(w)) (v_{μ(s)})  and  φ(ℋ_{(w,s)}) = ℋ_{(μ(w),μ(s))}

for w ∈ W, s ∈ S. In particular, φ(Perm(W)) = Perm(W).

Proof. As Δ^{∗} is a basis of V, φ = φ_{μ}. Moreover, since φ fixes M(e) we have

∑_{μ(s)∈S} κ_{μ(s)}v_{μ(s)} = ∑_{s∈S} κ_{s}v_{s} = M(e) = φ_{μ}(M(e)) = ∑_{s∈S} κ_{s}v_{μ(s)}.

By identification, we have κ_{s} = κ_{μ(s)} for all s ∈ S, which proves that μ is a u-automorphism.

We prove the first remaining claim by induction on the length of w. If w = e the claim is φ(v_{s}) = v_{μ(s)} and was shown in the proof of Proposition 3.2. Now assume ℓ(w) > 0. There is t ∈ S such that w = w′t with ℓ(w′) < ℓ(w). The action of t on V is a reflection in reflection hyperplane H_{t}. Hence we have

t(v_{s}) = v_{s} − \frac{2⟨v_{s}, α_{t}⟩}{⟨α_{t}, α_{t}⟩}α_{t}.

Also, since φ is an isometry that maps α_{r} to α_{μ(r)} and v_{r} to v_{μ(r)}, we have

φ_{μ}(w(v_{s})) = φ_{μ} (w′ (t(v_{s})))

= μ(w′) (v_{μ(s)} − \frac{2⟨v_{μ(s)}, α_{μ(t)}⟩}{⟨α_{μ(t)}, α_{μ(t)}⟩}α_{μ(t)})

= μ(w′)μ(t) (v_{μ(s)}) = (μ(w′t)) (v_{μ(s)})

= μ(w) (v_{μ(s)}) .

We now prove the second claim.

φ_{μ}(ℋ_{(w,s)}) = {φ_{μ}(v) ∈ V | ⟨v, w(v_{s})⟩ ≤ ⟨M(e), v_{s}⟩}
= {v ∈ V | ⟨v, φ_{μ}(w(v_{s}))⟩ ≤ ⟨φ_{μ}(M(e)), φ_{μ}(v_{s})⟩}
= {v ∈ V | ⟨v, μ(w)(v_{μ(s)}))⟩ ≤ ⟨M(e), v_{μ(s)}⟩}
= ℋ_{(μ(w),μ(s))}.
□

e^{s_{1}}^{s_{1}s_{2}}^{s_{1}s_{2}s_{3}}  ^{s_{1}s_{2}s_{1}}^{s_{1}s_{2}s_{3}s_{1}}^{s_{1}s_{2}s_{3}s_{1}s_{2}}^{s_{1}s_{2}s_{3}s_{1}s_{2}s_{1}} c = s_{1}s_{2}s_{3}  ^{e}^{s_{3}}^{s_{3}s_{2}}^{s_{3}s_{2}s_{1}}  ^{s_{3}s_{2}s_{3}}^{s_{3}s_{2}s_{1}s_{3}}^{s_{3}s_{2}s_{1}s_{3}s_{2}}^{s_{3}s_{2}s_{1}s_{3}s_{2}s_{3}} c = s_{3}s_{2}s_{1}  ^{e}^{s_{2}}^{s_{2}s_{3}}  ^{s_{2}s_{1}}^{s_{2}s_{1}s_{3}}^{s_{2}s_{1}s_{3}s_{2}}^{s_{2}s_{1}s_{3}s_{2}s_{1}} ^{s_{2}s_{1}s_{3}s_{2}s_{3}}^{s_{2}s_{1}s_{3}s_{2}s_{1}s_{3}} c = s_{2}s_{1}s_{3}  ^{e}^{s_{1}}  ^{s_{3}}^{s_{3}s_{1}}^{s_{3}s_{1}s_{2}}^{s_{3}s_{1}s_{2}s_{1}}  ^{s_{3}s_{1}s_{2}s_{3}}^{s_{3}s_{1}s_{2}s_{3}s_{1}}^{s_{3}s_{1}s_{2}s_{3}s_{1}s_{2}} c = s_{3}s_{1}s_{2}

Figure 4. There are four Coxeter elements in S_{4}, each yields a distributive lattice G_{c} of c-singletons.

The c-singletons form a distributive sublattice of the right weak order, see [3]. We denote the Hasse diagram of this poset by G_{c}, see Figure 4 for examples. They also form a sublattice of the c-Cambrian lattice.

There is an important linear isometry on V that fixes P and interchanges M(e) and M(w_{0}): the map g defined by v ⟼ w_{0}(v).

Reading proves in [7, Proposition 1.3] that the map w ⟼ ww_{0} is an antiisomorphism from the c-Cambrian lattice to the c^{−1}-Cambrian lattice. In particular, the map w ⟼ ww_{0} is an anti-isomorphism between the lattices of c-singletons and c^{−1}-singletons by restriction, that is, w is a c-singleton if and only if ww_{0} is a c^{−1}-singleton. Since the map w ↦ w_{0}ww_{0} is an isomorphism from the c-Cambrian lattice to the w_{0}cw_{0}-Cambrian lattice, the map w ↦ w_{0}w = (w_{0}ww_{0})w_{0} is an antiisomorphism from the c-Cambrian lattice to the w_{0}c^{−1}w_{0}-Cambrian lattice. In other words, ℋ_{(x,s)} is c-admissible for all s ∈ S if and only if ℋ_{(w_{0}x,s)} is w_{0}c^{−1}w_{0}- admissible for all s ∈ S. Therefore we obtain the following proposition.

Proposition 3.6. Let c be a Coxeter element of the finite Coxeter system (W, S). Then

Asso_{c}(W) = g (Asso_{w_{0}c^{−1}w_{0}}(W)) ,

that is, the generalized associahedra Asso_{c}(W) and Asso_{w_{0}c^{−1}w_{0}}(W) are isometric.

Let T be the reflections of W and I(w) be the inversions of w ∈ W defined as

T := ⋃_{w∈W} wSw^{−1} and I(w) := {t ∈ T | ℓ(tw) < ℓ(w)}.

A parabolic subgroup is a subgroup that is the conjugate of a standard parabolic subgroup of W. Given the Coxeter system (W, S) and a parabolic subgroup W′, there is a natural way to distinguish a set of simple generators of W′, see [6]. We shall only make use of the case that W′ is standard parabolic, in which case, the simple generators of W′ are simply W′ ∩ S.

Theorem 3.7. For w ∈ W and any Coxeter element c of W, the following statements are equivalent:

(i) w and ww_{0} are both c-singletons; (ii) w ∈ {e, w_{0}}; (iii) wcw^{−1} is a Coxeter element of W and wG_{c} = G_{wcw^{−1}}; (iv) wG_{c} = G_{c′} for some Coxeter element c′.

Proof. (i) ⇒ (ii): Suppose w and ww_{0} are c-singletons. A c-singleton u is csortable and c-antisortable by Proposition 2.2 of [3], that is, the element u is c-sortable and uw_{0} is c^{−1}-sortable. Hence w is c-sortable and c^{−1}-sortable. From [6, Theorem 4.1] we know that g ∈ W is c-sortable and c^{−1}-sortable if and only if I(g) ∩ (W′ \ {t_{1}}) ≠ ∅ implies t_{2} ∈ I(g) for any irreducible dihedral parabolic subgroup W′ of W (that is |W′| > 4) with simple generators t_{1}, t_{2} ∈ T.

Assume that w ≠ e. There exists s ∈ I(w)∩S. Pick t ∈ S such that the standard parabolic subgroup W′ generated by {s, t} is dihedral and of cardinality > 4. We first show that s, t ∈ I(w). We have to distinguish two cases:

(1) If I(w)∩(W′ \{s}) ≠ ∅ then t ∈ I(w) because w is c-sortable and c^{−1}-sortable. Hence s, t ∈ I(w).

(2) Assume I(w) ∩ (W′ \ {s}) = ∅. We first observe that I(ww_{0}) = I(w_{0}) \ I(w). Hence I(ww_{0}) ∩ (W′ \ {t}) ≠ ∅ which implies s ∈ I(ww_{0}) since ww_{0} is also csortable and c^{−1}-sortable. In particular, s ∈ I(w)∩I(ww_{0}) which is impossible.

Since (W, S) is irreducible, the Coxeter graph associated to (W, S) is connected. Now repeat this process along paths starting at s to conclude that S ⊆ I(w). Hence w = w_{0}.

(ii) ⇒ (iii): For w = e the result is clear. Recall that the conjugation by w_{0} is an automorphism φ of the Coxeter system (W, S). So the w_{0}cw_{0}-factorization of w_{0} is induced by φ from the c-factorization of w_{0}. The claim for w = w_{0} follows.

(iii) ⇒ (iv): Set c′ := wcw^{−1}.

(iv) ⇒ (i): Since e and w_{0} are c′-singletons, we conclude that w^{−1} and w^{−1}w_{0} are both c-singletons. Apply (i) ⇒ (ii) to deduce that w^{−1} = e or w^{−1} = w_{0}. In particular, w and ww_{0} are both c-singletons. □

Remark 3.8. Two maximal cones C and C′ in the c-Cambrian fan F_{c} are antipodal if C = −C′. Theorem 3.7 implies that a pair of antipodal maximal cones that correspond to c-singletons is unique and the corresponding elements are e and w_{0}.

4. Proof of Theorem 2.3

Assume there is an isometry φ on V such that Asso_{c_{1}}(W) = φ(Asso_{c_{2}}(W)). Let w be a c_{2}-singleton. Then

(1) M(w) = ⋂_{s∈S} H_{(w,s)} is a vertex of Asso_{c_{2}}(W),

(2) φ (M(w)) = ⋂_{s∈S} φ(H_{(w,s)}) is a vertex of Asso_{c_{1}}(W),

(3) φ (M(w)) = M(w′) for some c_{1}-singleton w′ since φ is an isometry. (For (3), note that c-singleton cones are the only cones in the Cambrian fan which consist of a single chamber from the Coxeter fan, and thus an isometry must take singleton cones to singleton cones.)

Apply these results to w = e to obtain a c_{1}-singleton w′_{e} with M(w′_{e}) = φ (M(e)). Moreover, w′_{e}w_{0} is also a c_{1}-singleton with M(w′_{e}w_{0}) = φ (M(w_{0})). Hence w′_{e} ∈ {e, w_{0}} by Theorem 3.7 and φ is a linear isometry of V that fixes P and either fixes M(e) and M(w_{0}) or interchanges M(e) and M(w_{0}). If φ fixes M(e) and P then there is an induced u-automorphism μ of the Coxeter graph of (W, S) by Proposition 3.2 and μ(c_{2}) = c_{1}. If φ interchanges M(e) and M(w_{0}), then we consider φ̃ := g ∘ φ. We have φ̃(Asso_{c_{2}}(W)) = Asso_{w_{0}c_{1}^{−1}w_{0}}(W) by Proposition 3.6 and φ̃ is an isometry that fixes P, M(e), and M(w_{0}). Hence φ̃ induces a uautomorphism μ of the Coxeter system (W, S) by Proposition 3.2 and we get μ(c_{2}) = w_{0}c_{1}^{−1}w_{0}.

Assume there is a u-automorphism μ of the Coxeter graph (W, S). Without loss of generality, we may assume that μ(c_{2}) = c_{1} because Asso_{c}(W) and Asso_{w_{0}c^{−1}w_{0}}(W) are isometric via g by Proposition 3.6.

We have to specify an isometry φ_{μ} on V such that φ_{μ}(Asso_{c_{2}}(W)) = Asso_{c_{1}}(W). This is done according to Proposition 3.4: Define φ_{μ} : V → V by φ_{μ}(α_{s}) := α_{μ(s)} for all s ∈ S or equivalently by φ_{μ}(v_{s}) := v_{μ(s)}.

It remains to show that φ_{μ} maps c_{2}-admissible halfspaces to c_{1}-admissible halfspaces. From Corollary 3.5 we know how the facet defining halfspaces ℋ_{(w,s)} are permuted by the isometry φ_{μ}, that is, φ_{μ}(ℋ_{(w,s)}) = ℋ_{(μ(w),μ(s))} for w ∈ W and s ∈ S. The automorphism μ on W preserves the length function ℓ, so we have μ(w_{0}) = w_{0} and any prefix of the c-factorization of w_{0} up to commutation is a prefix of the μ(c)-factorization of w_{0} up to commutation. In other words, μ induces a lattice isomorphism between the c_{2}-singletons and the μ(c_{2})-singletons. Hence ℋ_{(x,s)} is c_{2}-admissible if and only if ℋ_{(μ(x),μ(s))} is μ(c_{2})-admissible. This shows that φ_{μ}(Asso_{c}(W)) = Asso_{μ(c)}(W) and ends the proof of Theorem 2.3. □

Proof of Corollary 2.6. The assertion that (2) is equivalent to (3) is Theorem 2.3. That (2) implies (1) follows from the definition of normal fans.

Now we show that (1) implies (3). As the c-Cambrian fan F_{c} and the c′- Cambrian fan F_{c′} are isometric, there is an isometry φ such that the image under φ of each cone in F_{c} is a cone of F_{c′}. By Remark 3.8, the pair of antipodal singleton cones C(e), C(w_{0}) corresponding to e, w_{0} are the unique singleton antipodal cones in both Cambrian fans, and either φ fixes them or exchanges them. If u is balanced, then apply Corollary 3.5 with μ to be the conjugation by w_{0} to obtain

(1)  M(w_{0}) = ∑_{s∈S} κw_{0}(v_{s}) = ∑_{s∈S} κ(−v_{w_{0}sw_{0}}) = −M(e).

As C(e) is ℝ_{>0}-spanned by Δ^{∗} and C(w_{0}) is ℝ_{>0}-spanned by −Δ^{∗}, either φ fixes M(e) and M(w_{0}) or interchanges them. In both cases, φ(P) = P. So either φ or g ∘ φ fixes M(e) and P. Conclude by Proposition 3.2 as in the first part of the proof of Theorem 2.3. □

5. The reducible case

The reducible case does not follow immediately from an application of the irreducible case. Rather, one goes through the same steps as in the proof of the irreducible case, but with some slight added complication. We sketch the process below.

Let D denote the set of irreducible components of the Coxeter graph of (W, S). For any A ⊂ D, let w_{A} be the longest word for the subgroup generated by the components in A. Let L = {w_{A} | A ⊂ D}. All the elements of L are c-singletons (for any c).

Up to just before Proposition 3.6, the argument goes through in exactly the same way. Then, instead of constructing a single isometry g, we construct an isometry g_{A} for each A ⊂ D, defining g_{A}(v) = w_{A}(v). Write c^{A} for the Coxeter element obtained from c by reversing the order of the reflections in c coming from components in A. The generalization of Proposition 3.6 then asserts that Asso_{c}(W) = g_{A}(Asso_{w_{A}c^{A}w_{A}}(W)) and, in particular, these associahedra are isometric. Theorem 3.7 goes through with condition (ii) replaced by the condition that w ∈ L.

References

[1] F. Chapoton, S. Fomin and A. Zelevinsky, Polytopal realizations of generalized associahedra, Canad. Math. Bull. 45 (2003), 537–566.

[2] S. Fomin and A. Zelevinsky, Y-systems and generalized associahedra, Annals of Mathematics 158 (2003), 977–1018.

[3] C. Hohlweg, C. Lange, H. Thomas, Permutahedra and generalized associahedra,

   31 pages, 2007; arχiv:math.CO/0709.4241.

[4] J.E. Humphreys, Reflection groups and Coxeter groups, Cambridge University Press, 1990.

[5] J.-L. Loday, Realization of the Stasheff polytope, Arch. Math. 83 (2004), 267–278.

[6] N. Reading, Clusters, Coxeter-sortable elements and noncrossing partitions, 28 pages, 2005, to appear in Trans. Amer. Math. Soc.; arχiv:math.CO/0507186.

[7] N. Reading, Sortable elements and Cambrian lattices, Algebra Universalis 56(3-4) (2007), 411–437.

[8] N. Reading and D. Speyer, Cambrian fans, 40 pages, 2006; arχiv:math.CO/0606201.

[9] S. Shnider and S. Sternberg, Quantum groups: From coalgebas to Drinfeld algebras, Graduate texts in mathematical physics, International Press, 1994.

[10] J. Stasheff, Homotopy associativity of H-spaces I, II, Trans. Amer. Math. Soc. 108 (1963), 275–312.

[11] J. Stasheff, From operads to “physically” inspired theories, Operads: Proceedings of Renaissance Conferences (Hartford, CT/Luminy, 1995), Contemp. Math., 202, Amer. Math. Soc., 1997, pp. 53–81.

(Nantel Bergeron) Department of Mathematics and Statistics, York University, Toronto, Ontario, M3J 1P3, CANADA

 E-mail address: bergeron@mathstat.yorku.ca

(Christophe Hohlweg) Université du Québec à Montréal, LaCIM et Département de Mathématiques, CP 8888 Succ. Centre-Ville, Montréal, Québec, H3C 3P8, CANADA

 E-mail address: hohlweg.christophe@uqam.ca
 URL: http://www.lacim.uqam.ca/˜ hohlweg

(Carsten Lange) Freie Universität Berlin, Fachbereich für Mathematik und Informatik, Arnimallee 3, 14195 Berlin, GERMANY

 E-mail address: lange@math.tu-berlin.de

(Hugh Thomas) Department of Mathematics and Statistics, University of New Brunswick, Fredericton, New Brunswick, E3B 5A3, CANADA

 E-mail address: hugh@math.unb.ca