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 how looks like when is large. the dominant binomial coefficient in the the sum defining is . (Since every binomial coefficient in the sum is smaller than half the next binomial coefficient.) is smaller than . When is large this binomial coefficient equal to , where is the entropy function. 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.