4. Subsystems of root systems

Here we define subsystems of root systems and prove necessary facts about them. Unlike for groups, rings, etc. it's pretty tough to prove a subset closed under the operation is itself a root system. Though an equivalent statement is given as an exercise in the text Combinatorics of Coxeter groups, so are some unsolved problems, and the equivalent statement was the main result of Matthew Dyer's dissertation.

Definition 1: Let $(R,B)$ be a root system. A subset $U\subseteq R$ is called a subsystem if it is closed under the operation $\ast$ in $R$. Define $$B_R(U)=\{x\in R^+(B)\cap U|x\ast y\in R^+(B)\mbox{ for all }y\in R^+(B)\cap U\mbox{ with }x\neq y\}$$ We will be showing below that $B_R(U)$ forms a basis for $U$, though it's not even clear that $B_R(U)$ is nonempty. Define also for $x\in R$ and $U\subseteq R$ $$x\ast U=\{x\ast y|y\in U\}$$ Intuitively this is a "translation" of a subsystem by a root. We've been using this notation already for inversion sets. Note that $y\mapsto x\ast y$ is a bijection between $U$ and $x\ast U$, and since $(x\ast y)\ast (x\ast z)=x\ast (y\ast z)$ we have that $x\ast U$ is a subsystem of $R$. You may wish to verify that if $x\in U$ then $x\ast U=U$.



Lemma 4.1: If $(R,B)$ is a root system, $U\subseteq R$ is a subsystem, and $x\in B-U$ then $$B_R(x\ast U)=x\ast B_R(U)$$ and $$R^+(B_R(x\ast U))=x\ast R^+(B_R(U))$$
Proof: First we prove that $B_R(x\ast U)=x\ast B_R(U)$. Note that $x\notin x\ast U$. Suppose $y\in B_R(x\ast U)$. Then for all $z\in R^+(B)\cap (x\ast U)$ such that $y\neq z$ we have that $y\ast z\in R^+(B)\cap U$. Since $x\in B$ and $x\notin U$, $x\neq y,z$ and hence $x\ast (y\ast z)=(x\ast y)\ast (x\ast z)\in R^+(B)\cap U$. Thus $x\ast y\in B_R(U)$, hence $y\in x\ast B_R(U)$. Thus $B_R(x\ast U)\subseteq x\ast B_R(U)$.

Suppose conversely that $y\in x\ast B_R(U)$. Then for all $z\in R^+(B)\cap U$ with $z\neq x\ast y$ we have that $(x\ast y)\ast z \in R^+(B)\cap U$, hence $x\ast ((x\ast y)\ast z)=y\ast (x\ast z)\in R^+(B)\cap (x\ast U)$. Thus $y\in B_R(x\ast U)$, and the result follows.

Now note that $R^+(B_R(x\ast U))$ is the smallest set satisfying $B_R(x\ast U)=x\ast B_R(U)\subseteq R^+(B_R(x\ast U))$ and if $y\in R^+(B_R(x\ast U))$ and $x'\in x\ast B_R(U)$ are such that $x'\neq y$, then $x'\ast y\in R^+(B_R(x\ast U))$. Since $x\ast (y\ast z)=(x\ast y)\ast (x\ast z)$, we see that the bijection $y\mapsto x\ast y$ preserves these properties, thus $x\ast R^+(B_R(x\ast U))=R^+(B_R(U))$. The result follows. $\square$

The following theorem is essentially the main result of Dyer's dissertation (Reflection subgroups of Coxeter systems, Journal of Algebra 135 (1), 1990, 57-73).

Theorem 4.2: Let $(R,B)$ be a root system and let $U\subseteq R$ be a subsystem. Then $(U,B_R(U))$ is a root system and $$R^+(B_R(U))=R^+(B)\cap U$$
Proof: The theorem follows if we prove that $R^+(B_R(U))=R^+(B)\cap U$. It is an easy consequence of the definition of $B_R(U)$ that $R^+(B_R(U))\subseteq R^+(B)\cap U$. We prove that the reverse inclusion holds. Suppose $y\in R^+(B)\cap U$. Let $y=w(x)$ for $w\in W(R)$ and $x\in B$ with $\ell(w)$ minimal. We prove by induction on $\ell(w)$ that $y\in R^+(B_R(U))$. If $\ell(w)=0$, then $y\in B$, hence $y\in B_R(U)$, so $y\in R^+(B_R(U))$. Otherwise let $x'\in B$ be such that $\ell(s_{x'}w) < \ell(w)$. If $x'\in U$, then since $x'\ast y=s_{x'}w(x)$ and $\ell(s_{x'}w) < \ell(w)$ we have by the induction hypothesis that $x'\ast y\in R^+(B_R(U))$, hence the same is true of $y=x'\ast(x'\ast y)$. If $x'\notin U$, then $x'\ast y\in x'\ast U$ and by the induction hypothesis $x'\ast y\in R^+(B_R(x'\ast U))=R^+(x'\ast B_R(U))=x'\ast R^+(B_R(U))$ (the equalities by Lemma 4.1), so $y=x'\ast (x'\ast y)\in R^+(B_R(U))$. The result follows by induction. $\square$

