Membership in moment polytopes is in NP and coNP

Introduction and summary of results

Moment polytopes are convex polytopes that describe invariants of Hamiltonian manifolds. Their study has a long and rich history in mathematics and in physics , most recently in quantum information theory in the context of the quantum marginal problem . Moment polytopes and their underlying representation-theoretic data have also become of interest in computer science, since they are possible sources of representation-theoretic obstructions that may lead to new complexity-theoretic lower bounds .

We remark that $\operatorname{Kron}(m)$ is known to be a convex polytope of dimension $3(m-1)$ .

We consider the problem KronPolytope of deciding whether $(\lambda_{A},\lambda_{B},\lambda_{C})/k\in\operatorname{Kron}(m)$, given as input a triple of Young diagrams $\lambda_{A},\lambda_{B},\lambda_{C}\vdash k$ (each specified by its row lengths encoded in binary), where $m$ denotes the maximum among the heights of the three Young diagrams. Equivalently, KronPolytope is the problem of deciding whether there exists some positive integer $l>0$ such that the stretched Kronecker coefficient $g(l\lambda_{A},l\lambda_{B},l\lambda_{C})>0$.

Our main result in the case of the Kronecker polytopes then is the following theorem:

The problem KronPolytope is in $\NP\cap\coNP$.

That is, there exists polynomially-sized certificates such that both membership and non-membership can be verified in polynomial time. We discuss the implications of Theorem 1 in section 1.1 below.

We now consider the general case. Let $G$ denote a compact, connected Lie group and $M$ a unitary representation of $G$. For each integer $k>0$, we denote by $m_{G,M,k}(\lambda)$ the multiplicity of the irreducible $G$-representation with highest weight $\lambda$ in $\operatorname{Sym}^{k}(M)$, the $k$-th symmetric power of $M$. Then the pairs $(k,\lambda)$ for which $m_{G,M,k}(\lambda)>0$ form a finitely generated semigroup and so the following set is a rational convex polytope, called the moment polytope associated with the $G$-representation $M$:

We are interested in the problem MomentPolytope of deciding whether $\lambda/k\in\Delta_{G}(M)$, given as input a compact, connected Lie group $G$, a finite-dimensional unitary representation $M$ with moment polytope of maximal dimension, a highest weight $\lambda$, and a positive integer $k$. Equivalently, MomentPolytope is the problem of deciding whether there exists some positive integer $l>0$ such that the stretched multiplicity $m_{G,M,lk}(l\lambda)>0$. We discuss the precise encoding of the input in section 3.1 below. Roughly speaking, the group is specified in terms of Dynkin diagrams and the representation in terms of its highest weights, given by its coefficients in binary with respect to a basis of fundamental weights, together with the total dimension of the representation $M$ in unary. The latter is a natural requirement, as it allows the algorithms to run in polynomial time in the dimension of the representation, which can be exponential in the specification of the highest weights alone. In the case of the Kronecker coefficients, this requirement is vacuous, as the dimension is only of polynomial size in the specification of $\lambda_{A},\lambda_{B},\lambda_{C}$, and so it is not hard to see that the problem MomentPolytope is indeed a proper generalization of KronPolytope.

The main result of this paper is the following theorem, which generalizes Theorem 1 above.

The problem MomentPolytope is in $\NP\cap\coNP$.

Sets of defining inequalities for $\Delta_{G}(M)$ have been computed in . To prove Theorems 1 and 2, our principal ingredient is the recent description from . We also rely on an alternative, geometric characterization of $\Delta_{G}(M)$, often taken as its definition, whose equivalence has been established by Mumford . In both cases, a major challenge is to show that these mathematical results can be made effective, i.e., that approximations can be found that give rise to polynomial-sized certificates, and that these certificates can in turn be verified efficiently.

