Explore the vast range of titles available.

We construct an example of a group G=Z2×G0 for a finite abelian group G0, a subset E of G0, and two finite subsets F1,F2 of G, such that it is undecidable in ZFC whether Z2×E can be tiled by translations of F1,F2. In particular, this implies that this tiling problem is aperiodic, in the sense that (in the standard universe of ZFC) there exist translational tilings of E by the tiles F1,F2, but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in Z2). A similar construction also applies for G=Zd for sufficiently large d. If one allows the group G0 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.

The periodic tiling conjecture asserts that any finite subset of a lattice \\(\\mathbb{Z}^d\\) which tiles that lattice by translations, in fact tiles periodically. In this work we disprove this conjecture for sufficiently large \\(d\\), which also implies a disproof of the corresponding conjecture for Euclidean spaces \\(\\mathbb{R}^d\\). In fact, we also obtain a counterexample in a group of the form \\(\\mathbb{Z}^2 \\times G_0\\) for some finite abelian \\(2\\)-group \\(G_0\\). Our methods rely on encoding a \"Sudoku puzzle\" whose rows and other non-horizontal lines are constrained to lie in a certain class of \"\\(2\\)-adically structured functions,\" in terms of certain functional equations that can be encoded in turn as a single tiling equation, and then demonstrating that solutions to this Sudoku puzzle exist, but are all non-periodic.

We construct an example of a group \\(G = \\mathbb{Z}^2 \\times G_0\\) for a finite abelian group \\(G_0\\), a subset \\(E\\) of \\(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 is aperiodic, in the sense that (in the standard universe of ZFC) there exist translational tilings of \\(E\\) by 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.

In the 60's, Berger famously showed that translational tilings of \\(\\mathbb{Z}^2\\) with multiple tiles are algorithmically undecidable. Recently, Bhattacharya proved the decidability of translational 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 and 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\\), where \\(G_0\\) is a finite Abelian group. This also implies the undecidability of translational monotilings in \\(\\mathbb{Z}^d\\), \\(d\\geq 3\\).

Let \\(\\Omega\\subset \\mathbb{R}^d\\) be a set of finite measure. The periodic tiling conjecture suggests that if \\(\\Omega\\) tiles \\(\\mathbb{R}^d\\) by translations then it admits at least one periodic tiling. Fuglede's conjecture suggests that \\(\\Omega\\) admits an orthogonal basis of exponential functions if and only if it tiles \\(\\mathbb{R}^d\\) by translations. Both conjectures are known to be false in sufficiently high dimensions, with all the so-far-known counterexamples being highly disconnected. On the other hand, both conjectures are known to be true for convex sets. In this work we study these conjectures for connected sets. We show that the periodic tiling conjecture, as well as both directions of Fuglede's conjecture are false for connected sets in sufficiently high dimensions.

The periodic tiling conjecture asserts that any finite subset of a lattice \\(\\mathbb{Z^d}\\) which tiles that lattice by translations, in fact tiles periodically. We announce here a disproof of this conjecture for sufficiently large \\(d\\), which also implies a disproof of the corresponding conjecture for Euclidean spaces \\(\\mathbb{R^d}\\). In fact, we also obtain a counterexample in a group of the form \\(\\mathbb{Z^2} \\times G_0\\) for some finite abelian \\(G_0\\). Our methods rely on encoding a certain class of \"\\(p\\)-adically structured functions\" in terms of certain functional equations.

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.

Let \\(\\Omega\\) be a convex polytope in \\(\\mathbb{R}^d\\). We say that \\(\\Omega\\) is spectral if the space \\(L^2(\\Omega)\\) admits an orthogonal basis consisting of exponential functions. There is a conjecture, which goes back to Fuglede (1974), that \\(\\Omega\\) is spectral if and only if it can tile the space by translations. It is known that if \\(\\Omega\\) tiles then it is spectral, but the converse was proved only in dimension \\(d=2\\), by Iosevich, Katz and Tao. By a result due to Kolountzakis, if a convex polytope \\(\\Omega\\subset \\mathbb{R}^d\\) is spectral, then it must be centrally symmetric. We prove that also all the facets of \\(\\Omega\\) are centrally symmetric. These conditions are necessary for \\(\\Omega\\) to tile by translations. We also develop an approach which allows us to prove that in dimension \\(d=3\\), any spectral convex polytope \\(\\Omega\\) indeed tiles by translations. Thus we obtain that Fuglede's conjecture is true for convex polytopes in \\(\\mathbb{R}^3\\).

We develop a new approach to address some classical questions concerning the size and structure of integer distance sets. Our main result is that any integer distance set in the Euclidean plane has all but a very small number of points lying on a single line or circle. From this, we deduce a near-optimal lower bound on the diameter of any non-collinear integer distance set of size \\(n\\) and a strong upper bound on the size of any integer distance set in \\([-N,N]^2\\) with no three points on a line and no four points on a circle.

A bounded set \\(\\Omega \\subset \\mathbb{R}^d\\) is called a spectral set if the space \\(L^2(\\Omega)\\) admits a complete orthogonal system of exponential functions. We prove that a cylindric set \\(\\Omega\\) is spectral if and only if its base is a spectral set. A similar characterization is obtained of the cylindric sets which can tile the space by translations.