2005/07/30 by Xiaoyang Gu, Gu, Xiaoyang, Jack H. Lutz +3
Computer Science · Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.CC #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0508001
19 pages
arxiv created 2005/07/30 · arxiv updated 2009/12/01
The base-k \em 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 \em finite-state dimension \dimfs (\CEk(A)), a finite-state version of classical Hausdorff dimension introduced in 2001. The \em 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 \em zeta-dimension \Dimzeta(A), a kind of discrete fractal dimension discovered many times over the past few decades. The \em lower zeta-dimension \dimzeta(A), a dual of \Dimzeta(A) satisfying \dimzeta(A)≤ \Dimzeta(A). We prove the following. \dimfs(\CEk(A))≥ \dimzeta(A). This extends the 1946 proof by Copeland and Erdös that the sequence \CEk(PRIMES) is Borel normal. \Dimfs(\CEk(A))≥ \Dimzeta(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.