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
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
- Subject(s) / Keyword(s):
- 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
-
DeMarco, Krieger, and Ye conjectured that there is a uniform boundB, depending only on the degreed, so that any pair of holomorphic maps$$f, g :{\mathbb {P}}^1\to {\mathbb {P}}^1$$with degree$$d$$will either share all of their preperiodic points or have at most$$B$$in common. Here we show that this uniform bound holds for a Zariski open and dense set in the space of all pairs,$$\mathrm {Rat}_d \times \mathrm {Rat}_d$$, for each degree$$d\geq 2$$. The proof involves a combination of arithmetic intersection theory and complex-dynamical results, especially as developed recently by Gauthier and Vigny, Yuan and Zhang, and Mavraki and Schmidt. In addition, we present alternate proofs of the main results of DeMarco, Krieger, and Ye [Uniform Manin-Mumford for a family of genus 2 curves, Ann. of Math. (2)191(2020), 949–1001;Common preperiodic points for quadratic polynomials, J. Mod. Dyn.18(2022), 363–413] and of Poineau [Dynamique analytique sur$$\mathbb {Z}$$II : Écart uniforme entre Lattès et conjecture de Bogomolov-Fu-Tschinkel, Preprint (2022), arXiv:2207.01574 [math.NT]]. In fact, we prove a generalization of a conjecture of Bogomolov, Fu, and Tschinkel in a mixed setting of dynamical systems and elliptic curves.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
An official website of the United States government

