text:
\newcommand\calW{\mathscr W}
\newcommand\grn{\mathfrak n}
\newcommand\fin{\operatorname{fin}}
\newcommand\calA{\mathcal A}
\newcommand\calF{\mathcal F}
\newcommand\calG{\mathcal G}
\newcommand\IH{\operatorname{IH}}
\section{Introduction}

The main purpose of this paper is to describe the (equivariant) intersection cohomology of certain moduli spaces (``framed Uhlenbeck spaces")
together with some structures on them (such as e.g.\ the Poincar\'e pairing) in terms of representation theory of some vertex
operator algebras (``$\calW$-algebras"). In this introduction we first briefly introduce the relevant geometric and algebraic objects
(cf.\ Subsections \ref{int-geom} and \ref{int-alg}) and then state our main result (in a somewhat weak form) in Subsection \ref{int-main-local} (a more precise version is discussed in \ref{int-main-global}). In Subsection \ref{int-motiv} we discuss the motivation for our results and relate them to some previous works.

In \subsecref{int-tech} we mention earlier works from which we obtain
strategy and techniques of the proof.

\subsection{Uhlenbeck spaces}\label{int-geom}

Let $G$\index{G@$G$ (group)} be an almost simple simply-connected algebraic
group over $\CC$ with Lie algebra $\mathfrak g$. Let also $\mathfrak h$ be a Cartan subalgebra of $\mathfrak g$.

Let $\Bun{d}$\index{Bun@$\Bun{d}$} be the moduli space of algebraic
$G$-bundles over the projective plane $\proj^2$ (over $\mathbb C$)
with the instanton number $d$ and with trivialization at the line at
infinity $\linf$.\index{linfinity@$\linf$ (line at infinity)} It is a
non-empty smooth quasi-affine algebraic variety of dimension
$2dh^\vee$ for $d\in\Z_{\ge 0}$, where $h^\vee$ is the dual Coxeter
number of $G$.

By results of Donaldson \cite{MR763753} (when $G$ is classical) and
Bando \cite{Bando} (when $G$ is arbitrary) $\Bun{d}$ is homeomorphic
to the moduli space of anti-self-dual connections (instantons) on
$S^4$ modulo gauge transformations $\gamma$ with $\gamma(\infty) = 1$
where the structure group is the maximal compact subgroup of $G$.  We
will use an algebro-geometric framework, as we can use various tools.

It is well-known that $\Bun{d}$ has a natural partial compactification $\Uh{d}$\index{Uh@$\Uh{d}$}, called the Uhlenbeck space.
Set-theoretically, $\Uh{d}$ can be described as follows:
$$
\Uh{d}=\bigsqcup\limits_{0\leq d'\leq d}\Bun{d'}\times S^{d-d'}(\AA^2),
$$
where $S^{d-d'}(\AA^2)$ denotes the corresponding symmetric power of the affine plane $\AA^2$.

The variety $\Uh{d}$ is affine and it is always singular unless $d=0$. It has a natural action of the group $G\times GL(2)$, where
$G$ acts by changing the trivialization at $\linf$ and $GL(2)$ just acts on $\proj^2$ (preserving $\linf$). In what follows,
it will be convenient for us to restrict ourselves to the action of $\GG=G\times \CC^*\times \CC^*$ where $\CC^*\times \CC^*$ is the diagonal subgroup of $GL(2)$.

\subsection{Main geometric object}\label{int-ih}
The main object of our study on the geometric side is the
$\GG$-equivariant intersection cohomology
$\IH^*_{\GG}(\Uh{d})$.\index{IHG@$\IH^*_{\GG}(\Uh{d})$} By the
definition, it is endowed with the following structures:

\medskip
1) It is a module over $H^*_{\GG}(\mathrm{pt})$. The latter algebra can be canonically identified with the algebra of polynomial functions
on $\mathfrak h\times \CC^2$ which are invariant under $W$, where $W$ is the Weyl group of $G$. In what follows we shall denote this ring by $\bA_G$; let also $\bF_G$\index{FFG@$\bF_G = \CC(\ve_1,\ve_2,\ba)^W$} denote its field of fractions.
We shall typically denote an element of $\grh\times \CC^2$ by
$(\ba,\varepsilon_1,\varepsilon_2)$.

2) There exists a natural symmetric (Poincar\'e) pairing $\IH^*_{\GG}(\Uh{d})\underset {\bA_G}\otimes \IH^*_{\GG}(\Uh{d})\to \bF_G$
(this follows from the fact that $(\Uh{d})^{T\times \CC^2}$ consists of one point).

3) For every $d\geq 0$ we have a canonical unit cohomology class $|1^d\rangle\in \IH^*_{\GG}(\Uh{d})$.\index{1d@$\vert 1^d\rangle$}

\medskip
\noindent
The main purpose of this paper is to describe the above structures in terms of representation theory.
To formulate our results, we need to introduce the main algebraic player -- the $\calW$-algebra.

\subsection{Main algebraic object: $\calW$-algebras}\label{int-alg}
In this subsection we recall some basic facts and constructions from the theory of $\calW$-algebras (cf.\ \cite{F-BZ} and references therein). First, we need to recall the notion of Kostant-Whittaker reduction for finite-dimensional Lie algebras.

Let $\grg$ be as before a simple Lie algebra over $\CC$ with the universal enveloping algebra $U(\grg)$. Let us choose a triangular decomposition
$\grg=\grn_+\oplus\grh\oplus \grn_-$ for $\grg$. Let $\chi\colon\grn_+\to \CC$ be a non-degenerate character of $\grn_+$, i.e.\ a Lie algebra
homomorphism such that $\chi|_{\grn_{+,i}}\neq 0$ for every vertex $i$ of the Dynkin diagram of $\grg$ (here $\grn_{+,i}$ denotes the corresponding simple root subspace). Then we can define the finite $\calW$-algebra of $\grg$ (to be denoted by $\calW_{\fin}(\grg)$) as
the quantum Hamiltonian reduction of $U(\grg)$ with respect to $(\grn_+,\chi)$. In other words,
we have
$$
\calW_{\fin}(\grg)=\Hom_{U(\grg)}(U(\grg)\underset{U(\grn_+)}\otimes\CC_{\chi},U(\grg)\underset{U(\grn_+)}\otimes\CC_{\chi}).
$$

\noindent
A well-known theorem of Kostant asserts that

(1f) $\calW_{\fin}(\grg)$ is naturally isomorphic to the center ${\mathcal Z}(\grg)$ of $U(\grg)$.

In particular, we have

(2f) The algebra $\calW_{\fin}(\grg)$ has a natural embedding into $S(\grh)$, whose image coincides with the algebra
$S(\grh)^W$.

(3f) The algebra $\calW_{\fin}(\grg)$ is a polynomial algebra in some variables $F^{(1)},...,F^{(\ell)}$, where $\ell=\operatorname{rank}(\grg)$.
Each $F^{(\kappa)}$ is homogeneous as an element of $S(\grh)^W$ of some degree $d_{\kappa}+1\geq 2$.

(4f) The algebra $\calW_{\fin}(\grg)$ is isomorphic to the algebra $\calW_{\fin}(\grg^{\vee})$.

\noindent
Feigin and Frenkel (cf.\ \cite{F-BZ} and references therein) have generalized the above results to the case of affine Lie algebras.
Namely, let $\grg((t))$ denote the Lie algebra of $\grg$-valued formal loops.
It has a natural central extension
$$
0\to \CC\to \hat{\grg}\to\grg((t))\to 0
$$
(this extension depends on a choice of an invariant form on $\grg$ which we choose so that the the squared length of every short
coroot is equal to 2).
\begin{NB}
    Long roots have square length 2.
\end{NB}
The group $\CC^*$ acts naturally on $\hat{\grg}$ by ``loop rotation" and the same is true for its Lie algebra $\CC$.
We let $\grg_{\aff}$ be the semi-direct product of $\hat{\grg}$ and $\CC$ (for the above action).

For every $k\in \CC$ one can consider the algebra $U_k(\hat{\grg})$ --- this is the quotient of $U(\hat{\grg})$ by the ideal generated
by $\mathbf{1}-k$ where $\mathbf{1}$ denotes the generator of the central $\CC\subset \grg_{\aff}$.
Let us also extend $\chi$ to $\grn_+((t))$ by taking the composition of the residue map $\grn_+((t))\to \grn_+$ with $\chi:\grn_+\to \CC$. Abusing slightly the notation, we shall denote this map again by $\chi$.

The $\calW$-algebra $\calW_k(\grg)$\index{Wkg@$\scW_k(\g)$} is roughly
speaking the Hamiltonian reduction of $U_k(\hat{\grg})$ with respect
to $(\grn_+((t)),\chi)$.  However, the reader must be warned that
rigorously this reduction must be performed in the language of vertex
operator algebras; in particular, $\calW_k(\grg)$ is a vertex operator
algebra (cf.\ again \cite{F-BZ} for the relevant definitions).

Unlike in the finite case, the algebra $\calW_k(\grg)$ is usually non-commutative (unless $k=-h^{\vee}$).
The main results of Feigin and Frenkel about $\calW_k(\grg)$ can be summarized as follows (notice the similarities between
(1f)-(4f) and (1)-(4)):

\begin{Theorem}\label{FF-intro}\leavevmode
\begin{enumerate}
  \item
  The algebra $\calW_{-h^{\vee}}(\grg)$ can be naturally identified with the center of the \textup(vertex operator algebra version of\textup)
  $U_{-h^{\vee}}(\hat{\grg})$.
  \item
  Let $\Heis(\h)$ denote the central extension of $\grh((t))$ corresponding to the bilinear form on $\grh$ chosen above. Abusing the notation we shall use the same symbol for the corresponding vertex operator algebra. Also for any $k\in \CC$ we can consider the corresponding algebra $\Heis_k(\grh)$ \textup(``Heisenberg algebra of level $k$''\textup).\footnote{Note that for all $k\neq 0$ these algebras are isomorphic.}
  Then for generic $k$ there exists a canonical embedding $\calW_k(\grg)\hookrightarrow \Heis_{k+h^{\vee}}(\grh)$.
  \item
  The algebra $\calW_k(\grg)$ is generated \textup(in the sense of \cite[15.1.9]{F-BZ}\textup)
  by certain elements $W^{(\kappa)}$, $\kappa=1,\cdots,\ell$ of conformal dimension $d_\kappa+1$. This \textup(among other things\textup)
  means that for every module $M$ over $\calW_k(\grg)$ and every $\kappa=1,\ldots,\ell$ there is a well defined
  field $Y(W^{(\kappa)},z)=\sum\limits_{n\in \ZZ} W^{(\kappa)}_n z^{-n-d_{\kappa}-1}$ where $W^{(\kappa)}_n$ can be regarded as a linear endomorphism
  of $M$.
    \item Suppose $k$ is generic.  There is a natural isomorphism
  $\scW_k(\grg)\simeq \scW_{k^{\vee}}(\grg^{\vee})$ where
  $(k+h^{\vee}_{\grg})(k^{\vee}+h^{\vee}_{\grg^{\vee}})=r^{\vee}$
  where $r^{\vee}$ is the ``lacing number of $\grg$'' \textup(i.e.\ the
  maximal number of edges between two vertices of the Dynkin diagram
  of $\grg$\textup). We shall call this isomorphism ``the
  Feigin-Frenkel duality".

  \end{enumerate}
  \end{Theorem}

The representation theory of $\scW_k(\grg)$ has been extensively studied (cf.\ for example \cite{Arakawa2007}).
In particular, to any $\lambda\in\mathfrak h^*$ one can attach a Verma module $M(\lambda)$\index{Mlambda@$M(\lambda)$} over $\calW_k(\grg)$ and $M(\lambda_1)$ is isomorphic to $M(\lambda_2)$ if $\lambda_1+\rho$ and $\lambda_2+\rho$ are on the same orbit of the Weyl group. This module carries
a natural (Kac-Shapovalov) bilinear form, with respect to which the  operator $W^{(\kappa)}_n$ is conjugate to $W^{(\kappa)}_{-n}$ (up to sign).
This module can be obtained as the Hamiltonian reduction of the corresponding Verma module for $\grg$.

\subsection{The main result: localized form}\label{int-main-local}
Let us set
$$
M^d_{\bF_G}(\ba)=\IH^*_{\GG}(\Uh{d})\underset {\bA_G}\otimes \bF_G;\quad M_{\bF_G}(\ba)=\bigoplus\limits_{d=0}^{\infty} M^d_{\bF_G}(\ba).
\index{MFG@$M_{\bF_G}(\ba)$}
$$
It is easy to see that $M^d_{\bF_G}(\ba)$ is also naturally isomorphic to  $\IH^*_{\GG,c}(\Uh{d})\underset{\bA_G}\otimes\bF_G$ where the subscript
$_c$ stands for cohomology with compact support.

Let us also set
$$
k=-h^{\vee}-\frac{\ve_2}{\ve_1}.
$$

Then (a somewhat weakened) form of our main result is the following:

\begin{Theorem}\label{main-intro-loc}
Assume that $G$ is simply laced and let us identify $\grh$ with $\grh^*$ by means of the invariant form such that $(\alp,\alp)=2$ for
every root of $\grg$. Then
there exists an action
of the algebra $\calW_k(\grg)$ on $M_{\bF_G}(\ba)$ such that
\begin{enumerate}
  \item
  The resulting module is isomorphic to the Verma module $M(\lambda)$ over $\calW_k(\grg)$ where
  $$
  \lambda=\frac{\ba}{\ve_1}-\rho
  $$
  \textup(here we take $\bF_T =
  \operatorname{Frac}(H^*_T(\mathrm{pt}))$\index{FFT@$\bF_T = \CC(\ve_1,\ve_2,\ba)$|textit} as our field of
  scalars\textup).
    \item Under the above identification a twisted Poincar\'e pairing
  on $M_{\bF_G}(\ba)$ goes over to the Kac-Shapovalov form on
  $M(\lambda)$.  \textup(The twisting will be explained in
  \subsecref{sec:kac-shapovalov-form}.\textup)
  \begin{NB}
      Corrected on Sep.~14, 2014
  \end{NB}
  \item
  Under the above identification the grading by $d$ corresponds to the grading by eigenvalues of $L_0$.
  \item
  Let $d\ge 1$, $n > 0$. We have
\begin{equation}\label{eq:Whittaker-intro}
  W^{(\kappa)}_n |1^d\rangle =
  \begin{cases}
     \pm \ve_1^{-1}\ve_2^{-h^{\vee}+1}|1^{d-1}\rangle &
    \text{if $\kappa=\ell$ and $n=1$},
    \\
    0 & \text{otherwise}.
  \end{cases}
\end{equation}

\end{enumerate}

\end{Theorem}
\noindent
{\bf Remarks.} 1) We believe that the sign in (\ref{eq:Whittaker-intro}) is actually always $``+"$, however, currently we don't know how to eliminate the sign issue. Note, however, that (\ref{eq:Whittaker-intro}) still defines the scalar product $\langle 1^d|1^d\rangle$
unambiguously. Also (assuming that the above sign issue can be settled) it follows from (\ref{eq:Whittaker-intro}) that if we formally
set $w=\sum_d |1^d\rangle$ then we have
$$
W^{(\kappa)}_n (w) =
  \begin{cases}
   \ve_1^{-1}\ve_2^{-h^{\vee}+1} w &
    \text{if $\kappa=\ell$ and $n=1$},
    \\
    0 & \text{otherwise}.
\end{cases}
$$

Sometimes we shall write $w_{\ba,\ve_1,\ve_2}$ to emphasize the dependence on the corresponding parameters.

2) The assumption that $G$ is simply laced is essential for Theorem \ref{main-intro-loc} to hold as stated. However, we believe that
a certain modified version of Theorem \ref{main-intro-loc} holds in the non-simply laced case as well, although at the moment we don't
 have a proof of this modified statement (cf.\ subsection \ref{non-simply-laced} for a brief discussion of the non-simply laced case).

3) Since $\Uh{d}$ is acted on by the full $GL(2)$ and not just by $\CC^*\times \CC^*$, it follows that the vector space $M_{\bF_G}(\ba)$ has a natural automorphism which induces the involution $\ve_1\leftrightarrow \ve_2$ on $\bF$ (and leaves $\ba$ untouched).
Note that changing $\ve_1$ to $\ve_2$ amounts to changing $k=-h^{\vee}-\frac{\ve_2}{\ve_1}$ to $k^{\vee}=-h^{\vee}-\frac{\ve_1}{\ve_2}$
and we have $(k+h^{\vee})(k^{\vee}+h^{\vee})=1$. Note also that we are assuming that $\grg$ is simply laced, so
$\grg$ is isomorphic to $\grg^{\vee}$ and the above geometrically defined automorphism is in fact a corollary of the Feigin-Frenkel duality (cf.\ Theorem \ref{FF-intro}).

