ECCC-Report TR05-089https://eccc.weizmann.ac.il/report/2005/089Comments and Revisions published for TR05-089en-usTue, 16 Aug 2005 23:18:05 +0300
Paper TR05-089
| Dimensions of Copeland-Erdos Sequences |
Xiaoyang Gu,
Jack H. Lutz,
Philippe Moser
https://eccc.weizmann.ac.il/report/2005/089The 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}
Tue, 16 Aug 2005 23:18:05 +0300https://eccc.weizmann.ac.il/report/2005/089