%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{66}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}









\usepackage[dvipsnames]{xcolor}
\usepackage{dynkin-diagrams}

\usepackage{algorithm} 
\usepackage{algorithmic}
\renewcommand{\algorithmicrequire}{ \textbf{Input:}}
\renewcommand{\algorithmicensure}{ \textbf{Output:}}
\usepackage{subfigure}
\usepackage{tikz,tikz-cd}
%\usepackage{todonotes}
\newcommand{\bigdot}{\boldsymbol{\cdot}}

\newcommand{\precdot}{\mathrel{\ooalign{$\prec$\cr
  \hidewidth\raise0.001ex\hbox{$\cdot\mkern0.6mu$}\cr}}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{problem}[theorem]{Problem}

\theoremstyle{definition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\DeclareMathOperator{\wt}{\mathrm{wt}}%weight,as a polynomial in y
\newcommand{\op}[1]{\overset{#1}{\rightsquigarrow}}%operations for cohomology and equivariant cohomology
\DeclareMathOperator{\mul}{\mathrm{mul}}%multiplicity,as an positive integer
\newcommand{\nb}{\mathcal{NB}}%the ideal generated by the classses w.r.t non-boolean elements
\newcommand{\bl}{\mathcal{B}}
\DeclareMathOperator{\supp}{S}%support of an weyl gp element
\newcommand{\di}[1]{B(#1)}%the diagram of a boolean element which is defined in the subsection{boolean elements}
\DeclareMathOperator{\type}{\mathrm{Type}}%type of operation, not the "Lie type"!
\newcommand{\con}[3]{c_{#1}^{#2}(#3)}%contribution of #3 in boolean element #1 w.r.t #2
\newcommand{\none}{\mathbf{None}}

\newcommand{\Yibo}[1]{\todo[size = \tiny,inline,color = yellow!30]{#1 \\ \hfill --- Yibo}}
\newcommand{\Hai}[1]{\todo[size = \tiny,inline,color = green!30]{#1 \\ \hfill --- Hai}}

\usepackage{lipsum}

%% define your title in the usual way
\title[Boolean structure constants]{Boolean structure constants}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[Y. Gao and H. Zhu]{\texorpdfstring{Yibo Gao\thanks{\href{mailto:gaoyibo@bicmr.pku.edu.cn}{gaoyibo@bicmr.pku.edu.cn}}\addressmark{1} \and Hai Zhu\thanks{\href{mailto:zhuhai1686@stu.pku.edu.cn}{zhuhai1686@stu.pku.edu.cn}}\addressmark{2}}{Yibo Gao and Hai Zhu}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Beijing International Center for Mathematical Research, Peking University, Beijing 100871, China \\ \addressmark{2}School of Mathematical Sciences, Peking University, Beijing 100871, China}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{The Schubert problem asks for combinatorial models to compute structure constants of the cohomology ring with respect to the Schubert classes, and has been an important open problem in algebraic geometry and combinatorics that guided fruitful research in decades. In this paper, we provide an explicit formula for the (equivariant) Schubert structure constants $c_{uv}^w$ across all Lie types when the elements $u,v,w$ are boolean. In particular, in type $A$, all Schubert structure constants on boolean elements are either $0$ or $1$.}

%% put your French abstract here, or comment this out if you don't have one
%% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Schubert calculus, Boolean, structure constant, Dynkin diagram}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{ref.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above



\section{Introduction}\label{sec:intro}
% background on Schubert problem
% background on boolean elements
% In our proof, the Dynkin diagram do not have circles of length >=3.
% use \mathbb{Z}[\textbf{t}] to denote the coefficient ring.

Let $G$ be a complex, connected, reductive algebraic group and $B$ be a Borel subgroup of $G$ with a maximal torus $T$. The homogeneous space $G/B$ is called the \emph{generalized flag variety}, which admits a \emph{Bruhat decomposition} $\sqcup_{w\in W}X_w^{\circ}$ into open \emph{Schubert cells}, whose closures are the \emph{Schubert varieties} $\{X_w\:|\: w\in W\}$, indexed by the \emph{Weyl group} $W=N_G(T)/T$. Let $\sigma_w\in H^*(G/B;\mathbb{Z})$ be the Poincar\'e dual of the fundamental class of $X_w$. 

The \emph{Schubert problem} asks for combinatorial interpretations of the structure constants $c_{uv}^w\in\mathbb{Z}_{\ge 0}$ of $H^*(G/B;\mathbb{Z})$ appearing in the expansion $\sigma_u\cdot\sigma_v=\sum_w c_{uv}^w\sigma_w$. It has been a major open problem in algebraic geometry and combinatorics for decades, guiding numerous fruitful research in recent years. We mention a few beautiful results here in the massive literature: the most classical Chevalley--Monk's formula \cite{monk}, Pieri's rule \cite{sottile-pieri}, the separated descent case \cite{huang-separated-descent,knutson-separated-descent-puzzles}, puzzle rules for the Grassmannian \cite{knutson-tao-puzzles,knutson-tao-woodward-puzzles}, a survey on the equivariant Schubert calculus of the Grassmannian \cite{robichaux-survey}, $2$ or $3$ step partial flag varieties \cite{buch-kresch-purbhoo-tamvakis-puzzle,buch-kresch-tamvakis-GW,knutson-zinn-justin-puzzle1}, and various others working in richer cohomology theories. 

The goal of this paper is to make progress towards the Schubert problem. We describe an explicit rule (\Cref{cor:main}) for the Schubert structure constants $c_{uv}^w$ across all Lie types when the element $w$ is \emph{boolean}, a previously unexplored family of the Schubert problem, with connections to the Pieri's rule \cite{sottile-pieri} and hook's rule \cite{postnikov-FK}. Interestingly, our formula demonstrates certain ``multiplicity-freeness'', especially in type $A_n$, where all $c_{uv}^w\in\{0,1\}$ when $w$ is boolean. Boolean elements play an important role in the study of Schubert calculus. The Schubert variety $X_w$ is a toric variety if and only if $w$ is boolean \cite{karupp-boolean}, and the Schubert variety $X_{w_0(I)c}$ is $L_I$-spherical if and only if $c$ is boolean \cite{levi-spherical-1,levi-spherical-2}. 

We work in the generality of the torus equivariant cohomology ring $H_T^*(G/B;\mathbb{Z})$. Let $\{\xi_w\:|\: w\in W\}$ be the \emph{equivariant Schubert classes} and write $\xi_u\cdot\xi_v=\sum d_{uv}^w\xi_w$ where $d_{uv}^w\in \mathbb{Z}[\Lambda]=H_{T}^{*}(\mathrm{pt};\mathbb{Z})$ is the \emph{equivariant Schubert structure constant}. 

\begin{remark}
The Kostant--Kumar formula \cite[Theorem 4.15]{kostant1986nil} provides $d_{uv}^w$ with a recursive formula \cite[Theorem 4.2]{richmond2023nil}. Moreover, in the boolean case, the Kostant--Kumar formula reduces to a combinatorially positive formula as follows.

Let $\mathcal{A} \coloneqq \mathbb{Z}[\alpha_1,\cdots,\alpha_n]$ denote the polynomial algebra in the simple roots and define two operators $\partial_j \, : \, \mathcal{A} \rightarrow \mathcal{A}$ and $B_j \, : \, \mathcal{A} \rightarrow \mathcal{A}$ as
\[\partial_j(p) \coloneqq \frac{s_j(p) - p}{\alpha_j},
\phantom{\;=\;}
B_j(p)\coloneqq\begin{cases}
    \alpha_j \cdot s_j (p) &\text{if $s_j \in S(u) \cap S(v)$}\\
    s_j(p) &\text{if $s_j \in S(u) \bigtriangleup S(v)$}\\
    \partial_j(p) &\text{if $s_j \not\in S(u) \cup S(v)$}
\end{cases}.\]
Let $w \in W$ be a boolean element with support set $S(w)=\{ i_1,i_2,\cdots,i_k \} $ and fix a reduced word $w = s_{i_1}s_{i_2}\cdots s_{i_k}$. Consider $u,v \le w$ and note that $u,v$ must be boolean as well. Furthermore, $u,v$ are uniquely determined by their support sets $S(u),S(v) \subseteq S(w)$. According to \cite[Subsection 4.4]{richmond2023nil}, the Kostant--Kumar formula says that
\begin{equation}\label{eq:kk-formula}
    d_{u,v}^w = B_{i_1} \circ B_{i_2} \circ \cdots \circ B_{i_k}(1).
\end{equation}
Now if $p \in \mathcal{A}$ with non-negative coefficients does not contain the variable $\alpha_j$, then it can be shown using the twisted Leibniz formula \cite[Theorem 11.1.7 part (h)]{kumar2012kac} that $\partial_j(p)$ is a polynomial with non-negative coefficients in the simple roots. Hence Equation~\eqref{eq:kk-formula} is combinatorially positive in the boolean case since the root variable $\alpha_j$ only gets introduced when applying $B_j$.

However, it is not immediately from Equation~\eqref{eq:kk-formula} that boolean structure constants $c_{uv}^w \in \{ 0,1\}$ in type A which we prove in \Cref{cor:0-1}. 
\end{remark}


The following is our main theorem.

\begin{theorem}\label{thm:main}
    For boolean elements $u,v,w\in W$, 
    \[
        d_{uv}^w =\begin{cases}
            \sum\limits_{u\op{\supp(v)}w }\mul(u\op{\supp(v)}w)\cdot\wt(u\op{\supp(v)}w), &\text{if there exists a boolean insertion path $v\op{\supp(u)}w$} \\
            0, &\text{otherwise}
        \end{cases} 
    \]
    where the summation is over all boolean insertion paths $u\op{\supp(v)}w$.
\end{theorem}
The \emph{boolean insertion path} consists of the \emph{boolean insertion steps} that encode the equivariant Chevalley's rule on boolean elements. These steps are also called the \emph{$k$-Bruhat order} in $H^*(\mathrm{Fl}_n;\mathbb{Z})$, and have been very useful in the Schubert problem \cite{lenart-sottile-skew-Schubert,lenart-growth-diagram}. The appearance of our boolean insertion path in the formula is not surprising. What's interesting and what's unique about the boolean elements, is that these paths precisely govern the structure constants in a subtraction-free and multiplicity-free way (\Cref{prop:insert}). 

The precise definitions in \Cref{thm:main} are given in \Cref{def:path-wt,def:path-mul}. We remark that $\mul(u\op{\supp(v)}w)\wt(u\op{\supp(v)}w)$ can be replaced by $\mul(v\op{\supp(u)}w)\wt(v\op{\supp(u)}w)$ in \Cref{thm:main}, making the formula symmetric. The proof is given in \Cref{sec:proof}.

We also have a cohomology version of \Cref{thm:main}.
\begin{corollary}\label{cor:main}
     For boolean elements $u,v,w\in W$,
    \[c_{uv}^w=\begin{cases}
            \sum\limits_{u\op{\supp(v)}w }\mul(u\op{\supp(v)}w), &\text{if there exists a non-equivariant boolean insertion path $v\op{\supp(u)}w$} \\
            0, &\text{otherwise}
        \end{cases} \] where the summation is over all non-equivariant boolean insertion paths $u\op{\supp(v)}w$.
\end{corollary}
Furthermore, $c_{uv}^w\in\{0,1\}$ in type $A$ (\Cref{cor:0-1}). 

This paper is organized as follows. In \Cref{sec:prelim}, we provide the necessary background on root systems, Weyl groups, the equivariant Chevalley's formula, boolean elements and their boolean diagrams. In \Cref{sec:proof}, we introduce the boolean insertion algorithms and prove the main Theorem (\Cref{thm:main}). In \Cref{sec:algo}, we give a fast algorithm to compute $c_{uv}^w$ for boolean elements.



\section{Preliminaries}\label{sec:prelim}
\subsection{Root systems and Weyl groups}
%mention Dynkin diagrams: 1.how to represent a simple reflection action on a root using Dynkin diagrams; 2.how to read orthogonality and ratio of length from Dynkin diagrams
Let $\Phi:=\Phi(\mathfrak{g},T)$ be the \emph{root system} of weights for the adjoint action of $T$ on the Lie algebra $\mathfrak{g}$ of $G$, with a decomposition $\Phi^+\sqcup\Phi^-$ into \emph{positive roots} and negative roots. Let $\Delta=\{\alpha_1,\ldots,\alpha_r\}\subseteq\Phi^+$ be the corresponding set of \emph{simple roots}, which is a basis of $\mathfrak{h}_{\mathbb{R}}^{*}$, the real span of all roots. Let $\langle\cdot,\cdot\rangle$ be the nondegenerate scalar product on $\mathfrak{h}_{\mathbb{R}}^{*}$ induced by the Killing form. For each root $\alpha\in\Phi$, denote by $s_{\alpha}$ the corresponding reflection. 
For simplicity of notations, write the \emph{simple reflections} as $s_i:=s_{\alpha_i}$ for $\alpha_i\in\Delta$. For each root $\alpha\in\Phi$, we have a \emph{coroot} $\alpha^{\vee}=2\alpha/\langle\alpha,\alpha\rangle$. The \emph{fundamental weights} $\{\omega_{\alpha}\:|\:\alpha\in\Delta\}$ are the dual basis to the simple coroots $\{\alpha^{\vee}\:|\:\alpha\in\Delta\}$. Let $\Lambda$ be the weight space and we identify $\mathbb{Z}[\Lambda]$ as $\mathbb{Z}[\mathbf{t}]$, the polynomial ring in $\{t_{\alpha}:=\omega_{\alpha}-s_{\alpha}(\omega_{\alpha})\:|\:\alpha\in\Delta\}$.

\begin{definition}\label{def:dynkin}
The \emph{Dynkin diagram} of $\Phi$ with a choice of simple root $\Delta$ is a directed graph whose vertex set is $\Delta$ with $-2\langle\alpha,\beta\rangle/\langle\beta,\beta\rangle\in\mathbb{N}$ edges going from $\alpha$ to $\beta$ for $\alpha\neq\beta\in\Delta$.
\end{definition}

The \emph{Weyl group}, generated by the reflections $\{s_{\beta}\:|\:\beta\in\Phi\}$, is equipped with a \emph{Coxeter length} function $\ell(w)\coloneqq\min\{\ell\:|\: w=s_{i_1}\cdots s_{i_{\ell}}\}$. Such an expression $w=s_{i_1}\cdots s_{i_{\ell}}$ is called a \emph{reduced word} of $w$ if $\ell(w)=\ell$. The \emph{Bruhat order} on $W$ is generated by $w<ws_{\beta}$ if $\ell(w)<\ell(ws_{\beta})$ for $\beta\in\Phi^+$. For $w\in W$, its \emph{support} is \[\supp(w):=\{\alpha_i\:|\: s_i\text{ appears in any/all reduced words of }w\}.\]

The following result \cite[p.351, Theorem 19.1.2]{anderson2023equivariant} lets us do calculations in $H^*_T(G/B;\mathbb{Z})$.
\begin{theorem}[Equivariant Chevalley's formula]\label{thm:chevalley}
For $\alpha\in\Delta$ and $v \in W$,
\[
\xi_v\cdot\xi_{s_{\alpha}}=(\omega_{\alpha}-v(\omega_{\alpha}))\xi_v+\sum_{\substack{w=vs_{\beta}\\\ell(w)=\ell(v)+1}}\langle\omega_{\alpha},\beta^{\vee}\rangle\ \xi_w
\]
in $H_T^{*}(G/B;\mathbb{Z})$, where we sum over positive roots $\beta\in\Phi^+$.
\end{theorem}


\subsection{Boolean elements}
\begin{definition}
A Weyl group element $w\in W$ is \emph{boolean} if its lower Bruhat interval $[\mathrm{id},w]$ is isomorphic to a boolean lattice.
\end{definition}
The following Lemma is straightforward by the subword property \cite[Theorem 2.2.2]{Bjorner-Brenti}. See also \cite[Proposition 7.3]{tenner-boolean} and \cite[Proposition 3,1]{gao2020boolean}.
\begin{lemma}
An element $w\in W$ is boolean if and only if $w$ is a product of distinct simple reflections. In other words, $w$ is boolean if and only if $\ell(w)=|\supp(w)|$.
\end{lemma}
We now view boolean elements visually using \emph{boolean diagrams}.
\begin{definition}\label{def:boolean-diagram}
For $w\in W$ that is boolean, its \emph{boolean diagram} $\di{w}$ is a directed graph on $\supp(w)$ such that $\alpha_{k}\rightarrow\alpha_{j}$ if $s_{j}$ appears before $s_{k}$ in any/all reduced words of $w$.
\end{definition}
For two boolean diagrams $B(u)$ and $B(w)$, we write $B(u)\subseteq B(w)$ if $\supp(u)\subseteq\supp(w)$ and if $\alpha_k\rightarrow\alpha_j$ in $B(u)$, we also have $\alpha_k\rightarrow\alpha_j$ in $B(w)$.

\begin{ex}\label{ex:boolean-diagram-example}
Consider $w=s_3s_2s_4s_5s_7$ in $W(E_7)$. The Dynkin diagram of type $E_7$ and the boolean diagram $B(w)$ marked with solid nodes are shown in \Cref{fig:boolean-diagram-example}.
\begin{figure}[ht!]
\centering
\dynkin[label,label macro/.code={\alpha_{\drlap{#1}}},edge
    length=.75cm,mark=o]E7
\qquad
\begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {2,3,4,5,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 2);
        \draw[very thick, black,-latex]
            (root 5) to (root 4);
    \end{dynkinDiagram}
\caption{Left: the Dynkin diagram of type $E_7$. Right: $B(s_3s_2s_4s_5s_7)$.}
\label{fig:boolean-diagram-example}
\end{figure}
\end{ex}
Let $\nb$ be the ideal of $H_T^*(G/B;\mathbb{Z})$ spanned by classes $\xi_w$ such that $w$ is not boolean.



\section{Schubert structure constants for boolean elements}\label{sec:proof}
\subsection{The boolean insertion algorithms}
Now we define an operation between boolean elements $u,v\in W$ with respect to a simple root $\alpha$, which is denoted by $u\op{\alpha}v$. In fact, it encodes Equivariant Chevalley's formula in \Cref{thm:chevalley} restricted to boolean elements. In particular, in type $A$, $u\op{k}v$ exactly means that $v$ covers $u$ under the $k$-Bruhat order. We associate each operation with a multiplicity $\mul(u\op{\alpha}v)\in\mathbb{N}$ and weight $\wt(u\op{\alpha}v)\in\mathbb{Z}[\mathbf{t}]=\mathbb{Z}[\Lambda]$ as a nonzero polynomial in $\{t_{\gamma}:=\omega_{\gamma}-s_{\gamma}(\omega_{\gamma})\:|\:\gamma\in\Delta\}$ with non-negative coefficients.
\begin{definition}\label{def:op}
For boolean elements $u,v\in W$ and $\alpha\in\Delta$, we write $u\op{\alpha}v$ and call it a \emph{boolean insertion} if one of the following mutually exclusive events happens:
\begin{enumerate}
\item\label{ev:1} $\alpha\in\supp(u)$, $\ell(v)=\ell(u)+1$, $\di{u}\subseteq\di{v}$ and there is a directed path in $\di{v}$ from $\alpha$ to the unique vertex of $\di{v}\setminus\di{u}$. In this case, $\wt(u\op{\alpha}v)\coloneqq1$.
\item\label{ev:2} $\alpha\in\supp(u)$ and $u=v$. In this case, $\wt(u\op{\alpha}v)\coloneqq\sum\limits_{L}t_{\gamma}$, summing over all directed paths $L$ of the Dynkin diagram from $\alpha$ to some vertex $\gamma\in\supp(u)$, which is compatible with the direction of $B(u)$. Here $L$ is permitted to has length $0$.
\item\label{ev:3} $\alpha\not\in\supp(u)$, $\ell(v)=\ell(u)+1$ and $B(u)\subseteq B(v)$ where $\alpha$ is the unique vertex of $B(v)\setminus B(u)$. In this case, $\wt(u\op{\alpha}v)\coloneqq1$.
\end{enumerate}
We say $u\op{\alpha}v$ is \emph{non-equivariant} if \eqref{ev:1} or \eqref{ev:3} happens and is \emph{equivariant} if \eqref{ev:2} happens.
\end{definition}

Note that a non-equivariant boolean insertion has weight $1$ and changes the element, whereas an equivariant boolean insertion picks up a nontrivial weight without modifying the element. In \Cref{subsec:coh}, we focus only on non-equivariant insertions.

\begin{definition}\label{def:path-wt}
For a boolean insertion path $u^{(0)}\op{\beta_1}u^{(1)}\op{\beta_2}\cdots\op{\beta_n}u^{(n)}$, its \emph{weight} is
\[\wt(u^{(0)}\op{\beta_1}u^{(1)}\op{\beta_2}\cdots\op{\beta_n}u^{(n)})\coloneqq\prod_{j=1}^{n}\wt(u^{(j-1)}\op{\beta_j}u^{(j)}).\]
For convenience, we also write the boolean insertion path above as $u^{(0)}\op{B}u^{(n)}$ where $B=\{\beta_1, \cdots, \beta_n\}$. Note that we need to always fix an ordering $B=\{\beta_1, \cdots, \beta_n\}$ first, before summing over boolean insertion paths $u^{(0)}\op{B}u^{(n)}$ for a fixed set $B$.
\end{definition}
\begin{remark}
The ordering of $B$ in \Cref{def:path-wt} can be arbitrary and we have freedom for practical applications. Choosing an appropriate one is especially useful in \Cref{sec:algo}.
\end{remark}

\begin{ex}\label{ex:op}
The Dynkin diagram of type $E_7$ is shown in \Cref{fig:boolean-diagram-example}. Let $u=s_{_3}s_{_5}s_{_4}s_{_7}$ and $\di{u}$ be its boolean diagram indicated by the solid vertices and directed edges shown in \Cref{fig:op-start}.
\begin{figure}[ht!]
\centering
\begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
\foreach\r in {3,4,5,7} {\dynkinRootMark{*}\r}
\draw[very thick, black,-latex]
            (root 4) to (root 3);
\draw[very thick, black,-latex]
            (root 4) to (root 5);
\end{dynkinDiagram}
\caption{The boolean diagram $B(u)$ for the boolean element $u=s_3s_5s_4s_7$.}
\label{fig:op-start}
\end{figure}
Then there are $5$ boolean elements $v\in W$ satisfying $u\op{\alpha_4}v$, corresponding to the boolean terms in the expansion of $\xi_u \cdot \xi_{\alpha_4}$. One of them is $u$ itself with the equivariant step and $\wt(u\op{\alpha_4}u)=t_3+t_4+t_5$. The other $4$ elements are shown in \Cref{fig:op-end1}.
    
    \begin{figure}[ht!]
    \centering
    \begin{tabular}{cc}
    \begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {1,3,4,5,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 3) to (root 1);
    \end{dynkinDiagram}
    &\begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {2,3,4,5,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 4) to (root 2);
    \end{dynkinDiagram}\\
    \begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {3,4,5,6,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 5) to (root 6);
        \draw[very thick, black,-latex]
            (root 7) to (root 6);
    \end{dynkinDiagram}
    &\begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {3,4,5,6,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 5) to (root 6);
        \draw[very thick, black,-latex]
            (root 6) to (root 7);
    \end{dynkinDiagram}\\
    \end{tabular}
    \caption{The boolean diagrams $B(v)$ for all the boolean elements $v$ satisfying $s_3s_5s_4s_7=u\op{\alpha_4}v$ with a non-equivariant insertion step.}
    \label{fig:op-end1}
    \end{figure}
    In the above example, $\alpha\in\supp(u)$. Now choose $\alpha_6\notin\supp(u)$ and consider $u\op{\alpha_6}v$. Here, only non-equivariant insertion steps are possible. All of the boolean elements $v\in W$ satisfying $u\op{\alpha_6}v$ are shown in \Cref{fig:op-end2}, corresponding to the expansion of $\xi_u \cdot \xi_{\alpha_6}$.
    \begin{figure}[ht!]
    \centering
    \begin{tabular}{cc}
    \begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {3,4,5,6,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 6) to (root 5);
        \draw[very thick, black,-latex]
            (root 7) to (root 6);
    \end{dynkinDiagram}
    &\begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {3,4,5,6,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 6) to (root 5);
        \draw[very thick, black,-latex]
            (root 6) to (root 7);
    \end{dynkinDiagram}\\
    \begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {3,4,5,6,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 5) to (root 6);
        \draw[very thick, black,-latex]
            (root 7) to (root 6);
    \end{dynkinDiagram}
    &\begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]E7
        \foreach\r in {3,4,5,6,7} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 5) to (root 6);
        \draw[very thick, black,-latex]
            (root 6) to (root 7);
    \end{dynkinDiagram}\\
    \end{tabular}
    \caption{The boolean diagrams $B(v)$ for $s_3s_5s_4s_7=u\op{\alpha_6}v$.}
    \label{fig:op-end2}
    \end{figure}
\end{ex}

\begin{ex}\label{ex:wt}
Consider a non simply-laced case. Let $u=s_2s_3s_4$ in $W(C_4)$ shown in \Cref{fig:wt}. Since there are $2$ edges from $\alpha_4$ to $\alpha_3$ of the Dynkin diagram by \Cref{def:dynkin}, there are $2$ directed paths from $\alpha_4$ to $\alpha_3$ and $2$ directed paths from $\alpha_4$ to $\alpha_2$ in the Dynkin diagram aligning with the direction of $B(u)$. It follows that $\wt(u\op{\alpha_4}u)=2t_2+2t_3+t_4$.
    \begin{figure}[ht!]
    \centering
    \begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]C4
        \foreach\r in {2,3,4} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
    \end{dynkinDiagram}
    \caption{The boolean diagrams $B(u)$ for $u=s_2s_3s_4$}
    \label{fig:wt}
    \end{figure}
\end{ex}
\begin{definition}\label{def:mul}
    For $u\op{\alpha}v$, define its \emph{multiplicity}, denoted by $\mul(u\op{\alpha}v)$, as follows:
    \begin{enumerate}
        \item If $u\op{\alpha}v$ is equivariant as in \Cref{def:op}, $\mul(u\op{\alpha}v)\coloneqq1$.
        \item If $u\op{\alpha}v$ is non-equivariant as in \Cref{def:op}, let $\gamma$ be the unique vertex of $B(v)\setminus B(u)$. Then $\mul(u\op{\alpha}v)$ is the number of directed paths from $\alpha$ to $\gamma$ in the Dynkin diagram which are compatible with the direction of $B(v)$.
    \end{enumerate}
\end{definition}
Note that when event~\eqref{ev:2} or \eqref{ev:3} in \Cref{def:op} occurs, $\mul(u\op{\alpha}v)=1$.
\begin{definition}\label{def:path-mul}
    For a boolean insertion path $u^{(0)}\op{\beta_1}u^{(1)}\op{\beta_2}\cdots\op{\beta_n}u^{(n)}$,  its \emph{multiplicity} is the product of the multiplicities of all its steps.
%\[\mul(u^{(0)}\op{\beta_1}u^{(1)}\op{\beta_2}\cdots\op{\beta_n}u^{(n)})\coloneqq\prod_{j=1}^{n}\mul(u^{(j-1)}\op{\beta_j}u^{(j)}).\]
\end{definition}
\begin{ex}\label{ex:mul}
    Consider $u=s_2s_3s_4$ in $W(C_4)$ shown in \Cref{fig:wt}. The boolean insertion $u\op{\alpha_4}v$ gives $v=s_1s_2s_3s_4$ shown in \Cref{fig:mul}. In this case, $\mul(u\op{\alpha_4}v)=2$.
    \begin{figure}[ht!]
    \centering
    \begin{dynkinDiagram}[label,label macro/.code={\alpha_{\drlap{#1}}},edge length=.75cm,mark=o]C4
        \foreach\r in {1,2,3,4} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 4) to (root 3);
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
        \draw[very thick, black,-latex]
            (root 2) to (root 1);
    \end{dynkinDiagram}
    \caption{The boolean diagram $B(v)$ for $v=s_1s_2s_3s_4$.}
    \label{fig:mul}
    \end{figure}
\end{ex}
Restricting \Cref{thm:chevalley} to boolean elements yields the following lemma, which is the basis of our calculations.

\begin{lemma}\label{lem:monk}
    For $\alpha\in\Delta$ and a boolean element $v\in W$,
    \[\xi_v\cdot\xi_{s_\alpha}=\sum_{v\op{\alpha}w}\mul(v\op{\alpha}w)\wt(v\op{\alpha}w)\xi_w \mod \nb.\]
\end{lemma}




\subsection{Multiplying Schubert classes indexed by boolean elements}\label{subsec:mult}
Recall that once we fix an ordering $B=\{\beta_1, \cdots, \beta_n\}\subseteq\Delta$, a boolean insertion path $u=u^{(0)}\op{\beta_1}u^{(1)}\op{\beta_2}\cdots\op{\beta_n}u^{(n)}=w$ can be written as $u\op{B}w$. The following is a direct corollary of \Cref{lem:monk}, which is obtained from applying \Cref{lem:monk} on $\beta_1,\ldots,\beta_n$ step by step. 
\begin{corollary}\label{cor:monk}
    For boolean element $u\in W$ and a set of simple roots $B\subseteq\Delta$, fix an ordering $B=\{\beta_1, \cdots, \beta_n\}$ of $B$, then
    \[\xi_u\prod_{\beta\in B}\xi_{s_{\beta}}=\sum_{u\op{B}w}\mul(u\op{B}w)\wt(u\op{B}w)\xi_{w} \mod \nb\]
    summing over all boolean insertion paths $u=u^{(0)}\op{\beta_1}u^{(1)}\op{\beta_2}\cdots\op{\beta_n}u^{(n)}=w$.
\end{corollary}
For convenience, for $f\in H_T^*(G/B;\mathbb{Z})$, we write $[\xi_w]f$ for the coefficient of $\xi_w$ in $f$ expanded in the basis of the equivariant Schubert classes.

The following result is the last technical lemma for \Cref{thm:main}.
\begin{lemma}\label{lem:sym}
    For boolean elements $u,v,w\in W$ satisfying $u\op{\supp(v)}w$ and $v\op{\supp(u)}w$,
    \[[\xi_w](\xi_u\cdot\xi_v)\!=\![\xi_w]\Big(\xi_u\prod_{\beta\in\supp(v)}\xi_{s_{\beta}}\Big)\!=\![\xi_w]\Big(\Big(\prod_{\alpha\in\supp(u)}\xi_{s_{\alpha}}\Big)\xi_v\Big)\!=\![\xi_w]\Big(\Big(\prod_{\alpha\in\supp(u)}\xi_{s_{\alpha}}\Big)\Big(\prod_{\beta\in\supp(v)}\xi_{s_{\beta}}\Big)\Big).\]
\end{lemma}
\begin{proof}
    (Sketch.) By \Cref{lem:monk}, we have that
    \[\prod_{\alpha\in\supp(u)}\xi_{s_{\alpha}}=\sum_{\supp(u^{\prime})=\supp(u)}\xi_{u^{\prime}}\mod{\nb},\qquad\prod_{\beta\in\supp(v)}\xi_{s_{\beta}}=\sum_{\supp(v^{\prime})=\supp(v)}\xi_{v^{\prime}}\mod{\nb}\] summing over boolean elements $u^{\prime}$ and $v^{\prime}$. It follows that
    \begin{equation}
    \label{eq:exp}\Big(\prod_{\alpha\in\supp(u)}\xi_{s_{\alpha}}\Big)\Big(\prod_{\beta\in\supp(v)}\xi_{s_{\beta}}\Big)=\sum_{u^{\prime},v^{\prime}}\xi_{u^{\prime}}\xi_{v^{\prime}} \mod{\nb}
    \end{equation}
    summing over boolean elements $u^{\prime},v^{\prime}\in W$ satisfying $\supp(u^{\prime})=\supp(u)$ and $\supp(v^{\prime})=\supp(v)$. Note that the terms $\xi_{u^{\prime}}\xi_{v^{\prime}}$ on the right hand side of \eqref{eq:exp} are all ``disjoint'', after expanding in the basis of the equivariant Schubert classes and restricting to the boolean elements. Further, with \Cref{cor:monk}, $u\op{\supp(v)}w$ and $v\op{\supp(u)}w$ indicate that $\xi_w$ appears in the expansions of both $\xi_u\prod_{\beta\in\supp(v)}\xi_{s_{\beta}}$ and $\Big(\prod_{\alpha\in\supp(u)}\xi_{s_{\alpha}}\Big)\xi_v$, completing the proof.
\end{proof}
\begin{remark}
\Cref{lem:sym} demonstrates a very unique property of boolean elements. Let $u\in W$ be any element and let $\mathbf{u}$ be a reduced word of $u$. We know that $\prod_{\alpha\in\mathbf{u}}\xi_{s_{\alpha}}$ contains $\xi_u$ and a lot of other terms. In general, we expect \[[\xi_w](\xi_u\cdot\xi_v)<[\xi_w]\Big(\prod_{\alpha\in\mathbf{u}}\xi_{s_{\alpha}}\Big)\Big(\prod_{\beta\in\mathbf{v}}\xi_{s_{\beta}}\Big).\]
However, \Cref{lem:sym} tells us that when $w$ is boolean, which implies that the relevant $u$ and $v$ are also boolean, we have an equality so that the structure constants are manageable. 
\end{remark}

We are now ready to prove \Cref{thm:main}.
\begin{proof}[Proof of \Cref{thm:main}]
    By \Cref{lem:sym}, we have 
    \[d_{uv}^w=[\xi_w](\xi_u\cdot\xi_v)=[\xi_w]\Big(\xi_u\prod_{\beta\in\supp(v)}\xi_{s_{\beta}}\Big).\]
    We are done by applying \Cref{cor:monk} to the right hand side.
\end{proof}

\subsection{Structure constants in the cohomology ring \texorpdfstring{$H^*(G/B;\mathbb{Z})$}{H*(G/B;Z)}}\label{subsec:coh}
In this section, we only need to consider non-equivariant boolean insertions with weights equal to $1$.
% First we can prove \Cref{cor:main} immediately.
\begin{proof}[Proof of \Cref{cor:main}]
The cohomology version can be derived from the equivariant cohomology version by setting $t_{\alpha}=0$ in \Cref{thm:main} for each simple root $\alpha\in\Delta$. This is equivalent to requiring each boolean insertion to be non-equivariant with weight $1$.
\end{proof}

The following result is an interesting property of boolean insertions.
\begin{proposition}\label{prop:insert}
In the case where the Dynkin diagram is a path, fix an ordering $B=\{\beta_1, \cdots, \beta_n\}$ of a set of simple roots $B\subseteq\Delta$, then there exists at most one non-equivariant boolean insertion path $u\op{B}w$ for any boolean elements $u,w\in W$.
\end{proposition}

In type $A$, all the multiplicities as in \Cref{def:mul} are $1$. Combining \Cref{cor:main} and \Cref{prop:insert}, we arrive at the following result.
\begin{corollary}\label{cor:0-1}
For boolean elements $u,v,w$ in the Weyl group of type $A$, $c_{uv}^w=1$ if there exist non-equivariant boolean insertion paths $u\op{\supp(v)}w$ and $v\op{\supp(u)}w$; $c_{uv}^{w}=0$ otherwise.
\end{corollary}



\section{Fast algorithms for computation}\label{sec:algo}
In this section, we work in type $A_n$. We provide \Cref{algo} that determines whether there exists a non-equivariant boolean insertion path $u\op{\supp(v)}w$ for boolean elements $u,v,w\in W$. This algorithm works by finding a good ordering of $S(v)$ for the insertion paths. The correctness and the time complexity of the algorithm is provided in \Cref{thm:work}. By \Cref{cor:main}, we can calculate the structure constants $c_{uv}^w$ for boolean permutations in the symmetric group in $O(n^2)$ time as well. 

\begin{algorithm}[ht!]
\begin{algorithmic}[1]
\caption{Construction of a boolean insertion path}\label{algo}
\REQUIRE Boolean elements $u,v,w\in W$.
\ENSURE A boolean insertion path $u\op{\supp(v)}w$ if it exists.
    \STATE Initialize $B=B(u)$, $P$ to be an empty list and $S=\supp(v)$. 
    \STATE Check whether $B(u)\subseteq B(w)$. If not, return $\none$.
    \STATE For each $i\in S$ in increasing order, try the boolean insertion $B\op{i}$. If there is only one possible insertion step $B\op{i} B'$ satisfying $B'\subseteq B(w)$, remove $i$ from $S$, append this step to $P$ and replace $B$ by $B'$. If no such $B'\subseteq B(w)$ exists, return $\none$.
    \STATE Repeat Step 3 until no such insertions are available.
    \STATE Let the remaining vertices in $S$ and $B(w)\setminus B$ be $i_1<i_2<\cdots <i_m$ and $j_1<j_2<\cdots <j_m$ respectively. For $k=1,\ldots,m$ in increasing order, do $B\op{i_k}B'$ such that the newly added vertex in $B'$ is exactly $j_k$ and that $B'\subseteq B(w)$. Append this sequence of insertions to $P$ if they exist and return $\none$ if not.
    \STATE Return $P$.
\end{algorithmic}
\end{algorithm}

\begin{ex}\label{ex:algo}
    Let $u=s_4s_3s_8s_{11}s_{12}$, $v=s_2s_3s_7s_6s_8s_{12}$ and $ w=s_7s_6s_5s_4s_2s_3s_9s_8s_{11}s_{13}s_{12}$. In \Cref{algo}, we begin with $B=B(u_0)$ where $u_0=u$ and $S=\supp(v)=\{2,3,6,7,8,12\}$. The boolean diagrams of $u$ and $w$ and all steps in \Cref{algo} are shown in \Cref{fig:algo}. 
    \begin{figure}[ht!]
    \centering
    \subfigure[In each step, we should keep $B\subseteq B(w)$]{
    \begin{tabular}{cc}
         $B(w)$
         & \begin{dynkinDiagram}[labels={1,2,3,4,5,6,7,8,9,10,11,12,13},edge length=.75cm,mark=o]A{13}
        \foreach\r in {2,3,4,5,6,7,8,9,11,12,13} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
        \draw[very thick, black,-latex]
            (root 3) to (root 4);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 5) to (root 6);
        \draw[very thick, black,-latex]
            (root 6) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 9);
        \draw[very thick, black,-latex]
            (root 12) to (root 11);
        \draw[very thick, black,-latex]
            (root 12) to (root 13);
    \end{dynkinDiagram}
    \end{tabular}
    }
    \subfigure[Initialize, $S=\{2,3,6,7,8,12\}$]{
    \begin{tabular}{cc}
         $B(u_0)$
         & \begin{dynkinDiagram}[labels={1,2,3,4,5,6,7,8,9,10,11,12,13},edge length=.75cm,mark=o]A{13}
        \foreach\r in {3,4,8,11,12} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 3) to (root 4);
        \draw[very thick, black,-latex]
            (root 12) to (root 11);
    \end{dynkinDiagram}
    \end{tabular}
    }
    \subfigure[$u_0\op{2}u_1$ in Step 3, $S=\{3,6,7,8,12\}$]{
    \begin{tabular}{cc}
         $B(u_1)$&  \begin{dynkinDiagram}[labels={1,2,3,4,5,6,7,8,9,10,11,12,13},edge length=.75cm,mark=o]A{13}
        \foreach\r in {2,3,4,8,11,12} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
        \draw[very thick, black,-latex]
            (root 3) to (root 4);
        \draw[very thick, black,-latex]
            (root 12) to (root 11);
    \end{dynkinDiagram}
    \end{tabular}
    }
    \subfigure[$u_1\op{6}u_2$ in Step 3, $S=\{3,7,8,12\}$]{
    \begin{tabular}{cc}
         $B(u_2)$&\begin{dynkinDiagram}[labels={1,2,3,4,5,6,7,8,9,10,11,12,13},edge length=.75cm,mark=o]A{13}
        \foreach\r in {2,3,4,6,8,11,12} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
        \draw[very thick, black,-latex]
            (root 3) to (root 4);
        \draw[very thick, black,-latex]
            (root 12) to (root 11);
    \end{dynkinDiagram}
    \end{tabular}
    }
    \subfigure[$u_2\op{7}u_3$ in Step 3, $S=\{3,8,12\}$]{
    \begin{tabular}{cc}
         $B(u_3)$&\begin{dynkinDiagram}[labels={1,2,3,4,5,6,7,8,9,10,11,12,13},edge length=.75cm,mark=o]A{13}
        \foreach\r in {2,3,4,6,7,8,11,12} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
        \draw[very thick, black,-latex]
            (root 3) to (root 4);
        \draw[very thick, black,-latex]
            (root 12) to (root 11);
        \draw[very thick, black,-latex]
            (root 6) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 7);
    \end{dynkinDiagram}
    \end{tabular}
    }
    \subfigure[$u_3\op{8}u_4$ in Step 3, $S=\{3,12\}$]{
    \begin{tabular}{cc}
         $B(u_4)$&\begin{dynkinDiagram}[labels={1,2,3,4,5,6,7,8,9,10,11,12,13},edge length=.75cm,mark=o]A{13}
        \foreach\r in {2,3,4,6,7,8,9,11,12} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
        \draw[very thick, black,-latex]
            (root 3) to (root 4);
        \draw[very thick, black,-latex]
            (root 12) to (root 11);
        \draw[very thick, black,-latex]
            (root 6) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 9);
    \end{dynkinDiagram} 
    \end{tabular}
    }
    \subfigure[$u_4\op{3}u_5$ in Step 5, $S=\{12\}$]{
    \begin{tabular}{cc}
         $B(u_5)$&\begin{dynkinDiagram}[labels={1,2,3,4,5,6,7,8,9,10,11,12,13},edge length=.75cm,mark=o]A{13}
        \foreach\r in {2,3,4,5,6,7,8,9,11,12} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
        \draw[very thick, black,-latex]
            (root 3) to (root 4);
        \draw[very thick, black,-latex]
            (root 12) to (root 11);
        \draw[very thick, black,-latex]
            (root 6) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 9);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 5) to (root 6);
    \end{dynkinDiagram} 
    \end{tabular}
    }
    \subfigure[$u_5\op{12}u_6$ in Step 5, $S=\varnothing$]{
    \begin{tabular}{cc}
         $B(u_6)$&\begin{dynkinDiagram}[labels={1,2,3,4,5,6,7,8,9,10,11,12,13},edge length=.75cm,mark=o]A{13}
        \foreach\r in {2,3,4,5,6,7,8,9,11,12,13} {\dynkinRootMark{*}\r}
        \draw[very thick, black,-latex]
            (root 3) to (root 2);
        \draw[very thick, black,-latex]
            (root 3) to (root 4);
        \draw[very thick, black,-latex]
            (root 12) to (root 11);
        \draw[very thick, black,-latex]
            (root 6) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 7);
        \draw[very thick, black,-latex]
            (root 8) to (root 9);
        \draw[very thick, black,-latex]
            (root 4) to (root 5);
        \draw[very thick, black,-latex]
            (root 5) to (root 6);
        \draw[very thick, black,-latex]
            (root 12) to (root 13);
    \end{dynkinDiagram} 
    \end{tabular}
    }
    \caption{An example for \Cref{algo}, that results in a boolean insertion path $u=u_0\op{2}u_1\op{6}u_2\op{7}u_3\op{8}u_4\op{3}u_5\op{12}u_6=w$.}
    \label{fig:algo}
    \end{figure}
    In the end, we obtain a boolean insertion path $u\op{\supp(v)}w$. In fact, there is a boolean insertion path $v\op{\supp(u)}w$ as well. Thus, by \Cref{cor:0-1}, $c_{uv}^w=1$.
\end{ex}

\begin{theorem}\label{thm:work}
    \Cref{algo} returns a boolean insertion path $u\op{\supp(v)}w$ if it exists and otherwise returns $\none$. The runtime of \Cref{algo} is $O(n^2)$ in type $A_n$.
\end{theorem}
\begin{remark}
In arbitrary types, we can construct similar algorithms to find insertion paths and to compute structure constants $c_{uv}^w$ for boolean elements with the same time complexity $O(n^2)$, where $n=\mathrm{rank}(\Phi)$. The general idea stays the same.
\end{remark}

\acknowledgements{We thank Prof. Anders Buch's equivariant Schubert calculator for calculations and we thank Weihong Xu, Rui Xiong and Alex Yong for pointing to us helpful references. }

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography


\end{document}
