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ètreConvention
Réseau mathématiqueRé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 cycleMultiplication par $-i$
État initial d’un rotor$L$, représenté par $-1$
Règle localePré-rotation
Premier départ d’un sommet$U$, représenté par $i$
Activation lors de la première occupationNon
Rang d’une cellule libre$0$
Encodage du rang$29$ bits
Encodage de l’orientation$2$ bits
Contrôle du bordExterne à 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

a+ib|a,b∈ℤ,i2=−1.{a+ib\mid a,b\in\mathbb Z}, \qquad i^2=-1.

Le réseau carré $\mathbb Z^2$ est identifié à $\mathbb Z[i]$ au moyen de l’application

κ:ℤ2⟶ℤ[i],κ(x,y)=x−iy.\kappa:\mathbb Z^2\longrightarrow\mathbb Z[i], \qquad \kappa(x,y)=x-iy.

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

x=Re⁡(z),y=−Im⁡(z).x=\operatorname{Re}(z), \qquad y=-\operatorname{Im}(z).

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é :

z∼w⟺w−z∈−1,i,1,−i.z\sim w \quad\Longleftrightarrow\quad w-z\in{-1,i,1,-i}.

La source de toutes les particules est le sommet

o=0.o=0.

Dans les coordonnées affichées, ce sommet correspond à $(0,0)$.

Déplacements élémentaires

Les quatre déplacements sont les suivants :

DirectionVariation de $(x,y)$Déplacement complexe
$L$$(-1,0)$$-1$
$U$$(0,-1)$$i$
$R$$(1,0)$$1$
$D$$(0,1)$$-i$

Ainsi,

L:z⟼z−1,U:z⟼z+i,R:z⟼z+1,D:z⟼z−i.\begin{aligned} L &: z\longmapsto z-1,\\ U &: z\longmapsto z+i,\\ R &: z\longmapsto z+1,\\ D &: z\longmapsto z-i. \end{aligned}

Le cycle comme multiplication complexe

L’ordre cyclique retenu est

L⟶U⟶R⟶D⟶L.L\longrightarrow U\longrightarrow R\longrightarrow D \longrightarrow L.

Dans la représentation complexe, ce cycle devient

−1⟶i⟶1⟶−i⟶−1.-1 \longrightarrow i \longrightarrow 1 \longrightarrow -i \longrightarrow -1.

Chaque changement de direction est obtenu par multiplication par $-i$ :

σ(ξ)=(−i)ξ.\sigma(\xi)=(-i)\xi.

En particulier,

(−i)(−1)=i,(−i)i=1,(−i)(1)=−i,(−i)(−i)=−1.\begin{aligned} (-i)(-1)&=i,\\ (-i)i&=1,\\ (-i)(1)&=-i,\\ (-i)(-i)&=-1. \end{aligned}

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é

S=10001.S=10001.

Comme $S$ est impair, le tableau possède une cellule centrale unique. Nous posons

c=S−12=5000.c=\frac{S-1}{2}=5000.

Les coordonnées informatiques $(X,Y)$ vérifient

0≤X<S,0≤Y<S.0\leq X<S, \qquad 0\leq Y<S.

La source est stockée à la position

(X,Y)=(c,c)=(5000,5000).(X,Y)=(c,c)=(5000,5000).

Passage entre les trois représentations

Les coordonnées affichées et informatiques sont reliées par

X=x+c,Y=y+c.X=x+c, \qquad Y=y+c.

Réciproquement,

x=X−c,y=Y−c.x=X-c, \qquad y=Y-c.

La coordonnée complexe associée à la cellule $(X,Y)$ est donc

z=(X−c)−i(Y−c).z=(X-c)-i(Y-c).

Inversement, pour $z\in\mathbb Z[i]$,

X=c+Re⁡(z),Y=c−Im⁡(z).X=c+\operatorname{Re}(z), \qquad Y=c-\operatorname{Im}(z).

Le domaine représenté par le tableau est le carré

