Bruhat intervals of rank two are diamonds

Right lifting. Let $s$ be a simple reflection and $x\le y$ with $ys<y$ and $xs>x$. Then $x\le ys$ and $xs\le y$. Indeed, choose a reduced expression $y=s_1\cdots s_q$ ending in $s$, which exists because $ys<y$; by the subword characterisation in [F1], $x$ has a reduced subword expression inside $s_1\cdots s_q$. That subword cannot use the last letter: if it did, then $x=x^{\mathrm{\prime }}s$ with $\mathrm{\ell }(x)=\mathrm{\ell }(x^{\mathrm{\prime }})+1$ and thus $xs=x^{\mathrm{\prime }}$ has length $\mathrm{\ell }(x)-1$, contradicting $xs>x$. Hence $x$ is a reduced subword of $s_1\cdots s_{q-1}$, which is a reduced expression for $ys$, so $x\le ys$. Adjoining the last letter to a reduced subword for $x$ gives a reduced expression of length $\mathrm{\ell }(x)+1=\mathrm{\ell }(xs)$ for $xs$, so $xs\le y$.

Three consequences of step 1.1 are used below. (a) If $x\le y$ and $xs<x$, then $xs\le y$ since $xs<x\le y$. (b) If $x\le y$, $xs<x$ and $ys<y$, then $xs\le ys$: apply (a) to get $xs\le y$, then apply step 1.1 to the pair $xs\le y$, whose right products are $(xs)s=x>xs$ and $ys<y$. (c) If $x\le y$, $xs>x$ and $ys>y$, then $xs\le ys$, which is the order-preservation statement in [F1].

Main claim, case $ys>y$. Let $y<x$ with $\mathrm{\ell }(x)=\mathrm{\ell }(y)+2$. By [F2] choose a simple reflection $s$ with $xs<x$, and put $x_0=xs$, $y_0=ys$; then $\mathrm{\ell }(x_0)=\mathrm{\ell }(x)-1=\mathrm{\ell }(y)+1$ and $\mathrm{\ell }(y_0)=\mathrm{\ell }(y)\pm 1$. Assume first that $ys>y$, so $y_0>y$. Step 1.1 applied to $y\le x$ gives $y\le x_0$ and $y_0\le x$. Hence $y_0⊳y$ and $y_0\le x$ with $\mathrm{\ell }(x)=\mathrm{\ell }(y_0)+1$ give $x⊳y_0$; similarly $x_0⊳y$ and $x⊳x_0$. Thus $y_0$ and $x_0$ are two distinct elements between $y$ and $x$. Conversely, let $m$ be any element with $y<m<x$. If $ms>m$, step 1.1 applied to $m\le x$ gives $m\le x_0$, and $\mathrm{\ell }(m)=\mathrm{\ell }(y)+1=\mathrm{\ell }(x_0)$ forces $m=x_0$. If $ms<m$, step 1.1 applied to $y\le m$ gives $y_0\le m$, and $\mathrm{\ell }(y_0)=\mathrm{\ell }(y)+1=\mathrm{\ell }(m)$ forces $m=y_0$. Hence the interval is exactly $\{y,y_0,x_0,x\}$.

Main claim, case $ys<y$; reduction. Now assume $ys<y$, so $y_0=ys$. By consequence (b) of step 2.1 applied to $y\le x$, we get $y_0\le x_0$, and $\mathrm{\ell }(x_0)-\mathrm{\ell }(y_0)=\mathrm{\ell }(x)-\mathrm{\ell }(y)=2$; since $y_0\mathrm{\ne }{x}_0$ we may apply the induction hypothesis (strong induction on $\mathrm{\ell }(x)$) to the pair $y_0<x_0$: its interval has exactly two elements $n_1,n_2$, with $x_0⊳n_i⊳y_0$. This is the induction step: we analyse the elements between $y$ and $x$. Every such $m$ satisfies $ms\mathrm{\ne }m$; if $ms>m$, step 1.1 applied to $m\le x$ gives $m\le x_0$, and $\mathrm{\ell }(m)=\mathrm{\ell }(y)+1=\mathrm{\ell }(x_0)$ gives $m=x_0$. If $ms<m$, then $n:=ms$ satisfies $y_0\le n$ and $n\le x_0$ by the two applications of consequence (b) to $y\le m$ and $m\le x$, and $\mathrm{\ell }(n)=\mathrm{\ell }(m)-1=\mathrm{\ell }(y_0)+1$, so $n\in \{n_1,n_2\}$; moreover $ns=m>n$. Conversely, if $n\in \{n_1,n_2\}$ and $ns>n$, then $m:=ns$ satisfies $y\le m$ and $m\le x$ by the two applications of consequence (c) to $y_0\le n$ and $n\le x_0$, and $\mathrm{\ell }(m)=\mathrm{\ell }(n)+1=\mathrm{\ell }(y)+1$, so $x⊳m⊳y$. Thus the elements between $y$ and $x$ are exactly $x_0$ (if it lies between, i.e. if $y\le x_0$) together with the elements $ns$ for those $n\in \{n_1,n_2\}$ with $ns>n$.

Case $ys<y$ and $y\le x_0$. Then $x_0$ lies between $y$ and $x$. The element $y$ itself is a middle of the interval $y_0<x_0$: indeed $y⊳y_0$ (case hypothesis), $y\le x_0$ and $\mathrm{\ell }(x_0)=\mathrm{\ell }(y)+1$, so $x_0⊳y$. As $y=ys\cdot s=y_{0}s$ does not rise under $s$, at least one of $n_1,n_2$ fails to rise. If the other one, say $n$, also failed to rise, then step 1.1 applied to $y_0\le n$ would give $y=y_{0}s\le n$ with $\mathrm{\ell }(y)=\mathrm{\ell }(n)$, so $y=n$, contradiction. Hence exactly one of $n_1,n_2$ rises, and by step 3.1 the interval between $y$ and $x$ consists of $x_0$ and that one element $ns$: exactly two elements.

Case $ys<y$ and $y\nleqq x_0$. Then $x_0$ is not between $y$ and $x$. If some $n\in \{n_1,n_2\}$ failed to rise, then step 1.1 applied to $y_0\le n$ would give $y=y_{0}s\le n$ with $\mathrm{\ell }(y)=\mathrm{\ell }(n)$, hence $y=n$, and then $y\le x_0$ because $n\le x_0$—contrary to the case hypothesis. Therefore both $n_1,n_2$ rise, and step 3.1 exhibits exactly the two elements $n_{1}s,n_{2}s$ between $y$ and $x$.

The two cases of steps 2.2 and 3.1 (with the sub-cases resolved in steps 4.1 and 4.2) cover all possibilities for $y<x$ with $\mathrm{\ell }(x)=\mathrm{\ell }(y)+2$, and in each the set $\{m:y<m<x\}$ has exactly two elements. The base case of the induction is $\mathrm{\ell }(x)=2$, $\mathrm{\ell }(y)=0$, where $y=1$ and the hypothesis $ys>y$ of step 2.2 holds for every simple $s$, so step 2.2 applies; the induction step uses only the pair $y_0<x_0$ with $\mathrm{\ell }(x_0)=\mathrm{\ell }(x)-1<\mathrm{\ell }(x)$. Since every element strictly between $y$ and $x$ has length $\mathrm{\ell }(y)+1=\mathrm{\ell }(x)-1$ (the chain description of [F1] forces length to increase by one along any saturated chain), each such element is a cover of $y$ and is covered by $x$, and $[y,x]=\{y,m_1,m_2,x\}$.