Bruhat intervals are Eulerian: parity balance of the elements, and the Möbius function of a full interval

Case 1: the lifting-paired involution. Let $u<v$ and let $s\in S$ satisfy $\mathrm{\ell }(vs)=\mathrm{\ell }(v)-1$; such an $s$ exists because a reduced expression $v=s_1\cdots s_q$ of positive length $q=\mathrm{\ell }(v)$ [F3] has $vs=s_1\cdots s_{q-1}$, a word of length $q-1$ representing $vs$, so $\mathrm{\ell }(vs)\le q-1$ and hence $\mathrm{\ell }(vs)=q-1$ by [F2]. Assume $\mathrm{\ell }(us)>\mathrm{\ell }(u)$. Then $z\mapsto zs$ is a fixed-point-free involution of the finite set $[u,v]$ [F5]: for $z\in [u,v]$ with $\mathrm{\ell }(zs)>\mathrm{\ell }(z)$, lifting case (a) applied to $z\le v$ (with $\mathrm{\ell }(vs)<\mathrm{\ell }(v)$) gives $zs\le v$, while $u\le z\le zs$ gives $u\le zs$; for $z\in [u,v]$ with $\mathrm{\ell }(zs)<\mathrm{\ell }(z)$, lifting case (a) applied to $u\le z$ (with $\mathrm{\ell }(us)>\mathrm{\ell }(u)$) gives $u\le zs$, while $zs\le z\le v$ gives $zs\le v$. Since $(zs)s=z$ by $s^2=1$ and associativity [F4, F13], and $\mathrm{\ell }(zs)\mathrm{\ne }\mathrm{\ell }(z)$ [F2], the map is an involution without fixed point, so $[u,v]$ is partitioned into the pairs $\{z,zs\}$ of opposite length; each pair contributes $1+(-1)=0$ to ${\sum }_{x\in [u,v]}(-1{)}^{\mathrm{\ell }(x)}$, and the cardinality of the finite set $[u,v]$ is defined [F8], so the sum vanishes.

Case 2: the reduction to the strip $[u^{\mathrm{\prime }},v^{\mathrm{\prime }}]$. Keep $s$ with $\mathrm{\ell }(vs)=\mathrm{\ell }(v)-1$ and assume now $\mathrm{\ell }(us)<\mathrm{\ell }(u)$; put $u^{\mathrm{\prime }}:=us$ and $v^{\mathrm{\prime }}:=vs$, so that $u^{\mathrm{\prime }}<u\le v$ and $v^{\mathrm{\prime }}<v$ by [F2], and $[u,v]=[u^{\mathrm{\prime }},v]\setminus B$ with $B:=\{z\in [u^{\mathrm{\prime }},v]:u\nleqq z\}$. Since $\mathrm{\ell }(u^{\mathrm{\prime }})+\mathrm{\ell }(v)=\mathrm{\ell }(u)+\mathrm{\ell }(v)-1$, the induction hypothesis applies to the pair $(u^{\mathrm{\prime }},v)$; and $u^{\mathrm{\prime }}\mathrm{\ne }v$, because their lengths satisfy $\mathrm{\ell }(u^{\mathrm{\prime }})=\mathrm{\ell }(u)-1<\mathrm{\ell }(u)<\mathrm{\ell }(v)$ by [F12]; so $\mathrm{\Phi }(u^{\mathrm{\prime }},v):={\sum }_{x\in [u^{\mathrm{\prime }},v]}(-1{)}^{\mathrm{\ell }(x)}$ is assumed to vanish, and $\mathrm{\Phi }(u,v)=-\mathrm{\Phi }(B)$, both sums being finite by [F5]. To compute $B$, let $z\in [u^{\mathrm{\prime }},v]$ with $u\nleqq z$: if $\mathrm{\ell }(zs)<\mathrm{\ell }(z)$, then lifting case (a) applied to $u^{\mathrm{\prime }}\le z$ (with $\mathrm{\ell }(u^{\mathrm{\prime }}s)=\mathrm{\ell }(u)>\mathrm{\ell }(u^{\mathrm{\prime }})$ and $\mathrm{\ell }(zs)<\mathrm{\ell }(z)$) gives $u=u^{\mathrm{\prime }}s\le z$, a contradiction; hence $\mathrm{\ell }(zs)>\mathrm{\ell }(z)$, and lifting case (a) applied to $z\le v$ gives $z\le vs=v^{\mathrm{\prime }}$. Conversely every $z\in [u^{\mathrm{\prime }},v^{\mathrm{\prime }}]$ with $u\nleqq z$ lies in $B$, because $v^{\mathrm{\prime }}\le v$. So $B=\{z\in [u^{\mathrm{\prime }},v^{\mathrm{\prime }}]:u\nleqq z\}$. If $u\le v^{\mathrm{\prime }}$, then $B=[u^{\mathrm{\prime }},v^{\mathrm{\prime }}]\setminus [u,v^{\mathrm{\prime }}]$ and $\mathrm{\Phi }(B)=\mathrm{\Phi }(u^{\mathrm{\prime }},v^{\mathrm{\prime }})-\mathrm{\Phi }(u,v^{\mathrm{\prime }})$, where both pairs $(u^{\mathrm{\prime }},v^{\mathrm{\prime }})$ and $(u,v^{\mathrm{\prime }})$ have strictly smaller length sum and are strictly ordered: $u^{\mathrm{\prime }}<v^{\mathrm{\prime }}$ because $u^{\mathrm{\prime }}\le u\le v^{\mathrm{\prime }}$ and $u^{\mathrm{\prime }}=v^{\mathrm{\prime }}$ would give $u\le u^{\mathrm{\prime }}=us<u$, and $u<v^{\mathrm{\prime }}$ because $u\le v^{\mathrm{\prime }}$ with $u=v^{\mathrm{\prime }}$ would give $us=v$, hence $\mathrm{\ell }(v)=\mathrm{\ell }(us)=\mathrm{\ell }(u)-1<\mathrm{\ell }(u)\le \mathrm{\ell }(v)$; the induction hypothesis therefore makes both sums vanish and $\mathrm{\Phi }(B)=0$. If $u\nleqq v^{\mathrm{\prime }}$, then no element $z$ of $[u^{\mathrm{\prime }},v^{\mathrm{\prime }}]$ satisfies $u\le z$ (else $u\le z\le v^{\mathrm{\prime }}$), so $B=[u^{\mathrm{\prime }},v^{\mathrm{\prime }}]$; here $u^{\mathrm{\prime }}\le v^{\mathrm{\prime }}$ because $u^{\mathrm{\prime }}\in B$, as $u^{\mathrm{\prime }}\in [u^{\mathrm{\prime }},v]$ and $u\nleqq u^{\mathrm{\prime }}$, and $B\subseteq [u^{\mathrm{\prime }},v^{\mathrm{\prime }}]$ was shown above, while $u^{\mathrm{\prime }}<v^{\mathrm{\prime }}$ by the length computation, so the induction hypothesis gives $\mathrm{\Phi }(B)=\mathrm{\Phi }(u^{\mathrm{\prime }},v^{\mathrm{\prime }})=0$.

