%% 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{150}
%% 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{amssymb,verbatim}
\usepackage{amsmath,amsfonts,enumitem}
\usepackage[mathscr]{euscript} % make a nice \Net
\usepackage{amsthm}
% \usepackage{color}
\usepackage{url}
\usepackage{graphicx} %to include figure
\usepackage{enumitem} %to use nice enumeration with changed indent
%\usepackage[titletoc,toc,title]{appendix}
% \usepackage{lineno,xcolor} %to make line numbers
%\usepackage{authblk} %to make line numbers
\usepackage{hyperref} % to make links for lemmas and theorems
\hypersetup{colorlinks} %so the links look nicer
\usepackage{bbm} % for the characteristic function 1
\usepackage{bm} % for bold greek letter
\usepackage{mathrsfs} %to use \mathscr
\usepackage{cancel} %to make sout to cross things out
\usepackage{ytableau} %to draw tableaux

%\usepackage{cleveref} % to make references use name without needing to type it out
% \usepackage[lined,algonl,boxed,norelsize]{algorithm2e} % to make algorithm
% \usepackage{diagbox}%making diagonal for tables
% \usepackage{threeparttable} %making footnotes in table
% \usepackage{extarrows} %to use \xlongrightarrow, note that it doesn't come with \xdashrightarrow! We need to define it ourselves.
% \usepackage{tikz-cd} %to draw commutative diagram
% \usepackage{ltablex} % to allow for automatic new line and multipages in table


% \usepackage{refcheck}
% \nocite{*}


%\usepackage[colorinlistoftodos]{todonotes}

\RequirePackage{cleveref}
\usepackage{hypcap}
%\hypersetup{colorlinks=true, citecolor=darkblue, linkcolor=darkblue}
\definecolor{darkblue}{rgb}{0.0,0,0.7}
\newcommand{\darkblue}{\color{darkblue}}

\definecolor{darkred}{rgb}{0.68,0,0}
\newcommand{\darkred}{\color{darkred}}


\definecolor{darkgreen}{rgb}{0,.38,0}
\newcommand{\darkgreen}{\color{darkgreen}}

