We study parabolic double cosets in a Coxeter system  by decomposing them into atom(ic coset)s, a generalization of simple reflections introduced in a joint work with Elias, Libedinsky, Patimo.

We define and classify braid relations between compositions of atoms and prove a Matsumoto theorem.

Our consideration of reduced compositions of atoms gives rise to a new combinatorial structure, which is equipped with a length function and a Bruhat order
and is realized as Tits cone intersections in the sense of Iyama-Wemyss.

§ INTRODUCTION

Let $(W,S)$ be a Coxeter system.
For a subset $J\subset S$ we denote by $W_J$ the parabolic subgroup generated by $J$.
Recall (or see <cit.>) that the associated Coxeter complex $\Com(W,S)$ consists of cells (simplices)  indexed by parabolic left cosets, so that the cell $C_{wW_J}$ corresponding to $wW_J$, where $w\in W$ and $J\subset S$, has dimension $|S\setminus J|-1$. In particular, the maximal cells in $\Com(W,S)$ are indexed by the one-element cosets $wW_\emptyset = \{w\}$.

The Coxeter group $W$ acts naturally on the left cosets in $(W,S)$, thus on the cells in $\Com(W,S)$.
Let us fix a subset $I\subset S$ and consider the subcomplex $\Com(W,S,I)$ in $\Com(W,S)$ consisting of the cells fixed by the action of every $s\in I$.
Then a cell $C_{wW_J}$ in $\Com(W,S)$ is contained in $\Com(W,S,I)$ if and only if the (left) action of $W_I$ on $wW_J$ is trivial, and the latter is if and only if $wW_J=W_IwW_J$.
Thus, given $I\subset S$, we can relabel the cells in $\Com(W,S,I)$ by such double cosets $W_IwW_J$.
The maximal cells in $\Com(W,S,I)$ are then indexed by what we call
the core $(W_I,W_J)$-cosets (where $J\subset S$ varies):

A parabolic double coset $W_I w W_J$ is called a core coset if $W_Iw = W_IwW_J = wW_J$ as sets.

Here is an illustration of the above discussions in an example.

Consider the affine symmetric group $(\widetilde{S_2},\{s,t,u\})$.
can I do it?

A reduced expression $w=s_1\cdots s_\ell$ in $(W,S)$ is read from the left to right to give the sequence

\[[e,s_1,s_1s_2,\ldots ,s_1s_1\cdots s_\ell].\]

We view the sequence as a path going through the coressponding maximal cells in $\Com(W,S)$.
Here $e\in W$ denotes the identity element in the group $W$ and marks the starting point of the path.
One observes that, when moving from one maximal cell to the next, the path actually goes through the (codimension one) face shared by the two maximal cells:

\begin{equation}\label{eq.regex}
[\{e\}\subset \{e,s_1\}\supset \{s_1\}\subset\{s_1,s_1s_2\}\supset\{s_1s_2\}\subset\cdots %\subset \{w s_\ell\inv,w\}
\supset\{w\}]
=[e, eW_{s_1}, s_1, s_1W_{s_2}, s_1s_2 ,\cdots%, wW_{s_\ell}
, w].
\end{equation}

Note that in every `$\supset$' we make a choice of going forward: take the maximal element from the previous step, e.g., take $s_1s_2$ from $\{s_1,s_1s_2\}=s_1W_{s_2}$.
To record (<ref>), it is therefore enough to give the following list of parabolic subsets.

\begin{equation}\label{eq.realregex}
\end{equation}

A main idea of singular Coxeter combinatorics (see <cit.> and <cit.>) is that a path can go through even smaller cells, and that a path can end not only at some $\{w\}$ but at any $wW_J$.
More generally, a path can start at $W_I=W_I e W_I$ instead of at $\{e\}=W_\emptyset e W_{\emptyset}$, in which case our path is a sequence of double cosets rather than of left cosets.
In this generality, a (singular) expression in $(W,S)$ is a sequence

\begin{equation}\label{eq.multiexp}
M_{\bullet} = [[I_0 \subset K_1 \supset I_1 \subset K_2 \supset \ldots \subset K_m \supset I_m]]. \end{equation}

where $I_i,K_i\subset S$ are finitary subsets, i.e., $W_{I_i},W_{K_i}$ are finite.
The finitary restriction is necessary when assigning a path to (<ref>): denoting the unique Bruhat maximal element of a finite double coset $q$ by $\ma{q}$, the (forward) path for (<ref>) is

\[p_\bullet=[[p_0,p_1,\cdots,p_{2m}]]\quad\text{where}\quad p_{2i+1} = p_{2i}W_{K_i} \text{ and }p_{2i} = \ma{p_{2i-1}}W_{I_i}\]

Here $p_{2i+1}$ is an $(I_0,K_i)$-coset and $p_{2i}$ is an $(I_0,I_i)$-coset, and by $(I,J)$-coset we mean $(W_I,W_J)$-double coset; see Section <ref> for more details.
The path $p_\bullet$ ends at the $(I_0,I_m)$-coset $p_{2m}$.
Thus, analogously to the regular case [To be more precise, the singular expressions are not analogous to the Coxeter group $W$ but to the Coxeter monoid $(W,*)$ (see Section <ref>). For reduced expressions, there is no difference between the two variations.], the expression (<ref>) expresses the double coset $p_{2m}$. We write in this case

\[p_{2m}\expr [[I_0 \subset K_1 \supset I_1 \subset K_2 \supset \ldots \subset K_m \supset I_m]].\]

The notion of reduced expressions (resp., reduced paths) for double cosets is introduced also in Williamson <cit.> (see <cit.>, or Definition <ref> and <cit.> for a singlestep formulation; a reduced path is a forward path associated to a reduced expression in the sense of the previous paragraph).
A joint work with Elias <cit.> introduces and classifies the braid relations for double cosets and proves Matsumoto's theorem, i.e., that any two reduced expressions of the same double coset are related by a series of braid relations.

Now suppose $p$ is a core $(I,J)$-coset, for some finitary subsets $I,J\subset S$.
Then $C_p$ is a maximal cell in $\Com(W,S,I)$.
It is thus natural to ask whether there exist $|I|$-regular (expressions and) paths in $\Com(W,S,I)$
that terminates at $p$.
By an $r$-regular expression we mean an expression (<ref>) such that $|I_i|=r$ and $|K_i|=r+1$ hold, exactly like a regular expression (<ref>) does. Its
path alternates between two types of moves:

* from a maximal cell $C_{W_IwW_{I_i}}$ to its $s_{i+1}$-face
$C_{W_IwW_{K_{i+1}}}$ (where  $K_{i+1}=I_i\sqcup\{s_{i+1}\}$),

* from a face $C_{W_IwW_{K_i}}$ to the adjacent maximal cell $C_{W_IyW_{I_i}}$ where $y=\ma{W_IwW_{K_i}}$,

from a maximal cell to its codimension one face and from a codimension one face to a maximal cell,
exactly like a regular path (<ref>) does.
The answer is positive and appears in a joint work with Elias-Libedinsky-Patimo <cit.> (see Proposition <ref>).
In fact, <cit.> shows that there is a reduced expression with the above condition and calls it an
atomic reduced expression. To explan the terminology, let us start with atoms.

An atom (or an atomic coset) is
a core coset of the form $W_{K\setminus s}w_{K}W_{K\setminus t}$, where $K\subset S$ is finitary and $s,t\in K$.

Here $w_K$ denotes the maximal element in $W_K$, and it is straightforward that the core coset condition implies $t=w_Ksw_K$.
A further justification of the definition (in addition to that they are the simplest core cosets) is given by the fact that an atom has a unique reduced expression (see Proposition <ref>).
An atomic (reduced) expression then refers to a (reduced) composition of atoms, identifying the atoms with their unique reduced expressions. For example, if $\at=W_{I}w_{K}W_{J}$
and $\atb = W_Jw_LW_M$ are atoms, then
their unique reduced expressions are

\[\at\expr [[I\subset K\supset J]],\quad \atb \expr [[J\subset L\supset M]]\]

and we have

\[ \at\circ \atb \expr [[I\subset K\supset J\subset L\supset M]].\]

Thus the forementioned result of <cit.> says that a core coset decomposes as a reduced composition of atoms.
In all above senses, an atom, in the study of (core) double cosets, plays the same role as what a simple reflection $s\in S$ plays in Coxeter combinatorics.

The purpose of the current work is to understand the relations between atomic expressions. For reduced expressions, we achieve this in the atomic Matsumoto theorem:

Two atomic reduced expressions of the same core coset are related by atomic braid relations.

We refer to Definition <ref> for its definition, but an atomic braid relation is of the form

\begin{equation}\label{eq.atomicbr}
\underbrace{\at \circ \atb' \circ \at''\cdots}_{m} = \underbrace{\atb \circ \at' \circ \atb''\cdots}_{m}     ,
\end{equation}

where $\at,\atb$ are atoms; the atoms $\at',\at'',\cdots$ and  $\atb',\atb'',\cdots$ are certain twists of the atoms $\at$ and $\atb$, respectively, determined by their position in the composition; and $m=m_{\at,\atb}\geq 2$ is an integer (in general not equal to one of the entries in the Coxeter matrix for $(W,S)$). See also Proposition <ref> and Proposition <ref>.
We point out a key feature of our braid relations, a feature the braid relations from <cit.> do not enjoy: the two sides of (<ref>) are of the same width.
Due to this feature, the combinatorics of atomic reduced expressions very much resembles that of regular reduced expressions in a Coxeter group, bringing us a substantial computational and pedagogical advantage over the presentation in <cit.>.

The non-reduced (atomic or not) expressions depend on different natural ways of composing double cosets in a non-reduced way. We consider two of them, namely the singular Coxeter monoid $\SC$ studied in <cit.> (see Section <ref>) and the nilCoxeter algebroid $\Dem$ studied in <cit.> (see Section <ref>).
As is implicit above, we use the adjective  `singular' to mean `of parabolic double cosets'.
In particular $\SC$ is the double coset analogue of the Coxeter monoid, and $\Dem$ is that of the nilCoxeter algebra (the name comes from $\Dem$ being equivalent to the category of singular Demazure operators, i.e., Demazure operators associated to parabolic double cosets), and they differ only in the quadratic relations, namely, $ss=s$ in the Coxeter monoid and $ss=0$ in the nilCoxeter algebra.
As can be guessed from the quadratic relation, it is easier to deal with non-reduced expressions in $\Dem$: they are equal to zero. For this category we obtain a presentation theorem Theorem <ref>.

We restricted ourselves to core double cosets in the above. Let us justify.
Let $p$ be a $(I,J)$-coset. The left (resp. right) redundancy of $p$ is the subset

\begin{equation*}\label{introeq.red}
\leftred(p) = I\cap \mi{p}J\mi{p}\inv\subset I,\quad \text{resp.,}\quad \rightred(p) = \mi{p}\inv I\mi{p} \cap J\subset J,
\end{equation*}

where $\mi{p}$ denotes the unique minimal element in $p$ (see Section <ref> for more details).
We have $W_{\leftred(p)} = W_I\cap \mi{p}W_J\mi{p}$ (see e.g., <cit.>), which says that the redundancy encodes the redundancy in combining the left action and the right action of $W_I$ and $W_J$.
In particular, the coset $p$ is core if and only if $I=\leftred(p)$ and $J=\rightred(p)$.
Then a result from <cit.> (see Proposition <ref>) says that $p^{\core}=W_{\leftred(p)}\mi{p}W_{\rightred(p)}$ is a core $(\leftred(p),\rightred(p))$-coset and our coset $p$ has a reduced expression of the form

\begin{equation}\label{introeq.lowroad}
[[I\supset \leftred(p)]]\circ M_\bullet \circ [[\rightred(p)\subset J]]
\end{equation}

where $M_\bullet$ is a reduced expression for $p^{\core}$.

This allows us to reduce problems on arbitrary double cosets to that on core cosets.

For example, if an $(I,J)$-coset $p$ corresponds to a cell in $\Com(W,S,I)$, then we have $\leftred(p)=I$, $\rightred(p)=\mi{p}\inv I\mi{p}\subset J$, and $p^{\core}=W_I\mi{p}W_{\rightred(p)}$. The cell $p$ is not maximal in $\Com(W,S,I)$ if and only if the last inclusion $\rightred(p)\subset J$ is strict.
In this case $p$ is a face of the maximal cell $p^{\core}$ in $\Com(W,S,I)$.
Therefore, if we take a reduced path $p_\bullet$ in $\Com(W,S,I)$ for $p^{\core}$ then we obtain such a path for $p$ by adding to $p_\bullet$ the final extra step of restricting to a face. This extra step is the postcomposition $-\circ [[\rightred(p)\subset J]]$ in (<ref>).

Now that we have given purely combinatorial motivations for our work, let us explain our original motivations from the study of Hecke categories.
In the forementioned joint work <cit.> with Elias, Libedinsky, Patimo, we construct a cellular-like basis of the singular Hecke category (also known as the singular Soergel bimodules <cit.>) associated to $(W,S)$. The latter is a categorification of the Hecke algebroid and is the double coset analogue of the regular Hecke category (Soergel bimodules).
In constructing our basis elements, called light leaves, a crucial step is to find desirable (with conditions depending on the situation) reduced expressions of double cosets.
The result of <cit.> providing reduced expressions of the form (<ref>) is one main ingredient for the step. Another important ingredient is to find a reduced expression $M_\bullet$ of a core coset.
In type $A$ and type $B$, as proved in <cit.>, the atomic reduced expressions are exactly the same as the regular reduced expressions in type $A$ and type $B$ respectively, and thus finding $M_\bullet$ reduces to the well-understood problem of finding a regular reduced expression of an element in a Coxeter group (of type $A$ and $B$).
This vastly simplifies the basis construction in finite and affine types $A$ and $B$.
In fact, the latter is the original motivation of <cit.> for initiating the atomic theory of Coxeter systems.

Finally, we mention an unexpected (or, expected but unexpectedly strong; see <cit.>) connection to a work of Iyama-Wemyss <cit.>, discovered in the final stage of the project.
<cit.> introduces a new combinaorial structure $\cone(W,S,I)$, associated to a Coxeter system $(W,S)$ and a subset $I\subset S$, which they call a Tits cone intersection.
They develop combinatorics of Tits cone intersections in affine type $ADE$ to describe the tilting theory for contracted preprojective algebras (certain idempotent summands of preprojective algebras) as well as the noncommutative resolutions for compound Du Val singularities, with eventual applications to birational geometry.
And this $\cone(W,S,I)$ corresponds exactly to $\Com(W,S,I)$ discussed above (under the construction of $\Com(W,S)$ as a quotient of the Tits cone; see Section <ref>).
In particular, the chambers in $\cone(W,S,I)$ are labeled by the core $(I,J)$-cosets (see Proposition <ref>).
When we explain the connection in Section <ref>, we work in the Tits cone instead of the Coxeter complex for a more convenient comparison to <cit.>, but the explanation is implicit in <cit.> and in our discussion in the introduction.

