The rank-two half-space alternative and the chamber-length induction $(P_n)$, $(Q_n)$

Set-up. For the rank-two calculation fix $s\mathrm{\ne }t$ in $S$ and adopt the notation of [F1] and [F3]. For $r\in S$ the sets $B_r=\{f\in V^{\ast }:f(e_r)>0\}$ and $r{B}_r=\{f\in V^{\ast }:f(e_r)<0\}$ are disjoint and $C^{\circ }={\bigcap }_{r\in S}{B}_r$; the dual action satisfies $v(B_s\cap B_t)=\{v\cdot f:f\in B_s\cap B_t\}$, and the action of $v\in W_{s,t}$ on $V^{\ast }$ is linear. By [F5] the intrinsic length satisfies ${\mathrm{\ell }}_{s,t}(x)=\mathrm{\ell }(x)$ for $x\in W_{s,t}$.

Reduction to the rank-two plane. Put $C_P^{\circ }:=\{g\in P^{\ast }:g(e_s)>0,g(e_t)>0\}$ and let $\pi :V^{\ast }\to P^{\ast }$, $\pi (f):=f{\mathrm{\mid }}_P$. Then $\pi$ is linear and surjective, because a functional prescribed on $P$ extends to a functional on $V$ by $0$ on the remaining basis vectors. Every $v\in W_{s,t}$ preserves $P$ and fixes $P^{\perp }$ pointwise by [F1], so for $x\in P$ and $f\in V^{\ast }$ one has $(v\cdot f)(x)=f(\rho (v{)}^{-1}x)$ with $\rho (v{)}^{-1}x\in P$; hence $\pi (v\cdot f)=v\cdot \pi (f)$ and ${\pi }^{-1}(C_P^{\circ })=B_s\cap B_t$, ${\pi }^{-1}\{g:g(e_{s^{\mathrm{\prime }}})>0\}=B_{s^{\mathrm{\prime }}}$, ${\pi }^{-1}\{g:g(e_{s^{\mathrm{\prime }}})<0\}=s^{\mathrm{\prime }}{B}_{s^{\mathrm{\prime }}}$ for $s^{\mathrm{\prime }}\in \{s,t\}$. Consequently $v(B_s\cap B_t)\subseteq B_{s^{\mathrm{\prime }}}$ if and only if $v{C}_P^{\circ }\subseteq \{g:g(e_{s^{\mathrm{\prime }}})>0\}$, and $v(B_s\cap B_t)\subseteq s^{\mathrm{\prime }}{B}_{s^{\mathrm{\prime }}}$ if and only if $v{C}_P^{\circ }\subseteq \{g:g(e_{s^{\mathrm{\prime }}})<0\}$.

Sectors avoid the walls. By [F4] the interiors of the chambers $w{C}_P$ $(w\in W_{s,t})$ are convex open cones that are connected components of the complement of the union of the root lines in $P^{\ast }$ (respectively in $\{f\in P^{\ast }:f(e_s+e_t)>0\}$ when $m(s,t)=\mathrm{\infty }$), so each is disjoint from every root line $H_{\beta }\cap P^{\ast }$ $(\beta \in {\mathrm{\Phi }}_P)$, and $H_{e_s}\cap P^{\ast }$, $H_{e_t}\cap P^{\ast }$ are root lines because $e_s,e_t\in {\mathrm{\Phi }}_P$. An open convex set disjoint from a line lies in exactly one of the two open half-planes bounded by it. Hence for every $v\in W_{s,t}$ and $s^{\mathrm{\prime }}\in \{s,t\}$ exactly one of $v{C}_P^{\circ }\subseteq \{g:g(e_{s^{\mathrm{\prime }}})>0\}$ and $v{C}_P^{\circ }\subseteq \{g:g(e_{s^{\mathrm{\prime }}})<0\}$ holds.

