Normal number

In mathematics, a normal number is, roughly speaking, a real number whose digits show a random distribution with all digits being equally likely. "Digits" refers to the finitely many digits before the point and the infinite sequence of digits after the point.

Suppose b>1 is an integer and x is a real number. Consider the digit sequence of x in the base b positional number system. If s is a finite string of digits in base b, we write N(s,n) for the number of times the string s occurs among the first n digits of x. The number x is called normal in base b if

<math>\lim_{n\to\infty} \frac{N(s,n)}{n} = \frac{1}{b^{k}}</math>

for every string s of length k. (In words: the probability of finding the string s among the digits of x is precisely the one expected if the digit sequence had been produced completely randomly.) The number x is called normal (or sometimes absolutely normal) if it is normal in every base b.

The concept was introduced by Émile Borel[?] in 1909. Using the Borel-Cantelli Lemma, he proved the normal number theorem: almost all real numbers are normal, in the sense that the set of non-normal numbers has Lebesgue measure zero. However, the set of non-normal numbers is uncountable.

Champernowne’s number

0.1234567891011121314151617...

containing as digit sequence the concatenation of all natural numbers is normal in base 10, but it is not normal in some other bases. The Copeland-Erdös constant

0.235711131719232931373941...

obtained by concatenating the prime numbers is also known to be normal in base 10.

No rational number is normal to any base, since the digit sequences of rational numbers are eventually periodic. Waclaw Sierpinski provided the first explicit construction of a normal number in 1917. A computable normal number was constructed by Becher and Figuera; an example of an uncomputable normal number is given by Chaitin's constant Ω.

It is extremely hard to prove the normality of numbers which were not explicitly constructed for the purpose. It is for instance unknown whether √2, π, ln(2) or e are normal (but all of them are strongly conjectured to be normal, because of some empirical evidence). Proofs are out of reach: we don't even know which digits occur infinitely often in the decimal expansions of those constants. Bailey and Crandall conjectured in 2001 that every irrational algebraic number is normal; while no counterexamples are known, not a single irrational algebraic number has ever been proven normal in any base.

References

• Bailey, D. H. and Crandall, R. E. "On the Random Character of Fundamental Constant Expansions." Experimental Mathematics 10, 175-190, 2001. online version (http://www.nersc.gov/~dhbailey/dhbpapers/baicran.pdf)
• Becher, V. and Figueira, S. "An example of a computable absolutely normal number", Theoretical Computer Science, 270, pp. 947-958, 2002. online version (http://www.dc.uba.ar/people/profesores/becher/absnor.pdf)
• Borel, E. "Les probabilités dénombrables et leurs applications arithmétiques." Rend. Circ. Mat. Palermo 27, 247-271, 1909.
• Champernowne, D. G. "The Construction of Decimals Normal in the Scale of Ten." Journal of the London Mathematical Society 8, 254-260, 1933.
• Sierpinski, W. "Démonstration élémentaire d'un théorème de M. Borel sur les nombres absolutment normaux et détermination effective d'un tel nombre." Bull. Soc. Math. France 45, 125-144, 1917.