An exponential improvement for Borsuk's problem

The result and the ideas

Let $b(n)$ be the least integer such that every bounded set of positive diameter in $\mathbb{R}^{n}$ can be partitioned into at most $b(n)$ sets of strictly smaller diameter. Schramm [8] and Bourgain–Lindenstrauss [2] established the classical bound

The purpose of this note is to improve its exponential base with simple constants and a fully explained proof¹. For further background on Borsuk’s problem, see Kalai’s 2015 survey [5].

For a compact nonempty $A\subset S^{n-1}$, write

This is the open positive polar: the directions making an acute angle with every member of $A$. Let $\nu_j$ be probability surface measure on $S^j$. The estimate behind the theorem is the following stable form.

Here $\operatorname{diam}_{S}$ denotes angular diameter, and the choices are uniform over all compact nonempty $A$.

Why this is relevant to partitions. Fix a small $\varepsilon> 0$ and join two points of a diameter-one set whenever their distance is at least $1-\varepsilon$. A direction $v$ selects a point $x$ if $\langle v, x-y\rangle> 0$ for every neighbour $y$: viewed along $v$, the point $x$ lies strictly ahead of all its neighbours. Two neighbours cannot both be selected, because this would require both $\langle v, x-y\rangle> 0$ and $\langle v, y-x\rangle> 0$. The class selected by $v$ therefore has diameter at most $1-\varepsilon$. A collection of directions selecting every point gives a covering by such classes, and assigning each point to one class gives the desired partition.

Within a small neighborhood in the set, collect all unit vectors pointing from nearly diametral neighbours towards points of that neighborhood. Their angular diameter is close to $\pi/3$, and any direction in their open positive polar selects the whole neighborhood. Proposition 1.2 gives a uniform lower bound for the probability of this event. Only exponentially many neighborhoods are needed; a union bound then requires an additional factor of order $n$ in the number of sampled directions.

This is a direct analogue of Schramm’s approach to illuminating bodies of constant width [8]. At a boundary point, the outward unit normals have angular diameter at most $\pi/3$, and the negative of a direction in their open positive polar illuminates that point. Schramm used spherical cap-containment and an antipodal pairing argument to estimate the measure of admissible directions. Discretization and random sampling then gave the exponential base $C = \sqrt{3}/2$, both for illumination and, as a consequence, for Borsuk’s problem.

How the polar estimate improves the exponent. We first prove the polar estimate for the set $A$ in Proposition 1.2 under the exact assumption $\operatorname{diam}_{S} A \le\pi/3$; the small increase of the diameter is handled in § 6. Central projection (also known as gnomonic projection) writes $A$ as

where $p$ is a suitable pole and $L$ lies in the unit ball of $p^{\perp}$. If a unit vector $u\in p^{\perp}$ satisfies $h_{L}(u):=\sup_{x\in L}\langle x,u\rangle\le a$, then

This sector supplies the exponential measure factor $(1+a^{2})^{-n/2}$. The value $a=1/\sqrt{2}$ corresponds to the classical base $\sqrt{3}/2$, so we seek many directions satisfying the stronger inequality with $a=7/10$.

An antipodal pairing first reduces the task to the outer shell $E=\{x\in L:|x|^{2}\ge3/4\}$, losing only a factor two in measure. The lift

makes the shell acute: every pair of lifted vectors has nonnegative scalar product. A self-dual cone $D$ containing the lift has a reflection $R$ which is even, preserves length, and is nonexpansive, meaning $|R(z)-R(w)|\le|z-w|$. Evenness and Gaussian Poincaré force $\mu=ER(G)$ to have length at least $\sqrt{n}/2$. The cone also ensures $R(G)-G\in D$, giving supporting inequalities for every lifted point at once.

