y≥x

Let µ denote the M¨bius function of L(A) ∼ L(Aq ). By M¨bius inversion (Theo-

o o

=

rem 1.1),

g(x) = µ(x, y)f (y)

y≥x

µ(x, y)q dim(y) .

=

y≥x

Put x = ˆ to get

0

g(ˆ = µ(y)q dim(y) = χA (q).

0)

y

For the remainder of this lecture, we will be concerned with applications of

Theorem 5.15 and further interesting examples of arrangements.

LECTURE 5. FINITE FIELDS 63

Example 5.12. Let G be a graph with vertices 1, 2, . . . , n, so

(xi ’ xj ).

QAG (x) =

ij∈E(G)

Then by Theorem 5.15,

χAG (q) = q n ’ #{(±1 , . . . , ±n ) ∈ Fn : ±i = ±j for some ij ∈ E(G)}

1

= #{(β1 , . . . , βn ) ∈ Fn : βi = βj ∀ ij ∈ E(G)}

q

= χG (q),

in agreement with Theorem 2.7. Note that this equality holds for all prime powers

q, not just for pm with p 0. This is because the matrix with rows ei ’ ej , where

ij ∈ E(G) and ei is the ith unit coordinate vector in Qn , is totally unimodular, i.e.,

every minor (determinant of a square submatrix) is 0, ±1. Hence the nonvanishing

of a minor is independent of the ambient ¬eld.

A very interesting class of arrangements, including the braid arrangement, is

associated with root systems, or more generally, ¬nite re¬‚ection groups. We will

simply mention some basic results here without proof. A root system is a ¬nite

set R of nonzero vectors in Rn satisfying certain properties that we will not give

here. (References include [4][7][12].) The Coxeter arrangement A(R) consists of

the hyperplanes ± · x = 0, where ± ∈ R. There are four in¬nite (irreducible) classes

of root systems (all in Rn ):

= {ei ’ ej : 1 ¤ i < j ¤ n} = Bn

An’1

= {ei ’ ej , ei + ej : 1 ¤ i < j ¤ n}

Dn

= Dn ∪ {ei : 1 ¤ i ¤ n}

Bn

= Dn ∪ {2ei : 1 ¤ i ¤ n}.

Cn

We should really regard An’1 as being a subset of the space

±i = 0} ∼ Rn’1 .

{(±1 , . . . , ±n ) ∈ Rn : =

We thus obtain the following Coxeter arrangements. In all cases 1 ¤ i < j ¤ n

and 1 ¤ k ¤ n.

: xi ’ x j = 0

A(An’1 ) = Bn

: xi ’ xj = 0, xi + xj = 0, xk = 0

A(Bn ) = A(Cn )

: xi ’ xj = 0, xi + xj = 0.

A(Dn )

See Figure 1 for the arrangements A(B2 ) and A(D2 ).

Let us compute the characteristic polynomial χA(Bn ) (q). For p 0 (actually

p > 2) and q = pm we have

χA(Bn ) (q) = #{(±1 , . . . , ±n ) ∈ Fn : ±i = ±±j (i = j), ±i = 0 (1 ¤ i ¤ n)}.

q

Choose ±1 ∈ F— = Fq ’ {0} in q ’ 1 ways. Then choose ±2 ∈ F— ’ {±1 , ’±1 } in

q q

q ’ 3 ways, then ±3 in q ’ 5 ways, etc., to obtain:

χA(Bn ) (t) = (t ’ 1)(t ’ 3) · · · (t ’ (2n ’ 1)).

In particular,

r(A(Bn )) = (’1)n χA(Bn ) (’1) = 2 · 4 · 6 · · · (2n) = 2n n!.

64 R. STANLEY, HYPERPLANE ARRANGEMENTS

A(B 2 ) A(D2 )

Figure 1. The arrangements A(B2 ) and A(D2 )

By a similar but slightly more complicated argument we get (Exercise 1)

χA(Dn ) (t) = (t ’ 1)(t ’ 3) · · · (t ’ (2n ’ 3)) · (t ’ n + 1).

(37)

Note. Coxeter arrangements are always free in the sense of Theorem 4.14 (a result

of Terao [21]), but need not be supersolvable. In fact, A(An ) and A(Bn ) are

supersolvable, but A(Dn ) is not supersolvable for n ≥ 4 [3, Thm. 5.1].

5.2. The Shi arrangement

We next consider a modi¬cation (or deformation) of the braid arrangement called

the Shi arrangement [15, §7] and denoted Sn . It consists of the hyperplanes

xi ’ xj = 0, 1, 1 ¤ i < j ¤ n.

Thus Sn has n(n ’ 1) hyperplanes and rank(Sn ) = n ’ 1. Figure 2 shows the Shi

arrangement S3 in ker(x1 + x2 + x3 ) ∼ R2 (i.e., the space {(x1 , x2 , x3 ) ∈ R3 :

=

x1 + x2 + x3 = 0}).

Theorem 5.16. The characteristic polynomial of Sn is given by

χSn (t) = t(t ’ n)n’1 .

Proof. Let p be a large prime. By Theorem 5.15 we have

χSn (p) = #{(±1 , . . . , ±n ) ∈ Fn : i < j ’ ±i = ±j and ±i = ±j + 1}.

p

Choose a weak ordered partition π = (B1 , . . . , Bp’n ) of [n] into p ’ n blocks, i.e.,

Bi = [n] and Bi © Bj = … if i = j, such that 1 ∈ B1 . (“Weak” means that we

allow Bi = ….) For 2 ¤ i ¤ n there are p ’ n choices for j such that i ∈ Bj , so

(p’n)n’1 choices in all. We will illustrate the following argument with the example

p = 11, n = 6, and

π = ({1, 4}, {5}, …, {2, 3, 6}, …).

(38)

Arrange the elements of Fp clockwise on a circle. Place 1, 2, . . . , n on some n of

these points as follows. Place elements of B1 consecutively (clockwise) in increasing

order with 1 placed at some element ±1 ∈ Fp . Skip a space and place the elements

of B2 consecutively in increasing order. Skip another space and place the elements

of B3 consecutively in increasing order, etc. For our example (38), say ±1 = 6.

LECTURE 5. FINITE FIELDS 65

Figure 2. The Shi arrangement S3 in ker(x1 + x2 + x3 )

10 0

2

5 9 1

3

8 2

7 3

4 6

6 4

5

1

Let ±i be the position (element of Fp ) at which i was placed. For our example

we have

(±1 , ±2 , ±3 , ±4 , ±5 , ±6 ) = (6, 1, 2, 7, 9, 3).

It is easily veri¬ed that we have de¬ned a bijection from the (p’n)n’1 weak ordered

partitions π = (B1 , . . . , Bp’n ) of [n] into p’n blocks such that 1 ∈ B1 , together with