Nonexpansive $\mathbb {Z}^2$-subdynamics and Nivat’s Conjecture
HTML articles powered by AMS MathViewer
- by Van Cyr and Bryna Kra PDF
- Trans. Amer. Math. Soc. 367 (2015), 6487-6537 Request permission
Abstract:
For a finite alphabet $\mathcal {A}$ and $\eta \colon \mathbb {Z}\to \mathcal {A}$, the Morse-Hedlund Theorem states that $\eta$ is periodic if and only if there exists $n\in \mathbb {N}$ such that the block complexity function $P_\eta (n)$ satisfies $P_\eta (n)\leq n$, and this statement is naturally studied by analyzing the dynamics of a $\mathbb {Z}$-action associated with $\eta$. In dimension two, we analyze the subdynamics of a $\mathbb {Z}^2$-action associated with $\eta \colon \mathbb {Z}^2\to \mathcal {A}$ and show that if there exist $n,k\in \mathbb {N}$ such that the $n\times k$ rectangular complexity $P_{\eta }(n,k)$ satisfies $P_{\eta }(n,k)\leq nk$, then the periodicity of $\eta$ is equivalent to a statement about the expansive subspaces of this action. As a corollary, we show that if there exist $n,k\in \mathbb {N}$ such that $P_{\eta }(n,k)\leq \frac {nk}{2}$, then $\eta$ is periodic. This proves a weak form of a conjecture of Nivat in the combinatorics of words.References
- Valérie Berthé and Laurent Vuillon, Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences, Discrete Math. 223 (2000), no. 1-3, 27–53. MR 1782038, DOI 10.1016/S0012-365X(00)00039-X
- F. Blanchard and A. Maass, Dynamical properties of expansive one-sided cellular automata, Israel J. Math. 99 (1997), 149–174. MR 1469091, DOI 10.1007/BF02760680
- Mike Boyle and Alejandro Maass, Expansive invertible onesided cellular automata, J. Math. Soc. Japan 52 (2000), no. 4, 725–740. MR 1774627, DOI 10.2969/jmsj/05240725
- Mike Boyle and Douglas Lind, Expansive subdynamics, Trans. Amer. Math. Soc. 349 (1997), no. 1, 55–102. MR 1355295, DOI 10.1090/S0002-9947-97-01634-6
- Mike Boyle, Open problems in symbolic dynamics, Geometric and probabilistic structures in dynamics, Contemp. Math., vol. 469, Amer. Math. Soc., Providence, RI, 2008, pp. 69–118. MR 2478466, DOI 10.1090/conm/469/09161
- Valentin E. Brimkov and Reneta P. Barneva, Plane digitization and related combinatorial problems, Discrete Appl. Math. 147 (2005), no. 2-3, 169–186. MR 2127073, DOI 10.1016/j.dam.2004.09.010
- Julien Cassaigne, Double sequences with complexity $mn+1$, J. Autom. Lang. Comb. 4 (1999), no. 3, 153–170. Journées Montoises d’Informatique Théorique (Mons, 1998). MR 1719387
- Julien Cassaigne, Subword complexity and periodicity in two or more dimensions, Developments in language theory (Aachen, 1999) World Sci. Publ., River Edge, NJ, 2000, pp. 14–21. MR 1880477
- Fabien Durand and Michel Rigo, Multidimensional extension of the Morse-Hedlund theorem, European J. Combin. 34 (2013), no. 2, 391–409. MR 2994406, DOI 10.1016/j.ejc.2012.08.003
- Chiara Epifanio, Michel Koskas, and Filippo Mignosi, On a conjecture on bidimensional words, Theoret. Comput. Sci. 299 (2003), no. 1-3, 123–150. MR 1973149, DOI 10.1016/S0304-3975(01)00386-3
- N. J. Fine and H. S. Wilf, Uniqueness theorems for periodic functions, Proc. Amer. Math. Soc. 16 (1965), 109–114. MR 174934, DOI 10.1090/S0002-9939-1965-0174934-9
- N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, Lecture Notes in Mathematics, vol. 1794, Springer-Verlag, Berlin, 2002. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. MR 1970385, DOI 10.1007/b13861
- Michael Hochman, Non-expansive directions for $\Bbb Z^2$ actions, Ergodic Theory Dynam. Systems 31 (2011), no. 1, 91–112. MR 2755923, DOI 10.1017/S0143385709001084
- François Ledrappier, Un champ markovien peut être d’entropie nulle et mélangeant, C. R. Acad. Sci. Paris Sér. A-B 287 (1978), no. 7, A561–A563 (French, with English summary). MR 512106
- Marston Morse and Gustav A. Hedlund, Symbolic dynamics II. Sturmian trajectories, Amer. J. Math. 62 (1940), 1–42. MR 745, DOI 10.2307/2371431
- M. Nivat. Invited talk at ICALP, Bologna, 1997.
- Anthony Quas and Luca Zamboni, Periodicity and local complexity, Theoret. Comput. Sci. 319 (2004), no. 1-3, 229–240. MR 2074955, DOI 10.1016/j.tcs.2004.02.026
- J. W. Sander and R. Tijdeman, The complexity of functions on lattices, Theoret. Comput. Sci. 246 (2000), no. 1-2, 195–225. MR 1780238, DOI 10.1016/S0304-3975(99)00078-X
- J. W. Sander and R. Tijdeman, Low complexity functions and convex sets in $\mathbf Z^k$, Math. Z. 233 (2000), no. 2, 205–218. MR 1743434, DOI 10.1007/PL00004798
- J. W. Sander and R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices, Theoret. Comput. Sci. 270 (2002), no. 1-2, 857–863. MR 1871099, DOI 10.1016/S0304-3975(01)00281-X
Additional Information
- Van Cyr
- Affiliation: Department of Mathematics, Northwestern University, Evanston, Illinois 60208
- Address at time of publication: Department of Mathematics, 361 Olin, Bucknell University, Lewisburg, Pennsylvania 17837
- MR Author ID: 883244
- Email: cyr@math.northwestern.edu, van.cyr@bucknell.edu
- Bryna Kra
- Affiliation: Department of Mathematics, Northwestern University, Evanston, Illinois 60208
- MR Author ID: 363208
- ORCID: 0000-0002-5301-3839
- Email: kra@math.northwestern.edu
- Received by editor(s): March 29, 2013
- Received by editor(s) in revised form: April 10, 2013, and August 23, 2013
- Published electronically: February 4, 2015
- Additional Notes: The second author was partially supported by NSF grant $1200971$.
- © Copyright 2015 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 367 (2015), 6487-6537
- MSC (2010): Primary 37B50; Secondary 68R15, 37B10
- DOI: https://doi.org/10.1090/S0002-9947-2015-06391-0
- MathSciNet review: 3356945