Algebraic Metacomplexity and Representation Theory

van den Berg, Maxim; Dutta, Pranjal; Gesmundo, Fulvio; Ikenmeyer, Christian; Lysikov, Vladimir

doi:10.4230/LIPIcs.CCC.2025.26

Algebraic Metacomplexity and Representation Theory

Maxim van den Berg

Ruhr University Bochum, Germany
University of Amsterdam, The Netherlands Pranjal Dutta

Nanyang Technological University, Singapore Fulvio Gesmundo

University of Toulouse, France Christian Ikenmeyer

University of Warwick, UK Vladimir Lysikov

Ruhr University Bochum, Germany

Abstract

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.

Keywords and phrases:

Algebraic complexity theory, metacomplexity, representation theory, geometric complexity theory

Funding:

Maxim van den Berg: supported by the European Research Council through an ERC Starting Grant (grant agreement No. 101040907, SYMOPTIC) and the Dutch National Growth Fund (NGF) as part of the Quantum Delta NL visitor programme.

Pranjal Dutta: The work was done while PD was at the National University of Singapore, funded by NRF Singapore under the project “Computational Hardness of Lattice Problems and Implications” [NRF-NRFI09-0005].

Christian Ikenmeyer: supported by EPSRC grants EP/W014882/1 and EP/W014882/2.

Vladimir Lysikov: supported by the European Research Council through an ERC Starting Grant (grant agreement No. 101040907, SYMOPTIC).
Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

Copyright and License:

© Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo, Christian
Ikenmeyer, and Vladimir Lysikov; licensed under Creative Commons License CC-BY 4.0

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Algebraic complexity theory

Acknowledgements:

We are grateful to Alessandro Danelon and Nutan Limaye for helpful discussions. We thank anonymous referees for their comments, and especially for bringing our attention to Open Question 2 in [40].

DOI:

10.4230/LIPIcs.CCC.2025.26

Event:

40th Computational Complexity Conference (CCC 2025)

Editors:

Srikanth Srinivasan

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Strong computational complexity lower bounds are often difficult to prove, for many different complexity measures. In most cases, the inability to prove lower bounds can be explained by barrier results such as the Relativization barrier due to Baker, Gill and Solovay [5], the Algebrization barrier due to Aaronson and Wigderson [1] and the Natural Proofs barrier due to Razborov and Rudich [66]. Metacomplexity studies the complexity of computing various complexity measures, such as the minimum circuit complexity of a function. One eventual goal of the metacomplexity program is to understand mathematically why lower bounds are hard to prove. In this paper, we study metacomplexity in the algebraic circuit complexity setup from a representation-theoretic viewpoint.

Algebraic complexity focuses on proving complexity lower bounds for various problems related to the computation of multivariate polynomials and rational functions. Prominent examples include the discrete Fourier transform, matrix multiplication, and solving systems of linear equations; see [14]. In algebraic complexity, the main model of computation is the algebraic circuit, which is a labeled directed graph encoding an algorithm to evaluate a polynomial. Most polynomials require large algebraic circuits; however, exhibiting explicit ones with such property is difficult. Valiant’s flagship conjecture [71], known as $\mathsf{VP}\neq\mathsf{VNP}$ , states that the algebraic circuit complexity of the permanent polynomial $\mathsf{per}_{d}(x_{1,1},\dots,x_{d,d})=\sum_{\pi\in\mathfrak{S}_{d}}\prod_{i=% 1}^{d}x_{i,\pi(i)}$ is not polynomially bounded as a function of $d$ . This conjecture is an algebraic analogue of the $\mathsf{P}\neq\mathsf{NP}$ conjecture: indeed, the permanent of the adjacency matrix of a bipartite graph counts the number of perfect matchings, which is a $\#\mathsf{P}$ -hard problem.

Many current proof techniques in algebraic complexity theory are implicitly based on metapolynomials. Examples of such techniques are rank methods, dating back to [70], and used more recently in complexity theory both for polynomials [62, 55] and for tensors [69, 54], methods based on geometric features [53, 36], and the geometric complexity program [60, 59]. We refer to Section 2.2 for a more extensive discussion. Informally, metapolynomials are polynomials whose variables are coefficients of polynomials. The concept dates back to resultants and invariants of forms [20, 70], while the term “metapolynomial” was coined in [67] and made popular in [40]. A classical example is the metapolynomial $b^{2}-4ac$ in the coefficients of a univariate degree $2$ polynomial $ax^{2}+bx+c$ , which vanishes exactly when the two roots of the polynomial coincide. Grochow pointed out in [39] that for many border complexity measures the complexity lower bounds can without loss of generality be proved by metapolynomials that lie in separating modules, or are isotypic, or are highest weight vectors. These are all closely related concepts (and we prove analogous results for all of them), where being isotypic is the most natural one because it does not depend on choosing any bases. Being a homogeneous metapolynomial is the same as being isotypic with respect to the action of $1\times 1$ matrices. Being isotypic also generalizes the property of being invariant under the special linear group. While invariants can have large circuit size, see [34], we prove that not all separating isotypic metapolynomials have large circuit size, unless all separating metapolynomials have large circuit size. More precisely, we prove that without loss of generality one may assume the metapolynomial to be isotypic, or to be a highest weight vector, or to lie in a separating module, with only a quasipolynomial blowup in the circuit size. We use this to answer Open Question 2 in [40] by proving that all metapolynomials that lie in an irreducible representation have the same circuit complexity up to quasipolynomial blowup, see Corollary 1.2.

Our result reduces the search space for lower bounds from all homogeneous metapolynomials to the isotypic metapolynomials, which is a technique for example used in [2, 15, 16, 43, 3, 23, 11]. In particular the large-scale cluster computations in [3, 23, 11] would be infeasible without this search space reduction. For example, [43] reduces the search space for proving that the border complexity of the $2\times 2$ matrix multiplication tensor is 7 to a 4-dimensional linear subspace of isotypic metapolynomials in a $\binom{64+20-1}{20}=8,179,808,679,272,664,720$ -dimensional space of homogeneous degree 20 metapolynomials on $4\times 4\times 4$ tensors. On the reduced search space, the problem is then easily solved by linear algebra. This specific approach was used in [8] to prove that the border support rank of the $2\times 2$ matrix multiplication tensor is 7. To this date, this is the only proof of this fact. Similar methods are used in [63, 37], where the polynomials of interest are invariants for the action of a special linear group: this information is crucially used to reduce the search space and determine the polynomial via interpolation methods on a small space. These are finite results, but the techniques work in the asymptotic settings as well, for example for lower bounds on the rank of matrix multiplication as in [15, 16], or the best known lower bound for the border determinantal complexity of the permanent [53].

Our result also points to potential future lower bounds: Our method can be used to extract isotypic metapolynomials for example from rank-based lower bounds proofs, and the obtained metapolynomials give at least the same lower bounds, but potentially better ones. It is conceivable that these metapolynomials can be adjusted to not be affected by barriers for rank methods [26, 33].

Our procedure uses explicit efficient circuit constructions and hence makes a contribution to algorithmic representation theory that is of independent interest.

Metapolynomials

We work over the field $\mathbb{C}$ of complex numbers, and the set $\{x_{1},x_{2},\ldots\}$ of variables. For every sequence $\bm{i}$ of nonnegative integers with $\sum_{j}i_{j}<\infty$ , a monomial $x^{\bm{i}}$ is the finite product of variables $x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots$ , and a polynomial $f$ is a finite linear combination of monomials. For every monomial $x^{\bm{i}}=x_{1}^{i_{1}}x_{2}^{i_{2}}\cdots$ , define a metavariable $c_{\bm{i}}$ . A metavariable $c_{{\bm{i}}}$ has degree 1, and it has weight $\bm{i}$ . Finite products of metavariables are called metamonomials, and finite linear combinations of metamonomials are called metapolynomials. The weight of a metamonomial is the sum of the weights of its metavariables. If every metamonomial in a metapolynomial $\Delta$ has the same weight, then $\Delta$ is called a weight metapolynomial (and the zero metapolynomial has every weight). For a fixed weight $w$ the metapolynomials of that weight form a vector space, the weight $w$ space. Every metapolynomial can be written as a unique sum of weight metapolynomials of different weights. A metapolynomial is called affine linear if all its metamonomials have degree at most 1, i.e., are just a metavariable or a constant. Every metapolynomial $\Delta$ can be evaluated at any polynomial $f$ by assigning to each metavariable the coefficient of the corresponding monomial in $f$ . For example, the discriminant of a degree two homogeneous polynomial in two variables $c_{20}x_{0}^{2}+c_{11}x_{0}x_{1}+c_{02}x_{1}^{2}$ is the metapolynomial $\Delta=c_{11}^{2}-4c_{20}c_{02}$ . It is a classical fact that $\Delta(f)=0$ if and only if $f=\ell^{2}$ for some homogeneous linear polynomial $\ell=\alpha_{0}x_{0}+\alpha_{1}x_{1}$ . In principle, metapolynomials can involve metavariables that correspond to monomials of different degrees, but for our purposes it is sufficient to consider the case where all metavariables correspond to monomials of the same degree $d$ , see Remark 1.3. Every such metapolynomial can be decomposed uniquely as a sum of its homogeneous degree $\delta$ components, and we call a homogeneous degree $\delta$ metapolynomial a metapolynomial of format $(\delta,d,k)$ if all its metavariables only involve the variables $x_{1},\ldots,x_{k}$ .

Algebraic circuits

In this paper, we are mostly interested in the algebraic circuit size of metapolynomials. Algebraic circuits for metapolynomials are defined in the same way as for usual polynomials, as follows.

An algebraic circuit is a directed acyclic graph in which each vertex has indegree $0$ or $2$ . Every indegree 0 vertex is called input gate and it is labelled by an affine linear metapolynomial; every indegree 2 vertex is called a computation gate and it is labeled by either “ $+$ ” or “ $\times$ ”; every edge is labeled by a complex number, which is assumed to be 1 if this scalar is omitted; there is exactly one vertex of outdegree 0. An algebraic circuit computes a metapolynomial at every vertex by induction over the directed acyclic graph structure (the labels on the edges rescale the computed values), i.e., if the values computed at the children of a gate $v$ are $\Delta_{1}$ and $\Delta_{2}$ and the incoming edges to $v$ are labelled with $\alpha_{1}$ and $\alpha_{2}$ , respectively, then the value computed at $v$ is $\alpha_{1}\Delta_{1}+\alpha_{2}\Delta_{2}$ or $\alpha_{1}\alpha_{2}\Delta_{1}\Delta_{2}$ , depending on whether $v$ is labelled with a “ $+$ ” or a “ $\times$ ”. An algebraic circuit computes the metapolynomial computed at its outdegree 0 vertex. The size of a circuit is the total number of its vertices. The algebraic circuit complexity of a metapolynomial is the minimum size of an algebraic circuit computing it. For example, Figure 1 shows that the algebraic circuit complexity of the discriminant is at most 6. Algebraic circuits for polynomials are defined analogously.

Figure 1: An algebraic circuit computing the discriminant

\Delta=c_{11}^{2}-4c_{20}c_{02}

.

Representation Theory

Let $\mathbb{N}$ denote the set of natural numbers including zero. A partition $\lambda=(\lambda_{1},\lambda_{2},\ldots)$ is a finite sequence of non-increasing natural numbers. Let $\ell(\lambda)=\max\{j\mid\lambda_{j}\neq 0\}$ . We define $\lambda_{j}=0$ for all $j>\ell(\lambda)$ . Write $|\lambda|:=\sum_{j}\lambda_{j}$ , and say that $\lambda$ is a partition of $|\lambda|$ of length $\ell(\lambda)$ . In this case we write $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}\,}{\scalebox{1.2}[0.7]{ $% \vdash$}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}\,}{\scalebox{0.5}{% \scalebox{1.2}[0.7]{$\vdash$}}\,}|\lambda|$ or $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}_{\ell(\lambda)}\,}{\scalebox% {1.2}[0.7]{ $\vdash$}_{\ell(\lambda)}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$% \vdash$}}_{\ell(\lambda)}\,}{\scalebox{0.5}{\scalebox{1.2}[0.7]{$\vdash$}}_{% \ell(\lambda)}\,}|\lambda|$ depending on whether the length is relevant. For example, $\lambda=(4,2,2)$ is a partition of $8$ of length $3$ , i.e., $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}_{3}\,}{\scalebox{1.2}[0.7]{ % $\vdash$}_{3}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}_{3}\,}{% \scalebox{0.5}{\scalebox{1.2}[0.7]{$\vdash$}}_{3}\,}8$ . The Young diagram of a partition $\lambda$ is a top-left justified array of boxes with $\lambda_{j}$ many boxes in row $j$ . For example, the Young diagram for $(4,2,2)$ is . A Young tableau $T$ is a filling of the boxes of a Young diagram with positive integer numbers. The partition $\lambda$ is called the shape of $T$ . For example, is a Young tableau of shape $(4,2,2)$ . A Young tableau is semistandard if the numbers within each row from left to right are non-decreasing, and the numbers within each column from top to bottom are strictly increasing, for example . For each partition $\lambda$ there exists a unique superstandard tableau, that is, the tableau with only the number $j$ in row $j$ , e.g., .

The group $\textnormal{GL}_{k}$ acts on the space $\mathbb{C}[x_{1},\ldots,x_{k}]_{d}$ of homogeneous polynomials on $\mathbb{C}^{k}$ of degree $d$ by linear change of coordinates. This action induces, again by linear change of coordinates, an action on the space of metapolynomials with format $(\delta,d,k)$ for every $\delta$ . For instance, the change of basis swapping the two coordinates on $\mathbb{C}^{2}$ , defines the change of basis on $\mathbb{C}[x_{0},x_{1}]_{2}$ obtained by exchanging $x_{0}$ and $x_{1}$ . This induces a linear change of coordinates on $\mathbb{C}[c_{20},c_{11},c_{02}]$ which exchanges $c_{20}$ and $c_{02}$ and leaves $c_{11}$ fixed. The discriminant $c_{11}^{2}-4c_{02}c_{20}$ is sent to itself by this change of coordinates. More precisely the group actions are defined as follows. For every homogeneous degree $d$ polynomial $f$ in $k$ variables and every $g\in\textnormal{GL}_{k}$ , the polynomial $g\cdot f$ is defined by $(g\cdot f)(x)=f(g^{-1}x)$ for every $x\in\mathbb{C}^{k}$ . Similarly, for every format $(\delta,d,k)$ metapolynomial $\Delta$ , the metapolynomial $g\cdot\Delta$ is defined by $(g\cdot\Delta)(f)=\Delta(g^{-1}\cdot f)$ for every homogeneous degree $d$ polynomial $f$ . The details about this action are provided in Section 4.

The vector space of metapolynomials of format $(\delta,d,k)$ is closed under this action of $\textnormal{GL}_{k}$ , and it decomposes into a direct sum of subspaces which are also closed under the action of $\textnormal{GL}_{k}$ : these subspaces are called isotypic components and they are in one to one correspondence with partitions $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}_{k}\,}{\scalebox{1.2}[0.7]{ % $\vdash$}_{k}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{% \scalebox{0.5}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{\delta d}$ . The summand corresponding to the partition $\lambda$ is called the $\lambda$ -isotypic component. This is called the isotypic decomposition. Each $\lambda$ -isotypic component decomposes even further into a direct sum of subspaces with one summand for each semistandard tableau $T$ of shape $\lambda$ . We call the component for $T$ the $T$ -isotypic component. If $V$ is $\lambda$ -isotypic and irreducible (i.e., has no nontrivial subrepresentations), then $\lambda$ is called the isomorphism type of $V$ , and each $T$ -isotypic component of $V$ is 1-dimensional. If $T$ is a superstandard tableau of shape $\lambda$ , then the corresponding $T$ -isotypic component is called the highest weight metapolynomial vector space of weight $\lambda$ . Equivalently, a highest weight vector of weight $\lambda$ is a metapolynomial $\Delta$ with $g\cdot\Delta=t_{1}^{\lambda_{1}}\cdots t_{k}^{\lambda_{k}}\Delta$ , for every $g\in\textnormal{GL}_{k}$ upper triangular with $t_{1},\ldots,t_{k}$ on the main diagonal. The $\lambda$ -isotypic component is known to be the linear span of the union of the orbits of all its highest weight vectors.

For example (not easily verifiable by hand, see Example 5.4), the space of metapolynomials of format $(\delta,d,k)=(3,2,3)$ decomposes into three nonzero isotypic components, corresponding to partitions $(6,0,0)$ , $(4,2,0)$ and $(2,2,2)$ of $\delta\cdot d=6$ . The isotypic component $(4,2,0)$ further decomposes into three $T$ -isotypic components for the three semistandard tableaux of shape $(4,2,0)$ : , , . The metapolynomial $\Delta=c_{200}c_{020}c_{002}$ can be written according to this decomposition as

$\displaystyle 60\,\Delta$	$\displaystyle=$	$\displaystyle 2\big{(}c_{101}^{2}c_{020}+2c_{110}c_{101}c_{011}+c_{200}c_{011}% ^{2}+c_{110}^{2}c_{002}+2c_{200}c_{020}c_{002}\big{)}$
	$\displaystyle+$	$\displaystyle\Big{[}\ 2\big{(}-c_{020}c_{101}^{2}-2c_{011}c_{101}c_{110}+4c_{0% 02}c_{110}^{2}-c_{011}^{2}c_{200}+8c_{002}c_{020}c_{200}\big{)}$
	$\displaystyle+$	$\displaystyle\phantom{\Big{[}\ }0$
	$\displaystyle+$	$\displaystyle\phantom{\Big{[}\ }5\big{(}c_{020}c_{101}^{2}-c_{011}c_{101}c_{11% 0}-c_{002}c_{110}^{2}+c_{011}^{2}c_{200}+4c_{002}c_{020}c_{200}\big{)}\ \Big{]}$
	$\displaystyle+$	$\displaystyle 5\big{(}-c_{101}^{2}c_{020}+c_{110}c_{101}c_{011}-c_{200}c_{011}% ^{2}-c_{110}^{2}c_{002}+4c_{200}c_{020}c_{002}\big{)},$

where the five summands from top to bottom are -isotypic, -isotypic, -isotypic, -isotypic, and -isotypic, respectively. The fifth summand is a highest weight vector, because is superstandard. All summands have weight (2,2,2), because $\Delta$ has weight (2,2,2).

Theorem 1.1 (Main theorem).

Let $\Delta\colon\mathbb{C}[x_{1},\dots,x_{k}]_{d}\to\mathbb{C}$ be a metapolynomial of format $(\delta,d,k)$ computed by an algebraic circuit of size $s$ . Then

1.

For every weight $\mu\in\mathbb{N}^{k}$ , $|\mu|=d\delta$ , the projection of $\Delta$ onto the weight space of weight $\mu$ can be computed by a circuit of size $O(s(\delta d)^{2k^{3}})$ .
2.

For every partition $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}\,}{\scalebox{1.2}[0.7]{ $% \vdash$}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}\,}{\scalebox{0.5}{% \scalebox{1.2}[0.7]{$\vdash$}}\,}d\delta$ the projection of $\Delta$ onto the $\lambda$ -isotypic component can be computed by a circuit of size $O(sk^{2k^{2}}(\delta d)^{2k^{3}})$ .
3.

For every partition $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}\,}{\scalebox{1.2}[0.7]{ $% \vdash$}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}\,}{\scalebox{0.5}{% \scalebox{1.2}[0.7]{$\vdash$}}\,}d\delta$ the projection of $\Delta$ onto the highest weight space of weight $\lambda$ can be computed by a circuit of size $O(s(k+1)^{2k^{2}}(\delta d)^{2k^{3}})$ .
4.

For every semistandard tableau $T$ of shape $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}\,}{\scalebox{1.2}[0.7]{ $% \vdash$}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}\,}{\scalebox{0.5}{% \scalebox{1.2}[0.7]{$\vdash$}}\,}d\delta$ the projection of $\Delta$ onto the $T$ -isotypic space can be computed by a circuit of size $O(sk^{2k^{2}}(\delta d)^{2k^{4}})$ .

In all applications of Theorem 1.1, we will always have that $k$ is logarithmic in the number of metavariables, which we explain in Section 2.5. Open Question 2 in [40] asks: given a sequence of irreducible representations of metapolynomials, what is the sequence of metapolynomials in it that has the lowest circuit complexity? Theorem 1.1 answers this question in a very satisfying way: Every such sequence of metapolynomials has the same circuit complexity up to quasipolynomial blowup, as seen in the following corollary.

Corollary 1.2.

Let $s$ be the smallest circuit complexity of a nonzero metapolynomial in an irreducible $\textnormal{GL}_{k}$ -representation $V$ of type $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}\,}{\scalebox{1.2}[0.7]{ $% \vdash$}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}\,}{\scalebox{0.5}{% \scalebox{1.2}[0.7]{$\vdash$}}\,}\delta d$ . Then every metapolynomial in $V$ has circuit complexity at most $O(sk^{2k^{2}}(\delta d)^{2k^{4}+k^{2}})$ .

Proof.

If $V$ is irreducible of isomorphism type $\lambda$ , then it decomposes into a direct sum of $1$ -dimensional $T$ -isotypic components, where $T$ ranges over all semistandard tableaux of shape $\lambda$ . Take a nonzero metapolynomial $\Delta$ with minimal complexity in $V$ and apply a generic basis change, i.e., apply a generic element of $\textnormal{GL}_{k}$ . Then independently project the result onto all $T$ -isotypic components. We claim that since the basis change was generic, the projections are nonzero, and therefore form a basis of $V$ . In fact, we can be more precise about how we pick the basis change element $g\in\textnormal{GL}_{k}$ . For every semistandard tableau $T$ , define $X_{T}:=\{g\in\textnormal{GL}_{k}\mid g\Delta\text{ has zero $T$-isotypic % projection}\}$ . Such $X_{T}$ is Zariski closed in $\textnormal{GL}_{k}$ , but it is not the whole $\textnormal{GL}_{k}$ , otherwise the linear span of $\textnormal{GL}_{k}\Delta$ would be a nontrivial subrepresentation of the irreducible representation $V$ . Therefore the finite union $X:=\bigcup_{T}X_{T}$ is also a proper Zariski closed subset of $V$ , and its complement $\textnormal{GL}_{k}\setminus X$ is a nonempty Zariski open subset. If we pick $g\in\textnormal{GL}_{k}\setminus X$ , then the projections of $g\Delta$ to every $T$ -isotypic space are nonzero. Moreover, by Theorem 1.1, all these projections have complexity at most $O(sk^{2k^{2}}(\delta d)^{2k^{4}})$ . But the dimension of $V$ equals the number of semistandard tableaux of shape $\lambda$ with entries $1,\ldots,k$ , which is at most $(\delta d)^{k^{2}}$ (each tableaux has $k$ rows, and each row has length at most $\delta d$ , so can be filled in at most $(\delta d)^{k}$ ways). $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 1.3.

In general, algebraic complexity classes are defined for possibly nonhomogeneous polynomials. In this paper, we assume that polynomials and metapolynomials are homogeneous. However, one can lift the results to the nonhomogeneous setting as follows.

A polynomial $f(x_{1},\ldots,x_{k})$ is called homogeneous if all its monomials have the same degree. For $d\geq\deg(f)$ , define the degree $d$ homogenization

f^{\sharp d}(x_{0},x_{1},\ldots,x_{k}):=x_{0}^{d}f(x_{1}/x_{0},\ldots,x_{k}/x_% {0}).

If $f$ has an algebraic circuit of size $s$ , then $f^{\sharp d}$ has an algebraic circuit of size at most $O(sd)$ : $s(d+1)$ for extracting the homogeneous parts of $f$ via interpolation, $d$ operations to compute all values $x_{0},x_{0}^{2},\ldots,x_{0}^{d}$ , and another $d+1$ for multiplying the homogeneous components with the correct powers of $x_{0}$ , and a final $d$ for adding up the results. Given a metapolynomial $\Delta$ that does not involve $x_{0}$ , define $\Delta^{\sharp d}$ by replacing every metavariable $c_{\bm{i}}$ with $c_{(d-|\bm{i}|,i_{1},i_{2},\ldots)}$ , and setting every metavariable $c_{\bm{i}}$ with $|\bm{i}|>d$ to zero. Clearly we have $\Delta^{\sharp d}(f^{\sharp d})=\Delta(f)$ , provided that $d\geq\deg(f)$ . Hence, in this paper we can always assume that $f$ is homogeneous.

