Kazhdan–Lusztig Bases, Polynomials, and Cells

Uniqueness and inverse generators. Any semilinear ring homomorphism with the prescribed coefficient action and generator images is unique: its action on $A=\mathbb{Z}[v^{\pm 1}]$ is fixed, and the $H_{s_i}$ generate $H_v(n)$ as an $A$-algebra. Put $\lambda :=v^{-1}-v$. By the quadratic relation, $H_{s_i}(H_{s_i}-\lambda )=1=(H_{s_i}-\lambda )H_{s_i}$, so $H_{s_i}^{-1}=H_{s_i}-\lambda$. Multiplying the quadratic relation by $H_{s_i}^{-2}$ gives $H_{s_i}^{-2}=1-\lambda H_{s_i}^{-1}=1+(v-v^{-1})H_{s_i}^{-1}$, the quadratic relation with $v$ replaced by $v^{-1}$.

The assignment respects the presentation. On the free associative algebra, extend $v\mapsto v^{-1}$ and $H_{s_i}\mapsto H_{s_i}-\lambda$ semilinearly and multiplicatively as in [F2]. In the quotient, step 1.1 identifies $H_{s_i}-\lambda$ with $H_{s_i}^{-1}$. The inverse quadratic relation in step 1.1 shows that the image of each quadratic relator is zero in the quotient. The braid relator maps to the equality obtained by inverting both sides of $H_{s_i}{H}_{s_{i+1}}{H}_{s_i}=H_{s_{i+1}}{H}_{s_i}{H}_{s_{i+1}}$; the words are palindromes. A distant commutation relator maps to the commutation of the inverse generators, which follows by inverting the original equality. Thus the defining ideal is preserved and the assignment descends to a unital semilinear algebra endomorphism of $H_v(n)$.

Involutivity. Applying bar twice fixes $v$. Since a ring homomorphism sends the inverse of a unit to the inverse of its image, $\stackrel{‾}{\overline{H_{s_i}}}=\overline{H_{s_i}^{-1}}={\overline{H_{s_i}}}^{-1}=(H_{s_i}^{-1}{)}^{-1}=H_{s_i}$. It therefore fixes every generator and coefficient, so bar squared is the identity.

Formula on the standard basis. Let $w=s_{i_1}\cdots s_{i_k}$ be reduced. By multiplicativity, $\overline{H_w}=H_{s_{i_1}}^{-1}\cdots H_{s_{i_k}}^{-1}=(H_{s_{i_k}}\cdots H_{s_{i_1}}{)}^{-1}=H_{w^{-1}}^{-1}$. This includes $w=\mathrm{i}\mathrm{d}$, for which the product is empty. Every generator is a unit by step 1.1, hence every $H_w$ is a unit, and applying bar gives the equivalent formula $\overline{H_{w^{-1}}}=H_w^{-1}$. This proves the statement. The case $n=1$ has no generators and reduces to the coefficient involution of $A$.

Conventions and length. Let $\bar{x}$ be the conjugate of the zero-based permutation $x$ under $i\mapsto i+1$, and put $R_x(m,h):=r_x(m-1,h-1)$ for $1\le m,h\le n$, with $R_x(0,h)=R_x(m,0)=0$. Then $R_x(m,h)=\mathrm{\mid }\{i\le m:\bar{x}(i)\le h\}\mathrm{\mid }$. For $n\ge 2$, in the type-$A_{n-1}$ root realization on $E=\{(a_1,\dots ,a_n):\sum a_i=0\}$ the roots are $e_a-e_b$ $(a\mathrm{\ne }b)$. Choose the positive roots $e_a-e_b$ for $a<b$; their simple roots are $e_i-e_{i+1}$. Each root has squared length $2$, all root pairings are integers, and coordinate swaps preserve the root set, so this is a finite reduced crystallographic root system. Its simple reflections swap adjacent coordinates, its root reflections are all coordinate transpositions, and its Weyl group is $S_n$. For $n=1$ the root system is empty and the group is trivial. Swapping adjacent entries changes inversion count by one; repeatedly swapping an adjacent descent reduces any nonidentity permutation to the identity, so Coxeter length is the inversion length $\mathrm{\ell }$. A nonidentity permutation has a left simple descent because its inverse list is not increasing. Thus the strong order in [F3], transported by the shift, has covers $x\to tx$ with $t$ a transposition and $\mathrm{\ell }(tx)=\mathrm{\ell }(x)+1$; left multiplication by a simple $s_i$ raises or lowers $\mathrm{\ell }$ by one.

