Metallic mean Wang tiles II: the dynamics of an aperiodic computer chip

Labbé, Sébastien 

Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e155

Résumé

We consider a new family $(\mathcal {T}_n)_{n\geq 1}$ of aperiodic sets of Wang tiles and we describe the dynamical properties of the set $\Omega _n$ of valid configurations $\mathbb {Z}^2\to \mathcal {T}_n$. The tiles can be defined as the different instances of a square-shaped computer chip whose inputs and outputs are 3-dimensional integer vectors. The family include the Ammann aperiodic set of 16 Wang tiles and gathers the hallmarks of other small aperiodic sets of Wang tiles. Notably, the tiles satisfy additive versions of equations verified by the Kari–Culik aperiodic sets of 14 and 13 Wang tiles. Also configurations in $\Omega _n$ are the codings of a $\mathbb {Z}^2$-action on a 2-dimensional torus like the Jeandel–Rao aperiodic set of 11 Wang tiles. The family broadens the relation between quadratic integers and aperiodic tilings beyond the omnipresent golden ratio as the dynamics of $\Omega _n$ involves the positive root $\beta $ of the polynomial $x^2-nx-1$, also known as the n-th metallic mean. We show the existence of an almost one-to-one factor map $\Omega _n\to \mathbb {T}^2$ which commutes the shift action on $\Omega _n$ with horizontal and vertical translations by $\beta $ on $\mathbb {T}^2$. The factor map can be explicitly defined by the average of the top labels from the same row of tiles as in Kari and Culik examples. The proofs are based on the minimality of $\Omega _n$ (proved in a previous article) and a polygonal partition of $\mathbb {T}^2$ which we show is a Markov partition for the toral $\mathbb {Z}^2$-action. The partition and the sets of Wang tiles are symmetric which makes them, like Penrose tilings, worthy of investigation.

Détail

DOI : 10.1017/fms.2025.10098

Bibliographie

[1] Aaronson, S., ‘The busy beaver frontier’, SIGACT News 51 (2020), 32–54. http://doi.org/10.1145/3427361.3427369. Google Scholar | DOI

[2] Akiyama, S. and Arnoux, P. (eds), Substitution and Tiling Dynamics: Introduction to Self-inducing Structures, CIRM Jean-Morlet Chair, Marseille, France, Fall 2017, Vol. 2273 (Cham: Springer, 2020), xix+453 pp. Google Scholar

[3] Ammann, R., Grünbaum, B. and Shephard, G. C., ‘Aperiodic tiles’, Discrete Comput. Geom. 8 (1992), 1–25.10.1007/BF02293033 Google Scholar | DOI

[4] Aujogue, J.-B., Barge, M., Kellendonk, J. and Lenz, D., ‘Equicontinuous factors, proximality and Ellis semigroup for Delone sets’, in Mathematics of Aperiodic Order, Vol. 309 of Progr. Math., Birkhäuser/Springer, Basel (2015), 137–194. http://doi.org/10.1007/978-3-0348-0903-0_5. Google Scholar | DOI

[5] Baake, M. and Grimm, U., Aperiodic Order. Vol. 1, Vol. 149 of Encycl. Math. Appl. (Cambridge University Press, Cambridge, 2013), xvi+531 pp. http://doi.org/10.1017/CBO9781139025256. Google Scholar | DOI

[6] Baake, M. and Grimm, U. (eds), Aperiodic Order. Vol. 2: Crystallography and almost periodicity, Vol. 166 of Encycl. Math. Appl. (Cambridge University Press, Cambridge, 2017). http://doi.org/10.1017/9781139033862. Google Scholar | DOI

[7] Berger, R., ‘The undecidability of the domino problem’, Mem. Amer. Math. Soc. No. 66 (1966), 72. Google Scholar

[8] Bowen, R., ‘Markov partitions are not smooth’, Proc. Amer. Math. Soc. 71 (1978), 130–132. http://doi.org/10.2307/2042234. Google Scholar

[9] Brady, A. H., ‘The busy beaver game and the meaning of life’, in The Universal Turing Machine, a Half-Century Survey, (1988), 259–277.10.1093/oso/9780198537748.003.0009 Google Scholar | DOI

