# An algorithm for computing root multiplicities in Kac-Moody algebras

Aidan Backus, Peter Connick, and Joshua Lin

(December 2019)

###### Abstract

Root multiplicities encode information about the structure of Kac-Moody
algebras, and appear in applications as far-reaching as string theory and the
theory of modular functions. We provide an algorithm based on the Peterson
recurrence formula to compute multiplicities, and argue that it is more
efficient than the naive algorithm.

##  1 Introduction

Kac-Moody algebras were introduced in the 1960s by Kac and Moody working
independently as generalizations of finite-dimensional semisimple Lie
algebras. Every Kac-Moody algebra $\mathfrak{g}$ is equipped with a root
system $\Delta$ and a Cartan subalgebra $\mathfrak{h}$, and we have a root
space decomposition

$\mathfrak{g}=\bigoplus_{\alpha}\mathfrak{g}_{\alpha}\oplus\mathfrak{h}\oplus\bigoplus_{\alpha}\mathfrak{g}_{-\alpha}$

where the direct sums are taken over all _positive_ roots $\alpha\in\Delta$.
The dimension of the root space $\mathfrak{g}_{\alpha}$ is called the
_multiplicity_ of $\alpha$. The root multiplicities of $\mathfrak{g}$ encode
important information about the structure of $\mathfrak{g}$. Closed
expressions for the root multiplicities are only known in a few cases, and a
major open problem in the field to give general closed expressions, or at
least estimates, for root multiplicities. A historical overview of
multiplicity theory is given by [2, §1].

In this paper, we discuss an algorithm that implements the Peterson recurrence
formula for the root multiplicities. Naively implemented, the Peterson formula
iterates over the entire root lattice, whose cardinality grows exponentially
in the height of a root; we exploit the semigroup structure of the imaginary
roots and divisibility properties of the real roots to greatly cut down on the
space of roots one must iterate over.

We have implemented our algorithm in Sage, and at the time of writing are
preparing for submission to the Sage Project. Our implementation can also be
downloaded on GitHub. It can compute the root multiplicities of the
exceptional algebra $E_{10}$ up to height $100$ in a matter of minutes. We
compared our computations to the computations for $E_{10}$ and $E_{11}$ given
by Kleinschmidt [5] and for certain hyperbolic Kac-Moody algebras given by Kac
[4, §11.15].

##  2 Preliminaries

Fix a symmetrizable generalized Cartan matrix $A=(a_{ij})_{i,j=1}^{d}$. We
decompose $A=DB$ where $D$ is a diagonal matrix with entries
$\varepsilon_{1},\dots,\varepsilon_{d}$ and $B=(b_{ij})_{ij}$ is symmetric.
Then $A$ determines a unique Kac-Moody algebra $\mathfrak{g}$, equipped with a
Cartan subalgebra $\mathfrak{h}\subseteq\mathfrak{g}$ and an indexed set
$\Delta_{simp}=\\{\alpha_{1},\dots,\alpha_{d}\\}\subset\mathfrak{h}^{*}$ of
simple roots. We will always take $\Delta_{simp}$ as the basis of its span, so
when we take dot products $\cdot$, they are with $\Delta_{simp}$ as an
orthonormal basis.

Let $Q$ denote the root lattice of $\mathfrak{g}$; i.e. the lattice in
$\mathfrak{h}^{*}$ generated by $\Delta_{simp}$.

######  Definition 2.1.

The _multiplicity_ $m(\beta)$ of $\beta\in Q$ is the dimension of the vector
space $\mathfrak{g}_{\beta}$ of $g\in\mathfrak{g}$ such that for every
$h\in\mathfrak{h}$,

$[h,g]=\beta(h)(g).$

If $m(\beta)>0$, we say that $\Delta$ is a _root_ of $\mathfrak{g}$ and write
$\beta\in\Delta$.

If $\beta\in\Delta$, then either all coordinates of $\beta$ are positive (i.e.
$\geq 0$) or they are all negative. The set of positive $\beta$ is called
$\Delta^{+}$. One has $m(\beta)=m(-\beta)$, so for the purposes of computing
root multiplicities, one might as well assume $\beta\in\Delta^{+}$ (and
henceforth we do).

Let $(\cdot,\cdot)$ denote the Killing form of $\mathfrak{g}$, so
$(\beta,\gamma)=\beta\cdot B\gamma$. Recall that the _fundamental reflection_
by $\alpha_{i}\in\Delta_{simp}$ is defined by

