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] Tatsächlich hatte aber ein französischer Mathematiker namens Haros einige grundlegende Eigenschaften dieser Folge schon 1802 veröffentlicht, wovon aber erst später Notiz genommen wurde.[2]

Formale Definition[Bearbeiten]

Eine Farey-Folge N-ter Ordnung F_N ist eine geordnete Menge von Brüchen \frac{p_i}{q_i} mit p_i \leq q_i \leq N, i \in I, \operatorname{ggT}(p_i, q_i)=1 mit I Indexmenge und p_i, q_i, N \in \N, so dass

\frac{p_i}{q_i} < \frac{p_j}{q_j} für alle i < j gilt.

Beispiele[Bearbeiten]

F_1 = \left( \tfrac{0}{1}, \tfrac{1}{1}\right)
F_2 = \left( \tfrac{0}{1}, \tfrac{1}{2}, \tfrac{1}{1}\right)
F_3 = \left( \tfrac{0}{1}, \tfrac{1}{3}, \tfrac{1}{2}, \tfrac{2}{3}, \tfrac{1}{1}\right)
F_4 = \left( \tfrac{0}{1}, \tfrac{1}{4}, \tfrac{1}{3}, \tfrac{1}{2}, \tfrac{2}{3}, \tfrac{3}{4}, \tfrac{1}{1}\right)
F_5 = \left( \tfrac{0}{1}, \tfrac{1}{5}, \tfrac{1}{4}, \tfrac{1}{3}, \tfrac{2}{5}, \tfrac{1}{2}, \tfrac{3}{5}, \tfrac{2}{3}, \tfrac{3}{4},  \tfrac{4}{5}, \tfrac{1}{1}\right)
F_6 = \left( \tfrac{0}{1}, \tfrac{1}{6}, \tfrac{1}{5}, \tfrac{1}{4}, \tfrac{1}{3}, \tfrac{2}{5}, \tfrac{1}{2}, \tfrac{3}{5}, \tfrac{2}{3}, \tfrac{3}{4}, \tfrac{4}{5}, \tfrac{5}{6}, \tfrac{1}{1} \right).


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]

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

Methode 1[Bearbeiten]

Bei der ersten Methode sammelt man zunächst alle notwendigen Brüche und sortiert sie anschließend. Für eine Farey-Folge F_N werden die beiden Brüche \tfrac{0}{1} und \tfrac{1}{1} 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 \{\tfrac{0}{1}, \tfrac{1}{1}\} und

q = 2 : \{\tfrac{1}{2}\}
q = 3 : \{\tfrac{1}{3}, \tfrac{2}{3}\}
q = 4 : \{\tfrac{1}{4}, \tfrac{2}{4}, \tfrac{3}{4}\}
q = 5 : \{\tfrac{1}{5}, \tfrac{2}{5}, \tfrac{3}{5}, \tfrac{4}{5}\}
q = 6 : \{\tfrac{1}{6}, \tfrac{2}{6}, \tfrac{3}{6}, \tfrac{4}{6}, \tfrac{5}{6}\}
q = 7 : \{\tfrac{1}{7}, \tfrac{2}{7}, \tfrac{3}{7}, \tfrac{4}{7}, \tfrac{5}{7}, \tfrac{6}{7}\}
q = 8 : \{\tfrac{1}{8}, \tfrac{2}{8}, \tfrac{3}{8}, \tfrac{4}{8}, \tfrac{5}{8}, \tfrac{6}{8}, \tfrac{7}{8}\}.

Alle möglichen Brüche werden nun so weit wie möglich gekürzt, der Größe nach aufsteigend sortiert, und doppelte Elemente gestrichen:

F_8 = \left( \tfrac{0}{1}, \tfrac{1}{8}, \tfrac{1}{7}, \tfrac{1}{6}, \tfrac{1}{5}, \tfrac{1}{4}, \tfrac{2}{7}, \tfrac{1}{3}, \tfrac{3}{8}, \tfrac{2}{5}, \tfrac{3}{7}, \tfrac{1}{2}, \tfrac{4}{7}, \tfrac{3}{5}, \tfrac{5}{8}, \tfrac{2}{3}, \tfrac{5}{7}, \tfrac{3}{4}, \tfrac{4}{5}, \tfrac{5}{6}, \tfrac{6}{7}, \tfrac{7}{8}, \tfrac{1}{1} \right)

Methode 2[Bearbeiten]