We need to know now that $W(U)$ can be naturally treated as a subgroup of $W(R)$. For $x\in U$ define $s_x^U:U\to U$ to be the corresponding reflection in $U$, and $s_x^R$ to be the corresponding reflection in $R$. Define $W_R(U)$ to be the subgroup of $W(R)$ generated by all $s_x^R$.

Theorem 4.3: Let $(R,B)$ be a root system and let $U\subseteq R$ be a subsystem. Then the group homomorphism $W_R(U)\to W(U)$ determined by $s_x^R\mapsto s_x^U$ is an isomorphism.

Proof: The reflections $s_x^R$ for $x\in B_R(U)$ generate $W_R(U)$ by Theorem 2.2. Let $w\in W_R(U)$ be a nonidentity element; we claim that the image of $w$ is not the identity. Let $\ell_U(w)$ be the minimal length of a word for $w$ in terms of elements of $S(B_R(U))$. Let $y\in R^+(B)\cap U$. We claim that $\ell_U(ws_y) < \ell_U(w)$ if and only if $y\in I(w)$. The proof of this is similar to an earlier proof (Theorem 2.3), so we omit it. By exactly the same line of reasoning as the proof of Proposition 2.4, it follows that $\ell_U(w)=|R^+(B)\cap U|$. Thus if $w$ fixes $R$ we must have that $\ell_U(w)=0$, so $w$ is the identity. This proves injectivity of the homomorphism. Surjectivity is clear. $\square$

We therefore do not distinguish reflections in a subsystem from the corresponding reflections in the larger root system, and we identify $W(U)$ with the subgroup $W_R(U)$ of $W(R)$.

Definition 2: If $(R,B)$ is a root system, $U\subseteq R$ is a subsystem, and $w\in W(U)$ define $$I_U(w) = I(w)\cap U$$ so that $I(w)=I_R(w)$. We use this notation to distinguish inversion sets of elements in $W(U)$ in the subsystem $U$ from the inversion sets of the elements in the larger root system $R$.

Lemma 4.4: Let $(R,B)$ be a root system, $U\subseteq R$ a subsystem, $x\in B-U$, and $w\in W(U)$. Then $$I_U(w)=x\ast I_{x\ast U}(ws_x)$$
Proof: If $y\in I_U(w)$, then $w(y)\notin R^+(B)$ and $y\in U$. Then $x\ast y\in (x\ast U)\cap R^+(B)$, and $ws_x(x\ast y)=w(y)\notin R^+(B)$. Thus $I_U(w)\subseteq x\ast I_{x\ast U}(ws_x)$. Conversely, if $y\in I_{x\ast U}(ws_x)$, then $y\in x\ast U$, so that $x\ast y\in U$, and $ws_x(y)=w(x\ast y)\notin R^+(B)$. Since $x\notin x\ast U$ we have that $x\ast y\in I_U(w)$ and the result follows. $\square$



Now we define a function $\phi_U:W(R)\to W(U)$ that allows us to "project" elements of $W(R)$ onto $W(U)$.

Theorem-Definition 4.5 If $(R,B)$ is a root system and $U\subseteq R$ is a subsystem, then there is a unique function $\phi_U:W(R)\to W(U)$ such that for each $w\in W(R)$ we have that $$I(w)\cap U=I_U(\phi_U(w))$$
Proof: We prove existence by induction $\ell(w)$, the result being clear if $\ell(w)=0$. Let $x\in I(w)\cap B$. If $x\in U$, then since $I(w)=\{x\}\cup (x\ast I(ws_x))$ we have that $$\begin{align} I(w)\cap U &= (\{x\}\cup (x\ast I(ws_x)))\cap U\\ &=\{x\}\cup (x\ast I_U(\phi_U(ws_x)))\\ &=I_U(\phi_U(ws_x)s_x) \end{align}$$ (using Lemma 3.2), so $$\phi_U(w)=\phi_U(ws_x)s_x$$ If $x\notin U$, we note that $$\begin{align} I(w)\cap U&=(\{x\}\cup (x\ast I(ws_x)))\cap U\\ &=x\ast (I(ws_x)\cap (x\ast U))\\ &=x\ast (I_{x\ast U}(\phi_{x\ast U}(ws_x)))\\ &=x\ast (x\ast I_U(\phi_{x\ast U}(ws_x)s_x))\\ &=I_U(\phi_{x\ast U}(ws_x)s_x)\\ \end{align}$$ (using Lemma 3.2 and Lemma 4.4), hence $$\phi_U(w)=\phi_{x\ast U}(ws_x)s_x$$ and the result follows by induction. Uniqueness follows by uniqueness of inversion sets (Proposition 3.5). $\square$

