The structure of translational tilings in Z^d

DOI10.19086/DA.28324MaRDI QIDQ5028503zbMATH OpenOpenAlexFDO

Authors Rachel Greenfeld, Terence Tao

Publication date 10 February 2022

Published in discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(24)

• On rationality of spectrums for spectral sets in \(\mathbb{R} \)
• 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
• The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
• Expansivity and periodicity in algebraic subshifts
• 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
• A reduction of lattice tiling by translates of a cubical cluster
• Algorithms for translational tiling
• Periodic structure of translational multi-tilings in the plane
• The structure of multiplicative tilings of the real line
• Universal spectra in \(G\times\mathbb{Z}_p\)

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)