Why the characteristic polynomial factors

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027 sagan@math.msu.edu

September 24, 1995

Key Words: characteristic polynomial, free arrangement, Möbius function, partially ordered set, signed graph, subspace arrangement, supersolvable lattice

AMS subject classification (1991): Primary 06A07; Secondary 05C15, 20F55, 06C10, 52B30.

Proposed running head:

Why χ factors

Send proofs to:

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027

Tel.: 517-355-8329 FAX: 517-336-1562 Email: sagan@mth.msu.edu

Abstract

We survey three methods for proving that the characteristic polynomial of a finite ranked lattice factors over the nonnegative integers and indicate how they have evolved recently. The first technique uses geometric ideas and is is based on Zaslavsky’s theory of signed graphs. The second approach is algebraic and employs results of Saito and Terao about free hyperplane arrangements. Finally we consider a purely combinatorial theorem of Stanley about supersolvable lattices and its generalizations.

1 Introduction

If one chooses a random polynomial with real coefficients, the chances are very small that it will have all its roots in ℤ_{≥0}, the nonnegative integers. However if one considers the characteristic polynomials of various lattices that arise in practice, a surprisingly large number of them do factor over ℤ_{≥0}. The natural question to ask is: Why? In this survey, we provide three reasons with tools drawn from three different areas of mathematics: graph theory/geometry, algebra, and pure combinatorics. The first of these uses Zaslavsky’s lovely theory of signed graph coloring [41, 42, 43] which can be generalized to counting points of ℤ^{n} inside a certain polytope [9]. The next technique is based on theorems of Saito [30] and Terao [37] about free hyperplane arrangements. Work has also been done on related concepts such as inductive freeness [36] and recursive freeness [44]. The third method employs a theorem of Stanley [31] on semimodular supersolvable lattices which has recently been generalized by Blass and myself [10] by relaxing both restrictions on the lattice. Since this paper is expository, I will provide a fair number of definitions and examples. However for the proofs of most theorems the reader will have to see the articles cited.

A lattice, L, is a set with a partial order ≤ such that every pair x, y ∈ L has a meet or greatest lower bound, x ∧ y, and a join or least upper bound, x ∨ y. All our lattices will be finite and so have a unique minimal element ˆ0 = ⋀ L and a unique maximal element ˆ1 = ⋁ L. Another set of important elements of L are its atoms which are all elements a covering ˆ0. (If x, y ∈ L then x covers y if x > y and there is no z with x > z > y.) We let A(L) denote the atom set of L.

One of the fundamental invariants of a lattice, or indeed of any partially ordered set, is its Möbius function of L, μ : L → Z, defined recursively by

μ(x) = \{ \begin{matrix}1 & if x = ˆ0, \\ − ∑_{y<x} μ(y) & if x > ˆ0. \end{matrix}  (1)

The number-theoretic Möbius function is obtained as a special case by taking L to be the lattice of divisors of an integer ordered by divisibility. Our main object of study will be the generating function for μ. Let L be ranked so that for any x ∈ L all maximal chains from ˆ0 to x have the same length denoted ρ(x) and called the rank of x. (A chain is a totally ordered subset of L.) The characteristic polynomial of L is then

χ(L, t) = ∑_{x∈L} μ(x)t^{ρ(ˆ1)−ρ(x)}.  (2)

Note that we use the corank rather than the rank in the exponent on t so that χ will be monic. The usual generating function by rank is the related Poincaré

[figure: 0; 1; 2; 3; The chain C_{3}; ∅; The Boolean algebra B_{3}; {1}; {2}; {3}; {1, 2}; {1, 3}; {2, 3}; {1, 2, 3}; {1}{2}{3}; The Partition lattice Π_{3}; {1, 2}{3}; {1, 3}{2}; {1}{2, 3}; {1, 2, 3}]

Figure 1: Some example lattices

polynomial of L

π(L, t)) = ∑_{x∈L} |μ(x)|t^{ρ(x)}.

Let us look at three simple examples of lattices and their characteristic polynomials. The chain C_{n} consists of the integers {0, 1, …, n} ordered in the usual manner, see Figure 1 for a picture of C_{3}. It is immediate directly from the definition (1) that in C_{n} we have

