Suite de Farey

En mathématiques, la suite de Farey d'ordre ${\displaystyle n}$ est la suite finie formée par les fractions irréductibles de dénominateur inférieur ou égal à ${\displaystyle n}$ comprises entre 0 et 1, rangées dans l'ordre croissant. Certains auteurs ne restreignent pas les suites de Farey à l'intervalle de 0 à 1[1].

Chaque suite de Farey commence par la valeur 0, décrite par la fraction ${\displaystyle 0/1,}$ et se termine par la valeur 1, décrite par la fraction ${\displaystyle 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.

Exemples

Les suites de Farey d'ordre 1 à 8 sont (les termes nouveaux étant colorés en vert):

${\displaystyle F_{1}=\left({\color {Green}{\frac {0}{1}}},\,{\color {Green}{\frac {1}{1}}}\right)}$

${\displaystyle F_{2}=\left({\frac {0}{1}},\,{\color {Green}{\frac {1}{2}}},\,{\frac {1}{1}}\right)}$

${\displaystyle F_{3}=\left({\frac {0}{1}},\,{\color {Green}{\frac {1}{3}}},\,{\frac {1}{2}},\,{\color {Green}{\frac {2}{3}}},\,{\frac {1}{1}}\right)}$

${\displaystyle F_{4}=\left({\frac {0}{1}},\,{\color {Green}{\frac {1}{4}}},\,{\frac {1}{3}},\,{\frac {1}{2}},\,{\frac {2}{3}},\,{\color {Green}{\frac {3}{4}}},\,{\frac {1}{1}}\right)}$

${\displaystyle F_{5}=\left({\frac {0}{1}},\,{\color {Green}{\frac {1}{5}}},\,{\frac {1}{4}},\,{\frac {1}{3}},\,{\color {Green}{\frac {2}{5}}},\,{\frac {1}{2}},\,{\color {Green}{\frac {3}{5}}},\,{\frac {2}{3}},\,{\frac {3}{4}},\,{\color {Green}{\frac {4}{5}}},\,{\frac {1}{1}}\right)}$

${\displaystyle F_{6}=\left({\frac {0}{1}},\,{\color {Green}{\frac {1}{6}}},\,{\frac {1}{5}},\,{\frac {1}{4}},\,{\frac {1}{3}},\,{\frac {2}{5}},\,{\frac {1}{2}},\,{\frac {3}{5}},\,{\frac {2}{3}},\,{\frac {3}{4}},\,{\frac {4}{5}},\,{\color {Green}{\frac {5}{6}}},\,{\frac {1}{1}}\right)}$

${\displaystyle F_{7}=\left({\frac {0}{1}},\,{\color {Green}{\frac {1}{7}}},\,{\frac {1}{6}},\,{\frac {1}{5}},\,{\frac {1}{4}},\,{\color {Green}{\frac {2}{7}}},\,{\frac {1}{3}},\,{\frac {2}{5}},\,{\color {Green}{\frac {3}{7}}},\,{\frac {1}{2}},\,{\color {Green}{\frac {4}{7}}},\,{\frac {3}{5}},\,{\frac {2}{3}},\,{\color {Green}{\frac {5}{7}}},\,{\frac {3}{4}},\,{\frac {4}{5}},\,{\frac {5}{6}},\,{\color {Green}{\frac {6}{7}}},\,{\frac {1}{1}}\right)}$

${\displaystyle F_{8}=\left({\frac {0}{1}},\,{\color {Green}{\frac {1}{8}}},\,{\frac {1}{7}},\,{\frac {1}{6}},\,{\frac {1}{5}},\,{\frac {1}{4}},\,{\frac {2}{7}},\,{\frac {1}{3}},\,{\color {Green}{\frac {3}{8}}},\,{\frac {2}{5}},\,{\frac {3}{7}},\,{\frac {1}{2}},\,{\frac {4}{7}},\,{\frac {3}{5}},\,{\color {Green}{\frac {5}{8}}},\,{\frac {2}{3}},\,{\frac {5}{7}},\,{\frac {3}{4}},\,{\frac {4}{5}},\,{\frac {5}{6}},\,{\frac {6}{7}},\,{\color {Green}{\frac {7}{8}}},\,{\frac {1}{1}}\right)}$

Histoire

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

... 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 portent le nom du géologue britannique Sir John Farey. Dans une lettre concernant ces suites publiée dans le Philosophical Magazine en 1816, Farey conjecture que chaque terme dans une telle suite est le médian de ses voisins — néanmoins, à ce que l'on connaît, il n'a pas prouvé cette propriété. La lettre de Farey a été 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), avait publié des résultats similaires en 1802 mais il n'était pas aussi connu que Farey ou Cauchy. Ainsi, c'est un accident historique qui relie le nom de Farey à ces suites [2].

