# Simultaneous tiling

Mihail N. Kolountzakis  Department of Mathematics and Applied Mathematics,
University of Crete, Voutes Campus, 70013 Heraklion, Crete, Greece.
<EMAIL_ADDRESS>
###### Abstract.

We discuss problems of simultaneous tiling. This means that we have an object
(set, function) which tiles space with two or more different sets of
translations. The most famous problem of this type is the Steinhaus problem
which asks for a set simultaneously tiling the plane with all rotates of the
integer lattice as translation sets.

###### Key words and phrases:

Lattices, tiling, common fundamental domain, Steinhaus problem

###### 2020 Mathematics Subject Classification:

primary 52C22; secondary 20K99

Supported by the Hellenic Foundation for Research and Innovation, Project
HFRI-FM17-1733 and by grant No 4725 of the University of Crete.

Dedicated to the memory of Dimitris Gatzouras

§1. Tiling by translation. For the purposes of this paper 111This is a survey
paper which contains no new results. Many of the results and questions in this
paper are from [21] on parts of which this paper is heavily based. tiling is
by translation only [16]. We have an object $T$ (the tile) which may be a set
or a function on some abelian group $G$ (usually the Euclidean space but it
may be ${\mathbb{Z}}^{d}$ or a finite group)

Figure 1. An $L$-shaped tile. The red point is the origin

which we are translating around by a set of translations $\Lambda$, in such a
way that everything in the group $G$ is covered exactly once, with the
possible exception of a set of zero Haar measure, to account for such
irrelevant things such as boundaries overlapping, which we generally do not
care about.

Figure 2. A translational tiling by the $L$-shaped region. The red points are
the translation set.

One convenient way to define tiling by a function $f$ (which can be an
indicator function, if we want tiling by a set) when translated at the
locations $\Lambda$ is to demand that

(1) $\sum_{\lambda\in\Lambda}f(x-\lambda)=\text{const.},$

for almost all $x\in G$. To avoid most issues of convergence it makes sense to
ask that $f\geq 0$, though some interesting problems do arise with signed $f$
[20].

§2. Tiling in Fourier space. It is easy to see that (1) may be rewritten as a
convolution

(2) $f*\delta_{\Lambda}=\text{const.}$

where $\delta_{\Lambda}=\sum_{\lambda\in\Lambda}\delta_{\lambda}$ is the
measure that encodes the locations $\Lambda$ by placing a unit mass on each of
them.

Figure 3. The collection $\delta_{\Lambda}$ of point masses that encodes the
set $\Lambda$

Taking the Fourier Transform of this we obtain

(3) $\widehat{f}\widehat{\delta_{\Lambda}}=C\delta_{0}.$

This implies that the tempered distribution $\widehat{\delta_{\Lambda}}$ is
supported on the zeros of $\widehat{f}$ plus the origin

(4) ${\rm
supp\,}\widehat{\delta_{\Lambda}}\subseteq{\left\\{{\widehat{f}=0}\right\\}}\cup{\left\\{{0}\right\\}}.$

Let us now restrict ourselves to the case of $G={\mathbb{R}}^{d}$ and
$\Lambda\subseteq{\mathbb{R}}^{d}$ being a lattice
$\Lambda=A{\mathbb{Z}}^{d}$, where $A$ is a non-singular $d\times d$ matrix.
The Poisson summation formula reads

$\widehat{\delta_{\Lambda}}=\frac{1}{{\left|{\det
A}\right|}}\delta_{\Lambda^{*}}$

in this case, where $\Lambda^{*}=A^{-\top}{\mathbb{Z}}^{d}$ is the dual
lattice of $\Lambda$, so the tiling of $f$ with $\Lambda$ becomes equivalent
to

$\widehat{f}(\lambda^{*})=0\ \ \text{ for all
}\lambda^{*}\in\Lambda^{*}\setminus{\left\\{{0}\right\\}}.$

size(12cm);

picture pic, picd; real[][] a=2, 1.2, 0, 1; real[][] b=transpose(inverse(a));

int N=5;

for(int i=-N; i<=N; ++i) for(int j=-N; j<=N; ++j) real[] x=i, j; real[] y=a*x;
pair p=(y[0], y[1]); dot(pic, p, red); y = b*x; pair p=(y[0], y[1]); dot(picd,
p, blue);

dot(pic, "0", (0, 0), black); dot(picd, "0", (0, 0), black);

clip(pic, (-N, -N)–(N, -N)–(N, N)–(-N, N)–cycle); label(pic, "$\Lambda$:",
(-1.2*N, 0)); clip(picd, (-N, -N)–(N, -N)–(N, N)–(-N, N)–cycle); label(picd,
"$\Lambda^{*}$:", (-0.7*N, 0)); add(pic); add(shift((2.3*N, 0))*picd);

