\documentclass[12pt,draft]{article}
\usepackage{amsmath,amssymb,amsthm}


\pagestyle{empty}

\newcommand*{\vct}[1]{\mathbf{#1}}
\newcommand*{\Exp}[1]{\mathrm e^{#1}}

\newcommand{\rls}{\mathcal R}

\newcommand{\half}{\frac{1}{2}}
\newcommand{\lb}{\mathop{\rm lb}}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\phi}{\varphi}

\begin{document}

\begin{center}
\bf\large
On sharpening Kolmogorov bounds
that relative to random number generators and
complexity definition of randomness
\end{center}

\centerline{\large Alexey Semenov\hfil Andrej Muchnik}
\bigskip
\bigskip
\bigskip

\section*{Remark during proofreading}

In~[1], Kolmogorov defined the notion
of a table of $(n,\epsilon,p)$-random numbers
for $\rls_L$;
this notion differs from $(n,\epsilon)$-random
generator from Definition~1 in the point
that in ``long'' selections
obtained by rules from $\rls_L$,
the fraction of occurencies of one
is close not to $1/2$ but to $p$.
Kolmogorov denote by $l(n,\epsilon)$
the maximal number $l$ such that,
for each $p$, for each $L$,
and for each set of rules
of complexity less than $l$,
at least one table of
$(n,\epsilon,p)$-random numbers
of length $L$ exists.
It follows from~[1] that
for $\epsilon$ small enough
(e.\,g., $\epsilon < 1/20$)
and $n\ge \epsilon^{-4}$
$$
(2\lb\mathrm e)n\epsilon^2(1-\epsilon) < l(n,\epsilon) <
4n\epsilon(1+5\epsilon)\,.
$$
Kolmogorov set the problem of removing
the discrepancy in the power of $\epsilon$
in the lower and upper bounds on
$l(n,\epsilon)$.
Our Theorem~3 implies the inequality
$$
l(n,\epsilon) <
  (2\lb\mathrm e) n\epsilon^2 (1+2\epsilon)
$$
for $\epsilon$ small enough
and $n\ge \epsilon^{-4}$.
(To prove this, in Theorem~3 we assume
$L=\left\lfloor 2^{n\epsilon^3/2}\right\rfloor$.)
Thus, the upper bound on $l(n,\epsilon)$,
as the lower one, has the form
$(2\lb\mathrm e) n(\epsilon^2 + o(\epsilon^2))$.
\end{document}




