Farey-Folge

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.<ref>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.</ref> Augustin Louis Cauchy griff das auf und benannte die Folgen nach Farey. Tatsächlich hatte aber ein Franzose namens Haros einige grundlegende Eigenschaften dieser Folge schon 1802 veröffentlicht, wovon aber erst später Notiz genommen wurde.<ref>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.</ref>

Formale Definition

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

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

Beispiele

<math>F_1 = \left( \frac{0}{1}, \frac{1}{1}\right)</math>

<math>F_2 = \left( \frac{0}{1}, \frac{1}{2}, \frac{1}{1}\right)</math>

<math>F_3 = \left( \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}\right)</math>

<math>F_4 = \left( \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}\right)</math>

<math>F_5 = \left( \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1}\right)</math>

<math>F_6 = \left( \frac{0}{1}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{1}{1} \right)</math>.

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

Für gegebenes <math>N>2</math> erhält man den Bruch <math>\frac{p_i}{q_i}</math> der Folge <math>F_N</math> aus den letzten beiden Brüchen derselben Folge:

<math>\begin{array}{lcl} p_1 & = & 0 \\ q_1 & = & 1 \\ p_2 & = & 1 \\ q_2 & = & N \\ p_i & = & \left\lfloor\frac{ q_{i-2}+N}{q_{i-1}}\right\rfloor p_{i-1}-p_{i-2}\\ q_i & = & \left\lfloor\frac{ q_{i-2}+N}{q_{i-1}}\right\rfloor q_{i-1}-q_{i-2}\\ \end{array}</math>

Dabei bedeuten die unten eckigen Klammern ein Abrunden. Mit Integer-Arithmetik wird bei Division implizit abgerundet, so dass man beispielsweise in Java die Berechnung ohne explizites Abrunden programmieren kann:<syntaxhighlight lang="java"> public class FareySequence { @FunctionalInterface public static interface BiIntConsumer { void accept(int p, int q); } public static void forEach(int n, BiIntConsumer consumer) { int p__ = 0; // p_{i-2} = p_1 int q__ = 1; // q_{i-2} = q_1 int p_ = 1; // p_{i-1} = p_2 int q_ = n; // q_{i-1} = q_2 consumer.accept(p__, q__); consumer.accept(p_, q_); while ((q_ != 1)) { int p = ((q__ + n) / q_) * p_ - p__; int q = ((q__ + n) / q_) * q_ - q__; p__ = p_; p_ = p; q__ = q_; q_ = q; consumer.accept(p, q); } }

// Beispiel Verwendung: public static void main(String[] args) { FareySequence.forEach(8,(p, q) -> System.out.print(p + "/" + q+", ")); // Ausgabe: 0/1, 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/1, } } </syntaxhighlight>

Eigenschaften

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:

<math>|F_N| = |F_{N-1}| + \varphi(N)</math>.

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

<math>\begin{vmatrix} a & c \\ b & d \end{vmatrix} = a d - b c = -1</math>.

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

Hieraus folgt

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

Ebenso folgt

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

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

Farey-Folgen und Riemannvermutung

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

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

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

und Landau bemerkte, dass die Riemannhypothese dann auch zu

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

äquivalent ist.

Siehe auch

Literatur

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

{{#if: | {{{author}}} | Eric W. Weisstein }}: Farey Sequence. In: MathWorld (englisch). {{#if: FareySequence | {{#ifeq: {{#property:P2812}} | FareySequence | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}
Farey Series auf cut-the-knot
Skript zu Fibonacci-Zahlen, Kettenbrüchen und Farey-Folgen (PDF; 1,22 MB)
Horst Hischer: 4000 Jahre Mittelwertbildung (PDF; 4,23 MB)
Farey-Reihen in der Encyclopedia of Mathematics (Springer)
<templatestyles src="Webarchiv/styles.css" />{{#if:

      | {{#ifeq: {{{wayback}}} | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Bibliografie mit Beziehung zur riemannschen Vermutung | {{#invoke:WLink|getEscapedTitle|Bibliografie mit Beziehung zur riemannschen Vermutung}} | {{#invoke:Webarchiv|getdomain|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|{{{wayback}}}}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Bibliografie mit Beziehung zur riemannschen Vermutung | {{#invoke:WLink|getEscapedTitle|Bibliografie mit Beziehung zur riemannschen Vermutung}} | {{#invoke:Webarchiv|getdomain|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|{{{wayback}}}}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Bibliografie mit Beziehung zur riemannschen Vermutung | {{#invoke:WLink|getEscapedTitle|Bibliografie mit Beziehung zur riemannschen Vermutung}} | {{#invoke:Webarchiv|getdomain|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Bibliografie mit Beziehung zur riemannschen Vermutung | {{#invoke:WLink|getEscapedTitle|Bibliografie mit Beziehung zur riemannschen Vermutung}} | {{#invoke:Webarchiv|getdomain|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Bibliografie mit Beziehung zur riemannschen Vermutung | {{#invoke:WLink|getEscapedTitle|Bibliografie mit Beziehung zur riemannschen Vermutung}} | {{#invoke:Webarchiv|getdomain|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 20121218091153
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Bibliografie mit Beziehung zur riemannschen Vermutung | {{#invoke:WLink|getEscapedTitle|Bibliografie mit Beziehung zur riemannschen Vermutung}} | {{#invoke:Webarchiv|getdomain|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:20121218091153|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: Bibliografie mit Beziehung zur riemannschen Vermutung
    | {{#if: {{#invoke:WLink|isBracketedLink|Bibliografie mit Beziehung zur riemannschen Vermutung}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.math.jussieu.fr/~miw/telecom/biblio-Amoroso.html }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

Einzelnachweise