\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=Thursday, April 17, 2025 17:56:00}
%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}
\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}}}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\setlength\textheight{25cm}
\setlength\textwidth{15.5cm}
\newenvironment{noncompile}{}{}
\excludecomment{noncompile}
\ihead{One-sided cycle shuffles (talk)}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{The one-sided cycle shuffles, and other mysteries and wonders of the symmetric
group algebra [talk slides]}
\date{George Washington University, 2023-04-10 (Sections 1--12);\\
Temple University, 2023-10-16 (Sections 1--15);\\
Uppsala Universitet, 2024-03-26;\\
CAGE seminar, 2025-04-17 (Sections 1--15)}
\author{Darij Grinberg
\and joint work with Nadia Lafreni\`{e}re}
\maketitle

\begin{abstract}
{\small Elements in the group algebra of a symmetric group $S_{n}$ are known
to have an interpretation in terms of card shuffling. I will discuss a new
family of such elements, recently constructed by Nadia Lafreni\`{e}re: }

{\small Given a positive integer $n$, we define $n$ elements $\mathbf{t}%
_{1},\mathbf{t}_{2},\ldots,\mathbf{t}_{n}$ in the group algebra of $S_{n}$ by%
\begin{align*}
\mathbf{t}_{i}  &  =\text{the sum of the cycles }\left(  i\right)
,\ \ \left(  i,i+1\right)  ,\\
&  \ \ \ \ \ \ \ \ \ \ \ \ \left(  i,i+1,i+2\right)  ,\ \ \ldots,\ \ \left(
i,i+1,\ldots,n\right)  ,
\end{align*}
where the cycle $\left(  i\right)  $ is the identity permutation. The first of
them, $\mathbf{t}_{1}$, is known as the top-to-random shuffle and has been
studied by Diaconis, Fill, Pitman (among others). }

{\small The $n$ elements $\mathbf{t}_{1},\mathbf{t}_{2},\ldots,\mathbf{t}_{n}$
do not commute. However, we show that they can be simultaneously
triangularized in an appropriate basis of the group algebra (the
"descent-destroying basis"). As a consequence, any rational linear combination
of these $n$ elements has rational eigenvalues. The maximum number of possible
distinct eigenvalues turns out to be the Fibonacci number $f_{n+1}$, and
underlying this fact is a filtration of the group algebra connected to
"lacunar subsets" (i.e., subsets containing no consecutive integers). }

{\small This talk will include an overview of other families (both well-known
and exotic) of elements of these group algebras. I will also briefly discuss
the probabilistic meaning of these elements as well as many tempting
conjectures. }

{\small This is joint work with Nadia Lafreni\`{e}re. }

\end{abstract}

\newpage

\section*{***}

\textbf{Preprints on one-sided cycle shuffles:}

\begin{itemize}
\item Darij Grinberg and Nadia Lafreni\`{e}re, \textit{The one-sided cycle
shuffles in the symmetric group algebra}, arXiv:2212.06274,\newline%
\url{https://www.cip.ifi.lmu.de/~grinberg/algebra/s2b1.pdf}\newline%
\url{https://darijgrinberg.gitlab.io/algebra/s2b1.pdf}\newline Published in:
\href{https://doi.org/10.5802/alco.346}{Algebraic Combinatorics \textbf{7}
(2024) no. 2, pp. 275--326}.

\item Darij Grinberg, \textit{Commutator nilpotency for somewhere-to-below
shuffles}, arXiv:2309.05340,\newline%
\url{https://www.cip.ifi.lmu.de/~grinberg/algebra/s2b2.pdf}\newline\url{https://darijgrinberg.gitlab.io/algebra/s2b2.pdf}

\item Darij Grinberg, \textit{The representation theory of somewhere-to-below
shuffles}, rough draft,\newline%
\url{https://www.cip.ifi.lmu.de/~grinberg/algebra/s2b3.pdf}\newline\url{https://darijgrinberg.gitlab.io/algebra/s2b3.pdf}
\end{itemize}

\noindent\textbf{Preprint on row-to-row-sums:}

\begin{itemize}
\item Darij Grinberg, \textit{Rook sums in the symmetric group algebra},
outline 2024.\newline%
\url{https://www.cip.ifi.lmu.de/~grinberg/algebra/rooksn.pdf}\newline\url{https://darijgrinberg.gitlab.io/algebra/rooksn.pdf}
\end{itemize}

\noindent\textbf{Slides of this talk:}

\begin{itemize}
\item \url{https://www.cip.ifi.lmu.de/~grinberg/algebra/dc2023.pdf}\newline\url{https://darijgrinberg.gitlab.io/algebra/dc2023.pdf}
\end{itemize}

\noindent Items marked with $\circled{$\ast$}$ are more important.

\bigskip

\noindent\textbf{FPSAC abstract on one-sided cycle shuffles:}

\begin{itemize}
\item \url{https://www.cip.ifi.lmu.de/~grinberg/algebra/fps2024sn.pdf}\newline\url{https://darijgrinberg.gitlab.io/algebra/fps2024sn.pdf}
\end{itemize}

\newpage

\section{Finite group algebras}

\subsection{Finite group algebras}

\begin{itemize}
\item This talk is mainly about a certain family of elements of the group
algebra of the symmetric group $S_{n}$. But I shall begin with some generalities.

\item[$\circled{$\ast$}$] Let $\mathbf{k}$ be any commutative ring (but
$\mathbf{k}=\mathbb{Z}$ is enough for most of our results).

\item[$\circled{$\ast$}$] Let $G$ be a finite group. (It will be a symmetric
group from the next chapter onwards.)

\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.

\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)   &  =1+s_{1}-s_{1}-s_{1}%
^{2}=1+s_{1}-s_{1}-1=0;\\
\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}

\subsection{Left and right actions of $u$ on $\mathbf{k}\left[  G\right]  $}

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

\item (\textbf{Note:} I will try to consistently use boldface letters for
elements of $\mathbf{k}\left[  G\right]  $, such as $\mathbf{x}$ and
$\mathbf{u}$ here.)

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

\item Studying $\mathbf{u}$, $L\left(  \mathbf{u}\right)  $ and $R\left(
\mathbf{u}\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$).
\end{itemize}

\subsection{Minimal polynomials}

\begin{itemize}
\item[$\circled{$\ast$}$] Each $\mathbf{u}\in\mathbf{k}\left[  G\right]  $ has
a \textbf{minimal polynomial}, i.e., a minimum-degree monic polynomial
$P\in\mathbf{k}\left[  X\right]  $ such that $P\left(  \mathbf{u}\right)  =0$.
It is unique when $\mathbf{k}$ is a field.

The minimal polynomial of $\mathbf{u}$ is also the minimal polynomial of the
endomorphisms $L\left(  \mathbf{u}\right)  $ and $R\left(  \mathbf{u}\right)
$.

\item \textbf{Proposition 1.1.} Let $\mathbf{u}\in\mathbb{Z}\left[  G\right]
$. Then, the minimal polynomial of $\mathbf{u}$ over $\mathbb{Q}$ is actually
in $\mathbb{Z}\left[  X\right]  $, and is the minimal polynomial of
$\mathbf{u}$ over $\mathbb{Z}$ as well.

\item \textit{Proof:} Follow the standard proof that the minimal polynomial of
an algebraic number is in $\mathbb{Z}\left[  X\right]  $. (Use Gauss's Lemma.)
\end{itemize}

\subsection{Left and right are usually conjugate}

\begin{itemize}
\item \textbf{Theorem 1.2.} Assume that $\mathbf{k}$ is a field. Let
$\mathbf{u}\in\mathbf{k}\left[  G\right]  $. Then, $L\left(  \mathbf{u}%
\right)  \sim R\left(  \mathbf{u}\right)  $ as endomorphisms of $\mathbf{k}%
\left[  G\right]  $.

\textbf{Note:} The symbol $\sim$ means \textquotedblleft conjugate
to\textquotedblright. Thinking of these endomorphisms as $\left\vert
G\right\vert \times\left\vert G\right\vert $-matrices, this is just similarity
of matrices.

\item We will see a proof of this soon.

\item \textbf{Note:} $L\left(  \mathbf{u}\right)  \sim R\left(  \mathbf{u}%
\right)  $ would fail if $G$ was merely a monoid, or if $\mathbf{k}$ was
merely a commutative ring (e.g., for $\mathbf{k}=\mathbb{Q}\left[  t\right]  $
and $G=S_{3}$).
\end{itemize}

\subsection{The antipode}

\begin{itemize}
\item The \textbf{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*}


\item \textbf{Proposition 1.3.} The antipode $S$ is an involution (that is,
$S\circ S=\operatorname*{id}$) and a $\mathbf{k}$-algebra anti-automorphism
(that is, $S\left(  \mathbf{ab}\right)  =S\left(  \mathbf{b}\right)  \cdot
S\left(  \mathbf{a}\right)  $ for all $\mathbf{a},\mathbf{b}$).

\item \textbf{Lemma 1.4.} Assume that $\mathbf{k}$ is a field. Let
$\mathbf{u}\in\mathbf{k}\left[  G\right]  $. Then, $L\left(  \mathbf{u}%
\right)  \sim L\left(  S\left(  \mathbf{u}\right)  \right)  $ in
$\operatorname*{End}\nolimits_{\mathbf{k}}\left(  \mathbf{k}\left[  G\right]
\right)  $.

\item \textit{Proof:} Consider the standard basis $\left(  g\right)  _{g\in
G}$ of $\mathbf{k}\left[  G\right]  $. The matrix representing the
endomorphism $L\left(  S\left(  \mathbf{u}\right)  \right)  $ in this basis is
the transpose of the matrix representing $L\left(  \mathbf{u}\right)  $. But
\href{https://math.stackexchange.com/a/596842/}{the Taussky--Zassenhaus
theorem} says that over a field, each matrix $A$ is similar to its transpose
$A^{T}$.

\item \textbf{Lemma 1.5.} Let $\mathbf{u}\in\mathbf{k}\left[  G\right]  $.
Then, $L\left(  S\left(  \mathbf{u}\right)  \right)  \sim R\left(
\mathbf{u}\right)  $ in $\operatorname*{End}\nolimits_{\mathbf{k}}\left(
\mathbf{k}\left[  G\right]  \right)  $.

\item \textit{Proof:} We have $R\left(  \mathbf{u}\right)  =S\circ L\left(
S\left(  \mathbf{u}\right)  \right)  \circ S$ and $S=S^{-1}$.

\item \textit{Proof of Theorem 1.2:} Combine Lemma 1.4 with Lemma 1.5.

\item \textbf{Remark (Martin Lorenz).} Theorem 1.2 generalizes to arbitrary
Frobenius algebras.

\item \textbf{Remark.} Let $\mathbf{u}\in\mathbf{k}\left[  G\right]  $. Even
if $\mathbf{k}=\mathbb{C}$, we don't always have $\mathbf{u}\sim S\left(
\mathbf{u}\right)  $ in $\mathbf{k}\left[  G\right]  $ (easy counterexample
for $G=C_{3}$).
\end{itemize}

\newpage

\section{The symmetric group algebra}

\subsection{Symmetric groups}

\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}$.

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

Multiplication in $S_{n}$ is composition:%
\[
\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]  .
\]


(\textbf{Warning:} SageMath has a different opinion!)
\end{itemize}

\subsection{Symmetric group algebras}

\begin{itemize}
\item What can we say about the group algebra $\mathbf{k}\left[  S_{n}\right]
$ that doesn't hold for arbitrary $\mathbf{k}\left[  G\right]  $?

\item There is a classical theory (\textquotedblleft Young's seminormal
form\textquotedblright) of the structure of $\mathbf{k}\left[  S_{n}\right]  $
when $\mathbf{k}$ has characteristic $0$. Two modern treatments are

\begin{itemize}
\item \href{https://doi.org/10.1007/978-3-030-58373-6}{Adriano M. Garsia,
\"{O}mer Egecioglu, \textit{Lectures in Algebraic Combinatorics}, Springer
2020}.

\item \href{https://eudml.org/doc/287582}{Murray Bremner, Sara Madariaga, Luiz
A. Peresi, \textit{Structure theory for the group algebra of the symmetric
group, ...}, Commentationes Mathematicae Universitatis Carolinae, 2016}.
\end{itemize}

The best source I know (dated but readable and careful) is:

\begin{itemize}
\item Daniel Edwin Rutherford, \textit{Substitutional Analysis}, Edinburgh 1948.
\end{itemize}

\item \textbf{Theorem 2.1 (Artin--Wedderburn--Young).} If $\mathbf{k}$ is a
field of characteristic $0$, then%
\[
\mathbf{k}\left[  S_{n}\right]  \cong\prod_{\lambda\text{ is a partition of
}n}\underbrace{\operatorname*{M}\nolimits_{f_{\lambda}}\left(  \mathbf{k}%
\right)  }_{\text{matrix ring}}\ \ \ \ \ \ \ \ \ \ \left(  \text{as
}\mathbf{k}\text{-algebras}\right)  ,
\]
where $f_{\lambda}$ is the number of standard Young tableaux of shape
$\lambda$.

\item \textit{Proof:} This follows from Young's seminormal form. For the
shortest readable proof, see Theorem 1.45 in Bremner/Madariaga/Peresi.

Alternatively, see \S 5.14 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{my
\textit{Introduction to the Symmetric Group Algebra}}.
\end{itemize}

\subsection{Antipodal conjugacy}

\begin{itemize}
\item[$\circled{$\ast$}$] \textbf{Theorem 2.2.} Let $\mathbf{k}$ be a field of
characteristic $0$. Let $\mathbf{u}\in\mathbf{k}\left[  S_{n}\right]  $. Then,
$\mathbf{u}\sim S\left(  \mathbf{u}\right)  $ in $\mathbf{k}\left[
S_{n}\right]  $.

\item \textit{Proof:} Again use Young's seminormal form. Under the isomorphism
$\mathbf{k}\left[  S_{n}\right]  \cong\prod_{\lambda\text{ is a partition of
}n}\operatorname*{M}\nolimits_{f_{\lambda}}\left(  \mathbf{k}\right)  $, the
matrices corresponding to $S\left(  \mathbf{u}\right)  $ are the transposes of
the matrices corresponding to $\mathbf{u}$ (this follows from (2.3.40) in
Garsia/Egecioglu). Now, use
\href{https://math.stackexchange.com/a/596842/}{the Taussky--Zassenhaus
theorem} again.

\item \textit{Alternative proof:} See \S 5.20 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{my
\textit{Introduction to the Symmetric Group Algebra}}.

\item \textit{Alternative proof:} More generally, let $G$ be an
\textbf{ambivalent} finite group (i.e., a finite group in which each $g\in G$
is conjugate to $g^{-1}$). Let $\mathbf{u}\in\mathbf{k}\left[  G\right]  $.
Then, $\mathbf{u}\sim S\left(  \mathbf{u}\right)  $ in $\mathbf{k}\left[
G\right]  $. To prove this, pass to the algebraic closure of $\mathbf{k}$. By
Artin--Wedderburn, it suffices to show that $\mathbf{u}$ and $S\left(
\mathbf{u}\right)  $ act by similar matrices on each irreducible $G$-module
$V$. But this is easy: Since $G$ is ambivalent, we have $V\cong V^{\ast}$ and
thus%
\[
\left(  \mathbf{u}\mid_{V}\right)  \sim\left(  \mathbf{u}\mid_{V^{\ast}%
}\right)  \sim\left(  S\left(  \mathbf{u}\right)  \mid_{V}\right)  ^{T}%
\sim\left(  S\left(  \mathbf{u}\right)  \mid_{V}\right)
\]
(by Taussky--Zassenhaus).

\item \textbf{Note.} Characteristic $0$ is needed!
\end{itemize}

\newpage

\section{The Young--Jucys--Murphy elements}

\begin{itemize}
\item From now on, we shall discuss concrete elements in $\mathbf{k}\left[
S_{n}\right]  $.

\item[$\circled{$\ast$}$] For any distinct elements $i_{1},i_{2},\ldots,i_{k}$
of $\left[  n\right]  $, let $\operatorname*{cyc}\nolimits_{i_{1},i_{2}%
,\ldots,i_{k}}$ be the permutation in $S_{n}$ that cyclically permutes
$i_{1}\mapsto i_{2}\mapsto i_{3}\mapsto\cdots\mapsto i_{k}\mapsto i_{1}$ and
leaves all other elements of $\left[  n\right]  $ unchanged.

\item \textbf{Note.} We have $\operatorname*{cyc}\nolimits_{i}%
=\operatorname*{id}$;$\ \ \ \ \ \ \ \ \ \ \operatorname*{cyc}\nolimits_{i,j}$
is a transposition.

\item[$\circled{$\ast$}$] For each $k\in\left[  n\right]  $, we define the
$k$\textbf{-th Young--Jucys--Murphy (YJM) element}%
\[
\mathbf{m}_{k}:=\operatorname*{cyc}\nolimits_{1,k}+\operatorname*{cyc}%
\nolimits_{2,k}+\cdots+\operatorname*{cyc}\nolimits_{k-1,k}\in\mathbf{k}%
\left[  S_{n}\right]  .
\]


\item \textbf{Note.} We have $\mathbf{m}_{1}=0$. Also, $S\left(
\mathbf{m}_{k}\right)  =\mathbf{m}_{k}$ for each $k\in\left[  n\right]  $.

\item[$\circled{$\ast$}$] \textbf{Theorem 3.1.} The YJM elements
$\mathbf{m}_{1},\mathbf{m}_{2},\ldots,\mathbf{m}_{n}$ commute: We have
$\mathbf{m}_{i}\mathbf{m}_{j}=\mathbf{m}_{j}\mathbf{m}_{i}$ for all $i,j$.

\item \textit{Proof:} Easy computational exercise.

\item[$\circled{$\ast$}$] \textbf{Theorem 3.2.} The minimal polynomial of
$\mathbf{m}_{k}$ over $\mathbb{Q}$ divides%
\[
\prod_{i=-k+1}^{k-1}\left(  X-i\right)  =\left(  X-k+1\right)  \left(
X-k+2\right)  \cdots\left(  X+k-1\right)  .
\]
(For $k\leq3$, some factors here are redundant.)

\item \textit{First proof:} Study the action of $\mathbf{m}_{k}$ on each
Specht module (simple $S_{n}$-module). See, e.g.,
\href{https://doi.org/10.1016/0021-8693(81)90205-2}{G. E. Murphy, \textit{A
New Construction of Young's Seminormal Representation ...}, 1981} for details.

\item \textit{Second proof (Igor Makhlin):} Some linear algebra does the
trick. Induct on $k$ using the facts that $\mathbf{m}_{k}$ and $\mathbf{m}%
_{k+1}$ are simultaneously diagonalizable over $\mathbb{C}$ (since they are
symmetric as real matrices and commute) and satisfy $s_{k}\mathbf{m}%
_{k+1}=\mathbf{m}_{k}s_{k}+1$, where $s_{k}:=\operatorname*{cyc}%
\nolimits_{k,k+1}$. See \url{https://mathoverflow.net/a/83493/} for details.

\item More results and context can be found in \S 3.3 in
\href{https://doi.org/10.1017/CBO9781139192361}{Ceccherini-Silberstein/Scarabotti/Tolli,
\textit{Representation Theory of the Symmetric Groups}, 2010}.

\item \textbf{Question.} Is there a self-contained algebraic/combinatorial
proof of Theorem 3.2 without linear algebra or representation theory? (Asked
on MathOverflow: \url{https://mathoverflow.net/questions/420318/} .)

\item \textbf{Theorem 3.3.} For each $k\in\mathbb{N}$, we can evaluate the
$k$-th elementary symmetric polynomial $e_{k}$ at the YJM elements
$\mathbf{m}_{1},\mathbf{m}_{2},\ldots,\mathbf{m}_{n}$ to obtain%
\[
e_{k}\left(  \mathbf{m}_{1},\mathbf{m}_{2},\ldots,\mathbf{m}_{n}\right)
=\sum_{\substack{\sigma\in S_{n};\\\sigma\text{ has exactly }n-k\text{
cycles}}}\sigma.
\]


\item \textit{Proof:} Nice homework exercise (once stripped of the algebra).
See Corollary 3.8.20 in
\href{https://www.cip.ifi.lmu.de/~grinberg/t/24s/sga.pdf}{my
\textit{Introduction to the Symmetric Group Algebra}}.

\item There are formulas for other symmetric polynomials applied to
$\mathbf{m}_{1},\mathbf{m}_{2},\ldots,\mathbf{m}_{n}$ (see Garsia/Egecioglu).

\item \textbf{Theorem 3.4 (Murphy).}
\begin{align*}
&  \left\{  f\left(  \mathbf{m}_{1},\mathbf{m}_{2},\ldots,\mathbf{m}%
_{n}\right)  \ \mid\ f\in\mathbf{k}\left[  X_{1},X_{2},\ldots,X_{n}\right]
\text{ symmetric}\right\} \\
&  =\left(  \text{center of the group algebra }\mathbf{k}\left[  S_{n}\right]
\right)  .
\end{align*}


\item \textit{Proof:} See any of:

\begin{itemize}
\item
\href{https://www.ams.org/journals/tran/1992-332-01/S0002-9947-1992-1062873-1/}{Gadi
Moran, \textit{The center of }$\mathbb{Z}\left[  S_{n+1}\right]  $
\textit{...}, 1992}.

\item \href{https://doi.org/10.1016/0021-8693(83)90219-3}{G. E. Murphy,
\textit{The Idempotents of the Symmetric Group ...}, 1983}, Theorem 1.9 (for
the case $\mathbf{k}=\mathbb{Z}$, but the general case easily follows).

\item
\href{https://doi.org/10.1017/CBO9781139192361}{Ceccherini-Silberstein/Scarabotti/Tolli,
\textit{Representation Theory of the Symmetric Groups}, 2010}, Theorem 4.4.5
(for the case $\mathbf{k}=\mathbb{Q}$, but the proof is easily adjusted to all
$\mathbf{k}$).
\end{itemize}
\end{itemize}

\newpage

\section*{A. The card shuffling point of view}

\begin{itemize}
\item Permutations are often visualized as shuffled decks of cards:

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

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

\item A \textbf{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$.

\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}$.

\item For instance, $1+\operatorname*{cyc}\nolimits_{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}$.

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

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

\item Transposing such a matrix performs a time reversal of a random shuffle.
\end{itemize}

\newpage

\section{Top-to-random and random-to-top shuffles}

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


\item As a random shuffle, $\mathbf{B}_{k}$ (to be precise, $R\left(
\mathbf{B}_{k}\right)  $) takes the top $k$ cards and moves them to random positions.

\item $\mathbf{B}_{1}$ is known as the \textbf{top-to-random shuffle} or the
\textbf{Tsetlin library}.

(Why \textquotedblleft library\textquotedblright? Instead of a deck of cards,
think of a bookshelf. Then, $\mathbf{B}_{1}$ is taking the leftmost book and
placing it in a random position.)

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


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


\item \textbf{Theorem 4.3 (Wallach).} The minimal polynomial of $\mathbf{B}%
_{1}$ over $\mathbb{Q}$ is%
\[
\prod_{i\in\left\{  0,1,\ldots,n-2,n\right\}  }\left(  X-i\right)  =\left(
X-n\right)  \prod_{i=0}^{n-2}\left(  X-i\right)  .
\]


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

\item More can be said: in particular, the multiplicities of the eigenvalues
$0,1,\ldots,n-2,n$ of $R\left(  \mathbf{B}_{1}\right)  $ over $\mathbb{Q}$ are known.

\item The antipodes $S\left(  \mathbf{B}_{0}\right)  ,S\left(  \mathbf{B}%
_{1}\right)  ,\ldots,S\left(  \mathbf{B}_{n}\right)  $ are known as the
\textbf{random-to-top shuffles} and have the same properties (since $S$ is an
algebra anti-automorphism).

\item Main references:

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

\item
\href{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}

\newpage

\section{Random-to-random shuffles}

\begin{itemize}
\item Here is a further family. For each $k\in\left\{  0,1,\ldots,n\right\}
$, we let%
\[
\mathbf{R}_{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.

\item \textbf{Theorem 5.1 (Reiner, Saliola, Welker).} The $n+1$ elements
$\mathbf{R}_{0},\mathbf{R}_{1},\ldots,\mathbf{R}_{n}$ commute (but are not
polynomials in $\mathbf{R}_{1}$ in general).

\item \textbf{Theorem 5.2 (Dieker, Saliola, Lafreni\`{e}re).} The minimal
polynomial of each $\mathbf{R}_{k}$ over $\mathbb{Q}$ is a product of $X-i$'s
for distinct integers $i$. For example, the one of $\mathbf{R}_{1}$ divides
\[
\prod_{i=0}^{n^{2}}\left(  X-i\right)  .
\]
The exact factors can be given in terms of certain statistics on Young diagrams.

\item Main references:

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

\item \href{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 \href{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}

\item \textbf{Question:} Simpler proofs? (Even commutativity takes a dozen pages!)

\item \textbf{Answer:} Yes! See:

\begin{itemize}
\item \href{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}, draft (2025).}
\end{itemize}

We actually generalize Theorems 5.1 and 5.2 to the Hecke algebra, building on
prior work on $\mathbf{R}_{1}$:

\begin{itemize}
\item \href{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.}
\end{itemize}

\item \textbf{Question (Reiner):} How big is the subalgebra of $\mathbb{Q}%
\left[  S_{n}\right]  $ generated by $\mathbf{R}_{0},\mathbf{R}_{1}%
,\ldots,\mathbf{R}_{n}$ ? Some small values:%
\[%
\begin{tabular}
[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$\\\hline
$\dim\left(  \mathbb{Q}\left[  \mathbf{R}_{0},\mathbf{R}_{1},\ldots
,\mathbf{R}_{n}\right]  \right)  $ & $1$ & $2$ & $4$ & $7$ & $15$ & $30$ &
$54$ & $95$ & $159$ & $257$ & $400$\\\hline
\end{tabular}
\
\]
(sequence not in the OEIS as of 2025-01-29).

\item \textbf{Remark 5.3.} We have%
\[
\mathbf{R}_{k}=\dfrac{1}{k!}\cdot S\left(  \mathbf{B}_{k}\right)
\cdot\mathbf{B}_{k},
\]
but this is just a first step, since the $\mathbf{B}_{k}$ don't commute with
the $S\left(  \mathbf{B}_{k}\right)  $.

\item \textbf{Generalization (implicit in Reiner, Saliola, Welker).} For each
$k\in\left\{  0,1,\ldots,n\right\}  $, we let%
\[
\widetilde{\mathbf{R}}_{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 \textbf{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{\mathbf{R}}_{1},\widetilde{\mathbf{R}}_{2}%
,\ldots,\widetilde{\mathbf{R}}_{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?
\end{itemize}

\newpage

\section{Somewhere-to-below shuffles}

\begin{itemize}
\item[$\circled{$\ast$}$] In 2021, Nadia Lafreni\`{e}re defined the
\textbf{somewhere-to-below shuffles} $\mathbf{t}_{1},\mathbf{t}_{2}%
,\ldots,\mathbf{t}_{n}$ by setting%
\[
\mathbf{t}_{\ell}:=\operatorname*{cyc}\nolimits_{\ell}+\operatorname*{cyc}%
\nolimits_{\ell,\ell+1}+\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ell
+2}+\cdots+\operatorname*{cyc}\nolimits_{\ell,\ell+1,\ldots,n}\in
\mathbf{k}\left[  S_{n}\right]
\]
for each $\ell\in\left[  n\right]  $. (These $\mathbf{t}_{\ell}$ are called
$t_{\ell}$ in my papers.)

\item[$\circled{$\ast$}$] Thus, $\mathbf{t}_{1}=\mathbf{B}_{1}$ and
$\mathbf{t}_{n}=\operatorname*{id}$.

\item As a card shuffle, $\mathbf{t}_{\ell}$ takes the $\ell$-th card from the
top and moves it further down the deck.

\item Their linear combinations%
\[
\lambda_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}_{2}+\cdots+\lambda
_{n}\mathbf{t}_{n}\ \ \ \ \ \ \ \ \ \ \text{with }\lambda_{1},\lambda
_{2},\ldots,\lambda_{n}\in\mathbf{k}%
\]
are called \textbf{one-sided cycle shuffles} and also have a probabilistic
meaning when $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\geq0$.

\item \textbf{Fact:} $\mathbf{t}_{1},\mathbf{t}_{2},\ldots,\mathbf{t}_{n}$ do
not commute for $n\geq3$. For $n=3$, we have%
\[
\left[  \mathbf{t}_{1},\mathbf{t}_{2}\right]  =\operatorname*{cyc}%
\nolimits_{1,2}+\operatorname*{cyc}\nolimits_{1,2,3}-\operatorname*{cyc}%
\nolimits_{1,3,2}-\operatorname*{cyc}\nolimits_{1,3}.
\]


\item However, they come pretty close to commuting!

\item[$\circled{$\ast$}$] \textbf{Theorem 6.1 (Lafreniere, G., 2022).} There
exists a basis of the $\mathbf{k}$-module $\mathbf{k}\left[  S_{n}\right]  $
in which all of the endomorphisms \newline$R\left(  \mathbf{t}_{1}\right)
,R\left(  \mathbf{t}_{2}\right)  ,\ldots,R\left(  \mathbf{t}_{n}\right)  $ are
represented by upper-triangular matrices.
\end{itemize}

\newpage

\section{The descent-destroying basis}

\begin{itemize}
\item This basis is not hard to define, but I haven't seen it before.

\item[$\circled{$\ast$}$] For each $w\in S_{n}$, we let%
\[
\operatorname*{Des}w:=\left\{  i\in\left[  n-1\right]  \ \mid\ w\left(
i\right)  >w\left(  i+1\right)  \right\}  \ \ \ \ \ \ \ \ \ \ \left(
\text{the \textbf{descent set} of }w\right)  .
\]


\item[$\circled{$\ast$}$] For each $i\in\left[  n-1\right]  $, we let
$s_{i}:=\operatorname*{cyc}\nolimits_{i,i+1}$.

\item[$\circled{$\ast$}$] For each $I\subseteq\left[  n-1\right]  $, we let
\[
G\left(  I\right)  :=\left(  \text{the subgroup of }S_{n}\text{ generated by
the }s_{i}\text{ for }i\in I\right)  .
\]


\item[$\circled{$\ast$}$] For each $w\in S_{n}$, we let%
\[
\mathbf{a}_{w}:=\sum_{\sigma\in G\left(  \operatorname*{Des}w\right)  }%
w\sigma\in\mathbf{k}\left[  S_{n}\right]  .
\]
In other words, you get $\mathbf{a}_{w}$ by breaking up the word $w$ into
maximal decreasing factors and re-sorting each factor arbitrarily (without
mixing different factors). (The $\mathbf{a}_{w}$ are called $a_{w}$ in my papers.)

\item[$\circled{$\ast$}$] The family $\left(  \mathbf{a}_{w}\right)  _{w\in
S_{n}}$ is a basis of $\mathbf{k}\left[  S_{n}\right]  $ (by triangularity).

\item For instance, for $n=3$, we have
\begin{align*}
\mathbf{a}_{\left[  {\textcolor{blue}{1}}{\textcolor{red}{2}}%
{\textcolor{green!50!black}{3}}\right]  }  &  =\left[  {\textcolor{blue}{1}}%
{\textcolor{red}{2}}{\textcolor{green!50!black}{3}}\right]  ;\\
\mathbf{a}_{\left[  {\textcolor{blue}{1}}\textcolor{red}{32}\right]  }  &
=\left[  {\textcolor{blue}{1}}\textcolor{red}{32}\right]  +\left[
{\textcolor{blue}{1}}\textcolor{red}{23}\right]  ;\\
\mathbf{a}_{\left[  \textcolor{blue}{21}\textcolor{red}{3}\right]  }  &
=\left[  \textcolor{blue}{21}\textcolor{red}{3}\right]  +\left[
\textcolor{blue}{12}\textcolor{red}{3}\right]  ;\\
\mathbf{a}_{\left[  \textcolor{blue}{2}\textcolor{red}{31}\right]  }  &
=\left[  \textcolor{blue}{2}\textcolor{red}{31}\right]  +\left[
\textcolor{blue}{2}\textcolor{red}{13}\right]  ;\\
\mathbf{a}_{\left[  \textcolor{blue}{31}\textcolor{red}{2}\right]  }  &
=\left[  \textcolor{blue}{31}\textcolor{red}{2}\right]  +\left[
\textcolor{blue}{13}\textcolor{red}{2}\right]  ;\\
\mathbf{a}_{\left[  \textcolor{blue}{321}\right]  }  &  =\left[
\textcolor{blue}{321}\right]  +\left[  \textcolor{blue}{312}\right]  +\left[
\textcolor{blue}{231}\right]  +\left[  \textcolor{blue}{213}\right]  +\left[
\textcolor{blue}{132}\right]  +\left[  \textcolor{blue}{123}\right]  .
\end{align*}


\item[$\circled{$\ast$}$] \textbf{Theorem 7.1 (Lafreni\`{e}re, G.).} For any
$w\in S_{n}$ and $\ell\in\left[  n\right]  $, we have%
\[
\mathbf{a}_{w}\mathbf{t}_{\ell}=\mu_{w,\ell}\mathbf{a}_{w}+\sum
_{\substack{v\in S_{n};\\v\prec w}}\lambda_{w,\ell,v}\mathbf{a}_{v}%
\]
for some nonnegative integer $\mu_{w,\ell}$, some integers $\lambda_{w,\ell
,v}$ and a certain partial order $\prec$ on $S_{n}$.

Thus, the endomorphisms $R\left(  \mathbf{t}_{1}\right)  ,R\left(
\mathbf{t}_{2}\right)  ,\ldots,R\left(  \mathbf{t}_{n}\right)  $ are
upper-triangular with respect to the basis $\left(  \mathbf{a}_{w}\right)
_{w\in S_{n}}$.

\item \textit{Examples:}

\begin{itemize}
\item For $n=4$, we have%
\[
\mathbf{a}_{\left[  4312\right]  }\mathbf{t}_{2}=\mathbf{a}_{\left[
4312\right]  }+\underbrace{\mathbf{a}_{\left[  4321\right]  }-\mathbf{a}%
_{\left[  4231\right]  }-\mathbf{a}_{\left[  3241\right]  }-\mathbf{a}%
_{\left[  2143\right]  }}_{\text{subscripts are }\prec\left[  4312\right]  }.
\]


\item For $n=3$, the endomorphism $R\left(  \mathbf{t}_{1}\right)  $ is
represented by the matrix%
\[%
\begin{tabular}
[c]{c|cccccc}
& $\mathbf{a}_{\left[  321\right]  }$ & $\mathbf{a}_{\left[  231\right]  }$ &
$\mathbf{a}_{\left[  132\right]  }$ & $\mathbf{a}_{\left[  213\right]  }$ &
$\mathbf{a}_{\left[  312\right]  }$ & $\mathbf{a}_{\left[  123\right]  }%
$\\\hline
$\mathbf{a}_{\left[  321\right]  }$ & $3$ & $1$ & $1$ &  & $1$ & \\
$\mathbf{a}_{\left[  231\right]  }$ &  &  &  & $1$ & $-1$ & $1$\\
$\mathbf{a}_{\left[  132\right]  }$ &  &  &  & $1$ &  & \\
$\mathbf{a}_{\left[  213\right]  }$ &  &  &  & $1$ &  & \\
$\mathbf{a}_{\left[  312\right]  }$ &  &  &  &  & $1$ & \\
$\mathbf{a}_{\left[  123\right]  }$ &  &  &  &  &  & $1$%
\end{tabular}
\]
(empty cells = zero entries). For instance, the last column means
$\mathbf{a}_{\left[  123\right]  }\mathbf{t}_{1}=\mathbf{a}_{\left[
123\right]  }+\mathbf{a}_{\left[  231\right]  }$.
\end{itemize}

\item \textbf{Corollary 7.2.} The eigenvalues of these endomorphisms
\newline$R\left(  \mathbf{t}_{1}\right)  ,R\left(  \mathbf{t}_{2}\right)
,\ldots,R\left(  \mathbf{t}_{n}\right)  $ and of all their linear combinations%
\[
R\left(  \lambda_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}_{2}+\cdots
+\lambda_{n}\mathbf{t}_{n}\right)
\]
are integers as long as $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ are.

\item How many different eigenvalues do they have?

\item $R\left(  \mathbf{t}_{1}\right)  =R\left(  \mathbf{B}_{1}\right)  $ has
only $n$ eigenvalues: $0,1,\ldots,n-2,n$, as we have seen before. The other
$R\left(  \mathbf{t}_{\ell}\right)  $'s have even fewer.

\item But their linear combinations $R\left(  \lambda_{1}\mathbf{t}%
_{1}+\lambda_{2}\mathbf{t}_{2}+\cdots+\lambda_{n}\mathbf{t}_{n}\right)  $ can
have many more. How many?
\end{itemize}

\newpage

\section{Lacunar sets and Fibonacci numbers}

\begin{itemize}
\item[$\circled{$\ast$}$] A set $S$ of integers is called \textbf{lacunar} if
it contains no two consecutive integers (i.e., we have $s+1\notin S$ for all
$s\in S$).

\item[$\circled{$\ast$}$] \textbf{Theorem 8.1 (combinatorial interpretation of
Fibonacci numbers, folklore).} The number of lacunar subsets of $\left[
n-1\right]  $ is the \textbf{Fibonacci number} $f_{n+1}$.

(Recall:$\ \ \ \ \ \ \ \ \ \ f_{0}=0,\ \ \ \ \ \ \ \ \ \ f_{1}%
=1,\ \ \ \ \ \ \ \ \ \ $ $f_{n}=f_{n-1}+f_{n-2}$.)

\item[$\circled{$\ast$}$] \textbf{Theorem 8.2.} When $\lambda_{1},\lambda
_{2},\ldots,\lambda_{n}\in\mathbb{C}$ are generic, the number of distinct
eigenvalues of $R\left(  \lambda_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}%
_{2}+\cdots+\lambda_{n}\mathbf{t}_{n}\right)  $ is $f_{n+1}$. In this case,
the endomorphism $R\left(  \lambda_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}%
_{2}+\cdots+\lambda_{n}\mathbf{t}_{n}\right)  $ is diagonalizable.

\item Note that $f_{n+1}\ll n!$.

\item[$\circled{$\ast$}$] We prove this by finding a filtration
\[
0=F_{0}\subseteq F_{1}\subseteq F_{2}\subseteq\cdots\subseteq F_{f_{n+1}%
}=\mathbf{k}\left[  S_{n}\right]
\]
of the $\mathbf{k}$-module $\mathbf{k}\left[  S_{n}\right]  $ such that each
$R\left(  \mathbf{t}_{\ell}\right)  $ acts as a \textbf{scalar} on each of its
quotients $F_{i}/F_{i-1}$. In matrix terms, this means bringing $R\left(
\mathbf{t}_{\ell}\right)  $ to a block-triangular form, with the diagonal
blocks being \textquotedblleft scalar times $I$\textquotedblright\ matrices.

\item It is only natural that the quotients should correspond to the lacunar
subsets of $\left[  n-1\right]  $.

\item Let us approach the construction of this filtration.
\end{itemize}

\newpage

\section{The $F\left(  I\right)  $ and the Fibonacci filtration}

\begin{itemize}
\item[$\circled{$\ast$}$] For each $I\subseteq\left[  n\right]  $, we set%
\[
\operatorname*{sum}I:=\sum_{i\in I}i
\]
and%
\[
\widehat{I}:=\left\{  0\right\}  \cup I\cup\left\{  n+1\right\}
\ \ \ \ \ \ \ \ \ \ \left(  \text{\textquotedblleft
enclosure\textquotedblright\ of }I\right)
\]
and%
\[
I^{\prime}:=\left[  n-1\right]  \setminus\left(  I\cup\left(  I-1\right)
\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{\textquotedblleft
non-shadow\textquotedblright\ of }I\right)
\]
and%
\[
F\left(  I\right)  :=\left\{  \mathbf{q}\in\mathbf{k}\left[  S_{n}\right]
\ \mid\ \mathbf{q}s_{i}=\mathbf{q}\text{ for all }i\in I^{\prime}\right\}
\subseteq\mathbf{k}\left[  S_{n}\right]  .
\]
In probabilistic terms, $F\left(  I\right)  $ consists of those random states
of the deck that do not change if we swap the $i$-th and $\left(  i+1\right)
$-st cards from the top as long as neither $i$ nor $i+1$ is in $I$. To put it
informally: $F\left(  I\right)  $ consists of those random states that are
\textquotedblleft fully shuffled\textquotedblright\ between any two
consecutive $\widehat{I}$-positions.

\item \textbf{Example:} If $n=11$ and $I=\left\{  3,6,7\right\}  $, then
$\widehat{I}=\left\{  0,3,6,7,12\right\}  $ and $I^{\prime}=\left\{
1,4,8,9,10\right\}  $ and%
\[
F\left(  I\right)  =\left\{  \mathbf{q}\in\mathbf{k}\left[  S_{11}\right]
\ \mid\ \mathbf{q}s_{1}=\mathbf{q}s_{4}=\mathbf{q}s_{8}=\mathbf{q}%
s_{9}=\mathbf{q}s_{10}=\mathbf{q}\right\}  .
\]
Illustrating this:%
\[%
%TCIMACRO{\TeXButton{tikz ruler}{\begin{tikzpicture}[scale=1]
%\begin{scope}[every edge/.style={draw=black,thick}]
%\filldraw[very thick, fill=blue, draw=green!50!black] (0,0) rectangle (1, 1);
%\draw[very thick, draw=green!50!black] (1,0) rectangle (2, 1);
%\filldraw
%[very thick, fill=black!50!white, draw=green!50!black] (2,0) rectangle (3, 1);
%\filldraw[very thick, fill=black, draw=green!50!black] (3,0) rectangle (4, 1);
%\draw[very thick, draw=green!50!black] (4,0) rectangle (5, 1);
%\filldraw
%[very thick, fill=black!50!white, draw=green!50!black] (5,0) rectangle (6, 1);
%\filldraw[very thick, fill=black, draw=green!50!black] (6,0) rectangle (7, 1);
%\filldraw[very thick, fill=black, draw=green!50!black] (7,0) rectangle (8, 1);
%\draw[very thick, draw=green!50!black] (8,0) rectangle (9, 1);
%\draw[very thick, draw=green!50!black] (9,0) rectangle (10, 1);
%\draw[very thick, draw=green!50!black] (10,0) rectangle (11, 1);
%\filldraw
%[very thick, fill=blue!50!white, draw=green!50!black] (11,0) rectangle (12, 1);
%\filldraw
%[very thick, fill=blue, draw=green!50!black] (12,0) rectangle (13, 1);
%\node at (0.5, -0.5) {$0$};
%\node at (1.5, -0.5) {$1$};
%\node at (2.5, -0.5) {$2$};
%\node at (3.5, -0.5) {$3$};
%\node at (4.5, -0.5) {$4$};
%\node at (5.5, -0.5) {$5$};
%\node at (6.5, -0.5) {$6$};
%\node at (7.5, -0.5) {$7$};
%\node at (8.5, -0.5) {$8$};
%\node at (9.5, -0.5) {$9$};
%\node at (10.5, -0.5) {$10$};
%\node at (11.5, -0.5) {$11$};
%\node at (12.5, -0.5) {$12$};
%\end{scope}
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=1]
\begin{scope}[every edge/.style={draw=black,thick}]
\filldraw[very thick, fill=blue, draw=green!50!black] (0,0) rectangle (1, 1);
\draw[very thick, draw=green!50!black] (1,0) rectangle (2, 1);
\filldraw
[very thick, fill=black!50!white, draw=green!50!black] (2,0) rectangle (3, 1);
\filldraw[very thick, fill=black, draw=green!50!black] (3,0) rectangle (4, 1);
\draw[very thick, draw=green!50!black] (4,0) rectangle (5, 1);
\filldraw
[very thick, fill=black!50!white, draw=green!50!black] (5,0) rectangle (6, 1);
\filldraw[very thick, fill=black, draw=green!50!black] (6,0) rectangle (7, 1);
\filldraw[very thick, fill=black, draw=green!50!black] (7,0) rectangle (8, 1);
\draw[very thick, draw=green!50!black] (8,0) rectangle (9, 1);
\draw[very thick, draw=green!50!black] (9,0) rectangle (10, 1);
\draw[very thick, draw=green!50!black] (10,0) rectangle (11, 1);
\filldraw
[very thick, fill=blue!50!white, draw=green!50!black] (11,0) rectangle (12, 1);
\filldraw
[very thick, fill=blue, draw=green!50!black] (12,0) rectangle (13, 1);
\node at (0.5, -0.5) {$0$};
\node at (1.5, -0.5) {$1$};
\node at (2.5, -0.5) {$2$};
\node at (3.5, -0.5) {$3$};
\node at (4.5, -0.5) {$4$};
\node at (5.5, -0.5) {$5$};
\node at (6.5, -0.5) {$6$};
\node at (7.5, -0.5) {$7$};
\node at (8.5, -0.5) {$8$};
\node at (9.5, -0.5) {$9$};
\node at (10.5, -0.5) {$10$};
\node at (11.5, -0.5) {$11$};
\node at (12.5, -0.5) {$12$};
\end{scope}
\end{tikzpicture}%
%EndExpansion
\]
(black = $I$;\qquad grey = $I-1$;\qquad blue = $\widehat{I}\setminus I$;\qquad
lightblue = $n$;\qquad white = $I^{\prime}$).

\item[$\circled{$\ast$}$] For any $\ell\in\left[  n\right]  $, we let
$m_{I,\ell}$ be the distance from $\ell$ to the next-higher element of
$\widehat{I}$. In other words,%
\[
m_{I,\ell}:=\left(  \text{smallest element of }\widehat{I}\text{ that is }%
\geq\ell\right)  -\ell\in\left\{  0,1,\ldots,n\right\}  .
\]


In our above example,%
\[
\left(  m_{I,1},\ m_{I,2},\ \ldots,\ m_{I,11}\right)  =\left(
2,\ 1,\ 0,\ 2,\ 1,\ 0,\ 0,\ 4,\ 3,\ 2,\ 1\right)  .
\]


For another example, if $n=5$ and $I=\left\{  2,3\right\}  $, then
$\widehat{I}=\left\{  0,2,3,6\right\}  $ and%
\[
\left(  m_{I,1},\ m_{I,2},\ m_{I,3},\ m_{I,4},\ m_{I,5}\right)  =\left(
1,\ 0,\ 0,\ 2,\ 1\right)  .
\]


\item We note that, for any $\ell\in\left[  n\right]  $, we have the
equivalence%
\[
m_{I,\ell}=0\ \ \ \ \Longleftrightarrow\ \ \ \ \ell\in\widehat{I}%
\ \ \ \ \Longleftrightarrow\ \ \ \ \ell\in I.
\]


\item[$\circled{$\ast$}$] \textbf{Crucial Lemma 9.1.} Let $I\subseteq\left[
n\right]  $ and $\ell\in\left[  n\right]  $. Then,%
\[
\mathbf{qt}_{\ell}\in m_{I,\ell}\mathbf{q}+\underbrace{\sum
_{\substack{J\subseteq\left[  n\right]  ;\\\operatorname*{sum}%
J<\operatorname*{sum}I}}F\left(  J\right)  }_{\substack{\text{Think of these
as}\\\text{\textquotedblleft lower-order terms\textquotedblright}%
}}\ \ \ \ \ \ \ \ \ \ \text{for each }\mathbf{q}\in F\left(  I\right)  .
\]


\item \textit{Proof:} Expand $\mathbf{qt}_{\ell}$ by the definition of
$\mathbf{t}_{\ell}$, and break up the resulting sum into smaller bunches using
the interval decomposition%
\[
\left[  \ell,n\right]  =\left[  \ell,i_{k}-1\right]  \sqcup\left[
i_{k},i_{k+1}-1\right]  \sqcup\left[  i_{k+1},i_{k+2}-1\right]  \sqcup
\cdots\sqcup\left[  i_{p},n\right]
\]
(where $i_{k}<i_{k+1}<\cdots<i_{p}$ are the elements of $I$ larger or equal to
$\ell$). The $\left[  \ell,i_{k}-1\right]  $ bunch gives the $m_{I,\ell
}\mathbf{q}$ term; the others live in appropriate $F\left(  J\right)  $'s.

See the paper for the details.

\item[$\circled{$\ast$}$] Thus, we obtain a filtration of $\mathbf{k}\left[
S_{n}\right]  $ if we label the subsets $I$ of $\left[  n\right]  $ in the
order of increasing $\operatorname*{sum}I$ and add up the respective $F\left(
I\right)  $s.

On each subquotient of this filtration, $\mathbf{t}_{\ell}$ acts as a scalar
$m_{I,\ell}$.

\item Unfortunately, this filtration has $2^{n}$, not $f_{n+1}$ terms.

\item[$\circled{$\ast$}$] Fortunately, that's because many of its terms are
redundant. The ones that aren't correspond precisely to the $I$'s that are
lacunar subsets of $\left[  n-1\right]  $:

\item \textbf{Lemma 9.2.} Let $k\in\mathbb{N}$. Then,%
\[
\sum_{\substack{J\subseteq\left[  n\right]  ;\\\operatorname*{sum}%
J<k}}F\left(  J\right)  =\sum_{\substack{J\subseteq\left[  n-1\right]  \text{
is lacunar;}\\\operatorname*{sum}J<k}}F\left(  J\right)  .
\]


\item \textit{Proof:} If $J\subseteq\left[  n\right]  $ contains $n$ or fails
to be lacunar, then $F\left(  J\right)  $ is a submodule of some $F\left(
K\right)  $ with $\operatorname*{sum}K<\operatorname*{sum}J$. (Exercise!)

\item Now, we let $Q_{1},Q_{2},\ldots,Q_{f_{n+1}}$ be the $f_{n+1}$ lacunar
subsets of $\left[  n-1\right]  $, listed in such an order that%
\[
\operatorname*{sum}\left(  Q_{1}\right)  \leq\operatorname*{sum}\left(
Q_{2}\right)  \leq\cdots\leq\operatorname*{sum}\left(  Q_{f_{n+1}}\right)  .
\]
Then, define a $\mathbf{k}$-submodule%
\[
F_{i}:=F\left(  Q_{1}\right)  +F\left(  Q_{2}\right)  +\cdots+F\left(
Q_{i}\right)  \ \ \ \ \ \ \ \ \ \ \text{of }\mathbf{k}\left[  S_{n}\right]
\]
for each $i\in\left[  0,f_{n+1}\right]  $ (so that $F_{0}=0$). The resulting
filtration%
\[
0=F_{0}\subseteq F_{1}\subseteq F_{2}\subseteq\cdots\subseteq F_{f_{n+1}%
}=\mathbf{k}\left[  S_{n}\right]
\]
(which we call the \textbf{Fibonacci filtration} of $\mathbf{k}\left[
S_{n}\right]  $) satisfies the properties we need:

\item \textbf{Theorem 9.3.} For each $i\in\left[  f_{n+1}\right]  $ and
$\ell\in\left[  n\right]  $, we have%
\[
F_{i}\cdot\left(  \mathbf{t}_{\ell}-m_{Q_{i},\ell}\right)  \subseteq F_{i-1}%
\]
(so that $R\left(  \mathbf{t}_{\ell}\right)  $ acts on $F_{i}/F_{i-1}$ as
multiplication by $m_{Q_{i},\ell}$).

\item \textit{Proof:} Lemma 9.1 + Lemma 9.2.

\item \textbf{Lemma 9.4.} The quotients $F_{i}/F_{i-1}$ are nontrivial for all
$i\in\left[  f_{n+1}\right]  $.

\item \textit{Proof:} See below.

\item[$\circled{$\ast$}$] \textbf{Corollary 9.5.} Let $\mathbf{k}$ be a field,
and let $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\in\mathbf{k}$. Then, the
eigenvalues of $R\left(  \lambda_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}%
_{2}+\cdots+\lambda_{n}\mathbf{t}_{n}\right)  $ are the linear combinations%
\[
\lambda_{1}m_{I,1}+\lambda_{2}m_{I,2}+\cdots+\lambda_{n}m_{I,n}%
\ \ \ \ \ \ \ \ \ \ \text{for }I\subseteq\left[  n-1\right]  \text{ lacunar.}%
\]


\item Theorem 8.2 easily follows by some linear algebra.

\item More generally, this holds not just for linear combinations $\lambda
_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}_{2}+\cdots+\lambda_{n}\mathbf{t}_{n}$
but for any noncommutative polynomials in $\mathbf{t}_{1},\mathbf{t}%
_{2},\ldots,\mathbf{t}_{n}$.
\end{itemize}

\newpage

\section{Back to the basis}

\begin{itemize}
\item The descent-destroying basis $\left(  \mathbf{a}_{w}\right)  _{w\in
S_{n}}$ is compatible with our filtration:

\item[$\circled{$\ast$}$] \textbf{Theorem 10.1.} For each $I\subseteq\left[
n\right]  $, the family $\left(  \mathbf{a}_{w}\right)  _{w\in S_{n}%
;\ I^{\prime}\subseteq\operatorname*{Des}w}$ is a basis of the $\mathbf{k}%
$-module $F\left(  I\right)  $.

\item[$\circled{$\ast$}$] If $w\in S_{n}$ is any permutation, then the
$Q$\textbf{-index} of $w$ is defined to be the \textbf{smallest} $i\in\left[
f_{n+1}\right]  $ such that $Q_{i}^{\prime}\subseteq\operatorname*{Des}w$. We
call this $Q$-index $\operatorname*{Qind}w$.

\item \textbf{Proposition 10.2.} Let $w\in S_{n}$ and $i\in\left[
f_{n+1}\right]  $. Then, $\operatorname*{Qind}w=i$ if and only if
$Q_{i}^{\prime}\subseteq\operatorname*{Des}w\subseteq\left[  n-1\right]
\setminus Q_{i}$.

\item \textbf{Note:} The numbering $Q_{1},Q_{2},\ldots,Q_{f_{n+1}}$ of the
lacunar subsets of $\left[  n-1\right]  $ is not unique; we just picked one.
The $Q$-index $i=\operatorname*{Qind}w$ of a $w\in S_{n}$ depends on this
numbering. However, the corresponding lacunar set $Q_{i}$ does not, since
Proposition 10.2 determines it canonically (it is the unique lacunar
$L\subseteq\left[  n-1\right]  $ satisfying $L^{\prime}\subseteq
\operatorname*{Des}w\subseteq\left[  n-1\right]  \setminus L$).

Thus, think of this set $Q_{i}$ as the \textquotedblleft
real\textquotedblright\ index of $w$. But $i$ is easier to work with.

(You can get rid of the numbering altogether if you allow filtrations indexed
by a poset.)

\item[$\circled{$\ast$}$] \textbf{Theorem 10.3.} For each $i\in\left[
0,f_{n+1}\right]  $, the $\mathbf{k}$-module $F_{i}$ is free with basis
$\left(  \mathbf{a}_{w}\right)  _{w\in S_{n};\ \operatorname*{Qind}w\leq i}$.

\item[$\circled{$\ast$}$] \textbf{Corollary 10.4.} For each $i\in\left[
f_{n+1}\right]  $, the $\mathbf{k}$-module $F_{i}/F_{i-1}$ is free with basis
$\left(  \overline{\mathbf{a}_{w}}\right)  _{w\in S_{n};\ \operatorname*{Qind}%
w=i}$.

\item This yields Lemma 9.4 and also leads to Theorem 7.1, made precise as follows:

\item[$\circled{$\ast$}$] \textbf{Theorem 10.5 (Lafreni\`{e}re, G.).} For any
$w\in S_{n}$ and $\ell\in\left[  n\right]  $, we have%
\[
\mathbf{a}_{w}\mathbf{t}_{\ell}=\mu_{w,\ell}\mathbf{a}_{w}+\sum
_{\substack{v\in S_{n};\\\operatorname*{Qind}v<\operatorname*{Qind}w}%
}\lambda_{w,\ell,v}\mathbf{a}_{v}%
\]
for some nonnegative integer $\mu_{w,\ell}$ and some integers $\lambda
_{w,\ell,v}$.

Thus, the endomorphisms $R\left(  \mathbf{t}_{1}\right)  ,R\left(
\mathbf{t}_{2}\right)  ,\ldots,R\left(  \mathbf{t}_{n}\right)  $ are
upper-triangular with respect to the basis $\left(  \mathbf{a}_{w}\right)
_{w\in S_{n}}$ as long as the permutations $w\in S_{n}$ are ordered by
increasing $Q$-index.
\end{itemize}

\newpage

\section{The multiplicities}

\begin{itemize}
\item In Corollary 9.5, we found the eigenvalues of the endomorphism $R\left(
\lambda_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}_{2}+\cdots+\lambda
_{n}\mathbf{t}_{n}\right)  $. With Corollary 10.4, we can also find their
algebraic multiplicities. To state a formula for them, we need a definition:

\item[$\circled{$\ast$}$] For each $i\in\left[  f_{n+1}\right]  $, we set%
\[
\delta_{i}:=\left(  \text{the number of all }w\in S_{n}\text{ satisfying
}\operatorname*{Qind}w=i\right)  .
\]


\item[$\circled{$\ast$}$] \textbf{Corollary 11.1 (approximate version).}
Assume that $\mathbf{k}$ is a field. Let $\lambda_{1},\lambda_{2}%
,\ldots,\lambda_{n}\in\mathbf{k}$. Then, the endomorphism $R\left(
\lambda_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}_{2}+\cdots+\lambda
_{n}\mathbf{t}_{n}\right)  $ has eigenvalues%
\[
\lambda_{I}:=\lambda_{1}m_{I,1}+\lambda_{2}m_{I,2}+\cdots+\lambda_{n}%
m_{I,n}\ \ \ \ \ \ \ \ \ \ \text{for all lacunar }I\subseteq\left[
n-1\right]  \text{.}%
\]
Each such eigenvalue has algebraic multiplicity $\delta_{i}$, where
$i\in\left[  f_{n+1}\right]  $ is such that $I=Q_{i}$. If several such
eigenvalues happen to coincide, then their algebraic multiplicities must be
added together.

\item \textbf{Corollary 11.1 (pedantic version).} Assume that $\mathbf{k}$ is
a field. Let $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}\in\mathbf{k}$. For
each $i\in\left[  f_{n+1}\right]  $, we let%
\[
g_{i}:=\sum_{\ell=1}^{n}\lambda_{\ell}m_{Q_{i},\ell}\in\mathbf{k}.
\]
Let $\kappa\in\mathbf{k}$. Then, the algebraic multiplicity of $\kappa$ as an
eigenvalue of the endomorphism $R\left(  \lambda_{1}\mathbf{t}_{1}+\lambda
_{2}\mathbf{t}_{2}+\cdots+\lambda_{n}\mathbf{t}_{n}\right)  $ equals%
\[
\sum_{\substack{i\in\left[  f_{n+1}\right]  ;\\g_{i}=\kappa}}\delta_{i}.
\]


\item Can we compute the $\delta_{i}$ explicitly? Yes!

\item[$\circled{$\ast$}$] \textbf{Theorem 11.2.} Let $i\in\left[
f_{n+1}\right]  $. Then:

\begin{enumerate}
\item[\textbf{(a)}] Write the set $Q_{i}$ in the form $Q_{i}=\left\{
i_{1}<i_{2}<\cdots<i_{p}\right\}  $, and set $i_{0}=1$ and $i_{p+1}=n+1$. Let
$j_{k}=i_{k}-i_{k-1}$ for each $k\in\left[  p+1\right]  $. Then,%
\[
\delta_{i}=\underbrace{\dbinom{n}{j_{1},j_{2},\ldots,j_{p+1}}}%
_{\substack{\text{multinomial}\\\text{coefficient}}}\cdot\prod_{k=2}%
^{p+1}\left(  j_{k}-1\right)  .
\]


\item[\textbf{(b)}] We have $\delta_{i}\mid n!$.
\end{enumerate}

\item \textbf{Note.} This reminds of the hook-length formula for standard
tableaux, but is much simpler.
\end{itemize}

\newpage

\section{Variants}

\begin{itemize}
\item Most of what we said about the somewhere-to-below shuffles
$\mathbf{t}_{\ell}$ can be extended to their antipodes $S\left(
\mathbf{t}_{\ell}\right)  $ (the \textquotedblleft\textbf{below-to-somewhere
shuffles}\textquotedblright). For instance:

\item \textbf{Theorem 12.1.} There exists a basis of the $\mathbf{k}$-module
$\mathbf{k}\left[  S_{n}\right]  $ in which all of the endomorphisms $R\left(
S\left(  \mathbf{t}_{1}\right)  \right)  ,R\left(  S\left(  \mathbf{t}%
_{2}\right)  \right)  ,\ldots,R\left(  S\left(  \mathbf{t}_{n}\right)
\right)  $ are represented by upper-triangular matrices.

\item We can also use left instead of right multiplication:

\item \textbf{Theorem 12.2.} There exists a basis of the $\mathbf{k}$-module
$\mathbf{k}\left[  S_{n}\right]  $ in which all of the endomorphisms $L\left(
\mathbf{t}_{1}\right)  ,L\left(  \mathbf{t}_{2}\right)  ,\ldots,L\left(
\mathbf{t}_{n}\right)  $ are represented by upper-triangular matrices.

\item These follow from Theorem 6.1 using dual bases, transpose matrices and
Proposition 1.3. No new combinatorics required!

\item \textbf{Question.} Do we have $L\left(  \mathbf{t}_{\ell}\right)  \sim
R\left(  \mathbf{t}_{\ell}\right)  $ in $\operatorname*{End}%
\nolimits_{\mathbf{k}}\left(  \mathbf{k}\left[  S_{n}\right]  \right)  $ when
$\mathbf{k}$ is not a field?

\item \textbf{Remark.} The similarity $\mathbf{t}_{\ell}\sim S\left(
\mathbf{t}_{\ell}\right)  $ in $\mathbf{k}\left[  S_{n}\right]  $ holds when
$\operatorname*{char}\mathbf{k}=0$, but not for general fields $\mathbf{k}$.
(E.g., it fails for $\mathbf{k}=\mathbb{F}_{2}$ and $n=4$ and $\ell=1$.)
\end{itemize}

\newpage

\section{Commutators}

\begin{itemize}
\item The simultaneous trigonalizability of the endomorphisms \newline%
$R\left(  \mathbf{t}_{1}\right)  ,R\left(  \mathbf{t}_{2}\right)
,\ldots,R\left(  \mathbf{t}_{n}\right)  $ yields that their pairwise
commutators are nilpotent. Hence, the pairwise commutators $\left[
\mathbf{t}_{i},\mathbf{t}_{j}\right]  $ are also nilpotent.

\item \textbf{Question.} How small an exponent works in $\left[
\mathbf{t}_{i},\mathbf{t}_{j}\right]  ^{\ast}=0$ ?

\item[$\circled{$\ast$}$] \textbf{Theorem 13.1.} We have $\left[
\mathbf{t}_{i},\mathbf{t}_{j}\right]  ^{j-i+1}=0$ for any $1\leq i\leq j\leq
n$.

\item[$\circled{$\ast$}$] \textbf{Theorem 13.2.} We have $\left[
\mathbf{t}_{i},\mathbf{t}_{j}\right]  ^{\left\lceil \left(  n-j\right)
/2\right\rceil +1}=0$ for any $i,j\in\left[  n\right]  $.

\item Depending on $i$ and $j$, one of the exponents is better than the other.

\textbf{Conjecture.} The better one is optimal! (Checked for all $n\leq12$.)

\item[$\circled{$\ast$}$] Stronger results hold, replacing powers by products.

\item[$\circled{$\ast$}$] Several other curious facts hold: For example,%
\[
\mathbf{t}_{i+1}\mathbf{t}_{i}=\left(  \mathbf{t}_{i}-1\right)  \mathbf{t}%
_{i}\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \mathbf{t}_{i+2}\left(
\mathbf{t}_{i}-1\right)  =\left(  \mathbf{t}_{i}-1\right)  \left(
\mathbf{t}_{i+1}-1\right)
\]
and%
\[
\mathbf{t}_{n-1}\left[  \mathbf{t}_{i},\mathbf{t}_{n-1}\right]
=0\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \left[  \mathbf{t}%
_{i},\mathbf{t}_{n-1}\right]  \left[  \mathbf{t}_{j},\mathbf{t}_{n-1}\right]
=0
\]
for all $i$ and $j$.

\item All this is completely elementary but surprisingly hard to prove (dozens
of pages of manipulations with sums and cycles). The proofs can be found in
\href{http://arxiv.org/abs/2309.05340v2}{arXiv:2309.05340v2} aka%
\[
\text{\url{https://www.cip.ifi.lmu.de/~grinberg/algebra/s2b2.pdf}}%
\]


\item What is \textquotedblleft really\textquotedblright\ going on? No idea...
\end{itemize}

\newpage

\section{Representation theory}

\begin{itemize}
\item Where groups go, representations are not far away...

If you know representation theory, you will have asked yourself two questions:

\begin{enumerate}
\item The $F\left(  I\right)  $ and the $F_{i}$ are left ideals of
$\mathbf{k}\left[  S_{n}\right]  $; how do they decompose into Specht modules?

\item How do $\mathbf{t}_{1},\mathbf{t}_{2},\ldots,\mathbf{t}_{n}$ act on a
given Specht module?
\end{enumerate}

\item We can answer these (when $\mathbf{k}$ is a field):

\item The answer uses symmetric functions, specifically:

\begin{itemize}
\item Let $s_{\lambda}$ be the Schur function for a partition $\lambda$.

\item Let $h_{m}=s_{\left(  m\right)  }$ be the $m$-th complete homogeneous
symmetric function for each $m\geq0$.

\item Let $z_{m}=s_{\left(  m-1,1\right)  }=h_{m-1}h_{1}-h_{m}$ for each $m>1$.
\end{itemize}

\item For each lacunar subset $I$ of $\left[  n-1\right]  $, we define a
symmetric function
\[
z_{I}:=h_{i_{1}-1}\prod_{j=2}^{k}z_{i_{j}-i_{j-1}}\ \ \ \ \ \ \ \ \ \ \left(
\text{over }\mathbb{Z}\right)  ,
\]
where $i_{1},i_{2},\ldots,i_{k}$ are the elements of $I\cup\left\{
n+1\right\}  $ in increasing order (so that $i_{k}=n+1$ and $I=\left\{
i_{1}<i_{2}<\cdots<i_{k-1}\right\}  $).

This is a skew Schur function corresponding to a disjoint union of hooks:
e.g., if $n=11$ and $I=\left\{  3,6,8\right\}  $, then the skew shape is%
\[%
%TCIMACRO{\TeXButton{tikz skew dia}{\begin{tikzpicture}[scale=0.7]
%\begin{scope}[every edge/.style={draw=black,thick}]
%\filldraw[thick, fill=green!50!white] (6,0) rectangle (8,-1);
%\filldraw
%[thick, fill=yellow!50!white] (4,-1) -- (6, -1) -- (6, -2) -- (5, -2) -- (5, -3) -- (4, -3) -- cycle;
%\filldraw[thick, fill=blue!50!white] (3, -3) rectangle (4, -5);
%\filldraw
%[thick, fill=red!50!white] (0, -5) -- (3, -5) -- (3, -6) -- (1, -6) -- (1, -7) -- (0, -7) -- cycle;
%\end{scope}
%\node at (-3, -0.5) {$i_1-1$};
%\node at (-3, -1.5) {$i_2-i_1-1$};
%\node at (-3, -2.5) {$1$};
%\node at (-3, -3.5) {$i_3-i_2-1$};
%\node at (-3, -4.5) {$1$};
%\node at (-3, -5.5) {$i_4-i_3-1$};
%\node at (-3, -6.5) {$1$};
%\end{tikzpicture}}}%
%BeginExpansion
\begin{tikzpicture}[scale=0.7]
\begin{scope}[every edge/.style={draw=black,thick}]
\filldraw[thick, fill=green!50!white] (6,0) rectangle (8,-1);
\filldraw
[thick, fill=yellow!50!white] (4,-1) -- (6, -1) -- (6, -2) -- (5, -2) -- (5, -3) -- (4, -3) -- cycle;
\filldraw[thick, fill=blue!50!white] (3, -3) rectangle (4, -5);
\filldraw
[thick, fill=red!50!white] (0, -5) -- (3, -5) -- (3, -6) -- (1, -6) -- (1, -7) -- (0, -7) -- cycle;
\end{scope}
\node at (-3, -0.5) {$i_1-1$};
\node at (-3, -1.5) {$i_2-i_1-1$};
\node at (-3, -2.5) {$1$};
\node at (-3, -3.5) {$i_3-i_2-1$};
\node at (-3, -4.5) {$1$};
\node at (-3, -5.5) {$i_4-i_3-1$};
\node at (-3, -6.5) {$1$};
\end{tikzpicture}%
%EndExpansion
\]


\item For each lacunar $I\subseteq\left[  n-1\right]  $ and each partition
$\lambda$ of $n$, we let $c_{\lambda}^{I}$ be the coefficient of $s_{\lambda}$
in the Schur expansion of $z_{I}$.

This is a nonnegative integer (actually a Littlewood--Richardson coefficient,
since $z_{I}$ is a skew Schur function).

\item \textbf{Theorem 14.1.} Let $\nu$ be a partition. Let $\lambda
_{1},\lambda_{2},\ldots,\lambda_{n}\in\mathbf{k}$. Then, the one-sided cycle
shuffle $\lambda_{1}\mathbf{t}_{1}+\lambda_{2}\mathbf{t}_{2}+\cdots
+\lambda_{n}\mathbf{t}_{n}$ acts on the Specht module $S^{\nu}$ as a linear
map with eigenvalues%
\begin{align*}
&  \lambda_{1}m_{I,1}+\lambda_{2}m_{I,2}+\cdots+\lambda_{n}m_{I,n}\\
&  \ \ \ \ \ \ \ \ \ \ \text{for all lacunar }I\subseteq\left[  n-1\right]
\text{ satisfying }c_{\nu}^{I}\neq0,
\end{align*}
and the multiplicity of each such eigenvalue is $c_{\nu}^{I}$ in the generic
case (i.e., if no two $I$'s produce the same linear combination; otherwise the
multiplicities of colliding eigenvalues should be added together).

If all these linear combinations are distinct, then this linear map is diagonalizable.

\item \textbf{Theorem 14.2 (lazy version).} Let $\mathbf{k}$ be a field of
characteristic $0$. Let $i\in\left[  f_{n+1}\right]  $. As a representation of
$S_{n}$, the quotient module $F_{i}/F_{i-1}$ has Frobenius characteristic
$z_{Q_{i}}$.

\item \textbf{Theorem 14.2 (careful version, true in every characteristic).}
Let $i\in\left[  f_{n+1}\right]  $. Consider the lacunar subset $Q_{i}$ of
$\left[  n-1\right]  $. Let $i_{1},i_{2},\ldots,i_{k}$ be the elements of
$Q_{i}\cup\left\{  n+1\right\}  $ in increasing order. Then, as
representations of $S_{n}$, we have%
\[
F_{i}/F_{i-1}\cong\underbrace{\mathcal{H}_{i_{1}-1}\ast\mathcal{Z}%
_{i_{2}-i_{1}}\ast\mathcal{Z}_{i_{3}-i_{2}}\ast\cdots\ast\mathcal{Z}%
_{i_{k}-i_{k-1}}}_{\substack{\text{the first factor is an }\mathcal{H}%
\text{,}\\\text{while all others are }\mathcal{Z}\text{'s}}},
\]
where $\ast$ means induction product (that is, $U\ast V=\operatorname*{Ind}%
\nolimits_{S_{i}\times S_{j}}^{S_{i+j}}\left(  U\otimes V\right)  $), and
where $\mathcal{H}_{m}$ is the trivial $1$-dimensional representation of
$S_{m}$, whereas $\mathcal{Z}_{m}$ is the reflection representation of $S_{m}$
(that is, $\mathbf{k}^{m}$ modulo the span of $\left(  1,1,\ldots,1\right)  $).

\item Proofs appear in:

\begin{itemize}
\item \href{https://www.cip.ifi.lmu.de/~grinberg/algebra/s2b3.pdf}{Darij
Grinberg, \textit{The representation theory of somewhere-to-below shuffles},
draft 2025}.
\end{itemize}

Theorem 14.2 is proved by directly constructing an isomorphism; Theorem 14.1
is obtained from it by applying a Hom-functor $\operatorname*{Hom}%
\nolimits_{\mathbf{k}\left[  S_{n}\right]  }\left(  -,S^{\nu}\right)  $ to the
Fibonacci filtration (to obtain a filtration of $S^{\nu}$).
\end{itemize}

\newpage

\section{Conjectures and questions}

\begin{itemize}
\item \textbf{Question.} What can be said about the $\mathbf{k}$-subalgebra
$\mathbf{k}\left[  \mathbf{t}_{1},\mathbf{t}_{2},\ldots,\mathbf{t}_{n}\right]
$ of $\mathbf{k}\left[  S_{n}\right]  $ ? Note:%
\[%
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|c|}\hline
$n$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$\\\hline
$\dim\left(  \mathbb{Q}\left[  \mathbf{t}_{1},\mathbf{t}_{2},\ldots
,\mathbf{t}_{n}\right]  \right)  $ & $1$ & $2$ & $4$ & $9$ & $23$ & $66$ &
$212$ & $761$\\\hline
\end{tabular}
\ \
\]
(this sequence is not in the OEIS as of 2025-04-16).

{\small Also, the Lie subalgebra }$\mathcal{L}\left(  \mathbf{t}%
_{1},\mathbf{t}_{2},\ldots,\mathbf{t}_{n}\right)  $ {\small of }%
$\mathbb{Q}\left[  S_{n}\right]  $ {\small has dimensions}%
\[%
\begin{tabular}
[c]{|c||c|c|c|c|c|c|c|}\hline
$n$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$\\\hline
$\dim\left(  \mathcal{L}\left(  \mathbf{t}_{1},\mathbf{t}_{2},\ldots
,\mathbf{t}_{n}\right)  \right)  $ & $1$ & $2$ & $4$ & $8$ & $20$ & $59$ &
$196$\\\hline
\end{tabular}
\]
{\small (also not in the OEIS).}

\item \textbf{Question (\textquotedblleft Is there a }$q$%
\textbf{-deformation?\textquotedblright).} Much of the above (e.g., Theorems
10.5, 13.1, 13.2) seems to still hold if $\mathbb{Q}\left[  S_{n}\right]  $ is
replaced by the Iwahori--Hecke algebra (but $\mathbf{t}_{1},\mathbf{t}%
_{2},\ldots,\mathbf{t}_{n}$ are defined in the exact same way, with $w$
replaced by $T_{w}$). Even $\dim\left(  \mathbb{Q}\left[  \mathbf{t}%
_{1},\mathbf{t}_{2},\ldots,\mathbf{t}_{n}\right]  \right)  $ appears to be the
same for the Hecke algebra, suggesting that all identities come from the Hecke
algebra. Why?

(Verified for Corollary 9.5 and Theorem 10.5, with the integers $m_{I,\ell}$
replaced by $q$-integers $\left[  m_{I,\ell}\right]  _{q}$. More details in
forthcoming work...)
\end{itemize}

\newpage

\section{The Gaudin Bethe subalgebras}

\begin{itemize}
\item We now leave the topic of one-sided cycle shuffles, and return to
surveying other (families of) elements of $\mathbf{k}\left[  S_{n}\right]  $.

\item The following was found (at least in a significant case) by
\href{https://arxiv.org/abs/1004.4248}{Mukhin, Tarasov and Varchenko (2013)},
and recently extended and reproved by
\href{https://arxiv.org/abs/2207.05743}{Purbhoo (2022)} and
\href{https://arxiv.org/abs/2309.04645v1}{Karp and Purbhoo (2023)}.

\item \textbf{Definition.} Let $z_{1},z_{2},\ldots,z_{n}$ be any $n+2$
elements of $\mathbf{k}$.

For any subset $T$ of $\left[  n\right]  $, we set%
\[
\boldsymbol{\alpha}_{T}^{+}:=\sum_{\sigma\in S_{T}}\sigma\in\mathbf{k}\left[
S_{n}\right]
\]
(where $S_{T}$ is embedded into $S_{n}$ in the obvious way: all elements
$\notin T$ are fixed).

\item \textbf{Theorem 16.1 (Mukhin/Tarasov/Varchenko/Purbhoo).} Set%
\[
\boldsymbol{\beta}_{k}^{+}\left(  u\right)  :=\sum_{\substack{T\subseteq
\left[  n\right]  ;\\\left\vert T\right\vert =k}}\boldsymbol{\alpha}_{T}%
^{+}\prod_{m\in\left[  n\right]  \setminus T}\left(  z_{m}+u\right)
\ \ \ \ \ \ \ \ \ \ \text{for any }k\in\mathbb{N}\text{ and }u\in\mathbf{k}.
\]
Then, $\boldsymbol{\beta}_{i}^{+}\left(  u\right)  $ and $\boldsymbol{\beta
}_{j}^{+}\left(  v\right)  $ commute for all $i,j\in\mathbb{N}$ and
$u,v\in\mathbf{k}$.

\item More generally:

\item \textbf{Theorem 16.2 (Karp/Purbhoo).} Fix $i,j\in\mathbb{N}$ and
$u,v\in\mathbf{k}$. Fix a class function $\varphi$ on the symmetric group
$S_{i}$, and a class function $\psi$ on the symmetric group $S_{j}$. For any
$i$-element subset $T$ of $\left[  n\right]  $, set
\[
\boldsymbol{\alpha}_{T}^{\varphi}:=\sum_{\sigma\in S_{T}}\varphi\left(
\sigma\right)  \sigma\in\mathbf{k}\left[  S_{n}\right]  ,
\]
where $\varphi$ is transported onto $S_{T}$ via any bijection $\left[
i\right]  \rightarrow T$ (the choice does not matter). Set%
\[
\boldsymbol{\beta}_{i}^{\varphi}\left(  u\right)  :=\sum_{\substack{T\subseteq
\left[  n\right]  ;\\\left\vert T\right\vert =i}}\boldsymbol{\alpha}%
_{T}^{\varphi}\prod_{m\in\left[  n\right]  \setminus T}\left(  z_{m}+u\right)
.
\]
Similarly define $\boldsymbol{\beta}_{j}^{\psi}\left(  v\right)  $. Then,
$\boldsymbol{\beta}_{i}^{\varphi}\left(  u\right)  $ and $\boldsymbol{\beta
}_{j}^{\psi}\left(  v\right)  $ commute.

\item The proofs are not very long but surprisingly complicated. A major
ingredient is the group version of antipodal conjugacy: Each permutation
$\sigma\in S_{n}$ is conjugate to its inverse. (A trickier refinement of this
is used.)

\item Both Mukhin/Tarasov/Varchenko and Purbhoo prove further results about
the (commutative) subalgebra of $\mathbf{k}\left[  S_{n}\right]  $ generated
by the $\boldsymbol{\beta}_{i}^{\varphi}\left(  u\right)  $. In particular,
Purbhoo shows that the subalgebra generated by $\boldsymbol{\beta}_{i}%
^{+}\left(  u\right)  $ is that generated by $\boldsymbol{\beta}%
_{i}^{\operatorname*{sign}}\left(  u\right)  $.

\item \textbf{Question:} Simpler proofs?
\end{itemize}

\newpage

\section{Excendances and anti-excedances}

\begin{itemize}
\item \textbf{Definition.} Let $\sigma\in S_{n}$ be a permutation. Then, we
define%
\begin{align*}
\operatorname*{exc}\sigma &  :=\left(  \text{\# of }i\in\left[  n\right]
\text{ such that }\sigma\left(  i\right)  >i\right)
\ \ \ \ \ \ \ \ \ \ \text{and}\\
\operatorname*{anxc}\sigma &  :=\left(  \text{\# of }i\in\left[  n\right]
\text{ such that }\sigma\left(  i\right)  <i\right)
\end{align*}
(the \textquotedblleft\textbf{excedance number}\textquotedblright\ and the
\textquotedblleft\textbf{anti-excedance number}\textquotedblright\ of $\sigma$).

\item \textbf{Conjecture 17.1.} For any $a,b\in\mathbb{N}$, define%
\[
\mathbf{X}_{a,b}:=\sum_{\substack{\sigma\in S_{n};\\\operatorname*{exc}%
\sigma=a;\\\operatorname*{anxc}\sigma=b}}\sigma\in\mathbf{k}\left[
S_{n}\right]  .
\]
Then, the elements $\mathbf{X}_{a,b}$ for all $a,b\in\mathbb{N}$ commute (for
fixed $n$).

\item Checked for all $n\leq7$ using SageMath. Inspired by the
Mukhin\allowbreak/Tarasov/Varchenko results from the previous section (thanks
Theo Douvropoulos for the idea!).

\item The antipode plays well with these elements:%
\[
S\left(  \mathbf{X}_{a,b}\right)  =\mathbf{X}_{b,a}.
\]


\item \textbf{Question.} What can be said about the (commutative) $\mathbf{k}%
$-subalgebra $\mathbf{k}\left[  \mathbf{X}_{a,b}\ \mid\ a,b\in\left\{
0,1,\ldots,n\right\}  \right]  $ of $\mathbf{k}\left[  S_{n}\right]  $ ? Note:%
\[%
\begin{tabular}
[c]{|c||c|c|c|c|c|c|}\hline
$n$ & $1$ & $2$ & $3$ & $4$ & $5$ & $6$\\\hline
$\dim\left(  \mathbb{Q}\left[  \mathbf{X}_{a,b}\right]  \right)  $ & $1$ & $2$
& $4$ & $10$ & $26$ & $76$\\\hline
\end{tabular}
\ \ \ .
\]
So far, this looks like the \# of involutions in $S_{n}$, which is exactly the
dimension of the Gelfand--Zetlin subalgebra (generated by the
Young--Jucys--Murphy elements)!

What is the exact relation?
\end{itemize}

\newpage

\section{Riffle shuffles}

\begin{itemize}
\item For a change, here is something classical.

\item For each $k\in\mathbb{N}$, we define an element%
\[
\mathbf{S}_{k}:=\sum_{\substack{\mathbf{i}=\left(  i_{1},i_{2},\ldots
,i_{k}\right)  \in\mathbb{N}^{k};\\i_{1}+i_{2}+\cdots+i_{k}=n}}\ \ \sum
_{\substack{\sigma\in S_{n};\\\sigma\text{ is increasing on}\\\text{every
}\mathbf{i}\text{-interval}}}\sigma
\]
of $\mathbf{k}\left[  S_{n}\right]  $. Here, for any $k$-tuple $\mathbf{i}%
=\left(  i_{1},i_{2},\ldots,i_{k}\right)  \in\mathbb{N}^{k}$ satisfying
$i_{1}+i_{2}+\cdots+i_{k}=n$, the $\mathbf{i}$\textbf{-intervals} are the
intervals of lengths $i_{1},i_{2},\ldots,i_{k}$ into which the set $\left[
n\right]  $ is subdivided (i.e., the intervals $\left[  i_{1}+i_{2}%
+\cdots+i_{j-1}+1,\ i_{1}+i_{2}+\cdots+i_{j}\right]  $ for all $0<j\leq k$).
(Recall that $0\in\mathbb{N}$, so that these intervals may be empty.)

This $\mathbf{S}_{k}$ is called the $k$\textbf{-riffle shuffle}. Roughly
speaking, it corresponds to cutting the deck into $k$ piles of sizes
$i_{1},i_{2},\ldots,i_{k}$ and shuffling them back together arbitrarily. (This
description is a bit imprecise, as it ignores probabilities.)

\item \textbf{Theorem 18.1 (e.g., Gerstenhaber/Schack 1991).} The elements
$\mathbf{S}_{0},\mathbf{S}_{1},\mathbf{S}_{2},\ldots$ commute. Moreover,%
\[
\mathbf{S}_{i}\mathbf{S}_{j}=\mathbf{S}_{ij}\ \ \ \ \ \ \ \ \ \ \text{for all
}i,j\in\mathbb{N}.
\]


\item \textit{Proof using Hopf algebras:} It suffices to show that $S\left(
\mathbf{S}_{i}\right)  \cdot S\left(  \mathbf{S}_{j}\right)  =S\left(
\mathbf{S}_{ij}\right)  $ for all $i,j\in\mathbb{N}$ (where $S$ is the
antipode, sending each $\sigma\in S_{n}$ to $\sigma^{-1}$).

The symmetric group algebra $\mathbf{k}\left[  S_{n}\right]  $ acts faithfully
on the tensor power $V^{\otimes n}$ of any free $\mathbf{k}$-module $V$ of
rank $\geq n$ (by permuting the tensorands). This tensor power $V^{\otimes n}$
is the $n$-th degree part of the tensor algebra $T\left(  V\right)  $, which
is a cocommutative connected graded Hopf algebra ($\Delta$ = unshuffle
coproduct). Now, the action of $S\left(  \mathbf{S}_{i}\right)  $ on
$V^{\otimes i}$ is just the convolution $\operatorname*{id}\nolimits^{\star
i}=\underbrace{\operatorname*{id}\star\operatorname*{id}\star\cdots
\star\operatorname*{id}}_{i\text{ times}}:T\left(  V\right)  \rightarrow
T\left(  V\right)  $ (restricted to $V^{\otimes i}$). So it remains to prove
that $\operatorname*{id}\nolimits^{\star i}\circ\operatorname*{id}%
\nolimits^{\star j}=\operatorname*{id}\nolimits^{\star\left(  ij\right)  }$.
But this can be done easily using cocommutativity.

\item \textit{Remark:} These $\operatorname*{id}\nolimits^{\star i}$ are known
as \textbf{Adams operations}, and are defined on any bialgebra. The equality
$\operatorname*{id}\nolimits^{\star i}\circ\operatorname*{id}\nolimits^{\star
j}=\operatorname*{id}\nolimits^{\star\left(  ij\right)  }$ holds for any
commutative or cocommutative bialgebra.

\item \textbf{Theorem 18.2.} The minimal polynomial of $\mathbf{S}_{i}$ is a
divisor of
\[
\left(  X-i^{1}\right)  \left(  X-i^{2}\right)  \cdots\left(  X-i^{n}\right)
.
\]


\item \textbf{Theorem 18.3.} If $\mathbf{k}$ is a field of characteristic $0$,
the subalgebra of $\mathbf{k}\left[  S_{n}\right]  $ generated (= spanned) by
$\mathbf{S}_{0},\mathbf{S}_{1},\mathbf{S}_{2},\ldots$ is $n$-dimensional as a
$\mathbf{k}$-vector space, and is isomorphic to a product of $n$ copies of
$\mathbf{k}$. It is called the \textbf{Eulerian subalgebra} of $\mathbf{k}%
\left[  S_{n}\right]  $, and its decomposing idempotents are the famous
\textbf{Eulerian idempotents}.

\item Reference: \href{https://doi.org/10.1007/978-3-662-11389-9}{Loday,
\textit{Cyclic homology}, 2nd edition 1998, \S 4.5}.

\item \textbf{Question.} How does the Eulerian subalgebra look like for
general $\mathbf{k}$ ?
\end{itemize}

\newpage

\section{Row-to-row sums}

\begin{itemize}
\item[$\circled{$\ast$}$] \textbf{Definition.} A \textbf{set composition} of
$\left[  n\right]  $ is defined to mean a tuple $\mathbf{U}=\left(
U_{1},U_{2},\ldots,U_{k}\right)  $ of disjoint nonempty subsets of $\left[
n\right]  $ such that $U_{1}\cup U_{2}\cup\cdots\cup U_{k}=\left[  n\right]
$. We set $\ell\left(  \mathbf{U}\right)  =k$ and call $k$ the \textbf{length}
of $\mathbf{U}$.

\item[$\circled{$\ast$}$] \textbf{Definition.} Let $\operatorname*{SC}\left(
n\right)  $ be the set of all set compositions of $\left[  n\right]  $.

\item[$\circled{$\ast$}$] \textbf{Definition.} If $\mathbf{A}=\left(
A_{1},A_{2},\ldots,A_{k}\right)  $ and $\mathbf{B}=\left(  B_{1},B_{2}%
,\ldots,B_{k}\right)  $ are two set compositions of $\left[  n\right]  $
having the same length, then we define the \textbf{row-to-row sum}%
\[
\nabla_{\mathbf{B},\mathbf{A}}:=\sum_{\substack{w\in S_{n};\\w\left(
A_{i}\right)  =B_{i}\text{ for all }i}}w\ \ \ \ \ \ \ \ \ \ \text{in
}\mathbf{k}\left[  S_{n}\right]  .
\]


\item \textbf{Easy properties:}

\begin{itemize}
\item We have $\nabla_{\mathbf{B},\mathbf{A}}=0$ unless $\left\vert
A_{i}\right\vert =\left\vert B_{i}\right\vert $ for all $i$.

\item We have $\nabla_{\mathbf{B},\mathbf{A}}=\nabla_{\mathbf{B}%
\sigma,\mathbf{A}\sigma}$ for any $\sigma\in S_{k}$ (acting on set
compositions by permuting the blocks).

\item We have $S\left(  \nabla_{\mathbf{B},\mathbf{A}}\right)  =\nabla
_{\mathbf{A},\mathbf{B}}$.
\end{itemize}

\item[$\circled{$\ast$}$] \textbf{Theorem 19.1.} Let $\mathcal{A}%
=\mathbf{k}\left[  S_{n}\right]  $. Let $k\in\mathbb{N}$. We define two
$\mathbf{k}$-submodules $\mathcal{I}_{k}$ and $\mathcal{J}_{k}$ of
$\mathcal{A}$ by
\[
\mathcal{I}_{k}:=\operatorname*{span}\left\{  \nabla_{\mathbf{B},\mathbf{A}%
}\ \mid\ \mathbf{A},\mathbf{B}\in\operatorname*{SC}\left(  n\right)  \text{
with }\ell\left(  \mathbf{A}\right)  =\ell\left(  \mathbf{B}\right)  \leq
k\right\}
\]
and%
\[
\mathcal{J}_{k}:=\mathcal{A}\cdot\operatorname*{span}\left\{
\boldsymbol{\alpha}_{U}^{-}\ \mid\ U\text{ is a }\left(  k+1\right)
\text{-element subset of }\left[  n\right]  \right\}  \cdot\mathcal{A},
\]
where%
\[
\boldsymbol{\alpha}_{U}^{-}:=\sum_{\sigma\in S_{U}}\left(  -1\right)
^{\sigma}\sigma\in\mathbf{k}\left[  S_{n}\right]  .
\]
Then:

\begin{itemize}
\item Both $\mathcal{I}_{k}$ and $\mathcal{J}_{k}$ are ideals of $\mathcal{A}%
$, and are preserved under $S$.

\item We have
\begin{align*}
\mathcal{I}_{k}  &  =\mathcal{J}_{k}^{\perp}=\operatorname*{LAnn}%
\mathcal{J}_{k}=\operatorname*{RAnn}\mathcal{J}_{k}%
\ \ \ \ \ \ \ \ \ \ \text{and}\\
\mathcal{J}_{k}  &  =\mathcal{I}_{k}^{\perp}=\operatorname*{LAnn}%
\mathcal{I}_{k}=\operatorname*{RAnn}\mathcal{I}_{k}.
\end{align*}
Here, $\mathcal{U}^{\perp}$ means orthogonal complement wrt the standard
bilinear form on $\mathcal{A}$, whereas $\operatorname*{LAnn}$ and
$\operatorname*{RAnn}$ mean left and right annihilators.

\item The $\mathbf{k}$-module $\mathcal{I}_{k}$ is free of rank = \# of
$\left(  1,2,\ldots,k+1\right)  $-avoiding permutations in $S_{n}$.

\item The $\mathbf{k}$-module $\mathcal{J}_{k}$ is free of rank = \# of
$\left(  1,2,\ldots,k+1\right)  $-nonavoiding permutations in $S_{n}$.

\item The quotients $\mathcal{A}/\mathcal{J}_{k}$ and $\mathcal{A}%
/\mathcal{I}_{k}$ are also free, with the same ranks as $\mathcal{I}_{k}$ and
$\mathcal{J}_{k}$ (respectively), and with bases consisting of (residue
classes of) the relevant permutations.

\item If $n!$ is invertible in $\mathbf{k}$, then $\mathcal{A}=\mathcal{I}%
_{k}\oplus\mathcal{J}_{k}$ (internal direct sum) as $\mathbf{k}$-modules, and
$\mathcal{A}\cong\mathcal{I}_{k}\times\mathcal{J}_{k}$ as $\mathbf{k}$-algebras.
\end{itemize}

\item This is not hard to show using representation theory if $\mathbf{k}%
=\mathbb{C}$ (or $\mathbb{Q}$), but the characteristic-free case needs to be
done from scratch.

\item \textbf{Remark.} The \textbf{Murphy basis} of $\mathcal{A}$ consists of
the elements $\nabla_{\mathbf{B},\mathbf{A}}$ for the \textbf{standard} set
compositions $\mathbf{A}$ and $\mathbf{B}$ of $\left[  n\right]  $. Here,
\textquotedblleft standard\textquotedblright\ means that the blocks are the
rows of a standard Young tableau (in particular, they must be of partition shape).

This is a cellular basis of $\mathcal{A}$. Thus, the Specht modules are
quotients of spans of certain subfamilies of this basis.

(This was done for Hecke algebras in:
\href{https://core.ac.uk/download/pdf/82422274.pdf}{G. E. Murphy, \textit{On
the Representation Theory of the Symmetric Groups and Associated Hecke
Algebras}, 1991}. Our $\nabla_{\mathbf{B},\mathbf{A}}$ correspond to his
$x_{s,t}$ for $q=1$.)

\item \textbf{Question.} How far can we develop the representation theory of
$S_{n}$ using this approach? (e.g., prove the LR rule?)
\end{itemize}

\newpage

\section{Row-to-row sums of length 2}

\begin{itemize}
\item The elements $\nabla_{\mathbf{B},\mathbf{A}}$ are fairly general, and in
fact each $w\in S_{n}$ can be written as $\nabla_{\mathbf{B},\mathbf{A}}$ for
some $\mathbf{A}$ and $\mathbf{B}$. But some things can be said when
$\ell\left(  \mathbf{A}\right)  =\ell\left(  \mathbf{B}\right)  \leq2$.

\item[$\circled{$\ast$}$] \textbf{Definition.} If $A$ and $B$ are two subsets
of $\left[  n\right]  $, then we set%
\[
\nabla_{B,A}:=\sum_{\substack{w\in S_{n};\\w\left(  A\right)  =B}%
}w\ \ \ \ \ \ \ \ \ \ \text{in }\mathbf{k}\left[  S_{n}\right]  .
\]
This is $\nabla_{\mathbf{B},\mathbf{A}}$ for $\mathbf{A}=\left(  A,\ \left[
n\right]  \setminus A\right)  $ and $\mathbf{B}=\left(  B,\ \left[  n\right]
\setminus B\right)  $.

\item[$\circled{$\ast$}$] \textbf{Theorem 20.1.} The minimal polynomial of
each $\nabla_{B,A}$ over $\mathbb{Q}$ is a product of linear factors.

\item \textbf{Example.} For $n=5$, the minimal polynomial of $\nabla_{\left\{
1,2\right\}  ,\left\{  2,3\right\}  }$ is $\left(  x-12\right)  \left(
x-2\right)  x\left(  x+4\right)  $.

\item More generally:

\item[$\circled{$\ast$}$] \textbf{Theorem 20.2.} Fix any $A\subseteq\left[
n\right]  $. Then, the minimal polynomial of any $\mathbb{Q}$-linear
combination of $\nabla_{B,A}$ with $B$ ranging over the subsets of $\left[
n\right]  $ is a product of linear factors.

\item This can be proved using a filtration (albeit not of $\mathcal{A}$).

\item \textbf{Questions.} What are the linear factors (i.e., the eigenvalues)?
(I have a complicated sum formula.)

What is the characteristic polynomial? (i.e., what are the multiplicities of
the eigenvalues?)

\item The proofs of Theorems 20.1 and 20.2 rely on the following fact:

\item \textbf{Proposition 20.3 (product formula).} Let $A,B,C,D$ be four
subsets of $\left[  n\right]  $ such that $\left\vert A\right\vert =\left\vert
B\right\vert $ and $\left\vert C\right\vert =\left\vert D\right\vert $. Then,%
\[
\nabla_{D,C}\nabla_{B,A}=\omega_{B,C}\sum_{\substack{U\subseteq D,\\V\subseteq
A;\\\left\vert U\right\vert =\left\vert V\right\vert }}\left(  -1\right)
^{\left\vert U\right\vert -\left\vert B\cap C\right\vert }\dbinom{\left\vert
U\right\vert }{\left\vert B\cap C\right\vert }\nabla_{U,V},
\]
where%
\[
\omega_{B,C}:=\left\vert B\cap C\right\vert !\cdot\left\vert B\setminus
C\right\vert !\cdot\left\vert C\setminus B\right\vert !\cdot\left\vert \left[
n\right]  \setminus\left(  B\cup C\right)  \right\vert !\in\mathbb{Z}.
\]


\item \textit{Proof.} Nice exercise in enumeration!

\item \textbf{Digression.} Define a free $\mathbf{k}$-module with basis
$\left(  \Delta_{B,A}\right)  _{A,B\subseteq\left[  n\right]  \text{ with
}\left\vert A\right\vert =\left\vert B\right\vert }$, where the $\Delta_{B,A}$
are formal symbols. Define a multiplication on $\mathcal{D}$ by%
\[
\Delta_{D,C}\Delta_{B,A}:=\omega_{B,C}\sum_{\substack{U\subseteq
D,\\V\subseteq A;\\\left\vert U\right\vert =\left\vert V\right\vert }}\left(
-1\right)  ^{\left\vert U\right\vert -\left\vert B\cap C\right\vert }%
\dbinom{\left\vert U\right\vert }{\left\vert B\cap C\right\vert }\Delta
_{U,V}.
\]


\item \textbf{Theorem 20.4.} This $\mathcal{D}$ is a nonunital algebra (i.e., associative).

\item \textbf{Question.} Is this algebra unital when $n!$ is invertible in
$\mathbf{k}$ ?

\item \textbf{Question.} What is this algebra really? (It is a free
$\mathbf{k}$-module of rank $\dbinom{2n}{n}$, so it might be a diagram algebra
-- e.g., a nonunital $\mathbb{Z}$-form of the planar rook algebra?)
\end{itemize}

\newpage

\section{Philosophical questions}

\begin{itemize}
\item Why is so much happening in $\mathbf{k}\left[  S_{n}\right]  $ ? In particular:

\item \textbf{Why do so many elements commute?} Are there any general methods
for proving commutativity?

\item \textbf{Why do so many elements have integer eigenvalues} (i.e.,
factoring minimal polynomials)?

\item Methods I have seen so far:

\begin{itemize}
\item Explicit multiplication rules: proves commutativity for $\mathbf{B}_{k}%
$, eigenvalues for $\nabla_{B,A}$, and various properties for elements in the
descent algebra (Solomon Mackey rule).

\item Faithful action on $V^{\otimes n}$: proves commutativity for
$\mathbf{S}_{i}$, $\mathbf{R}_{i}$ (Lafreni\`{e}re's approach).

\item Preserved filtration: proves eigenvalues and simultaneous
trigonalizability for $\mathbf{t}_{i}$; can theoretically be used for
commutativity as well when the elements generate an $S$-invariant subalgebra
(via Okounkov-Vershik involution trick), but haven't seen that happen.

\item Bijective brute-force: proves commutativity for $\mathbf{m}_{k}$,
$\boldsymbol{\beta}_{k}^{\varphi}$.

\item Action on irreps (= Specht modules): proves eigenvalues for
$\mathbf{m}_{k}$, $\mathbf{R}_{i}$.

\item Diagonalization: proves eigenvalues for $\mathbf{m}_{k}$ (Young
seminormal basis), $\mathbf{R}_{i}$.

\item Faithful action on something else (e.g., Gelfand model, polynomial ring
via divided symmetrization, etc.): would be nice to see a use, but have not
encountered yet.

\item Transfer principles (e.g., \S 3.1 in
\href{https://arxiv.org/abs/0906.5185v1}{Mukhin/Tarasov/Varchenko
arXiv:0906.5185v1}): would be really great to see.

\item Recognition as polynomials in simpler commuting elements: would be nice
to see.

\item Okounkov--Vershik lemma (centralizer of multiplicity-free branching):
would be nice to see.

\item Categorization (replacing $S_{n}=\operatorname*{Bij}\left(  \left[
n\right]  ,\left[  n\right]  \right)  $ by $\operatorname*{Inj}\left(  \left[
n\right]  ,\left[  m\right]  \right)  $ or $\operatorname*{Surj}\left(
\left[  n\right]  ,\left[  m\right]  \right)  $, just like square matrices are
a particular case of rectangular matrices): would be great to see!
\end{itemize}

Any additions to this list are welcome!
\end{itemize}

\newpage

\section{I thank}

\begin{itemize}
\item \textbf{Nadia Lafreni\`{e}re} for obvious reasons.

\item \textbf{Sarah Brauner, Patricia Commins, Martin Lorenz, Franco Saliola,
Marcelo Aguiar, Vic Reiner, Travis Scrimshaw}, \textbf{Theo Douvropoulos},
\textbf{Volkmar Welker} for helpful conversations recent and not so recent.

\item \textbf{Vasily Dolgushev} for the invitation (Temple).

\item \textbf{Joel Brewster Lewis} for the invitation (GW).

\item \textbf{Walter Mazorchuk} for the invitation (Uppsala).

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


\end{document}