We translate $G$ opposite to the horizontal part of $\mu$, by a fraction $k=1/16$ of that mean. The supporting inequalities and the mean bound then show that the direction of the translated horizontal Gaussian is good for the entire shell with probability tending to one. Returning to ordinary Gaussian measure costs a factor at worst $\exp(-n/512-o(n))$. Together with the sector factor, this gives the reciprocal exponential base $e^{-k^{2}/2}/\sqrt{1+a^{2}}$. Once the support bound is established, these two factors improve the classical exponent provided that

For $a=7/10$ and $k=1/16$, the reciprocal base is $e^{-1/512}/\sqrt{149/100}$. Its reciprocal is less than the value $C$ in Theorem 1.1, hence less than $\sqrt{3}/2$.

Sources of the ideas. The study of small spherical bodies of constant width by Hall, Prymak and Sujsuntinukul [3], including Gaussian methods near the central width $\pi/2$, provided a crucial context for this work. The central projection and antipodal pairing follow Schramm’s method [8]. The outer-shell pairing used here is a generalization of that idea. The key geometric fact about self-dual cones comes from Moreau’s decomposition [7]: every vector $z$ is the difference of two orthogonal vectors $P_Dz$ and $P_D(-z)$ in the cone $D$, where $P_D$ is the nearest-point projection onto $D$. Replacing their difference by their sum defines the length-preserving folding $R$ and ensures $R(z)-z\in D$. The additional ingredient in the present argument is the radial lift which makes this cone geometry available for the outer shell.

From good directions to smaller-diameter pieces

We first prove Theorem 1.1 from Proposition 1.2. This is Schramm’s discretization and random-direction strategy, expressed directly in terms of partition classes. It uses packing, random sampling, and the observation that two points cannot both lie ahead of each other.

Fix $0<\beta<C^{-1}$ and choose $\delta$ from the proposition. Choose a fixed $0<\varepsilon<1/4$ so small that

After taking a closure and rescaling, it suffices to partition a compact set $K\subset\mathbb{R}^n$ of diameter one. Take a maximal $\varepsilon$-separated family $x_1,\ldots,x_M\in K$ and put $F_i=K\cap B(x_i,\varepsilon)$. These neighborhoods cover $K$. Disjoint balls of radius $\varepsilon/2$ around their centres lie in a ball of radius $1+\varepsilon/2$, so

For each neighborhood consider all directions from a nearly diametral neighbour towards a point in that neighborhood:

If nonempty, $A_i$ is compact. For $u=(x-y)/\lvert x-y\rvert$ and $u'=(x'-y')/\lvert x'-y'\rvert$ in $A_i$,

Thus (3) and Proposition 1.2 give $\nu_{n-1}((A_i)_+)\geq\beta^n$ for all sufficiently large $n$.

Choose

independent directions uniformly distributed on $S^{n-1}$. The probability of missing at least one of the polars $(A_i)_+$ with $A_i\neq\varnothing$ is at most $M(1-\beta^n)^J\leq M\exp(-J\beta^n)<1$. Some choice $v_1,\ldots,v_J$ therefore meets them all.

For a direction $v$ define

If $v\in(A_i)_+$, then $F_i\subset B_v$. If $A_i$ is empty, this inclusion holds for every $v$. Consequently the $B_{v_j}$ cover $K$. If $x,y\in B_v$ had $\lvert x-y\rvert\geq1-\varepsilon$, the definition would give both $\langle v,x-y\rangle>0$ and $\langle v,y-x\rangle>0$, an impossibility. Hence

Assigning each point to the first covering set containing it gives a partition. By (4), $b(n)\leq O_\varepsilon(n)\beta^{-n}$. Letting $\beta\uparrow C^{-1}$ proves the theorem.

Central projection and an outer shell

We now prove Proposition 1.2, starting with the exact diameter assumption $\operatorname{diam}_{\mathbb{S}} A \le\pi/3$, or equivalently $\langle z,z'\rangle\ge1/2$ for all $z,z' \in A$.

Flattening the spherical set

