Karol Borsuk conjectured in 1933 that every bounded set in can be covered by sets of smaller diameter. Jeff Kahn and I found a counterexample in 1993. It is based on the Frankl-Wilson theorem.
Let be the set of vectors of length . Suppose that and is a prime, as the conditions of Frankl-Wilson theorem require. Let . All vectors in are unit vectors.
Consider the set . is a subset of .
Remark: If , regard as the by matrix with entries .
It is easy to verify that:
It follows that all vectors in are unit vectors, and that the inner product between every two of them is nonnegative. The diameter of is therefore . (Here we use the fact that the square of the distance between two unit vectors and is 2 minus twice their inner product.)
Suppose that has a smaller diameter. Write for some subset of . This means that (and hence also ) does not contain two orthogonal vectors and therefore by the Frankl-Wilson theorem
It follows that the number of sets of smaller diameter needed to cover is at least . This clearly refutes Borsuk’s conjecture for large enough . Sababa.
Let me explain in a few more words Continue reading