\documentstyle{article}
\hfuzz=1pt
\tolerance=1000
\emergencystretch=10pt

%%\input amssym.def
\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}}
\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil
\penalty50\hskip1em\null\nobreak\hfil\squareforqed
\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi}


\expandafter\ifx\csname amssym.def\endcsname\relax \else\endinput\fi
%
%  Store the catcode of the @ in the csname so that it can be restored later.
\expandafter\edef\csname amssym.def\endcsname{%
       \catcode`\noexpand\@=\the\catcode`\@\space}
%  Set the catcode to 11 for use in private control sequence names.
\catcode`\@=11
%
%  Include all definitions related to the fonts msam, msbm and eufm, so that
%  when this file is used by itself, the results with respect to those fonts
%  are equivalent to what they would have been using AMS-TeX.
%  Most symbols in fonts msam and msbm are defined using \newsymbol;
%  however, a few symbols that replace composites defined in plain must be
%  defined with \mathchardef.

\def\undefine#1{\let#1\undefined}
\def\newsymbol#1#2#3#4#5{\let\next@\relax
 \ifnum#2=\@ne\let\next@\msafam@\else
 \ifnum#2=\tw@\let\next@\msbfam@\fi\fi
 \mathchardef#1="#3\next@#4#5}
\def\mathhexbox@#1#2#3{\relax
 \ifmmode\mathpalette{}{\m@th\mathchar"#1#2#3}%
 \else\leavevmode\hbox{$\m@th\mathchar"#1#2#3$}\fi}
\def\hexnumber@#1{\ifcase#1 0\or 1\or 2\or 3\or 4\or 5\or 6\or 7\or 8\or
 9\or A\or B\or C\or D\or E\or F\fi}

\font\tenmsa=msam10
\font\sevenmsa=msam7
\font\fivemsa=msam5
\newfam\msafam
\textfont\msafam=\tenmsa
\scriptfont\msafam=\sevenmsa
\scriptscriptfont\msafam=\fivemsa
\edef\msafam@{\hexnumber@\msafam}
\mathchardef\dabar@"0\msafam@39
\def\dashrightarrow{\mathrel{\dabar@\dabar@\mathchar"0\msafam@4B}}
\def\dashleftarrow{\mathrel{\mathchar"0\msafam@4C\dabar@\dabar@}}
\let\dasharrow\dashrightarrow
\def\ulcorner{\delimiter"4\msafam@70\msafam@70 }
\def\urcorner{\delimiter"5\msafam@71\msafam@71 }
\def\llcorner{\delimiter"4\msafam@78\msafam@78 }
\def\lrcorner{\delimiter"5\msafam@79\msafam@79 }
\def\yen{{\mathhexbox@\msafam@55 }}
\def\checkmark{{\mathhexbox@\msafam@58 }}
\def\circledR{{\mathhexbox@\msafam@72 }}
\def\maltese{{\mathhexbox@\msafam@7A }}

\font\tenmsb=msbm10
\font\sevenmsb=msbm7
\font\fivemsb=msbm5
\newfam\msbfam
\textfont\msbfam=\tenmsb
\scriptfont\msbfam=\sevenmsb
\scriptscriptfont\msbfam=\fivemsb
\edef\msbfam@{\hexnumber@\msbfam}
\def\Bbb#1{{\fam\msbfam\relax#1}}
\def\widehat#1{\setbox\z@\hbox{$\m@th#1$}%
 \ifdim\wd\z@>\tw@ em\mathaccent"0\msbfam@5B{#1}%
 \else\mathaccent"0362{#1}\fi}
\def\widetilde#1{\setbox\z@\hbox{$\m@th#1$}%
 \ifdim\wd\z@>\tw@ em\mathaccent"0\msbfam@5D{#1}%
 \else\mathaccent"0365{#1}\fi}
\font\teneufm=eufm10
\font\seveneufm=eufm7
\font\fiveeufm=eufm5
\newfam\eufmfam
\textfont\eufmfam=\teneufm
\scriptfont\eufmfam=\seveneufm
\scriptscriptfont\eufmfam=\fiveeufm
\def\frak#1{{\fam\eufmfam\relax#1}}
\let\goth\frak

%  Restore the catcode value for @ that was previously saved.
\csname amssym.def\endcsname

%%\endinput

\begin{document}

\date{}
\title{ On common information.}

\author{An.A. Muchnik\\
Institute  of  New Technologies,\\
Moscow,109004, Russia, Nizhnaya Radishevskaya 10,\\
fax 7095 915-69-63; E-mail: amuchnik@int.glasnet.ru}

\maketitle

\begin{abstract}
We present a complexity-theoretic proof of the result of P.G{\'a}cs
and J.K{\"o}rner on existence of a pair of words whose common information
can not be materialized. Our method is easier than G{\'a}cs and K{\"o}rner's
method and gives a possibility to get some generalization of the result.
Besides, we show that there are many enough pairs of words with this property.

\medskip
{\it Keywords:} Kolmogorov entropy; Algorithmic information theory;
Common information of two words.
\end{abstract}

\section{Introduction}

The results of the present paper were announced in \cite{much}.

In paper \cite{kol1} A.N. Kolmogorov gave  the  definition  of  the
entropy $K(x)$ of finite  object $x$  and  the  definition  of  the
quantity of information $I(x:y)$ about $y$ contained in $x$. In~\cite{zvlev}
it was proved that the quantity of information  is  commutative  to
within an additive term of $O(\log K(x)+\log K(y))$
(all logarithms in our paper have base two).
In that paper it was also proved that
$$
|I(x:y)-(K(x)+K(y)-K(x,y))|=O(\log K(x)+\log K(y)).
$$

Because of commutativity of $I(x:y)$ we will  call $I(x:y)$,
$I(y:x)$ and $K(x)+K(y)-K(x,y)$ the quantity of  common  information
of $x$, $y$.

My father, A.A. Muchnik, raised the following  question:  is
there  a  word $z$   such  that $K(z)=I(z:x)=I(z:y)=I(x:y)$?  
That  is,  can   we   materialize   the   common
information? As $I(x:y)$ is commutative only to within an additive
term  of $O(\log K(x)+\log K(y))$  the  exact  formulation  of   this
question is the following.

\medskip
{\bf The problem of A.A. Muchnik.}  Is  the  following   assertion
true?

For some constant $c$ for all binary words $x$, $y$  there  is  a
binary word $z$ such that
$$
\cases{K(z)\leq I(x:y)+c(\log K(x)+\log K(y))+c\cr
I(z:x)\geq I(x:y)-c(\log K(x)+\log K(y))-c\cr
I(z:y)\geq I(x:y)-c(\log K(x)+\log K(y))-c}\leqno (1)
$$

\medskip
In the paper \cite{gachker} G{\'a}cs and K{\"o}rner gave a negative
solution to this problem. They used probabilistic  methods.
In the present paper we present a complexity-theoretic solution to
the problem of  A.A. Muchnik,  which  is  easier  than G{\'a}cs  and
K{\"o}rner's solution. We  are  interested  also  in  the  following
generalization of  the  question.  Let  us  fix  the  parameters
$m,n,a,b,i\in {\Bbb N}$ such that $a\le m$, $b\le n$, $i\le m$, $i\le n$.

What is the minimal $d$ such that for every words $x$, $y$  which
have respectively the  entropies $m$, $n$  and  the  quantity  of
common information $i$  there  is  a  word $z$  such  that $K(z)\le d$,
$I(z:x)\ge a$, $I(z:y)\ge b$? We can easily prove that 
$$
d\le a+b+2(\log m+\log n)+{\rm const.}
$$
It turns out that this  upper  bound  is  tight  (to  within  an
additive logarithmic  term) if $m\geq a+i$, $n\geq b+i$  (Theorem~2).

We are also interested in the following question:  for  how
many $x$, $y$ there is no $z$ such that the assertion (1) is  true?  We
give the following answer.  Let  us  fix  some  value  of $c$  in
(1). Then for all sufficiently large $n$ for all $x$ if ${K(x)\ge n}$ then
there is $y$ such that $K(y)$ is equal to $K(x)$ to within an additive
logarithmic term and such that there  is  no $z$  satisfying~(1)
(Theorem~3).
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
\section{Basic definitions.}

Let us denote by $\Xi$  the set of  all  binary  words.  Let  us
denote the length of a word $x$ by $l(x)$. Let us call  any  partial
computable function $f\colon\,\Xi\longrightarrow \Xi$ the specifying method.
We call  the word $p$ a description of $x$ (with respect to $f$) if $f(p)=x$.

The complexity $K_{f}(x)$ of word $x$ with respect to  the
specifying method $f$ is defined as
$$
K_{f}(x)=\min\{l(p)\mid f(p)=x\}
$$
and $K_{f}(x)=\infty$ if there is no $p$ such that $f(p)=x$.  We  say  that
specifying method $f$ is no worse than a specifying  method $g$  if
there is some $c\in {\Bbb N}$ such that for all
$x\in \Xi$ $\ K_{f}(x)\le K_{g}(x)+c$.  The
well known theorem of Solomonoff-Kolmogorov states  that  there
is an {\it optimal\/} specifying method, that is a method  which  is  no
worse than all other ones. Let us fix  some  optimal  specifying
method and denote it by $f_{0}$. Let us  denote $K(x)=K_{f_{0}}(x)$.
We call $K(x)$ the {\it entropy\/} of $x$. Obviously for  some  constant $c$
all $x$ satisfy the inequality $K(x)\le l(x)+c$. Therefore $K(x)<\infty$  for
all $x$.

In the above inequality, $c$ denotes a  constant  in  the  following  sense: $c$
doesn't depend on $x$ but $c$ depends on the choice of $f_{0}$.  In  our
paper there are also  absolute  constants.  We  will  give
absolute constants explicitly.

Let $g\colon\,\Xi\times \Xi\longrightarrow \Xi$ be partial computable
function. The
complexity $K_{g}$ of $x$, with respect  to $g$,  conditional  to $y$  is
defined by
$$
K_{g}(x|y)=\min \{l(p)\mid g(p,y)=x\}.
$$

Among all partial computable functions
$g\colon\,\Xi\times \Xi \longrightarrow \Xi$ there
is an optimal one, that is a function $g$  such  that  for  all $h$
there is a constant $c\in {\Bbb N}$ for which
$K_{g}(x|y)\le K_{h}(x|y)+c$  for  all
$x,y\in \Xi$. Let us fix some optimal $g$ and denote it by $g_{0}$. We define
$K(x|y)=K_{g_{0}}(x|y)$. Let us call the difference
$$
I(x:y)=K(y)-K(y|x)
$$
the quantity of information about $y$ contained in $x$.

Let us define some convenient coding  of  pairs  of  binary
words. Let $x$ be a word, $x=b_{1}b_{2}\ldots
b_{n}$, $b_{i}\in \{0,1\}$; denote by $\bar x$ the
word $b_{1}b_{1}b_{2}b_{2}\ldots
b_{n}b_{n}01$ (for  example,  $\overline{010}=00110001$). Obviously
given ${\bar x}y$ we can find both $x$ and $y$. Let us denote
$K({\bar x}y)$ by $K(x,y)$. The
well known theorem (\cite{zvlev}) states that there is $c\in {\Bbb N}$  such
that for every $x,y\in \Xi$
\par
$$
|K(x,y)-(K(x)+K(y|x))|\le 5(\log K(x)+\log K(y))+c.
$$
This yields
$$
|I(x:y)-(K(x)+K(y)-K(x,y))|\le 5(\log K(x)+\log K(y))+c,
$$
$$
|I(x:y)-I(y:x)|\le 10(\log K(x)+\log K(y))+c_{1}.
$$
Let us denote for the sake of convenience $(K(x)+K(y)-K(x,y))$ by
$\bar I(x:y)$. We will write $a\mathrel{{=}_{c}}b$ instead of $|a-b|<c$.

\section{The Results}

Let $a,b\in {\Bbb N}$; $x,y\in \Xi$.  Let
$C_{a,b}(x,y)=\min \{K(z)\mid I(z:x)\ge a,\,
I(z:y)\ge b\}$. The following simple theorem yields upper and  lower  bounds
for $C_{a,b}(x,y)$.  By $m,n,i$ we denote respectively
$K(x),K(y),\bar I(x:y)$.

\medskip
{\bf Theorem 1.} {\it There is a constant $c\in {\Bbb N}$ such that
if $m\ge a+c$, $n\ge b+c$ then}
\begin{eqnarray*}
\max \{a,b,a+b-i\}-40(\log m+\log n)-c\le C_{a,b}(x,y)\le\\
\le a+b+2(\log m+\log n)+c.
\end{eqnarray*}

\medskip
{\it Proof.} We will denote in this proof as well  as  in  others
proofs by $c_{1}$, $c_{2},\ldots$
constants depending only  on  the  choice  of
$f_{0}$, $g_{0}$. The value of $c$ will be clear from the proof.

Let us prove first the lower bound of $C_{a,b}(x,y)$. We  have
to prove three inequalities:\\
$a-40(\log K(x)+\log K(y))-c\le C_{a,b}(x,y)$,\\
$b-40(\log K(x)+\log K(y))-c\le C_{a,b}(x,y)$,\\
$a+b-\bar I(x:y)-40(\log K(x)+\log K(y))-c\le C_{a,b}(x,y)$.

The first two  inequalities  follow  from  the  well  known
inequality\\
$K(x)\le K(x|z)+K(z)+2\log K(x)+c_{1}$, i.e.\ $K(z)\ge I(z:x)-2\log
K(x)-c_{1}$.

Let us prove the third inequality. This inequality  follows
from the inequality
$$
K(z)\ge I(z:x)+I(z:y)-\bar I(x:y)-40(\log K(x)+\log K(y))-c_{2}.
$$

Let us prove this inequality. Note that we can take as $z$ the pair
$(x,y)$. Therefore $K(z)\leq K(x)+K(y)+2\log K(x)+c_{1}$. Since the function
$\log$ is concave, this implies that $\log K(z)\leq 2(\log K(x)+\log K(y))+c_{1}$. 
In the next proof  we  will  omit additive logarithmic terms.\\
$I(z:x)+I(z:y)-\bar I(x:y)=K(x)+K(z)-K(x,z)+K(y)+K(z)-$\\
$-K(y,z)-K(x)-K(y)+K(x,y)=2K(z)+K(x,y)-K(x,z)-K(y,z)$.

As $K(x,z)=K(x|z)+K(z)$ we get\\
$K(z)+K(x,y)-K(x,z)-K(y,z)=K(x,y)-K(x|z)-K(y,z)\le$\\
$\le K(x,y)-K(x|{\bar y}z)-K({\bar y}z)=K(x,y)-K(x,{\bar y}z)\le 0$.

Thus to within an additive logarithmic term
$$
I(z:x)+I(z:y)-\bar I(x:y)\le K(z).
$$

Now let us prove the upper bound of  $C_{a,b}$.
Clearly, we can take as $z$ the concatenation
of $a$ first bits of the shortest description of $x$,
$b$ first bits of the shortest description of $y$ and 
$\overline{l(a)}$ ($\overline{l(a)}$ stands for $\bar u$, where $u$
is binary representation of $l(a)$). 

The  theorem is proved.

It is easy to prove that the lower bound  in  Theorem~1  is
tight (to within an additive logarithmic term). Indeed, let ${m\ge a}$,
${n\ge b}$, ${m\ge i}$, ${n\ge i}$. Let us define
words $x$, $y$  such  that ${K(x)=m}$,
${K(y)=n}$, ${\bar I(x:y)=i}$, ${C_{a,b}(x,y)=\max \{a,b,a+b-i\}}$
(factors of logarithmic length in words and logarithmic terms in numbers
are omitted in the following reasoning). 
Let ${a\ge b}$. Let us 
take random mutually independent words $p$, $q$, $r$ with lengths
respectively $i$,
${m-i}$, ${n-i}$, i.e.\ ${K(p|{\bar q}r)=i}$, ${K(q|{\bar p}r)=m-i}$, 
${K(r|{\bar p}q)=n-i}$. Let ${x=pq}$, ${y=pr}$. We consider two cases.\\
1) $a\ge a+b-i$, i.e. $i\ge b$.\\
Let $z$ be the beginning of $x$ of length $a$. Then $I(z:x)=a$.  If
$i\ge a$ then $z$ is beginning of $y$  consequently $I(z:y)=a\ge b$. If $a\ge
i$
then $z$ begins with $p$ therefore $I(z:y)=i\ge b$.\\
2) $a+b-i\ge a$, i.e. $b\ge i$.\\
Let $z$ be equal to $pq_{1}r_{1}$, where $q_{1}$, $r_{1}$  are 
respectively
the   beginnings   of $q$, $r$   of   lengths $a-i$, $b-i$.  Then
$K(z)=i+a-i+b-i=a+b-i$, $I(z:x)=i+a-i=a$, $I(z:y)=i+b-i=b$.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
The following theorem shows that the upper bound in Theorem~1 is tight  if
$m\ge a+i$, $n\ge b+i$.

\medskip
{\bf Theorem 2.} {\it There  is  a  constant $c\in {\Bbb N}$  such  that  
the
following holds. For every $m$, $n$, $a$, $b$, $i$ such that 
$m\ge i$, $n\ge i$, $m\ge a$, $n\ge b$ there    are $x$, $y$     such     
that $K(x)\mathrel{{=}_{c}}m$, $K(y)\mathrel{{=}_{c}}n$,
$|\bar I(x:y)-i|\le 5(\log m+\log n)+ c$, $C_{a,b}(x,y)\ge
\max\{a,b,\min\{a+n-i,b+m-i,a+b\}\}-5(\log m+\log n)-c$.}

\medskip
{\it Proof.} Let $m$, $n$, $a$, $b$, $i$ satisfy  the  inequalities $m\ge i$,
$n\ge i$,
$m\ge a$, $n\ge b$. Let us denote $k=\min \{a+b,a+n-i,b+m-i\}$.

It is easy to see that
$C_{a,b}(x,y)\ge a-5(\log m+\log n)-c$ and\\
$C_{a,b}(x,y)\ge b-5(\log m+\log n)-c$. So we have to prove that
$C_{a,b}(x,y)\ge k-c$ for appropriate $c$.

We will define two words $x$  and $y$  satisfying  the  conditions  of the
theorem. The words $x$, $y$ must be such that there is no $z$ such that
${K(z)\le k-c}$, ${I(z:x)\ge a}$, $I(z:y)\ge b$. The last  two  inequalities 
means
that ${K(x|z)\le K(x)-a}$, $K(y|z)\le K(y)-b$.

Let $c_{1}$ stand for the constant such  that $K(u)\le l(u)+c_{1}$  for
all $u\in \Xi$. Let us define\\
$M_{1}=\{(x,y)\in \Xi\times \Xi\mid 
\exists z\in \Xi\ K(z)\le k-c,\ K(x|z)\le m+c_{1}-a,$\\
$\phantom{aaaaaa} K(y|z)\le n+c_{1}-b\}$,\\
$M_{2}=\{(x,y)\mid l(y)=n,\ K(x)<m-2\}$,\\
$M_{3}=\{(x,y)\mid l(x)=m,\ K(y)<n-2\}$,\\
$M_{4}=\{(x,y)\mid K(x,y)<m+n-i-2\}$.

We\quad claim\quad that\quad for\quad sufficiently\quad large\qquad $c\in 
{\Bbb N}$\qquad the\quad inequality
${|M_{1}\bigcup M_{2}\bigcup M_{3}\bigcup M_{4}|<2^{m+n}}$ holds. 
To  prove  this  claim  we  will
estimate $|M_{1}|$, $|M_{2}|$, $|M_{3}|$, $|M_{4}|$. 
Remember the  following well  known  inequalities 
${|\{x\in \Xi\mid K(x)\le l\}|<2^{l+1}}$,
${\forall y\in \Xi\, |\{x\in \Xi\mid K(x|y)\le l\}|<2^{l+1}}$.
These inequalities yield\\
$|M_{1}|\le \sum\limits_{z\colon\,K(z)\le k-c}\Bigl\vert\{(x,y)\mid 
K(x|z)\le m+c_{1}-a,\ K(y|z)\le n+c_{1}-b\}\Bigr\vert\le$\\
$\le 2^{k-c+1}\cdot 2^{m+c_{1}-a+1}\cdot
2^{n+c_{1}-b+1}=2^{m+n+(k-a-b)+2c_{1}+3-c}\le 
2^{m+n+2c_{1}+3-c}$\\
(as $k\le a+b$),\\
$|M_{2}|<2^{m-2}\cdot 2^{n}=2^{m+n-2}$,\\
$|M_{3}|<2^{m}\cdot 2^{n-2}=2^{m+n-2}$,\\
$|M_{4}|<2^{m+n-i-2}\le 2^{m+n-2}$.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Therefore\quad if\qquad $c\ge 2c_{1}+5$\qquad then\qquad $|M_{1}\bigcup
M_{2}\bigcup 
M_{3}\bigcup M_{4}|<2^{m+n}$.  Hence
there is a pair of  words $x$, $y$  such  that ${l(x)=m}$, ${l(y)=n}$  and
${(x,y)\notin M_{1}\bigcup M_{2}\bigcup M_{3}\bigcup M_{4}}$. Let us take the
first pair $(x,y)$ with
these properties. We claim that if $c$ is large enough  then $(x,y)$
satisfies all requirements.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
The conditions $|K(x)-m|\le c$, $|K(y)-n|\le c$ are satisfied because\\
$(x,y)\notin M_{2}\bigcup M_{3}$ therefore\\
$m-2\le K(x)\le l(x)+c_{1}=m+c_{1}$,\\
$n-2\le K(y)\le l(y)+c_{1}=n+c_{1}$.\\
As $(x,y)\notin M_{1}$  there  is  no $z$   such   that $K(z)\le k-c$   and
$K(x|z)\le m+c_{1}-a$, $K(y|z)\le n+c_{1}-b$. We know that $K(x)\le m+c_{1}$,
$K(y)\le n+c_{1}$.
Therefore  there  is  no $z$  such that $K(z)\le k-c$  and $K(x|z)\le
K(x)-a$,
$K(y|z)\le K(y)-b$.

It   remains   to    prove    the    difficult    assertion\\
\centerline{$|\bar I(x:y)-i|\le 5(\log m+\log n)+c$.}

The upper bound of $\bar I(x:y)$ is  easy: $K(x)\le m+c_{1}$, $K(y)\le
n+c_{1}$,
$K(x,y)\ge m+n-i-2$ (as $(x,y)\notin M_{4})$   therefore\\
$\bar I(x:y)\le m+c_{1}+n+c_{1}-(m+n-i-2)=i+2c_{1}+2\le i+c$.

Now let us estimate $\bar I(x:y)$ from below. We have to  estimate
$K(x,y)$ by the  quantity  about $m+n-i$.  The  main  idea  is  the
following:  every  finite  set $M$  can  be   specified   by   its
cardinality $|M|$ and  by  an  algorithm  $A$  which  generates  all
elements of $M$ (and only them). Indeed, given $A$ we can generate the elements of $M$
until we get $|M|$ different elements.

So  let  us  estimate $K(x,y)$.  To  specify $(x,y)$  it   is
sufficient to specify $m$, $n$ and $M_{1}$, $M_{2}$, $M_{3}$, $M_{4}$. 
To specify $M_{1}$  it is
sufficient to specify the set 
${\Gamma_{1}=\{(p,u)\mid l(p)\le k-c,\  f_{0}(p)=u\}}$  and
the set ${\Gamma_{2}=\{(p,z,u)\mid g_{0}(p,z)=u,\ l(p)\le 
\max(m-a,n-b)+c_{1},\ K(z)\le k-c\}}$.
To specify $M_{2}$, $M_{3}$, $M_{4}$ it is sufficient 
to specify ${m-2}$, ${n-2}$, ${m+n-2}$
and   the   set ${\Gamma_{3}=\{(p,u)\mid f_{0}(p)=u,\ l(p)\le m+n-i-2\}}$
(because
${m+n-i\ge m,n}$). To specify $\Gamma_{1}$, $\Gamma_{2}$, $\Gamma_{3}$  it  is 
sufficient  to  specify
${\Gamma=\Gamma_{1}\bigcup\Gamma_{2}\bigcup\Gamma_{3}}$ and 
$m$, $n$, $a$, $b$, $i$, $c$, $c_{1}$. 
Moreover, to specify $\Gamma_{1}$, $\Gamma_{2}$, $\Gamma_{3}$ it
is sufficient to  specify $|\Gamma|$  and 
$m$, $n$, $a$, $b$, $i$, $c$, $c_{1}$  because  given
$m$, $n$, $a$, $b$, $i$, $c$, $c_{1}$ we can generate the elements of $\Gamma$.  
Therefore  there is a specifying method which on the input 
${\bar m\bar n\bar a\bar b\,\bar i\bar c\bar c_{1}|\Gamma|}$ 
outputs $(x,y)$. Consequently\\
$K(x,y)\le 2(\log m+\log n+\log a+\log b+\log i)+2\log c+2\log c_{1}+
\log |\Gamma|+c_{2}\le$\\
$\le 5(\log m+\log n)+4\log c+\log |\Gamma|+c_{2}$.
{\sloppy

}
Let us estimate $|\Gamma|$. The number of words of  length $\le l$  is
less than $2^{l+1}$. Therefore\\
$|\Gamma_{2}|<2^{k-c+1}\cdot 2^{\max(m-a,n-b)+c_{1}+1}=
2^{\max(k+m-a,k+n-b)-c+c_{1}+2}\le$\\
$\le 2^{m+n-i-c+c_{1}+2}$\\
(the    last    inequality    holds     because $k\le a+n-i$,
$k\le b+m-i$),\\
$|\Gamma_{3}|<2^{m+n-i-1}$,\\
$|\Gamma_{1}|<2^{k-c+1}\le 2^{a+n-i-c+1}\le 2^{m+n-i-c+1}$.

Therefore   if $c>c_{1}+1$    then 
$|\Gamma_{1}|,|\Gamma_{2}|,|\Gamma_{3}|<2^{m+n-i+1}$
consequently\\
$|\Gamma|<2^{m+n-i+3}$. Hence\\
$K(x,y)<5(\log m+\log n)+4\log c+m+n-i+3+c_{2}$,\\
$\bar I(x:y)>m-2+n-2-5(\log m+\log n)-4\log c-m-n+i-3-c_{2}=$\\
$=i-5(\log m+\log n)-4\log c-7-c_{2}$.

Let us take $c\in {\Bbb N}$ such  that $c>4\log c+7+c_{2}$. Then we have
proved the desired lower bound of $\bar I(x:y)$. The theorem is proved.

Let  us   deduce   from   Theorem~2  negative solution   of
A.A.Muchnik's problem. Let us fix some constant $c$ in assertion  (1).  We
will call a pair $(x,y)$ bad if there is no $z$ satisfying  (1).  We
claim that there is bad $(x,y)$ with arbitrary large $K(x)$, $K(y)$  and
arbitrary ratios $\frac{\bar I(x:y)}{K(y)}$, $\frac{\bar I(x:y)}{K(x)}$
belonging to the interval $(0,1)$.

\medskip
{\bf Corollary.} {\it Let $\gamma,\alpha,\beta\in {\Bbb R}$  satisfy
inequalities
${0\le \alpha,\beta\le 1}$ and ${0<\gamma<\alpha,\beta}$. Then for some
$c$ for all  sufficiently  large
${j\in {\Bbb N}}$  there  is a bad  pair ${(x_{j},y_{j})}$   such   that 
${K(x_{j})\mathrel{{=}_{c}}\alpha\cdot j}$,
${K(y_{j})\mathrel{{=}_{c}}\beta\cdot j}$, 
${\bar I(x_{j}:y_{j})\mathrel{{=}_{10\log j+c}}\gamma\cdot j}$.}
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
\medskip
{\it Proof.} Let us take $\varepsilon>0$.  Define 
$b=a=(\gamma-\varepsilon)j$, $m=\alpha j$, $n=\beta j$, $i=\gamma j$.
Obviously we can choose $\varepsilon$ so small that for all $j$\\
$(\gamma+\varepsilon)j\le \min\{a+b,a+n-i,b+m-i\}=$\\
$=\min\{\gamma-\varepsilon+\gamma-\varepsilon,\gamma-\varepsilon+\beta-\gamma,
\gamma-\varepsilon+\alpha-\gamma\}\cdot j$.

By Theorem~2 there is a pair $(x_{j},y_{j})$ such that\\
$K(x_{j})\mathrel{{=}_{c}}\alpha j$, $K(y_{j})\mathrel{{=}_{c}}\beta j$, 
$\bar I(x_{j}:y_{j})\mathrel{{=}_{10\log j+c}}\gamma j$,\\
$C_{(\gamma-\varepsilon)j,(\gamma-\varepsilon) j}(x_{j},y_{j})\ge 
(\gamma+\varepsilon)j-10\log j-c$.\\
Evidently for sufficiently large $j$ the  pair $(x_{j},y_{j})$
is bad.

\medskip
{\bf Theorem 3.} {\it There is a constant $c$ such  that  the  following
holds. For every $x\in \Xi$ for every $a\le K(x)$ there is $y\in \Xi$ such
that}\\
$K(y)\mathrel{{=}_{4\log K(x)+c}}K(x)$, 
$\bar I(x:y)\mathrel{{=}_{6\log K(x)+c}}\frac{K(x)}{2}$,\\
$C_{a,a}(x,y)\ge \frac{3}{2}a-4\log K(x)-c$.

\medskip
{\it Proof.} Let us fix some $x_{0}\in \Xi$  and  some 
$a\in {\Bbb N}$  such  that
$a\le K(x_{0})$. Denote $n=K(x_{0})$. It is well known that for  every 
$l\in {\Bbb N}$ there is a prime number $p$ in interval $[l,l+1,\ldots,2l]$. 

Take  the least prime $p\ge 2^{\left\lceil\frac{n+1}{2}\right\rceil}$. As 
$p\le 2^{\left\lceil\frac{n+1}{2}\right\rceil+1}$, we have\\ 
$2^{n+1}\le p^{2}\le 2^{n+4}$.

Consider the following bipartite graph $\Gamma_{1}$. We will call the
vertices from the first part ``left vertices''  and  the  vertices
from the second part ``right vertices''.

The set of left vertices is ${\Bbb Z}_{p}\times {\Bbb Z}_{p}$, where 
${\Bbb Z}_{p}$ stands for the
field of residues modulo $p$. The set  of  right  vertices  is  an
another  copy  of ${\Bbb Z}_{p}\times {\Bbb Z}_{p}$.  Each  left  vertex 
$(q,r)\in {\Bbb Z}_{p}\times {\Bbb Z}_{p}$  is
connected with $p$ right vertices $(q+i,r+qi)$, $i\in {\Bbb Z}_{p}$. Let us
prove
that $\Gamma_{1}$ has no closed cycles consisting of four edges (we will call
such a cycle ``4-cycle'').

It is sufficient to prove that if $(v_{1},v_{2})$ and $(v_{1},v_{3})$  are
edges and $v_{2}\neq v_{3}$ then given $v_{2}$, $v_{3}$ we can find $v_{1}$. 

Let $v_{1}=(q,r)$, $v_{2}=(q+i,r+qi)$, $v_{3}=(q+j,r+qj)$. Then given 
$v_{2}$, $v_{3}$ we can  find $i-j$
and $q(i-j)$. As ${\Bbb Z}_{p}$ is field we can find $q$. 
From $q$ and $q+i$ we  can compute $i$. From $r+qi$ and $qi$ we can compute
$r$.

Furthermore, one can easily verify that for each right vertex
$v$ there are exactly $p$ edges incident to $v$.

Now we will mark left and right vertices with binary  words
and delete some left vertices. Let us  mark $i$-th  right  vertex
with $i$-th word of length $n+4$ (we  assume  that  some  computable
well ordering on words and vertices is fixed).

We will mark left vertices with the words of  entropy $\le n$
as follows. Let us begin to generate the words  of  entropy
$\le n$. The $i$-th generated word marks the $i$-th vertex. As
$$
|\{x\in \Xi\mid K(x)\le n\}|<2^{n+1}\le |{\Bbb Z}_{p}\times {\Bbb Z}_{p}|,
$$
this is possible. Then we delete  all  unmarked  left  vertices.
We'll denote by $\Gamma_{2}$ the marked graph obtained by this procedure.
Note
that we can not compute $\Gamma_{2}$ given $n$ because we don't know at which
moment the last word $x$ with $K(x)\le n$  is  generated.  Nevertheless
there is a procedure which given $n$ generates  all  edges  of $\Gamma_{2}$
with their markings. We will say  ``left  vertex $x$''  instead  of
``left vertex with marking $x$'' and for the right vertices also.

Our plan is as follows. We will construct subgraphs $M_{d}$ of the graph 
$\Gamma_{2}$ ($d\in \Bbb N$). There will exist an algorithm which given
$n$, $a$, $d$ generates all edges of $M_{d}$ and only them. Cardinality
(i.e.\ the number of edges) of $M_{d}$ will be not greater than
$2^{\frac{3}{2}n-4\log n-d+c_{2}}$ ($c_{2}$ is a constant; $c_{1}$, as
earlier, will be the constant such that $\forall u\,K(u)\leq l(u)+c_{1}$).

Further, $M'_{d}$ will be the set of those left vertices which are
incident to edges only from $M_{d}$. Then 
$|M'_{d}|\leq\frac{|M_{d}|}{p}\leq 2^{n-4\log n-d+c_{2}}$. 
For $M'_{d}$, like it holds for $M_{d}$, there will be an algorithm
generating on $n$, $a$, $d$ all vertices of $M'_{d}$ and only them.
In the same way as in the proof of Theorem 2, it will follow from the previous
conditions that\\ 
$\forall x\in M'_{d}\ K(x)\leq 2\log n+2\log a+2\log d+\log |M'_{d}|+c_{3}\leq$\\
$\leq 4\log n+2\log d+n-4\log n-d+c_{4}=n+2\log d-d+c_{4}$.

Choose $d$ so large that $2\log d-d+c_{4}<0$. Then 
$x\in M'_{d}\Longrightarrow K(x)<n$, thus $x_{0}\notin M'_{d}$. Therefore 
there exists $y_{0}\in \Xi$ such that $(x_{0},y_{0})\in \Gamma_{2}$ and
$(x_{0},y_{0})\notin M_{d}$.

Let us turn to defining of $M_{d}$.

Let $E'$ be the set of all edges $(x,y)\in \Gamma_{2}$ such that
$K(y)<n-4\log n-d$. Since each vertex is incident to no more than $p$
edges, we obtain\\
$|E'|\leq p2^{n-4\log n-d}\leq 2^{\frac{n}{2}+2}2^{n-4\log n-d}=
2^{\frac{3}{2}n-4\log n-d+2}$.

Let $E''$ be the set of all edges $(x,y)\in \Gamma_{2}$ such that
$K(x,y)<\frac{3}{2}n-4\log n-d$. This implies that
$|E''|<2^{\frac{3}{2}n-4\log n-d}$. 

For any $z\in \Xi$ we define $\Gamma^{z}$ to be the subgraph of $\Gamma_{2}$
consisting of all vertices (left and right) $y$ such that 
$K(y|z)\leq n+4+c_{1}-a$, and of all edges between these vertices.
The left and the right parts of $\Gamma^{z}$ consist of less than $2^{n+5+c_{1}-a}$ 
vertices. Let us deduce from this an upper bound of the number of edges
of $\Gamma^{z}$. Note that $\Gamma^{z}$ has no 4-cycles as a subgraph of
$\Gamma_{1}$. 

\medskip
{\bf Lemma.} {\it If a bipartite graph has no $4$-cycles  and  the
number of vertices in both  parts  doesn't  exceed $m$  then  the
number of edges in the graph doesn't exceed $m^{3/2}+2m$.}

\medskip
{\it Proof.} Let the left  vertices  of  the  graph  be  integers
$1,2,\ldots,m$.
Let us denote by $k_{i}$ the number of edges incident to the left
vertex $i$.

Let $M_{i}$ be the set of all nonordered pairs $(j,q)$,  where $j$
and $q$ are right vertices connected with $i$.  Then 
$|M_{i}|=\frac{k_{i}(k_{i}-1)}{2}$.
As the graph has no 4-cy\-cles the sets $M_{1},\ldots,
M_{m}$  are  pairwise
disjoint.   As $\left|\bigcup\limits_{i=1}^{m}M_{i}\right|\le
\frac{m(m-1)}{2}$,  
we    can    conclude    that
$\sum\limits^{m}_{i=1}\frac{k_{i}(k_{i}-1)}{2}\le\frac{m(m-1)}{2}$. 
Let  us  deduce  from  this  inequality  the
inequality $\sum\limits^{m}_{i=1}k_{i}\le m^{3/2}+2m$.

Repeat till this is possible the  following  transformation
with the vector $(k_{1},\ldots,
k_{m})$: pick $k_{i}$ and $k_{j}$  such  that $k_{i}\le k_{j}-2$
then decrease $k_{j}$ by 1 and increase $k_{i}$  by  1.  After  performing
this transformation $\sum\limits^{m}_{i=1}k_{i}$ isn't changed  and 
$\sum\limits^{m}_{i=1}k_{i}(k_{i}-1)$  isn't
increased because the function $r(r-1)$ is convex.  Therefore  the
inequality
$$
\sum\limits^{m}_{i=1}k_{i}(k_{i}-1)\le m(m-1)\leqno (2)
$$
remains valid.

Finally we get a vector consisting  (for  some $k$) only  of
numbers $k$ and $k+1$. Because (2) we have\\
$mk(k-1)\le m(m-1)$; $k(k-1)\le m-1$; $k\le \sqrt{m}+1$.

Hence $\sum\limits^{m}_{i=1}k_{i}\le (k+1)m\le m(\sqrt{m}+2)$ q.e.d.

It follows from the lemma that the number of edges of the 
graph $\Gamma^{z}$ doesn't exceed 
$2^{\frac{3}{2}(n+5+c_{1}-a)}+2^{n+6+c_{1}-a}\leq 2^{\frac{3}{2}(n-a)+c_{5}}$.

Let $E'''$ be the set of all edges $(x,y)\in \Gamma_{2}$ for which
there exists $z\in \Xi$ such that $K(z)<\frac{3}{2}a-4\log n-d$ and
$(x,y)\in \Gamma^{z}$. We have\\
$|E'''|\leq \sum\limits_{z\colon\,K(z)\leq\frac{3}{2}a-4\log n-d}
({\rm number\ of\ edges\ of\ }\Gamma^{z})\leq$\\
$\leq 2^{\frac{3}{2}a-4\log n-d}\cdot 2^{\frac{3}{2}(n-a)+c_{5}}=
2^{\frac{3}{2}n-4\log n-d+c_{5}}$.

Let $M_{d}=E'\bigcup E''\bigcup E'''$. First, the existence of algorithms
generating the graphs $E'$, $E''$, $E'''$ given $n$, $a$, $d$ is evident.
The same statement is true for $M_{d}$. Second,
$|M_{d}|\leq |E'|+|E''|+|E'''|\leq 2^{\frac{3}{2}n-4\log n-d+c_{2}}$.

Now let us verify that the edge $(x_{0},y_{0})$ satisfies the conditions
of the theorem being proved.

{\bf I}. $K(y_{0})\leq l(y_{0})+c_{1}=n+4+c_{1}$.

{\bf II}. $(x_{0},y_{0})\notin E'$, consequently $K(y_{0})\geq n-4\log n-d$.

{\bf III}. $\bar I(x_{0}:y_{0})=K(x_{0})+K(y_{0})-K(x_{0},y_{0})$. As
$(x_{0},y_{0})\notin E''$, we have $K(x_{0},y_{0})\geq \frac{3}{2}n-4\log n-d$.
This implies\\  
$\bar I(x_{0}:y_{0})\leq n+(n+4+c_{1})-(\frac{3}{2}n-4\log n-d)
=\frac{n}{2}+4\log n+c_{6}$.

{\bf IV}. The graph $\Gamma_{1}$ is specified by the number $n$, and the number
of its edges is equal to $p^{3}$. Therefore, the entropy of each edge
doesn't exceed\\ 
$2\log n+\log p^{3}+c_{7}$. Thus,
$K(x_{0},y_{0})\leq \frac{3}{2}n+2\log n+c_{8}$;\\
$\bar I(x_{0}:y_{0})\geq n+(n-4\log n-d)-(\frac{3}{2}n+2\log n+c_{8})
=\frac{n}{2}-6\log n-c_{9}$.

{\bf V}. If $K(z)<\frac{3}{2}a-4\log n-d$ then 
$(x_{0},y_{0})\notin E'''\Longrightarrow [K(x_{0}|z)>n+4+c_{1}-a$ or 
$K(y_{0}|z)>n+4+c_{1}-a]$. Assume $K(y_{0}|z)>n+4+c_{1}-a$, then\\
$I(z:y_{0})=K(y_{0})-K(y_{0}|z)<(n+4+c_{1})-(n+4+c_{1}-a)=a$. The argument
for $x_{0}$ is similar. From this it follows that $C_{a,a}(x_{0},y_{0})\geq
\frac{3}{2}a-4\log n-d$.

The theorem is proved.
  
Let us apply Theorem~3  to  arbitrary $x$  and  to  $a=\frac{2}{5}K(x)$.
Obviously for sufficiently large $K(x)$ for the pair $(x,y)$  there
is no ${\it z}$ such that (1) holds.

\begin{thebibliography}{99}

\bibitem{much}
An.A. Muchnik. On the extraction of common information of two words, {\it In
the book:
Pervyi Vsemirnyi Kongress Obshestva matematicheskoi statistiki i teorii
veroyatnostei
imeni Bernulli. Thesises.} Vol. 1 M.: Nauka, 1986, p. 453. (In Russian).

\bibitem{kol1}
A.N. Kolmogorov.  Three  approaches  to  the   quantitative
definition  of   information,   {\it Problems   in   Information
Transmission} {\bf 1} (1), pp.1-7 (1965).

\bibitem{zvlev}
A.K. Zvonkin and L.A. Levin. 
The complexity of finite objects
and the algorithmic concepts of information and randomness,
{\it Russ. Math. Surv.} {\bf 25}, pp. 83--124 (1970).

\bibitem{gachker}
P. G{\'a}cs, J. K{\"o}rner. Common  information  is  far  less  than
mutual information, {\it Problems  of  Control  and  Information
theory} {\bf 2}, pp.149-162 (1973).


\end{thebibliography}
\end{document}

