\documentclass{article}
\usepackage[margin=1.2in]{geometry}
\usepackage{parskip}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{hyperref}

\title{Faster Inner Products in Character Spaces}
\author{Kaashif Hymabaccus, Robert Moore}

\newtheorem{prop}{Proposition}

\begin{document}

\maketitle

\begin{abstract}
  A common problem in the representation theory of finite groups is to
  examine the structure of a representation by computing characters
  and performing inner products. By writing an open source Rust
  library to perform these inner products, we demonstrate how the
  implementation of cyclotomic field arithmetic can be adapted to this
  use case to yield speed improvements over current computer algebra
  systems.
\end{abstract}

\section{Background}

Let $G$ be a finite group and $\rho : G \to \text{GL}(\mathbb{C})$ be a
representation of $G$. Let $n$ be the exponent of $G$. Due to a
theorem by Brauer \cite{Brauer1945}, any such $\rho$ can be realised
over a cyclotomic field $K = \mathbb{Q}(\zeta_n)$ where $\zeta_n$ is
an $n$th primitive root of unity. We will now consider all
representations of $G$ to be realised over $K$.

Let $\chi_\rho : G \to K$ be the character of $\rho$,
$\rho_1, \ldots, \rho_N$ the irreducible representations of $G$ over
$K$, and $\chi_1, \ldots, \chi_N$ the corresponding irreducible
characters. These characters can be computed by, for example, the
Dixon-Schneider \cite{Schneider1990} or Baum-Clausen \cite{Baum1994}
algorithms. Both of these algorithms are implemented in the GAP
computer algebra system \cite{Gap2020}, which was used to generate
most of our examples and benchmarks.

Given that $\chi_\rho$ and the $\chi_i$ have already been computed,
our problem is to compute the inner product:

$$\langle \chi_\rho, \chi_i \rangle = \frac{1}{|G|} \sum_{g \in G} \chi_\rho(g) \overline{\chi_i(g)}$$

From basic results in character theory, this will give the
multiplicity of the representation $\rho_i$ in the direct sum
decomposition of $\rho$ into irreducibles.

\section{Optimisations}

TODO: rephrase most of this, but it's right.

The key optimisation is in the data structures used to represent
elements $z \in K$. There are two broad approaches: a dense approach,
representing $z$ as a $\mathbb{Q}$-vector in the
$\varphi(n)$-dimensional $\mathbb{Q}$-vector space $K$; and a sparse
approach, where only the nonzero elements of this vector are stored.

A problem that's not entirely obvious is that we have to make a choice
of basis for $K$. The obvious choice is $\{ \zeta_n^i : 0 \leq i \leq
\varphi(n)-1 \}$, but multiplying vectors in this space would require
explicitly operating modulo the cyclotomic polynomial $\Phi_n(x)$. We
have implemented and benchmarked this approach to show that the
running time grows very quickly.

GAP takes the approach of defining a basis and canonicalising into
that basis after each multiplication. This turns out to be unnecessary
in our case, since we know that the final result
$\langle \chi_\rho, \chi_i \rangle$ will not only be rational, but a
nonnegative integer.

This means we can just operate modulo $x^n-1$ (easy, just mod all
powers by $n$) and at the end just take the first nonzero integer
coefficient we see as our result.

\section{Benchmarks}

TODO: rephrase all of this

GAP computes the irreducible characters and passes them to our
program. These times are for the computation of the inner products
given the characters and class sizes.

TODO: graphs showing our library is fast vs Antic and GAP

We can pick a really pathological examples with really huge orders
e.g. cyclic groups or extraspecial groups. The only problem is that
GAP is really slow computing extraspecial characters. Maybe we could
speed that up but that would require implementing a LOT of stuff.

\section{Conclusions and Future Work}

Here's the source code:
\url{https://github.com/CyclotomicFields/cyclotomic}. In the future we
could extend this code to interface with GAP more directly and
perform more advanced computations. Or SageMath, which used to have
their own handwritten cyclotomic field implementation.

Also there is this great paper with some sick algorithms by Hymabaccus
et al \cite{Hymabaccus2020}, we could speed those up.

\bibliographystyle{unsrt}
\bibliography{paper}

\end{document}