COMBINATORICS & TOPOLOGY OF STRATIFICATIONS OF

THE SPACE OF MONIC POLYNOMIALS WITH REAL COEFFICIENTS

BORIS SHAPIRO AND VOLKMAR WELKER^{1}

Abstract. We study the stratification of the space of monic polynomials with real coefficients according to the number and multiplicities of real zeros. In the first part, for each of these strata we provide a purely combinatorial chain complex calculating (co)homology of its one-point compactification and describe the homotopy type by order complexes of a class of posets of compositions. In the second part, we determine the homotopy type of the one-point compactification of the space of monic polynomials of fixed degree which have only real roots (i.e., hyperbolic polynomials) and at least one root is of multiplicity k. More generally, we describe the homotopy type of the one-point compactification of strata in the boundary of the set of hyperbolic polynomials, that are defined via certain restrictions on root multiplicities, by order complexes of posets of compositions. In general, the methods are combinatorial and the topological problems are mostly reduced to the study of partially ordered sets.

1Supported by DFG through “Habilitationsstipendium” 1479/4, work on the project was completed while the author was “General Member” of the MSRI 1996/97 program on combinatorics, research at MSRI is supported in part by NSF grant DMS-9022140

1991 Mathematics Subject Classification. Primary 06A07, 58C27. Secondary 57R45. Key words and phrases. Elliptic Polynomial, Hyperbolic Polynomial, Composition, Poset.

1. Introduction

Let f(X) = X^{n} + c_{n−1}X^{n−1} + ⋯ + c_{0} be a monic polynomial of degree n with coefficients in the real numbers. The space of all monic polynomials of degree n is homeomorphic to real n-space R^{n}. If we speak of R^{n} as the space of monic real polynomials of fixed degree n we denote it by Pol^{n}. We call f(X) a hyperbolic polynomial if all roots of f(X) are real. We call f(X) an elliptic polynomial if all roots of f(X) are complex (with non-vanishing imaginary part). In particular, an elliptic polynomial is of even degree. The terminology is borrowed from the theory of partial differential equations, see Hörmander’s book [18], where elliptic and hyperbolic polynomials in several variables are defined.

In this paper we are concerned with topological properties of strata from the stratification described below. We study the homotopy type and the homology of these spaces by combinatorial techniques. Some of these questions are reduced to the study of certain subcomplexes of the boundary complex of a simplex that are indexed by number-partitions.

1.1. Stratification. Let us describe a cellular decomposition of Pol^{n} whose cells are indexed by the compositions of numbers ≤ n. A composition π = (a_{1}, …, a_{t}) of a number l is an ordered tuple of positive integers such that a_{1} + ⋯ + a_{t} = l (i.e., a representation of l as an ordered sum). Let (a_{1}, …, a_{t}) be a composition of l. We denote by C_{l} the set of all compositions of the number l. We order the set C_{l} by the partial order “⪯” given by refinement (i.e., the minimal composititions greater than the composition (a_{1}, …, a_{t}) are of the form (a_{1}, …, a_{i−2}, a_{i−1} + a_{i}, a_{i+1}, …, a_{t}) for some 2 ≤ i ≤ t). If (a_{1}, …, a_{t}) is a composition of l then we denote by Hyp_{(a_{1},... ,a_{t})}^{n} the set of hyperbolic polynomials f(X) = (X −x_{1})^{a_{1}} ⋯ (X −x_{t})^{a_{t}} satisfying the strict inequalities x_{1} < ⋯ < x_{t}. By Hyp^{l} we denote the space of hyperbolic polynomials in Pol^{l}. It is a simple observation that Hyp^{l} is homeomorphic to R × R_{+}^{l−1}, where R_{+} denotes the space of real numbers ≥ 0. Thus Hyp_{(a_{1},... ,a_{t})}^{l} is an open t-dimensional cell in the closed subspace Hyp^{l} of R^{l}. Let us denote for an even number n by Ell^{n} the space of monic elliptic polynomials of degree n. Again, standard reasoning implies that Ell^{n} is homeomorphic to C^{\frac{n}{2}} . For an arbitrary number n and a composition π = (a_{1}, …, a_{t}) of some number l ≤ n with n − l even, – if n is even we allow l = 0 and π = () – we denote by Pol_{(a_{1},... ,a_{t})}^{n} the cell Hyp_{(a_{1},... ,a_{t})}^{l} × Ell^{n−l}. We call each Pol_{(a_{1},... ,a_{t})}^{n} a standard cell in Pol^{n}. For n even and π = () we obtain Pol_{π}^{n} = Ell^{n}. Now if π runs over all compositions of numbers l ≤ n with n − l even then the cells Pol_{π}^{n} stratify Pol^{n}.

In a next step we group the compositions of the number n into classes. A numberpartition λ = (λ_{1} ≤ ⋯ ≤ λ_{t}) of the number n is an ascending sequence of positive numbers such n = λ_{1} + ⋯ + λ_{t}. We use the notation λ = (1^{e_{1}}, …, n^{e_{n}}) to denote a number-partition consisting of e_{i} copies of i, 1 ≤ i ≤ n. One may regard a numberpartition as an equivalence class of compositions. A composition (a_{1}, …, a_{t}) is of type λ = (1^{e_{1}}, …, n^{e_{n}}) if there are exactly e_{i} numbers i among the numbers (a_{1}, …, a_{t}) for 1 ≤ i ≤ n. For a number-partition λ of n, we denote by Hyp_{λ}^{n} the closure of the union of all cells Hyp_{(a_{1},... ,a_{t})}^{n}, for (a_{1}, …, a_{t}) of type λ, in Hyp^{n}. For a numberpartition λ of a number l ≤ n such that n−l is even, we write Pol_{λ}^{n} for Hyp_{λ}^{l} ×Ell^{n−l}. We call each Pol_{λ}^{n} a standard stratum in Pol^{n}. In particular, if n is even and λ = () then Pol_{λ}^{n} = Ell^{n}.

The main results of the paper are :

• For a number-partition λ = (λ_{1} ≤ ⋯ ≤ λ_{t}) of a number l with n − l even, we describe the homotopy type of the one-point compactification of Pol_{λ}^{n} as a double suspension over another space whose topology is “essentially” described via the partially ordered set of compositions of numbers l ≤ n with n−l even and whose type is coarser than λ. In particular, the homotopy type of Pol_{λ}^{n} only depends on n and the combinatorics of λ. Then we present a chain complex calculating its cohomology.

• For a number-partition λ of n we describe the one-point compactification \begin{matrix} \\ Hyp & n λ \end{matrix} as a double suspension over the order complex of some partially ordered set of compositions. In case the number-partition λ is free of resonances (see Section 3.1) we also describe \begin{matrix} \\ Hyp & n λ \end{matrix} as a quotient of the permutahedron and give the homotopy type.

• The one-point compactification \begin{matrix} \\ Hyp & {n \atop (k,1^{n−k})} \end{matrix} of the space Hyp_{(k,1^{n−k})}^{n} of all hyperbolic polynomials with at least one kfold root is homotopic to a sphere or contractible.

Our attempts were motivated by results of Arnold [1], [2] and Vassiliev [25] on similarly defined spaces of real and complex polynomials. Spaces of rational functions with real coefficients appear in the realm of control theory. We refer the reader to the work of Brockett [8], the more recent results by Helmke [16], [17] and the references contained therein. The general flavor of our definitions is also influenced by the work of Björner [3] on arrangements of linear subspaces in R^{n} and in particular by the class of “orbit arrangements” defined in [3]. The strata Hyp_{λ}^{n} and Pol_{λ}^{n} may be regarded as “unordered analogs” of the arrangements introduced and studied by Björner.