$w_{i}(\beta)=\beta-(\beta,\alpha_{i})\alpha_{i},$

and that the fundamental reflections generate the Weyl group $W$. In
particular, $\Delta^{r}$ is the closure of $\Delta_{simp}$ under fundamental
reflections.

We let $\Delta_{f}$ denote the set of all positive imaginary roots
$\beta\in\Delta^{i}$ such that for every $\alpha_{j}\in\Delta_{simp}$,
$(\beta,\alpha_{j})\leq 0$.

For any $\beta\in Q$, we let $|\beta|$ denote the height of $\beta$, i.e. the
sum of the coordinates of $\beta$ with respect to $\Delta_{simp}$. We let
$\rho$ denote the Weyl vector, so $2(\rho,\beta)=|\beta|$.

######  Definition 2.2.

A _divisor_ of $\beta$ is a $\gamma\in Q^{+}$ such that there is a
$n\in\mathbb{N}$ satisfying $n\gamma=\beta$. In this case, we write
$\gamma|\beta$.

With this definition in mind, we define

$c(\beta)=\sum_{\gamma_{p}|\beta}\frac{m(\gamma_{p})}{p}$

where we have $d\gamma_{p}=\beta$. This sum appears in the Peterson recurrence
formula. We let $\gcd\beta$ denote the $\gcd$ of the coordinates of $\beta$
(with respect to $\Delta_{simp}$).

######  Definition 2.3.

Let $\beta\in\Delta_{f}$. If $\gamma\in Q^{+}$ is such that $\beta-\gamma\in
Q^{+}$, then we say that $\gamma$ is a _subroot_ of, or is _under_ , $\beta$,
and write $\gamma\prec\beta$.

It is immediate that $\preceq$ is a partial order, and that if
$\gamma\prec\beta$, then $|\gamma|<|\beta|$.

To compute $c(\beta)$, we use Peterson’s recurrence formula.

######  Theorem 2.4 (Peterson’s recurrence formula).

One has

$c(\beta)=\frac{1}{(\beta,\beta-2\rho)}\sum_{\gamma\prec\beta}(\gamma,\beta-\gamma)c(\gamma)c(\beta-\gamma).$

Peterson’s recurrence formula is proven, for example, in Kac’s book [4].

We will also need the following theorem of convex geometry, proven for example
in Bruns-Gubeladze [1].

######  Theorem 2.5 (Gordan).

Let $\Gamma$ be a rational convex polyhedral cone in $\mathbb{R}^{d}$ with
dual cone

$\Gamma^{*}=\\{y\in\mathbb{R}^{d}:\forall x\in\Gamma~{}y\cdot x\geq 0\\}.$

If $G=(G,+)$ is the semigroup of lattice points in $\Gamma^{*}$, then $G$ is
finitely generated.

##  3 The algorithm

We can use the action of the Weyl group to compute $\Delta^{r}$ from
$\Delta_{simp}$. More specifically, we use the _pingpong algorithm_.

Data: a root $\alpha\in\Delta^{+}$, a maximum height $h$

$\ell:=\text{Stack}(\alpha)$;

while  _$\ell\neq\emptyset$_ do

$\beta:=\text{Pop}(\ell)$;

$P:=\\{w_{1}(\beta),\dots,w_{d}(\beta)\\}$;

$P:=\\{\gamma\in P:|\gamma|\leq h\text{ and }\gamma\geq 0\\}$;

for  _$\gamma\in P\setminus\Delta^{+}$_ do

$\Delta^{+}:=\Delta^{+}\cup\gamma$;

Push$(\ell,\gamma)$;

$m(\gamma):=m(\alpha)$;

$c(\gamma):=c(\alpha)$;

end for

end while

Algorithm 1 The pingpong algorithm.

The pingpong algorithm will add $w\alpha$ to $\Delta^{+}$ for every $w\in W$
such that $|w\alpha|\leq h$, along with recording the values of $m(\gamma)$
and $c(\gamma)$ for $\gamma$ in the orbit, which are preserved by the action
of the Weyl group. Indeed, let $w=w_{i_{1}}\dots w_{i_{k}}$ and assume that
$w^{\flat}=w_{i_{2}}\dots w_{i_{k}}$ is such that $w^{\flat}\alpha$ been added
to $\Delta^{+}$. Then $w\alpha=w_{i_{1}}w^{\flat}\alpha$ and so $w\alpha\in
P$. Therefore the claim follows by induction.