Propriétés

Nombre de termes d'une suite de Farey

La suite de Farey d'ordre ${\displaystyle n}$ contient tous les éléments des suites de Farey d'ordre inférieur. En particulier, ${\displaystyle F_{n}}$ contient tous les éléments de la suite ${\displaystyle F_{n-1},}$ ainsi qu'une fraction supplémentaire pour chaque entier inférieur à ${\displaystyle n}$ et premier avec ${\displaystyle n.}$ Par exemple, la suite ${\displaystyle F_{6}}$ est composée des éléments de la suite ${\displaystyle F_{5}}$ auxquels il faut ajouter les fractions ${\displaystyle 1/6}$ et ${\displaystyle 5/6.}$ Le terme médian d'une suite de Farey est toujours ${\displaystyle 1/2,}$ lorsque ${\displaystyle n>1.}$

Le nombre de termes de ${\displaystyle F_{n}}$ (noté ${\displaystyle |F_{n}|}$) est donc égal à celui de ${\displaystyle F_{n-1}}$ augmenté du nombre de nombres inférieurs à ${\displaystyle n}$ et premiers avec lui ; en utilisant l'indicatrice d'Euler ${\displaystyle \varphi \,}$ ceci s'écrit :

${\displaystyle |F_{n}|=|F_{n-1}|+\varphi (n)}$

En utilisant le fait que ${\displaystyle |F_{1}|=2,}$ le nombre de termes de ${\displaystyle F_{n}}$ peut donc s'exprimer en fonction de ${\displaystyle n}$ de la façon suivante :

${\displaystyle |F_{n}|=1+\sum _{k=1}^{n}\varphi (k)}$

Le comportement asymptotique de ${\displaystyle |F_{n}|}$ est donné par l'équivalence :

${\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}}$

Les voisins dans une suite de Farey

Deux fractions consécutives dans une suite de Farey ${\displaystyle F_{n}}$ sont dites voisines ou consécutives à l'ordre ${\displaystyle n.}$ Par exemple les fractions ${\displaystyle 3/5}$ et ${\displaystyle 2/3}$ sont voisines aux ordres 5, 6 et 7.

La notion de voisinage est relative à la suite considérée: deux fractions voisines à l'ordre ${\displaystyle n}$ peuvent ne plus l'être à l'ordre ${\displaystyle p}$ pour un ${\displaystyle p}$ plus grand. Par exemple ${\displaystyle 3/5}$ et ${\displaystyle 2/3}$ ne sont plus voisines dans ${\displaystyle F_{8}}$ puisque ${\displaystyle 5/8}$ est venue s'intercaler entre les deux.

Mathématiquement, deux fractions irréductibles ${\displaystyle a/b}$ et ${\displaystyle a'/b'}$ sont voisines à l'ordre ${\displaystyle n}$ si ${\displaystyle a/b<a'/b'}$ et s'il n'y a aucune autre fraction dans ${\displaystyle F_{n}}$ qui soit comprise entre ${\displaystyle a/b}$ et ${\displaystyle a'/b',}$ c'est-à-dire si pour toute fraction ${\displaystyle c/d}$ telle que ${\displaystyle a/b<c/d<a'/b'}$ on a ${\displaystyle d>n.}$

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

Deux fractions irréductibles ${\displaystyle a/b}$ et ${\displaystyle a'/b'}$ sont consécutives à l'ordre ${\displaystyle \max(b,b')}$ si et seulement si la relation ${\displaystyle a'b-ab'=1}$ est vérifiée.