[10] Cawley, E., ‘Smooth Markov partitions and toral automorphisms’, Ergodic Theory Dynam. Systems 11 (1991), 633–651. http://doi.org/10.1017/S0143385700006404. Google Scholar | DOI

[11] Culik, K. Ii ‘An aperiodic set of 13 Wang tiles’, Discrete Math. 160 (1996), 245–251. http://doi.org/10.1016/S0012-365X(96)00118-5. Google Scholar

[12] De Bruijn, N. G., ‘Algebraic theory of Penrose’s nonperiodic tilings of the plane. I, II’, Indag. Math. 43 (1981), 39–52, 53–66. Google Scholar

[13] De Spinadel, V. W., ‘The family of metallic means’, Vis. Math. 1 (1999), 1 HTML document; approx. 16. Google Scholar

[14] Durand, B., Gamard, G. and Grandjean, A., ‘Aperiodic tilings and entropy’, Theoret. Comput. Sci. 666 (2017), 36–47. http://doi.org/10.1016/j.tcs.2016.12.013. Google Scholar

[15] Eigen, S., Navarro, J. and Prasad, V. S., ‘An aperiodic tiling using a dynamical system and Beatty sequences’, in Dynamics, Ergodic Theory, and Geometry, Vol. 54 of Math. Sci. Res. Inst. (Cambridge University Press, Cambridge, 2007), 223–241. http://doi.org/10.1017/CBO9780511755187.009. Google Scholar | DOI

[16] Einsiedler, M. and Schmidt, K., ‘Markov partitions and homoclinic points of algebraic -actions’, Tr. Mat. Inst. Steklova 216 (1997), 265–284. Google Scholar

[17] Fiebig, D., ‘Factor maps, entropy and fiber cardinality for Markov shifts’, Rocky Mountain J. Math. 31 (2001), 955–986. http://doi.org/10.1216/rmjm/1020171674. Google Scholar | DOI

[18] Fuhrmann, G., Gröger, M. and Lenz, D., ‘The structure of mean equicontinuous group actions’, Israel J. Math. 247 (2022), 75–123. http://doi.org/10.1007/s11856-022-2292-8. Google Scholar | DOI

[19] Grünbaum, B. and Shephard, G. C., Tilings and Patterns (W. H. Freeman and Company, New York, 1987), xii+700 pp. Google Scholar

[20] Hochman, M., ‘Multidimensional shifts of finite type and sofic shifts’, in Combinatorics, Words and Symbolic Dynamics, Vol. 159 of Encycl. Math. Appl., Cambridge Univ. Press, Cambridge (2016), 296–358. http://doi.org/10.1017/CBO9781139924733.010. Google Scholar

[21] Jeandel, E. and Rao, M., ‘An aperiodic set of 11 Wang tiles’, Adv. Comb. 2021 (2021), 37. http://doi.org/10.19086/aic.18614. Google Scholar

[22] Jeandel, E. and Vanier, P., ‘The undecidability of the Domino Problem’, in Substitution and tiling dynamics: introduction to self-inducing structures, Vol. of Lecture Notes in Math., Springer, Cham (2020), 293–357. http://doi.org/10.1007/978-3-030-57666-0_6. Google Scholar

[23] Jolivet, T., ‘Toral automorphisms, Markov partitions and fractals’ (2012). https://jolivet.org/timo/docs/slides_guangzhou_toral.pdf. Google Scholar

[24] Kari, J., ‘A small aperiodic set of Wang tiles’, Discrete Math. 160 (1996), 259–264. http://doi.org/10.1016/0012-365X(95)00120-L. Google Scholar | DOI

[25] Kari, J., ‘The tiling problem revisited (extended abstract)’, in Machines, Computations, and Universality. 5th International Conference, MCU 2007, Orléans, France, September 10–13, 2007. Proceedings, Springer, Berlin (2007), 72–79. http://doi.org/10.1007/978-3-540-74593-8_6. Google Scholar | DOI

[26] Kari, J., ‘On the undecidability of the tiling problem’, in Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P. and Bieliková, M. (eds), SOFSEM 2008: Theory and Practice of Computer Science (Springer, Berlin, 2008), 74–82. Google Scholar | DOI