{z∈ℤ[i] | |Re⁡(z)|≤5000,|Im⁡(z)|≤5000}.\left\{ z\in\mathbb Z[i]\ \middle|\ \left|\operatorname{Re}(z)\right|\leq 5000, \left|\operatorname{Im}(z)\right|\leq 5000 \right\}.

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

Δ(L)=(−1,0),Δ(U)=(0,−1),Δ(R)=(1,0),Δ(D)=(0,1).\begin{aligned} \Delta(L)&=(-1,0),\\ \Delta(U)&=(0,-1),\\ \Delta(R)&=(1,0),\\ \Delta(D)&=(0,1). \end{aligned}

Autrement dit,

L:(x,y)⟼(x−1,y),U:(x,y)⟼(x,y−1),R:(x,y)⟼(x+1,y),D:(x,y)⟼(x,y+1).\begin{aligned} L &: (x,y)\longmapsto(x-1,y),\\ U &: (x,y)\longmapsto(x,y-1),\\ R &: (x,y)\longmapsto(x+1,y),\\ D &: (x,y)\longmapsto(x,y+1). \end{aligned}

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

x2+y2\sqrt{x^2+y^2}

et

θ(z)=Arg⁡(z).\theta(z)=\operatorname{Arg}(z).

Compte tenu de la convention $z=x-iy$, l’angle peut être calculé à partir des coordonnées affichées par

θ(z)=atan2⁡(−y,x).\theta(z)=\operatorname{atan2}(-y,x).

À partir des coordonnées informatiques, cette formule devient

atan2⁡(c−Y,X−c).\operatorname{atan2}(c-Y,X-c).

Les directions principales possèdent alors les angles suivants :

DirectionNombre complexeAngle
$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

[−π2−θ(z)]2π.\left[ -\frac{\pi}{2}-\theta(z) \right]_{2\pi}.

Si le disque est partagé en $K$ secteurs, l’indice du secteur contenant $z$ est

⌊K,α(z)2π⌋,0≤jK(z)<K.\left\lfloor \frac{K,\alpha(z)}{2\pi} \right\rfloor, \qquad 0\leq j_K(z)<K.

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

𝒟=−1,i,1,−i.\mathcal D={-1,i,1,-i}.

Nous notons $\rho(z)$ l’état courant du rotor situé au sommet $z$.

Les correspondances sont :

L=−1,U=i,R=1,D=−i.L=-1, \qquad U=i, \qquad R=1, \qquad D=-i.

Configuration initiale

Avant le dépôt de la première particule, aucun sommet n’est occupé :

A0=⌀.A_0=\varnothing.

Tous les rotors sont initialement orientés vers la gauche :

ρ0(z)=−1pour tout z∈ℤ[i].\rho_0(z)=-1 \qquad \text{pour tout }z\in\mathbb Z[i].

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 :

  1. le rotor est multiplié par $-i$ ;
  2. la particule se déplace dans la nouvelle direction du rotor.

La règle locale s’écrit donc

ρ(z)⟵(−i)ρ(z),\rho(z)\longleftarrow(-i)\rho(z),

puis

z⟵z+ρ(z).z\longleftarrow z+\rho(z).

Comme l’état initial est $-1$, les départs successifs depuis un sommet suivent la séquence

i, 1, −i, −1, i, 1, −i, −1,…i,\ 1,\ -i,\ -1,\ i,\ 1,\ -i,\ -1,\ldots

c’est-à-dire

U, R, D, L, U, R, D, L,…U,\ R,\ D,\ L,\ U,\ R,\ D,\ L,\ldots

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

1,2,3,…1,2,3,\ldots

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

An=An−1∪z.A_n=A_{n-1}\cup{z}.

Chaque particule ajoute exactement un nouveau sommet à l’amas.

Trajectoire d’une particule

La trajectoire de la particule $n$ est notée

zn,0,zn,1,…,zn,ℓ(n),z_{n,0},z_{n,1},\ldots,z_{n,\ell(n)},

où

zn,0=0z_{n,0}=0

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 :

zn,t∈An−1.z_{n,t}\in A_{n-1}.

Le sommet final est libre avant l’arrivée de la particule :

zn,ℓ(n)∉An−1.z_{n,\ell(n)}\notin A_{n-1}.

