1 Introduction
The following question, in some sense dual to Tarski’s famous plank problem [Reference Bang1, Reference Bang2, Reference McFarland, McFarland and Smith8–Reference Tarski10], was raised by Fejes Tóth [Reference Fejes Tóth5]: What is the “sparsest” sequence of points in the plane with the property that every straight line
$\ell$
comes closer than
$1$
to at least one of its points? Erdős and Pach [Reference Erdős and Pach4] answered this question by showing that for every infinite sequence of positive numbers
$(r_{i})_{i\in I}$
, one can find points
$p_{i}$
with
$|p_{i}|=r_{i}$
such that every line
$\ell$
passes at a distance less than
$1$
from
$p_{i}$
, for at least one
$i\in I$
, if and only if
$\lim _{n\rightarrow \infty }r_{n}=\infty$
and
$\sum _{i=1}^{n}(1/r_{i})=\infty$
.
Makai and Pach [Reference Makai and Pach7] proposed a closely related, but more general question. Given a family
${\mathcal{F}}$
of real functions
$f:\mathbb{R}\rightarrow \mathbb{R}$
, we say that an infinite sequence
$x_{i},i\in I$
, is
${\mathcal{F}}$
-controlling if one can choose reals
$y_{i},i\in I$
, such that the graph of any function
$f\in {\mathcal{F}}$
“comes close” to at least one of the points
$p_{i}=(x_{i},y_{i}),i\in I$
, in the sense that
$$\begin{eqnarray}|f(x_{i})-y_{i}|<1\quad \text{holds for some }i\in I.\end{eqnarray}$$
In particular, they proved that if
${\mathcal{F}}$
is the family of all linear functions
$f(x)=a_{0}+a_{1}x\;(a_{0},a_{1}\in \mathbb{R})$
, a sequence of numbers
$x_{i}\geqslant 1$
is
${\mathcal{F}}$
-controlling if and only if
$\sum _{i\in I}(1/x_{i})=\infty$
. Kupavskii and Pach [Reference Kupavskii, Pach, Akiyama, Ito, Sakai and Uno6] managed to generalize this statement to the case where
${\mathcal{F}}$
consists of all polynomials
$f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{k}x^{k}$
of degree at most
$k$
, for some positive
$k$
. In this case, the corresponding necessary and sufficient condition is
$\sum _{i\in I}(1/x_{i}^{k})=\infty$
.
The aim of this paper is to investigate the analogous problem for another interesting class of functions. Given two positive integers
$m$
and
$d$
, let
${\mathcal{L}}(m,d)$
denote the class of Lipschitz functions from
$\mathbb{R}^{m}$
to
$\mathbb{R}^{d}$
, that is, the class of functions for which there exists a constant
$C$
such that
$$\begin{eqnarray}|f(x)-f(x^{\prime })|\leqslant C|x-x^{\prime }|\quad \text{for all }x,x^{\prime }\in \mathbb{R}^{m}.\end{eqnarray}$$
If a function
$f$
satisfies the condition above with a fixed
$C>0$
, then
$f$
is called a
$C$
-Lipschitz function (or a function with Lipschitz constant
$C$
). Note that in this definition we can use any norm equivalent to the Euclidean norm. Throughout this paper, we will work with maximum norm. For convenience,
$|\cdot |$
will stand for the maximum norm, and the word “ball” will refer to a ball in the maximum norm, that is, a cube.
Definition.
Given a function
$f:\mathbb{R}^{m}\rightarrow \mathbb{R}^{d}$
and two points
$x\in \mathbb{R}^{m},y\in \mathbb{R}^{d}$
, we say that the pair
$(x,y)$
controls
$f$
if
$|f(x)-y|<1$
.
An infinite sequence
$(x_{i})_{i\in I}$
of points in
$\mathbb{R}^{m}$
is said to be
${\mathcal{L}}(m,d)$
-controlling or, in short,
$d$
-controlling if one can choose points
$(y_{i})_{i\in I}$
in
$\mathbb{R}^{d}$
such that for every
$f\in {\mathcal{L}}(m,d)$
there exists
$i$
such that
$(x_{i},y_{i})$
controls
$f$
.
It follows from the definition that replacing the condition
$|f(x)-y|<1$
by the inequality
$|f(x)-y|<\unicode[STIX]{x1D700}$
for any fixed
$\unicode[STIX]{x1D700}>0$
, does not effect whether a sequence is
$d$
-controlling. To see this, it is enough to notice that
$f\in {\mathcal{L}}(m,d)$
if and only if
$\unicode[STIX]{x1D700}f\in {\mathcal{L}}(m,d)$
, and that
$(x_{i},y_{i})$
controls
$f\in {\mathcal{L}}(m,d)$
if and only if
$|(\unicode[STIX]{x1D700}f)(x_{i})-(\unicode[STIX]{x1D700}y_{i})|<\unicode[STIX]{x1D700}$
.
Obviously, if a sequence is
$d$
-controlling, then it is also
$d^{\prime }$
-controlling for every
$1\leqslant d^{\prime }\leqslant d$
. Indeed,
$\mathbb{R}^{d^{\prime }}$
can be regarded as a subspace of
$\mathbb{R}^{d}$
, so every Lipschitz function from
$\mathbb{R}^{m}$
to
$\mathbb{R}^{d^{\prime }}$
is a Lipschitz function from
$\mathbb{R}^{m}$
to
$\mathbb{R}^{d}$
.
We solve a problem in [Reference Makai and Pach7] by giving, for any
$d$
, a necessary and sufficient condition for a sequence of points in
$\mathbb{R}$
to be
$d$
-controlling (
$m=1$
). We conjecture that this result generalizes to sequences of points in
$\mathbb{R}^{m}$
, for any
$m\leqslant d$
, but we can prove only a slightly weaker statement.
The following theorem gives a necessary condition. A somewhat weaker result was established in [Reference Makai and Pach7, Theorem 3.6A] (it is stated in the concluding remarks of this paper).
Theorem 1. Let
$m,d$
be positive integers. If a sequence of points
$(x_{i})_{i\in I}$
in
$\mathbb{R}^{m}$
is
$d$
-controlling, then we have
$$\begin{eqnarray}\sup _{n\in \mathbb{N}}\frac{|\{i\in I:|x_{i}|\leqslant n\}|}{n^{d}}=\infty .\end{eqnarray}$$
Our next result shows that for
$m=1$
, the necessary condition in Theorem 1 is also sufficient for a sequence of points in
$\mathbb{R}$
to be
$d$
-controlling.
Theorem 2. Let
$d$
be a positive integer. A sequence of points
$(x_{i})_{i\in I}$
in
$\mathbb{R}$
is
$d$
-controlling if and only if
$$\begin{eqnarray}\sup _{n\in \mathbb{N}}\frac{|\{i\in I:|x_{i}|\leqslant n\}|}{n^{d}}=\infty .\end{eqnarray}$$
For
$m>d$
, the condition in Theorems 1 and 2 is necessary, but not sufficient for a sequence in
$\mathbb{R}^{m}$
to be
$d$
-controlling. To see this, observe that the sequence
$(x_{i})_{i\in I}$
consisting of all integer points in
$\mathbb{R}^{m}$
satisfies the condition for all
$d<m$
. Nevertheless, this sequence is not even
$1$
-controlling. Indeed, for any function
$h:I\rightarrow \{-1,1\}$
, there exists a 2-Lipschitz function
$f_{h}:\mathbb{R}^{m}\rightarrow \mathbb{R}$
for which
$f(x_{i})=h(i)$
for all
$i\in I$
. For any sequence of reals
$(y_{i})$
, choose
$\bar{h}(i)\in \{-1,1\}$
so that
$|\bar{h}(i)-y_{i}|\geqslant 1$
for every
$i\in I$
, and notice that
$f_{\bar{h}}$
is not controlled by any pair
$(x_{i},y_{i})$
.
However, we believe that for
$m\leqslant d$
, the above condition is not only necessary but also sufficient for a sequence in
$\mathbb{R}^{m}$
to be
$d$
-controlling.
Conjecture 3. Let
$m,d$
be positive integers,
$m\leqslant d$
. A sequence of points
$(x_{i})_{i\in I}$
in
$\mathbb{R}^{m}$
is
$d$
-controlling if and only if
$$\begin{eqnarray}\sup _{n\in \mathbb{N}}\frac{|\{i\in I:|x_{i}|\leqslant n\}|}{n^{d}}=\infty .\end{eqnarray}$$
We cannot prove this conjecture for
$m>1$
, but we can formulate a slightly stronger condition that is already sufficient for a sequence to be
$d$
-controlling, provided that
$m\leqslant d$
.
Theorem 4. Let
$m,d$
be positive integers,
$m\leqslant d$
. Suppose that a sequence of points
$(x_{i})_{i\in I}$
in
$\mathbb{R}^{m}$
satisfies the following condition for every positive
$\unicode[STIX]{x1D6FC}$
: the set of all points
$x\in \mathbb{R}^{m}$
with
$$\begin{eqnarray}|\{i\in I:|x_{i}-x|<\unicode[STIX]{x1D6FC}\}|<|x|^{d-m}\end{eqnarray}$$
is bounded. Then the sequence
$(x_{i})_{i\in I}$
is
$d$
-controlling.
For any
$\unicode[STIX]{x1D6FD}>\unicode[STIX]{x1D6FC}>0$
, the region
$\{x\in \mathbb{R}^{m}:\unicode[STIX]{x1D6FD}\leqslant |x|\leqslant 2\unicode[STIX]{x1D6FD}\}$
contains at least some positive constant
$c=c(m)$
times
$(\unicode[STIX]{x1D6FD}/\unicode[STIX]{x1D6FC})^{m}$
pairwise disjoint balls of radius
$\unicode[STIX]{x1D6FC}$
(that is, cubes of side length
$2\unicode[STIX]{x1D6FC}$
, in the maximum norm). If the condition of the last theorem is satisfied, then each of these balls contains at least
$\unicode[STIX]{x1D6FD}^{d-m}$
points
$x_{i}$
, provided that
$\unicode[STIX]{x1D6FD}>\unicode[STIX]{x1D6FD}(\unicode[STIX]{x1D6FC})$
is sufficiently large. Thus, in this case,
$$\begin{eqnarray}|\{i\in I:|x_{i}|\leqslant 2\unicode[STIX]{x1D6FD}\}|\geqslant c(\unicode[STIX]{x1D6FD}/\unicode[STIX]{x1D6FC})^{m}\unicode[STIX]{x1D6FD}^{d-m}=(c/\unicode[STIX]{x1D6FC}^{m})\unicode[STIX]{x1D6FD}^{d}.\end{eqnarray}$$
Letting
$\unicode[STIX]{x1D6FC}\rightarrow 0$
, we obtain that the condition in Conjecture 3 also holds. Roughly speaking, the condition in Theorem 4 is equivalent to the condition in Conjecture 3 for “uniformly distributed” sequences
$x_{i}$
, but the two conditions differ when the density of the point sequence depends “unevenly” on the location. We remark that our Theorem 1 differs from [Reference Makai and Pach7, Theorem 3.6A] in the same sense: for “uniform” sequences the two statements are equivalent, but in general they are not.
The exponent of
$|x|$
in the right-hand side of the displayed formula in Theorem 4 cannot be replaced by any smaller number, as follows from Theorem 1. Theorem 4 disproves a conjecture from [Reference Makai and Pach7]; see the Remark at the end of §4.
It is easy to see that the sufficient condition stated in Theorem 4 is not necessary even if
$m=1$
and
$d$
is arbitrary. The sequence of points consisting of
$k2^{kd}$
copies of
$2^{k}\in \mathbb{R}$
for every positive integer
$k$
, satisfies the condition of Theorem 2 and is, therefore,
$d$
-controlling. On the other hand, apart from those
$x\in \mathbb{R}$
that are closer than
$\unicode[STIX]{x1D6FC}$
to some power of
$2$
, every
$x\not =0$
satisfies the inequality in Theorem 4. The set of these
$x$
is unbounded, thus Theorem 4 is not applicable. Since every
$d$
-controlling sequence of points in
$\mathbb{R}$
can be regarded as a
$d$
-controlling sequence of points in
$\mathbb{R}^{m}$
for any
$m>1$
, we obtain that the sufficient condition stated in Theorem 4 is not necessary for a sequence to be
$d$
-controlling, for any values of
$m$
and
$d$
.
Nevertheless, for some “natural” classes of sequences, the two conditions are equivalent, that is, Conjecture 3 holds. For instance, let
$m\leqslant d$
and
$c>0$
be fixed, and consider the sequence of all points
$(x_{i})_{i\in I}$
in
$\mathbb{R}^{m}$
whose each coordinate is the
$c$
th power of some natural number. It is easy to see that this sequence satisfies both the condition in Conjecture 3 and the one in Theorem 4 if
$c<m/d$
and neither of them, otherwise.
Concerning the case
$m>d$
, we have a conjecture that (roughly speaking) states that a sequence in
$\mathbb{R}^{m}$
is
$d$
-controlling if and only if there is a
$d$
-dimensional Lipschitz surface passing through a subset of its points that already guarantees this property. The precise statement can be formulated for every
$m$
and
$d$
, but for
$m\leqslant d$
the conjecture is obviously true.
Conjecture 5. Let
$m,d$
be positive integers. A sequence of points
$(x_{i})_{i\in I}$
in
$\mathbb{R}^{m}$
is
$d$
-controlling if and only if there exist a Lipschitz map
$g:\mathbb{R}^{d}\rightarrow \mathbb{R}^{m}$
and a
$d$
-controlling sequence of points
$(x_{i}^{\prime })_{i\in I^{\prime }}$
in
$\mathbb{R}^{d}$
with
$I^{\prime }\subseteq I$
such that
$g(x_{i}^{\prime })=x_{i}$
for all
$i\in I^{\prime }$
.
The “if” part of the conjecture is trivially true. Indeed, suppose that a sequence
$(y_{i})_{i\in I^{\prime }}$
in
$\mathbb{R}^{d}$
shows that
$(x_{i}^{\prime })_{i\in I^{\prime }}$
is
$d$
-controlling. Then the same sequence also shows that the sequence of points
$(x_{i})_{i\in I^{\prime }}$
in
$\mathbb{R}^{m}$
is also
$d$
-controlling. To see this, take any Lipschitz function
$f:\mathbb{R}^{m}\rightarrow \mathbb{R}^{d}$
, and observe that
$f(g(x)):\mathbb{R}^{d}\rightarrow \mathbb{R}^{d}$
is also a Lipschitz function. Thus, we have
$|f(x_{i})-y_{i}|=|f(g(x_{i}^{\prime }))-y_{i}|<1$
for some
$i\in I^{\prime }$
.
The “only if” part of the conjecture evidently holds for
$m\leqslant d$
. Indeed, choose
$g:\mathbb{R}^{d}\rightarrow \mathbb{R}^{m}$
to be the projection to the subspace induced by the first
$m$
coordinates, set
$I^{\prime }=I$
and
$x_{i}^{\prime }=x_{i}\times 0^{d-m}\in \mathbb{R}^{d}$
for every
$i\in I$
. The important part of the conjecture is the “only if” direction where
$m>d$
.
The proofs of Theorems 1, 2, and 4, are presented in §§2, 3, and 4, respectively.
2 Proof of Theorem 1
As mentioned in the introduction, a somewhat weaker statement (Theorem 3.6A) was proved in [Reference Makai and Pach7]. Here we extend the proof to the general case.
Consider a sequence
$(x_{i})_{i\in I}$
that violates the condition in the theorem, that is, for which
$$\begin{eqnarray}\sup _{n\in \mathbb{N}}\frac{|\{i\in I:|x_{i}|\leqslant n\}|}{n^{d}}<\infty .\end{eqnarray}$$
Given any sequence
$(y_{i})_{i\in I}$
of points in
$\mathbb{R}^{d}$
, we have to find a Lipschitz function
$f\in {\mathcal{L}}(m,d)$
from
$\mathbb{R}^{m}$
to
$\mathbb{R}^{d}$
that is not controlled by any of the pairs
$(x_{i},y_{i}),i\in I$
. We will find such a function
$f$
with the property that
$f(x)=g(|x|)$
for some Lipschitz function
$g:\mathbb{R}\rightarrow \mathbb{R}^{d}$
. Then it is enough to guarantee that no pair
$(|x_{i}|,y_{i})$
controls
$g$
. In other words, it is enough to prove the statement for
$m=1$
.
For technical reasons, we deal with the indices
$i$
for which
$x_{i}=0$
, separately. Let
$k$
denote the number of such indices. It follows from the assumption that
$k$
is finite. Suppose without loss of generality that the index set
$I$
is the set of integers larger than
$-k$
and that
$|x_{i}|$
is monotonically increasing in
$i$
with
$\lim _{i\rightarrow \infty }|x_{i}|=\infty$
. Thus, we have
$$\begin{eqnarray}\left\{\begin{array}{@{}ll@{}}x_{i}=0\quad & \text{if}~i\leqslant 0,\\ |x_{i}|>0\quad & \text{if}~i>0.\end{array}\right.\end{eqnarray}$$
Let
$\unicode[STIX]{x1D6FC}=\sup _{i>0}(i/|x_{i}|^{d})$
and
$\unicode[STIX]{x1D6FD}=2\unicode[STIX]{x1D6FC}^{1/d}$
. For
$\unicode[STIX]{x1D707}\in \mathbb{R}$
, denote
$\lfloor \unicode[STIX]{x1D707}\rfloor$
and
$\lceil \unicode[STIX]{x1D707}\rceil$
the lower and the upper integer part of
$\unicode[STIX]{x1D707}$
, respectively. Define a real number
$\unicode[STIX]{x1D707}:=\max _{j>0}(\lceil |x_{j}|\rceil ^{d}/|x_{j}|^{d})$
. It is easy to see that
$\unicode[STIX]{x1D707}$
is a finite number bigger than
$1$
. Notice that
$\unicode[STIX]{x1D6FC}<\infty$
and, hence,
$\unicode[STIX]{x1D6FD}<\infty$
, because
$$\begin{eqnarray}\unicode[STIX]{x1D6FC}=\sup _{i>0}\frac{i}{|x_{i}|^{d}}\leqslant \sup _{i>0}\frac{|\{j\in I:|x_{j}|\leqslant |x_{i}|\}|}{|x_{i}|^{d}}\leqslant \unicode[STIX]{x1D707}\sup _{n\in \mathbb{N}}\frac{|\{j\in I:|x_{j}|\leqslant n\}|}{n^{d}}<\infty .\end{eqnarray}$$
In what follows, we define a nested sequence
${\mathcal{L}}_{0}\supseteq {\mathcal{L}}_{1}\supseteq {\mathcal{L}}_{2}\supseteq \cdots \,$
of families of
$\unicode[STIX]{x1D6FD}$
-Lipschitz functions from
$\mathbb{R}$
to
$\mathbb{R}^{d}$
, we show that their intersection is non-empty, and any function
$g\in \bigcap _{i\geqslant 0}{\mathcal{L}}_{i}$
meets the requirements.
Fix a point
$y\in \mathbb{R}^{d}$
such that
$|y-y_{j}|>1$
for every
$j\leqslant 0$
. Let
${\mathcal{L}}_{0}\subset {\mathcal{L}}(1,d)$
denote the family of all
$\unicode[STIX]{x1D6FD}$
-Lipschitz functions
$g:\mathbb{R}\rightarrow \mathbb{R}^{d}$
with
$g(0)=y$
. By the choice of
$y$
, no function
$g\in {\mathcal{L}}_{0}$
is controlled by any of the points
$(|x_{j}|,y_{j})$
with
$j\leqslant 0$
.
The case
$d=1$
.
For every
$i>0$
, let
${\mathcal{L}}_{i}$
be defined as the set of all functions in
${\mathcal{L}}_{0}$
that are not controlled by any of the pairs
$(|x_{j}|,y_{j})$
with
$j\leqslant i$
, and let
$$\begin{eqnarray}D_{i}=\{g(|x_{i}|):g\in {\mathcal{L}}_{i}\}.\end{eqnarray}$$
See Figure 1, for an illustration of the case
$d=1$
. (The points
$(x_{i},y_{i})$
are marked red. If a
$\unicode[STIX]{x1D6FD}$
-Lipschitz function belongs to
${\mathcal{L}}_{i}$
, its graph cannot intersect the yellow region incident to
$(x_{i},y_{i})$
.)
We establish a lower bound for the Lebesgue measures
$\unicode[STIX]{x1D707}(D_{i})$
of the sets
$D_{i}$
.
Claim 2.1. For every
$i\geqslant 0$
, we have
$\unicode[STIX]{x1D707}(D_{i})\geqslant 2^{d+1}\unicode[STIX]{x1D6FC}|x_{i}|^{d}-2^{d}i$
.
Proof. By induction on
$i$
. For
$i=0$
, we have
$D_{0}=\{y\}$
, which is a non-empty set of zero measure. It follows from the definition of
$\unicode[STIX]{x1D6FC}$
that the bound in Claim 2.1 is strictly positive for every
$i>0$
. Assume that we have already verified the Claim for some
$i\geqslant 0$
, and we want to prove it for
$i+1$
.
Let
$D^{\prime }=\{g(|x_{i+1}|):g\in {\mathcal{L}}_{i}\}$
. Clearly,
$D^{\prime }$
can be obtained as the Minkowski sum of
$D_{i}$
and the ball
$B_{r}=B_{r}(0)$
of radius
$r=\unicode[STIX]{x1D6FD}(|x_{i+1}|-|x_{i}|)$
around the origin. On the other hand, we have
$D_{i+1}=D^{\prime }\setminus B_{1}(y_{i+1})$
, where
$B_{1}(y_{i+1})$
denotes the ball of radius
$1$
around
$y_{i+1}$
. Therefore,
$$\begin{eqnarray}\unicode[STIX]{x1D707}(D_{i+1})\geqslant \unicode[STIX]{x1D707}(D^{\prime })-\unicode[STIX]{x1D707}(B_{1}(y_{i+1}))=\unicode[STIX]{x1D707}(D^{\prime }+B_{r})-\unicode[STIX]{x1D707}(B_{1}(y_{i+1})).\end{eqnarray}$$
By the Brunn–Minkowski inequality, we have
$$\begin{eqnarray}\unicode[STIX]{x1D707}(D^{\prime }+B_{r})\geqslant (\unicode[STIX]{x1D707}^{1/d}(D_{i})+\unicode[STIX]{x1D707}^{1/d}(B_{r}))^{d}.\end{eqnarray}$$
Combining the last two inequalities,
$$\begin{eqnarray}\unicode[STIX]{x1D707}(D_{i+1})\geqslant (\unicode[STIX]{x1D707}^{1/d}(D_{i})+\unicode[STIX]{x1D707}^{1/d}(B_{r}))^{d}-\unicode[STIX]{x1D707}(B_{1}(y_{i+1})).\end{eqnarray}$$
As we use the maximum norm, we have
$\unicode[STIX]{x1D707}(B_{1}(y_{i+1}))=2^{d}$
and
$\unicode[STIX]{x1D707}(B_{r})=2^{d}r^{d}$
. Using the inductive hypothesis, we get the following chain of implications:
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D707}(D_{i+1}) & {\geqslant} & \displaystyle 2^{d+1}\unicode[STIX]{x1D6FC}|x_{i+1}|^{d}-2^{d}(i+1)\quad \Leftarrow \nonumber\\ \displaystyle ((2^{d+1}\unicode[STIX]{x1D6FC}|x_{i}|^{d}-2^{d}i)^{1/d}+2r)^{d}-2^{d} & {\geqslant} & \displaystyle 2^{d+1}\unicode[STIX]{x1D6FC}|x_{i+1}|^{d}-2^{d}(i+1)\quad \Leftrightarrow \nonumber\\ \displaystyle ((2\unicode[STIX]{x1D6FC}|x_{i}|^{d}-i)^{1/d}+r)^{d} & {\geqslant} & \displaystyle 2\unicode[STIX]{x1D6FC}|x_{i+1}|^{d}-i\qquad \qquad \quad \quad \Leftrightarrow \nonumber\\ \displaystyle \unicode[STIX]{x1D6FD}(|x_{i+1}|-|x_{i}|) & {\geqslant} & \displaystyle (2\unicode[STIX]{x1D6FC}|x_{i+1}|^{d}-i)^{1/d}-(2\unicode[STIX]{x1D6FC}|x_{i}|^{d}-i)^{1/d},\nonumber\end{eqnarray}$$
where
$\unicode[STIX]{x1D6FD}=2\unicode[STIX]{x1D6FC}^{1/d}$
, as before. By the definition of
$\unicode[STIX]{x1D6FC}$
, we have
$2\unicode[STIX]{x1D6FC}x^{d}-i\geqslant \unicode[STIX]{x1D6FC}x^{d}$
for every
$x\geqslant |x_{i}|$
. Consider the function
$f(x):=(2\unicode[STIX]{x1D6FC}x^{d}-i)^{1/d}$
. Then
$$\begin{eqnarray}f^{\prime }(x)=\frac{1}{d}2\unicode[STIX]{x1D6FC}d\frac{x^{d-1}}{(2\unicode[STIX]{x1D6FC}x^{d}-i)^{(d-1)/d}}\leqslant 2\unicode[STIX]{x1D6FC}\frac{x^{d-1}}{(\unicode[STIX]{x1D6FC}x^{d})^{(d-1)/d}}=2\unicode[STIX]{x1D6FC}^{1/d},\end{eqnarray}$$
for every
$x\geqslant |x_{i}|$
. Therefore, the last inequality of the chain holds, and so does the first one, as claimed.◻
In particular, it follows from Claim 2.1 that
$D_{i}\not =\emptyset$
and, hence,
${\mathcal{L}}_{i}$
is not empty for every
$i\geqslant 0$
. To complete the proof of Theorem 1, it is enough to note that the set
${\mathcal{L}}_{0}$
is compact in the pointwise topology. Therefore,
$\bigcap _{i\geqslant 0}{\mathcal{L}}_{i}\neq \emptyset$
. By definition, no function
$g\in \bigcap _{i\geqslant 0}{\mathcal{L}}_{i}$
is controlled by any pair
$(|x_{i}|,y_{i})$
, as required.
3 Proof of Theorem 2
The “only if” part of the theorem is a special case of Theorem 1. Thus, we have to prove only the “if” part.
Let
$(x_{i})_{i\in \mathbb{N}}$
be a sequence of real numbers satisfying the “density condition”
$$\begin{eqnarray}\sup _{n\in \mathbb{N}}\frac{|\{i\in I:|x_{i}|\leqslant n\}|}{n^{d}}=\infty .\end{eqnarray}$$
Split this sequence into two sequences, one consisting of the non-negative numbers and the other consisting of the negative ones. At least one of these two sequences must satisfy the above density condition, so we can assume without loss of generality that, say,
$x_{i}\geqslant 0$
for all
$i$
. If
$(x_{i})_{i\in \mathbb{N}}$
has a convergent subsequence
$(x_{i_{j}})_{j\in \mathbb{N}}\rightarrow x$
, as
$j\rightarrow \infty$
, then choose any sequence of points
$(y_{j})_{j\in \mathbb{N}}$
, everywhere dense in
$\mathbb{R}^{d}$
. Obviously, every Lipschitz function
$f:\mathbb{R}\rightarrow \mathbb{R}^{d}$
is controlled by infinitely many pairs
$(x_{i_{j}},y_{j})$
. Therefore, we can assume without loss of generality that
$(x_{i})_{i\in \mathbb{N}}$
is an increasing sequence of non-negative numbers, tending to infinity.
We need a simple statement about a finite portion of the sequence
$(x_{i})$
.
Fix a positive integer
$j$
. Let
${\mathcal{L}}_{j}$
denote the family of
$j$
-Lipschitz functions
$f:\mathbb{R}\rightarrow \mathbb{R}^{d}$
with
$|f(0)|\leqslant j$
. (Note that this deviates from the definition of
${\mathcal{L}}_{j}$
used in the previous section.) We also fix
$n\in \mathbb{N}$
. Let
$k=k(j,n)=(j(n+1)+1)^{d}$
, and assume that
$x_{i}\leqslant n$
for
$1\leqslant i\leqslant k$
.
Since we use the maximum norm in
$\mathbb{R}^{d}$
, the ball (cube)
$B_{r}$
of radius
$r=j(n+1)$
around the origin can be uniquely partitioned into
$k$
balls of radius
$r^{\prime }=r/(r+1)<1$
. Let the centers of these balls be denoted by
$z_{i}$
and the balls themselves by
$B_{r^{\prime }}(z_{i}),\;1\leqslant i\leqslant k$
. Index the centers
$z_{i}$
decreasingly with respect to the lexicographic order. For every
$i,1\leqslant i\leqslant k$
, set
$$\begin{eqnarray}y_{i}=z_{i}-j(n-x_{i})v,\end{eqnarray}$$
where
$v$
is the all-
$1$
vector in
$\mathbb{R}^{d}$
. See Figure 2, which depicts the case
$d=1$
.
Illustration for the proof of Theorem 2. Choosing the points
$y_{i}$
.
Claim 3.1. Any function
$f\in {\mathcal{L}}_{j}$
is controlled by one of the pairs
$(x_{i},y_{i}),\;1\leqslant i\leqslant k$
.
Proof. Let
$f$
be an arbitrary element of
${\mathcal{L}}_{j}$
. Notice that the function
$g(x)=f(x)+j(n-x)v$
is monotonically decreasing in all of its coordinates, and that
$g(x)\in B_{r}$
for every
$x\in [0,n]$
.
Consider the set
$S$
of all indices
$1\leqslant i\leqslant k$
such that
$g(x_{i})$
is contained in a ball
$B_{r^{\prime }}(z_{i^{\prime }})$
for some
$1\leqslant i^{\prime }\leqslant i$
. As
$g(x_{k})$
is in
$B_{r}$
, it belongs to a ball
$B_{r^{\prime }}(z_{i^{\prime }})$
for some
$1\leqslant i^{\prime }\leqslant k$
. Therefore,
$k\in S$
, so that the set
$S$
is not empty. Let
$i_{0}$
denote the smallest element of
$S$
.
Then we have
$g(x_{i_{0}})\in B_{r^{\prime }}(z_{i_{0}})$
. Indeed, otherwise
$g(x_{i_{0}})\in B_{r^{\prime }}(z_{i^{\prime }})$
for some index
$i^{\prime }<i_{0}$
. Thus,
$i_{0}>1$
. Using the monotonicity of
$g$
and the monotonicity of the sequences
$(x_{i})_{1\leqslant i\leqslant k}$
and
$(z_{i})_{1\leqslant i\leqslant k}$
, we obtain that
$g(x_{i_{0}-1})\in B_{r^{\prime }}(z_{i^{\prime \prime }})$
for some
$i^{\prime \prime }\leqslant i^{\prime }\leqslant i_{0}-1$
, contradicting the minimality of
$i_{0}$
. Hence,
$$\begin{eqnarray}1>r^{\prime }\geqslant |g(x_{i_{0}})-z_{i_{0}}|=|f(x_{i_{0}})-y_{i_{0}}|.\end{eqnarray}$$
This means that
$(x_{i_{0}},y_{i_{0}})$
controls
$f$
, as claimed.◻
Now we can easily finish the proof of Theorem 2. We need to show that the sequence
$(x_{i})_{i\in \mathbb{N}}$
is
$d$
-controlling. To control all functions in
${\mathcal{L}}_{j}$
for a fixed
$j$
, pick an
$n=n(j)$
such that for at least
$k=(j(n+1)+1)^{d}$
distinct indices
$i$
we have
$x_{i}\leqslant n$
. It follows from the density condition that such an
$n$
exists.
By Claim 3.1, we can choose
$y_{i}$
for
$k$
distinct indices
$i$
such that every function in
${\mathcal{L}}_{j}$
is controlled by one of the
$k$
pairs
$(x_{i},y_{i})$
. Repeat this step successively for
$j=1,2,\ldots \,$
, making sure that we always use pairwise disjoint sets of indices. This is possible, because removing any finite number of elements from
$(x_{i})_{i\in \mathbb{N}}$
, the remaining sequence still satisfies the density condition. Since every Lipschitz function
$\mathbb{R}\rightarrow \mathbb{R}^{d}$
belongs to one of the classes
${\mathcal{L}}_{j}$
, after completing the above process for all
$j\in \mathbb{N}$
, all Lipschitz functions
$\mathbb{R}\rightarrow \mathbb{R}^{d}$
will be controlled by one of the pairs
$(x_{i},y_{i})$
. This proves Theorem 2.
4 Proof of Theorem 4
As in the proof of Theorem 2, for every positive integer
$j$
,
${\mathcal{L}}_{j}$
denotes the family of
$j$
-Lipschitz functions
$f:\mathbb{R}^{m}\rightarrow \mathbb{R}^{d}$
with
$|f(0)|\leqslant j$
. As we did in that proof, we fix
$j$
and we show that one can control
${\mathcal{L}}_{j}$
using only finitely many points
$x_{i}$
. To complete the proof of Theorem 4, we perform this step for
$j=1,2,\ldots \,$
, sequentially, observing that the density condition in the theorem continues to hold even if we delete any finite number of points
$x_{i}$
from our sequence.
The proof of Theorem 4 is based on a topological lemma. We consider a continuously moving set
$D$
that leaves a ball
$B\subset R^{d}$
. By continuity, each point of
$D$
must cross the boundary of the ball. Using Brouwer’s fixed point theorem, we find a point
$z\in D$
that crosses the boundary at a point with a special property. See Figure 3, for an illustration. The color gradation distinguishes different points of
$D$
, that is, points of the same color indicate the trajectory of a point, as it progresses in time
$t$
.
Finding the fixed point: the diagram of the maps we use.
Lemma 4.1. Let
$d$
be a positive integer. Let
$B$
denote a closed ball of positive radius around the origin in
$\mathbb{R}^{d}$
, and let
$S$
stand for the boundary of
$B$
. Let
$J=[t_{0},t_{1}]$
be a closed interval on the real line, let
$D$
be an arbitrary topological space, and let
$f:D\times J\rightarrow \mathbb{R}^{d}$
and
$g:B\rightarrow D$
be continuous functions.
If
$f(z,t_{0})\in B\setminus S$
and
$f(z,t_{1})\notin B$
for all
$z\in D$
, then there exist
$z\in D$
and
$t\in (t_{0},t_{1})$
such that
$f(z,t)\in S$
and
$g(f(z,t))=z$
.
Proof. Denote
$l$
the radius of
$B$
. Let
$B^{\prime }=B\times J\subset \mathbb{R}^{d+1}$
, and let
$h:$
$B^{\prime }\rightarrow \mathbb{R}^{d+1}$
be defined as
$h(y,t)=(y^{\prime },t^{\prime })$
, where
$y^{\prime }=f(g(y),t)$
and
$t^{\prime }=t-|y^{\prime }|+l$
. Let
$c:\mathbb{R}^{d+1}\rightarrow B^{\prime }$
be a coordinate-wise retraction; to be specific, let
$c(y,t)=(\min (1,l/|y|)\cdot y,\min (t_{1},\max (t_{0},t)))$
. Finally, let
$\bar{h}:B^{\prime }\rightarrow B^{\prime }$
be the composition of these functions:
$\bar{h}(y,t)=c(h(y,t))$
.
Clearly,
$\bar{h}$
is continuous and
$B^{\prime }$
is homeomorphic to the
$(d+1)$
-dimensional ball. Thus, we can apply Brouwer’s fixed point theorem to conclude that there exists
$(y,t)\in B^{\prime }$
with
$\bar{h}(y,t)=(y,t)$
. Let
$z=g(y)$
and
$(y^{\prime },t^{\prime })=h(y,t)$
.
If
$t=t_{0}$
, then the second coordinate of
$c(y^{\prime },t^{\prime })$
equals
$t_{0}$
. Hence, either we have
$t^{\prime }=t_{0}$
or
$t^{\prime }$
was retracted to
$t_{0}$
from the left. Since
$t^{\prime }\leqslant t$
, we have
$|y^{\prime }|\geqslant l$
, and thus
$f(z,t_{0})\notin B\setminus S$
, contradicting our assumption.
Analogously, if
$t=t_{1}$
, then
$t^{\prime }\geqslant t$
, so
$|y^{\prime }|\leqslant l$
, implying that
$f(z,t_{1})\in B$
, which is again a contradiction.
Consequently, we must have
$t_{0}<t<t_{1}$
. Using the fact that
$c$
is a retraction, we obtain that
$t^{\prime }=t$
, so
$|y^{\prime }|=l$
and
$y^{\prime }=f(z,t)\in S$
. We must also have
$y^{\prime }=y$
, which implies that
$g(f(z,t))=g(y)=z$
.◻
To apply the lemma, we think of
$\mathbb{R}^{m}$
as a product space
$\mathbb{R}^{m-1}\times \mathbb{R}$
, with the last coordinate considered as time. Let
$D\subset \mathbb{R}^{m-1}$
and
$B\subset \mathbb{R}^{d}$
be balls, let
$J=[t_{0},t_{1}]$
be an interval, and let
$g:B\rightarrow D$
a linear map (see Figure 3). Consider any
$j$
-Lipschitz function
$f:\mathbb{R}^{m}\rightarrow \mathbb{R}^{d}\;(m\leqslant d)$
, and focus our attention on the restriction of
$f$
to
$D\times J$
. In order to apply Lemma 4.1, we choose
$B$
large enough to make sure that
$f(z,t_{0})$
lies in the interior of
$B$
for all
$z\in D$
. By the lemma, we can either find
$z\in D$
such that
$x=(z,t_{1})$
satisfies
$y=f(x)\in B$
, or there exists
$x=(z,t)\in D\times J$
such that
$y=f(x)$
belongs to the boundary of
$B$
and
$g(y)=z$
. Our goal is to find sufficiently many indices
$i\in I$
with
$x_{i}\in D\times J$
, and to assign appropriate values
$y_{i}$
to them, so that for every conceivable pair
$(x,y)$
provided by the lemma we can find a pair
$(x_{i},y_{i})$
that is close to it. Specifically, if we have
$|x-x_{i}|<1/2j$
and
$|y-y_{i}|<{\textstyle \frac{1}{2}}$
for some
$i$
, then
$f(x)=y$
implies that the pair
$(x_{i},y_{i})$
controls
$f\in {\mathcal{L}}_{j}$
. Next we spell out the details of the proof.
Proof of Theorem 4.
Let
$m\leqslant d$
and let
$(x_{i})_{i\in I}$
be a sequence of points in
$\mathbb{R}^{m}$
satisfying the density condition in the theorem. Let us fix
$j\in \mathbb{N}$
. As we have pointed out earlier, it is sufficient to show that we can select finitely many indices
$i\in I$
and assign to them suitable points
$y_{i}\in \mathbb{R}^{d}$
such that every function in
${\mathcal{L}}_{j}$
is controlled by at least one of the pairs
$(x_{i},y_{i})$
.
Set
$\unicode[STIX]{x1D716}=1/(8j+8)$
and choose a positive integer
$c$
with
$c^{m}>4d/\unicode[STIX]{x1D716}^{d-m}$
. Using the density condition in the theorem with
$\unicode[STIX]{x1D6FC}=\unicode[STIX]{x1D716}/c$
, we obtain that there exists
$t_{0}>j+1$
such that
$$\begin{eqnarray}|\{i\in I:|x_{i}-x|<\unicode[STIX]{x1D6FC}\}|\geqslant |x|^{d-m}\end{eqnarray}$$
holds for every
$x\in \mathbb{R}^{m}$
with
$|x|\geqslant t_{0}-2\unicode[STIX]{x1D716}$
. Set
$l=\lfloor jt_{0}+j\rfloor +1<(j+1)t_{0}$
. The density condition we really need for our argument is
$$\begin{eqnarray}|\{i\in I:|x_{i}-x|<\unicode[STIX]{x1D716}\}|\geqslant 4d(2l)^{d-m},\end{eqnarray}$$
which holds for every
$|x|\geqslant t_{0}-\unicode[STIX]{x1D716}$
, since the ball of radius
$\unicode[STIX]{x1D716}$
around
$x$
can be split into
$c^{m}$
internally disjoint balls of radius
$\unicode[STIX]{x1D6FC}$
, each containing at least
$(|x|-\unicode[STIX]{x1D716})^{d-m}$
points
$x_{i}$
in their interior. This adds up to total of
$c^{m}(t_{0}-2\unicode[STIX]{x1D716})^{d-m}>4d(2l)^{d-m}$
, as required. Finally, set
$t_{1}>t_{0}$
such that
$$\begin{eqnarray}|\{i\in I:|x_{i}-x|<\unicode[STIX]{x1D716}\}|\geqslant 4d(2l)^{d-m}+(2l)^{d}\end{eqnarray}$$
holds for all
$|x|\geqslant t_{1}-\unicode[STIX]{x1D716}$
. The existence of such a value
$t_{1}$
follows easily from the density condition on the sequence
$(x_{i})$
, because for every sufficiently large
$|x|$
, the left-hand side of the above inequality is at least
$|x|^{d-m}$
, while its right-hand side is a constant.
Let
$D=\{z\in \mathbb{R}^{m-1}:|z|\leqslant t_{0}\}$
be the ball of radius
$t_{0}$
around the origin in
$\mathbb{R}^{m-1}$
, let
$J=[t_{0},t_{1}]$
, let
$B=\{y\in \mathbb{R}^{d}:|y|\leqslant l\}$
be the ball of radius
$l$
around the origin in
$\mathbb{R}^{d}$
, and let
$S=\{y\in \mathbb{R}^{d}\,:\,|y|=l\}$
denote the sphere bounding
$B$
. Define a linear map
$g:B\rightarrow D$
by setting
$$\begin{eqnarray}g(y_{1},\ldots ,y_{d})=\frac{t_{0}}{2l}(y_{1}-y_{m},y_{2}-y_{m},\ldots ,y_{m-1}-y_{m}).\end{eqnarray}$$
We identify
$\mathbb{R}^{m}$
with
$\mathbb{R}^{m-1}\,\times \,\mathbb{R}$
and will use the notation
$(z,t)\,\in \,\mathbb{R}^{m}$
for
$z\,\in \,\mathbb{R}^{m-1}$
and
$t\in \mathbb{R}$
.
Cover
$D\times J$
with internally disjoint balls (cubes, in the
$l_{\infty }$
-norm) of radius
$\unicode[STIX]{x1D716}$
. These balls will be referred to as the
$\unicode[STIX]{x1D716}$
-balls. Let
$Z=Z_{0}\times Z_{1}$
be a fixed
$\unicode[STIX]{x1D716}$
-ball, where
$Z_{0}\subset \mathbb{R}^{m-1}$
is a ball of radius
$\unicode[STIX]{x1D716}$
and
$Z_{1}$
is an interval of length
$2\unicode[STIX]{x1D716}$
.
The sphere
$S$
consists of
$2d$
facets (
$(d-1)$
-dimensional cubes). A facet is obtained by fixing one of the
$d$
coordinates to
$l$
or
$-l$
, and letting the other coordinates take arbitrary values in the interval
$[-l,l]$
. Consider all points
$y$
on a facet such that
$g(y)\in Z_{0}$
. If the fixed coordinate of the facet is one of the first
$m$
coordinates, and such points
$y$
exist at all, then the first
$m$
of their coordinates are determined within an interval of
$8l\unicode[STIX]{x1D716}/t_{0}\leqslant 1$
, while the remaining coordinates can take arbitrary values in
$[-l,l]$
. This set can be covered by at most
$(2l)^{d-m}$
balls of radius
$1/2$
. We refer to these balls as the
$1/2$
-balls for
$Z$
.
Next, consider all points
$y$
on a facet of
$S$
such that
$g(y)\in Z_{0}$
, but assume that the fixed coordinate of this facet is one of the last
$d-m$
coordinates. Cover this set with balls of radius
$1/2$
, as follows. Partition the possible values of the
$m$
th coordinate into
$4l$
intervals, each of length
$1/2$
. These intervals determine each of the first
$m-1$
coordinates of
$y$
within an interval of length
$1$
, and there are
$d-m-1$
further coordinates that can take any value in
$[-l,l]$
. We have
$2(2l)^{d-m}$
balls of radius
$1/2$
that cover all points
$y$
on this facet with
$g(y)\in Z_{0}$
. Summing up over all facets of
$S$
, we have at most
$4d(2l)^{d-m}$
$1/2$
-balls for
$Z$
. For each of these
$1/2$
-balls
$W$
for
$Z$
, select a separate index
$i\in I$
such that
$x_{i}$
lies in the interior of
$Z$
, and set
$y_{i}$
to be the center of the ball
$W$
. Note that the center
$x$
of
$Z$
satisfies
$|x|\geqslant t_{0}-\unicode[STIX]{x1D716}$
(otherwise,
$Z$
would be disjoint from
$D\times J$
). Thus, by our choice of
$t_{0}$
, we have enough indices to choose from. We repeat the same procedure for every
$\unicode[STIX]{x1D716}$
-ball
$Z$
.
Case 1. Consider now any
$f\in {\mathcal{L}}_{j}$
for which there exists
$x=(z,t)\in D\times J$
such that
$y=f(x)\in S$
and
$g(y)=z$
.
Clearly,
$x\in Z$
for some
$\unicode[STIX]{x1D716}$
-ball
$Z$
, and
$y\in W$
for some
$1/2$
-ball
$W$
for
$Z$
. Thus, there exists
$i\in I$
such that
$x_{i}$
lies in the interior of
$Z$
, and
$y_{i}$
is the center of
$W$
. This implies that
$|x_{i}-x|<2\unicode[STIX]{x1D716}$
and
$|y_{i}-y|\leqslant \frac{1}{2}$
. Using the Lipschitz property, we obtain
$$\begin{eqnarray}|f(x_{i})-y|=|f(x_{i})-f(x)|\leqslant j|x_{i}-x|<2j\unicode[STIX]{x1D716}<{\textstyle \frac{1}{2}}.\end{eqnarray}$$
Hence,
$(x_{i},y_{i})$
controls
$f$
, as
$|f(x_{i})-y_{i}|\leqslant |f(x_{i})-y|+|y_{i}-y|<1$
.
Case 2. It remains to deal with the case where for some
$f\in {\mathcal{L}}_{j}$
we cannot find
$x=(z,t)\in D\times J$
such that
$y=f(x)\in S$
and
$g(y)=z$
.
Let
$f$
be such a function. Notice that
$f(z,t_{0})\in B\setminus S$
for every
$z\in D$
. Indeed, we have
$|(z,t_{0})|=t_{0}$
and, hence,
$|f(z,t_{0})|\leqslant jt_{0}+|f(0)|\leqslant jt_{0}+j<l$
, as required. Then, according to Lemma 4.1, if we cannot find
$x=(z,t)\in D\times J$
such that
$y=f(x)\in S$
and
$g(y)=z$
, then
$f(z,t_{1})\in B$
must hold for some
$z\in D$
. We show that in this case one can select a few more indices
$i\in I$
and set the corresponding values
$y_{i}$
so that for some of the newly selected indices
$i$
, the pairs
$(x_{i},y_{i})$
control
$f$
.
To achieve this, cover the entire ball
$B$
with
$(2l)^{d}$
balls of radius
$1/2$
, and refer to them as new balls. For any
$\unicode[STIX]{x1D716}$
-ball
$Z$
that contains a point
$(z,t_{1})$
and for any new ball
$W$
, choose a separate (yet unselected) index
$i\in I$
such that
$x_{i}$
lies in the interior of
$Z$
, and set
$y_{i}$
to be the center of
$W$
. Note that the center
$x$
of
$Z$
satisfies the inequality
$|x|\geqslant t_{1}-\unicode[STIX]{x1D716}$
. Thus, by our choice of
$t_{1}$
, we have enough indices to choose from. It can be shown by a simple computation similar to the above one that if for some
$z\in D$
we have
$y=f(z,t_{1})\in B$
, then for the indices
$i\in I$
selected for the
$\unicode[STIX]{x1D716}$
-ball containing
$(z,t_{1})$
and the new ball containing
$y$
the pair
$(x_{i},y_{i})$
controls
$f$
.
This completes the proof of the fact that every
$f\in {\mathcal{L}}_{j}$
is controlled by one of the pairs
$(x_{i},y_{i})$
and, hence, the proof of Theorem 4.◻
Remark.
Makai and Pach [Reference Makai and Pach7] proved the following result (that also follows from our Theorem 1). Let
$m\leqslant d$
and let
$A$
be a set of points in
$\mathbb{R}^{m}$
satisfying the condition that for any
$x\in \mathbb{R}^{m}$
, the number of points in the unit ball around
$x$
is at most
$K(|x|^{d-m}+1)$
, where
$K$
is a suitable constant. Then
$A$
is not
$d$
-controlling. Makai and Pach made the conjecture that the same statement remains valid if for any
$x\in \mathbb{R}^{m}$
, the unit ball around
$x$
contains at most
$K(|x|^{d-1}+1)$
points of
$A$
. This would be a significant improvement for
$m>1$
. However, our Theorem 4 shows that no such improvement is possible. Indeed, for any function
$f:\mathbb{R}^{+}\rightarrow \mathbb{R}^{+}$
tending to infinity, one can construct a set of point in
$\mathbb{R}^{m}$
with at most
$f(|x|)|x|^{d-m}$
points in the unit ball around any point
$x$
, but still satisfying the condition of Theorem 4. By the theorem, such a set is
$d$
-controlling.
We close this paper by constructing an explicit set
$A$
with the properties mentioned above. We choose an increasing sequence of reals
$c_{i}>4$
such that
$f(x)>2^{m(i+2)+d}$
whenever
$x\geqslant c_{i}-2$
. Consider the set
$S_{i}:=\{x\in 2^{-i}\mathbb{Z}^{m}\mid c_{i}\leqslant |x|<c_{i+1}\}$
. Form a set
$A_{i}\subset \mathbb{R}^{m}$
by collecting
$\lceil |x|^{d-m}\rceil$
points from the ball of radius
$2^{-i}$
around every point
$x\in S_{i}$
. Consider the set
$A:=\bigcup _{i=1}^{\infty }A_{i}$
. For
$|x|>c_{i}$
, we have at least
$|x|^{d-m}$
points of
$A$
in the
$2^{1-i}$
-ball around
$x$
. This shows that
$A$
satisfies the conditions of Theorem 4 and is, therefore,
$d$
-controlling. On the other hand, if
$i$
is the highest index such that the unit ball around
$x$
contains a point in
$A_{i}$
, then
$|x|>c_{i}-2>2$
, and the unit ball around
$x$
contains at most
$\lceil (|x|+2)^{d-m}\rceil$
points of
$A$
around each of the at most
$2^{m(i+2)}$
points of
$\bigcup _{i=1}^{\infty }S_{i}$
in the ball of radius
$2$
about
$x$
. By our choice of
$c_{i}$
, this shows that the unit ball around
$x$
contains at most
$f(|x|)|x|^{d-m}$
points of
$A$
, as claimed.
Acknowledgements
We thank the referee for carefully reading the text and pointing out an inaccuracy in the proof of Claim 2.1. The first author is supported in part by the grant N 15-01-03530 of the Russian Foundation for Basic Research. The second author is supported by Swiss National Science Foundation Grants 200020-162884 and 200021-165977. The third author is supported by the Cryptography “Lendület” project of the Hungarian Academy of Sciences and by the National Research, Development and Innovation Office, NKFIH, projects K-116769 and SNN-117879.