[27] Kari, J., ‘Piecewise affine functions, Sturmian sequences and Wang tiles’, Fundam. Inform. 145 (2016), 257–277. http://doi.org/10.3233/FI-2016-1360. Google Scholar

[28] Kari, J. and Papasoglu, P., ‘Deterministic aperiodic tile sets’, Geom. Funct. Anal. 9 (1999), 353–369. http://doi.org/10.1007/s000390050090. Google Scholar | DOI

[29] Knuth, D. E., The Art of Computer Programming. Vol. 1: Fundamental Algorithms, 2nd printing (Addison-Wesley, Reading, London, Don Mills, 1969), xxi+634 pp. Google Scholar

[30] Kuipers, L. and Niederreiter, H., Uniform Distribution of Sequences, Pure and Applied Mathematics (Wiley, New York, 1974), xiv+390 pp. Google Scholar

[31] Kurka, P., Topological and Symbolic Dynamics, Vol. 11 of Cours Spécialisés, Société Mathématique de France, Paris (2003), xii+315 pp. Google Scholar

[32] Labbé, S., ‘A self-similar aperiodic set of 19 Wang tiles’, Geom. Dedicata 201 (2019), 81–109. http://doi.org/10.1007/s10711-018-0384-8. Google Scholar

[33] Labbé, S., ‘Markov partitions for toral -rotations featuring Jeandel–Rao Wang shift and model sets’, Ann. H. Lebesgue 4 (2021), 283–324. http://doi.org/10.5802/ahl.73. Google Scholar

[34] Labbé, S., ‘Rauzy induction of polygon partitions and toral -rotations’, J. Mod. Dyn. 17 (2021), 481–528. http://doi.org/10.3934/jmd.2021017. Google Scholar

[35] Labbé, S., ‘Substitutive structure of Jeandel–Rao aperiodic tilings’, Discrete Comput. Geom. 65 (2021), 800–855. http://doi.org/10.1007/s00454-019-00153-3. Google Scholar | DOI

[36] Labbé, S., ‘Three characterizations of a self-similar aperiodic 2-dimensional subshift’, Preprint (2020), , 46 pp., book chapter in preparation. Google Scholar | arXiv

[37] Labbé, S., ‘Metallic mean Wang tiles I: self-similarity, aperiodicity and minimality’, Forum Math. Sigma 13 (2025), e133. http://doi.org/10.1017/fms.2025.10069. Google Scholar | DOI

[38] Labbé, S., ‘Optional SageMath Package slabbe (Version 0.8.0)’, https://pypi.python.org/pypi/slabbe/ (2025). Google Scholar

[39] Lind, D., ‘Multi-dimensional symbolic dynamics’, in Symbolic Dynamics and its Applications, Vol. 60 of Proc. Sympos. Appl. Math., Amer. Math. Soc., Providence, RI (2004), 61–79. http://doi.org/10.1090/psapm/060/2078846. Google Scholar

[40] Lind, D. and Marcus, B., An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, Cambridge, 1995), xvi+495 pp. http://doi.org/10.1017/CBO9780511626302. Google Scholar

[41] Mozes, S., ‘Tilings, substitution systems and dynamical systems generated by them’, J. Analyse Math. 53 (1989), 139–186. http://doi.org/10.1007/BF02793412. Google Scholar | DOI

[42] OEIS Foundation Inc., ‘Entry A060843 in the On-Line Encyclopedia of Integer Sequences: Busy Beaver problem: maximal number of steps that an -state Turing machine can make on an initially blank tape before eventually halting’, (2023). https://oeis.org/A060843. Google Scholar

[43] Ollinger, N., ‘Two-by-two substitution systems and the undecidability of the domino problem’, in Logic and Theory of Algorithms, Vol. 5028 of Lecture Notes in Comput. Sci., Springer, Berlin (2008), 476–485. http://doi.org/10.1007/978-3-540-69407-6_51. Google Scholar | DOI

[44] Penrose, R., ‘Pentaplexity. A class of non-periodic tilings of the plane’, Math. Intell. 2 (1979), 32–37. http://doi.org/10.1007/BF03024384. Google Scholar | DOI

