Borsuk’s Conjecture « Combinatorics and more

Borsuk’s Conjecture

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.

Tags: Borsuk, Borsuk's conjecture

This entry was posted on June 21, 2009 at 4:29 pm and is filed under Combinatorics. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “Borsuk’s Conjecture”

Gil Kalai Says:
June 21, 2009 at 9:22 pm
Here is a wikipedia article on the problem http://en.wikipedia.org/wiki/Borsuk%27s_conjecture
Some musings around Borsuk’s conjecture « Konrad Swanepoel’s blog Says:
June 23, 2009 at 6:30 pm
[...] is false if the dimension is sufficiently large. For a short explanation by Gil Kalai, click here. For a wonderful (very) short story on how their proof came about, click here. The lowest dimension [...]
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

Combinatorics and more

Borsuk’s Conjecture

3 Responses to “Borsuk’s Conjecture”

Leave a Reply