A COMBINATORIAL APPROACH TO ROOT MULTIPLICITIES OF RANK 2 HYPERBOLIC KAC-MOODY ALGEBRAS 5 SEOK-JINKANG⋆, KYU-HWANLEE⋄, ANDKYUNGYONGLEE† 1 0 2 Abstract. Inthispaperwestudyroot multiplicities of rank2hyperbolicKac-Moody algebras n using thecombinatorics of Dyckpaths. a J 9 ] T R 1. Introduction . h t This paper takes a new approach to the study of root multiplicities for hyperbolic Kac-Moody a m algebras. Even though the root multiplicities are fundamental data in understanding the struc- [ tures of Kac-Moody algebras, we have not seen much progress in this topic for the last twenty 1 v years. The method taken in this paper is totally new, though depending on the previous devel- 6 opments, and opens different perspectives that can bring new results on root multiplicities and 2 0 make advancements, for example, toward Frenkel’s conjecture. To begin with, let us first explain 2 0 the backgrounds of the problem considered in this paper. . 1 After introduced by Kac and Moody more than four decades ago, the Kac-Moody theory has 0 5 become a standard generalization of the classical Lie theory. However, it makes one surprised to 1 : notice that little is known beyond the affine case. Even in the hyperbolic case, our knowledge is v i X very limited in comparison with the affine case. r The first difficulty in the hyperbolic case and other indefinite cases stems from wild behaviors a of root multiplicities. To be precise, let g be a Kac-Moody algebra with Cartan subalgebra h. For a root α, the root space g is given by α g = {x ∈ g |[h,x] = α(h)x for all h ∈ h}. α 2010 Mathematics Subject Classification. Primary 17B67, 17B22; Secondary 05E15. ⋆ This work was supported byNRFGrant # 2014-021261 and by NRFGrant # 2010-0010753. ⋄This work was partially supported by a grant from theSimons Foundation (#318706). †This work was partially supported by NSAgrant H98230-14-1-0323. 1 2 S.-J.KANG,K.-H.LEE,ANDK.LEE Then we have the root space decomposition g = g ⊕ h ⊕ g , α α αM∈∆+ αM∈∆− whichisadecompositionof gintofinitedimensionalsubspaces,where∆+ (resp. ∆ )is thesetof − positive (resp. negative) roots. The dimension of the root space g is called the multiplicity of α. α Obviously, root multiplicities are fundamental data to understand the structure of a Kac-Moody algebra g. However, the status of our knowledge shows a dichotomy according to types of g. Recall that the Weyl group W of g acts on the set ∆ of all roots, preservingroot multiplicities. If α is a real root, α has an expression α = wα for w ∈ W where α is a simple root. It follows i i that dim(g ) = 1. Since all roots in finite dimensional Lie algebras are real, all root spaces α in finite dimensional Lie algebras are 1 dimensional. Let g be an untwisted affine Kac-Moody algebra of rank ℓ+1. Then the multiplicity of every imaginary root of g is ℓ ([9, Corollary 7.4]). There is a similar formula for twisted affine Kac-Moody algebras as well ([9, Corollary 8.3]). For hyperbolic and more general indefinite Kac-Moody algebras, the situation is vastly differ- ent,duetotheexponentialgrowthoftheimaginaryrootspaces. Ourknowledgeofthedimensions of imaginary root spaces is far from being complete, though there are known formulas for root multiplicities. The first formulas for root multiplicities of Kac–Moody algebras are a closed form formula by Berman and Moody ([1]) and a recursive formula by Peterson ([21]). Both formulas are based on the denominator identity for a Kac–Moody algebra g and enable us to calculate the multiplicity of a given root (of a reasonable height). Computations of root multiplicities of hyperbolic Kac–Moody algebras began with the paper by Feingold and Frenkel [5], where the (1) hyperbolic Kac–Moody algebra F of type HA was considered. Using the same method, Kac, 1 (1) Moody and Wakimoto [10] calculated some root multiplicities for HE (= E ). 8 10 These methods were further systematically developed and generalized by the first author [11, 12]forarbitraryKac–Moodyalgebrasandhasbeenadoptedinmanyworksonrootsmultiplicities of indefinite Kac–Moody algebras. In his construction, the first author adopted homological techniques and Kostant’s formula ([8]) to devise a method that works for higher levels. For (1) example, he applied his method to compute roots multiplicities of the algebra F of type HA 1 up to level 5 ([13, 14]). Despite all these results, we still do not have any unified, efficient approach to computing all root multiplicities. Essentially these methods give answers to root multiplicities one at a time, ROOT MULTIPLICITIES OF RANK 2 HYPERBOLIC KAC-MOODY ALGEBRAS 3 with no general formulas or effective bounds on multiplicities. In particular, these formulas are given by certain alternating sums of rational numbers and make it difficult to control overall behavior of root multiplicities. Therefore it is already quite hard to find effective upper or lower bounds for root multiplicities for hyperbolic and other indefinite Kac-Moody algebras. For hyperbolic Kac–Moody algebras, in the setting of the ‘no-ghost’ theorem from String theory, I. Frenkel [7] proposed a bound on the root multiplicities of hyperbolic Kac–Moody algebras. Frenkel’s conjecture: Let g be a symmetric hyperbolic Kac–Moody algebra associated to a hyperbolic lattice of dimension d and equipped with invariant form (· | ·) such that (α |α ) = 2 for i i simple roots α . Then we have: i (α|α) dim(g ) ≤ p(d 2) 1− , α − 2 (cid:18) (cid:19) where the function p(ℓ)(n) is the multi-partition function with ℓ colors. Frenkel’s conjecture is known to be true for any symmetric Kac-Moody algebra associated to a hyperbolic lattice of dimension 26 [7], though Kac, Moody and Wakimoto [10] showed that the conjecture fails for E . The conjecture is still open for the rank 3 hyperbolic Kac–Moody 10 algebra F and proposes arguably the most tantalizing question about root multiplicities. Open Problem: Prove Frenkel’s conjecture for the rank 3 hyperbolic Kac-Moody algebra F. As mentioned earlier, Feingold and Frenkel [5] and the first author [13, 14] studied root mul- tiplicities of F. There is another approach to root multiplicities of F and other hyperbolic Kac- Moody algebras, taken by Niemann [20], which follows Borcherds’idea inconstruction of thefake Monster Lie algebra [2]. This approach was further pursued by Kim and the second author [16]. A recent survey on root multiplicities can be found in [3]. In this paper, we adopt quite a different methodology and investigate root multiplicities of ranktwo symmetrichyperbolicKac-Moodyalgebras H(a)(a ≥ 3)throughcombinatorial objects. More precisely, we use lattice paths, known as Dyck paths, to describe root multiplicities. Suppose that α = rα +sα is an imaginary root of H(a) with r and s relatively prime, for 1 2 simplicity. Then our first main theorem (Theorem 3.7) shows that Theorem 1.1. We have mult(α) = c(D). D:Dyckpath X wt(D)=α 4 S.-J.KANG,K.-H.LEE,ANDK.LEE Here c(D) has values 1, 0 or −1 and is immediately determined by the shape of the Dyck path D. Theresultforgeneralαinvolvesconsideringcyclicequivalenceofpathsandaminorcorrection termcomingfrompathswithweightα/2. Animportantfeatureisthatthisformulaonlycontains integers and has clear combinatorial interpretation, and makes it possible to prove properties of root multiplicities through combinatorial manipulations of Dyck paths. For example, in the symmetricranktwocase, wecanproveananalogueofFrenkel’s conjecturethroughcombinatorics of Dyck paths. Proposition 1.2. Let g = H(a). Then we have: (α|α) mult(α) ≤ p 1− , t 2 (cid:18) (cid:19) where α = rα +sα , t = max(r,s) and p (n) is the number of partitions of n with at most t 1 2 t parts. Even though this upperboundis in the form of Frenkel’s conjecture, it is actually crude. More interestingly, Theorem 1.1 gives a natural upper bound by only counting paths with c(D) = 1. This upper bound can be significantly improved by considering cancellation with paths having c(D) = −1. Namely, we consider a function Φ from {D : c(D) = −1} to {D : c(D) = 1}. Suppose that α = rα + sα is an imaginary root of H(a) with r and s relatively prime, for 1 2 simplicity. Then we obtain Theorem 1.3. mult(α) ≤ #{D : Dyck path, wt(D) = α, c(D) = 1, D is not an image under Φ}. Thisupperboundisquitesharpandgivesexactrootmultiplicitiesforrootsuptoheight16with a suitable choice of Φ. In Section 5, the function Φ will be carefully constructed. The resulting upperboundis satisfactorily accurate and enlightens combinatorics of Dyck paths related to root multiplicities. OurapproachclearlyextendstohigherrankKac-MoodyalgebrasbyreplacingDyckpathswith certain lattice paths. In a subsequent paper, we will consider higher rank cases; in particular, we will study the Feingold-Frenkel rank 3 algebra F. We hope that our approach may bring significant advancements toward Frenkel’s conjecture for the algebra F. ROOT MULTIPLICITIES OF RANK 2 HYPERBOLIC KAC-MOODY ALGEBRAS 5 2. Rank Two Symmetric Hyperbolic Kac-Moody Algebras In this section, we fix our notations for rank 2 hyperbolic Kac-Moody algebras. A general theory of Kac-Moody algebras can be found in [9], and the root systems of rank two hyper- bolic Kac-Moody algebras were studied by Lepowsky and Moody [17] and Feingold [4]. Root multiplicities of these algebras were investigated by Kang and Melville [15]. 2 −a Let A = be a generalized Cartan matrix with a ≥ 3, and H(a) be the hyperbolic −a 2 ! Kac-Moody algebra associated with the matrix A. In this section, we write g = H(a) if there is no need to specify a. Let {h ,h } be the set of simple coroots in the Cartan subalgebra 1 2 h = Ch ⊕Ch ⊂ g. Let {α ,α } ⊂ h be the set of simple roots, and Q = Zα ⊕Zα be the 1 2 1 2 ∗ 1 2 root lattice. The set of roots of g will be denoted by ∆, and the set of positive (resp. negative) roots by ∆+ (resp. by ∆ ), and the set of real (resp. imaginary) roots by ∆ (resp. by ∆ ). − re im We will use the notation ∆+ to denote the set of positive real roots. Similarly, we use ∆+ , ∆ re im −re and ∆ . The Lie algebra g has the root space decomposition g = h⊕ g and we define −im α ∆ α ∈ the multiplicity of α by multα := dimg . α L We define a symmetric bilinear form on h by (α |α ) = a , where a is the (i,j)-entry of the ∗ i j ij ij Cartan matrix A. The simple reflection corresponding to α in the root system of g is denote i by r (i = 1,2), and the Weyl group W is given by W = {(r r )i,r (r r )i|i ∈ Z}. Define a i 1 2 2 1 2 sequence {B } by n B = 0, B = 1, B = aB −B for n ≥ 0. 0 1 n+2 n+1 n It can be shown that 1−γ2n B = (n ≥ 0), n γn 1(1−γ2) − where γ = a+√a2 4. We will write (A,B) = Aα +Bα . Then the set of real roots are given by 2 − 1 2 ∆+ = {(B ,B ), (B ,B ) | n ≥ 0}. re n n+1 n+1 n See [15] for details. To describe the set of imaginary roots, we first define the set 4k k am− (a2−4)m2−4k Ω = (m,n) ∈Z ×Z : ≤ m ≤ , n = k ( ≥0 ≥0 ra2−4 ra−2 p 2 ) for k ≥ 1. 6 S.-J.KANG,K.-H.LEE,ANDK.LEE Proposition 2.1. [15] For a ≥ 3, the set of positive imaginary roots α of H(a) with (α|α) = −2k is (m,n), (mB −nB ,mB −nB ), ∆+ = j+1 j j+2 j+1 (m,n) ∈ Ω or (n,m) ∈ Ω , j ≥ 0 . im,k k k ( (mBj+2−nBj+1,mBj+1−nBj) ) (cid:12) (cid:12) The denominator identity is given by (cid:12) (1−e α)multα = (−1)ℓ(w)ewρ ρ, − − α ∆+ w W Y∈ X∈ where ℓ(w) is the length of w and ρ= (α +α )/(2−a). 1 2 3. Contribution multiplicity In this section, we fix a hyperbolic Kac-Moody algebra H(a), a ≥ 3. First, we recall Kang and Melville’s result [15] on root multiplicities of H(a). For r,s ∈ Z , write α = rα +sα . As in 0 1 2 ≥ [15], we define a sequence {A } as follows: n n 0 ≥ A = 0, A = 1, 0 1 A = aA −A +1 for n ≥ 0. n+2 n+1 n Let C = {c = (c0,c1,c0,c1,...) | cj are non-negative integers,j ∈{0,1},i ≥ 0}, 0 0 1 1 i and let (3.1) C(α) = {c ∈ C | (c0A +c1A )= r, (c0A +c1A )= s}. i i+1 i i i i i i+1 i 0 i 0 X≥ X≥ We write τ|α if α= dτ for some d∈ Z , and set α/τ = d. >0 Proposition 3.2. [15, Proposition 2.1, 2.2] We have α τ ( (c0+c1)−1)! (3.3) mult(α) = µ (−1)Pi:odd(c0i+c1i) i≥0 i i . τ α c0!c1! Xτ|α (cid:16) (cid:17) c∈XC(τ) P i≥0 i i Q For r,s ∈ Z , define a Dyck path of size r×s to be a lattice path from (0,0) to (r,s) that 0 ≥ never goes above the main diagonal joining (0,0) and (r,s). We identify a Dyck path with aword in alphabet {1,2}, where 1 represents a horizontal move and 2 a vertical move. Then a Dyck path has 12-corners and 21-corners. We consider the end points (0,0) and (r,s) as 21-corners. We define the weight of a Dyck path D of size r×s to be wt(D) := rα +sα ∈Q. 1 2 ROOT MULTIPLICITIES OF RANK 2 HYPERBOLIC KAC-MOODY ALGEBRAS 7 We say that two Dyck paths D and D are equivalent if D is a cyclic permutation of D 1 2 1 2 (as words in the alphabet {1,2}). Then we obtain equivalent classes of Dyck paths. When no confusion arises, we will frequently identify an equivalent class D with any representative D ∈ D. For an equivalence class D, the weight wt(D) is well-defined. The concatenation of Dyck paths D ,D ,...,D will be denoted by D D ···D . For a positive integer d and a Dyck path D, the 1 2 r 1 2 r concatenation Dd is defined in an obvious way. We distinguish a concatenation from its resulting path. The resulting path of a concatenation D D ···D will be denoted by π(D D ···D ). A 1 2 r 1 2 r Dyck path D is said to be essential if D 6= π(Dd) for any subpath D and d ≥ 2. Likewise, an 0 0 equivalence class D is said to be essential if any element D of D is essential. Definition 3.4. For any positive integers u,v, denote by L the Dyck path of size u×v, which u v × consists of u horizontal edges followed by v vertical edges, and call it an elementary path. We say that the elementary Dyck path L is of u v × type (−1), if A ≤ min(u,v), max(u,v) < A , and n: even > 0; n n+1  type (1), if A ≤ min(u,v), max(u,v) < A , and n: odd; n n+1    type (0), if A ≤ min(u,v) < A ≤ max(u,v), and n > 0. n n+1 For a given Dyck path D, defineS(D) to betheset of all concatenations of copies of L  Ai+1×Ai and copies of L in some order that realize D. For a concatenation s in S(D), the number Ai×Ai+1 of copies of L is denoted by c0(s) and the number of copies of L by c1(s). We Ai+1×Ai i Ai×Ai+1 i define seq(s) = (c0i(s),c1i(s))i 0 ∈ C and sgn(s) = (−1)Pi:odd(c0i(s)+c1i(s)). ≥ If D is an equivalence class, we observe that S(D ) is in one-to-one correspondence with S(D ) 1 2 through cyclic permutation for D ,D ∈ D. For an equivalence class D, we define the set S(D) 1 2 to be equal to S(D) for a fixed Dyck path D ∈ D. Now the contribution multiplicity c(D) of D is defined by c(D) = sgn(s). s S( ) ∈XD For a Dyck path D, a subpath D of D is called framed if the starting point and the ending 0 point of D are both 21-corners. 0 Lemma 3.5. For any Dyck path D, we have 0, if D contains a framed subpath of type (0); c(D) =  (−1)# of framed subpaths of D of type ( 1), otherwise.  −  8 S.-J.KANG,K.-H.LEE,ANDK.LEE Proof. Assume that D = π(D D ). Then we have 1 2 c(D) = sgn(s) = sgn(s ) sgn(s ) 1 2 s∈XS(D) (s1,s2)∈SX(D1)×S(D2) = sgn(s ) sgn(s )= c(D )c(D ). 1 2 1 2 s1∈XS(D1) s2∈XS(D2) Thus it is enough to consider the case when D is an elementary path. In this case, we need to prove that c(D) is equal to its type. We will use induction. Clearly, c(L ) = c(L ) = 1, and 1 0 0 1 × × the assertion of the lemma is true. Suppose that the assertion is true for L . We will prove u v × the case L . The other case L is obtained from the symmetry. (u+1) v u (v+1) × × Write L = L and L = L to ease the notations. Assume that c(L) is equal to its u v 1 (u+1) v × × type. If L and L is of the same type, then we get all the elements of S(L ) from those of S(L) 1 1 by adding 1 to c0(s), s ∈ S(L), and c(L ) = c(L). 0 1 IfLisoftype(1)andL isoftype(0), thenthepathL newlycontains L asasubpath 1 1 An+1 An × for n odd, where A = u+1. Consequently, c(L ) = c(L)−1= 0 by induction. If L is of type n+1 1 (−1) and L is of type (0), then the path L newly contains L as a subpath for n even, 1 1 An+1 An × where A = u+1. Thus, again, we have c(L ) = c(L)+1 = 0. n+1 1 Similarly, if L is of type (0) and L is of type (−1) (respectively, if L is of type (0) and L is 1 1 of type (1)), then L newly contains L as a subpath for n odd (respectively, for n even), 1 An+1 An × where A = u+1. Thus we have c(L ) = c(L)−1 = −1 (respectively, c(L ) = c(L)+1 = 1). n+1 1 1 Now, by induction, we are done. (cid:3) Remark 3.6. The above lemma enables us to compute c(D) efficiently and combinatorially. In particular, c(D) = 1 if D contains no framed subpaths of type (0) and an even number of framed subpaths of type (−1). The following theorem is a combinatorial realization of Kang and Melville’s formula (3.3), which says that the root multiplicity of α is equal to the sum of contribution multiplicities c(D) of essential equivalence classes D of weight α plus some correction term. Theorem 3.7. For α ∈∆+, we have 1 c( ) mult(α) = c(D)+ − D . 2 Dw:te(Xsse)n=tiαal wDt:(eXss)e=nαti/a2lj k D D ByLemma3.5,weseethatthesecondsum(i.e., thecorrectionterm)isnothingbutthenumber of essential D such that wt(D)= α/2 and c(D) = −1. ROOT MULTIPLICITIES OF RANK 2 HYPERBOLIC KAC-MOODY ALGEBRAS 9 Proof. Write α = rα +sα . Before we deal with the general case, we first consider a simpler 1 2 case and assume that r and s are relatively prime. Then the correction term is 0, and each equivalence class of weight α has only one essential Dyck path. Recall that we defined C(α) in (3.1). We claim that, for each c = (c0,c1) ∈ C(α), the number of concatenations s such that i i i 0 ( (c0+c1)−1)! ≥ seq(s) = c is i≥0 i c0!ci1! . Indeed, let p be a concatenation of the c0i copies of LAi+1×Ai P i 0 i i and c1 copies of L ≥ in some order, and consider the concatenation pN for N sufficiently i QAi×Ai+1 large. Then we can find a unique line with slope s/r which intersects the path π(pN) so that the path never goes above the line. Since r and s are relatively prime, two consecutive intersection points uniquely determine a concatenation which is a cyclic permutation of p, and the number of cyclic permutations is (c0+c1). Now the claim follows. i 0 i i ≥ From Proposition 3.2 and the claim above, we obtain P c(D) = (−1)Pi:odd(c0i(s)+c1i(s)) :essential :wt( )=α s S( ) Dwt(X)=α D XD ∈XD D ( (c0+c1)−1)! = (−1)Pi:odd(c0i+c1i) i≥0 i i = mult(α). c0!c1! c∈XC(α) P i≥0 i i Q Now we consider arbitrary r,s ∈ Z . We will show 0 ≥ (3.8) ( (c0+c1)−1)! τ (−1)Pi:odd(c0i+c1i) i≥0 i i =  c(D)+ 1−c(D) . c0!c1! α 2 c∈XC(α) P i≥0 i i Xτ|α Dw:teX(sse)n=tiτal wDt:(eXss)e=nτti/a2lj k Q  D D    Let c ∈ C(α). As before, assume that p is a concatenation of the c0 copies of L and i Ai+1×Ai c1 copies of L in some order, and consider the concatenation pN for N sufficiently large. i Ai×Ai+1 Then we can find a unique line with slope s/r which intersects the path π(pN) so that the path never goes above the line. Then we obtain an equivalence class of concatenations of size r×s. We choose a concatenation from the equivalence class and denote it again by p. If p = pd for some concatenation p of weight τ such that α/τ = d and d is maximal, then the 0 0 number of cyclic permutations of p is (c0+c1)/d. Define the contribution of the equivalence i 0 i i ≥ class of p to be (−1)Pi:odd(c0i+c1i)/d. TPhen the total sum of contributions of equivalence classes of concatenations p such that seq(p) = c is given by (−1)Pi:odd(c0i+c1i)(Pi≥0(c0i+c1i)−1)!. One can see Qi≥0c0i!c1i! this by observing that (Pi≥0c0i+c1i)! counts the numberof concatenations andthat (Pi≥0(c0i+c1i)−1)! Qi≥0c0i!c1i! Qi≥0c0i!c1i! 10 S.-J.KANG,K.-H.LEE,ANDK.LEE is the weighted number of cyclic equivalence classes of concatenations when we assign a weight 1/d to an equivalence class of (c0+c1)/d members. i 0 i i ≥ We group the equivalence classes of concatenations p according to the resulting equivalence P classes D of Dyck paths so that π(p) ∈D, and define T to be the total sum of contributions of D the equivalence classes of p such that π(p) ∈ D. Then we have ( (c0+c1)−1)! (3.9) (−1)Pi:odd(c0i+c1i) i≥0 i i = T . c0!c1! D c∈XC(α) P i≥0 i i D:wXt(D)=α Q We consider an equivalence class D of Dyck paths of weight α and choose a representative D. Let D be an essential subpath of D such that D = π(Dd), and let S(D ) = {s ,...,s }. If p 0 0 0 1 k is a concatenation such that π(p) = D then p is equal to a concatenation of d choices of s from i S(D ) with repetition allowed. Thus the total sum T of contributions is equal to 0 D T = 1(sgn(s )+···+sgn(s ))d = 1c(D )d. d 1 k d 0 D By Lemma 3.5, we know that c(D ) = −1,0 or 1. Unless c(D ) = −1 and d is even, we have 0 0 T = 1c(D ). If c(D ) = −1 and d is even, then we have T = 1 = 1c(D )+ 2. d 0 0 d d 0 d D D Now we obtain τ 2τ T = c(D )+ δ D α 0 α c(D0)+1,0 D:wXt(D)=α Xτ|α Dw0t:(eXss0e)n=tiτal 2Xτ|α Dw0t:(eXss0e)n=tiτal D D τ 1 c( ) =  c(D)+ − D , α 2 Xτ|α Dw:teX(sse)n=tiτal wDt:(eXss)e=nτti/a2lj k  D D    where δ is the Kronecker delta. Combined with (3.9), this establishes the desired identity (3.8). Finally, let β = r α +s α be such that r and s are relatively prime and β|α. Multiplying 0 1 0 2 0 0 both sides of (3.8) by α/β, we obtain (3.10) α ( (c0 +c1)−1)! τ (−1)Pi:odd(c0i+c1i) i≥0 i i =  c(D)+ 1−c(D) . β c0!c1! β 2 c∈XC(α) P i≥0 i i Xτ|α Dw:teX(sse)n=tiτal wDt:(eXss)e=nτti/a2lj k Q  D D    It follows from the M¨obius inversion and Proposition 3.2 that 1 c( ) mult(α) = c(D)+ − D . 2 Dw:te(Xsse)n=tiαal wDt:(eXss)e=nαti/a2lj k D D