We note that Theorems 2 and 1 are non-trivial complexity-theoretic results. On the one hand, from the representation-theoretic point of view, all known upper bounds on the stretching factor $l$ required to witness membership of some $\lambda/k$ in the moment polytope can be exponential in the input specification (even when restricted to invariants, see, e.g., ). On the other hand, the geometric description of the moment polytopes naively amounts to a quadratically constrained program, which are NP-hard in general. In contrast, Theorems 2 and 1 strongly suggest that MomentPolytope and KronPolytope are not NP-hard problems, for otherwise $\NP=\coNP$, which is widely regarded as implausible (e.g., ). Thus the situation is similar to that of the integer factorization problem (likewise in $\NP\cap\coNP$), the unknotting problem (in $\NP\cap\coNP$, assuming the generalized Riemann hypothesis), and the graph isomorphism problem (in $\NP\cap\coAM$). This is in remarkable contrast to the recent result in that deciding positivity of a single Kronecker coefficient is NP-hard in general.

It might be conjectured that membership in moment polytopes can in fact be decided in polynomial time. This is known to be true for the Horn polytopes, which geometrically characterize the eigenvalues of triples of Hermitian matrices that add up to zero, $A+B+C=0$. However, the proof in this case relies precisely on the fact that the Littlewood-Richardson coefficients, which are the associated representation-theoretic coefficients and in fact special Kronecker coefficients, are saturated and that their positivity can be decided in polynomial time . Saturation does not hold in general, and in particular not for the Kronecker coefficients. Moreover, as we have just discussed, deciding positivity is in general an NP-hard problem, so this strategy of proof cannot be generalized. In contrast, our strategy of proof circumvents this barrier and may be seen as a first step towards establishing the conjecture.

Finally, we remark that for a fixed group and representation (such as for Young diagrams with bounded height), the membership problem is trivial, since it concerns only a single polytope which can be precomputed. Likewise, it is known that in this case positivity can be decided and indeed that the coefficients can be calculated precisely in polynomial time .

2 Organization of the paper

In section 2, we first prove our result in the important special case of the family of Kronecker polytopes (Theorem 1). We will follow the proof strategy for the general membership problem, but our presentation will not rely on expert knowledge in the representation theory of Lie groups. Then, in section 3 we prove our general result, where the group and representation defining the moment polytope are part of the input (Theorem 2).

3 Notation and conventions

The Kronecker polytopes

In this section, we will prove our complexity result for the Kronecker polytopes (Theorem 1). While this result can also be obtained as a consequence of our general result (Theorem 2), which we prove in section 3 below, the exposition in this section contains all essential ideas while not requiring expert knowledge in representation theory. Our notation and terminology will match precisely the one used in section 3 below.

Admissibility: The points in $\Phi(H=z)$ span an affine hyperplane in $P(m)$.

Determinant condition: Consider the following matrix $D_{H,z}$ whose rows are indexed by elements $\omega\in\Phi(H<z)$ and whose columns are indexed by elements $\alpha\in N(H<0)$,

where the $X_{\varphi}$ are indeterminates. By the trace condition, $D_{H,z}$ is a square matrix, so that we can form the determinant polynomial $d_{H,z}:=\det D_{H,z}$, and the condition is that $d_{H,z}$ should be non-zero.

We observe that the number of Ressayre elements is finite (up to overall rescaling). We have the following description of the Kronecker polytopes in terms of finitely many inequalities :

where $P_{+}(m)=\{(r_{A},r_{B},r_{C})\in P(m)\;:\;r_{X,1}\geq\dots\geq r_{X,m}\;(\forall X=A,B,C)\}$ is the positive Weyl chamber. It is known that $\operatorname{Kron}(m)\subseteq P(m)$ is a convex polytope of maximal dimension $3(m-1)$ . Let us call a facet of $\operatorname{Kron}(m)$ non-trivial if it is not of the form $r_{X,i}\geq r_{X_{i}+1}$. Equation 2 implies that any non-trivial facet is necessarily given by a Ressayre element.

