If
and every integer can be written
uniquely as with and , then we write
, and we say that is a tiling
of by . If
and is
finite, it follows from the pigeonhole principle that is
periodic, i.e. with some positive integer .
Let
. If the diameter of is , and
the least period of is , the pigeonhole principle gives
that . This result was recently improved by I.Z. Ruzsa,
who proved in [3] that
. A slightly
weaker result was proved independently by M. Kolountzakis in [2].
In the other direction, the best known result is that
is not true, see [2]. We see that these upper and lower
estimates are very far from each other.
In the present talk we sketch the proof of the new upper bound
proved in [1]:
However, the problem whether a polynomial upper bound can be given
for or not, remains open.
The new upper bound will be a corollary of a theorem on the
divisibility of integer polynomials.
 1

András Biró.
Divisibility of integer polynomials and tilings of the integers.
(submitted to Acta Arithmetica).
 2

Mihail N. Kolountzakis.
Translational tilings of the integers with long periods.
Electron. J. Combin., 10:Research Paper 22, 9 pp. (electronic),
2003.
 3

Robert Tijdeman (appendix by Imre Z. Ruzsa).
Periodicity and almost periodicity.
(preprint available at http://www.math.leidenuniv.nl/
tijdeman/preprints.html), 2002.
Back to the Index
Please send comments and corrections to Thomas Klausner.