Convexity properties of Hyp^{n} – in the coefficients of the polynomials as coordinates – have been studied rather intensively. We refer the reader to the papers by Meguerditchian [20] and Dedieu [11] and the references contained therein.

This work war started while the second author enjoyed the hospitality of KTH in Stockholm and finished while the first author was visiting the Max Planck Institute in Bonn. We thank both institutions and A. Björner at KTH for providing these opportunities. Finally, we are grateful to U. Helmke for his interest in our work and for providing helpful references.

2. Cohomology of 1-point compactification of Pol_{λ}^{n}

2.1. Adjacency of cells and strata. Let us describe combinatorially the closure of the standard cells Pol_{(a_{1},... ,a_{t})}^{n}. In order to pursue this program we introduce a partial order on the set C_{≤l} of all compositions of numbers m ≤ l with l − m even extending the partial order “⪯” on the compositions C_{m} ⊆ C_{≤l} for m ≤ l. Let us define the cover relation in C_{≤l}. A composition (a_{1}, …, a_{t}) covers a composition (b_{1}, …, b_{s}) if and only if either

• s = t + 1 and (b_{1}, …, b_{s}) arises from (a_{1}, …, a_{t}) by adding a block “2” (i.e., there is an 1 ≤ i ≤ s such that a_{j} = b_{j}, 1 ≤ j ≤ i − 1, b_{i} = 2, a_{j−1} = b_{j}, i + 1 < j ≤ s) or

• s = t − 1 and (b_{1}, …, b_{s}) arises from (a_{1}, …, a_{t}) by merging two neighboring

blocks (i.e., (a_{1}, …, a_{t}) ≺ (b_{1}, …, b_{s}) in C_{m}, m = ∑_{j=1}^{t} a_{j} = ∑_{j=1}^{s} b_{j}).

The partial order on C_{≤l} is the transitive closure of the above defined cover relation. Since this partial order coincides with the “usual” partial order “⪯” on each C_{m}, m ≤ l, we also denote this partial order by “⪯.” For a number-partition λ = (λ_{1} ≤ ⋯ ≤ λ_{t}) of m ≤ l with l − m even we denote by C_{λ,≤l} all compositions in C_{≤l} that are coarser than some composition of type λ in the order “⪯.”

Obviously, for any number-partition λ of m ≤ n with n − m even one has

Pol_{λ}^{n} = ⋃_{(a_{1},... ,a_{t})⪯(b_{1},... ,b_{s})} Pol_{(b_{1},... ,b_{s})}^{n},

where the union is over C_{λ,≤n}.

Proposition 2.1. Let (a_{1}, …, a_{t}), (b_{1}, …, b_{s}) ∈ C_{≤l} be compositions. The cell Pol_{(b_{1},... ,b_{s})}^{n} lies in the boundary of Pol_{(a_{1},... ,a_{t})}^{n} if and only if the corresponding compositions satisfy (b_{1}, …, b_{s}) ⪯ (a_{1}, …, a_{t}) in C_{≤l}.

Proof. This is obvious.

2.2. Homotopy Type. The homotopy type of the one-point compactification \begin{matrix} \\ Pol & {n \atop λ} \end{matrix} is described via a double suspension.

Consider the obvious action of the “positive” affine group Aff_{+}(R) = {X ↦ ρX + γ | ρ > 0, γ ∈ R} on the space of monic polynomials of even degree n by

X^{n} + c_{n−1}X^{n−1} + ⋯ + c_{0} ↦ \frac{((ρX + γ)^{n} + c_{n−1}(ρX + γ)^{n−1} + ⋯ + c_{0})}{ρ^{n}}.

Let Σ_{n} denote the one-parameter family of polynomials of the form (X +α)^{n}, α ∈ R.

Proposition 2.2. The action of Aff_{+}(R) on the space Pol^{n} \ Σ_{n} is free. The complement Pol^{n} \ Σ_{n} is homeomorphic to R × R^{+} × S^{n−2}, where S^{n−2} is the unit sphere in the space P̃ol^{n−1} of polynomials of the form X^{n} + c_{n−2}X^{n−2} + ⋯ + c_{0}.

Proof. Assume a polynomial f(X) = X^{n} + c_{n−1}X^{n−1} + ⋯ + c_{0} is stabilized by the map X → ρX + γ under the action of Aff_{+}(R). Then

c_{n−1} = \frac{c_{n−1} + γ}{ρ} ⇔ c_{n−1}(ρ − 1) = γ.

Thus if c_{n−1} = 0 then γ = 0. In this case c_{i} = \frac{c_{i}}{ρ^{n−i}}, 0 ≤ i ≤ n − 2. But this implies either ρ = 1 or c_{i} = 0, 0 ≤ i ≤ n − 2. Thus either f(X) ∈ Σ_{n} or ρX + γ = X. If c_{n−1} ≠ 0 then the image of f(X) under the transformation X ↦ X − \frac{c_{n−1}}{n} has coefficient 0 at the term X^{n−1}. Thus the stabilizer of f(X − c_{n−1}) is conjugate to the stabilizer of f(X). In particular, either f(X) = (X + α)^{n} or ρX + γ = X. For each element f(X) ∈ Pol^{n} \ Σ_{n} there is a unique element ρX + γ ∈ Aff_{+}(R) such that f(X)^{ρX+γ} = X^{n} + d_{n−1}X^{n−1} + ⋯ + d_{0} satisfies d_{n−1} = 0 and d_{n−2}^{2} + ⋯ + d_{0}^{2} = 1. To see this one realizes that d_{n−1} = 0 implies γ = c_{n−1}. Thus we may assume γ = c_{n−1} = 0. Then f(X)^{ρX} = X^{n} + \frac{c_{n−2}}{ρ^{2}} X^{n−2} + ⋯ + \frac{c_{0}}{ρ^{n}}. For ρ > 0 the function h(ρ) = (\frac{c_{n−2}}{ρ^{2}} )^{2}+⋯+(\frac{c_{0}}{ρ^{n}})^{2} is strictly decreasing. Since, lim_{ρ→0} h(ρ) = ∞ and lim_{ρ→∞} h(ρ) =

0 there is a unique ρ such that h(ρ) = 1. Thus, Pol^{n} \ Σ_{n} is a fibered over S^{n−2} with fiber R × R_{>0}. Since the fibration is trivial – the map (f(X), ρX + γ) ↦ f(X)^{ρX+γ} defines an homeomorphism S^{n−2}×Aff_{+}(R) ≅ Pol^{n}\Σ_{n} – the assertion follows.

Corollary 2.3.

(a) For every number-partition λ = (λ_{1} ≤ ⋯ ≤ λ_{t}) of a number l ≤ n with n − l even the space Pol_{λ}^{n} \ Σ_{n} is homeomorphic to R × R_{>0} × (Pol_{λ}^{n} ∩ S^{n−2}), where S^{n−2} is the unit sphere in the space P̃ol^{n} of monic polynomials of degree n with vanishing coefficient at X^{n−1}. In particular, Pol_{λ}^{n} \ Σ_{n} and Pol_{λ}^{n} ∩ S^{n−2} are homotopically equivalent.

(b) Pol_{λ}^{n} is homeomorphic to R × Cone(Pol_{λ}^{n} ∩ S^{n−2}), where Cone(Pol_{λ}^{n} ∩ S^{n−2}) is a cone over Pol_{λ}^{n} ∩ S^{n−2}.

Proof.

(a) This follows immediately from Proposition 2.2. Note that the fibration constructed in Proposition 2.2 respects the standard strata and cells – outside Σ_{n} –.

(b) If f(X) is a monic polynomial of degree n. Then lim_{ρ→+∞} f(X)^{ρX} = X^{n}. Thus

each Pol_{λ}^{n} is homeomorphic to a cone over Pol_{λ}^{n} ∩ S^{n−2} with apex X^{n}.