Organization of the paper

In the first part of Section 2 we illustrate the motivations for studying the circuit complexity of the isotypic components and the highest weight vectors in the space of metapolynomials, in the context of algebraic complexity lower bounds and border complexity classes. In Section 2.5, based on Theorem 1.1 we prove that algebraic natural proofs can without loss of generality be assumed to be isotypic, see Theorem 2.4. Section 3 sketches the main ideas behind Theorem 1.1. In Section 4, we provide an introduction to Lie algebras, universal enveloping algebras, and their representation theory, on which the core of the proof is built. In Section 5.1, we explain the construction of the projection maps used in the proof of the main theorem; we describe the efficient circuit implementation in Section 5.2. In Appendix A, we prove the results of Section 2.5. In Appendix B, we show one part of the proof of the Poincaré–Birkhoff–Witt Theorem (Theorem 4.9); this proof is explicit and can be used to construct the projectors in Theorem 1.1.

2 Context and consequences of the main theorem

2.1 Complexity classes defined by invariant complexity measures

A p-family is a sequence of polynomials $(f_{n})_{n\in\mathbb{N}}$ for which the number of variables of $f_{n}$ and the degree of $f_{n}$ are polynomially bounded functions of $n$ . The class $\mathsf{VP}$ is the set of p-families whose algebraic circuit complexity is polynomially bounded. Valiant’s landmark conjecture is that the permanent sequence $(\mathsf{per}_{n})_{n\in\mathbb{N}}$ with $\mathsf{per}_{n}=\sum_{\sigma\in\mathfrak{S}_{n}}\prod_{i=1}^{n}x_{i,\sigma(i)}$ is not contained in $\mathsf{VP}$ , i.e., $\mathsf{VP}\neq\mathsf{VNP}$ ; for details see [14, 57, 13]. The extended conjecture states that $(\mathsf{per}_{n})\notin\mathsf{VQP}$ [12], i.e., that the algebraic circuit complexity of the permanent is not quasipolynomially bounded.

Let $\operatorname{cc}(f)$ denote the algebraic circuit complexity of the polynomial $f\in\mathbb{C}[x_{1},\ldots,x_{k}]$ . It is easy to see that $\operatorname{cc}(f)=\operatorname{cc}(g\cdot f)$ for any $g\in\textnormal{GL}_{k}$ : A circuit for $g\cdot f$ is obtained from the one for $f$ by applying $g$ at the input gates. Recall that in the definition of algebraic circuits we allow affine linear forms at the input gates. We say that the complexity measure $\operatorname{cc}$ is an invariant complexity measure. In more restrictive circuit definitions, for instance if the input gates are required to be variables, the associated circuit complexity $c^{\prime}$ might change under the action of $\textnormal{GL}_{k}$ . However, both definitions give the same class $\mathsf{VP}$ .

Several other classical classes in algebraic complexity theory can be defined as the set of p-families for which some invariant complexity measure is polynomially bounded. For example, the class $\mathsf{VF}$ is the set of p-families whose algebraic formula size is polynomially bounded; this is the smallest size of an algebraic circuit whose underlying directed graph is a tree. The class $\mathsf{VBP}$ is the set of p-families whose algebraic branching program width is polynomially bounded; we do not define this notion here, but it is an easy consequence of the definition that it is an invariant complexity measure, e.g. [68, Def. 2.2]. More classical classes can be readily defined in this way, for example the class of p-families of polynomially bounded circuit size and constant depth (still allowing arbitrary linear forms as inputs), such as $\Sigma\Pi\Sigma$ , or the class of p-families of sums of polynomially many powering gates $\Sigma\Lambda\Sigma$ . Finally, we mention $\mathsf{VNP}$ , which is the class of p-families of polynomially bounded permanental complexity: The smallest $r$ such that $f$ can be written as the permanent of an $r\times r$ matrix with affine linear entries. In all these cases, the relevant complexity measure is invariant.

Notable complexity measures that are not invariant are those related to the sparsity of the polynomial, in the sense of [49], or to restrictions on how often a variable can occur, such as read-once or read- $k$ models [27]. A non-invariant complexity measure $c^{\prime}$ can be converted into an invariant complexity measure $c$ by defining $c(f):=\min\{c^{\prime}(gf)\mid g\in\textnormal{GL}_{k}\}$ , i.e., by taking the minimum complexity over all base changes, but for some non-invariant measures this can change the corresponding complexity class. In this paper, we only study complexity classes defined by invariant measures.

2.2 Lower bounds via isotypic metapolynomials

An important problem in algebraic complexity theory concerns proving concrete lower bounds for interesting complexity measures $c$ . More precisely, given a polynomial $f_{\textup{hard}}$ and a certain integer $r$ , one aims to show $c(f_{{\textup{hard}}})>r$ or equivalently $f_{{\textup{hard}}}\notin X_{r}$ where $X_{r}=\{f\in\mathbb{C}[x_{1},\ldots,x_{k}]_{d}\mid c(f)\leq r\}$ is the set of polynomials satisfying the upper bound $r$ on the complexity measure $c(\cdot)$ . A standard approach is to determine a function $\Delta$ with the property that $\Delta(f)=0$ for every $f\in X_{r}$ and $\Delta(f_{\textup{hard}})\neq 0$ .

Several lower bound methods in complexity theory are based on this approach, and most often the function $\Delta$ is a metapolynomial. This is the case for rank methods such as the method of partial derivatives [70, 22], the method of shifted partial derivatives [41, 28], and other augmented flattening methods such as Koszul–Young flattenings [54]: in all these cases the complexity lower bound is obtained in terms of a lower bound of the rank of a matrix whose entries depend on the metavariables, or equivalently on the nonvanishing of a suitable set of minors, which are metapolynomials. Rank methods yield the recent breakthrough of [55] giving the first superpolynomial lower bounds for explicit polynomials to be computed by low-product-depth algebraic circuits in large characteristic, further extended to any field in [30]. Similarly, the current best known lower bounds for the border determinantal complexity of the permanent, as well as the one of the sum of powers, are based on a non-degeneracy condition which can be translated into the vanishing of a suitable metapolynomial [53, 52]. Finally, the algebraic branching program lower bounds discussed in [50, 36] are built on geometric conditions of the zero set of the polynomial of interest, which in turn can be translated into the vanishing of metapolynomials.

When the complexity measure $c(\cdot)$ is invariant, one can use representation theory to enhance the search for the metapolynomials yielding a separation. Our main result Theorem 1.1 shows that this enhancement is not expensive: the computational overhead is quasi-polynomial.

To illustrate the effect of our result, first consider a simpler reduction. Let $\Delta$ be a metapolynomial vanishing on $X_{r}$ such that $\Delta(f_{\textup{hard}})\neq 0$ . Write $\Delta=\sum_{i}\Delta^{(i)}$ for homogeneous metapolynomials $\Delta^{(i)}$ of degree $i$ . If $X_{r}$ is invariant under rescaling, one has $\Delta^{(i)}(X_{r})=0$ for every $i$ . On the other hand, there exists at least one $i$ such that $\Delta^{(i)}(f_{\textup{hard}})\neq 0$ . The relevant homogeneous component $\Delta^{(i)}$ can be extracted from $\Delta$ with a simple interpolation argument, and one has $\operatorname{cc}(\Delta^{(i)})\leq(\deg(\Delta)+1)\cdot\operatorname{cc}(\Delta)$ . In summary, if the lower bound $c(f_{\textup{hard}})>r$ can be proved via a metapolynomial $\Delta$ satisfying $\operatorname{cc}(\Delta)\leq s$ , then the same lower bound can be proved via a homogeneous metapolynomial $\Delta^{(i)}$ satisfying $\operatorname{cc}(\Delta^{(i)})\leq(\deg(\Delta)+1)s$ ; and even further, the homogeneous metapolynomial $\Delta^{(i)}$ can be realized as the projection of $\Delta$ onto the $i$ -th homogeneous component of the space of metapolynomials.

Theorem 1.1 shows similar results for other projections and in particular for the projection onto a specific isotypic component. Indeed, suppose $\Delta$ is a (homogeneous) metapolynomial vanishing on $X_{r}$ and such that $\Delta(f_{\textup{hard}})\neq 0$ . Write $\Delta=\sum_{\lambda}\Delta^{(\lambda)}$ as the sum of its isotypic components. If $c(\cdot)$ is an invariant complexity measure, then $X_{r}$ is invariant under the action of $\textnormal{GL}_{k}$ . In this case, one has $\Delta^{(\lambda)}(X_{r})=0$ for every $\lambda$ . On the other hand, there exists at least one $\lambda$ such that $\Delta^{(\lambda)}(f_{\textup{hard}})\neq 0$ . Theorem 1.1 provides an upper bound on the circuit complexity of $\Delta^{(\lambda)}$ in terms of the circuit complexity of $\Delta$ , showing that if the lower bound $c(f_{\textup{hard}})>r$ can be proved via a metapolynomial $\Delta$ satisfying $\operatorname{cc}(\Delta)\leq s$ , then the same lower bound can be proved via an isotypic metapolynomial with circuit complexity controlled by the parameter $s$ . Theorem 1.1 further proves analogous results for more refined projections, such as the $T$ -isotypic projections or the projection on the highest weight space. These are discussed in Section 2.3.

2.3 Highest weight vectors and representation theoretic obstructions

Theorem 1.1 can be used to convert lower bounds proved by $\Delta$ into lower bounds proved by a highest weight vector (HWV for short). To see this, note that if $\Delta$ vanishes on $X_{r}$ and $\Delta(f_{\textup{hard}})\neq 0$ , then there exists a highest weight vector $\Delta^{\prime}$ vanishing on $X_{r}$ and such that $\Delta^{\prime}(g\cdot f_{\textup{hard}})\neq 0$ for some $g\in\textnormal{GL}_{k}$ ; in fact, this can be achieved with a random $g\in\textnormal{GL}_{k}$ . Hence a HWV proves the lower bound $c(g\cdot f_{{\textup{hard}}})>r$ ; if $c(\cdot)$ is an invariant complexity measure, the same lower bound holds for $f_{{\textup{hard}}}$ . Similarly to before, Theorem 1.1 provides an upper bound on the circuit complexity $\operatorname{cc}(\Delta^{\prime})$ in terms of $\operatorname{cc}(\Delta)$ , showing only a quasipolynomial blowup in the complexity of the metapolynomial.

A coarser view on HWVs is given via representation theoretic multiplicities, which is a central idea of geometric complexity theory [60, 61, 59]. Let $Y:=\overline{\textnormal{GL}_{k}\,f_{\textup{hard}}}$ denote the orbit closure, and let $X:=\overline{X_{s}}$ . It is easy to see that $f_{\textup{hard}}\in X$ if and only if $Y\subseteq X$ . The vector space of HWVs of weight $\lambda$ defines a vector space of polynomial functions on $X$ ; the dimension of such space is called the multiplicity $\mathsf{mult}_{\lambda}\mathbb{C}[X]$ of $\lambda$ in the coordinate ring $\mathbb{C}[X]$ . Standard facts in representation theory, and in particular Schur’s Lemma (see Lemma 4.4), guarantee that if $\mathsf{mult}_{\lambda}\mathbb{C}[X]>\mathsf{mult}_{\lambda}\mathbb{C}[Y]$ for some $\lambda$ , then $X\not\subset Y$ . Therefore, multiplicities give a method to potentially separate two varieties, and obtain a lower bound on $c(f_{\textup{hard}})$ . In this case, we say $\lambda$ is a multiplicity obstruction. If additionally $\mathsf{mult}_{\lambda}\mathbb{C}[X]>0=\mathsf{mult}_{\lambda}\mathbb{C}[Y]$ , then $\lambda$ is called an occurrence obstruction. Occurrence obstructions [15, 16] and multiplicity obstructions [46] are sometimes sufficient to obtain separations. However, it is known that occurrence obstructions do not work in certain setups [47, 38, 18, 24].

Theorem 1.1 makes no statement about the viability of the method of multiplicity obstructions. Indeed, one main hope of geometric complexity theory is that information about $\mathsf{mult}_{\lambda}\mathbb{C}[X]$ can be obtained without ever having to write down any circuit for a HWV. Information can be gained by decomposing much easier coordinate rings of orbits, see [19, 17]. This gives upper bounds on $\mathsf{mult}_{\lambda}\mathbb{C}[X]$ by using classical representation theoretic branching rules. The lower bounds on $\mathsf{mult}_{\lambda}\mathbb{C}[\overline{\textnormal{GL}_{k}f_{\textup{hard% }}}]$ are more difficult to obtain, see [46] for a recent implementation.

2.4 Border complexity

Lower bounds achieved via metapolynomials are better described in the setting of border complexity. Generally, for a given algebraic complexity measure $c(\cdot)$ , one can define a corresponding border measure, $\underline{c}(\cdot)$ as follows:

\underline{c}(f)=\min\left\{r:\begin{array}[]{l}\text{there exists a sequence % $f_{\varepsilon}$ such that $f=\lim_{\varepsilon\to 0}f_{\varepsilon}$}\\ \text{and $c(f_{\varepsilon})=r$ for all but finitely many $\varepsilon\in% \mathbb{C}$}\end{array}\right\};

correspondingly, a complexity class $\mathcal{C}$ defined in terms of the growth of a given complexity measure naturally induces a border complexity class $\bar{\mathcal{C}}$ , described by the growth of the corresponding border complexity measure. In fact, $\bar{\mathcal{C}}$ can be defined as the closure of $\mathcal{C}$ with respect to a suitable topology [48]. In the setting of algebraic circuits, the circuit size $\operatorname{cc}(\cdot)$ has a corresponding border circuit measure $\underline{\operatorname{cc}}(\cdot)$ which defines the complexity class $\overline{\mathsf{VP}}$ .

A natural question concerns whether $\mathcal{C}=\bar{\mathcal{C}}$ and more generally how much larger $\bar{\mathcal{C}}$ is compared to $\mathcal{C}$ . For example, the border class of sequences admitting (border) polynomial size $\Sigma\Lambda\Sigma$ circuits is contained in $\mathsf{VBP}$ , see [29] and [9, Theorem 4.2]. In [25], the same containment was shown for the border classes of $\Sigma^{[k]}\Pi\Sigma$ circuits (for every constant $k$ ). In some restricted setting, for instance in the study of matrix multiplication complexity, it is known that a complexity measure and its associated border complexity are equivalent [7]. In general, the question is wide open for most complexity classes and, in particular, for $\mathsf{VP}$ .

Metapolynomials characterize border complexity classes in the following sense: if a sequence of polynomials $(f_{n})$ does not belong to a border complexity class $\bar{\mathcal{C}}$ then there is a sequence of metapolynomials witnessing the non-membership. This is made precise in Theorem 2.2.

2.5 Algebraic complexity and algebraic natural proofs

Razborov and Rudich [66] introduced the notion of natural proofs in Boolean circuit complexity.

Definition 2.1 (Natural property).

A subset $P\subset\{f:\{0,1\}^{n}\rightarrow\{0,1\}\}$ of Boolean functions is said to be a natural property useful against a class $\mathcal{C}$ of Boolean circuits if the following is true:

$\blacksquare$

(Usefulness). Any Boolean function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ that can be computed by a Boolean circuit in $\mathcal{C}$ does not have the property $P$ .
$\blacksquare$

(Constructivity). Given the truth table of a Boolean function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ , whether it has the property $P$ can be decided in time polynomial in the length of the input, i.e., in time $2^{O(n)}$ .
$\blacksquare$

(Largeness). For all large enough $n$ , at least a $2^{-O(n)}$ fraction of all $n$ variate Boolean functions have the property $P$ .

A proof that a certain family of Boolean functions cannot be computed by circuits in $\mathcal{C}$ is said to be a natural lower bound proof if the proof (perhaps implicitly) proceeds via establishing a natural property useful against $\mathcal{C}$ , and showing that the candidate hard function has this property. Razborov and Rudich showed that most of the known Boolean circuit lower bound proofs, such as lower bounds for $\mathsf{AC}^{0}$ (constant-depth) circuits have the natural property. One can set the same framework in the algebraic setting; see [39, 40, 31, 21, 51]. The exact details of the definitions are not fully settled yet, see page 19 of [21].

Following [40], the stretched classes $\mathsf{metaVP}$ and $\mathsf{metaVQP}$ arise as follows. The class $\mathsf{metaVP}$ is the class of sequences $(\Delta_{1},\Delta_{2},\ldots)$ of metapolynomials of format $(\delta(n),n,k(n))$ with $k(n)$ polynomially bounded in $n$ , and $\delta(n)$ and $\operatorname{cc}(\Delta_{n})$ polynomially bounded in $N(n)=\binom{k(n)+n-1}{n}$ , which is the number of degree $n$ monomials in $k(n)$ variables. The class $\mathsf{metaVQP}$ is defined analogously, but with $\operatorname{cc}(\Delta_{n})$ quasipolynomially bounded in $N(n)$ .

We will now argue that $k(n)$ is bounded by a polynomial in $\log(N(n))$ . To see this, choose $\gamma$ such that $k(n)\leq n^{\gamma}$ for $n$ large enough. Take any such large enough $n$ and make a case distinction. If $k(n)\leq n$ , then $N=\binom{k+n-1}{k-1}\geq(1+\frac{n}{k-1})^{k-1}$ implies $\log N\geq(k-1)\log(1+\frac{n}{k-1})\geq(k-1)$ , since $\frac{n}{k-1}\geq 1$ ; here we use the fact that $\binom{m}{r}\geq(m/r)^{r}$ . On the other hand, if $k(n)\geq n+1$ , then since $\binom{m}{r}$ is an increasing function on $m$ for a fixed $r$ , we get that $N=\binom{k+n-1}{n}\geq\binom{2n}{n}\geq 2^{n}$ , for $n\geq 1$ . Therefore, $(\log N)^{\gamma}\geq n^{\gamma}\geq k$ . Hence, the claim is proved in both cases.

Fix an invariant complexity measure $c$ and let $X_{d,r}$ denote the set of homogeneous degree $d$ polynomials $f$ with $c(f)\leq r$ . For a format $(\delta,d,k)$ metapolynomial $\Delta:\mathbb{C}[x_{1},\ldots,x_{k}]_{d}\to\mathbb{C}$ let $\Delta|_{X_{d,r}}:X_{d,r}\to\mathbb{C}$ denote the restriction of $\Delta$ to $X_{d,r}$ . Let $\mathcal{C}$ denote the set of p-families with polynomially bounded $c$ . The vanishing ideal of $\mathcal{C}$ is defined as

\displaystyle I(\mathcal{C}):=\left\{(\Delta_{n})_{n\in\mathbb{N}}\textup{ of % format $(\ast,n,\ast)$ }:\begin{array}[]{l}\text{for every polynomially % bounded }r(n),\\ \text{the sequence }\big{(}\Delta_{1}|_{X_{1,r(1)}},\Delta_{2}|_{X_{2,r(2)}},% \ldots\big{)}\\ \text{eventually vanishes identically}\end{array}\right\}

To emphasize how natural this definition is, we provide a corresponding Nullstellensatz.

Theorem 2.2 (Nullstellensatz for $\mathcal{C}$ ).

Let $(f_{n})_{n\in\mathbb{N}}$ be a p-family of homogeneous polynomials such that $(\deg f_{n})$ is a strictly increasing sequence. The sequence $(f_{n})$ lies in $\overline{\mathcal{C}}$ if and only if for every $(\Delta_{n})\in I(\mathcal{C})$ we have $\Delta_{\deg(f_{n})}(f_{n})=0$ eventually.

The proof of Theorem 2.2 is given in Appendix A.

Definition 2.3 (Algebraic natural proof).

We say that $\mathcal{C}$ has algebraic natural proofs if $I(\mathcal{C})\mathop{\cap}\mathsf{metaVQP}$ contains a sequence that is not eventually zero.

Here we loosened the definition from the literature slightly from $\mathsf{metaVP}$ (see [40, 21]) to $\mathsf{metaVQP}$ , but note that the literature does not have just one standard definition, see page 19 of [21]. The landmark question in algebraic metacomplexity is whether $\mathsf{VP}$ has algebraic natural proofs.

Definition 2.3 should be compared with Definition 2.1 in the Boolean setting. If $I(\mathsf{VP})\mathop{\cap}\mathsf{metaVQP}$ contains an eventually nonzero sequence $\Delta$ of format $(\delta(n),n,k(n))$ , then clearly there exists the largest $r(n)$ such that $\Delta_{n}(X_{n,r(n)})=\{0\}$ , and further $\operatorname{cc}(\Delta_{n})\leq 2^{\operatorname{poly}(\log N)}$ , where $N:=\binom{k(n)+n-1}{n}$ , and $k(n)\leq\operatorname{poly}(n)$ . Therefore, $\Delta$ certifies the non-membership, a useful natural property. Furthermore, it trivially satisfies the largeness criterion, since $\Delta_{n}$ does not vanish on most polynomials. Finally, the quasipolynomial bound on the algebraic circuit complexity of $\Delta_{n}$ gives a natural algebraic analogue of the notion of constructivity.

Let Isotypic denote the set of sequences of isotypic metapolynomials. The following theorem follows from Theorem 1.1. It states in a concise way that only isotypic metapolynomials have to be considered for algebraic natural proofs.

Theorem 2.4 (Main theorem about algebraic natural proofs).

$\mathcal{C}$ has algebraic natural proofs if and only if $I(\mathcal{C})\mathop{\cap}\mathsf{metaVQP}\mathop{\cap}\textup{{Isotypic}}$ contains a sequence that is not eventually zero.

Proof.

One direction is clear, because $I(\mathcal{C})\mathop{\cap}\mathsf{metaVQP}\mathop{\cap}\textup{{Isotypic}}% \subseteq I(\mathcal{C})\mathop{\cap}\mathsf{metaVQP}$ .

For the other direction, we first consider a general property of isotypic components of vanishing ideals. Let $I(X)_{\delta}=\{\Delta\textup{ of format $(\delta,d,k)$}\mid\Delta|_{X}=0\}$ . Let $X$ be closed under the action of $\textnormal{GL}_{k}$ . If $\Delta\in I(X)_{\delta}$ , then $g\Delta\in I(X)_{\delta}$ for every $g\in\textnormal{GL}_{k}$ . Indeed, in this case for all $x\in X$ we have $(g\Delta)(x)=(\Delta)(g^{-1}x)=0$ , since $g^{-1}x\in X$ . Moreover, $I(X)_{\delta}$ is closed under linear combinations, hence $I(X)_{\delta}$ is a vector space, and in particular closed under taking limits and thus closed under the action of the Lie algebra. We have $\Delta\in I(X)_{\delta}$ if and only if for all $\lambda$ we have $\Delta^{(\lambda)}\in I(X)_{\delta}$ , because the projection of $\Delta$ to an isotypic component $\Delta^{(\lambda)}$ involves only finite linear combinations of Lie algebra actions, see Section 5.

Let $\mathcal{C}$ have algebraic natural proofs, witnessed by a sequence $(\Delta_{n})_{n\in\mathbb{N}}\in I(\mathcal{C})\mathop{\cap}\mathsf{metaVQP}$ of format $(\delta(n),n,k(n))$ that is not eventually zero. Now, let $(\lambda^{n})_{n\in\mathbb{N}}$ be a sequence of partitions, $\lambda^{n}\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}_{k(n)}\,}{\scalebox{1.2}% [0.7]{ $\vdash$}_{k(n)}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}_{k(n)% }\,}{\scalebox{0.5}{\scalebox{1.2}[0.7]{$\vdash$}}_{k(n)}\,}{n\cdot\delta(n)}$ , such that the isotypic component $\Delta_{n}^{(\lambda^{n})}$ of $\Delta_{n}$ is nonzero whenever $\Delta_{n}$ is nonzero. By construction, $(\Delta_{n}^{(\lambda_{n})})_{n\in\mathbb{N}}\in\textup{{Isotypic}}$ and $(\Delta_{n}^{(\lambda_{n})})_{n\in\mathbb{N}}$ is not eventually zero. Since each $X_{n,i}$ is invariant under the group action, we have for all $i$ and $n$ : Whenever $\Delta_{n}|_{X_{n,i}}=0$ , then also $\Delta_{n}^{(\lambda^{n})}|_{X_{n,i}}=0$ . For every polynomially bounded $r$ we have $\Delta_{n}|_{X_{n,r(n)}}=0$ eventually, hence we have $\Delta_{n}^{(\lambda^{n})}|_{X_{n,r(n)}}=0$ eventually, and hence $(\Delta_{n}^{(\lambda_{n})})_{n\in\mathbb{N}}\in I(\mathcal{C})$ . Let $N(n)=\binom{k(n)+n-1}{n}$ . Let $s(n)=\operatorname{cc}(\Delta_{n})\in 2^{\operatorname{poly}(\log(N))}$ . By Theorem 1.1 with $k(n)\in\operatorname{poly}(\log(N))$ , $\delta(n)\in\operatorname{poly}(N)$ , and $d=n$ , we have $\operatorname{cc}(\Delta^{(\lambda^{n})}_{n})\in 2^{\operatorname{poly}(\log(N% ))}$ , which implies $(\Delta_{n}^{(\lambda_{n})})_{n\in\mathbb{N}}\in\mathsf{metaVQP}$ , which finishes the proof. $\hfill\blacktriangleleft$