After initializing each of the $m(\alpha_{j})=c(\alpha_{j})=1$, and
pingponging each of the $\alpha_{j}\in\Delta_{simp}$, we have generated all of
$\Delta^{r}$ up to height $h$. We now must generate the imaginary roots
$\Delta^{i}$. Similar to the case of real roots, we simply must choose one
root from each orbit, and to this end we compute the imaginary roots from the
imaginary fundamental chamber, $\Delta_{f}$.

######  Lemma 3.1.

$\Delta_{f}$ is contained in a semigroup which admits a _Hilbert basis_ ; i.e.
a minimal, finite generating set.

###### Proof.

Let $\Gamma\subset\mathfrak{h}$ be the fundamental chamber of $\mathfrak{g}$.
Then $\Gamma$ is defined by the inequality $Bx\geq 0$, $\Gamma$ is polyhedral,
and rational since the entries of $\mathfrak{g}$ are integers. Now
$\Delta_{f}$ is contained in the semigroup of lattice points $G$ of the dual
cone of $\Gamma$ [4, §5.8]. By Gordan’s theorem, $G$ is finitely generated, so
we take as our Hilbert basis a generating set of minimal cardinality. ∎

The Hilbert basis $\beta_{1},\dots,\beta_{k}$ of $\Gamma^{*}$ can be computed
efficiently from the Cartan matrix of $\mathfrak{g}$ by e.g. the Elliot-
MacMahon algorithm [6]. In our implementation we use polymake [3]’s
implementation of the Elliot-MacMahon algorithm. From the Hilbert basis, any
$\beta\in\Delta_{f}$ can be written uniquely as a linear combination of the
$\beta_{j}$.

######  Lemma 3.2.

Let $\ell=\gcd\gamma$ and assume $(\gamma,\gamma)>0$. If
$\gamma/\ell\in\Delta$, then $c(\gamma)=1/\ell$. Otherwise, $c(\gamma)=0$.

###### Proof.

We write $\gamma=\sum_{i}\gamma^{i}\alpha_{i}$. We first claim that if $w\in
W$ and $\ell=1$, then $\gcd w\gamma=1$. Indeed, one has

$w_{j}\gamma=\sum_{i}\gamma^{i}(\alpha_{i}-a_{ij}\alpha_{j})=\sum_{i\neq
j}\gamma^{i}\alpha_{i}+(\gamma^{j}-\sum_{i}a_{ij}\gamma^{i})\alpha_{j}$

and

$\gamma\sum_{i\neq
j}(d_{i}+d_{j}a_{ij})\gamma^{i}+d_{j}\left(\gamma^{j}-\sum_{i}a_{ij}\gamma^{i}\right)=\sum_{i}d_{i}\gamma^{i}=\ell.$

Therefore Bezout’s theorem implies that $\gcd w\gamma=1$. From this it follows
that if $\gamma\in\Delta$, then $\ell=1$.

Since $(\gamma,\gamma)>0$, there is at most one $\gamma^{\flat}\in Q$ in the
span of $\gamma$ such that $\gamma\in\Delta$. If $\gamma\in\Delta$, then the
above argument shows that $c(\gamma)=m(\gamma)=1$ and $\ell=1$. Otherwise,
since $c(\gamma)>0$ and $(\gamma,\gamma)>0$, there is a
$\gamma^{\flat}|\gamma$ with $m(\gamma^{\flat})=1$. Since we then have
$\gcd\gamma^{\flat}=1$, it follows that $\ell\gamma^{\flat}=\gamma$, so the
claim follows from definition of $c$. ∎

We now introduce the _graded ascent algorithm_.

Data: a root $\beta\in\Delta_{f}$, a maximal height $h$

$R:=0$;

for  _$\gamma\in\Delta:\gamma\prec\beta$_ do

if  _$(\gamma,\gamma) >0$_ then

$S:=0$;

for  _$1\leq n\leq|\beta|/|\gamma|$_ do

if  _$\beta\leq n\gamma$_ then

break;

end if

$S:=S+((\gamma,\beta)-n(\gamma,\gamma))c(\gamma)$;

end for

$R:=R+S$;

end if

else