μ(x) = \{ \begin{matrix}1 & if x = 0 \\ −1 & if x = 1 \\ 0 & if x ≥ 2 \end{matrix}

and so

χ(C_{n}, t) = t^{n} − t^{n−1} = t^{n−1}(t − 1).

The Boolean algebra B_{n} has as elements all subsets of [n] := {1, 2, …, n} and ⊆ as order relation, the case n = 3 being displayed in Figure 1. It is well known that for x ∈ B_{n} we have μ(x) = (−1)^{|x|} were the absolute value signs denote cardinality. It follows that

χ(B_{n}, t) = ∑_{x⊆[n]}(−1)^{|x|}t^{n−|x|} = (t − 1)^{n}.

Finally consider the partition lattice Π_{n} which consists of all partitions of [n] ordered by refinement. Direct computation with Π_{3} as shown in Figure 1 shows that χ(Π_{3}, t) = t^{2} − 3t + 2 = (t − 1)(t − 2). In general

χ(Π_{n}, t) = (t − 1)(t − 2) ⋯ (t − n + 1).

Note that in all three cases χ has only nonnegative integral roots.

Many of our example lattices will arise as intersection lattices of subspace arrangements. (See [3, 27] for details about the theory of arrangements.) A subspace arrangement is a finite set

A = {K_{1}, K_{2}, …, K_{l}}  (3)

of subspaces of real Euclidean space ℝ^{n}. If dim K_{i} = n − 1 for 1 ≤ i ≤ l then we say that A is a hyperplane arrangement and will uses H’s in place of K’s. The intersection lattice of A, L(A), has as elements all subspaces X of ℝ^{n} that can be written as an intersection of some of the elements of A. The partial order is reverse inclusion, so that X ≤ Y if and only if X ⊇ Y. So L(A) has minimal element ℝ^{n}, maximal element K_{1} ∩ ⋯ ∩ K_{l}, and join operation X ∨ Y = X ∩ Y. The characteristic polynomial of A is defined by

χ(A, t) = ∑_{X∈L(A)} μ(X)t^{dim X}.  (4)

This is not necessarily the same as χ(L(A), t) as defined in (2). If A is a hyperplane arrangement then the two will be equal up to a factor of a power of t, so from the point of view of having integral roots there is no difference. In the general subspace case (2) and (4) may be quite dissimilar and often the latter turns out to factor at least partially over ℤ_{≥0} while the former does not. In the arrangement case the roots of (4) are called the exponents of A and denoted exp A. In fact when A is a the set of reflecting hyperplanes for a Weyl group W then these roots are just the usual exponents of the W [37] which are always nonnegative integers.

All three of our previous example lattices can be realized as intersection lattices of subspace arrangements. The n-chain is L(A) with A = {K_{0}, …, K_{n}} where K_{i} is the set of all points having the first i coordinates zero. The Boolean algebra is the intersection lattice of the arrangement of coordinate hyperplanes H_{i} : x_{i} = 0, 1 ≤ i ≤ n. To get the partition lattice we use the Weyl arrangement of type A

A_{n} = {x_{i} − x_{j} = 0 : 1 ≤ i < j ≤ n}.

To see why Π_{n} and L(A_{n}) are the same, associate the hyperplane x_{i} = x_{j} with the partition where i, j are in one subset and all other subsets are singletons. This will then make the join operations in the two lattices correspond. Note that the

\begin{matrix}A & χ(A, t) & exp(A) \\ A_{n} & t(t − 1)(t − 2) ⋯ (t − n + 1) & 0, 1, 2, …, n − 1 \\ B_{n} & (t − 1)(t − 3) ⋯ (t − 2n + 1) & 1, 3, 5, …, 2n − 1 \\ D_{n} & (t − 1)(t − 3) ⋯ (t − 2n + 3)(t − n + 1) & 1, 3, 5, …, 2n − 3, n − 1 \end{matrix}

Table 1: Characteristic polynomials and exponents of some Weyl arrangements

characteristic polynomials defined by (2) and (4) are the same in the first two examples while χ(A_{n}, t) = tχ(Π_{n}, t).

We will also be concerned with the hyperplane arrangements associated with other Weyl groups. The reader interested in more information about these groups should consult the excellent text of Humphreys [21]. In particular, the other two infinite families

B_{n} = {x_{i} ± x_{j} = 0 : 1 ≤ i < j ≤ n} ∪ {x_{i} = 0 : 1 ≤ i ≤ n},
D_{n} = {x_{i} ± x_{j} = 0 : 1 ≤ i < j ≤ n}.

will play a role. The corresponding characteristic polynomials are listed in Table 1 along with χ(A_{n}, t) for completeness. (We do not consider the arrangement for the group C_{n} because it is the same as for the group B_{n}.) We will show how to derive the formulas for the characteristic polynomials of A_{n}, B_{n} and D_{n} using elementary graph theory in the next section.

2 Signed graphs

Zaslavsky developed his theory of signed graphs [41, 42, 43] to study hyperplane arrangements contained in the Weyl arrangement B_{n}. (Note that this includes A_{n} and D_{n}.) In particular his coloring arguments provide one of the simplest ways to compute the corresponding characteristic polynomials.

A signed graph, G = (V, E), consists of a set V of vertices which we will always take to be {1, 2, …, n}, and a set of edges E which can be of three possible types:

1. a positive edge between i, j ∈ V, denoted ij^{+},

2. a negative edge between i, j ∈ V, denoted ij^{−},

3. and a half-edge which has only one endpoint i ∈ V, denoted i^{h}.

One can have both the positive and negative edges between a given pair of vertices in which case it is called a doubled edge and denoted ij^{±}. The three types of edges

[figure: 2; 3; 1; G_{A_{3}}; 2; 3; 1; G_{B_{3}}; 2; 3; 1; G_{D_{3}}]

Figure 2: Graphs for Weyl arrangements

correspond to the three types of hyperplanes in B_{n}, namely x_{i} = x_{j}, x_{i} = −x_{j}, and x_{i} = 0 for the positive, negative, and half-edges, respectively. So to every hyperplane arrangement A ⊆ B_{n} we have an associated signed graph G_{A} with a hyperplane in A if and only if the corresponding edge is in G_{A}. Actually, the possible edges in G_{A} really correspond to the vectors in the root system of type B_{n} perpendicular to the hyperplanes which are e_{i} − e_{j}, e_{i} + e_{j}, and e_{i}. In the full theory one also considers the root system C_{n} with roots 2e_{i} which are modeled by loops ii in G. This is why the somewhat strange definition of a half-edge is necessary. In picturing a signed graph I will draw an ordinary edge for ij^{+}, an edge with a slash through it for ij^{−}, an edge with a two slash through it for ij^{±}, and an edge starting at a vertex and wandering off into space for i^{h}. The graphs G_{A_{3}}, G_{B_{3}}, and G_{D_{3}} are shown in Figure 2.

Since we are using signed edges, we are also going to use signed colors for the vertices. For s ∈ ℤ_{≥0} let [−s, s] = {−s, −s + 1, …, s − 1, s}. A coloring of the signed graph G is a function c : V → [−s, s]. The fact that the number of colors t = |[−s, s]| = 2s + 1 is always odd will be of significance later. A proper coloring c of G requires that for every edge e ∈ E we have

1. if e = ij^{+} then c(i) ≠ c(j),

2. if e = ij^{−} then c(i) ≠ −c(j),

3. if e = i^{h} then c(i) ≠ 0.

Note that the first of these three restrictions is the one associated with ordinary graphs and the four-color theorem [14]. The chromatic polynomial of G is

P (G, t) = the number of proper colorings of G with t colors.

It is not obvious from the definition that P (G, t) is actually a polynomial in t. In fact even more is true as we see in the following theorem of Zaslavsky.

Theorem 2.1 ([42]) Suppose A ⊆ B_{n} has signed graph G_{A}. Then

χ(A, t) = P (G_{A}, t).

Theorem 2.1 trivializes the calculation of the characteristic polynomials for the three infinite families of Weyl arrangements and in so doing explains why they factor over ℤ_{≥0}. For A_{n} the graph G_{A_{n}} consists of every possible positive edge. So to properly color G_{A_{n}} we have t choices for vertex 1, then t − 1 for vertex 2 since c(2) ≠ c(1), and so forth yielding

χ(A_{n}, t) = P (G_{A_{n}}) = t(t − 1) ⋯ (t − n + 1).

in agreement with Table 1. It will be convenient in a bit to have a shorthand for this falling factorial, so let ⟨t⟩_{n} = t(t − 1) ⋯ (t − n + 1). In G_{B_{n}} we also have every negative edge and half-edge. This gives t − 1 choices for vertex 1 since color 0 is not allowed, t − 3 choices for vertex 2 since c(2) ≠ ±c(1), 0, and so on. These are exactly the factors in the B_{n} entry of Table 1. Finally consider G_{D_{n}} which is just G_{B_{n}} with the half-edges removed. There are two cases depending on whether the color 0 appears once or not at all. (It can’t appear two or more times because G_{A_{n}} ⊂ G_{D_{n}}.) If the color 0 is never used then we have the same number of colorings as with B_{n}. If 0 is used once then there are n vertices that could receive it and the rest are colored as in B_{n−1}. So

χ(D_{n}, t) = ∏_{i=1}^{n}(t − 2i + 1) + n ∏_{i=1}^{n−1}(t − 2i + 1) = (t − n + 1) ∏_{i=1}^{n−1}(t − 2i + 1)

which again agrees with the table.

Recently Blass and I have generalized Zaslavsky’s theorem from hyperplane arrangements to subspace arrangements. If A and B are subspace arrangements then we say that A is embedded in B if all subspaces of A are intersections of subspaces of B, i.e., A ⊆ L(B). Now consider [−s, s]^{n} as a cube of integer lattice points in R^{n} (not to be confused with our use of lattice as a type of partially ordered set). Let [−s, s]^{n} \ ⋃ A denote the set of points of the cube which lie on none of the subspaces in A.

Theorem 2.2 ([9]) Let t = 2s + 1 where s ∈ ℤ_{≥0} and let A be any subspace arrangement embedded in B_{n}. Then

χ(A, t) = |[−s, s]^{n} \ ⋃ A|.

To see why our theorem implies Zaslavsky’s in the hyperplane case, note that a point c ∈ [−s, s]^{n} is just a coloring c : V → [−s, s] where the ith coordinate of the point is the color of the vertex i. With this viewpoint, a coloring is proper if and only if the corresponding point is not on any hyperplane of A. For example, if ij^{+} ∈ E then the coloring must have c(i) ≠ c(j) and so the point does not lie on the hyperplane x_{i} = x_{j}.

As an application of Theorem 2.2, we consider a set of subspace arrangements that has been arousing a lot of interest lately. The k-equal arrangement of type A is

A_{n,k} = {x_{i_{1}} = x_{i_{2}} = … = x_{i_{k}} : 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n}.

The A_{n,k} arrangement were introduced in the work of Björner, Lovász and Yao [5] motivated, surprisingly enough, by its relevance to a certain problem in computational complexity. Its study has been continued by many people including Linusson, Sundaram, Wachs and Welker [4, 8, 7, 25, 26, 34, 35]. Analogs of this subspace arrangement for types B and D have also been studied by Björner and myself [6].

Now in general χ(A_{n,k}) does not factor completely over ℤ_{≥0}, but it does factor partially. In fact it is divisible by the characteristic polynomial ⟨t⟩_{m} for a certain hyperplane arrangement of type A. What’s more if one expands χ(A_{n,k}) in the basis ⟨t⟩_{n}, n ≥ 0, for the polynomial ring then the coefficients are nonnegative integers with a simple combinatorial interpretation. In particular, let S_{k}(n, j) denote the number of partitions of an n-element set into j subsets each of which is of size at most k. Thus these are generalizations of the Stirling numbers of the second kind. We now have the expansion, first derived by Sundaram [33]

χ(A_{n,k}, t) = ∑_{j} S_{k−1}(n, j)⟨t⟩_{j}.  (5)

To see why this is true, consider an arbitrary point c ∈ [−s, s]^{n} \ ⋃ A_{n,k}. So c can have at most k−1 of its coordinates equal. Consider the c’s with exactly j different coordinates. Then there are S_{k−1}(n, j) ways to distribute the j values among the n coordinates with at most k − 1 equal. Next we can choose which values to use in ⟨t⟩_{j} ways. Summing over all j gives the desired equation. From (5) we immediately have the divisibility relation

⟨t⟩_{⌈n/(k−1)⌉} | χ(A_{n,k}, t)

since S_{k−1}(n, j) = 0 if j < ⌈n/(k − 1)⌉. (Obviously j sets of at most k − 1 elements can partition a set of size of at most n = j(k − 1).)

Thinking about things in terms of lattice points also permits us to generalize Zaslavsky’s theorem in another direction, namely to all Weyl hyperplane arrangements (even the exceptional ones). Let Φ ⊂ ℝ^{n} be a root system for a finite Weyl group W and let W be the set of hyperplanes perpendicular to the roots. Let (·, ·) denote the standard inner product on ℝ^{n}. The role of the cube in Theorem 2.2 will be played by

P_{t}(Φ) = {x ∈ ℝ^{n} : (x, α) ∈ ℤ_{<t} for all α ∈ Φ}

which is a set of points in the coweight lattice of Φ closely associated with the Weyl chambers of the corresponding affine Weyl group.

Consider a fixed a simple system

Δ = {σ_{1}, …, σ_{n}}

in Φ. Since Δ is a basis for R^{n} any root α ∈ Φ can be written as a linear combination,

α = ∑_{i=1}^{n} s_{i}(α)σ_{i}.

In fact the coefficients s_{i}(α) are always integers. Among all the roots, there is a highest one, α̃, characterized by the fact that for all roots α and all i ∈ [n], s_{i}(α̃) ≥ s_{i}(α). We will also need a weighting factor called the index of connection, f, which is the index of the lattice generated by the roots in the coweight lattice. Our second generalization can now be stated.

Theorem 2.3 ([9]) Let Φ be a root system for a finite Weyl group with associated arrangement W. Let t be a positive integer relatively prime to s_{i}(α̃) for all i. Then

χ(W, t) = \frac{1}{f} |P_{t}(Φ) \ ⋃ W| .  (6)

Note how the condition in the first two theorems that t be odd has been replaced by a relative primeness restriction. This is typical when dealing with Ehrhart quasi-polynomials [32, page 235ff.] which enumerate the number of points of a given lattice inside a polytope and its blowups. Unfortunately, the demonstration of Theorem 2.3 is done case-by-case. It would be wonderful if someone could find a proof that is as uniform as the statement of the result. Furthermore, we have not been able to use (6) to explain the factorization of χ(W, t) over Z_{≥0} as was done with Theorem 2.1 for the three infinite families. It would be interesting if this hole could be filled as well.

3 Free arrangements

In this section we consider a large class of hyperplane arrangements called free arrangements which were introduced by Terao [37]. The characteristic polynomial of such an arrangement factors over the ℤ_{≥0} because its roots are related to the degrees of basis elements for a certain associated free module.

Our modules will be over the polynomial algebra A = ℝ[x_{1}, …, x_{n}] = ℝ[x] graded by total degree A = ⊕_{i≥0}A_{i}. The module of derivations, D, consists of all ℝ-linear maps θ : A → A satisfying

θ(fg) = fθ(g) + gθ(f)

for any f, g ∈ A. This module can be graded by saying that θ has degree d, deg θ = d, if θ(A_{i}) ⊆ A_{i+d} for all i ≥ 0. Also, D is free with basis ∂/∂x_{1}, …, ∂/∂x_{n}. It is simplest to display a derivation as a column vector with entries being its components with respect to this basis. So if θ = p_{1}(x)∂/∂x_{1} + ⋯ + p_{n}(x)∂/∂x_{n} then we write

θ = [ p_{1}(x) ; ⋮ ; p_{n}(x) ] = [ θ(x_{1}) ; ⋮ ; θ(x_{n}) ] .

Two operators that we will find useful are

X^{d} = x_{1}^{d}∂/∂x_{1} + ⋯ + x_{n}^{d}∂/∂x_{n} = [ x_{1}^{d} ; ⋮ ; x_{n}^{d} ]

and

X̂ = x̂_{1}∂/∂x_{1} + ⋯ + x̂_{n}∂/∂x_{n} = [ x̂_{1} ; ⋮ ; x̂_{n} ]

where x̂_{i} = x_{1}x_{2} ⋯ x_{n}/x_{i}. Note that deg X^{d} = d − 1 and deg X̂ = n − 2.

To see the connection with hyperplane arrangements, notice that any hyperplane H is defined by a linear equation α_{H}(x_{1}, …, x_{n}) = 0. So an arrangement A is determined by the homogeneous polynomial

Q = Q(A) = ∏_{H∈A} α_{H}(x).

The associated module of A-derivations is defined by

D(A) = {θ ∈ D : Q|θ(Q)}

where p|q is division of polynomials in A. One can rewrite the defining condition for D(A) in a way that is more amenable to computation. Since the α_{H} are relatively prime (being linear) we have Q|θ(Q) is equivalent to α_{H}|θ(Q) for all H ∈ A. And since θ is a derivation this is true if and only if α_{H}|θ(α_{H}) for all H ∈ A. As examples, consider the Weyl arrangements. Clearly

Q(A_{n}) = ∏_{1≤i<j≤n}(x_{i} − x_{j})
Q(B_{n}) = x_{1}x_{2} ⋯ x_{n} ∏_{1≤i<j≤n}(x_{i}^{2} − x_{j}^{2})
Q(D_{n}) = ∏_{1≤i<j≤n}(x_{i}^{2} − x_{j}^{2}).

It is also easy to verify that X^{d} ∈ D(A_{n}) for all d ≥ 0 since X^{d}(x_{i} − x_{j}) = x_{i}^{d} − x_{j}^{d} which is divisible by x_{i} − x_{j}. Similarly X^{2d+1} ∈ D(D_{n}) because of what we just showed for A_{n} and the fact that x_{i} +x_{j}|x_{i}^{2d+1} +x_{j}^{2d+1}. The X^{2d+1} are also in D(B_{n}) since x_{i}|x_{i}^{2d+1}. By the same methods we get X̂ ∈ D(D_{n}).

We can now relate freeness and the factorization of χ.

Theorem 3.1 ([37]) If A is free then D(A) has a homogeneous basis θ_{1}, …, θ_{n} and the degree set {d_{1}, …, d_{n}} = {deg θ_{1}, …, deg θ_{n}} depends only on A. Furthermore

χ(A, t) = (t − d_{1} − 1) ⋯ (t − d_{n} − 1).

We have a simple way to test whether a derivation is in D(A) for a given arrangement A. It would be nice to have an easy way to test whether A is free and if so find a basis. This is the Saito criterion. Given derivations θ_{1}, …, θ_{n}, consider the matrix whose columns are the corresponding column vectors

Θ = [θ_{1}, …, θ_{n}] = [θ_{j}(x_{i})].

Theorem 3.2 ([30, 38]) Suppose θ_{1}, …, θ_{n} ∈ D(A) and that Q is the defining form of A. Then A is free with basis θ_{1}, …, θ_{n} if and only if

det Θ = cQ

for some c ∈ ℝ \ 0.

Let us return to the Weyl arrangements. Given what we know about elements in their derivation modules and the factorization of their characteristic polynomials, it is natural to guess that we might be able to prove freeness with the following matrices

Θ(A_{n}) = [X^{0}, X^{1}, X^{2}, …, X^{n−1}] ,
Θ(B_{n}) = [X^{1}, X^{3}, X^{5}, …, X^{2n−1}] ,
Θ(D_{n}) = [X^{1}, X^{3}, X^{5}, …, X^{2n−3}, X̂] .

Of course det Θ(A_{n})) = ∏_{1≤i<j≤n}(x_{i} − x_{j}) = ±Q(A_{n}) is just Vandermonde’s determinant. Similarly we get det Θ(B_{n})) = ±x_{1}x_{2} ⋯ x_{n} ∏_{1≤i<j≤n}(x_{i}^{2} − x_{j}^{2}) by first factoring out x_{i} from the ith row which results in a Vandermonde in squared variables. For D_{n} just factor out x_{1}x_{2} ⋯ x_{n} from the last column and then put these factors back in by multiplying row i by x_{i}. The result is again a Vandermonde in squares. Now the roots of the corresponding characteristic polynomials can be read off these matrices in agreement with Table 1.

