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]:

$$\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