Figure 4. A lattice $\Lambda$ and its dual $\Lambda^{*}$

§3. The Steinhaus tiling problem. In the Steinhaus tiling problem we are
seeking a tile that can tile simultaneously with many different sets of
translations. The most important case is: can we find a subset of the plane
which can tile (by translations) with all rotates of the integer lattice
${\mathbb{Z}}^{2}$? In some sense we are asking for a set in the plane that
can behave simultaneously like all these rotated squares (Fig. 5).

Figure 5. The rotated squares are fundamental domains of all rotates of
${\mathbb{Z}}^{2}$

There are two major variations of the Steinhaus problem: the measurable and
the set-theoretic case. In the measurable case we demand our tile to be a
Lebesgue measurable subset of ${\mathbb{R}}^{d}$ and we are, at the same time,
relaxing our requirements and are allowing a subset of measure 0 of space not
to be covered exactly once by the translates of the tile. In the set-theoretic
case we allow the tile to by any subset and we typically ask that every point
is covered exactly once, allowing no exceptions.

Komjáth [22] answered the Steinhaus question in the affirmative in
${\mathbb{R}}^{2}$ when tiling by all rotates of the set
$B={\mathbb{Z}}\times{\left\\{{0}\right\\}}$ showing that there are such
Steinhaus sets (but such a set $A$ cannot be measurable as was shown recently
in [18]). Sierpinski [26] showed that a bounded set $A$ which is either closed
or open cannot have the lattice Steinhaus property (that is, intersect all
rigid motions of ${\mathbb{Z}}^{2}$ at exactly one point – another way to say
that $A$ tiles precisely with all rotates of ${\mathbb{Z}}^{2}$). Croft [5]
and Beck [1] showed that no bounded and measurable set $A$ can have the
lattice Steinhaus property (but see also [23]). Kolountzakis [14, 13] and
Kolountzakis and Wolff [19] proved that any measurable set in the plane that
has the measurable Steinhaus property must necessarily have very slow decay at
infinity (any such set must have measure 1). In [19] it was also shown that
there can be no measurable Steinhaus sets in dimension $d\geq 3$ (tiling with
all rotates $\rho{\mathbb{Z}}^{d}$, where $\rho$ is in the full orthogonal
group) a fact that was also shown later by Kolountzakis and Papadimitrakis
[17] by a very different method. See also [3, 24, 4, 27]. Kolountzakis [15]
looks at the case where we are only asking for our set to tile with finitely
many lattices, not all rotates as in the original problem, which we are also
doing in this paper. In a major result Jackson and Mauldin [11, 10] proved the
existence of Steinhaus sets in the plane which tile with all rotates of
${\mathbb{Z}}^{2}$ (not necessarily measurable). Their method does not extend
to higher dimension $d\geq 3$. See also [25, 12]. It was also shown in [18]
that a set $A$ which tiles with all rotates of a finite set $B$ cannot be
measurable.

§4. The Steinhaus problem in Fourier space. Most of the results on the
measurable Steinhaus problem start by observing that if
$E\subseteq{\mathbb{R}}^{2}$ is Steinhaus then every rotate $R_{\theta}E$ of
$E$ tiles with ${\mathbb{Z}}^{2}$, which means that for every angle $\theta$
the Fourier Transform $\widehat{{\mathds{1}}_{R_{\theta}E}}$ vanishes on
${\mathbb{Z}}^{2}\setminus{\left\\{{0}\right\\}}$ since ${\mathbb{Z}}^{2}$ is
the dual lattice of itself. This implies that $\widehat{{\mathds{1}}_{E}}$
vanishes on all rotates of ${\mathbb{Z}}^{2}$. In other words
$\widehat{{\mathds{1}}_{E}}$ vanishes on all circles centered at the origin
that go through at least one integer lattice point.

\begin{picture}(3902.0,3901.0)(2421.0,-4840.0)\end{picture}

Figure 6. The Fourier Transform of any Steinhaus set must vanish on all
circles centered at the origin that go through at least one integer lattice
point

The number of these circles is large. There are a little less than $O(R^{2})$
such circles of radius $\leq R$. Many zeros of a function sometimes imply
decay at infinity, and, by the usual uncertaintly principle (both $f$ and
$\widehat{f}$ cannot decay fast at infinity), since
$\widehat{{\mathds{1}}_{E}}$ is small at infinity it follows that
${\mathds{1}}_{E}$ is large (e.g., $E$ cannot be bounded).