Chaque incrément appartient à l’ensemble des quatre directions :

zn,t+1−zn,t∈−1,i,1,−i.z_{n,t+1}-z_{n,t} \in {-1,i,1,-i}.

En notant

ξn,t=zn,t+1−zn,t,\xi_{n,t}=z_{n,t+1}-z_{n,t},

la position finale est la somme complexe des déplacements :

∑t=0ℓ(n)−1ξn,t.\sum_{t=0}^{\ell(n)-1}\xi_{n,t}.

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)$ :

f(n)=zn,ℓ(n).f(n)=z_{n,\ell(n)}.

L’application de placement est donc

f:ℕ∗⟶ℤ[i],f:\mathbb N^*\longrightarrow\mathbb Z[i],

où

ℕ∗=1,2,3,….\mathbb N^*={1,2,3,\ldots}.

La première particule rencontre immédiatement un sommet libre et occupe l’origine :

f(1)=0.f(1)=0.

Pour chaque particule,

∑t=0ℓ(n)−1ξn,t.\sum_{t=0}^{\ell(n)-1}\xi_{n,t}.

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

f(1),f(2),…,f(N).{f(1),f(2),\ldots,f(N)}.

Comme chaque particule s’arrête sur un sommet encore libre, les valeurs $f(1),\ldots,f(N)$ sont toutes distinctes.

Par conséquent,

|AN|=N.|A_N|=N.

Le champ du rang d’occupation $T$

Définition

Nous considérons l’ensemble de tous les sommets qui finissent par être occupés :

⋃N≥1AN.\bigcup_{N\geq1}A_N.

Pour chaque sommet $z\in A_\infty$, le rang d’occupation est défini par

min⁡n≥1|z∈An.\min {n\geq1\mid z\in A_n}.

Autrement dit,

T(z)=n⟺f(n)=z.T(z)=n \quad\Longleftrightarrow\quad f(n)=z.

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 :

n→fz→Tn.n \xrightarrow{\quad f\quad} z \xrightarrow{\quad T\quad} n.

Champ observé après $N$ particules

Une simulation numérique est effectuée avec un nombre fini $N$ de particules.

Nous définissons

TN⟶1,2,…,NT_N\longrightarrow{1,2,\ldots,N}

par restriction de $T$ à $A_N$ :

TN=T|AN.T_N=T|_{A_N}.

Ainsi, pour tout $z\in A_N$,

TN(z)=T(z).T_N(z)=T(z).

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

T~N:ℤ[i]⟶ℕ\widetilde T_N:\mathbb Z[i]\longrightarrow\mathbb N

par

