## Borsuk’s Conjecture

Karol Borsuk conjectured in 1933 that every bounded set in $R^d$ can be covered by $d+1$ sets of smaller diameter.  Jeff Kahn and I found a counterexample in 1993. It is based on the Frankl-Wilson theorem.

Let $\cal G$ be the set of $\pm 1$ vectors of length $n$. Suppose that $n=4p$ and $p$ is a prime, as the conditions of Frankl-Wilson theorem require. Let ${\cal G'} = \{(1/\sqrt n)x:x \in {\cal G}\}$. All vectors in ${\cal G}'$ are unit vectors.

Consider the set $X=\{x \otimes x: x \in {\cal G}'\}$. $X$ is a subset of $R^{n^2}$.

Remark: If $x=(x_1,x_2,\dots,x_n)$, regard $x\otimes x$ as the $n$ by $n$ matrix with entries $(x_ix_j)$.

It is easy to verify that:

Claim: $ = ^2$.

It follows that all vectors in $X$ are unit vectors, and that the inner product between every two of them is nonnegative. The diameter of $X$ is therefore $\sqrt 2$. (Here we use the fact that the square of the distance between two unit vectors $x$ and $y$ is 2 minus twice their inner product.)

Suppose that $Y \subset X$ has a smaller diameter. Write $Y=\{x \otimes x: x \in {\cal F}\}$ for some subset $\cal F$ of $\cal G$. This means that $Y$ (and hence also $\cal F$) does not contain two orthogonal vectors and therefore by the Frankl-Wilson theorem

$|{\cal F}| \le U=4({{n} \choose {0}}+{{n}\choose {1}}+\dots+{{n}\choose{p-1}})$.

It follows that the number of sets of smaller diameter needed to cover $X$ is at least $2^n / U$. This clearly refutes Borsuk’s conjecture for large enough $n$. Sababa.

Let me explain in a few more words how $U$ looks like when $n$ is large. the dominant binomial coefficient in the the sum defining $U$ is ${{n} \choose {p-1}}$. (Since $p=n/4$ every binomial coefficient in the sum is smaller than half the next binomial coefficient.) ${{n} \choose {p-1}}$ is smaller than ${{n} \choose {n/4}}$. When $n$ is large this binomial coefficient equal to $2^{n(H(1/4)+o(1)}$, where $H$ is the entropy function. $H(1/4)=-(1/4)\log_2(1/4)-(3/4)\log_2(3/4)=0.811..$ To verify it and even to get better estimates you can use Stirling’s formula.

We will further discuss Borsuk’s conjecture and related problems in a later post.

An extremely flattering I was very happy to read a description of the work of Jeff Kahn and me in the context of surprises in mathematics and theoretical computer science can be found in Dick’s Lipton’s blog.