 Normal number

For the floatingpoint 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 b^{2} pairs of digits are equally likely with density b^{−2}, all b^{3} triplets of digits equally likely with density b^{−3}, etc.
While a general proof can be given that almost all numbers are normal (in the sense that the set of exceptions has Lebesgue measure zero), this proof is not constructive and only very few concrete 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.
Contents
Definitions
Let Σ be a finite alphabet of b digits, and Σ^{∞} the set of all sequences that may be drawn from that alphabet. Let S,w ∈ Σ^{∞} be two such sequences, of which the latter is finite string drawn from the alphabet Σ. Let n be a positive integer. Define 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; see also limit.) 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}⁄_{2}; 00, 01, 10, and 11 each occur with frequency ^{1}⁄_{4}; 000, 001, 010, 011, 100, 101, 110, and 111 each occur with frequency ^{1}⁄_{8}, 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 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 baseb expansion for each integer b ≥ 2, may be normal in one base but not in another (Cassels 1959 and Schmidt 1960). All normal numbers in base r are normal in base s if and only if log r / log s is a rational number (Schmidt 1960).
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 number that is disjunctive to every base is called absolutely disjunctive or is said to be a lexicon (Calude and Zamfirescu, 1999). A lexicon contains all writings, which have been or will be ever written, in any possible language. Every normal number is bdense, 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 (Calude and Zamfirescu, 1999).
Another weaker property than normality is simple normality. A number is 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 bdense), bdense (but not simply normal or normal), normal (and thus simply normal and bdense), or none of these.
Properties and examples
The concept of a normal number was introduced by Émile Borel in 1909. Using the BorelCantelli lemma, he proved the normal number theorem: almost all real numbers are normal, in the sense that the set of nonnormal numbers has Lebesgue measure zero (Borel 1909). This theorem established the existence of normal numbers. In 1917, Waclaw Sierpinski showed that it is possible to specify a particular such number. Becker and Figueira proved in 2002 that there is a computable normal number.
The set of nonnormal 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.
 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.
 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 n^{th} prime expressed in base b, is normal in base b. Besicovitch (1935) proved that the number represented by the same expression, with f(n) = n^{2},
 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 nonconstant polynomial with real coeﬃcients 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 abovementioned 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 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.
No rational number is normal to any base, since the digit sequences of rational numbers are eventually periodic.^{[2]}
Bailey and Crandall show an explicit uncountably infinite class of bnormal numbers by perturbing Stoneham numbers.^{[3]}
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. 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.
Additional properties of normal numbers include:
 Every positive number x is the product of two normal numbers. For instance if y is chosen uniformly at random from the interval (0,1) then almost surely y and x/y are both normal, and their product is x.
 If x is normal in base b and q ≠ 0 is a rational number, then is normal in base b. (Wall 1949)
 If is dense (for every α < 1 and for all sufficiently large n, ) and are the baseb expansions of the elements of A, then the number , formed by concatenating the elements of A, is normal in base b (Copeland and Erdős 1946). From this it follows that Champernowne's number is normal in base 10 (since the set of all positive integers is obviously dense) and that the CopelandErdős constant is normal in base 10 (since the prime number theorem implies that the set of primes is dense).
 A sequence is normal if and only if every block of equal length appears with equal frequency. (A block of length k is a substring of length k appearing at a position in the sequence that is a multiple of k: e.g. the first lengthk block in S is S[1..k], the second lengthk block is S[k+1..2k], etc.) This was implicit in the work of Ziv and Lempel (1978) and made explicit in the work of Bourke, Hitchcock, and Vinodchandran (2005).
 A number is normal in base b if and only if it is simply normal in base b^{k} for every integer . This follows from the previous block characterization of normality: Since the n^{th} block of length k in its base b expansion corresponds to the n^{th} digit in its base b^{k} expansion, a number is simply normal in base b^{k} if and only if blocks of length k appear in its base b expansion with equal frequency.
 A number is normal if and only if it is simply normal in every base. This follows from the previous characterization of base b normality.
 A number is bnormal if and only if there exists a set of positive integers where the number is simply normal to bases b^{m} for all ^{[4]} No finite set suffices to show that the number is bnormal.
 The set of normal sequences is closed under finite variations: adding, removing, or changing a finite number of digits in any normal sequence leaves it normal.
