# Some Recurrence Relations and Hilbert Series of Right-Angled Affine Artin MonoidM(D~n∞)

Authors: Young Chel Kuwn; Zaffar Iqbal; Abdul Rauf Nizami; Mobeen Munir; Sana Riaz; Shin Min Kang
Journal: Journal of Function Spaces
 (2018)

---

## Abstract

We find the Hilbert series of the right-angled affine Artin monoidM(D~n∞). We also discuss its recurrence relation and the growth rate.


---

## Body

## 1. Introduction

Coxeter groups were introduced by Coxeter in 1934 as abstract form of reflection groups. These groups were classified into two categories in 1935 also by Coxeter: spherical and affine. In the list of spherical Coxeter groups,An is the first. The Artin group associated with An is the braid group. Cardinality is an invariant of graded algebraic structures. Hilbert series deals with the cardinality of elements in the graded algebraic structures. In [1] Iqbal gave a linear system for the reducible and irreducible words of the braid monoid MBn, which leads to compute the Hilbert series of MBn. In [2] Iqbal and Yousaf computed the Hilbert series of the braid monoid MB4 in band generators. In [3] Berceanu and Iqbal proved that the growth rate of all the spherical Artin monoids is less than 4. In [4] Iqbal et al. studied the braid monoid M(A~n∞) of the affine type A~n of the Coxeter systems. Authors also found the recurrence relations, the growth series of M(A~n∞), and proved that the growth rate of M(A~n∞) is unbounded (see Figure 1).Figure 1In the present paper we study the affine-type Coxeter groupD~n and find the Hilbert series (or spherical growth series) of the associated right-angled affine Artin monoid M(D~n∞). We also discuss its recurrence relations and the growth rate. For detailed explanation of related concepts and basic ideas about Coxeter groups and its types, readers are referred to [4] and references therein.The affine (or infinite) Coxeter groups form another important series of Coxeter groups. These well-known affine Coxeter groups areA~n, B~n, C~n, D~n, E~6, E~7, E~8, G~2, and I~1 (for details, see [5]). In [3] authors proved that the universal upper bound for all the spherical Artin monoids is less than 4.In this work we discuss right-angled affine Artin monoids; specifically, we study the affine monoidM(D~n∞) and compute its Hilbert series. We show that the growth of M(D~n∞) series is bounded above by 4. Along with Hilbert series we also compute the recurrence relations related to M(D~n∞). We give a conjecture about the growth rate of M(D~n∞), and the growth rates (maximal roots of the characteristic polynomial Dn(λ)) are computed using the softwares Drive6 and Mathematica.The monoidM(D~n∞) is represented by its Coxeter graph as shown in Figure 2.Figure 2Herex1,x2,…,xn are vertices of the graph and all the labels are ∞. If all the labels in a Coxeter diagram are replaced by ∞, then there is no relation between the adjacent edges. Hence we have the associated right-angled Artin groups and the associated right-angled Artin monoids denoted by G(D~n∞) and M(D~n∞), respectively.In a monoid the relationα=β will be written as α>β in the length-lexicographic order. Let α1=uw and α2=wv; then the word of the form uwv is said to be anambiguity. If α1v=uα2 is in the length-lexicographic order, then we say that the ambiguity uwv is solvable. Such a presentation iscomplete if and only if all the ambiguities are solvable. Corresponding to the relation α=β, the changes γαδ→γβδ give a rewriting system. A complete presentation is equivalent to a confluent rewriting system. In a complete presentation of a monoid, word containing α will be calledreducible word and a word that does not contain α will be called anirreducible word orcanonical word. In a presentation of a monoid we fix a total order x1<x2<⋯<xn on the generators. Hence clearly we have the following.Lemma 1.
The monoidM(D~n∞) has the following presentation:(1)MD~n∞=x1,x2,…,xn∣x2x1=x1x2,xjxi=xixj,3≤i+2≤j≤n-1,j≠3xnxk=xkxn,k≠n-2.


## 2. Recurrence Relations of the MonoidM(D~n∞)