3.1. Flattening the spherical set. Let $q$ be the nearest point of $\operatorname{conv} A$ to the origin and set $p=q/|q|$. For any convex combination $q=\sum_i \alpha_i z_i$,

The nearest-point inequality gives $\langle z,q\rangle\ge|q|^2$ for $z\in A$, so $\langle z,p\rangle\ge1/\sqrt{2}$. Central projection onto the tangent hyperplane $p+p^\perp$ therefore writes

where $\mathbb{B}^{n-1}$ is the unit ball in $p^\perp$. The spherical diameter bound $\operatorname{diam}_{\mathbb{S}} A\le\pi/3$ says that any two points of $A$ have scalar product at least $1/2$. Substituting their representations from (5) therefore gives

For a compact set $F$ put $h_F(u)=\sup_{x\in F}\langle x,u\rangle$; for the empty set use $h_{\varnothing}=-\infty$. Fix throughout

Let $E=\{x\in L:|x|\ge r\}$ and $\mathcal{H}_F=\{u\in\mathbb{S}^{n-2}:h_F(u)\le a\}$.

Support bounds give a spherical sector

3.2. Support bounds give a spherical sector. We first relate the measure of $\mathcal{H}_L$ to that of the positive polar $A_+$. For every $u\in\mathcal{H}_L$ and $0\le\theta<\theta_a:=\arctan(1/a)$, the direction $v_\theta=\cos\theta\,p-\sin\theta\,u$ belongs to $A_+$, because

Figure 1 illustrates the projection and this sector. Polar integration gives

Image not extracted

The ratio is at least $(\sin\theta_a)^n\exp(-o(n))=(1+a^2)^{-n/2}\exp(-o(n))$. For an elementary verification, bound the denominator by $\pi$ and integrate the numerator only over $[\theta_a-1/n,\theta_a]$; this loses only a polynomial factor and an absolute constant. Thus the remaining task is to find enough support directions with threshold $a<1/\sqrt{2}$ to compensate for their probability cost, as in (2).

Pairing opposite directions

3.3. Pairing opposite directions.

Proof. We first exclude $x,y\in L$ and a unit vector $u$ with

Put $z=\sqrt{|x|^2-a^2}$ and $w=\sqrt{|y|^2-a^2}$. Decomposing along $u$ bounds $\langle x,y\rangle$ above by $-a^2+zw$. By (6), $1+\langle x,y\rangle>0$, so this upper bound can be squared after adding one. For the next step, apply Cauchy–Schwarz to the two vectors

Their scalar product is $1-a^2+zw$, so

Consequently,

The expression on the second line increases with $z^2$, and $z^2\le r^2-a^2$. The strict last inequality is exactly

This contradicts (6). Now suppose $u\in\mathcal{H}_E\setminus\mathcal{H}_L$. A point witnessing $h_L(u)>a$ must lie inside the shell. The excluded configuration shows that $h_L(-u)\le a$. Thus $\mathcal{H}_E\subset\mathcal{H}_L\cup(-\mathcal{H}_L)$, and antipodal symmetry proves (9). □

The point of this pairing is that we need not control the inner part of $L$ probabilistically. If an inner point “spoils” a direction already good for the shell, the pairing argument shows that the opposite direction is good for all of $L$.

A lift with one formula

Set $g(t)=7/6-t$ and lift each $x\in E$ to

Geometrically, these points lie on the graph of the paraboloid $s=7/6-|x|^2$, restricted to $x\in E$. The last coordinate is its height above the horizontal space $p^\perp$. These lifted vectors have positive pairwise scalar products. Indeed, for $t = |x|^2$ and $s = |y|^2$ in $[3/4,1]$, (6) gives

The right-hand side is concave in each variable separately, so its minimum occurs at a corner. The three distinct corner values are

All are positive: for the middle value, $7/8-(67/72)^2=47/5184>0$.

