Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Suite de Farey

En mathématiques, la suite de Farey d'ordre n est la suite des fractions irréductibles entre 0 et 1 dont le dénominateur est inférieur ou égal à n et en ordre croissant.

Chaque suite de Farey commence avec la valeur 0, décrite par la fraction ⁰⁄₁, et finit avec la valeur 1, décrite par la fraction ¹⁄₁ (bien que certains auteurs omettent ces termes).

Une suite de Farey est quelquefois appelée série de Farey, ce qui n'est pas véritablement correct, les termes n'étant pas additionnés.

Exemples

Les suites de Farey d'ordre 1 à 8 sont :

F₁ = {⁰⁄₁, ¹⁄₁}

F₂ = {⁰⁄₁, ¹⁄₂, ¹⁄_1}

F₃ = {⁰⁄₁, ¹⁄₃, ¹⁄₂, ²⁄₃, ¹⁄_1}

F₄ = {⁰⁄₁, ¹⁄₄, ¹⁄₃, ¹⁄₂, ²⁄₃, ³⁄₄, ¹⁄_1}

F₅ = {⁰⁄₁, ¹⁄₅, ¹⁄₄, ¹⁄₃, ²⁄₅, ¹⁄₂, ³⁄₅, ²⁄₃, ³⁄₄, ⁴⁄₅, ¹⁄_1}

F₆ = {⁰⁄₁, ¹⁄₆, ¹⁄₅, ¹⁄₄, ¹⁄₃, ²⁄₅, ¹⁄₂, ³⁄₅, ²⁄₃, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ¹⁄_1}

F₇ = {⁰⁄₁, ¹⁄₇, ¹⁄₆, ¹⁄₅, ¹⁄₄, ²⁄₇, ¹⁄₃, ²⁄₅, ³⁄₇, ¹⁄₂, ⁴⁄₇, ³⁄₅, ²⁄₃, ⁵⁄₇, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇, ¹⁄_1}

F₈ = {⁰⁄₁, ¹⁄₈, ¹⁄₇, ¹⁄₆, ¹⁄₅, ¹⁄₄, ²⁄₇, ¹⁄₃, ³⁄₈, ²⁄₅, ³⁄₇, ¹⁄₂, ⁴⁄₇, ³⁄₅, ⁵⁄₈, ²⁄₃, ⁵⁄₇, ³⁄₄, ⁴⁄₅, ⁵⁄₆, ⁶⁄₇, ⁷⁄₈, ¹⁄_1}

Histoire

L'histoire des 'séries de Farey' est très curieuse — Hardy & Wright (1979) Chapitre III

... une fois encore, l'homme dont le nom fut donné à la relation mathématique n'était pas celui qui l'a découverte. — Beiler (1964) Chapitre XVI

Les suites de Farey furent nommées en l'honneur du géologue britannique, Sir John Farey. Sa lettre à propos de ces suites fut publiée dans le Philosophical Magazine en 1816. Farey conjectura que chaque terme dans une telle suite est le médian de ses voisins — néanmoins, à ce que l'on connaît, il ne prouva pas cette propriété. La lettre de Farey fut lue par Cauchy, qui donna la preuve dans ses Exercices de mathématique, et attribua ce résultat à Farey. En fait, un autre mathématicien, C. Haros, publia des résultats similaires en 1802 qui ne fut pourtant certainemant pas autant connu que Farey ou Cauchy. Ainsi, c'est un accident historique qui relie le nom de Farey à ces suites.

Propriétés

Nombre de termes d'une suite de Farey

La suite de Farey d'ordre n contient tous les éléments des suites de Farey d'ordre inférieur. En particulier, F_n contient tous les éléments de la suite F_n−1, ainsi qu'une fraction supplémentaire pour chaque entier inférieur à n et premier avec n. Ainsi, la suite F₆ est composé des éléments de la suite F₅ auxquels il faut ajouter les fractions ¹⁄₆ and ⁵⁄₆. Le terme médian d'une suite de Farey est toujours ¹⁄₂, lorsque n > 1.

