\documentclass[numbers=enddot,14pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage[breaklinks=true]{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{color}
\usepackage{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, November 22, 2024 06:52:35}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows}
\usetikzlibrary{arrows.meta}
\usetikzlibrary{decorations.markings}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newcommand{\arinj}{\ar@{_{(}->}}
\newcommand{\arinjrev}{\ar@{^{(}->}}
\newcommand{\arsurj}{\ar@{->>}}
\newcommand{\arelem}{\ar@{|->}}
\newcommand{\arback}{\ar@{<-}}
\newcommand{\id}{\operatorname{id}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\DeclareMathOperator{\osc}{OSC}
\DeclareMathOperator{\rtb}{R2B}
\DeclareMathOperator{\uosc}{UOSC}
\newcommand{\red}[1]{\textcolor{red}{#1}}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
\newcommand{\green}[1]{\textcolor{green!50!black}{#1}}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{\node[shape=circle,fill,inner sep=2pt] (char) {\textcolor{white}{#1}};}}
\newcommand{\icast}{\circled{$\ast$}}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\tikzset{->-/.style={decoration={
markings,
mark=at position .5 with {\arrow{>}}},postaction={decorate}}}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{25cm}
\setlength\textwidth{15.5cm}
\newenvironment{noncompile}{}{}
\excludecomment{noncompile}
\ihead{Monomial identities in the Weyl algebra (talk)}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{Monomial identities in the Weyl algebra [talk slides]}
\date{CAP 2024, 2024-11-22}
\author{Darij Grinberg
\and joint work with Tom Roby, Stephan Wagner, Mei Yin
\and inspired by a question of Richard P. Stanley}
\maketitle

\begin{abstract}
{\small \textbf{Abstract.} The \emph{Weyl algebra} (or \emph{Heisenberg-Weyl
algebra}) is the free algebra with two generators $D$ and $U$ and single
relation $DU-UD=1$. As a consequence of this relation, certain monomials are
equal, such as $DUUD$ and $UDDU$. We characterize all such equalities over a
field of characteristic $0$, describing them in several ways: operational (by
a combinatorial equivalence relation generated by certain moves),
computational (through lattice path invariants) and in terms of rook theory.
We also enumerate the equivalence classes and several variants thereof and
discuss possible extensions to other algebras.}

\end{abstract}

\section*{***}

\textbf{Preprint:}

\begin{itemize}
\item \href{https://arxiv.org/abs/2405.20492}{Darij Grinberg, Tom Roby,
Stephan Wagner, Mei Yin, \textit{Monomial identities in the Weyl algebra},
arXiv:2405.20492,}
\end{itemize}

\bigskip

\noindent\textbf{Slides of this talk:}

\begin{itemize}
\item \url{https://www.cip.ifi.lmu.de/~grinberg/algebra/cap2024.pdf}
\end{itemize}

\noindent Items marked with $\circled{$\ast$}$ contain definitions/notations/terminology.

\newpage

\section{The Weyl algebra}

\begin{itemize}
\item[$\circled{$\ast$}$] Let $\mathbf{k}$ be a field of characteristic $0$.

\item[$\circled{$\ast$}$] Let $\mathcal{M}$ be the free monoid with generators
$D$ and $U$. It consists of words with entries in $\left\{  D,U\right\}  $,
such as $DUDDUUUD$.

\item[$\circled{$\ast$}$] Let $\mathcal{W}$ be the Weyl algebra over
$\mathbf{k}$ with generators $D$ and $U$ and relation $DU-UD=1$.

\item[$\circled{$\ast$}$] The Weyl algebra $\mathcal{W}$ acts on the
polynomial $\mathbf{k}\left[  x\right]  $ by $D\mapsto\dfrac{d}{dx}$ and
$U\mapsto x$. This action is faithful (since $\operatorname*{char}%
\mathbf{k}=0$).

\item[$\circled{$\ast$}$] There is a canonical monoid morphism $\phi
:\mathcal{M}\rightarrow\mathcal{W}$ sending $D,U$ to $D,U$.

\item[$\circled{$\ast$}$] Say that two words $u$ and $v$ in $\mathcal{M}$ are
$\phi$\textbf{-equivalent} if $\phi\left(  u\right)  =\phi\left(  v\right)  $
in $\mathcal{W}$.

\item[$\circled{$\ast$}$] \textbf{Questions to be discussed} (posed by Richard
P. Stanley)\textbf{:}

\begin{enumerate}
\item When are two words $\phi$-equivalent, in combinatorial terms?

\item How efficiently can we test $\phi$-equivalence?

\item How many $\phi$-equivalence classes are there, and how large are they?

\item What is a minimal class of relations that generate $\phi$-equivalence?

\item What holds in other algebras or for other $\operatorname*{char}%
\mathbf{k}$ ?
\end{enumerate}

\item We shall answer 1, 2, 3 fully and 4, 5 partly.
\end{itemize}

\newpage

\section{Words and paths}

\subsection{Definitions}

\begin{itemize}
\item[$\circled{$\ast$}$] A \textbf{word} means a finite tuple of $D$'s and
$U$'s. Thus, $\mathcal{M}$ is the set of all words.

\item[$\circled{$\ast$}$] A word $u$ is called a \textbf{prefix},
\textbf{suffix} or \textbf{factor} of a word $w$ if and only if $w=uq$ or
$w=pu$ or $w=puq$ (respectively) for some words $p$ and $q$. These $p$ and $q$
can be empty.

\item[$\circled{$\ast$}$] We encode words as \textbf{diagonal paths} (short:
\textbf{paths}) on the plane, by reading each $D$ as a step to the southeast
(\textquotedblleft\textbf{down}step\textquotedblright) and each $U$ as a step
to the northeast (\textquotedblleft\textbf{up}step\textquotedblright). For
example, the word $UDUUDDD$ gives rise to the path
\[
\begin{tikzpicture}
\draw[help lines] (-0.2, -1.2) grid (7.2, 2.2);
\draw
[line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 0) (2, 0) edge (3, 1) (3, 1) edge (4, 2) (4, 2) edge (5, 1) (5, 1) edge (6, 0) -- (7, -1);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {\textcolor{blue}{$\left(0, 0\right)\ $}};
\draw[fill=blue] (7, -1) circle (0.1) node[right] {\textcolor{blue}{$\ \left(7, -1\right)$}};
\end{tikzpicture}\ .
\]


This is a many-to-1 correspondence, as the starting point can be chosen
freely. The \textbf{standard path} of a word $w$ is the corresponding diagonal
path starting at $\left(  0,0\right)  $.

The word corresponding to a given path $\mathbf{p}$ is denoted
$\operatorname*{w}\left(  \mathbf{p}\right)  $, and is called the
\textbf{reading word} of $\mathbf{p}$.

\item[$\circled{$\ast$}$] A word is \textbf{balanced} if it has equally many
$U$'s and $D$'s.

\item[$\circled{$\ast$}$] If $\mathbf{p}=\left(  p_{0},p_{1},\ldots
,p_{k}\right)  $ is a path, then

\begin{itemize}
\item the \textbf{vertices} of $\mathbf{p}$ are $p_{0},p_{1},\ldots,p_{k}$;

\item the \textbf{NE-steps} of $\mathbf{p}$ are the vertices $p_{i}$ of
$\mathbf{p}$ with $p_{i}\nearrow p_{i+1}$;

\item the \textbf{SE-steps} of $\mathbf{p}$ are the vertices $p_{i}$ of
$\mathbf{p}$ with $p_{i}\searrow p_{i+1}$.
\end{itemize}

For example, the above picture shows a path $\mathbf{p}=\left(  p_{0}%
,p_{1},\ldots,p_{7}\right)  $ with $p_{0}\nearrow p_{1}\searrow p_{2}\nearrow
p_{3}\nearrow p_{4}\searrow p_{5}\searrow p_{6}\searrow p_{7}$.
\end{itemize}

\subsection{The $\omega$ involutions}

\begin{itemize}
\item[$\circled{$\ast$}$] Let $\omega:\mathcal{M}\rightarrow\mathcal{M}$ be
the map that reads a word right-to-left and also changes each letter to the
other possible letter ($D\mapsto U$ and $U\mapsto D$).

Formally, $\omega$ is a monoid anti-automorphism.

\item Pictorially, $\omega$ is reflection across a vertical axis:%
\[%
%TCIMACRO{\TeXButton{tikzpicture[scale=0.5]}{\begin{tikzpicture}[scale=0.5]
%\draw
%[fill=blue] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (14,0) -- (5,1);
%\draw
%[line width=2pt] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (14,0);
%\draw[fill=blue] (5, 1) circle (0.1) node[left] {};
%\draw[fill=blue] (14, 0) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw
[fill=blue] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (14,0) -- (5,1);
\draw
[line width=2pt] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (14,0);
\draw[fill=blue] (5, 1) circle (0.1) node[left] {};
\draw[fill=blue] (14, 0) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
\overset{\omega}{\mapsto}%
%TCIMACRO{\TeXButton{tikzpicture[scale=0.5]}{\begin{tikzpicture}%
%[xscale=-1, scale=0.5]
%\draw
%[fill=blue] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (14,0) -- (5,1);
%\draw
%[line width=2pt] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (14,0);
%\draw[fill=blue] (5, 1) circle (0.1) node[left] {};
%\draw[fill=blue] (14, 0) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[xscale=-1, scale=0.5]
\draw
[fill=blue] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (14,0) -- (5,1);
\draw
[line width=2pt] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (14,0);
\draw[fill=blue] (5, 1) circle (0.1) node[left] {};
\draw[fill=blue] (14, 0) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
\]


\item[$\circled{$\ast$}$] Likewise, let $\omega:\mathcal{W}\rightarrow
\mathcal{W}$ be the algebra anti-automorphism sending $D\mapsto U$ and
$U\mapsto D$.
\end{itemize}

\subsection{Balanced commutations and flips}

\begin{itemize}
\item[$\circled{$\ast$}$] \textbf{Balanced commutations} and \textbf{balanced
flips} are two ways to transform a word $v$ into another word $w$.

\item[$\circled{$\ast$}$] In a \textbf{balanced commutation}, we write our
word $v$ as $v=pxyq$ with two balanced factors $x$ and $y$, and we set
$w:=pyxq$.

\item[$\circled{$\ast$}$] In a \textbf{balanced flip}, we write our word $v$
as $v=pxq$ with a balanced factor $x$, and we set $w:=p\omega\left(  x\right)
q$.

\item Both operations can be applicable to a word in many different ways.

\item \textbf{Example:}%
\[%
\begin{tabular}
[c]{ccc}%
\textbf{word} &  & \textbf{standard path}\\\hline
$%
\begin{array}
[c]{c}%
U\underline{UUUDDUDD}\overline{DDUU}DD\\
\vphantom{\int}\\
\vphantom{\int}
\end{array}
$ &  & $%
%TCIMACRO{\TeXButton{tikzpicture[scale=0.5]}{\begin{tikzpicture}[scale=0.5]
%\draw
%[fill=blue] (1,1) -- (2,2) -- (3,3) -- (4,4) -- (5,3) -- (6,2) -- (7,3) -- (8,2) -- (9,1) -- (1,1);
%\draw[fill=yellow] (9,1) -- (10,0) -- (11,-1) -- (12,0) -- (13,1) -- (9,1);
%\draw[help lines] (-0.2, -1.2) grid (15.2, 4.2);
%\draw[line width=2pt] (0, 0) -- (1,1);
%\draw
%[line width=2pt] (1,1) -- (2,2) -- (3,3) -- (4,4) -- (5,3) -- (6,2) -- (7,3) -- (8,2) -- (9,1);
%\draw[line width=2pt] (9,1) -- (10,0) -- (11,-1) -- (12,0) -- (13,1);
%\draw[line width=2pt] (13,1) -- (14,0) -- (15,-1);
%\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
%\draw[fill=blue] (15, -1) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw
[fill=blue] (1,1) -- (2,2) -- (3,3) -- (4,4) -- (5,3) -- (6,2) -- (7,3) -- (8,2) -- (9,1) -- (1,1);
\draw[fill=yellow] (9,1) -- (10,0) -- (11,-1) -- (12,0) -- (13,1) -- (9,1);
\draw[help lines] (-0.2, -1.2) grid (15.2, 4.2);
\draw[line width=2pt] (0, 0) -- (1,1);
\draw
[line width=2pt] (1,1) -- (2,2) -- (3,3) -- (4,4) -- (5,3) -- (6,2) -- (7,3) -- (8,2) -- (9,1);
\draw[line width=2pt] (9,1) -- (10,0) -- (11,-1) -- (12,0) -- (13,1);
\draw[line width=2pt] (13,1) -- (14,0) -- (15,-1);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
\draw[fill=blue] (15, -1) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
$\\
balanced commutation & $\downarrow$ & balanced commutation\\
$%
\begin{array}
[c]{c}%
UDDUU\underline{UUUDDUDD}DD\\
\vphantom{\int}\\
\vphantom{\int}
\end{array}
$ &  & $%
%TCIMACRO{\TeXButton{tikzpicture[scale=0.5]}{\begin{tikzpicture}[scale=0.5]
%\draw
%[fill=blue] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (5,1);
%\draw[fill=yellow] (1,1) -- (2,0) -- (3,-1) -- (4,0) -- (5,1) -- (1,1);
%\draw[help lines] (-0.2, -1.2) grid (15.2, 4.2);
%\draw[line width=2pt] (0, 0) -- (1,1);
%\draw
%[line width=2pt] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1);
%\draw[line width=2pt] (1,1) -- (2,0) -- (3,-1) -- (4,0) -- (5,1);
%\draw[line width=2pt] (13,1) -- (14,0) -- (15,-1);
%\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
%\draw[fill=blue] (15, -1) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw
[fill=blue] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1) -- (5,1);
\draw[fill=yellow] (1,1) -- (2,0) -- (3,-1) -- (4,0) -- (5,1) -- (1,1);
\draw[help lines] (-0.2, -1.2) grid (15.2, 4.2);
\draw[line width=2pt] (0, 0) -- (1,1);
\draw
[line width=2pt] (5,1) -- (6,2) -- (7,3) -- (8,4) -- (9,3) -- (10,2) -- (11,3) -- (12,2) -- (13,1);
\draw[line width=2pt] (1,1) -- (2,0) -- (3,-1) -- (4,0) -- (5,1);
\draw[line width=2pt] (13,1) -- (14,0) -- (15,-1);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
\draw[fill=blue] (15, -1) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
$\\
balanced flip & $\downarrow$ & balanced flip\\
$%
\begin{array}
[c]{c}%
UDDUUUUUDDUDDDD\\
\vphantom{\int}\\
\vphantom{\int}
\end{array}
$ &  & $%
%TCIMACRO{\TeXButton{tikzpicture[scale=0.5]}{\begin{tikzpicture}[scale=0.5]
%\draw
%[fill=blue] (5,1) -- (6,2) -- (7,3) -- (8,2) -- (9,3) -- (10,4) -- (11,3) -- (12,2) -- (13,1) -- (5,1);
%\draw[fill=yellow] (1,1) -- (2,0) -- (3,-1) -- (4,0) -- (5,1) -- (1,1);
%\draw[help lines] (-0.2, -1.2) grid (15.2, 4.2);
%\draw[line width=2pt] (0, 0) -- (1,1);
%\draw
%[line width=2pt] (5,1) -- (6,2) -- (7,3) -- (8,2) -- (9,3) -- (10,4) -- (11,3) -- (12,2) -- (13,1) -- (13,1);
%\draw[line width=2pt] (1,1) -- (2,0) -- (3,-1) -- (4,0) -- (5,1);
%\draw[line width=2pt] (13,1) -- (14,0) -- (15,-1);
%\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
%\draw[fill=blue] (15, -1) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw
[fill=blue] (5,1) -- (6,2) -- (7,3) -- (8,2) -- (9,3) -- (10,4) -- (11,3) -- (12,2) -- (13,1) -- (5,1);
\draw[fill=yellow] (1,1) -- (2,0) -- (3,-1) -- (4,0) -- (5,1) -- (1,1);
\draw[help lines] (-0.2, -1.2) grid (15.2, 4.2);
\draw[line width=2pt] (0, 0) -- (1,1);
\draw
[line width=2pt] (5,1) -- (6,2) -- (7,3) -- (8,2) -- (9,3) -- (10,4) -- (11,3) -- (12,2) -- (13,1) -- (13,1);
\draw[line width=2pt] (1,1) -- (2,0) -- (3,-1) -- (4,0) -- (5,1);
\draw[line width=2pt] (13,1) -- (14,0) -- (15,-1);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
\draw[fill=blue] (15, -1) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
$%
\end{tabular}
\ \
\]
(NB: underlines and overlines mark the factors being transformed).
\end{itemize}

\subsection{Heights}

\begin{itemize}
\item[$\circled{$\ast$}$] The \textbf{height} $\operatorname*{ht}\left(
p\right)  $ of a point $p$ is its y-coordinate.

\item[$\circled{$\ast$}$] The \textbf{initial height} and the \textbf{final
height} of a path $\mathbf{p}$ are the heights of its starting and ending points.

\item[$\circled{$\ast$}$] If $\mathbf{p}=(p_{0},p_{1},\ldots,p_{k})$ is any
diagonal path, then we associate three Laurent polynomials (in the
indeterminate $z$) to $\mathbf{p}$:%
\[
\underbrace{\sum\limits_{i=0}^{k}z^{\operatorname*{ht}(p_{i})}}_{\text{the
\textbf{height polynomial}}},\ \ \ \ \ \ \ \ \ \ \underbrace{\sum
\limits_{p_{i}\text{ is an NE-step of }\mathbf{p}}z^{\operatorname*{ht}%
(p_{i})}}_{\text{the \textbf{NE-height polynomial}}}%
,\ \ \ \ \ \ \ \ \ \ \underbrace{\sum\limits_{p_{i}\text{ is an SE-step of
}\mathbf{p}}z^{\operatorname*{ht}(p_{i})}}_{\text{the \textbf{SE-height
polynomial}}}.
\]
These encode (respectively) the multiset of heights of all vertices, of all
NE-steps, and of all SE-steps of $\mathbf{p}$.

\item[$\circled{$\ast$}$] All concepts defined for paths can be applied to
words (just replace a word by its standard path).

\item \textbf{Example:} For the word $w=UDUUDDD$, the heights are shown in the
following:%
\[%
\begin{array}
[c]{c}%
\text{heights of SE-steps}\\
\begin{tikzpicture} \draw[help lines] (-0.2, -1.2) grid (7.2, 2.2); \draw [line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 0) (2, 0) edge (3, 1) (3, 1) edge (4, 2) (4, 2) edge (5, 1) (5, 1) edge (6, 0) -- (7, -1); \draw[fill=blue] (0, 0) circle (0.1) node[left] {\textcolor{blue}{$\left(0, 0\right)\ $}}; \draw[fill=blue] (7, -1) circle (0.1) node[below] {\textcolor{blue}{$\ \left(7, -1\right)$}}; \draw (0,0) -- (0, -3); \node at (0,-3) [below] {$0$}; \draw (2,0) -- (2, -3); \node at (2,-3) [below] {$0$}; \draw (3,1) -- (3, -3); \node at (3,-3) [below] {$1$}; \draw (1,1) -- (1, 4); \node at (1,4) [above] {$1$}; \draw (4,2) -- (4, 4); \node at (4,4) [above] {$2$}; \draw (5,1) -- (5, 4); \node at (5,4) [above] {$1$}; \draw (6,0) -- (6, 4); \node at (6,4) [above] {$0$}; \draw (7,-1) -- (9,-1); \node at (9,-1) [right] {$-1$}; \end{tikzpicture}\\
\text{heights of NE-steps}%
\end{array}
\ .
\]
(The ending point is neither an SE-step nor an NE-step.) Thus, the word $w$
has%
\begin{align*}
&  \text{height polynomial }z^{0}+z^{1}+z^{0}+z^{1}+z^{2}+z^{1}+z^{0}+z^{-1}\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =z^{-1}%
+3+3z+z^{2};\\
&  \text{NE-height polynomial }z^{0}+z^{0}+z^{1}=2+z;\\
&  \text{SE-height polynomial }z^{1}+z^{2}+z^{1}+z^{0}=1+2z+z^{2}.
\end{align*}


\item \textbf{Lemma:} Balanced commutations and balanced flips leave all three
polynomials (NE-height, SE-height, height) as well as the final height unchanged.
\end{itemize}

\newpage

\section{The main theorems}

\begin{itemize}
\item[$\circled{$\ast$}$] \textbf{Equivalence Theorem.}

Let $u$ and $v$ be two words in $\mathcal{M}$. Then, the following seven
statements are equivalent:

\begin{enumerate}
\item[$\mathcal{S}_{\phi}$:] The words $u$ and $v$ are $\phi$-equivalent (that is,
$\phi\left(  u\right)  =\phi\left(  v\right)  $).

\item[$\mathcal{S}_{\operatorname{pol}}$:] The elements $\phi\left(  u\right)  $ and
$\phi\left(  v\right)  $ act equally on the polynomial ring $\mathbf{k}\left[
x\right]  $.
(Reminder: $D$ acts as $\dfrac{d}{dx}$, and $U$ as $x$.)

\item[$\mathcal{S}_{\operatorname{NE}}$:] The words $u$ and $v$ have the same final height and
the same NE-height polynomial (i.e., the multiset of heights of the NE-steps
of $u$ is the same as for $v$).

\item[$\mathcal{S}_{\operatorname{SE}}$:] The words $u$ and $v$ have the same final
height and the same SE-height polynomial (i.e., the multiset of heights of the
SE-steps of $u$ is the same as for $v$).

\item[$\mathcal{S}_{\operatorname{ht}}$:] The words $u$ and $v$ have the same final height and
the same height polynomial (i.e., the multiset of heights of all vertices of
$u$ is the same as for $v$).

\item[$\mathcal{S}_{\operatorname{comm}}$:] The word $u$ can be transformed into $v$ by balanced commutations.

\item[$\mathcal{S}_{\operatorname{flip}}$:] The word $u$ can be transformed into $v$ by balanced flips.
\end{enumerate}

\item[$\circled{$\ast$}$] \textbf{Reflection Theorem.} Each balanced word $u$
is $\phi$-equivalent to $\omega\left(  u\right)  $.

\item \textbf{Consequence (word problem):} The $\phi$-equivalence of two words
$u,v$ of length $\leq n$ can be tested in $O\left(  n\right)  $ time and memory.

\item \textbf{Remark (easy part of the Equivalence Theorem):} The lemma on the
previous page shows that $\mathcal{S}_{i}\Longrightarrow\mathcal{S}_{j}$ for
all $i\in\left\{  \phi,\operatorname{pol}\right\}  $ and $j\in\left\{  \operatorname{NE},\operatorname{SE},\operatorname{ht}\right\}  $.

\item \textbf{Remark:} The implication $\mathcal{S}_{\operatorname{comm}}\Longrightarrow
\mathcal{S}_{\phi}$ is essentially known.

Indeed, \href{https://doi.org/10.24033/bsmf.1667}{Dixmier (1968)} observed
that the Weyl algebra $\mathcal{W}$ is $\mathbb{Z}$-graded ($\deg U=1$ and
$\deg D=-1$) and that its $0$-th graded component $\mathcal{W}_{0}$ is
commutative (being spanned by the powers of $DU$). Hence, any two balanced
words (upon application of $\phi$) commute (as they lie in $\mathcal{W}_{0}$).
Thus, balanced commutations don't change the $\phi$-image.

\item There are also other connections to existing results; see below.
\end{itemize}

\newpage

\section{Up-normal words}

\begin{itemize}
\item To prove the main theorems, we need some more concepts.

\item[$\circled{$\ast$}$] A word $w$ is called

\begin{itemize}
\item \textbf{rising} if it has at least as many $U$'s as $D$'s;

\item \textbf{falling} if it has at most as many $U$'s as $D$'s.
\end{itemize}

Note that balanced = rising $\wedge$ falling.

\item[$\circled{$\ast$}$] A \textbf{down-zig} means a word of the form
$UD^{k}U$ for some $k\geq2$. Pictorially:%
\[
\begin{tikzpicture}
\draw[help lines] (-0.2, -3.2) grid (6.2, 1.2);
\draw[line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 0) (2, 0) edge (3, -1) (3, -1) edge (4, -2) (4, -2) edge (5, -3) (5, -3) -- (6, -2);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
\draw[fill=blue] (6, -2) circle (0.1) node[right] {};
\end{tikzpicture}
\]


\item[$\circled{$\ast$}$] A word $w\in\mathcal{M}$ is said to be
\textbf{up-normal} if it is rising and contains no down-zig as a factor.

\item \textbf{Crucial lemmas.}

\begin{enumerate}
\item Every up-normal word has the form
\[
D^{a}\,(UD)^{r_{1}}U\,(UD)^{r_{2}}U\,\cdots\,(UD)^{r_{h}}U\,D^{b}%
\]
for some nonnegative integers $a,b,h$ and $r_{1},r_{2},\ldots,r_{h}$.

\item An up-normal word $w$ is uniquely determined by its final height and its
height polynomial.

\item The height, NE-height and SE-height polynomials of a word $w$ mutually
determine each other, as long as the final height of $w$ is known.

\item If a rising word $w$ is not up-normal, then we can write $w$ as
$w=upqv$, where $u$ and $v$ are two words, where $p$ is a balanced word
starting with a $U$, and where $q$ is a balanced word starting with a $D$.
(Thus, we can make $w$ lexicographically smaller by applying a balanced commutation.)
\end{enumerate}

\item These easily yield:

\item \textbf{Proposition.} Let $w\in\mathcal{M}$ be a rising word. Then,
there exists a unique up-normal word $t\in\mathcal{M}$ that can be obtained
from $w$ by balanced commutations.

\item Hence, $\mathcal{S}_{\operatorname{ht}}\Longrightarrow\mathcal{S}_{\operatorname{comm}}$ easily follows
for rising $w$. If $w$ is falling, then apply the same argument to
$\omega\left(  w\right)  $.

\item Also, $\mathcal{S}_{\operatorname{comm}}\Longrightarrow\mathcal{S}_{\operatorname{flip}}$ because any
balanced commutation can be written as three balanced flips:%
\begin{align*}
\ldots pq\ldots\ \  &  \mapsto\ \ \ldots\omega\left(  p\right)  q\ldots
\ \ \mapsto\ \ \ldots\omega\left(  p\right)  \omega\left(  q\right)  \ldots\\
&  \mapsto\ \ \ldots\omega\left(  \omega\left(  p\right)  \omega\left(
q\right)  \right)  \ldots\ \ =\ \ \ldots qp\ldots
\end{align*}


\item Altogether, $\mathcal{S}_{\operatorname{NE}},\ldots,\mathcal{S}_{\operatorname{flip}}$ are thus equivalent.
\end{itemize}

\newpage

\section{Height polynomials and the Weyl action}

\begin{itemize}
\item To link $\mathcal{S}_{\phi}$ and $\mathcal{S}_{\operatorname{pol}}$ with $\mathcal{S}%
_{3},\ldots,\mathcal{S}_{\operatorname{flip}}$, we need the following easy fact:

\item \textbf{Proposition.} Let $w$ be a word and $\mathbf{p}=\left(
p_{0},p_{1},\ldots,p_{k}\right)  $ be a path corresponding to it. Let
$h_{i}:=\operatorname*{ht}\left(  p_{i}\right)  $ for each $i\in\left\{
0,1,\ldots,k\right\}  $. Then, for each $s\in\mathbb{Z}$, we have%
\[
\left(  \phi\left(  w\right)  \right)  \left(  x^{s}\right)  =\left(
\prod_{p_{i}\text{ is an SE-step of }\mathbf{p}}\left(  s+h_{k}-h_{i+1}%
\right)  \right)  \cdot x^{s+h_{k}-h_{0}}.
\]
Here, we let $\mathcal{W}$ act on the Laurent polynomial ring $\mathbf{k}%
\left[  x,x^{-1}\right]  $ (extending the action on $\mathbf{k}\left[
x\right]  $ in the obvious way).

\item An $\omega$-reflected version also holds.

\item Thus, $\mathcal{S}_{\operatorname{pol}}\Longrightarrow\mathcal{S}_{\operatorname{SE}}$ can be
proved by uniqueness of roots of a polynomial.

The rest of the proofs are easy.
\end{itemize}

\newpage

\section{Enumeration}

\subsection{All words}

\begin{itemize}
\item[$\circled{$\ast$}$] For $0\leq k\leq n$, let $a(n,k)$ be the number of
$\phi$-equivalence classes of words with $k$ many $D$'s and $n-k$ many $U$'s.

\item \textbf{Easy fact.} We have
\[
a\left(  n,0\right)  =a\left(  n,n\right)  =1\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ a\left(  n,k\right)  =a\left(  n,n-k\right)  .
\]


\item \textbf{Theorem.} For $n>2k\geq0$, we have
\[
a(n,k)=a(n-1,k)+a(n-2,k-1).
\]


\item \textbf{Proposition.} For $k>0$, we have
\[
a(2k,k)=(k+3)2^{k-2}\quad\text{and}\quad a(2k+1,k)=(k+2)2^{k-1}.
\]


\item \textbf{Theorem.} We have
\[
\sum_{n\geq0}\ \ \sum_{0\leq k\leq n}a(n,k)t^{k}x^{n}=\frac{(1-3tx^{2}%
+t^{2}x^{4})(1-tx^{2})^{2}}{(1-tx-tx^{2})(1-x-tx^{2})(1-2tx^{2})^{2}}%
\]
or equivalently
\[
\sum_{n\geq0}\ \ \sum_{0\leq k\leq n/2}a(n,k)t^{k}x^{n}=\frac{(1-tx^{2})^{3}%
}{(1-x-tx^{2})(1-2tx^{2})^{2}}.
\]


\item \textbf{Theorem.} For all $n$ and $k$ with $0\leq k\leq n/2$, we have
\[
a(n,k)=\sum_{j=0}^{k}(k-j+1)\binom{n-k-1}{j}.
\]


\item \textbf{Corollary.} The total number of $\phi$-equivalence classes of
words of length $n>0$ is
\[
\sum_{k=0}^{n}a(n,k)=2\underbrace{F_{n+4}}_{\text{Fibonacci}}-%
\begin{cases}
(3n+42)2^{n/2-3}, & \text{if }n\text{ even,}\\
(n+15)2^{(n-3)/2}, & \text{if }n\text{ odd.}%
\end{cases}
\]


\item
\[%
\begin{tabular}
[c]{|c|ccccccccccc|}\hline
$n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$\\\hline
$\sum_{k}a(n,k)$ & $1$ & $2$ & $4$ & $8$ & $15$ & $28$ & $50$ & $90$ & $156$ &
$274$ & $466$\\\hline
\end{tabular}
\
\]

\end{itemize}

\subsection{$c$-Dyck words}

\begin{itemize}
\item[$\circled{$\ast$}$] Fix a constant $c>0$, and let $\mathcal{M}%
_{c}\subseteq\mathcal{M}$ be the set of words whose every prefix has at least
$c$ times as many $U$'s as $D$'s. This is a submonoid of $\mathcal{M}$.

Let $a_{c}(n,k)$ be the number of $\phi$-equivalence classes of words in
$\mathcal{M}_{c}$ that consist of $k$ $D$'s and $n-k$ $U$'s.

\item \textbf{Lemma.} For every real constant $c\geq1$ and any positive
integers $n$ and $k$ with $n-1\geq(c+1)k$, we have
\[
a_{c}(n,k)=a_{c}(n-1,k)+a_{c}(n-2,k-1).
\]


\item \textbf{Theorem.} If $c$ is a positive integer and $n,k$ are positive
integers with $n\geq(c+1)k$, then
\[
a_{c}(n,k)=\binom{n-k-1}{k}-(c-2)\sum_{j=0}^{k-1}\binom{n-k-1}{j}.
\]


\item In particular,%
\begin{align*}
a_{1}(n,k)  &  =\sum_{j=0}^{k}\binom{n-k-1}{j}\ \ \ \ \ \ \ \ \ \ \text{and}\\
a_{2}(n,k)  &  =\binom{n-k-1}{k},
\end{align*}
both of which can be proved bijectively.
\end{itemize}

\subsection{The size of an equivalence class}

\begin{itemize}
\item \textbf{Theorem.} Let $w\in\mathcal{M}$ be a word with NE-height
polynomial $\sum\limits_{i\in\mathbb{Z}}a_{i}z^{i}$ and SE-height polynomial
$\sum\limits_{i\in\mathbb{Z}}b_{i}z^{i}$. Then, the size of the $\phi
$-equivalence class containing $w$ is
\begin{align*}
&  \prod_{i\geq0}\binom{a_{i}+b_{i+2}-1}{b_{i+2}}\binom{b_{-i}+a_{-i-2}%
-1}{a_{-i-2}}\\
&  \qquad\cdot%
\begin{cases}
\binom{a_{0}+b_{0}}{a_{0}}, & \text{ if $w$ is balanced;}\\
\binom{a_{0}+b_{0}-1}{b_{0}}, & \text{ if $w$ is rising and non-balanced;}\\
\binom{a_{0}+b_{0}-1}{a_{0}}, & \text{ if $w$ is falling and non-balanced.}%
\end{cases}
\end{align*}

\end{itemize}

\newpage

\section{Bond percolation}

\begin{itemize}
\item Consider again the number of all $\phi$-equivalence classes of words of
length $n$:%
\[%
\begin{tabular}
[c]{|c|ccccccccccc|}\hline
$n$ & $0$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$\\\hline
$\sum_{k}a(n,k)$ & $1$ & $2$ & $4$ & $8$ & $15$ & $28$ & $50$ & $90$ & $156$ &
$274$ & $466$\\\hline
\end{tabular}
\
\]
This agrees with \href{https://oeis.org/A006727}{OEIS sequence A006727
\textquotedblleft Bond percolation series for square lattice\textquotedblright%
} up to $n=11$ (but no further). Why?

\item \textbf{Bond percolation on the directed square lattice} is one of the
fundamental problems in statistical physics.

In our language:

\begin{itemize}
\item Fix a number $p\in\left[  0,1\right]  $.

\item Consider the integer lattice $\mathbb{Z}^{2}$.

\item A \textbf{site} is a lattice point $\left(  i,j\right)  $ with $i\equiv
j\operatorname{mod}2$.

\item The NE-arcs and the SE-arcs are called \textbf{bonds}. They connect sites.

\item Each bond is \textbf{open} with probability $p$ and \textbf{closed} with
probability $1-p$ (all bonds are independent).

\item Fluid is dropped at the origin $\left(  0,0\right)  $ and flows
left-to-right across open bonds.

\item Which sites end up wet (i.e., eventually get some fluid)?
\end{itemize}

\item We are interested in the infinite sum%
\[
S\left(  p\right)  :=\sum_{\text{sites }\left(  i,j\right)  }%
\operatorname*{Prob}\left(  \text{the site }\left(  i,j\right)  \text{ ends up
wet}\right)
\]
and its finite approximations%
\[
S_{n}\left(  p\right)  :=\sum_{\substack{\text{sites }\left(  i,j\right)
;\\i\leq n}}\operatorname*{Prob}\left(  \text{the site }\left(  i,j\right)
\text{ ends up wet}\right)  .
\]
The latter is an explicit polynomial in $p$.

The former is a power series, and can be found as the coefficientwise limit
$\lim\limits_{n\rightarrow\infty}S_{n}\left(  p\right)  $.

\item \href{https://oeis.org/A006727}{OEIS sequence A006727 \textquotedblleft
Bond percolation series for square lattice\textquotedblright} is the sequence
of coefficients of this series%
\[
S\left(  p\right)  =1+2p+4p^{2}+8p^{3}+15p^{4}+28p^{5}+\cdots.
\]


Why do they agree with $\sum_{k}a(n,k)$ up to $n=11$ ?

There is some relation: $\sum_{k}a(n,k)$ is the total \# of $\phi$-equivalence
classes of paths from $\left(  0,0\right)  $ to all sites $\left(  i,j\right)
$ with $i=n$.

Is there a clearer connection?

\item Note that $S\left(  p\right)  $ has some negative coefficients, e.g.
$-48816119038p^{50}$.
\end{itemize}

\newpage

\section{The rook theory connection}

\begin{itemize}
\item The Weyl algebra $\mathcal{W}$ is known to be connected to \textbf{rook
theory}.

\item[$\circled{$\ast$}$] Recall the standard definitions:

\begin{itemize}
\item A \textbf{cell} is a pair $\left(  i,j\right)  $ of positive integers,
drawn as a $1\times1$-square.

\item A \textbf{board} is a finite set of cells, e.g.,
\[
\begin{tikzpicture} \draw[fill=red!50] (0, 0) rectangle (1, 1); \draw[fill=red!50] (1, 1) rectangle (2, 2); \draw[fill=red!50] (2, 0) rectangle (3, 1); \draw[fill=red!50] (3, 1) rectangle (4, 2); \draw[fill=red!50] (5, 0) rectangle (6, 1); \draw[fill=red!50] (5, 1) rectangle (6, 2); \end{tikzpicture}\ \ .
\]


\item A \textbf{rook placement} of a board $B$ is a subset $S$ of $B$ such
that no two cells in $S$ lie in the same row or column.

\item The $k$\textbf{-th rook number }$r_{k}\left(  B\right)  $ of a board $B$
is the number of $k$-element rook placements of $B$.

For example, the above example board has $r_{0}\left(  B\right)  =1$ and
$r_{1}\left(  B\right)  =\left\vert B\right\vert =6$ and $r_{2}\left(
B\right)  =8$ and $r_{k}\left(  B\right)  =0$ for all $k>2$.

\item Two boards $B$ and $C$ are said to be \textbf{rook-equivalent} if they
share the same rook numbers (i.e., if $r_{k}\left(  B\right)  =r_{k}\left(
C\right)  $ for all $k\in\mathbb{N}$).

\item A well-known class of boards are the Ferrers boards:

If $w$ is a word in $\mathcal{M}$, then the \textbf{Ferrers board }$B_{w}$ is
a contiguous set of cells, whose bottom and right boundaries are straight
lines, whereas the rest of its boundary is a jagged path that (when walked
from southwest to northeast) takes a north-step for each $D$ in $w$ and an
east-step for each $U$ in $w$ (reading the word $w$ from left to right).

For instance, if $w=UDDUDUUDUD$, then%
\[
B_{w}=\ \ \begin{tikzpicture}
\draw[fill=red!50] (1, 0) rectangle (2, 1);
\draw[fill=red!50] (1, 1) rectangle (2, 2);
\draw[fill=red!50] (2, 0) rectangle (3, 1);
\draw[fill=red!50] (2, 1) rectangle (3, 2);
\draw[fill=red!50] (2, 2) rectangle (3, 3);
\draw[fill=red!50] (3, 0) rectangle (4, 1);
\draw[fill=red!50] (3, 1) rectangle (4, 2);
\draw[fill=red!50] (3, 2) rectangle (4, 3);
\draw[fill=red!50] (4, 0) rectangle (5, 1);
\draw[fill=red!50] (4, 1) rectangle (5, 2);
\draw[fill=red!50] (4, 2) rectangle (5, 3);
\draw[fill=red!50] (4, 3) rectangle (5, 4);
\draw (0, 0) -- (1, 0);
\draw (5, 4) -- (5, 5);
\node(x1) at (0.5, -0.25) {$U$};
\node(x2) at (0.75, 0.5) {$D$};
\node(x3) at (0.75, 1.5) {$D$};
\node(x4) at (1.5, 1.75) {$U$};
\node(x5) at (1.75, 2.5) {$D$};
\node(x6) at (2.5, 2.75) {$U$};
\node(x7) at (3.5, 2.75) {$U$};
\node(x8) at (3.75, 3.5) {$D$};
\node(x9) at (4.5, 3.75) {$U$};
\node(x10) at (4.75, 4.5) {$D$};
\end{tikzpicture}
\]

\end{itemize}

\item \textbf{Theorem (\href{https://doi.org/10.1007/BF02828687}{\textbf{Navon
1973}}).} Let $w\in\mathcal{M}$ be any word that contains $n$ many $D$'s and
$m$ many $U$'s. Then, in $\mathcal{W}$, we have%
\[
\phi\left(  w\right)  =\sum_{k=0}^{\min\left\{  m,n\right\}  }r_{k}\left(
B_{w}\right)  U^{m-k}D^{n-k}.
\]


\item Consequently:

\item \textbf{Equivalence Theorem +.} Let $u$ and $v$ be two words in
$\mathcal{M}$. Assume that $u$ and $v$ have the same \# of $U$'s and the same
\# of $D$'s. Then, the seven statements $\mathcal{S}_{\phi},\mathcal{S}%
_{\operatorname{pol}},\ldots,\mathcal{S}_{\operatorname{flip}}$ of the Equivalence Theorem are also equivalent to
the following statement:

\begin{itemize}
\item $\mathcal{R}_{1}$: The boards $B_{u}$ and $B_{v}$ are rook-equivalent.
\end{itemize}

\item \textbf{Remark:} The Ferrers board $B_{w}$ \textquotedblleft does not
see\textquotedblright\ any $U$'s at the beginning of $w$ and any $D$'s at the
end of $w$. Thus, $\phi$-equivalence is stronger than rook-equivalence in
general. Hence the need for the extra\ assumption in the Equivalence Theorem +.

\item \textbf{Remark:} The implication $\mathcal{R}_{1}\Longrightarrow
\mathcal{S}_{\phi}$ is folklore among rook theorists. What else follows from rook theory?

\begin{itemize}
\item A classical result of
\href{https://irma.math.unistra.fr/~foata/paper/pub13.pdf}{Foata and
Sch\"{u}tzenberger (1970)} shows that each Ferrers board is rook-equivalent to
a unique \textquotedblleft increasing Ferrers board\textquotedblright. These
\textquotedblleft increasing Ferrers boards\textquotedblright\ are somewhat
similar to our up-normal words, but not quite in bijection.

\item Foata and Sch\"{u}tzenberger have their own kind of moves that they use
to normalize a Ferrers board modulo rook equivalence: the \textquotedblleft%
$\left(  k,k^{\prime}\right)  $-transforms\textquotedblright. These appear to
be close relatives of our balanced flips.
\end{itemize}

\item[$\circled{$\ast$}$] Rook equivalence has a surprising interpretation
(\href{https://doi.org/10.1006/aama.1998.0582}{Haglund 1998} and
\href{https://arxiv.org/abs/2312.02508v1}{Cotardo/Gruica/Ravagnani 2023}):

For any finite field $F$, any nonnegative integers $n$ and $k$, and any board
$B\subseteq\left\{  1,2,\ldots,n\right\}  ^{2}$, we define $P_{k}\left(
B/F\right)  $ to be the number of $n\times n$-matrices $A\in F^{n\times n}$ of
rank $k$ such that all entries of $A$ in cells outside of $B$ are zero.

\item \textbf{Example:}%
\[
B_{w}=\ \ \begin{tikzpicture}
\draw[fill=red!50] (1, 0) rectangle (2, 1);
\draw[fill=red!50] (1, 1) rectangle (2, 2);
\draw[fill=red!50] (2, 0) rectangle (3, 1);
\draw[fill=red!50] (2, 1) rectangle (3, 2);
\draw[fill=red!50] (2, 2) rectangle (3, 3);
\draw[fill=red!50] (3, 0) rectangle (4, 1);
\draw[fill=red!50] (3, 1) rectangle (4, 2);
\draw[fill=red!50] (3, 2) rectangle (4, 3);
\draw[fill=red!50] (4, 0) rectangle (5, 1);
\draw[fill=red!50] (4, 1) rectangle (5, 2);
\draw[fill=red!50] (4, 2) rectangle (5, 3);
\draw[fill=red!50] (4, 3) rectangle (5, 4);
\draw (0, 0) -- (1, 0);
\draw (5, 4) -- (5, 5);
\node(x1) at (0.5, -0.25) {$U$};
\node(x2) at (0.75, 0.5) {$D$};
\node(x3) at (0.75, 1.5) {$D$};
\node(x4) at (1.5, 1.75) {$U$};
\node(x5) at (1.75, 2.5) {$D$};
\node(x6) at (2.5, 2.75) {$U$};
\node(x7) at (3.5, 2.75) {$U$};
\node(x8) at (3.75, 3.5) {$D$};
\node(x9) at (4.5, 3.75) {$U$};
\node(x10) at (4.75, 4.5) {$D$};
\end{tikzpicture}\ \ \Longrightarrow\ \ A=\left(
\begin{array}
[c]{ccccc}%
0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & x\\
0 & 0 & y & z & w\\
0 & p & q & r & s\\
0 & a & b & c & d
\end{array}
\right)  .
\]


\item \textbf{Equivalence Theorem ++.} Let $u$ and $v$ be two words in
$\mathcal{M}$ that have the same \# of $U$'s and the same \# of $D$'s. Then,
the seven statements $\mathcal{S}_{\phi},\mathcal{S}_{\operatorname{pol}},\ldots,\mathcal{S}_{\operatorname{flip}}$
of the Equivalence Theorem are also equivalent to the following statements:

\begin{itemize}
\item $\mathcal{R}_{1}$: The boards $B_{u}$ and $B_{v}$ are rook-equivalent.

\item $\mathcal{R}_{2}$: For any finite field $F$ and any $k\in\mathbb{N}$, we
have $P_{k}\left(  B_{u}/F\right)  =P_{k}\left(  B_{v}/F\right)  $.

\item $\mathcal{R}_{3}$: For any finite field $F$, we have $P_{1}\left(
B_{u}/F\right)  =P_{1}\left(  B_{v}/F\right)  $.
\end{itemize}

\item The proofs follow from
\href{https://arxiv.org/abs/2312.02508v1}{Cotardo/Gruica/Ravagnani 2023},
which also gives some further equivalent conditions (Corollary 3.2 loc. cit.).
\end{itemize}

\newpage

\section{Irreducible balanced words}

\begin{itemize}
\item The Equivalence Theorem shows that $\phi$-equivalence is
\textquotedblleft generated\textquotedblright\ by balanced commutations.

\item But do we need \textbf{all} balanced commutations, or can we make do
with a proper subset?

\item The latter is the case. I don't know what the smallest sufficient set of
balanced commutations is (I don't think it is even unique), but here is one
that suffices:

\item We define special classes of balanced words:

\begin{itemize}
\item A \textbf{UIB word} means a balanced word that begins with a $U$ and
whose standard path never returns to the x-axis before its ending point.

\item A \textbf{DIB word} means a balanced word that begins with a $D$ and
whose standard path never returns to the x-axis before its ending point.
\end{itemize}

Examples:%
\[%
\begin{tabular}
[c]{cccc}%
UIB & DIB & neither & neither\\
$%
%TCIMACRO{\TeXButton{tikzpicture}{\begin{tikzpicture}[scale=0.5]
%\draw[help lines] (-0.2, -0.2) grid (6.2, 2.2);
%\draw(-0.2, 0) -- (6.2, 0);
%\draw
%[line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 2) (2, 2) edge (3, 1) (3, 1) edge (4, 2) (4, 2) edge (5, 1) (5, 1) -- (6, 0);
%\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
%\draw[fill=blue] (6, 0) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw[help lines] (-0.2, -0.2) grid (6.2, 2.2);
\draw(-0.2, 0) -- (6.2, 0);
\draw
[line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 2) (2, 2) edge (3, 1) (3, 1) edge (4, 2) (4, 2) edge (5, 1) (5, 1) -- (6, 0);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
\draw[fill=blue] (6, 0) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikzpicture}{\begin{tikzpicture}[scale=0.5, yscale=-1]
%\draw[help lines] (-0.2, -0.2) grid (6.2, 2.2);
%\draw(-0.2, 0) -- (6.2, 0);
%\draw
%[line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 2) (2, 2) edge (3, 1) (3, 1) edge (4, 2) (4, 2) edge (5, 1) (5, 1) -- (6, 0);
%\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
%\draw[fill=blue] (6, 0) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5, yscale=-1]
\draw[help lines] (-0.2, -0.2) grid (6.2, 2.2);
\draw(-0.2, 0) -- (6.2, 0);
\draw
[line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 2) (2, 2) edge (3, 1) (3, 1) edge (4, 2) (4, 2) edge (5, 1) (5, 1) -- (6, 0);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
\draw[fill=blue] (6, 0) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikzpicture}{\begin{tikzpicture}[scale=0.5]
%\draw[help lines] (-0.2, -0.2) grid (4.2, 2.2);
%\draw(-0.2, 0) -- (4.2, 0);
%\draw
%[line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 0) (2, 0) edge (3, 1) (3, 1) -- (4, 0);
%\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
%\draw[fill=blue] (4, 0) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw[help lines] (-0.2, -0.2) grid (4.2, 2.2);
\draw(-0.2, 0) -- (4.2, 0);
\draw
[line width=2pt,-stealth] (0, 0) edge (1, 1) (1, 1) edge (2, 0) (2, 0) edge (3, 1) (3, 1) -- (4, 0);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
\draw[fill=blue] (4, 0) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
$ & $%
%TCIMACRO{\TeXButton{tikzpicture}{\begin{tikzpicture}[scale=0.5]
%\draw[help lines] (-0.2, -1.2) grid (4.2, 2.2);
%\draw(-0.2, 0) -- (4.2, 0);
%\draw
%[line width=2pt,-stealth] (0, 0) edge (1, -1) (1, -1) edge (2, 0) (2, 0) edge (3, 1) (3, 1) -- (4, 0);
%\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
%\draw[fill=blue] (4, 0) circle (0.1) node[right] {};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.5]
\draw[help lines] (-0.2, -1.2) grid (4.2, 2.2);
\draw(-0.2, 0) -- (4.2, 0);
\draw
[line width=2pt,-stealth] (0, 0) edge (1, -1) (1, -1) edge (2, 0) (2, 0) edge (3, 1) (3, 1) -- (4, 0);
\draw[fill=blue] (0, 0) circle (0.1) node[left] {};
\draw[fill=blue] (4, 0) circle (0.1) node[right] {};
\end{tikzpicture}%
%EndExpansion
$%
\end{tabular}
\]


\item An \textbf{irreducible balanced commutation} means a balanced
commutation $pxyq\mapsto pyxq$ in which one of the words $x$ and $y$ is UIB
and the other is DIB.

\item \textbf{Theorem.} Any two $\phi$-equivalent words can be transformed
into each other by a sequence of irreducible balanced commutations.
\end{itemize}

\newpage

\section{Other algebras}

\begin{itemize}
\item What if we replace the Weyl algebra $\mathcal{W}=\mathbf{k}\left\langle
D,U\ \mid\ DU-UD=1\right\rangle $ by other algebras?
\end{itemize}

\subsection{Multivariate Weyl algebras}

\begin{itemize}
\item[$\circled{$\ast$}$] For any $n\in\mathbb{N}$, there is an $n$%
\textbf{-Weyl algebra}\ $\mathcal{W}_{n}$, defined as the $\mathbf{k}$-algebra
given by $2n$ generators $D_{1},D_{2},\ldots,D_{n},U_{1},U_{2},\ldots,U_{n}$
and relations%
\begin{align*}
D_{i}U_{j}  &  =U_{j}D_{i}\ \ \ \ \ \ \ \ \ \ \text{for all }i\neq j;\\
D_{i}U_{i}  &  =U_{i}D_{i}+1\ \ \ \ \ \ \ \ \ \ \text{for all }i;\\
D_{i}D_{j}  &  =D_{j}D_{i}\ \ \ \ \ \ \ \ \ \ \text{for all }i,j;\\
U_{i}U_{j}  &  =U_{j}U_{i}\ \ \ \ \ \ \ \ \ \ \text{for all }i,j.
\end{align*}
This is $\cong$ the $\mathbf{k}$-algebra of differential operators on the
polynomial ring $\mathbf{k}\left[  x_{1},x_{2},\ldots,x_{n}\right]  $.

\item It is also $\cong$ the $n$-fold tensor power $\mathcal{W}^{\otimes n}$
of the original Weyl algebra $\mathcal{W}$.

Any word in the $D_{1},D_{2},\ldots,D_{n},U_{1},U_{2},\ldots,U_{n}$
corresponds to a tensor product $w_{1}\otimes w_{2}\otimes\cdots\otimes w_{n}$
of $n$ words $w_{i}\in\mathcal{M}$.

The following theorem reduces the $\phi$-equivalence problem to that in
$\mathcal{M}$:

\item \textbf{Theorem.} Let $u_{1},u_{2},\ldots,u_{n},v_{1},v_{2},\ldots
,v_{n}$ be $2n$ words in $\mathcal{M}$. Then,%
\[
\phi\left(  u_{1}\right)  \otimes\phi\left(  u_{2}\right)  \otimes
\cdots\otimes\phi\left(  u_{n}\right)  =\phi\left(  v_{1}\right)  \otimes
\phi\left(  v_{2}\right)  \otimes\cdots\otimes\phi\left(  v_{n}\right)  \text{
in }\mathcal{W}^{\otimes n}%
\]
if and only if
\[
\phi\left(  u_{i}\right)  =\phi\left(  v_{i}\right)  \text{ for all }i.
\]

\end{itemize}

\subsection{Characteristic $p$}

\begin{itemize}
\item Hitherto we have assumed that the field $\mathbf{k}$ has characteristic
$0$.

\item If $\mathbf{k}$ has characteristic $p\neq0$ instead, some things go south:

\begin{itemize}
\item the words $U^{p+1}D$ and $UDU^{p}$ become $p$-equivalent despite not
satisfying $\mathcal{S}_{\operatorname{NE}},\ldots,\mathcal{S}_{\operatorname{flip}}$;

\item the action of $\mathcal{W}$ on $\mathbf{k}\left[  x\right]  $ is no
longer faithful.
\end{itemize}

The implications $\mathcal{S}_{\operatorname{NE}},\ldots,\mathcal{S}_{\operatorname{flip}}\Longrightarrow
\mathcal{S}_{\phi}\Longrightarrow\mathcal{S}_{\operatorname{pol}}$ still hold, but both arrows are
proper implications.

\item Actually, $U^{p}$ and $D^{p}$ are central in $\mathcal{W}$ if
$\operatorname*{char}\mathbf{k}=p$.

Thus, we get an additional kind of commutations where we swap a $U^{p}$ or
$D^{p}$ factor with any neighboring factor.

\textbf{Question:} Do these suffice? If not, what transformations are needed?

\item The Weyl algebra $\mathcal{W}$ in characteristic $p$ also has three
quotients%
\begin{align*}
\mathcal{W}^{-}  &  :=\mathcal{W}/\left(  \mathcal{W}U^{p}\mathcal{W}\right)
,\ \ \ \ \ \ \ \ \ \ \mathcal{W}_{-}:=\mathcal{W}/\left(  \mathcal{W}%
D^{p}\mathcal{W}\right)  ,\\
\mathcal{W}_{-}^{-}  &  :=\mathcal{W}/\left(  \mathcal{W}U^{p}\mathcal{W}%
+\mathcal{W}D^{p}\mathcal{W}\right)  ,
\end{align*}
and we can study a variant of $\phi$-equivalence on each of them.

\item \textbf{Question:} Find analogues of the main theorems for $\mathcal{W}%
$, $\mathcal{W}^{-}$, $\mathcal{W}_{-}$ and $\mathcal{W}_{-}^{-}$.
\end{itemize}

\subsection{Down-up algebras}

\begin{itemize}
\item We now return to the case when $\mathbf{k}$ is a field of characteristic
$0$.

\item[$\circled{$\ast$}$] The Weyl algebra $\mathcal{W}$ has several
deformations and variations. One of the most general is the \textbf{down-up
algebra} $\mathcal{A}\left(  \alpha,\beta,\gamma\right)  $ (due to
\href{https://doi.org/10.1006/jabr.1998.7511}{Benkart/Roby 1998}), defined for
any three scalar parameters $\alpha,\beta,\gamma\in\mathbf{k}$. It is the
$\mathbf{k}$-algebra with generators $D$ and $U$ and the two relations%
\begin{align*}
D^{2}U  &  =\alpha DUD+\beta UD^{2}+\gamma D\ \ \ \ \ \ \ \ \ \ \text{and}\\
DU^{2}  &  =\alpha UDU+\beta U^{2}D+\gamma U.
\end{align*}


\item \textbf{Examples:}

\begin{itemize}
\item $\mathcal{A}\left(  2,-1,0\right)  $ is the \textbf{homogenized Weyl
algebra} (with generators $D$ and $U$ and relations $\left[  D,\ DU-UD\right]
=0$ and $\left[  U,\ DU-UD\right]  =0$). This is also the universal enveloping
algebra $U\left(  \mathfrak{H}\right)  $ of the Heisenberg Lie algebra
$\mathfrak{H}$.

\item $\mathcal{A}\left(  2,-1,-2\right)  =U\left(  \mathfrak{sl}_{2}\right)
$.
\end{itemize}

\item If $\alpha+\beta=\gamma-\beta=1$, then $\mathcal{W}$ is a quotient of
$\mathcal{A}\left(  \alpha,\beta,\gamma\right)  $.

\item Define a map $\phi:\mathcal{M}\rightarrow\mathcal{A}\left(  \alpha
,\beta,\gamma\right)  $ in the same way as we defined $\phi:\mathcal{M}%
\rightarrow\mathcal{W}$. Surprisingly:

\item \textbf{Proposition:} If two words $u$ and $v$ in $\mathcal{M}$ are
$\phi$-equivalent for $\mathcal{W}$, then they are also $\phi$-equivalent for
$\mathcal{A}\left(  \alpha,\beta,\gamma\right)  $.

\item We can show that the converse holds whenever $\alpha+\beta=\gamma
-\beta=1$, but we suspect that it holds in more cases.

But not always! e.g., not in:

\begin{enumerate}
\item the case $\left(  \alpha,\beta,\gamma\right)  =\left(  0,1,0\right)  $
(here, we have $\phi\left(  DU^{2}\right)  =\phi\left(  U^{2}D\right)  $);

\item more generally, the case $\alpha=\gamma=0$ and arbitrary $\beta$ (here
we have $\phi\left(  DU^{4}D\right)  =\phi\left(  U^{2}D^{2}U^{2}\right)  $);

\item the case $\left(  \alpha,\beta\right)  =\left(  0,-1\right)  $ and
arbitrary $\gamma$ (here we have $\phi\left(  DU^{4}\right)  =\phi\left(
U^{4}D\right)  $);

\item the case $\left(  \alpha,\beta\right)  =\left(  -1,-1\right)  $ and
arbitrary $\gamma$ (here we have $\phi\left(  DU^{3}\right)  =\phi\left(
U^{3}D\right)  $);

\item the case $\left(  \alpha,\beta\right)  =\left(  1,-1\right)  $ and
arbitrary $\gamma$ (here we have $\phi\left(  DU^{6}\right)  =\phi\left(
U^{6}D\right)  $).
\end{enumerate}
\end{itemize}

\subsection{Bonus question: Hecke algebras}

\begin{itemize}
\item \textbf{Question:} Consider the Hecke algebra $\mathcal{H}_{n}\left(
q\right)  $ of the symmetric group $S_{n}$, where $q$ is an indeterminate
(i.e., generic). When do two words $i_{1}i_{2}\ldots i_{k}$ and $j_{1}%
j_{2}\ldots j_{\ell}$ over the alphabet $\left\{  1,2,\ldots,n-1\right\}  $
satisfy $T_{i_{1}}T_{i_{2}}\cdots T_{i_{k}}=T_{j_{1}}T_{j_{2}}\cdots
T_{j_{\ell}}$ ?
\end{itemize}

\newpage

\section*{I thank}

\begin{itemize}
\item \textbf{Richard P.\ Stanley} for the problem and \textbf{Tom Roby,
Stephan Wagner} and \textbf{Mei Yin} for the wonderful collaboration.

\item \textbf{J\"{o}rgen Backelin}, \textbf{G\'{e}rard H. E. Duchamp} and
\textbf{Joel Brewster Lewis} for enlightening conversations.

\item \textbf{G\'{e}rard H. E. Duchamp} for the invitation.

\item \textbf{you} for your patience.
\end{itemize}


\end{document}