Farey-rij

In de wiskunde is de Farey-rij van orde n de rij 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 een dergelijke 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 ⁰/₁ en eindigt met de waarde 1, aangeduid door de fractie ¹/₁ (hoewel sommige auteurs deze begin- en eindterm weglaten).

Voorbeelden

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

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

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

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

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

${\displaystyle F_{5}=({\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}})}$

Inderdaad geldt bijvoorbeeld in ${\displaystyle F_{5}}$:

${\displaystyle {\frac {2}{5}}}$ is gelegen tussen ${\displaystyle {\frac {1}{3}}}$ en ${\displaystyle {\frac {1}{2}}}$, en ${\displaystyle {\frac {2}{5}}={\frac {1+1}{3+2}}}$

Analoog:

${\displaystyle {\frac {2}{3}}={\frac {3+3}{5+4}}}$

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 ${\displaystyle {\frac {3n^{2}}{\pi ^{2}}}}$.

Farey-afstand

De Farey-afstand tussen twee breuken ${\displaystyle r_{1}={\frac {a_{1}}{b_{1}}},r_{2}={\frac {a_{2}}{b_{2}}}}$ is:

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

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 F₁ tot F₅.

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

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

${\displaystyle 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}+_{\ddots {\cfrac {1}{a_{n}}}}}}}}}$

De getallen ${\displaystyle x_{1},\dots x_{n},a_{1},\dots a_{n}}$ zijn te bepalen als volgt:

• ${\displaystyle a_{1}=\left\lfloor {\frac {1}{x_{0}}}\right\rfloor }$
• ${\displaystyle x_{1}={\frac {1}{x_{0}}}-a_{1}}$
• doe voor ${\displaystyle k=1,2,...}$
  • ${\displaystyle a_{k+1}=\left\lfloor {\frac {1}{x_{k}}}\right\rfloor }$
  • ${\displaystyle x_{k+1}={\frac {1}{x_{k}}}-a_{k+1}}$ en stop wanneer ${\displaystyle x_{k+1}=0}$

Wanneer de opeenvolgende ${\displaystyle x_{k}}$ weggelaten worden, krijgt men een rij breuken die opeenvolgende benaderingen zijn van ${\displaystyle x_{0}}$:

${\displaystyle \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 ${\displaystyle \alpha _{k+1}-\alpha _{k}}$ verandert steeds van teken. De opeenvolgende breuken ${\displaystyle \alpha _{k}}$ zijn met andere woorden afwisselend een overschatting en onderschatting van ${\displaystyle x_{0}=\alpha _{n}}$.

De getallen ${\displaystyle x_{1},x_{2},...x_{n}}$ worden gegenereerd door de afbeelding ${\displaystyle g:x\mapsto \{1/x\}}$, te beginnen bij ${\displaystyle x_{0}}$, waarbij ${\displaystyle \{y\}=y-\lfloor y\rfloor }$ het fractionele deel van een getal is.

Wanneer ${\displaystyle x_{0}}$ een irrationaal getal tussen 0 en 1 is, is de rij ${\displaystyle \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 ${\displaystyle x_{0}}$ en benadert steeds dichter dat getal.

Voorbeeld

Als ${\displaystyle x_{0}=3/5}$ verkrijgen we achtereenvolgens:

• ${\displaystyle a_{1}=\lfloor 5/3\rfloor =1}$
• ${\displaystyle \alpha _{1}=1}$
• ${\displaystyle x_{1}=5/3-1=2/3}$
• ${\displaystyle a_{2}=\lfloor 3/2\rfloor =1}$
• ${\displaystyle \alpha _{2}={\cfrac {1}{1+{\cfrac {1}{1}}}}=1/2}$
• ${\displaystyle x_{2}=3/2-1=1/2}$
• ${\displaystyle a_{3}=\lfloor 2/1\rfloor =2}$
• ${\displaystyle x_{3}=2/1-2=0}$

Dus

${\displaystyle x_{0}=\alpha _{3}={\frac {3}{5}}={\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{2}}}}}}}$

Het pad dat leidt naar ${\displaystyle x_{0}}$ is ${\displaystyle 1,{\frac {1}{2}},{\frac {3}{5}}.}$

Toepassingen

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

• (de) Bodo Werner. "Fibonacci-getallen, gulden snede, kettingbreuken en toepassingen"
• (en) Rich Schwartz. Cursusnota over kettingbreuken en de Farey-graaf