The finite dihedral group. Assume $m:=m(s,t)<\mathrm{\infty }$ and write $u:=st$. Since $u^m=1$ by [F5], the set $\{u_0,\dots ,u_{2m-1}\}$ is closed under right multiplication by $s$ and $t$: indeed $u_{2j}s=u_{2j+1}$ and $u_{2j+1}s=u_{2j}$ for $2j<2m$; $u_{2j}t=u_{2j-1}$ for $j\ge 1$; $u_{0}t=u_{2m-1}$ because $(st{)}^{m-1}s=(st{)}^{-1}s=(ts)s=t$; and $u_{2j+1}t=u_{2j+2}$ for $2j+1<2m$, $u_{2m-1}t=1$. Since $W_{s,t}$ is generated by $s,t$ and contains $1$, it equals $\{u_0,\dots ,u_{2m-1}\}$. The $u_k$ are pairwise distinct: if $u_j=u_k$ with $j<k<2m$, then $1=u_j^{-1}{u}_k$; for $j,k$ of equal parity this equals $u^{\pm (k-j)\mathrm{/}2}$ with $0<(k-j)\mathrm{/}2<m$, contradicting the exact order $m$ of $u$ from [F5], while for parities differing it equals $s{u}^p$ or $u^{p}s$ with $2\mathrm{\mid }p\mathrm{\mid }<2m$, so it would give $u^p=s$, impossible because $\mathrm{sgn}(u^p)=1$ while $\mathrm{sgn}(s)=-1$. Hence $\mathrm{\mid }{W}_{s,t}\mathrm{\mid }=2m$, the $u_k$ are distinct, $u_{k+2m}=u_k$, and the pairs $u_k,u_{k+1}$ and $u_{2m-1},u_0$ are edges of the Cayley graph of $W_{s,t}$ for the generating set $\{s,t\}$. That graph is connected, and every vertex has degree exactly $2$ because $x\mathrm{\ne }xs$ and $xs\mathrm{\ne }xt$ for all $x$ (as $s\mathrm{\ne }1$ and $s\mathrm{\ne }t$ by [F5]); it therefore is the displayed $2m$-cycle, so ${\mathrm{\ell }}_{s,t}(u_k)=\min (k,2m-k)$ is the graph distance from $u_0$. Moreover $s{u}_k=u_{\sigma (k)}$ and $t{u}_k=u_{\tau (k)}$ with $\sigma (k)\equiv 1-k(\mathrm{m}\mathrm{o}\mathrm{d}2m)$ and $\tau (k)\equiv -1-k(\mathrm{m}\mathrm{o}\mathrm{d}2m)$ for $0\le k<2m$: these are $s(st{)}^j=u^{-j}s$, $t(st{)}^j=u^{-j}t=u^{-j-1}s$ applied to $u_{2j}=u^j$ and $u_{2j+1}=u^{j}s$, together with the case $k=0$.

