Présentation et fonctionnement
Description
Le rotor-router est un analogue déterministe d’une marche aléatoire sur un graphe. Dans cette étude, nous considérons un graphe orienté. À chaque sommet $v$, on fixe un ordre cyclique de ses voisins (ou de ses arêtes sortantes), et un rotor pointe vers l’un d’eux.
Règle de marche (rotor walk) : à chaque visite de $v$ par une particule, on fait tourner le rotor d’un cran dans l’ordre puis on envoie la particule le long de l’arête désormais indiquée (convention « pré-rotation ».
Ce mécanisme équilibre à long terme l’utilisation des directions : chaque sommet « sert » ses voisins à la ronde avec des déséquilibres bornés — un « hasard discipliné » [N/A].
Nous utiliserons la variante agrégation (rotor-router aggregation) : on émet des puces depuis une source ; chacune suit la marche de rotor jusqu’à rencontrer un sommet encore inoccupé, où elle s’arrête et « occupe » ce sommet. On obtient ainsi un amas dont la forme limite en 2D est (numériquement et en partie théoriquement) proche d’un disque.
Historique bref : le mécanisme a été popularisé par James Propp [N/A] sous le nom de rotor-router ; il est apparenté aux Eulerian walkers étudiés dans les années 1990 [N/A].
Fonctionnement du Rotor-Router
Pour mieux comprendre le parcours d’une particule depuis l’origine, voici les 10 premières étapes :










Figure 1 – Les premières étapes de placement
L’auteur a choisi, par convention, le sens horaire pour la rotation de chaque sommet, ainsi que l’ordre LURD.
- L pour Left
- U pour Up
- R pour Right
- D pour Down
Remarque. Chaque sommet de ce Rotor-Router est voisin de 4 autres sommets. Nous verrons dans la section 3 un autre type de Rotor-Router .

Si l’on affecte à chaque direction une couleur par exemple :

On obtient la figure suivante réalisée pour les entiers de 1 à 28 000 000.

Cliquer sur l’image pour ouvrir la vue détaillée et zoomable.
La trajectoire empruntée par la particule et performance
Il a été montré [5] que la particule arrive toujours à trouver une place vide à l’issue d’une trajectoire plus ou moins longue. Ci dessous, la représentation de 3 trajectoires placées par les particules :



Figure 5 – Différentes trajectoires
Avant d’atteindre l’extérieur du disque, la particule peut parcourir une trajectoire dont la longueur peut être supérieure aux nombres de particules déjà placées. Néanmoins la moyenne des longueurs de la trajectoire $m$ croit linéairement en fonction du nombre $n$ de particules ajoutées

Le coût de la nième particule est (avec de petites oscillations dues aux effets de maille et à la rugosité du bord).
Le travail total pour poser N particules est
Plus l’amas est grand, plus chaque particule supplémentaire coûte cher. L’algorithme, pour placer les particules, est simple et écrit en C++ (voir le code en annexe ann:pseudocode). L’ordinateur utilisé dans le cadre de ce travail permet de placer N particules selon la formule T(N) = 5,767 \times 10^{-10} N^2 secondes
L’auteur s’est limité dans la suite de ce travail à placer 28 millions de particules. soit un peu plus de 4 jours de traitement.
Les entiers dans l’amas du Rotor-Router
Comme on le voit à la figure~fig:placement, le placement de chaque particule, indicé par l’ordre de placement, défini l’entier associé à chaque case. Il est donc possible d’opérer des filtres afin de visualiser la répartition des entiers en fonction de ces filtres.Pour analyser la répartition angulaire des points entiers de l’amas Rotor Router, on partitionne le disque centré en l’origine en (k) secteurs d’ouverture égale $2\pi/k$ puis on comptabilise le nombre de points dans chaque secteur. Reportons ces valeurs sur une courbe en fonction du secteur variant sur $2\pi$ à partir de $-\pi/2$ dans le sens horaire, nous obtenons un spectre qui exprime la densité des entiers filtrés. L’ordonnée correspond à la proportion (en $%$) d’entiers observés dans le secteur.

Remarque. Comme on le voit à la fgure 2, la position d’un entier dans un cadran dépend du sens de rotation et de l’orientation initiale de chaque particule.

Résultats observés sur Rotor-Router Carré
Filtrer sur la divisibilité
Filtrer sur $n=2k$ (entiers pairs)
Commençons par filtrer les entiers de la forme $n = 2k$ avec $k \in \mathbb{N}^*$

Un zoom sur la partie inférieure de la figure au alentour de $-\pi/2$ met en évidence 4 densités \(d_i\).

De gauche à droite: $d_1 > 85$%, $d_2 = 1$, $d_3 = 0$, $d_4 < 15$%
Remarque. Le changement de densité entre $d_2$ et $d_3$ n’est pas dans l’alignement de $-\pi/2$, on constate un léger décalage approximativement de $\pi/100$ dans le cas présent. Dans la suite du document nous le définirons par $\delta\theta$. Ce décalage peut être observé sur le spectre correspondant:

Observation numérique 1. La densité des entiers de la forme $n = 2k$ avec $k \in \mathbb{N}^*$, déterminée par la dynamique du Rotor-Router Carré , décroît globalement à partir de $-\pi/2 + \delta\theta$, sur un intervalle de $2\pi$, en suivant le sens horaire.
Observation numérique 2. Hormis le changement brutal de densité à $-\pi/2$ (+$\delta\theta$), 3 autres sauts se manifestent respectivement en $-\pi$, $\pi/2$ et $0$.
Filtrer sur $n = 2k – 1$ (entiers impairs)
Filtrons les entiers de la forme $n = 2k-1$ avec $k \in \mathbb{N}^*$. Nous devrions trouver un résultat complémentaire du précédent.

Zoom sur la partie inférieure de la figure au alentour de $-\pi/2$.

Le spectre correspondant est le suivant:

Observation numérique 3. La densité des entiers de la forme $n = 2k-1$ avec $k \in \mathbb{N}^*$, déterminée par la dynamique du Rotor-Router Carré , croît globalement à partir de $-\pi/2 + \delta\theta$, sur un intervalle de $2\pi$, en suivant le sens horaire.
Filtrer sur $n = 3k$
Intéressons-nous maintenant aux entiers de la forme $n = 3k$ et, plus généralement, aux entiers de la forme $n =(2m+1)k$ avec $m \in \mathbb{N}^*$.

Observation numérique 4. La densité des entiers de la forme $n =(2m+1)k$ avec $m \in \mathbb{N}^*$, déterminée par la dynamique du Rotor-Router Carré, est globalement homogène à partir de $-\pi/2$, sur un intervalle de $2\pi$, en suivant le sens horaire.
Le spectre correspondant est le suivant:

Filtrer sur $n = 4k$
Ceux de la forme $n = 4k$

Le spectre correspondant est le suivant:

On trouve une répartition similaire à celle de la figure~fig:n2k, mais la plage de densité est plus marquée pour les $n = 4k$ .
Remarque. Pour les courbes ci-dessus, le disque a été subdivisé en $400$ secteurs. Les petites oscillations observées résultent des erreurs d’affectation d’un entier à un secteur, erreurs dont l’amplitude est inversement proportionnelle à la taille du secteur. Pour illustrer ce phénomène, nous avons également utilisé des subdivisions en $100$ et en $2000$ secteurs pour les entiers divisibles par $4$. L’allure générale de la courbe gagne néanmoins en précision avec l’augmentation du nombre de secteurs, notamment pour les décrochements constatés en $\pi$, $\pi/2$ et $0$.


Congruences et nombres premiers
Considérons les entiers $n$ de la forme $n \equiv 3 \pmod{4}$ puis $n \equiv 1 \pmod{4}$. En annexe ann:classecongruencecarre les spectres de quelques classes de congruence $b \pmod{a}$ avec $gcd(b,a)=1$.
Filtrer sur $n \equiv 3 \pmod{4}$


Filtrer sur $n \equiv 1 \pmod{4}$


Primalité
Si l’on ne retient que les nombres premiers :


Observation numérique 5. La densité des entiers premiers, déterminée par la dynamique du Rotor-Router Carré , croît globalement à partir de $-\pi/2 + \delta\theta$, sur un intervalle de $2\pi$, en suivant le sens horaire.
Position des chiffres et motifs fractals
Objectif du filtre
On note
Le chiffre de rang $k$ (position $10^k$) est $a_k$.On étudie la distribution de $a_k$ (pour un $k$ fixé) quand $n \leq N$.
Les ilots d’entiers $n$ qui obéissent à $a_3 = 0$ sont en blanc dans les figure ci-dessous.
Position $a_2 = 0$
La figure~fig:a_3_square, qui illustre le cas $a_2 = 0$ (c’est-à-dire lorsque le chiffre des centaines est nul), a été générée avec $N = 1200 \times 10^3$ sommets. Le zoom présenté dans la figure~fig:zoom_a_3_square correspond à un îlot d’entiers situé à gauche du centre de la figure.


Observation numérique 6. Les entiers $n$ qui obéissent à $a_2 = 0$, déterminée par la dynamique du Rotor-Router Carré, se disposent suivant des figures évoquant des fractales.
Position $a_3 = 0$
La figure~fig:zoom_a_4_square, correspondant au cas $a_3 = 0$ (c’est-à-dire lorsque le chiffre des millier est nul), a été générée avec $N = 28\cdot10^6$ sommets. Les zooms présentés dans les figures~fig:zoom2_a_4_square et~fig:zoom_chiffres_rang_square_1 correspondent à l’îlot d’entiers situé en bas à gauche du centre de la figure.

Observation numérique 7. Les entiers $n$ qui obéissent à $a_3 = 0$, déterminée par la dynamique du Rotor-Router Carré, se disposent suivant des motifs évoquant des fractales.



Un traitement de l’image permet de mettre en évidence le caractère fractal du Rotor-Router Carré pour $a_3 = 0$

Généralisation
L’allure générale de la figure ne dépend pas de $a_k$ ; par exemple, pour $a_3 = 0 \ldots 9$, la position des clusters sur la figure reste stable.
Observation numérique 8. Pour un $k$ donné, le parcours de $a_k \in {0,\dots,9}$ ne modifie pas l’allure de la structure. Les motifs dépendent de $k$. Ils ne sont pas perceptibles pour $k=0$ et $k=1$. Les exemples plus haut correspondent à $k=2$ et $k=3$. Pour des valeurs de $k>3$, des motifs seraient plus visibles pour $N > 50\cdot10^6$
Les observations et conjectures présentées sur cette page sont susceptibles d’évoluer à la suite de nouvelles simulations ou de retours critiques.