[45] Praggastis, B., ‘Numeration systems and Markov partitions from self-similar tilings’, Trans. Amer. Math. Soc. 351 (1999), 3315–3349. http://doi.org/10.1090/S0002-9947-99-02360-0. Google Scholar

[46] Priebe, N. and Solomyak, B., ‘Characterization of planar pseudo-self-similar tilings’, Discrete Comput. Geom. 26 (2001), 289–306. Google Scholar | DOI

[47] Rauzy, G., ‘Nombres algébriques et substitutions’, Bull. Soc. Math. France 110 (1982), 147–178. http://doi.org/10.24033/bsmf.1957. Google Scholar

[48] Robinson, E. A. Jr. ‘The dynamical properties of Penrose tilings’, Trans. Amer. Math. Soc. 348 (1996), 4447–4464. http://doi.org/10.1090/S0002-9947-96-01640-6. Google Scholar | DOI

[49] Robinson, R. M., ‘Undecidability and nonperiodicity for tilings of the plane’, Invent. Math. 12 (1971), 177–209. http://doi.org/10.1007/BF01418780. Google Scholar | DOI

[50] Sage Developers, SageMath, the Sage Mathematics Software System (Version 10.6) (2025). http://www.sagemath.org. Google Scholar

[51] Schmidt, K., ‘Multi-dimensional symbolic dynamical systems’, in Codes, Systems, and Graphical Models (Minneapolis, MN, 1999), Vol. of IMA Vol. Math. Appl. (Springer, New York, 2001), 67–82. http://doi.org/10.1007/978-1-4613-0165-3_3. Google Scholar

[52] Schroeder, M., Fractals, Chaos, Power Laws. Minutes from an Infinite Paradise (W.H. Freeman and Company, New York, 1991). Google Scholar | DOI

[53] Senechal, M., Quasicrystals and Geometry (Cambridge University Press, Cambridge, 1995). Google Scholar

[54] Siefken, J., ‘A minimal subsystem of the Kari–Culik tilings’, Ergodic Theory Dynam. Systems 37 (2017), 1607–1634. http://doi.org/10.1017/etds.2015.118. Google Scholar | DOI

[55] Smith, D., Myers, J. S., Kaplan, C. S. and Goodman-Strauss, C., ‘An aperiodic monotile’, Comb. Theory 4 (2024), Paper No. 6, 91. http://doi.org/10.5070/C64163843. Google Scholar

[56] Smith, D., Myers, J. S., Kaplan, C. S. and Goodman-Strauss, C., ‘A chiral aperiodic monotile’, Comb. Theory 4 (2024), Paper No. 13, 25. http://doi.org/10.5070/C64264241. Google Scholar

[57] Socolar, J. E. S. and Taylor, J. M., ‘An aperiodic hexagonal tile’, J. Combin. Theory Ser. A 118 (2011), 2207–2231. http://doi.org/10.1016/j.jcta.2011.05.001. Google Scholar | DOI

[58] Solomyak, B., ‘Dynamics of self-similar tilings’, Ergodic Theory Dynam. Systems 17 (1997), 695–738. http://doi.org/10.1017/S0143385797084988. Google Scholar | DOI

[59] Solomyak, B., ‘Nonperiodicity implies unique composition for self-similar translationally finite tilings’, Discrete Comput. Geom. 20 (1998), 265–279. http://doi.org/10.1007/PL00009386. Google Scholar | DOI

[60] Turing, A. M., ‘On computable numbers, with an application to the Entscheidungsproblem’, Proc. London Math. Soc. 42(2) (1936), 230–265. http://doi.org/10.1112/plms/s2-42.1.230. Google Scholar

[61] Walters, P., An Introduction to Ergodic Theory, Vol. of GTM (Springer-Verlag, New York, Berlin, 1982), ix+250 pp.10.1007/978-1-4612-5775-2 Google Scholar | DOI

[62] Wang, H., ‘Proving theorems by pattern recognition – II’, Bell Syst. Tech. J. 40 (1961), 1–41. http://doi.org/10.1002/j.1538-7305.1961.tb03975.x. Google Scholar | DOI