The following theorem is quite deep and is related to the theory of permutation patterns.

Theorem-Definition 4.6: Let $(R,B)$ be a root system, let $w\in W(R)$, and let $U\subseteq R$ be a subsystem. Then there exist unique elements $w^U\in W(R)$ and $w_U\in W(U)$ such that $I(w^U)\cap U=\emptyset$ and $$w=w^Uw_U$$ In particular, $w^U$ is the unique element of minimal length in the coset $wW(U)$.

Proof: I claim that $w_U=\phi_U(w)$ satisfies the condition, with $w^U=ww_U^{-1}$. We prove by induction on $\ell_U(\phi_U(w))$ that $I(w\phi_U(w)^{-1})\cap U=\emptyset$. Set $v=\phi_U(w)$. If $\ell_U(v)=0$, then $w^U=w$ and $w_U=1=\phi_U(w)$ will work because $I(w^U)\cap U=\emptyset$ by definition. Otherwise let $x\in B_R(U)\cap I_U(v)$. Then $\ell(ws_x) < \ell(w)$ because $x\in I(w)$, and by the induction hypothesis since $\phi_U(ws_x)=vs_x$ we have that $I((ws_x)^U)\cap U=I((ws_x)(vs_x)^{-1})\cap U=\emptyset$. Since $(ws_x)(vs_x)^{-1}=wv^{-1}$, the result follows by induction.

To prove uniqueness of $w^U$, and hence of $w_U$, suppose $u\in wW(U)$ is an element of minimal length. Then $I(u)\cap U=\emptyset$ because $\ell(us_y) > \ell(u)$ for all $y\in R^+(B)\cap U$. Any element in $wW(U)$ is equal to $uv$ for some $v\in W(U)$, and if $y\in I_U(v)$ then $-v(y)\in R^+(B)\cap U$, hence $-uv(y)\in R^+(B)\cap U$, hence $y\in I(uv)$. This proves uniqueness of the minimal element as well as the element $u$ such that $I(u)\cap U=\emptyset$, because any other element in the coset contains a root in $R^+(B)\cap U$ in its inversion set. $\square$

3. Roots, words and inversion sets

In this post we gather some technical results relating roots, words and inversion sets. This is all standard Coxeter group theory.

Definition 1: Let $(R,B)$ be a root system and let $\mathbf{w}=(s_{x_1},\ldots,s_{x_n})$ be a word. For each index $i\leq n$ we assign a root $$r_i(\mathbf{w})=s_{x_n}s_{x_{n-1}}\cdots s_{x_{i+1}}(x_i)$$
The proof of Lemma 3.1 below is actually quite easy and we leave it to the reader.

Lemma 3.1: Let $(R,B)$ be a root system and let $\mathbf{u}=(s_{x_1},\ldots,s_{x_n})$ be a word. Let $x\in B$ and let $$\mathbf{v}=(s_{x_1},\ldots,s_{x_n},s_x)$$ Then for each $1\leq i\leq n$ we have $$r_i(\mathbf{v})=x\ast r_i(\mathbf{u})$$ $\square$

The next lemma allows us to build inversion sets root by root.

Lemma 3.2: Let $(R,B)$ be a root system, $w\in W(R)$, and $x\in B$. If $x\notin I(w)$, then $$I(ws_x)=\{x\}\cup (x\ast I(w))$$ If $x\in I(w)$, then $$I(ws_x)=x\ast (I(w)-\{x\})$$
Proof: Suppose $x\notin I(w)$. Then since $ws_x(x)=w(-x)=-w(x)\in R^-(B)$ we have that $x\in I(ws_x)$. If $y\in I(ws_x)$, then $$ws_x(y)=w(s_x\ast y)\notin R^+(B)$$ Since $y\neq x$, $x\ast y\in R^+(B)$. Thus $x\ast y\in I(w)$. Conversely, if $y\in I(w)$, then $w(y)=ws_x(x\ast y)\notin R^+(B)$, hence $x\ast y\in I(ws_x)$. Thus $y\mapsto x\ast y$ is a bijection of $I(w)$ with $I(ws_x)-\{x\}$, and we are done. The second part is left to the reader. $\square$

