1 Introduction
A convex body
$K$
in the
$d$
-dimensional Euclidean space
$\mathbb{R}^{d}$
is a compact convex set with non-empty interior, and is
$o$
-symmetric if
$K=-K$
. A (positive) homothet of
$K$
is a set of the form
$\unicode[STIX]{x1D706}K+v:=\{\unicode[STIX]{x1D706}k+v:k\in K\}$
, where
$\unicode[STIX]{x1D706}>0$
is the homothety ratio and
$v\in \mathbb{R}^{d}$
is a translation vector. We investigate arrangements of homothets of convex bodies. The starting point of our investigations is a paper of Füredi and Loeb [Reference Füredi and Loeb9, Problem 4.4].
Is it true that for any centrally symmetric body
$K$
of dimension
$d,d\geqslant d_{0}$
, the number of pairwise intersecting homothetic copies of
$K$
which do not contain each other’s centers is at most
$2^{d}$
?
There exist eight such homothets of the circular disc [Reference Harary, Jacobson, Lipman and McMorris11, Reference Malnič and Mohar14] (Figure 1). A Minkowski arrangement of an
$o$
-symmetric convex body
$K$
is defined to be a family
$\{v_{i}+\unicode[STIX]{x1D706}_{i}K\}$
of positive homothets of
$K$
such that none of the homothets contains the center of any other homothet in its interior. This notion was introduced by Fejes Tóth [Reference Fejes Tóth5] in the context of Minkowski’s fundamental theorem on the minimal determinant of a packing lattice for a symmetric convex body, and it was further studied in the papers [Reference Böröczky and Szabó2, Reference Fejes Tóth6, Reference Fejes Tóth8] and in connection with the Besicovitch covering theorem in [Reference Füredi and Loeb9]. Recently, Minkowski arrangements have been used to study a problem arising in the design of wireless networks [Reference Naszódi, Sandoval and Smorodinsky21].
A pairwise intersecting strict Minkowski arrangement of eight circles (after Harary et al [Reference Harary, Jacobson, Lipman and McMorris11]).
We also define a strict Minkowski arrangement of
$K$
to be a family
$\{v_{i}+\unicode[STIX]{x1D706}_{i}K\}$
of positive homothets of
$K$
such that none of the homothets contains the center of any other homothet. We write
$\unicode[STIX]{x1D705}(K)$
(
$\unicode[STIX]{x1D705}^{\prime }(K)$
) for the largest number of homothets that a pairwise intersecting (strict) Minkowski arrangement of
$K$
can have.
Thus, the question of Füredi and Loeb may be phrased as follows. Is it true that
$\unicode[STIX]{x1D705}^{\prime }(K)\leqslant 2^{d}$
for any
$o$
-symmetric convex body
$K$
in
$\mathbb{R}^{d}$
with
$d$
sufficiently large? A construction of Talata [Reference Talata27] implies that the answer to this question is negative: there exists a
$d$
-dimensional convex body
$K$
such that
$\unicode[STIX]{x1D705}^{\prime }(K)\geqslant {\textstyle \frac{16}{35}}\sqrt{7}^{d}$
for all
$d\geqslant 3$
(see §2). The question now becomes a search to find an upper bound for
$\unicode[STIX]{x1D705}^{\prime }(K)$
. It follows from [Reference Füredi and Loeb9, Theorem 2.1] that
$\unicode[STIX]{x1D705}^{\prime }(K)\leqslant \unicode[STIX]{x1D705}(K)\leqslant 5^{d}$
for any
$o$
-symmetric
$d$
-dimensional convex body
$K$
. Our first result is the following improvement.
Theorem 1. For any
$d$
-dimensional
$o$
-symmetric convex body
$K$
,
$$\begin{eqnarray}\unicode[STIX]{x1D705}^{\prime }(K)\leqslant \unicode[STIX]{x1D705}(K)\leqslant O(3^{d}d\log d).\end{eqnarray}$$
It is easy to see that for the
$d$
-cube
$C^{d}$
,
$\unicode[STIX]{x1D705}(C^{d})=3^{d}$
, which shows that the upper bound for
$\unicode[STIX]{x1D705}(K)$
in Theorem 1 is sharp up to the
$O(d\log d)$
factor. We will, in fact, prove a strengthening of this theorem in Theorem 5 below. However, we have no better upper bound for
$\unicode[STIX]{x1D705}^{\prime }(K)$
than that for
$\unicode[STIX]{x1D705}(K)$
.
Theorem 1 implies that if we have a sequence of balls
$B_{1},B_{2},\ldots ,B_{n}$
(of not necessarily equal radii) in a
$d$
-dimensional normed space, such that for any
$1\leqslant i<j\leqslant n$
, the center of
$B_{j}$
is on the boundary of
$B_{i}$
, then
$n\leqslant O(6^{d}d^{2}\log d)$
(Corollary 14 in §4). This has recently been improved to an almost tight bound by Polyanskii [Reference Polyanskii22]. This result has an application to
$k$
-distance sets [Reference Swanepoel25].
We next consider convex bodies that are not necessarily
$o$
-symmetric, and we extend the notion of a Minkowski arrangement as follows. In the absence of a center, we choose a fixed reference point in the interior of the convex body.
Definition 1. Let
$K$
be a convex body and let
$p$
be a fixed point in the interior of
$K$
. A Minkowski arrangement of
$K$
with respect to
$p$
is a family
$\{v_{i}+\unicode[STIX]{x1D706}_{i}K\}$
of positive homothets of
$K$
with the property that
$v_{i}+p$
is not in
$v_{j}+\unicode[STIX]{x1D706}_{j}\operatorname{int}(K)$
for any distinct
$i$
and
$j$
. We denote the largest number of homothets that a pairwise intersecting Minkowski arrangement of
$K$
with respect to
$p$
can have by
$\unicode[STIX]{x1D705}(K,p)$
.
Similarly, we define a strict Minkowski arrangement of
$K$
with respect to
$p$
to be a family
$\{v_{i}+\unicode[STIX]{x1D706}_{i}K\}$
of positive homothets of
$K$
such that
$v_{i}+p\notin v_{j}+\unicode[STIX]{x1D706}_{j}K$
for any
$i\neq j$
, and we write
$\unicode[STIX]{x1D705}^{\prime }(K,p)$
for the largest number of homothets that a pairwise intersecting strict Minkowski arrangement of
$K$
with respect to
$p$
can have.
Thus, when
$K$
is
$o$
-symmetric,
$\unicode[STIX]{x1D705}(K)=\unicode[STIX]{x1D705}(K,o)$
and
$\unicode[STIX]{x1D705}^{\prime }(K)=\unicode[STIX]{x1D705}^{\prime }(K,o)$
. For bodies that are not
$o$
-symmetric, we also need to measure in some way how far they are from being
$o$
-symmetric.
Definition 2. Let
$K$
be a convex body with
$p$
in its interior. Define
$\unicode[STIX]{x1D703}(K,p)$
, the measure of asymmetry of
$K$
with respect to
$p$
to be
$\unicode[STIX]{x1D703}(K,p):=\inf \{\unicode[STIX]{x1D703}:p-K\subseteq \unicode[STIX]{x1D703}(K-p)\}$
.
(Grünbaum [Reference Grünbaum10, §6.1] defines a quantity similar to
$\unicode[STIX]{x1D703}$
.) Our next result generalizes Theorem 1.
Theorem 2. Let
$K$
be a convex body in
$\mathbb{R}^{d}$
with
$p\in \operatorname{int}(K)$
. Then
$$\begin{eqnarray}\displaystyle \unicode[STIX]{x1D705}^{\prime }(K,p) & {\leqslant} & \displaystyle \unicode[STIX]{x1D705}(K,p)\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \biggl(\frac{3}{2}\biggr)^{d}\frac{\operatorname{vol}(K-K)}{\operatorname{vol}((K-p)\cap (p-K))}O(d(\log d+\log \unicode[STIX]{x1D703}(K,p))).\nonumber\end{eqnarray}$$
If
$c$
is the centroid of
$K$
, then
$$\begin{eqnarray}\unicode[STIX]{x1D705}^{\prime }(K,c)\leqslant \unicode[STIX]{x1D705}(K,c)\leqslant 3^{d}\binom{2d}{d}O(d\log d).\end{eqnarray}$$
There exists a
$d$
-dimensional convex body
$K$
with centroid
$c$
such that
$\unicode[STIX]{x1D705}(K,c)\geqslant \sqrt{10}^{d}$
(detailed at the end of §3). We prove a strengthening of Theorem 2 in Theorem 8 below.
When
$K$
is
$o$
-symmetric, Arias-de Reyna et al [Reference Arias-de Reyna, Ball and Villa1, Theorem 1] derived a lower bound
$\unicode[STIX]{x1D6FA}((2/\sqrt{3})^{d})$
for the strict Hadwiger number
$H^{\prime }(K)$
(see Definition 3 in §2), which implies that
$\unicode[STIX]{x1D705}^{\prime }(K)=\unicode[STIX]{x1D6FA}((2/\sqrt{3})^{d})$
. We show the same lower bound in the non-symmetric case.
Theorem 3. Let
$K$
be a convex body with
$p\in \operatorname{int}(K)$
. Then
$\unicode[STIX]{x1D705}^{\prime }(K,p)>c(2/\sqrt{3})^{d}$
for some universal constant
$c>0$
.
We also prove a lower bound for a variant
$h^{\prime }(K)$
(see Definition 7 in §3) of the strict Hadwiger number
$H^{\prime }(K)$
for
$K$
that is not
$o$
-symmetric.
Theorem 4. Let
$K$
be a convex body in
$\mathbb{R}^{d}$
with
$o\in \operatorname{int}(K)$
. Then, for sufficiently large
$d$
,
$$\begin{eqnarray}\unicode[STIX]{x1D705}^{\prime }(K,o)\geqslant h^{\prime }(K)\geqslant \frac{1}{4d^{2}}\biggl(\frac{2}{\sqrt{3}}\biggr)^{d}.\end{eqnarray}$$
The paper is organized as follows. In §2, we apply a result of Talata to give a negative answer to the question of Füredi and Loeb quoted at the beginning of the Introduction. In §3, we state two stronger versions of Theorem 1 (Theorems 5 and 8). The latter one, which is the main result in this paper, is valid for all (not necessarily centrally symmetric) convex bodies. It is proved in §4. The other two main results, Theorems 3 and 4, also hold for non-symmetric bodies. They are proved in the last section. Along the way, we obtain some facts (Lemmas 9 and 15, Theorem 16) that are useful in studying non-symmetric convex bodies in general.
2 A negative answer to the question of Füredi and Loeb
Let
$K$
be an
$o$
-symmetric convex body in
$\mathbb{R}^{d}$
. Denote the norm with unit ball
$K$
by
$\Vert \cdot \Vert _{K}$
.
Definition 3. For any convex body
$K$
, the Hadwiger number (respectively, strict Hadwiger number) of
$K$
is defined as the maximum number
$H(K)$
(respectively,
$H^{\prime }(K)$
) of non-overlapping (respectively, disjoint) translates of
$K$
touching
$K$
.
When
$K$
is
$o$
-symmetric,
$H(K)$
equals the maximum number of points
$v_{1},\ldots ,v_{m}$
such that
$\Vert v_{i}\Vert _{K}=1$
for all
$i$
and
$\Vert v_{i}-v_{j}\Vert _{K}\geqslant 1$
for all distinct
$i,j$
. Then
$\{K\}\cup \{K+v_{i}:i=1,\ldots ,m\}$
is a Minkowski arrangement of translates of
$K$
all intersecting in
$o$
, and hence
$\unicode[STIX]{x1D705}(K)\geqslant H(K)+1$
. Similarly,
$H^{\prime }(K)$
equals the maximum number of points
$v_{1},\ldots ,v_{m}$
such that
$\Vert v_{i}\Vert _{K}=1$
for all
$i$
and
$\Vert v_{i}-v_{j}\Vert _{K}>1$
for all distinct
$i,j$
. Thus,
$\{K+v_{i}:i=1,\ldots ,m\}$
is a strict Minkowski arrangement of translates of
$K$
all intersecting in
$o$
, and hence
$\unicode[STIX]{x1D705}^{\prime }(K)\geqslant H^{\prime }(K)$
. To answer the question of Füredi and Loeb in the negative, it is therefore sufficient to find an
$o$
-symmetric convex body
$K$
with
$H^{\prime }(K)>2^{d}$
. In dimension three, we may take the Euclidean ball
$B^{3}$
, for which it is well known that
$H^{\prime }(B^{3})=12$
. For
$d>3$
, we may use a result of Talata [Reference Talata27, Lemma 3.1] according to which
$H^{\prime }(C^{k}\times K)=2^{k}H^{\prime }(K)$
holds for any
$o$
-symmetric convex body
$K$
, where
$C^{k}$
is the
$k$
-dimensional cube. In particular,
$H^{\prime }(B^{3}\times C^{d-3})=3\cdot 2^{d-1}>2^{d}$
for all
$d\geqslant 3$
. In fact, Talata [Reference Talata27, Theorem 1.3] constructed
$d$
-dimensional
$o$
-symmetric convex bodies
$K$
such that
$H^{\prime }(K)\geqslant \frac{16}{35}\sqrt{7}^{d}$
for all
$d\geqslant 3$
. It follows that, for these bodies,
$\unicode[STIX]{x1D705}(K)\geqslant \unicode[STIX]{x1D705}^{\prime }(K)\geqslant \unicode[STIX]{x1D6FA}(\sqrt{7}^{d})$
.
3 Packing and non-symmetric norms
Definition 4. If
$K$
is
$o$
-symmetric, we define the packing number
$P(K,\unicode[STIX]{x1D706})$
of
$K$
as the maximum number of points in the normed space with unit ball
$K$
, such that the ratio of the maximal distance to the minimal distance is at most
$\unicode[STIX]{x1D706}$
. We denote the normed space with unit ball
$K$
as
${\mathcal{N}}$
, and also use the notation
$\unicode[STIX]{x1D705}({\mathcal{N}})$
,
$P({\mathcal{N}},\unicode[STIX]{x1D706})$
,
$H({\mathcal{N}})$
,
$\ldots \,$
in place of
$\unicode[STIX]{x1D705}(K)$
,
$P(K,\unicode[STIX]{x1D706})$
,
$H(K)$
,
$\ldots \,$
.
It follows from the isodiametric inequality in normed spaces (an immediate corollary to the Brunn–Minkowski Theorem [Reference Busemann3, Reference Mel’nikov15]) that
$$\begin{eqnarray}P({\mathcal{N}},\unicode[STIX]{x1D706})\leqslant (\unicode[STIX]{x1D706}+1)^{d}\end{eqnarray}$$
for any
$d$
-dimensional normed space
${\mathcal{N}}$
. (See Lemma 7 below for a generalization.) Our next result strengthens Theorem 1.
Theorem 5. Let
${\mathcal{N}}$
be a
$d$
-dimensional real normed space. Then
$$\begin{eqnarray}\unicode[STIX]{x1D705}^{\prime }({\mathcal{N}})\leqslant \unicode[STIX]{x1D705}({\mathcal{N}})\leqslant P\biggl({\mathcal{N}},2\biggl(1+\frac{1}{d}\biggr)\biggr)(d+O(1))\log d=O(3^{d}d\log d).\end{eqnarray}$$
Since
$\unicode[STIX]{x1D705}(C^{d})\geqslant H(C^{d})+1=3^{d}$
, the upper bound for
$\unicode[STIX]{x1D705}({\mathcal{N}})$
in Theorem 5 is sharp up to the
$O(d\log d)$
factor. Theorem 5 is a special case of Theorem 8 below that also deals with
$K$
that are not necessarily
$o$
-symmetric, which are considered next.
Definition 5. If the convex body
$K$
contains the origin in the interior, we define the (asymmetric) norm
$\Vert \cdot \Vert _{K}:\mathbb{R}^{d}\rightarrow \mathbb{R}$
by
$\Vert x\Vert _{K}=\inf \{\unicode[STIX]{x1D706}>0:x\in \unicode[STIX]{x1D706}K\}$
.
Note that the measure of asymmetry of
$K$
with respect to
$o$
can be defined in terms of the norm:
$$\begin{eqnarray}\unicode[STIX]{x1D703}(K,o)=\sup \{\Vert x\Vert _{K}/\Vert -x\Vert _{K}:x\in \operatorname{bd}K\}.\end{eqnarray}$$
We need the following well-known result.
Lemma 6 (Minkowski [Reference Minkowski20]).
For any
$d$
-dimensional convex body
$K$
with centroid
$c$
,
$\unicode[STIX]{x1D703}(K,c)\leqslant d$
.
We will also use the (symmetric) norm defined by the unit ball
$K\cap -K$
. Thus,
$\Vert x\Vert _{K\cap -K}=\max \{\Vert x\Vert _{K},\Vert -x\Vert _{K}\}$
. We also need another symmetric norm.
Definition 6. For any convex body
$K$
, define its central symmetral to be
$\frac{1}{2}(K-K)$
. If
$o\in \operatorname{int}(K)$
, then
$P(K,\unicode[STIX]{x1D706})$
is defined to be the maximum number of points
$p_{1},\ldots ,p_{m}$
such that
$$\begin{eqnarray}\frac{\max \{\Vert p_{i}-p_{j}\Vert _{(1/2)(K-K)}:1\leqslant i<j\leqslant m\}}{\min \{\Vert p_{i}-p_{j}\Vert _{K\cap -K}:1\leqslant i<j\leqslant m\}}\leqslant \unicode[STIX]{x1D706}.\end{eqnarray}$$
If
$K$
is
$o$
-symmetric, then the norms
$\Vert \cdot \Vert _{K}$
,
$\Vert \cdot \Vert _{K\cap -K}$
and
$\Vert \cdot \Vert _{(1/2)(K-K)}$
are all identical, and
$P(K,\unicode[STIX]{x1D706})$
coincides with the definition given before.
Lemma 7. For any convex body
$K$
with
$o$
in its interior and any
$\unicode[STIX]{x1D706}>0$
,
$$\begin{eqnarray}P(K,\unicode[STIX]{x1D706})\leqslant (\unicode[STIX]{x1D706}+1)^{d}\frac{\operatorname{vol}((1/2)(K-K))}{\operatorname{vol}(K\cap -K)}.\end{eqnarray}$$
We also need to generalize the Hadwiger number to the non-symmetric case in the following non-standard way.
Definition 7. If
$o\in \operatorname{int}(K)$
, define
$h(K)$
to be the maximum number of points
$p_{1},\ldots ,p_{m}$
on
$\operatorname{bd}K$
such that
$\Vert p_{i}-p_{j}\Vert _{K}\geqslant 1$
for all distinct
$i,j=1,\ldots ,m$
. Similarly, we define
$h^{\prime }(K)$
to be the maximum number of points
$p_{1},\ldots ,p_{m}\in \operatorname{bd}K$
such that
$\Vert p_{i}-p_{j}\Vert _{K}>1$
for all distinct
$i,j=1,\ldots ,m$
.
If
$K=-K$
, then
$h(K)=H(K)$
and
$h^{\prime }(K)=H^{\prime }(K)$
(cf. Definition 3). This is not necessarily the case if
$K$
is not
$o$
-symmetric. (Note that for all convex bodies,
$H(K)=H(\frac{1}{2}(K-K))$
.) Generalizing our observation for the symmetric case above, if
$p_{1},\ldots ,p_{m}\in \operatorname{bd}K$
satisfy
$\Vert p_{i}-p_{j}\Vert _{K}>1$
for all distinct
$i,j$
, then the collection
$\{K-p_{i}:i=1,\ldots ,m\}$
is a pairwise intersecting strict Minkowski arrangement of translates of
$K$
, and hence
$\unicode[STIX]{x1D705}^{\prime }(K,o)\geqslant h^{\prime }(K)$
. Similarly (by adding
$K$
to the collection),
$\unicode[STIX]{x1D705}(K,o)\geqslant h(K)+1$
. We can now formulate our generalization of Theorem 2.
Theorem 8. Let
$K$
be a convex body in
$\mathbb{R}^{d}$
with
$o\in \operatorname{int}(K)$
. Then
$$\begin{eqnarray}\unicode[STIX]{x1D705}^{\prime }(K,o)\leqslant \unicode[STIX]{x1D705}(K,o)\leqslant P\biggl(K,2\biggl(1+\frac{1}{d}\biggr)\biggr)(d+O(1))(\log d+\log \unicode[STIX]{x1D703}(K,o)).\end{eqnarray}$$
If
$c$
is the centroid of
$K$
, then
$$\begin{eqnarray}\unicode[STIX]{x1D705}(K,c)\leqslant P\biggl(K,2\biggl(1+\frac{1}{d}\biggr)\biggr)(2d+O(1))\log d.\end{eqnarray}$$
The proof is postponed to the next section. The following is an example of a
$d$
-dimensional convex body
$K$
with centroid
$c$
for which
$\unicode[STIX]{x1D705}(K,c)$
is much larger than in the symmetric case. Note that
$\unicode[STIX]{x1D705}(\unicode[STIX]{x1D6E5},o)=10$
, where
$\unicode[STIX]{x1D6E5}$
is a triangle with centroid
$o$
[Reference Fejes Tóth7] (see Figure 2). A Cartesian product of
$\lfloor d/2\rfloor$
triangles gives a
$d$
-dimensional convex body
$K$
with centroid
$c$
such that
$\unicode[STIX]{x1D705}(K,c)\geqslant 10^{\lfloor d/2\rfloor }\geqslant \sqrt{10}^{d-1}$
.
A pairwise intersecting Minkowski arrangement of ten triangles [Reference Fejes Tóth7].
4 Bounding
$\unicode[STIX]{x1D705}$
from above
Proof of Lemma 7.
Let
$T\subset \mathbb{R}^{d}$
be such that
$\Vert x-y\Vert _{K\cap -K}\geqslant 1$
and
$\Vert x-y\Vert _{(1/2)(K-K)}\leqslant \unicode[STIX]{x1D706}$
for all distinct
$x,y\in T$
. Then
$\{v+\frac{1}{2}(K\cap -K):v\in T\}$
is a packing. Let
$P=T+\frac{1}{2}(K\cap -K)$
. Then
$\operatorname{vol}(P)=2^{-d}|T|\operatorname{vol}(K\cap -K)$
and
$$\begin{eqnarray}P-P=T-T+(K\cap -K)\subseteq \frac{\unicode[STIX]{x1D706}}{2}(K-K)+\frac{1}{2}(K-K)=\frac{\unicode[STIX]{x1D706}+1}{2}(K-K).\end{eqnarray}$$
By the Brunn–Minkowski inequality,
$\operatorname{vol}(P-P)\geqslant 2^{d}\operatorname{vol}(P)$
, and it follows that
$$\begin{eqnarray}\hspace{8.0pt}|T|=\frac{2^{d}\operatorname{vol}(P)}{\operatorname{vol}(K\cap -K)}\leqslant \frac{\operatorname{vol}(P-P)}{\operatorname{vol}(K\cap -K)}\leqslant \frac{(\unicode[STIX]{x1D706}+1)^{d}\operatorname{vol}(\frac{1}{2}(K-K))}{\operatorname{vol}(K\cap -K)}.\hspace{2.0pt}\square\end{eqnarray}$$
Before we prove Theorem 8, we first show an extension of the so-called “bow-and-arrow” inequality of [Reference Füredi and Loeb9] (Corollary 10 below) to the case of an asymmetric norm.
Definition 8. For any non-zero
$v\in \mathbb{R}^{d}$
, write
$v^{\wedge }=(1/\Vert v\Vert _{K})v$
for the normalization of
$v$
with respect to
$\Vert \cdot \Vert _{K}$
.
We will only consider normalizations with respect to
$\Vert \cdot \Vert _{K}$
; never with respect to
$\Vert \cdot \Vert _{K\cap -K}$
or
$\Vert \cdot \Vert _{(1/2)(K-K)}$
.
Lemma 9. Let
$K$
be a convex body in
$\mathbb{R}^{d}$
containing
$o$
in its interior. Let
$a,b\in \mathbb{R}^{d}$
such that
$\Vert a\Vert _{K}\geqslant \Vert b\Vert _{K}>0$
. Then
$$\begin{eqnarray}\Vert a^{\wedge }-b^{\wedge }\Vert _{K}\geqslant \frac{\Vert a-b\Vert _{K}-\Vert a\Vert _{K}+\Vert b\Vert _{K}}{\Vert b\Vert _{K}}.\end{eqnarray}$$
Proof.
$$\begin{eqnarray}\displaystyle \Vert a-b\Vert _{K} & = & \displaystyle \Vert \Vert a\Vert _{K}a^{\wedge }-\Vert b\Vert _{K}b^{\wedge }\Vert _{K}\nonumber\\ \displaystyle & = & \displaystyle \Vert \Vert b\Vert _{K}(a^{\wedge }-b^{\wedge })+(\Vert a\Vert _{K}-\Vert b\Vert _{K})a^{\wedge }\Vert _{K}\nonumber\\ \displaystyle & {\leqslant} & \displaystyle \Vert b\Vert _{K}\Vert a^{\wedge }-b^{\wedge }\Vert _{K}+\Vert a\Vert _{K}-\Vert b\Vert _{K}.\square\nonumber\end{eqnarray}$$
Corollary 10. For any two non-zero elements
$a$
and
$b$
of a normed space,
$$\begin{eqnarray}\Vert a^{\wedge }-b^{\wedge }\Vert \geqslant \frac{\Vert a-b\Vert -|\Vert a\Vert -\Vert b\Vert |}{\Vert b\Vert }.\end{eqnarray}$$
Proof of Theorem 8.
Consider a pairwise intersecting Minkowski arrangement
$\{\unicode[STIX]{x1D706}_{i}K+v_{i}:i=1,\ldots ,m\}$
. Without loss of generality,
$\unicode[STIX]{x1D706}_{1}=\min _{i}\unicode[STIX]{x1D706}_{i}=1$
and
$v_{1}=o$
. Given
$N\in \mathbb{N}$
and
$\unicode[STIX]{x1D6FF}>0$
, we partition the Minkowski arrangement into
$N$
subarrangements as follows. Let
$I_{j}=\{i:\unicode[STIX]{x1D706}_{i}\in [(1+\unicode[STIX]{x1D6FF})^{j-1},(1+\unicode[STIX]{x1D6FF})^{j})\}$
for each
$j=1,\ldots ,N$
, and let
$I_{\infty }=\{i:\unicode[STIX]{x1D706}_{i}\in [(1+\unicode[STIX]{x1D6FF})^{N},\infty )\}$
. We bound the size of each subarrangement
$\{\unicode[STIX]{x1D706}_{i}K+v_{i}:i\in I_{j}\}$
,
$j\in \{1,\ldots ,N,\infty \}$
separately. Finally, we choose appropriate values for
$N$
and
$\unicode[STIX]{x1D6FF}$
.
The next lemma bounds
$I_{j}$
,
$j\neq \infty$
, in terms of
$\unicode[STIX]{x1D6FF}$
and
$K$
.
Lemma 11. Let
$K$
be a
$d$
-dimensional convex body with
$o\in \operatorname{int}(K)$
. Let
$\{v_{i}+\unicode[STIX]{x1D706}_{i}K:i\in I\}$
be a pairwise intersecting Minkowski arrangement of positive homothets of
$K$
, with
$\unicode[STIX]{x1D706}_{i}\in [1,1+\unicode[STIX]{x1D6FF})$
for each
$i\in I$
. Then
$$\begin{eqnarray}|I|\leqslant P(K,2(1+\unicode[STIX]{x1D6FF})).\end{eqnarray}$$
Proof. For any distinct
$i,j\in I$
,
$(v_{i}+\unicode[STIX]{x1D706}_{i}K)\cap (v_{j}+\unicode[STIX]{x1D706}_{j}K)\neq \emptyset$
, so there exist
$x,y\in K$
such that
$v_{i}-v_{j}=\unicode[STIX]{x1D706}_{j}y-\unicode[STIX]{x1D706}_{i}x$
. Since
$\unicode[STIX]{x1D706}_{i},\unicode[STIX]{x1D706}_{j}\in [1,1+\unicode[STIX]{x1D6FF}]$
,
$o\in K$
and
$K$
is convex,
$\unicode[STIX]{x1D706}_{i}x,\unicode[STIX]{x1D706}_{j}y\in (1+\unicode[STIX]{x1D6FF})K$
. Hence,
$v_{i}-v_{j}\in (1+\unicode[STIX]{x1D6FF})(K-K)$
and
$\Vert v_{i}-v_{j}\Vert _{(1/2)(K-K)}\leqslant 2(1+\unicode[STIX]{x1D6FF})$
. Since
$v_{i}\notin v_{j}+\unicode[STIX]{x1D706}_{j}\operatorname{int}(K)$
, it follows that
$v_{i}-v_{j}\notin \operatorname{int}(K\cap -K)$
for all distinct
$i,j\in I$
, which gives
$\Vert v_{i}-v_{j}\Vert _{K\cap -K}\geqslant 1$
. ◻
The following lemma is used to bound
$I_{\infty }$
.
Lemma 12. Let
$K$
be a
$d$
-dimensional convex body with
$o\in \operatorname{int}(K)$
. Let
$\{v_{i}+\unicode[STIX]{x1D706}_{i}K:i\in I\}$
be a Minkowski arrangement of positive homothets of
$K$
with
$\unicode[STIX]{x1D706}_{i}\geqslant 1$
,
$(v_{i}+\unicode[STIX]{x1D706}_{i}K)\cap -\unicode[STIX]{x1D700}K\neq \emptyset$
and
$o\notin v_{i}+\unicode[STIX]{x1D706}_{i}\operatorname{int}(K)$
for all
$i\in I$
. Then
$$\begin{eqnarray}|I|\leqslant P\biggl(K,\frac{2}{1-\unicode[STIX]{x1D700}}\biggr).\end{eqnarray}$$
We first consider any two homothets in the Minkowski arrangement of the previous lemma.
Lemma 13. Let
$v_{1}+\unicode[STIX]{x1D706}_{1}K$
and
$v_{2}+\unicode[STIX]{x1D706}_{2}K$
be two positive homothets of
$K$
such that
$\unicode[STIX]{x1D706}_{1},\unicode[STIX]{x1D706}_{2}\geqslant 1$
,
$v_{1}\notin v_{2}+\unicode[STIX]{x1D706}_{2}\operatorname{int}(K)$
,
$v_{2}\notin v_{1}+\unicode[STIX]{x1D706}_{1}\operatorname{int}(K)$
,
$o\notin v_{i}+\unicode[STIX]{x1D706}_{i}\operatorname{int}(K)$
and
$(v_{i}+\unicode[STIX]{x1D706}_{i}K)\cap -\unicode[STIX]{x1D700}K\neq \emptyset \;(i=1,2)$
. Then
$$\begin{eqnarray}\biggl\|\frac{1}{\Vert -v_{1}\Vert _{K}}(-v_{1})-\frac{1}{\Vert -v_{2}\Vert _{K}}(-v_{2})\biggr\|_{K\cap -K}\geqslant 1-\unicode[STIX]{x1D700}.\end{eqnarray}$$
Proof. Since
$\Vert \cdot \Vert _{K\cap -K}$
is symmetric, we may assume that
$\Vert -v_{1}\Vert _{K}\leqslant \Vert -v_{2}\Vert _{K}$
. Since
$(v_{1}+\unicode[STIX]{x1D706}_{1}K)\cap -\unicode[STIX]{x1D700}K\neq \emptyset$
,
$v_{1}+\unicode[STIX]{x1D706}_{1}x=-\unicode[STIX]{x1D700}y$
for some
$x,y\in K$
. Therefore,
$\Vert -v_{1}\Vert _{K}\leqslant \unicode[STIX]{x1D706}_{1}\Vert x\Vert _{K}+\unicode[STIX]{x1D700}\Vert y\Vert _{K}\leqslant \unicode[STIX]{x1D706}_{1}+\unicode[STIX]{x1D700}$
. Also, since
$o\notin v_{1}+\unicode[STIX]{x1D706}_{1}\operatorname{int}(K)$
, we know that
$\Vert -v_{1}\Vert _{K}\geqslant \unicode[STIX]{x1D706}_{1}$
. Similarly,
$\unicode[STIX]{x1D706}_{2}\leqslant \Vert -v_{2}\Vert _{K}\leqslant \unicode[STIX]{x1D706}_{2}+\unicode[STIX]{x1D700}$
, and it follows from
$v_{1}\notin v_{2}+\unicode[STIX]{x1D706}_{2}\operatorname{int}(K)$
that
$\Vert v_{1}-v_{2}\Vert _{K}\geqslant \unicode[STIX]{x1D706}_{2}$
. We apply Lemma 9 to obtain
$$\begin{eqnarray}\displaystyle \Vert (-v_{1})^{\wedge }-(-v_{2})^{\wedge }\Vert _{K\cap -K} & {\geqslant} & \displaystyle \Vert (-v_{2})^{\wedge }-(-v_{1})^{\wedge }\Vert _{K}\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \frac{\Vert v_{1}-v_{2}\Vert _{K}-\Vert -v_{2}\Vert _{K}+\Vert -v_{1}\Vert _{K}}{\Vert -v_{1}\Vert _{K}}\nonumber\\ \displaystyle & {\geqslant} & \displaystyle \frac{\unicode[STIX]{x1D706}_{2}-(\unicode[STIX]{x1D706}_{2}+\unicode[STIX]{x1D700})+\Vert -v_{1}\Vert _{K}}{\Vert -v_{1}\Vert _{K}}\nonumber\\ \displaystyle & = & \displaystyle 1-\frac{\unicode[STIX]{x1D700}}{\Vert -v_{1}\Vert _{K}}\geqslant 1-\frac{\unicode[STIX]{x1D700}}{\unicode[STIX]{x1D706}_{1}}\geqslant 1-\unicode[STIX]{x1D700}.\square\nonumber\end{eqnarray}$$
Proof of Lemma 12.
For each
$i\in I$
, let
$t_{i}=(-v_{i})^{\wedge }$
. Let
$T:=\{t_{i}:i\in I\}$
. By Lemma 13,
$\Vert t_{i}-t_{j}\Vert _{K\cap -K}\geqslant 1-\unicode[STIX]{x1D700}$
for all distinct
$i,j\in I$
. Since
$T\subset \operatorname{bd}K\subset K$
,
$\Vert t_{i}-t_{j}\Vert _{(1/2)(K-K)}\leqslant 2$
. It follows that
$|I|\leqslant P(K,2/(1-\unicode[STIX]{x1D700}))$
.◻
We now finish the proof of Theorem 8. By Lemma 11,
$|I_{j}|\leqslant P(K,2(1+\unicode[STIX]{x1D6FF}))$
for
$j=1,\ldots ,N$
, and by Lemma 12 applied to
$I_{\infty }$
and
$\unicode[STIX]{x1D700}=\unicode[STIX]{x1D703}(K,o)(1+\unicode[STIX]{x1D6FF})^{-N}$
,
$$\begin{eqnarray}|I_{\infty }|\leqslant P\biggl(K,\frac{2}{1-\unicode[STIX]{x1D703}(K,o)(1+\unicode[STIX]{x1D6FF})^{-N}}\biggr).\end{eqnarray}$$
It follows that
$$\begin{eqnarray}m=\mathop{\sum }_{j=1}^{N}|I_{j}|+|I_{\infty }|\leqslant NP(K,2(1+\unicode[STIX]{x1D6FF}))+P\biggl(K,\frac{2}{1-\unicode[STIX]{x1D703}(K,o)(1+\unicode[STIX]{x1D6FF})^{-N}}\biggr).\end{eqnarray}$$
We now choose
$$\begin{eqnarray}N:=1+\lceil \frac{\log d+\log \unicode[STIX]{x1D703}(K,o)}{\log (1+1/d)}\rceil =(d+O(1))O(\log d+\log \unicode[STIX]{x1D703}(K,o))\end{eqnarray}$$
and
$\unicode[STIX]{x1D6FF}=1/d$
. Then
$$\begin{eqnarray}N\geqslant 1+\frac{\log d+\log \unicode[STIX]{x1D703}(K,o)}{\log (1+\unicode[STIX]{x1D6FF})},\end{eqnarray}$$
which implies that
$$\begin{eqnarray}\frac{2}{1-\unicode[STIX]{x1D703}(K,o)(1+\unicode[STIX]{x1D6FF})^{-N}}\leqslant 2(1+\unicode[STIX]{x1D6FF}),\end{eqnarray}$$
and hence
$$\begin{eqnarray}\displaystyle m & {\leqslant} & \displaystyle P\biggl(K,2\biggl(1+\frac{1}{d}\biggr)\biggr)(N+1)\nonumber\\ \displaystyle & = & \displaystyle P\biggl(K,2\biggl(1+\frac{1}{d}\biggr)\biggr)(d+O(1))(\log d+\log \unicode[STIX]{x1D703}(K,o)).\nonumber\end{eqnarray}$$
The second inequality follows from the first and Lemma 6. ◻
Note that Theorem 5 immediately follows from Theorem 8, and Theorem 1 follows from Theorem 5.
Proof of Theorem 2.
The first statement follows from Theorem 8 and Lemma 7. Also, by a result of Milman and Pajor [Reference Milman and Pajor18, Corollary 3] for a convex body
$K$
with centroid
$o$
,
$\operatorname{vol}(K)/\text{vol}(K\cap -K)\leqslant 2^{d}$
, which, together with the Rogers–Shephard inequality [Reference Rogers and Shephard23]
$\operatorname{vol}(K-K)/\text{vol}(K)\leqslant \binom{2d}{d}$
, gives the second statement.
We derive the following application of Theorem 1.
Corollary 14. Let
$K$
be an
$o$
-symmetric convex body, and let
$p_{1},p_{2},\ldots ,p_{n}$
be points in
$\mathbb{R}^{d}$
. Let
$r_{1},r_{2},\ldots ,r_{n}>0$
, and assume that, for any
$1\leqslant i<j\leqslant n$
,
$p_{j}\in p_{i}+r_{i}\operatorname{bd}K$
. Then
$n\leqslant O(6^{d}d^{2}\log d)$
.
Proof. Let
$D\subseteq \{1,2,\ldots ,n-1\}$
be the index set of a longest decreasing subsequence of
$r_{1},r_{2},\ldots ,r_{n-1}$
. Thus, if
$i,j\in D$
with
$i<j$
, then
$r_{i}\geqslant r_{j}$
. Then
$\{p_{i}+r_{i}K:i\in D\}$
is a pairwise intersecting Minkowski arrangement, and by Theorem 1,
$|D|=O(3^{d}d\log d)$
.
Next, let
$I\subseteq \{1,2,\ldots ,n-1\}$
be the index set of a longest increasing subsequence of
$r_{1},r_{2},\ldots ,r_{n-1}$
, that is, if
$i,j\in I$
with
$i<j$
, then
$r_{i}\leqslant r_{j}$
. Let
$m:=\min I$
. By the triangle inequality,
$r_{i}\leqslant 2r_{m}$
for any
$i\in I$
. Indeed, without loss of generality, we may assume that
$i\neq m$
, and then, since
$m<i<n$
,
$\Vert p_{i}-p_{m}\Vert _{K}=\Vert p_{n}-p_{m}\Vert _{K}=r_{m}$
and
$\Vert p_{n}-p_{i}\Vert _{K}=r_{i}$
, from which
$r_{i}\leqslant 2r_{m}$
follows.
We now use the same “logarithmic cut” method as in the proof of Theorem 8. Choose
$N\in \mathbb{N}$
. For each
$k=1,\ldots ,N$
, let
$I_{k}:=\{i\in I:r_{i}/r_{m}\in [2^{(k-1)/N},2^{k/N})\}$
. Then
$\Vert p_{i}-p_{j}\Vert _{K}\in [2^{(k-1)/N},2^{k/N})$
for any distinct
$i,j\in I_{k}$
, and hence
$$\begin{eqnarray}|I_{k}|\leqslant P(K,2^{1/N})\leqslant (1+2^{1/N})^{d},\end{eqnarray}$$
by (1), and
$$\begin{eqnarray}|I|=\mathop{\sum }_{k=1}^{N}|I_{k}|\leqslant N(1+2^{1/N})^{d}.\end{eqnarray}$$
We now choose an optimal value
$N:=d$
to obtain
$|I|\leqslant d(1+2^{1/d})^{d}=O(2^{d}d)$
.
By the Erdős–Szekeres theorem [Reference Erdős and Szekeres4], any sequence of real numbers for which all decreasing subsequences are of length at most
$s$
and all increasing subsequences are of length at most
$t$
, has length at most
$st$
. It follows that
$n-1\leqslant |D|\cdot |I|$
, and hence
$$\begin{eqnarray}n=O(3^{d}d\log d)O(2^{d}d)=O(6^{d}d^{2}\log d),\end{eqnarray}$$
as claimed. ◻
5 Bounding
$\unicode[STIX]{x1D705}^{\prime }$
from below
In this section, we prove Theorems 3 and 4 by extending a lower bound for the strict Hadwiger number
$H^{\prime }(K)$
by Arias-de Reyna et al [Reference Arias-de Reyna, Ball and Villa1, Theorem 1] to non-symmetric convex bodies. Earlier, Bourgain [Reference Füredi and Loeb9] showed an exponential lower bound to
$H^{\prime }(K)$
for
$o$
-symmetric
$K$
that depends only on the dimension of
$K$
. (This argument was also independently discovered by Talata [Reference Talata26].) The key tool used by Bourgain and Talata is Milman’s quotient of subspace theorem (or, in short, the QS theorem) [Reference Milman17].
In order to obtain a lower bound on
$\unicode[STIX]{x1D705}(K,p)$
in the non-symmetric case, it is possible to use a non-symmetric version of the QS theorem (see Milman and Pajor [Reference Milman and Pajor18] or Rudelson [Reference Rudelson24]), or one may generalize the approach from [Reference Arias-de Reyna, Ball and Villa1]. The first approach does not lead to a concrete lower bound, and we will follow the second. However, neither approach is straightforward. One obstacle is that
$p$
may not coincide with the centroid of
$K$
. To bypass this problem, we use the following topological result.
Lemma 15. Let
$K$
be a convex body in
$\mathbb{R}^{d}$
. Then there is a
$(d-1)$
-dimensional linear subspace
$H$
of
$\mathbb{R}^{d}$
such that the centroid of the orthogonal projection of
$K$
onto
$H$
is the origin.
Statements similar to this lemma are known (see, for instance, [Reference Izmestiev13]). The lemma itself is surely also known. However, since we could not find a reference, we include its simple proof.
Proof. For any unit vector
$u\in \mathbb{S}^{d-1}$
, let
$f(u)$
be the centroid of the orthogonal projection of
$K$
onto
$u^{\bot }$
. We need to show that
$f(u)=o$
for some
$u\in \mathbb{S}^{d-1}$
. Suppose not. Then
$f^{\wedge }:\mathbb{S}^{d-1}\rightarrow \mathbb{S}^{d-1}$
, defined by
$f^{\wedge }(u)=f(u)/\Vert f(u)\Vert _{2}$
, is a continuous, even mapping such that
$\langle u,f^{\wedge }(u)\rangle =0$
for all
$u\in \mathbb{S}^{d-1}$
. Since
$f^{\wedge }$
is even, its degree is even (see, for instance, [Reference Hatcher12, Proposition 2.30]). Also,
$f^{\wedge }(u)\neq -u$
for all
$u\in \mathbb{S}^{d-1}$
. It follows that
$f^{\wedge }$
is homotopic to the identity map, which has degree one, which is a contradiction. ◻
We briefly outline how this lemma can be combined with the non-symmetric QS theorem to obtain that
$h^{\prime }(K)>c^{d}$
for some universal constant
$c>1$
. Later on in this section, we will obtain more explicit bounds (Theorems 3 and 4) using the main result of [Reference Arias-de Reyna, Ball and Villa1].
First, the non-symmetric version of the QS theorem ([Reference Milman and Pajor18, Theorem 9] and [Reference Rudelson24, Theorem 4]), combined with Lemma 15, yield that, for any convex body
$K$
in
$\mathbb{R}^{d}$
, there is a roughly
$(d/2)$
-dimensional subspace
$E$
and an origin-centered ellipsoid
${\mathcal{E}}$
in
$E$
, such that for an appropriate projection
$P$
of
$\mathbb{R}^{d}$
,
${\mathcal{E}}\subseteq P(K)\cap E\subseteq c{\mathcal{E}}$
with some universal constant
$c$
. By a theorem of Milman [Reference Milman16] (see also [Reference Milman and Schechtman19, §4.3]), we can take a
$C(d/2)$
-dimensional subspace
$E^{\prime }$
of
$E$
such that
${\mathcal{E}}^{\prime }:={\mathcal{E}}\cap E^{\prime }\subseteq P(K)\cap E^{\prime }\subseteq 1.1{\mathcal{E}}^{\prime }$
for a universal constant
$C>0$
. Although this is stated only for symmetric bodies
$K$
in [Reference Milman and Schechtman19], the proof works in the non-symmetric case as well.
Now, we can follow the proof of the symmetric case [Reference Füredi and Loeb9, (Theorem 4.3)] closely. There are exponentially many points on the relative boundary of
$K^{\prime }:=P(K)\cap E^{\prime }$
such that the distance (with respect to the slightly non-symmetric norm
$\Vert \cdot \Vert _{K^{\prime }}$
on
$E^{\prime }$
) between any two points is at least
$1.21$
. Let
$X$
be the set of these points. For every
$x\in X$
, choose a point
$p\in \operatorname{bd}K$
such that
$P(p)=x$
. These points satisfy Definition 7.
Before we prove Theorems 3 and 4, we state a non-symmetric version of [Reference Arias-de Reyna, Ball and Villa1, Theorem 1].
Theorem 16. Let
$K$
be a convex body in
$\mathbb{R}^{d}$
with
$o\in \operatorname{int}(K)$
. Let
$\unicode[STIX]{x1D707}$
denote the uniform (with respect to Lebesgue measure) probability measure on
$K$
. Then, for any
$0<t<\sqrt{2}$
,
$$\begin{eqnarray}F(t):=\unicode[STIX]{x1D707}\otimes \unicode[STIX]{x1D707}\{(x,y)\in K\times K:\Vert x-y\Vert _{K}\leqslant t\}\leqslant \biggl(\frac{t^{2}(4-t^{2})}{4}\biggr)^{d/2}.\end{eqnarray}$$
The proof of Theorem 16 is virtually the same as in [Reference Arias-de Reyna, Ball and Villa1]. We recall the first part of this proof, which is where the only (slight) difference lies. In that proof,
$\unicode[STIX]{x1D707}\otimes \unicode[STIX]{x1D707}\{(x,y)\in K\times K:\Vert x-y\Vert _{K}\leqslant t\}$
is written as a threefold convolution. In the non-symmetric case, it is easy to see that, for any
$t\geqslant 0$
,
$$\begin{eqnarray}F(t)=\unicode[STIX]{x1D707}\otimes \unicode[STIX]{x1D707}\{(x,y)\in K\times K:\Vert x-y\Vert _{K}\leqslant t\}=(\unicode[STIX]{x1D712}_{K}\ast \unicode[STIX]{x1D712}_{-K}\ast \unicode[STIX]{x1D712}_{tK})(0),\end{eqnarray}$$
where
$\unicode[STIX]{x1D712}_{A}$
denotes the indicator function of a set
$A$
. The only difference with the symmetric case is the occurrence of
$\unicode[STIX]{x1D712}_{-K}$
instead of
$\unicode[STIX]{x1D712}_{K}$
in the right-hand side. This does not affect the rest of the proof in [Reference Arias-de Reyna, Ball and Villa1], which is an application of a strong form of Young’s inequality to this threefold convolution, and which we do not repeat.
Proof of Theorem 3.
Let
$m=\frac{1}{4}(2/\sqrt{3})^{d}$
, and choose
$2m$
points
$x_{1},\ldots ,x_{2m}$
independently and uniformly from
$K$
. Then the expected number of ordered pairs
$(x_{i},x_{j})$
,
$i\neq j$
, such that
$\Vert x-y\Vert _{K}\leqslant 1$
, equals
$2m(2m-1)F(1)$
by linearity of expectation. This quantity is at most
$m$
by Theorem 16 and the choice of
$m$
. Thus, there exists a choice of points
$x_{1},\ldots ,x_{2m}$
from
$K$
such that
$\Vert x_{i}-x_{j}\Vert _{K}>1$
for all except at most
$m$
pairs
$(i,j)$
,
$i\neq j$
. For each such pair, delete one of the points. We end up with
$m$
points
$x_{1},\ldots ,x_{m}$
, say, such that
$\Vert x_{i}-x_{j}\Vert _{K}>1$
for all distinct
$i,j$
. It follows that
$-x_{1}+K,\ldots ,-x_{m}+K$
is a strict Minkowski arrangement. This family of translates of
$K$
is clearly pairwise intersecting since all members contain the origin.◻
If
$K$
is
$o$
-symmetric, it follows from Corollary 10 that if
$a,b\in K$
satisfy
$\Vert a-b\Vert _{K}>1$
, then
$\Vert a^{\wedge }-b^{\wedge }\Vert _{K}>1$
. We therefore obtain the lower bound
$h^{\prime }(K)=H^{\prime }(K)=\unicode[STIX]{x1D6FA}((2/\sqrt{3})^{d})$
by normalizing the points
$x_{i}$
in the proof above. When
$K$
is not
$o$
-symmetric, the probabilistic argument above can be adapted to obtain the slightly worse lower bound
$h^{\prime }(K)=\unicode[STIX]{x1D6FA}((2/\sqrt{3})^{d}/d^{2})$
of Theorem 4. The proof is technically more involved, and the details are as follows.
Proof of Theorem 4.
We first assume that
$o$
is the centroid of
$K$
. By Lemma 6,
$\unicode[STIX]{x1D703}(K,o)\leqslant d$
, and hence
$\Vert -x\Vert _{K}\leqslant d\Vert x\Vert _{K}$
for all
$x\in \mathbb{R}^{d}$
. Let
$k\in \mathbb{N}$
, to be fixed later, and choose
$k$
points
$x_{1},\ldots ,x_{k}$
independently and uniformly from
$K$
. Let
$\unicode[STIX]{x1D6FF}$
be such that
$\text{e}^{\unicode[STIX]{x1D6FF}d}=(d+4)/(d+1)$
(and thus
$\unicode[STIX]{x1D6FF}\sim 3/d^{2}$
). Then the expected number of points
$x_{i}$
such that
$\Vert x_{i}\Vert _{K}\leqslant 1-\unicode[STIX]{x1D6FF}$
(we call these points short) equals
$$\begin{eqnarray}(1-\unicode[STIX]{x1D6FF})^{d}k<\text{e}^{-\unicode[STIX]{x1D6FF}d}k=\biggl(1-\frac{3}{d+4}\biggr)k.\end{eqnarray}$$
We say that an ordered pair
$(x_{i},x_{j})$
,
$i\neq j$
, is close if
$\Vert x_{i}-x_{j}\Vert _{K}\leqslant 1+(d+1)\unicode[STIX]{x1D6FF}$
. Then, by Theorem 16, the expected number of ordered close pairs is less than
$$\begin{eqnarray}\displaystyle & & \displaystyle k^{2}\biggl(\frac{(1+(d+1)\unicode[STIX]{x1D6FF})^{2}(4-(1+(d+1)\unicode[STIX]{x1D6FF})^{2})}{4}\biggr)^{d/2}\nonumber\\ \displaystyle & & \displaystyle \quad <k^{2}\biggl(\frac{\sqrt{3}}{2}\biggr)^{d}\biggl(1+\frac{4}{3}(d+1)\unicode[STIX]{x1D6FF}\biggr)^{d/2}\nonumber\\ \displaystyle & & \displaystyle \quad <k^{2}\biggl(\frac{\sqrt{3}}{2}\biggr)^{d}\text{e}^{2\unicode[STIX]{x1D6FF}d(d+1)/3}=k^{2}\biggl(\frac{\sqrt{3}}{2}\biggr)^{d}\biggl(\frac{d+4}{d+1}\biggr)^{2(d+1)/3}\nonumber\\ \displaystyle & & \displaystyle \quad <\text{e}^{2}k^{2}\biggl(\frac{\sqrt{3}}{2}\biggr)^{d}.\nonumber\end{eqnarray}$$
Thus, if we delete each short point, as well as one member of each close pair, then the expected number
$m$
of points left is at least
$$\begin{eqnarray}m\geqslant k\biggl(\frac{3}{d+4}-\biggl(\frac{\sqrt{3}}{2}\biggr)^{d}\text{e}^{2}k\biggr).\end{eqnarray}$$
To maximize this quadratic expression in
$k$
, we set
$k=\frac{1}{2}(2/\sqrt{3})^{d}(3/\text{e}^{2}(d+4))$
. Thus, there exist at least
$$\begin{eqnarray}m\geqslant \biggl(\frac{2}{\sqrt{3}}\biggr)^{d}\frac{9}{4\text{e}^{2}(d+4)^{2}}\end{eqnarray}$$
points
$x_{1},\ldots ,x_{m}\in K$
such that
$\Vert x_{i}\Vert >1-\unicode[STIX]{x1D6FF}$
for each
$i$
and
$\Vert x_{i}-x_{j}\Vert _{K}>1+(d+1)\unicode[STIX]{x1D6FF}$
for each pair of distinct
$i,j$
. Normalize these points to obtain
$$\begin{eqnarray}x_{1}^{\wedge }=\frac{1}{\Vert x_{1}\Vert _{K}}x_{1},\ldots ,x_{m}^{\wedge }=\frac{1}{\Vert x_{m}\Vert _{K}}x_{m}\in \operatorname{bd}K.\end{eqnarray}$$
Note that
$\Vert x_{i}^{\wedge }-x_{i}\Vert _{K}<\unicode[STIX]{x1D6FF}$
, and hence
$\Vert x_{i}-x_{i}^{\wedge }\Vert _{K}<d\unicode[STIX]{x1D6FF}$
. By the triangle inequality, for distinct
$i,j$
,
$$\begin{eqnarray}\displaystyle \Vert x_{i}^{\wedge }-x_{j}^{\wedge }\Vert _{K} & {\geqslant} & \displaystyle \Vert x_{i}-x_{j}\Vert _{K}-\Vert x_{i}-x_{i}^{\wedge }\Vert _{K}-\Vert x_{j}^{\wedge }-x_{j}\Vert _{K}\nonumber\\ \displaystyle & {>} & \displaystyle 1+(d+1)\unicode[STIX]{x1D6FF}-d\unicode[STIX]{x1D6FF}-\unicode[STIX]{x1D6FF}=1.\nonumber\end{eqnarray}$$
Therefore, the requirements of Definition 7 are satisfied.
Next, we reduce the case when
$o$
is an arbitrary point in
$\operatorname{int}(K)$
to the case where
$o$
is the centroid of
$K$
. By Lemma 15, there is an orthogonal projection
$\unicode[STIX]{x1D70B}:\mathbb{R}^{d}\rightarrow H$
, where
$H$
is a linear subspace of dimension
$d-1$
such that
$\unicode[STIX]{x1D70B}(K)$
has centroid
$o$
. By what was shown above, there exist
$m\geqslant (2/\sqrt{3})^{d-1}9/(4\text{e}^{2}(d+3)^{2})$
points
$y_{1},\ldots ,y_{m}\in \operatorname{bd}\unicode[STIX]{x1D70B}(K)$
such that
$\Vert y_{1}-y_{j}\Vert _{\unicode[STIX]{x1D70B}(K)}>1$
for all distinct
$i,j$
. For each
$i$
, choose
$p_{i}\in \unicode[STIX]{x1D70B}^{-1}(y_{i})\in K$
. Since
$\Vert x\Vert _{K}\geqslant \Vert \unicode[STIX]{x1D70B}(x)\Vert _{\unicode[STIX]{x1D70B}(K)}$
for all
$x\in \mathbb{R}^{d}$
, we obtain that
$p_{1},\ldots ,p_{m}\in \operatorname{bd}K$
satisfy
$\Vert p_{i}-p_{j}\Vert _{K}\geqslant \Vert y_{1}-y_{j}\Vert _{\unicode[STIX]{x1D70B}(K)}>1$
for all distinct
$i,j$
. This finishes the proof of Theorem 4 in the general case. ◻
