Search for: All records

In the 1960s, Berger famously showed that translational tilings of\mathbb{Z}^{2}with multiple tiles are algorithmically undecidable. Recently, Bhattacharya proved the decidability oftranslational monotilings(tilings by translations of a single tile) in\mathbb{Z}^{2}. The decidability of translational monotilings in higher dimensions remained unsolved. In this paper, by combining our recently developed techniques with ideas introduced by Aanderaa–Lewis, we finally settle this problem, achieving the undecidability of translational monotilings of (periodic subsets of) virtually\mathbb{Z}^{2}spaces, namely, spaces of the form\mathbb{Z}^{2}\times G_{0}, whereG_{0}is a finite Abelian group. This also implies the undecidability of translational monotilings in\mathbb{Z}^{d},d\geq 3. 

We prove that for $$d\geq 0$$ and $$k\geq 2$$, for any subset $$A$$ of a discrete cube $$\{0,1\}^d$$, the $k-$higher energy of $$A$$ (i.e., the number of $2k-$tuples $$(a_1,a_2,\dots,a_{2k})$$ in $$A^{2k}$$ with $$a_1-a_2=a_3-a_4=\dots=a_{2k-1}-a_{2k}$$) is at most $$|A|^{\log_{2}(2^k+2)}$$, and $$\log_{2}(2^k+2)$$ is the best possible exponent. We also show that if $$d\geq 0$$ and $$2\leq k\leq 10$$, for any subset $$A$$ of a discrete cube $$\{0,1\}^d$$, the $k-$additive energy of $$A$$ (i.e., the number of $2k-$tuples $$(a_1,a_2,\dots,a_{2k})$$ in $$A^{2k}$$ with $$a_1+a_2+\dots+a_k=a_{k+1}+a_{k+2}+\dots+a_{2k}$$) is at most $$|A|^{\log_2{ \binom{2k}{k}}}$$, and $$\log_2{ \binom{2k}{k}}$$ is the best possible exponent. We discuss the analogous problems for the sets $$\{0,1,\dots,n\}^d$$ for $$n\geq2$$. 

Abstract Let $$X$$ be a measure space with a measure-preserving action $$(g,x) \mapsto g \cdot x$$ of an abelian group $$G$$. We consider the problem of understanding the structure of measurable tilings $$F \odot A = X$$ of $$X$$ by a measurable tile $$A \subset X$$ translated by a finite set $$F \subset G$$ of shifts, thus the translates $$f \cdot A$$, $$f \in F$$ partition $$X$$ up to null sets. Adapting arguments from previous literature, we establish a “dilation lemma” that asserts, roughly speaking, that $$F \odot A = X$$ implies $$F^{r} \odot A = X$$ for a large family of integer dilations $$r$$, and use this to establish a structure theorem for such tilings analogous to that established recently by the second and fourth authors. As applications of this theorem, we completely classify those random tilings of finitely generated abelian groups that are “factors of iid”, and show that measurable tilings of a torus $${\mathbb{T}}^{d}$$ can always be continuously (in fact linearly) deformed into a tiling with rational shifts, with particularly strong results in the low-dimensional cases $d=1,2$ (in particular resolving a conjecture of Conley, the first author, and Pikhurko in the $d=1$ case).