To be more precise, we recall that the Tits cone $\cone(W,S)\subset V^*$, associated to $(W,S)$ and its geometric realization $V$, has cells labelled by the parabolic left cosets.
Some of these left cosets are also right cosets, and, as shown in <cit.>, the cells corresponding to such cosets $W_Iw=wW_J$, where $w\in W$ and $I,J\subset S$, form a subset $\cone(W,S,I)$ of the Tits cone $\cone(W,S)$ which is realized also as the intersection of $\cone(W,S)$ and the $s$-hyplanes in $V^*$ for all $s\in s$.
<cit.> calls $\cone(W,S,I)$ the Tits cone intersection and shows that the

Now observe that $W_Iw=wW_J$ readily implies $W_IwW_J=W_Iw=wW_J$ is a double coset, and moreover a core double coset.
This establishes the bijection between the chambers in $\cone(W,S,I)$ and the
See (the proofs of) Proposition <ref> for more details.

This provides $\cone(W,S,I)$ with additional information obtained in the current paper, in particular, the atomic braid relations, the atomic Matsumoto theorem, and a presentation by generators and relations (see
Proposition <ref>).
Conversely, the results in <cit.> shed a new light on the singular Coxeter monoid $\SC$ and the nilCoxeter algebroid $\Dem$.

We do not explore such consequences in the current paper, but content with
referring to <cit.> for a beautifully illustrated classification of the arrangements of $(I,J)$-core cosets, where $I$ is fixed of order $|S|-3$ and $S$ is of affine type.

§.§ Organization of the paper

Section <ref> introduces some algebraic structures commonly associated to a Coxeter system: Section <ref> recalls basic definitions and fix notation; Section <ref> recalls the singular Coxeter monoid $\SC$; Section <ref> recalls the nilCoxeter algebroid $\Dem$.
Section <ref> introduces core cosets and the atom(ic coset)s and state necessary facts from <cit.>.
Section <ref> explains the switchback relations from <cit.> and  how they gives rise to atomic braid relations.
Section <ref> proves the atomic Matsumoto theorem.
Section <ref> discusses atomic non-braid relations and give a presentation by generators and relations of the nilCoxeter algebroid.
In Section <ref> and Section <ref>, we consider the substructures $\coreJ{J}$ of $\SC$ and $\Dem^{\core}_J$ of $\Dem$ consisting of the $(I,J)$-core cosets and study their combinatorics.
Section <ref> completely describe $\coreJ{J}$ and $\Dem^{\core}_J$ when $|S\setminus J|=2$; Section <ref> discusses the weak Bruhat order on $\coreJ{J}$, resp., $\Dem^{\core}_J$, and computes some examples when $|S\setminus J|>2$.
Section <ref> relates our $\coreJ{J}$ and $\Dem^{\core}_J$ with <cit.>'s Tits cone intersection.

§.§ Acknowledgements.

The main ideas in the paper came from discussions with Ben Elias, Nicolas Libedinsky and Leonardo Patimo during our joint expedition in the singular land; additional thanks to ELP for agreeing about posting the current paper before its prequel <cit.>.
The technical portion of the project benefited from examples of atomic expressions computed on SageMath.

§ SINGULAR COXETER PRESENTATIONS

In this section we collect some basics of Coxeter combinatorics and recall two presentations of parabolic double cosets by generators and relations, from <cit.> and <cit.> respectively.
Let $(W,S)$ be a Coxeter system.

§.§ Coxeter group preliminaries

Given an element $x\in W$ the (Coxeter) length $\ell(x)$ is the smallest length of an expression of $x\in W$, i.e., the smallest $\ell$ where $x=s_1s_2\cdots s_\ell$ for some $s_i\in S$.
A product $xy$, for $x,y\in W$, is said to be reduced if $\ell(xy)=\ell(x)+\ell(y)$. In this case we write $xy=x.y$.
An expression $w=s_1s_2\cdots s_m$, where $s_1,s_2,\cdots,s_m\in S$, is called a reduced expression if every product involved in computing the expression, in any order, is reduced.
The latter condition is equivalent to the product

\[(s_1\cdots s_i)s_{i+1}\]

being reduced for each $i=1,\cdots, m-1$, which also is equivalent to the length $m$ of the expression being the shortest possible, i.e., $m=\ell(x)$.
The left (resp., right) descent set of $w\in W$ is defined and denoted as

\[\leftdes(w) = \{s\in S\ |\ sw\text{ is not reduced}\},\quad \text{ resp., }\quad \rightdes(w)=\{s\in S\ |\ ws\text{ is not reduced}\}.\]

A subset $I\subset S$ is said to be finitary if the parabolic subgroup $W_I$ generated by $I$ is finite.
Given finitary $I,J\subset S$ we consider an $(I,J)$-coset by which we mean an element in $W_I\backslash W/W_J$.

The left (resp. right) redundancy of an $(I,J)$-coset $\pcoset$ is

\begin{equation}\label{eq.red}
\leftred(p) = I\cap \mi{p}J\mi{p}\inv,\quad \text{resp.,}\quad \rightred(p) = \mi{p}\inv I\mi{p} \cap J.
\end{equation}

An $(I,J)$-coset $\pcoset$ has a unique maximal element, denoted by $\ma{p}$, and a unique minimal element, denoted by $\mi{p}$, with respect to the Bruhat order (see, e.g., <cit.>).
Howlett's theorem <cit.> says that, when writing $\ma{p}\in p = W_I\mi{p}W_J$ as a product $x\mi{p} y$, the choice of elements $x\in W_I$, $y\in W_J$ is unique up to the action of the redundancy, that is, the surjective map

\begin{equation}
\begin{aligned}
W_I\times W_J  &\to p  \\
(x,y) &\mapsto x\mi{p}y
\end{aligned}
\end{equation}

induces the bijections

\begin{equation}\label{eq.Howl}
(W_I/W_{\leftred(p)})\times W_J\to p\quad\text{ and }\quad W_I\times (W_{\rightred(p)}\backslash W_J)\to p.
\end{equation}

<cit.> also says that, if $x\in W_I$ is a minimal representative in $xW_{\leftred(p)}$ and $y\in W_J$, or if $x\in W_I$ and $y\in W_J$ is minimal in $W_{\rightred (p)}y$, then we have $x\mi{p}y=x.\mi{p}.y$.

§.§ Coxeter monoids

This subsection briefly introduces the regular and singular Coxeter monoids. We refer to  <cit.> for details.

The Coxeter monoid (also known as the 0-Hecke monoid or the star monoid) $(W,S,*)$ is defined as the monoid with the following presentation by generators and relations. The generator is the set $S$; the generating relations are

* the $*$-quadratic relation for $s \in S$

\[s*s = s;\]

* the braid relation
for $s,t\in S$ with $m=m_{st}<\infty$

\[\underbrace{s * t * \cdots}_{m} = \underbrace{t * s * \cdots}_{m} .\]

An expression $s_1*s_2*\cdots *s_k$ is reduced if its width $k$ is minimal among that of the expressions of the same element in $(W,S,*)$.
If $s*t*\cdots *u$ is a reduced expression in $(W,*)$, then $st\cdots u$ is a reduced expression in the Coxeter group $W$, and we identify the element $w=s*t*\cdots *u\in (W,*)$ with the element $w=st\cdots u\in W$.
This identification import the length function $\ell$ on the Coxeter group $W$ to the Coxeter monoid $(W,*)$ and justifies the following (abuse of) notation: we write $x*y=x.y$ in $(W,*)$ if $\ell(xy)=\ell(x)+\ell(y)$.

The singular Coxeter monoid is the category $\SC=\SC(W,S)$ whose

* objects are the finitary subsets $I\subset S$;

* morphisms, from $I$ to $J$, are the $(I,J)$-cosets, i.e., $\Hom_\SC(I,J) = W_I \backslash W/W_J$;

