On the Steinhaus tiling problem

Mihail N. Kolountzakis^{1} Department of Mathematics University of Crete 714 09 Iraklion, Crete, Greece kolount@math.uch.gr

Thomas Wolff Department of Mathematics 253-37 Caltech Pasadena, Ca 91125, USA wolff@cco.caltech.edu

Abstract: We prove several results related to a question of Steinhaus: is there a set E ⊂ ℝ^{2} such that the image of E under each rigid motion of ℝ^{2} contains exactly one lattice point? Assuming measurability we answer the analogous question in higher dimensions in the negative, and we improve on the known partial results in the two dimensional case. We also consider a related problem involving finite sets of rotations.

The following question was raised by Steinhaus in 1957 and has been the subject of several recent papers.

Does there exist a set E ⊂ ℝ^{2} such that every rotation and translation of E contains exactly one integer lattice point?

By a rotation and translation of a set E ⊂ ℝ^{d} we mean of course a set of the form ρE+x for some ρ ∈ SO(d) and x ∈ ℝ^{d}. It is natural to consider Steinhaus’ question separately for measurable and nonmeasurable sets. Both the measurable and nonmeasurable cases are presently open, but this paper will be concerned only with the measurable case, which leads to some attractive questions in harmonic analysis. Accordingly we define a \underline{Steinhaus set} to be a measurable set E ⊂ ℝ^{d} with the property that every rigid motion ρE + x contains exactly one lattice point. Croft [3] showed that a Steinhaus set cannot be bounded and Beck [1] gave a Fourier analysis proof of this result. One of the present authors showed in [9] that if E is a Steinhaus set (in ℝ^{2}), then ∫_{E} |x|^{α} = ∞ for all α > \frac{10}{3}. The case of closed sets has also been considered in the literature; see [4]. Some further references may be found for example in [10].

For a given lattice Λ, the condition that every translate of E contain exactly one point of Λ is equivalent to requiring that the translates of E under the elements of Λ form a tiling. Note in particular that a Steinhaus set must have measure 1. More generally, one can consider tilings by functions instead of sets; we will say that an L^{1} function f tiles with a lattice Λ if

1Partially supported by the U.S. National Science Foundation, under grant DMS 97-06753.

∑_{ν∈Λ} f(x − ν) is constant a.e.(dx)

One purpose of this paper is to solve the higher dimensional analogue of the (measurable) Steinhaus problem:

\underline{Theorem 1} Suppose that d ≥ 3 and that f : ℝ^{d} → ℝ is an L^{1} function which tiles with every rotation of ℤ^{d}, i.e.

∑_{ν∈ℤ^{d}} f(x − ρν)

is constant a.e. for each ρ ∈ SO(d). Then f agrees a.e. with a continuous function.

In particular this means that f cannot be the indicator function of a set with positive measure, so we obtain

\underline{Corollary} There are no Steinhaus sets in three or more dimensions.

We have been unable to prove a similar result in ℝ^{2} but we will improve on the bound in [9] in the following way:

\underline{Theorem 2} Assume a bound of the form

n(r) = πr^{2} + O(r^{β})  (1)

where n(r) = card((ℤ^{2}\{0}) ∩ D(0, r)). Then any Steinhaus set E ⊂ ℝ^{2} must satisfy

∫_{E} |x|^{α}dx = ∞  (2)

for all α > \frac{β}{1−β}.

Thus the result of [7] (β = \frac{46}{73} + ϵ) implies that if E is Steinhaus then (2) holds for all α > \frac{46}{27}; this is the best that we know unconditionally. The conjectured result (β = \frac{1}{2} + ϵ, see e.g. [8] or [11]) on (1) would imply (2) for all α > 1. This same range α > 1 also arises in another way - see the remark after the proof of Corollary 2.3.

Property (2) with α = 2 can be proved by an argument similar to [9] but based on L^{2} → L^{2} instead of L^{1} → L^{∞} estimates. We give this argument in Corollary 2.3 below. The relevant L^{2} estimate, Corollary 2.2(b), is quite simple and may be of some independent interest. Theorem 1 is proved in section 1 and Theorem 2 (in the case α < 2) is proved in section 3. Both proofs use bounds for exponential sums, although not very sophisticated ones.

We also consider a related problem for finite sets of rotations. It is natural to ask whether there are sets E which have the Steinhaus property relative to a large finite set of rotations {ρ_{i}}, i.e., whether it is possible to have ∑_{ν∈ℤ^{d}} χ_{E}(x − ρ_{i}ν) = 1 for each i. This question was answered in the affirmative in [10] - see section 4 for a more precise statement. We will prove an analogue of the Croft-Beck unboundedness result in this context and more generally for images of ℤ^{d} under linear maps with determinant 1 rather than just rotations:

\underline{Theorem 3} There is a constant B = B(d) making the following true. Suppose that the lattices Λ_{i}, i = 1, …, n, have volume 1 and that

Λ_{i} ∩ Λ_{j} = {0}, for all i ≠ j  (3)

Let f ∈ L^{1}(ℝ^{d}) be a function which tiles with all the Λ_{i}, and assume that f̂(0) ≠ 0. Then the diameter of the support of f is at least Bn^{\frac{1}{d}}.

The proof will be given in section 4. It is based on uniform distribution modulo 1 and a theorem of Ronkin [12] and Berndtsson [2] on the real zeros of entire functions of exponential type in ℂ^{d}.

We remark that Theorem 2 and the corollary to Theorem 1 remain valid, with the same proofs, if one adopts a somewhat more general definition of Steinhaus set as is sometimes done in the literature. For example, one could define a Steinhaus set to be a measurable set E such that, for some fixed k ∈ ℤ^{+}, and almost every (ρ, x) ∈ SO(d)×ℝ^{d}, the image ρE + x contains exactly k lattice points.

A word about notation: we will use x ≲ y to mean “x ≤ Cy for a suitable fixed constant C”.

\underline{Added November 30, 1998}: we understand that S. Jackson and D. Mauldin have recently solved the nonmeasurable Steinhaus problem, i.e. have shown that there are (nonmeasurable) sets in ℝ^{2} intersecting every isometric image of the integer lattice exactly once.

1. The higher dimensional Steinhaus problem In this section we prove Theorem 1. The argument is Fourier analytic and is based

on the following observation: let f be a function satisfying the hypotheses of Theorem 1. Then f̂ vanishes identically on any sphere centered at the origin which contains a point of ℤ^{d}. When d = 2, this observation was made in [1] (and used also in [9]) and the proof extends immediately to higher dimensions. Since every integer is the sum of four squares and every integer congruent to 1 mod 8 is the sum of three squares, we see that it suffices to prove the following:

\underline{Theorem 1′} Assume that d ≥ 3 and let a and b be positive real numbers. Let f : ℝ^{d} → ℂ be an L^{1} function such that f̂ vanishes identically on the sphere centered at the origin with radius \sqrt{am + b} for every positive integer m. Then f is continuous.

We let σ_{t} be the surface measure on the sphere in ℝ^{d} of radius t, and will normalize the Fourier transform via f̂(ξ) = ∫ f(x)e^{−2πix·ξ}dx. We note also that a “Schwarz function” will mean a function belonging to the Schwarz space as defined (say) in [6], p. 160, Definition 7.1.2.

\underline{Lemma 1.1} Assume d ≥ 2. Let q : ℝ → ℝ be a C_{0}^{∞} function supported in [\frac{1}{2}, 2], and let b ∈ (0, 1]. Define K_{N} : ℝ^{d} → ℂ

K_{N}(x) = ∑_{n} \frac{1}{\sqrt{n + b}}q(\frac{\sqrt{n + b}}{N})σ\sqrt{n+b}(x)

Then for large N there is an estimate

