TR05-089 Authors: Xiaoyang Gu, Jack H. Lutz, Philippe Moser

Publication: 16th August 2005 23:18

Downloads: 2316

Keywords:

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}