\begin{NB}

\subsection{Relation to previous works}\label{int-motivNB}
There are several motivations for the above result. One comes from the so called Alday-Gaiotto-Tachikawa conjecture (cf.\ \cite{AGT} for $G=SL(2)$ and \cite{ABCDEFG} for general $G$) in mathematical physics, which claims certain duality between $N=2$ super-symmetric gauge theory on ${\mathbb R}^4$
and the 2-dimensional Toda conformal field theory. Theorem \ref{main-intro-loc} might probably be viewed as a mathematical corollary of that physical conjecture, although we are not aware of a reference with the physical derivation of something like \ref{main-intro-loc}. However, it is worthwhile to note that the pairing $\langle 1^d|1^d\rangle$ is sometimes called ``the equivariant integral of 1 over $\Uh{d}$"
and their generating function
\begin{equation}
Z(Q,\ba,\ve_1,\ve_2)=\sum\limits_{d=0}^{\infty} Q^d \langle 1^d|1^d\rangle
\end{equation}
is called ``the instanton part of the Nekrasov partition function for pure $N=2$ gauge theory".
It follows from \ref{main-intro-loc} that
$$
Z(Q,\ba,\ve_1,\ve_2)=\langle Q^{-L_0} w_{\ba,\ve_1,\ve_2}|w_{\ba,\ve_1,\ve_2}\rangle.
$$
This statement appears as a conjecture in \cite{Gaiotto} for $G=SL(2)$ and in \cite{ABCDEFG} for general $G$.

In addition, there are now many purely mathematical results in the spirit of Theorem \ref{main-intro-loc}. First, the fact that the character of  $M_{\bF_G}(\ba)$ is equal to the character of a Verma module over $\calW_k(\grg)$ follows from the main result of
\cite{BFG}. In addition, the paper \cite{BraInstantonCountingI} by the first-named author contains a result, which is very similar to Theorem \ref{main-intro-loc} (but technically much simpler). Namely, in the situation of {\em loc. cit.} on the representation theory side one deals with the affine
Lie algebra $\grg_{\aff}$ instead of the corresponding $W$-algebra, and on the geometric side one needs to replace the Uhlenbeck
spaces $\Uh{d}$ by certain {\em flag Uhlenbeck spaces}. In fact, it is important to note that when the original group $G$ is not simply laced, the main result of \cite{BraInstantonCountingI} relates the equivariant intersection cohomology of the flag Uhlenbeck spaces for
the group $G$ with the representation theory of the affine Lie algebra $\grg_{\aff}^{\vee}$, whose root system is dual to that
of $\grg_{\aff}$. A somewhat simpler construction exists also for the finite-dimensional Lie algebra $\grg^{\vee}$ -- in that case on the geometric side one has to work with the so called space of {\em based quasi-maps into the flag variety of $\grg$}, also known as Zastava
spaces (cf.\ \cite{Bra-icm} for a survey on these spaces). In \cite{BFFR} a similar result is conjectured (and proved in type A) for
{\em finite $W$-algebras} for $\grg^{\vee}$ (in that case on the geometric side one works with the so called parabolic Zastava spaces - cf.\ again \cite{Bra-icm} for the relevant definitions).

Last but not least we must mention the fundamental work \cite{MO}, which contains (among many other things) a result which is essentially
equivalent to Theorem \ref{main-intro-loc} in the case when $G=SL(r)$. More precisely, when $G=SL(r)$, the Uhlenbeck spaces $\Uh{d}$ have a natural semi-small symplectic resolution $\Gi{r}^d\to \Uh{d}$; here $\Gi{r}^d$ is the moduli space of torsion-free sheaves
on $\proj^2$ together with a trivialization at $\proj^1_{\infty}$ of generic rank $r$ and of second Chern class $r$.
The authors of \cite{MO} work with the equivariant cohomology of $\Gi{r}^d$ rather than with equivariant intersection cohomology
of $\Uh{d}$, which is slightly bigger. As a result on the representation theory side they get a Verma module over
$\calW(\gl_r)$ (this algebra is isomorphic to the tensor product of $\calW(\mathfrak{s}\mathfrak{l}_r)$
with a (rank 1) Heisenberg algebra). We should also mention that we use the construction of \cite{MO} for $r=2$ in a crucial way for the proof of Theorem \ref{main-intro-loc}.

Let us also mention the work \cite{SV}
where the authors prove a result similar to the above result of \cite{MO} by a different method.
\end{NB}

\subsection{Relation to previous works}\label{int-motiv}

We discuss previous works related to the above result here and later
in \subsecref{int-tech}. This subsection is devoted for those works
related to statements themselves, and \subsecref{int-tech} is for
those which give us a strategy and techniques of the proof.