§5. Allowing functions instead of sets in the Steinhaus problem. Let us now
relax our requirements and allow our tile to be a function instead of a set
(instead of indicator function, in other words). Satisfying the requirements
of the Steinhaus tiling problem with a function is generally much easier than
with a set. The problem becomes interesting only if one asks for further
properties that this function should have. Therefore we try to find a function
with small support, or to prove that the support of such a function must
necessarily be large. Asking for $f$ to have a small support goes against $f$
having the ability to tile space, especially with many different sets of
translations $T$. The reason is that for $f$ to tile by translations with $T$
its Fourier transform must contain a rich set of zeros [16]. This set of zeros
must be able to support the Fourier transform of the measure
$\delta_{T}=\sum_{t\in T}\delta_{t}$ (which encodes the set of translations).
By the well known uncertainty principle in harmonic analysis a rich set of
zeros for $\widehat{f}$ usually requires (in various different senses) a large
support for $f$ [9].

It is very easy to take $\widehat{f}$ to vanish on the required circles, but
one must do it in a way that ensures that $f$ is itself small in some sense,
such as the diameter of its support or the volume of its support.

§6. Small diameter of the support: lower bounds. The first thing that comes to
mind is to take $f$ to be a convolution. It takes a moment to verify that if
$f$ tiles with a set of translates $T$ then so does $g*f$ for any $g\in
L^{1}({\mathbb{R}}^{d})$. One can either verify this by checking the
definition of tiling for $g*f$ or observe that tiling is a condition that can
be checked on the Fourier side [16] and
$\widehat{g*f}=\widehat{g}\cdot\widehat{f}$ has an even richer set of zeros
that $\widehat{f}$.

So, since $\widehat{f}$ has to vanish on the dual lattices
$\Lambda_{i}^{*}\setminus{\left\\{{0}\right\\}}$ we can take

(5) $f={\mathds{1}}_{D_{1}}*{\mathds{1}}_{D_{2}}*\cdots*{\mathds{1}}_{D_{N}},$

where $D_{i}$ is a fundamental parallelepiped of $\Lambda_{i}$. Since
$D_{i}+\Lambda_{i}$ is a tiling it follows that
$\widehat{{\mathds{1}}_{D_{i}}}$ vanishes on
$\Lambda_{i}^{*}\setminus{\left\\{{0}\right\\}}$ and that $f$ vanishes on
their union and hence tiles with all $\Lambda_{i}$. This can be slightly
generalized by taking, instead if the indicator functions
${\mathds{1}}_{D_{i}}$ any function $f_{i}$ that tiles with $\Lambda_{i}$

(6) $f=f_{1}*f_{2}*\cdots f_{N}.$

Figure 7. The fundamental doamins of several lattices. A constant fraction of
them project to a set of large diameter onto one of the coordinate axes.

The following observation (see detailed proof in [21]) was already made in
[19] in the case $f_{i}={\mathds{1}}_{D_{i}}$.

######  Theorem 1.

If $\Lambda_{1},\ldots,\Lambda_{N}$ are lattices in ${\mathbb{R}}^{d}$ of
volume $c_{1}\leq{\rm vol\,}\Lambda_{i}$ and $f=f_{1}*f_{2}*\cdots*f_{N}$ then

(7) ${\rm diam\,}{\rm supp\,}f\geq C_{d}N.$

The reason is that a constant fraction of the supports of the $f_{i}$ project
onto a constant fraction of their diameter onto some line, say one of the
axes. This implies (obvious if the $f_{i}$ are nonnegative; one needs the
Titchmarsh convolution theorem in the general case) that so does the support
of the convolution $f=f_{1}*\cdots*f_{N}$ (shown in Fig. 7 for the $f_{i}$
being the indicator functions of fundamental parallelepipeds of the lattices).

If the lattices $\Lambda_{i}$ satisfy some “roundness” assumption, e.g. if
each $\Lambda_{i}$ is assumed to have a fundamental domain of diameter bounded
independent of $N$ (as in the important case when all the lattices are rotates
of ${\mathbb{Z}}^{d}$), then the convolution tile (5) has diameter which is
also at most $C\cdot N$.

On the other hand we have the following rather general lower bound for the
diameter of the support [19] assuming only a certain genericity assumption (8)
on the $\Lambda_{i}$.

######  Theorem 2.

If $\Lambda_{1},\ldots,\Lambda_{N}\subseteq{\mathbb{R}}^{d}$, $d\geq 1$, are
lattices of volume equal to 1 such that

(8) $\Lambda_{i}\cap\Lambda_{j}={\left\\{{0}\right\\}}\ \ \text{ for all
$i\neq j$,}$

