Les piles de sable Kadanoff

Introduction aux piles de sable Kadanoff 

 Le modele de pile de sable Kadanoff, d’apres le nom du physicien Leo P. Kadanoff, est un systeme dynamique discret g ènéralisant le modele de pile de sable SPM. Ce mod èle, que nous imageons par des grains cubiques se deplac¸ant de colonne parfaitement empil ée en colonne parfaitement empilee, a davantage pour objet la compr éhension des mecanismes d’ émergence , et de la notion de complexité, que de simuler l’eboulement de sable d’un point de vue physique. Il est d éfini à partir d’une regle locale tr ès simple d ècrivant les mouvements des grains, et presente des comportements difficiles à pr èdire et à expliquer. Dans ce chapitre, nous commencerons par une breve pr èsentation du modele tel que Leo P. K adanoff et al. l’ont introduit, c’est-a-dire comme un extension du modele BTW. Nous d èfinirons ensuite formelle- ment le modele de pile de sable Kadanoff tel que nous le consid èrerons dans la suite du manuscrit, donnerons des eléments de vocabulaire, et établirons la conservation du nombre de grains au cours de la dyna- 39 – 40 Chapitre 2. Introduction aux piles de sable Kadanoff mique. Nous montrerons l’unicite du point fixe atteint, et pr ésenterons la structure de treillis de l’ensemble des configurations qu’il est possible de visiter a partir d’une configuration origine. Le Chip Firing Game, dont notre modele est une sous-classe, fera une succincte apparition, et lais- sera la place a quelques r èsultats pr éliminaires pour nous familiariser àvec le formalisme. Nous aborderons enfin la complexite algorithmique de predire la taille des avalanches, et la derni ére partie de ce chapitre sera consacreeà la formulation d’une conjecture sur la forme des points fixes du modele, dont la recherche d’une preuve formelle est l’objet des cha- pitres qui suivent. Pour simplifier les discussions, nous considererons que la direction dans laquelle les grains s’eboulent est la droite. 

Definition originale

Le modele de pile de sable que nous allons ètudier par la suite a été introduit comme un automate cellulaire sous le nom de ! modele de pile de sable unidimensionnel limite non-local  » en 1989, par les physiciens Leo P. Kadanoof, Sidney R. Nagel, Lei Wu, et Su-min Zhou [KNW+89]. Leur objectif etait de d éfinir des variantes du mod éle de tas de sable BTW presentant également un ph énom éne d’auto-organisation critique, ce qu’il jugent concluant dans leur etude, pour les m émes raisons qu’exposees dans la partie . Informellement, modele de pile de sable unidimensionnel  » doit etre compris comme faisant r ˆ eférence au modele de tas de sable BTW en une dimension, d èfini quelques ann ées plus tot par Per B ˆ ak, Chao Tang, et Kurt Wiesenfeld [BTW87 ; BT88] ; l’adjectif ! limité  » signifie que le nombre de grains se deplac¸ant par l’application de la regle est fix è par une constante ; et ! non-local  » que les grains ne se deplacent pas uniquement d’une colonne à sa voisine de droite, mais s’eboulent sur plusieurs colonnes adjacentes. Quatre modeles ont ainsi ètéétudi és d’un point de vue physique. Sur un support de L colonnes, S “ J0 ; L 1K, une configuration est une assignation pour chaque colonne i d’une quantite de grains hi , et la pente a l’indice i est ainsi definie par zi “ hi hi1. Nous conservons la condition d’un bord ferme sur la gauche, et ouvert sur la droite : z1 “ 0 et hi “ 0 pour i ą L. La regle d’it èration peut étre appliqu ˆ eeà l’indice i si sa pente est strictement plus grande que la valeur critique globale zc . Dans tous ces modeles, une quantit è de grains d énot éé ni tombe de la colonne i. Si hi ą zc alors hi Ñ hi ni (tous les modeles) ènsuite, plusieurs variations sont proposees, tout d’abord concernant la quantite de grains qui tombent de la colonne i. ni “ p (modele limit è) ni “ zi p (modele illimit è)àvec p une constante. La seconde variation concerne les colonnes sur lesquelles ces grains sont repartis. hi1 Ñ hi1 ni (modele local) hij “ hij 1 pour j “ 1, 2, . . . , ni (modele non-local) Ceci defini quatre mod éles, chacun comportant deux param ètres : zc , qui determine quand la r égle peut ètre appliqu ˆ ee, et p, qui determine le nombre de grains qui se deplacent. Nous avons d éj à discut è du fait que la valeur de zc n’a pas d’importance pour la comprehension du mod éle, puisqu’il equivaut simplement à un choix d’origine (partie 1.2.1 sur la definition du mod éle ASM). Remarquons que les modeles limit ès g énéralisent tous deux le mod éle BTW, que nous retrouvons pour p “ 1 et zc “ 1. De meme que le mod ˆ ele SPM est une variante du mod èle BTW, le modele de pile de sable Kadanoff est une variante du mod èle ! unidimensionnel limite local  » present é ici, et nous d énoterons ce dernier KBTW (Kadanoff Bak-Tang-Wiesenfeld). KBTW est defini sur un support fini S, qui comporte des bords lui permettant de tendre vers un ensemble de configurations recurrentes (la dynamique de ces configura- tions a etéétudi ée pour p “ 2 [GK93b]). Le modele que nous allons ètudier peut étre vu comme le mod ˆ ele ! unidimensionnel limite local  » sur un support S infini, de telle sorte que nous etudierons le comporte- ment transient de la pile de sable, avant qu’elle n’atteigne l’ensemble des configurations recurrentes. Nous avons d éj à discut è lors du passage du modele BTW au mod èle SPM (section 1.3.1), du fait que les attributs qui rendent le systeme int èressant du point de vue de la complexité semblent conserves. 

