Namespaces
Variants
Actions

Difference between revisions of "Normal number"

From Encyclopedia of Mathematics
Jump to: navigation, search
(refs format)
(→‎References: isbn link)
 
(12 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{MSC|11K16}}
+
{{TEX|done}}{{MSC|11K16}}
  
 
[[Category:Probabilistic number theory]]
 
[[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
+
A real number $\alpha$, $0 < \alpha < 1$, having the following property: For every natural number $s$, any given $s$-tuple $\delta = (\delta_1,\ldots,\delta_s)$ consisting of the symbols $0,1,\ldots,g-1$ appears with asymptotic frequency $1/g^s$ in the sequence
 +
$$\label{eq:a1}
 +
\alpha_1,\ldots,\alpha_n,\ldots
 +
$$
 +
obtained from the expansion of $\alpha$ as an infinite fraction in base $g$,
 +
$$
 +
\alpha = \frac{\alpha_1}{g} + \cdots + \frac{\alpha_n}{g^n} + \cdots \ .
 +
$$
  
<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>
+
In more detail, let $g>1$ be a natural number and let
 +
$$\label{eq:a2}
 +
(\alpha_1,\ldots,\alpha_s), (\alpha_2,\ldots,\alpha_{s+1}), \ldots
 +
$$
 +
be the infinite sequence of $s$-tuples corresponding to \ref{eq:a1}. Let $N(n,\delta)$ denote the number of occurrences of the tuple $\delta = (\delta_1,\ldots,\delta_s)$ among the first $n$ tuples of \ref{eq:a2}. The number
 +
$$
 +
\alpha = \frac{\alpha_1}{g} + \cdots + \frac{\alpha_n}{g^n} + \cdots \ .
 +
$$
 +
is said to be normal if for any number $s$ and any given $s$-tuple $\delta$ consisting of the symbols $0,\ldots,g-1$,
 +
$$
 +
\lim_{n \rightarrow \infty} \frac{N(n,s)}{ n } = \frac{1}{g^s} \ .
 +
$$
  
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" />,
+
The concept of a normal number was introduced for $g=10$ by E. Borel (see {{Cite|B}}, {{Cite|B2}}, p. 197). He called a real number $\alpha$ ''weakly normal'' to the base $g$ if
 +
$$
 +
\lim_{n \rightarrow \infty} \frac{N(n,\delta)}{n} = \frac{1}{g}
 +
$$
 +
where $N(n,\delta)$ is the number of occurrences of $\delta$, $0 \le \delta \le g-1$, among the first $n$ terms of the sequences $\alpha_1,\alpha_2,\ldots$ and normal if $\alpha, g\alpha, g^2\alpha, \ldots$ are weakly normal to the bases $g, g^2, \ldots$. He also showed that for a normal number
 +
$$
 +
\lim_{n \rightarrow \infty} \frac{N(n,s)}{ n } = \frac{1}{g^s}
 +
$$
 +
for any $s$ and any given $s$-tuple $\delta = (\delta_1,\ldots,\delta_s)$. Later it was proved (see {{Cite|Pi}}, {{Cite|NZ}}, and also {{Cite|Po}}) that the last relation is equivalent to Borel's definition of 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/n06756011.png" /></td> </tr></table>
+
A number $\alpha$ is called absolutely normal if it is normal with respect to every base $g$. 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 {{Cite|C}}. Earlier (see {{Cite|S}}, {{Cite|L}}) 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 {{Cite|Po}}.
  
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
+
[[Uniform distribution|Uniform distribution]] of the fractional parts $\{ \alpha g^x \}$, $x = 0, 1, \ldots$ on the interval $[0,1]$ is equivalent to $\alpha$ being normal.
 
 
<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 {{Cite|B}}, {{Cite|B2}}, 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 {{Cite|Pi}}, {{Cite|NZ}}, and also {{Cite|Po}}) 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 {{Cite|C}}. Earlier (see {{Cite|S}}, {{Cite|L}}) 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 {{Cite|Po}}.
 
 
 
[[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====
 
====References====
Line 57: Line 59:
  
 
====Comments====
 
====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 {{Cite|N}}). 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" /> {{Cite|C}}. The same recipe works to obtain normal numbers to any given base.
+
Almost all numbers (with respect to [[Lebesgue measure]]) are normal with respect to every base $g$ (see e.g. Theorem 8.11 in {{Cite|N}} or section 9.13 of {{Cite|HW}}). It is not known whether familiar numbers like $\sqrt2,\,e,\,\pi$ are normal or not. Normal numbers are potentially interesting in the context of random number generators. A normal number to a base $g$ is necessarily irrational. The weakly-normal number (to base $10$) $0\cdot12345678901234567890\ldots$ is of course rational. The ''[[Champernowne number]]'' $x = 0\cdot1234567891011121314\ldots$, obtained as $x = 0 \cdot \alpha_1 \alpha_2 \alpha_3 \ldots$ where $\alpha_i$ stands for the group of digits representing $i$ to base $10$, is normal to base $10$ {{Cite|C}}. The same recipe works to obtain normal numbers to any given base.
  
 
====References====
 
====References====
 
{|
 
{|
 +
|valign="top"|{{Ref|HW}}|| Hardy, G. H.; Wright, E. M. "An Introduction to the Theory of Numbers", Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.), Oxford: Oxford University Press (2008) [1938] {{ISBN|978-0-19-921986-5}}  {{ZBL|1159.11001}}
 +
|-
 
|valign="top"|{{Ref|N}}|| I. Niven, "Irrational numbers" , Math. Assoc. Amer. (1956) {{MR|1570844}} {{MR|0080123}} {{ZBL|0070.27101}}
 
|valign="top"|{{Ref|N}}|| I. Niven, "Irrational numbers" , Math. Assoc. Amer. (1956) {{MR|1570844}} {{MR|0080123}} {{ZBL|0070.27101}}
 +
|}
 +
 +
====Comments====
 +
The example of Champernowne's number as an explicitly normal number in base 10 was generalised by Copeland and Erdős [CE] who showed that if $a_n$ is an increasing sequence of natural numbers with the property that for every $\theta > 1$ then  $a_n < n^\theta$ for sufficiently large $n$, then the number $0 \cdot \alpha_1 \alpha_2 \ldots$ is normal in base $g$ where $\alpha_n$ is the base $g$ expression of $a_n$.  See also [B] pp.86-87.
 +
 +
====References====
 +
{|
 +
|valign="top"|{{Ref|CE}}|| Copeland, A. H.; Erdős, P.  "Note on normal numbers", ''Bulletin of the American Mathematical Society'' '''52''' (1946) 857–860, {{DOI|10.1090/S0002-9904-1946-08657-7}} {{ZBL|0063.00962}}
 +
|-
 +
|valign="top"|{{Ref|B}}|| Bugeaud, Yann. ''Distribution modulo one and Diophantine approximation'', Cambridge Tracts in Mathematics 193, Cambridge: Cambridge University Press (2012) {{ISBN|978-0-521-11169-0}}, {{ZBL|1260.11001}}
 
|}
 
|}

Latest revision as of 08:11, 4 November 2023

2020 Mathematics Subject Classification: Primary: 11K16 [MSN][ZBL]

A real number $\alpha$, $0 < \alpha < 1$, having the following property: For every natural number $s$, any given $s$-tuple $\delta = (\delta_1,\ldots,\delta_s)$ consisting of the symbols $0,1,\ldots,g-1$ appears with asymptotic frequency $1/g^s$ in the sequence $$\label{eq:a1} \alpha_1,\ldots,\alpha_n,\ldots $$ obtained from the expansion of $\alpha$ as an infinite fraction in base $g$, $$ \alpha = \frac{\alpha_1}{g} + \cdots + \frac{\alpha_n}{g^n} + \cdots \ . $$

In more detail, let $g>1$ be a natural number and let $$\label{eq:a2} (\alpha_1,\ldots,\alpha_s), (\alpha_2,\ldots,\alpha_{s+1}), \ldots $$ be the infinite sequence of $s$-tuples corresponding to \ref{eq:a1}. Let $N(n,\delta)$ denote the number of occurrences of the tuple $\delta = (\delta_1,\ldots,\delta_s)$ among the first $n$ tuples of \ref{eq:a2}. The number $$ \alpha = \frac{\alpha_1}{g} + \cdots + \frac{\alpha_n}{g^n} + \cdots \ . $$ is said to be normal if for any number $s$ and any given $s$-tuple $\delta$ consisting of the symbols $0,\ldots,g-1$, $$ \lim_{n \rightarrow \infty} \frac{N(n,s)}{ n } = \frac{1}{g^s} \ . $$

The concept of a normal number was introduced for $g=10$ by E. Borel (see [B], [B2], p. 197). He called a real number $\alpha$ weakly normal to the base $g$ if $$ \lim_{n \rightarrow \infty} \frac{N(n,\delta)}{n} = \frac{1}{g} $$ where $N(n,\delta)$ is the number of occurrences of $\delta$, $0 \le \delta \le g-1$, among the first $n$ terms of the sequences $\alpha_1,\alpha_2,\ldots$ and normal if $\alpha, g\alpha, g^2\alpha, \ldots$ are weakly normal to the bases $g, g^2, \ldots$. He also showed that for a normal number $$ \lim_{n \rightarrow \infty} \frac{N(n,s)}{ n } = \frac{1}{g^s} $$ for any $s$ and any given $s$-tuple $\delta = (\delta_1,\ldots,\delta_s)$. Later it was proved (see [Pi], [NZ], and also [Po]) that the last relation is equivalent to Borel's definition of a normal number.

A number $\alpha$ is called absolutely normal if it is normal with respect to every base $g$. 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 [C]. Earlier (see [S], [L]) 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 [Po].

Uniform distribution of the fractional parts $\{ \alpha g^x \}$, $x = 0, 1, \ldots$ on the interval $[0,1]$ is equivalent to $\alpha$ being normal.

References

[B] E. Borel, "Les probabilités dénombrables et leurs applications arithmétiques" Rend. Circ. Math. Palermo , 27 (1909) pp. 247–271 Zbl 40.0283.01
[B2] E. Borel, "Leçons sur la théorie des fonctions" , Gauthier-Villars (1928) MR0033328 Zbl 54.0327.02
[Pi] S. Pillai, "On normal numbers" Proc. Indian Acad. Sci. Sect. A , 12 (1940) pp. 179–184 MR0002324 Zbl 0025.30802 Zbl 66.1212.02
[NZ] I. Niven, H. Zuckerman, "On the definition of normal numbers" Pacific J. Math. , 1 (1951) pp. 103–109 MR0044560 Zbl 0042.26902
[C] D.G. Champernowne, "The construction of decimals normal in the scale of ten" J. London Math. Soc. , 8 (1933) pp. 254–260 Zbl 0007.33701 Zbl 59.0214.01
[S] 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 MR0073664 MR0055398 MR0021058 MR1550055
[L] H. Lebesgue, "Sur certaines démonstrations d'existence" Bull. Soc. Math. France , 45 (1917) pp. 132–144 MR1504765
[Po] A.G. Postnikov, "Arithmetic modelling of random processes" Trudy Mat. Inst. Steklov. , 57 (1960) (In Russian)

Comments

Almost all numbers (with respect to Lebesgue measure) are normal with respect to every base $g$ (see e.g. Theorem 8.11 in [N] or section 9.13 of [HW]). It is not known whether familiar numbers like $\sqrt2,\,e,\,\pi$ are normal or not. Normal numbers are potentially interesting in the context of random number generators. A normal number to a base $g$ is necessarily irrational. The weakly-normal number (to base $10$) $0\cdot12345678901234567890\ldots$ is of course rational. The Champernowne number $x = 0\cdot1234567891011121314\ldots$, obtained as $x = 0 \cdot \alpha_1 \alpha_2 \alpha_3 \ldots$ where $\alpha_i$ stands for the group of digits representing $i$ to base $10$, is normal to base $10$ [C]. The same recipe works to obtain normal numbers to any given base.

References

[HW] Hardy, G. H.; Wright, E. M. "An Introduction to the Theory of Numbers", Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.), Oxford: Oxford University Press (2008) [1938] ISBN 978-0-19-921986-5 Zbl 1159.11001
[N] I. Niven, "Irrational numbers" , Math. Assoc. Amer. (1956) MR1570844 MR0080123 Zbl 0070.27101

Comments

The example of Champernowne's number as an explicitly normal number in base 10 was generalised by Copeland and Erdős [CE] who showed that if $a_n$ is an increasing sequence of natural numbers with the property that for every $\theta > 1$ then $a_n < n^\theta$ for sufficiently large $n$, then the number $0 \cdot \alpha_1 \alpha_2 \ldots$ is normal in base $g$ where $\alpha_n$ is the base $g$ expression of $a_n$. See also [B] pp.86-87.

References

[CE] Copeland, A. H.; Erdős, P. "Note on normal numbers", Bulletin of the American Mathematical Society 52 (1946) 857–860, DOI 10.1090/S0002-9904-1946-08657-7 Zbl 0063.00962
[B] Bugeaud, Yann. Distribution modulo one and Diophantine approximation, Cambridge Tracts in Mathematics 193, Cambridge: Cambridge University Press (2012) ISBN 978-0-521-11169-0, Zbl 1260.11001
How to Cite This Entry:
Normal number. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Normal_number&oldid=26888
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article