\begin{NB}
    I do not refer any physical papers earlier than AGT, nor even
    mention there are.
\end{NB}

First we discuss the statements (1),(2),(3).

There are many previous works in almost the same pattern: We consider
moduli spaces of instantons or variants on complex surfaces, and their
homology groups or similar theory.

Then some algebras similar to affine Lie algebras act on direct sums
of homology groups, where we sum over various Chern classes.

The first example of such a result was given by the third-named author
\cite{Na-quiver,Na-alg}. The $4$-manifold is $\CC^2/\Gamma$ for a
nontrivial finite subgroup $\Gamma\subset SU(2)$, and the gauge group
is $U(r)$. The direct sum of homology groups of symplectic resolutions
of Uhlenbeck spaces, called {\it quiver varieties\/} in more general
context, is an integrable representation of the affine Lie algebra
$\mathfrak g_{\Gamma,\aff}$ of level $r$.

Here $\mathfrak g_\Gamma$ is a simple Lie algebra of type $ADE$
corresponding to $\Gamma$ via the McKay correspondence, and
$\mathfrak g_{\Gamma,\aff}$ is its affine Lie algebra.

This result nicely fitted with the $S$-duality conjecture on the
modular invariance of the partition function of $4d$ $N=4$
supersymmetric gauge theory by Vafa-Witten \cite{Vafa-Witten}, as
characters of integrable representations are modular forms.

It was understood that the correspondence \cite{Na-quiver,Na-alg}
should be understood in the framework of a duality in string theories
\cite{Vafa2}. There are lots of subsequent developments in physics
literature since then.

In mathematics, the case $\Gamma = \{e\}$ was subsequently treated by
\cite{MR1441880} and Grojnowski \cite{Grojnowski} for $r=1$, and by
Baranovsky \cite{Baranovsky} for general $r$. The corresponding
$\mathfrak g_{\Gamma,\aff}$ is the Heisenberg algebra, i.e., the
affine Lie algebra associated with the trivial Lie algebra $\gl_1$, in
this case.

For $\Gamma=\{e\}$, the symplectic resolution $\Gi{r}^d\to
\Uh{d}$\index{UhTilder@$\Gi{r}^d$} of the Uhlenbeck space $\Uh{d}$ is
given by the moduli space of torsion-free sheaves on $\proj^2$
together with a trivialization at $\linf$ of generic rank
$r$ and of second Chern class $d$. We call it {\it the Gieseker
  space\/} in this paper.

For general $\Gamma$, we have its variant. All have description
in terms of representations of quivers by variants of the ADHM
description, and hence are examples of quiver varieties.

\begin{NB}
    The integrable representation becomes irreducible if we only take
    middle degree homology groups (for $\Gamma\neq\{e\}$).
\end{NB}

This result was extended to an action of the quantum toroidal algebra
$\mathbf U_q(\mathbf L\mathfrak g_{\Gamma,\aff})$ on the equivariant
K-theory of the moduli spaces when $\Gamma\neq\{e\}$
\cite{Na-qaff,MR1989196}. A variant for equivariant homology groups
was given by Varagnolo \cite{Varagnolo}.

In all these works, the action was given by introducing
correspondences in products of moduli spaces, which give generators of
the algebra. In particular, the constructions depend on {\it good\/}
presentations of algebras.

The case $\Gamma=\{e\}$ was studied much later, as we explain below,
as the corresponding algebra, which would be $\mathbf U_q(\mathbf
L({\gl}_1)_{\aff})$, was considerably more difficult.

\begin{NB}
    Misha, I add your result.
\end{NB}

Let us also mention that the second-named author with Kuznetsov
\cite{MR1799936} constructed an action of the affine Lie algebra
$\widehat{\gl}_r$ on the homology group of moduli spaces of parabolic
sheaves on a surface, called {\it flag Gieseker spaces\/} or {\it
  affine Laumon spaces\/} when the surface is $\proj^2$, the parabolic
structure is put on a line and the framing is added. (Strictly
speaking, the action was constructed on the homology group of the
fibers of morphisms from flag Gieseker spaces to flag Uhlenbeck
spaces. The action for the whole variety is constructed much later by
Negut \cite{Negut} in the equivariant K-theory framework.)

Let us turn to works on the inner product $\la 1^d|1^d\ra$, which
motivate the statement (4). It is given by the equivariant integration
of $1$ over $\Uh{d}$, and their generating function
\begin{equation}\label{Nekrasov function}
   Z(Q,\ba,\ve_1,\ve_2)=\sum\limits_{d=0}^{\infty} Q^d \langle 1^d|1^d\rangle
\end{equation}
is called ``the instanton part of the Nekrasov partition function for
pure $N=2$ supersymmetric gauge theory" \cite{Nekrasov}.

This partition function has been studied intensively in both
mathematical and physical literature. In particular, a result, which
is very similar to Theorem~\ref{main-intro-loc}(1)$\sim$(4) (but
technically much simpler) was proved by the first-named author
\cite{BraInstantonCountingI}. Namely, in the situation of
\cite{BraInstantonCountingI} on the representation theory side one
deals with the affine Lie algebra $\grg_{\aff}$ instead of the
corresponding $\scW$-algebra, and on the geometric side one needs to
replace the Uhlenbeck spaces $\Uh{d}$ by
{\em flag Uhlenbeck spaces} $\calZ^{\alp}_G$\index{ZalphaG@$\calZ^\alpha_G$}.
In fact, it is important to note that when the original
group $G$ is not simply laced, the main result of
\cite{BraInstantonCountingI} relates the equivariant intersection
cohomology of the flag Uhlenbeck spaces for the group $G$ with the
representation theory of the affine Lie algebra $\grg_{\aff}^{\vee}$,
whose root system is dual to that of $\grg_{\aff}$.
A somewhat simpler construction exists also for the finite-dimensional Lie algebra $\grg^{\vee}$ -- in that case on the geometric side one has to work with the so called space of {\em based quasi-maps into the flag variety of $\grg$}, also known as Zastava
spaces (cf.\ \cite{Bra-icm} for a survey on these spaces).
\begin{NB}
    \cite{BFFR} = [BFFR] is later than \cite{AGT} = [AGT]. Therefore
    this part should be moved later, I think.
\end{NB}

The Nekrasov partition functions are equal for $\Uh{d}$ and for flag
Uhlenbeck spaces at $\ve_2 = 0$, and it is enough for some purposes,
say to determine Seiberg-Witten curves, but they are different in
general. Therefore it was clear that we must replace
$\grg_{\aff}^\vee$ by something else, but we did not know what it is.

A breakthrough was given in a physics context by
Alday-Gaiotto-Tachikawa \cite{AGT} (AGT for short). They conjectured
that the partition functions for $G=SL(2)$ with four fundamental
matters and adjoint matters are conformal blocks of the Virasoro
algebra.

They provided enough mathematically rigorous evidences, say numerical
checks for small instanton numbers, and also physical intuition that
this correspondence is coming from an observation that $N=2$ $4d$
gauge theories are obtained by compactifying the underlying $6d$
theory on a Riemann surface.

They also guessed that the Virasoro algebra is replaced by the
$\scW$-algebra for a group $G$ of type $ADE$.

There is a large literature in physics after AGT, especially for type
$A$. We do not give the list, though those works are implicitly
related to ours. We mention only one which was most relevant for us,
it is \cite{ABCDEFG} by Keller et al, where the statement (4) was
written down for the first time for general $G$. (There is an earlier
work by Gaiotto for $G=SL(2)$ \cite{Gaiotto}, and various others for
classical groups.)

Around the same time when \cite{AGT} appeared in a physics context,
there was an independent advance on the understanding of the algebra
$\mathbf U_q(\mathbf L({\gl}_1)_{\aff})$ acting on the K-theory of
resolutions of Uhlenbeck spaces of type $A$ by Feigin-Tsymbaliuk
\cite{MR2854154} and Schiffmann-Vasserot \cite{MR3018956}. They
noticed that that $\mathbf U_q(\mathbf L({\gl}_1)_{\aff})$ is
isomorphic to various algebras, which had been studied in different
contexts: a Ding-Iohara algebra, a shuffle algebra with the wheel
conditions, the Hall algebra for elliptic curves, and an algebra
studied by Miki \cite{MR2377852}.

Combined with the AGT picture, we understand that $\mathbf U_q(\mathbf
L({\gl}_1)_{\aff})$ is the limit of the deformed $\scW(\algsl_r)$, or
$\scW(\gl_r)$ by the reason explained below, when $r\to\infty$.

In \cite{BFFR} a similar result is conjectured (and proved in type A) for
{\em finite $W$-algebras} associated with a nilpotent element $e\in \grg^{\vee}$, which is principal in some Levi subalgebra (in that case on the geometric side one works with the so called parabolic Zastava spaces - cf. \cite{Bra-icm} for the relevant definitions).

Finally Maulik-Okounkov \cite{MO} and Schiffmann-Vasserot \cite{SV} proved
Theorem~\ref{main-intro-loc} in the case when $G=SL(r)$.

More precisely, they work with the equivariant cohomology of
$\Gi{r}^d$ rather than with equivariant intersection cohomology of
$\Uh{d}$, which is slightly bigger. As a result on the representation
theory side they get a Verma module over $\calW(\gl_r)$ (this algebra
is isomorphic to the tensor product of
$\calW(\mathfrak{s}\mathfrak{l}_r)$ with a (rank 1) Heisenberg
algebra). We should also mention that we use the construction of
\cite{MO} for $r=2$ in a crucial way for the proof of Theorem
\ref{main-intro-loc}.

\subsection{Hyperbolic restriction}
One of the main technical tools used in the proof of Theorem~\ref{main-intro-loc} is the notion of {\em hyperbolic restriction}.
Let us recall the general definition of this notion.

Let $X$ be an algebraic variety endowed with an action of $\CC^*$. Then $X^{\CC^*}$ is a closed subvariety of $X$.
Let $\calA_X$ denote the corresponding attracting set. Let $i\colon X^{\CC^*}\to\calA_X$ and $j\colon \calA_X\to X$ be the natural embeddings.
Then we have the functor $\Phi=i^*j^!$\index{UZphi@$\Phi$ (hyperbolic restriction functor)} from the derived category of constructible sheaves on $X$ to the derived
category of constructible sheaves on $X^{\CC^*}$. This functor has been extensively studied by
Braden in \cite{Braden}. In particular, the main result of \cite{Braden} says that $\Phi$ preserves the semi-simplicities of complexes.

Assume that we have a symplectic resolution $\pi\colon Y\to X$ in the sense of \cite{MO} and assume in addition that the above $\CC^*$-action
lifts to $Y$ preserving the symplectic structure. Let $\calF=\pi_*\CC_Y[\dim X]$ (where $\CC_Y$  denotes the constant sheaf
on $Y$). Then we have
\begin{Theorem}\label{nakajima-symplectic}
    \begin{enumerate}
          \item \cite{VV2}
        $\Phi(\calF)$ is isomorphic to $\pi_*\CC_{Y^{\CC^*}}[\dim X^{\CC^*}]$.
          \item Maulik-Okounkov's stable envelop \cite{MO} gives us a
        choice of an isomorphism in \textup{(1)}.
    \end{enumerate}

