Arbre de Stern-Brocot

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, l'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 (1858) et par l'horloger français Achille Brocot (en) (1861).

Construction[modifier | modifier le code]

Représentation de l'arbre Stern-Brocot

On part du couple de fractions irréductibles (0/1, 1/0), (on affirme que 1/0 = +\infty).

Et l'on répète autant de fois que l'on le souhaite, le procédé suivant :

Insérer entre \frac mn et \frac{m'}{n'}, la fraction appelée médian de m/n et m'/n' : \frac{m+m'}{n+n'}.

On a tout d'abord donc : \frac01,\,\frac11,\,\frac10 qui constituent les fondements de la construction.

À l'étape suivante on obtient donc : \frac01,\,\frac12,\,\frac11,\,\frac21,\,\frac10

On construit encore quatre fractions ensuite : \frac01,\,\frac13,\,\frac12,\,\frac23,\,\frac11,\,\frac32,\,\frac21,\,\frac31,\,\frac10

et ainsi de suite. Les termes qui apparaissent au numérateur sont les termes de la suite diatomique de Stern.

Ainsi définie, on peut représenter 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.

Preuves[modifier | modifier le code]

Cette section apporte la preuve que toutes les fractions de l'arbre sont irréductibles et que chaque fraction irréductible apparaît dans l'arbre une et une seule fois.

Irréductibilité de chaque fraction[modifier | modifier le code]

On peut montrer cette relation par récurrence. On pose l'hypothèse de récurrence :

H_p : Si m/n et m'/n' sont deux fractions consécutives sur le p-ième niveau de l'arbre, alors : m'n-mn' = 1.

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

Hérédité : Supposons que H_p est vraie et montrons que H_{p+1} est vraie.

La fraction médiane (m + m')/(n + n') se trouve sur l'étage p + 1 de l'arbre. On remarque que :

(m+m')n-m(n+n')= m'n - mn' = 1,

m'(n+n')-(m+m')n'= m'n - mn' = 1.

Notre relation est vérifiée et l'on a une relation de Bézout entre n + n' et m + m' avec un PGCD égal à 1. Les deux nombres sont donc premiers entre eux, ce qui prouve que (m + m')/(n + n') est irréductible et achève la récurrence.

Unicité[modifier | modifier le code]

On veut montrer qu'aucune fraction n'apparaît plus d'une fois dans l'arbre. Soient les deux fractions m/n et m'/n', telles que m'/n' > m/n. On vérifie que :

\frac{m+m'}{n+n'} - \frac mn = \frac{(m+m')n-m(n+n')}{n(n+n')} = \frac{m'n-mn'}{n(n+n')} > 0.

De même on démontre une relation similaire pour m'/n'. On obtient finalement :

\frac mn<\frac{m+m'}{n+n'}<\frac{m'}{n'}.

Ceci nous assure de l'unicité de chaque fraction.

Existence[modifier | modifier le code]

On veut montrer que toutes les fractions irréductibles apparaissent dans l'arbre. Considérons une fraction irréductible notée a/b.

On a au départ : 0/1 < a/b < 1/0.

À 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 :

  •  \frac{m+m'}{n+n'} = \frac ab : l'algorithme s'arrête, la fraction a/b est dans l'arbre ;
  •  \frac{m+m'}{n+n'} < \frac ab : on pose pour l'étape suivante  m := m+m' et  n := n+n'  ;
  •  \frac{m+m'}{n+n'} > \frac ab : on pose pour l'étape suivante  m' := m+m' et  n' := n+n' .

Montrons que l'algorithme s'arrête :

On a vu que les conditions : \frac ab-\frac mn>0 et \frac{m'}{n'}-\frac ab>0 entraînaient que  an-bm \geq 1 et  bm'-an'\geq 1 .

Ceci nous permet d'écrire que :

 (m'+n')(an-bm)+(m+n)(bm'-an') \geq m'+n'+m+n.

Or notre première relation donne :  a+b \geq m'+n'+m+n.

Au fur et à mesure des étapes, on constate que m'+n'+m+n croît strictement. Donc l'algorithme s'arrête (en a+b étapes au maximum).

Suite de Farey[modifier | modifier le code]

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.

Déplacement dans l'arbre[modifier | modifier le code]

Idée[modifier | modifier le code]

Étant donné qu'un rationnel n'apparait qu'une et une seule fois dans l'arbre, alors on peut considérer cet arbre comme un pur système de numération. Prenons la suite des pas que l'on va faire dans l'arbre pour atteindre la fraction souhaité. On définit donc deux « pas » : le pas G (gauche) et le pas D (droite) (dans le livre cité en référence on a L et R mais pour des raisons évidentes de traduction, on mettra G et D). On peut donc représenter tout rationnel positif comme une unique suite de G et D qui représente son chemin dans l'arbre.

Prenons un exemple : considérons le mot GDDG, on part de 1/1 pour arriver à 1/2, puis on va à droite vers 2/3, encore à droite, 3/4, et enfin à gauche 5/7.

On remarque que l'on doit partir de 1/1 (pour avoir un point de départ bien fixé et l'on suppose que 0 n'est jamais demandé). Convenons pour l'instant de l'appeler « Identité ».

Mais comment trouver de façon simple une fraction à partir d'un mot composé de G et de D.

Représentation matricielle[modifier | modifier le code]

Soit un mot S composé de G et de D, on définit f(S) comme la fraction correspondant à S.

On aimerait trouver un moyen simple pour exprimer f.

Pour cela, on va partir d'une représentation matricielle. Si vous ne comprenez pas les calculs ci-dessous, reportez vous à l'article sur les matrices. La théorie pure des matrices n'est pas vraiment utile ici, mais le calcul l'est, cela ne requiert donc aucun niveau d'algèbre linéaire.

On identifiera dans la suite la fraction \frac mn à la matrice colonne \begin{pmatrix}m \\ n\end{pmatrix}. Étant donné une telle matrice colonne, on notera q(\begin{pmatrix}m \\ n \end{pmatrix}) le rationnel \frac mn associé. Étant donné deux matrices colonnes V_1 et V_2, leur médian est V_1 + V_2. De façon matricielle, si l'on définit M comme la matrice 2×2 \begin{pmatrix}V_1 & V_2 \end{pmatrix} constituée des deux blocs V_1 et V_2, leur médian est tout simplement M\begin{pmatrix}1 \\ 1\end{pmatrix}.

Remarquons maintenant que chaque élément V de l'arbre de Stern-Brocot est associé de façon unique aux deux éléments de l'arbre V_1 et V_2 à partir desquels il a été obtenu lors de la construction de l'arbre avec q(V_1) < q(V_2). On note gen(V) la matrice par blocs \begin{pmatrix} V_2 & V_1\end{pmatrix}.

Pour calculer f(S), l'idée est alors de calculer récursivement gen(f(S)), qu'on notera \widehat S.

On remarque tout d'abord \widehat{\epsilon}= gen(\begin{pmatrix}1 \\ 1\end{pmatrix})= \begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix} = I (où \epsilon représente le mot vide et I est la matrice identité).

Si \widehat S=\begin{pmatrix}V_2 & V_1\end{pmatrix}, on a f(S) = V_1 + V_2 = \begin{pmatrix}V_2 & V_1\end{pmatrix}\begin{pmatrix}1 \\ 1\end{pmatrix}.

D'où :

\widehat{SD} = \begin{pmatrix}V_2 & f(S)\end{pmatrix} = \widehat S\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}