The reader may have noticed that the bases we have for D(B_{n}) and D(D_{n}) are the same except for the last derivation. This reflects the fact that exp B_{n} and exp D_{n} are the same except for the last root. Note that the difference between these roots is n which is exactly the number of hyperplanes in B_{n} but not in D_{n}. Wouldn’t it be lovely if adding these hyperplanes one at a time to D_{n} would produce a sequence of arrangements all of whose exponents agreed with exp(D_{n}) except the last one which would increase by one each time a hyperplane is added until we reach exp(B_{n})? This is in fact what happens. Define

DB_{n,k} = D_{n} ∪ {x_{1}, x_{2}, …, x_{k}}

so that DB_{n,0} = D_{n} and DB_{n,n} = B_{n}. Now the derivation θ_{k} = x_{1}x_{2} ⋯ x_{k}X̂ (scalar multiplication) is in D(DB_{n,k}) since X̂ ∈ D(D_{n}) and x^{i} | θ_{k}(x_{i}) for 1 ≤ i ≤ k. Furthermore, if we let

Θ(DB_{n,k}) = [X^{1}, X^{3}, X^{5}, …, X^{2n−3}, θ_{k}]

then det Θ(DB_{n,k}) = x_{1}x_{2} ⋯ x_{k} det Θ(D_{n}) = Q(DB_{n,k}) so we do indeed have a basis. Thus exp(DB_{n,k}) = {1, 3, 5, …, 2n−3, n−1+k} as desired. The DB_{n,k} were first considered by Zaslavsky [41]. Bases for the module of derivations associated to other hyperplane arrangements interpolating between the three infinite Weyl families have been computed by Józefiak and myself [23]. Edelman and Reiner [15] have determined all free arrangements lying between A_{n} and B_{n}. It is still an open problem to find all the free subarrangements of B_{n} which do not contain A_{n}.

