% tcs.tex
% corrected July 4 2000 -(keywords, bibliography)
% correction made by Chernov in final proofs added - Feb 20, 2001
\documentclass[11pt]{article}          % LaTeX 2e
\usepackage{amsthm,amsmath,amssymb,latexsym}       % LaTeX 2e
\usepackage{times}                               % LaTeX 2e

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}{Lemma}
\theoremstyle{remark}
\newtheorem{remark}{Remark}

%\newcommand{\R}{\mathbb{R}}
\newcommand{\R}{[0,\infty)}
\newcommand{\eps}{\varepsilon}
\newcommand{\olog}{O(\log n)}
\newcommand{\pair}[1]{\langle #1\rangle}
\newcommand{\bs}[1]{\boldsymbol  #1}
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}

\sloppy
\begin{document}

\title{Upper semi-lattice of binary strings with the relation
``$x$ is simple conditional to $y$''}

\author{
      %
Alexei Chernov\\Dept. of Mathematical Logic  and
Theory of Algorithms\\ Moscow State University\\ Vorobjewy Gory,
Moscow, Russia 119899\\
      %
\and
Andrej Muchnik\\Institute of New Technologies of Education\\ 10
Nizhnyaya Radischewskaya,\\ Moscow, Russia 109004\\
FAX: +70959156963
     \and
Andrei Romashchenko\\Dept. of Mathematical Logic  and
Theory of Algorithms\\ Moscow State University\\ Vorobjewy Gory,
Moscow, Russia 119899\\  \texttt{an@romash.mccme.ru}
     \and
Alexander Shen\thanks{
The work was
supported by Volkswagen Foundation while visiting Bonn
University}\\
Institute of Problems \\ of Information
Transmission\\  \texttt{shen@mccme.ru}
     \and
Nikolai Vereshchagin\thanks{
The work was partially done while visiting the University of
Amsterdam and DIMACS center}\\
 Dept. of Mathematical Logic  and
Theory of Algorithms\\ Moscow State University\\ Vorobjewy Gory,
Moscow, Russia 119899\\  \texttt{ver@mech.math.msu.su}
        %
}
\date{}

\maketitle

\begin{abstract}

In this paper we construct a structure $R$ that is a ``finite
version'' of the semi-lattice of Turing degrees. Its elements are
strings (technically, sequences of strings) and $x\le y$ means
that $K(x|y)={}$(conditional Kolmogorov complexity of $x$ relative
to $y$) is small.

We construct two elements in $R$ that do not have greatest lower bound.
We give a series of examples that show how natural algebraic
constructions give two elements that have lower bound $0$
(minimal element) but significant mutual information. (A first
example of that kind was constructed by
G\'acs--K\"orner~\cite{gacskorner} using a completely different
technique.)

We define a notion of ``complexity profile'' of the pair of
elements of $R$ and give (exact) upper and lower bounds for it
in a particular case.

Keywords: Kolmogorov complexity, common information, conditional complexity

\end{abstract}

\section{Introduction}

Let $\alpha$ and $\beta$ be two infinite binary sequences. We
say that $\alpha$ is Turing reducible to $\beta$ if there exists
a Turing machine $M$ that produces $\alpha$ on its output tape
when $\beta$ is provided on input tape. Turing reducibility is
reflexive and transitive, so we get a pre-order on the set of
all infinite binary sequences (this pre-order is usually
denoted by $\le_T$). The equivalence classes $((x\sim
y)\Leftrightarrow(x\le_T y)\land(y\le_T x))$ form an upper
semi-lattice whose elements are called Turing degrees. This
semi-lattice is well studied in recursion theory (see, e.g.,
\cite{shoenfield})

Now let us replace infinite sequences $\alpha$ and $\beta$ by
finite binary strings $x$ and $y$. Of course, for any $x$ and
$y$ there exists a Turing machine $M$ that produces $x$ from
$y$. So to get a non-trivial relation we have to put some
restrictions on $M$. It is natural to require that $M$ is simple
(its program is short compared to $x$ and $y$). Here the notion
of Kolmogorov complexity comes into play. By definition, the
conditional Kolmogorov complexity $K(x|y)$ is the length of the
shortest program that produces $x$ having $y$ as an input. Now
we can define the relation $x\le_c y$ as $K(x|y)\le c$ (here $x$
and $y$ are binary strings, $c$ is a number).

If $c$ is a constant, this relation does not have good
properties (for example, it is not transitive). This relation
also depends on a specific programming language used in the
definition of Kolmogorov complexity. To overcome these
difficulties, we use the standard trick and consider the
asymptotic behavior of the complexity for sequences of strings.

Let $\boldsymbol{x}=x_1, x_2,\dots$ be a sequence of binary
strings. We call it \emph{regular} if length of $x_i$ is
polynomially bounded, i.e., if $|x_i| \le ci^k$ for some $c,k$
and for all~$i$. Let $R$ denote the set of all regular
sequences. We say that regular sequence $\boldsymbol{x}$ is
\emph{simple} conditional to a regular sequence $\boldsymbol{y}$
if
        $$
K(x_i|y_i) = O(\log i)
        $$
and write $\boldsymbol{x}\le\boldsymbol{y}$. The $\le$-relation
is a pre-order defined on $R$. The relation $(x\le y) \land (y\le
x)$ is an equivalence relation. Equivalence classes form a
partially ordered set which (for the same reasons as in the case
of Turing degrees) is an upper semi-lattice (any two elements
have a least upper bound).

We prove (Section~\ref{semi-lattice}) that this set is not a
lower semi-lattice: there are two elements that do not have
greatest lower bound. Note that the set of Turing degrees is
not a lower semi-lattice either (see, e.g.,~\cite{shoenfield}), but
our proof goes in a completely different way.

The semi-lattice $R$ is useful for analyzing the notion of
common information. This notion was introduced by G\'acs and
K\"orner~\cite{gacskorner} in the context of Shannon information
theory. They also described a similar notion in the algorithmic
theory but do not give a precise definition. We give such a
definition in terms of the semi-lattice $R$
(Section~\ref{common}).

The main result of~\cite{gacskorner} is an example of two
objects whose ``common information'' is far less than their
``mutual information''; G\'acs and K\"orner provide
such an example in context
of Shannon information theory and mention that it could be
reformulated for algorithmic information theory. This example
was analyzed in \cite{germany-talk} where an alternative proof
for a special case of G\'acs--K\"orner example was provided.

A completely different example of two strings whose common
information is much less than their mutual information was
given in \cite{muchnik1}; for details see~\cite{muchnik2}.

In this paper we develop a third approach to  construct
such pairs of strings. It is based on the geometry of finite
fields. Several examples of this type are given in
Section~\ref{common-mutual}.
Our examples (as well as G\'acs--K\"orner's)
are constructive in the following sense.
In the recursion theory, we call a proof
of a theorem of the form $\forall n\exists a\ P(n,a)$
constructive if there exists
an algorithm that given $n$ computes an object  $a_n$
such that $P(n,a_n)$.
In our context
this makes no sense, as in this case the complexity
of $a_n$ is bounded by $\log n$ and we are interested in
properties $P(n,a)$ implying that
complexity of $a$ is linear in $n$.
We find reasonable the following meaning of
constructivity here: there is a probabilistic
algorithm that given $n$ with high probability  outputs such an object $a$
that $P(n,a)$. More specifically, the
probability should tend to 1 as $n$ tends to infinity.
All our examples except one from Theorem~\ref{thfine}(c)
are constructive in this sense.

The amount of common information does not determine completely
how much the strings $x$ and $y$ have in common. What reflects
this better is the ``complexity profile of $x$ and $y$'', defined as
the set of triples $(u,v,w)$ such that
$K(z)\le u$,
$K(x|z)\le v$, and $K(y|z)\le w$ for some string $z$.
We use the method
of~\cite{muchnik2} to find exact
upper and lower bounds for complexity profile
(Section~\ref{geometric-description}).
(Technically we have to speak not about strings $x$ and $y$ but
about sequences of strings $x_0,x_1,\dots$ and $y_0,y_1,\dots$
such that complexity of $x_i$ and $y_i$ is proportional to $i$;
see Section~\ref{geometric-description} for details.)

\section{The upper semi-lattice $\boldsymbol{R}$}\label{semi-lattice}

Let us recall the definition of conditional Kolmogorov
complexity. Let $U$ be a computable (partial)
function of two arguments;
arguments and values are binary strings. (Informally, $U$ is an
interpreter of some programming language, the first argument is
a program and the second one is program's input.) Let us define
$K_U(x|y)$ as $\min\{|p|\colon U(p,y)=x\}$; here $|p|$ stands
for the length of~$p$. There exists an optimal~$U$, that is,
a $U$ such that
$K_U \le K_V + O(1)$ for any other computable function~$V$. We
fix some optimal $U$ and call $K_U(x|y)$ the \emph{conditional
complexity} of~$x$ when~$y$ is known.

The \emph{unconditional} Kolmogorov complexity can be defined as
$K(x|\Lambda)$ where $\Lambda$ is the empty string. It turns out
(see, e.g.,~\cite{li-vitanyi}) that conditional complexity can
be expressed in terms of unconditional complexity. Indeed, let
us fix some computable bijection $p,q\mapsto\langle p,q\rangle$
between pairs of strings and strings. Then
        $$
K(\langle p, q\rangle) = K(p) + K(q|p) + O(\log (|p|+|q|)).
        $$

A sequence $\boldsymbol{x}=x_1,x_2,\dots$ of binary strings is
called \emph{regular} if there exist constants $c$ and $k$ such
that $|x_i|\le ci^k$ for all $i$. The set of all regular
sequences is denoted by~$R$. We define a pre-order on $R$ saying
that $\boldsymbol{x}=x_1,x_2\dots$ precedes
$\boldsymbol{y}=y_1,y_2,\dots$ if there exists a constant $c$
such that $K(x_i|y_i)\le c\log i$ for all $i$. (Let us agree
that $\log x$ means $\log_2(x+2)$ so $\log x$ is positive for
all $x\ge 0$ and we do not need to consider the case $i=1$
separately.)

The $O$-term guarantees that the definition does not change if
we replace the optimal function $U$ used in the definition of
Kolmogorov complexity by another optimal function. Moreover,
since we use $O(\log i)$ (and not $O(1)$), the definition
remains the same if we replace conditional Kolmogorov complexity
defined as above by
prefix complexity (see~\cite{li-vitanyi}  for the definition).
Indeed, these
complexities differ only by $O(\log n)$ for strings of length
$n$. Since elements of $R$ are regular, this
difference is absorbed by $O(\log i)$-term.

Two elements $\boldsymbol{x}$ and $\boldsymbol{y}$ are
\emph{equivalent} if $\boldsymbol{x}\le\boldsymbol{y}$ and
$\boldsymbol{y}\le\boldsymbol{x}$. The equivalence classes form
a partially ordered set. We denote this set by $\boldsymbol{R}$.

\begin{proposition}\label{least-upper-bound}
The set $\boldsymbol{R}$ is an upper semi-lattice: any two elements
have a least upper bound.
\end{proposition}

\begin{proof}
By definition, $\boldsymbol{z}\in\boldsymbol{R}$ is a least
upper bound of $\boldsymbol{x},\boldsymbol{y}\in\boldsymbol{R}$
if
        %
\begin{itemize}
        \item
$\boldsymbol{z}$ is an upper bound for $\boldsymbol{x}$ and
$\boldsymbol{y}$, i.e., $\boldsymbol{x}\le\boldsymbol{z}$ and
$\boldsymbol{y}\le\boldsymbol{z}$;
        \item
$\boldsymbol{z}\le\boldsymbol{u}$ for any other upper bound
$\boldsymbol{u}$ of $\boldsymbol{x}$ and $\boldsymbol{y}$.
        %
\end{itemize}

Let $\boldsymbol{x}=x_1,x_2,\dots$ and
$\boldsymbol{y}=y_1,y_2,\dots$ be any two elements of
$R$. Consider the sequence
$\boldsymbol{z}=z_1,z_2,\dots$ where $z_i=\langle x_i,
y_i\rangle$. (Recall that $p,q\mapsto\langle p,q\rangle$ denotes a
computable bijection between pairs of strings and strings.) It
is easy to see that $\boldsymbol{z}$ is regular and is
the least upper bound for
$\boldsymbol{x}$ and $\boldsymbol{y}$.
\end{proof}

\begin{theorem}\label{non-exist}
The ordered set $\boldsymbol{R}$ is not a lower semi-lattice:
there exist two
elements $\boldsymbol{x}$ and $\boldsymbol{y}$ that do not have
a greatest lower bound.
\end{theorem}

\begin{proof}
   To prove the theorem we have to construct two sequences
$\boldsymbol{x}$ and $\boldsymbol{y}$ that have no greatest
lower bound. Assume some $n$ is fixed; let us explain how $n$-th
terms of $\boldsymbol{x}$ and $\boldsymbol{y}$ are constructed.
Consider $2n$ binary strings of length $n$ denoted by
        $$
b^0_1, b^0_2,\dots, b^0_n,
b^1_1, b^1_2,\dots, b^1_n,
        $$
and one more string of length $n$ denoted by
        $$
\varepsilon = \varepsilon_1\dots\varepsilon_n
        $$
($\varepsilon_i$ are individual bits). We want all these strings to be
random and independent in the following sense: its
concatenation is a
string of length $2n^2+n$ which is incompressible (its Kolmogorov
complexity is equal to its length up to $O(1)$ additive term). Such
strings do exist, see~\cite{li-vitanyi}. Now consider two strings
        $$
x=b^0_1 b^0_2 \ldots b^0_n b^1_1 b^1_2 \ldots b^1_n
        $$
and
        $$
y=b^{\varepsilon_1}_1
  b^{\varepsilon_2}_2
        \ldots
  b^{\varepsilon_n}_n.
        $$
Strings $x$ and $y$ are $n$-th terms of the sequences $\boldsymbol{x}$
and $\boldsymbol{y}$.

Let us mention that the pair $\langle x,y\rangle$ contains the
same information as the concatenation string of length $2n^2+n$
mentioned above, so the complexity of the pair $\langle
x,y\rangle$ is $2n^2+n+O(1)$. (As $x$ is random,
$b^0_i\ne b^1_i$ for all $i$.)

In the sequel we use the following terminology. Strings
$b^{e}_{i}$ (for $e=0,1$ and $i=1,\ldots,n$) are called
\emph{blocks}. We have $2n$ blocks; each block has length $n$.
All the blocks $b^{\varepsilon_i}_i$ that are included in $y$
are called \emph{selected} blocks; all other blocks
$b^{1-\varepsilon_i}_i$ are called \emph{omitted} blocks. Our
construction starts with $n$ pairs of blocks and a string
$\varepsilon$ that says which block is selected in each pair.
The string $x$ is a concatenation of all $2n$ blocks; the string
$y$ is a concatenation of $n$ selected blocks.

Now the proof goes as follows. Each selected block is simple
relative to both $x$ and $y$ since it is a substring of both $x$
and $y$ and position information could be encoded by
$O(\log n)$ bits. (When we say that a string $u$ is
\emph{simple} relative to a string $v$ we mean that
$K(u|v)=O(\log n)$.)

Suppose that the greatest lower bound of $x$ and $y$ exists.
Let us denote it by $z$.
Then
any selected block is simple relative to $z$. On the other
hand, any omitted block could not be simple relative to $z$.
Indeed,
assume that some omitted block $b$ is simple
relative to $z$. Then $b$ is simple relative to $y$ since $z$ is
simple relative to $y$ by assumption. Then to restore $x$ from
$y$ it is enough to specify the string $\varepsilon$ and $n-1$
omitted blocks different from $b$, i.e., $n^2$ bits, and the
complexity of pair $\langle x,y\rangle$ is at most $2n^2+O(\log
n)$ ($n^2$ bits in $y$ and $n^2$ bits to specify $x$ when $y$ in
known). This contradiction shows that no omitted block is simple
relative to $z$.

Now let us show that $y$ is simple relative to $x$. Indeed, to
find $y$ when $x$ is known we need only to distinguish between
omitted and selected blocks in each pair of blocks. We may
assume that $z$ is known since it is simple relative to $x$.
Then we may enumerate all the objects that have small complexity
relative to $z$ until we find $n$ blocks (we have the list of
all blocks since we know $x$). These $n$ blocks will be (as
shown above) exactly the selected blocks, and we are done. So $y$ is
simple relative to $x$. But this is impossible, because in this
case the pair $\langle x,y\rangle$ will have complexity at most
$2n^2+O(\log n)$ (instead of $2n^2+n$).

In the argument above we were quite vague about $O$-notation, so
let us repeat the same argument more formally. The construction
described above is performed for each $n$; to indicate the
dependence on $n$ let us write $x(n)$ instead of $x$, $b^0_i(n)$
instead of $b^0_i$, etc. Assume that
$\boldsymbol{z}=z(0),z(1),\dots$ is a greatest lower bound of
$\boldsymbol{x}$ and $\boldsymbol{y}$. The first step in the proof
is the following lemma.

\begin{lemma}\label{lemma1}
        %
There exists some constant $c$ such that
        $$
K(b|z(n)) \le c \log n
        $$
for any $n$ and for any block $b$ that was selected at
$n$-th step of the construction. \textup{(}There were $n$
selected blocks at $n$-th step; each of them has length
$n$.\textup{)}
        %
\end{lemma}

Indeed, consider all the blocks $b$ that were selected at $n$-th
step; let $b(n)$ be one of them for which the complexity
$K(b|z(n))$ is maximal. The sequence
$\boldsymbol{b}=b(1),b(2),\dots$ belongs to $R$. It is easy to
see that $\boldsymbol{b}\le \boldsymbol{x}$ and that
$\boldsymbol{b}\le \boldsymbol{y}$, because $b(n)$ is a
substring of both $x(n)$ and $y(n)$. Therefore,
$\boldsymbol{b}\le\boldsymbol{z}$, since $z$ is the greatest
lower bound of $\boldsymbol{x}$ and $\boldsymbol{y}$. By
definition,
        $$
K(b(n)|z(n)) \le c \log n
        $$
for some constant $c$; the same inequality is valid for all
other selected blocks $b$ since $b(n)$ has maximal complexity
(relative to $z(n)$) among them. Lemma~\ref{lemma1}
is proved.

\begin{lemma}\label{lemma2}
        %
There exists some constant $c$ such that
        $$
K(b|y(n)) \ge n - c \log n
        $$
for any $n$ and for any block $b$ that was omitted at
$n$-th step of the construction.
        %
\end{lemma}

Proof. As we have said, the string $x(n)$ can be reconstructed
from the string $y(n)$, the string $\varepsilon(n)$, some
omitted block $b$, its number and the concatenation of all other
omitted blocks. Here all the information except $b$ has bit
size $n^2+n+(n^2-n)+O(\log n)=2n^2+O(\log n)$, and this
information includes $y(n)$. Therefore, the complexity of
$\langle x(n),y(n)\rangle$ does not exceed
$K(b|y(n))+2n^2+O(\log n)$. On the other hand, the complexity of
$\langle x(n),y(n)\rangle$ is $2n^2+n+O(1)$. Comparing the two
inequalities, we see that $K(b|y(n)) \ge n - O(\log n)$.
Lemma~\ref{lemma2} is proved.

\begin{lemma}\label{lemma3}
        %
There exists some constant $c$ such that
        $$
K(b|z(n)) \ge n - c \log n
        $$
for any $n$ and for any block $b$ that was omitted at
$n$-th step of the construction.
        %
\end{lemma}

Indeed, recall that $K(z(n)|y(n))=O(\log n)$ by our assumption;
note also that $K(b|y(n))\le K(b|z(n))+K(z(n)|y(n))+O(\log n)$.
Hence, $n-O(\log n)\le K(b|y(n))\le
K(b|z(n))+K(z(n)|y(n))+O(\log n)= K(b|z(n))+O(\log n)$.
Lemma~\ref{lemma3} is proved.

\begin{lemma}\label{lemma4}
        $$
K(\varepsilon(n)|x(n))=O(\log n).
        $$
\end{lemma}

Proof. Lemma~\ref{lemma1}
implies that for big $n$ the value $K(b|z(n))$ is less than
$n/2$ for any selected block $b$; Lemma~\ref{lemma3} implies
that for big $n$ the value $K(b|z(n))$ is bigger than $n/2$ for
any omitted block $b$. Therefore, knowing $x(n)$ and $z(n)$ we
can reconstruct the list of selected blocks just enumerating the
strings $s$ such that $K(s|z(n)) < n/2$ until $n$ blocks from
$x(n)$ appear. Since $K(z(n)|x(n))=O(\log n)$ by assumption, we
need only $O(\log n)$ additional bits to reconstruct
$\varepsilon(n)$ from $x(n)$. Lemma~\ref{lemma4} is proved.

We
conclude that $K(\langle x(n), \eps(n)\rangle)$ is $2n^2+O(\log n)$
but it should be $2n^2+n+O(1)$. The contradiction shows that
$\boldsymbol{x}$ and $\boldsymbol{y}$ do not have the greatest
lower bound.
        %
\end{proof}


Let us mention some other properties of the semi-lattice
$\boldsymbol{R}$.

1. The operations ``infimum'' and ``supremum'' do not satisfy
the distributive law even when they are defined. Indeed,
consider sequences $\boldsymbol{x}$ and $\boldsymbol{y}$ where
$x_n$ and $y_n$ are random independent strings of length $n$.
Let $z_n=x_n\oplus y_n$ (bitwise addition modulo $2$). Then
        $$
\sup(\inf(\boldsymbol{x},\boldsymbol{y}),\boldsymbol{z})\ne
          \inf(\sup(\boldsymbol{x},\boldsymbol{z}),
               \sup(\boldsymbol{y},\boldsymbol{z})),
        $$
since
      $\inf(\boldsymbol{x},\boldsymbol{y})=\boldsymbol{\Lambda}$
(where $\boldsymbol{\Lambda}$ is the least
element of the
semi-lattice), so the left-hand side is equal to $\boldsymbol{z}$
while the right-hand side is equal to
$\sup(\boldsymbol{x},\boldsymbol{y})$.

Moreover,
        $$
\inf(\sup(\boldsymbol{x},\boldsymbol{y}),\boldsymbol{z})\ne
          \sup(\inf(\boldsymbol{x},\boldsymbol{z}),
               \inf(\boldsymbol{y},\boldsymbol{z})),
        $$
since left-hand side is equal to $\boldsymbol{z}$ and right-hand
side is equal to $\boldsymbol{\Lambda}$.

2. For any two elements $\boldsymbol{x}$ and $\boldsymbol{y}$
in $\boldsymbol{R}$  there exists
a sequence $\boldsymbol z$ such that
$\sup(\boldsymbol{y},\boldsymbol{z})=
\sup(\boldsymbol{y},\boldsymbol{x})$ and $\inf(\boldsymbol{y},
\boldsymbol{z})=\boldsymbol{\Lambda}$.
Indeed, given $x$, $y$ and $K(x|y)$ we can enumerate the set
of all programs $p$ such that $p(y)=x$ and length of $p$ is equal
to $K(x|y)$. Let $z$ be the first program in this enumeration.


This $\boldsymbol z$ could be considered as a ``difference''
between $\boldsymbol x$ and $\boldsymbol y$.
Difference is not defined uniquely; for instance, if $x_n$ and
$y_n$ are random independent strings of length $n$, both $x_n$
and $x_n\oplus y_n$ are differences of $x_n$ and $y_n$.

The semi-lattice $\boldsymbol{R}$ is only one of the possible
refinements of the intuitive notion ``$x$ is simple relative to
$y$''. Here is another possibility. Let us fix a
function $\log n\le f(n)=o(n)$; assume that $\boldsymbol{x}$ and
$\boldsymbol{y}$ are sequences of strings such that
$|x_n|=O(n)$, $|y_n|=O(n)$. Define $\boldsymbol{x}\le_f
\boldsymbol{y}$ as $K(x_n|y_n)=O(f(n))$. One can show that this
definition gives a semi-lattice with similar properties (no
greatest lower bound; however, the proof is more difficult and
is omitted).

\section{Common and mutual information}\label{common}

The semi-lattice $\boldsymbol R$ is a useful tool to analyze the amount of
common information shared by two strings.

Let $x$ and $y$ be two strings. By \emph{mutual} information in
$x$ and $y$ we mean the value $I(x:y)=K(x)+K(y)-K(\langle
x,y\rangle)$. (Sometimes $I(x:y)$ is defined as $K(y)-K(y|x)$,
but these quantities differ only by $O(\log n)$ for strings of
length at most $n$, see~\cite{li-vitanyi}.)

\begin{theorem}\label{thcm}
        %
Let $\boldsymbol{x}=x_1,x_2,\dots$ and
 $\boldsymbol{y}=y_1,y_2,\dots$ be elements of $\boldsymbol R$.

\textup{(a)} If $\boldsymbol{z}=z_1,z_2,\dots$ is a lower bound
of $\boldsymbol{x}$ and $\boldsymbol{y}$ then
        \begin{equation}\label{lowerbound-inequality}
K(z_n) \le I(x_n:y_n) + O(\log n).
        \end{equation}

\textup{(b)} If $\boldsymbol{z}=z_1,z_2,\dots$ is a lower bound
of $\boldsymbol{x}$ and $\boldsymbol{y}$ and
        \begin{equation}\label{lowerbound-equality}
K(z_n) = I(x_n:y_n) + O(\log n)
        \end{equation}
then $\boldsymbol{z}$ is the greatest lower bound of
$\boldsymbol{x}$ and $\boldsymbol{y}$ in $\boldsymbol R$.
        %
\end{theorem}

\begin{proof}
        %
(a) Since $\boldsymbol{z}\le\boldsymbol{x}$,
        $$
K(\langle x_n,z_n\rangle)=K(x_n)+K(z_n|x_n)+O(\log n)=K(x_n)+O(\log n).
        $$
So
        \begin{equation}\label{ineq-a}
K(x_n)=K(\langle x_n,z_n\rangle)+O(\log n)=
      K(z_n)+K(x_n|z_n)+O(\log n).
        \end{equation}

Similarly
        \begin{equation}\label{ineq-b}
K(y_n)=K(\langle y_n,z_n\rangle)+O(\log n)=
       K(z_n)+K(y_n|z_n)+O(\log n).
        \end{equation}
On the other hand,
        \begin{equation}\label{ineq-c}
K(\langle x_n,y_n\rangle)\le
       K(z_n)+K(x_n|z_n)+K(y_n|z_n)+O(\log n).
        \end{equation}
since we can reconstruct the pair $\langle x_n,y_n\rangle$ from
$z_n$ and programs that transform $z_n$ into $x_n$ and $y_n$.
Combining the last three inequalities [$(\ref{ineq-a}) + (\ref{ineq-b}) -
(\ref{ineq-c})$],
we get the statement (a).

Let us prove the part (b) now. Assume that $\boldsymbol{z}$ is a
lower bound for $\boldsymbol{x}$ and $\boldsymbol{y}$ and the
inequality (\ref{lowerbound-inequality}) turns into equality
(\ref{lowerbound-equality}).
Let $\boldsymbol{z}'$ be any
other lower bound for $\boldsymbol{x}$ and $\boldsymbol{y}$.
Consider the sequence $\boldsymbol{z}''$ defined as
$z''_n=\langle z_n, z'_n\rangle$. It is the least upper bound of
$\boldsymbol{z}$ and $\boldsymbol{z}'$
(Proposition~\ref{least-upper-bound}). Therefore
$\boldsymbol{z}''\le \boldsymbol{x}$ and $\boldsymbol{z}''\le
\boldsymbol{y}$. Applying (a) to $\boldsymbol{z}''$ we see that
        $$
K(z''_n)=K(\langle z_n,z'_n\rangle) \le I(x_n:y_n) +O(\log n)
        $$
By assumption, $I(x_n:y_n)=K(z_n)+O(\log n)$, so $K(\langle
z_n,z'_n\rangle)\le K(z_n)+O(\log n)$. On the other hand,
$K(\langle z_n,z'_n\rangle)=K(z_n)+K(z'_n|z_n)+O(\log n)$, therefore
$K(z'_n|z_n) \le O(\log n)$ and $\boldsymbol{z}' \le
\boldsymbol{z}$ in $\boldsymbol R$.
        %
\end{proof}

Remark. If two sequences $\boldsymbol{x}=x_1,x_2,\dots$ and
$\boldsymbol{y}=y_1,y_2,\dots$ have the greatest lower bound
$\boldsymbol{z}=z_1,z_2,\dots$, one may call $K(z_n)$ ``the
amount of common information in strings $x_n$ and $y_n$''.

%However, this is not a good definition since the good one should
%use only strings $x_n$ and $y_n$ but not the whole sequences
%$\boldsymbol{x}$ and $\boldsymbol{y}$.
%In a correct definition,
%different $n$ should be considered  separately.
%Here is an attempt to give an appropriate one.
%In order not to confuse the new notion with
%the old one we use the term ``common part'' instead
%of ``lower bound''.
%A sequence $\bs z$ is called a \emph{greatest common part}
%of $\bs x$ and $\bs y$
%if $K(z_n|x_n)=\olog$, $K(z_n|x_n)=\olog$
%and
%$$
%\forall c_2\ \exists c_3\ \forall n\
%\forall z'\ (z'\le_{c_2}x_n,y_n\ \land\ |z'|\le c_2n^{c_2}
%\Rightarrow z'\le_{c_3}z_n)
%$$
%where $x\le_c y$ stands for $K(x|y)\le c\log n$.
%If $\bs z$ is a  greatest common part  of $\bs x,\bs y$
%then it is a greatest
%lower bound of $\bs x,\bs y$
%(with respect to pre-order on $R$).
%The definition of a least upper bound can be also strengthened
%in a similar way (we shall use the term
%``common source'' instead of ``upper bound'').
%Call a sequence $\bs z$ a \emph{least common source}
%of sequences $x_n$ and $y_n$ if
%$$
%\forall c_2\ \exists c_3\ \forall n\
%\forall z'\ (z'\ge_{c_2}x_n,y_n\ \land\ |z'|\le c_2n^{c_2}
%\Rightarrow z'\ge_{c_3}z_n).
%$$
%It is easy to check that  the sequence $\pair{x_n,y_n}$ is
%a least common source of $x_n$ and $y_n$
%(actually, this is true even if we omit
%the  restriction $|z'|\le c_2n^{c_2}$
%in the above definition,
%but our principle is do not consider very long strings at all).
%
%On the other hand, the informal assertion that for certain
%$\bs x,\bs y$ it is impossible to find
%maximum common part can be also understood in a stronger sense,
%than  just saying that $\bs x,\bs y$ have no greatest
%lower bound with respect to pre-order on $R$.
%Namely, say that
%$\bs x$ and $\bs y$ \emph{have no greatest lower bound everywhere} if
%for all $c_1$ there is $c_2$ such that for all $c_3$
%and all sufficiently large $n$
%$$
%\forall z(z\le_{c_1}x_n,y_n\ \land\ |z|\le c_1n^{c_1}\Rightarrow
%\exists z'\ (z'\le_{c_2}x_n,y_n\ \land\ |z'|\le c_2n^{c_2}
%\ \land\  z'\not\le_{c_3}z)).
%$$
%If $\bs x,\bs y$ have no greatest lower bound everywhere
%then they have  no greatest
%lower bound with respect to pre-order on $R$. Note that
%sequences
%$(\bs x,\bs y)$ constructed in the proof of Theorem~\ref{non-exist}
%have no greatest lower bound  everywhere
%(and moreover there is $c_2$ such that for all
%$c_1,c_3$ and all  sufficiently large $n$ the displayed assertion
%is true).


\section{Examples where common information is less than
         mutual information}\label{common-mutual}

Informally speaking, strings $x$ and $y$ have $u$-bit common
information $z$ if $K(z)=u$, $K(z|x)\approx 0$, and
$K(z|y)\approx 0$.
We know (Theorem~\ref{thcm}\textup{(a)}) that the amount of
common information in two strings
is not larger than the mutual information of these strings.
A natural related question is the following one:
can common information be far less than mutual information?

This question was positively answered by G\'acs and
K\"orner~\cite{gacskorner}.
They  found out that there are pairs of strings $x$
and $y$ such that $I(x:y)$ is big but nevertheless any string
$z$ that is simple relative to both $x$ and $y$ (both $K(z|x)$
and $K(z|y)$ are small) is simple (has small $K(z)$).

Their construction uses ideas from Shannon information theory.
Another construction was suggested in~\cite{muchnik1}
(see~\cite{muchnik2} for details). Here we present a third way
to construct examples of that kind.

Consider a finite field $F_n$ of cardinality $q=q_n$ close to $2^n$.
(Any field of size $2^{n+O(1)}$ will work, so we may use the
field of cardinality $2^n$ or the field $\mathbb{Z}/q\mathbb{Z}$
where $q$ is a prime number between $2^n$ and $2^{n+1}$.)
Consider three-di\-men\-sional vector space over $F_n$. Any non-zero
vector $(f_1,f_2,f_3)$ generates a line (by ``line'' we mean a
line going through $0$, i.e., one-di\-men\-sional subspace). Two
lines generated by $(f_1,f_2,f_3)$ and $(g_1,g_2,g_3)$ are
called orthogonal if $f_1g_1+f_2g_2+f_3g_3=0$. Now consider two
random orthogonal lines $x$ and $y$ (i.e. pair of two orthogonal
lines $( x,y)$ which
has the greatest possible complexity).
We claim that $I(x:y)$ is
significant but there is no string $z$ which is simple relative
to both $x$ and $y$ unless $z$ is simple.

More precisely, consider the set
$$
O=\{( x,y) :
\text{$x$ and $y$ are orthogonal lines}\}.
$$
This set contains
$q^3+o(q^3)$ elements (there are $q^2+q+1$ lines and each
line is orthogonal to $q+1$ lines). Therefore, $O$ contains a
pair $(x,y)$ whose complexity is $\log (q^3(1+o(1)))=
3n+O(1)$. (We assume that elements of $F_n$ are encoded by
binary strings of length $n+O(1)$,
so we can speak about complexities.) Note
that $K(x)\le 2n+O(\log n)$ since there are about $2^{2n}$
lines; moreover, $K(y|x)\le n+O(\log n)$ since $y$ is one of
$2^{n+O(1)}$ lines orthogonal to $A$. Recalling the inequality
$K(\langle x,y\rangle) \le K(x)+K(y|x)+O(\log n)$,
we conclude that $K(x)=2n+O(\log n)$ and $K(y|x)=n+O(\log
n)$. For similar reasons $K(y)=2n+O(\log n)$ and $K(x|y)=n+O(\log
n)$. Therefore, $I(x:y)=n+O(\log n)$.

Remark. We would like to caution against free usage of geometrical
intuition in our context. For instance, though we use the term
``orthogonal", we have no scalar product in linear spaces over finite
fields and a nonzero vector may be orthogonal to itself.

\begin{theorem}\label{random-orthogonal-lines}
        %
Let $\langle x_n,y_n\rangle$ be a random pair of orthogonal
lines in the three-di\-men\-sional space over $F_{n}$.
For any sequence of strings
$z_n$
        $$
K(z_n) \le 2K(z_n|x_n) + 2K(z_n|y_n) + O(\log n)
        $$
assuming that $z_n$ has polynomial \textup{(}in $n$\textup{)}
length. \textup{[}The constant in $O(\log n)$-notation does not
depend on $n$.\textup{]}

\end{theorem}

This theorem implies that sequences
$\boldsymbol{x}=x_1,x_2,\dots$ and
$\boldsymbol{y}=y_1,y_2,\dots$ have
$\boldsymbol{\Lambda}=\Lambda,\Lambda,\ldots$ as their greatest
lower bound. (Here $\Lambda$ denotes the empty string.) Indeed,
if $K(z_n|x_n)=O(\log n)$ and $K(z_n|y_n)=O(\log n)$ for some
sequence $\boldsymbol{z}=z_1,z_2,\dots$, then $K(z_n) =
O(\log n)$ according to Theorem~\ref{random-orthogonal-lines}.

\begin{proof}
        %
The proof of Theorem~\ref{random-orthogonal-lines} is based on a
simple combinatorial observation.

\begin{lemma}\label{lemmaa}
        %
Consider a bipartite graph with $k$ vertices $1,\dots,k$
on the left and $l$ vertices $1,\dots,l$ on the right. Assume
that for any two different
nodes $u,v$
on the left there are at most $r$ nodes on the right connected with both
$u,v$. Then the
following bound for the number of edges $|E|$ is valid:
        %
\begin{itemize}
        \item
$k\le \sqrt{l/r}\Rightarrow |E|\le 2l;$
        \item
$k\ge \sqrt{l/r}\Rightarrow |E|\le 2k\sqrt{lr}.$
        %
\end{itemize}
        %
\end{lemma}

Indeed, for each element $v$ on the left consider the set $N_v$
of its neighbors on the right; let $n_v$ be the cardinality of
$N_v$. The intersection $N_v\cap N_w$ (for $v\ne w$) contains at
most $r$ elements. Assume that $k\le \sqrt{l/r}$.
Consider the union of all $N_v$; it has at least
        $$
n_1+n_2+\ldots+n_k-\sum_{i<j} |N_i \cap N_j|
        $$
elements. On the other hand, it has at most $l$ elements.
The number of
pairs $\langle i,j\rangle$ is less than
$k^2 \le l/r$, therefore
        $$
n_1+n_2+\ldots+n_k-(l/r)r\le l\Rightarrow
|E|=n_1+n_2+\ldots+n_k\le 2l.
        $$

The first statement is proved. It implies that for $k=\sqrt{l/r}$ (we
assume here that the number $\sqrt{l/r}$ is integer; the
proof can be easily modified to handle the general case) the
average number of neighbors for vertices on the left is at most
$2\sqrt{lr}$. We use this observation to prove the second part of the
lemma.

Let $k\ge\sqrt{l/r}$. Consider $\sqrt{l/r}$ vertices on the left
having maximum neighborhoods and delete all other vertices on
the left; this makes the average number of neighbors bigger. But
we know that it does not exceed $2\sqrt{lr}$. The same is true
for the initial graph, therefore $|E|\le k\cdot2\sqrt{lr}$.
Lemma~\ref{lemmaa} is proved.

This lemma will be applied to a bipartite graph whose vertices
(both on the left and on the right) are lines; edges connect
pairs of orthogonal lines. It is easy to see that we can let
$r=1$ (if both $x,y$ are orthogonal to
both $ z,u$ and $x\ne y$ then $z=u$).

Now we are ready to prove Theorem~\ref{random-orthogonal-lines}.
As we know, $K(x)=K(y)=2n$ and $K(\langle x,y\rangle)=3n$ (from
now on we omit $O(\log n)$-terms for brevity). Let $K(z|x)=p_1$ and
$K(z|y)=p_2$. We want to get an upper
bound for $m=K(z)$. First, let us compute $K(x|z)$ and $K(y|z)$:
$$
K(x|z) = K(\langle x,z\rangle) - K(z)
=K(x)+K(z|x)-K(z)=2n+p_1-m.
$$
Similarly, $K(y|z)=2n+p_2-m$. Consider the set $P$ of all lines
whose complexity relative to $z$ does not exceed $K(x|z)$; this
set contains line $x$ and has cardinality $2^{2n+p_1-m}$ (up to a
polynomial in $n$ factor). Similarly we get a set $Q$ that
contains lines whose complexity relative to $z$ does not exceed
$K(y|z)$; this set has cardinality $2^{2n+p_2-m}$. Consider a
bipartite graph whose edges connect orthogonal lines from $P$
and $Q$. This graph satisfies the lemma for
$r=1$, so the number of
edges $|E|$ does not exceed
$$
        \begin{cases}
2^{2n+p_2-m} &\text{if } (2n+p_1-m) \le \frac{2n+p_2-m}{2};\\
2^{2n+p_1-m}\cdot\sqrt{2^{2n+p_2-m}}
         &\text{if } (2n+p_1-m) \ge \frac{2n+p_2-m}{2}.
        \end{cases}
$$
On the other hand, the pair $\langle x,y\rangle$ represents
one of the edges of that graph. If $z$ is known, we can enumerate
$P$, $Q$ and $E$, so the pair $\langle x,y\rangle$ may be described
by its number in $E$. Hence
 $3n=K(\langle x,y\rangle)\le K(z)+\log |E|$.
Therefore, the two bounds for $|E|$ imply
\begin{align*}
3n \le  m + (2n+p_2-m) &\Rightarrow n \le p_2\\
\intertext{(the first one) and}\\
3n \le  m + (2n+p_1-m)+\frac{1}{2}(2n+p_2-m) &\Rightarrow
                m \le 2p_1+p_2
\end{align*}
(the second one). We have to prove that $m\le 2p_1+2p_2$ (recall
that logarithmic terms are omitted). In the second case it is
evident; in the first case one should note that $K(z)\le
K(z|x)+K(x) \le p_1 + 2n \le p_1+2p_2 \le 2p_1+2p_2$.
        %
\end{proof}

Remark. The same example may be reformulated in several ways.
Replacing line $y$ by the orthogonal plane $y^{\perp}$, we may
say that $\langle x,y\rangle$ is a random pair $\langle
\text{line $x$},\text{plane $y$ going through $x$}\rangle$. We
may then switch from projective plane to affine plane and say
that $\langle x,y\rangle$ is a random pair $\langle\text{point
$x$}$ on the affine plane, line $y$ that goes $\text{through
$x$}\rangle$. Indeed, fix any affine plane $P$ not going through
zero. Then $x$ may be identified with the common point of $P$
and $x$ and plane $y$ with the common line of $y$ and $P$. (We
lose lines that are parallel to $P$, but those lines are not
random.) The third way (used in~\cite{muchnik2})
to reformulate the example is to say that
$x=(a,b)$ and $y=(c,ac+b)$ where $(a,b,c)$ is a random triple of
elements of $F$. Indeed, $x=(a,b)$ identifies the affine line
$\{(u,v)\mid v=au+b\}$ (again we lose affine lines that are
parallel to the line $u=0$, but all those lines are not random)
and $y=(c,ac+b)$ is a point on that line.

Using Lemma~\ref{lemmaa} we can prove that
 several other examples of pairs have no common
information. Here are two of them:

\begin{theorem}\label{more-examples}
        %
\textup{(a)} Let $\langle x_n,y_n\rangle$ be a random pair of orthogonal
lines in four-di\-men\-sional space over $F_{n}$.
For any sequence of strings $z_n$
        $$
K(z_n) \le 2K(z_n|x_n) + 2K(z_n|y_n) + O(\log n)
        $$
assuming that $z_n$ has polynomial \textup{(}in $n$\textup{)}
length.

\textup{(b)} The same is true if $\langle x_n,y_n\rangle$ is a random
pair of intersecting affine lines (one-di\-men\-sional affine
subspaces) in three-di\-men\-sional affine space over $F_{n}$.

\end{theorem}

\begin{proof}
(a) The proof goes along the same lines as the proof
of the previous theorem,
so we just outline the main points.
\begin{itemize}
\item
$K(x)=K(y)=3n$ and $K(\langle x,y\rangle)=5n$
(we omit $O(\log n)$-terms).
Thus, in this case $K(x|z) =K(x)+K(z|x)-K(z)=3n+p-m$
and $K(y|z)=3n+q-m$.

\item We consider the same bipartite graph
(but now a line means a line in a four-di\-men\-sional space).
This time the conditions of
Lemma~\ref{lemmaa} are fulfilled for  $r=2^n$, because the number
of lines in four-di\-men\-sional space
orthogonal to two different given lines is $2^n$.

\item Thus the number of
edges $|E|$ does not exceed
        \begin{align*}
2^{3n+q-m} &\text{\; if\;\;\:} (3n+p-m) \le \frac{2n+q-m}{2};\\
        %
2^{3n+p-m}\cdot\sqrt{2^{4n+q-m}}
         &\text{\; if\;\;\:}
              (3n+p-m) \ge \frac{2n+q-m}{2}.
        \end{align*}

\item On the other hand,
$5n=K(\langle x,y\rangle)\le K(z)+\log |E|$.
Therefore, the two bounds for $|E|$ imply
        $$
5n \le  m + (3n+q-m) \Rightarrow 2n \le q
        $$
(the first one) and
        $$
5n \le  m + (3n+p-m)+\frac{1}{2}(4n+q-m) \Rightarrow
                m \le 2p+q
        $$
(the second one).

\item In the  first case one should note that $K(z)\le
K(z|x)+K(x) \le p + 3n \le p+\frac32q \le 2p+2q$.
\end{itemize}

(b)
This time we  connect by edges affine  lines
that  have a common point, thus
the conditions of the lemma are true for
$r=2^{2n}$ (there are this many affine lines intersecting
two  given different affine lines).
The rest is as follows:
\begin{itemize}
\item
 $K(x)=K(y)=4n$ and $K(\langle x,y\rangle)=7n$
(omitting  $O(\log n)$-terms),
\item $K(x|z) = 4n+p-m,\quad K(y|z)=4n+q-m$,
\item the number of edges $|E|$ does not exceed
$2^{4n+q-m}$ if     $(4n+p-m) \le \frac{2n+q-m}{2}$ and
$2^{4n+p-m}\cdot\sqrt{2^{6n+q-m}}$ if
$(4n+p-m) \ge \frac{2n+q-m}{2}$,
\item hence
  $7n \le  m + (4n+q-m) \Rightarrow 3n \le q$ in the first case and
 $7n \le  m + (4n+p-m)+\frac{1}{2}(6n+q-m) \Rightarrow
                m \le 2p+q$ in the second
case. In the first case one should note that $K(z)\le
K(z|x)+K(x) \le p + 4n \le p+\frac43q \le 2p+2q$.
\end{itemize}

\end{proof}

%Remark. The method based on Lemma~\ref{lemmaa} will work
%for pairs of orthogonal $k$-di\-men\-sional subspaces
%of $m$-di\-men\-sional space for any $m\ge3k$.

Let us note that in these examples some $z_n$ still have more
information about $x_n$ and $y_n$ than one could expect. For
example, if in (b) we consider the intersection point $p_n$ of
$x_n$ and $y_n$, then $K(p_n)= 3n$, $K(x_n|p_n)= 2n$,
$K(y_n|p_n)= 2n$
(omitting  $O(\log n)$-terms). There are some $x'_n$ and $y'_n$ with the
same complexities ($K(x'_n)= 4n$, $K(y'_n)= 4n$,
$K(\langle x'_n,y'_n\rangle)= 7n$) for which there is no $p_n$
with similar properties.
(Remark:  Instead of intersection point we could consider
two-di\-men\-sional affine subspace that contains both lines.)

For (a) one also can find $p_n$ that contain more information
about $x_n$ and $y_n$ than one could expect. The way to
construct such $p_n$ was pointed by Finkelberg and
Bezrukawnikov.
Let $W$ be the two-di\-men\-sional subspace (a plane)
containing the vectors $(1,0,0,0)$ and
$(0,1,0,0)$ (the choice of $W$  is not important:
any plane $W$ with $K(W)=\olog$ would work). Let $w$ be any line in $W$
orthogonal to $y$ (obviously it exists).
Take as $P$ the plane having the lines $x$ and $w$ (as $x$ is random,
$x\not\in W$).  Let us note
that $P$ has 1-di\-men\-sional intersection with $W$ and the
number of planes with this property is about $2^{3n}$,
therefore $K(P)\le3n+\olog$. The number of
lines in $P$ is about $2^n$, thus $K(x|P)\le n+\olog$. The
line $y$ is orthogonal to both $x,w$, therefore this line is
orthogonal to $P$. The number of lines orthogonal to $P$ is about $2^n$,
therefore $K(y|P)\le n+\olog$.

This effect (some $p$ contains more information about $x$ and
$y$ than one could expect) is analyzed in
Section~\ref{geometric-description}.

% rwalk-m.tex

\newcommand{\calo}{{ O}}
\newcommand{\calr}{{\cal R}}
\newcommand{\poly}{{\rm poly}}
\newcommand\Prob{\mathop{\rm Prob}\nolimits}
\newtheorem{definition}{Definition}

\section{More examples: a new method}
The examples of Theorem~\ref{random-orthogonal-lines}
and~\ref{more-examples}~(a)
are specific cases of the following example.
Let $m,k$ be integer constants and let
$x_n$ and $y_n$ be random  orthogonal $k$-di\-men\-sional subspaces
of an  $m$-di\-men\-sional linear  space  over   $F_n$.
(Recall that $F_n$ denotes
a field having about $2^n$ elements.)
If $m<2k$ then there are no orthogonal $k$-di\-men\-sional subspaces. If
$m=2k$ then $x_n$ determines $y_n$ uniquely, hence their greatest
lower bound is equal to $x_n$.
So we will assume that $m>2k$. It was proven in~\cite{rom}
 that for any such $m,k$
the greatest  lower
bound of $\bs x,\bs y$ is the
sequence ${\bs  \Lambda}=\Lambda,\Lambda,\ldots$.
%In the case  $m\ge 3k$ we can just use
%Lemma~\ref{lemmaa} but for other $m,k$ we need another method.
Note that the most interesting case is
when $m$ is close to $2k$
because then  the
mutual information of $x_n,y_n$ is close to complexities
of both $x_n,y_n$. Indeed,  it is easy to verify that
 $$\begin{array}{l}
   K(x_n)=(mk-k^2)n+\calo(\log n),\nonumber\\
   K(y_n)=(mk-k^2)n+\calo(\log n),\nonumber\\
   I(x_n:y_n)=k^2n+\calo(\log n). \nonumber
  \end{array}$$
So, the  fraction $I(x_n:y_n)/K(x_n)$ is close to $1$ as $k/m$
is close  to
$1/2$ (recall that $k,m$ are fixed thus the constants in O-notation may
depend on $k,m$).
In this section, we give a new proof of the result of~\cite{rom}
using clearer combinatorial arguments.


\begin{theorem}[\cite{rom}] \label{romash}
Let $2k<m$ and $x_n$ and $y_n$ be
random  orthogonal $k$-di\-men\-sional subspaces
of an  $m$-di\-men\-sional linear  space  over   $F_n$
(where $F_n$ is
a field having about $2^n$ elements).
Then there are positive $c_1,c_2$ such that the following holds.
For any sequence of strings $z_n$
such that $K(z_n|x_n),K(z_n|y_n)<c_1n$,
we have $K(z_n)\le c_2(K(z_n|x_n)+K(z_n|y_n))+O(\log n)$.
(The constant in $O$-notation may
depend on $m$ but not on $n$.)
\label{rw}
\end{theorem}
\begin{proof}
Recall the proof of  Theorem~\ref{random-orthogonal-lines}.
Using a combinatorial property of  the graph
whose nodes
are   $1$-di\-men\-sional subspaces
of the $3$-di\-men\-sional space over
$F_n$ and edges connect orthogonal subspaces, we proved
that any its subgraph has few edges.
(A subgraph of a graph $(V,E)$ is a graph of the form
$(U,E\cap (U\times U))$
where $U\subseteq V$.) That property stated that any two nodes
have at most one
common neighbor. Now this property
does not hold and we shall define another one.
Graphs satisfying that
property will be called
$t,\eps$-oblivious.
(Now
we shall  consider ordinary undirected
graphs, not bipartite ones.)
Then we will prove an appropriate analog of Lemma~\ref{lemmaa} for
$t,\eps$-oblivious graphs.

Assume that starting from a node
$v\in V$ we make $t$ moves of a random walk
in the finite graph $(V,E)$; on every step we move to a random neighbor
of the current node. Let $v(t)$ stand for the end  node of the
walk. The graph is called \emph{$t,\eps$-oblivious}
if for any $v\in V$ and for any
$U\subseteq V$,
$$
\Prob[v(t)\in U]\le \frac{|U|}{|V|}+\eps.
$$


\begin{lemma} Let $(V,E)$ be the graph
whose nodes
are   $k$-di\-men\-sional subspaces
of the $m$-di\-men\-sional space  over
$F_n$ and edges connect orthogonal subspaces.
Then $(V,E)$ is $t,\eps$-oblivious, where
$t=2\lceil k/(m-2k)\rceil$, and $\eps=C2^{-n}$
(where $C$ is a positive real depending on $m$ but not on $n$).
\end{lemma}
\begin{proof}

Let $a,b$ be two subspaces of the $m$-di\-men\-sional
space over $F_n$. It is well known that
$$
\dim a +\dim b=\dim (a\cup b) +\dim (a\cap b).
$$
Here $a\cup b$ stands for linear sum of $a$ and $b$.
Hence $\dim(a\cap b)\ge\dim a +\dim b-m$.
Assume that $a$ is fixed, $\dim a=k$,
and $b$ is a random $l$-di\-men\-sional subspace.
With overwhelming probability the dimension of $a\cap b$
is as low as possible (that is, $\max\{0;k+l-m\}$). More precisely,
the following claim is true.

{\bf Claim~1.}
The probability of the event
  $$\dim(a\cap b)=\max\{0;k+l-m\}$$
is at least $(1-C2^{n})$  for some positive $C$
depending only on $m$.
(We postpone the proof of the claim to the end of the proof
of the theorem.)


Let $a$ and $b$ be
$k$-di\-men\-sional subspaces such that
  $$\left\{
   \begin{array}{rcl}
    \dim(a\cap a^\bot)&=&r_0\\
    \dim(a\cap b)&=&r_1\\
    \dim(a^{\bot}\cap b)&=&r_2\\
    \dim(a\cap a^{\bot}\cap b)&=&r_3\\
    \dim((a\cup a^{\bot})\cap b)&=&r_4.
    \end{array}
    \right.
  $$
where $a^{\bot}$ stands for
orthogonal complement to $a$.
(Note that intersection of $a$ and $a^\bot$
may be nontrivial.)
Let $c$ be a random $k$-di\-men\-sional  subspace from  the  orthogonal
complement to $b$.

{\bf Claim~2.} For some positive $C$ depending only on $m$
with probability greater than
$(1-C2^{-n})$ it holds
  $$\left\{
   \begin{array}{rcl}
    \dim(a\cap c)&=&\max\{0;r_2-(m-2k)\}\\
    \dim(a^{\bot}\cap c)&=&r_1\\
    \dim(a\cap a^\bot\cap c)&=&\max\{0;r_4-(m-k-r_0)\}\\
    \dim((a\cup a^\bot)\cap c)&=&r_3+k-r_0.
    \end{array}
    \right.
  $$
Proof of the claim.
Find first the dimension of intersection of  $a$ with the orthogonal
complement to $b$. As  $\dim a^\bot=m-\dim a=m-k$, we have
 \begin{eqnarray}
&&\dim(a\cap b^\bot)=\dim(a^\bot\cup b)^\bot
=m-\dim(a^\bot\cup b)=             \nonumber\\
&&m-(\dim a^\bot+\dim b-\dim (a^\bot\cap b))
= m-((m-k)+k-r_2)=r_2.\nonumber
 \end{eqnarray}
As $a\cap c=(a\cap  b^\bot)\cap c$ we can find the most
probable dimension of $a\cap  c$ by
applying Claim~1 to  subspaces $a\cap b^\bot$ and $c$
of the linear space $b^\bot$. Thus we obtain
 $$\dim(a\cap  c)=\max\{0;r_2+k-(m-k)\}=
 \max\{0;r_2-(m-2k)\}$$
with probability
at least $(1-C2^{-n})$.

In a similar way  we  find the most probable
dimension of intersection of subspaces $a^\bot$
and $c$. We have:
 $$
 \begin{array}{l}
 \dim(a^\bot\cap b^\bot)=\dim(a\cup b)^\bot
 =m-\dim(a\cup b)=           \\
 =m-(\dim a+\dim b-\dim (a\cap b))
 =m-(k+k-r_1)=m-2k+r_1.\nonumber
 \end{array}
 $$
Applying Claim~1 to subspaces    $a^\bot\cap
b^\bot$ and $c$ of linear  space
$b^\bot$ we see that
 $$\dim(a^\bot\cap c)=\max\{0;(m-2k+r_1)+k-(m-k)\}=
   \max\{0;r_1\}$$
with  probability  at least   $(1-C2^{-n})$.


In a similar way   we obtain
  $$
  \begin{array}{l}
  \dim(a\cap a^\bot\cap b^\bot)=m-\dim(a\cup a^\bot\cup b)=\\
  =m-\dim(a\cup a^\bot)-\dim b+\dim((a\cup a^\bot)\cap b)= \\
  =m-(m-r_0)-k+r_4=r_0-k+r_4.\nonumber
  \end{array}
  $$
Thus
$$
\dim(a\cap a^\bot\cap c)=\max\{0;(r_0-k+r_4)+k-(m-k)\}=
\max\{0;k+r_4-m+r_0\}
$$
with  probability  at least   $(1-C2^{-n})$.

Finally,
  $$
  \begin{array}{l}
  \dim((a\cup a^\bot)\cap b^\bot)=m-\dim((a\cap a^\bot)\cup b)=\\
  =m-\dim(a\cap a^\bot)-\dim b+\dim(a\cap a^\bot\cap b)= \\
  =m-r_0-k+r_3.\nonumber
  \end{array}
  $$
Thus
$$
\dim((a\cup a^\bot)\cap c)=\max\{0;(m-r_0-k+r_3)+k-(m-k)\}=
r_3+k-r_0
$$
with  probability  at least   $(1-C2^{-n})$.
The claim is proven.

Fix an arbitrary $v\in V$. Denote by $r_0$ dimension of intersection
$v\cap v^\bot$.
Let $S_i$ stand for the set of all
$u\in V$ such that
       $$\left\{
        \begin{array}{rcl}
         \dim (v\cap u)&=&r_1(i)\\
         \dim (v^{\bot}\cap u)&=&r_2(i)\\
         \dim (v\cap v^{\bot}\cap u)&=&r_3(i)\\
         \dim ((v\cup v^{\bot})\cap u)&=&r_4(i),
         \end{array}
         \right.
       $$
where $r_1(0)=k$, $r_2(0)=r_0$, $r_3(0)=r_0$, $r_4(0)=k$, and
       $$\left\{
        \begin{array}{rcl}
         r_1(i+1)&=&\max\{0;r_2(i)-(m-2k)\}\\
         r_2(i+1)&=&r_1(i)\\
         r_3(i+1)&=&\max\{0;r_4(i)-(m-k-r_0)\}\\
         r_4(i+1)&=&r_3(i)+k-r_0.
         \end{array}
         \right.
       $$
The above recurrence implies that
  $$\left\{
   \begin{array}{rcl}
    r_1(i+2)&=&\max\{0;r_1(i)-(m-2k)\}\\
    r_2(i+2)&=&\max\{0;r_2(i)-(m-2k)\}\\
    r_3(i+2)&=&\max\{0;r_3(i)-(m-2k)\}\\
    r_4(i+2)&=&\max\{k-r_0;r_4(i)-(m-2k)\},
    \end{array}
    \right.
  $$
hence $r_1(t)=r_2(t)=r_3(t)=0$, $r_4(t)=k-r_0$
(recall that $t=2\lceil k/(m-2k)\rceil$).
By Claim~1 the probability for a random
$x\in V$ to get into $S_t$ is at least
$1-C2^{-n}$ for some $C$ depending only on $m$.

Let $v(i)$, $i\le t$ denote the $i$th node
in a random walk starting from $v$ (and $v(0)=v$).
Let $G_i$ stand for the event
$$
v(0)\in S_0,v(1)\in S_1,\dots,v(i)\in S_i.
$$
Using Claim~2
it is  easy  to prove  by induction
that  for any $v\in V$ the
probability of $G_i$
is at least $1-C2^{-n}$ (where  $C$ depends on $m$ only).

{\bf Claim~3.}
Let $a,b$ and $c$ be  as in Claim~2.
The probability of event
 $$\left\{
  \begin{array}{rcl}
   \dim(a\cap c)&=&q_1\\
   \dim(a^{\bot}\cap c)&=&q_2\\
   \dim(a\cap a^{\bot}\cap c)&=&q_3\\
   \dim((a\cup a^{\bot})\cap c)&=&q_4
   \end{array}
   \right.
 $$
is a function of $k,r_0,r_1,r_2,r_3,r_4,q_1,q_2,q_3,q_4$
(but it does not depend on
the choice of $a$ and $b$).
(We postpone the proof of the claim to the end of the proof
of the theorem.)

{\bf Claim~4.} The probability
$\Prob[v(i)=u_i| G_i]$ is the same for
all $u_i\in S_i$ (and hence is equal to $1/|S_i|$).

Proof of the claim. The proof is by induction on $i$.
For $i=0$ the statement is trivial. Let $i>0$
and $u_i\in S_i$. We have
\begin{align*}
\Prob[v(i)=u_i|G_i]=
\Prob[v(i)=u_i|G_{i-1}]\frac{\Prob[G_{i-1}]}{\Prob[G_{i}]}.
\end{align*}
The second factor does not depend on $u_i$, so
it remains to prove that neither does the first factor.
Let $U_i^\bot$ denote the set of all $u\in V$ orthogonal to $u_i$.
We have
\begin{align*}
\Prob[v(i)=u_i|G_{i-1}]
=\sum_{u_{i-1}\in S_{i-1}\cap U_i^\bot}
\frac{\Prob[v(i-1)=u_{i-1}|G_{i-1}]}{M},
\end{align*}
where $M$ stands for the number of $k$-di\-men\-sional
subspaces orthogonal to a fixed $k$-di\-men\-sional subspace.
By induction hypothesis the numerator of the
last fraction is equal to $1/|S_{i-1}|$,
therefore  we have
\begin{align*}
\Prob[v(i)=u_i|G_{i-1}]
=\sum_{u_{i-1}\in S_{i-1}\cap U_i^\bot}
\frac{1}{M|S_{i-1}|}
=\frac{|S_{i-1}\cap U_i^\bot|}{M|S_{i-1}|}.
\end{align*}
The factor
$|S_{i-1}\cap U_i^\bot|/M$
is equal to the probability of the event
``a random
$x\in V$ orthogonal to $u_i$ belongs
to $S_{i-1}$''. By Claim~3 this probability does not depend
on $u_i\in S_i$. (End   of proof  of Claim~4.)

By Claim~4
for any $U\subseteq V$ we have
$$
\Prob[v(t)\in U|G_t]=|U\cap S_t|/|S_t|
$$
Therefore,
\begin{align*}
 \Prob[v(t)\in U]
=&\Prob[v(t)\in U|{G_t}]\cdot\Prob[G_t]
+\Prob[v(t)\in U, \bar{G_t}]\\
\le&|U\cap S_t|/|S_t|+\Prob[\bar{G_t}].
\end{align*}
The second term is bounded by $C2^{-n}$.
Estimate the first term:
$$
\frac{|U\cap S_t|}{|S_t|}\le\frac{|U|}{|V|(1-C2^{-n})}
\le\frac{|U|}{|V|}+C'2^{-n}.\qed
$$
\renewcommand{\qed}{}
\end{proof}

\begin{lemma} Assume that every node in a $t,\eps$-oblivious
graph $(V,E)$ has degree $d$ or less. Then
the number of edges in any subgraph $U$ of $V$ is at most $\alpha|U|$,
where
$$
\alpha=\left\lfloor  d\left(  \frac{|U|}{|V|}  +\eps
\right)^{1/t}\right\rfloor.
$$
\label{lem4}
\end{lemma}

\begin{proof}
Define $U'\subseteq U$ as follows.
Let us start with $U'=\emptyset$
and iterate the following step:
if there is a node     $v\in U\setminus U'$ that
has at most  $\alpha$  adjacent nodes in
$U\setminus U'$ then choose any such node and include it in $U'$.
Otherwise halt.
The resulting subgraph  $U'$ has at most $\alpha|U'|$ edges,
as on each step  the number of edges that are incident to some node in
$U'$ increases
at most by $\alpha$. Another useful property of $U'$ is as follows:
any node $v\in U\setminus U'$ has at least $\alpha+1$ neighbors
in the set $U\setminus U'$.
Let us prove that actually
$U'$ coincides with $U$. Suppose this is not true. Then
choose a node $v\in U\setminus U'$.
We have
  $$
\Prob[v(t)\in U\setminus U']\ge
\left(\frac{\alpha+1}{d}\right)^t> \frac{|U|}{|V|}+\eps.
$$
On the other hand,
$$
\Prob[v(t)\in U\setminus U']\le\Prob[v(t)\in U]\le
\frac{|U|}{|V|}+\eps.
$$
These two inequalities are inconsistent,
this proves that $U'=U$, thus the number of edges in
 $U$ is at most $\alpha|U|$.
\end{proof}

\begin{lemma}
Let $t$ be an integer  number and $0<\eps<1$ a real number.
Let $G=(V,E)$ be a $t,\eps$-oblivious
graph in which any node has degree $d$. Let $(u,v)$ be a random
edge in $G$ (that is, $K(u,v|G)\ge\log|E|$)
and let $z$ be a string. Then at least one of the following three
inequalities holds:
\begin{gather*}
K(z|u,G)\ge\frac 1t\left(\log\frac1\eps-1\right),\\ %\quad
K(z|v,G)\ge\frac 1t\left(\log\frac1\eps-1\right),\\
K(z|G)<(t+1)\max\{K(z|u,G),K(z|v,G)\}+O
\left(\log \left(\log\frac1\eps+\log|V|
\right)\right)
\end{gather*}
(the constant in O-notation does not depend on $t,\eps$).
\end{lemma}
\begin{proof}
Assume that the first two inequalities are false.
Let
$$
k=\max\{K(z|u,G),K(z|v,G)\},\qquad m=K(z|G).
$$
We have $\eps<2^{-kt-1}$.
First estimate $m$ very roughly:
$$
m=K(z|G)\le K(z|u,G) +2K(u|G)+O(1)\le\frac 1t \log\frac1\eps+2\log |V|+O(1).
$$
Thus the complexities of all $u,v,z$ conditional to $G$
are polynomial in $\log|V|,\log\frac1\eps$.
In what follows we omit additive
$O(\log(\log|V|+\log\frac1\eps))$ terms.
We have
$$
K(u|z,G)=K(u|G)+K(z|u,G)-K(z|G)\le \log|V|+k-m.
$$
The same bound is valid for $K(v|z,G)$.

Let $U$ be the  set of  all $x\in V$ such that
$K(x|z,G)\le K(u|z,G),K(v|z,G) $. Then
$|U|\le |V|2^{k-m}$ (up to a factor polynomial in
$\log |V|,\log\frac1\eps$). By Lemma~\ref{lem4} we obtain
the following upper bound for the number $E_U$
of edges in $U$:
$$
|E_U|\le
d|U|\left(  \frac{|U|}{|V|}  +\eps
\right)^{1/t}.
$$
As $u,v\in U$ and $U$ (hence $E_U$) is enumerable
given $z,G,K(u|z,G),K(v|z,G)$, we have
\begin{align*}
\log(|V|d/2)=&\log|E|\le K(u,v|G)\le \log|E_U|+K(z|G)\\
\le& \log d+\log |U|+\log \left(  \frac{|U|}{|V|}  +\eps
\right)^{1/t}+m\\
\le& \log d+\log |V|+(k-m)+(1/t)\log\left(  2^{k-m} +\eps
\right)+m.
\end{align*}
Therefore, we have
$$
2^{-kt}\le 2^{k-m}+\eps
$$
(up to a factor polynomial in
$\log|V|,\log(1/\eps)$).
By our assumption $\eps$ is less than half of $2^{-kt}$, hence
$$
-kt\le k-m\Rightarrow m\le (t+1)k.\qed
$$
\renewcommand{\qed}{}
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The assertion of the theorem is a direct corollary of the proven lemmas.


\newcommand{\seq}{\text{\textit{Seq}}}
\newcommand{\sub}{\text{\textit{Sub}}}

Thus it remains to prove Claims 1 and 3.

Proof of Claim~1.
Let $N$ stand for the number of elements in the field $F_n$
(recall that $N\approx  2^n$).
Let $u$ be an $i$-di\-men\-sional subspace
of the $m$-di\-men\-sional space over $F_n$.
The number of  vectors
that do not belong
to $u$ is equal  to $N^m-N^i=N^m(1+O(1/N))$
(provided  $i<m$). Assume that $i+l\le m$.
The number $\seq^{mi}_{l}$
of sequences of vectors $e_1,\dots,e_l$ such that
the system
$$
(\text{a basis of $u$})\cup\{e_1,\dots,e_l\}
$$
is independent
is equal to $N^{ml}(1+O(1/N))$ (the  constant in $O$-notation
depends on  $l$).

Let $\sub^m_l$ stand for the number of $l$-di\-men\-sional subspaces of the
$m$-di\-men\-sional space. We have
$$
\sub^{m}_{l}=\frac{\seq^{m0}_{l}}{\seq^{l0}_{l}}
=\frac{ N^{ml}(1+O(1/N))}{N^{l^2}(1+O(1/N))}= N^{(m-l)l}(1+O(1/N)).
$$

Let $a$ be a $k$-di\-men\-sional subspace. The
number of $l$-di\-men\-sional
subspaces $b$ such that $\dim (a\cap b)=s$ is equal to
the number of $s$-di\-men\-sional subspaces $c$ of $a$
multiplied by the number of $l$-di\-men\-sional subspaces
$b$ whose intersection with $a$ is equal to a fixed
$s$-di\-men\-sional subspace $c$:
$$
\sub^{k}_{s}\frac{\seq^{mk}_{l-s}}{\seq^{ls}_{l-s}}.
$$

Hence the probability that a random
$l$-di\-men\-sional subspace $b$ satisfies the equality
$\dim (a\cap b)=s$ is equal to
\begin{align*}
&\frac{\sub^{k}_{s}\seq^{mk}_{l-s}}{\seq^{ls}_{l-s}\sub^{m}_{l}}
=\frac{N^{(k-s)s}N^{m(l-s)}}{N^{l(l-s)}N^{(m-l)l}}(1+O(1/N))\\
&=N^{(k+l-m-s)s}(1+O(1/N)).
\end{align*}
This probability is exponentially (in $n$) close to 1 when
either $s=0$ or
$s=k+l-m$.

Proof of Claim~3.
Assume that
$$
\dim(a\cap b)=r_1,\ \dim(a^{\bot}\cap b)=r_2,\
\dim(a\cap a^\bot\cap b)=r_3,\ \dim((a\cup a^\bot)\cap b)=r_4.
$$
Then
 $$
 \begin{array}{rcl}
 \dim(a\cap b^\bot)&=&r_2,\\
 \dim(a^\bot\cap b^\bot)&=&m-2k+r_1,\\
 \dim(a\cap a^\bot\cap b^\bot)&=&r_0-k+r_4,\\
 \dim((a\cup a^\bot)\cap b^\bot)&=&m-r_0-k+r_3.
 \end{array}
 $$
Thus the claim is  a particular case of the
following general fact.
\begin{quote}
Let $\alpha$, $\beta$, $\gamma$ be subspaces of a linear
space $L$ over a finite field $F$ such that $\alpha\cup\beta\subseteq\gamma$.
Then the probability
for a random $k$-di\-men\-sional subspace $\delta$ of $L$ of satisfying
the equalities $\dim (\delta\cap\alpha)=q_1$, $\dim (\delta\cap\beta)=q_2$,
$\dim (\delta\cap\alpha\cap\beta)=q_3$, $\dim (\delta\cap\gamma)=q_4$,
depends only on
$k,q_1,q_2,q_3,q_4,\dim\alpha,\dim\beta,\dim(\alpha\cap\beta),\dim\gamma,
\dim L,|F|$.
\end{quote}
(We apply this  assertion  to $\alpha=a\cap b^\bot$,
$\beta=a^\bot\cap b^\bot$,
$\gamma=(a\cup a^\bot)\cap b^\bot$,
$L=b^\bot$.)

Proof. Let $\alpha',\beta',\gamma'$  be a
triple of linear subspaces such that
$\alpha'\cup\beta'\subseteq\gamma'$ and
$\dim\alpha'=\dim\alpha$, $\dim\beta'=\dim\beta$,
$\dim(\alpha'\cap\beta')=\dim(\alpha\cap\beta)$,
$\dim\gamma'=\dim\gamma$.
Then there is an automorphism $\phi$ of  $L$ such that
$\phi\alpha=\alpha'$,
$\phi\beta=\beta'$,
$\phi\gamma=\gamma'$.
Indeed, construct five systems of vectors
$A_1,A_2,\dots, A_5$
as follows.
The first system, $A_1$ is a basis of $\alpha\cap\beta$.
The second system, $A_2$ completes $A_1$ to
the basis of $\alpha$.
The third system, $A_3$ completes $A_1$
to the basis of $\beta$. It is easy to see that
$A_1\cup A_2\cup A_3$ is a basis
of $\alpha\cup\beta$. The forth system, $A_4$ completes
this union to the basis of $\gamma$. The fifth system, $A_5$
completes the union of the four defined systems
to the basis of $L$.
In a similar way construct five systems
$A_1',A_2',\dots, A_5'$
for
$\alpha',\beta',\gamma'$. The assumptions
on dimensions of subspaces guarantee that
$A_i$ and $A_i'$
have the same number of elements.
The automorphism $\phi$ is generated by one to one
correspondence between $A_i$ and $A_i'$.

Thus we have
\begin{align*}
&\Prob[
\dim (\delta\cap\alpha)=q_1,\ \dim (\delta\cap\beta)=q_2,\\
&\qquad\qquad  \dim (\delta\cap\alpha\cap\beta)=q_3,\ \dim (\delta\cap\gamma)=q_4
]\\
&=\Prob[
\dim \phi(\delta\cap\alpha)=q_1,\ \dim \phi(\delta\cap\beta)=q_2,&\\
&\qquad\qquad\dim \phi(\delta\cap\alpha\cap\beta)=q_3,
\ \dim \phi(\delta\cap\gamma)=q_4
]\\
&=\Prob[
\dim (\phi\delta\cap\phi\alpha)=q_1,\ \dim (\phi\delta\cap\phi\beta)=q_2,\\
&\qquad\qquad\dim (\phi\delta\cap\phi\alpha\cap\phi\beta)=q_3,
\ \dim (\phi\delta\cap\phi\gamma)=q_4
]\\
&=\Prob[
\dim (\delta\cap\alpha')=q_1,\ \dim (\delta\cap\beta')=q_2,\\
&\qquad\qquad\dim (\delta\cap\alpha'\cap\beta')=q_3,
\ \dim (\delta\cap\gamma')=q_4
].\qed
\end{align*}
\renewcommand{\qed}{}

\end{proof}



\section{More about common information}\label{geometric-description}

Let us reformulate our informal definition of common information.
We say that strings $x$ and $y$ have $u$-bit common
information $z$ if $K(z)\le u$, $K(x|z)\le K(x)-u$, and
$K(y|z)\le K(y)-u$. (It is easy to see that all three
inequalities in fact are equalities in that case.)

The question whether such $z$ exists
is a special case of a more general question: we may
ask for given $u,v,w$ whether there is a string $z$ such that
$K(z)\le u$, $K(x|z)\le v$, and $K(y|z)\le w$. The set of all
triples $(u,v,w)$ for which such a $z$ exists could
be considered as ``complexity profile'' of the pair $x,y$.

Technically speaking, we should consider sequences of strings
instead of individual strings. Let
$\boldsymbol{x}=x_1,x_2,\dots$ and
$\boldsymbol{y}=y_1,y_2,\dots$ be two sequences such that $|x_n|
= O(n)$ and $|y_n|=O(n)$. (Only sequences satisfying these
conditions will be considered in this section.) A triple of
reals $(u,v,w)$ is called
$\boldsymbol{x},\boldsymbol{y}$-\emph{admissible}, if there
exists a sequence $\boldsymbol{z}=z_1,z_2,\dots$ and a constant $c$
such that
\begin{equation}\label{p4}
K(z_n)\le un+c\log n,\ K(x_n|z_n)\le vn+c\log n,\
K(y_n|z_n)\le wn+c\log n
\end{equation}
for all $n$.
A triple of
reals $(u,v,w)$ is called
$\boldsymbol{x},\boldsymbol{y}$-\emph{non-admissible}, if
for any $c$ and for all sufficiently large $n$ there
is no $z_n$ satisfying~\textup{(\ref{p4})} (we consider
triples of non-negative reals only).
Note that no triple can be
$\boldsymbol{x},\boldsymbol{y}$-admissible
and $\boldsymbol{x},\boldsymbol{y}$-non-admissible
simultaneously. But it may happen that a triple falls in
neither of these two categories (below we shall give such an example).
%This means that the properties of $x_n,y_n$ we are interested in
%depend on $n$.

The set of all $\boldsymbol{x},\boldsymbol{y}$-admissible
triples is denoted by $M_{\boldsymbol{x},\boldsymbol{y}}^+$. The
larger  $M_{\boldsymbol{x},\boldsymbol{y}}^+$ is, the more
information $\boldsymbol{x}$ and $\boldsymbol{y}$ share.
The set of all $\boldsymbol{x},\boldsymbol{y}$-non-admissible
triples is denoted by $M_{\boldsymbol{x},\boldsymbol{y}}^-$.

Here is a trivial example: assume that
$x_n$ is a random string of length $n$ and $y_n=x_n$. Then
        $$
M_{\boldsymbol{x},\boldsymbol{y}}^+=\{(u,v,w)\mid u+v
\ge1,\ u+w\ge1\},\qquad
M_{\boldsymbol{x},\boldsymbol{y}}^-=\R^3\setminus
M_{\boldsymbol{x},\boldsymbol{y}}^+.
        $$
If $x_n,y_n$ are random independent strings of length $n$, then
$M_{\boldsymbol{x},\boldsymbol{y}}^+$ is much smaller:
\begin{align*}
M_{\boldsymbol{x},\boldsymbol{y}}^+&=\{(u,v,w)\mid
u+v \ge1,\ u+w\ge1,\ u+v+w\ge2\},\\
M_{\boldsymbol{x},\boldsymbol{y}}^-&=\R^3\setminus
M_{\boldsymbol{x},\boldsymbol{y}}^+.
\end{align*}
If $x_n,y_n$ are random strings
of length $n$ such that
$x_n=y_n$ for even $n$ and $x_n,y_n$ are independent
for odd $n$ then
\begin{align*}
M_{\boldsymbol{x},\boldsymbol{y}}^+&=\{(u,v,w)\mid
u+v \ge1,\ u+w\ge1,\ u+v+w\ge2\},\\
M_{\boldsymbol{x},\boldsymbol{y}}^-&=\{(u,v,w)\mid
u+v<1\text{ or }u+w<1\}
\end{align*}
(so in this example $M_{\bs x,\bs y}^+$ and $M_{\bs x,\bs y}^-$
are not complementary).
As we shall see, the values of $K(x_n)$, $K(y_n)$ and
$K(\langle x_n,y_n\rangle)$ do not determine the sets
$M_{\boldsymbol{x},\boldsymbol{y}}^+$,
$M_{\boldsymbol{x},\boldsymbol{y}}^-$ completely.

For simplicity we restrict ourselves to one special case: we
assume that
       \begin{equation}\label{special-case}
\begin{split}
K(x_n)=2n+O(\log n),\
K(y_n)=2n+O(\log n),\\
K(\langle x_n,y_n\rangle)=3n+O(\log n).
\end{split}
        \end{equation}

Consider the following two sets of triples. The first one, called
$M_{\mathrm{min}}^-$,  contains all the triples
satisfying \emph{at least one} of the
inequalities
    \begin{equation}\label{m-min}
u+v+w<3,\ u+v<2,\ u+w<2.
     \end{equation}
The second one, called $M_{\mathrm{min}}^+$, contains all the triples
outside $M_{\mathrm{min}}^-$ satisfying \emph{at least one} of the
inequalities
        \begin{equation}\label{m+min}
u+v+w\ge4,\ u+v\ge3,\ u+w\ge3.
        \end{equation}
%
        \begin{theorem}\label{thfine}
\textup{(a)} For any sequences $\boldsymbol{x},\boldsymbol{y}$
satisfying~\textup{(\ref{special-case})}
        $$
M_{\mathrm{min}}^+ \subseteq M_{\boldsymbol{x},\boldsymbol{y}}^+,\qquad
M_{\mathrm{min}}^- \subseteq M_{\boldsymbol{x},\boldsymbol{y}}^-.
        $$

\textup{(b)} There exist sequences
$\boldsymbol{x},\boldsymbol{y}$
satisfying~\textup{(\ref{special-case})}
such that $M_{\boldsymbol{x},\boldsymbol{y}}^+ =
\R^3\setminus M_{\mathrm{min}}^-$ (hence
 $M_{\boldsymbol{x},\boldsymbol{y}}^- = M_{\mathrm{min}}^-$).

\textup{(c)} There exist sequences
$\boldsymbol{x},\boldsymbol{y}$ satisfying~\textup{(\ref{special-case})}
such that
        $
M_{\boldsymbol{x},\boldsymbol{y}}^- =\R^3\setminus  M_{\mathrm{min}}^+
        $
(hence
 $M_{\boldsymbol{x},\boldsymbol{y}}^+ = M_{\mathrm{min}}^+$).

        %
        \end{theorem}

\begin{proof}

(a)
Using the inequalities
$$
K(\langle x_n,y_n\rangle)\le K(z_n)+K(x_n|z_n)+K(y_n|z_n)+O(\log n)
$$ and
$K(x_n)\le K(z_n)+K(x_n|z_n)+O(\log n)$ we see  that
inequalities~(\ref{p4}) and~\textup{(\ref{special-case})} imply
\begin{eqnarray*}
3n+O(\log n)&\le& un+vn+wn+O(\log n),\\
 2n+O(\log n)&\le& un+vn+O(\log n),\\
2n+O(\log n)&\le& un+wn+O(\log n).
\end{eqnarray*}
Hence if at least one of the inequalities
\begin{equation}\label{p3}
3\le u+v+w,\ 2\le u+v,\ 2\le u+w
\end{equation}
is not fulfilled the triple $(u,v,w)$ is
$\bs x,\bs y$-non-admissible.
Thus, for every $\bs x,\bs y$ the set
$M_{\boldsymbol{x},\boldsymbol{y}}^-$
includes  the set
$M_{\min}^-$.

Let us prove that $M_{\min}^ +\subseteq M_{\boldsymbol{x},\boldsymbol{y}}$.
Without loss of generality assume that
$|x_n|=2n+\olog$, $|y_n|=2n+\olog$ (otherwise replace $x_n$ and $y_n$
by minimum length programs to compute them).
Let $(u,v,w)$ be in $M_{\min}^+$. Then the triple
$(u,v,w)$  satisfies all the
the inequalities~(\ref{p3}) and  at least one of the
inequalities~(\ref{m+min}).
So consider three cases.

1) $u+v+w\ge4$. If $v,w\le2$ let $z$ be the concatenation
of the first $2n-vn$ bits of $x$
and the first $2n-wn$ bits of $y$
(we omit logarithmic terms).
Since $u+v+w\ge4$, we have
$|z|=2n-vn+2n-wn\le un$. To obtain $x$ given
$z$ we need the remaining $vn$ bits of $x$ and the numbers
$n,\lceil vn\rceil,\lceil wn\rceil$, so
$K(x|z)\le vn$. Analogously, $K(y|z)\le wn$.

Otherwise, if say $v>2$, let $z$ consist of the first $un$
bits of $y$ (and $z=y$ if $2<u$).
Then $K(y|z)\le 2n-un\le wn$
(if $u\le 2$, and $K(y|z)=0\le wn$ otherwise). And
$K(x|z)\le K(x)\le 2n\le vn$.

2) $u+v\ge 3$. If $u\le2$
let $z$ consist of the first $un$ bits of $y$. To find $x$ given
$z$ it suffices to know the remaining $2n-un$ bits of $y$
and the minimum program to compute $x$ given $y$
(having $n$ bits).
So to find $x$ given $z$
it suffices to have $2n-un+n\le vn$ extra bits.
And $K(y|z)\le 2n-un\le wn$.

Otherwise (if $u>2$) let $z$ be the concatenation of $y$
and the first $un-2n$ bits of minimum length program $p$
to compute $x$ given $y$ (and $z=yp$ if $un-2n>n$).
To obtain $x$ given $z$ it suffices to
have the remaining $n-(un-2n)\le vn$
bits of $p$.

3) $u+w\ge 3$. Similar to the previous case.

(b)
Let $x_n=pq$, $y_n=pr$,
where $p,q,r$ are random independent strings of length
$n$. We have to prove that any triple satisfying
the inequalities~(\ref{p3}) is  ${\bs x},{\bs y}$-admissible.

If $u\le1$  let $z$ consist of the first $un$ bits of $p$.
To find $x$ [$y$] given $z$ it suffices to have the remaining
$n-un$ bits of $p$ and the whole string
$q$ [$r$]. So the total number of bits
is  $n-un+n\le vn$
[$n-un+n\le wn$].

If $u>1$ and  $v\ge1$ let $z$ consist of
the first $un$ bits of  $y$.
To find $x$ given $z$ it suffices to have $q$ ($n$ bits).
To find $y$ given $z$ it suffices to have the remaining
$2n-un$ bits of $y$ and $2n-un\le wn$.

If $u>1$ and  $w\ge1$ use the same argument.

If $u>1$ and  $v,w<1$ let $z$ be the concatenation
of $p$,  the first $n-vn$ bits of $q$ and the first $n-wn$ bits
of $r$. The length of $z$ is $n+n-vn+n-wn\le un$.
To find $x$ [$y$] given $z$ it suffices to have the remaining
$vn$ [$wn$] bits of $q$ [$r$].

The proven  fact agrees with our intuition that these
$\bs x$ and $\bs y$ have as much common information as possible
(under restriction (\ref{special-case})).

(c)
    This is the most interesting part of the theorem; the proof
    uses methods from~\cite{muchnik2}.

The set $\R^3\setminus M_{\text{min}}^+$
consists $M_{\text{min}}^-$ and of those triples satisfying the  inequalities
\begin{equation}\label{eqstrict}
u+v+w<4,\ u+v<3,\ u+w<3.
\end{equation}
By item (a) we have $M_{\text{min}}^-\subseteq M_{\bs x,\bs y}^-$.
Therefore it suffices to prove
that any triple satisfying~\eqref{eqstrict}
belongs to $M_{\bs x,\bs y}^-$.
Let $(u,v,w)$
satisfy~\eqref{eqstrict}.
Note that all three inequalities are  strict.
Assume that for infinitely many $n$ there is $z_n$
for which inequalities~(\ref{p4}) are true.
Then for infinitely many $n$,
\begin{eqnarray}
K(z_n)+K(x_n|z_n)+K(y_n|z_n)&<&4n\label{equ1}\\
K(z_n)+K(x_n|z_n)&<&3n\label{eq2}\\
K(z_n)+K(y_n|z_n)&<&3n.\label{eq3}
\end{eqnarray}
Therefore it suffices to prove
the following lemma.
\begin{lemma}\label{lemma11}
There are ${\bs x},{\bs y}$ satisfying~(\ref{special-case})
such that for all but finitely many $n$
there is no $z_n$ satisfying the
inequalities~\eqref{equ1},
\eqref{eq2} and~\eqref{eq3}.
\end{lemma}

\begin{proof}
Let us fix a natural number $n$. As usually we will omit the
subscript $n$ in $x_n$, $y_n$, etc.

We choose the pair $(x,y)$ from the set $U$ consisting
of pairs of strings of  length $2n+2\log n$.
So $|U|=2^{4n}n^{4}$.
First remove from $U$ all
pairs satisfying at least one of the following requirements:
\begin{itemize}
\item
$K(x)<2n$,
\item $K(y)<2n$,
\item
$K(\langle x,y\rangle)<3n$,
\item there is $z$ satisfying
the inequalities~(\ref{equ1}), (\ref{eq2}), and~(\ref{eq3}).
\end{itemize}
Let us count the number of pairs removed from $U$ to show that
$U$ does not become empty. Indeed,
less than $2^{2n}2^{2n}n^2$ pairs have been
removed for the first reason (and the same amount for the second one),
less than $2^{3n}$ for the third  reason and less than
$(4n)^32^{4n}$ for the fourth reason
(for any $k,l,m$ there are  at
most $2^k2^l2^m$ pairs $x,y$ such that there is $z$ with $K(z)=k$,
$K(x|z)=l$, $K(y|z)=m$; and the number of triples $k,l,m$ satisfying
the inequality $k+l+m<4n$ is less than $(4n)^3$).
Thus the total number of removed pairs is less than
$$
2\times2^{4n}n^2+2^{3n}+(4n)^32^{4n}<2^{4n}n^{4}
$$
(for sufficiently large $n$).

Let $(x,y)$ be the least  pair remaining in $U$
(with respect to any fixed well founded order).
Then $K(x)=2n+\olog$, $K(y)=2n+\olog$,
$K(\pair{x,y})\ge3n$ and there is no $z$ satisfying
inequalities (\ref{equ1}), \eqref{eq2} and \eqref{eq3}.
Thus, to prove the lemma it suffices to show that
$K(\langle x,y\rangle)\le3n+\olog$.

Let
$W_{k,l}$ stand for the set consisting
of all pairs $(a,b)$ such that $K(a)\le k$ and $K(b|a)\le l$.
%of all quadruples $(p,q,z,x')$ such that $|p|=k$, $|q|=l$,
%$U(p,\Lambda)=z$ and $U(z,q)=x'$
%(recall that $U$ is the optimal
%computable function and
%$\Lambda$ denotes the empty string).
To identify $(x,y)$ it suffices to know
$n$, the set $\{x'\mid K(x')<2n\}$,
the set $\{(x',y')\mid K(\pair{x',y'})<3n\}$, and
the sets $W_{k,l}$ for all $k+l<3n$.
The elements of these  sets
can be enumerated given $n$,
therefore to get the lists of all these sets
it suffices to know $n$ and the number
$$
m=|\{x'\mid K(x')<2n\}|+|\{(x',y')\mid K(\pair{x',y'})<3n\}|
+\sum_{k+l<3n}|W_{k,l}|
$$
(given $n$ we enumerate all these sets until
$m$ elements have been enumerated; if a
pair belongs to several sets we
count it separately for each set).
As
$$
m<2^{2n}+2^{3n}+\sum_{k+l<3n}2^{k+l+2}<2^{3n+1}+\sum_{j<3n}(j+1)2^{j+2}
\le(3n)^22^{3n+2},
$$
we get
$$
K(\langle x,y\rangle)\le\log m+\olog\le 3n+\olog.\qed
$$
\renewcommand{\qed}{}
\end{proof}
\renewcommand{\qed}{}
\end{proof}

The proof of Theorem~\ref{thfine}\textup{(c)} is
non-constructive, it gives no ``example'' of the pair $({\bs
x},{\bs y})$ with
$M_{\boldsymbol{x},\boldsymbol{y}}^-=\R^3\setminus M_{\min}^+$.
An example would be a computable sequence of finite non-empty
sets $A_n$ of low complexity (say $O(\log n)$) such that any
random pair $(x_n,y_n)$ in $A_n$ satisfies
Theorem~\ref{thfine}\textup{(c)}. Such an example was recently
constructed by An.~A.~Muchnik (unpublished).


In Section~\ref{common-mutual} we presented several examples of
sequences $\boldsymbol{x},\boldsymbol{y}$ whose common
information is less than mutual information. It would be
interesting to find the complexity profile for these examples.
Unfortunately, we know only few things. We present here
known facts about random orthogonal lines in three-di\-men\-sional
space. In the rest of the  paper let
$\boldsymbol{x},\boldsymbol{y}$ be sequences
mentioned in Theorem~\ref{random-orthogonal-lines}.
Using  Lemma~\ref{lemmaa} we obtain the following lower bound
for $M_{\boldsymbol{x},\boldsymbol{y}}^-$.

       \begin{theorem}\label{random-orthogonal-lines-bound}
The set
$ M_{\boldsymbol{x},\boldsymbol{y}}^-$ contains any triple
$(u,v,w)$ such that %\linebreak
$u+v/2+\max\{w,v/2\}<3\ $ or
$\ u+w/2+\max\{v,w/2\}<3$.
       \end{theorem}
Note that there are such triples outside
$M_{\mathrm{min}}^-$ (for instance, the triple
$(1.1,1.1,1.1)$).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{proof}
Assume that
$u+w/2+\max\{w/2,v\}<3$ (the other case is entirely similar).
Assume that for some $c$ for infinitely many $n$ there
is $z_n$ such that (\ref{p4}) holds. Fix any such $n$
(in the sequel we omit subscript $n$ in $x_n,y_n,z_n$).
We use Lemma~\ref{lemmaa} for the same
bipartite graph as in Theorem~\ref{random-orthogonal-lines}:
left nodes are  lines having complexity at most
$K(x|z)$ conditional to $z$,
right nodes are  lines having complexity at most
$K(y|z)$ conditional to $z$, and edges connect orthogonal lines.
By Lemma~\ref{lemmaa} we have
$$
|E|\le 2\sqrt{l}\max\{\sqrt{l},k\}.
$$
Therefore (we omit logarithmic terms)
\begin{align*}
3n&\le K(\langle x,y\rangle)\le
\log |E|+K(z)\le (1/2)\log l+\log\max\{\sqrt{l},k\}+K(z)\\
&\le wn/2+\max\{w/2,v\}n+un.
\end{align*}
As this is true for infinitely many $n$ (up to $\olog$ term)
we get
$3\le u+w/2+\max\{w/2,v\}$, a contradiction.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A natural question is whether the inclusion
$M_{\mathrm{min}}^+\subseteq M_{\boldsymbol x,\boldsymbol y}^+$ is
also strict. The answer to this question may depend on the choice of
the field $F_n$. Note that all proven
theorems on $\bs x,\bs y$ are true for any choice of
$F_n$.
%(see Theorem~\ref{random-orthogonal-lines}).
However, it turns
out that if the field $F_n$ has size $p^2$, where $p$ is an integer
then the set $M_{\boldsymbol x,\boldsymbol y}^+$ contains the triple
$(1.5,1,1)$ that is outside $M_{\mathrm{min}}^+$. But we don't know whether
this is true for other fields.
Recall that we gave similar examples for $\bs x,\bs y$ from
Theorem~\ref{more-examples}. To obtain such examples we used arguments from
linear
algebra. Such arguments can provide only triples $(u,v,w)$ whose
coefficients are dimensions of certain linear spaces. But the
first component of the triple $(1.5,1,1)$ is not an integer so now we
cannot use linear-algebraic arguments directly. To overcome this
difficulty we ``double'' the dimension by regarding three-di\-men\-sional
linear space over $F_n$ as a six-di\-men\-sional linear space over the
subfield $G_n$ of $F_n$ of size $p$. Now 1.5 may be
obtained as dimension 3 of a space over $G_n$.

\begin{theorem}
        %
Assume that all fields $F_n$ are of size $p_n^2$ where $p_n$ are
integers. Then $M_{\boldsymbol x,\boldsymbol y}^+$
contains the triple $(1.5,1,1)$.
        %
\end{theorem}

Note that together with previous theorem this implies
that in the case $|F_n|=p_n^2$
the triple $(1.5,1,1)$  is  on the border line between
$M_{\boldsymbol x,\boldsymbol y}^-$ and
$M_{\boldsymbol x,\boldsymbol y}^+$.


\begin{proof}
        %
We shall use the following representation of the example $x,y$
of Theorem~\ref{random-orthogonal-lines}: $x=(a,b)$,
$y=(c,ac+b)$ where $(a,b,c)$ is a random triple of elements of
$F_n$. The pair $x=(a,b)$ will be called a line and $y=(c,ac+b)$
a point (on that line). (See the remark after
Theorem~\ref{random-orthogonal-lines}.)

What do we gain assuming that
$|F_n|=p_n^2$ (for all $n$)? In this case the field  $F=F_n$ has a subfield
of $p=p_n$ elements, denoted by $G$.
Let $\alpha\in F$ be
a primitive element of $F$ over $G$. Thus
any element in $F$ can be represented in the form
$h+s\alpha$ for some $h,s\in G$.
%We can choose $\alpha$ in such a way
%that, moreover,
%any element in $F$ can be represented in the form
%$t+s\alpha^2$ for some $t,s\in G$. Why?
%The multiplicative group of the field $F$ is cyclic,
%%(see \cite[page 184]{lang}),
%therefore the square of
%any generator of this group does not belong to $G$. Let us take as $\alpha$
%any such generator.
%Then $\alpha^2$ is also a primitive element.

We construct  a family of $p^3$ disjoint $p^3$-element
sets of pairs
$\langle$a line, a point on that line$\rangle$, whose union covers the set
$S$ of all $p^6$
such pairs. Each set will involve
$p^2$ different points  and $p^2$ different lines,
each of those $p^2$ points will belong to $p$ of those $p^2$ lines,
and conversely
each of those $p^2$ lines will have  $p$ of those $p^2$ points.
To construct such family represent
each pair $\pair{x,y}\in S$ in the form
$$
x=(f+r\alpha,h+s\alpha),\quad
y=(g+t\alpha,fg+h+(ft+gr+s)\alpha+rt\alpha^2),
$$
where $f,g,h,r,t,s\in G$.
Fixing $r,t,s$ we obtain a set  $S_{rts}$
of $p^3$ pairs from $S$ having $p^2$ lines.
Unfortunately $S_{rts}$ has about $p^3$ points.
Let is try to reduce the number of points in each
$S_{rts}$: the substitution $s\mapsto s-ft$
changes the above representation of a pair
$\pair{x,y}\in S$ to
$$
x= (f+r\alpha,h+(s-ft)\alpha),\quad
y=(g+t\alpha,fg+h+(gr+s)\alpha+rt\alpha^2).
$$
%Any pair $(x,y)\in S$ belongs to some $S_{rts}$
%and each $S_{rts}$ has $p^2$ lines (each line in
%$S_{rts}$ is identified by pair $(f,h)$)
%, but again every
%$S_{rts}$ has about $p^3$ points. Now comes the crucial
%trick: replace in both representations
%$h+s\alpha$ by $h+s\alpha^2$ (recall that $\alpha^2$
%is a primitive element as well).
%The second representation
%becomes
%$$
%x=(f+r\alpha,h+s\alpha^2-gr\alpha),\quad
%y=(g+t\alpha,fg+h+ft\alpha+(rt+s)\alpha^2).
%$$
Now, any line in $S_{rts}$ is identified by pair $(f,h)$ thus there
are $p^2$ different lines in $S_{rts}$; any point in $S_{rts}$ is
identified by pair $(g,fg+h)$ thus there are $p^2$ different points
in $S_{rts}$.

Let us finish  the proof. We take as $z$ the set from
our family which contains the pair $\pair{x,y}$.
As the number of sets is $p^3$ we have $K(z)\le 3\log p+\olog=1.5n+\olog$.
As each set has  $p^2$ different lines and
$p^2$ different points, we have
$K(x|z),K(y|z)\le 2\log p+O(\log n)= n+O(\log n)$.
\end{proof}

%Remark.
%The proof of the theorem easily generalizes
%to any field $F$ of size $p^k$. Instead of
%$r$ we just take $k-1$-tuple $r_1,\dots,r_{k-1}$ of elements of
%$G$ and
%instead of $r\alpha$ the expression $r_1\alpha+\dots+r_{k-1}\alpha^{k-1}$,
%where $\alpha$ is a primitive element $F$ over $G$;
%$t,s$ are understood in a similar way.
%So we get that for such fields $M^+_{\bs x,\bs y}$
%has the point $(3(k-1)/k,2/k,2/k)$.

\medskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{9}

\bibitem{gacskorner}
P. G\'acs, J. K\"orner, Common information is far less than
mutual information, \emph{Problems of Control and Information
Theory}, \textbf{2} (1973), pp.~149--162.

\bibitem{germany-talk}
D. Hammer, A. Romashchenko, A. Shen, N. Vereshchagin.
Inequalities for Shannon entropies and Kolmogorov complexities.
In: \emph{Proc. Twelfth Annual IEEE Conference on Computational
Complexity}, Ulm, Germany, June 1997, pp. 13--23. (Final
version: \emph{Journal of Computer and System Sciences},
\textbf{60} (2000), p.~442--464.)

%\bibitem{lang}
%S. Lang. Algebra. Addison-Wesley, 1965.

\bibitem{li-vitanyi}
M. Li, P. Vit\'anyi. \textit{An introduction to Kolmogorov
complexity and its applications}. Second edition. Springer, 1997.

\bibitem{muchnik1}
An.A. Muchnik, On the extraction of common information of two
strings, \textit{Abstracts of talks at the First World Congress
of Bernoulli Society}, Moscow, Nauka, 1986, p.~453. (In
Russian.)

\bibitem{muchnik2}
An.A. Muchnik. On common information, \emph{Theoretical Computer
Science}, \textbf{207}~(1998), pp.~319--328.

\bibitem{rom}
A.E.~Romashchenko, Pary slov s nematerialisuemoi vzaimnoi
informatsiei (Pairs of strings with no extractable mutual
information, in Russian), \emph{Problemy peredachi informatsii}
(Problems of Information Transmission), \textbf{36}~(2000),
vyp.~1, p.~3--20.

\bibitem{shoenfield}
J.R. Shoenfield. \emph{Degrees of unsolvability}. North-Holland
Publishing Company, 1971.

\end{thebibliography}

\end{document}
