Publication:2304526

DOI10.1007/978-3-662-47666-6_22zbMath1434.68266DBLPconf/icalp/KariS15arXiv1510.00177OpenAlexW2980575108WikidataQ123181793 ScholiaQ123181793MaRDI QIDQ2304526

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

zbMATH Keywords

periodicityLaurent polynomialssymbolic dynamicsalgebraic geometryNivat's conjecturepattern complexity

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Periodicity and local complexity
• Complexity of short rectangles and periodicity
• Algebraic theory of brick packing. I
• On translating one polyomino to tile the plane
• Tiling the integers with translates of one finite set
• The complexity of functions on lattices
• Algebraic theory of brick packing. II
• On a conjecture on bidimensional words.
• Tiling the line with translates of one tile
• An algebraic geometric approach to Nivat's conjecture
• An Algebraic Geometric Approach to Multidimensional Words
• An Introduction to Symbolic Dynamics and Coding
• Periodicity and decidability of tilings of ℤ2
• Nonexpansive $\mathbb {Z}^2$-subdynamics and Nivat’s Conjecture
• The rectangle complexity of functions on two-dimensional lattices

Related Items (17)

On perfect coverings of two-dimensional grids ⋮ An Algebraic Geometric Approach to Multidimensional Words ⋮ Expansivity and periodicity in algebraic subshifts ⋮ On periodic decompositions, one-sided nonexpansive directions and Nivat's conjecture ⋮ Nivat's conjecture and pattern complexity in algebraic subshifts ⋮ Minimal Complexities for Infinite Words Written with d Letters ⋮ On periodic decompositions and nonexpansive lines ⋮ The structure of translational tilings in $\mathbb{Z}^d$ ⋮ On forced periodicity of perfect colorings ⋮ An alphabetical approach to Nivat’s conjecture ⋮ Decidability and periodicity of low complexity tilings ⋮ Two-dimensional comma-free and cylindric codes ⋮ No lattice tiling of \(\mathbb{Z}^n\) by Lee sphere of radius 2 ⋮ An algebraic geometric approach to Nivat's conjecture ⋮ Aperiodic two-dimensional words of small abelian complexity ⋮ Recurrence along directions in multidimensional words ⋮ Domino problem for pretty low complexity subshifts

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