Related to these interpolations are the notions of inductive and recursive freeness. If A is any hyperplane arrangement and H ∈ A then we have the corresponding deleted arrangement

A′ = A \ H

and the restricted arrangement

A′′ = {H′ ∩ H : H′ ∈ A′}.

In this case (A, A′, A′′) is called a triple of arrangements. Of course A′ and A′′ depend on H even though the notation does not reflect this fact. Also if A ⊆ B_{n} then one can mirror these two operations by defining deletion or contraction of corresponding edges in G_{A}. The following Deletion-Restriction Theorem shows how the characteristic polynomials of these three arrangements are related.

Theorem 3.3 ([13, 40]) If (A, A′, A′′) is a triple of arrangements then

χ(A, t) = χ(A′, t) − χ(A′′, t).

For freeness, we have Terao’s Addition-Deletion Theorem. Note that its statement about the exponents follows immediately from the previous result.

Theorem 3.4 ( [36]) If (A, A′, A′′) is a triple of arrangements then any two of the following statements implies the third:

A is free with exp A = {e_{1}, …, e_{n−1}, e_{n}},
A′ is free with exp A′ = {e_{1}, …, e_{n−1}, e_{n} − 1},
A′′ is free with exp A′′ = {e_{1}, …, e_{n−1}}.