* composition `$*$', of $\pcoset\in W_I \backslash W/W_J$ and $\qcoset\in W_J \backslash W/W_K$, is given by

\[p*\qcoset = W_I (\ma{p}*\ma{q}) W_K,\]

for finitary subsets $I,J,K\subset S$.

The category $\SC$ is given a presentation by generators and relations in <cit.>.
The generators are the double cosets of the form $W_IeW_{Is}$ and $W_{Is}eW_{I}$, where $Is:=I\sqcup s$ is our notation and $Is\subset S$ is finitary.
The composition of these generators are expressed in two ways.
One way is to list the finitary subsets appearing:

\begin{equation}\label{IInotation}
[I_0,I_1,I_2,\cdots ,I_m] := (W_{I_0}eW_{I_1})*(W_{I_1}eW_{I_2})*\cdots *(W_{I_{m-1}}eW_{I_m})
\end{equation}

The other way is to list the differences between the finitary subsets:

\begin{equation}\label{pmnot}
[I \pm_1 s_1 \pm_2 s_2 \cdots \pm_m s_m] := [I_0,I_1,I_2\cdots ,I_m]
\end{equation}

Here $\pm_i\in\{+,-\}$ and $s_i$ are such that, if $I_is_i=I_{i-1}$ then $\pm_i = -$ and if $I_i=I_{i-1}s_i$ then $\pm_i = +$. We call $m$ the width of the expression (<ref>). (See <cit.> for discussions on the length of an expression, which is not needed for us.)

Under notation (<ref>), the generating relations are

* the up-up relations
\[[I+s+t] \expr [I+t+s] ;\]

* the down-down relations

\[[I-s-t] \expr [I-t-s];\]

* the switchback relations

\[ [I + \sblue - \teal] \expr [I - \textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1}];\]

* the $*$-quadratic relations

\[[I-s+s] \expr [I];\]

where the only condition on $I,s,t$ is that the expressions are well-defined, e.g., $s,t\not\in I$ and $Ist\subset S$ is finitary for the up-up relation.
The elements $u_i\in I\sblue$ are explained in Section <ref> in detail (see in particular Definition <ref> where we call $u_\bullet$ the rotation sequence associated to $(I\sblue,\sblue,\teal)$).
The first three classes of relations are called the braid relations.

For finitary $I,J,K\subset S$, an $(I,J)$-coset $\pcoset$, and a $(J,K)$-coset $\qcoset$, the composition $\pcoset*\qcoset$ is said to be reduced if $(\ma{\pcoset}w_J\inv).\ma{\qcoset}$, or equivalently $\ma{p}.(w_J\inv \ma{q})$, is reduced.

An expression

\[I_\bullet = [I_0,I_1,\cdots,I_m]=(W_{I_0}eW_{I_1})*(W_{I_1}eW_{I_2})*\cdots *(W_{I_{m-1}}eW_{I_m})\]
is reduced if the composition
of the $(I_0,I_{i})$-coset $\pcoset_i = (W_{I_0}eW_{I_1})*(W_{I_1}eW_{I_2})*\cdots *(W_{I_{i-1}}eW_{I_i})$ and the $(I_i,I_{i+1})$-coset $W_{I_{i}}eW_{I_{i+1}}$
is reduced for each of $i=1,\cdots m-1$.
If $1\leq i \leq m-1$ is such that $I_i\supset I_{i+1}$ then the latter condition at $i$ is automatic; if $I_i\supset I_{i+1}$ then reducedness at $i$ is equivalent to the two conditions $\mi{p_i}=\mi{p_{i+1}}$ and $\leftred(p_i)=\leftred(p_{i+1})$.

The condition in Definition <ref> is equivalent to the more symmetric condition

\[I_\bullet =(W_{I_0}eW_{I_1}).(W_{I_1}eW_{I_2}).\cdots .(W_{I_{m-1}}eW_{I_m}),\]

by which we mean every composition that can be involved in the right hand side, in all possible order of composition, is reduced.
See <cit.> for other equivalent criteria and explanations; our formulation in Definition <ref> in terms of redundancy is the original definition from Williamson <cit.>.

The singular Matsumoto theorem <cit.> states that every reduced expression of an $(I,J)$-coset is related by braid relations.

§.§ NilCoxeter algebras

This subsection introduces the nilCoxeter algebras and nilCoxeter algebroids. We follow <cit.> and refer to it for all omitted details.

Let $\kk$ be a field.
The nilCoxeter algebra $\NCA(W,S)$ associated to a Coxeter system $(W,S)$ is the $\kk$-linear algebra presented by generators and relations as follows.
The set of generators is $\{\partial_s\ |\ s\in S\}$;
the generating relations are

* the Coxeter braid relations, that is, for $s,t\in S$ with $m=m_{st}<\infty$

\[\underbrace{\partial_s  \partial_t  \cdots}_{m} = \underbrace{\partial_t  \partial_s \cdots}_{m} \]

* the nil-quadratic relations, that is, for $s\in S$

\[\partial_s \partial_s = 0.\]

Then $\NCA(W,S)$ has a $\kk$-basis indexed by the elements in $(W,S)$, or equivalently the elements in $(W,S,*)$, and moreover has the same reduced expressions as for the Coxeter group $(W,S)$ or the Coxeter monoid $(W,S,*)$.
In fact, $\NCA(W,S)$ is the associated graded of the group algebra $\kk W$ (resp., the linearization of the Coxeter monoid $(W,*)$) filtered with respect to the length function.

The nilCoxeter algebroid, or the singular Demazure algebroid, $\Dem=\Dem(W,S)$ is the $\kk$-linear category whose

objects are the finitary subsets $I\subset S$

and whose morphisms and their composition are defined via the following presentation by generators and relations.

* The generating morphisms are
\begin{equation}\label{eq.demgen}
\partial_{[I,Is]}:Is\to I\quad\text{and}\quad \partial_{[Is,I]}:I\to Is,
\end{equation}

for $Is\subset S$ finitary. That is, a morphism in $\Dem(W,S)$ is a $\kk$-linear combination of compositions of some morphisms of the form (<ref>). We denote such compositions as expressions as in (<ref>) and (<ref>), for example, $\partial_{[I+s-s]}=\partial_{[I,Is,I]}:=\partial_{[I,Is]}\circ \partial_{[Is,I]}$.

* The generating relations are

* the up-up and down-down relations
\[\partial_{[I+s+t]} = \partial_{[I+t+s]}, \quad
\partial_{[I-s-t]} = \partial_{[I-t-s]};\]

* the switchback relation

\[ \partial_{[I + \sblue - \teal]} = \partial_{[I - \textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1}]};\]

* the nil-quadratic relation

\[\partial_{[I-s+s]}= 0.\]

The subset $I\subset S$ and elements $s,t\in S$ involved in the generating relations are only required to make the expressions well-defined, and $u_\bullet\in S$ is the rotation sequence for $(I\sblue,\sblue,\teal)$ (see Definition <ref>).

In other words, $\Dem(W,S)$ has the same presentation as (the liniarization of) $\SC(W,S)$ except it satisfies

the nil-quadratic relation instead of the $*$-quadratic relation.
<cit.> shows that $\Dem(W,S)$ agrees with the category of Demazure operators (on the symmetric algebra of a reflection faithful and balanced realization).
In particular, we have

\begin{equation}\label{eq.kSC=SD}
\Hom_{\Dem(W,S)}(I,J) = \langle \partial_\pcoset\rangle_{\pcoset\in W_I\backslash W/W_J} =\kk\Hom_{\SC(W,S)}(I,J),
\end{equation}

for each morphisms space in $\Dem(W,S)$ where the set $\{\partial_p\ |\ \pcoset\in W_I\backslash W/W_J\}=\Hom_{\SC(W,S)}(I,J)$ is a $\kk$-basis.
Moreover, each basis element $\partial_\pcoset$ has the same reduced expressions as $\pcoset\in W_I\backslash W/W_J$ in $\SC(W,S)$ does.

§ CORE AND ATOMS

This section contains no original content and is based on <cit.>. As <cit.> is not available at the moment, we repeat some of its proofs here.

Let $p$ be an $(I,J)$-coset. We call $p$ a core coset[Note that we call a core coset a coset with full redundancy in <cit.> but switch to the current terminology in all other papers.]  if $\leftred(p) = I$ and $\rightred(p) = J$, or equivalently if $I = \mi{p} J \mi{p}^{-1}$.

It follows from (<ref>) and the suceeding discussion that Definition <ref> is equivalent to Definition <ref>.
The following result allows us to reduce problems on double cosets to that on core cosets.

Given an $(I,J)$-coset $p$, the $(\leftred(p),\rightred(p))$-coset $p^{\core}:=W_{\leftred(p)}\mi{p}W_{\rightred(p)}$ is a core coset. Moreover, if $p^{\core}\expr M_\bullet$ is a reduced expression then

\[p\expr[[I\supset \leftred(p)]]\circ M_\bullet \circ [[\rightred(p)\subset J]]\]

is a reduced expression.

Here is an important observation about reduced expressions of a core coset and of a general coset.
Let $p$ be an $(I,J)$-coset with a reduced expression $p\expr [I_0,\cdots, I_m]$. Letting $p_i\expr[I_0,\cdots,I_i]$, the sequence $\leftred(p_i)$ is decreasing. If furthermore $p$ is core, then $I=\leftred(p_i)$ for all $i\leq m$.

<cit.> proves a number of additional facts on core cosets. In particular, composition of core cosets can be understood as follows.

Let $p$ be a $(I,J)$-coset and $q$ be a $(J,K)$-coset and suppose  $r=p*q$ is reduced.
If $p$ and $q$ are core cosets, then $r$ is a core coset.
Conversely, if $r$ is a core coset and $|J|=|I|=|K|$, then $p$ and $q$ are core cosets.

Let $p,q,r$ be as in the first statement.
We claim that $\mi{p} * \mi{q}*w_K$ is also reduced, which, in this case, is equivalent to $\rightdes(\mi{p} * \mi{q})\cap K= \emptyset$.
In fact, if $s\in \rightdes(\mi{p} * \mi{q})\cap K$, then, by the exchange property (see, e.g., <cit.>), either the product $\mi{q}*s$ or $\mi{p}*t$ is not reduced, where $t= \mi{q}s\mi{q}\inv\in \mi{q}K\mi{q}\inv = J$, contradicting the minimality of $\mi{p}$ in $p$ and $\mi{q}$ in $q$.
It follows, using <cit.>, that

\begin{equation} \mi{p}.\mi{q}.w_K = \mi{p}.\ma{q} = (\ma{p}w_J\inv).\ma{q}
\end{equation}

holds, which says $p*q$ is reduced.

By definition and <cit.>, we have

\begin{equation}\label{lemfoo}
\ma{p*q} = \ma{p}*\ma{q} = \mi{p}*w_J*w_J*\mi{q}=\mi{p}*w_J*\mi{q} =\mi{p}*\mi{q}*w_K,
\end{equation}

in particular, $\mi{p}.\mi{q} \in p*q$.
Note that $\mi{p}.\mi{q}.w_K$ shown above shows that $\mi{p}.\mi{q}$ has a right descent disjoint from $K$, and similarly $\mi{p}.\mi{q}$ has a left descent disjoint from $I$. Thus we have $\mi{p}.\mi{q} = \mi{p*q}$.
Then <cit.> shows that $p*q$ is core, since the right hand side of (<ref>) is equal to $\mi{p}.\mi{q}.w_K = \mi{p*q}.w_K$.
This proves the first claim.

Now we let $r$ be core as in the converse statement. Let us show that $p$ is core. The proof for $q$ is similar, or follows by reversing expressions.
By Lemma <ref> we have $\leftred(r) \subset \leftred(p)$. But $\leftred(r) = I$ and $\leftred(p) \subset I$ so $\leftred(p) = I$. Then $|\rightred(p)|=|I|=|J|$, thus $\rightred(p)=J$ as well. This completes the proof.

Now we introduce the atoms of this paper.

A coset is called an atomic coset (or an atom) if it is a core coset and has a reduced expression of the form $[I+s-t]$.

We emphasize the core condition. In fact, a coset of the form $\pcoset\expr[I+s-t]$ is core exactly when $t = w_{Is} s w_{Is}$.
Thus, the atoms are indexed by the pairs $(I,s)$, with $I\subset S$ finitary and $s\in S\setminus I$.
Another way to characterize an atom among the cosets of the form $\pcoset\expr[I+s-t]$ is that an atom does not allow for braid relations:

An atomic coset has a unique reduced expression. More precisely, a coset of the form $\pcoset\expr[I+s-t]$ is atomic if and only if $\pcoset$ has a unique expression; when $\pcoset$ is not atomic the switchback relation applies.

Thus a single atom is not a subject of investigation. What we study is the composition of atoms:

An expression of the form

\[[L_0,I_0,L_1,I_1,\cdots I_{m-1},L_m]=[L_0+s_1-t_1+\cdots +s_m-t_m]\]

is called an atomic expression if, for each $0\leq i<m$, the coset

\[\at_i\expr [L_i,I_i,L_{i+1}]=[L_i+s_{i+1}-t_{i+1}]\]
is core (thus an atom).

Using Proposition <ref>, we also call a composition of atomic cosets
$\at_1*\at_2*\cdots *\at_m$ an atomic expression. In this sense, a result of <cit.> is that every core coset decomposes into atoms. In fact, it is more precise:

Let $\pcoset$ be a core $(I,J)$-coset.

* For each $\sblue\in \leftdes(\ma{\pcoset})\setminus I$, there is a reduced atomic expression of the form

\[\pcoset\expr [I+\sblue-t+\cdots].\]

* For each $\sblue\in \rightdes(\ma{\pcoset})\setminus J$, there is a reduced atomic expression of the form

\[\pcoset\expr [I+\cdots + u-\sblue].\]

Note that
$\leftdes(\ma{\pcoset})=I$ implies $\ma{\pcoset}=w_I\in W_I$ and thus $\pcoset$ is a trivial $(I,I)$-coset with the empty atomic expression $[I]$.

We prove the first claim by induction on $\ma{p}$. The second claim has a similar proof.
The base case is given by Remark <ref>, which also allows us to assume that $I \subsetneq \leftdes(r)$.

Let $s \in \leftdes(r) \setminus I$.
<cit.> gives a reduced expression $r\expr [I,Is, \ldots, J]$. Let $n$ be the $(Is,J)$-coset such that $r = [I,Is] . n$.
The left redundancy of $n$ is at most the size of $J$, so it is a proper subset of $Is$. By Proposition <ref>, for any $t \in Is \setminus \leftred(n)$, the coset $n$ has a reduced expression of the form $[Is, Is \setminus t, \ldots J]$. Let $q$ be the $(Is \setminus t,J)$-coset such that $n = [Is,Is\setminus t] . q$.
$ r = \at . q$ for $\at \expr[I,Is, Is \setminus t]$. Then $\at$ is an atom and $q$ is a core coset by Lemma <ref>. Since $\ma{q}<\ma{p}$ (see Definition <ref>, the induction step is established.

Atomic relations

§ SWITCHBACK RELATIONS VERSUS ATOMIC BRAID RELATIONS

In this section we fix a finite Coxeter system $(W,S)$ and employ Notation <ref>.
We recommend the reader to have in mind that the discussion in this section is to be applied in the setting where we have a not-necessarily-finite Coxeter system $(\widetilde W,\widetilde S)$ and $S\subset \widetilde S$ is a finitary subset generating $W$ in $\widetilde W$.

For $s\in S$, we write $\con{s} = w_S\inv s w_S$. For $L\subset S$, we write $\Lcon = \{\con{s}\ |\ s\in L\}$.

Behind what follows, we have a subset $L\subset S$ such that $|S\setminus L|=2$, say $S\setminus L = \{\sblue,s'\}$.
If $\scon =s'$ then we set $\teal = \sblue$; if $\scon \neq s'$ then we set $\teal = s'$.
The resulting $\sblue,\teal\in S$ are any two elements with the condition $\teal\neq \scon$ (or equivalently $\sblue\neq \tcon$), and here is where we start.

Our convention throughout the section is that  $\sblue,\teal\in S$ are two elements with the condition $\sblue\neq\tcon$, where $\sblue=\teal$ is possible.

Given $\sblue,\teal\in S$ with $\sblue\neq\tcon$, the rotation sequence associated to $(S,\sblue,\teal)$
is defined as follows.

\begin{equation}\label{eq.u0u-1}
\textcolor{RoyalBlue}{u_0 = s}%\sblue
,\quad \textcolor{Magenta}{\textcolor{Magenta}{u_{-1}} =\tcon}  ,  \quad I_0 =S\setminus u_0,\quad I_{-1} =S\setminus u_{-1} %= S\setminus \sblue, \quad I_{-1} = S \setminus \tcon
\end{equation}

and define the elements $u_i \in S$ and subsets $I_i \subset S$, for $i\in \mathbb Z$, by

\begin{equation} \label{urecurse} u_{i+1} = w_{I_i} u_{i-1} w_{I_i}, \quad I_i = S \setminus u_i. \end{equation}

See <cit.> for further discussions on the rotation sequence and examples (some other examples appear below in Examples <ref>-<ref>), but beware that <cit.> uses the index $(S\setminus\sblue,\sblue,\teal)$ for the rotation sequence we associate to $(S,\sblue,\teal)$. Here we give an alternative characterization of the rotation sequences.

Let $u_\bullet$ be the rotation sequence for $(S,\sblue,\teal)$ and let

\[I_i=S\setminus u_i,\quad L_i=I_i\setminus u_{i-1}.\]

\begin{equation}\label{eq.at_i}
\at_i=[L_i,I_i,L_{i+1}] = [L_i +u_{i-1}-u_{i+1}]
\end{equation}

is an atomic coset for each $i\in\mathbb Z$. Conversely, if $u_i\in S$ and $I_i$ are as above, with the cases $i=0,-1$ given by (<ref>), such that (<ref>) is atomic, then $u_\bullet$ is the rotation sequence for $(S,\sblue,\teal)$.

Both claims are direct consequences of the definitions.

It follows from Proposition <ref> that
\begin{equation}\label{eq.tok}
[L_0,I_0,L_1,I_1,L_2,I_2,\cdots,L_k,I_k,L_{k+1}] = [L_0+ u_{-1}- \textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} %-u_3+\textcolor{black}{u_2}
\ \cdots\ %-u_{k-1}
+u_{k-2} -{u_k}+u_{k-1} - u_{k+1}]
\end{equation}

is an atomic expression for each $k\geq 0$. The expression (<ref>) is reduced if $k$ is small enough, e.g., if $k=0$. This leads to the following definition.

Let $d(S,\sblue,\teal)$ be the maximal $k\geq 0$ such that the atomic expression

\begin{equation}\label{eq.tok2}
[K+ u_{-1}- \textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} %-u_3+\textcolor{black}{u_2}
\ \cdots\ %-u_{k-1}
+u_{k-2} -{u_k}+u_{k-1} - u_{k+1}] ,
\end{equation}

where $K=L_0 =S\setminus\{\sblue,\tcon\}$,
is reduced.

Let $u_\bullet$ be the rotation sequence for $(S,\sblue,\teal)$. Then, for $d =d(S,\sblue,\teal)$, we have $u_d =\teal$. Moreover, the relation

\begin{equation}\label{sb}
[I_0, S, I_d]=[I_0+\sblue-\teal] %&\expr [Lt- \textcolor{black}{u_1} +s -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{d-1}+u_{d-2} -t+u_{d-1}]\\
\expr [I_0- \textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1}] ,
\end{equation}

between two reduced expressions holds.
The relation of this form is called a switchback relation.

In general, a composition of the form $[I\subset J]\circ -$ or $-\circ[I\supset J]$ applied to a reduced expression is a reduced expression (see Definition <ref>; for example, the $(I,J)$-coset $\pcoset\expr[I\subset J]$ has the maximal element $\ma{\pcoset}=w_J$, whence $(w_Jw_J\inv).\qcoset=e.\qcoset=\qcoset$ gives that $[I\subset J]\circ J_\bullet$ is reduced for any reduced expression $\qcoset\expr J_\bullet$).
In particular,

\[ [I_0 -\textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{k-1}+u_{k-2} -{u_k}+u_{k-1}]\]

is reduced if and only if (<ref>) is reduced. Therefore, the claims follow directly from <cit.>.

An observation for later use:

The $(I_0,I_d)$-coset involved in the switchback relation (<ref>) is not a core coset but has the left and right redundancies $L_1=I_0\setminus u_1$ and $L_{d}=I_d\setminus u_{d-1}$ respectively. This can be seen in the left hand side of (<ref>) by direct computations but also in the right hand side of (<ref>) in view of the low road in the sense of <cit.>.

We record an additional information on the rotation sequence.

Let $u_\bullet$ be the rotation sequence for $(S,\sblue,\teal)$ and $d=d(S,\sblue,\teal)$, as above. Then
{u_{d+1} =\scon}$.

By <cit.>, reversing (<ref>) yields the switchback relation for the coset $W_{Ls} w_S W_{Lt}\expr [Ls,S,Lt]$. Thus the rotation sequence $v_\bullet$ appearing in this switchback relation is given by $v_i = u_{d-i}$.
At the same time, the rotation sequence $v_\bullet$ satisfy $\textcolor{Green}{v_0=t}$ and $\textcolor{Orange}{v_{-1}=\scon}$ as given in Definition <ref>.
In particular, we have $\textcolor{Orange}{u_{d+1}= v_{-1}=\scon}$ as desired.

The first sentence in the proof of Proposition <ref> says that

\begin{equation}\label{extendsb}
[L_0+ u- \textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1} - u'],
\end{equation}

where $u,u'\in S$ are any elements making (<ref>) well-defined, is reduced.
Among such $u\in S$, a unique choice which makes
$[L_0+ u- {u_1}]$
atomic is $u=u_{-1}$.
Similarly, if the last factor $[L_d+u_{d-1} - u']$ is atomic then $u'=u_{d+1}$ must be the case.
These observations show that (<ref>) extends uniquely to the equality between atomic reduced expressions

\begin{equation}\label{atomicsb}
\begin{aligned}
&[L_0,I_0,S,I_{d},L_{d+1}] \\
&= [L_0 + \textcolor{Magenta}{u_{-1}} + \sblue - \teal - \textcolor{Orange}{u_{d+1}}]\\
& \expr [L_0 +\textcolor{Magenta}{u_{-1}} -\textcolor{black}{u_1}+\textcolor{black}{\textcolor{RoyalBlue}{u_0}} -\textcolor{black}{u_2} +\textcolor{black}{u_1} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1} - \textcolor{Orange}{u_{d+1}}]
\end{aligned}
\end{equation}

\begin{equation*}\label{eq.sbatomic}
%+ u_{-1}- \textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1} - u_{d+1}
+\textcolor{Magenta}{u_{-1}} -\textcolor{black}{u_1}+\textcolor{black}{\textcolor{RoyalBlue}{u_0}} -\textcolor{black}{u_2} +\textcolor{black}{u_1} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1} - \textcolor{Orange}{u_{d+1}}]
\end{equation*}

which also agrees with the maximal atomic expression from Definition <ref>.

Now we obtain a new atomic reduced expression for (<ref>) giving rise to a `slightly zoomed out' relation between expressions of double cosets.

