Arbre de Stern-Brocot - Définition

Introduction

En mathématiques, un arbre de Stern-Brocot est une représentation de tous les rationnels strictement positifs, sous forme de fractions irréductibles.

Il a été découvert presque simultanément par le mathématicien allemand Moritz Stern (en) (1858) et par l'horloger français Achille Brocot (en) (1861).

Construction

Représentation de l'arbre Stern-Brocot

On part du couple de fractions irréductibles (0/1, 1/0), (on affirme que ).
Et on répète autant de fois que l'on le souhaite, le procédé suivant :

Insérer entre et , la fraction appelée médian de m/n et m'/n' :

On a tout d'abord donc : qui constituent les fondements de la construction.

A l'étape suivante on obtient donc :

On construit encore quatre fractions ensuite :

Et ainsi de suite... Mais ainsi défini, on peut imaginer la représentation de cette construction par un arbre binaire que l'on appelle Arbre de Stern-Brocot (voir image).

On remarque au passage que sur l'extrême-gauche se trouvent les fractions unitaires, sur l'extrême-droite, les nombres entiers écrits sous forme rationnelle, le dénominateur étant égal à 1.

Suite de Farey

La suite de Farey d'ordre N, que l'on note F_N, est la suite croissante des fractions réduites comprises entre 0 et 1 dont le dénominateur est inférieur ou égal à N.

L'étroite relation entre Stern-Brocot et cette suite est développé dans l'article correspondant.

Questions

Mais finalement, le procédé étant simple, pourquoi fonctionnerait-il ? Les réponses aux questions suivantes apporteront la preuve que la construction est justifiée.

Chaque fraction est-elle irréductible ?

On doit montrer cette relation par récurrence. On pose le fait fondamental :

À l'étage 0, c'est évident : on a 1.1 - 0.0 = 1.

Insérons un médian (m+m')/(n+n'), on doit donc vérifier la relation de récurrence pour ce médian avec m'/n' et avec m/n.
Il est donc évident de voir que :

Notre relation est vérifiée et on a l'équation de Bézout de (n+n') et (m+m') avec comme PGCD : 1. Les deux nombres sont donc premiers entre eux.

Une fraction apparait-elle deux fois ?

Non, parce que l'ordre est conservé tout au long de la construction.

Soient les deux fractions m/n et m'/n'. On vérifie donc :

On a encore utilisé la relation fondamentale que l'on a démontrée juste avant. On peut démontrer le même genre de relation avec m'/n'. Et on obtient donc :

On a gagné !

Tous les rationnels strictement positifs sont-ils dans l'arbre ?

Bien sûr, mais ce n'est pas immédiat ! Prenons a/b tel que a soit premier à b.
On a au départ : 0/1 < a/b < 1/0.
A une étape donnée, on a la configuration : m/n < a/b < m'/n'. En engendrant (m+m')/(n+n'), trois cas s'offrent à nous :

• , et là on arrête le processus (puisqu'on a gagné).
• , on pose donc pour l'étape suivante m: = m + m' et n: = n + n'
• , on pose donc pour l'étape suivante m': = m + m' et n': = n + n'

Or cet algorithme au bout d'un moment s'arrête !

On a vu que les conditions : et entraînent que et .

Ce qui nous amène à écrire que :
et d'après notre première relation on a : .

Au fur et à mesure des étapes, vous m'accorderez que m' + n' + m + n croit strictement. Donc l'algorithme s'arrêtera (au maximum en a+b étapes d'ailleurs).