3 Outline of the proof of Theorem 1.1

The proof of Theorem 1.1 is built on an efficient construction of the image of metapolynomials under projections onto the isotypic spaces.

Roughly speaking, we will construct the projectors of Theorem 1.1 as linear combinations of repeated derivations applied to metapolynomials. These derivations live naturally in a vector space called the Lie algebra $\mathfrak{gl}_{k}$ of $\textnormal{GL}_{k}$ . They are defined as the linearization of linear change of coordinates by elements of $\textnormal{GL}_{k}$ applied to polynomials on which a metapolynomial is evaluated. Repeated applications of these operations is formally described using products in an associative algebra $\mathcal{U}(\mathfrak{gl}_{k})\supseteq\mathfrak{gl}_{k}$ called the universal enveloping algebra of $\mathfrak{gl}_{k}$ . More concretely, a standard basis element in $\mathfrak{gl}_{k}$ corresponds to an analogue of a shifted partial derivative for metapolynomials (see ˜4.2), and an element of $\mathcal{U}(\mathfrak{gl}_{k})$ captures repeated applications of such shifted partial derivatives.

Lie algebras and their universal enveloping algebras have a long history in mathematics, and their theory is rich and well-developed. We review the theory in Section 4 to the extent required to construct the projectors. The construction is completely explicit. The universal enveloping algebra $\mathcal{U}(\mathfrak{gl}_{k})$ contains elements $\{C_{1},\ldots,C_{r}\}$ which separate isotypic components in the following sense: each $C_{i}$ acts by scalar multiplication on each isotypic component, and for any two distinct isotypic components there is a $C_{i}$ for which the corresponding scalars are different; the precise statement is the content of Theorem 4.11 and Theorem 4.13. This property is used to construct the projectors via an analogue of standard multivariate polynomial interpolation, see Section 5.1. The elements $\{C_{1},\ldots,C_{r}\}$ are called Casimir operators, and they are defined as generators of certain commutative subalgebras of $\mathcal{U}(\mathfrak{gl}_{k})$ . For each case of Theorem 1.1, there is a suitable algebra for which the corresponding isotypic components are the spaces of interest, see Table 1.

The proof that the projectors can be implemented efficiently is built on the following insights. The Poincaré–Birkhoff–Witt theorem (Theorem 4.9) allows one to express each projector as a linear combination in $\mathcal{U}(\mathfrak{gl}_{k})$ of $m$ -fold products of elements of $\mathfrak{gl}_{k}$ with $m$ bounded polynomially in the number of isotypic components. This number is exponential in $k$ , which is polylogarithmic in $N$ as observed in Section 2.5. We use this fact to construct circuits of quasipolynomial size for the projectors in Section 5.2. In turn, this will complete the proof of Theorem 1.1.

4 Representations of Lie algebras

In this section, we provide an introduction to Lie algebras, universal enveloping algebras, and their representation theory, following mainly [32, 42]. Afterwards, we introduce and explain the results needed to construct the projectors in Theorem 1.1. These results are typically stated in the language of abstract Lie algebras, and therefore we take time to build up this general theory. In our case of interest, the Lie algebra arises from $\textnormal{GL}_{k}$ and many parts simplify. We will regularly indicate this in the text for clarity and concreteness. We establish homogeneous polynomials and metamonomials as a Lie algebra representation, which we will use as running examples.

A Lie algebra $\mathfrak{g}$ is a vector space endowed with a bilinear bracket operation $[-,-]$ which is skew-commutative, i.e., $[X,Y]=-[Y,X]$ , and satisfies a relation called the Jacobi identity $[X,[Y,Z]]+[Z,[X,Y]]+[Y,[Z,X]]=0$ ; in particular, the bracket operation is usually not associative. Every associative algebra $\mathcal{A}$ is a Lie algebra with the commutator bracket given by $[a,b]\coloneqq ab-ba$ for every $a,b\in\mathcal{A}$ . In this paper, we are interested in the representation theory of the general linear group $\textnormal{GL}_{k}$ , and we study it via the representation theory of its Lie algebra $\mathfrak{gl}_{k}$ : this is the space of $k\times k$ matrices endowed with the commutator bracket.

A Lie algebra representation is a vector space $V$ with an associated linear map $\rho:\mathfrak{g}\to\textnormal{End}(V)$ such that $\rho([X,Y])=[\rho(X),\rho(Y)]$ where the bracket on the right is the commutator bracket. We equivalently say that $\mathfrak{g}$ (or its elements) acts on $V$ . For $v\in V$ , we often write $X.v\coloneqq\rho(X)v$ as a shorthand. A simple example is $V=\mathbb{C}^{k}$ , where $\mathfrak{gl}_{k}$ acts by matrix-vector multiplication. This is called the standard representation of $\mathfrak{gl}_{k}$ . In this paper we examine the space of metapolynomials $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ as a Lie algebra representation of $\mathfrak{gl}_{k}$ . The Lie algebra action is explicitly given in in ˜4.2.

Representation theory of Lie algebras is used to study the representation theory of Lie groups because it allows one to “linearize” a group action. More precisely, every Lie group $G$ has an associated Lie algebra $\mathfrak{g}$ and every Lie group representation (a non-linear map) defines naturally a Lie algebra representation (a linear map). All Lie algebra representations we will encounter arise from this correspondence. We will describe the $\mathfrak{gl}_{k}$ action on polynomials and metapolynomials explicitly in ˜4.1 and ˜4.2, which may be taken as the definition. The details of the correspondence between Lie groups and Lie algebras are not crucial for the rest of the paper. We briefly outline them in Remark 4.3.

For a vector space $V$ with basis $v_{1},\ldots,v_{r}$ , let $v_{1}^{*},\ldots,v_{r}^{*}\in V^{*}$ be the dual basis of $V^{*}$ . Explicitly, $v_{\ell}^{*}$ is the linear form mapping a vector $v=\sum_{i}c_{i}v_{i}\in V$ , with $c_{i}\in\mathbb{C}$ , to the coefficient $c_{\ell}$ . The basis dual to the standard basis of $\mathbb{C}^{k}$ is the set of variables $x_{1},\ldots,x_{k}$ . Let $E_{i,j}\in\mathfrak{gl}_{k}$ be the $k\times k$ matrix having $1$ at the entry $(i,j)$ and zero elsewhere. Regarding $E_{i,j}:\mathbb{C}^{k}\to\mathbb{C}^{k}$ as a linear map, we have $x_{\ell}\circ E_{i,j}=0$ if $\ell\neq i$ and $x_{\ell}\circ E_{i,j}=x_{j}$ if $\ell=i$ ; here $\circ$ denotes the composition of functions. Since $\{E_{i,j}\}_{i,j}$ forms a basis for $\mathfrak{gl}_{k}$ , the action of $\mathfrak{gl}_{k}$ on a representation $V$ is uniquely determined by the action of the $E_{i,j}$ ’s.

$\vartriangleright$ Claim 4.1 (Action on polynomials).

The vector space $\mathbb{C}[x_{1},\ldots,x_{k}]_{d}$ of homogeneous degree $d$ polynomials is a representation of $\mathfrak{gl}_{k}$ . It is the linearization of the action of $\textnormal{GL}_{k}$ acting by base change on the variables $x_{1},\ldots,x_{k}$ . For $f\in\mathbb{C}[x_{1},\ldots,x_{k}]_{d}$ , the action is defined by the shifted partial derivative

\displaystyle E_{i,j}.f=-\sum_{\ell=1}^{k}(x_{\ell}\circ E_{i,j})\frac{% \partial}{\partial x_{\ell}}f=-x_{j}\frac{\partial}{\partial x_{i}}f.

(1)

In particular, for a monomial $f=x_{\ell_{1}}\cdots x_{\ell_{d}}$ , we have

E_{i,j}.f=\textstyle\sum_{p=1}^{d}x_{\ell_{1}}\cdots x_{\ell_{p-1}}(E_{i,j}.x_% {\ell_{p}})x_{\ell_{p+1}}\cdots x_{\ell_{d}}.

For a multiindex $\mu\in\mathbb{N}^{k},\sum_{i}\mu_{i}=d$ , let $c_{\mu}$ be the corresponding variable, that is, the linear map sending a polynomial $f$ to the coefficient of $x^{\mu}$ . Let $e_{1},\ldots,e_{k}\in\mathbb{N}^{k}$ be the standard basis vectors: $e_{i}$ is the vector with $1$ at the $i$ -th entry and $0$ elsewhere.

$\vartriangleright$ Claim 4.2 (Action on metapolynomials).

The vector space of metapolynomials of format $(\delta,d,k)$ , that is $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}=\mathbb{C}[c_{\mu}:\mu% \in\mathbb{N}^{k},|\mu|=d]_{\delta}$ is a representation of $\mathfrak{gl}_{k}$ . It is the linearization of the action of $\textnormal{GL}_{k}$ acting by base change on the variables $x_{1},\ldots,x_{k}$ . For a metapolynomial $\Delta\in\mathbb{C}[c_{\mu}:\mu\in\mathbb{N}^{k},|\mu|=d]_{\delta}$ , the action is given by

\displaystyle E_{i,j}.\Delta=\sum_{\mu}(E_{i,j}.c_{\mu})\frac{\partial}{% \partial c_{\mu}}\Delta,

(2)

where the summation is over all multi-indices $\mu\in\mathbb{N}^{k}$ with $\sum_{i}\mu_{i}=d$ . The action on metavariables is given by

E_{i,j}.c_{\mu}=\begin{cases}(\mu_{i}+1)\,c_{\mu+e_{i}-e_{j}}&\text{ if }i\neq j% ,\\ \mu_{i}\,c_{\mu}&\text{ otherwise},\end{cases}

(3)

where we set $c_{\mu+e_{i}-e_{j}}=0$ if $\mu_{j}=0$ . In particular, for a metamonomial $\Delta=c_{\mu_{1}}\cdots c_{\mu_{\delta}}$ , we have

E_{i,j}.\Delta=\textstyle\sum_{p=1}^{\delta}c_{\mu_{1}}\cdots c_{\mu_{p-1}}(E_% {i,j}.c_{\mu_{p}})c_{\mu_{p+1}}\cdots c_{\mu_{\delta}}.

The following remark illustrates the correspondence between representations of complex algebraic Lie groups and representations of the corresponding Lie algebras. As mentioned before, it is not essential for the rest of the paper, but the proof of ˜4.1 and ˜4.2 are built on this correspondence.

$\blacktriangleright$ Remark 4.3.

A complex algebraic Lie group is a group with the structure of a complex algebraic variety, [32, Ch. 7]. One can show that $\textnormal{GL}_{k}$ is such a group. Let $V$ be a finite-dimensional vector space. A representation of a complex algebraic Lie group $G$ on $V$ is a group homomorphism $\rho:G\to\textnormal{GL}(V)$ which is a regular map, in the sense that the entries of $\rho(g)\in\textnormal{GL}(V)$ regarded as a matrix in a fixed basis, are polynomial functions on $G$ .

As a vector space, the Lie algebra of $G$ is, by definition, the tangent space of $G$ at its identity element $\mathfrak{g}=T_{\mathsf{id}}G$ . The bracket operation is defined via the adjoint representation of $G$ on $\mathfrak{g}$ , see [32, Ch. 8] In the case of $\textnormal{GL}_{k}$ one has $\mathfrak{gl}_{k}\simeq T_{\mathsf{id}_{k}}\textnormal{GL}_{k}$ is the space of $k\times k$ matrices, and the bracket is the standard commutator.

Every representation $\rho:G\to\textnormal{GL}(V)$ of $G$ defines a representation $\mathfrak{g}$ via its differential at the identity: $\textnormal{d}\rho:T_{\mathsf{id}}G\to T_{\mathsf{id}}\textnormal{GL}(V)$ ; this is a linear map and defines a Lie algebra homomorphism from $T_{\mathsf{id}}G=\mathfrak{g}$ to $T_{\mathsf{id}}\textnormal{GL}(V)=\textnormal{End}(V)=\mathfrak{gl}(V)$ .

Explicitly, the value of $\textnormal{d}\rho$ at $X\in\mathfrak{g}$ is the element $\textnormal{d}\rho(X)\in\mathfrak{gl}(V)\simeq\textnormal{End}(V)$ defined by

\big{(}\textnormal{d}\rho(X)\big{)}v=\frac{\textnormal{d}}{\textnormal{d}s}% \Big{|}_{s=0}\Big{(}\rho\big{(}\gamma(s)\big{)}v\Big{)}\quad\text{ for every $% v\in V$};

(4)

here $\gamma:\mathbb{C}\to G$ is any smooth curve such that $\gamma(0)=\mathsf{id}_{G}$ and $\gamma^{\prime}(0)=X$ . It is easy to see that $\textnormal{d}\rho(X)$ does not depend on the choice of $\gamma$ .

Proof of ˜4.1 and ˜4.2.

We derive the Lie algebra representations from their respective group representations, as in Remark 4.3.

Every representation $\rho:G\to\textnormal{GL}(V)$ defines a pullback representation on the space of polynomials of degree $p$ on $V$ , $\mathbb{C}[V]_{p}$ . For $g\in G$ and $f\in\mathbb{C}[V]_{p}$ , this is given by $g\cdot f=f\circ\rho(g^{-1})$ where $\rho(g^{-1}):V\to V$ is regarded as a linear map and $\circ$ denotes the composition of functions.

The standard representation of $\textnormal{GL}_{k}$ on $\mathbb{C}^{k}$ induces in this way a representation on the space of polynomials $\mathbb{C}[x_{1},\ldots,x_{k}]_{d}$ . Similarly, the action of $\textnormal{GL}(\mathbb{C}[x_{1},\ldots,x_{k}]_{d})$ induces a representation on the space of metapolynomials $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ ; the action of $\textnormal{GL}_{k}$ on metapolynomials is the composition of the two representations

\textnormal{GL}_{k}\to\textnormal{GL}(\mathbb{C}[x_{1},\ldots,x_{k}]_{d})\to% \textnormal{GL}(\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}).

Now, if $\rho:G\to\textnormal{GL}(V)$ induces the Lie algebra representation $\textnormal{d}\rho:\mathfrak{g}\to\textnormal{GL}(V)$ , the pullback representation of $G$ on $\mathbb{C}[V]_{p}$ induces the Lie algebra representation described as follows. For $X\in\mathfrak{g}$ , let $\gamma(s)$ be a smooth curve in $G$ such that $\gamma(0)=\mathsf{id}_{G}$ and $\gamma^{\prime}(0)=X$ . The chain rule of derivatives implies $\frac{\textnormal{d}}{\textnormal{d}s}\big{|}_{s=0}\gamma(s)^{-1}=-X$ . We show this in the case where $G$ is a group of matrices: in this case, one can multiply elements of $G$ by elements of $\mathfrak{g}$ and obtain

\frac{\textnormal{d}}{\textnormal{d}s}\bigg{|}_{s=0}\gamma(s)^{-1}=-\bigl{[}% \frac{\textnormal{d}}{\textnormal{d}s}\bigg{|}_{s=0}\gamma(s)\bigr{]}\cdot% \bigl{[}(\gamma(s)^{-2})\big{|}_{s=0}\bigr{]}=-\gamma^{\prime}(0)\cdot\gamma(0% )^{-2}=-X\cdot\mathsf{id}^{-2}=-X.

In general, the multiplication of matrices should be replaced by the action of $G$ on $\mathfrak{g}$ .

Let $V^{*}$ be the dual space of $V$ with basis $z_{1},\ldots,z_{r}$ ; in particular $\mathbb{C}[V]_{p}$ is the space of polynomials of degree $p$ in $z_{1},\ldots,z_{r}$ . By Equation 4, for every $F\in\mathbb{C}[V]_{p}$ , $X . F$ is the polynomial function described as follows, on every $\zeta\in V$ :

	$\displaystyle X.F(\zeta)=$	$\displaystyle\frac{\textnormal{d}}{\textnormal{d}s}\Big{\|}_{0}(\gamma(s)\cdot F% )(\zeta)=$
		$\displaystyle\frac{\textnormal{d}}{\textnormal{d}s}\Big{\|}_{0}(F\circ\gamma(s)% ^{-1})(\zeta)=\qquad(\text{using chain rule})$
		$\displaystyle\sum_{\ell=1}^{r}\frac{\partial}{\partial z_{\ell}}F(\zeta)\cdot(% z_{\ell}(\frac{\textnormal{d}}{\textnormal{d}s}\Big{\|}_{0}\gamma(s)^{-1}\zeta))=$
		$\displaystyle\sum_{\ell=1}^{r}\frac{\partial}{\partial z_{\ell}}F(\zeta)\cdot(% z_{\ell}(-X.\zeta))=-\sum_{\ell=1}^{r}\frac{\partial}{\partial z_{\ell}}F(% \zeta)\cdot z_{\ell}(X.\zeta).$

Specialize the calculation above to the case of polynomials and metapolynomials to obtain Equation 1 and Equation 2. It remains to show Equation 3, which follows from a direct calculation: regarding $c_{\mu}$ as a function of a polynomial $f$ , we have

E_{ij}.c_{\mu}(f)=-c_{\mu}(E_{ij}.f)=c_{\mu}(x_{j}\frac{\partial}{\partial x_{% i}}f)=\begin{cases}(\mu_{i}+1)\,c_{\mu+e_{i}-e_{j}}(f)&\text{ if }i\neq j,\\ \mu_{i}\,c_{\mu}(f)&\text{ otherwise}.\end{cases}\

$\hfill\blacktriangleleft$

Let $V$ be a representation of a Lie algebra $\mathfrak{g}$ . A subspace $V^{\prime}\subseteq V$ that is itself a $\mathfrak{g}$ -representation is called a subrepresentation. A representation $V$ is irreducible if it contains no subrepresentations except the zero space of $V$ and $V$ itself. A map $\phi:V\to W$ between two representations is called equivariant if it commutes with the action of $\mathfrak{g}$ . Schur’s Lemma characterizes equivariant maps between irreducible representations:

Lemma 4.4 (Schur’s Lemma, [32, Lem. 1.7]).

Let $V, W$ be irreducible representations for a Lie algebra $\mathfrak{g}$ and let $\phi:V\to W$ be an equivariant map. Then either $\phi=0$ or $\phi$ is an isomorphism. Moreover, if $V=W$ , then $\phi=c\cdot\mathsf{id}_{V}$ for some $c\in\mathbb{C}$ .

A complex algebraic Lie group is called reductive if every representation is completely reducible, namely it splits into direct sum of irreducible subrepresentations; the general linear group $\textnormal{GL}_{k}$ is reductive, see e.g. [45, Ch.X]. In the following $\mathfrak{g}$ is the Lie algebra of a reductive group, and explicitly we are interested in the case where $G=\textnormal{GL}_{k}$ and $\mathfrak{g}=\mathfrak{gl}_{k}$ .

4.1 Cartan subalgebras and weights

A subalgebra $\mathfrak{t}\subseteq\mathfrak{g}$ is called abelian if $[\mathfrak{t},\mathfrak{t}]=0$ . A Cartan subalgebra $\mathfrak{h}$ of $\mathfrak{g}$ is a maximal abelian subalgebra with the property that if $[X,\mathfrak{h}]\subseteq\mathfrak{h}$ then $X\in\mathfrak{h}$ . The subalgebra of diagonal matrices in $\mathfrak{gl}_{k}$ is a Cartan subalgebra of $\mathfrak{gl}_{k}$ . It turns out that if $G$ is reductive, then all Cartan subalgebras of $\mathfrak{g}$ have the same dimension; in fact they are all equivalent under a natural action of $G$ on $\mathfrak{g}$ [32, Sec. D3]. In the case of $\textnormal{GL}_{k}$ , the action on $\mathfrak{gl}_{k}$ is given by conjugation: $g\cdot X=gXg^{-1}$ for $g\in\textnormal{GL}_{k}$ and $X\in\mathfrak{gl}_{k}$ . In this case, one can show that any Cartan subalgebra is equivalent to the subspace of diagonal matrices.

If $\mathfrak{g}$ is the Lie algebra of a complex reductive Lie group $G$ , then Cartan subalgebras of $\mathfrak{g}$ correspond to maximal abelian subgroups in $G$ . For a fixed Cartan subalgebra $\mathfrak{h}$ , let $\mathbb{T}$ be the corresponding abelian subgroup of $G$ . If $\mathfrak{h}$ is the subset of diagonal matrices in $\mathfrak{gl}_{k}$ , then $\mathfrak{h}$ is the Lie algebra of the abelian group $\mathbb{T}$ of diagonal matrices with nonzero diagonal entries. Irreducible $\mathbb{T}$ -representations are $1$ -dimensional and they are in one-to-one correspondence with a lattice $\Lambda$ in the space $\mathfrak{h}^{*}$ , called the weight lattice of $\mathfrak{g}$ ; the elements of $\Lambda$ are called weights. When $\mathbb{T}$ is the subgroup of $\textnormal{GL}_{k}$ of diagonal matrices, then this definition coincides with the one used in Section 1 for metapolynomials; see also Example 4.7. The construction of the weight lattice is not straightforward for arbitrary Lie algebras, but it is very explicit in the case where $\mathfrak{h}$ is the subalgebra of diagonal elements in $\mathfrak{gl}_{k}$ :

$\vartriangleright$ Claim 4.5.

The weight lattice of $\mathfrak{gl}_{k}$ with respect to the Cartan subalgebra $\mathfrak{h}$ of diagonal elements is the abelian group of integer linear combinations of the diagonal elements, that is, the group of linear functions

	$\displaystyle\alpha:\mathfrak{h}$	$\displaystyle\to\mathbb{C}$
	$\displaystyle\left(\begin{smallmatrix}h_{1}&&\\ &\ddots&\\ &&h_{k}\end{smallmatrix}\right)$	$\displaystyle\mapsto\alpha_{1}h_{1}+\cdots+\alpha_{k}h_{k}.$

with $\alpha_{1},\ldots,\alpha_{k}\in\mathbb{Z}$ . In the following, we usually identify the weight $\alpha$ with the $k$ -tuple of its integer coefficients $\alpha=(\alpha_{1},\ldots,\alpha_{k})$ .

Proof.

Let $\mathbb{T}$ be the subgroup of diagonal matrices in $\textnormal{GL}_{k}$ . Let $(\alpha_{1},\ldots,\alpha_{k})\in\mathbb{Z}^{k}$ be an integer vector.

	$\displaystyle\rho:\mathbb{T}$	$\displaystyle\to\mathbb{C}^{\times}\simeq\textnormal{GL}_{1}$
	$\displaystyle\left(\begin{smallmatrix}t_{1}&&\\ &\ddots&\\ &&t_{k}\end{smallmatrix}\right)$	$\displaystyle\mapsto t_{1}^{\alpha_{1}}\cdots t_{k}^{\alpha_{k}}$

is a group homomorphism, hence it defines a $1$ -dimensional (irreducible) representation of $\mathbb{T}$ . It is not hard to prove that all irreducible representations of $\mathbb{T}$ arise in this way.

The induced $\mathfrak{h}$ -representation is

	$\displaystyle\textnormal{d}\rho:\mathfrak{h}$	$\displaystyle\to\mathbb{C}\simeq\mathfrak{gl}_{1}$
	$\displaystyle\left(\begin{smallmatrix}h_{1}&&\\ &\ddots&\\ &&h_{k}\end{smallmatrix}\right)$	$\displaystyle\mapsto\alpha_{1}h_{1}+\cdots+\alpha_{k}h_{k}.$