For each pair $\sblue,\teal \in S$ such that $\teal \neq \scon$, the relation

\begin{equation}\label{eq.atombraid}
\begin{aligned}
&[K +\textcolor{Magenta}{u_{-1}} -\textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1} - \textcolor{Orange}{u_{d+1}}]\expr\\
&[K+\textcolor{RoyalBlue}{\ucon_{d+1}} -\textcolor{black}{\ucon_{d-1}} +\textcolor{Magenta}{\ucon_d} -\textcolor{black}{\ucon_{d-2}} +\textcolor{black}{\ucon_{d-1}} -\ucon_{d-3}+\textcolor{black}{\ucon_{d-2}} \ \ldots\ -\ucon_{1}+\ucon_{2} -\textcolor{Orange}{\ucon_0}+\ucon_{1}- \textcolor{Green}{\ucon_{-1}}]
\end{aligned}
\end{equation}

holds, where $K=S\setminus \{\sblue,\tcon\}$, the rotation sequence $u_\bullet$ is associated to the triple $(S,\sblue,\teal)$, and $d=d(S,\sblue,\teal)$.
In terms of the generating relations in $\SC$, the relation (<ref>) is the composition

\begin{equation}\label{eq.braidcomp}
\begin{aligned}
&[K +\textcolor{Magenta}{u_{-1}} -\textcolor{black}{u_1}+\textcolor{RoyalBlue}{u_0} -\textcolor{black}{u_2} +\textcolor{black}{u_1} -u_3+\textcolor{black}{u_2} \ \ldots\ -u_{d-1}+u_{d-2} -\textcolor{Green}{u_d}+u_{d-1} - \textcolor{Orange}{u_{d+1}}]\\
&\underset{switchback}{\expr}[K +\textcolor{Magenta}{u_{-1}} +\textcolor{RoyalBlue}{u_0} -\textcolor{Green}{u_d}- \textcolor{Orange}{u_{d+1}}]\\
&\underset{downdown}{\overset{upup}{\expr}}[K +\textcolor{RoyalBlue}{u_0} +\textcolor{Magenta}{u_{-1}} - \textcolor{Orange}{u_{d+1}}-\textcolor{Green}{u_d}]=[K +\textcolor{RoyalBlue}{\ucon_{d+1}} +\textcolor{Magenta}{\ucon_d} - \textcolor{Orange}{\ucon_0}-\textcolor{Green}{\ucon_{-1}}]\\
&\underset{switchback}{\expr}[K+\textcolor{RoyalBlue}{\ucon_{d+1}} -\textcolor{black}{\ucon_{d-1}} +\textcolor{Magenta}{\ucon_d} -\textcolor{black}{\ucon_{d-2}} +\textcolor{black}{\ucon_{d-1}} -\ucon_{d-3}+\textcolor{black}{\ucon_{d-2}} \ \ldots\ -\ucon_{1}+\ucon_{2} -\textcolor{Orange}{\ucon_0}+\ucon_{1}- \textcolor{Green}{\ucon_{-1}}]
\end{aligned}
\end{equation}

where the middle relations is the composition of two commuting relations upup and downdown.

Note that $K=L_0$ and the first relation in (<ref>) is (<ref>) written reversed.
The next relation (upup and downdown) in (<ref>) is clear and, since $\textcolor{RoyalBlue}{u_0}=\sblue =\textcolor{RoyalBlue}{\ucon_{d+1}}$, by Lemma <ref>, and $\textcolor{Green}{u_d} =\teal = \textcolor{Green}{\ucon_{-1}}$, by Proposition <ref>, we arrive at the expression

\begin{equation}\label{eqafteruudd}
[K + \textcolor{RoyalBlue}{\ucon_{d+1}}+ \textcolor{Magenta}{u_{-1}} - \textcolor{Orange}{u_{d+1}} - \textcolor{Green}{\ucon_{-1}}].
\end{equation}

The expression (<ref>) contains the non-atomic expression

\begin{equation}\label{tconscon}
[K\sblue+\textcolor{Magenta}{u_{-1}} - \textcolor{Orange}{u_{d+1}}] = [K\sblue+ \tcon - \scon]
\end{equation}

where the equality between the elements is given again by Lemma <ref>.
The switchback relation for (<ref>) differ from (<ref>) by the automorphism $u\mapsto \ucon$ and reversing the expression, namely,

\begin{equation}\label{sb2}
\begin{aligned}
[Ks%S\setminus \con{t}
, S, S\setminus \con{s}] &\expr [Ks%(S\setminus \con{t})
- \textcolor{black}{\ucon_{d-1}} +\tcon -\textcolor{black}{\ucon_{d-2}} +\textcolor{black}{\ucon_{d-1}} -\ucon_{d-3}+\textcolor{black}{\ucon_{d-2}} \ \ldots\ -\ucon_{1}+\ucon_{2} -\scon+\ucon_{1}]\\
&=[Ks%(S\setminus \con{t})
- \textcolor{black}{\ucon_{d-1}} +\textcolor{Magenta}{\ucon_d} -\textcolor{black}{\ucon_{d-2}} +\textcolor{black}{\ucon_{d-1}} -\ucon_{d-3}+\textcolor{black}{\ucon_{d-2}} \ \ldots\ -\ucon_{1}+\ucon_{2} -\textcolor{Orange}{\ucon_0}+\ucon_{1}].
\end{aligned}
\end{equation}

Putting (<ref>) back into (<ref>), we obtain the rest of (<ref>).
This completes the proof.

The atomic braid relation associated to $(S,s,t)$, for $t\neq\con{s}$, is the relation  (<ref>).

The atomic braid relation (<ref>) is analogous to the regular braid relation, say between two simple generators $a$ and $b$, with $m_{ab} = d+1$. For example,

If $S=\{s,t\}$,
then (<ref>) is exactly the regular braid relation

\[ \{\underbrace{st\cdots}_{m_{st}}\} \expr \underbrace{[\emptyset,\{s\},\emptyset,\{t\},\emptyset,\cdots ]}_{2m_{st}} \expr \underbrace{[\emptyset,\{t\},\emptyset,\{s\},\emptyset, \cdots ]}_{2m_{st}}\expr\{\underbrace{ts\cdots}_{m_{st}}\}.\]

A switchback relation with $d=1$ is of the form $[+s-t]=[-t+s]$ (this happens when $s,t$ belong to different irreducible compoments of $S$), so the associated atomic braid relation is the $m=2$ braid relation given by the composition

\begin{equation}
[K+u-s+t-v]\underset{switchback}{\expr} [K+u+t-s-v]\underset{downdown}{\overset{upup}{\expr}} [K+t+u-v-s]\underset{switchback}{\expr} [K+t-v+u-s].
\end{equation}

If $S$ is of type $A$, a switchback relation has either $d=1$ or $d=2$. So the atomic braid relations in this case are either described in Example <ref> or of the form resembling the $m=3$ braid relation.

In a general (finite) type, the number $d+1$ may be strictly bigger than any $m_{st}$ for $s,t\in S$. Here is an example in type $D_4$ with $d+1 = 4$

\[[\{s_1,s_3\}+s_2 -s_2+s_4 -s_4+s_2 -s_2+s_4 -s_4]\expr
[\{s_1,s_3\}+s_4 -s_4+s_2 -s_2+s_4 -s_4+s_2 -s_2],\]

where $s_2$ is the special element in $S=\{s_1,\cdots,s_4\}$ corresponding to the hub of the $D_4$ Dynkin diagram.
Here is an example in type $E_8$ with $d+1 = 8$

\begin{equation*}
\begin{aligned}
&[K +s_1 -s_3 +s_4-s_7+s_3-s_5+s_7-s_7+s_5-s_3+s_7-s_4+s_3-s_1+s_4-s_4]\\
[K +s_4-s_4+s_1-s_3+s_4-s_7+s_3-s_5+s_7-s_7+s_5-s_3+s_7-s_4+s_3-s_1]
\end{aligned}
\end{equation*}

where $K=\{s_2, s_3, s_5, s_6, s_7, s_8\}$ and it is an exercise for the reader to find how we index $S=\{s_1,\cdots,s_8\}$.

The atomic braid relation associated to $(S,s,t)$ is the same as that associated to $(S,\con{t},\con{s})$.
It follows that the atomic braid relations are parametrized by the (unordered) subsets

\[\{\{s,t\}\subset S\ |\ t\neq\con{s}\},\]
while the switchback relations are parametrized by the ordered pairs

\[\{(s,t)\in S\times S\ |\ t\neq\con{s}\}.\]

The full list of the switchback relations, for irreducible $S$, is given in <cit.>, and <cit.> shows that the switchback relation for $(S,s,t)$ is trivial, i.e., of the form $[L+s-t]\expr[L+t-s]$ when $s,t$ belong to different connected component of $S$ and has the same form as the switchback relation for $(S^0,s,t)$ if $s,t\in S^0$ for a connected component $S^0$.
This gives a classification of the atomic braid relations.

An implicit point of Proposition <ref> is another characterization of atomic braid relations, which we make explicit in the following two propositions.

Let $s,t\in S$ be such that $t\neq \con{s}$ and let

\[p\expr [K+\tcon + \sblue - \teal - \scon].\]

Then the reduced expression graph of $\pcoset$ is of the form (<ref>) (together with the expressions obtained by upup only, or downdown only, in the middle, as in (<ref>) below).

By Proposition <ref> and Matsumoto's theorem <cit.>, it is enough to show that no braid relation in $\SC$ other than what appears in (<ref>) is applicable to each of the four (plus two, hidden behind the commutativity of upup and downdown) expressions in (<ref>).

First consider the first expression in (<ref>).
Since it has alternating signs, no upup or downdown relation is applicable. Also, by Proposition <ref> and Proposition <ref>, no switchback relation is applicable to any $[u_{i-1}-u_{i+1}]$.
Therefore it remains to note that the only (consecutive) subexpression where a switchback relation is applicable is
$[-u_1\ \cdots + u_{d-1}]$, since such a subexpression cannot start earlier or later for sign reasons and cannot be a subexpression of $[-u_1\ \cdots + u_{d-1}]$ by maximality of $d$ in switchback relations.

For the second expression in (<ref>), it is clear that there is one place that upup is applicable, one place that downdown is applicable, and one place that switchback is applicable.

For the hidden expressions $[K+\tcon + \sblue - \scon -\teal]$ and $[K+ \sblue +\tcon -\teal - \scon]$, no switchback is applicable to the atomic subexpressions $[\sblue - \scon]$ and $[\tcon -\teal]$, respectively, and thus upup and downdown are the only applicable relations.

The rest follows by symmetry.

Let $\pcoset$ be a double coset of the form $\pcoset\expr[K+s+t-v-u]$.

*  If $\pcoset$ has a rex graph of the form

\begin{equation}\label{atomicbraidgraph}
\begin{tikzcd}%[ampersand replacement=\&, column sep=small, row sep=small]
&[3em]&[3em]  \arrow[dl,dash,swap,"downdown"] E_3 \arrow [dr,dash,"upup"]  &[3em]&[3em]   \\
E_1 \arrow[r,dash,"switchback"] & E_2   \arrow [dr,dash,swap,"upup"]    &  &  \arrow[dl,dash,"downdown"] E_5  &  E_6 \arrow[l,dash,"switchback"]\\
& & E_4 & & ,
\end{tikzcd}
\end{equation}

where $E_1,\cdots ,E_6$ are the reduced expressions of $\pcoset$,
then the composition $E_1\expr E_6$ is an atomic braid relation.

* If $t\neq w_{Kst} v w_{Kst}$ and if applying the switchback relation for $[+t-v]$ in $[K+s+t-v-u]$ yields an atomic expression, then the rex graph of $\pcoset$ is of the form (<ref>) (which gives an atomic braid relation by Part (<ref>)).

We set $ S = Kst$ and, by renaming, assume that $t\neq \con{v}$ (if $t=\con{v}$ then swap $v$ and $u$ and apply the downdown relation).

