Normal number

In mathematics, a normal number is a real number , below whose decimal digits all possible -digit blocks with the same asymptotic relative frequencies occur for each . ${\displaystyle k\geq 1}$ ${\displaystyle k}$

A number is called normal if every number block appears in its sequence of numbers and number blocks of the same length occur with the same frequency.

definition

Sequences over an alphabet

Let be a finite alphabet and denote the set of all sequences (= infinite sequences) over this alphabet. Be such a consequence. For each character, let us denote the number of times it occurs in the first parts of the sequence . The consequence is simply called normal if and only if the following limit relation is fulfilled for each : ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{\infty }}$ ${\displaystyle S\in \Sigma ^{\infty }}$ ${\displaystyle a\in \Sigma }$ ${\displaystyle N_{S}(a,n)}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle a}$

${\displaystyle \lim _{n\to \infty }{\frac {N_{S}(a,n)}{n}}={\frac {1}{|\Sigma |}}}$

Let be a word (= finite sequence) above this alphabet, i.e. off , and be the number of times the word occurs as a partial word in the first characters of the sequence . (Example: Let , is for example .) The sequence is called normal if and only if the following limit relation holds for all finite values: ${\displaystyle w}$ ${\displaystyle \textstyle \Sigma ^{*}=\bigcup \{\Sigma ^{n}\mid n\in \mathbb {N} _{0}\}}$ ${\displaystyle N_{S}(w,n)}$ ${\displaystyle w}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle S=01010101...}$ ${\displaystyle N_{S}(010,8)}$ ${\displaystyle S}$ ${\displaystyle w\in \Sigma ^{\ast }}$

${\displaystyle \lim _{n\to \infty }{\frac {N_{S}(w,n)}{n}}={\frac {1}{{|\Sigma |}^{|w|}}}}$

where denotes the length of the word and the number of characters in the alphabet . ${\displaystyle |w|}$ ${\displaystyle w}$ ${\displaystyle |\Sigma |}$ ${\displaystyle \Sigma }$

In other words, the sequence is normal if and only if all words of the same length occur with the same asymptotic frequency. In a normal binary sequence (= sequence over the alphabet ) are the numbers and in the limit with the frequency before, also the pairings , , and with the frequency that three blocks , , , , , and with the frequency , etc. ${\displaystyle S}$ ${\displaystyle k=|w|}$ ${\displaystyle \{0,1\}}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle n\to \infty }$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle 00}$ ${\displaystyle 01}$ ${\displaystyle 10}$ ${\displaystyle 11}$ ${\displaystyle {\tfrac {1}{4}}}$ ${\displaystyle 000}$ ${\displaystyle 001}$ ${\displaystyle 010}$ ${\displaystyle 011}$ ${\displaystyle 100}$ ${\displaystyle 101}$ ${\displaystyle 111}$ ${\displaystyle {\tfrac {1}{8}}}$

Let us now consider a string of digits of any real number in the representation in a place value system (as a number system ) with an integer base ( -adic representation). The characters here are the digits of this representation from to , so the alphabet is . The position of the decimal separator (comma) does not matter. ${\displaystyle S_{x,b}}$ ${\displaystyle x}$ ${\displaystyle b\geq 2}$ ${\displaystyle b}$ ${\displaystyle 0}$ ${\displaystyle b-1}$ ${\displaystyle \Sigma _{b}=\{0,1,\dots ,b-1\}}$

For each -digit number block in this representation (i.e. from digits to the base and with length ) denotes the number with which the number block appears under the first decimal places of. ${\displaystyle k}$ ${\displaystyle w}$ ${\displaystyle b}$ ${\displaystyle |w|=k}$ ${\displaystyle N_{S_{x,b}}(w,n)}$ ${\displaystyle w}$ ${\displaystyle n}$ ${\displaystyle x}$

Just normal number

The number is simply called normal to the base if every sequence of digits in the -adic representation is a simply normal sequence above the alphabet . (If this is the case, the choice for the sequence of digits is unambiguous; in general, this sequence of digits is not unambiguous, see 0.999 ... ) This is exactly the case if the following applies to all digits in this representation: ${\displaystyle x\in \mathbb {R} }$ ${\displaystyle b}$ ${\displaystyle S_{x,b}}$ ${\displaystyle b}$ ${\displaystyle \Sigma _{b}}$ ${\displaystyle a}$

${\displaystyle \lim _{n\to \infty }{\frac {N_{S_{x,b}}(a,n)}{n}}={\frac {1}{b}}}$

For example, the number (periodic block from in base ) is simply normal in base , because the digits and occur equally often. ${\displaystyle {\tfrac {1}{3}}=0{,}{\overline {01}}_{2}}$ ${\displaystyle 01}$ ${\displaystyle 2}$ ${\displaystyle 2}$ ${\displaystyle 0}$ ${\displaystyle 1}$

Normal number

The number is called normal to the base if and only if the sequence of digits in the -adic representation is a normal sequence above the alphabet . This is the case if and only if for every finite sequence of digits this representation holds: ${\displaystyle x\in \mathbb {R} }$ ${\displaystyle b}$ ${\displaystyle S_{x,b}}$ ${\displaystyle b}$ ${\displaystyle \Sigma _{b}}$ ${\displaystyle w}$