In other words, irreducible $\mathfrak{h}$ -representations induced from $\mathbb{T}$ -representations are in one-to-one correspondence with functions $\alpha\in\mathfrak{h}^{*}$ mapping a diagonal element $H\in\mathfrak{h}$ to an integer linear combination of its diagonal entries. $\hfill\vartriangleleft$

Every $\mathfrak{g}$ -representation $V$ restricts to an $\mathfrak{h}$ -representation, hence it decomposes into the direct sum of irreducible $1$ -dimensional $\mathfrak{h}$ -representations. Since they are uniquely determined by their weights, we have $V=\bigoplus_{\alpha\in\Lambda}V_{\alpha}^{\oplus m_{\alpha}}$ ; in particular $m_{\alpha}\neq 0$ only for finitely many $\alpha\in\Lambda$ . If $m_{\alpha}\neq 0$ , then $\alpha$ is called a weight of $V$ , $m_{\alpha}$ is called multiplicity and the direct summand $V_{\alpha}^{\oplus m_{\alpha}}$ is called the weight subspace of $V$ of weight $\alpha$ . An element $X\in\mathfrak{h}$ acts simultaneously on the $m_{\alpha}$ copies of $V_{\alpha}$ via scalar multiplication by $\alpha(X)\in\mathbb{C}$ . The elements of a weight subspace are called weight vectors; a basis of $V$ consisting of weight vectors is called a weight basis.

Example 4.6.

Consider the $\mathfrak{gl}_{3}$ -representation $V=\mathbb{C}[x_{1},x_{2},x_{3}]_{2}$ with the action described in ˜4.1. Let $\mathfrak{h}\subseteq\mathfrak{gl}_{3}$ be the subalgebra of diagonal matrices. Consider the six monomials of $V$ , which define a basis:

\begin{array}[]{lll}x_{1}^{2},&x_{2}^{2},&x_{3}^{2},\\ x_{2}x_{3},&x_{1}x_{3},&x_{1}x_{2}.\end{array}

One can verify that they form a weight basis of $V$ . For instance, given $H=\left(\begin{smallmatrix}t_{1}&&\\ &t_{2}&\\ &&t_{3}\end{smallmatrix}\right)=t_{1}E_{11}+t_{2}E_{22}+t_{3}E_{33}\in% \mathfrak{h}$ , we have

H.(x_{1}^{2})=\textstyle\sum_{i}t_{i}E_{ii}.(x_{1}^{2})=-\sum_{i}t_{i}\sum_{j}% x_{j}\displaystyle\frac{\partial}{\partial x_{j}}(x_{1}^{2})=-(2t_{1})x_{1}^{2}

showing that $x_{1}^{2}$ is a weight vector of weight $(-2,0,0)$ . More generally, we have

\begin{array}[]{rlrlrl}H.(x_{1}^{2})=\hskip-4.62497pt&\hskip-4.62497pt-2t_{1}% \,x_{1}^{2},&H.(x_{2}^{2})=\hskip-4.62497pt&\hskip-4.62497pt-2t_{2}\,x_{2}^{2}% ,&H.(x_{3}^{2})=\hskip-4.62497pt&\hskip-4.62497pt-2t_{3}\,x_{3}^{2},\\ H.(x_{2}x_{3})=\hskip-4.62497pt&\hskip-4.62497pt-(t_{2}+t_{3})\,x_{2}x_{3},&H.% (x_{1}x_{3})=\hskip-4.62497pt&\hskip-4.62497pt-(t_{1}+t_{3})\,x_{1}x_{3},&H.(x% _{1}x_{2})=\hskip-4.62497pt&\hskip-4.62497pt-(t_{1}+t_{2})\,x_{1}x_{2}.\end{array}

This shows that $V$ decomposes into the sum of six weight spaces, each spanned by one of the weight vectors above. The corresponding weights are the six elements of $\mathfrak{h}^{*}$ mapping $H$ to the eigenvalues of $H$ on each weight vector. As $k$ -tuple of integers, they are

\begin{array}[]{lll}(-2,0,0),&(0,-2,0),&(0,0,-2),\\ (0,-1,-1),&(-1,0,-1),&(-1,-1,0).\end{array}

More generally, in a space of polynomials $V=\mathbb{C}[x_{1},\ldots,x_{k}]_{d}$ , the monomials form a weight basis. The weight of a monomial $x^{\mu}=x_{1}^{\mu_{1}}\cdots x_{k}^{\mu_{k}}$ , regarded as a vector of integers, is $-\mu$ .

Example 4.7.

Consider the $\mathfrak{gl}_{2}$ -representation $V=\mathbb{C}[\mathbb{C}[x_{1},x_{2}]_{3}]_{2}$ of metapolynomials of format $(2,3,2)$ , with the action described in ˜4.2. One can verify that the metamonomials form a weight basis. For instance, given $H=\left(\begin{smallmatrix}t_{1}&\\ &t_{2}\end{smallmatrix}\right)=t_{1}E_{11}+t_{2}E_{22}\in\mathfrak{h}$ , we have

H.(c_{30}^{2})=\textstyle\sum_{i=1}^{2}t_{i}E_{ii}.(c_{30}^{2})=\textstyle\sum% _{i=1}^{2}t_{i}\sum_{\mu}E_{ii}.c_{\mu}\cdot\displaystyle\frac{\partial}{% \partial c_{\mu}}(c_{30}^{2})=3\cdot 2\cdot t_{1}\cdot c_{30}^{2}=(6t_{1})c_{3% 0}^{2}.

showing that $c_{30}^{2}$ is a weight vector of weight $(6,0)$ . Similarly, one can compute the weight of every metamonomial:

\begin{array}[]{rlrlrl}H.(c_{21}^{2})=\hskip-7.39998pt&(4t_{1}+2t_{2})c_{21}^{% 2},&H.(c_{12}^{2})=\hskip-7.39998pt&(2t_{1}+4t_{2})c_{12}^{2},&H.(c_{03}^{2})=% \hskip-7.39998pt&(6t_{2})c_{03}^{2},\\ H.(c_{30}c_{21})=\hskip-7.39998pt&(5t_{1}+\phantom{1}t_{2})c_{30}c_{21},&H.(c_% {30}c_{12})=\hskip-7.39998pt&(4t_{1}+2t_{2})c_{30}c_{12},&H.(c_{30}c_{03})=% \hskip-7.39998pt&(3t_{1}+3t_{2})c_{30}c_{03},\\ H.(c_{21}c_{12})=\hskip-7.39998pt&(3t_{1}+3t_{2})c_{21}c_{12},&H.(c_{21}c_{03}% )=\hskip-7.39998pt&(2t_{1}+4t_{2})c_{21}c_{03},&H.(c_{12}c_{03})=\hskip-7.3999% 8pt&(\phantom{1}t_{1}+5t_{2})c_{21}c_{12}.\end{array}

Therefore $V$ has seven weight spaces of weight $(p,6-p)$ with $p=0,\ldots,6$ . The weight spaces of weight $(4,2),(3,3),(2,4)$ have dimension $2$ , the others have dimension $1$ .

More generally, the metamonomials give a weight basis for the space of metapolynomials of format $(\delta,d,k)$ . A metamonomial $c_{\mu_{1}}\cdots c_{\mu_{\delta}}$ has weight $\mu_{1}+\cdots+\mu_{\delta}$ , in accordance with what we defined in the introduction.

4.2 Roots and highest weights

An important representation is given by the action of the Lie algebra on itself, called the adjoint representation $\textnormal{ad}:\mathfrak{g}\to\textnormal{End}(\mathfrak{g})$ and defined by $\textnormal{ad}(X)=[X,-]$ . By definition, the weight space of weight $0$ is $\mathfrak{h}$ itself; moreover, one can prove that all other weight spaces are $1$ -dimensional [32, Ch. 14]. The nonzero weights of the adjoint representation are called the roots of the Lie algebra $\mathfrak{g}$ (with respect to $\mathfrak{h}$ ); let $\Phi_{\mathfrak{g}}\subseteq\Lambda$ denote the set of roots of $\mathfrak{g}$ . It turns out that $\eta\in\mathfrak{h}^{*}$ is a root if and only if $-\eta$ is a root and $\pm\eta$ are the only integer multiples of $\eta$ that are roots.

We compute the roots for $\mathfrak{gl}_{k}$ with $\mathfrak{h}$ the algebra of diagonal matrices. Let $H=\textnormal{diag}(t_{1},\ldots,t_{k})\in\mathfrak{h}$ . Then

\displaystyle\textnormal{ad}(H)E_{i,j}=HE_{i,j}-E_{i,j}H=t_{i}E_{i,j}-t_{j}E_{% i,j}=(t_{i}-t_{j})E_{i,j}.

(5)

So $\mathbb{C}E_{i,j}$ is the weight space corresponding to the weight $(e_{i}-e_{j})\in\mathfrak{h}^{*}$ . Since the matrices $E_{i,j}$ span $\mathfrak{gl}_{k}$ , we obtain that the set of roots is $\Phi_{\mathfrak{gl}_{k}}=\{e_{i}-e_{j}\mid i,j\in[k],i\neq j\}$ .

The roots of the Lie algebra shift the weights of the Lie algebra representations: more precisely, let $V$ be a representation of $\mathfrak{g}$ , $v\in V$ a weight vector of weight $\lambda$ and $X\in\mathfrak{g}_{\alpha}$ for some root $\alpha$ ; then $X . v$ is a weight vector of weight $\lambda+\alpha$ .

A choice of positive roots is a subset $\Phi_{\mathfrak{g}}^{+}$ of $\Phi_{\mathfrak{g}}$ with the following two properties: for every root $\alpha$ , either $\alpha$ or $-\alpha$ belong to $\Phi_{\mathfrak{g}}^{+}$ ; for every pair of roots $\alpha_{1},\alpha_{2}$ such that $\alpha_{1}+\alpha_{2}$ is a root, if $\alpha_{1},\alpha_{2}\in\Phi_{\mathfrak{g}}^{+}$ then $\alpha_{1}+\alpha_{2}\in\Phi_{\mathfrak{g}}^{+}$ . For $\mathfrak{gl}_{k}$ , one such choice is $\Phi_{\mathfrak{gl}_{k}}^{+}=\{e_{i}-e_{j}\mid i<j\}$ .

All choices of positive roots are equivalent under the action of a finite group $\mathcal{W}_{\mathfrak{g}}$ , called the Weyl group of $\mathfrak{g}$ . This group acts on $\mathfrak{h}$ and hence on $\mathfrak{h}^{*}$ ; the action of $\mathfrak{h}^{*}$ sends the set of roots to itself. All possible sets of positive roots are obtained one from the other via the action of $\mathcal{W}_{\mathfrak{g}}$ . The Weyl group of $\mathfrak{gl}_{k}$ is the permutation group $\mathfrak{S}_{k}$ on $k$ elements. If $\mathfrak{h}$ is the Cartan subalgebra of diagonal matrices, then $\mathcal{W}_{\mathfrak{g}}$ acts by permuting the diagonal elements; the induced action on $\mathfrak{h}^{*}$ permutes the weights $e_{i}$ : for $\sigma\in\mathfrak{S}_{k}$ , $\sigma\cdot e_{i}$ is the weight $e_{\sigma^{-1}(i)}$ .

Since for every root $\alpha$ , either $\alpha$ or $-\alpha$ is positive, the weight decomposition of $\mathfrak{g}$ gives $\mathfrak{g}=\mathfrak{h}\oplus\bigoplus_{\alpha\in\Phi_{\mathfrak{g}}^{+}}(% \mathfrak{g}_{\alpha}\oplus\mathfrak{g}_{-\alpha})$ . In the case of $\mathfrak{gl}_{k}$ , this decomposition is $\mathfrak{gl}_{k}=\mathfrak{h}\oplus\bigoplus_{i<j}(\mathbb{C}E_{ij}\oplus% \mathbb{C}E_{ji})$ . A raising operator (resp. lowering operator) is an element $X\in\bigoplus_{\alpha\in\Phi_{\mathfrak{g}}^{+}}\mathfrak{g}_{\alpha}$ (resp. $X\in\bigoplus_{\alpha\in\Phi_{\mathfrak{g}}^{+}}\mathfrak{g}_{-\alpha}$ ). Let $\mathfrak{n}=\bigoplus_{\alpha\in\Phi_{\mathfrak{g}}^{+}}$ be the space of raising operators; the condition that a root $\alpha_{1}+\alpha_{2}$ is positive whenever $\alpha_{1},\alpha_{2}$ are positive make $\mathfrak{n}$ into a Lie algebra.

For $\mathfrak{gl}_{k}$ , the space $\mathfrak{n}=\textup{span}\{E_{i,j}:i<j\}$ of raising operators is the space of strictly upper triangular matrices and the space of lowering operators is the space of strictly lower triangular matrices.

Let $V$ be a representation of $\mathfrak{g}$ . A highest weight vector for $V$ is a weight vector $v\in V$ with the property that $\mathfrak{n}.v=0$ . The corresponding weight is called a highest weight for $V$ . When $\mathfrak{g}=\mathfrak{gl}_{k}$ and $V$ is a space of metapolynomials, it is not hard to verify that this condition is equivalent to the characterization of highest weight metapolynomials in Section 1; the characterization in terms of tableaux is explained in details in Section 4.5. A fundamental result in representation theory is that if $V$ is irreducible, then $V$ has a unique highest weight and this highest weight uniquely determines $V$ up to isomorphism [32, Prop. 14.13]. In particular, this result classifies finite-dimensional representations of $\mathfrak{g}$ .

Only a subset of weights occur as highest weights of finite-dimensional irreducible representations. Such vectors are called dominant weights and their characterization in general requires the introduction of a suitable inner product structure on $\mathfrak{h}^{*}$ , which is not straightforward. Let $\Lambda^{+}$ denote the subset of the weight lattice consisting of dominant weights. The representation associated to the highest weight $\lambda$ is denoted $V_{\lambda}$ and it is the unique $\mathfrak{g}$ -representation having highest weight $\lambda$ . In the case of $\mathfrak{gl}_{k}$ , the set of dominant weights consist of weights $\lambda=(\lambda_{1},\ldots,\lambda_{k})$ such that $\lambda_{j}\geq\lambda_{j+1}$ . If $\lambda_{i}\geq 0$ for every $i$ , we usually identify the weight $\lambda$ with a partition of length $k$ .

Example 4.8.

We determine the highest weights vectors in the representations $\mathbb{C}[x_{1},x_{2},x_{3}]_{2}$ and $\mathbb{C}[\mathbb{C}[x_{1},x_{2},x_{3}]_{2}]_{3}$ . The space of raising operators of $\mathfrak{gl}_{3}$ is $\mathfrak{n}=\textnormal{span}\{E_{12},E_{23},E_{13}\}$ of upper triangular matrices. The highest weight vectors are weight vectors characterized by the condition $\mathfrak{n}.v=0$ . Since $E_{13}=[E_{12},E_{23}]$ , the condition $\mathfrak{n}.v=0$ is equivalent to $E_{12}.v=E_{23}.v=0$ .

For $\mathbb{C}[x_{1},x_{2},x_{3}]_{2}$ , one can check the unique highest weight vector is $x_{3}^{2}$ and the corresponding highest weight is $(0,0,-2)$ . Therefore $\mathbb{C}[x_{1},x_{2},x_{3}]_{2}$ is irreducible, and it is isomorphic to the $\mathfrak{gl}_{3}$ -representation $V_{(0,0,-2)}$ .

For $\mathbb{C}[\mathbb{C}[x,y,z]_{2}]_{3}$ , the highest weight vectors are the metapolynomials

\begin{gathered}c_{2,0,0}^{3},\qquad\quad c_{2,0,0}c_{1,1,0}^{2}-4c_{2,0,0}^{2% }c_{0,2,0}\qquad\quad\text{and}\\ 4c_{2,0,0}c_{0,2,0}c_{0,0,2}-c_{0,0,2}c_{1,1,0}^{2}+c_{1,0,1}c_{1,1,0}c_{0,1,1% }-c_{0,2,0}c_{1,0,1}^{2}-c_{2,0,0}c_{0,1,1}^{2}.\end{gathered}

Their weights are $(6,0,0)$ , $(4,2,0)$ and $(2,2,2)$ . Therefore $\mathbb{C}[\mathbb{C}[x_{1},x_{2},x_{3}]_{2}]_{3}$ is a direct sum of three irreducible $\mathfrak{gl}_{3}$ -representations

\mathbb{C}[\mathbb{C}[x_{1},x_{2},x_{3}]_{2}]_{3}=V_{(6,0,0)}\ \oplus\ V_{(4,2% ,0)}\ \oplus\ V_{(2,2,2)}.\

4.3 Universal enveloping algebra

The universal enveloping algebra of a Lie algebra $\mathfrak{g}$ is an associative algebra associated to the Lie algebra $\mathfrak{g}$ . It is used to study representation theory of Lie algebras using representation theory of associative algebras.

A representation of an associative (unital) algebra $\mathcal{A}$ is a vector space $V$ equipped with a homomorphism of associative algebras $\rho\colon\mathcal{A}\to\textnormal{End}(V)$ . For $v\in V$ and $U\in\mathcal{A}$ , write $U.v=\rho(U)v$ , as in the Lie algebra setting. Subrepresentations and equivariant maps are defined for representations of an associative algebra in the same way as for Lie algebra representations. For a subset $S\subseteq\mathcal{A}$ , the subalgebra generated by $S$ is the smallest subalgebra of $\mathcal{A}$ containing $S$ ; explicitly, it can be realized as the set of (noncommutative) polynomials in elements of $S$ .

Let $\mathfrak{g}$ be a Lie algebra. Consider a representation $\rho\colon\mathfrak{g}\to\textnormal{End}(V)$ . Since $\textnormal{End}(V)$ is an associative algebra, we can consider the subalgebra of $\textnormal{End}(V)$ generated by the linear maps in the image $\rho(\mathfrak{g})$ . Since $\rho$ is a representation, these generators satisfy the relations

\rho(X)\rho(Y)-\rho(Y)\rho(X)=\rho([X,Y]).

(6)

The universal enveloping algebra $\mathcal{U}(\mathfrak{g})$ is an associative algebra constructed in such a way that the relations (6) are forced for every representation $\rho$ of $\mathcal{U}(\mathfrak{g})$ . It is a quotient of the tensor algebra $\mathcal{T}(\mathfrak{g})$ over $\mathfrak{g}$ . The tensor algebra is spanned by formal products of elements of $\mathfrak{g}$ ,

\displaystyle\mathcal{T}(\mathfrak{g})=\bigoplus_{k=0}^{\infty}\mathfrak{g}^{% \otimes k}=\mathbb{C}\oplus\mathfrak{g}\oplus\mathfrak{g}^{\otimes 2}\oplus% \mathfrak{g}^{\otimes 3}\oplus\cdots

(7)

with multiplication induced by the tensor products $\otimes\colon\mathfrak{g}^{\otimes p}\times\mathfrak{g}^{\otimes q}\to% \mathfrak{g}^{\otimes(p+q)}$ . In particular, the tensor algebra is graded, with $\mathfrak{g}^{\otimes p}$ being the component of degree $p$ . Consider the ideal $\mathcal{I}(\mathfrak{g})\subset\mathcal{T}(\mathfrak{g})$ generated by the elements of the form

X\otimes Y-Y\otimes X-[X,Y]

for $X,Y\in\mathfrak{g}$ . The universal enveloping algebra of $\mathfrak{g}$ is defined as $\mathcal{U}(\mathfrak{g})=\mathcal{T}(\mathfrak{g})/\mathcal{I}(\mathfrak{g})$ . The multiplication in $\mathcal{U}(\mathfrak{g})$ is denoted by the usual multiplication sign rather than $\otimes$ . The inclusion of $\mathfrak{g}$ into $\mathcal{T}(\mathfrak{g})$ (as a vector space) gives rise to a linear map $\mathfrak{g}\to\mathcal{U}(\mathfrak{g})$ , which is also injective. We identify $\mathfrak{g}$ with the image of this injection. The elements of $\mathcal{T}(\mathfrak{g})$ and, therefore, $\mathcal{U}(\mathfrak{g})$ can be written as noncommutative polynomials in elements of $\mathfrak{g}$ . When $\mathfrak{g}$ is abelian (for instance, in the case of a Cartan algebra), the ideal $\mathcal{I}(\mathfrak{g})$ is indeed homogeneous, since $[X,Y]=0$ ; in this case $\mathcal{U}(\mathfrak{g})$ is the symmetric algebra of $\mathfrak{g}$ , isomorphic to the polynomial ring on $\mathfrak{g}^{*}$ .

By construction of the ideal $\mathcal{I}(\mathfrak{g})$ we have $XY-YX=[X,Y]$ in $\mathcal{U}(\mathfrak{g})$ for every $X,Y\in\mathfrak{g}$ . This implies that every representation of $\mathcal{U}(\mathfrak{g})$ restricts to a Lie algebra representation of the Lie algebra $\mathfrak{g}$ , via the embedding $\mathfrak{g}\subseteq\mathcal{U}(\mathfrak{g})$ ; conversely every representation $\rho\colon\mathfrak{g}\to\textnormal{End}(V)$ of $\mathfrak{g}$ uniquely extends to a representation of $\mathcal{U}(\mathfrak{g})$ by setting $\rho(X_{1}X_{2}\dots X_{\ell})=\rho(X_{1})\rho(X_{2})\dots\rho(X_{\ell})$ for all $X_{i}\in\mathfrak{g}$ .

Note that in general the ideal $\mathcal{I}(\mathfrak{g})$ is not homogeneous, so $\mathcal{U}(\mathfrak{g})$ does not inherit the grading from the tensor algebra $\mathcal{T}(\mathfrak{g})$ . However, $\mathcal{U}(\mathfrak{g})$ has a filtration, in the following sense: define $\mathcal{U}(\mathfrak{g})_{\leq\ell}=\{X+\mathcal{I}(\mathfrak{g})\mid X\in% \bigoplus_{k=0}^{\ell}\mathfrak{g}^{\otimes k}\}$ ; then $\mathcal{U}(\mathfrak{g})_{\leq\ell}\subseteq\mathcal{U}(\mathfrak{g})_{\leq(% \ell+1)}$ for every $\ell$ , and if $X\in\mathcal{U}(\mathfrak{g})_{\leq p},Y\in\mathcal{U}(\mathfrak{g})_{\leq q}$ then $XY\in\mathcal{U}(\mathfrak{g})_{\leq(p+q)}$ .

In particular, the elements of $\mathcal{U}(\mathfrak{g})_{\leq\ell}$ are represented by noncommutative polynomials of degree at most $\ell$ in elements of $\mathfrak{g}$ . The length of an element $X\in\mathcal{U}(\mathfrak{g})$ is the minimal $\ell$ such that $X\in\mathcal{U}(\mathfrak{g})_{\leq\ell}$ .

Theorem 4.9 (Poincaré–Birkhoff–Witt [42, Theorem 9.10]).

Let $X_{1},\dots,X_{r}$ be a basis of $\mathfrak{g}$ . Then the set of ordered monomials $X_{i_{1}}X_{i_{2}}\cdots X_{i_{d}}$ , $i_{1}\leq i_{2}\leq\cdots\leq i_{d}$ is a basis of $\mathcal{U}(\mathfrak{g})$ . Moreover, the set of ordered monomials of length at most $\ell$ is a basis of the subspace $\mathcal{U}(\mathfrak{g})_{\leq\ell}$ of elements with length at most $\ell$ .

In fact, we will only use that ordered monomials are a set of generators for the spaces $\mathcal{U}(\mathfrak{g})_{\leq\ell}$ . This is proved explicitly in Theorem B.1. The Poincaré–Birkhoff–Witt theorem (PBW theorem) shows that elements of $\mathcal{U}(\mathfrak{g})$ have unique representation as noncommutative polynomials in $X_{1},\dots,X_{r}$ with ordered terms, and the length of the element is given by the longest monomial in this polynomial.

Example 4.10.

