Suite de Farey
Un article de Wikipédia, l'encyclopédie libre.
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 0⁄1, et finit avec la valeur 1, décrite par la fraction 1⁄1 (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.
Sommaire |
[modifier] Exemples
Les suites de Farey d'ordre 1 à 8 sont :
- F1 = {0⁄1, 1⁄1}
- F2 = {0⁄1, 1⁄2, 1⁄1}
- F3 = {0⁄1, 1⁄3, 1⁄2, 2⁄3, 1⁄1}
- F4 = {0⁄1, 1⁄4, 1⁄3, 1⁄2, 2⁄3, 3⁄4, 1⁄1}
- F5 = {0⁄1, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 1⁄1}
- F6 = {0⁄1, 1⁄6, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 1⁄1}
- F7 = {0⁄1, 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⁄1}
- F8 = {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}
[modifier] 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 certainement pas autant connu que Farey ou Cauchy. Ainsi, c'est un accident historique qui relie le nom de Farey à ces suites.
[modifier] Propriétés
[modifier] 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, Fn contient tous les éléments de la suite Fn−1, ainsi qu'une fraction supplémentaire pour chaque entier inférieur à n et premier avec n. Ainsi, la suite F6 est composée des éléments de la suite F5 auxquels il faut ajouter les fractions 1⁄6 et 5⁄6. Le terme médian d'une suite de Farey est toujours 1⁄2, lorsque n > 1.
Il est possible de relier le nombre de termes de Fn (noté | Fn | ) et celui de Fn−1 en utilisant la fonction d'Euler :
En utilisant le fait que |F1| = 2, le nombre de termes de Fn peut donc s'exprimer en fonction de n de la façon suivante :
Le comportement asymptotique de |Fn| est :
[modifier] 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 à 1⁄bd. Comme
- ,
il est équivalent de dire ceci
- bc − ad = 1.
Ainsi 1⁄3 et 2⁄5 sont voisins dans F5, et leur différence est 1⁄15.
L'inverse est également vrai. Si
- bc − ad = 1
pour les entiers naturels 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 max(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 lorsque l'ordre de la suite de Farey est augmenté est
- ,
lequel apparaît en premier dans la suite de Farey d'ordre b+d.
Ainsi, le premier terme apparaissant entre 1⁄3 et 2⁄5 est 3⁄8, qui apparaît dans F8.
L'arbre de Stern-Brocot est une structure de données montrant comment la suite est construite à partir de 0 (= 0⁄1) et 1 (= 1⁄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 continue reliée. Chaque fraction possède deux développements en fractions continues - dans l'un, le terme final est 1 ; et dans l'autre, le terme final est plus grand que 1. Si p⁄q, qui apparaît en premier dans la suite de Farey Fq, admet un développement en fraction continue
- [0;a1,a2,...,an − 1,an,1]
- [0;a1,a2,...,an − 1,an + 1]
alors le voisin le plus proche de p⁄q dans Fq (lequel sera celui de ses voisins ayant le plus grand dénominateur) admet un développement en fraction continue
- [0;a1,a2,...,an]
et son autre voisin admet un développement en fraction continue
- [0;a1,a2,...,an − 1]
Ainsi 3⁄8 possède les deux développements en fraction continue [0;2,1,1,1] et [0;2,1,2], et ses voisins dans F8 son 2⁄5, lesquels peuvent être développés en [0;2,1,1]; et 1⁄3, lequel peut être développé en [0;2,1].
[modifier] Cercles de Ford
Il existe une relation intéressante entre les suites de Farey et les cercles de Ford.
Pour toute fraction (réduite) p/q il existe un cercle de Ford C[p/q], qui est le cercle de rayons 1/2q2 et de centre (p/q,1/2q2). Les cercles de Ford correspondant à deux fractions distinctes sont soit disjoints soit tangents - deux cercles de Ford ne peuvent pas être sécants. Si 0<p/q<1, alors les cercles de Ford qui sont tangents à C[p/q] sont précisément les cercles de Ford associés aux fractions qui sont voisines de p/q dans une suite de Farey.
Ainsi C[2/5] est tangent à C[1/2], C[1/3], C[3/7], C[3/8], etc.
[modifier] Hypothèse de Riemann
Les suites de Farey sont utilisées dans deux formulations équivalentes de l'hypothèse de Riemann. Supposons que les termes de soient . Définissons , en d'autres mots dk,n est la différence entre le k-ème terme de la n-ème suite de Farey, et le k-ème membre d'un ensemble de même nombre de points, distribués également sur l'intervalle unité. Franel et Landau ont démontré que les deux énoncés :
- pour tout r>1/2, et
- pour tout r>-1,
sont équivalents à l'hypothèse de Riemann.
[modifier] Un algorithme simple
De manière surprenante, un algorithme simple existe pour engendrer les termes dans un ordre, soit traditionnel (ascendant), soit non-traditionnel (descendant) :
100 'Code UBASIC pour engendrer une Suite de Farey d'ordre N dans l'ordre traditionnel 110 N=7:NumTerms=1 120 A=0:B=1:C=1:D=N 140 print A;B 150 while (C<N) 160 NumTerms=NumTerms+1 170 K=int((N+B)/D) 180 E=K*C-A:F=K*D-B 190 A=C:B=D:C=E:D=F:print A;B 200 wend 210 print NumTerms 220 end
(Note : aucune manipulation spéciale n'est requise près de la ligne 180 pour réduire chaque terme en une fraction réduite)
Pour engendrer la suite dans un ordre descendant (non-traditionnel) :
120 A=1:B=1:C=N-1:D=N 150 while (A>0)
Des recherches en force brute pour les solutions d'équations diophantiennes rationnelles peuvent souvent prendre l'avantage sur les suites de Farey (pour chercher seulement celles en formes réduites); la ligne 120 peut aussi être modifiée pour inclure deux termes adjacents quelconques afin d'engendrer seulement les termes plus grands (ou plus petits) qu'un terme donné.
[modifier] Références
- Beiler, Albert H. (1964) Recreations in the Theory of Numbers (Second Edition). Dover. ISBN 0486210960
- (en) G. H. Hardy et E. M. Wright An Introduction to the Theory of Numbers [détail des éditions]