2 KronPolytope is in coNP

The algorithm proceeds as follows: We first check the conditions in section 2.1 to verify that $(H,z)$ is a Ressayre element for $\operatorname{Kron}(m)$:

Admissibility: The number of weights $\#\Phi(m)$ is $m^{3}$ and each weight lives in a space of dimension $3m$. For each weight $\varphi\in\Phi(m)$, we can check whether $\varphi\in\Phi(H=z)$ by verifying that the inner product with $H$ satisfies $H\cdot\varphi=z$. Thus we can in polynomial time determine $\Phi(H=z)$ and compute the rank of the polynomial-size matrix with columns $\begin{pmatrix}\varphi\\ -1\end{pmatrix}$ for $\varphi\in\Phi(H=z)$. The element $(H,z)$ is admissible if and only if the rank is equal to $3(m-1)$.

Trace condition: As there are $O(m^{2})$ negative roots and $m^{3}$ weights, each of which lives in a space of dimension $3m$ and can be constructed efficiently, both cardinalities can be computed and compared in polynomial time.

Determinant: We construct the matrix $D_{H,z}(p)$ defined as in Eq. 1 for $X=p$. The matrix is of polynomial size and we can therefore compute its determinant $d_{H,z}(p)$ exactly in polynomial time. We accept if and only if $d_{H,z}(p)\neq 0$.

At this point we are sure that $(H,z)$ defines a non-trivial facet of the Kronecker polytope (the trivial inequalities are automatically satisfied since $\lambda_{A}$, $\lambda_{B}$ and $\lambda_{C}$ are partitions). In the last step of the algorithm, we verify that this facet indeed separates $(\lambda_{A},\lambda_{B},\lambda_{C})/k$ from the polytope by checking that

It is clear that the algorithm will accept only if $(\lambda_{A},\lambda_{B},\lambda_{C})/k\not\in\operatorname{Kron}(m)$.

We will now show that, conversely, if $(\lambda_{A},\lambda_{B},\lambda_{C})/k\not\in\operatorname{Kron}(m)$ then there always exists a polynomial-sized certificate $(H,z,p)$ such that the algorithm accepts. For this, we need the following basic estimate:

Any non-trivial facet of $\operatorname{Kron}(m)$ can be described by a Ressayre element $(H,z)$ with

Note that we have $M=3m$ equations for $N=3m+1$ unknowns, and the absolute value of the coefficients is at most $B=1$. Therefore, Siegel’s lemma ensures that there exists an integral solution with

The upshot of Lemma 3 is the following: If $(\lambda_{A},\lambda_{B},\lambda_{C})/k\not\in\operatorname{Kron}(m)$ then there exists a non-trivial facet separating it from the Kronecker polytope. Lemma 3 tells us that any such facet can be encoded by some Ressayre element $(H,z)$ that can be specified using no more than $O(m^{2}\log m)$ bits. Indeed, $(H,z)$ consists of $3m+1$ coefficients, each of which requires $O(m\log m)$ bits.

At last, consider the determinant polynomial $d_{H,z}$, which is a nonzero multivariate polynomial of degree $\#\Phi(H<z)=\#N(H<0)\leq m^{3}$ in $\#\Phi(H=z)\leq m^{3}$ variables. The Schwartz-Zippel lemma [40, Corollary 1] shows that the fraction of points $p\in\{0,\dots,m^{3}\}^{\#\Phi(H=z)}$ with $d_{H,z}(p)=0$ is at most $\#\Phi(H<z)/(m^{3}+1)<1$. It follows that there exists some $p\in\{0,\dots,m^{3}\}^{\#\Phi(H=z)}$ such that $d_{H,z}(p)\neq 0$. Note that $p$ can be specified using no more than $O(m^{3}\log m)$ bits.

As the input size is $\Omega(m)$, the data $(H,z,p)$ together consists of a polynomial-sized certificate that will be accepted by the algorithm. We conclude that the problem KronPolytope is in $\coNP$.

