--- abstract: | If $\sigma \in S_n$ is a permutation of $\{1, 2, \ldots, n\}$, the inversion set of $\sigma$ is $\Phi(\sigma) = \{ (i, j) \, | \, 1 \leq i < j \leq n, \sigma(i) > \sigma(j)\}$. We describe all $r$-tuples $\sigma_1, \sigma_2, \ldots, \sigma_r \in S_n$ such that $\Delta_n^+ = \{ (i, j) \, | \, 1 \leq i < j \leq n\}$ is the disjoint union of $\Phi(\sigma_1), \Phi(\sigma_2), \ldots, \Phi(\sigma_r)$. Using this description we prove that certain faces of the Littlewood-Richardson cone are simplicial and provide an algorithm for writing down their sets of generating rays. We also consider and solve the analogous problem for the Weyl groups of root systems of type $B$ and $C$ and provide some enumerative results. Keywords: Inversion set, Simple permutation, Littlewood-Richardson cone, Catalan numbers. address: - | Department of Mathematics and Statistics Queen's University\ Kingston, Ontario, Canada\ K7L 3N6 - | Department of Mathematics and Statistics Queen's University\ Kingston, Ontario, Canada\ K7L 3N6 - | 760 Lawrence Ave. West\ Toronto, Ontario, Canada\ M6A 1B7 - | Department of Mathematics and Statistics Queen's University\ Kingston, Ontario, Canada\ K7L 3N6 - | Department of Mathematics and Computer Science\ Royal Military College\ Kingston, Ontario, Canada\ K7K 5L0 - | Department of Mathematics\ University of Chicago\ Chicago, IL\ 60637 USA author: - 'R. Dewji' - 'I. Dimitrov' - 'A. McCabe' - 'M. Roth' - 'D. Wehlau' - 'J. Wilson' title: 'Decomposing Inversion Sets of Permutations and Applications to Faces of the Littlewood-Richardson Cone' --- Introduction {#Introduction} ============ Let $n$ be a positive integer and consider a root system $\Delta_{n}$. Fix a set of positive roots $\Delta_n^+$ so that $\Delta_{n} = \Delta_n^+ \sqcup \Delta_n^-$ where $\Delta_n^- = - \Delta_n^+$. Let ${{\mathcal W}}$ denote the corresponding Weyl group. For $\sigma \in {{\mathcal W}}$, the inversion set of $\sigma$, ${{\Phi({\sigma})}}$ is defined by ${{\Phi({\sigma})}} := \{ v \in \Delta^+_n \mid \sigma\cdot v \in \Delta_n^-\}$. We are concerned with ways to express the positive roots as a disjoint union of inversion sets: $\Delta_n^+ = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}$ where $\sigma_1,\sigma_2,\dots,\sigma_r \in {{\mathcal W}}$. We consider here only root systems of type $A$, $B$ or $C$. For simplicity we describe the problem and our results first for root systems of type $A$. The Weyl group of the root system $A_n$ is ${{\mathcal W}}=S_{n+1}$ the symmetric group on $n+1$ letters. For ease of notation, we replace $n+1$ by $n$ and work with $A_{n-1}$ and $S_{n}$. Thus $\Delta_{n}$ refers to the rank $n-1$ root system of type $A_{n-1}$. Root systems of type $B$ and $C$ have isomorphic Weyl groups and so yield identical answers to our questions. We describe our results for type $B/C$ root systems in §\[B section\]–\[C section\]. For $\sigma \in S_n$ we write $\sigma=(\sigma(1),\sigma(2),\dots,\sigma(n))$. ${{\rm Id}}_n$ denotes the identity permutation: ${{\rm Id}}_n = (1,2,\dots,n)$ and ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}={w_{\rm o}\tlist@if@empty@nTF{n}{}{ [n]}} = (n,n-1,\dots,1) \in S_n$. Often we will write ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$ to denote ${w_{\rm o}\tlist@if@empty@nTF{n}{}{ [n]}}$ when the value of $n$ is clear from the context. We use the symbol $\sqcup$ to denote a disjoint union. For the root system of type $A_{n-1}$ we may take $\Delta_n^+ := \{(i,j) \mid 1 \leq i < j \leq n\}$ for the positive roots. The element $(1,n)$ is the <span>*highest root*</span>. The elements $(i,i+1)$ with $1\leq i \leq n-1$ are the <span>*simple roots*</span>. Often we will use $\Delta^+$ to denote $\Delta^+_n$ when the value of $n$ is clear from the context. Given $\sigma \in S_n$, the <span>*inversion set of $\sigma$*</span> is the set ${{\Phi({\sigma})}} := \{ (i,j) \in \Delta^+_n \mid \sigma(i) > \sigma(j)\}$. Note that ${{\Phi({{{\rm Id}}})}} = \emptyset$ and ${{\Phi({{w_{\rm o}\tlist@if@empty@nTF{n}{}{ [n]}}})}} = \Delta_n^+$. It is not hard to see that the element $\sigma \in S_n$ is determined by its inversion set ${{\Phi({\sigma})}}$. Thus there are exactly $n!$ inversion sets contained in $\Delta_n^+$. A <span>*decomposition*</span> of an inversion set ${{\Phi({\sigma})}}$ is a set of disjoint inversion sets ${{\Phi({\sigma_1})}},{{\Phi({\sigma_2})}},\dots,{{\Phi({\sigma_r})}}$ such that $${{\Phi({\sigma})}} = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}\ .$$ The decomposition is called <span>*trivial*</span> if ${{\Phi({\sigma})}}={{\Phi({\sigma_a})}}$ for some $a$ with $1 \leq a \leq r$. We say that an element $\sigma\in S_n$ (and its inversion set ${{\Phi({\sigma})}}$) is <span>*reducible*</span> if there exists a non-trivial decomposition of ${{\Phi({\sigma})}}$. Otherwise we say that $\sigma$ (and ${{\Phi({\sigma})}}$) is <span>*irreducible*</span>. Note that ${{\Phi({{{\rm Id}}})}}=\emptyset$ may occur in a decomposition. Solving the following problem was the motivation for this article. \[main problem\] Identify all decompositions of $\Delta_n^{+}$: $$\Delta_n^+ = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}\ .$$ Here the ordering of the $\sigma_i$ is not relevant. We are interested in this problem because of its relation to two problems: (i) determining the regular codimension $n$ faces of the Littlewood-Richardson cone; and (ii) studying the cup product of the cohomology of line bundles on homogeneous varieties. We briefly describe the relation to the Littlewood-Richardson cone in the next paragraph. More details and the relation of Problem \[main problem\] to the cup product of line bundles appear in §\[Motivation\]. If $A$ is a Hermitian matrix, denote by $\lambda = (\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n) \in {{\mathbb R}}^n$ its eigenvalues and let ${{\mathbb R}}^{3n}_+ = \{(\lambda, \mu, \nu) \, | \, \lambda_i \geq \lambda_{i+1}, \mu_i \geq \mu_{i+1}, \nu_i \geq \nu_{i+1} {\text { for }} 1 \leq i \leq n-1\}$. In 1912 H. Weyl posed the following question: For which triples $(\lambda, \mu, \nu) \in {{\mathbb R}}^{3n}_+$ do there exist Hermitian matrices $A,B,C$ such that $C = A+ B$ and whose eigenvalues are $\lambda, \mu,\nu$ respectively. In 1962 A. Horn proved that the set of such triples is a polyhedral cone $\mathcal{C'}$ and conjectured inequalities determining $\mathcal{C'}$. Horn's conjecture was proved in the 1990's by Klyachko and Knutson and Tao, see @F for a nice exposition on Horn's conjecture. It is worth mentioning that the lattice points of $\mathcal{C'}$ are exactly the triples $(\lambda, \mu, \nu)$ for which the corresponding Littlewood-Richardson coefficient $c_{\lambda, \mu}^\nu$ is nonzero. N. Ressayre described all <span>*regular faces of $\mathcal{C}'$*</span>, i.e. faces that intersect the interior of ${{\mathbb R}}^{3n}_+$. In particular (after symmetrizing the problem, as described in §\[Motivation\]), the regular faces of codimension $n$ are exactly the intersection of ${{\mathbb R}}^{3n}_+$ with the subspaces defined by $$w_1^{-1} \lambda + w_2^{-1} \mu + w_3^{-1} \nu = 0$$ for $w_1, w_2, w_3 \in S_n$ with the property that $\Delta_n^+ = {{\Phi({w_1})}} \sqcup {{\Phi({w_2})}} \sqcup {{\Phi({w_3})}}$. Let $\sigma \in S_n$. An <span>*interval*</span> (of size $t$) is a set of consecutive integers $\{i,i+1,i+2,\dots,i+t-1\}$. A <span>*block*</span> (of size $t$) of the permutation $\sigma$ is an interval $\{i,i+1,i+2,\dots,i+t-1\}$ of size $t$ such that the set $\{\sigma(i),\sigma(i+1),\dots,\sigma(i+t-1)\}$ is also an interval (of size $t$). Every permutation in $S_n$ has $n$ blocks of size 1 and a block of size $n$. If $\sigma \in S_n$ has no blocks of size $t$ for all $1 < t < n$ then we say that $\sigma$ is <span>*simple*</span>[^1]. The permutation $\sigma = (9,7,1,5,3,4,6,8,2)\in S_9$ has a block of size 8 corresponding to the interval $\{2,3,\dots9\}$ and a block size 4 corresponding to the interval $\{4,5,6,7\}$. The permutation $\tau=(5,2,6,1,4,7,3)\in S_6$ has no non-trivial blocks and so is simple. A block of size $t+1$ for the permutation $\sigma$ corresponds to a $t \times t$ closed square in $[1,n]\times[1,n]$ which contains $t+1$ points of the the graph of $\sigma$. Hence $\sigma$ is simple if there does not exist a $t\times t$ closed square in containing $t+1$ points of the graph of $\sigma$ with $2\leq t \leq n-1$. To state our results we need to introduce an inflation procedure to describe permutations inductively. We describe this procedure heuristically as follows. We consider a permutation on $n$ letters as a shuffling of a deck of $n$ cards. We shuffle as follows. First cut the deck into $m$ piles of sizes $z_1,z_2,\dots,z_m$ respectively. Shuffle each of these piles according to a permutation $\sigma_a \in S_{z_a}$. Finally reassemble the piles in an order determined by a permutation $\sigma_0 \in S_m$. The resulting permutation in $S_n$ is denoted by $\sigma_0[\sigma_1,\sigma_2,\dots,\sigma_m]$ and is called an inflation of $\sigma_0$. Note that a permutation $\alpha\in S_n$ is simple if and only if $\alpha$ cannot be expressed as an inflation $\alpha=\sigma[\beta_1,\beta_2,\dots,\beta_r]$ with $2 \leq r \leq n-1$. A permutation $\sigma\in S_n$ is called <span>*plus-decomposable*</span> if $\sigma$ may be written in the form $\sigma = {{\rm Id}}_2[\alpha,\beta]$. Otherwise $\sigma$ is <span>*plus-indecomposable*</span>. Similarly, $\sigma\in S_n$ is called <span>*minus-decomposable*</span> if $\sigma$ may be written in the form $\sigma = {w_{\rm o}\tlist@if@empty@nTF{2}{}{ [2]}}[\alpha,\beta]$. Otherwise $\sigma$ is <span>*minus-indecomposable*</span>. The following theorem of Albert, Atkinson and Klazar illustrates the importance of simple permutations and the inflation procedure. \[<span>@AAK\[Theorem 1\]</span>\] Let $n \geq 2$. For every permutation $\alpha \in S_n$ there exists a simple permutation $\sigma \in S_m$ and permutations $\beta_1,\beta_2,\dots,\beta_m$ such that $\alpha = \sigma[\beta_1,\beta_2,\dots,\beta_m]$. Moreover if $\sigma \ne {{\rm Id}}_2$ and $\sigma\neq {w_{\rm o}\tlist@if@empty@nTF{2}{}{ [2]}}$ then $\beta_1,\beta_2,\dots,\beta_m$ and $\sigma$ are unique. If $\sigma = {{\rm Id}}_2$ then $\beta_1,\beta_2$ and $\sigma$ are unique if we add the additional condition that $\beta_1$ is plus-indecomposable. Similarly, if $\sigma = {w_{\rm o}\tlist@if@empty@nTF{2}{}{ [2]}}$ then $\beta_1,\beta_2$ and $\sigma$ are unique if we add the additional condition that $\beta_1$ is minus-indecomposable. For our purposes, we modify the statement of the above theorem as follows. \[simple form theorem\] Let $n \geq 2$. For every permutation $\alpha \in S_n$ there exists a permutation $\sigma \in S_m$ and permutations $\beta_1,\beta_2,\dots,\beta_m$ such that $\alpha = \sigma[\beta_1,\beta_2,\dots,\beta_m]$ where either $\sigma$ is simple and $m \geq 4$ or $\sigma = {{\rm Id}}_m$ or $\sigma={w_{\rm o}\tlist@if@empty@nTF{m}{}{ [m]}}$. Furthermore this expression for $\alpha$ is unique if we require that $m$ be maximal when $\sigma={{\rm Id}}_m$ or $\sigma={w_{\rm o}\tlist@if@empty@nTF{m}{}{ [m]}}$, i.e., that each $\beta_a$ is plus-indecomposable when $\sigma={{\rm Id}}$ and each $\beta_a$ is minus-indecomposable when $\sigma={w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$. We say that $\alpha$ is expressed in <span>*simple form*</span> when we write $\alpha = \sigma[\beta_1,\beta_2,\dots,\beta_m]$ in the form guaranteed by Theorem \[simple form theorem\], i.e, when $\sigma$ is simple with $m \geq 4$ or $\sigma={w_{\rm o}\tlist@if@empty@nTF{m}{}{ [m]}}$ or ${{\rm Id}}_m$ with $m$ maximal. We now state our main result. \[main theorem\] Let $\Delta_n^+ = {{\Phi({w_1})}} \sqcup {{\Phi({w_2})}} \sqcup \dots \sqcup {{\Phi({w_r})}}$ be a decomposition with all ${{\Phi({w_a})}} \neq \emptyset$. Then (after possibly reordering) we have $$\begin{aligned} w_1 &= & \sigma_1[\beta_{11},\beta_{12},\dots,\beta_{1m}]\\ w_2 &= & \sigma_2[\beta_{21},\beta_{22},\dots,\beta_{2m}]\\ & & \vdots\\ w_r &= & \sigma_r[\beta_{r1},\beta_{r2},\dots,\beta_{rm}] \end{aligned}$$ where $$(\dag)\quad {{\Phi({\beta_{1b}})}} \sqcup {{\Phi({\beta_{2b}})}} \sqcup \dots \sqcup {{\Phi({\beta_{rb}})}} = \Delta^+_{z_b} \text{ is a decomposition} \qquad \forall b=1,2,\dots,m$$ and $\sigma_q=\sigma_{q+1}=\dots=\sigma_r={{\rm Id}}_m$ with $$ \_1 = <span>w\_<span>o</span>@if@empty@nTF<span>m</span><span> \[m\]</span></span> $q=2$,& w\_1;\ \_1 , \_2=<span>w\_<span>o</span>@if@empty@nTF<span> \[\]</span></span>\_1 $q=3$,& w\_1 $$ Moreover, the above decomposition of $\Delta_n^+$ is irreducible if and only if the decompositions $(\dag)$ are irreducible for all $b$, exactly one of $\beta_{a1},\beta_{a2},\dots,\beta_{am}$ is not equal to ${{\rm Id}}$ for each $a=q,q+1,\dots,r$, and $$ m=2 \_<span>11</span>=<span><span>Id</span></span>\_<span>z\_1</span> \_<span>12</span>=<span><span>Id</span></span>\_<span>z\_2</span>,& w\_1\ \_<span>1b</span>=\_<span>2b</span>=<span><span>Id</span></span>\_<span>z\_b</span> b=1,2,…,m,& w\_1 $$ \[example\] Let $n=8$ and let $w_1 = (5,3,4,8,1,2,6,7)$, $w_2 = (4,5,6,1,7,8,3,2)$, $w_3 = (1,3,2,4,6,5,7,8)$. Then $\Delta_8^+ = {{\Phi({w_1})}} \sqcup {{\Phi({w_2})}} \sqcup {{\Phi({w_3})}}$, $m=4$, and $$\begin{array}{rcl} w_1 &=& (2,4,1,3)[(3,1,2),(1),(1,2),(1,2)]\\ w_2 &=& (3,1,4,2)[(1,2,3),(1),(1,2),(2,1)]\\ w_3 &=& (1,2,3,4)[(1,3,2),(1),(2,1),(1,2)]. \end{array}$$ Also $\beta_{11}= (21)[(1),(12)]=(2,3,1)$, $\beta_{21}=(12)[(1),(12)]={{\rm Id}}_3$, $\beta_{31}=(12)[(1),(21)]=(1,3,2)$ and all other $\beta_{ij}={{\rm Id}}$. Note that $\Delta_3^+ = {{\Phi({\beta_{11}})}} \sqcup {{\Phi({\beta_{21}})}} \sqcup {{\Phi({\beta_{31}})}} = {{\Phi({\beta_{11}})}} \sqcup {{\Phi({\beta_{31}})}}$. The recursive form of this theorem allows us to inductively solve many problems concerning decompositions. For example, in §\[enumerative section\] we exploit this recursiveness to obtain a number of results enumerating various solutions to the main problem. In §\[Motivation\] we use the form to prove a result about the decompositions which yields an algorithm producing all generating rays on a given regular codimension $n$ face of the Littlewood-Richardson cone. Preliminaries ============= It is easy to see that an inversion set $\Phi$ must satisfy the following two conditions: - If $(i,j), (j,k) \in \Phi$ then $(i,k) \in \Phi$. (<span>*closed condition*</span>) - If $(i,j), (j,k) \notin \Phi$ then $(i,k) \notin \Phi$. (<span>*co-closed condition*</span>) In @K [Proposition 5.10] it is shown that any subset $\Phi \subseteq \Delta_n^+$ which satisfies the above two conditions is an inversion set. Thus $\Phi \subset \Delta_n^{+}$ is an inversion set if and only if both $\Phi$ and $\Phi^\text{c}$ satisfy the closed condition. The graph of a permutation $\sigma$ is the set of $n$ lattice points $\{(i,\sigma(i))\mid i=1,2,\dots,n\}$ considered as a subset of $[1,n]\times [1,n] \subset {{\mathbb R}}^2$. There are ${\genfrac{(}{)}{0pt}{}{n}{2}}$ line segments joining points of the graph of $\sigma$. Each such line segment corresponds to an element of $\Delta_n^+$ and those with negative slope correspond to the elements ${{\Phi({\sigma})}}$, i.e., $(i,j) \in {{\Phi({\sigma})}}$ if and only if the line segment joining the points $(i,\sigma(i))$ and $(j,\sigma(j))$ has negative slope. We have already noted that ${{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}})}} = \Delta^+$. The following lemma gives another indication of the importance of ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$. Let $\sigma \in S_n$. Then $\Delta_n^+ = {{\Phi({\sigma})}} \sqcup {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma})}}$. The graph of ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma$ is obtained from the graph of $\sigma$ by reflecting in the line $y=n/2$. Using the characterization of ${{\Phi({\sigma})}}$ as those positive roots whose corresponding line segment has negative slope completes the proof of the lemma. \[coalescence\] 1. Suppose $\Delta_n^+ = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots {{\Phi({\sigma_r})}}$ is a decomposition and let $A$ be any subset of $\{1,2,\dots,r\}$. Then $\exists \sigma \in S_n$ such that ${{\Phi({\sigma})}} = \sqcup_{a\in A} {{\Phi({\sigma_a})}}$. 2. Every non-empty inversion set ${{\Phi({\sigma})}}$ contains at least one simple root. Clearly it suffices to prove the first assertion for doubleton sets $A=\{p,q\}$. Thus it suffices to show that ${{\Phi({\sigma_p})}} \sqcup {{\Phi({\sigma_q})}}$ is both closed and co-closed. For ease of notation, we will assume $A = \{1,2\}$. First we show that ${{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$ is co-closed. Suppose that $(i,j),(j,k) \notin {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$. Then for $b=1,2$ we have $(i,k) \notin {{\Phi({\sigma_b})}}$ since ${{\Phi({\sigma_b})}}$ is co-closed. Thus $(i,k) \notin {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$ which shows ${{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$ is co-closed. To see that ${{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$ is closed, suppose that $(i,j), (j,k) \in {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$. Then for $b=3,4,\dots,r$ we have $(i,j),(j,k) \notin {{\Phi({\sigma_b})}}$ and thus $(i,k) \notin {{\Phi({\sigma_b})}}$ since ${{\Phi({\sigma_b})}}$ is co-closed. Hence $(i,k) \notin \sqcup_{b=3}^r {{\Phi({\sigma_b})}}$ which implies that $(i,k) \in {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$. This shows that that ${{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$ is closed and completes the proof of the first assertion. The second assertion follows easily from the fact that if $\sigma(i) < \sigma(i+1)$ for all $i=1,2,\dots,n-1$ then $\sigma={{\rm Id}}_n$. Note that the hypothesis that $\Delta_n^+ = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots {{\Phi({\sigma_r})}}$ is necessary in the above proposition; arbitrary unions of inversion sets need not be inversion sets. For example, consider $n=3$, $\sigma_1 = (2,1,3)$ and $\sigma_2 = (1,3,2)$. Then ${{\Phi({\sigma_1})}} = \{(1,2)\}$, ${{\Phi({\sigma_2})}} = \{(2,3)\}$ and ${{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$ is not closed and so is not an inversion set. The first assertion of Proposition \[coalescence\] implies that if ${{\Phi({\sigma})}} = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}$ and $A$ is any subset of $\{1,2,\dots,r\}$ then $\exists \alpha\in S_n$ with ${{\Phi({\alpha})}} = \sqcup_{a\in A} {{\Phi({\sigma_a})}}$. This fact follows easily from the first assertion of the above proposition and the fact that $\Delta_n^+ = {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma})}} \sqcup {{\Phi({\sigma})}} = {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma})}} \sqcup {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}$. In particular, an element $\sigma \in S_n$ is reducible if and only if there exist non-identity elements $\alpha_1,\alpha_2 \in S_n$ with ${{\Phi({\sigma})}} ={{\Phi({\alpha_1})}} \sqcup {{\Phi({\alpha_2})}}$. Note that we may also write this last equation as the decomposition $\Delta^+_n = {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma})}} \sqcup {{\Phi({\alpha_1})}} \sqcup {{\Phi({\alpha_2})}}$. These considerations show that in our study of decompositions of $\Delta^+$ we may focus our attention on <span>*irreducible decompositions*</span>, i.e., decompositions $\Delta^+_n = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}$ where $\sigma_a$ is irreducible for $a=1,2,\dots,r$. Two sequences $x_1,x_2,\dots,x_n$ and $y_1,y_2,\dots,y_n$ each comprised of $n$ distinct real numbers are <span>*order isomorphic*</span> if $x_i > x_j$ if and only if $y_i > y_j$. Let $\sigma\in S_n$ and suppose ${{{\mathcal F}}}$ is some subset of $\{1,2,\dots,n\}$ with $m = |{{\mathcal F}}|$. Write ${{\mathcal F}}=\{i_1,i_2,\dots,i_m\}$ where $i_1 < i_2 < \dots < i_m$. Restricting $\sigma$ to ${{\mathcal F}}$ yields a sequence $\sigma(i_1),\sigma(i_2),\dots,\sigma(i_m)$ which is order isomorphic to the sequence $\mu(1),\mu(2),\dots,\mu(m)$ corresponding to a unique element $\mu \in S_m$. We denote this element $\mu$ by $\mu = \theta_{{\mathcal F}}(\sigma)$. If ${{\mathcal F}}\subset \{1,2,\dots,n\}$ we write $\Delta^+_{{\mathcal F}}$ to denote the set $\Delta^+_{{\mathcal F}}:= \{(i,j) \in \Delta^+_n \mid i,j \in {{\mathcal F}}\}$. Inflation Procedure =================== Now we want to describe the inflation procedure for permutations. For a history of the inflation procedure and a discussion of a number of applications we refer the reader to the survey article of Brignall @B. The following definition will be useful. Write $\{1,2,\dots,n\}=I_1 \sqcup I_2 \sqcup \dots \sqcup I_m$ as a disjoint union of ordered intervals. A subset ${{\mathcal F}}\subset \{1,2,\dots,n\}$ is <span>*admissible*</span> if $|{{\mathcal F}}\cap I_a|=1$ for all $a=1,2,\dots,m$. In addition to the heuristic description given in §\[Introduction\], we may describe the inflation procedure as follows. Write $\{1,2,\dots,n\}$ as an ordered disjoint union of intervals: $\{1,2,\dots,n\} = I_1 \sqcup I_2 \sqcup \dots \sqcup I_m$ where each $I_a$ is an interval and $I_a < I_b$ if $a < b$, i.e., if $a < b$ and $i_a\in I_a, i_b \in I_b$ then $i_a < i_b$. Put $z_a=|I_a|$. Take $\sigma_0 \in S_m$ and $\sigma_a \in S_{z_a}$ for $a=1,2,\dots,m$. Then $\sigma := \sigma_0[\sigma_1,\sigma_2,\dots,\sigma_m]$ is characterized by the following two conditions. 1. $\theta_{{\mathcal F}}(\sigma)=\sigma_0$ for every admissible ${{\mathcal F}}$. 2. $\theta_{I_a}(\sigma) = \sigma_a$ for all $a=1,2,\dots,m$. The proof of the following lemma is straightforward and is left to the reader. \[easy lemma\] Suppose $\alpha=\alpha_0[\beta_1,\beta_2,\dots,\beta_m]$ where $\beta_a \in S_{z_a}$ for $a=1,2,\dots,m$. Define $I_1 := \{1,2,\dots,z_1\}$, $I_2 := \{z_1+1,z_1+2,\dots,z_1+z_2\},\dots, I_m:=\{z_1+z_2+\dots+z_{m-1}+1, \dots, n\}$. Let $\Psi_a$ denote the order preserving bijection $\Psi_a : I_a \to \{1,2,\dots.z_a\}$. Then $${{\Phi({\alpha})}} = \{(i_a,i_b) \mid i_a \in I_a, i_b \in I_b, (a,b) \in {{\Phi({\alpha_0})}}\} \sqcup \left(\sqcup_{a=1}^m\Psi_a^{-1}({{\Phi({\beta_a})}})\right)\ .$$ \[irreducible under inflation\] Let $\sigma_0 \in S_m$ and let $z_1,z_2,\dots,z_m$ be positive integers. Put $n := z_1+z_2+\dots+z_m$. The permutation $\sigma:=\sigma_0[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_m}] \in S_n$ is irreducible if and only if $\sigma_0$ is irreducible. Let $\{1,2,\dots,n\} = I_1 \sqcup I_2 \sqcup \dots \sqcup I_m$ be the decomposition into intervals corresponding to the the inflation $\sigma:=\sigma_0[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_m}]$. By Lemma \[easy lemma\], we have ${{\Phi({\sigma})}} = \{(i,j) \in \Delta_n^+ \mid i \in I_a, j \in I_b, (a,b) \in {{\Phi({\sigma_0})}}\}$. First suppose that $\sigma_0$ is reducible and write ${{\Phi({\sigma_0})}} = {{\Phi({\alpha_0})}} \sqcup {{\Phi({\beta_0})}}$. Then ${{\Phi({\sigma})}} = {{\Phi({\alpha})}} \sqcup {{\Phi({\beta})}}$ where $\alpha:=\alpha_0[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_n}]$ and $\beta:=\beta_0[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_n}]$. Thus if $\sigma_0$ is irreducible then so is $\sigma$. Next suppose that $\sigma$ is reducible and write ${{\Phi({\sigma})}} = {{\Phi({\alpha})}} \sqcup {{\Phi({\beta})}}$ where $\alpha, \beta \in S_n$. Consider a positive root $(p,q)\in \Delta_n^+$. Define $a$ and $b$ by $p \in I_a$ and $q \in I_b$. If $a=b$ then $(p,q) \notin {{\Phi({\sigma})}}$. Suppose then that $a < b$. Again if $(a,b) \notin {{\Phi({\sigma_0})}}$ then $(p,q) \notin {{\Phi({\sigma})}}$. Thus we suppose that $(a,b) \in {{\Phi({\sigma})}}$. Write $I_a = \{u,u+1,\dots,u+z_a-1\}$ and $I_b = \{v,v+1,\dots,v+z_n-1\}$. Then $(u+z_a-1,v) \in {{\Phi({\sigma})}}$ and thus, without loss of generality, $(u+z_a-1,v) \in {{\Phi({\beta})}}$. Then $\alpha(u+z_a-1) < \alpha(v)$. This implies that $(I_a,I_b) \cap {{\Phi({\alpha})}} = \emptyset$ where $(I_a,I_b) := \{(i,j) \mid i \in I_a, j\in I_b\}$. Since $(I_a,I_b) \subset {{\Phi({\sigma})}}$, this implies that $(I_a,I_b) \subset {{\Phi({\beta})}}$. This shows that ${{\Phi({\beta})}} = \{ (i,j) \mid i \in I_c, j \in I_d, (c,d) \in T\} = \sqcup_{(c,d) \in T} (I_c,I_d)$ for some set $T \subset \Delta_m^+$. Moreover, the fact that ${{\Phi({\beta})}}$ is both closed and co-closed implies that the set $T$ is also both closed and co-closed and so $T = {{\Phi({\beta_0})}}$ for some non-identity permutation $\beta_0 \in S_m$. This shows that $\beta = \beta_0[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_m}]$. Similarly $\alpha = \alpha_0[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_m}]$ for some non-identity $\alpha_0 \in S_m$. Thus ${{\Phi({\sigma_0})}} = {{\Phi({\alpha_0})}} \sqcup {{\Phi({\beta_0})}}$ is reducible. The following proposition follows easily from the two preceding lemmas. \[easy proposition\] Suppose $\alpha=\alpha_0[\beta_1,\beta_2,\dots,\beta_m]$ where $\beta_a \in S_{z_a}$ for $a=1,2,\dots,m$. Let $A \subset \{1,2,\dots,m\}$ and define $\gamma_a = \begin{cases} \beta_a, &\text{if } a \in A;\\ {{\rm Id}}_{z_a}, &\text{if } a \notin A \end{cases}$ and $\gamma'_a = \begin{cases} {{\rm Id}}_{z_a}, &\text{if } a \in A;\\ \beta_a, &\text{if } a \notin A. \end{cases}$ Define $\sigma_0 = \alpha_0[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_n}]$, $\sigma_1={{\rm Id}}[\gamma_1,\gamma_2,\dots,\gamma_m]$ and $\sigma_2 = Id[\gamma'_1,\gamma'_2,\dots,\gamma'_m]$ Then ${{\Phi({\gamma})}} = {{\Phi({\sigma_0})}} \sqcup {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$. Therefore, if $\alpha\neq {{\rm Id}}$ is irreducible, then exactly one of the permutations $\alpha_0,\beta_1,\beta_2,\dots,\beta_m$ is a non-identity permutation. In particular, if $\alpha$ is irreducible with $\alpha_0 \neq {{\rm Id}}$ then $\alpha=\alpha_0[{{\rm Id}},{{\rm Id}},\dots.{{\rm Id}}]$ where $\alpha_0$ is irreducible. \[complements are simple\] Let $\sigma \in S_n$. The permutation $\sigma$ is simple if and only if ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma$ is simple. This result follows immediately from the fact that that the graph of ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma$ is obtained from the graph of $\sigma$ by reflecting in the line $y=n/2$. Let $\sigma \in S_n$, and ${{\mathcal F}},{{\mathcal F}}' \subset \{1,2,\dots,n\}$. If ${{\Phi({\sigma})}} \cap \Delta^+_{{\mathcal F}}\cap \Delta^+_{{{\mathcal F}}'} \neq \emptyset$ then we say that ${{\mathcal F}}$ and ${{\mathcal F}}'$ are $\sigma$-<span>*connected*</span>. Let ${{\mathcal F}}$ and ${{\mathcal F}}'$ be subsets of $\{1,2,\dots,n\}$. If there exist subsets ${{\mathcal F}}_1,{{\mathcal F}}_2,\dots,{{\mathcal F}}_t \subset \{1,2,\dots,n\}$ such that ${{\mathcal F}}={{\mathcal F}}_1$, ${{\mathcal F}}'={{\mathcal F}}_t$ and ${{\mathcal F}}_a$ is $\sigma$-connected to ${{\mathcal F}}_{a+1}$ for $a=1,2,\dots,t-1$ then we say that ${{\mathcal F}}$ and ${{\mathcal F}}'$ are $\sigma$-<span>*path-connected*</span>. We will make use of the following lemma a number of times. \[technical\] Let $\sigma \in S_n$ and ${{\mathcal F}},{{\mathcal F}}' \subset \{1,2,\dots,n\}$. Write $\mu = \theta_{{\mathcal F}}(\sigma)$ and $\mu' = \theta_{{{\mathcal F}}'}(\theta)$. Suppose that ${{\Phi({\sigma})}} = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}$. 1. If $\mu$ is irreducible then there exists $\delta({{\mathcal F}})$ with $1 \leq \delta({{\mathcal F}}) \leq n$ such that ${{\Phi({\sigma})}} \cap \Delta^+_{{\mathcal F}}\subset {{\Phi({\sigma_{\delta({{\mathcal F}})}})}}$. 2. If $\mu$ and $\mu'$ are both irreducible and ${{\mathcal F}}$ and ${{\mathcal F}}'$ are $\sigma$-path connected then $\delta({{\mathcal F}})=\delta({{\mathcal F}}')$. Let $|{{\mathcal F}}|=m$ and suppose that $\mu$ is irreducible. Put $\mu_a = \theta_{{{\mathcal F}}}(\sigma_a)$ for $a=1,2,\dots,r$. There exists an order preserving bijection $\Psi : {{\mathcal F}}\to \{1,2,\dots,m\}$. It is easy to see that $(i,j) \in {{\Phi({\alpha})}} \cap \Delta^+_{{\mathcal F}}$ if and only if $(\Psi(i),\Psi(j)) \in {{\Phi({\theta_{{\mathcal F}}(\alpha)})}}$ for all $\alpha \in S_n$. Thus $\Psi$ identifies ${{\Phi({\alpha})}} \cap \Delta^+_{{\mathcal F}}$ with ${{\Phi({\theta_{{\mathcal F}}(\alpha)})}}$. Intersecting ${{\Phi({\sigma})}} = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}$ with $\Delta^+_{{\mathcal F}}$ and using this identification we get ${{\Phi({\mu})}} = {{\Phi({\mu_1})}} \sqcup {{\Phi({\mu_2})}} \sqcup \dots \sqcup {{\Phi({\mu_r})}}$. Since $\mu$ is irreducible, there exists $\delta({{\mathcal F}})$ such that ${{\Phi({\mu})}} \subset {{\Phi({\mu_{\delta({{\mathcal F}})}})}}$. Therefore ${{\Phi({\sigma})}} \cap \Delta^+_{{{\mathcal F}}} \subset {{\Phi({\sigma_{\delta({{\mathcal F}})}})}}$. For the second assertion, suppose that $\mu$ and $\mu'$ are irreducible. Clearly it suffices to consider the case where ${{\mathcal F}}$ and ${{\mathcal F}}'$ are $\sigma$-connected. By the above, ${{\Phi({\sigma})}} \cap \Delta^+_{{{\mathcal F}}} \subset {{\Phi({\sigma_{\delta({{\mathcal F}})}})}}$ and ${{\Phi({\sigma})}} \cap \Delta^+_{{{\mathcal F}}'} \subset {{\Phi({\sigma_{\delta({{\mathcal F}}')}})}}$. But ${{\mathcal F}}$ and ${{\mathcal F}}'$ are $\sigma$-connected implies that there exists $(i,j) \in {{\Phi({\sigma})}} \cap \Delta^+_{{\mathcal F}}\cap \Delta^+_{{{\mathcal F}}'}$. Thus $(i,j) \in {{\Phi({\sigma_{\delta({{\mathcal F}})}})}} \cap {{\Phi({\sigma_{\delta({{\mathcal F}}')}})}}$. Hence $\delta({{\mathcal F}})=\delta({{\mathcal F}}')$. \[technical cor\] Suppose ${{\mathcal F}}_1,{{\mathcal F}}_2,\dots,{{\mathcal F}}_s \subset \{1,2,\dots,n\}$ where ${{\mathcal F}}_i$ and ${{\mathcal F}}_j$ are $\sigma$-path-connected for all $1\leq i, j \leq s$. Further suppose that $\theta_{{{\mathcal F}}_i}(\sigma)$ is irreducible for all $i=1,2,\dots,s$ and ${{\Phi({\sigma})}} \subset \cup_{i=1}^s \Delta_{{{\mathcal F}}_i}^+$. Then $\sigma$ is irreducible. Suppose that ${{\Phi({\sigma})}} = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}} \sqcup \dots \sqcup {{\Phi({\sigma_r})}}$. By the lemma, we have $j = \delta({{\mathcal F}}_1) = \delta({{\mathcal F}}_2) = \dots = \delta({{\mathcal F}}_r)$ with ${{\Phi({\theta})}} \cap \Delta_{{{\mathcal F}}_i}^+ \subset {{\Phi({\sigma_j})}}$. Therefore ${{\Phi({\sigma})}} = \sqcup_{i=1}^r ({{\Phi({\sigma})}} \cap \Delta_{{{\mathcal F}}_i}^+) \subset {{\Phi({\sigma_j})}}$ and thus the decomposition of ${{\Phi({\sigma})}}$ is trivial. \[technical remark\] Suppose $\sigma=\sigma_0[\sigma_1,\sigma_2,\dots,\sigma_m]$ where $\sigma_0$ is irreducible. Further suppose that the sets ${{\mathcal F}}_1,{{\mathcal F}}_2,\dots,{{\mathcal F}}_t$ are all admissible (with respect to $\sigma$). If the ${{\mathcal F}}_i$ are all $\sigma$-path connected and ${{\Phi({\sigma})}} \subset \cup_{i=1}^s \Delta_{{{\mathcal F}}_i}^+$ then the above corollary applies and shows that $\sigma$ is irreducible. A permutation $\sigma\in S_n$ is <span>*atomic*</span> if $\sigma(i+1)\neq\sigma(i)+1$ for all $i=1,2,\dots,n-1$. Let $n=2m$ be even with $n \geq 4$. A permutation $\sigma$ is <span>*exceptional*</span> if $\sigma$ is one of the following permutations 1. $\sigma = (2,4,6,\dots,n-2,n,1,3,5,\dots,n-3,n-1)$, 2. $\sigma=(m+1,1, m+2, 2, m+3, 3,\dots, 2m-1, m-1, 2m, m)$, 3. $\sigma= (n-1,n-3,n-5,\dots,3,1,n,n-2,n-4,\dots,4,2)$, 4. $\sigma =(m, 2m, m-1, 2m-1,m-2,2m-2,\dots,2, m+2, 1, m+1)$. \[exceptional\] Let $\sigma \in S_n$ be exceptional. Then $\sigma$ is atomic and irreducible. It is easily seen that all of these permutations are atomic. \(1) Suppose $\sigma = (2,4,6,\dots,n-2,n,1,3,5,\dots,n-3,n-1)$. Then ${{\Phi({\sigma})}}$ has only one simple root, $(m,m+1)$ and so is irreducible. For the remaining cases, we proceed by induction and use Corollary \[technical cor\] repeatedly. If $n=4$, it is easy to check that the only two exceptional permutations (2,4,1,3) and (3,1,4,2) are irreducible. To prove the induction step, let $n \geq 6$. \(2) Suppose $\sigma=(m+1,1, m+2, 2, m+3, 3,\dots, 2m-1, m-1, 2m, m)$. Let ${{\mathcal F}}' = \{1,2,\dots,2m-2\}$ and ${{\mathcal F}}' := \{3,4,\dots,2m\}$. We let $\mu = \theta_{{\mathcal F}}(\sigma) = \theta_{{{\mathcal F}}'}(\sigma)$. Then $\mu = (m+1,1, m+2, 2, m+3, 3,\dots, 2m-1, m-1)$ is again exceptional and so is irreducible by the induction hypothesis. Furthermore ${{\mathcal F}}$ and ${{\mathcal F}}'$ are $\sigma$-connected since $(3,4) \in {{\Phi({\sigma})}}$ with $3,4 \in {{\mathcal F}}\cap {{\mathcal F}}'$. Now ${{\Phi({\sigma})}} \cap (\Delta^+_{{\mathcal F}}\cup \Delta^+_{{{\mathcal F}}'}) = {{\Phi({\sigma})}} \setminus \{(2,2m)\}$. If we take ${{\mathcal F}}''=\{2,3,2m-1,2m\}$ then $\theta_{{{\mathcal F}}''}(\sigma) = (3,1,2,4)$ is irreducible with $(2,2m) \in {{\Phi({\sigma})}} \cap \Delta^+_{{{\mathcal F}}''}$ and $(2,3) \in {{\Phi({\sigma})}} \cap \Delta^+_{{\mathcal F}}\cap \Delta^+_{{{\mathcal F}}''}$. Hence Corollary \[technical cor\] implies that $\sigma$ is irreducible. \(3) Suppose $\sigma= (n-1,n-3,n-5,\dots,3,1,n,n-2,n-4,\dots,4,2)$. Take ${{\mathcal F}}= \{1,2,\dots,n\} \setminus \{1,m+1\}$ and ${{\mathcal F}}' = \{1,2,\dots,n\} \setminus \{m,2m\}$. Then $\theta_{{\mathcal F}}(\sigma) = \theta_{{{\mathcal F}}'}(\sigma) = \sigma= (n-3,n-5,\dots,3,1,n-2,n-4,\dots,4,2)$ is again exceptional and so is irreducible by the induction hypothesis. Also the root $(2,2m-1)$ shows that ${{\mathcal F}}$ and ${{\mathcal F}}'$ are $\sigma$-connected. Then ${{\Phi({\sigma})}} \cap (\Delta^+_{{\mathcal F}}\cup \Delta^+_{{{\mathcal F}}'}) = {{\Phi({\sigma})}} \setminus \{(1,m), (1,2m), (m+1,2m)\}$. For ${{\mathcal F}}''=\{1,m,m+1,2m\}$ we have $\theta_{{{\mathcal F}}''}(\sigma) = (3,1,4,2)$ which is irreducible with ${{\Phi({\sigma})}} \cap \Delta^+_{{{\mathcal F}}''} = \{(1,m), (1,2m), (m+1,2m)\}$. Finally if we take ${{\mathcal F}}''' = \{2,m,m+1,2m\}$ we have $\theta_{{{\mathcal F}}'''}(\theta) = (3,1,4,2)$ and ${{\mathcal F}}'''$ is $\sigma$-connected to both ${{\mathcal F}}$ and ${{\mathcal F}}''$ since $(2,m), (m+1,2m) \in {{\Phi({\sigma})}}$. Thus $\sigma$ is irreducible. \(4) Finally suppose that $\sigma = (m, 2m, m-1, 2m-1,m-2,2m-2,\dots,2,m+2,1, m+1)$. It is straightforward to verify that $\sigma=(3,6,2,5,1,4)$ is irreducible. Thus we suppose $2m \geq 8$. Let ${{\mathcal F}}= \{1,2,\dots,2m\}\setminus\{2,2m-1\}$, ${{\mathcal F}}' = \{1,2,\dots,2m\}\setminus\{m,2m\}$ and ${{\mathcal F}}'' = \{1,2,\dots,2m\}\setminus\{1,m+1\}$. Then $\theta_{{\mathcal F}}(\sigma) = \theta_{{{\mathcal F}}'}(\sigma)= \theta_{{{\mathcal F}}'}(\sigma)=(m-1, 2m-2, m-2, 2m-3,\dots,2,m+1,1, m)$ is exceptional and so is irreducible by induction. Also ${{\mathcal F}}$ and ${{\mathcal F}}'$ are $\sigma$-connected by $(1,3)$ and ${{\mathcal F}}$ and ${{\mathcal F}}''$ are $\sigma$-connected by $(2m-2,2m)$. Since $\Delta_{{{\mathcal F}}}^+ \cup \Delta_{{{\mathcal F}}'}^+ \cup \Delta_{{{\mathcal F}}''}^+ = \Delta_{2m}^+$, Corollary \[technical cor\] implies that $\sigma$ is irreducible. Let $\sigma \in S_n$. Choose $k$ with $1 \leq k \leq n$ and put ${{\mathcal F}}= \{1,2,\dots,n\} \setminus \{k\}$. The permutation $\sigma^\circ=\theta_{{\mathcal F}}(\sigma) \in S_{n-1}$ is called a <span>*one point deletion*</span> of $\sigma$. The following theorem, expressed in the language of posets, was first proved by Schmerl and Trotter @ST. For a proof using permutations we refer the reader to @AA\[Theorem 5\]. Let $n \geq 2$ and suppose $\sigma \in S_n$ is simple but not exceptional. Then $\sigma$ has a one point deletion $\sigma^\circ$ which is simple. \[simple implies irreducible\] Let $\sigma \in S_n$ with $n \geq 4$. The permutation $\sigma$ is simple if and only if it is atomic and irreducible. First suppose $\sigma$ is atomic and irreducible and express $\sigma$ in simple form: $\sigma=\sigma_0[\beta_1,\beta_2,\dots,\beta_m]$ with $\beta_a \in S_{z_a}$ for $a=1,2,\dots,m$. By Lemma \[irreducible under inflation\], exactly one of the permutations $\sigma_0,\beta_1,\beta_2,\dots,\beta_m$ is a non-identity permutation. If $\sigma_0={{\rm Id}}_m$ then the simplicity of $\sigma$ implies that $\beta_1 \neq {{\rm Id}}$. Similarly, if $\sigma_0={{\rm Id}}_m$ we cannot have $\beta_m={{\rm Id}}$. Thus $\sigma_0 \neq {{\rm Id}}$. Therefore $\sigma=\sigma_0[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_m}]$. Since $\sigma$ is atomic, this implies that $z_a=1$ for all $a$. But then $\sigma=\sigma_0$ is simple. Next we suppose that $\sigma$ is simple. It follows immediately, from the definition that $\sigma$ is atomic. We prove that simple implies irreducible by induction. For the base case, we have $n=4$ and this implies that $\sigma$ is exceptional. Thus $\sigma$ is irreducible by Lemma \[exceptional\]. We prove the induction step by contradiction. Suppose $n \geq 5$ and that $\sigma \in S_n$ is simple. If $\sigma$ is exceptional then the result follows from Lemma \[exceptional\]. Thus we suppose that $\sigma$ is not exceptional and assume by way of contradiction that ${{\Phi({\sigma})}}= {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$. Let the simple permutation $\sigma^\circ\in S_{n-1}$ be a one point deletion of $\sigma$. By the induction hypothesis, $\sigma^\circ$ is irreducible. Suppose that $\sigma^\circ = \theta_{{\mathcal F}}(\sigma)$ where ${{\mathcal F}}= \{1,2,\dots,n\} \setminus \{k\}$ and $\sigma(k) = \ell$. Since $\sigma^\circ$ is irreducible we may assume without loss of generality that $\{(i,j) \in {{\Phi({\sigma})}} \mid i \neq k, j\neq k\} \subseteq {{\Phi({\sigma_1})}}\ .$ Assume, by way of contradiction, that ${{\Phi({\sigma_2})}} \neq \emptyset$. Write ${{\Phi({\sigma_2})}} = \{(i_1,k),(i_2,k),\dots,(i_p,k)\} \sqcup \{(k,i'_1),(k,i'_2),\dots,(k,i'_q)\}$ and $j_a=\sigma(i_a)$ for $a=1,2,\dots,p$ and $j'_a = \sigma(i'_a)$ for $a=1,2,\dots a$. Define $s=\max\{k-i_a,j_a-\ell \mid 1\leq a \leq p\}$. We consider two cases. For the first case, suppose that $s=k-i_b$ for some $b$ with $1 \leq b \leq p$. If $s=n-1$ then we must have $k=n$ and $i_b=1$. Since $\sigma$ is simple, $j_b \neq 1$ and $\ell \neq 1$. Hence, $i_0 :=\sigma^{-1}(1)$ satisfies $1 < i_0 < k=n$. Taking ${{\mathcal F}}= \{1,i_0,n\}$, we find $\theta_{{\mathcal F}}(\sigma)=(312)$. Then $\theta$ carries the decomposition ${{\Phi({\sigma})}} = {{\Phi({\sigma_1})}} \sqcup {{\Phi({\sigma_2})}}$ to a non-trivial decomposition of $(312)$ since $(1,i_0) \in {{\Phi({\sigma_1})}}$ and $(1,n)\in {{\Phi({\sigma_2})}}$. This contradiction shows $s \neq n-1$. The $s\times s$ square ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s := [k-s,k]\times[\ell,\ell+s]$ is contained in $ [1,n]\times[1,n]$. Since $\sigma$ is simple and $1 \leq s \leq n-2$, the graph of $\sigma$ has at most $s$ points within ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$. Then the simplicity of $\sigma$ implies that there is a point $V=(i_0,j_0)$ of the graph of $\sigma$ either strictly above ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$ or strictly below ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$. If $V$ is above ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$, i.e, if $k-s \leq i_0 \leq k$ and $\ell + s < j_0$ then taking ${{\mathcal F}}= \{i_b,i_0,k\}$, we find $\theta_{{\mathcal F}}(\sigma)=(231)$. Then $\theta$ the decomposition of ${{\Phi({\sigma})}}$ induces a non-trivial decomposition of $(231)$ since $(i_b,k) \in {{\Phi({\sigma_2})}}$ and $(i_0,k)\in {{\Phi({\sigma_1})}}$. This contradiction shows $V$ must be strictly below ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$. Thus $k-s \leq i_0 \leq k$ and $j_0 < \ell$. For ${{\mathcal F}}=\{i_b,i_0,k\}$, we have $\theta_{{\mathcal F}}(\sigma)=(312)$. This yields a non-trivial decomposition of $(312)$ since $(i_b,i_0) \in {{\Phi({\sigma_1})}}$ and $(i_b,k) \in {{\Phi({\sigma_2})}}$. Again we have a contradiction. For the second case, suppose that $s=j_b-\ell$ for some $b$ with $1 \leq b \leq p$. If $s=n-1$, then $j_b=n$ and $\ell=1$. The simplicity of $\sigma$ implies that $i_b \neq n$ and $k\neq n$. With ${{\mathcal F}}= \{i_b,k,n\}$ we have $\theta_{{\mathcal F}}(\sigma)=(312)$. Since $(i_b,k) \in {{\Phi({\sigma_2})}}$ and $(i_b,n) \in {{\Phi({\sigma_1})}}$, the decomposition of ${{\Phi({\sigma})}}$ induces a non-trivial decomposition of $(312)$. This contradiction shows that $s \neq n-1$, Therefore $1 \leq s \leq n-2$, By the simplicity of $\sigma$, the square ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$ contains at most $s$ points of the graph of $\sigma$. Hence there is a point $V=(i_0,j_0)$ of the graph of $\sigma$ either strictly to the right of ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$ or strictly to the left of ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$. If $V$ is to the left of ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$, i.e, if $i_0 < k-s \leq i_b < k$ and $\ell \leq j_0 \leq \ell+s$ then we consider ${{\mathcal F}}=\{i_0,i_b,k\}$. Then $\theta_{{\mathcal F}}(\sigma)=(231)$. By the definition of $s$, we have $(i_0,k) \in {{\Phi({\sigma_1})}}$ Also $(i_b,k) \in {{\Phi({\sigma_2})}}$. Hence the decomposition of ${{\Phi({\sigma})}}$ induces a non-trivial decomposition of $(231)$, a contradiction. Conversely, if $V$ is to the right of ${{\raisebox{0.7ex}{\framebox[0.62em][c]{\ }}}}_s$ then $i_b < k < i_0$ and $\ell \leq j_0 \leq \ell+s$. Taking ${{\mathcal F}}=\{i_b,k,i_0\}$ we have $\theta_{{\mathcal F}}(\sigma)=(312)$. Now $(i_b,k) \in {{\Phi({\sigma_2})}}$ and $(i_b,i_0) \in {{\Phi({\sigma_1})}}$. Thus the decomposition of ${{\Phi({\sigma})}}$ yields a non-trivial decomposition of $(312)$, a contradiction. These contradictions imply that $p=0$, i.e., there are no roots of the form $(i_a,k)$ in ${{\Phi({\sigma_2})}}$. The same proof works, mutatis mutandis, to show that there are no roots of the form $(k,i'_a) \in {{\Phi({\sigma_2})}}$. Thus ${{\Phi({\sigma_2})}}$ must be empty and so ${{\Phi({\sigma})}}$ is irreducible as required. The following corollary follows immediately from Lemma \[complements are simple\] and Proposition \[simple implies irreducible\]. The corollary is required for our proof of Theorem \[main theorem\] and is the motivation for proving Proposition \[simple implies irreducible\]. \[main cor\] Suppose that $\sigma \in S_n$ is simple. Then ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma$ is irreducible. We now give our proof of Theorem \[main theorem\] First we suppose that $\Delta_n^+ = {{\Phi({w_1})}} \sqcup {{\Phi({w_2})}} \sqcup \dots \sqcup {{\Phi({w_r})}}$ is an irreducible decomposition. Without loss of generality, the highest root $(1,n)$ is an element of ${{\Phi({w_1})}}$. Express $w_1 = \sigma_1[\beta_{11},\beta_{12},\dots,\beta_{1m}]$ in simple form. It is easy to see that $(1,n) \in {{\Phi({w_1})}}$ implies that $\sigma_1 \neq {{\rm Id}}$. By Lemma \[irreducible under inflation\], $\sigma_1$ is irreducible. If $\sigma_1={{w_{\rm o}\tlist@if@empty@nTF{m}{}{ [m]}}}$ this implies that $m=2$ since $\Delta^+_m = {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{m}{}{ [m]}}})}} = {{\Phi({\sigma})}} \sqcup {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{m}{}{ [m]}}\sigma})}}$ gives a non-trivial decomposition for any $\sigma \in S_m \setminus \{{w_{\rm o}\tlist@if@empty@nTF{m}{}{ [m]}},{{\rm Id}}_m\}$ when $m\geq 3$. Since $w_1$ is irreducible, by Lemma \[irreducible under inflation\], we must have $w_1 = {w_{\rm o}\tlist@if@empty@nTF{2}{}{ [2]}}[{{\rm Id}},{{\rm Id}}]$ if $w_1$ is minus-decomposable. If $\sigma_1 \neq {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$, then $\sigma_1$ must be simple and $m \geq 4$. Let $\{1,2,\dots,n\} = I_1 \sqcup I_2 \sqcup \dots \sqcup I_m$ be the intervals corresponding to the simple form $w_1 = \sigma_1[\beta_{11},\beta_{12},\dots,\beta_{1m}]$ with $|I_a| = z_a$. Since $w_1$ is irreducible, we must have $w_1= \sigma_1[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_m}]$. We have ${{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}w_1})}} = {{\Phi({w_2})}} \sqcup {{\Phi({w_3})}} \sqcup \dots \sqcup {{\Phi({w_r})}}$. Let ${{\mathcal F}}$ be an admissible set. Then $\theta_{{\mathcal F}}(w_1)=\sigma_1$. Since ${{\Phi({{w_{\rm o}\tlist@if@empty@nTF{n}{}{ [n]}} w_1})}} ={{\Phi({w_1})}}^\text{c}$, we must have ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}w_1= ({w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1)[{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}},{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}},\dots,{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}]$. Then since ${{\mathcal F}}$ is admissible, $\theta_{{\mathcal F}}({w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}w_1)= {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1$. The element ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1$ is simple by Corollary \[main cor\]. Applying Lemma \[technical\], we see that there exists $\delta({{\mathcal F}})$ such that ${{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}w_1})}} \subset {{\Phi({w_{\delta({{\mathcal F}})}})}}$. Suppose ${{\mathcal F}}$ is admissible and $1 \leq a \leq m$. We claim that there exists a root $(s,t)\in {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1})}}$ $s\neq a$ and $t \neq a$. This is clear since otherwise ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma$ has ${{\rm Id}}_{m-1}$ as a one point deletion. Since $m \geq 4$, it is clear that this cannot happen since ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma$ is simple. If $|I_a| > 1$ then let $i_a \in {{\mathcal F}}\cap I_a$ and $i'_a \in I_a \setminus {{\mathcal F}}$ and construct a new admissible set by replacing $i_a$ by $i'_a$, i.e., ${{\mathcal F}}' := ({{\mathcal F}}\setminus \{i_a\}) \cup \{i'_a\}$. Write $\{i_s\} = I_s \cap {{\mathcal F}}= I_s \cap F'$ and $\{i_t\} = I_t \cap {{\mathcal F}}= I_t \cap F'$. Since $(s,t)\in {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1})}}$ it follows that $(i_s,i_t) \in {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}w_1})}} \cap \Delta^+_{{\mathcal F}}\cap \Delta^+_{{{\mathcal F}}'}$. Therefore ${{\mathcal F}}$ and ${{\mathcal F}}'$ are ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}w_1$-connected. From this it follows that any two admissible sets are ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}w_1$-path-connected. This implies that $\delta({{\mathcal F}})$ is constant for all admissible sets ${{\mathcal F}}$. Without loss of generality, we have $\delta({{\mathcal F}})=2$ for all admissible sets ${{\mathcal F}}$. Hence ${{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1})}} \subset {{\Phi({\theta_{{\mathcal F}}(w_2)})}}$. Assume, by way of contradiction, that this is a proper inclusion. Then there exists $(a,b) \in {{\Phi({\theta_{{\mathcal F}}(w_2)})}} \setminus {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1})}}$. Then $(i_a,i_b) \in {{\Phi({w_1})}} \cap \Delta^+_{{\mathcal F}}$ where $\{i_a\} = {{\mathcal F}}\cap I_a$ and $\{i_b\} = I_b \cap {{\mathcal F}}$. But $(a,b) \in {{\Phi({\theta_{{\mathcal F}}(w_2)})}}$ implies that $(i_a,i_b) \in {{\Phi({w_2})}} \cap \Delta^+_{{\mathcal F}}$. Thus $(i_a,i_b) \in {{\Phi({w_1})}} \cap {{\Phi({w_2})}}$. This contradiction shows that ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1 = \theta_{{\mathcal F}}(w_2)$. Since ${w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1 = \theta_{{\mathcal F}}(w_2)$ for all admissible sets ${{\mathcal F}}$, we see that $$\{(i_a,i_b) \in {{\Phi({w_2})}} \mid i_a \in I_a, i_b \in I_b, a\neq b\} = \{(i_a,i_b) \in \Delta_n^+ \mid i_a \in I_a, i_b \in I_b, (a,b) \in {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1})}}\}\ .$$ Hence ${{\Phi({w_2})}} = \{(i_a,i_b) \in \Delta_n^+ \mid i_a \in I_a, i_b \in I_b, (a,b) \in {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1})}}\} \sqcup \left(\sqcup_{b=1}^m \Delta^+_{I_b} \cap {{\Phi({w_2})}}\right)$. From this it is clear that $w_2 = {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1[\beta_{21},\beta_{22},\dots,\beta_{2m}]$ where $\beta_{2b} = \theta_{I_b}(w_2)$ for all $b=1,2,\dots,m$. But since ${{\Phi({w_2})}}$ is irreducible, we must have $\beta_{21}=\beta_{22}=\dots=\beta_{2m}={{\rm Id}}$ and therefore $w_2 = {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1[{{\rm Id}}_{z_1},{{\rm Id}}_{z_2},\dots,{{\rm Id}}_{z_m}]$ as required. Hence we have shown $$w_1 =\begin{cases} {w_{\rm o}\tlist@if@empty@nTF{2}{}{ [2]}}[{{\rm Id}},{{\rm Id}}],& \text{ if }w_1 \text{ is minus-decomposable};\\ \sigma_1[{{\rm Id}},{{\rm Id}},\dots,{{\rm Id}}] \text{ and } w_2={w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma_1[{{\rm Id}},{{\rm Id}},\dots,{{\rm Id}}],& \text{ if }w_1 \text{ is minus-indecomposable}. \end{cases}$$ Therefore $$\{(i,j)\in\Delta^+_n \mid i \in I_a, j\in I_b, a\neq b\} = \begin{cases} {{\Phi({w_1})}},& \text{ if }w_1 \text{ is minus-decomposable};\\ {{\Phi({w_1})}} \sqcup {{\Phi({w_2})}},& \text{ if }w_1 \text{ is minus-indecomposable}. \end{cases}$$ From this it follows that all other $w_a$ have the form $w_a = {{\rm Id}}_m[\beta_{a1},\beta_{a2},\dots,\beta_{am}]$. Let $\Psi_b$ denote the order preserving bijection $\Psi_b : I_b \to \{1,2,\dots,z_b\}$ for $b=1,2,\dots,m$. Then ${{\Phi({w_a})}} = \sqcup_{b=1}^m \Psi^{-1}({{\Phi({\beta_{ab}})}})$ for all $a=3,4,\dots,r$. Thus we have shown that the characterization of irreducible decompositions given in the statement of the theorem is correct. For general decompositions we use the fact that every decomposition may be realized by beginning with an irreducible decomposition and then merging some collections of the irreducible inversion sets. We consider the effect of such mergers by examining effect of merging pairs of inversion sets. Let $w= \sigma[\beta_1,\beta_2,\dots,\beta_m]$ and $w' = \sigma'[\beta'_1,\beta'_2,\dots,\beta'_m]$ with $\beta_b,\beta'_b \in S_{z_b}$ for $b=1,2,\dots,m$ and $\sigma,\sigma' \in S_n$. It is easy to see that $${{\Phi({w})}} \sqcup {{\Phi({w'})}} = {{\Phi({\mu})}}$$ where $\mu=\nu[\gamma_1,\gamma_2,\dots,\gamma_m]$ where ${{\Phi({\sigma})}} \sqcup {{\Phi({\sigma'})}} = {{\Phi({\nu})}}$ and ${{\Phi({\beta_b})}} \sqcup {{\Phi({\beta'_b})}} = {{\Phi({\gamma_b})}}$ for $b=1,2,\dots,m$. Since ${{\Phi({\sigma})}} \sqcup {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\sigma})}} = {{\Phi({{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}})}}$, it follows that the characterization of general decompositions given in the statement of the theorem is correct. Decompositions for Type B {#B section} ========================= Here we consider root systems of type $B_{n}$. In this section and the next, we will consider the Weyl group ${{\mathcal W}}(A_m) \cong S_{m+1}$ as the group of all permutations of the set $\{e_1,e_2,\dots,e_{m+1}\}$. With this notation, the positive roots are $\Delta_{A_m}^+ = \{(i,j)=e_i-e_j \mid 1 \leq i < j \leq m\}$. We denote the positive roots for the root system of type $B_n$ by $$\Delta^+_{B_n} = \{\varepsilon_i - \varepsilon_j \mid 1 \leq i < j \leq n\} \sqcup \{\varepsilon_i + \varepsilon_j \mid 1 \leq i < j \leq n\} \sqcup \{\varepsilon_i \mid 1 \leq i \leq n\}.$$ The set of simple roots in $\Delta^+_{B_n}$ is $\{\varepsilon_i - \varepsilon_{i+1} \mid 1 \leq i \leq n-1\} \sqcup \{\varepsilon_n\}$. For type $B_n$ the Weyl group ${{\mathcal W}}(B_n)$ is the set of signed permutations of the set $$\{\varepsilon_1,\varepsilon_2,\dots,\varepsilon_n,0,-\varepsilon_n,\dots,-\varepsilon_2,-\varepsilon_1 \}.$$ These are the permutations $\sigma$ of this set such that $\sigma(0)=0$ and $\sigma(-\varepsilon_i)=-\sigma(\varepsilon_i)$ for all $1 \leq i \leq n$. Abstractly, ${{\mathcal W}}(B_n) \cong S_n \rtimes ({{\mathbb Z}}/2{{\mathbb Z}})^{n}$. For $1 \leq i \leq 2n+1$ we define $i' := (2n+2)-i$. It is convenient to define $\varepsilon_i = -\varepsilon_{i'}$ for $1 \leq i \leq 2n+1$ and $\varepsilon_{n+1}=0$. We embed ${{\mathcal W}}(B_n)$ in ${{\mathcal W}}(A_{2n})$ by the group homomorphism $\sigma \mapsto \tilde{\sigma}$ where $\tilde{\sigma}(e_i)=e_k$ if $\sigma(\varepsilon_i) = \varepsilon_k$. The condition that $\sigma(-\varepsilon_i)=-\sigma(\varepsilon_i)$ implies that if $\tilde{\sigma}(e_i)=e_k$ then $\tilde{\sigma}(e_{i'})=e_{k'}$. This condition is equivalent to the condition that the graph of $\tilde{\sigma}$ is invariant under a rotation of $\pi$ radians about the point $(n+1,n+1) \in {{\mathbb R}}^2$. We say that a permutation in $S_{2n+1}$ is <span>*symmetric*</span> if it satisfies these two equivalent conditions. Consider the involution $\mu$ of $\Delta_{A_{2n}}^+$ induced by $\mu(e_i)=-e_{i'}$. Note that the elements of $\Delta_{A_{2n}}^+$ fixed pointwise by $\mu$ are precisely the positive roots $e_i - e_{i'}$ for $i=1,2,\dots,n$. We define the map $\rho: \Delta_{A_{2n}} \to \Delta_{B_n}$ by $\rho(e_i - e_j) = \begin{cases} \varepsilon_i - \varepsilon_j,& \text{if } j \neq {i'},i;\\ \varepsilon_i=(\varepsilon_i-\varepsilon_j)/2& \text{if } j = i'. \end{cases}$\ Since $\tilde{\sigma}(e_i - e_{i'}) = e_k -e_{k'}$ we have $\sigma(\rho(\alpha))=\rho(\tilde{\sigma}(\alpha))$ for all $\alpha \in \Delta_{A_{2n}}$. Observe that $\rho(\mu(\alpha))=\rho(\alpha)$ for all $\alpha \in \Delta^+_{A_{2n}}$. Suppose $\alpha=e_i-e_j \in \Delta_{A_{2n}}^+$.\ Observe that $\rho(\alpha) = \begin{cases} \varepsilon_i - \varepsilon_j, &\text{if }1 \leq i < j \leq n;\\ \varepsilon_i, &\text{if } 1 \leq i \leq n, j=n+1;\\ \varepsilon_i + \varepsilon_{j'}, &\text{if } 1 \leq i \leq n, n+2 \leq j \leq 2n+1 \text{ with } j \neq i';\\ \varepsilon_i, &\text{if } 1 \leq i =j' \leq n;\\ \varepsilon_{j'}, &\text{if } i=n+1 < j \leq 2n+1;\\ \varepsilon_{i'} - \varepsilon_{j'}, &\text{if } n+2 \leq i < j \leq 2n+1. \end{cases}$.\ Thus $\rho(\Delta^+_{A_{2n}}) = \Delta^+_{B_n}$. Clearly $\rho(\Delta^-_{A_{2n}}) = \Delta^-_{B_n}$ also. Suppose $\sigma \in {{\mathcal W}}(B_n)$. Then $\rho({{\Phi({\tilde{\sigma}})}}) = {{\Phi({\sigma})}}$. Let $\alpha \in \Delta_{A_{2n}}^+$ and let $\beta = \tilde{\sigma}(\alpha)$. Then $\rho(\alpha) \in \Delta^+_{B_n}$. Now $\alpha \in {{\Phi({\tilde{\sigma}})}}$ if and only if $\beta \in \Delta^-_{A_{2n}}$ if and only $\rho(\beta) \in \Delta^-_{B_n}$. Since $\rho(\beta) = \sigma(\rho(\alpha))$ this implies $\alpha \in {{\Phi({\tilde{\sigma}})}}$ if and only if $\rho(\alpha) \in {{\Phi({\sigma})}}$. Thus $\rho({{\Phi({\tilde{\sigma}})}}) = {{\Phi({\sigma})}}$ Let $\sigma \in {{\mathcal W}}(B_n)$ and let $1 \leq i \leq n$. Then $e_i - e_{n+1} \in {{\Phi({\tilde{\sigma}})}}$ if and only if $e_i - e_{i'} \in {{\Phi({\tilde{\sigma}})}}$. Furthermore $\alpha \in {{\Phi({\tilde{\sigma}})}}$ if and only if $\mu(\alpha) \in {{\Phi({\tilde{\sigma}})}}$ for all $\alpha \in \Delta^+_{A_{2n}}$. In particular, if ${{\Phi({\tilde{\sigma}})}}\cap \rho^{-1}(\gamma) \ne \emptyset$ then ${{\Phi({\tilde{\sigma}})}}\supset \rho^{-1}(\gamma)$ for all $\gamma \in \Delta^+_{B_n}$. First we suppose that $e_i - e_{n+1} \in {{\Phi({\tilde{\sigma}})}}$. Then $\mu(e_i - e_{n+1}) = e_{n+1} - e_{i'} \in {{\Phi({\tilde{\sigma}})}}$. Hence by the closed property $e_i - e_{i'} = (e_i - e_{n+1}) + (e_{n+1} - e_{i'}) \in {{\Phi({\tilde{\sigma}})}}$. Conversely, suppose $e_i - e_{n+1} \notin {{\Phi({\tilde{\sigma}})}}$. Then $\mu(e_i - e_{n+1}) = e_{n+1} - e_{i'} \notin {{\Phi({\tilde{\sigma}})}}$ and the co-closed property shows that $e_i - e_{i'} \notin {{\Phi({\tilde{\sigma}})}}$. For the second assertion write $\alpha = e_i - e_j$ (with $i < j$) and write $\tilde{\sigma}(\alpha) = e_k - e_\ell$. Then $\tilde{\sigma}(\mu(\alpha)) = \tilde{\sigma}(e_{j'} - e_{i'}) = e_{\ell'}-e_{k'}$. Hence $\alpha \in {{\Phi({\tilde{\sigma}})}}$ if and only if $k > \ell$ if and only if $\ell' > k'$ if and only if $\mu(\alpha) \in {{\Phi({\tilde{\sigma}})}}$. The final assertion follows from the above. The following corollary follows immediately from the preceding lemma. Let $\sigma_1, \sigma_2 \in {{\mathcal W}}(B_n)$ with ${{\Phi({\tilde{\sigma}_1})}} \cap {{\Phi({\tilde{\sigma}_2})}} = \emptyset$. Then $\rho({{\Phi({\tilde{\sigma}_1})}} \sqcup {{\Phi({\tilde{\sigma}_2})}}) = \rho({{\Phi({\tilde{\sigma}_1})}}) \sqcup \rho({{\Phi({\tilde{\sigma}_2})}})$. In particular, suppose $\sigma_1,\sigma_2,\dots,\sigma_r \in {{\mathcal W}}(B_n)$. Then $\Delta_{B_n}^+ = \sqcup_{i=1}^r {{\Phi({\sigma_r})}}$ if and only if $\Delta_{A_{2n}}^+ = \sqcup_{i=1}^r {{\Phi({\tilde{\sigma}_r})}}$. Furthermore the element $\sigma_1 \in {{\mathcal W}}(B_n)$ is indecomposable if and only if $\tilde{\sigma}_1 \in {{\mathcal W}}(A_{2n})$ is indecomposable. The embedding of ${{\mathcal W}}(B_n)$ into ${{\mathcal W}}(A_{2n})$ allows us to define an inflation operation for Weyl groups of type B as follows. Let $m \leq n$ and let $\{1,2,\dots,m\} = I_1 \sqcup I_2 \sqcup \dots I_r$ be a decomposition into intervals. Put $z_t = |I_t|$ for $t=1,2,\dots,r$. Suppose that $\sigma_0 \in {{\mathcal W}}(B_r)$, $\tau_{r+1} \in {{\mathcal W}}(B_{n-m})$ and $\tau_t \in S_{z_t}$ for $t=1,2,\dots,r$. We form the inflation $\tilde{\sigma} = \tilde{\sigma}_0[\tau1,\tau_2,\dots,\tau_r,\tilde{\tau}_{r+1},\tau_{r+2},\dots,\tau_{2r+1}]$ where $\tau_{2r+2-t} = {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\tau_t {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$ for $t=1,2,\dots,r$. Then $\tilde{\sigma} \in {{\mathcal W}}(A_{2n})$ is symmetric and so corresponds to an element $\sigma \in {{\mathcal W}}(B_n)$. We say that $\sigma$ is an inflation in ${{\mathcal W}}(B_n)$. An element $\sigma \in {{\mathcal W}}(B_n)$ which cannot be realized as such an inflation in ${{\mathcal W}}(B_n)$ except with $r=0$ or $r=n$ is said to be simple in ${{\mathcal W}}(B_n)$. The proof of the following lemma is straight forward and left to the reader. \[B symmetric inflations\] If $\alpha[\tau_1,\tau_2,\dots,\tau_s] \in {{\mathcal W}}(A_{2n})$ is symmetric then $\alpha$ must be symmetric, $s$ is odd, and $\tau_{s+1-t} = {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\tau_t {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$ for all $t=1,2,\dots,s$. Let $\sigma \in {{\mathcal W}}(B_n)$. Then $\sigma$ is simple in ${{\mathcal W}}(B_n)$ if and only if $\tilde{\sigma}$ is simple (in ${{\mathcal W}}(A_{2n})$). If $\tilde{\sigma}$ is simple in ${{\mathcal W}}(A_{2n})$, then $\tilde{\sigma}$ cannot be realized as a non-trivial inflation and so cannot be realized as a non-trivial inflation in ${{\mathcal W}}(B_n)$. Conversely, suppose that $\sigma$ is simple in ${{\mathcal W}}(B_n)$. Assume by way of contradiction that $\tilde{\sigma}$ is not simple. Then $\tilde{\sigma} =\alpha[\tau_1,\tau_2,\dots,\tau_s]$. Since $\tilde{\sigma} \in S_{2n+1}$ is symmetric, Lemma \[B symmetric inflations\] shows that $\sigma$ is an inflation in ${{\mathcal W}}(B_n)$. \[B symmetric main theorem\] Let $\Delta_{B_n}^+ = {{\Phi({w_1})}} \sqcup {{\Phi({w_2})}} \sqcup \dots \sqcup {{\Phi({w_r})}}$ be a decomposition with all ${{\Phi({w_a})}} \neq \emptyset$. Then (after possibly reordering) we have $$\begin{aligned} \tilde{w}_1 &= & \tilde{\sigma}_1[\beta_{11},\beta_{12},\dots,\beta_{1(2s+1)}]\\ \tilde{w}_2 &= & \tilde{\sigma}_2[\beta_{21},\beta_{22},\dots,\beta_{2(2s+1)}]\\ & & \vdots\\ \tilde{w}_r &= & \tilde{\sigma}_r[\beta_{r1},\beta_{r2},\dots,\beta_{r(2s+1)}] \end{aligned}$$ where $\sigma_1,\sigma_2,\dots,\sigma_r \in {{\mathcal W}}(B_s)$, $\beta_{qt} = {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\beta_{q(2s+2-t)}{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$ for all $q=1,2,\dots,r$ and all $t=1,2,\dots,2s+1$ and $$(\dag)\quad {{\Phi({\beta_{1b}})}} \sqcup {{\Phi({\beta_{2b}})}} \sqcup \dots \sqcup {{\Phi({\beta_{rb}})}} = \Delta^+_{A_{z_b}} \text{ is a decomposition} \qquad \forall b=1,2,\dots,2s+1$$ and $\sigma_q= \sigma_{q+1}=\dots=\sigma_r={{\rm Id}}$ with $$\begin{cases} \tilde{\sigma}_1 = {w_{\rm o}\tlist@if@empty@nTF{2s+1}{}{ [2s+1]}} \text{ and } q=2,& \text{if }w_1\text{ is minus-decomposable};\\ \sigma_1 \text{ is ${{\mathcal W}}(B_s)$ simple},\ \tilde{\sigma}_2={w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\tilde{\sigma}_1 \text{ and } q=3,& \text{if } w_1 \text{ is minus-indecomposable.} \end{cases}$$ Moreover, the above decomposition of $\Delta_{B_n}^+$ is irreducible if and only if the decompositions $(\dag)$ are irreducible for all $b$, exactly one of $\beta_{a1},\beta_{a2},\dots,\beta_{a(s+1)}$ is not equal to ${{\rm Id}}$ for each $a=q,q+1,\dots,r$, and $$ s=1 \_<span>11</span>=\_<span>13</span>=<span><span>Id</span></span>\_<span>z\_1</span> \_<span>12</span>=<span><span>Id</span></span>\_<span>z\_2</span>,& w\_1\ \_<span>1b</span>=\_<span>2b</span>=<span><span>Id</span></span>\_<span>z\_b</span> b=1,2,…,2s+1,& w\_1 $$ Decompositions for Type C {#C section} ========================= In this section we consider root systems of type $C_{n}$. We denote the positive roots for the root system of type $C_n$ by $$\Delta^+_{B_n} = \{\varepsilon_i - \varepsilon_j \mid 1 \leq i < j \leq n\} \sqcup \{\varepsilon_i + \varepsilon_j \mid 1 \leq i \leq j \leq n\}.$$ The set of simple roots in $\Delta^+_{C_n}$ is $\{\varepsilon_i - \varepsilon_{i+1} \mid 1 \leq i \leq n-1\} \sqcup \{2\varepsilon_n\}$. The Weyl group ${{\mathcal W}}(C_n)$ is the set of signed permutations of the set $$\{\varepsilon_1,\varepsilon_2,\dots,\varepsilon_n,-\varepsilon_n,\dots,-\varepsilon_2,-\varepsilon_1 \}.$$ Abstractly, ${{\mathcal W}}(C_n) \cong {{\mathcal W}}(B_n) \cong S_n \rtimes ({{\mathbb Z}}/2{{\mathbb Z}})^{n}$. For $1 \leq i \leq 2n$ we define $i' := (2n+1)-i$ and put $\varepsilon_i = -\varepsilon_{i'}$ for $1 \leq i \leq 2n$. We embed ${{\mathcal W}}(C_n)$ in ${{\mathcal W}}(A_{2n-1})$ by the group homomorphism $\sigma \mapsto \tilde{\sigma}$ where $\tilde{\sigma}(e_i)=e_k$ if $\sigma(\varepsilon_i) = \varepsilon_k$. Again the condition that $\sigma(-\varepsilon_i)=-\sigma(\varepsilon_i)$ implies that if $\tilde{\sigma}(e_i)=e_k$ then $\tilde{\sigma}(e_{i'})=e_{k'}$. This condition is equivalent to the condition that the graph of $\tilde{\sigma}$ is invariant under a rotation of $\pi$ radians about the point $(n+1/2,n+1/2) \in {{\mathbb R}}^2$. We say that a permutation in $S_{2n}$ is <span>*symmetric*</span> if it satisfies these two equivalent conditions. As in the previous section, we define $\mu$ to be the involution of $\Delta_{A_{2n-1}}^+$ induced by $\mu(e_i)=-e_{i'}$. Then $\mu$ has no fixed points in $\Delta_{A_{2n-1}}^+$. We define the map $\rho: \Delta_{A_{2n-1}} \to \Delta_{C_n}$ by $\rho(e_i - e_j) = \varepsilon_i - \varepsilon_j$. Then $\rho(\mu(\alpha))=\rho(\alpha)$ for all $\alpha \in \Delta^+_{A_{2n}}$. Suppose $\alpha=e_i-e_j \in \Delta_{A_{2n-1}}^+$.\ Then $\rho(\alpha) = \begin{cases} \varepsilon_i - \varepsilon_j, &\text{if }1 \leq i < j \leq n;\\ \varepsilon_i + \varepsilon_{j'}, &\text{if } 1 \leq i \leq n, n+1 \leq j \leq 2n \text{ with } j \neq i';\\ 2\varepsilon_i, &\text{if } 1 \leq i=j' \leq n;\\ \varepsilon_{i'} - \varepsilon_{j'}, &\text{if } n+1 \leq i < j \leq 2n. \end{cases}$.\ Thus $\rho(\Delta^+_{A_{2n-1}}) = \Delta^+_{C_n}$ and $\rho(\Delta^-_{A_{2n-1}}) = \Delta^-_{C_n}$. As in the previous section, this implies that $\rho({{\Phi({\tilde{\sigma}})}}) = {{\Phi({\sigma})}}$ for $\sigma \in {{\mathcal W}}(C_n)$. Also if ${{\Phi({\tilde{\sigma}})}}\cap \rho^{-1}(\gamma) \ne \emptyset$ then ${{\Phi({\tilde{\sigma}})}}\supset \rho^{-1}(\gamma)$ for all $\sigma \in {{\mathcal W}}(C_n)$ and $\gamma \in \Delta_{C_n}$. The following corollary follows the above considerations. Let $\sigma_1, \sigma_2 \in {{\mathcal W}}(C_n)$ with ${{\Phi({\tilde{\sigma}_1})}} \cap {{\Phi({\tilde{\sigma}_2})}} = \emptyset$. Then $\rho({{\Phi({\tilde{\sigma}_1})}} \sqcup {{\Phi({\tilde{\sigma}_2})}}) = \rho({{\Phi({\tilde{\sigma}_1})}}) \sqcup \rho({{\Phi({\tilde{\sigma}_2})}})$. In particular, suppose $\sigma_1,\sigma_2,\dots,\sigma_r \in {{\mathcal W}}(C_n)$. Then $\Delta_{C_n}^+ = \sqcup_{i=1}^r {{\Phi({\sigma_r})}}$ if and only if $\Delta_{A_{2n-1}}^+ = \sqcup_{i=1}^r {{\Phi({\tilde{\sigma}_r})}}$. Furthermore the element $\sigma_1 \in {{\mathcal W}}(C_n)$ is indecomposable if and only if $\tilde{\sigma}_1 \in {{\mathcal W}}(A_{2n-1})$ is indecomposable. As before, the embedding of ${{\mathcal W}}(C_n)$ into ${{\mathcal W}}(A_{2n-1})$ allows us to define an inflation operation for Weyl groups of type C as follows. Let $\{1,2,\dots,n\} = I_1 \sqcup I_2 \sqcup \dots I_r$ be a decomposition into intervals. Put $z_t = |I_t|$ for $t=1,2,\dots,r$. Suppose that $\sigma_0 \in {{\mathcal W}}(C_r)$ and $\tau_t \in S_{z_t}$ for $t=1,2,\dots,r$. We form the inflation $\tilde{\sigma} = \tilde{\sigma}_0[\tau1,\tau_2,\dots,\tau_r,\tilde{\tau}_{r+1},\dots,\tau_{2r}]$ where $\tau_{2r+1-t} = {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\tau_t {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$ for $t=1,2,\dots,r$. Then $\tilde{\sigma} \in {{\mathcal W}}(A_{2n-1})$ is symmetric and so corresponds to an element $\sigma \in {{\mathcal W}}(C_n)$. We say that $\sigma$ is an inflation in ${{\mathcal W}}(C_n)$. An element $\sigma \in {{\mathcal W}}(C_n)$ which cannot be realized as such an inflation in ${{\mathcal W}}(C_n)$ except with $r=1$ or $r=n$ is said to be simple in ${{\mathcal W}}(C_n)$. As before we have have the following two results. \[C symmetric inflations\] If $\alpha[\tau_1,\tau_2,\dots,\tau_s] \in {{\mathcal W}}(A_{2n-1})$ is symmetric then $\alpha$ must be symmetric, $s$ is even and $\tau_{s+1-t} = {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\tau_t {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$ for all $t=1,2,\dots,s$. Let $\sigma \in {{\mathcal W}}(C_n)$. Then $\sigma$ is simple in ${{\mathcal W}}(C_n)$ if and only if $\tilde{\sigma}$ is simple (in ${{\mathcal W}}(A_{2n-2})$). Finally we obtain the analogue of Theorem \[main theorem\] for type $C$. \[C symmetric main theorem\] Let $\Delta_{C_n}^+ = {{\Phi({w_1})}} \sqcup {{\Phi({w_2})}} \sqcup \dots \sqcup {{\Phi({w_r})}}$ be a decomposition with all ${{\Phi({w_a})}} \neq \emptyset$. Then (after possibly reordering) we have $$\begin{aligned} \tilde{w}_1 &= & \tilde{\sigma}_1[\beta_{11},\beta_{12},\dots,\beta_{1(2s)}]\\ \tilde{w}_2 &= & \tilde{\sigma}_2[\beta_{21},\beta_{22},\dots,\beta_{2(2s)}]\\ & & \vdots\\ \tilde{w}_r &= & \tilde{\sigma}_r[\beta_{r1},\beta_{r2},\dots,\beta_{r(2s)}] \end{aligned}$$ where $\sigma_1,\sigma_2,\dots,\sigma_r \in {{\mathcal W}}(C_s)$, $\beta_{qt} = {w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\beta_{q(2s+1-t)}{w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}$ for all $q=1,2,\dots,r$ and all $t=1,2,\dots,2s$ and $$(\dag)\quad {{\Phi({\beta_{1b}})}} \sqcup {{\Phi({\beta_{2b}})}} \sqcup \dots \sqcup {{\Phi({\beta_{rb}})}} = \Delta^+_{A_{z_b}} \text{ is a decomposition} \qquad \forall b=1,2,\dots,2s$$ and $\sigma_q= \sigma_{q+1}=\dots=\sigma_r={{\rm Id}}$ with $$\begin{cases} \tilde{\sigma}_1 = {w_{\rm o}\tlist@if@empty@nTF{2s}{}{ [2s]}} \text{ and } q=2,& \text{if }w_1\text{ is minus-decomposable};\\ \sigma_1 \text{ is ${{\mathcal W}}(C_s)$ simple},\ \tilde{\sigma}_2={w_{\rm o}\tlist@if@empty@nTF{}{}{ []}}\tilde{\sigma}_1 \text{ and } q=3,& \text{if } w_1 \text{ is minus-indecomposable.} \end{cases}$$ Moreover, the above decomposition of $\Delta_{C_n}^+$ is irreducible if and only if the decompositions $(\dag)$ are irreducible for all $b$, exactly one of $\beta_{a1},\beta_{a2},\dots,\beta_{as}$ is not equal to ${{\rm Id}}$ for each $a=q,q+1,\dots,r$, and $$ s=1 \_<span>11</span>=\_<span>13</span>=<span><span>Id</span></span>\_<span>z\_1</span> \_<span>12</span>=<span><span>Id</span></span>\_<span>z\_2</span>,& w\_1\ \_<span>1b</span>=\_<span>2b</span>=<span><span>Id</span></span>\_<span>z\_b</span> b=1,2,…,2s,& w\_1 $$ Enumerative Results {#enumerative section}
{'source': 'arXiv_out/1110'}