|
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>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
-
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.
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 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: we don't even know 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
- Becher, V. and Figueira, S. "An example of a computable absolutely normal number", Theoretical Computer Science, 270, pp.
947-958, 2002. online version
- 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.
In computing, a normal number is one that is within the normal range of a floating-point format.
|