Theorem 3.3 tells us why the roots we assign to these indices are important.

Theorem 3.3: Let $(R,B)$ be a root system and let $\mathbf{w}=(s_{x_1},\ldots,s_{x_n})$ be a reduced word for the element $$w=s_{x_1}\cdots s_{x_n}$$ Then $$I(w)=\{r_i(\mathbf{w})|1\leq i\leq n\}$$
Proof: We prove this by induction on $\ell(w)$. The base case is $\ell(w)=0$, in which case a reduced word for $w$ is empty and hence the result is true. For the induction step, we assume the result is true for $w$ with an arbitrary word $\mathbf{w}=(s_{x_1},\ldots,s_{x_n})$, let $x\in B-I(w)$, and prove the result for the element $ws_x$ and the word $$\mathbf{w}'=(s_{x_1},\ldots,s_{x_n},s_x)$$ We define unambiguously $$I_{ws_x}=\{r_i(\mathbf{w}')|1\leq i\leq n+1\}$$ By Lemma 3.1 above and the induction hypothesis, we have that $$I_{ws_x}=\{x\}\cup (x\ast I(w))$$ Hence by Lemma 3.2, $$I_{ws_x}=I(ws_x)$$ and the result follows. $\square$

Definition 2: Given an element $w\in W(R)$, denote by $R(w)$ the set of reduced words for $w$. Given a reduced word $\mathbf{w}=(s_{x_1},\ldots,s_{x_n})$ for the element $w$, we define a bijection $b_{\mathbf{w}}:I(w)\to [\ell(w)]$ by declaring that $b_{\mathbf{w}}(r_j(\mathbf{w}))=j$. Then define $$B(w)=\{b_{\mathbf{w}}|\mathbf{w}\in R(w)\}$$ These can be seen as linear orderings on the inversion set. These correspond bijectively to reduced words as we prove now.

Theorem 3.4: Let $(R,B)$ be a root system and let $w\in W(R)$. Then the map $R(w)\to B(w)$ given by $\mathbf{w}\mapsto b_{\mathbf{w}}$ is a bijection.

Proof: Clearly the map is surjective. We prove it is injective by induction on $\ell(w)$. This is clear if $\ell(w)=0$. Otherwise, suppose $\mathbf{u}\neq \mathbf{v}$ are reduced words for $w$. If $\mathbf{u}_{\ell(w)}\neq \mathbf{v}_{\ell(w)}$, then there exist distinct $x,x'\in B\cap I(w)$ such that $b_{\mathbf{u}}(x)=b_{\mathbf{v}}(x')=\ell(w)$, hence $b_{\mathbf{u}}\neq b_{\mathbf{v}}$. If instead $\mathbf{u}_{\ell(w)}=\mathbf{v}_{\ell(w)}$, then there exists $x\in B\cap I(w)$ such that $b_{\mathbf{u}}(x)=b_{\mathbf{v}}(x)=\ell(w)$. Define $$\mathbf{u}'=(\mathbf{u}_i)_{i < \ell(w)}$$ and $$\mathbf{v}'=(\mathbf{v}_i)_{i < \ell(w)}$$ Then $\mathbf{u}'\neq \mathbf{v'}$ and if $y\neq x$ then $$b_{\mathbf{u}}(y)=b_{\mathbf{u}'}(x\ast y)$$ and $$b_{\mathbf{v}}(y)=b_{\mathbf{v}'}(x\ast y)$$ By the induction hypothesis, $b_{\mathbf{u}'}(x\ast y)\neq b_{\mathbf{v}'}(x\ast y)$ for some $y\in I(w)$, hence $b_{\mathbf{u}}\neq b_{\mathbf{v}}$ and the result follows by induction. $\square$

Uniqueness of inversion sets is a very useful fact that we now prove.

Proposition 3.5: Let $(R,B)$ be a root system and let $u,v\in W(R)$. If $I(u)=I(v)$, then $u=v$.

Proof: We prove this by induction on $\ell(u)=\ell(v)$. If $\ell(u)=\ell(v)=0$ this is clear. Otherwise let $x\in I(u)\cap B$. Then $$I(us_x)=I(vs_x)=x\ast (I(u)-\{x\})$$ By the induction hypothesis, $us_x=vs_x$, hence $u=(us_x)s_x=(vs_x)s_x=v$ by induction. $\square$