An official website of the United States government
Abstract We construct an example of a group$$G = \mathbb {Z}^2 \times G_0$$ for a finite abelian group $$G_0$$ , a subsetEof $$G_0$$ , and two finite subsets$$F_1,F_2$$ of G, such that it is undecidable in ZFC whether$$\mathbb {Z}^2\times E$$ can be tiled by translations of$$F_1,F_2$$ . In particular, this implies that this tiling problem isaperiodic, in the sense that (in the standard universe of ZFC) there exist translational tilings ofEby the tiles$$F_1,F_2$$ , but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in $$\mathbb {Z}^2$$ ). A similar construction also applies for$$G=\mathbb {Z}^d$$ for sufficiently large d. If one allows the group$$G_0$$ to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile F. The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.
more »
« less
This content will become publicly available on June 21, 2026
Undecidability of translational monotilings
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.
more »
« less
- Award ID(s):
- 2448416
- PAR ID:
- 10611298
- Publisher / Repository:
- EMS Press
- Date Published:
- Journal Name:
- Journal of the European Mathematical Society
- ISSN:
- 1435-9855
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Fix an integer$$d\ge 2$$ . The parameters$$c_0\in \overline{\mathbb {Q}}$$ for which the unicritical polynomial$$f_{d,c}(z)=z^d+c\in \mathbb {C}[z]$$ has finite postcritical orbit, also known asMisiurewiczparameters, play a significant role in complex dynamics. Recent work of Buff, Epstein, and Koch proved the first known cases of a long-standing dynamical conjecture of Milnor using their arithmetic properties, about which relatively little is otherwise known. Continuing our work from a companion paper, we address further arithmetic properties of Misiurewicz parameters, especially the nature of the algebraic integers obtained by evaluating the polynomial defining one such parameter at a different Misiurewicz parameter. In the most challenging such combinations, we describe a connection between such algebraic integers and the multipliers of associated periodic points. As part of our considerations, we also introduce a new class of polynomials we callp-special, which may be of independent number theoretic interest.more » « less
-
Let\Sigmabe a strictly convex, compact patch of aC^{2}hypersurface in\mathbb{R}^{n}, with non-vanishing Gaussian curvature and surface measured\sigmainduced by the Lebesgue measure in\mathbb{R}^{n}. The Mizohata–Takeuchi conjecture states that \int |\widehat{g d\sigma}|^{2} w \leq C \|Xw\|_{\infty} \int |g|^{2} for allg\in L^{2}(\Sigma)and all weightsw \colon \mathbb{R}^{n}\rightarrow [0,+\infty), whereXdenotes theX-ray transform. As partial progress towards the conjecture, we show, as a straightforward consequence of recently-established decoupling inequalities, that for every\varepsilon>0, there exists a positive constantC_{\varepsilon}, which depends only on\Sigmaand\varepsilon, such that for allR \geq 1and all weightsw \colon \mathbb{R}^{n}\rightarrow [0,+\infty), we have \int_{B_R}|\widehat{g d\sigma}|^{2} w \leq C_{\varepsilon} R^{\varepsilon} \sup_{T} \Big(\int_{T} w^{(n+1)/2}\Big)^{2/(n+1)}\int |g|^{2}, whereTranges over the family of tubes in\mathbb{R}^{n}of dimensionsR^{1/2}\times \cdots \times R^{1/2}\times R. From this we deduce the Mizohata–Takeuchi conjecture with anR^{(n-1)/(n+1)}-loss; i.e., that \int_{B_R}|\widehat{g d\sigma}|^{2} w \leq C_{\varepsilon} R^{\frac{n-1}{n+1}+ \varepsilon}\|Xw\|_{\infty} \int |g|^{2} for any ballB_{R}of radiusRand any\varepsilon>0. The power(n-1)/(n+1)here cannot be replaced by anything smaller unless properties of\widehat{g d\sigma}beyond ‘decoupling axioms’ are exploited. We also provide estimates which improve this inequality under various conditions on the weight, and discuss some new cases where the conjecture holds.more » « less
-
For a net of C*-algebras on a discrete metric space, we introduce a bimodule version of the DHR tensor category and show that it is an invariant of quasi-local algebras under isomorphisms with bounded spread. For abstract spin systems on a latticeL\subseteq \mathbb{R}^{n}satisfying a weak version of Haag duality, we construct a braiding on these categories. Applying the general theory to quasi-local algebrasAof operators on a lattice invariant under a (categorical) symmetry, we obtain a homomorphism from the group of symmetric QCA to\mathbf{Aut}_{\mathrm{br}}(\mathbf{DHR}(A)), containing symmetric finite-depth circuits in the kernel. For a spin chain with fusion categorical symmetry\mathcal{D}, we show that the DHR category of the quasi-local algebra of symmetric operators is equivalent to the Drinfeld center\mathcal{Z}(\mathcal{D}). We use this to show that, for the double spin-flip action\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}\curvearrowright \mathbb{C}^{2}\otimes \mathbb{C}^{2}, the group of symmetric QCA modulo symmetric finite-depth circuits in 1D contains a copy ofS_{3}; hence, it is non-abelian, in contrast to the case with no symmetry.more » « less
-
Abstract Consider two half-spaces$$H_1^+$$ and$$H_2^+$$ in$${\mathbb {R}}^{d+1}$$ whose bounding hyperplanes$$H_1$$ and$$H_2$$ are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$ is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$ , which contains a great subsphere of dimension$$d-2$$ and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$ and consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$ . A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$ . The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere.more » « less
