Some complexity results in the theory of normal numbers. (28th February 2022)

• Record Type: Journal Article
• Authors: Airey, Dylan; Jackson, Steve; Mance, Bill
• Is Part Of: Canadian journal of mathematics. Volume 74:Number 1(2022)
• Page Start: 170
• Page End: 198
• Publication Date: 2022-02-28
• Subjects: 03E15 -- 11K16 -- 11U99; normal numbers -- noise -- complexity; Mathematics -- Periodicals; Mathematics; Electronic journals; Periodicals; 510
• DOI: 10.4153/S0008414X20000723
• Languages: English
• ISSNs: 0008-414X

Abstract

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 {\Pi }^0_3$ -complete. We show that the set ${\mathcal {N}}^\perp (b)$ of reals, which preserve $\mathcal {N}(b)$ under addition, is also $\boldsymbol {\Pi }^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 {\Pi }^0_4$ level. Finally, we get upper and lower bounds on the Hausdorff dimension of the level sets associated with the noise.