A strong cover decreases every rank number. Let $z=tx$ be a cover, with $t=(ab)$ and $a<b$. Write $p_x(c):={\bar{x}}^{-1}(c)$. If $p_x(a)<p_x(b)$, swapping the values creates their inversion and changes each intermediate value $c$ with $a<c<b$ and $p_x(a)<p_x(c)<p_x(b)$ by two more inversions in the same direction; if $e$ is the number of such values, the total length change is $1+2e>0$. Reversing the positions gives the negative change, so $\mathrm{\ell }(z)=\mathrm{\ell }(x)+1$ implies $p_x(a)<p_x(b)$. For thresholds $h<a$ or $h\ge b$, swapping $a,b$ leaves $R_x(m,h)$ unchanged. For $a\le h<b$, a prefix changes only when $p_x(a)\le m<p_x(b)$; there it contains $a$ for $x$ and $b$ for $z$, so $R_x(m,h)=R_z(m,h)+1$, while outside that range the counts agree. Hence $R_x(m,h)\ge R_z(m,h)$ for every $m,h$, and every strong-order chain is rank-inequality increasing. The rank inequalities are a partial order: reflexivity and transitivity are immediate, and the differences $R_x(m,h)-R_x(m-1,h)$ for all $h$ determine each value $\bar{x}(m)$, so equal rank matrices imply equal permutations.

Rank lifting, including paired descents. Put $p_x(c)={\bar{x}}^{-1}(c)$. Multiplication by $s=s_i$ changes rank numbers only at threshold $h=i$: it adds $1$ on the descent window $p_x(i+1)\le m<p_x(i)$, subtracts $1$ on the ascent window $p_x(i)\le m<p_x(i+1)$, and is unchanged elsewhere. Suppose $u\le v$ in rank order and $sv<v$, with descent window $V$. At $m\in V$, put $a=R_v(m,i)$; the prefix contains $i+1$ but not $i$, so $R_v(m,i-1)=a$ and $R_v(m,i+1)=a+1$. If $su>u$ and $R_u(m,i)=a$, a prefix of $u$ containing $i$ would have $R_u(m,i-1)=a-1$, contrary to the rank inequality at $i-1$. Otherwise ascent forces it to contain neither adjacent value, giving $R_u(m,i+1)=a$, contrary to the inequality at $i+1$. Thus $R_u(m,i)\ge R_v(m,i)+1$ on $V$, and $u\le sv$. Now suppose $su<u$, with descent window $U$. To prove $su\le sv$, the only potentially worsened inequality is at $h=i$ and $m\in V\setminus U$. Such a prefix of $u$ contains either both $i,i+1$ or neither. If its rank at $i$ equalled $a$, the both case would give rank $a-1$ at $i-1$, and the neither case rank $a$ at $i+1$, contradicting the respective inequalities. Hence again the rank gap is at least $1$. Outside $V\setminus U$, adding the two window indicators cannot spoil the original rank inequalities; therefore $su\le sv$. The conventions $R_x(m,0)=0$ and $R_x(m,n)=m$ include the extreme adjacent pairs. Also $su<u$ implies $su\le u$ directly from the window formula.

Rank order is strong Bruhat order. Induct on $\mathrm{\ell }(u)+\mathrm{\ell }(v)$ for $u\le v$ in rank order. If $v$ is the identity, its ranks $\min (m,h)$ are the largest possible prefix counts; the inequalities force the same rank matrix for $u$, hence $u=v$ by step 2.1. Otherwise take a simple left descent $s$ of $v$. If $su>u$, step 2.2 gives $u\le sv$ in rank order, so induction gives $u⪯sv$, and the cover $sv\to v$ completes the chain. If $su<u$, the paired-descent argument gives $su\le sv$ in rank order. Both lengths have decreased, so induction gives $su⪯sv$. By the independently proved finite-Weyl subword equivalence in [F3], a fixed reduced expression for $sv$ contains a reduced subword for $su$. Prefixing $s$ to that expression gives a reduced expression for $v$, and prefixing it to the selected subword gives a reduced expression for $u$, since both lengths increase by one. Thus [F3] supplies $u⪯v$ from this reduced subword. This establishes rank order contained in reflection-chain order. Step 2.1 proves the reverse containment, so the two orders agree, proving (a).