if  _$c(\beta-\gamma) >0$_ then

$R:=R+((\gamma,\beta)-(\gamma,\gamma))c(\gamma)$;

end if

end if

end for

$c(\beta):=R/((\beta,\beta)-2|\beta|)$;

$\Delta:=\Delta\cup\beta$;

pingpong$(\beta,h)$;

Algorithm 2 The graded ascent algorithm.

######  Theorem 3.3.

Let $\beta\in\Delta_{f}$ and $h\geq 0$. Suppose that:

  1. 1.

For every $\alpha\in\Delta_{f}$ such that $\alpha\prec\beta$, we have already
computed $c(\alpha)$ using the graded ascent algorithm with $h$ as input.

  2. 2.

We have run the pingpong algorithm on the simple roots and a Hilbert basis.

  3. 3.

$|\beta|\leq h$.

Then for every $w\in W$ such that $|w\beta|\leq h$, the graded ascent
algorithm correctly computes $c(w\beta)$.

###### Proof.

Let $\gamma\in Q$, and suppose $\gamma\prec\beta$. If we can show that either
$c(\gamma)$ was already computed, or that the graded ascent algorithm will
correctly compute $c(\gamma)$, then the correctness of $c(\beta)$ will follow
by the Peterson recurrence formula.

Suppose $(\gamma,\gamma)>0$ and let $\ell=\gcd\gamma$. By Lemma 3.2, then
either $\gamma/\ell$ is a root and $c(\gamma)=1/\ell$, or $\gamma/\ell$ is not
a root and $c(\gamma)=0$.

First suppose $\ell=1$. If $\gamma$ is a root, then there is a simple root
$\alpha_{j}$ and a $w\in W$ such that $\gamma=w\alpha_{j}$. So the pingpong
algorithm correctly placed $\gamma$ in $\Delta$, and $c(\gamma)=1$. Moreover,
every multiple of $\gamma$ which lies under $\gamma$ is of the form $n\gamma$
for $n\in\\{1,\dots,|\beta|/|\gamma|\\}$. Iterating over such $n$, we also
compute the $c(n\gamma)$ correctly. The variable $S$, after iterating over
$n$, the sum of the contributions of the $c(n\gamma)$.

Now suppose $\ell>1$. Then the contribution of $c(\gamma)$ will be added to
$R$ with the contribution of $\gamma/\ell$. In this case,
$\gamma\notin\Delta$, so the algorithm does not double-count.

Now suppose $(\gamma,\gamma)\leq 0$. If $c(\beta-\gamma)=0$, then $\gamma$
does not contribute to the Peterson recurrence formula and can be neglected.
Otherwise, we need to show that the graded ascent algorithm already placed
$\gamma$ in $\Delta$. But this follows by the assumption that this is true if
$\gamma\in\Delta_{f}$, by the pingpong algorithm. Indeed, $\gamma=w\gamma_{0}$
for some $\gamma_{0}\in\Delta_{f}$ and $w\in W$ by basic properties of Kac-
Moody algebras.

By linearity of $w\in W$, $c(w\beta)=c(\beta)$, so that the algorithm
correctly computes $c(w\beta)$ as well, and adds them to $\Delta$ correctly. ∎

We now outline the structure of a program that would use the pingpong and
graded ascent algorithms to compute root multiplicities. First, the program
runs the Elliot-MacMahon algorithm to compute the Hilbert basis
$\beta_{1},\dots,\beta_{k}$. The program then runs the pingpong algorithm on
the simple roots and the Hilbert basis with input height $h$. The program
maintains an ordering on $\Delta_{f}$ by height, and iterates the graded
ascent algorithm on $\Delta_{f}$. This guarantees that the assumptions of
Theorem 3.3 are met, by induction.

##  4 Runtime

We now study the runtime of the above algorithm.

Let $d$ be the dimension of the Cartan matrix, as above and assume that we
want to compute all multiplicities up to height $h$. Let $\omega$ be the
complexity exponent for matrix multiplication (so multiplication of two
$n\times n$ matrices has runtime $O(n^{\omega})$, and this estimate is best
possible). It is known that $2\leq\omega<2.38$ [7]. Then the computation of a
Killing form $(\cdot,\cdot)$ has runtime $O(d^{\omega})$. In particular,
computing the action of a fundamental reflection has runtime $O(d^{\omega})$.