Consider $\mathfrak{g}=\mathfrak{gl}_{2}$ with a $\mathfrak{gl}_{2}$ -representation $V$ . Then $F\coloneqq E_{2,1},E\coloneqq E_{1,2},H_{i}\coloneqq E_{i,i}$ gives an ordered basis $(F,E,H_{1},H_{2})$ of $\mathfrak{gl}_{2}$ . Examples of elements of $\mathcal{U}(\mathfrak{gl}_{2})$ are $H_{1}EF$ and $1-\tfrac{1}{2}FE+\tfrac{1}{12}F^{2}E^{2}$ . Note that these are formal products, not matrix multiplication (general Lie algebras do not have this additional algebra structure). Taking $v\in V$ , the second element acts as $(1-\tfrac{1}{2}FE+\tfrac{1}{12}F^{2}E^{2}).v=v-\tfrac{1}{2}F.(E.v)+\tfrac{1}{1% 2}F.(F.(E.(E.v)))\in V$ . The PBW theorem guarantees that these elements can be written as polynomials with ordered monomials. Indeed, we have

	$\displaystyle H_{1}EF$	$\displaystyle=H_{1}(FE+[E,F])=H_{1}FE+H_{1}(H_{1}-H_{2})$
		$\displaystyle=\cdots=FEH_{1}+2FE+H_{1}^{2}-H_{1}H_{2}.\$

4.4 Central characters and Casimir elements

Let $\mathfrak{g}$ be a Lie algebra. An element $X\in\mathcal{U}(\mathfrak{g})$ of the universal enveloping algebra is central if $XY=YX$ for every $Y\in\mathcal{U}(\mathfrak{g})$ (or equivalently every $Y\in\mathfrak{g}$ ). The center $\mathcal{Z}(\mathfrak{g})$ of $\mathcal{U}(\mathfrak{g})$ is the set of all central elements; $\mathcal{Z}(\mathfrak{g})$ is a commutative associative subalgebra of $\mathcal{U}(\mathfrak{g})$ .

A representation $\rho\colon\mathfrak{g}\to\textnormal{End}(V)$ of $\mathfrak{g}$ extends to a representation of $\mathcal{U}(\mathfrak{g})$ , and if $X\in\mathcal{Z}(\mathfrak{g})$ is a central element, the map $\rho(X):V\to V$ is $\mathcal{U}(\mathfrak{g})$ -equivariant. If $V$ is irreducible, then by Schur’s lemma (Lemma 4.4) $\rho(X)$ is a multiplication by some scalar $\chi_{V}(X)$ . More precisely, $\rho$ induces a $1$ -dimensional representation $\chi_{V}:\mathcal{Z}(\mathfrak{g})\to\mathbb{C}$ . This representation is called the central character of $V$ .

It is a crucial fact that for Lie algebras $\mathfrak{g}$ of reductive groups central characters separate non-isomorphic irreducible representations.

Theorem 4.11 ([65], see also [10, §VIII.8.5, Cor.2]).

Let $\mathfrak{g}$ be a reductive Lie algebra. If $V$ and $W$ are irreducible representations of $\mathfrak{g}$ and the central characters $\chi_{V}$ and $\chi_{W}$ coincide, then $V$ and $W$ are isomorphic.

It follows that for reductive $\mathfrak{g}$ the isotypic components of a $\mathfrak{g}$ -representation are also isotypic components of the induced $\mathcal{Z}(\mathfrak{g})$ -representation. More specifically, if a $\mathfrak{g}$ -representation $V$ decomposes as $\bigoplus_{\lambda\in\Lambda}V_{\lambda}^{\oplus m_{\lambda}}$ with pairwise non-isomorphic $V_{\lambda}$ , then as a $\mathcal{Z}(\mathfrak{g})$ -representation we have $V\cong\bigoplus_{\lambda\in\Lambda}\chi_{\lambda}^{\oplus m_{\lambda}\cdot\dim V% _{\lambda}}$ , where we denote by $\chi_{\lambda}$ the $1$ -dimensional representation of $\mathcal{Z}(\mathfrak{g})$ corresponding to the central character of $V_{\lambda}$ .

Example 4.12.

Consider the $\mathfrak{gl}_{3}$ representation $V=\mathbb{C}[x_{1},x_{2},x_{3}]_{d}$ of homogeneous degree 3 polynomials in three variables (˜4.1). Consider the element $I\coloneqq-(E_{1,1}+E_{2,2}+E_{3,3})$ . Clearly, $I\in\mathcal{Z}(\mathfrak{gl}_{3})$ . We determine the value of the central characters. Take $f\in V$ . We find

\displaystyle I.f=x_{1}\frac{\partial}{\partial x_{1}}f+x_{2}\frac{\partial}{% \partial x_{2}}f+x_{3}\frac{\partial}{\partial x_{3}}f=df.

So $\chi_{V}(I)=d$ . As a simple applications of Theorem 4.11, this allows us to conclude $\mathbb{C}[x_{1},x_{2},x_{3}]_{d}$ and $\mathbb{C}[x_{1},x_{2},x_{3}]_{d^{\prime}}$ contain no isomorphic irreducible subrepresentations unless $d=d^{\prime}$ .

When $\mathfrak{g}$ is the Lie algebra of a reductive group, then $\mathcal{Z}(\mathfrak{g})$ can be described explicitly as the ring of invariants for the the action of the Weyl group on the Cartan subalgebra. Note that since the Cartan subalgebra $\mathfrak{h}$ is abelian, the universal enveloping algebra $\mathcal{U}(\mathfrak{h})$ is in fact commutative and can be identified with the polynomial algebra $\mathbb{C}[\mathfrak{h}^{*}]$ . Recall that the Weyl group $\mathcal{W}_{\mathfrak{g}}$ acts on $\mathfrak{h}$ and, therefore, on $\mathcal{U}(\mathfrak{h})\cong\mathbb{C}[\mathfrak{h}^{*}]$ .

Theorem 4.13 (Harish–Chandra isomorphism, [44, Ch. 23];[6]).

Let $\mathfrak{g}$ be a reductive algebra and let $\mathfrak{h}$ be a Cartan subalgebra. The center $\mathcal{Z}(\mathfrak{g})$ of the universal enveloping algebra is isomorphic to the algebra of invariants $\mathcal{U}(\mathfrak{h})^{\mathcal{W}_{\mathfrak{g}}}$ . Moreover, if $\dim\mathfrak{h}=k$ , there exist algebraically independent $C_{1},\dots,C_{k}\in\mathcal{U}(\mathfrak{g})$ such that $\mathcal{Z}(\mathfrak{g})=\mathbb{C}[C_{1},\dots,C_{k}]$ . The lengths of these elements coincide with the degrees of the fundamental invariants of $\mathcal{U}(\mathfrak{h})^{\mathcal{W}_{\mathfrak{g}}}$ .

The generators $C_{1},\dots,C_{k}$ of the center $\mathcal{Z}(\mathfrak{g})$ are known as Casimir elements. These generators are not unique.

Consider the case of $\mathfrak{gl}_{k}$ , with $\mathfrak{h}$ the Cartan subalgebra of diagonal matrices. Then $\mathcal{W}_{\mathfrak{gl}_{k}}$ is the symmetric group $\mathfrak{S}_{k}$ , and it acts on $\mathfrak{h}$ by permuting the diagonal elements. Then $\mathcal{U}(\mathfrak{h})$ is the polynomial ring in $k$ variables, and $\mathcal{U}(\mathfrak{h})^{\mathcal{W}_{\mathfrak{gl}_{k}}}$ is the subring of polynomials invariant under permutation of variables: this is the classical ring of symmetric polynomials in $k$ variables. It is generated, for instance, by the elementary symmetric polynomials, which have degrees $1,\ldots,k$ . These numbers give lengths of Casimir elements generating the center $\mathcal{Z}(\mathfrak{g})$ . There are several constructions of Casimir elements, one possible choice being

\displaystyle C_{p}\coloneqq\sum_{i_{1}=1}^{k}\dots\sum_{i_{p}=1}^{k}E_{i_{1},% i_{2}}E_{i_{2},i_{3}}\cdots E_{i_{p},i_{1}}\quad\text{with }1\leq p\leq k.

(8)

Example 4.14.

Let $\mathfrak{g}=\mathfrak{gl}_{2}$ . Then the Casimir elements are given by

\displaystyle C_{1}=E_{1,1}+E_{2,2}\qquad\text{and}\qquad C_{2}=E_{1,1}E_{1,1}% +E_{1,2}E_{2,1}+E_{2,1}E_{1,2}+E_{2,2}E_{2,2}.

We will use ˜4.2 to evaluate the application of $C_{1}$ and $C_{2}$ to the metapolynomials

\displaystyle\Delta=c_{11}^{2}+2\,c_{02}c_{20}\qquad\text{and}\qquad\Gamma=-c_% {11}^{2}+4\,c_{02}c_{20}.

We find that

\displaystyle C_{1}.\Delta=E_{1,1}.\Delta+E_{2,2}.\Delta=2c_{11}^{2}+4c_{02}c_% {20}+2c_{11}^{2}+4c_{02}c_{20}=4\Delta

and similarly $C_{1}.\Gamma=4\Gamma$ (in fact, one can show $C_{1}$ always scales a metapolynomial of format $(\delta,d,k)$ by $d\delta$ ). We also compute

	$\displaystyle E_{2,1}.\Delta$	$\displaystyle=2\,c_{02}^{2}c_{11}+2\,c_{11}^{2}c_{02}+2\cdot 0c_{20}+2\,c_{02}% c_{11}=6\,c_{02}^{2}c_{11}$
	$\displaystyle(E_{1,2}E_{2,1}).\Delta$	$\displaystyle=6\,c_{11}c_{11}+6\cdot 2\,c_{02}c_{20}=6\Delta$

By symmetry of multiindices in the metapolynomial we know $(E_{2,1}E_{1,2}).\Delta=6\Delta$ too. An analogous computation shows $E_{2,1}.\Gamma=0$ and $E_{1,2}.\Gamma=0$ . We find

\displaystyle C_{2}.\Delta=\big{(}2^{2}+6+6+2^{2}\big{)}\Delta=20\Delta\qquad% \text{and}\qquad C_{2}.\Gamma=\big{(}2^{2}+0+0+2^{2}\big{)}\Delta=8\Delta.

We obtain that $\Delta$ and $\Gamma$ live in different isotypic components with respect to $\mathcal{Z}(\mathfrak{gl}_{2})$ , and hence with respect to $\mathfrak{gl}_{2}$ .

The eigenvalues of these Casimir elements on irreducible representations of $\mathfrak{gl}_{k}$ are computed by Perelomov and Popov [64]:

\displaystyle\chi_{\lambda}(C_{p})=\mathsf{Tr}(A_{\lambda}^{p}E)

(9)

where $E$ is the $k\times k$ matrix consisting of all ones, and the entries of the $k\times k$ matrix $A_{\lambda}=(a^{(\lambda)}_{ij})$ are given by

\displaystyle a^{(\lambda)}_{ij}=\begin{cases}\lambda_{i}+k-i,&\text{if $i=j$,% }\\ 0,&\text{if $i>j$,}\\ -1,&\text{if $i<j$.}\end{cases}

(10)

Example 4.15.

Observe first that $\mathsf{Tr}(A_{\lambda}^{p}E)$ is simply the sum of the entries of $A_{\lambda}^{p}$ . Consider again Example 4.14. We compute the formula in Equation 9.

	$\displaystyle A_{(4,0)}$	$\displaystyle=\left[\begin{smallmatrix}5&-1\\ 0&2\\ \end{smallmatrix}\right]\ \text{ and thus }\ \chi_{(4,0)}(C_{2})=\mathsf{Tr}% \left(\left[\begin{smallmatrix}25&-7\\ 0&4\\ \end{smallmatrix}\right]\left[\begin{smallmatrix}1&1\\ 1&1\\ \end{smallmatrix}\right]\right)=20$
	$\displaystyle A_{(2,2)}$	$\displaystyle=\left[\begin{smallmatrix}3&-1\\ 0&2\\ \end{smallmatrix}\right]\ \text{ and thus }\ \chi_{(2,2)}(C_{2})=\mathsf{Tr}% \left(\left[\begin{smallmatrix}9&-5\\ 0&4\\ \end{smallmatrix}\right]\left[\begin{smallmatrix}1&1\\ 1&1\\ \end{smallmatrix}\right]\right)=8.$
Observe that this matches our results in Example 4.14. We give one more example for $\mathfrak{gl}_{3}$ .
	$\displaystyle A_{(6,0,0)}$	$\displaystyle=\left[\begin{smallmatrix}8&-1&-1\\ 0&1&-1\\ 0&0&0\end{smallmatrix}\right]\ \text{ and thus }\ \chi_{(6,0,0)}(C_{2})=% \mathsf{Tr}\left(\left[\begin{smallmatrix}64&-9&-7\\ 0&1&-1\\ 0&0&0\end{smallmatrix}\right]\left[\begin{smallmatrix}1&1&1\\ 1&1&1\\ 1&1&1\end{smallmatrix}\right]\right)=48.\$

4.5 Gelfand–Tsetlin theory

Gelfand–Tsetlin bases are used to explicitly construct irreducible representations of some classical Lie algebras. The explicit bases first appeared in [35] without much explanation. The construction was expanded upon by Želobenko [72] and independently by Baird and Biedenharn [4]. It can be explained in terms of restrictions of irreducible representations along a chain of Lie algebra inclusions.

Let $\mathfrak{a}$ be a Lie subalgebra of $\mathfrak{b}$ . Every representation $V$ of $\mathfrak{b}$ can be regarded as a representation of $\mathfrak{a}$ using this inclusion. The resulting representation is called the restriction of $V$ to $\mathfrak{a}$ and is denoted as $V{\downarrow}^{\mathfrak{b}}_{\mathfrak{a}}$ .

Let $\mathfrak{g}_{1}\subset\mathfrak{g}_{2}\subset\dots\subset\mathfrak{g}_{k}$ be an inclusion chain of reductive Lie algebras. We call this chain a Gelfand–Tsetlin chain if $\mathfrak{g}_{1}$ is abelian and every irreducible representation $V$ of $\mathfrak{g}_{\ell}$ ( $1<\ell\leq k$ ), when restricted to $\mathfrak{g}_{\ell-1}$ , is a multiplicity-free completely reducible representation, that is,

\displaystyle V_{\lambda}{\downarrow}^{\mathfrak{g}_{\ell}}_{\mathfrak{g}_{% \ell-1}}\cong\bigoplus_{\mu\in R_{\ell}(\lambda)}V_{\mu}

(11)

for some set $R_{\ell}(\lambda)$ of isomorphism types of irreducible representations of $\mathfrak{g}_{i-1}$ . We write $\mu\to\lambda$ if $V_{\mu}$ appears in the decomposition for $V_{\lambda}$ .

Let $V_{\lambda}$ be a irreducible representation of $\mathfrak{g}_{k}$ . By repeatedly restricting irreducible representations of $\mathfrak{g}_{i}$ we obtain a decomposition of $V_{\lambda}$ as a representation of $\mathfrak{g}_{1}$ .

\displaystyle V_{\lambda}{\downarrow}^{\mathfrak{g}_{k}}_{\mathfrak{g}_{1}}=% \bigoplus_{\lambda^{(1)}\to\lambda^{(2)}\to\dots\to\lambda^{(k)}=\lambda}V_{% \lambda^{(1)}}

(12)

Since $\mathfrak{g}_{1}$ is abelian, its irreducible representations are $1$ -dimensional, so the decomposition above distinguishes a set of $1$ -dimensional subspaces in $V_{\lambda}$ indexed by chains $\lambda^{(1)}\to\lambda^{(2)}\to\dots\to\lambda^{(k)}$ called Gelfand–Tsetlin patterns. We denote the subspace of $V_{\lambda^{(k)}}$ corresponding to a Gelfand–Tsetlin pattern $T=\lambda^{(1)}\to\lambda^{(2)}\to\dots\to\lambda^{(k)}$ by $V_{T}$ .

The inclusions $\mathfrak{g}_{\ell}\subseteq\mathfrak{g}_{k}$ give an inclusion of universal enveloping algebras $\mathcal{U}(\mathfrak{g}_{\ell})\subseteq\mathcal{U}(\mathfrak{g}_{k})$ , and therefore a chain $\mathcal{U}(\mathfrak{g}_{1})\subset\mathcal{U}(\mathfrak{g}_{2})\subset\dots% \subset\mathcal{U}(\mathfrak{g}_{k})$ . The Gelfand–Tsetlin algebra $\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g}_{k})$ of $\mathfrak{g}_{k}$ is the subalgebra of $\mathcal{U}(\mathfrak{g})$ generated by all centers $\mathcal{Z}(\mathfrak{g}_{\ell})$ with $\ell\leq k$ . Since the center $\mathcal{Z}(\mathfrak{g}_{\ell})$ of $\mathcal{U}(\mathfrak{g}_{\ell})$ commutes with all elements of $\mathcal{U}(\mathfrak{g}_{\ell})$ , it commutes in particular with the centers $\mathcal{Z}(\mathfrak{g}_{j})$ for $j<\ell$ ; as a result, $\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g}_{k})$ is a commutative subalgebra.

Consider a Gelfand–Tsetlin pattern $T=\lambda^{(1)}\to\lambda^{(2)}\to\dots\to\lambda^{(k)}$ and the corresponding $1$ -dimensional subspace $V_{T}\subset V_{\lambda^{(k)}}$ . For every $\ell\leq k$ the subspace $V_{T}$ is contained in an irreducible representation of $\mathfrak{g}_{\ell}$ isomorphic to $V_{\lambda^{(\ell)}}$ , and the center $\mathcal{Z}(\mathfrak{g}_{\ell})$ acts on $V_{T}$ via the central character $\chi_{\lambda^{(\ell)}}$ . It follows that $V_{T}$ is a $1$ -dimensional representation of $\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g}_{k})$ given by a Gelfand–Tsetlin character $\chi_{T}\colon\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g}_{k})\to% \mathbb{C}$ such that $X.v=\chi_{T}(X)v$ for $X\in\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g}_{k})$ , $v\in V_{T}$ . More specifically, on $\mathcal{Z}(\mathfrak{g}_{\ell})$ we have $\chi_{T}(X)=\chi_{\lambda^{(\ell)}}(X)$ . Theorem 4.11 implies that different Gelfand–Tsetlin patterns correspond to different Gelfand–Tsetlin characters.

By the previous discussion, every completely reducible representation of $\mathfrak{g}_{k}$ is also completely reducible as a representation of $\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g}_{k})$ . That is, if $V$ is a completely reducible representation of $\mathfrak{g}_{k}$ with isotypic decomposition $V=\bigoplus_{\lambda\in\Lambda}V_{\lambda}^{\oplus m_{\lambda}}$ , then the action of $\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g}_{k})$ on $V$ splits the decomposition further into Gelfand–Tsetlin characters as

\displaystyle V=\bigoplus\limits_{T\colon\lambda^{(1)}\to\dots\to\lambda^{(k)}% ,\lambda^{(k)}\in\Lambda}\chi_{T}^{\oplus m_{\smash{\lambda^{(k)}}}}.

(13)

We call the components of this decomposition GZ-isotypic spaces of $V$ .

The classical case – used to construct a basis of irreducible representations of $\mathfrak{gl}_{n}$ – corresponds to the chain of inclusions $\mathfrak{gl}_{1}\subset\mathfrak{gl}_{2}\subset\dots\subset\mathfrak{gl}_{k}$ where $\mathfrak{gl}_{k-1}$ is included in $\mathfrak{gl}_{k}$ as the subalgebra of $\mathfrak{gl}_{k}$ consisting of matrices having the $k$ -th row and the $k$ -th column identically equal to $0$ . The Gelfand–Tsetlin algebra in this case is the polynomial algebra $\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g}_{k})=\mathbb{C}[C_{\ell,p}]$ generated by the Casimir elements

\displaystyle C_{\ell,p}\coloneqq\sum_{i_{1}=1}^{\ell}\dots\sum_{i_{p}=1}^{% \ell}E_{i_{1},i_{2}}E_{i_{2},i_{3}}\cdots E_{i_{p},i_{1}}\quad\text{with }1% \leq\ell\leq k\text{ and }1\leq p\leq\ell.

(14)

The irreducible representations of $\mathfrak{gl}_{k}$ correspond highest weights $\lambda=(\lambda_{1},\dots,\lambda_{k})$ with integer $\lambda_{1}\geq\dots\geq\lambda_{k}$ . The restriction $V_{\lambda}{\downarrow}^{\mathfrak{gl}_{k}}_{\mathfrak{gl}_{k-1}}$ is given by the classical branching rule (attributed to Schur in [58]) which states that $\mu\to\lambda$ if and only if $\mu$ and $\lambda$ interleave, that is $\lambda_{\ell}\geq\mu_{\ell}\geq\lambda_{\ell+1}$ for all $\ell$ , $1\leq\ell\leq k-1$ . Moreover, $E_{k,k}$ acts on the copy of $V_{\mu}$ in $V_{\lambda}$ as multiplication by $|\lambda|-|\mu|=\sum_{\ell=1}^{k-1}(\lambda_{k}-\mu_{k})$ .

A Gelfand-Tsetlin pattern is given by a sequence $\lambda^{(1)}\to\lambda^{(2)}\to\dots\to\lambda^{(k)}$ , that is, by integers $\lambda^{(\ell)}_{i}$ with $1\leq\ell\leq k$ , $1\leq i\leq\ell$ such that $\lambda^{(\ell)}_{i}\geq\lambda^{(\ell-1)}_{i}\geq\lambda^{(\ell)}_{i+1}$ , often arranged into a triangular shape, see Figure 2.

Figure 2: Gelfand–Tsetlin pattern of

\mathfrak{gl}_{k}

.

The $1$ -dimensional subspace $V_{T}$ corresponding to the pattern $T=\lambda^{(1)}\to\lambda^{(2)}\to\dots\to\lambda^{(k)}$ is spanned by a weight vector of weight $(|\lambda^{(1)}|,|\lambda^{(2)}|-|\lambda^{(1)}|,\dots,|\lambda^{(k)}|-|% \lambda^{(k-1)}|)$ . The generators $C_{\ell,p}$ of $\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{gl}_{k})$ act on this space as multiplications by the corresponding eigenvalues $\chi_{T}(C_{\ell,p})$ . Since $C_{\ell,p}$ is a Casimir operator for $\mathfrak{gl}_{\ell}$ , we have $\chi_{T}(C_{\ell,p})=\chi_{\lambda^{(\ell)}}(C_{\ell,p})=\mathsf{Tr}(A_{% \lambda^{(\ell)}}^{p}E)$ from Perelomov–Popov formula.

If $\lambda^{(k)}$ is a partition, that is, all $\lambda^{(k)}_{i}$ are nonnegative, then the Gelfand–Tsetlin patterns for $\mathfrak{gl}_{k}$ are in bijective correspondence with semistandard Young tableaux filled with numbers from $\{1,2,\dots,k\}$ . Recall that a Young tableau is semistandard whenever the numbers are strictly increasing along the columns, and weakly increasing along the rows.

A semistandard tableau $T$ gives rise to a sequence of partitions $\lambda^{(1)},\dots,\lambda^{(k)}$ where $\lambda^{(\ell)}$ is the shape of the tableau $T^{(\ell)}$ obtained from $T$ be removing all boxes labeled with numbers greater than $\ell$ . Semistandardness of $T$ guarantees that all $T^{(\ell)}$ are also semistandard tableaux and the interleaving property $\lambda^{(\ell)}_{i}\geq\lambda^{(\ell-1)}_{i}\geq\lambda^{(\ell)}_{i+1}$ holds (see e. g. [56, p.5]). The weight is given by the content of the tableau $T$ , that is, the vector $\mu=(\mu_{1},\dots,\mu_{k})$ where $\mu_{i}$ records the number of occurrences of the label $i$ in the tableau.

For example, the tableau gives

and the sequence of shapes is $\lambda^{(1)}=(2)$ , $\lambda^{(2)}=(4,1)$ , $\lambda^{(3)}=(4,2,0)$ , $\lambda^{(4)}=(4,2,2,0)$ . The corresponding weight is $(2,3,1,2)$ , the content of the tableau.

