Hostname: page-component-848d4c4894-8kt4b Total loading time: 0 Render date: 2024-06-25T06:56:16.876Z Has data issue: false hasContentIssue false
  • English
  • Français

Indistinguishable asymptotic pairs and multidimensional Sturmian configurations

Part of: Discrete mathematics in relation to computer science Smooth dynamical systems: general theory Topological dynamics Discrete geometry

Published online by Cambridge University Press:  31 May 2024

SEBASTIÁN BARBIERI Open the ORCID record for SEBASTIÁN BARBIERI [Opens in a new window]  and
SÉBASTIEN LABBÉ
SEBASTIÁN BARBIERI*
Affiliation:
Departamento de Matemática y Ciencia de la Computación, Universidad de Santiago de Chile, Las Sophoras 173, Estación Central, Santiago, Chile
SÉBASTIEN LABBÉ
Affiliation:
Université de Bordeaux, CNRS, Bordeaux INP, LaBRI, UMR 5800, F-33400 Talence, France (e-mail: [email protected])
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Two asymptotic configurations on a full $\mathbb {Z}^d$-shift are indistinguishable if, for every finite pattern, the associated sets of occurrences in each configuration coincide up to a finitely supported permutation of $\mathbb {Z}^d$. We prove that indistinguishable asymptotic pairs satisfying a ‘flip condition’ are characterized by their pattern complexity on finite connected supports. Furthermore, we prove that uniformly recurrent indistinguishable asymptotic pairs satisfying the flip condition are described by codimension-one (dimension of the internal space) cut and project schemes, which symbolically correspond to multidimensional Sturmian configurations. Together, the two results provide a generalization to $\mathbb {Z}^d$ of the characterization of Sturmian sequences by their factor complexity $n+1$. Many open questions are raised by the current work and are listed in the introduction.

Keywords

asymptotic pairsSturmian sequencescomplexitybispecial patternsymbolic dynamicscut and project scheme

MSC classification

