\documentclass[11pt]{report} \usepackage{amsmath,amsfonts,amssymb,epsfig,color} \usepackage{rotating} \setlength{\parskip}{0.13cm} \setlength{\baselineskip}{10pt} %\renewcommand{\baselinestretch}{1.5} %\includeonly{evidence,biblio} \begin{document} \title{Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry} \author{ Dedicated to Sri Ramakrishna \\ \\ Ketan D. Mulmuley \\ The University of Chicago and I.I.T., Mumbai\footnote{Visiting faculty member} \\ \\ (Preprint, Comp. Sci. Dept., The University of Chicago, May, 2007)} %\includeonly{} \maketitle \newtheorem{prop}{Proposition}[section] \newtheorem{claim}[prop]{Claim} \newtheorem{goal}[prop]{Goal} \newtheorem{theorem}[prop]{Theorem} \newtheorem{hypo}[prop]{Hypothesis} \newtheorem{guess}[prop]{Guess} \newtheorem{problem}[prop]{Problem} \newtheorem{axiom}[prop]{Axiom} \newtheorem{question}[prop]{Question} \newtheorem{remark}[prop]{Remark} \newtheorem{lemma}[prop]{Lemma} \newtheorem{claimedlemma}[prop]{Claimed Lemma} \newtheorem{claimedtheorem}[prop]{Claimed Theorem} \newtheorem{cor}[prop]{Corollary} \newtheorem{defn}[prop]{Definition} \newtheorem{ex}[prop]{Example} \newtheorem{conj}[prop]{Conjecture} \newtheorem{obs}[prop]{Observation} \newtheorem{phyp}[prop]{Positivity Hypothesis} \newcommand{\bitlength}[1]{\langle #1 \rangle} \newcommand{\ca}[1]{{\cal #1}} \newcommand{\floor}[1]{{\lfloor #1 \rfloor}} \newcommand{\ceil}[1]{{\lceil #1 \rceil}} \newcommand{\gt}[1]{{\langle #1 |}} \newcommand{\C}{\mathbb{C}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\frcgc}[5]{\left(\begin{array}{ll} #1 & \\ #2 & | #4 \\ #3 & | #5 \end{array}\right)} \newcommand{\cgc}[6]{\left(\begin{array}{ll} #1 ;& \quad #3\\ #2 ; & \quad #4 \end{array}\right| \left. \begin{array}{l} #5 \\ #6 \end{array} \right)} \newcommand{\wigner}[6] {\left(\begin{array}{ll} #1 ;& \quad #3\\ #2 ; & \quad #4 \end{array}\right| \left. \begin{array}{l} #5 \\ #6 \end{array} \right)} \newcommand{\rcgc}[9]{\left(\begin{array}{ll} #1 & \quad #4\\ #2 & \quad #5 \\ #3 &\quad #6 \end{array}\right| \left. \begin{array}{l} #7 \\ #8 \\#9 \end{array} \right)} \newcommand{\srcgc}[4]{\left(\begin{array}{ll} #1 & \\ #2 & | #4 \\ #3 & | \end{array}\right)} \newcommand{\arr}[2]{\left(\begin{array}{l} #1 \\ #2 \end{array} \right)} \newcommand{\unshuffle}[1]{\langle #1 \rangle} \newcommand{\ignore}[1]{} \newcommand{\f}[2]{{\frac {#1} {#2}}} \newcommand{\tableau}[5]{ \begin{array}{ccc} #1 & #2  \\ #4 & #5 \end{array}} \newcommand{\embed}[1]{{#1}^\phi} \newcommand{\stab}{{\mbox {stab}}} \newcommand{\perm}{{\mbox {perm}}} \newcommand{\trace}{{\mbox {trace}}} \newcommand{\polylog}{{\mbox {polylog}}} \newcommand{\sign}{{\mbox {sign}}} \newcommand{\proj}{{\mbox {Proj}}} \newcommand{\poly}{{\mbox {poly}}} \newcommand{\std}{{\mbox {std}}} \newcommand{\m}{\mbox} \newcommand{\formula}{{\mbox {Formula}}} \newcommand{\circuit}{{\mbox {Circuit}}} \newcommand{\core}{{\mbox {core}}} \newcommand{\orbit}{{\mbox {orbit}}} \newcommand{\cycle}{{\mbox {cycle}}} \newcommand{\ideal}{{\mbox {ideal}}} \newcommand{\qed}{{\mbox {Q.E.D.}}} \newcommand{\proof}{\noindent {\em Proof: }} %\newcommand{\det}{{\mbox {det}}} %\newcommand{\dim}{{\mbox {dim}}} \newcommand{\weight}{{\mbox {wt}}} \newcommand{\tab}{{\mbox {Tab}}} \newcommand{\level}{{\mbox {level}}} \newcommand{\vol}{{\mbox {vol}}} \newcommand{\vect}{{\mbox {Vect}}} \newcommand{\val}{{\mbox {wt}}} \newcommand{\sym}{{\mbox {Sym}}} \newcommand{\convex}{{\mbox {convex}}} \newcommand{\spec}{{\mbox {spec}}} \newcommand{\strong}{{\mbox {strong}}} \newcommand{\adm}{{\mbox {Adm}}} \newcommand{\eval}{{\mbox {eval}}} \newcommand{\for}{{\quad \mbox {for}\ }} \newcommand{\Q}{Q} \newcommand{\mand}{{\quad \mbox {and}\ }} \newcommand{\invlim}{{\mbox {lim}_\leftarrow}} \newcommand{\directlim}{{\mbox {lim}_\rightarrow}} \newcommand{\sformal}{{\cal S}^{\mbox f}} \newcommand{\vformal}{{\cal V}^{\mbox f}} \newcommand{\crystal}{\mbox{crystal}} \newcommand{\conje}{\mbox{\bf Conj}} \newcommand{\graph}{\mbox{graph}} \newcommand{\ind}{\mbox{index}} \newcommand{\rank}{\mbox{rank}} \newcommand{\id}{\mbox{id}} \newcommand{\str}{\mbox{string}} \newcommand{\RSK}{\mbox{RSK}} \newcommand{\wt}{\mbox{wt}} \setlength{\unitlength}{.75in} %%\input{satpos} %%\input{posintpgm} %%\input{phyp} %%\include{polynomiality} %%\include{smooth} %%\include{experimental} %\include{abstract} \begin{abstract} This article belongs to a series on geometric complexity theory (GCT), an approach to the $P$ vs. $NP$ and related problems through algebraic geometry and representation theory. The basic principle behind this approach is called the {\em flip}. In essence, it reduces the negative hypothesis in complexity theory (the lower bound problems), such as the $P$ vs. $NP$ problem in characteristic zero, to the positive hypothesis in complexity theory (the upper bound problems): specifically, to showing that the problems of deciding nonvanishing of the fundamental structural constants in representation theory and algebraic geometry, such as the well known plethysm constants \cite{macdonald,fultonrepr}, belong to the complexity class $P$. In this article, we suggest a plan for implementing the {flip}, i.e., for showing that these decision problems belong to $P$. This is based on the reduction of the preceding complexity-theoretic positive hypotheses to mathematical positivity hypotheses: specifically, to showing that there exist positive formulae--i.e. formulae with nonnegative coefficients--for the structural constants under consideration and certain functions associated with them. These turn out be intimately related to the similar positivity properties of the Kazhdan-Lusztig polynomials \cite{kazhdan,kazhdan1} and the multiplicative structural constants of the canonical (global crystal) bases \cite{kashiwara2,lusztigcanonical} in the theory of Drinfeld-Jimbo quantum groups. The known proofs of these positivity properties depend on the Riemann hypothesis over finite fields (Weil conjectures proved in \cite{weil2}) and the related results \cite{beilinson}. Thus the reduction here, in conjunction with the flip, in essence, says that the validity of the $P\not = NP$ conjecture in characteristic zero is intimately linked to the Riemann hypothesis over finite fields and related problems. The main ingradients of this reduction are as follows. First, we formulate a general paradigm of saturated, and more strongly, positive integer programming, and show that it has a polynomial time algorithm, extending and building on the techniques in \cite{loera,GCT3,GCT5,lovasz,kannan,king,kirillov,knutson}. Second, building on the work of Boutot \cite{boutot} and Brion (cf. \cite{dehy}), we show that the stretching functions associated with the structural constants under consideration are quasipolynomials, generalizing the known result that the stretching function associated with the Littlewood-Richardson coefficient is a polynomial for type $A$ \cite{derkesen,kirillov} and a quasi-polynomial for general types \cite{berenstein,dehy}. In particular, this proves Kirillov's conjecture \cite{kirillov} for the plethysm constants. Third, using these stretching quasi-polynomials, we formulate the mathematical saturation and positivity hypotheses for the plethysm and other structural constants under consideration, which generalize the known saturation and conjectural positivity properties of the Littlewood-Richardson coefficients \cite{knutson,loera,king}. Assuming these hypotheses, it follows that the problem of deciding nonvanishing of any of these structural constants can be transformed in polynomial time into a saturated, and more strongly, positive integer programming problem, and hence, can be solved in polynomial time. Fourth, we give theoretical and experimental results in support of these hypotheses. Finally, we suggest an approach to prove these positivity hypotheses motivated by the works on Kazhdan-Lusztig bases for Hecke algebras \cite{kazhdan,kazhdan1} and the canonical (global crystal) bases of Kashiwara and Lusztig \cite{lusztigcanonical,lusztigbook, kashiwara2} for representations of Drinfeld-Jimbo quantum groups \cite{drinfeld,jimbo}. Steps in this direction are taken \cite{GCT4,plethysm,canonical}. Specifically, in \cite{GCT4,plethysm} are constructed generalizations of the Drinfeld-Jimbo quantum group, with compact real forms, and also associated algebras whose relationship with the generalized quantum groups is conjecturally similar to the realtionship of the Hecke algebra with the Drinfeld-Jimbo quantum group. It is conjectured in \cite{canonical}, on the basis of theoretical and experimental evidence, that the coordinate rings of these generalized quantum groups have bases that are analogous to the canonical (global crystal) bases, as per Kashiwara and Lusztig, for the coordinate ring of the Drinfeld-Jimbo quantum group, or in the dual setting, the associated algebras have bases that are akin to the Kazhdan-Lusztig bases for Hecke algebras. These conjectures lie at the heart of this approach. In view of \cite{kazhdan1,lusztigcanonical}, their validity is intimately linked to the Riemann hypothesis over finite fields and the related works mentioned above. \end{abstract} \tableofcontents %\include{intro} \chapter{Introduction} This article belongs to a series of papers, \cite{GCT1} to \cite{GCT11}, on geometric complexity theory (GCT), which is an approach to the $P$ vs. $NP$ and related problems in complexity theory through algebraic geometry and representation theory. We assume here that the underlying field of computation is of characteristic zero. For the problems that arise when the field is algebraically closed of positive characteristic or is finite, see \cite{GCT11}. The usual $P$ vs. $NP$ problem is over a finite field. The characteristic zero version is its weaker, formal implication, and philosophically, the crux. The basic principle underlying GCT is called the {\em flip}. It was proposed in \cite{GCT0}. Its detailed exposition will appear in \cite{GCTflip}. The flip, in essence, reduces the negative hypotheses (lower bound problems) in complexity theory, such as the $P\not =?NP$ problem in characteristic zero, to the positive hypotheses in complexity theory (upper bound problems): specifically, to the problem of showing that a series of decision problems in representation theory and algebraic geometry belong to the complexity class $P$. Each of these decision problem is of the form: Given a nonnegative structural constant in representation theory or geometric invariant theory, such as the well known plethysm constant, decide if it is nonzero (nonvanishing). - This flip from the negative to the positive may be considered to be a nonrelativizable form of the flip--from the undecidable to the decidable--that underlies the proof of G\"odel's incompleteness theorem. But the classical diagonalization technique in G\"odel's result is relativizable \cite{solovay}, and hence, not applicable to the $P$ vs. $NP$ problem. The flip, in contrast, is nonrelativizable. It is furthermore nonnaturalizable \cite{GCT10}); i.e., it crosses the natural proof barrier \cite{rudich} that any approach to the $P$ vs. $NP$ problem must cross. We suggest here a plan for implementating the flip; i.e., for showing that the decision problems above belong to $P$. This is based on the reduction in this paper of the complexity-theoretic positivity hypotheses mentioned above to mathematical positivity hypotheses: specifically, to showing that there exist positive formulae for the structural constants under consideration and certain functions associated with them. We also give theoretical and experimental evidence in support of the latter hypotheses. Here we say that a formula is positive if its coefficients are nonegative. The problem finding the positive formulae as above turns out be intimately related to the analogous problem for the Kazhdan-Lusztig polynomials \cite{kazhdan} and the multiplicative structural constants of the canonical (global crystal) bases \cite{kashiwara2,lusztigcanonical} in the theory of Drinfeld-Jimbo quantum groups. The known solution to the latter problem \cite{kazhdan1,lusztigcanonical} depends on the Riemann hypothesis over finite fields, proved in \cite{weil2}, and the related results in \cite{beilinson}. Thus the flip and the reduction here together roughly say that the validity of the $P\not = NP$ conjecture in characteristic zero is intimately linked to the Riemann hypothesis over finite fields and related problems. This is illustrated in Figure~\ref{fbasicintro}; the question marks there indicate unsolved problems. It seems that substantial extension of the techniques related to the Riemann hypothesis over finite fields may be needed to prove the required mathematical positivity hypotheses here. We do not have the necessary mathematical expertize for this task. But it is our hope that the experts in algebraic geometry and representation theory will have something to say on this matter. \begin{figure} \[ \begin{array}{c} \fbox{Complexity theoretic negative hypotheses (lower bound problems)} \\ | \\ | \\ \mbox{The flip} \\ | \\ \downarrow \\ \fbox{Complexity theoretic positive hypotheses (upper bound problems)} \\ | \\ | \\ \mbox{The reduction in this paper} | \\ | \\ \downarrow \\ \fbox{Mathematical positivity hypotheses} | \\ | \\ \mbox{?}\\ | \\ \downarrow \\ \fbox{(?) The Riemann hypothesis over finite fields, related problems and their extensions} \end{array} \] \caption{Pictorial depiction of the basic plan for implementing the flip} \label{fbasicintro} \end{figure} Now we turn to a more detailed exposition of the main results in this paper and of Figure~\ref{fbasicintro}. \section{The decision problems} \label{sdecision} The decision problems in representation theory and algebraic geometry mentioned above (the second box in Figure~\ref{fbasicintro}) are as follows. \begin{problem} (Decision version of the Kronecker problem) \label{pintrokronecker} Given partitions $\lambda,\mu,\pi$, decide nonvanishing of the Kronecker coefficient $k_{\lambda,\mu}^\pi$. This is the multiplicity of the irreducible representation (Specht module) $S_\pi$ of the symmetric group $S_n$ in the tensor product $S_\lambda \otimes S_\mu$. Equivalently \cite{fultonrepr}, let $H=GL_n(\C)\times GL_n(\C)$ and $\rho: H \rightarrow G=GL(\C^n \otimes \C^n)=GL_{n^2}(\C)$ the natural embedding. Then $k_{\lambda,\mu}^\pi$ is the multiplicity of the $H$-module $V_\lambda(GL_n(\C)) \otimes V_\mu(GL_n(\C))$ in the $G$-module $V_\pi(G)$, considered as an $H$-module via the embedding $\rho$. \end{problem} Here $V_\lambda(GL_n(\C))$ denotes the irreducible representation (Weyl module) of $GL_n(\C)$ corresponding to the partition $\lambda$; $V_\pi(G)$ is the Weyl module of $G=GL_{n^2}(\C)$. Problem~\ref{pintrokronecker} is a special case of the following generalized plethysm problem. \begin{problem} (Decision version of the plethysm problem) \label{pintroplethysm} Given partitions $\lambda,\mu,\pi$, decide nonvanishing of the plethysm constant $a_{\lambda,\mu}^\pi$. This is the multiplicity of the irreducible representation $V_\pi(H)$ of $H=GL_n(\C)$ in the irreducible representation $V_\lambda(G)$ of $G=GL(V_\mu)$, where $V_\mu=V_\mu(H)$ is an irreducible representation $H$. Here $V_\lambda(G)$ is considered an $H$-module via the representation map $\rho:H\rightarrow G=GL(V_\mu)$. \noindent (Decision version of the generalized plethysm problem) The same as above, allowing $H$ to be any connected reductive group. \end{problem} This is a special case of the following fundamental problem of representation theory (characteristic zero): \begin{problem} (Decision version of the subgroup restriction problem) \label{pintrosubgroup} Let $G$ be connected reductive group, $H$ a reductive group, possibly disconnected, and $\rho:H \rightarrow G$ an explicit, polynomial homomorphism (as defined in Section~\ref{sssubgroup}). Here $H$ will generally be a subgroup of $H$, and $\rho$ its embedding. Let $V_\pi(H)$ be an irreducible representation of $H$, and $V_\lambda(G)$ an irreducible representation of $G$. Here $\pi$ and $\lambda$ denote the classifying labels of the irreducible representations $V_\pi(H)$ and $V_\lambda(G)$, respectively. Let $m_\lambda^\pi$ be the multiplicity of $V_\pi(H)$ in $V_\lambda(G)$, considered as an $H$-module via $\rho$. Given specifications of the embedding $\rho$ and the labels $\lambda,\pi$, as described in Section~\ref{sssubgroup}, decide nonvanishing of the multiplicity $m_\lambda^\pi$. \end{problem} All reductive groups in this paper are over $\C$. The reductive groups that arise in GCT in characteristic zero are: the general and special linear groups $GL_n(\C)$ and $SL_n(\C)$, algebraic tori, the symmetric group $S_n$, and the groups formed from these by (semidirect) products. The reader may wish to focus on just these concrete cases, since all main ideas in this paper are illustrated therein. Problem~\ref{pintrosubgroup} is, in turn, a special case of the following most general problem. \begin{problem} (Decision problem in geometric invariant theory) \label{pintrogit} Let $H$ be a reductive group, possibly disconnected, $X$ a projective $H$-variety ($H$-scheme), i.e., a variety with $H$-action. Let $\rho$ denote this $H$-action. Let $R=\oplus_d R_d$ be the homogeneous coordinate ring of $X$. Assume that the singularities of $\spec(R)$ are rational. We assume that $X$ and $\rho$ have special properties (as described in Section~\ref{sspgit}), so that, in particular, they have short specifications. Let $V_\pi(H)$ be an irreducible representation of $H$. Let $s_d^\pi$ be the multiplicity of $V_\pi(H)$ in $R_d$, considered as an $H$-module via the action $\rho$. Given $d,\pi$, the specifications of $X$ and $\rho$, decide nonvanishing of the multiplicity $s_d^\pi$. \end{problem} This last problem is hopeless for general $X$. Indeed the usual specification of $X$, say in terms of the generators of the ideal of its appropriate embedding, is so large as to make this problem meaningless for a general $X$. But the instances of this decision problem that arise in GCT are for the following very special kinds of projective $H$-varieties $X$, which, in particular, have small specifications (Section~\ref{sspgit}): \begin{enumerate} \item $G/P$, where $G$ is a connected, reductive group, $P\subseteq G$ its parabolic subgroup, and $H\subseteq G$ a reductive subgroup with an explicit polynomial embedding. Problem~\ref{pintrosubgroup} reduces to this special case of Problem~\ref{pintrogit}; cf. Section~\ref{sspgit}. \item {\em Class varieties} \cite{GCT1,GCT2}, which are associated with the fundamental complexity classes such as $P$ and $NP$. They are very special like $G/P$, with conjecturally rational singularities \cite{GCT10}. Each class variety is specified by the complexity class and the parameters of the lower bound problem under consideration. Briefly, the $P$ vs. $NP$ problem in characteristic zero is reduced in \cite{GCT1,GCT2} to showing that the class variety corresponding to the complexity class $NP$ and the parameters of the lower bound problem (such as the input size) cannot be embedded in the class variety corresponding to the complexity class $P$ and the same parameters. Efficient criteria for the decision problems stated above are needed to construct {\em explicit obstructions} \cite{GCT2} to such embeddings, thereby proving their nonexistence. Specifically, Problems~\ref{pintrosubgroup} and \ref{pintrogit} are the decision problems associated with Problems 2.5 and 2.6 in \cite{GCT2}, respectively. \end{enumerate} For these varieties Problem~\ref{pintrogit} turns out to be qualitatively similar to Problem~\ref{pintrosubgroup} (cf. Section~\ref{sspgit} and \cite{GCT2,GCT10}). For this reason, the Kronecker and the plethysm problems, which lie at the heart of the subgroup restriction problem, can be taken as the main prototypes of the decision problems that arise here. The main conjectural complexity-theoretic positivity hypothesis governing the flip is the following. \begin{hypo} \label{PHflip} {\bf (PHflip)} Problems~\ref{pintrokronecker}, \ref{pintroplethysm}, \ref{pintrosubgroup}, and the special cases of Problem~\ref{pintrogit}, when $X$ therein is $G/P$ or a class variety--which together include all decision problems that arise in the flip--belong to the complexity class $P$. This means nonvanishing of any of these structural constants can be decided in $\poly(\bitlength{x})$ time, where $x$ denotes the input-specification of the structural constant and $\bitlength{x}$ its bitlength. \end{hypo} For Problem~\ref{pintroplethysm}, the input specification for the plethysm constant $a_{\lambda,\mu}^\pi$ is given in the form of a triple $x=(\lambda,\mu,\pi)$. Here a partition $\lambda$ is specified as a sequence of positive integers $\lambda_1 \ge \lambda_2 \ge \cdots \lambda_k>0$ (the zero parts of the partition are suppressed). The bitlength $\bitlength{\lambda}$ is the total bitlength of the integers $\lambda_r$'s. For the plethsym problem the hypothesis above says that nonvanishing of $a_{\lambda,\pi}^\pi$ can be decided in time that is polynomial in the bit lengths $\bitlength{\lambda}, \bitlength{\mu},\bitlength{\pi}$ of the partitions $\lambda,\mu,\pi$. A detailed specification of the input specification $x$ for the other problems is given in Section~\ref{sphypo}. The structural constants in Problems~\ref{pintrokronecker}-\ref{pintrosubgroup} are of fundamental importance in representation theory. The kronecker and the plethysm constants in Problems~\ref{pintrokronecker} and \ref{pintroplethysm}, in particular, have been studied intensively; see \cite{fultonrepr,macdonald,stanleypos} for their significance. There are many known formulae for these structural constants based on on the character formulae in representation theory. Several formulae for the characters of connected, reductive groups are known by now \cite{fultonrepr}, starting with the Weyl character formula. For the symmetric group, there is the Frobenius character formula \cite{fultonrepr}, for the general linear group over a finite field, Green's formula \cite{macdonald}, and for finite simple groups of Lie type, the character formula of Deligne-Lusztig \cite{deligne}, and Lusztig \cite{lusztig}. (Finite simple groups of Lie type, other than $GL_n(F_q)$, are not needed in GCT.) One obvious method for deciding nonvanishing of the structural constants in Problems~\ref{pintrokronecker}-\ref{pintrogit} is to compute them exactly. But all known algorithms for exact computation of the structural constants in Problems~\ref{pintrokronecker}-\ref{pintrosubgroup} take exponential time. This is expected, since this problem is $\#P$-complete. In fact, even the problem of exact computation of a Kostka number, which is a very special case of these structural constants, is $\#P$-complete \cite{hari}. This means there is no polynomial time algorithm for computing any of them, assuming $P \not = NP$. Of course, there are $\#P$-complete quantities--e.g. the permanent of a nonnegative matrix \cite{valiant}--whose nonvanishing can still be decided in polynomial time \cite{schrijver}. But the decision problems above are of a totally different kind and, at the surface, appear to have inherently exponential complexity. This is because the dimensions of the irreducible representations that occur in their statements can be exponential in the ranks of the groups involved and the bit lengths of the classifying labels of these representations. For example, the dimension of the Weyl module $V_\lambda(GL_n(\C))$ can be exponential in $n$ and the bit length of the partition $\lambda$. Furthermore, the number of terms in any of the preceding character formulae is also exponential. All these decisions problems ask if one exponential dimensional representation can occur within another exponential dimensional representation. To solve them, it may seem necessary to take a detailed look into these representations and/or the character formulae of exponential complexity. Hence, it seemed hard to believe, when the flip was announced, that nonvanishing of these structural constants can, nevertheless, be decided in polynomial time. This constituted the main philosophical obstacle in the course of GCT. \section{Deciding nonvanishing of Littlewood-Richardson coefficients} \label{sintroLR} The first result, which indicated that this obstacle may be removable, came in the wake of the saturation theorem of Knutson and Tao \cite{knutson}. This concerns the following special case of Problem~\ref{pintrosubgroup}, with $G=H \times H$, the embedding $\rho:H \rightarrow G$ being diagonal. \begin{problem} \label{pintrolittle} (Littlewood-Richardson problem) Given a complex semisimple, simply connected Lie group $H$, and its dominant weights $\alpha,\beta,\lambda$, decide nonvanishing of a generalized Littelwood-Richardson coefficient $c_{\alpha,\beta}^{\lambda}$. This is the multiplicity of the irreducible representation $V_\lambda(H)$ of $H$ in the tensor product $V_{\alpha}(H) \otimes V_{\beta}(H)$. \end{problem} It was shown in \cite{GCT3,knutson2,loera} independently that nonvanishing of the Littlewood-Richardson coefficient of type $A$ can be decided in polynomial time; i.e., polynomial in the bit lengths of $\alpha,\beta,\lambda$. Furthermore, the algorithm in \cite{GCT3} works in strongly polynomial time in the terminology of \cite{lovasz}; cf. Section~\ref{sstandard}. The three main ingradients in this result are: \begin{enumerate} \item {\bf PH1}: The Littlewood-Richarson rule, which goes back to 1940's, and whose most important feature is that it is {\em positive}--i.e., it involves no alternating signs as in character-based formulae--and its strengthening in \cite{berenstein}, which gives a positive, polyhedral formula for the Littlewood-Richardson coefficient as the number of integer points in a polytope; this can be the BZ-polytope \cite{berenstein} or the hive polytope \cite{knutson}. We shall refer to this positivity property as the first positivity hypothesis (PH1). \item The polynomial and strongly polynomial time algorithms for linear programming \cite{khachian,tardos}, and \item {\bf SH}: The saturation theorem of Knutson and Tao \cite{knutson}. This says that $c_{\alpha,\beta}^\lambda$ is nonzero if $c_{n \alpha,n \beta}^{n \lambda}$ is nonzero for any $n\ge 1$. We shall refer to this saturation property as the saturation hypothesis (SH). \end{enumerate} Brion \cite{zelevinsky} observed that the verbatim translation of the saturation property in \cite{knutson} fails to hold for the the generalized Littlewood-Richardson coefficients of types $B$, $C$, $D$ (it also fails for the Kronecker coefficients, as well as the plethysm constants \cite{kirillov}). Hence, the algorithms in \cite{GCT3,knutson2,loera} do not work in types $B$, $C$ and $D$. Fortunately, this situation can be remedied. It is shown in \cite{GCT5} that nonvanishing of the generalized Littewood-Richardson coefficient $c_{\alpha,\beta}^\lambda$ of arbitrary type can be decided in (strongly) polynomial time, assuming the positivity conjecture of De Loera and McAllister \cite{loera}. This conjectural hypothesis, based on considerable experimental evidence, is as follows. Let \begin{equation} \label{eqintrostretch1} \tilde c_{\alpha,\beta}^\lambda(n)=c_{n \alpha, n \beta}^{n \lambda} \end{equation} be the stretching function associated with the Littlewood-Richardson coefficient $c_{\alpha,\beta}^\lambda$. It is known to be a polynomial in type $A$ \cite{derkesen,kirillov}, and a quasi-polynomial, in general \cite{berenstein,dehy,loera}. Recall that a fuction $f(n)$ is called a quasi-polynomial if there exist $l$ polynomials $f_j(n)$, $1\le j \le l$, such that $f(n)=f_j(n)$ if $n=j$ mod $l$. Here $l$ is supposed to be the smallest such integer, and is called the period of $f(n)$. The period of $\tilde c_{\alpha,\beta}^\lambda(n)$ for types $B,C,D$ is either $1$ or $2$ \cite{loera}. In general, it is bounded by a fixed constant depending on the types of the simple factors the Lie algebra. \begin{defn} \label{dintropos1} We say that the quasi-polynomial $f(n)$ is {\em positive}, if all coefficients of $f_j(n)$, for all $j$, are nonnegative; i.e., the nonzero coefficients are positive. \end{defn} With this terminology, the hypothesis mentioned above is the following. We say a connected reductive group $H$ is {\em classical}, if each simple factor of its Lie algebra ${\cal H}$ is of type $A,B,C$ or $D$. We also say that the type of $H$ or ${\cal H}$ is classical. \begin{hypo} \label{hph2little} {\bf (PH2)}: \cite{king,loera} Assume that $H$ in Problem~\ref{pintrolittle} is classical. Then the Littlewood-Richardson stretching quasi-polynomial $\tilde c_{\alpha,\beta}^\lambda(n)$ is positive. \end{hypo} We shall refer to this as the second positivity hypothesis (PH2). This was conjectured by King, Tollu and Toumazet \cite{king} for type $A$, and De Loera and McAllister for types $B,C,D$. Since the stretching function above is a polynomial in type $A$, the positivity conjecture of King et al clearly implies the saturation theorem of Knutson and Tao. That is, PH2 implies SH for type $A$. We can formulate an analogue of SH for a Lie algerbra of arbitrary classical type so that PH2 implies SH for an arbitrary type. For this, we need to formulate the notion of a saturated quasi-polynomial, which is not contradicted by the counterexamples, mentioned above, to verbatim translation of the saturation property in \cite{knutson,kirillov} to the setting of quasi-polynomials. Specifically, the notion of saturation in \cite{knutson,kirillov} works well if the stretching function is a polynomial, but not so if it is a quasipolynomial. Let $f(n)$ be a quasi-polynomial with period $l$. Let $f_j(n)$, $1\le j \le l$, be the polynomials such that $f(n)=f_j(n)$ if $n=j$ mod $l$. The index of $f$, $\ind(f)$, is defined to be the smallest $j$ such that the polynomial $f_j(n)$ is not identically zero. If $f(n)$ is identically zero, we let $\ind(f)=0$. If $f(1)\not =0$, then clearly $\ind(f)=1$. \begin{defn} \label{dintrosat} We say that $f(n)$ is {\em saturated} if the converse also holds: i.e., $\ind(f)=1$ implies $f(1)\not = 0$. \end{defn} \begin{remark} \label{rsatstronger} A slightly stronger definition of saturation is: if $f$ is not identically zero, then $f(\ind(f))\not = 0$. \end{remark} If $f(n)$ is positive (Definition~\ref{dintropos1}) then it is clearly saturated. Hence, PH2 (Hypothesis~\ref{hph2little}) implies: \begin{hypo} \label{shlittle} {\bf (SH)}: The Littlewood-Richardson stretching quasi-polynomial $c_{\alpha,\beta}^\lambda(n)$ of arbitary classical type is saturated. \end{hypo} The polynomial time algorithm in \cite{GCT5} works assuming SH as well. For the Littlewood-Richardson coefficient of type $A$, the notion of saturation here coincides with the notion of saturation in \cite{knutson} since $c_{\alpha,\beta}^\lambda(n)$ is a polynomial in that case. Knutson and Tao \cite{knutson} also conjectured a generalized saturation property for arbitrary types. But that property, unlike the one defined above, is only conjectured to be sufficient, but not claimed to be, or expected to be necessary. For this reason, it cannot be used in the complexity-theoretic applications in this paper. There is another positivity conjecture for Littlewood-Richardson coefficients that also implies the saturation theorem of Knutson and Tao. For this consider the generating function \begin{equation} \label{eqlittlerational} C_{\alpha,\beta}^\lambda(t)=\sum_{n\ge 0} \tilde c_{\alpha,\beta}^\lambda(n) t^n. \end{equation} It is a rational function since $\tilde c_{\alpha,\beta}^\lambda(n)$ is a quasi-polynomial \cite{stanleyenu}. For type $A$, if $\tilde c_{\alpha,\beta}^\lambda(n)$ is not identically zero, then $C_{\alpha,\beta}^\lambda(t)$ is a rational function of form \begin{equation}\label{eqintro1} \f{h_d t^d + \cdots + h_0}{(1-t)^{d+1}}, \end{equation} since $\tilde c_{\alpha,\beta}^\lambda(n)$ is a polynomial \cite{stanleyenu}. It is conjectured in \cite{king} that: \begin{hypo} \label{hintrolittleph3} ({\bf PH3}:) The coefficients $h_i$'s in eq.(\ref{eqintro1}) are nonnegative (and $h_0=1$). \end{hypo} We shall call this the third positivity hypothesis (PH3). It clearly implies SH for Littlewood-Richardson coefficients of type $A$. To describe its analogue for arbitrary classical type we need a definition. Let $F(t)=\sum_n f(n) t^n$ be the generating function associated with the quasi-polynomial $f(n)$. It is a rational function \cite{stanleyenu}. \begin{defn} \label{dintroreducedpos} We say that $F(t)$ has a {\em reduced positive form}, if, when $f(n)$ is not identically zero, $F(t)=\bar F(t^c)$, where $c=\ind(f)$, and $\bar F(x)$ is a rational function of the form \begin{equation} \label{eqpos2intro} \bar F(x)=\f{h_d x^d +\cdots + h_0}{\prod_{i=0}^k (1-x^{a_i})^{d_i}}, \end{equation} where (1) $h_0=1$, and $h_i$'s are nonnegative integers, (2) $a_0$=1, and $a_i$'s and $d_i$'s are positive integers, (3) $\sum_i d_i=d+1$, where $d=\max{\deg(f_j(n))}$ is the degree of $f(n)$. We define the modular index of this reduced positive form to be $\max\{a_i\}$. \end{defn} If $F(t)$ has a reduced positive form then $f(n)$ is saturated (Definition~\ref{dintrosat}); this easily follows from the power series expansion of the right hand side of eq.(\ref{eqpos2intro}). The analogue of Hypothesis~\ref{hintrolittleph3} for arbitrary classical type is: \begin{hypo} \label{hintrolittleph3gen} ({\bf PH3}:) The rational function $C_{\alpha,\beta}^\lambda(t)$ has a reduced positive form of modular index bounded by a constant depending only on the types of the simple factors of the Lie algebra of $H$. \end{hypo} This too implies SH for arbitrary classical type. For types $B,C,D$, the constant above is $2$. Experimental evidence for this hypothesis is given in Section~\ref{sevilittle}. The analogue of the PH3, even in the more general $q$-setting, is known to hold for the generating function of the Kostant partition function of type $A$, and more generally, for a parabolic Kostant partition function; cf. Kirillov \cite{kirillov}. This also gives a support for the PH3 above, given a close relationship between Littlewood-Richardson coefficients and Kostant partition functions \cite{fultonrepr}. \section{Back to the general decision problems} It may be remarked that the Littlewood-Richardson problem actually never arises in the flip. It is only used as a simplest proptotype of the actual (much harder) problems that arise--namely Problems~\ref{pintrokronecker}-\ref{pintrogit}. Now we turn to these problems. The goal is to generalize the preceding results and hypotheses for the Littlewood-Richardson coefficients to the structural constants that arise in these problems. The problem of finding a positive, combinatorial formula for the plethysm constant (Problem~\ref{pintroplethysm}), akin to the positive Littlewood-Richardson rule, has already been recognized as an outstanding, classical problem in representation theory \cite{stanleypos}--the known formulae based on character theory mentioned in Section~\ref{sdecision} are not positive, because they involve alternating signs. Indeed, existence of such a formula is a part of the first positivity hypothesis (PH1) below for the plethysm constant, and this problem is the main focus of the work in \cite{GCT4,algcomb,canonical,plethysm}. In view of the intensive work on the plethym constant in the literature, it has now become clear that the complexity of the plethysm problem (Problem~\ref{pintroplethysm}) is far higher than that of the Littlewood-Richardson problem (Problem~\ref{pintrolittle}). This gap in the complexity is the main source of difficulties that has to be addressed. We now state the main ingradients in the plan in this paper to show that Problems~\ref{pintrokronecker}, \ref{pintroplethysm}, \ref{pintrosubgroup}, and \ref{pintrogit}, with $X=G/P$ or a class variety, belong to $P$. \section{Saturated and positive integer programming} \label{ssatpospgm} First, we formulate a general algorithmic paradigm of saturated and positive integer programming that can be applied in the context of these problems. Let $A$ be an $m\times n$ integer matrix, and $b$ an integral $m$-vector. An integer programming problem asks if the polytope $P: A x \le b$ contains an integer point. In general, it is NP-complete. Let $f_P(n)$ be the Ehrhart quasi-polynomial of $P$ \cite{stanleyenu}. By definition, $f_P(n)$ is the number of integer points in the dilated polytope $n P$. An integer programming problem is called {\em saturated} if the Ehrhart quasi-polynomial $f_P(n)$, if $P$ is nonempty, is guaranteed to be saturated (Definition~\ref{dintrosat}). It is called {\em positive} if $f_P(n)$, if $P$ is nonempty, is guaranteed to be {\em positive} (Definition~\ref{dintropos1}). We allow $m$, the number of constraints, to be exponential in $n$. Hence, we cannot assume that $A$ and $b$ are explicitly specified. Rather, it is assumed that the polytope $P$ is specified in the form of a (polynomial-time) separation oracle in the spirit of Gr\"otschel, Lov\'asz and Schrijver \cite{lovasz}; cf. Section~\ref{sseporacle}. Given a point $x \in \R^n$, the separation oracle tells if $x \in P$, and if not, gives a hyperplane that separates $x$ from $P$. The following is the main complexity-theoretic result in this paper. \begin{theorem} \label{tintrosat} (cf. Section~\ref{ssaturated}) \begin{enumerate} \item Index of the Ehrhart quasi-polynomial $f_P(n)$ of a polytope $P$ presented by a separation oracle can be computed in oracle-polynomial time, and hence, in polynomial time, assuming that the oracle works in polynomial time. \item A saturated, and hence positive, integer programming problem has a polynomial time algorithm. \end{enumerate} \end{theorem} The second statement is an immediate consequence of the first. It may be remarked that the index as well as the period of the Ehrhart quasi-polynomial can be exponential in the bit length of the specification of $P$. The known algorithms to compute the period (e.g. \cite{woods}) take time that is exponential in the dimension of $P$. It may be conjectured that one cannot do much better: i.e., the period, unlike the index here, cannot be computed in polynomial time, in fact, even in $2^{o(\dim(P))}$ time. Theorem~\ref{tintrosat} is the main reason why the notion of saturation defined in this paper makes sense. Indeed, the notion of saturation was introduced in \cite{zelevinsky} to reduce the condition that is hard to check--namely, whether the Littlewood-Richardson coefficient $c_{\alpha,\beta}^\lambda$ in type A is nonzero--to a condition that is easy to check--namely, whether the polynomial $\tilde c_{\alpha, \beta}^{ \lambda}(n)$ is identically nonzero. Theorem~\ref{tintrosat} does the same for the Ehrhart quasi-polynomial of a general polytope. The algorithm in Theorem~\ref{tintrosat} is based on the separation-oracle-based linear programming algorithm of Gr\"otschel, Lov\'asz and Schrijver \cite{lovasz}, and a polynomial time algorithm for computing the Smith normal form \cite{kannan}. \section{Quasi-polynomiality, positivity hypotheses, and the canonical models} \label{sintroquasi} The basic goal now is to use Theorem~\ref{tintrosat} to get polynomial time algorithms to decide nonvanishing of the structural constants in Problems~\ref{pintrokronecker}, \ref{pintroplethysm}, \ref{pintrosubgroup} and ~\ref{pintrogit}, with $X=G/P$ or a class variety. The main results in this paper which go towards this goal are as follows. \subsubsection*{Quasi-polynomiality} We associate stretching functions with the structural constants in Problems~\ref{pintrokronecker}-\ref{pintrogit}, akin to the stretching function $\tilde c_{\alpha,\beta}^\lambda(n)$ in eq.(\ref{eqintrostretch1}) associated with the Littlewwod-Richardson coefficient, and show that they are quasipolynomials; cf. Chapter~\ref{cquasipoly}. (But their periods need not be constants, as in the case of Littlewood-Richardson coefficients; in fact, they may be exponential in general.) In particular, this proves Kirillov's conjecture \cite{kirillov} for the plethysm constants. The proof is an extension of Brion's remarkable proof (cf. \cite{dehy}) of quasi-polynomiality of the stretching function associated with the Littlewood-Richardson coefficient. The main ingradient in the proof is Boutot's result \cite{boutot} that singularities of the quotient of an affine variety with rational singularities with respect to the action of a reductive group are also rational. This is a generalization of an earlier result of Hochster and Roberts \cite{hochster} in the theory of Cohen-Macauley rings. \subsubsection*{Saturation and positivity hypotheses} Using the stretching quasipolynomials above, we formulate (cf. Section~\ref{sphypo}) analogues of the saturation and positivity hypotheses SH, PH1,PH2,PH3 in Section~\ref{sintroLR} for the structural constants in Problems~\ref{pintrokronecker}-\ref{pintrosubgroup} and Problem~\ref{pintrogit}, with $X=G/P$ or a class variety. As for Littlewood-Richardson coefficients, it turns out that PH2 and PH3 imply SH. The hypotheses PH1 and SH (more strongly, PH2) together imply that the problem of deciding nonvanishing of the structural constant in any of these problems can be transformed in polynomial time into a saturated (more strongly, positive) integer programming problem, and hence, can be solved in polynomial time by Theorem~\ref{tintrosat}. In particular, this shows that all the decision problems that arise in flip (cf. Hypothesis~\ref{PHflip}) have polynomial time algorithms, assuming these positivity hypotheses. Though these algorithms are elementary, the positivity hypotheses on which their correctness depends turn out to be nonelementary. They are intimately linked to the fundamental phenomena in algebraic geometry and the theory of quantum groups, as we shall see. We also give theoretical and experimental results in support of these hypotheses; cf. Chapter~\ref{cquasipoly}-\ref{cevidence}. \subsubsection*{Canonical models} The proofs of quasi-polynomiality mentioned above also associate with each structural constant under consideration a projective scheme, called the {\em canonical model}, whose Hilbert function coicides with the stretching quasi-polynomial associated with that structural constant, akin to the model associated by Brion \cite{dehy} with the Littlewood-Richardson coefficient. These canonical models play a crucial role in the approach to the posivity hypotheses suggested in Section~\ref{sapproach}. \section{The plethysm problem} \label{sintroplethysm} We now give precise statements of these results and hypotheses for the plethysm problem (Problem~\ref{pintroplethysm}). It is the main prototype in this paper, which illustrates the basic ideas. Precise statements for the more general Problems~\ref{pintrosubgroup} and \ref{pintrogit} appear in Section~\ref{sphypo}. As for the Littlewood-Richardson coefficients (cf.(\ref{eqintrostretch1})), Kirillov \cite{kirillov} associates with a plethysm constant $a_{\lambda,\mu}^\pi$ a stretching function \begin{equation} \tilde a_{\lambda,\mu}^\pi (n)=a_{n \lambda,\mu}^{n \pi}, \end{equation} and a generating function \[ A_{\lambda,\mu}^\pi(t)=\sum_{n\ge 0} a_{n \lambda,\mu}^{n \pi} t^n. \] (Note that $\mu$ is not stretched in these definitions.) He conjectured that $A_{\lambda,\mu}^\pi(t)$ is a rational function. This is verified here in a stronger form: \begin{theorem} \label{tquasiplethysm} \noindent (a) (Rationality) The generating function $A_{\lambda,\mu}^\pi(t)$ is rational. \noindent (b) (Quasi-polynomiality) The stretching function $\tilde a_{\lambda,\mu}^\pi(n)$ is a quasi-polynomial function of $n$. This is equivalent to saying that all poles of $A_{\lambda,\mu}^\pi(t)$ are roots of unity, and the degree of the numerator of $A_{\lambda,\mu}^\pi(t)$ is strictly smaller than that of the denominator. \noindent (c) There exist graded, normal $\C$-algebras $S=S(a_{\lambda,\mu}^\pi)=\oplus_n S_n$, and $T=T(a_{\lambda,\mu}^\pi)=\oplus_n T_n$ such that: \begin{enumerate} \item The schemes $\spec(S)$ and $\spec(T)$ are normal and have rational singularities. \item $T=S^H$, the subring of $H$-invariants in $S$, where $H=GL_n(\C)$ as in Problem~\ref{pintroplethysm}, \item The quasi-polynomial $\tilde a_{\lambda,\mu}^\pi(n)$ is the Hilbert function of $T$. In other words, it is the Hilbert function of the homogeneous coordinate ring of the projective scheme $\mbox{Proj}(T)$. \end{enumerate} \noindent (d) (Positivity) The rational function $A_{\lambda,\mu}^\pi(t)$ can be expressed in a positive form: \begin{equation} \label{eqtquasip} A_{\lambda,\mu}^\pi(t)=\f{h_0+h_1 t+ \cdots+h_d t^d}{\prod_j(1-t^{a(j)})^{d(j)}}, \end{equation} where $a(j)$'s and $d(j)$'s are positive integers, $\sum_j d(j)=d+1$, where $d$ is the degree of the quasi-polynomial $\tilde a_{\lambda,\mu}^\pi(n)$, $h_0=1$, and $h_i$'s are nonnegative integers. \end{theorem} The specific rings $S(a_{\lambda,\mu}^\pi)$ and $T(a_{\lambda,\mu}^\pi)$ constructed in the proof of Theorem~\ref{tquasiplethysm} are very special. We call them {\em canonical rings} associated with the plethysm constant $a_{\lambda,\mu}^\pi$. We call $Y(a_{\lambda,\mu}^\pi)=\proj(S(a_{\lambda,\mu}^\pi))$, and $Z(a_{\lambda,\mu}^\pi)=\proj(T(a_{\lambda,\mu}^\pi))$ the {\em canonical models} associated with $a_{\lambda,\mu}^\pi$. The canonical rings are their homogenous coordinate rings. The positive rational form in Theorem~\ref{tquasiplethysm} (d) is not unique, and in general, need not be reduced (cf. Definition~\ref{dintroreducedpos}). Indeed, there is one such form for every h.s.o.p. (homogeneous sequence of parameters) of the homogenenous coordinate ring $S$; the $a(j)$'s in eq.(\ref{eqtquasip}) are the degrees of these parameters. Kirillov also asked if the only possible pole of $A_{\lambda,\mu}^\pi$ is at $t=1$--i.e. if $a_{\lambda,\alpha}^\mu(n)$ is a polynomial. This is not so (cf. Section~\ref{sevikron}). But it may be conjectured that the structural constants $a(j)$'s are small. Specifcally, consider an h.s.o.p. of $S$ with a (lexicographically) minimum degree sequence, and call the (unique) positive rational form in Theorem~\ref{tquasiplethysm} (d) associated with such an h.s.o.p. {\em minimal}. Then: \begin{conj} \label{cminimalplethysm} The minimal positive rational form of $A_{\lambda,\mu}^\pi(t)$ is reduced (cf. Definition~\ref{dintroreducedpos}) with modular index bounded by a polynomial in the heights of the partitions $\lambda,\mu$ and $\pi$; by the height of a partition we mean the height of the corresponding Young diagram. \end{conj} This would imply that the period of $A_{\lambda,\mu}^\pi(t)$ is smooth--i.e. has small prime factors--though it may be exponential in the heights of $\lambda,\mu,\pi$. It may be remarked that the analogue of Theorem~\ref{tquasiplethysm} (b) for Littlewood-Richardson coefficients has an elementary polyhedral proof. Specifically, the Littlewood-Richardson stretching function $\tilde c_{\alpha,\beta}^\lambda(n)$ of any type is a quasi-polynomial since it coincides with the Ehrhart quasi-polynomial of the BZ-polytope \cite{berenstein}. Similalry, the analogue of Theorem~\ref{tquasiplethysm} (d) for Littlewood-Richardson coefficients follows from Stanley's positivity theorem for the Ehrhart series of a rational polytope (which is implicit in \cite{stanleytoric}). These polyhderal proofs cannot be extended to the plethysm constant at this point, since no polyhedral expression for them is known so far--in fact, this is a part of the conjectural positivity hypothesis PH1 below. In contrast, Brion's proof in \cite{dehy} of quasi-polynomiality of $\tilde c_{\alpha,\beta}^\lambda(n)$ can be extended to prove Theorem~\ref{tquasiplethysm} since it does not need a polyhedral interpretation for $a_{\lambda,\mu}^\pi$. But Boutot's result \cite{boutot} that it relies on is nonelementary (because it needs resolution of singularities in characteristic zero, among other things). We also give an elementary (nonpolyhedral proof) for Theorem~\ref{tquasiplethysm} (a) (rationality). But this does not extend to a proof of quasipolynomiality for all $n$, which turns out to be a far delicate problem. It is crucial in the context of saturated integer programming. \begin{theorem} \label{tconeplethysm} (Finitely generated cone) For a fixed partition $\mu$, let $T_\mu$ be the set of pairs $(\pi,\lambda)$ such that the irreducible representation $V_\pi(H)$ of $H=GL_n(\C)$ occurs in the irreducible representation $V_\lambda(G)$ of $G=GL(V_\mu(H))$ with nonzero multiplicity. Then $T_\mu$ is a finitely generated semigroup with respect to addition. \end{theorem} This is proved by an extension of Brion and Knop's proof of the analogous result for Littlewood-Richardson coefficients based on invariant theory. In the case of Littlewood-Richardson coefficients, this again has an elementary polyhedral proof \cite{zelevinsky}. \begin{theorem} \label{tpspaceplethysm} (PSPACE) Given partitions $\lambda,\mu,\pi$, the plethysm constant $a_{\lambda,\mu}^\pi$ can be computed in $\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi})$ space. \end{theorem} The notation $\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi})$ here means bounded by a polynomial of constant degree in $\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi}$. The main observation in the proof of Theorem~\ref{tpspaceplethysm} is that the oldest algorithm for computing the plethysm constant, based on the Weyl character formula, can be efficiently parallelized so as to work in polynomial parallel time using exponentially many processors. After this, the result follows from the relationship between parallel and space complexity classes. It may be remarked that the known algorithms for computing $a_{\lambda,\mu}^\pi$ in the literature--e.g., the one based on Klimyk's formula \cite{fultonrepr}--take exponential time as well as space. Theorems~\ref{tquasiplethysm}, \ref{tconeplethysm} and \ref{tpspaceplethysm} lead to the following conjectural saturation and positivity hypotheses for the plethysm constant. THese are analogues of PH1,PH2,PH3, SH in Section~\ref{sintroLR} for Littlewood-Richardson coefficients. \begin{hypo} {\bf (PH1)} For every $(\lambda,\mu,\pi)$ there exists a polytope $P=P_{\lambda,\mu}^\pi \subseteq \R^m$ such that: \noindent (1) The Ehrhart quasi-polynomial of $P$ coincides with the stretching quasi-polynomial $\tilde a_{\lambda,\mu}^\pi(n)$ in Theorem~\ref{tquasiplethysm}. (This means $P$ is given by a linear system of the form $A x \le b$, where $A$ does not depend on $\lambda$ and $\pi$ and $b$ depends only on $\lambda$ and $\pi$ in a homogeneous, linear fashion.) In particular, \begin{equation} \label{eqph1int} a_{\lambda,\mu}^\pi=\phi(P), \end{equation} where $\phi(P)$ is equal to the number of integer points in $P$. \noindent (2) The dimension $m$ of the ambient space, and hence the dimension of $P$ as well, are polynomial in the bitlengths $\bitlength{\lambda},\bitlength{\mu}$ and $\bitlength{\pi}$. \noindent (3) Whether a point $x \in R^m$ lies in $P$ can be decided in $\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi})$ time. That is, the membership problem belongs to the complexity class $P$. If $x$ does not lie in $P$, then this membership algorithm also outputs, in the spirit of \cite{lovasz}, the specification of a hyperplane separating $x$ from $P$. \end{hypo} The first statement here, in particular, would imply a {\em positive}, polyhedral formula for $a_{\lambda,\alpha}^\mu$, in the spirit of the known positive polyhedral formulae for the Littlewood-Richardson coefficients in terms of the BZ- \cite{berenstein}, hive \cite{knutson} or other types of polytopes \cite{dehy}. It would also imply polyhedral proofs for Theorem~\ref{tquasiplethysm} (a), (b), (d), and Theorem~\ref{tconeplethysm}. Conversely, Theorem~\ref{tquasiplethysm} (a), (b), (d), and Theorem~\ref{tconeplethysm} constitute a theoretical evidence for existence of such a positive polyhedral formula. The second statement in PH1 is justified by Theorem~\ref{tpspaceplethysm}. Specifically, it should be possible to compute the number of integer points in $P$ in PSPACE in view of Theorem~\ref{tpspaceplethysm}. If $\dim(P)$ and $m$ were exponential, then the usual algorithms for this problem, e.g. Barvinok \cite{barvinok}, cannot be made to work in PSPACE. Indeed, it may be conjectured that the number of integer points in a general polytope $P\subseteq \R^m$ can not be computed in $o(m)$ space. The number of constraints in the hive \cite{knutson} or the BZ-polytope \cite{berenstein} for the Littlewood-Richardson coefficient $c_{\alpha,\beta}^\lambda$ is polynomial in the number of parts of $\alpha,\beta,\lambda$. In contrast, the number of constraints defining $P_{\lambda,\mu}^\pi$ may be exponential in the $\bitlength{\mu}$ and the number of parts of $\lambda$ and $\pi$. But this is not a serious problem. As long as the faces of the polytope $P$ have a nice description, the third statement in PH1 is a reasonable assumption. This has been demonstrated in \cite{lovasz} for the well-behaved polytopes in combinatorial optimization with exponentially many constraints. The situation in representation theory should be similar, or even better. For example, the facets of the hive polytope \cite{knutson} are far nicer than the facets of a typical polytope in combinatorial optimization. It is known that membership in a polytope is a ``very easy'' problem. Formally, if a polytope has polynomially many constraints, this problem belongs to the complexity class $NC \subseteq P$ \cite{karp}, the subclass of problems with efficient parallel algorithms, which is very low in the usual complexity hierarchy. Even if the number of constraints of $P_{\lambda,\mu}^\pi$ in PH1 is exponential, the membership problem is still expected to be in $NC$ (cf. Remark{rnc})--which would be ``very easy'' compared to the decision problem we began with (Problem~\ref{pintroplethysm}). For this reason, PH1 is primarily a mathematical positivity hypothesis as against PHflip (Hypothesis~\ref{PHflip}), and the positive, polyhedral formula for $a_{\lambda,\mu}^pi$ in (\ref{eqph1int}) is its main content. The remaining two positivity hypotheses are purely mathematical. \begin{hypo} {\bf (PH2)} The stretching quasi-polynomial $\tilde a_{\lambda,\mu}^\pi(n)$ is positive (Definition~\ref{dintropos1}). \end{hypo} PH2 implies the following saturation hypothesis: \begin{hypo} {\bf (SH)} The quasi-polynomial $\tilde a_{\lambda,\mu}^\pi(n)$ is saturated (Defintion~\ref{dintrosat}). \end{hypo} The following is another stronger form of SH: \begin{hypo} \label{hph3plethysm} {\bf (PH3)} The rational function $A_{\lambda,\mu}^\pi(t)$ has a reduced positive form of modular index bounded by a polynomial in the heights of $\lambda,\mu$ and $\pi$. (Definition~\ref{dintroreducedpos}). \end{hypo} This is implied by Conjecture~\ref{cminimalplethysm}. The following result addresses the second arrow in Figure~\ref{fbasicintro}: \begin{theorem} The complexity theoretic positivity hypothesis PHflip (Hypothesis~\ref{PHflip}) for the plethysm constant is implied by the mathematical positivity hypotheses PH1 and PH2. Specifically, assuming PH1 and SH (or, more strongly, PH2), nonvanishing of a plethysm constant $a_{\lambda,\mu}^\pi$ can be decided in $\poly(\bitlength{\lambda},\bitlength{\mu}, \bitlength{\pi})$ time; i.e. the problem of deciding nonvanishing of a plethysm constant belongs to $P$. \end{theorem} This follows from Theorem~\ref{tintrosat}. \subsection*{Evidence for the positivity hypotheses in special cases} Littlewood-Richardson coefficients are special cases of (generalized) plethym constants. We have already seen that PH1 holds in this case, and that there is considerable experimental evidence for PH2 and PH3 (Section~\ref{sintroLR}). Another crucial special case of the plethym problem is the Kronecker problem (Problem~\ref{pintrokronecker})--in fact, this may be considered to be the crux of the plethysm problem. It follows from the results in \cite{algcomb} that PH1 holds for the Kronecker problem when $n=2$; the earlier known formulae \cite{remmel,rosas} for the Kronecker coefficient in this case are not positive. Experimental evidence for PH2 and PH3 in this case is given in Section~\ref{sevikron}. We also give in Chapter~\ref{cevidence} additional experimental evidence for PH2 for another basic special case of Problem~\ref{pintrosubgroup}, with $H$ therein being the symmetric group. \section{Towards PH1 and SH via positive bases and canonical models} \label{sapproach} In this section, we suggest an approach to prove PH1 and SH for the plethysm constant and the analogous hypotheses for the other structural constants in Problems~\ref{pintrosubgroup}, and \ref{pintrogit}, with $X=G/P$ or a class variety. In the case of Littlewood-Richardson coefficients of type A, PH1 and SH have purely combinatorial proofs. But it seems unrealistic to expect such proofs of the saturation and positivity hypotheses for the plethysm and other structural constants under consideration here given their substantially higher complexity. The approach that we suggest is motivated by the proof of PH1 for Littlewood-Richardson coefficients of arbitrary types based on the canonical (local/global crystal) bases of Kashiwara and Lusztig for representations of Drinfeld-Jimbo quantum groups \cite{dehy,kashiwara2,littelmann,lusztigcanonical,lusztigbook}. By a Drinfeld-Jimbo quantum group we shall mean in this paper quantization $G_q$ of a complex, semisimple group $G$ as in \cite{rtf} that is dual to the Drinfeld-Jimbo quantized enveloping algebra \cite{drinfeld}. Canonical bases for representions of a Drinfeld-Jimbo quantum group in type $A$ are intimately linked \cite{gro} to the Kazhdan-Lusztig basis for Hecke algebras \cite{kazhdan,kazhdan1}. A starting point for the approach suggested here is: \begin{obs} {\bf (PH0)} \label{obslusztig} The homogeneous coordinate rings of the canonical models associated by Brion with the Littlewood-Richardson coefficients have quantizations endowed with canonical bases as per Kashiwara and Lusztig. \end{obs} This is a consequence of the work of Kashiwara \cite{kashiwaraglobal} and Lusztig \cite{lusztigpnas,lusztigbook}; see Proposition~\ref{plusztigkashi} for its precise statment. This is why we call the models here canonical models. We shall refer to the property above as the zeroeth positivity hypothesis PH0. Positivity here refers to the deep characteristic positivity property of the canonical basis proved by Lusztig: namely its multiplicative and comultiplicative structure constants are nonnegative. For this reason, we say that a canonical basis is positive. Similar positivity property is also known for the Kazhdan-Lusztig basis \cite{kazhdan1}. The proofs of these positivity properties are based on the Riemann hypothesis over finite fields (Weil conjectures) \cite{weil2} and the related work of Beilinson, Bernstein, Deligne \cite{beilinson}. The property above is called PH0 because it implies PH1 for Littlewood-Richardson coefficients of arbitrary types. Specifically, the latter is a formal consequence of the abstract properties of these canonical bases and is intimately related to their positivity; cf. Sections~\ref{sexlittle}, \ref{ssmathvscomplex}\ref{sph0ph1} and \cite{dehy,kashiwara2,littelmann,lusztigbook}. The saturation hypothesis SH in type A \cite{knutson} is a refined property of the polyhedral formulae in PH1. It may be possible to extend this proof of SH to arbitrary types based on the properties of the canonical bases in Observation~\ref{obslusztig}; cf. Section~\ref{ssigni}. Furthermore, PH2 and PH3 can also be interpreted as statements regarding the canonical bases. All this together indicates that for the Littlewood-Richardson problem PH1 and SH (and possibly, PH2 and PH3 as well) are intimately linked to PH0. Now we turn to the general structural constants under consideration in this paper. Observation~\ref{obslusztig} and other evidence (cf. Section~\ref{sexamples}-\ref{squantumgroup}) lead to the following conjectural positivity hypothesis: \begin{hypo} \label{hph0intro} (PH0) The homogeneous coordinate rings of the canonical models associated in this paper with the structural constants that arise in the flip, such as the plethysm constant, have quantizations endowed with analogous positive bases. \end{hypo} See Hypothesis~\ref{hph0main} for its precise statement and Section~\ref{spositivebasis} for the definition of a positive basis in the context Problem~\ref{pintroplethysm}, and specific instances of Problems~\ref{pintrosubgroup} and \ref{pintrogit} that arise in the flip. Roughly, a basis is positive if its multiplicative and representational structural constants are nonnegative and it admits a localization with operators akin to Kashiwara's crystal operators \cite{kashiwara1} that are polynomial-time computable. Experimental and theoretical evidence for PH0 is given in \cite{GCT4,canonical} for special cases of the Kronecker problem, which is the most basic prototype of the decision problems in this paper. The discussion of the Littlewood-Richardson problem above suggests the following approach for proving PH1 and SH for the plethysm and other structural constants under consideration in this paper: \begin{enumerate} \item Construct quantizations of the homogeneous coordinate rings of the canonical models associated with these structural constants, \item Show that they have positive bases as per PH0. \item Prove PH1 and SH (and, possibly, the stronger PH2, and 3 as well) by a detailed analysis and study of these positive bases. \end{enumerate} Pictorially, this is depicted in Figure~\ref{fbasicapp}. \begin{figure} \[ \begin{array}{c} \fbox{Construction of quantizations of the coordinate rings of canonical models}\\ | \\ | \\ | \\ \downarrow \\ \fbox{Construction of positive bases for these quantizations (PH0)} \\ | \\ | \\ | \\ \downarrow \\ \fbox{Positivity and saturation hypotheses PH1, SH} | \\ | \\ | \\ \downarrow \\ \fbox{Polynomial-time algorithms for the decision problems} \end{array} \] \caption{Pictorial depiction of the approach} \label{fbasicapp} \end{figure} Quantizations of the homogeneous coordinate rings of the canonical models associated with Littlewood-Richardson coefficients and their positive canonical bases are constructed using the theory Drinfeld-Jimbo quantum group. In type $A$, it is intimately related to the theory of Hecke algebras. But, as expected, the theories of Drinfeld-Jimbo quantum groups and Hecke algebras do not work for the plethysm problem. What is needed is a quantum group and a quantized algebra that can play the same role in the plethysm problem that the Drinfeld-Jimbo quantum group and the Hecke algebra play in the Littlewood-Richardson problem. These have been constructed in \cite{GCT4} for the Kronecker problem (Problem~\ref{pintrokronecker}) and in \cite{plethysm} for the generalized plethysm problem (Problem~\ref{pintroplethysm}); cf. Section~\ref{squantumgroup} for a brief synopsis of these results. In the special case of the Littlewood-Richardson problem, these specialize to the Drinfeld-Jimbo quantum group and the Hecke algebra, respectively. It is conjectured in \cite{canonical,plethysm} on the basis of theoretical and experimental evidence that the coordinate rings of these quantum groups and these quantized algebras have positive canonical bases analogous to the canonical bases for the coordinate rings of the Drinfeld-Jimbo quantum group, and the Kazhdan-Lusztig bases for Hecke algebras. These conjectures lie at the heart of the approach suggested here, since they are crucial for construction of quantizations endowed with positive bases of the homogeneous coordinate rings of the canonical models associated with the plethysm constants as in Hypothesis~\ref{hph0intro}. Their verification seems to need substantial extension of the work surrounding the Riemann hypothesis over finite fields mentioned above. \section{Basic plan for implementing the flip} \begin{figure}[!p] \centering \[\begin{array} {c} \fbox{Negative hypotheses in complexity theory (Lower bound problems)} \\ |\\ | \\ \mbox{The flip}\\ |\\ \downarrow \\ \fbox{Positive hypotheses in complexity theory (Upper bound problems)} \\ |\\ | \\ \mbox{Saturated and positive integer programming, and} \\ \mbox{the quasi-polynomiality results in this paper}\\ |\\ \downarrow \\ \fbox{Mathematical saturation and positivity hypotheses: PH1,SH (PH2,3)} \\ |\\ |\\ \mbox{Construction of the canonical models in this paper, and }\\ \mbox{construction of the quantum groups in GCT4,7}\\ |\\ ?? \\ |\\ \downarrow \\ \fbox{\parbox{3.75in}{(PH0): Construction of quantizations of the coordinate rings of the canonical models and their positive bases}} \\ |\\ |\\ |\\ ?? \\ |\\ |\\ \downarrow \\ \fbox{\parbox{4in}{(?): Problems related to the Riemann Hypothesis over finite fields, and their generalizations}} \end{array}\] \caption{A basic plan for implementing the flip} \label{fflip} \end{figure} A basic plan for implementing the flip suggested by the considerations above is summarized in Figure~\ref{fflip}. It is an elaboration of Figure~\ref{fbasicintro}. Question marks in the figure indicate open problems. \section{Organization of the paper} The rest of this paper is organized as follows. In Chapter~\ref{cprelim} we describe the basic complexity theoretic notions that we need in this paper and describe their significance in the context of representation theory. In Chapter~\ref{csatpos}, we give a polynomial time algorithm for saturated integer programming (Theorem~\ref{tintrosat}), and give precise statements of the results and positivity hypotheses for Problems~\ref{pintrosubgroup} and \ref{pintrogit} (with $X=G/P$ or a class variety) mentioned in Section~\ref{sintroquasi}. These generalize the ones given in Section~\ref{sintroplethysm} for the plethysm constant. The framework of saturated integer programming in this paper may be applicable to many other structural constants in representation theory and algebraic geometry, such as the Kazhdan-Lusztig polynomials (cf. Sections~\ref{sother} and \ref{sskazhdan}). With this in mind, we also describe extension of the saturated programming paradigm to the $q$-setting. In Chapter~\ref{cquasipoly}, we prove the basic quasi-polynomiality results--Theorem~\ref{tquasiplethysm} and its generalizations for Problems~\ref{pintrosubgroup} and \ref{pintrogit}. We also define canonical models for the structural constants under consideration, define positive bases, give a precise statement of Hypothesis~\ref{hph0intro} (PH0), and indicate how it may lead to PH1,3. In Chapter~\ref{cpspace}, we prove the basic PSPACE results--Theorem~\ref{tpspaceplethysm} and its extensions for the various cases of Problem~\ref{pintrosubgroup}. In Chapter~\ref{cevidence}, we give experimental evidence for the positivity hypotheses PH2 and PH3 in some special cases of the Problems~\ref{pintrokronecker}-\ref{pintrogit}. \section{Notation} We let $\bitlength{X}$ denote the total bitlength of the specification of $X$. Here $X$ can be an integer, a partition, a classifying label of an irreducible representation of a reductive group, a polytope, and so on. The exact meaning of $\bitlength{X}$ will be clear from the context. The notation $\poly(n)$ means $O(n^a)$, for some constant $a$. The notation $\poly(n_1,n_2,\ldots)$ similarly means bounded by a polynomial of a constant degree in $n_1,n_2,\ldots$. Given a reductive group $H$, $V_\lambda(H)$ denotes the irreducible representation of $H$ with the classifying label $\lambda$. The meaning depends on $H$. Thus if $H=GL_n(\C)$, $\lambda$ is a partition and $V_\lambda(H)$ the Weyl module indexed by $\lambda$, if $H=S_m$, then $\lambda$ is a partition of size $|\lambda|=m$, and $V_\lambda(H)$ the Specht module indexed by $\lambda$, and so on. \section{Acknoledgements} We are grateful to Peter Littelmann for bringing the reference \cite{dehy} to our attention, to H. Narayanan for suggesting the use of \cite{kannan} in the proof of Theorem~\ref{tindexquasi} and bringing the positivity conjecture in \cite{loera} to our attention, and to Madhav Nori for a helpful discussion. The experimental results in Chapter~\ref{cevidence} were obtained using Latte \cite{latte}. %\include{defn} \chapter{Preliminaries in complexity theory} \label{cprelim} In this chapter, we recall basic definitions in complexity theory, introduce additional ones, and illustrate their significance in the context of representation theory. \section{Standard complexity classes} \label{sstandard} As usual, $P$, $NP$ and $PSPACE$ are the classes of problems that can be solved in polnomial time, nondeterministic polynomial time, and polynomial space, respectively. The class of functions that can be computed in polynomial time (space) is sometimes denoted by $FP$ (resp. $FPSPACE$). But, to keep the notation simple, we shall denote these classes by $P$ and $PSPACE$ again. Let $SPACE(s(N))$ denote the class of problems that can be solved in $O(s(N))$ space on inputs of bit length $N$; by convention $s(N)$ counts only the size of the work space. In other words, the size of the input, which is on the read-only input tape, and the output, which is on the write-only output tape is not counted. Hence $s(N)$ can be less than the size of the input or the output, even logarithmic compared to these sizes. The class $space(\log(N))$ is denoted by LOGSPACE. An algorithm is called strongly polynomial \cite{lovasz}, if given an input $x=(x_1,\ldots,x_k)$, \begin{enumerate} \item the total number of arithmetic steps ($+,*,-$ and comparisones) in the algorithm is polynomial in $k$, the total number of input parameters, but does not depend $\bitlength{x}$, where $\bitlength{x}=\sum_i \bitlength{x_i}$ denotes the bitlength of $x$. \item the bit length of every intermediate operand in the computation is polynomial in $\bitlength{x}$. \end{enumerate} Clearly, a strongly polynomial algorithm is also polynomial. let strong $P \subseteq P$ denote the subclass of problems with strongly polynomial time algorithms. \ignore{Similarly, a strongly polynomial space algorithm means \begin{enumerate} \item the total number of intermediate operands (in the work space) is polynomial in $k$, the total number of input parameters, but does not depend on the bit lengths of these parameters, and \item the bit length of every intermediate operand in the computation is polynomial in the total bit length $||a||$ of the input. \end{enumerate} Let $strongPSPACE \subseteq PSPACE$ be the subclass of problems having strongly polynomial space algorithms. } The counting class associated with $NP$ is denoted by $\#P$. Specifically, a function $f:\N^k\rightarrow \N$, where $\N$ is the set of nonnegative integers, is in $\#P$ if it has a formula of the form: \begin{equation} \label{eqsharpp1} f(x)=f(x_1,\cdots,x_k)=\sum_{y \in \N^l} \chi(x,y), \end{equation} where $\chi$ is a polynomial-time computable function that takes values $0$ or $1$, and $y$ runs over all tuples such that $\bitlength{y}=\poly(\bitlength{x})$. The formula (\ref{eqsharpp1}) is called a $\#P$-formula. An important feature of a $\#P$-formula in the context of representation theory is that it is {\em positive}; i.e., it does not contain any alternating signs. The formula (\ref{eqsharpp1}) is called a strong $\#P$-formula, if, in addition, $l$ is polynomial in $k$ and $\chi$ is a strongly polynomial-time computable function. Let strong $\#P$ be the class of functions with strong $\#P$-fomulae. It is known and easy to see that \begin{equation} \#P \subseteq PSPACE. \end{equation} \subsection{Example: Littlewood-Richardson coefficients} By the Littlewood-Richardson rule \cite{fultonrepr}, the coefficient $c_{\alpha,\beta}^\lambda$ (cf. Problem~\ref{pintrolittle}) in type $A$ is given by: \begin{equation} \label{eqdefnlittle1} c_{\alpha,\beta}^\lambda=\sum_T \chi(T), \end{equation} where $T$ runs over all numbering of the skew shape $\lambda / \alpha$, and $\chi(T)$ is $1$ if $T$ is a Littlewood-Richardson skew tableau of content $\beta$, and zero, otherwise. The total number of entries in $T$ is quadratic in the total number of nonzero parts in $\alpha,\beta,\lambda$, and the number of arithmetic steps needed to compute $\chi(T)$ is linear in this total number. Hence (\ref{eqdefnlittle1}) is a strong $\#P$-formula, and Littlewood-Richardson function $c(\alpha,\beta,\lambda)=c_{\alpha,\beta}^\lambda$ belongs to strong $\#P$. It may be remarked that the character-based formulae for the Littlewood-Richardson coefficients are not $\#P$-formulae, since they involve alternating signs. But the algorithms based on the these formulae for computing Littlewood-Richardson coefficients run in polynomial space. Thus, from the perspective of complexity theory, the main significance of the Littlewood-Richardson rule is that it puts the problem, which at the surface is only in $PSPACE$, in its smaller subclass (strong) $\#P$. Though the Littlewood-Richardson rule is often called efficient in the representation theory literature, it is not really so from the perspective of complexity theory. Because computation of $c_{\alpha,\beta}^\lambda$ using this formula takes time that is exponential in both the total number of parts of $\alpha,\beta$ and $\lambda$, and their bit lengths. This is inevitable, since this problem is $\#P$-complete \cite{hari}. Specifically, this means there is no polynomial time algorithm to compute $c_{\alpha,\beta}^\lambda$, assuming $P\not = NP$. As remarked in earlier, nonzeroness (nonvanishing) of $c_{\alpha,\beta}^\lambda$ can be decided in $\poly(\bitlength{\alpha},\bitlength{\beta},\bitlength{\lambda})$ time; \cite{loera,GCT3,knutson}. Furthermore, the algorithm in \cite{GCT3} is strongly polynomial; i.e., the number of arithemtic steps in this algorithm is a polynomial in the total number of parts of $\alpha,\beta,\lambda$, and does not depend on the bit lengths of $\alpha,\beta,\lambda$. Hence the problem of deciding nonvanishing of $c_{\alpha,\beta}^\lambda$ (type $A$) belongs to strong $P$. The discussion above shows that the Littlewood-Richardson problem is akin to the problem of computing the permanent of an integer matrix with nonnegative coefficients. The latter is known to be $\#P$-complete \cite{valiant}, but its nonvanishing can be decided in polynomial time, using the polynomial-time algorithm for finding a perfect matching in bipartite graphs \cite{schrijver}. If the positivity hypotheses in this paper hold, the situation would be similar for many fundamental structural constants in representation theory and algebraic geometry. \section{Convex $\#P$} \label{sconvexsharpp} Next we want to introduce a subclass of $\#P$ called convex $\#P$. Given a polytope $P \subseteq R^l$, let $\chi_P$ denote the characteristic (membership) function of $P$: i.e., $\chi_P(y)=1$, if $y\in P$, and zero otherwise. We say that $f=f(x)=f(x_1,\ldots,x_k)$ has a convex $\#P$-formula if, for every $x \in \Z^k$, there exists a convex polytope (or, more generally, a convex body) $P_x \subseteq \R^l$, such that \begin{enumerate} \item The membership function $\chi_{P_x}(y)$ can be computed in $\poly(\bitlength{x},\bitlength{y})$ time, and \item \begin{equation} \label{eqconvex0} f(x)=\phi(P_x), \end{equation} where $\phi(P_x)$ denotes the number of integer points in $P_x$. Equivalently, \begin{equation} \label{eqconvex1} f(x)=\sum_{y\in \Z^l} \chi_{P_x}(y), \end{equation} where $y$ runs over tuples in $\Z^l$ of $\poly(\bitlength{x})$ bitlength, and $\chi_{P_x}$ denotes the membership function of the polytope $P_x$. \end{enumerate} Equation (\ref{eqconvex1}) is similar to eq.(\ref{eqsharpp1}). The main difference is that $\chi$ is now the membership function of a convex polytope. Clearly, eq.(\ref{eqconvex1}), and hence, eq.(\ref{eqconvex0}) is a $\#P$-formula, when $\chi_{P_x}$ can be computed in polynomial time. Let convex $\#P$ be the subclass of $\#P$ consisting of functions with convex $\#P$-formulae. We say that eq.(\ref{eqconvex0}) is a strongly convex $\#P$-formula, if the characteristic function of $P_x$ is computable in strongly polynomial time. Let strongly convex $\#P$ be the subclass of $\#P$ consisting of functions with strongly convex $\#P$-formulae. We do not assume in eq.(\ref{eqconvex0}) that the polytope $P_x$ is explicitly specified by its defining constraints. Rather, we only assume, following \cite{lovasz}, that we are given a computer program, called a {\em membership oracle}, which, given input parameters $x$ and $y$, tells whether $y \in P_x$ in $\poly(\bitlength{x},\bitlength{y})$ time. If the number of constraints defining $P_x$ is polynomial in $\bitlength{x}$, then it is possible to specify $P_x$ by simply writing down these constraints. In this case the membership question can be trivially decided in polynomial time--in fact, even in LOGSPACE--by verifying each constraint one at a time. This would not work if $P_x$ has exponentially many constraints. In good cases, it is possible to answer the membership question in polynomial time even if $P_x$ has exponentially many facets. Many such examples in combinatorial optimization are given in \cite{lovasz}. One such illustrative example in representation theory is given in Section~\ref{slittlecone}. In contrast to the BZ-polytopes that arise in the Littlewood-Richardson problem, the polytopes that would arise in the plethysm and other problems of main interest in this paper are also expected to be of this kind. We now illustrate the notion of convex $\#P$ with a few examples in representation theory. \subsection{Littlewood-Richardson coefficients} \label{sconvexlittle} A geeneralized Littlewood-Richardson coefficient $c_{\alpha,\beta}^\lambda$ for arbitrary semisimple Lie algebra (Problem~\ref{pintrolittle}) has a strong, convex $\#P$-formula, because \[c_{\alpha,\beta}^\lambda=\phi(P_{\alpha,\beta}^\lambda),\] where $P_{\alpha,\beta}^\lambda$ is the BZ-polytope \cite{berenstein} associated with the triple $(\alpha,\beta,\lambda)$. It is easy to see from the description in \cite{berenstein} that the number of defining constraints of $P_{\alpha,\beta}^\lambda$ is polynomial in the total number of parts (coordinates) of $\alpha,\beta,\lambda$. Given $\alpha,\beta,\lambda$, these constraints can be computed in strongly polynomial time. Hence, the membership problem for $P_{\alpha,\beta}^\lambda$ belongs to $LOGSPACE \subseteq P$. It follows that the Littlewood-Richardson function $c(\alpha,\beta,\lambda)=c_{\alpha,\beta}^\lambda$ belongs to strongly convex $\#P$. \subsection{Littlewood-Richardson cone} \label{slittlecone} We now give a natural example of a polytope in representation theory, the number of whose defining constraints is exponential, but whose membership function can still be computed in polynomial time. Given a complex, semisimple, simply connected group $G$, let the Littlewood-Richardson semigroup $LR(G)$ be the set of all triples $(\alpha,\beta,\lambda)$ of dominant weights of $G$ such that the irreducible module $V_\lambda(G)$ appears in the tensor product $V_\alpha(G) \otimes V_\beta(G)$ with nonzero multiplicity \cite{zelevinsky}. Brion and Knop \cite{elashvili} have shown that $LR(G)$ is a finitely generated semigroup with respect to addition. This also follows from the polyhedral expression for Littlewood-Richardson coefficients in terms of BZ-polytopes \cite{zelevinsky}. Let $LR_\R(G)$ be the polyhedral cone generated by $LR(G)$. When $G=GL_n(\C)$, the facets of $LR_\R(G)$ have an explicit description by the affirmative solution to Horn's conjecture in \cite{kly,knutson}. But their number can be quite large (possibly exponential). Nevertheless, membership of any rational $(\alpha,\beta,\lambda)$ (not necessarily integral) in $LR_\R(G)$ can be decided in strongly polynomial time. This is because $LR_\R(G)$ is the projection of a polytope $P(G)$, the number of whose constraints is polynomial in the heights of $\alpha,\beta,\lambda$ \cite{zelevinsky}. If $\phi: P(G)\rightarrow LR(G)$ is this projection, we can choose $P(G)$ so that for any integral $(\alpha,\beta,\lambda)$, $\phi^{-1}(\alpha,\beta,\lambda)$ is the BZ-polytope associated with the triple $(\alpha,\beta,\lambda)$. To decide if $(\alpha,\beta,\lambda) \in LR(G)$, we only have to decide if the polytope $\phi^{-1}(\alpha,\beta,\lambda)$ is nonempty. This can be done in strongly polynomial time using Tardos' linear programming algorithm \cite{tardos}. For any linear function $l=l(\alpha,\beta,\lambda)$, let $LR_{l}(G)$ be the intersection of $LR(G)$ with the hyperplane $l=0$. It follows that the membership in $LR_{l}(G)$ can be decided in polynomial time. Assume that $LR_{l}(G)$ is bounded. Let \[N_{l}(G)=\{(\alpha,\beta,\lambda \in LR(G) \ | \ l(\alpha,\beta,\lambda=0\}\] be the number of interger points in $LR_{l}(G)$. Then, it follows that $N_{l}(G)$ has a convex $\#P$-formula, namely \[ N_{l}(G)=\sum_{\alpha,\beta,\lambda} \chi_{LR_{l}(G)}(\alpha,\beta,\lambda). \] For general $\alpha,\beta,\lambda,l$, the number of constraints of $LR_l(G)$ can be exponential. \subsection{Eigenvalues of Hermitian matrices} Here is another example of a polytope in representation theory with exponentially many facets, whose membership problem can still belong to $P$. For a Hermitian matrix $A$, let $\lambda(A)$ denote the sequence of eigenvalues of $A$ arranged in a weakly decreasing order. Let $HE_r$ be the set of triple $(\alpha,\beta,\lambda) \in \R^r$ such that $\alpha=\lambda(A+B)$, $\beta=\lambda(A)$, $\lambda=\lambda(B)$ for some Hermitian matrices $A$ and $B$ of dimension $r$. It is closely related to the Littlewood-Richardson semisgroup $LR_r=LR(GL_r(\C))$: $HE_r \cap P_r^3=LR_r$, where $P_r$ is the semigroup of partitions of length $\le r$. I. M. Gelfand asked for an explicit description of $HE_r$. Klyachko \cite{kly} showed that $HE_r$ is a convex polyhedral cone. An explicit description of its facets is now known by the affirmative answer to Horn's conjecture. But their number may be exponential. Hence, membership in $HE_r$ is still not easy to check using this explicit description. This leads to the following complexity theoretic variant of Gelfand's question: \begin{question} Does the memembership problem for $HE_r$ belong to $P$? \end{question} Given that the answer is yes for the closely related $LR_r=LR(GL_r(\C))$ (Section~\ref{slittlecone}), this may be so. If $HE_r$ were a projection of some polytope with polynomially many facets, this would follow as in Section~\ref{slittlecone}. But this is not necessary. For example, Edmond's perfect matching polytope for non-bipartite graphs is not known to be a projection of any polytope with polynomially many constraints. Still the associated membership problem belongs to $P$ \cite{schrijver}. \section{Separation oracle} \label{sseporacle} Suppose $P \subseteq \R^l$ is a convex polytope whose membership function $\chi_P$ is polynomial time computable. If $\chi_P(y)=0$ for some $y \in \R^r$, it is natural to ask, in the spirit of \cite{lovasz}, for a ``proof'' of nonmembership in the form of a hyperplane that separates $y$ from $P$. In this paper, we assume that all polytopes are specified by the {\em separation oracle}. This is a computer program, which given $y$, tells if $y \in P$, and if $y\not \in P$, returns such a separting hyperplane as a proof of nonmembership. We assume that the hyperplane is given in the form $l=0$, where a linear function $l$ such that $P$ is contained in the half space $l\ge 0$, but $l(y)<0$. Furthermore. we assume that $P$ is a well-described polyhedron in the sense of \cite{lovasz}. This is means $P$ is specified in the form of a triple $(\chi_P,n,\phi)$, where $P\subseteq \R^n$, $\chi_P$ is a program for computing the membership function given $y\in \R^n$, and there exists a system of inequalities with rational coefficients having $P$ as its solution set such that the encoding bit length of each inequality is at most $\phi$. We define the encoding length $\bitlength{P}$ of $P$ as $n+\phi$. We also assume that the separation oracle works in $O(\poly(\bitlength{P},\bitlength{y})$ time. For example, the polynomial time algorithm for the membership function of the Littlewood-Richardson cone (cf. Section~\ref{slittlecone}) can be easily modified to return a separating hyperplane as a proof of nonmembership. In what follows, we shall assume, as a part of the definition of a convex $\#P$-formula, that $P_x$ in (\ref{eqconvex0}) is a well-described polyhedron specified by a separation oracle that works in polynomial time with $\bitlength{P_x}=\poly(\bitlength{x})$. These additional requirements are needed for the saturated integer programming algorithm in Chapter~\ref{csatpos}. %\include{satposintpgm} \chapter{Saturation and positivity} \label{csatpos} In this chapter we describe (Section~\ref{ssaturated}) a polynomial time algorithm for saturated and positive integer programming (Theorem~\ref{tintrosat}). In Section~\ref{sphypo} we state the main results and positivity hypotheses for Problem~\ref{pintrosubgroup} and Problem~\ref{pintrogit}, with $X=G/P$ or a class variety therein. Together they say that these problems can be efficiently transformed into saturated (more strongly, positive) integer programming problems, and hence can be solved in polynomial time. We also describe an extension of the saturated programming algorithm to the $q$-setting (Section~\ref{sqsat}), and examine the role of saturation and positivity in the context of Kazhdan-Lusztig polynomials (Section~\ref{sskazhdan}). \section{Saturated and positive integer programming} \label{ssaturated} We begin by proving Theorem~\ref{tintrosat}. Let $P\subseteq R^n$ be a polytope given by a separation oracle (Section~\ref{sseporacle}). The integer programming problem is to determine if $P$ contains an integer point. Let $\bitlength{P}$ be the encoding length of $P$ as defined in Section~\ref{sseporacle}. An oracle-polynomial time algorithm \cite{lovasz} is an algorithm whose running time is $O(\poly(\bitlength{P}))$, where each call to the separation oracle is computed as one step. Thus if the separation oracle works in polynomial time, then such an algorithm works in polynomial time in the usual sense. Let $\phi(P)$ be the number of integer points in $P$. Let $f_P(n)=\phi(n P)$ be the Ehrhart quasi-polynomial \cite{stanleyenu} of $P$. Let $l(P)$ be the least period of $f_P(n)$, if $P$ is nonempty. Let $f_{i,P}(n)$, $1\le i \le l(P)$, be the polynomials such that $f_P(n)=f_{i,P}(n)$ if $n=i$ modulo $l(P)$. Let $F_P(t)=\sum_{n\ge 0} f_P(n) t^n$ denote the Ehrhart series of $P$. It is a rational function. \begin{theorem} \label{tindexquasi} \noindent (a) The index of $f_P(n)$, $\ind(f_P)$, can be computed in oracle-polynomial time, and hence, in polynomial time, assuming that the oracle works in polynomial time. \noindent (b) Thus, saturated, and hence, positive integer programming problem, as defined in Section~\ref{ssatpospgm}, can be solved in oracle-polynomial time. \end{theorem} \proof \noindent (a): Nonemptyness of $P$ can be decided in oracle-polynomial time using the algorithm of Gr\"otschel, Lov\'asz and Schrijver \cite{lovasz} (cf. Theorem 6.4.1 therein). An extension of this algorithm, furthermore, yields a specification of the affine space $\mbox{span}(P)$ containing $P$ if $P$ is nonempty (cf. Theorems 6.4.9, and 6.5.5 in \cite{lovasz}). Specifically, it outputs an integral matrix $C$ and an integral vector $d$ such that $span(P)$ is defined by $C x=d$. This final specification is exact, even though the first part of the algorithm in \cite{lovasz} uses the ellipsoid method. Indeed, the use of simultneous diophantine approximation based on basis reduction in lattices is precisely to ensure this exactness in the final answer. This is crucial for the next step of our algorithm. If $P$ is empty, $\ind(f_P)=0$. So assume that it is nonempty. Let $\bar C$ be the Smith normal form of $C$; i.e., $\bar C= A C B$ for some unimodular matrices $A$ and $B$, where the leftmost principal submatrix of $\bar C$ is a diagonal, integral matrix, and all other columns are zero. The matrices $\bar C, A$ and $B$ can be computed in polynomial time using the algorithm in \cite{kannan}. After a unimodular change of coordinates, by letting $z=B^{-1} x$, $\mbox{span}(P)$ is specified by the linear system $\bar C z=\bar d=A d$. The equations in this system are of the form: \begin{equation} \label{eqspan1} \bar c_i z_i=\bar d_i, \end{equation} $i \le \mbox{codim}(P)$, for some integers $\bar c_i$ and $\bar d_i$. By removing common factors if necessary, we can assume that $\bar c_i$ and $\bar d_i$ are relatively prime for each $i$. Let $\tilde c$ be the l.c.m. of $\bar c_i$'s. The statement (a) follows from: \begin{claim} $\ind(f_P)=\tilde c$. \end{claim} \noindent {\em Proof of the claim:} Indeed, $n P=\{n z \ | \ z \in P\}$ contains no integer point unless $\tilde c$ divides $n$. Hence, it is easy to see that $F_P(t)=F_{\bar P}(t^{\tilde c})$, where $F_{\bar P}(x)$ is the Ehrhart series of the dilated polytope $\bar P=\tilde c P$. By eq.(\ref{eqspan1}), the equations defining $\bar P$ are: \begin{equation} \label{eqspan2} z_i=\bar d_i (\tilde c/\bar c_i), \end{equation} Clearly, $\tilde c$ divides the least period $l(P)$ of $f_P$, and $l(\bar P)=l(P)/\tilde c$ is the period of the Ehrhart quasipolynomial $f_{\bar P}(n)$. It suffices to show that the index of $f_{\bar P}(n)$ is one. That is, $f_{\tilde c,P}$ is not identically zero. This is equivalent to showing that $\bar P$ contains a point $z$ with with $z_i=a_i/b$, for some integers $a_i$'s and $b$ such that $b=1$ modulo $l(\bar P)$. Let us call such a point admissible. Because of the form of the equations (\ref{eqspan2}) defining $\mbox{span}(\bar P)$, we can assume, without loss of generality, that $\bar P$ is full dimensional. This means the system (\ref{eqspan2}) is empty. Then this follows from denseness of the set of admissible points. This proves the claim, and hence (a). \noindent (b): This immediately follows from (a) and Definitions~\ref{dintrosat}, and \ref{dintropos1}. \qed We note down one corollary of the proof (this should be well known): \begin{prop} \label{pcorsatint} The rational function $F_P(t)=F_{\bar P}(t^{\tilde c})$, where $F_{\bar P}(x)$ is the Ehrhart series of the dilated polytope $\bar P=\tilde c P$, and $\tilde c$ is the index of $f_P(n)$. \end{prop} This, in conjunction with Stanley's positivity result \cite{stanleytoric}, gives a different definition of saturation: \begin{prop} \label{psatequivdefn} The Ehrhart quasipolynomial $f_P(n)$ is saturated iff the Ehrhart series $F_P(t)$ has a reduced positive form (cf. Definition~\ref{dintroreducedpos}). \end{prop} Here we use a slightly stronger definition of saturation as in Remark~\ref{rsatstronger}. \begin{remark} The rational functions in Hypotheses~\ref{hintrolittleph3gen} and \ref{hph3plethysm} are stipulated to have reduced positive form in view of this result. \end{remark} \proof If $F_P(t)$ has a reduced positive form then $f_P(n)$ is clearly staturated; cf. remarks after Definition~\ref{dintrosat}. Conversely, suppose $f_P(n)$ is not identically zero and saturated. Let $c=\ind(f_P)$. The quasipolynomial $f_P(n)$ has two properties: \noindent (1) $f_P(c) \not = 0$. This follows from saturation. \noindent (2) $f_P(n) \not =0$ only if $n$ is divisible by $c$. This follows from Proposition~\ref{pcorsatint}. Following Stanley \cite{stanleytoric}, we can associate with $P$ a Cohen-Macauley graded ring $T_P$, whose Hilbert function coincides with $f_P(n)$. By (1) and (2) it follows that $T_P$ has an h.s.o.p. $(t_0,\ldots,t_k)$, where $k=\deg(f_P)+1$, each $d_i=\deg(t_i)$ is divisible $c$, and $d_0=c$. Since $T_P$ is Cohen-Macauley it follows \cite{stanleycomb} that $F_P(t)=F_{\bar P}(t^c)$, where $F_{\bar P}(x)$ has the form \[ F_{\bar P}(x)= \f{h_d x^d +\cdots + h_0}{\prod_{i=0}^k (1-x^{a_i})}, \] where (1) $h_0=1$, (2) $h_i$'s are nonnegative integers, (3) $a_i=d_i/c$, and (4) $a_0=1$. This means $F_P(t)$ has a reduced positive form. \qed If $P$ is explicitly specified in the form a linear system \begin{equation} \label{eqAB} A x \le b, \end{equation} where $A$ is an $m\times n$ matrix, $b$ an $m$ vector and $m=\poly(n)$, then the following stronger version of Theorem~\ref{tindexquasi} holds. Let $\bitlength{A}$ and $\bitlength{A,b}$ denote the bitlength of the specification of $A$ and of the linear system (\ref{eqAB}). \begin{theorem} \label{tstrongindex} Suppose $P$ is specified in terms of an explicit linear system (\ref{eqAB}). Then the index of the Erhart quasi-polynomial $f_P(n)$ can be computed in $\poly(\bitlength{A,b})$ time, using $\poly(\bitlength{A})$ arithmetic operations. Thus, saturated, and hence, positive integer programming problem specified in the form (\ref{eqAB}) can be solved in in $\poly(\bitlength{A,b})$ time, using $\poly(\bitlength{A})$ arithmetic operations. \end{theorem} \proof This is proved exactly as Theorem~\ref{tindexquasi}, but with Tardos' strongly polynomial time algorithm for combinatorial linear programming \cite{tardos} used in place of the algorithm in \cite{lovasz}. \qed \subsection{Extensions} \label{ssextension} We now mention a few straightforard extensions of Theorem~\ref{tindexquasi}. First, it is not necessary that $P$ be a closed polytope. We can allow it to be half-closed. Specifically, it can be a solution set of a system of inequalitites of the form: \begin{equation} A_1 x \le b_1 \quad \mbox{and} \quad A_2 x < b_2, \end{equation} where we have allowed strict inequalities. The function $F_P(n)=\phi(n P)$, the number of integer points in $n P$, is again a quasi-polynomial. Hence, the notions of saturation and positivity can be generalized to this setting in a natural way. Second, the algorithm in Theorem~\ref{tindexquasi} only needs the following: \noindent {\bf Saturation guarantee:} If the affine span of $P$ contains an integer point, then $P$ is guaranteed to contain an integer point. If $f_P(n)$ is guaranteed to be saturated, then this guarantee holds, as can be seen from the proof of Theorem~\ref{tindexquasi}. \subsection{The optimization problem}\label{ssoptimize} The algorithm in the proof of Theorem~\ref{tindexquasi} has a curious property. It can decide if the polytope $P$ contains an integer point, but cannot return such a point as a ``proof'' if it does. A folklore in complexity theory is that if an existence problem is in the complexity class $P$, then, under reasonable conditions, the associated search and optimization problems should also be in $P$. This leads to: \begin{question} \label{qopti} Given a positive integer programming problem as in Theorem~\ref{tindexquasi}, is there a polynomial time algorithm to find an integer point in $P$, if it contains one? More generally, is there a polynomial time algorithm for the optimization version of the positive integer programming problem? \end{question} In the optimization version, one is also given a linear fuction $l$, and the goal is to find an integer point in $P$ where $l$ is optimized, if $P$ contains an integer point. Though an affirmative answer to this question is not needed in the context of Problems~\ref{pintrokronecker}-\ref{pintrogit}, it is needed in the context of a decision problem associated with Kazhdan-Lusztig polynomials (Section~\ref{sskazhdan}). \subsection{Is there a simpler algorithm?} \label{sistheresimpler} Though the algorithm for saturated integer programming in Theorem~\ref{tindexquasi} is conceptually very simple, in reality it is quite intricate, because the work of Gr\"otschel, Lov\'asz and Schrijver \cite{lovasz} needs a delicate extension of the ellipsoid algorithm \cite{khachian} and the polynomial-time algorithm for basis reduction in lattices due to Lenstra, Lenstra and Lov\'asz \cite{lenstra}. As has been emphasized in \cite{lovasz}, such a polynomial-time algorithm should only be taken as a proof of existence of an efficient algorithm for the problem under consideration. It may be conjectured that for the problems under consideration in this paper such simple, combinatorial algorithms exist. But for the design of such algorithms, saturation alone does not suffice. The stronger property (PH3), and more, is necessary. We shall address this issue in Section~\ref{ssissimpler}. \section{Littlewood-Richardson coefficients again} \label{slittleagain} Theorem~\ref{tstrongindex} applied to the BZ-polytope \cite{berenstein} specializes to the following in the setting of the Littlewood-Richardson problem (Problem~\ref{pintrolittle}): \begin{theorem} \label{tsatlit} \cite{GCT5} Assuming SH (Hypothesis~\ref{shlittle}), nonvanishing of $c_{\alpha,\beta}^\lambda$, given $\alpha,\beta,\lambda$, can be decided in strongly polynomial time (Section~\ref{sstandard}) for any semisimple classical Lie algebra ${\cal G}$. \end{theorem} It is assumed here that $\alpha,\beta,\lambda$ are specified by their coordinates in the basis of fundamental weights. For type $A$, this reduces to the result in \cite{GCT3}, which holds unconditionly. The saturation conjecture for type $A$ arose \cite{zelevinsky} in the context of Horn's conjecture and the related result of Klyachko \cite{kly}. We now turn to implications of Theorem~\ref{tsatlit} in this context. Given a complex, semisimple, simply connected, classical group $G$, let $LR(G)$ be the Littlewood-Richardson semigroup as in Section~\ref{slittlecone}. The following is a natural generalization of the problem raised by Zelevinsky \cite{zelevinsky} to this general setting: \begin{problem} Give an efficient description of $LR(G)$. \end{problem} Zelevinsky asks for a mathematically explicit description. This is a computer scientist's variant of his problem. Let $LR_\R(G)$ be the polyhedral convex cone generated by $LR(G)$. For $G=GL_n(\C)$, by saturation theorem, a triple $(\alpha,\beta,\lambda)$ of dominant weights belongs to $LR(G)$ iff it belongs to $LR_\R(G)$. Assuming SH (Hypothesis~\ref{shlittle}), Theorem~\ref{tsatlit} provides the following efficient description for $LR(G)$ in general. Recall that the period of the Littlewood-Richardson stretching polynomial $\tilde c_{\alpha,\beta}^\lambda(n)$ divides a fixed constant $d(G)$, which only depends on the types of simple factors of $G$ \cite{loera,GCT5}. Let $\alpha_i$'s denote the coordinates of $\alpha$ in the basis of fundamental weights. \begin{cor} \label{csatlit} \noindent (a) Whether a given $(\alpha,\beta,\lambda)$ belongs to $LR(G)$ can be determined in strongly polynomial time. \noindent (b) There exists a decomposition of $LR_\R(G)$ into a set of polyhedral cones, which form a cell complex ${\cal C}(G)$, and, for each chamber $C$ in this complex, a set $M(C)$ of $O(\rank(G)^2)$ modular equations, each of the form \[ \sum_i a_i \alpha_i + \sum_i b_i \beta_i + \sum_i c_i \lambda_i = 0 \quad (\mbox{mod}\ d),\] for some $d$ dividing $d(G)$, such that \begin{enumerate} \item SH (Hypothesis~\ref{shlittle}) is equivalent to saying that: $(\alpha,\beta,\lambda) \in LR(G)$ iff $(\alpha,\beta,\lambda) \in LR_\R(G)$ and $(\alpha,\beta,\lambda)$ satisfies the modular equations in the set $M(C_{\alpha,\beta,\lambda})$ associated with the cone $C_{\alpha,\beta,\lambda}$ containing $\alpha,\beta,\lambda$. \item Given $(\alpha,\beta,\lambda)$, whether $(\alpha,\beta,\lambda) \in LR_\R(G)$ can be determined in strongly polynomial time (cf. Section~\ref{shlittle}). \item If so, the cone $C_{\alpha,\beta,\lambda}$ and the associated set $M(C_{\alpha,\beta}^\lambda)$ of modular equations can also be determined in strongly polynomial time. After this, whether $(\alpha,\beta,\lambda)$ satisfies the equations in $M(C_{\alpha,\beta}^\lambda)$ can be trivially determined in strongly polynomial time. \end{enumerate} \end{cor} \proof (a) is a consequence of Theorem~\ref{tsatlit}. (b) follows from a careful analysis of the algorithm therein; see the proof of a more general result (Theorem~\ref{tconesatform}) later. \qed We call the labelled cell complex ${\cal C}(G)$, in which each cell $C \in {\cal C}(G)$ is labelled with the set of modular equations $M(C)$, the {\em modular complex}, associated with $LR_\R(G)$. When $G=SL_n(\C)$, the modular complex is trivial: it just consists of the whole cone $LR_\R(G)$ with only one obvious modular equation attached to it. But, for general $G$, the modular complex and the map $C\rightarrow M(C)$ are nontrivial. We do not know their explicit description. Corollary~\ref{csatlit} says that, given $x=(\alpha,\beta,\lambda)$, whether $x \in LR_\R(G)$, and whether the relevant modular equations are satisfied can be quickely verified on a computer, though the modular equations cannot be easily determined and verified by hand, as in type $A$. This is the main difference between type $A$ and general types. This naturally leads to: \begin{question} Is there a mathematically explicit description of the modular complex ${\cal C}(G)$ for a general $G$? \end{question} \ignore{Such a description seems necessary to extend the combinatorial proof \cite{knutson} of the saturation theorem to general $G$. This may be unwieldy, and in view of Corollary~\ref{csatlit}, not even necessary (for computer scientists). So, is there a way to prove the saturation property for arbitrary $G$ that does need an explicit description? One possible approach is via a study of the canonical basis of the canonical model associated with a Littlewood-Richardson coefiicient, as suggested in Section~\ref{sapproach}; see Sections~\ref{squasiproof} and \ref{scanonicalmodel} for more. } \section{Saturated and positive $\#P$} \label{ssharpp} Motivated by Theorem~\ref{tindexquasi},, we define certain subclasses of convex $\#P$ (Section~\ref{sconvexsharpp}), called saturated and positive $\#P$, which will play an important role in this paper. Let $f(x)=f(x_1,\ldots,x_k)$ be a function in convex $\#P$ (Section~\ref{sconvexsharpp}). Let \begin{equation} \label{eqsatsharpdef} f(x)=\phi(P_x), \end{equation} be its convex $\#P$-formula; cf. eq.(\ref{eqconvex0}). We say that this formula is saturated if its Ehrhart polynomial $f_{P_x}(n)$ is guaranteed to be saturated (Definition~\ref{dintrosat}), whenever $P_x$ is nonempty. Similarly, we say that the formula is positive, if $f_{P_x}(n)$ is guaranteed to be positive (Definition~\ref{dintropos1}), whenever $P_x$ is nonempty. If a $\#P$-formula is positive, it is also saturated. If $f_{P_x}(n)$ is saturated then the Ehrhart series $F_{P_x}(t)$ has a reduced positive form (Proposition~\ref{psatequivdefn}). We call a saturated formula modular if $F_{P_x}(t)$ has a reduced positive form with modular index $\poly(\rank(x))$. Here $\rank(x)$ denotes the rank of $x$, which we assume is given to us. In the problems of interest, we will define it explicitly. Typically, it will just be $k$, the number of parameters in $x$. In the definition of a modular formula, we can also stipulate that the dimension of the ambient space containing $P_x$ be $\poly(k)$, though we shall not do so. Strongly saturated (positive, modular) convex $\#P$-formulae are defined similarly. Let saturated $\#P$ be the subclass of convex $\#P$ consting of functions with saturated convex $\#P$-formulae. The subclasses positive and modular $\#P$ are defined similarly. So also the strong versions of these classes. These complexity classes can be enlarged in a natural way by taking into account the extensions in Section~\ref{ssextension}, as we shall assume henceforth. The inclusions among these complexity classes are shown in Figure~\ref{finclclass}. \begin{figure}[!h] \[\begin{array} {lcl} PSPACE\\ \\ \cup \\ \#P \\ \\ \cup \\ \mbox{convex} \ \#P \\\\ \cup \\ \mbox{saturated}\ \#P &\supset & \mbox{modular} \ \#P \\ \\ \cup & & \cup \\ \mbox{positive}\ \#P &\supset & \mbox{modular, positive} \ \#P \end{array} \] \caption{Hierarachy among the complexity classes.} \label{finclclass} \end{figure} \noindent {\bf Example}: We have already seen that the Littlewood-Richardson function $c(\alpha,\beta,\lambda)=c_{\alpha,\beta,\lambda}$ belongs to convex $\#P$ (Section~\ref{sconvexlittle}). It belongs to saturated $\#P$, by the saturation theorem of Knutson and Tao in type $A$, and by SH (Hypothesis~\ref{shlittle}) in general. It belongs to modular, positive $\#P$, in general, by PH2 and PH3 (Hypotheses~\ref{hph2little}, and \ref{hintrolittleph3gen}). Theorems~\ref{tindexquasi} and \ref{tstrongindex} imply the following: \begin{theorem} \label{tdecision} \noindent (a) Decision problem associated with any function $f$ in saturated, and hence, positive $\#P$ belongs to $P$. In other words, given $x$, nonvanishing of $f(x)$ can be decided in $\poly(\bitlength{x})$ time. \noindent (b) Decision problem associated with any function $f$ in strongly saturated, and hence, strongly positive $\#P$ belongs to strong $P$. In other words, given $x$, nonvanishing of $f(x)=f(x_1,\ldots,x_k)$ can be decided in $\poly(\bitlength{x})$ time using $\poly(k)$ arithmetic steps. \end{theorem} Significance of the complexity classes modular and positive $\#P$ will be discussed in Section~\ref{sfurther}. \section{The saturation and positivity hypotheses} \label{sphypo} Now let $f(x)$, $x\in \N^k$, be a counting function associated with a structural constant in representation theory or algebraic geometry. Here $x$ denotes the sequence of parameters associated with the constant. Let $\bitlength{x}$ denote the bitlength of $x$. Let $\rank(x)$ denote its rank--typically this will be just $k$, the number of parameters in $x$. For example, in the Littlewood-Richardson problem, $x$ is the triple $(\alpha,\beta,\lambda)$, $f(x)=f(\alpha,\beta,\lambda)=c_{\alpha,\beta}^\lambda$, $\bitlength{x}$ is the total bitlength of the coordinates of $\alpha,\beta,\lambda$ and $\rank(x)$ is the total number of coordinates of $\alpha,\beta$ and $\lambda$. Assume that $f(x)$ is nonnegative for all $x\in \N^k$, and that $f \in PSPACE$; i.e., $f(x)$ can be computed in $\poly(\bitlength{x})$ space. Then we can ask: where does $f$ lie in the complexity hierarchy shown in Figure~\ref{finclclass}? In particular, let $f=f(x)$ be a nonnegative function associated with a structural constant in any of the decision problems in Section~\ref{sdecision}. Exact specifications of $x$ and $f(x)$ for these decision problems, and the definition of the bitlength $\bitlength{x}$ and $\rank(x)$ are given in Sections~\ref{sssubgroup}-\ref{sspgit}. It is shown in Chapter~\ref{cpspace} that $f \in PSPACE$ for Problem~\ref{pintroplethysm} and the special cases of Problem~\ref{pintrosubgroup} that arise in the flip. This may be conjectured to be so for the $f$'s in Problem~\ref{pintrogit}, with $X$ therein a class variety; cf \cite{GCT10} for its justification. \begin{hypo} {\bf (The main positivity hypothesis)} \label{phmain} Let $f=f(x)$ be the function associated with a structural constant in \begin{enumerate} \item Problem~\ref{pintrokronecker}, or \ref{pintroplethysm}, or \item Problem~\ref{pintrosubgroup}, with $H$ and $G$ therein being classical as defined below, or \item Problem~\ref{pintrogit}, with $X$ being a class variety therein. \end{enumerate} Then: \noindent (a) $f$ belongs to saturated $\#P$. \noindent (b) More strongly, it belongs to modular, positive $\#P$. \end{hypo} We say that a reductive group $G$ is {\em classical}, if $G_0$, its connected component containing the identity, is classical as defined in Section~\ref{sintroLR}, and each simple composition factor of its discrete component $G/G_0$ is a cyclic or an alternating group. All groups that arise in the context of the flip in characteristic zero are classical. For the positivity hypotheses for nonclassical groups, see Section~\ref{snonclassical}. \begin{theorem} \label{tmainphyp} Hypothesis~\ref{phmain} (a) implies Hypothesis~\ref{PHflip} (PHflip). That is, assuming Hypothesis~\ref{phmain} (a), nonvanishing of $f(x)$ as therein, for a given $x$, can be decided in $\poly(\bitlength{x})$ time. \end{theorem} This follows from Theorem~\ref{tdecision}. For complexity-theoretic significance of Hypothesis~\ref{phmain} (b), see Section~\ref{sfurther}. Next we want to break the positivity Hypothesis~\ref{phmain} into PH1, SH, PH2 and PH3, as we did for the plethysm constant in Section~\ref{sintroplethysm}. For this, we need to solve the following: \begin{problem} Associate a stretching function $\tilde f(x,n)$ with $f(x)$ such that (a) $\tilde f(x,1)=f(x)$, (b) for every $x$, $\tilde f(x,n)$, as a function of $n$, is a quasi-polynomial. \end{problem} This is done in Chapter~\ref{cquasipoly} for the $f$'s in Problems~\ref{pintrokronecker}-\ref{pintrogit}. Using the stretching quasi-polynomial $\tilde f(x,n)$, Hypothesis~\ref{phmain} can be broken into the following four hypotheses. Let $f(x)$ be as therein. \begin{hypo} \label{phph1} {\bf (PH1)} The function $f(x)$ belongs to convex $\#P$. Furthermore, it has a convex $\#P$-formula (cf. (\ref{eqconvex0})) \[ f(x)=\phi(P_x),\] that is compatible with the stretching function $\tilde f(x,n)$ in the sense that, for every fixed $x$, the Ehrhart quasi-polynomial $f_{P_x}(n)$ of $P_x$ coincides with $\tilde f(x,n)$. \end{hypo} \begin{hypo} \label{phsh} {\bf (SH)} For every $x$, the stretching function $\tilde f(x,n)$ is saturated (Definition~\ref{dintrosat}). \end{hypo} More strongly, \begin{hypo} \label{phph2} {\bf (PH2)} For every $x$, the stretching function $\tilde f(x,n)$ is positive (Definition~\ref{dintropos1}). \end{hypo} \begin{hypo} \label{phph3} {\bf (PH3)} For every $x$, the generating function $F_x(t)=\sum_n \tilde f(x,n) t^n$ has a reduced positive form of modular index $\poly(\rank(x))$. (Definition~\ref{dintroreducedpos}). \end{hypo} In the following sections, we specify the details for the decision problems under consideration. In particular, for each of these decision problems, we have to define the input $x$, its specification, the bitlength $\bitlength{x}$, the rank of $x$, and the stretching function $\tilde f(x,n)$. \subsection{The subgroup restriction problem} \label{sssubgroup} In this section we consider the subgroup restriction problem (Problem~\ref{pintrosubgroup}). The Kronecker and the plethysm problems (Problems~\ref{pintrokronecker}, \ref{pintroplethysm}) are its special cases. Let $G,H,\rho,\lambda,\pi,m_\lambda^\pi$ be as in Problem~\ref{pintrosubgroup}, where $G$ and $H$ can be nonclassical. We shall define below an explicit polynomial homomorphism $\rho:H \rightarrow G$, as needed in the statement of Problem~\ref{pintrosubgroup}, and also the precise specifications $[H],[\rho],[\lambda],[\pi]$ of $H,\rho,\lambda,\pi$, respectively. We shall also define the bitlengths $[H],\bitlength{\rho},\bitlength{\lambda},\bitlength{\pi}$ and the ranks. The input $x$ in the subgroup restriction problem is the tuple $([H],[\rho],[\lambda],[\pi])$. Its bitlength $\bitlength{x}$ is defined to be the sum of the bitlengths $\bitlength{H}, \bitlength{\rho},\bitlength{\lambda},\bitlength{\pi}$, and $\rank(x)$ is defined to be the sum of the ranks of $H,\rho,\lambda$ and $\pi$. With this terminology, we let $f(x)=m_\lambda^\pi$ and $x$ as defined here in Hypotheses~\ref{phmain} and \ref{phph1}-\ref{phph3} and Theorem~\ref{tmainphyp} to get their precise statements for the subgroup restriction problem. Here $H$ and $\rho$ are implicit in the definition of $m_\lambda^\pi$. For example, in the plethym problem (Problem~\ref{pintroplethysm}, these specifications are as follows. The specification $[H]$ is just the root system for $H=GL_n(\C)$. Its bitlength $\bitlength{H}$ is $n$, and the rank is also $n$. The specification $[\rho]$ of the representation map $\rho: H \rightarrow G=GL(V_\mu(H))$ consists of just the partition $\mu$ specified in terms of its nonzero parts. Its bitlength $\bitlength{\rho}=\bitlength{\mu}$ and $\rank(\rho)$ is the number of parts of $\mu$. The partitions $\lambda$ and $\mu$ are specified in terms of their nonzero parts. Their bitlength is the total bitlength of the parts, and the rank is the total number of parts. It is crucial here that only nonzero parts of $\lambda$ are specified, because the rank of $G$ can be exponential in the rank of $H$ and the bitlength of $\mu$. Hence, the bitlength of this compact representation of $\lambda$ can be polynomial in the rank of $H$ and the bitlength of $\mu$, even if the dimension of $G$ is exponential. The plethysm problem is the main prototype of the subgroup restriction problem. If the reader wishes, he can skip the rest of this section in the first reading. In general, we assume that $H$ in Problem~\ref{pintrosubgroup} is a finite simple group, or a complex simple, simply connected Lie group, or an algebraic torus $(\C^*)^k$, or a direct product of such groups. The results and hypotheses in this paper are also applicable if we allow simple types of semidirect products, such as wreath products, which is all that we need for the sake of the flip. But these extensions are routine, and hence, for the sake of simplicity, we shall confine ourselves to direct products. \subsubsection*{Explicit polynomial homomorphism} Now let us define an {\em explicit polynomial homomorphism}. This will be done by defining basic explicit homomorphisms, and composing them functorially. \noindent{\em Basic explicit homomorphisms:} Let $V$ be an irreducible polynomial representation of $H$ (characteristic zero), or more generally, an explicit polynomial representation that is constructed functorially from the irreducible polynomial representations using the operations $\oplus$ and $\otimes$. Then the corresponding homomorphism $\rho:H\rightarrow G=GL(V)$ is an explicit polynomial homomorphism. The identity map $H\rightarrow H$ is also an explicit polynomial homomorphism. The polynomiality restriction here only applies to the torus component of $H$. If $H$ is a finite simple group, or a complex semisimple group, then any irreducible representation of $H$ is, by definition, polynomial. In general, a representation is polynomial if its restriction to the torus component is polynomial; i.e., a sum of polynomial (one dimensional) characters. To see why the polynomiality restriction is essential, let $H$ be a torus, $V$ its rational representation, and $G=GL(V)$. Let $V_\lambda(G)=\sym^d(V)$, the symmetric representation of $G$, and let $\pi$ be the label of the trivial character of $H$. Then the multiplicity $m_\lambda^\pi$ is the number of $H$-invariants in $\sym^d(V)$. This is easily seen to be the number of nonnegative solutions of a system of linear diophontine equations. But the problem of deciding whether a given system of linear diophontine equations has a nonnegative solution is, in general, $NP$-complete. Though the system that arises above is of a special form, it is not expected to be in $P$ if $V$ is allowed to be any rational representation; the associated decision problem may be $NP$-complete even in this special case. If $V$ is a polynomial representation of a torus $H$, then all coefficients of the system are nonnegative, and the decision problem is trivially in $P$. \noindent{\em Composition:} We can now compose the basic explicit (polynomial) homomorphisms above functorially: \begin{enumerate} \item If $\rho_i: H \rightarrow G_i$ are explicit, the product map $\rho:H \rightarrow \prod_i G_i$ is also explicit. \item If $\rho_i: H_i\rightarrow G_i$ are explicit, the product map $\rho: \prod H_i \rightarrow \prod G_i$ is also explicit. \end{enumerate} Instead of products, we can also allow simple semi-direct products such as wreath products here. We may also allow other functorial constructions such as induced representations and restrictions. For example, if $\rho:H\rightarrow G$ is an explicit polynomial homomorphism, and $G'\subseteq G$ is an explicit subgroup of $G$ such that $\rho(H)\subseteq G'$, then the restricted homomorphism $\rho':H \rightarrow G'$ can also be considered to be an explicit polynomial homomorphism. But for the sake of simplicity, we shall confine ourselves to the simple functorial constructions above. \subsubsection{Input specification, bitlengths and ranks} Now we describe the specifications $[H],[\rho],[\lambda],[\mu]$, their bitlengths, and ranks. These are very similar to the ones in the plethysm problem. \noindent {\bf The specification $[H]$:} We assume that $H$ is specified as follows. \noindent (1) If $H$ is a complex, simple, simply connected Lie group, then the specification $[H]$ consists of the root system of $H$ or the Dynkin diagram. Let $\bitlength{H}$ be the bitlength of this specification. Thus, if $H=SL_n(\C)$, then $\bitlength{H}=O(n)$. We define $\rank(H)$, the rank of $H$, to be $n$. \noindent (2) If $H$ is a simple group of Lie type (Chevalley group) then it has a similar specification \cite{carter}. The only finite groups of Lie type that arise in GCT are $SL_n(F_{p^k})$ and $GL_n(F_{p^k})$. In this case the specification $[H]$ is easy: we only have to specify $n,p,k$. We define $\bitlength{H}$ in this case to be $n+k+\log_2 p$; not $\log_2 n + \log_2 k + \log_2 n$. As a rule, $\bitlength{H}$ is defined to be the sum of the rank parameters (such as $n$ and $k$ here) and bit lengths of the weight parameters (such as $p$ here) in the specification. This is equivalen to assuming that the rank parameters are specified in unary. We define $\rank(H)$ to be $n+k+1$. \noindent (3) If $H$ is the alternating group $A_n$, we only specify $n$. Let $\bitlength{H}=n$, and $\rank(H)=n$. \noindent (4) The torus is specified by its dimension. We define $\rank(H)$ and $\bitlength{H}$ to be the dimension. \noindent (5) If $H$ is a product of such groups, its specification is composed from the specifications of its factors, and the bitlength $\bitlength{H}$ is defined to be the sum of the bitlengths of the constituent specifcations, and $\rank(H)$ the sum of the ranks of the constituents. \noindent {\bf The specification $[\rho]$:} Let us first assume that $\rho$ is a basic explicit polynomial homomorphism. In this case the specification of $\rho: H\rightarrow G=GL(V)$ is a pair $[\rho]=([H],[V])$ consisting of the specification $[H]$ of $H$ as above, and the combinatorial specification $[V]$ of the representation $V$ as defined below: \noindent (1) If $H$ is a semisimple, simply connected Lie group, and $V=V_\mu(H)$ its irrreducible representation for a dominant weight $\mu$ of $H$, then $V$ is specified by simply giving the coordinates of $\mu$ in terms of the fundamental weights of $H$. Thus $[V]=\mu$, and its bitlength $\bitlength{V}$ is the total bitlength of all coordinates of $\mu$, and $\rank([V])$ is the total number of coordinates of $\mu$. \noindent (2) If $H=S_n$, and $V=S_\gamma$ its irreducible representation (Specht module), then $[V]$ is the partition $\gamma$ labelling this Specht module. We define $\bitlength{V}$ to be the bitlength of this partition, and $\rank([V])$ to be the height of the partition. \noindent (3) If $H$ is a finite general linear group $GL_n(F_{p^k})$, and $V$ its irreducible representation, as classified by Green \cite{macdonald}, then $[V]$ is the combinatorial classifying label of $V$ as given in \cite{macdonald}. It is a certain partition-valued function, which can be specified by listing the places where the function is nonzero and the nonzero partition values at these places. Let $\bitlength{V}$ be the bitlength of this specification; it is $O(\poly(n,k,\bitlength{p}))$. We let $\rank([V])=n+k$. More generally, if $H$ is a finite group of Lie type, and $V$ its irreducible representation, then $[V]$ is the combinatorial classifying label of $V$ as given by Lusztig \cite{lusztig}. \noindent (4) If $H$ is a torus and $V$ is a polynomial character, then $[V]$ is the specification of the character. Its bitlength is the bitlength of the specification, and rank is the dimension of $H$. \noindent (5) If $V$ is composed from irreducible representations, then $[V]$ is composed from the specifications of the irreducible representations in an obvious way. Bitlengths and ranks are defined additively. The bitlength $\bitlength{\rho}$ is defined to be $\bitlength{H}+\bitlength{V}$, where $\bitlength{V}$ is the bitlength of $[V]$. Similarly $\rank(\rho)=\rank(H)+\rank([V])$, where $\rank([V])$ is the rank of the specification $[V]$ of $V$ as above; not $\dim(V)$. If $\rho$ is a composite homomorphism, its specification $[\rho]$ is composed from the specifications of its basic constituents in an obvious way. The bitlength $\bitlength{\rho}$ is defined to be the sum of the bitlengths of these basic specifications. The rank is defined similarly. \noindent {\bf The specifications $[\lambda]$ and $[\pi]$:} $V_\pi(H)$ is the tensor product of the irreducible representations of the factors of $H$. We let $[\pi]$ be the tuple of the combinatorial classifying labels of each of these irreducible representations, as specified above. Let $\bitlength{\pi}$ be their total bit length, and $\rank(\pi)$ the total rank. Similarly, $V_\lambda(G)$ is the tensor product of the irreducible representations of the factors of $G$. When $G=GL_m(\C)$, $\lambda$ is a partition, which we specify by only giving its nonzero parts, whose number is equal to the height of $\lambda$. This is crucial since the height of $\lambda$ can be much less than than the rank $m$ of $G$, as in the plethysm problem (Problem~\ref{pintroplethysm}). We shall leave a similar compact specification $[\lambda]$ for a general connected, reductive $G$ to the reader. Let $\bitlength{\lambda}$ be its bitlength and $\rank(\lambda)$ its rank. \subsubsection{Stretching function and quasipolynomiality} Let $f(x)=m_\lambda^\pi$ as above, with $x=([H],[\rho],[\lambda],[\pi])$. Here $\lambda$ is the dominant weight of $G$. First, assume that $H$ is connected, reductive. Then $\pi$ is the dominant weight of $H$. For a given $x$, let us define the stretching function as \begin{equation} \tilde f(x,n)=\tilde m_{\lambda}^\pi(n)=m_{n \lambda}^{n \pi}, \end{equation} which is the multiplicity of $V_{n \pi}(H)$ in $V_{n \lambda}(G)$, considered as an $H$-module via $\rho: H \rightarrow G$. Let $M_\lambda^\pi(t)=\sum_{n \ge 0} \tilde m_{\lambda}^\pi(n) t^n$ be the generating function of this stretching quasi-polynomial. The following is the generalization of Theorem~\ref{tquasiplethysm} in this setting. \begin{theorem} \label{tquasisubgroup} \noindent (a) (Rationality) The generating function $M_{\lambda}^\pi(t)$ is rational. \noindent (b) (Quasi-polynomiality) The stretching function $\tilde m_{\lambda}^\pi(n)$ is a quasi-polynomial function of $n$. \noindent (c) There exist graded, normal $\C$-algebras $S=S(m_{\lambda}^\pi)=\oplus_n S_n$ and $T=T(m_{\lambda}^\pi)=\oplus_n T_n$ such that: \begin{enumerate} \item The schemes $\spec(S)$ and $\spec(T)$ are normal and have rational singularities. \item $T=S^H$, the subring of $H$-invariants in $S$. \item The quasi-polynomial $\tilde m_{\lambda}^\pi(n)$ is the Hilbert function of $T$. \end{enumerate} \noindent (d) (Positivity) The rational function $M_{\lambda}^\pi(t)$ can be expressed in a positive form: \begin{equation} M_{\lambda}^\pi(t)=\f{h_0+h_1 t+ \cdots+h_d t^d}{\prod_j(1-t^{a(j)})^{d(j)}}, \end{equation} where $a(j)$'s and $d(j)$'s are positive integers, $\sum_j d(j)=d+1$, where $d$ is the degree of the quasi-polynomial, $h_0=1$, and $h_i$'s are nonnegative integers. \end{theorem} The specific rings $S(m_\lambda^\pi)$ and $T(m_\lambda^\pi)$ constructed in the proof of this result are called the {\em canonical rings} associated with the structrural constant $m_{\lambda}^\pi$. The projective schemes $Y(m_{\lambda}^\pi)=\proj(S(m_{\lambda}^\pi))$, and $Z(m_{\lambda}^\pi)=\proj(T(m_{\lambda}^\pi))$ are called the canonical models associated with $m_{\lambda}^\pi$. The minimal positive form of $M_\lambda^\pi(t)$ is defined very much as in Section~\ref{sintroplethysm}, and an analogue of Conjecture~\ref{cminimalplethysm} can be made, which would imply PH3 (Hypothesis~\ref{phph3}) for the structural constant $m_\lambda^\pi$. Theorem~\ref{tquasisubgroup} and its generalization, when $H$ can be disconnected, is proved in Chapter~\ref{cquasipoly}; cf. Theorem~\ref{tquasimain1}. \subsubsection{Finitely generated semigroup} The following is an analogue of Theorem~\ref{tconeplethysm}. \begin{theorem} \label{tfinitegensubgroup} Assume that $H$ is connected. For a fixed $\rho:H \rightarrow G$, let $T(H,G)$ be the set of pairs $(\mu,\lambda)$ of dominant weights of $H$ and $G$ such that the irreducible representation $V_\pi(H)$ of $H$ occurs in the irreducible representation $V_\lambda(G)$ of $G$ with nonzero multiplicity. Then $T(H,G)$ is a finitely generated semigroup with respect to addition. \end{theorem} This is proved in Section~\ref{sconesub}. \subsubsection{PSPACE} The following is a generalization of Theorem~\ref{tpspaceplethysm}. \begin{theorem} \label{tpspacesubgroup} Assume that $H$ in Problem~\ref{pintrosubgroup} is a direct product, whose each factor is a complex simple, simply connected Lie group, or an alternating (or symmetric) group, or $SL_n(F_{p^k})$ (or $GL_n(F_{p^k})$), or a torus. Then $f(x)=m_\lambda^\pi$ can be computed in $\poly(\bitlength{x})$ space, with $x$ as specified above. \end{theorem} This is proved in Chapter~\ref{cpspace}. It may be conjectured that Theorem~\ref{tpspacesubgroup} holds even when the composition factors of $H$ are allowed to be general finite simple groups of Lie type. This will be so if Lusztig's algorithm \cite{lusztigchar} for computing the characters of finite simple groups of Lie type can be parallelized; cf. Section~\ref{sfinitesimple}. \subsubsection{Positivity hypotheses for classical groups} \label{sclassical} Theorem~\ref{tquasisubgroup}-\ref{tpspacesubgroup}, along with the experimental results in special cases (cf. Chapter~\ref{cevidence}), constitute the main evidence in support of the positivity Hypotheses~\ref{phmain}-\ref{phph2} for the subgroup restrition problem, with $H$ and $G$ therein being classical. \subsubsection{Positivity hypotheses for nonclassical groups} \label{snonclassical} Theorem~\ref{tquasisubgroup} holds even when $H$ or $G$ are nonclassical. To state the positivity hypotheses when $H$ or $G$ in the subgroup restriction problem is nonclassical, we need to extend the notion of a saturated or positive quasi-polynomial. Let $f_P(n)$ be the Ehrhart quasi-polynomial of a polytope $P$. Let $f_{i,P}(n)$, $1\le i \le l(P)$ be the polynomials such that $f_P(n)=f_{i,P}(n)$ if $n=i$ modulo $l(P)$. We say that $f_P(n)$ is {\em positive up to multiplicative factors} if every $f_{i,P}(n)$ can be written in the form \[ f_{i,P}(n)=g_{i,P}(n) f_{i,P}'(n),\] such that the factor $g_{i,P}(n)$ is computable in $\poly(\bitlength{P})$ time, and $f_{i,P}'(n)$ is positive. We say that $f_P(n)$ is {\em saturated up to multiplicative factors} if $\ind(f_P)=1$ implies that $f_{1,P}'(1)\not = 0$. To see when multiplicative factors may be needed, let us consider the case when $P$ is the BZ-polytope associated with the exceptional Lie algebra ${\cal G}$ of type $G_2$. That is, $\phi(P)$ is the Littlewood-Richardson coefficient of type of $G_2$. Then the positivity Hypothesis ~\ref{hph2little} and the saturation Hypothesis~\ref{shlittle} may not hold for type $G_2$ as they are stated. But it is known \cite{millson} that the Littlewood-Richardson coefficient $c_{\alpha,\beta}^\lambda$ of type $G_2$ has the following property: if $c_{n \alpha, n \beta}^{n \lambda} \neq 0$ for some natural number $n$, then for every natural number $n \geq 2$, $c_{n \alpha, n \beta}^{n \lambda} \neq 0$\footnote{This was pointed out to us by a referee for \cite{GCT5}}. This suggests that $\tilde c_{\alpha,\beta}^\lambda(n)$ in this case is positive up to a multiplicative factor of $(n-1)$. We shall say that the integer programming problem in Section~\ref{ssaturated} is saturated or positive up to multiplicative factors, if $f_P(n)$ is saturated or positive up to multiplicative factors, respectively. It is clear that Theorem~\ref{tindexquasi} (b) holds even for integer programming problems that are saturated or positive up to multiplicative factors. With this terminology, it may be conjectured that Hypothesis~\ref{phph1} holds for the subgroup restriction problem (Problem~\ref{pintrosubgroup}) even when $H$ and $G$ therein are nonclassical, and Hypotheses~\ref{phsh} and \ref{phph2} hold, if the pharases saturated and positive in their statements are meant to be only up to multiplicative factors, wherein we assume that $\tilde f(x,n)=f_{P_x}(n)$, as in Hypothesis~\ref{phph1}. \subsection{The decision problem in geometric invariant theory} \label{sspgit} Finally, let us turn to the most general Problem~\ref{pintrogit}. \subsubsection{Reduction from Problem~\ref{pintrosubgroup} to Problem~\ref{pintrogit}} \label{sreduction} First, let us note that the subgroup restriction problem (Problem~\ref{pintrosubgroup}) is a special case of Problem~\ref{pintrogit}. To see this, let $H,\rho$ and $G$ be as in Problem~\ref{pintrosubgroup}, and let $X$ be the closed $G$-orbit of the point $v_\lambda$ corresponding to the highest weight vector of $V_\lambda(G)$ in the projective space $P(V_\lambda(G))$. Then \begin{equation} \label{eqXsubgroup} X=G v_\lambda \cong G/P_\lambda, \end{equation} where the $P=P_\lambda=G_{v_\lambda}$ is the parabolic stabilizer of $v_\lambda$. We have a natural action of $H$ on $X$ via $\rho$. Let $R$ be the homogeneous coordinate ring of $X$. By \cite{hashimoto,mehta,ramanathan,smith}, the singularities of $\mbox{spec}(R)$ are rational. By Borel-Weil \cite{fultonrepr}, the degree one component $R_1$ of the homogeneous coordinate ring $R$ of $X$ is $V_\lambda(G)$. Hence, $s_1^\pi$ in this special case of Problem~\ref{pintrogit} is precisely $m^\pi_\lambda$ in Problem~\ref{pintrosubgroup}. The results in Section~\ref{sssubgroup} for $s_1^\pi$ generalize in a natural way for $s_d^\pi$. \subsubsection{Input specification} The variety $X$ in the above example is completely specified by $H,\rho$ and $\lambda$. Hence its specification $[X]$ can be given in the form a tuple $([H],[\rho],[\lambda])$, where where $[H],[\rho]$ and $[\lambda]$ are the specifications of $H$, $\rho$ and $\lambda$ as in Section~\ref{sssubgroup}, The input specification $x$ for Problem~\ref{pintrogit} in the special case above is the tuple $([X], d,[\pi])=([H],[\rho], [\lambda],d,[\pi])$, where $[\pi]$ is the specification of $\pi$ as in Section~\ref{sssubgroup}. We now describe a class of varieties $X$ which have similar compact specifications. Let $G$ be a connected, reductive group, $H$ a reductive, possibly disconnected, reductive group, and $\rho: H \rightarrow G$ an explicit polynomial homomorphism as in Section~\ref{sssubgroup}. Let $V=V_\lambda(G)$ be an irreducible representation of $G$ for a dominant weight $\lambda$. Let $P(V)$ be the projective space associated with $V$. It has a natural action of $H$ via $\rho$. Let $v \in P(V)$ be a point that is characterized by its stabilizer $G_v \subseteq G$. This means it is the only point in $P(V)$ that is stabilized by $G_v$. For example, the point $v_\lambda$ above is characterized by its parabolic stabilier. We assume that we know the Levi decompositioon of $G_v$ explicity, and its compact specification $[G_v]$, like that of $H$, and also an explicit compact specification of the embedding $\rho':G_v \rightarrow G$, aking to that of the explicit homomorphism $\rho:H \rightarrow G$. Let $X\subseteq P(V)$ be the projective closure of the $G$-orbit of $v$ in $P(V)$. Then $X$ as well as the action of $H$ on $X$ are completely specified by $\lambda,H,\rho,G_v$ and $\rho'$. Hence, we can let $[X]$ be the tuple $(\lambda,[H],[\rho],[G_v],[\rho'])$. The input specification $x$ for Problem~\ref{pintrogit} with the $X$ of this form is the tuple $([X], d,[\pi])$. The bitlength $\bitlength{x}$ and $\rank(x)$ are defined additively. Since the point $v_\lambda$ above is characterized by its stabilizer, $G/P$ is a variety of this form. The class varieties \cite{GCT1,GCT2} are either of this form, or a slight extension of this form, and admit such compact specifications. The algebraic geometry of an $X$ of the above form is completely determined by the representation theories of the two homomorphisms $\rho:H \rightarrow G$ and $\rho':G_v\rightarrow G$. Furthermore, the results in \cite{GCT2} say that Problem~\ref{pintrogit} for a class variety is intimately linked with the subgroup restriction problem and its variants for the homomomorphisms $\rho$ and $\rho'$. Hence it is qualitatively similar to the subgroup restriction problem in this case; cf. \cite{GCT10} for further elaboration of the connection between these two problems. \subsubsection{Stretching function and quasi-polynomiality} Now let $H,X,R$ and $s_d^\pi$ be as in Problem~\ref{pintrogit}, with $H$ therein assumed to be connected. We associate with $f(x)=s_d^\pi$ the following stretching fucntion: \begin{equation} \tilde f(x,n)=\tilde s_d^\pi(n)= s_{n d}^{n \pi}, \end{equation} where $s_{n d}^{n \pi}$ is the multiplicity of the irrreducible representation $V_{n \pi}(H)$ of $H$ in $R_{n d}$, the componenent of the homogeneous coordinate ring $R$ of $X$ with degree $n d$. Let $S(t)=\sum_{n\ge 0} \tilde s_d^\pi(n) t^n$. \begin{theorem} \label{tquasigit} Assume that the singularities of $\spec(R)$ are rational. \noindent (a) (Rationality) The generating function $S_{d}^\pi(t)$ is rational. \noindent (b) (Quasi-polynomiality) The stretching function $\tilde s_{d}^\pi(n)$ is a quasi-polynomial function of $n$. \noindent (c) There exist graded, normal $\C$-algebras $S=S(s_{d}^\pi)=\oplus_n S_n$ and $T=T(s_{d}^\pi)=\oplus_n T_n$ such that: \begin{enumerate} \item The schemes $\spec(S)$ and $\spec(T)$ are normal and have rational singularities. \item $T=S^H$, the subring of $H$-invariants in $S$. \item The quasi-polynomial $\tilde s_{d}^\pi(n)$ is the Hilbert function of $T$. \end{enumerate} \noindent (d) (Positivity) The rational function $S_{d}^\pi(t)$ can be expressed in a positive form: \begin{equation} S_{d}^\pi(t)=\f{h_0+h_1 t+ \cdots+h_k t^k}{\prod_j(1-t^{a(j)})^{k(j)}}, \end{equation} where $a(j)$'s and $k(j)$'s are positive integers, $\sum_j k(j)=k+1$, where $k$ is the degree of the quasi-polynomial $\tilde s_d^\pi(n)$, $h_0=1$, and $h_i$'s are nonnegative integers. \end{theorem} This is proved in Chapter~\ref{cquasipoly}. Theorem~\ref{tquasisubgroup} is a special case of this theorem, in view of the reduction in Section~\ref{sreduction}. Theorem~\ref{tquasigit} is applicable when $X$ is a class variety, assuming that its singularities are rational. %; cf. \cite{GCT2} for the results which support this. \subsubsection{Positivity hypotheses} Even though Theorem~\ref{tquasigit} holds for any $X$, with $\spec(R)$ having rational singularities, the positivity hypotheses PH1,PH2,PH3 can be expected hold for only very special $X$'s. In general, characterizing the $X$'s with compact specification for which the positivity hypotheses would hold is a delicate problem. Hypotheses~\ref{phmain}-\ref{phph2} say that these hold when $X$ in Problem~\ref{pintrogit} is $G/P$ (as in Section~\ref{sreduction}) or a class variety, with the input specification $x$ as described above. For future reference, we shall reformulate these hypotheses in geometric terms. For this we need a definition. Let $T=\sum_n T_n$ be a graded complex $\C$-algebra so that the singularities of $\spec(T)$ rational. Let $Z=\proj(T)$. Assume that $Z$ has a compact specification $[Z]$; we shall specify it below for the $Z$'s of interest to us. We let $[T]$, the specification of $T$, to be $[Z]$. This will play the role of the input in the definition below. Let $\bitlength{T}$ denote its bitlength. Let $h_T(n)=\dim(T_n)$ be its Hilbert function, which is a quasipolynomial, since the singularities of $\spec(T)$ are rational; cf. Lemma~\ref{ldehy}. \begin{defn} \label{dphcanonicalz} \noindent (1) We say that PH1 holds for $T$ (or $Z$) if the Hilbert quasi-polynomial $h_T(n)$ is convex. This means there exists a polytope $P=P_T$ depending on the input $[T]$, whose Ehrhart quasipolynomial $f_P(n)$ coincides with the Hilbert function $h_T(n)$, and whose membership function $\chi_P(y)$ can be computed in $\poly(\bitlength{T},y)$ time. We assume that a separating hyperplane can also be computed in polynomial time if $y \not \in P$ (Section~\ref{sseporacle}). \noindent (2) We say that SH holds for $T$ (or $Z$) if the Hilbert quasipolynomial $h_T(T)$ is saturated (Definition~\ref{dintrosat}). \noindent (3) We say that PH2 holds for $T$ (or $Z$) if the Hilbert quasipolynomial $h_T(T)$ is positive (Definition~\ref{dintropos1}). \noindent (4) We say that PH3 holds for $T$ (or $Z$) if Hilbert series $H_T(t)=\sum_{n \ge 0} h_T(n) t^n$, which is a rational function since $h_T(n)$ is a quasipolynomial, has a reduced positive form with modular index $\poly(rank([T]))$ (Definition~\ref{dintroreducedpos}). Here $\rank([T])$ is the rank of the specification $[T]$ of $T$. \end{defn} \subsubsection{$G/P$ and Schubert varieties} \label{sschubertandgmodp} Let us illustrate this definition with an example. Let $X\cong G/P_\lambda$ be as in Section~\ref{sreduction} and $R$ its homogeneous coordinate ring. We have already seen that it has a compact specification: namely $[X]=\lambda$. Since singularities of $\spec(R)$ are rational, PH1,2,3 make sense. PH1 for $G/P$ is follows from the Borel-Weil theorem. PH3 follows because the Hilbert series of $R$ is of the form \[ \f {h_0 + \cdots + h_d t^d} {(1-t)^{d+1}},\] with $h_0=1$ and $h_i$'s nonnegative. This is so because $R$ is Cohen-Macauley \cite{ramanathan} and is generated by its degree one component. PH2 turns out to be nontrivial. Experimental evidence in its support for the classical $G/P$ is given in Section~\ref{sevigmodp}. Considerations for the Schubert subvarieties are similar. Experimental evidence for PH2 for the classical Schubert varieties is also given in Section~\ref{sevigmodp}. Now let $s=s_d^\pi$ be the multiplicity as Problem~\ref{pintrogit}, with $X$ having a compact specification $[X]$ as above. Let $T=T(s)$ be the ring associated with $s$ as in Theorem~\ref{tquasigit} (c). Let $Z=Z(s)=\proj(T)$. We let the specification $[Z]=([X],d,\pi)$. Let $\bitlength{Z}$ be its bitlength. So Theorem~\ref{tindexquasi} in this context implies: \begin{theorem} If PH1 and SH hold for $Z(s)$ then nonvanishing of $s$ can be decided in $\poly(\bitlength{Z})$ time. \end{theorem} We also have the following reformulation: \begin{prop} Hypotheses~\ref{phph1}-\ref{phph3} are equivalent to PH1, SH, PH2, and PH3 for $Z(s)$, where $s$ is a stucture constant that corresponds the structure constant $f(x)$ in Hypotheses~\ref{phph1}-\ref{phph3}. Thus, in the case of the subgroup restriction problem, $s=s_1^\pi=m^\pi_\lambda$ as in Section~\ref{sreduction}. \end{prop} This is just a consequence of definitions. \section{Further significance of PH2 and PH3} \label{sfurther} The saturated integer programming algorithm in Section~\ref{ssaturated} needs only PH1 and SH; cf. Theorem~\ref{tmainphyp}. We briefly describe here the problems wherein the full strength of PH2 and PH3 seems necessary. \subsection{PH3 and existence of a simpler algorithm} \label{ssissimpler} As we remarked in Section~\ref{sistheresimpler}, the use of the ellipsoid method and basis reduction in lattices makes the the algorithm for saturated integer programming (cf. Theorem~\ref{tindexquasi}) fairly intricate. The flip needs \cite{GCTflip} simple combinatorial algorithms for the decision problems mentioned in the introduction, akin to the the polynomial time, combinatorial algorithms in combinatorial optimization \cite{schrijver}. We briefly examine in this section, what is needed, in addition to saturation, for such simple algorithms to exist for the problems under consideration. The simple combinatorial algorithms in combinatorial optimization work only when the problem under consideration is unimodular--in which case the vertices of the underlying polytope $P$ are integral--or almost unimodular--e.g. when the vertices of $P$ are half integral. Edmond's algorithm for finding minimum weight perfect matching in nonbipartite graphs \cite{schrijver} is a classic example of the second case. In the unimodular case, Stanley's positivity result \cite{stanleyenu} implies that the rational function $F_P(t)$ has a positive form \[F_P(t)=\f {h(d) t^d + \cdots + h(0)} {(1-t)^{d+1}}.\] This is a reduced positive form with modular index one (Definition~\ref{dintroreducedpos}). In general, given a quasipolynomial $f(n)$, let us define the modular index $\Delta(F)$ of the rational function $F(t)=\sum_n f(n) t^n$ to be the minimum of the modular indices of the reduced positive forms of $F(t)$. It is defined to be $\infty$ if $F(t)$ has no reduced positive form. We can take $\Delta(F)$ as the deviation from unimodularity. For example, by Hypothesis~\ref{hintrolittleph3gen}, the modular index of the rational function $C_{\alpha,\beta}^\lambda(t)$ associated with the Littlewood-Richardson coefficient of arbitrary type is bounded by a constant. This constant is one in type $A$ (cf. Hypothesis~\ref{hintrolittleph3}), though the Littlewood-Richardson problem in type $A$ is not unimodular, since the hive polytope can have nonintegral vertices \cite{deloeravertices}. Similarly, by PH3 for the plethysm constant (Section~\ref{hph3plethysm}), the modular index of the rational function $A_{\lambda,\mu}^\pi(t)$ associated with the plethysm constant $a_{\lambda,\mu}^\pi$ is $\poly(\mbox{ht}(\lambda),\mbox{ht}(\mu), \mbox{ht}(\pi))$, where $\mbox{ht}(\lambda)$ denotes the height of the partition $\lambda$. If a function $f(x)$ belongs to modular $\#P$ (Figure~\ref{finclclass}), the modular index of the Ehrhart series $F_{P_x}(t)$ of $P_x$ in eq.(\ref{eqsatsharpdef} is polynomial in the rank of $x$. Roughly, this says that the situation is ``close'' to the unimodular case. Hence, in ``reasonable situations'' we can expect a purely combinatorial polynomial-time algorithm for deciding nonvanishing of $f(x)$ that does not need the ellipsoid method or basis reduction in lattices. This would constitute a stronger form of Theorem~\ref{tdecision}. Furthermore, in analogy with the known situations in combinatorial optimization, we can even expect a polynomial-time combinatorial algotithm for the asscociated the optimization problem (cf. Question~\ref{qopti}). We cannot specify what a reasonable situation means. But we expect it to hold for the structural constants under consideration in this paper. These belong to modular $\#P$ by PH1 (Hypothesis~\ref{phph1}) and PH3 (Hypothesis~\ref{phph3}). \subsection{PH2 and existence of an FPRAS} \label{ssisfpras} So far we have only discussed the problems of deciding nonvanishing of various types of structural constants. Though exact computation of these structural constants is necessarily hard, due to their $\#P$-completeness, we may ask if their approximate values can be computed efficiently if they are nonzero. Specifically, we ask if there is an FPRAS (Fully Polynomial Randomized Approximation Scheme) \cite{sinclair} for its computation. It is plausible that this is so for each of the structural constants in Problems~\ref{pintrokronecker}-\ref{pintrosubgroup} and \ref{pintrogit} with $X$ being a class variety--though this is not necessary for the purposes of the flip. We shall see in this section that PH2 plays a crucial role in this context. Let us see how. Let $f(x)$ be the function associated with the structural constant under consideration and $\tilde f(x,n)$ the associated stretching quasi-polynomial (Theorem~\ref{tquasisubgroup}, \ref{tquasigit}). Assume that PH1 (Hypothesis~\ref{phph1}) holds. Let $P=P_x$ be the polytope as therein so that $f(x)$ is equal to the number integer points in $P$ and $\tilde f(x,n)$ is equal to the Ehrhart quasi-polynomial $f_P(n)$ of $P$. If PH2 also holds (Hypothesis~\ref{phph2})--so that $f(x)$ belongs to positive $\#P$ (Figure~\ref{finclclass})--then the coefficients of the Ehrhart quasi-polynomial $f_P(n)$ are nonnegative. The leading coefficient of each $f_{i,P}(n)$ is equal to the volume of $P$ \cite{stanleyenu}. This can be approximately to a high precision efficiently, because there is a FPRAS for computing the volume of a convex polytope \cite{dyer}. If there is an FPRAS for every nonnegative coefficient of each $f_{i,P}(n)$ under consideration, then by positivity, there is an FPRAS for computing $f(x)=f_P(1)$. For such an FPRAS to exist, there has to be a {\em positive} formula for each coefficient of $f_{i,P}(n)$, like the positive formula in terms of the volume for its leading coefficient. If such positive formulae exist, then the such FPRAS'es can be expected. There are residue formulae \cite{szenes} for the Ehrhart quasi-polynomial of an arbitrary polytope. But these are not positive. Existence of positive formulae may be intimately linked with the algebraic geometry of the canonical models associated with these structural constants. It may be remarked that PH2 is crucial here. For a general $P$, the coefficients of $f_P(n)$ can be negative, and hence, would not be efficiently approximable. A rough analogy is provided by the problem computing the permament of an integer matrix. If the entries are nonnegative, then the usual formula for the the permament is positive; i.e., there are no cancellations. For this case, there is an FPRAS \cite{sinclair}. Otherwise, even deciding if the permanent is nonzero (which is easier than the FPRAS problem) is conjecturally intractable assuming $P\not = NP$. The main significance of PH2 here is that it converts a discrete approximation problem--the problem of approximating the number of integer points in a convex polytope, which is known to be hard--into a continuous approximation problem that is analogous to the problem of approximating the volume, which is known to be easy. \section{Other structural constants} \label{sother} The paradigm of saturated and positive integer programming in this paper may be applicable to the problems of deciding nonvanishing of several other fundamental structural constants in representation theory and algebraic geometry, in addition to the ones in Problems~\ref{pintrokronecker}-\ref{pintrogit} treated above, such as \begin{enumerate} \item the coefficients of the Kazhdan-Lusztig polynomials \cite{kazhdan}; cf. Section~\ref{sskazhdan}, \item the well behaved special cases of the parabolic Kostka polynomials and their $q$-analogues \cite{kirillov}; cf. Section~\ref{ssqkostka}, \item the structural coefficients of the multiplication of Schubert polynomials, \end{enumerate} \section{$q$-saturated programming}\label{sqsat} We shall briefly address in this section the first two problems mentioned above. For that we need to extend the paradigm of saturated integer programming to the $q$-setting that arises when the structural constants of interest are $q$-polynomials. We turn to this task next. Let $f(x,q)$ be a $q$-polynomial; i.e., \[ f(x,q)=\sum_i q^i f_i(x),\] where $x\in \N^l$, and for every $i$, $f_i(x)$ is a polynomial in $x$. We say that $f(x,q)$ has a $q$-convex $\#P$-formula, if for every $x\in \N^l$, there exists a linear function $l_x$ on $\R^m$, whose specification can be computed in $\poly(\bitlength{x})$ time, and a polytope $P_x \subseteq R^m$ such that \begin{equation} \label{eqqdefnsat0} f(x,1)=\phi(P_x), \end{equation} is a convex $\#P$-formula (cf. eq~\ref{eqconvex0}) for $f(x,1)$, and $f_i(x)$ is the number of integer points $y$ in $P_x$ with $l_x(y)=i$. Using this formula we can associate with every $x$ an Ehrhart $q$-series as follows. First, let us observe that, given a polytope $P$ and a linear function $l(y)$, the generating function \[ F_{P,l}(t,q)=\sum_{n,i\ge 0} f_P(n,i) t^n q^i,\] where $f_P(n,i)$ is the number of integer points $y$ in the polytope $n P$ with $l(y)=i$, is a rational function of the form \begin{equation} \label{eqqsat11} \f{P(q,t)}{\prod_j (1-q^{a_j}t^{b_j})^{c_j}}, \end{equation} where $P(t,q)$ is a polynomial in $t$ and $q$, and $a_j,b_j,c_j$ are nonnegative integers. This follows from the theory of linear diophontine equations \cite{stanleyenu}. We call $F_{P,l}(t,q)$ the Ehrhart $q$-series of $(P,l)$. If $f(x,q)$ has a $q$-convex $\#P$-formula, then for every $x$, we have an Ehrhart $q$-series $F_{P_x,l_x}(t,q)$ for the pair $(P_x,l_x)$. We say that a $q$-convex $\#P$-formula is saturated, if the formula (\ref{eqqdefnsat0}) for $f(x,1)$ is saturated (cf. Definition~\ref{dintrosat} and its extension in Section~\ref{ssextension}). A $q$-positive or a $q$-modular $\#P$-formula is defined similarly. Using these, we can define the complexity classes $q$-convex $\#P$, $q$-saturated $\#P$, $q$-positive $\#P$ and $q$-modular $\#P$ of $q$-polynomials very much as in Section~\ref{ssharpp}. We can also define analogues of SH, PH1,2,3 in the $q$-setting. If $f(x,q)$ belongs to $q$-saturated or $q$-convex $\#P$, we also want to associate with it a stretching function $\tilde f(x,q,n)$ in an intrinsic fashion, without resorting to its $q$-convex $\#P$-formula, such that the generating function \[ F(t,q)=\sum_{n,i\ge 0} \tilde f(x,q,n)t^n q^i,\] coincides with the Ehrhart $q$-series associated with its $q$-convex $\#P$-formula. The following are two problems associated with a $q$-polynomial $f(x,q)$: \begin{enumerate} \item Given $x$, decide if $f(x,1)$ is nonvanishing. \item Compute the degree of $f(x,q)$. \end{enumerate} In the context of the first problem, Theorem~\ref{tindexquasi} implies: \begin{theorem} \label{tqsatdecision} Suppose $f(x,q)$ belongs to $q$-saturated (more strongly, $q$-positive) $\#P$. Then nonvanishing of $f(x,1)$ can be decided in $\poly(\bitlength{x})$ time. \end{theorem} The computation of the degree of $f(x,q)$ is equivalent to finding the maximum of the linear function $l_x$ on the polytope $P_x$. The result above does not say anything about this optimization problem (cf. Question~\ref{qopti}). But a polynomial time algorithm for this can be expected if the modular index of the Ehrhart series of $P_x$ is always small (cf. Section~\ref{ssissimpler}). We now illustrate these notions with two examples. \subsection{Parabolic $q$-Kostka polynomials} \label{ssqkostka} Given a partition $\lambda$, and sequences of nonnegative integers $\mu$ and $\eta$, called compositions, satisfying certain constraints, Kirillov \cite{kirillov} defines a parabolic Kostka polynomial $K_{\lambda,\mu,\eta}(q)$, and proves that the series \begin{equation} \label{eqkirillov1} \sum_{n\ge 0} K_{n \lambda,n \mu,\eta}t^n \end{equation} is a rational function of the form $P_{\lambda,\mu,\eta}(q,t)/Q_{\lambda,\mu,\eta}(q,t)$, where $P_{\lambda,\mu,\eta}(q,t)$ and $Q_{\lambda,\mu,\eta}(q,t)$ are mutually prime polynomials in $q$ and $t$ with integer coefficients, and $Q_{\lambda,\mu,\eta}$ is of the form: \[ Q_{\lambda,\mu,\eta}(q,t)=\sum_j(1-q^j t)^{a_j},\] where $j$ runs over a finite set of nonnegative integers and $a_j$'s are positive integers. Thus a natural definition of the stretching function associated with $K_{\lambda,\mu,\eta}(q)$ is $K_{\lambda,\mu,\eta}(q,n)=K_{n \lambda,n \mu,\eta}(q)$. Kirillov also defines a certain notion of saturation for parabolic Kostant polynomials. It is quite different from the notion of saturation in this paper. It is known that the coefficients of $K_{\lambda,\mu,\eta}(q)$ are nonnegative if $\lambda,\mu,\eta$ satisfy certain constraints \cite{kirillov}. Under these conditions, it is possible that the parabolic $q$-Kostka polynomial belongs to $q$-saturated (and possibly, $q$-positive) $\#P$. By Theorem~\ref{tqsatdecision}, this would imply that nonvanishing of its value at $q=1$ can be decided in polynomial time. Since the modular index of the rational function (\ref{eqkirillov1}) is one, it may be expected that its degree can also be computed in polynomial time. \subsection{Kazhdan-Lusztig polynomials}\label{sskazhdan} Given permutations $x,w$ in the symmetric group $S_m$, let $P_{x,w}(q)$ denote the Kazhdan-Lusztig polynomial \cite{kazhdan}. In what follows, we can consider any finite Weyl group in place of $S_m$. We assume that $x$ and $w$ are specified in the usual sequential notation. Given $x$ and $w$, $P_{x,w}(q)$ can be computed in $\poly(\bitlength{x},\bitlength{w})$ space. Specifically, the algorithm for its computation in \cite{kazhdan} can be made to work in PSPACE in a straightforward way. In view of the complexity hierarchy in Figure~\ref{finclclass}, we can then ask if the Kazhdan-Lusztig polynomial belongs to $q$-saturated, and more strongly, $q$-positive $\#P$. A supporting evidence in the affirmative direction is provided by the work of Lascoux and Sch\"utzenberger in the Grassmannian case \cite{lakshmibai}. Specifically, they give a formula of $P_{x,w}(q)$ in this case, which can be seen to be a $q$-convex $\#P$-formula. It is trivially saturated. It is easy to verify PH3 in this case using the theory of $P$-partitions in \cite{stanleyenu}. Experimental results on computer (akin to the ones in Chapter~\ref{cevidence}) support PH2. Another supporting evidence is given by the work in \cite{leclerc}, which shows that Littlewood-Richardson coefficients are specializations of certain Kazhdan-Lusztig polynomials for the affine symmetric group at $q=1$. We have already discussed the saturation and positivity hypotheses in this special case in Section~\ref{sintroLR}. If PH2 holds for the Kazhdan-Lusztig polynomial, then an FPRAS for the approximate computation if its value at $q=1$ can be expected (Section~\ref{ssisfpras}). This value has fundamental significance \cite{kazhdan}. If PH3 holds then one can also expect a polynomial-time algorithm for computing its degree (cf. the remark after Theorem~\ref{tqsatdecision}). This also plays a crucial role in the Kazhdan-Lusztig theory. The saturation and positivity hypotheses for the Kazhdan-Lusztig polynomial seem far harder than the ones for the structural constants in Problems~\ref{pintrokronecker}-\ref{pintrogit}, since the only known proof \cite{kazhdan1} of the nonnegativity of its coefficients is based on Weil conjectures \cite{kazhdan1,weil2}. In general, we do not even know how to associate with it a stretching function whose generating function is rational of the form (\ref{eqqsat11}). %\include{quasipoly} \chapter{Quasi-polynomiality and canonical models} \label{cquasipoly} In this chapter we prove quasipolynomiality of the stretching functions associated with the various structural constants under consideration (Section~\ref{squasiproof}), describe the associated canonical models (Section~\ref{scanonicalmodel}), define a positive basis (Section~\ref{spositivebasis}), formulate the positivity hypothesis PH0 (Section~\ref{sonex}), describe the role of quantum groups in that context (Section~\ref{squantumgroup}), and discuss the significance of PH0 in the context of PH1,3 (Section~\ref{ssigni}). We also prove finite generation of the semigroup of weights (Theorem~\ref{tfinitegensubgroup}) in Section~\ref{sconesub}, give an elementary proof of rationality in Theorem~\ref{tquasisubgroup} (a) (Section~\ref{selement}), and take a step towards bounding the order of poles of the rational generating function of the stretching quasipolynomial associated with the kronecker coefficient (Section~\ref{spole}). \section{Quasi-polynomiality} \label{squasiproof} Here we prove Theorem~\ref{tquasigit}; Theorems~\ref{tquasiplethysm} and \ref{tquasisubgroup} are its special cases in view of the reduction in Section~\ref{sreduction}. This, in turn, follows from the following more general result. Let $R=\oplus_k R_d$ be a normal graded $\C$-algebra with an action of a reductive group $H$. Assume that $\spec(R)$ has rational singularities. Let $H_0$ be the connected component of $H$ containing the identity. Let $H_D=H/H_0$ be its discrete component. Given a dominant weight $\pi$ of $H_0$, we consider the module $V_\pi=V_\pi(H_0)$, an $H$-module with trivial action of $H_D$. Let $s_d^\pi$ denote the multiplicity of the $H$-module $V_\pi$ in $R_d$. Let $\tilde s_d^\pi(n)$ be the multiplicity of the $H$-module $V_{n \pi}$ in $R_{n d}$. This is a stretching function associated with the mulitplicity $s_d^\pi$. Let $S_d^\pi(t)=\sum_{n\ge 0} \tilde s_d^\pi(n) t^n$. \begin{theorem} \label{tquasimain1} \noindent (a) (Rationality) The generating function $S_{d}^\pi(t)$ is rational. \noindent (b) (Quasi-polynomiality) The stretching function $\tilde s_{d}^\pi(n)$ is a quasi-polynomial function of $n$. \noindent (c) There exist graded, normal $\C$-algebras $S=S(s_{d}^\pi)=\oplus_n S_n$ and $T=T(s_{d}^\pi)=\oplus_n T_n$ such that: \begin{enumerate} \item The schemes $\spec(S)$ and $\spec(T)$ are normal and have rational singularities. \item $T=S^H$, the subring of $H$-invariants in $S$. \item The quasi-polynomial $\tilde s_{d}^\pi(n)$ is the Hilbert function of $T$. \end{enumerate} \noindent (d) (Positivity) The rational function $S_{d}^\pi(t)$ can be expressed in a positive form: \begin{equation} \label{eqtquasipnew} S_{d}^\pi(t)=\f{h_0+h_1 t+ \cdots+h_k t^k}{\prod_j(1-t^{a(j)})^{k(j)}}, \end{equation} where $a(j)$'s and $k(j)$'s are positive integers, $\sum_j k(j)=k+1$, where $k$ is the degree of the quasi-polynomial $\tilde s_d^\pi(n)$, $h_0=1$, and $h_i$'s are nonnegative integers. \end{theorem} Theorem~\ref{tquasigit} follows from this by letting $R$ be the homogeneous coordinate ring of $X$. More generally, if $W$ is an irreducible representation of $H_D$, we can consider the $H$-module $V_\pi\otimes W$. Let $s_d^{\pi,W}$ be its multiplicity in $R_d$. Let $\tilde s_d^{\pi,W}(n)$ be the multiplicity of the trivial $H$-representation in the $H$-module $R_{n d} \otimes V_{n \pi}^* \otimes \sym^n(W^*)$. Then \begin{theorem} \label{tquasimain2} Analogue of Theorem~\ref{tquasimain1} holds for $\tilde s_d^{\pi,W}(n)$. \end{theorem} For the purposes of the flip, Theorem~\ref{tquasimain1} suffices. \proof We shall only prove Theorem~\ref{tquasimain1}, the proof of Theorem~\ref{tquasimain2} being similar. The proof is an extension of M. Brion's proof (cf. \cite{dehy}) of quasi-polynomiality of the stretching function associated with a Littlewood-Richardson coefficient of any semisimple Lie algebra. Clearly (a) follows from (b); cf. \cite{stanleyenu}. \noindent (b) and (c): Let $C_d$ be the cyclic group generated by the primitive root $\zeta$ of unity of order $d$. It has a natural action on $R$: $ x \in C_d$ maps $z \in R_k$ to $x^k z$. Let $B=R^{C_d}=\sum_{n\ge 0} R_{nd} \subseteq R$ be the subring of $C_d$-invariants. By Boutot \cite{boutot}, $B$ is a normal $\C$-algebra and $\spec(B)$ has rational singularities. Assume that $H_0$ is semisimple; extension to the reductive case being easy. Let $\pi^*$ be the dominant weight of $H_0$ such that $V_\pi^*=V_{\pi^*}$. By Borel-Weil \cite{fultonrepr}, \[ C_{\pi^*}=\oplus_{n \ge 0} V_{n \pi}^*= \oplus_{n \ge 0} V_{n \pi^*},\] is the homogeneous coordinate ring of the $H_0$-orbit of the point $v_{\pi^*} \in P(V_{\pi^*})$ corresponding to the highest weight vector. This $H_0$-orbit is isomorphic to $H_0/P_{\pi^*}$, where $P_{\pi^*} \subseteq H_0$ is the parabolic stabilizer of $v_{\pi^*}$. Hence $C_{\pi^*}$ is normal and $\spec(C_{\pi^*})$ has rational signularities; cf. \cite{hashimoto,mehta,ramanathan,smith}. It follows that $B\otimes C_{\pi^*}$ is also normal, and $\spec(B\otimes C_{\pi^*})$ has rational singularities. Consider the action of $\C^*$ on $B\otimes C_{\pi^*}$ given by: \[ x (b \otimes c)=(x\cdot b) \otimes (x^{-1} \cdot c),\] where $x \in \C^*$ maps $b \in B_n$ to $x^n b$, the action on $\C_{\pi^*}$ being similar. Consider the invariant ring \begin{equation} \label{eqS} S=(B\otimes C_{\pi^*})^{\C^*}= \oplus_n S_n= \otimes_{n \ge 0} R_{n d} \otimes V_{n \pi}^*. \end{equation} By Boutot \cite{boutot}, it is a normal, and $\spec(D)$ has rational singularities. Since $V_{n \pi}$ is an $H$-module, the algebra $S$ has an action of $H$. Let \begin{equation} \label{eqT} T=T(s_d^\pi)=S^{H}=\oplus_{n \ge 0} T_n \end{equation} be its subring of $H$-invariants. By Boutot \cite{boutot}, it is normal, and $\spec(T)$ has rational singularities--this is the crux of the proof. By Schur's lemma, the multiplicity of the trivial $H$-representation in $S_n=R_{n d}\otimes V_{n \pi}^*$ is precisely the multiplicity $\tilde s_d^\pi(n)$ of the $H$-module $V_{n \pi}$ in $R_{n d}$. Hence, the Hilbert function of $T$, i.e., $\dim(T_n)$, is precisely $\tilde s_d^\pi(n)$, and the Hilbert series $\sum_{n\ge 0} \dim(T_n) t^n$ is $S_d^\pi(t)$. Quasipolynomiality of $\tilde s_d^\pi(n)$ follows by applying the following lemma: \begin{lemma} \label{ldehy} (cf. \cite{dehy}) If $T=\oplus_{n=0}^\infty T_n$ is a graded $\C$-algebra, such that $\spec(T)$ is normal and has rational simgularites, then $\dim(T_n)$, the Hilbert function of $T$, is a quasi-polynomial function of $n$. \end{lemma} \noindent (d) Since $\spec(T)$ has rational singularities, $T$ is Cohen-Macaualey. Let $t_1,\ldots,t_u$ be its homogeneous sequence of parameters (h.s.o.p.), where $u=k+1$ is the Krull dimension of $T$. By the theory of Cohen-Macauley rings \cite{stanleycomb}, it follows that its Hilbert series $S_d^\pi(t)$ is of the form \begin{equation} \label{eqposform1} \f{h_0+ h_1 t + \cdots +h_k t^k} {\prod_{i=1}^{k+1} (1-t^{d_i})}, \end{equation} where (1) $h_0=1$, (2) $d_i$ is the degree of $t_i$, and (3) $h_i$'s are nonnegative integers. This proves (d). \qed \begin{remark} \label{rfinitegen} A careful examination of the proof above shows that rationality of $S_d^\pi(t)$, and more strongly, asymptotic quasi-polynomiality of $\tilde s_d^\pi(n)$ as $n\rightarrow \infty$, can be proved using just Hilbert's result on finite generation of the algebra of invariants of a reductive-group action. Boutot's result is necessary to prove quasi-polynomiality for all $n$. This is crucial for saturated and positive integer programming (Chapter~\ref{csatpos}). \end{remark} \subsection{A minimal positive form} \label{sminimal} The form (\ref{eqposform1}) of $S_d^\pi(t)$ is not unique because it depends on the degrees $d_i$'s of the paramters $t_i$'s. For future use, let us record the following consequences of the proof. Let $T$ be the ring constructed in the proof above. \begin{cor} Suppose $T$ has an h.s.o.p. $t=(t_1,\ldots,t_u)$ with $d_i=\deg(t_i)$. Then $S_d^\pi(T)$ has a positive rational form (\ref{eqposform1}) with $d_i=\deg(t_i)$ therein. \end{cor} Let us call an h.s.o.p. $t=(t_1,\ldots,t_u)$ of $T$ reduced, if each $d_i=\deg(t_i)$ is divisible by $\ind(\tilde s_d^\pi)$, the index of $\tilde s_d^\pi(n)$, and $\min\{d_i\}= \ind(\tilde s_d^\pi)$. \begin{cor} If $T$ has a reduced h.s.o.p. then $S_d^\pi(t)$ has a reduced positive form (Definition~\ref{dintroreducedpos}). \end{cor} The proof above is lets us define a minimal positive form of the rational function $S_d^\pi(t)$ associated with a structural constant $s$. For this, let us order h.s.o.p.'s of $T$ lexicographically as per their degree sequences. Here the degree seqeunce of an h.s.o.p. $t=(t_1,\ldots,t_u)$ is defined to be $(d_1,\ldots,d_u)$, where $d_i=\deg(t_i)$. The form (\ref{eqposform1}) is the same for any h.s.o.p. of lexicographically minimum degree sequence. We call it the {\em minimal positive form} of $S_d^\pi(t)$. Since Problems~\ref{pintrokronecker}, \ref{pintroplethysm},\ref{pintrosubgroup}, \ref{pintrolittle} are special cases of Problem~\ref{pintrogit}, this defines minimal positive forms of the rational generating functions of the stretching quasi-polynomials (cf. Theorem~\ref{tquasisubgroup}) associated with the structural constants in these problems. \subsection{The rings associated with a structural constant}\label{ssringsassoc} The preceding proof also associates with the structural constant $s$ a few rings which will be important later. Specifically, let $S=S(s)$ and $T=T(s)$ be the rings as in Theorem~\ref{tquasimain1} (c) associated with the structural constant $s=s_d^\pi$. Let $R=R(s)$ be the homogeneous coordinate ring of $X$ as in Theorem~\ref{tquasimain1}. We call $R(s),S(s)$ and $T(s)$ the rings associated with the structure constant $s$. When $s=m_\lambda^\pi$, as in the subgroup restriction problem (Problem~\ref{pintrosubgroup}), $X\cong G/P$ as given in eq.(\ref{eqXsubgroup}. Then these rings are explicitly as follows: \begin{equation} \begin{array} {lcl} R(m_\lambda^\pi)&=&\oplus_{n\ge 0} V_{n \lambda} (G), \\ S(m_\lambda^\pi)&=&\oplus_{n\ge 0} V_{n \lambda}(G) \otimes V_{n \pi}(H)^*, \\ T(m_\lambda^\pi)&=& \oplus_{n\ge 0} (V_{n \lambda} (G) \otimes V_{n \pi}(H)^*)^H. \end{array} \end{equation} By specializing the subgroup restriction problem further to the Littlewood-Richardson problem (Problem~\ref{pintrolittle}), we get the following rings associated by Brion (cf. \cite{dehy}) with the Littlewood-Richardson coefficient $c_{\alpha,\beta}^\lambda$: \begin{equation} \label{eqringslittle} \begin{array}{lcl} R(c_{\alpha,\beta}^\lambda)&=&\oplus_{n\ge 0} V_{n \alpha} (H) \otimes V_{n \beta} (H), \\ S(c_{\alpha,\beta}^\lambda)&=& \oplus_{n\ge 0} V_{n \alpha} (H) \otimes V_{n \beta} (H) \otimes V_{n \lambda}(H)^*, \\ T(c_{\alpha,\beta}^\lambda)&= &\oplus_{n\ge 0} (V_{n \alpha} (H) \otimes V_{n \beta} (H) \otimes V_{n \lambda}(H)^*)^H. \end{array} \end{equation} \section{Canonical models} \label{scanonicalmodel} There are several rings other than $T(c_{\alpha,\beta}^\lambda)$ whose Hilbert function coincides with the Littlewood-Richardson stretching quasi-polynomial $\tilde c_{\alpha,\beta}^\lambda (n)$. For example, let $P=P_{\alpha,\beta}^\lambda$ be the $BZ$-polytope whose Ehrhart quasi-polynomial coincides with $\tilde c_{\alpha,\beta}^\lambda (n)$. We can associate with $P$ a ring $T_P$ as in Stanley \cite{stanleytoric} whose Hilbert function coincides with $\tilde c_{\alpha,\beta}^\lambda (n)$. There are many other choices for $P$. For example, in type $A$, we can consider a hive polytope or a honeycomb polytope instead of the BZ-polytope. The rings $T_P$'s associated with different $P$'s will, in general, be different, and there is nothing canonical about them. In contrast, the ring $T(c_{\alpha,\beta}^\lambda)$ is special because: \begin{prop} \label{plusztigkashi} The rings $R(c_{\alpha,\beta}^\lambda), S(c_{\alpha,\beta}^\lambda), T(c_{\alpha,\beta}^\lambda)$ have quantizations $R_q(c_{\alpha,\beta}^\lambda), S_q(c_{\alpha,\beta}^\lambda), T_q(c_{\alpha,\beta}^\lambda)$ endowed with canonical bases in the terminology of Lusztig \cite{lusztigbook}. Furthermore, the canonical bases of $R_q(c_{\alpha,\beta}^\lambda), S_q(c_{\alpha,\beta}^\lambda)$ are compatible with the action of the Drinfeld-Jimbo quantum group associated with $H=GL_n(\C)$, and the canonical basis of $S_q(c_{\alpha,\beta}^\lambda)$ is an extension of the canonical basis of $T_q(c_{\alpha,\beta}^\lambda)$ in a natural way (cf. Definition~\ref{dextension} below). \end{prop} This follows from the work of Lusztig (cf. \cite{lusztigpnas}, Chapter 27 in \cite{lusztigbook}) and Kashiwara (cf. Theorem2 in \cite{kashiwaraglobal}). Specializations of these canonical bases at $q=1$ will be called canonical bases of $R(c_{\alpha,\beta}^\lambda), S(c_{\alpha,\beta}^\lambda), T(c_{\alpha,\beta}^\lambda)$. In view of Proposition~\ref{plusztigkashi}, we call the rings $R(c_{\alpha,\beta}^\lambda),S(c_{\alpha,\beta}^\lambda)$ and $T(c_{\alpha,\beta}^\lambda)$ the {\em canonical rings} associated with the Littlewood-Richardson coefficient $c_{\alpha,\beta}^\lambda$, and $X=\proj(R(c_{\alpha,\beta}^\lambda)), Y=\proj(S(c_{\alpha,\beta}^\lambda))$ and $Z=\proj(T(c_{\alpha,\beta}^\lambda))$ the {\em canonical models} associated with $c_{\alpha,\beta}^\lambda$. As already remarked in Section~\ref{sapproach}, PH1 for Littlewood-Richardson coefficients is a formal consequence of the properties of Kashiwara's crystal operators associated with these canonical bases; cf. Sections~\ref{sexlittle}, \ref{sph0ph1} and \cite{dehy,kashiwara2,littelmann,lusztigbook}. SH and PH3 may also follow from the properties of these canonical bases as suggsted in Section~\ref{ssigni}. This leads us to ask if the rings associated with other structural constants under consideration in this paper have quantizations with analogous bases. If so, these may be used in the same spirit to prove PH1, SH and PH3, and plausibly, even PH2. To formalize this, let $s$ be a structural constant which is either the Kronecker coefficient as in Problem~\ref{pintrokronecker}, or the plethysm constant as in Problem~\ref{pintroplethysm}, or the multiplicity $m_\lambda^\pi$ in Problem~\ref{pintrosubgroup}, or the multiplicity $s_d^\pi$, as in Problem~\ref{pintrogit}, when $X$ therein is a class variety. Let $R(s),S(s),T(s)$ be the rings associated with $s$ (Section~\ref{ssringsassoc}). Let $X(s)=\proj(R(s)), Y(s)=\proj(S(s))$ and $Z(s)=\proj(R(s))$. We call $R(s), S(s), T(s)$ the {\em canonical rings} associated with $s$, and $X(s), Y(s), Z(s)$ the canonical models associated with $s$, because we expect them to be special as in the case of the Littlewood-Richardson coefficients. Specifically, a conjectural hypothesis PH0 below (Hypothesis~\ref{hph0main}) states that they have quantizations endowed with positive bases that are analogous to the canonical bases of the quantizations of the canonical rings associated with the Littlewood-Richardson coefficient (cf. Proposition~\ref{plusztigkashi}). Before we can state this hypothesis, we have to specify what is meant by a positive basis. We turn to this task next. \section{A positive basis}\label{spositivebasis} We define a {\em positive basis} in this section by abstracting the fundamental positivity property of a canonical basis in the theory of Drinfeld-Jimbo quantum groups and the Kazhdan-Lusztig basis of Hecke algebra. Roughly a basis is called {\em positive} if it has the following positivity properties: \begin{enumerate} \item {\bf Mathematical positivity}: its multiplicative and representational structural constants are nonnegative. \item {\bf Complexity theoretic positivity}: It admits a localization akin to the local crystal basis of Kashiwara \cite{kashiwara1}, which is, furthermore, efficient. This means there are operators on this localization, akin to Kashiwara's crystal operators, which can be computed in polynomial time. \end{enumerate} As we shall see below, these two positivity properties are the most important properties in the context of the hypotheses PH1, SH and PH3. Kashiwara's crystal operators on the canonical bases that arise in the theory of Drinfeld-Jimbo quantum groups can be computed in polynomial time. Though the complexity-theoretic issues are not discussed in Kashiwara's or Lusztig's papers, this fact is easy to verify using Littlemann's \cite{littelmann} combinatorial characterization of Kashiwara's operators. In fact, it can be verified that these operators can even be computed fast in parallel; i.e., in polylogarithmic time using polynomially many processors. This means the problem of their computation belongs to the complexity class $NC \subseteq P$ \cite{karp}. Analogously, we can stipulate in the definition of a positive basis below--though we shall not do so--that the problem of computing the operators in the second condition therein belongs to $NC$. Since $NC$ lies low in the complexity hierarchy, this means the complexity-theoretic problem underneath the second positivity condition is ``easy'' compared to the complexity-theoretic positivity hypothesis (PHflip) that we began with. Now we turn to a formal definition of a positive basis. This needs several preliminary definitions. \subsection{Positivity of multiplication and representation} \label{sposmultrepr} We begin with definitions in the unquantized setting. Let $T$ be a $\C$-algebra, and $B(T)$ its basis. If $T$ is graded, we also assume that each element of $B(T)$ is homogeneous. Let $\bar B(T)\subseteq B(T)$ be a (minimal) subset of basis elements which generate $T$. \begin{defn} \label{dpositive1} We say that the multiplicative structure of $B(T)$ is positive if for any $b \in \bar B(T)$ and $b' \in B(T)$, \begin{equation} \label{eqdpos1} b b'= \sum_{b'' \in B(T)} g(b,b',b'') b'', \end{equation} where $g(b,b',b'')$ is a nonegative integer. More strongly, we can also require this for any $b,b' \in B(T)$. Here $g(b,b',b'')$'s are called multiplicative structural constants. \end{defn} A weaker notion is the following. Let $[T]$ denote a compact specification of $T$, and $\bitlength{T}$ its bit length. For example, when $T$ is the coordinate ring of a variety $Z$ with a compact specification, as in Section~\ref{sspgit}, then we can let $[T]=[Z]$. The compact specifications in the cases of interest will be clear from the context. Let $B(T)$ be a basis of $T$ as above. We assume that each element $b \in B(T)$ is assigned a degree $d(B)$. For example, when $T$ is graded, $d(B)$ is just the degree of $B$. In other cases of interest to us, $d(B)$ will be clear from the context. We assume that each $b\in B(T)$ has a unique label $[b]$, whose bitlength $\bitlength{b}$ is $\poly(\bitlength{d(b)},\bitlength{T})$, where $d(b)$ is the degree of $b$. \begin{defn} \label{dpositivemult1} We say that the multiplicative structure of $B(T)$ is positive up to multiplicative factors if for any $b \in \bar B(T)$ and $b' \in B(T)$ \begin{equation} \label{eqdposmult1} b b'= \sum_{b'' \in B(T)} f(b,b',b'') g(b,b',b'') b'', \end{equation} where $f(b,b',b'') \in \C$ is computable in $\poly(\bitlength{b},\bitlength{b'},\bitlength{b''})$ time, and $g(b,b',b'')$ is a nonegative integer. Typically, $f(b,b',b'')$ will just be a polynomial time computable sign (plus or minus one). \end{defn} \begin{remark} Nonnegativity of $g(b,b',b'')$ is the main condition here. In problems of interest polynomial-time computability of $f(b,b',b'')$ is typically an easy condition in comparison; see Section~\ref{ssheckealgebra} for an example. For this reason, positivity up to multiplicative factors, here and below, is primarily a mathematical notion. \end{remark} \begin{defn} \label{dstrongpos} We say that the multiplicative structure of $B(T)$ is strongly positive if it is positive and the multiplicative structure has low computational complexity. This means, given $b,b',b''$, nonvanishing of each coefficient $g(b,b',b'')$ can be decided in $\poly(\bitlength{b},\bitlength{b'},\bitlength{b''})$ time. A strongly positive multiplicative structure upto mutiplicative factors is defined similarly. \end{defn} A basic decision problem concerning the multiplicative structure of $B(T)$ is: \begin{problem}\label{pdecpos1} Given $b,b',b''$, decide if $b''$ belongs to the support of the product $b b'$, when expressed in terms of $B(T)$. \end{problem} If the multiplciative structure of $B(T)$ is strongly positive (upto multiplicative factors), this decision problem belongs to the complexity class $P$. Now let $R$ be a $\C$-algebra, with action of a reductive group $H$. Let us assume that it has a compact representation $[R]$, with bit length $\bitlength{R}$. For the sake of simplicity, let us also assume that the reductive group $H=H_D \times H_0$, where the discrete component $H_D$ is the symmetric group $S_m$, for some $m$, and $H_0$, the connected component containing the identity, is the semisimple, simply connected complex Lie group. All $H$'s that arise in the flip in characteristic zero are essentially of this form, with slight extensions that can be easily taken into account. For the problems that arise when $H_D$ is the general linear group over a finite field, as needed for a flip over a finite field \cite{GCT11}, or, more generally, a finite simple group of a Lie type, see Section~\ref{sgeneralh}. Let $B(R)$ be a basis of $R$. We assume, as above, that every $b\in B(R)$ has a label, whose bitlength is denoted by $\bitlength{b}$. Let ${\cal H}_0$ denote the semisimple Lie algebra of $H_0$. Let $e_i,f_i$ denote its usual generators. Let $s_i$'s denote the usual (simple transposition) generators of $H_D=S_m$. We say that $a$ is a generator associated with $H$, if $a=s_i$, for some $i$, or $a=e_j$ or $f_j$ for some $j$. \begin{defn} We say that $B$ is compatible with respect to the $H$-action if there exists a filtration \begin{equation} \label{eqcomposition} B=B_0 \supseteq B_1 \supseteq B_2 \supseteq \cdots \end{equation} such that each ${\cal B}_i/{\cal B}_{i+1}$ is an irreducible $H$-module, where ${\cal B}_i$ denotes the linear $\C$-span of $B_i$. We call $\hat B_i=B_i \setminus B_{i+1}$ the factors of $B$. \end{defn} \begin{remark} This definition can be relaxed somewhat. It would suffice for our purposes if each ${\cal B}_i/{\cal B}_{i+1}$ has an explicit decomposition as an $H$-module; i.e., it need not be irreducible. \end{remark} \begin{defn} \label{dposcomp} We say that the action (representation) of $H$ is positive in the basis $B=B(R)$ if for any generator $a$ and $b\in B$, \begin{equation} \label{eqposcompat} a \cdot b= \sum_{b' \in B(T)} k(a,b,b') b', \end{equation} where $k(a,b,b')$ is a nonegative integer. Here $k(a,b,b')$'s are called representation-structure constants. We say that the action is positive up to multiplicative factors, if for any generator $a$ and $b\in B$, \begin{equation} \label{eqdcan2} a \cdot b= \sum_{b' \in B(T)} h(a,b,b') k(a,b,b') b', \end{equation} where the factor $h(a,b,b') \in \C$ is computable in $\poly(\bitlength{b},\bitlength{b'})$ time, and $k(a,b,b')$ is a nonegative integer. Typically, $h(a,b,b')$ will be a polynomial time computable sign (plus or minus one). \end{defn} \begin{remark} If $R$ an algebra with the action of a semisimple Lie algerba ${\cal G}$, then positivity of the ${\cal G}$-action can be defined similarly. \end{remark} \begin{defn} \label{dstrongposcomp} We say that the representation of $H$ is strongly positive in $B(R)$ if it is positive as above, and in addition, it has low computational complexity. This means, given $a,b,b'$, nonvanishing of the representation-structure constant $k(a,b,b')$ can be decided in $\poly(\bitlength{a},\bitlength{b},\bitlength{b'})$ time. A strongly positive action, upto multiplicative factors, is defined similarly. \end{defn} A basic decision problem associated with the representation structure of $B(R)$ is: \begin{problem} \label{pdecpos2} given $b,b'$ and $g$, decide if $b'$ occurs in the support of $g\cdot b$. \end{problem} If the action of $H$ is strongly positive (up to multiplicative factors) this decision problem belongs to $P$. Finally, we need the notion of compatibility between two bases. Let $S$ be a $\C$-algebra with $H$-action. Let $T=S^H\subseteq S$ be the subring of $H$-invariants. \begin{defn} \label{dextension} We say that a basis $B(S)$ of $S$ is an extension of a basis $B(T)$ of $T$ if there an $H$-homomorphism $\psi:S \rightarrow T$ such that $B(T)$ consists of images of the canonical basis elements in $B(S)$ that belong to the composition factors isomorphic to the trivial $H$-representation. \end{defn} We illustrate the preceding definitions with an example. \subsubsection{Example: The ring of symmetric functions} \label{sringsym} Let $V=\C^m$, $G=GL(V)$, $H=S_m$, with the natural embedding $H \rightarrow G$. Let us consider the spacial case of the subgroup restriction problem (Problem~\ref{pintrosubgroup}), with $V_\lambda(G)=V$, and $V_\pi(H)$ the trivial representation of $H$. Then $s=m_\lambda^\pi$, the multiplicity of the trivial representation in $V$, is one. Though the decision problem (Problem~\ref{pintrosubgroup}) is trivial in this case, the canonical model associated with $s$ is nontrivial. The canonical rings $R=R(s)$ and $S=S(s)$ associated with $s$ in this case coincide with $\C[V]=\C[x_1,\ldots,x_m]$. The ring $T=T(s)=S^H$ is the subring of symmetric functions. Let $\{s_\alpha\}$ be the Schur basis of $T$, where each $s_\alpha(x_1,\ldots,x_m)$ is the Schur polynomial \cite{macdonald}. Its multiplication structure is strongly positive. Because \[ s_\alpha s_\beta = \sum_\gamma c_{\alpha,\beta}^\gamma s_\gamma,\] where $c_{\alpha,\beta}^\gamma$ is the Littlewood-Richardson coefficient, which is nonnegative, and its nonvanishing can be decided in polynomial time as we discussed in Section~\ref{sintroLR}. It may be conjectured that $S$ has a basis such that: \begin{enumerate} \item it is an extension of the Schur basis of $T$, \item it has (strongly) positive multiplicative and repressentation structures, and \item it is compatible with the $H$-action. \end{enumerate} This is a special case of the more general Hypothesis~\ref{hph0main} later. The usual basis of $S$ consisting of the monomials in $x_i$'s is not compatible with the $H$-action. The ring $T$ has another basis $\{e_\lambda\}$ with (strongly) positive multiplication structure consiting of the monomials in elementary symmetric functions. But this basis is not expected to have a positive extension to $S$ as above. Thus even in this simplest example we see that a basis of $T$ with positive multiplication structure is extremely rigid if we require, in addition, a positive extention to $S$ compatible with the $H$-action. This indicates a general phenomenon that positive structures are extremely rigid. \subsection{Positivity of multiplication and representation in a $q$-setting} \label{ssqposbasis} We now give $q$-analogues of the definitions in Section~\ref{sposmultrepr}. Assume that $R_q$ and $T_q$ are $\C(q)$-algebras. In the applications of interest $R_q$ and $T_q$ will be certain quantizations of $R$ and $T$, respectively--we shall elaborate what this means later in this section. More generally, as in the Kazhdan-Lusztig theory, we can consider, instead of $\C(q)$, rings obtained by adjoining fractional powers of $q$ to $\C(q)$. We assume that $R_q$ and $T_q$ have compact specifications, as in the unquantized setting. Let $\bitlength{R_q}$ and $\bitlength{T_q}$ denote their bitlengths. Let $B(T_q)$ be a basis of $T_q$, homogeneous if $T_q$ is graded. We assume, as before, that each $b\in B(T_q)$ has a unique label $[b]$, whose bitlength $\bitlength{b}$ is $\poly(\bitlength{d(b)},\bitlength{T_q})$, where $d(b)$ is the degree of $b$. Let $\bar B(T_q)\subseteq B(T_q)$ be a (minimal) subset of basis elements which generate $T_q$. \begin{defn} \label{dpositiveq} We say that the multiplicative structure of $B(T_q)$ is positive if, for any $b \in \bar B(T_q)$ and $b' \in B(T_q)$, \begin{equation} \label{eqdcan1q} b b'= \sum_{b'' \in B(T)} g(b,b',b'') b'', \end{equation} where $g(b,b',b'') \in \N[q,q^{-1}]$; i.e., it is a polynomial in $q$ and $q^{-1}$ with nonnegative integers; more strongly, we can require this for any $b,b' \in B(T_q)$. \end{defn} \begin{defn} \label{dpositivemultq} We say that the multiplicative structure of $B(T_q)$ is positive up to multiplicative factor, if for any $b \in \bar B(T_q)$ and $b' \in B(T_q)$, \begin{equation} \label{eqdcan1qmult} b b'= \sum_{b'' \in B(T)} f(b,b',b'') g(b,b',b'') b'', \end{equation} where the factor $f(b,b',b'') \in \C(q)$ is computable in $\poly(\bitlength{b},\bitlength{b'},\bitlength{b''})$ time, and $g(b,b',b'') \in \N[q,q^{-1}]$. \end{defn} \begin{remark} If we have adjoined fractional powers of $q$ to $\C(q)$, we can allow the factor $f(b,b',b'')$ to be an element in this enlarged ring. \end{remark} \begin{defn} We say that the multiplicative structure of $B(T_q)$ in Definition~\ref{dpositiveq} is strongly positive if, in addition, the multiplicative structure has low computational complexity. That is, the problem of deciding nonvanishing of the multiplicative structural constant $g(b,b',b'')$, as a polynomial in $q$, given $b,b',b''$, belongs to $P$. A strongly positive multiplication structure up to multiplicative factors is defined similarly; cf. Defintion~\ref{dpositivemultq}. \end{defn} Now assume that $R$ is as in Section~\ref{sposmultrepr}. Let $H=H_D \times H_0$ be as there, with $H_D=S_m$. Let $H_m(q)$ denote the Hecke algebra \cite{kazhdan} associated with $H_D=S_m$, and $U_q({\cal H}_0)$ the Drinfeld-Jimbo quantized enveloping algebra \cite{drinfeld,jimbo} associated with the Lie algebra ${\cal H}_0$. Let $H_q=H_m(q)\otimes U_q({\cal H}_0)$. This notation is a bit unsatisfying: $H$ should have been $\C[S_m]\otimes U({\cal H}_0)$ here, where $\C[S_m]$ denotes the group of algebra of $S_m$, since $H_m(q)$ is, really speaking, a quantization of $\C[S_m]$. We shall ignore this slight mismatch. \begin{defn} \label{dquantization} We say that $R_q$ is a quantization of $R$, with an action of $H_q$ that is a quantization of the $H$-action on $R$, if: \begin{enumerate} \item when $R$ is graded, $\dim(R_{q,d})=\dim(R_d)$, where $R_{q,d}$ denotes the degree $d$ component of $R_q$ and $R_d$ the degree $d$ component of $R$. \item the multiplicity of any irreducible representation $V$ of $H$ in $R$ is equal to the multiplicity of its quantization $V_q$ in $R_q$. \end{enumerate} \end{defn} Recall that there are several irreducible representations of $U_q({\cal H}_0)$ that specialize at $q=1$ to the same irreducible representation of $U({\cal H}_0)$. But all of them only differ in sign \cite{klimyk}. In the definition above, we are assuming for the sake of simplicity that the only irreducible representations of $U_q({\cal H})$ with trivial sign occur in $R_q$. If that is not the case, the multiplicity of any irreducible representation $V$ of $H$ in $R$ is required to be equal to the total multiplicity of all irreducible representations $V_q^j$ of $H_q$ that specialize to $V$ at $q=1$. Definition~\ref{dquantization} is the only property of quantization that is needed in this paper. So assume that $R_q$ is a quantization of $R$ as above. Let $B(R_q)$ be a basis of $R_q$. By a quantized generator $a$, we mean either a generator of $H_q(m)$ that is a quantization of a generator $s_i$ of $S_m$--which we denote by $T_i$-- or a generator of $U_q({\cal H}_0)$ that is a quantization of a generator $e_j$ or $f_j$ of ${\cal H}_0$--which we again denote by $e_j$ or $f_j$. \begin{defn} \label{dcompatq} We say that $B$ is compatible with respect to the $H_q$-action if there exists a filtration \begin{equation} \label{eqcompositionq} B=B_0 \supseteq B_1 \supseteq B_2 \supseteq \cdots \end{equation} such that each ${\cal B}_i/{\cal B}_{i+1}$ is an irreducible $H_q$-module, where ${\cal B}_i$ denotes the linear $\C$-span of $B_i$. We call $\hat B_i=B_i \setminus B_{i+1}$ the factors of $B$. \end{defn} \begin{defn} \label{dposreprq} We say that the representation of $H_q$ in the basis $B=B(R_q)$ is positive if for any quantized generator $a$ and $b\in B$, \begin{equation} \label{eqposcompq2} a \cdot b= \sum_{b' \in B(T)} k(a,b,b') b', \end{equation} where $k(a,b,b')\in \N[q,q^{-1}]$. We say that the representation is strongly positive if it has low computational complexity; i.e., nonvanishing of the representation-structure constant $k(a,b,b')$, as a polynomial, can be decided in $\poly(\bitlength{b},\bitlength{b'},\bitlength{b''})$ time. A (strongly) positive representation, up to multiplicative factors, is defined similarly (cf. Definition~\ref{dpositivemultq}). \end{defn} \subsection{Efficient localization} \label{slocalization} Now we define an efficient localization of an $H_q$-action on $R_q$. Let $A$ be the ring of rational functions in $q$ without a pole at $q=0$. Let $B=B(R_q)$ be a basis of $R_q$ compatible with the $H_q$ action. Let \begin{equation} \label{eqfiltration} B=B_0 \supseteq B_1 \supseteq B_2 \supseteq \cdots \end{equation} be its $H_q$-compatible filtration as in eq.(\ref{eqcompositionq}) corresponding to a composition series. Let $\hat B_i=B_i \setminus B_{i+1}$ be its factors. First, let us assume that $H$ is a complex semisimple group. Hence, $H_q=U_q({\cal H})$. Let $L\subseteq R_q$ be the $A$-lattice, i.e., the free $A$-module generated by $B$. Let $\bar B=\{\bar b| b \in B\}$ be the basis of $L/ q L$, where $-: L \rightarrow L/ q L$ is the quotient map. We assume that each element $b\in B$ is a weight vector, and the weight of $b \in B$ can be computed in $O(\poly(\bitlength{b}))$ time. \begin{defn} \label{dlocalizationsemisimple} We say that the representation of $U_q({\cal H}_0)$ on $R_q$ has a polynomial-time computable localization in the basis $B$ if \begin{enumerate} \item The pair $(L,\bar B)$ is an (upper) crystal base of $R_q$ as per Kashiwara's terminology \cite{kashiwara1}, \item Given $b\in B$ and a generator $e_i$ of $U_q({\cal H}_0)$, $\tilde e_i(\bar b)$, where $\tilde e_i$ denotes Kashiwara's crystal operator \cite{kashiwara1} associated with $e_i$, can be computed in $\poly(\bitlength{b})$ time (recall that $\tilde e_i(\bar b) \in \bar B \cup\{0\}$). Similarly for $f_i$. \end{enumerate} \end{defn} In this case, let $C(B)$ be a graph on $B$, wherein we connect two vertices $b,b'$ with a red directed edge labelled $i$ if $\tilde e_i(\bar b)=\bar b'$, and with a blue directed edge labelled $i$ if $\tilde f_i(\bar b)=\bar b'$. Then $C(B)$ is a crystal graph \cite{kashiwara1} on $B$ with respect to the action of $U_q({\cal H}_0)$. The connected components of this crystal graph correspond to factors of the filtration (\ref{eqfiltration}). We call $b\in B$ a highest weight vertex of $C(B)$ if $\tilde e_i(\bar b)=0$ for all $i$. Whether a given $b\in B$ is a highest weight vertex can be decided in $\poly(\bitlength{b})$ time. Now assume that $H=S_m$, the symmetric group. So $H_q=H_m(q)$, the Hecke algebra. \begin{defn} \label{dlocalizationhecke} We say the representation of $H_m(q)$ on $R_q$ has a polynomial-time computable localization in the basis $B$ if there exists for each $b\in B$, a polynomial-time computable standard tableau $\mbox{Tab}(b)$, and for each $b \in B$ and a generator $T_i$ of $H_m(q)$, a polynomial-time computable element $\tilde T_i(b) \in B\cup \{0\}$ so that \begin{enumerate} \item $\tilde T_i(b)$ belongs to the support of $T_i(b)$, \item Letting $C'(B)$ be the graph with $B$ as its vertices formed by connecting two nodes $b,b'\in B$ by a yellow directed edge labelled $i$ if $b'=\tilde T_i(b)$, each connected component of $C'(B)$ has precisely one node labelled with each standard tableau of size $m$. Furthermore, the connected components of $C'(B)$ correspond to the factors of the filtration (\ref{eqfiltration}). \end{enumerate} \end{defn} We call $C'(B)$ a crystal graph with respect to the $H_q(m)$-action, and $\tilde T_i$ a crystal operator corresponding to $T_i$. Now assume that $H_D \times H_0$, with $H_D=S_m$, and $H_0$ a complex semisimple algebra. So $H_q=H_m(q)\otimes U_q({\cal H}_0)$. \begin{defn} \label{dlocalization} We say that the $H_q$-action on $R_q$ has a polynomial-time computable localization in the basis $B$ if the actions of $H_q(m)$ as well as $U_q({\cal H}_0)$ have polynomial-time computable localizations in $B$, and both these localizations are compatible in the obvious sense. \end{defn} Compatibility above means the following. Let $G(B)$ be the graph on $B$ obtained by connecting two vertices $b,b$ with a red directed edge labelled $i$ if $\tilde e_i(\bar b)=\bar b'$, with a blue directed edge labelled $i$ if $\tilde f_i(\bar b)=\bar b'$, and with a yellow directed edge labelled $i$ if $\tilde T_i(b)=b'$. Then the connected components of $G(B)$ correpsond to the factors of an $H_q$-compatible filtration of $B$ as in (\ref{eqfiltration}), and furthermore, the restriction of $G(B)$ to any factor is a product of a (red-blue) crystal graph for the $U_q({\cal H}_0)$-action with a (yellow) crystal graph for the $H_q(m)$-action. We call $G(B)$ the crystal graph on $B$. Given a generator $g$ of $H_q$, let $\tilde g$ denote its localization: That is, if $g=e_i,f_i$ or $T_i$, $\tilde g=\tilde e_i, \tilde f_i$ or $\tilde T_i$, respectively. The following is a localization of the decision Problem~\ref{pdecpos2}: \begin{problem} \label{plocal} \noindent Decision problem: Given $b,b',g$, decide if $\tilde g(b)=b'$. \noindent Functional problem: Given $b,g$, compute $\tilde g(b)$. \end{problem} If the representation of $H_q$ has a polynomial-time computable localization in the basis $B$, this decision (functional) problem belongs to $P$. \subsection{A positive basis} Finally, we can define a positive basis. \begin{defn} \label{dpositivebasisquant} A basis $B=B(R_q)$ is called a positive basis of $R_q$ compatible with $H_q$-action if \begin{enumerate} \item Its multiplicatition structure is positive (Definition~\ref{dpositiveq}). \item The representation of $H_q$ in $B$ is positive (Definition~\ref{dposreprq}). \item It is compatible with respect to the $H_q$-action (Definition~\ref{dcompatq}). \item The $H_q$-action on $R_q$ has a polynomial-time computable localization in $B$ (Definition~\ref{dlocalization}). \end{enumerate} A positive basis of $R_q$ up to multiplicative factors is defined similarly. A strongly positive basis of $R_q$ (up to multiplicative factors) compatible with the $H_q$-action is also defined similarly. In particular, if $H$ is trivial, i.e., $R_q$ is a plain ring, then a positive basis of $R_q$ is just a basis of $R_q$ with positive multiplicative structure. Positive basis up to multiplicative factors, and a strongly positive basis (up to multiplicative factors) are defined similarly. \end{defn} \begin{remark} As we shall in the examples below, a positive basis, if it exists, is an extremely rigid, essential unique, structure. But this definition of a positive basis does not tell us how to construct such a basis if it exists. Actual construction needs extension of the theory of quantum groups alongs the lines discussed in Section~\ref{squantumgroup}. \end{remark} \begin{remark} \label{rimportant} Suppose $H$ is a complex semisimple group. Then any ring $R_q$ with $H_q$ action has a local crystal basis \cite{kashiwara1}. But Kashiwara's crystal operators on this basis need not be polynomial-time computable in general, because existence of a local crystal basis in \cite{kashiwara1} nonconstructive. It can be made constructive, but the resulting algorithm would have exponential complexity. For this reason, polynomial-time computability of the localization is a crucial complexity-theoretic positivity condition here. Mathematical positivity of the representation and the multiplicative structure are there, in essence, to enforce it; see Section~\ref{ssmathvscomplex}. \end{remark} \begin{remark} Any ring $R_q$ with $H_q$ action has a basis admitting positive representation. For example, assume $H$ is complex, semisimple. Consider a complete decomposition of of $R_q$ into finite dimensional irreducible $H_q$-modules; $H_q=U_q({\cal H})$. Consider the canonical basis for each irreducible $H_q$-submodule of $R_q$ as per Lusztig \cite{lusztigbook}. The union of these canonical bases is a basis that admits positive representation by Lusztig's result. But, in general, the multiplicative structure of such a basis need not be positive, and Kashiwara's crystal operators on the corresponding local crystal basis need not be polynomial-time computable. The main problem here is that irredcible $H_q$-modules can occur with high multiplicities. Unless these multiplicities are resolved in some ``canonical'' manner, we cannot expect the multiplicative structure to be positive and the crystal operators to be polynomial-time computable. \end{remark} For future reference, we note down an immediate consequence of the definition above. Let $H=H_d \times H_0$ with $H_D=S_m$. Let $\alpha$ be a partition of size $m$, and $\beta$ a dominant weight of $H_0$. Then $V_{\alpha,\beta}(H)=V_\alpha(S_m) \times V_\beta(H_0)$ is an irreducible $H$-representation--here $V_\alpha(S_m)$ is the Specht module labelled by the partition $\alpha$. Let $a_d^{\alpha,\beta}$ be the multiplicity of $V_{\alpha,\beta}(H)$ in $R_d$, the degree $d$ component of $R$. \begin{prop} \label{pbasiccrystal} Suppose $R$ is a graded ring with an $H$-action. Suppose $R_q$ is its quantization, with the action of $H_q$ that is a quantization of the action of $H$ on $R$ (Definition~\ref{dquantization}). Suppose $R_q$ has a positive basis $B(R_q)$ compatible with the $H_q$-action. Then, $a_d^{\alpha,\beta}$ has a $\#P$-formula. That is, it belongs to the complexity class $\#P$; see Figure~\ref{finclclass}. \end{prop} Here the input consists of the specification $[R]$ of $R$, $\alpha,\beta$ and $d$. \proof Given a partition $\alpha$ of size $m$, let $V_{q,\alpha}$ be the $q$-analogue (quantization) of the Specht module $V_\alpha(S_m)$ \cite{kazhdan}. It is an irreducible representation of the Hecke algebra $H_m(q)$. Given a dominant weight $\beta$ of $U_q({\cal H}_0)$, let $V_{q,\beta}$ denote the $q$-analogue of $V_\beta(H_0)$ \cite{klimyk}. It is an irreducible representation of $U_q({\cal H}_0)$. Well, there are several irreducible representations of $U_q({\cal H}_0)$ that specialize to $V_{\beta}(H_0)$. But all of them differ just in sign; cf. \cite{klimyk}. For the sake of simplicity, we assume that the only irreducible representation of $U_q({\cal H}_0)$ that occurs in $R_q$ is the one with the trivial sign, the general case being not very different. We let $V_{q,\beta}$ denote this quantization of $V_\beta(H_0)$. Let $G(B)$ be the crystal graph over $B$ as defined after Definition~\ref{dlocalization}. Each connected component of $G(B)$ is a product of a crystal graph for the $H_q(m)$-action on $R_q$ and a crystal graph of the $U_q({\cal H}_0)$-action on $R_q$. We call a vertex $c$ of a crystal graph for the $H_q(m)$-action distinguished if the standard tableau $\mbox{Tab}(c)$ associated with it (cf. Definition~\ref{dlocalizationhecke}) is canonical; i.e., the entries $1$ to $m$ occur in the consecutive order as the tableau is read left to right and top to bottom. We call a vertex $c'$ of a crystal graph for the $U_q({\cal H}_0)$-action distinguished if $\tilde e_i(\bar c')=0$ for all $e_i$; i.e., it is a highest weight vertex. We call a vertex $b \in B$ of $G(B)$ distinguished if it is of the form $(c,c')$ where $c$ and $c'$ are distinguished vertices of the crystal graphs for the $H_q(m)$- and $U_q({\cal H}_0)$-action respectively. Let $\alpha(b)$ denote the shape (partition) of the tableau $\mbox{Tab}(c)$. Let $\beta(b)$ denote the weight of $c'$. Then it follows from Definitions~\ref{dlocalizationsemisimple}-\ref{dlocalization} that, given $b$, whether it is distinguished can be determined in $\poly(\bitlength{b})$ time, and if so, $\alpha(b)$ and $\beta(b)$ can be computed in $\poly(\bitlength{b})=\poly(\bitlength{d},\bitlength{R})$ time. Now $a_d^{\alpha,\beta}$ is just the multiplicity of $V_{q,\alpha}\otimes V_{q,\beta}$ in $R_{q,d}$, the degree $d$ component of $R_q$. Then \[ a_d^{\alpha,\beta}=\sum_{b \in B} 1,\] where $b$ ranges over all distinguished elements (vertices) in $B$ of degree $d$ such that $\alpha(b)=\alpha$ and $\beta(b)=\beta$. Whether a given $b \in B$ of degree $d$ contributes to this sum can be clearly checked in $\poly(\bitlength{d},\bitlength{R},\bitlength{\alpha},\bitlength{\beta})$ time. Hence this is a $\#P$-formula. \qed \section{Examples} \label{sexamples} We illustrate the preceding definitions with a few examples of positive bases. \subsection{Hecke algebra} \label{ssheckealgebra} Let $H=S_m$, the symmetric group, $H_q=H_m(q)$ the corresponding Hecke algebra, and $R_q=H_m(q)$ with the action of $H_m(q)$ from the left (or right). We can also consider $R_q$ as a bimodule with $H_m(q)$-action from the left and the right. Here the compact specification $[R]$ of $H_m(q)$ is simply the rank parameter $m$. We define the bitlength $\bitlength{R}$ to be $m$, since $m$ is a rank parameter; i.e., $m$ is specified in unary. The Kazhdan-Lusztig basis \cite{kazhdan,kazhdan1} of $H_m(q)$ is a positive basis of $R_q$, up to multiplicative factors, compatible with the $H_q$-action. This can be seen as follows. Compatibility with the $H_q$-action is implied by the cellular decomposition of the Kazhdan-Lusztig basis into left (or right, or two-sided) cells. Positivity of the representation as well as positivity of the multiplicative structure, up to multiplicative factors, is implied by the following well-known multiplicative formula. Let $T_r$ be the generator of $H_m(q)$ corresponding to the simple transposition $s_r \in S_m$. Let $C_w$ be the Kazhdan-Lusztig basis element corresponding to a permutation $w \in S_m$. Let $<$ denote the Bruhat order on $S_m$. Let $\mu(z,w)$ be the coefficient of $q^{1/2(l(w)-l(x)-1)}$ in the Kazhdan-Lusztig polynomial $P_{x,w}$, where $l(w)$ denotes the length of $w$. Write $x \prec w$ if $P_{x,w}$ has the largest possible degree $(l(w)-l(x)-1)/2$. Then \begin{equation} \label{eqkazhdanmult} \begin{array}{lcll} T_r C_w &=& -Cw & \mbox{if}\quad r w w. \end{array} \end{equation} Since the coefficients of $P_{x,w}$ are known to be nonnegative integers \cite{kazhdan1}, it follows that $\mu(z,w)$ is a nonnegative integer. Hence, positivity of the multiplicative structure and the representation, up to multiplicative factors, is clear. The multiplicative factors here are the sign $-$ and the factors $q,q^{1/2}$ in eq.(\ref{eqkazhdanmult}). They are computable in $\poly(m)$ time since, given $w,w' \in S_m$, whether $w0$ is represented in a compact form by specifying only its nonzero parts $\lambda_1,\ldots, \lambda_r$. This is important since $\dim(G)$ can be exponential in $\dim(H)$ and $\bitlength{\mu}$. A compact representation allows $\bitlength{\lambda}$ to be small, say $\poly(\dim(H), \bitlength{\mu})$, in this case. We begin with a simpler special case. \begin{prop} If $\dim(V)=\poly(\dim(H))$, then $m_{\lambda}^\pi$ can be computed in $PSPACE$; i.e., in $\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi},\dim(H))$ space. \end{prop} This implies that the Kronecker coefficient (Problem~\ref{pintrokronecker}) can be computed in PSPACE. \proof Let us use the notation $\bar \lambda$ instead of $\lambda$ to be consistent with the notation used in Klimyk's formula (\ref{eqklimyk}). By the latter, $m^{\pi}_{\bar \lambda}$ can be computed in PSPACE if $n_{\bar \mu}(V_{\bar \lambda})$ in that formula can be computed in PSPACE for every $\bar \mu$ and $\bar \lambda$. In type $A$, this is just the number of Gelfand-Tsetlin tableau with the shape $\bar \lambda$ and weight $\bar \mu$. If $\dim(V)=\poly(\dim(H))$, the size of such a tableau is $O(\dim(V)^2)=\poly(\dim(H))$. So we can count the number of such tableu in PSPACE as follows: Begin with a zero count, and cycle through all tableaux of shape $\bar \lambda$ in polynomial space one by one, increasing the count by one everytime the tableau satisfies all constraints for Gelfand-Tsetlin tableau and has weight $\bar \mu$. In general, the role of Gelfand-Tsetlin tableaux is played by Lakshmibai-Seshadri (LS) paths \cite{littelmann,dehy}. \qed The argument above does not work if $\dim(V)$ is not $\poly(\dim(H))$, as in the plethym problem (Problem~\ref{pintroplethysm}), where $\dim(V)=\dim(V_\mu)$ can be exponential in $n=dim(H)$ and the bitlength of $\mu$. In this case, the algorithm cannot even afford to write down a tableau since its size need not be polynomial. Next we turn to Theorem~\ref{tpspacegenplethysm}. For the sake of simplicity, we shall prove it only for $H=SL_n(\C)$, or rather $GL_n(\C)$--i.e., the usual plethysm problem. This illustrates all the basic ideas. The general case is similar. We shall prove a slightly stronger result in this case: \begin{theorem} \label{tpspaceplethysm2} The plethysm constant $a_{\lambda,\mu}^\pi$ can be can be computed in $\poly(\bitlength{\lambda},\bitlength{\mu}, \bitlength{\pi})$ space. \end{theorem} Here the dependence on $n=\dim(H)$ is not there. This makes a difference if the heights of $\mu$ and $\pi$ are less than $n=\dim(H)$--remember that we are using a compact representation of a partition in which only nonzero parts are specified. This is really not a big issue. Because $a_{\lambda,\mu}^\pi$ depends only on the partitions $\lambda,\mu,\pi$ and not $n$. Hence, without loss of generality, we can assume that $n$ is the maximum of the heights of $\mu$ and $\pi$. It is possible to strengthen Theorem~\ref{tpspacegenplethysm} similarly. To prove Theorem~\ref{tpspaceplethysm2}, we shall give an efficient parallel algorithm to compute $\tilde a_{\lambda,\mu}^\pi$ that works in $\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi})$ parallel time using $O(2^{\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi})})$ processors. This will show that the problem of computing $\tilde a_{\lambda,\mu}^\pi$ is in the complexity class $NC(\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi}), 2^{\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi})})$, which is contained in PSPACE by Proposition~\ref{pinclusion}. The basic idea is to parallelize the classical character-based algorithm for computing $a_{\lambda,\mu}^\pi$ by using efficient parallel algorithm for inverting a matrix and solving a linear system (Proposition~\ref{pparallel}). We begin by recalling the standard facts concerning the characters of the general linear group. Given a representation $W$ of $GL_m(\C)$, let $\rho:GL_m(\C)\rightarrow GL(W)$ be the representation map. Let $\chi_\rho(x_1,\ldots,x_m)$ denote the formal character of this representation $W$. This is the trace of $\rho(\mbox{diag}(x_1,\ldots,x_m))$, where $\mbox{diag}(x_1,\ldots,x_n)$ denotes the generic diagonal matrix with variable entries $x_1,\ldots,x_m$ on its diagonal. If $W$ is an irreducible representation $V_\lambda(GL_m(\C))$, then $\chi_\rho(x_1,\ldots,x_m)$ is the Schur polynomial $S_\lambda(x_1,\ldots,x_m)$. By the Weyl character formula, \begin{equation} \label{eqweylchar} S_\lambda=\f{|x_j^{\lambda_i+m-i}|}{|x_j^{m-i}|}, \end{equation} where $|a^i_j|$ denotes the determinant of an $m\times m$-matrix $a$. The Schur polynomials form a basis of the ring of symmetric polynomials in $x_1,\ldots,x_m$. The simplest basis of this ring consists of the complete symmetric polynomials $M_\beta(x_1,\ldots,x_m)$ defined by \[M_\beta(x_1,\ldots,x_m)= \sum_\gamma t^\gamma,\] where $\gamma$ ranges over all permutations of $\beta$ and $t^\gamma=\prod_i x_i^{\gamma_i}$. Schur polynomials are related to $M_\beta$ by: \begin{equation} \label{eqschurmon} S_\lambda=\sum_\beta k_\lambda^\beta M_\beta, \end{equation} where $k_\lambda^\beta$ is the Kostka number. This is the number of semistandard tableau of shape $\lambda$ and weight $\beta$. If the representation $W$ is reducible, its decomposition into irreducibles is given by: \begin{equation} W=\sum_\pi m(\pi) V_\pi(GL_n(\C)), \end{equation} where $m(\pi)$'s are the coefficients of the formal character $\chi_\rho(x_1,\ldots,x_m)$ in the Schur basis: \[\chi_\rho=\sum_\pi m(\pi) S_\pi.\] \subsubsection*{Proof of Theorem~\ref{tpspaceplethysm2}} Let $\lambda,\mu,\pi$ be as in Theorem~\ref{tpspaceplethysm2}. Let $H=GL_n(\C)$, $V=V_\mu(H)$, $G=GL(V)$. Let $s_\lambda(x_1,\ldots,x_m)$ be the formal character of the representation $V_\lambda(G)$ of $G$. Here $m=\dim(V_\mu)$ can be exponential in $n$ and $\bitlength{\mu}$. The basis of $V_\mu(H)$ is indexed by semistandard tableau of shape $\mu$ with entries in $[1,n]$. Let us order these tableau, say lexicographically, and let $T_i$, $1\le i \le m$, denote the $i$-th tableau in this order. With each tableau $T$, we associate a monomial \[t(T)=\prod_{i=1}^n t_i^{w_i(T)},\] where $w_i(T)$ denotes the number of $i$'s in $T$. Given a polynomial $f(x_1,\ldots,x_m)$, let us define $f_\mu=f_\mu(t_1,\ldots,t_n)$ to be the polynomial obtained by substituting $x_i=t(T_i)$ in $f(x_1,\ldots,x_m)$. Then the formal character of $V_\lambda(G)$, considered as an $H$-representation of via the homomorphism $H \rightarrow G=GL(V_\mu(H))$, is the symmetric polynomial $S_{\lambda,\mu}(t_1,\ldots,t_n) =(S_\lambda)_\mu$. The plethysm constant $a_{\lambda,\mu}^\pi$ is defined by: \begin{equation} S_{\lambda,\mu}(t_1,\ldots,t_n) =\sum_\pi a_{\lambda,\mu}^\pi S_\pi(t_1,\ldots,t_n). \end{equation} An efficient parallel algorithm to compute $a_{\lambda,\mu}^\pi$ is as follows. Here by an efficient parallel algorithm, we mean an algorithm that works in $\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi})$ time using $2^{\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength{\pi})}$ processors. We will repeatedly use Proposition~\ref{pparallel}. \subsubsection*{Algorithm} \noindent (1) Compute $S_{\lambda,\mu}(t_1,\ldots,t_n)$. By the Weyl character formula (\ref{eqweylchar}), \[S_{\lambda,\mu}(t_1,\ldots,t_n)=\f {A_{\lambda,\mu}(t_1,\ldots,t_n)} {B_{\lambda,\mu}(t_1,\ldots,t_n)},\] where $A_\lambda(x_1,\ldots,x_m)$ and $B_\lambda(x_1,\ldots, x_m)$ denote the numerator and denominator in (\ref{eqweylchar}), and $A_{\lambda,\mu}=(A_\lambda)_\mu$, and $B_{\lambda,\mu}=(B_\lambda)_\mu$. Let $R=\C[t_1,\ldots,t_n]$. Then \[A_{\lambda,\mu}(t_1,\ldots,t_n)=|t(T_j)^{\lambda_i+m-i}|.\] This is the determinant of an $m\times m$ matrix with entries in $R$, where $m=\dim(V)$ can be exponential in $n$ and $\bitlength{\mu}$. It can be evaluated in $O(\log^2m)$ parallel ring operations using $\poly(m)$ processors. Each ring element that arises in the course of this algorithm is a polynomial in $t_1,\ldots, t_n$ of total degree $O(|\lambda| m)$, where $|\lambda|$ denotes the size of $\lambda$. The total number of its coefficients is $r=O((|\lambda| m)^n)$. Hence each ring operation can be carried out efficiently in $O(\log^2(r))$ parallel time using $\poly(r)$ processors. Since $\log m= \poly(n,\bitlength{\mu})$ and $\log r=\poly(n,\bitlength{\lambda},\bitlength{\mu})$, it follows that $A_{\lambda,\mu}$ can be evaluated in $\poly(n,\bitlength{\mu},\bitlength{\lambda})$ parallel time using $2^{\poly(n,\bitlength{\mu,\lambda})}$ processors. The determinant $B_{\lambda,\mu}$ can also be computed efficiently in parallel in a similar fashion. To compute $S_{\lambda,\mu}$, we have to divide $A_{\lambda,\mu}$ by $B_{\lambda,\mu}$. This can be done by solving an $r\times r$ linear system, which, again, can be done efficiently in parallel. This computation yields representation of $S_{\lambda,\mu}$ in the monomial basis $\{M_\beta\}$ of the ring of symmetric polynomials in $t_1,\ldots, t_n$. \noindent (2) To get the coefficients $a_{\lambda,\mu}^\pi$, we have to get the representation of $S_{\lambda,\mu}(t)$ in the Schur basis. This change of basis requires inversion of the matrix in the linear system (\ref{eqschurmon}). The entries of the matrix $K$ occuring in this linear system are Kostka numbers. Each Kostka number can be computed efficiently in parallel. Hence, all entries of this matrix can be computed efficiently in parallel. After this, the matrix can be inverted efficiently in parallel, and the coefficients $a_{\lambda,\mu}^\pi$'s of $S_{\lambda,\mu}$ in the Schur basis can be computed efficiently in parallel. Finally, we use Proposition~\ref{pinclusion} to conclude that $a_{\lambda,\mu}^\pi$ can be computed in $PSPACE$. \qed \section{Symmetric group} Next we prove Theorem~\ref{tpspacesubgroup} when $H=S_m$. Let $X=V_\mu(S_m)$ be an irreducible representation (the Specht module) of $S_m$ corresponding to a partition $\mu$ of size $m$. Let $\rho: H \rightarrow G=GL(X)$ be the corresponding homomorphism. \begin{theorem} \label{tpspacesymmetric} Given partitions $\lambda,\mu,\pi$, where $\mu$ and $\pi$ have size $m$, the multiplicity $m_{\lambda,\mu}^\pi$ of the Specht module $V_\pi(S_m)$ in $V_\lambda(G)$ can be computed in $\poly(m,\bitlength{\lambda})$ space. \end{theorem} \begin{remark} The bitlengths $\bitlength{\mu}$ and $\bitlength{\pi}$ are not mentioned in the complexity bound because they are bounded by $m$. \end{remark} For this, we need three lemmas. \begin{lemma} \label{lsymchar} The character of a symmetric group can be computed in $PSPACE$. Specifically, given a partition $\pi$ of size $m$, and a sequence $i=(i_1,i_2,\ldots)$ of nonnegative integers such that $\sum j i_j=m$, the value of the character $\chi_\pi$ of $S_m$ on the conjugacy class $C_i$ of permutations indexed by $i$ can be computed in $\poly(m)$ parallel time using $2^{\poly(m)}$ processors. Hence it can be computed in $\poly(m)$ space (cf. Proposition~\ref{pinclusion}). \end{lemma} Here the conjugacy class $C_i$ consists of those permutations that have $i_1$ $1$-cycles, $i_2$ $2$-cycles, and so on. \proof Let $k$ be the height of the partition $\pi$. Let $x=(x_1,\ldots,x_k)$ be the tuple of variables $x_i$'s. Given a formal series $f(x)$ and a tuple $(l_1,\ldots,l_k)$ of nonnegative integers, let $[f(x)]_{(l_1,\ldots,l_k)}$ denote the coefficient of $x_1^{l_1}\cdots x_k^{l_k}$ in $f$. By the Frobenius character formula \cite{fultonrepr}, \begin{equation} \chi_\lambda(C_i)=[f(x)]_{(l_1,\ldots,l_k)}, \end{equation} where \[ l_1=\pi_1+k-1,l_2=\pi_2+k-2,\ldots, l_k=\pi_k, \] and \[f(x)=\Delta(x) \prod_{j=1}^m P_j(x)^{i_j},\] with \begin{equation} \begin{array}{lcl} \Delta(x)&=&\prod_{i