4
$\begingroup$

Given any set of jordan curves that can tile the plane, how to prove that the number of possible tilings using tiles from this set is either in bijection with the real numbers or a (possibly infinite) subset of the integers?

Two tilings are equal if they can be made to coincide by translations or rotations.

  • 0
    I'm not sure what the title supposed to mean, the Continuum Hypothesis says that the continuum has a very specific cardinality, its minimal possible. What does that have to do with the question?2011-10-09
  • 1
    "There is no set whose cardinality is strictly between that of the integers and that of the real numbers." - Georg Cantor. Does it hold for cardinalities of tilings of the plane ?2011-10-09
  • 0
    I know very well what is the continuum hypothesis. I'm just not sure how it relates to this question. Are you asking how to prove that the number of tiling is of cardinality continuum? That would be a clearer statement of the problem. Using CH implies that it can be made into something else, just as the continuum can be blown above $\aleph_1$ and can be collapsed to $\aleph_1$ by forcing.2011-10-09
  • 2
    I know there is sets of polyominoes say, for which the number of tilings are of the same cardinality as the integers, and there are sets of polyominoes which admit uncountable number of tilings. Is there a way to prove that there is no set of tiles that tiles the plane such that the number of tilings are not in bijection with the integers or the reals?2011-10-09
  • 0
    While I am sincerely clueless about polynominoes, I can only say that if one proves that tilings correspond to Borel sets (or even analytic sets) then your question is answered with "Yes", since the continuum hypothesis is true for Borel sets: every uncountable Borel set is of cardinality continuum.2011-10-09
  • 5
    @Asaf: It is not unusual to call results of the form "every blah is either countable or of size continuum" a continuum hypothesis result. This is why one sometimes says that CH holds for Borel sets. I take the question here is in the same spirit.2011-10-09
  • 1
    Can you be more precise about what a tile is, and what it means to tile the plane (e.g., are rotations allowed)? For example, if you allow tiles which are unit squares with edges perturbed by a sine function of varying magnitude, it's not hard to build a family of $\kappa$ many tiles (for any $\kappa \leq 2^{\aleph_0}$) which can tile the plane in exactly $\kappa$ many ways (up to translation/rotation invariance): each tiling will use a single tile type.2011-10-09
  • 0
    Examples. (1) One tile, regular hexagon. The number of tilings of the plane is 1. (We identify tilings under rotations and translations.) (2) One tile, a square. The number of distinct tilings has cardinal of the continuum. (Even after we identify under rotations and translations.) But I agree the OP needs to explain further. In particular: is it allowed for the set of distinct tiles to have power $\aleph_1$ even if that is not the continuum?2011-10-09
  • 0
    @GEdgar: How do you know this is what the question intends? Of course, in general what we would call tiles is very broad, as you suggest. Based on past teaching experience, I am not so sure this is the case here.2011-10-09
  • 0
    [Crossposted to MO](http://mathoverflow.net/questions/77637/): If you decide to move your question to another forum, please say so on both fora!2011-10-10

1 Answers 1

2

Are your tiles square shaped? One can then prove the result by what is essentially a compactness argument. Here is a brief idea:

Tile in order a square of size $1\times1$, then a larger square containing that one, of size $2\times 2$, then a larger one containing it, of size $3\times 3$, etc.

Suppose that your tiling allows us you to tile the plane in a non-periodic fashion. Then, for some $n$, you will have at least two options on how to tile the $n\times n$ square when you get there. Continue "on separate boards" with each of these two ways. Again, by non-periodicity, you should in each case reach a larger $m$ such that the $m\times m$ square can be tiled in at least two ways when you get there (of course, the $m$ in one case may be different from the $m$ in the other case). Continuing "on separate boards" in this fashion, you are building a complete binary tree, each path through which gives you a "different" tiling of the plane. The quotes are here, as we are not yet distinguishing between translations. But there are only countably many translates of a given tiling (if we insist that, say, the borders of our squares coincide with the lines of the form $x=n$ or $y=m$ for $n,m\in{\mathbb Z}$). But then, even after identifying translates, we are left with continuum many different tilings of the plane.

The other possibility is that your tiles does not allow non-periodic tilings. Then, no matter what path you follow, the process above should stop "splitting". But then you are only producing countably many tilings in this fashion.

  • 0
    No, the tiles need not be square shaped.2011-10-09