then if $f$ tiles with all these lattices we have

(9) ${\rm diam\,}{\rm supp\,}f\geq C_{d}N^{1/d}.$

The main question is therefore:

######  Question 1.

Can the gap between the lower bound (9) and the linear upper bound $O(N)$
achievable by the convolution tile (5) (in the case of “round” lattices,
having fundamental domains bounded in diameter by a constant) be bridged? Are
there examples of lattices $\Lambda_{i}$, $i=1,2,\ldots,N$, satisfying (8) and
a non-zero function $f\in L^{1}({\mathbb{R}}^{d})$ that tiles with all
$\Lambda_{i}$ and such that ${\rm diam\,}{\rm supp\,}f=o(N)?$ In other words,
do there exist collections of lattices for which a common tile $f$ can be
found which is diameter-wise more efficient than the convolution construction
(5)?

§7. A case of large diameter. We observe now [21] that for some collections of
lattices the linear upper bound cannot be improved. The lattices given are
both “round” (have a fundamental domain bounded independent of $N$) and
satisfy the genericity assumption (8). There are however collinearities so, in
some sense, this is not a generic situtation.

######  Theorem 3.

For $d\geq 1$ and for each $N$ there are lattices
$\Lambda_{1},\ldots,\Lambda_{N}\subseteq{\mathbb{R}}^{d}$, of volume 1, such
that if $f\in L^{1}({\mathbb{R}}^{d})$, $\int f\neq 0$, tiles with all of them
then

${\rm diam\,}{\rm supp\,}f\geq C_{d}N.$

###### Proof.

We give the proof in the case $d=2$. It works with obvious changes in all
dimensions $d>2$ and it is even easier in dimension $d=1$.

Figure 8. The fundamental rectangles of the lattices of Theorem 3 which have
only very long common tiles.

Take $\Lambda_{i}^{*}$ to be generated by the two vectors

$u_{i}=(0,a_{i}),v_{i}=(1/a_{i},0),$

where the numbers $a_{1},\ldots,a_{N}$ are linearly independent over
${\mathbb{Q}}$ and

$0.9<a_{i}<1.$

If $f$ tiles with all $\Lambda_{i}$ then $\widehat{f}$ vanishes on all points
of the form

$(0,k\cdot a_{i}),\ \ i=1,2,\ldots,N,\ \
k\in{\mathbb{Z}}\setminus{\left\\{{0}\right\\}}.$

Since all these points are different it follows that the density of zeros on
the $y$-axis is $\geq C\cdot N$. This implies that

${\rm diam\,}{\rm supp\,}\pi_{2}(f)\geq C\cdot N$

(say, by Jensen’s formula) where $\pi_{2}(f)$ is the one-variable function

$\pi_{2}(f)(y)=\int_{{\mathbb{R}}}f(x,y)\,dx.$

(This is not an identically zero function by our assumption on the integral of
$f$.) This in turn implies

${\rm diam\,}{\rm supp\,}f\geq C\cdot N.$

∎

§8. Small volume of the support. Another measure of the size of the support is
its volume. Can we construct a common tile $f$ for the lattices $\Lambda_{i}$
such that ${\left|{{\rm supp\,}f}\right|}$ is small?

In the case of $f$ given by (5) it is clear that

${\rm supp\,}{f}=D_{1}+D_{2}+\ldots+D_{N}.$

To keep things concrete let us assume that all ${\left|{D_{i}}\right|}=1$ in
(5) (unimodular lattices). Then the Brunn-Minkowski inequality [7] says that

${\left|{{\rm
supp\,}f}\right|}={\left|{D_{1}+\cdots+D_{N}}\right|}\geq\left({\left|{D_{1}}\right|}^{1/d}+\cdots+{\left|{D_{N}}\right|}^{1/d}\right)^{d}\geq
N^{d}.$

This lower bound

${\left|{{\rm supp\,}f}\right|}\geq CN^{d}$

clearly holds also for functions of the form

(10) $f=f_{1}*f_{2}*\cdots*f_{N},\ \ \ f_{i}\geq 0,$

where for all $i=1,2,\ldots,N$ we assume that the nonnegative function $f$
tiles with $\Lambda_{i}$.

We have proved [21]:

######  Theorem 4.

For any collection of lattices $\Lambda_{1},\ldots,\Lambda_{N}$ in
${\mathbb{R}}^{d}$ of volume at least 1 and any common tile $f$ for them of
the form

$f=f_{1}*f_{2}*\cdots*f_{N},\ \ \ f_{i}\geq 0,$

