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