The superstandard tableau of shape $\lambda=(\lambda_{1},\dots,\lambda_{n})$ corresponds to the Gelfand-Tsetlin pattern with $\lambda^{(\ell)}=(\lambda_{1},\dots,\lambda_{\ell})$ . The corresponding $1$ -dimensional subspace of $V_{\lambda}$ contains the highest weight vectors. To prove this, recall that since $E_{i,j}$ with $i\neq j$ span root spaces of $\mathfrak{gl}_{k}$ , they shift the weights of weight vectors, that is, $E_{i,j}.v$ is a weight vector of weight $\mu+e_{i}-e_{j}$ . The content of the superstandard tableau of shape $\lambda$ is $\lambda$ , so every nonzero vector $v$ in the corresponding $1$ -dimensional subspace has weight $\lambda$ , and for every $E_{i,j}$ the vector $E_{i,j}.v$ has weight $\lambda+e_{i}-e_{j}$ . But there are no semistandard tableaux with shape $\lambda$ and content $\lambda+e_{i}-e_{j}$ when $i<j$ . Therefore, $E_{i,j}.v=0$ if $i<j$ , and it follows that $v$ is annihilated by every strictly upper triangular matrix.

5 Efficient construction of projectors

In this section we prove Theorem 1.1. We explain the construction of the projectors in Section 5.1, and describe the efficient circuit implementation in Section 5.2.

5.1 Construction of projectors

We construct the required projections as projections onto a common eigenspace of several commuting matrices. The construction is elementary and is based on the classical construction of eigenprojectors from basic linear algebra.

We present the construction in full generality in Theorem 5.2. The projectors in the cases relevant for Theorem 1.1 are obtained by applying the general construction to suitable commutative subalgebras of the universal enveloping algebra $\mathcal{U}(\mathfrak{gl}_{k})$ , see Table 1. If $\mathcal{A}$ is a commutative algebra generated by $U_{1},\dots,U_{q}$ , then a representation of $\rho:\mathcal{A}\to\textnormal{End}(V)$ is uniquely determined by $\rho(U_{1}),\ldots,\rho(U_{q})$ , which are $q$ commuting endomorphisms of $V\to V$ . Every irreducible representation of $\mathcal{A}$ is $1$ -dimensional, so it is given by an algebra homomorphism $\chi\colon\mathcal{A}\to\mathbb{C}$ . In other words, an irreducible representation is spanned by a common eigenvector of the generators $U_{1},\dots,U_{q}$ of $\mathcal{A}$ with the corresponding eigenvalues $\chi(U_{1}),\dots,\chi(U_{q})$ .

Recall that a representation is called completely reducible if it can be decomposed into a direct sum of irreducible representations. All representations in this paper have this property. For a commutative algebra this means that the generators of the algebra act not just by commuting but by simultaneously diagonalizable linear maps.

We slightly abuse notation and denote the character $\chi\colon\mathcal{A}\to\mathbb{C}$ and the corresponding irreducible representation by the same letter. Every completely reducible representation $V$ of $\mathcal{A}$ has a unique isotypic decomposition

\displaystyle V\cong\bigoplus_{\lambda\in\Lambda}\chi_{\lambda}^{\oplus m_{% \lambda}},

(15)

where $\Lambda$ is a set indexing irreducible representations of $\mathcal{A}$ . We denote the isotypic component $\chi_{\lambda}^{\oplus m_{\lambda}}$ in $V$ by $V_{\mathcal{A},\lambda}$ .

The length of the projectors as elements of $\mathcal{U}(\mathfrak{g})$ depends mainly on the number of different isotypic components of the representation.

Definition 5.1.

Let $V$ be a completely reducible representation of an algebra $\mathcal{A}$ . We call the number of isomorphism types of irreducible subrepresentations of $V$ the diversity of $V$ .

Theorem 5.2.

Let $\mathcal{A}$ be a commutative algebra generated by $U_{1},\dots,U_{q}$ and $V$ be a completely reducible representation of $\mathcal{A}$ with diversity at most $p$ . For every irreducible representation $\chi_{\lambda}$ of $\mathcal{A}$ there exists a polynomial $f_{\lambda}$ of degree at most $p-1$ such that

\displaystyle f_{\lambda}(U_{1},\dots,U_{q}).x=\Pi_{\lambda}x

(16)

where $\Pi_{\lambda}\colon V\to V$ is the unique $\mathcal{A}$ -equivariant projection onto the isotypic component $V_{\mathcal{A},\lambda}$ .

Proof.

Let $\Lambda$ be the set of isomorphism types appearing in the isotypic decomposition of $V$ , so that $V\cong\bigoplus_{\mu\in\Lambda}V_{\mathcal{A},\mu}$ with $V_{\mathcal{A},\mu}\neq 0$ . An element $U\in\mathcal{A}$ acts as $U.x=\chi_{\mu}(U)x$ on $V_{\mathcal{A},\mu}$ . If $\lambda\notin\Lambda$ , set $f_{\lambda}=0$ .

Fix $\lambda\in\Lambda$ . For every $\mu\in\Lambda$ with $\mu\neq\lambda$ , let $U_{i_{\mu}}$ be a generator such that $\chi_{\mu}(U_{i_{\mu}})\neq\chi_{\lambda}(U_{i_{\mu}})$ . Such generator exist because $\chi_{\lambda}$ and $\chi_{\mu}$ are different characters of $\mathcal{A}$ . Define

\displaystyle P_{\lambda}\coloneqq\prod_{\mu\in\Lambda,\mu\neq\lambda}\frac{U_% {i_{\mu}}-\chi_{\mu}(U_{i_{\mu}})}{\chi_{\lambda}(U_{i_{\mu}})-\chi_{\mu}(U_{i% _{\mu}})}\quad\in\mathcal{A}.

(17)

The factor $\dfrac{U_{i_{\mu}}-\chi_{\mu}(U_{i_{\mu}})}{\chi_{\lambda}(U_{i_{\mu}})-\chi_{% \mu}(U_{i_{\mu}})}$ acts on $V$ as the zero map on $V_{\mathcal{A},\mu}$ and as the identity map on $V_{\mathcal{A},\lambda}$ ; moreover, its action maps isotypic components to themselves. The element $P_{\lambda}$ acts as the composition of these factors; therefore its image in $\textnormal{End}(V)$ is the projection $\Pi_{\lambda}$ onto $V_{\mathcal{A},\lambda}$ . Finally, since every factor is linear in $U_{1},\ldots,U_{q}$ , $P_{\lambda}$ is a polynomial in $U_{1},\ldots,U_{q}$ . Its degree is (at most) $p-1$ . $\hfill\blacktriangleleft$

The projections required in Theorem 1.1 arise as special cases of this construction. In each case, the image of the projection is an isotypic component of some commutative subalgebra $\mathcal{A}\subset\mathcal{U}(\mathfrak{gl}_{k})$ . Theorem 5.2 then gives a construction of the projectors as elements of $\mathcal{U}(\mathfrak{gl}_{k})$ , expressed as polynomials in the generators of $\mathcal{A}$ . The length of the projectors is easily bounded in terms of lengths of generators of $\mathcal{A}$ in $\mathcal{U}(\mathfrak{gl}_{K})$ and the diversity of $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ as a representation of $\mathcal{A}$ . Indeed, if the generators $U_{1},\dots,U_{q}$ of $\mathcal{A}$ have length at most $\ell$ , and the projectors are expressed as polynomials in $U_{1},\dots,U_{q}$ of degree at most $p-1$ , then the lengths of the projectors are bounded by $\ell(p-1)$ . The following table summarizes these parameters for the three cases considered.

Table 1: Isotypic components, generators of their corresponding subalgebras, and their diversity in

\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}

. See Equation 8 and Equation 14 for the definitions of

C_{p}

and

C_{\ell,p}

.

Isotypic components	Weight spaces	$\lambda$ -isotypic spaces	$T$ -isotypic spaces
Algebra $\mathcal{A}$	$\mathcal{U}(\mathfrak{h})\cong\mathbb{C}[\mathfrak{h}^{*}]$	$\mathcal{Z}(\mathfrak{gl}_{k})$	$\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{gl}_{k})$
Generators $U_{i}$	$\big{\{}E_{i,i}\mid i\in[k]\big{\}}$	$\big{\{}C_{p}\mid p\in[k]\big{\}}$	$\big{\{}C_{\ell,p}\mid\ell\in[k],p\in[\ell]\big{\}}$
Generator lengths	$1$	$\leq k$	$\leq k$
Diversity	$\leq(\delta d)^{k}$	$\leq(\delta d)^{k}$	$\leq(\delta d)^{k^{2}}$

$\blacktriangleright$ Remark 5.3.

In the construction of Theorem 5.2 we require knowledge of the value of $\chi_{\mu}$ evaluated on the generators $U_{i}$ , for all irreducible representation types $\mu$ occurring in the representation. For the weight spaces these values are given by the weights themselves, and for the other two algebra they can be computed using Equation 9. It is then also possible to remove any choices in the construction by taking for each term instead a linear combination $U$ of all $U_{i}$ with algebraically independent irrational weights. Since the values $\chi_{\mu}$ are always integer, this ensures $\chi_{\mu}(U)\neq\chi_{\lambda}(U)$ when $\mu\neq\lambda$ .

Example 5.4.

We construct and evaluate a $\lambda$ -isotypic projector for metapolynomials of format $(3,2,3)$ . From Example 4.8 we know $\Lambda=\{(6,0,0),(4,2,0),(2,2,2)\}$ . By Equation 9 we find that the Casimir element $C_{2}$ scales these three irreducible representations with different scalars, namely $48$ , $28$ and $12$ respectively. Hence we can use $C_{2}$ to construct the projectors from Theorem 5.2. Consider first the projector $P_{(6,0,0)}$ to the $(6,0,0)$ -isotypic component. We have that

\displaystyle P_{(6,0,0)}=\frac{C_{2}-\chi_{(2,2,2)}(C_{2})}{\chi_{(6,0,0)}(C_% {2})-\chi_{(2,2,2)}(C_{2})}\cdot\frac{C_{2}-\chi_{(4,2,0)}(C_{2})}{\chi_{(6,0,% 0)}(C_{2})-\chi_{(4,2,0)}(C_{2})}=\frac{C_{2}-12}{36}\cdot\frac{C_{2}-28}{20}.

Consider again the example $\Delta=c_{002}c_{020}c_{200}$ from the introduction. We will compute $P_{(6,0,0)}.\Delta$ . Using the equations in ˜4.2 we find

\displaystyle C_{2}.\Delta

\displaystyle=\sum_{i=1}^{3}\sum_{j=1}^{3}\big{(}E_{i,j}E_{j,i}\big{)}.\Delta=% 2\,c_{020}c_{101}^{2}+2\,c_{002}c_{110}^{2}+2\,c_{011}^{2}c_{200}+24\,c_{002}c% _{020}c_{200}.

It directly follows that

\displaystyle C_{2}.\Delta-28\Delta=2\,c_{020}c_{101}^{2}+2\,c_{002}c_{110}^{2% }+2\,c_{011}^{2}c_{200}-4\,c_{002}c_{020}c_{200}.

We apply $C_{2}$ again (at this point a computer algebra program is recommended) and find

\displaystyle C_{2}.(C_{2}.\Delta-28\Delta)=48\big{(}c_{020}c_{101}^{2}+c_{011% }c_{101}c_{110}+c_{002}c_{110}^{2}+c_{011}^{2}c_{200}\big{)}.

Hence,

	$\displaystyle 60\,P_{(6,0,0)}.\Delta$	$\displaystyle=\frac{C_{2}.(C_{2}.\Delta-28\Delta)-12(C_{2}.\Delta-28\Delta)}{12}$
		$\displaystyle=2\,c_{020}c_{101}^{2}+4\,c_{011}c_{101}c_{110}+2\,c_{002}c_{110}% ^{2}+2\,c_{011}^{2}c_{200}+4\,c_{002}c_{020}c_{200}.$

This is indeed the isotypic component as given in the introduction. The other two can be determined by an analogous computation.

5.1.1 Weight projectors

Let $V$ be a representation of a complex reductive Lie group $G$ . The action of $G$ on $V$ induces the action of the corresponding Lie algebra $\mathfrak{g}$ . Fix a maximal torus $T\subset G$ and let $\mathfrak{h}\subset\mathfrak{g}$ be the corresponding Cartan subalgebra. The torus $T$ is reductive, and the isotypic components of $V$ with respect to the action of $T$ are exactly the weight spaces. The action of $T$ induces the action of $\mathfrak{h}$ with the same isotypic components, so the action of $\mathfrak{h}$ is completely reducible.

Let $H_{1},\dots,H_{r}$ be a basis of the Cartan subalgebra $\mathfrak{h}$ . Since $\mathfrak{h}$ is abelian, the universal enveloping algebra $\mathcal{U}(\mathfrak{h})\subset\mathcal{U}(\mathfrak{g})$ is commutative. It can be identified with the polynomial algebra $\mathbb{C}[H_{1},\dots,H_{r}]$ . We can now apply Theorem 5.2 to obtain for every weight $\mu\in\mathfrak{h}^{*}$ an element $H_{\mu}\in\mathcal{U}(\mathfrak{g})$ such that $H_{\mu}.v$ is the projection of $v\in V$ onto the weight space of weight $\mu$ . The projectors $H_{\mu}$ are obtained as polynomial expressions $H_{\mu}=f_{\mu}(H_{1},\dots,H_{r})$ with $\deg f_{\mu}\leq p-1$ where $p$ is the diversity of $V$ as a representation of $\mathfrak{h}$ (or, equivalently, of $\mathcal{U}(\mathfrak{h})$ ), that is, the number of weights of $V$ . Since $H_{i}$ as elements of $\mathcal{U}(\mathfrak{g})$ have length $1$ , the length of $H_{\mu}$ is also bounded by $p-1$ .

We can specialize this construction to the action of $\mathfrak{gl}_{k}$ on the space of metapolynomials $W\coloneqq\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ . The standard Cartan subalgebra consists of all diagonal matrices, and we can take $H_{i}\coloneqq E_{i,i}$ . The weights appearing in $W$ correspond to $k$ -tuples of nonnegative integers summing to $\delta d$ (see Example 4.7). The number of such tuples is $\binom{\delta d+k-1}{k-1}\leq(\delta d)^{k}$ .

Corollary 5.5.

For each weight $\mu=(\mu_{1},\dots,\mu_{k})$ with $\sum_{i=1}^{k}\mu_{i}=\delta d$ there is an element $H_{\mu}\in\mathcal{U}(\mathfrak{gl}_{k})$ of length at most $(\delta d)^{k}$ which acts on $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ as the projector onto the weight space corresponding to $\mu$ .

5.1.2 Isotypic projectors

Let $V$ be a representation of a complex reductive Lie group $G$ with the corresponding Lie algebra $\mathfrak{g}$ . Then $V$ is completely reducible as a representation of $\mathfrak{g}$ , with the same isotypic components as for $G$ . As discussed in Section 4.4, they are also isotypic components of $V$ as a representation of $\mathcal{Z}(\mathfrak{g})$ , which is a commutative algebra generated by Casimir elements $C_{1},\dots,C_{r}$ .

Applying Theorem 5.2, we obtain for every highest weight $\lambda$ a corresponding element $Z_{\lambda}\in\mathcal{U}(\mathfrak{g})$ such that $Z_{\lambda}.v$ is the projection of $v$ onto the isotypic component of corresponding to the irreducible representation with highest weight $\lambda$ . The projectors $Z_{\lambda}$ are obtained as polynomial expressions $Z_{\lambda}=f_{\lambda}(C_{1},\dots,C_{r})$ with $\deg f_{\lambda}$ is at most $p-1$ , where $p$ is the diversity of $V$ as a representation of $\mathfrak{g}$ . It follows that if the Casimir elements $C_{1},\dots,C_{r}$ have length at most $\ell$ , then the length of $Z_{\lambda}$ is at most $\ell(p-1)$ .

For the Lie algebra $\mathfrak{gl}_{k}$ Casimir elements have length at most $k$ . Since every highest weight is a weight, the diversity of $\mathbb{C}[\mathbb{C}[x_{1},\dots,x_{k}]_{d}]_{\delta}$ is bounded by $(d\delta)^{k}$ as in the previous section.

Corollary 5.6.

For each partition $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}_{k}\,}{\scalebox{1.2}[0.7]{ % $\vdash$}_{k}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{% \scalebox{0.5}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{\delta d}$ there is an element $Z_{\lambda}\in\mathcal{U}(\mathfrak{gl}_{k})$ of length at most $k(\delta d)^{k}$ which acts on $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ as the projector onto the isotypic component corresponding to $\lambda$ .

5.1.3 Highest weight projectors

Since the highest weight subspace of weight $\lambda$ is exactly the weight $\lambda$ subspace of the isotypic component corresponding to the irreducible representation $V_{\lambda}$ , the projector onto the highest weight subspace is the composition $H_{\lambda}Z_{\lambda}$ of the projectors constructed in the previous sections.

Corollary 5.7.

For each partition $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}_{k}\,}{\scalebox{1.2}[0.7]{ % $\vdash$}_{k}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{% \scalebox{0.5}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{\delta d}$ there is an element $X_{\lambda}=H_{\lambda}Z_{\lambda}\in\mathcal{U}(\mathfrak{gl}_{k})$ of length at most $(k+1)(\delta d)^{k}$ which acts on $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ as the projector onto the highest weight space of weight $\lambda$ .

5.1.4 GZ-isotypic projectors

Let $V$ be a representation of a complex reductive Lie group $G$ with the corresponding Lie algebra $\mathfrak{g}$ admitting a Gelfand–Tsetlin chain $\mathfrak{g}_{1}\subset\mathfrak{g}_{2}\subset\dots\subset\mathfrak{g}_{k}=% \mathfrak{g}$ . As discussed in Section 4.5, under the action of the Gelfand–Tsetlin algebra $\mathcal{G}\hskip-1.00006pt\mathcal{Z}(\mathfrak{g})$ the representation $V$ decomposes into GZ-isotypic components indexed by Gelfand–Tsetlin patterns, and Theorem 5.2 can be used to construct for every Gelfand–Tsetlin pattern $T$ an element $Y_{T}\in\mathcal{U}(\mathfrak{g})$ such that $Y_{T}.x$ is the projection of $x$ onto the $T$ -isotypic subspace of $V$ . The length of $Y_{T}$ is bounded in terms of the lengths of Casimir elements of $\mathfrak{g}_{\ell}$ and the number of Gelfand–Tsetlin patterns appearing in the decomposition of $V$ .

Consider the case of $\mathfrak{gl}_{k}$ acting on $\mathbb{C}[\mathbb{C}[x_{1},\dots,x_{k}]_{d}]_{\delta}$ . For the chain $\mathfrak{gl}_{1}\subset\mathfrak{gl}_{2}\subset\dots\subset\mathfrak{gl}_{k}$ , Casimir elements have length at most $k$ . Every irreducible subrepresentation of $\mathbb{C}[\mathbb{C}[x_{1},\dots,x_{k}]_{d}]_{\delta}$ corresponds to a partition $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}_{k}\,}{\scalebox{1.2}[0.7]{ % $\vdash$}_{k}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{% \scalebox{0.5}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{d\delta}$ . Gelfand–Tsetlin patterns are in bijective correspondence with semistandard Young tableaux with $\delta d$ cells and $k$ rows. Each row of a tableau is an ordered tuple of integers from $\{1,\dots,k\}$ , so there are at most $\binom{d\delta+k-1}{k-1}\leq(d\delta)^{k}$ tuples that can serve as rows of a tableau, and therefore at most $(d\delta)^{k^{2}}$ possible semistandard tableaux.

Corollary 5.8.

For each semistandard tableau $T$ of shape $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}_{k}\,}{\scalebox{1.2}[0.7]{ % $\vdash$}_{k}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{% \scalebox{0.5}{\scalebox{1.2}[0.7]{$\vdash$}}_{k}\,}{\delta d}$ there is an element $Y_{T}\in\mathcal{U}(\mathfrak{gl}_{k})$ of length at most $k(\delta d)^{k^{2}}$ which acts on $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ as the projector onto the $T$ -isotypic space corresponding to $T$ .

5.2 Circuit transformations

We now combine the bounds on the lengths of the projectors with the PBW theorem (Theorem 4.9) to prove Theorem 1.1. Pick any ordered basis $(X_{1},\ldots,X_{k^{2}})$ for $\mathfrak{gl}_{k}$ , such as $\{E_{i,j}\}_{i,j}$ with $(i,j)$ ordered lexicographically.

We first introduce some notation. Set $K\coloneqq k^{2}$ . For $\bm{i}=(i_{1},\ldots,i_{K})\in\mathbb{N}^{K}$ we will use the shorthand notation $X^{\bm{i}}\coloneqq X_{1}^{i_{1}}\cdots X_{K}^{i_{K}}\in\mathcal{U}(\mathfrak{% gl}_{k})$ . Let $\bm{i}^{\prime}\leq\bm{i}$ denote that $\bm{i}^{\prime}=(i^{\prime}_{1},\ldots,i^{\prime}_{K})\in\mathbb{N}^{K}$ with $i^{\prime}_{r}\leq i_{r}$ for all $r\in[K]$ . Write $\bm{i}-\bm{i}^{\prime}\coloneqq(i_{1}-i^{\prime}_{1},\ldots,i_{K}-i^{\prime}_{% K})$ and $\binom{\bm{i}}{\bm{i}^{\prime}}\coloneqq\binom{i_{1}}{i^{\prime}_{1}}\cdots% \binom{i_{K}}{i^{\prime}_{K}}$ . Lastly, define $|\bm{i}|\coloneqq\sum_{r}i_{r}$ and $\mathbb{N}^{K}_{\leq L}\coloneqq\{\bm{i}\in\mathbb{N}^{K}\mid|\bm{i}|\leq L\}$ .

By ˜4.2, any element $X\in\mathcal{U}(\mathfrak{gl}_{k})$ acts as a derivation on the space of metapolynomials $\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]=\bigoplus_{\delta\geq 0}\mathbb% {C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]_{\delta}$ .

Lemma 5.9.

Suppose $\Phi,\Gamma\in\mathbb{C}[\mathbb{C}[x_{1},\ldots,x_{k}]_{d}]$ are metapolynomials. Then

1.

$X^{\bm{i}}.(\Phi+\Gamma)=X^{\bm{i}}.\Phi+X^{\bm{i}}.\Gamma$
2.

$\displaystyle X^{\bm{i}}.(\Phi\Gamma)=\sum_{{\bm{i}}^{\prime}\colon{\bm{i}}^{% \prime}\leq{\bm{i}}}\Bigl{(}\begin{array}[]{@{}c@{}}{\bm{i}}\\ {\bm{i}}^{\prime}\end{array}\Bigr{)}\big{(}X^{{\bm{i}}^{\prime}}.\Phi\big{)}% \big{(}X^{{\bm{i}}-{\bm{i}}^{\prime}}.\Gamma\big{)}$

Proof.

Item 1 follows directly from linearity. Since $\mathfrak{gl}_{k}$ acts by derivations (see ˜4.2) we have $X.(fg)=(X.f)g+f(X.g)$ . For $i\in\mathbb{N}$ a straightforward induction argument shows $X^{i}.(fg)=\sum_{i^{\prime}\colon i^{\prime}\leq i}\binom{i}{i^{\prime}}\big{(% }X^{i^{\prime}}.f\big{)}\big{(}X^{i-i^{\prime}}.g\big{)}$ . Then Item 2 follows. $\hfill\blacktriangleleft$

Theorem 5.10.

Let $P\in\mathcal{U}(\mathfrak{gl}_{k})$ be an element of length $L$ . Suppose there exists an arithmetic circuit $C$ of size $s$ computing a metapolynomial $\Delta\colon\mathbb{C}[x_{1},\ldots,x_{k}]_{d}\to\mathbb{C}$ . Then there exists an arithmetic circuit $C^{\prime}$ of size $O\big{(}sL^{2k^{2}}\big{)}$ computing $P.\Delta$ .

Proof.

Again set $K\coloneqq k^{2}$ . Construct $C^{\prime}$ from $C$ using the following recursive procedure:

1.

Add for every input gate $\Theta$ in $C$ the input gates $X^{\bm{i}}.\Theta$ for ${\bm{i}}\in\mathbb{N}^{K}_{\leq L}$ .
2.

