View source for Normal number

{{MSC|11K16}}

[[Category:Probabilistic number theory]]

A real number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675601.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675602.png" />, having the following property: For every natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675603.png" />, any given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675604.png" />-tuple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675605.png" /> consisting of the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675606.png" /> appears with asymptotic frequency <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675607.png" /> in the sequence

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675608.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

obtained from the expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n0675609.png" /> in an infinite fraction in base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756010.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756011.png" /></td> </tr></table>

In more detail, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756012.png" /> be a natural number and let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

be the infinite sequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756014.png" />-tuples corresponding to (1). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756015.png" /> denote the number of occurrences of the tuple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756016.png" /> among the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756017.png" /> tuples of (2). The number

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756018.png" /></td> </tr></table>

is said to be normal if for any number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756019.png" /> and any given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756020.png" />-tuple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756021.png" /> consisting of the symbols <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756022.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756023.png" /></td> </tr></table>

The concept of a normal number was introduced for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756024.png" /> by E. Borel (see [[#References|[1]]], [[#References|[2]]], p. 197). He called a real number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756025.png" /> weakly normal to the base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756027.png" /> if

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756028.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756029.png" /> is the number of occurrences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756031.png" />, among the first <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756032.png" /> terms of the sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756033.png" /> and normal if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756034.png" /> are weakly normal to the bases <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756035.png" />. He also showed that for a normal number

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756036.png" /></td> </tr></table>

for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756037.png" /> and any given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756038.png" />-tuple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756039.png" />. Later it was proved (see [[#References|[3]]], [[#References|[4]]], and also [[#References|[8]]]) that the last relation is equivalent to Borel's definition of a normal number.

A number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756040.png" /> is called absolutely normal if it is normal with respect to every base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756041.png" />. The existence of normal and absolutely-normal numbers was established by Borel on the basis of measure theory. The construction of normal numbers in an explicit form was first achieved in [[#References|[5]]]. Earlier (see [[#References|[6]]], [[#References|[7]]]) an effective procedure for constructing normal numbers was indicated. For other methods for constructing normal numbers and for connections between the concepts of normality and randomness see [[#References|[8]]].

[[Uniform distribution|Uniform distribution]] of the fractional parts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756043.png" /> on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756044.png" /> is equivalent to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756045.png" /> being normal.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> E. Borel, "Les probabilités dénombrables et leurs applications arithmétiques" ''Rend. Circ. Math. Palermo'' , '''27''' (1909) pp. 247–271 {{MR|}} {{ZBL|40.0283.01}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> E. Borel, "Leçons sur la théorie des fonctions" , Gauthier-Villars (1928) {{MR|0033328}} {{ZBL|54.0327.02}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> S. Pillai, "On normal numbers" ''Proc. Indian Acad. Sci. Sect. A'' , '''12''' (1940) pp. 179–184 {{MR|0002324}} {{ZBL|0025.30802}} {{ZBL|66.1212.02}} </TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> I. Niven, H. Zuckerman, "On the definition of normal numbers" ''Pacific J. Math.'' , '''1''' (1951) pp. 103–109 {{MR|0044560}} {{ZBL|0042.26902}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> D.G. Champernowne, "The construction of decimals normal in the scale of ten" ''J. London Math. Soc.'' , '''8''' (1933) pp. 254–260 {{MR|}} {{ZBL|0007.33701}} {{ZBL|59.0214.01}} </TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> W. Sierpiński, "Démonstration élémentaire d'un théorème de M. Borel sur les nombres absolument normaux et détermination effective d'un tel nombre" ''Bull. Soc. Math. France'' , '''45''' (1917) pp. 127–132 {{MR|0073664}} {{MR|0055398}} {{MR|0021058}} {{MR|1550055}} {{ZBL|}} </TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top"> H. Lebesgue, "Sur certaines démonstrations d'existence" ''Bull. Soc. Math. France'' , '''45''' (1917) pp. 132–144 {{MR|1504765}} {{ZBL|}} </TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top"> A.G. Postnikov, "Arithmetic modelling of random processes" ''Trudy Mat. Inst. Steklov.'' , '''57''' (1960) (In Russian)</TD></TR></table>



====Comments====
Almost-all numbers are normal with respect to every base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756046.png" /> (see e.g. Theorem 8.11 in [[#References|[a1]]]). It is not known whether familiar numbers like <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756047.png" /> are normal or not. Normal numbers are potentially interesting in the context of random number generators. A normal number to a base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756048.png" /> is necessarily irrational. The weakly-normal number (to base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756049.png" />) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756050.png" /> is of course rational. The number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756051.png" />, obtained as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756052.png" /> where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756053.png" /> stands for the group of digits representing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756054.png" /> to base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756055.png" />, is normal to base <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/n/n067/n067560/n06756056.png" /> [[#References|[5]]]. The same recipe works to obtain normal numbers to any given base.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> I. Niven, "Irrational numbers" , Math. Assoc. Amer. (1956) {{MR|1570844}} {{MR|0080123}} {{ZBL|0070.27101}} </TD></TR></table>