In this section we discuss few interesting results relating to the recurrence relations ofM(D~n∞). First we talk about the solution of the system of linear recurrences.Consider a system [6] of linear recurrences(2)u1t+1=a11tu1t+⋯+a1ntunt+f1tu2t+1=a11tu1t+⋯+a1ntunt+f2t⋮unt+1=a11tu1t+⋯+a1ntunt+fnt.This system can be written as u(t+1)=A(t)u(t)+f(t), where(3)ut=u1t⋮unt,At=a11t⋯a1nt⋮⋱⋮an1t⋯annt,ft=f1t⋮fnt.The solution (which we need in our work) of the homogenous equationu(t+1)=A(t)u(t) is given by u(t)=c1λ1tu1+⋯+ckλktuk, where λ1,…,λk are the eigenvalues of A(t) and ui is an eigenvector corresponding to λi. The largest eigenvalue is the growth rate of the sequence (ui(t)) (by the definition of growth rate).Letck=#{canonical words of length k} and ck;i=#{canonical words starting with xi of length k}. Then we have the following.Lemma 2.
The monoidM(D~n∞) satisfies the following recurrence relations:
(a)c0=1, c1;i=1, and ck=∑i=1nck;i,(k≥1).
(b)ck;i(k≥1) are given by the recurrence(4)ck;i=∑j=inck-1;j,i=1,2,ck;1,i=3,∑j=i-1nck-1;j,i=4,5,…,n-1,ck-1;n-2+ck-1;n,i=n.LetKn be a Coxeter diagram (Kn is similar to the standard Coxeter diagram Dn but opposite in direction) (see Figure 3).Figure 3We useM(Kn∞) in the solution of the recurrence of M(D~n∞). Therefore we have the following.Lemma 3.
The monoidM(Kn∞) satisfies the recurrence relations
(a)c0=1, c1;i=1, and ck=∑i=1nck;i,(k≥1).
(b)ck;i(k≥1) are given by the recurrence(5)ck;i=∑j=inck-1;j,i=1,2,ck;1,i=3,∑j=i-1nck-1;j,i=4,5,…,nLetKn(λ) and Dn(λ) denote the characteristic polynomials of the system of recurrence relations of the monoids M(Kn∞) and M(D~n∞), respectively. Then we have the following.Lemma 4.
The polynomials(Kn(λ))n≥3 satisfy the recurrence relation(6)Knλ=λKn-1λ-λKn-2λ,n≥3with the initial values K3(λ)=λ3-3λ2+λ and K4(λ)=λ4-4λ3+3λ2-λ.Proof.
LetPn be the matrix of order n×n of the recurrences given in the Lemma 3. Then the characteristic polynomial Kn(λ) of Pn is(7)Knλ=λ-1-1⋯-1-1-1-10λ-1⋯-1-1-1-1-1-1⋯-1-1-1-1⋮⋮⋮⋮⋮⋮00⋯0-1λ-1-100⋯00-1λ-1.We write Kn(λ)=Sn(λ)+Tn(λ), where the determinants Sn(λ) and Tn(λ) are obtained by splitting Kn(λ) such that the last rows of Sn(λ) and Tn(λ) are (0,…,0,λ) and (0,…,0,-1,-1), respectively. Therefore easily we have Sn(λ)=λKn-1(λ) and(8)Tnλ=λ-1-1⋯-1-1-1-10λ-1⋯-1-1-1-1-1-1⋯-1-1-1-1⋮⋮⋮⋮⋮⋮00⋯0-1λ-1-100⋯00-1-1.Subtracting last column from 2nd last column of Tn(λ) and after few easy computations we have the recurrence relation Kn(λ)=λKn-1(λ)-λKn-2(λ),n≥3.Here we have an explicit formula to computeKn(λ).Lemma 5.
Letq=λ2-4λ; then we have the following:
(‍1)  K2m(λ)=(1/22m)∑k=02m2mkt2m-kq2k(a+b),
(‍2)  K2m+1(λ)=(1/22m+1)∑k=02m+12m+1kt2m-k+1q2k+1(a-b), where(9)a=4tqt3-3t+1+t3-5t2+5t-2qt+q3,b=4tqt3-3t+1-t3-5t2+5t-2qt-q3.Proof.
LetKn(λ)=αn. Then Kn(λ)=λKn-1(λ)-λKn-2(λ) can be written as αn=λαn-1-λαn-2; i.e., α2-λα+λ=0. This characteristic equation has the roots α=(λ±λ2-4λ)/2. Let α1=(λ+λ2-4λ)/2 and α2=(λ-λ2-4λ)/2. Then we have the solution of the recurrence given by Kn(λ)=aα1n+bα2n, where a and b are constants to determine. Since K3(λ)=λ3-3λ2+λ and K4(λ)=λ4-4λ3+3λ2-λ, therefore(10)λ3-3λ2+λ=α13a+α23b,λ4-4λ3+3λ2-λ=α14a+α24b.Solving these equations we get a=(4t/q(t+q)3)(q(t3-3t+1)+(t3-5t2+5t-2)) and b=(4t/q(t-q)3)(q(t3-3t+1)-(t3-5t2+5t-2)). Hence(11)Knλ=at+qn+bt-qn2n=a2n∑k=0nnktn-kqk+b2n∑k=0nnktn-k-qk.For even and odd values of n we have(12)K2mλ=122m∑k=02m2mkt2m-kq2ka+b,K2m+1λ=122m+1∑k=02m+12m+1kt2m-k+1q2k+1a-b.Theorem 6.
The polynomials(Dn(λ))n≥5 satisfy the recurrence relation(13)Dnλ=λ-1Kn-1λ-λ2Kn-4λ,n≥5with D0(λ)=1, D1(λ)=λ-1, D2(λ)=(λ-1)2, D3(λ)=λ(λ2-3λ+1), and D4(λ)=λ2(λ2-4λ+3) being the initial values.Proof.
LetMn be the matrix of order n×n of the recurrences given in Lemma 2. Then the characteristic polynomial of Mn is(14)Dnλ=λ-1-1⋯-1-1-1-10λ-1⋯-1-1-1-1-1-1⋯-1-1-1-1⋮⋮⋮⋮⋮⋮00⋯-1λ-1-1-100⋯0-1λ-1-100⋯0-10λ-1.Write Dn(λ)=Un(λ)+Vn(λ), where the determinants Un(λ) and Vn(λ) are obtained by splitting Dn(λ) such that the last row of Un(λ) is (0,…,0,λ-1) and the last row of Vn(λ) is (0,…,0,-1,0,0). Hence easily we have Un(λ)=(λ-1)Kn-1(λ). Subtracting last column from 3rd last and 2nd last columns of Vn(λ), respectively, we have Vn(λ)=-λ2Kn-4(λ). Hence(15)Dnλ=λ-1Kn-1λ-λ2Kn-4λ,n≥5.


