Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-089 | 30th July 2005 00:00

Dimensions of Copeland-Erdos Sequences

RSS-Feed

Abstract:

The base-$k$ {\em Copeland-Erd\"os sequence} given by an infinite
set $A$ of positive integers is the infinite
sequence $\CE_k(A)$ formed by concatenating the base-$k$
representations of the elements of $A$ in numerical
order. This paper concerns the following four
quantities.
\begin{enumerate}[$\bullet$]
\item
The {\em finite-state dimension} $\dimfs (\CE_k(A))$,
a finite-state version of classical Hausdorff dimension introduced in 2001.
\item
The {\em finite-state strong dimension} $\Dimfs(\CE_k(A))$,
a finite-state version of classical packing dimension
introduced in 2004. This is a dual of $\dimfs(\CE_k(A))$
satisfying $\Dimfs(\CE_k(A))$
$\geq \dimfs(\CE_k(A))$.
\item
The {\em zeta-dimension} $\Dimzeta(A)$, a kind of discrete
fractal dimension discovered many times over the
past few decades.
\item
The {\em lower zeta-dimension} $\dimzeta(A)$, a dual
of $\Dimzeta(A)$ satisfying $\dimzeta(A)\leq \Dimzeta(A)$.
\end{enumerate}
We prove the following.
\begin{enumerate}
\item
$\dimfs(\CE_k(A))\geq \dimzeta(A)$. This extends the 1946
proof by Copeland and Erd\"os that the sequence $\CE_k(\mathrm{PRIMES})$
is Borel normal.
\item
$\Dimfs(\CE_k(A))\geq \Dimzeta(A)$.
\item
These bounds are tight in the strong sense
that these four quantities can have (simultaneously)
any four values in $[0,1]$ satisfying the four
above-mentioned inequalities.
\end{enumerate}



ISSN 1433-8092 | Imprint