In the formulation of the next corollary we denote by Susp(X) the suspension of the space X.

Corollary 2.4. For every number-partition λ = (λ_{1} ≤ ⋯, λ_{t}) of a number l ≤ n the one-point compactification \begin{matrix} \\ Pol & {n \atop λ} \end{matrix} is the one-point compactification (i.e., the Thom space) of the trivial bundle R × Σ(Pol_{λ}^{n} ∩ S^{n−2}). In particular, \begin{matrix} \\ Pol & {n \atop λ} \end{matrix} is homotopic to the wedge

S^{1} ∨ Susp(Susp(Ell^{n,λ} ∩ S^{n−2})).

Proof. By Corollary 2.3 the space Pol_{λ}^{n} is homeomorphic to R×Cone(Pol_{λ}^{n} ∩S^{n−2}). Therefore, \begin{matrix} \\ Pol & {n \atop λ} \end{matrix} can be obtained by a sequence of two one-point compactifications

(R × Cone(Pol_{λ}^{n} ∩ S^{n−2}) ) . The one-point compactification of Cone(Pol_{λ}^{n} ∩ S^{n−2})

is Susp(Pol_{λ}^{n} ∩ S^{n−2}), since Pol_{λ}^{n} ∩ S^{n−2} is closed and compact. Thus \begin{matrix} \\ Pol & {n \atop λ} \end{matrix} is homeo-

morphic to (R × Susp(Pol_{λ}^{n} ∩ S^{n−2})) . The one-point compactification of a cylinder over a compact (non-empty) set X is homotopic to a wedge of a circle and the suspension over X. This implies the rest of the assertion.

2.3. (Co)chain complex. Let us now describe combinatorially a (co)-chain complex for the calculation of the (co)-homology of Pol_{λ}^{n} – or, equivalently by Corollary 2.4 modulo a twofold shift the (co)-homology of Pol_{λ}^{n} ∩ S^{n−2}.

Let us introduce the following orientation on Pol_{(a_{1},... ,a_{t})}^{n} given by the top differential form

ξ = du_{1} ∧ dv_{1} ∧ ⋯ ∧ du_{(n−∑ a_{i})} ∧ dv_{(n−∑ a_{i})} ∧ dx_{1} ∧ ⋯ ∧ dx_{t}.

The notation is chosen in the following way. Let F (X) = g(X)h(X) be a polynomial in Pol_{(a_{1},... ,a_{t})}^{n}, where g(X) ∈ Hyp_{(a_{1},... ,a_{t})}^{l} is an hyperbolic polynomial of degree l and h(X) elliptic of degree n − l. Then we denote by u_{i} and v_{i} the real and the imaginary part (assumed positive) of complex conjugate zeros of h(X) and by x_{i} the roots of g(X). Note, that the form does not depend on the order of pairs of conjugate roots. For each cell Pol_{(a_{1},... ,a_{t})}^{n} we call the orientation given by ξ the standard orientation. We write Pol_{(a_{1},... ,a_{t})}^{n,ξ} to denote the cell Pol_{(a_{1},... ,a_{t})}^{n} oriented by the standard orientation.

Having fixed the above orientations of strata we describe the boundary operator in terms of the incidence coefficients.

Proposition 2.5. Let (a_{1}, …, a_{t}) ⪯ (b_{1}, …, b_{t+1}) be two compositions in C_{≤n}. Assume a_{i} = b_{i}, 1 ≤ i ≤ l, a_{i} = b_{i+1}, l + 1 ≤ i ≤ t, b_{l+1} = 2. Let j_{1} ≤ l be the minimal index such that b_{j_{1}} = ⋯ = b_{l+1} = 2 and let j_{2} be the maximal index such that b_{l+1} = ⋯ = b_{j_{2}} = 2. Then:

(i) dim(Pol_{(a_{1},... ,a_{t})}^{n}) = dim(Pol_{(b_{1},... ,b_{t+1})}^{n}) + 1 and Pol_{(b_{1},...,b_{t+1})}^{n} lies in the boundary ∂Pol_{(a_{1},...,a_{t})}^{n}.

(ii) The coefficient of Pol_{(b_{1},... ,b_{t+1})}^{n,ξ} in the expansion of ∂Pol_{(a_{1},... ,a_{t})}^{n,ξ} equals 0 if j_{2}−j_{1} is even and (−1)^{j_{1}−1} if j_{2} − j_{1} is odd.

Proof.

(i) This follows from Proposition 2.1 and the fact that in Pol_{(b_{1},... ,b_{t+1})}^{n} we impose one additional condition on the set of roots.

(ii) Take a generic polynomial f(X) ∈ Pol_{(b_{1},... ,b_{t+1})}^{n} and a sufficiently small neighborhood O_{f} ⊂ Pol_{(b_{1},... ,b_{t+1})}^{n}. Then O_{f} lies in the boundary of j_{2} − j_{1} different neighborhoods O_{f}^{1} ⊂ Pol_{(a_{1},... ,a_{t})}^{n}, …, O_{f}^{j_{2}−j_{1}} ⊂ Pol_{(a_{1},... ,a_{t})}^{n}. For 1 ≤ i ≤ j_{2} − j_{1} the neighborhood O_{f}^{i} is obtained by splitting the double root corresponding to the part a_{i} in the composition (a_{1}, …, a_{t}) into complex conjugate roots for all polynomials from O_{f}. Then the coefficient of O_{f} in the expansion of ∂O_{f}^{i} is (−1)^{i−1}. Indeed, O_{f} ⊆ ∂O_{f}^{i} with the orientation

dx_{i} ∧ du_{1} ∧ dv_{1} ∧ ⋯ ∧ du_{(n−∑ a_{i})} ∧ dv_{(n−∑ a_{i})} ∧ dx_{1} ∧ ⋯ ∧ d̂x_{i} ∧ ⋯ ∧ dx_{t}.

Note, that by the definition of the standard orientation the orientation of O_{f} ⊆ ∂O_{f}^{i} does not depend on the choice of the complex root that is split. This orientation differs from the standard orientation by (−1)^{i−1}. Taking the sum over all i then implies the assertion.

Again fixing (a_{1}, …, a_{t}) let us denote by (a_{1}, …, a_{i−1}, a_{i} + a_{i+1}, a_{i+2}, …, a_{t}) the sequence of length t−1 obtained by merging a_{i} and a_{i+1}. Then the standard stratum Pol_{(a_{1},... ,a_{i−1},a_{i}+a_{i+1},a_{i+2},... ,a_{t})}^{n} lies in the boundary of Pol_{(a_{1},... ,a_{t})}^{n} and

dim(Pol_{(a_{1},... ,a_{t})}^{n}) = dim Pol_{(a_{1},... ,a_{i−1},a_{i}+a_{i+1},a_{i+2},... ,a_{t})}^{n} + 1.

Proposition 2.6. The coefficient of Pol_{(a_{1},... ,a_{i−1},a_{i}+a_{i+1},a_{i+2},... ,a_{t})}^{n,ξ} in the expansion of ∂Pol_{(a_{1},... ,a_{t})}^{n,ξ} equals (−1)^{i}.

Proof. As defined the orientation of strata and differential coincides with the the usual orientation of faces and differential of the boundary of an n − 1-simplex.

Now we are in position to state the main result of this section.

Theorem 2.7. Let λ = (λ_{1} ≤ ⋯ ≤ λ_{t}) be a number-partition of a number l ≤ n with n − l even.

(a) The homology of Pol_{λ}^{n} ∩ S^{n−2} coincides with homology of the chain complex given by the cells Pol_{(a_{1},... ,a_{t})}^{n,ξ}, for (a_{1}, …, a_{t}) ∈ C_{λ,≤n}, as generators and with the differential given in Propositions 2.5 and 2.6.