Continuing to follow [36], define the class IF of inductively free arrangements to be those generated by the rules

(1) the empty arrangement in ℝ^{n} is in IF for all n ≥ 0,

(2) if there exists H ∈ A such that A′, A′′ ∈ IF and exp A′′ ⊂ exp A′ then A ∈ IF.

So to show that A is inductively free, we must start with an arrangement which is known to be inductively free and add hyperplanes one at a time so that (2) is always satisfied. If F denotes the class of free arrangements then Theorem 3.4 shows that IF ⊂ F and one can come up with examples to show that the inclusion is indeed strict. On the other hand, it is not hard to show using interpolating arrangements that A_{n}, B_{n} and D_{n} are all inductively free. Ziegler [44] has introduced an even larger class of arrangements. The class of recursively free arrangements, RF, is gotten by using the same two conditions as for IF plus

(3) if there exists H ∈ A such that A, A′′ ∈ RF and exp A′′ ⊂ exp A then A′ ∈ IF.

It can be shown that IF ⊂ RF strictly but it is not known whether every free arrangement is recursively free.

4 Supersolvability

In this section we will look at a combinatorial method of Stanley [31] which applies to lattices in general, not just those which arise from arrangements. First, however, we must review an important result of Rota [29] which gives a combinatorial interpretation to the Möbius function of a semimodular lattice.

