Les fractions continues et l'arbre de Stern–Brocot

Prenez un rectangle de côtés x et 1. Découpez-y le plus grand carré possible, autant de fois que possible : il en tient a₀. Il reste un rectangle plus petit ; recommencez. La suite des nombres de carrés est exactement le développement en fraction continue de x. Le procédé s'arrête si et seulement si x est rationnel — c'est l'algorithme d'Euclide, et c'est la définition grecque de la commensurabilité.

carrés d'une même étaperéduites par défautréduites par excès

Pourquoi l'irrationnel ne s'arrête jamais. Chaque étape remplace le couple (grand côté, petit côté) par (petit côté, reste) : c'est exactement une division euclidienne. Si les deux côtés ont une commune mesure, le reste finit par s'annuler ; sinon jamais. Les Grecs appelaient ce procédé anthyphairèse, et c'est probablement par lui, sur le carré et sa diagonale, que l'incommensurabilité a été découverte — la périodicité pure du développement de √2 rendant l'absence de fin évidente.

Partez de 0/1 et 1/0. Insérez entre elles leur médiante (0+1)/(1+0) = 1/1, puis recommencez dans chaque intervalle. L'arbre ainsi construit contient chaque fraction irréductible positive exactement une fois, et déjà rangée. Descendre vers un nombre produit un mot en G et D — et les longueurs des séries de ce mot sont précisément les quotients partiels de la fraction continue. Les deux objets sont le même.

Moritz Stern, 1858 ; Achille Brocot, 1861. Le premier était théoricien des nombres à Göttingen, successeur de Gauss ; le second horloger à Paris, qui cherchait des rapports d'engrenages réalisables approchant un rapport voulu. Ils ont trouvé la même construction à trois ans d'intervalle, pour des raisons entièrement différentes — et c'est encore par cet arbre qu'on calcule aujourd'hui la meilleure approximation rationnelle à dénominateur borné.

À chaque fraction irréductible p/q, associez le cercle tangent à l'axe en p/q, de rayon 1/(2q²). Deux de ces cercles ne se coupent jamais — et ils sont tangents exactement quand |ps − qr| = 1, c'est-à-dire quand les deux fractions sont voisines dans une suite de Farey, c'est-à-dire quand l'une est le parent de l'autre dans l'arbre. La verticale d'un irrationnel traverse une infinité de ces cercles : ce sont ses réduites.

Une figure qui démontre. Deux cercles de Ford de rayons 1/(2q²) et 1/(2s²) sont tangents si la distance de leurs centres vaut la somme des rayons ; le calcul donne (p/q − r/s)² = (1/q² )(1/s²), soit |ps − qr| = 1. La non-intersection générale s'écrit |ps − qr| ≥ 1, ce qui est vrai pour tout couple d'entiers non proportionnels. Toute la théorie de l'approximation diophantienne tient dans cette inégalité entière.

Pour juger une approximation, la bonne quantité n'est pas l'erreur |x − p/q| — qui tend vers zéro pour tout le monde — mais l'erreur rapportée au dénominateur, q·|qx − p|. Le nuage ci-dessous la donne pour tous les dénominateurs jusqu'à Q. Les réduites sont les seuls points bas, et la valeur vers laquelle descend leur suite est la constante de Lagrange du nombre : jamais moins de 1/√5, et exactement 1/√5 pour le nombre d'or.

Le théorème de Lagrange, et sa réciproque. Toute réduite vérifie |x − p/q| < 1/q² ; réciproquement, toute fraction vérifiant |x − p/q| < 1/(2q²) est nécessairement une réduite. Autrement dit, la fraction continue ne rate aucune bonne approximation, et n'en fabrique aucune mauvaise. C'est ce qui fait sa valeur pratique : 355/113 donne π à 3·10⁻⁷ près avec trois chiffres au dénominateur, et aucune fraction de dénominateur inférieur à 16 604 ne fait mieux.

Semez des graines à distance √k du centre, chacune tournée de α tour par rapport à la précédente. Si α est rationnel, tout retombe sur un petit nombre de rayons et le disque est mal rempli. Si α est proche d'un rationnel simple, l'alignement reparaît en spirales larges. Le meilleur remplissage est obtenu par le nombre le plus difficile à approcher — celui dont tous les quotients partiels valent 1, le nombre d'or. Et les spirales que l'œil compte sont les dénominateurs des réduites de α.

Ce que mesure la courbe de droite. Pour chaque α, on calcule la plus petite distance entre deux graines du semis : plus elle est grande, mieux le disque est occupé. La courbe s'effondre à chaque rationnel simple — 1/2, 1/3, 2/5, 3/8 — et culmine aux nombres dont le développement ne contient que des 1 à partir d'un certain rang, ce qu'on appelle les nombres nobles. Le maximum absolu tombe sur 1/φ² = 0,381966, à la résolution du balayage près. Rien dans ce calcul ne parle de botanique : c'est la seule arithmétique de l'approximation qui décide, et les tournesols n'ont fait que la trouver avant nous.