We assume that initializing a root object has $O(d)$ runtime, as a result of
overhead due to copying lists. We also observe that by standard results about
the complexity of the Euclidean algorithm, the time needed to compute
$\gcd\gamma$ for any $\gamma\in Q^{+}$ is $O(d\log\max\gamma)$ where
$\max\gamma$ is the maximum of the coordinates of $\gamma$ with respect to
$\Delta_{simp}$. We assume that inserting and looking up in dictionaries has
average-case runtime $O(1)$, as it does in Python.

It is not hard to see, then, that the computations of Killing forms will be
the dominant term in the runtime of the algorithm, so we bound the number of
Killing form computations.

######  Proposition 4.1.

A naive application of the Peterson recurrence formula requires computation of

$K_{\text{naive}}(h)=4\left(\binom{h+2d-1}{2d}-\left\lceil\frac{h^{d}}{d!}\right\rceil\right)$

Killing forms.

###### Proof.

The naive algorithm requires that we must iterate over $h^{d}$ many elements
of the positive root lattice $Q^{+}$, and for each $\beta\in Q$,
$\beta=(\beta_{1},\dots,\beta_{n})$ written in the basis of simple roots, we
must iterate over $-1+\prod_{j}\beta_{j}$ many subroots of $\beta$, computing
$4$ Killing forms for each subroot. We arrange the set

$Q_{d,h}=\\{\beta\in Q^{+}:|\beta|\leq h\\}$

into a $d$-dimensional grid (here shown in dimension $d=2$, where the left
grid shows the coordinates $(\beta_{j})_{j}$ and the right grid shows the
product of the coordinates $\prod_{j}\beta_{j}$)

$\displaystyle\begin{matrix}(1,h)&\\\ (1,h-1)&(2,h-1)\\\
(1,h-2)&(2,h-2)&\ddots\\\ \vdots&\vdots&(\beta_{1},\beta_{2})&\ddots\\\
(1,1)&(2,1)&\cdots&&(h,1)\end{matrix}$ $\displaystyle\begin{matrix}h&\\\
h-1&2(h-1)\\\ h-2&2(h-2)&\ddots\\\ \vdots&\vdots&\beta_{1}\beta_{2}&\ddots\\\
1&2&\cdots&&h.\end{matrix}$

We then compute the sum $S_{d,h}$ of the entries in the right grid. A direct
computation shows that

$S_{1,h}=1+\dots+h=\binom{h+1}{2}.$

Suppose inductively that $S_{d,h}=\binom{h+2d-1}{2d}$. We sum up the rows of
the right grid corresponding to $Q_{d+1,h}$, each of which is a multiple of a
right grid corresponding to $Q_{d+1,h-j}$, to see that

$\displaystyle S_{d+1,h}$ $\displaystyle=S_{d,h}+2S_{d,h-1}+\dots+hS_{d,1}$
$\displaystyle=\binom{h+2d-1}{2d}+2\binom{h+2d-2}{2d}+\dots+h\binom{2d}{2d}$
$\displaystyle=\left(\binom{h+2d-1}{2d}+\binom{h+2d-2}{2d}+\dots+\binom{2d}{2d}\right)$
$\displaystyle~{}~{}+\left(\binom{h+2d-2}{2d}+\dots+\binom{2d}{2d}\right)+\dots+\binom{2d}{2d}$
$\displaystyle=\binom{h+2d}{2d+1}+\binom{h+2d-1}{2d+1}+\dots+\binom{2d+1}{2d+1}$
$\displaystyle=\binom{h+2d+1}{2d+2}=\binom{h+2(d+1)-1}{2(d+1)}.$

Therefore, since $|Q_{d,h}|$ is contained in a $d$-simplex of side length $h$
and hence volume $h^{d}/d!$,

$\sum_{\beta\in
Q_{d,h}}-1+\prod_{j=1}^{d}\beta_{j}=-h^{d}+S_{d,h}=\left\lceil\frac{h^{d}}{d!}\right\rceil+\binom{h+2d-1}{2d}.$

This completes the proof. ∎

Let $\mathcal{O}_{\beta}$ denote the set of those elements $\gamma$ of the
Weyl orbit of $\beta\in Q^{+}$ such that $|\gamma|\leq h$. The pingpong
algorithm iterates over all of $\mathcal{O}_{\beta}$. For each $\gamma$ in the
orbit, each fundamental reflection $w_{j}(\beta)=(\beta,\alpha_{j})$, of which
there are $d$, must be computed. So computing $\mathcal{O}_{\beta}$ using the
pingpong algorithm requires $d|\mathcal{O}_{\beta}|$ computations of Killing
forms.

