Normal number

For the floating-point meaning in computing, see normal number (computing).

In mathematics, a normal number is a real number whose infinite sequence of digits in every base b[1] is distributed uniformly in the sense that each of the b digit values has the same natural density 1/b, also all possible b2 pairs of digits are equally likely with density b−2, all b3 triplets of digits equally likely with density b−3, etc.

Intuitively this means that no digit, or (finite) combination of digits, occurs more frequently than any other, and this is true whether the number is written in base 10, binary, or any other base. A normal number can be thought of as an infinite sequence of coin flips (binary) or rolls of a die (base 6). Even though there will be sequences such as 10, 100, or more consecutive tails (binary) or fives (base 6) or even 10, 100, or more repetitions of a sequence such as tail-head (two consecutive coin flips) or 6-1 (two consecutive rolls of a die), there will also be equally many of any other sequence of equal length. No digit or sequence is "favored".

While a general proof can be given that almost all real numbers are normal (in the sense that the set of exceptions has Lebesgue measure zero), this proof is not constructive and only very few specific numbers have been shown to be normal. For example, it is widely believed that the numbers 2, π, and e are normal, but a proof remains elusive.

Definitions

Let Σ be a finite alphabet of b digits, and Σ the set of all sequences that may be drawn from that alphabet. Let S ∈ Σ be such a sequence. For each a in Σ let NS(a, n) denote the number of times the letter a appears in the first n digits of the sequence S. We say that S is simply normal if the limit

\lim_{n\to\infty} \frac{N_S(a,n)}{n} = \frac{1}{b}

for each a. Now let w be any finite string in Σ and let NS(w, n) to be the number of times the string w appears as a substring in the first n digits of the sequence S. (For instance, if S = 01010101..., then NS(010, 8) = 3.) S is normal if, for all finite strings w ∈ Σ,

\lim_{n\to\infty} \frac{N_S(w,n)}{n} = \frac{1}{b^{|w|}}

where |w| denotes the length of the string w. In other words, S is normal if all strings of equal length occur with equal asymptotic frequency. For example, in a normal binary sequence (a sequence over the alphabet {0,1}), 0 and 1 each occur with frequency 12; 00, 01, 10, and 11 each occur with frequency 14; 000, 001, 010, 011, 100, 101, 110, and 111 each occur with frequency 18, etc. Roughly speaking, the probability of finding the string w in any given position in S is precisely that expected if the sequence had been produced at random.

Suppose now that b is an integer greater than 1 and x is a real number. Consider the infinite digit sequence expansion Sx, b of x in the base b positional number system (we ignore the decimal point). We say that x is simply normal in base b if the sequence Sx, b is simply normal[2] and that x is normal in base b if the sequence Sx, b is normal.[3] The number x is called a normal number (or sometimes an absolutely normal number) if it is normal in base b for every integer b greater than 1.[4][5]

A given infinite sequence is either normal or not normal, whereas a real number, having a different base-b expansion for each integer b ≥ 2, may be normal in one base but not in another.[6][7] For bases r and s with log r / log s rational (so that r = bm and s = bn) every number normal in base r is normal in base s. For bases r and s with log r / log s irrational, there are uncountably many numbers normal in each base but not the other.[7]

A disjunctive sequence is a sequence in which every finite string appears. A normal sequence is disjunctive, but a disjunctive sequence need not be normal. A rich number in base b is one whose expansion in base b is disjunctive:[8] one that is disjunctive to every base is called absolutely disjunctive or is said to be a lexicon. A number normal in base b is rich in base b, but not necessarily conversely. The real number x is rich in base b if and only if the set { x bn mod 1: n∈N } is dense in the unit interval.[8][9]

We defined a number to be simply normal in base b if each individual digit appears with frequency 1/b. For a given base b, a number can be simply normal (but not normal or b-dense), b-dense (but not simply normal or normal), normal (and thus simply normal and b-dense), or none of these. A number is absolutely non-normal or absolutely abnormal if it is not simply normal in any base.[4][10]

Properties and examples

The concept of a normal number 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 (Borel 1909). This theorem established the existence of normal numbers. In 1917, Wacław Sierpiński showed that it is possible to specify a particular such number. Becher and Figueira proved in 2002 that there is a computable absolutely normal number, however no digits of their number are known.

The set of non-normal numbers, though "small" in the sense of being a null set, is "large" in the sense of being uncountable. For instance, there are uncountably many numbers whose decimal expansion does not contain the digit 5, and none of these are normal.

Champernowne's number

0.1234567891011121314151617...,

obtained by concatenating the decimal representations of the natural numbers in order, is normal in base 10, but it might not be normal in some other bases.

The Copeland–Erdős constant

0.235711131719232931374143...,

obtained by concatenating the prime numbers in base 10, is normal in base 10, as proved by Copeland and Erdős (1946). More generally, the latter authors proved that the real number represented in base b by the concatenation

0.f(1)f(2)f(3)...,

where f(n) is the nth prime expressed in base b, is normal in base b. Besicovitch (1935) proved that the number represented by the same expression, with f(n) = n2,

0.149162536496481100121144...,

obtained by concatenating the square numbers in base 10, is normal in base 10. Davenport & Erdős (1952) proved that the number represented by the same expression, with f being any polynomial whose values on the positive integers are positive integers, expressed in base 10, is normal in base 10.