\end{Theorem}

See \cite{tensor2} for the proof. Though both $\Phi(\calF)$ and
$\pi_*\CC_{Y^{\CC^*}}[\dim X^{\CC^*}]$ are isomorphic semi-simple
perverse sheaves, the proof of \cite{VV2} only gives us a canonical
filtration on the former whose associated graded is canonically
isomorphic to the latter. Then the stable envelop \cite{MO} gives us a
choice of a splitting.

Now we specialize the above discussion to the following situation. Let $P\subset G$ be a parabolic subgroup of $G$ with Levi subgroup $L$. Let us choose a subgroup $\CC^*\subset Z(L)$ (here $Z(L)$ stands for the center of $L$) such that the fixed point set of its adjoint action on $P$ is $L$ and the attracting set is equal to all of $P$. Let now $X=\Uh{d}$. We denote by $\UhL{d}$ the fixed point set of
the above $\CC^*$ on $\Uh{d}$ and by $\UhP{d}$ the corresponding attracting set.
It is easy to see that if $L$ is not a torus, then $\UhL{d}$ is just homeomorphic to ${\mathcal U}_{[L,L]}^d$ (and if $L$ is a torus, then
$\UhL{d}$ is just $S^d(\CC^2)$).
 Often we are going to drop the instanton number $d$ from
the notation, when there is no fear of confusion. We let
$i$\index{i@$i$ (inclusion $\UhL{d}\to\UhP{d}$)} and $p$\index{p@$p$
  (projection $\UhP{d}\to\UhL{d}$)} denote the corresponding maps from
$\UhL{}$ to $\UhP{}$ and from $\UhP{}$ to $\UhL{}$. Also we denote by
$j$\index{j@$j$ (inclusion $\UhP{d}\to \Uh{d}$)} the embedding of
$\UhP{}$ to $\Uh{}$. We have the
diagram
\begin{equation}
    \label{eq:1intro}
    \UhL{} \overset{p}{\underset{i}{\leftrightarrows}}
    \UhP{} \overset{j}{\rightarrow} \Uh{},
\end{equation}

Thus we can consider the corresponding hyperbolic restriction functor
$\Phi_{L,G}=i^* j^!$\index{UZphiLG@$\Phi_{L,G}$} (note that the functor actually depends on $P$ and not just on $L$, but it is easy to see that it doesn't
depend on the choice of $\CC^*\subset Z(L)$ made above).

The following is one of the main technical results used in the proof of Theorem~\ref{main-intro-loc}:
\begin{Theorem}\label{perverse-intro}
\begin{enumerate}
  \item
  Let $P_1\subset P_2$ be two parabolic subgroups and let $L_1\subset L_2$ be the corresponding Levi subgroups. Then
  we have a natural isomorphism of functors $\Phi_{L_1,G}\simeq \Phi_{L_1,L_2}\circ \Phi_{L_2,G}$.
  \item
  For $P$ and $L$ as above the complex $\Phi_{L,G}(\IC(\Uh{d}))$ is perverse and semi-simple.
  Moreover, the same is true for any semi-simple perverse sheaf on $\Uh{d}$ which is constructible with respect to the natural stratification.
\end{enumerate}
\end{Theorem}
Note that when $G=SL(r)$, it is easy to deduce Theorem~\ref{perverse-intro} from \thmref{nakajima-symplectic}(1), since in this case
the scheme $\Uh{d}$ has a symplectic resolution $\Gi{r}^d$.

\subsection{Sketch of the proof}\label{sketch}
The proof of Theorem \ref{main-intro-loc} will follow the following plan:

1) Replace $\GG=G\times \CC^*\times \CC^*$-equivariant cohomology with $\TT=T\times \CC^*\times \CC^*$-equivariant cohomology.
Note that the former is just equal to the space of $W$-invariants in the latter, so if we define an action
of $\calW_k(\grg)$ on $\oplus \IH^*_{\TT}(\Uh{d})\underset {\bA_T}\otimes \bF_T$
\index{IHT@$\IH^*_{\TT}(\Uh{d})$}
(where $\bA_T=H^*_{T\times \CC^*\times \CC^*}(\mathrm{pt})$
and $\bF_T$ is its field of fractions) and check that if commutes with the action of $W$, we get an action of $\calW_k(\grg)$ on
$\oplus_d \IH^*_{\GG}(\Uh{d})\underset {\bA_G}\otimes \bF_G$.

2) We are going to construct an action of $\Heis_{k+h^{\vee}}(\grh)$ on $\oplus_d \IH^*_{\TT}(\Uh{d})\underset {\bA_T}\otimes \bF_T$
and then get the action of $\calW_k(\grg)$ by using the embedding $\calW_k(\grg)\hookrightarrow \Heis_{k+h^{\vee}}(\grh)$.
It should be noted that the above $\Heis_{k+h^{\vee}}(\grh)$-action will have several ``disadvantages" that will disappear
when we restrict ourselves to $\calW_k(\grg)$. For example, this action will depend on a certain auxiliary choice (a choice of a Weyl
chamber).
\begin{NB}
I do not agree with this.

Also it will not have any nice compatibility properties with the Poincar\'e pairing on $\oplus_d \IH^*_{\TT}(\Uh{d})\underset {\bA_T}\otimes \bF_T$.
\end{NB}

3) The action of the Heisenberg algebra on $\oplus_d \IH^*_{\TT}(\Uh{d})\underset {\bA_T}\otimes \bF_T$ will be constructed
in the following way. Let us choose a Borel subgroup $B$ containing the chosen maximal torus $T$.
We can identify $\oplus_d \IH^*_{\TT}(\Uh{d})\underset {\bA_T}\otimes \bF_T$ with $\oplus_d H^*_{\TT}\Phi_{T,G}(\IC(\Uh{d}))\underset {\bA_T}\otimes \bF_T$, so it is enough to define an action of the Heisenberg algebra on the latter. For this it is enough to define
the action of $\Heis(\CC\alp_i^{\vee})$ for every simple coroot $\alp_i^{\vee}$ of $G$ (and then check the corresponding relations).
Let $P_i$ denote the corresponding sub-minimal parabolic subgroup containing $B$.
Let also $L_i$ be its Levi subgroup (it is canonical after the choice of $T$). Note that $[L_i,L_i]\simeq SL(2)$.
Using the isomorphism
$\Phi_{T,G}(\IC(\Uh{d}))\simeq \Phi_{T,L_i}\circ\Phi_{L_i,G}(\IC(\Uh{d}))$ and Theorem~\ref{nakajima-symplectic}, we define
the action of $\Heis(\CC\alp_i^{\vee})$ on $\oplus_d H^*_{\TT}\Phi_{T,G}(\IC(\Uh{d}))\underset {\bA_T}\otimes \bF_T$ using the results
of \cite{MO} for $G=SL(2)$.

