Rotor-Router carré

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 .

Figure 2 – Sens de rotation

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

Figure 3 – Une couleur par direction

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

Figure 4 – Motif du Rotor-Router lié à l’orientation de chaque cellule

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

m≈nπm \approx \frac{n}{\pi}
Figure 6 – Longueur de la trajectoire proportionnel à l’indice de la particule

Le coût de la nième particule est (avec de petites oscillations dues aux effets de maille et à la rugosité du bord).

τn=nπ+O(n) \tau_n = \frac{n}{\pi} + O(\sqrt{n})

Le travail total pour poser N particules est

T(N)=∑n≤Nτn∼∑n≤Nnπ=N22π(ΘN2)T(N) = \sum_{n \leq N} \tau_n \sim \sum_{n \leq N} \frac{n}{\pi}= \frac{N^2}{2\pi} \qquad (\Theta N^2)

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

T(N)=5,767×10−10N2secondesT(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.

Figure 7 – Répartition angulaire

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.

Figure 8 – Spectre

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}^*$

Figure 9 – Entiers de la forme n = 2k

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

Figure 10 – Zoom Entiers de la forme n = 2k

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:

Figure 11 – Entiers de la forme n = 2k

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.

Figure 12 – Entiers de la forme n = 2k − 1

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

Figure 13 – Zoom Entiers de la forme n = 2k − 1

Le spectre correspondant est le suivant:

Figure 14 – Entiers de la forme n = 2k − 1

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}^*$.

Figure 15 – Entiers de la forme n = 3k

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:

Figure 16 – Entiers de la forme n = 3k

Filtrer sur $n = 4k$

Ceux de la forme $n = 4k$

Figure 17 – Entiers de la forme n = 4k

Le spectre correspondant est le suivant:

Figure 18 – Entiers de la forme n = 4k

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$.

Figure 19 – Entiers divisibles par 4 – 100 secteurs
Figure 20 – Entiers divisibles par 4 – 2000 secteurs

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}$

Figure 21 – Entiers de la forme n ≡ 3 (mod 4)
Figure 22 – Spectre des entiers n ≡ 3 (mod 4)

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

Figure 23 – Entiers de la forme n ≡ 1 (mod 4)
Figure 24 – Spectre des entiers n ≡ 1 (mod 4)

Primalité

Si l’on ne retient que les nombres premiers :

Figure 25 – Entiers de la forme n est premier)
Figure 26 – Spectre n est premier

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

n=∑k≥0ak10k,ak∈0,…,9n = \sum_{k \geq 0} a_k \, 10^k, \quad a_k \in {0,\dots,9}

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.

Figure 27 – $a_2 = 0$avec $N = 1200 \times 10^3$
Figure 28 – zoom $a_2 = 0$

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.

Figure 29 – $a_3 = 0$ avec $N = 28\cdot10^6$

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.

Figure 30 – zoom $a_3 = 0$
Figure 31 – zoom $a_3 = 0$
Figure 32 – Les chiffres correspondant aux sommets encadrés ci dessus (12×18)

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

Figure 33 – Traitement de l’image du Rotor-Router Carré $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$

Travail en cours — v0.1 · Mise à jour : 5 août 2026.
Les observations et conjectures présentées sur cette page sont susceptibles d’évoluer à la suite de nouvelles simulations ou de retours critiques.
References
    Défiler vers le haut