TR-2007-04
Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
Ketan D. Mulmuley. 18 May, 2007.
Communicated by Ketan Mulmuley.
Obsolete: Yes (updated 12/19/12)
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}
Original Document
The original document is available in LaTeX (uploaded 18 May, 2007 by Ketan Mulmuley).