Primary: 37B10: Symbolic dynamics
Secondary: 37C29: Homoclinic and heteroclinic orbits 52C23: Quasicrystals, aperiodic tilings 68R15: Combinatorics on words
Type
Original Article
Information
Ergodic Theory and Dynamical Systems , First View , pp. 1 - 59
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allouche, J.-P. and Shallit, J.. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.CrossRefGoogle Scholar
Andersson, K. G.. Poincaré’s discovery of homoclinic points. Arch. Hist. Exact Sci. 48(2) (1994), 133–147.CrossRefGoogle Scholar
Arnoux, P.. Sturmian sequences. Substitutions in Dynamics, Arithmetics and Combinatorics (Lecture Notes in Mathematics, 1794). Ed. Berthé, V., Ferenczi, S., Mauduit, C. and Siegel, A.. Springer, Berlin, 2002, pp. 143–198.Google Scholar
Arnoux, P., Berthé, V. and Ito, S.. Discrete planes, ${\mathbb{Z}}^2$ -actions, Jacobi–Perron algorithm and substitutions. Ann. Inst. Fourier (Grenoble) 52(2) (2002), 305–349.CrossRefGoogle Scholar
Arnoux, P., Berthé, V. and Siegel, A.. Two-dimensional iterated morphisms and discrete planes. Theoret. Comput. Sci. 319(1–3) (2004), 145–176.CrossRefGoogle Scholar
Baake, M. and Grimm, U.. Aperiodic Order. Volume 1. A Mathematical Invitation (Encyclopedia of Mathematics and its Applications, 149). Cambridge University Press, Cambridge, 2013.Google Scholar
Barbieri, S., Gómez, R., Marcus, B., Meyerovitch, T. and Taati, S.. Gibbsian representations of continuous specifications: the theorems of Kozlov and Sullivan revisited. Comm. Math. Phys. 382(2) (2021), 1111–1164.CrossRefGoogle Scholar
Barbieri, S., Gómez, R., Marcus, B. and Taati, S.. Equivalence of relative Gibbs and relative equilibrium measures for actions of countable amenable groups. Nonlinearity 33(5) (2020), 2409–2454.CrossRefGoogle Scholar
Barbieri, S., Labbé, S. and Starosta, Š.. A characterization of Sturmian sequences by indistinguishable asymptotic pairs. European J. Combin. 95 (2021), 103318, 22pp.CrossRefGoogle Scholar
Berthé, V.. Discrete geometry and symbolic dynamics. Complex Analysis and Digital Geometry (Acta Univ. Upsaliensis Skr. Uppsala Univ. C Organ. Hist., 86). Ed. Passare, M.. Uppsala Universitet, Uppsala, 2009, pp. 81–110.Google Scholar
Berthé, V., Dolce, F., Durand, F., Leroy, J. and Perrin, D.. Rigidity and substitutive dendric words. Internat. J. Found. Comput. Sci. 29(5) (2018), 705–720.CrossRefGoogle Scholar
Berthé, V. and Vuillon, L.. Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences. Discrete Math. 223(1–3) (2000), 27–53.CrossRefGoogle Scholar
Cassaigne, J.. Double sequences with complexity $mn+1$ . J. Autom. Lang. Comb. 4(3) (1999), 153–170. Journées Montoises d’Informatique Théorique (Mons, 1998).Google Scholar
Cassaigne, J. and Nicolas, F.. Factor complexity. Combinatorics, Automata and Number Theory (Encyclopedia of Mathematics and its Applications, 135). Ed. Berthe, V. and Rigo, M.. Cambridge University Press, Cambridge, 2010, pp. 163–247.CrossRefGoogle Scholar
Chandgotia, N. and Meyerovitch, T.. Markov random fields, Markov cocycles and the 3-colored chessboard. Israel J. Math. 215(2) (2016), 909–964.CrossRefGoogle Scholar
Coven, E. M. and Hedlund, G. A.. Sequences with minimal block growth. Math. Syst. Theory 7 (1973), 138–153.CrossRefGoogle Scholar
Cyr, V. and Kra, B.. Nonexpansive ${\mathbb{Z}}^2$ -subdynamics and Nivat’s conjecture. Trans. Amer. Math. Soc. 367(9) (2015), 6487–6537.CrossRefGoogle Scholar
de Luca, A.. Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci. 183(1) (1997), 45–82.CrossRefGoogle Scholar
Georgii, H.-O.. Gibbs Measures and Phase Transitions. Walter de Gruyter, Berlin, 1988.CrossRefGoogle Scholar
Haynes, A.. Equivalence classes of codimension-one cut-and-project nets. Ergod. Th. & Dynam. Sys. 36(3) (2016), 816–831.CrossRefGoogle Scholar
Hochman, M.. Multidimensional shifts of finite type and sofic shifts. Combinatorics, Words and Symbolic Dynamics (Encyclopedia of Mathematics and its Applications, 159). Ed. Berthe, E. V. and Rigo, M.. Cambridge University Press, Cambridge, 2016, pp. 296–358.Google Scholar
Jamet, D.. Coding stepped planes and surfaces by two-dimensional sequences over a three-letter alphabet. Technical Report 05047, LIRMM - Université Montpellier II - UMR 5506, July 2005.Google Scholar
Jolivet, T.. Combinatorics of Pisot Substitutions. PhD Thesis, University of Turku & Université Paris Diderot, 2013.Google Scholar
Kari, J. and Szabados, M.. An algebraic geometric approach to Nivat’s conjecture. Inform. and Comput. 271 (2020), 104481, 25pp.CrossRefGoogle Scholar
Labbé, S.. Markov partitions for toral ${\mathbb{Z}}^2$ -rotations featuring Jeandel–Rao Wang shift and model sets. Ann. H. Lebesgue 4 (2021), 283–324.CrossRefGoogle Scholar
Labbé, S. and Reutenauer, C.. A $d$ -dimensional extension of Christoffel words. Discrete Comput. Geom. 54(1) (2015), 152–181.Google Scholar
Lanford, O. E. III and Ruelle, D.. Observables at infinity and states with short range correlations in statistical mechanics. Comm. Math. Phys. 13(3) (1969), 194–215.Google Scholar
Lind, D. and Marcus, B.. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995.CrossRefGoogle Scholar
Lothaire, M.. Algebraic Combinatorics on Words (Encyclopedia of Mathematics and its Applications, 90). Cambridge University Press, Cambridge, 2002.CrossRefGoogle Scholar
Morse, M. and Hedlund, G. A.. Symbolic dynamics. Amer. J. Math. 60(4) (1938), 815–866.Google Scholar
Morse, M. and Hedlund, G. A.. Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940), 1–42.CrossRefGoogle Scholar
Nivat, M.. Invited talk at ICALP, Bologna, 1997.Google Scholar
Putnam, I. F.. Cantor Minimal Systems (University Lecture Series, 70). American Mathematical Society, Providence, RI, 2018.CrossRefGoogle Scholar
Ruelle, D.. Thermodynamic Formalism, 2nd edn. Cambridge University Press, Cambridge, 2004.CrossRefGoogle Scholar
Schmidt, W. M.. Diophantine Approximation (Lecture Notes in Mathematics, 785). Springer, Berlin, 1980.Google Scholar
Szabados, M.. Nivat’s conjecture holds for sums of two periodic configurations. SOFSEM 2018: Theory and Practice of Computer Science (Lecture Notes in Computer Science, 10706). Ed. Tjoa, A. M., Bellatreche, L., Biffl, S., van Leeuwen, J. and Wiedermann, J.. Springer, Cham, 2018, pp. 539–551.Google Scholar