Normale Zahl

Grundidee und Folgen über endlichen Alphabeten

Eine normale Zahl ist eine reelle Zahl, in deren Nachkommastellen jeder mögliche Ziffernblock vorkommt und alle Blöcke derselben Länge asymptotisch gleich häufig sind. „Asymptotisch“ bedeutet dabei, dass sich die relative Häufigkeit dem angegebenen Wert annähert, wenn immer mehr Stellen betrachtet werden.

Allgemeiner sei Σ ein endliches Alphabet und Σ^∞ die Menge aller unendlichen Folgen über diesem Alphabet. Für eine Folge S bezeichnet N_S(a,n), wie oft das Zeichen a unter den ersten n Folgengliedern vorkommt. S heißt einfach normal, wenn für jedes a ∈ Σ gilt:

limₙ→∞ N_S(a,n)/n = 1/|Σ|.

Dabei ist |Σ| die Anzahl der Zeichen des Alphabets. Einfach normal bedeutet somit, dass alle einzelnen Zeichen langfristig gleich häufig erscheinen.

Für ein endliches Wort w bezeichnet N_S(w,n), wie oft w als zusammenhängendes Teilwort in den ersten n Zeichen von S auftritt. Die Folge S heißt normal, wenn für jedes endliche Wort w gilt:

limₙ→∞ N_S(w,n)/n = 1/|Σ|^|w|,

wobei |w| die Länge von w ist. Folglich treten alle Wörter gleicher Länge k mit derselben asymptotischen Häufigkeit auf. Überlappende Vorkommen werden mitgezählt: Für S = 01010101… gilt beispielsweise N_S(010,8) = 3.

In einer normalen Binärfolge über {0,1} besitzen 0 und 1 jeweils die Grenzhäufigkeit 1/2. Die vier Zweierblöcke 00, 01, 10 und 11 haben jeweils die Grenzhäufigkeit 1/4; jeder der acht möglichen Dreierblöcke hat die Grenzhäufigkeit 1/8.

Normalität von Zahlen

Für eine reelle Zahl x betrachtet man ihre Ziffernfolge S_{x,b} in einem Stellenwertsystem mit ganzzahliger Basis b ≥ 2. Das zugehörige Alphabet ist Σ_b = {0,1,…,b−1}. Die Position des Zahlentrenners spielt für die Normalität keine Rolle. N_{S_{x,b}}(w,n) gibt an, wie oft der Ziffernblock w unter den ersten n Nachkommastellen vorkommt.

x heißt einfach normal zur Basis b, wenn jede einzelne Ziffer a langfristig mit derselben relativen Häufigkeit erscheint:

limₙ→∞ N_{S_{x,b}}(a,n)/n = 1/b.

Die Zahl 1/3 = 0,‾01₂ ist beispielsweise zur Basis 2 einfach normal, weil in ihrer periodischen Binärdarstellung 0 und 1 gleich häufig vorkommen. Das genügt jedoch nicht für vollständige Normalität, da dafür auch sämtliche längeren Blöcke gleichmäßig verteilt sein müssen.

x heißt normal zur Basis b, wenn für jeden endlichen Ziffernblock w gilt:

limₙ→∞ N_{S_{x,b}}(w,n)/n = 1/b^|w|.

Ein Block der Länge k hat demnach die Grenzhäufigkeit 1/b^k. Eine Zahl ist genau dann normal zur Basis b, wenn die Folge (bⁿx)ₙ≥1 = (b·x,b²·x,b³·x,…) gleichverteilt modulo 1 ist. Gleichwertig dazu ist x genau dann zur Basis b normal, wenn sie zu jeder der Basen b, b², b³, … einfach normal ist.

Eine Zahl heißt absolut normal, wenn sie zu jeder ganzzahligen Basis b ≥ 2 normal ist.

Häufigkeit normaler Zahlen

Fast alle reellen Zahlen im Lebesgue-Sinn sind normal und sogar absolut normal. Das bedeutet, dass die Menge der Ausnahmen das Lebesgue-Maß null besitzt. Dieses Ergebnis bewies Émile Borel 1909 mithilfe des Borel-Cantelli-Lemmas.

Trotzdem gibt es nicht nur abzählbar viele Ausnahmen: Die Menge der nicht normalen Zahlen ist überabzählbar. „Fast alle“ ist hier daher eine Aussage über das Maß einer Menge und nicht darüber, ob ihre Elemente abgezählt werden können.

Konstruktionen und Abhängigkeit von der Basis

Wacław Sierpiński gab 1917 die erste Konstruktion einer normalen Zahl an. Verónica Becher und Santiago Figueira veröffentlichten 2002 einen Algorithmus zur Berechnung dieser Zahl. Die Chaitinsche Konstante ist dagegen ein Beispiel für eine nicht berechenbare normale Zahl.

Die erste explizite Konstruktion stammt von David Gawen Champernowne aus dem Jahr 1933. Die Champernowne-Zahl entsteht durch Aneinanderreihen der natürlichen Zahlen in Basis 10:

C₁₀ = 0,12345678910111213141516…

Sie ist zur Basis 10 normal, jedoch bezüglich einiger anderer Basen nicht normal. Ein weiteres Beispiel ist die Copeland-Erdős-Zahl, benannt nach Arthur Herbert Copeland und Paul Erdős. Sie entsteht durch Aneinanderreihen aller Primzahlen in Basis 10:

CE₁₀ = 0,235711131719232931374143…

Auch sie ist zur Basis 10 normal.

Wolfgang Schmidt zeigte 1960 einen Zusammenhang zwischen verschiedenen Basen r und s: Ist ln(r)/ln(s) rational, was gleichbedeutend damit ist, dass positive natürliche Zahlen m und n mit rⁿ = sᵐ existieren, dann ist jede zur Basis r normale Zahl auch zur Basis s normal. Die Umkehrung gilt ebenfalls. Ist ln(r)/ln(s) dagegen irrational, so hat die Menge der Zahlen, die zur Basis r normal, aber zur Basis s nicht normal sind, die Mächtigkeit des Kontinuums.

Nicht normale und noch ungeklärte Zahlen

Eine rationale Zahl kann zu keiner Basis normal sein, weil ihre Darstellung in jedem Stellenwertsystem schließlich periodisch wird. Außerdem lassen sich irrationale Zahlen konstruieren, die zu keiner Basis normal sind; solche Zahlen heißen absolut abnormal.

Bei vielen bekannten irrationalen Zahlen ist bislang nicht bewiesen, ob sie zu irgendeiner Basis normal sind. Dazu gehören die Kreiszahl π, die Eulersche Zahl e, der natürliche Logarithmus von 2 und √2. Die meisten Zahlen, deren Normalität bewiesen ist, wurden gezielt mit dieser Eigenschaft konstruiert.

David H. Bailey und Richard E. Crandall formulierten 2001 die bis heute unbewiesene Vermutung, dass jede irrationale algebraische Zahl normal ist.