Die zweite Methode benutzt eine spezielle Form der Addition von Brüchen. Zur Konstruktion der Folge F_N muss die vorhergehende Farey-Folge F_{N-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 \tfrac{a}{b} und \tfrac{c}{d} sind, und die Summe der beiden Nenner b und d = N ist, dann ist der neue Bruch \tfrac{a+c}{b+d}. Für diese Operation hat sich die Bezeichnung Farey-Addition etabliert. Durch die gemachte Einschränkung (b+d) \le N gilt für jede Farey-Folge, dass sie Teilmenge der Peirce-Zahlen  \mathbb V_N \ ist.

Wird F_1 = \left( \tfrac{0}{1}, \tfrac{1}{1}\right) angenommen, ist eine rekursive Konstruktion möglich.

Beispiel[Bearbeiten]

Berechnet werden soll F_7. F_6 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:

F_6 = ( \underbrace{ \frac{0}{1}, \frac{1}{6}}_{\frac{1}{7}}, \frac{1}{5}, \underbrace{\frac{1}{4}, \frac{1}{3}}_{\frac{2}{7}}, \underbrace{\frac{2}{5}, \frac{1}{2}, \frac{3}{5}}_{\frac{3}{7}\ \mathrm{und}\ \frac{4}{7}}, \underbrace{\frac{2}{3}, \frac{3}{4}}_{\frac{5}{7}}, \frac{4}{5}, \underbrace{\frac{5}{6}, \frac{1}{1}}_{\frac{6}{7}} )

Die neuen Elemente sind:

\tfrac{0+1}{1+6} = \tfrac{1}{7} \ \ ; \ \ \tfrac{1+1}{4+3} = \tfrac{2}{7} \ \ ; \ \ \ \tfrac{2+1}{5+2} = \tfrac{3}{7} \ \ ; \ \ \tfrac{1+3}{2+5} = \tfrac{4}{7} \ \ ; \ \ \tfrac{2+3}{3+4} = \tfrac{5}{7} \ \ ; \ \ \tfrac{5+1}{6+1} = \tfrac{6}{7}

Richtig einsortiert ergibt sich nun

F_7 = \left( \tfrac{0}{1}, \boldsymbol \tfrac{1}{7}, \tfrac{1}{6}, \tfrac{1}{5}, \tfrac{1}{4}, \boldsymbol \tfrac{2}{7}, \tfrac{1}{3}, \tfrac{2}{5}, \boldsymbol \tfrac{3}{7}, \tfrac{1}{2}, \boldsymbol \tfrac{4}{7}, \tfrac{3}{5}, \tfrac{2}{3}, \boldsymbol \tfrac{5}{7} \ \tfrac{3}{4}, \tfrac{4}{5}, \tfrac{5}{6}, \boldsymbol \tfrac{6}{7}, \tfrac{1}{1} \right) .

Eigenschaften[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:

|F_N| = |F_{N-1}| + \varphi(N).

Bei zwei aufeinander folgenden Brüchen \tfrac{a}{c} und \tfrac{b}{d} einer Farey-Folge ergeben die Produkte a·d und b·c zwei aufeinander folgende Zahlen. Man kann auch schreiben:

\begin{vmatrix} a & b \\ c & d \end{vmatrix} = a d - b c = -1.

Sind umgekehrt \tfrac ac und \tfrac b d zwei Brüche mit 0\le\tfrac{a}{c} < \tfrac {b}{d} \le 1 und ad - bc=-1, so handelt es sich um Nachbarn bis zur Farey-Folge F_{c+d-1}, mit anderen Worten: Jeder dazwischen liegende Bruch \tfrac {p}{q} hat einen Nenner q \ge c+d. In der Tat müssen nämlich die Zähler der positiven Brüche \tfrac{p}{q} - \tfrac{a}{b} = \tfrac{bp - aq}{qb} und \tfrac{c}{d}-\tfrac{p}{q} = \tfrac{cq - dp}{dq} positive ganze Zahlen sein, also bp - aq \ge 1 und cq - dp \ge 1.

Hieraus folgt

q = (bc-ad) \cdot q = b \cdot (cq-dp) + d \cdot (bp-aq) \ge b+d.

Ebenso folgt

p = (bc-ad) \cdot p = c \cdot (bp-aq) + a \cdot (cq-dp) \ge c+a.

Beide Ungleichungen werden scharf genau für die Farey-Summe \tfrac{p}{q} = \tfrac{a+c}{b+d}.

Farey-Folgen und Riemannvermutung[Bearbeiten]

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

Seien \{a_{k,n} : k = 0, 1, \ldots, m_n\} die Elemente der n-ten Farey-Folge F_n und sei d_{k,n} = a_{k,n} - k/m_n 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):

\sum_{k=1}^{m_n} d_{k,n}^2 = \mathcal{O}(n^r)\quad\forall r>-1

und Landau bemerkte, dass die Riemannhypothese dann auch zu

\sum_{k=1}^{m_n} |d_{k,n}| = \mathcal{O} (n^r)\quad\forall r>1/2

äquivalent ist.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[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.