We remark that Alon’s combinatorial Nullstellensatz [1, Theorem 1.2] gives a much stronger bound than the Schwartz-Zippel lemma, and it would be interesting to see if it can be exploited to find even smaller certificates.

3 KronPolytope is in NP

Here, we write $\operatorname{diag}v$ for the diagonal matrix with diagonal entries $v$, and $\lVert-\rVert_{F}$ denotes the Frobenius norm. It is immediate that Eq. 6 can be verified in polynomial time.

By combining all three statements we obtain that

As $\psi$ is a unit vector, the magnitude of each of its $D$ components is no larger than one. Thus the truncation incurs an absolute error of at most $2^{-b}$ on the real and imaginary parts. We conclude that

We have the following sequence of inequalities,

As a direct consequence of Lemmas 5 and 7, the truncation to $b$ bits leads to an error of at most

Comparing with Eq. 6, we find that we only need to choose $b=O(m\log m+\log k)$ bits of precision to produce a certificate that the algorithm accepts. This is polynomial in the size of the problem instance $(\lambda_{A},\lambda_{B},\lambda_{C})$, which is $\Omega(m)$ and $\Omega(\log k)$. Thus there exists a polynomially-sized certificate that our algorithm accepts.

Conversely, let us assume that in fact $(\lambda_{A},\lambda_{B},\lambda_{C})/k\not\in\operatorname{Kron}(m)$. We will use the following lemma, which in colloquial terms asserts that the “slope” of any facet of $\operatorname{Kron}(m)$ is never too steep. More precisely:

Let $\lambda_{A},\lambda_{B},\lambda_{C}\vdash k$. Then, if $(\lambda_{A},\lambda_{B},\lambda_{C})/k\not\in\operatorname{Kron}(m)$, it has Euclidean distance at least

Consider a non-trivial facet that separates $(\lambda_{A},\lambda_{B},\lambda_{C})/k$ from $\operatorname{Kron}(m)$. According to Lemma 3, any such facet can be described by some Ressayre element $(H,z)$ satisfying Eq. 3. We can therefore lower-bound the distance to $\operatorname{Kron}(m)$ in the following way:

where we have used that both $(H,z)$ and $(\lambda_{A},\lambda_{B},\lambda_{C})$ have integer coefficients. We now use that $\lVert H\rVert_{2}\leq\sqrt{3m}\lVert H\rVert_{\infty}\leq 3m\lVert H\rVert_{\infty}$ and the upper bound Eq. 3 to conclude that

In view of Eq. 6, our algorithm will therefore never accept if $(\lambda_{A},\lambda_{B},\lambda_{C})/k\not\in\operatorname{Kron}(m)$.

We conclude that the problem KronPolytope is in $\NP$. Sections 2.2 and 2.3 together establish Theorem 1.

The general membership problem

We now turn to the membership problem for the moment polytope associated with an arbitrary finite-dimensional unitary representation $M$ of a compact, connected Lie group $G$.

Given an arbitrary group $G=G_{1}\times\dots\times G_{n}$, the above choices determine a maximal torus $T$, Lie algebra $\mathfrak{t}$, Weyl group $W$, positive roots $P(G)$ and negative roots $N(G)=-P(G)$, the lattice $\Lambda_{G}\subseteq i\mathfrak{t}$ with basis the simple coroots $h_{\alpha}$ together with the basis vectors of the tori, the dual weight lattice $\Lambda^{*}_{G}\subseteq i\mathfrak{t}^{*}$ with basis the fundamental weights $\omega_{i}$ together with the basis vectors of the tori, a positive Weyl chamber $i\mathfrak{t}^{*}_{+}=\{r\in i\mathfrak{t}^{*}:r(h_{\alpha})\geq 0\;\forall\alpha\in P(G)\}$, and a $G$-invariant inner product on $i\mathfrak{g}$; we will denote the induced norm by $\lVert-\rVert_{i\mathfrak{g}}$. By duality, we likewise obtain an inner product and norm $\lVert-\rVert_{i\mathfrak{g}^{*}}$ on $i\mathfrak{g}^{*}$ and on $i\mathfrak{t}^{*}$. We note that the basis vectors of $\Lambda_{G}$ and $\Lambda_{G}^{*}$ have norm $\Theta(1)$ by our conventions (however we caution that they are not orthogonal). At last, we obtain a basis of $i\mathfrak{g}$ by adjoining to the basis of $\Lambda_{G}$ the basis vectors $e_{\alpha}$ of the root spaces; this also determines a dual basis of $i\mathfrak{g}^{*}$. We will make repeated use of these objects in the following.

