%% 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]{FPSAC2023}
\articlenumber{86}
%% 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{tikz}
\usepackage{tikz-cd}
\newcommand{\creflastconjunction}{, and\nobreakspace}
\usepackage{mathtools}
\usepackage{float}

\usetikzlibrary{decorations.markings, arrows.meta}

\tikzcdset{
 arrow style=tikz,
 diagrams={>={Straight Barb[scale=0.8]}},
 marrow/.style={decoration={markings,mark=at position 0.5 with {\arrow{#1}}}, postaction=decorate},
 rmarrow/.style={decoration={markings,mark=at position 0.8 with {\arrow{#1}}}, postaction=decorate}
}

\newtheorem{theorem}{Theorem}
\newtheorem*{theorem*}{Main Theorem}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}[lemma]{Proposition}
\newtheorem*{conjecture*}{Conjecture}

\theoremstyle{definition}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{definition}[lemma]{Definition}

\renewcommand{\AA}{\mathbb{A}}
\newcommand{\BB}{\mathbb{B}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\DD}{\mathbb{D}}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\GG}{\mathbb{G}}
\newcommand{\HH}{\mathbb{H}}
\newcommand{\II}{\mathbb{I}}
\newcommand{\JJ}{\mathbb{J}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\LL}{\mathbb{L}}
\newcommand{\MM}{\mathbb{M}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\OO}{\mathbb{O}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\renewcommand{\SS}{\mathbb{S}}
\newcommand{\TT}{\mathbb{T}}
\newcommand{\UU}{\mathbb{U}}
\newcommand{\VV}{\mathbb{V}}
\newcommand{\WW}{\mathbb{W}}
\newcommand{\XX}{\mathbb{X}}
\newcommand{\YY}{\mathbb{Y}}
\newcommand{\ZZ}{\mathbb{Z}}

%Calligraphic letters

\newcommand{\cA}{\mathcal{A}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cJ}{\mathcal{J}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cN}{\mathcal{N}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cQ}{\mathcal{Q}}
\newcommand{\cR}{\mathcal{R}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cV}{\mathcal{V}}
\newcommand{\cW}{\mathcal{W}}
\newcommand{\cX}{\mathcal{X}}
\newcommand{\cY}{\mathcal{Y}}
\newcommand{\cZ}{\mathcal{Z}}

\newcommand{\tA}{\widetilde{A}}
\newcommand{\tB}{\widetilde{B}}
\newcommand{\tC}{\widetilde{C}}
\newcommand{\tD}{\widetilde{D}}
\newcommand{\tG}{\widetilde{G}}
\newcommand{\tS}{\widetilde{S}}
\newcommand{\tT}{\widetilde{T}}
\newcommand{\tR}{\widetilde{R}}
\newcommand{\tH}{\widetilde{H}}
\newcommand{\te}{\widetilde{e}}

%% define your title in the usual way
\title{Combinatorial invariance for lower intervals using hypercube decompositions}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Grant T. Barkley and Christian Gaetz]{Grant T. Barkley\thanks{\href{mailto:gbarkley@math.harvard.edu}{gbarkley@math.harvard.edu}. GTB was supported by NSF grant DMS-1854512.}\addressmark{1} \and Christian Gaetz\thanks{\href{mailto:crgaetz@gmail.com}{crgaetz@gmail.com}. CG was partially supported by a Klarman Postdoctoral Fellowship at Cornell University and by an NSF Postdoctoral Research Fellowship  (DMS-2103121).}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Harvard University, Cambridge MA \\ \addressmark{2}Cornell University, Ithaca NY}

%% put the date of submission here
\received{November 15, 2022}

%% 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{We give a new proof of the combinatorial invariance conjecture for lower intervals of the symmetric group. This conjecture posits that Kazhdan--Lusztig polynomials associated to intervals in the Bruhat order depend only on the poset structure of the interval. For lower intervals of the symmetric group, this was originally shown by Brenti using special matchings. Our proof uses a different combinatorial structure, called a hypercube decomposition, which was recently introduced by Blundell, Buesing, Davies, Veli{\v{c}}kovi{\'{c}}, and Williamson as an approach to proving combinatorial invariance for arbitrary intervals. Instead of studying the Kazhdan--Lusztig polynomials directly, we apply hypercube decompositions to the related family of $\widetilde{R}$-polynomials. We prove a new, explicit combinatorial recurrence for $\widetilde{R}$-polynomials using certain hypercube decompositions.}

%% 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{Bruhat order, Kazhdan--Lusztig polynomials, $R$-polynomials}

%% 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]{biblatex}
\addbibresource{KL.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}

Kazhdan--Lusztig polynomials $P_{u,v}(q)$ are polynomials associated to a pair $u,v$ of elements of a Coxeter group $W$. They were first introduced in \cite{Kazhdan1979} as transition functions between the standard basis of the Hecke algebra of $W$ and the Kazhdan--Lusztig basis. The polynomials can also be defined geometrically: if $X_u,X_v$ are the Schubert cells associated to $u$ and $v$ in a flag variety, and $x\in X_u$ is any point, then $P_{u,v}(q)$ is the Poincare polynomial of the stalk at $x$ of the intersection cohomology sheaf on the Schubert variety $\overline{X}_v$. Recall that the Bruhat order is a partial order on Coxeter group elements such that $u\leq v$ if and only if $X_u$ is contained in the Schubert variety $\overline{X}_v$. In particular, $P_{u,v}(q)=0$ unless $u\leq v$. The \emph{combinatorial invariance conjecture} is the assertion, proposed by Dyer \cite{Dyer1987} and Lusztig, that if the Bruhat intervals $[u,v]$ and $[u',v']$ are isomorphic as posets, then $P_{u,v}(q) = P_{u',v'}(q)$. 

If $u=u'=e$, so that both $[u,v]$ and $[u',v']$ are lower intervals in Bruhat order, then the combinatorial invariance conjecture is a theorem. This was first proven when $W=S_n$ by Brenti \cite{Brenti2004} using \emph{special matchings} of the Hasse diagram of $[e,v]$. Du Cloux \cite{DuCloux2003} then extended the result to a large class of Coxeter groups using an analysis of isomorphisms between lower intervals. Finally combinatorial invariance of lower intervals was shown for all Coxeter groups by Delanoy \cite{Delanoy2006} and independently by Brenti--Caselli--Marietti \cite{Brenti2006} via a classification of all possible special matchings of these posets. Little is known about special matchings in intervals that are not lower, and there exist non-lower intervals which have no special matchings. As a result, the technique used by these authors does not extend to all intervals, and there are few other cases where combinatorial invariance is known. These include intervals with no subinterval isomorphic to Bruhat order on $S_3$ \cite{Brenti1994}, intervals of $S_n$ with length up to 8 \cite{Dyer1987,Incitti2006,Incitti2007},  intervals in the infinite group $\widetilde A_2$ \cite{Burrull2022}, and intervals where $P_{u,v}(q)=1$ \cite{Carrell1994,Deodhar1985}. 

Here we will give a new proof of combinatorial invariance for lower intervals in the symmetric group, which is quite distinct from the earlier proofs using special matchings. Our method gives hope for proving combinatorial invariance for an arbitrary interval of $S_n$, because the combinatorial structure it relies upon exists in every such interval (in contrast to special matchings). Following the conventions in this area, we will say that a notion is \emph{combinatorial} if it depends only on the isomorphism class of the poset $[u,v]$.
 
Our proof is inspired by recent work of Blundell, Buesing, Davies, Veli{\v{c}}kovi{\'{c}}, and Williamson \cite{Blundell2023}, in which the authors created a machine learning model to predict $P_{u,v}(q)$ from the Bruhat graph associated to $[u,v]$. They found that the model placed more importance on edges that formed a subgraph shaped like the edges of a hypercube. A more refined analysis led them to the notion of a \emph{hypercube decomposition}. A hypercube decomposition of $[u,v]$ is a subinterval $[u,z]$ whose complement contains many hypercubes (see \Cref{def:hyp}). The authors conjecture an intriguing combinatorial recursion for $P_{u,v}(q)$ that should hold for any hypercube decomposition. They also show that the formula is true for a certain (non-combinatorial) \emph{standard hypercube decomposition} which exists in any interval of the symmetric group. 

In this paper we do not prove their conjecture, or even study the polynomials $P_{u,v}(q)$ directly at all. Instead we prove a more explicit recursion for a related family of polynomials, the $\tR$-polynomials. For elements $u\leq v$ of a Coxeter group $W$, Theorem 5.1.4 of \cite{Bjorner2005} implies that combinatorial invariance of $\tR_{u,z}(q)$ for all $z\in [u,v]$ is equivalent to combinatorial invariance of $P_{u,z}(q)$ for all $z\in [u,v]$. We also specialize to certain \emph{strong} hypercube decompositions (see \Cref{def:stronghyp}), which include the standard hypercube decomposition. In the next section we define a combinatorial polynomial $\tH_{u,z,v}(q)$ associated to a hypercube decomposition and depending on the polynomials $\tR_{u,x}$ for $x\leq z$.

\newpage
\begin{theorem*}\label{thm:introthm}\hypertarget{thm:main}{}
	Let $W=S_n$. Then for any $v\in W$, and any $z\leq v$ such that $[e,z]$ gives a strong hypercube decomposition of $[e,v]$, we have 
	\[ \tR_{e,v}(q) = \tH_{e,z,v}(q). \]
	
	%\vspace{.5em}
	Furthermore, for any $u < v$ in $S_n$, there exists $u\leq z < v$ such that $[u,z]$ gives a strong hypercube decomposition of $[u,v]$, and we have
	\begin{equation}\label{eqn} \tR_{u,v}(q) = \tH_{u,z,v}(q). \tag{$\ast$} \end{equation}
	
	As a result of these two facts, the polynomial $\tR_{e,v}(q)$ depends only on the isomorphism class of $[e,v]$ as a poset. 
\end{theorem*}

The first fact alone is not enough to imply combinatorial invariance for lower intervals: without the second fact (for $u=e$), our combinatorial recursion for $\tR_{e,v}$ may not reach a base case. But also the second fact of the theorem alone does not imply any cases of combinatorial invariance, because the $z$ produced there is not defined combinatorially.  

In light of the theorem statement, one might ask whether \eqref{eqn} always holds for any strong hypercube decomposition of $[u,v]$. The answer is no; a (minimal) counterexample is given by 
\[u=[132546],~z=[612345],~v=[651234].\] 
However, we make the following conjecture, which when combined with the main theorem implies combinatorial invariance. For polynomials $P$ and $Q$, we write $P\leq Q$ to mean that the coefficient of $q^k$ in $P$ is less than or equal to that in $Q$, for all $k$.

\begin{conjecture*}\hypertarget{conj}{}
	For any interval $[u,v]$ in $S_n$, and any strong hypercube decomposition $[u,z]$, we have
	\[ \tR_{u,v} \leq \tH_{u,z,v}. \]
\end{conjecture*}

The %\hyperlink{thm:main}{Main Theorem} 
main theorem is a summary of \Cref{thm:formula,,thm:existence,,thm:stdeqn}. To state these theorems requires some details on hypercube decompositions, which are given in the next section. %\Cref{sec:Background}. %The theorems are then proven in \Cref{sec:proofs}.

\vspace{1.5em}

\noindent The authors have generalized the results announced in this extended abstract in order to prove new interesting cases of combinatorial invariance. For the details, see \cite{Barkley2023}. That same reference contains the details of many proofs which are omitted here.

%Using a strong hypercube decomposition of a lower interval, \Cref{thm:main} gives an explicit combinatorial recursion for $\tR_{u,v}(q)$. Since combinatorial invariance for $\tR_{u,v}$ is equivalent to combinatorial invariance for $P_{u,v}$ \cite{BB}, this .


%\acknowledgements{\lipsum[20]}

\section{Hypercube decompositions}\label{sec:Background}

Let $W$ be a Coxeter group with generating set $S$ and reflection set $T \coloneqq \{wsw^{-1}\mid w\in W, s\in S\}$. Elements of these sets are called simple generators and reflections, respectively. For the \hyperlink{thm:introthm}{Main Theorem} it will suffice to take $W=S_n$, $S = \{(12), (23), \ldots, (n-1,n)  \}$, and $T = \{(ab) \mid a<b  \}$, but some of the results hold for any Coxeter group. Here we write $(ab)$ or $(a,b)$ to denote the transposition swapping $a$ and $b$. We will also use one-line notation for permutations: $[3124]$ and $[3,1,2,4]$ both denote the permutation sending $1\mapsto 3, 2\mapsto 1, 3\mapsto 2, 4\mapsto 4$. The length of a Coxeter group element $w$ the minimal number of simple generators needed to express $w$ and is denoted $\ell(w)$.

\begin{definition}\label{def:brugraph}
	The \emph{Bruhat graph} $\Omega_W$ is the directed graph with vertices given by the elements of $W$ and an edge from $u$ to $v$ if and only if $\ell(u)<\ell(v)$ and $vu^{-1}$ is a reflection. We make this an edge-labeled graph by labeling the edge $u\to v$ by the unique reflection $t\in T$ such that $tu=v$. We denote this by $u \xrightarrow{t} v$.
	
	We say $u\leq v$ in \emph{Bruhat order} if there is path from $u$ to $v$ in the Bruhat graph. The Bruhat graph $\Omega_{u,v}$ is the induced subgraph of $\Omega_W$ on the elements of $[u,v]$.
\end{definition}

From this description there are two facts that aren't obvious about the Bruhat graph:

\begin{proposition}[{\cite[Proposition 3.3]{Dyer1991a}}]
	The Bruhat order is a graded poset with rank function $\ell$. In particular, the Hasse diagram of Bruhat order is a subgraph of $\Omega_W$. Furthermore, the unlabeled graph underlying $\Omega_{u,v}$ is determined by the poset isomorphism class of $[u,v]$.
\end{proposition}

As a result of this proposition, we are allowed to use the (unlabeled) edges of $\Omega_{u,v}$ in constructing combinatorial invariants. The following definition introduces our main object of study, the $\tR$-polynomials.

\begin{definition}
	A \emph{reflection order} is a total ordering $\prec$ on the reflections $T$ satisfying certain properties (see \cite[Section 5.2]{Bjorner2005}). If $W=S_n$, reflection orders are exactly those such that whenever $1\leq a < b < c \leq n$, we have either
	\[ (ab) \prec (ac) \prec (bc) \text{ or } (bc) \prec (ac) \prec (ab) \]
	
	Fix a reflection order $\prec$. An \emph{increasing path} of length $k$ in the Bruhat graph $\Omega_{u,v}$ is a path $u \xrightarrow{t_1} u_1 \xrightarrow{t_2} \cdots \xrightarrow{t_k} u_k = v$ such that $t_1\prec t_2 \prec \cdots \prec t_k$ in the reflection order. The \emph{$\tR$}-polynomial is defined by 
	\[ \tR_{u,v}(q) = \sum_{k=0}^{\ell(v)-\ell(u)} (\text{\# of length-$k$ increasing paths in $\Omega_{u,v}$})\cdot q^k. \]
\end{definition}

\begin{proposition}[{\cite[Theorems 5.1.4 and 5.3.4]{Bjorner2005}}]
	The $\tR$-polynomials are independent of the choice of reflection order. Furthermore, the Kazhdan--Lusztig polynomial $P_{u,v}(q)$ can be computed from the family $\tR_{u,z}(q)$ as $z$ varies in $[u,v]$. In particular, combinatorial invariance for $\tR$-polynomials implies combinatorial invariance for Kazhdan--Lusztig polynomials.
\end{proposition} 

The proposition implies that the Kazhdan--Lusztig polynomials can be computed from $\Omega_{u,v}$ as an abstract digraph with its edge-labeling by elements of $T$. 
%This is non-obvious and, using Dyer's \cite[Thm subgraphs]{graphs}, allows one to prove ``any two isomorphic intervals of length $k$ in any finite Coxeter group have the same Kazhdan-Lusztig polynomial'' for a fixed $k$ using a finite computation (see e.g. \cite{5or6}).
We will be especially interested in certain configurations of edges introduced in \cite{Blundell2023}. First we define a useful family of directed graphs. 
%\begin{center}
%\begin{tikzpicture}
%	\draw[-stealth] (0,0) -- (1,1) (1,1) -- (0,2);
%	\draw[-stealth] (0,0) -- (-1,1)  (-1,1) -- (0,2);
%\end{tikzpicture}.
%\end{center}
The \emph{$k$-hypercube} is the Hasse diagram of the Boolean lattice with $k$ atoms, equivalently the $1$-skeleton of an $k$-dimensional hypercube. The $2$-hypercube is also called a \emph{diamond}.

\begin{figure}[H]
\[
\begin{tikzcd}[arrows={start anchor=center, end anchor=center,-,rmarrow=>}]
	& \phantom{a} & \\
	\ar[ur]& &\ar[ul] \\
	& \ar[ul]\ar[ur] &
\end{tikzcd}
\qquad
\begin{tikzcd}[arrows={start anchor=center, end anchor=center,-,rmarrow=>}]
	& \phantom{a} & \\
	\ar[ur]& \ar[u] &\ar[ul] \\
	\ar[u]\ar[ur]&\ar[ul]\ar[ur] &\ar[ul]\ar[u] \\
	&\ar[ul]\ar[u]\ar[ur] & 
\end{tikzcd}
\]
\vspace{-1em}
\caption{The $2$-hypercube and the $3$-hypercube.}\label{fig:hyps}
\end{figure}

Fix $x\in [u,v]$. Let $Y$ be a collection of $k$ elements of $\Omega_{u,v}$ which each have incoming edges from $x$. We say that $Y$ \emph{spans a hypercube} at $x$ if $Y$ is the set of atoms of a subgraph of $\Omega_{u,v}$ which is isomorphic to the $k$-hypercube. If $Y$ spans a unique hypercube at $x$, then we define $\theta_x(Y)$ to be the top vertex of the hypercube spanned by $Y$.

\vspace{.5em}
\begin{definition}\label{def:hyp}
	Let $[u,v]$ be a Bruhat interval. Let $z\in [u,v]$. We say that $I=[u,z]$ is a \textbf{hypercube decomposition} (following \cite{Blundell2023}) if these two properties hold:
	\begin{itemize}
		\item[(D)] If \(~\begin{tikzcd}[cramped,sep=small] & w & \\ y\ar[ur]& &y'\ar[ul] \\ &x\ar[ul]\ar[ur]& \end{tikzcd}~\) is a subgraph of $\Omega_{u,v}$ and $x,y,y'$ are all in $I$, then $w$ is in $I$.
		
		\item[(H)] If $x\in I$ and $Y = \{ y_1, y_2, \ldots, y_k  \} \subseteq [u,v]$ is such that $x\to y_i$ and $y_i\not\in I$ for all $i$, and the $\{y_i\}$ are pairwise incomparable, then $Y$ spans a unique hypercube.
	\end{itemize}
\end{definition}
\vspace{.5em}

For $x$ in a hypercube decomposition $I$, define the set $Y_x\coloneqq \{y\in [u,v]\setminus I \mid x\to y\}$. 
%If $Y$ is a subset of $Y_x$, then we write $Y^{\mathrm{max}}$ for the collection of maximal elements of the induced poset on $Y$. It follows that $Y^{\mathrm{max}}$ is an antichain. The \emph{hypercube map} at $x\in I$ is the function from subsets of $Y_x$ to $[u,v]$ which sends $Y\subseteq Y_x$ to 
%\[\theta_x(Y) \coloneqq \theta_x(Y^{\mathrm{max}}),\] 
%the top vertex of the hypercube spanned by the collection of maximal elements in $Y$. 
For any antichain $Y\subseteq Y_x$, property (H) implies that $\theta_x(Y)$ is well-defined. The function $\theta_x$ is called the \emph{hypercube map}; in \cite{Blundell2023} its domain is extended to all subsets of $Y_x$. Note that $\theta_x(\varnothing)=x$. To simplify exposition, in the remainder of this abstract we will assume that if $Y,Y'\subseteq Y_x$ are distinct antichains, then $\theta_x(Y)\neq\theta_x(Y')$. We also define for each $x\in I$ a subset $Y_x^\circ\subseteq Y_x$ which is the unique antichain satisfying $\theta_x(Y_x^\circ)=v$ if it exists. If such a subset does not exist, we set $Y_x^\circ\coloneqq \varnothing$.
 
%note one motivation to define it this way is that I don't know that $\theta(Y_x^max)$ is the largest element in the image of $\theta_x$ in general 
We can now define the polynomial
\begin{equation*} \tH_{u,z,v}(q) \coloneqq \sum_{\substack{x\in I\\ \theta_x(Y_x^\circ)=v}} q^{|Y_x^{\circ}|}\tR_{u,x}(q), \end{equation*}
where the sum is taken over $x\in [u,z]$ such that there is an antichain contained in $Y_x$ which spans a hypercube with top $v$. We are almost ready to state our theorem computing $\tR_{e,v}$. We first need a special condition on a hypercube decomposition.

\vspace{.5em}
\begin{definition}\label{def:stronghyp}
	We say that the hypercube decomposition $I$ of $[u,v]$ is \emph{strong} if it satisfies the following condition: 
	
	\begin{itemize}
				
		\item[(U)] For all $x\in I$ and antichains $Y,Y'\subseteq Y_x$ with $|Y|=|Y'|=|Y\cap Y'|+1$, if 
		\[~\begin{tikzcd}[cramped,sep=small] & w & \\ \theta_x(Y)\ar[ur]& &\theta_x(Y')\ar[ul] \\ &\theta_x(Y\cap Y')\ar[ul]\ar[ur]& \end{tikzcd}~\] 
		is a subgraph of $\Omega_{u,v}$, then $Y\cup Y'$ is an antichain and $w=\theta_x(Y\cup Y')$.
		
		%\item[(A)] If $x\in I$ and  $Y,Y'\subseteq Y_x$ are two distinct antichains, then $\theta_x(Y)\neq \theta_x(Y')$.
			
		%\item[(A)] If $x\in I$ and $y,y'\not\in I$ and \(~\begin{tikzcd}[cramped,sep=small] & w & \\ y\ar[ur]& &y'\ar[ul] \\ &x\ar[ul]\ar[ur]& \end{tikzcd}~\) is a subgraph of $\Omega_{u,v}$, then $y$ and $y'$ are incomparable. Equivalently, $w=\theta_x(\{y,y'\})$.
	\end{itemize}
\end{definition}
\vspace{.5em}


\begin{theorem}\label{thm:formula}
	Let $W=S_n$ and $z\leq v$ any two elements such that $I=[e,z]$ gives a strong hypercube decomposition of $[e,v]$. Then 
	\[ \tR_{e,v} = \tH_{e,z,v}. \]
	%where the sum is over $x\in I$ and edge sets $E=\{x\to y_1, x\to y_2, \ldots, x\to y_k\}$ such that $\{y_1,\ldots, y_k\} \subseteq [e,v]\setminus I$ is an antichain and $\theta_x(E)=v$.
\end{theorem}
\begin{proof}[Proof sketch]
	The left-hand side is the generating function which counts increasing paths $\gamma$ from $e$ to $v$, weighted by $q^{\ell(\gamma)}$, where $\ell(\gamma)$ is the number of edges in $\gamma$. The right hand side is the generating function which counts pairs $(x,\gamma')$, where $x$ is in $I$ and  $\gamma'$ is an increasing path from $e$ to $x$. Such a pair is weighted by $q^{\ell(\gamma') + |Y_x^{\circ}|}$. To prove the inequality, it will suffice to give a bijective, weight-preserving map from the objects counted by the left-hand side to the objects counted by the right-hand side.
	
	Given an increasing path $\gamma$ from $e$ to $v$, we define $x$ to be the last vertex of $\gamma$ which is in $I$. The path $\gamma'$ is defined as the initial section of $\gamma$ which ends at $x$. We would like to show that $\gamma$ is the unique completion of $\gamma'$ to an increasing path from $e$ to $v$, and furthermore that $\ell(\gamma) = \ell(\gamma')+|Y_x^\circ|$. This reduces to two facts: that every hypercube subgraph of $\Omega_W$ contains a unique increasing path, and that once $\gamma$ leaves $I$, every remaining vertex used by $\gamma$ is in the image of $\theta_x$. The proof of the latter fact uses (U), but it also requires that we define increasing paths using a reflection order with special properties. That such a reflection order exists is a consequence of property (D) and uses the fact that $[e,v]$ is a lower Bruhat interval. 
	
	We would also like to know that the map $\gamma\mapsto (x,\gamma')$ is surjective. This amounts to checking, for each $x\in J$ with $\theta_x(Y_x^\circ)=v$, that the unique increasing path in the hypercube spanned by $Y_x^\circ$ may be concatenated to the end of any increasing path from $e$ to $x$ to produce a path that is still increasing. Again this relies on a specially constructed reflection order.  See \cite{Barkley2023} for more details. %Specifically, Theorem 3.9 and Corollary 4.6 (at the time of writing_)
\end{proof} 

If the only strong hypercube decomposition is the trivial one where $z=v$, then this formula gives us no information. Fortunately, in the symmetric group, there are always nontrivial strong hypercube decompositions. If $v = [v(1),v(2),\ldots,v(n)]$ is the one-line notation for $v$, and $i$ is the minimal index such that $v(i)\neq i$, then the \emph{standard hypercube decomposition} of $[e,v]$ is $I = \{x \in [e,v] \mid x(i) = i  \}$. One can similarly define the standard hypercube decomposition in any nontrivial interval of $S_n$. 

The following is a strengthening of \cite[Theorem 5.1]{Blundell2023}, and its proof can be extracted from the explicit description of the hypercube map in Section 5 of that paper.

\begin{theorem}\label{thm:existence}
	For every $u<v$ in $S_n$, the standard hypercube decomposition of $[u,v]$ is strong.
\end{theorem}

Finally we have the following result applying to non-lower intervals. Remarkably, Brenti proved essentially the same result in \cite[Corollary 3.9]{Brenti1997}, long before the invention of hypercube decompositions. Our proof is quite different from Brenti's, and proceeds in the same way as that of \Cref{thm:formula}. 
% We discovered after submission that Brenti has a direct proof of this result in "Combinatorial properties of R-polynomials". (His result was not known to the authors when this abstract was first written!)

\begin{theorem}\label{thm:stdeqn}
	For every $u<v$ in $S_n$, the standard hypercube decomposition $I=[u,z]$ of $[u,v]$ satisfies
	\[ \tR_{u,v}(q) = \tH_{u,z,v}(q). \]
\end{theorem}

\vspace{1em}

\Cref{thm:stdeqn}, when combined with our \hyperlink{conj}{Conjecture}, implies that 
\[ \tR_{u,v} = \min_{\substack{u\leq z < v\\ [u,z]=\text{strong hyp. dec.}}} \tH_{u,z,v}. \]
Here the comparison of polynomials is taken coefficient-wise. If the \hyperlink{conj}{Conjecture} is true, then this gives a recursion for $\tR_{u,v}$ depending only on the unlabeled graph structure for $\Omega_{u,v}$, hence proving the combinatorial invariance conjecture for $S_n$.

%\begin{remark}
%	We note that \cite{Blundell2023} has an example of an interval in the group $H_3$ with no hypercube decomposition. It may be possible to replace hypercubes with a more general family of graphs.
%\end{remark}

%\section{Proof of \Cref{thm:formula}}\label{sec:proofs}
%
%Fix a Coxeter group $W$ and elements $u,z,v\in W$ such that $I=[u,z]$ gives a strong hypercube decomposition of $[u,v]$. Let $S$ denote the set of simple generators of $W$. The main result of the section is the following, which directly implies \Cref{thm:stdeqn}, and together with \Cref{lem:lowerparabolic} implies \Cref{thm:formula}.
%
%\begin{lemma}
%	Pick a subset $I\subseteq S$. If $I = W_I \cap [u,v]$, then 
%	\[ \tR_{u,v}(q) = \tH_{u,z,v}(q). \]
%\end{lemma}


%% 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}
