## 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