Here it is important for us to write down $\Phi_{L_i,G}(\IC(\Uh{d}))$
in terms of $\IC(\Uh[L_i]{d'})$ ($d'\le d$) and local systems on
symmetric products in a `canonical' way.

In particular, we need to construct a base in the multiplicity space of
$\IC(\Uh[L_i]{d'})$ in $\Phi_{L_i,G}(\IC(\Uh{d}))$.

For $G=SL(r)$, this follows from the stable envelop, thanks to
Theorem~\ref{nakajima-symplectic}(2).

For general $G$, this argument does not work, and we use the
factorization property of Uhlenbeck spaces together with the special
case $G=SL(2)$. A further detail is too complicated to be explained in
Introduction, so we ask an interested reader to proceed to the main text.

4) We now need to check the relations between various $\Heis(\CC\alp_i^{\vee})$. For this we have two proofs. One reduces it again to
the results of
\cite{MO} for $G=SL(3)$ (note that since we assume that $G$ is simply laced, any connected rank 2 subdiagram of the Dynkin diagram of $G$ is of type $A_2$). The other goes through the theory of certain ``geometric" $R$-matrices (cf.\  Section \ref{sec:R-matrix}).
The proof of assertions (2) and (3) of Theorem~\ref{main-intro-loc} is more or less straightforward. The proof of assertion (4) is more technical and we are not going to discuss it in the Introduction. Let us just mention that for that proof we need a stronger form of the first 3 statements of Theorem~\ref{main-intro-loc} which is briefly discussed below.

\subsection{Relation to previous works -- technical parts}\label{int-tech}

Let us mention previous works which give us a strategy and techniques of the proof.

First of all, we should mention that the overall framework of the
proof is the same as those in \cite{MO,SV}. We realize the
Feigin-Frenkel embedding of $\scW_k(\mathfrak g)$ into
$\Heis_{k+h^\vee}(\mathfrak h)$ in a geometric way via the fixed point
$(\Uh{d})^{\CC^*} = \Uh[L]{d}$,

as is explained the geometric realization in 3),4) in
\subsecref{sketch}.

This was first used in \cite{MO,SV} for type $A$.

What we do here is to replace the equivariant homology of Gieseker
spaces $\Gi{r}^d$ by intersection cohomology of $\Uh{d}$ as the former
exists only in type $A$.

Various foundational issues were discussed in the joint work of the
first and second-named authors with Gaitsgory \cite{BFG}.

In particular, the fact that the character of $M_{\bF_G}(\ba)$ is
equal to the character of a Verma module over $\calW_k(\grg)$ follows
from the main result of \cite{BFG}.

(For type A, it was done earlier in the joint work of the third-named
author with Yoshioka. See \cite[Exercise~5.15]{Lecture} and its
solution in \cite{MR2095899}.)

A search of a replacement of Maulik-Okounkov's stable envelop
\cite{MO} was initiated by the third-named author \cite{tensor2}.

In particular, the relevance of the hyperbolic restriction functor
$\Phi$ and the statement \thmref{nakajima-symplectic}(2) were found.

Therefore our technical aim is to find a `canonical' isomorphism
between $\Phi_{L,G}(\IC(\Uh{d}))$ and a certain perverse sheaf on $\Uh[L]d$.

Let us also mention that \thmref{nakajima-symplectic}(1) was proved
much earlier by Varagnolo-Vasserot \cite{VV2} in their study of quiver
varieties. The functor $\Phi$ realized tensor products of
representations of $\mathfrak g_{\Gamma,\aff}$.  (Strictly speaking,
only quiver varieties of finite types were considered in \cite{VV2}. A
slight complication occurs for quiver varieties of affine types which
give $\mathfrak g_{\Gamma,\aff}$. See \cite[Remark~1]{tensor2} for
detail.)

When we do not have a symplectic resolution like $\Gi{d}^r$, we need another tool to analyze $\Phi$.

Fortunately the hyperbolic restriction functor was studied by
Mirkovi\'c-Vilonen \cite{MV,MV2} in the context of the geometric
Satake isomorphism, which asserts the category of
$G(\CC[[t]])$-equivariant perverse sheaves on the affine Grassmannian
$\operatorname{Gr}_G = G(\CC((t)))/G(\CC[[t]])$ is equivalent to the
category of finite dimensional representations of the Langlands dual
$G^\vee$ of $G$ as tensor categories.

The hyperbolic restriction functor realizes the restriction from
$G^\vee$ to its Levi subgroup.

In particular, it was proved that $\Phi$ sends perverse sheaves to
perverse sheaves. This was proved by estimating dimension of certain
subvarieties of $\operatorname{Gr}_G$, now called Mirkovi\'c-Vilonen
cycles. The proof of \thmref{perverse-intro} is given in the same
manner, replacing Mirkovi\'c-Vilonen cycles by attracting sets of the
$\CC^*$-action.

It is clear that we should mimic the geometric Satake isomorphism from
the conjecture of the first and second-named authors
\cite{braverman-2007} which roughly says the following: it is
difficult to make sense of perverse sheaves on the double affine
Grassmannian, i.e., the affine Grassmannian
$\operatorname{Gr}_{G_{\aff}}$ for the affine Kac-Moody group
$G_{\aff}$. But perverse sheaves on $\Uh{d}$ (and more generally
instanton moduli spaces on $\CC^2/\Gamma$ with $\Gamma = \ZZ/k\ZZ$)
serve as their substitute. Then they control the representation theory
of $G_{\aff}^\vee$ at level $k$.

This conjecture nicely fits with the third-named author's works
\cite{Na-quiver,Na-alg} on quiver varieties via I.~Frenkel's
level-rank duality for the affine Lie algebra of type $A$
\cite{MR675108}. Namely in the correspondence between moduli spaces
and representation theory, the gauge group determines the rank, and
$\Gamma$ the level respectively in the double affine Grassmannian. And
the role is reversed in quiver varieties.

In \cite{BF2}, the first and second-named authors proposed a functor,
acting on perverse sheaves, which conjecturally gives tensor products
of $G_{\aff}^\vee$. This proposal was checked in \cite{Na-branching}
for type $A$, by observing that the same functor gives the branching
from $\mathfrak g_{\Gamma,\aff}$ to the affine Lie algebra of a Levi
subalgebra. The interchange of tensor products and branching is
again compatible with the level-rank duality.

Here in this paper, tensor products and branching appear in the
opposite side: The hyperbolic restriction functor $\Phi$ realizes the
tensor product in the quiver variety side, as we mentioned
above. Therefore it should correspond to branching in the dual affine
Grassmannian side. This is a philosophical explanation why the study of
analog of Mirkovi\'c-Vilonen cycles is relevant here.

\subsection{The main result: integral form}\label{int-main-global}
The formulation of Theorem~\ref{main-intro-loc} has an obvious drawback: it is only formulated in terms
of {\em localized} equivariant cohomology.

\begin{NB}
I do not agree:

     In fact, localization with respect to $\ba$ is not very essential,
but
\end{NB}
First of all,
it is clear that as stated Theorem~\ref{main-intro-loc} only has a chance to work over
the the localized field $\bF=\CC(\ve_1,\ve_2)$
\index{FF@$\bF = \CC(\ve_1,\ve_2)$|textit}
rather than over $\bA=\CC[\ve_1,\ve_2]$.
\index{AA@$\bA = \CC[\ve_1,\ve_2]$|textit}

The reason is that our formula for the level
$k=-h^{\vee}-\frac{\ve_2}{\ve_1}$ and the highest weight $\lambda =
\frac{\ba}{\ve_1} - \rho$ are not elements of $\bA$.
\begin{NB}
However, for many purposes,
\end{NB}
For many purposes, it is convenient to have an $\bA$-version of
Theorem~\ref{main-intro-loc}. In fact, technically in order to prove
the last assertion of Theorem~\ref{main-intro-loc} we need such a
refinement of the first 3 assertions (the reason is that we need to
use the cohomological grading which is lost after localization).

In earlier works \cite{MO,SV} for type $A$, the $\bA$-version appears
only implicitly, as operators $\W{\kappa}{n}$ are given by cup
products on Gieseker spaces. But in our case, Uhlenbeck spaces are
singular, and we need to work with intersection cohomology groups. Hence
$\W{\kappa}n$ do not have such descriptions.

So, in order to formulate a non-localized version of Theorem~\ref{main-intro-loc} one needs to define
an $\bA$-version $\calW_{\bA}(\grg)$
\index{WAg@$\scW_\bA(\g)$|textit}
of the $\calW$-algebra (such that after tensoring with $\bF$ we get the algebra
$\calW_k(\grg)$ with $k=-h^{\vee}-\frac{\ve_2}{\ve_1}$). We also want this algebra to be graded (such that
the degrees of $\ve_1$ and $\ve_2$ are equal to 2); in addition we need analogs of statements (2) and (3) of
Theorem~\ref{FF-intro}. This is performed in the Appendix B. Let us note, that although this $\bA$-form is motivated by geometry, it can be defined
purely in an algebraic way, following the work of Feigin and Frenkel.

As far as we know, this $\bA$-form does not appear in the literature before.

As a purely algebraic application, we can remove the genericity
assumption in \thmref{FF-intro}(4). The third named author learns from
Arakawa that this was known to him before, but the proof is not written.

After this we prove an  $\bA$-version of Theorem~\ref{main-intro-loc} in Section \ref{sec:whittaker-state}.

The non-localized equivariant cohomology groups also give us a refined
structure in our construction. We construct $\scW_\bA(\g)$-module
structures on four modules
\begin{multline*}
    \bigoplus_d \IH^*_{\GG,c}(\Uh{d}), \quad
    \bigoplus_d H^*_{\TT,c}(\Phi_{T,G}(\IC(\Uh{d})))
\\
    \bigoplus_d H^*_{\TT}(\Phi_{T,G}(\IC(\Uh{d}))), \quad
    \bigoplus_d \IH^*_{\GG}(\Uh{d}),
\end{multline*}
where the subscript $c$ stands for cohomology with compact support.

They become isomorphic if we take tensor products with $\bF_T$, i.e.,
in the localized equivariant cohomology. But they are different over
$\bA_G$ and $\bA_T$.

We show that they are {\it universal\/} Verma, Wakimoto modules
$M_\bA(\ba)$\index{MA@$M_\bA(\ba)$|textit},
$N_\bA(\ba)$\index{NA@$N_\bA(\ba)$|textit},
and
their duals respectively.

Here by a Wakimoto module, we mean the pull-back of a Fock space via the embedding of $\scW(\g)$ in $\Heis(\mathfrak h)$.

They are universal in the sense that we can specialize to Verma/Wakimoto and their duals at any evaluation $\bA_G\to\CC$, $\bA_T\to\CC$.

This will be important for us to derive character formulas for simple
modules, which will be discussed in a separate publication.

The importance of the integral form and the application to character
formulas were first noticed in the context of the equivariant K-theory
of the Steinberg variety and the affine Hecke algebra (see \cite{CG}),
and then in quiver varieties \cite{Na-qaff} and parabolic Laumon spaces (=
handsaw quiver varieties) \cite{handsaw}.

\subsection{Remarks about non-simply laced case}\label{non-simply-laced}
We have already mentioned above that verbatim Theorem~\ref{main-intro-loc} doesn't hold for non-simply laced $G$.
However, we expect that the following modification of Theorem \ref{main-intro-loc} should hold.

First, let $\calG$ be any affine Lie algebra in the sense of \cite{Kac} with connected Dynkin diagram.
For example, $\calG$ can be untwisted, and in this case it is isomorphic to a Lie algebra of the form $\grg_{\aff}$ for some
simple finite-dimensional Lie algebra. But in addition there exist twisted affine Lie algebras. We refer the reader to
\cite{Kac} for the relevant definitions; let us just mention that every twisted $\calG$ comes from a pair $(\calG',\sigma)$
where $\calG'=\grg_{\aff}$ for some simply laced simple finite-dimensional Lie algebra $\grg$ and $\sigma$ is a certain automorphism of
$\grg$ of finite order.

The Dynkin diagram of $\calG$ comes equipped with a special ``affine" vertex. We let $G_{\calG}$ denote the semi-simple and simply connected group whose Dynkin diagram is obtained from that of $\calG$ by removing that vertex.

To such an algebra one can attach another affine Lie algebra $\calG^{\vee}$ ---
``the Langlands dual Lie algebra". By definition, this is just the Lie algebra whose generalized Cartan matrix is transposed to that of $\calG$. It is worthwhile to note that:

1) If $\grg$ is a simply laced finite-dimensional simple Lie algebra, then $\grg_{\aff}^{\vee}$ is isomorphic to $\grg_{\aff}$ (which
is also the same as $(\grg^{\vee})_{\aff}$ in this case).

2) In general, if $\grg$ is not simply laced, then $\grg_{\aff}^{\vee}$ is not isomorphic to $(\grg^{\vee})_{\aff}$. In fact, if $\grg$
is not simply laced, then $\grg_{\aff}^{\vee}$ is always a twisted Lie algebra.

It turns our that one can define the Uhlenbeck spaces $\mathcal U^d_{\calG}$ for any affine Lie algebra $\calG$ in such a way that
that $\mathcal U^d_{\calG}=\Uh{d}$ when $\calG=\grg_{\aff}$ and $\grg=\operatorname{Lie}(G)$ (the definition uses the corresponding simply laced
algebra $\grg$ and its automorphism $\sigma$ mentioned above). We are not going to explain the definition here
(we shall postpone it for a later publication). This scheme is endowed with an action of the group $G_{\calG}\times \CC^*\times \CC^*$.

In addition to $\calG$ as above one can also attach a $W$-algebra $\calW(\calG)$. Then we expect the following to be true:
\begin{Conjecture}\label{non-simp}
There exists an action of $\calW(\calG)$ on $\oplus \IH^*_{G(\calG^{\vee})\times \CC^*\times \CC^*}(\mathcal U_{\calG^{\vee}}^d)$ satisfying properties similar to those of Theorem~\ref{main-intro-loc}.
\end{Conjecture}

