L’arbre de Calkin-Wilf : toutes les fractions, une seule fois

Intervenant 10:00

Bienvenue dans le podcast du magazine Tangente pour cette nouvelle plongée au cœur des mathématiques. Je suis absolument ravie de vous embarquer aujourd'hui. Pour commencer, j'ai envie de citer le célèbre mathématicien Léopold Kronecker. Il a dit un jour « Dieu a fait les nombres entiers, tout le reste est l'œuvre de l'homme ».

Intervenant 20:22

C'est une entrée en matière fantastique, vraiment. Parce que ça sous-entend que les nombres 1, 2, 3, c'est en quelque sorte la matière première de l'univers, tu vois. La fondation naturelle. Et que tout le reste, surtout l'immense système des fractions, ce serait juste un bricolage artificiel de l'esprit humain.

Intervenant 10:40

Finité de toutes les fractions existantes.

Intervenant 20:43

Ouais, c'est une construction qui donne littéralement le vertige. Et le but de notre discussion d'aujourd'hui, c'est d'explorer comment cet arbre génère absolument chaque fraction concevable, sans en oublier une seule. Et on va voir que ça révèle des connexions complètement dingues avec l'informatique ou même l'architecture de la nature.

Intervenant 11:00

Je promets à ceux qui nous écoutent que ça va être plein de rebondissements. Même les concepts qui ont l'air un peu abstraits au début vont se transformer en énorme moment d'illumination, je vous le garantis. Alors, il faut bien commencer par le début, la toute première fraction, l'origine du système.

Intervenant 21:17

Exactement. Le texte l'appelle, de manière très poétique d'ailleurs, lève des fractions. C'est tout simplement la fraction 1 sur 1.

Intervenant 11:25

L’ève des fractions, j'adore. Donc à partir de cette Ève, on applique une règle d'une simplicité vraiment enfantine pour créer les générations suivantes. Chaque fraction mère, disons de la forme A sur B, donc avec A en haut le numérateur et B en bas le dénominateur.

Intervenant 21:43

C'est ça.

Intervenant 11:43

Eh bien cette mère donne systématiquement naissance à deux fractions filles.

Intervenant 21:47

Et la mécanique repose uniquement sur l'opération la plus basique du monde, l'addition, rien d'autre. La première fille, qu'on appelle la Benjamine, elle est toujours plus petite que sa mère. Et pour la calculer, c'est tout bête. On garde le numérateur intact en haut, donc A, et en bas, on additionne le numérateur et le dénominateur de la mère, ce qui donne A divisé par A plus B.

Intervenant 12:08

D'accord, je vois le truc. Donc le chiffre du haut glisse simplement à sa place et en bas on fait la somme. Et si je suis bien la logique, pour la deuxième fille, l'aînée, on inverse le processus pour qu'elle soit plus grande.

Intervenant 22:20

Ouais, c'est exactement l'inverse.

Intervenant 12:21

Donc cette fois c'est en haut qu'on additionne les deux termes, le nouveau numérateur devient A plus B et on garde le dénominateur de la mère, le B, intact en bas. Donc ça fait A plus B divisé par B. On devrait peut-être faire le test avec une vraie fraction, juste pour que tout le monde visualise bien.

Intervenant 22:37

Carrément. Prenons par exemple 22 sur 7, la fameuse approximation de puits.

Intervenant 12:42

Super exemple ! Donc 22 sur 7, c'est notre mère. Le A vaut 22 et le B vaut 7. Si je calcule la benjamine, je garde le 22 en haut et en bas, je fais 22 plus 7, ça fait 29. La benjamine, c'est donc 22 sur 29.

Intervenant 23:00

Parfait ! Et pour l'aîné de cette même mère, on additionne en haut, donc 22 plus 7, ça donne 29, sur le dénominateur qui reste à 7. L'aîné est donc 29 sur 7. C'est fou la symétrie du truc. Et ce processus, il faut imaginer qu'il se répète à l'infini. C'est une vraie division cellulaire mathématique. Chaque fille devient une mère qui crée une benjamine et une aînée, et ainsi de suite.

Intervenant 13:24

Moi, ce qui me fascine avec cette division cellulaire de l'ADN mathématique, c'est quand on regarde les extrémités de cet arbre géant. Si je pars de l'Ève 1 sur 1 et que je décide de descendre perpétuellement sur la branche tout à gauche, genre je ne génère que des benjamines, à l'infini.

Intervenant 23:41

Ah oui, c'est très intéressant de regarder

Intervenant 13:43

les bords. En appliquant la règle A sur A plus B, en boucle, le A commence à 1, et puisqu'on le garde en haut pour chaque benjamine, il ne changera jamais 1. Par contre, en bas, on ajoute le numérateur à chaque fois. Donc la première benjamine, c'est 1 sur 2, sa benjamine à elle garde le 1 en haut et fait 1 plus 2 en bas, donc 1 sur 3. Puis 1 sur 4, 1 sur 5.

Intervenant 24:04

Exact. Du coup, toute la lisière gauche de l'arbre, ce n'est que la suite des inverses des nombres entiers. Et comme ce système est d'une symétrie parfaite, si tu observes la branche tout à droite, la lignée pure des aînés, c'est l'inverse.

Intervenant 14:19

Laisse-moi deviner un décanique. La règle des aînés, c'est A plus B sur B. Ça veut dire que le dénominateur B en bas, qui commence à 1, va rester intact tout le temps. Et en haut, on ajoute 1 à chaque génération. Donc ça donne 2 sur 1, 3 sur 1, 4 sur 1.

Intervenant 24:37

C'est ça. La lisière droite de l'arbre, ce sont simplement les nombres entiers purs. Un, deux, trois, quatre.

Intervenant 14:43

Mais c'est génial ! Les extrêmes bordent le système de façon hyper ordonnée et toute l'infinie complexité des autres fractions, elle bourgeonne et s'entremêle au milieu.

Intervenant 24:52

Et ça se ramifie de façon exponentielle, tu sais. À chaque nouvelle ligne, le nombre de fractions double.

Intervenant 14:57

Ouais, alors justement, c'est là que j'ai une question. Ok, décortiquons ça. Avec cette croissance vertigineuse, si j'attrape une fraction complètement au hasard, disons à la millième génération, tout en bas de cet arbre géant, est-ce que ce n'est pas un cauchemar absolu de retrouver sa mère aînée ? Il faut la carte complète, non ?

Intervenant 25:17

Ben, figure-toi que non. C'est même d'une simplicité redoutable. La réversibilité est vraiment la clé de voûte de l'arbre de Calkin-Wilf. Puisque la naissance utilise l'addition, la règle pour remonter à la mer utilise tout bêtement la soustraction.

Intervenant 15:31

Ah, juste une soustraction ?

Intervenant 25:32

Ouais, juste une soustraction. Il suffit de regarder la valeur de ta fraction.

Intervenant 15:36

Attends, laisse-moi essayer de trouver la logique. Si je prends une fraction qui est plus petite que 1, genre 22 sur 29, le haut est plus petit que le bas, c'est obligatoirement une benjamine, on est d'accord ?

Intervenant 25:49

Complètement, les benjamines sont toujours inférieurs à 1.

Intervenant 15:53

Donc, sa mère avait le même numérateur en haut, parce que la règle garde le chiffre intact, le 22 reste 22. Et le dénominateur de notre Benjamine, 29, c'était le haut plus le bas de la mère. Donc, si je soustrais le 22 du 29...

Intervenant 26:08

Tu retombes sur 7.