The infinite dihedral group. Assume $m(s,t)=\mathrm{\infty }$, write $u:=st$, and let $u_k^{\mathrm{\prime }}$ be the alternating word of length $k$ beginning with $t$. By [F5], $u$ has infinite order, and by [F6] ${\mathrm{\ell }}_{s,t}(u_k)=k={\mathrm{\ell }}_{s,t}(u_k^{\mathrm{\prime }})$ for all $k\ge 0$. The union $X:=\{u_k:k\ge 0\}\cup \{u_k^{\mathrm{\prime }}:k\ge 0\}$ is closed under right multiplication by $s$ and $t$ ($u_{2j}s=u_{2j+1}$, $u_{2j+1}s=u_{2j}$, $u_{2j}t=u_{2j-1}$ for $j\ge 1$, $u_{0}t=u_1^{\mathrm{\prime }}$, $u_{2j+1}t=u_{2j+2}$, symmetrically for $u_k^{\mathrm{\prime }}$), so $X=W_{s,t}$; by [F6] the elements $u_k$ are pairwise distinct with ${\mathrm{\ell }}_{s,t}(u_k)=k$ for every $k\ge 0$, and likewise the $u_k^{\mathrm{\prime }}$. The Cayley graph of $W_{s,t}$ for $\{s,t\}$ is connected, and every vertex has degree exactly $2$ (as in 1.4), so it is the two-way infinite path $\cdots u_2^{\mathrm{\prime }},u_1^{\mathrm{\prime }},1,u_1,u_2\cdots$, and the graph distance from $1$ to $u_k$, or to $u_k^{\mathrm{\prime }}$, equals ${\mathrm{\ell }}_{s,t}$ of that element, namely $k$. On the affine line $\{f\in P^{\ast }:f(e_s+e_t)=1\}$, parametrized by $y_s$, the generators act by $s:y_s\mapsto -y_s$ and $t:y_s\mapsto 2-y_s$ by [F3] (here $c=1$); consequently the affine map of $u_k$ is $y_s\mapsto y_s-2j$ for $k=2j$ and $y_s\mapsto -y_s-2j$ for $k=2j+1$, and that of $u_k^{\mathrm{\prime }}$ is $y_s\mapsto y_s+2j$ for $k=2j$ and $y_s\mapsto -y_s+2j+2$ for $k=2j+1$, by induction on $k$ (each step composes with $s$ or $t$ alternately). Hence the trace of $u_k{C}_P^{\circ }$ is the interval $(-k,-k+1)$ and that of $u_k^{\mathrm{\prime }}{C}_P^{\circ }$ is $(k,k+1)$. Since these intervals are pairwise distinct, an element of $W_{s,t}=X$ is determined by the trace of its chamber. Writing $v_j$ $(j\in \mathbb{Z})$ for the element with trace $(j,j+1)$, namely $v_j=u_{-j}$ for $j\le 0$ and $v_j=u_j^{\mathrm{\prime }}$ for $j\ge 0$, one therefore has ${\mathrm{\ell }}_{s,t}(v_j)=\mathrm{\mid }j\mathrm{\mid }$ together with $s\cdot v_j=v_{-j-1}$ and $t\cdot v_j=v_{1-j}$, because the affine maps send the interval $(j,j+1)$ to $(-j-1,-j)$, respectively $(1-j,2-j)$.

Signs in the infinite case. In the situation of 1.5 the sign of $y_s$ on $v_j{C}_P^{\circ }$ is the sign of $y_s$ on the interval $(j,j+1)$, hence negative exactly when $j\le -1$, and the sign of $y_t=1-y_s$ is negative exactly when $j\ge 1$.

(P_0) and (Q_0). For $w=1$ one has $\mathrm{\ell }(w)=0$, $w{C}^{\circ }=C^{\circ }\subseteq B_r$ for every $r\in S$ by 1.1, and choosing $u=1$ gives $C^{\circ }\subseteq B_s\cap B_t$ and $\mathrm{\ell }(1)=0={\mathrm{\ell }}_{s,t}(1)+\mathrm{\ell }(1)$ for all $s\mathrm{\ne }t$.

Signs of the finite sectors. In the finite case let $C_k:=u_k{C}_P^{\circ }$ $(0\le k<2m)$; by [F4] these are the interiors of all $2m$ sectors. Consecutive $u_k$ differ by right multiplication by a generator $r$, so $u_k{C}_P$ and $u_{k}r{C}_P$ share the image under $u_k$ of the wall of $C_P$ fixed by $r$ and lie on its opposite sides, by [F3]. They are adjacent sectors. The distinct vertices of the Cayley cycle in 1.4 therefore list the sectors in cyclic order. The sign of $y_s$ is constant on each $C_k$ (no $C_k$ meets the line $y_s=0$ by 1.3), is $+$ on $C_0$, and is $-$ on $C_1=s{C}_P^{\circ }$ because $s$ negates $y_s$ by [F3]. It changes exactly at those transitions whose common boundary ray lies on the line $y_s=0$: that line contains exactly two boundary rays of the arrangement, hence exactly two transitions; and the involution $s$ maps each sector to the sector on the opposite side of $y_s=0$ and fixes no sector, because $s$ swaps the two half-planes and no sector meets the wall. Hence exactly $m$ sectors lie on each side, and the negative side is the contiguous block of $m$ sectors containing $C_1$ but not $C_0$, that is $\{k:y_s<0\text{ on }{C}_k\}=\{1,\dots ,m\}$. Applying the same argument to $t$, which is $u_{2m-1}$ and negates $y_t$, gives $\{k:y_t<0\text{ on }{C}_k\}=\{m,\dots ,2m-1\}$.

