Some complexity results in the theory of normal numbers. (28th February 2022) - Airey, Dylan; Jackson, Steve; Mance, Bill
Abstract: Let 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 N(b) is Π ^0_3 -complete. We show that the set N^(b) of reals, which preserve N(b) under addition, is also Π ^0_3 -complete. We use the characterization of N^(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 N^(b) . We compute the exact descriptive complexity of other naturally occurring sets associated with noise. One of these is complete at the Π ^0_4 level. Finally, we get upper and lower bounds on the Hausdorff dimension of the level sets associated with the noise.