Recall that MomentPolytope is the problem of deciding whether a given point $\lambda/k$ is an element of some moment polytope $\Delta_{G}(M)$. A problem instance of MomentPolytope is thus given abstractly by a quadruple $(G,M,\lambda,k)$ consisting of a group $G$, a representation $M$, a highest weight $\lambda$, and an integer $k$. We will now describe explicitly the specification in which we assume that this data is given to an algorithm. For this, we follow ; in particular, we will write $\langle X\rangle$ for the bitsize of an object $X$. Thus the input size of a problem instance $(G,M,\lambda,k)$ is $\Theta(\langle G\rangle+\langle M\rangle+\langle\lambda\rangle+\langle k\rangle)$.

To specify the group $G$, we recall from the discussion above that its Lie algebra is of the form $\mathfrak{g}=\mathfrak{g}_{1}\oplus\dots\oplus\mathfrak{g}_{n}$, where each $\mathfrak{g}_{i}$ is either one-dimensional abelian or the compact real form of a complex simple Lie algebra. We will therefore specify $G$ in terms of its Lie algebra by listing the summands in such a decomposition: For each $\mathfrak{g}_{i}$, we first record in a single bit whether it is abelian or not; in the latter case, we also specify the Dynkin diagram by giving its type ($A$–$D$, or one of the five exceptional families) and rank (in unary). Thus $\langle\mathfrak{g}\rangle=\Omega(R)$, where $R$ is the rank of $\mathfrak{g}$ (i.e., the dimension of a maximal torus of $G$).

Finally, to specify the highest weight $\lambda$ we likewise list its coefficients with respect to the basis fixed above (in binary), and the integer $k>0$ is also specified in binary.

2 Monomial bases and representation matrices

To generalize our algorithms in section 2 to the general case, it will be necessary to perform various Lie-theoretic computations, such as determining the multiset of weights $\Phi(M)$ as well as computing representation matrices of the Lie algebra representation on $M$. In this section we will explain how this can be done in polynomial time. More precisely, we will establish the following results, which may be of independent interest:

Given $G$ and $M$ as specified in section 3.1, the multiset of weights $\Phi(M)$ can be computed in polynomial time (as integer vectors with respect to the basis fixed at the beginning of section 3).

Given $G$ and $M$ as specified in section 3.1, there exists a basis of weight vectors, indexed by $\Phi(M)$, such that the representation matrix of any of the basis vectors of $i\mathfrak{g}$ fixed at the beginning of section 3 are rational and can be computed in polynomial time.

It is plain that the set of negative roots $N(G)$ can also be computed in polynomial time.

For the classical Lie groups, Lemmas 7 and 8 can be established using well-known properties of Gelfand-Tsetlin or Molev patterns . We will give a different proof, based on Lakshmibai’s notion of a monomial basis of an irreducible representation , which can be understood as a generalization of the Gelfand-Tsetlin basis to general semisimple complex Lie algebras. This allows for a uniform proof of Lemma 7 for all types, including the exceptional Lie groups. Moreover, our proof of Lemma 8 for the exceptional Lie groups relies crucially on using monomial bases in order to reduce to type $A_{n}$.

