Borsuk’s Conjecture

Posted on June 21, 2009 by Gil Kalai

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 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.

This entry was posted in Combinatorics and tagged , . Bookmark the permalink.

7 Responses to Borsuk’s Conjecture

  2. Pingback: Some musings around Borsuk’s conjecture « Konrad Swanepoel’s blog

  3. rjlipton says:
    September 30, 2009 at 3:57 pm

    I disagree. I think my post is well deserved. One of the cool results of all time. And one of the biggest surprises.

    dick

    Reply

  4. Pingback: Around Borsuk’s Conjecture 1: Some Problems | Combinatorics and more

  5. Pingback: Andriy Bondarenko Showed that Borsuk’s Conjecture is False for Dimensions Greater Than 65! | Combinatorics and more

  6. Pingback: Around Borsuk’s Conjecture 3: How to Save Borsuk’s conjecture | Combinatorics and more

  7. Pingback: Some Mathematical Puzzles that I encountered during my career | Combinatorics and more

Leave a comment