with $f_{i}$ tiling with $\Lambda_{i}$, we have

${\left|{{\rm supp\,}f}\right|}\geq N^{d}.$

But when the functions $f$ are signed (or complex) we only have

${\rm supp\,}{f}\subseteq{\rm supp\,}{f_{1}}+\cdots{\rm supp\,}{f_{N}},$

not necessarily equality, which brings us to the next question.

######  Question 2.

If $f$ is given by (10), is it true that (11) ${\left|{{\rm
supp\,}f}\right|}\geq CN^{d}?$

If one requires that the lattices
$\Lambda_{1},\Lambda_{2},...,\Lambda_{N}\subset\mathbb{R}^{d}$ have the same
volume, say $1$, and the sum
$\Lambda_{1}^{\ast}+\Lambda_{2}^{\ast}+...+\Lambda_{N}^{\ast}$ of their dual
lattices is direct, then, by [15, Theorem 2], they possess a measurable common
almost fundamental domain $E$ (generally unbounded).See Fig. 9.

Move by $\lambda_{1}$Move by $\lambda_{2}$

Figure 9. How to rearrange the fundamental domains of two lattices so that
they agree almost everywhere [15, Theorem 2]. One breaks up the two domains
into smaller and smaller parts, then moves each by a vector in its own lattice
so that they agree almost completely.

In this case, $|E|={\rm vol\,}(\Lambda_{i})=1$. So then one can take
$f={\mathds{1}}_{E}$, which tiles with all $\Lambda_{i}$, $i=1,2,...,N$, with
$|{\rm supp\,}f|=|E|=1$.

Motivated by the previous observation, but now dropping the equal volume
assumption, we ask the following:

######  Question 3.

Consider the lattices $\Lambda_{1},\Lambda_{2},...,\Lambda_{N}$, with
$\frac{1}{2}\leq{\rm vol\,}(\Lambda_{i})\leq 2$. Is there a function $f$ that
tiles with all $\Lambda_{i}$, such that $|{\rm supp\,}f|=o(N^{d})?$

######  Question 4.

In the case when $\Lambda_{1},\ldots,\Lambda_{N}$ all have volume 1 and
satisfy some sort of genericity condition, such as
$\Lambda_{1}^{*}+\cdots\Lambda_{N}^{*}$ being a direct sum, as in [15, Theorem
2], can the common fundamental domain of the $\Lambda_{i}$ be bounded? In the
construction of [15, Theorem 2] the unboundedness is unavoidable, but is it in
the nature of things?

§9. Small length of the support in $d=1$. In the simplest case in dimension
$d=1$, and for two lattices only, a basic question is to ask if the
convolution (10) is best in terms of the length of the support. Here we can
give [21] a simple lower bound assuming a nonnegative function.

######  Theorem 5.

Suppose the nonnegative $f:{\mathbb{R}}\to{\mathbb{R}}^{\geq 0}$ is measurable
and tiles with both $\Lambda_{1}={\mathbb{Z}}$ and with
$\Lambda_{2}=\alpha{\mathbb{Z}}$, where $\alpha\in(0,1)$:

(12) $\sum_{n\in{\mathbb{Z}}}f(x-n)=1,\ \ \
\sum_{n\in{\mathbb{Z}}}f(x-n\alpha)=\frac{1}{\alpha},\ \ \text{for almost
every $x\in{\mathbb{R}}$}.$

Then

(13) ${\left|{{\rm
supp\,}f}\right|}\geq{\left\lceil{\frac{1}{\alpha}}\right\rceil}\alpha\geq
2\alpha.$

######  Remark 1.

If we assume the first equation in (12) then the constant in the second
equation is forced to be $1/\alpha$. This is because $\int f=1$ (from the
first equation), so repeating $f$ at a set of translates of density $1/\alpha$
will give a constant (assuming it tiles) at that level.

######  Remark 2.

Notice that if $\alpha$ is just a little less than 1 then (13) gives a lower
bound of $2\alpha$, which shows that the convolution
${\mathds{1}}_{[0,1]}*{\mathds{1}}_{[0,\alpha]}$ is almost optimal in this
case, having support of size $1+\alpha$.

But if, on the other hand, $\alpha$ is just over $1/2$ then the lower bound is
just over 1 but the convolution upper bound is just over $3/2$, a considerable
gap.

###### Proof.

From the first equation in (12) it follows that $f(x)\leq 1$ for almost every
$x$. For the second equation to be true it therefore follows that for almost
every $x\in{\mathbb{R}}$ there are at least
${\left\lceil{1/\alpha}\right\rceil}$ different values of $n\in{\mathbb{Z}}$
such that $f(x-n\alpha)>0$. Using this for almost all $x\in[0,\alpha)$ (which
ensures that for different $x$ the locations $x-n\alpha$ are also different)
gives (13).