et :

\widehat{SG} = \begin{pmatrix}f(S) & V_1\end{pmatrix} = \widehat S\begin{pmatrix} 1 & 0 \\1 & 1\end{pmatrix}.

On peut alors définir deux matrices : \hat G=\begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix},\,\hat D=\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}.

Ainsi, on a une façon très agréable de calculer notre fraction puisque si S est le mot x_1x_2\ldots x_n, on a \widehat S=\hat x_1\hat x_2\ldots\hat x_n et f(S)=\hat x_1\hat x_2\ldots\hat x_n\begin{pmatrix}1\\ 1\end{pmatrix}.

Reprenons l'exemple cité précédemment :

f(GDDG)=\hat G\hat D\hat D\hat G=\begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix}\begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix}\begin{pmatrix}1 \\ 1\end{pmatrix} = \begin{pmatrix} 5 \\ 7\end{pmatrix}.

Réciproque / Algorithmes[modifier | modifier le code]

Pour la réciproque, c’est-à-dire, pour trouver le chemin effectué pour atteindre une fraction quelconque m/n il faut utiliser le théorème de Bachet-Bézout : si l'on suppose que m/n est irréductible, c'est-à-dire que m et n sont premiers entre eux, alors il existe deux entiers m' et n' tels que mn' - m'n = 1; si de plus on suppose que m et n sont distincts et tous les deux non nuls, alors on peut choisir m' et n' de façon que 0\leq m'< m et 0< n'< n (les coefficients m' et n' satisfaisant toutes ces contraintes sont directement calculés par l'algorithme d'Euclide étendu). Dans ce cas les fractions m'/n' et m/n sont consécutives dans la suite de Farey d'ordre n.

On pose alors m'' = m-m' et n'' = n - n' ; par construction m/n est le médian de m'/n' et m''/n'' et l'on a m'/n' < m/n < m''/n''. Dans l'arbre de Stern-Brocot, la fraction m/n est la fille de celle des deux fractions m'/n' et m''/n'' qui a le plus grand dénominateur, c'est-à-dire la fille droite de m'/n' si n'>n'', ou la fille gauche de m''/n'' si au contraire n' < n''.

Par exemple si l'on considère la fraction 5/7 alors l'algorithme de d'Euclide nous donne 5\times 3 - 7\times 2 = 1. On en déduit que 2/3 et (5-2)/(7-3) = 3/4 sont les voisines de 5/7 dans la suite de Farey d'ordre 7 ; comme 4 > 3, on a que 5/7 est la fille de gauche de 3/4 dans l'arbre de Stern-Brocot.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Stern-Brocot Tree », MathWorld

Référence[modifier | modifier le code]

Mathématiques concrètes (2e édition) de Ronald Graham, Donald Knuth et Oren Patashnik (en) (ISBN 978-2-7117-4824-2)