You are currently browsing the tag archive for the ‘tiling’ tag.
Jan Grebik, Rachel Greenfeld, Vaclav Rozhon and I have just uploaded to the arXiv our preprint “Measurable tilings by abelian group actions“. This paper is related to an earlier paper of Rachel Greenfeld and myself concerning tilings of lattices , but now we consider the more general situation of tiling a measure space
by a tile
shifted by a finite subset
of shifts of an abelian group
that acts in a measure-preserving (or at least quasi-measure-preserving) fashion on
. For instance,
could be a torus
,
could be a positive measure subset of that torus, and
could be the group
, acting on
by translation.
If is a finite subset of
with the property that the translates
,
of
partition
up to null sets, we write
, and refer to this as a measurable tiling of
by
(with tiling set
). For instance, if
is the torus
, we can create a measurable tiling with
and
. Our main results are the following:
- By modifying arguments from previous papers (including the one with Greenfeld mentioned above), we can establish the following “dilation lemma”: a measurable tiling
automatically implies further measurable tilings
, whenever
is an integer coprime to all primes up to the cardinality
of
.
- By averaging the above dilation lemma, we can also establish a “structure theorem” that decomposes the indicator function
of
into components, each of which are invariant with respect to a certain shift in
. We can establish this theorem in the case of measure-preserving actions on probability spaces via the ergodic theorem, but one can also generalize to other settings by using the device of “measurable medial means” (which relates to the concept of a universally measurable set).
- By applying this structure theorem, we can show that all measurable tilings
of the one-dimensional torus
are rational, in the sense that
lies in a coset of the rationals
. This answers a recent conjecture of Conley, Grebik, and Pikhurko; we also give an alternate proof of this conjecture using some previous results of Lagarias and Wang.
- For tilings
of higher-dimensional tori, the tiling need not be rational. However, we can show that we can “slide” the tiling to be rational by giving each translate
of
a “velocity”
, and for every time
, the translates
still form a partition of
modulo null sets, and at time
the tiling becomes rational. In particular, if a set
can tile a torus in an irrational fashion, then it must also be able to tile the torus in a rational fashion.
- In the two-dimensional case
one can arrange matters so that all the velocities
are parallel. If we furthermore assume that the tile
is connected, we can also show that the union of all the translates
with a common velocity
form a
-invariant subset of the torus.
- Finally, we show that tilings
of a finitely generated discrete group
, with
a finite group, cannot be constructed in a “local” fashion (we formalize this probabilistically using the notion of a “factor of iid process”) unless the tile
is contained in a single coset of
. (Nonabelian local tilings, for instance of the sphere by rotations, are of interest due to connections with the Banach-Tarski paradox; see the aforementioned paper of Conley, Grebik, and Pikhurko. Unfortunately, our methods seem to break down completely in the nonabelian case.)
I’ve just uploaded to the arXiv my preprint “Perfectly packing a square by squares of nearly harmonic sidelength“. This paper concerns a variant of an old problem of Meir and Moser, who asks whether it is possible to perfectly pack squares of sidelength for
into a single square or rectangle of area
. (The following variant problem, also posed by Meir and Moser and discussed for instance in this MathOverflow post, is perhaps even more well known: is it possible to perfectly pack rectangles of dimensions
for
into a single square of area
?) For the purposes of this paper, rectangles and squares are understood to have sides parallel to the axes, and a packing is perfect if it partitions the region being packed up to sets of measure zero. As one partial result towards these problems, it was shown by Paulhus that squares of sidelength
for
can be packed (not quite perfectly) into a single rectangle of area
, and rectangles of dimensions
for
can be packed (again not quite perfectly) into a single square of area
. (Paulhus’s paper had some gaps in it, but these were subsequently repaired by Grzegorek and Januszewski.)
Another direction in which partial progress has been made is to consider instead the problem of packing squares of sidelength ,
perfectly into a square or rectangle of total area
, for some fixed constant
(this lower bound is needed to make the total area
finite), with the aim being to get
as close to
as possible. Prior to this paper, the most recent advance in this direction was by Januszewski and Zielonka last year, who achieved such a packing in the range
.
In this paper we are able to get arbitrarily close to
(which turns out to be a “critical” value of this parameter), but at the expense of deleting the first few tiles:
Theorem 1 If, and
is sufficiently large depending on
, then one can pack squares of sidelength
,
perfectly into a square of area
.
As in previous works, the general strategy is to execute a greedy algorithm, which can be described somewhat incompletely as follows.
- Step 1: Suppose that one has already managed to perfectly pack a square
of area
by squares of sidelength
for
, together with a further finite collection
of rectangles with disjoint interiors. (Initially, we would have
and
, but these parameter will change over the course of the algorithm.)
- Step 2: Amongst all the rectangles in
, locate the rectangle
of the largest width (defined as the shorter of the two sidelengths of
).
- Step 3: Pack (as efficiently as one can) squares of sidelength
for
into
for some
, and decompose the portion of
not covered by this packing into rectangles
.
- Step 4: Replace
by
, replace
by
, and return to Step 1.
The main innovation of this paper is to perform Step 3 somewhat more efficiently than in previous papers.
The above algorithm can get stuck if one reaches a point where one has already packed squares of sidelength for
, but that all remaining rectangles
in
have width less than
, in which case there is no obvious way to fit in the next square. If we let
and
denote the width and height of these rectangles
, then the total area of the rectangles must be
In comparison, the perimeter of the squares that one has already packed is equal to
By choosing the parameter suitably large (and taking
sufficiently large depending on
), one can then prove the theorem. (In order to do some technical bookkeeping and to allow one to close an induction in the verification of the algorithm’s correctness, it is convenient to replace the perimeter
by a slightly weighted variant
for a small exponent
, but this is a somewhat artificial device that somewhat obscures the main ideas.)
Rachel Greenfeld and I have just uploaded to the arXiv our preprint “Undecidable translational tilings with only two tiles, or one nonabelian tile“. This paper studies the following question: given a finitely generated group , a (periodic) subset
of
, and finite sets
in
, is it possible to tile
by translations
of the tiles
? That is to say, is there a solution
to the (translational) tiling equation
A bit more specifically, the paper studies the decidability of the above question. There are two slightly different types of decidability one could consider here:
- Logical decidability. For a given
, one can ask whether the solvability of the tiling equation (1) is provable or disprovable in ZFC (where we encode all the data
by appropriate constructions in ZFC). If this is the case we say that the tiling equation (1) (or more precisely, the solvability of this equation) is logically decidable, otherwise it is logically undecidable.
- Algorithmic decidability. For data
in some specified class (and encoded somehow as binary strings), one can ask whether the solvability of the tiling equation (1) can be correctly determined for all choices of data in this class by the output of some Turing machine that takes the data as input (encoded as a binary string) and halts in finite time, returning either YES if the equation can be solved or NO otherwise. If this is the case, we say the tiling problem of solving (1) for data in the given class is algorithmically decidable, otherwise it is algorithmically undecidable.
Note that the notion of logical decidability is “pointwise” in the sense that it pertains to a single choice of data , whereas the notion of algorithmic decidability pertains instead to classes of data, and is only interesting when this class is infinite. Indeed, any tiling problem with a finite class of data is trivially decidable because one could simply code a Turing machine that is basically a lookup table that returns the correct answer for each choice of data in the class. (This is akin to how a student with a good memory could pass any exam if the questions are drawn from a finite list, merely by memorising an answer key for that list of questions.)
The two notions are related as follows: if a tiling problem (1) is algorithmically undecidable for some class of data, then the tiling equation must be logically undecidable for at least one choice of data for this class. For if this is not the case, one could algorithmically decide the tiling problem by searching for proofs or disproofs that the equation (1) is solvable for a given choice of data; the logical decidability of all such solvability questions will ensure that this algorithm always terminates in finite time.
One can use the Gödel completeness theorem to interpret logical decidability in terms of universes (also known as structures or models) of ZFC. In addition to the “standard” universe of sets that we believe satisfies the axioms of ZFC, there are also other “nonstandard” universes
that also obey the axioms of ZFC. If the solvability of a tiling equation (1) is logically undecidable, this means that such a tiling exists in some universes of ZFC, but not in others.
(To continue the exam analogy, we thus see that a yes-no exam question is logically undecidable if the answer to the question is yes in some parallel universes, but not in others. A course syllabus is algorithmically undecidable if there is no way to prepare for the final exam for the course in a way that guarantees a perfect score (in the standard universe).)
Questions of decidability are also related to the notion of aperiodicity. For a given , a tiling equation (1) is said to be aperiodic if the equation (1) is solvable (in the standard universe
of ZFC), but none of the solutions (in that universe) are completely periodic (i.e., there are no solutions
where all of the
are periodic). Perhaps the most well-known example of an aperiodic tiling (in the context of
, and using rotations as well as translations) come from the Penrose tilings, but there are many others besides.
It was (essentially) observed by Hao Wang in the 1960s that if a tiling equation is logically undecidable, then it must necessarily be aperiodic. Indeed, if a tiling equation fails to be aperiodic, then (in the standard universe) either there is a periodic tiling, or there are no tilings whatsoever. In the former case, the periodic tiling can be used to give a finite proof that the tiling equation is solvable; in the latter case, the compactness theorem implies that there is some finite fragment of that is not compatible with being tiled by
, and this provides a finite proof that the tiling equation is unsolvable. Thus in either case the tiling equation is logically decidable.
This observation of Wang clarifies somewhat how logically undecidable tiling equations behave in the various universes of ZFC. In the standard universe, tilings exist, but none of them will be periodic. In nonstandard universes, tilings may or may not exist, and the tilings that do exist may be periodic (albeit with a nonstandard period); but there must be at least one universe in which no tiling exists at all.
In one dimension when (or more generally
with
a finite group), a simple pigeonholing argument shows that no tiling equations are aperiodic, and hence all tiling equations are decidable. However the situation changes in two dimensions. In 1966, Berger (a student of Wang) famously showed that there exist tiling equations (1) in the discrete plane
that are aperiodic, or even logically undecidable; in fact he showed that the tiling problem in this case (with arbitrary choices of data
) was algorithmically undecidable. (Strictly speaking, Berger established this for a variant of the tiling problem known as the domino problem, but later work of Golomb showed that the domino problem could be easily encoded within the tiling problem.) This was accomplished by encoding the halting problem for Turing machines into the tiling problem (or domino problem); the latter is well known to be algorithmically undecidable (and thus have logically undecidable instances), and so the latter does also. However, the number of tiles
required for Berger’s construction was quite large: his construction of an aperiodic tiling required
tiles, and his construction of a logically undecidable tiling required an even larger (and not explicitly specified) collection of tiles. Subsequent work by many authors did reduce the number of tiles required; in the
setting, the current world record for the fewest number of tiles in an aperiodic tiling is
(due to Amman, Grunbaum, and Shephard) and for a logically undecidable tiling is
(due to Ollinger). On the other hand, it is conjectured (see Grunbaum-Shephard and Lagarias-Wang) that one cannot lower
all the way to
:
Conjecture 1 (Periodic tiling conjecture) Ifis a periodic subset of a finitely generated abelian group
, and
is a finite subset of
, then the tiling equation
is not aperiodic.
This conjecture is known to be true in two dimensions (by work of Bhattacharya when , and more recently by us when
), but remains open in higher dimensions. By the preceding discussion, the conjecture implies that every tiling equation with a single tile is logically decidable, and the problem of whether a given periodic set can be tiled by a single tile is algorithmically decidable.
In this paper we show on the other hand that aperiodic and undecidable tilings exist when , at least if one is permitted to enlarge the group
a bit:
Theorem 2 (Logically undecidable tilings)
- (i) There exists a group
of the form
for some finite abelian
, a subset
of
, and finite sets
such that the tiling equation
is logically undecidable (and hence also aperiodic).
- (ii) There exists a dimension
, a periodic subset
of
, and finite sets
such that tiling equation
is logically undecidable (and hence also aperiodic).
- (iii) There exists a non-abelian finite group
(with the group law still written additively), a subset
of
, and a finite set
such that the nonabelian tiling equation
is logically undecidable (and hence also aperiodic).
We also have algorithmic versions of this theorem. For instance, the algorithmic version of (i) is that the problem of determining solvability of the tiling equation for a given choice of finite abelian group
, subset
of
, and finite sets
is algorithmically undecidable. Similarly for (ii), (iii).
This result (together with a negative result discussed below) suggest to us that there is a significant qualitative difference in the theory of tiling by a single (abelian) tile, and the
theory of tiling with multiple tiles (or one non-abelian tile). (The positive results on the periodic tiling conjecture certainly rely heavily on the fact that there is only one tile, in particular there is a “dilation lemma” that is only available in this setting that is of key importance in the two dimensional theory.) It would be nice to eliminate the group
from (i) (or to set
in (ii)), but I think this would require a fairly significant modification of our methods.
Like many other undecidability results, the proof of Theorem 2 proceeds by a sequence of reductions, in which the undecidability of one problem is shown to follow from the undecidability of another, more “expressive” problem that can be encoded inside the original problem, until one reaches a problem that is so expressive that it encodes a problem already known to be undecidable. Indeed, all three undecidability results are ultimately obtained from Berger’s undecidability result on the domino problem.
The first step in increasing expressiveness is to observe that the undecidability of a single tiling equation follows from the undecidability of a system of tiling equations. More precisely, suppose we have non-empty finite subsets of a finitely generated group
for
and
, as well as periodic sets
of
for
, such that it is logically undecidable whether the system of tiling equations
We view systems of the form (2) as belonging to a kind of “language” in which each equation in the system is a “sentence” in the language imposing additional constraints on a tiling. One can now pick and choose various sentences in this language to try to encode various interesting problems. For instance, one can encode the concept of a function taking values in a finite group
as a single tiling equation
This begins to resemble the equations that come up in the domino problem. Here one has a finite set of Wang tiles – unit squares where each of the four sides is colored with a color
(corresponding to the four cardinal directions North, South, East, and West) from some finite set
of colors. The domino problem is then to tile the plane with copies of these tiles in such a way that adjacent sides match. In terms of equations, one is seeking to find functions
obeying the pointwise constraint
Proposition 3 (Swapping property) Consider the solutions to a tiling equationin a one-dimensional group
(with
a finite abelian group,
finite, and
periodic). Suppose there are two solutions
to this equation that agree on the left in the sense that
For any function
, define the “swap”
of
and
to be the set
Then
also solves the equation (9).
One can think of and
as “genes” with “nucleotides”
,
at each position
, and
is a new gene formed by choosing one of the nucleotides from the “parent” genes
,
at each position. The above proposition then says that the solutions to the equation (9) must be closed under “genetic transfer” among any pair of genes that agree on the left. This seems to present an obstruction to trying to encode equation such as
Rachel Greenfeld and I have just uploaded to the arXiv our paper “The structure of translational tilings in “. This paper studies the tilings
of a finite tile
in a standard lattice
, that is to say sets
(which we call tiling sets) such that every element of
lies in exactly one of the translates
of
. We also consider more general tilings of level
for a natural number
(several of our results consider an even more general setting in which
is periodic but allowed to be non-constant).
In many cases the tiling set will be periodic (by which we mean translation invariant with respect to some lattice (a finite index subgroup) of
). For instance one simple example of a tiling is when
is the unit square
and
is the lattice
. However one can modify some tilings to make them less periodic. For instance, keeping
one also has the tiling set
The most well known conjecture in this area is the Periodic Tiling Conjecture:
Conjecture 1 (Periodic tiling conjecture) If a finite tilehas at least one tiling set, then it has a tiling set which is periodic.
This conjecture was stated explicitly by Lagarias and Wang, and also appears implicitly in this text of Grunbaum and Shepard. In one dimension there is a simple pigeonhole principle argument of Newman that shows that all tiling sets are in fact periodic, which certainly implies the periodic tiling conjecture in this case. The
case was settled more recently by Bhattacharya, but the higher dimensional cases
remain open in general.
We are able to obtain a new proof of Bhattacharya’s result that also gives some quantitative bounds on the periodic tiling set, which are polynomial in the diameter of the set if the cardinality of the tile is bounded:
Theorem 2 (Quantitative periodic tiling in) If a finite tile
has at least one tiling set, then it has a tiling set which is
-periodic for some
.
Among other things, this shows that the problem of deciding whether a given subset of of bounded cardinality tiles
or not is in the NP complexity class with respect to the diameter
. (Even the decidability of this problem was not known until the result of Bhattacharya.)
We also have a closely related structural theorem:
Theorem 3 (Quantitative weakly periodic tiling in) Every tiling set of a finite tile
is weakly periodic. In fact, the tiling set is the union of at most
disjoint sets, each of which is periodic in a direction of magnitude
.
We also have a new bound for the periodicity of tilings in :
Theorem 4 (Universal period for tilings in) Let
be finite, and normalized so that
. Then every tiling set of
is
-periodic, where
is the least common multiple of all primes up to
, and
is the least common multiple of the magnitudes
of all
.
We remark that the current best complexity bound of determining whether a subset of tiles
or not is
, due to Biro. It may be that the results in this paper can improve upon this bound, at least for tiles of bounded cardinality.
On the other hand, we discovered a genuine difference between level one tiling and higher level tiling, by locating a counterexample to the higher level analogue of (the qualitative version of) Theorem 3:
Theorem 5 (Counterexample) There exists an eight-element subsetand a level
tiling
such that
is not weakly periodic.
We do not know if there is a corresponding counterexample to the higher level periodic tiling conjecture (that if tiles
at level
, then there is a periodic tiling at the same level
). Note that it is important to keep the level fixed, since one trivially always has a periodic tiling at level
from the identity
.
The methods of Bhattacharya used the language of ergodic theory. Our investigations also originally used ergodic-theoretic and Fourier-analytic techniques, but we ultimately found combinatorial methods to be more effective in this problem (and in particular led to quite strong quantitative bounds). The engine powering all of our results is the following remarkable fact, valid in all dimensions:
Lemma 6 (Dilation lemma) Suppose thatis a tiling of a finite tile
. Then
is also a tiling of the dilated tile
for any
coprime to
, where
is the least common multiple of all the primes up to
.
Versions of this dilation lemma have previously appeared in work of Tijdeman and of Bhattacharya. We sketch a proof here. By the fundamental theorem of arithmetic and iteration it suffices to establish the case where is a prime
. We need to show that
. It suffices to show the claim
, since both sides take values in
. The convolution algebra
(or group algebra) of finitely supported functions from
to
is a commutative algebra of characteristic
, so we have the Frobenius identity
for any
. As a consequence we see that
. The claim now follows by convolving the identity
by
further copies of
.
In our paper we actually establish a more general version of the dilation lemma that can handle tilings of higher level or of a periodic set, and this stronger version is useful to get the best quantitative results, but for simplicity we focus attention just on the above simple special case of the dilation lemma.
By averaging over all in an arithmetic progression, one already gets a useful structural theorem for tilings in any dimension, which appears to be new despite being an easy consequence of Lemma 6:
Corollary 7 (Structure theorem for tilings) Suppose thatis a tiling of a finite tile
, where we normalize
. Then we have a decomposition
where each
is a function that is periodic in the direction
, where
is the least common multiple of all the primes up to
.
Proof: From Lemma 6 we have for any
, where
is the Kronecker delta at
. Now average over
(extracting a weak limit or generalised limit as necessary) to obtain the conclusion.
The identity (1) turns out to impose a lot of constraints on the functions , particularly in one and two dimensions. On one hand, one can work modulo
to eliminate the
and
terms to obtain the equation
For level tilings the analogue of (2) becomes
We are currently studying what this machinery can tell us about tilings in higher dimensions, focusing initially on the three-dimensional case.
Let be a finite additive group. A tiling pair is a pair of non-empty subsets
such that every element of
can be written in exactly one way as a sum of an element
of
and an element
of
, in which case we write
. The sets
are then called tiles, with
being a complementary tile to
and vice versa. For instance, every subgroup
of
is a tile, as one can pick one representative from each coset of
to form the complementary tile. Conversely, any set formed by taking one representative from each coset of
is also a tile.
Tiles can be quite complicated, particularly when the group is “high-dimensional”. We will therefore restrict to the simple case of a cyclic group
, and restrict even further to the special case when the modulus
is square-free. Here, the situation should be much simpler. In particular, we have the following conjecture of Coven and Meyerowitz, which asserts that the previous construction of a tile is, in fact, the only such construction:
Conjecture 1 (Coven-Meyerowitz conjecture, square-free case) Let
be square-free, and let
be a tile of
. Then there exists a subgroup
of
such that
consists of a single representative from each coset of
.
Note that in the square-free case, every subgroup of
has a complementary subgroup
(thus
). In particular,
consists of a single representative from each coset of
, and so the examples of subgroups of
are covered by the above conjecture in the square-free case.
In the non-square free case, the above assertion is not true; for instance, if is a prime, then the multiples of
in
are a tile, but cannot be formed from taking a single representative from all the cosets of a given subgroup. There is a more general conjecture of Coven and Meyerowitz to handle this more general case, although it is more difficult to state:
Conjecture 2 (Coven-Meyerowitz conjecture, general case) Let
be a natural number, and let
be a tile of
. Then there exists a set
of prime powers with
such that the Fourier transform
vanishes whenever
is a non-zero element of
whose order is the product of elements of
that are powers of distinct primes. Equivalently, the generating polynomial
is divisible by the cyclotomic polynomials
whenever
is the product of elements of
that are powers of distinct primes.
It can be shown (with a modest amount of effort) that Conjecture 2 implies Conjecture 1, but we will not do so here, focusing instead exclusively on the square-free case for simplicity.
It was observed by Laba that Conjecture 2 is connected to the following well-known conjecture of Fuglede:
Conjecture 3 (One-dimensional Fuglede conjecture, tiling to spectral direction) Let
be a compact subset of
of positive measure which is a tile (thus
for some set
). Then
(with Lebesgue measure) has a spectrum, that is to say an orthogonal set of plane waves
.
Indeed, it was shown by Laba that Conjecture 2 implies Conjecture 3 in the case when is the finite union of unit intervals. Actually, thanks to the more recent work of Farkas, Matolcsi, and Mora we know that Conjecture 2 in fact implies the universal spectrum conjecture of Lagarias and Wang, which in turn was known to imply Conjecture 3 in full generality. (On the other hand, the conjecture fails in four and higher dimensions; see the papers of Kolountzakis-Matolcsi and of Farkas-Revesz.)
Given the simple statement of Conjecture 1, it is perhaps somewhat surprising that it remains open, even in simple cases such as when is the product of just four primes. One reason for this is that some plausible strengthenings of this conjecture (such as the Tijdeman-Sands conjecture) are known to be false, as we will review below. On the other hand, as we shall see, tiling sets have a lot of combinatorial structure, and in principle one should be able to work out a lot of special cases of the conjecture. Given the combinatorial nature of this problem, it may well be quite suitable for a polymath project in fact, if there is sufficient interest.
Recent Comments