\newcommand{\defn}[1]{\emph{\darkblue #1}}
\newcommand{\defna}[1]{\emph{\darkred #1}}
\newcommand{\defnb}[1]{\emph{\darkblue #1}}
\newcommand{\defng}[1]{\emph{\darkgreen #1}}


% \usepackage{lipsum} % to insert latin gibberish

% \usepackage{graphicx}
%\usepackage{tikz}
%\usetikzlibrary{arrows.meta} %to draw bigger arrows

%\usepackage{standalone} %to externalize tikz load


%global options for enumerate
\setlist[enumerate]{
	label=\textnormal{({\roman*})},
	ref={\roman*}}


%to make the theorem name bold
\makeatletter
\def\th@plain{%
	\thm@notefont{}% same as heading font
	\itshape % body font
}
\def\th@definition{%
	\thm@notefont{}% same as heading font
	\normalfont % body font
}
\makeatother


%\linespread{1.5}


\newtheorem{thm}{Theorem}[section]
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{claim}[thm]{Claim}
\newtheorem*{claim*}{Claim}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{Def}[thm]{Definition}
\newtheorem{mt}[thm]{Meta Theorem}

\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{conv}[thm]{Convention}
\newtheorem{question}[thm]{Question}
\newtheorem{por}[thm]{Porism}
\newtheorem{result}[thm]{Result}
\newtheorem{exc}{Exercise}[section]
\newtheorem{sublemma}[thm]{Sublemma}
\newtheorem{op}[thm]{Open Problem}

% Theorem environments with roman or slanted font
\theoremstyle{definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{rem}[thm]{Remark}
%\newtheorem{rem}[thm]{Example}
\newtheorem{definition}[thm]{Definition}
%\newtheorem{Alg}[thm]{Algorithm}
%\newtheorem{Rtne}[thm]{Routine}
\newtheorem{Warn}[thm]{Caution}


%\numberwithin{figure}{section}
%\numberwithin{equation}{section}

%%%%%%%%%%%%% shortcuts and macros

\def\wh{\widehat}
\def\bu{\bullet}
\def\emp{\nothing}
\def\sq{\square}
%\def\st{\star}
\def\bd{\blacktriangledown}
\def\ap{\approx}
\def\RP{\mathbb R \mathbb P}
\def\aA{\mathbb A}
\def\zz{\mathbb Z}
\def\nn{\mathbb N}
\def\cc{\mathbb C}
\def\ll{{\mathcal{L}}}
\def\rr{\mathbb R}
\def\qqq{\mathbb Q}
\def\tT{\mathbb T}
\def\ee{\mathbb E}
\def\hH{\mathbb H}
\def\ff{\mathbb F}
\def\sS{\mathbb S}
\def\SS{\mathbb S}
\def\oo{\mathbb O}
\def\pp{\mathbb P}
\def\fq{{\mathbb F}_q}
\def\ov{\overline}
\def\gG{\mathbb G}
\def\sm{\smallsetminus}
\def\pr{\prime}
\def\Ga{\Gamma}
\def\Om{\Omega}
\def\BOm{{\mathbf{\Omega}}}
\def\De{\Delta}
\def\Si{\Sigma}
\def\la{\lambda}
\def\ga{\gamma}
\def\si{\sigma}
\def\de{\delta}
\def\ep{\ve}
\def\al{\alpha}
\def\be{\beta}
\def\om{\omega}
\def\k{\kappa}
\def\ka{\vk}
\def\ve{\varepsilon}
\def\vr{\text{\rm deg}}
\def\vp{\varphi}
\def\vk{\varkappa}
%\def\CR{\mathcal R}
%\def\GG{\mathfrak G}
\def\GI{\mathfrak I}
\def\CS{\mathcal S}
\def\cC{\mathcal C}
\def\cB{\mathcal B}
\def\cI{\mathcal I}
\def\ca{\mathcal A}
\def\cA{\mathcal A}
\def\cd{\mathcal D}
\def\cD{\mathcal D}
\def\ce{\mathcal E}
\def\cf{\mathcal F}
\def\cF{\mathcal F}
\def\cg{\mathcal G}
\def\cH{\mathcal H}
\def\ck{\mathcal K}
\def\cl{\mathcal L}
\def\cL{\mathcal L}
\def\cm{\mathcal M}
\def\cM{\mathcal M}
\def\co{\mathcal O}
\def\cO{\mathcal O}
\def\cp{\mathcal P}
\def\cP{\mathcal P}
\def\cq{\mathcal Q}
\def\cQ{\mathcal Q}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cT{\mathcal T}
\def\cv{\mathcal V}
\def\cw{\mathcal W}
\def\cX{\mathcal X}
\def\cY{\mathcal Y}
\def\cZ{\mathcal Z}



\def\CB{\mathcal B}
\def\T{\mathbf{T}}
\def\CT{\text{CT}}
\def\CTr{\text{\em CT}}
\def\BB{\mathbf{B}}
\def\bP{\mathbf{P}}
\def\ssu{\subset}
\def\sss{\supset}
\def\wt{\widetilde}
\def\<{\langle}
\def\>{\rangle}

\def\DET{\text{{\rm DET}}}

\def\ComW{\text{\small {\rm W}}}
\def\vrV{\text{\small {\rm V}}}

\def\const{\text{{\rm const}}}
\def\width{\text{{\rm width}}}
\def\height{\text{{\rm height}}}
%\def\sc{ {\text {\rm sc}  } }
\def\rc{ {\text {\rm rc}  } }
\def\y{ {\text {\rm y}  } }
\def\sy{ {\text {\rm sy}  } }
%\def\Z{ {\text {\rm Z} } }
\def\Z{\zz}
\def\FF{ {\text {\rm F} } }
\def\RR{ {\text {\rm R} } }
\def\SO{ {\text {\rm SO} } }
\def\OOO{ {\text {\rm O} } }
\def\SL{ {\text {\rm SL} } }
\def\GL{ {\text {\rm GL} } }
\def\NF{ {\text {\rm NF} } }
\def\rR{ {\textsc {\rm R} } }
\def\rM{ {\text {\rm M} } }
\def\rP{ {\text {\rm P} } }
\def\rU{ {\text {\rm U} } }
\def\rH{ {\text {\rm H} } }
\def\Ker{ {\text {\rm Ker} } }
\def\Cat{ {\text {\rm Cat} } }

\def\rk{\dim}
\def\srk{\dim}
\def\prev{\prec}
\def\oa{\overrightarrow}
\def\Ups{{{\Upsilon}}}
\def\ups{\upsilon}
\def\vt{\ze}
\def\dv{\divideontimes}
\def\U{{\text {\rm U} } }
\def\rT{{\text {\rm T} } }
\def\Q{{\text {\rm Q} } }
\def\mix{{\text {\rm mix} } }
\def\Sf{{\text{\rm \bf S}}}
\def\rK{{\text{\textsf{K}}}}
\def\bF{{\text{\bf F}}}
\def\RU{\UR}

\def\St{{\text {\rm Stab} } }

\def\0{{\mathbf 0}}
\def\id{{\rm id}}
\def\st{{\rm st}}
\def\ma{{\rm ma}}


\def\th{{\rm th}}
\def\ol#1{{\overline {#1}}}
\def\tl{\triangleleft}
%\def\ED{{\text{\rm ED}}}
\def\II{{\mathcal I}}

%\def\par{{\partial}}
\def\LL{{\mathcal L}}
\def\NN{{\mathbb N}}
\def\OO{{\mathcal O}}
%\def\TT{{\mathcal T}}
\def\VV{{\mathcal V}}
\def\YY{{\mathcal Y}}

\def\closest{\multimap}
\def\implies{\Rightarrow}
\def\nothing{\varnothing}

\def\.{\hskip.06cm}
% \def\ts{\hskip 0cm}
 \def\ts{\hskip.03cm}
\def\mts{\hspace{-.04cm}}
\def\ang{\angle \.}
\def\sphang{\sphericalangle}
\def\sang{\sphericalangle \.}

\def\dist{{\text {\rm dist} }}
\def\area{{\text {\rm area} }}
%\def\per{{\text {\rm perimeter} }}
\def\vol{{\text {\rm vol}}}
\def\conv{{\text {\rm {conv}} }}
\def\shul{{\text {\rm {sh}} }}
\def\clip{{\text {\rm {clip}} }}
\def\radius{{\text {\rm radius}}}
\def\cent{{{\text{\rm cm}}}}
\def\diam{{\text {\rm diam}}}
\def\ind{{\text {\rm ind}}}
\def\cayley{{\text {\rm Cayley} }}
\def\CM{{\text {\rm CM}}}

\def\lra{\leftrightarrow}
\def\Lra{\Leftrightarrow}
\def\bow{\bowtie}
\def\zyl{\asymp}
\def\pt{\partial}
\def\nl{\textbf{\textit{u}}}
\def\nlH{\nl_{\hskip-.04cm H}}
\def\nlF{\nl_{\hskip-.04cm F}}
\def\bio{{\text{\bf {0}}}}
\def\bz{{\textbf{z}}}
\def\bzr{\emph{\textbf{z}}}
\def\bx{{\textbf{\textit{x}}}}
\def\bxr{\emph{\textbf{x}}}
\def\by{{\textbf{y}}}
\def\nts{\hskip-.04cm}
%
\def\bbu{\textbf{\textit{u}}}
\def\bbe{\textbf{\textit{e}}}
\def\bw{\textbf{\textit{w}}}
\def\bbw{\textbf{\textit{w}}}
\def\bbv{\textbf{\textit{v}}}
\def\br{\textbf{\textit{r}}}
%\def\vb{\textbf{\textit{a}}}
\def\bv{\textbf{\textit{v}}}
\def\ba{\textbf{\textbf{a}}}
\def\bb{\textbf{\textbf{b}}}
\def\bd{\textbf{\textbf{d}}}

\def\rba{\textbf{\em \textbf{a}}}
\def\rbb{\textbf{\em \textbf{b}}}
\def\bat{\emph{\textbf{\textbf{a}}}}
\def\bc{\textbf{\textbf{c}}}
\def\bC{\textbf{\textbf{C}}}
\def\bct{\emph{\textbf{\textbf{c}}}}

\def\bA{\textbf{\textit{A}}}

\def\bX{\textbf{\textit{X}}}
\def\bZ{\textbf{\textit{Z}}}
\def\bcx{\textbf{\textit{x}}}
\def\bcy{\textbf{\textit{y}}}

\def\bI{\textbf{\textit{I}}}

\def\PerC{C$_{\text{\sc PER}}$}
\def\PerV{V$_{\text{\sc PER}}$}

%
\def\gR{\frak{A}}
\def\gD{\frak{D}}
\def\bal{{\mathbf{\al}}}
\def\vvt{f}
\def\bdel{\mathbf{\de}}
\def\ud{}
\def\mi{{\rm {\textsf{m}}}}

\def\cyR{{$(\Re)$}}
\def\mcc{{($\frak{J})$}}
\def\corn{{($\frak{C})$}}
\def\mich{{($\frak{M})$}}

\def\La{\Lambda}
\def\LA{\Lambda}
\def\LAM{\Lambda^\triangledown}

\def\btr{{\rho}}
\def\ctr{{\mathfrak{R}}}
\def\Ctr{{\mathcal{A}}}
%\def\bbu{\text{\bf{{e}}}}
%\def\bw{\text{\bf{{w}}}}
%\def\bw{\textbf{w}}
%\def\br{\textbf{r}}

\def\bba{{\text{\bf a}}}
\def\bbb{{\text{\bf b}}}
\def\bbc{{\text{\bf c}}}
\def\sfb{{\text{\sc s}}}

\def\di{{\small{\ts\diamond\ts}}}
\def\dQ{{\mathcal{Q}}}
\def\Di{{\mathfrak{D}}}
\def\kK{{\Bbbk}}
\def\ze{{\zeta}}

\def\senkin{{{Sen{\rm \small \textsf{'}}kin}}}
\def\fsenkin{{{Sen{\rm \footnotesize\textsf{'}}kin}}}

\def\dimo{{\diamond}}
\def\bstar{{\sharp}}

\def\open{{\rm \footnotesize [{$\ast$}] \.\ts\ts}}

\def\ram{{\!\! {\footnotesize $\lozenge$ \,}}}
\def\ra{{\rm {\footnotesize [\texttt{1}]} \.\ts }}
\def\rapu{{\rm {\footnotesize [\texttt{1+}]} \.\ts }}
\def\rami{{\rm {\footnotesize [\texttt{1-}]} \.\ts }}
%
\def\rapmu{{\rm {\footnotesize [\texttt{1-}]}, {\footnotesize [\texttt{1}]} \. and {\footnotesize [\texttt{1+}]}}}
\def\rbpmu{{\rm {\footnotesize [\texttt{2-}]}, {\footnotesize [\texttt{2}]} \. and {\footnotesize [\texttt{2+}]}}}
%
\def\rbmi{{\rm {\footnotesize [\texttt{2-}]} \.\ts }}
\def\rb{{\rm {\footnotesize [\texttt{2}]} \.\ts }}
\def\rbpu{{\rm {\footnotesize [\texttt{2+}]} \.\ts }}
% \def\rbpmu{{\rm {\footnotesize [\texttt{2$\pm$}]} \.\ts }}
% \def\rcmi{{\rm {\footnotesize [\texttt{3-}]} \.\ts }}
% \def\rd{{\rm {\footnotesize [\texttt{3}]} \.\ts }}
\def\rcmi{\rbpu}
\def\rd{\rbpu}

% \newcommand{\id}{\mathrm{id}}

\newcommand{\Ehr}{\mathrm{Ehr}}
\newcommand{\tr}{\mathrm{tr}}
\newcommand{\sh}{\mathrm{sh}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\bin}{\mathrm{bin}}
\newcommand{\red}{\mathrm{red}}
\newcommand{\pc}{\mathrm{PC}}
\newcommand{\PM}{\mathrm{PM}}
\newcommand{\per}{\mathrm{per}}
\newcommand{\maj}{\mathrm{maj}}
\newcommand{\wi}{\mathrm{width}}
\newcommand{\EA}{\mathcal{A}}
\newcommand{\BT}{\mathcal{BT}}
\newcommand{\PT}{\mathcal{PT}}
%\newcommand{\LR}{\mathcal{LR}}
%i\newcommand{\PP}{\operatorname{PP}}
\newcommand{\Hex}{\operatorname{H}}
\newcommand{\RPP}{\operatorname{RPP}}
\newcommand{\SSYT}{\operatorname{SSYT}}
\newcommand{\SYT}{\operatorname{{\rm SYT}}}

\def\aH{\textrm{H}}
\def\aHr{\textrm{\em H}}
\def\ah{\textrm{h}}
\def\aI{{ \textrm{I} } }
\def\aIr{\textrm{\em I}}
\def\aJ{\textrm{J}}
\def\aJr{\textrm{\em J}}
\def\aK{\textrm{K}}
\def\aKr{\textrm{\em K}}
\def\aL{\textrm{L}}
\def\aLr{\textrm{\em L}}
\def\aM{\textrm{M}}
\def\am{\textrm{m}}
\def\aMr{\textrm{\em M}}
\def\aN{\textrm{N}}
\def\aNr{\textrm{\em N}}
\def\an{\textrm{n}}

\def\ah{\textrm{h}}
\def\ahr{\textrm{\em h}}

\def\atom{\textsf{{atom}}}
\def\atomrm{\textsf{\em {atom}}}

\def\.{\hskip.06cm}
\def\ts{\hskip.03cm}
\def\mts{\hspace{-.04}}
\def\nin{\noindent}
\def\tts{\hskip.02cm}


\def\SS{{S}}
\def\bal{\ov{\al}}
\def\bbe{\ov{\be}}
\def\hba{\hslash}

\def\qp{\textrm{q}}
\def\eG{\Phi}

\newcommand{\textsu}[1]{\textup{\textsf{#1}}}


\newcommand{\SI}{\textup{{\ensuremath{\mathcal S\!I}}}}
\newcommand{\ComCla}[1]{\textup{\textsu{#1}}}
\newcommand{\problem}[1]{\mbox{{\normalfont\textsc{#1}}}} %do not use all caps here, but use "upper camel case" instead: UpperCamelCase
\newcommand{\problemp}[1]{\mbox{\normalfont\textsc{$(\problem{#1})$}}}
\newcommand{\sharpP}{\ComCla{\#P}}
\newcommand{\SP}{\ComCla{\#P}}
\newcommand{\SBQP}{\ComCla{\#BQP}}

\newcommand{\sharpFA}{\ComCla{\#FA}}
\newcommand{\sharpPDA}{\ComCla{\#PDA}}
\newcommand{\sharpPDAF}{\ComCla{\#PDAF}}
\newcommand{\sharpEXP}{\ComCla{\#EXP}}

\newcommand{\GapP}{\ComCla{GapP}}
\newcommand{\GapFP}{\ComCla{GapP/FP}}
\newcommand{\GapPP}{\ComCla{GapP}_{\ge 0}}
\newcommand{\PolynP}{\ComCla{PolynP}}
\newcommand{\PolynPP}{\ComCla{PolynP}_{\ge 0}}
\newcommand{\MultGapP}{\ComCla{MultGapP}}

\newcommand{\Sigmap}{\ensuremath{\Sigma^{{\textup{p}}}}}

\newcommand{\PPAD}{\ComCla{PPAD}}
\newcommand{\PPADS}{\ComCla{PPADS}}
\newcommand{\PPA}{\ComCla{PPA}}
\newcommand{\PPP}{\ComCla{PPP}}
\newcommand{\CLS}{\ComCla{CLS}}
\newcommand{\PLS}{\ComCla{PLS}}
\newcommand{\TFNP}{\ComCla{TFNP}}
\newcommand{\PTFNP}{\ComCla{PTFNP}}

\newcommand{\F}{\ComCla{F}}
\newcommand{\UP}{\ComCla{UP}}
\newcommand{\coUP}{\ComCla{coUP}}
\newcommand{\NP}{\ComCla{NP}}
\newcommand{\BPP}{\ComCla{BPP}}
\newcommand{\coNP}{\ComCla{coNP}}
\renewcommand{\P}{\ComCla{P}}
\newcommand{\CeqP}{\ComCla{C$_=$P}}
\newcommand{\coCeqP}{\ComCla{coC$_=$P}}
\newcommand{\PH}{\ComCla{PH}}
\newcommand{\PSPACE}{\ComCla{PSPACE}}
\newcommand{\FP}{\ComCla{FP}}
\newcommand{\PP}{\ComCla{PP}}

\def\SP{\sharpP}
\def\poly{{\P}}
\def\CEP{{\CeqP}}

\def\HH{\Phi}
%\def\GapP{{\textsc{GapP}}}


\def\Pb{{\text{\bf P}}}
\def\Path{{\text{\rm Path}}}

\def\xx{\textbf{\textit{x}}}
\def\yy{\textbf{\textit{y}}}
\def\uu{\textbf{\textit{u}}}
\def\aa{\textbf{{\textit{a}}}}

\def\RG{\textrm{G}}
\def\RH{\textrm{H}}
\def\GG{\wh{\RG}}

\newcommand{\inv}{\operatorname{{\rm inv}}}

\newcommand\cover{\mathrel{\ooalign{$<$\cr
  \hidewidth\hbox{$\cdot\mkern0.5mu$}\cr}}}


\newcommand{\LE}{\ce}


\def\QSym{ {\text {\sc QSym} } }

\def\Com{ {\text {\rm Com} } }
\def\lc{ {\textup {\rm lc} } }
\def\uc{ {\textup {\rm uc} } }

\def\Incom{\overline{\Com} }

\newcommand{\iA}{\textnormal{A}} %% Macro for convex bodies
\newcommand{\iB}{\textnormal{B}} %% Macro for convex bodies
\newcommand{\iC}{\textnormal{C}} %% Macro for convex bodies
\newcommand{\iD}{\textnormal{D}} %% Macro for convex bodies
\newcommand{\iF}{\textnormal{F}} %% Macro for convex bodies
\newcommand{\iJ}{\textnormal{J}} %% subspaces
\newcommand{\iK}{\textnormal{K}} %% Macro for convex bodies
\newcommand{\iL}{\textnormal{L}} %% Macro for convex bodies
\newcommand{\iM}{\textnormal{M}} %% Macro for convex bodies
\newcommand{\ir}{\textnormal{r}} %% Macro for convex bodies

\newcommand{\iQ}{\textnormal{Q}} %% Macro for convex bodies
\newcommand{\ibQ}{{\textnormal{\bf Q}}} %% Macro for convex bodies

\newcommand{\iS}{\textnormal{S}} %% Macro for segments
\newcommand{\iU}{\textnormal{U}} %% Mixed volumes
\newcommand{\iV}{\textnormal{V}} %% Mixed volumes
\newcommand{\iW}{\textnormal{W}} %% subspaces
%\newcommand{\Sc}{\mathcal{S}} %% Macro for convex bodies

%\newcommand{\Ac}{\mathcal{A}} %% An a-type
\newcommand{\Rc}{\mathcal{R}} %% unit normal vectors
\newcommand{\Vol}{\textnormal{Vol}} %% Normal volume

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Macros by Swee Hong
\DeclareMathOperator{\Ac}{\mathcal{A}} % Minimum elements of poset of order ideals
\DeclareMathOperator{\Adm}{\textnormal{Adm}} % Admissible sets
\DeclareMathOperator{\Al}{\overline{A}} % partial tiered events
\DeclareMathOperator{\alb}{\bm{\alpha}} % bolded alpha
\newcommand{\Alh}{\overline{A'}} % partial tiered events
\DeclareMathOperator{\Bc}{\mathscr{B}} % special set of events
\DeclareMathOperator{\cb}{\mathbf{c}} % characteristic vector
\DeclareMathOperator{\eb}{\mathbf{e}} % standard basis vector
\DeclareMathOperator{\Dc}{\mathcal{D}} %The set of partial linear extensions
\DeclareMathOperator{\Ec}{\mathcal{E}} %The set of all linear extensions
\DeclareMathOperator{\El}{\overline{\mathcal{E}}} %The set of all partial linear extensions
\DeclareMathOperator{\CR}{\textnormal{CR}} % Cross-ratio partial order
\DeclareMathOperator*{\essinf}{ess\,inf}
\DeclareMathOperator{\Fc}{\mathcal{F}} %polynomial
\DeclareMathOperator{\fwd}{\text{fwd}} %forward operation
\DeclareMathOperator{\Gc}{\mathcal{G}} %polynomial
\DeclareMathOperator{\hb}{\mathbf{h}} % characteristic vector
\DeclareMathOperator{\Hc}{\mathcal{H}} % characteristic vector
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\Kc}{\mathcal{K}} %polynomial
\DeclareMathOperator{\Krew}{\text{Krew}} % Kreweras posets
\DeclareMathOperator{\Lc}{\mathscr{L}} % Linear extensions of parallel composition of two chains
\newcommand{\Ll}[1]{\overline{L_{#1}}} % partial linear extensions
\newcommand{\Llh}[1]{\overline{L'_{#1}}} % partial linear extensions
\DeclareMathOperator{\Ndg}{\text{Ndg}} % nondegenerate relations
\DeclareMathOperator{\Oc}{\mathcal{O}} % Order polytopes
\newcommand{\Nl}[1]{\overline{N_{#1}}} % partial linear extensions
\DeclareMathOperator{\Omegal}{\overline{\Omega}} % vector with value 1 at the first entry 0 everything else
\DeclareMathOperator{\one}{\mathbf{1}} % vector with value 1 at the first entry 0 everything else
\DeclareMathOperator{\Pc}{\mathscr{P}} % parallel composition of two chains
\newcommand{\Pl}[1]{\overline{\Pb_{#1}}} % partial linear extensions
\DeclareMathOperator{\Rb}{\mathbb{R}} %Real numbers
\DeclareMathOperator{\rv}{\mathbf{r}} %Real vectors
\def\precc{\preccurlyeq} % nicer poset leq sign
\def\succc{\succcurlyeq} % nicer poset geq sign
\newcommand{\sumh}{\overline{\sum_{h}}} %
\newcommand{\sumhh}{\overline{\sum_{h}'}} %
\DeclareMathOperator{\Sz}{\textnormal{Sz}} % Szemeredi parallel symbol
\DeclareMathOperator{\vb}{\mathbf{v}} % vector
\DeclareMathOperator{\wb}{\mathbf{w}} % vector
\DeclareMathOperator{\wgt}{\mathtt{wgt}} % weight function
\DeclareMathOperator{\xb}{\mathbf{x}} % a vector
\DeclareMathOperator{\Xc}{\mathcal{X}} % parallel composition of two chains
\DeclareMathOperator{\yb}{\mathbf{y}} % a vector
\DeclareMathOperator{\zb}{\mathbf{z}} % a vector
\DeclareMathOperator{\Zb}{\mathbb{Z}} % Integers
\DeclareMathOperator{\zero}{\mathbf{0}} % zero vector

\DeclareMathOperator{\Nc}{\mathcal{N}}
\DeclareMathOperator{\Eb}{\mathbb{E}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Macros by Colleen
\newcommand{\Sc}{\mathfrak{S}}
\newcommand{\FS}{\mathfrak{F}}
\newcommand{\code}{{\sf{code}}}
\newcommand\wtx{{\tt wt}}



%% define your title in the usual way
\title[Signed combinatorial interpretations]{\texorpdfstring{Signed combinatorial interpretations \\ in algebraic combinatorics}{Signed combinatorial interpretations in algebraic combinatorics}}

%% 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{\texorpdfstring{Igor Pak\addressmark{1} \and Colleen Robichaux\thanks{\href{mailto:robichaux@math.ucla.edu}{robichaux@math.ucla.edu}. The first author was partially supported by the NSF grant CCF-2007891.
The second author was partially supported by the NSF MSPRF grant DMS-2302279.}\addressmark{1}}{Igor Pak and Colleen Robichaux}}



%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, UCLA, Los Angeles, CA 90095, USA}

%% put the date of submission here
\received{October 30, 2024}

%% 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 prove the existence of signed combinatorial interpretations for
several large families of structure constants.  These families include
standard bases of symmetric and quasisymmetric polynomials, as well as
various bases in  Schubert theory.  The results are stated in the
language of computational complexity, while the proofs are based on the
effective M\"obius inversion.}

%% 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{symmetric functions, quasisymmetric functions, Schubert polynomials, combinatorial interpretation, structure constants, $\#{\sf P}$, ${\sf GapP}$}

%% 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{GapP.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle

\nin

\section{Introduction}\label{s:intro}
In this paper, we make a systematic study and prove signed combinatorial
interpretations for structure constants
for many families of symmetric functions, their relatives, and generalizations.
We present signed combinatorial interpretations in all cases,
leading to the following meta observation:

\begin{center}\begin{minipage}{8cm}%
{\hskip-.5cm\defn{In algebraic combinatorics, all integral constants have signed combinatorial
interpretations.}}
\end{minipage}\end{center}
This is an extended abstract of \cite{PR24}.


\subsection{Signed combinatorial interpretations} \label{ss:intro-signed}


Let \ts $W:=\{0,1\}^\ast$ \ts and \ts $W_n :=\{0,1\}^n$ \ts be sets of \emph{words}.
The length \ts $|w|$ \ts is called the \emph{size} of~$w\in W$.
A \emph{language} \ts is defined as \ts $A \subseteq W$.
Denote \ts $A_n :=  A \cap W_n$.  We say \ts $A$ \ts
is in \ts $\NP$ \ts if the membership \ts $[w\in^? A]$ \ts can
be decided in polynomial time (in the size $|w|$),
by a nondeterministic Turing Machine.  We view \ts $A_n$ \ts
as the set of \emph{combinatorial objects} of size~$n$.  


Let \ts $f: W\to \nn$ \ts be an integer function.
We say that $f$ has a \defn{combinatorial interpretation}
(also called a \emph{combinatorial formula}) if \ts $f\in \SP$.
This means there is a language \ts $B\subseteq W^2$ \ts
in~$\NP$, such that for all \ts $w\in W$ \ts we have \ts
$f(w) = \#\{u \. : \. (w,u) \in B\}$.  
% Informally, we say that the language
% \ts $B$ \ts \defn{counts the numbers}~$\{f(w)\}$.
In algebraic combinatorics, all standard combinatorial interpretations are
in~$\SP$. 
These include \emph{character degrees} \ts $f^\la = \chi^\la(1)$, \ts
\emph{Kostka numbers} \ts $K_{\la\mu}$, \ts and the \emph{Littlewood--Richardson} (LR) \emph{coefficients}
\ts $c^\la_{\mu\nu}$, see e.g.\ \cite{Mac95}. 
For broader discussion, consult \cite{IP22,Pak-OPAC}.


Let \ts $f: \{0,1\}^\ast\to \zz$ \ts be an integer function.
We say that function $f$ has a \defn{signed combinatorial interpretation}
(also called \emph{signed combinatorial formula}),
if \ts $f = g-h$ \ts for some \ts $g,h\in \SP$.  The set of such functions
is denoted \ts $\GapP := \SP-\SP$.  


In algebraic combinatorics, there are many natural examples of signed combinatorial
interpretations. As we mentioned above, these include \emph{character values} \ts
$\chi^\la(\mu)$ \ts via the \emph{Murnaghan--Nakayama rule}.
Another example is the
\emph{inverse Kostka numbers} \ts $K^{-1}_{\la\mu}$ \ts defined as the entry
in the inverse Kostka matrix \ts $(K_{\la\mu})^{-1}$, given by the
\emph{E\u{g}ecio\u{g}lu--Remmel rule} \cite{ER90}.  In both cases,
the rules subtract the number of certain rim hook tableaux, some with
a positive sign and some with a negative, where the sign is easily computable.


Additionally
there are many examples of signed combinatorial interpretations
for nonnegative functions.
Famously, \emph{Kronecker coefficients} \ts $g(\la,\mu,\nu)$ \ts are given by the
large signed summation of the numbers of $3$-dimensional contingency arrays.
Another celebrated example is the \emph{Schubert structure constants}  \ts $c^\ga_{\al\be}$ \ts
given by the \emph{Postnikov--Stanley formula} \ts  in terms of the number of
chains in the Bruhat order \cite[Corollary~17.13]{PS09}.

\subsection{Main results} \label{ss:intro-main}
%
Let \ts $\rR$ \ts be a ring and let \ts $\Ups:=\{\xi_\al\}$ \ts be a linear basis
in~$\rR$, where the indices form a set \ts $A$ \ts of combinatorial
objects.
%
The \defn{structure constants} \ts $c(\al,\be,\ga)$ \ts
for \ts $\Ups$ \ts are defined
$$
\xi_\al \cdot \xi_\be \, = \, \sum_{\ga\in A} \. c(\al,\be,\ga) \. \xi_\ga \ \ \text{where} \ \ \al,\be\in A\ts.
$$
When the structure constants are integral, one can ask whether the function \ts $\bc: A^3 \to \zz$ \ts
is in $\GapP$, i.e.,\
has a signed combinatorial interpretation.   Additionally, when they are nonnegative,
one can ask if \ts $\bc$ \ts is in $\SP$, i.e.,\ has a (usual) combinatorial interpretation.



\begin{thm}[{\rm classic structure constants}{}]\label{t:main-classic}
Let \ts $\La_n = \cc[x_1,\ldots,x_n]^{S_n}$ \ts denote symmetric polynomials in $n$ variables.
The following bases in \ts $\La_n$ \ts have structure constants in~$\SP:$ 
Schur polynomials \ts $\{s_\la\.:\. \ell(\la) \le n\}$, monomial symmetric polynomials \ts $\{m_\la\.:\. \ell(\la) \le n\}$, power sum symmetric polynomials \ts $\{p_\la\.:\. \la_1 \le n\}$, elementary symmetric polynomials \ts $\{e_\la\.:\. \la_1 \le n\}$, and complete homogeneous symmetric polynomials \ts $\{h_\la\.:\. \la_1 \le n\}$.
\end{thm}

The last four of these items are completely straightforward and follow
directly from their definition. However, the first item 
is highly nontrivial.  


Now consider deformations of Schur polynomials.  Fix \ts $q,t,\al \in \qqq$.

\begin{thm}\label{t:main-qt}
    The following bases in $\La_n$ have structure coefficients in~$\GapFP:$
    \begin{itemize}
        \item Jack symmetric polynomials \ts $\{P_{\la}(x;\alpha)\.:\. \ell(\la) \le n\}$, where \ts $\al>0$,
        \item Hall--Littlewood polynomials \ts $\{P_{\la}(x;t)\.:\. \ell(\la) \le n\}$, where \ts $0\le t <1$,  and
        \item Macdonald symmetric polynomials \ts $\{P_{\la}(x;q,t)\.:\. \ell(\la) \le n\}$, where \ts $0\le q,t <1$.
    \end{itemize}
\end{thm}


Here \ts $\GapFP$ \ts is a class of rational functions which can be written as \ts
$f/g$ \ts where $f\in \GapP$ \ts and \ts $g\in \FP$ \ts is a function which can be computed in
polynomial time.  



Second, we consider quasisymmetric polynomials which are somewhat
intermediate between symmetric and general polynomials:

\begin{thm}[{\rm quasisymmetric structure constants}{}]\label{t:main-quasi}
Let \ts $\QSym_n\subseteq\cc[x_1,\ldots,x_n]$ \ts be the ring of quasisymmetric polynomials.  The following bases have structure constants in~$\SP:$
    \begin{itemize}
        \item monomial quasisymmetric polynomial \ts $\{M_{\al}\}$, and
        \item fundamental quasisymmetric polynomials \ts $\{F_{\al}\}$.
\end{itemize}
The following bases have structure constants in~$\GapP:$
    \begin{itemize}
        \item dual immaculate polynomials \ts $\{\Sc_\al^*\}$, and
        \item quasisymmetric Schur polynomials \ts $\{\mathcal{S}_\al\}$.
\end{itemize}
The following  bases have structure constants in~$\SP/\FP:$
    \begin{itemize}
        \item  type 1 and type 2 quasisymmetric power sums \ts
        $\{\Psi_\al\}$ and $\{\Phi_\al\}$, as well as
        \item combinatorial quasisymmetric power sum \ts
        $\{\mathfrak{p}_\al\}$.
\end{itemize}
Here we have \ts $\al$ \ts ranges over compositions into at most $n$ positive parts.
\end{thm}


The first two items go back to Gessel \cite{Ges84}, while the rest are new.
%
Next, recall that Schubert polynomials mentioned above generalize Schur polynomials
and form a linear basis in the ring of \emph{all} \ts polynomials.  We further generalize \Cref{t:main-classic}. 

\begin{thm}[{\rm polynomial structure constants}{}]\label{t:main-schubert}
In the ring of polynomials $\cc[x_1,\ldots,x_n]$, the following bases have structure
constants in~$\SP:$
\begin{itemize}
         \item monomial slide polynomials \ts $\{\mathfrak{M}_{\al}\}$, and
         \item fundamental slide polynomials \ts $\{\FS_\al\}$.
\end{itemize}
The following bases have structure
constants in~$\GapP:$
    \begin{itemize}
         \item Demazure atoms \ts $\{{\atomrm}_{\al}\}$,
         \item key polynomials \ts $\{\kappa_\al\}$,
         \item Schubert polynomials \ts $\{\mathfrak{S}_{\al}\}$,
         \item Lascoux polynomials \ts $\{\mathfrak{L}_{\al}\}$, and
    \item Grothendieck polynomials \ts $\{\mathfrak{G}_{\al}\}$.
    \end{itemize}
Here we \ts $\al\in \nn^n$ \ts ranges over compositions into $n$ nonnegative parts.
\end{thm}


The result for Schubert polynomials follows from work of Postnikov and Stanley \cite{PS09}.  We reprove this result
in a simpler (but related) way, leading to results
in other cases.


Finally, we consider \defn{plethysm}.  
Let \ts $\pi: \GL(V)\to \GL(W)$ \ts and $\rho: \GL(W)\to \GL(U)$ \ts be polynomial
representations of the general linear group.  One can define $\rho[\pi]:=\rho\circ \pi$
to be the {composition} of these representations.
%
At the level of characters, the composition above corresponds to \emph{plethysm}
of symmetric functions $f_{\mu}$ and $g_{\nu}$ and gives \defn{plethysm coefficients}:
$$
f_{\mu}\ts [\ts g_{\nu}\ts ] \, = \, \sum_{\la} \. a_\la(f_{\mu},g_{\nu}) \. s_\la \quad \text{where} \ \ \ f_{\mu},g_{\nu}\in \La\ts,
$$
and \ts $\La$ \ts is the inverse limit of \ts $\La_n$ \ts in the category of
graded rings.
%
It was shown by Fischer and Ikenmeyer \cite[Section~9]{FI20} that plethysm coefficients
for \ts $s_{\la}[s_\mu]$ \ts are \ts $\GapP$-complete, so they are
in \ts $\GapP$.   We  generalize to those bases listed in \Cref{t:main-classic}.



\begin{thm}[{\rm plethysm coefficients}{}]\label{t:main-plethysm}
Let \ts $\{f_\la\}$ \ts and \ts $\{g_\la\}$ \ts be families of
symmetric polynomials from the following linear bases$:$
\[
\{s_\la\}, \ \ \{m_\la\}, \ \ \{p_\la\}, \ \ \{e_\la\}, \ \ \{h_\la\}\ts.
\]
Then the corresponding plethysm coefficients \ts $a_\la(f_{\mu},g_{\nu})$ \ts are in $\GapP$.
\end{thm}


\smallskip
\subsection{Background and motivation} \label{ss:intro-back}
%

Combinatorial interpretations
reveal structure which is
a shadow of a rich but non-quantitative geometric or algebraic structure.
For example, standard Young tableaux are the leading
terms in a linear basis of irreducible $S_n$ modules.
On a deeper level, they are a byproduct of the \emph{branching rule},
which comes from $S_n$ having a long subgroup chain.


Having a combinatorial interpretation does
wonders for applications.  For example, for LR-coefficients,
these include the \emph{saturation theorem},  an efficient algorithm for
positivity \ts $[c^\la_{\mu\nu}>^?0]$, and various lower and
upper bounds.  Even with combinatorial interpretations
in special cases, remarkable applications follow.
For example, for the Kronecker coefficients, these include unimodality
and $\NP$-hardness of positivity $[g(\la,\mu,\nu)>^?0]$.



Naturally, a signed combinatorial interpretation is inherently less powerful
than an unsigned one.  Yet this is usually the best known tool
to obtain any results.  For the Kronecker coefficients,
the signed combinatorial interpretation mentioned above
gives both a fast algorithm to compute the numbers and
a sharp upper bound in some cases.  



An interesting case study is the Murnaghan--Nakayama (MN) rule for $S_n$
character values $\chi^\la(\mu)$,  defined as a signed sum over certain
rim hook tableaux.  This gives upper bounds for character values, which in turn
implies upper bounds for mixing times of random walks on $S_n$ generated
by conjugacy classes.
For $\mu$ a rectangle,
 rim hook tableaux given by the MN rule have the same sign.
This led to rich developments, including combinatorial
proofs of character orthogonality, applications
in probability, tilings, and LLT polynomials
describing representations of Hecke algebra at roots of unity.



In a different direction, a signed combinatorial interpretation coming from
the \emph{Frobenius formula},
was used to show that deciding positivity \ts $[\chi^\la(\mu)>0]$ \ts
of the character value is $\PH$-hard.  Moreover, the character absolute value has no combinatorial interpretation, unless one believes
 the polynomial hierarchy collapses.



We emphasize that some natural
combinatorial formulas defining the
numbers above are not \ts $\GapP$ \ts formulas.  For example, the
definition of Kronecker coefficients gives:
$$
g(\la,\mu,\nu) \. := \. \<\chi^\la,\chi^\mu \cdot \chi^\nu\> \. = \.
\frac{1}{n!} \.\sum_{\si\in S_n} \chi^\la(\si) \. \chi^\mu(\si)\. \chi^\nu(\si)\ts,
$$
for all \ts $\la,\mu,\nu\vdash n$.  This only shows that \ts $\{g(\la,\mu,\nu)\}$ \ts
are in \ts $\GapFP$.

Indeed, while the summation above is in \ts $\GapP$ \ts via the MN~rule,
the division by~$n!$ is not allowed in~$\GapP$.  The same issue appears also
when applying \emph{Billey's formula} to compute Schubert coefficients,
the \emph{F\'{e}ray--\'{S}niady formula} for the characters,
and Hurwitz's original formula for the \emph{double Hurwitz numbers}.
These formulas involve divisions, thus they only prove the
corresponding integral functions are in \ts $\GapFP$.



There are cases when the integrality was established
algebraically.  For example, the integrality 
\ts $\chi^\la(\mu)\in \zz$, follows from the fact that $\si$ and $\si^a$
are conjugate, for all \ts $\si \in S_n$ \ts and \ts $(a,\ord(\si))=1$.
The proof uses a Galois theoretic
argument and a calculation of cyclotomic polynomials, which cannot
be easily translated to a $\GapP$ formula.  In other words, being in $\GapP$
can be a strong result of independent interest.




\section{Basic definitions and notations} \label{s:notation}

We use $\nn=\{0,1,2,\ldots\}$ and $[n]=\{1,\ldots,n\}$.
To simplify notation,
for a set $X$ and an element $x\in X$, we write \ts $X-x:=X \sm \{x\}$.
Similarly, we write \ts $X+y:=X\cup \{y\}$.

Let \ts $\cP=(X,\prec)$ \ts be a poset on the ground set~$X$ with a partial
order~``$\prec$''. Function \ts $h: X^2\to \rr$ \ts is called
\defn{triangular} \ts w.r.t.~$\cP$ \ts if \ts $h(x,y) = 0$ \ts unless
\ts $x\preccurlyeq y$ \ts for all \ts $x,y\in X$,
and \ts $h(x,x)\ne 0$ \ts for all \ts $x\in X$.
Similarly, function \ts $h: X^2\to \rr$ \ts is called
\defn{unitriangular} \ts w.r.t.~$\cP$ \ts if it is triangular
and \ts $h(x,x)=1$ \ts for all \ts $x\in X$.


Fix~$n$.  An \defn{integer partition} \ts $\la$ of $k$, denoted \ts $\la \vdash k$,
is a sequence of weakly decreasing nonnegative integers \ts
$(\la_1,\ldots,\la_n)$ \ts which sum up to~$k$.  
Let $\rU_n = \cup_k \ts \{\la\in \nn^n \, : \, \la\vdash k\}$.
Similarly a \defn{composition} (sometimes called \emph{weak composition})
\ts $\al$ of $k$, denoted $\al \vDash k$,
is a sequence of nonnegative integers \ts
$(\al_1,\ldots,\al_n)$ \ts which sum up to~$k$.
Let \.  $\vrV_{n,k} \ts :=\{\al\in \nn^n \, : \, \al \vDash k\}$, and \ts let \ts
$\vrV_{n}:=\cup_k \vrV_{n,k}$ \ts be sets of compositions. A \defn{strong composition}
\ts $\al \vDash k$ has all parts strictly positive.
Let \.  $\ComW_{n,k} \ts :=\{\al\in \nn^m_{\geq 1} \, : \, \al \vDash k, \ts  m\leq n\}$, and \ts let \ts
$\ComW_{n}:=\cup_k \ComW_{n,k}$ \ts be sets of strong compositions.
%
Let \ts
$D(\al) : =\{(i,j) \. : \. i\leq \al_j\}$ \ts denote the \defn{diagram} of~$\al$.

We write \ts $|\al| := \al_1+\ldots + \al_n$ \ts the size of the composition,
and \ts $\ell(\al)$ \ts the number of parts in~$\al$.
%
%
For two compositions \ts $\al,\be\vDash k$, the \defn{dominance order} \ts
is defined as follows:
$$\al\unlhd \be \ \ \Longleftrightarrow \ \
\al_1 \ts + \ts \ldots \ts + \ts \al_i \ts \ge \ts \be_1 \ts + \ts \ldots \ts + \ts \be_i  \ \ \text{for all} \ i.
$$


For a permutation \ts $\si\in S_n$\ts, the \defn{Lehmer code} \ts is
a sequence \ts $\bc=(c_1,\ldots,c_n)\in \nn^n$ \ts given by \ts
$c_i(\si) := \#\{j > i : \si_i \ge \si_j\}$.  
%
Denote by \ts $S_{\infty}$ \ts the set of bijections \ts $w:\nn_{\ge 1} \to \nn_{\ge 1}$ \ts
which eventually stabilize: \ts $w(m)=m$ \ts for $m$ large enough.  


The \defn{Young diagram} \ts of shape \ts $\la$, denoted \ts $[\la]$,
is $D(\lambda)$.
A \defn{semistandard Young tableau} \ts of shape~$\la$ is a
map \ts $A: [\la] \to \nn$, which is weakly increasing in rows: \ts $A(i,j) \le A(i,j+1)$ \ts
and strictly increasing in columns: \ts $A(i,j) < A(i+1,j)$.  The \defn{content} of~$A$
is a sequence \ts $(m_1,m_2,\ldots)$, where $m_k$ is the number of $k$ in the multiset~$\{A(i,j)\}$.
Let \ts $\SSYT(\la,\mu)$ \ts denote the set of semistandard Young tableaux of shape $\la$
and content~$\mu$.



\section{Effective M\"obius inversion} \label{s:basic}

Let \. $X =\cup X_n$, where \. $X_n \subseteq \{0,1\}^n$, be a family of combinatorial
objects. Let \. $\cP:=(X,\prec)$ \.  be a poset such that \ts $x \prec y$ \ts only if
\ts $x,y\in X_n$ \ts for some~$n$.  We use \ts $\cP_n=(X_n,\prec)$ \ts to denote a subposet of~$\cP$.
%
The \defn{height} \ts of a poset $\cQ$, denoted \ts $\height(\cQ)$, is the size of the maximal chain in~$\cQ_n$\ts.  Then $\cP$ has \defn{polynomial height}
if \ts $\height(\cP_n)\le C \ts n^c$, for some fixed \ts $C, c>0$.

Let \ts $\de: X^2\to \{0,1\}$ \ts be the \defn{delta function} \ts defined as \ts
$\de(x,y) =1$ \ts if \ts $x=y$, and \ts $\de(x,y) =0$ \ts otherwise.
Let \ts $\xi: X^2\to \{0,1\}$ \ts be the \defn{incidence function} \ts
defined as \ts $\xi(x,y) =1$ \ts if \ts $x\preccurlyeq y$ \ts and \ts
$\xi(x,y) =0$ \ts otherwise.  Then $\xi$ is \defn{poly-time computable}, if for all \ts
$x,y\in X_n$ \ts the decision problem \ts $[x\preccurlyeq ^? y]$ \ts can be decided in \ts $O(n^c)$ \ts
time, for some fixed \ts $c>0$.

The \defn{M\"obius inverse} \ts is a function \ts $\mu(x,y): X^2 \to \zz$, such that
$$
\sum_{z\in X_n} \. \xi(x,z) \cdot \mu(z,y) \, = \, \de(x,y) \quad
\text{for all} \quad x,y\in X_n\..
$$

\begin{prop} \label{p:mu}
Let \. $\cP:=(X,\prec)$ \.  be a poset with polynomial height, and
suppose that the incidence function~$\xi$ is poly-time computable.
Then the M\"obius inverse function \. $\mu$ \. is in \ts $\GapP$.
\end{prop}



Let \ts $\eta: X^2 \to \zz$ \ts be unitriangular w.r.t.\ $\cP$, i.e.,\  \ts $\eta(x,x)=1$ \ts for all \ts
$x\in X$, and \ts $\eta(x,y)\ne 0$ \ts implies \ts $x\preccurlyeq y$ \ts and \ts $x,y\in X_n$ \ts
for some~$n$.
The \defn{inverse} \ts of~$\eta$ (in the incidence algebra),
is a function \ts $\rho(x,y): X^2 \to \zz$, such that
$$
\sum_{z\in X_n} \. \eta(x,z) \cdot \rho(z,y) \, = \, \de(x,y) \quad
\text{for all} \quad x,y\in X_n\..
$$

\begin{prop} \label{p:rho}
Let \. $\cP:=(X,\prec)$ \.  be a poset with polynomial height, and
suppose that the incidence function~$\xi$ is poly-time computable.
Suppose function \ts $\eta$ \ts is in \ts $\GapP$.  Then the inverse
function \ts of~$\eta$ \ts is also in \ts $\GapP$.
\end{prop}
 Combining this with (uni)triangularity of the given bases yields our main results.



\section{Symmetric polynomials}\label{s:sym}
%
Let \ts $\La_n=\cc[x_1,\ldots,x_n]^{S_n}$ \ts be the ring of symmetric polynomials. See \cite{Mac95} for background on bases $\{p_\la\}$, \ts $\{e_\la\}$\ts,  \ts $\{h_\la\}$\ts, and $\{m_\la\}$.
Denote by \ts $\cq_m$ \ts the poset on partitions \ts $\la \vdash m$ \ts with
dominance order \. $\la \unlhd \mu$, for \ts $\la,\mu \vdash m$.   It is known
that the dominance order is a lattice.
%
Clearly, \. $\height(\cq_m)=O(m^2)$.  




\subsection{Structure constants} \label{ss:sym-structure-const}
%
Recall \defn{Schur polynomials} \. $\{s_\la\.:\. \la\in \rU_n\}$ \. can be defined as
\[
s_{\la}(x_1,\ldots,x_n) \, := \, \sum_{\mu} \. K_{\la\mu}\. m_{\mu}(x_1,\ldots,x_n),
\]
where the \defn{Kostka numbers} \ts $K_{\la\mu}$ \ts
compute the number of semistandard Young tableaux of shape~$\la$ and content~$\mu$.
The
\defn{Littlewood--Richardson coefficients} \ts $c^\la_{\mu\nu}$ \ts are
defined by
\[
s_\mu \cdot s_\nu \, = \, \sum_{\la} \. c^\la_{\mu\nu} \. s_\la\..
\]
Recall that \ts $c^\la_{\mu\nu}$ \ts are given as the number
of LR-tableaux of shape $\nu/\la$ with content $\mu$, a subset of semistandard
Young tableaux, see e.g.\ \cite{Mac95}. \Cref{t:main-classic} follows by the definitions of $\{p_\la\}$, \ts $\{e_\la\}$\ts,  \ts $\{h_\la\}$, and $\{m_\la\}$ along with the LR rule for $\{s_\la\}$.



\subsection{\texorpdfstring{\texorpdfstring{$(q,t)$}{q,t}}{(q,t)} deformations} \label{ss:sym-qt}
%
%
Following \cite{Mac88}, \defn{Macdonald symmetric polynomials} \ts
$P_{\la}$ \ts can be defined combinatorially:
\[
P_{\la}(\bx;q,t) \, := \, \sum_{\mu} \. m_{\mu}(\bx) \.
\sum_{T\ts \in \ts \SSYT(\la,\mu)} \. \psi_T(q,t)\ts,
\]
where \ts $\bx = (x_1,\ldots,x_n)$ \ts and
\ts $\psi_T(q,t)$ \ts is a explicit rational function given by
a product formula.  For fixed \ts $q,t\in \qqq$ \ts such that
\ts $0\le q, t < 1$, this function \ts $\psi: T \to \qqq$ \ts is in \ts $\FP/\FP$.

The \defn{Hall--Littlewood polynomials} \. $P_{\la}(\bx;t)$ are defined as $P_{\la}(\bx;0,t)$, see \cite{Lit61}.
%
Similarly, the \defn{Jack symmetric polynomials} \. $P_{\la}(\bx;\al)$,
see \cite{Jac70}, specialize Macdonald symmetric polynomials in another direction, $
P_{\la}(\bx;\al) \. := \. \lim_{t\rightarrow 1}P_{\la}(\bx;t^\al,t)
$.

By the definition above and the explicit form of \ts $\psi_T$,  Macdonald symmetric polynomials are unitriangular in $m_\mu(\bx)$, see  \cite[Theorem~2.3]{Mac95}.
Using \Cref{p:rho} we obtain
the $\GapP$ result.
By the specialization to Hall--Littlewood polynomials and Jack polynomials,
we obtain \Cref{t:main-qt}. 




\subsection{\texorpdfstring{\texorpdfstring{$(q,t)$}{q,t}}{(q,t)} analogues} \label{ss:sym-qt-analogues}
%
One can also view $(q,t)$ as variables and
extend \Cref{t:main-qt}.  For Hall--Littlewood polynomials
\ts $P_{\la}(\bx;t)\in \La[t]$, the corresponding
Kostka polynomials \ts $K_{\la,\mu}(t)\in \nn[t]$ \ts are the coefficients
of their Schur expansion.  They have a known combinatorial
interpretation by Lascoux and Sch\"utzenberger (see e.g.\ \cite[Section~III.6]{Mac95}).
Using the LR rule, we have:

\begin{prop}\label{prop:q-analogues}
Hall--Littlewood polynomials \ts $\{P_{\la}(t)\}$ \ts
have structure constants in \ts $\SP$.
\end{prop}

Here structure constants form the polynomials \ts $c^\la_{\mu\nu}(t)\in \nn[t]$.
The proposition states there is a \ts $\SP$ \ts function \. $f: \{(\la,\mu,k)\} \to \nn$, such that $c^\la_{\mu\nu}(t) \, = \, \sum_{k\in \nn} \. f(\la,\mu,k,\ell) \. t^k$.


Recall the \emph{modified Macdonald polynomials}
\. $\wt H_{\mu}(\bx;q,t)\in \La[q,t]$,
see e.g.\ \cite[Theorem~2.8]{Hag08}.  They are defined so that the corresponding
\defn{$(q,t)$-Kostka polynomials} \.
$\widetilde{K}_{\la\mu}(q,t)\in \nn[q,t]$ \ts become the coefficients
of their expansion in Schur polynomials. The problem of finding a combinatorial interpretation for the $(q,t)$-Kostka polynomials remains open

On the other hand, a \emph{signed}
\ts combinatorial interpretation of \ts $\widetilde{K}_{\la\mu}(q,t)\in \nn[q,t]$ \ts
follows immediately from \emph{Haglund's monomial formula} \ts
\cite[Appendix~A]{Hag08}, giving a combinatorial interpretation for coefficients
of their expansion in Schur functions, combined with a \ts $\GapP$ \ts formula
for the (usual) inverse Kostka numbers.
%
%
Using the LR rule again, we conclude:

\begin{prop}\label{prop:qt-analogues}
Modified Macdonald polynomials \ts $\{\wt H_{\mu}(q,t)\}$ \ts have structure constants in \ts $\GapP$.
\end{prop}




\section{Quasisymmetric bases}\label{s:qsym}

\subsection{Posets of interest}\label{ss:qsym-posets}
%
Denote by \ts $\mathcal{Z}_{n,k}=(\ComW_{n,k},\lhd)$ \ts  the poset on strong compositions w.r.t.\ the
dominance order. Let \ts $\cZ_{n}=\cup_k\cZ_{n,k}$.
Clearly, we have \ts $\height(\cZ_{n,k})= O(kn)$.

For $\al\in \nn^m$, define ${\sf{sort}}(\al)$ as the partition formed by listing $\al$ in weakly decreasing order.
For $\al,\be\in \ComW_{n,k}$ we say $\be$ is a \defn{refinement} of $\al$ if one can obtain $\al$ by adding consecutive parts of $\be$. 
This defines the \defn{refinement order} \ts ``$\preccurlyeq$'' \ts on \ts $\ComW_{n,k}$\ts.
%
Denote by \ts $\cD_{n,k}=(\ComW_{n,k},\unlhd')$ \ts the poset on \ts $\ComW_{n,k}$ \ts where
$$\al\unlhd'\be\., \al,\be\in \ComW_{n,k} \quad \Longleftrightarrow \quad \left\{
\aligned
& {\sf sort}(\be)\lhd {\sf sort}(\al) \ \ \text{if} \ \ {\sf sort}(\be) \ne {\sf sort}(\al), \\
&  \be\unlhd\al \ \ \text{if} \ \ {\sf sort}(\be)= {\sf sort}(\al).
\endaligned
\right.
$$
Observe that \. $\height\big(\cD_{n,k}\big)=O(kn^3)$.


\subsection{Quasisymmetric bases} \label{ss:qsym-int-bases}
%
Let \ts $\QSym_n\subseteq\cc[x_1,\ldots,x_n]$ \ts be the ring of quasisymmetric
polynomials in $n$ variables. The \defn{monomial quasisymmetric polynomials}
\ts $\{M_\al\. : \. \al \in \ComW_{n}\}$ \ts are defined as
\[
M_\al(x_1,\ldots,x_n) \, := \, \sum_{1\ts \le \ts i_1 \ts < \ts \ldots \ts < \ts i_\ell \ts \le \ts n}
x_{i_1}^{\al_1} \. \cdots \. x_{i_\ell}^{\al_\ell}\.,
\]
where  \ts $\ell =\ell(\al) \le n$.
Clearly, \ts $\{M_\al\}_{\al \in \ComW_{n}}$ \ts is a linear basis in \ts $\QSym_n$.

Following \cite{Ges84}, the \defn{fundamental quasisymmetric polynomials} \.
$\{F_{\al} \. : \. \al\in \ComW_{n}\}$ \ts are given by
\[
F_{\al}(x_1,x_2,\ldots,x_n)\, := \, \sum_{\be\ts\preccurlyeq\ts\al} \. M_{\be}(x_1,x_2,\ldots,x_n).
\]
The \defn{dual immaculate polynomials} \.
$\{\Sc_\al^* \. : \. \al\in \ComW_{n}\}$ \ts can be defined by
\begin{equation*}\label{eq:dualimExp}
    \Sc_\al^*(x_1,x_2,\ldots,x_n) \, := \, \sum_{\be}K_{\al,\be}^I \. M_\be(x_1,x_2,\ldots,x_n),
\end{equation*}
where \ts $K_{\al,\be}^I$ \ts counts certain fillings of  \ts
$D(\al)$ \ts with content $\be$, see \cite{BBSSZ14}.

The \defn{quasisymmetric Schur polynomials} \.
$\{\mathcal{S}_\al\. : \. \al\in \ComW_{n}\}$ \ts can be defined by
\begin{equation*}\label{eq:qschExp}
    {\mathcal{S}_\al}(x_1,x_2,\ldots,x_n) \, := \, \sum_{\be}K_{\al,\be}^S \. M_\be(x_1,x_2,\ldots,x_n),
\end{equation*}
where \ts $K_{\al,\be}^S$ \ts counts particular fillings of $D(\al)$ with content $\be$, as defined in \cite{HLMvW11}.



By their definition,
\ts $\{F_{\al}\}_{\al \in \ComW_{n}}$ \ts are unitriangular w.r.t.\
the dominance order.
 The unitriangular property for $\{\Sc_\al^*\}_{\al \in \ComW_{n}}$ and $\{\mathcal{S}_\al\}_{\al \in \ComW_{n}}$ follows by examining the combinatorial objects computing their corresponding Kostka coefficients. Then the results in \Cref{t:main-quasi} follow from this unitriangular property combined with \Cref{p:rho}.




\begin{rem} \label{rem:quasi-signs}
%
Structure constants for dual immaculate
and quasisymmetric Schur polynomials can be negative.  Thus,
\Cref{t:main-quasi} is optimal.
\end{rem}

For brevity, we exclude the details for the {combinatorial quasisymmetric power sums} \ts
$\{\mathfrak{p}_\al\. : \. \al \in \ComW_{n}\}$ ~\cite{AWvW23}, as well as the {type 1 quasisymmetric power sums} \.
$\{\Psi_\al\. : \. \al \in \ComW_{n}\}$ and {type 2 quasisymmetric power sums} \.
$\{\Phi_\al\. : \. \al \in \ComW_{n}\}$ \cite{BDHMN20}.



\section{Polynomial bases}\label{s:poly}

\subsection{Posets of interest}\label{ss:poly-posets}
For \ts $k\in\zz_{>0}$, 
denote by \ts $\mathcal{I}_{n,k}=(\vrV_{n,k},\lhd)$ \ts the poset on weak compositions
w.r.t. dominance order. 
Clearly, \ts $\height(\mathcal{I}_{n,k})=O(kn)$.
%
Let \ts $\mathcal{I}_{n}=\cup_k \mathcal{I}_{n,k}$.
Thus \ts $\height(\mathcal{I}_{n})=O(n^3)$.




\subsection{Polynomial bases}
%
For $\al\in \vrV_{n}$, let ${\rm flat}(\al)$ be the strong composition formed
by removing \ts $0$'s \ts in~$\al$.  Following \cite[Section~3.4]{Hiv00},
the \defn{monomial slide polynomials} \. $\{\mathfrak{M}_{\al} \. : \. \al\in\vrV_{n}\}$ \.
and the \defn{fundamental slide polynomials} \. $\{\FS_{\al} \. : \. \al\in\vrV_{n}\}$ \.
are defined as
\[
  \mathfrak{M}_{\al}(\bx) \, := \, \sum_{\substack{\be\ts \unlhd \ts \al \\ {\rm flat}(\be) \ts = \ts {\rm flat}(\al)}} \bx^\be
  \qquad\text{and} \qquad
\FS_{\al}(\bx) \, := \, \sum_{\substack{\be\ts \unlhd \ts \al \\ {\rm flat}(\be)\ts \preccurlyeq\ts {\rm flat}(\al)}}\bx^\be\..
  \]


The \defn{Demazure atoms}
\. $\{{\atom}_{\al}\. : \. \al\in\vrV_{n}\}$ \ts can be defined as ${\atom}_{\al}(\bx) \, := \, \sum_{\be}\. K_{\al,\be}^\atom \.\bx^\be$.
Here \. $K_{\al,\be}^\atom$ \. counts particular fillings of $T: D(\al)\to \nn_{\ge 1}$, see \cite{Mas09}.
 The \defn{key polynomials} \. $\{\kappa_\al\. : \. \al\in\vrV_{n}\}$ \.
 and \defn{Lascoux polynomials} $\{\mathcal{L}_\al\. : \. \al\in\vrV_{n}\}$
can be computed as
\[\kappa_\al(\bx)  \, := \, \sum_{S\ts\in\ts{\sf Koh}(D(\al))} \. \bx^{\wtx(S)} \text{\ \ \ and \ \ \ } \mathcal{L}_\al(\bx)  \, := \, \sum_{S\ts\in\ts{\sf KKoh}(D(\al))}(-1)^{|\al|-\#S}\. \bx^{\wtx(S)}.\]
Here ${\sf Koh}(D(\al))$ and ${\sf KKoh}(D(\al))$ are recursively generated diagrams, see \cite{Koh91} and \cite{PY23}, respectively.


Let \ts $D\subset[n]\times[n]$ \ts be a diagram and let \ts $(i,j)\in D$ \ts be a box in the diagram.
The \defn{ladder move} \ts is a transformation \ts $D\ts \to \ts  D-(i,j)+(i-k,j+1)$ \ts and the
\defn{K-ladder move} \ts  is a transformation \ts   $D \ts \to \ts D + (i-k,j+1)$, allowed only
when the following are satisfied:
\begin{itemize}
    \item \ts $(i,j+1)\not\in D$,
    \item \ts $(i-k,j),(i-k,j+1)\not\in D$ \. for some \. $0<k<i$, and
    \item \ts $(i-l,j),(i-l,j+1)\in D$ \. for all \. $0<l<k$.
\end{itemize}

Recall that the \defn{Lehmer code} \. $\code(w) \in \nn^n$ \ts uniquely
determines \ts $w\in S_{\infty}$.
Let ${\sf rPipes}(w)$ denote the set of diagrams obtainable through successive ladder moves, starting from $D(\code(w))$, where $w\in S_n$.
Similarly take ${\sf Pipes}(w)$ to be the set of diagrams obtainable through successive ladder and K-ladder moves, starting from $D(\code(w))$, where $w\in S_n$.


Using \cite{BB93} and \cite{FK94}, the  \defn{Schubert polynomials} \ts $\{\mathfrak{S}_{w} \. : \. w\in S_n\}$ and \defn{Grothendieck polynomials} \ts
$\{{\text{$\mathfrak{G}$}}_{w} \. : \. w\in S_n\}$ can be defined as
\[
{\text{$\mathfrak{S}$}}_{w}(\bx) \, : = \, \sum_{P\ts \in \ts {\sf rPipes}(w)} \. \bx^{\wtx(P)} \text{ \ \ \ and \ \ \ } {\text{$\mathfrak{G}$}}_{w}(\bx) \, = \, \sum_{P\in{\sf Pipes}(w)} \. (-1)^{|\al|\ts - \ts \#P} \. \bx^{\wtx(P)}.
\]
 Since $\code(w)$ uniquely determines $w$, we write
$\mathfrak{S}_{\al}:=\mathfrak{S}_{\code^{-1}(\al)}$ and $\mathfrak{G}_{\al}:=\mathfrak{G}_{\code^{-1}(\al)}$.


\Cref{t:main-schubert} follows from \Cref{p:rho}
with the fact that each basis is unitriangular.




\begin{rem}
The poset of monomials is also unitriangular w.r.t.\ the reverse lexicographic order, so
the M\"obius inversion can also be used in this setting.  However, the height
of the resulting poset is exponential, so \Cref{p:rho} is not applicable.
\end{rem}





\begin{rem}\label{rem:Schubert-signs}
%
It is easy to see that the structure constants for Demazure atoms,
key, and Lascoux polynomials can be negative without predictable signs.
Thus,  \Cref{t:main-quasi} proving their signed combinatorial
interpretation is optimal in this case.  
\end{rem}



\section{Plethysm and further applications} \label{s:app}
The proof of \Cref{t:main-plethysm} follows by the inverse Kostka formula once we show that the coefficients in the corresponding monomial expansion
are in $\GapP$. This follows by 
extending the argument in \cite[Section~9]{FI20}.



We conclude with one additional application relating structure
constants.

\begin{thm}\label{t:main-symQsymCOB}
Let \ts $A=\cup A_n$ \ts be a family of combinatorial objects, and let
\ts $\{G_w(\bx) \. : \. w\in A\}$ \ts be a family of symmetric polynomials
such that $G_w(\bx) \. = \. \sum_{\al\ts\in \ts \vrV_n} \. c_{w\al} \ts F_{\al}(\bx)\ts$
where the coefficients \ts $\{c_{w\al}\}$ \ts are in $\GapP$.
Consider the coefficients defined by
% $$
$G_w(\bx) \. = \. \sum_{\la\ts\in \ts \rU_n} \. d_{w\la} \ts s_{\la}(\bx)\ts$.
% $$
Then \ts $\{d_{w\la}\}$ \ts are also in $\GapP$.  Furthermore, the result holds
when the \ts $F_{\al}$ \ts are replaced with \ts $M_\al$.
\end{thm}




\begin{rem}\label{rem:LLT}
Combining \Cref{t:main-symQsymCOB} with \cite[Equation~(82)]{HHL05} gives a \ts $\GapP$ \ts
formula for the Schur expansion of \emph{LLT polynomials}. While this expansion is proven to be Schur-positive, there is no known (unsigned) combinatorial interpretation.
\end{rem}





\acknowledgements{We are grateful to Jim Haglund, Christian Ikenmeyer, Nick Loehr,
and Alex Yong for interesting discussions and helpful remarks.
Special thanks to Darij Grinberg and Vasu Tewari for
careful reading of the paper and useful comments, and to Greta Panova
for suggesting \Cref{t:main-symQsymCOB}. We thank the anonymous referees for their helpful remarks. 
}

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