\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=Tuesday, November 29, 2022 06:51:48}
%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}}
\newcommand{\silentsection}{\section}
\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}}
\NOEXPAND{\silentsection}{\section}
\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 in the symmetric group algebra [talk slides]}
\date{CAP 2022, 2022-11-29}
\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 $t_{1}%
,t_{2},\ldots,t_{n}$ in the group algebra of $S_{n}$ by%
\begin{align*}
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, $t_{1}$, is known as the top-to-random shuffle and has been studied by
Diaconis, Fill, Pitman (among others). }

{\small The $n$ elements $t_{1},t_{2},\ldots,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 some tempting
conjectures. }

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

\end{abstract}

\newpage

\section*{***}

Preprint:

\begin{itemize}
\item Darij Grinberg and Nadia Lafreni\`{e}re, \textit{The one-sided cycle
shuffles in the symmetric group algebra}, preprint,\newline\url{https://www.cip.ifi.lmu.de/~grinberg/algebra/s2b1.pdf}
\end{itemize}

Slides of this talk:

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

\newpage

\section{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*}


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

\item Both $L\left(  u\right)  $ and $R\left(  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(  u\right)  $ and $R\left(  u\right)  $ can be viewed as
$\left\vert G\right\vert \times\left\vert G\right\vert $-matrices.

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

\item[$\circled{$\ast$}$] When $\mathbf{k}$ is a field, each $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(  u\right)  =0$. This is also the minimal polynomial of the
endomorphisms $L\left(  u\right)  $ and $R\left(  u\right)  $.

\item Minimal polynomials also exist for $\mathbf{k}=\mathbb{Z}$:

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

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

\item \textbf{Theorem 1.2.} Assume that $\mathbf{k}$ is a field. Let
$u\in\mathbf{k}\left[  G\right]  $. Then, $L\left(  u\right)  \sim R\left(
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(  u\right)  \sim R\left(  u\right)  $ would fail
if we allowed $G$ to be a monoid.

\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(  ab\right)  =S\left(  b\right)  \cdot S\left(  a\right)  $
for all $a,b$).

\item \textbf{Lemma 1.4.} Assume that $\mathbf{k}$ is a field. Let
$u\in\mathbf{k}\left[  G\right]  $. Then, $L\left(  u\right)  \sim L\left(
S\left(  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(  u\right)  \right)  $ in this basis is the
transpose of the matrix representing $L\left(  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 $u\in\mathbf{k}\left[  G\right]  $. Then,
$L\left(  S\left(  u\right)  \right)  \sim R\left(  u\right)  $ in
$\operatorname*{End}\nolimits_{\mathbf{k}}\left(  \mathbf{k}\left[  G\right]
\right)  $.

\item \textit{Proof:} We have $R\left(  u\right)  =S\circ L\left(  S\left(
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.} The conjugacy $L\left(  u\right)  \sim R\left(
u\right)  $ can fail if $\mathbf{k}$ is not a field (e.g., for $\mathbf{k}%
=\mathbb{Q}\left[  t\right]  $ and $G=S_{3}$).

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

\newpage

\section{The symmetric group algebra}

\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!)

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

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

\item[$\circled{$\ast$}$] \textbf{Theorem 2.2.} Let $\mathbf{k}$ be a field of
characteristic $0$. Let $u\in\mathbf{k}\left[  S_{n}\right]  $. Then, $u\sim
S\left(  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(  u\right)  $ are the transposes of the
matrices corresponding to $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:} More generally, let $G$ be an
\emph{ambivalent} finite group (i.e., a finite group in which each $g\in G$ is
conjugate to $g^{-1}$). Let $u\in\mathbf{k}\left[  G\right]  $. Then, $u\sim
S\left(  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 $u$ and $S\left(  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(  u\mid_{V}\right)  \sim\left(  u\mid_{V^{\ast}}\right)  \sim\left(
S\left(  u\right)  \mid_{V}\right)  ^{T}\sim\left(  S\left(  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 We now go further down the abstraction pole and study 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.} $\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}%
\[
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 $m_{1}=0$. Also, $S\left(  m_{k}\right)  =m_{k}$
for each $k\in\left[  n\right]  $.

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

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

\item[$\circled{$\ast$}$] \textbf{Theorem 3.2.} The minimal polynomial of
$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 $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 $m_{k}$ and $m_{k+1}$ are
simultaneously diagonalizable over $\mathbb{C}$ (since they are symmetric as
real matrices and commute) and satisfy $s_{k}m_{k+1}=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\left\{  0,1,\ldots,n\right\}  $, we
can evaluate the $k$-th elementary symmetric polynomial $e_{k}$ at the YJM
elements $m_{1},m_{2},\ldots,m_{n}$ to obtain%
\[
e_{k}\left(  m_{1},m_{2},\ldots,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).

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

\item \textbf{Theorem 3.4 (Murphy).}
\begin{align*}
&  \left\{  f\left(  m_{1},m_{2},\ldots,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).
\end{itemize}

(For $\mathbf{k}=\mathbb{Q}$, this is Theorem 4.4.5 in
\href{https://doi.org/10.1017/CBO9781139192361}{CS/S/T} as well.)
\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(  u\right)  $ or $R\left(  u\right)  $ for
some $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(
m_{k}\right)  $ by the YJM element $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}.

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

\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 essentially 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}_{i}$ 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=-n^{2}}^{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{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}$ ? Does it have dimension $O\left(  n^{2}\right)  $ ?
Some small values:%
\[%
\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{R}_{0},\mathbf{R}_{1},\ldots
,\mathbf{R}_{n}\right]  \right)  $ & $1$ & $2$ & $4$ & $7$ & $15$ &
$30$\\\hline
\end{tabular}
\
\]


\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 isn't all that helpful, since the $\mathbf{B}_{k}$ don't commute with
the $S\left(  \mathbf{B}_{k}\right)  $.
\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} $t_{1},t_{2},\ldots,t_{n}$ by setting%
\[
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]  $.

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

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

\item Their linear combinations%
\[
\lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}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:} $t_{1},t_{2},\ldots,t_{n}$ do not commute for $n\geq3$.
For $n=3$, we have%
\[
\left[  t_{1},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(  t_{1}\right)  ,R\left(
t_{2}\right)  ,\ldots,R\left(  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%
\[
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 $a_{w}$ by breaking up the word $w$ into maximal
decreasing factors and re-sorting each factor arbitrarily (without mixing
different factors).

\item[$\circled{$\ast$}$] The family $\left(  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*}
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]  ;\\
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]  ;\\
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]  ;\\
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]  ;\\
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]  ;\\
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%
\[
a_{w}t_{\ell}=\mu_{w,\ell}a_{w}+\sum_{\substack{v\in S_{n};\\v\prec w}%
}\lambda_{w,\ell,v}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(  t_{1}\right)  ,R\left(  t_{2}\right)
,\ldots,R\left(  t_{n}\right)  $ are upper-triangular with respect to the
basis $\left(  a_{w}\right)  _{w\in S_{n}}$.

\item \textit{Examples:}

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


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

\item \textbf{Corollary 7.2.} The eigenvalues of these endomorphisms
\newline$R\left(  t_{1}\right)  ,R\left(  t_{2}\right)  ,\ldots,R\left(
t_{n}\right)  $ and of all their linear combinations%
\[
R\left(  \lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}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(  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(
t_{\ell}\right)  $'s have even fewer.

\item But their linear combinations $R\left(  \lambda_{1}t_{1}+\lambda
_{2}t_{2}+\cdots+\lambda_{n}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}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda
_{n}t_{n}\right)  $ is $f_{n+1}$. In this case, the endomorphism $R\left(
\lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}\right)  $ is diagonalizable.

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

\item[$\circled{$\ast$}$] One way such a theorem can be proved is 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(  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(
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)  $ 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\}
\]
and%
\[
I^{\prime}:=\left[  n-1\right]  \setminus\left(  I\cup\left(  I-1\right)
\right)
\]
and%
\[
F\left(  I\right)  :=\left\{  q\in\mathbf{k}\left[  S_{n}\right]
\ \mid\ qs_{i}=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[$\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\}  .
\]


For 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)  .
\]
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,%
\[
qt_{\ell}\in m_{I,\ell}q+\sum_{\substack{J\subseteq\left[  n\right]
;\\\operatorname*{sum}J<\operatorname*{sum}I}}F\left(  J\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }q\in F\left(  I\right)  .
\]


\item \textit{Proof:} Expand $qt_{\ell}$ by the definition of $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}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.

\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]
\]
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(  t_{\ell}-m_{Q_{i}%
,\ell}\right)  \subseteq F_{i-1}$ (so that $R\left(  t_{\ell}\right)  $ acts
as multiplication by $m_{Q_{i},\ell}$ on $F_{i}/F_{i-1}$).

\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}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda
_{n}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.
\end{itemize}

\newpage

\section{Back to the basis}

\begin{itemize}
\item The descent-destroying basis $\left(  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(  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$\emph{-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[$\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(  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{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%
\[
a_{w}t_{\ell}=\mu_{w,\ell}a_{w}+\sum_{\substack{v\in S_{n}%
;\\\operatorname*{Qind}v<\operatorname*{Qind}w}}\lambda_{w,\ell,v}a_{v}%
\]
for some nonnegative integer $\mu_{w,\ell}$ and some integers $\lambda
_{w,\ell,v}$.

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

\item Note that 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.
Nevertheless, our construction is \textquotedblleft
essentially\textquotedblright\ independent of choices, since Proposition 10.2
describes $Q_{\operatorname*{Qind}w}$ independently of this numbering (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$). To
get rid of the dependence on the numbering, we should think of the filtration
as being indexed by a poset.
\end{itemize}

\newpage

\section{The multiplicities}

\begin{itemize}
\item With Corollary 10.4, we know not only the eigenvalues of the $R\left(
t_{\ell}\right)  $'s, but also their multiplicities:

\item[$\circled{$\ast$}$] \textbf{Corollary 11.1.} 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]  $, let $\delta_{i}$ be the number of all
permutations $w\in S_{n}$ satisfying $\operatorname*{Qind}w=i$, and 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}t_{1}+\lambda_{2}%
t_{2}+\cdots+\lambda_{n}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]  $. Let $\delta_{i}$ be the number of all permutations $w\in
S_{n}$ satisfying $\operatorname*{Qind}w=i$. 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{Question.} This reminds of the hook-length formula for standard
tableaux. Is it connected to Fibonacci tableaux (paths in the Young--Fibonacci lattice)?
\end{itemize}

\newpage

\section{Variants}

\begin{itemize}
\item Most of what we said about the somewhere-to-below shuffles $t_{\ell}$
can be extended to their antipodes $S\left(  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(  t_{1}\right)  \right)  ,R\left(  S\left(  t_{2}\right)  \right)
,\ldots,R\left(  S\left(  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(
t_{1}\right)  ,L\left(  t_{2}\right)  ,\ldots,L\left(  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(  t_{\ell}\right)  \sim R\left(
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 $t_{\ell}\sim S\left(  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{Conjectures and questions}

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

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

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

\item[$\circled{$\ast$}$] \textbf{Conjecture 13.2.} We have $\left[
t_{i},t_{j}\right]  ^{n-j+1}=0$ for any $1\leq i<j\leq n$.

\item[$\circled{$\ast$}$] \textbf{Conjecture 13.3.} We have $\left[
t_{i},t_{j}\right]  ^{n-j}=0$ for any $1\leq i<j<n-1$.

\item[$\circled{$\ast$}$] We can prove Conjecture 13.1 for $j=i+1$ and
Conjecture 13.2 for $j=n-1$. We can also show that
\begin{align*}
&  t_{n-1}\left[  t_{i},t_{n-1}\right]  =0\ \ \ \ \ \ \ \ \ \ \text{and}%
\ \ \ \ \ \ \ \ \ \ \left[  t_{i},t_{n-1}\right]  \left[  t_{j},t_{n-1}%
\right]  =0\\
\text{and}\ \ \ \ \ \ \ \ \ \  &  t_{i+1}t_{i}=\left(  t_{i}-1\right)  t_{i}%
\end{align*}
for all $i$ and $j$.

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

{\small To answer a question: The Lie subalgebra }$\mathcal{L}\left(
t_{1},t_{2},\ldots,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(  t_{1},t_{2},\ldots,t_{n}\right)  \right)  $ &
$1$ & $2$ & $4$ & $8$ & $20$ & $59$ & $196$\\\hline
\end{tabular}
\
\]
{\small (also not in the OEIS).}

\item \textbf{Question.} How do the $F\left(  I\right)  $ and the $F_{i}$
decompose into Specht modules when $\mathbf{k}$ is a field of characteristic
$0$ ?

\item \textbf{Question.} How do $t_{1},t_{2},\ldots,t_{n}$ act on a given
Specht module?
\end{itemize}

\newpage

\section{I thank}

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

\item \textbf{Martin Lorenz, Franco Saliola, Marcelo Aguiar, Vic Reiner,
Travis Scrimshaw} for helpful conversations recent and not so recent.

\item \textbf{G\'erard Duchamp} for the invitation.

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


\end{document}