Let

$P_{h}=\frac{|\\{\beta\in\Delta^{+}:|\beta|=h\\}|}{|\\{\beta\in
Q^{+}:|\beta|=h\\}|}$

denote the probability that a randomly selected element of the root lattice of
height $h$ is actually a root. Note that $P_{\infty}=\lim_{h\to\infty}P_{h}$
can actually be computed from the Cartan matrix in many cases, and can be used
to approximate $P_{h}$ well in such cases. In trivial cases, such as $E_{9}$
and finite-dimensional Lie algebras, $P_{\infty}=0$. In general,
$P_{\infty}<1$, since the $\mathbb{Z}$-span of each real root $\alpha$ can
only meet $\Delta^{+}$ at one point, namely $\alpha$ itself, yet if
$\mathfrak{g}$ is infinite-dimensional then there are infinitely many real
roots. We similarly define

$Q_{h}=\max_{j\leq h}\frac{|\\{\beta\in\Delta_{f}:|\beta|=j\\}|}{|\\{\beta\in
Q^{+}:|\beta|=j\\}|}$

and $Q_{\infty}=\lim_{h\to\infty}Q_{h}$, so that $Q_{h}\leq P_{h}$.

Suppose, for simplicity, that all simple roots $\alpha_{j}$ have the same
Killing length, i.e. $(\alpha_{j},\alpha_{j})=C$; this follows, for example,
if the Cartan matrix $A$ is symmetric. We note that $P_{h}$ is increasing,
since $P_{h}h^{d}$ counts the number of $\gamma\in Q$ such that
$(\gamma,\gamma)\leq C$ and $|\gamma|=h$, and the curve $(\gamma,\gamma)=C$ is
a hyperboloid. By definition, $Q_{h}$ is also increasing. So the limits
$P_{\infty}$, $Q_{\infty}$ exist by the monotone convergence theorem.

######  Proposition 4.2.

Suppose that all simple roots have the same Killing length. Let
$K_{\text{ascent}}(h)$ denote the number of Killing forms needed to compute
root multiplicities using the graded ascent algorithm up to height $h$. Then

$K_{\text{ascent}}(h)\leq P_{h}Q_{h}K_{\text{naive}}(h)+dP_{h}h^{d}.$

In particular, for any $h$,

$K_{\text{ascent}}(h)\leq
P_{\infty}Q_{\infty}K_{\text{naive}}(h)+dP_{\infty}h^{d}.$

###### Proof.

For each $\beta\in\Delta_{f}$, $K_{\beta}$ denote the number of Killing forms
that the graded ascent algorithm uses to apply the Peterson recurrence formula
to compute $c(\beta)$. Then

$K_{\text{ascent}}(h)=f(h)+\sum_{j=1}^{h}\sum_{\begin{subarray}{c}\beta\in\Delta_{f}\\\
|\beta|=j\end{subarray}}K_{\beta},$

where $f(h)$ is the number of Killing form computations used by the pingpong
algorithm. Moreover, $K_{\beta}$ is at most $4$ times the set of
$\gamma\in\Delta$ such that $\gamma\prec\beta$. The set of $\gamma\in\Delta$
such that $|\gamma|=j$ has cardinality $P_{j}\binom{j+d-1}{d-1}$ since each
such $\gamma$ corresponds to a way of summing $d$ natural numbers up to $j$.
For the same reason the set of all such $\beta$ has cardinality
$Q_{h}\binom{h+d-1}{d-1}$, so

$\displaystyle K_{\text{ascent}}(h)$
$\displaystyle\leq\sum_{j=1}^{h}P_{j}\binom{j+d-1}{d-1}Q_{h}\binom{h+d-1}{d-1}$
$\displaystyle\leq
P_{h}Q_{h}\sum_{j=1}^{h}\binom{j+d-1}{d-1}\binom{h+d-1}{d-1}$
$\displaystyle=P_{h}Q_{h}K_{\text{naive}}(h)\leq
P_{\infty}Q_{\infty}K_{\text{naive}}(h).$

Here we use the fact that