Definition et état de l ’art

Nous commenc¸ons par donner une definition informelle. Le mod éle de pile de sable Kadanoff KSPM (Kadanoff Sand Pile Model), est un systeme dynamique discret —en espace et en temps— decrivant l’ éboulement d’un nombre fini N de grains empiles. à chaque application de la r ègle d’iteration, un nombre de grains fix é par un param étre p se deplacent, jusqu’a l’obtention d’une configuration stable. La r ègle est la suivante : si la difference de hauteur entre une colonne et celle qui est à sa droite èst strictement superieure à p, alors p grains peuvent s’ebouler de cette  colonne, un grain se posant sur chacune des p colonnes adjacentes sur la droite, comme present é sur la figure 2.1. Le parametre p est fixe, et ne change pas au cours de la dynamique. Un exemple d’application de la regle jusqu’ a l’obtention d’une configuration stable est propos è en fi- gure 2.2. Dans la suite, le symbole p designera toujours le param étre du modele. > p Figure 2.1 – Regle d’it èration du mod éle de pile de sable Kadanoff pour un parametre p. Sur cet exemple, p “  Figure 2.2 – Une possible suite d’iterations pour p “ 2 a partir d’une configuration constituee de N “ 24 grains empiles en colonne 0, jusqu’ à une configuration stable. La regle est appliqu èe selon le mode s équentiel (a une unique colonne a chaque it èration), et les fl éches sont ètiquet ées par la colonne a laquelle la r ègle est appliqu èe. Dans la partie suivante, nous proposons deux definitions équivalentes du modele. Pour varier le vocabulaire, nous utiliserons les termes sui- vants comme synonymes : colonne et indice ebouler , tomber et tirer iteration , etape ét transition

Configurations et regle d’it èration 

Les configurations du modele de pile de sable KSPM admettent dif- ferentes repr ésentations. Les trois repr ésentations les plus naturelles uti-lisent les notions de : hauteur, pente et action. Nous commencerons par definir les configurations sous forme de suite de hauteurs, et ensuite sous forme de suite de pentes, qui est la principale representation que nous manipulerons. Nous presenterons deux d éfinitions équivalentes du modele, la premi ère ètant plus naturelle, et la seconde plus appropri éé pour les developpements formels. Nous reviendrons par la suite sur la notion d’action d’une colonne. hauteur L’espace des configurations dans la representation en hauteurs est defini comme l’ensemble des suites infinies d écroissantes et ulti- mement nulles d’entiers naturels, dans lesquelles chaque entier represen- te un nombre de grains empiles. Soit h “ phiqiPN une configuration, hi est le nombre de grains sur la colonne i. Nous obtenons ainsi la definition suivante.