Let us prove the first statement.
Let $p\expr [K+s+t-v-u]$ has a rex graph (<ref>).
Switchback, upup, and downdown relations are applicable to $[K+s+t-v-u]$ so we have to have  $[K+s+t-v-u]=E_2$, up to the symmetry of (<ref>).
Then $E_1$ is of the form $[K+s -u_1+u_0 -u_2 + u_1 \ \cdots - u_d + u_{d-1} -u]$ with the rotation sequence $u_\bullet$. Since $E_1$ has no other edge in the graph, it involves no other switchback relations, in particular, $[+s-u_1]$ and $[+u_{d-1} - u]$ are atomic.
The latter implies $s=u_{-1}$ and $u = u_{d+1}$ (see remark <ref>) and the claim is proved.

Now suppose the right hand side of

\[[K+s+t-v-u]\underset{switchback}{\expr}[K+s -u_1+u_0 -u_2 + u_1 \ \cdots - u_d + u_{d-1} -u]\]
is atomic. Then we have $s=u_{-1}$ and $u = u_{d+1}$, and Proposition <ref> and Proposition <ref> gives the second statement.

§ THE ATOMIC MATSUMOTO THEOREM

In this section we let $(W,S)$ be an arbitrary Coxeter system and $I,J\subset S$ be finitary subsets.

Given a core $(I,J)$-coset $\pcoset$, any two atomic reduced expressions of $\pcoset$ are related by a composition of atomic braid relations.

Given two atomic expressions $L_\bullet$ and $K_\bullet$ of a core coset, we write $L_\bullet \sim K_\bullet$ if $L_\bullet$ and $K_\bullet$ are related by a composition of atomic braid relations.
Recall that the width of an expression $[L_0,L_1,\cdots, L_m]$ is the number $m$.

We proceed by induction on the minimal width of atomic reduced expressions of $\pcoset$. The base case $\pcoset\expr [I]$ has a unique reduced expression, hence the claim of the theorem is trivially true.

Suppose that the claim is true for every core coset with an atomic reduced expression of width $<m$.