(b) The homology of \begin{matrix} \\ Pol & {n \atop λ} \end{matrix} equals the homology of the chain complex given by the cells Pol_{(a_{1},... ,a_{t})}^{n,ξ}, for (a_{1}, …, a_{t}) ∈ C_{λ,≤n}, as generators and with the differential given in Propositions 2.5 and 2.6 shifted twice to the right.

Proof. The assertion follows immediately from Proposition 2.5, Proposition 2.6 and Corollary 2.4.

The next figure illustrates the chain complex for λ = (4) in the space of monic polynomials of degree n = 16.

Figure 1 : The poset C_{(8),≤16}

2.4. Stabilization of standard strata. Let us briefly discuss the properties of Pol_{λ}^{n} for a given λ and varying n. Obviously, there is an inclusion of closures Pol^{n} ⊂ Pol^{m} for n < m and m − n even by multiplying each f(X) ∈ Pol^{n} by (x^{2} + 1)^{\frac{(m−n)}{2}} . By considering the above complex for calculation of H_{∗}(\begin{matrix} \\ Pol & {n \atop λ} \end{matrix}) one sees by Alexander duality that the cohomology of the complement H^{∗}(Pol^{n} \ Pol_{λ}^{n}) stabilizes. This

stabilization is apparently induced by the above inclusion and for 2∑_{i=1}^{t} λ_{i} − t > 2

one gets stabilization of the homotopy groups as well. Probably the most interesting detail of this stabilization is that one gets a universal infinite purely combinatorial cell (or chain) complex for the calculation of H^{∗}(Pol^{∞} \ Pol_{λ}^{∞}). The cells in this complex are index by compositions in C_{λ,<∞} = ⋃_{l<∞} C_{λ,≤l} (the case λ = (3, 2) is illustrated in

Figure 2).

Figure 2 : The poset C_{(2,3),<∞}

The situation with the stabilization resembles the one considered in [2] and [25]. One can speculate if the above infinite universal complex associated to each numberpartition has another interpretations.

3. Hyperbolic Polynomials, partitions and compositions

In this section we will study the special case of the standard strata Hyp_{λ} consisting of hyperbolic polynomials. Before we begin with the study of the spaces Hyp_{λ} we have to introduce some notions and facts about the combinatorics of compositions and partitions.

3.1. Combinatorics of compositions. Let δ^{n} be the boundary complex of the nsimplex (i.e., the simplicial complex spanned by the (n − 1)-dimensional faces of the n-simplex). In particular, δ^{n} ≅ S^{n−1}. We fix an arbitrary bijection φ(·) of the (n+1) maximal simplices of δ^{n} and the collection of set-partitions

{|1| ⋯ |i i + 1| ⋯ |n + 2| | 1 ≤ i ≤ n + 1}.

Thus we have labeled each maximal simplex τ of δ^{n} by a set-partition φ(τ).

Set-partitions are ordered by refinement (i.e., a set-partition τ = B_{1}| ⋯ |B_{t} of [n] is less than a set-partition σ = C_{1}| ⋯ |C_{s} of [n] if for all 1 ≤ i ≤ t there is an index 1 ≤ j ≤ s such that B_{i} ⊆ C_{j}). We write τ ⪯ σ if τ is less than σ. It is a well known fact that the partially ordered set Π_{n} of all set-partitions of [n] ordered by “⪯” is a lattice (i.e., the supremum operation – denoted by “∨” – and the infimum operation – denote by “∧” – are well defined).

The labeling φ of the (n − 1)-dimensional faces induces a labeling of all simplices of δ^{n} by assigning to a simplex σ the join ⋁ ; \begin{matrix}σ ⊆ τ \\ dim(τ) = n − 1 \end{matrix} φ(τ) in the lattice Π_{n+2}

of set-partitions of the set [n + 2].

Lemma 3.1.

(i) Let π be a set-partition of [n]. Then the following are equivalent:

(a) After possibly reindexing the blocks we have π = B_{1}| ⋯ |B_{t} and max(B_{i}) < min(B_{i+1}), 1 ≤ i ≤ t − 1.

(b) π = ⋁_{σ∈Γ}φ(σ) for some set Γ of (n − 3)-simplices in δ^{n−2}.

(ii) Let Γ_{1} and Γ_{2} be two subsets of the set of (n − 3)-simplices in δ^{n−2}. Then the following are equivalent :

(a) Γ_{1} = Γ_{2}.

(b) ⋂_{σ∈Γ_{1}}σ = ⋂_{σ∈Γ_{2}}σ.

(c) ⋁_{σ∈Γ_{1}}φ(σ) = ⋁_{σ∈Γ_{2}}φ(σ).

Proof.

(i) If π = B_{1}| ⋯ |B_{t} then define Γ by σ ∈ Γ if and only if there exists an 1 ≤ l ≤ n and i, i + 1 ∈ B_{l} such that φ(σ) = |1| ⋯ |i i + 1| ⋯ |n|. Then ⋁_{σ∈Γ}φ(σ) = π. The

converse is obvious from the definitions. (ii)

(a) ⇔ (b) This is easily seen from the the fact that the face lattice of the simplex is isomorphic to the Boolean lattice (see also Remark 3.2 below).

(a) ⇒ (c) This is obvious.

(c) ⇒ (a) If B is a block of ⋁_{σ∈Γ_{1}}φ(σ). Then for i < j ∈ B there must be simplices

σ_{i}, …, σ_{j−1} such that φ(σ_{l}) = |1| ⋯ |l l + 1| ⋯ |n| for i ≤ l ≤ j − 1. But

this implies that ⋁_{σ∈Γ_{1}}φ(σ) determines Γ_{1}.

We call a set-partition a composition if it satisfies one of the two equivalent conditions of Lemma 3.1 (ii). This definition does not conflict with the definition of composition given in the introduction. There is a natural bijection sending a setpartition of [n] which is a composition to a composition of the integer n in the usual sense. Namely, let B_{1}, …, B_{n} be the reordering of the blocks of a composition π such that max(B_{i}) < min(B_{i+1}), then we map π to the composition n = |B_{1}| + ⋯ + |B_{t}|. By C_{n} we denote the partially ordered set – poset for short – of compositions of n ordered by refinement (i.e., by the ordering induced from the usual ordering “⪯” of the lattice Π_{n}). Let λ be an number-partition of n. We denote by C_{λ} the join-semilattice of C_{n} spanned by the compositions π of type λ in C_{n}. Of course C_{n+2} = C_{λ} for λ = (2, 1^{n−2}).

Now we need to introduce some basic material from the theory of partially ordered sets and its order complexes. There is a canonical way to associate to a poset P a simplicial complex Δ(P). The complex Δ(P) is the complex of all chains x_{0} < ⋯ < x_{n} in P and is called the order complex of P.

If Δ is a simplicial complex. Then Δ may be regarded as a poset ordered by inclusion of faces. The order complex Δ(Δ) is the barycentric subdivision of Δ and hence Δ(Δ) is homeomorphic to Δ. Note that we assume ∅ ∉ Δ for a simplicial complex Δ.

By δ_{λ} we denote simplicial complex spanned by the faces τ of δ^{n−1} such that φ(τ) is of type λ.

Remark 3.2.

(i) The Boolean lattice B_{n−1}, the lattice C_{(1^{n−2},2)} and the face lattice of δ^{n−1} = δ_{(1^{n−2},2)} are isomorphic lattices.

(ii) The simplicial complex δ_{λ} is homeomorphic to a sphere for λ = (1, 2^{n−2}).

More delicate is the situation for λ ≠ (1^{n−2}, 2). Before we can proceed, we need some basic tools to manipulate posets preserving the homotopy type. By a map f : P → Q of posets we understand an order preserving map (i.e., x ≤ y implies f(x) ≤ f(y)). A map f : P → P of a poset into itself is called a closure operator if f(x) ≥ x and f(f(x)) = f(x). The following lemma is a standard tool in topological combinatorics, we refer the reader for references, proofs and further result to the excellent survey by Björner [4].

