Farey-rij

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Farey-diagram van F5.

In de wiskunde is de Farey-rij van orde n de rij van breuken tussen 0 en 1, die in volledig gereduceerde vorm een noemer hebben die kleiner dan of gelijk is aan n. De elementen in de Farey-rij zijn gerangschikt in volgorde van toenemende grootte. De rij is vernoemd naar de Britse geoloog John Farey. Hij merkte in een kort artikel uit 1816 het volgende op:[1] elke breuk in zo een rij is gelijk aan de breuk met als teller de som van de tellers en als noemer de som van de noemers van de twee breuken aan weerszijden ervan, eventueel na vereenvoudiging.

Elke Farey-rij begint met de waarde 0, aangeduid door de fractie 0/1 en eindigt met de waarde 1, aangeduid door de fractie 1/1 (hoewel sommige auteurs deze begin- en eindterm weglaten).

Voorbeelden[bewerken]

De Farey-rijen van de orden 1 tot 5 zijn :

 F_{1} = \left \{ \frac{0}{1} \ ; \ \frac{1}{1} \right \}
 F_{2} = \left \{ \frac{0}{1} \ ; \ \frac{1}{2} \ ; \ \frac{1}{1} \right \}
 F_{3} = \left \{ \frac{0}{1} \ ; \ \frac{1}{3} \ ; \ \frac{1}{2} \ ; \ \frac{2}{3} \ ; \ \frac{1}{1}\right \}
 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 \}
 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 \}

Bijvoorbeeld in F_5 : \frac{2}{5} = \frac {1+1}{3+2}, \frac {2}{3} = \frac {3+3}{5+4} = \frac{6}{9}, enzovoort.

Het aantal breuken in de Farey-rijen van orde 0, 1, 2, 3, 4, ... is 1, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43, 47, 59, 65, 73, ... (rij A005728 in OEIS). De lengte van de Farey-rijen van orde n nadert asymptotisch tot \frac{3n^2}{\pi^2}.

Farey-afstand[bewerken]

De Farey-afstand tussen twee breuken  r_1 = \frac{a_1}{b_1}, r_2 = \frac{a_2}{b_2} is:

d = | a_1 b_2 - a_2 b_1 |

Twee breuken zijn Farey-gerelateerd als hun Farey-afstand d gelijk is aan 1; dit is bijvoorbeeld het geval voor de paren 1/3 en 2/7 of 2/7 en 7/24. d is de determinant van de matrix  \left( \begin{matrix}
a_1 & a_2 \\
b_1 & b_2
\end{matrix} \right)

Twee opeenvolgende breuken in een Farey-rij zijn altijd Farey-gerelateerd. Deze relatie kan grafisch voorgesteld worden in de zogenaamde Farey-graaf.

Farey-graaf[bewerken]

Gedeelte van de Farey-graaf in het hyperbolische halfvlak

De Farey-graaf is een oneindig grote graaf met als knopenverzameling de verzameling van volledig gereduceerde rationale getallen plus oneindig (d.i. de breuk 1/0). Twee knopen zijn verbonden door een kant wanneer ze Farey-gerelateerd zijn, dus wanneer hun Farey-afstand gelijk is aan 1.

De Farey-graaf wordt vaak afgebeeld in het hyperbolische halfvlak, waarbij de rationale getallen op een rechte lijn staan en de kanten voorgesteld worden als geodetische krommen. De figuur hiernaast stelt het deel van de Farey-graaf voor dat correspondeert met de Farey-rijen F1 tot F5.

Twee opeenvolgende breuken in een Farey-rij zijn verbonden in de Farey-graaf. Elke Farey-rij vormt bijgevolg een cykel in de Farey-graaf.

Elke kant in de Farey-graaf behoort tot een 3-cykel. Met andere woorden: de Fareygraaf is een triangulatie. De knopen die een 3-cykel vormen hebben steeds de waarden:   \frac{a_1}{b_1},  \frac{(a_1 + a_2)}{(b_1 + b_2)},  \frac{a_2}{b_2}; bijvoorbeeld 0/1, 1/4 en 1/5 of 1/3, 1/2 en 2/5; dit is de eigenschap die Farey in zijn artikel aan het licht bracht.

Farey-graaf en kettingbreuken[bewerken]