\begin{equation}\label{eq.p=sss}
p\expr L_\bullet = [L_0,L_1,\cdots, L_m] =[I+s-s' +  \ldots - s'']
\end{equation}

\begin{equation}\label{eq.p=ttt}
p\expr K_\bullet = [K_0,K_1,\cdots, K_l] =[I+t-t' + \ldots - t'']
\end{equation}

be two atomic reduced expressions (where $l$ is any positive integer).

If $s=t$, then we also have
$s'= w_{Is} s w_{Is}=t'$ since $L_\bullet,K_\bullet$ are atomic, thus $L_i=K_i$ for $i=0,1,2$. Therefore, $[L_2,\cdots, L_m]\expr [K_2,\cdots, K_l]$ are two atomic reduced expressions covered by the induction hypothesis, and the claim
$L_\bullet\sim K_\bullet$ follows from $[L_2,\cdots, L_m]\sim [K_2,\cdots, K_l]$.

It is thus enough to consider the case $s\neq t$. By <cit.>
, we have $s,t\in \leftdes(\ma{p})$ and by <cit.> there exist reduced expressions (called high roads) of the form

\[p\expr[I,Is,Ist]\circ J_\bullet \expr [I,It,Ist]\circ J_\bullet,\]

where $J_\bullet$ expresses some $(Ist,J)$-coset $\qcoset$.
Then we have

\[\mi{q}\inv J \mi{q}= \mi{q}\inv \mi{p}I \mi{p}\inv \mi{q}\subset W_{Ist} I W_{Ist} = W_{Ist}\]

where we use that $p$ is core in the first equality and $\mi{q}\in W_{Ist}\mi{p}$ in the inclusion.
By Kilmoyer's theorem <cit.>, we obtain $ Ist\supset \mi{q}\inv J\mi{q}$ and thus

\[\leftred(q) = Ist\cap \mi{q}\inv J\mi{q}= \mi{q}\inv J\mi{q}.\]

Note also that $|\leftred(q)| = |J|=|I| = |Ist|-2$. Naming  $\{u,v\} =  Ist\setminus \leftred(q)$, we have by Proposition <ref>

\begin{equation*}
q\expr [Ist - u - v]\circ q^{\core}
\end{equation*}

from which it follows

\begin{equation}\label{eq.pqcore}
p\expr  [I+s+t-v-u]\circ q^{\core}
\end{equation}

We may and do assume that $u\neq w_{Ist}\inv s w_{Ist}$ and $v\neq w_{Ist}\inv t w_{Ist}$, since we can swap $u$ and $v$ if an equality holds.

Applying the switchback relation for $(Ist,\textcolor{RoyalBlue}{t}, \textcolor{Green}{v})$
to (<ref>), we get

\begin{equation}\label{tvsb}
p\expr [I + s {+ \textcolor{RoyalBlue}{t} - \textcolor{Green}{v}} - u ] \circ q^{\core}  \expr [I + s {-u_1 + \textcolor{RoyalBlue}{u_0} - \ldots - \textcolor{Green}{u_d} + u_{d-1}} -u ]\circ q^{\core} .
\end{equation}

By Lemma <ref> below, the expression $[I + s {-u_1 + \textcolor{RoyalBlue}{u_0} - \ldots -\textcolor{Green}{u_d} + u_{d-1}} -u ]$ is atomic. Since $[I+s-s']$ is also atomic (recall the atomic expression (<ref>)) we have $u_1=s'$. For a visual effect let us introduce a new letter $u':=u_{d-1}$.

Now, taking an atomic reduced expression $M_\bullet\expr q^{\core}$, we obtain the atomic expression

\[ [L_0,L_1,L_2\cdots, L_m] =[I+s-s' +  \ldots - s''] \expr [I + s {-s' + \textcolor{RoyalBlue}{t} - \ldots - \textcolor{Green}{v} + u'} -u ]\circ M_\bullet\]

\begin{equation}\label{eq.subtractss'}
[L_2,\cdots,L_m]\expr [(Is\setminus s')+\textcolor{RoyalBlue}{t} - \ldots - \textcolor{Green}{v} + u' -u ]\circ M_\bullet
\end{equation}

where the right hand side, being a subexpression of such, is an atomic reduced expression.
Then induction hypothesis gives $[L_2,\cdots, L_m]\sim  [(Is\setminus s')+\textcolor{RoyalBlue}{t} - \ldots - \textcolor{Green}{v}+ u' -u ]\circ M_\bullet$ , from which it follows

\begin{equation}\label{eq.indstep}
L_\bullet\sim [I + s {-s' + \textcolor{RoyalBlue}{t} - \ldots -\textcolor{Green}{v} + u'} -u ]\circ M_\bullet
\end{equation}

Since the same arguments establishes (an analogue of) (<ref>) for $K_\bullet$, we

\begin{equation}
\begin{aligned}
L_\bullet &\overset{\eqref{eq.indstep}\text{ for $L_\bullet$}}{\sim}  [I + s \underbrace{-s' + t - \ldots -v + u'} -u ]\circ M_\bullet \\
[I + s \overbrace{+ t - v} - u ] \circ M_\bullet  \\
&\underset{downdown}{\overset{upup}{\expr}}  [I + t \underbrace{+ s - u} - v ]\circ M_\bullet \\
&\overset{\textcolor{black}{switchback}}{\expr} [I +t \overbrace{-t'+s - \ldots -u + v'} - v ]\circ M_\bullet \\
&\underset{\eqref{eq.indstep}\text{ for $K_\bullet$}}{\sim} K_\bullet,
\end{aligned}
\end{equation}

where, by Proposition <ref>, the middle three relations compose to an atomic braid relation. The proof is complete.

If $u_\bullet$ is a rotation sequence and

\[\pcoset\expr [I + s {-u_1 + u_0 - \ldots - u_d + u_{d-1}} -u ]\circ \rcoset\]
is a core coset, then
$[I + s {-u_1 + u_0 - \ldots - u_d + u_{d-1}} -u ]$ is an atomic expression.

By Proposition <ref>, it is enough to show that $[I+s-u_1]$ is atomic and that $[+u_{d-1}-u]$ is atomic.

Let us prove that $[I+s-u_1]$ is atomic. Suppose not. Then, by Proposition <ref>, a switchback relation applies to $[I+s-u_1]$ to give a reduced expression of $\pcoset$ starting with some $[I \supset I']$.
Since the redundancy decreases in the first step of the latter expression (see also remark <ref>), this contradicts  $\pcoset$ being a core coset (see e.g., <cit.>).

Similarly, if the subexpression $[+u_{d-1}-u]$ is not atomic, then remark <ref> applies here to result in a contradictory size of the redundancy for $p$.

Thoerem <ref> does not say that the atomic reduced expressions are in correspondence with the reduced expressions in some Coxeter group.
Although this is true in type $A$ and type $B$ (as is proved in <cit.>), new structures appear in other types. See Section <ref>.

Theorem <ref> does not say that any relation between two atomic reduced expressions in $\SC$ is a composition of atomic braid relations.
For a core coset $\pcoset$ and its atomic reduced expressions, it seems more reasonable to consider the rex graph whose edges are the atomic braid relations, rather than the full subgraph of the rex graph for $\pcoset$ in $\SC$.

All atomic reduced expression of a given core coset are of the same width.

This follows from Theorem <ref> since every atomic braid relation relates expressions of the same width.

The width of an atomic expression of a core coset $\pcoset$ is an even number $2l$, where $l$ is the number of atomic cosets that are composed in the expression.
Corollary <ref> says that the following is well-defined.

The atomic length of a core coset $\pcoset$ is half of the width of an atomic expression of $\pcoset$.

One may define the atomic length for all double cosets by setting the atomic length of $\pcoset\in\SC$ to be the atomic length of $\pcoset^{\core}$, but this definition lacks desirable properties.
For example, the atomic length of $(p\circ q)^{\core}$ need not agree with the sum of the atomic lengths of $\pcoset^{\core}$ and of $\qcoset^{\core}$.
Also, the atomic length is not compatible with the Bruhat order in the sense that there exist $(I,J)$-cosets $\pcoset\leq q$ where the atomic length of $\pcoset^{\core}$ is strictly bigger than that of $\qcoset^{\core}$, even for $\qcoset=q^{\core}$ atomic.

§ NON-BRAID RELATIONS

We continue letting $(W,S)$ be an arbitrary Coxeter system.
Let us introduce two classes of non-braid relations between atomic expressions.

Associated to an atomic expression in $\SC$ of the form
$[I+s-s]$, we define the atomic quadratic relation as the composition

\begin{equation}\label{quadratic}
[I+s\underbrace{-s+s}-s] \underset{*-quadratic}{\expr} [I+s-s] .
\end{equation}

Associated to an atomic expression in $\SC$ of the form $[I+s-t]$ with $s\neq t$, we define the atomic cubic relation as the composition (of two commuting relations)

\begin{equation}\label{cubic}
[I+s\underbrace{-t+t}\overbrace{-s+s}-t] \overset{*-quadratic}{\underset{*-quadratic}{\expr}} [I+s-t].
\end{equation}

The relation (<ref>) still holds when $s=t$ but is generated by (<ref>), so we exclude such cases to have less number of relations.

The left hand side of the atomic quadratic relation (<ref>) and the atomic cubic relation (<ref>) are indeed atomic expressions. The only nontrivial part is $[(Is\setminus t) +t-s]$ in (<ref>), but the latter is the inverse of the atomic expression $[I+s-t]$.

The atomic quadratic relation (or the absence of other quadratic relations) is motivated by the following statement from <cit.> (the first part is a special case of Lemma <ref>).

Let $\at\expr [I+s-t]$ be an atomic $(I,J)$-expression (where $J=Is\setminus t$) and $\atb\expr [J+u-v]$ be an atomic $(J,K)$-expression.

*  If $\pcoset=\at*\atb\expr [I+s-t]\circ[J+u-v]=[I+s-t+u-v] $ is reduced, then $\pcoset$ is a core coset.

*  If the composition $\pcoset=\at*\atb$ is not reduced, then $\pcoset$ is core if and only if $I=J=K$ and $s=t=u=v$, in which case $\pcoset\expr[I+s-s]$.

The first part is a special case of Lemma <ref>. The `if' claim follows from the $*$-quadratic relation $[Is-s+s]\expr[Is]$ which also gives  $p\expr[I+s-s]$ in this case.

Now suppose $p=\at*\atb\expr [I+s-t+u-v]$ is not reduced while $p$ is core. Then $q\expr [I+s-t+u]$ is not reduced, that is, $\mi{q}<\mi{\at}$ or $\leftred(q) \supsetneq \leftred(\at)$. The latter is not the case since $\at$ is core.
Since $\mi{\at} = \mi{q}.x$ for some $x\in W_{Ju}$ and since the only right descent of  $\mi{\at}$ is $t$, we have $t=x\in Ju$, thus $t=u$. It follows $s=v$ and $I=K$.
Finally, the $*$-quadratic relaton gives $p=[I+s-s]$ implying that $p$ is an atom and thus $p=\at$. The other equalities follows.

Let $p$ be a core $(I,J)$-coset and $q$ be a core $(J,K)$-coset. If $r=p*q$ is reduced then $r$ is a core coset.

By Proposition <ref>, both $p$ and $q$ has atomic expressions. Thus it is enough to assume that $q\expr [J+s-t]$ is an atomic coset.

\[r=p*q\expr p\circ [J+s-t] =p\circ [J+s] \circ[Js-t]\]

is reduced, the subexpression $p\circ [J+s]$ is reduced and thus we have
$I = \leftred(p)=\leftred(p\circ [J+s])$ and $\mi{pW_{Js}}=\mi{p}$.
Also $\leftred(p\circ [J+s-t]) = I\cap \mi{r}K\mi{r}\inv$

\[I=\leftred(p)=\leftred(p\circ [J+s])=\leftred(p\circ [J+s-t])=\leftred(r).\]

(see e.g. <cit.>)

Recall that by atomic expression we mean a composition of (the unique reduced expressions of) atomic cosets, which is not necessarily reduced or core. We introduce an auxiliary definition useful for this section.

An atomic expression $[I_0,\cdots, I_{2\ell}]$ is said to be admissible if each $[I_0\cdots, I_{2m}]$ for $m\leq \ell$ expresses a core coxet.

A reduced atomic expression $[I_0,\cdots, I_{2\ell}]$ is automatically admissible since redundancy for all $p_i\expr [I_0,\cdots,I_i]$ are the same (see <cit.>).

The following lemma generalizes Proposition <ref> (<ref>).

A reduced atomic expression of a core coset is admissible.

We prove the claim by induction on the atomic length $\ell$ of the core coset $p$.
Let $p=\at_1.\at_2.\cdots.\at_\ell$ be a reduced product for atomic cosets $\at_i$. By induction it is enough to show that $p=q.r$ for $q=\at_1.\at_2.\cdots .\at_m$ and $r$

\[\ell =\max\{\text{atomic length of }p, \text{atomic length of }q\}.\]

The base case $\ell=1$ is Proposition <ref> (<ref>).

If $\pcoset$ is a core $(I,J)$-coset and $\qcoset$ is a core $(J,K)$-coset such that $\pcoset *\qcoset$ is reduced, then $\pcoset *\qcoset$ is core.

We then have the following analogue of the Coxeter presentation.

A non-reduced admissible atomic expression is related to a reduced atomic expression by a composition of atomic braid relations, atomic quadratic relations, and atomic cubic relations. Moreover, atomic quadratic and cubic relations may be applied only from the left hand side to the right hand side of (<ref>) and (<ref>).

Our proof of Proposition <ref> uses the following analogue of the (weak) exchange property for Coxeter groups.

Let $\qcoset$ be a core $(I,J)$-coset and suppose $r = q\circ[J+s]$ is a (well-defined) non-reduced composition.

* We have $\mi{q}> \mi{r}$.

* The core coset $\qcoset$ has an atomic reduced expression ending in $[-s]$.

Since $\qcoset\subset r$ we have $\mi{q}\geq \mi{r}$.
Suppose $\mi{q}=\mi{r}$. Then

\[\rightred(r)\underset{def}{=}Js\cap \mi{r}\inv I \mi{r} \underset{\mi{q}=\mi{r}}{=} Js\cap \mi{q}\inv I \mi{q} = Js\cap J = \rightred(q),\]

where we use that $\qcoset$ is a core coset in the last two equalities. It follows that  $q\circ[J+s]$ is reduced, contrary to the assumption. This proves the first claim.

The condition $\mi{q}> \mi{r}$ implies $t\in\rightdes(\mi{q})$ for some $t\in Js$. But since $\rightdes(\mi{q})\cap J =\emptyset$, we have $t=s$.

\[s\in \rightdes(\mi{q})\subset \rightdes (w_I.\mi{q})=\rightdes(\ma{q})\]

since $\qcoset$ is core. Now Proposition <ref> guarantees an atomic reduced expression of $\qcoset$ ending with $[-s]$.

We proceed by induction on the atomic length, which agrees with the induction on the width. Our induction begins with two base cases, namely the reduced expressions $[I]$ and $[I+s-t]$, where the claim is trivial.

Let $m\geq 1$ and suppose the claim is true for any non-reduced admissible atomic expression of atomic length $\leq m$ and let

\[p \expr \at_0*\cdots *\at_m \expr I_\bullet = [I_0,\cdots , I_{2m+2}]= [I+s_0-t_0+s_1-t_1\ \cdots +s_m-t_m]\]
be a non-reduced admissible atomic expression of atomic length $m+1$, where each $\at_i$ is an atomic coset. We work with the `expression' $\at_0*\cdots *\at_m$ instead of the expression $I_\bullet$, identifying each $\at_i$ with its unique reduced expression $[I_{2i}+s_i-t_i]$.

The proper subexpression $\qcoset \expr \at_0*\cdots *\at_{m-1}$ is core since $I_\bullet$ is an admissible atomic expression.

Applying the induction hypothesis, we assume that $\qcoset\expr p_0*\cdots *\pcoset_{m-1}= [I_0,\cdots, I_{2m}]$ is reduced.
Since $I_\bullet$ is not reduced, we have that $r\expr q\circ [I_{2m}+s_m]$ is not reduced.

By Lemma <ref>, there is an atomic reduced exprssion $\qcoset\expr M_\bullet=[M_0,\cdots ,M_{2m}]$ so that
\begin{equation}\label{eq1}
I_\bullet \sim M_\bullet\circ [I_{2m}+s_m - t_m] = [M_0,\cdots , M_{2m-2}]\circ [I_{2m-2}+t -s_m]\circ [I_{2m}+ s_m - t_m]
\end{equation}

holds for some $t\in S$. Here `$\sim$' denotes a composition of atomic braid relations and follows by Theorem <ref>. The latter also justifies the width of $M_\bullet$ being $2m$.
Since $[I_{2m-2}+t -s_m]=[M_{2m-2},M_{2m-1},M_{2m}]$ is atomic, we have in fact $t = w_{I_{2m}s_m} s_m w_{I_{2m}s_m}$. Since $[I_{2m}+s_m-t_m]$ is also atomic, we have $t=t_m$. Now there are two cases.

The easy case is when $s_m=t_m$. In this case, the atomic quadratic relation (<ref>) applies to the last part of (<ref>), in the correct direction. The resulting atomic expression has the atomic length $m$. This establishes the induction step in the case $s_m=t_m$.

Let us consider the other case, that is, suppose $s_m\neq t_m$. Then

\[[M_{2m-2}+t_m-s_m+s_m-t_m]\expr[M_{2m-2}+t_m-t_m]\]

neither is atomic nor expresses a core coset. In particular, we cannot have $\pcoset\expr [M_{2m-2}+t_m-s_m+s_m-t_m]$, i.e., we have $m\geq 2$.
Now consider the non-atomic composition

\[[M_0,\cdots, M_{2m-2}]\circ [+t_m-t_m]\]
which is not reduced by Lemma <ref>.
Since $[M_0,\cdots, M_{2m-2}]$ is reduced, it is the step `$+t_m$' that is not reduced, namely, we are again in the situation in Lemma <ref>.
Lemma <ref> gives an atomic reduced expression $N_\bullet \expr [M_0,\cdots, M_{2m-2}]$  ending in `$-t_m$'. Note that $N_{2m-2}=M_{2m-2} = I_{2m-2}$.

We see that (<ref>) continues to

\begin{equation}\label{eq.long}
\begin{split}
I_\bullet&\sim [M_0,\cdots , M_{2m-4}, M_{2m-3}, M_{2m-2}] \circ [+t_m-s_m+s_m-t_m]\\
&\sim [N_0,\cdots , N_{2m-4}, N_{2m-3}, N_{2m-2}] \circ [+t_m-s_m+s_m-t_m] \\
&= [N_0,\cdots, N_{2m-4}]\circ [+u-t_m+t_m-s_m+s_m-t_m]
\end{split}
\end{equation}

for some $u\in S$. The second equivalence in (<ref>) follows from Theorem <ref> since  $[M_0,\cdots, M_{2m-2}]\expr N_\bullet$ involve reduced atomic expressions.
Since $N_\bullet$, and thus $[N_{2m-4}+u-t_m]$, is an atomic expression we necessarily have $u = s_m$.
Applying the cubic relation (<ref>) to the last part of (<ref>), in the correct direction, completes the induction step.

All admissible atomic expressions of a (core) coset are related by atomic braid relations, atomic quadratic relations, and atomic cubic relations.

This follows from Proposition <ref>, Remark <ref>, and Theorem <ref>.

We may have a stronger analogue of the Coxeter presentation than Corollary <ref> by including non-admissible atomic expressions. The proof could be by induction similar to that of Proposition <ref>, but we need to consider the possibility that $\qcoset$ is not a core coset. The latter leads us to remark <ref>.

We may have a different analogue of the Coxeter presentation than Corollary <ref> by including atomic expressions of non-core cosets, namely, all cosets generated by the atomic cosets.
There a class of generating non-braid relation would be

\begin{equation}
[I+s-t+t-s]\expr [I+s-s]
\end{equation}

arising from the composition $\at*\at\inv$ for each atomic coset $\at\expr[I+s-t]$.
But we may need more relations for a presentation whose proof may also be not similar to ours.

A consequence of Corollary <ref> is a new presentation of Demazure operators, which is a `zoomed-out' version of the `zoomed-in' presentation in <cit.>.
To make this precise, we introduce a subcategory.

The atomic Demazure algebroid $\Dem^{\core}$ is the subcategory of the nilCoxeter algebroid $\Dem$ spanned by the morphisms $\partial_\pcoset$ associated to core cosets $\pcoset$.

Definition <ref> does define a category, that is, $\Dem^{\core}$ is closed under composition.

By Proposition <ref> and Proposition <ref>, a reduced composition of core cosets is belongs to $\Dem^{\core}$.
But any non-reduced composition in $\Dem$, being zero, also belongs to $\Dem^{\core}$.

The category $\Dem^{\core}$ admits the following presentation by generators and relations. Its generating set is

\[\{\partial_\at\ |\ \at\text{ is an atomic double coset}\}\]

and its (generating) relations are

* the atomic braid relations;

* the atomic nil-quadratic relations  $\partial_\at\circ \partial_{\at\inv}=0$ for each generator $\partial_\at$.

By Proposition <ref>, any core coset has an atomic reduced expression, proving that $\Dem^{\core}$ has the claimed generator.
Since an atomic braid relation is a composition of singular braid relations, the atomic braid relations hold in $\Dem$. For the atomic nil-quadratic relation, first note that a double coset $\at$ is atomic if and only if $\at\inv$ is atomic, so it is a relation between atomic compositions.
That the atomic nil-quadratic relation hold follows from the composition

\[\at * \at\inv \expr [I\setminus s+s-t]\circ [I\setminus t+t-s]=[I\setminus s+s]\circ [I-t+t] \circ [I -s]\]

being not reduced.

Now we show that the above relations are generating.
Theorem <ref> covers the reduced expressions, i.e., the nonzero compositions in $\Dem^{\core}$.
It remains to show that if $\partial_{[\at_\bullet]}=\partial_{\at_1}\circ \partial_{\at_2}\circ \cdots \circ \partial_{\at_m}$ is zero, for $\at_i$ atomic, then the expression $\at_\bullet=[\at_0,\cdots,\at_m]$ is related by atomic braid relations to an expression $[\atb_0,\cdots,\atb_m]$ with  $\atb_k=\atb_{k+1}\inv$ at some index $k$.
Since both the atomic quadratic relation and the atomic cubic relation contains a product of the form $\at*\at\inv$,  Corollary <ref> gives the claim for when $\at_\bullet$ is an admissible atomic expression.

Now suppose $\at_\bullet$ is not an admissible atomic expression. In this case, there exists a proper admissible subexpression $\qcoset= \at_0*\at_1*\cdots * \at_k$ of atomic length $\geq 1$ such that $r = \at_0*\cdots * \at_k*\at_{k+1}$ is not a core coset.
If $\qcoset= \at_0*\at_1*\cdots * \at_k$ is not reduced then, as in the above paragraph,  Corollary <ref> gives the claim.

If $\qcoset= \at_0*\at_1*\cdots * \at_k$ is reduced, then $\qcoset$ has an atomic reduced expression ending at $[L+u-s]$, where $s\in S$ is such that $\at_{k+1} \expr [K+s-t]$, by Lemma <ref>.
By Thoerem <ref>, we may assume that $\at_k=[L+u-s]$.
But $t=w_{Ks}sw_{Ks} = u$ implies $\at_k=\at_{k+1}\inv$.

Now suppose $\at_\bullet$ is not an admissible atomic expression. In this case, since any atom $\at_i$ is admissible, there exists a proper consecutive subexpression $\qcoset= \at_i*\cdots * \at_k$ of atomic length $\geq 1$ which is admissible, so that $r = \at_i*\cdots * \at_k*\at_{k+1}$ (or $r=\at_{i-1}*\at_{i}*\cdots * \at_k$ where the proof goes the same way) is not core.
Writing $\at_{k+1} \expr [K+s-t]$, by Lemma <ref> $\qcoset$ has an atomic reduced expression ending at $[L+u-s]$, and
by Corollary <ref>, we may assume that $\at_k=[L+u-s]$.
But $t=w_{Ks}sw_{Ks} = u$ implies $\at_k=\at_{k+1}\inv$ as claimed.

Core combinatorics

§ CORANK 2 CASE

Let $(W,S)$ be a finite Coxeter system.
Note that if $|S\setminus I| = |S\setminus J| \in\{0,1\}$ then a core $(I,J)$-coset is either the identity coset or the unique atomic $(I,J)$-coset and thus has a unique reduced expression which is atomic.
In this section we consider the next easiest case, namely, the core $(I,J)$-cosets where $|S\setminus I| = |S\setminus J| = 2$.
Our goal is to explain how the discussion from Section <ref>  completely describes the atomic reduced expressions.

We denote the dihedral group of order $2m$ by $W(I_2(m))$ viewed as the Coxeter group with the generators $\{a,b\}$ and the relation $\underbrace{ab\cdots}_m =\underbrace{ba\cdots}_m$.
Then $W(I_2(m))$ has exactly $2m+1$ reduced expressions, whose list is

\begin{equation}\label{eq.rexsdihed}
e,\ a,\ b,\ ba,\ ab,\ \cdots\ ,\ \ka{m},\ \kb{m}.
\end{equation}

where we use the notation

\[ \ka{k} = \underbrace{\cdots ba}_k ,\quad \kb{k}= \underbrace{\cdots ab}_k.\]

The following lemma is implicit in the construction of the switchback relation.

Let $J\subset S$ be such that $S\setminus J = \{s_1,s_2\}$ for $s_1\neq s_2$ and let $k>0$.
For $i=1,2$, there exists exactly one atomic expression, denoted by $E(i,k)$, ending in $[Js_i,J]$ of atomic length $k$.
The expression $E(1,k)$ is reduced if and only if $k\leq d+1$, where  $d+1$ is the atomic length of the atomic braid relation associated to $(S,\textcolor{RoyalBlue}{\con{s_1}},\textcolor{Green}{s_2})$,
i.e., $d=d(S,\textcolor{RoyalBlue}{\con{s_1}},\textcolor{Green}{s_2})$
(see Definition <ref>
and recall $\textcolor{RoyalBlue}{\con{s_1}} = w_S \textcolor{Orange}{s_1} w_S$).
Moreover, $E(1,d+1)\expr E(2,d+1)$ is an atomic braid relation.

Note that there exists exactly two atomic $(I,J)$-cosets, for exactly two $I\subset S$, namely, $[Js_i\setminus w_{Js_i}s_iw_{Js_i},Js_i,J]$.
Similarly, if $L\subset S$ is any subset with $|L|=|J|$, then there exists exactly two atomic $(I,L)$-cosets where $I$ runs.
Thus, at each step of composing atomic cosets, from the right to left, we have exactly two choices of composable atomic cosets.
Except of at the first step, one of the two choices yields a non-reduced subexpression of the form $[+s-t+t-s]$.

It follows that there is a unique atomic expression, call it $E(i,k)$, of atomic length $k>0$ ending at $[Js_i,J]$, which does not contain a subexpression of the form $[+s-t+t-s]$.
By Proposition <ref>, this is of the form (<ref>) for the rotation sequence $u_\bullet$ associated to $(S,\con{u_{k}},u_{k-1})$(these are the same rotation sequence up to shift, which arises since we start from the right here).
If $k=d+1$ then we obtain the atomic expression in the left hand side of (<ref>).

The claim thus follows from Definition <ref> and Proposition <ref>.

Let $(W,S)$ be a finite Coxeter system and let  $J\subset S$ with $|S\setminus J|=2$.
Then we have a bijection

\[\phi:W(I_2(d+1)) \to \{\text{core $(I,J)$-cosets where $I\subset S$ varies}\}=: \coreJ{J}\]

where $d+1$ is the atomic length of the atomic braid relation associated to  $(S,S\setminus J)$ (see Definition <ref> and remark <ref>).
Moreover, the bijection is compatible with the braid relations in the sense that the only braid relation

\[\ka{m} \expr \kb{m}\]

in $W(I_2(d+1))$
corresponds to the only atomic braid relation in $\coreJ{J}$, which is on the element $\phi(\ka{m})=\phi(\kb{m})$.

We construct two such bijections $\phi_1, \phi_2$ in the proof. Let $S\setminus J = \{s_1,s_2\}$.  Then Lemma <ref> and the related discussion in Section <ref> applies.

\begin{equation}
\Phi_i: \{\text{all reduced expressions in $I_2(d+1)$}\} \to \{\text{atomic reduced expressions for $(W,S)$}\}
\end{equation}

by letting $\Phi_1(\ka{k})=E(1,k)$, $\Phi_1(\kb{k})=E(2,k)$, from Lemma <ref> and the other way for $\Phi_2$.

Each $\Phi_i$ is injective by construction.

The only braid relation in the domain of $\Phi_i$ is $\ka{d+1}\expr \kb{d+1}$. Lemma <ref> says that $\Phi_i$ maps this to the atomic braid relation $\Phi_i(\ka{d+1})\expr \Phi_i(\kb{d+1})$. By Proposition <ref>, the latter is the only atomic braid relation in the image of $\Phi_i$.

Now the classical Matsumoto theorem and the atomic Matsumoto theorem (Theorem <ref>) together show that $\Phi_i$ induces a well-defined injection $\phi_i$ satisfying the second claim of the proposition. That $\phi_i$ is surjective follows from Proposition <ref>.
This completes the proof.

The following examples are deduced from <cit.> and Proposition <ref>.

Let $(W,S)$ be of type $D$. Let $s_1\in S$ be the unique element having three edges in the associated Dynkin diagram.
If $s_1\in J\subset S$ with $|S\setminus J|=2$, then   $\coreJ{J}$ and its atomic reduced expressions correspond to that of the dihedral group of type $A_2$.
If $s_1\not\in J\subset S$ with $|S\setminus J|=2$, then $\coreJ{J}$ and its atomic reduced expressions correspond to that of the dihedral group of type $B_2$.

This is a convenient point to introduce the following abuse of notation.

Let $(W,S)$ be of type $H_4$ with the indexing
(4 cm,0.05cm) – (2 cm,0.05 cm);
(4 cm,-0.05cm) – (2 cm,-0.05 cm);
(4 cm,0cm) – (2 cm,0 cm) ;
(2 cm,0) – (0 cm,0);
(0 cm,0) – (-2 cm,0);
[fill=white] (3 cm, 0 cm) circle (0cm) node[below=0pt]$5$;
[fill=white] (4 cm, 0 cm) circle (.15cm) node[above=1pt]$4$;
[fill=white] (2 cm, 0 cm) circle (.15cm) node[above=1pt]$3$;
[fill=white] (0 cm, 0 cm) circle (.15cm) node[above=1pt]$2$;
[fill=white] (-2 cm, 0 cm) circle (.15cm) node[above=1pt]$1$;
Then $\coreJ{\{s_3,s_4\}}$ and its atomic reduced expressions correspond to that of the dihedral group of type $I_2(10)$.
If $J \subset S$ is any subset of order two other than $\{s_3,s_4\}$, then $\coreJ{J}$ and its atomic reduced expressions correspond to that of the dihedral group of type $I_2(12)$.

If $J\subset S$ is such that $S\setminus J=\{s,t\}$ with $w_{Js}sw_{Js} = s$ and $w_{Jt}tw_{Jt} = t$ then $\SC^{\core}_J$ consists only of $(J,J)$-cosets.
Thus $\SC^{\core}_J$
is a monoid and $\phi_i$ are upgraded to isomorphisms from $(W(I_2(d+1)),*)$ (viewed as a category with one object) to $\SC^{\core}_J$ so that $\phi_1\inv\circ \phi_2$ is the automorphism on $(W(I_2(d+1)),*)$ swapping the two Coxeter generators. Similarly, we have an algebra isomorphism between the nilCoxeter algebra of type $I_2(d+1)$ and $\Dem^{\core}_J$ in this case.

In general, one can define an equivalence relation on the subsets of $S$ generated by $K\sim L$ if there exists an atomic $(K,L)$-coset and consider the subcategory

\begin{equation}\label{eq.DemJeqclass}
\Dem^{\core}_{(J)}:=\bigcup_{K\in(J)}\Dem^{\core}_J
\end{equation}

in $\Dem^{\core}$ associated to the equivalence class $(J)$ of $J$.
Then $\Dem^{\core}_{(J)}$ is a multiple object version of the nilCoxeter algebra $D(I_2(d+1))$.
Viewing a bijection $\phi^K$ from Proposition <ref>, for each $K\in(J)$, as a bijection from $D(I_2(d+1))$ to $\Dem^{\core}_K$, we have a decomposition

\[\Dem^{\core}_{(J)} = \bigsqcup_{K\in (J)} \phi^K(D(I_2(d+1))).\]

In our discussion in this section, the ambient Coxeter system $(W,S)$ is assumed to be finite in order for Section <ref> to apply. The next remark  provides some complement to this.

Let $(W,S)$ be infinite and $J\subset S$ finitary with $S\setminus J = \{s_1,s_2\}$ for $s_1\neq s_2$.
If $Js_i\subset S$ is not finitary then there is no $(I,J)$-expression ending in $[-s_i]$, for any $I\subset S$.
If $Js_1\subset S$ is finitary, then a reduced $(I,J)$-expression ending in $[-s_1]$ is still of the form $E(1,k)$, which exists for $k< m$ where an infinitary subset $K\subset S$ is first involved at the $m$-th step. In particular, if $S$ is of affine type then we have well-defined and distinct $E(1,k)$ and $E(2,k)$ for all $k$ which identifies $\SC^{\core}_J$ with the Coxeter monoid of type $I_2(\infty)$.

§ GENERAL CASE

§.§ The poset of left/right-fixed core cosets

Let $(W,S)$ be a Coxeter system.
The rest of the paper is devoted to general and special discussions on

\begin{equation}\label{eq.defcoreJ}
\coreJ{J}:=\{\text{core $(I,J)$-cosets where $I\subset S$ varies}\} \end{equation}

for $J\subset S$ finitary.

Since non-reduced expressions do not appear in the rest of the paper, the discussions below are valid, up to linearization, for

\[\Dem^{\core}_J=\bigcup_{I\in\Dem^{\core}}\Hom_{\Dem^{\core}}(I,J)\]

which is more naturally defined from the category $\Dem^{\core}$ (recall that the core cosets in $\SC$ do not form a subcategory).

We consider the left-fixed versions

\begin{equation*}
\!_{I}\SC^{\core}:=\{\text{core $(I,J)$-cosets where $J\subset S$ varies}\},\quad \!_{I}\Dem^{\core}=\bigcup_{J\in\Dem^{\core}}\Hom_{\Dem^{\core}}(I,J)
\end{equation*}

as well.

In the special cases covered in Section <ref> or in <cit.>, the atomic reduced expressions and the atomic braid relations in $\coreJ{J}$
agrees with the ordinary reduced expressions and the ordinary braid relations in some Coxeter system. This is not the case in general. The easiest such example is the following.

The order of $\coreJ{\{s\}}$ in type $D_4$, for any $s\in S$, is $32$. Moreover, each such $\coreJ{\{s\}}$ has is a unique maximal element of atomic length $7$.
(While these numbers are the same, the structure of $\coreJ{\{s\}}$, e.g., the atomic reduced expression graphs, does depend on $s\in S$.
We discuss one of the two, up to symmetry, cases in detail in Section <ref>.)

Here is some more result of computations on SageMath.

We consider the four corank 3 cases in type $H_4$. We index $S=\{s_1,s_2,s_3,s_4\}$ as in [scale=0.4,baseline=-3]
(4 cm,0.05cm) – (2 cm,0.05 cm);
(4 cm,-0.05cm) – (2 cm,-0.05 cm);
(4 cm,0cm) – (2 cm,0 cm) ;
(2 cm,0) – (0 cm,0);
(0 cm,0) – (-2 cm,0);
[fill=white] (3 cm, 0 cm) circle (0cm) node[below=0pt]$5$;
[fill=white] (4 cm, 0 cm) circle (.15cm) node[above=1pt]$4$;
[fill=white] (2 cm, 0 cm) circle (.15cm) node[above=1pt]$3$;
[fill=white] (0 cm, 0 cm) circle (.15cm) node[above=1pt]$2$;
[fill=white] (-2 cm, 0 cm) circle (.15cm) node[above=1pt]$1$;
In all cases, the set $\coreJ{\{s_i\}}$ is of order 480 and contains a unique maximal element of atomic length 31.
When $i=1$ the number of elements of atomic length $j$ is the $j$-th number in the sequence

\[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 24, 24, 24, 24, 24, 24, 24, 24, 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1\]

and the longest element has 25392 atomic reduced expressions;
when $i=2$ we have the numbers

\[1, 3, 5, 7, 9, 12, 14, 15, 17, 19, 22, 23, 22, 22, 23, 26, 26, 23, 22, 22, 23, 22, 19, 17, 15, 14, 12, 9, 7, 5, 3, 1\]

and the longest element has 35032 atomic reduced expressions;
when $i=3$ we have

\[1, 3, 5, 7, 9, 12, 15, 16, 17, 19, 21, 22, 22, 23, 24, 24, 24, 24, 23, 22, 22, 21, 19, 17, 16, 15, 12, 9, 7, 5, 3, 1\]

and the longest element has 36874 atomic reduced expressions;
when $i=4$ we have

\[1, 3, 5, 7, 9, 12, 15, 17, 18, 18, 19, 21, 23, 24, 24, 24, 24, 24, 24, 23, 21, 19, 18, 18, 17, 15, 12, 9, 7, 5, 3, 1\]

and the longest element 36746 atomic reduced expressions.
That all atomic length sequences are symmetric is because the involution $s\mapsto\con{s}$ is the identity in type $H$, which we explain in Proposition <ref>.

The objects $\coreJ{J}$ do share a number of general properties of the Coxeter monoids. We investigate some of such in this section.
Recall that, for $S$ finitary, we set $\con J = w_SJw_S$ where $w_S$ is the longest element in $(W_S,S)$.

Let $S$ be finitary.
Then for $I,J\subset S$, the $(I,J)$-coset $W_Iw_SW_J$ is core if and only if $I=\con J$.

The claim is trivial when $|I|\neq |J|$, so we assume $|I|=|J|$.

Let $\pcoset= W_{I} w_S W_J$ and consider the element $w_Sw_J\inv\in \pcoset$.
We write $w_Sw_J\inv = x.\mi{p}$ for some $x\in W_I$.

\begin{equation}\label{pJp}
\mi{p} J \mi{p}\inv = x\inv w_S w_J J w_J w_S x = x\inv w_S J w_S x = x\inv \con{J} x
\end{equation}

Now we have

\[\leftred(p) \underset{\text{def.}}{=} I\cap \mi{p}J\mi{p}\inv \underset{}{=} W_I\cap\mi{p}J\mi{p}\inv \underset{\eqref{pJp}}{=} W_I\cap x\inv \con{J} x \underset{\text{conjugate}}{\cong} x W_I x\inv \cap \con{J} \underset{x\in W_I}{=} W_I\cap \con{J} = I\cap \con{J}\]

where the second equality is due to Kilmoyer's theorem <cit.>.
Since $\pcoset$ is core if and only if $\leftred(p) = |J|$, this proves the claim.

An immediate consequence of Lemma <ref> is:

Let $S$ be finitary and $J\subset S$. The core coset $\pcoset_J=W_{\con J} w_S W_J$ is the unique maximal element in $\coreJ{J}$.

In a Coxeter group, multiplication by the longest element $w_0$ induces an anti-involution on the strong and weak Bruhat poset.
Thus we have the same anti-involution on a Coxeter monoid, even though the $*$-multiplication by an element cannot induce an anti-involution.

To define such anti-involutions directly in terms of the $*$-multiplication, we do as follows:
Given $w\in W$, there is a unique element $x\in W$ satisfying $w.x=w_0$. Letting $w\mapsto x$, we obtain an anti-involution on the left Bruhat order.
Proposition <ref> is its atomic analogue.

We first fix notation for the left and right Bruaht orders on $\SC$. The (weak) left Bruaht order is defined and denoted as

\[p\leq_l q \text{ if $\qcoset = r.\pcoset$ for some $r\in \SC$ ;}\]

the (weak) right Bruaht order is defined and denoted as

\[p\leq_r q \text{ if $\qcoset = p.r$ for some $r\in \SC$} .\]

Let $S$ be finitary and $J\subset S$.
If $\con{J} = J$ then there exists an anti-involution of the poset $(\coreJ{J},\leq_l)$.
More generally, there is an anti-isomorphism of the posets $(\coreJ{J},\leq_l)\to (_{\con J}\SC^{\core},\leq_r)$.

Given a core $(I,J)$-coset $\pcoset$,
by (the right-to-left analogue of) <cit.> and its proof, there is a unique $(\con J, I)$-coset $\qcoset$ such that $\qcoset*\pcoset = W_{\con J} w_S W_J$.
The assignment $\pcoset\mapsto\qcoset$ defines a map

\[f:(\coreJ{J},\leq_l)\to ( _{\con J}\SC^{\core},\leq_r)\]

whose inverse is given by a similar map. Thus $f$ is an anti-isomorphism claimed in the more general statement.

Now, if $J=\con J$ then reversing expressions induces a poset isomorphism  $g:( _{ J}\SC^{\core},\leq_r)\to (\coreJ{J},\leq_l)$.
The anti-involution $g\circ f$ proves the first claim.

One may also consider the strong Bruhat order on $\coreJ{J}$ as restricted from $\SC$ (see <cit.>), but for the purpose of studying $\coreJ{J}$ the weak Bruhat order seems more natural.

§.§ A corank 3 example

Let $(W,S)$ be of type $D_4$ and let $c\in S:=\{c,t,u,v\}$ be the simple generator corresponding to the center of the Dynkin diagram of type $D_4$. In this subsection we describe the atomic reduced expressions for $P:=\coreJ{\{c\}}$.

The atomic cosets in $P$ are

\[\at^c_t :\expr [t, ct,c],\quad \at^c_u :\expr [u,cu,c],\quad \at^c_v :\expr [v,cv,c].\]

Here $t$ is a shorthand for $\{t\}$, $ct$ denotes $\{c,t\}$, and so on.
Note that the $S_3$-symmetry permuting $t,u,v$ induces an $S_3$-symmetry on $P$.
The other atomic cosets that appears in atomic reduced expressions in $P$ are

\[\at^t_c:\expr [c,ct,t],\quad \at^t_u:\expr [t,tu,t]\]

up to the $S_3$-symmetry. We drop the superscripts when it is clear from the context: for example,
there is a unique $s\in S$ which makes $\at^s_v*\at^c_t$ well-defined, namely $s=t$, so we write $\at_v*\at^c_t$ instead.
Since each element in $P$ can be composed on the left by three atoms, and one of those three produces a subexpression of the form $[-s]\circ [+s]$, the number of reduced expressions in $P$ of (atomic) length $m$ is bounded by $3\cdot 2^{m-1}$.

A direct computation (or <cit.>) determines the full list of atomic braid relations in $P$.
The atomic braid relations for $(I,\{c\})$-cosets are

\begin{equation}\label{withc}
\at_c\at_t\at^c_u = \at_c\at_u\at^c_t,\quad \at_c\at_t\at^c_v = \at_c\at_v\at^c_t,\quad \at_c\at_v\at^c_u = \at_c\at_u\at^c_v,
\end{equation}

but we also need the atomic braid relations

\begin{equation}\label{noc}
\at_t\at_u^v%\at^c_v
= \at_u\at_t^v%\at^c_v
, \quad \at_t\at_v^u
= \at_v\at_t^u%\at^c_u
, \quad \at_v\at_u^t%\at^c_t
= \at_u\at_v^t,%\at^c_t,
\end{equation}

since they give relations in $P$, for example,

\begin{equation}\label{noc3}
\at_t\at_u^v\at^c_v
= \at_u\at_t^v\at^c_v
, \quad \at_t\at_v^u
\at^c_u
= \at_v\at_t^u\at^c_u
, \quad \at_v\at_u^t\at^c_t
= \at_u\at_v^t\at^c_t
\end{equation}

Then it is easy to see (or use Corollary <ref>) that there are 6 elements in $P$ of (atomic) length two, each of which has a unique reduced expression.
From (<ref>) and (<ref>), it follows that the 12 potentially-reduced length three expressions are indeed reduced and give 6 elements in $P$ of length three. Each of these has two reduced expressions

There is only one way to extend a length three expression in $P$ to a length four expression in $P$, because a length three expression is related by braid relation to another that has a different atom on the left.
So we have 6 elements of length four in $P$ each of which has two reduced expressions.

Now we may stop computing and apply Proposition <ref>, since the maximal element

\[W_{c}w_S W_c= \{w_S, cw_S=w_Sc\}\in P\]
has atomic length seven. This determines in particular the number of elements in $P$ of length four, five, six, seven, namely, 6, 6, 3, 1, respectively, as well as their weak Bruhat relations.
This also determines the number of reduced expressions for each element, namely all elements of length four (resp., five, six, seven) has 2 (resp., 4, 8, 24) reduced expressions.

A few additional direct computations determine the Hasse diagram for the weak Bruhat poset $P$, which we include below. The diagram is aligned according to the atomic lengths. The number on each vertex is the number of atomic reduced expressions for the represented element.

\[
\begin{tikzpicture}[scale=0.8]
%\node (l0) at (-8,2) {$\ell=0$};
%\node (l1) at (-8,1) {$\ell=1$};
%\node (l2) at (-8,0) {$\ell=2$};
%\node (l3) at (-8,-1) {$\ell=3$};
%\node (l4) at (-8,-2) {$\ell=4$};
%\node (l5) at (-8,-3) {$\ell=5$};
%\node (l6) at (-8,-4) {$\ell=6$};
%\node (l7) at (-8,-5) {$\ell=7$};
\node (1) at (0,2) {$1$};
\node (11) at (-2,1) {$1$};
\node (12) at (0,1) {$1$};
\node (13) at (2,1) {$1$};
\node (21) at (-5,0) {$1$};
\node (22) at (-3,0) {$1$};
\node (23) at (-1,0) {1};
\node (24) at (1,0) {$1$};
\node (25) at (3,0) {$1$};
\node (26) at (5,0) {1};
\node (31) at (-5,-1) {$2$};
\node (32) at (-3,-1) {$2$};
\node (33) at (-1,-1) {2};
\node (34) at (1,-1) {$2$};
\node (35) at (3,-1) {$2$};
\node (36) at (5,-1) {2};
\node (41) at (-5,-2) {$2$};
\node (42) at (-3,-2) {$2$};
\node (43) at (-1,-2) {2};
\node (44) at (1,-2) {$2$};
\node (45) at (3,-2) {$2$};
\node (46) at (5,-2) {2};
\node (51) at (-5,-3) {$4$};
\node (52) at (-3,-3) {$4$};
\node (53) at (-1,-3) {$4$};
\node (54) at (1,-3) {$4$};
\node (55) at (3,-3) {$4$};
\node (56) at (5,-3) {$4$};
\node (61) at (-2,-4) {$8$};
\node (62) at (0,-4) {$8$};
\node (63) at (2,-4) {$8$};
\node (7) at (0,-5) {$24$};
\draw (1) -- %node{$\at_t^c$} ++
(11) -- (21) -- (31) -- (41) -- (51) --(61) -- (7)
(11) -- (22) -- (32) -- (42) -- (51)% -- (61)
(1) -- (12) -- (23) -- (31)
(43) -- (53) -- (62) -- (7)
(12) -- (24) -- (34) -- (44) -- (52) -- (61)
(1) -- (13) -- (25) -- (33) -- (43) -- (53) -- (62)
(13) -- (26)
(21) -- (32)
(22) -- (33)
(23) -- (34)
(24) -- (35)
(25) -- (36)
(26) -- (35)
(26) -- (36)
(35) -- (45) -- (55) -- (63) -- (7)
(36) -- (46)
(41) -- (52)
(42) -- (53)
(43) -- (54)
(44) -- (55)
(45) -- (56)
(46) -- (54)
(46) -- (56)
(54) -- (62)
(56) -- (63);
%  (13) -- (26) -- (36)
%  (46) -- (56) -- (63);
%  (24) -- (min) -- (25) -- (c) -- (max)
%  (21) -- (b);
%  \draw%[preaction={draw=white, -,line width=6pt}]
%  (a) -- (23) -- (c);
\end{tikzpicture}
\]

Proposition <ref> below says that <cit.> illustrates our $P$.

If $S$ is of type $D_{n+2}$ and $S\setminus J =\{s_0,s_{\bar{0}}, s_n\}$ corresponds to the three extreme vertices in the Dynkin diagram, then the reduced expression graphs and the left Bruhat order on $\coreJ{J}$ are the same as our example in type $D_4$. The same explanation applies.

When $S$ is of type $D$ and $J\subset S$ is such than $|S\setminus J|=4$, the object $\coreJ{J}$ can have:

The above list covers all such $\coreJ{J}$ up to type $D_{11}$.

§ TITS CONE INTERSECTIONS

Let us consider the Tits cone $\cone(W,S)$ associated to $(W,S)$ (see e.g. <cit.>, <cit.>, or <cit.>). To briefly recall, the Tits cone is defined as the subset

\[\cone(W,S)=\bigcup_{w\in W}w(\overline{C})\subset V^*\]
where  $V$ is the geometric (standard) realization of $(W,S)$ over $\mathbb R$ with the basis $\{\alpha_s\}_{s\in S}$ and  $\overline{C}$ is the closure of the standard chamber

\[C=\{\theta\in V^*\ |\ \theta(\alpha_s)>0 \text{ for all }s\in S\}.\]

Given a subset $I\subset S$, the Tits $I$-cone is the intersection

\[\mathsf{Cone}(W,S,I) := \mathsf{Cone}(W,S)\cap \{ \theta \in V^* \ |\ \theta(\alpha_s)=0\text{ for }s\in I\}.\]

The intersection $\cone(W,S,I)$ gives rise to a new kind of chamber geometry, as developed in <cit.>.
Let us fix $I\subset S$ for the rest of the section.
For $w\in W$ and $J\subset S$, let

\[C_J:=\{\theta\in V^*\ |\ \theta(\alpha_s)>0\text{ for $s\in S\setminus J$ and $\theta(\alpha_s)=0$ for $s\in J$}\}\]

be the standard $J$-chamber in $\cone(W,S,J)$.
One sees from the definition that the image $w(C_J)$ is either contained in $\cone(W,S,I)$ or
disjoint from $\cone(W,S,I)$.
A subset in $\cone(W,S,I)$ of the form $w(C_J)$, with some $w\in W$ and $J\subset S$ with $|J|=|I|$, is called an $I$-chamber.

Let us denote by $\cham(W,S,I)$ the set of $I$-chambers in $\cone(W,S,I)$.
Then <cit.> provides the following relation between the Tits cone intersection and the core double cosets.
First note that, for a core $(I,J)$-coset $p$, we have $p=W_IxW_J=xW_J$ as sets, where $x\in p$. We thus let $p(C_J):=\mi{p}(C_J)=x(C_J)$.

For each finitary subset $I\subset S$, we have a bijection

\begin{equation}
\ _{I}\SC^{\core}(W,S) \rightarrow \mathsf{Cham}(W,S,I)
\end{equation}

sending a core $(I,J)$-coset $p$ to the chamber $p(C_J)$.

For the claimed bijection to be well-defined, we need that $p(C_J)$ is a chamber in $\cone(W,S,I)$. But if $\theta\in C_J$ and  $s\in I$, then

\[(p(\theta))(\alpha_s)=(\mi{p}(\theta))(\alpha_s)=\theta(\alpha_{\mi{p}\inv s\mi{p}}) =0 \]

\[\mi{p}\inv s\mi{p}\in \mi{p}\inv I\mi{p} =\mi{p}\inv \leftred(p)\mi{p} =\rightred(p)= J,\]
which shows that $p(C_J)\subset \cone(W,S,I)$.

Now let $w(C_J)\in \cham(W,S,I)$, i.e., $w(C_J)\subset \cone(W,S,I)$ for some $w\in W$ and $J\subset S$ with $|J|=|I|$.

We need to show that $W_Iw=wW_J$, from which it follows that $p:=W_IwW_J=W_Iw=wW_J$ is core
and that our map is bijective.
But if $x\in W_I$ then the assumtion
$w(C_J)\subset \cone(W,S,I)$ implies $xw(C_J) = w(C_J)$ and thus $xw\in wW_J$. This shows $W_Iw\subset wW_J$, which suffices because of the assumption $|I|=|J|$.

Proposition <ref> is merely an interpretation of <cit.> in our setting. Those readers familiar with <cit.> may prefer:

<cit.> states that
$\cham(W,S,I)$ is in bijection with the set $\mathsf{cCham}(W,S,I)$ of combinatorial chambers [Note that $\mathsf{cCham}(W,S,I)$ is what <cit.> denotes by $\cham(W,S,I)$. See <cit.>.], which consists of the pairs $(x, J)$, for $x\in W$ and $J\subset S$, satisfying

*  $\ell(x) = \min\{\ell(y)\ |\ y\in xW_J\}$;

*  $W_Ix = xW_J$

via $(x,J)\mapsto x(C_{J})$.
It is therefore enough to show that the map $\!_{I}\SC^{\core}(W,S) \rightarrow \mathsf{cCham}(W,S,I)$
given by $p\mapsto (\mi{p},J)$ is a bijection.
In fact,
is equivalent to $W_IxW_J$ being a core $(I,J)$-coset, so  $(x,J)\mapsto W_IxW_J%{x\inv I x}
$ defines a left inverse.
Condition (<ref>)
makes it a right inverse.

Proposition <ref> readily establish a similar connection to the Demazure algebroid as well.

We have

\[\bigsqcup_{I\subset S \text{ finitary}}\cham(W,S,I)\xhookrightarrow[\text{basis}]{} \Dem^{\core}(W,S)\]

which restricts to

\[\bigsqcup_{K\in (I)}\cham(W,S,K)\xhookrightarrow[\text{basis}]{} \!_{(I)}\Dem^{\core}(W,S)\]

for each $I\subset S$ (see (<ref>)).

Since the categories $\SC$ and $\Dem$ have the same morphisms, up to linearization, and the same reduced expression with respect to the Coxeter presentations (see Section <ref>), we have

\begin{equation}\label{eq.SC=SD}
\ _{I}\SC^{\core}(W,S) \xhookrightarrow[\text{basis}]{} \ _{I}\Dem^{\core}(W,S).
\end{equation}

for each $I\subset S$ finitary.
The claim follows by Proposition <ref>.

Proposition <ref> interprets Theorem <ref> as a generators and relations presentation of all (resp., equivalent) $I$-chambers.

While the current paper only considers finitary subsets $I\subset S$, there is no finiteness assumption in defining $\cone(W,S)$ and $\cham(W,S)$. However, for the application in <cit.> to tilting theory and birational geometry, it is enough to assume that $S$ is affine or finite.
In either case, a proper subset in $S$ is automatically finitary, so our setting suffices for the purpose.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

Springer, New York

noteTheory and applications
seriesGraduate Texts in Mathematics

Springer, New York

seriesGraduate Texts in Mathematics
titleCombinatorics of Coxeter groups

journaltitleProc. Lond. Math. Soc. (3)
titleA singular Coxeter presentation

notein preparation
titleOn reduced expressions for core double cosets

notein preparation
titleSingular light leaves

titleDemazure operators for double cosets

titleSubexpressions and the Bruhat order for double cosets

titleTits Cone Intersections and Applications
yearaccessed on 20 Nov. 2023
s.gla.ac.uk/ mwemyss/MainFile_for_web.pdf

eprinttypePersonal webpage
notePhD thesis
titleSingular Soergel bimodules

journaltitleInt. Math. Res. Not. IMRN
titleSingular Soergel bimodules