Add for every addition gate $\Theta=\Phi+\Gamma$ in $C$ the addition gates computing $X^{\bm{i}}.\Theta$ for ${\bm{i}}\in\mathbb{N}^{K}_{\leq L}$ , using the expression in Lemma 5.9.
3.
Add for every product gate $\Theta=\Phi\Gamma$ in $C$ :
- $\blacksquare$
  
  product gates computing $\big{(}X^{{\bm{i}}^{\prime}}.\Phi\big{)}\big{(}X^{{\bm{i}}-{\bm{i}}^{\prime}}.% \Gamma\big{)}$ for ${\bm{i}}\in\mathbb{N}^{K}_{\leq L}$ and ${\bm{i}}^{\prime}\leq{\bm{i}}$ ,
- $\blacksquare$
  
  addition gates computing $X^{\bm{i}}.\Theta$ for ${\bm{i}}\in\mathbb{N}^{K}_{\leq L}$ , using the expression in Lemma 5.9.
4.

The resulting circuit computes $X^{\bm{i}}.\Delta$ for ${\bm{i}}\in\mathbb{N}^{K}_{\leq L}$ . By the PBW theorem (Theorem 4.9), there exists scalars $\beta_{\bm{i}}\in\mathbb{C}$ such that

$\displaystyle P=\sum_{\bm{i}\in\mathbb{N}^{K}_{\leq L}}\beta_{\bm{i}}X^{\bm{i}}.$

Add to $C^{\prime}$ the addition gates computing $P.\Delta$ .

The largest blow-up occurs in step 3. Let $A\coloneqq\{({\bm{i}},{\bm{i}}^{\prime})\mid{\bm{i}}\in\mathbb{N}^{K}_{\leq L}% ,{\bm{i}}^{\prime}\leq{\bm{i}}\}$ . We added for every product gate in $C$ exactly $|A|$ product gates computing $\big{(}X^{{\bm{i}}^{\prime}}.f\big{)}\big{(}X^{{\bm{i}}-{\bm{i}}^{\prime}}.g% \big{)}$ for $(\bm{i},\bm{i}^{\prime})\in A$ , and $|A|-1$ addition gates computing $X^{\bm{i}}.(fg)=\sum_{(\bm{i},\bm{i}^{\prime})\in A}\binom{{\bm{i}}}{{\bm{i}}^% {\prime}}\big{(}X^{{\bm{i}}^{\prime}}.f\big{)}\big{(}X^{{\bm{i}}-{\bm{i}}^{% \prime}}.g\big{)}$ .

The blow-up of the other steps is bounded above by $|A|$ , and the total blow-up is therefore upper bounded by $2|A|-1$ . We now prove that $|A|=\binom{L+2K}{2K}$ .

Let $(\bm{i},\bm{i}^{\prime})\in A$ . By definition, $i_{1}+\cdots+i_{K}\leq L$ , and $(i_{j}-i_{j}^{\prime})\geq 0$ , for all $j\in[K]$ , with $i_{j}^{\prime}\geq 0$ . Let $a_{j}:=(i_{j}-i_{j}^{\prime})$ , and $b_{j}:=i_{j}^{\prime}$ . We want to find the number of $(\bm{a},\bm{b})\in\mathbb{N}^{2K}$ such that $\sum_{j=1}^{2K}(a_{j}+b_{j})\leq L$ . So the number of pairs $(\bm{a},\bm{b})\in\mathbb{N}^{2K}$ such that $\sum_{j=1}^{2K}(a_{j}+b_{j})=t$ is $\binom{t+2K-1}{2K-1}$ . Therefore, by the hockey-stick identity,

|A|\;=\;\sum_{t=0}^{L}\binom{t+2K-1}{2K-1}\;=\;\binom{L+2K}{2K}.

The above equality readily gives us the upper bound of $|A|=O(L^{2K})$ , which gives the desired complexity. $\hfill\blacktriangleleft$

Proof of Theorem 1.1.

Let $\Delta$ be a metapolynomial of format $(d,\delta,n)$ admitting an algebraic circuit of size $s$ . For each case of Theorem 1.1, we have a corresponding projector:

1.

For every weight $\mu$ , Corollary 5.5 provides an element $H_{\mu}\in\mathcal{U}(\mathfrak{gl}_{k})$ of length at most $O((\delta d)^{k})$ acting as projection on the weight space of weight $\mu$ . Theorem 5.10 guarantees that $H_{\mu}.\Delta$ admits a circuit of size at most $O(s((\delta d)^{k})^{2k^{2}})=O(s(\delta d)^{2k^{3}})$ .
2.

For every partition $\lambda$ , Corollary 5.6 provides an element $Z_{\mu}\in\mathcal{U}(\mathfrak{gl}_{k})$ of length at most $O(k(\delta d)^{k})$ acting as projection on the isotypic component of type $\lambda$ . Theorem 5.10 guarantees that $Z_{\lambda}.\Delta$ admits a circuit of size at most $O(s(k(\delta d)^{k})^{2k^{2}})=O(sk^{2k^{2}}(\delta d)^{2k^{3}})$ .
3.

For every partition $\lambda$ , Corollary 5.7 provides an element $X_{\lambda}\in\mathcal{U}(\mathfrak{gl}_{k})$ of length at most $O((k+1)(\delta d)^{k})$ acting as projection on the highest weight space of weight $\lambda$ . Theorem 5.10 guarantees that $X_{\lambda}.\Delta$ admits a circuit of size at most $O(s((k+1)(\delta d)^{k})^{2k^{2}})=O(s(k+1)^{2k^{2}}(\delta d)^{2k^{3}})$ .
4.

For every semistandard tableaux $T$ of shape $\lambda\mathchoice{\scalebox{1.2}[0.7]{ $\vdash$}\,}{\scalebox{1.2}[0.7]{ $% \vdash$}\,}{\scalebox{0.7}{\scalebox{1.2}[0.7]{$\vdash$}}\,}{\scalebox{0.5}{% \scalebox{1.2}[0.7]{$\vdash$}}\,}d\delta$ , Corollary 5.8 provides an element $Y_{\lambda}\nobreak\in\nobreak\mathcal{U}(\mathfrak{gl}_{k})$ of length at most $O(k(\delta d)^{k^{2}})$ acting as projection on $T$ -isotypic space. Theorem 5.10 guarantees that $Y_{T}.\Delta$ admits a circuit of size at most $O(s(k(\delta d)^{k^{2}})^{2k^{2}})=O(sk^{2k^{2}}(\delta d)^{2k^{4}})$ .

$\hfill\blacktriangleleft$

References

[1] S. Aaronson and A. Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory (TOCT), 1(1):1–54, 2009. doi:10.1145/1490270.1490272.
[2] A. Abdesselam and J. Chipalkatti. Brill–Gordan loci, transvectants and an analogue of the Foulkes conjecture. Advances in Mathematics, 208(2):491–520, 2007. doi:10.1016/j.aim.2006.03.003.
[3] A. Abdesselam, C. Ikenmeyer, and G. Royle. 16,051 formulas for Ottaviani’s invariant of cubic threefolds. J. Algebra, 447:649–663, 2016. doi:10.1016/j.jalgebra.2015.11.009.
[4] G. E. Baird and L. C. Biedenharn. On the representations of the semisimple Lie groups. II. J. Mathematical Phys., 4:1449–1466, 1963. doi:10.1063/1.1703926.
[5] T. Baker, J. Gill, and R. Solovay. Relativizations of the $\mathcal{P}=?\mathcal{NP}$ question. SIAM Journal on computing, 4(4):431–442, 1975. doi:10.1137/0204037.
[6] F. Berdjis. A criterion for completeness of Casimir operators. J. Math. Phys., 22:1851–1856, 1981. doi:10.1063/1.525156.
[7] D. Bini, M. Capovani, G. Lotti, and F. Romani. $O(n^{2.7799})$ complexity for $n\times{}n$ approximate matrix multiplication. Inform. Process. Lett., 8(5):234–235, 1979. doi:10.1016/0020-0190(79)90113-3.
[8] M. Bläser, M. Christandl, and J. Zuiddam. The border support rank of two-by-two matrix multiplication is seven. Chicago Journal OF Theoretical Computer Science, 5:1–16, 2018.
[9] M. Bläser, J. Dörfler, and C. Ikenmeyer. On the Complexity of Evaluating Highest Weight Vectors. 36th Computational Complexity Conference (CCC 2021), 200:29:1–29:36, 2021. doi:10.4230/LIPIcs.CCC.2021.29.
[10] N. Bourbaki. Lie groups and Lie algebras. Chapters 7–9. Elements of Mathematics (Berlin). Springer-Verlag, Berlin, 2005. Translated from the 1975 and 1982 French originals by Andrew Pressley.
[11] P. Breiding, R. Hodges, C. Ikenmeyer, and M. Michałek. Equations for GL invariant families of polynomials. Vietnam Journal of Mathematics, 50(2):545–556, 2022. doi:10.1007/s10013-022-00549-4.
[12] P. Bürgisser. Completeness and reduction in algebraic complexity theory, volume 7. Springer Science & Business Media, 2000. doi:10.1007/978-3-662-04179-6.
[13] P. Bürgisser. Completeness classes in algebraic complexity theory. arXiv:2406.06217, 2024.
[14] P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315. Springer Science & Business Media, 2013.
[15] P. Bürgisser and C. Ikenmeyer. Geometric complexity theory and tensor rank. In Proceedings of the 43rd Annual ACM Symp. on Th. of Comp., pages 509–518, New York, 2011. STOC ’11, ACM. doi:10.1145/1993636.1993704.
[16] P. Bürgisser and C. Ikenmeyer. Explicit Lower Bounds via Geometric Complexity Theory. In Proceedings of the 45th Annual ACM Symp. on Th. of Comp., pages 141–150. ACM, 2013. doi:10.1145/2488608.2488627.
[17] P. Bürgisser and C. Ikenmeyer. Fundamental invariants of orbit closures. J. Algebra, 477:390–434, 2017. doi:10.1016/j.jalgebra.2016.12.035.
[18] P. Bürgisser, C. Ikenmeyer, and G. Panova. No occurrence obstructions in geometric complexity theory. J. Amer. Math. Soc., 32(1):163–193, 2019. doi:10.1090/jams/908.
[19] P. Bürgisser, J. M. Landsberg, L. Manivel, and J. Weyman. An overview of mathematical issues arising in the Geometric Complexity Theory approach to $VP\neq VNP$ . SIAM J. Comput., 40(4):1179–1209, 2011. doi:10.1137/090765328.
[20] A. Cayley. On the theory of linear transformations. Cambridge Math. J., iv:193–209, 1845.
[21] P. Chatterjee, M. Kumar, C. Ramya, R. Saptharishi, and A. Tengse. On the Existence of Algebraically Natural Proofs. In 2020 IEEE 61st Annual Symp. on Found. of Comp. Sc. (FOCS), pages 870–880, 2020. Full version at arXiv:2004.14147. doi:10.1109/FOCS46700.2020.00085.
[22] X. Chen, N. Kayal, and A. Wigderson. Partial derivatives in arithmetic complexity and beyond. Found. Trends Theor. Comput. Sci., 6(1–2):1–138, 2011. doi:10.1561/0400000043.
[23] M.-W. Cheung, C. Ikenmeyer, and S. Mkrtchyan. Symmetrizing tableaux and the 5th case of the Foulkes conjecture. J. Symbolic Comp., 80:833–843, 2017. doi:10.1016/j.jsc.2016.09.002.
[24] J. Dörfler, C. Ikenmeyer, and G. Panova. On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions. SIAM Journal on Applied Algebra and Geometry, 4(2):354–376, 2020. doi:10.4230/LIPIcs.ICALP.2019.51.
[25] P. Dutta, P. Dwivedi, and N. Saxena. Demystifying the border of depth-3 algebraic circuits. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 92–103. IEEE, 2021. doi:10.1109/FOCS52979.2021.00018.
[26] K. Efremenko, A. Garg, R. Oliveira, and A. Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:19, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2018.1.
[27] M. A. Forbes. Polynomial identity testing of read-once oblivious algebraic branching programs. PhD thesis, Massachusetts Institute of Technology, 2014.
[28] M. A. Forbes. Deterministic divisibility testing via shifted partial derivatives. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 451–465. IEEE, 2015. doi:10.1109/FOCS.2015.35.
[29] M. A. Forbes. Some concrete questions on the border complexity of polynomials. Presentation given at the Workshop on Algebraic Complexity Theory WACT 2016 in Tel Aviv, 2016. URL: https://www.youtube.com/watch?v=1HMogQIHT6Q.
[30] M. A. Forbes. Low-Depth Algebraic Circuit Lower Bounds over Any Field. In 39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, volume 300 of LIPIcs, pages 31:1–31:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.CCC.2024.31.
[31] M. A. Forbes, A. Shpilka, and B. L. Volk. Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. Theory of Computing, 14(1):1–45, 2018. doi:10.4086/toc.2018.v014a018.
[32] W. Fulton and J. Harris. Representation theory: a first course, volume 129 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991.
[33] M. Gałązka. Vector bundles give equations of cactus varieties. Lin. Alg. Appl., 521:254–262, 2017. doi:10.1016/j.laa.2016.12.005.
[34] A. Garg, C. Ikenmeyer, V. Makam, R. Oliveira, M. Walter, and A. Wigderson. Search problems in algebraic complexity, GCT, and hardness of generators for invariant rings. In 35th Computational Complexity Conference, page 1, 2020.
[35] I. M. Gelfand and M. L. Tsetlin. Finite-dimensional representations of the group of unimodular matrices. Dokl. Akad. Nauk SSSR, 71(8):825, 1950.
[36] F. Gesmundo, P. Ghosal, C. Ikenmeyer, and V. Lysikov. Degree-Restricted Strength Decompositions and Algebraic Branching Programs. In 42nd IARCS Ann. Conf. Found. Soft. Tech. and TCS (FSTTCS 2022), volume 250 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:15, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.FSTTCS.2022.20.
[37] F. Gesmundo, Y.-I. Han, and B. Lovitz. Linear preservers of secant varieties and other varieties of tensors. J. Symbolic Comp., 131:102449, 2025. doi:10.1016/j.jsc.2025.102449.
[38] F. Gesmundo, C. Ikenmeyer, and G. Panova. Geometric complexity theory and matrix powering. Diff. Geom. Appl., 55:106–127, 2017. doi:10.1016/j.difgeo.2017.07.001.
[39] J. A. Grochow. Unifying known lower bounds via geometric complexity theory. computational complexity, 24:393–475, 2015. doi:10.1007/s00037-015-0103-x.
[40] J. A. Grochow, M. Kumar, M. Saks, and S. Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv, 2017. arXiv:1701.01717.
[41] A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Arithmetic circuits: A chasm at depth three. Electronic Colloquium on Computational Complexity (ECCC), 20:26, 2013. doi:10.1109/FOCS.2013.68.
[42] B. C. Hall. Lie Groups, Lie Algebras, and Representations: An Elementary Introduction, volume 222 of Graduate Texts in Mathematics. Springer, New York, 2010.
[43] J. Hauenstein, C. Ikenmeyer, and J. M. Landsberg. Equations for lower bounds on border rank. Experimental Mathematics, 22(4):372–383, 2013. doi:10.1080/10586458.2013.825892.
[44] J. E. Humphreys. Introduction to Lie algebras and representation theory, volume 9 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1978.
[45] J. E. Humphreys. Linear algebraic groups, volume 21. Springer Science & Business Media, 2012.
[46] C. Ikenmeyer and U. Kandasamy. Implementing geometric complexity theory: On the separation of orbit closures via symmetries. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 713–726, 2020. doi:10.1145/3357713.3384257.
[47] C. Ikenmeyer and G. Panova. Rectangular Kronecker coefficients and plethysms in geometric complexity theory. Adv. Math., 319:40–66, 2017. doi:10.1016/j.aim.2017.08.024.
[48] C. Ikenmeyer and A. Sanyal. A note on VNP-completeness and border complexity. Information Processing Letters, 176:106243, 2022. doi:10.1016/j.ipl.2021.106243.
[49] A. G. Khovanskiĭ. Fewnomials, volume 88. American Mathematical Soc., 1991.
[50] M. Kumar. A quadratic lower bound for homogeneous algebraic branching programs. computational complexity, 28:409–435, 2019. doi:10.1007/s00037-019-00186-3.
[51] M. Kumar, C. Ramya, R. Saptharishi, and A. Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th Int. Symp. on Th. Asp. of Comp. Sc. (STACS 2022), volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1–44:13, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2022.44.
[52] M. Kumar and B. L. Volk. A lower bound on determinantal complexity. Comput. Complex., 31(2):12, 2022. doi:10.1007/S00037-022-00228-3.
[53] J. M. Landsberg, L. Manivel, and N. Ressayre. Hypersurfaces with degenerate duals and the Geometric Complexity Theory program. Comment. Math. Helv., 88(2):469–484, 2013. doi:10.4171/CMH/292.
[54] J. M. Landsberg and G. Ottaviani. New lower bounds for the border rank of matrix multiplication. Th. of Comp., 11(11):285–298, 2015. doi:10.4086/toc.2015.v011a011.
[55] N. Limaye, Srinivasan S., and S. Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 804–814. IEEE, 2021. doi:10.1109/FOCS52979.2021.00083.
[56] I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, second edition, 1995.
[57] M. Mahajan. Algebraic complexity classes. Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, pages 51–75, 2014. doi:10.1007/978-3-319-05446-9_4.
[58] A. I. Molev. Gelfand-Tsetlin bases for classical Lie algebras. In Handbook of algebra. Vol. 4, volume 4 of Handb. Algebr., pages 109–170. Elsevier/North-Holland, Amsterdam, 2006. doi:10.1016/S1570-7954(06)80006-9.
[59] K. D. Mulmuley. The GCT program toward the P vs. NP problem. Communications of the ACM, 55(6):98–107, 2012. doi:10.1145/2184319.2184341.
[60] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput., 31(2):496–526, 2001. doi:10.1137/S009753970038715X.
[61] K. D. Mulmuley and M. Sohoni. Geometric complexity theory II: towards explicit obstructions for embeddings among class varieties. SIAM Journal on Computing, 38(3):1175–1206, 2008. doi:10.1137/080718115.
[62] N. Nisan and A. Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational complexity, 6:217–234, 1996. doi:10.1007/BF01294256.
[63] L. Oeding and S.V Sam. Equations for the fifth secant variety of Segre products of projective spaces. Exp. Math., 25(1):94–99, 2016. doi:10.1080/10586458.2015.1037872.
[64] A. M. Perelomov and V. S. Popov. Casimir Operators for Semisimple Lie Groups. Mathematics of the USSR-Izvestiya, 2(6):1313, December 1968. doi:10.1070/IM1968v002n06ABEH000731.
[65] G. Racah. Sulla caratterizzazione delle rappresentazioni irriducibili dei gruppi semisemplici di Lie. Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. (8), 8:108–112, 1950.
[66] A. A. Razborov and S. Rudich. Natural proofs. In Proc. of the 26th Ann. ACM Symp. Th. of Comp., pages 204–213, 1994.
[67] K. W. Regan. Understanding the Mulmuley–Sohoni approach to P vs. NP. Bulletin of the EATCS, 78:86–99, 2002.
[68] R. Saptharishi. A survey of lower bounds in arithmetic circuit complexity. https://github.com/dasarpmar/lowerbounds-survey/, 2021. Version 9.0.3.
[69] V. Strassen. Rank and optimal computation of generic tensors. Lin. Alg. Appl., 52/53:645–685, 1983. doi:10.1016/0024-3795(83)80041-X.
[70] J. J. Sylvester. On the principles of the calculus of forms. Cambridge and Dublin Math. J., 7:52–97, 1852.
[71] L. G. Valiant. Completeness classes in algebra. In Proceedings of the 11th ACM Symp. on Th. of Comp., STOC ’79, pages 249–261, New York, 1979. ACM. doi:10.1145/800135.804419.
[72] D. P. Žhelobenko. The classical groups. Spectral analysis of their finite-dimensional representations. Uspehi Mat. Nauk, 17(1(103)):27–120, 1962. doi:10.1070/RM1962v017n01ABEH001123.

Appendix A Proofs on algebraic natural proofs

In this section we prove Theorem 2.2.

Definition A.1.

We call a sequence $r\colon\mathbb{N}\to\mathbb{N}$ strongly superpolynomial if $r(n)$ dominates every polynomial sequence eventually, that is, for every polynomial $p$ there exists $N$ such that $r(n)>p(n)$ for all $n\geq N$ .

Lemma A.2.

$(\Delta_{n})\in I(\mathcal{C})$ if and only if there exists a strongly superpolynomial sequence $r$ such that $\Delta_{n}(X_{n,r(n)})=0$ .

Proof.

Clearly, if $\Delta_{n}(X_{n,r(n)})=0$ , then $\Delta_{n}(X_{n,p(n)})$ vanishes eventually for every polynomially bounded sequence $p$ , since $p(n)\leq r(n)$ eventually.

On the other hand, if $(\Delta_{n})$ is a sequence of metapolynomials in $I(\mathcal{C})$ , we can define $r(n)$ as $r(n):=\max\{r\mid\Delta_{n}(X_{n,r})=0\}$ . For every polynomially bounded sequence $p(n)$ we have that $\Delta_{n}(X_{n,p(n)})$ vanishes eventually, so $r(n)\geq p(n)$ eventually. $\hfill\blacktriangleleft$

Proof of Theorem 2.2.

We first observe we may assume $\deg(f_{n})=n$ . Indeed, for every p-family $(f_{n})$ with the property that $\deg(f_{n})$ is strictly increasing, let $(f^{\prime}_{n})$ be the sequence defined by