Given $G$ and $M=M_{\lambda}$ as specified in section 3.1, the set of monomials $\mathcal{M}_{\lambda}$ can be constructed in polynomial time.

If $\mathfrak{g}$ is the compact real form of simple Lie algebra and $M$ is irreducible then this follows directly from Lemma 9: First compute $\mathcal{M}_{\lambda}$ and then add the weight $\beta(x)$ of $\pi(x)v_{\lambda}$ for all $x\in\mathcal{M}_{\lambda}$ into the multiset. If $\mathfrak{g}$ is one-dimensional abelian and $M$ irreducible then there is only a single weight, which we already know from the specification of $M$. If $\mathfrak{g}=\mathfrak{g}_{1}\oplus\dots\oplus\mathfrak{g}_{n}$ is a direct sum of such Lie algebras and $M$ irreducible, then any irreducible representation is a tensor product of irreducible $\mathfrak{g}_{i}$-representations for $i=1,\dots,n$, and the multiset of weights can be identified with the Cartesian product of the multiset of weights of its constituents, which can be computed in polynomial time. Finally, if $M$ is reducible we apply the above procedure to each irreducible summand in its specification.

3 Inequalities for moment polytopes

For each root $\alpha$, we had defined a basis vector $e_{\alpha}\in i\mathfrak{g}$ in the corresponding root space. Let $E_{\alpha}$ denote the linear operator given by the (complexified) representation of the Lie algebra of $G$ on $M$. We will call $E_{\alpha}$ the root operator corresponding to the root $\alpha$.

Admissibility: The points in $\Phi(H=z)$ span an affine hyperplane in $i\mathfrak{t}^{*}$.

Determinant condition: Consider a weight vector $\psi_{j}$ of weight $\varphi_{j}\in\Phi(H=z)$. Its image under a root operator $E_{\alpha}$ for $\alpha\in N(H<0)$ is necessarily a weight vector of some weight $\varphi_{j}+\alpha\in\Phi(H<z)$. Thus we can write

whereby we obtain a matrix $D_{H,z,j}$ whose rows are indexed by integers $i$ with $\varphi_{i}\in\Phi(H<z)$ and whose columns are indexed by roots $\alpha\in N(H<0)$. Let $D_{H,z}$ denote the polynomial matrix

in variables $X_{j}$. By the trace condition, $D_{H,z}$ is a square matrix, so that we can form the determinant polynomial $d_{H,z}:=\det D_{H,z}$, and the condition is that $d_{H,z}$ should be non-zero.

As in section 2.1, we observe that the number of Ressayre elements is finite (up to overall rescaling), and – assuming that $\Delta_{G}(M)$ is maximal-dimensional – we have the following description of the moment polytope in terms of finitely many inequalities :

We will call a facet of $\Delta_{G}(M)$ non-trivial if it is not a defining inequality of the Weyl chamber, i.e., if it is not of the form $\lambda(h_{\alpha})>0$ for any of the simple coroots $h_{\alpha}$. Equation 11 implies that any non-trivial facet is necessarily given by a Ressayre element.

4 MomentPolytope is in coNP

The algorithm proceeds as follows: We first check the conditions in section 3.3 to verify that $(H,z)$ is a Ressayre element for $\Delta_{G}(M)$:

Trace condition: As there are no more than $O(\langle G\rangle^{2})$ negative roots and $\dim M=O(\langle M\rangle)$ weights, each of which lives in a space of dimension $\dim T=O(\langle G\rangle)$ and can be constructed efficiently (Lemma 7), both cardinalities can be computed and compared in polynomial time.

Determinant: We construct the matrix $D_{H,z}(p)$ defined in Eq. 10 for $X=p$. The matrix is of polynomial size and can be constructed efficiently (Lemma 8). We can therefore compute its determinant $d_{H,z}(p)$ exactly in polynomial time. We accept if and only if $d_{H,z}(p)\neq 0$.