A lattice L is modular if for all x, y, z ∈ L with y ≤ z we have an associative law

y ∨ (x ∧ z) = (y ∨ x) ∧ z.  (7)

A number of natural examples, e.g. the partition lattice, are not modular but satisfy the weaker condition

if x and y both cover x ∧ y then x ∨ y covers both x and y

for all x, y ∈ L. Such lattices are called semimodular. Lattice L is modular if and only if both L and its dual L^{∗} (where the order relation is reversed) are semimodular.

If L is semimodular then one can show that it is ranked. Furthermore, if B ⊆ A(L) (the atom set of L defined in Section 1) then one can prove that

ρ(⋁ B) ≤ |B|.  (8)

We will call B independent and a base for x = ⋁ B if (8) holds with equality. This terminology comes from the theory of vector spaces. Indeed if one takes L to be the lattice of all subspaces of 𝔽_{q}^{n} (𝔽_{q} a finite field) ordered by inclusion then atoms have dimension 1 and lattice independence corresponds to independence of lines. A circuit is a dependent set which is minimal with respect to inclusion. If arrangement A ⊆ A_{n} has graph G = G_{A} then the atoms of L(A) are edges of G and a circuit of L(A) forms a circuit in G in the usual graph-theoretic sense.

Now impose an arbitrary total order on A(L) which will be denoted ⊴ so as to distinguish it from the partial order ≤ on L. A ciruit C ⊆ A(L) gives rise to a broken circuit. \overline{C}, obtained by removing the minimal element of C in ⊴. A set B ⊆ A(L) is NBC (No Broken Circuit) if B does not contain any of the \overline{C}. Note that in this case B must be independent and so a base for ⋁ B. To illustrate, consider the semimodular lattice L in Figure 3. If we order the atoms a ⊲ b ⊲ c ⊲ d then L has unique circuit C = \{a, b, c\} with associated broken circuit \overline{C} = \{b, c\}. Comparing the number of NBC bases of each element with its Möbius function in the following table

element x ˆ0 a b c d s t u v  ˆ1
NBC bases of x ∅ a b c d a, b a, d b, d c, d a, b, d
a, c  a, c, d
μ(x) +1 −1 −1 −1 −1 +2 +1 +1 +1 −2

[figure: ˆ0; a; b; c; d; ˆ1; s; t; u; v]

Figure 3: A lattice L

should lead the reader to a conjecture! This is in fact the famous result of Rota referred to earlier and usually called the NBC Theorem.

Theorem 4.1 ([29]) Let L be a semimodular lattice. Then for any total ordering ⊴ of A(L) we have

μ(x) = (−1)^{ρ(x)}(number of NBC bases of x).

In order to apply the NBC theorem to our factorization problem, we will need to make an additional restriction on L. Write xMz and call x, z a modular pair if equation (7) is satisfied for all y ≤ z. Furthermore x ∈ L is a modular element if xMz and zMx for every z ∈ L. For example, if L = L(A_{n}) or L(B_{n}) then an element corresponding to a graph K_{W} which has a complete component on the vertex set W ⊆ {1, 2, …, n} (all possible edges from the parent graph between elements of W) and all other components trivial (isolated vertices) is modular. A semimodular lattice is supersolvable if it has a maximal chain of modular elements. The lattice of subgroups of a finite supersolvable group (one possessing a normal series where quotients of consecutive terms are cyclic) is supersolvable. From the previous example we see that L(A_{n}) and L(B_{n}) are supersolvable. However it is not true that L(D_{n}) is supersolvable as we will see later.

Now any chain ˆ0 = x_{0} < x_{1} < … < x_{n} = ˆ1 in L defines a parition of the atoms A(L) into subsets

A_{i} = {a ∈ A(L) : a ≤ x_{i} and a ≰ x_{i−1}}  (9)

called levels. A total order ⊴ on A(L) is said to be induced if it satisfies

if a ∈ A_{i} and b ∈ A_{j} with i < j then a ⊴ b.  (10)

With these definitions we can state one of Stanley’s main results [31] about semimodular supersolvable lattices. It states that their characteristic polynomials factor over ℤ_{≥0} because the roots are the cardinalities of the the A_{i}.

Theorem 4.2 ([31]) Let L be a semimodular supersolvable lattice and suppose ˆ0 = x_{0} < x_{1} < … < x_{n} = ˆ1 is a maximal chain of modular elements of L. Then for any induced total order ⊴ on A(L)

(1) the NBC bases of L are exactly the sets of atoms gotten by picking at most one atom from each A_{i},

(2) χ(L, t) = (t − |A_{1}|)(t − |A_{2}|) ⋯ (t − |A_{n}|).

Proof. The proof that (1) implies (2) is so simple and beautiful that I cannot resist giving it. The coefficient of t^{n−k} on the right side of (2) is (−1)^{k} times the number of ways to pick atoms from exactly k of the A_{i}. But by (1) this is up to sign the number of NBC bases of elements at rank k. Putting back in the sign and using the NBC theorem, we see that this coefficient is the sum of all the Möbius values for elements of rank k, which agrees with the corresponding coefficient on the left side.

As an example, consider the chain of graphs with a single nontrivial complete component

ˆ0 = K_{{1}} < K_{{1,2}} < … < K_{{1,2,...,n}} = ˆ1

