F WI WW IH J WI 1H ‘\ W Iooo l (/3010) \ ‘mlll‘lllllllflll'ljlllllflllfllml “ 3 1293 00 2 This is to certify that the dissertation entitled q-Analogs and Vector Spaces presented by Kathy J. Dempsey has been accepted towards fulfillment of the requirements for Ph . D degree in Mathematics Major professéy’ Date 8/6/92 A'ISU is an Affirmattw' Act/m1“lit/nu! Opportunity Institution 0- 12771 LHBRARY Michigan State Universlty PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. DATE DUE DATE DUE DATE DUE c:\cbrc\datedue. ems-0,1 q-ANALOGS AND VECTOR SPACES By Kathy J. Dempsey A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY Department of I\"Iathematics 19912 i‘o “V0 t‘f3 \‘j\ ABSTRACT q—ANALOGS AND VECTOR SPACES BY Kathy J. Dempsey First, we give q-analogs of several known identities involving the Stirling numbers of the second kind and prove them combinatorially using partitions or restricted growth functions and vector spaces. Sequences of lines in vector spaces over finite fields can be used to represent these q-Stirling numbers of the second kind. We introduce a partial order on such sequences to form a poset which in many ways is a q-analog of the partition lattice. Finally, we define the q-cross product of a ranked poset with f) and a one chain and show that, with this construction, we get a nice formula for the Mobius function. In particular, the subspace lattice can be written as a q-cross product and this combinatorially explains the fact that its Mobius function factors nicely. DEDICATION To Bob and Bub iii ACKNOWLEDGEMENTS I would like to thank my parents and all the other people who have helped and encouraged me along the way though they are too numerous to name. In addition a hearty yee-ha goes out to the Easy Money softball club for helping to keep me sane for the last three years. Finally, I would like to acknowledge the Reverend Bob, and the Clemens St. Temple, without whom all of this would have been much easier. Contents 0.1 Introduction ................................ 1 1 Bijective proofs of q-analogs 4 1.1 Partitions ................................. 4 1.? Restricted growth functions ....................... 10 1.3 Vector spaces ............................... 13 2 A q-Partition Lattice 19 2.1 Preliminaries ............................... 20 2.2 The Mobius Function ........................... 29 3 q-Cross Products 35 3.1 General Theory .............................. 36 3.2 The Subspace Lattice ........................... 37 BIBLIOGRAPHY 41 a- Twh 0.1 Introduction The concept of a q-analog plays a major role in this entire work. There is no rigorous definition of a q-analog, so we will give a “pseudo-definition.” Given any mathematical object, for example a number, theorem, definition, or identity, a q-analog of it is something (a number, theorem, definition, or identity) such that if we take the limit as q —> 1 then we get back the original object. For example, a q-analog of the number 4 might be 1+q+ q2+q3. It is very important to notice that q-analogs are not unique. There may be several equally valid q-analogs of the same object. The reasons for studying q—analogs are varied. Generalization is one reason in and of itself. Further, by using weight functions, we can use q—analogs to study more specifically what is happening within a class of objects. As an example of this consider the binomial coefficients n n! = —— ' * > (k) kl(n _ k)! ‘f n’ I” - 0 It is well known that (Z) is the number of sequences of 0’s and 1’s consisting of k 0’s and n — 1: 1’5. We will use the notation {{Ok,1"‘k}} to denote the set of all such sequences. We say ('2) counls these sequences. We will now define a q-analog of the binomial coefficients and show how it relates to these sequences. Let N = {0. 1,2, . . .} be the natural numbers and let q be an indeterminate. If k E N define a q-analog of k by llfl=1+q+q2+-~+qk"‘- Further define a q-analog of the factorial by [k]! = [km- - 11---[21[11. 1 t0 We can then define the q-binomial coefficients [Hzfi ifn,k20 For example [ 3 ] = BMW 2 [lelllll = 1 + q + q2 The history of the q-binomial coefficients can be traced all the way back to Gauss. Although it is not clear from this definition the [Z] are polynomials. This fact is a q-analog of the fact that the usual binomial coefficients are integers. It is easy to see that if we set q = 1 in the q-binomial coefficients we get back the usual binomial coefficients. A statistic is a function from a set to the non-negative integers. Using statistics we can keep track of additional information about individual elements of the set. We now define a statistic on {{Ok,1"""‘}}. If to = W1LU2 . . .wn E {{Ok,1"'k}} then define an inversion to be a pair (whwj) where i < j and w,- > wj. Note that this definition is independent of the fact that we are using only 0’s and 1’s, it works for any ordered alphabet. Then we let the number of inversions in w be invw = lif’w‘uwjl l i < w. = 1 and wj = 0}! where | ~ I denotes cardinality. For example, if n = 5, k = 3 and w = 1 0 1 1 0, then invw = 4. For our puposes a weight is a function from a set to the polynomial ring Zlq] (weight functions can also have values in fields or groups). For to E {{Ok,1"'k}} we define wtw : qlnv‘”. Then it can be shown that TL 2 Wtw = |: k :| w6{{0k,1”-k}} For example, we again see that [g] = wt(0 01)+ wt(010)+wt(10 0) = 1+q+q2 This equation makes it clear that the q-binomial coefficients are polynomials. In the situation where the sum of the weights of all objects in a set gives a polynomial, we say the polynomial counts the set with that weight. Here we say the q-binomial coefficients count sequences of k 0’s and n — k 1’5 with wtw = qinv‘“. In this example we see that by using q-analogs we obtain more information about these sequences than we would by merely counting them with the usual binomial coefficients. Another reason for studying q-analogs is their conection with linear algebra. Here all vector spaces will be over finite fields. If (1 is a prime power and we consider the vector space of dimension 11 over the field G'Fq then the q-binomial coe‘ffients have another interpretation. In this situation, the q-binomial coefficient is the number of k dimensional subspaces of the n dimensional space. One of our goals in this thesis will be to further study ways in which q—analogs can be studied in terms of vector spaces and set partitions. In the first chapter we will prove q-analogs of several identities found in Comtet [Com 74]. These identities will be proved in two ways: first using standard combinatorial techniques and then using vector space ideas. In the second chapter we will define and examine a partially ordered set which in many ways is a q-analog of the partition lattice. Finally, in the last chapter we begin to look at the possibility of forming posets by using a q-analog of the cross product of posets. Chapter 1 Bijective proofs of q-analogs The q-Stirling numbers of the second kind were introduced by Carlitz [Car 33, Car 48] and were also studied by Gould [Con 61] and Milne [Mil 78]. Later, Milne [Mil 82] showed that these numbers could be viewed as generating functions for an inversion statistic on partitions. Also, Milne [Mil 82] and VVachs and White [VV-W 91] showed that these q-Stirling numbers of the second kind also count restricted growth functions using an equivalent statistic. Finally, Milne [Mil 82] gave a vector space interpretation of these numbers. The purpose of this chapter is to give q-analogs of three old identities [Com 74] and to prove them by various combinatorial techniques. Each identity is proved using either partitions or restricted growth functions and then proved again using vector spaces. 1.1 Partitions Let n = {1, . . . , n}. The set of all partitions of a into disjoint subsets Bl, B2, . . . , Bk (sometimes called parts or blocks) will be denoted S(n_, k). Thus the ordinary Stirling numbers of the second kind are S(n, k) 2 [5(11, 1.7)]. If 71' E 5(n, k) then we write 7r 2 Bl/B-2/---/B;c 4 with the convention that 1: minB1< minBz--- < mian. Given such a partition 7r we will let m,- = min B; and denote by b.- any element of B,- \ {mi}. It should also be noted that we always refer to elements of 7r with small letters, and to blocks of 7r with capital letters. It is easy to see that we have the following recursion for the ordinary Stirling numbers of the second kind. . __ S(n—1,k—1)+kS(n—1,k)ifn,k21 501’“ _{ 6,“ ifn = 0 or k = 0 (1'1) where 6m); is the Kronecker delta. If 7r 6 5(3, k) we define an inversion to be a pair (b;,mj) such that b.- > m]- and i < j. Note that this definition is similar to that in the introduction when dealing with sequences. The inversion set of7r is Inv7r = {(b,,mj) I b,- > m,- and i 0 then qinvrr = Z qinvrr+ Z qinvrr 7rES(_r£,k) Bk={n} Bk¢inl qinvrr’+(1+q+ + qk—l) Z qinvr' 1r’ES(_n—1,k—1) «ESQ—1,16) where the (1 + q + - - - + qk‘l) comes from the inversions causes by the element n 6 7r. Hence by induction qinvrr : Z qinvrr’ + [16] Z qinv 11" ”65(21) rr’E$(1—-1,k—1) «'esm—uc) _ S[n — 1,19 — 1] + [k]S[n — 1,13] 5[n,1c] I Comtet [Corn 74] contains several identities involving the Stirling numbers of the second kind. Theorems 1.1.3 through 1.3.4 are q-analogs of some of these identites. These q-analogs also appear (independently) in de Médicis and Leroux [M-L ta]. The following theorem is a q-analog of [Com 74, 5.3c]. The proof appearing here is ba- sically analogous to that in de Médicis and Leroux [M—L ta, 2.12] except that theirs uses non-inversions where this proof uses inversions. Theorem 1.1.3 For all n.1c E N S[71, kl : Z qj—k+1Slji k _1l :20 Proof. The left side counts partitions, 7r, of n with 1; parts and wt 7r 2 qln”. On the other hand (";1)S[j,1c — 1] counts partitions o of j-subsets A Q {2, 3, . . . , 72} into 18 — 1 parts with wta = qi—quinva. So, given a partition, 7r : Bl/B'Z/ ' ' ' /Bl~‘7 0f 2 define the Pair (14,0) as follows. A = {i | 2 S i S n, i 2 ml for some l or i causes an inversion in 1r} Let a = Cl/C2/---/Ck_1 where for i E A, ifi 2 ml then let i 6 01-1 and ifi = b; causes an inversion in 1r then let i 6 C1. For example, 14/237/569/8 ——> {2,4,5,7,8,9} and 24/57/89 Now, we must show that this map is well-defined. It is easy to see that a has k—l blocks since no element in the 1;“ block of it can cause an inversion. We note also that the first element of the I” block of a is merely the first element of the 1+ 1‘t block of 71'. Hence ifi Z 2 is not the first element of a block and i E C; then i E B; and i caused an inversion in 71'. Thus i >ml+1 : min 0;. Further, weights are preserved by this map: If i causes t inversions in 7r then i causes t — 1 inversions in 0 because the first elements of the blocks have moved left. Thus a has one less inversion than 7r for each element that caused an inversion in 71'. But there arej — (k — 1) = j — 1: + 1 such elements since a is a partition ofj things into k — 1 parts and hence k — 1 of thesej things are the minimum of some block and the rest caused inversions in 71' by the definition of A. Thus wt 7." : qmvz : (11—k+lqmva : Wt 0.. The inverse map is given as follows: Given A g {2, 3, . . . ,n} and o a partition of A into k—l parts, form 7r by adding a first block with 1 as its initial element and shifting all non—initial elements left one block. Then we must insert all missing elements from {1, 2,. . . , n} so that they are not initial elements and cause no inversions. This can be done uniquely since the first elements of the block form a strictly increasing sequence. To do this i is placed in the 1th block of 7r if min B, < i < min Bl“. For example, if n = 9 {2,3,6,8} '2/38/6 ——+1/'28/3/6———>1/28/345/679 . The following is a q-analog of [Com 74, 5.36] which also appears in de Médicis and Leroux [M-L ta, 3.8] with an analagous proof. Theorem 1.1.4 For all n, k E N n—k Slmkl = Z(—1)j[k + 111-5112 +1.1c +j+11 i=0 where [13+ 1],- 2 [19+ 1][1c+2]---[1c+j]. Proof. If a; = wlwg . . .w, is a string of integers with w,- 6 {0,1,.. .,lc + i — 1} and 7r = 31/32/ - - - /Bk+j+1 is a partition of n + 1 we say that the weight of the pair (to, 7r) is q: “"qlnvr' and its sign is (—1)j. So, it suffices to find a weight preserving, Sign reversing involution, f, on such pairs with fixed points corresponding to S'[n,1c]. The sum of the weights of all such pairs will then be S[n, 1c] because pairs with opposite signs will cancel and only the fixed points will remain. These will be pairs that are in one-to-one correspondence with partitions on into 1: parts and so will correspond to S[n,1c]. Define f(w,7r) = (w’,7r’) as follows: F—I (\9 C2.) . If {n +1} is a block of 7r and j : 0 then f(w,7r) = (w,7r) . If {n + 1} is a block of 71' and j > 0 then define w’ = w1w2.. .wj_1. Further, let 7r’ 2 Cl/C2/~--/Ck+j where Ck+j_wj = Bk+j_w1 U {n +1} and C,- = B,- for i¢k+j—UJJ'. . If {n + I} is not a block of 7r then let w’ = wlwg . . -wj°~’j+1 where Wj+1 is the number of inversions caused by n + 1 in 7r. Also let 7r’ be 71' with n + I removed to its own part. First we check that f is weight preserving. In case 1 this is clear. In case 2, we lose q”) from the weight in going from w to w’ but by adding n + 1 to block number 10 1c +j — a), we gain wj inversions in 7r’. Hence the weights are the same. The exact opposite changes occur in case 3, again leaving us with the same weight. Pairs in cases 2 and 3 clearly change signs since the length of w’ changes from that of to by exactly one. Finally, since parts 2 and 3 simply reverse one another, we have f2 = id. So f is a weight preserving, sign reversing involution with fixed points corresponding to those pairs which fall under case 1. But these are pairs where w = 0 and 7r is a partition of n +1 into k + 1 parts where the last part contains only n + 1. These clearly correspond to partitions ofn into 1; parts and since the n + 1 causes no inversions, the weights are the same. Thus the fixed points of f correspond to S'[n,1:] as desired. I 1.2 Restricted growth functions Partitions can also be modeled using restricted growth functions [Mil 82, W-W 91]. We can then count these restricted growth functions using the q-Stirling numbers of the second kind. Let w = wlwg . . .wn be a word with w,- E Z+. We say that w is a restricted growth function of length n if to] = 1 and w;§ maij+1for2SiSn l_<__)<1 Let RG(n,1c) stand for the set of all restricted growth functions of length n and largest element 1‘. We construct a bijection f: 5(31‘) —> HG(n,/c) as follows: if 7r E 3(3, k) then let f(7r) = a; where w,- =j ifi E 13,-. We will introduce the notation of Sagan, \Vachs and \Vhite [Sag 91, VV—VV 91], suppose that w E RG(n,1c) and j E k. Then let ij be the position of the leftmost occurence ofj in to. We define then L(w) = {i1,i2, . . . ,ik}. If to corresponds to 71’ by the above bijection f then L(w) is just the set consisting of the smallest element from each block. We also define the inversion vector, lb(w) (lb stands for left bigger) whose j‘h component is given by lbj(LU) = |{i E L(w) : i wJ-H. Again, ifw corresponds to 7r by the bijection f then lbj(U)) = t ifj causes t inversions in 71'. We then use the statistic lb(w) = :lbj(w). j=1 Example 1.2.1 If w=121343241 then f(w):139/27/46/58 as in Erample 1.1.1. Also L(w) : {1,2,4,5} lb(w)=001001203 so that lb(w) = 7 This statistic easily leads to the q-Stirling numbers of the second kind, as shown by Milne [Mil 82]. Theorem 1.2.2 For all n,1r E N 5'[n, 1;] = Z qu’(“’) wERG(n,k) 1’7 .4 Proof. If n = k = 0 then the sum is 1. Otherwise, if n, k > 0 then qlb(w) : Z qlb(w) + Z qlb(w) wERG(n,k) n€L(w) ¢6L(w) : qlb(w’) w’ERG(n—1,k—1) +(1+q + + qk-l) Z qtb(w’) w’eRG(n—1,k) where (1 + q + - - - + qk‘l) comes from the possible values of lbn(w). So by induction qzbm) : 5“, _17k — 1] + [1c]S[TL —11kl wERG(n,k) = S[n, 1;] l The following identity is once again a q-analog of an identity in Comtet [Com 74, 5.3d]. An analagous proof appears in de-Médicis and Leroux [M-L ta, 2.10]. Theorem 1.2.3 For all n, 17 E N S'[n, k] : Zn: S[j_1,k _1][;€]n—j 1:1 Proof. S[n,1c] counts restricted growth functions, to, of length n with maximal element 1;, where wtw = qlwa). Such an to can be associated to a pair (o,‘r). Here a is a restricted growth function of length j — 1 with maximal element 13 — 1 where wt 0‘ 2 gm"), and r = 7172 . . . T,,_J~ is a string of length n —j over the alphabet E where T,- E E has wt T,- = q"_T' and n—j wt T = H wt 7', i=1 Such a are counted by S[j —— 1, k — 1] while the r are counted by [Mn—j. The map is f (10) = (0, T) where j is the first position in which Is appears in w, 0 consists of the first j —— 1 elements of w and r of the last 17. —j elements of a; (note that the 3"" element is not included in either). To see that weights are preserved we note that for i < j we have Since all elements of L(w) are less than or equal to j we see that for i >j lb,-(w) = 1“. — on. Also we have lbj = 0 because wJ- : k and j E L(w). Hence, wtw = wto+ wtr as desired. The inverse map is given by f‘1(o,r) = okr a restricted growth function of length n constructed by concatenation. I 1.3 Vector spaces Milne [Mil 78] has given a vector space interpretation of the S[n, k] as follows. Any sequence of lines (one dimensional subspaces) 11,12,. . .,l,,, in a vector space V over G'Fq, where q is a prime power, determines a flag VOCVICH-CVk obtained by deleting the repeated subspaces in (0)9 (11)§---§(11,12,...,ln) 14 where () denotes linear span. The flag is said to be of dimension 1: if the largest subspace is of dimension 1". Given a fixed flag of dimension k, Milne [Mil 78] showed that the number of sequences of 71 lines which generate this flag is S'[n, k]. The group of upper unitriangular matrices (in a suitable basis) then acts on these sequences of lines. Milne then obtained S[n, k] as the number of orbits. We wish to give a representation of S[n,1c] in terms of these sequences of lines by picking a canonical representative for each orbit. First we must establish some notation. By a common abuse of notation, we will represent a line I by a non- zero point on I. We may assume that the point representing a line is of the form (*, . . . , *, 1,0, . . . ,0) where each * is an element of GE]. Let 61, . . . , 6,, be the standard basis for GFq". Then define VV,’ 2 (61,... ,61'). Let [1, . . . , ln be a sequence of lines generating the flag W0 C W1 C -- - Wk. We say the sequence is standard if for each i with l,- a’ (11,. ..,l.~_1) we have 1,- = fj where (11,...,l;) = W,. Further, we say the sequence has dimension k if the flag generated is of dimension k. Let 11,,(q) denote the set of all standard sequences of n lines and let I = l1, . . . , In E IIn(q). The mapping T defined by T(l) = 7r where 7r is given by iEBjfiliEWj\Wj_1 establishes a surjective correspondence between sequences of lines and partitions. We say that I has type 7r. Because of this map we will say that l,- is in the 3'” part whenever I,- E Wj \ Wj_1. 15 For example, if n = 9,1; = 4 and q = 3 we have (1,0,0,0,0,0.0,0,0) (0,1,0,0,0,0,0,0,0) (1,0,0,0,0,0,0,0,0) (0,0,1.0,0,0,0,0,0) (0,0,0,1,0,0.0,0,0) —» 139/27/46/58 (2,1,1.0,0,0,0,0,0) (2,1,0,0.0,0.0,0,0) (1,0,2.1,0.0,0,0,0) (1,0,0,0,0,0,0,0,0) We claim that the number of standard sequences of n lines of dimension 1c is equal to S[n,1c]. Using induction we note that if n = k = 0 then both the number of sequences and S[0, 0] are 1. For the induction step we delete the nth line. Two possible situations occur: 1. If 1,, is the first line in the 1'“1 part then 1n = 6;, and deleting 1,, leaves a standard sequence of n — 1 lines of dimension 1: — 1. 2. Otherwise there are q"—1 possible lines 1,, such that 1,, is in the ith part. Deleting 1,, here leaves a standard sequence of n — 1 lines of dimension 1:. This gives the recursion for S[n,1c]. Given a line 1 = (a1....,ak_1,1,0,...,0) define the shift left operation, L, as follows. Ll : ((12,...,ak_1,1,0,...,0) so that the 1 now appears in the (1‘ — 1)5t position and there is one extra 0 at the end. Shifting left m, Lml. is just the result of shifting left m times in succession. When we prove an identity using these vector space ideas we really only prove the identity for values of q that are prime powers. The following lemma implies that this is sufficient to prove the identity for all values of q. 16 Lemma 1.3.1 If f(a),g(ar) E Z[.r] are polynomials with f(a) = 9(a) for an infinite number values a then f(x) = g(:r) for all 1'. The following theorem is the same as theorem 1.1.3 but with the proof now given in terms of vector spaces. Theorem 1.3.2 For all n. 1' E N ‘—k+1 n _ 1 - Sln-kl=2q’ . Slate—1] 1'20 3 Proof. S'[n,1c] counts standard sequences of n lines of dimension k. We give a bijection which takes such a sequence to a triple consisting of a list ofj — k + 1 field elements, a subset of the set {2, 3, . . . , n} of size j, and a standard sequence ofj lines of dimension 1: —- 1. So, given a standard sequence 11,12,. . . , 1,, we look first at the subsequence of lines 1,,,1,-,, . . . ,1,] which are not equal to 61 (the first standard basis vector). Clearly A = {i1,i2,...,i,} Q {2,3,...,n} and by definition this set has size j. Let the sequence l’,,l’2,. . . ,1]- be given by l; = Llis. In practice, we have deleted the first coordinate of those lines 1,, gé 61. Now, some of these deleted coordinates may be non-zero. In fact, of thej lines, 1; — 1 are standard basis elements so that the remaining j —- (h — 1) = j — h + 1 lines have meaningful first coordinates. These are saved as our list of field elements. The inverse relationship is easy to see since all lines are reconstructible from the information given except those lines that are 51. Thus all lines that correspond to elements not in the set A should be 51. I 17 Once again we give a vector space proof of a theorem previously stated. The following theorem is the same as theorem 1.1.4 Theorem 1.3.3 For all n. k E N $171.11: likenin- + 1115172 + 1.1 +1 + 11 1:0 where [1c+ 1],- : [k+ 1][k+2]---[1:,+j]. Proof. Ifw = tole . . .w‘, is a string of integers with w,- E {0, 1,. . . , 1: + i — 1} and 1 = 11,12, . . .,l,,+1 is a standard sequence of lines of dimension 1; + j + 1 then define the weight of the pair to be q: “" and the sign of the pair to be (—1)j. We wish to match up pairs with opposite signs so that all pairs cancel except those corresponding to S[n,1c]. In fact, we will match many pairs of one sign with only one pair of the opposite sign so that the sum of all weights comes out to be zero. We have the following possibilities: I. Ifj = 0,1,,+1 = 6k.“ and l,,, 5£ 6H1 form 3 n then to = 0 and 11,12,...,1,, is a standard sequence of lines of dimension 1?. All such pairs have sign +1 so these correspond to S[n, 1‘]. IO . Any pair (w,l) where [n+1 is not the first occurence of 6.1.4.141 (either because l,,+1 yé 61+,“ or 1m : 611,11 for m S n) is matched with the pair (w’,l’) where w’ and l’ are defined as follows. If 1,,“ is in the r‘h part then define to,“ = r—1 and let w’ = wlwg .....'j<.uj+1. Also define 1’ = 11,12,...,1,,,ek+j+2. There are q"1 pairs (to, 1) which will be matched with the same pair (w’, 1’) since [n+1 is in the 1‘” part. But this is exactly the change in weight between to and w’. Clearly the signs are different since the length of w’ is one more than the length of w. Hence all such pairs will cancel. 18 3. Any pair (to, 1) where ln+1 is the first occurence of 6H,“ and j > 0 is matched with pairs from case 2 as explained above. Thus all terms on the right side cancel except those corresponding to S[n, k]. I Finally, we give a vector space proof of theorem 1.2.3, the last of the q-analogs presented in the previous sections. Theorem 1.3.4 For all n,1c E N S[n.1c] = 2 5U — 1, k —1][k]n-J' j=1 Proof. We define a map 0 from standard sequences of lines 1 = 11,12,...,1,, of dimension Is to pairs (1’,w) where l’ = 11,12,...,lj_1 is a standard sequence of lines of dimension 1: — 1 and w = 411122 . . .Ldn_j is a string with w E {0, 1,. . . ,k — 1}. The weight of a string to is defined to be wtw = qu'. The number of sequences 1 mapped to the same pair (l’,w) will equal the weight of to. Define (19(1) : (l’,w) as follows: Let j be the smallest integer such that 1,- : ck. Then 1’ = 11,12, . . . , l,_1. Define also to,- = m — 1 if 1,- is in the mth part. The number of 1 mapping to the same pair (l’,w) equals wtw since for each i, 1,: (*,*,...,*71,0,07...,0) with the 1 in the mth place. Hence there are q’"‘1 different possibilities for 1,- while to,- contributes qm‘1 to the weight of w. I Chapter 2 A q-Partition Lattice Consider a finite poset P with unique minimum0 and maximum 1. Define the Mobius function ,u : P -—-) Z by M0) = 1 and 11(17): — Z p(y). y TU) < T(l’) If 7r is a partition we make a covering partition by combining two parts, say the s“ and t” parts. Hence for sequences of lines we will move the lines from the t” part into the .9“1 part. If 1 = 11.....l,, and l’ = l’,,...,l’ Tl. are standard then 1 -< 1’ if there exists and t, 1 S s < t S n such that: 1. If l,,, is the first line in the t” part then 1],, : (a1,...,as_1,1,0,...,0) where the a,- E GFq are arbitrary. 2. For each 1, in the 1“1 part with i 51$ m, l:- = [it—31,. 3. For each 1, E IV,, i.e. 1, in a part after the t”, then 1: 2 L1,. 4. For all other 1, (1, E IV,_1, i.e. 1, in a part before the t‘h), l: = 1,. For example is covered by where the * could be any element of CF3. (1,0,0,0,0,0 0,0,0) (0,1,0,0,0,0,0,0,0) (1,0,0,0,0,0,0,0,0) (0,0,1,0,0,0,0,0,0) (0,0,0,1,0,0,0,0,0) (2,1,1,0,0,0,0,0,0) (2,1,0,0,0,0 0,0,0) (1,0,2,1.0.0,0,0,0) (1,0.0,0,0,0 0,0,0) (1,0.0,0.0,0,0,0,0 (0,1,0,0,0.0,0,0,0 (1,0,0,0,0.0,0,0,0 (*,1,0,0,0,0,0,0,0 (0,0,1,0,0.0.0,0,0 (1,1.0,0.0.0.0,0.0 (2,1.0.0.0.0.0,0,0 (0,2,1.0,0.0.0.0,0 (1,0,0,0,0.0 0,0,0 VVVVVVVVV __. 139/27/46/58 __. 139/2467/58 We claim that 1 -< 1’ implies T(l) -< T(l’). In particular, if T(1) = 7r 2 Bl/ - - - /B), then T(1’) = 7r’ 2 B[/---/B,"._1 where B]- : B,- forj < t,j # s, B; = B, U B,, and B;- = Bj+1 forj Z t. To see this note first that i E B,- iff the last non-zero element of 1,, Which must be a 1, is in the jth position. In this case we will say the final 1 in 1, is in the jth position. There are three situations: 24 1. The final 1 in If is in the 3“ position iff the final 1 in 1, is in either the :5th or tth position. So B; = B, U B,. 2. The final 1 in 1: is in the jth position, j 2 1, iff the final 1 in 1, is in the j + 13‘ position. So B;- = szl for j Z t. 3. The final 1 in 1:- is in the J“ position, j < t,j # 3, iff the final 1 in 1, is in the jth position. So B3. = B,- for j < t,j 7e 3, This completes the proof. Given any set of integers, S : {(1, < (12 < < (1,} define Si : qaltqal ‘1 (1a?) ---((1“1 + q‘12 + . . . + (101) and S—bz {al—b,a2—b,...,a,_1—b} It should be pointed out that S — b has only 1 — 1 elements and that (S — b)! is a q—analog of (1 — 1)! Note that we can consider (5' — b)! to be a product with a factor corresponding to each element of 5' where the factor corresponding to a,- forj > 1 is (qal—b + (lag—b + . . . + an_1—b) and the factor for a, is 1. Lemma 2.1.1 Let B = {al < a; < < (1,} be a set of positive integers, then (B — (11)! Z Z J), put a, in the same block as (1,. Clearly this gives a partition B = C U D. Also, by definition the factor corresponding to a, in (C — (11)! (or (D — (11)!) contains the term an‘a”. Hence the term in question does appear as a term in some (C -— a1)l(D —- a1)l. Also, each term of (C — (1,)!(D — (11)! has a factor corresponding to each a, since 26 0i E C or a, E D and this factor is gal—“1 for somej < i (ifi = 1,2 this factor is 1). This gives a term in (B — a1)! as desired. I Recall that the Mbbius function is 11(0) = 1 and #13:) = - Z #01) y i. Hence a = min Ci, b E Cj,,j’ >j and so (a, b) E Nina which implies (a,b) E Nina\7r. Conversely, if (a,b) E Nin-r \ a then a1 S a S a2. If a = a1 then b E D’, so (a,b) é Nin7r and thus (a,b) E NinT\7r. lfa1< a < a2 then b E D’. So, b E B and a is in a later block of 7r since a1 < a and B is the first non—trivial block in 7r. Thus (a,b) E Nin7r and so (a,b) E NinT \71’. If a = a; then a 96 min B,- for all i so (a,b) 62 Ninrr and so (a,b) E NinT \ 7r. Further, if (a,b) E Nina \ 7r then b # a2, because if b = a2 and (a, b) E Nina then (a, b) E Nin7r since all parts before C in a are the same as parts before B in 7:. Thus b # a2 and so b is not the minimum of any part in 7'. Also a is still the minimum of some part in T and refinement at worst moves b to the right so (a, b) E Nin 7'. Hence we have (a, b) E Nin‘r \ 7r as desired. I 2.2 The Mbbius Function We now show that the functions 0 defined in the previous section gives the Mobius function for Hn(q). 30 Theorem 2.2.1 [fl = [1,12, . . . ,l,l is a standard sequence of lines of type 7r and ,u is the lilo'bz'us function oan(q) then #(1) = (-1)"‘k¢(7rl Proof. Let 7r = Bl/B-Z/ - - ' /Bk as before. If n — k = 0 then I,- = e, for all i and hence 7r 2 1/2/---./n Thus (-—1)""’°o(7r) = (—1)0 = 1. If n — k > 0 then define f(l) = (—1)"""¢(7r). We wish to show that EN) = o ('31 for then f will satisfy the recurrence for the Mobius function and by uniqueness of the Mobius function we will have f = ,u. we claim first that for any refinement a of 71' there are qninav sequences of lines 1’ = 11,15. .. l’ l’ < l where l’ is of type a. Recall that in? Nina = U Nin, b. b Using the notation of Theorem 2.1.2 and Lemma 2.1.3, that is, a = Cl/Cz/ ~ ~ ~ /Ck/ note that if b E C,,,b 7é min Cu. (these are the only elements which could cause non—inversions in a) then Nina b = {(a, b) [ a = mian,,j’ < 2"}. Since b is not the minimum of a block in a it could not have been the minimum of a block in 7r; so if b E B, then Nin,T b = {(a, b) | a = minBj,j < i}. Also, this forces i S 2" and so we have Nin, b g Nin, b. 31 Since by definition Ninflr b = Nina b\ Nin,r b we have nina\z b = (nino b) — (nin7r b) = (i’—1)—(2'—1) : z"—z'. Further, since 6 E 0;! Q B, and b 7E min Cy we have 15 = Lil—’11,. Hence there are 2" —i positions in If, that are arbitrary. Thus there are q"" possible such lines. Also, a line that corresponds to the minimum of a block must be the appropriate standard basis vector so these lines contribute nothing. This gives a total of gm”)7r sequences of lines 1’ < l of type a as desired. Hence we have Z N) : Z(—1)"""¢(0’) 1'51 ['51 = Zr—nn-k’qmwa) (2.3) where the sum is taken over all a that are (possibly trivial) refinements of 7r. Let B and C be defined as in Theorem 2.1.2. Then for each a which keeps a1 and a2 in the same block Theorem 2.1.2 says that 0(0') : Z ¢(T)qninr\a where the sum is taken over all refinements T of a which split C into two parts with al and a2 separated but keep all other parts the same. Hence by Lemma 2.1.3 we have qnina\x¢(0,) : Z (Inin‘r\aqnina\1r¢(7_) Z qninr\1r¢(7,) II 32 for refinements T of a which split a1 and a2 but keep other blocks the same. Thus every term in (2.3) cancels out since every refinement of 7r (including 7r itself) either has al and a2 in the same block and so cancels with even finer refinements or has al and a2 separated and so cancels as part of some coarser refinement. Hence we have 2 f (1’) = 0 151 as desired so n(l) = (—1)"‘ko’(:). I Since we wish Hn(q) to be a q-analog of the partition lattice 11,, let us examine the Mobius function values and Whitney numbers of both. As noted before, for a partition 7r = 31/82/ - - - /Bk E Hn we have M) = (—1> H(IB-!l—1) (24) 1:1 If I = [112...17, E Hn(q) is of type 7 then by Theorem 2.3 k u #(l) = <—1)"**‘ H q'*“B-(B.- — mi)! (2.5) .=1 It is easy to see that equation (2.5) is a q-analog of equation (2.4). The (signless) Stirling number of the first kind, c(n,k), is the number of per- mutations of 11 that can be written as a product of k disjoint cycles. We then write s(n, k): (~1)" " c(n, k). In the case of ll”, it is well known that w(n, k) = s(n,n—k) and lV(n, k) = S(n, n — I.) (recall that the smallest element of 11,, corresponds to the partition of Q into n parts, hence the n —~ It). The q-Stirling numbers of the first kind were introduced by Gould [Gou 61] and are defined by s[n, k]: )" A c[n, A] where __ c[n—1,/\'—1]+[n—l]c[n—1,k] ifn,k21 C["”'l—{5n,k(—11fn=oork=0 It is clear by construction that in H,,(q) we have lV(n,k) => S[n,n — k] Thus the Whitney numbers of the second kind in H,,(q) are q-analogs of the Whitney numbers 33 of the second kind in H“. We claim that a similar relationship holds for the Whitney numbers of the first kind. Theorem 2.2.2 For n,k E N Z |/t(1)| = elm/fl where the sum is taken over all standard sequences ofn lines with dimension k. Proof. Since there are qan sequences of lines of type 7r we see that ZlMUl Z qnméh) ”65(2Jv) (Ininfiéhl') + Z qnin7r¢(7r) Bk={n} other 7r = Z qnin ”I¢(7r') + Z cfllqninnqninn’¢(7rl) 1r’ES(n_—l.,k—1) 7r’ES(n_-1,k) Where 1r’ is 7r with n deleted and C3: is a polynomial in q. To see what Cr, is we must look at how adding an n to the 2"" block affects (25. It is actually easier to consider the two factors Cwiqnin" together. If B, : {a1 < a2 < - -- < am} is a block of 7r’ then adding an n to that block means we must insert the factor gal—1(1 + gar“l + + gum-1“”) = q‘“‘1 + garl + + (jam-1’1 into qni“"'q5(7r’) in order to get qm“"¢(7r). Here it should be noticed that (11—1 ninnqintn (I =(1 Since we may add n to any block of 77’ (and the other factors will not change) we add all such possible extra factors to get 1 + q + ([2 + + q"_2 : [n — 1]. This can be seen by noting that ifj E B, then (11—1 appears in the extra factor for block i. Hence qj 1 appears for allj E n — 1. Since this extra factor does not depend on 7r’ we have ZIMUM = Z q“i“"o'(7r’)+[‘n-1l Z q“i“"'¢(7r’) n’ES(n—1.k—1) n’ES(n—1,k) 34 #(l’) + Z #(1’) dim(l’)=k-—1 dim(l’)=k c[n— 1,L‘— 1] + [n —1]c[n— 1,k] = c[n, k] by induction so we are done. I Recall that sequences of lines with dimension I: have rank n — Is. Also the sign of the Mobius function (determined by the factor (~1)""°) agrees with that of the q-Stirling numbers of the first kind. Hence Theorem 2.2.2 implies that for Hn(q) we have w(n, k) = s[n, n — 1;]. Thus the Whitney numbers of the first kind for Hn(q) are also q-analogs of those for flu as desired. Chapter 3 q-Cross Products Let P and Q be posets. Then the cross product, P x Q, is the partially ordered set with elements (a, at) where a E P and l‘ E Q. The relations are given by (a, x) S (b, y) iff a S b and x S y. It is well-known that for any two posets #(P X Q) = #(P)#(Q)- (3-1) Also, for the Boolean algebra. B". of all subsets of an n-set, we have azaxmxm am where C1 is the two element chain (which has one edge). The standard q-analog of Bn is the lattice Ln = L,,(q) of subspaces of an n—dimensional vector space over the Galois field GFq. Its Mobius function also factors as ”(Ln) = i—llan) = (—1)(—q)(—q2)---(—q"‘1) even though the lattice is not a cross product. We will now start developing the notion of a q-analog of the cross product. 3 5 36 3.1 General Theory Let P be a ranked poset with rank function rk. Also if to = wlwz . . .wk where the an E G'Fq then we will say that w is a word over GFq of length to and write l(w) = k. A q—cross product P xq C1 is defined as follows. The elements of P Xq 01 are all pairs of the form (aw,:r) where a E P,:r E C1 and w is a word over GFq such that Cl. (120,1) > (a@,1) for all a < b in P C2. (le, 1) > (aa‘,f)) for all words to and a S b in P C3. (b7), 0) > (a...‘,0) where, for each a < b, there is a unique corresponding word w. Note that there are many possible partial orders that will satisfy C3, so we can construct many q-cross products, i.e., P xq C1 is really a family of posets. With this definition in hand we can prove a theorem that is a q-analog of equa- tion (3.1). Theorem 3.1.1 Suppose P is a rankedposet with rk(P) = n. Then any Q E P Xqu satisfies MQ) = qn/’(P)l’(01) = —q”it(P)- Proof. To find ,u(Q) we will induct on 72. If n = 0 the result is clear. If m > 0 then consider any b E P. Let Pb be the lower order ideal of all elements a E P with a S b. If b 74 1 then Q(b.i) E Pb xq Cl. Hence #(UL 1)) = —q‘k‘b)/t(b) 37 by induction. Also, for all b E P, QUWIJ) ’5 Pb by COHStI‘UCtiOH and SO MUN/,0)) = #0?)- There are q’kb such elements so (b 1)) )+ Z; ((,bl/ 0)) — —qub; i(b) +qubu(b)= 0 (3.3) 1W): rkb Thus II | ‘E A t—‘) E O) V 0.. A U3 CO \—/ 3.2 The Subspace Lattice We now show that the subspace lattice can be built up in this way. We need only the definition from the previous section to establish this. Theorem 3.2.1 L,, E L,,_1 xq C1. Proof. In order to show that the subspace lattice is such a q-cross product let us first define some notation. Fixing a basis, all subspaces can be written uniquely as a matrix in row-echelon form with entries from GE]. Hence we will say that the matrix A is a subspace. Further, if A is a subspace, define 38 and W1 A (Aw,0) = A Wk where k = rkA and w = wlwg . . .wk. For the proof that L, E Ln_1 xq C1 induct on n. The case when n = 1 is clear. For n > 1 we must show that the relations in Ln satisfy the conditions C1, C2, and C3 and no others. 1. If A Q B are subspaces in L,,_1 then 0 0 A ; g B 0 0 0 01 0~01 0 0)] . B A , g an, 0 ~0 1 since a row [(1:31 am -~a,,,,_1 an] can be written as the appropriate linear com- bination of the rows of B plus to,- times the appended pivot row. 3. If A Q B are subspaces in Ln_1 and n is a word with ((7)) = rk B = k then there exists a unique to, 1(a)) = rk A 2 cl such that W1 771 wd 71k 39 since each row of A is a unique linear combination of the rows of B and so each w,- is uniquely determined as a linear combination of the 775,8. We must now show that the only relations are those described by C1-C3. Suppose A Q B are subspaces in L,,. Then one of the following holds: 1. 0 0 A: C : and B: D : 0 O 0 1 0-- 0 1 This implies C Q D so this is a C1 relation. A = : and B = D This is impossible since the last row of A is not a linear combination of the rows of B. 3. , ‘ 0 W1 A = C j and B = D “f 0 --0 1 This implies C Q D so this is a C2 relation. 4. <~1 771 A = C and B = D ova 77k 40 This implies C Q D and by uniqueness this is the C3 relation. Hence the relations in Ln are exactly those described by C1-C3 and therefore Ln E 1111.] Xq Cl. I The next step is to define a general q-cross product of posets. To do this we will use the fact that the isotropic subspaces of a vector space ordered by inclusion give a q-analog of the lattice of faces of an octahedron. Also, in a finite abelian group, the subgroup lattice is a q-analog of a product of chains. We hope to use these specific examples to defined the general case. Bibliography [Car 33] [Car 43] [Com 74] [G-R 86] [Gou 61] [M-L ta] [Mil 78] [Mi] 82] [Sag 91] [WV 91] L. Carlitz, On Abelian fields, Trans. Amer. .Math. 500., 35 (1933), 122- 136. L. Carlitz, q-Bernoulli numbers and polynomials, Duke Math J., 15 (1948), 987-1000. L. Comtet, “Advanced Combinatorics”, D. Reidel Publishing Co], Dor- drecht, 1974. A. M. Garsia and .l. B. Remmel, Q-counting rook configurations and a formula of Frobenius. J. Combin. Theory Ser. A, 41 (1986), 246-275. H. W. Gould, The q-Stirling numbers of the first and second kinds, Duke ll/Iath. J., 28 (1961), 281—289. A. de Médicis and P. Leroux, A Unified combinatorial approach for q-(and p,q-)Stirling numbers, J. Statist. Plann. Inference , to appear. S. C. Milne, A q-analog of restricted growth functions, Dobinski’s equality, and Charlier polynomials, Trans. Amer. ll/Iath. Soc., 245 (1978), 89-118. S. C. Milne, Restricted growth functions, rank row matchings of partition lattices, and q-Stirling numbers, Adv. in Math, 43 (1982), 173-196. B. E. Sagan, A maj statistic for partitions, European J. Combin., 12 (1991), 69-79. M. VVachs and D. White, p,q-Stirling numbers and set partition statistics, J. Combin. Theory 561‘. A 56 (1991), 27-46. 41 1 .