Nakai & Shiokawa (1992) proved that if f(x) is any non-constant polynomial with real coefficients such that f(x) > 0 for all x > 0, then the real number represented by the concatenation

0.[f(1)][f(2)][f(3)]...,

where [f(n)] is the integer part of f(n) expressed in base b, is normal in base b. (This result includes as special cases all of the above-mentioned results of Champernowne, Besicovitch, and Davenport & Erdős.) The authors also show that the same result holds even more generally when f is any function of the form

f(x) = α·xβ + α1·xβ1 + ... + αd·xβd,

where the αs and βs are real numbers with β > β1 > β2 > ... > βd ≥ 0, and f(x) > 0 for all x > 0.

Every Chaitin's constant \ \Omega is a normal number (Calude, 1994). A computable normal number was constructed in (Becher 2002). Although these constructions do not directly give the digits of the numbers constructed, the second shows that it is possible in principle to enumerate all the digits of a particular normal number.

Bailey and Crandall show an explicit uncountably infinite class of b-normal numbers by perturbing Stoneham numbers.[11]

It has been an elusive goal 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 ). It is not even known whether all digits occur infinitely often in the decimal expansions of those constants. In particular, the popular claim "every string of numbers eventually occurs in π" is not known to be true. It has been conjectured that every irrational algebraic number is normal; while no counterexamples are known, there also exists no algebraic number that has been proven to be normal in any base.

Non-normal numbers

No rational number is normal to any base, since the digit sequences of rational numbers are eventually periodic.[12] (However, a rational number can be simply normal to a particular base: \frac{123,\!456,\!789}{9,\!999,\!999,\!999}=0.\overline{0123456789} is simply normal to base 10.)

Martin 2001 has given a simple example of an irrational absolutely non-normal number.[13] Let d2 = 4 and

d_j = j^{d_{j-1} / (j-1)} \ ,
\xi = \prod_{j=2}^\infty \left({1 - \frac{1}{d_j}}\right) \ .

Then ξ is absolutely non-normal and a Liouville number; hence a transcendental number.

Properties

Additional properties of normal numbers include:

Connection to finite-state machines

Agafonov showed an early connection between finite-state machines and normal sequences: every infinite subsequence selected from a normal sequence by a regular language is also normal. In other words, if one runs a finite-state machine on a normal sequence, where each of the finite-state machine's states are labeled either "output" or "no output", and the machine outputs the digit it reads next after entering an "output" state, but does not output the next digit after entering a "no output state", then the sequence it outputs will be normal (Agafonov 1968).

A deeper connection exists with finite-state gamblers (FSGs) and information lossless finite-state compressors (ILFSCs).

\limsup_{n\to\infty} d(S \upharpoonright n) = \infty,
where d(S \upharpoonright n) is the amount of money the gambler d has after reading the first n digits of S (see limit superior).
\liminf_{n\to\infty} \frac{|C(S \upharpoonright n)|}{n} < 1,
where |C(S \upharpoonright n)| is the number of digits output by C after reading the first n digits of S. Note that the compression ratio (the limit inferior above) can always be made to equal 1 by the 1-state ILFSC that simply copies its input to the output.

Schnorr and Stimm showed that no FSG can succeed on any normal sequence, and Bourke, Hitchcock and Vinodchandran showed the converse. Therefore:

A sequence is normal if and only if there is no finite-state gambler that succeeds on it.

Ziv and Lempel showed:

A sequence is normal if and only if it is incompressible by any information lossless finite-state compressor

(they actually showed that the sequence's optimal compression ratio over all ILFSCs is exactly its entropy rate, a quantitative measure of its deviation from normality, which is 1 exactly when the sequence is normal). Since the LZ compression algorithm compresses asymptotically as well as any ILFSC, this means that the LZ compression algorithm can compress any non-normal sequence. (Ziv Lempel 1978)

These characterizations of normal sequences can be interpreted to mean that "normal" = "finite-state random"; i.e., the normal sequences are precisely those that appear random to any finite-state machine. Compare this with the algorithmically random sequences, which are those infinite sequences that appear random to any algorithm (and in fact have similar gambling and compression characterizations with Turing machines replacing finite-state machines).

Connection to equidistributed sequences

A number x is normal in base b if and only if the sequence {\left( b^k x \right) }_{k=0}^\infty is equidistributed modulo 1,[15][16] or equivalently, using Weyl's criterion, if and only if

\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}e^{2 \pi i m b^k x}=0 \quad\text{ for all integers } m\geq 1.

This connection leads to the terminology that x is normal in base β for any real number β if the sequence \left({x \beta^k}\right)_{k=0}^\infty is equidistributed modulo 1.[16]

Notes

  1. The only bases considered here are natural numbers greater than 1
  2. Bugeaud 2012, p. 78
  3. Bugeaud 2012, p. 79
  4. 1 2 Bugeaud 2012, p. 102
  5. Adamczewski & Bugeaud 2010, p. 413
  6. Cassels 1959
  7. 1 2 Schmidt 1960
  8. 1 2 Bugeaud 2012, p. 92
  9. x bn mod 1 denotes the fractional part of x bn.
  10. Martin (2001)
  11. Bailey & Crandall (2002).
  12. Murty (2007, p. 483).
  13. Bugeaud (2012) p.113
  14. Long (1957).
  15. Bugeaud 2012, p. 89
  16. 1 2 Everest et al. 2003, p. 127

See also

References

Further reading

External links

This article is issued from Wikipedia - version of the Wednesday, March 09, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.