Andras Biro: Tilings of the integers

If $ A,B\subseteq$ $ {\bf Z}$ and every integer can be written uniquely as $ a+b$ with $ a\in A$ and $ b\in B$, then we write $ A\oplus B=$$ {\bf Z} $, and we say that $ A\oplus B$ is a tiling of $ {\bf Z} $ by $ A$. If $ A\oplus B=$$ {\bf Z} $ and $ A$ is finite, it follows from the pigeon-hole principle that $ B$ is periodic, i.e. $ B+k=B$ with some positive integer $ k$. Let $ A\oplus B=$$ {\bf Z} $. If the diameter of $ A$ is $ n$, and the least period of $ B$ is $ k$, the pigeon-hole principle gives that $ k\le 2^n$. This result was recently improved by I.Z. Ruzsa, who proved in [3] that $ \log k\ll\sqrt {n\log n}$. A slightly weaker result was proved independently by M. Kolountzakis in [2]. In the other direction, the best known result is that $ k=o(n^2)$ 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]:

$\displaystyle \log k\le n^{\frac{1}{3}+\epsilon}.$

However, the problem whether a polynomial upper bound can be given for $ k$ or not, remains open. The new upper bound will be a corollary of a theorem on the divisibility of integer polynomials.


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

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

Robert Tijdeman (appendix by Imre Z. Ruzsa).
Periodicity and almost periodicity.
(preprint available at $ \:\tilde{\
}$tijdeman/preprints.html), 2002.

Back to the Index

Please send comments and corrections to Thomas Klausner.