Length, inversion symmetry, subwords, and lifting. Every strong cover raises $\mathrm{\ell }$ by one, so if $y\le w$ then $\mathrm{\ell }(y)\le \mathrm{\ell }(w)$, equality holds exactly when $y=w$, and every saturated chain has $\mathrm{\ell }(w)-\mathrm{\ell }(y)$ steps. Moreover $R_{x^{-1}}(h,m)=R_x(m,h)$, so $y\le w$ iff $y^{-1}\le w^{-1}$; this proves (b). Part (c) follows from the reduced-subword characterization in [F3] and the order identification in step 3.1, transported through the index shift. For the first lifting implication in (d), if $sw>w$ then $y\le w<sw$; if $sw<w$, choose a reduced expression for $w$ beginning with $s$. A reduced subword for $y$ cannot use that first letter when $sy>y$, since then its product would have left descent $s$; hence it is a subword for $sw$ and $y\le sw$. For the second implication, if $sy<y$ then $sy\le y\le w$; if $sy>y$, the same reduced-subword argument makes a reduced subword for $sy$ by prefixing $s$ to the subword for $y$, so $sy\le w$. This proves (d).

Intervals. The group $S_n$ is finite, so each interval is finite. For the decomposition, assume $y\le w$, so $y\in [y,w]$. If $z\in [y,w]$ and $z\mathrm{\ne }y$, a saturated chain from $y$ to $z$ has a first cover $y\to a$ with $a\le z\le w$, whence $z\in [a,w]$. Conversely, for every cover $y\to a\le w$, transitivity gives $[a,w]\subseteq [y,w]$. The point $y$ is not in any such upper interval, so $[y,w]=\{y\}\cup {\bigcup }_{y\to a\le w}[a,w]$. This proves (e), including $y=w$, when the union is empty. The arguments use only finite permutations and finite chains; no choice principle is needed.

The reversal map descends. On the free associative $A$-algebra, fix every coefficient and generator and reverse each word; this defines an $A$-linear anti-homomorphism. It sends each quadratic relator to itself, each adjacent braid relator to itself because both sides are palindromes, and each distant commutation relator to its negative. Hence it preserves the defining ideal and descends to an $A$-linear anti-homomorphism $\mathrm{♭}$ of $H_v(n)$.

It is an involution with the required formula. Reversing twice fixes every word, so ${\mathrm{♭}}^2=\mathrm{i}\mathrm{d}$ and $\mathrm{♭}$ is an anti-automorphism. If $w=s_{i_1}\cdots s_{i_k}$ is reduced, then $w^{-1}=s_{i_k}\cdots s_{i_1}$ is reduced and $\mathrm{♭}(H_w)=H_{s_{i_k}}\cdots H_{s_{i_1}}=H_{w^{-1}}$. The empty word gives $\mathrm{♭}(H_{\mathrm{i}\mathrm{d}})=H_{\mathrm{i}\mathrm{d}}$.

It commutes with bar. Put $\lambda =v^{-1}-v$. On coefficients, $\mathrm{♭}(\bar{v})=\mathrm{♭}(v^{-1})=v^{-1}=\overline{\mathrm{♭}(v)}$. On a generator, $\mathrm{♭}(\overline{H_{s_i}})=\mathrm{♭}(H_{s_i}-\lambda )=H_{s_i}-\lambda =H_{s_i}^{-1}=\overline{\mathrm{♭}(H_{s_i})}$. Both composites of $\mathrm{♭}$ and bar are semilinear anti-homomorphisms, so agreement on coefficients and generators from the presentation proves that $\mathrm{♭}$ and bar commute on all of $H_v(n)$. No choice principle is used.