Hauteurs

Le modele de pile de sable Kadanoff pour un parametre fix è p, KSPM(p), est defini par deux ensembles. Configurations. L’ensembles des suites infinies decroissantes et ulti-mement nulles d’entiers naturels. Ch “ $ ’& ’% phiqiPN : hi P N pour tout i hi hi1 ě 0 pour tout i D i0 tel que @ i ě i0 : hi “ 0 , /. /- Regle d’it èration . Nous avons une transition de la configuration h a la configuration h 1 sur la colonne i, denot éé h i Ñ h 1 , si $ ’& ’% h 1 i “ hi p h 1 j “ hj 1 pour j P Ji 1 ; i pK h 1 j “ hj pour j R Ji ; i pK. Nous dirons egalement que la colonne i est tireé lorsque nous appliquons la regle d’it èration à la colonne i. D’apres la d èfinition de l’en- semble des configurations Ch , une condition pour qu’un indice i soit tireést bien que hi hi1 ą p, car dans le cas contraire h 1 i h 1 i1 ă 0 et donc h 1 R Ch . Le symbole h designera toujours une configuration repr ésent éé par une suite de hauteurs phiqiPN. La regle est appliqu èeà une seule position a chaque it èration, selon le mode sequentiel. pente Dans le but de ne considerer que les hauteurs relatives entre les colonnes, ce qui permet d’avoir une representation uniformis ée (qui ne depend pas de la position et de sa hauteur), nous utiliserons principa- lement la representation sous forme de suite de differences de hauteur , ou  pentes, dans l’espace des suites infinies et ultimement nulles d’entiers naturels. Soit b “ pbiqiPN une configuration, nous avons ainsi bi “ hi hi1 pour tout i. La definition 2.2 suivante est une reformulation de la 2.1, et defini le m éme syst ˆ eme dynamique discret. Definition 2.2. (Pentes) Le modele de pile de sable Kadanoff pour un parametre fix è p, KSPM(p), est defini par deux ensembles. Configurations. L’ensembles des suites infinies et ultimement nulles d’entiers naturels. Cb “ # pbiqiPN : bi P N pour tout i D i0 tel que @ i ě i0 : bi “ 0 + Regle d’it èration . Nous avons une transition de la configuration b a la configuration b 1 sur la colonne i, denot éé b i Ñ b 1 , si $ ’’’& ’’’% b 1 i1 “ bi1 p si i ‰ 0 b 1 i “ bi pp 1q b 1 ip “ bip 1 b 1 j “ bj pour j R ti 1, i, i pu. Nous pouvons de nouveau remarquer qu’une condition pour que l’indice i soit tire est que bi ą p, car dans le cas contraire b 1 i ă 0 et donc b 1 R Cb . Le symbole b designera toujours une configuration repr ésent éé par une suite de pentes pbiqiPN. La regle est encore une fois appliqu èeà une seule position a chaque iteration, selon le mode s équentiel. équivalence des deux definitions La bijection entre Ch et Cb pour observer que les definitions 2.1 et 2.2 decrivent bien le m éme mod ˆ ele èst evidemment celle qui a une suite phiqiPN associe la suite pbiqiPN telle que bi “ hi hi1 pour tout i. Cette bijection f : Ch Ñ Cb commute avec l’application de la regle d’it èration. # @ h, h 1 P Ch telles que h i Ñ h 1 : fphq i Ñ fph 1 q @ b, b 1 P Cb telles que b i Ñ b 1 : f 1 pbq i Ñ f 1 pb 1 q Dans la suite, nous ne ferons pas de distinction entre une configuration et ses representations.

Notations

