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.

Bibliography

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/ $ \:\tilde{\
}$tijdeman/preprints.html), 2002.

Back to the Index


Please send comments and corrections to Thomas Klausner.