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

6 thoughts on “Borsuk’s Conjecture

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

  2. rjlipton

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


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

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

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s