Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Telling people that you need an answer doesn't make anyone want to give you an answer. –  Qiaochu Yuan Jan 19 '12 at 0:56
1  
If you are not looking for an answer, why ask the question? –  Henry Jan 19 '12 at 1:42
3  
Apparently, the first known aperiodic tiling using just one shape was found about two years ago, see 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 mathworld.wolfram.com/PolyominoTiling.html –  Gerry Myerson Jan 19 '12 at 3:35
1  
Apparently there exist a set of two polyominos that tile only aperiodically aswell. 2nd last page: univ-orleans.fr/lifo/Members/Nicolas.Ollinger/talks/2011/04/… I couldnt find further reference for this –  gerdur Jan 19 '12 at 12:34
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. –  gerdur Jan 19 '12 at 16:54

3 Answers 3

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.

share|improve this answer
    
You mean, Taylor discovered a tile that can only tile in a non-periodical manner. –  Per Alexandersson Aug 11 at 13:33

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

share|improve this answer
1  
You didnt. A 3-L can tile a 2*3 rectangle. A 2*3 rectangle is a polyomino which tiles the plane. –  gerdur Jan 19 '12 at 0:59
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. –  Henry Jan 19 '12 at 1:20
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. –  Henry Jan 19 '12 at 1:45
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. –  Gerry Myerson Jan 19 '12 at 9:10
3  
@Gerry: Joseph Myers 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..." –  Henry Jan 19 '12 at 12:08

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.

share|improve this answer
4  
In your diagram, if you take four connected octominoes in different orientations, then combined they form a 32-omino which tiles the plane. –  Henry Jan 19 '12 at 7:47
    
So I see. Thanks for pointing out my error! –  Mark Beadles Jan 19 '12 at 16:12
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... –  Pete L. Clark Jan 20 '12 at 2:57
    
No offense taken, and touché! –  Mark Beadles Jan 20 '12 at 2:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.