\section{Introduction}
This paper is a survey of the joint work with Xavier G\'omez-Mont and Luis Giraldo spread over some 15 years. We give a formula for calculating the index of singularities of real vector fields on singular hypersurfaces. Some partial results are published in \cite{GGM1}, \cite{GM1}, \cite{GM2},  \cite{GGM2}.

In \cite{GSV}, G\'omez-Mont, Seade and Verjovsky studied vector fields tangent  to a complex hypersurface with isolated singularity. They introduced a notion of index, now called GSV-index
 at a common singularity of
the vector field and the hypersurface (see also \cite{BG}).
It is a kind of relative version of the Poincar\'e-Hopf index at a singularity.
A natural question is how can one calculate this
index.
Complex case was studied first. It was solved by G\'omez-Mont in his seminal paper \cite{G}. G\'omez-Mont's formula expresses the GSV index via dimensions of certain local algebras. The GSV index can be generalized to the real case. More precisely, depending on the side of the singular hypersurface, there are two GSV indices.
Real case, is more difficult than the complex case since in the real case a simple singularity can carry the index $+1$ or $-1$, whereas in the complex case all simple singularities count as $+1$.

In the absolute  real case Eisenbud, Levine and Khimshiashvili expressed the Poincar\'e-Hopf index of a vector field in terms of the signature of a bilinear form.

Our result in the relative real case expresses the GSV-index of a real vector field on a singular variety as a sum of certain terms. Each term is a signature of a  non-degenerate bilinear form on some local algebra.

Our proof has two essential ingredients:  on one hand Gomez-M\'ont's result in the singular complex case and on the other hand the Eisenbud, Levine, Khimshiashvili's result in the real absolute case.

\subsection{Real absolute case}
Let us recall first the definition of the Poincar\'e-Hopf index of a singularity of a real vector field in $\mathbb{R}^{n+1}$.
Let
\begin{equation}\label{X}
X=\sum_{i=0}^n X^i\frac{\partial}{\partial x_i}
\end{equation}
 be a smooth vector field in $\mathbb{R}^{n+1}$ having an isolated singularity at the origin $X_0=0$. One can identify the vector field $X$ with a mapping
$X:(\mathbb{R}^{n+1},0)\to(\mathbb{R}^{n+1},0)$. Taking a small sphere $S^{n}$ around the origin, the vector field $X$ induces a map $N=\frac{X}{||X||}:S^n\to\mathbb{S}^n$, where $\mathbb{S}^n$ is the unitary sphere in $\mathbb{R}^{n+1}$.
The Poincar\'e-Hopf index $\operatorname{Ind}_0(X)$ of the vector field $X$ at the origin is defined as the degree of $N$.
That is, $\operatorname{Ind}(X,0)$ is the number of pre-images of generic points taken with orientation.

 \begin{example} Let $X$ be the vector field  $X(x,y)=x\frac{\partial}{\partial x}+y\frac{\partial}{\partial y}$ in $\mathbb{R}^2$ having a node at the origin and let $Y$ be the vector field $Y(x,y)=x\frac{\partial}{\partial x}-y\frac{\partial}{\partial x}$ having a saddle at the origin.

 Then $\operatorname{Ind}_0(X)=1$ and $\operatorname{Ind}_0(Y)=-1$.

 \end{example}

\subsection{Complex absolute case}
Consider the complex $n$-dimensional space $\mathbb{C}^n$, with complex coordinates $x_1,\ldots,x_n$ and a complex vector field $X$ of the form $X=\sum_{i=0}^n X^i\frac{\partial}{\partial x_i}$.
We can identify $\mathbb{C}^n$ with $\mathbb{R}^{2n}$. With this identification a holomorphic vector field on $\mathbb{C}^n$ becomes a smooth real vector field on $\mathbb{R}^{2n}$
and one can apply the previous definition of the Poincar\'e-Hopf index $\operatorname{Ind}_0(X)$ to a singularity of a holomorphic vector field.
Note that not every smooth real vector field on $\mathbb{R}^{2n}$ comes from a holomorphic vector field on $\mathbb{C}^{n}$. By holomorphy, a holomorphic vector field seen as a map preserves orientation. Hence the index of a singularity of a holomorphic vector field is necessarily positive.

\begin{example} Let $n=1$ and let $X=x\frac{\partial}{\partial x}$ and $Y=x^2\frac{\partial}{\partial x}$ be vector fields in $\mathbb{C}$.
Then $\operatorname{Ind}_0(X)=1$ and $\operatorname{Ind}_0(Y)=2$.
\end{example}

In the complex case, the Poincar\'e-Hopf index is simply the multiplicity. One counts how many points are hidden at the singularity at the origin.

\section{Definition of the GSV-index in the complex and real case}

\subsection{Smooth points}
Let now $f:(\mathbb{R}^{n+1},p)\to(\mathbb{R},0)$ be a germ of an analytic function. Then $V=f^{-1}(0)$ is a germ of a hypersurface at $p$.  We say that a vector field defined in a neighborhood of $p\in V$ is a vector field tangent to $V$, if there exists an analytic function $h$ such that

