Up: Index of
A finite set A of integers tiles the integers if the integers can be written as a union of disjoint translates of A. In this case, A is called a prototile. Can one decide whether a given set of integers tiles the integers?
Very few results exist. Necessary and sufficient conditions are known for the case that #A is a prime power (D. Newman, J. Number Theory, 1972), but none are known even for the case that #A=6. We will discuss the cases #A=p^n, giving an alternate formulation and an alternate proof of Newman's Theorem, and #A=pq. In the latter case, we will discuss an easily verified sufficient condition which holds for all known (to me) prototiles.
The problem is related to the problem of ``factoring'' finite cylic groups (writing the group as a direct sum of two subsets, not necessarily subgroups), which goes back to Hajos and ultimately to Minkowski. The corresponding problem of tiling the nonnegative integers is easy --- the solution is in your pocket/purse.
Thu January 11, 1996