Farey episode

A Farey- sequence (mathematically inaccurate also Farey- series or simply Farey fractions ) is in the number theory an ordered quantity of the fully shortened fractions between 0 and 1, the respective denominator does not exceed the index n. The Farey Sequences are named after the British geologist John Farey Sr., who proposed this arrangement of the fractures in 1816. Augustin Louis Cauchy took up this and named the consequences after Farey. In fact, a Frenchman named Haros had published some of the basic properties of this series as early as 1802, but this was only noticed later.

Formal definition

A Farey sequence N th order is an ordered set of fractures with , , with index set and so that ${\displaystyle F_{N}}$ ${\displaystyle {\frac {p_{i}}{q_{i}}}}$ ${\displaystyle p_{i}\leq q_{i}\leq N}$ ${\displaystyle i\in I}$ ${\displaystyle \operatorname {ggT} (p_{i},q_{i})=1}$ ${\displaystyle I}$ ${\displaystyle p_{i},q_{i},N\in \mathbb {N} }$

${\displaystyle {\frac {p_{i}}{q_{i}}}<{\frac {p_{j}}{q_{j}}}}$applies to all . ${\displaystyle i<j}$

Examples

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

The first 8 episodes in a structured presentation:

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}

construction

For a given n> 2 we get the fraction of the sequence from the last two fractions of the same sequence: ${\displaystyle {\frac {p_{i}}{q_{i}}}}$ ${\displaystyle F_{N}}$

${\displaystyle {\begin{array}{lcl}p_{1}&=&0\\q_{1}&=&1\\p_{2}&=&1\\p_{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}}}$

The square brackets below mean rounding off. With integer arithmetic, division is implicitly rounded down so that, for example, the calculation in Java can be programmed without explicit rounding off:

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

properties

The cardinality of a Farey sequence with index N is equal to the cardinality of the previous sequence with index N-1 added with the value of Euler's φ-function for N:

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

With two consecutive fractions and a Farey sequence, the products a · d and b · c result in two consecutive numbers. One can also write: ${\displaystyle {\tfrac {a}{b}}}$ ${\displaystyle {\tfrac {c}{d}}}$

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

If reversed and are two fractions with and , then we are dealing with neighbors up to the Farey sequence , in other words: every fraction in between has a denominator . In fact, namely the counter of positive breakthroughs must and positive integers be so and . ${\displaystyle {\tfrac {a}{b}}}$ ${\displaystyle {\tfrac {c}{d}}}$ ${\displaystyle 0\leq {\tfrac {a}{b}}<{\tfrac {c}{d}}\leq 1}$ ${\displaystyle ad-bc=-1}$ ${\displaystyle F_{b+d-1}}$ ${\displaystyle {\tfrac {p}{q}}}$ ${\displaystyle q\geq b+d}$ ${\displaystyle {\tfrac {p}{q}}-{\tfrac {a}{b}}={\tfrac {bp-aq}{qb}}}$ ${\displaystyle {\tfrac {c}{d}}-{\tfrac {p}{q}}={\tfrac {cq-dp}{dq}}}$ ${\displaystyle bp-aq\geq 1}$ ${\displaystyle cq-dp\geq 1}$

It follows from this

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

Likewise follows

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

Both inequalities become sharply exact for the Farey sum . ${\displaystyle {\tfrac {p}{q}}={\tfrac {a+c}{b+d}}}$

Farey consequences and the Riemann assumption

Jérôme Franel proved in 1924 (supplemented by Edmund Landau ) that the Riemann conjecture is equivalent to a statement about Farey series.

Let be the elements of the nth Farey sequence and be the distance between the kth term of the nth Farey sequence and the kth term of the equidistant point series in the unit interval with the same number of terms as the nth Farey sequence. Franel then proved the equivalence of the Riemann hypothesis to (the Landau symbols are used ): ${\displaystyle \{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$ ${\displaystyle F_{n}}$ ${\displaystyle d_{k,n}=a_{k,n}-k/m_{n}}$

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

and Landau remarked that the Riemann hypothesis then too

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

is equivalent.

See also

• Farey graph
• Ford circles
• Star Brocot Tree

literature

• 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 , Volume 1 (Divisibility and Primality). Carnegie Institution, Washington 1919, pp. 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, No. 3, pp. 283-294.
• Harald Scheid , Andreas Frommer : Number theory. 4th edition. Springer Spectrum, Heidelberg; [u. a.] 2006, ISBN 978-3-8274-1692-6 .

Web links

• Eric W. Weisstein : Farey Sequence . In: MathWorld (English).
• Farey Series on cut-the-knot
• Script on Fibonacci numbers, continued fractions and Farey sequences (PDF; 1.22 MB)
• Horst Hischer: 4000 years of averaging (PDF; 4.23 MB)
• Farey series in the Encyclopedia of Mathematics (Springer)
• Bibliography related to the Riemann Hypothesis

Individual evidence

1. ^ John Farey: On a Curious Property of Vulgar Fractions. In: The Philosophical Magazine and Journal , 47, 1816, pp. 385-386, No. LXXIX. See SA: On Vulgar Fractions. In: The Philosophical Magazine and Journal , 48, 1816, p. 204, No. XLIII.
2. ↑ C. [itoy] en [= citizen] Haros: Tables pour évaluer une fraction ordinaire avec autant de decimales 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, No. 11, pp. 364–368.