Connection to finitestate machines
Agafonov showed an early connection between finitestate machines and normal sequences: every subsequence selected from a normal sequence by a regular language is also normal. In other words, if one runs a finitestate machine on a normal sequence, where each of the finitestate 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 finitestate gamblers (FSGs) and information lossless finitestate compressors (ILFSCs).
 A finitestate gambler (a.k.a. finitestate martingale) is a finitestate machine over a finite alphabet Σ, each of whose states is labelled with percentages of money to bet on each digit in Σ. For instance, for an FSG over the binary alphabet Σ = {0,1}, the current state q bets some percentage of the gambler's money on the bit 0, and the remaining q_{1} = 1 − q_{0} fraction of the gambler's money on the bit 1. The money bet on the digit that comes next in the input (total money times percent bet) is multiplied by  Σ  , and the rest of the money is lost. After the bit is read, the FSG transitions to the next state according to the input it received. A FSG d succeeds on an infinite sequence S if, starting from $1, it makes unbounded money betting on the sequence; i.e., if
 A finitestate compressor is a finitestate machine with output strings labelling its state transitions, including possibly the empty string. (Since one digit is read from the input sequence for each state transition, it is necessary to be able to output the empty string in order to achieve any compression at all). An information lossless finitestate compressor is a finitestate compressor whose input can be uniquely recovered from its output and final state. In other words, for a finitestate compressor C with state set Q, C is information lossless if the function , mapping the input string of C to the output string and final state of C, is 11. Compression techniques such as Huffman coding or ShannonFano coding can be implemented with ILFSCs. An ILFSC C compresses an infinite sequence S if
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 finitestate gambler that succeeds on it.
Ziv and Lempel showed:
 A sequence is normal if and only if it is incompressible by any information lossless finitestate 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 nonnormal sequence. (Ziv Lempel 1978)
These characterizations of normal sequences can be interpreted to mean that "normal" = "finitestate random"; i.e., the normal sequences are precisely those that appear random to any finitestate 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 finitestate machines).
Connection to equidistributed sequences
A number x is normal in base b if and only if the sequence is equidistributed modulo 1, or equivalently, using Weyl's criterion, if and only if
Notes
 ^ The only bases considered here are natural numbers greater than 1
 ^ Murty (2007, p. 483).
 ^ Bailey & Crandall (2002).
 ^ Long (1957).