Descent recursion. Put $\alpha :=v-v^{-1}$. If $sx>x$, concatenating reduced words gives $H_s{H}_x=H_{sx}$. If $sx<x$, then $x=s(sx)$ is reduced and $H_s{H}_x=H_s^2{H}_{sx}=H_{sx}+(v^{-1}-v)H_x$ by the quadratic relation. For a left descent $sw<w$, write $w=s(sw)$ and apply bar to its reduced product: $\overline{H_w}=(H_s+\alpha ){\sum }_x{r}_{x,sw}{H}_x$. In the expansion, the coefficient correction $(v^{-1}-v)r_{x,sw}$ from the $sx<x$ terms cancels the $\alpha r_{x,sw}$ term; reindexing the remaining $H_{sx}$ terms gives $\overline{H_w}={\sum }_y{r}_{sy,sw}{H}_y+\alpha {\sum }_{sy>y}{r}_{y,sw}{H}_y$. Comparing coefficients in the standard basis proves (a).

Inverse-index symmetry. Apply $\mathrm{♭}$ to $\overline{H_w}={\sum }_y{r}_{y,w}{H}_y$. Since $\mathrm{♭}$ is $A$-linear, the result is ${\sum }_y{r}_{y,w}{H}_{y^{-1}}$; because $\mathrm{♭}$ commutes with bar and $\mathrm{♭}(H_w)=H_{w^{-1}}$, it is also $\overline{H_{w^{-1}}}={\sum }_x{r}_{x,w^{-1}}{H}_x$. Comparing coefficients at $H_{y^{-1}}$ gives $r_{y,w}=r_{y^{-1},w^{-1}}$.

Support and diagonal. Induct on $\mathrm{\ell }(w)$, with $r_{\mathrm{i}\mathrm{d},\mathrm{i}\mathrm{d}}=1$ and all other coefficients in the identity column zero. If $sy<y$ and $r_{y,w}\mathrm{\ne }0$, (a) gives $r_{sy,sw}\mathrm{\ne }0$, so induction gives $sy\le sw$; take a reduced expression for $sw$ and a reduced subword for $sy$. Prefixing $s$ gives a subword for $s(sy)=y$ in the reduced expression $w=s(sw)$; it is reduced because its length is $1+\mathrm{\ell }(sy)=\mathrm{\ell }(y)$. Hence $y\le w$. If $sy>y$ and $r_{y,w}\mathrm{\ne }0$, at least one of $r_{sy,sw}$ and $r_{y,sw}$ is nonzero. In the first case induction gives $sy\le sw$, and $y<sy$ implies $y\le w$; in the second it gives $y\le sw<w$. Thus the support is contained in $[\mathrm{i}\mathrm{d},w]$. Taking $y=w$ in (a) gives $r_{w,w}=r_{sw,sw}=1$ for a left descent, completing the induction (and the $n=1$ case is the identity base).

Bar symmetry. Induct on $\mathrm{\ell }(w)$ using (a), with the identity column as base. If $sy<y$, then $r_{y,w}=r_{sy,sw}$ and $\mathrm{s}\mathrm{g}\mathrm{n}(sy)\mathrm{s}\mathrm{g}\mathrm{n}(sw)=\mathrm{s}\mathrm{g}\mathrm{n}(y)\mathrm{s}\mathrm{g}\mathrm{n}(w)$, so the induction identity for the smaller column proves the first formula in (d). If $sy>y$, set $\epsilon =\mathrm{s}\mathrm{g}\mathrm{n}(y)\mathrm{s}\mathrm{g}\mathrm{n}(w)$; induction gives $\overline{r_{sy,sw}}=\epsilon r_{sy,sw}$ and $\overline{r_{y,sw}}=-\epsilon r_{y,sw}$, while $\bar{\alpha }=-\alpha$. Applying bar to (a) therefore gives $\overline{r_{y,w}}=\epsilon r_{y,w}$.

