Algorithm to list all Kostant partitions

Question

Let $\Phi_+$ be the set of positive roots in some root system, and let $Q_+$ be the positive part of the root lattice, i.e., the set of elements of the form $\sum_{\beta\in \Phi_+}m_\beta\beta$ with $m_\beta \in \mathbb{Z}_{\geq 0}$. For $\theta\in Q_+$, a Kostant partition of $\theta$ is a sequence $(\beta_1^{(m_1)}, \ldots, \beta_t^{(m_t)})$ such that $\beta_i\in \Phi_+$, $m_i\in \mathbb{Z}_{>0}$, $m_1\beta_1 + \cdots + m_t\beta_t = \theta$, and $\beta_1 > \cdots > \beta_t$ according to some fixed total order on $\Phi_+$. For example, for the root system of type $A_3$ with simple roots $\alpha_1, \alpha_2, \alpha_3$, the Kostant partitions of $\theta = \alpha_1+2\alpha_2+\alpha_3$ are $$(\alpha_1+\alpha_2+\alpha_3, \alpha_2), \ (\alpha_2+\alpha_3, \alpha_1+\alpha_2), \ (\alpha_3, \alpha_2, \alpha_1+\alpha_2), \ (\alpha_2+\alpha_3, \alpha_1, \alpha_1), \ (\alpha_3, \alpha_2^{(2)}, \alpha_1).$$ Is there an algorithm for listing or iterating through all Kostant partitions of a given $\theta\in Q_+$ (for an arbitrary root system)? An inefficient/recursive attempt is as follows:

Phi := the set of positive roots Q := the positive part of the root lattice def KostantPartitions(theta): L = [] for beta in Phi: if theta-beta is in Q: for kp in KostantPartitions(theta-beta): new = kp with beta inserted if new not in L: L += [new] return L 

Is there a more efficient algorithm? I realize this question is ill-posed (what does "efficient" mean?); I am really just looking for something better than the above. I would also be happy with partial answers, e.g., an algorithm for root systems of type $A$.

Answer 1

For fixed $\theta$, the set of $(m_{\beta})$ giving a Kostant partition is evidently the set of lattice points in some polyhedron given in terms of hyperplane inequalities and equalities: they are exactly the integer points satisfying the inequalities $m_{\beta} \geq 0$ and equalities coming from $\theta = \sum_{\beta} m_{\beta} \beta$. There are a lot of software out there which can solve the general problem of finding all the lattice points of a given polyhedron: e.g., general math software like Sage can do this (see the documentation at http://doc.sagemath.org/html/en/reference/discrete_geometry/sage/geometry/lattice_polytope.html), but also there is specialized software like "LattE" (https://www.math.ucdavis.edu/~latte/).

Incidentally, this kind of reasoning is what lets you conclude that the Kostant partition function (i.e., the number of Kostant partitions) is a piecewise quasipolynomial, a fact which you may be interested in if you were not aware of it already. And in the particular case of the Type A root system, which you mentioned you were specially interested in, unimodularity implies that the Kostant partition function is a piecewise polynomial; see https://www.sciencedirect.com/science/article/pii/S0021869304000055.

Answer 2

The Kostant partition function is closely related to so called flow polytopes. This might give some insight in how to compute it, see for example Thm. 37 in this paper.

See also this paper that mentions implementations.