Event № 348
Let $b$ be a positive integer larger than or equal to two. A real number $x$ is called normal to base $b$, if in its base-$b$ expansion all finite blocks of digits occur with the expected frequency. Equivalently, $x$ is normal to base $b$ if the orbit of $x$ under the multiplication-by-$b$ map is uniformly distributed in the unit interval with respect to Lebesgue measure.While there are many explicit constructions of normal numbers to a single base it remains an open problem going back to Borel in 1909 to exhibit an easy example of an absolutely normal number (i.e. a real number that is normal to all integer bases simultaneously). In this talk I will explain algorithms by Sierpinski and Becher-Heiber-Slaman that produce absolutely normal numbers one digit after the other. I will show how these algorithms can be extended to give computable constructions of absolutely normal numbers that also have a normal continued fraction expansion, or are normal with respect to expansions to non-integer bases. Some ideas from ergodic theory will occur, but the proofs are based on large deviation theorems from probability theory for sums of dependent random variables. This allows to make certain constants implied by the Shannon-McMillan-Breimann theorem in special cases explicit so we can in fact avoid ergodic theory. If time permits, I will also say something about the trade-off between time-complexity and speed of convergence to normality for normal numbers.