Progress Around Borsuk’s Problem

Combinatorics and more 2023-12-05

I was excited to see the following 5-page paper:

Convex bodies of constant width with exponential illumination number by Andrii Arman, Andrii Bondarenko, and Andriy Prymak

Abstract: We show that there exist convex bodies of constant width in $\mathbb E ^n$ with illumination number at least $(\cos (\pi/14)+o(1)^{-n}$ , answering a question by G. Kalai. Furthermore, we prove the existence of finite sets of diameter 1 in $\mathbb E^n$ which cannot be covered by $(2/\sqrt{3}+o(1))^{n}$ balls of diameter 1, improving a result by J. Bourgain and J. Lindenstrauss.

Let me tell you a little about it. (I will switch from $n$ to $d$ .) Borsuk problem asks for the smallest integer $f(d)$ so that every set of diameter 1 in $\mathbb R^d$ can be covered by $f(d)$ sets of smaller diameter.

The best asymptotic upper bound from 1987 by Oded Schramm is exponential in $d$ ,

$f(d) \le (\sqrt {3/2}+o(1))^d.$

(Note that $\sqrt {3/2}=1.2247...$ .) There is also an 1982 elegant upper bound by Marek Lassak

$f(d) \le 2^{d-1}+1$ .

There are two different proofs for the upper bound $f(d) \le (\sqrt {3/2}+o(1))^d,$ and both proofs give stronger results.

The first proof by Oded Schramm is based on covering a set of constant width by smaller homothets of the same set. It has been an outstanding question since the late 80’s if the assertion of Schramm’s result could be strengthened with $(\sqrt {3/2}+o(1))^d$ being replaced with $(1+o(1))^d$ .

Arman, Bondarenko, and Prymak have now showed that this is not the case: they constructed a set of diameter 1 that cannot be covered by less than

$(1. 026.. + o(1))^d$

homothets of smaller diameter. Here 1.026.. stands for $1/cos(\pi /14)$ .

The second 1991 proof for the upper bound $f(d) \le (\sqrt {3/2}+o(1))^d,$ by Jean Bourgain and Joram Lindenstrauss is based on covering a set of diameter 1 with balls of diameter 1. (A ball of diameter 1 can be covered by $d+1$ balls of smaller diameter.) For covering by balls, it was known that the upper bound cannot be pushed down to $(1+o(1))^d$ ; there was an old result from the mid 1960s by Danzer showing that we need at least $1.001^d$ balls of diameter 1 to cover an arbitrary set of diameter 1 in $\mathbb R^d$ . In their paper along with the upper bound, Bourgain and Lindenstrauss improved Danzer’s $1.001^d$ to $1.0645^d$ . The second theorem of the paper improves 1.0645 to $2/\sqrt 3$ which is 1.1547.

ABP

Some more comments:

The first (main) result of Arman, Bondarenko, and Prymak was already improved by Alexey Glazyrin in his 4-page Note on illuminating constant width bodies who improved the constant 1.026… to $\approx$ 1.047… which stands for $\frac {1}{4} \sqrt {\frac {1}{6}(111-\sqrt {33})}$ .
Schramm’s result as well as the new result are formulated in terms of illumination numbers. “A boundary point $x$ of a convex $n$ -dimensional body $B$ is said to be illuminated by a direction (unit vector) $\ell$ if the ray from $x$ in the direction of $\ell$ intersects the interior of $B.$ The set of directions $\cal L$ illuminate $B$ if each boundary point of $B$ is illuminated by some direction from $\cal L$ . A natural question is to determine the minimal size of an illuminating set, also called an illumination number, for a given $B$ or for a given class of convex $n$ -dimensional bodies.” The illumination number of a convex set $B$ equals the number of homothets of smaller diameter needed to cover $B$ .
Let $K$ be a set of diameter one. Let ${\cal B}(K)$ be the class of sets of diameter one of the form $\alpha K + \beta B$ . It is interesting if by using such sets (of diameter 1) the upper bound of $(\sqrt {3/2}+o(1))^n$ could be pushed down to $(\sqrt {3/2}-\delta)^n$ , for some $\delta >0$ . It is also interesting if we can find a lower bound for covering with such sets of the form $(1+\delta)^d$ .
We had several posts about and around Borsuk’s problem. But I missed lot of very nice results and questions, in the blog and even in my survey article from 2015.
Here is a quick summary of the best known (asymptotic) lower bounds for Borsuk’s problem and related problems. The Frankl-Wilson bound for the double cap conjecture is $1.13975...^{-n}$ and Raigorodskii’s (world record) lower bound is $1.1547...^{-n}$ . Raigorodskii’s (world record) bound for the double cup conjecture gives a bound of $1.225^{\sqrt d}$ for the Borsuk problem.
Borsuk conjectured that $f(d)=d+1$ , namely, every set of diameter 1 can be covered by $d+1$ sets of smaller diameter. The smallest dimension where this is known to be false is 64 and this was proved by Thomas Jenrich.
Schramm asked if there are convex sets of constant width with exponentially smaller volume compared to a ball of the same width. (See this mathoverflow question.) He also asked the question for spherical sets. A negative answer will push (as far as I remember) the constant in his bound from $\sqrt {3/2}$ to $\sqrt {4/3}=1.155..$ ).

Glazyrin