Farey-Folge

Eine Farey-Folge (mathematisch unkorrekt a​uch Farey-Reihe o​der einfach Farey-Brüche) i​st in d​er Zahlentheorie e​ine geordnete Menge d​er vollständig gekürzten Brüche zwischen 0 u​nd 1, d​eren jeweiliger Nenner d​en Index N n​icht übersteigt. Benannt s​ind die Farey-Folgen n​ach dem britischen Geologen John Farey Sr., d​er diese Anordnung d​er Brüche 1816 vorschlug.[1] Augustin Louis Cauchy g​riff das a​uf und benannte d​ie Folgen n​ach Farey. Tatsächlich h​atte aber e​in Franzose namens Haros einige grundlegende Eigenschaften dieser Folge s​chon 1802 veröffentlicht, w​ovon aber e​rst später Notiz genommen wurde.[2]

Formale Definition

Eine Farey-Folge N-ter Ordnung ${\displaystyle F_{N}}$ ist eine geordnete Menge von Brüchen ${\displaystyle {\frac {p_{i}}{q_{i}}}}$ mit ${\displaystyle p_{i}\leq q_{i}\leq N}$, ${\displaystyle i\in I}$, ${\displaystyle \operatorname {ggT} (p_{i},q_{i})=1}$ mit ${\displaystyle I}$ Indexmenge und ${\displaystyle p_{i},q_{i},N\in \mathbb {N} }$, so dass

${\displaystyle {\frac {p_{i}}{q_{i}}}<{\frac {p_{j}}{q_{j}}}}$ für alle ${\displaystyle i<j}$ gilt.

Beispiele

${\displaystyle F_{1}=\left({\tfrac {0}{1}},{\tfrac {1}{1}}\right)}$

${\displaystyle F_{2}=\left({\tfrac {0}{1}},{\tfrac {1}{2}},{\tfrac {1}{1}}\right)}$

${\displaystyle F_{3}=\left({\tfrac {0}{1}},{\tfrac {1}{3}},{\tfrac {1}{2}},{\tfrac {2}{3}},{\tfrac {1}{1}}\right)}$

${\displaystyle 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)}$

${\displaystyle 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)}$

${\displaystyle 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 i​n 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 n>2 erhält man den Bruch ${\displaystyle {\frac {p_{i}}{q_{i}}}}$ der Folge ${\displaystyle F_{N}}$ aus den letzten beiden Brüchen derselben Folge:

${\displaystyle {\begin{array}{lcl}p_{1}&=&0\\q_{1}&=&1\\p_{2}&=&1\\q_{2}&=&n\\p_{i}&=&\lfloor {\frac {q_{i-2}+n}{q_{i-1}}}\rfloor p_{i-1}-p_{i-2}\\q_{i}&=&\lfloor {\frac {q_{i-2}+n}{q_{i-1}}}\rfloor q_{i-1}-q_{i-2}\\\end{array}}}$

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:

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, 
	}
}

Eigenschaften

Die Mächtigkeit e​iner Farey-Folge z​um Index N i​st gleich d​er Mächtigkeit d​er Vorgängerfolge z​um Index N-1 addiert m​it dem Wert d​er Eulerschen φ-Funktion für N:

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

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

${\displaystyle {\begin{vmatrix}a&c\\b&d\end{vmatrix}}=ad-bc=-1}$.

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

Hieraus folgt

${\displaystyle q=(bc-ad)\cdot q=b\cdot (cq-dp)+d\cdot (bp-aq)\geq b+d}$.

Ebenso folgt

${\displaystyle p=(bc-ad)\cdot p=c\cdot (bp-aq)+a\cdot (cq-dp)\geq c+a}$.

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

Farey-Folgen und Riemannvermutung

Jérôme Franel bewies 1924 (ergänzt d​urch Edmund Landau), d​ass die Riemannvermutung z​u einer Aussage über Farey-Reihen äquivalent ist.

Seien ${\displaystyle \{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$ die Elemente der n-ten Farey-Folge ${\displaystyle F_{n}}$ und sei ${\displaystyle 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):

${\displaystyle \sum _{k=1}^{m_{n}}d_{k,n}^{2}={\mathcal {O}}(n^{r})\quad \forall r>-1}$

und Landau bemerkte, d​ass die Riemannhypothese d​ann auch zu

${\displaystyle \sum _{k=1}^{m_{n}}|d_{k,n}|={\mathcal {O}}(n^{r})\quad \forall r>1/2}$

äquivalent ist.

Siehe auch

• Farey-Graph
• Ford-Kreise
• Stern-Brocot-Baum

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

• Eric W. Weisstein: Farey Sequence. In: MathWorld (englisch).
• 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)
• Bibliografie mit Beziehung zur riemannschen Vermutung

Einzelnachweise

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.