\documentclass[finalversion]{FPSAC2024} \articlenumber{17} \usepackage{tikz,enumitem,rotating,latexsym,bm,stmaryrd} \usetikzlibrary{positioning,intersections} \usepackage{amsmath,amsthm,amsfonts,amssymb,mathrsfs,pb-diagram,hyperref} \usepackage{caption,cases} \usepackage{lipsum,wasysym,genyoungtabtikz} \usepackage{mathtools,scalefnt} \usetikzlibrary{arrows,calc,through,backgrounds,matrix,decorations.pathmorphing} \usetikzlibrary{arrows,calc,through,backgrounds,matrix,decorations.pathmorphing,calligraphy} \colorlet{darkgreen}{green!50!black} \DeclarePairedDelimiter\parentheses{\lparen}{\rparen} \usepackage[vcentermath,enableskew]{youngtab} \newcommand{\cpi}{{{{\color{orange}\pi}}}} \newcommand{\csigma}{{{{\color{magenta}\sigma}}}} \newcommand{\ctau}{{{{\color{cyan}\tau}}}} \newcommand{\crho}{{{{\color{darkgreen}\rho}}}} \newcommand{\csigmaw}{{{{\color{magenta}\sigma}}}} \newcommand{\ctauw}{{{{\color{cyan}\tau}}}} \tikzset{snake it/.style={decorate, decoration=snake}} \tikzset{zigzag/.style={decorate, decoration=zigzag}} \tikzset{/.style={gray,double=gray!15!white, distance=1pt}} \newcommand{\thalf}{\tfrac{1}{2}} \renewcommand{\leq}{\leqslant} \renewcommand{\trianglerighteq}{\trianglerighteqslant} \newcommand{\Lad}{{\rm Lad}} \renewcommand{\trianglelefteq}{\trianglelefteqslant} \newcommand{\w}{{\underline w}} \newcommand{\y}{{\underline y}} \newcommand{\x}{{\SSTT_\la}} \newcommand{\la}{\lambda} \newcommand{\Path}{{\rm Path}} \usepackage{cleveref} \captionsetup{width=0.8\linewidth} \newtheorem{thm}{Theorem}[section] \newtheorem{cor}[thm]{Corollary} \newtheorem{conj}[thm]{Conjecture} \newtheorem{lem}[thm]{Lemma} \newtheorem{prop}[thm]{Proposition} \newtheorem*{prop*}{Proposition} \newtheorem*{thm*}{Main Theorem} \newtheorem*{Hook}{Hook length formula} \newtheorem*{cor*}{Corollary} \newtheorem*{conj*}{Conjecture} \newtheorem*{move1}{Move 1} \newtheorem*{move1'}{Move $\mathbf{1^*}$} \newtheorem*{move2}{Move 2} \newtheorem*{clcopieri}{Classical co-Pieri rule} \newtheorem*{spmainthm}{Special case of Main Theorem} \theoremstyle{remark} \newtheorem*{prob}{Problem} \newtheorem*{alg}{Algorithm} \newtheorem{rmk}[thm]{Remark} \newtheorem*{notation}{Notation} \newtheorem{rem}[thm]{Remark} \newtheorem*{ques}{Question} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \newtheorem{eg}[thm]{Example} \newtheorem{egnum}[thm]{Example} \newtheorem{examples}[thm]{Examples} \crefname{defn}{Definition}{Definitions} \crefname{thm}{Theorem}{Theorems} \crefname{prop}{Proposition}{Propositions} \crefname{lem}{Lemma}{Lemmas} \crefname{cor}{Corollary}{Corollaries} \crefname{conj}{Conjecture}{Conjectures} \crefname{section}{Section}{Sections} \crefname{subsection}{Subsection}{Subsections} \crefname{eg}{Example}{Examples} \crefname{figure}{Figure}{Figures} \crefname{rem}{Remark}{Remarks} \crefname{rmk}{Remark}{Remarks} \crefname{equation}{equation}{equation} \Crefname{defn}{Definition}{Definitions} \Crefname{thm}{Theorem}{Theorems} \Crefname{prop}{Proposition}{Propositions} \Crefname{lem}{Lemma}{Lemmas} \Crefname{cor}{Corollary}{Corollaries} \Crefname{conj}{Conjecture}{Conjectures} \Crefname{section}{Section}{Sections} \Crefname{subsection}{Subsection}{Subsections} \Crefname{eg}{Example}{Examples} \Crefname{figure}{Figure}{Figures} \Crefname{rem}{Remark}{Remarks} \Crefname{rmk}{Remark}{Remarks} \numberwithin{equation}{section} \newcommand{\flux}{\mathsf{t}} %standard index \newcommand{\stw}{\mathsf{w}} %standard index \newcommand{\sts}{\mathsf{s}} %standard index \newcommand{\stt}{\mathsf{t}} %standard index \newcommand{\stu}{\mathsf{u}} %standard index \newcommand{\stv}{\mathsf{v}} %standard index \newcommand{\stq}{\mathsf{u}} %standard index \newcommand{\str}{\mathsf{v}} %standard index \newcommand{\SSTS}{\mathsf{S}} %semistandard index \newcommand{\SSTT}{\mathsf{T}} %semistandard index \newcommand{\SSTU}{\mathsf{U}} \newcommand{\SSTV}{\mathsf{V}} %semistandard index \newcommand{\xelt}{u} \renewcommand{\Vec}{V} %semistandard index \newcommand{\thepartitionmu}{\mu} \newcommand{\thepartitionnu}{\nu} \newcommand{\thepartitionlambda}{\lambda} \newcommand{\bil}[2]{\langle #1, #2 \rangle} \newcommand{\Ext}{\operatorname{Ext}} \newcommand{\down}{m{\downarrow}} \newcommand{\up}{m{\uparrow}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\Head}{\operatorname{head}} \newcommand{\rad}{\operatorname{rad}} \newcommand{\Soc}{\operatorname{soc}} \newcommand{\hd}{\operatorname{hd}} \newcommand{\minl}{\operatorname{min}} \newcommand{\End}{\operatorname{End}} \newcommand{\ind}{\operatorname{ind}} \newcommand{\id}{\operatorname{id}} \newcommand{\Sym}{\operatorname{Sym}} \newcommand{\first}{\operatorname{first}} \newcommand{\last}{\operatorname{last}} \newcommand{\res}{\operatorname{res}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\ct}{\operatorname{ct}} \newcommand{\suchthat}{\;\ifnum\currentgrouptype=16 \middle\fi|\;} \newcommand{\ZZ}{{\mathbb Z}} \newcommand{\NN}{{{\mathbb N} }} \newcommand{\remb}{\operatorname{rem}} \newcommand{\add}{\operatorname{add}} \renewcommand{\le}{\leqslant} \renewcommand{\ge}{\geqslant} \newcommand{\GL}{\mathrm{GL}} \newcommand{\G}{\mathrm{G}} \newcommand{\F}{\mathrm{F}} \newcommand{\Id}{\mathrm{Id}} \newcommand{\Specht}{\mathbf{ \textbf \rm S}} \newcommand{\g}{\mathfrak{g}} \newcommand{\T}{\mathrm{T}} \renewcommand{\P}{\mathrm{P}} \newcommand{\CC}{\mathbb{Q}} \DeclareMathOperator{\mn}{min} \newcommand{\U}{\mathfrak{U}} \newcommand{\M}{\mathrm{M}} \newcommand{\N}{\mathrm{N}} \newcommand{\St}{\mathrm{St}} \newcommand{\ch}{\operatorname{ch}} \newcommand{\im}{\operatorname{im}} \newcommand{\Stab}{\operatorname{Stab}} \newcommand{\pr}{\operatorname{pr}} \newcommand{\minmax}{\operatorname{minmax}} \newcommand{\maxl}{\operatorname{max}} \newcommand{\divided}[2]{{#1}^{(#2)}} \newcommand{\C}{\mathbb{C}} \newcommand{\soc}{\operatorname{soc}} \newcommand{\hatQ}{\widehat{\mathrm{Q}}} \newcommand{\eleven}{11} \newcommand\mptn {\mathscr{P}_{m,n}} \renewcommand{\labelitemi}{$\circ $} \hyphenation{tab-le-aux } \usetikzlibrary{decorations.pathreplacing} \DeclareMathOperator{\Au}{Aut} \DeclareMathOperator{\Ob}{Ob} \DeclareMathOperator{\autn}{Aut} \DeclareMathOperator{\A}{A} \DeclareMathOperator{\Op}{O} \DeclareMathOperator{\Z}{\mathbb{Z}} \DeclareMathOperator{\sn}{\,sn\,} \DeclareMathOperator{\Tr}{tr} \usepackage{amsmath} \mathchardef\mhyphen="2D \DeclareMathOperator{\Block}{part} \DeclareMathOperator{\Span}{span} \DeclareMathOperator{\row}{row} \DeclareMathOperator{\col}{col} \DeclareMathOperator{\node}{node} \DeclareMathOperator{\shape}{shape} \DeclareMathOperator{\spn}{span} \DeclareMathOperator{\perm}{perm} \newcommand{\dten}{10} \newcommand{\half}{\frac{1}{2}} \newcommand{\dhalf}{\frac{\delta}{2}} \newcommand{\iph}[2]{{{#1}+\frac{#2}{2}}} \newcommand{\imh}[2]{{{#1}-\frac{#2}{2}}} \newcommand{\Std}{\mathrm{Std}} \newcommand{\DRStd}{\mathrm{DR\mhyphen Std}} \newcommand{\DRmStd}{\mathrm{DR\mhyphen Std}} \newcommand{\Shape}{\mathrm{Shape}} %\newcommand{\Path}{\mathrm{SStd}} \newcommand{\Latt}{\mathrm{Latt}} \newcommand\semistd[2]{\mathcal{T}^\Path_{#1}(#2)} \newcommand\std[1]{\mathcal{T}^\Path(#1)} \let\originalleft\left \let\originalright\right \def\left#1{\mathopen{}\originalleft#1} \def\right#1{\originalright#1\mathclose{}} \renewcommand{\ge}{\geqslant} \renewcommand{\baselinestretch}{1.1} \renewcommand{\ge}{\geqslant} \renewcommand{\geq}{\geqslant} \renewcommand{\le}{\leqslant} \renewcommand{\leq}{\leqslant} \renewcommand{\succeq}{\succcurlyeq} \renewcommand{\preceq}{\preccurlyeq} \newcommand{\cell}[3]{\Delta_{{#1}_{#2}}^{#3}} \newcommand{\el}{l} \newcommand\generator[2]{\delta_{#1}^{#2}} \newcommand\inv{^{-1}} \newcommand{\dd}[3]{d_{{#1} \to {#2}}^{\power {#3}}} \newcommand{\uu}[3]{u_{{#1} \to {#2}}^{\power {#3}}} \newcommand{\ddbar}[3]{\bar d_{{#1} \to {#2}}^{\power {#3}}} \newcommand{\uubar}[3]{\bar u_{{#1} \to {#2}}^{\power {#3}}} \def\mf{\mathfrak} %\def\la{\overline\thepartitionmu } \def\mft{\mathfrak t} \def\mfs{\mathfrak s} \def\mfu{\mathfrak u} \def\mfv{\mathfrak v} \newcommand\boldq{\bm q} \def\ignore#1{\relax} \def\power #1{^{(#1)}} \def\leftbrace{\big\{} \def\rightbrace{\big\}} \def\ignore#1{\relax} \def\p #1{ \bm {#1}} \def\pbar #1{\overline{\p {#1}}} \newcommand{\ik}{k} \newcommand{\jk}{{j_{s+1}}} \usepackage[backend=bibtex]{biblatex} \addbibresource{master.bib} \usepackage{scalefnt} \title{Dyck combinatorics in $p$-Kazhdan--Lusztig theory } %\author{C. Bowman} \author{Chris Bowman\thanks{\href{mailto:chris.bowman-scargill@york.ac.uk}{chris.bowman-scargill@york.ac.uk}}\addressmark{1}, Maud De Visscher\addressmark{2}, Amit Hazi\addressmark{3}, \and Catharina Stroppel\addressmark{4}} % \address{ Mathematical Institute, Endenicher Allee 60, 53115 Bonn} % \email{Stroppel@math.uni-bonn.de} \address{\addressmark{1}Department of Mathematics, University of York \\ \addressmark{2}Department of Mathematics, City, University of London \\ \addressmark{3}School of Mathematics, University of Leeds \\ \addressmark{4}Mathematical Institute of the University of Bonn} \abstract{We survey some recent advances in combinatorial modular representation theory in type $A$ through the lens of $p$-Kazhdan--Lusztig theory.} \begin{document} \maketitle \section{Introduction} The diagrammatic Hecke category has provided the intuition and tools necessary to cut through the most famous conjectures of Lie theory: the Lusztig and Kazhdan--Lusztig positivity conjectures. These conjectures place the Kazhdan--Lusztig polynomials (associated to parabolic Coxeter systems) centre-stage in the (modular) representation theory of Lie theoretic objects. Kazhdan--Lusztig polynomials encode a great deal of character-theoretic and indeed cohomological information about cell modules. We further know that Kazhdan--Lusztig polynomials often carry information about the radical layers of indecomposable projective and cell modules. Given the almost ridiculous level of detail these polynomials encode, it is natural to ask {\em``what are the limits to what $p$-Kazhdan--Lusztig combinatorics can tell us about the structure of the Hecke category?"} %The starting point of this paper is to delve deep into the Dyck/Temperley--Lieb combinatorics for $p$-Kazhdan--Lusztig polynomials, which was initiated in % \cite{MR2918294,MR4323501,compan}. There is a wealth of extra, richer combinatorial information which can be encoded into the Dyck tilings underlying these % $p$-Kazhdan--Lusztig % polynomials. % Instead of looking only at the sets of Dyck tilings % (which enumerate the $p$-Kazhdan--Lusztig % polynomials) we look at the relationships for passing % between % these Dyck tilings. % In fact, this ``meta-Kazhdan--Lusztig combinatorics" % is sufficiently rich as to completely determine the full structure of our Hecke categories: % % \begin{thmB} %% Let $\Bbbk$ be a field. The ${\rm Ext}$-quiver of %The $\Bbbk$-algebra $ \mathcal{H}_{m,n} $ admits a quadratic presentation as the path algebra of the ``Dyck quiver" $\mathscr{D}_{m,n}$ of \cref{quiverdefn} % modulo ``Dyck-combinatorial relations" \eqref{rel1} to \eqref{adjacent}. %If $\Bbbk$ is a field, then the ${\rm Ext}$-quiver of %$\mathcal{H}_{m,n} %$ is isomorphic to $\mathscr{D}_{m,n}$ %and this gives a presentation of the algebra by quiver and relations. % \end{thmB} % % In a nutshell, the power of Theorem B is that it allows us to understand not only the %{\em graded composition series} of standard and projective modules % (the purview of classical Kazhdan--Lusztig combinatorics) but the {\em explicit % extensions interrelating these composition factors} % (in terms of meta-Kazhdan--Lusztig combinatorics). % In essence, Theorem B provides complete information about the structure of the anti-spherical Hecke categories %of $(S_{m+n},S_m \times S_n)$ for $m,n\in\NN$. % We reap some of the fruits of Theorem B by providing an incredibly elementary description of the full submodule lattices of Verma modules: %The truth of Lusztig's conjecture, which concerns the modular setting, was never questioned and the search for a proof was the backbone of 20th century Lie theory. %In 2012, Williamson found startling counterexamples to Lusztig's conjecture within the diagrammatic Hecke category and upended the status quo of modular representation theory. %More precisely, Williamson showed that the characteristic of the field must be exponentially enormous in order for the Kazhdan--Lusztig polynomials to control the representation theory of reductive groups. %%However, this was only the beginning of the story. %The diagrammatic Hecke category provides the setting in which we can finally understand this chasm between representation theory over fields of positive characteristic and characteristic $0$. %This problem will undoubtedly be the core of Lie theory in the 21st century. % % % % % % % % % %The diagrammatic Hecke category was introduced as % an interface between Kazhdan--Lusztig combinatorics and (modular) Lie theory. This diagrammatic setting provided the %intuition and tools necessary to resolve the Lusztig and Kazhdan--Lusztig positivity conjectures. The family of ordinary Kazhdan--Lusztig polynomials which are combinatorially best understood are those for maximal parabolics of finite symmetric groups $\mathfrak{S}_m \times \mathfrak{S}_n \leq \mathfrak{S}_{m+n}$. These polynomials can be calculated in terms of the combinatorics of Dyck tilings \cite{MR646823}. The starting point of this project was to extend this to the modular case by proving that the $p$-Kazhdan--Lusztig polynomials of $\mathfrak{S}_m \times \mathfrak{S}_n \leq \mathfrak{S}_{m+n}$ are entirely independent of $p\geq0$. % to delve deeper into this Dyck combinatorics to obtain more structural. W We also find that there is a wealth of extra, richer combinatorial information which can be encoded into the Dyck tilings. Instead of looking only at the sets of Dyck tilings (which enumerate these Kazhdan--Lusztig polynomials) we look at the relationships for passing between these Dyck tilings. In fact, this ``meta-Kazhdan--Lusztig combinatorics" is sufficiently rich as to completely determine the full structure of our Hecke categories. In this extended abstract, we discuss how this allows us to provide a complete combinatorial description of the submodule lattices of the cell modules for these categories. % These polynomials admit inexplicably simple % combinatorial formulae in terms of Dyck paths \cite{MR646823}. We also proved in \cite{compan2} that the Hecke categories of $\mathfrak{S}_m \times \mathfrak{S}_n \leq \mathfrak{S}_{m+n}$ control the structure of parabolic Verma modules for Lie algebras \cite{MR2781018,MR888703,MR646823}; the representation category of the general linear supergroups \cite{MR1937204}; arc algebras from categorified knot theory \cite{MR2881300}; walled Brauer algebras \cite{MR2813567}; % and categories $\mathcal{O}$ for Grassmannians \cite{MR646823}. and the combinatorics of attracting cells for torus fixed points in Springer fibers \cite{MR2914857}. This makes the cell modules of these categories some of the most well-understood representations in all of non-semisimple Lie theory. % and categories $\mathcal{O}$ for Grassmannians \cite{MR646823}. \section{Kazhdan--Lusztig polynomials}\label{reduced-defn} Let $(W, S_W)$ be a Coxeter system: $W$ is the group generated by the finite set $S_W$ subject to the relations $(\csigma\ctau)^{m_{\csigma\ctau}} = 1$ for $\csigma,\ctau\in S_W$, $ {m_{\csigma\ctau}}\in \NN\cup\{\infty\}$ satisfying ${m_{\csigma\ctau}}= {m_{\ctau\csigma}}$, and ${m_{\csigma\ctau}}=1$ if and only if $\csigma= \ctau$. Let $\ell : W \to \mathbb{N}$ be the corresponding length function. Consider $S_P \subseteq S_W$ a subset and $(P, S_P)$ its corresponding Coxeter system. We say that $P$ is the parabolic subgroup corresponding to $S_P\subseteq S_W$. Let $^ PW \subseteq W$ denote a set of minimal coset representatives in $P\backslash W$. For $\w=\sigma_1\sigma_2\cdots \sigma_\ell$ an expression, we define a subword to be a sequence $\underline{t}=(t_1,t_2,\dots ,t_\ell)\in\{0,1\}^\ell$ and set $\w^{\underline{t}} :=\sigma_1^{t_1}\sigma_2^{t_2}\cdots \sigma_\ell^{t_\ell}$. % and we emphasise that $s_i^0=1 \in W$. We let $\leq $ denote the strong Bruhat order on $^PW$: namely $y\leq w$ if for some reduced expression $\w$ there exists a subword ${\underline{t}}$ and a reduced expression $\y$ such that $\w^{\underline{t}}=\y$. We denote the Hasse diagram of this poset by $\mathcal{G}_{(W,P)}$ {and we refer to it as the {\em Bruhat graph} of the pair $(W,P)$.} Explicitly, the vertices of $\mathcal{G}_{(W,P)}$ are labelled by the elements of $^PW$ and for $\lambda \in {^PW}$ we have a directed edge $\lambda \rightarrow \lambda s_i$ if $\lambda < \lambda s_i \in {^PW}$ for some $s_i\in S_W$. We denote by $\varnothing$ (for the empty word in the generators) the minimal coset representative for the identity coset $P$. \begin{figure}[ht!] $$ \begin{tikzpicture} [yscale=0.51,xscale=-0.51] \draw[magenta, line width=3] (2,0.5)--(2,3) coordinate (hi); \draw[cyan, line width=3] (hi)--(6,5.5) coordinate (hi2); \draw[darkgreen, line width=3] (hi)--(-2,5.5) coordinate (hi3); \draw[cyan, line width=3] (hi3)--(2,8) coordinate (hi4); \draw[darkgreen, line width=3] (hi2)--(2,8) coordinate (hi4); \draw[magenta, line width=3] (hi4)--++(90:2.5) coordinate (hi7); \path (hi7) --++(180:2)coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3 \color{cyan}s_1 \color{magenta}s_2 $}; \path (0,0) coordinate (origin) ; \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {$\varnothing$}; \path (0,2.5) coordinate (origin) ; \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2 $}; \path (-4,5) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3 $}; \path (4,5) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{cyan}s_1 $}; \path (0,7.5) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3 \color{cyan}s_1 $}; \draw[very thick]( -7+1.8,3-1)--(-4+1.8,3-1); \draw[very thick, fill=darkgreen] ( -7+1.8,3-1) coordinate circle (7pt); \draw[very thick, fill=magenta] ( -5.5+1.8,3-1) coordinate circle (7pt); \draw[very thick, fill=cyan] ( -4+1.8,3-1) coordinate circle (7pt); %\draw[very thick, rounded corners] (-7.5+1.8,2.5-1) rectangle (-7.2+1.8,3.5-1); % %\draw[very thick, rounded corners] (-4.8+1.8,2.5-1) rectangle (-3.2+1.8,3.5-1); \draw[very thick, rounded corners] (-6.5+1.8,2.5-1) rectangle (-7.5+1.8,3.5-1); \draw[very thick, rounded corners] (-4.5+1.8,2.5-1) rectangle (-3.5+1.8,3.5-1); \end{tikzpicture} \quad \begin{tikzpicture} [yscale=0.51,xscale=-0.51] \draw[magenta, line width=3] (2,0.5)--(2,3) coordinate (hi); \draw[cyan, line width=3] (hi)--(6,5.5) coordinate (hi2); \draw[darkgreen, line width=3] (hi)--(-2,5.5) coordinate (hi3); \draw[cyan, line width=3] (hi3)--(2,8) coordinate (hi4); \draw[darkgreen, line width=3] (hi2)--(2,8) coordinate (hi4); \draw[orange, line width=3] (hi3)--(-6,8) coordinate (hi5); \draw[cyan, line width=3] (hi5)--(-2,10.5) coordinate (hi6); \draw[orange, line width=3] (hi4)--(-2,10.5) coordinate (hi6); \draw[magenta, line width=3] (hi4)--(6,10.5) coordinate (hi7); \draw[magenta, line width=3] (hi6)--(2,13) coordinate (hi8); \draw[orange, line width=3] (hi7)--(2,13) coordinate (hi8); \draw[darkgreen, line width=3] (hi8)--(2,15) ; \path (0,0) coordinate (origin) ; \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {$\varnothing$}; \path (0,2.5) coordinate (origin) ; \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2 $}; \path (-4,5) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3 $}; \path (4,5) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{cyan}s_1 $}; \path (0,7.5) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3 \color{cyan}s_1 $}; \path (-8,7.5) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3 \color{orange}s_4 $}; \path (-4,10) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3\color{orange}s_4 \color{cyan}s_1 $}; \path (4,10) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3 \color{cyan}s_1 \color{magenta}s_2 $}; \path (0,12.5) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3\color{orange}s_4 \color{cyan}s_1 \color{magenta}s_2$}; \path (0,15) coordinate (origin); \draw[fill=white,rounded corners](origin) rectangle ++(4,1) node [midway] {\scalefont{0.9}$\color{magenta}s_2\color{darkgreen}s_3\color{orange}s_4 \color{cyan}s_1 \color{magenta}s_2\color{darkgreen}s_3$}; % %\draw[very thick]( -10+1.8,3-1)--(-4+1.8,3-1); %\draw[very thick, fill=orange] ( -10+1.8,3-1) coordinate circle (7pt); % %\draw[very thick, fill=darkgreen] ( -8+1.8,3-1) coordinate circle (7pt); % %\draw[very thick, fill=magenta] ( -6+1.8,3-1) coordinate circle (7pt); % %\draw[very thick, fill=cyan] ( -4+1.8,3-1) coordinate circle (7pt); % %\draw[very thick, rounded corners] (-10.8+1.8,2.5-1) rectangle (-7.2+1.8,3.5-1); % %\draw[very thick, rounded corners] (-4.8+1.8,2.5-1) rectangle (-3.2+1.8,3.5-1); \draw[very thick]( -8.5+1.8,3-1)--(-4+1.8,3-1); \draw[very thick, fill=darkgreen] ( -7+1.8,3-1) coordinate circle (7pt); \draw[very thick, fill=magenta] ( -5.5+1.8,3-1) coordinate circle (7pt); \draw[very thick, fill=cyan] ( -4+1.8,3-1) coordinate circle (7pt); %\draw[very thick, rounded corners] (-7.5+1.8,2.5-1) rectangle (-7.2+1.8,3.5-1); % %\draw[very thick, rounded corners] (-4.8+1.8,2.5-1) rectangle (-3.2+1.8,3.5-1); \draw[very thick, fill=orange] ( -8.5+1.8,3-1) coordinate circle (7pt); \draw[very thick, rounded corners] (-6.5+1.8,2.5-1) rectangle (-9+1.8,3.5-1); \draw[very thick, rounded corners] (-4.5+1.8,2.5-1) rectangle (-3.5+1.8,3.5-1); \end{tikzpicture} $$ \caption{The graph $\mathcal{G}_{(W,P)}$ for $(W,P)=(\mathfrak{S}_4,\mathfrak{S}_2 \times \mathfrak{S}_2 )$ and $(\mathfrak{S}_5, \mathfrak{S}_2 \times \mathfrak{S}_3 )$ respectively. %(We haven't drawn the direction on the edges but all arrows are pointing upwards). } %$A_4 \setminus A_2 \times A_1$. } \label{Bruhatexample-KL} \end{figure} We define the {\em extended Bruhat graph} $\widehat{\mathcal{G}}_{(W,P)}$ to be the directed graph having the same set of vertices as $\mathcal{G}_{(W,P)}$ but replacing each edge in $\mathcal{G}_{(W,P)}$ between $\lambda$ and $\lambda s_i$ for $\lambda < \lambda s_i$ by four ``up" and ``down" directed edges \begin{align}\label{begin!} \lambda \xrightarrow{ \ i \ }\lambda s_i , \quad \lambda \xrightarrow{ \ i \ }\lambda , \quad \lambda s_i \xrightarrow{ \ i \ }\lambda \quad \lambda s_i \xrightarrow{ \ i \ }\lambda s_i, \end{align} which we denote $ {\sf U}_i^1$, ${\sf U}_i^0$, ${\sf D}_i^1$, ${\sf D}_i^0$ respectively. We assign a degree to each edge in $\widehat{\mathcal{G}}_{(W,P)}$ by setting \[{\rm deg}(\lambda \xrightarrow{ \ i \ } \lambda s_i) = {\rm deg}(\lambda s_i \xrightarrow{ \ i \ } \lambda) = 0 \qquad {\rm deg}(\lambda \xrightarrow{ \ i \ } \lambda) = \left\{ \begin{array}{ll} 1 & \mbox{if $\lambda s_i > \lambda$}\\ -1 & \mbox{if $\lambda s_i < \lambda$}\end{array}\right.\] %{\color{magenta} A walk on the usual Bruhat graph $\mathcal{G}_{(W,P)}$ can be thought of as a path in the extended Bruhat graph $\widehat{\mathcal{G}}_{(W,P)}$ . Given a path (or ``Bruhat stroll") on $\widehat{\mathcal{G}}_{(W,P)}$ \[\SSTT \, : \, \lambda_1 \xrightarrow{i_1} \lambda_2 \xrightarrow{i_2} \lambda_3 \xrightarrow{i_3} \ldots \xrightarrow{i_{k-1}} \lambda_k,\] we say that the {\em degree} ${\rm deg}(\SSTT)$ is the sum of the degrees of each edge in $\SSTT$. (The degree is also sometimes known as the ``Deodhar defect".) We also define the {\sf weight of $\SSTT$}, denoted by $w(\SSTT)$ to be the expression \[w(\SSTT) := {s_{i_1}s_{i_2}s_{i_3} \ldots s_{i_{k-1}}}.\] %We write $\SSTT_\la \otimes \csigma$ for the path of weight %$ {s_{i_1}s_{i_2}s_{i_3} \ldots s_{i_{k-1}}}\csigma$. Given $\la \in {^PW}$, we let $\Path (\la)$ denote the set of all paths from $\varnothing$ and ending at $\la$ in the extended Bruhat graph. \begin{defn} We say that a path $\SSTT\in \Path (\mu)$ is {\em reduced} if it is a path of shortest possible length from $\varnothing$ to $\mu$. \end{defn} Throughout the paper we will fix one reduced path, $\SSTT^\mu \in \Path (\mu)$, for each $\mu \in {^PW}$. For a fixed $\la$, we denote the set of all paths $\SSTT\in \Path(\la)$ with $w(\SSTT) = \SSTT^\mu$ by $\Path (\la,\SSTT^\mu)$. Examples are given in Figure 2. \begin{defn}\label{troll} Given $(W,P)$ a parabolic Coxeter system, we define the {\em matrix of light-leaves polynomials} \[ \Delta ^{(W,P)}:=( \Delta _{\la,\mu}(q))_{\la,\mu\in {{^P}W}} \qquad \qquad \Delta _{\la,\mu}(q)=\sum_{\SSTS \in {\rm Path}(\la,\SSTT^\mu)}\!\!\!\!\!\! q^{\deg(\SSTS)} \] which is a (square) lower uni-triangular matrix. This matrix can be factorised {\em uniquely} as a product of lower uni-triangular matrices \[N^{(W,P)}:=(n_{\la,\nu}(q))_{\la,\nu\in {{^P}W}} \qquad B^{(W,P)}:=(b_{\nu,\mu}(q))_{\nu,\mu\in {{^P}W}} \] such that $n_{\la,\nu}(q)\in q\ZZ[q]$ for $\la \neq \nu$ and $b_{\nu,\mu}(q)\in \ZZ[q+q^{-1}]$. The polynomials $n_{\la,\nu}(q)$ are the anti-spherical Kazhdan--Lusztig polynomials of $(W,P)$. %We set %$b_{\la,\la}(q)=1=n_{\la,\la}$. %For $\la\neq \mu$, we recursively define polynomials %\[ %b_{\la,\mu}(q)\in \ZZ [q+q^{-1}] \qquad %n_{\la,\mu}(q)\in q\ZZ [q] %\] % by induction on the Bruhat order $\leq$ as follows %\begin{equation}\label{kl-pol-d} %b_{\la,\mu}(q) +n_{\lambda,\mu}(q) = %\!\!\! \sum_{\SSTS \in {\rm Path}(\la,\SSTT^\mu)}\!\!\!\!\!\! q^{\deg(\SSTS)} - % \!\!\sum_{ %\begin{subarray}c %\la < \nu < \mu\end{subarray} %} \!\!\! n_{\lambda,\nu}(q) %b_{\nu,\mu}(q). %\end{equation} %The polynomials $n_{\la,\mu}(q)$ are called the {\em Kazhdan--Lusztig polynomials} associated to $\la,\mu$. \end{defn} \begin{figure} [ht!] $$\qquad\quad \begin{tikzpicture} [yscale=0.425,xscale=-0.425] \path[magenta, line width=3] (2,0.5)--(2,3) coordinate (hi); \path[cyan, line width=3] (hi)--(6,5.5) coordinate (hi2); \path[darkgreen, line width=3] (hi)--(-2,5.5) coordinate (hi3); \path[cyan, line width=3] (hi3)--(2,8) coordinate (hi4); \path[darkgreen, line width=3] (hi2)--(2,8) coordinate (hi4); \path[orange, line width=3] (hi3)--(-6,8) coordinate (hi5); \path[cyan, line width=3] (hi5)--(-2,10.5) coordinate (hi6); \path[orange, line width=3] (hi4)--(-2,10.5) coordinate (hi6); \path[magenta, line width=3] (hi4)--(6,10.5) coordinate (hi7); \path[magenta, line width=3] (hi6)--(2,13) coordinate (hi8); \path[orange, line width=3] (hi7)--(2,13) coordinate (hi8); \path[darkgreen, line width=3] (hi8)--(2,15.5) ; \path (0,0) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \draw[magenta, line width=3] (2,0.5)--(2,3) coordinate (hi); \path (0,0) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (0,2.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \draw[darkgreen, line width=3] (hi)--(-2,5.5) coordinate (hi3); \path (0,2.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (-4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \draw[cyan, line width=3] (hi)--(6,5.5) coordinate (hi2); \path (0,2.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \draw[cyan, line width=3] (hi3)--(2,8) coordinate (hi4); \draw[darkgreen, line width=3] (hi2)--(2,8) coordinate (hi4); \path (-4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (0,7.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \draw[orange, line width=3] (hi3)--(-6,8) coordinate (hi5); %\draw[cyan, line width=3] (hi5)--(-2,10.5) coordinate (hi6); \path (-4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (-8,7.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \draw[cyan, line width=3] (hi5)--(-2,10.5) coordinate (hi6); \draw[orange, line width=3] (hi4)--(-2,10.5) coordinate (hi6); \path (-8,7.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (0,7.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (-4,10) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; %\draw[orange, line width=3] (hi4)--(-2,10.5) coordinate (hi6); \draw[magenta, line width=3] (hi4)--(6,10.5) coordinate (hi7); \path (-8,7.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (0,7.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (4,10) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \draw[magenta, line width=3] (hi6)--(2,13) coordinate (hi8); \draw[orange, line width=3] (hi7)--(2,13) coordinate (hi8); %\draw[darkgreen, line width=3] (hi8)--(2,15) ; \path (-4,10) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (4,10) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (0,12.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \draw[darkgreen, line width=3] (hi8)--(2,15) ; \path (0,12.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (0,15) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; %\draw[line width=3 ] (2,0.5)--++(90:2.5) --(-2,5.5)--(-6,8)--(2,13)--++(90:2.5); \fill(hi)circle (8pt); \draw[darkgreen, line width=3] (hi8)--++(90:2.5) ; \path (hi8)--++(90:2.5) coordinate (ghfj) ; \fill (ghfj) circle (8pt); \draw[line width=3, , ] (2,0.5)--++(90:2.5)--(-2,5.5) --(-6,8) --(-2,10.5)--(2,13)--++(90:2.5) coordinate(hi); \draw[fill=black] (hi)circle (22pt); \foreach \i in {2,3,...,8} {\fill(hi\i)circle (8pt); } \draw (hi) node { \color{white}$ \alpha$}; \fill(2,0.5)circle (8pt); \fill(2,3)circle (8pt); \path (2,15.5) circle (22pt); \end{tikzpicture}\qquad \quad\begin{tikzpicture} [yscale=0.425,xscale=-0.425] \path[magenta, line width=3] (2,0.5)--(2,3) coordinate (hi); \path[cyan, line width=3] (hi)--(6,5.5) coordinate (hi2); \path[darkgreen, line width=3] (hi)--(-2,5.5) coordinate (hi3); \path[cyan, line width=3] (hi3)--(2,8) coordinate (hi4); \path[darkgreen, line width=3] (hi2)--(2,8) coordinate (hi4); \path[orange, line width=3] (hi3)--(-6,8) coordinate (hi5); \path[cyan, line width=3] (hi5)--(-2,10.5) coordinate (hi6); \path[orange, line width=3] (hi4)--(-2,10.5) coordinate (hi6); \path[magenta, line width=3] (hi4)--(6,10.5) coordinate (hi7); \path[magenta, line width=3] (hi6)--(2,13) coordinate (hi8); \path[orange, line width=3] (hi7)--(2,13) coordinate (hi8); \path[darkgreen, line width=3] (hi8)--(2,15.5) ; \path (0,0) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \draw[magenta, line width=3] (2,0.5)--(2,3) coordinate (hi); \path (0,0) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (0,2.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \draw[darkgreen, line width=3] (hi)--(-2,5.5) coordinate (hi3); \path (0,2.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (-4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \draw[cyan, line width=3] (hi)--(6,5.5) coordinate (hi2); \path (0,2.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \draw[cyan, line width=3] (hi3)--(2,8) coordinate (hi4); \draw[darkgreen, line width=3] (hi2)--(2,8) coordinate (hi4); \path (-4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (0,7.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \draw[orange, line width=3] (hi3)--(-6,8) coordinate (hi5); %\draw[cyan, line width=3] (hi5)--(-2,10.5) coordinate (hi6); \path (-4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (4,5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (-8,7.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \draw[cyan, line width=3] (hi5)--(-2,10.5) coordinate (hi6); \draw[orange, line width=3] (hi4)--(-2,10.5) coordinate (hi6); \path (-8,7.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (0,7.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (-4,10) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; %\draw[orange, line width=3] (hi4)--(-2,10.5) coordinate (hi6); \draw[magenta, line width=3] (hi4)--(6,10.5) coordinate (hi7); \path (-8,7.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(-90:0.175) node { $ \up $} ; \path (0,7.5) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (4,10) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \draw[magenta, line width=3] (hi6)--(2,13) coordinate (hi8); \draw[orange, line width=3] (hi7)--(2,13) coordinate (hi8); %\draw[darkgreen, line width=3] (hi8)--(2,15) ; \path (-4,10) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(-90:0.175) node { $ \up $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (4,10) coordinate (origin); %\path(a1) --++(90:0.175) node { $ \down $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (0,12.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \draw[darkgreen, line width=3] (hi8)--(2,15) ; \path (0,12.5) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(90:0.175) node { $ \down $} ; %\path(a3) --++(-90:0.175) node { $ \up $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; \path (0,15) coordinate (origin); %\path(a1) --++(-90:0.175) node { $ \up $} ; %\path(a2) --++(-90:0.175) node { $ \up $} ; %\path(a3) --++(90:0.175) node { $ \down $} ; %\path(a4) --++(90:0.175) node { $ \down $} ; %\path(a5) --++(90:0.175) node { $ \down $} ; %\draw[line width=3 ] (2,0.5)--++(90:2.5) --(-2,5.5)--(-6,8)--(2,13)--++(90:2.5); \draw[line width=3 ,,] (2,0.5)--++(90:2.5) coordinate(hi); \draw[line width=3, , ] (2,0.5)--++(90:2.5)--(-2,5.5) coordinate(hi); \draw[line width=3 , ] (hi) to [out=180,in=-120] (-4,6.75) to [out=60,in=90] (-2,5.5) ; \draw[line width=3 , , ] (-2,5.5) --(2,8); \draw[line width=3 , ] (2,8) to [out=0,in=-60] (4,9.25) to [out=120,in=90] (2,8) ; \fill(hi)circle (8pt); \draw[line width=3 , ] (2,8)--(6,5.5) coordinate (hi); \draw[darkgreen, line width=3] (hi8)--++(90:2.5) ;\foreach \i in {2,3,...,8} {\fill(hi\i)circle (8pt); } \path (hi8)--++(90:2.5) coordinate (ghfj) ; \fill (ghfj) circle (8pt); \draw[fill=black] (hi)circle (22pt); \draw (hi) node { \color{white}$ \beta$}; \fill(2,0.5)circle (8pt); \fill(2,3)circle (8pt); \path (2,15.5) circle (22pt); \end{tikzpicture} $$ \caption{On the left we depict a path $\SSTT^\alpha$ and on the right we depict the unique element $\SSTS \in \Path(\beta,\SSTT^\alpha)$ for $\alpha=\color{magenta}s_2\color{darkgreen}s_3\color{orange}s_4 \color{cyan}s_1 \color{magenta}s_2\color{darkgreen}s_3$ and $\beta=\color{magenta}s_2 \color{cyan}s_1 $. These are paths on $\widehat{\mathcal{G}}_{ {(\mathfrak{S}_5, \mathfrak{S}_2\times \mathfrak{S}_3)} } $ (also known as ``Bruhat strolls") but we depict only the edges in $\mathcal{G}_{ {(\mathfrak{S}_5, \mathfrak{S}_2\times \mathfrak{S}_3)} }$ (for readability). } \label{pppspspspsps} \end{figure} %We can reformulate the above in terms of matrix multiplication. %We define the {\sf matrix of light-leaves polynomials} %\[ %\Delta^\Bbbk^{(W,P)}:=( \Delta^\Bbbk_{\la,\mu}(q))_{\la,\mu\in {{^P}W}} %\qquad \qquad %\Delta^\Bbbk_{\la,\mu}(q)=\sum_{\SSTS \in {\rm Path}(\la,\SSTT^\mu)}\!\!\!\!\!\! q^{\deg(\SSTS)} %\] %to be the (square) lower uni-triangular matrix whose entries record the degrees of paths of a given weight and shape. %This matrix can be factorised {\em uniquely} as a product %$\Delta^\Bbbk^{(W,P)}= N^{(W,P)} \times B^{(W,P)}$ of %lower uni-triangular matrices %\[N^{(W,P)}:=(n_{\la,\nu}(q))_{\la,\mu\in {{^P}W}} %\qquad %B^{(W,P)}:=(b_{\nu,\mu}(q))_{\nu,\mu\in {{^P}W}} %\] %such that $n_{\la,\nu}(q)\in q\ZZ[q]$ %for $\la \neq \nu$ %and %$b_{\nu,\mu}(q)\in \ZZ[q+q^{-1}]$. \begin{eg} The matrix $\Delta^\Bbbk$ in type $(\mathfrak{S}_4,\mathfrak{S}_2\times \mathfrak{S}_2)$ is depicted below. \[ %\setlength{\arraycolsep}{8pt} \begin{array}{r|cccccc} \Delta^\Bbbk & \color{magenta}s_2\color{cyan}s_1 \color{darkgreen}s_3 \color{magenta}s_2 & \color{magenta}s_2\color{cyan}s_1 \color{darkgreen}s_3 & \color{magenta}s_2 \color{cyan}s_1 &\color{magenta}s_2 \color{darkgreen}s_3 & \phantom{s_2}\color{magenta}s_2 \phantom{s_2} & \phantom{s_2} \varnothing \phantom{s_2} \\ \hline \color{magenta}s_2\color{cyan}s_1 \color{darkgreen}s_3 \color{magenta}s_2 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ \color{magenta}s_2\color{cyan}s_1 \color{darkgreen}s_3 & q & 1 & \cdot & \cdot & \cdot & \cdot \\ \color{magenta}s_2\color{cyan}s_1 & \cdot & q & 1 & \cdot & \cdot & \cdot \\ \color{magenta}s_2 \color{darkgreen}s_3 & \cdot & q & \cdot & 1 & \cdot & \cdot \\ \color{magenta}s_2 & q & q^2 & q & q & 1 & \cdot \\ \varnothing & q^2 & \cdot & \cdot & \cdot & q & 1 \end{array}\] The factorisation of this matrix is trivial, with $N=\Delta^\Bbbk$ and $B={\rm Id}_{6\times 6}$ the identity matrix. \end{eg} The Hecke category (over the complex field) gives a categorification of this matrix factorisation. \section{Hecke categories and $p$-Kazhdan--Lusztig polynomials} Hecke categories provide the interface between Lie theory and Kazhdan--Lusztig theory. We begin by lifting the ``folded paths" of the previous section to provide (what will be) a basis of the ${\rm Hom}$-spaces of the Hecke category. In this section, we will only explicitly discuss the generators and relations for $\mathscr{H}_{(W,P)}$, the category algebra of the Hecke category, when $W=\mathfrak{S}_{n+m}$ is a finite symmetric group and $P$ is a maximal parabolic $P=\mathfrak{S}_m \times \mathfrak{S}_n$, as this simplifies the definitions considerably, whilst still illustrating the important points of the general case. We define the {\em Soergel generators} to be the framed graphs $$ {\sf 1}_{\emptyset } = \begin{minipage}{1.5cm} \begin{tikzpicture}[scale=1] \draw[densely dotted,rounded corners](-0.5cm,-0.6cm) rectangle (0.5cm,0.6cm); \clip(0,0) circle (0.6cm); %\draw[line width=0.06cm, magenta](0,-1)--(0,+1); \end{tikzpicture} \end{minipage} \quad {\sf 1}_{\csigma } = \begin{minipage}{1.5cm} \begin{tikzpicture}[scale=1] \draw[densely dotted,rounded corners](-0.5cm,-0.6cm) rectangle (0.5cm,0.6cm); \clip(0,0) circle (0.6cm); \draw[line width=0.06cm, magenta](0,-1)--(0,+1); \end{tikzpicture} \end{minipage} \quad {\sf spot}_\csigma^\emptyset = \begin{minipage}{1.5cm} \begin{tikzpicture}[scale=1] \draw[densely dotted,rounded corners](-0.5cm,-0.6cm) rectangle (0.5cm,0.6cm); \clip(0,0) circle (0.6cm); \draw[line width=0.06cm, magenta](0,-1)--(0,+0); \fill[magenta] (0,0) circle (5pt); \end{tikzpicture}\end{minipage} \quad {\sf fork}_{\csigma\csigma}^{\csigma}= \begin{minipage}{2cm} \begin{tikzpicture}[scale=1] \draw[densely dotted,rounded corners](-0.75cm,-0.5cm) rectangle (0.75cm,0.5cm); \clip (-0.75cm,-0.5cm) rectangle (0.75cm,0.5cm); \draw[line width=0.08cm, magenta](0,0)to [out=-30, in =90] (10pt,-15pt); \draw[line width=0.08cm, magenta](0,0)to [out=-150, in =90] (-10pt,-15pt); \draw[line width=0.08cm, magenta](0,0)--++(90:1); \end{tikzpicture} \end{minipage} \quad {\sf braid}_{\csigma\ctau}^{\ctau\csigma}= \begin{minipage}{1cm} \begin{tikzpicture}[scale=1.1] \draw[densely dotted,rounded corners](-0.5cm,-0.5cm) rectangle (0.5cm,0.5cm); \clip(-0.5cm,-0.5cm) rectangle (0.5cm,0.5cm); %\clip(0,0) circle (15pt); \draw[line width=0.08cm, magenta] (0,0) to [out=45, in =-90] (10pt,0.5cm); \draw[line width=0.08cm, magenta] (0,0) to [out=-135, in =90] (-10pt,-0.5cm); \draw[line width=0.08cm, cyan] (0,0) to [out=-45, in =90] (10pt,-0.5cm); \draw[line width=0.08cm, cyan] (0,0) to [out=135, in =-90] (-10pt,0.5cm); \end{tikzpicture}\end{minipage} $$ associated to any pair $\csigma, \ctau\in S_W$ with $m_{\csigma \ctau}=2$. We define the northern/southern reading word of any diagram obtained from horizontal and vertical concatenation of Soergel generators to be the word in the alphabet $S_W $ which records the colours along the northern/southern edge of the frame respectively. We let $\otimes$ to be horizontal concatenation of diagrams, the algebra multiplication $\circ$ will be given by vertical concatenation in the usual manner for diagram algebras. We let $\ast$ denote the anti-involution which flips a diagram through the horizontal axis. \begin{defn}\label{upanddown} We define up and down operators on diagrams as follows \begin{itemize}[leftmargin=*] \item %For $D$ an arbitrary diagram, we define Suppose that $D $ has northern colour sequence $\SSTT^\la $ with $\la\csigma >\la$. We define $$ \qquad {\sf U}^1_\csigma(D)=\begin{minipage}{1.85cm} \begin{tikzpicture}[scale=1.5] \draw[densely dotted, rounded corners] (-0.5,0) rectangle (0.75,0.75) node [midway] {$ D$} ; %\draw[magenta,line width=0.08cm](0,0)--++(90:0.75); % \end{tikzpicture}\end{minipage} %\otimes \begin{minipage}{0.75cm}\begin{tikzpicture}[scale=1.5] \draw[densely dotted, rounded corners] (-0.25+1,0) rectangle (0.25+1,0.75); \draw[magenta,line width=0.08cm](0+1,0)--++(90:0.75); \end{tikzpicture}\end{minipage} \qquad \qquad \qquad \qquad {\sf U}^0_\csigma(D)= \begin{minipage}{1.85cm}\begin{tikzpicture}[scale=1.5] \draw[densely dotted, rounded corners] (-0.5,0) rectangle (0.75,0.75) node [midway] {$D$} ; %\draw[magenta,line width=0.08cm](0,0)--++(90:0.75); % \end{tikzpicture}\end{minipage} % \otimes %\begin{minipage}{0.75cm}\begin{tikzpicture}[scale=1.5] \draw[densely dotted, rounded corners] (-0.25+1,0) rectangle (0.25+1,0.75); \draw[magenta,line width=0.08cm](0+1,0)--++(90:0.3525) coordinate (hi); \draw[fill=magenta,magenta] (hi) circle (3pt); \end{tikzpicture}\end{minipage} \qquad \qquad \qquad $$ \item Now suppose that $D $ has northern colour sequence $ \SSTT^\la \otimes \csigma $ with $\la\csigma >\la$. %We let $\y \in $ be obtained by deleting $\x {\color{magenta}[r,c]}=k$ then we let % $\y ^{-1}(j)=\x ^{-1}(j)$ for $ 1\leq j