f^{\prime}_{m}=\left\{\begin{array}[]{ll}f_{n}&\text{if $m=\deg(f_{n})$ for % some $n$}\\ 0&\text{otherwise}\end{array}\right.

Since $(f_{n})$ is a p-family, the sequence $\deg(f_{n})$ is polynomially bounded, hence $(f^{\prime}_{n})$ is a p-family as well. Moreover $(f_{n})\in\mathcal{C}$ if and only if $(f_{n})\in\mathcal{C}$ , and similarly for $\bar{\mathcal{C}}$ . Finally, for a sequence of metapolynomials $(\Delta_{n})$ of format $(*,n,*)$ , we have $\Delta_{\deg(f_{n})}(f_{n})=0$ eventually if and only if $\Delta_{n}(f^{\prime}_{n})=0$ eventually. In particular, proving the statement for $(f^{\prime}_{n})$ is equivalent to proving the statement for $(f_{n})$ . Since $\deg(f^{\prime}_{n})=n$ , this shows we may assume $\deg(f_{n})=n$ .

Suppose $(f_{n})\in\overline{\mathcal{C}}$ , that is, the sequence $p(n)=\underline{c}(f_{n})$ is polynomially bounded. For every sequence of metapolynomials $(\Delta_{n})\in I(\mathcal{C})$ we have that $\Delta_{n}(X_{n,p(n)})$ vanishes eventually. Since the metapolynomials $\Delta_{n}$ are continuous, $\Delta_{n}(\overline{X_{n,p(n)}})$ vanishes eventually, so $\Delta_{n}(f_{n})=0$ eventually.

Conversely, suppose $(f_{n})\notin\overline{\mathcal{C}}$ . Therefore $r(n)=\underline{c}(f_{n})$ is not polynomially bounded. Let $\theta(n)=\log_{n}r(n)$ , $\hat{\theta}(n)=\max\{\theta(m)\mid m\leq n\}$ , and $R(n)=\lceil n^{\hat{\theta}(n)}\rceil$ . Note that $R(n)$ is monotonically increasing.

The sequence $R(n)$ is strongly superpolynomial. Indeed, since $r(n)$ is not polynomially bounded, for every $k$ there exists $n_{0}$ such that $\theta(n_{0})\geq k$ and, therefore, $\hat{\theta}(n)\geq k$ for all $n\geq n_{0}$ . It follows that for every $k$ we have $R(n)\geq n^{k}$ eventually.

For all $\Theta$ , if $n_{\Theta}$ is the minimal value such that $\theta(n_{\Theta})\geq\Theta$ , then $\hat{\theta}(n_{\Theta})=\theta(n_{\Theta})$ . Since $\theta$ is unbounded, it follows that $\theta$ and $\hat{\theta}$ coincide on an infinite subset of $\mathbb{N}$ . On this subset we also have $R(n)=r(n)$ .

Consider a metapolynomial sequence $\Delta_{n}$ such that $\Delta_{n}(\overline{X_{n,R(n)-1}})=0$ , and if $r(n)=R(n)$ , then $\Delta_{n}$ is chosen so that $\Delta_{n}(f_{n})\neq 0$ (this is possible because $\underline{c}(f_{n})=r(n)=R(n)>R(n)-1$ ). Since $R(n)$ is strongly superpolynomial, $R(n)-1$ is strongly superpolynomial, and $(\Delta_{n})\in I(\mathcal{C})$ by Lemma A.2, and since $R(n)=r(n)$ infinitely often, $\Delta_{n}(f_{n})\neq 0$ infinitely often. $\hfill\blacktriangleleft$

Appendix B PBW, proof that monomials span the space

In this section, we give an elementary proof of the implication in Theorem 4.9 that we use. We include this standard result in this appendix, because it is the main result that enables our algorithmic speedup compared to a naive implementation.

Recall that the universal enveloping algebra $\mathcal{U}(\mathfrak{g})$ is the quotient of the tensor algebra $\mathcal{T}(\mathfrak{g})$ by the ideal $\mathcal{I}(\mathfrak{g})=\{X\otimes Y-Y\otimes X-[X,Y]:X,Y\in\mathfrak{g}\}$ . The quotient induces a filtration $\mathcal{U}(\mathfrak{g})_{\leq m}\subseteq\mathcal{U}(\mathfrak{g})_{\leq(m+1)}$ and the elements of $\mathcal{U}(\mathfrak{g})_{\leq m}$ are represented by noncommutative polynomials of degree at most $m$ in the elements of $\mathfrak{g}$ .

Theorem B.1 (One direction of the PBW Theorem).

Let $X_{1},\ldots,X_{r}$ be a basis for a Lie algebra $\mathfrak{g}$ . Then

\displaystyle\mathcal{B}_{m}\coloneqq\big{\{}X_{i_{1}}X_{i_{2}}\cdots X_{i_{% \ell}}\mid i_{1}\leq i_{2}\leq\cdots\leq i_{\ell}\text{ and }\ell\leq m\}

spans $\mathcal{U}(\mathfrak{g})_{\leq m}$ .

Proof.

It is clear that $\mathcal{T}(\mathfrak{g})_{m}$ is spanned by all elements $X_{i_{1}}\otimes\cdots\otimes X_{i_{m}}$ ; hence it suffices to prove that any such element is equivalent, modulo $\mathcal{I}(\mathfrak{g})$ , to a linear combination of elements of $\mathcal{B}_{m}$ . We prove this statement by induction on $m$ .

Let $X_{j_{1}}\otimes\cdots\otimes X_{j_{m}}\in\mathcal{T}(\mathfrak{g})_{m}$ . For every $a=1,\ldots,m-1$ , we have $X_{j_{a}}\otimes X_{j_{a+1}}-X_{j_{a+1}}\otimes X_{j_{a}}-[X_{j_{a}},X_{j_{a+1% }}]\in\mathcal{I}(\mathfrak{g})$ ; in particular $X_{j_{a}}\otimes X_{j_{a+1}}=X_{j_{a+1}}\otimes X_{j_{a}}+Y$ where $Y$ is a linear combination of elements $\mathcal{I}(\mathfrak{g})$ and of $\mathcal{T}(\mathfrak{g})_{\leq 1}$ . We obtain

\begin{split}X_{j_{1}}\otimes\cdots\otimes X_{j_{\ell}}=&X_{j_{1}}\otimes% \cdots\otimes X_{j_{a-1}}\otimes X_{j_{a+1}}\otimes X_{j_{a}}\otimes X_{j_{a+2% }}\otimes\cdots\otimes X_{j_{\ell}}+Y\end{split}

(18)

where $Y$ is a linear combination of elements of $\mathcal{I}(\mathfrak{g})$ and of $\mathcal{T}(\mathfrak{g})_{\leq m-1}$ .

Let $\pi\in\mathfrak{S}_{m}$ be a permutation such that $(j_{\pi(1)}\cdots j_{\pi(m)})$ is nondecreasing. Write $\pi$ as a composition of elementary transpositions $\pi=\sigma_{s}\cdots\sigma_{1}$ , where $\sigma_{q}=(a,a+1)$ for some $a=1,\ldots,m-1$ . Applying Equation 18 $s$ times we obtain

X_{j_{1}}\otimes\cdots\otimes X_{j_{m}}=X_{j_{\pi(1)}}\otimes\cdots\otimes X_{% j_{\pi(m)}}+U

where $U\in\mathcal{I}(\mathfrak{g})+\mathcal{U}_{\leq(m-1)}$ . Passing to the quotient modulo $\mathcal{I}(\mathfrak{g})$ , we obtain the following identity in $\mathcal{U}(\mathfrak{g})_{\leq m}$ :

X_{j_{1}}\cdots X_{j_{m}}=X_{j_{\pi(1)}}\cdots X_{j_{\pi(m)}}+U

with $U\in\mathcal{U}(\mathfrak{g})_{\leq(m-1)}$ . Apply the induction hypothesis to $U$ to conclude. $\hfill\blacktriangleleft$

[bib.bib1] [1] S. Aaronson and A. Wigderson. Algebrization: A new barrier in complexity theory. ACM Transactions on Computation Theory (TOCT), 1(1):1–54, 2009. doi:10.1145/1490270.1490272.

[bib.bib2] [2] A. Abdesselam and J. Chipalkatti. Brill–Gordan loci, transvectants and an analogue of the Foulkes conjecture. Advances in Mathematics, 208(2):491–520, 2007. doi:10.1016/j.aim.2006.03.003.

[bib.bib3] [3] A. Abdesselam, C. Ikenmeyer, and G. Royle. 16,051 formulas for Ottaviani’s invariant of cubic threefolds. J. Algebra, 447:649–663, 2016. doi:10.1016/j.jalgebra.2015.11.009.

[bib.bib4] [4] G. E. Baird and L. C. Biedenharn. On the representations of the semisimple Lie groups. II. J. Mathematical Phys., 4:1449–1466, 1963. doi:10.1063/1.1703926.

[bib.bib5] [5] T. Baker, J. Gill, and R. Solovay. Relativizations of the $\mathcal{P}=?\mathcal{NP}$ question. SIAM Journal on computing, 4(4):431–442, 1975. doi:10.1137/0204037.

[bib.bib6] [6] F. Berdjis. A criterion for completeness of Casimir operators. J. Math. Phys., 22:1851–1856, 1981. doi:10.1063/1.525156.

[bib.bib7] [7] D. Bini, M. Capovani, G. Lotti, and F. Romani. $O(n^{2.7799})$ complexity for $n\times{}n$ approximate matrix multiplication. Inform. Process. Lett., 8(5):234–235, 1979. doi:10.1016/0020-0190(79)90113-3.

[bib.bib8] [8] M. Bläser, M. Christandl, and J. Zuiddam. The border support rank of two-by-two matrix multiplication is seven. Chicago Journal OF Theoretical Computer Science, 5:1–16, 2018.

[bib.bib9] [9] M. Bläser, J. Dörfler, and C. Ikenmeyer. On the Complexity of Evaluating Highest Weight Vectors. 36th Computational Complexity Conference (CCC 2021), 200:29:1–29:36, 2021. doi:10.4230/LIPIcs.CCC.2021.29.

[bib.bib10] [10] N. Bourbaki. Lie groups and Lie algebras. Chapters 7–9. Elements of Mathematics (Berlin). Springer-Verlag, Berlin, 2005. Translated from the 1975 and 1982 French originals by Andrew Pressley.

[bib.bib11] [11] P. Breiding, R. Hodges, C. Ikenmeyer, and M. Michałek. Equations for GL invariant families of polynomials. Vietnam Journal of Mathematics, 50(2):545–556, 2022. doi:10.1007/s10013-022-00549-4.

[bib.bib12] [12] P. Bürgisser. Completeness and reduction in algebraic complexity theory, volume 7. Springer Science & Business Media, 2000. doi:10.1007/978-3-662-04179-6.

[bib.bib13] [13] P. Bürgisser. Completeness classes in algebraic complexity theory. arXiv:2406.06217, 2024.

[bib.bib14] [14] P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315. Springer Science & Business Media, 2013.

[bib.bib15] [15] P. Bürgisser and C. Ikenmeyer. Geometric complexity theory and tensor rank. In Proceedings of the 43rd Annual ACM Symp. on Th. of Comp., pages 509–518, New York, 2011. STOC ’11, ACM. doi:10.1145/1993636.1993704.

[bib.bib16] [16] P. Bürgisser and C. Ikenmeyer. Explicit Lower Bounds via Geometric Complexity Theory. In Proceedings of the 45th Annual ACM Symp. on Th. of Comp., pages 141–150. ACM, 2013. doi:10.1145/2488608.2488627.

[bib.bib17] [17] P. Bürgisser and C. Ikenmeyer. Fundamental invariants of orbit closures. J. Algebra, 477:390–434, 2017. doi:10.1016/j.jalgebra.2016.12.035.

[bib.bib18] [18] P. Bürgisser, C. Ikenmeyer, and G. Panova. No occurrence obstructions in geometric complexity theory. J. Amer. Math. Soc., 32(1):163–193, 2019. doi:10.1090/jams/908.

[bib.bib19] [19] P. Bürgisser, J. M. Landsberg, L. Manivel, and J. Weyman. An overview of mathematical issues arising in the Geometric Complexity Theory approach to $VP\neq VNP$ . SIAM J. Comput., 40(4):1179–1209, 2011. doi:10.1137/090765328.

[bib.bib20] [20] A. Cayley. On the theory of linear transformations. Cambridge Math. J., iv:193–209, 1845.

[bib.bib21] [21] P. Chatterjee, M. Kumar, C. Ramya, R. Saptharishi, and A. Tengse. On the Existence of Algebraically Natural Proofs. In 2020 IEEE 61st Annual Symp. on Found. of Comp. Sc. (FOCS), pages 870–880, 2020. Full version at arXiv:2004.14147. doi:10.1109/FOCS46700.2020.00085.

[bib.bib22] [22] X. Chen, N. Kayal, and A. Wigderson. Partial derivatives in arithmetic complexity and beyond. Found. Trends Theor. Comput. Sci., 6(1–2):1–138, 2011. doi:10.1561/0400000043.

[bib.bib23] [23] M.-W. Cheung, C. Ikenmeyer, and S. Mkrtchyan. Symmetrizing tableaux and the 5th case of the Foulkes conjecture. J. Symbolic Comp., 80:833–843, 2017. doi:10.1016/j.jsc.2016.09.002.

[bib.bib24] [24] J. Dörfler, C. Ikenmeyer, and G. Panova. On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions. SIAM Journal on Applied Algebra and Geometry, 4(2):354–376, 2020. doi:10.4230/LIPIcs.ICALP.2019.51.

[bib.bib25] [25] P. Dutta, P. Dwivedi, and N. Saxena. Demystifying the border of depth-3 algebraic circuits. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 92–103. IEEE, 2021. doi:10.1109/FOCS52979.2021.00018.

[bib.bib26] [26] K. Efremenko, A. Garg, R. Oliveira, and A. Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:19, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2018.1.

[bib.bib27] [27] M. A. Forbes. Polynomial identity testing of read-once oblivious algebraic branching programs. PhD thesis, Massachusetts Institute of Technology, 2014.

[bib.bib28] [28] M. A. Forbes. Deterministic divisibility testing via shifted partial derivatives. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 451–465. IEEE, 2015. doi:10.1109/FOCS.2015.35.

[bib.bib29] [29] M. A. Forbes. Some concrete questions on the border complexity of polynomials. Presentation given at the Workshop on Algebraic Complexity Theory WACT 2016 in Tel Aviv, 2016. URL: https://www.youtube.com/watch?v=1HMogQIHT6Q.

[bib.bib30] [30] M. A. Forbes. Low-Depth Algebraic Circuit Lower Bounds over Any Field. In 39th Computational Complexity Conference, CCC 2024, July 22-25, 2024, volume 300 of LIPIcs, pages 31:1–31:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.CCC.2024.31.

[bib.bib31] [31] M. A. Forbes, A. Shpilka, and B. L. Volk. Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. Theory of Computing, 14(1):1–45, 2018. doi:10.4086/toc.2018.v014a018.

[bib.bib32] [32] W. Fulton and J. Harris. Representation theory: a first course, volume 129 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1991.

[bib.bib33] [33] M. Gałązka. Vector bundles give equations of cactus varieties. Lin. Alg. Appl., 521:254–262, 2017. doi:10.1016/j.laa.2016.12.005.

[bib.bib34] [34] A. Garg, C. Ikenmeyer, V. Makam, R. Oliveira, M. Walter, and A. Wigderson. Search problems in algebraic complexity, GCT, and hardness of generators for invariant rings. In 35th Computational Complexity Conference, page 1, 2020.

[bib.bib35] [35] I. M. Gelfand and M. L. Tsetlin. Finite-dimensional representations of the group of unimodular matrices. Dokl. Akad. Nauk SSSR, 71(8):825, 1950.

[bib.bib36] [36] F. Gesmundo, P. Ghosal, C. Ikenmeyer, and V. Lysikov. Degree-Restricted Strength Decompositions and Algebraic Branching Programs. In 42nd IARCS Ann. Conf. Found. Soft. Tech. and TCS (FSTTCS 2022), volume 250 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:15, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.FSTTCS.2022.20.

[bib.bib37] [37] F. Gesmundo, Y.-I. Han, and B. Lovitz. Linear preservers of secant varieties and other varieties of tensors. J. Symbolic Comp., 131:102449, 2025. doi:10.1016/j.jsc.2025.102449.

[bib.bib38] [38] F. Gesmundo, C. Ikenmeyer, and G. Panova. Geometric complexity theory and matrix powering. Diff. Geom. Appl., 55:106–127, 2017. doi:10.1016/j.difgeo.2017.07.001.

[bib.bib39] [39] J. A. Grochow. Unifying known lower bounds via geometric complexity theory. computational complexity, 24:393–475, 2015. doi:10.1007/s00037-015-0103-x.

[bib.bib40] [40] J. A. Grochow, M. Kumar, M. Saks, and S. Saraf. Towards an algebraic natural proofs barrier via polynomial identity testing. arXiv, 2017. arXiv:1701.01717.

[bib.bib41] [41] A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Arithmetic circuits: A chasm at depth three. Electronic Colloquium on Computational Complexity (ECCC), 20:26, 2013. doi:10.1109/FOCS.2013.68.

[bib.bib42] [42] B. C. Hall. Lie Groups, Lie Algebras, and Representations: An Elementary Introduction, volume 222 of Graduate Texts in Mathematics. Springer, New York, 2010.

[bib.bib43] [43] J. Hauenstein, C. Ikenmeyer, and J. M. Landsberg. Equations for lower bounds on border rank. Experimental Mathematics, 22(4):372–383, 2013. doi:10.1080/10586458.2013.825892.

[bib.bib44] [44] J. E. Humphreys. Introduction to Lie algebras and representation theory, volume 9 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1978.

[bib.bib45] [45] J. E. Humphreys. Linear algebraic groups, volume 21. Springer Science & Business Media, 2012.

[bib.bib46] [46] C. Ikenmeyer and U. Kandasamy. Implementing geometric complexity theory: On the separation of orbit closures via symmetries. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 713–726, 2020. doi:10.1145/3357713.3384257.

[bib.bib47] [47] C. Ikenmeyer and G. Panova. Rectangular Kronecker coefficients and plethysms in geometric complexity theory. Adv. Math., 319:40–66, 2017. doi:10.1016/j.aim.2017.08.024.

[bib.bib48] [48] C. Ikenmeyer and A. Sanyal. A note on VNP-completeness and border complexity. Information Processing Letters, 176:106243, 2022. doi:10.1016/j.ipl.2021.106243.

[bib.bib49] [49] A. G. Khovanskiĭ. Fewnomials, volume 88. American Mathematical Soc., 1991.

[bib.bib50] [50] M. Kumar. A quadratic lower bound for homogeneous algebraic branching programs. computational complexity, 28:409–435, 2019. doi:10.1007/s00037-019-00186-3.

[bib.bib51] [51] M. Kumar, C. Ramya, R. Saptharishi, and A. Tengse. If VNP Is Hard, Then so Are Equations for It. In 39th Int. Symp. on Th. Asp. of Comp. Sc. (STACS 2022), volume 219 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44:1–44:13, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2022.44.

[bib.bib52] [52] M. Kumar and B. L. Volk. A lower bound on determinantal complexity. Comput. Complex., 31(2):12, 2022. doi:10.1007/S00037-022-00228-3.

[bib.bib53] [53] J. M. Landsberg, L. Manivel, and N. Ressayre. Hypersurfaces with degenerate duals and the Geometric Complexity Theory program. Comment. Math. Helv., 88(2):469–484, 2013. doi:10.4171/CMH/292.

[bib.bib54] [54] J. M. Landsberg and G. Ottaviani. New lower bounds for the border rank of matrix multiplication. Th. of Comp., 11(11):285–298, 2015. doi:10.4086/toc.2015.v011a011.

[bib.bib55] [55] N. Limaye, Srinivasan S., and S. Tavenas. Superpolynomial lower bounds against low-depth algebraic circuits. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 804–814. IEEE, 2021. doi:10.1109/FOCS52979.2021.00083.

[bib.bib56] [56] I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York, second edition, 1995.

[bib.bib57] [57] M. Mahajan. Algebraic complexity classes. Perspectives in Computational Complexity: The Somenath Biswas Anniversary Volume, pages 51–75, 2014. doi:10.1007/978-3-319-05446-9_4.

[bib.bib58] [58] A. I. Molev. Gelfand-Tsetlin bases for classical Lie algebras. In Handbook of algebra. Vol. 4, volume 4 of Handb. Algebr., pages 109–170. Elsevier/North-Holland, Amsterdam, 2006. doi:10.1016/S1570-7954(06)80006-9.

[bib.bib59] [59] K. D. Mulmuley. The GCT program toward the P vs. NP problem. Communications of the ACM, 55(6):98–107, 2012. doi:10.1145/2184319.2184341.

[bib.bib60] [60] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput., 31(2):496–526, 2001. doi:10.1137/S009753970038715X.

[bib.bib61] [61] K. D. Mulmuley and M. Sohoni. Geometric complexity theory II: towards explicit obstructions for embeddings among class varieties. SIAM Journal on Computing, 38(3):1175–1206, 2008. doi:10.1137/080718115.

[bib.bib62] [62] N. Nisan and A. Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational complexity, 6:217–234, 1996. doi:10.1007/BF01294256.

[bib.bib63] [63] L. Oeding and S.V Sam. Equations for the fifth secant variety of Segre products of projective spaces. Exp. Math., 25(1):94–99, 2016. doi:10.1080/10586458.2015.1037872.

[bib.bib64] [64] A. M. Perelomov and V. S. Popov. Casimir Operators for Semisimple Lie Groups. Mathematics of the USSR-Izvestiya, 2(6):1313, December 1968. doi:10.1070/IM1968v002n06ABEH000731.

[bib.bib65] [65] G. Racah. Sulla caratterizzazione delle rappresentazioni irriducibili dei gruppi semisemplici di Lie. Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. (8), 8:108–112, 1950.

[bib.bib66] [66] A. A. Razborov and S. Rudich. Natural proofs. In Proc. of the 26th Ann. ACM Symp. Th. of Comp., pages 204–213, 1994.

[bib.bib67] [67] K. W. Regan. Understanding the Mulmuley–Sohoni approach to P vs. NP. Bulletin of the EATCS, 78:86–99, 2002.

[bib.bib68] [68] R. Saptharishi. A survey of lower bounds in arithmetic circuit complexity. https://github.com/dasarpmar/lowerbounds-survey/, 2021. Version 9.0.3.

[bib.bib69] [69] V. Strassen. Rank and optimal computation of generic tensors. Lin. Alg. Appl., 52/53:645–685, 1983. doi:10.1016/0024-3795(83)80041-X.

[bib.bib70] [70] J. J. Sylvester. On the principles of the calculus of forms. Cambridge and Dublin Math. J., 7:52–97, 1852.

[bib.bib71] [71] L. G. Valiant. Completeness classes in algebra. In Proceedings of the 11th ACM Symp. on Th. of Comp., STOC ’79, pages 249–261, New York, 1979. ACM. doi:10.1145/800135.804419.

[bib.bib72] [72] D. P. Žhelobenko. The classical groups. Spectral analysis of their finite-dimensional representations. Uspehi Mat. Nauk, 17(1(103)):27–120, 1962. doi:10.1070/RM1962v017n01ABEH001123.

	$\displaystyle X.F(\zeta)=$	$\displaystyle\frac{\textnormal{d}}{\textnormal{d}s}\Big{\|}_{0}(\gamma(s)\cdot F% )(\zeta)=$
		$\displaystyle\frac{\textnormal{d}}{\textnormal{d}s}\Big{\|}_{0}(F\circ\gamma(s)% ^{-1})(\zeta)=\qquad(\text{using chain rule})$
		$\displaystyle\sum_{\ell=1}^{r}\frac{\partial}{\partial z_{\ell}}F(\zeta)\cdot(% z_{\ell}(\frac{\textnormal{d}}{\textnormal{d}s}\Big{\|}_{0}\gamma(s)^{-1}\zeta))=$
		$\displaystyle\sum_{\ell=1}^{r}\frac{\partial}{\partial z_{\ell}}F(\zeta)\cdot(% z_{\ell}(-X.\zeta))=-\sum_{\ell=1}^{r}\frac{\partial}{\partial z_{\ell}}F(% \zeta)\cdot z_{\ell}(X.\zeta).$

Algebraic Metacomplexity and Representation Theory

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Metapolynomials

Algebraic circuits

Representation Theory

Theorem 1.1 (Main theorem).

Corollary 1.2.

Proof.

▶ Remark 1.3.

Organization of the paper

2 Context and consequences of the main theorem

2.1 Complexity classes defined by invariant complexity measures

2.2 Lower bounds via isotypic metapolynomials

2.3 Highest weight vectors and representation theoretic obstructions

2.4 Border complexity

2.5 Algebraic complexity and algebraic natural proofs

Definition 2.1 (Natural property).

Theorem 2.2 (Nullstellensatz for 𝒞).

Definition 2.3 (Algebraic natural proof).

Theorem 2.4 (Main theorem about algebraic natural proofs).

Proof.

3 Outline of the proof of Theorem 1.1

4 Representations of Lie algebras

⊳ Claim 4.1 (Action on polynomials).

⊳ Claim 4.2 (Action on metapolynomials).

▶ Remark 4.3.

Proof of ˜4.1 and ˜4.2.

Lemma 4.4 (Schur’s Lemma, [32, Lem. 1.7]).

4.1 Cartan subalgebras and weights

⊳ Claim 4.5.

Proof.

Example 4.6.

Example 4.7.

4.2 Roots and highest weights

Example 4.8.

4.3 Universal enveloping algebra

Theorem 4.9 (Poincaré–Birkhoff–Witt [42, Theorem 9.10]).

Example 4.10.

4.4 Central characters and Casimir elements

Theorem 4.11 ([65], see also [10, §VIII.8.5, Cor.2]).

Example 4.12.

Theorem 4.13 (Harish–Chandra isomorphism, [44, Ch. 23];[6]).

Example 4.14.

Example 4.15.

4.5 Gelfand–Tsetlin theory

5 Efficient construction of projectors

5.1 Construction of projectors

Definition 5.1.

Theorem 5.2.

Proof.

▶ Remark 5.3.

Example 5.4.

5.1.1 Weight projectors

Corollary 5.5.

5.1.2 Isotypic projectors

Corollary 5.6.

5.1.3 Highest weight projectors

Corollary 5.7.

5.1.4 GZ-isotypic projectors

Corollary 5.8.

5.2 Circuit transformations

Lemma 5.9.

Proof.

Theorem 5.10.

Proof.

Proof of Theorem 1.1.

References

Appendix A Proofs on algebraic natural proofs

Definition A.1.

Lemma A.2.

$\blacktriangleright$ Remark 1.3.

Theorem 2.2 (Nullstellensatz for $\mathcal{C}$ ).

$\vartriangleright$ Claim 4.1 (Action on polynomials).

$\vartriangleright$ Claim 4.2 (Action on metapolynomials).

$\blacktriangleright$ Remark 4.3.

$\vartriangleright$ Claim 4.5.

$\blacktriangleright$ Remark 5.3.