Coxeter Descents, Poincaré Polynomials, and Growth — Examples

This example re-derives the products of Classical Poincare products for A, B, D and I2(m) from the permutation and signed-permutation models (3) by explicit insertion in the same models, with $[k{]}_t=1+t+\cdots +t^{k-1}$. For the $B_n,D_n$ orbit labels below, write $z_i=\sqrt{2}{\epsilon }_i^{\ast }$ for the scaled dual coordinate functionals from that item; a vertex labelled $\pm {\epsilon }_i$ denotes the corresponding orbit point $\pm z_i$.

(1) Type $A$: inserting a letter into a permutation. Let $n\ge 2$. Use the order-preserving identification of the library's $S_n=\mathrm{Sym}(\{0,\dots ,n-1\})$ with permutations of $\{1,\dots ,n\}$; under it the adjacent generator is $s_i\mapsto (ii+1)$ and $\mathrm{\ell }$ is the inversion number (The finite symmetric group $S_n$, one-line notation, and cycle notation, Inversions, inversion number, the sign $\mathrm{sgn}(\sigma )=(-1{)}^{\mathrm{inv}(\sigma )}$, and even and odd permutations, Classical Poincare products for A, B, D and I2(m) from the permutation and signed-permutation models (1)(a), Proof 3.1). In this one-based notation, every $\sigma \in S_{n-1}$ and every position $i\in \{1,\dots ,n\}$ give a permutation ${\sigma }^{(i)}$ by inserting the letter $n$ between positions $i-1$ and $i$. The map $(\sigma ,i)\mapsto {\sigma }^{(i)}$ is a bijection $S_{n-1}\times \{1,\dots ,n\}\to S_n$, and since the new inversions are exactly the $n-i$ pairs formed by $n$ with the entries to its right, $\mathrm{\ell }({\sigma }^{(i)})=\mathrm{\ell }(\sigma )+(n-i)\mathrm{.}$ Hence $P_{S_n}(t)=P_{S_{n-1}}(t){\sum }_{i=1}^n{t}^{n-i}=[n{]}_t{P}_{S_{n-1}}(t)$, so $P_{S_n}(t)=[n{]}_t!=[2{]}_t[3{]}_t\cdots [n{]}_t$ and $P_{A_n}(t)=[n+1{]}_t!$.

(2) Type $B$: inserting a sign. For $n\ge 2$, let $W(B_n)$ be the signed permutation group acting on ${\mathbb{R}}^n$ as in Classical Poincare products for A, B, D and I2(m) from the permutation and signed-permutation models (1)(b) and (2)(b), with $W(B_{n-1})$ the subgroup fixing ${\epsilon }_1$, as identified by Classical Poincare products for A, B, D and I2(m) from the permutation and signed-permutation models (1)(b), (2)(b), and the parabolic-length fact in its Fact F16. Each $w\in W(B_n)$ has a unique decomposition $w=du$ with $u\in W(B_{n-1})$ and $d$ the minimal element of its left coset $wW(B_{n-1})$; the possible $d$ correspond bijectively to the orbit points labelled $\{\pm {\epsilon }_1,\dots ,\pm {\epsilon }_n\}$, and the distance (minimal coset length) of the representative sending ${\epsilon }_1$ to ${\epsilon }_i$ is $i-1$, while for $-{\epsilon }_i$ it is $2n-i$; the list $0,1,\dots ,2n-1$ is obtained by moving ${\epsilon }_1$ along the chain ${\epsilon }_1,\dots ,{\epsilon }_n$, applying the sign change of the last coordinate, and returning along the negative chain. By The orbit of a dual fundamental functional: stabilizer, minimal coset length, Schreier distance, and the quotient formula (2),(4), $P_{B_n}(t)=[2n{]}_t{P}_{B_{n-1}}(t),\text{so}{P}_{B_n}(t)={\prod }_{i=1}^n[2i{]}_t\mathrm{.}$