En divisant les deux membres par ${\displaystyle bb'}$ on voit que la relation peut également s'écrire :

${\displaystyle {\frac {a'}{b'}}-{\frac {a}{b}}={\frac {1}{bb'}}.}$

La quantité ${\displaystyle a'b-ab'}$ 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 ${\displaystyle 3/5}$ et ${\displaystyle 2/3}$ qui sont voisines dans ${\displaystyle F_{5}}$, leur produit en croix est ${\displaystyle 2\times 5-3\times 3}$ qui est bien égal à ${\displaystyle 1.}$ Mais si on considère une représentation non irréductible des deux mêmes fractions, par exemple ${\displaystyle 9/15}$ et ${\displaystyle 4/6,}$ alors leur produit en croix est ${\displaystyle 4\times 15-9\times 6=6.}$

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 ${\displaystyle b+b'-1}$ mais plus à partir de ${\displaystyle b+b'}$. Ainsi ${\displaystyle 3/5}$ et ${\displaystyle 2/3}$ sont voisines aux ordres ${\displaystyle 5=\max(5,3),}$ ${\displaystyle 6}$ et ${\displaystyle 7}$ mais plus à l'ordre ${\displaystyle 8=5+3.}$

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 ${\displaystyle a/b}$ et ${\displaystyle a'/b'}$ sont consécutives dans la suite d'ordre ${\displaystyle \max(b,b')}$ et si ${\displaystyle c/d}$ est la fraction médiane:

${\displaystyle {\frac {c}{d}}={\frac {a+a'}{b+b'}}}$

alors les fractions ${\displaystyle a/b,}$ ${\displaystyle c/d}$ et ${\displaystyle a'/b'}$ sont consécutives dans la suite d'ordre ${\displaystyle b+b'.}$

Par exemple si on reprend les deux fractions ${\displaystyle 3/5}$ et ${\displaystyle 2/3}$ voisines dans ${\displaystyle F_{5},}$ on a vu que la première fraction à s'intercaler est ${\displaystyle 5/8}$ 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 ${\displaystyle O}$ l'origine du repère ; à la fraction ${\displaystyle a/b}$ on associe le point ${\displaystyle A}$ de coordonnées ${\displaystyle (b,a)}$ ; ainsi ${\displaystyle a/b}$ est la pente de la droite du plan ${\displaystyle (OA)}$ issue de ${\displaystyle O}$ et passant par ${\displaystyle A.}$ Si ${\displaystyle A'}$ est le point de coordonnées ${\displaystyle (b',a')}$ associé à la fraction ${\displaystyle a'/b'}$alors le milieu de ${\displaystyle A}$ et ${\displaystyle A'}$ a pour coordonnées ${\displaystyle (b+b')/2}$ et ${\displaystyle (a+a')/2}$ ; on voit que la fraction médiane ${\displaystyle (a+a')/(b+b')}$ est alors la pente de la médiane issue de ${\displaystyle O}$ du triangle ${\displaystyle (OAA').}$

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 ${\displaystyle a/b}$ et ${\displaystyle a'/b'}$ sont irréductibles, la fraction médiane ${\displaystyle (a+a')/(b+b')}$ 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: ${\displaystyle 3/5=9/15}$ et ${\displaystyle 2/3=4/6}$. Dans ce cas, on voit que les médianes de ${\displaystyle 3/5}$ et ${\displaystyle 2/3}$, d'une part, et de ${\displaystyle 9/15}$ et ${\displaystyle 4/6}$ d'autre part (égales respectivement à ${\displaystyle 5/8}$ et ${\displaystyle 13/21}$), ne sont pas égales. 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 ambiguïté.

La propriété admet une réciproque : si ${\displaystyle a/b,}$ ${\displaystyle c/d}$ et ${\displaystyle a'/b'}$ sont consécutives dans une suite d'ordre ${\displaystyle n}$, alors ${\displaystyle c/d}$ est la médiane de ${\displaystyle a/b}$ et ${\displaystyle a'/b'}$ ; il se peut toutefois, lorsque ${\displaystyle a/b}$ et ${\displaystyle a'/b'}$ ne sont pas voisines, que cette fraction médiane ne soit pas irréductible. Par exemple si on considère les trois fractions ${\displaystyle 3/5,}$ ${\displaystyle 2/3}$ et ${\displaystyle 5/7}$ qui sont consécutives dans la suite ${\displaystyle F_{7}}$ la fraction médiane de ${\displaystyle 3/5}$ et ${\displaystyle 5/7}$ est ${\displaystyle 8/12}$ qui n'est pas irréductible mais redonne ${\displaystyle 2/3}$ après simplification. De fait ${\displaystyle 3/5}$ et ${\displaystyle 5/7}$ ne sont voisines dans aucune suite.

Il existe également une caractérisation du voisinage en termes de fraction continue : si ${\displaystyle a/b}$ admet le développement en fraction continue :

${\displaystyle [a_{0},a_{1},a_{2},...,a_{n-1},a_{n},1]}$

alors ses deux voisines dans la suite d'ordre ${\displaystyle b}$ ont pour développement en fraction continue :

${\displaystyle [a_{0},a_{1},a_{2},...,a_{n-1},a_{n}]}$

${\displaystyle [a_{0},a_{1},a_{2},...,a_{n-1}]}$

Ainsi ${\displaystyle 3/8}$ a pour développement en fraction continue ${\displaystyle [0,2,1,1,1],}$ et ses voisines dans ${\displaystyle F_{8}}$ sont ${\displaystyle 2/5}$ qui admet le développement ${\displaystyle [0,2,1,1]}$ et ${\displaystyle 1/3}$ qui se développe en ${\displaystyle [0,2,1].}$

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 (= ${\displaystyle 0/1}$) et l'infini (= ${\displaystyle 1/0}$)

.

Cercles de Ford

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

Pour toute fraction (réduite) ${\displaystyle p/q}$ il existe un cercle de Ford ${\displaystyle C[p/q],}$ qui est le cercle de rayon ${\displaystyle 1/2q^{2}}$ et de centre ${\displaystyle (p/q,1/2q^{2}).}$ Les cercles de Ford correspondant à deux fractions distinctes sont soit disjoints soit tangents - deux cercles de Ford ne peuvent pas être sécants. Si ${\displaystyle 0<p/q<1,}$ alors les cercles de Ford qui sont tangents à ${\displaystyle C[p/q]}$ sont précisément les cercles de Ford associés aux fractions qui sont voisines de ${\displaystyle p/q}$ dans une suite de Farey.

Ainsi ${\displaystyle C[2/5]}$ est tangent à ${\displaystyle C[1/2],}$ ${\displaystyle C[1/3],}$ ${\displaystyle C[3/7],}$ ${\displaystyle C[3/8],}$ etc.

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 ${\displaystyle F_{n}\,}$ soient ${\displaystyle \{a_{k,n}:k=0,1,\ldots m_{n}\}.}$ Définissons ${\displaystyle d_{k,n}=a_{k,n}-k/m_{n},}$ en d'autres termes ${\displaystyle d_{k,n}}$ 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[3] a démontré que l'assertion :

${\displaystyle \sum _{k=1}^{m_{n}}d_{k,n}^{2}=O(n^{r})\quad \forall r>-1}$

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

${\displaystyle \sum _{k=1}^{m_{n}}|d_{k,n}|=O(n^{r})\quad \forall r>1/2}$

lui est également équivalente.

(${\displaystyle O(n^{r})}$ est la notation de domination de Landau).

Un algorithme simple

De manière surprenante, un algorithme simple existe pour engendrer les termes dans l'ordre croissant ou décroissant :

 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 ${\displaystyle a/b}$ et ${\displaystyle c/d}$ sont deux termes successifs dans une suite de Farey alors les successeurs de ${\displaystyle c/d}$ sont tous de la forme ${\displaystyle (kc-a)/(kd-b).}$ Pour trouver le successeur à l'ordre ${\displaystyle n}$ il faut trouver le plus grand ${\displaystyle k}$ tel que ${\displaystyle kd-b\leq n}$ et celui-ci est fourni par la partie entière du quotient de ${\displaystyle n+b}$ par ${\displaystyle d.}$

Pour engendrer la suite dans l'ordre décroissant :

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

En Python 3 :

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jan 23 16:34:16 2023

@author: Dominique
"""
from fractions import Fraction

n=int(input('Dénominateur maximum : '))

numterm=1
a,b,c,d=0,1,1,n
resu=str(a)+'/'+str(b)
print(resu,end=', ')
while c<n:
    numterm+=1
    k=int((n+b)/d)
    e=k*c-a
    f=k*d-b
    a,b,c,d=c,d,e,f
    resu=str(a)+'/'+str(b)
    if a==1 and b==1:
        print(resu,end='')
        continue

    print(Fraction(resu),end=(', '))

Notes et références

1. Ivan Niven and Herbert S. Zuckerman, An Introduction to the theory of numbers, third edition, John Wiley and Sons 1972. Definition 6.1. "The sequence of all reduced fractions with denominators not exceeding n, listed in order of their size, is called the Farey sequence of order n." Les auteurs ajoutent: "This definition of the Farey sequences seems to be the most convenient. However, some authors prefer to restrict the fractions to the interval from 0 to 1."
2. Daniel Barthes, « Suites de Farey et cercles de Ford », Hors Série Bibliothèque Tangente, n^o 33,‎ 2019, p. 122-123
3. "Les suites de Farey et le théorème des nombres premiers", Gött. Nachr. 1924, 198-201
4. "Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel", Gött. Nachr. 1924, 202-206

Bibliographie

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Farey sequence » (voir la liste des auteurs).
• Actes de l'Académie royale des sciences, belles-lettres et arts de Bordeaux (Valat, rapporteur), « Rapport sur un mémoire d'analyse de M. Stouvenel (sur la théorie de Farey et Cauchy) », C. Lawalle (Bordeaux),‎ octobre 1839, p. 639 (lire en ligne)
• (en) Albert Beiler, Recreations in the Theory of Numbers, 2^e éd., 1964, Dover (ISBN 0486210960)
• (en) G. H. Hardy et E. M. Wright, An Introduction to the Theory of Numbers (1^re éd. 1938) [détail des éditions]

Voir aussi

• Arbre de Stern-Brocot
• Suite de Stern-Brocot
• Arbre de Calkin-Wilf

Liens externes

• (en) Suites de Farey sur cut-the-knot
• (en) Eric W. Weisstein, « Farey Sequence », sur MathWorld
• Robert Ferréol, « Addition des cancres, suites de Brocot et friandises associées », Quadrature, n^o 36,‎ avril mai juin 1999, p. 13 - 24 (lire en ligne)