Dimensions of Points in Self-Similar Fractals
Authors:
- Jack H. LutzJLJack H. Lutz
- Elvira MayordomoEMElvira Mayordomo
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (3) , 1080-1112
Abstract
Self-similar fractals arise as the unique attractors of iterated function systems (IFSs) consisting of finitely many contracting similarities satisfying an open set condition. Each point x in such a fractal F arising from an IFS S is naturally regarded as the “outcome” of an infinite coding sequence T (which need not be unique) over the alphabet $\Sigma_k = \{0, \ldots, k-1\}$, where k is the number of contracting similarities in S. A classical theorem of Moran (1946) and Falconer (1989) states that the Hausdorff and packing dimensions of a self-similar fractal coincide with its similarity dimension, which depends only on the contraction ratios of the similarities. The theory of computing has recently been used to provide a meaningful notion of the dimensions of individual points in Euclidean space. In this paper, we use (and extend) this theory to analyze the dimensions of individual points in fractals that are computably self-similar, meaning that they are unique attractors of IFSs that are computable and satisfy the open set condition. Our main theorem states that, if $F \subseteq \mathbb{R}^n$ is any computably self-similar fractal and S is any IFS testifying to this fact, then the dimension identities $\operatorname{dim}(x) = \operatorname{sdim}(F) \operatorname{dim}^{\pi_S}(T)$ and $\operatorname{Dim}(x) = \operatorname{sdim}(F) \operatorname{Dim}^{\pi_S}(T)$ hold for all $x \in F$ and all coding sequences T for x. In these equations, $\operatorname{sdim}(F)$ denotes the similarity dimension of the fractal F; $\operatorname{dim}(x)$ and $\operatorname{Dim}(x)$ denote the dimension and strong dimension, respectively, of the point x in Euclidean space; and $\operatorname{dim}^{\pi_S}(T)$ and $\operatorname{Dim}^{\pi_S}(T)$ denote the dimension and strong dimension, respectively, of the coding sequence T relative to a probability measure $\pi_S$ that the IFS S induces on the alphabet $\Sigma_k$. The above-mentioned theorem of Moran and Falconer follows easily from our main theorem by relativization. Along the way to our main theorem, we develop the elements of the theory of constructive dimensions relative to general probability measures. The proof of our main theorem uses Kolmogorov complexity characterizations of these dimensions.
Keywords
This publication has 44 references indexed in Scilit:
- Effective Strong Dimension in Algorithmic Information and Computational ComplexitySIAM Journal on Computing, 2007
- Is the Mandelbrot set computable?Mathematical Logic Quarterly, 2004
- Finite-state dimensionTheoretical Computer Science, 2004
- Iterated Function Systems and Control LanguagesInformation and Computation, 2001
- Computability on subsets of Euclidean space I: closed and compact subsetsTheoretical Computer Science, 1999
- On hausdorff and topological dimensions of the kolmogorov complexity of the real lineJournal of Computer and System Sciences, 1994
- Dimensions and measures of quasi self-similar setsProceedings of the American Mathematical Society, 1989
- Hausdorff dimension in probability theoryIllinois Journal of Mathematics, 1960
- Computable functionalsFundamenta Mathematicae, 1955
- Dimension und u eres MaMathematische Annalen, 1918