Let us discuss one curious corollary of the above conjecture. Let $\grg$ be a finite-dimensional simple Lie algebra.
Set $\calG_1=\grg_{\aff}^{\vee}, \calG_2=(\grg^{\vee})_{\aff}^{\vee}$. Then Conjecture \ref{non-simp} together with Feigin-Frenkel
duality imply that there should be an isomorphism between $\IH^*_{G(\calG_1)\times \CC^*\times \CC^*}(\mathcal U_{\calG_1}^d)$
and
$\IH^*_{G(\calG_2)\times \CC^*\times \CC^*}(\mathcal U_{\calG_2}^d)$ which sends $\frac{\ve_2}{\ve_1}$ and to $r^{\vee}\frac
{\ve_1}{\ve_2}$.
It would be interesting to see whether this isomorphism can be constructed geometrically (let us note that the naive guess
that
there exists an isomorphism between $\mathcal U_{\calG_1}^d$ and $\mathcal U_{\calG_2}^d$ giving rise to the above isomorphism between
$\IH^*_{G(\calG_1)\times \CC^*\times \CC^*}(\mathcal U_{\calG_1}^d)$
and
$\IH^*_{G(\calG_2)\times \CC^*\times \CC^*}(\mathcal U_{\calG_2}^d)$ is probably wrong).
This question might be related to the work \cite{Vafa} where the author explains how to derive
the 4-dimensional Montonen-Olive duality for non-simply laced groups from 6-dimensional (2,0) theory.

\subsection{Further questions and open problems}
In this subsection we indicate some possible directions for future research on the subject (apart from generalizing everything
to the non-simply laced case, which was discussed before).

\subsubsection{VOA structure and CFT}
Our results imply that the space $M_{\bF_G}(\ba)$ has a natural vertex operator algebra structure. It would be extremely interesting
to construct this structure geometrically.

The AGT conjecture predicts a duality between $N=2$ $4d$ gauge
theories and $2d$ conformal field theories (CFT). The equivariant
intersection cohomology group $M_{\bF_G}(\ba)$ is just the quantum
Hilbert space associated with $S^1$, appeared as a boundary of a
Riemann surface. We should further explore the $4d$ gauge theory from
CFT perspective, as almost nothing is known so far.

\subsubsection{Gauge theories with matter}
Our results give a representation-theoretic interpretation of the Nekrasov partition function of the {\em pure} $N=2$ super-symmetric
gauge theory on $\RR^4$. For physical reasons it is also interesting to study gauge theories with matter. Mathematically it usually means that in the definition of the partition function (\ref{Nekrasov function}) one should replace the equivariant integral of 1 by the equivariant integral of some other (intersection) cohomology class. However, when $G$ is not of type $A$ even the definition of
the partition function is not clear to us. Namely, for $G=SL(r)$ one usually works with the Gieseker space $\Gi{r}^d$ instead
of $\Uh{d}$. In this case the cohomology classes in question are usually defined as Chern classes of certain natural sheaves
$\Gi{r}^d$ (such as, for example, the tangent sheaf). Since $\Uh{d}$ is singular and we work with {\em intersection cohomology}
such constructions don't literally make sense for $\Uh{d}$.

\subsubsection{The case of $\mathbb C^2/\Gamma$}It would be interesting to try and generalize our results to Uhlenbeck space
of $\mathbb C^2/\Gamma$. Here we expect the case when $\Gamma$ is a cyclic group to be more accessible than the general case;
in fact, in this case one should be able to see connections with  \cite{braverman-2007},\cite{BF2} and on the other hand with
\cite{2011JHEP...07..079B,2013CMaPh.319..269B}.

On the other hand the theory of quiver varieties deals with general
$\Gamma$, but the group $G$ is of type $A$, as we mentioned in \subsecref{int-motiv}.

The case when both $\Gamma$ and $G$ are not of type $A$ seems more
difficult. Note that we must impose $\ve_1=\ve_2$, therefore the level
$k = -h^\vee - \ve_2/\ve_1$ cannot be deformed. In particular, the
would-be $\scr W$-algebra does not have a classical limit.

\subsubsection{Surface operators}

As we have already mentioned in \subsecref{int-motiv}, there are {\it
  flag Uhlenbeck spaces\/} parametrizing (generalized) $G$-bundles on
$\proj^2$ with parabolic structure on the line $\proj^1$. A type of
parabolic structure corresponds to a parabolic subgroup $P$ of $G$.

Generalizing results in two extreme cases, $P=B$ in
\cite{BraInstantonCountingI} and $P=G$ in this paper, it is expected
that the equivariant intersection cohomology group admits a
representation of the $\scr W$-algebra associated with the principal
nilpotent element in the Lie algebra $\mathfrak l$ of the Levi part of
$P$. (We assume $G$ is of type $ADE$, and the issue of Langlands
duality does not occur, for brevity.) This is an affine version of the conjecture in \cite{BFFR} mentioned before.

Moduli of $G$-bundles with parabolic structure of type $P$ is called a
surface operator of Levi type $\mathfrak l$ in the context of $N=4$
supersymmetric gauge theory \cite{MR2459305}.

However there is a surface operator corresponding to
{\it arbitrary\/} nilpotent element $e$ in $\operatorname{Lie}G$
proposed in \cite{MR3027737}, which is supposed to have the symmetry
of $\scr W(\g,e)$, the $\scr W$-algebra associated with $e$. We do not understand what kind of parabolic structures nor equivariant intersection cohomology groups we should consider if $e$ is not regular in Levi.

\subsection{Organization of the paper}
In Section \ref{sec:preliminaries}  we discuss some generalities about Uhlenbeck spaces. Section \ref{sec:local}
is devoted to the general discussion of hyperbolic restriction
and Section \ref{sec:hyper-uhlenbeck} ---
to hyperbolic restriction on Uhlenbeck spaces. In Section \ref{sec:typeA} we relate the constructions and results of Section \ref{sec:hyper-uhlenbeck} to certain
constructions of \cite{MO} in the case when $G$ is of type $A$. Section \ref{sec:w-algebra-repr} is devoted to the construction of the action of the algebra $\calW_k(\grg)$ on $M_{\bF_G}(\ba)$
along the lines presented above. Section \ref{sec:R-matrix} is devoted to the discussion of ``geometric $R$-matrices".
\subsection{Some notational conventions}\label{sec:convent}

\begin{enumerate}
  \renewcommand{\theenumi}{\roman{enumi}}
  \renewcommand{\labelenumi}{\textup{(\theenumi)}}

\item A partition $\lambda$ is a nonincreasing sequence
  $\lambda_1\ge\lambda_2\ge \cdots$ of nonnegative integers with
  $\lambda_N = 0$ for sufficiently large $N$. We set $|\lambda| = \sum
  \lambda_i$, $l(\lambda) = \# \{ i \mid \lambda_i \neq 0\}$. We also
  write $\lambda = (1^{n_1} 2^{n_2}\cdots)$ with $n_k = \# \{ i\mid
  \lambda_i = k\}$.

    \item The equivariant cohomology group $H^*_\GG(\mathrm{pt})$ of a
  point is canonically identified with the ring of invariant
  polynomials on the Lie algebra $\operatorname{Lie}\GG$ of $\GG$. The
  coordinate functions for the two factors $\CC^*$ are denoted by
  $\ve_1$, $\ve_2$ respectively. We identify the ring of invariant
  polynomials on $\g = \operatorname{Lie}G$ with the ring of the Weyl
  group invariant polynomials on the Cartan subalgebra $\h$ of $\g$.

  When we consider the simple root $\alpha_i$ as
  a polynomial on $\h$, we denote it by $a^i$.

    \item For a variety $X$, let $D^b(X)$ denote the bounded derived
  category of complexes of constructible $\CC$-sheaves on $X$.

  Let $\IC(X_0,\mathcal L)$ denote the intersection cohomology complex
  associated with a local system $\mathcal L$ over a Zariski open
  subvariety $X_0$ in the smooth locus of $X$. We denote it also by
  $\IC(X)$ if $\mathcal L$ is trivial.

  When $X$ is smooth and irreducible, $\cC_X$\index{CCX@$\cC_X$}
  denotes the constant sheaf on $X$ shifted by $\dim X$. If $X$ is a
  disjoint union of irreducible smooth varieties $X_\alpha$, we
  understand $\cC_X$ as the direct sum of $\cC_{X_\alpha}$.

\item\label{conv2} We make a preferred degree shift for the
  Borel-Moore homology group (with complex coefficients), and denote
  it by $H_{[*]}(X)$\index{HstarX@$H_{[*]}(X)$}. The shift is coming
  from a related perverse sheaf, which is clear from the context.

  For example, if $X$ is smooth, $\cC_X$ is a perverse sheaf. Hence
  $H_{[*]}(X) = H_{*+\dim X}(X)$ is a natural degree shift, as it is
  isomorphic to $H^{-*}(X, \cC_X)$.

  More generally, if $L$ is a closed subvariety in a smooth variety
  $X$, we consider $H_{[*]}(L) = H_{*+\dim X}(L) = H^{-*}(L,j^!
  \cC_X)$, where $j\colon L\to X$ is the inclusion.

\item We use the ADHM description of framed torsion free sheaves on
  $\proj^2$ at several places. We change the notation $(B_1,B_2,i,j)$
  in \cite[Ch.~2]{Lecture} to $(B_1,B_2,I,J)$ as $i$, $j$ are used for
  different things.
\end{enumerate}

\subsection{Acknowledgments}

We dedicate this paper to the memory of Kentaro Nagao, who passed away
on Oct. 22, 2013. His enthusiasm to mathematics did not stop until the
end, even under a very difficult health condition. H.N.\ enjoyed
discussions on results in this paper, and other mathematics with him
last summer.

It is clear that this paper owes a lot to earlier works by D.~Maulik,
A.~Okounkov, O.~Schiffmann and E.~Vasserot. The authors thank them for
their patient explanation on the works.

A.B. is grateful to D.~Gaitsgory for very helpful discussions related to Appendix A as well as with the proof of
Theorem \ref{thm:nonlocal}.

H.N.\ thanks to Y.~Tachikawa who explained physical intuition to him,
and to T.~Arakawa, R.~Kodera and S.~Yanagida who taught him various
things on $\scW$-algebras.

This work was started at 2012 fall, while H.N.\ was visiting the
Simons Center for Geometry and Physics, and he wishes to thank the
Center for warm hospitality. We thank the Abdus Salam International
Centre for Theoretical Physics, the Euler International Mathematical
Institute, the Higher School of Economics, Independent University of
Moscow, where we continued the discussion.

A.B.\ was partially supported by the NSF grant DMS-1200807 and by the Simons foundation.
Also this work was completed when A.B. was visiting the New Economic School of Russia and the Mathematics
Department of the Higher School of Economics and he would like to thank those institutions for their hospitality.

M.F.\ was supported by The National Research
University Higher School of Economics Academic Fund Program in 2014/2015
(research grant No. 14-01-0047).

The research of H.N.\ was supported in part by JSPS Kakenhi Grant
Numbers 00201666, 25220701, 30165261, 70191062.


TITLE: Is it possible to reflect over non-linear functions like quadratics or cubics?
QUESTION [2 upvotes]: This is a problem I have been investing for a while now and I have come up with several ideas. For the purpose of simplicity I am taking $y=x^2$ as my example and reflecting $y=0$ over it.