The extra coordinate compensates for possible negative products $\langle x,y\rangle$. Its height decreases towards the outside, where (6) already gives better products. This is why a radius-dependent lift is useful.

Reflection and its Gaussian mean

For a closed convex cone $D\subset\mathbb{R}^n$ let $D^*=\{y:\langle x,y\rangle\ge0\ (x\in D)\}$. A cone is acute when $D\subset D^*$ and self-dual when $D=D^*$.

We use the classical completion result of Barker and Foran [1], which is an easy consequence of Zorn’s lemma.

By (11), the closed convex cone generated by the $\lambda_x$ is acute. Complete it to a self-dual cone $D\subset\mathbb{R}^n$. If $E$ is empty, $\mathcal{H}_E$ is the whole sphere and this and the next section may be skipped.

Let $P_D$ be nearest-point projection onto $D$ and put $R=2P_D-I$. Moreau’s decomposition reads

For completeness, if $p_0=P_Dz$, the projection inequality gives $z-p_0\in-D$ and $\langle z-p_0,p_0\rangle=0$. Writing $q_0=p_0-z\in D$, the same inequality shows $q_0=P_D(-z)$. Thus $R(z)=p_0+q_0\in D$: the reflection folds the space into the cone. It also follows that

The folding is illustrated in Figure 2.

Image not extracted

Projection also satisfies

Expanding a square gives $|R(z)-R(w)| \le|z-w|$. For $D=\mathbb{R}^{+}$, we have $R(z)=(|z_1|,\ldots,|z_n|)$: this folds each coordinate to the positive half-line and preserves length. The general reflection has the same three properties in (12).

Let $G$ be a standard Gaussian vector in $\mathbb{R}^{n}$ and $\mu=\mathbb{E}R(G)$. The coordinates of $G$ are independent real Gaussians of mean zero and variance one. We use the ordinary Gaussian Poincaré inequality and its even version:

The first inequality is the standard Gaussian Poincaré inequality; see [4]. For the second, apply [6 Lemma 2.3] to $f-\mathbb{E}f(G)$: an even function is orthogonal to every linear function under Gaussian measure. Both inequalities extend to Lipschitz functions by smooth approximation, preserving evenness when needed. Each coordinate function $R_i$ is even and $1$-Lipschitz. The second inequality therefore gives $\operatorname{Var}R_i(G)\le1/2$. Summing these scalar inequalities yields

Since $\mathbb{E}|R(G)|^{2}=n$, we obtain

This is the source of the gain: an even contraction preserving Gaussian length cannot have a small mean.

A translation makes good directions typical

Let $e$ be the added coordinate direction and let $\Pi$ be orthogonal projection onto $e^{\perp}$. We use the horizontal part and the height of the mean:

The projection $\Pi$ keeps the original horizontal coordinates and discards the coordinate added in the lift. Thus $m$ is the average horizontal position of the folded Gaussian $R(G)$, while $d$ is the absolute value of its average height, on the scale $\sqrt{n}$. Now define the shifted horizontal Gaussian and its direction:

The vector $X$ is shifted opposite to $m$ and rescaled to have typical length of order one. Its direction $U$ is the candidate good support direction; $X\ne0$ almost surely.

The cone projection supplies the auxiliary vector

It is the horizontal part of $P_DG$, shifted by $-km$. Since $P_DG=(G+R(G))/2$, the candidate splits as

The full vector $G-R(G)$ belongs to $-D$, so its scalar product with every lifted point is nonpositive. Thus the second term has an upper support bound supplied by the added coordinate. It remains to control the length of $W$.

Three scalar estimates

Because $R$ is even, $\mathbb{E}\langle\Pi G,\Pi R(G)\rangle=0$. Also $\mathbb{E}_P D G=\mu/2$. Consequently

where (14) was used and

Notice the term linear in $k$ in $A_0$: the geometric improvement starts at first order in the translation, while its measure cost will be quadratic.

