skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Undecidable Translational Tilings with Only Two Tiles, or One Nonabelian Tile
Abstract We construct an example of a group$$G = \mathbb {Z}^2 \times G_0$$ G = Z 2 × G 0 for a finite abelian group $$G_0$$ G 0 , a subsetEof $$G_0$$ G 0 , and two finite subsets$$F_1,F_2$$ F 1 , F 2 of G, such that it is undecidable in ZFC whether$$\mathbb {Z}^2\times E$$ Z 2 × E can be tiled by translations of$$F_1,F_2$$ 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$$ 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$$ Z 2 ). A similar construction also applies for$$G=\mathbb {Z}^d$$ G = Z d for sufficiently large d. If one allows the group$$G_0$$ 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
Award ID(s):
1764034
PAR ID:
10389611
Author(s) / Creator(s):
;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Discrete & Computational Geometry
Volume:
70
Issue:
4
ISSN:
0179-5376
Format(s):
Medium: X Size: p. 1652-1706
Size(s):
p. 1652-1706
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; (, Mathematische Annalen)
    Abstract Given a prime powerqand$$n \gg 1$$ n ≫ 1 , we prove that every integer in a large subinterval of the Hasse–Weil interval$$[(\sqrt{q}-1)^{2n},(\sqrt{q}+1)^{2n}]$$ [ ( q - 1 ) 2 n , ( q + 1 ) 2 n ] is$$\#A({\mathbb {F}}_q)$$ # A ( F q ) for some ordinary geometrically simple principally polarized abelian varietyAof dimensionnover$${\mathbb {F}}_q$$ F q . As a consequence, we generalize a result of Howe and Kedlaya for$${\mathbb {F}}_2$$ F 2 to show that for each prime powerq, every sufficiently large positive integer is realizable, i.e.,$$\#A({\mathbb {F}}_q)$$ # A ( F q ) for some abelian varietyAover$${\mathbb {F}}_q$$ F q . Our result also improves upon the best known constructions of sequences of simple abelian varieties with point counts towards the extremes of the Hasse–Weil interval. A separate argument determines, for fixedn, the largest subinterval of the Hasse–Weil interval consisting of realizable integers, asymptotically as$$q \rightarrow \infty $$ q → ∞ ; this gives an asymptotically optimal improvement of a 1998 theorem of DiPippo and Howe. Our methods are effective: We prove that if$$q \le 5$$ q ≤ 5 , then every positive integer is realizable, and for arbitraryq, every positive integer$$\ge q^{3 \sqrt{q} \log q}$$ ≥ q 3 q log q is realizable. 
    more » « less
  2. ; (, Mathematische Annalen)
    Abstract We study holomorphic mapsFfrom a smooth Levi non-degenerate real hypersurface$$ M_{\ell }\subset {\mathbb {C}}^n $$ M ℓ ⊂ C n into a hyperquadric$$ {\mathbb {H}}_{\ell '}^N $$ H ℓ ′ N with signatures$$ \ell \le (n-1)/2 $$ ℓ ≤ ( n - 1 ) / 2 and$$ \ell '\le (N-1)/2,$$ ℓ ′ ≤ ( N - 1 ) / 2 , respectively. Assuming that$$ N - n < n - 1,$$ N - n < n - 1 , we prove that if$$ \ell = \ell ',$$ ℓ = ℓ ′ , thenFis either CR transversal to$$ {\mathbb {H}}_{\ell }^N $$ H ℓ N at every point of$$ M_{\ell },$$ M ℓ , or it maps a neighborhood of$$ M_{\ell } $$ M ℓ in$$ {\mathbb {C}}^n $$ C n into$$ {\mathbb {H}}_{\ell }^N.$$ H ℓ N . Furthermore, in the case where$$ \ell ' > \ell ,$$ ℓ ′ > ℓ , we show that ifFis not CR transversal at$$0\in M_\ell ,$$ 0 ∈ M ℓ , then it must be transversally flat. The latter is best possible. 
    more » « less
  3. ; ; ; ; ; ; ; ; ; ; et al (, Graphs and Combinatorics)
    Abstract Let$$\mathbb {F}_q^d$$ F q d be thed-dimensional vector space over the finite field withqelements. For a subset$$E\subseteq \mathbb {F}_q^d$$ E ⊆ F q d and a fixed nonzero$$t\in \mathbb {F}_q$$ t ∈ F q , let$$\mathcal {H}_t(E)=\{h_y: y\in E\}$$ H t ( E ) = { h y : y ∈ E } , where$$h_y:E\rightarrow \{0,1\}$$ h y : E → { 0 , 1 } is the indicator function of the set$$\{x\in E: x\cdot y=t\}$$ { x ∈ E : x · y = t } . Two of the authors, with Maxwell Sun, showed in the case$$d=3$$ d = 3 that if$$|E|\ge Cq^{\frac{11}{4}}$$ | E | ≥ C q 11 4 andqis sufficiently large, then the VC-dimension of$$\mathcal {H}_t(E)$$ H t ( E ) is 3. In this paper, we generalize the result to arbitrary dimension by showing that the VC-dimension of$$\mathcal {H}_t(E)$$ H t ( E ) isdwhenever$$E\subseteq \mathbb {F}_q^d$$ E ⊆ F q d with$$|E|\ge C_d q^{d-\frac{1}{d-1}}$$ | E | ≥ C d q d - 1 d - 1 . 
    more » « less
  4. ; ; ; ; ; (, Letters in Mathematical Physics)
    Abstract The amplituhedron is a mathematical object which was introduced to provide a geometric origin of scattering amplitudes in$$\mathcal {N}=4$$ N = 4 super Yang–Mills theory. It generalizescyclic polytopesand thepositive Grassmannianand has a very rich combinatorics with connections to cluster algebras. In this article, we provide a series of results about tiles and tilings of the$$m=4$$ m = 4 amplituhedron. Firstly, we provide a full characterization of facets of BCFW tiles in terms of cluster variables for$$\text{ Gr}_{4,n}$$ Gr 4 , n . Secondly, we exhibit a tiling of the$$m=4$$ m = 4 amplituhedron which involves a tile which does not come from the BCFW recurrence—thespuriontile, which also satisfies all cluster properties. Finally, strengthening the connection with cluster algebras, we show that each standard BCFW tile is the positive part of a cluster variety, which allows us to compute the canonical form of each such tile explicitly in terms of cluster variables for$$\text{ Gr}_{4,n}$$ Gr 4 , n . This paper is a companion to our previous paper “Cluster algebras and tilings for the$$m=4$$ m = 4 amplituhedron.” 
    more » « less
  5. ; (, Research in Number Theory)
    Abstract We present an efficient algorithm to compute the Euler factor of a genus 2 curve$$C/\mathbb {Q}$$ C / Q at an odd primepthat is of bad reduction forCbut of good reduction for the Jacobian ofC(a prime of “almost good” reduction). Our approach is based on the theory of cluster pictures introduced by Dokchitser, Dokchitser, Maistret, and Morgan, which allows us to reduce the problem to a short, explicit computation over$$\mathbb {Z}$$ Z and$$\mathbb {F}_p$$ F p , followed by a point-counting computation on two elliptic curves over$$\mathbb {F}_p$$ F p , or a single elliptic curve over$$\mathbb {F}_{p^2}$$ F p 2 . A key feature of our approach is that we avoid the need to compute a regular model forC. This allows us to efficiently compute many examples that are infeasible to handle using the algorithms currently available in computer algebra systems such as Magma and Pari/GP. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email