In the algebraic metacomplexity framework we prove that the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. We use this to resolve an open question posed by Grochow, Kumar, Saks & Saraf (2017). Our result means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, it means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincaré-Birkhoff-Witt theorem for Lie algebras and on Gelfand-Tsetlin theory, for which we give the necessary comprehensive background.

Tensors play a central role in various areas of computer science and mathematics, such as algebraic complexity theory (matrix multiplication), quantum information theory (entanglement), and additive combinatorics (slice rank). Fundamental problems about tensors are strongly tied to well-known questions in computational complexity - such as the problem of determining the matrix multiplication exponent via asymptotic rank, and the stronger Strassen asymptotic rank conjecture, which has recently been intimately linked to a whole range of computational problems. Unlike matrices, which are often well understood through their rank, tensors have such intricate structure that understanding them (and aforementioned problems) requires information of a more subtle nature. The moment polytope, going back decades to work in symplectic geometry, invariant theory, and representation theory, is a mathematical object associated to any tensor that collects such "rank-like"information. Their relevance has become apparent in several areas: (1) through applications in geometric complexity theory (GCT), (2) in the construction of functions in Strassen's asymptotic spectrum of tensors, (3) as entanglement polytopes in quantum information theory, and (4) in optimization via scaling algorithms. Despite their fundamental role and interest from many angles, little is known about these polytopes, and in particular for tensors beyondC2λ-λ.,⊗2λ-λ.,⊗2 andC2λ-λ.,⊗2λ-λ.,⊗2λ-λ.,⊗2 only sporadically have they been computed. Even less is known about the polytopes' inclusions and separations (which are particularly relevant for applications). We give a new algorithm for computing moment polytopes of tensors (and in fact moment polytopes for a natural general class of reductive algebraic groups) based on a mathematical characterization of moment polytopes by Franz. This algorithm enables us to compute moment polytopes of tensors of dimension an order of magnitude larger than previous methods, allowing us to compute with certainty, for the first time, all moment polytopes of tensors inC3λ-λ.,⊗3λ-λ.,⊗3, and with high probability those inC4λ-λ.,⊗4λ-λ.,⊗4. Towards an open problem in geometric complexity theory, we prove (guided by moment polytopes computed with our algorithm) separations between the moment polytopes of matrix multiplication tensors and unit tensors, showing in particular that the matrix multiplication moment polytopes are not maximal (i.e., not equal to the corresponding Kronecker polytopes). As a consequence of the above, we obtain a no-go result for a certain operational characterization of moment polytope inclusion, by proving that Strassen's asymptotic restriction on tensors does not imply moment polytope inclusion. Finally, based on our algorithmic observations, we construct explicit (concise) non-free tensors in every formatCn λ-Cn λ-Cn, thus solving a "hay in a haystack"problem for this generic property that plays an important role in Strassen's theory of asymptotic spectra.