∎

######  Question 5.

What is the least possible length of the support of $f$ for a nonnegative $f$
that tiles with both ${\mathbb{Z}}$ and $\alpha{\mathbb{Z}}$?

§10. Very small diameter of the support with relations among the lattices. If
we have $N$ lattices

$\Lambda_{1},\ldots,\Lambda_{N}\subseteq{\mathbb{R}}^{d}$

we can find a function that tiles with them all, namely the function $f$ in
(5). If our lattices are assumed to each have a fundamental domain bounded by
$\sim 1$ then ${\rm diam\,}{\rm supp\,}f=O(N)$, and this cannot be improved
for functions $f$ arising from (5). We show here [21] that we can choose the
lattices $\Lambda_{j}$ so that a common tiling function exists which is much
more tight than that, tighter even than what Theorem 2 imposes. Of course our
lattices will not satisfy the genericity condition (8) of Theorem 2, but will
satisfy a lot of relations (their intersection will be a large lattice, in
terms of density).

Fix a large prime $p$ and consider the group ${\mathbb{Z}}_{p}^{d}$. Any
nonzero element $g$ of this group generates a cyclic subgroup of order $p$. It
follows that ${\mathbb{Z}}_{p}^{d}$ has

$\frac{p^{d}-1}{p-1}\sim p^{d-1}=:N$

different cyclic subgroups. For each such subgroup $G$, which we now view as a
subset of ${\left\\{{0,1,\ldots,p-1}\right\\}}^{d}$, consider the lattice

$\Lambda_{G}=(p{\mathbb{Z}})^{d}+G.$

Figure 10. How we construct the $(p{\mathbb{Z}})^{d}$-periodic set
$\Lambda_{G}$ from the subgroup $G$ of ${\mathbb{Z}}_{p}^{d}$

This contains the lattice $\Lambda=(p{\mathbb{Z}})^{d}$ and has volume

${\rm vol\,}\Lambda_{G}=\frac{{\rm
vol\,}(p{\mathbb{Z}})^{d}}{{\left|{G}\right|}}=p^{d-1}=N.$

The function $f={\mathds{1}}_{[0,p)^{d}}$, $[0,p)^{d}$ being a fundamental
domain of $\Lambda$, tiles with $\Lambda$ and, therefore, with any larger
group, so $f$ is a common tile of all $\Lambda_{G}$.

In order to make the volume of the $\Lambda_{G}$ equal to 1 we shrink
everything by $N^{1/d}$:

$\Lambda_{G}^{\prime}=N^{-1/d}\Lambda_{G},\ \ \ f^{\prime}(x)=f(N^{1/d}x).$

So we have $\sim N$ lattices $\Lambda^{\prime}_{G}$ of volume 1 and a common
tile $f^{\prime}$ for them with

${\rm diam\,}{\rm supp\,}f^{\prime}={\rm diam\,}{\rm supp\,}f\cdot
N^{-1/d}=\sqrt{d}\,pN^{-1/d}=\sqrt{d}\,N^{\frac{1}{d-1}-\frac{1}{d}}=\sqrt{d}\,N^{\frac{1}{d(d-1)}}.$

We have proved:

######  Theorem 6.

In dimension $d\geq 2$ and for arbitrarily large $N$ we can find $N$ lattices
of volume $1$ and a common tile $f$ for them with

${\rm diam\,}{\rm supp\,}f=O_{d}\left(N^{\frac{1}{d(d-1)}}\right),$

and, consequently, with

(14) ${\left|{{\rm supp\,}f}\right|}=O_{d}\left(N^{\frac{1}{d-1}}\right).$

######  Question 6.

Derive a lower bound for ${\rm diam\,}{\rm supp\,}f$, for $f$ tiling with
$\Lambda_{1},\ldots,\Lambda_{N}\subseteq{\mathbb{R}}^{d}$ and with $f\geq 0$
(or just $\int f>0$) under no algebraic conditions for the lattices
$\Lambda_{j}$, assuming only that ${\rm vol\,}\Lambda_{j}\sim 1$.

######  Question 7.

In Theorem 6 we have used the cyclic subgroups of ${\mathbb{Z}}_{p}^{d}$
because they are easier to count. However the same argument could be carried
out using a larger class of subgroups, perhaps all of them. What is the
estimate that can be achieved this way to replace (14)?