Descents in the infinite case. In the situation of 1.5, let $v=v_j$ be the element with trace $(j,j+1)$; by 1.5, ${\mathrm{\ell }}_{s,t}(v)=\mathrm{\mid }j\mathrm{\mid }$ and ${\mathrm{\ell }}_{s,t}(sv)=\mathrm{\mid }j+1\mathrm{\mid }$, so ${\mathrm{\ell }}_{s,t}(sv)={\mathrm{\ell }}_{s,t}(v)-1$ exactly when $j\le -1$, which by 1.6 is exactly the side $y_s<0$; and ${\mathrm{\ell }}_{s,t}(tv)=\mathrm{\mid }j-1\mathrm{\mid }$, so ${\mathrm{\ell }}_{s,t}(tv)={\mathrm{\ell }}_{s,t}(v)-1$ exactly when $j\ge 1$, exactly the side $y_t<0$. In particular no element has both left descents, and ${\mathrm{\ell }}_{s,t}(u_k)=k$ for all $k\ge 0$ with the $u_k$ pairwise distinct.

The dichotomy in the original space. Combining 1.2 with 1.3: for every $v\in W_{s,t}$ and $s^{\mathrm{\prime }}\in \{s,t\}$ exactly one of $v(B_s\cap B_t)\subseteq B_{s^{\mathrm{\prime }}}$ and $v(B_s\cap B_t)\subseteq s^{\mathrm{\prime }}{B}_{s^{\mathrm{\prime }}}$ holds, according to the side of $H_{e_{s^{\mathrm{\prime }}}}\cap P^{\ast }$ carrying $v{C}_P^{\circ }$.

Descents in the finite case. Let $m(s,t)<\mathrm{\infty }$ and $v=u_k$ $(0\le k<2m)$. By 1.4, ${\mathrm{\ell }}_{s,t}(s{u}_k)$ equals the distance from $0$ to $\sigma (k)\equiv 1-k$, namely $k-1$ when $1\le k\le m$ and $2m+1-k$ when $m<k<2m$, and equals $1$ when $k=0$; comparing with ${\mathrm{\ell }}_{s,t}(u_k)=\min (k,2m-k)$ gives ${\mathrm{\ell }}_{s,t}(s{u}_k)={\mathrm{\ell }}_{s,t}(u_k)-1$ exactly for $1\le k\le m$. Likewise ${\mathrm{\ell }}_{s,t}(t{u}_k)={\mathrm{\ell }}_{s,t}(u_k)-1$ exactly for $m\le k\le 2m-1$, and ${\mathrm{\ell }}_{s,t}(t{u}_k)={\mathrm{\ell }}_{s,t}(u_k)+1$ for $0\le k<m$. Hence, by 2.1, the left descent for $s$ occurs exactly on the side $y_s<0$ and the left descent for $t$ exactly on the side $y_t<0$, and $u_m$ is the unique element with both descents.