Degree, parity, and extreme coefficients. Induct on $\mathrm{\ell }(w)$ for $y\le w$ and write $d=\mathrm{\ell }(w)-\mathrm{\ell }(y)$. If $sy<y$, then $sy\le sw$: indeed $sy\le w$ by $sy<y\le w$, and the first lifting implication in [F3] applied to $sy$ gives $sy\le sw$. Now (a) identifies $r_{y,w}=r_{sy,sw}$, whose length difference is $d$; induction gives the asserted parity, range of degrees, and both extreme coefficients because $\mathrm{s}\mathrm{g}\mathrm{n}(sy)\mathrm{s}\mathrm{g}\mathrm{n}(sw)=\mathrm{s}\mathrm{g}\mathrm{n}(y)\mathrm{s}\mathrm{g}\mathrm{n}(w)$. If $sy>y$, the same lifting implication applied to $y\le w$ gives $y\le sw$, so $r_{y,sw}$ has length difference $d-1$. Its product with $\alpha$ has exponents between $-d$ and $d$, all congruent to $d$ modulo $2$; its top term is $v^d$ and its bottom term is $-\mathrm{s}\mathrm{g}\mathrm{n}(y)\mathrm{s}\mathrm{g}\mathrm{n}(sw)v^{-d}=\mathrm{s}\mathrm{g}\mathrm{n}(y)\mathrm{s}\mathrm{g}\mathrm{n}(w)v^{-d}$. The other term $r_{sy,sw}$ in (a) is zero unless $sy\le sw$ by (b), and when nonzero its length difference is $d-2$, so it has the same parity and lies strictly between those two extreme degrees. This proves (c), including the endpoint $d=0$ through the first case.

Matrix inversion. Apply bar to $\overline{H_z}={\sum }_y{r}_{y,z}{H}_y$ and use bar squared equal to the identity to obtain $H_z={\sum }_{x,y}{r}_{x,y}\overline{r_{y,z}}{H}_x$. Standard-basis independence gives ${\sum }_y{r}_{x,y}\overline{r_{y,z}}={\delta }_{x,z}$. Applying coefficient bar to this equality gives $\bar{R}R=1$ as well as $R\bar{R}=1$; all sums are finite because $S_n$ is finite. By (b), coefficients outside Bruhat order vanish, including when the interval is empty. The inductions use the identity permutation as their length-zero base, and all arguments are choice-free.

Reduce to the interval. Fix $x<z$ and set $d:=\mathrm{\ell }(z)-\mathrm{\ell }(x)$. Bruhat gradedness gives $d>0$. The R-matrix identity and bar symmetry yield $0={\sum }_y{r}_{x,y}\overline{r_{y,z}}=\mathrm{s}\mathrm{g}\mathrm{n}(z){\sum }_y\mathrm{s}\mathrm{g}\mathrm{n}(y)r_{x,y}{r}_{y,z}$. By support, a nonzero summand requires both $x\le y$ and $y\le z$, so $0={\sum }_{x\le y\le z}\mathrm{s}\mathrm{g}\mathrm{n}(y)r_{x,y}{r}_{y,z}$.

Extract the lowest degree. For each $y\in [x,z]$, let $d_1:=\mathrm{\ell }(y)-\mathrm{\ell }(x)$ and $d_2:=\mathrm{\ell }(z)-\mathrm{\ell }(y)$, so $d_1+d_2=d$. The least exponent in $r_{x,y}{r}_{y,z}$ is $-d$ and its coefficient is $\mathrm{s}\mathrm{g}\mathrm{n}(x)\mathrm{s}\mathrm{g}\mathrm{n}(y{)}^2\mathrm{s}\mathrm{g}\mathrm{n}(z)=\mathrm{s}\mathrm{g}\mathrm{n}(x)\mathrm{s}\mathrm{g}\mathrm{n}(z)$. The external factor $\mathrm{s}\mathrm{g}\mathrm{n}(y)$ in step 1.1 makes the coefficient of $v^{-d}$ in that summand $\mathrm{s}\mathrm{g}\mathrm{n}(x)\mathrm{s}\mathrm{g}\mathrm{n}(z)\mathrm{s}\mathrm{g}\mathrm{n}(y)$. Since every other exponent in each factor is strictly above its least exponent, no other product terms contribute to degree $-d$. Taking that coefficient in the zero sum of step 1.1 gives $0=\mathrm{s}\mathrm{g}\mathrm{n}(x)\mathrm{s}\mathrm{g}\mathrm{n}(z){\sum }_{x\le y\le z}\mathrm{s}\mathrm{g}\mathrm{n}(y)$. The prefactor is $\pm 1$, proving the claim. The interval is finite, and no choice principle is used.