Il est possible de relier le nombre de termes de F_n (noté ) et celui de F_n−1 en utilisant la fonction φ d'Euler  :

En utilisant le fait que |F₁| = 2, le nombre de termes de F_n peut donc s'exprimer en fonction de n de la façon suivante :

Le comportement asymptotique de |F_n| est :

Les voisins dans une suite de Farey

Les fractions qui sont des termes voisins dans une suite de Farey ont les propriétés suivantes.

Si ^a⁄_b et ^c⁄_d sont voisins dans une suite de Farey, avec ^a⁄_b < ^c⁄_d, alors leur différence ^c⁄_d − ^a⁄_b est égale à ¹⁄_bd. Comme

,

il est équivalent de dire ceci

bc − ad = 1.

Ainsi ¹⁄₃ et ²⁄₅ sont voisins dans F₅, et leur différence est ¹⁄₁₅.

L'inverse est également vrai. Si

bc − ad = 1

pour les for positive integers a,b,c et d avec a < b et c < d alors ^a⁄_b et ^c⁄_d seront voisins dans la suite de Farey dans l'ordre min(b,d).

Si ^p⁄_q possèdent des voisins ^a⁄_b et ^c⁄_d dans certaines suites de Farey, avec

^a⁄_b < ^p⁄_q < ^c⁄ _d

alors ^p⁄_q est le médian de ^a⁄_b et ^c⁄_d — en d'autres mots,

.

Et, si ^a⁄_b et ^c⁄_d sont voisins dans une suite de Farey alors le premier terme qui apparaît entre eux comme l'ordre de la suite de Farey est augmenté

,

lequel apparaît en premier dans la suite de Farey d'ordre b+d.

Ainsi, le premier terme apparaissant entre ¹⁄₃ et ²⁄₅ est ³⁄₈, qui apparaît dans F₈.

L'arbre de Stern-Brocot est une structure de données montrant comment la suite est construite à partir de 0 (= ⁰⁄₁) et 1 (= ¹⁄₁), en prenant les médians successifs.

Les fractions qui apparaîssent comme voisines dans une suite de Farey possèdent pour fermeture un développement en fraction continuée relié. Chaque fraction possède deux développement en fractions continuées - dans l'un, le terme final est 1 ; et dans l'autre, le terme final est plus grand que 1. Si ^p⁄_q, which first appears in Farey sequence F_q, has continued fraction expansions

then the nearest neighbour of ^p⁄_q in F_q (which will be its neighbour with the larger denominator) has a continued fraction expansion

and its other neighbour has a continued fraction expansion

Thus ³⁄₈ has the two continued fraction expansions [0;2,1,1,1] and [0;2,1,2], and its neighbours in F₈ are ²⁄₅, which can be expanded as [0;2,1,1]; and ¹⁄₃, which can be expanded as [0;2,1].

Ford circles

There is an interesting connection between Farey sequence and Ford circles.

For every fraction p/q (in its lowest terms) there is a Ford circle C[p/q], which is the circle with radius 1/2q² and centre at (p/q,1/2q²). Two Ford circles for different fractions are either disjoint or they are tangent to one another - two Ford circles never intersect. If 0<p/q<1 then the Ford circles that are tangent to C[p/q] are precisely the Ford circles for fractions that are neighbours of p/q in some Farey sequence.

Thus C[2/5] is tangent to C[1/2], C[1/3], C[3/7], C[3/8] etc.

References

• Beiler, Albert H. (1964) Recreations in the Theory of Numbers (Second Edition). Dover. ISBN 0486210960

• Hardy, G.H. & Wright, E.M. (1979) An Introduction to the Theory of Numbers (Fifth Edition). Oxford University Press. ISBN 0198531710

External links

• Farey series
• MathWorld page on Stern-Brocot trees