\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 m