18 312 Algebraic Combinatorics Lionel Levine Lecture 14 Lecture date March 31 2011 1 1 1 Notes by Leon Zhou q binomial coefficients Connection to partitions Let al partitions of l the Young diagram of fits in a box of dimensions k n k Theorem 1 k n k X n al q l k q l 0 Proof Fix a flag E0 E1 En of Fnq Given a k subspace V let di dim V Ei and write d d0 d1 dn Now given d let f d k subspaces V Fnq dim V Ei di i 0 n Lemma 2 f d q m1 1 q m2 2 q mk k where mi min j dj i Recall from last time lines 0 L V L 6 H n q n 1 q q n 1 where H is a hyperplane in Fnq We want to count the number of ways to choose a k subspace V Define Vi V Emi where dim Vi i Choosing V is the same as choosing the sequence Vi 0 i k since the intersections of V with our flag define V To choose V1 V Em1 is to choose a line in Em1 that is not contained in Em1 1 As we recalled there are q m1 1 ways to do this To choose V2 V Em2 is to choose a line in Em2 V1 that is not contained in Em2 1 V1 There are q m2 2 ways to do this In general to choose Vj V Emj Vj 1 is to choose a line in Emj Vj 1 that is not contained in Emj 1 Vj 1 and there are q mj j ways to do this 14 1 So n k q is the number of k subspaces of Fnq But this is equal to X f d d where the sum ranges over all sequences d d0 dn with 0 d0 dn k and di 1 di 1 for all i Given a sequence d we form a southwest lattice path where step i is S if di 1 di and W if di 1 di 1 starting at k 0 and ending at 0 k n This draws a Young diagram for a partition we can call then is the number of boxes above the lattice path which is equal to c1 c2 ck where cj is the height of column j Note that ci mi i since all but ci of the steps before column i are westward So k n k X X X n al q l f d q k q d 1 2 in box l 0 The q Binomial Theorem n X n k n k So there s this Binomial Theorem x y x y and we might ask whether we k k 0 can come up with an analagous formula in q binomial coefficients n As it turns out we can Consider the algebra A Q q x y yx qxy the polynomials in three variables q x y over Q in which q commutes with everything but yx qxy Say we try to do some binomial expansion 14 2 x y 3 x y x y x y xxx xxy xyx yxx xyy yxy yyx yyy xxx xxy qxxy qx qxy xyy qxyy q qxy y yyy x3 x2 y qx2 y q 2 x2 y xy 2 qxy 2 q 2 xy 2 y 3 x3 1 q q 2 x2 y 1 q q 2 xy 2 y 3 3 X n xk y n k k q k 0 As it turns out this is true in general see homework 5 1 3 Counting irreducible monic polynomials Question 3 How many irreducible monic polynomials f x a0 a1 x an xn of degree n are there in Fq x Say we make a list f1 x f2 x of all the monic irreducible polynomials in Fq x and let di deg fi x By unique Yfactorization any monic polynomial f x Fq x can be written uniquely as a product fi x ai where all but finitely many ai are 0 i 1 This leads to a bijection between the set of monic polynomials of degree n and the set of sequences a1 a2 such that a1 d1 a2 d2 n In other words partitions of n into piles of size di We can write a generating function for these partitions 1 1 xd1 1 xd2 Then since the number of monic polynomials in Fq x of degree n in just q n our bijection tells us that we have X 1 1 q n xn 1 qx 1 xd1 1 xd2 n 0 14 3 Taking the log of both sides log 1 1 1 log log d d 1 2 1 qx 1 x 1 x X qx n n n 1 We can rewrite the left hand side as X Nd log d 1 1 1 xd where Nd is the number of irreducible monic polynomials of degree d over Fq since there are Nd terms in the left hand sum for which di d And X d 1 Nd log X xdj X X X Nd 1 N xn d d j n d 1 x d 1 j 1 n 1 d n where the second equality is obtained by substituting n for dj Equating coefficients X qx n X X Nd xn n d n n 1 d n n 1 qn 1X dNd n n d n X n q dNd d n Mo bius Inversion n q d d d n 1X n d Nn q n d nNn X d n Hey this expression on the right is equal to the number of rotation classes of primitive necklaces of length n using q colors of beads Example 4 If p is a prime then Np p1 q p q 14 4 2 2 1 Hyperplane Arrangements Definitions Definition 5 Given a vector space V with dim V l a hyperplane arrangement is a finite set of hyperplanes A H1 Hn Hi is an l 1 dimentional subspace of V P A is defined over Z if Hi x V cij xi bi bi cij Z that is if the equations defining the Hi have integer coefficients Note that we implicitly take a basis for V in this definition Definition 6 The intersection poset of A is the set of subspaces L A Hi I n i I ordered by inclusion Note that is not actually a subspace of V so L A may not have a minimal element It does have a maximal element V Definition 7 A is central if every Hi passes through the origin i e if bi 0 in every defining equation T On the other hand if A is central then it does have a minimal element ni 1 Hi which contains 0 and is thus nonempty In this case L A is actually a lattice where Hi Hj Hi Hj 2 2 Connection to finite fields Given a hyperplane arrangement which is defined over Z we can take the …