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.

Farey-diagram van F5.

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).

VoorbeeldenBewerken

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

 
 
 
 
 

Inderdaad geldt bijvoorbeeld in  :

  is gelegen tussen   en  , en  

Analoog:

 

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  .

Farey-afstandBewerken

De Farey-afstand tussen twee breuken   is:

 

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  

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

Farey-graafBewerken

 
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:  ; 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 kettingbreukenBewerken

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

 

De getallen   zijn te bepalen als volgt:

  •  
  •  
  • doe voor  
    •  
    •   en stop wanneer  

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

 

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   verandert steeds van teken. De opeenvolgende breuken   zijn met andere woorden afwisselend een overschatting en onderschatting van  .

De getallen   worden gegenereerd door de afbeelding  , te beginnen bij  , waarbij   het fractionele deel van een getal is.

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

VoorbeeldBewerken

Als   verkrijgen we achtereenvolgens:

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Dus

 

Het pad dat leidt naar   is  

ToepassingenBewerken

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 linksBewerken