Take the tangent of certain points on $x^2$ and relate the distance from the tangent to $y=0$ to the reflection of the point over $y=x^2$ (might be a bit confusing)
Take the square root of the quadratic to linearize it then reflect the line over linear function and square it afterwards. Because the quadratic is symmetrical both sides will be the same.
Try to derive a common equation using a similar method to what is shown here except for a quadratic https://www.slideshare.net/hcr1991/reflection-of-a-point-about-a-line-a-plane-in-2d-3d-space-geometry-by-hcr

REPLY [1 votes]: When a point "looks" in a direction perpendicular to the curved "mirror" it should "see" it's image directly in front of it, at a distance twice the distance to the "mirror" in that direction.
More formally, given a point $p$ we would like to reflect, any point $q$ on the reflection curve $\Gamma$ for which our given point has a perpendicular displacement $q-p \perp T_\Gamma(q)$ to should reflect $p$ to $p + 2(q-p)$ which is equal to $2q-p$.
$$ R_\Gamma: p \mapsto \left\{ 2q-p \ \big | \ q\in\Gamma, \ q-p \perp T_\Gamma(q)\right\}$$
When $\Gamma$ is a line, there is a unique $q$ for each $p$ such that $q-p \perp T_\Gamma(q)$, so $R_\Gamma$ is a function. This is no longer true for general curves, hence the need for set notation.
To find that set, note that for a parameterization $\gamma(t)$ of $\Gamma$, we have $T_\Gamma(q)$ is parallel to $\gamma'(t)$ whenever $q = \gamma(t)$, so you can solve
$$ (\gamma(t)-p)\cdot\gamma'(t) = 0 $$
for $t$ in terms of $p$ and evaluate $\gamma$ there to get $q$. If we call the set of solutions $T$ then we have
$$R_\Gamma(p) = \left\{ 2\gamma(\tau(p)) - p \ \big | \ \tau \in T \right\}$$

As an example, take the parabola defined by $y = x^2$. We can parameterize this so that $\gamma(t) = (t,t^2)$ and $\Gamma = \gamma(\Bbb{R})$. Note that $\gamma'(t) = (1,2t)$. Now for a given $p = (p_x,p_y)\in\Bbb{R}$, we have
$$ (\gamma(t) - p)\cdot\gamma'(t) = (t-p_x,t^2-p_y)\cdot(1,2t) = t-p_x + 2t^3 - 2tp_y $$
In general, this vanishes for one or three (real) values of $t$, so we'll call the one guaranteed to be real $\tau_0(p)$ and the other two $\tau_+(p)$ and $\tau_-(p)$. Let $U$ be the region where $\tau_\pm\in\Bbb{R}$, so by the cubic discriminant
$$ U = \left\{(x,y)\in\Bbb{R}^2 \ \Bigg | \ 4 y \geq 3\sqrt[3]{2x^2} + 2 \right\} $$
and let $V = \Bbb{R}^2 - U$. Note that in $U$, we may have $\tau_+ = \tau_-$ or possibly $\tau_\pm = \tau_0$, while in $V$ we always have exactly one real root $\tau_0$ of multiplicity $1$.
Then, the restriction of $R_\Gamma$ to $V$ is a function, and
$$R_\Gamma|_V(p) = 2\gamma(\tau_0(p)) - p$$
Without the restriction, we don't have a function, but we do have
$$R_\Gamma(p) = \left\{ 2\gamma(\tau(p)) - p \ | \ \tau \in \{\tau_0,\tau_+,\tau_-\} \right\}$$
however writing these explicitly means writing $\tau(p)$ explicitly, which are the roots of a cubic polynomial, and therefore somewhat messy to write out.
If I pick a particularly easy to work with kind of point, where $p_x = 0$ and $p_y = v \leq \frac{1}{2}$, then we have $T = \{ 0 \}$, $\gamma(\tau_0((0,v))) = (0,0)$, and so
$$ R_\Gamma((0,v)) = 2(0,0) - (0,v) = (0,-v) $$
which is just reflection over the $y$-axis.
For a slightly more interesting one, we'll take $p_y = \frac{1}{2}$ and $p_x = 2u^3$ can be anything. Then, $T = \{ u \}$, $\gamma(\tau_0((2u^3,\frac{1}{2})) = (u,u^2)$, so then
$$ R_\Gamma\left(\left(2u^3,\frac{1}{2}\right)\right) = 2\left(u,u^2\right) - \left(2u^3,\frac{1}{2}\right) = \left(2u-2u^3,2u^2 - \frac{1}{2}\right) $$
Any more interesting than that and the formulas get too messy for me to want to work with, but the framework is all here, so you are welcome to do that yourself.


TITLE: Solving Weird Logarithms without a Calculator
QUESTION [2 upvotes]: Given "$x = \log 8$", it is very easy to rewrite the expression as "$10^x = 8$", which cannot easily be solved for by hand. However, if I plug "$x = \log 8$" into my calculator, I get "$x = 0.903089986992$".
So How Does It Know?
Is there some sort of logarithmic formula implemented by calculators, or does it really just brute-force the value for all of those decimal places?
Note:
I develop apps as a hobby, so if said formula involves loops or binary-operators, don't feel overly pressured to explain how they work; I already understand them.

REPLY [1 votes]: As pointed out in the comments, it probably uses the Taylor Series, which gives us $$
\ln(1+x)=\sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} x^n = x - \frac{x^2}{2} + \frac{x^3}{3} - \cdots
$$
However, more insightful answers are given here.