§11. Almost matching upper and lower bounds for the diameter, $d=1$. The
construction that we used to prove Theorem 6 gives nothing in dimension $d=1$.
Yet, we can prove [21] that, if we allow relations among the lattices, we can
achieve ${\rm diam\,}{\rm supp\,}f=o(N)$ in dimension 1 as well.

Let us start by defining

$\lambda_{j}=\frac{1}{N+j},\ \ \ \Lambda_{j}=\lambda_{j}{\mathbb{Z}},\ \ \
(j=1,2,\ldots,N).$

We will first construct a function $f$ which tiles with all the $\Lambda_{j}$,
$j=1,2,\ldots,N$, such that

${\rm diam\,}{\rm supp\,}f=o(1).$

The Fourier transform of such an $f$ must vanish on the dual lattices

$\Lambda_{j}^{*}=\lambda_{j}^{-1}{\mathbb{Z}}=(N+j){\mathbb{Z}},\ \ \
(j=1,2,\ldots,N)$

except at 0. Write

$U=\bigcup_{j=1}^{N}(N+j){\mathbb{Z}}\ \setminus{\left\\{{0}\right\\}}.$

By a result of Erdős [6] $U$, the set of integers which are divisible by one
of the integers in ${\left\\{{N+1,N+2,\ldots,2N}\right\\}}$, has density
tending to 0 with $N$. Tenenbaum [28] has given the estimate that this density
is at most

(15) $\frac{1}{\log^{\delta-o(1)}N},$

where $\delta=0.086071\cdots$ is an explicit constant.

It is an important result of Beurling [2] that if $\Lambda$ is a uniformly
discrete set of real numbers of upper density $\rho$ then for any $\epsilon>0$
we can find a continuous function $f$, not identically zero, supported by the
interval $[0,\rho+\epsilon]$ such that $\widehat{f}(\lambda)=0$ for all
$\lambda\in\Lambda$. We can even ask that $\widehat{f}(0)=1$ if
$0\notin\Lambda$. By Tenenbaum’s estimate (15) we can take
$\rho=\log^{-\delta+o(1)}N$ and the set $U$, being a set of integers and thus
uniformly discrete, satisfies the assumptions of Beurling’s theorem, so there
is a function $f$ supported in the interval $[0,\log^{-\delta+o(1)}N]$, with
integral 1, such that $\widehat{f}=0$ on $U$. It follows that $f$ tiles with
all $\Lambda_{j}$.

We now scale by a factor of $N$

$f^{\prime}(x)=f(x/N),\ \ \ \Lambda_{j}^{\prime}=N\Lambda_{j},\ \ \ {\rm
diam\,}{\rm supp\,}f^{\prime}=O(N\log^{-\delta+o(1)}N)$

and obtain the first half of the following theorem.

######  Theorem 7.

We can find $N$ lattices $\Lambda_{j}\subseteq{\mathbb{R}}$ of with ${\rm
vol\,}\Lambda_{j}\sim 1$ and a function $f$ with $\int f>0$ and supported in
an interval of length

$\frac{N}{\log^{\delta-o(1)}N)}$

which tiles with all $\Lambda_{j}$.

Furthermore, for any $\epsilon>0$ any such function $f$ must have

${\rm diam\,}{\rm supp\,}f\gtrsim_{\epsilon}N^{1-\epsilon}.$

Arguing similarly we can also prove the lower bound for ${\rm diam\,}{\rm
supp\,}f$ in Theorem 7. If we assume that $f$ tiles with all
$\Lambda_{j}=\lambda_{j}{\mathbb{Z}}$, with, say, $1\leq\lambda_{j}\leq 2$,
$j=1,2,\ldots,N$, then $\widehat{f}$ vanishes on

$\bigcup_{j=1}^{N}\lambda_{j}^{-1}{\mathbb{Z}}\ \
\setminus{\left\\{{0}\right\\}}.$

If this set is large then Jensen’s formula implies that ${\rm diam\,}{\rm
supp\,}f$ is also large. It was proved in [8, Theorem 1.1, special case
$\ell=n$] that, for any $\epsilon>0$, the above union of arithmetic
progressions contains at least $c_{\epsilon}N^{2-\epsilon}$ points in
$[0,2N]$. By Jensen’s formula then we have ${\rm diam\,}{\rm
supp\,}f\gtrsim_{\epsilon}N^{1-\epsilon}$ and this completes the proof of
Theorem 7.

######  Question 8.

Can we ensure $f\geq 0$ in the first half of Theorem 7?