The cancellation formula. We prove $\mathrm{\Phi }(a,b)={\delta }_{a,b}(-1{)}^{\mathrm{\ell }(a)}$ for all $a\le b$ by induction on $\mathrm{\ell }(a)+\mathrm{\ell }(b)$: the base case $a=b$ has the single term $(-1{)}^{\mathrm{\ell }(a)}$, and for $a<b$ the pair $(a,b)$ falls into Case 1 or Case 2 above according to the signs of $\mathrm{\ell }(as)$ and $\mathrm{\ell }(bs)$, where $s$ is a right descent of $b$, so steps 1.1 and 1.2 give $\mathrm{\Phi }(a,b)=0$; the intervals are finite by [F5] and a finite set has a cardinality [F8]. This is the first formulation of (i); multiplying the equality by $(-1{)}^{\mathrm{\ell }(v)}$ gives the form with $(-1{)}^{\mathrm{\ell }(v)-\mathrm{\ell }(x)}$, since $(-1{)}^{\mathrm{\ell }(v)+\mathrm{\ell }(x)}=(-1{)}^{\mathrm{\ell }(v)-\mathrm{\ell }(x)}$ and ${\delta }_{u,v}(-1{)}^{\mathrm{\ell }(v)+\mathrm{\ell }(u)}={\delta }_{u,v}$, and when $u<v$ it says that the numbers of even-length and of odd-length elements agree.

The Möbius function. Define $\nu (a,b):=(-1{)}^{\mathrm{\ell }(b)-\mathrm{\ell }(a)}$ for $a\le b$; then $\nu (a,a)=1$ and, for $u<v$, ${\sum }_{u\le z\le v}\nu (u,z)=(-1{)}^{-\mathrm{\ell }(u)}{\sum }_{u\le z\le v}(-1{)}^{\mathrm{\ell }(z)}=0$ by step 2.1, so ${\sum }_{u\le z<v}\nu (u,z)=-\nu (u,v)$ and $\nu$ satisfies the recurrence characterising the Möbius function of the interval [F6]; since that recurrence determines $\mu$ uniquely interval by interval [F7], $\mu (u,v)=\nu (u,v)=(-1{)}^{\mathrm{\ell }(v)-\mathrm{\ell }(u)}$, which is (ii).

The falling-chain count. By [F10] the deleted-position labeling satisfies (N) and (L) on every rooted interval of $[u,v]$, and by [F11] and [F5] the interval $[u,v]$ is finite and graded; hence the falling-chain formula [F9] applies to the rooted interval $([u,v],(v))$, whose root consists of the single vertex $v$ and has zero edges, and gives $\mu (u,v)=(-1{)}^{\mathrm{\ell }(v)-\mathrm{\ell }(u)}\cdot \mathrm{\#}\{\text{strictly falling maximal chains of }[u,v]\}$. Comparing with step 3.1 shows that $[u,v]$ has exactly one strictly falling maximal chain, and conversely the count one reproduces (ii); this is (iii).

Scope. Steps 1.1, 1.2, 2.1, 3.1 and 4.1 use only the interval $[u,v]\subseteq W$, the lifting property [F1] and the length parity [F2]; the quotient enters only through [F14], which records that the quotient order is the restriction of the Bruhat order and asserts no fullness of quotient intervals, so the sign formula is not transferred to intervals of a proper parabolic quotient $W^I$: there the fullness of the interval is an additional hypothesis, and the companion page exhibits a quotient interval for which the formula fails. This is (iv).