At this point we are sure that $(H,z)$ defines a non-trivial facet of the moment polytope (the trivial inequalities are automatically satisfied since $\lambda$ is a highest weight and therefore an element of the positive Weyl chamber $i\mathfrak{t}^{*}_{+}$). In the last step of the algorithm, we verify that this facet indeed separates $\lambda/k$ from the polytope by checking that $H\cdot\lambda<kz$. It is clear that the algorithm will accept only if $\lambda/k\not\in\Delta_{G}(M)$.

We will now show that, conversely, if $\lambda/k\not\in\Delta_{G}(M)$ then there always exists a polynomial-sized certificate $(H,z,p)$ such that the algorithm accepts. For this, we derive the following estimates:

Let $\varphi\in\Phi(M)$. Then $\lVert\varphi\rVert_{\infty}\leq 2^{\langle M\rangle}$, where we think of $\varphi$ as an integer vector with respect to the basis of $\Lambda^{*}_{G}$ fixed at the beginning of section 3.

We may assume that $\mathfrak{g}$ is simple and that $M$ is an irreducible representation of highest weight $\nu$. In this case, $\varphi$ is specified with respect to the basis of fundamental weights, i.e., the coefficients of $\varphi$ are given by $\varphi(h_{\alpha})$ where $\alpha$ ranges over the simple coroots. To bound $\varphi(h_{\alpha})$, we use the classical fact that the convex hull of the weights $\Phi(M)$ is equal to the convex hull of the Weyl group orbit $W\cdot\nu$ of the highest weight (e.g., [20, Theorem 7.41]). Therefore,

where the last maximization is over all simple coroots $h_{\beta}$. This shows that $\lVert\varphi\rVert_{\infty}\leq\lVert\nu\rVert_{\infty}$. As $M$ is specified in terms of the coefficients of the highest weight $\nu$ given in binary, this shows that

Any non-trivial facet of $\Delta_{G}(M)$ can be described by a Ressayre element $(H,z)$ with

where we think of $H$ as an integer with respect to the basis of $\Lambda_{G}$ fixed at the beginning of section 3.

Note that we have $R$ equations for $R+1$ unknowns, and the absolute value of the coefficients is at most $2^{\langle M\rangle}$ by Lemma 10 above. Therefore, Siegel’s lemma ensures that there exists an integral solution with

Since $R\leq\langle G\rangle$ we obtain the claim of the lemma.

The upshot of Lemma 11 is the following: If $\lambda/k\not\in\Delta_{G}(M)$ then there exists a non-trivial facet separating it from the moment polytope. Lemma 11 tells us that any such facet can be encoded by some Ressayre element $(H,z)$ that can be specified using no more than $O(\langle G\rangle^{2}(\log\langle G\rangle+\langle M\rangle))$ bits. Indeed, $(H,z)$ consists of $\dim T+1=O(\langle G\rangle)$ coefficients, each of which requires $O(\langle G\rangle(\log\langle G\rangle+\langle M\rangle))$ bits.

Now consider the determinant polynomial $d_{H,z}$, which is a multivariate polynomial of degree $\#\Phi(H<z)\leq\dim M\leq\langle M\rangle$ in $\#\Phi(H=z)\leq\dim M\leq\langle M\rangle$ variables. As before, we can use the Schwartz-Zippel lemma to deduce the existence of a point $p\in\{0,\dots,\langle M\rangle\}^{\#\Phi(H=z)}$ such that $d_{H,z}(p)\neq 0$. Note that $p$ can be encoded using no more than $O(\langle M\rangle\log\langle M\rangle)$ bits.

We have thus obtained a polynomial-sized certificate $(H,z,p)$ that will be accepted by the algorithm. We conclude that the problem MomentPolytope is in $\coNP$.

5 MomentPolytope is in NP

