Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Sandpile Toppling on Penrose Tilings: Identity and Isotropic Dynamics

  • Chapter
  • First Online:
Automata and Complexity

Part of the book series: Emergence, Complexity and Computation ((ECC,volume 42))

  • 495 Accesses

Abstract

We present experiments of sandpiles on grids (square, triangular, hexagonal) and Penrose tilings. The challenging part is to program such simulator; and our javacript code is available online, ready to play! We first present some identity elements of the sandpile group on these aperiodic structures, and then study the stabilization of the maximum stable configuration plus the identity, which lets a surprising circular shape appear. Roundness measurements reveal that the shapes are not approaching perfect circles, though they are close to be. We compare numerically this almost isotropic dynamical phenomenon on various tilings.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 149.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 199.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 199.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The identity element of the sandpile group is unique.

  2. 2.

    Note that in order to enforce aperiodicity in P2 and P3, matching constraints should be added on tile edges, for example via notches, but the finite tiling generation methods we employ do not require such considerations.

  3. 3.

    Well, this is a bit disappointing, but we think that it is worth showing that it does not appear to be a fruitful research direction, or maybe a more insightful reader would encounter something out there....

  4. 4.

    This also takes place on other tilings, outside the scope of the present work.

  5. 5.

    They all remain stable with \(deg({v})-1\) grains until reaching m. Observe that any outer tile receiving some grain would topple, and that toppling any outer tile would result in toppling the whole maximum stable component it belongs to.

  6. 6.

    The difficulty may be to find constructions from non Wang tiles, because Wang tiles would lead to square grids for the sandpile model to play on (as we remove tile decorations).

