Editing Normal number (section)

== Definitions ==

Let {{mvar|Σ}} be a finite [[alphabet (computer science)|alphabet]] of {{mvar|b}}-digits, {{math|{{var|Σ}}{{sup|ω}}}} the set of all infinite [[sequence]]s that may be drawn from that alphabet, and {{math|{{var|Σ}}{{sup|&lowast;}}}} the set of finite sequences, or [[String (computer science)#Formal theory|strings]].<ref>ω is the smallest infinite [[ordinal number]]; {{sup|&lowast;}} is the [[Kleene star]].</ref> Let {{math|{{var|S}} ∈ {{var|Σ}}{{sup|ω}}}} be such a sequence. For each {{mvar|a}} in {{mvar|Σ}} let {{math|{{var|N}}{{sub|{{var|S}}}}({{var|a}}, {{var|n}})}} denote the number of times the digit {{mvar|a}} appears in the first {{mvar|n}} digits of the sequence {{mvar|S}}. We say that {{mvar|S}} is '''simply normal''' if the [[limit of a sequence|limit]]

<math display="block">\lim_{n\to\infty} \frac{N_S(a,n)}{n} = \frac{1}{b}</math>

for each {{mvar|a}}. Now let {{mvar|w}} be any finite string in {{math|{{var|Σ}}{{sup|&lowast;}}}} and let {{math|{{var|N}}{{sub|{{var|S}}}}({{var|w}}, {{var|n}})}} be the number of times the string {{mvar|w}} appears as a [[substring]] in the first {{mvar|n}} digits of the sequence {{mvar|S}}. (For instance, if {{math|1={{var|S}} = {{mono|01010101}}...}}, then {{math|1={{var|N}}{{sub|{{var|S}}}}({{mono|010}}, 8) = 3}}.) {{mvar|S}} is '''normal''' if, for all finite strings {{math|1={{var|w}} ∈ {{var|Σ}}{{sup|&lowast;}}}},

<math display="block">\lim_{n\to\infty} \frac{N_S(w,n)}{n} = \frac{1}{b^{|w|}}</math>

where {{math|{{mabs|{{var|w}}}}}} denotes the length of the string {{mvar|w}}. In other words, {{mvar|S}} is normal if all strings of equal length occur with equal [[Asymptotic analysis|asymptotic]] frequency. For example, in a normal binary sequence (a sequence over the alphabet {{math|{{mset|{{mono|0}},{{sans-serif|1}}}}}}), {{mono|0}} and {{mono|1}} each occur with frequency {{frac|2}}; {{mono|00}}, {{mono|01}}, {{mono|10}}, and {{mono|11}} each occur with frequency {{frac|4}}; {{mono|000}}, {{mono|001}}, {{mono|010}}, {{mono|011}}, {{mono|100}}, {{mono|101}}, {{mono|110}}, and {{mono|111}} each occur with frequency {{frac|8}}; etc. Roughly speaking, the [[probability]] of finding the string {{mvar|w}} in any given position in {{mvar|S}} is precisely that expected if the sequence had been produced at [[random sequence|random]].

Suppose now that {{mvar|b}} is an [[integer]] greater than 1 and {{mvar|x}} is a [[real number]]. Consider the infinite digit sequence expansion {{math|{{var|S}}{{sub|{{var|x}}, {{var|b}}}}}} of {{mvar|x}} in the base {{mvar|b}} [[numeral system|positional number system]] (we ignore the decimal point). We say that {{mvar|x}} is '''simply normal in base {{mvar|b}}''' if the sequence {{math|{{var|S}}{{sub|{{var|x}}, {{var|b}}}}}} is simply normal{{sfn|Bugeaud|2012|p=78}} and that {{mvar|x}} is '''normal in base {{mvar|b}}''' if the sequence {{math|{{var|S}}{{sub|{{var|x}}, {{var|b}}}}}} is normal.{{sfn|Bugeaud|2012|p=79}} The number {{mvar|x}} is called a '''normal number''' (or sometimes an '''absolutely normal number''') if it is normal in base {{mvar|b}} for every integer {{mvar|b}} greater than 1.{{sfn|Bugeaud|2012|p=102}}{{sfn|Adamczewski|Bugeaud|2010|p=413}}

A given infinite sequence is either normal or not normal, whereas a real number, having a different base-{{mvar|b}} expansion for each integer {{math|{{var|b}} ≥ 2}}, may be normal in one base but not in another{{sfn|Cassels|1959}}{{sfn|Schmidt|1960}} (in which case it is not a normal number). For bases {{mvar|r}} and {{mvar|s}} with {{math|log {{var|r}} / log {{var|s}}}} [[Rational number|rational]] (so that {{math|1={{var|r}} = {{var|b}}{{sup|{{var|m}}}}}} and {{math|1={{var|s}} = {{var|b}}{{sup|{{var|n}}}}}}) every number normal in base {{mvar|r}} is normal in base {{mvar|s}}. For bases {{mvar|r}} and {{mvar|s}} with {{math|log {{var|r}} / log {{var|s}}}} irrational, there are uncountably many numbers normal in each base but not the other.{{sfn|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 ''[[rich number]]'' in base {{mvar|b}} is one whose expansion in base {{mvar|b}} is disjunctive:{{sfn|Bugeaud|2012|p=92}} one that is disjunctive  to every base is called ''absolutely disjunctive'' or is said to be a ''[[lexicon (mathematics)|lexicon]]''. A number normal in base {{mvar|b}} is rich in base {{mvar|b}}, but not necessarily conversely. The real number {{mvar|x}} is rich in base {{mvar|b}} if and only if the set {{math|{{mset|{{var|x}} {{var|b}}{{sup|{{var|n}}}} mod 1 : {{var|n}} ∈ {{var|N}}}}}} is [[Dense set|dense]] in the [[unit interval]].{{sfn|Bugeaud|2012|p=92}}<ref>{{math|{{var|x}} {{var|b}}{{sup|{{var|n}}}} mod 1}} denotes the [[fractional part]] of {{math|{{var|x}} {{var|b}}{{sup|{{var|n}}}}}}.</ref>

We defined a number to be simply normal in base {{mvar|b}} if each individual digit appears with frequency {{frac|{{mvar|b}}}}. For a given base {{mvar|b}}, a number can be simply normal (but not normal or rich), rich (but not simply normal or normal), normal (and thus simply normal and rich), or none of these. A number is '''absolutely non-normal''' or '''absolutely abnormal''' if it is not simply normal in any base.{{sfn|Bugeaud|2012|p=102}}{{sfn|Martin|2001}}