in Π_{n} = L(A_{n}). Then A_{k} is the set of all positive edges from k + 1 to i, i < k + 1, and so |A_{k}| = k. Thus χ(Π_{n}, t) = ∏_{i=1}^{n−1}(t−i) as before. Using the analogous chain in L(B_{n}) (which starts at K_{∅}) gives A_{k} as containing all edges ik^{±}, i < k, and all half-edges j^{h}, j ≤ k. So |A_{k}| = 2k − 1 giving the usual roots. Now we can also see why L(D_{n}) is not supersolvable for n ≥ 4. When n ≥ 4 the second smallest root of χ(D_{n}, t) is 3. So if the lattice were supersolvable then Theorem 4.2 would imply that some element x ∈ L(D_{n}) of rank two would have to cover at least 3+|A_{1}| = 4 atoms. It is easy to verify that there is no such element.

It is frustrating that L(D_{n}) is not supersolvable. To get around this problem, Bennett and I have introduced a more general concept [2]. Looking at the previous proof, the reader will note that it would still go through if every NBC base could be obtained in the following manner. First pick an atom from a set A_{1} = {a_{1}, a′_{1}, a′′_{1}, …}. Then pick the second atom from one of a family of sets A_{2}, A′_{2}, A′′_{2}, … according to whether the first atom picked was a_{1}, a′_{1}, a′′_{1}, … respectively, where |A_{2}| = |A′_{2}| = |A′′_{2}| = …, and continue similarly. This process can be modeled by an object which we call an atom decision tree or ADT and any lattice admitting an ADT has a characteristic polynomial with roots r_{i} equal to the common cardinality of all the sets of index i. It turns out that the lattices for all of the interpolating arrangements DB_{n,k} admit ADTs and this combinatorially explains their factorization. Hélène Barcelo and Alain Goupil [1] have independently come up with a factorization of the NBC complex of L(D_{n}) (the simplicial complex of all NBC bases of a lattice) which is similar to the ADT one. Their paper also contains a nice result (joint with Garsia) relating the NBC sets with reduced decompositions into reflections of Weyl group elements.

Another way to generalize the previous theorem is to replace the semimodularity and supersolvability restrictions by weaker conditions. The new concepts are based on a generalization of the NBC Theorem that completely eliminates semimodularity from its hypothesis. Let ⊴ be any partial order on A(L). It can be anything from a total order to the total incomparability order induced by the ordering on L. A set D ⊆ A(L) is bounded below if for any d ∈ D there is a ∈ A(L) such that

(a) a ⊲ d and

(b) a < ⋁ D.

In other words a bounds d below in (A(L), ⊴) and also bounds ⋁ D below in (L, ≤). We say B ⊆ A(L) is NBB if it contains no bounded below set and say that B is an NBB base for x = ⋁ B. Blass and I have proved the following NBB Theorem which holds for any lattice

Theorem 4.3 ([10]) Let L be any lattice and let ⊴ be any partial order on A(L). Then for any x ∈ L we have

μ(x) = ∑_{B}(−1)^{|B|}

where the sum is over all NBB bases of x.

Note that when L is semimodular and ⊴ is total then the NBB and NBC bases coincide. Also in this case all NBC bases of x have the same cardinality, namely ρ(x), and so our theorem reduces to Rota’s. However this result has much wider applicability, giving combinatorial explanations for the Möbius functions of the non-crossing partition lattices and their type B and D analogs [24, 28], integer partitions under dominance order [11, 12, 18], and the shuffle posets of Greene [19].

Call x ∈ L left modular if xMz for all z ∈ L. So this is only half of the condition for modularity of x. Call L itself left modular if

L has a maximal chain ˆ0 = x_{0} < x_{1} < … < x_{n} = ˆ1 of left modular elements.

This is strictly weaker than supersolvability as can be seen by considering the 5-element nonmodular lattice [31, Proposition 2.2 and ff.].

In Stanley’s theorem we cannot completely do away with semimodularity as we did in Rota’s (the reason why will come shortly), but we can replace it with a weaker hypothesis which we call the level condition. In it we assume that the partial order ⊴ has been induced by some maximal chain, i.e., satisfies (10) with “if” replaced by “if and only if.”

If ⊴ is induced and b_{0} ⊲ b_{1} ⊲ b_{2} ⊲ … ⊲ b_{k} then b_{0} ≰ ⋁_{i=1}^{k} b_{i}.

It can be shown that semimodularity implies the level condition for any induced order but not conversely. An LL lattice is one having a maximal left modular chain such that the induced partial order satisfies the level condition. So Theorem 4.2 generalizes to the following. Note that we must extend the definition of the characteristic polynomial since an LL lattice may not have a rank function and the first of the two parts makes χ well-defined.

Theorem 4.4 ([10]) Let L be an an LL lattice with ⊴ the partial order on A(L) induced by a left modular chain.

(1) The NBB bases of L are exactly the sets of atoms obtained by picking at most one atom from each A_{i} and all NBB bases of a given x ∈ L have the same cardinality denoted ρ(x).

(2) If we define χ(L, t) = ∑_{x∈L} μ(x)t^{ρ(ˆ1)−ρ(x)} with ρ as in (1), then

χ(L, t) = (t − |A_{1}|)(t − |A_{2}|) ⋯ (t − |A_{n}|).

This theorem can be used on lattices where Stanley’s theorem does not apply, e.g., the Tamari lattices [16, 17, 20] and certain shuffle posets [18]. Note also that we cannot drop the level condition which replaced semimodularity completely: If one considers the non-crossing partition lattice then it has the same modular chain as Π_{n}. However, it does not satisfy the level condition and its characteristic polynomial does not factor over ℤ_{≥0}.

I hope that you have enjoyed this tour through the world of the characteristic polynomial and its factorizations. Maybe you will feel inspired to try one of the open problems mentioned along the way.

References

[1] H. Barcelo and A. Goupil, Non broken circuits of reflection groups and their factorization in D_{n}, preprint.