References
 Agafonov, V. N. (1968), "Normal sequences and finite automata", Soviet Mathematics Doklady 9: 324–325.
 Bailey, D. H.; Crandall, R. E. (2001), "On the random character of fundamental constant expansions", Experimental Mathematics 10: 175–190, http://www.nersc.gov/~dhbailey/dhbpapers/baicran.pdf.
 Bailey, D. H.; Crandall, R. E. (2002), "Random generators and normal numbers", Experimental Mathematics 11 (4): 527–546, http://www.emis.de/journals/EM/expmath/volumes/11/11.4/pp527_546.pdf.
 Bailey, D. H.; Misiurewicz, M. (2006), "A strong hot spot theorem", Proceedings of the American Mathematical Society 134 (9): 2495–2501, doi:10.1090/S0002993906085510, http://repositories.cdlib.org/lbnl/LBNL53656_Journal/.
 Becher, V.; Figueira, S. (2002), "An example of a computable absolutely normal number", Theoretical Computer Science 270: 947–958, doi:10.1016/S03043975(01)001700.
 Besicovitch, A. S. (1935), "The asymptotic distribution of the numerals in the decimal representation of the squares of the natural numbers", Mathematische Zeitschrift 39: 146–156, doi:10.1007/BF01201350.
 Borel, E. (1909), "Les probabilités dénombrables et leurs applications arithmétiques", Rendiconti del Circolo Matematico di Palermo 27: 247–271, doi:10.1007/BF03019651.
 Bourke, C.; Hitchcock, J. M.; Vinodchandran, N. V. (2005), "Entropy rates and finitestate dimension", Theoretical Computer Science 349 (3): 392–406, doi:10.1016/j.tcs.2005.09.040.
 Calude, C. (1994), "Borel normality and algorithmic randomness", in Rozenberg, G.; Salomaa, A., Developments in Language Theory: At the Crossroads of Mathematics, Computer Science and Biology, World Scientific, Singapore, pp. 113–119.
 Calude, C.S.; Zamfirescu, T. (1999), "Most numbers obey no probability laws", Publicationes Mathematicae Debrecen 54, (Supplement): 619–623.
 Cassels, J. W. S. (1959), "On a problem of Steinhaus about normal numbers", Colloquium Mathematicum 7: 95–101.
 Champernowne, D. G. (1933), "The construction of decimals normal in the scale of ten", Journal of the London Mathematical Society 8 (4): 254–260, doi:10.1112/jlms/s18.4.254.
 Copeland, A. H.; Erdős, P. (1946), "Note on normal numbers", Bulletin of the American Mathematical Society 52 (10): 857–860, doi:10.1090/S000299041946086577.
 Davenport, H.; Erdős, P. (1952), "Note on normal decimals", Canadian Journal of Mathematics 4: 58–63, doi:10.4153/CJM19520053.
 Khoshnevisan, Davar (2006), "Normal numbers are normal", Clay Mathematics Institute Annual Report 2006: 15, continued pp. 27–31, http://www.claymath.org/library/annual_report/ar2006/06report_normalnumbers.pdf.
 Long, C. T. (1957), "Note on normal numbers", Pacific Journal of Mathematics 7 (2): 1163–1165, http://projecteuclid.org/DPubS/Repository/1.0/Disseminate?view=body&id=pdf_1&handle=euclid.pjm/1103043507.
 Murty, Maruti Ram (2007), Problems in analytic number theory (2 ed.), Springer, ISBN 0387723498.
 Nakai, Y.; Shiokawa, I. (1992), "Discrepancy estimates for a class of normal numbers", Acta Arithmetica 62 (3): 271–284.
 Schmidt, W. (1960), "On normal numbers", Pacific Journal of Mathematics 10: 661–672, http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.pjm/1103038420.
 Schnorr, C. P.; Stimm, H. (1972), "Endliche Automaten und Zufallsfolgen", Acta Informatica 1 (4): 345–359, doi:10.1007/BF00289514.
 Sierpiński, W. (1917), "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", Bulletin de la Société Mathématique de France 45: 125–144.
 Wall, D. D. (1949), Normal Numbers, Ph.D. thesis, Berkeley, California: University of California.
 Ziv, J.; Lempel, A. (1978), "Compression of individual sequences via variablerate coding", IEEE Transactions on Information Theory 24 (5): 530–536, doi:10.1109/TIT.1978.1055934, http://citeseer.ist.psu.edu/ziv78compression.html.
Further reading
 Quéfflec, M. (2006), "Old and new results on normality", in Denteneer, D.; den Hollander, F.; Verbitskiy, E., Dynamics & Stochastics: Festschrift in honor of M. S. Keane, IMS Lecture Notes – Monograph Series, 48, Beachwood, Ohio: Institute of Mathematical Statistics, pp. 225–236, arXiv:math.DS/0608249, doi:10.1214/074921706000000248, ISBN 0940600641.
Categories: Number theory
 Sets of real numbers
Wikimedia Foundation. 2010.