%% 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[final]{FPSAC2022}
%% 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}

% quick blackboard bold
\newcommand{\n}{\mathbb{N}}
\newcommand{\z}{\mathbb{Z}}
\newcommand{\q}{\mathbb{Q}}
\renewcommand{\r}{\mathbb{R}}
\renewcommand{\c}{\mathbb{C}}
\newcommand{\f}{\mathbb{F}}

% quick greek letters
\renewcommand{\a}{\alpha}
\renewcommand{\b}{\beta}
\newcommand{\g}{\gamma}
\renewcommand{\d}{\delta}
\newcommand{\e}{\varepsilon}
\renewcommand{\l}{\lambda}
\newcommand{\m}{\mu}

% quick linear algebra
\newcommand{\<}{\left\langle}
\renewcommand{\>}{\right\rangle}
\newcommand{\pmat}[4]{ \ds\begin{bmatrix} {#1}&{#2}\\{#3}&{#4} \end{bmatrix} }
\newcommand{\smat}[9]{ \ds\begin{bmatrix} {#1}&{#2}&{#3} \\ {#4}&{#5}&{#6} \\ {#7}&{#8}&{#9} \end{bmatrix} }
\newcommand{\pvec}[2]{ \ds\begin{bmatrix} {#1}\\{#2} \end{bmatrix} }
\newcommand{\svec}[3]{ \ds\begin{bmatrix} {#1}\\{#2}\\{#3} \end{bmatrix} }
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Mat}{Mat}
\DeclareMathOperator{\diag}{diag}
\DeclareMathOperator{\linspan}{span}

% quick algebra
\newcommand{\is}{\cong}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\mult}{mult}

% formatting conveniences and general laziness
\newcommand{\ds}{\displaystyle}
\newcommand{\ts}{\textstyle}
\newcommand{\minus}{\smallsetminus}
\renewcommand{\ss}{\subseteq}
\newcommand{\defn}[1]{\textbf{{#1}}}
\DeclareMathOperator{\Park}{Park}

% weyl group nonsense
\DeclareMathOperator{\A}{A}
\DeclareMathOperator{\B}{B}
\DeclareMathOperator{\C}{C}
\DeclareMathOperator{\D}{D}
\DeclareMathOperator{\E}{E}
\DeclareMathOperator{\F}{F}
\DeclareMathOperator{\G}{G}

% amsthm stuff
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\theoremstyle{remark}
\newtheorem{example}{Example}
\theoremstyle{plain}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{conjecture}{Conjecture}
\newtheorem{question}{Question}

\usepackage{cleveref}
% TODO: UNCLEAR IF YOU'RE GOING TO NEED THIS
%\crefformat{definition}{Definition~#2#1#3}
%\crefformat{example}{Example~#2#1#3}
%\crefformat{lemma}{Lemma~#2#1#3}
%\crefformat{proposition}{Proposition~#2#1#3}
%\crefformat{theorem}{Theorem~#2#1#3}
%\crefformat{corollary}{Corollary~#2#1#3}
%\crefformat{conjecture}{Conjecture~#2#1#3}
%\crefformat{question}{Question~#2#1#3}

\usepackage{lipsum}

%% define your title in the usual way
\title{Cyclic Actions in Parking Spaces}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[E.~N.~Stucky]{Eric Nathan Stucky\thanks{\href{mailto:enstucky@gmail.com}{enstucky@gmail.com}. Partially supported by NSF grant DMS-1601961 and Czech Science Foundation GACR, grant 21-00420M.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Charles University, Faculty of Mathematics and Physics, Department of Algebra, Sokolovsk\'a 83, 18600 Praha 8, Czech Republic}

%% 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 describe a cyclic action of order $q-1$ on the classical space of generalized parking functions for Weyl groups $W$ when $q$ is prime, as well as a similar action when $q$ is a power of a prime on an isomorphic ``semi-classical'' parking space. We show that these actions agree with the action described by Armstrong, Reiner, and Rhoades in their parking conjectures. Along the way, we also conjecture minimal rings in which Weyl group elements have a parametrized Smith normal form.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Coxeter--Catalan, cyclic action, parking space, root lattice, Smith form}

%% 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, ie. [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{enstucky-119.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}
\label{sec-intro}

Classically, a \defn{parking function} is a sequence $(a_1,\dots, a_n)$ of integers $1\leq a_i\leq n$ such that $(a'_1,\dots, a'_n)$ is the same sequence in increasing order, then $a'_i\leq i$. They were first enumerated by Konheim and Weiss~\cite{KonWei}. Shortly after their introduction, Pollack (via Riordan~\cite{Rio}) gave a different but particularly elegant proof of their enumeration. This proofs shows that the natural inclusion of parking functions into $(\z/(n+1)\z)^n$ becomes an $S_n$-equivariant bijection after passing to the quotient by the all-ones vector, that is, $(\z/(n+1)\z)^n/\!\<(1,\dots,1)\>$.

This quotient from Pollak's argument is isomorphic to $Q/(n+1)Q$ for the root lattice $Q$ of type $A_{n-1}$, and so it is sensible to consider the ``finite torus'' $Q/bQ$ for any root systems $\Phi$ and integer $b$. When $W=S_n$ and $b$ is coprime to $n$, the natural analogue of Pollack's bijection converts these objects into the so-called ``rational-parking functions'' of Armstrong, Loehr, and Warrington~\cite{ArmLoeWar}. In this extended abstract we will primarily be concerned with the action of $W$ on this set: because the Weyl group $W$ preserves the root lattice $Q$, we know that $\c[Q/bQ]$ is a permutation representation of $W$.


\subsection{Semi-classical Parking Spaces}
\label{sec-semiparking}

Sommers \cite[Proposition 3.9]{Som} defines and integer $b$ to be \defn{very good} for a Weyl group $W$ if it satisfies certain coprimality conditions (defined uniformly), which for irreducible $W$ are equivalent to:
\begin{itemize}
\item $b$ is coprime to the Coxeter number $h$, if $W$ has type $\A,\E,\F,$ or $\G$; or
\item $b$ is odd, if $W$ has type $\B$ (or $\C$) or $\D$.
\end{itemize}

He also showed that in this case, the character of $\c[Q/bQ]$ has a simple formula: $\chi^{\c[Q/bQ]}(w)=b^{\dim_\c\ker(1-w)}$. Our first main result shows the coprimality conditions on $b$ appear to be more important, in some sense, than how it is used in the construction:

\begin{theorem}
\label{thm-weyl}
Let $Q$ be a root lattice for an irreducible Weyl group $W$, $b$ be an integer very good for $W$, and $A$ be any finite abelian group of order $b$. Then $\c[Q\otimes A]$, as a $W$-representation, is independent of the choice $A$. Concretely,
$$\chi^{\mathbb{C}[Q\otimes A]}(w)=b^{\dim_\c\ker(1-w)}. $$
\end{theorem}

The character formula is equivalent to the independence statement because $Q\otimes (\z/b\z)\is Q/bQ$, and hence this theorem generalizes Sommers'. In light of it, we will call any $\c[Q\otimes A]$, for an abelian group $A$ of order $b$, a \defn{semi-classical parking space} with parameter $b$. Although all such constructions are isomorphic as $W$-representations, there are advantages to choosing particular $A$ in certain circumstances, as we will see below.


\subsection{Graded Parking Spaces}
\label{sec-gradedparking}

The isomorphism class of the classical parking space makes appearances in other constructions as well. Perhaps the first of these is that Haiman \cite[Proposition 2.5.3]{Hai} proved the existence of a graded $S_n$-representation with graded character
$$ \chi_b(w;t) = \frac{\det(1-t^bw)}{\det(1-tw)}$$
if and only if $b$ is coprime to $n$. Note that $n$ is the Coxeter number of $S_n$ and hence this means that $b$ is very good for $S_n$. Such a representation is a graded version of the classical parking space in the sense that $\chi_b(w;1)=b^{\dim_\c\ker(1-w)}$.

Since then, many other constructions have been noted. The $b=h+1$ setting has a very extensive history, but we briefly mention Postnikov's work \cite[Remark 2]{Rei} on nonnesting parking functions, as well as the paper of Armstrong, Reiner, and Rhoades~\cite{ArmReiRho} defining the noncrossing and ``algebraic'' parking spaces. In very good generality, developments came largely from the theory of rational Cherednik algebras, \textit{e.g.}\ Gordon~\cite{Gor} and Berest, Etingof, and Ginzburg~\cite{BerEtiGin}.

Finally, in a yet-unpublished paper~\cite{ItoOka}, Ito and Okada prove a remarkable classification theorem that unifies these observations. They begin with the following definitions:

\begin{definition}
Let $W$ be a complex reflection group. A \defn{graded parking space} for $W$ with \defn{parameter} $b$ is a graded representation with graded character
$$\chi_b(w;t) = \frac{\det(1-t^b w)}{\det(1-tw)}. $$
Similarly, the \defn{parking space} for $W$ with parameter $b$ is a representation with character $\chi_b(w;1)$; that is, $w\mapsto b^{\dim_\c \ker(1-w)}$.
\end{definition}

The (graded) parking space is clearly unique for each $W$ and $b$ when it exists, in the sense that (graded) representations are determined by their (graded) characters. Existence, however, is nontrivial; the $\chi_b$ in the definition of a graded parking space is always a class function, but not always the character of an actual representation. The content of the aforementioned paper by Ito and Okada is to give a complete classification of those $b$ which are parameters for (graded) parking spaces, for all complex reflection groups. Their description is type-dependent, but coincides with Sommers' for Weyl groups:

\begin{theorem}[Ito--Okada~\cite{ItoOka}]
\label{thm-hsop}
If $W$ is an irreducible Weyl group, then a (graded) parking space with parameter $b$ exists if and only if $b$ is very good for $W$.
\end{theorem}

Unfortunately, Ito and Okada's proof does not provide any hints as to a natural construction: they proceed by explicitly expanding $\chi_b$ as a weighted sum of characters of irreducible representations, and check whether the coefficients in the sum are positive integers. However, there does exist a framework for finding parking spaces ``in the wild,'' essentially proposed by Haiman, with proof completed by Rouquier~\cite{Rou}:

\begin{theorem}
\label{thm-verygood}
Let $W$ be an irreducible complex reflection group with irreducible reflection representation $V$, and let $\mathbf{x}=(x_1,\dots, x_r)$ be a basis for $V^*$. For every very good integer $b$, there exist elements $\theta_1,\dotsc, \theta_r\in S^b V^*$ (that is, polynomials in $\c[\mathbf{x}]$ of degree $b$) such that 
\begin{itemize}
\item $(\theta_1,\dots, \theta_r)$ is a \defn{homogeneous sequence of parameters} for $SV^*$; that is, the quotient $SV^*/\!\<\theta_1,\dots,\theta_r\>$ is finite-dimensional, and
\item the linear map $\theta_\bullet: V^*\to S^b V^*$ defined by $x_i\mapsto\theta_i$, is \defn{$W$-equivariant}; that is to say, $w\cdot \theta_i = \theta_\bullet(w\cdot x_i)$.
\end{itemize}
Moreover, the quotient $\Park_b(W) := SV^*/\!\<\theta_1,\dots,\theta_r\>$ is a graded parking space.
\end{theorem}

Although this is a rather involved definition, it is worth noting that in some cases the relevant homogeneous sequence of parameters can be quite simple.

\begin{example}
Recall that the Weyl group of type $\B_r$ acts on $\c^r$ (and $(\c^r)^*$) by signed permutation matrices, and hence it acts on $\c[\mathbf{x}]$ by accordingly permuting coordinates and swapping signs. Now let $b$ be an odd integer, and write $\theta_i=x_i^b$ for all $1\leq i\leq r$. On one hand $\c[\mathbf{x}]/\!\<\theta_1,\dots,\theta_r\>$ is evidently an $r^b$-dimensional vector space. On the other, if $w$ sends $x_i$ to $\pm x_{j}$ then 
$ w\cdot(\theta_i) = w(x_i^b) = (\pm x_j)^b = \pm x_j^b$,
which is indeed $\theta_\bullet(w\cdot x_i)$. Notice the last equality requires $b$ to be odd.
\end{example}


\subsection{Cyclic Actions}
\label{sec-cyclic}

We prescribe an action of the cyclic group $C$ (with generator $c$) of order $b-1$ on $\Park_b(W)$ in a manner following Armstrong, Reiner, and Rhoades~\cite{ArmReiRho}. Let $\zeta$ be a primitive $(b-1)^\text{th}$ root of unity, and let $C$ act by $c^d \colon \mathbf{x}^\mathbf{a} \mapsto \zeta^{|\mathbf{a}|d} \mathbf{x}^\mathbf{a}$. In particular, this is a scalar multiplication on each graded component, and so clearly it commutes with the action of $W$.

That paper also describes an equivalent combinatorial action on the noncrossing parking space, but leaves open the problem of finding an appropriate combinatorial action on a different parking space that they call the non\emph{nesting} parking space (see, for instance, their Problem 11.4) which is canonically isomorphic to $\c[Q/bQ]$. Etingof~\cite{EtiRei} conjectured a partial solution: when $b=p$ is prime, the finite torus $Q/b Q$ is in fact a vector space over $\f_p$, and so we may consider the action of $C\is\f_p^\times$ via scalar multiplication in the vector space: $c^d \colon \alpha\mapsto c^d\alpha$.

We may be tempted to extend this to powers of primes, but unfortunately if $q=p^e$ then $Q/q Q$ is not a vector space over $\f_q$. One na\"ive fix is to modify the classical parking space to enforce this vector space structure.

\begin{definition}
Let $W$ be an irreducible Weyl group and $q$ be a prime power $q=p^e$ which is very good for $W$. Then we write $\Park_q^\sim(W) :=Q\otimes \f_q$.
\end{definition}

When $q=p$, this definition agrees with the classical parking space, and in general it has the same $W$-representation structure by \Cref{thm-weyl}. But by swapping the abelian group from $\z/q\z$ to $\f_q$, we now may naturally define an action of the cyclic group $C$ of order $q-1$: match a generator of $C$ to one of $\f_q^\times$ and then perform scalar multiplication on the right tensor factor. After making this adjustment, we find that there is indeed an isomorphism of $(W\times C)$-representations.

\begin{theorem}
\label{thm-cyclic}
Let $W$ be an irreducible Weyl group, $q$ be a primal power $q=p^e$ which is very good for $W$, and $C$ be the cyclic group of order $q-1$. Then as $(W\times C)$-representations,
$$\Park_q(W)\is \Park_q^\sim(W).$$
\end{theorem}

We prove both \Cref{thm-weyl} and \Cref{thm-cyclic} by an explicit type-dependent character computation. The proofs are rather similar, and will be treated together whenever possible; it seems to us that there should be some common generalization.


\section{Linear-Algebraic Reductions}
\label{sec-lemmas}

Let $A$ be a finite abelian group of order $b$ and suppose that $Z=\<z\>$ is a cyclic group acting $\z$-linearly on $A$. Observe that the actions of $W$ and $Z$ commute on $Q\otimes A$, because they act on the left and right tensor factors, respectively. Thus $\c[Q\otimes A]$ is a permutation $(W\times Z)$-representation; we denote its character by $\widetilde\chi_A$. 

Since it is a permutation representation, the character simply counts fixpoints, which we write as
$$ \widetilde\chi(w z^d) = \vert\{\a\in Q\otimes A: w\a= z^{-d}\a\}\vert. $$
These fixpoints form a subgroup of $Q\otimes A$, written explicitly as $\ker_{Q\otimes A}(z^{-d}-w)$. We would like these subgroups to have their orders be ``appropriate'' powers of $b$. More precisely if we may embed $Z\leq C$ with $z=c^k$ for some $k$ (that is, if $k|Z| \equiv 0 \bmod b-1$), then we may consider both $\Park_b(W)$ and $\c[Q\otimes A]$ as $(W\times Z)$-representations, and we see that they are isomorphic if and only if
$$ \vert\ker_{Q\otimes A}(z^d-w)\vert = b^{\dim_\c \ker(\zeta^d-w)} $$
for all integers $d$ and all $w\in W$. By this line of reasoning, we reduce the main theorems to the following lemmata.

On one hand, for any $A$ we may take $Z$ to be the trivial group. The following is then a slight algebraic strengthening of \Cref{thm-weyl}:

\begin{lemma}
\label{lem-weyl}
Let $Q$ be a root lattice for an irreducible Weyl group $W$, and $b$ be very good for $W$. Then for any abelian group $A$ of order $b$ and any $w\in W$, 
$$ \ker_{Q\otimes A}(1-w) \is A^{\dim_{\c}\ker(1-w)}$$
as abelian groups, where we have written $1$ as shorthand for $\id\otimes\id$, and $w$ for $w\otimes\id$.
\end{lemma}

On the other, let us restrict to $A=\f_q$, where $q=p^e$ is a prime power that is very good for $W$. (In particular, this means that $p$ is also very good for $W$.) In this case there is a natural choice for $Z$, namely $\f_q^\times$. Since $|Z|=b-1$ in this case, we write $Z=C$. 

Let $\zeta^d$ be a primitive $(q-1)^\text{th}$ root of unity. Because the generator $c\in C$ acts on the degree-$d$ polynomials as multiplication by $\zeta^d$, the ungraded $(W\times C)$-character evaluations of $wc^d$ simply substitute $t=\zeta^d$ in $\chi(w;t)$. Thus, if $w$ has eigenvalues $\l_1,\l_2,\dots, \l_r$ then
$$ \chi(wc^d) = \lim_{t\to\zeta^d}\frac{\det(1-t^q w)}{\det(1-tw)} = \prod_{j=1}^r \left(\lim_{t\to\zeta^d} \frac{1-t^q\l_j}{1-t\l_j}\right). $$

Each eigenvalue contributes $1$ to the product except for $\l_j\neq\zeta^{-d}$, which collectively contribute $q^\kappa$. Since $w$ is diagonalizable over $\c$, we have $\kappa = \dim_\c\ker(\zeta^{-d}-w)$.

Finally, $Q\otimes \f_q$ is a vector space over $\f_q$ and $\ker_{Q\otimes \f_q}(c-w)$ is a subspace. Thus it suffices only to say that its dimension is equal to that of $\ker(\zeta^{-d}-w)$, and so \Cref{thm-cyclic} is equivalent to this lemma:

\begin{lemma}
\label{lem-cyclic}
Let $Q$ be a root lattice for an irreducible Weyl group $W$, and suppose that $q=p^e$ is a prime power which is very good for $W$. Then for any $w\in W$ and any integer $d$, we have
$$ \dim_\c\ker(\zeta^{d} - w) = \dim_{\f_q}\ker_{Q\otimes \f_q}(c^{d}-w)$$
where $\zeta$ is a primitive $(q-1)^\text{th}$ root of unity, and $c$ is a generator of $\f_{q}^\times$.
\end{lemma}

Roughly speaking, these lemmata state that the dimensions of the eigenspaces for $w$ over $\c$ agree with the ``dimensions'' for corresponding ``eigenspaces'' over $Q\otimes A$. However, even in the finite field case this is not precisely true, since in general $w$ will not be diagonalizable over $\f_q$ (whereas it is over $\c$). \Cref{lem-cyclic} succeeds despite this fact because it does not detect all $\c$-eigenspaces, only those for the $(q-1)^\text{th}$ roots of unity.


\subsection{A Speculative Generalization}
\label{sec-crgs}

Carlos Arreche suggested the following arithmetic interpretation of \Cref{thm-cyclic}. Rather than ``forcing'' the $\f_q$-vector space structure, it may be found in the following way. Let $\widetilde Q$ be the $\z[\zeta]$-span of the root basis rather than just the $\z$-span; that is, $\widetilde Q = Q\otimes_\z \z[\zeta]$. The extension $\z\ss \z[\zeta]$ is unramified at the prime $p$; that is, $\mathfrak p = p\z[\zeta]$ is a prime ideal. Because of this, $\z[\zeta]/\mathfrak p \is \f_q$ and therefore we may construct $Q\otimes \f_q$ as $\widetilde Q/\mathfrak p \widetilde Q$.

Noticing that $\widetilde Q$ is not a lattice, but instead a ``$\z[\zeta]$-lattice,'' we propose the following extension. Recall that given a number field $\f$ with ring of integers $\mathcal{O}$, an \defn{$\mathcal{O}$-lattice} $L$ is a finitely generated $\mathcal{O}$-submodule of the vector space $\f^r$ for some $r$, such that $L\otimes_\z\f$ is all of $\f^r$. This is an intriguing reformulation because every \emph{complex} reflection group can be defined over a number field (easy to see since there are only finitely many matrix entries in $W$), and the content of \Cref{lem-cyclic} is that we do not gain any eigenvectors when thinking of $w\in \Mat_{r\times r}(\mathcal{O}/\mathfrak p)$.

\begin{question}
Let $\f$ be a number field, $\mathcal{O}$ be its ring of integers, and $W$ be an reflection group defined over $\f$. For which $\mathcal{O}$-lattices $L$ and which prime ideals $\mathfrak p$ do we have, for all integers $d$ and all $w\in W$,
$$\dim_\c\ker(\zeta^{d} - w) = \dim_{\mathcal{O}/\mathfrak p}\ker_{L/\mathfrak p L}(c^{d}-w)?$$
(As usual, $\zeta$ is a primitive $(q-1)^\text{th}$ root of unity, and $c$ is a generator of $(\mathcal{O}/\mathfrak p)^\times \is \f_{q}^\times$.)
\end{question}


\section{Techniques}
\label{sec-facts}

\subsection{Almost-Diagonalizability}
\label{sec-almostdiag}

An essential difficulty in the lemmata is that $w$ is not generally diagonalizable over $\f_q$, even when $q$ is very good for $W$, as the following example displays.

\begin{example}
Let $w$ be the simple transposition $(1\,2)\in S_3$; then $w$ acts on the type $\A$ root lattice $Q=\linspan_\z(e_1-e_2,e_2-e_3)\ss\z^3$ by the matrix
$$\pmat{-1}{1}{0}{1}.$$
Over $\f_{2^e}$, for any $e$, this matrix is a Jordan block and is not diagonalizable. (Note that this does not contradict \Cref{lem-cyclic} since the actual eigenspace for $1=c^0$ over $\f_{2^e}$ is one-dimensional, same as for $1=\zeta^0$ over $\c$.)
\end{example}

Because of this, it is not sufficient to work with the characteristic polynomials of Weyl group elements, we have to work with the eigenspaces of Weyl group elements directly. However, when $W$ is held fixed, this problem disappears for most $q$.

\begin{lemma}
\label{lem-almostdiag}
Let $\f$ be a field and $\pi$ the unique ring map $\z\to\f$. Let $w\in\GL_r(\z)$ be any element of finite order $m$ such that $\pi(m)\in\f^\times$. Then any $\beta\in\f$ has $\dim_\f(\beta-w)$ vanishing unless $\beta$ has finite order $\ell$ dividing $m$, in which case $\dim_\f(\beta-w)$ is the multiplicity of the irreducible cyclotomic polynomial $\Phi_\ell(t)$ as a factor of $\det(t-w)\in\z[t]$.
\end{lemma}

This implies that for all $p$ except possibly the finitely many dividing $m$, Weyl group elements are ``as diagonalizable as possible'' over $\f_q$; that is, their eigenspaces coincide with their generalized eigenspaces. In particular, this reduces the proof of \Cref{lem-cyclic} to a finite check, which we use to handle the exceptional types.

\subsection{RC-Equivalence}
\label{sec-smith}

The main tool used in these proofs is a sort of ``partial'' calculation of the Smith normal form for certain matrices. To be more precise, we introduce the following definition.

\begin{definition}
For any commutative ring $R$ and any matrices $X,Y\in \Mat_{r\times r}(R)$, let us say that $X$ and $Y$ are \defn{RC-equivalent (over $R$)} if there exist matrices $U\in \GL_r(R)$ and $V\in \GL_r(R)$ such that $Y= UXV$.
\end{definition}

The ``RC'' in this definition stands for row/column, as justified by part 1 of the following proposition.

\begin{proposition}
\label{prop-smithfacts}
Let $R$ be a commutative ring and $X,Y\in \Mat_{r\times r}(R)$.
\begin{enumerate}
\item \label{colrowop} If there is a sequence of invertible row and column operations that transform $X$ into $Y$, then $X$ and $Y$ are RC-equivalent over $R$.
\item \label{kernel} For an $R$-module $M$, let $\Mat_{r\times r}(R)$ act on $M^r$ by matrix (left-)multiplication (\textit{i.e.}\ make the identification $M^r \is R^r\otimes_R M$). Then if $X$ and $Y$ are RC-equivalent matrices over $R$, we have $\ker_{M^r}(X) \is \ker_{M^r}(Y)$ as $R$-modules.
\end{enumerate}
\end{proposition}

Recall that when $R$ is a PID, there is a (mostly) canonical choice of representative for RC-equivalence classes:

\begin{theorem}
\label{thm-smith}
Let $X\in\Mat_{r\times r}(R)$ be a matrix with entries in a principal ideal domain $R$. Then $X$ is RC-equivalent to a diagonal matrix $D=\diag(d_1,\dots, d_r)$ such that $d_i|d_{i+1}$ for each $1\leq i<r$. Moreover, the matrix $D$ is unique up to multiplication of each $d_i$ by a unit of $R$.
\end{theorem}

We may consider such forms over any commutative ring $R$. That is, say that a matrix $X\in\Mat_{r\times r}(R)$ \defn{has a Smith normal form (over $R$)} if it is RC-equivalent to a diagonal matrix $D=\diag(d_1,\dots, d_r)$ such that $d_i|d_{i+1}$. In this way, the classical \Cref{thm-smith} says that every matrix over a PID has a Smith normal form. Moreover we say that the matrix equation $X=UDV$, with $D$ as before and $U,V\in \GL_n(R)$, is a \defn{Smith factorization of $X$ (over $R$)}.  Note that Smith factorizations are not unique, even up to units; the uniqueness statement of the theorem only applies to the diagonal part $D$.

\subsection{A Conjecture on Smith Normal Forms}
\label{sec-conj}

It is a small class of matrices $M\in\Mat_{r\times r}(R)$ such that $tI-M$ has a Smith normal form in $R[t]$ (see, \textit{e.g.},~\cite[Proposition 8.9]{MilRei}). In general, Weyl group elements need not be among them. For instance, if $W$ is the Weyl group of type $\B_2$, and $w\in W(B_2)$ is the signed permutation with matrix $\begin{bmatrix} 1&0\\0&-1 \end{bmatrix}$, it is easy to check that $tI-w$ has no Smith normal form over $\z[t]$ by computing cokernels at $t=1$.

On the other hand, they appear to be ``close'' in the following sense. Every $t-w$ has a Smith normal form over $\q[t]$, and so we may blame such failures on ``necessary denominators'' appearing in every Smith factorization. But computer calculations with $r\leq 10$ suggest that there are not so many of these.

\begin{conjecture}
\label{conj-smithweyl}
Let $Q$ be a root lattice for an irreducible Weyl group with Coxeter number $h$. Define
$$ h' = \begin{cases}
1 & \text{ if } W \text{ is of type $\A$}, \\
2 & \text{ if } W \text{ is of type $\B, \C,$ or $\D$}, \\
h & \text{ if } W \text{ is of exceptional type ($\E, \F$, or $\G$)}. \\
 \end{cases} $$
Then $t-w$ has a Smith normal form over $\z[\frac1{g},t]$ if and only if $g$ is divisible by $h'$, in the sense that this is true when $w$ is identified with an integer matrix describing its action on $Q$ in some basis (\textit{e.g.}\ the root basis). 
\end{conjecture}

In particular $t-w$ has a Smith normal form over $\z[\frac1h,t]$ for all exceptional types, and for the classical types, the conjecture holds for $w$ with at most $2$ cycles. However, the conjecture is perhaps somewhat surprising because $h'$ has a natural interpretation for almost all types: the integers coprime to $h'$ are those which are very good for $W$. Mysteriously, though, in type A it seems that we do not have any necessary denominators at all. It is not clear whether this numerical invariant has a more conceptual, type-independent definition.


\section{A Uniform Inequality}
\label{sec-uniform}

Our proofs proceed in a largely case-by-case fashion, computing the characters of the representations, but it is worth noting that the equality in \Cref{lem-cyclic} can be replaced by an inequality in a rather general setting.

\begin{proposition}
\label{prop-inequality}
Let $q=p^e$ be a prime power. For any $r\times r$ matrix $w\in\Mat_{r\times r}(\z)$, any $\a\in\c^\times$ with finite order $\ell$ dividing $q-1$, and any $\b\in\f_q^\times$ also with order $\ell$:
$$ \dim_\c\ker(\a-w) \leq \dim_{\f_q}\ker(\b-\pi(w)), $$
where $\pi$ is the unique ring map $\z\to\f_q$, namely reduction mod $p$.
\end{proposition}

\begin{proof}[Outline of proof]
Since $\zeta$ is a primitive $(q-1)^\text{th}$ root of unity, $\alpha$ is a power of $\zeta$. So we would like to compute a Smith factorization of $\alpha-w$ over $\z[\zeta]$ and then apply $\pi$ to see that the diagonal elements divisible by $p$ vanish.

Executing this plan rigorously requires a number of technicalities the beginning of the proof. The most fundamental problem is that $\z[\zeta]$ need not be a PID, so it is not clear that $\a-w$ should even have a Smith normal form. However, going all the way to $\q(\zeta)$, we lose the ability to apply $\pi$. We can thread this needle by localizing $\z$ away from $p$, but there is one last technical hiccup, which is resolved by completing to the $p$-adic integers $\z_p$.
\end{proof}

As an extended comment, we note that \Cref{prop-inequality} together with the classification of Ito and Okada shows that \Cref{lem-cyclic} in some sense characterizes the primes (or prime powers) which are very good.

\begin{corollary}
\label{cor-iff}
Let $W$ be a Weyl group, $p$ be any prime number, and suppose that $q=p^e$ is a prime power. Then for any $w\in W$ and any integer $d$, we have
$$ \dim_\c\ker(\zeta^{d} - w) \leq \dim_{\f_q}\ker(c^{d}-w)$$
where $\zeta$ is a primitive $(q-1)^\text{th}$ root of unity, and $c$ is a generator of $\f_{q}^\times$. Moreover, equality holds for all $w\in W$ and all integers $d$ if and only if $q$ (equivalently, $p$) is very good for $W$.
\end{corollary}

\begin{proof}[Proof (conditional on \Cref{lem-cyclic})]
The inequality comes directly from \Cref{prop-inequality}. If $q$ is very good for $W$, equality is precisely the statement of \Cref{lem-cyclic}. Conversely, if $q$ is not very good for $W$, then it does not satisfy condition (iii) of Ito and Okada's Theorem 1.4~\cite{ItoOka}, and thus $w\mapsto\left[\frac{\det(1-t^q w)}{\det(1-tw)}\right]_{t=1}$ cannot be the character of a permutation representation of $W$. As argued in \Cref{sec-lemmas}, we have $\chi(w) = q^{\dim_\c\ker(1-w)}$. But $\c[Q\otimes\f_q]$ is manifestly a permutation representation of $W$ for any prime power $q$. Therefore, the inequality is strict for some $w\in W$, since
$q^{\dim_\c\ker(1 - w)} = \chi(w) \neq \chi'(w) =  q^{\dim_{\f_q}\ker(1 - w)}$.
\end{proof}



\section{Proofs of Lemmata}
\label{sec-proofs}

\subsection{Type A}
\label{sec-proofsa}

Recall the root lattice of type $\A_r$ is $Q:=\{(v_0,\dots, v_r)\in\r^{r+1}:\sum_{i=0}^r v_i = 0\}$. The Weyl groups are $W(\A_r)=S_{r+1}$, and so the conjugacy classes of Weyl group elements are determined by the corresponding cycle types. Also, we recall that an integer $b$ is very good for $W(\A_r)=S_{r+1}$ if and only if it is coprime to $h=r+1$. 

\begin{proposition}
\label{prop-typea}
Let $V$ be the irreducible reflection representation of $S_{r+1}$, and let the element $w\in S_{r+1}$ have cycle type $\lambda=(\lambda_1,\dots,\lambda_k)$. Then $tI-w$ is RC-equivalent over $\z[t]$ to the block-diagonal matrix $\diag(I_{r-1-k},\Lambda(t))$ where $\Lambda(t)$ is the $k\times k$ matrix
$$ \Lambda(t) = \begin{bmatrix}
[\lambda_1]_t & [\lambda_2]_t & [\lambda_3]_t & \cdots & [\lambda_k]_t \\
0 & t^{\lambda_2}-1 & 0 & & 0 \\
0 & 0 & t^{\lambda_3}-1 & & 0 \\
\\
0 & 0 & 0 & & t^{\lambda_k}-1
\end{bmatrix}. $$
where $[m]_t=1+t+\cdots+t^{m-1}$.
\end{proposition}

We omit the proof of this proposition, which is a technical computation with row and column operations. However, we use it to prove that both lemmata hold for type $\A$.

\begin{corollary}
\label{cor-typea}
\Cref{lem-weyl} and \Cref{lem-cyclic} both hold for $W=W(\A_r)$.
\end{corollary}

For Lemma \Cref{lem-weyl} we apply \Cref{prop-typea} and evaluate at $t=1$. All entries of $\Lambda(t)$ except those in the first row are zero, and by iterating the Euclidean algorithm we find that $I-w$ is RC-equivalent to $\diag(I_{r-k},\gcd(\l),0,\dots, 0)$, where we write $\gcd(\l)$ as shorthand for $\gcd(\l_1,\dots,\l_k)$. Clearly, $\gcd(\l)$ must divide $h=r+1=\sum\l_i$, and thus any number coprime to $h$ is also coprime to $\gcd(\l)$. 

Therefore, multiplication by $\gcd(\l)$ is an invertible operator on $A$, since the order of $A$ is very good for $W$ (that is, coprime to $h$). We conclude that
$$\ker_{Q\otimes A}(1-w)\is \ker_{A^r}(I-w)\is \ker_{A^r}\diag(I_{r-k},\gcd(\l),0_{k-1}) \is A^{k-1}$$
as abelian groups, with the middle isomorphism following from \Cref{prop-smithfacts}(2). Finally, \Cref{lem-weyl} follows by tensoring instead with $\c$ to find $\dim_\c\ker(1-w)=k-1$ as well.


For \Cref{lem-cyclic}, we first tensor with any field $\f$ to observe that $tI-w$ is RC-equivalent to $\diag(I_{r-1-k},\Lambda(t))$ over $\f[t]$. We now evaluate $t$ at any non-unity element of the field $t_0\neq 1$ (which is dealt with above), so that $t_0-1$ is invertible. Thus by performing the row operations $\textbf{R}_{r-k+1} \mapsto (t_0-1)\textbf{R}_{r-k+1}$ followed by $\textbf{R}_{r-k+1} \mapsto \textbf{R}_{r-k+1} - \textbf{R}_{r-k+i}$ for $2\leq i\leq k$, we conclude that $t_0I-w$ is RC-equivalent to $\diag(t_0^{\l_1}-1,\dots, t_0^{\l_k}-1)$ over $\f$.

We thus see that the $\f$-nullity of $w$ is precisely the number of $\l_i$ such that $t_0^{\l_i}=1$. Thus what remains to be shown is that for any very good prime power $q$ and any integer $d$, the number of $i$ such that $c^{d\l_i}\equiv 1$ in $\f_q$ is equal to the number of $i$ such that $\zeta^{d\l_i}=1$. The condition in either case is equivalent to $d\l_i$ being divisible by $q-1$, and so the eigenspaces have equal dimension, as desired.

\subsection{Other Types}
\label{sec-proofsx}

We omit complete proofs in types $\B_r, \C_r$, and $\D_r$, as the ideas are similar, but we do write down the partial Smith computation. Any Weyl group element $w$ in these types acts on the respective root lattice $Q$ by a signed permutation matrix. Ignoring the signs, the underlying permutation has a cycle type $\lambda=(\lambda_1,\dots, \lambda_k)$ which we call the cycle type of $w$. Putting the signs back, let $\e_i=1$ for cycles with an even number of sign changes, and $\e_i=-1$ otherwise; we call the tuple $(\e_1\lambda_1,\dots, \e_k\lambda_k)$ the \defn{signed cycle type} of $w$.

\begin{proposition}
\label{prop-typex}
Let $V$ be the irreducible reflection representation of $W(X)$ for $X=\B_r,\C_r$, or $\D_r$ and $w\in W(X)$ be a signed permutation matrix with signed cycle type $\lambda=(\e_1\l_1,\dots,\e_k\l_k)$. Then $tI-w$ is RC-equivalent over $\z[t]$ to the diagonal matrix $\diag(I_{r-k}, t^{\l_1}-\e_1,\dots, t^{\l_k}-\e_k)$.
\end{proposition}

We conclude by dealing with the exceptional types. For \Cref{lem-weyl} this is a simple matter. We need to compute fixpoints, and so we evaluate at $tI-w$ at $t=1$ as in type $\A$. We used \textsc{gap3} to compute a Smith factorization $I-w=UDV$ over $\z$, and saw that the nonzero diagonal entries of $D$ are integers whose action on $A$ (by multiplication) is an invertible operator, which completes the proof for the exceptional types.

For \Cref{lem-cyclic} we recall that \Cref{lem-almostdiag} implies that we need to check the equality of eigenspace dimensions for only finitely many $p$. More precisely, for each $w\in W$, we need only check the list of primes that divide its order $m$.

This is still an infinite calculation because there are many finite fields of characteristic $p$, but here again \Cref{lem-almostdiag} is useful. Since we need only check the $\beta$ whose order divides $m$, and there are only $m$ of these $\overline{\f}_p$, it suffices to perform the check at the minimal power $q=p^e$ in which all of them appear; that is, for which $m$ divides $q-1$. Again, a simple \textsc{gap3} script verifies the lemma in these cases, completing the proof for the exceptional types.

\acknowledgements{
This work formed part of the author's Ph.D. thesis from the University of Minnesota-Twin Cities, defended in June 2021. We thank Carlos Arreche for suggesting the arithmetic interpretation of \Cref{thm-cyclic} as discussed in \Cref{sec-crgs}.
}

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