Dimensions of Copeland-Erdos Sequences
Xiaoyang Gu,
Jack H. Lutz, and
Philippe Moser
Abstract
The base-k Copeland-Erdös Sequence
given by an infinite set A of positive integers
is the infinite sequence CEk(A)
formed by concatenating the base-k representations
of the elements of A in numerical order. This paper
concerns the following four quantities.
-
The finite-state dimension dimFS
(CEk(A)),
a finite-state version of classical
Hausdorff dimension introduced in 2001.
-
The finite-state strong dimension
DimFS(CEk(A)),
a finite-state version of classical
packing dimension introduced in 2004.
This is a dual of dimFS(CEk(A))
satisfying
DimFS(CEk(A)) ≥
dimFS(CEk(A)).
-
The zeta-dimension Dimζ(A),
a kind of discrete fractal dimension discovered
many times over the past few decades.
-
The lower zeta-dimension
dimζ(A),
a dual of Dimζ(A)
satisfying dimζ(A)≤
Dimζ(A).
We prove the following.
-
dimFS(CEk(A)) ≥
dimζ(A). This extends
the 1946 proof by Copeland and Erdös that the sequence
CEk(PRIMES) is Borel normal.
-
DimFS(CEk(A))≥
Dimζ(A).
-
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.
Journal Version:
-
Information and Computation, 205(9): 1317-1333, 2007.
[ PS | PDF
| DOI ]
Conference Version:
-
Proceedings of the Twenty-Fifth Conference on Foundations
of Software Technology and Theoretical Computer Science
(Hyderabad, India, December 15-18, 2005), Springer-Verlag, 2005, pp. 250-260.
[ DOI
| BibTex ]
Last modified on October 4, 2007.