Farey-Folge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine Farey-Folge (mathematisch unkorrekt auch Farey-Reihe oder einfach Farey-Brüche) ist in der Zahlentheorie eine geordnete Menge der vollständig gekü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 Sr., der diese Anordnung der Brüche 1816 vorschlug.[1] Augustin Louis Cauchy griff das auf und benannte die Folgen nach Farey. Tatsächlich hatte aber ein französischer Mathematiker namens Charles Haros einige grundlegende Eigenschaften dieser Folge schon 1802 veröffentlicht, wovon aber erst später Notiz genommen wurde.[2]

Formale Definition[Bearbeiten | Quelltext bearbeiten]

Eine Farey-Folge N-ter Ordnung ist eine geordnete Menge von Brüchen mit , , mit Indexmenge und , so dass

für alle gilt.

Beispiele[Bearbeiten | Quelltext bearbeiten]

.

Die ersten 8 Folgen in einer strukturierten Darstellung:

F1 = {0   ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·   1}
F2 = {0   ·    ·    ·    ·    ·    ·    ·    ·    ·    ·   1/2   ·    ·    ·    ·    ·    ·    ·    ·    ·    ·   1}
F3 = {0   ·    ·    ·    ·    ·    ·   1/3   ·    ·    ·   1/2   ·    ·    ·   2/3   ·    ·    ·    ·    ·    ·   1}
F4 = {0   ·    ·    ·    ·   1/4   ·   1/3   ·    ·    ·   1/2   ·    ·    ·   2/3   ·   3/4   ·    ·    ·    ·   1}
F5 = {0   ·    ·    ·   1/5  1/4   ·   1/3   ·   2/5   ·   1/2   ·   3/5   ·   2/3   ·   3/4  4/5   ·    ·    ·   1}
F6 = {0   ·    ·   1/6  1/5  1/4   ·   1/3   ·   2/5   ·   1/2   ·   3/5   ·   2/3   ·   3/4  4/5  5/6   ·    ·   1}
F7 = {0   ·   1/7  1/6  1/5  1/4  2/7  1/3   ·   2/5  3/7  1/2  4/7  3/5   ·   2/3  5/7  3/4  4/5  5/6  6/7   ·   1}
F8 = {0  1/8  1/7  1/6  1/5  1/4  2/7  1/3  3/8  2/5  3/7  1/2  4/7  3/5  5/8  2/3  5/7  3/4  4/5  5/6  6/7  7/8  1}

Konstruktion[Bearbeiten | Quelltext bearbeiten]

Es gibt wenigstens zwei Wege, eine Farey-Folge zu konstruieren.

Methode 1[Bearbeiten | Quelltext bearbeiten]

Bei der ersten Methode sammelt man zunächst alle notwendigen Brüche und sortiert sie anschließend. Für eine Farey-Folge 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 so weit wie möglich gekürzt, der Größe nach aufsteigend sortiert, und doppelte Elemente gestrichen:

Methode 2[Bearbeiten | Quelltext bearbeiten]

Die zweite Methode benutzt eine spezielle Form der Addition von Brüchen. Zur Konstruktion der Folge muss die vorhergehende Farey-Folge 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.

Wird angenommen, ist eine rekursive Konstruktion möglich.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Berechnet werden soll . 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[Bearbeiten | Quelltext bearbeiten]

Die Mächtigkeit einer Farey-Folge zum Index N ist gleich der Mächtigkeit der Vorgängerfolge zum Index N-1 addiert mit dem Wert der Eulerschen φ-Funktion für 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 , so handelt es sich um Nachbarn bis zur Farey-Folge , 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 .

Farey-Folgen und Riemannvermutung[Bearbeiten | Quelltext bearbeiten]

Jérôme Franel bewies 1924 (ergänzt durch Edmund Landau), dass die Riemannvermutung zu einer Aussage über Farey-Reihen äquivalent ist.

Seien die Elemente der n-ten Farey-Folge und sei der Abstand zwischen dem k-ten Term der n-ten Fareyfolge und dem k-ten Term der äquidistanten Punktreihe im Einheitsintervall mit derselben Anzahl von Termen wie die n-te Fareyfolge. Franel bewies dann die Äquivalenz der Riemannhypothese zu (verwendet werden die Landau-Symbole):

und Landau bemerkte, dass die Riemannhypothese dann auch zu

äquivalent ist.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • John H. Conway, Richard K. Guy: The Book of Numbers. Copernicus Books, New York 1996, ISBN 0-387-97993-X.
  • Leonard Eugene Dickson: Farey Series. In: History of the Theory of Numbers, Band 1 (Divisibility and Primality). Carnegie Institution, Washington 1919, S. 155–158.
  • Jeffrey Lagarias, Charles Tresser: A walk along the branches of the extended Farey tree. In: IBM Journal of Research and Development, 39, 1995, Nr. 3, S. 283–294.
  • Harald Scheid; Andreas Frommer: Zahlentheorie. 4. Auflage. Springer Spektrum, Heidelberg; [u. a.] 2006, ISBN 978-3-8274-1692-6.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. John Farey: On a curious Property of vulgar Fractions. In: The Philosophical Magazine and Journal, 47, 1816, S. 385–386, Nr. LXXIX. Vgl. S. A.: On Vulgar Fractions. In: The Philosophical Magazine and Journal, 48, 1816, S. 204, Nr. XLIII.
  2. C.[itoy]en [= Bürger] Haros: Tables pour évaluer une fraction ordinaire avec autant de décimales qu'on voudra; et pour trouver la fraction ordinaire la plus simple, et qui approche sensiblement d’une fraction décimale. In: Journal de l’école polytechnique, 4, 1802, Nr. 11, S. 364–368.