%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2024}
\articlenumber{16}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{example}{Example}

%% define your title in the usual way
\title[Somewhere-to-below shuffles]{The somewhere-to-below shuffles in the symmetric group and Hecke algebras}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Darij Grinberg\thanks{\href{mailto:darijgrinberg@gmail.com}{darijgrinberg@gmail.com}}\addressmark{1} \and Nadia Lafreni\`{e}re\thanks{\href{mailto:nadia.lafreniere@concordia.ca}{nadia.lafreniere@concordia.ca}}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Mathematics Department, Drexel University, Philadelphia, PA, USA \\
\addressmark{2}Department of Mathematics \& Statistics, Concordia University, Montreal, QC, Canada}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We introduce and study the \emph{somewhere-to-below shuffles},
which are elements of the group algebra of the symmetric group $S_n$ defined 
as sums of cycles. 
We show that these elements are
simultaneously triangularizable (in an easily-defined basis of
$\mathbf{k}\left[  S_{n}\right]$), and compute their joint
eigenvalues with multiplicities.
We furthermore discuss some identities between them, a
card shuffling interpretation and its probabilistic properties, and a possible 
generalization to the Hecke algebra.}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{symmetric group, permutations, card shuffling,
top-to-random shuffle, group algebra, substitutional analysis, Fibonacci
numbers, filtration, representation theory, Markov chain, Specht module,
symmetric functions}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{biblio.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\usepackage{comment}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}

\begin{document}

\maketitle

\section{Introduction}

The group algebra $\mathbf{k}\left[  S_{n}\right]  $ of the symmetric group
$S_{n}$ is one of the most elementary, yet richest examples of an algebra in
combinatorics. Over a characteristic-zero field, it is known (by the
representation theory of the symmetric group) to be isomorphic to a direct
product of matrix rings, a viewpoint that clarifies some of its features while
obscuring others. The structure of $\mathbf{k}\left[  S_{n}\right]  $ becomes
more interesting when $\mathbf{k}$ is less well-behaved (e.g., the ring
$\mathbb{Z}$), but also when combinatorics is invited back onto the stage.

The latter can be done by defining a simple-looking family of elements of
$\mathbf{k}\left[  S_{n}\right]  $ combinatorially and asking algebraic
questions: Do its elements commute? Do they have integer eigenvalues (viewed
as endomorphisms of $\mathbf{k}\left[  S_{n}\right]  $ by left
multiplication)? What subalgebra do they generate? Such families often come
with a rich provenance. Examples are the Young--Jucys--Murphy elements
(originating from representation theory), the
Eulerian idempotents (born in homological algebra) and
the more recent Wronski--Purbhoo elements (inspired by mathematical physics).

A wide class of recent examples has come from probability theory, the most
elementary example being perhaps the \emph{top-to-random shuffle}%
\[
t_{1}:=\operatorname*{cyc}\nolimits_{1}+\operatorname*{cyc}\nolimits_{1,2}%
+\operatorname*{cyc}\nolimits_{1,2,3}+\cdots+\operatorname*{cyc}%
\nolimits_{1,2,\ldots,n}\in\mathbf{k}\left[  S_{n}\right]  ,
\]
where $\operatorname*{cyc}\nolimits_{i_{1},i_{2},\ldots,i_{m}}$ denotes the
$m$-cycle sending $i_{1}\mapsto i_{2}\mapsto\cdots\mapsto i_{m}\mapsto i_{1}$.
After this shuffle was fully analyzed in 1986 \cite{Wallach88}, several
generalizations and extensions have come up
and are still undergoing active research.

The work outlined in this abstract, and detailed in our papers \cite{s2b1} and
\cite{s2b2} (and forthcoming work), concerns the perhaps simplest way to
generalize the top-to-random shuffle: namely, by embedding it in the $n$-tuple
$\left(  t_{1},t_{2},\ldots,t_{n}\right)  $ of the \emph{somewhere-to-below
shuffles}%
\[
t_{i}:=\operatorname*{cyc}\nolimits_{i}+\operatorname*{cyc}\nolimits_{i,i+1}%
+\operatorname*{cyc}\nolimits_{i,i+1,i+2}+\cdots+\operatorname*{cyc}%
\nolimits_{i,i+1,\ldots,n}\in\mathbf{k}\left[  S_{n}\right]
\]
for all $i\in\left\{  1,2,\ldots,n\right\}  $. These $n$ shuffles have a
simple probabilistic meaning (shuffling a deck of cards by picking the $i$-th
card from the top and randomly moving it further down the deck), and are also
related to the insertion sort algorithm and to subgroups (each $t_{i}$ is a
sum of coset representatives for a certain $S_{n-i}$ subgroup inside
$S_{n-i+1}$).

The somewhere-to-below shuffles $t_{1},t_{2},\ldots,t_{n}$ do not commute, but
they \textquotedblleft commute up to nilpotent error terms\textquotedblright.
In rigorous language, this means that there exists a basis $\left(
a_{1},a_{2},\ldots,a_{n!}\right)  $ of the $\mathbf{k}$-module $\mathbf{k}%
\left[  S_{n}\right]  $ on which these elements act from the right as
upper-triangular matrices (i.e., we have $a_{k}t_{\ell}\in\operatorname*{span}%
\left(  a_{1},a_{2},\ldots,a_{k}\right)  $ for each $k$). This basis can be
constructed explicitly over any ring $\mathbf{k}$, in contrast to the more
classical diagonalizing bases that exist for various other known families but
only over characteristic-$0$ fields. (A common diagonalizing basis is
impossible for the $t_{1},t_{2},\ldots,t_{n}$, since some of their linear
combinations fail to act semisimply.) A more conceptual but less catchy
formulation of our main result is the existence of 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]  $ that is
preserved by the somewhere-to-below shuffles $t_{1},t_{2},\ldots,t_{n}$
(acting from the right), and on whose quotients $F_{i}/F_{i-1}$ these shuffles
act as scalars. The length of this filtration is (rather unexpectedly) the
$\left(  n+1\right)  $-st \emph{Fibonacci number} $f_{n+1}$.

A consequence of all this is that each linear combination $\lambda_{1}%
t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}$ of the somewhere-to-below
shuffles has explicitly computable eigenvalues, which are all integers if the
coefficients $\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ are, and of which at
most $f_{n+1}$ are distinct. Their multiplicities (in the generic case) are
certain divisors of $n!$, counting some kinds of permutations. We give the
constructions and say a few words on the proofs below; details can be found in
\cite{s2b1}. Some variants of these results (replacing right by left
multiplication, and replacing the $t_{1},t_{2},\ldots,t_{n}$ by their
\textquotedblleft antipodes\textquotedblright) are briefly outlined in Section
\ref{sec.vars}.

The filtration above explains much but not everything. In particular, it shows
that the commutators $\left[  t_{i},t_{j}\right]  $ are nilpotent, but gives
fairly bad (exponential) bounds on their nilpotency degrees. The actual
nilpotency degrees, however, are much smaller (in fact, no larger than
$n/2+1$). This is elaborated upon in Section \ref{sec.nilp}, but the detailed
proofs are too long to even hint at; they can be found in \cite{s2b2}.

The motivation for studying the somewhere-to-below shuffles comes largely from 
probability theory. Card shuffling can be thought of applying a permutation at 
random, according to some probability, to a deck of cards. For us, 
it means acting on the right by an element of $\mathbf{k}\left[  S_{n}\right]$ 
whose coefficients are nonnegative reals. A question of interest is thus, given the 
choice of an element of  $\mathbf{k}\left[  S_{n}\right]$, how many 
applications of it would suffice to shuffle the deck of cards properly. In 
Section \ref{sec.stoppingtime}, we give an optimal strong stationary time 
for linear combinations of the somewhere-to-below shuffles.

Anything about $\mathbf{k}\left[  S_{n}\right]  $ is, of course, connected to
integer partitions and Young diagrams, since the irreducible representations
of $\mathbf{k}\left[  S_{n}\right]  $ are the \emph{Specht modules}
$S^{\lambda}$ assigned to the partitions $\lambda$ of $n$. Thus, one can
wonder how the somewhere-to-below shuffles $t_{1},t_{2},\ldots,t_{n}$ act on a
given Specht module $S^{\lambda}$. We answer this in Section \ref{sec.rep};
the proof will appear in forthcoming work.

In the last Section \ref{sec.hecke}, we suggest a further potential
generalization, replacing the symmetric group algebra $\mathbf{k}\left[
S_{n}\right]  $ by the Hecke algebra $\mathcal{H}_{n}\left(  q\right)  $. We
have only just began the study of this setting, but it appears that many of
our results extend to it. Research on this, as well as on our Specht module
conjecture, is underway.



\section{\label{sec.def}Definitions}

\subsection{Combinatorics}

Let us first introduce some basic notations (more will be defined as needed).
We set $\mathbb{N}:=\left\{  0,1,2,\ldots\right\}  $. Furthermore, we set
$\left[  a,b\right]  :=\left\{  x\in\mathbb{Z}\ \mid\ a\leq x\leq b\right\}  $
for any $a,b\in\mathbb{Z}$. For any $k\in\mathbb{Z}$, we set $\left[
k\right]  :=\left[  1,k\right]  =\left\{  1,2,\ldots,k\right\}  $.

We fix a positive integer $n$. We let $S_{n}$ denote the $n$-th symmetric
group; it consists of the $n!$ permutations of $\left[  n\right]  $, with
multiplication given by composition: $\left(  \alpha\beta\right)  \left(
i\right)  =\alpha\left(  \beta\left(  i\right)  \right)  $ for each
$\alpha,\beta\in S_{n}$ and $i\in\left[  n\right]  $.

\subsection{\label{subsec.def.alg}Algebra}

We fix a commutative ring $\mathbf{k}$. (The cases $\mathbf{k}=\mathbb{Z}$ and
$\mathbf{k}=\mathbb{Q}$ are fully sufficient.)

We let $\mathbf{k}\left[  S_{n}\right]  $ denote the group algebra of $S_{n}$
over $\mathbf{k}$. This $\mathbf{k}$-algebra consists of all formal
$\mathbf{k}$-linear combinations $\sum_{\sigma\in S_{n}}\lambda_{\sigma}%
\sigma$ of the permutations $\sigma\in S_{n}$, and its multiplication is the
$\mathbf{k}$-linear extension of the multiplication on $S_{n}$. Its unity is
$1=\operatorname*{id}\nolimits_{\left[  n\right]  }\in S_{n}$.

For each $u\in\mathbf{k}\left[  S_{n}\right]  $, we define the two
$\mathbf{k}$-linear maps $L\left(  u\right)  :\mathbf{k}\left[  S_{n}\right]
\rightarrow\mathbf{k}\left[  S_{n}\right]  $ and $R\left(  u\right)
:\mathbf{k}\left[  S_{n}\right]  \rightarrow\mathbf{k}\left[  S_{n}\right]  $
by%
\[
\left(  L\left(  u\right)  \right)  \left(  a\right)
=ua\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \left(  R\left(
u\right)  \right)  \left(  a\right)  =au\ \ \ \ \ \ \ \ \ \ \text{for each
}a\in\mathbf{k}\left[  S_{n}\right]  .
\]
These are just the left multiplication and the right multiplication by $u$.
Being endomorphisms of the $\mathbf{k}$-module $\mathbf{k}\left[
S_{n}\right]  $, they can be represented as $n!\times n!$-matrices over
$\mathbf{k}$ (since $\mathbf{k}\left[  S_{n}\right]  $ is a free $\mathbf{k}%
$-module of rank $n!$, with basis $\left(  w\right)  _{w\in S_{n}}$), and thus
have characteristic polynomials, eigenvalues and eigenvectors (at least when
$\mathbf{k}$ is a field).

\subsection{Cycles, somewhere-to-below and other random-to-below shuffles}

For any distinct elements $i_{1},i_{2},\ldots,i_{k}$ of $\left[  n\right]  $,
we 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. In particular, $\operatorname*{cyc}%
\nolimits_{i,j}$ is a transposition, while $\operatorname*{cyc}\nolimits_{i}%
=\operatorname*{id}=1$.

We are now ready for our main definition: For each $\ell\in\left[  n\right]
$, we define the element%
\[
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]  .
\]
These $n$ elements $t_{1},t_{2},\ldots,t_{n}$ will be called the
\emph{somewhere-to-below shuffles}. The first of these elements, $t_{1}$, is
also known as the \emph{top-to-random shuffle} or the \emph{Tsetlin library},
whereas the last is just the identity ($t_{n}=\operatorname*{cyc}%
\nolimits_{n}=1$).

Linear combinations of the somewhere-to-below shuffles are also interesting. 
Assuming the coefficients $\lambda_{1},\lambda_{2},\ldots, \lambda_n$ are 
nonnegative reals, $\lambda_{1}t_1 + \lambda_{2}t_2 + 
\ldots +\lambda_n t_n$ represents the action of choosing the $i$-th 
somewhere-to-below shuffle  with some probability dictated by $\lambda_i$. 
In particular, the \textit{random-to-below shuffle} is the 
shuffle in which we pick $i$ with uniform probability (among $[n]$), and then 
apply the $i$-th somewhere-to-below shuffle. In terms of card shuffling, this 
amounts to drawing a card (uniformly) at random and moving it weakly below. See 
\cite[\S 3]{s2b1} for other interesting shuffles of this sort.

\section{\label{sec.ddb}The descent-destroying basis}

The $n$ somewhere-to-below shuffles do not commute (e.g., we have $t_{1}%
t_{2}\neq t_{2}t_{1}$ for $n=3$). Nevertheless, they behave far better than a
\textquotedblleft random\textquotedblright\ family of elements of
$\mathbf{k}\left[  S_{n}\right]  $. In particular, there exists a basis of the
$\mathbf{k}$-module $\mathbf{k}\left[  S_{n}\right]  $ in which all of the
endomorphisms $R\left(  t_{1}\right)  ,R\left(  t_{2}\right)  ,\ldots,R\left(
t_{n}\right)  $ are represented by upper-triangular matrices. We shall
construct this basis now. This requires some more definitions.

For each $w\in S_{n}$, we define the \emph{descent set} of $w$ to be the set%
\[
\operatorname*{Des}w:=\left\{  i\in\left[  n-1\right]  \ \mid\ w\left(
i\right)  >w\left(  i+1\right)  \right\}  .
\]


For each $i\in\left[  n-1\right]  $, we define the \emph{simple transposition}
$s_{i}:=\operatorname*{cyc}\nolimits_{i,i+1}\in S_{n}$.

For each $I\subseteq\left[  n-1\right]  $, we define the \emph{Young subgroup}
$G\left(  I\right)  $ to be the subgroup of $S_{n}$ generated by the $s_{i}$
for $i\in I$. This can be viewed as a product $S_{n_{1}}\times S_{n_{2}}%
\times\cdots\times S_{n_{k}}$ with $n_{1}+n_{2}+\cdots+n_{k}=n$, embedded into
$S_{n}$ via the canonical homomorphism.

For each $w\in S_{n}$, we define%
\[
a_{w}:=\sum_{\sigma\in G\left(  \operatorname*{Des}w\right)  }w\sigma
\in\mathbf{k}\left[  S_{n}\right]  .
\]
The following is easy to see by triangularity:

\begin{proposition}
The family $\left(  a_{w}\right)  _{w\in S_{n}}$ is a basis of the
$\mathbf{k}$-module $\mathbf{k}\left[  S_{n}\right]  $.
\end{proposition}

\begin{example}
For $n=3$, we have%
\[%
\begin{tabular}
[c]{ll|ll}%
$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]  ;$ &
$\vphantom{\int_f^f}$ &  & $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}{1}}\textcolor{red}{32}\right]  }=\left[
{\textcolor{blue}{1}}\textcolor{red}{32}\right]  +\left[
{\textcolor{blue}{1}}\textcolor{red}{23}\right]  ;$ & $\vphantom{\int_f^f}$ &
& $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}{21}\textcolor{red}{3}\right]  }=\left[
\textcolor{blue}{21}\textcolor{red}{3}\right]  +\left[
\textcolor{blue}{12}\textcolor{red}{3}\right]  ;$ & $\vphantom{\int_f^f}$ &  &
$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{tabular}
\]
(where we use one-line notation for permutations: $\left[  i_{1}i_{2}\cdots
i_{n}\right]  $ means the permutation of $\left[  n\right]  $ that sends
$1,2,\ldots,n$ to $i_{1},i_{2},\ldots,i_{n}$).
\end{example}

Now, we claim that the endomorphisms $R\left(  t_{1}\right)  ,R\left(
t_{2}\right)  ,\ldots,R\left(  t_{n}\right)  $ are upper-triangular with
respect to this basis (appropriately ordered). More concretely:

\begin{theorem}
\label{thm.ddb}There is some partial order $\prec$ on $S_{n}$ such that 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}\ \ \ \ \ \ \ \ \ \ \text{for some }\mu_{w,\ell}%
\in\mathbb{N}\text{ and }\lambda_{w,\ell,v}\in\mathbb{Z}.
\]

\end{theorem}

\begin{example}
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]  }$.
\end{example}

\section{\label{sec.Fi}The invariant spaces $F\left(  I\right)  $}

To prove Theorem \ref{thm.ddb} directly, we would need to understand how
$R\left(  t_{\ell}\right)  $ acts on each single $a_{w}$. But this is not
easy. Thus, we shall instead analyze the action of $R\left(  t_{\ell}\right)
$ on a certain filtration $0=F_{0}\subseteq F_{1}\subseteq F_{2}%
\subseteq\cdots\subseteq F_{f_{n+1}}=\mathbf{k}\left[  S_{n}\right]  $ of
$\mathbf{k}\left[  S_{n}\right]  $ by left ideals (which are
preserved by the $R\left(  t_{\ell}\right)  $). The basis $\left(
a_{w}\right)  _{w\in S_{n}}$ will then reveal itself to be compatible
with this filtration (i.e., each $F_{i}$ is spanned by some subfamily of this
basis), and thus we will be able to draw conclusions about $a_{w}t_{\ell}$
from the action of $R\left(  t_{\ell}\right)  $ on the filtration.
Essentially, the filtration will act as a \textquotedblleft
middleman\textquotedblright\ between the $t_{\ell}$ and the $a_{w}$.

In order to construct the filtration, we shall in turn need another middleman:
some left ideals $F\left(  I\right)  $ defined for each $I\subseteq\left[
n\right]  $. These are easy to define:

For each subset $I$ of $\left[  n\right]  $, we define the number
\[
\operatorname*{sum}I:=\sum_{i\in I}i,
\]
and the sets
\[
\widehat{I}:=\left\{  0\right\}  \cup I\cup\left\{  n+1\right\}
\qquad \qquad \text{and} \qquad \qquad
%\ \ \ \ \ \ \ \ \ \ \left(  \text{the \textquotedblleft\emph{enclosure}%
%\textquotedblright\ of }I\right)  ,
%\]
%and the set%
%\[
I^{\prime}:=\left[  n-1\right]  \setminus\left(  I\cup\left(  I-1\right)
\right)
%  \ \ \ \ \ \ \ \ \ \ \left(  \text{the \textquotedblleft%
%\emph{non-shadow}\textquotedblright\ of }I\right)
\]
(where $I-1:=\left\{  i-1\ \mid\ i\in I\right\}  $), and finally the left
ideal%
\[
F\left(  I\right)  :=\left\{  u\in\mathbf{k}\left[  S_{n}\right]
\ \mid\ us_{i}=u\text{ for all }i\in I^{\prime}\right\}  \subseteq
\mathbf{k}\left[  S_{n}\right]
\]
(the \textquotedblleft\emph{invariant space}\textquotedblright\ corresponding
to $I$).

\begin{example}
Let $n=9$ and $I=\left\{  2,3,7\right\}  $. Then, $\widehat{I}=\left\{
0,2,3,7,10\right\}  $ and $I^{\prime}=\left[  8\right]  \setminus\left\{
1,2,3,6,7\right\}  =\left\{  4,5,8\right\}  $ and $F\left(  I\right)
=\left\{  u\in\mathbf{k}\left[  S_{n}\right]  \ \mid\ us_{4}=us_{5}%
=us_{8}=u\right\}  $.
\end{example}

The following is easy to see:

\begin{proposition}
\label{prop.FI.basis}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)  $.
\end{proposition}

The main workhorse of our study of the somewhere-to-below shuffles is a lemma
which, for each $I\subseteq\left[  n\right]  $ and $\ell\in\left[  n\right]  $
and $u\in F\left(  I\right)  $, expresses the product $ut_{\ell}$ as a scalar
multiple of $u$ plus a sum of \textquotedblleft error terms\textquotedblright%
\ in \textquotedblleft smaller\textquotedblright\ invariant spaces $F\left(
J\right)  $ (to be precise: invariant spaces $F\left(  J\right)  $ for subsets
$J\subseteq\left[  n\right]  $ satisfying $\operatorname*{sum}%
J<\operatorname*{sum}I$). We can actually be more specific and characterize
the scalar in front of the $u$ as follows:

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


\begin{example}
If $n=9$ and $I=\left\{  2,3,7\right\}  $, then $\widehat{I}=\left\{
0,2,3,7,10\right\}  $ and%
\[
\left(  m_{I,1},\ m_{I,2},\ \ldots,\ m_{I,9}\right)  =\left(
1,0,0,3,2,1,0,2,1\right)  .
\]

\end{example}

\begin{lemma}
[Workhorse lemma]\label{lem.qtl}Let $I\subseteq\left[  n\right]  $ and
$\ell\in\left[  n\right]  $. Then,%
\[
ut_{\ell}\in m_{I,\ell}u+\sum_{\substack{J\subseteq\left[  n\right]
;\\\operatorname*{sum}J<\operatorname*{sum}I}}F\left(  J\right)
\ \ \ \ \ \ \ \ \ \ \text{for each }u\in F\left(  I\right)  .
\]

\end{lemma}

\begin{proof}
[Proof idea.] Expand $ut_{\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}u$
term; the others live in appropriate $F\left(  J\right)  $'s. See
\cite[Theorem 7.3]{s2b1} for details.
\end{proof}


\section{\label{sec.fib}The Fibonacci filtration}

The filtration $0=F_{0}\subseteq F_{1}\subseteq F_{2}\subseteq\cdots\subseteq
F_{f_{n+1}}=\mathbf{k}\left[  S_{n}\right]  $ that we want to construct will
consist of sums of certain invariant spaces $F\left(  I\right)  $. However, we
do not need all $F\left(  I\right)  $, but only the ones that correspond to
certain subsets $I$: namely, those that are \emph{lacunar} (i.e., contain no
two consecutive integers) and do not contain $n$. Arranging these lacunar
subsets $I$ in order of increasing sum, we will define
$F_{i}$ as the sum of the $F\left(  I\right)  $ corresponding to the first $i$
many $I$'s.

Let us elaborate on this. A set $S$ of integers is called \emph{lacunar} if it
contains no two consecutive integers (i.e., we have $s+1\notin S$ for all
$s\in S$). The number of lacunar subsets of $\left[  n-1\right]  $ is known to
be the Fibonacci number $f_{n+1}$. (Recall that the Fibonacci numbers
$f_{0},f_{1},f_{2},\ldots$ are defined by $f_{0}=0$ and $f_{1}=1$ and
$f_{k}=f_{k-1}+f_{k-2}$ for each $k\geq2$.)

The following lemma (essentially \cite[Proposition 8.7]{s2b1}) is easy to check:

\begin{lemma}
\label{lem.red-to-lac}Let $J\subseteq\left[  n\right]  $ be a subset that
fails to be lacunar or contains $n$. Then, there exists some subset
$K\subseteq\left[  n\right]  $ such that $\operatorname*{sum}%
K<\operatorname*{sum}J$ and $K^{\prime}\subseteq J^{\prime}$ (so that
$F\left(  J\right)  \subseteq F\left(  K\right)  $).
\end{lemma}

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)  $. (We fix such an
order once and for all.) Then, for each $i\in\left[  0,f_{n+1}\right]  $,
define a left ideal%
\[
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]
\]
(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 following crucial property:

\begin{theorem}
\label{thm.fibfil.tl}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)  $ preserves
$F_{i}$ and $F_{i-1}$, and acts as multiplication by $m_{Q_{i},\ell}$ on
$F_{i}/F_{i-1}$).
\end{theorem}

\begin{proof}
[Proof idea.] This follows from Lemmas \ref{lem.qtl}
and \ref{lem.red-to-lac}. See \cite[Theorem 8.1
\textbf{(c)}]{s2b1} for details.
\end{proof}


\begin{noncompile}
\begin{proof}
[Proof idea.] Apply Lemma \ref{lem.qtl}; then observe that the sum
$\sum_{\substack{J\subseteq\left[  n\right]  ;\\\operatorname*{sum}%
J<\operatorname*{sum}I}}F\left(  J\right)  $ on the right hand side can be
reduced to the smaller sum $\sum_{\substack{J\subseteq\left[  n-1\right]
\text{ is lacunar;}\\\operatorname*{sum}J<\operatorname*{sum}I}}F\left(
J\right)  $ (by Lemma \ref{lem.red-to-lac}). See \cite[Theorem 8.1
\textbf{(c)}]{s2b1} for details.
\end{proof}

\end{noncompile}

Now we claim that our basis $\left(  a_{w}\right)  _{w\in S_{n}}$ of
$\mathbf{k}\left[  S_{n}\right]  $ respects the filtration $0=F_{0}\subseteq
F_{1}\subseteq F_{2}\subseteq\cdots\subseteq F_{f_{n+1}}=\mathbf{k}\left[
S_{n}\right]  $. To make this precise, we introduce some more notation:

The $Q$\emph{-index} $\operatorname*{Qind}w$ of a permutation $w\in S_{n}$ is
defined to be the \textbf{smallest} $i\in\left[  f_{n+1}\right]  $ such that
$Q_{i}^{\prime}\subseteq\operatorname*{Des}w$. (Note that this depends on our
ordering of $Q_{1},Q_{2},\ldots,Q_{f_{n+1}}$.)

The following facts (\cite[\S 10]{s2b1}) are not hard to see:

\begin{proposition}
\label{prop.Qind.=i}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}$.
\end{proposition}

\begin{theorem}
\label{thm.fibfilt.basis}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}$.
\end{theorem}

\begin{corollary}
\label{cor.fibfilt.basisquot}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}$.
\end{corollary}

\section{\label{sec.tria}Triangularizability}

Combining Theorem \ref{thm.fibfilt.basis} with Theorem \ref{thm.fibfil.tl}, we
easily obtain the following concretization of Theorem \ref{thm.ddb}
(\cite[Theorem 11.1]{s2b1}):

\begin{theorem}
\label{thm.awtl-Qind}Let $w\in S_{n}$ and $\ell\in\left[  n\right]  $. Let
$i=\operatorname*{Qind}w$. Then,%
\[
a_{w}t_{\ell}=m_{Q_{i},\ell}a_{w}+\sum_{\substack{v\in S_{n}%
;\\\operatorname*{Qind}v<\operatorname*{Qind}w}}\lambda_{w,\ell,v}%
a_{v}\ \ \ \ \ \ \ \ \ \ \text{for some integers }\lambda_{w,\ell,v}.
\]

\end{theorem}

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. Their diagonal entries are the
numbers $m_{Q_{\operatorname*{Qind}w},\ell}\in\mathbb{N}$.

Therefore, any $\mathbf{k}$-linear combination $R\left(  \sum\limits_{\ell
=1}^{n}\lambda_{\ell}t_{\ell}\right)  =\sum\limits_{\ell=1}^{n}\lambda_{\ell
}R\left(  t_{\ell}\right)  $ of these endomorphisms $R\left(  t_{1}\right)
,R\left(  t_{2}\right)  ,\ldots,R\left(  t_{n}\right)  $ (with $\lambda
_{1},\lambda_{2},\ldots,\lambda_{n}\in\mathbf{k}$) is upper-triangular with
respect to this basis as well, and its diagonal entries will be the
appropriate $\mathbf{k}$-linear combinations $\sum\limits_{\ell=1}^{n}%
\lambda_{\ell}m_{Q_{\operatorname*{Qind}w},\ell}$. Hence, regarded as an
$n!\times n!$-matrix, $R\left(  \sum\limits_{\ell=1}^{n}\lambda_{\ell}t_{\ell
}\right)  $ is triangularizable with eigenvalues $\sum\limits_{\ell=1}%
^{n}\lambda_{\ell}m_{Q_{\operatorname*{Qind}w},\ell}$ for $w\in S_{n}$.

This matrix is not always diagonalizable. A sufficient (but far from
necessary) criterion can nevertheless be given:

\begin{theorem}
\label{thm.evals.1}Let $\mathbf{k}$ be a field, and let $\lambda_{1}%
,\lambda_{2},\ldots,\lambda_{n}\in\mathbf{k}$. Then, the eigenvalues of the
operator $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}%
\]
(with multiplicities discussed below). If all these $f_{n+1}$ linear
combinations are distinct, then $R\left(  \lambda_{1}t_{1}+\lambda_{2}%
t_{2}+\cdots+\lambda_{n}t_{n}\right)  $ is diagonalizable.
\end{theorem}

\begin{proof}
[Proof idea.] The first claim follows from the discussion above; the second
uses Theorem \ref{thm.fibfil.tl} and some linear algebra. See \cite[Corollary
12.2 and Theorem 12.3]{s2b1} for details.
\end{proof}


\section{\label{sec.mult}Multiplicities of the eigenvalues}

We can also describe the multiplicities of the eigenvalues of $R\left(
\lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}\right)  $
(\cite[Theorem 13.2]{s2b1}):

\begin{theorem}
\label{thm.evals.2}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 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 $R\left(  \lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda
_{n}t_{n}\right)  $ equals the sum of the $\delta_{i}$ over all $i\in\left[
f_{n+1}\right]  $ satisfying $g_{i}=\kappa$.
\end{theorem}

Furthermore, these $\delta_{i}$ can be expressed by an explicit formula
(similar to but simpler than the famous hook-length formula), and are divisors
of $n!$ (just like in the hook-length formula); we refer to \cite[Theorem
13.1]{s2b1} for details.

\section{\label{sec.vars}Variants}

So far, we have directed our attention at the right multiplication maps
$R\left(  t_{1}\right)  ,R\left(  t_{2}\right)  ,\ldots,$\newline$R\left(
t_{n}\right)  $, while neglecting their left counterparts $L\left(
t_{1}\right)  ,L\left(  t_{2}\right)  ,\ldots,L\left(  t_{n}\right)  $.
However, almost all our claims about the former can be extended to the latter
using general properties of group algebras. In particular, 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.
This basis is not the basis $\left(  a_{w}\right)  _{w\in S_{n}}$, but rather
its dual basis with respect to a certain bilinear form (and its order is
modified). Theorems \ref{thm.evals.1} and \ref{thm.evals.2} remain valid if
\textquotedblleft$R$\textquotedblright\ is replaced by \textquotedblleft%
$L$\textquotedblright\ throughout them. For the proofs of all these claims, we
refer to \cite[\S 14]{s2b1}; all we shall say here is that they are derived
from the analogous properties of $R$ purely algebraically, with no further
combinatorial input.

It is also natural to study the \emph{below-to-somewhere shuffles}
$t_{1}^{\prime},t_{2}^{\prime},\ldots,t_{n}^{\prime}$, where%
\[
t_{\ell}^{\prime}:=\operatorname*{cyc}\nolimits_{\ell}+\operatorname*{cyc}%
\nolimits_{\ell+1,\ell}+\operatorname*{cyc}\nolimits_{\ell+2,\ell+1,\ell
}+\cdots+\operatorname*{cyc}\nolimits_{n,n-1,\ldots,\ell}\in\mathbf{k}\left[
S_{n}\right]
\]
for each $\ell\in\left[  n\right]  $. Again, Theorems \ref{thm.evals.1} and
\ref{thm.evals.2} remain valid if each $t_{\ell}$ is replaced by the
corresponding $t_{\ell}^{\prime}$; but this is again not too surprising, since
the $t_{\ell}^{\prime}$ are the images of $t_{\ell}$ under a very simple
$\mathbf{k}$-algebra anti-automorphism of $\mathbf{k}\left[  S_{n}\right]  $
called the \emph{antipode} (sending each permutation $w\in S_{n}$ to its
inverse $w^{-1}$). Thus, again, most properties can be transferred between the
$t_{\ell}$ and the $t_{\ell}^{\prime}$ by purely algebraic tools (see
\cite[\S 14]{s2b1} for details).

\section{\label{sec.nilp}Nilpotent commutators}

Since the endomorphisms $R\left( t_{1}\right)  ,R\left(  t_{2}\right)  ,
\ldots,R\left(  t_{n}\right)  $ are simultaneously triangularizable,
their pairwise commutators are nilpotent. Hence, the pairwise commutators
$\left[  t_{i},t_{j}\right]  $ in $\mathbf{k}\left[  S_{n}\right]  $ are also
nilpotent. A natural question is: How small is the required exponent?

As it turns out, it is much smaller than one might expect:

\begin{theorem}
\label{thm.nilp.m}Let $1\leq i\leq j\leq n$. Then,
\[
\left[  t_{i},t_{j}\right]  ^{m}=0\ \ \ \ \ \ \ \ \ \ \text{holds for }%
m=\min\left\{  j-i+1,\ \left\lceil \left(  n-j\right)  /2\right\rceil
+1\right\}  .
\]

\end{theorem}

We conjecture (and have verified for all $n\leq12$) that this choice of $m$ is
optimal (i.e., that $\left[  t_{i},t_{j}\right]  ^{m-1}\neq0$, at least for
$\mathbf{k}=\mathbb{Z}$).

Actually, Theorem \ref{thm.nilp.m} can be generalized, replacing the $m$-th
power of a single $\left[  t_{i},t_{j}\right]  $ by a product of several
$\left[  t_{i},t_{j}\right]  $'s (with the same $j$ but possibly different
$i$'s). The reader can find this generalization in \cite[Theorems 8.15 and
9.10]{s2b2}, where it is proved by long and tricky but completely elementary
manipulations of permutations and sums.

Several other curious facts hold, such as the following (\cite[Theorems 5.1
and 6.1, Corollaries 7.6 and 8.20]{s2b2}):

\begin{proposition}
\label{prop.ti+1ti}If $i\in\left[  n-1\right]  $, then $t_{i+1}t_{i}=\left(
t_{i}-1\right)  t_{i}$.

If $i\in\left[  n-2\right]  $, then $t_{i+2}\left(  t_{i}-1\right)  =\left(
t_{i}-1\right)  \left(  t_{i+1}-1\right)  $.
\end{proposition}

\begin{proposition}
Let $i,j\in\left[  n\right]  $. Then, $t_{n-1}\left[  t_{i},t_{n-1}\right]
=0$ and $\left[  t_{i},t_{n-1}\right]  \left[  t_{j},t_{n-1}\right]  =0$.
\end{proposition}

These facts suggest that the $\mathbf{k}$-subalgebra $\mathbf{k}\left[
t_{1},t_{2},\ldots,t_{n}\right]  $ of $\mathbf{k}\left[  S_{n}\right]  $ has
some interesting structure (apart from the \textquotedblleft
split-semisimple-by-nilpotent\textquotedblright\ decomposition following from
Theorem \ref{thm.ddb}). Yet it remains mysterious in many ways. For
$\mathbf{k}=\mathbb{Q}$ and $n \in \left[8\right]$, here is its
dimension as a $\mathbb{Q}$-vector space (the sequence is not in the OEIS
as of 2023-11-07!):
\begin{equation}%
\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[  t_{1},t_{2},\ldots,t_{n}\right]  \right)  $ &
$1$ & $2$ & $4$ & $9$ & $23$ & $66$ & $212$ & $761$\\\hline
\end{tabular}
\ \ \ \ \ . \label{eq.dimQt}%
\end{equation}

\section{\label{sec.stoppingtime}Probability theory}

We shall now make a few comments on the probabilistic side of
the one-sided cycle shuffles. Viewing them as shuffling 
operators, we are interested in the number of iterations needed to get a 
well-mixed deck of cards. We describe a strong stationary time for all one-sided cycle shuffles (see 
\cite[\S 10]{s2b1}), imitating a similar result for the
top-to-random shuffle (\cite{AldDia86}). Once the strong stationary time 
is reached, the deck is perfectly mixed.

%A stopping time for the one-sided cycle shuffles can be obtained using the
%following clever argument: Put a \textit{bookmark} right above the bottommost
%card before starting to shuffle, and assume that this bookmark is thin enough
%so it does not interfere with the shuffling process. At any given time, the
%cards that have been inserted below the bookmark will appear in a uniformly
%random relative order. Hence, the bookmark serves as a marker that
%distinguishes the fully mixed part (which is the part below the bookmark) from
%the rest of the deck. The bookmark itself is not considered to be a card in
%the deck, so the only way it moves is when a card that was above it is
%inserted below it.\footnote{We agree that if a card moves into the space that
%contains the bookmark, then it is inserted below (not above) the bookmark.}
%Thus, the bookmark never moves down but occasionally moves up the deck. The
%deck is mixed once the bookmark is at the top. The following theorem follows:

\begin{theorem}
\label{thm.times.stat-osc}If $\lambda_{1}\neq0$, then the one-sided cycle
shuffle $\lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}$ admits a
stopping time $\tau$ obtained as follows:
Place a bookmark right above the bottommost card of the deck.
The bookmark itself does not move (but cards can move down past it).
We let $\tau$ be the time it takes for the bookmark to reach the top of
the deck.

The distribution of the deck is uniform at time $\tau$ and any time
afterwards;
i.e., $\tau$ is a strong stationary time. Furthermore, this stopping
time is optimal.
\end{theorem}

If $\lambda_{1}= 0$, then the top card never moves, so the deck
will never be uniformly mixed.

%Aldous and Diaconis (\cite{AldDia86}) showed that the waiting time for this
%strong stationary time to occur for the top-to-random shuffle is about $n\log
%n$.

For the random-to-below shuffle, we can compute the waiting time explicitly:

\begin{theorem}
\label{thm.times.expect-r2b}Let $H_n$ be the $n$-th harmonic number.
The expected number of steps to get
to the strong stationary time for the random-to-below shuffle is
\[
\mathbb{E}(\tau) = \sum_{i=2}^{n}\frac{n}{i\left(  H_{n}-H_{i-1}\right)  }
\leq n\log n+n\log\left(  \log n\right)  + n\log 2 +1
\qquad \text{if } n \geq 2.
\]
\end{theorem}

We conjecture that the strong stationary time for the random-to-below
shuffle satisfies $\mathbb{E}(\tau) = n\left(\log n+\log\left(  \log n\right) + 
O(1)\right)$, which makes the random-to-below shuffle slower than
top-to-random, for which the strong stationary time approaches $n \log n$ 
(\cite{AldDia86}).
% We
% attribute the fact that random-to-below is slower to its greater
% \textit{laziness}, in other words, to the fact that the probability of
% applying the identity permutation is higher for random-to-below than for top-to-random.

\section{\label{sec.rep}Representation theory}

Recall the maps $L\left(  u\right)  $ and $R\left(  u\right)  $ defined in
Subsection \ref{subsec.def.alg} for any $u\in\mathbf{k}\left[  S_{n}\right]
$. Any representation theorist will recognize them as the actions of $u$ on
the left and the right regular representation of $S_{n}$. Similar maps can be
defined for any other representation of $S_{n}$. It thus is natural to ask
about analogues of Theorems \ref{thm.evals.1} and \ref{thm.evals.2} for
arbitrary representations. We shall briefly summarize the answer (yet unpublished).

In this section, we assume that $\mathbf{k}$ is a field of characteristic $0$.
We shall use some basic notions from the representation theory of $S_{n}$ and
from symmetric functions; the reader can find all prerequisites in
\cite[Chapters 6 and 7]{Fulton97}. For any partition $\lambda$ of $n$, a
Specht module $S^{\lambda}$ is defined, which is an irreducible representation
of $S_{n}$ with a basis indexed by standard tableaux of shape $\lambda$. Each
$u\in\mathbf{k}\left[  S_{n}\right]  $ acts (on the left) on this Specht
module $S^{\lambda}$; we let $L_{\lambda}\left(  u\right)  $ denote this
action (viewed as a $\mathbf{k}$-module endomorphism of $S^{\lambda}$).

We let $\mathcal{R}$ denote the representation ring of the symmetric groups
(called $R$ in \cite[\S 7.3]{Fulton97}), and $\Lambda$ denote the ring of
symmetric functions over $\mathbb{Z}$ (defined in \cite[\S 6.2]{Fulton97}). An
isomorphism $\varphi:\Lambda\rightarrow\mathcal{R}$ (often called the
\emph{Frobenius characteristic map}) is defined in \cite[\S 7.3]{Fulton97},
and the famous \emph{Schur function} $s_{\lambda}\in\Lambda$ corresponding to
a partition $\lambda$ is the preimage of the Specht module $S^{\lambda}$ under
this isomorphism $\varphi$.

For each $m\in\mathbb{N}$, we let $h_{m}\in\Lambda$ denote the $m$-th complete
homogeneous symmetric polynomial. For each $m>0$, we let $z_{m}\in\Lambda$
denote the Schur function $s_{\left(  m-1,1\right)  }=h_{m-1}h_{1}-h_{m}%
\in\Lambda$. (This is $0$ for $m=1$.)

For each subset $I$ of $\left[  n\right]  $, we define a symmetric function
$z_{I}:=h_{i_{1}-1}\prod_{j=2}^{k}z_{i_{j}-i_{j-1}}\in\Lambda$, 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\}  $). When this symmetric function $z_{I}$ is expanded
in the basis $\left(  s_{\lambda}\right)  _{\lambda\text{ is a partition}}$ of
$\Lambda$, the coefficient of a given Schur function $s_{\lambda}$ shall be
called $c_{\lambda}^{I}$. This coefficient $c_{\lambda}^{I}$ is actually a
Littlewood--Richardson coefficient (since $z_{I}$ is a skew Schur function),
hence $\in\mathbb{N}$.

We now claim the following:

\begin{theorem}
\label{thm.specht.eigs}Let $\nu$ be a partition. Let $\lambda_{1},\lambda
_{2},\ldots,\lambda_{n}\in\mathbf{k}$. Then, the eigenvalues of the operator
$L_{\nu}\left(  \lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}%
t_{n}\right)  $ on the Specht module $S^{\nu}$ 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
satisfying }c_{\nu}^{I}\neq0,
\]
and their respective multiplicities are the $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 $L_{\nu}\left(  \lambda_{1}%
t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}\right)  $ is diagonalizable.
\end{theorem}

\begin{verlong}
[Proof idea.] Let $\mathcal{T}$ be the $\mathbf{k}$-subalgebra of
$\mathbf{k}\left[  S_{n}\right]  $ generated by $t_{1},t_{2},\ldots,t_{n}$.
Then, each $F_{i}$ is a $\left(  \mathbf{k}\left[  S_{n}\right]
,\mathcal{T}\right)  $-bimodule (since it is a left ideal of $\mathbf{k}%
\left[  S_{n}\right]  $ and preserved under the action of each $R\left(
t_{\ell}\right)  $).

A right $\mathcal{T}$-module will be called \emph{diagonal} if each $t_{\ell}$
acts on it by a scalar (i.e., a scalar multiple of the identity). Thus, the
quotients $F_{i}/F_{i-1}$ are diagonal right $\mathcal{T}$-modules (by Theorem
\ref{thm.fibfil.tl}).

On the other hand, the Specht module $S^{\nu}$ is a left $\mathbf{k}\left[
S_{n}\right]  $-module, so that its dual $S^{\nu\ast}:=\operatorname*{Hom}%
\nolimits_{\mathbf{k}}\left(  S^{\nu},\mathbf{k}\right)  $ is a right
$\mathbf{k}\left[  S_{n}\right]  $-module (with the action given by $\left(
fw\right)  \left(  m\right)  =f\left(  wm\right)  $ for all $f\in S^{\nu\ast}$
and $w\in S_{n}$ and $m\in S^{\nu}$). Thus, for any left $\mathbf{k}\left[
S_{n}\right]  $-module $N$, the homspace $\operatorname*{Hom}%
\nolimits_{\mathbf{k}\left[  S_{n}\right]  }\left(  S^{\nu},N\right)  $ is
well-defined. This results in a functor%
\begin{align*}
\left.  _{\mathbf{k}\left[  S_{n}\right]  }\operatorname*{Mod}\right.    &
\rightarrow\left.  _{\mathbf{k}}\operatorname*{Mod}\right.  ,\\
N  & \mapsto\operatorname*{Hom}\nolimits_{\mathbf{k}\left[  S_{n}\right]
}\left(  S^{\nu},N\right)  .
\end{align*}
This functor is furthermore exact, since the $\mathbf{k}\left[  S_{n}\right]
$-module $N$ is projective (because $\mathbf{k}\left[  S_{n}\right]  $ is
semisimple). We denote this functor by $\mathbf{h}$.

Now, for each $i\in\left[  0,f_{n+1}\right]  $, set $G_{i}%
:=\operatorname*{Hom}\nolimits_{\mathbf{k}\left[  S_{n}\right]  }\left(
S^{\nu},F_{i}\right)  $; this is the image of $F_{i}$ under the functor
$\mathbf{h}$. Since $\mathbf{h}$ is exact, we thus obtain a filtration
$0=G_{0}\subseteq G_{1}\subseteq\cdots\subseteq G_{f_{n+1}}$ of $G_{f_{n+1}}$
(since exact functors preserve filtrations). But each $G_{i}$ is also a right
$\mathcal{T}$-module (since  $F_{i}$ is a $\left(  \mathbf{k}\left[
S_{n}\right]  ,\mathcal{T}\right)  $-bimodule), and the quotients
$G_{i}/G_{i-1}$ are diagonal $\mathcal{T}$-modules (this is easy to see from
the diagonality of the $F_{i}/F_{i-1}$). Finally,%
\[
G_{f_{n+1}}=\operatorname*{Hom}\nolimits_{\mathbf{k}\left[  S_{n}\right]
}\left(  S^{\nu},F_{f_{n+1}}\right)  =\operatorname*{Hom}\nolimits_{\mathbf{k}%
\left[  S_{n}\right]  }\left(  S^{\nu},\mathbf{k}\left[  S_{n}\right]
\right)  .
\]
Thus, we have found a filtration $0=G_{0}\subseteq G_{1}\subseteq
\cdots\subseteq G_{f_{n+1}}$ of $\operatorname*{Hom}\nolimits_{\mathbf{k}%
\left[  S_{n}\right]  }\left(  S^{\nu},\mathbf{k}\left[  S_{n}\right]
\right)  $ by diagonal $\mathcal{T}$-modules. Hence, to understand the
eigenvalues (with algebraic multiplicities) of the right action of
$\lambda_{1}t_{1}+\lambda_{2}t_{2}+\cdots+\lambda_{n}t_{n}$ on the right
$\mathcal{T}$-module $\operatorname*{Hom}\nolimits_{\mathbf{k}\left[
S_{n}\right]  }\left(  S^{\nu},\mathbf{k}\left[  S_{n}\right]  \right)  $
boils down to understanding the dimensions of $G_{i}/G_{i-1}$.

But the right action of the element $\lambda_{1}t_{1}+\lambda_{2}t_{2}%
+\cdots+\lambda_{n}t_{n}$ on the right $\mathcal{T}$-module
$\operatorname*{Hom}\nolimits_{\mathbf{k}\left[  S_{n}\right]  }\left(
S^{\nu},\mathbf{k}\left[  S_{n}\right]  \right)  $ is the same as the left
action of its antipode $\lambda_{1}t_{1}^{\prime}+\lambda_{2}t_{2}^{\prime
}+\cdots+\lambda_{n}t_{n}^{\prime}$ on the left $\mathbf{k}\left[
S_{n}\right]  $-module $S^{\nu}$, since $S^{\nu}$ is a self-dual left
$\mathbf{k}\left[  S_{n}\right]  $-module (being the image of the Young
idempotent). (TODO: This needs to be checked and written up better.)

TODO: Old stuff.

Consider the $\mathbf{k}$-algebra homomorphism $L_{\nu}:\mathbf{k}\left[
S_{n}\right]  \rightarrow\operatorname*{End}\left(  S^{\nu}\right)  $ sending
each $u$ to $L_{\nu}\left(  u\right)  $. This $L_{\nu}$ is surjective (by the
Jacobson density theorem), and thus the filtration $0=F_{0}\subseteq
F_{1}\subseteq F_{2}\subseteq\cdots\subseteq F_{f_{n+1}}=\mathbf{k}\left[
S_{n}\right]  $ of $\mathbf{k}\left[  S_{n}\right]  $ by left ideals gives
rise to a filtration $0=L_{\nu}\left(  F_{0}\right)  \subseteq L_{\nu}\left(
F_{1}\right)  \subseteq L_{\nu}\left(  F_{2}\right)  \subseteq\cdots\subseteq
L_{\nu}\left(  F_{f_{n+1}}\right)  =\operatorname*{End}\left(  S^{\nu}\right)
$ of $\operatorname*{End}\left(  S^{\nu}\right)  $ by left ideals. The generic
multiplicity of the eigenvalue $\lambda_{1}m_{I,1}+\lambda_{2}m_{I,2}%
+\cdots+\lambda_{n}m_{I,n}$ of $L_{\nu}\left(  \lambda_{1}t_{1}+\lambda
_{2}t_{2}+\cdots+\lambda_{n}t_{n}\right)  $ is therefore the dimension of the
quotient $L_{\nu}\left(  F_{i}\right)  /L_{\nu}\left(  F_{i-1}\right)  $,
where $I=Q_{i}$ (TODO: this is not quite correct, and we need both right and
left actions here, and we need to divide by $\dim\left(  S^{\nu}\right)  $).
But the latter dimension equals the multiplicity $\left[  F_{i}/F_{i-1}%
:S^{\nu}\right]  $ (recalling that $F_{i}/F_{i-1}$ is a representation of
$S_{n}$, since $F_{i}$ and $F_{i-1}$ are left ideals of $\mathbf{k}\left[
S_{n}\right]  $), since it is easy to see that any left ideal $J$ of
$\mathbf{k}\left[  S_{n}\right]  $ satisfies $\dim_{\mathbf{k}}\left(  L_{\nu
}\left(  J\right)  \right)  =\left[  J:S^{\nu}\right]  \cdot\dim\left(
S^{\nu}\right)  $. It remains to prove that $\left[  F_{i}/F_{i-1}:S^{\nu
}\right]  =c_{\nu}^{I}$. For this purpose, we consider the skew diagram
$\omega/\alpha$ whose Frobenius characteristic is $z_{I}$, and show that
$F_{i}/F_{i-1}$ is isomorphic to its Specht module $S^{\omega/\alpha}$ as a
representation of $S_{n}$. (This relies on a notion of Specht modules
corresponding to skew diagrams; but this is defined analogously to Specht
modules for single partitions.)
\end{verlong}

Relatedly, (the isomorphism class of) the representation $F_{i}/F_{i-1}$ of
$S_{n}$ is $\varphi\left(  z_{Q_i}\right)$.

\section{\label{sec.hecke}Into the Hecke algebra}

Like many objects originating in combinatorics, the symmetric group algebra
$\mathbf{k}\left[  S_{n}\right]  $ has a $q$-deformation. This deformation is
the \emph{type-A Hecke algebra} (or\emph{ Iwahori-Hecke algebra}), defined in
terms of a parameter $q\in\mathbf{k}$. It is commonly denoted by
$\mathcal{H}=\mathcal{H}_{q}\left(  S_{n}\right)  $; it has a basis $\left(
T_{w}\right)  _{w\in S_{n}}$ indexed by the permutations $w\in S_{n}$, but a
more intricate multiplication than $\mathbf{k}\left[  S_{n}\right]  $. We
refer to \cite{Mathas99} for the definition of this multiplication, and much
more about $\mathcal{H}$. We can now define the $q$\emph{-deformed
somewhere-to-below shuffles} $t_{1}^{\mathcal{H}},t_{2}^{\mathcal{H}}%
,\ldots,t_{n}^{\mathcal{H}}$ by%
\[
t_{\ell}^{\mathcal{H}}:=T_{\operatorname*{cyc}\nolimits_{\ell}}%
+T_{\operatorname*{cyc}\nolimits_{\ell,\ell+1}}+T_{\operatorname*{cyc}%
\nolimits_{\ell,\ell+1,\ell+2}}+\cdots+T_{\operatorname*{cyc}\nolimits_{\ell
,\ell+1,\ldots,n}}\in\mathcal{H}.
\]
Surprisingly, these $q$-deformed shuffles appear to share many properties of
the original $t_{1},t_{2},\ldots,t_{n}$. In particular, the analogues of
Theorems \ref{thm.ddb} and \ref{thm.nilp.m} in $\mathcal{H}$ (where the
$t_{\ell}$ are replaced by the $t_{\ell}^{\mathcal{H}}$) seem to hold. Even
more surprisingly perhaps, the dimensions of $\mathbb{Q}\left[  t_{1}%
,t_{2},\ldots,t_{n}\right]  $ tabulated in (\ref{eq.dimQt}) (at least for
$n\leq6$) appear to be the same for the $\mathcal{H}$-analogue, which suggests
that all algebraic relations between the $t_{1},t_{2},\ldots,t_{n}$ are
\textquotedblleft coming from\textquotedblright\ the Hecke algebra. Attempts
to prove these conjectures are underway.

\acknowledgements{We thank Eran Assaf, Sarah Brauner, Colin Defant, Persi
Diaconis, Theo Douvropoulos, Maxim Kontsevich, Martin Lorenz, Oliver
Matheau-Raven, Amy Pang, Karol Penson, Victor Reiner and Franco Saliola for
inspiring discussions and insightful comments.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}