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: <x \otimes x,y\otimes y> = <x,y>^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