Lemma 3.3. Let P be a poset and let f : P → P be a morphism of posets such that f(x) ≥ x and f ∘ f = f. Then Δ(P) and Δ(f(P)) are homotopy equivalent.

Now we are position to state the lemma.

Lemma 3.4. The lattice C_{λ} is homotopy equivalent to the simplicial complex δ_{λ}.

Proof. Let us regard δ_{λ} as a partially ordered set, ordered by reversed inclusion. Then Δ(δ_{λ}) ≅ δ_{λ} (recall, Δ(δ_{λ}) is the barycentric subdivision of δ_{λ}). For any σ ∈ δ_{λ} let f(σ) be the union of all maximal simplices of δ_{λ} containing σ. Then

• f(σ) ≥ σ, • τ ≤ σ implies f(τ) ≤ f(σ),

• f(f(σ)) = f(σ).

Hence f is a closure operator on the partially ordered set δ_{λ}. Then by Lemma 3.3 it follows that f induces a homotopy equivalence onto its image. But the image of f is by Lemma 3.1 isomorphic to C_{λ}.

3.2. Stratification and (co)-homology. The following result links the combinatorics of δ_{λ} and C_{λ} to the topology of the space \begin{matrix} \\ Hyp & n λ \end{matrix}.

Theorem 3.5. Let λ be a number-partition of n. Then:

(a) The one-point compactification \begin{matrix} \\ Hyp & n λ \end{matrix} is homeomorphic to the double suspension over δ_{λ}. In particular, the homeomorphism type of \begin{matrix} \\ Hyp & n λ \end{matrix} depends only on the combinatorics of λ.

(b) The one-point compactification \begin{matrix} \\ Hyp & n λ \end{matrix} is homotopic to to the double suspension over Δ(C_{λ}). In particular, if C_{λ} ≅ C_{λ′} for two number-partitions λ of nand λ′

of m then \begin{matrix} \\ Hyp & n λ \end{matrix} ≃ \begin{matrix} \\ Hyp & {m \atop λ′} \end{matrix}.

