Normal number

A different topic is treated in the article titled normal number (computing).

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 (the integer part) and the infinite sequence of digits after the point (the fractional part).

Suppose b is an integer greater than 1 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 a normal number (or sometimes an absolutely normal number) 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. This theorem established the existence of normal numbers, but Waclaw Sierpinski was the first to give an example of one.

The set of non-normal numbers is known to be uncountable; this follows easily by simply omitting one digit from each real number.

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.235711131719232931374143...

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 Verónica Becher and Santiago Figueira; 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 is normal (but all of them are strongly conjectured to be normal, because of some empirical evidence). Proofs are out of reach: it is not even known which digits occur infinitely often in the decimal expansions of those constants. David H. Bailey and Richard E. 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.
• 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.de:Normale Zahl

fr:Nombre normal sl:Normalno število pt:Número normal zh:正规数