Brocot Achille

En 1861, en France, l'horloger Achille Brocot décrit une façon d'organiser les fractions positives comme les embranchements d'un arbre. Entre deux fractions déjà placées, on additionne les numérateurs entre eux et les dénominateurs entre eux.

En répétant ce geste et en choisissant la bonne branche, on rencontre chaque fraction irréductible une seule fois. Cette structure relie le travail d'un mathématicien amateur issu d'une famille d'horlogers à la théorie des nombres et à l'algorithmique.

Achille Brocot (1817-1878) est un horloger français et un mathématicien amateur, issu d'une famille d'horlogers. Il perfectionne plusieurs mécanismes horlogers. En mathématiques, il décrit en 1861 la structure aujourd'hui appelée arbre de Stern-Brocot, qui ordonne les nombres rationnels strictement positifs. Chaque nombre y est représenté par une fraction irréductible et apparaît exactement une fois.

La construction emploie la médiante. Si la fraction de gauche est $\frac{a}{b}\backslash frac\{a\}\{b\}$ et celle de droite $\frac{c}{d}\backslash frac\{c\}\{d\}$, avec des dénominateurs b et d strictement positifs pour les fractions ordinaires, leur médiante est $\frac{a+c}{b+d}\backslash frac\{a+c\}\{b+d\}$. Dans l'arbre, les bornes symboliques 0/1 et 1/0 encadrent la racine 1/1 ; 1/0 sert seulement de frontière et n'est pas une fraction rationnelle. À chaque comparaison, la fraction cherchée se trouve à gauche de la médiante, à sa droite ou lui est égale. Ces trois cas déterminent la branche suivante ou l'arrêt. Cette organisation a des applications en théorie des nombres, dans l'approximation rationnelle et en algorithmique.

On cherche la fraction irréductible 5/3 dans l'arbre de Stern-Brocot. Les données sont la cible 5/3, les bornes initiales 0/1 et 1/0, et la règle de la médiante : on additionne séparément les numérateurs et les dénominateurs.

1. La première médiante est $\frac{0+1}{1+0}=\frac{1}{1}\backslash frac\{0+1\}\{1+0\}=\backslash frac\{1\}\{1\}$. Comme 5/3 est supérieur à 1/1, 1/1 devient la borne de gauche.

2. Entre 1/1 et 1/0, la médiante vaut $\frac{1+1}{1+0}=\frac{2}{1}\backslash frac\{1+1\}\{1+0\}=\backslash frac\{2\}\{1\}$. Comme 5/3 est inférieur à 2/1, 2/1 devient la borne de droite.

3. Entre 1/1 et 2/1, on obtient $\frac{1+2}{1+1}=\frac{3}{2}\backslash frac\{1+2\}\{1+1\}=\backslash frac\{3\}\{2\}$. La cible est supérieure à 3/2, qui devient la nouvelle borne de gauche.

4. Entre 3/2 et 2/1, la médiante est $\frac{3+2}{2+1}=\frac{5}{3}\backslash frac\{3+2\}\{2+1\}=\backslash frac\{5\}\{3\}$ : la cible est atteinte. Le contrôle est direct : 3 × 3 = 9 est inférieur à 2 × 5 = 10, puis 1 × 5 = 5 est inférieur à 2 × 3 = 6 ; ainsi 3/2 < 5/3 < 2/1. De plus, 5 et 3 n'ont aucun diviseur commun supérieur à 1.

Pour retrouver une fraction positive, on part de 1/1 et on compare la cible à chaque médiante. Une cible plus petite fait choisir la branche gauche ; une cible plus grande, la branche droite. Cette recherche évite d'énumérer toutes les fractions précédentes.

Pour produire des fractions sans doublon, on parcourt l'arbre et on conserve chaque écriture irréductible rencontrée. Si l'on doit seulement trier une liste finie déjà fournie, un tri ordinaire est plus direct : l'arbre est utile quand les fractions sont générées ou recherchées par leur position.

Pour approcher une valeur par des rationnels, les comparaisons successives resserrent deux bornes autour de la cible. Une fraction continue constitue une autre voie d'approximation ; l'arbre est préférable lorsque l'on veut aussi conserver le chemin gauche-droite exploitable par un algorithme.

Achille Brocot et l'arbre de Stern-Brocot. Le premier est l'horloger et mathématicien amateur né en 1817 ; le second est la structure mathématique qu'il a décrite en 1861. Une date biographique désigne la personne, tandis qu'un chemin de fractions désigne l'arbre.

Médiante et moyenne arithmétique. Entre 1/2 et 2/3, la médiante vaut 3/5, tandis que leur moyenne vaut 7/12. Le test consiste à additionner séparément numérateurs et dénominateurs pour la médiante ; faire la demi-somme des deux valeurs calcule une moyenne.

La frontière 1/0 ne représente pas un rationnel positif : son dénominateur est nul. Si elle est lue comme une fraction ordinaire, la construction semble contenir une division interdite. Il faut la traiter uniquement comme la borne symbolique située au-delà de tous les rationnels positifs.

Une écriture réductible n'ajoute pas un nouveau nœud. Par exemple, 2/4 désigne le même rationnel que 1/2 ; chercher deux positions distinctes contredirait l'unicité annoncée. Il faut réduire la fraction cible avant d'interpréter sa place dans l'arbre.

La règle de la médiante ne suffit pas avec deux écritures arbitraires. Si les bornes sont égales ou mal ordonnées, la nouvelle fraction ne fournit pas une branche stricte entre elles. Il faut conserver les deux bornes voisines et ordonnées produites par la recherche dans l'arbre.

L'arbre est infini : aucun dessin fini ne montre toutes les fractions positives. Le symptôme d'une lecture erronée serait de prendre les premiers niveaux pour une liste complète. Pour une cible rationnelle positive donnée sous forme irréductible, on suit seulement son chemin jusqu'au nœud correspondant.

Fraction continue — Pour étudier une autre organisation des approximations rationnelles et comparer la manière dont ses convergents sélectionnent des fractions.

Rationnels — Pour préciser l'ensemble de nombres que l'arbre de Stern-Brocot énumère du côté strictement positif.