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.
On
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:
does tile the plane*:
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.
On
I think it can easily be proven that the answer is yes for polyominos which tile the plane in a fully periodic tiling.
One has to be careful 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-Beenker 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 disconnected, the aperiodicity is forced by some rules on the 2nd-rank neighbours of the tile).
But one should not forget that there could be something in between 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 easily 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.
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