The descriptive complexity of the set of Poisson generic numbers

Abstract

Let $b\ge 2$ be an integer. We show that the set of real numbers that are Poisson generic in base $b$ is ${\mathbf{\Pi }}_3^0$-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base $b$ and not Poisson generic in base $b$ is complete for the class given by the differences between ${\mathbf{\Pi }}_3^0$ sets. We also show that the effective versions of these results hold in the effective Borel hierarchy.

15 pages