← nimbers

Les boucles de la roue

Trois anneaux de points, reliés par les rayons, et un bit posé sur chaque rayon. Chaque ruban binaire dessine une boucle qui passe une fois et une seule par tous les points de la roue, sauf les deux rubans constants. Basculez les bits, faites tourner la roue : le petit théorème de Fermat est dessiné dedans.

Roue à trois anneaux et sa boucle
La boucle, en garance, passe une fois par chacun des points. En teinte dorée, le côté du centre. Les pastilles du bord portent le ruban : touchez un rayon pour basculer son bit.

La roue déroulée

Les trois anneaux à plat, l'anneau intérieur en bas, le centre en dessous. Chaque colonne est un rayon, et son bit est au-dessus : touchez-le pour le basculer. Après le dernier rayon, on revient au premier.

Sous chaque secteur, sa lettre : S quand la boucle le traverse en trois brins, i ou e quand elle n'y passe que par un brin, sur l'anneau intérieur ou extérieur.

Un ruban, une boucle

Sur une roue de trois anneaux de L points, reliés par ses L rayons, cherchons les boucles qui passent une fois et une seule par chacun des 3L points, en ne suivant que les arcs d'anneau et les rayons. C'est le problème du voyageur de commerce de la grille, enroulé sur un cylindre (Carnet Mathématique, L·115 ; ces boucles sont la fiche L·118).

Celles qui font le tour du centre ont une description parfaite. Entre deux rayons voisins, la boucle traverse le secteur soit par un seul brin, sur l'anneau intérieur ou sur l'anneau extérieur, soit par trois brins en S. Et les brins simples alternent forcément : intérieur, extérieur, intérieur… Il suffit donc de poser un bit sur chaque rayon. Deux rayons voisins portant le même bit encadrent un S ; un passage de 0 à 1, dans le sens des aiguilles d'une montre, est un brin intérieur, et un passage de 1 à 0 un brin extérieur. Les changements de bit alternent d'eux-mêmes, et tout ruban donne une boucle, sauf les deux rubans constants : ils ne font que des S, et chaque anneau se referme sur lui-même. Trois cercles, pas une boucle. D'où

boucles qui font le tour = 2L − 2

C'est la suite A000918 de l'OEIS : 6, 14, 30, 62, 126, 254… Elle compte aussi les parties d'un ensemble de L éléments qui ne sont ni vides ni pleines, et c'est le même objet vu autrement : l'ensemble des rayons qui portent un 1. Vérifié en dressant toutes les boucles par force brute jusqu'à L = 12, et en construisant celles de tous les rubans jusqu'à L = 14. Chaque rayon ajouté double le compte : la roue à trois anneaux garde exactement un bit par rayon.

Fermat sur la roue

Faire tourner la roue d'un cran fait tourner le ruban, donc la boucle. Une boucle ne revient sur elle-même qu'au bout de d crans, où d est la période de son ruban, un diviseur de L. Si L est premier, seule la rotation complète la ramène : les 2L − 2 boucles se rangent par paquets de L, et

L divise 2L − 2

C'est le petit théorème de Fermat (L·40 du Carnet), et sa preuve par les colliers, dessinée sur une roue. Pour L quelconque, le lemme de Burnside compte les boucles à rotation près :

(1/L) Σd | L φ(d) 2L/d − 2

soit 2, 4, 6, 12, 18, 34, 58, 106, 186, 350 pour L = 3 à 12 : le nombre de colliers binaires (suite A000031), moins les deux colliers unis. La même suite compte les polynômes irréductibles sur deux éléments dont le degré divise L. Les boucles qui ne viennent d'aucune roue plus petite, celles de période exacte L, se comptent par la fonction de Möbius, Σd | L μ(L/d) 2d : 6, 12, 30, 54, 126… (A027375).

L'argument vaut quel que soit le nombre d'anneaux, dès qu'il y en a deux : une boucle qui revient sur elle-même après un seul cran utiliserait les mêmes arêtes dans tous les secteurs, donc des anneaux entiers, et ne passerait pas par tous les points. Pour L premier, le nombre de boucles de la roue est donc toujours un multiple de L : avec quatre anneaux et sept rayons, 1 484 = 7 × 212.

Les boucles qui restent sur place

Quand L est pair, d'autres boucles ne font pas le tour : elles enferment un morceau de couronne, sans le centre. Avec trois anneaux, il y en a L · 2L/2 − 1, soit 8, 24, 64, 160 pour L = 4, 6, 8, 10 ; la formule est vérifiée jusqu'à 12, mais nous n'en avons pas de démonstration. Le total, 6, 22, 30, 86, 126, 318, 510, 1 182…, est la ligne des trois anneaux de la table A359855 de l'OEIS.

Une loi de parité décide de tout. Une boucle qui ne fait pas le tour a une longueur paire, comme le bord de toute région faite de cases carrées ; une boucle qui fait le tour une fois a la parité de L. Avec r anneaux, la boucle a rL arêtes : si r et L sont impairs, toutes les boucles font le tour ; si r est pair et L impair, aucune.

À l'infini

Infiniment de rayons. Le compte double à chaque rayon, et les boucles qui restent sur place, de l'ordre de √2 par rayon, deviennent négligeables : presque toutes les boucles font le tour. Les roues s'emboîtent comme celles de la roue lcm : un ruban de période d vit sur toute roue dont le nombre de rayons est un multiple de d, recopié autant de fois qu'il faut. Sur la roue de lcm(1, …, m) rayons, toutes les boucles de toutes les roues d'au plus m rayons sont donc présentes. Les rubans de la roue lcm eux-mêmes, un 1 sur chaque multiple de k, sont des boucles, avec 2L/k brins simples. À la limite, une boucle devient un ruban infini : périodique, elle se referme sur une roue finie ; non périodique, elle ne se referme jamais, comme le développement binaire d'un nombre irrationnel ne se répète jamais.

Infiniment d'anneaux. Le ruban binaire ne suffit plus dès quatre anneaux, et la croissance par point monte avec le nombre d'anneaux. Elle vaut exactement 21/3 ≈ 1,26 avec trois anneaux. D'après la table A359855, elle est d'environ 1,34, 1,36, 1,38 et 1,40 avec cinq à huit anneaux. Elle se rapproche lentement de 1,4728, la constante de la grille infinie, qui n'est connue que numériquement (Jacobsen et Kondev, 1998). À l'infini en anneaux, la roue devient le plan, et la simplicité binaire se perd : la mémoire nécessaire d'un secteur au suivant grossit sans fin (L·116 du Carnet).

Références