$\sum_{j=1}^{h}\binom{j+d-1}{d-1}\binom{h+d-1}{d-1}\leq K_{\text{naive}}(h),$

which follows from the “right grid” computation of $K_{\text{naive}}(h)$. We
also use the fact that $P_{j},Q_{j}$ are increasing sequences.

Pingponging $\beta$ then requires $d|\mathcal{O}_{\beta}|$ computations of
Killing forms. Since every $\beta\in\Delta^{+}$ such that $|\beta|\leq h$ will
appear in exactly one Weyl orbit computed this way, the sum
$\sum_{\beta}|\mathcal{O}_{\beta}|=P_{h}h^{d}$ where $\beta$ ranges over
representatives of each Weyl orbit. So a total of $f(h)=dP_{h}h^{d}$ Killing
forms must be computed to execute the pingpong algorithm. ∎

Note that for $h$ very large, both our algorithm and the naive algorithm have
super-exponential runtime in $d$. However, the coefficient on the leading-
order terms are quite different, which can make the difference between minutes
and hours’ worth of computation in practice. In addition, the estimate in
Proposition 4.2 is general enough to hold for any symmetric Cartan matrix, it
is rarely sharp. To illustrate, we compute $K_{\text{naive}}$ and
$K_{\text{ascent}}$ for some small values for the exceptional algebra
$E_{10}$.

$h$ | $K_{\text{naive}}(h)$ | $K_{\text{ascent}}(h)$
---|---|---
$10$ | $8.218\cdot 10^{9}$ | $950$
$30$ | $9.488\cdot 10^{19}$ | $4490$
$60$ | $3.299\cdot 10^{28}$ | $35451$
$93$ | $4.407\cdot 10^{34}$ | $696021$

But $E_{10}$ has few imaginary roots of height $\leq 100$, and has a high
dimension, so this is an extreme example. To illustrate a much less extreme
case, we consider the Kac-Moody algebra with Cartan matrix
$\begin{bmatrix}2&-3\\\ -3&2\end{bmatrix}$, which is more typical of Kac-Moody
algebras in practice. Since this algebra is a symmetric algebra whose Cartan
matrix has dimension $2$, we only have to compute the subroots
$\gamma=\gamma^{1}\alpha_{1}+\gamma^{2}\alpha_{2}$ of a $\beta\in\Delta_{f}$
for which $\gamma^{1}<\gamma^{2}$, and then multiply the total multiplicity by
$2$ – an easy optimization which will save us some computation time.

$h$ | $K_{\text{naive}}(h)$ | $K_{\text{ascent}}(h)$
---|---|---
$10$ | $2660$ | $236$
$20$ | $34620$ | $1719$
$30$ | $161880$ | $6556$
$40$ | $490440$ | $18079$
$50$ | $1116300$ | $40883$
$100$ | $17665100$ | $566541$

So the algorithm is approximately a constant (which is highly significant for
practical purposes!) times faster than the naive algorithm, exactly what
Proposition 4.2 predicts.

## Acknowledgements

The authors gratefully acknowledge the financial backing of the Sherrill Fund
and the Summer Undergraduate Research Fellowship.

## References

  * [1] W. Bruns and J. Gubeladze.  Polytopes, Rings, and K-Theory.  Springer Monographs in Mathematics. Springer New York, 2009.
  * [2] Lisa Carbone, Walter Freyn, and Kyu-Hwan Lee.  Dimensions of imaginary root spaces of hyperbolic kac-moody algebras.  Contemp. Math, 623:23–40, 2014.
  * [3] Ewgenij Gawrilow and Michael Joswig.  polymake: a framework for analyzing convex polytopes.  In Polytopes—combinatorics and computation (Oberwolfach, 1997), volume 29 of DMV Sem., pages 43–73. Birkhäuser, Basel, 2000.
  * [4] Victor G. Kac.  Infinite-dimensional Lie algebras: an introduction.  Birkhauser, 2014.
  * [5] Axel Kleinschmidt.  E11 as e10 representation at low levels.  Nuclear physics. B, 677(3):553–586, 2004.
  * [6] Dmitrii V Pasechnik.  On computing hilbert bases via the elliot–macmahon algorithm.  Theoretical computer science, 263(1-2):37–46, 2001.
  * [7] Virginia Vassilevska Williams.  Multiplying matrices in o(n2̂.373) time.  2014\.