Nous presentons quelques notations et éléments de vocabulaire, pour certains herit és du mod éle de pile de sable SPM pr èsent é en section 1.3, ainsi qu’une premiere remarque sur la conservation du nombre de grains. Tout d’abord, soulignons que le modele est non deterministe car la regle est appliqu èe de fac¸on s équentielle. Pour une configuration b, nous dirons que la colonne i est instable dans b si bi ą p. Une configuration b est stable, ou un point fixe, si aucune transition n’est possible depuis b, c’est-a-dire si toutes ses colonnes sont stables, bi ď p pour tout i. Nous noterons b Ñ b 1 lorsqu’il existe un indice i tel que b i Ñ b 1 , et nous appellerons b 1 un successeur de b. La cloture r ˆ eflexive et transitive de Ñ est denot éé ˚Ñ, et nous dirons que la configuration b 1 est accessible, ou atteignable depuis la configuration b si b ˚Ñ b 1 . Pour tout ensemble A Ď N et toute suite c “ pciqiPA, nous designerons la sous-suite de c induite par l’ensemble d’indices B Ď A par cB. Par exemple, bJn ; 8J designera la configuration b a partir de l’indice n. loi de conservation du nombre de grains Nous verifions ais ément que le nombre N de grains est conserve par l’application de la r égle d’iteration. Pour une configuration phiqiPN ou pbiqiPN nous pouvons definir N par N “ ÿ iPN hi “ ÿ iPN pi 1q bi et pour h j Ñ h 1 nous avons d’apres la r ègle de transition ř iPN h 1 i “ ř iPNzJj ; jpK hi phj pq ř iPJj1 ; jpK phi 1q “ ř iPN hi . L’equivalence des deux d éfinitions nous assure qu’il en est de m éme ˆ pour la representation pbiqiPN.

Structure de treillis