[2] C. Bennett and B. E. Sagan, A generalization of semimodular supersolvable lattices, J. Algebraic Combin., to appear.

[3] A. Björner, Subspace arrangements, in “Proc. 1st European Congress Math. (Paris 1992),” A. Joseph and R. Rentschler eds., Birkhäuser, Boston, MA, to appear.

[4] A. Björner and L. Lovász, Linear decision trees, subspace arrangements and Möbius functions, J. Amer. Math. Soc. 7 (1994), to appear.

[5] A. Björner, L. Lovász and A. Yao, Linear decision trees: volume estimates and topological bounds, in “Proc. 24th ACM Symp. on Theory of Computing,” ACM Press, New York, NY, 1992, 170–177.

[6] A. Björner and B. Sagan, Subspace arrangements of type B_{n} and D_{n}, J. Algebraic Combin., submitted.

[7] A. Björner and M. Wachs, Shellable nonpure complexes and posets, preprint.

[8] A. Björner and V. Welker, The homology of “k-equal” manifolds and related partition lattices, Adv. in Math., to appear.

[9] A. Blass and B. E. Sagan, Characteristic and Ehrhart polynomials, Trans. Amer. Math. Soc., submitted.

[10] A. Blass and B. E. Sagan, Möbius functions of lattices, in preparation.

[11] K. Bogart, The Möbius function of the domination lattice, unpublished manuscript, 1972.

[12] T. Brylawski, The lattice of integer partitions, Discrete Math. 6 (1973), 201– 219.

[13] T. Brylawski, The broken circuit complex, Trans. Amer. Math. Soc. 171 (1977), 235–282.

[14] G. Chartrand and L. Lesniak, “Graphs and Digraphs,” second edition, Wadsworth & Brooks/Cole, Monteray, CA, 1986.

[15] P. H. Edelman and V. Reiner, Free hyperplane arrangements between A_{n−1} and B_{n}, preprint.

[16] H. Friedman and D. Tamari, Problèmes d’associativité: Une treillis finis induite par une loi demi-associative, J. Combin. Theory 2 (1967), 215–242.

[17] G. Grätzer, “Lattice Theory,” Freeman and Co., San Francisco, CA, 1971, pp. 17–18, problems 26-36.

[18] C. Greene, A class of lattices with Möbius function ±1, European J. Combin. 9 (1988), 225–240.

[19] C. Greene, Posets of Shuffles, J. Combin. Theory Ser. A 47 (1988), 191–206.

[20] S. Huang and D. Tamari, Problems of associativity: A simple proof for the lattice property of systems ordered by a semi-associative law, J. Combin. Theory Ser. A 13 (1972), 7–13.

[21] J. E. Humphreys, “Reflection Groups and Coxeter Groups,” Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1990.

[22] M. Jambu and L. Paris, Combinatorics of inductively factored arrangements, European J. Combin. 16 (1995), 267–292.

[23] T. Józefiak and B. E. Sagan, Basic derivations for subarrangements of Coxeter arrangements, J. Algebraic Combin. 2 (1993), 291–320.

[24] G. Kreweras, Sur les partitions non-croisées d’un cycle, Discrete Math. 1 (1972), 333–350.

[25] S. Linusson, Möbius functions and characteristic polynomials for subspace arrangements embedded in B_{n}, preprint.

[26] S. Linusson, Partitions with restricted block sizes, Möbius functions and the k-of-each problem, preprint.

[27] P. Orlik and H. Terao, “Arrangements of Hyperplanes,” Grundlehren 300, Springer-Verlag, New York, NY, 1992.

[28] V. Reiner, Non-crossing partitions for classical reflection groups, preprint.

[29] G.-C. Rota, On the foundations of combinatorial theory I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340–368.

[30] K. Saito, Theory of logarithmic differential forms and logarithmic vector fields, J. Fac. Sci. Univ. Tokyo Sec. 1A Math. 27 (1980), 265–291.

[31] R. P. Stanley, Supersolvable lattices, Algebra Universalis 2 (1972), 197–217.

[32] R. P. Stanley, “Enumerative Combinatorics, Volume 1,” Wadsworth and Brooks/Cole, Pacific Grove, CA, 1986.

[33] S. Sundaram, Applications of the Hopf trace formula to computing homology representations, Contemp. Math. 178 (1994), 277–309.

[34] S. Sundaram and M. Wachs, The homology representations of the k-equal partition lattice, Trans. Amer. Math. Soc., to appear.

[35] S. Sundaram and V. Welker, Group actions on linear subspace arrangements and applications to configuration spaces, Trans. Amer. Math. Soc., to appear.

[36] H. Terao, Arrangements of hyperplanes and their freeness I, II, J. Fac. Sci. Univ. Tokyo, 27 (1980), 293–320.

[37] H. Terao, Generalized exponents of a free arrangement of hyperplanes and the Shepherd-Todd-Brieskorn formula, Invent. Math. 63 (1981), 159–179.

[38] H. Terao, Free arrangements of hyperplanes over an arbitrary field, Proc. Japan Acad. Ser. A Math 59 (1983), 301–303.

[39] H. Terao, Factorizations of Orlik-Solomon algebras, Adv. in Math. 91 (1992), 45–53.

[40] T. Zaslavsky, “Facing up to arrangements: Face-count formulas for partitions of space by hyperplanes,” Memoirs Amer. Math. Soc., No. 154, Amer. Math. Soc., Providence, RI, 1975.

[41] T. Zaslavsky, The geometry of root systems and signed graphs, Amer. Math. Monthly 88 (1981), 88–105.

[42] T. Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982) 215–228.

[43] T. Zaslavsky, Chromatic invariants of signed graphs, Discrete Math. 42 (1982) 287–312.

[44] G. Ziegler, Algebraic combinatorics of hyperplane arrangements, Ph. D. thesis, M.I.T., Cambridge, MA, 1987.