Er is een verband tussen kettingbreuken en de Farey-graaf, een object uit de hyperbolische meetkunde. Elke echte breuk x_0 tussen 0 en 1 kan men schrijven als een eindige kettingbreuk die men iteratief kan bepalen:

x_0 = \frac{1}{a_1 + x_1} = \cfrac 1{a_1 + \cfrac 1{a_2 + x_2}} = \dots = \cfrac 1{a_1+\cfrac 1{a_2+\cdots \cfrac 1{a_n}}}

De getallen x_1, \dots x_n, a_1, \dots a_n zijn te bepalen als volgt:

  • a_1 = \lfloor \frac{1}{x_0} \rfloor
  •  x_1 = \frac{1}{x_0} - a_1
  • doe voor k = 1, 2, ...
    •  a_{k+1} = \lfloor \frac{1}{x_k} \rfloor
    • x_{k+1} =  \frac{1}{x_k} - a_{k+1} en stop wanneer x_{k+1} = 0

Wanneer de opeenvolgende x_k weggelaten worden, krijgt men een rij breuken die opeenvolgende benaderingen zijn van x_0:

 \alpha_1 = \cfrac 1{a_1} \ , \alpha_2 =  \cfrac 1{a_1 + \cfrac 1{a_2}}, \dots \alpha_n = x_0

Tussen deze convergenten loopt een pad in de Farey-graaf: de Farey-afstand tussen twee opeenvolgende getallen in de rij is steeds 1. In de "hyperbolische" voorstelling van de graaf is het een zigzagpad: het verschil \alpha_{k+1} - \alpha_k verandert steeds van teken. De opeenvolgende breuken \alpha_k zijn met andere woorden afwisselend een overschatting en onderschatting van x_0 = \alpha_n.

De getallen x_1, x_2, ... x_n worden gegenereerd door de afbeelding  g: x \mapsto \{1/x\} , te beginnen bij x_0, waarbij \{y\} = y -\lfloor y\rfloor het fractionele deel van een getal is.

Wanneer x_0 een irrationaal getal tussen 0 en 1 is, is de rij  \alpha_1, \alpha_2, \dots oneindig lang; het verschil tussen twee opeenvolgende breuken in die rij wordt steeds kleiner en in de limiet wordt het nul. Het corresponderende oneindige pad in de Farey-graaf zigzagt eeuwig heen en weer rond x_0 en benadert steeds dichter dat getal.

Voorbeeld[bewerken]

Als x_0 =3/5 verkrijgen we achtereenvolgens:

  • a_1 =  \lfloor 3/5 \rfloor = 1
  • \alpha_1 = 1
  • x_1 = 5/3 - 1 = 2/3
  • a_2 =  \lfloor 3/2 \rfloor = 1
  • \alpha_2 = 1 + \cfrac 1{1} = 1/2
  • x_2 = 3/2 - 1 = 1/2
  • a_3 =  \lfloor 2/1 \rfloor = 2
  • x_3 = 2/1 - 2 = 0

Dus

x_0 = \alpha_3 = \frac{3}{5} = \cfrac 1{1+\cfrac 1{1+ \cfrac 1{2}}}

Het pad dat leidt naar x_0 is  1, \frac{1}{2}, \frac{3}{5}.

Toepassingen[bewerken]

Farey-rijen en de Farey-graaf zijn het onderwerp van talrijke publicaties op zowel theoretisch als toegepast vlak. Zo zijn Farey-rijen onder meer gebruikt voor het genereren van pseudo-toevalsgetallen[2], of voor het bepalen van de boven- en ondergrens van de equivalente weerstand van een schakeling van n gelijke weerstanden in een willekeurige combinatie.[3]

Externe links[bewerken]

Bronnen, noten en/of referenties
  1. J. Farey. "On a curious Property of vulgar Fractions." Philosophical Magazine (1816), vol. 17 nr. 217, blz. 385-386. DOI:10.1080/14786441608628487
  2. Bozhidar Doynov, Chavdar Alexandrov. "Generation of pseudorandom numbers with very long period based on Farey sequences." Journal of Marine Technology and Environment (2011), vol. 2, blz. 25-30.
  3. Sameen Khan. "Farey sequences and resistor networks." Proceedings of the Indian Academy of Sciences: Mathematical Sciences (2012), vol. 122 nr. 2, blz. 153-162. DOI:10.1007/s12044-012-0066-7