Borsuk’s Conjecture

Posted on June 21, 2009 by

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.

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

4 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

Leave a Reply

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

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com 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 )

Cancel

Connecting to %s