We now show that MomentPolytope is also in $\NP$. As in the case of the Kronecker polytope, we will use the geometric description from . For any non-zero vector $\psi\in M$, define its image under the moment map $\mu(\psi)\in i\mathfrak{g}^{*}$ by the following formula:

where $\pi$ denotes the (complexified) representation of the Lie algebra of $G$ on $M$. Let $r(\psi)$ denote the unique point of intersection of the coadjoint $G$-orbit through $\mu(\psi)$ with the positive Weyl chamber $i\mathfrak{t}^{*}_{+}$. Then we have the following characterization of the moment polytope :

Here, we think of the highest weight $\lambda\in i\mathfrak{t}^{*}$ as an element in $i\mathfrak{g}^{*}$ by extending by zero on the root spaces.

For any $x\in i\mathfrak{g}$, we have from Eqs. 13 and 4 that

where $\lVert\pi(x)\rVert$ denotes the operator norm of $\pi(x)$. Therefore,

To compute the right-hand side maximum, we recall that $\lVert-\rVert_{i\mathfrak{g}}$ is invariant under the adjoint action, the operator norm is (in particular) invariant under conjugation by unitaries, and $\pi$ is correspondingly equivariant, so that we may restrict the maximization to $x\in i\mathfrak{t}$. Then $\pi(x)$ acts as a multiplication operator in the weight basis, multiplying weight vectors of weight $\varphi$ by $\varphi(x)$. We may assume without loss of generality that $M$ is an irreducible representation with some highest weight $\nu$, so that

where we have again used that the convex hull of weights is equal to the convex hull of the Weyl group orbit of the highest weight (cf. the proof of Lemma 10). It follows that

where the last estimate follows from observing that the highest weight $\nu$ is specified in terms of its coefficients (in binary) with respect to the basis vectors of the weight lattice, which have norm $\Theta(1)$. The asserted bound follows from plugging Eq. 17 back into Eq. 16.

As a direct consequence of Lemma 12, the truncation to $b$ bits leads to an error of at most

Comparing with Eq. 15, we find that it suffices to choose $b=O(\log k+\langle G\rangle(\log\langle G\rangle+\langle M\rangle)$ bits of precision to produce a certificate that the algorithm accepts. This is polynomial in the size of the problem instance.

Conversely, let us assume that in fact $\lambda/k\not\in\Delta_{G}(M)$. We will use the following lemma:

Let $\lambda\in\Lambda^{*}_{G}$ and $k>0$. Then, if $\lambda/k\not\in\Delta_{G}(M)$, it has $\lVert-\rVert_{i\mathfrak{g}^{*}}$-distance at least

Consider a non-trivial facet that separates $\lambda/k$ from $\operatorname{Kron}(m)$. According to Lemma 11, any such facet can be described by some Ressayre element $(H,z)$ satisfying Eq. 12. We can therefore lower-bound the distance of $\lambda/k$ to $\Delta_{G}(m)$ by

Recall that we may also think of $H$ as an integer vector with respect to the basis vectors fixed at the beginning of section 3. As the latter have norm $\Theta(1)$, we obtain that $\lVert H\rVert_{i\mathfrak{g}}\leq\sqrt{\langle G\rangle}\lVert H\rVert_{\infty}$. Together with the upper bound Eq. 12, we find that

where the second inequality is [42, Lemma 4.10]. In view of the acceptance condition in Eq. 15, we find that our algorithm will therefore never accept if $\lambda/k\not\in\operatorname{Kron}(m)$. We conclude that the problem KronPolytope is in $\NP$. Sections 3.4 and 3.5 together establish Theorem 2.

Acknowledgments

We acknowledge pleasant discussions with Christian Ikenmeyer. We thank the Simons Institute for the Theory of Computing, the American Institute of Mathematics, and the organizers of the workshop on “Combinatorics and complexity of Kronecker coefficients”, where this work has been initiated.

References