Part (1). Let $v\in W_{s,t}$ and $s^{\mathrm{\prime }}\in \{s,t\}$. The dichotomy is 2.3, and its two alternatives correspond to the signs of $y_{s^{\mathrm{\prime }}}$ on $v{C}_P^{\circ }$. If $m(s,t)<\mathrm{\infty }$ then $v=u_k$ for a unique $k$ by 1.4 and ${\mathrm{\ell }}_{s,t}(u_k)=\min (k,2m-k)$; the negative side alternative holds exactly for $k\in \{1,\dots ,m\}$ when $s^{\mathrm{\prime }}=s$ and for $k\in \{m,\dots ,2m-1\}$ when $s^{\mathrm{\prime }}=t$ by 2.1, and exactly there $s^{\mathrm{\prime }}v$ shortens by 3.1; the elements $u_0,\dots ,u_{2m-1}$ exhaust $W_{s,t}$, and the unique double-descent element is $u_m$. If $m(s,t)=\mathrm{\infty }$ then every $v$ has a trace $(j,j+1)$ and ${\mathrm{\ell }}_{s,t}(u_k)=k$ with the $u_k$ pairwise distinct by 2.2; the negative side alternative for $s^{\mathrm{\prime }}$ holds exactly for $j\le -1$ (respectively $j\ge 1$), and exactly there $s^{\mathrm{\prime }}v$ shortens by 2.2, and no element has both descents. This proves all clauses of (1) in both cases.

The conditional step for $(\mathrm{P})$. Fix $n\ge 0$ and suppose only $({\mathrm{Q}}_n)$. If $S$ is empty there is no $s$ to check. If $S=\{s\}$ then $W=\{1,s\}$ by $s^2=1$ and [F5], and the only positive-length chamber is $s{C}^{\circ }\subseteq s{B}_s$, with $\mathrm{\ell }(s)=1$, proving $({\mathrm{P}}_{n+1})$ directly. Now suppose $\mathrm{\mid }S\mathrm{\mid }\ge 2$. First $({\mathrm{Q}}_n)$ and (1) imply $({\mathrm{P}}_n)$: for any $a$ of length $n$ and generator $r$, choose $q\mathrm{\ne }r$ and use $({\mathrm{Q}}_n)$ to write $a=ud$, with $a{C}^{\circ }\subseteq u(B_r\cap B_q)$ and $n={\mathrm{\ell }}_{r,q}(u)+\mathrm{\ell }(d)$. The rank-two dichotomy gives the positive alternative or the negative alternative with ${\mathrm{\ell }}_{r,q}(ru)={\mathrm{\ell }}_{r,q}(u)-1$; in the latter case $\mathrm{\ell }(ra)\le {\mathrm{\ell }}_{r,q}(ru)+\mathrm{\ell }(d)=n-1$, hence equality by [F5]. This is $({\mathrm{P}}_n)$. Let $w\in W$ with $\mathrm{\ell }(w)=n+1$ and let $s\in S$; choose $t$ with $w=t{w}^{\mathrm{\prime }}$ and $\mathrm{\ell }(w^{\mathrm{\prime }})=n$. If $s=t$, then $({\mathrm{P}}_n)$ applied to $w^{\mathrm{\prime }}$ gives $w^{\mathrm{\prime }}{C}^{\circ }\subseteq B_s$: the second alternative would give $\mathrm{\ell }(s{w}^{\mathrm{\prime }})=\mathrm{\ell }(w^{\mathrm{\prime }})-1=n-1$, whereas $\mathrm{\ell }(s{w}^{\mathrm{\prime }})=\mathrm{\ell }(w)=n+1$ here. Hence $w{C}^{\circ }=t(w^{\mathrm{\prime }}{C}^{\circ })\subseteq t{B}_s=s{B}_s$ and $\mathrm{\ell }(sw)=\mathrm{\ell }(w^{\mathrm{\prime }})=n=\mathrm{\ell }(w)-1$, the second alternative of $({\mathrm{P}}_{n+1})$. If $s\mathrm{\ne }t$, apply $({\mathrm{Q}}_n)$ to $w^{\mathrm{\prime }}$: there is $u\in W_{s,t}$ with $w^{\mathrm{\prime }}{C}^{\circ }\subseteq u(B_s\cap B_t)$ and $\mathrm{\ell }(w^{\mathrm{\prime }})={\mathrm{\ell }}_{s,t}(u)+\mathrm{\ell }(u^{-1}{w}^{\mathrm{\prime }})$. Put $v:=tu\in W_{s,t}$. If $v(B_s\cap B_t)\subseteq B_s$, then $w{C}^{\circ }\subseteq tu(B_s\cap B_t)\subseteq B_s$. Otherwise $v(B_s\cap B_t)\subseteq s{B}_s$ and ${\mathrm{\ell }}_{s,t}(sv)={\mathrm{\ell }}_{s,t}(v)-1$ by (1) from 4.1, so with $d:=u^{-1}{w}^{\mathrm{\prime }}$ one has $w{C}^{\circ }\subseteq s{B}_s$ and $\mathrm{\ell }(sw)=\mathrm{\ell }(stud)\le {\mathrm{\ell }}_{s,t}(stu)+\mathrm{\ell }(d)={\mathrm{\ell }}_{s,t}(v)-1+\mathrm{\ell }(d)\le {\mathrm{\ell }}_{s,t}(u)+\mathrm{\ell }(d)=\mathrm{\ell }(w^{\mathrm{\prime }})=\mathrm{\ell }(w)-1$, where ${\mathrm{\ell }}_{s,t}(tu)\le 1+{\mathrm{\ell }}_{s,t}(u)$ follows by prepending $t$ to a shortest word for $u$. The reverse bound $\mathrm{\ell }(sw)\ge \mathrm{\ell }(w)-1$ follows from [F5], so $\mathrm{\ell }(sw)=\mathrm{\ell }(w)-1$, the second alternative of $({\mathrm{P}}_{n+1})$.