## 3. The Hilbert Series of the MonoidM(D~n∞)

Now we compute the Hilbert series ofM(D~n∞). For this we need to fix some notations first. Let HM(n)(t)=∑k≥0cktk denote the Hilbert series of M(D~n∞), where ck=#{canonical words of length k}, and HM;i(n)(t)=∑k≥0ck;i(n)tk denote the Hilbert series of M(D~n∞) of words starting with xi, where ck;i=#{canonical words starting with xi of length k}.Theorem 7.
The Hilbert series ofM(D~n∞) is given by the following:
(1) HM(n)(t)=1+∑i=1nHM;in(t),
(2) HM;i(n)(t)=t+t∑j=inHM;j(n)(t),i=1,2,
(3) HM;1(n)(t)=HM;3(n)(t),
(4) HM;i(n)(t)=t+t∑j=i-1nHM;j(n)(t),i=4,5,…,n-1,
(5) HM;n(n)(t)=t+tHM;n-2(n)(t)+tHM;n(n)(t).Proof.
( 1 ) From Lemma 2 we have ck=∑i=1nck;i,(k≥1). Therefore(16)HMnt=∑k≥0cktk=c0+∑k≥1cktk=1+∑k≥1∑i=1nck;itk=1+∑i=1n∑k≥1ck;itk=1+∑i=1nHM;int.
( 2 ) From Lemma 2 we have ck;i=∑j=inck-1;j(i=1,2). Hence(17)HM;int=∑k≥1nck;ittk=c1;itt+∑k≥2nck;ittk=t+∑k≥2n∑j=inck-1;jttk=t+t∑j=in∑k≥2nck-1;jttk-1=t+t∑j=inHM;int.Similarly we can easily prove (3), (4), and (5).The system of equations in Theorem7 can be written in matrix form as WnX=B, where(18)Wn=1-t-t⋯-t-t-t-t01-t⋯-t-t-t-t-t-t⋯-t-t-t-t⋮⋮⋮⋮⋮⋮00⋯-t1-t-t-t00⋯0-t1-t-t00⋯0-t01-t,X=HM;1ntHM;2ntHM;3nt⋮HM;nnt,B=ttt⋮t.Lemma 8.
In the monoidM(D~n∞)(19)detWn=tnDn1t.Proof.
The result follows immediately by factoring outt from each row of det(Wn).Lemma 9.
InM(D~n∞)(20)HM;mnt=tm-1Km-21/ttnDn1/t,5≤m≤n-11-ttm-2Km-31/ttnDn1/t,m=n.Proof.
The system given in Theorem7 of n equations in n variables HM;i(n)(t),1≤i≤n is already written in the form WnX=B, where X=[HM;1(n)(t),…,HM;n(n)(t)]t, det(Wn)=tnDn(1/t), and B=[t,…,t]t. Here we have only two cases.
Case I ( 5 ≤ m ≤ n - 1 ). By using Cramer’s rule we have(21)HM;mnt=TmdetWn,where Tm is a determinant obtained by replacing mth column of Wn by column of B; i.e.,(22)HM;mnt=1tnDn1/t1-t-t⋯-tt⋯-t-t01-t⋯-tt⋯-t-t-t-t⋯-tt⋯-t-t⋮⋮⋮⋮⋮⋮00⋯0t⋯01-t.Let Ci denote the ith column of Tm. Adding Cm in Cm+1,Cm+2,…,Cn of Tm and simplifying it we have a determinant of order m. Hence(23)HM;mnt=1tnDn1/t1-t-t⋯-tt01-t⋯-tt-t-t⋯-tt⋮⋮⋮⋮00⋯-tt.Now by adding (m-1)th column of the last determinant in its mth column and simplifying it we finally have(24)HM;mnt=tm-1Km-21/ttnDn1/t.
Case II ( m = n ). Using again Cramer’s rule, we have(25)HM;nnt=1tnDn1/t1-t-t⋯-t-t-tt01-t⋯-t-t-tt-t-t⋯-t-t-tt⋮⋮⋮⋮⋮⋮00⋯-t1-t-tt00⋯0-t1-tt00⋯0-t0t.Adding Cn in Cn-2 and simplifying we have the result(26)HM;mnt=1-ttm-2Km-31/ttnDn1/t.Now we have our main result.Theorem 10.
The Hilbert series of the monoidM(D~n∞) is(27)HMnt=1tnDn1/t.Proof.
From Theorem7 we have(28)HMnt=1+HM;1nt+HM;2nt+⋯+HM;n-1nt+HM;nnt=1tnDn1/ttnDn1t+t3-3t2+4t+t4K31t+t5K41t+⋯+tn-1Kn-21t+1-ttn-1Kn-31t=1tnDn1/t1-ttn-1Kn-11t-tn-2Kn-21t+t3-3t2+4t+t4B31t+⋯+tn-1Kn-21t+1-ttn-1Kn-31t=1tnDn1/tt4K41t+t3-3t2+4t=1tnDn1/tt41t4-4t3+3t2-1t+t3-3t2+4t=1tnDn1/t.


## 4. Conjecture on the Upper Bound of Growth Rate ofM(D~n∞)

In this section we compute the growth rates ofM(D~n∞) and show them on the graph. We see that the growth rate is bounded above by 4. Let rn be the growth rate (or the maximal root of the polynomial Dn(λ)). We compute few initial growth rates (using Mathematica and derive 6) for M(D~n∞). Let rn denote the growth rate of M(D~n∞); then we have the following few initial values of rn: r5=3.629, r6=3.732, r7=3.791, r8=3.831, r9=3.858, r10=3.879, r11=3.895, r12=3.907, r13=3.917, r14=3.926, r15=3.933, r16=3.939, r17=3.944, r18=3.948, r19=3.952, r20=3.956. We also compute r40=3.984, r60=3.992, r80=3.995, r100=3.996, and r120=3.997 (using Mathematica). We have Figure 4 representing the growth rate of M(D~n∞).Figure 4We observe that the growth rate forM(D~n∞) approaching 4 as n approaches ∞. Hence at the end we have the following.Conjecture. The growth rate of M(D~n∞) is bounded above by 4.



---

*Source: 1901657-2018-07-17.xml*