|K_{N}(x)| ≲ \{ \begin{matrix}(N|x|)^{−100} & if 1 ≤ |x| ≤ \frac{N}{2} \\ (\frac{N}{|x|})^{\frac{d−2}{2}} & if |x| ≥ \frac{N}{2} \end{matrix}

\underline{Proof} This will follow from the asymptotics for the Fourier transform of surface measure and a simple form of the vander Corput method for estimating exponential sums. We remark that if |x| ≥ N^{α} with α > 1 then the bound can be improved by using exponent pairs, but Lemma 1.1 as stated is enough for the proof of Theorem 1′.

It is well known (e.g. [13] p. 50) that σ̂_{1}(x) = re(B(|x|)) where B(r) = a(r)e^{2πir}, with a(r) being a complex valued function satisfying estimates

|\frac{d^{k}a}{dr^{k}}| ≲ r^{− \frac{d−1}{2} −k}  (4)

Hence also σ̂_{t}(x) = re(t^{d−1}B(t|x|)). Define t_{+} = max(t, 0), and let r = |x|. In the calculation below, we use that q(t) = 0 when t < \frac{1}{2}; this implies that various integrals may be taken interchangeably over ℝ and over (0, ∞). We have

∑_{n≥0} \frac{1}{\sqrt{n + b}}q(\frac{\sqrt{n + b}}{N})(\sqrt{n + b})^{d−1}B(r\sqrt{n + b})

= ∑_{n∈ℤ}((n + b)_{+})^{\frac{d−2}{2}} q(\frac{\sqrt{(n + b)_{+}}}{N})a(r\sqrt{(n + b)_{+}})e^{2πir\sqrt{(n+b)_{+}}}

= ∑_{ν∈ℤ} ∫ℝ((y + b)_{+})^{\frac{d−2}{2}} q(\frac{\sqrt{(y + b)_{+}}}{N})a(r\sqrt{(y + b)_{+}})e^{2πir\sqrt{(y+b)_{+}}}e^{−2πiνy}dy

= ∑_{ν∈ℤ} ∫ℝ(Nz)^{d−2}q(z)a(rNz)e^{2πirNz}e^{−2πiν(N^{2}z^{2}−b)}d(N^{2}z^{2} − b)

= r^{− \frac{d−1}{2}} N^{\frac{d+1}{2}} ∑_{ν∈ℤ} ∫ℝ ϕ(z)e^{2πirNz}e^{−2πiν(N^{2}z^{2}−b)}dz  (5)

where ϕ(z) = 2z^{d−1}(rN)^{\frac{d−1}{2}} a(rNz)q(z). We used the Poisson summation formula and then the change of variables z = \frac{\sqrt{y+b}}{N}. We note that the estimate (4) implies that the functions ϕ = ϕ_{N,r} belong to a compact subset of C_{0}^{∞}; this means that the estimates below are uniform in r and N.

We rewrite the sum (5) isolating the ν = 0 term and making some algebraic manipulations:

(5) = r^{− \frac{d−1}{2}} N^{\frac{d+1}{2}} ∫ℝ ϕ(z)e^{2πirNz}dz
+r^{− \frac{d−1}{2}} N^{\frac{d+1}{2}} ∑_{ν∈ℤ\\{0\}} e^{2πi(νb+ \frac{r^{2}}{4ν})} ∫ℝ ϕ(z)e^{−2πiνN^{2}(z− \frac{r}{2Nν})^{2}}dz  (6)

The first term in (6) is equal to r^{− \frac{d−1}{2}} N^{\frac{d+1}{2}} ϕ̂(−Nr), hence ≲ r^{− \frac{d−1}{2}} N^{\frac{d+1}{2}} (Nr)^{−k} for any k. In particular, it is ≲ (Nr)^{−100} if r ≥ 1. The terms in the sum in (6) may be evaluated via the asymptotics for Gaussian Fourier transforms ([6], Lemma 7.7.3); the νth term is equal to

e^{2πi(νb+ \frac{r^{2}}{4ν})} ∑_{k=0}^{m−1} c_{k}(νN^{2})^{−k− \frac{1}{2}} ϕ_{k}(\frac{r}{2Nν}) + O((νN^{2})^{−m− \frac{1}{2}} )  (7)

for any m; here c_{k} are fixed constants and the ϕ_{k} are certain derivatives of ϕ. All the terms in the sum over k vanish if ν ∉ [\frac{r}{4N} , \frac{r}{N}] so that

(7) ≲ \{ \begin{matrix}(νN^{2})^{− \frac{1}{2}} & if ν ∈ [\frac{r}{4N} , \frac{r}{N}] \\ (νN^{2})^{−m− \frac{1}{2}} & if ν ∉ [\frac{r}{4N} , \frac{r}{N}] \end{matrix}

Accordingly the sum in (6) is

≲ card(ℤ ∩ [\frac{r}{4N} , \frac{r}{N}])(rN)^{− \frac{1}{2}} + (rN)^{−m− \frac{1}{2}}

Taking m sufficiently large we obtain

(6) ≲ r^{− \frac{d−1}{2}} N^{\frac{d+1}{2}} card(ℤ ∩ [\frac{r}{4N} , \frac{r}{N}])(rN)^{− \frac{1}{2}} + (rN)^{−100} ≲ \{ \begin{matrix}(\frac{N}{r})^{\frac{d−2}{2}} & if r ≥ \frac{N}{2} \\ (rN)^{−100} & if 1 ≤ r ≤ \frac{N}{2} \end{matrix}

The lemma follows since K_{N} is the real part of the quantity (6). □

We need one more lemma, an easy consequence of the Poisson summation formula.

\underline{Lemma 1.2} Let k ≥ 2 be an integer, let q be a fixed C_{0}^{∞} function supported in [\frac{1}{2}, 2], let b ∈ [0, 1) and let h = h(t) be a function on the line satisfying the following estimate:

|\frac{d^{j}h}{dt^{j}}| ≤ R

when 0 ≤ j ≤ k and \frac{N}{100} ≤ t ≤ 100N. Then for large N

| ∑_{n} \frac{1}{\sqrt{n + b}}q(\frac{\sqrt{n + b}}{N})h(\sqrt{n + b}) − 2 ∫ q(\frac{t}{N})h(t)dt| ≲ RN^{−(k−1)}  (8)

where the implicit constant depends on q only.

\underline{Proof} Set g(x) = \frac{h(\sqrt{x+b})}{\sqrt{x+b}} and a(x) = q(\frac{\sqrt{x+b}}{N}). Then a is supported in x ≈ N^{2} and derivatives of a satisfy

|\frac{d^{j}a}{dx^{j}}| ≲ N^{−2j}  (9)

since the functions q(\sqrt{x + bN^{−2}}) belong to a compact subset of C_{0}^{∞} and a(x) is obtained from q(\sqrt{x + bN^{−2}}) by dilating by N^{2}. When x ≈ N^{2}, derivatives of g satisfy

|\frac{d^{j}g}{dx^{j}} | ≲ RN^{−(1+j)}  (10)

when j ≤ k. Namely, it is easy to show by induction on j that the jth derivative of g is a sum of finitely many terms each of which has the form \frac{h^{(i)}(\sqrt{x+b})}{(\sqrt{x+b})^{ℓ}} where h^{(i)} = ith derivative of h, with i ≤ j and ℓ ≥ j + 1. Estimate (10) is then obvious.

The left side of (8) is (make the change of variables t = \sqrt{x + b}) equal to

| ∑_{n} a(n)g(n) − ∫ a(x)g(x)dx|

By Poisson summation this is

| ∑_{ν≠0} âg(ν)|  (11)

and if we integrate by parts k times and use (9) and (10), we bound the νth term in the sum (11) by

|ν|^{−k} ∫ |\frac{d^{k}(ag)}{dx^{k}}|dx ≲ |ν|^{−k} ∫_{0}^{2N^{2}} RN^{−(1+k)}dx
≲ |ν|^{−k}RN^{−(k−1)}

Hence (11)≲ RN^{−(k−1)} and the proof is complete. □

\underline{Proof of Theorem 1′} We may clearly assume that a = 1 and b ≤ 1.

We let q ∈ C_{0}^{∞}(ℝ) be supported in [\frac{1}{2}, 2] and such that the functions \{q_{2^{j}}\}_{−∞}^{∞} form a partition of unity on (0, ∞); here we have defined q_{2^{j}}(x) = q(\frac{x}{2^{j}}). We define K_{N} as in Lemma 1.1 using this q.

Fix a ball D with radius 1; we will show that f is continuous on D. Let D̃ be the concentric ball with radius 2, and let f_{i} = χD̃f and f_{o} = χ_{ℝ^{d}\D̃}f where χ_{E} is the indicator function of the set E. By assumption, σ\sqrt{n+b}∗f vanishes identically for any positive integer n and therefore K_{N} ∗ f vanishes identically for any N.

\underline{Claim} Suppose η > 0 is given. Then, provided k is large enough, we have

∑_{j≥k} |K_{2^{j}} ∗ f_{i}(y)| ≤ η  (12)

for all y ∈ D.

Namely, by the preceding remarks it suffices to prove this with f_{i} replaced by f_{o}. If |y − z| ≥ 1, then Lemma 1.1 implies that

∑_{j≥0} |K_{2^{j}}(y − z)| ≲ ∑_{j:2^{j}≥2|y−z|}(2^{j}|y − z|)^{−100} + ∑_{j:2^{j}≤2|y−z|}(\frac{2^{j}}{|y − z|})^{\frac{d−2}{2}}

Since d ≥ 3, it follows easily that for a suitable constant C_{0}

∑_{j≥0} |K_{2^{j}}(y − z)| ≤ C_{0}  (13)

for all y ∈ D and z ∈ ℝ^{d}\D̃. Now fix a number R ≥ 2 which is large enough that

∫_{ℝ^{d}\D_{R}} |f| < \frac{η}{2C_{0}}

where D_{R} is the ball concentric with D and with radius R. Then, using Lemma 1.1 as in the proof of (13), if k is sufficiently large then

∑_{j≥k} |K_{2^{j}}(y − z)| < \frac{η}{2∥f∥_{1}}

for all y ∈ D and z ∈ D_{R}\D̃. It follows that

∑_{j≥k} |K_{2^{j}} ∗ f_{o}(y)| ≤ ∫_{D_{R}\D̃} ∑_{j≥k} |K_{2^{j}}(y − z)| |f(z)|dz + ∫_{ℝ^{d}\D_{R}} ∑_{j≥k} |K_{2^{j}}(y − z)| |f(z)|dz
< \frac{η}{2∥f∥_{1}} · ∥f∥_{1} + C_{0} · \frac{η}{2C_{0}}
= η

as claimed.

We now fix y ∈ D and define

h(r) =^{def} ∫ e^{2πiy·ξ}f̂_{i}(ξ)dσ_{r}(ξ) = r^{d−1} ∫_{|ξ|=1} ∫D̃ f(z)e^{2πir(y−z)·ξ}dzdσ_{1}(ξ)

The estimates below will be uniform in y ∈ D. Using Fourier inversion, we have

K_{N} ∗ f_{i}(y) = ∑_{n} \frac{1}{\sqrt{n + b}}q(\frac{\sqrt{n + b}}{N}) ∫ e^{2πiy·ξ}f̂_{i}(ξ)dσ\sqrt{n+b}(ξ)

= ∑_{n} \frac{1}{\sqrt{n + b}}q(\frac{\sqrt{n + b}}{N})h(\sqrt{n + b})

If y ∈ D, then the second form of the definition of h shows that h and all its derivatives are O(N^{d−1}) when r ∈ [\frac{N}{100}, 100N]. Accordingly, Lemma 1.2 with a large value of k implies

∫ h(t)q(\frac{t}{N})dt = \frac{1}{2}K_{N} ∗ f_{i}(y) + O(N^{−100})  (14)

Now define ψ_{N} : ℝ^{d} → ℝ via

ψ̂_{N}(ξ) = q(\frac{|ξ|}{N})

Then, using Fourier inversion and the definition of h, we have

ψ_{N} ∗ f_{i}(y) = ∫ e^{2πiy·ξ}q(\frac{|ξ|}{N})f̂_{i}(ξ)dξ
= ∫ h(t)q(\frac{t}{N})dt

On the other hand ψ_{N} belongs to the Schwarz space, and ∑_{j≥k} ψ̂_{2^{j}}(ξ) = 1 when |ξ| is large. Accordingly, the function ϕ_{2^{k}} defined via

ϕ̂_{2^{k}}(ξ) = 1 − ∑_{j≥k} ψ̂_{2^{j}}(ξ)

belongs to the Schwarz space. We have

f_{i}(y) − ϕ_{2^{k}} ∗ f_{i}(y) = ∑_{j≥k} ψ_{2^{j}} ∗ f_{i}(y)

= ∑_{j≥k} ∫ h(t)q(\frac{t}{2^{j}})dt

= \frac{1}{2} ∑_{j≥k} K_{2^{j}} ∗ f_{i}(y) + O(2^{−100k})

by (14). We conclude using (12) that

|f_{i}(y) − ϕ_{2^{k}} ∗ f_{i}(y)| ≲ ∑_{j≥k} |K_{2^{j}} ∗ f_{i}(y)| + 2^{−100k}
≲ 2η

for any given η provided k is sufficiently large. Hence, on D, f is the uniform limit of the continuous functions ϕ_{2^{k}} ∗ f_{i} and therefore continuous. □

\underline{Remark} When d = 2, we do not know whether Theorem 1′ remains true as stated, since one can no longer conclude (12). The above argument shows though that it is true if one assumes in addition that ∫ℝ^{2} |x|ϵ|f(x)| < ∞ for some ϵ > 0. Of course, when d = 2 Theorem 1′ is no longer closely related to the Steinhaus problem, since the set of integers which are sums of two squares does not contain any arithmetic progression.

2. Sobolev properties of indicator functions If E is a nice enough set in ℝ^{d} then it is well known that the indicator function χ_{E}

cannot belong to the Sobolev space W^{\frac{1}{2}} , i.e. the integral ∫ℝ_{d} |ξ| |χ̂_{E}(ξ)|^{2}dξ must be infinite. In fact, there is an asymptotic expression which implies in particular that

∫_{|ξ|≥R} |χ̂_{E}(ξ)|^{2}dξ ≈ R^{−1}  (15)

as R → ∞. This is often used in connection with irregularities of distribution; see e.g. [11].

We will not use (15) in this paper, but we will need to know that the lower bound in (15) is valid without any regularity assumptions on the set E. This is not difficult but does not seem to be in the literature, so we prove it in Corollary 2.2 below.

Let ϕ be a Schwarz class function in ℝ^{d} with ϕ̂(0) = 1; ϕ will be kept fixed for the rest of this section. Let ϕϵ be the corresponding approximate identity defined by ϕϵ(x) = ϵ^{−d}ϕ(ϵ^{−1}x).

\underline{Lemma 2.1} Suppose that E is a set in ℝ^{d} with |E| = 1 and |E ∩ D| > 0 for a certain ball D with radius 1. Let D̃ be the concentric ball with radius C_{d}. Then

|\{x ∈ D̃ : \frac{1}{4} ≤ ϕϵ ∗ χ_{E}(x) ≤ \frac{3}{4}\}| ≳ ϵ

provided that ϵ is sufficiently small; the implicit constants may depend on E.

\underline{Proof} We will use the following well-known fact:

∥∇(ϕϵ ∗ χ_{E})∥_{∞} ≲ ϵ^{−1}  (16)

To prove (16), let ψ = ∇ϕ, let C = ∥ψ∥_{1} and define ψϵ(x) = ϵ^{−d}ψ(ϵ^{−1}x). Differentiation under the integral sign leads to∇(ϕϵ∗χ_{E}) = ϵ^{−1}ψϵ∗χ_{E}. On the other hand, for any x ∈ ℝ^{d}, we have |ψϵ ∗ χ_{E}(x)| ≤ ∥ψϵ∥_{1}∥χ_{E}∥_{∞} = ∥ψ∥_{1}, which proves that ∥∇(ϕϵ ∗ χ_{E})∥_{∞} ≤ Cϵ^{−1}, as claimed.

It follows by the mean value theorem that if ϕϵ ∗ χ_{E}(x_{0}) = \frac{1}{2}, then ϕϵ ∗ χ_{E}(x) ∈ [\frac{1}{4}, \frac{3}{4}] for all x ∈ D(x_{0}, C^{−1}ϵ). We let σ be surface measure on S^{d−1}; here we take it to be normalized so that σ(S^{d−1}) = 1. We also let E^{c} be the complement of the set E.

Choose once and for all a point of density of E ∩ D, which we may assume to be the origin. Let A be the set of all ω ∈ S^{d−1} such that the ray {rω : 1 < r < C_{d}} contains a point of density of E^{c}. Since E has measure 1 it is clear that A must have measure ≥ \frac{3}{4} provided C_{d} is large enough. If ω ∈ A then we let p_{ω} = r_{ω}ω be the corresponding point of density of E^{c}. In a similar way we can choose a small sphere centered at 0, x = {ρω : ω ∈ S^{d−1}}, where ρ < 1 in such a way that q_{ω} = ρω is a point of density of E for all ω ∈ B where B ⊂ S^{d−1} is a set of measure > \frac{3}{4}.

By Egoroff’s theorem, we can find subsets A^{∗} ⊂ A with measure ≥ \frac{2}{3} and B^{∗} ⊂ B with measure ≥ \frac{2}{3} and a number ϵ_{0} such that if ϵ < ϵ_{0} then

\frac{|E ∩ D(p_{ω}, ϵ)|}{|D(p_{ω}, ϵ)|} < 10^{−6} for all ω ∈ A^{∗}  (17)

and

\frac{|E^{c} ∩ D(q_{ω}, ϵ)|}{|D(q_{ω}, ϵ)|} < 10^{−6} for all ω ∈ B^{∗}.  (18)

Note |A^{∗} ∩ B^{∗}| ≥ \frac{1}{3}.

Now fix ϵ < ϵ_{0}, let ω ∈ A^{∗} ∩ B^{∗} and consider ϕϵ ∗ χ_{E} as a function on the line segment {tω : ρ ≤ t ≤ r_{ω}}. Its value at ρ is ≥ 1 − 10^{−6} and its value at r_{ω} is ≤ 10^{−6}. Accordingly, there must be a value of t_{ω} ∈ (ρ, r_{ω}) where ϕϵ ∗ χ_{E}(t_{ω}ω) = \frac{1}{2}. Then by the remarks at the beginning of the proof, ϕϵ ∗ χ_{E}(tω) ∈ (\frac{1}{4}, \frac{3}{4}) for all ω ∈ A^{∗} ∩ B^{∗} and all t in the interval centered at t_{ω} with length C^{−1}ϵ. Using polar coordinates it now follows that the set \{x : ϕϵ ∗ χ_{E}(x) ∈ (\frac{1}{4}, \frac{3}{4})\} has measure ≳ ϵ where the constant is independent of ϵ provided ϵ is small. □

\underline{Corollary 2.2} If E ⊂ ℝ^{d} is a set with finite nonzero measure and if ϕϵ is as in Lemma 2.1 then

(a) ∥ϕϵ ∗ χ_{E} − χ_{E}∥_{2} ≥ C_{E}^{−1}ϵ^{\frac{1}{2}} for small ϵ.

(b) ∫_{|ξ|≥R} |χ̂_{E}|^{2} ≥ (C_{E}R)^{−1} for a certain constant C_{E} depending on E and all sufficiently large R. In particular, χ_{E} ∉ W^{\frac{1}{2}} .

\underline{Proof} Part (a) is immediate from Lemma 2.1, since \frac{1}{4} ≤ ϕϵ ∗ χ_{E}(x) ≤ \frac{3}{4} implies |ϕϵ ∗ χ_{E}(x) − χ_{E}(x)| ≥ \frac{1}{4}. Part (b) follows easily from (a). By (a) we have

∫_{ℝ_{n}} |χ̂_{E}(ξ)|^{2}|ϕ̂(R^{−1}ξ) − 1|^{2}dξ ≥ (C_{E}R)^{−1}  (19)

uniformly in R, and if ϕ has been chosen to be nonnegative, then |ϕ̂(R^{−1}ξ)−1| is bounded away from zero when |ξ| ≥ R. □

¿From Corollary 2.2 we can obtain a form of Theorem 2 where α = 2:

\underline{Corollary 2.3} If E ⊂ ℝ^{2} is Steinhaus then ∫_{E} |x|^{2}dx = ∞.

\underline{Proof} As was done in [9], we use the elementary estimate (which is also the only known estimate) for the maximum gap between sums of two squares:

(G): If r ∈ [1, ∞) then for a suitable fixed constant C_{1} there is ν ∈ ℤ^{2} such that |r − |ν|| ≤ C_{1}r^{− \frac{1}{2}} .

We also use the following form of the Poincare inequality, which is well-known.

(PI): Let Q be a square in the plane with side r and let γ be a Jordan arc contained in Q, such that the distance between the endpoints of γ is ≥ C_{1}^{−1}r. Let f be a function which vanishes on γ. Then

∫_{Q} |f|^{2} ≤ C_{2}r^{2} ∫_{Q} |∇f|^{2}

where C_{2} depends on C_{1} only.

Fix a large number N and define A_{N} =^{def} {ξ ∈ ℝ^{2} : N ≤ |ξ| ≤ 2N}. Let C be a large enough constant and cover A_{N} with nonoverlapping squares Q of side CN^{− \frac{1}{2}} . If E is Steinhaus, f = χ̂_{E}, then (G) implies that each square will satisfy the hypothesis of (PI). We conclude that

∫_{Q} |χ̂_{E}|^{2} ≲ N^{−1} ∫_{Q} |∇χ̂_{E}|^{2}

for each Q and therefore

∫_{A_{N}} |χ̂_{E}|^{2} ≲ N^{−1} ∫_{A_{N}^{∗}} |∇χ̂_{E}|^{2}

where A_{N}^{∗} is the union of the squares and is contained in {ξ ∈ ℝ^{2} : N −1 ≤ |ξ| ≤ 2N +1}. Consequently

∫_{A_{N}} |ξ||χ̂_{E}(ξ)|^{2}dξ ≲ ∫_{A_{N}^{∗}} |∇χ̂_{E}|^{2}

If we now sum over dyadic values of N and use that no point belongs to more than two A_{N}^{∗}’s, we obtain

∫_{ℝ_{2}} |ξ||χ̂_{E}(ξ)|^{2}dξ ≲ ∫_{ℝ_{2}} |∇χ̂_{E}|^{2}dξ + 1

Hence by Corollary 2.2(b), ∫ℝ^{2} |∇χ̂_{E}|^{2} = ∞, i.e. ∫_{E} |x|^{2}dx = ∞. □

\underline{Remarks} 1. In [9] the estimate (G) was used to prove that ∫_{E} |x|^{4}dx = ∞ and then the exponent 4 was lowered to \frac{10}{3} + ϵ via a deep result of Hooley [5] regarding the ℓ^{p} averages of the gap lengths. However, it does not appear that [5] can be used in a similar way in connection with the argument in the proof of Corollary 2.3, since it is difficult to estimate the contribution from the large gaps, even though by Hooley’s theorem there are comparatively few of them. Instead, in section 3 we will improve on the exponent 2 using a different argument and the known results on the circle problem (1), as discussed in the introduction.

On the other hand, assume for a moment that (G) holds with the exponent \frac{1}{2} replaced by 1 − ϵ (i.e. assume that the maximum gap between numbers which are sums of two squares is O(Nϵ)). Then it would follow easily by an argument like the proof of Corollary 2.3 (using fractional integration instead of the Poincare inequality) that any Steinhaus set E satisfies ∫_{E} |x|^{α} = ∞ for all α > 1 - the same range of exponents that would follow from the conjectured result on the circle problem via Theorem 2.

2. The last statement in Corollary 2.2 is also valid in L^{p} norms. If 1 < p < ∞ and α > 0, then we let W^{p,α} be the L^{p} Sobolev space with α derivatives. If E is any set with positive measure, then χ_{E} cannot belong to W^{p, \frac{1}{p}}. This is because Lemma 2.1 implies that ∥χ_{E} − ϕϵ ∗ χ_{E}∥_{p} ≳ ϵ^{\frac{1}{p}}, which implies that χ_{E} cannot belong to any Besov space Λpq_{\frac{1}{p}} with q < ∞. Since Λpq_{\frac{1}{p}} contains W^{p, \frac{1}{p}} when q ≥ max(p, 2) it follows that χ_{E} cannot

belong to W^{p, \frac{1}{p}}.

3. We note that Croft’s proof [3] that Steinhaus sets are unbounded was based on considering points which are density points neither of E nor of its complement. Corollary 2.2 is basically a quantitative version of existence of such points.

We now prove a further technical result, which we will need in the next section for the proof of Theorem 2. It says roughly that the lower bounds on ∥ϕϵ∗χ_{E} −χ_{E}∥_{2} obtained (as above) by considering large values are always sharp. If E ⊂ ℝ^{d} is a set of finite measure, then we define

Aϵ(E) = ∥ϕϵ ∗ χ_{E} − χ_{E}∥_{1}
Bϵ(E) = ∥ϕϵ ∗ χ_{E} − χ_{E}∥_{2}^{2}

Cϵ(E) = |\{x ∈ ℝ^{d} : |ϕϵ ∗ χ_{E}(x) − χ_{E}(x)| ≥ \frac{1}{4}\}|

It is easy to see that

Cϵ(E) ≲ Bϵ(E) ≲ Aϵ(E)  (20)

for any E and ϵ.

\underline{Lemma 2.4} For any given set E ⊂ ℝ^{d} with |E| < ∞ there is a sequence ϵ_{j} = 2^{−k_{j}} → 0 such that A_{ϵ_{j}}(E) ≲ C_{ϵ_{j}}(E); the constants here (and in (20)) depend only on d and ϕ.

\underline{Remark} The proof of Lemma 2.4 is somewhat shorter when ϕ has compact support, but we did not want to assume this since in section 3 it will be convenient to assume instead that ϕ̂ has compact support.

\underline{Proof} We may assume that |E| = 1. If D = D(x, ρ) is the ball with center x and radius ρ then we define

α(D) = min(|E ∩ D|, |E^{c} ∩ D|)

β(D) = ∑_{j=0}^{∞} 2^{−10dj}α(2^{j}D)

Here we have used the notation E^{c} = ℝ^{d}\E and rD(x, ρ) = D(x, rρ).

Let C_{0} be a large constant. If D is any ball of radius C_{0}^{−1}ϵ then we claim that the following are valid:

I. ∥ϕϵ ∗ χ_{E} − χ_{E}∥_{L^{1}(D)} ≲ β(D)

II. |\{x ∈ D : |ϕϵ ∗ χ_{E}(x) − χ_{E}(x)| ≥ \frac{1}{4}\}| ≥ α(D).

In fact, II follows easily from (16). Namely, if C_{0} is large then (16) implies via the mean value theorem that the difference between the maximum and minimum values of ϕϵ ∗ χ_{E} on the ball D is less than \frac{1}{2}. It follows that one of the following must hold

(i) ϕϵ ∗ χ(x) ≤ \frac{3}{4} for all x ∈ D, or

(ii) ϕϵ ∗ χ(x) ≥ \frac{1}{4} for all x ∈ D.

In case (i) we have |\{x ∈ D : |ϕϵ ∗ χ_{E}(x) − χ_{E}(x)| ≥ \frac{1}{4}\}| ≥ |E ∩ D| ≥ α(D) and in case (ii) we have |\{x ∈ D : |ϕϵ ∗ χ_{E}(x) − χ_{E}(x)| ≥ \frac{1}{4}\}| ≥ |E^{c} ∩ D| ≥ α(D), i.e. II holds in either case.

To prove I, we express ϕ as a synthesis of C_{0}^{∞} functions, say

ϕ = ∑_{j=0}^{∞} a_{j}ϕ^{j}

where suppϕ^{j} ⊂ D(0, (2C_{0})^{−1}2^{j}), ϕ̂_{j}(0) = 1, ∥ϕ_{j}∥_{1} ≤ C and a_{j} ≤ C2^{−10dj}. Let ϕϵ^{j}(x) = ϵ^{−d}ϕ^{j}(ϵ^{−1}x). It follows by Minkowski’s inequality and the support properties that

∥ϕϵ^{j} ∗ χ_{E} − χ_{E}∥_{L^{1}(D)} ≲ |E ∩ (2^{j}D)|

and therefore also

∥ϕϵ^{j} ∗ χ_{E} − χ_{E}∥_{L^{1}(D)} ≲ α(2^{j}D)

since the left side is unchanged when E is replaced by E^{c}. I now follows by summing over j.

Let I(ϵ) = ∫ℝ_{d} α(D(x, C_{0}^{−1}ϵ))dx, J(ϵ) = ∫ℝ_{d} β(D(x, C_{0}^{−1}ϵ))dx. Integrating I and II over ℝ^{d} we get

ϵ^{−d}I(ϵ) ≲ Cϵ(E) ≲ Aϵ(E) ≲ ϵ^{−d}J(ϵ)  (21)

Let k be a large positive integer and consider the sums

I_{k} = ∑_{ℓ=0}^{∞} 2^{−5dℓ}I(2^{ℓ−k})

J_{k} = ∑_{ℓ=0}^{∞} 2^{−5dℓ}J(2^{ℓ−k})

For any k, we have

J_{k} = ∑_{ℓ=0}^{∞} ∑_{j=0}^{∞} 2^{−d(5ℓ+10j)}I(2^{ℓ+j−k})

≲ ∑_{m=0}^{∞} 2^{−5dm}I(2^{m−k})
= I_{k}

On the next to last line, we set m = j + ℓ and used that ∑_{j+ℓ=m} 2^{−d(5ℓ+10j)} ≲ 2^{−5dm}.

Now observe that J(ϵ) ≳ ϵ^{d+1} for small ϵ, e.g. by (21) and Corollary 2.2(a), and that I(ϵ) ≲ ϵ^{d} for any ϵ (even when ϵ > 1), e.g. by (21). It follows that J_{k} ≳ 2^{−(d+1)k} and that ∑_{ℓ> \frac{k}{2}} 2^{−5dℓ}I_{k−ℓ} is small compared with 2^{−(d+1)k}. Accordingly

∑_{ℓ≤ \frac{k}{2}} 2^{−5dℓ}J(2^{ℓ−k}) ≲ ∑_{ℓ≤ \frac{k}{2}} 2^{−5dℓ}I(2^{ℓ−k})

which implies there is a value 2^{ℓ−k} ≤ \sqrt{2^{−k}} with J(2^{ℓ−k}) ≲ I(2^{ℓ−k}). This and (21) prove the lemma. □

In the rest of this section we assume that the Schwarz function ϕ satisfies the following conditions:

suppϕ̂ ⊂ D(0, 1), ϕ̂(ξ) = 1 if ξ ∈ D(0, \frac{1}{2})  (22)

We set ψ(x) = ϕ(x)−2^{d}ϕ(2x); thus ψ is a Schwarz function with suppψ̂ ⊂ D(0, 2)\D(0, \frac{1}{2}). We define ψϵ(x) = ϵ^{−d}ψ(ϵ^{−1}x), so that ∑_{j=0}^{∞} ψ_{2^{−j}ϵ} ∗ f = ϕϵ ∗ f − f for any f and ϵ, as may be seen by taking Fourier transforms. Property (22) implies that no point belongs to the support of ψ̂_{j} for more that three values of j, so it follows by the Plancherel theorem that

∑_{j=0}^{∞} ∥ψ_{2^{−j}ϵ} ∗ f∥_{2}^{2} ≳ ∥f − ϕϵ ∗ f∥_{2}^{2}  (23)

Furthermore,

∥ψ_{2^{−j}ϵ} ∗ f∥_{1} ≲ ∥f − ϕϵ ∗ f∥_{1}  (24)

Namely, the support property (22) makes it possible to represent ψ_{2^{−j}} = g_{j} ∗ (δ − ϕ) with ∥g_{j}∥_{1} ≤ C (here δ is the Dirac delta function). Indeed if j ≥ 1 then ψ̂_{2^{−j}} and ϕ̂ have disjoint support so we can take g_{j} = ψ_{2^{−j}}, and when j = 0, ψ̂_{2^{−j}} = ψ̂ is obtained from 1−ϕ̂ by multiplication by the C_{0}^{∞} function m defined via m(ξ) = −1 when |ξ| ≤ 1 and \frac{ψ̂}{1−ϕ̂} when |ξ| ≥ 1. It follows using dilations that ψ_{2^{−j}ϵ} = g_{j,ϵ} ∗ (δ − ϕϵ) where ∥g_{j,ϵ}∥_{1} = ∥g_{j}∥_{1} ≤ C.

Accordingly ∥ψ_{2^{−j}ϵ} ∗ f∥_{1} = ∥g_{j,ϵ} ∗ (δ − ϕϵ) ∗ f∥_{1} = ∥g_{j,ϵ} ∗ (f − ϕϵ ∗ f)∥_{1} ≤ C∥f − ϕϵ ∗ f∥_{1} which is (24).

\underline{Corollary 2.5} Assume that ϕ satisfies (22) and define ψ as above. If E is a set of finite measure then there is a sequence ϵ_{j} → 0 such that, for each j, (i) ∥ψ_{ϵ_{j}} ∗ χ_{E}∥_{1} ≲

(log \frac{1}{ϵ_{j}})^{2}∥ψ_{ϵ_{j}} ∗ χ_{E}∥_{2}^{2} and (ii) ∥ψ_{ϵ_{j}} ∗ χ_{E}∥_{2}^{2} ≳ ϵ_{j}.

\underline{Proof} Let ϵ be such that Aϵ(E) ≲ Bϵ(E). If η_{k} = 2^{−k}ϵ then ∥ψ_{η_{k}} ∗ χ_{E}∥_{1} ≲ Aϵ(E) by (24) and ∑_{k≥0} ∥ψ_{η_{k}} ∗ χ_{E}∥_{2}^{2} ≳ Bϵ(E) by (23). Hence, for some k we must have

max((k + 1)^{−2}∥ψ_{η_{k}} ∗ χ_{E}∥_{1}, (k + 1)^{−2}Bϵ(E)) ≲ ∥ψ_{η_{k}} ∗ χ_{E}∥_{2}^{2}

Also Bϵ(E) ≳ ϵ by Corollary 2.2(a), so (k + 1)^{−2}Bϵ(E) ≳ η_{k}, and (k + 1)^{−2} ≳ (log \frac{1}{η_{k}})^{−2}. We conclude that

max((log \frac{1}{η_{k}})^{−2}∥ψ_{η_{k}} ∗ χ_{E}∥_{1}, η_{k}) ≲ ∥ψ_{η_{k}} ∗ χ_{E}∥_{2}^{2}

i.e. that there are arbitrarily small numbers ϵ_{j} such that (i) and (ii) hold. □

3. Proof of Theorem 2 The following fact will be used repeatedly below, so we formulate it as a lemma.

\underline{Lemma 3.1} If N ≥ 1 then for any ϵ > 0 and r > 0

∑_{ν∈ℤ^{2}}(1 + N|r − |ν||)^{−100} ≤ CϵNϵ max(\frac{r}{N} , 1)

\underline{Proof} Because of the rapid decay of (1 + Nt)^{−100} when t ≥ \frac{1}{N}, it is easy to show that it suffices to prove the following estimate for all r:

n(r + \frac{1}{N}) − n(r) ≲ Nϵ max(\frac{r}{N} , 1)  (25)

where n(r) is as in (1). To prove (25), consider two cases.

(i) r ≤ N^{3}. The number of lattice points on a circle is bounded by any given power of the radius, hence a circle of radius ρ ∈ (r, r+ \frac{1}{N}) contains ≲ r\frac{ϵ}{3} ≲ Nϵ lattice points. There are ≲ max(\frac{r}{N} , 1) values of ρ for which it contains some lattice point and (25) follows.

(ii) r ≥ N^{3}. In this case we use (1) with the classical exponent β = \frac{2}{3}. Thus n(r + \frac{1}{N}) − n(r) ≲ \frac{r}{N} + r^{\frac{2}{3}} ≈ \frac{r}{N}. □

The proof of Theorem 2 will be like the proof of Theorem 1 insofar as it is also based on using an appropriate “fundamental solution”. However, we must replace the kernel in Lemma 1.1 by an analogous one involving a sum only over circles which contain lattice points. We will use the obvious choice where one counts each circle according to the number of lattice points it contains.

Let p be a nonnegative C^{∞} function of one variable supported in t ≤ 1 and with p(t) = 1 when t ≤ \frac{1}{2}. Define

K_{N}(x) = ∑_{ν∈ℤ^{2},ν≠0} \frac{1}{|ν|}σ̂_{|ν|}(r)p(\frac{|ν|}{N})

where r = |x|.

\underline{Lemma 3.2} Assume the bound (1). Then

|K_{N}(x)| ≲ N|x|^{−(1−β)}  (26)

if |x| ≥ N ≥ 1.

The proof of this lemma is routine but a bit long, so to avoid loss of continuity we postpone it to the appendix, and will now continue with the proof of Theorem 2.

We will use complex notation when convenient and define operators T_{ρ} on L^{2}(ℝ^{2}) via T_{ρ}f(x) = ∫ f(x + ρe^{iθ})\frac{dθ}{2π}, i.e. T_{ρ}f is the circular mean over the circle of radius ρ.

\underline{Lemma 3.3} Let E ⊂ ℝ^{2} be a Steinhaus set and let ψ be a Schwarz function in ℝ^{2} with ψ̂(0) = 0. Let f = χ_{E}. Then

ψ ∗ f(x) = − ∑_{ν∈ℤ^{2},ν≠0} T_{|ν|}(ψ ∗ f)

\underline{Proof} The Steinhaus property gives after convolving with ψ that

ψ ∗ f(x) = − ∑_{ν∈ℤ^{2},ν≠0} ψ ∗ f(x + e^{iθ}ν)

for all θ and x. The lemma follows by integrating with respect to θ. □

\underline{Proof of Theorem 2} We let β be such that (1) is true and assume toward a contradiction that E is Steinhaus and ∫_{E} |x|^{α} < ∞ for some α > \frac{β}{1−β}.

Fix a Schwarz function ϕ satisfying (22) and set ψ(x) = ϕ(x)−4ϕ(2x). Thus suppψ̂ ⊂ D(0, 2)\D(0, \frac{1}{2}). Let ψ_{R}(x) = R^{2}ψ(Rx). Also fix a function p as in Lemma 3.2. Applying Lemma 3.3 with ψ_{R}, we get for any M

ψ_{R} ∗ χ_{E} = −A_{M}(ψ_{R} ∗ χ_{E}) − B_{M}(ψ_{R} ∗ χ_{E})  (27)

where the operators A_{M} and B_{M} are defined by

A_{M} = ∑_{ν≠0} p(\frac{|ν|}{M})T_{|ν|}

B_{M} = ∑_{ν}(1 − p(\frac{|ν|}{M}))T_{|ν|}

Note that A_{M} and B_{M} are convolution operators and the convolution kernel of A_{M} is supported in |x| ≤ M.

The strategy of the proof is to show that the right side of (27) is too small to be equal to the left side, and we start by making appropriate L^{2} → L^{2} and L^{1} → L^{∞} estimates for the operators A_{M} and B_{M} respectively. We state the estimates in a “localized” form for the sake of the application below.

\underline{Claim 1} Assume that M < R and that supp(ĝ) ⊂ D(0, 2R)\D(0, \frac{R}{2}). Then, given (1), there is an estimate

∥A_{M}g∥_{L^{2}(D(a,M))} ≲ MR^{−(1−β)}∥g∥_{L^{2}(D(a,10M))} + R^{−100}∥g∥_{2}

for any a ∈ ℝ^{2}.

Namely, let J_{0}^{R} and J^{R} be the annuli \{ξ : \frac{R}{3} ≤ |ξ| ≤ 3R\} and \{ξ : \frac{R}{4} ≤ |ξ| ≤ 4R\} respectively. The estimate

suppĝ ⊂ J^{R} ⇒ ∥A_{M}g∥_{2} ≲ MR^{−(1−β)}∥g∥_{2}  (28)

is immediate from Lemma 3.2: A_{M} is a convolution operator, and the corresponding multiplier is the function K_{M}, whose L^{∞} norm on D(0, 4R)\D(0, \frac{R}{4}) is ≲ MR^{−(1−β)} by Lemma 3.2.

The localized form follows in a standard way using that the convolution kernel of A_{M} is supported in |x| ≤ M: we may suppose a = 0, and we let ρ ∈ C_{0}^{∞} be such that ρ = 1 on D(0, 10). Define ρ_{M}(x) = ρ(M^{−1}x). Let χ be a Schwarz function whose Fourier transform is supported in J^{1} and equal to 1 on J_{0}^{1} and define χ_{R}(x) = R^{2}χ(Rx).

The support property of the convolution kernel implies that A_{M}g(x) = A_{M}(gρ_{M})(x) when x ∈ D(0, M). Accordingly

∥A_{M}g∥_{L^{2}(D(0,M))} ≤ ∥(A_{M}(χ_{R} ∗ (gρ_{M}))∥_{2} + ∥A_{M}(gρ_{M} − χ_{R} ∗ (gρ_{M}))∥_{2}
≲ MR^{−(1−β)}∥gρ_{M}∥_{2} + M^{2}∥gρ_{M} − χ_{R} ∗ (gρ_{M})∥_{2}  (29)

where we used (28), that ∥χ_{R}∥_{1} = ∥χ∥_{1} ≤ C, and the trivial estimate ∥A_{M}f∥_{2} ≲ M^{2}∥f∥_{2} (since A_{M} is convolution with a sum of O(M^{2}) probability measures) in the second term. On taking Fourier transforms we see that ∥gρ_{M} − χ_{R} ∗ (gρ_{M})∥_{2} = ∥(1 − χ̂_{R})ρ̂_{M} ∗ ĝ∥_{2} ≲ ∥ρ̂_{M} ∗ ĝ∥_{L^{2}(ℝ^{2}\J_{0}^{R})} ≲ (MR)^{−102}∥g∥_{2}, where the last inequality follows since ĝ is supported in \frac{R}{2} ≤ |ξ| ≤ 2R and |ρ̂_{M}(η)| ≲ M^{2}(M|η|)^{−200}. Claim 1 follows by substituting this bound into (29).

\underline{Claim 2} If M < R, suppĝ ⊂ D(0, 2R) then for any ϵ > 0,

|B_{M}g(x)| ≲ Rϵ \frac{R}{M} ∥g∥_{L^{1}(D(x, \frac{M}{3} )^{c})} + R^{−100}∥g∥_{1}

For this, we fix a Schwarz function ρ such that ρ̂ = 1 on D(0, 2) and define ρ_{R}(x) = R^{2}ρ(Rx). Then g = ρ_{R} ∗ g, so

B_{M}g = ∑_{ν}(1 − p(\frac{|ν|}{M}))T_{|ν|}(ρ_{R} ∗ g)
= ∑_{ν}(1 − p(\frac{|ν|}{M}))|ν|^{−1}(ρ_{R} ∗ σ_{|ν|}) ∗ g  (30)

where σ_{|ν|} is arclength measure on the circle centered at 0 with radius |ν|. We let H be the convolution kernel in (30), i.e. H(x) = ∑_{ν}(1 − p(\frac{|ν|}{M}))|ν|^{−1}ρ_{R} ∗ σ_{|ν|}(x).

Uniformly in ν we have

|ρ_{R} ∗ σ_{|ν|}(x)| ≲ R(1 + R||ν| − |x||)^{−101}  (31)

This is well known and is easy to prove using that σ_{|ν|}(D(a, t)) ≲ t uniformly in ν, a and t. We now sum over ν and use that p(t) = 1 when t ≤ \frac{1}{2}. Thus

|H(y)| ≲ ∑_{|ν|≥ \frac{M}{2}} \frac{R}{|ν|}(1 + R||ν| − |y||)^{−101}

It is clear that

∑_{||ν|−|y||≥ \frac{|ν|}{100}^{|ν|≥ \frac{M}{2}}} \frac{R}{|ν|}(1 + R||ν| − |y||)^{−101} ≲ ∑_{|ν|≥ \frac{M}{2}} \frac{R}{|ν|}(R|ν|)^{−101} ≲ R^{−100}

Accordingly,

|H(y)| ≲ R^{−100} + ∑_{||ν|−|y||≤ \frac{|ν|}{100}^{|ν|≥ \frac{M}{2}}} \frac{R}{|ν|}(1 + R||ν| − |y||)^{−100}  (32)

If |y| ≤ \frac{M}{3} then the sum in (32) is empty, so

|H(y)| ≲ R^{−100}  (33)

If |y| > \frac{M}{3} , then we observe that |ν| ≥ \frac{|y|}{2} for all ν in the sum (32), and then apply Lemma 3.1 with r = |y| and N = R obtaining

|H(y)| ≲ R^{−100} + \frac{R}{|y|} ∑_{ν}(1 + R||ν| − |y||)^{−100}
≲ \frac{R}{|y|} · Rϵ max(\frac{|y|}{R}, 1)
≲ Rϵ \frac{R}{M}  (34)

Claim 2 follows from formula (30) and the estimates (33), (34) for the convolution kernel H.

We now continue with the main proof. By Corollary 2.5, we can find arbitrarily large numbers R such that ∥ψ_{R}∗χ_{E}∥_{2}^{2} ≥ (log R)^{−2}∥ψ_{R}∗χ_{E}∥_{1} and also ∥ψ_{R}∗χ_{E}∥_{2}^{2} ≳ R^{−1}. In the subsequent argument R is taken to be a sufficiently large number with these properties. We fix γ with 1 − β > γ > \frac{1}{1+α}, and define

M = R^{γ}  (35)

To ease the notation we also define

g = ψ_{R} ∗ χ_{E}

Note that supp(ĝ) ⊂ D(0, 2R)\D(0, \frac{R}{2}); this fact will be used without mention below.

We subdivide ℝ^{2} in squares Q of side 10^{−6}M taking one of them to be centered at the origin. We will denote the square centered at the origin by Q_{0}. Let Q̃ be the disc concentric with Q with radius \frac{1}{10}M and ˜ Q̃ the concentric disc with radius M. Define a square Q to be \underline{good} if ∥g∥_{L^{2}(Q)}^{2} ≥ (log R)^{−4}∥g∥_{L^{1}( ˜Q̃)} and \underline{bad} otherwise. The reason for making this definition is as follows:

\underline{Claim 3} If Q is a good square and h : Q → ℂ is a function on Q such that ∥h∥_{∞} ≤ \frac{1}{4}(log R)^{−4} then

∥g + h∥_{L^{2}(Q)}^{2} ≳ (log R)^{−4}∥g∥_{L^{2}( ˜Q̃)}^{2}

Namely, let Y = {y ∈ Q : |g(y)| ≥ 2∥h∥_{∞}}. Then

∥g∥_{L^{2}(Q\Y)}^{2} ≤ ∥g∥_{L^{∞}(Q\Y)}∥g∥_{L^{1}(Q\Y)}
≤ 2∥h∥_{∞}∥g∥_{L^{1}(Q)}
≤ 2(log R)^{4}∥h∥_{∞}∥g∥_{L^{2}(Q)}^{2}
≤ \frac{1}{2}∥g∥_{L^{2}(Q)}^{2}

so that ∥g∥_{L^{2}(Y)}^{2} ≥ \frac{1}{2}∥g∥_{L^{2}(Q)}^{2}. If y ∈ Y, then |g(y) + h(y)| ≥ \frac{1}{2}|g(y)|, so we have |g + h∥_{L^{2}(Y)}^{2} ≥ \frac{1}{4}∥g∥_{L^{2}(Y)}^{2} ≥ \frac{1}{8}∥g∥_{L^{2}(Q)}^{2}. Claim 3 now follows since ∥g∥_{L^{2}(Q)}^{2} ≥ (log R)^{−4}∥g∥_{L^{1}( ˜Q̃)} ≳ (log R)^{−4}∥g∥_{L^{2}( ˜Q̃)}^{2}.

Next we have

\underline{Claim 4} There is a good square Q with the following two additional properties:

∥g∥_{L^{1}(Q̃^{c})} ≲ (log R)^{100}M^{−α}  (36)
∥g∥_{L^{1}(Q)} ≥ R^{−50}  (37)

For this, we let G and B be the unions of the good and bad squares respectively and let ˜ B̃ be the union of the ˜ Q̃’s corresponding to bad Q’s. We note that any given point y belongs to ˜ Q̃ for only a bounded number of Q’s. We have

∥g∥_{L^{1}(G)} + ∥g∥_{L^{1}( ˜B̃)} ≲ ∥g∥_{1}
≲ (log R)^{2}∥g∥_{2}^{2}
= (log R)^{2}∥g∥_{L^{2}(G)}^{2} + (log R)^{2}∥g∥_{L^{2}(B)}^{2}
≲ (log R)^{2}∥g∥_{L^{1}(G)} + (log R)^{−2}∥g∥_{L^{1}(˜B̃)}

so that ∥g∥_{L^{1}(˜B̃)} ≲ (log R)^{2}∥g∥_{L^{1}(G)} and therefore

∥g∥_{1} ≲ (log R)^{2}∥g∥_{L^{1}(G)}  (38)

Next define G_{∗} to be the union of all good squares Q which have property (36). We will show that

∥g∥_{L^{1}(G_{∗})} ≳ (log R)^{−2}∥g∥_{1}  (39)

Namely, our decay assumption on the set E implies that

∥g∥_{L^{1}(Q_{0}^{c})} ≲ M^{−α}  (40)

Now consider two cases:

(i) ∥g∥_{L^{1}(Q_{0})} ≤ \frac{1}{2}(log R)^{100}M^{−α}

(ii) ∥g∥_{L^{1}(Q_{0})} > \frac{1}{2}(log R)^{100}M^{−α}

In case (i), (40) implies that all squares Q satisfy (36) so (39) follows tautologically from (38). In case (ii), (40) implies that

∥g∥_{L^{1}(Q_{0}^{c})} ≲ (log R)^{−100}∥g∥_{L^{1}(Q_{0})}  (41)

If Q_{0} were bad, then (41) would imply that ∥g∥_{L^{1}(G)} ≲ (log R)^{−100}∥g∥_{1}, contradicting (38) if R is large enough. So Q_{0} must be good, and therefore contained in G_{∗} by (40). Accordingly ∥g∥_{L^{1}(G_{∗})} ≥ ∥g∥_{L^{1}(Q_{0})} ≳ \frac{(log R)^{100}}{1+(log R)^{100}} ∥g∥_{1}, where the last inequality follows from (41). This is stronger than (39), which has therefore been proved in both cases (i) and (ii).

Now let X be the union of all squares Q such that ∥g∥_{L^{1}(Q)} < R^{−50}. Then, taking (say) T = R^{10},

∥g∥_{L^{1}(X)} ≤ ∥g∥_{L^{1}(X∩D(0,T))} + ∥g∥_{L^{1}(X∩D(0,T)^{c})}
≲ R^{−50}(\frac{T}{R})^{2} + T^{−α}
≤ R^{−10}
≲ R^{−9}∥g∥_{1}

This and (39) imply that G_{∗} cannot be contained in X, which gives Claim 4.

Let Q be the square in Claim 4. If x ∈ Q, then D(x, \frac{M}{3} )^{c} is disjoint from Q̃. Accordingly, by Claim 2 and then (36) and (35), for any ϵ > 0

∥B_{M}(g)∥_{L^{∞}(Q)} ≤ Rϵ \frac{R}{M} ∥g∥_{L^{1}(Q̃^{c})} + R^{−100}∥g∥_{1}
≲ R^{1−γ+ϵ} · (log R)^{100}M^{−α}
= (log R)^{100}R^{1−γ−γα+ϵ}

If ϵ is small, then the exponent of R here is negative. It follows by Claim 3 that

∥g + B_{M}(g)∥_{L^{2}(Q)}^{2} ≳ (log R)^{−4}∥g∥_{L^{2}( ˜Q̃)}^{2}  (42)

On the other hand,

∥g + B_{M}(g)∥_{L^{2}(Q)}^{2} = ∥ − A_{M}(g)∥_{L^{2}(Q)}^{2}
≲ (MR^{−(1−β)})^{2}∥g∥_{L^{2}( ˜Q̃)}^{2} + R^{−200}
≲ R^{−η}∥g∥_{L^{2}( ˜Q̃)}^{2} + R^{−200}  (43)

where η = 2(1 − β − γ) > 0. We used Claim 1 and (35). Combining (42) and (43) we get

(log R)^{−4}∥g∥_{L^{2}( ˜Q̃)}^{2} ≲ R^{−η}∥g∥_{L^{2}( ˜Q̃)}^{2} + R^{−200}

and therefore ∥g∥_{L^{2}(Q)}^{2} ≲ R^{−199}. Since Q is good it follows that ∥g∥_{L^{1}(Q)} ≤ R^{−198}, which contradicts (37) so the proof of Theorem 2 is complete. □

4. A lower bound for the diameter of the support of multi-lattice tiles Before proving Theorem 3 we will make some further remarks about the question. If

Λ ⊂ ℝ^{d} is a lattice then let Λ^{∗} = {ξ ∈ ℝ^{d} : ξ · x ∈ ℤ ∀x ∈ Λ} be the dual lattice. We note that a function f tiles with the lattice Λ precisely when f̂ vanishes on Λ^{∗}\{0}.

The Steinhaus problem asks for a subset of ℝ^{d} that tiles with all rotations of the lattice ℤ^{d}. It seems reasonable instead to ask for a set E ⊂ ℝ^{d} that tiles with a given finite collection of lattices, say Λ_{1}, …, Λ_{n}. For lattices with volume 1 and with no nontrivial relation of the type

λ_{1} + ⋯ + λ_{n} = 0, λ_{i} ∈ Λ_{i}^{∗}

it is shown in [10] that measurable such sets exist. The existence question is of course very easy if instead of trying to tile with a subset of ℝ^{d} we try to find a function f ∈ L^{1}(ℝ^{d}) that tiles simultaneously with a given collection of lattices, that is

∑_{λ∈Λ} f(x − λ) = Const_{Λ}, for a.e. x ∈ ℝ^{d},  (44)

and for all lattices Λ in the collection under consideration. Indeed, say we are dealing with the finite collection Λ_{1}, …, Λ_{n}, assume that D_{i} is a fundamental parallelepiped for the lattice Λ_{i}, and write

f = χ_{D_{1}} ∗ ⋯ ∗ χ_{D_{n}}.  (45)

Since tiling with a lattice Λ is equivalent with the vanishing of the Fourier Transform on Λ^{∗} \ {0}, and since it is clear that χ_{D_{i}} tiles with the lattice Λ_{i}, it follows that the function f defined in (45) tiles with all Λ_{i}, i = 1, …, n.

The problem becomes nontrivial if we try to find such a function f that tiles with Λ_{1}, …, Λ_{n} which has small support. It is easy to see that, whenever the Λ_{i} have volume 1, no matter what the choice of the D_{i}, the function f defined in (45) necessarily has support of diameter at least Cn, where C depends only on the dimension.

Theorem 3 gives a lower bound for the diameter of the support of a function f ∈ L^{1}(ℝ^{d}) that tiles with a given finite number of trivially intersecting unimodular lattices.

Proof of Theorem 3

All constants below may depend only on the dimension d. We note that Λ_{1} ∩Λ_{2} = {0} implies that the lattice Λ_{1}^{∗} is uniformly distributed mod Λ_{2}^{∗}. This can be proved using Weyl’s lemma–see for example [10].

We shall make use of a theorem of Ronkin [12] and Berndtsson [2] which concerns the zero set on the real plane of an entire function of several complex variables which is of exponential type. We formulate it as a lemma:

\underline{Lemma 4.1}([12],[2]) Assume that E ⊂ ℝ^{d} is a countable set with any two points having distance at least h and let

d_{E} = lim sup_{r→∞} \begin{matrix}| & E ∩ D(0, r) & | \\ | & D(0, r) & | \end{matrix}

be its “upper density”. Assume that g : ℂ^{d} → ℂ is an entire function vanishing on E which is of exponential type

σ < A(d)h^{d−1}d_{E}.

Then g is identically 0. (Here A(d) is an explicit function of the dimension d)

When d = 1 this is classical and follows from Jensen’s formula.

Assume that f : ℝ^{d} → ℂ is as in Theorem 3. Then f̂ vanishes on (∪_{i}Λ_{i}^{∗})\{0}. Write

α = diam supp f

We may assume that suppf is contained in a disc of radius ≲ α centered at the origin, since the assumptions are unaffected by a translation of coordinates. Then f̂ can be extended to ℂ^{d} as an entire function of exponential type Cα, in fact

|f̂(x + iy)| ≤ C_{f}e^{Cα|y|}, for x + iy ∈ ℂ^{d}.

Furthermore, f̂ vanishes on

Z = ⋃_{i=1}^{n} Λ_{i}^{∗} \ {0}.

Observe that, since every lattice Λ_{i}^{∗} is uniformly distributed mod every Λ_{j}^{∗}, j ≠ i, the density of points in each Λ_{i}^{∗} which are also in some Λ_{j}^{∗} is 0 and therefore the density of the set Z is n.

In order to use Lemma 4.1 we have to select a large (in terms of upper density), well-separated subset of Z. Notice first that we can assume that for each i all points of Λ_{i}^{∗} are at least distance n^{− \frac{1}{d}} apart. For if u, v ∈ Λ_{i}^{∗} have |u − v| < n^{− \frac{1}{d}} then for a suitable constant c, the one-dimensional version of Lemma 4.1 implies that the function f̂ on the subspace E = ℂ(u − v) cannot be of exponential type ≤ cn^{\frac{1}{d}}. Note also that the assumption f̂(0) ≠ 0 precludes f̂ vanishing identically on this subspace. But f̂ restricted to E is the Fourier transform of f_{E} : E → ℂ defined by f_{E}(x) = ∫_{x+E^{⊥}} f(y) dy (here E^{⊥} is the orthogonal complement of E ∩ ℝ^{n} in ℝ^{n}). Hence α ≥ diam supp f_{E} ≥ Cn^{\frac{1}{d}}, which is what we want to conclude about α.

Suppose now that we want to extract a subset of Z whose elements are at least h distance apart, for some h > 0 to be determined later. We shall say that point x of lattice Λ_{i}^{∗} is killed by point y of lattice Λ_{j}^{∗} if |x − y| < h. Then, we define the subset Z′ of Z as those points of Z which are not killed by any point of the other lattices. This set clearly has all its points at distance at least h apart, provided that

h ≤ \frac{1}{2} min_{u,v∈Λ_{i}^{∗}} |u − v| ≤ Cn^{− \frac{1}{d}} ,  (46)

so that no point of a lattice may kill a point of the same lattice. Let us see how many points of Λ_{2}^{∗} are killed by some point of Λ_{1}^{∗}. We use the uniform distribution of Λ_{2}^{∗} mod Λ_{1}^{∗}.

Fix a fundamental parallelepiped D_{1} of Λ_{1}^{∗}. It is clear that only a fraction ρ(h) ≤ Ch^{d} of D_{1} = ℝ^{d}/Λ_{1}^{∗} has distance from 0 that is less than h (this distance is measured on the torus D_{1}). As Λ_{2}^{∗} is uniformly distributed mod Λ_{1}^{∗} the subset of points of Λ_{2}^{∗} which are killed by some point of Λ_{1}^{∗} has density ρ(h). Hence the density of those points of Λ_{2}^{∗} that are killed by any other lattice is at most (n − 1)ρ(h) ≤ Ch^{d}n. We deduce that the density of Z′ is at least (1 − Cnh^{d})n. We now choose h = cn^{− \frac{1}{d}}, for a sufficiently small constant c, to ensure that the density of Z′ is at least Cn. Applying Lemma 4.1 with g = f̂ and E = Z′ we get

α ≥ CAh^{d−1}n ≥ Cn^{\frac{1}{d}} .

□

\underline{Remark} The assumption f̂(0) ≠ 0 was used only in connection with the possibility that some Λ_{i}^{∗} contains two points at distance ≤ n^{− \frac{1}{d}}. Hence it can be dropped if we assume that this does not occur - e.g. if we assume that the lattices Λ_{i} are rotations of ℤ^{d}. However, in the general case Theorem 3 is false without this assumption. Namely, note first that for any ϵ > 0 there is a function f : ℝ^{2} → ℝ which tiles for ℤ^{2} and is supported in [−ϵ, ϵ] × [−2, 2]. For this, take f(x, y) = a(x)b(y) where b : ℝ → ℝ is a fixed function with support in [−2, 2] and orthogonal to e^{2πiky} for integer k, and a : ℝ → ℝ is supported in [−ϵ, ϵ] and is otherwise arbitrary. Next, by change of variable (x, y) → (\frac{x}{\sqrt{ϵ}}, y\sqrt{ϵ}) it follows that for any ϵ there is a function supported in D(0, 3\sqrt{ϵ}) ⊂ ℝ^{2} which tiles for some unimodular lattice. We may then convolve n rotations of this function to obtain a function supported in D(0, 3n\sqrt{ϵ}) which tiles for n unimodular lattices. Here n and ϵ run independently so we’re done.

Appendix: Proof of Lemma 3.2

We first let q be a nonnegative C_{0}^{∞} function supported in the interval [\frac{1}{2}, 2] and define a kernel J_{N} analogously to K_{N} replacing p by q:

J_{N}(x) = ∑_{ν∈ℤ^{2}} \frac{1}{|ν|}σ̂_{|ν|}(r)q(\frac{|ν|}{N})  (47)

\underline{Lemma A.1} With notation as above there is a Schwarz function ψ, such that ψ̂ vanishes in a neighborhood of the origin, and making the following true. Let r = |x|. If (say) r ≥ \frac{1}{2} and N ≥ \frac{1}{2} then

J_{N}(x) = Nr^{− \frac{1}{2}} ∑_{ν∈ℤ^{2},ν≠0}|ν|^{− \frac{1}{2}} ψ(N(|ν| − r)) + O(N^{−(1−ϵ)}r^{−1} + N^{\frac{1}{2}} r^{− \frac{3}{2}} )  (48)

for any ϵ > 0.

\underline{Remarks} In fact ψ̂ could be given quite explicitly as a linear combination of q(x) and q(−x) - this can be seen from the calculations below, but it is irrelevant for our purposes.

Note that the right side of (48) is rather large if r is small compared with N and r is close to |ν| for some ν ∈ ℤ^{2}. This contrasts with the situation in Lemma 1.1 where K_{N}(x) was negligibly small if |x| ≤ \frac{N}{2} .

\underline{Proof of Lemma A.1} First let ϕ : ℝ → ℝ be any C_{0}^{∞} function supported in the interval [\frac{1}{2}, 2]. Define

I(T, μ) = ∫_{0}^{2π} ∫_{0}^{∞} ϕ(r)e^{−2πiT r(μ−cos θ)}drdθ

We will show that there is a Schwarz function χ such that χ̂ vanishes in a neighborhood of 0 and such that, for μ > 0 and T ≥ \frac{1}{2},

I(T, μ) = T^{− \frac{1}{2}} χ(T (μ − 1)) + O(T^{− \frac{3}{2}} (1 + T |μ − 1|)^{−100})  (49)

To prove (49), note first of all that ϕ̂ is an entire function and satisfies

|ϕ̂(x + iy)| ≲ (1 + |x|)^{−200}e^{πy}

when y < 0. Making a change of variable and using contour integration,

I(T, μ) = 2 ∫_{0}^{π} ϕ̂(T (μ − cos θ))dθ
= 2 ∫_{−1}^{1} ϕ̂(T (μ − s))\frac{ds}{\sqrt{1 − s^{2}}}
= I + II

where

I = 2i ∫_{t=0}^{∞} ϕ̂(T (μ + 1 − it))\frac{dt}{\sqrt{1 − (−1 + it)^{2}}}

II = −2i ∫_{t=0}^{∞} ϕ̂(T (μ − 1 − it))\frac{dt}{\sqrt{1 − (1 + it)^{2}}}

Using that μ > 0, we have

|I| ≤ 2 ∫_{t=0}^{∞} |ϕ̂(T (μ + 1 − it))|\frac{dt}{\sqrt{t}}
≤ (1 + T (1 + μ))^{−200} ∫_{t=0}^{∞} e^{−πT t} \frac{dt}{\sqrt{t}}
≲ T^{− \frac{1}{2}} (1 + T (1 + μ))^{−200} ≲ T^{− \frac{3}{2}} (1 + T |μ − 1|)^{−100}

On the other hand,

II = \frac{−2i}{\sqrt{−i}} ∫_{t=0}^{∞} ϕ̂(T (μ − 1 − it))\frac{dt}{\sqrt{2t + it^{2}}}
= \frac{−2i}{\sqrt{−i}} ∫_{t=0}^{∞} ϕ̂(T (μ − 1 − it))\frac{dt}{\sqrt{2t}} + O(∫_{t=0}^{∞} |ϕ̂(T (μ − 1 − it))|\sqrt{t}dt) (50)

since |\frac{1}{\sqrt{2t+it^{2}}} − \frac{1}{\sqrt{2t}}| ≲ \sqrt{t}. The second term in (50) satisfies

∫_{t=0}^{∞} |ϕ̂(T (μ − 1 − it))|\sqrt{t}dt ≲ (1 + T |μ − 1|)^{−100} ∫_{t=0}^{∞} e^{−πT t}t^{\frac{1}{2}} dt
≈ T^{− \frac{3}{2}} (1 + T |μ − 1|)^{−100}

The first term in (50) is by change of variable t → T t equal to T^{− \frac{1}{2}} χ(T (μ − 1)) where

χ(x) = \frac{−2i}{\sqrt{−i}} ∫_{t=0}^{∞} ϕ̂(x − it)\frac{dt}{\sqrt{2t}}

χ is a Schwarz function, and the support of its inverse Fourier transform is contained in the support of ϕ - in fact χ̌(y) is a constant multiple of \frac{ϕ(y)}{\sqrt{y}}. This proves (49).

To prove Lemma A.1 we use the first term in the asymptotic expansion of σ̂_{1}: let r = |x|. Then

σ̂_{1}(x) = 2\sqrt{2π}r^{− \frac{1}{2}} cos(2πr − \frac{π}{4} ) + O(r^{− \frac{3}{2}} )

See e.g. [6], Theorem 7.7.14 or [14], Lemma IV.3.11 and the preceding discussion relating Bessel functions to σ̂_{1}. It follows that

|ν|^{−1}σ̂_{|ν|}(r) = 2\sqrt{2π}(r|ν|)^{− \frac{1}{2}} cos(2πr|ν| − \frac{π}{4} ) + O((r|ν|)^{− \frac{3}{2}} )  (51)

Substituting (51) into the definition of J_{N} we find that

(2\sqrt{2π})^{−1}J_{N}(x) = ∑_{ν∈ℤ^{2}}(r|ν|)^{− \frac{1}{2}} cos(2πr|ν| − \frac{π}{4} )q(\frac{|ν|}{N}) + O( ∑_{ν∈ℤ^{2}\\{0\}} q(\frac{|ν|}{N})(r|ν|)^{− \frac{3}{2}} )

The second term here is ≲ N^{\frac{1}{2}} r^{− \frac{3}{2}} since there are O(N^{2}) lattice points ν with \frac{N}{2} ≤ |ν| ≤ 2N. We rewrite the first term using the Poisson summation formula, obtaining

(2\sqrt{2π})^{−1}J_{N}(x) = r^{− \frac{1}{2}} ∑_{ν∈ℤ^{2}} re(e^{i \frac{π}{4}} ∫_{ℝ_{2}} e^{2πiν·y}|y|^{− \frac{1}{2}} e^{−2πir|y|}q(\frac{|y|}{N})dy) + O(N^{\frac{1}{2}} r^{− \frac{3}{2}} )

= N^{\frac{3}{2}} r^{− \frac{1}{2}} ∑_{ν∈ℤ^{2}} re(e^{i \frac{π}{4}} ∫_{ℝ_{2}} e^{−2πiN(r|y|−ν·y)}|y|^{− \frac{1}{2}} q(y)dy) + O(N^{\frac{1}{2}} r^{− \frac{3}{2}} )

= N^{\frac{3}{2}} r^{− \frac{1}{2}} ∑_{ν≠0} re(e^{i \frac{π}{4}} ∫_{−π}^{π} ∫_{0}^{∞} ϕ(t)e^{−2πiN|ν|t( \frac{r}{|ν|} −cos θ)}dtdθ) + O(N^{\frac{1}{2}} r^{− \frac{3}{2}} )

where ϕ(t) = t^{\frac{1}{2}} q(t). Here the second line followed by change of variables y → Ny, and on the last line we introduced polar coordinates with θ = ∠ν0y, and used that the contribution from ν = 0 is equal to re(e^{i \frac{π}{4}} N^{\frac{3}{2}} r^{− \frac{1}{2}} ϕ̂(Nr)) and therefore O((Nr)^{−100}). Now we apply (49) to the terms in the sum, with T = N|ν|, μ = \frac{r}{|ν|}. Letting ψ(t) = re(e^{i \frac{π}{4}} χ(t)) we conclude that

(2\sqrt{2π})^{−1}J_{N}(x) = N^{\frac{3}{2}} r^{− \frac{1}{2}} ∑_{ν≠0}(N|ν|)^{− \frac{1}{2}} ψ(N(|ν| − r))

+O(N^{\frac{3}{2}} r^{− \frac{1}{2}} ∑_{ν≠0}(N|ν|)^{− \frac{3}{2}} (1 + N||ν| − r|)^{−100}) + O(N^{\frac{1}{2}} r^{− \frac{3}{2}} )

The second term is ≲ r^{−2}Nϵ max(\frac{r}{N} , 1), since the contibution to the sum from terms with |ν| ≤ \frac{r}{2} is clearly very small and the contribution from |ν| ≥ \frac{r}{2} can be estimated by Lemma 3.1. (48) follows from this on replacing ψ by 2\sqrt{2π}ψ. □

\underline{Proof of Lemma 3.2} We first prove the estimate (26) with K_{N} replaced by J_{N}. We define f(t) = t^{− \frac{1}{2}} ψ(N(t − r)), with ψ as in Lemma A.1. Since ψ is in the Schwarz space it is easily seen using the product rule that for any fixed β > 0,

∫_{t=1}^{∞} t^{β}|f′(t)|dt ≲ r^{β− \frac{1}{2}}  (52)

uniformly in N ≥ \frac{1}{2} and r ≥ \frac{1}{2}. Now consider the quantity (r ≥ \frac{1}{2}, N ≥ \frac{1}{2})

∑_{ν∈ℤ^{2},ν≠0}|ν|^{− \frac{1}{2}} ψ(N(|ν| − r)) = ∫_{t=0}^{∞} f(t)dn(t)

= ∫_{t=0}^{∞} 2πtf(t)dt + ∫_{t=0}^{∞} f(t)d(n(t) − πt^{2})
= ∫_{t=0}^{∞} 2πtf(t)dt + ∫_{t=0}^{∞}(n(t) − πt^{2})f′(t)dt (53)

The first term in (53) is easily seen to be very small:

| ∫_{t=0}^{∞} 2πtf(t)dt| = 2π| ∫_{t=−r}^{∞}(t + r)^{\frac{1}{2}} ψ(Nt)dt|
= 2π| ∫_{−∞}^{∞}(t + r)^{\frac{1}{2}} ψ(Nt)dt| + O((rN)^{−100})
≲ r^{− \frac{1}{2}} ∫_{t=−∞}^{∞} |t||ψ(Nt)|dt + (rN)^{−100}
≈ r^{− \frac{1}{2}} N^{−2}

Here the second line followed since ψ is in the Schwarz space and the third line followed since (r+t)^{\frac{1}{2}} = r^{\frac{1}{2}} +O(r^{− \frac{1}{2}} |t|) and ψ̂(0) = 0. The second term in (53) is ≲ ∫_{t=1}^{∞} t^{β}|f′(t)|dt+ ∫_{t=0}^{1} t^{2}|f′(t)|dt ≲ r^{β− \frac{1}{2}} by (52) and an obvious estimate for the contribution from t < 1. Now we use (48). Let r = |x|. We’ve assumed that r ≥ N, so the error term in (48) is ≲ r^{−1}. Hence

|J_{N}(x)| ≲ Nr^{− \frac{1}{2}} | ∑_{ν∈ℤ^{2},ν≠0}|ν|^{− \frac{1}{2}} ψ(N(|ν| − r))| + r^{−1}
≲ Nr^{− \frac{1}{2}} · r^{β− \frac{1}{2}} + Nr^{− \frac{1}{2}} · r^{− \frac{1}{2}} N^{−2} + r^{−1}
≈ Nr^{−(1−β)}

When t > 0 we can express p in the form p(t) = ∑_{j≥0} q(2^{j}t) where q is supported in [\frac{1}{2}, 2]. Observe that if \frac{N}{2^{j}} < \frac{1}{2} then the sum defining J_{\frac{N}{2^{j}}} is empty. Hence |K_{N}(x)| ≤

∑_{j} |J_{\frac{N}{2^{j}}} (x)| ≲ ∑_{j} \frac{N}{2^{j}} |x|^{−(1−β)} ≲ N|x|^{−(1−β)} and the proof is complete. □

References

[1] J. Beck, \underline{On a lattice point problem of H. Steinhaus}, Studia Sci. Math. Hung. 24(1989), 263-268.

[2] B. Berndtsson, \underline{Zeros of analytic functions of several variables}, Ark. Mat. 16(1978), 251-262.

[3] H. T. Croft, \underline{Three lattice-point problems of Steinhaus}, Quart. J. Math. 33(1982), 71-83.

[4] M. Ciucu, \underline{A remark on sets having the Steinhaus property}, Combinatorica 16 (1996), 3, 321-324.

[5] C. Hooley, \underline{On the intervals between numbers that are sums of two squares}, Acta Math. 127 (1971), 280-297.

[6] L. Hörmander, The Analysis of Linear Partial Differential Operators, vol. 1, 2nd edition, Springer-Verlag, 1990.

[7] M. N. Huxley, \underline{Exponential sums and lattice points II}, Proc. London Math. Soc. 66(1993), 279-301.

[8] H. Iwaniec, C. J. Mozzochi, \underline{On the divisor and circle problems}, J. Number Theory 29(1988), 60-93.

[9] M. N. Kolountzakis, \underline{A new estimate for a problem of Steinhaus}, Intern. Math. Res. Notices 11(1996), 547-555.

[10] M. N. Kolountzakis, \underline{Multi-lattice tiles}, Intern. Math. Res. Notices 19(1997), 937-952.

[11] H. Montgomery, Ten Lectures on the Interface between Analytic Number Theory and Harmonic Analysis, CBMS Regional Conference Series in Mathematics, American Mathematical Society, 1994.

[12] L.I. Ronkin, \underline{Real sets of uniqueness for entire functions of several variables and the} \underline{completeness of the system of functions e^{i⟨λ,x⟩}}, Sibirsk. Mat. Z. 13(1972), 638-644.

[13] C. Sogge, Fourier Integrals in Classical Analysis, Cambridge University Press, 1993.

[14] E. M. Stein, G. L. Weiss, Introduction to Fourier Analysis on Euclidean Spaces, Princeton University Press, 1971.