1 Introduction
The problem of packing congruent spherical caps on a sphere has received considerable attention, because the centers of the caps form spherical codes which have many applications [Reference Conway and Sloane5]. The corresponding covering problem is not that well studied. The general results of Rogers [Reference Rogers14, Reference Rogers15] have been improved in this context by Böröczky and Wintsche [Reference Böröczky, Wintsche, Aronov, Basu, Pach and Sharir4] and later by Dumer [Reference Dumer9] and Naszódi [Reference Naszódi12]. All these results specifically target higher dimensions, and underperform in the lower dimensions compared to concrete constructions of covering sets derived from lattices or from other regular or symmetric arrangements of points. Motivated by applications in certain problems from convex geometry considered by Bezdek and Kiss [Reference Bezdek and Kiss2], our goal in this work is to construct several spherical coverings with some additional properties such as origin symmetry and a specific covering radius. Our constructions, as well as the method for calculation of the covering radius, may also be of independent interest. Now, let us describe the corresponding geometric problems.
A convex body in the n-dimensional Euclidean space
${\mathbb {E}}^n$
is a convex compact set with nonempty interior. A point x on the boundary of a convex body K in
${\mathbb {E}}^n$
is illuminated along a direction
$\xi \in {\mathbb {S}}^{n-1}$
(where
${\mathbb {S}}^{n-1}$
is the unit sphere in
${\mathbb {E}}^n$
) if the ray
$\{x+t\xi :t\ge 0 \}$
intersects the interior of K. A convex body K is illuminated along a set of directions
$E\subset {\mathbb {S}}^{n-1}$
if for any point of the boundary of K, there is a direction
$\xi \in E$
such that this point is illuminated by
$\xi $
. The illumination number
$I(K)$
is defined as the smallest cardinality of a set of directions illuminating K. The well-known illumination conjecture is that for any convex body
$K\subset {\mathbb {E}}^n$
, one has
$I(K)\le 2^n$
. Note that the illumination number of an n-cube is
$2^n$
. An equivalent formulation of the illumination conjecture is that any convex body
$K\subset {\mathbb {E}}^n$
can be covered by at most
$2^n$
smaller homothetic copies of K. For a survey on these conjectures, also known as the (Levi–)Hadwiger conjecture or Gohberg–Markus covering conjecture, see [Reference Bezdek, Khan, Conder, Deza and Weiss1] and the references therein; for recent results in the asymptotic case, see [Reference Huang, Slomka, Tkocz and Vritsiou10]; for recent results in the low-dimensional case, see [Reference Prymak and Shepelska13]; and for a computer-based approach, see [Reference Zong17].
A related concept to illumination is that of X-raying a convex body introduced by Soltan. A point
$x\in K$
, where
$K\subset {\mathbb {E}}^n$
is a convex body, is X-rayed along a direction
$\xi \in {\mathbb {S}}^{n-1}$
if the line
$\{x+t\xi : t\in {\mathbb {R}} \}$
intersects the interior of K. K is X-rayed by
$E\subset {\mathbb {S}}^{n-1}$
if for every point
$x\in K$
, there is a direction
$\xi \in E$
such that x is X-rayed along
$\xi $
. The X-ray number
$X(K)$
is the smallest cardinality of a set of directions X-raying K. X-raying conjecture by Bezdek and Zamfirescu is that
$X(K)\le 3\cdot 2^{n-2} $
for any convex body
$K\subset {\mathbb {E}}^n$
. An example achieving the bound is the convex hull of the vertices of an n-cube with one
$(n-2)$
-dimensional face removed. The reader can refer to [Reference Bezdek and Kiss2] for further details.
The connection between the X-raying and the illumination problems is not hard to observe: one always has
$X(K)\le I(K)\le 2X(K)$
for any convex body K.
Convex body has constant width if its projection onto any line has length independent of the choice of the direction of the line. This class of convex bodies plays a very important role in convex geometry and other areas of mathematics (see, e.g., [Reference Martini, Montejano and Oliveros11] for a comprehensive exposition). We define
$X_n^w$
and
$I_n^w$
as the largest values of
$X(W)$
and
$I(W)$
, respectively, where W varies over all convex bodies of constant width in
${\mathbb {E}}^n$
. A natural problem considered by Bezdek and Kiss in [Reference Bezdek and Kiss2] is to confirm X-raying and illumination conjectures for the class of convex bodies of constant width, e.g., to establish
$X_n^w\le 2^{n-1}$
.
Using an interesting probabilistic argument, Schramm proved in [Reference Schramm16] that asymptotically
$I_n^w < n^{1.5+o(1)} (3/2)^{n/2}$
as
$n\to \infty $
. He provided an explicit estimate for all n, namely (see [Reference Schramm16, p. 188]),
$$ \begin{align} I_n^w < 1+4n\sqrt{\pi n/3} \ln(13+16n) \left(\frac32\right)^{n/2}. \end{align} $$
If
$n\ge 16$
, the right-hand side of (1.1) is less than
$3\cdot 2^{n-2}$
, and we always have
$X_n^w\le I_n^w$
, so (1.1) confirms the X-raying and illumination conjectures for the class of convex bodies of constant width and dimensions
$n\ge 16$
. (We remark that the simpler estimate than (1.1) given in [Reference Schramm16, Theorem 1] is not sufficient for
$n=16$
, and, on the other hand, further fine-tuning of parameters and constants in the proof in [Reference Schramm16] does not seem to allow to confirm the conjectures of our interest for
$n=15$
.)
Returning to small dimensions, for
$n\le 6$
, the inequality
$X_n^w\le 2^{n-1}$
was confirmed by Bezdek and Kiss in [Reference Bezdek and Kiss2] by reduction to a specific covering problem on the sphere. Let us explicitly formulate this reduction which is valid in all dimensions. For a finite set
$A\subset {\mathbb {S}}^{n-1}$
, the covering radius of A is the smallest
$r>0$
such that the union of spherical balls of radii r centered at the points of A is
${\mathbb {S}}^{n-1}$
. A is origin-symmetric if
$-A=A$
. Let
$w_n$
denote the smallest cardinality of an origin-symmetric set
$A\subset {\mathbb {S}}^{n-1}$
with covering radius not exceeding
$\arccos \sqrt {\tfrac {n-1}{2n}}$
.
Lemma 1.1 [Reference Bezdek and Kiss2, Lemma 3.1]
$X^w_n\le \frac 12 w_n$
.
Let us briefly describe two main ingredients in the proof of this lemma; full details can be found in [Reference Bezdek and Kiss2]. The key concept is that of the Gauss image of a face (intersection of the boundary with a supporting hyperplane) of a convex body, which is the set of outer unit normal vectors of all supporting hyperplanes containing the face (see also [Reference Martini, Montejano and Oliveros11, p. 35] for the simpler case of smooth boundary). If the Gauss image (which is a subset of the unit sphere) of any face of a convex body can be covered by an appropriate spherical cap, then an estimate on the X-ray number of the body follows, as established in [Reference Bezdek and Kiss2, Lemma 2.4]. The second ingredient, which was used in [Reference Schramm16] as well, is a nice geometric property of convex bodies of constant width stating that the angle between any two outer unit normal vectors of supporting hyperplanes at the same point of the boundary is at most
$\pi /3$
. The value
$\arccos \sqrt {\tfrac {n-1}{2n}}$
arises as the complementary angle to the circumradius of a regular
$(n-1)$
-dimensional spherical simplex of edge length
$\pi /3$
.
It was shown in [Reference Bezdek and Kiss2] that
$w_4\le 12$
and
$w_n\le 2^n$
, for
$n=5,6$
, and was asked if this inequality can be extended to
$7\le n\le 15$
. We show by explicit construction that
$w_n< 2^n$
, for
$5\le n\le 15$
, and thus completely confirm the X-raying and the illumination conjectures for the class of convex bodies of constant width in any dimension. X-raying problem is connected to a theorem of Danzer and Grünbaum [Reference Danzer and Grünbaum7] on antipodal convex polytopes (see [Reference Bezdek and Kiss2, Section 4]). Furthermore, X-raying problem has found applications in approximation theory [Reference Dai and Prymak6, Section 7] where explicit upper bounds on the number of directions required for X-raying are of interest.
Our main result is the following theorem.
Theorem 1.2
$w_5\le 30$
,
$w_6\le 44$
,
$w_7\le 112$
,
$w_8\le 240$
,
$w_9\le 470$
,
$w_{10}\le 692$
,
$w_{11}\le 2024$
,
$w_{12}\le 3832$
,
$w_{13}\le 7074$
,
$w_{14}\le 11132$
, and
$w_{15}\le 16442$
.
Our constructions started from an observation that the (normalized) minimal norm vectors of the
$E_8$
lattice (see, e.g., [Reference Conway and Sloane5, Section 4.8.1, p. 120]) settle the problem for
$n=8$
. We further explored various origin-symmetric systems of vectors which are invariant under permutations of coordinates and were able to solve the problem for the outstanding dimensions and also improve the known results from [Reference Bezdek and Kiss2] for
$n=5,6$
.
An important part of the proof which can be of independent interest is an efficient procedure for computation of covering radius of a given point system which is based on the computation of the polar of a convex polytope (see Section 2). SageMath [8] code we used for computations can be found in the Appendix of the preprint [Reference Bondarenko, Prymak and Radchenko3] of this article.
2 Computation of covering radius
Recall that the polar of a convex body (convex compact set with nonempty interior)
$K\subset {\mathbb {E}}^n$
containing the origin is defined as
$K^\circ =\{x\in {\mathbb {E}}^n: \langle x, y\rangle \le 1\ \forall y\in K \}$
, where
$\langle \cdot ,\cdot \rangle $
is the canonical Euclidean scalar product. By
${\textrm {conv}}(A)$
we denote the convex hull of A, by
$\|\cdot \|$
the Euclidean norm, and by
${\textrm {ext}}(K)$
we denote the set of extreme points of a convex set K. In the case K is a polytope,
${\textrm {ext}}(K)$
is the set of its vertices.
Lemma 2.1 Suppose a finite subset
$A\subset {\mathbb {S}}^{n-1}$
is such that the interior of
$K:={\textrm {conv}}(A)$
contains the origin. Then, the covering radius of A equals
$\arccos ((\max \{\|x\|:x\in {\textrm {ext}}(K^\circ )\})^{-1})$
.
Proof Because
$K^\circ $
is a convex polytope and
$x\mapsto \|x\|$
is a convex function, by Krein–Milman theorem,
$\max \{\|x\|:x\in {\textrm {ext}}(K^\circ )\} = \max \{\|x\|:x\in K^\circ \}=:\lambda $
. A point
$x\in {\mathbb {S}}^{n-1}$
is not covered by the union of spherical balls of radii r centered at the points of A if and only if
$\langle x,y \rangle < \cos r$
for any
$y\in A$
, i.e.,
$(\cos r)^{-1}x$
lies in the interior of
$K^\circ $
. The covering radius of A is then
$ \sup \{r>0: (\cos r)^{-1}{\mathbb {S}}^{n-1} \cap K^\circ \ne \emptyset \}=\lambda , $
and the claim of the lemma follows.█
Under the hypothesis of the lemma,
$K^\circ $
is a convex polytope given as the intersection of half-spaces. Therefore, the covering radius of A can be efficiently computed after the half-space representation of
$K^\circ $
is converted into the vertex representation. A function performing such a conversion is readily available in most softwares for mathematical computations, e.g., MATLAB or SageMath.
If A possesses certain symmetries, then it may be possible to restrict the computations only to a certain part of the polytope. By
$O(n)$
we denote the group of distance-preserving transformations of
${\mathbb {E}}^n$
that preserve origin. For
${\mathcal {T}}\subset O(n)$
, the notation
$\langle {\mathcal {T}}\rangle $
stands for the subgroup of
$O(n)$
generated by
${\mathcal {T}}$
.
Lemma 2.2 Suppose
${\mathcal {T}}\subset O(n)$
is finite and
$C\subset {\mathbb {E}}^n$
is such that
$\bigcup \{T(C):T\in \langle {\mathcal {T}}\rangle \}={\mathbb {E}}^n$
. Furthermore, suppose that for a finite subset
$A\subset {\mathbb {S}}^{n-1}$
, the interior of
$K:={\textrm {conv}}(A)$
contains the origin and
$T(A)=A$
for any
$T\in {\mathcal {T}}$
. Then, the covering radius of A equals
$\arccos ((\max \{\|x\|:x\in C\cap {\textrm {ext}}(K^\circ )\})^{-1})$
.
Proof Clearly, under the hypotheses of the lemma,
$T(K^\circ )=K^\circ $
and
$T({\textrm {ext}}(K^\circ ))={\textrm {ext}}(K^\circ )$
for any
$T\in \langle {\mathcal {T}}\rangle $
. By Theorem 2.1, the covering radius of A equals
$\arccos ((\max \{\|x\|:x\in {\textrm {ext}}(K^\circ )\})^{-1})$
. Suppose the maximum is attained at a point
$x_0 \in {\textrm {ext}}(K^\circ )$
. Because
$\bigcup \{T(C):T\in \langle {\mathcal {T}}\rangle \}={\mathbb {E}}^n$
, there exists
$T\in \langle {\mathcal {T}}\rangle $
such that
$x_0\in T(C)$
, then
$T^{-1}x_0\in C\cap {\textrm {ext}}(K^\circ )$
. We have
$\|x_0\|=\|T^{-1}x_0\|\le \max \{\|x\|:x\in C\cap {\textrm {ext}}(K^\circ )\} \le \max \{\|x\|:x\in {\textrm {ext}}(K^\circ )\}= \|x_0\|$
, and the lemma is proved.█
For example, if A is origin-symmetric and invariant under permutations of coordinates, we can take
$C=\{x\in {\mathbb {E}}^n: x_1\ge 0, x_1\ge x_2\ge \dots \ge x_n \}$
, which is applicable to all the cases in the next section. As C is given as intersection of half-spaces,
$C\cap K^\circ $
is a convex polytope, and
$\max \{\|x\|:x\in C\cap {\textrm {ext}}(K^\circ )\}=\max \{\|x\|:x\in {\textrm {ext}}(C\cap K^\circ )\}$
.
3 Proof of Theorem 1.2
We write
$(x_1^{n_1},x_2^{n_2},\dots )$
to denote a vector that has some
$n_i$
coordinates equal to
$x_i$
; for example,
$(2,2,-1,0,\dots ,0)\in {\mathbb {E}}^n$
can be written as
$(2^2,-1,0^{n-3})$
. For each n,
$5\le n\le 15$
, we construct an appropriate system of points
$A\subset {\mathbb {S}}^{n-1}$
, so that Theorem 1.1 is applicable. The set A is obtained by taking all possible permutations of coordinates and symmetries about the origin of a certain smaller generating set of vectors. For convenience, we list the vectors of the generating set on a sphere which is not necessarily unit; the generating set can be normalized using a scalar multiple. Covering radii are found on a computer using the techniques of Section 2 and the code supplied in [Reference Bondarenko, Prymak and Radchenko3, Appendix]. The constructions and the results are given in Table 1 (
$|A|$
denotes the cardinality of A), where the decimal approximations are stated with the precision of five digits, while actual computational precision is double floating point arithmetic.
Constructions and covering radii.
For the dimensions
$5\le n\le 10$
, we computed the precise values of the covering radius by using exact computations in the field of rational numbers or in appropriate quadratic fields. Note that for
$n=5$
, the covering radius is equal to the one required by Theorem 2.1. All coordinates in our constructions are given by algebraic numbers, so with appropriate computational resources, the covering radii can be computed precisely.
The running time of our script is well under a minute on a modern personal computer even for the case
$n=15$
if floating point arithmetic is used. Getting precise results through symbolic computations takes longer for
$n=9$
(5 minutes) and
$n=10$
(1 hour).