The conditional step for $(\mathrm{Q})$. Suppose $({\mathrm{Q}}_n)$ and $({\mathrm{P}}_m)$ for all $m\le n+1$, as in the second conditional implication of (2), and let $w\in W$ with $\mathrm{\ell }(w)=n+1$ and $s\mathrm{\ne }t$. By [F5] factor $w=ud$ with $u\in W_{s,t}$ and $d$ the minimal representative of $W_{s,t}w$; then $\mathrm{\ell }(w)=\mathrm{\ell }(u)+\mathrm{\ell }(d)$ and $\mathrm{\ell }(s^{\mathrm{\prime }}d)>\mathrm{\ell }(d)$ for $s^{\mathrm{\prime }}\in \{s,t\}$. Since $\mathrm{\ell }(d)\le n+1$, $({\mathrm{P}}_{\mathrm{\ell }(d)})$ is available: it is part of the stated supposition. Applying it to $d$ and $s^{\mathrm{\prime }}\in \{s,t\}$, the second alternative would give $\mathrm{\ell }(s^{\mathrm{\prime }}d)=\mathrm{\ell }(d)-1$, contradicting $\mathrm{\ell }(s^{\mathrm{\prime }}d)>\mathrm{\ell }(d)$; hence $d{C}^{\circ }\subseteq B_s\cap B_t$. Therefore $w{C}^{\circ }=u(d{C}^{\circ })\subseteq u(B_s\cap B_t)$ and $\mathrm{\ell }(w)=\mathrm{\ell }(u)+\mathrm{\ell }(d)={\mathrm{\ell }}_{s,t}(u)+\mathrm{\ell }(u^{-1}w)$, which is $({\mathrm{Q}}_{n+1})$.

The induction. $({\mathrm{P}}_0)$ and $({\mathrm{Q}}_0)$ hold by 1.7, and 5.1 and 6.1 show that the validity of $({\mathrm{P}}_m)$ and $({\mathrm{Q}}_m)$ for all $m\le n$ implies $({\mathrm{P}}_{n+1})$ and $({\mathrm{Q}}_{n+1})$, for every $n\ge 0$. By the induction principle [F7], $({\mathrm{P}}_n)$ and $({\mathrm{Q}}_n)$ hold for every $n\ge 0$.