text:
\subsection{Graphs with restrictions on $K_{2,\gamma+1}$'s}\label{ssec:acyclic-gamma}

We prove Theorem~\ref{thm:gamma} by contradiction. Suppose there
exists a graph $G \in {\cal K}_\gamma$ with maximum degree $\Delta$
such that $\chi_a(G) > \nbmaxcolgamma$. We define an algorithm that
``tries'' to acyclically color $G$ with $\kappa = \nbmaxcolgamma$
colors. Define a total order $\prec$ on the vertices of $G$.

\subsubsection{The algorithm}

Let $V\in\set{1,2,\ldots,\kappa}^t$ be a vector of length $t$, for some
arbitrarily large $t \gg n=|V(G)|$. Algorithm~\acm (see
\vpageref[below]{algo:acm}) takes the
vector $V$ as input and returns a partial acyclic coloring $\varphi :
V(G) \to \set{\bullet,1,2,\ldots,\kappa}$ of $G$ ($\bullet$ means that
the vertex is uncolored) and a text file $R$ that is called a
\emph{record} in the remaining of the paper. The acyclic coloring
$\varphi$ is necessarily partial since we try to color $G$ with a
number of colors less than its acyclic chromatic number.
For a given vertex $v$ of $G$, we denote by $N(v)$ the set of
neighbors of $v$.

\begin{algorithm}
  \DontPrintSemicolon
  \LinesNumbered

  \SetKwInOut{Input}{Input}
  \SetKwInOut{Output}{Output}
  \Input{$V$ (vector of length $t$).}
  \Output{($\varphi$, $R$).\vspace{.2cm}}

  \For{ all $v$ in $V(G)$}{
    $\varphi(v)\gets \bullet$
  }
  $R\gets newfile()$

  \For{$i\gets 1$ \KwTo $t$}{

    Let $v$ be the smallest (w.r.t. $\prec$) uncolored vertex of $G$

    $\varphi(v) \gets V[i]$

    Write "\texttt{Color $\backslash$n}" in $R$

    \If{$\varphi(v)=\varphi(u)$ \rm{for} $u\in N(v)$}
    {
      \tcp{Proper coloring issue}
      $\varphi(v) \gets \bullet$

      Write "\texttt{Uncolor, neighbor $u\ \backslash$n}" in $R$

    }
    \ElseIf{$v$ belongs to a bicolored cycle of length $2k$ ($k\ge 2$), say $(v=u_1,\ldots,u_{2k})$}
    {
      \tcp{Bicolored cycle issue}

      \For{$j\gets 1$ \KwTo $2k-2$}{ $\varphi(u_j) \gets \bullet$ }
      Write "\texttt{Uncolor, $2k$-cycle $(v=u_1,\ldots,u_{2k})\
        \backslash$n}" in $R$ } } \Return ($\varphi$, $R$)
  \caption{\acm\label{algo:acm}}
\end{algorithm}

Algorithm \acm runs as follows. Let $\varphi_i$ be the partial
coloring of $G$ after $i$ steps (at the end of the $i^{\rm th}$ loop).
At Step $i$, we first consider $\varphi_{i-1}$ and we color the
smallest uncolored vertex $v$ with $V[i]$ (line 6 of
the algorithm).  We then verify whether one of the
following types bad events happens:

\begin{enumerate}[Event 1:]
\item $G$ contains a monochromatic edge $vu$ for some $u$ (line 8 of the
  algorithm) ;
\item[Event $k$:] $G$ contains a bicolored cycle of length $2k$
  $(v=u_1,u_2,\ldots,u_{2k})$ (line 11 of the algorithm).
\end{enumerate}

If such events happen, then we uncolor some vertices (including $v$) in
order that none of the two previous events remains.
Clearly, $\varphi_i$ is a partial acyclic coloring of $G$. Indeed,
since Event~1 is avoided, $\varphi_i$ is a proper coloring and since
Event~2 is avoided, $\varphi_i$ is acyclic.

\bigskip
\begin{proofof}{Theorem~\ref{thm:gamma}}
  Let us first note that the function defined by Algorithm \acm is
  injective. This comes from the fact that from each output of the
  algorithm, one can determine the corresponding input by
  Lemma~\ref{lem:vo2}.
  Now we obtain a contradiction by showing that the number of possible
  outputs is strictly smaller than the number of possible inputs when
  $t$ is chosen large enough. The number of possible
  inputs is exactly $\kappa^t$ while the number of possible outputs is
  $\smallO{\kappa^t}$, as it is at most $(1+\kappa)^n\times
  \smallO{\kappa^t}$. Indeed, there are at most $(1+\kappa)^n$ possible
  partial $\kappa$-colorings of $G$ and there are at most
  $\smallO{\kappa^t}$ possible records by Lemma~\ref{lem:r2}. Therefore,
  assuming the existence of a counterexample $G$ leads us to a
  contradiction. That concludes the proof of Theorem~\ref{thm:gamma}.
\end{proofof}

\subsubsection{Algorithm analysis}

Recall that $\varphi_i$ denotes the partial acyclic coloring obtained
after $i$ steps. Let us denote by $\ovphi_i \subset V(G)$ the set of
vertices that are colored in $\varphi_i$. Let also $v_i$, $R_i$ and
$V_i$ respectively denote the current vertex $v$ of the $i^{\rm th}$
step, the record $R$ after $i$ steps, and the input vector $V$
restricted to its $i$ first elements.  Observe that as $\varphi_i$ is
a partial acyclic $\kappa$-coloring of $G$, and as $G$ is not acyclically
$\kappa$-colorable, we have that $\ovphi_i \subsetneq V(G)$, and thus
$v_{i+1}$ is well defined. This also implies that $R$ has $t$
\algo{Color} lines. Finally observe that $R_i$ corresponds to the lines
of $R$ before the $(i+1)^{\rm th}$ \algo{Color} line.

\begin{lemma}\label{lem:vo2}
  One can recover $V_i$ from $(\varphi_i,R_i)$.
\end{lemma}

\begin{proof} By induction on $i$. Trivially, $V_0$ (which is empty)
  can be recovered from $(\varphi_0,R_0)$.  Consider now
  $(\varphi_i,R_i)$ and let us try to recover $V_i$. It is thus
  sufficient to recover $R_{i-1}$, $\varphi_{i-1}$, and $V[i]$.  As
  observed before, to recover $R_{i-1}$ from $R_i$ it is sufficient to
  consider the lines before the last (i.e. the $i^{\rm th}$)
  \algo{Color} line.  Then reading $R_{i-1}$, one can easily recover
  $\ovphi_{i-1}$ and deduce $v_i$.  Note that in the $i^{\rm th}$ step
  we wrote one or two lines in the record: exactly one \algo{Color}
  line followed by either nothing, or one \algo{Uncolor, neighbor}
  line, or one \algo{Uncolor, $2k$-cycle} line. Indeed there cannot be an
  \algo{Uncolor, $2k$-cycle} line following an \algo{Uncolor, neighbor}
  line, as $v$ would be uncolored by the algorithm before considering
  bicolored cycles passing through $v$. Let us
  consider these three cases separately.

  \begin{itemize}
  \item If Step $i$ was a color step alone, then $V[i]
    = \varphi_i(v_i)$ and $\varphi_{i-1}$ is obtained from $\varphi_i$
    by uncoloring $v_i$.

  \item If the last line of $R_i$ is \algo{Uncolor, neighbor $u$},
    then $V[i] = \varphi_i(u)$ and $\varphi_{i-1} = \varphi_i$.

  \item If the last line of $R_i$ is \algo{Uncolor, $2k$-cycle $(u_1,\ldots
      ,u_{2k})$}, then $V[i]=\varphi_i(u_{2k-1})$ and $\varphi_{i-1}$ is
    obtained from $\varphi_i$ by coloring the vertices $u_j$ for $2\le
    j\le 2k-2$ (which were uncolored in $\varphi_i$), in such a way
    that $\varphi_{i-1}(u_j)$ equals $\varphi_i(u_{2k-1})$ if $j \equiv
    1\mod 2$, or equals $\varphi_i(u_{2k})$ otherwise. Note that this is
    possible because in the $i^{\rm th}$ loop, the algorithm uncolored
    neither $u_{2k-1}$ nor $u_{2k}$.

  \end{itemize}
  This concludes the proof of the lemma.
\end{proof}

Let us now bound the number of possible records.

\begin{lemma}\label{lem:r2}
  Algorithm~\acm produces at most $\smallO{\kappa^t}$ distinct
  records~$R$.
\end{lemma}

\begin{proof}
  Since Algorithm \acm fails to color $G$, the record $R$ has exactly
  $t$ \algo{Color} lines (i.e. the algorithm consumes the whole input
  vector). It contains also \algo{Uncolor} lines of different types:
  \algo{neighbor} (type 1), \algo{$4$-cycle} (type 2),
  \algo{$6$-cycle} (type 3), \dots \algo{$n$-cycle} (type $\frac
  n2$).
  Let $\type=\set{1,2,\ldots,\frac n2}$ be the set of bad event types.
  Let denote $s_j$ the number of uncolored vertices when a bad event
  of type $j$ occurs. Observe that:
  \begin{itemize}
  \item For every \algo{Uncolor, neighbor} step, the algorithm uncolors
    1 previously colored vertex. Hence set $s_1=1$.
  \item For every \algo{Uncolor, $2k$-cycle} step, where the cycle has length
    $2k$, the algorithm uncolors $2k-2$ previously colored vertices. Hence
    set $s_k=2k-2$ for $2\le k \le {\floor {n/2}}$.
  \end{itemize}

  To compute the total number of possible records, let us compute how
  many different entries, denoted $C_j$, an \algo{Uncolor} step of type
  $j$ can produce in the record.  Observe that:
  \begin{itemize}

  \item An \algo{Uncolor, neighbor} line can produce $\Delta$ different
    entries in the record, according to the neighbor of $v$ (the
    vertex just
    colored by the algorithm) that shares the same color. Hence set $C_1=\Delta$.

  \item An \algo{Uncolor, $2k$-cycle} line involving a cycle of length $2k$
    can produce as many different entries in the record as the number of
    $2k$-cycles going through $v$. Thus this number of entries is at
    most $\frac12 \gamma \Delta^{2k-2}$ according to Lemma 3.2 of
    \cite{AMR91}. Hence set $C_k=\frac12 \gamma \Delta^{2k-2}$ for $2\le
    k \le {\floor {n/2}}$.
  \end{itemize}

  We complete the proof by means of
  Theorem~\ref{thm:nb_of_rec} of Section~\ref{sec:general} (see
  \vpageref[below]{thm:nb_of_rec}). Theorem~\ref{thm:nb_of_rec} applies
  on Algorithm~\gc which is a generic version of Algorithm~\acm.
  Consequently, let us consider the following polynomial $Q(x)$:
  \begin{eqnarray*}
    Q(x) &=& 1+ \sum_{i\in\type} C_i x^{s_i}\\
         &=&1+\Delta x + \sum_{2\le i\le\frac n2}\frac12 \gamma \Delta^{2i-2}x^{2i-2}\\
         &<&1+\Delta x + \frac{\gamma\Delta^2x^2}{2-2\Delta^2x^2} \qquad\qquad \;
             \mbox{for} \;
             x<\frac 1\Delta
  \end{eqnarray*}
  Setting $X =
  \frac{1}{\Delta}\sqrt{\frac{2}{\gamma+2}}$, we have:
  $$
  \frac{Q(X)}{X}  < \Delta \sqrt{\frac{\gamma+2}{2}}\left(1+ \sqrt{\frac{2}{\gamma+2}}
    +1\right) = \Delta \left(1+\sqrt{2\gamma+4} \right) \le \kappa
  $$

  Since $\gamma\ge 1$, then $\frac2{\gamma+2}<1$ and thus we have $0< X <
  \frac1\Delta \le 1$. Therefore, Algorithm \acm produces at most
  $o(\kappa^t)$ different records by Theorem~\ref{thm:nb_of_rec}.  This completes the proof.
\end{proof}

config: arxiv


TITLE: Abstract notion for energy complexity of computational problems?
QUESTION [3 upvotes]: Energy is very valuable computational resource especially in mobile computing. Optimizing the energy consumed during the execution of algorithms has significant practical implications. Intuitively, It seems that such abstract energy measure has to be correlated to the time complexity, the space complexity, and the frequency of space (memory) access operations. Communications costs should be accounted for if we consider distributed computing model.

Are there abstract notions of energy (possibly analogous to the action quantity in physics) which could be useful for establishing energy-complexity classes for computational problems?

This is a follow-up to  this question on SE TCS

REPLY [2 votes]: Yes, DJ Bernstein has a big rant which shows up (for example) in his work on integer factorization circuits.  He goes a bit further than "energy" and discusses assigning a cost in dollars to a computation (in terms of the hardware needed, etc).  He uses this measure to evaluate various trade-offs in serial vs. parallel computation, and argues that lots of existing analyses use the wrong measures and for that reason reach the wrong conclusions even asymptotically.  Some links:

http://cr.yp.to/nfscircuit/opcost.html
http://cr.yp.to/papers/nfscircuit.pdf
http://cr.yp.to/snuffle/bruteforce-20050425.pdf


TITLE: inequality in geometry
QUESTION [4 upvotes]: Given triangle $ABC$ has $BC=a$, $CA=b$, $AB=c$ and  $M$ is a point of the triangle plane. Prove that:
  \begin{align*}
  \cos \dfrac{A}{2} \cdot MA+\cos \dfrac{B}{2} \cdot MB+\cos \dfrac{C}{2} \cdot MC \geq \dfrac{a+b+c}{2}.
 \end{align*}

My attempts:
\begin{eqnarray*}
   a \cdot \overrightarrow{IA}+b \cdot \overrightarrow{IB}+c \cdot \overrightarrow{IC}=\overrightarrow{0} \Rightarrow \dfrac{\cos \dfrac{A}{2}}{IA}\overrightarrow{IA}+\dfrac{\cos \dfrac{B}{2}}{IB}\overrightarrow{IB}+\dfrac{\cos \dfrac{C}{2}}{IC}\overrightarrow{IC}=\overrightarrow{0}??????
  \end{eqnarray*}
with $I$ is center of inscribed circle of triangle $ABC$.
\begin{eqnarray*}
   \cos \dfrac{A}{2} \cdot MA=\dfrac{\cos \dfrac{A}{2}}{IA} \cdot MA \cdot IA\geq \dfrac{\cos \dfrac{A}{2}}{IA} \cdot \overrightarrow{MA} \cdot \overrightarrow{IA}.
  \end{eqnarray*}
The same as,
\begin{eqnarray*}
   \cos \dfrac{B}{2} \cdot MB &\geq& \dfrac{\cos \dfrac{B}{2}}{IB} \cdot \overrightarrow{MB} \cdot \overrightarrow{IB}\\
 \cos \dfrac{C}{2} \cdot MC &\geq& \dfrac{\cos \dfrac{C}{2}}{IC} \cdot \overrightarrow{MC} \cdot \overrightarrow{IC}.
  \end{eqnarray*}
I am stuck here.

REPLY [1 votes]: Here is my proof, based on the main result that if $DEF$ is the pedal triangle of $M$ then we have: $$\cos\left(\frac{A}{2}\right)\cdot MA\ge \frac{AE+AF}{2}\qquad (1)$$
In short, we prove the above inequality by using the formula for $\sin\alpha -\sin\beta$ to show that $$\cos\left(\frac{A}{2}\right) \cdot MA =  \dfrac{MF-ME}{2\sin\left(\dfrac{\widehat{MAF}-\widehat{MAE}}{2}\right)}\quad (2)$$
Then we use the following lemma: If $ABCD$ is a cyclic quadrilateral and $\widehat{B}=\widehat{D}=90^{\circ}$ then $$\dfrac{DA-DC}{BA+BC}\ge \sin\left(\dfrac{\widehat{ABD}-\widehat{CBD}}{2}\right) \qquad (3)$$
$(1)$ follows from $(2)$ and $(3)$, which gives us the original inequality