Suite de Farey

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Farey.

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

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[modifier | modifier le code]

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

Histoire[modifier | modifier le code]

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, Charles Haros (en), 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.

Propriétés[modifier | modifier le code]

Nombre de termes d'une suite de Farey[modifier | modifier le code]

La suite de Farey d'ordre contient tous les éléments des suites de Farey d'ordre inférieur. En particulier, contient tous les éléments de la suite ainsi qu'une fraction supplémentaire pour chaque entier inférieur à et premier avec Ainsi, la suite est composée des éléments de la suite auxquels il faut ajouter les fractions et Le terme médian d'une suite de Farey est toujours lorsque

Il est possible de relier le nombre de termes de (noté ) et celui de en utilisant l'indicatrice d'Euler  :

En utilisant le fait que le nombre de termes de peut donc s'exprimer en fonction de de la façon suivante :

Le comportement asymptotique de est :

Les voisins dans une suite de Farey[modifier | modifier le code]

Deux fractions consécutives dans une suite de Farey sont dites voisines ou consécutives à l'ordre Par exemple les fractions et sont voisines aux ordres 5, 6 et 7.

La notion de voisinage est relative à la suite considérée: deux fractions voisines à l'ordre peuvent ne plus l'être à l'ordre pour un plus grand. Par exemple et ne sont plus voisines dans puisque est venue s'intercaler entre les deux.

Mathématiquement, deux fractions irréductibles et sont voisines à l'ordre si et si il n'y a aucune autre fraction dans qui soit comprise entre et c'est-à-dire si pour toute fraction telle que on a

La propriété fondamentale des suites de Farey est une caractérisation très simple de la relation de voisinage:

Deux fractions irréductibles et sont consécutives à l'ordre ssi la relation est vérifiée.

En divisant les deux membres par on voit que la relation peut également s'écrire:

La quantité est parfois appelée produit en croix ou déterminant des deux fractions; elle dépend de la représentation choisie des deux fractions aussi il faut bien supposer dans la propriété ci-dessus que les deux fractions sont en forme irréductibles (ce qui est implicite dans la définition de consécutives). Par exemple si on considère les fractions et qui sont voisines dans leur produit en croix est qui est bien égal à Mais si on considère une représentation non irréductible des deux mêmes fractions, par exemple et alors leur produit en croix est

Attention également à la condition sur l'ordre de la suite de Farey considérée: le fait que la relation est vérifiée n'implique pas que les deux fractions sont voisines dans toutes les suites de Farey; en fait on va voir qu'elles sont voisines jusqu'à l'ordre mais plus après. Ainsi et sont voisines aux ordres et mais plus à l'ordre

La seconde propriété fondamentale des suites de Farey est que l'on peut facilement déterminer la première fraction à venir s'intercaler entre deux voisines:

Si et sont consécutives dans la suite d'ordre et si est la fraction médiane:

alors les fractions et sont consécutives dans la suite d'ordre

Par exemple si on reprend les deux fractions et voisines dans on a vu que la première fraction à s'intercaler est qui est bien la médiane.

Interprétation géométrique de la médiane de deux fractions

L'emploi du terme médiane s'explique géométriquement: on se place dans le plan euclidien, on nomme l'origine du repère; à la fraction on associe le point de coordonnées ; ainsi est la pente de la droite du plan issue de et passant par Si est le point de coordonnées associé à la fraction alors le milieu de et a pour coordonnées et ; on voit que la fraction médiane est alors la pente de la médiane issue de du triangle

La propriété se démontre en utilisant la caractérisation des fractions voisines vue précédemment; de plus sous les hypothèses ci-dessus, notamment que et sont irréductibles, la fraction médiane est automatiquement irréductible également.

La médiane est parfois également appelée somme du cancre ce qui est trompeur car, comme le produit en croix, elle dépend des représentations des fractions. Si on reprend l'exemple du produit en croix on a: et mais la médiane de et est tandis que celle de et est qui n'est pas égale à Comme pour le produit en croix on se restreindra à ne calculer les médianes que lorsque les fractions sont en forme irréductible de façon à lever toute ambigüité.

La propriété admet une réciproque: si et sont consécutives dans une suite d'ordre alors est la médiane de et ; il se peut toutefois, lorsque et ne sont pas voisines, que cette fraction médiane ne soit pas irréductible. Par exemple si on considère les trois fractions et qui sont consécutives dans la suite la fraction médiane de et est qui n'est pas irréductible mais redonne après simplification. De fait et ne sont voisines dans aucune suite.

Il existe également une caractérisation du voisinage en termes de fraction continue: si admet le développement en fraction continue:

alors ses deux voisines dans la suite d'ordre ont pour développement en fraction continue

Ainsi a pour développement en fraction continue et ses voisines dans sont qui admet le développement et qui se développe en

La propriété de la médiane est à la base de la construction de l'arbre de Stern-Brocot, une structure énumérant les fractions irréductibles obtenue en itérant l'opération de médiane à partir de 0 (= ) et l'infini (= )

Article détaillé : Arbre de Stern-Brocot.

.

Cercles de Ford[modifier | modifier le code]

Il existe une relation intéressante entre les suites de Farey et les cercles de Ford.

Pour toute fraction (réduite) il existe un cercle de Ford qui est le cercle de rayon et de centre Les cercles de Ford correspondant à deux fractions distinctes sont soit disjoints soit tangents - deux cercles de Ford ne peuvent pas être sécants. Si alors les cercles de Ford qui sont tangents à sont précisément les cercles de Ford associés aux fractions qui sont voisines de dans une suite de Farey.

Ainsi est tangent à etc.

Article détaillé : Cercle de Ford.

Hypothèse de Riemann[modifier | modifier le code]

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 termes est la différence entre le k-ième terme de la n-ième suite de Farey, et le k-ième élément d'un ensemble de même nombre de points, distribués également sur l'intervalle unité. Jérôme Franel[1] a démontré que l'assertion

est équivalente à l'hypothèse de Riemann, puis Landau[2] a remarqué, à la suite de l'article de Franel, que l'assertion

lui est également équivalente.


( est la notation de domination de Landau)

Article détaillé : Hypothèse de Riemann.

Un algorithme simple[modifier | modifier le code]

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

Cet algorithme se déduit du fait que, si et sont deux termes successifs dans une suite de Farey alors les successeurs de sont tous de la forme Pour trouver le successeur à l'ordre il faut trouver le plus grand tel que et celui-ci est fourni par la partie entière du quotient de par

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

Notes et références[modifier | modifier le code]

  1. "Les suites de Farey et le théorème des nombres premiers", Gött. Nachr. 1924, 198-201
  2. "Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel", Gött. Nachr. 1924, 202-206

Bibliographie[modifier | modifier le code]

Liens externes[modifier | modifier le code]