The type-A Kazhdan–Lusztig basis has elementary triangular bar properties

Construct the coefficients. Fix $w$ and descend on $d=\mathrm{\ell }(w)-\mathrm{\ell }(x)$ over the finite lower Bruhat ideal $\{x:x\le w\}$, starting with $p_{w,w}=1$. Suppose $x<w$ and $p_{y,w}$ has been constructed for every $x<y\le w$, satisfying $p_{y,w}={\sum }_{y\le z\le w}{r}_{y,z}\overline{p_{z,w}}$. Put $a_x:={\sum }_{x<y\le w}{r}_{x,y}\overline{p_{y,w}}$. Then $\begin{array}{rl}{\displaystyle \overline{a_x}}& {\displaystyle =\sum _{x<y\le w}\overline{r_{x,y}}{p}_{y,w}=\sum _{x<y\le z\le w}\overline{r_{x,y}}{r}_{y,z}\overline{p_{z,w}}}\\ {\displaystyle }& {\displaystyle =-\sum _{x<z\le w}{r}_{x,z}\overline{p_{z,w}}=-a_x\mathrm{.}}\end{array}$ The second equality uses the induction equations; for $x<z$, the identity $\bar{R}R=I$ makes the sum over $x\le y\le z$ zero, and its omitted diagonal term is $\overline{r_{x,x}}{r}_{x,z}=r_{x,z}$. Write $a_x={\sum }_{m\in \mathbb{Z}}{\gamma }_m{v}^m$. Anti-invariance gives ${\gamma }_{-m}=-{\gamma }_m$ and ${\gamma }_0=0$. Define $p_{x,w}:={\sum }_{m>0}{\gamma }_m{v}^m$. Then $p_{x,w}\in v\mathbb{Z}[v]$ and $p_{x,w}-\overline{p_{x,w}}=a_x$. The induction is finite and uses no choice principle.

Bar invariance and the coefficient equations. Set ${\underset{‾}{H}}_w:={\sum }_{y\le w}{p}_{y,w}{H}_y$. The coefficient of $H_x$ in $\overline{{\underset{‾}{H}}_w}$ is ${\sum }_{x\le y\le w}{r}_{x,y}\overline{p_{y,w}}$. For $x=w$ this is $1$; for $x<w$ it is $\overline{p_{x,w}}+a_x=p_{x,w}$ by step 1.1. If $x\le ̸w$, no $y\le w$ can satisfy $x\le y$, so support from [F3] gives coefficient zero. Thus $\overline{{\underset{‾}{H}}_w}={\underset{‾}{H}}_w$ and $p_{x,w}={\sum }_{x\le y\le w}{r}_{x,y}\overline{p_{y,w}}$, which is the bar-duality formula.

Uniqueness. If two bar-invariant elements satisfy the triangular condition, their difference is a bar-fixed sum $h={\sum }_{y<w}{c}_y{H}_y$ with each $c_y\in v\mathbb{Z}[v]$. If $h\mathrm{\ne }0$, choose a Bruhat-maximal $x$ in its finite support. The coefficient of $H_x$ in $\bar{h}$ is $\overline{c_x}$: no supported $y>x$ contributes, and support of $r_{x,y}$ requires $x\le y$. Since $h=\bar{h}$, $c_x=\overline{c_x}$; but $v\mathbb{Z}[v]$ and $v^{-1}\mathbb{Z}[v^{-1}]$ intersect only in $0$, a contradiction. Thus the element is unique. The construction also gives $p_{w,w}=1$ and $p_{y,w}=0$ unless $y\le w$.

Basis. The transition from $(H_w)$ to $({\underset{‾}{H}}_w)$ is unitriangular on the finite Bruhat poset: each ${\underset{‾}{H}}_w=H_w+{\sum }_{y<w}{p}_{y,w}{H}_y$. A finite unitriangular matrix over $A$ is invertible, so $({\underset{‾}{H}}_w{)}_{w\in S_n}$ is an $A$-basis.

Degree, leading term, and parity. Induct on $d=\mathrm{\ell }(w)-\mathrm{\ell }(x)$, with $p_{w,w}=1$. For $x<w$, the equation in step 1.1 has $a_x={\sum }_{x<y\le w}{r}_{x,y}\overline{p_{y,w}}$. By [F3] and induction, every term has exponents congruent to $d$ modulo $2$. The term $y=w$ is $r_{x,w}$, whose highest term is $v^d$ with coefficient $1$. For each $y<w$, put $d_1=\mathrm{\ell }(y)-\mathrm{\ell }(x)$ and $d_2=\mathrm{\ell }(w)-\mathrm{\ell }(y)\ge 1$, so $d_1+d_2=d$; the highest degree of $r_{x,y}\overline{p_{y,w}}$ is at most $d_1-1\le d-2$, since $p_{y,w}\in v\mathbb{Z}[v]$. Therefore $a_x$ has highest term $v^d$ with coefficient $1$ and only exponents of parity $d$. As $p_{x,w}$ is its positive-degree part by step 1.1, it follows that $p_{x,w}=v^d+$ terms of strictly smaller degree and $p_{x,w}\in v^d\mathbb{Z}[v^{-2}]$. This proves the degree and parity clauses.

Inverse-index symmetry. By [F4], $\mathrm{♭}({\underset{‾}{H}}_w)$ is bar-fixed. By [F5], inversion preserves Bruhat order, so this element has the form $H_{w^{-1}}+{\sum }_{y<w}{p}_{y,w}{H}_{y^{-1}}$ with lower terms in $v\mathbb{Z}[v]$. Uniqueness from step 3.1 gives $\mathrm{♭}({\underset{‾}{H}}_w)={\underset{‾}{H}}_{w^{-1}}$. Comparing coefficients yields $p_{y^{-1},w^{-1}}=p_{y,w}$.