### Abstract

For a finite alphabet A and η : ℤ → A, the Morse-Hedlund Theorem states that η is periodic if and only if there exists n ∈ ℕ such that the block complexity function P_{η}(n) satisfies P_{η}(n) ≤ n, and this statement is naturally studied by analyzing the dynamics of a ℤ-action associated with η. In dimension two, we analyze the subdynamics of a ℤ^{2}-action associated with η : ℤ^{2} → A and show that if there exist n, k ∈ ℕ such that the n × k rectangular complexity P_{η}(n, k) satisfies P_{η}(n, k) ≤ nk, then the periodicity of η is equivalent to a statement about the expansive subspaces of this action. As a corollary, we show that if there exist n, k ∈ ℕ such that (formula presented) then η is periodic. This proves a weak form of a conjecture of Nivat in the combinatorics of words.

Original language | English (US) |
---|---|

Pages (from-to) | 6487-6537 |

Number of pages | 51 |

Journal | Transactions of the American Mathematical Society |

Volume | 367 |

Issue number | 9 |

DOIs | |

State | Published - Jan 1 2015 |

### Keywords

- Block complexity
- Nivat’s Conjecture
- Nonexpansive subdynamics
- Periodicity
- ℤ-subshift

### ASJC Scopus subject areas

- Mathematics(all)
- Applied Mathematics