Finite Fields

LECTURE 5 Finite fields 5.1. The finite field method In this lecture we will describe a method based on finite fields for computing the characteristic polynomial of an arrangement defined over Q. We will then discuss several interesting examples. The main result (Theorem 5.15) is implicit in the work of Crapo and Rota [9, §17]. It was first developed into a systematic tool for computing characteristic polynomials by Athanasiadis [1][2], after a closely related but not as general technique was presented by Blass and Sagan [6]. Suppose that the arrangement A is defined over Q. By multiplying each hyper­ plane equation by a suitable integer, we may assume A is defined over Z. In that case we can take coefficients modulo a prime p and get an arrangement Aq defined over the finite field Fq , where q = pr . We say that A has good reduction mod p (or over Fq ) if L(A) ∪ = L(Aq ). For instance, let A be the affine arrangement in Q1 = Q consisting of the points 0 and 10. Then L(A) contains three elements, viz., Q, {0}, and {10}. If p = ⇔ 2, 5 then 0 and 10 remain distinct, so A has good reduction. On the other hand, if p = 2 or p = 5 then 0 = 10 in Fp , so L(Ap ) contains just two elements. Hence A has bad reduction when p = 2, 5. Proposition 5.13. Let A be an arrangement defined over Z. Then A has good reduction for all but finitely many primes p. Proof. Let H1 , . . . , Hj be affine hyperplanes, where Hi is given by the equation vi · x = ai (vi , ai ≤ Zn ). By linear algebra, we have H1 ⊕ · · · ⊕ Hj = ⇔ � if and only if ⎟ ⎟ � � v1 a1 v1 ⎣ ⎝ .. ⎝ . .. ⎠ = rank ⎞ ... ⎣ (36) rank ⎞ . ⎠. vj aj vj Moreover, if (36) holds then ⎟ v1 ⎣ ⎝ dim(H1 ⊕ · · · ⊕ Hj ) = n − rank ⎞ ... ⎠ . vj � Now for any r × s matrix A, we have rank(A) ⊂ t if and only if some t × t submatrix B satisfies det(B) ⇔= 0. It follows that L(A) ⇔∪ = L(Ap ) if and only if at least one member S of a certain finite collection S of subsets of integer matrices B satisfies the following condition: (≡B ≤ S) det(B) ⇔= 0 but det(B) � 0 (mod p). This can only happen for finitely many p, viz., for certain B we must have p| det(B), so L(A) ∪ � = L(Ap ) for p sufficiently large. The main result of this section is the following. Like many fundamental results in combinatorics, the proof is easy but the applicability very broad. Theorem 5.15. Let A be an arrangement in Qn , and suppose that L(A) ∪ = L(Aq ) for some prime power q. Then ⎤ � � ψA (q) = # �Fnq − H⎢ H⊆Aq = qn − # � H. H⊆Aq Proof. Let x ≤ L(Aq ) so #x = q dim(x) . Here dim(x) can be computed either over Q or Fq . Define two functions f, g : L(Aq ) ∃ Z by f (x) g(x) = = #x � # x− In particular, Clearly ⎤ � ˆ = g(Fnq ) = # �Fnq − g(0) f (x) = � y y>x � � H⊆Aq . � H⎢ . g(y). y∗x ∪ L(Aq ). By M¨ Let µ denote the M¨ obius function of L(A) = obius inversion (Theo­ rem 1.1), � g(x) = µ(x, y)f (y) y∗x = � µ(x, y)q dim(y) . y∗x Put x = 0̂ to get g(0̂) = � µ(y)q dim(y) = ψA (q). y � For the remainder of this lecture, we will be concerned with applications of Theorem 5.15 and further interesting examples of arrangements. Example 5.12. Let G be a graph with vertices 1, 2, . . . , n, so � QAG (x) = (xi − xj ). ij⊆E(G) Then by Theorem 5.15, ψAG (q) = q n − #{(κ1 , . . . , κn ) ≤ Fn1 : κi = κj for some ij ≤ E(G)} = #{(λ1 , . . . , λn ) ≤ Fnq : λi ⇔= λj ≡ ij ≤ E(G)} = ψ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 field. A very interesting class of arrangements, including the braid arrangement, is associated with root systems, or more generally, finite reflection groups. We will simply mention some basic results here without proof. A root system is a finite 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 infinite (irreducible) classes of root systems (all in Rn ): An−1 Dn Bn Cn = {ei − ej : 1 → i < j → n} = Bn = {ei − ej , ei + ej : 1 → i < j → n} = Dn ∅ {ei : 1 → i → n} = Dn ∅ {2ei : 1 → i → n}. We should really regard An−1 as being a subset of the space � {(κ1 , . . . , κn ) ≤ Rn : κi = 0} ∪ = Rn−1 . We thus obtain the following Coxeter arrangements. In all cases 1 → i < j → n and 1 → k → n. A(An−1 ) = Bn A(Bn ) = A(Cn ) A(Dn ) : xi − x j = 0 : xi − xj = 0, xi + xj = 0, xk = 0 : xi − xj = 0, xi + xj = 0. 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 ) ≤ Fnq : κi ⇔= ±κj (i ⇔= j), κi ⇔= 0 (1 → i → n)}. Choose κ1 ≤ F∼q = Fq − {0} in q − 1 ways. Then choose κ2 ≤ Fq∼ − {κ1 , −κ1 } in 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!. 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) (37) ψA(Dn ) (t) = (t − 1)(t − 3) · · · (t − (2n − 3)) · (t − n + 1). 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 modification (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 ∪ R2 (i.e., the space {(x1 , x2 , x3 ) ≤ R3 : arrangement S3 in ker(x1 + x2 + x3 ) = 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 ) ≤ Fnp : i < j ⊆ κi ⇔= κj and κi ⇔= κj + 1}. 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 (38) β = ({1, 4}, {5}, �, {2, 3, 6}, �). 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. Figure 2. The Shi arrangement S3 in ker(x1 + x2 + x3 ) 10 5 0 9 1 8 4 2 2 7 3 6 1 5 3 6 4 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 verified that we have defined 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 the choice of κ1 ≤ Fp , to the set Fnp −∅H⊆(Sn )p H. There are (p−n)n−1 choices for β and p choices for κ1 , so it follows from Theorem 5.15 that ψSn (t) = t(t − n)n−1 . � We obtain the following corollary immediately from Theorem 2.5. Corollary 5.11. We have r(Sn ) = (n + 1)n−1 and b(Sn ) = (n − 1)n−1 . Note. Since r(Sn ) and b(Sn ) have such simple formulas, it is natural to ask for a direct bijective proof of Corollary 5.11. A number of such proofs are known; a sketch that r(Sn ) = (n + 1)n−1 is given in Exercise 3. Note. It can be shown that the cone cSn is not supersolvable for n ⊂ 3 (Ex­ ercise 4) but is free in the sense of Theorem 4.14. 5.3. Exponential sequences of arrangements The braid arrangement (in fact, any Coxeter arrangement) is highly symmetrical; indeed, the group of linear transformations that preserves the arrangement acts transitively on the regions. Thus all regions “look the same.” The Shi arrangement lacks this symmetry, but it still possesses a kind of “combinatorial symmetry” that allows us to express the characteristic polynomials ψSn (t), for all n ⊂ 1, in terms of the number r(Sn ) of regions. Definition 5.14. A sequence A = (A1 , A2 , . . . ) of arrangements is called an expo­ nential sequence of arrangements (ESA) if it satisfies the following three conditions. (1) An is in K n for some field K (independent of n). (2) Every H ≤ An is parallel to some hyperplane H � in the braid arrangement Bn (over K). (3) Let S be a k-element subset of [n], and define ASn = {H ≤ An : H is parallel to xi − xj = 0 for some i, j ≤ S}. Then L(AS ) ∪ = L(Ak ). n Examples of ESA’s are given by An = Bn or An = Sn . In fact, in these cases we have ASn ∪ = Ak × K n−k . The combinatorial properties of ESA’s are related to the exponential formula in the theory of exponential generating functions [19, §5.1], which we now review. Informally, we are dealing with “structures” that can be put on a vertex set V such that each structure is a disjoint union of its “connected components.” We obtain a structure on V by partitioning V and placing a connected structure on each block (independently). Examples of such structures are graphs, forests, and posets, but not trees or groups. Let h(n) be the total number of structures on an n-set V (with h(0) = 1), and let f (n) be the number that are connected. The exponential formula states that � � xn xn = exp f (n) . (39) h(n) n! n! n∗1 n∗0 More precisely, let f : P ∃ R, where R is a commutative ring. (For our purposes, R = Z will do.) Define a new function h : N ∃ R by h(0) = 1 and � f (#B1 )f (#B2 ) · · · f (#Bk ). (40) h(n) = �={B1 ,...,Bk }⊆�n Then equation (39) holds. A straightforward proof can be given by considering the expansion � � xn xn exp f (n) = exp f (n) n! n! n∗1 n∗1 � ⎤ kn � � x � f (n)k k ⎢ . = n! k! n∗1 We omit the details (Exercise 5). k∗0 For any arrangement A in K n , define r(A) = (−1)n ψA (−1). Of course if K = R this coincides with the definition of r(A) as the number of regions of A. We come to the main result concering ESA’s. Theorem 5.17. Let A = (A1 , A2 , . . . ) be an ESA. Then �−t ⎤ n n � � x x ψAn (t) (−1)n r(An ) ⎢ . =� n! n! n∗0 n∗0 Example 5.13. For A = (B1 , B2 , . . . ) Theorem 5.17 asserts that �−t ⎤ n � � x xn =� (−1)n n! ⎢ , t(t − 1) · · · (t − n + 1) n! n! n∗0 n∗0 as immediately follows from the binomial theorem. On the other hand, if A = (S1 , S2 , . . . ), then we obtain the much less obvious identity �−t ⎤ n n � � x x t(t − n)n−1 =� (−1)n (n + 1)n−1 ⎢ . n! n! n∗0 n∗0 Proof of Theorem 5.17. By Whitney’s theorem (Theorem 2.4) we have for any arrangement A in K n that � ψA (t) = (−1)#Btn−rank(B) . B→A B central Let A = (A1 , A2 , . . . ), and let B ∗ An for some n. Define β(B) ≤ Γn to have blocks that are the vertex sets of the connected components of the graph G on [n] with edges E(G) = {ij : ∩ xi − xj = c in B}. (41) Define ψ̃An (t) = � (−1)#B tn−rk(B) . B→A B central �(B)=[n] Then ψAn (t) � = �={B1 ,...,Bk }⊆�n � = �={B1 ,...,Bk }⊆�n � (−1)#B tn−rk(B) B→A B central �(B)=� ˜A#B2 (t) · · · ψ ˜A#Bk (t). ψ ˜A#B1 (t)ψ Thus by the exponential formula (39), � n∗0 ψAn (t) � xn xn = exp ψ̃An (t) . n! n! n∗1 But β(B) = [n] if and only if rk(B) = n − 1, so ψ̃An (t) = cn t for some cn ≤ Z. We therefore get � � xn xn ψAn (t) = exp t cn n! n! n∗0 n∗1 �t ⎤ � xn bn ⎢ , = � n! n∗0 where exp � n x n∗1 cn n! � n x n∗0 bn n! . Put t = −1 to get �−1 ⎤ n � � xn x (−1)n r(An ) =� bn ⎢ , n! n! = n∗0 n∗0 from which it follows that � n∗0 n ψAn (t) ⎤ x =� n! � (−1)n r(An ) n∗0 n �−t x ⎢ n! . � For a generalization of Theorem 5.17, see Exercise 10. 5.4. The Catalan arrangement Define the Catalan arrangement Cn in K n , where char(K) ⇔= 2, by � QCn (x) = (xi − xj )(xi − xj − 1)(xi − xj + 1). 1⊇i xw(2) > · · · > xw(n) of Bn is divided “in the same way” in Cn . In particular, if r0 (Cn ) denotes the number of regions of Cn contained in some fixed region of Bn , then r(Cn ) = n!r0 (Cn ) . See Figure 3 for C3 in the ambient space ker(x1 + x2 + x3 ), where the hyperplanes of B3 are drawn as solid lines and the remaining hyperplanes as dashed lines. Each region of B3 contains five regions of C3 , so r(C3 ) = 6 · 5 = 30. We can compute r(Cn ) (or equivalently r0 (Cn )) by a direct combinatorial ar­ gument. Let R0 denote the region x1 > x2 > · · · > xn of Bn . The regions of Cn contained in R0 are determined by those i < j such that xi − xj < 1. We need only specify the maximal intervals [i, j] such that xi − xj < 1, i.e., if a → i < j → b and xa − xb < 1, then a = i and b = j. It is easy to see that any such specification of maximal intervals determines a region of Cn contained in R0 . Thus r0 (Cn ) is equal Figure 3. The Catalan arrangement C3 in ker(x1 + x2 + x3 ) to the number of antichains A of strict intervals of [n], i.e., sets A of intervals [i, j], where 1 → i < j → n, such that no interval in A is contained in another. (“Strict” means that i = j is not allowed.) It is known (equivalent to [19, Exer. 6.19(bbb)]) ⎜2n� 1 that the number of such antichains is the Catalan number Cn = n+1 n . For the sake of completeness we give a bijection between these antichains and a stan­ dard combinatorial structure counted by Catalan numbers, viz., lattice paths from (0, 0) to (n, n) with steps (1, 0) and (0, 1), never rising above the line y = x ([19, Exer. 6.19(h)]). Given an antichain A of intervals of [n], there is a unique lattice path of the claimed type whose “outer corners” (a step (1, 0) followed by (0, 1)) consist of the points (j, i − 1) where [i, j] ≤ A, together with the points (i, i − 1) where no interval in A contains i. Figure 4 illustrates this bijection for n = 8 and A = {[1, 4], [3, 5], [7, 8]}. We have therefore proved the following result. For a refinement, see Exercise 11. Proposition 5.14. The number of regions of the Catalan arrangement Cn is given by r(Cn ) = n!Cn . Each region of Bn contains Cn regions of Cn . In fact, there is a simple formula for the characteristic polynomial ψCn (t). Theorem 5.18. We have ψCn (t) = t(t − n − 1)(t − n − 2)(t − n − 3) · · · (t − 2n + 1). 86 65 52 40 Figure 4. A bijection corresponding to A = {[1, 4], [3, 5], [7, 8]} Proof. Clearly the sequence (C1 , C2 , . . . ) is an ESA, so by Theorem 5.17 we have �−t ⎤ n � � xn x ψCn (t) (−1)n n!Cn ⎢ = � n! n! n∗0 n∗0 ⎤ �−t � (−1)n Cn xn ⎢ . = � n∗0 One method for expanding this series is to use the Lagrange inversion formula [19, Thm. 5.4.2]. Let F (x) = a1 x + a2 x2 + · · · be a formal power series over K, where char(K) = 0 and a1 ⇔= 0. Then there exists a unique formal power series F ∧−1∨ = a−1 1 x + · · · satisfying F (F ∧−1∨ (x)) = F ∧−1∨ (F (x)) = x. Let k, t ≤ Z. The Lagrange inversion formula states that �t � x t ∧−1∨ k t−k (42) t[x ]F (x) = k[x ] . F (x) � Let y = n∗0 (−1)n Cn xn+1 . By a fundamental property of Catalan numbers, y 2 = −y + x. Hence y = (x + x2 )∧−1∨ . Substitute t − n for k and apply equation (42) to y = F (x), so F ∧−1∨ (x) = x + x2 : � �t x t 2 t−n n (43) t[x ](x + x ) = (t − n)[x ] . y The right-hand side of (43) is just (t − n)[xn ] � y �−t x = (t − n)ψCn (t) . n! a f c b d e f c d a e b Figure 5. An example of an interval order The left-hand side of (43) is given by � � t(t − n)(t − n − 1) · · · (t − 2n + 1) t−n t[xt ]xt−n (1 + x)t−n = t = . n n! It follows that ψCn (t) = t(t − n − 1)(t − n − 2)(t − n − 3) · · · (t − 2n + 1) for all t ≤ Z. It then follows easily (e.g., using the fact that a polynomial in one variable over a field of characteristic 0 is determined by its values on Z) that this equation holds when t is an indeterminate. � Note. It is not difficult to give an alternative proof of Theorem 5.18 based on the finite field method (Exercise 12). 5.5. Interval orders The subject of interval orders has a long history (see [10][23]), but only recently [20] was their connection with arrangements noticed. Let P = {I1 , . . . , In } be a finite set of closed intervals Ii = [ai , bi ], where ai , bi ≤ R and ai < bi . Partially order P by defining Ii < Ij if bi < aj , i.e., Ii lies entirely to the left of Ij on the real number line. A poset isomorphic to P is called an interval order. Figure 5 gives an example of six intervals and the corresponding interval order. It is understood that the real line lies below and parallel to the line segments labelled a, . . . , f , and that the actual intervals are the projections of these line segments to R. If all the intervals Ii have length one, then P is called a semiorder or unit interval order. We will be considering both labelled and unlabelled interval orders. A labelled interval order is the same as an interval order on a set S, often taken to be [n]. If an interval order P corresponds to intervals I1 , . . . , In , then there is a natural 1 6 3 3 6 Figure 6. The number of labelings of semiorders with three elements labeling of P , viz., label the element corresponding to Ii by i. Thus the intervals I1 = [0, 1] and I2 = [2, 3] correspond to the labelled interval order P1 defined by 1 < 2, while the intervals I1 = [2, 3] and I2 = [0, 1] correspond to P2 defined by 2 < 1. Note that P1 and P2 are different labelled interval orders but are isomorphic as posets. As another example, consider the intervals I1 = [0, 2] and I2 = [1, 3]. The corresponding labelled interval order P consists of the disjoint points 1 and 2. If we now let I1 = [1, 3] and I2 = [0, 2], then we obtain the same labelled interval order (or labelled poset) P , although the intervals themselves have been exchanged. An unlabelled interval order may be regarded as an isomorphism class of interval orders; two intervals orders P1 and P2 represent the same unlabelled interval order if and only if they are isomorphic. Of course our discussion of labelled and unlabelled interval orders applies equally well to semiorders. Figure 6 shows the five nonisomorphic (or unlabelled) interval orders (which for three vertices coincides with semiorders) with three vertices, and below them the number of distinct labelings. (In general, the number of labelings of an nelement poset P is n!/#Aut(P ), where Aut(P ) denotes the automorphism group of P .) It follows that there are 19 labelled interval orders or labelled semiorders on a 3-element set. The following proposition collects some basic results on interval orders. We sim­ ply state them without proof. Only part (a) is needed in what follows (Lemma 5.6). We use the notation i to denote an i-element chain and P + Q to denote the disjoint union of the posets P and Q. Proposition 5.15. (a) A finite poset is an interval order if and only if it has no induced subposet isomorphic to 2 + 2. (b) A finite poset is a semiorder if and only if it has no induced subposet isomorphic to 2 + 2 or 3 + 1. (c) A finite poset P is a semiorder if and only if its elements can be ordered as I1 , . . . , In so that the incidence matrix of P (i.e., the matrix M = (mij ), where mij = 1 if Ii < Ij and mij = 0 otherwise) has the form shown below. Moreover, all such semiorders are nonisomorphic. 000 000 000 001 000 000 011 000 000 001 001 000 011 001 000 Figure 7. The semiorders with three elements 1 n 1 1 0 n In (c) above, the southwest boundary of the positions of the 1’s in M form a lattice path which by suitable indexing goes from (0, 0) to (n, n) with steps (0, 1) and (1, 0), never rising above y = x. Since the number of such lattice paths is the Catalan number Cn , it follows that the number of nonisomorphic n-element semiorders is Cn . Later (Proposition 5.17) we will give a proof based on properties of a certain arrangement. Figure 7 illustrates Proposition 5.15(c) when n = 3. It shows the matrices M , the corresponding set of unit intervals, and the associated semiorder. Let σ1 , . . . , σn > 0 and set ρ = (σ1 , . . . , σn ). Let Pδ denote the set of all interval orders P on [n] such that there exist a set I1 , . . . , In of intervals corresponding to P P (with Ii corresponding to i ≤ P ) such that σ(Ii ) = σi . In other words, i < j if and only if Ii lies entirely to the left of Ij . For instance, it follows from Figure 6 that #P(1,1,1) = 19. We now come to the connection with arrangements. Given ρ = (σ1 , . . . , σn ) as above, define the arrangement Iδ in Rn by letting its hyperplanes be given by xi − x j = σ i , i = ⇔ j. (Note the condition i ⇔= j, not i < j.) Thus Iδ has rank n − 1 and n(n − 1) hyperplanes (since σi > 0). Figure 8 shows the arrangement I(1,1,1) in the space ker(x1 + x2 + x3 ). Proposition 5.16. Let ρ ≤ Rn+ . Then r(Iδ ) = #Pδ . Figure 8. The arrangement I(1,1,1) in the space ker(x1 + x2 + x3 ) Proof. Let (x1 , . . . , xn ) belong to some region R of Iδ . Define the interval Ii = [xi − σi , xi ]. The region R is determined by whether xi − xj < σi or xi − xj > σi . Equivalently, Ii ⇔> Ij or Ii > Ij in the ordering on intervals that defines interval orders. Hence the number of possible interval orders corresponding to intervals � I1 , . . . , In with σ(Ii ) = σi is just r(Iδ ). Consider the case σ1 = · · · = σn = 1, so we are looking at the semiorder arrangement xi − xj = 1 for i = ⇔ j. We abbreviate (1, 1, . . . , 1) as 1n and denote this arrangement by I1n . By the proof of Proposition 5.16 the regions of I1n are in a natural bijection with semiorders on [n]. Now note that Cn = I1n ∅ Bn , where Cn denotes the Catalan arrangement. Fix a region R of Bn , say x1 < x2 < · · · < xn . Then the number of regions of I1n that intersect R is the number of semiorders on [n] that correspond to (unit) intervals I1 , . . . , In with right endpoints x1 < x2 < · · · < xn . Another set I1� , . . . , In� of unit intervals Ii� = [x�i − 1, xi� ] with x�1 < x�2 < · · · < x�n defines a different region from that defined by I1 , . . . , In if and only if the corresponding semiorders are nonisomorphic. It follows that the number of nonisomorphic semiorders on [n] is equal to the number of regions of I1n intersecting the region x1 < x2 < · · · < xn of Bn . Since Cn = I1n ∅ Bn , there follows from Proposition 5.14 the following result of Wine and Freunde [24]. Proposition 5.17. The number u(n) of nonisomorphic n-element semiorders is given by 1 u(n) = r(Cn ) = Cn . n! Figure 9 shows the nonisomorphic 3-element semiorders corresponding to the regions of Cn intersecting the region x1 < x2 < · · · < xn of Bn . We now come to the problem of determining r(I1n ), the number of semiorders on [n]. x3 = x2 x3 = x2 + 1 3 2 3 2 1 1 3 2 x 2 = x1 +1 3 1 1 1 2 3 2 x2 = x1 Figure 9. The nonisomorphic 3-element semiorders as regions of C1n Theorem 5.19. Fix distinct real numbers a1 , a2 , . . . , am > 0. Let An be the ar­ rangement in Rn with hyperplanes xi − xj = a1 , . . . , am , i = ⇔ j, An : and let A∼n = An ∅ Bn . Define F (x) = � r(An ) xn n! r(A∼n ) xn . n! n∗1 G(x) = � n∗1 Then F (x) = G(1 − e−x ). Proof. Let c(n, k) denote the number of permutations w of n objects with k cycles (in the disjoint cycle decomposition of w). The integer c(n, k) is known as a signless Stirling number of the first kind and for fixed k has the exponential generating function � (44) c(n, k) n∗0 �k 1 ⎜ xn = log(1 − x)−1 . n! k! For futher information, see e.g. [18, pp. 17–20][19, (5.25)]. We have F (x) = G(1 − e−x ) √ G(x) = F (log(1 − x)−1 ) � �k 1 ⎜ r(Ak ) log(1 − x)−1 = k! k∗1 = � r(Ak ) � c(n, k) n∗0 k∗1 xn . n! It follows that we need to show that r(A∼n ) = (45) n � c(n, k)r(Ak ). k=1 For simplicity we consider only the case m = 1 and a1 = 1, but the argument is completely analogous in the general case. When m = 1 and a1 = 1 we have that r(A∼n ) = n!Cn and that r(An ) is the number of semiorders on [n]. Thus it suffices χ to give a map (P, w) �∃ Q, where w ≤ Sk and P is a semiorder whose elements are labelled by the cycles of w, and where Q is an unlabelled n-element semiorder, such that χ is n!-to-1, i.e., every Q appears exactly n! times as an image of some (P, w). Choose w ≤ Sn with k cycles in c(n, k) ways, and make these cycles the vertices of a semiorder P in r(Ak ) ways. Define a new poset χ(P, w) as follows: if the cycle (c1 , . . . , cj ) is an element of P , then replace it with an antichain with elements c1 , . . . , cj . Given 1 → c → n, let C(c) be the cycle of w containing c. Define c < d in χ(P, w) if C(c) < C(d) in P . We illustrate this definition with n = 8 and w = (1, 5, 2)(3)(6, 8)(4, 7): (3) (4,7) 3 4 7 6 8 ρ (1,5,2) (6,8) ( P,w ) 1 5 2 Q = ρ ( P,w) Given an unlabelled n-element semiorder Q, such as we now show that there are exactly n! pairs (P, w) for which χ(P, w) ∪ = Q. Call a pair of elements x, y ≤ Q autonomous if for all z ≤ Q we have x < z √ y < z, x > z √ y > z. Equivalently, the map δ : Q ∃ Q transposing x, y and fixing all other z ≤ Q is an automorphism of Q. Clearly the relation of being autonomous is an equivalence relation. Partition Q into its autonomous equivalence classes. Regard the elements of Q as being distinguished, and choose a bijection (labeling) � : Q ∃ [n] (in n! ways). Fix a linear ordering (independent of �) of the elements in each equivalence class. (The linear ordering of the elements in each equivalence class in the diagram below is left-to-right.) 5 3 6 7 4 1 2 8 In each class, place a left parenthesis before each left-to-right maximum, and place a right parenthesis before each left parenthesis and at the end. (This is the bijection Sn ∃ Sn , w ˆ �∃ w, in [18, p. 17].) Merge the elements c1 , c2 , . . . , cj (appearing in that order) between each pair of parentheses into a single element labelled with the cycle (c1 , c2 , . . . , cj ). (5) (4 , 1) (5) (4,1) ρ −1 (3) (7 , 6) (2) (8) 3 Q (7,6) (2) P We have thus obtained a poset P whose elements are labelled by the cycles of a permutation w ≤ Sn , such that χ(P, w) = Q. For each unlabelled Q, there are exactly n! pairs (P, w) (where the poset P is labelled by the cycles of w ≤ Sn ) for which χ(P, w) ∪ = Q. Since by Proposition 5.17 there are Cn nonisomorphic n-element semiorders, we get n!Cn = n � c(n, k)r(Ak ). k=1 � Note. Theorem 5.19 can also be proved using Burnside’s lemma (also called the Cauchy-Frobenius lemma) from group theory. To test one’s understanding of the proof of Theorem 5.19, consider why it doesn’t work for all posets. In other words, let f (n) denote the number of posets on � n [n] and g(n) � the number of nonisomorphic n-element posets. Set F (x) = f (n) xn! and G(x) = g(n)xn . Why doesn’t the above argument show that G(x) = F (1 − (8) e−x )? Let Q = 2 + 2 (the unique obstruction to being an interval order, by Proposition 5.15(a)). The autonomous classes have one element each. Consider the two labelings � : Q ∃ [4] and the corresponding χ−1 : 2 4 1 3 4 2 3 1 ρ −1 ρ −1 2 4 1 3 4 2 3 1 We obtain the same labelled posets in both cases, so the proof of Theorem 5.19 fails. The key property of interval orders that the proof of Theorem 5.19 uses implicitly is the following. Lemma 5.6. If π : P ∃ P is an automorphism of the interval order P and π(x) = π(y), then x and y are autonomous. Proof. Assume not. Then there exists an element s ≤ P satisfying s > x, s > ⇔ y (or dually). Since π(x) = y, there must exist t ≤ P satisfying t > y, t > ⇔ x. But then {x, s, y, t} form an induced 2 + 2, so by Proposition 5.15(a) P is not an interval order. � Specializing m = 1 and a1 = 1 in Theorem 5.19 yields the following corollary, due first (in an equivalent form) to Chandon, Lemaire and Pouget [8]. Corollary 5.12. Let f (n) denote the number of semiorders on [n] (or n-element labelled semiorders). Then � xn f (n) = C(1 − e−x ), n! n∗0 where C(x) = � n Cn x = n∗0 1− ≥ 1 − 4x . 2x 5.6. Intervals with generic lengths A particularly interesting class of interval orders are those corresponding to intervals with specified generic lengths ρ = (σ1 , . . . , σn ). Intuitively, this means that the intersection poset P (Iδ ) is as “large as possible.” One way to make this precise is to say that ρ is generic if P (Iδ ) ∪ = P (Iδ� ), where ρ � = (σ�1 , . . . , σ�n ) and the � σi ’s are linearly independent over Q. Thus if ρ is generic, then the intersection poset L(Iδ ) does not depend on ρ, but rather only on n. In particular, r(Iδ ) does not depend on ρ (always assuming ρ is generic). Hence by Proposition 5.16, the number #Pδ of labelled interval orders corresponding to intervals I1 , . . . , In with σ(Ii ) = σi depends only on n. This fact is not at all obvious combinatorially, since the interval orders themselves do depend on ρ. For instance, it is easy to see that ρ = (1, 1.0001, 1.001, 1.01, 1.1) is generic and that no corresponding interval order can be isomorphic to 4 + 1. On the other hand, ρ = (1, 10, 100, 1000, 10000) is also generic, but this time there is a corresponding interval order isomorphic to 4 + 1. (See Exercise 17.) The preceding discussion raises the question of computing #Pn when ρ is generic. We write Gn for the corresponding interval order xi − xj = σi , i ⇔= j, since the intersection poset depends only on n. The following result is a nice appli­ cation of arrangements to “pure” enumeration; no proof is known except the one sketched here. Theorem 5.20. Let � x2 x3 x4 x5 xn = 1 + x + 3 + 19 + 195 + 2831 + · · · . z= r(Gn ) n! 2! 3! 4! 5! n∗0 Define a power series y =1+x+5 by 1 = y(2 − exy ). Equivalently, y =1+ � x2 x3 x4 + 46 + 631 + · · · 2! 3! 4 1 + 2x 1 log 1+x 1+x �∧−1∨ . Then z is the unique power series satisfying z � /z = y 2 , z(0) = 1. � Note. The condition z � /z = y 2 can be rewritten as z = exp y 2 dx. Sketch of proof. Putting t = −1 in Theorem 2.4 gives � (46) r(Gn ) = (−1)#B−rk(B) . B→Gn B central Given a central subarrangement B ∗ Gn , define a digraph (directed graph) GB on [n] by letting i ∃ j be a (directed) edge if the hyperplane xi − xj = σi belongs to B. One then shows that as an undirected graph GB is bipartite, i.e., the vertices can be partitioned into two subsets U and V such that all edges connect a vertex in U to a vertex in V . The pair (U, V ) is called a vertex bipartition of GB . Moreover, if B is a block of GB (as defined preceding Proposition 4.11), say with vertex bipartition (UB , VB ), then either all edges of B are directed from UB to VB , or all edges are directed from VB to UB . It can also be seen that all such directed bipartite graphs can arise in this way. It follows that equation (46) can be rewritten � (−1)e(G)+c(G) 2b(G) , (47) r(Gn ) = (−1)n G where G ranges over all (undirected) bipartite graphs on [n], e(G) denotes the number of edges of G, and b(G) denotes the number of blocks of G. Equation (47) reduces the problem of determining r(G) to a (rather difficult) problem in enumeration, whose solution may be found in [14, §6]. � 5.7. Other examples There are two additional arrangements related to the braid arrangement that in­ volve nice enumerative combinatorics. We merely repeat the definitions here from Lecture 1 and assemble some of their basic properties in Exercises 19–28. The Linial arrangement in K n is given by the hyperplanes xi − xj = 1, 1 → i < j → n. It consists of “half” of the semiorder arrangement I1n . Despite its similarity to I1n , it is considerably more difficult to obtain its characteristic polynomial and other enumerative invariants. Finally the threshold arrangement in K n is given by the hyperplanes xi + xj = 0, 1 → i < j → n. It is a subarrangement of the Coxeter arrangements A(Bn ) (=A(Cn )) and A(Dn ).