1
$\begingroup$

How to prove or disprove that if a polyomino tiles the plane, it must also be able to perfectly tile some larger polyomino, which also tiles the plane?

A polyomino is finite set of unit squares connected side to side. Allowed to rotate when tiling. Tiles must be disjoint. Perfect tiling=Exact cover.

  • 2
    Telling people that you need an answer doesn't make anyone want to give you an answer.2012-01-19
  • 1
    If you are not looking for an answer, why ask the question?2012-01-19
  • 3
    Apparently, the first known aperiodic tiling using just one shape was found about two years ago, see http://blog.makezine.com/2010/03/26/worlds-first-aperiodic-tiling-with/ It's not a polyomino. There are sets of three polyominos that tile only aperiodically, see http://mathworld.wolfram.com/PolyominoTiling.html2012-01-19
  • 1
    Apparently there exist a set of two polyominos that tile only aperiodically aswell. 2nd last page: http://www.univ-orleans.fr/lifo/Members/Nicolas.Ollinger/talks/2011/04/greyc.pdf I couldnt find further reference for this2012-01-19
  • 1
    here http://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Goodman3.pdf2012-01-19
  • 0
    @gerdur I am interested what led you down this line of questioning and what kind of research you may have already done. Some of the proofs in this area are notoriously difficult (Hilbert was misled regarding anisohedral tilings) and there are many unproven conjectures.2012-01-19
  • 2
    When I asked it seemed kind of obvious that a counterexample cant exist, and I thought there was a simple proof, but now I am not so sure anymore.2012-01-19
  • 0
    @GerryMyerson I think you can find it here: http://en.wikipedia.org/wiki/Ammann%E2%80%93Beenker_tiling . The Ammann 4 tile consists of two polyominos2012-08-21

3 Answers 3

1

I think it can easily be proven that the answer is yes for polynomios which tile the plane in a fully periodic tiling.

One has to be carefull with the language though. When we speak about aperiodic tiles, we understand a set of tiles which can tile the plane, but no tiling has any period. As it was mentioned in the previous answers/comments, there exists a set of two tiles (the most famous being the Penrose and the Ammann-Benker tilings) which can tile the plane, but tiling have any periods. And only couple years ago, Taylor discovered a one tile which can tile the plane only periodically (but the tile is not connected). These tiles are not polyomino, but there exists small sets of aperiodic polyomino tiles.

The question about the existence of a one aperiodic polyomino tile is, as far as I know, still open. The Taylor aperiodic tiling is hexagonal, and is not really a tiling in the standard sense (as I said the tile is dissconnected, the aperiodicity is forced by some rules one the 2nr rank neighbours of the tile).

But one should not forget that there could be something inbetween fully periodic and fully aperiodic: maybe there exists a polyomino for which some tilings are periodic, but not fully periodic.

A tiling of the plane can have easely a rank 1 periodic lattice (for example tile the plane with squares, cut it along a line which is boundary of the squares, and shift "half" of it up).

I don't know if a polyomino tile for which no fully periodic tiling exists, but partially periodic tiling exists is known.

  • 0
    You mean, Taylor discovered a tile that can only tile in a *non*-periodical manner.2014-08-11
0

If I understand you correctly then there are many counter-examples.

A three-tile L tiles the plane, as does a four tile L, but a three tile L cannot tile a four tile L.

Response to Mark Beadles's comment Anisohedral periodic tilings such as your example do tile larger polyominoes. In your example, you could combine four connected octominoes in different orientations to get something like

enter image description here

  • 1
    You didnt. A 3-L can tile a 2*3 rectangle. A 2*3 rectangle is a polyomino which tiles the plane.2012-01-19
  • 1
    In that case, any polyomino with a periodic tiling of the plane will not do; it must only have an aperiodic tiling of the plane. You will not find one.2012-01-19
  • 0
    Im looking for a proof there isnt one2012-01-19
  • 1
    You have tagged this as "homework" which suggests that somebody else knows the answer and that there is a relatively easy proof one way or another. I have my doubts.2012-01-19
  • 0
    And now you change the tags having already changed the question2012-01-19
  • 0
    @henry there are no aperiodic polyominoes, but there are anisohedral ones which I believe suffice. See my answer above.2012-01-19
  • 1
    @Mark: See my diagram2012-01-19
  • 0
    @Mark, you and Henry seem to be quite confident that there is no polyomino that tiles only aperiodically, but no citation has been presented. Is the non-existence documented somewhere?2012-01-19
  • 1
    @Gerry. Given that the only known aperiodic single tile is a prototile not a tile (http://arxiv.org/abs/1003.4279), I am confident gerdur will not find an aperiodic polyomino.2012-01-19
  • 3
    @Henry, so, the answer to my question is, no, the non-existence of an aperiodic polyomino is not documented anywhere. Too bad for gerdur, who is looking for such documentation.2012-01-19
  • 3
    @Gerry: [Joseph Myers](http://www.polyomino.org.uk/mathematics/polyform-tiling/) says "Subject to limitations of time and space, my programs can in principle resolve the tiling status of any polyomino, polyhex or polyiamond that either does not tile, or tiles the plane periodically. It is a notable unsolved problem whether there exists a single polygon that tiles the plane only non-periodically (such a hypothetical shape being known as aperiodic; my programs would in principle run forever on such a shape). Within the ranges covered by these tables, there are no aperiodic polyominoes..."2012-01-19
  • 0
    Henry has shot down Mark's answer, and Mark thanks Henry for pointing out the error. Yet, two people have voted Henry's contribution down, without giving any reason. What's going on here?2012-01-19
  • 0
    @Gerry: The initial version of the question was "How to prove that if a polyomino tiles the plane, it must perfectly tile a larger polyomino, which also tiles the plane?" and I misunderstood gerbur's intention. By the time that was sorted out and after gerbur had made and deleted some unwise comments, I was using my answer for a diagram on the anisohedral issue and you entered the debate; it seems a little unhelpful to delete the answer now. I don't care about the votes.2012-01-19
  • 0
    Likewise. I would normally delete my answer, but since @Henry took the time to correct it within his own answer, I won't. It would make it look like Henry was talking to himself :)2012-01-20
0

EDIT: This answer is incorrect, but it sparked a discussion so I am leaving in place for now.


You don't make it clear whether you mean for any polyomino, or given a particular polyomino.

If you mean "for any polyomino", then a counterexample will suffice.

Any of the anisohedral polyominoes, for example the unique 2-anisohedral octomino:

the unique anisohedral 8-omino

does tile the plane*:

enter image description here

but by inspection obviously does not ever tile any large polyomino.

This is because the tiles don't "line up" on translation, that is they have a symmetry group which is not transitive on the tiles. The repeat of the tiles falls instead into a orbit (in this case of order 2). There are anisohedral tilings for certain polyominoes of any order > 8.

If you mean "given a particular polyomino", I don't know of such a proof.


*Tiling from Wolfram Mathworld.

  • 4
    In your diagram, if you take four connected octominoes in different orientations, then combined they form a 32-omino which tiles the plane.2012-01-19
  • 0
    So I see. Thanks for pointing out my error!2012-01-19
  • 1
    I don't mean to rub things in, but when I read the phrase "by inspection obviously" I first thought "Gosh, this is really not obvious to me; maybe I'm no good at this math stuff after all" and then second thought "Wait, remember that whenever an author says 'obviously' or 'by inspection' he is pointing out to you a likely location for a mistake." I trust the moral is clear...2012-01-20
  • 0
    No offense taken, and touché!2012-01-20