Proof. From part (a) the assertion (b) follows immediately by Lemma 3.4. Thus it remains to verify part (a) of the assertion. We recall, that Hyp^{n} is homeomorphic to a closed simplicial (n − 1)-cone R_{+}^{n−1} times a copy of R. Thus Hyp_{λ}^{n} is the cone over Hyp_{λ}^{n} ∩ S_{+}^{n−2} times a copy of R. Here S_{+}^{n−2} denotes the positive part of the the unit sphere in R^{n−1} (i.e., S^{n−2} ∩ R_{+}^{n−1}. The one-point compactification of Cone(Hyp_{λ}^{n} ∩ S_{+}^{n−2}) is the suspension over Hyp_{λ}^{n} ∩ S_{+}^{n−2}. The one-point compactification of R ×

{ \atop Hyp_{λ}^{n} ∩ S_{+}^{n−2}} is the suspension over (Cone(Hyp_{λ}^{n} ∩ S_{+}^{n−2})) . Since

(R × { \atop Hyp_{λ}^{n} ∩ S_{+}^{n−2}}) ≅ \begin{matrix} \\ Hyp & n λ \end{matrix},

the assertion follows one we have identified Hyp_{λ}^{n} ∩ S_{+}^{n−2} with δ_{λ}.

The intersection of the (n−1)-cone R_{+}^{n−1} with S^{n−2} is an (n−2)-simplex. Its interior corresponds to n-tuples x_{1} < ⋯ < x_{n} of strictly ascending positive real numbers (on S^{n−2}). Its maximal faces correspond to tuples x_{1} < ⋯ < x_{i} = x_{i+1} < ⋯ < x_{n} with exactly one equality. In particular, they are naturally labeled by compositions |1| ⋯ |i i + 1| ⋯ |n|. This in turn establishes the desired homeomorphism of Hyp_{λ}^{n} ∩ S_{+}^{n−2} with δ_{λ}.

Now, we describe combinatorially the inclusion C_{λ} ↪ B_{n−1} that is induced by a fixed isomorphism C_{(1^{n−2},2)} ≅ B_{n−1}. First we identify the composition n = a_{1} + a_{2} + ⋯ + a_{t} with the subset A of all elements i of [n − 1] such that a_{1} + ⋯ + a_{j} ≤ i ≤ a_{1} + ⋯ + a_{j+1} − 1 for some 0 ≤ j ≤ t − 1 – the sum over the empty index set is treated as 0. Let us denote this map between C_{(1^{n−2},2)} by γ. Obviously, γ is order preserving and bijective. Thus γ induces the desired isomorphism between B_{n−1} and C_{(1^{n−2},2)}. Let us study the restriction of γ to C_{λ} for λ different from (1^{n−2}, 2). Let λ be a number-partition of n. We say that a subset A of [n − 1] is of type λ if its preimage under γ is a composition of type λ. In particular, the subsets of type (1^{n−2}, 2) are the singleton subsets of [n − 1]. For λ = (1^{n−k}, k) the subsets of λ are the k − 1 element subsets of [n − 1] consisting of k − 1 consecutive numbers. More generally, our considerations so far imply.

Lemma 3.6. C_{λ} is isomorphic to the join-subsemilattice of B_{n−1} that is generated by all subsets of [n − 1] of type λ.

If n = a_{1} + ⋯ + a_{t} is a composition for a number n there may possibly be more than two ways of expressing a number l ≤ n as a sum using the parts a_{1}, …, a_{t}. For example take the composition 4 = 2 + 1 + 1 then 2 = 1 + 1 is such an identity that holds within the given composition. An identity n_{1} + ⋯ + n_{r} = m_{1} + ⋯ + m_{s} is called primitive partition identity (see for example Sturmfels’ book [23, Chap. 6]), if n_{i} ≠ m_{j} for 1 ≤ i ≤ r and 1 ≤ j ≤ s. We say that a composition n = a_{1} + ⋯ + a_{t} is free of resonances if there is no primitive partition identity ∑_{i∈I} a_{i} = ∑_{j∈J} a_{j}, for

disjoint non-empty subsets I, J of [t]. Clearly, the property of being free of resonances only depends on the type of the composition. So one may as well apply “free of resonances” to number-partitions. For the description of the Δ(C_{λ}) in case λ is free of resonances, we use an important class of polytopes. The permutahedron P_{t} is the (t − 1)-dimensional polytope – for us the polytope is the sphere subdivided by the polytope – spanned in R^{t} be the the vectors (σ(1), …, σ(t)) for σ ∈ S_{t} (note that all these points lie on the hyperplane x_{1} + ⋯ + x_{t} = \frac{t(t−1)}{2}. Alternatively, the permutahedron allows the following description. Let A_{t} = {H_{ij} : x_{i} = x_{j} | 1 ≤ i < j ≤ t} be the arrangement (i.e., finite set) of reflecting hyperplanes of the Coxeter group S_{t} in R^{t}. Let H : x_{1} + ⋯ + x_{t} = 0 be the hyperplane orthogonal to the line x_{1} = ⋯ = x_{t}. Then the arrangement triangulates the intersection S^{t−2} of H with the unit sphere in R^{t}. Let Δ_{t} be this triangulation of S^{t−2}. Then let P_{t} the cellular dual of Δ_{t} (i.e., the cellular complex constructed by replacing cells of dimension i in Δ_{t} by a cell of dimension t − 2 − i preserving adjacency; see the book by Björner, Las Vergnas, Sturmfels, White & Ziegler [5] for more details on permutahedra). One easily checks that the cellular dual of a polytope again can be realized as a polytope, thus P_{t} is indeed a polytope. We denote by L_{t} the poset of faces of P_{t} ordered by reverse inclusion. Again it is a well known fact that L_{t} is S_{t}-isomorphic to the poset of cosets of Young-subgroups ≠ S_{t} of S_{t} ordered by inclusion. In general if P is a poset on which a group G acts as a group of (poset)-automorphisms then we denote by P/G the poset on the set of orbits x^{G} = {x^{g} | g ∈ G} whose order relation is given by x^{G} ≤ y^{G} :⇔ ∃ g ∈ G : x^{g} ≤ y.

Proposition 3.7. Let λ = (1^{e_{1}}, …, n^{e_{n}}) be a number-partition of n that is free of resonances. Let H = S_{e_{1}} × ⋯ × S_{e_{n}} be the corresponding Young-subgroup of S_{t}, t = e_{1} + ⋯ + e_{n}. Then:

(i) The poset C_{λ} is isomorphic to the lattice of cells of the quotient P_{t}/H of the permutahedron P_{t}. In particular, C_{λ} is homotopic to P_{t}/H.

(ii) If 0 ≤ e_{i} ≤ 1 then C_{λ} is S_{t}-isomorphic to the face lattice of the permutahedron

P_{t}, t = e_{1} + ⋯ + e_{n}. The order complex Δ(C_{λ}) triangulates an (t − 2)-sphere. (iii) If e_{i} ≥ 2 for some i then P_{t}/H and Δ(C_{λ}) are contractible.

Proof.

(i) By the second description of the permutahedron given above, the quotient of the permutahedron P_{t} by a Young-subgroup S_{b_{1}} × ⋯ × S_{b_{f}} is homeomorphic to the closure of the intersection of P_{t} with a fundamental domain C of the Coxeter group S_{b_{1}} × ⋯ × S_{b_{f}} in R^{t}. Thus if F is a (closed) face of P_{t} that intersects the fundamental domain C then the image of F under the projection map P_{t} → P_{t}/H is F ∩ \overline{C}. Thus the images of the (closed) faces of P_{t} under the action of H are ordered along the orbits poset of the poset L_{t} under the action of H.

If X is a CW-complex that is stratified into closed cells C_{p}, p ∈ P for a poset P, such that:

(a) The set {C_{p} | p ∈ P } is closed under taking intersections.

(b) The order relation in P is the reversed inclusion relation on {C_{p} | p ∈ P }. Then X ≃ Δ(P). Since (a) and (b) are satisfied for X = P_{t}/H and P = L_{t}/H the assertion follows once we have verified that C_{λ} is isomorphic to L_{t}/H.

Obviously, if a_{1} + ⋯ + a_{t} is a composition of type λ and σ, τ ∈ S_{t} are permutations then a_{σ(1)} + ⋯ + a_{σ(t)} is a composition different from a_{τ(1)} + ⋯ + a_{τt} if and only if στ^{−1} ∉ H. Thus the minimal elements of C_{λ} and the minimal elements of L_{t}/H are in bijection. Assume, we are given a composition b_{1} + ⋯ + b_{s} in C_{λ}. Let σ, τ be two permutations such that a_{σ(1)} + ⋯ + a_{σ(t)} and a_{τ(1)} + ⋯ + a_{τ(t)} are finer than b_{1} + ⋯ + b_{s}. Since there are no resonances, it follows that σ and τ must lie in the same H orbit on the cosets of S_{b_{1}} ×⋯×S_{b_{s}} in S_{t}. Conversely, if σ and τ lie in the same H-orbit on the cosets of S_{b_{1}}×⋯×S_{b_{s}} in S_{t} but in different cosets of H in S_{t} then a_{σ(1)} + ⋯ + a_{σ(t)} and a_{τ(1)} + ⋯ + a_{τ(t)} are different. This induces a bijection between the minimal elements below c_{1} + ⋯ + c_{s} in C_{λ} and the minimal elements below an H orbit on the cosets of S_{b_{1}} × ⋯ × S_{b_{s}} in S_{t}. Since in C_{λ} and L_{t}/H each element is the supremum of all minimal elements below it, the assertion follows.

(ii) If H = 1 then L_{t}/H = L_{t} and P_{t}/H = P_{t}. Thus P_{t}/H and Δ(C_{λ}) triangulate a (t − 2)-sphere.

(iii) If e_{i} ≥ 2 for some e_{i} then the intersection of P_{t} with the fundamental domain C (i.e., a convex cone) is homeomorphic to a (t − 2)-ball. Thus C_{λ} is contractible.

Theorem 3.8. Let λ = (1^{e_{1}}, …, n^{e_{n}}) be a number-partition of n that is free of resonances. Then \begin{matrix} \\ Hyp & n λ \end{matrix} is contractible if e_{i} ≥ 2 for some i and homeomorphic to an (e_{1} + ⋯ + e_{n})-sphere if 0 ≤ e_{i} ≤ 1, 1 ≤ i ≤ n.

Proof. The assertion follows immediately from Proposition 3.7 and Theorem 3.5. Note that the suspension of a i-sphere is homeomorphic to an (i + 1)-sphere.

We come to explicit results on the homotopy type for special classes of numberpartitions λ. We consider number-partitions λ = (1^{n−k}, k), 2 ≤ k ≤ n. In this case the subsets of [n − 1] of type λ are intervals themselves. Thus C_{λ} is isomorphic to the sub-poset of B_{n−1} that is generated by the intervals [(k − 1) · t + 1, (k − 1) · (t + 1)] for 0 ≤ t ≤ ⌊\frac{n}{(k−1)}⌋. In general, a join-sublattice L of B_{n} is called interval generated

if there is a set I of intervals I = {[a_{i}, b_{i}] | i = 1, …, t} such that L is generated by the elements of I. Interval generated sublattices of B_{n} have been introduced and studied by Greene [15]. Recently the method of non-pure shellability, a concept due to by Björner & Wachs [7], [6], allowed to compute in [6] the homotopy type of the lattice of intervals generated by all (k − 1)-element subsets of [n − 1].

Proposition 3.9. [6, Theorem 8.2, Corollary 8.4] Let λ = (1^{n−k}, k). Then,

Δ(C_{(1^{n−k},k)}) ≃ \{ \begin{matrix}S^{2(n−1)/k−2}, & if & n ≡ 1 & (mod k), \\ S^{2n/k−3}, & if & n ≡ 0 & (mod k), \\ pt., & otherwise. \end{matrix}

Proof. By Lemma 3.6 the poset C_{(1^{n−k},k)} is isomorphic to the join-subsemilattice of B_{n−1} generated by all intervals of length k −1. Now by the result of Björner & Wachs [6, Theorem 8.2, Corollary 8.4] the assertion follows.

Corollary 3.10. Let λ = (1^{n−k}, k). Then

\begin{matrix} \\ Hyp & n λ \end{matrix} ≃ \{ \begin{matrix}S^{2(n−1)/k}, & if & n ≡ 1 & (mod k), \\ S^{2n/k−1}, & if & n ≡ 0 & (mod k), \\ pt., & otherwise. \end{matrix}

Proof. The assertion follows immediately from Proposition 3.9 together with Theorem 3.5.

Finally, we would like to provide the results of some computer computations using a program package for Mathematica^{\begin{matrix}c \\ ◯ \end{matrix}} written by Vic Reiner. For the parameters λ = (1^{n−4}, 2^{2}), n ≤ 9, λ = (1^{n−6}, 3^{2}) for n ≤ 11 all homology of Δ(C_{λ}) vanishes. For λ = (a, b, c, d), a < b < c < d, with a + b = c, b + c = d as the only primitive partition identities, homology is free of rank 3 and concentrated in dimension 2. For λ = (a, b, c, d), a < b < c < d, with a + b + c = d as the only primitive partition identity, homology is free of rank 1 in dimensions 1 and 2.

3.3. Iterated compositions. One may regard the consideration of hyperbolic polynomials as the 1-dimensional case of a general situation. To understand the general philosophy, one has to regard Hyp^{n} as the space of unordered point configurations (i.e., configurations of roots) on the real line R^{1}. The essential combinatorial ingredient for the 1-dimensional case – compositions – will prevail to be important in higher dimensions too. Most of what follows now is a translation of Section I.3.3 of Vassiliev’s book [25] into the language of posets and compositions. Let d ≥ 1 be some number. The orbit space (R^{d})^{n}/S_{n} admits the following cell decomposition. An iterated-composition of degree d of the number n is a d-tuple (π_{1} ⪯ ⋯ ⪯ π_{d}) of compositions of n. We order the iterated compositions of n of degree d by the order induced by the lexicographic order on d-tuples of compositions. By C_{n}^{d} we denote the poset of iterated compositions of n of degree d.

Proposition 3.11. The poset C_{n}^{d} of iterated compositions of n of degree d is isomorphic to a direct product of n − 1 chains of cardinality d + 1.

Proof. We already know that the poset of compositions C_{n}^{1} = C_{n} is isomorphic to the Boolean lattice B_{n−1}. Thus the assertion follows for the case d = 1. Let π_{i}, i = 1, …, n be the atoms of the lattice of compositions of [n]. Let ˆ0 be the least element of the lattice of compositions of n. Then we define chains c_{i} : x_{i,0} < ⋯ < x_{i,d} by setting

x_{i,j} = (\underbrace{ˆ0 ⪯ ⋯ ⪯ ˆ0}_{d−j times} ⪯ \underbrace{π_{i} ⪯ ⋯ ⪯ π_{i}}_{j times}).

Now one checks that C_{n+1}^{d} ≅ c_{1} × ⋯ × c_{n−1}.

To each iterated composition π of n of degree d one associates (see Vassiliev’s book [25, II,3.3]) a cell c(π) in (R^{d})^{n}/S_{n}. Namely, let π = (π_{1} ⪯ ⋯ ⪯ π_{d}) be an iterated composition of n of degree d. The element \underline{x} = (x_{1}, …, x_{d}) ∈ (R^{d})^{n}/S_{n} is an element of c(π) if and only if

(i) for every pair i, j of elements which lie in the same block of π_{s} for some 1 ≤ s ≤ d the coordinates x_{s}^{i} and x_{s}^{j} satisfy x_{s}^{i} = x_{s}^{j},

(ii) for every pair i < j of elements which do not lie in the same block of π_{s}, but lie in the same block of π_{s−1} (here we set π_{0} = |1| ⋯ |n|), for some 1 ≤ s ≤ d the coordinates x_{s}^{i} and x_{s}^{j} satisfy x_{s}^{i} ≤ x_{s}^{j}.

Lemma 3.12. [25, Lemma 3.3.1, 3.3.2] Let π = (π_{1} ⪯ ⋯ ⪯ π_{d}) be an iterated composition of n of degree d. Assume π_{i} consists of t_{i} blocks, 1 ≤ i ≤ d. Then c(π) is a cell of dimension nd − (n − t_{1}) − ⋯ − (n − t_{d}).

Again one is able to identify within C_{n}^{d} certain strata that correspond to various degenerations in (R^{d})^{n}/S_{n}. Let λ be a number-partition of n then set C_{λ}^{d} to be the join-sublattice of C_{n+1}^{d} that is generated by iterated compositions (π ⪯ ⋯ ⪯ π) for which π is of type λ. The corresponding cells stratify a d-dimensional analog of Hyp^{n}. But for general d the situation is more delicate than in the case d = 1. The cells c(π) for π ∈ C_{λ}^{d} are attached to each other in a more subtle than in case d = 1. Still it is possible to compute the boundary map (see Fuchs [14], Cohen [10], Vainshtain [24] and Vassiliev [25]).

4. Concluding remarks and problems

4.1. Hyperbolic polynomials & resonance arrangements. By Theorem 3.5 (a) and (b) the topology of \begin{matrix} \\ Hyp & n λ \end{matrix} is determined by the “combinatorics” of C_{λ}. On the other hand it is clear that the lattice structure of C_{λ} is determined by the “resonances” of λ. Note that any lattice identity in C_{λ} corresponds to some resonance identity of λ and vice versa. Therefore, it is reasonable to ask for the “set of resonances” valid for a number-partition λ or equivalently for a composition π of type λ. This leads necessarily to the study of a certain arrangement of hyperplanes. Assume

λ = (1^{e_{1}}, …, n^{e_{n}}), t = ∑_{i=1}^{n}e_{i}. Then we consider a composition (a_{1}, …, a_{t}) of type λ

as a point in R^{t}. Let A_{t} be the arrangement (i.e., finite set) of hyperplanes

{H_{J,K} : ∑_{i∈J} x_{i} = ∑_{i∈K} x_{i} | ∅ ≠ J, K ⊆ [t], J ∩ K = ∅}.

For a composition π = (a_{1}, …, a_{t}) let A_{π} be the set of hyperplanes in A_{t} that contain the point (a_{1}, …, a_{t}). Note, that A_{π} is empty if and only if a_{i} ≠ a_{j} for i ≠ j and (a_{1}, …, a_{t}) is free of resonances. Now the combinatorics of C_{λ} is determined by the S_{t} orbit A_{π} or equivalently ⋂_{H∈A_{π}} H in the positive orthant (i.e., x_{i} ≥ 0, 1 ≤ i ≤ t),

where S_{t} acts on R^{t} by permuting coordinates. Therefore, it appears as a challenging problem to count the number of different S_{t} orbits. The problem of counting the number of connected components of the complement R^{t} \ ⋃_{H∈A_{t}} H amounts to the

enumeration of the number of different classes of resonance free compositions with no multiple parts. This problem has evoked interest in statistics (see Fine & Gill [13]) and electrical engineering. In general, arrangements that contain only hyperlanes defiened by linear form with 0, 1 and −1 as coefficients are were studied by Edelman & Reiner [12].

Another challenging problem that arises here, is the question : “How general are the order complexes Δ(C_{λ}) for various λ ?” The results presented and the examples supplied provide only evidence for “very nice” simplicial complexes (i.e., Δ(C_{λ}) has the homotopy type of a sphere). So one may as : “Is it true that in general Δ(C_{λ}) is homotopic a wedge of spheres ? ” Or “Is it true that in general the homology of Δ(C_{λ}) is free ? ” See the examples at the end of Section 2.2. On the other hand the number-partitions (1^{n−k}, k) allow only a single and very basic resonance. Namely, k = \underbrace{1 + ⋯ + 1}_{k times}. Thus the topology of Δ(C_{λ}) may be much more complicated in

general. We mention that for λ = (k^{r}, 1^{q}), q ≥ k ≥ 3, r ≥ 2 the method of shellability used by Björner & Wachs [6] to determine the homotopy type fails. This follows by a similar argument used by Kozlov [19] for analogously defined partition lattices. So conversely, it may even be true that the complexes Δ(C_{λ}) are universal in the homotopy category of finite CW-complexes (i.e., for any finite CW-complex X there is a number-partition λ such that X ≃ Δ(C_{λ})). We regard this as a very interesting, albeit difficult, problem. A combinatorial reformulation and generalization of this problem can be found in [22], where “weight”-functions on lattices are considered.

4.2. Quotients of permutahedra. The procedure of passing from P_{t} to P_{t}/H for a Young-subgroup H of S_{t} applied in Proposition 3.7 is reminiscent of the construction of the braid space as a quotient of the permutahedron (see Carlsson & Milgram [9]). For the other Artin braid groups this was generalized by Salvetti [21]. Let us briefly sketch and compare the two constructions in order to exhibit the significant difference between them. The construction described by Carlsson & Milgram and Salvetti is a quotient construction under the full symmetric group (resp., Coxeter group). Thus we start describing the cellular complex that is constructed in both cases for the quotient operation under the “action” of S_{t}.

(i) The quotient space of the permutahedron P_{t} modulo the action of S_{t} has exactly ( \begin{matrix}t−1 \\ i \end{matrix} ) cells of dimension i, 0 ≤ i ≤ t−2. Namely, by Proposition 3.7 the cellular decomposition of P_{t}/S_{t} is given by the cells of a simplex. Note that L_{t}/S_{t} is isomorphic to the Boolean lattice on t−1 elements with the top element removed.

(ii) The second complex, that arises by “modding” out the S_{t}-action on the permutahedron, consists as well of ( \begin{matrix}t−1 \\ i \end{matrix} ) cells of dimension i, 0 ≤ i ≤ t − 2. But here attachment and the boundary maps are much more complicated. Let v be a vertex of the permutahedron. For each face F of the permutahedron let σ_{F} be the permutation of minimal length – length as a word in Coxeter generators – in S_{t} such that F^{σ_{F}} intersects the fundamental chamber of the S_{t} action on R^{t} – here we use the second description of the permutahedron. If two faces F, F′ lie in the same S_{t} orbit, then they are be identified via σ_{F} σ_{F′}^{−1}. The resulting space will be denoted by Braid_{t}. It has be shown (see Carlsson & Milgram [9]) thatBraid_{t} is the K(π, 1) space for the braid group π = Br_{t} on t strings. For the other Coxeter groups the result is due to Salvetti [21].

In Figure 3 we perform the two constructions for t = 3. Obviously, the two constructions do not yield homotopy equivalent spaces.

Classifying space of the braid group Br_{1} ≅ Z Permutahedron P_{3}  Quotient space P_{3}/S_{3}

Figure 3 : Quotient constructions on the permutahedron P_{3}

4.3. Complex polynomials. One can consider similarly defined stratification by multiplicities of roots of the space of monic polynomials of degree n with complex coefficients. Note that these strata are enumerated by the set of all number-partitions of n and the only stratum of top dimension coincides with the standard braid space. The strata corresponding to a number-partition whose Young diagram is of the hook shape were studied in the work of Arnol’d [1] and Vassiliev [25]. In particular, Vassiliev has shown that the homotopy type of the 1-point compactification of such a stratum is stably homotopically equivalent to a wedge of vector bundles over the braid spaces coming from the sign representation in the symmetric group. These spaces are not so simple to approach and combinatorial stratifications may be more difficult to handle. Nevertheless, teh first author has observed that the homotopy type of each such stratum depends only on the combinatorics of the corresponding number-partition. More generally, the first author has checked that the homotopy type of Σ̂_{μ,λ} depends only on the combinatorics of the number-partitions μ and λ. But in these cases homology and cohomology computations become much more delicate and torsion appears all over the place (see the work of Fuchs [14], Cohen [10], Vainshtain [24] for the case λ = (1^{n−2}, 2)). It will be very interesting to find the analog of Vassiliev’s result for the case of any number-partition.

4.4. Stable complexes. The problem of calculation of the stable cohomology of the complement Pol^{∞} \ Pol_{λ}^{∞} mentioned in Section 2 is closely related to the one considered in [2] and [25]. One can hope that this question is solvable for any numberpartition λ. In particular, if each entry of λ is greater or equal 3 then the technique of Vassiliev’s resolving spaces [25] is applicable and one can apparently get a (simple?) answer for the additive structure of H^{∗}(Pol^{∞} \ Pol_{λ}^{∞}).

References

[1] V.I. Arnol’d. Topological invariants of algebraic functions. Trans. Moscow Math. Soc., 21:30–52, 1970.

[2] V.I. Arnol’d. Spaces of functions with moderate singularities. Functional Anal. Appl., 23(3):169– 177, 1989.

[3] A. Björner. Subspace arrangements. In A. Joseph, editor, Proceedings of the 1st European Congress of Mathematics (Paris 1992), volume 1, pages 321–371, Boston, 1995. Birkhäuser.

[4] A. Björner. Topological methods. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, pages 1819–1872. North-Holland, Amsterdam, 1995.

[5] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G.M. Ziegler. Oriented Matroids. Encyclopedia of Mathematics. Cambridge University Press, Cambridge, 1993.

[6] A. Björner and M.L. Wachs. Shellable non-pure complexes and posets, II. Trans. Amer. Math. Soc., 1995. (to appear).

[7] A. Björner and M.L. Wachs. Shellable non-pure complexes and posets, I. Trans. Amer. Math. Soc., 348(4):1299–1327, 1996.

[8] R.W. Brockett. Some geometric questions in the theory of linear systems. IEEE Trans. Automat. Control, AC-21:449–455, 1976.

[9] G. Carlsson and R.J. Milgram. Stable homotopy and iterated loop spaces. In I.M. James, editor, Handbook of Algebraic Topology, pages 505–583. North Holland, Amsterdam, 1995.

[10] F.R. Cohen. The homology of C_{n+1}-spaces, n ≥ 0. In F.R. Cohen, T.J. Lada, and J.P. May, editors, The homology of iterated loop spaces, volume 533 of Lecture Notes in Math., pages 207–353. Springer, Heidelberg, 1976.

[11] J. Dedieu. Obreschoff’s theorem revisited: what convex sets are contained in the set of hyperbolic polynomials. J. Pure Appl. Algebra, 81(3):269–278, 1992.

[12] P. Edelman and V. Reiner. Free hyperplane arrangements between A_{n} and B_{n}. Math. Z., 215:347–365, 1994.

[13] T. Fine and J. Gill. The enumeration of comparative probability relations. Ann. Probab., 4:667– 673, 1976.

[14] D. Fuchs. Cohomologies of the group cos mod 2. Functional Anal. Appl., 4:143–151, 1970.

[15] C. Greene. A class of lattices with Möbius function ±1, 0. European J. Combin., pages 225–240, 1988.

[16] U. Helmke. A compactification of the space of rational transfer functions by singular systems. J. Math. Systems, 3(4):459–472, 1993.

[17] U. Helmke and C.I. Byrnes. The cohomology of the moduli space of controllable linear systems. Acta Appl. Math., 28:161–188, 1992.

[18] L. Hörmander. The Analysis of Linear Partial Differential Operators, volume 256 of Grundlehren der Math. Wissenschaften. Springer, Heidelberg, 2 edition, 1990.

[19] D. Kozlov. On generalized lexicographic shellability. (Preprint 1995).

[20] I. Meguerditchian. A theorem on escape from the space of hyperbolic polynomials. Math. Z., 211:350–359, 1992.

[21] M. Salvetti. The homotopy type of the Artin groups. Math. Res. Lett., 1:565–577, 1995.

[22] B. Shapiro. Valuations on posets and associated simplicial complexes. University of Stockholm, Preprint 1996.

[23] B. Sturmfels. Gröbner Bases and Convex Polytopes, volume 8 of University Lecture Series. Amer. Math. Soc., Providence, RI, 1995.

[24] F.V. Vainshtain. Cohomology of the braid groups. Functional Anal. Appl., 12:135–137, 1978.

[25] V.A. Vassiliev. Complements of Discriminants of Smooth Maps : Topology and Applications, volume 98 of Transl. of Math. Monographs. Amer. Math. Soc., Providence, RI, 1994. Revised Edition.

Department of Mathematics, Stockholm University, S-106 91 Stockholm, Sweden

E-mail address: shapiro@matematik.su.se

Institute for Experimental Mathematics, Ellernstr. 29, 45326 Essen, Germany

E-mail address: welker@exp-math.uni-essen.de