## References

  * [1] J. Beck, _On a lattice point problem of H. Steinhaus_ , Studia Sci. Math. Hung 24 (1989), 263–268.
  * [2] A Beurling, _Collected Works of Arne Beurling (2 vol.), edited by L. Carleson et al_ , 1989.
  * [3] W. K. Chan and R. Mauldin, _Steinhaus tiling problem and integral quadratic forms_ , Proceedings of the American Mathematical Society 135 (2007), no. 2, 337–342.
  * [4] M. Ciucu, _A remark on sets having the Steinhaus property_ , Combinatorica 16 (1996), no. 3, 321–324.
  * [5] H. T. Croft, _Three lattice-point problems of Steinhaus_ , The Quarterly Journal of Mathematics 33 (1982), no. 1, 71–83.
  * [6] Paul Erdos, _Note on sequences of integers no one of which is divisible by any other_ , J. London Math. Soc 10 (1935), no. 1, 126–128.
  * [7] R. Gardner, _The Brunn-Minkowski inequality_ , Bulletin of the American Mathematical Society 39 (2002), no. 3, 355–405.
  * [8] S. Gilboa and R. Pinchasi, _On the union of arithmetic progressions_ , SIAM Journal on Discrete Mathematics 28 (2014), no. 3, 1062–1073.
  * [9] V. Havin and B. Jöricke, _The Uncertainty Principle in Harmonic Analysis_ , Springer, Berlin, 1994.
  * [10] S. Jackson and R. Mauldin, _On a lattice problem of H. Steinhaus_ , Journal of the American Mathematical Society 15 (2002), no. 4, 817–856.
  * [11] S. Jackson and R. D. Mauldin, _Sets meeting isometric copies of the lattice ${\mathbb{Z}}^{2}$ in exactly one point_, Proceedings of the National Academy of Sciences 99 (2002), no. 25, 15883–15887.
  * [12] by same author, _Survey of the Steinhaus tiling problem_ , Bulletin of Symbolic Logic 9 (2003), no. 03, 335–361.
  * [13] M. N. Kolountzakis, _A new estimate for a problem of Steinhaus_ , International Mathematics Research Notices 1996 (1996), no. 11, 547–555.
  * [14] by same author, _A problem of Steinhaus: Can all placements of a planar set contain exactly one lattice point?_ , Progress in Mathematics 139 (1996), 559–566.
  * [15] by same author, _Multi-lattice tiles_ , International Mathematics Research Notices 1997 (1997), no. 19, 937–952.
  * [16] by same author, _The study of translational tiling with Fourier Analysis_ , Fourier Analysis and Convexity (L. Brandolini, ed.), Birkhäuser, 2004, pp. 131–187.
  * [17] M. N. Kolountzakis and M. Papadimitrakis, _The Steinhaus tiling problem and the range of certain quadratic forms_ , Illinois Journal of Mathematics 46 (2002), no. 3, 947–951.
  * [18] by same author, _Measurable steinhaus sets do not exist for finite sets or the integers in the plane_ , Bulletin of the London Mathematical Society 49 (2017), no. 5, 798–805.
  * [19] M. N. Kolountzakis and T. Wolff, _On the Steinhaus tiling problem_ , Mathematika 46 (1999), no. 02, 253–280.
  * [20] Mihail N Kolountzakis and Nir Lev, _Tiling by translates of a function: results and open problems_ , Discrete Analysis (2021), 28122.
  * [21] Mihail N Kolountzakis and Effie Papageorgiou, _Functions tiling with several lattices_ , arXiv preprint arXiv:2106.11701 (2021).
  * [22] P. Komjáth, _A lattice-point problem of Steinhaus_ , The Quarterly Journal of Mathematics 43 (1992), no. 2, 235–241.
  * [23] E. Mallinikova and S. Rukshin, _On one Steinhaus problem_ , Vestnik St.Petersburg Univ. Math. 28 (1995), no. 1, 28–32.
  * [24] R. Mauldin and A. Yingst, _Comments about the Steinhaus tiling problem_ , Proceedings of the American Mathematical Society 131 (2003), no. 7, 2071–2079.
  * [25] R. D. Mauldin, _Some problems in set theory, analysis and geometry_ , Paul Erdos and his Mathematics I (2001), 493–505.
  * [26] W. Sierpiński, _Sur un probleme de H. Steinhaus concernant les ensembles de points sur le plan_ , Fundamenta Mathematicae 2 (1958), no. 46, 191–194.
  * [27] S. M. Srivastava and R. Thangadurai, _On Steinhaus sets_ , Expositiones Mathematicae 23 (2005), no. 2, 171–177.
  * [28] G. Tenenbaum, _Lois de répartition des diviseurs_ , Séminaire Delange-Pisot-Poitou. Théorie des nombres 19 (1980), no. 1, 1–3.