Normal Number - Definitions

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 N_S(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

for each a. Now let w be any finite string in Σ∗ and let N_S(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 N_S(010, 8) = 3.) S is normal if, for all finite strings 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 1⁄₂; 00, 01, 10, and 11 each occur with frequency 1⁄₄; 000, 001, 010, 011, 100, 101, 110, and 111 each occur with frequency 1⁄₈, 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 S_{x, 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 S_{x, b} is simply normal and that x is normal in base b if the sequence S_{x, b} is normal. 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.

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. All normal numbers in base r are normal in base s if and only if log r / log s is a rational number.

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 on e whose expansion in base b is disjunctive: one that is disjunctive to every base is called absolutely disjunctive or is said to be a lexicon. A lexicon contains all writings, which have been or will be ever written, in any possible language. Every simply normal number is rich in the corresponding base, but not necessarily vice versa. A set is called "residual" if it contains the intersection of a countable family of open dense sets. The set of absolutely disjunctive reals (lexicons) is a residual.

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 if it is not simply normal in any base.