Basic properties of the Bruhat order on $S_n$

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.