The structure of translational tilings in Z^d

DOI10.19086/DA.28324zbMATH Open1482.05036arXiv2010.03254OpenAlexW3204665133MaRDI QIDQ5028503FDOQ5028503

Authors: Rachel Greenfeld, Terence Tao 

Publication date: 10 February 2022

Published in: discrete Analysis (Search for Journal in Brave)

Abstract: We obtain structural results on translational tilings of periodic functions in $mathbb{Z}^d$ by finite tiles. In particular, we show that any level one tiling of a periodic set in $mathbb{Z}^2$ must be weakly periodic (the disjoint union of sets that are individually periodic in one direction), but present a counterexample of a higher level tiling of $mathbb{Z}^2$ that fails to be weakly periodic. We also establish a quantitative version of the two-dimensional periodic tiling conjecture which asserts that any finite tile in $mathbb{Z}^2$ that admits a tiling, must admit a periodic tiling, by providing a polynomial bound on the period; this also gives an exponential-type bound on the computational complexity of the problem of deciding whether a given finite subset of $mathbb{Z}^2$ tiles or not. As a byproduct of our structural theory, we also obtain an explicit formula for a universal period for all tilings of a one-dimensional tile.

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

Recommendations

• Periodicity and decidability of tilings of \(\mathbb{Z}^2\)
• Tiling the line with translates of one tile
• Algorithms for translational tiling
• Periodic structure of translational multi-tilings in the plane
• On the structure of multiple translational tilings by polygonal regions

zbMATH Keywords

tilingdecidabilityperiodicity

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (n) dimensions (aspects of discrete geometry) (52C22) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25) Combinatorial complexity of geometric structures (52C45)

Cites Work

• Higher order Fourier analysis
• Spectral pairs in Cartesian coordinates
• Tiling the line with translates of one tile
• Title not available (Why is that?)
• The Fuglede conjecture holds in \(\mathbb{Z}_p\times \mathbb{Z}_p\)
• Title not available (Why is that?)
• The undecidability of the domino problem
• Title not available (Why is that?)
• Caracterisation des operateurs hypoelliptiques homogenes
• Tiling the integers with translates of one finite set
• Spectrality and tiling by cylindric domains
• Convex bodies which tile space by translation
• TORSION POINTS ON CURVES
• Undecidability and nonperiodicity for tilings of the plane
• Structure of tilings of the line by a function
• Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino
• Rédei-matrices and applications
• Uniform partitions of unity on locally compact groups
• Tesselation of integers
• Divisibility of integer polynomials and tilings of the integers
• Factoring groups into subsets.
• Division points on curves
• Estimate of a complete rational trigonometric sum
• Rigidity of planar tilings
• Convex bodies which tile space by translation: Acknowledgement of priority
• Indecomposable tilings of the integers with exponentially long periods
• Tilings of the integers can have superpolynomial periods
• Tiling, circle packing and exponential sums over finite fields
• Spectrality of product domains and Fuglede's conjecture for convex polytopes
• Tiling by translates of a function: results and open problems
• On non-periodic tilings of the real line by a function
• Periodicity and decidability of tilings of \(\mathbb{Z}^2\)
• Tiling \(\mathbb Z^2\) with translations of one set

Cited In (24)

• A Fuglede type conjecture for discrete Gabor bases
• Undecidable translational tilings with only two tiles, or one nonabelian tile
• On forced periodicity of perfect colorings
• Periodicity and decidability of tilings of \(\mathbb{Z}^2\)
• Tiling by translates of a function: results and open problems
• Spectral sets and tiles in \(\mathbb{Z}_p^2 \times \mathbb{Z}_q^2\)
• Equivalence between Clar covering polynomials of single zigzag chains and tiling polynomials of \(2 \times n\) rectangles
• Cube tilings with linear constraints
• An aperiodic monotile
• Expansivity and periodicity in algebraic subshifts
• The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
• Combinatorial and harmonic-analytic methods for integer tilings
• Characterization of the Two-Dimensional Fivefold Translative Tiles
• Max-norm Ramsey theory
• Spectral theory of spin substitutions
• The Coven-Meyerowitz tiling conditions for 3 odd prime factors
• Periodicity of one-dimensional tilings
• Tiling \(\mathbb Z^2\) with translations of one set
• Periodic structure of translational multi-tilings in the plane
• Algorithms for translational tiling
• A reduction of lattice tiling by translates of a cubical cluster
• The structure of multiplicative tilings of the real line
• Universal spectra in \(G\times\mathbb{Z}_p\)
• On rationality of spectrums for spectral sets in \(\mathbb{R} \)

This page was built for publication: The structure of translational tilings in \(\mathbb{Z}^d\)

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