${\displaystyle \lim _{n\to \infty }{\frac {N_{S_{x,b}}(w,n)}{n}}={\frac {1}{b^{|w|}}}}$

(The sequence is also known as a -digit number pad) ${\displaystyle w}$ ${\displaystyle k}$

It can be shown that a number is normal to the base if and only if the sequence ${\displaystyle x}$ ${\displaystyle b}$

${\displaystyle (b^{n}x)_{n\geq 1}=(b\cdot x,b^{2}\cdot x,b^{3}\cdot x,\dots )}$

is evenly distributed modulo 1 .

Absolutely normal number

The number is called absolutely normal if it is normal on every basis . ${\displaystyle x}$ ${\displaystyle b\geq 2}$

The following equivalence applies: the number is normal to the base if and only if it is simply normal to each of the bases . ${\displaystyle x}$ ${\displaystyle b}$ ${\displaystyle b,b^{2},b^{3},\ldots }$

Number of normal numbers

The term normal number was introduced by Émile Borel in 1909 . He also immediately proved with the help of the Borel-Cantelli lemma that almost all (in the Lebesgue sense ) real numbers are normal or even absolutely normal.

However, the set of non-normal numbers is uncountable , as can easily be shown using a construction corresponding to Cantor's discontinuum .

Construction of normal numbers

Wacław Sierpiński delivered the first construction of a normal number in 1917. In 2002 Verónica Becher and Santiago Figueira gave an algorithm to calculate the number constructed by Sierpiński. The Chaitin's constant is an example of a non- computable normal number.

David Gawen Champernowne gave the first explicit construction of a normal number known as the Champernowne number in 1933 . In the decimal system, the first digits are:

${\displaystyle C_{10}=0{,}12345678910111213141516\ldots }$

It is sequence A033307 in OEIS and is formed by stringing together the natural numbers as a base . The Champernowne number is not normal with respect to some other bases. ${\displaystyle 10}$

The Copeland Erdős number , named after Arthur Herbert Copeland and Paul Erdős , is another example of a base normal number, sequence A33308 in OEIS . The first decimal places are: ${\displaystyle 10}$

${\displaystyle CE_{10}=0{,}235711131719232931374143\ldots }$

It is formed by stringing together all prime numbers to form the basis . ${\displaystyle 10}$

Wolfgang Schmidt examined in 1960, under what conditions and numbers to the base are normal, and the base are normal, and showed: If a rational number (equivalent: if there are positive integers and with are), then each to the base normal number also to the base normal. The converse is also true, and even: if is irrational, then the set of numbers that are base normal and abnormal to base has the width of the continuum . ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle {\tfrac {\ln(r)}{\ln(s)}}}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle r^{n}=s^{m}}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle {\tfrac {\ln(r)}{\ln(s)}}}$ ${\displaystyle r}$ ${\displaystyle s}$

Not normal numbers

A rational number cannot be normal on any basis because its representation is always periodic. But there are also constructions of irrational numbers that are not normal on any basis (such numbers are called absolutely abnormal ).

Circle number π

It is not known of many irrational numbers whether they are normal on any basis or not, among them are the circle number ${\displaystyle \pi }$ , Euler's constant ${\displaystyle e}$ , the natural logarithm of the number 2 or . Most of the numbers recognized as normal were constructed with this property as a goal. ${\displaystyle {\sqrt {2}}}$

In 2001, the mathematicians David H. Bailey and Richard E. Crandall made the as yet unproven conjecture that every irrational algebraic number is normal.

Individual evidence

1. ↑ See pages 5 and 12 in the diploma thesis by Christoph Aistleitner named under “References”.
2. ↑ Wolfgang M. Schmidt: On normal numbers. Pacific Journal of Mathematics 10, 1960, pp. 661-672 ( online , ZMath Review ).

literature

• Ivan Niven: Irrational Numbers. Carus Math. Monographs, John Wiley and Sons Inc., 1956.
• Lauwerens Kuipers, Harald Niederreiter: Uniform distribution of sequences. Wiley-Interscience Publ., 1974.
• David H. Bailey, Richard E. Crandall: On the Random Character of Fundamental Constant Expansions , in: Experimental Mathematics 10 (2001), pp. 175–190 ( online ; PDF file; 279 kB)
• Émile Borel: Les probabilités dénombrables et leurs applications arithmétiques , in: Rend. Circ. Mat. Palermo 27 (1909), pp. 247-271
• David G. Champernowne: The Construction of Decimals Normal in the Scale of Ten , in: Journal of the London Mathematical Society , 8 (1933), pp. 254-260
• Waclaw Sierpinski: 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 , in: Bull. Soc. Math. France , 45 (1917), pp. 125-144
• Verónica Becher, Santiago Figueira: An example of a computable absolutely normal number , in: Theoretical Computer Science , 270 (2002), pp. 947–958 ( www-2.dc.uba.ar/profesores/becher/becherTCS2002.pdf )
• Christoph Aistleitner: Normal numbers , diploma thesis, Vienna University of Technology, 2006, online (PDF file; 795 kB)