# 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 Continue reading