\begin{equation}\label{tangent}
X(f)=fh.
\end{equation}
The function $h$ is sometimes called the \emph{cofactor} of $X$. Assume first that $p\in V$ is a regular point of $f$. Then the variety $V$ is smooth in  a neighborhood of $p$. Let $x=(x_1,\ldots,x_n)$ be a chart of $V$ in a neighborhood of $p$. We assume moreover that the orientation of $\nabla f,\frac{\partial}{\partial x_1},\ldots,\frac{\partial}{\partial x_n}$ is positive. The chart $x=(x_1,\ldots,x_n)$ transports the vector field $X$ to $\mathbb{R}^n$. One then applies the usual definition of the Poincar\'e-Hopf index.
Thus we define the \emph{relative Poincar\'e-Hopf index} $\operatorname{Ind}_{V,p}(X)$ of a vector field tangent to a hypersurface, relative to the surface. It is easy to verify that the definition is independent of the choices.

If $f:(\mathbb{C}^{n+1},p)\to(\mathbb{C},0)$ is a germ of holomorphic function instead, $p\in\mathbb{C}^{n+1}$ is a regular point of $f$, $V=f^{-1}(f(p))\subset\mathbb{C}^{n+1}$ is a complex hypersurface,  and $X$ a holomorphic vector field tangent to $V$, one transports as previously the vector field to $\mathbb{C}^n$ and defines the  \emph{relative Poincar\'e-Hopf index} $\operatorname{Ind}_{V,p}(X)$ in the complex case. Note that in the relative complex case, just as in the absolute complex case, the relative index is always positive.

\subsection{Singular points, GSV-index in the complex case} Let as previously,
$f:(\mathbb{C}^{n+1},0)\to(\mathbb{C},0)$ be a germ of a holomorphic function. Assume now that $p\in\mathbb{C}^{n+1}$ is an isolated singularity of $f$. Then $V=f^{-1}(0)\subset\mathbb{C}^{n+1}$ is a complex hypersurface with isolated singularity at $p$. Let $X$ be a holomorphic vector field defined in a neighborhood of $p\in \mathbb{C}^{n+1}$
tangent to $V$. That is, relation \eqref{tangent}
holds. In \cite{GSV}, G\'omez-Mont, Seade and Verjovsky defined what is now called the GSV-index of a vector field tangent to a singular variety at the singularity   $\operatorname{Ind}_{V,0}(X)$.

 In order to formulate the definition, let us first recall that the holomorphic  function $f:(\mathbb{C}^{n+1},0)\to(\mathbb{C},0)$ having an isolated singularity at the origin defines a Milnor fibration: $f:B\setminus \{0\}\to \mathbb{C}^*$, where $B\subset\mathbb{C}^{n+1}$ is a small ball around the origin. Denote $V_\epsilon=f^{-1}(\epsilon)$. For $\epsilon\ne0$ small, close enough to zero, all fibers $V_\epsilon\cap B$ are isotopic. Note that the vector field
 $X$ is not necessarily tangent to the fibers $V_\epsilon\cap B$, for $\epsilon\ne0$. We modify X slightly, giving a $C^\infty$ vector field $X_\epsilon$ tangent to a fiber $V_\epsilon\cap B$, for $\epsilon\ne0$
close to zero.  We assume moreover that the restriction of the vector field $X_\epsilon$ on $\partial(V_\epsilon\cap B)$ is isotopic to the restriction of the vector field $X$ to $\partial(V\cap B)$ see \cite{P} and \cite{BG}.

The GSV-index can be defined by the formula

\begin{equation}\label{GSV}
\operatorname{Ind}_{V,0}(X)=\sum_{p_i(\epsilon)\in V_{\epsilon}\cap B}\operatorname{Ind}_{V_\epsilon,p_i(\epsilon)}(X_\epsilon).
\end{equation}
 It follows from the Poincar\'e-Hopf theorem that the definition is independent of all choices. Indeed, the
 Poincar\'e-Hopf theorem says that the right-hand side of \eqref{GSV} is the Euler characteristic
 $\chi(V_\epsilon\cap B)$ up to some correction term given by the behavior of any vector field
 $X_\epsilon$ on $\partial(V_\epsilon\cap B)$. Note that by the Milnor fibration theorem all regular fibers $V_\epsilon\cap B$, $\epsilon\ne0$, have the same Euler characteristic. Moreover, the behavior of any vector field in $X_\epsilon$ on $\partial(V_\epsilon\cap B)$
is the same as the behavior of $X$ on $\partial(V\cap B)$. Hence the correction term is independent of the choices.

 For an equivalent topological definition using residues see Suwa \cite{Su}.

 \begin{proposition}\label{uptoconstant}\label{char}\cite{BG}
 Up to a constant $K(V)$  independent of the vector field $X$, the GSV-index $\operatorname{Ind}_{V,0}(X)$ is characterized  by the two following conditions:

\begin{description}
\item[(i)] At smooth points $p\in V$, the GSV-index coincides with the relative Poincar\'e-Hopf index $\operatorname{Ind}_{V,p}(X)$.
\item[(ii)] The GSV-index satisfies the \emph{law of conservation of number}: For any holomorphic vector field $X'$ tangent to
$V$ sufficiently close to $X$ the following law of conservation of number holds:
\begin{equation}\label{conservation}
\operatorname{Ind}_{V,0}(X)=\sum_{p_{i}\in V} \operatorname{Ind}_{V,p_{i}(\epsilon)}(X').
\end{equation}
Here $p_{i}$ are singularities of $X'$ belonging to $V$, which are close to $0$.
\end{description}
\end{proposition}

The constant can be determined by calculating the GSV-index $\operatorname{Ind}_{V,0}(X)$, for any vector field tangent to $V$.

\subsection{GSV-index in the real case}
Let now $f:(\mathbb{R}^{n+1},0)\to(\mathbb{R},0)$ be a germ of a real analytic function.
In this case, there is no Milnor fibration, or more precisely there are two Milnor fibrations:
one for strictly positive small values of $\epsilon$ and one for small strictly negative values of $\epsilon$.
The Euler characteristic of all fibers $V_\epsilon\cap B$, for $\epsilon$ small of the same sign are the same, but can be different for $\epsilon$ positive or $\epsilon$ negative. (Think of $f:\mathbb{R}^3\to\mathbb{R}$ given by
$f(x,y,z)=x^2+y^2-z^2$.)
As in the complex case, in the real case one now defines the GSV-index. More precisely, one defines two GSV indices $\operatorname{Ind}_{V^\pm,0}(X)$, taking $V_\epsilon$, for $\epsilon$ positive or negative respectively.

\section{Calculating the GSV-index on complex hypersurfaces}
A formula for calculating the GSV-index in the complex case was given by G\'omez-Mont in \cite{G}.
Let us first define the principal ingredients. Let $\mathcal{O}_{\mathbb{C}^{n+1},0}$ be the algebra of germs of holomorphic functions at the origin. Let $f\in\mathcal{O}_{\mathbb{C}^{n+1},0}$ be given, with $f(0)=0$. Let $f_i=\frac{\partial f}{\partial z_i}$, $i=0,\ldots,n$, be the partial derivatives of $f$.
Assume that $0$ is an isolated singularity of $f$. This means that the algebra
\begin{equation}\label{A}
\mathbb{A^\C}=\frac{\mathcal{O}_{\mathbb{C}^{n+1},0}}{(f_0,\ldots,f_n)}
\end{equation}
is finite dimensional. Here $\mathcal{O}_{\mathbb{C}^{n+1,0}}$ is the algebra of germs at $0$ of holomorphic functions. The dimension $\mu=\operatorname{dim}(\mathbb{A^\C})$ is the Milnor number of the singularity. Let $X$ be a germ of holomorphic vector field at $0\in\mathbb{C}^{n+1}$ given by \eqref{X}. Assume that $0$ is an isolated singularity of $X$. This means that the algebra
\begin{equation}\label{B}
\mathbb{B^\C}=\frac{\mathcal{O}_{\mathbb{C}^{n+1},0}}{(X^0,\ldots,X^n)}
\end{equation}
is finite dimensional. Its dimension $\operatorname{dim}(\mathbb{B^\C})$ is the Poincar\'e-Hopf index $\operatorname{Ind}_0(X)$ of the vector field $X$ in the ambient space.

Let $V=f^{-1}(0)$ be the hypersurface defined by $f$ and assume that $X$ is tangent to $V$. That is,
\eqref{tangent} holds for some holomorphic function $h$.

\begin{theorem}\label{Xavier}\cite{G} The GSV-index of a holomorphic vector field $X$ tangent to a complex hypersurface $V$ at an isolated singularity $0$ is given by.
\begin{equation}
\operatorname{Ind}_{V,0}(X)=
 \begin{cases}
          \operatorname{dim}\frac{\mathbb{B^\C}}{(f)}-\operatorname{dim}\frac{\mathbb{A^\C}}{(f)}, & \text{if } $(n+1)$ \text{ even},\\
                  \operatorname{dim} \mathbb{B^\C}-\operatorname{dim}\frac{\mathbb{B^\C}}{(h)}+\operatorname{dim}\frac{\mathbb{A^\C}}{(f)}, & \text{if } $(n+1)$ \text{ odd}.
                   \end{cases}
\end{equation}
\end{theorem}
We give the idea of proof of Theorem \ref{Xavier}. As recalled in Proposition~\ref{uptoconstant}, the GSV index is defined up to a constant by condition (i) and (ii) in Proposition \ref{uptoconstant}.
In \cite{G} G\'omez-Mont
considers the \emph{Koszul complex}:
\begin{equation}\label{Koszul}
0\to\Omega_{V,0}^{n-1}{\to}\Omega_{V,0}^{n-1}\to\cdots\to\Omega_{V,0}^1\to\mathcal{O}_{V,0}\to0,
\end{equation}
where
\begin{equation}\label{omega}
\Omega_{V,0}^i=\frac{\Omega_{\mathbb{C}^{n+1},0}}{f\Omega_{\mathbb{C}^{n+1},0}+df\wedge\Omega_{\mathbb{C}_{n+1,0}^{i-1}}}.
\end{equation}
is the space of \emph{relatively exact forms} on $V$ and the arrows in \eqref{Koszul} are given by contraction of forms by the vector field $X$.
G\'omez-Mont defines the \emph{homological index} $\operatorname{Ind}^{hom}_{V,0}$ as the Euler characteristic of the complex \eqref{Koszul}:
\begin{equation}\label{hom}
\operatorname{Ind}^{hom}_{V,0}=\sum_{i=0}^{n-1}(-1)^i\operatorname{dim} H_i(K)
\end{equation}
where $H_i(K)$, $i=0,\dots,n-1$, are the $i$-th homology groups of the Koszul complex \eqref{Koszul}.
It is easy to see that at smooth points the homological index coincides with the relative Poincar\'e-Hopf index. In \cite{GGK}, Giraldo and G\'omez-Mont show that the homological index verifies the law of conservation (ii) of Proposition \ref{char}.
Hence, the homological index coincides with the GSV-index up to a constant $K(V)$.
The homological index has the advantage that it can be calculated using projective resolutions of a double complex. The horizontal complexes in the double complex are obtained as a \emph{mapping cone} induced by multiplication by the cofactor $h$ in \eqref{tangent} in the Koszul complex in the ambient space. Vertical complexes are obtained as the mapping cone induced by multiplication by $f$  in the \emph{de Rham complex} in the ambient space.  To show that
the homological index $\operatorname{Ind}^{hom}_{V,0}$ coincides with the GSV-index $\operatorname{Ind}_{V,0}$,
it is sufficient for each $f$ to calculate both indices on a vector field $X$ associated to $f$.
If the dimension of the ambient space  $(n+1)$ is even, a natural candidate is the Hamiltonian vector field

\begin{equation}\label{Xf}
X_f=\sum_{i=1}^{(n+1)/2}[f_{2i}\frac{\partial}{\partial x_{2i-1}}-f_{2i-1}\frac{\partial}{\partial x_{2i}}].
\end{equation}
If $(n+1)$ is odd, G\'omez-Mont uses the vector field
\begin{equation}\label{Yf}
Y_f=f\frac{\partial}{\partial x_0}\sum_{i=1}^{(n+1)/2}[f_{2i}\frac{\partial}{\partial x_{2i-1}}-f_{2i-1}\frac{\partial}{\partial x_{2i}}]
\end{equation}
in generic coordinates $x_i$.

\section{Calculating the Poincar\'e-Hopf index of vector fields in $\mathbb{R}^{n+1}$}
When studying the Poincar\'e-Hopf index in the real case, one has to take into account orientation and not just multiplicity. This is done using some bilinear forms. We recall in this section the results of Eisenbud, Levine \cite{EL} and Khimshiashvili \cite{Kh} who solve this problem for real vector fields in the ambient space $\mathbb{R}^{n+1}$. This, in addition to G\'omez-Mont's formula for calculating the GSV-index on complex hypersurfaces, are the two main ingredients in our study.

Let
\begin{equation}\label{BR}
\mathbb{B}=\frac{{\mathcal A}_{\mathbb{R}^{n+1},0}}{(X^0,\ldots,X^n)},
\end{equation}
where ${\mathcal A}_{\mathbb{R}^{n+1},0}$ is the algebra of germs at $0$ of analytic functions in $\mathbb{R}^{n+1}$. Let
$X$, given by \eqref{X}, be a germ of analytic vector field with an algebraically isolated singularity. That is, the singularity when considered over the complex domain remains isolated.  Then the algebra $\mathbb{B}$ is finite dimensional. Let $J=\det(\frac{\partial X^i}{\partial x_j})\in {\mathcal A}_{\mathbb{R}^{n+1},0}$ be the Jacobian of the map defined by the vector field $X$.
It can be shown that the class $[J]\in \mathbb{B}$ of $J$ in $\mathbb{B}$
is non-zero.
In \cite{EL} and \cite{Kh} Eisenbud, Levine and Khimshiashvili define a nondegenerate bilinear form
$<\,,\,>_{\mathbb{B},J}$ as follows.
\begin{equation}\label{bilin}
\mathbb{B} \times\mathbb{B}{\stackrel {\cdot}\longrightarrow} \mathbb{B}{\stackrel{
L}\longrightarrow } \mathbb{R}.
\end{equation}
Here the first arrow is simply multiplication in the algebra $\mathbb{B}$  and $L$ is any linear mapping such that $L([J])>0$.
Of course, the bilinear form depends on the choice of $L$. However its signature
$\operatorname{sgn}(\mathbb{B},J)=\operatorname{sgn}(<\,,\,>_{\mathbb{B},J})$
does not. More precisely Eisenbud, Levine, Khimshiashvili show

\begin{theorem}\label{ELK} Let $X$ be a germ at $0$ of a real analytic vector field on $\mathbb{R}^{n+1}$ having an algebraically isolated singularity at the origin. Then the Poincar\'e-Hopf index $\operatorname{Ind}_{\mathbb{R}^{n+1},0}(X)$ of
the vector filed $X$
at the origin is given by
\begin{equation}\label{eqELK}
\operatorname{Ind}_{\mathbb{R}^{n+1},0}(X)=\operatorname{sgn}(\mathbb{B},J).
\end{equation}
\end{theorem}

In order to prove the theorem, one has to prove that the signature $\operatorname{sgn}(\mathbb{B},J)$ coincides with the Poincar\'e-Hopf index for simple singularities and verifies the law of conservation of number.
The first claim is easily verified. The key-point of the proof of the law of conservation of number is the claim that the bilinear form $<\,,\,>_{\mathbb{B},J}$ is nondegenerate.

Once one knows that the form is nondegenerate, the law of conservation of number will follow. Indeed, let $X'$ be a small real deformation of the vector field $X$.  As the bilinear form is nondegenerate, its signature does not change by a small deformation.
The local algebra $\mathbb{B}$ will decompose into a multilocal algebra $\mathbb{B}(X')$ of the same dimension concentrated in some real point and complex conjugated pairs of points. One verifies that the contribution to the signature of the pairs of complex conjugated points is zero.
From the preservation of signature, there follows the law of conservation of number once one knows that the bilinear form is nondegenerate.

The nondegeneracy of the form $<\,,\,>_{\mathbb{B},J}$ is a more general feature. It follows from the fact that $J$
generates the \emph{socle} of the algebra $\mathbb{B}$. By definition a socle in an algebra is the \emph{minimal}
nonzero ideal of the algebra.

In general, let $\mathbb{B}$ be a real algebra. Assume that the socle of $\mathbb{B}$ is one-dimensional generated by $J\in\mathbb{B}$. We can define a bilinear form $<\,,\,>_{\mathbb{B},J}$ as above. Following the proof of Eisenbud-Levine in \cite{EL} one verifies that the form $<\,,\,>_{\mathbb{B},J}$ is nondegenerate. Its signature does not depend on the choice of the linear map $L$ such that $L(J)>0$.

\begin{example} Consider for instance $\mathbb{B}=\frac{{\mathcal A}_{\mathbb{R}^2,0}}{(x^2,y^3)}$. Then the socle is one-dimensional generated by $J=xy^2$.
The bilinear form $<\,,\,>_{\mathbb{B},J}$ is a nondegenerate form on the six dimensional space $\mathbb{B}$.

If $\mathbb{B}=\frac{{\mathcal A}_{\mathbb{R}^2,0}}{(x^2,xy^2,y^3)}$, then the socle is generated by $xy$ and $y^2$. It is not one-dimensional and one cannot define a nondegenerate bilinear form as above.
\end{example}

\section{Bilinear Forms on Local Algebras}
Let $\mathbb{B}=\frac{{\mathcal A}_{\mathbb{R}^{n+1},0}}{(X^0,\ldots,X^n)}$ be a finite dimensional complete intersection algebra. This assures that its socle is one-dimensional  generated by the Jacobian $J=\det(\frac{\partial X^i}{\partial x_j})$.

In \cite{GM1}, we observed that the Eisenbud-Levine, Khimshiashvili signature generalizes.
Let $h\in\mathbb{B}$ be arbitrary.
Denote $\operatorname{Ann}(h)=\{g\in\mathbb{B}: gh=0\}$ the \emph{annihilator ideal}
of $h$.
For $\mathbb{B}$ as above, the algebra $\frac{\mathbb{B}}{\operatorname{Ann}(h)}$ has a one-dimensional socle generated by the element $\frac{J}{h}\in\frac{\mathbb{B}}{\operatorname{Ann}(h)}$.
The assumption that $(J)$ is minimal guarantees that $J$ can be divided by $h$.
We define the bilinear form $<\,,\,>_{\mathbb{B},h,J}$ on $\frac{\mathbb{B}}{\operatorname{Ann}(h)}$ by
$<b,b'>_{\mathbb{B},h,J}=L(bb'h)$, where $L:\mathbb{B}\to\mathbb{R}$ is a linear mapping such that $L(J)>0$. In other words
$<b,b'>_{\mathbb{B},h,J}=L_h(bb')$, where $L_h(\frac{J}{h})>0$ is a linear mapping.
Note that in general the element $\frac{J}{h}$ is not well defined in $\mathbb{B}$. However, the ambiguity is lifted in the quotient space $\frac{\mathbb{B}}{\operatorname{Ann}(h)}$.

We put
\begin{equation}\label{rel}
\operatorname{sgn}(\mathbb{B},h,J)=\operatorname{sgn}<\,,\,>_{\mathbb{B},h,J}=\operatorname{sgn}(\frac{\mathbb{B}}{\operatorname{Ann}(h)},\frac{J}{h}).
\end{equation}
\subsection{Signatures associated to a singular point of a hypersurface}
Let now $f:(\mathbb{R}^{n+1},0)\to(\mathbb{R},0)$ be a germ of analytic function having an algebraically isolated singularity at the origin. Let $f_i=\frac{\partial }{\partial x_i}$ be the partial derivatives of $f$.
Consider the  local algebra $\mathbb{A}=\frac{{\mathcal A}_{\mathbb{R}^{n+1},0}}{(f_0,\ldots,f_n)}$. It is a finite complete intersection algebra. Its socle is one-dimensional generated by the Hessian $\operatorname{Hess}(f)=\det(\frac{\partial^2 f}{\partial x_i\partial x_j})$.

Define a flag of ideals in $\mathbb{A}$

\begin{equation}\label{Km}
K_m=\operatorname{Ann}_\mathbb{A}(f)\cap(f^{m-1}), \quad m\geq1.
\end{equation}
Note that
\begin{equation}\label{filtration}
0\subset K_{\ell+1}\subset\cdots\subset K_1\subset K_0=\mathbb{A}.
\end{equation}
Define a family of bilinear forms $<\,,\,>_{f,m}:K_m\times K_m\to\mathbb{R}$ by
\begin{equation}\label{<>}
<a,a'>_{f,m}=<\frac{a}{f^{m-1}},a'>, \quad m=0,\ldots,\ell+1,
\end{equation}
where $<\,,\,>_{\mathbb{A},Hess(f)}$ is the bilinear form defined in \eqref{bilin} for some linear map $L$ with $L(\operatorname{Hess}(f))>0$. In particular $<a,a'>_{f,0}=<fa,a'>_{\mathbb{A},\operatorname{Hess}(f)}$. The form $<\,,\,>_{f,0}$ degenerates on $\operatorname{Ann}_\mathbb{A}(f)$, but on $K_0/K_1$ defines a nondegenerate form. We have
$<a,a'>_{f,1}=<a,a'>_{\mathbb{A},\operatorname{Hess}(f)}$. This form degenerates on $K_2=\operatorname{Ann}_\mathbb{A}(f)\cap(f)$ etc.
In \cite{GGM2}, we define

\begin{equation}\label{sigma}
\sigma_i=\operatorname{sgn}<\,,\,>_{f,i}, \quad i=0\ldots,\ell.
\end{equation}
The signatures $\sigma_i$ are intrinsically associated to the singularity $0$ of $f$.

\section{Main Result}
The following theorem resumes our results \cite{GM1}, \cite{GM2}, \cite{GGM1}, \cite{GGM2} about the calculation of the GSV-index of singularities of real vector fields on hypersurfaces:

\begin{theorem} \label{main} Let $f:(\mathbb{R}^{n+1},0)\to(\mathbb{R},0)$ be a germ of analytic function with algebraically isolated singularity at the origin. Let $X$ be an analytic vector field in $\mathbb{R}^{n+1}$ having an algebraically isolated singularity at the origin. Assume that $X$ is tangent to $V=f^{-1}(0)$. That is $X(f)=hf$, for some analytic function $h$. Then
 \begin{description}
\item[(i)] if $(n+1)$ is even,
\begin{equation}\label{even}
\operatorname{Ind}_{V^+,0}(X)=\operatorname{Ind}_{V^-,0}(X)=\operatorname{sgn}(\mathbb{B},h(X),J(X))-\operatorname{sgn}(\mathbb{A},h(X),\operatorname{Hess}(f)).
\end{equation}

\item[(ii)] if $(n+1)$ is odd,
\begin{equation}\label{odd}
\operatorname{Ind}_{V^\pm,0}(X)=\operatorname{sgn}(\mathbb{B},h(X),J(X))+\operatorname{sgn}(\mathbb{A},\operatorname{Hess}(f))+K_\pm, \end{equation}
where
\begin{equation}
K_+=\sum_{i\geq 1}\sigma_i, \quad K_-=\sum_{i\geq 1}(-1)^i\sigma_i.
\end{equation}

\end{description}
\end{theorem}

\section{Proof of the Main theorem}

We give here the main ingredients of the proof of Theorem \ref{main}. The GSV-index is determined by three properties:
\begin{description}
\item[(i)] Value at smooth points
\item[(ii)] The law of conservation of number
\item[(iii)] Constants $K_\pm$ depending only on the orientation (side) $V_\pm$ of the variety $V=f^{-1}(0)$ and not on the vector field.
\end{description}

One verifies easily that at smooth points of $V$,  the formula is valid. Indeed, from the tangency condition there follows $(f)\subset \operatorname{Ann}(h)$. In smooth points the converse is also true. Hence
$\operatorname{Ann}(h)=(f)$. Next, working in a local chart at smooth points one shows that
$\operatorname{sgn}<\,,\,>_{\mathbb{B},h,J}$ gives the relative Poincar\'e-Hopf index of the vector field. Then, one has to show that our formulas  \eqref{even}  and \eqref{odd} verify the law of conservation of number.
Some parts are easier in the even case and some other are easier in the odd case.

\subsection{$(n+1)$ odd case}

 The law of conservation of number is easy for $(n+1)$ odd.
Indeed, in this case the complex index, up to a constant depending only of $f$, is  $\operatorname{dim}\mathbb{B}^\mathbb{C}-\operatorname{dim}\frac{\mathbb{B}^\mathbb{C}}{(h)}=\operatorname{dim}\frac{\mathbb{B}^\mathbb{C}}{\operatorname{Ann}(h)}$ (see Theorem \ref{Xavier}). On the other hand on $\frac{\mathbb{B}}{\operatorname{Ann}(h)}$ there is the non-degenerate form $<\,,\,>_{\mathbb{B},h,J}$. Make a small deformation $X'$ of $X$, tangent to $V$.  The corresponding local algebra $\mathbb{B}$ or rather its complexification decomposes into a multilocal algebra concentrated in several points corresponding to singular points of $X'$.
The dimension of the multilocal algebra is equal to the sum of the dimensions at points in which it is concentrated. On the other hand, by Theorem \ref{Xavier} of Gomez-Mont, the dimension
$\operatorname{dim}\frac{\mathbb{B}^\mathbb{C}(X')}{\operatorname{Ann}(h)}$ verifies the law of conservation of number. Hence, the dimension of the
multilocal algebra obtained after deformation $X'$ of $X$ is
equal to the dimension of the local algebra $\operatorname{dim}\frac{\mathbb{B}^\mathbb{C}}{\operatorname{Ann}(h)}$ before the deformation.
This permits to extend continuously the bilinear form $<\,,\,>_{h,J}$ from the algebra $\frac{\mathbb{B}}{\operatorname{Ann}(h)}$
to its deformation. By nondegeneracy of the form $<\,,\,>_{h,J}$, its signature is unchanged by a small deformation. This gives the law of conservation of number for the signature of $<\,,\,>_{h,J}$ when adding the signatures for all (real or complex) singular points of $X'$ appearing after deformation.  Note that from the tangency condition \eqref{tangent}, it follows that $(f)\subset \operatorname{Ann}(h)$, so only points in $V=f^{-1}(0)$ can contribute to the signature $\operatorname{sgn}<\,,\,>_{\mathbb{B}(X'),h,J}$ after deformation.
At the end, let us note that complex zeros of $X'$ come in pairs. One verifies that the contribution to the signature of each pair is equal to zero. Hence only real singular points of $X'$ belonging to $V$ contribute.
The law of conservation of number (in the real case) for the formula $\operatorname{sgn}(\mathbb{B},h,J)$ follows.

The final step in proving the formula in the case $(n+1)$ odd is to adjust the constant $\operatorname{sgn}(\mathbb{A},\operatorname{Hess}(f))+K_\pm$. This is difficult in the odd case. We will come back to it in subsection \ref{7.4}.

\subsection{$(n+1)$ even case}
In the $(n+1)$ even case Theorem \ref{Xavier} says that in the complex case, up to a constant, the index is given by $\operatorname{dim}\frac{\mathbb{B}^\mathbb{C}}{(f)}$.  There is no natural bilinear form on  $\frac{\mathbb{B}^\mathbb{C}}{(f)}$.
We consider a non-degenerate bilinear form on $\frac{\mathbb{B}^\mathbb{C}}{\operatorname{Ann}(h)}$. We stratify the space of bilinear vector fields by the dimension of the ideal $(h)$ in the algebra $\mathbb{A}$.  The signature $\operatorname{sgn}(h(X),J(X))$ verifies the law of conservation of number in restriction to each stratum. We show that when changing the stratum the jump in $\operatorname{sgn}(\mathbb{B},h,J)$ is equal to the jump in $\operatorname{sgn}(\mathbb{A},h,\operatorname{Hess}(f)).$ The two jumps hence compensate in the index formula \eqref{even}. In order to show the equality of the jumps it is sufficient to study the place where all strata meet i.e. the stratum of highest codimension. One has the highest codimension for the Hamiltonian vector field $X_f$ given by \eqref{Xf}, when $h=0$. Note that in this case the two algebras $\mathbb{A}$ and $\mathbb{B}$ coincide and $J(X)=\operatorname{Hess}(f)$.

In this case it is very easy to determine the constant (independent of the vector field) adjusting the  signature formula with index. For that purpose, one studies the Hamiltonian vector field $X_f$. Note that the Hamiltonian vector field $X_f$ is tangent to all fibers $V_\epsilon=f^{-1}(\epsilon)$. Moreover, it has the same behavior on the boundary $V_\epsilon\cap B$, for $\epsilon\ne0$  as on $V\cap B$.
The Hamiltonian vector field $X_f$ has no zeros on $V_\epsilon=f^{-1}(\epsilon)$, for $\epsilon\ne0$.
Hence $\operatorname{Ind}_{V_\pm}(X_f)=0$.
On the other hand $\operatorname{sgn}(\mathbb{B},h(X),J(X))-\operatorname{sgn}(\mathbb{A},h,Hess)=0$, as $\mathbb{A}=\mathbb{B}$ and $J=\operatorname{Hess}$. It follows that no correction term has to be added to $\operatorname{sgn}(\mathbb{B},h(X),J(X))-\operatorname{sgn}(\mathbb{A},h,Hess)$ in order to obtain the formula for $\operatorname{Ind}_{V_\pm,0}(X)$.

\subsection{Why is $\operatorname{Ind}_{V_+,0}(X)=\operatorname{Ind}_{V_-,0}(X)$ in the $(n+1)$ even case and not in the odd case?}

We explain here why $\operatorname{Ind}_{V_+,0}(X)=\operatorname{Ind}_{V_-,0}(X)$ in the $(n+1)$ even case and not in the odd case.
Note first that the index of a vector field in the ambient space is an even function if the dimension $(n+1)$ of the ambient space is even and is an odd function if $(n+1)$ is odd. We next use Morse theory.
Consider the vector field $\nabla f.$ By Morse theory, the Euler characteristic $\chi$ verifes:
\begin{equation}\label{chi}
\left.
\begin{array}{rcl}
  \chi(V_+)& =  &   1+\operatorname{Ind}(\nabla f)\\
 \chi(V_-) &=   & 1+\operatorname{Ind}(-\nabla f).
\end{array}
\right.\end{equation}
Here $\chi(V_{+})$ is the Euler characteristic of $V_\epsilon\cap B$, for $\epsilon>0$ small. The value $\chi(V_{-})$ is defined analogously.

If $(n+1)$ is even, then $\operatorname{Ind}(\nabla f)=\operatorname{Ind}(-\nabla f)$, so $\chi(V_+)=\chi(V_-)$ and $\operatorname{Ind}_{V_+,0}(X)=-\operatorname{Ind}_{V_-,0}(X)$.

If $(n+1)$ is odd, then $\operatorname{Ind}(-\nabla f)=-\operatorname{Ind}(\nabla f)$, so $\chi(V^+)-1=-(\chi(V_-)-1)$ and
$\operatorname{Ind}_{V_-,0}(X)=2-\operatorname{Ind}_{V_+,0}(X)$.
\subsection{Adjusting the constant $K$ in the $(n+1)$ odd case}\label{7.4}
In order to complete the sketch of proof of the main theorem, we have to explain how do we calculate the constant $K_\pm$ appearing in the $(n+1)$ odd case \eqref{odd}.

As shown previously, the two signature terms in \eqref{odd} calculate the GSV-index up to a constant independent of the vector field. In order to determine the constant, for each $V=f^{-1}(0)$, one has to take a vector field tangent to $V$, having an algebraically isolated singularity at the origin.
Contrary to the situation in the $(n+1)$ even case, in the odd case, there is no such natural vector field. As in \cite{G}, we use the family of vector fields
\begin{equation}\label{Xft}
X_t=(f-t)\frac{\partial}{\partial x_0}\sum_{i=1}^{(n+1)/2}[f_{2i}\frac{\partial}{\partial x_{2i-1}}-f_{2i-1}\frac{\partial}{\partial x_{2i}}]
\end{equation}
 in generic coordinates.
 The local algebra is $\mathbb{B}=\mathbb{B}(X_0)=\frac{\mathcal{A}_{\mathbb{R}^{n+1},0}}{(f,f_1,f_2,\ldots,f_n)}.$
Note that $X_t$ is tangent to $V_t=f^{-1}(t)$, for any $t$.
More precisely, $X_t(f)=f_0 f$, so $h=f_0$ is the cofactor of $X_t$.
Hence, by definition
\begin{equation}
\operatorname{Ind}_{V_+}(X,0)=\sum_{p_t\in V_t\cap B}\operatorname{Ind}_{V_t,p_t}(X_t).
\end{equation}
But, these indices are calculated using the multilocal algebra $\mathbb{B}_t$ and the relative Jacobian $\frac{J(X_t)}{f_0}$. That is, the index is given by the signature of the bilinear form $<\,,\,>_{\mathbb{B}_t}$, for $t\ne0$ small.
For the index $\operatorname{Ind}_{V_+,0}(X_0)$, we have to take it positive and for $\operatorname{Ind}_{V_-,0}(X_0)$ it is negative.
 The problem is that this form degenerates on $\operatorname{Ann}_{\mathbb{B}_t}(f_0)$, for $t=0$.

We prove in \cite{GGM2} a general result for algebras $\mathbb{A}=\mathbb{A}(f)$ and $\mathbb{B}=\mathbb{B}(X)$ associated to  a vector field $X$ tangent to $V=f^{-1}(0)$ i.e. verifying \eqref{tangent}:

\begin{lemma}\label{iso}
There exists a natural isomorphism between the algebras $\operatorname{Ann}_{\mathbb{B}}(h)$ and $\operatorname{Ann}_\mathbb{A}(f)$.
\end{lemma}
\begin{proof}
The isomorphism is given by the mapping $g\mapsto k$ if $gh=fk$.
\end{proof}

Lemma \ref{iso} permits to transport all higher order signature vanishing in $\operatorname{Ann}_{\mathbb{B}_0}$ to a natural algebra $\mathbb{A}$. We apply it to our vector field $X_t$. When looking at the signature of the form $<\,,\,>_{\mathbb{B}_t}$, we have one part which does not degenerate. It is the part in $\frac{\mathbb{B}}{\operatorname{Ann}_\mathbb{B}(f_0)}$. The bilinear form $<\,,\,>_{\mathbb{B}_t}$ degenerates at different orders on different parts of
$\operatorname{Ann}_{\mathbb{B}_t}(f_0)$.  By Lemma \ref{iso}, we transport the bilinear form $<\,,\,>_{\mathbb{B}_t}$ to a bilinear form in the coordinate independent algebra  $\operatorname{Ann}_\mathbb{A}(f)$. Note that in $\mathbb{B}_t$, we have $f=t$, so degeneration of $<\,,\,>_{\mathbb{B}_t}$ at different orders of $t$ corresponds to multiplication by $f$ in the algebra $\operatorname{Ann}_{\mathbb{A}}(f)$.
For more details see \cite{GGM2}.

\section{Open problems}

\subsection{Geometric interpretation of the signatures $\sigma_i$. Filtration of contributions to the Euler characteristic of the generic fiber}
In Theorem \ref{main} appear higher order signatures $\sigma_i$ defined in \eqref{sigma}.  These signatures are associated to the singularity $f$ alone. We would like to give a geometric interpretation of these numbers. We believe that they correspond to parts of the Euler characteristic of the generic fiber, filtered by the speed of arrival at the singular fiber.

Let us be more precise. In \cite{T} Teissier studies polar varieties in the complex case.
He considers a germ of a function $f:(\mathbb{C}^2,0)\to(\mathbb{C},0)$ having an isolated critical point at the origin.
He considers a Morsification $f_s=f-s x_0$ of $f$ in generic coordinates $(x_0,\ldots,x_{n})$. Its critical points are given by

\begin{equation}
f_0-s=f_1=\cdots=f_n=0.
\end{equation}
Let $\Gamma$ be the curve given by $f_1=\cdots=f_n=0$. The curve $\Gamma$ is called \emph{polar curve}. In general it has several branches $\Gamma=\cup_{q=1}^\ell\Gamma_q$. By Morsification, the critical point $0$ of $f$ decomposes in several critical points arriving along the polar curve to the origin. For each value of $s\ne0$,  the critical points of $f_s$ belong to $f_0^{-1}(s)\cap\Gamma$.
Each critical point corresponds to a vanishing cycle contributing to $H_n(V_{t_0})$.
In \cite{T}, Teissier observed that, after Morsification, critical points arrive at different speed at the origin.
More precisely, each component $\Gamma_q$ of the polar curve $\Gamma$ is parametrized as
\begin{equation}\label{Gamma}
\left.
\begin{array}{rcl}
  x_0(t_q)& =& t_q^{m_q}+\cdots \\
  \ldots&\ldots&\ldots\\
 x_n(t_q) &= &\lambda_n t_q^{k_{q,n}} +\cdots
\end{array}
\right.\end{equation}
where $m_q\leq k_{q,i}$.
In \cite{T}, Teissier calculates the exponent $m_q$.
One can use $x_0$ (or the corresponding critical value) as a measure for the speed of approach of a critical point in the Morsification.
One can filter the $n$-th group of homology of the generic fiber $H_n(f^{-1}(t))$ i.e. the space of vanishing cycles, by  the speed of arrival of the corresponding critical points.
We believe that this filtration is given by  the filtration \eqref{filtration} or rather its complex counterpart.
The dimensions
\begin{equation}
0=\operatorname{dim}\frac{\mathbb{A}}{K_0}\leq\operatorname{dim}\frac{\mathbb{A}}{K_1}\leq\operatorname{dim}\frac{\mathbb{A}}{K_{\ell+1}}\leq\operatorname{dim}\mathbb{A}
\end{equation}
 would measure the dimension of the space of vanishing cycles arriving at a certain minimal speed.

 The signatures $\sigma_i$ would be the real counterpart. The signature $\sigma_0$ is a signature  of a bilinear form on $\mathbb{A}$. It measures the Euler characteristic $\chi(V_t)$. We believe that the signatures $\sigma_i$ that we introduced measure the filtered part of the Euler characteristic of the generic fiber $\chi(V_t)$, the filtration being done  by taking only the part of the topology of the fiber arriving at a certain minimal speed.
 We hope to be able to address this problem in a continuation of our research.

 \subsection{Generalization to higher codimension}

 In \cite{BEG} Bothmer, Ebeling and  G\'omez-Mont generalized G\'omez-Mont's formula (Theorem \ref{Xavier}) to a  formula for the index of a vector field on an isolated complete intersection singularity in the complex case.
 A natural problem would be to extend the result to the real case. Here, as in our Theorem \ref{main}, one would certainly have to define some bilinear forms on the spaces studied in \cite{BEG}.

\bibliographystyle{plain}


\section{Introduction}
\label {sec:introduction}

Galaxy bars spontaneously form due to instabilities in dynamically
cold disks.  The growth rate of bars depends on the halo-to-disk mass
ratio and the velocity dispersions of the disk and halo and bars grow
faster in massive and cold disks \citep[see][for a
  review]{Athanassoula2012}.
Moreover, environmental processes can regulate the life cycle of bars
contributing both to their development by forcing disk instabilities
and to their destruction via disk heating.
A variety of methods to detect
bars in galaxy disks and measure the local galaxy density have been
adopted, but the results on the correlation between the bar fraction
and environment are controversial \citep[see][and references
  therein]{MendezAbreu2012}.

Here, we derive the bar fraction in three different galaxy
environments ranging from the field to the Virgo and Coma clusters.
The unprecedentedly large range of luminosities (or, equivalently,
stellar masses) covered by the different galaxy samples we investigate
allows us to distinguish the effects of environment in heating galaxy
disks from those triggering bar formation.

\section{Galaxy sample, identification of disks, and detection of bars}
\label{sec:sample}

Four galaxy samples were selected in order to analyze three different
galaxy environments (i.e., the field, Virgo cluster, and Coma
cluster):

\begin{itemize}

\item field1 sample: 2389 field galaxies with magnitude
  $-24\,\lesssim\,M_r\,\lesssim\,-20$ from \citet{Aguerri2009};

\item field2 sample: 352 field galaxies with
  $-21\,\lesssim\,M_r\,\lesssim\,-13$ from \citet{SanchezJanssen2010};

\item Virgo sample: 588 Virgo galaxies with
  $-22\,\lesssim\,M_r\,\lesssim\,-13$ from Zarattini et al. (in
  prep.);

\item Coma sample: 169 Coma galaxies with
  $-23\,\lesssim\,M_r\,\lesssim\,-14$ and located mainly in the
  cluster center from \citet{MendezAbreu2010}.

\end{itemize}

The $g$ and $r$ apparent magnitudes and axial ratios $b/a$, of all the
galaxies were retrieved from Sloan Digital Sky Survey (SDSS) III
(\citealt{Aihara2011}). We considered only the galaxies with
$b/a\,>\,0.5$ in order to deal with projection effects.
The galaxy images of field2, Virgo, and Coma samples have a similar
spatial resolution ($r_{\rm bar}\simeq150$ pc). Indeed, the farthest
galaxies (i.e., those in the Coma sample) were analyzed by studying
their {\em Hubble Space Telescope\/} images.  The mean resolution of
the field1 sample is $r_{\rm bar}\,\simeq\,1.3$ kpc. However, since
the field1 galaxies are the largest galaxies in our sample, bars
smaller than the resolution limit should be considered as nuclear
bars.
We computed the stellar mass from the $g-r$ color following
\citet{Zibetti2009} to avoid a possible color bias due to cluster
galaxies being on average redder than in the field.

We adopted the morphological classification of the galaxies in the
SSDS-Data Release 7 spectroscopic sample given by
\citet{HuertasCompany2011}. Due to the incompleteness of the SDSS
spectroscopic sample and since several of our sample galaxies do not
have any spectroscopic information, we remained with 1604, 336, 228,
and 44 disk galaxies in the field1, field2, Virgo, and Coma sample,
respectively.
Following \citet{Aguerri2009} and \citet{MendezAbreu2010}, we detected
the presence of bars by visually inspecting the galaxy images. We
classified all the galaxies into strong barred, weakly barred, and
unbarred.

\section{Results}
\label{sec:results}

For each galaxy sample we derived the {\em ordinary\/} bar fraction
$f_{\rm D}$ (calculated only for the disk galaxies) and the {\em
  overall\/} bar fraction $f_{\rm T}$ (calculated for all the galaxies
independently of their Hubble type).
Since bars can only be triggered in disks, $f_{\rm T}$ combines the
luminosity distribution of disk galaxies with their probability of
having a bar overcoming the problem of the identification of disk
galaxies.  This is always a major concern in morphological
classifications dealing with the measurement of bar fraction.  $f_{\rm
  T}$ allows us to probe a larger range of luminosities than $f_{\rm
  D}$.

Figure \ref{fig:1} shows $f_{\rm D}$ and $f_{\rm T}$ as function of
the $r$-band absolute magnitude and mass of the galaxies.
The lower and upper boundaries  of the hatched areas correspond to the
bar fraction calculated by  considering only the strong (i.e., secure)
bars and both  the strong and weak (i.e.,  secure and uncertain) bars,
respectively and including their  statistical uncertainties.
The values of $f_{\rm D}$ and $f_{\rm T}$ for the samples of bright
(field1) and faint field galaxies (field2) are in good agreement.
Therefore, for studying the bar fraction distribution we merged the
two samples into a joint sample of field galaxies (hereafter field
sample).
The fraction of barred galaxies shows a maximum of about $50\%$ at
$M_r\,\simeq\,-20.5$ in clusters, whereas the peak is shifted to
$M_r\,\simeq\,-19$ in the field.

 \begin{figure*}[!ht]
 \centering
 \includegraphics[width=0.45\textwidth]{corsini_f1a.ps}
 \includegraphics[width=0.45\textwidth]{corsini_f1b.ps}
 \includegraphics[width=0.45\textwidth]{corsini_f1c.ps}
 \includegraphics[width=0.45\textwidth]{corsini_f1d.ps}
 \caption{\footnotesize Bar fraction distribution as function of the
   galaxy magnitudes (left panels) and masses (right panels).  The bar
   fraction calculated using all the Hubble types ($f_{\rm T}$) and
   only the disk galaxies ($f_{\rm D}$) are plotted in the upper and
   bottom panels, respectively. The field1, field2, Virgo, and Coma
   samples are showed by the hatched orange, green, blue, and red
   areas, respectively.  The grey arrow indicates the characteristic
   mass below which low-mass galaxies start to be systematically
   thicker \citep{SanchezJanssen2010}.}
 \label{fig:1}
 \end{figure*}

For a consistency check we performed the same analysis in the sample
studied by \citet{NairAbraham2010}.  We adopted their morphological
classification and estimate of the local galaxy density to identify
galaxies in the field ($\Sigma_5\,<\,1$ Mpc$^{-2}$) and in compact
groups ($\Sigma_5\,>\,10$ Mpc$^{-2}$). The bar fraction distributions
of these two subsamples probing the very low-density and very
high-density environments, respectively are shown in
Figure~\ref{fig:2}.  The trends we derived from the data by
\citet{NairAbraham2010} are fully in agreement with the findings for
our samples once we take into account that \citet{NairAbraham2010}
impose a more severe definition in identifying barred galaxies and
hence the values of $f_{\rm D}$ and $f_{\rm T}$ we derived for their
samples are systematically lower than those in this work.

 \begin{figure*}[!ht]
 \centering
\includegraphics[width=0.8\textwidth, clip=true]{corsini_f2.ps}
 \caption{\footnotesize Bar fraction distribution for two subsamples
   of galaxies from \citet{NairAbraham2010} and calculated for all the
   Hubble types (upper panel) and disks only (bottom panel) as a
   function of the galaxy magnitude.  The black and red regions show
   the galaxies in low ($\Sigma_5\,<\,1 $ Mpc$^{-2}$) and high density
   environments ($\Sigma_5\,>\,10$ Mpc$^{-2}$), respectively.}
 \label{fig:2}
 \end{figure*}

\section{Conclusions}

The difference of the bar fraction distributions as a function of
galaxy luminosity (and mass) in the field and Coma cluster is found to
be statistically significant ($>68\%$ confidence level), with the
Virgo cluster being an intermediate case.
Since bars live in disks, these findings allow us to distinguish
between the environmental processes inhibiting bar formation (heating)
or even destroying the host disk from the processes triggering the
disk instabilities which are responsible for bar formation.

We interpret the decrease of $f_{\rm D}$ and $f_{\rm T}$ with
decreasing galaxy luminosity observed for fainter
($M_r\,\gtrsim\,-19$) or, equivalently, less massive galaxies ($ {\cal
  M_{*}}/{\cal M}_{\sun}\,\lesssim\,10^{9}$) as due to the increase of
the disk thickness. Indeed, \citet{SanchezJanssen2010} have recently
found that the minimum of the disk thickness distribution occurs at a
characteristic mass ${\cal M_{*}}/{\cal
  M}_{\sun}\,\simeq\,2\,\times\,10^9$ (corresponding to
$M_r\simeq\,18.5$) below which low-mass galaxies start to be
systematically thicker making it difficult to develop a bar.  We
suggest that the values of $f_{\rm D}$ and $f_{\rm T}$ in the field
are systematically larger than those in Virgo and Coma because the
low-mass galaxy disks in clusters are more easily heated, or
destroyed, by galaxy interactions and can not develop a bar. In the
low luminosity regime nurture and nature are acting on galaxy disks in
cluster and field, respectively.

Since the values of $f_{\rm D}$ and $f_{\rm T}$ are larger for cluster
galaxies with $ -21.5\,\lesssim\,M_r\,\lesssim\,-19.5$ (or $
10^{9.5}\,\lesssim\,{\cal M_{*}}/{\cal M}_{\sun}\,\lesssim\,10^{11}$),
we conclude that brighter disks are strong enough to survive
interactions and form a bar.  In the high luminosity regime nurture
and nature are acting on bar formation in galaxy disks of cluster and
field, respectively.

Our results highlight the importance of studying galaxy samples which
have been carefully selected in luminosity to avoid biases when
dealing with bar statistics. We argue that most of the controversial
results about the relationship between environment and bar fraction
could be explained in terms of the different luminosity ranges covered
by the galaxy samples studied so far.

\bibliographystyle{aa}


\section{Introduction}
The Kolmogorov complexity of a string $x$  is the length of the shortest program computing it. Determining the Kolmogorov complexity of a string  is a  canonical example of  a function that is not computable.
Closely related is the problem of actually producing a shortest program for $x$. This problem is also not
algorithmically solvable.
When faced with a function that is not computable,  it is natural to ask whether it can be effectively approximated in a meaningful way.
This question has been investigated for Kolmogorov complexity in various ways. First of all,  it is well-known that the Kolmogorov complexity can be effectively approximated from above. A different type of approximation is given by what is typically called \emph{list computability} in algorithms and complexity theory and \emph{traceability} in  computability theory. For this type of approximation, one would like to compute a list of ``suspects'' for the result of the function with the guarantee that the actual result is in the list. Of course, the shorter the list is, the better is the approximation.

The list approximability of the Kolmogorov complexity, $C(x)$, has been studied by Beigel et al.~\cite{bei-bur:j:enumerations}.  They observe that $C(x)$ can be approximated by a list of size $(n-a)$ for every constant $a$, where $n = |x|$. On the other hand, they show that, for every universal machine $U$, there is a constant $c$ such that for infinitely many strings $x$ (in fact for at least one $x$ at each sufficiently large length $n$), any computable list containing $C_U(x)$ must have size larger than $n/c$.

In this paper we study  list approximability for the problem of producing short programs. In order to describe our results, we need several formal definitions.

A machine $U$ is {\em optimal} if $\C_U(x|y) \le C_V(x|y) + O(1)$ for all machines $V$  (where the
constant $O(1)$ may depend on $V$).
An optimal machine $U$ is \emph{standard}\footnote{
This notion was introduced by Schnorr~\cite{schnorr}, and he called such machines \emph{optimal
G\"odel numberings} (of the family of all computable functions from strings to strings).
We use a different term
to distinguish between optimal functions in Kolmogorov's sense and Schnorr's sense},
if for every machine $V$ there is a
total computable function $t$ such that for all $p,y$: $U(t(p),y) = V(p,y)$ and $|t(p)| = |p| +O(1)$.
For results that hold in polynomial time, we additionally assume these functions $t$ run in
time polynomial in $|p|$.
Let $U(p)$ stand for $U(p,\text{the empty string})$ and  $C_U(x)$ for $C_U(x|\text{the empty string})$.
A {\em $c$-short program} for $x$ with respect to  $U$ is a string $p$ that satisfies
$U(p) = x$ and $|p| \le \C_U(x) +c$.

Given an optimal machine $U$,
a \emph{list-approximator} for $c$-short programs is a function $f$ that on every input $x$ outputs a finite list of strings such that at least one of the elements in the list is a $c$-short  program for $x$ on $U$.
Let $|f(x)|$ denote the number of elements in the list  $f(x)$. Obviously, for every optimal $U$, there is a (trivial) computable list-approximator $f$ such that $|f(x)| \leq 2^{|x|+O(1)}$.

The question we study is how small can $|f(x)|$ be for computable list-approximators $f$ for $c$-short programs, where $c$
is a constant or $O(\log|x|)$.
At first glance it seems that in both cases  $|f(x)|$ must be exponential in $|x|$.
Surprisingly, this is not the case. We prove that there is a computable approximator
with list of size $O(|x|^2)$ for $c$-short programs for some constant $c$ depending on the choice of the standard machine $U$.
And we show that this bound is tight.
We show also that there is a \emph{polynomial time computable}
approximator with list of size $\poly(|x|)$ for  $c$-short programs for $c=O(\log|x|)$.

We start with the positive results, i.e., the upper bounds.
We show  that for every standard machine, there exists a list-approximator for $O(1)$-short programs, with lists of \emph{quadratic} size.

\begin{theorem} \label{t:complist}
For every standard machine $U$ there exists a computable function $f$ that for any $x$ produces a
list with  $O(|x|^2)$ many elements containing a program $p$ for $x$ of length $|p| = C_U(x) + O(1)$.
\end{theorem}

If we allow $O(\log |x|)$-short  programs we can construct lists of polynomial size in \emph{polynomial time}.

\begin{theorem} \label{t:polytimelist}
  For every standard machine $U$, there exists a polynomial-time computable function $f$
  that for any $x$ produces a list with $\poly(|x|)$ many elements containing  a program for $x$
  of length $C_U(x)+ O(\log |x|)$.\footnote{Recently, Jason  Teutsch~\cite{teu:t:shortlist} has improved this result replacing $O(\log |x|)$ by $O(1)$.}
\end{theorem}

Now we move to the lower bounds. We show that
the quadratic lower bound in Theorem \ref{t:complist} is optimal:
it is not possible to compute lists of subquadratic size that contain a $O(1)$-short program.

\begin{theorem}\label{th:quadraticlistt}
For all $c>0$, for every optimal $U$, for every computable $f$ that is  a  list-approximator for $c$-short programs,
\[
|f(x)| \ge \Omega(|x|^2/c^2),
\]
for infinitely many $x$.
(The constant hidden in $\Omega$-notation depends on the function $f$ and machine $U$.)
\end{theorem}

A weaker linear lower bound can be easily derived
from a result of  Bauwens~\cite{bau:c:complexity}, improving a theorem of
G\'{a}cs~\cite{gac:j:symmetry}. The result states that  $\C_U(C_U(x) \mid x)$ is greater than $\log |x| - O(1)$
for infinitely many $x$.  Thus, for infinitely many $x$,
\[
\log |x| - O(1) \leq \C_U(\C_U(x) \mid x) \leq \log |f(x)| + 2 \log c + O(1),
\]
and therefore $|f(x)| \geq \Omega(|x|/c^2)$.

The next theorem shows that,  at least for some standard machine $U$,  we can not compute  lists of subexponential size containing a program of
length exactly $\C(x)$.

\begin{theorem}\label{th:computeSetsShortest}
There exists a standard\/\footnote{The construction implies the existence of such $U$ with a stronger universality property:
for every machine $V$ there exists a string $w_V$ such that $U(w_Vp|z) = V(p|z)$ for all $p,z$.}
machine $U$ such that for every  computable $f$ that is a  list-approximator for $0$-short programs,
\[
|f(x)| \ge 2^{|x|-O(1)},
\]
for infinitely many $x$. (The constant hidden in $O$-notation depends on the function $f$.)\footnote{
Independently, this result was obtained by Frank Stephan (personal communication).}
 \end{theorem}
The construction of $U$ can be easily adapted to show that
for every $c$ there
is a standard machine $U_c$ satisfying the theorem for $c$-short programs.
This exponential lower bound  does not hold for all standard machines (see Remark~\ref{rem1} below).

\textbf{A few words about the proof technique and paper organization.}
Essentially, list-approximability reduces to a weak form of (polynomial-time) computable compression to (close to) minimal length, such that decompression is computable. Inspired by~\cite{mus-rom-she:j:muchnik}, we achieve such compression by using unbalanced bipartite graphs which allow on-line matching (one receives requests to match left nodes and each request has to be satisfied before seeing the next one).
 The connection between list-approximability and graphs with on-line matching  is studied
in Section~\ref{matching}.  In the proofs of upper bounds we use non-explicit and explicit bipartite graphs of small degree that have expander-like properties
and hence have good matching abilities. The lower bounds are based on lower bounds for the left degree of such  graphs.
The upper bounds, i.e., Theorem~\ref{t:complist} and Theorem~\ref{t:polytimelist}, are proved in Section~\ref{s:ub}.
 The lower bounds, i.e., Theorem~\ref{th:quadraticlistt} and Theorem~\ref{th:computeSetsShortest}, are proved in Section~\ref{s:lb}.
In Section~\ref{s:other}, we observe that our construction  can  be used to improve Muchnik's
Theorem~\cite{muc:j:condcomp,mus-rom-she:j:muchnik}, and a  result concerning
distinguishing complexity~\cite{bfl:j:boundedkolmogorov}.

\section{List approximators for short programs and on-line matching}\label{matching}

We show that the problem of constructing approximators for short programs is equivalent to
constructing families of bipartite graphs of a certain type.
Let a bipartite graph $G = (L,R,E\subset L\times R)$ be given,
where the set $L$ of left nodes and the set $R$ of right nodes consist of binary strings.
Assume that we receive ``requests for matching'' in the graph, each request having the form  (a binary string $x\in L$, a natural number $k$).
Such a request means that we have to provide to the left node $x$ a match of length at most $k$ or slightly more.
It might happen that we receive a request $(x,k)$ and later a request $(x,k')$ with the same $x$,  but another $k'<k$.
In this case we are allowed to match $x$ to a  second right node, thus $x$ has now two matching right nodes.
Assignments cannot be changed and different right nodes must have different
matches (however any left node $x$ may have different matches).  We will sometimes call right nodes \emph{hash-values}.

\begin{definition}\label{overhead}
Let $c(n)$ be a function of $n$
with natural values. A bipartite graph whose left and right nodes are binary strings
\emph{has matching with overhead $c(n)$} if
the following holds. For every set $S$ of pairs  $(x \in L, k)$
having at most $2^k$ pairs with the second component $k$ (for all $k$) one can choose
for every pair $(x,k)$ in $S$ a neighbor $p(x,k)$ of $x$ so that
$|p(x,k)|\le k+c(|x|)$ and $p(x_1,k_1)\ne p(x_2,k_2)$ whenever $x_1\ne x_2$. If this is done,
we will say that $p(x,k)$ \emph{matches} $x$.

A bipartite graph
\emph{has on-line matching with overhead $c(n)$}
if this can be done in the on-line fashion: requests for matching
$(x,k)$ appear one by one and we have to find $p(x,k)$ before the next
request appears. All the made assignments cannot be changed.
\end{definition}

A bipartite graph is \emph{(polynomial time) computable} if given a left node $x$ we can compute (in polynomial time)
the list of all its neighbors.

\begin{theorem}\label{th3}
Assume there is a  computable
graph with $L=\zo^*$ where the left node $x$ has degree $D(x)$ and
which has on-line matching with overhead $c(n)$.
Assume further that the matching strategy is computable.
Then for every standard machine $U$ there exists a computable function $f$ that for any $x$ produces a
list with  $D(x)$ many elements containing a program $p$ for $x$ of length $|p| = C_U(x) + c(|x|)+O(1)$.
If the graph is polynomial time computable then the function $f$ is polynomial time computable, too
\end{theorem}
\begin{proof}
Run the optimal machine  $U(q)$ in parallel for all strings $q$.
Once $U(q)$ halts with the result $x$
we pass the request $(x,|q|)$ to the matching
algorithm in the graph and find a hash value $p$ of length at most $|q|+c(|x|)$ for $x$.

By construction, every string $x$ is matched to a string $p$ of length
at most $C_U(x)+c(|x|)$. Each right node is matched to at most one node in the graph.
Hence there is a machine $V$ such that $V(p)=x$ whenever $p$ is matched to $x$.
Thus for every string  $x$ there is a neighbor $p$ of  $x$ with
$|p|\le C_U(x)+c(|x|)$ and $V(p)=x$. As $U$ is a standard machine, there is a (polynomial time) computable
function $t$ with $U(t(p))=V(p)$ and $|t(p)|\le|p|+O(1)$.
Let $f(x)$ be the list consisting of  $t(p)$ for all  the neighbors $p$ of $x$ in the graph. By  construction
$|f(x)|=D(x)$ and we are done.
\end{proof}

\begin{remark}\label{rem1}
If $c(n)=c$ is a constant function, then we can construct a standard machine
$U_1$ which has a computable
approximator for 0-short programs with lists  of size $D(x)$.
To this end let $U_1(0p)=V(p)$ and  $U_1(1^{c+2}p)=U(p)$ and let $t(p)=0p$ in the construction
of $f$ in the proof of the above theorem. By Theorem~\ref{th1a} below there is a graph having on-line matching
with constant overhead and degree $O(|x|^2)$. Thus there is a standard machine $U_1$ which has a computable
approximator  for 0-short programs with lists  of size $O(|x|^2)$.
\end{remark}

There is also a reduction in the other direction.

\begin{theorem}\label{th3a}
Assume that $c(n)$ is computable function and
there are an optimal machine $U$
and a computable function $f$ that for any $x$ produces a
finite list containing a program $p$ for $x$ of length $|p| \le C_U(x) + c(|x|)$.
Consider the bipartite graph $G$ with $L=\zo^*$
where the neighbors of node $x$ are all strings from $f(x)$.
Then $G$  has on-line  matching with overhead $c(|x|)+O(1)$.
\end{theorem}
\begin{proof}
For each $n$ let $G_n$ be the subgraph of $G$ with $L=\zo^{\le n}$.
W.l.o.g. we assume that all strings in $f(x)$ have length at most $|x|+O(1)$
and hence the graph $G_n$ is finite.
We claim that $G_n$ has on-line matching with overhead $c(|x|)+O(1)$ for all $n$,
(where the $O(1)$ constant does not depend on $n$).

We first show that this implies the theorem.
Suppose that $M_1, M_2, \dots$ are on-line matching strategies for graphs $G_1, G_2, \dots$
It suffices to convert them to strategies $M'_1, M'_2, \dots$ for $G_1, G_2, \dots$
such that for all $i$, $j > i$ strategy $M'_j$ is an extension of $M'_i$,
i.e. on a series of requests only containing nodes from $G_i$,
strategy $M'_j$ behaves exactly as $M'_i$.
Because each $G_n$ finite, there are only finitely many different matching strategies for $G_n$.
Hence, there is a strategy $M'_1$ that equals the restriction of $M_n$ to $G_1$ for infinitely many $n$.
Therefore there is also a strategy $M'_2$ that is an extension of $M'_1$ and
equals the restriction of $M_n$ to $G_2$ infinitely often, and so on.

It remains to show the claim.
For the sake of contradiction assume that for every constant $i$ there is $n$
such that $G_n$ has not on-line matching with overhead  $c(|x|)+i$,
(and $f$ is a list-approximator for $c(|x|)$-short programs on $U$).
Because $G_n$ is finite, for all $n$ and $c$ one can find
algorithmically (using an exhaustive search) whether $G_n$ has on-line matching
with overhead  $c(|x|)+i$ or not. One can also find a winning strategy for that player
who wins (``Matcher'' or ``Requester'').
Therefore for every $i$ we can algorithmically find the first $n$
such that the graph $G_n$ has not on-line matching with overhead  $c(|x|)+i$
and the corresponding winning strategy for Requester for $G_n$.

Let that strategy play against the following ``blind'' strategy of Matcher.
Receiving a request $(x,k)$ the Matcher runs $U(p)$ for all $p\in f(x)$,  $|p|\le k+c(|x|)+i$,  in parallel.
If for some $p$, $U(p)$ halts with the result $x$, he matches the first such $p$ to $x$ and proceeds to the next
request. Otherwise the request remains not fulfilled.

Consider the following machine $V$. On input $(q,i)$ with $|q|=k$ it finds
the first $G_n$ such that the graph $G_n$ has not on-line matching with overhead  $c(|x|)+i$ and a winning strategy for Requester,
and runs it against the blind strategy of Matcher. Then it returns $x$ where $(x,k)$ is the $q$th
request with the second component $k$.
As Requester wins, there is a request $(x,k)$ that
was not fulfilled.
We have
\begin{equation}\label{eq34}
C_U(x)\le C_V(x)+O(1)\le k+ 2\log i+O(1)\le k+ i
\end{equation}
(the last inequality holds for all large enough $i$).
As the request $(x,k)$
was not fulfilled, there is no $p$ in $f(x)$ with $|p|\le k+i+c(|x|)$. Due to~\eqref{eq34},
$f(x)$ has no $c(|x|)$-short program for $x$, a contradiction.
\end{proof}

From the technical point of view, our main contributions are the following theorems.

\begin{theorem}[Combinatorial version of Theorem~\ref{t:complist}]\label{th1a}
There is a computable graph with $L=\zo^*$ with left degree $D(x) = O(|x|^2)$
which has on-line matching with overhead $O(1)$.
\end{theorem}

\begin{theorem}[Combinatorial version of Theorem~\ref{t:polytimelist}]\label{th2}
There is a polynomial time computable
graph with $L=\zo^*$ with left degree $D(x) = \poly(|x|)$
which has on-line matching with overhead $O(\log |x|)$.
\end{theorem}

\begin{theorem}[Combinatorial version of Theorem~\ref{th:quadraticlistt}]\label{th1b}
In every graph $G$ with $L=\zo^n$
that has off-line matching with overhead $c$,
the maximal degree of left nodes is $\Omega(n^2/(c+O(1))^2)$.
\end{theorem}

Theorems~\ref{th1a}, \ref{th2}  and~\ref{th1b} imply Theorems~\ref{t:complist},
\ref{t:polytimelist} and~\ref{th:quadraticlistt}, respectively.
Moreover, our on-line matching strategy used in the proofs of Theorems~\ref{th1a} and~\ref{th2} are very simple:
receiving a new request of the form $(x,k)$ we just find the maximal $i\le k+c$ such that
there is a free hash-value of length $i$ and match  $x$ with the first neighbor of $x$, in some order, which is not used so far.

\section{The upper bounds}
\label{s:ub}
In this section we prove Theorems~\ref{th1a} and~\ref{th2}. We will need the notion
of a graph with on-line matching, introduced in  \cite{mus-rom-she:j:muchnik}.

\begin{definition}\label{def2}
Say that a bipartite graph has \emph{matching up to $K$ with at most $M$ rejections},
if for any set of left nodes of size at most $K$ we can drop at most $M$ its elements
so that there is a matching in the graph for the set of remaining nodes.
A graph has  an \emph{on-line matching up to $K$ with at most $M$ rejections}
if we can do this in on-line fashion.
For $M=0$ we say that the graph has \emph{matching up to $K$}.
A bipartite graph is called a \emph{$(K,K')$-expander},
if every set of $K$ left nodes has at least $K'$ distinct neighbors.
\end{definition}

Graphs that have matching up to $K$ are closely related to $(K,K)$-expanders. Indeed,
any graph having off-line matching up to $K$ is obviously a  $(K',K')$-expander
for all $K'\le K$. Conversely, by Hall's theorem~\cite{hall} any graph which is a  $(K',K')$-expander
for all $K'\le K$ has off-line matching up to $K$.

In \cite{mus-rom-she:j:muchnik} it was shown that a reduction from expanders to \emph{on-line}
matching is also possible. More specifically,
every family of $(2^i,2^i)$-expanders, one for each  $i<k$, sharing the same set $L$ of left
nodes can be converted into a graph with the same set $L$ of left nodes that has on-line
matching up to $2^k$, at the expense of multiplying the degree by $k$ and increasing hash-values by 1.
(We will present the construction in the proof of Theorem~\ref{th7}.)

The connection between graphs with matching up to $K$ and graphs with matching with overhead $c$ is the following.
If a graph $G$ has  (on-line) matching with overhead $c$ then removing from $G$ all left nodes of length different from $n$ and
all right nodes of length more than $k+c(n)$ we obtain a graph with (on-line) matching up to $2^k$.
On the other hand, assume that for some  $n$ for all $k<n$ we have a graph $G_{n,k}$ with $L=\zo^n$  and $R=\zo^{k+c(n)}$ which
has (on-line) matching up to $2^k$. Then the union $G_n$ of $G_{n,k}$ over all $k<n$ has (on-line)
matching with overhead $c$, provided  all requests $(x,k)$ satisfy $k<|x|$. At the expense of increasing
the degree and $c$ by 1, the graph $G_n$ can be easily modified to have (on-line)
matching with overhead $c$ unconditionally: append 0 to all right nodes of $G_n$ and for every
$x\in\zo^n$ add a new right node $x1$ connected to $x$ only.

In~\cite{mus-rom-she:j:muchnik} it is observed that every $(2^{k-1},2^{k-1})$-expander
has on-line matching up to $2^k$ with at most $2^{k-1}$ rejections. We need a slight generalization if this fact.

\begin{lemma}
Every $(2^{k-\ell},2^{k}-2^{k-\ell})$-expander
has on-line matching up to $2^k$ with at most $2^{k-\ell}$ rejections.
\end{lemma}
\begin{proof}
Use the following greedy  strategy
for on-line matching: each time a left vertex is received, check if it has a neighbor
that was not used yet. If yes, any such neighbor is selected as the match for that node.
Otherwise, the node is rejected.

For the sake of contradiction, assume that the number of rejected nodes is more
than $2^{k-\ell}$. Choose from them exactly $2^{k-\ell}$ rejected nodes.
By expansion property, they have at least $2^{k}-2^{k-\ell}$ neighbors and
all those neighbors are used by the greedy strategy (otherwise the node having a non-used neighbor
would not be rejected). Thus we have at least $2^{k}-2^{k-\ell}$ matched left nodes
and more than $2^{k-\ell}$ rejected nodes. Thus we have received more than $2^{k}$ requests.
\end{proof}

In particular, every  $(2^{k},2^{k})$-expander has on-line matching up to $2^{k+1}$ with at most $2^{k}$ rejections.
For Theorem~\ref{th1a} we will use non-explicit such graphs, for Theorem~\ref{th2} we will need
explicit such graphs, which we obtain from the disperser of~\cite{ats-uma-zuc:j:expanders}.

Assume that for every $n$ and $k<n$ we are given a $(2^k,2^k)$-expander $G_{n,k}$
with $L=\zo^n$, $R=\zo^{k+c(n)}$ and the degree of all left nodes is at most $D(n)$.
Assume further that given $n,k$ and a left node $x$ in $G_{n,k}$
we can algorithmically find the list of all neighbors of $x$ in $G_{n,k}$.

\begin{theorem}\label{th7}
Given a family of expanders as above we can construct
a computable graph $G$ with $L=\zo^*$ that has on-line matching with overhead
$c(n)+O(\log n)$ and the degree of each left node is $O(D(n)n)$.
The matching strategy for $G$ is computable.
Moreover, if given $n,k$ and a left node $x$ in $G_{n,k}$ we can find the list
of all neighbors of $x$ in time $\poly(n)$ then $G$ is polynomial time computable.
\end{theorem}
\begin{proof}
The main tool is borrowed from~\cite{mus-rom-she:j:muchnik}:
all the graphs $G_{n,k}$ share the same set of left nodes while their sets of right nodes
are disjoint. Let $H_{n,k}$ denote the union of $G_{n,i}$ over all $i<k$.
Then  $H_{n,k}$ has on-line matching up to $2^k$ (without
rejections).  Indeed, each input left node is first given to the matching
algorithm for $G_{n,k-1}$ (that has on-line matching up to $2^k$ with at most $2^{k-1}$ rejections)
and, if rejected is given to the matching algorithm for
$G_{n,k-2}$ and so on.

Using this construction we can prove the theorem with slightly worse parameters as claimed.
To this end identify right nodes of the graph   $H_{n,k}$ with strings of length $k+c(n)+1$
(the number of right nodes of  $H_{n,k}$ does not exceed the sum of geometrical series $2^{k+c(n)}+2^{k+c(n)-1}+\dots<2^{k+c(n)+1}$).
The degree of $H_{n,k}$ is $D(n)k$.

Recall the connection between matching up to $2^k$ and matching with overhead (the third paragraph
after Definition~\ref{def2}).
We see that the family $H_{n,k}$ can be converted into
a graph $H_n$ with $L=\zo^n$ and degree $D(n)n(n-1)/2+1$ having on-line matching  with overhead $c(n)+2$.
Finally, prepend each right nodes of $H_n$ by a $O(\log n)$-bit prefix code of the number $n$
and consider the union of all $H_n$. The resulting graph has on-line matching
with overhead $c(n)+O(\log n)$, its set of left nodes is $\zo^*$ and the degree
of every left node of length $n$ is $O(D(n)n^2)$.

Now we will explain how to reduce the degree to $O(D(n)n)$.
Consider four copies of $G_{n,k-1}$  with the same set $L$ of left nodes
and disjoint sets of right nodes (say append 00 to every right node to get the first
copy, 01 to get the second copy and so on). Their union is a
$(2^{k-1},2^{k+1})$-expander, and hence has matching up to $2^{k+1}$ with at most $2^{k-1}$ rejections.  \footnote{One can also
consider the union of $G_{n,k-1}$ and $G_{n,k}$, which also   has matching up to $2^{k+1}$ with at most $2^{k-1}$ rejections.}
Its left degree is $4D(n)$ and the length of right nodes is $k+c(n)+2$.
Replace in the above construction of $H_n$ the graph $H_{n,k}$ by this graph.
Thus the left degree of $H_n$ becomes $O(D(n)n)$ in place of $O(D(n)n^2)$.
It remains to show that (the union of all graphs) $H_n$ has still on-line matching with overhead  $c(n)+O(\log n)$

Again the matching strategy is greedy. Once we receive a request $(x,k)$ with $|x|=n$, we match
$x$ to $1x$ if $k\ge n$. Otherwise we pass $x$ to the matching algorithm
in  $H_{n,k}$.
If the algorithm rejects $x$, we pass $x$  to the matching
algorithm in $H_{n,k-1}$ and so on.
We claim that we eventually find a match in one of
the graphs $H_{n,i}$ for $i\le k$.
To prove the claim  it suffices to show that the
matching algorithm for $H_{n,k}$ receives
at most $2^{k+1}$ input strings. This is proved by a downward induction on $k$ (for any fixed $n$).
For $k=n-1$ this is obvious: we try to match
in $H_{n,n-1}$ up to $2^{n-1}$ strings.
The induction step: by induction hypothesis the matching algorithm for
$H_{n,k+1}$ receives at most $2^{k+2}$ input strings an thus rejects at most $2^{k}$ of them.
The matching algorithm  for $H_{n,k}$ thus receives at most $2^{k}$ rejected strings and at most $2^{k}$ new ones,
coming from requests of the form $(x,k)$.
\end{proof}

\subsection{Proof of Theorem~\ref{th1a}}
\label{s:complist}

A weaker form of Theorem~\ref{th1a} can be derived from Theorem~\ref{th7}
and the following lemma from~\cite{muc:j:condcomp}.

\begin{lemma} \label{l:onlineMatching}
For all $n$ and $k<n$, there exists a  $(2^{k},2^{k})$-expander with $L=\zo^n$,  $R=\zo^{k+2}$  and
all left nodes have degree at most $n+1$.
\end{lemma}

\begin{proof}
We use the probabilistic method, and for each left node we choose its $n+1$ neighbors at random:
all neighbors of each node are selected independently
among all $2^{k+2}$ right nodes with uniform distribution,
and the choices for different left nodes
are independent too.
We show that  expansion property is satisfied with positive probability. Hence there exists at least one
such graph. To estimate the probability that the property is not satisfied,
consider a pair of sets
$L'$ and $R'$ of left and right nodes, respectively, of sizes $2^{k},2^{k}-1$.
The probability that the neighbors of all nodes in $L'$ belong to $R'$ is upper-bounded by $(1/4^c)^{(1/c)(n+c)2^{k}} = (1/4)^{(n+c)2^k}$.
The total probability that expansion condition is not satisfied, is obtained by summing over all such $L',R'$, i.e.
$$
\left(\frac{1}{4}\right)^{(n+1)2^{k}} (2^n)^{2^{k}} (2^{k+2})^{2^{k}-1}\le
\left(\frac{2^n2^{k+2}}{4^{n+1}}\right)^{2^{k}}\le
\left(\frac{2^n2^{n+1}}{4^{n+1}}\right)^{2^{k}}=
\left(\frac{1}{2}\right)^{2^{k}}<1.\qed
$$
\renewcommand{\qed}{}
\end{proof}

\begin{remark}
By the very same construction we can obtain
a graph with $L=\zo^n$,  $R = \zo^{k+2}$,  $D=n+1$
that is a $(t,t)$-expander \emph{for all} $t\le 2^{k}$.
Indeed, the probability that a random graph is not $(t,t)$-expander
is at most $\left(\frac{1}{2}\right)^{t}$ (we may replace $2^k$ by $t$ in the above
formulas). By union bound, the probability that it happens for some $t\le 2^k$ is at most
the sum of geometric series   $\sum_{t=1}^{2^k}\left(\frac{1}{2}\right)^{t}<1$.
By Hall's theorem, this graph has off-line matching up to $2^k$.
An interesting open question is whether there is a graph with the same parameters, i.e. $L=\zo^n$,  $R = \zo^{k+O(1)}$,
$D=O(n)$, that has  \emph{on-line} matching up to $2^k$.
\end{remark}

From this lemma and Theorem~\ref{th7} we obtain a computable
graph with on-line matching with overhead  $O(\log n)$, degree $O(|x|^2)$ and $L=\zo^*$
We now need to replace the $O(\log n)$ overhead by $O(1)$. Recall the $O(\log n)$ appeared from the prefix code of
$n$ added to hash values. To get rid of it we need a computable graph
$F_k$ in place of previously used $G_{n.k}$ with the same parameters but with $L=\zo^{>k}$,
and not $L=\zo^n$.  Such a graph is constructed in the following

\begin{lemma}
\label{l:compositeMatching}
For every $k$ there is a computable bipartite graph $F_{k}$ with $L=\zo^{\ge k}$, $R=\zo^{k+3}$
that is a $(2^k,2^k)$-expander and  the degree of every left node $x$ is $O(|x|)$.
\end{lemma}

\begin{proof} \marginpar{Reorganized the proof a bit.}
  We first build such a graph with left nodes being all strings of length between $k$ and $K=2^{k+3}$.
This is again done by probabilistic method: we choose $|x| + 3$ neighbors of every node $x$ independently.
Let  $L_i$ stand for all left nodes of
length $i$. For any $i \in k, \dots, K$, the probability that all elements  of a fixed $L' \subset L_i$
are mapped to a fixed set of size at most $2^k-1$
at the right is at most $\left(\frac{1}{2^3}\right)^{(i + 3)|L'|}$.
The probability that some $t_i$ elements
in $L_i$ are mapped into a fixed set of $2^k-1$ elements at the right is bounded by
\[
2^{it_i} \left( \frac{1}{2^{3}} \right)^{(i+3)t_i} = \left( \frac{1}{2^{2}} \right)^{it_i} \left( \frac{1}{2^{3}} \right)^{3t_i}
\le \left( \frac{1}{2^{2}} \right)^{(i+3)t_i + t_i}\le \left( \frac{1}{2^{2}} \right)^{( k+3)t_i + t_i}
= \left( \frac{1}{K} \right)^{2t_i}\left( \frac{1}{2} \right)^{2t_i}.
\]
If $\sum_{i=k}^K t_i = t$ with $t = 2^k$,
the probability that the union of neighbors of
$t_k$ elements in $L_k$, $t_{k+1}$ elements in $L_{k+1}$, \dots , and $t_K$ elements in $L_K$
are mapped to a fixed set of size at most $2^k-1$ is bounded by
$\prod_i\left( \frac{1}{2K} \right)^{2t_i}=\left( \frac{1}{2K} \right)^{2t}$.
Multiplying by the number $K^{2^k-1} \le K^{t}$ of different right sets of size $K-1$,
and multiplying by the number $K^t$ of different solutions to the equation $\sum_{i=k}^K t_i = K$,
we find
\[
\left( \frac{1}{2K} \right)^{2t} K^{t} \; K^{t} \le \left( \frac{1}{4} \right)^t < 1.
\]
Hence, the total probability to randomly generate a graph that is not an expander is strictly less than $1$.
Therefore, a graph satisfying the conditions must exist, and can be found by exhaustive search.

On the left side, we now need to add the strings of length larger than $K = 2^{k+3}$.
These nodes are connected to all
the  nodes on the right side. Thus the degree of every such node $x$  is $2^{k} \le |x|/2^{3} \le O(|x|)$
and we are done.
\end{proof}

\begin{remark}
By the very same construction we can obtain
a graph with $L=\zo^{\ge k}$, $R=\zo^{k+3}$,  $D=O(n)$
that is a $(t,t)$-expander \emph{for all} $t\le 2^{k}$
and thus has off-line matching up to $2^k$
(use the union bound over all $t\in\{k,\dots,K\}$).
An interesting open question is whether there is a graph with the same parameters that has  \emph{on-line} matching up to $2^k$.
\end{remark}

Now we can finish the proof of Theorem~\ref{th1a}.
Appending all 2-bit strings to all the right nodes of the graph $F_{k-1}$ (and thus increasing the degree 4 times)
we obtain a $(2^{k-1},2^{k+1})$-expander $H_{k}$. The union of $H_{k}$ over all $k$ is a computable graph, whose
left degree is $O(|x|^2)$,
and the set of left nodes is $\zo^*$. It has on-line matching with constant overhead.
This is proved by the downward induction, as in Theorem~\ref{th7}. Indeed,
by step $s$ in the matching,  there are only finitely many requests for matching.
By a downward induction on $k$ we can again prove that the number of
matching requests in $H_k$ is at most $2^{k+1}$. Now the base of induction
is the maximal $k$ for which
there has been at least one request for matching in $H_k$  up to step $s$.
We conclude that the request made at step $s$ is satisfied and, since this holds for every $s$, we are done.

\subsection{ Proof of  Theorem~\ref{th2}}

By Theorem~\ref{th7} we have to construct for every $k\le n$
an explicit $(2^k,2^k)$-expander of left degree $\poly(n)$, with $2^n$ left nodes and $\poly(n)2^k$ right nodes.
A graph is \emph{explicit} if there is an algorithm that on input $x \in \zo^n = L$ lists in $\poly(n)$ time  all the neighbors of $x$.

The proof relies on the explicit disperser graphs of  Ta-Shma, Umans, and Zuckerman from Theorem~\ref{t:tuz} below.
\begin{definition}
A bipartite graph $G = (L,R,E)$ is a \emph{$(K, \delta)$-disperser}, if every subset
$B \subseteq L$ with $|B| \geq K$  has at least $(1-\delta)|R|$ distinct neighbors.
\end{definition}
\begin{theorem}
\label{t:tuz} [Ta-Shma, Umans, Zuckerman~\cite{ats-uma-zuc:j:expanders}]
For every $K,n$ and constant $\delta$,
there exists explicit $(K, \delta)$-dispersers
$G = (L=\zo^n, R= \zo^m, E \subseteq L \times R)$ in which every node in $L$ has degree
$D=\poly(n)$ and $|R| =\frac{ \alpha K D}{n^3}$, for some constant $\alpha$.
\end{theorem}

Given $n$ and $k$ we  apply this theorem to $K=2^k$ and $\delta=1/2$.
We obtain a $(2^k, \frac{\alpha 2^k D}{2n^3})$-expander with degree $D=\poly(n)$, $L=\zo^n$  and
$|R| = \frac{\alpha K D}{n^3}$.
Consider $t=\max\{1,\lceil \frac{2n^3}{\alpha D}\rceil\}$ disjoint copies of this graph and identify left
nodes of the resulting graphs (keeping their sets of right nodes disjoint).
We get an explicit  $(2^k, 2^k)$-expander with $2^n$ left and $2^{k}\poly(n)$ right nodes
and degree $\poly(n)t=\poly(n)$.

\section{The lower bounds}\label{s:lb}

\subsection{Proof of Theorem~\ref{th1b}}
Assume that $G$ has off-line matching with overhead  $c$.
Let $G[\ell,k]$ denote the induced graph that is obtained from $G$
by removing all right nodes of length more than $k$ or less than $\ell$.
The graph $G[0,k+c]$ is obviously a $(2^k,2^k)$-expander for every $k$.
As there are less than $2^{k-1}$ strings of length less than $k-1$,
it follows that the graph   $G[k-1,k+c]$ is a $(2^k,2^{k-1}+1)$-expander.

The next lemma  inspired by \cite{kovari1954} (see \cite[Theorem 1.5]{rad-tas:j:extractors})
shows that any such expander must have large degree.

\begin{lemma}\label{l1}
Assume that a bipartite graph with $2^\ell$ left nodes and $2^{k+c}$ right nodes
is a $(2^k,2^{k-1}+1)$-expander. Then there is a left
node in the graph with degree more than $D=\min\{2^{k-2}, (\ell-k)/(c+2)\}$.
\end{lemma}
\begin{proof}
For the sake of contradiction assume that all left nodes have degree
at most $D$ (and w.l.o.g. we may assume that all degrees are exactly $D$).
We need to find a set of right nodes $B$ of size $2^{k-1}$
and $2^k$ left nodes all of whose neighbors lie in $B$.
The set $B$ is constructed via a probabilistic construction. Namely, choose $B$ at random (all $\binom{2^{k+c}}{2^{k-1}}$
sets have equal probabilities). The probability that all neighbors of a fixed left node are in $B$
is equal to
$$
\frac{\binom{2^{k+c}-D}{2^{k-1}-D}}{\binom{2^{k+c}}{2^{k-1}}}=
\frac{2^{k-1}(2^{k-1}-1)\cdots(2^{k-1}-D+1)}{2^{k+c}(2^{k+c}-1)\cdots(2^{k+c}-D+1)}.
$$
Both products in the numerator and denominator have $D$ factors and the ratio of corresponding factors is
at least
$$
\frac{2^{k-1}-D+1}{2^{k+c}-D+1}\ge 2^{-c-2}
$$
(the last inequality is due to the assumption $D\le 2^{k-2}$).
Thus the probability that all neighbors of a fixed left node are in $B$ is at least
$2^{-D(c+2)}$. Hence the average number of left nodes having this property is at least
$2^{\ell-D(c+2)}$, which is greater than or equal to $2^k$ by the choice of $D$.
Hence there is $B$ that includes neighborhoods of at least $2^k$ left nodes,
a contradiction.
\end{proof}

This lemma states that at least one left node has large degree. However, it implies more:
if the number of left nodes is much larger than $2^\ell$, then
almost all left nodes must have large degree. Indeed, assume that a bipartite graph with
$2^{k+c}$ right nodes is a $(2^k,2^{k-1}+1)$-expander.
Choose $2^\ell$ left nodes with smallest degree and apply the lemma
to the resulting induced graph (which is also  a $(2^k,2^{k-1}+1)$-expander).
By the lemma, in the original graph all except for less than $2^\ell$ nodes have degree
more than $D=\min\{2^{k-2}, (\ell-k)/(c+2)\}$.

Choose $n/4<k\le n/2$. As noticed,
the graph $G[k-1,k+c]$ is a $(2^k,2^{k-1}+1)$-expander and has less than $2^{k+c+1}$ right nodes.
By Lemma~\ref{l1} (applied to $\ell=3n/4$, $k$, $c+1$), all except for at most $2^{3n/4}$
left nodes of $G[k-1,k+c]$  have degree at least $n/4(c+3)$.

Pick now $\ell$ different $k$'s that are $c+2$ apart of each other, where $\ell$ is about  $n/(4(c+2))$.
For most left nodes  for all picked $k$
there are   $n/4(c+3)$ edges from those nodes in $G[k-1,k+c]$. As all picked $k$'s are $c+2$ apart of each other,
the degree of all those nodes is $\Omega(n^2/(c+3)^2)$.

\subsection{Proof of Theorem~\ref{th:computeSetsShortest}.}

The size of list-approximators is closely related to total conditional Kolmogorov complexity, which was first introduced by A.~Muchnik
and was used in~\cite{SSS,BauwensPhd}.  {\em Total conditional Kolmogorov complexity} with respect to $U$ is defined as:
\[
\CT_U(u|v) = \min \left\{ |q| : U(q,v) = u \wedge \forall z\left[ U(q,z) \downarrow \right] \right\} \,,
\]
where $U(q,z) \downarrow$ means that $U(q,z)$ halts.
If $U$ is a standard machine then $\CT_U(u|v)\le\CT_V(u|v)+c_V$ for every machine $V$.
The connection to list-approximators is the following:
\begin{lemma}
If $f$ is computable function that maps every string to a finite list of strings
then $\CT_U(p|x)\le \log|f(x)|+O(1)$ for any standard machine $U$ and every $p$ in $f(x)$. The constant in $O$-notation
depends on $f$ and $U$.
\end{lemma}
\begin{proof}
Let $V(j,x)$ stand for the $j$th entry of the list $f(x)$, if $j\le  |f(x)|$, and
for the empty string (say) otherwise. Obviously $\CT_V(p|x)\le \log|f(x)|$ for all $p$ in $f(x)$. Hence
$\CT_U(p|x)\le \log|f(x)|+O(1)$.
\end{proof}

Thus to prove the theorem it suffices to construct
a standard machine $U_0$ such that
for infinitely many $x$ every 0-short $p$ for $x$ with respect to $U_0$ satisfies $\CT_U(p|x)\ge |x|-O(1)$.
To this end we fix any standard machine $U$ and construct another machine $V$
such that for some constant $d$ and for every integer $k$
there are strings $p,x$ such that:\\
(a) $p$ is the unique 0-short program for $x$ with respect to $V$,\\
(b) $C_U(x)\ge k$,\\
(c) $|x|=|p|=k+d$,\\
(d) $\CT_U(0p|x)\ge k$.

Once such $V$ has been constructed, we let
$U_0(0q|z)=V(q|z)$ and $U_0(1^{d+2}q|z)=U(q|z)$.
The latter equality guarantees that $U_0$ is a standard machine. And both equalities
together with items (a), (b) and (c) imply that $0p$ is the unique 0-short program for $x$
with respect to $U_0$. Finally, item (d) guarantees that its total complexity conditional to $x$
is at least $|x|-d-1$.

The construction of $V$ can be described in game terms.
(The game-based technique in recursion theory was introduced by Lachlan~\cite{Lachlan} and
further developed by A.Muchnik and others~\cite{KolmogorovGames,VerSurvey,ShenCie12}.)

 \textbf{Description of the game.}
The game has integer  parameters $k,d$ and is played on a rectangular grid with $2^{k+d}$ rows and $2^{k+d}$ columns.
The rows and columns are identified with strings of length $k+d$.
Two players, Black and White, play in turn. In her turn White
can either pass or put a pawn on the board. White can place at most one pawn in each row
and at most one pawn in each column. Once a pawn is placed, it can not be moved nor removed.
In his turn Black can either pass, or choose a column and \emph{disable} all its cells, or
choose at most one cell in every column and \emph{disable} all of them.
If a player does not pass, we say that she/he \emph{makes a move}.
Black is allowed to make less that $2^{k+1}$ moves.
The game is played for an infinite time and
White looses if at some point after her turn, all her pawns are in disabled cells.

We will show that, for $d=3$, for every $k$,  White wins this game. More specifically, there is a winning strategy
for White that is uniformly computable given $k$. Assume that this is done. Then consider the following ``blind''
strategy for Black: start enumeration of all strings $x$ with $C_U(x)<k$ and all strings $q$ of length less than
$k$ such that $U(q,x)\downarrow$ for all $x$ of length $k+d$.
That enumeration can be done uniformly in $k$. In his $t$th turn Black:
disables all cells in the $x$th column, if
on step $t$ in this enumeration a new $x$ of length $k+d$  with $C_U(x)<k$ appears;
disables all cells $(p,x)$ with $|x|=|p|=k+d$, $U(q,x)=0p$, if
on step $t$  a new string $q$ of length less than
$k$ appears such that $U(q,x)\downarrow$ for all $x$ of length $k+d$;
and passes if none of these events occurs.
Note that the total number of Black's moves is less that $2^k+2^k=2^{k+1}$, as required.

Now consider the following machine $V(p)$: let $k=|p|-d$ and let
the White's computable winning strategy play against Black's blind strategy.
Watch the play waiting until White places a pawn on a cell $(p,x)$ in $p$th row. Then output
$x$ and halt. Note that such $x$ is unique (if exists), as White places at most one pawn in each row.
And that cell $(p,x)$ satisfies all the requirements (a)--(d).
Thus it suffices to design a computable winning strategy for White.

 \textbf{A winning White's strategy.}
The strategy is a greedy one. In the first round White places a pawn in any cell. Then she waits until that cell becomes
disabled. Then she places the second pawn in any enabled cell that lies in another row and another column and
again waits until that cell becomes disabled. At any time she chooses any enabled cell
that lies in a row and a column that both are free of pawns. In order to show that White wins, we just
need to prove that there is such cell. Indeed, Black makes less than
$2^{k+1}$ moves, thus White makes at most $2^{k+1}$ moves. On each of Black's moves at most
$2^{k+d}$ cells become disabled.  On each of White's moves at most $2^{k+d+1}$ cells becomes non-free because
either their column or row already has a pawn.
Thus if the total number of cells is more than
$$
2^{k+1}2^{k+d}+2^{k+1}2^{k+d+1}=6\cdot2^{2k}2^d,
$$
we are done. The total number of cells is $2^{k+d}2^{k+d}=2^{2k}2^{2d}$.
As $2^{2d}$ grows faster that $6\cdot2^d$, for large enough $d$ (actually for $d=3$)
the total number of cells is larger than the number of disabled or non-free cells.
The theorem is proved.
\medskip

Note that changing the construction a little bit
we can prove the same statement for $c$-short programs for every $c$.
To this end we just need to let $U_0(1^{c+d+2}q)=U(q)$ instead of
 $U_0(1^{d+2}q)=U(q)$. The optimal machine $U_0$ constructed in this way depends on the choice of
$c$, which is inevitable by Theorem~\ref{t:complist}.

\section{Other applications of explicit graphs with on-line matching}
\label{s:other}

The two first applications are related with the resource bounded Kolmogorov complexity.
Recall a machine $U$ is called standard if for any machine $V$ there is a
total computable function $f$ such that $U(t(p),z)=V(p,z)$ and $|t(p)|\le |p|+O(1)$ for all $p,z$.
In this section we assume that  $t$ is polynomial time computable and that
running time of
$U(t(p),z)$ is bounded by a polynomial of the computation time of $V(p,z)$.
By $C_U^T(x|z)$ we denote the minimal length of $p$ such that
$U(p,z)=x$ in at most $T$ steps.

\medskip

\textbf{Muchnik's Theorem~\cite{muc:j:condcomp,mus-rom-she:j:muchnik}.}
Let $a$ and $b$ be strings such that $|a|=n$ and $C(a \mid b) = k$.
Then there exists a string $p$ such that (1) $|p| = k + O(\log n)$, (2) $C(p \mid a) = O(\log n)$, (3) $C(a \mid p,b) = O(\log n)$.

In our improved version, we replace (2) by (2') $C^{q(n)}( p \mid a) = O(\log n)$, where $q$ is a polynomial.

\begin{proof}
Fix an explicit graph with $L=\zo^*$, polynomial degree, and that has computable on-line matching
with logarithmic overhead. Given a string $b$
run the  optimal machine $U(q,b)$ in parallel for all $q$ and once for some $q$,  $U(q,b)$ halts with
the result $x$ pass the request $(x,|q|)$ to the matching algorithm in the graph.
It will return a neighbor $p$ of length at most $|q|+O(\log n)$ of $x$.
At some moment a shortest program $q$ for $a$ conditional to $b$ will halt
and we get the sought $p$.

As the graph is explicit and has polynomial degree, we
have  $C^{\poly(n)}(p\mid a)=O(\log n)$ (requirement (2)).
Requirement (1) holds by construction. Finally, $C(a \mid p,b) = O(\log n)$
as given $p$ and $b$ we may identify $a$ by running the above algorithmic process (it is important
that $a$ is the unique string that was matched to $p$).
\end{proof}

\textbf{Distinguishing complexity~\cite{bfl:j:boundedkolmogorov}.}

Let $V$ be a machine, $x$ a string and $T$ a natural number.
The \emph{distinguishing complexity $CD^T_V(x)$ with respect to $V$} is defined
as the minimal length of $p$ such that $U(p,x)=1$ ($p$ ``accepts'' $x$) in at most $T$ steps, and $U(p,x')=0$
for all $x'\ne x$ ($p$ ''rejects'' all other strings).
From our assumption for the standard machine $U$ it follows that for every machine $V$ there is a polynomial $f$ and a constant $c$ such
that $CD^{f(T)}_U(x)\le CD^T_V(x)+c$. Indeed, let $p$ is a shortest distinguishing program for $x$ working in $T$ steps
with respect to $V$. Then $t(p)$ is a program for $U$ that accepts $x$ in $\poly(T)$ steps and rejects all other strings.

For a set $A$ of binary strings let $A^{=n}$ stand for the set of all strings of length $n$ in $A$.

\begin{theorem}[\cite{bfl:j:boundedkolmogorov}]
For every function $\epsilon(n)$ (mapping natural numbers
to numbers of the form $1/$natural) computable in time  $\poly(n)$ there is a polynomial $f$ such that
for every set $A$, for all $x \in A^{=n}$ except for a fraction $\epsilon(n)$,
$CD^{f(n),A}_U(x) \leq \log|A^{=n}| + {\rm polylog}(n/\eps(n))$.
\end{theorem}

We mean here that the set $A$ is given to the standard machine $U$ as an oracle (so we assume that the standard machine is an oracle machine
and all the requirements hold for every oracle.)

In our improved version, we obtain $CD^{f(n),A}(x) \leq \log|A^{=n}|
+ O(\log(n/\eps(n)))$.

\begin{proof}
For our improvement we need for every $n$, $k\le n$ and $\eps$
a bipartite graph  $G_{n,k,\eps}$ with $L=\zo^n$, $R=\zo^{k+O(\log n/\eps)}$ and degree $\poly(n/\eps)$ that has the following property:
\begin{quote}
for every subset $S$ of at most $2^k$ left nodes
for every node $x$ in $S$ except for a fraction $\eps$ there is a right neighbor $p$ of $x$
such that $p$ has no other neighbors in $S$.
\end{quote}

Assume that we have such an explicit family of graphs $G_{n,k,\eps}$.
Explicit means that given $n$, $k$, $\eps$,  a left node $x$ and $i$ we can in polynomial time find
the $i$th neighbor of $x$ in  $G_{n,k,\eps}$.
Then we can construct
a machine $V$ that given a tuple $(p,i,n,k)$, a string $x$ and $A$ as oracle
verifies that $x$ is in $A^{=n}$ and that $x$ is the $i$-th neighbor of $p$ in $G_{|x|,k,\eps(n)}$.
If this is the case it accepts and rejects otherwise.
By the property of the graph, applied to $S=A^{=n}$ and $k=\lceil\log|S|\rceil$ we see that
$$
CD^{f(n),A}_V(x)\le|(p,i,n,k)|\le \log |A^{=n}|+O(\log n/\eps(n))
$$
for some polynomial $f(n)$ for all but a fraction $\eps(n)$ for $x\in A^{=n}$.
By the assumptions on $U$ the same inequality holds for $U$.

The graph $G_{n,k,\eps}$ is again obtained from the disperser of~\cite{ats-uma-zuc:j:expanders}.
Given $n$, $k$ and $\eps$ we  apply Theorem~\ref{t:tuz} to $K=2^k\eps$ and $\delta=1/2$.
We obtain a $(K, \frac{\alpha K D}{2n^3})$-expander with degree $D=\poly(n)$, $L=\zo^n$ and
$|R| = \frac{\alpha K D}{n^3}$.
Consider $t=\max\{1,\lceil \frac{2n^3}{\alpha D}\rceil\}$ disjoint copies of this graph and identify left
nodes of the resulting graphs (keeping their sets of right nodes disjoint).
We get an explicit  $(2^k\eps, 2^k\eps)$-expander with $2^n$ left and $2^{k}\poly(n)/\eps$ right nodes
and degree $D=\poly(n)t/\eps=\poly(n)/\eps$.

This graph, called $H_{n,k,\eps}$, has the following ``low-congestion property'':
\emph{for every set of $2^k$ left nodes $S$ for every node $x$ in $S$ except for a fraction $\eps$ there is a right neighbor $p$ of $x$
such that $p$ has at most $D/\eps$ neighbors in $S$.}

Indeed, the total number of edges in the graph originating in  $S$ is at most $|S|D$.
Thus less than $|S|D/(D/\eps)=|S|\eps$ right nodes are ``fat'' in the sense that they have more
than  $D/\eps$ neighbors landing in $S$. By the expander property of $H_{n,k,\eps}$ there are less than $\eps|S|$
left nodes in $S$ that have only fat  neighbors.

It remains to ``split'' right nodes of $H_{n,k,\eps}$ so that $D/\eps$ becomes 1.
This is done exactly as in~\cite{bfl:j:boundedkolmogorov}. Using the Prime Number Theorem, it is not hard
to show (Lemma 3 in~\cite{bfl:j:boundedkolmogorov}) that for every set $W$ of $d$ strings of length $n$
the following holds:
\emph{for every $x\in W$ there is a prime number $q\le 4dn^2$ such that $x\not\equiv x' \pmod q$
for all $x'\in W$ different from $x$} (we identify here natural numbers and their binary expansions).

We apply this lemma to $d=D/\eps$.
To every right node $p$ in $H_{n,k,\eps}$ we add a prefix code of two natural numbers $a,q$, both at  most
$4dn^2$, and connect a left node $x$ to $(p,a,q)$ if $x$ is connected to $p$ in $H_{n,k,\eps}$
and $x\equiv a \pmod q$. We obtain the graph $G_{n,k,\eps}$ we were looking for.
Indeed, for every $S$ of $2^k$ left nodes for all $x\in S$ but a fraction
of $\eps$ there is a neighbor $p$ of $x$ in $H_{n,k,\eps}$ that has at most $d=D/\eps=\poly(n)/\eps$
neighbors in $S$. Besides there is a prime $q\le 4n^2d= \poly(n)/\eps$ such that
$x\not\equiv x' \pmod q$
for all neighbors $x'$ of $p$ different from $x$. Thus the neighbor $(p,q,x \bmod q)$ of $x$ in   $G_{n,k,\eps}$
has no other neighbors in $S$.

The degree of $G_{n,k,\eps}$ is $D\times (4n^2D/\eps)^2=\poly(n)/\eps^2$. The number of right
nodes is
$$
(\poly(n)2^k/\eps)(4n^2D/\eps)^2=2^k\poly(n)/\eps^3.
$$
Thus right nodes can be identified with strings of length $k+O(\log n/\eps)$ and we are done.
\end{proof}

\medskip

\if01
\textbf{Compression of samplable sources, Theorem 6.1~\cite{tre-vad-zuc:j:compression}.} Let $X_n$ be a flat source with membership algorithm and $H(X_n) \leq k$. Then $X_n$ is compressible to length $k + {\rm polylog}(n-k)$ in time $\poly(n, 2^{n-k})$.

In our version, the compression length becomes $k + O(\log n)$.

\marginpar{We need a rigorous formulation and a proof}
\fi

\section{Acknowledgments} We are grateful to Andrei Romashchenko, Alexander (Sasha) Shen
for useful discussion.
We also thank Jason Teutsch for stimulating the investigation of
Theorem~\ref{t:complist} with higher precision than $O(\log |x|)$.