An algebraic geometric approach to Nivat's conjecture

DOI10.1007/978-3-662-47666-6_22zbMATH Open1434.68266DBLPconf/icalp/KariS15arXiv1510.00177OpenAlexW2980575108WikidataQ123181793 ScholiaQ123181793MaRDI QIDQ2304526FDOQ2304526

Authors: Jarkko Kari, Michal Szabados 

Publication date: 12 March 2020

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: We study multidimensional configurations (infinite words) and subshifts of low pattern complexity using tools of algebraic geometry. We express the configuration as a multivariate formal power series over integers and investigate the setup when there is a non-trivial annihilating polynomial: a non-zero polynomial whose formal product with the power series is zero. Such annihilator exists, for example, if the number of distinct patterns of some finite shape D in the configuration is at most the size |D| of the shape. This is our low pattern complexity assumption. We prove that the configuration must be a sum of periodic configurations over integers, possibly with unbounded values. As a specific application of the method we obtain an asymptotic version of the well-known Nivat's conjecture: we prove that any two-dimensional, non-periodic configuration can satisfy the low pattern complexity assumption with respect to only finitely many distinct rectangular shapes D.

Full work available at URL: https://arxiv.org/abs/1510.00177

Recommendations

• An algebraic geometric approach to multidimensional words
• Nivat's conjecture and pattern complexity in algebraic subshifts
• Nivat's conjecture holds for sums of two periodic configurations
• An alphabetical approach to Nivat's conjecture

zbMATH Keywords

algebraic geometrysymbolic dynamicsperiodicityLaurent polynomialsNivat's conjecturepattern complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Symbolic dynamics (37B10) Combinatorics on words (68R15) Formal power series rings (13F25) Multidimensional shifts of finite type (37B51)

Cites Work

• An Introduction to Symbolic Dynamics and Coding
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tiling the line with translates of one tile
• Tiling the integers with translates of one finite set
• Title not available (Why is that?)
• On translating one polyomino to tile the plane
• On a conjecture on bidimensional words.
• Periodicity and local complexity
• The complexity of functions on lattices
• Nonexpansive \(\mathbb{Z}^{2}\)-subdynamics and Nivat's conjecture
• Complexity of short rectangles and periodicity
• Algebraic theory of brick packing. II
• The rectangle complexity of functions on two-dimensional lattices
• Algebraic theory of brick packing. I
• Periodicity and decidability of tilings of \(\mathbb{Z}^2\)
• An algebraic geometric approach to multidimensional words

This page was built for publication: An algebraic geometric approach to Nivat's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2304526)