Some complexity results in the theory of normal numbers. (28th February 2022) - Airey, Dylan; Jackson, Steve; Mance, Bill
Abstract: Let $\mathcal {N}(b)$ be the set of real numbers that are normal to base b . A well-known result of Ki and Linton [19 ] is that $\mathcal {N}(b)$ is $\boldsymbol {Π }^0_3$ -complete. We show that the set ${\mathcal {N}}^\perp (b)$ of reals, which preserve $\mathcal {N}(b)$ under addition, is also $\boldsymbol {Π }^0_3$ -complete. We use the characterization of ${\mathcal {N}}^\perp (b), $ given by Rauzy, in terms of an entropy-like quantity called the noise . It follows from our results that no further characterization theorems could result in a still better bound on the complexity of ${\mathcal {N}}^\perp (b)$ . We compute the exact descriptive complexity of other naturally occurring sets associated with noise. One of these is complete at the $\boldsymbol {Π }^0_4$ level. Finally, we get upper and lower bounds on the Hausdorff dimension of the level sets associated with the noise.