(3) Type $D$: even signs. For $n\ge 4$, let $W(D_n)$ be the even signed permutation group and let $W(D_{n-1})$ be the parabolic obtained by deleting the terminal node $s_n$ (Classical Poincare products for A, B, D and I2(m) from the permutation and signed-permutation models (1)(c),(2)(c)). The orbit of the corresponding dual fundamental functional has the Schreier graph obtained from the chains ${\epsilon }_1-\cdots -{\epsilon }_n$ and $(-{\epsilon }_1)-\cdots -(-{\epsilon }_n)$ by the cross edges ${\epsilon }_1-(-{\epsilon }_2)$ and $(-{\epsilon }_1)-{\epsilon }_2$; its distances are $0,\dots ,n-2$, then $n-1$ twice, then $n,\dots ,2n-2$ (Classical Poincare products for A, B, D and I2(m) from the permutation and signed-permutation models (2)(c)). Thus the quotient polynomial is $[n{]}_t(1+t^{n-1})$. The orbit quotient formula gives $P_{D_n}(t)=[n{]}_t(1+t^{n-1})P_{D_{n-1}}(t)$; since $(1+t^{n-1})[n-1{]}_t=[2n-2{]}_t$, this recurrence telescopes from $P_{D_3}=[4{]}_t!$ in (4) to $P_{D_n}(t)=[n{]}_t{\prod }_{i=1}^{n-1}[2i{]}_t$ for $n\ge 4$. The cases $D_2,D_3$ are checked separately in (4).

(4) Bases and consistency checks. $P_{S_2}=1+t=[2{]}_t$, $P_{S_3}=1+2t+2t^2+t^3=[2{]}_t[3{]}_t$, $P_{S_4}=[2{]}_t[3{]}_t[4{]}_t=1+3t+5t^2+6t^3+5t^4+3t^5+t^6$ (a symmetric unimodal inversion-count sequence), $P_{B_1}=1+t$, $P_{B_2}=[2{]}_t[4{]}_t=1+2t+2t^2+2t^3+t^4$; for $D$ one has $D_2=A_1\times A_1$, $D_3=A_3$ (Classical Poincare products for A, B, D and I2(m) from the permutation and signed-permutation models (3), Proof 5.1) with $P_{D_2}=(1+t{)}^2$ and $P_{D_3}=[3{]}_t(1+t^2)(1+t{)}^2=[4{]}_t!=P_{A_3}$, and $D_4$ gives $[4{]}_t[2{]}_t[4{]}_t[6{]}_t=1+4t+9t^2+16t^3+23t^4+28t^5+30t^6+28t^7+23t^8+16t^9+9t^{10}+4t^{11}+t^{12},$ a palindromic polynomial of degree $12$ whose coefficients sum to $192=\mathrm{\mid }W(D_4)\mathrm{\mid }$. The evaluations at $t=1$ recover $n!$, $2^{n}n!$ and $2^{n-1}n!$.

Let $W=S_3$ in its type $A_2$ Coxeter presentation with $S=\{s_1,s_2\}$ (The finite symmetric group $S_n$, one-line notation, and cycle notation, Inversions, inversion number, the sign $\mathrm{sgn}(\sigma )=(-1{)}^{\mathrm{inv}(\sigma )}$, and even and odd permutations). The library defines $S_3$ on $\{0,1,2\}$; the order-preserving relabelling $j\mapsto j+1$ identifies it with permutations of $\{1,2,3\}$ and preserves inversion number, so we write the adjacent generators as $s_1=(12)$ and $s_2=(23)$. This is the smallest-rank finite Coxeter system whose diagram is not a product of copies of $A_1$. The example checks the finite $A_2$ instances of parabolic factorization, descent inclusion-exclusion and the Steinberg identity of Finite descent parabolics, parabolic factorization, the Steinberg inclusion-exclusion identity, and rational growth, and of the degree product and reciprocity of The Poincare polynomial as a product of q-integers of the basic degrees, with longest-element reciprocity. The lengths, descents and reciprocity calculations use no choice. The basic-degree comparison assumes the Axiom of Choice (The Axiom of Choice) through the degree-table supplier cited in (3).

(1) Lengths and Poincare polynomial. The six elements are $1$ (length $0$), $s_1,s_2$ (length $1$), $s_1{s}_2,s_2{s}_1$ (length $2$) and $w_0=s_1{s}_2{s}_1=s_2{s}_1{s}_2$ (length $3$); hence $P_W(t)=1+2t+2t^2+t^3=[2{]}_t[3{]}_t=t^3{P}_W(t^{-1})$, with $N=\mathrm{\ell }(w_0)=3=\mathrm{\mid }{\mathrm{\Phi }}_{+}\mathrm{\mid }$ (The longest element as the opposition of the chamber, and longest elements of finite parabolics (1)(ii)).

