suite de Brocot

Écrivez 0 et l'infini aux deux extrémités d'une ligne. Entre deux fractions voisines, additionnez leurs numérateurs entre eux et leurs dénominateurs entre eux. Entre 1/2 et 1/1 apparaît ainsi 2/3.

En répétant ce geste à chaque rang, la suite se peuple de nouvelles fractions. Chaque rationnel positif finit par recevoir une place déterminée : la construction organise donc tous ces nombres au lieu de les ranger simplement par taille du numérateur ou du dénominateur.

Une suite de Brocot de rang n, notée B_n, est une liste ordonnée de fractions obtenue par insertions successives. Le rang initial est B₀ = (0/1, 1/0). La fraction 1/0 est une convention pour l'infini ; elle sert de borne et n'est pas un rationnel positif ordinaire.

Pour deux fractions consécutives a/b et c/d, où a et c sont les numérateurs et b et d les dénominateurs, l'addition des cancres, aussi appelée médiant, est $\frac{a}{b}\oplus \frac{c}{d}=\frac{a+c}{b+d}\backslash frac\{a\}\{b\}\backslash oplus\backslash frac\{c\}\{d\}=\backslash frac\{a+c\}\{b+d\}$. On insère ce résultat entre les deux fractions, tout en conservant celles du rang précédent. Par exemple, 1/2 et 1/1 donnent 2/3.

Le procédé produit B₁ = (0, 1, ∞), puis B₂ = (0, 1/2, 1, 2, ∞), et continue de même. Tout rationnel positif possède une première apparition dans cette construction. Cette énumération complète est liée aux fractions continues et fut proposée en 1862 par l'horloger français Achille Brocot pour calculer des rapports de roues dentées.

La construction réunit quatre éléments. Les bornes 0/1 et 1/0 encadrent chaque rang. Les fractions déjà présentes gardent leur ordre. Chaque paire de voisines fournit une nouvelle fraction par addition séparée des numérateurs et des dénominateurs. Enfin, l'indice n mémorise le nombre de vagues d'insertion effectuées depuis B₀.

Le voisinage commande donc le calcul : 1/2 ne produit 2/3 que parce que sa voisine droite est 1/1. En retour, toutes les fractions nouvelles deviennent des voisines utilisables au rang suivant. Le schéma du médiant rend visible cette double dépendance entre les deux fractions parentes et la fraction insérée.

Partons de B₂ = (0/1, 1/2, 1/1, 2/1, 1/0). Les cinq fractions et leurs quatre voisinages sont les seules données nécessaires pour construire le rang suivant.

1. Entre 0/1 et 1/2, insérez (0 + 1)/(1 + 2) = 1/3.
2. Entre 1/2 et 1/1, insérez (1 + 1)/(2 + 1) = 2/3.
3. Entre 1/1 et 2/1, insérez (1 + 2)/(1 + 1) = 3/2.
4. Entre 2/1 et 1/0, insérez (2 + 1)/(1 + 0) = 3/1.

En gardant les anciennes fractions à leur place, on obtient B₃ = (0, 1/3, 1/2, 2/3, 1, 3/2, 2, 3, ∞). Pour contrôler le calcul central, 1/2 < 2/3 < 1 : le médiant est bien situé entre ses deux voisines.

Pour énumérer les rationnels positifs sans en oublier, on développe les rangs et l'on note la première apparition de chaque fraction. Une liste classée seulement par numérateur laisserait ouverte la façon de départager une infinité de dénominateurs ; les insertions donnent ici une règle unique de progression.

Pour rechercher un rapport de roues dentées, on lit une fraction comme le rapport de deux nombres de dents. La construction de Brocot est adaptée lorsque l'on veut parcourir méthodiquement des rapports rationnels ; un calcul direct suffit si le rapport exact est déjà connu.

Pour étudier la structure d'un rationnel, le chemin de ses insertions peut être rapproché de son écriture en fraction continue. On préfère travailler directement avec les fractions continues lorsque cette écriture, plutôt que l'ordre de construction des rangs, constitue l'objet recherché.

L'addition des cancres n'est pas l'addition usuelle des fractions. Avec 1/2 et 1/1, le médiant vaut (1 + 1)/(2 + 1) = 2/3, tandis que leur somme ordinaire vaut 3/2. Le test est simple : pour le médiant, on additionne séparément les deux nombres écrits en haut et les deux nombres écrits en bas, sans chercher de dénominateur commun.

La convention 1/0 = ∞ est une sentinelle de la construction. Elle autorise le calcul au bord, par exemple 2/1 ⊕ 1/0 = 3/1, mais elle ne transforme pas 1/0 en rationnel positif. Il faut donc l'exclure lorsque l'on recense les rationnels obtenus.

Le médiant de deux fractions quelconques n'est pas nécessairement irréductible : 1/3 ⊕ 1/1 donne 2/4. La propriété d'énumération dépend des voisinages particuliers créés par la construction de Brocot ; il ne faut pas remplacer ces voisines par une paire choisie arbitrairement.

Les rangs sont emboîtés, car une fraction déjà présente est conservée. Ainsi 1 figure dans B₁, B₂ et B₃. Dire qu'un rationnel apparaît exactement une fois signifie qu'il possède une unique première insertion dans la construction, non qu'il disparaît des rangs ultérieurs.

Le glossaire Fraction continue présente l'écriture à laquelle la construction de Brocot est profondément liée.

Le glossaire Rationnels précise l'ensemble que les suites de Brocot énumèrent entièrement du côté positif.

L'article Les fractions continues, prolonge l'étude de ces représentations et de leurs liens avec les rationnels.