On the complexity of the set of codings for self-similar sets and a variation on the construction of Champernowne

Abstract

Let $F=\{{\mathbf{p}}_0,\dots ,{\mathbf{p}}_n\}$ be a collection of points in ${\mathbb{R}}^d.$ The set $F$ naturally gives rise to a family of iterated function systems consisting of contractions of the form $$S_i(\mathbf{x})=\hat{I}»\mathbf{x}+(1-\hat{I}»){\mathbf{p}}_i,$$ where $\hat{I}»\in (0,1)$. Given $F$ and $\hat{I}»$ it is well known that there exists a unique non-empty compact set $X$ satisfying $X={\cup }_{i=0}^n{S}_i(X)$. For each $\mathbf{x}\in X$ there exists a sequence $\mathbf{a}\in \{0,\dots ,n{\}}^{\mathbb{N}}$ satisfying $$\mathbf{x}=\underset{j\to \infty }{\lim }(S_{a_1}\circ \cdots \circ S_{a_j})(0).$$ We call such a sequence a coding of $\mathbf{x}$. In this paper we prove that for any $F$ and $k\in \mathbb{N},$ there exists $\hat{I}{´}_k(F)>0$ such that if $\hat{I}»\in (1-\hat{I}{´}_k(F),1),$ then every point in the interior of $X$ has a coding which is $k$-simply normal. Similarly, we prove that there exists $\hat{I}{´}_{uni}(F)>0$ such that if $\hat{I}»\in (1-\hat{I}{´}_{uni}(F),1),$ then every point in the interior of $X$ has a coding containing all finite words. For some specific choices of $F$ we obtain lower bounds for $\hat{I}{´}_k(F)$ and $\hat{I}{´}_{uni}(F)$. We also prove some weaker statements that hold in the more general setting when the similarities in our iterated function systems exhibit different rates of contraction. Our proofs rely on a variation of a well known construction of a normal number due to Champernowne, and an approach introduced by Erdős and Komornik.