References

  1. Baake M, Scholottmann M, Jarvis PD (1991) Quasiperiodic tilings with tenfold symmetry and equivalence with respect to local derivability. J Phys A: Math Gen 24(19):4637–4654. https://doi.org/10.1088/0305-4470/24/19/025

    Article  MathSciNet  MATH  Google Scholar 

  2. Bak P, Tang C, Wiesenfeld K (1987) Self-organized criticality: an explanation of the 1/f noise. Phys Rev Lett 59:381–384. https://doi.org/10.1103/PhysRevLett.59.381

    Article  Google Scholar 

  3. Bak P, Tang C, Wiesenfeld K (1988) Self-organized criticality. Phys Rev A 38(1):364–374. https://doi.org/10.1103/PhysRevA.38.364

    Article  MathSciNet  MATH  Google Scholar 

  4. Ballier A, Jeandel E (2010) Computing (or not) Quasi-periodicity functions of tilings. In: Journées automates cellulaires, pp 54–64

    Google Scholar 

  5. Berger R (1966) The undecidability of the domino problem. Mem Am Math Soc 66. https://doi.org/10.1090/memo/0066

  6. de Bruijn NG (1981) Algebraic theory of penrose’s non-periodic tilings of the plane. ii. Indag Math 84(1):53–66. https://doi.org/10.1016/1385-7258(81)90017-2

  7. Cairns H (2018) Some halting problems for abelian sandpiles are undecidable in dimension three. SIAM J Discret Math 32(4):2636–2666. https://doi.org/10.1137/16M1091964

    Article  MathSciNet  MATH  Google Scholar 

  8. Cervelle J, Durand B (2004) Tilings: recursivity and regularity. Theor Comput Sci 310(1):469–477. https://doi.org/10.1016/S0304-3975(03)00242-1

    Article  MathSciNet  MATH  Google Scholar 

  9. Delorme M, Mazoyer J, Tougne L (1999) Discrete parabolas and circles on 2D cellular automata. Theor Comput Sci 218(2):347–417. https://doi.org/10.1016/S0304-3975(98)00330-2

    Article  MATH  Google Scholar 

  10. Dhar D (1990) Self-organized critical state of sandpile automaton models. Phys Rev Lett 64:1613–1616. https://doi.org/10.1103/PhysRevLett.64.1613

    Article  MathSciNet  MATH  Google Scholar 

  11. Dhar D, Ruelle P, Sen S, Verma DN (1995) Algebraic aspects of abelian sandpile models. J Phys A 28(4):805–831. https://doi.org/10.1088/0305-4470/28/4/009

    Article  MathSciNet  MATH  Google Scholar 

  12. Durand B (1999) Tilings and quasiperiodicity. Theor Comput Sci 221(1):61–75. https://doi.org/10.1016/S0304-3975(99)00027-4

    Article  MathSciNet  MATH  Google Scholar 

  13. Durand-Lose JO (1998) Parallel transient time of one-dimensional sand pile. Theor Comput Sci 205(1–2):183–193. https://doi.org/10.1016/S0304-3975(97)00073-X

    Article  MathSciNet  MATH  Google Scholar 

  14. Fast VG, Efimov IR (1991) Stability of vortex rotation in an excitable cellular medium. Phys D: Nonlinear Phenom 49(1):75–81. https://doi.org/10.1016/0167-2789(91)90196-G

    Article  Google Scholar 

  15. Fernique T (2007) Pavages, fractions continues et géométrie discrète. PhD thesis, Université Montpellier II

    Google Scholar 

  16. Formenti E, Goles E, Martin B (2012) Computational complexity of avalanches in the Kadanoff sandpile model. Fundam Inform 115(1):107–124. https://doi.org/10.3233/FI-2012-643

    Article  MathSciNet  MATH  Google Scholar 

  17. Formenti E, Masson B, Pisokas T (2007) Advances in symmetric sandpiles. Fundam Inform 76(1–2):91–112. https://doi.org/10.5555/2366416.2366423

    Article  MathSciNet  MATH  Google Scholar 

  18. Formenti E, Perrot K (2019) How hard is it to predict sandpiles on lattices? a survey. Fundam Inform 171:189–219. https://doi.org/10.3233/FI-2020-1879

    Article  MathSciNet  MATH  Google Scholar 

  19. Formenti E, Perrot K, Rémila E (2014) Computational complexity of the avalanche problem on one dimensional Kadanoff sandpiles. In: Proceedings of AUTOMATA’2014, LNCS, vol 8996, pp 21–30. https://doi.org/10.1007/978-3-319-18812-6_2

  20. Formenti E, Perrot K, Rémila E (2018) Computational complexity of the avalanche problem for one dimensional decreasing sandpiles. J Cell Autom 13:215–228

    MathSciNet  MATH  Google Scholar 

  21. Formenti E, Pham VT, Phan HD, Tran TH (2014) Fixed-point forms of the parallel symmetric sandpile model. Theor Comput Sci 533:1–14. https://doi.org/10.1016/j.tcs.2014.02.051

    Article  MathSciNet  MATH  Google Scholar 

  22. Gajardo A, Goles E (2006) Crossing information in two-dimensional sandpiles. Theor Comput Sci 369(1–3):463–469. https://doi.org/10.1016/j.tcs.2006.09.022

    Article  MathSciNet  MATH  Google Scholar 

  23. Goles E (1992) Sand pile automata. Ann de l’institut Henri Poincaré (A) Physique théorique 56(1):75–90

    Google Scholar 

  24. Goles E, Kiwi M (1993) Games on line graphs and sand piles. Theor Comput Sci 115(2):321–349. https://doi.org/10.1016/0304-3975(93)90122-A

    Article  MathSciNet  MATH  Google Scholar 

  25. Goles E, Latapy M, Magnien C, Morvan M, Phan HD (2004) Sandpile models and lattices: a comprehensive survey. Theor Comput Sci 322(2):383–407. https://doi.org/10.1016/j.tcs.2004.03.019

    Article  MathSciNet  MATH  Google Scholar 

  26. Goles E, Maldonado D, Montealegre P, Ollinger N (2017) On the computational complexity of the freezing non-strict majority automata. In: Proceedings of AUTOMATA’2017, pp 109–119. https://doi.org/10.1007/978-3-319-58631-1_9

  27. Goles E, Margenstern M (1997) Universality of the chip-firing game. Theor Comput Sci 172(1–2):121–134. https://doi.org/10.1016/S0304-3975(95)00242-1

    Article  MathSciNet  MATH  Google Scholar 

  28. Goles E, Montealegre P (2014) Computational complexity of threshold automata networks under different updating schemes. Theor Comput Sci 559:3–19. https://doi.org/10.1016/j.tcs.2014.09.010

    Article  MathSciNet  MATH  Google Scholar 

  29. Goles E, Montealegre P (2016) A fast parallel algorithm for the robust prediction of the two-dimensional strict majority automaton. In: Proceedings of ACRI’2016, pp 166–175. https://doi.org/10.1007/978-3-319-44365-2_16

  30. Goles E, Montealegre P, Perrot K, Theyssier G (2017) On the complexity of two-dimensional signed majority cellular automata. J Comput Syst Sci 91:1–32. https://doi.org/10.1016/j.jcss.2017.07.010

    Article  MathSciNet  MATH  Google Scholar 

  31. Goles E, Montealegre-Barba P, Todinca I (2013) The complexity of the bootstraping percolation and other problems. Theor Comput Sci 504:73–82. https://doi.org/10.1016/j.tcs.2012.08.001

    Article  MathSciNet  MATH  Google Scholar 

  32. Goles E, Morvan M, Phan HD (2002) Sandpiles and order structure of integer partitions. Discret Appl Math 117(1–3):51–64. https://doi.org/10.1016/S0166-218X(01)00178-0

  33. Grünbaum B, Shephard GC (1986) Tilings and patterns. WH Freeman & Co

    Google Scholar 

  34. Kadanoff LP, Nagel SR, Wu L, Zhou S (1989) Scaling and universality in avalanches. Phys Rev A 39(12):6524–6537. https://doi.org/10.1103/PhysRevA.39.6524

    Article  Google Scholar 

  35. Levine L, Pegden W, Smart CK (2016) Apollonian structure in the abelian sandpile. Geom Funct Anal 26:306–336. https://doi.org/10.1007/s00039-016-0358-7

    Article  MathSciNet  MATH  Google Scholar 

  36. Levine L, Pegden W, Smart CK (2017) The apollonian structure of integer superharmonic matrices. Ann Math 186(1):1–67. https://doi.org/10.4007/annals.2017.186.1.1

    Article  MathSciNet  MATH  Google Scholar 

  37. Levine L, Peres Y (2017) Laplacian growth, sandpiles, and scaling limits. Bull Am Math Soc 54(3):355–382. https://doi.org/10.1090/bull/1573

    Article  MathSciNet  MATH  Google Scholar 

  38. Marek M (2013) Grid anisotropy reduction for simulation of growth processes with cellular automaton. Phys D: Nonlinear Phenom 253:73–84. https://doi.org/10.1016/j.physd.2013.03.005

    Article  MathSciNet  MATH  Google Scholar 

  39. Markus M, Hess B (1990) Isotropic cellular automaton for modelling excitable media. Nature 347:56–58. https://doi.org/10.1038/347056a0

    Article  Google Scholar 

  40. Miltersen PB (2005) The computational complexity of one-dimensional sandpiles. In: Proceedings of CiE’2005, pp 342–348. https://doi.org/10.1007/11494645_42

  41. Moore C (1997) Majority-vote cellular automata, ising dynamics, and P-completeness. J Stat Phys 88(3):795–805. https://doi.org/10.1023/B:JOSS.0000015172.31951.7b

    Article  MathSciNet  MATH  Google Scholar 

  42. Moore C, Nilsson M (1999) The computational complexity of sandpiles. J Stat Phys 96:205–224. https://doi.org/10.1023/A:1004524500416

    Article  MathSciNet  MATH  Google Scholar 

  43. Nguyen VH, Perrot K (2018) Any shape can ultimately cross information on two-dimensional abelian sandpile models. In: Proceedings of AUTOMATA’2018, LNCS, vol 10875, pp 127–142. https://doi.org/10.1007/978-3-319-92675-9_10

  44. Pegden W, Smart CK (2013) Convergence of the abelian sandpile. Duke Math J 162(4):627–642. https://doi.org/10.1215/00127094-2079677

    Article  MathSciNet  MATH  Google Scholar 

  45. Pegden W, Smart CK (2020) Stability of patterns in the abelian sandpile. Ann Henri Poincaré 21:1383–1399. https://doi.org/10.1007/s00023-020-00898-1

    Article  MathSciNet  MATH  Google Scholar 

  46. Penrose R (1974) The role of aesthetics in pure and applied mathematical research. Bull Inst Math Its Appl 10(2):266–271

    Google Scholar 

  47. Penrose R (1979) Pentaplexity: a class of non-periodic tilings of the plane. Math Intell 2:32–37. https://doi.org/10.1007/BF03024384

  48. Perrot K (2013) Les piles de sable Kadanoff. PhD thesis, École normale supérieure de Lyon

    Google Scholar 

  49. Perrot K, Phan HD, Pham VT (2011) On the set of fixed points of the parallel symmetric sand pile model. In: Proceedings AUTOMATA’2011, DMTCS. Open Publishing Association, pp 17–28

    Google Scholar 

  50. Phan, H.D.: Structures ordonnées et dynamiques de piles de sable. Ph.D. thesis, Université Paris 7 (1999)

    Google Scholar 

  51. Phan HD (2008) Two sided sand piles model and unimodal sequences. ITA 42(3):631–646. https://doi.org/10.1051/ita:2008019

    Article  MathSciNet  MATH  Google Scholar 

  52. Robinson RM (1971) Undecidability and nonperiodicity for tilings of the plane. Inven Math 12:177–209. https://doi.org/10.1007/BF01418780

    Article  MathSciNet  MATH  Google Scholar 

  53. Roka Z (1994) Automates cellulaires sur graphes de cayley. PhD thesis, École Normale Supérieure de Lyon

    Google Scholar 

  54. Schepers HE, Markus M (1992) Two types of performance of an isotropic cellular automaton: stationary (Turing) patterns and spiral waves. Phys A: Stat Mech Its Appl 188(1):337–343. https://doi.org/10.1016/0378-4371(92)90277-W

    Article  Google Scholar 

  55. Schönfisch B (1997) Anisotropy in cellular automata. Biosystems 41(1):29–41. https://doi.org/10.1016/S0303-2647(96)01664-4

    Article  MATH  Google Scholar 

  56. Sirakoulis GC, Karafyllidis I, Thanailakis A (2005) A cellular automaton for the propagation of circular fronts and its applications. Eng Appl Artif Intell 18(6):731–744. https://doi.org/10.1016/j.engappai.2004.12.008

    Article  Google Scholar 

  57. Wang H (1961) Proving theorems by pattern recognition —II. Bell Syst Tech J 40:1–41. https://doi.org/10.1002/j.1538-7305.1961.tb03975.x

  58. Weimar JR (1997) Cellular automata for reaction-diffusion systems. Parallel Comput 23(11):1699–1715. https://doi.org/10.1016/S0167-8191(97)00081-1

    Article  MathSciNet  Google Scholar 

  59. Weimar JR, Tyson JJ, Watson LT (1992) Diffusion and wave propagation in cellular automaton models of excitable media. Phys D: Nonlinear Phenom 55(3):309–327. https://doi.org/10.1016/0167-2789(92)90062-R

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are thankful to Valentin Darrigo for his contributions to JS-Sandpile, to Victor Poupet for stressing that the apparent isotropy of the \({(m+e)}^{\circ }\) process is surprising at the occasion of a talk given by KP during AUTOMATA’2014 in Himeji, to Thomas Fernique for sharing his expertise (and code!) regarding the cut and project method, and to Christophe Papazian for useful comments on quasi-periodicity functions. The work of JF was conducted while a Master student at Aix-Marseille Université, doing an internship at the LIS laboratory (UMR 7020), both in Marseille, France. The work of KP was funded mainly by his salary as a French State agent and therefore by French taxpayers’ taxes, affiliated to Aix-Marseille University, University de Toulon, CNRS, LIS, UMR 7020, Marseille, France and University Côte d’Azur, CNRS, I3S, UMR 7271, Sophia Antipolis, France. Secondary financial support came from ANR-18-CE40-0002 FANs project, ECOS-Sud C16E01 project, and STIC AmSud CoDANet 19-STIC-03 (Campus France 43478PD) project.

Author information

Authors and Affiliations

  1. Université publique, Marseille, France

    Jérémy Fersula

  2. Cogitamus laboratory, Marseille, France

    Camille Noûs

  3. Université publique, Marseille, France

    Kévin Perrot

Authors
  1. Jérémy Fersula
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Camille Noûs
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kévin Perrot
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kévin Perrot .

Editor information

Editors and Affiliations

  1. Unconventional Computing Centre, University of the West of England, Bristol, UK

    Andrew Adamatzky

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Fersula, J., Noûs, C., Perrot, K. (2022). Sandpile Toppling on Penrose Tilings: Identity and Isotropic Dynamics. In: Adamatzky, A. (eds) Automata and Complexity. Emergence, Complexity and Computation, vol 42. Springer, Cham. https://doi.org/10.1007/978-3-030-92551-2_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92551-2_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92550-5

  • Online ISBN: 978-3-030-92551-2

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation