\documentclass{beamer}%
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{tabls}
\usepackage{tikz}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Friday, April 05, 2024 10:34:15}
%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}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\begin{small}}{\end{small}}
\definecolor{grau}{rgb}{.5 , .5 , .5}
\definecolor{dunkelgrau}{rgb}{.35 , .35 , .35}
\definecolor{schwarz}{rgb}{0 , 0 , 0}
\definecolor{violet}{RGB}{143,0,255}
\definecolor{forestgreen}{RGB}{34, 100, 34}
\definecolor{darkred}{rgb}{0.7,0,0} % darkred color
\newcommand{\red}{\color{red}}
\newcommand{\grey}{\color{grau}}
\newcommand{\green}{\color{forestgreen}}
\newcommand{\violet}{\color{violet}}
\newcommand{\blue}{\color{blue}}
\newcommand{\defn}[1]{{\color{darkred}\emph{#1}}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\mono}{\hookrightarrow}
\newcommand{\epi}{\twoheadrightarrow}
\newcommand{\iso}{\overset{\cong}{\to}}
\newcommand{\arinj}{\ar@{_{(}->}}
\newcommand{\arinjrev}{\ar@{^{(}->}}
\newcommand{\arsurj}{\ar@{->>}}
\newcommand{\arelem}{\ar@{|->}}
\newcommand{\arback}{\ar@{<-}}
\newcommand{\symd}{\mathbin{\bigtriangleup}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Coker}{\operatorname{Coker}}
\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}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{\node[shape=circle,fill,inner sep=2pt] (char) {\textcolor{white}{#1}};}}
\newcommand{\icast}{\circled{$\ast$}}
\newcommand\redurl[1]{\textcolor{red}{\url{#1}}}
\newcommand\redhref[2]{\textcolor{red}{\href{#1}{#2}}}
\newcommand\arxiv[1]{\redhref{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\newenvironment{noncompile}{}{}
\excludecomment{noncompile}
\usetheme{Frankfurt}
\usefonttheme[onlylarge]{structurebold}
\setbeamerfont*{frametitle}{size=\normalsize,series=\bfseries}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{footline}[frame number]
\setbeamertemplate{itemize/enumerate body begin}{}
\setbeamertemplate{itemize/enumerate subbody begin}{\normalsize}
\beamersetuncovermixins{\opaqueness<1>{0}}{\opaqueness<2->{15}}
\newcommand{\STRUT}{\vrule width 0pt depth 8pt height 0pt}
\newcommand{\ASTRUT}{\vrule width 0pt depth 0pt height 11pt}
\setbeamertemplate{headline}{}
\begin{document}

\title{The random-to-random shuffles \\ and their $q$-deformations}
\author{Darij Grinberg (Drexel University)
\and \and \and \and \and joint work with Sarah Brauner,
\and Patricia Commins, \and Franco Saliola}
\date{AlCoVE conference, 2025-05-29}

\begin{noncompile}
\textbf{Abstract.} Consider a random shuffle acting on a deck of $n$ cards as follows:
Uniformly at random, we select $k$ out of our $n$ cards, remove them from the
deck, and then move them back to $k$ uniformly random positions. This shuffle
-- the so-called ``$k$-random-to-random shuffle''\ -- is a Markov chain that
is given by a certain element of the group algebra of the symmetric algebra. A
celebrated result of Dieker, Saliola and Lafreni\`ere says that this shuffle
is diagonalizable with all eigenvalues rational. Earlier, it was observed by
Reiner, Saliola and Welker that two such shuffles for different $k$'s always
commute. Both results are deep and hard.

I will discuss a new approach to these shuffles that has resulted in
simpler proofs as well as a $q$-deformation -- i.e., a generalization into the
Hecke algebra of the symmetric group. Along the way, some properties of the
Hecke algebras have been revealed, as well as some general results about
integrality of eigenvalues.

Joint work with Sarah Brauner, Patricia Commins and Franco Saliola.
\end{noncompile}


\frame{\titlepage\textbf{slides:}
\redurl{http://www.cip.ifi.lmu.de/~grinberg/algebra/alcove2025.pdf} \smallskip
\newline\textbf{paper (draft):}
\redurl{https://www.cip.ifi.lmu.de/~grinberg/algebra/r2r2.pdf}
\newline\textbf{or}
\redurl{https://arxiv.org/abs/2503.17580}}

\begin{frame} \frametitle{\ \ \ \ Finite group algebras: Basics}

\begin{itemize}
\item[$\circled{$\ast$}$] Let $\mathbf{k}$ be any commutative ring. (Usually
$\mathbb{Z}$, $\mathbb{Q}$ or a polynomial ring.)

\item[$\circled{$\ast$}$] Let $G$ be a finite group. (We will only use
symmetric groups.)

\item[$\circled{$\ast$}$] Let $\mathbf{k}\left[  G\right]  $ be the group
algebra of $G$ over $\mathbf{k}$. Its elements are formal $\mathbf{k}$-linear
combinations of elements of $G$. The multiplication is inherited from $G$ and
extended bilinearly.

\pause

\item \textbf{Example:} Let $G$ be the symmetric group $S_{3}$ on the set
$\left\{  1,2,3\right\}  $. For $i\in\left\{  1,2\right\}  $, let $s_{i}\in
S_{3}$ be the simple transposition that swaps $i$ with $i+1$. Then, in
$\mathbf{k}\left[  G\right]  =\mathbf{k}\left[  S_{3}\right]  $, we have%
\begin{align*}
\left(  1+s_{1}\right)  \left(  1-s_{1}\right)   &  =
\textcolor{blue}{1}+\textcolor{red}{s_{1}}-\textcolor{red}{s_{1}}
-\textcolor{blue}{s_{1}^2}=0
\end{align*}
(since $\textcolor{blue}{s_1^2} = \textcolor{blue}{1}$);
\pause
\begin{align*}
\left(  1+s_{2}\right)  \left(  1+s_{1}+s_{1}s_{2}\right)   &  =1+s_{2}%
+s_{1}+s_{2}s_{1}+s_{1}s_{2}+s_{2}s_{1}s_{2} \\
&=\sum_{w\in S_{3}}w.
\end{align*}


\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Finite group algebras: $L\left(a\right)$ and $R\left(a\right)$}

\begin{itemize}
\item[$\circled{$\ast$}$] For each $a\in\mathbf{k}\left[  G\right]  $, we
define two $\mathbf{k}$-linear maps%
\begin{align*}
L\left(  a\right)  :\mathbf{k}\left[  G\right]   &  \rightarrow\mathbf{k}%
\left[  G\right]  ,\\
x  &  \mapsto ax\ \ \ \ \ \ \ \ \ \ \left(  \text{\textquotedblleft left
multiplication by }a\text{\textquotedblright}\right)
\end{align*}
and%
\begin{align*}
R\left(  a\right)  :\mathbf{k}\left[  G\right]   &  \rightarrow\mathbf{k}%
\left[  G\right]  ,\\
x  &  \mapsto xa\ \ \ \ \ \ \ \ \ \ \left(  \text{\textquotedblleft right
multiplication by }a\text{\textquotedblright}\right)  .
\end{align*}
(So $L\left(  a\right)  \left(  x\right)  =ax$ and $R\left(  a\right)  \left(
x\right)  =xa$.)
\vspace{1pc}


\pause
\item Both $L\left(  a\right)  $ and $R\left(  a\right)  $
% belong to the
% endomorphism ring $\operatorname*{End}\nolimits_{\mathbf{k}}\left(
% \mathbf{k}\left[  G\right]  \right)  $
are endomorphisms of the $\mathbf{k}$-module
$\mathbf{k}\left[  G\right]  $,
that is, essentially,
% This ring is essentially a $\left\vert
% G\right\vert \times\left\vert G\right\vert $-matrix ring over $\mathbf{k}$.
$\abs{G} \times \abs{G}$-matrices...
%Thus, $L\left(  a\right)  $ and $R\left(  a\right)  $ can be viewed as
%$\left\vert G\right\vert \times\left\vert G\right\vert $-matrices...

\pause

\item ... and thus have kernels, characteristic polynomials, eigenvalues,
eigenvectors, etc.

\pause

\item The eigenvalues of $L\tup{a}$ or $R\tup{a}$
are the same (and have the same multiplicities).
We call them the \defn{eigenvalues} of $a$.

% \pause\pause

% \only<4>{\item Studying $a$, $L\left(  a\right)  $ and $R\left(  a\right)  $ is often
% (but not always) equivalent, because the maps%
% \begin{align*}
% L  &  :\mathbf{k}\left[  G\right]  \rightarrow\operatorname*{End}%
% \nolimits_{\mathbf{k}}\left(  \mathbf{k}\left[  G\right]  \right)
% \ \ \ \ \ \ \ \ \ \ \text{and}\\
% R  &  :\underbrace{\left(  \mathbf{k}\left[  G\right]  \right)
% ^{\operatorname*{op}}}_{\text{opposite ring}}\rightarrow\operatorname*{End}%
% \nolimits_{\mathbf{k}}\left(  \mathbf{k}\left[  G\right]  \right)
% \end{align*}
% are two injective $\mathbf{k}$-algebra morphisms (known as the left and right
% regular representations of the group $G$).}

% \pause
% \only<5-6>{
% \item \textbf{Theorem 1.1.} Assume that $\mathbf{k}$ is a field. Let
% $a\in\mathbf{k}\left[  G\right]  $. Then, the two linear endomorphisms
% $L\left(  a\right)  $ and $R\left(  a\right)  $ are conjugate in
% $\operatorname*{End}\nolimits_{\mathbf{k}}\left(  \mathbf{k}\left[  G\right]
% \right)  $ (that is, similar as matrices).

% Thus, they have the same eigenvalues (with the same
% multiplicities, both algebraic and geometric).}

% \pause\pause
% \item We define the \defn{eigenvalues} of $a$ to be
% the eigenvalues of $L\tup{a}$ or $R\tup{a}$.

\vspace{10pc}

\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Finite group algebras: The antipode}

\begin{itemize}
\item[$\circled{$\ast$}$] The \defn{antipode} of the group algebra
$\mathbf{k}\left[  G\right]  $ is defined to be the $\mathbf{k}$-linear map
\begin{align*}
S:\mathbf{k}\left[  G\right]   &  \rightarrow\mathbf{k}\left[  G\right]  ,\\
g  &  \mapsto g^{-1}\ \ \ \ \ \ \ \ \ \ \text{for each }g\in G.
\end{align*}
We shall write $a^{\ast}$ for $S\left(  a\right)  $.

\pause

\item[$\circled{$\ast$}$] \textbf{Proposition 1.2.} The antipode $S$ is an
involution:%
\[
a^{\ast\ast}=a\ \ \ \ \ \ \ \ \ \ \text{for all }a\in\mathbf{k}\left[
G\right]  ,
\]
and a $\mathbf{k}$-algebra anti-automorphism:%
\[
\left(  ab\right)  ^{\ast}=b^{\ast}a^{\ast}\ \ \ \ \ \ \ \ \ \ \text{for all
}a,b\in\mathbf{k}\left[  G\right]  .
\]

\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Symmetric groups: Notations}

\begin{itemize}
\item[$\circled{$\ast$}$] Let $\mathbb{N}:=\left\{  0,1,2,\ldots\right\}  $.

\item[$\circled{$\ast$}$] Let $\left[  k\right]  :=\left\{  1,2,\ldots
,k\right\}  $ for each $k\in\mathbb{N}$.

\pause

\item[$\circled{$\ast$}$] Now, fix a positive integer $n$, and let $S_{n}$ be
the \defn{$n$-th symmetric group}, i.e., the group of permutations of the
set $\left[  n\right]  $.

Multiplication in $S_{n}$ is composition:%
\begin{align*}
\left(  \alpha\beta\right)  \left(  i\right) 
&=\left(  \alpha\circ
\beta\right)  \left(  i\right)  =\alpha\left(  \beta\left(  i\right)  \right)
\\
&\ \ \ \ \ \ \ \ \ \ \text{for all }\alpha,\beta\in S_{n}\text{ and }%
i\in\left[  n\right]  .
\end{align*}

(\textbf{Warning:} SageMath disagrees!)

\pause

\item Much is known about the symmetric group algebra and its modules
(Young, Frobenius, James, ...; classical books by
\redhref{https://store.doverpublications.com/products/9780486316338}{Rutherford},
\redhref{https://doi.org/10.1007/BFb0067708}{James},
\redhref{https://doi.org/10.1017/CBO9781107340732}{James/Kerber},
\redhref{https://doi.org/10.1007/978-1-4757-6804-6}{Sagan},
recent ones by
\redhref{https://doi.org/10.1007/978-3-030-98025-2}{Howe},
\redhref{https://doi.org/10.1201/9781315371016}{Meliot};
nice introductions by
\redhref{https://www.ma.rhul.ac.uk/~uvah099/Maths/Sym/SymGroup2014.pdf}{Wildon}
and
\redhref{https://eudml.org/doc/287582}{Bremner/Madariaga/Peresi}).

Our focus here are specific elements of it.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The YJM elements}

\begin{itemize}
\item[$\circled{$\ast$}$] For each $k\in\left[  n\right]  $, we define the
\defn{$k$-th Young--Jucys--Murphy (YJM) element}%
\[
J_{k} := (1,k) + (2,k) + \cdots + (k-1,k)
\in\mathbf{k}\left[  S_{n}\right]
\]
(a sum of transpositions).


\only<1>{\item \textbf{Note.} We have $J_{1}=0$. Also, $J_{k}^{\ast}=J_{k}$ for each
$k\in\left[  n\right]  $.}

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 3.1 (Jucys, Murphy).} The YJM elements $J_{1}%
,J_{2},\ldots,J_{n}$ commute:
\[
J_{i}J_{j}=J_{j}J_{i} \text{ for all } i,j .
\]

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 3.2 (Jucys, Murphy).}
The eigenvalues of $J_{k}$ over $\mathbb{Q}$ are the integers
\[
-k+1, -k+2, \ldots, k-1,
\]
except that $0$ is sometimes missing (for $k \in \set{2,3}$).

\pause

\item The rest of the eigentheory (eigenvectors, multiplicities) is
also well-understood (in terms of standard Young tableaux).

\pause

\item The YJM elements are both an example of the type of elements
we will study, and a useful tool for other families.
\end{itemize}

\vspace{9pc}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The card shuffling point of view}

\begin{itemize}

\item Permutations are often visualized as shuffled decks of cards:

\[%
\begin{tabular}
[c]{|c|c|}%
\textbf{algebraic combinatorics} & \textbf{probability theory}\\\hline\hline
\multicolumn{1}{|r|}{permutation $\sigma\in S_{n}$} &
\multicolumn{1}{|r|}{state (deck of cards)}\\\hline
\multicolumn{1}{|r|}{element $\sum\limits_{\sigma\in S_{n}}a_{\sigma}\sigma
\in\mathbf{k}\left[  S_{n}\right]  $} & \multicolumn{1}{|r|}{random
state}\\\hline
\multicolumn{1}{|r|}{endomorphism of $\mathbf{k}\left[  S_{n}\right]  $} &
\multicolumn{1}{|r|}{random shuffle}\\\hline
\multicolumn{1}{|r|}{endomorphism $L\left(  a\right)  $} &
\multicolumn{1}{|r|}{random shuffle}\\
\multicolumn{1}{|r|}{for $a\in\mathbf{k}\left[  S_{n}\right]  $} &
\multicolumn{1}{|r|}{by card labels}\\\hline
\multicolumn{1}{|r|}{endomorphism $R\left(  a\right)  $} &
\multicolumn{1}{|r|}{random shuffle}\\
\multicolumn{1}{|r|}{for $a\in\mathbf{k}\left[  S_{n}\right]  $} &
\multicolumn{1}{|r|}{by positions}\\\hline
\end{tabular}
\]


% Imagine a deck of cards labeled $1,2,\ldots,n$.

% A permutation $\sigma\in S_{n}$ corresponds to the \defn{state} in which the
% cards are arranged $\sigma\left(  1\right)  ,\sigma\left(  2\right)
% ,\ldots,\sigma\left(  n\right)  $ from top to bottom.

% \pause

% \item A \defn{random state} is an element $\sum\limits_{\sigma\in S_{n}%
% }a_{\sigma}\sigma$ of $\mathbb{R}\left[  S_{n}\right]  $ whose coefficients
% $a_{\sigma}\in\mathbb{R}$ are nonnegative and add up to $1$. This is
% interpreted as a distribution on the $n!$ possible states, where $a_{\sigma}$
% is the probability for the deck to be in state $\sigma$.

% \pause

% \only<3-4>{
% \item We drop the \textquotedblleft add up to $1$\textquotedblright%
% \ condition, and only require that $\sum_{\sigma\in S_{n}}a_{\sigma}>0$. The
% probabilities must then be divided by $\sum_{\sigma\in S_{n}}a_{\sigma}$.
% }

% \only<4>{
% \item For instance, $1+(1,2,3)$ corresponds to
% the random state in which the deck is sorted as $1,2,3$ with probability
% $\dfrac{1}{2}$ and sorted as $2,3,1$ with probability $\dfrac{1}{2}$.
% }

% \pause \pause

% \item An $\mathbb{R}$-vector space endomorphism of $\mathbb{R}\left[
% S_{n}\right]  $, such as $L\left(  a\right)  $ or $R\left(  a\right)  $ for
% some $a\in\mathbb{R}\left[  S_{n}\right]  $, acts as a \defn{(random)
% shuffle}, i.e., a transformation of random states. This is just the standard
% way how Markov chains are constructed from transition matrices.

% \pause

\item For example, if $k>1$, then the right multiplication $R\left(
J_{k}\right)  $ by the YJM element $J_{k}$ corresponds to swapping the $k$-th
card with some card above it (chosen uniformly at random).

% \pause

% \item Transposing such a matrix means time-reversing the random shuffle.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Bottom-to-random and random-to-bottom shuffles: definitions}

\begin{itemize}
\item[$\circled{$\ast$}$] Another family of elements of $\mathbf{k}\left[
S_{n}\right]  $ are the \defn{$k$-bottom-to-random shuffles}%
\[
\mathcal{B}_{n,k}:=\sum_{\substack{\sigma\in S_{n};\\\sigma^{-1}\left(
1\right)  <\sigma^{-1}\left(  2\right)  <\cdots<\sigma^{-1}\left(  n-k\right)
}}\sigma
\]
defined for all $k\in\left\{  0,1,\ldots,n\right\}  $. Thus,%
\begin{align*}
\mathcal{B}_{n,n}  &  =\mathcal{B}_{n,n-1}=\sum_{\sigma\in S_{n}}\sigma;\\
\mathcal{B}_{n,1}  &  =\sum_{i=1}^{n} (n,n-1,\ldots,i);\\
\mathcal{B}_{n,0}  &  =\operatorname*{id}.
\end{align*}
We set $\mathcal{B}_{n}:=\mathcal{B}_{n,1}$.

\pause

\only<2>{
\item As a random shuffle, $\mathcal{B}_{n,k}$ (to be precise, $R\left(
\mathcal{B}_{n,k}\right)  $) takes the bottom $k$ cards and moves them to
random positions.

Its antipode $\mathcal{B}_{n,k}^{\ast}$ takes $k$ random cards and moves them
to the bottom positions.
}

\pause

\item $\mathcal{B}_{n}:=\mathcal{B}_{n,1}$ is known as the
\defn{bottom-to-random shuffle} or the \defn{Tsetlin library}.

\vspace{9pc}

\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Bottom-to-random and random-to-bottom shuffles: facts}

\begin{itemize}

\item \textbf{Theorem 5.1 (Diaconis, Fill, Pitman).} We have
\[
\mathcal{B}_{n,k+1}=\left(  \mathcal{B}_{n}-k\right)  \mathcal{B}%
_{n,k}\ \ \ \ \ \ \ \ \ \ \text{for each }k\in\left\{  0,1,\ldots,n-1\right\}
.
\]

\pause

\item \textbf{Corollary 5.2.} The $n+1$ elements $\mathcal{B}_{n,0}%
,\mathcal{B}_{n,1},\ldots,\mathcal{B}_{n,n}$ commute and are polynomials in
$\mathcal{B}_{n}$, namely%
\[
\mathcal{B}_{n,k}=\prod_{i=0}^{k-1}\left(  \mathcal{B}_{n}-i\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }k\in\left\{  0,1,\ldots,n\right\}  .
\]

\pause


\item \textbf{Theorem 5.3 (Wallach).} The eigenvalues of $\mathcal{B}%
_{n}$ over $\mathbb{Q}$ are
\[
0, 1, 2, \ldots, n-2, n .
\]

\pause


\item These are not hard to prove in this order. See
\redurl{https://mathoverflow.net/questions/308536} for the details.

\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Bottom-to-random and random-to-bottom shuffles: more}

\begin{itemize}

\item More can be said: in particular, the multiplicities of the eigenvalues
$0,1,\ldots,n-2,n$ of $\mathcal{B}_{n}$ over $\mathbb{Q}$
are given by
\begin{align*}
\tup{\text{multiplicity of } k}
= \tup{\text{\# of $w \in S_n$ with exactly $k$ fixed points}}.
\end{align*}

\pause

\item The antipodes
\[
\mathcal{B}_{n,k}^{\ast}:=\sum_{\substack{\sigma\in S_{n};\\\sigma\left(
1\right)  <\sigma\left(  2\right)  <\cdots<\sigma\left(  n-k\right)  }}\sigma
\]
of $\mathcal{B}_{n,k}$ are known as the \defn{$k$-random-to-bottom shuffles}
and have the same properties (since $S$ is an algebra anti-automorphism).

\pause

\item Moreover, there are \defn{top-to-random} and \defn{random-to-top}
shuffles defined in the same way but with renaming $1,2,\ldots,n$ as
$n,n-1,\ldots,1$. They are just images of the $\mathcal{B}_{n,k}$ and
$\mathcal{B}_{n,k}^{\ast}$ under the automorphism $a\mapsto w_{0}aw_{0}^{-1}$
of $\mathbf{k}\left[  S_{n}\right]  $, where $w_{0}$ is the permutation with
one-line notation $\left(  n,n-1,\ldots,1\right)  $.

Thus, top vs. bottom is mainly a matter of notation.

\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Bottom-to-random and random-to-bottom shuffles: references}

\begin{itemize}

\item Main references:

\begin{itemize}
\item \redhref{https://doi.org/10.2969/aspm/01410123}{Nolan R. Wallach,
\textit{Lie Algebra Cohomology and Holomorphic Continuation of Generalized
Jacquet Integrals}, 1988, Appendix}.

\item
\redhref{https://statweb.stanford.edu/~cgates/PERSI/papers/randomshuff92.pdf}{Persi
Diaconis, James Allen Fill and Jim Pitman, \textit{Analysis of Top to Random
Shuffles}, 1992}.
\end{itemize}
\end{itemize}


\section{Random-to-random shuffles}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Random-to-random shuffles: Definition}

\begin{itemize}
\item[$\circled{$\ast$}$] Here is a further family. For each $k\in\left\{
0,1,\ldots,n\right\}  $, we let%
\[
\mathcal{R}_{n,k}:=\sum_{\sigma\in S_{n}}\operatorname*{noninv}\nolimits_{n-k}%
\left(  \sigma\right)  \cdot\sigma,
\]
where $\operatorname*{noninv}\nolimits_{n-k}\left(  \sigma\right)  $ denotes
the number of $\left(  n-k\right)  $-element subsets of $\left[  n\right]  $
on which $\sigma$ is increasing. This is called the
\defn{$k$-random-to-random shuffle}.

\pause

\only<2>{
\item \textbf{Example:} Writing permutations in one-line notation,%
\begin{align*}
\mathcal{R}_{4,2}  &
=6[1,2,3,4]+5[1,2,4,3]+5[1,3,2,4]+4[1,3,4,2]\\
&  \ \ \ \ \ \ \ \ \ \ +4[1,4,2,3]+3[1,4,3,2]+5[2,1,3,4]+4[2,1,4,3]\\
&  \ \ \ \ \ \ \ \ \ \ +4[2,3,1,4]+3[2,3,4,1]+3[2,4,1,3]+2[2,4,3,1]\\
&  \ \ \ \ \ \ \ \ \ \ +4[3,1,2,4]+3[3,1,4,2]+3[3,2,1,4]+2[3,2,4,1]\\
&  \ \ \ \ \ \ \ \ \ \ +2[3,4,1,2]+[3,4,2,1]+3[4,1,2,3]+2[4,1,3,2]\\
&  \ \ \ \ \ \ \ \ \ \ +2[4,2,1,3]+[4,2,3,1]+[4,3,1,2].
\end{align*}
}

\pause

\item \textbf{Note:} $\mathcal{R}_{n,0}=\operatorname*{id}$ and $\mathcal{R}%
_{n,n-1}=n\sum_{\sigma\in S_{n}}\sigma$ and $\mathcal{R}_{n,n}=\sum_{\sigma\in
S_{n}}\sigma$.

\pause

\item The card-shuffling interpretation of $\mathcal{R}_{n,k}$ is
\textquotedblleft pick any $k$ cards from the deck and move them to $k$
randomly chosen positions\textquotedblright.
\end{itemize}

\vspace{9pc}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Random-to-random shuffles: Two surprises}

\begin{itemize}
\item[$\circled{$\ast$}$] \textbf{Theorem 6.1 (Reiner, Saliola, Welker).} The
$n+1$ elements $\mathcal{R}_{n,0},\mathcal{R}_{n,1},\ldots,\mathcal{R}_{n,n}$
commute (but are not polynomials in $\mathcal{R}_{n,1}$ in general).

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 6.2 (Dieker, Saliola,
Lafreni\`{e}re).} The eigenvalues of each $\mathcal{R}_{n,k}$ over
$\mathbb{Q}$ are integers. For example, the eigenvalues of $\mathcal{R}_{n,1}$
form a subset of
\[
\set{0, 1, 2, \ldots, n^2}.
\]
The exact factors can be given in terms of certain statistics on Young diagrams.

\end{itemize}


\end{frame} \begin{frame} \frametitle{\ \ \ \ Random-to-random shuffles: References}

\begin{itemize}
\item Main references: the \textquotedblleft classics\textquotedblright

\begin{itemize}
\item \redhref{https://arxiv.org/abs/1102.2460}{Victor Reiner, Franco Saliola,
Volkmar Welker, \textit{Spectra of Symmetrized Shuffling Operators},
arXiv:1102.2460}.

\item \redhref{https://doi.org/10.1016/j.aim.2017.10.034}{A.B. Dieker, F.V.
Saliola, \textit{Spectral analysis of random-to-random Markov chains}, 2018}.

\item \redhref{https://arxiv.org/abs/1912.07718}{Nadia Lafreni\`{e}re,
\textit{Valeurs propres des op\'{e}rateurs de m\'{e}langes sym\'{e}tris\'{e}s}%
, thesis, 2019}.
\end{itemize}

and the two recent preprints

\begin{itemize}
\item \redhref{https://arxiv.org/abs/2407.08644}{Ilani Axelrod-Freed, Sarah
Brauner, Judy Hsin-Hui Chiang, Patricia Commins, Veronica Lang,
\textit{Spectrum of random-to-random shuffling in the Hecke algebra},
arXiv:2407.08644.}

\item \redhref{https://www.cip.ifi.lmu.de/~grinberg/algebra/r2r2.pdf}{Sarah
Brauner, Patricia Commins, Darij Grinberg, Franco Saliola, \textit{The
q-deformed random-to-random family in the Hecke algebra}, arXiv:2503.17580.}
\end{itemize}
\end{itemize}


\end{frame} \begin{frame} \frametitle{\ \ \ \ Random-to-random shuffles: What we do}

\begin{itemize}

\item The \textquotedblleft classical\textquotedblright\ proofs are
complicated, technical and long.

In this talk, I will outline some parts of the two recent preprints, including
a simpler proof of Theorem 6.1 and most of Theorem 6.2. (The full proof of
Theorem 6.2 is still long and hard.)

Moreover, I will show how all these results can be generalized to the
\textbf{(Iwahori--)Hecke algebra} $\mathcal{H}_{n}=\mathcal{H}_{n}\left(
q\right)  $, a $q$-deformation of $\mathbf{k}\left[  S_{n}\right]  $.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ $\mathcal{R}$ vs. $\mathcal{B}$}

\begin{itemize}
\item The first step is a formula that is easy to prove combinatorially:

\item[$\circled{$\ast$}$] \textbf{Proposition 6.3.} For each $k\in\left\{
0,1,\ldots,n\right\}  $, we have%
\[
\mathcal{R}_{n,k}=\dfrac{1}{k!}\cdot\mathcal{B}_{n,k}^{\ast}\,\mathcal{B}%
_{n,k}.
\]

\pause

\item However, the $\mathcal{B}_{n,k}$ do not commute with the $\mathcal{B}%
_{n,k}^{\ast}$, so this is not by itself an answer.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The recursion}

\begin{itemize}
\item[$\circled{$\ast$}$] \textbf{Theorem 6.4 (Brauner--Commins--G.--Saliola
2025).} For any $1\leq k\leq n$, we have
\[
\hspace{-1.5pc}
\mathcal{B}_{n}\,\mathcal{R}_{n,k}=\underbrace{\left(\mathcal{R}%
_{n-1,k}+\left(  \left(n+1-k\right) + J_{n}\right)
\,\mathcal{R}_{n-1,k-1}\right)  }_{=:\mathcal{W}_{n,k}}\mathcal{B}_{n}.
\]


\pause

\item The $k=1$ case was done in
Axelrod-Freed--Brauner--Chiang--Commins--Lang 2024; inspired by
Lafreni\`ere 2019 and Dieker--Saliola 2018.

\item The proof takes about 5 pages, relying on some more elementary
computations from prior work (ca. 10--15 pages in total).

\pause

\item This recursion does not actually compute $\mathcal{R}_{n,k}$. But it
says enough about $\mathcal{R}_{n,k}$ to be the key to our proofs.

\item Note also that $\mathcal{R}_{n,k}\in\mathcal{B}_{n}^{\ast}%
\,\kk[S_n]$ by its definition (when $k\geq1$). This makes the recursion
so useful.
\end{itemize}

\vspace{9pc}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Commutativity of random-to-random}

\begin{itemize}
\item Theorem 6.4 leads fairly easily to a proof of commutativity (Theorem 6.1).

Indeed, inducting on $n$, we observe that the $\mathcal{W}_{n,k}$s all commute
by the induction hypothesis (and the easy fact that $J_{n}$ commutes with
everything in $\kk[S_{n-1}]$). Thus, using
$\mathcal{B}_n\, {\blue \mathcal{R}_{n,k}}
= {\blue \mathcal{W}_{n,k}}\, \mathcal{B}_n$, we find
\begin{align*}
\mathcal{B}_{n}\,{\blue \mathcal{R}_{n,i}\,\mathcal{R}_{n,j}}
&  = {\blue \mathcal{W}_{n,i}}\,\mathcal{B}_{n}\,{\blue \mathcal{R}_{n,j}}
= {\blue \mathcal{W}_{n,i}\,\mathcal{W}_{n,j}}\,\mathcal{B}_{n}\\
&  = {\blue \mathcal{W}_{n,j}\,\mathcal{W}_{n,i}}\,\mathcal{B}_{n}
= {\blue\mathcal{W}_{n,j}}\,\mathcal{B}_{n}\,{\blue \mathcal{R}_{n,i}}
= \mathcal{B}_{n}\, {\blue \mathcal{R}_{n,j}\,\mathcal{R}_{n,i}}.
\end{align*}


Remains to get rid of the $\mathcal{B}_{n}$ factor at the front. Recall that
all $\mathcal{R}_{n,i}$ (except for the trivial $\mathcal{R}_{n,0}$) lie in
$\mathcal{B}_{n}^{\ast}\,\kk[S_n]$. But it can be shown that
$\mathcal{B}_{n}\,\mathcal{B}_{n}^{\ast}\,a=0$ entails
$\mathcal{B}_{n}^{\ast}\,a=0$ (positivity trick! cf. linear algebra:
$\operatorname*{Ker}\left(  A^{T}A\right)  =\operatorname*{Ker}A$ for real
matrix $A$).

\item Alternatively, the trick can also be avoided (see our preprint).
\end{itemize}


\section{\textquotedblleft Integrality\textquotedblright\ of eigenvalues}

\end{frame} \begin{frame} \frametitle{\ \ \ \ Two approaches to eigenvalues}

\begin{itemize}
\item Now to Theorem 6.2: Why are all eigenvalues of $\mathcal{R}_{n,k}$
integers? (Nonnegativity follows from symmetry.)

\pause

\item We have two proofs:
\begin{itemize}
\item one -- quite elementary -- using a little theory of
``split elements'', which can help answer such questions in general.

\item one -- longer and more technical -- using the seminormal basis
of $\kk[S_n]$; this gives a formula for the eigenvalues.

\end{itemize}
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ A formula for eigenvalues}

\begin{itemize}

{\small
\item \textbf{Theorem 10.1.} Let $n,k\geq0$. The eigenvalues of $R\left(
\mathcal{R}_{n,k}\right)  $ on $\kk[S_n]$ are the elements%
\[
\mathcal{E}_{\lambda\setminus\mu}(k)
:= \sum_{\textcolor{green!40!black}{j}<(\ell
_{1}<\ell_{2}<\cdots<\ell_{k})\leq n}\ \prod_{m=1}^{k}
\left(\ell_{m}+1-m+\textcolor{blue}{\mathsf{c}}_{\textcolor{red}{\mathfrak{t}^{\lambda\setminus\mu}}}\left(  \ell
_{m}\right)\right)
\]
for all horizontal strips $\lambda\setminus\mu$ that satisfy
$\lambda \vdash n$ and
$\textcolor{violet}{d^{\mu}}\neq0$. Here,

\begin{itemize}
\item \small $\textcolor{violet}{d^{\mu}}$ denotes the number of
\defn{desarrangement tableaux} of
shape $\mu$ (that is, standard tableaux of shape $\mu$ whose smallest
non-descent is even);

\item \small $\textcolor{green!40!black}{j}$ is the size of $\mu$;

\item \small $\textcolor{red}{\mathfrak{t}^{\lambda\setminus\mu}}$ is the skew tableau of shape
$\lambda\setminus\mu$ obtained by filling in the boxes of $\lambda\setminus
\mu$ with $j+1,j+2,\ldots,n$ from top to bottom;

\item \small $\textcolor{blue}{\mathsf{c}_{\mathfrak{t}^{\lambda\setminus\mu}}\left(  p\right)}  =y-x$
if the cell of $\mathfrak{t}^{\lambda\setminus\mu}$ containing the entry $p$
is $\left(  x,y\right)  $.
\end{itemize}

Moreover, the multiplicity of each such eigenvalue $\mathcal{E}_{\lambda
\setminus\mu}(k)$ is $d^{\mu}f^{\lambda}$, where $f^{\lambda}$ is the number
of standard tableaux of shape $\lambda$ (unless there are collisions).
% \pause

% \item The right hand side can be rewritten as an evaluation of a factorial
% $h$-polynomial, but this may not be much of a simplification.
}
\end{itemize}

\section{The Hecke algebra $\mathcal{H}_{n}$}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Definition}

\begin{itemize}
\item[$\circled{$\ast$}$] Let $q\in\mathbf{k}$ be a parameter.

The $n$-th \defn{Hecke algebra} (or \defn{Iwahori--Hecke algebra} to be
more historically correct) is a $q$-deformation of the group algebra
$\mathbf{k}\left[  S_{n}\right]  $. It has generators $T_{1},T_{2}%
,\ldots,T_{n-1}$ and relations%
\begin{align*}
T_{i}^{2}  &  =\left(  q-1\right)  T_{i}+q\ \ \ \ \ \ \ \ \ \ \text{for all
}i\in\left[  n-1\right]  ;\\
T_{i}T_{j}  &  =T_{j}T_{i}\ \ \ \ \ \ \ \ \ \ \text{whenever }\left\vert
i-j\right\vert >1;\\
T_{i}T_{i+1}T_{i}  &  =T_{i+1}T_{i}T_{i+1}\ \ \ \ \ \ \ \ \ \ \text{for all
}i\in\left[  n-2\right]  .
\end{align*}
We call this algebra $\mathcal{H}_{n}$.

\pause

\item[$\circled{$\ast$}$] For $q=1$, this is the group algebra $\mathbf{k}%
\left[  S_{n}\right]  $ (and the generator $T_{i}$ is the simple transposition
$s_{i}=(i,i+1)$).

\pause

\item[$\circled{$\ast$}$] For general $q$, it still is a free $\mathbf{k}%
$-module of rank $n!$, with a basis $\left(  T_{w}\right)  _{w\in S_{n}}$
indexed by permutations $w\in S_{n}$. The basis vectors are defined by
$T_{w}:=T_{i_{1}}T_{i_{2}}\cdots T_{i_{k}}$, where
$s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}$ is a reduced expression for $w$.
For $q=1$, this $T_{w}$ is just $w$.
\end{itemize}


\section{The Hecke algebra $\mathcal{H}_{n}$}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: What for?}

\begin{itemize}
\item[$\circled{$\ast$}$] Much of the theory of $\mathbf{k}\left[
S_{n}\right]  $ exists in a subtler form for $\mathcal{H}_{n}$. Sometimes, the
added difficulty brings the best proofs to light.

\pause

\item $\mathcal{H}_{n}$ shows up in many places: as a better-behaved model for
the modular representation theory of $S_{n}$; as a nonunital subalgebra of
$\mathbf{k}\left[  \operatorname*{GL}\nolimits_{n}\left(  \mathbb{F}%
_{q}\right)  \right]  $ (when $q$ is a prime power); as an algebraic model for
some random walks (when $q\in\left[  0,1\right]  $), .... It also can be
defined for other types of groups.

Cf.
\redhref{https://staff.fnwi.uva.nl/a.l.kret/Galoistheorie/taylor-wiles.pdf}{Taylor--Wiles,
\textit{Ring-Theoretic Properties of Certain Hecke Algebras}, 1995}.

\pause

\item I think of $\mathcal{H}_{n}$ as a \textquotedblleft
biased\textquotedblright\ version of $\mathbf{k}\left[  S_{n}\right]  $, which
breaks the symmetry in favor of \textquotedblleft entropy\textquotedblright.
\end{itemize}


\section{The Hecke algebra $\mathcal{H}_{n}$}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Structure}

\begin{itemize}

\item[$\circled{$\ast$}$] \textbf{Theorem 7.1 (Dipper--James).} Assume that
$\mathbf{k}$ is a field, and that $q\neq0$ and $q^{n!}\neq1$. Then, the Hecke
algebra $\mathcal{H}_{n}$ is semisimple and in fact isomorphic to
$\mathbf{k}\left[  S_{n}\right]  $ (in a nontrivial way).

Thus, its irreducible representations are again some kind of Specht modules
$\mathcal{S}^{\lambda}$, deforming the ones for $\mathbf{k}\left[
S_{n}\right]  $.

\item This was proved for generic $q$ by
\redhref{https://doi.org/10.1112/plms/s3-52.1.20}{Dipper/James
(\textit{Representations of Hecke algebras of general linear groups}, 1984)},
and in the general case by
\redhref{https://doi.org/10.1006/jabr.1995.1079}{Murphy (\textit{The
Representations of Hecke algebras of type }$A_{n}$, 1995)}, modulo the
semisimplicity, which can be found in most texts now (e.g.,
\redhref{https://bookstore.ams.org/ulect-15}{Mathas, \textit{Iwahori-Hecke
Algebras and Schur Algebras of the Symmetric Group}, 1999}).

\item In the following, unless I say otherwise, I am working in $\mathcal{H}%
_{n}$.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: The antipode}

\begin{itemize}
\item[$\circled{$\ast$}$] The antipode $S:\mathbf{k}\left[  S_{n}\right]
\rightarrow\mathbf{k}\left[  S_{n}\right]  $ can be generalized to the Hecke
algebra. The generalization is the $\mathbf{k}$-linear map%
\begin{align*}
S:\mathcal{H}_{n}  &  \rightarrow\mathcal{H}_{n},\\
T_{w}  &  \mapsto T_{w^{-1}}\ \ \ \ \ \ \ \ \ \ \left(  \text{thus }%
T_{i}\mapsto T_{i}\right)  .
\end{align*}


\item[$\circled{$\ast$}$] Again, this is a $\mathbf{k}$-algebra
anti-automorphism and an involution.

\item[$\circled{$\ast$}$] Again, we write $a^{\ast}$ for $S\left(  a\right)  $.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: The YJM elements}

\begin{itemize}
\item[$\circled{$\ast$}$] When $q\in\mathbf{k}$ is invertible, we can define
the \defn{Young--Jucys--Murphy (YJM) elements in the Hecke algebra
}$\mathcal{H}_{n}$. These are the elements $J_{1},J_{2},\ldots,J_{n}%
\in\mathcal{H}_{n}$ defined by%
\[
J_{k}:=\sum_{i=1}^{k-1}q^{i-k} T_{(i,k)}\in
\mathcal{H}_{n}.
\]
Setting $q=1$ recovers the YJM elements of $\mathbf{k}\left[  S_{n}\right]  $.

\pause

\item[$\circled{$\ast$}$] Again, $J_{1}=0$.
Also, $J_{k}^{\ast}=J_{k}$ for each $k\in\left[
n\right]  $.

\item[$\circled{$\ast$}$]  The elements $J_{1},J_{2},\ldots,J_{n}$ commute.

\item[$\circled{$\ast$}$]  The eigenvalues of each $J_{k}$ are
\[
\left[  -k+1\right]  _{q},\ \left[  -k+2\right]  _{q},\ \ldots,\ \left[
k-1\right]  _{q},
\]
where we are using the \defn{$q$-integers}%
\[
\left[  m\right]  _{q}:=\dfrac{1-q^{m}}{1-q}=%
\begin{cases}
1+q+q^{2}+\cdots+q^{m-1}, & \text{if }m\geq0;\\
-q^{-1}-q^{-2}-\cdots-q^{m}, & \text{if }m\leq0.
\end{cases}
\]
Their multiplicities are as in the $\mathbf{k}\left[  S_{n}\right]  $ case.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Bottom-to-random and back, 1}

\begin{itemize}
\item[$\circled{$\ast$}$] We define the \defn{$q$-deformed
$k$-bottom-to-random shuffles} $\mathcal{B}_{n,k}$ and the
\defn{$q$-deformed $k$-random-to-bottom shuffles} $\mathcal{B}%
_{n,k}^{\ast}$ for $k\in\left\{  0,1,\ldots,n\right\}  $ by%
\[
\mathcal{B}_{n,k}:=\sum_{\substack{\sigma\in S_{n};\\\sigma^{-1}\left(
1\right)  <\sigma^{-1}\left(  2\right)  <\cdots<\sigma^{-1}\left(  n-k\right)
}}T_{\sigma}\in\mathcal{H}_{n}%
\]
and%
\[
\mathcal{B}_{n,k}^{\ast}:=\sum_{\substack{\sigma\in S_{n};\\\sigma\left(
1\right)  <\sigma\left(  2\right)  <\cdots<\sigma\left(  n-k\right)
}}T_{\sigma}\in\mathcal{H}_{n}.
\]
Note that $\mathcal{B}_{n,0}=\mathcal{B}_{n,0}^{\ast}=1$. We also set
$\mathcal{B}_{n,k}=\mathcal{B}_{n,k}^{\ast}=0$ for $k>n$.
\end{itemize}


\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Bottom-to-random and back, 2}

\begin{itemize}

\item[$\circled{$\ast$}$] \textbf{Theorem 7.2
(Axelrod-Freed--Brauner--Chiang--Commins--Lang 2024).} We have%
\[
\mathcal{B}_{n,k}=\mathcal{B}_{n-k+1}\mathcal{B}_{n-k+2}\cdots\mathcal{B}%
_{n},
\]
where we arrange the Hecke algebras in a chain of inclusions:%
\[
\mathbf{k}=\mathcal{H}_{0}\subseteq\mathcal{H}_{1}\subseteq\mathcal{H}%
_{2}\subseteq\cdots.
\]

\end{itemize}


\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Bottom-to-random and back, 3}

\begin{itemize}


\item[$\circled{$\ast$}$] \textbf{Theorem 7.3 (essentially
Brauner--Commins--Reiner 2023, to be made explicit in Grinberg 2025+ on
$q$-deformed somewhere-to-below shuffles).} The $n+1$ elements $\mathcal{B}%
_{n,0},\mathcal{B}_{n,1},\ldots,\mathcal{B}_{n,n}$ commute and are polynomials
in $\mathcal{B}_{n}$, namely%
\[
\mathcal{B}_{n,k}=\prod_{i=0}^{k-1}\left(  \mathcal{B}_{n}-\left[  i\right]
_{q}\right)  \ \ \ \ \ \ \ \ \ \ \text{for each }k\in\left\{  0,1,\ldots
,n\right\}  .
\]

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 7.4 (same).} The eigenvalues
of $\mathcal{B}_{n}$ over $\QQ$ are
\[
\ive{0}_q, \ \ \ive{1}_q, \ \ \ive{2}_q, \ \ \ldots, \ \ \ive{n-2}_q,
\ \ \ive{n}_q.
\]

\pause

\item The proofs here are similar to the $q=1$ case, but attention needs to be
paid to the lengths of the permutations as they get multiplied.

\pause

\item There is a bespoke interpretation of $\mathcal{B}_{n}$ as a
\textquotedblleft$q$-Tsetlin library\textquotedblright, where decks of cards
are replaced by flags of vector subspaces of $\mathbb{F}_{q}^{n}$.
(See \redhref{https://arxiv.org/abs/2407.08644}{arXiv:2407.08644} for details.)
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Random-to-random, definition}

\begin{itemize}
\item[$\circled{$\ast$}$] We can also generalize the $k$-random-to-random
shuffles $\mathcal{R}_{n,k}$: For each $k\geq0$, we set%
\[
\mathcal{R}_{n,k}:=\dfrac{1}{\left[  k\right]  !_{q}}\,\mathcal{B}_{n,k}%
^{\ast}\,\mathcal{B}_{n,k}\in\mathcal{H}_{n},
\]
where we use the $q$-factorial $\left[  k\right]  !_{q}=\left[  1\right]
_{q}\left[  2\right]  _{q}\cdots\left[  k\right]  _{q}$.

\pause

\item[$\circled{$\ast$}$] The coefficients of $\mathcal{R}_{n,k}$ are actually
in $\mathbb{Z}\left[  q\right]  $, since the denominator can be cancelled.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Random-to-random, example}

\begin{itemize}

\item \textbf{Example:} Again using one-line notation,%
{\scriptsize
\begin{align*}
\mathcal{R}_{4,2}  &  =\left(  q^{4}+q^{3}+2q^{2}+q+1\right)  T_{[1,2,3,4]}%
+\left(  q^{3}+2q^{2}+q+1\right)  T_{[1,2,4,3]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{4}+q^{3}+q^{2}+q+1\right)  T_{[1,3,2,4]}%
+\left(  q^{3}+q^{2}+q+1\right)  T_{[1,3,4,2]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{3}+q^{2}+q+1\right)  T_{[1,4,2,3]}+\left(
q^{3}+q+1\right)  T_{[1,4,3,2]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{4}+q^{3}+2q^{2}+q\right)  T_{[2,1,3,4]}%
+\left(  q^{3}+2q^{2}+q\right)  T_{[2,1,4,3]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{4}+q^{3}+q^{2}+q\right)  T_{[2,3,1,4]}%
+\left(  q^{3}+q^{2}+q\right)  T_{[2,3,4,1]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{3}+q^{2}+q\right)  T_{[2,4,1,3]}+\left(
q^{3}+q\right)  T_{[2,4,3,1]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{4}+q^{3}+q^{2}+q\right)  T_{[3,1,2,4]}%
+\left(  q^{3}+q^{2}+q\right)  T_{[3,1,4,2]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{4}+q^{3}+q^{2}+q-1\right)  T_{[3,2,1,4]}%
+\left(  q^{3}+q^{2}+q-1\right)  T_{[3,2,4,1]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{3}+q\right)  T_{[3,4,1,2]}+\left(
q^{3}+q-1\right)  T_{[3,4,2,1]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{3}+q^{2}+q\right)  T_{[4,1,2,3]}+\left(
q^{3}+q\right)  T_{[4,1,3,2]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{3}+q^{2}+q-1\right)  T_{[4,2,1,3]}+\left(
q^{3}+q-1\right)  T_{[4,2,3,1]}\\
&  \ \ \ \ \ \ \ \ \ \ +\left(  q^{3}+q-1\right)  T_{[4,3,1,2]}%
+\textcolor{blue}{\left( q^{3}+q-2\right) T_{[4,3,2,1]}}.
\end{align*}
}
Note: The last coefficient becomes $0$ in the $q=1$ case!
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: The main theorems}

\begin{itemize}
\item We have been able to extend the main properties of $k$-random-to-random
shuffles from $\mathbf{k}\left[  S_{n}\right]  $ to $\mathcal{H}_{n}$:

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 7.5 (Brauner--Commins--G.--Saliola
2025).} The $n+1$ elements $\mathcal{R}_{n,0},\mathcal{R}_{n,1},\ldots
,\mathcal{R}_{n,n}$ of $\mathcal{H}_{n}$ commute.
% (but are not polynomials in $\mathcal{R}_{n,1}$ in general).

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 7.6 (Brauner--Commins--G.--Saliola
2025).} All eigenvalues of each $\mathcal{R}_{n,k}$ over a field $\mathbf{k}$
can be written as polynomials in $q$ with coefficients in $\mathbb{N}$.

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 7.7 (Brauner--Commins--G.--Saliola
2025).} If $\mathbf{k}$ is a field and $q$ is generic, then there is a basis
of $\mathcal{H}_{n}$ in which all the $\mathcal{R}_{n,k}$ (that is, all the
$R\left(  \mathcal{R}_{n,k}\right)  $) are diagonal.

\pause

\only<5>{
\item We also have complicated formulas for the eigenvalues and their
multiplicities; more on that later.
}
\pause

\item For $k=1$, the above was done in:

\begin{itemize}
\item \redhref{http://arxiv.org/abs/2407.08644v2}{Ilani Axelrod-Freed, Sarah
Brauner, Judy Hsin-Hui Chiang, Patricia Commins, Veronica Lang,
\textit{Spectrum of random-to-random shuffling in the Hecke algebra},
arXiv:2407.08644.}
\end{itemize}

We use this work in our proofs (mostly for computing the eigenvalues).
\end{itemize}


\section{The recursion and commutativity}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: The recursion}

\begin{itemize}

\item The proof of commutativity is similar to the $q=1$ case.
The recursion takes the following form:

\item[$\circled{$\ast$}$] \textbf{Theorem 8.1 (Brauner--Commins--G.--Saliola
2025, based on Axelrod-Freed--Brauner--Chiang--Commins--Lang 2024).} For any
$1\leq k\leq n$, we have
\[
\hspace{-1.5pc}
\mathcal{B}_{n}\,\mathcal{R}_{n,k}=\underbrace{\left(  q^{k}\,\mathcal{R}%
_{n-1,k}+\left(  \left[  n+1-k\right]  _{q}+q^{n+1-k}J_{n}\right)
\,\mathcal{R}_{n-1,k-1}\right)  }_{=:\mathcal{W}_{n,k}}\mathcal{B}_{n}.
\]

\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: A formula for eigenvalues}

\begin{itemize}

{\small
\item \textbf{Theorem 10.1.} Let $n,k\geq0$. The eigenvalues of $R\left(
\mathcal{R}_{n,k}\right)  $ on $\mathcal{H}_{n}$ are the elements%
\[
\mathcal{E}_{\lambda\setminus\mu}(k)
:= q^{nk-{\binom{k}{2}}}\sum_{\textcolor{green!40!black}{j}<(\ell
_{1}<\ell_{2}<\cdots<\ell_{k})\leq n}\ \prod_{m=1}^{k}q^{-\ell_{m}}[\ell
_{m}+1-m
+\textcolor{blue}{\mathsf{c}}_{\textcolor{red}{\mathfrak{t}^{\lambda\setminus\mu}}}\left(  \ell
_{m}\right)  ]_{q}%
\]
for all horizontal strips $\lambda\setminus\mu$ that satisfy
$\lambda \vdash n$ and
$\textcolor{violet}{d^{\mu}}\neq0$. Here,

\begin{itemize}
\item \small $\textcolor{violet}{d^{\mu}}$ denotes the number of
\defn{desarrangement tableaux} of
shape $\mu$ (that is, standard tableaux of shape $\mu$ whose smallest
non-descent is even);

\item \small $\textcolor{green!40!black}{j}$ is the size of $\mu$;

\item \small $\textcolor{red}{\mathfrak{t}^{\lambda\setminus\mu}}$ is the skew tableau of shape
$\lambda\setminus\mu$ obtained by filling in the boxes of $\lambda\setminus
\mu$ with $j+1,j+2,\ldots,n$ from top to bottom;

\item \small $\textcolor{blue}{\mathsf{c}_{\mathfrak{t}^{\lambda\setminus\mu}}\left(  p\right)}  =y-x$
if the cell of $\mathfrak{t}^{\lambda\setminus\mu}$ containing the entry $p$
is $\left(  x,y\right)  $.
\end{itemize}

Moreover, the multiplicity of each such eigenvalue $\mathcal{E}_{\lambda
\setminus\mu}(k)$ is $d^{\mu}f^{\lambda}$, where $f^{\lambda}$ is the number
of standard tableaux of shape $\lambda$ (unless there are collisions).
% \pause

% \item The right hand side can be rewritten as an evaluation of a factorial
% $h$-polynomial, but this may not be much of a simplification.
}
\end{itemize}


\section{\textquotedblleft Integrality\textquotedblright\ of eigenvalues}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: The splitting approach to eigenvalues, 1}

\begin{itemize}
\item Alternatively, the fact that all eigenvalues of $\mathcal{R}_{n,k}$
are in $\ZZ[q]$ can be proved in a more light-handed way,
using a theory of \textquotedblleft split elements\textquotedblright%
\ that can help answer such questions in general. Here is an outline:
%(Note that we do not get nonnegativity in this way.)

\pause

\item[$\circled{$\ast$}$] An element $a$ of a $\mathbf{k}$-algebra $A$ is said
to be \defn{split} (over $\mathbf{k}$) if there exist some scalars
$u_{1},u_{2},\ldots,u_{n}\in\mathbf{k}$ (not necessarily distinct) such that
$\prod\limits_{i=1}^{n}\left(  a-u_{i}\right)  =0$.

\pause

\item[$\circled{$\ast$}$] When $\mathbf{k}$ is an integral domain and $A$ is a
free $\mathbf{k}$-module of finite rank, this is the same as saying that
$R\left(  a\right)  $ has all eigenvalues in $\mathbf{k}$.

\pause

\item In particular, for $\mathbf{k}=\mathbb{Z}\left[  q\right]  $ and
$A=\mathcal{H}_{n}$, this means that all eigenvalues of $a$ are $\in
\mathbb{Z}\left[  q\right]  $. This is what we want to show for $a=\mathcal{R}%
_{n,k}$.

\pause

\item So we must show that $\mathcal{R}_{n,k}$ is split over $\mathbb{Z}%
\left[  q\right]  $.
\end{itemize}


\section{\textquotedblleft Integrality\textquotedblright\ of eigenvalues}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: The approach to eigenvalues, 2}

\begin{itemize}
\item So we must show that $\mathcal{R}_{n,k}$ is split over $\mathbb{Z}%
\left[  q\right]  $.

\pause

\item It suffices to show that $\mathcal{R}_{n,k}$ is split over
$\mathbb{Z}\left[  q,q^{-1}\right]  $ (Laurent polynomials), since then an
integral closure argument will yield that the eigenvalues are in fact
$\in\mathbb{Z}\left[  q\right]  $. This is easier because we have YJM elements
over $\mathbb{Z}\left[  q,q^{-1}\right]  $.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ General theory of split elements, 1}

\begin{itemize}
\item We prove several general properties of split elements (nice exercises on
commutative algebra!):

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 9.1.} If two commuting elements
$a,b\in A$ are split, then both $a+b$ and $ab$ are split.

\item[$\circled{$\ast$}$] \textbf{Corollary 9.2.} A commutative subalgebra of
$A$ generated by split elements consists entirely of split elements.

\pause

\item[$\circled{$\ast$}$] \textbf{Theorem 9.3.} If $b,c,f$ are elements of $A$
such that $f$ is split and such that $bc=fb$ and $c\in Ab$, then $c$ is split.

\pause

\item Theorem 9.3 is tailored to our use:
\[%
\begin{tabular}
[c]{|c|c|}\hline
$bc=fb$ & $c\in Ab$\\\hline
$\mathcal{B}_{n}\,\mathcal{R}_{n,k}=\mathcal{W}_{n,k}\,\mathcal{B}_{n}$ &
$\mathcal{R}_{n,k}\in\mathcal{H}_{n}$ $\mathcal{B}_{n}$\\\hline
\end{tabular}
\ \ \ \ .
\]
The splitness of $\mathcal{W}_{n,k}$ follows from the splitness of the
commuting elements $J_{n}$, $\mathcal{R}_{n-1,k-1}$ and $\mathcal{R}_{n-1,k}$
(induction!) by Corollary 9.2. We need the splitness of the YJM elements,
which was proved (e.g.) by Murphy.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ General theory of split elements, 2}

\begin{itemize}

\item Theorem 9.3 looks baroque, but in fact it easily decomposes into two
particular cases:

\textbf{Corollary 9.4.} If $ba$ is split, then $ab$ is also split.

\textbf{Corollary 9.5.} If $a$ is split and $b^{2}=ab$, then $b$ is split.

(Both times, $a,b\in A$ are arbitrary.)

\pause

\item The splitness theory proves easily that all eigenvalues of
$\mathcal{R}_{n,k}$ belong to $\mathbb{Z}\left[  q\right]  $, but it fails to
show that they belong to $\mathbb{N}\left[  q\right]  $. Indeed, it produces
\textquotedblleft phantom eigenvalues\textquotedblright\ which do not actually
appear; some of them have negative coefficients.
It also does not compute the multiplicities.

\pause

\item Our eigenvalue formula requires a different approach.
\end{itemize}


\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Some explicit eigenvalues}

\begin{itemize}

\item \small We also have explicit eigenvalue formulas for specific shapes and strips:%
\[
\mathcal{E}_{(n)\setminus\varnothing}(k)=[k]!_{q}%
%TCIMACRO{\QATOPD{[}{]}{n}{k}}%
%BeginExpansion
\genfrac{[}{]}{0pt}{}{n}{k}%
%EndExpansion
_{q}^{2};
\]%
\[
\mathcal{E}_{(n-1,1)\setminus(j,1)}(k)=\left[  k\right]  !_{q}%
%TCIMACRO{\QATOPD{[}{]}{n-j-1}{k}}%
%BeginExpansion
\genfrac{[}{]}{0pt}{}{n-j-1}{k}%
%EndExpansion
_{q}%
%TCIMACRO{\QATOPD{[}{]}{n+j}{k}}%
%BeginExpansion
\genfrac{[}{]}{0pt}{}{n+j}{k}%
%EndExpansion
_{q}\qquad\text{ for all }j\in\left[  n-1\right]  .
\]
But $\mathcal{E}_{\left(  4,1,1\right)  \setminus\left(  1,1\right)  }\left(
1\right)  $ is not a quotient of products of $q$-integers.
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The Hecke algebra: Open questions}

\begin{itemize}

\item \textbf{Question:} Any nicer formulas for the eigenvalues $\mathcal{E}%
_{\lambda\setminus\mu}\left(  k\right)  $ ?

\item \textbf{Question:} As polynomials in $q$, are the eigenvalues
$\mathcal{E}_{\lambda\setminus\mu}\left(  k\right)  $ unimodal?

\item \textbf{Question (Reiner):} How big is the subalgebra of $\mathbb{Q}%
\left[  S_{n}\right]  $ generated by $\mathcal{R}_{n,0},\mathcal{R}%
_{n,1},\ldots,\mathcal{R}_{n,n}$ ? Some small values:
{\footnotesize
\[
\hspace{-2.5pc}
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|c|c|c|c|c|}\hline
$n$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ & $9$ & $10$ & $11$ &
$12$\\\hline
$\dim\left(  \text{subalgebra}\right)  $ & $1$ & $2$ & $4$ & $7$ & $15$ & $30$
& $54$ & $95$ & $159$ & $257$ & $400$ & $613$\\\hline
\end{tabular}
\ \ \ \
\]
(sequence not in the OEIS as of 2025-05-21).}

The same numbers hold for the $q$-deformation!
\end{itemize}

\end{frame} \begin{frame} \frametitle{\ \ \ \ The affine Hecke algebra: Open questions}

\begin{itemize}


\item \textbf{Generalization (implicit in Reiner, Saliola, Welker).} For each
$k\in\left\{  0,1,\ldots,n\right\}  $, we let%
\[
\widetilde{\mathcal{R}}_{n,k}:=\sum_{\sigma\in S_{n}}\ \ \sum
_{\substack{I\subseteq\left[  n\right]  ;\\\left\vert I\right\vert
=n-k;\\\sigma\text{ increases on }I}}\sigma\otimes\prod_{i\in I}x_{i}%
\]
in the \defn{twisted group algebra}
\begin{align*}
&  \mathcal{T}:=\mathbf{k}\left[  S_{n}\right]  \otimes\mathbf{k}\left[
x_{1},x_{2},\ldots,x_{n}\right] \\
&  \text{with multiplication }\left(  \sigma\otimes f\right)  \left(
\tau\otimes g\right)  =\sigma\tau\otimes\tau^{-1}\left(  f\right)  g.
\end{align*}
Then, the $\widetilde{\mathcal{R}}_{n,0},\widetilde{\mathcal{R}}_{n,1}%
,\ldots,\widetilde{\mathcal{R}}_{n,n}$ commute.

\item This twisted group algebra $\mathcal{T}$ acts on $\mathbf{k}\left[
x_{1},x_{2},\ldots,x_{n}\right]  $ in two ways: by multiplication ($\left(
\sigma\otimes f\right)  \left(  p\right)  =\sigma\left(  fp\right)  $) or by
differentiation ($\left(  f\otimes\sigma\right)  \left(  p\right)
=\sigma\left(  f\left(  \partial\right)  \left(  p\right)  \right)  $). (In
either case, the $S_{n}$ part permutes the variables.)

\item \textbf{Question:} Simpler proof for this generalization? $q$%
-deformation? (The obvious one in the affine Hecke algebra does not work!)
\end{itemize}


\end{frame} \begin{frame} \frametitle{\ \ \ \ I thank}

\begin{itemize}
\item \textbf{Sarah Brauner, Patricia Commins} and \textbf{Franco Saliola} for
obvious reasons.

\item the \textbf{Mathematisches Forschungsinstitut Oberwolfach} for the
Research in Pairs program during which most of this was found.

\item \textbf{Pavel Etingof,
Nadia Lafreni\`{e}re, Martin Lorenz, Franco Saliola, Marcelo
Aguiar, Vic Reiner, Travis Scrimshaw, Theo Douvropoulos,
Volkmar Welker} for various ideas shared over the years.

\item \textbf{Lorenzo Vecchi} for the invitation.

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

\end{frame}

\end{document}