Avant de presenter un r ésultat sur la structure de treillis de l’en- semble des configurations atteignables depuis une configuration du modele KSPM, nous commencerons par montrer que le mod èle est conver- geant, en suivant une methode tr és classique dans l’ ètude des syst émes dynamiques discrets. proprieté du diamant Le modele KSPM poss ède la proprieté du dia- mant : si b Ñ b 1 et b Ñ b 2 , alors il existe une configuration b 3 telle que b 1 Ñ b 3 et b 2 Ñ b 3. Cette proprieté est v érifi ée pour les m émes raisons que dans le mod ˆ ele SPM : si deux indices differents i et j peuvent etre tir ˆ es, alors l’ éboulement de l’indice i n’empechera pas l’ ˆ eboulement de l’indice j a l’ ètape de temps suivante car la pente a l’indice j n’aura pas diminue, et inversement ; quel que soit l’ordre dans lequel nous effectuons les transitions, nous atteignons la meme configuration, par commutativit ˆ e de l’ad- dition qui est le seul operateur arithm étique utilis é dans l’applica- tion de la regle d’it èration. convergence et point fixe La convergence est la proprieté suivante : si b ˚Ñ b 1 et b ˚Ñ b 2 , alors il existe une configuration b 3 telle que b 1 ˚Ñ b 3 et b 2 ˚Ñ b 3. b b 0 b 00 b 000 ∗ ∗ ∗ ∗ Proposition 2.3. Le modele KSPM est convergent. Demonstration. De la meme fac¸on que pour le mod ˆ ele SPM, nous pou- vons montrer que toute suite d’iterations termine en d éfinissant la fonc- tion d’energie 1 suivante, qui associe a une configuration un entier (cha- que grain compte pour sa propre hauteur dans la somme). E : Ch Ñ N h ÞÑ Ephq “ ř iPN ř hi j“0 j Nous remarquons alors que l’application de la regle fait strictement decroitre cette énergie : h Ñ h 1 ñ Ephq ą Eph 1 q. De plus, Ephq ě 0 pour toute configuration h P Ch . Comme il n’y a pas de suite infinie decroissante d’entiers naturels, toute suite de transitions termine. 1. Nous utilisons le terme fonction d’energie pour designer une valuation des configu- rations.  La terminaison et la proprieté du diamant impliquent la conver- gence du systeme (r èsultat classique sur les syst émes dynamiques dis- crets [BN98]). Soient trois configurations b, b 1 et b 2 telles que b ˚Ñ b 1 et b ˚Ñ b 2 . Sans perte de genéralit é, consid érons que la plus longue de ces deux derivations est celle de b a b 1 , qui comporte un nombre fini n d’etapes (propri été de terminaison). Nous montrons le r ésultat par induction sur n en utilisant la proprieté du diamant selon le sch éma sui- vant, qui nous assurera qu’il existe une configuration b 3 telle que b .Pour n “ 0, le resultat est évident avec b 3 “ b. Supposons que le systeme èst convergent pour les configurations atteintes en k ă n etapes depuis b, et montrons qu’il l’est pour n etapes. Soit b 1 (resp. b2) la configuration precédent b 1 (resp. b2 ) dans la derivation de b a b 1 (resp. b2 ) : b ˚Ñ b 1 Ñ b 1 (resp. b ˚Ñ b 2 Ñ b 2 ). Alors par hypothese d’induction, il existe une configuration b 3 telle que b 1 ˚Ñ b 3ét b 2 ˚Ñ b 3. Pour chacune de ces deux configurations, nous effectuons une nouvelle induction sur la longueur de la derivation de b 1 (resp. b2) a b 3, et nous obtenons avec la proprieté du diamant une configuration b 1 (resp. b2) successeur de b 3 qui est atteignable depuis b 1 (resp. b2 ). Par exemple pour la premiere ètape du c otˆ é b 2ét b 2 , soit b 21 la premiere configuration obtenue dans la derivation de b 2à b 3 : b 2 Ñ b 21 ˚Ñ – 48 Chapitre 2. Introduction aux piles de sable Kadanoff b 3, alors nous avons b 2 Ñ b 21 et b 2 Ñ b 2 donc d’apres la pro- prieté du diamant il existe une configuration b 21 telle que b 21 Ñ b 21 et b 2 Ñ b 21 . En appliquant une derniere fois la propri èté du diamant, il existe une configuration b 3 telle que b 1 Ñ b 3 (resp. b2 Ñ b 3). b 3 est ainsi atteignable depuis b 1 et b 2 , donc le systeme est convergent pour n. Pour toute configuration b P Cb , nous denoterons l’unique point fixe àtteint πpbq, qui est donc tel que b ˚Ñ πpbq. Remarquons de plus que pour toutes configurations b et b 1 telles que b ˚Ñ b 1 , ces deux configurations atteignent le meme point fixe, ˆ πpb 1 q “ πpbq. La Proposition suivante est corollaire. Proposition 2.4. Pour tout parametre p et toute configuration b P Cb , πpbq est unique. Les travaux present és dans les chapitres suivants vont s’int éresser én particulier au point fixe obtenu a partir de la configuration initiale composee d’un nombre fini N de grains empiles en colonne 0. Nous utiliserons la notation 0ω pour la suite infinie de zeros, de telle sorte que la configuration initiale s’ecrive pN, 0ωq, que nous abregerons par N. Ainsi, nous nous interesserons à πpNq, que nous prendrons comme la representation sous forme de diff érence de hauteur du point fixe atteint à partir de la configuration initiale pN, 0ωq. Pour alleger la notation, la dependance au param étre p de la configuration πpNq n’est pas indiquee. Nous utiliserons cette notation dans des contextes ou le param ètre p sera fixe, ou mentionné. L’ensemble des configurations accessibles depuis la configuration initiale pN, 0ωq pour un parametre p sera noté KSPMpp, Nq. La figure 2.3 montre un exemple de KSPMp2, 24q. action Une troisieme reprèsentation jouera un role important dans la   suite de notre expose, il s’agit de la suite d’actions (le terme anglais est shot vector) d’une configuration, definie à partir de l’action de chaque co- lonne. Cette representation est liée a la configuration initiale pN, 0ωq du modele. Pour une configuration atteignable depuis pN, 0ωq, c’est-a-dire un elément de KSPMpp, Nq, l’action d’une colonne i, denot éeài , est le nombre de fois que la regle a èté appliqu éeà l’indice i depuis la configuration pN, 0ωq. La suite d’actions d’une configuration, denot éeà “ paiqiPN, est ainsi definie comme la suite des actions de chaque indice. C’est une suite infinie et ultimement nulle d’entiers, c’est-a-dire un èlément de Ca “ Cb . Comme nous l’avons dej à remarqu è pour la propriete du diamant, l’ordre dans lequel la regle est appliquèe n’a pas d’importance, donc  pour un parametre p et un nombre de grains N, une suite d’actions .