Note méthodologique de référence — formulation complexe sur le réseau des entiers de Gauss
Résumé
Nous définissons un champ discret associé à une agrégation rotor-router sur le réseau carré. Des particules numérotées $1,2,\ldots$ sont déposées successivement à l’origine. Chaque particule suit les indications des rotors jusqu’à atteindre un sommet encore libre, où elle s’arrête définitivement.
Le réseau carré est identifié au réseau des entiers de Gauss $\mathbb Z[i]$. Compte tenu de la convention d’affichage utilisée dans les simulations, où l’axe vertical est orienté vers le bas, le sommet de coordonnées $(x,y)$ est représenté par le nombre complexe $z=x-iy$.
Avec cette convention, les directions $L,U,R,D$ correspondent respectivement aux déplacements complexes $-1,i,1,-i$. L’ordre cyclique $L\to U\to R\to D\to L$ s’écrit alors comme une multiplication par $-i$.
L’application de placement $f$ associe à chaque particule sa position finale complexe. Le champ du rang d’occupation $T$ adopte le point de vue inverse : il associe à chaque sommet occupé le numéro de la particule qui l’a occupé.
Nous introduisons également l’odomètre $u_N$, qui compte le nombre de départs depuis chaque sommet au cours du placement des $N$ premières particules. Le champ d’orientation des rotors est alors entièrement déterminé par $u_N$ modulo $4$.
Cette note fixe les conventions mathématiques et informatiques utilisées dans les simulations, définit les différents champs observés et fournit des tests permettant de vérifier indépendamment une implémentation.
Mots-clés
Rotor-router, agrégation déterministe, réseau carré, entiers de Gauss, rang d’occupation, odomètre, racines de l’unité, simulation numérique, reproductibilité.
Objet et portée de la note
Dans une agrégation rotor-router, des particules sont envoyées successivement depuis une source commune. Chaque particule se déplace suivant l’état local des rotors et s’arrête lorsqu’elle atteint le premier sommet encore libre de sa trajectoire.
Une première description du résultat consiste à associer à chaque particule sa position finale. Nous notons cette application $f$.
Une seconde description consiste à associer à chaque sommet occupé le numéro de la particule qui l’a occupé. Cette valeur est appelée le rang d’occupation du sommet et elle est notée $T$.
La représentation du réseau dans le plan complexe permet de réunir dans un même langage :
- les positions des particules ;
- les quatre directions du réseau carré ;
- la phase des rotors ;
- l’odomètre modulo $4$ ;
- les phases arithmétiques associées aux congruences du rang d’occupation ;
- les orientations angulaires observées dans l’amas.
Cette identification est algébrique et géométrique. Elle ne signifie pas que les fonctions $f$ ou $T$ sont holomorphes, ni qu’elles sont définies sur un domaine continu de $\mathbb C$. Leurs domaines restent discrets.
L’objectif de cette note n’est pas d’établir une propriété arithmétique particulière. Il est de définir précisément les objets utilisés, de fixer les conventions des simulations et de fournir un protocole de validation.
Conventions de référence
Les simulations décrites dans cette note utilisent les conventions suivantes :
| Paramètre | Convention |
|---|---|
| Réseau mathématique | Réseau carré identifié à $\mathbb Z[i]$ |
| Source mathématique | $0\in\mathbb Z[i]$, équivalente à $(0,0)$ |
| Coordonnées affichées | $(x,y)$, avec $x$ vers la droite et $y$ vers le bas |
| Coordonnée complexe | $z=x-iy$ |
| Taille du tableau informatique | $10001\times10001$ cellules |
| Source informatique | $(X,Y)=(5000,5000)$ |
| Directions | $L,U,R,D$ |
| Déplacements complexes | $-1,i,1,-i$ |
| Ordre cyclique | $L\to U\to R\to D\to L$ |
| Opération complexe du cycle | Multiplication par $-i$ |
| État initial d’un rotor | $L$, représenté par $-1$ |
| Règle locale | Pré-rotation |
| Premier départ d’un sommet | $U$, représenté par $i$ |
| Activation lors de la première occupation | Non |
| Rang d’une cellule libre | $0$ |
| Encodage du rang | $29$ bits |
| Encodage de l’orientation | $2$ bits |
| Contrôle du bord | Externe à la fonction optimisée de déplacement |
Ces conventions font partie intégrante de la définition de l’expérience. La modification de l’état initial, de l’ordre cyclique, du sens de rotation ou de la convention d’axes peut modifier les champs obtenus.
Convention géométrique.
Le réseau $\mathbb Z^2$ est représenté dans le plan cartésien usuel : l’axe horizontal $x$ est orienté vers la droite et l’axe vertical $y$ vers le haut.
Les quatre voisins d’un sommet $v=(x,y)$ sont donc :
$L(v)=(x-1,y)$,
$U(v)=(x,y+1)$,
$R(v)=(x+1,y)$,
$D(v)=(x,y-1)$.
Les directions sont identifiées aux angles du plan par :
$L=-\pi,\qquad U=\frac{\pi}{2},\qquad R=0,\qquad D=-\frac{\pi}{2}$.
Les angles sont représentés dans l’intervalle $[-\pi,\pi)$.
Le réseau carré comme réseau d’entiers de Gauss
Identification complexe
Le réseau des entiers de Gauss est l’ensemble
Le réseau carré $\mathbb Z^2$ est identifié à $\mathbb Z[i]$ au moyen de l’application
Le signe négatif devant $iy$ provient de la convention d’affichage : la coordonnée $y$ augmente vers le bas, alors que la partie imaginaire positive est habituellement représentée vers le haut.
Pour un sommet complexe $z$, les coordonnées affichées sont donc
Cette identification est bijective. Les notations $(x,y)$ et $z=x-iy$ désignent le même sommet.
Adjacence sur le réseau complexe
Deux sommets $z$ et $w$ sont voisins lorsque leur différence appartient à l’ensemble des quatre unités du réseau carré :
La source de toutes les particules est le sommet
Dans les coordonnées affichées, ce sommet correspond à $(0,0)$.
Déplacements élémentaires
Les quatre déplacements sont les suivants :
| Direction | Variation de $(x,y)$ | Déplacement complexe |
| $L$ | $(-1,0)$ | $-1$ |
| $U$ | $(0,-1)$ | $i$ |
| $R$ | $(1,0)$ | $1$ |
| $D$ | $(0,1)$ | $-i$ |
Ainsi,
Le cycle comme multiplication complexe
L’ordre cyclique retenu est
Dans la représentation complexe, ce cycle devient
Chaque changement de direction est obtenu par multiplication par $-i$ :
En particulier,
Le cycle des rotors est donc un parcours des quatre racines quatrièmes de l’unité, avec un déphasage initial fixé par l’état $L=-1$.
Coordonnées informatiques
Tableau fini
Le modèle mathématique est défini sur le réseau infini $\mathbb Z[i]$. Pour des raisons de capacité mémoire, l’implémentation utilise un tableau carré fini de côté
Comme $S$ est impair, le tableau possède une cellule centrale unique. Nous posons
Les coordonnées informatiques $(X,Y)$ vérifient
La source est stockée à la position
Passage entre les trois représentations
Les coordonnées affichées et informatiques sont reliées par
Réciproquement,
La coordonnée complexe associée à la cellule $(X,Y)$ est donc
Inversement, pour $z\in\mathbb Z[i]$,
Le domaine représenté par le tableau est le carré
La translation entre le repère centré et le repère informatique ne modifie pas la dynamique du rotor-router.
Convention d’orientation des axes
Nous utilisons une convention adaptée à l’affichage informatique :
- $x$ augmente vers la droite ;
- $y$ augmente vers le bas.
Les déplacements élémentaires sont donc
Autrement dit,
L’orientation verticale est donc inverse de celle d’un repère cartésien usuel. Il s’agit uniquement d’une convention de représentation.
Angles et convention des spectres
Pour tout sommet non nul $z$, nous définissons son rayon et son angle par
et
Compte tenu de la convention $z=x-iy$, l’angle peut être calculé à partir des coordonnées affichées par
À partir des coordonnées informatiques, cette formule devient
Les directions principales possèdent alors les angles suivants :
| Direction | Nombre complexe | Angle |
| $R$ | $1$ | $0$ |
| $U$ | $i$ | $\pi/2$ |
| $L$ | $-1$ | $\pi$ |
| $D$ | $-i$ | $-\pi/2$ |
Les spectres utilisés dans les expériences précédentes commencent dans la direction $D$, à l’angle $-\pi/2$, puis parcourent le disque dans le sens horaire.
Pour rendre cette convention explicite, nous notons $[\alpha]_{2\pi}$ l’unique représentant de $\alpha$ dans l’intervalle $[0,2\pi)$. La position angulaire dans le spectre est alors
Si le disque est partagé en $K$ secteurs, l’indice du secteur contenant $z$ est
Cette définition permet de reproduire exactement l’ordre angulaire des spectres, indépendamment du langage ou de la bibliothèque graphique utilisée.
Les rotors et la règle locale
État complexe d’un rotor
Chaque sommet $z$ possède un rotor dont l’état appartient à l’ensemble
Nous notons $\rho(z)$ l’état courant du rotor situé au sommet $z$.
Les correspondances sont :
Configuration initiale
Avant le dépôt de la première particule, aucun sommet n’est occupé :
Tous les rotors sont initialement orientés vers la gauche :
Dans le tableau informatique, une cellule libre possède un rang nul et des bits d’orientation nuls. L’orientation codée par zéro est précisément $L=-1$.
Pré-rotation
La convention utilisée est une pré-rotation.
Lorsqu’une particule se trouve sur un sommet occupé $z$, les opérations suivantes sont exécutées dans cet ordre :
- le rotor est multiplié par $-i$ ;
- la particule se déplace dans la nouvelle direction du rotor.
La règle locale s’écrit donc
puis
Comme l’état initial est $-1$, les départs successifs depuis un sommet suivent la séquence
c’est-à-dire
Le premier départ depuis un sommet est donc effectué vers le haut.
Première occupation d’un sommet
Lorsqu’une particule atteint un sommet libre, elle s’y arrête immédiatement.
Le rotor de ce sommet n’est pas activé lors de cette première occupation.
Si la particule $n$ atteint un sommet libre $z$ :
- le sommet $z$ devient occupé ;
- le rang $n$ lui est attribué ;
- son rotor conserve l’état initial $-1$, correspondant à $L$.
La pré-rotation n’intervient que lorsqu’une particule ultérieure visite ce sommet déjà occupé.
Construction de l’amas
Dépôt d’une particule
Les particules sont numérotées
et sont toutes déposées à la source $0$.
Supposons que les $n-1$ premières particules aient déjà été placées et que $A_{n-1}$ soit l’ensemble des sommets occupés.
La particule $n$ est déposée en $0$.
- Si le sommet courant est libre, elle s’y arrête.
- S’il est occupé, son rotor est pré-tourné, puis la particule suit la nouvelle direction.
- Le processus est répété jusqu’à la rencontre d’un sommet libre.
Si la particule s’arrête au sommet $z$, alors
Chaque particule ajoute exactement un nouveau sommet à l’amas.
Trajectoire d’une particule
La trajectoire de la particule $n$ est notée
où
et où $\ell(n)$ est le nombre de déplacements effectués par la particule.
Pour tout $0\leq t<\ell(n)$, le sommet $z_{n,t}$ appartient à l’amas déjà construit :
Le sommet final est libre avant l’arrivée de la particule :
Chaque incrément appartient à l’ensemble des quatre directions :
En notant
la position finale est la somme complexe des déplacements :
Pour la première particule, $\ell(1)=0$ et la somme est vide.
Pseudo-code de référence
A <- ensemble vide
Pour n allant de 1 à N :
z <- 0
Tant que z appartient à A :
rho(z) <- (-i) * rho(z)
z <- z + rho(z)
Fin Tant que
ajouter z à A
enregistrer le rang n dans z
rho(z) <- -1
f(n) <- z
Fin Pour
Le point essentiel est que le déplacement utilise la nouvelle direction du rotor, après sa rotation
L’application de placement $f$
Définition
La position finale de la particule numéro $n$ est notée $f(n)$ :
L’application de placement est donc
où
La première particule rencontre immédiatement un sommet libre et occupe l’origine :
Pour chaque particule,
La fonction $f$ répond à la question :
À quel sommet complexe s’arrête la particule numéro $n$ ?
Amas après $N$ particules
Après le dépôt des $N$ premières particules, l’amas est
Comme chaque particule s’arrête sur un sommet encore libre, les valeurs $f(1),\ldots,f(N)$ sont toutes distinctes.
Par conséquent,
Le champ du rang d’occupation $T$
Définition
Nous considérons l’ensemble de tous les sommets qui finissent par être occupés :
Pour chaque sommet $z\in A_\infty$, le rang d’occupation est défini par
Autrement dit,
Le champ $T$ répond à la question :
Quelle particule a occupé le sommet $z$ ?
La fonction $f$ part d’un entier et fournit une position, tandis que $T$ part d’une position occupée et retrouve cet entier :
Champ observé après $N$ particules
Une simulation numérique est effectuée avec un nombre fini $N$ de particules.
Nous définissons
par restriction de $T$ à $A_N$ :
Ainsi, pour tout $z\in A_N$,
Le champ $T_N$ est une bijection de $A_N$ vers ${1,\ldots,N}$.
Extension par zéro
Dans l’implémentation informatique, le rang nul représente une cellule libre. Il est donc utile de définir le champ étendu
par
La cellule $z$ est occupée si et seulement si
Cette extension correspond au contenu numérique des bits de rang dans le tableau informatique.
Relation entre $f$ et $T_N$
Pour toute particule $1\leq n\leq N$,
Réciproquement, pour tout sommet $z\in A_N$,
Les applications
et
sont donc inverses l’une de l’autre.
L’odomètre et la phase des rotors
Définition de l’odomètre
L’odomètre $u_N(z)$ est le nombre total de départs effectués depuis le sommet $z$ par les $N$ premières particules.
À partir des trajectoires, il peut être défini par
L’occupation initiale d’un sommet n’est pas comptée comme un départ. En particulier, un sommet nouvellement occupé possède initialement un odomètre nul.
Orientation finale d’un rotor
Chaque départ depuis un sommet multiplie son rotor par $-i$. Comme tous les rotors sont initialement dans l’état $-1$, l’orientation après le dépôt des $N$ premières particules est
L’orientation finale dépend uniquement de $u_N(z)$ modulo $4$ :
| $u_N(z)\bmod4$ | $\rho_N(z)$ | Direction |
| $0$ | $-1$ | $L$ |
| $1$ | $i$ | $U$ |
| $2$ | $1$ | $R$ |
| $3$ | $-i$ | $D$ |
Une image colorée suivant l’orientation des rotors représente donc, à une correspondance de couleurs près, le champ
Ce champ ne doit pas être confondu avec le rang d’occupation $T_N(z)$ ni avec $T_N(z)\bmod4$.
Retours à l’origine
Pour $n\geq2$, nous notons $R_n$ le nombre de retours de la particule $n$ à l’origine après son premier départ :
Nous posons $R_1=0$.
La première particule ne quitte pas l’origine. Chacune des particules $2,\ldots,N$ quitte l’origine au moins une fois. Chaque retour supplémentaire entraîne un nouveau départ depuis l’origine.
L’odomètre de la source vérifie donc l’identité exacte
La phase du rotor de la source est par conséquent
Cette identité fournit un lien exact entre les retours à l’origine et la phase dynamique de la source. Elle ne constitue pas, à elle seule, une relation entre les retours et une propriété arithmétique des indices.
Annulation des cycles complets
Les quatre directions utilisées au cours d’un cycle complet ont une somme nulle :
Considérons un sommet depuis lequel $u$ départs ont été effectués. Écrivons
Les $4q$ premiers déplacements se regroupent en cycles complets de somme nulle. La somme vectorielle des départs depuis ce sommet dépend donc uniquement du reste $r$.
Nous définissons
avec la convention qu’une somme vide vaut zéro.
Les quatre valeurs possibles sont
En regroupant tous les déplacements des $N$ premières particules selon leur sommet de départ, nous obtenons l’identité
Le membre de gauche est la somme des positions finales des particules. Le membre de droite est entièrement déterminé par l’odomètre modulo $4$.
Cette identité complexe constitue un invariant supplémentaire pour la validation d’une simulation.
Exemple de référence : les dix premières particules
Avec les conventions définies dans cette note, les dix premières particules donnent les résultats suivants :
| $n$ | Coordonnées $(x,y)$ | Position complexe $f(n)$ | Déplacements $\ell(n)$ |
| $1$ | $(0,0)$ | $0$ | $0$ |
| $2$ | $(0,-1)$ | $i$ | $1$ |
| $3$ | $(1,0)$ | $1$ | $1$ |
| $4$ | $(0,1)$ | $-i$ | $1$ |
| $5$ | $(-1,0)$ | $-1$ | $1$ |
| $6$ | $(0,-2)$ | $2i$ | $2$ |
| $7$ | $(1,-1)$ | $1+i$ | $2$ |
| $8$ | $(-1,-1)$ | $-1+i$ | $4$ |
| $9$ | $(1,-2)$ | $1+2i$ | $3$ |
| $10$ | $(2,0)$ | $2$ | $2$ |
Le champ $T_{10}$ peut être représenté dans les coordonnées affichées par le tableau suivant :
| $y\backslash x$ | $-1$ | $0$ | $1$ | $2$ |
| $-2$ | $6$ | $9$ | ||
| $-1$ | $8$ | $2$ | $7$ | |
| $0$ | $5$ | $1$ | $3$ | $10$ |
| $1$ | $4$ |
La somme complexe des dix positions est
L’identité fondée sur l’odomètre modulo $4$ doit produire la même valeur.
Ces dix placements constituent un test simple de compatibilité entre deux implémentations.
Propriétés élémentaires
Chaque particule occupe un sommet différent
Les positions
sont toutes différentes.
En effet, une particule s’arrête uniquement lorsqu’elle atteint un sommet encore libre.
Deux particules ne peuvent donc pas recevoir le même sommet final.
L’amas contient exactement $N$ sommets
Après le dépôt de $N$ particules,
Chaque particule ajoute exactement un nouveau sommet à l’amas.
Le rang d’occupation est définitif
Lorsqu’un sommet est occupé, son rang ne change plus.
Si $M\geq N$ et $z\in A_N$, alors
Le rotor situé en $z$ peut continuer à changer d’orientation lors du passage de nouvelles particules, mais le rang d’occupation reste fixé.
Objets à ne pas confondre
| Objet | Signification |
| $A_N$ | Amas après le dépôt de $N$ particules |
| $f(n)$ | Position finale de la particule $n$ |
| $T(z)$ | Rang d’occupation définitif du sommet $z$ |
| $T_N(z)$ | Rang observé dans l’amas $A_N$ |
| $\widetilde T_N(z)$ | Champ informatique prolongé par zéro |
| $\ell(n)$ | Nombre de déplacements de la particule $n$ |
| $R_n$ | Nombre de retours de la particule $n$ à l’origine |
| $u_N(z)$ | Nombre de départs depuis $z$ |
| $\rho_N(z)$ | Orientation du rotor en $z$ après $N$ dépôts |
Une image colorée selon les rotors représente $\rho_N$, donc $u_N\bmod4$.
Une image filtrée selon les valeurs inscrites dans les cellules représente une propriété de $T_N$.
Une étude des longueurs ou des retours à l’origine porte sur les trajectoires individuelles.
Implémentation informatique
Stockage linéaire
Le tableau de $S\times S$ cellules est stocké sous la forme d’un tableau linéaire, ligne après ligne.
L’indice de la cellule $(X,Y)$ est
Avec $S=10001$,
En fonction de la coordonnée complexe $z$, cet indice devient
Les déplacements linéaires sont :
| Direction | Déplacement complexe | Coordonnées informatiques | Variation de l’indice |
| $L$ | $-1$ | $(X-1,Y)$ | $-1$ |
| $U$ | $i$ | $(X,Y-1)$ | $-S$ |
| $R$ | $1$ | $(X+1,Y)$ | $+1$ |
| $D$ | $-i$ | $(X,Y+1)$ | $+S$ |
Dans le code C++ de référence, le tableau des déplacements est donc équivalent à :
const int delta[4] = { -1, -size, +1, +size };
L’ordre du tableau est exactement celui des orientations $L,U,R,D$.
Encodage d’une cellule
Chaque cellule est représentée par un entier non signé de $32$ bits.
L’encodage actuel est :
| Bits | Masque | Utilisation |
| $31$ | 0x80000000 | Indicateur d’affichage |
| $30$–$29$ | 0x60000000 | Orientation du rotor |
| $28$–$0$ | 0x1FFFFFFF | Rang d’occupation |
Les orientations sont codées par :
Les $29$ bits de poids faible contiennent le rang d’occupation.
La valeur
est réservée à une cellule libre.
Une cellule est donc considérée comme occupée si et seulement si la partie contenant le rang est non nulle.
Lorsqu’une cellule libre est occupée :
- son nouveau rang est écrit dans les $29$ bits de poids faible ;
- ses bits d’orientation restent à zéro ;
- son rotor est donc dans l’état initial $L$.
Rang maximal représentable
Avec $29$ bits réservés au rang, la plus grande valeur représentable est
Cette limite d’encodage est indépendante des limites pratiques liées au temps de calcul, à la mémoire et à la taille du tableau.
Taille mémoire
Le tableau contient
cellules.
Chaque cellule occupant $4$ octets, la mémoire du tableau principal est
soit environ $400{,}1$ Mo en notation décimale ou $381{,}5$ Mio.
Cette valeur ne comprend pas les autres structures utilisées par le programme.
Limite du rang stockable
Avec 29 bits réservés au rang, la plus grande valeur représentable est
L’encodage actuel permet donc théoriquement de distinguer les rangs d’occupation jusqu’à cette valeur.
Cette limite est indépendante de la limite pratique imposée par la taille du tableau et par le temps de calcul.
Le tableau fini et la gestion du bord
Le bord du tableau n’est pas une propriété du modèle mathématique. Il constitue une limite de l’implémentation.
Une simulation n’est valide que si toutes les positions visitées restent dans le domaine $\Omega_S$.
La fonction optimisée de déplacement utilise des déplacements par pointeurs et ne vérifie pas explicitement les coordonnées avant chaque mouvement. La validité doit donc être garantie par le programme appelant, par une vérification externe ou par une future version intégrant directement ce contrôle.
Une simulation doit être interrompue lorsqu’un prochain déplacement risque de sortir du tableau. Les résultats postérieurs à un dépassement ne doivent pas être utilisés.
Rayon maximal visité
Le rayon euclidien de l’amas ne suffit pas à vérifier la sécurité du tableau, car une trajectoire peut s’éloigner davantage que la position finale de la particule.
Nous définissons la norme infinie par
Le rayon maximal visité est
La marge minimale restante avant le bord est
La condition
garantit qu’au moins une cellule de marge subsiste entre toute position visitée et le bord du tableau.
Validation et reproductibilité
Invariants fondamentaux
Après le dépôt des $N$ premières particules, les propriétés suivantes doivent être vérifiées :
Les rangs présents dans les cellules occupées doivent être exactement
Aucun rang ne doit apparaître deux fois.
Aucune cellule occupée ne doit posséder un rang nul.
Pour chaque $1\leq n\leq N$,
Pour chaque $z\in A_N$,
Pour chaque sommet,
L’invariant complexe global doit également être vérifié :
Enfin, toutes les positions visitées doivent rester dans le tableau alloué.
Test des dix premières particules
Une implémentation utilisant les mêmes conventions doit produire exactement :
Une différence dès ces premiers rangs indique généralement une divergence concernant :
- la convention de l’axe vertical ;
- l’état initial du rotor ;
- l’ordre $L,U,R,D$ ;
- la pré-rotation ;
- la non-activation du rotor lors de la première occupation ;
- l’ordre des déplacements dans le tableau linéaire.
Filtres appliqués au champ $T$
Définition générale
Le champ $T_N$ permet de transporter une propriété des entiers vers les sommets de l’amas.
Soit $P$ une propriété portant sur les entiers. Nous définissons l’ensemble filtré
Autrement dit, nous conservons les sommets dont le rang d’occupation satisfait la propriété $P$.
Rang pair
L’ensemble des sommets dont le rang est pair est
Classe de congruence
Pour $m\geq2$ et $a\in{0,\ldots,m-1}$, nous définissons
Rang premier
L’ensemble des sommets dont le rang est premier est
Ces définitions ne constituent pas des résultats sur la distribution des ensembles. Elles définissent les objets qui seront étudiés dans des travaux séparés.
Champs de phase arithmétique
Caractères complexes des congruences
Les classes de congruence peuvent être codées au moyen de racines de l’unité.
Pour $m\geq2$ et $q\in{0,\ldots,m-1}$, nous définissons le champ de phase
Le champ $\Phi_{m,q,N}$ prend ses valeurs parmi les racines $m$-ièmes de l’unité.
Pour $m=4$ et $q=1$,
Les quatre classes modulo $4$ sont alors codées par les quatre valeurs
Reconstruction d’une classe
L’indicatrice de la classe $a$ modulo $m$ s’obtient par transformée de Fourier discrète :
Cette identité permet de remplacer une collection de $m$ champs binaires par une famille de champs complexes.
Deux phases distinctes
Deux champs complexes interviennent désormais dans l’étude :
- la phase dynamique du rotor,
- la phase arithmétique du rang,
La première dépend du nombre de départs depuis le sommet.
La seconde dépend du numéro de la particule qui a occupé ce sommet.
Le fait que ces deux champs utilisent des racines de l’unité ne signifie pas qu’ils sont identiques. L’étude d’un éventuel couplage entre eux constitue une question séparée.
Spectres angulaires
Densité sectorielle
Soit $K$ le nombre de secteurs angulaires et $\mathcal S_j^{(K)}$ l’ensemble des sommets appartenant au secteur $j$.
Pour une propriété $P$, la densité des rangs satisfaisant $P$ dans le secteur $j$ est définie par
Cette quantité est exprimée en pourcentage.
Le nombre de secteurs $K$, l’origine angulaire, le sens de parcours et la règle d’affectation des points situés sur une frontière doivent être indiqués avec chaque spectre publié.
Moments angulaires complexes
Les histogrammes sectoriels dépendent du nombre et de la position des secteurs. Une mesure complémentaire peut être obtenue au moyen des moments angulaires complexes.
Pour $z\neq0$,
Pour $m\geq2$, $q\in{0,\ldots,m-1}$ et $k\in\mathbb Z$, nous définissons
En utilisant la bijection entre les rangs et les sommets, cette expression peut aussi s’écrire
Le module
mesure l’intensité du mode angulaire $k$ associé à la phase arithmétique choisie.
L’argument de $C_{q,k}^{(m)}(N)$ décrit l’orientation de ce mode, modulo $2\pi/k$.
Pour le réseau carré, les modes $k=1$, $k=2$ et $k=4$ sont des diagnostics naturels :
- $k=1$ mesure une dissymétrie directionnelle globale ;
- $k=2$ mesure une opposition entre deux demi-plans ;
- $k=4$ mesure une composante compatible avec la symétrie quadrangulaire.
Une valeur nulle pour un mode particulier ne démontre pas l’uniformité complète de la distribution. Elle indique seulement l’absence de la composante harmonique mesurée.
Analyse par couronnes
Un spectre global mélange les sommets proches de l’origine et ceux proches de la frontière.
Pour distinguer les effets radiaux, les mêmes densités ou moments peuvent être calculés sur une couronne
Les valeurs $r_1$, $r_2$ et le nombre de sommets retenus doivent alors être enregistrés avec le résultat.
Métadonnées associées à une expérience
Chaque expérience publiée devrait être accompagnée au minimum des informations suivantes :
| Paramètre | Valeur ou information à publier |
| Modèle | Réseau carré |
| Identification complexe | $z=x-iy$ |
| Source mathématique | $0$ |
| Source informatique | $(5000,5000)$ |
| Nombre de particules | $N$ |
| Taille du tableau | $10001\times10001$ |
| Convention des axes | $x$ vers la droite, $y$ vers le bas |
| Angle utilisé | $\theta(z)=\operatorname{atan2}(-y,x)$ |
| Cycle des rotors | $L\to U\to R\to D\to L$ |
| Cycle complexe | Multiplication par $-i$ |
| État initial | $L=-1$ |
| Règle | Pré-rotation |
| Premier départ | $U=i$ |
| Activation lors de la première occupation | Non |
| Rang d’une cellule libre | $0$ |
| Version du simulateur | À renseigner |
| Version ou hash du code source | À renseigner |
| Date de l’expérience | À renseigner |
| Compilateur et options | À renseigner |
| Matériel utilisé | À renseigner |
| Rayon maximal occupé | À renseigner |
| Rayon maximal visité | À renseigner |
| Marge au bord $B_N$ | À renseigner |
| Nombre de secteurs $K$ | À renseigner pour les spectres |
| Origine et sens du spectre | $-\pi/2$, sens horaire |
| Somme de contrôle des données | À renseigner |
Ces informations permettent de distinguer les propriétés du modèle des choix propres à une expérience informatique.
Limites de cette note
Cette note définit le champ du rang d’occupation, sa représentation complexe et sa construction numérique.
Elle ne cherche pas à démontrer :
- une propriété asymptotique particulière de l’amas ;
- l’existence d’un biais pour une classe de congruence ;
- une propriété particulière des nombres premiers ;
- une relation entre la primalité et les retours à l’origine ;
- une équivalence entre les non-multiples de $4$ et les trajectoires sans retour ;
- le caractère fractal de motifs obtenus à partir des chiffres du rang ;
- une convergence des moments angulaires complexes.
Elle ne suppose pas non plus que $f$, $T$, $u_N$ ou $\rho_N$ possèdent une extension holomorphe au plan complexe.
Ces questions nécessitent des protocoles expérimentaux et des arguments mathématiques spécifiques. Elles feront l’objet d’études séparées.
Conclusion
Nous avons défini le champ du rang d’occupation $T$ associé à une agrégation rotor-router sur le réseau carré en identifiant ce réseau aux entiers de Gauss.
La convention
permet de conserver l’orientation informatique de l’axe vertical tout en utilisant la géométrie habituelle du plan complexe.
Les quatre directions deviennent
et le cycle des rotors s’écrit comme une multiplication par $-i$.
L’application
associe à chaque particule sa position finale, tandis que
associe à chaque sommet occupé son rang d’occupation.
Pour les $N$ premières particules, $f$ et $T_N$ établissent une correspondance bijective entre les entiers $1,\ldots,N$ et les sommets de l’amas $A_N$.
L’odomètre $u_N$ fournit une description dynamique complémentaire. L’orientation des rotors est donnée exactement par
de sorte que le champ d’orientation représente le champ $u_N\bmod4$.
Les congruences du rang peuvent, de leur côté, être représentées par les champs de phase
Le langage complexe distingue ainsi deux structures :
- une phase dynamique, issue des activations des rotors ;
- une phase arithmétique, issue du rang d’occupation.
Cette formulation constitue le cadre méthodologique commun des études ultérieures consacrées aux classes de congruence, aux moments angulaires, aux retours à l’origine et aux motifs produits par les filtres arithmétiques.
Références
[1] A. E. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Propp et D. B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs, arXiv:0801.3306.
[2] L. Levine et Y. Peres, Strong Spherical Asymptotics for Rotor-Router Aggregation and the Divisible Sandpile, arXiv:0704.0688.
Les observations et conjectures présentées sur cette page sont susceptibles d’évoluer à la suite de nouvelles simulations ou de retours critiques.