The ordinary inequality in (13) and Chebyshev’s inequality now imply, with probability $1-o(1)$,

Here are the details needed for uniformity. The functions $|\Pi G-km|$, $|W|$, and $\langle R(G)-G,e\rangle$ have Lipschitz constants at most $1,1,2$, respectively, so their variances are bounded by $1,1,4$. Each differs from its mean by at most $n^{1/4}$ with probability $1-O(n^{-1/2})$. Moreover,

so $\mathbb{E}|\Pi G-km|\geq\sqrt{n-2}$; and $\mathbb{E}|W|\leq\sqrt{\mathbb{E}|W|^2}$. These observations prove (17), with errors independent of $D$.

Controlling the whole shell at once

For $x\in E$, put $t=|x|^2$. Since $\lambda x\in D=D^*$ and $R(G)-G\in D$,

Combining this with (15), on the single event (17) we obtain, simultaneously for all $x\in E$,

The last inequality is Cauchy–Schwarz applied to $(\sqrt{A_0-B_0d^2},\sqrt{B_0}d)$ and $(\sqrt t,g(t)/(2\sqrt{B_0}))$. This step handles every possible orientation of the mean.

Only a quadratic on $[3/4,1]$ remains. It is convex, and its endpoint values are

Therefore the square of the main term in (18) is less than

It follows that $h_E(U)\leq a$ with probability $1-o(1)$. There is no union bound over $E$: the same three scalar estimates control every point of this possibly infinite set.

Paying for the translation

Let $v=km$ and define

We have just proved $\mathbb{P}(G-v\in\mathcal{E})=1-o(1)$, and $|v|^{2}\le k^{2}n$ by (14). Write $\gamma_n$ for standard Gaussian measure, whose density is $(2\pi)^{-n/2}e^{-|z|^{2}/2}$. This density gives the exact change-of-variables identity

Since $\operatorname{Var}\langle v,G\rangle=|v|^{2}=O(n)$, Chebyshev gives $\mathbb{P}(\langle v,G\rangle<-n^{3/4})=o(1)$. Restricting the expectation to the intersection of the two good events yields

The direction of $\Pi G$ is uniform on $S^{n-2}$, so

This calculation is the whole measure comparison. In probabilistic terms, we first make the desired event typical by shifting a Gaussian, then read its probability under the original Gaussian from the density.

The final bound and stability

Combining (9), (21), and (8) proves the uniform estimate

If $E$ is empty, (9) gives $\nu_{n-2}(\mathcal{H}_L)\ge1/2$, which is stronger than needed. Finally, $e^x<(1-x)^{-1}$ for $0<x<1$, and therefore

Handling a small increase of the diameter

To apply Proposition 1.2 simultaneously to all points in each small neighborhood in § 2, the polar bound must remain valid for angular diameters slightly larger than $\pi/3$. The strict gaps in the pairing and lift estimates allow this enlargement. Suppose now $\langle z,z'\rangle\ge c$, where $c<1/2$ is sufficiently close to $1/2$. The same nearest-point argument writes the image under central projection as $s_cL$, with

For $x,y\in L$ its constraint is

On the compact square $0\le|x|^2,|y|^2\le1$, the right-hand side converges uniformly to that of (6) solved for $\langle x,y\rangle$. The exclusion in Lemma 3.1 has the fixed gap (10), and the lift inequality (11) has strictly positive corner minima. Both therefore hold for $c$ close enough to $1/2$, with exactly the same $a,r,g$. The Gaussian part of the argument is unchanged. Only the sector factor changes, to $(1+s_c^2a^2)^{-n/2}$, so

All errors are uniform. For any $\beta<C^{-1}$, (23) and continuity allow a fixed $c<1/2$ for which the displayed base is greater than $\beta$. Taking $\delta=\arccos c-\pi/3$ proves Proposition 1.2.

References