\documentclass[11pt]{article} \usepackage{amsmath,amsfonts,amssymb,epsfig,color} \usepackage{rotating} \setlength{\parskip}{0.13cm} \setlength{\baselineskip}{10pt} %\renewcommand{\baselinestretch}{1.5} %\includeonly{appendix1} \begin{document} \title{Erratum to the saturation hypothesis (SH) in ``Geometric Complexity Theory VI''} \author{%Dedicated to Sri Ramakrishna \\ \\ Ketan D. Mulmuley \\ The University of Chicago \\ \\ http://ramakrishnadas.cs.uchicago.edu } \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{\limit}{{\mbox {lim}}} \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} A recent article \cite{rosas} points out an error in the saturation hypothesis (SH) in \cite{GCT6}. This hypothesis, and its stronger forms PH2 and PH3, are corrected in this note by appropriate relaxation without affecting the overall approach of Geometric Complexity Theory (GCT). 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. Let $\lambda$ and $\mu$ be partitions of length at most $n$, and $\pi$ a partition of length at most $n^2$. By a partition $\lambda$, we mean a sequence $\lambda: \lambda_1 \ge \lambda_2 \ge \cdots \lambda_k >0$ of nonnegative integers, where $k$ is called the height or length of $\lambda$. Let $V_\lambda(GL_n(\C))$ and $V_\mu(GL_n(\C))$ be the Weyl modules of $GL_n(\C)$ indexed by the parititions $\lambda$ and $\mu$, and $V_\pi(G)$ the Weyl module of $G$ indexed by $\pi$. Let $k_{\lambda,\mu}^\pi$ be the Kronecker coefficient. This 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$. Let $\tilde k_{\lambda,\mu}^\pi(n)=k_{n \lambda, n \mu}^{n \pi}$ be the associated stretching function, where $n$ is a positive integer. It is shown in \cite{GCT6} that it is a quasipolynomial. Here we say that $f(n)$ is a quasi-polynomial if there exist polynomials $f_i(n)$, $1\le i \le l$, for some positive integer $l$, such that $f(n)=f_i(n)$ if $n=i$ modulo $l$. We say it is {\em positive} if the coefficients of $f_i(n)$ are nonnegative for all $i$. We say it is {\em saturated} if $f_i(n) > 0$ for every $n\ge 1$ whenever $f_i(n)$ is not identically zero--this definition is slightly stronger than the one in \cite{GCT6}. Positivity implies saturation. It was conjectured in \cite{GCT6} that: \noindent (SH): $\tilde k_{\lambda,\mu}^\pi(n)$ is saturated. More strongly, \noindent (PH2) $\tilde k_{\lambda,\mu}^\pi(n)$ is positive. A recent article \cite{rosas} gives counter examples to SH and PH2 as stated. A similar phenomenon was also reported in \cite{GCT7,GCT8}, where it was observed that the structural constants of the nonstandard quantum groups associated with the plethysm problem (of which the Kronecker problem is a special case) need not satisfy an analogue of PH2. But it was observed there that PH2 holds after a small adjustment. Specifically, define the {\em positivity index} $p(f)$ of a quasipolynomial $f(n)$ to be the smallest nonnegative integer such that $f(n+p(f))$ is positive. The saturation index $s(f)$ is defined similarly. As per the experimental evidence in \cite{GCT7,GCT8}, the positivity (and hence saturation) indices of the structural constants there are small, though not always zero; eg. see Figures 30,33,35 in \cite{GCT8}. The same can be expected here. This leads to the following relaxed forms of SH and PH2. \begin{hypo} \label{hsh}{\bf (SH)} The quasipolynomial $k(n)=\tilde k_{\lambda,\mu}^\pi(n)$ is almost saturated; i.e. $s(k)=O(\poly(h))$, where $h \le n$ is the maximum of the heights of $\lambda,\mu$ and $\pi$. This means there exist nonnegative constants $a$ and $b$ (independent of $n$, $\lambda,\mu$ and $\pi$) such that $s(k)\le a{h^b}$, \end{hypo} The stronger hypothesis is the following. \begin{hypo} {\bf (PH2)} The quasipolynomial $k(n)=\tilde k_{\lambda,\mu}^\pi(n)$ is almost positive. This means $p(k)=O(\poly(h))$. \end{hypo} This is also supported by the experimental evidence in \cite{rosas} where too it may be observed that the positivity index is small. \begin{prop} \label{psh} Assuming the hypothesis PH1 in \cite{GCT6}, or rather its slightly strengthened form, weaker forms of PH2 and SH hold. Specifically, $p(k)$ (and hence s(k)) is $O(2^{\poly(h)})$. \end{prop} But this bound is very weak and conservative. In the strengthened form of PH1, it is required that the dimension as well as the bit size of each entry of the matrix $A$ in the specification $AX \le b$ of the polytope occuring in its statement is $O(\poly(h))$. \ignore{ \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 k_{\lambda,\mu}^\pi(n)$. This means $P$ is given by a linear system of the form \begin{equation} \label{eqpoly} A x \le b, \end{equation} where $A$ does not depend on $\lambda,\mu$ and $\pi$ and $b$ depends on $\lambda,\mu$ and $\pi$ in a homogeneous, linear fashion.) In particular, $k_{\lambda,\mu}^\pi=\tilde k_{\lambda,\mu}^\pi(1)$ is the number of integer points in $P$. \noindent (2) The dimension $m$ of the ambient space, and hence the dimension of $P$, and also the bitlength of every entry of the matrix $A$ in (\ref{eqpoly}) is polynomial in the heights of $\lambda,\mu$ and $\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, where $\bitlength{\lambda}$ denotes the bitlength of the specification of $\lambda$. 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} For the special case of the Kronecker problem considered in \cite{rosas}, i.e. when $n=2$, it is known \cite{GCT9} that PH1 holds. Hence, it follows from Theorem~\ref{tsh} that SH and PH2 also hold in this special case. } The following is a relaxed version of the Kronecker (decision) problem in \cite{GCT6}. \begin{problem} {\bf (Relaxed Kronecker Problem)} Given partitions $\lambda,\mu,\pi$ and a relaxation parameter $c > a{h^b}$, for the nonnegative constants $a$ and $b$ as in the statement of SH (Hypothesis~\ref{hsh}), decide whether $k_{c \lambda, c \mu}^{c \pi}$ is positive. \end{problem} \begin{theorem} \label{tkron} Assumming PH1 in \cite{GCT6} and SH here (Hypothesis~\ref{hsh}), the relaxed Kronecker problem can be solved in $\poly(\bitlength{\lambda},\bitlength{\mu},\bitlength(\pi),\bitlength{c})$ time, where $\bitlength{c}$ denotes the bitlength of $c$. In particular, if the relaxation parameter $c$ is small \footnote {In this statement it even suffices even if the bitlength of $c$, rather than its value, is $O(\poly(h))$}, i.e., $O(\poly(h))$, then the time is polynomial in the bitlengths of $\lambda,\mu$ and $\pi$. \end{theorem} This follows by a slight modification of the proof technique in \cite{GCT6}. The following is a relaxed form of the hypothesis PH3 in \cite{GCT6}. \begin{hypo} {\bf (PH3)} The rational function \[K(t)=K_{\lambda,\mu}^\pi(t)=\sum_{n\ge 0} \tilde k_{\lambda,\mu}^\pi(n) t^n\] can be expressed in a positive form: \begin{equation} K(t)=\f{h_d t^d +\cdots + h_0}{\prod_{i=0}^k (1-t^{a_i})^{d_i}}, \end{equation} where (1) $h_0=1$, and $h_i$'s are nonnegative integers, (2) $a_i$'s and $d_i$'s are positive integers, (3) $\sum_i d_i=d+1=O(\poly(h))$, where $d$ is the dimension of the polytope $P$ in PH1, and (4) the modular index of this positive form, defined to be $\max\{a_i\}$, is $O(\poly(h))$. \end{hypo} Here the positive form is not required to be reduced as in \cite{GCT6}; i.e. $a_0$ need not be $1$. It can be shown that PH3 implies SH and PH2. The hypotheses SH,PH2, and PH3 associated with other decision problems in \cite{GCT6} can be relaxed in a similar fashion, and analogues of Theorem~\ref{tkron} can be proven for the relaxed versions of those decision problems. SH and PH2 in \cite{GCT8} can also be relaxed similarly. These relaxations do not affect the overall GCT approach to the fundamental lower bound problems in complexity theory, such as the $P$ vs. $NP$ problem in characteristic zero. Because the final goal in GCT is to use the efficient algorithms for the decision problems such as the Kronecker problem above, or rather the structure of these algorithms, to show that, for every input size $n$, there exists an obstruction $O_n$ that serves as a ``proof-certificate'' or ``witness'' of hardness of the explicit function under consideration. When saturation only holds in a relaxed sense, the bit length of the label of this final obstruction $O_n$ would get multiplied by a small (polynomial) factor. But this small blow up does not affect the overall approach. The details of this relaxation would appear in the revised version of \cite{GCT6} under preparation. \begin{thebibliography}{[Welzl]} \bibitem[BOR]{rosas} E. Briand, R. Orellana, M. Rosas, Reduced Kronecker coefficients and counter-examples to Mulmuley's satuation conjecture SH, arXIv:0810.3163v1 [math.CO] 17 Oct, 2008. \ignore{%\bibitem[GCTflip1]{GCTflip1} K. Mulmuley, %On P. vs. NP, geometric complexity theory, and the flip I: a high-level %view, Technical Report TR-2007-13, Computer Science Department, %The University of Chicago, September 2007. %Available at: http://ramakrishnadas.cs.uchicago.edu \bibitem[GCT4]{GCT4} K. Mulmuley, M. Sohoni, Geometric complexity theory IV: quantum group for the Kronecker problem, cs. ArXiv preprint cs. CC/0703110, March, 2007. Available at: http://ramakrishnadas.cs.uchicago.edu } \bibitem[GCT6]{GCT6} K. Mulmuley, Geometric complexity theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry, Technical report TR 2007-04, Comp. Sci. Dept., The University of Chicago, May, 2007. Available at: http://ramakrishnadas.cs.uchicago.edu. Revised version to be available here. \bibitem[GCT7]{GCT7} K. Mulmuley, Geometric complexity theory VII: Nonstandard quantum group for the plethysm problem, cs. ArXiv preprint, arXiv:0709.0749v1, 1 Sept, 2008. \bibitem[GCT8]{GCT8} K. Mulmuley, Geometric complexity theory VIII: On canonical bases for the nonstandard quantum groups, cs. ArXiv preprint, arXiv:0709.0751v2, 1 Sept, 2008. \end{thebibliography} \end{document}