{TN(z),z∈AN, 0,z∉AN.\begin{cases} T_N(z),&z\in A_N,\ 0,&z\notin A_N. \end{cases}

La cellule $z$ est occupée si et seulement si

T~N(z)>0.\widetilde T_N(z)>0.

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

TN(f(n))=n.T_N(f(n))=n.

Réciproquement, pour tout sommet $z\in A_N$,

f(TN(z))=z.f(T_N(z))=z.

Les applications

f:1,…,N⟶ANf:{1,\ldots,N}\longrightarrow A_N

et

TN⟶1,…,NT_N\longrightarrow{1,\ldots,N}

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

∑n=1N#{t | 0≤t<ℓ(n), zn,t=z}.\sum_{n=1}^{N} \# \left\{ t\ \middle|\ 0\leq t<\ell(n), \ z_{n,t}=z \right\}.

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

−(−i)uN(z).-(-i)^{u_N(z)}.

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

uN(z)mod4.u_N(z)\bmod4.

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 :

#{t | 1≤t<ℓ(n), zn,t=0}.\# \left\{ t\ \middle|\ 1\leq t<\ell(n), \ z_{n,t}=0 \right\}.

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

N−1+∑n=2NRn.N-1 + \sum_{n=2}^{N}R_n.

La phase du rotor de la source est par conséquent

−(−i)N−1+∑n=2NRn.-(-i)^{ N-1+\sum_{n=2}^{N}R_n }.

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 :

i+1−i−1=0.i+1-i-1=0.

Considérons un sommet depuis lequel $u$ départs ont été effectués. Écrivons

u=4q+r,r∈0,1,2,3.u=4q+r, \qquad r\in{0,1,2,3}.

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

∑j=0r−1i(−i)j,\sum_{j=0}^{r-1}i(-i)^j,

avec la convention qu’une somme vide vaut zéro.

Les quatre valeurs possibles sont

J(0)=0,J(1)=i,J(2)=1+i,J(3)=1.J(0)=0, \qquad J(1)=i, \qquad J(2)=1+i, \qquad J(3)=1.

En regroupant tous les déplacements des $N$ premières particules selon leur sommet de départ, nous obtenons l’identité

∑z∈ANJ(uN(z)mod4).\sum_{z\in A_N} J\bigl(u_N(z)\bmod4\bigr).

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

∑n=110f(n)=3+6i.\sum_{n=1}^{10}f(n)=3+6i.

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

f(1),f(2),…,f(N)f(1),f(2),\ldots,f(N)

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,

|AN|=N.|A_N|=N.

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

TM(z)=TN(z)=T(z).T_M(z)=T_N(z)=T(z).

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

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

I(X,Y)=SY+X.I(X,Y)=SY+X.

Avec $S=10001$,

I(X,Y)=10001Y+X.I(X,Y)=10001Y+X.

En fonction de la coordonnée complexe $z$, cet indice devient

S(c−Im⁡(z))+c+Re⁡(z).S\bigl(c-\operatorname{Im}(z)\bigr) + c+\operatorname{Re}(z).

Les déplacements linéaires sont :

DirectionDéplacement complexeCoordonnées informatiquesVariation 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 :

BitsMasqueUtilisation
$31$0x80000000Indicateur d’affichage
$30$–$29$0x60000000Orientation du rotor
$28$–$0$0x1FFFFFFFRang d’occupation

Les orientations sont codées par :

0=L,1=U,2=R,3=D.0=L, \qquad 1=U, \qquad 2=R, \qquad 3=D.

Les $29$ bits de poids faible contiennent le rang d’occupation.

La valeur

00

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

536870911.536\,870\,911.

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

100020001100\,020\,001

cellules.

Chaque cellule occupant $4$ octets, la mémoire du tableau principal est

400080004 octets,400\,080\,004\ \text{octets},

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

536870911.536\,870\,911.

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

max⁡(|Re⁡(z)|,|Im⁡(z)|).\max \left( |\operatorname{Re}(z)|, |\operatorname{Im}(z)| \right).

Le rayon maximal visité est

max⁡{|z|∞ | z a été visité par l’une des N premières particules}.\max \left\{ |z|_\infty \ \middle|\ z\text{ a été visité par l’une des }N \text{ premières particules} \right\}.

La marge minimale restante avant le bord est

5000−Rvisite(N).5000-R_{\mathrm{visite}}(N).

La condition

BN>0B_N>0

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 :

|AN|=N.|A_N|=N.

Les rangs présents dans les cellules occupées doivent être exactement

1,2,…,N.1,2,\ldots,N.

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

TN(f(n))=n.T_N(f(n))=n.

Pour chaque $z\in A_N$,

f(TN(z))=z.f(T_N(z))=z.

Pour chaque sommet,

−(−i)uN(z).-(-i)^{u_N(z)}.

L’invariant complexe global doit également être vérifié :

∑z∈ANJ(uN(z)mod4).\sum_{z\in A_N} J\bigl(u_N(z)\bmod4\bigr).

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 :

f(1)=0,f(2)=i,f(3)=1,f(4)=−i,f(5)=−1,f(6)=2i,f(7)=1+i,f(8)=−1+i,f(9)=1+2i,f(10)=2.\begin{aligned} f(1)&=0,\\ f(2)&=i,\\ f(3)&=1,\\ f(4)&=-i,\\ f(5)&=-1,\\ f(6)&=2i,\\ f(7)&=1+i,\\ f(8)&=-1+i,\\ f(9)&=1+2i,\\ f(10)&=2. \end{aligned}

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é

{z∈AN |P(TN(z))}.\left\{ z\in A_N \ \middle| P(T_N(z)) \right\}.

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

{z∈AN |TN(z)≡0(mod2)}.\left\{ z\in A_N \ \middle| T_N(z)\equiv0\pmod2 \right\}.

Classe de congruence

Pour $m\geq2$ et $a\in{0,\ldots,m-1}$, nous définissons

{z∈AN |TN(z)≡a(modm)}.\left\{ z\in A_N \ \middle| T_N(z)\equiv a\pmod m \right\}.

Rang premier

L’ensemble des sommets dont le rang est premier est

{z∈AN |TN(z) est premier}.\left\{ z\in A_N \ \middle| T_N(z)\text{ est premier} \right\}.

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

exp⁡(2πiq,TN(z)m),z∈AN.\exp \left( \frac{2\pi iq,T_N(z)}{m} \right), \qquad z\in A_N.

Le champ $\Phi_{m,q,N}$ prend ses valeurs parmi les racines $m$-ièmes de l’unité.

Pour $m=4$ et $q=1$,

iTN(z).i^{T_N(z)}.

Les quatre classes modulo $4$ sont alors codées par les quatre valeurs

1, i, −1, −i.1,\ i,\ -1,\ -i.

Reconstruction d’une classe

L’indicatrice de la classe $a$ modulo $m$ s’obtient par transformée de Fourier discrète :

1m∑q=0m−1exp⁡(2πiq(TN(z)−a)m).\frac{1}{m} \sum_{q=0}^{m-1} \exp \left( \frac{2\pi iq\bigl(T_N(z)-a\bigr)}{m} \right).

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 :

  1. la phase dynamique du rotor,
−(−i)uN(z);-(-i)^{u_N(z)};
  1. la phase arithmétique du rang,
exp⁡(2πiqTN(z)m).\exp \left( \frac{2\pi iqT_N(z)}{m} \right).

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

100#(ℱP,N∩𝒮j(K))#(AN∩𝒮j(K)).100\, \frac{ \# \left( \mathcal F_{P,N} \cap \mathcal S_j^{(K)} \right) }{ \# \left( A_N \cap \mathcal S_j^{(K)} \right) }.

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

eiθ(z).e^{i\theta(z)}.

Pour $m\geq2$, $q\in{0,\ldots,m-1}$ et $k\in\mathbb Z$, nous définissons

1N−1∑z∈AN∖0Φm,q,N(z)(z|z|)k.\frac{1}{N-1} \sum_{z\in A_N\setminus{0}} \Phi_{m,q,N}(z) \left( \frac{z}{|z|} \right)^k.

En utilisant la bijection entre les rangs et les sommets, cette expression peut aussi s’écrire

1N−1∑n=2Nexp⁡(2πiqnm)(f(n)|f(n)|)k.\frac{1}{N-1} \sum_{n=2}^{N} \exp \left( \frac{2\pi iqn}{m} \right) \left( \frac{f(n)}{|f(n)|} \right)^k.

Le module

|Cq,k(m)(N)|\left|C_{q,k}^{(m)}(N)\right|

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

r1≤|z|<r2.r_1\leq|z|<r_2.

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ètreValeur ou information à publier
ModèleRé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 complexeMultiplication par $-i$
État initial$L=-1$
RèglePré-rotation
Premier départ$U=i$
Activation lors de la première occupationNon
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

z=x−iyz=x-iy

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

L=−1,U=i,R=1,D=−i,L=-1, \qquad U=i, \qquad R=1, \qquad D=-i,

et le cycle des rotors s’écrit comme une multiplication par $-i$.

L’application

f:ℕ∗⟶ℤ[i]f:\mathbb N^*\longrightarrow\mathbb Z[i]

associe à chaque particule sa position finale, tandis que

T:A∞⟶ℕ∗T:A_\infty\longrightarrow\mathbb N^*

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

−(−i)uN(z),-(-i)^{u_N(z)},

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

exp⁡(2πiqTN(z)m).\exp \left( \frac{2\pi iqT_N(z)}{m} \right).

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.

Travail en cours — v0.5 · Mise à jour : 7 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.
Défiler vers le haut