(2) Descent classes and Steinberg identity. The right descent sets are $D_R(1)=\mathrm{\varnothing }$, $D_R(s_1)=\{s_1\}$, $D_R(s_2)=\{s_2\}$, $D_R(s_1{s}_2)=\{s_2\}$, $D_R(s_2{s}_1)=\{s_1\}$, $D_R(w_0)=\{s_1,s_2\}$, so $D_S^S(t)=t^3$ and, with the interval convention $D_I^J=\{w:I\subseteq D_R(w)\subseteq J\}$ of Length generating series, descent-class series, spherical subsets, and the multivariate descent polynomial (2), the nine interval series are $D_{\mathrm{\varnothing }}^{\mathrm{\varnothing }}(t)=1,D_{\mathrm{\varnothing }}^{\{s_i\}}(t)=1+t+t^2,D_{\mathrm{\varnothing }}^S(t)=P_W(t)=1+2t+2t^2+t^3,D_{\{s_i\}}^{\{s_i\}}(t)=t+t^2,D_{\{s_i\}}^S(t)=t+t^2+t^3(i=1,2),D_S^S(t)=t^3\mathrm{.}$ The parabolic series are $P_{W_{\mathrm{\varnothing }}}=1$ and $P_{W_{\{s_i\}}}=1+t$. The Steinberg identity (Finite descent parabolics, parabolic factorization, the Steinberg inclusion-exclusion identity, and rational growth (4)) reads $1-\frac{2}{1+t}+\frac{1}{1+2t+2t^2+t^3}=\frac{t^3}{1+2t+2t^2+t^3},$ which is a polynomial identity after clearing denominators, and equivalently $1\mathrm{/}{P}_W(t^{-1})={\sum }_K(-1{)}^{\mathrm{\mid }K\mathrm{\mid }}\mathrm{/}{P}_{W_K}(t)$.

(3) Degree product. The basic degrees of $A_2$ are $2$ and $3$ (A regular Coxeter eigenvector determines the basic degrees: the exponent-residue identification and the complete degree tables for all finite Coxeter types (2), under the stated AC premise), so ${\prod }_i[d_i{]}_t=[2{]}_t[3{]}_t=P_W(t)$, $\mathrm{\mid }W\mathrm{\mid }=P_W(1)=6$ (The cardinality $\mid A\mid$ of a finite set) and ${\sum }_i(d_i-1)=1+2=3=N$.

(4) Reciprocity. $t^3{P}_W(t^{-1})=t^3(1+2t^{-1}+2t^{-2}+t^{-3})=t^3+2t^2+2t+1=P_W(t)$: the coefficient sequence $(1,2,2,1)$ is palindromic, in agreement with The Poincare polynomial as a product of q-integers of the basic degrees, with longest-element reciprocity (2).

Let $W=⟨s,t\mid s^2=t^2=1⟩$ be the infinite dihedral Coxeter group, so $S=\{s,t\}$ and $m(s,t)=\mathrm{\infty }$ (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, The rank-two block computation, exact dihedral orders, the signed reflection action, and ambient reducedness (3)(c),(4)). Then:

(1) Growth series. Every word reduces by canceling adjacent equal generators to an alternating word. For each $q\ge 1$, the two alternating words $(st{)}^q$ and $(ts{)}^q$ have length $2q$; for each $q\ge 0$, $(st{)}^{q}s$ and $(ts{)}^{q}t$ have length $2q+1$. These words are reduced by The rank-two block computation, exact dihedral orders, the signed reflection action, and ambient reducedness (7), with the generators interchanged for the words beginning with $t$; their pairwise distinctness is proved in step 1.1 below using the infinite order of $st$ from (4). They exhaust the nonidentity elements, so $W$ has one element of length $0$ and exactly two of each length $n\ge 1$: $P_W(t)=1+2t+2t^2+2t^3+\cdots =1+\frac{2t}{1-t}=\frac{1+t}{1-t}\in \mathbb{Q}(t)$ The coefficientwise identity $(1-t)P_W=1+t$ follows from the displayed coefficients by the Cauchy product (Formal power series over a commutative ring and the coefficient-extraction functional $[x^n]$), and $1-t$ has unit constant term (A formal power series is a unit exactly when its constant coefficient is a unit, Rational formal power series, proper presentations and reduced denominators).