- Farey-Reihe
-
Eine Farey-Folge (mathematisch unkorrekt auch Farey-Reihe oder einfach Farey-Brüche) ist in der Zahlentheorie eine geordnete Menge der ausgekürzten Brüche zwischen 0 und 1, deren jeweiliger Nenner den Index N nicht übersteigt. Benannt sind die Farey-Folgen nach dem britischen Geologen John Farey.
Inhaltsverzeichnis
Formale Definition
Eine Farey-Folge N-ter Ordnung FN ist eine geordnete Menge von Brüchen mit , mit I Indexmenge und , so dass
- für alle gilt.
Da in obiger Bedingung Gleichheit untersagt ist, wird stets die gekürzte Form eines Bruches in eine Farey-Folge aufgenommen.
Beispiele
- .
Konstruktion
Es gibt wenigstens zwei Wege, eine Farey-Folge zu konstruieren.
Methode 1
Bei der ersten Methode sammelt man zunächst alle notwendigen Brüche und sortiert sie anschließend. Für eine Farey-Folge FN werden die beiden Brüche und und alle Brüche gebraucht, deren Nenner q zwischen 2 und N liegen und deren Zähler zwischen 1 und N-1 liegen.
Die Brüche für F8 sind und
- .
Alle möglichen Brüche werden nun soweit wie möglich gekürzt, der Größe nach aufsteigend sortiert, und doppelte Elemente gestrichen:
Methode 2
Die zweite Methode benutzt eine spezielle Form der Addition von Brüchen. Zur Konstruktion der Folge FN muss die vorhergehende Farey-Folge FN − 1 bekannt sein. Man ergänzt dabei die vorhergehende Farey-Folge um Brüche, die man aus einer Operation jeweils nebeneinander liegender Brüche gewinnt, die aber folgende Bedingung erfüllen müssen: Die Summe der Nenner der beiden Brüche muss N ergeben. Die Operation sieht wie folgt aus: Wenn die beiden, nebeneinander liegenden Brüche und sind, und die Summe der beiden Nenner b und d = N ist, dann ist der neue Bruch . Für diese Operation hat sich die Bezeichnung Farey-Addition etabliert. Durch die gemachte Einschränkung gilt für jede Farey-Folge, dass sie Teilmenge der Peirce-Zahlen ist.
Wird angenommen, ist eine rekursive Konstruktion möglich.
Beispiel
Berechnet werden soll F7. F6 wird als bekannt vorausgesetzt, oder selbst erst noch erstellt werden. Mit nebeneinander liegenden Brüchen, deren Nennersumme gleich 7 ist, werden durch Addition von Zähler und Nenner die neuen Elemente gebildet:
Die neuen Elemente sind:
Richtig einsortiert ergibt sich nun
- .
Eigenschaften
Die Mächtigkeit einer Farey-Folge ist gleich der Mächtigkeit der Vorgängerfolge addiert mit dem Eulersche φ-Funktion von N:
Bei zwei aufeinander folgenden Brüchen und einer Farey-Folge ergeben die Produkte a·d und b·c zwei aufeinander folgende Zahlen. Man kann auch schreiben:
Sind umgekehrt und zwei Brüche mit und ad − bc = − 1, so handelt es sich um Nachbarn bis zur Farey-Folge Fc + d − 1, mit anderen Worten: Jeder dazwischen liegende Bruch hat einen Nenner . In der Tat müssen nämlich die Zähler der positiven Brüche und positive ganze Zahlen sein, also und .
Hieraus folgt
- .
Ebenso folgt
- .
Beide Ungleichungen werden scharf genau für die Farey-Summe .
Siehe auch
- Ford-Kreise
- Peirce-Zahlen
- Stern-Brocot-Baum
Literatur
- John H. Conway, Richard K. Guy: The Book of Numbers, ISBN 0-387-97993-X
- Scheid, Frommer: Zahlentheorie. 4. Auflage, Spektrum-Verlag.
Weblinks
Wikimedia Foundation.